Analysis of Images, Social Networks and Texts

Over the course of history, humankind used documents as one of the ways of organization of the data. In the recent decades, electronic documentation became increasingly widespread. To make electronic documents exchange possible, standards regulating transmission protocols, representation formats, and rules for document building are necessary. For some protocols (HTTP, SOAP, etc.) and formats (EDI, XML, JSON, etc.), relatively fixed and generally accepted standards are available. As for the electronic document design, there is an abundance of approaches where a leader could hardly be established; all of them have their benefits and drawbacks. This study explores some of these approaches (UN/CEFACT CCTS, WCO DM, ISO 20022, and NIEM). These approaches have different features but from the conceptual perspective they are intended to describe sets of details of some real-world objects. The paper proposes to describe such objects using an ontology and then, based on this ontology, build conceptual structures of electronic documents that can be converted to platform-independent structures of electronic documents in accordance with one of the standards. The introduced approach allows harmonizing the standards under consideration.

In this paper we analyse ways to improve the acoustic models based on deep neural networks with the help of data augmentation. These models are used for speech recognition in a priori unknown possibly noisy acoustic environment (with the presence of office or home noise, street noise, babble, etc.) and may deal with both the headset and distant microphone recordings. We compare acoustic models trained on speech corpora with artificially added noises of different origins and reverberation. At various test sets, word recognition accuracy improvement over the baseline model trained on clean headset recordings reaches 45%. In real-life environments like a meeting room or a noisy open space, the gain varies from 10 to 40%.

In this paper we suggest the first systematic review and compare performance of most frequently used machine learning algorithms for prediction of the match winner from the teams’ drafts in Dota 2 computer game. Although previous research attempted this task with simple models, weve made several improvements in our approach aiming to take into account interactions among heroes in the draft. For that purpose we’ve tested the following machine learning algorithms: Naive Bayes classifier, Logistic Regression and Gradient Boosted Decision Trees. We also introduced Factorization Machines for that task and got our best results from them. Besides that, we found that model’s prediction accuracy depends on skill level of the players. We’ve prepared publicly available dataset which takes into account shortcomings of data used in previous research and can be used further for algorithms development, testing and benchmarking.

The Cropland Capture game (CCG) aims to map cultivated lands using around 170000 satellite images. The contribution of the paper is threefold: (a) we improve the quality of the CCG’s dataset, (b) we benchmark state-of-the-art algorithms designed for an aggregation of votes in a crowdsourcing-like setting and compare the results with machine learning algorithms, (c) we propose an explanation for surprisingly similar accuracy of all examined algorithms. To accomplish (a), we detect image duplicates using the perceptual hash function pHash. In addition, using a blur detection algorithm, we filter out unidentifiable images. In part (c), we suggest that if all workers are accurate, the task assignment in the dataset is highly irregular, then state-of-the-art algorithms perform on a par with Majority Voting. We increase the estimated consistency with expert opinions from 77% to 91% and up to 96% if we restrict our attention to images with more than 9 votes.

In this paper, we study the computational complexity of the following subset search problem in a set of vectors. Given a set of N Euclidean q-dimensional vectors and an integer M, choose a subset of at least M vectors minimizing the Euclidean norm of the arithmetic mean of chosen vectors. This problem is induced, in particular, by a problem of clustering a set of points into two clusters where one of the clusters consists of points with a mean close to a given point. Without loss of generality the given point may be assumed to be the origin.We show that the considered problem is NP-hard in the strong sense and it does not admit any approximation algorithm with guaranteed performance, unless P = NP. An exact algorithm with pseudo-polynomial time complexity is proposed for the special case of the problem, where the dimension q of the space is bounded from above by a constant and the input data are integer.

The optimal packing problem of equal circles (2-D spheres) in a bounded set P in a two-dimensional metric space is considered. The sphere packing problem is to find an arrangement in which the spheres fill as large proportion of the space as possible. In the case where the space is Euclidean this problem is well known, but the case of non-Euclidean metrics is studied much worse. However there are some applied problems, which lead us to use other special non-Euclidean metrics. For instance such statements appear in the logistics when we need to locate a given number of commercial facilities and to maximize the overall service area. Notice, that we consider the optimal packing problem in the case, where P is a multiply-connected domain. The special algorithm based on optical-geometric approach is suggested and implemented. The results of numerical experiment are presented and discussed.

