Eng | Rus

“Informatics and Applications” scientific journal

Volume 9, Issue 2, 2015

Content   Abstract and Keywords   About Authors

ON AVAILABILITY OF PARETO EFFECTIVE EQUILIBRIUM SITUATIONS IN COLLECTIVE BEHAVIOR MODELS WITH DATA EXCHANGE .
  • N. S. Vasilyev  N. E. Bauman Moscow State Technical University, 5 Baumanskaya 2nd Str.,Moscow 105005, Russian Federation

Abstract: Use of network technologies impels investigations of collective behavior models. Processes of decision making based on data exchange are of utmost interest. For this purpose, strategy axiomatization is proposed. Information exchange diminishes uncertainty in the processes and models collective efforts to achieve rational decisions. Rational behavior uses the principles of effectiveness and stability usually contradicting one another. Rational game solutions’ structure is studied. It is discovered that data exchange allows achieving Pareto effective situation which is also the equilibrium one. A notion of coalitional stable game issue is introduced. The situation prevents from forming coalitions and can simultaneously satisfy the property of Pareto effectiveness. It can also give Nash equilibrium if adequate players’ strategies are used. An expansion of initial game by means of additional controlling player shows how the effective coalitional stable issue can be achieved.

Keywords:  game; strategy; situation; game issue; information exchange; dynamics of decision making; axiomatization; coalition; cooperative game; characteristic function; the best guaranteed result; strategy of punishment; Pareto effectiveness; Nash equilibrium

STATIONARY WAITING TIME IN A QUEUEING SYSTEM WITH INVERSE SERVICE ORDER AND GENERALIZED PROBABILISTIC PRIORITY .
  • L. A. Meykhanadzhyan Peoples’ Friendship University of Russia, 6 Miklukho-Maklaya Str., Moscow 117198, Russian Federation
  • T. A. Milovanova Peoples’ Friendship University of Russia, 6 Miklukho-Maklaya Str., Moscow 117198, Russian Federation
  • R. V. Razumchik Peoples’ Friendship University of Russia, 6 Miklukho-Maklaya Str., Moscow 117198, Russian Federation, Institute of Informatics Problems, Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences, 44-2 Vavilov Str.,Moscow 119333, Russian Federation

Abstract: The paper considers a single-server queueing system with a buffer of infinite capacity. Customers arrive according to a Poisson process. Service discipline is LIFO(Last In, FirstOut) with generalized probabilistic priority. It is assumed that at any instant, the remaining service time of each customer present in the system is known. Upon arrival of a new customer, its service time is compared with the remaining service time of the customer in service. As a result of the comparison, one of the following occurs: both customers leave the system; one customer leaves the system and the other occupies the server; and both customers stay in the system (one of the two occupies the server). These actions are governed by probabilistic functions. Whenever a customer remains in the system, it acquires a new (random) service time. The paper proposes the methods for calculating customer’s sojourn time distribution and busy period (in terms of Laplace–Stieltjes transform) and several performance characteristics.

Keywords:  queueing system; LIFO; probabilistic priority; general service time

MODELING OF NORMAL PROCESSES IN STOCHASTIC SYSTEMS WITH COMPLEX TRANSCENDENTAL NONLINEARITIES .
  • I. N. Sinitsyn Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
  • >V. I. Sinitsyn Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
  • E. R. Korepanov Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: Development of methods for analytical and statistical modeling for discrete and continuous stochastic systems (StS) with Wiener and Poisson noises and with complex transcendental nonlinearities (CTN) is given. Typical representation of scalar and vector CTN is considered. Equations for the normal approximation method (NAM) and the method of statistical linearization (MSL) are deduced. Also, NAM and MSL for StS with CTN algorithms are given. Test examples are presented. Some generalizations are given.

Keywords: analytical and statistical modeling; complex transcendental nonlinearities (CTN); Hermite polynomials; method of statistical linearization (MSL); normal approximationmethod (NAM); stochastic systems (StS)

NORMAL PUGACHEV FILTERS FOR STATE LINEAR STOCHASTIC SYSTEMS .
  • I. N. Sinitsyn Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
  • E. R. Korepanov Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: The applied theory of analytical synthesis of normal conditionally optimal (Pugachev) filters (NPF) in state linear non-Gaussian stochastic systems (StS) is presented. Special attention is paid to NPF for differential StS satisfying Liptzer-Shiraev conditions based on the normal approximation of a posteriori density and quasi-linear NPF based on statistical linearization of nonlinear functions depending on observations. For StS of high dimension and real-time problems, NPF are more effective than the suboptimal filters. The NPF algorithms are the basis of the "StS-Filters" software tool. Test examples are given.

Keywords:  Liptser-Shiraev filter (LSF); Liptser-Shiraev conditions; normal approximation method (NAM) for a posteriori density; normal conditionally optimal Pugachev filter (NPF); stochastic systems (StS); state linear StS; statistical linearization method (SLM)

