Search

Search Results

• STUDY OF POSSIBILITIES OF USING PHOTONIC AND QUANTUM COMPUTING TECHNOLOGIES TO CALCULATE EXACT PROBABILITY DISTRIBUTIONS OF STATISTIC VALUES FROM FINITE DISCRETE SEQUENCES

  А.К. Melnikov

  121-136

  2025-12-30

  Abstract ▼

  This article explores the feasibility of using photonic and quantum computing technologies to calculate exact probability distributions of discrete sequence statistics, assuming the existence of working hardware prototypes of computing systems and the development of the required quantum algorithms. The performance evaluation of computing systems based on photonic computing technologies is based on materials from the Sarov Scientific Center for Physics and Microphysics of the Russian Academy of Sciences. The performance of a quantum computing system is assessed by comparing the time it takes to solve a boson sampling problem from a given distribution on a computing system with known performance and the time it takes to solve it on a quantum computing system. To assess the feasibility of using photonic and quantum computing technologies to calculate exact distributions, modern methods for calculating them are considered. These methods are based on solving the type multiplicity equation and a system of linear equations in non-negative integers. Analytical expressions determining the computational complexity of these methods are presented. The values of the boundaries of the parameters of exact distributions accessible for calculation using photonic and quantum computing technologies are determined. A comparison of the obtained results with the results of using multiprocessor computing technologies to calculate exact distributions using various methods is presented. An analysis of the feasibility of using photonic and quantum computing technologies to calculate exact distributions is conducted by comparing the number of parameter pairs that can be calculated for exact distributions with the total number of distribution parameters within the Fisher region, which determines a fivefold increase in sample size over the alphabet size. An analysis of the data on the number of sample parameters shows that with increasing performance of the computing technologies used, the ability to calculate exact distributions increases. However, even with the most powerful quantum technologies, this number does not exceed one-tenth of the total number of exact distributions required for statistical analysis of discrete sequences in alphabets up to 256 characters long

• ON THE ACCURACY AND COMPLEXITY OF THE MULTI-STAGE METHOD FOR CORRECTING DISTORTED TEXTS DEPENDING ON THE DEGREE OF DISTORTION

  D.V. Vakhlakov, V. А. Peresypkin, А.V. Germanovich, S.Y. Melnikov, N.N. Copkalo

  130-142

  2021-10-05

  Abstract ▼

  One of the main factors that significantly complicate the understanding, translation and analysis of texts obtained by automatic recognition of speech or images of texts is the presence of distortions in the form of erroneous symbols, words and phrases. Until recently, there were no effective software tools for correcting texts with significant distortions, although this task is rele-vant both for Russian and other common languages in the context of the active use of recognition systems in advanced augmented reality systems. The authors proposed a new multi-stage method for correcting distorted texts, which significantly increases the accuracy of the correction (in terms of the number of correctly corrected words in the text) and is based on the sequential detec-tion of errors and their correction. In this paper, we evaluate the accuracy and computational complexity of the proposed method for correcting distorted texts at various levels of distortion, and determine its place among other modern approaches to correction. The most typical errors of recognition systems are: – replacing a word with a similar sound or graphic spelling; – replacing several words with one; – replacing one word with several; – omission of words; – insertion or deletion of short words (including prepositions and conjunctions). As a result of recognition, a distorted text is obtained, which consists mainly of dictionary words, even in places of distortion. With a large number of distortions, the texts become almost unreadable. Due to the fact that it is problematic to select texts with a wide range of distortion levels in the required amount based on the results of real machine recognition of speech and images of texts, software modeling of distor-tions was used. A text distortion technique has been proposed and implemented that simulates the results of recognition systems in a wide range of distortions; distorted texts have been prepared in the required amount. Within the framework of the proposed multi-stage correction method, non-dictionary word forms and words are considered distorted if the probability of their occurrence in the text in accordance with the chosen language model is less than a given threshold. For such distorted words, a list of possible variants of words is built, which includes only those word forms from the dictionary that are at a certain Levenshtein distance from the word under study. The cor-rected text from the tables of word variants is obtained by searching for the most probable chain of word forms. The correction method consists of several stages, at each stage only those frag-ments of the text that remain distorted after the previous stage are corrected. According to the results of the experiments on the correction of distorted texts, it was concluded that the proposed correction method showed good results with an average value of F-measure >50 % in the distor-tion range from 0 to 75 %. Linguistic experts confirmed the fruitfulness of the proposed approach to correction and its preference over other modern approaches, fixing that with a level of distor-tion of up to 50 % of words, the corrected text is read with much less effort than a distorted one, and with a level of distortion of up to 70% of words, the corrected text also allows you to highlight useful information about the content

