Add a filter

Of all publications in the section: 112

Sort:

by name

by year

Working paper

We study properties of Markov chain Monte Carlo simulations of classical spin models with local updates. We derive analytic expressions for the mean value of the acceptance rate of the single-spin-flip algorithms for the one-dimensional Ising model. We find that for the Metropolis algorithm the average acceptance rate is a linear function of energy. We further provide numerical results for the energy dependence of the average acceptance rate for the 3- and 4-state Potts model, and the XY model in one and two spatial dimensions. In all cases, the acceptance rate is an almost linear function of the energy in the critical region. The variance of the acceptance rate is studied as a function of the specific heat.

Added: Jul 17, 2019

Working paper

A Computational Model That Recovers Depth from Stereo-Input without Using Any Oculomotor Information

It is commonly believed that the visual system requires oculomotor information to perceive depth from binocular disparity. However, any effect of the oculomotor information on depth perception is too restricted to explain depth perception under natural viewing conditions. In this study, I describe a computational model that can recover depth from a stereo-pair of retinal images without using any oculomotor information. The model shows that, at least from a computational perspective, any oculomotor information is not necessary for perceiving depth from the stereo retinal images.

Added: Apr 20, 2019

Working paper

Added: Apr 8, 2015

Working paper

The problem of autonomous navigation is one of the basic problems for robotics. Although, in general, it may be challenging when an autonomous vehicle is placed into partially observable domain. In this paper we consider simplistic environment model and introduce a navigation algorithm based on Learning Classifier System.

Added: Nov 9, 2015

Working paper

The Competitive Industrial Performance index (developed by experts of the UNIDO) is designed as a measure of national competitiveness. Index is an aggregate of eight observable variables, representing different dimensions of competitive industrial performance. Instead of using a cardinal aggregation function, what CIP’s authors do, it is proposed to apply ordinal ranking methods borrowed from social choice: either direct ranking methods based on the majority relation (e.g. the Copeland rule, the Markovian method) or a multistage procedure of selection and exclusion of the best alternatives, as determined by a majority relation-based social choice solution concept (tournament solution), such as the uncovered set and the minimal externally stable set. The same method of binary comparisons based on the majority rule is used to analyse rank correlations. It is demonstrated that the ranking is robust but some of the new aggregate rankings represent the set of criteria better than the original ranking based on the CIP.

Added: Sep 25, 2014

Working paper

The Protein Structure Alignment Problem (PSAP) consists in finding the
best alignment of two proteins defined by their primary structures. It finds
the most similar substructure of two proteins. This problem is polynomially
reducible to the Maximum Clique Problem (MCP) for the protein alignment
graph. In this paper we present an efficient algorithm for the PSAP based on
our recent ILS&MCS algorithm (Batsyn et al., 2014) for the MCP. To reduce
the alignment problem to the MCP we follow the DAST method introduced
by Malod-Dognin et al. (2010). Our main contributions include: applying the
ILS heuristic to obtain a lower bound and make preprocessing of an alignment
graph to reduce its size; efficient implementation of the algorithm for large but
sparse alignment graphs including memory preallocation and bit representation
of adjacency matrix. The computational results are provided for the popular
Skolnick test set of 40 proteins and show that the suggested algorithm is more
efficient than one of the fastest PSAP solvers - the ACF algorithm by Malod-
Dognin et al. (2010).

Added: Oct 24, 2016

Working paper

We consider an initial-boundary value problem for a 2D time-dependent Schrödinger equation on a semi-infinite strip. For the Numerov-Crank-Nicolson finite-difference scheme with discrete transparent boundary conditions, the Strang-type splitting with respect to the potential is applied. For the resulting method, the uniqueness of a solution and the uniform in time L_2-stability (in particular, L_2-conservativeness) are proved. Due to the splitting, an effective direct algorithm using FFT in the direction perpendicular to the strip is developed to implement the splitting method for general potential. Numerical results on the tunnel effect for smooth and rectangular barriers together with the practical error analysis on refining meshes are included as well.

Added: Jul 24, 2013

Working paper

Classical approaches in recommender systems such as collaborative filtering are concentrated mainly on static user preference extraction. This approach works well as an example for music recommendations when a user behavior tends to be stable over long period of time, however the most common situation in e-commerce is different which requires reactive algorithms based on a short-term user activity analysis. This paper introduces a small mathematical framework for short-term user interest detection formulated in terms of item properties and its application for recommender systems enhancing. The framework is based on the fundamental concept of information theory --- Kullback-Leibler divergence.

Added: Nov 9, 2015

Working paper