APPLICATION OF THE PUGACHEV-SVESHNIKOV EQUATION TO THE BAXTER OCCUPATION TIME PROBLEM.
  • S. V. Berezin Institute of Applied Mathematics and Mechanics, Peter the Great St. Petersburg State Polytechnic University, 29 Politekhnicheskaya Str., St. Petersburg 195251, Russian Federation
  • O. I. Zayats Institute of Applied Mathematics and Mechanics, Peter the Great St. Petersburg State Polytechnic University, 29 Politekhnicheskaya Str., St. Petersburg 195251, Russian Federation

Abstract: The Baxter problem, that is, an occupation (sojourn) time above a moving barrier, for a skew Brownian motion is considered. The latter is known as a model of a semipermeable barrier which permits either movement through it or reflection to the opposite direction with a specified probability The Pugachev-Sveshnikov equation for a continuous Markov process is used to obtain an analytic solution of the problem. The generic method to solve the Pugachev-Sveshnikov equation for occupation-time type problems involves its reduction to a certain Riemann boundary value problem. This problem is solved, and the occupation time probability density function is derived.
Along the way, some additional characteristics of the skew Brownian motion are obtained such as the first passage time, nonexceedance probability, occupation time moments, and some other characteristics.

Keywords:  Markov process; Pugachev equation; Pugachev–Sveshnikov equation; Riemann boundary value problem; stochastic mechanics; skew Brownian motion; occupation time; sojourn time

ON A LIMIT DISTRIBUTION OF CHARACTERISTICS IN STATIONARY REGIME FOR THE LINEAR ASSIMILATION PROBLEM .
  • K. P. Belyaev Shirshov Institute of Oceanology , Russian Academy of Sciences, 36 Nakhimovsky Pr., Moscow 119299, Russian Federation
  • N. P. Tuchkova Dorodnicyn Computing Centre, Russian Academy of Sciences, 40 Vavilov Str., Moscow 119333, Russian Federation

Abstract: A commonly used linear assimilation problem when the model state vector is corrected by observed data through the system of linear equations is considered. This problem is formulated as a Markov chain problem. For this problem, convergence of transitional probability of the corresponding Markov chain is investigated and the sufficient conditions of this convergence are found out. A special case of series depending on a parameter when this parameter goes to zero is discussed and the limit theorem about convergence to Gaussian distribution for analysis of state vector characteristics for this case is proved. The mean value and variance of this distribution are determined.
The paper discusses how these results can be applied to practical operational assimilation and forecasting.

Keywords:  data assimilation methods; Markov chains stationary distributions; asymptotic distribution of chains at a small value of a parameter

COMPARATIVE ANALYSIS OF APPLICATION OF HEURISTIC AND METAHEURISTIC ALGORITHMS TO THE SCHOOL BUS ROUTING PROBLEM .
  • E. M. Bronshtein Ufa State Aviation Technical University, 12 K. Marx Str., Ufa 450000, Russian Federation
  • D. M. Vagapova Ufa State Aviation Technical University, 12 K. Marx Str., Ufa 450000, Russian Federation

Abstract: This paper considers the school bus routing problem, which is to ensure delivery of students after lessons from school to their stops. The objective function is to minimize the maximum length of the routes. A short review of the literature on this theme is provided. The problem definition and formalization is given. The heuristic algorithm proposed by the authors earlier is described. A two-step algorithm based on ant colony metaheuristics is described. The algorithm consists of initial clustering of stops at which students drop off, and subsequent ant colony optimization with different parameters, which is applied to each cluster. The results of comparing the efficiency of the proposed algorithms and the performance of the program for two algorithms are presented.

Keywords:  vehicle routing problem; school bus routing problem; ant colony optimization; clustering

MODELS FOR REPRESENTATION AND TREATMENT OF REFERENCE VALUES .
  • M. P. Krivenko Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: The article considers the problem of modeling reference values - results of a certain type of quantities obtained from a single individual or a group of individuals corresponding to a stated description. For this purpose, the article proposes to use a mixture of normal distributions, which can effectively serve as a means of approximating the actual data and to be accessible from the standpoint of theoretical analysis. In estimating the parameters of mixture of distributions, the major role is played by the maximum likelihood method and its embodiment in the form of the expectation-maximization (EM) algorithm. For assessing the number of mixture components, the article suggests to use the likelihood ratio test and a method based on the chi-square distance between the distributions. Their properties are investigated using the bootstrap method. As an experiment, the article considers the description of the empirical distribution of patient data, including the age and measurements of PSA (Prostate-Specific Antigen). The proposed solutions have clear advantages: high detail by age, smoothing the results of observations for age groups which are different in size, and the opportunity to form assumptions about the nature of the relationship between age and PSA.

Keywords:  mixture of normal distributions; assessing the number of components in mixture models; reference values