• ANALYSIS OF ADVANCED COMPUTER TECHNOLOGIES FOR CALCULATION OF EXACT APPROXIMATIONS OF STATISTICS PROBABILITY DISTRIBUTIONS

  А.К. Melnikov, I.I. Levin, А.I. Dordopulo, I.V. Pisarenko

  6-19

  2021-10-05

  Abstract ▼

  In the paper we consider the solution of a computationally expensive problem such as calcu-lation of statistics probability distribution with the help of modern computer technologies. To re-duce computational complexity and to provide a sufficient level of criteria efficiency not less than the specified threshold, we suggest to use Δ-exact approximations. To calculate exact approxima-tions, we use the method of second order, based on solution of a system of linear equations. Owing to this method, it is possible to calculate exact approximations for the maximum values of sample parameters for available computational resource. The most laborious part of the method of second order is the procedure of sequential detection of the vectors of possible solutions and test if the vectors belong to the set of solutions. The system solution set membership test for the vectors of possible solutions is data independent, so the algorithm can be data-parallelized. We give the al-gorithm complexity equation for calculation of exact approximations of statistics probability dis-tributions. Using this equation, we calculated the complexity of modern practical problems for the samples with the parameters (N, n) of the alphabet power and the sample size: (256,1280), (128,640), (128, 320), and (192,3200) for the accuracy of calculations =10-5. The computational complexity is 9.68·1022-1.60·1052 operations, and its average value is about 4.55·1025 operations, the number of tested vectors is 6.50·1023-1.39·1050, and the number of solutions is 4.67·1012-5.60·1025, respectively. The total solution time for clock-round duration of calculations cannot exceed 30 days or 2.592·106 sec. For the obtained complexity evaluation, we analysed abilities of modern cluster computer systems based on general-purpose processors, graphic accelerators, and FPGA-based reconfigurable computer systems. For each technology, we determined the number of computational nodes needed for calculation of exact approximations with the specified parameters during the specified time. We proved that it is impossible to obtain a solution for the required pa-rameters of exact approximations of statistics probability with the help of the reviewed modern computer technologies. In conclusion, we claim that it is necessary to analyse the abilities of ad-vanced computer technologies based of quantum and photonic computers, and also hybrid com-puter systems for calculation of exact approximations of statistics probability distributions with the specified parameters during reasonable time