The poetic texts pose a challenge to full morphological tagging and lemmatization since the authors seek to extend the vocabulary, employ morphologically and semantically deficient forms, go beyond standard syntactic templates, use non-projective constructions and non-standard word order, among other techniques of the creative language game. In this paper we evaluate a number of probabilistic taggers based on decision trees, CRF and neural network algorithms as well as one state-of-the-art dictionary-based tagger. The taggers were trained on prosaic texts and tested on three poetic samples of different complexity. Firstly, we discuss the method to compile the gold standard datasets for the Russian poetry. Secondly, we evaluate the taggers’ performance in the identification of the part of speech tags and lemmas. Finally, we analyze different types of errors in the taggers’ output. We analyse the confusion matrix of the parts of speech and mismatches in lemma annotation.

Added: Dec 12, 2018

Working paper

Ducomet B.,

, arxiv.org. math. Cornell University, 2013. No. 1309.7280 .
An initial-boundary value problem for the $n$-dimensional ($n\geq 2$) time-dependent Schrödinger equation in a semi-infinite (or infinite) parallelepiped is considered. Starting from the Numerov-Crank-Nicolson finite-difference scheme, we first construct higher order scheme with splitting space averages having much better spectral properties for $n\geq 3$. Next we apply the Strang-type splitting with respect to the potential and, third, construct discrete transparent boundary conditions (TBC). For the resulting method, the uniqueness of solution and the unconditional uniform in time $L^2$-stability (in particular, $L^2$-conservativeness) are proved. Owing to the splitting, an effective direct algorithm using FFT (in the coordinate directions perpendicular to the leading axis of the parallelepiped) is applicable for general potential. Numerical results on the 2D tunnel effect for a P\"{o}schl-Teller-like potential-barrier and a rectangular potential-well are also included.

Added: Oct 1, 2013

Working paper

The paper presents a Universal Dependencies (UD) annotation scheme for a learner English corpus. The REALEC dataset consists of essays written in English by Russian-speaking university students in the course of general English. The essays are a part of students' preparation for the independent final examination similar to the international English exam. While adjusting existing dependency parsing tools to a learner data, one has to take into account to what extent students' mistakes provoke errors in the parser output. The ungrammatical and stylistically inappropriate utterances may challenge parsers' algorithms trained on grammatically appropriate written texts. In our experiments, we compared the output of the dependency parser UDpipe (trained on UD-English 2.0) with the results of manual parsing, placing a particular focus on parses of ungrammatical English clauses. We show how mistakes made by students influence the work of the parser. Overall, UDpipe performed reasonably well (UAS 92.9, LAS 91.7). The following cases cause the errors in automatic annotation a) incorrect detection of a head, b) incorrect detection of the relation type, as well as c) both. We propose some solutions which could improve the automatic output and thus make the assessment of syntactic complexity more reliable.

Added: Dec 15, 2017

Working paper

Granin S.,

math. arxive. Cornell University, 2015
Added: Oct 30, 2015

Working paper

Recently proposed Skip-gram model is a powerful method for learning high-dimensional word representations that capture rich semantic relationships between words. However, Skip-gram as well as most prior work on learning word representations does not take into account word ambiguity and maintain only single representation per word. Although a number of Skip-gram modifications were proposed to overcome this limitation and learn multi-prototype word representations, they either require a known number of word meanings or learn them using greedy heuristic approaches. In this paper we propose the Adaptive Skip-gram model which is a nonparametric Bayesian extension of Skip-gram capable to automatically learn the required number of representations for all words at desired semantic resolution. We derive efficient online variational learning algorithm for the model and empirically demonstrate its efficiency on word-sense induction task.

Added: Nov 5, 2015

Working paper

We propose a new method for assessing agents’ influence in network structures, which takes into consideration nodes attributes, individual and group influences of nodes, and the intensity of interactions. This approach helps us to identify both explicit and hidden central elements which cannot be detected by classical centrality measures or other indices.

Added: Jul 13, 2016

Working paper

The paper analyzes legal issues associated with application of existing contract law provisions to so-called Smart contracts, defined in the paper as “agreements existing in the form of software code implemented on the Blockchain platform, which ensures autonomy and self-executive nature of Smart contract terms based on predetermined set of factors”. The paper consists of several sections. In the first section, the paper outlines peculiarities of Blockchain technology as currently implemented in Bitcoin cryptocurrency and which forms the core of Smart contracts. In the second section, the main characteristic features of Smart contracts are described. Finally, the paper outlines key tensions between classic contract law and Smart contracts.. The conclusion section sets the core question for analysis of the perspectives of implementation of this technology by governments: “How to align the powers of the government with Blockchain if there is no central authority but only distributed technologies”. The author suggests two solutions, which are not optimal: 1) providing the state authorities with the status of a Superuser with extra powers and 2) relying on traditional remedies and enforcement practices, by pursuing specific individuals – parties to Smart contract - in offline mode. It is emphasized that those jurisdictions, which have the most Blockchain-friendly regulations will have competitive advantage in attraction of new innovative business models and companies willing to exploit them in a legal way.

Added: Dec 22, 2016

Working paper

