The 8th Russian Summer School in Information Retrieval (RuSSIR 2014) was held on August 18-22, 2014 in Nizhniy Novgorod, Russia.1 The school was co-organized by the National Research University Higher School of Economics2 and the Russian Information Retrieval Evaluation Seminar (ROMIP)
This paper provides the reader with a report on 9th Russian Summer School in Information Retrieval (RuSSIR 2015).
We propose a concatenated code construction based on convolutional codes. We prove that minimum distance of this construction equals product of free distances of component codes.
The paper considers the phoneme recognition by facial expressions of a speaker in voice-activated control systems. We have developed a neural network recognition algorithm by using the phonetic words decoding method and the requirement for isolated syllable pronunciation of voice commands. The paper presents the experimental results of viseme (facial and lip position corresponding to a particular phoneme) classification of Russian vowels. We show the dependence of the classification accuracy on the used classifier (multilayer feed-forward network, support vector machine, k-nearest neighbor method), image features (histogram of oriented gradients, eigenvectors, SURF local descriptors) and the type of camera (built-in or Kinect one). The best accuracy of speaker-dependent recognition is shown to be 85% for a built-in camera and 96% for Kinect depth maps when the classification is performed with the histogram of oriented gradients and the support vector machine.
Methods of identification of the form of objects based on the signature analysis and invariant to affine transformations are considered. It is shown as these methods it is possible to apply to surface quality assurance. Questions of sensitivity of these methods are considered. Dependences of these methods on noise are brought.
The Cell Formation Problem (CFP) is an important optimisation problem in manufacturing. It has been introduced in the Group Technology (GT) and its goal is to group machines and parts processed on them into production cells minimising the movement of parts to other cells for processing and maximising for each cell the loading of its machines with operations on its parts. We consider one of the computationally hardest formulations of this problem – the CFP with a variable number of cells and the grouping efficacy objective, which is a fractional function. The CFP literature contains many heuristic algorithms, but only a small number of exact approaches especially for this formulation. In the current paper, we present an exact branch-and-bound algorithm for the same hard CFP formulation. To linearise the fractional objective function, we apply the Dinkelbach approach. We have been able to solve 24 of the 35 instances from the well known GT benchmark. For the remaining 11 instances, the difference in the grouping efficacy with the best known solutions is less than 2.6%.
This work is devoted to the investigation of particle acceleration during magnetospheric dipolarizations. A numerical model is presented taking into account the four scenarios of plasma acceleration that can be realized: (A) total dipolarization with characteristic time scales of 3 min; (B) single peak value of the normal magnetic component Bz occurring on the time scale of less than 1 min; (C) a sequence of rapid jumps of Bz interpreted as the passage of a chain of multiple dipolarization fronts (DFs); and (D) the simultaneous action of mechanism (C) followed by the consequent enhancement of electric and magnetic fluctuations with the small characteristic time scale 1 s. In a frame of the model, we have obtained and analyzed the energy spectra of four plasma populations: electrons e, protons Hþ, helium Heþ, and oxygen Oþ ions, accelerated by the above-mentioned processes (A)–(D). It is shown that Oþ ions can be accelerated mainly due to the mechanism (A); Hþ and Heþ ions (and to some extent electrons) can be more effectively accelerated due to the mechanism (C) than the single dipolarization (B). It is found that high-frequency electric and magnetic fluctuations accompanying multiple DFs (D) can strongly accelerate electrons e and really weakly influence other populations of plasma. The results of modeling demonstrated clearly the distinguishable spatial and temporal resonance character of particle acceleration processes. The maximum particle energies depending on the scale of the magnetic acceleration region and the value of the magnetic field are estimated. The shapes of energy spectra are discussed.
Cardiovascular disease associated with metabolic syndrome has a high prevalence, but the mechanistic basis of metabolic cardiomyopathy remains poorly understood. We characterised the cardiac transcriptome in a murine metabolic syndrome (MetS) model (LDLR−/−; ob/ob, DKO) relative to the healthy, control heart (C57BL/6, WT) and the transcriptional changes induced by ACE-inhibition in those hearts. RNA-Seq, differential gene expression and transcription factor analysis identified 288 genes differentially expressed between DKO and WT hearts implicating 72 pathways. Hallmarks of metabolic cardiomyopathy were increased activity in integrin-linked kinase signalling, Rho signalling, dendritic cell maturation, production of nitric oxide and reactive oxygen species in macrophages, atherosclerosis, LXR-RXR signalling, cardiac hypertrophy, and acute phase response pathways. ACE-inhibition had a limited effect on gene expression in WT (55 genes, 23 pathways), and a prominent effect in DKO hearts (1143 genes, 104 pathways). In DKO hearts, ACE-I appears to counteract some of the MetS-specific pathways, while also activating cardioprotective mechanisms. We conclude that MetS and control murine hearts have unique transcriptional profiles and exhibit a partially specific transcriptional response to ACE-inhibition.
Modeling tools provide a valuable support for DNA origami design. However, current solutions have limited application for conformational analysis of the designs. In this work we present a tool for a thorough study of DNA origami structure and dynamics. The tool is based on a novel coarse-grained model dedicated to geometry optimization and conformational analysis of DNA origami. We explored the ability of the model to predict dynamic behavior, global shapes, and fine details of two single-layer systems designed in hexagonal and square lattices using atomic force microscopy, Förster resonance energy transfer spectroscopy, and all-atom molecular dynamic simulations for validation of the results. We also examined the performance of the model for multilayer systems by simulation of DNA origami with published cryo-electron microscopy and atomic force microscopy structures. A good agreement between the simulated and experimental data makes the model suitable for conformational analysis of DNA origami objects. The tool is available at http://vsb.fbb.msu.ru/cosm as a web-service and as a standalone version.
Checking the correctness of distributed systems is one of the most difficult and urgent problems in software engineering. A combined toolset for the verification of real-time distributed systems (RTDS) is described. RTDSs are specified as statecharts in the Universal Modeling Language (UML). The semantics of statecharts is defined by means of hierarchical timed automata. The combined toolset consists of a UML statechart editor, a verification tool for model checking networks of real-time automata in UPPAAL, and a translator of UML statecharts into networks of timed automata. The focus is on the translation algorithm from UML statecharts into networks of hierarchical timed automata. To illustrate the proposed approach to the verification of RTDSs, a toy example of a real-time crossroad traffic control system is analyzed.
We study the computational complexity of the dominating set problem for hereditary graph classes, i.e., classes of simple unlabeled graphs closed under deletion of vertices. Every hereditary class can be defined by a set of its forbidden induced subgraphs. There are numerous open cases for the complexity of the problem even for hereditary classes with small forbidden structures. We completely determine the complexity of the problem for classes defined by forbidding a five-vertex path and any set of fragments with at most five vertices. Additionally, we also prove polynomial-time solvability of the problem for some two classes of a similar type. The notion of a boundary class is a helpful tool for analyzing the computational complexity of graph problems in the family of hereditary classes. Three boundary classes were known for the dominating set problem prior to this paper. We present a new boundary class for it.
We show that the inequality H(A|B, X) + H(A|B, Y) ≤ H(A|B) for jointly distributed random variables A, B, X, Y, which does not hold in general case, holds under some natural condition on the support of the probability distribution of A, B, X, Y. This result generalizes a version of the conditional Ingleton inequality: if for some distribution I(X : Y|A) = H(A|X, Y) = 0, then I(A : B) ≤ I (A : B|X) + I(A : B|Y)+I(X : Y). We present two applications of our result. The first one is the following easy-to-formulate theorem on edge colorings of bipartite graphs: assume that the edges of a bipartite graph are colored in K colors so that each two edges sharing a vertex have different colors and for each pair (left vertex x, right vertex y) there is at most one color a such both x and y are incident to edges with color a; assume further that the degree of each left vertex is at least L and the degree of each right vertex is at least R. Then K LR. The second application is a new method to prove lower bounds for biclique cover of bipartite graphs.
The paper grounds the necessity of much earlier socialization of children in the Internet age. The main goal is to make children (including teenagers) be aware of possible social consequences of their misuse of information and communication technologies, in particular, of the cell telephones and the Internet. An original method of early forming the cognitive subspace of moral values and social responsibility is stated. It is a part of the System of Emotional-Imaginative Teaching (the EIT-system) developed and successfully tested by the authors during 1990s – 2000s. For describing this method, a new formal notation for representing transformations of the learners’ cognitive-emotional sphere and the spectrum of information processing skills is proposed, it is called the notation of the maps of cognitive transformations. The described method of early socialization and the EIT-system as a whole are interpreted as an important component of cognitonics - a new scientific discipline. The paper also represents a new way of considering impressionism under the frame of cognitonics. An original algorithm of transforming the negative emotions (caused by the messages received from social networks) into the positive ones is proposed. This algorithm considers the possible reactions of a human (including the recommended reactions) to the emotional attacks via social networks. It is proposed to include an analysis of the kind into the program of the interdisciplinary course “Foundations of secure living in information society”.
We design temporal description logics (TDLs) suitable for reasoning about temporal conceptual data models and investigate their computational complexity. Our formalisms are based on DL-Lite logics with three types of concept inclusions (ranging from atomic concept inclusions and disjointness to the full Booleans), as well as cardinality constraints and role inclusions. The logics are interpreted over the Cartesian products of object domains and the flow of time (ℤ, <), satisfying the constant domain assumption. Concept and role inclusions of the TBox hold at all moments of time (globally), and data assertions of the ABox hold at specified moments of time. To express temporal constraints of conceptual data models, the languages are equipped with flexible and rigid roles, standard future and past temporal operators on concepts, and operators “always” and “sometime” on roles. The most expressive of our TDLs (which can capture lifespan cardinalities and either qualitative or quantitative evolution constraints) turns out to be undecidable. However, by omitting some of the temporal operators on concepts/roles or by restricting the form of concept inclusions, we construct logics whose complexity ranges between NLogSpace and PSpace. These positive results are obtained by reduction to various clausal fragments of propositional temporal logic, which opens a way to employ propositional or first-order temporal provers for reasoning about temporal data models.
There is a gap in the proof of the main theorem in the article  on optimal bounds for the Morse lemma in Gromov-hyperbolic spaces. We correct this gap, showing that the main theorem of  is true. We also describe a computer certification of this result.
A top-down approach is presented for checking the existence and derivation of an adaptive distinguishing test case (called also an adaptive distinguishing sequence) for a nondeterministic finite state machine (NDFSM). When such a test case exists, the method returns a canonical test case that includes all other distinguishing tests of the given complete observable NDFSM. In the second part of the paper, a constructive approach is provided for deriving a class of complete observable NDFSMs with n states, n > 2, and 2 n − n − 1 inputs such that a shortest adaptive distinguishing test case for each NDFSM in the intended class has the length (height) 2 n − n − 1. In other words, we prove the reachability of the exponential upper bound on the length of a shortest adaptive distinguishing sequence for complete observable NDFSMs while for deterministic machines the upper bound is polynomial with respect to the number of states. For constructing the intended class of NDFSMs for a given n, we propose a special linear order over all the non-empty subsets without singletons of an n-element set. The obtained tight exponential upper bound initiates further research on identifying certain NDFSM classes where this upper bound is not reachable.
An ensemble of classifiers has been built to solve the problem of video image recognition. The paper offers a way to estimate the a posteriori probability of an image belonging to a particular class in the case of an arbitrary distance and nearest neighbor method. The estimation is shown to be equivalent to the optimal naive Bayesian estimate given Kullback-Leibler divergence being used as proximity measure. The block diagram of a video image recognition system is presented. The system features automatic adaptation of the list of images of identical objects which is fed to the committee machine input. The system is tested in face recognition task using popular data bases (FERET, AT&T, Yale) and the results are discussed.
ARTM advantages: ARTM is much simpler that Bayesian Inference ARTM focuses on formalizing task-specific requirements ARTM simplifies the multi-objective PTMs learning ARTM reduces barriers to entry into PTMs research field ARTM encourages the development of regularization library ARTM restrictions: Choosing a regularization path is a new open issue for PTMs
We design a decidable extension of the description logic SROIQ underlying the Web Ontology Language OWL 2. The new logic, called SR+OIQ, supports a controlled use of role axioms whose right-hand side may contain role chains or role unions. We give a tableau algorithm for checking concept satisfiability with respect to SR+OIQ ontologies and prove its soundness, completeness and termination.