• ANALYSIS OF ADVANCED COMPUTER TECHNOLOGIES FOR CALCULATION OF EXACT APPROXIMATIONS OF STATISTICS PROBABILITY DISTRIBUTIONS

  А.К. Melnikov, I.I. Levin, А.I. Dordopulo, L.M. Slasten

  2022-11-01

  Abstract ▼

  The paper is devoted to the evaluation of the hardware resource of computer systems for
  solving a computational-expensive problem such as calculation of the probability distributions of
  statistics by the second multiplicity method based on Δ-exact approximations for samples with a
  size of 320-1280 characters and an alphabet power of 128-256 characters, and with an accuracy
  of Δ=10-5. The total solution time should not exceed 30 days or 2.592·106 seconds for 24/7 computing.
  Owing to the use of the properties of the second multiplicity method, the computational complexity
  of the calculations can be brought to the range of 9.68·1022-1.60·1052 operations with the
  number of tested vectors of 6.50·1023-1.39·1050. The solution of this problem for the specified parameters
  of samples during the given time requires the hardware resource which cannot be provided
  by modern computer means such as processors, graphics accelerators, programmable logic
  integrated circuits. Therefore, in the paper we analyze the possibilities of promising quantum and
  photon technologies for solving the problem with the given parameters. The main advantage of
  quantum computer systems is the high speed of calculations for all possible parameter values.
  However, quantum acceleration will not be achieved to calculate the probability distributions of
  statistics due to the need to check all the obtained solutions. Here, the number of obtained solutions
  corresponds to the dimension of the problem. In addition, due to the current development
  level of the quantum hardware components, it is impossible to create and use the 120-qubit quantum
  computers for the solution of the considered problem. Photon computers can provide high
  computation speed at low power consumption and require the smallest number of nodes to solve
  the considered problem. However, unsolved problems with the physical implementation of efficient
  memory elements and the lack of available hardware components make the use of photon computer
  technologies impossible for calculation of the probability distributions of statistics in the near
  future (5-7 years). Therefore, it is most reasonable to use hybrid computer systems containing
  nodes of different architectures. To solve the problem on various hardware platforms (generalpurpose
  processors, GPUs, FPGAs) and configurations of hybrid computer systems, we suggest to
  use an architecture independent high-level programming language SET@L. The language combines
  the representation of calculations as sets and collections (based on the alternative set theory
  of P. Vopenka), the absolutely parallel form of the problem represented as an information graph,
  and the paradigm of aspect-oriented programming.

• SOME ASPECTS OF APPLICATION OF ARTIFICIAL INTELLIGENCE TECHNOLOGIES IN INFORMATION SECURITY (REVIEW)

  S.Y. Melnikov, R. V. Meshcheryakov, V. А. Peresypkin

  2024-11-10

  Abstract ▼

  Artificial intelligence (AI) technologies are one of the most dynamically developing areas of information
  processing. AI technologies are used both to ensure the information security and to organize attacks
  on information security tools. AI systems themselves may contain vulnerabilities and be susceptible
  to various types of attacks. The article analyzes some aspects of the use of AI technologies in information
  security tasks. Within the framework of the task of biometric identification, threats of falsification of biometric
  identification characteristics in order to obtain access rights, and ways to counter such threats are
  considered. The advantages of using AI in protecting information in computer systems and networks in
  comparison with traditional means of protection are analyzed. Using the example of an acoustic channel
  of information leakage from a keyboard, the use of AI technologies for processing data from technical
  leakage channels is illustrated. Methods for increasing the information content of such channels using temporary convolutional networks and image classification models, as well as ways to counter them, are
  considered. Special attention is paid to information security issues in increasingly popular systems for
  compressing and transmitting information without significant semantic losses (Semantic Communications).
  A number of information security issues that arise when using large language models such as
  ChatGPT, capable of massively generating unique “human-like” content and using it to organize phishing
  and other social engineering attacks, are considered. An attack on AI systems using a covert channel is
  described. Attention is paid to the need to develop trusted artificial intelligence technologies

• LIMITING THE NUMBER OF DIFFERENT TEST VECTORS TO OBTAIN ALL SOLUTIONS OF A SYSTEM OF THE SECOND MULTIPLICITY LINEAR EQUATIONS ON MULTIPROCESSOR COMPUTER SYSTEM

  А.К. Melnikov

  2021-07-18

  Abstract ▼

  In the paper we consider calculation of all integer nonnegative solutions of a linear equation
  system (LES) of the second types order by a method of sequential vector testing. The method
  checks whether a vector is a solution of the LES. We consider different vectors and test if they
  belong to the set of the LES solutions. As a result, after such testing we obtain all solutions of the
  LES. The LES testing vector consists of the elements which are the numbers of some alphabet signs
  with the same number of occurrences in the sample. The LES unites the number of occurrences of
  the elements of all types into the considering sample, the power of the alphabet, the size of the
  sample, and the limitation for the maximum number of occurrences of the alphabet signs into the
  sample. The LES solution is the base for calculation of exact statistics probability distributions
  and their exact approximations by the method of the second types order. Here, the exact approximations
  are Δexact distributions. The difference between the Δexact distributions and the exact
  distributions does not exceed the predefined arbitrary small value Δ. The number of test vectors is
  one of those which defines algorithmic complexity of the method of second types order. Without it,
  it is impossible to define the parameters of samples, and to calculate exact distributions and their
  exact approximations for limited hardware resource. We consider various test vectors for the limited
  maximum number of occurrences of the alphabet signs in the sample, and for the unlimited
  one. We have obtained formulas to calculate the number of tests for various vectors. Here, the
  values of the power of the alphabet, the size of the sample, and the limitations for the maximum
  number of occurrences of the alphabet signs into the sample can be arbitrary. Using the obtained
  formulas, we can get all integer nonnegative solutions of the LES of the second types order. We
  can use the obtained formula for analysis of algorithmic complexity of calculations of exact distributions
  and their exact approximations with the predefined accuracy Δ.