Concept drift has potential in smart grid analysis because the socio-economic behaviour of consumers is not governed by the laws of physics. Likewise there are also applications in wind power forecasting. In this paper we present decision tree ensemble classification method based on the Random Forest algorithm for concept drift. The weighted majority voting ensemble aggregation rule is employed based on the ideas of Accuracy Weighted Ensemble (AWE) method. Base learner weight in our case is computed for each sample evaluation using base learners accuracy and intrinsic proximity measure of Random Forest. Our algorithm exploits ensemble pruning as a forgetting strategy. We present results of empirical comparison of our method and other state-of-the-art concept-drfit classifiers.

Economic agents’ behavior during the last 40 years had tremendously changed from perfect competition to cooperation between them, and coopetition phenomenon was revealed. This phenomenon is always based on the certain entrepreneurial network. The paper is focused on entrepreneurial networks which are geographically localized. Such networks are formed as a result of two different types of cooperation: production cluster cooperation and cooperation in a community. The main goal of the present study is to find differences between internal structures of these two types entrepreneurial networks. Data was collected using experimental economic techniques, it was represented in the form of transactions between network agents and was aggregated over the certain time period. Social Network Analysis (SNA) methods and instruments were used in this research. Detailed structure analysis was based on the set of quantitative parameters such as density, diameter, clustering coefficient, different kinds of centrality, and etc. The entrepreneurial networks of two production clusters and three cooperative communities were under investigation. These networks were compared with each other and also with random Bernoulli graphs of the corresponding size and density. It was found that cooperative community networks are more random and dense than the production cluster ones and their other parameters also differ. Discovered variations of network structures are explained by the peculiarities of agents functioning in these two type networks.

Homophily is considered by network scientists as one of the major mechanisms of social network formation. However, the role of dynamic homophily in the network growth process has not been investigated in detail yet. In this paper, we estimate the role of homophily by various attributes at different stages of online network formation process. We consider the process of online friendship formation in the Vkontakte social networking site among first-year students at a Russian university. We reveal that at the beginning of the network formation a similarity in gender and score in entrance exams plays the key role, while by the end of network establishment period the role of the same group affiliation becomes more important. We explain the results with the tendency of students to follow different strategies to control the information flow in their social environment.

A balanced social structure within an organization is often considered as one of the major factors of company success. Thus the analysis of organizational networks is an important direction in network and organizational studies. In this paper we explore the mechanisms of collaboration using information about scientific paper coauthorships. We reveal the collaboration mechanisms within research departments of top Russian oil companies, Gazpromneft, Bashneft, Lukoil, and Tatneft. We examine the role of management in professional community formation.

Organizational citizenship behavior (OCB) is an important management construct. Despite previous investigations in relation to social capital, the role of networks in its emergence has received only limited attention. In this paper we investigate the relationship between OCB, with data collected from supervisors evaluating their subordinates; sever-al types of organizational networks (professional, friendship, support, supervisor-subordinate), and several other constructs (collected from the employees themselves), shown to affect OCB in the past. All data were collected at a large insurance company in Russia.Outcomes of this study have several important implications. First, the impact of networks on manifestation of OCB depends not only on the strength of network ties, but on types of network. Second, interoganizational relationships are complex and consist of several levels of mediated relationships. Results of this study can impact the theoretical understanding of OCB and have practical implications for the supervisor-subordinate relationships in the workplace.

A probabilistic topic model is a modern statistical tool for document collection analysis that allows extracting a number of topics in the collection and describes each document as a discrete probability distribution over topics. Classical approaches to statistical topic modeling can be quite effective in various tasks, but the generated topics may be too similar to each other or poorly interpretable. We supposed that it is possible to improve the interpretability and differentiation of topics by using linguistic information such as collocations while building the topic model. In this paper we offer an approach to accounting bigrams (two-word phrases) for the construction of Anchor Words Topic Model.