FORECASTS RECONCILIATION FOR HIERARCHICAL TIME SERIES FORECASTING PROBLEM .
  • M. M. Stenina Moscow Institute of Physics and Technology, 9 Institutskiy Per., Dolgoprudny, Moscow Region 141700, Russian Federation
  • V. V. Strijov  Dorodnicyn Computing Center, Russian Academy of Sciences, 40 Vavilov Str., Moscow 119333, Russian Federation

Abstract: The hierarchical time series forecasting problem is researched. Time series forecasts must satisfy the physical constraints and the hierarchical structure. In this paper, a new algorithm for hierarchical time series forecasts reconciliation is proposed. The algorithm is called GTOp (Game-theoretically optimal reconciliation).
It guarantees that the quality of reconciled forecasts is not worse than the quality of self-dependent forecasts. This approach is based on Nash equilibrium search for the antagonistic game and turns the forecasts reconciliation problem into the optimization problem with equality and inequality constraints. It is proved that the Nash equilibrium in pure strategies exists in the game if some assumptions about the hierarchical structure, the physical constraints, and the loss function are satisfied. The algorithm performance is demonstrated for different types of hierarchical structures of time series.

Keywords:  hierarchical time series; reconciliation of time series forecasts; antagonistic game; Nash equilibrium

NONPARAMETRIC ESTIMATION OF MULTIDIMENSIONAL DENSITY WITH THE USE OF WAVELET ESTIMATES OF UNIVARIATE PROJECTIONS .
  • O. V. Shestakov  Department of Mathematical Statistics, Faculty of Computational Mathematics and Cybernetics, M.V. Lomonosov Moscow State University, 1-52 Leninskiye Gory, GSP-1, Moscow 119991, Russian Federation, Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: The paper explores the computerized tomography method of inverting the Radon transformation for obtaining statistical estimates of multidimensional probability densities. This method utilizes nonlinear wavelet estimators of univariate projections to construct the multidimensional density estimate. Nonlinear wavelet estimators possess the ability to adapt to the local properties of the estimated density function and, therefore, are less sensitive to the singular points than linear estimators. Another important practical feature of the considered method is its parallel structure, which allows a considerable speedup of constructing the estimates on the computers supporting parallel processing. It is also proved that under some regularity conditions, the uniform distance between the constructed estimate and the true multidimensional probability density converges to zero in the mean, and some estimates of the rate of this convergence are obtained.

Keywords: wavelets; multidimensional density; Radon transformation

ASSOCIATIVE PORTRAITS OF SUBJECT AREAS AS A TOOL FOR AUTOMATED CONSTRUCTION OF BIG DATA SYSTEMS FOR KNOWLEDGE EXTRACTION: THEORY, METHODS, VISUALIZATION, AND APPLICATION.
  • I. V. Galina Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
  • E. B. Kozerenko Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
  • Yu. I. Morozova Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
  • N. V. Somin Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
  • M. M. Charnine Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: The paper presents the technique of developing systems for extraction of knowledge which employs the approach of automated association portrait of a subject area (APSA) formation and building a semantic context space (SCS). The ideology of the APSA is based on the distributional hypothesis claiming that semantically equal (or related) lexemes have a similar context and, vice versa, in a similar context, the lexemes are semantically close. The model uses an extended hypothesis that consists in the investigation of similarities and differences in contexts not only of individual words, but of arbitrary multilexeme fragments of meaningful word-combinations. The examples of implemented projects for different subject domains are given.

Keywords: semantic modeling; associations; mathematical statistics; distributive semantics; big data; automated extraction of knowledge; digital natural language text corpora; semantic search; intelligent Internet technology

INDICATORS FOR THEMATIC LINKAGES BETWEEN SCIENCE AND INFORMATION AND COMPUTER TECHNOLOGIES AT THE BEGINNING OF THE XXI CENTURY .
  • V. A. Minin Foundation for Basic Research, 32 A Leninsky Prosp., Moscow 119991, Russian Federation
  • I. M. Zatsman Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
  • V. A. Havanskov Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
  • S. K. Shubnikov Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: Outcomes of experimental evaluation of thematic linkages between science and information and computer technologies (ICT) are presented. The indicator values for the linkages are calculated by the testbed of an analytical information system that was created within the project of the Russian Foundation for Humanities "Information system for monitoring and evaluating innovative and technological potential of the fields of basic research." Texts of inventions on the class G06 (Data processing; Calculations; Account) of the International patent classification were used. These texts, which were published in 2000-2012 by Rospatent, are full-text descriptions of inventions in a natural language. Prior to experimental calculation of indicator values for the linkages, automated extraction of information on the cited scientific publications was retrieved from full-text descriptions. A number of publications was determined for each field of basic research. Obtained numerical information was used for quantitative evaluation of thematic science-ICT linkages and gave the possibility to define an intensity of knowledge transfer from science to ICT sphere and estimate the linkages by quantitative indicators.

Keywords:  science-technology linkages; information and communication technologies; processing of invention text; regular expressions; classifying; evaluation of indicator values

 

RUS

Rambler's Top100 Rambler's Top100