• CALCULATION OF THE NUMBER OF SOLUTIONS TO THE EQUATION OF THE FIRST MULTIPLICITY OF TYPES UNDER RESTRICTIONS ON THE FREQUENCY OF OCCURRENCE OF ALPHABET CHARACTERS

  A.K. Melnikov

  2021-02-25

  Abstract ▼

  The article considers the number of solutions to the equation of the first multiplicity of types,
  composed of vectors of multiplicity of types, each element of which is the number of occurrences of
  elements of a certain type (any sign of the alphabet) in the sample under consideration. The equation
  of the first multiplicity of types relates the number of occurrences of elements of all types in
  the sample under consideration and the volume of this sample. The main attention is paid to the
  conclusion and proof of the correctness of the expression that determines the number of nonnegative
  integer solutions of the equation of the first multiplicity of types under conditions of restrictions
  on the frequency of occurrence of alphabet characters. The solution of the equation ofthe first multiplicity of types is the basis for calculating exact approximations of the probabilities
  of statistical values by the first multiplicity method, where the exact approximations are Δexact
  distributions that differ from the exact distributions by no more than a predetermined, arbitrarily
  small value Δ. The value that expresses the number of solutions to the equation of the first multiplicity
  of types is one of the values that determine the algorithmic complexity of the method of the
  first multiplicity, without knowing the value of which it is impossible to determine the parameters
  of samples for which, under restrictions on the computational resource, exact approximations of
  distributions can be calculated. Also, the value expressing the number of solutions to the equation
  of the first multiplicity of types is used in the method of the first multiplicity to limit the search area
  for solutions to the equation. The number of solutions to the equation of the first multiplicity is
  considered under conditions of restriction on the maximum value of the elements of the multiplicity
  vector, and the case is considered when one or more elements of the alphabet may be missing in
  the sample. First obtained the expression that defines the number of nonnegative integer solutions
  to equations of the first multiplicity of types in terms of restrictions on the values of the frequencies
  of occurrence of signs and the possibility of absence of one or more characters of the alphabet in
  the sample reviewed. Analytical expressions are obtained that allow calculating the number of
  integer nonnegative solutions of the equation of the first multiplicity of types for any values of the
  alphabet power, the sample size, and the limit on the maximum frequency of occurrence of alphabet
  characters. The form of the obtained expression allows you to use it when studying the algorithmic
  complexity of calculating exact approximations of probability distributions of statistical
  values with a pre-specified accuracy Δ.

