Preview

Modeling and Analysis of Information Systems

Advanced search
Vol 29, No 2 (2022)
View or download the full issue PDF (Russian)

Discrete Mathematics in Relation to Computer Science

78-91 540
Abstract
One of the problems of modern discrete mathematics is R. Dedekind problem on the number of monotone boolean functions. For other precomplete classes, general formulas for the number of functions of the classes had been found, but it has not been found so far for the class of monotone boolean functions. Within the framework of this problem, there are problems of a lower level. One of them is the absence of a general formula for the number of boolean functions of intersection $MS$ of two classes --- the class of monotone functions and the class of self-dual functions. In the paper, new lower bounds are proposed for estimating the cardinality of the intersection for both an even and an odd number of variables. It is shown that the election function of an odd number of variables is monotone and self-dual. The election function of an even number of variables is determined. Free election functions, which are functions with fictitious variables similar in properties to election functions, are introduced. Then the union of a set of election functions and a set of free election functions is considered, and the cardinality of this union is calculated. The resulting value of the cardinality is proposed as a lower bound for $|MS|$. For the class $MS$ of monotone self-dual functions of an even number of variables, the lower bound is improved over the bounds proposed earlier, and for functions of an odd number of variables, the lower bound for $|MS|$ is presented for the first time.
92-103 389
Abstract

Let $Q_n=[0,1]^n$ be the unit cube in ${\mathbb R}^n$ and let $C(Q_n)$ be a space of continuous functions $f:Q_n\to{\mathbb R}$ with the norm $\|f\|_{C(Q_n)}:=\max_{x\in Q_n}|f(x)|.$ By $\Pi_1\left({\mathbb R}^n\right)$ denote a set of polynomials in $n$ variables of degree $\leq 1$, i. e., a set of linear functions on ${\mathbb R}^n$. The interpolation projector $P:C(Q_n)\to \Pi_1({\mathbb R}^n)$ with the nodes $x^{(j)}\in Q_n$ is defined by the equalities $Pf\left(x^{(j)}\right)= f\left(x^{(j)}\right)$, $j=1,$ $\ldots,$ $ n+1$. Let $\|P\|_{Q_n}$ be the norm of $P$ as an operator from $C(Q_n)$ to $C(Q_n)$. If $n+1$ is an Hadamard number, then there exists a non-degenerate regular simplex having the vertices at vertices of $Q_n$. We discuss some approaches to get inequalities of the form $||P||_{Q_n}\leq c\sqrt{n}$ for the norm of the corresponding projector $P$.

104-114 350
Abstract
The term ``total enumeration degree'' is related to the fact that the e-degree is total if and only if it contains a graph of some total function. In a number of works by the author and a group of mathematicians from the University of Wisconsin-Madison, the so-called ``graph-cototal enumeration degrees'' were considered, i.e. e-degrees containing the complement of the graph of some total function $f(x)$. In this article, the next step is taken -- the enumeration degrees of sets bounded from above or below by a graph of a total function are considered. More precisely, the set A is bounded from above if $A=\\{\\langle x,y\\rangle:y < f(x)\\}$ for some total function $f(x)$ and the set A is bounded from below if $A=\\{\\langle x,y\\rangle:y > f(x)\\}$ for some total function $f(x)$. The article presents a number of results showing the existence of nontotal enumeration degrees containing bounded sets, and the constructed e-degrees are quasi-minimal. An important result is the one stating that bounded sets have the Friedberg property related to the jump inversion.

Theory of Data

116-133 446
Abstract
The paper is devoted to the classification of Russian sentences into four classes: positive, negative, mixed, and neutral. Unlike the majority of modern study in this area, the mixed sentiment class is introduced. Mixed sentiment sentences contain positive and negative sentiments simultaneously.To solve the problem, the following tools were applied: the attention-based LSTM neural network, the dual attention-based GRU neural network, the BERT neural network with several modifications of the output layer to provide classification into four classes. The experimental comparison of the efficiency of various neural networks were performed on three corpora of Russian sentences. Two of them consist of users’ reviews: one with wear reviews and another with hotel reviews. The third corpus contains news from Russian media. The highest weighted F-measure in experiments (0.90) was achieved when using BERT on the wear reviews corpus, as well as the highest weighted F-measure for positive and negative sentences (0.92 and 0.93, respectively). The best classification results for neutral and mixed sentences were achieved on the news corpus. For them F-measure was 0.72 and 0.58, respectively. As a result of experiments, the significant superiority of the BERT transfer network was demonstrated in comparison with older neural networks LTSM and GRU, especially for classification of sentences with weakly expressed sentiments. The error analysis showed that “adjacent” (positive/negative and mixed) classes are worse classified with BERT than “opposite” classes (positive and negative, neutral and mixed).
134-147 447
Abstract
The article is devoted to the task of sentiment detection of Russian sentences. The sentiment is conceived as the author's attitude to the topic of a sentence. This assay considers positive, neutral, and negative sentiment classes, i.e., the task of three-classes classification is solved. The article introduces a rule-based sentiment detection algorithm for Russian sentences. The algorithm is based on the assumption that the sentiment of a phrase can be determined by the sentiments of its parts by the recursive application of appropriate semantic rules to the sentiments of its parts organized as a constituency parse tree. The utilized set of semantic rules was constructed based on a discussion with experts in linguistics. The experiments showed that the proposed recursive algorithm performs slightly worse on the hotel reviews corpus than the adapted rule-based approach: weighted $F_1$-measures are 0.75 and 0.78, respectively. To measure the algorithm efficiency on complex sentences, we created OpenSentimentCorpus based on OpenCorpora, an open corpus of sentences extracted from Russian news and periodicals. On OpenSentimentCorpus the recursive algorithm performs better than the adapted approach does: $F_1$-measures are 0.70 and 0.63, respectively. This indicates that the proposed algorithm has an advantage in case of more complex sentences with more subtle ways of expressing the sentiment.


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)