Hierarchical structures are frequently used to formalize complex multicriteria decision analysis problems. The analytic hierarchy process (AHP) of Saaty (1980) is an established method used to solve practical multicriteria problems of the hierarchical nature. It is also well-known that AHP, and its modifications and generalizations poses a number of fundamental drawbacks that cannot in principle be overcome. The main drawbacks are the independence of the evaluation procedure of the criteria importance from the normalization of criterion values – this violates the requirement of the mathematical theory of measurement, and the lack of a formal definition of the notion of criteria importance. Furthermore, the use of ratio scales in AHP for the expression of importance of criteria is theoretically unsubstantiated. We suggest a new methodology suitable for the analysis of multicriteria problems with hierarchical structures. It is based on criteria importance theory.

Added: Apr 24, 2014

Working paper

Positive-Unlabeled Learning is an analog of supervised binary classification for the case when the Negative (N) sample in the training set is contaminated with latent instances of the Positive (P) class and hence is Unlabeled (U). We develop DEDPUL1 , a method able to solve two problems: first, to estimate the proportions of the mixing components (P and N) in U, and then, to classify U. The main steps are to reduce dimensionality of the data using Non-Traditional Classifier [11], to estimate densities of the reduced data in both P and U samples, and to apply the Bayes rule to density ratio. We experimentally show that DEDPUL outperforms current state-of-the-art methods for both problems. Additionally, we improve current state-of-the-art method for PU Classification [16].

Added: May 31, 2019

Working paper

The paper considers the features of selecting the teaching illustrative material for the theoretical part of a multimedia textbook on Russian as a foreign language, and describes the peculiarities of compiling a set of exercises on the basis of the National Corpus of the Russian Language. The author(s) analysed in detail the difficulties caused by working with the National Corpus of the Russian Language for educational purposes and problems emerged in the process of working on a project aimed at creating an electronic textbook "The Russian verb. Word formation". Technology of electronic textbook was created, which is used for learning foreign language. The helpful tool tip was added in the textbook. It was compounded with grammatical information and English translation for each separated word.

Added: Nov 8, 2012

Working paper

When utilities are additive, we uncovered in our previous paper (Bogomolnaia et al. "Dividing Goods or Bads under Additive Utilities") many similarities but also surprising differences in the behavior of the familiar Competitive rule (with equal incomes), when we divide (private) goods or bads. The rule picks in both cases the critical points of the product of utilities (or disutilities) on the efficiency frontier, but there is only one such point if we share goods, while there can be exponentially many in the case of bads.
We extend this analysis to the fair division of mixed items: each item can be viewed by some participants as a good and by others as a bad, with corresponding positive or negative marginal utilities. We find that the division of mixed items boils down, normatively as well as computationally, to a variant of an all goods problem, or of an all bads problem: in particular the task of dividing the non disposable items must be either good news for everyone, or bad news for everyone.
If at least one feasible utility profile is positive, the Competitive rule picks the unique maximum of the product of (positive) utilities. If no feasible utility profile is positive, this rule picks all critical points of the product of disutilities on the efficient frontier.

Added: Oct 13, 2016

Working paper

When utilities are additive, we uncovered in our previous paper (Dividing Goods or Bads Under Additive Utilities) many similarities but also surprising dierences in the behavior of the familiar Competitive rule (with equal incomes), when we divide (private) goods or bads. The rule picks in both cases the critical points of the product of utilities (or disutilities) on the eciency frontier, but there is only one such point if we share goods, while there can be exponentially many in the case of bads. We extend this analysis to the fair division of mixed items: each item can be viewed by some participants as a good and by others as a bad, with corresponding positive or negative marginal utilities. We nd that the division of mixed items boils down, normatively as well as computationally, to a variant of an all goods problem, or of an all bads problem: in particular the task of dividing the non disposable items must be either good news for everyone, or bad news for everyone. If at least one feasible utility prole is positive, the Competitive rule picks the unique maximum of the product of (positive) utilities. If no feasible utility prole is positive, this rule picks all critical points of the product of disutilities on the ecient frontier.

Added: Nov 14, 2016

Working paper

The Competitive Equilibrium with Equal Incomes is an especially appealing efficient and envy-free division of private goods when utilities are additive: it maximizes the Nash product of utilities and is single-valued and continuous in the marginal rates of substitution. The CEEI to divide bads captures similarly the critical points of the Nash product in the efficient frontier. But it is far from resolute, allowing routinely many divisions with sharply different welfare consequences. Even the much more permissive No Envy property is profoundly ambiguous in the division of bads: the set of efficient and envy-free allocations can have many connected components, and has no single-valued selection continuous in the marginal rates. The CEEI to divide goods is Resource Monotonic (RM): everyone (weakly) benefits when the manna increases. But when we divide bads efficiently, RM is incompatible with Fair Share Guarantee, a much weaker property than No Envy.

Added: Oct 14, 2016