• ALGORITHMIC COMPLEXITY OF CALCULATING EXACT APPROXIMATIONS OF PROBABILITY DISTRIBUTIONS OF STATISTICAL VALUES BY SOLVING THE EQUATION OF THE FIRST MULTIPLICITY OF TYPES

  A.K. Melnikov

  2021-02-25

  Abstract ▼

  We consider the algorithmic complexity of calculating the exact probability distributions of
  statistical values and their exact approximations by solving the first multiplicity equation. As exact
  approximations of probability distributions of statistical values, we consider their Δ−exact distributions
  that differ from the exact distributions by no more than a predetermined, arbitrarily small
  valueΔ. It is shown that the basis of the method for calculating the exact probability distributions
  of statistical values is the enumeration of elements of the search area for solutions to a linear
  equation of multiplicity of types, composed of vectors of multiplicity of types, each element of
  which is the number of occurrences of elements of a certain type (any sign of the alphabet) in the
  sample under consideration. At the same time, it is shown that the method of limiting the search
  area for solutions is used to calculate exact approximations of the probability distribution of statistical
  values. An expression is given that defines the algorithmic complexity of calculating exact
  distributions by solving the first multiplicity equation. The given expression is finite and allows for
  each value of the alphabet power to determine the maximum sample size for which, using a limited
  computational resource, exact distributions can be calculated by solving the first multiplicity
  equation. The range of parameters represented by the sample size and alphabet power for which
  exact distributions can be calculated with a limited computing resource is defined. To estimate the
  algorithmic complexity of calculating exact approximations of distributions, we present an expression
  for the first time obtained for the number of solutions to the equation of the first multiplicity
  with a restriction on the coordinate values of the solution vectors. An expression is given that defines
  the algorithmic complexity of calculating exact approximations by solving the first multiplicity
  equation with a restriction on the coordinate values of the solution vectors. As a parameter for
  limiting the coordinates of solution vectors, the maximum frequency statistic value is used, the
  probability of exceeding it is less than a pre-set, arbitrarily small valueΔ, which allows calculating
  exact approximations of distributions that differ from their exact distributions by no more than the
  selected value Δ. The given expression is finite and allows for each value of the alphabet to determine
  the maximum sample size for which, when using a limited computational resource, exact
  approximations can be calculated by solving the equation of the first multiplicity under the restrictions
  set using the valueΔ. The results of calculations of the maximum sample volumes for
  which exact approximations can be calculated are presented. It is shown that the algorithmiccomplexity of calculating exact distributions exceeds the complexity of calculating their exact approximations
  by many orders of magnitude. It is shown that the use of the first multiplicity method
  for calculating exact approximations allows for the same values of the alphabet power to increase
  the sample volume by two or more times compared to the calculation of exact distributions.

• MULTI-PASS METHOD FOR AUTOMATIC CORRECTION OF DISTORTED TEXTS

  D.V. Vakhlakov, V.A. Peresypkin, S.Y. Melnikov

  2021-02-25

  Abstract ▼

  One of the main factors that significantly complicate the understanding, translation and
  analysis of texts obtained by automatic speech recognition or optical recognition of text images
  are the distortions contained in them in the form of erroneous characters, words and phrases.
  The most typical errors of recognition systems are: – replacement of a word with a similar sounding
  or graphic spelling; – replacing several words with one; – replacement of one word with several;
  – skipping words; – insertion or deletion of short words (including prepositions and conjunctions).
  As a result of recognition, a text is obtained that has distortions and consists mainly of dictionary
  words, including in places of distortion. With a large amount of distortion, the texts become
  almost unreadable. Automatic processing of such texts is very difficult, although this task is
  relevant both for Russian and for other common languages. Correction software that works well at
  low distortions in the text, in the case of texts with a high level of distortion, regardless of their
  origin, show unsatisfactory results. This makes it necessary to develop independent approaches to
  correcting distorted texts. A new multi-pass method for correction of distorted texts based on sequential
  error identification and correction of distorted texts is proposed. Non-dictionary word
  forms and word forms which occurrence probability in the text in accordance with the selected
  probabilistic model is less than a preset threshold are considered to be distorted. After setting of
  the distortion sign for individual words, this sign is spread to their combinations, i.e. distorted text
  fragments are extracted. A list of possible word variants which includes only those word forms
  from the dictionary that are located at a certain Levenshtein distance from the word under study is
  built for them. The corrected text from word variants is obtained by searching for the most probable
  chain of word forms. The correction method consists of several passes, at each pass only those
  fragments of the text are corrected that remained distorted after the previous pass of correction.
  The method allows to increase significantly the quality (accuracy) of the correction. In the carried
  out experiments the quality of correction in terms of the F1-measure for moderately distorted texts
  has been increased by 9 %, and for highly distorted texts – by 7.7 %.