In this paper we present a new asynchronous algorithm for learning additively regularized topic models and discuss the main architectural details of our implementation. The key property of the new algorithm is that it behaves in a fully deterministic fashion, which is typically hard to achieve in a non-blocking parallel implementation. The algorithm had been recently implemented in the BigARTM library (http://bigartm.org). Our new algorithm is compatible with all features previously introduced in BigARTM library, including multimodality, regularizers and scores calculation. While the existing BigARTM implementation compares favorably with alternative packages such as Vowpal Wabbit or Gensim, the new algorithm brings further improvements in CPU utilization, memory usage, and spends even less time to achieve the same perplexity.

The paper deals with extracting contexts for keywords found in text, in particular in Automatic Speech Recognition (ASR) output. We propose using a syntactic parser to find contexts by analysing the sentence structure, rather than simply using a window of several words on the left and right of the keyword, or the whole sentence. This method provides concise but meaningful contexts that are easily readable by humans and can also be used in applications such as thematic clustering. We describe the Russian SemSin system which combines a syntactic dependency parser and elements of semantic ontology. We demonstrate the use of SemSin for our task both for normal text and for recognition output, and outline the suggestions for future developments of our method.

The paper presents a free and open source toolkit which aim is to quickly deploy web services handling distributed vector models of semantics. It fills in the gap between training such models (many tools are already available for this) and dissemination of the results to general public. Our toolkit, WebVectors, provides all the necessary routines for organizing online access to querying trained models via modern web interface. We also describe two demo installations of the toolkit, featuring several efficient models for English, Russian and Norwegian.

In this paper we present a comparison of three morphological taggers for Russian with regard to the quality of morphological disambiguation performed by these taggers. We test the quality of the analysis in three different ways: lemmatization, POS-tagging and assigning full morphological tags. We analyze the mistakes made by the taggers, outline their strengths and weaknesses, and present a possible way to improve the quality of morphological analysis for Russian.

Growing interest in automatic speaker verification (ASV) systems has lead to significant quality improvement of spoofing attacks on them. Many research works confirm that despite the low equal error rate (EER) ASV systems are still vulnerable to spoofing attacks. In this work we overview different acoustic feature spaces and classifiers to determine reliable and robust countermeasures against spoofing attacks. We compared several spoofing detection systems, presented so far, on the development and evaluation datasets of the Automatic Speaker Verification Spoofing and Countermeasures (ASVspoof) Challenge 2015. Experimental results presented in this paper demonstrate that the use of magnitude and phase information combination provides a substantial input into the efficiency of the spoofing detection systems. Also wavelet-based features show impressive results in terms of equal error rate. In our overview we compare spoofing performance for systems based on different classifiers. Comparison results demonstrate that the linear SVM classifier outperforms the conventional GMM approach. However, many researchers inspired by the great success of deep neural networks (DNN) approaches in the automatic speech recognition, applied DNN in the spoofing detection task and obtained quite low EER for known and unknown type of spoofing attacks.

Current machine-learning approaches for information extraction often include features based on large volumes of knowledge in form of gazetteers, word clusters, etc. In this paper we consider a CRF-based approach for Russian named entity recognition based on multiple lexicons. We test our system on the open Russian collections “Persons-1000” and “Persons-1111” labeled with personal names. We additionally annotated the collection “Persons-1000” with names of organizations, media, locations, and geo-political entities and present the results of our experiments for one type of names (Persons) for comparison purposes, for three types (Persons, Organizations, and Locations), and five types of names. We also compare two types of labeling schemes for Russian: IO-scheme and BIO-scheme.

We introduce a novel approach to constructing user profiles for recommender systems based on full-text items such as posts in a social network and implicit ratings (in the form of likes) that users give them. The profiles measure a user’s interest in various topics mined from the full texts of the items. As a result, we get a user profile that can be used for cold start recommendations for items, targeted advertisement, and other purposes. Our experiments show that the method performs on a level comparable with classical collaborative filtering algorithms while at the same time being a cold start approach, i.e., it does not use the likes of an item being recommended.

We study topic models designed to be used for sentiment analysis, i.e., models that extract certain topics (aspects) from a corpus of documents and mine sentiment-related labels related to individual aspects. For both direct applications in sentiment analysis and other uses, it is desirable to have a good lexicon of sentiment words, preferably related to different aspects in the words. We have previously developed a modification for several popular sentiment-related LDA extensions that trains prior hyperparameters $$\beta $$ for specific words. We continue this work and show how this approach leads to new aspect-specific lexicons of sentiment words based on a small set of “seed” sentiment words; the lexicons are useful by themselves and lead to improved sentiment classification.

Semantic relatedness of terms represents similarity of meaning by a numerical score. On the one hand, humans easily make judgements about semantic relatedness. On the other hand, this kind of information is useful in language processing systems. While semantic relatedness has been extensively studied for English using numerous language resources, such as associative norms, human judgements and datasets generated from lexical databases, no evaluation resources of this kind have been available for Russian to date. Our contribution addresses this problem. We present five language resources of different scale and purpose for Russian semantic relatedness, each being a list of triples $$({word}_{i}, {word}_{j}, {similarity}_{ij}$$). Four of them are designed for evaluation of systems for computing semantic relatedness, complementing each other in terms of the semantic relation type they represent. These benchmarks were used to organise a shared task on Russian semantic relatedness, which attracted 19 teams. We use one of the best approaches identified in this competition to generate the fifth high-coverage resource, the first open distributional thesaurus of Russian. Multiple evaluations of this thesaurus, including a large-scale crowdsourcing study involving native speakers, indicate its high accuracy.

In the paper vector-space semantic models based on Word2Vec word embeddings algorithm and a count-based association-oriented algorithm are evaluated and compared by measuring association strength between Russian nouns and adjectives. A dataset of nouns and associated adjectives is used as the test set for pseudodisambiguation task. Models are trained with corpora of Russian fiction. A measure of lexical association anomaly is applied evaluating similarity between the initial noun and the resulting attributive phrase. Results of association strength are reported for models characterized by different parameter values; the best parameter value combinations are proposed. The test exemplars producing the error rate are manually annotated, and the model errors are categorized in terms of their linguistic nature and compositionality features.

A text classification problem in Kazakh language is examined. The amount of training data for the task in Kazakh is very limited, but plenty of labeled data in Russian are available. Language vector space transform is built and used to transfer knowledge from Russian into Kazakh language. The obtained classification quality is comparable to that of an approach that employed sophisticated automatic translation system.

Within the framework of the Bayesian approach, the general problem of image processing can be represented as a problem of estimation of the hidden component of the two-component random field on the basis of realization of its observable component, that is an analyzed image. Nonstationary gamma-normal model of the two-component random field showed good results in processing quality and computation time by solving the problem of image denoising. This paper proposes to extend the initial formulation for solving problems requiring transferring structure of the intermediate image on the processing result. Haze removal problem, HDR image compression and edges refinement of an image are considered as practical examples of such problems.

This article continues studies of probability anomaly detector method which was presented in author’s previous works. Here two implementations of this method are introduced. The implementations are based on different vector quantization algorithms. Description of both algorithms and results of experimental research of their parameters are provided. Both implementations are compared with well known RX anomaly detector on synthetic hyperspectral images.

This paper considers an algebraic method for symmetry analysis of hexagonally sampled images, based on the interpretation of such images as functions on “Eisenstein fields”. These are finite fields $$\mathbb {GF}(p^2)$$ of special characteristics $$p=12k+5$$, where $$k>0$$ is an integer. Some properties of such fields are studied; in particular, it is shown that its elements may be considered as “discrete Eisenstein numbers” and are in natural correspondence with hexagons in a $$(p\times p)$$-diamond-shaped fragment of a regular plane tiling. The concept of logarithm in Eisenstein fields is introduced and used to define a “log-polar”-representation of hexagonal images. Next, an algorithm for threefold symmetry detection in gray-level images is proposed.

In this paper the novel fast approach to identify the reflection symmetry axis of binary images is proposed. We propose to divide a skeleton of a shape into two parts – the “left” and the “right” sub-skeletons. The left part is traversed counterclockwise and the right one – in clockwise direction. As a result, the “left” and the “right” primitive sub-chains are achieved; they can be compared by the known shape matching procedure based on pair-wise alignment of primitive chains. So, the most similar parts of a skeleton among all possible ones correspond to the most similar parts of a figure which are considered as reflection symmetric parts. The start and the end points of skeleton division into “left” and “right” parts will be the points belonging to a symmetry axis of a figure. Also, the exact brute-force symmetry evaluation algorithm and two its optimizations are suggested for finding ground truth of symmetry axis. All proposed methods were experimentally tested on Flavia leaves dataset.

Digital images are often used to prove some facts or events, but nobody can guarantee their originality. More often we can see in TV news, that some satellite imagery evidences were received to show what has happened. However, we cannot be sure, that these data were not changed by some hackers. In this paper we propose a new algorithm for detection of the most frequently used attack plain copy-move. The algorithm is based on a hash value calculation in a sliding window mode. The hash function is constructed using efficient linear local features that were developed by coauthor V. Myasnikov in 2010. Finally, we present results of conducted experiments and comparison with existing solutions, as well as recommendations for the use of the proposed approach. The main advantage of the proposed solution is 99.95% precision of copy-move blocks detection comparing with existing approaches. Another impact is that it can be easily used for large satellite image analysis as well as ordinary digital images processing because of low computational complexity.

In this work, we apply quantum cellular automata (QCA) to study pattern formation and image processing in quantum-diffusion Schrodinger systems (QDSS) with triplet-valued (color-valued) diffusion coefficients. Triplet numbers have the real part and two imaginary parts (with two imaginary units). They form 3-D triplet algebra. Discretization of the Schrodinger equation gives “lattice based metamaterial models” with various triplet–valued physical parameters. The process of excitation in these media is described by the Schrodinger equations with the wave functions that have values in triplet algebras. If a traditional computer is thought of as a “programmable object”, QDSS in the form of QCA is a computer of new kind and is better visualized as a “programmable material”. The purpose of this work is to introduce new metamedium in the form of cellular automata. The cells are placed in a 2-D array and they are capable of performing basic arithmetic operating in the triplet algebra and exchanging massages about their state. Cellular automata like architectures have been successfully used for computer vision problems and color image processing. Such metamedia possess large opportunities in processing of color images in comparison with the ordinary diffusion media with the real-valued diffusion coefficients. The latter media are used for creation of the eye-prosthesis (so called the “silicon eye”). The color metamedium suggested can serve as the prosthesis prototype for perception of the color images.

One-dimensional total variation (TV) regularization can be used for signal denoising. We consider one-dimensional signals distorted by additive white Gaussian noise. TV regularization minimizes a functional consisting of the sum of fidelity and regularization terms. We derive exact solutions to one-dimensional TV regularization problem that help us to recover signals with the proposed algorithm. The proposed approach to finding exact solutions has a clear geometrical meaning. Computer simulation results are provided to illustrate the performance of the proposed algorithm for signal denoising.

In this paper we examine the task of maintenance decision support in classification of the dangerous situations discovered by the monitoring system. This task is reduced to the contextual multi-armed bandit problem. We highlight the small sample size problem appeared in this task due to the rather rare failures. The novel algorithm based on the nearest neighbor search is proposed. An experimental study is provided for several synthetic datasets with the situations described by either simple features or grayscale images. It is shown, that our algorithm outperforms the well-known contextual multi-armed methods with the Upper Confidence Bound and softmax stochastic search strategies.

Here we present a new theoretical framework for multidimensional image processing using hypercomplex commutative algebras that codes color, multicolor and hypercolor. In this paper a family of discrete color–valued and multicolor–valued 2–D Fourier–like, wavelet–like transforms and splines has been presented (in the context of hypercomplex analysis). These transforms can be used in color, multicolor, and hyperspectral image processing. In our approach, each multichannel pixel is considered not as an K–D vector, but as an K–D hypercomplex number, where K is the number of different optical channels. Orthounitary transforms and splines are specific combination (Centaurus) of orthogonal and unitary transforms. We present several examples of possible Centuaruses (ortho–unitary transforms): Fourier+Walsh, Complex Walsh+Ordinary Walsh and so on. We collect basis functions of these transforms in the form of iconostas. These transforms are applicable to multichannel images with several components and are different from the classical Fourier transform in that they mix the channel components of the image. New multichannel transforms and splines generalize real–valued and complex–valued ones. They can be used for multichannel images compression, interpolation and edge detection from the point of view of hypercomplex commutative algebras. The main goal of the work is to show that hypercomplex algebras can be used to solve problems of multichannel (color, multicolor, and hyperspectral) image processing in a natural and effective manner.

Nowadays many algorithms for mobile robot mapping in indoor environments have been created. In this work we use a Kinect 2.0 camera, a visible range cameras Beward B2720 and an infrared camera Flir Tau 2 for building 3D dense maps of indoor environments. We present the RGB-D Mapping and a new fusion algorithm combining visual features and depth information for matching images, aligning of 3D point clouds, a “loop-closure” detection, pose graph optimization to build global consistent 3D maps. Such 3D maps of environments have various applications in robot navigation, real-time tracking, non-cooperative remote surveillance, face recognition, semantic mapping. The performance and computational complexity of the proposed RGB-D Mapping algorithm in real indoor environments is presented and discussed.