Все выпуски

В последнее время седловым задачам уделяется большое внимание благодаря их мощным возможностям моделирования для множества задач из различных областей. Приложения этих задач встречаются в многочисленных современных прикладных областях, таких как робастная оптимизация, распределенная оптимизация, теория игр и~приложения машинного обучения, такие как, например, минимизация эмпирического риска или обучение генеративно-состязательных сетей. Поэтому многие исследователи активно работают над разработкой численных методов для решения седловых задач в самых разных предположениях. Данная статья посвящена разработке численного метода решения седловых задач в невыпуклой равномерно вогнутой постановке. В этой постановке считается, что по группе прямых переменных целевая функция может быть невыпуклой, а по группе двойственных переменных задача является равномерно вогнутой (это понятие обобщает понятие сильной вогнутости). Был изучен более общий класс седловых задач со сложной композитной структурой и гёльдерово непрерывными производными высшего порядка. Для решения рассматриваемой задачи был предложен подход, при котором мы сводим задачу к комбинации двух вспомогательных оптимизационных задач отдельно для каждой группы переменных: внешней задачи минимизации и~внутренней задачи максимизации. Для решения внешней задачи минимизации мы используем адаптивный градиентный метод, который применим для невыпуклых задач, а также работает с неточным оракулом, который генерируется путем неточного решения внутренней задачи максимизации. Для решения внутренней задачи максимизации мы используем обобщенный ускоренный метод с рестартами, который представляет собой метод, объединяющий методы ускорения высокого порядка для минимизации выпуклой функции, имеющей гёльдерово непрерывные производные высшего порядка. Важной компонентой проведенного анализа сложности предлагаемого алгоритма является разделение оракульных сложностей на число вызовов оракула первого порядка для внешней задачи минимизации и оракула более высокого порядка для внутренней задачи максимизации. Более того, оценивается сложность всего предлагаемого подхода.

Recently, saddle point problems have received much attention due to their powerful modeling capability for a lot of problems from diverse domains. Applications of these problems occur in many applied areas, such as robust optimization, distributed optimization, game theory, and many applications in machine learning such as empirical risk minimization and generative adversarial networks training. Therefore, many researchers have actively worked on developing numerical methods for solving saddle point problems in many different settings. This paper is devoted to developing a numerical method for solving saddle point problems in the nonconvex uniformly-concave setting. We study a general class of saddle point problems with composite structure and H\"older-continuous higher-order derivatives. To solve the problem under consideration, we propose an approach in which we reduce the problem to a combination of two auxiliary optimization problems separately for each group of variables, the outer minimization problem w.r.t. primal variables, and the inner maximization problem w.r.t the dual variables. For solving the outer minimization problem, we use the Adaptive Gradient Method, which is applicable for nonconvex problems and also works with an inexact oracle that is generated by approximately solving the inner problem. For solving the inner maximization problem, we use the Restarted Unified Acceleration Framework, which is a framework that unifies the high-order acceleration methods for minimizing a convex function that has H\"older-continuous higher-order derivatives. Separate complexity bounds are provided for the number of calls to the first-order oracles for the outer minimization problem and higher-order oracles for the inner maximization problem. Moreover, the complexity of the whole proposed approach is then estimated.

В статье сформулирован обобщенный подход к выбору значений структурных параметров искусственной нейронной сети (ИНС) и объема обучающий выборки, основанный на принципе минимизации количества элементов структуры ИНС и объема обучающей выборки при ограничении на значение показателя качества работы нейросетевой модели динамики объекта. Реализован алгоритм выбора структурных параметров ИНС и построения нейросетевой модели.
Проведена серия вычислительных экспериментов, демонстрирующая применимость алгоритма для построения моделей динамических объектов, в основе которых лежит нелинейная автокорреляционная нейронная сеть.

The article presents an approach to configuration of an artificial neural network architecture and a training set size. Configuration is based on parameter minimization with constraints specifying neural network model quality criteria. The algorithm of artificial neural network architecture and training set size configuration is applied to dynamic object artificial neural network approximation.
Series of computational experiments were performed. The method is applicable to construction of dynamic object models based on non-linear autocorrelation neural networks.

В данной статье исследуются методы машинного обучения с определенным видом решающего правила. К ним относятся интерполяция по методу обратно взвешенных расстояний, метод интерполяции радиальными базисными функциями, метод многомерной интерполяции и аппроксимации на основе теории случайных функций, кригинг. Показано, что для данных методов существует способ быстрого переобучения «модели» при добавлении новых данных к существующим. Под «моделью» понимается построенная по обучающим данным интерполирующая или аппроксимирующая функция. Данный подход позволяет уменьшить вычислительную сложность построения обновленной «модели» с $O(n^3)$ до $O(n^2)$. Также будет исследована возможность быстрого оценивания обобщающих возможностей «модели» на обучающей выборке при помощи метода скользящего контроля leave-one-out cross-validation, устранив главный недостаток такого подхода — необходимость построения новой «модели» при каждом удалении элемента из обучающей выборки.

We investigate machine learning methods with a certain kind of decision rule. In particular, inverse-distance method of interpolation, method of interpolation by radial basis functions, the method of multidimensional interpolation and approximation, based on the theory of random functions, the last method of interpolation is kriging. This paper shows a method of rapid retraining “model” when adding new data to the existing ones. The term “model” means interpolating or approximating function constructed from the training data. This approach reduces the computational complexity of constructing an updated “model” from $O(n^3)$ to $O(n^2)$. We also investigate the possibility of a rapid assessment of generalizing opportunities “model” on the training set using the method of cross-validation leave-one-out cross-validation, eliminating the major drawback of this approach — the necessity to build a new “model” for each element which is removed from the training set.

Адекватное моделирование сложной динамики городских транспортных потоков требует сбора больших объемов данных для определения характера соответствующих моделей и их калибровки. Вместе с тем оборудование специализированных постов наблюдения является весьма затратным мероприятием и не всегда технически возможно. Совокупность этих факторов приводит к недостаточному фактографическому обеспечению как систем оперативного управления транспортными потоками, так и специалистов по транспортному планированию с очевидными последствиями для качества принимаемых решений. В качестве способа обеспечить массовый сбор данных хотя бы для качественного анализа ситуаций достаточно давно применяется обзорные видеокамеры, транслирующие изображения в определенные ситуационные центры, где соответствующие операторы осуществляют контроль и управление процессами. Достаточно много таких обзорных камер предоставляют данные своих наблюдений в общий доступ, что делает их ценным ресурсом для транспортных исследований. Вместе с тем получение количественных данных с таких камер сталкивается с существенными проблемами, относящимися к теории и практике обработки видеоизображений, чему и посвящена данная работа. В работе исследуется практическое применение некоторых мейнстримовских нейросетевых технологий для определения основных характеристик реальных транспортных потоков, наблюдаемых камерами общего доступа, классифицируются возникающие при этом проблемы и предлагаются их решения. Для отслеживания объектов дорожного движения применяются варианты сверточных нейронных сетей, исследуются способы их применения для определения базовых характеристик транспортных потоков. Простые варианты нейронной сети используются для автоматизации при получении обучающих примеров для более глубокой нейронной сети YOLOv4. Сеть YOLOv4 использована для оценки характеристик движения (скорость, плотность потока) для различных направлений с записей камер видеонаблюдения.

Correct modeling of complex dynamics of urban transportation flows requires the collection of large volumes of empirical data to specify types of the modes and their identification. At the same time, setting a large number of observation posts is expensive and technically not always feasible. All this results in insufficient factographic support for the traffic control systems as well as for urban planners with the obvious consequences for the quality of their decisions. As one of the means to provide large-scale data collection at least for the qualitative situation analysis, the wide-area video cameras are used in different situation centers. There they are analyzed by human operators who are responsible for observation and control. Some video cameras provided their videos for common access, which makes them a valuable resource for transportation studies. However, there are significant problems with getting qualitative data from such cameras, which relate to the theory and practice of image processing. This study is devoted to the practical application of certain mainstream neuro-networking technologies for the estimation of essential characteristics of actual transportation flows. The problems arising in processing these data are analyzed, and their solutions are suggested. The convolution neural networks are used for tracking, and the methods for obtaining basic parameters of transportation flows from these observations are studied. The simplified neural networks are used for the preparation of training sets for the deep learning neural network YOLOv4 which is later used for the estimation of speed and density of automobile flows.

С помощью программы, созданной на принципах компьютерного автоматизированного анализа, на планарных сцинтиграммах скелета больных диссеминированным раком молочной железы выделены очаги гиперфиксации радиофармпрепарата. Рассчитаны гистограммные параметры: средняя яркость, гладкость яркости, третий момент яркости, однородность яркости, энтропия яркости. Установлено, что в большинстве зон скелета значения гистограммных параметров в патологических очагах гиперфиксации преобладают над аналогичными значениями в физиологических. Наиболее часто в патологических очагах гиперфиксации, как на передних, так и на задних сцинтиграммах, фиксируется преобладание показателей яркости и гладкости яркости изображения по сравнению с аналогичными показателями физиологических очагов гиперфиксации радиофармпрепарата. Отдельные показатели гистограммного анализа используются в уточняющей диагностике метастазов при математическом моделировании и интерпретации данных остеосцинтиграфии.

The practical application of nuclear medicine demonstrates the continued information deficiency of the algorithms and programs that provide visualization and analysis of medical images. The aim of the study was to determine the principles of optimizing the processing of planar osteostsintigraphy on the basis of сomputer aided diagnosis (CAD) for analysis of texture descriptions of images of metastatic zones on planar scintigrams of skeleton. A computer-aided diagnosis system for analysis of skeletal metastases based on planar scintigraphy data has been developed. This system includes skeleton image segmentation, calculation of textural, histogram and morphometrical parameters and the creation of a training set. For study of metastatic images’ textural characteristics on planar scintigrams of skeleton was developed the computer program of automatic analysis of skeletal metastases is used from data of planar scintigraphy. Also expert evaluation was used to distinguishing ‘pathological’ (metastatic) from ‘physiological’ (non-metastatic) radiopharmaceutical hyperfixation zones in which Haralick’s textural features were determined: autocorrelation, contrast, ‘forth moment’ and heterogeneity. This program was established on the principles of сomputer aided diagnosis researches planar scintigrams of skeletal patients with metastatic breast cancer hearths hyperfixation of radiopharmaceuticals were identified. Calculated parameters were made such as brightness, smoothness, the third moment of brightness, brightness uniformity, entropy brightness. It has been established that in most areas of the skeleton of histogram values of parameters in pathologic hyperfixation of radiopharmaceuticals predominate over the same values in the physiological. Most often pathological hyperfixation of radiopharmaceuticals as the front and rear fixed scintigramms prevalence of brightness and smoothness of the image brightness in comparison with those of the physiological hyperfixation of radiopharmaceuticals. Separate figures histogram analysis can be used in specifying the diagnosis of metastases in the mathematical modeling and interpretation bone scintigraphy. Separate figures histogram analysis can be used in specifying the diagnosis of metastases in the mathematical modeling and interpretation bone scintigraphy.

Ингибиторы гистондеацетилаз (HDACi) рассматриваются в качестве перспективного класса препаратов для лечения рака из-за их влияния на рост клеток, дифференцировку и апоптоз. Ангиогенез играет важную роль в росте солидных опухолей и развитии метастазов. Фактор роста эндотелия сосудов (VEGF) является ключевым ангиогенным агентом, который секретируется злокачественными опухолями, что индуцирует пролиферацию и миграцию эндотелиальных клеток сосудов. В настоящее время наиболее перспективной стратегией в борьбе с онкологическими заболеваниями является создание гибридных лекарств, одновременно действующих на несколько физиологических мишеней. Значительный интерес с точки зрения создания бифункциональных противоопухолевых средств представляют соединения, содержащие одновременно N-фенил-4-аминохиназолин и гидроксамовую кислоту, так как данные фрагменты по отдельности присутствуют в уже успешно применяемых противоопухолевых лекарственных средствах. В этой связи в ходе литературного анализа была сформирована выборка из 42 соединений, содержащих указанные молекулярные фрагменты и обладающих экспериментальными данными по ингибированию HDAC, VEGFR-2 и росту клеток рака легкого человека MCF-7. С использованием симплексных дескрипторов и метода опорных векторов (Support Vector Machine, SVM) для указанной выборки, предварительно разделенной на обучающий и тестовый наборы, были построены удовлетворительные (R²_test = 0.64–0.87) модели количественной связи «структура–активность» (Quantitative Structure- Activity Relationship, QSAR). Для полученных QSAR-моделей была проведена структурная интерпретация. Было оценено согласованное влияние различных молекулярных фрагментов на увеличение противоопухолевой активности исследуемых соединений. Среди заместителей N-фенильного фрагмента можно выделить положительный вклад брома в пара-положении для всех трех видов активности. По результатам интерпретации был проведен рациональный молекулярный дизайн и предложены перспективные соединения. Для сравнительного QSAR-исследования использованы физико-химические дескрипторы, рассчитываемые программой HYBOT, метод случайного леса (Random Forest, RF), а также онлайн-версия экспертной системы OCHEM (https://ochem.eu). При моделировании OCHEM были выбраны PyDescriptor-дескрипторы и метод экстремального градиентного бустинга. Кроме того, полученные с помощью экспертной системы OCHEM модели были использованы для виртуального скрининга 300 соединений с целью отбора перспективных VEGFR-2/HDAC-ингибиторов для последующего синтеза и испытаний.

Inhibitors of histone deacetylases (HDACi) have considered as a promising class of drugs for the treatment of cancers because of their effects on cell growth, differentiation, and apoptosis. Angiogenesis play an important role in the growth of most solid tumors and the progression of metastasis. The vascular endothelial growth factor (VEGF) is a key angiogenic agent, which is secreted by malignant tumors, which induces the proliferation and the migration of vascular endothelial cells. Currently, the most promising strategy in the fight against cancer is the creation of hybrid drugs that simultaneously act on several physiological targets. In this work, a series of hybrids bearing N-phenylquinazolin-4-amine and hydroxamic acid moieties were studied as dual VEGFR-2/HDAC inhibitors using simplex representation of the molecular structure and Support Vector Machine (SVM). The total sample of 42 compounds was divided into training and test sets. Five-fold cross-validation (5-fold) was used for internal validation. Satisfactory quantitative structure—activity relationship (QSAR) models were constructed (R²_test = 0.64–0.87) for inhibitors of HDAC, VEGFR-2 and human breast cancer cell line MCF-7. The interpretation of the obtained QSAR models was carried out. The coordinated effect of different molecular fragments on the increase of antitumor activity of the studied compounds was estimated. Among the substituents of the N-phenyl fragment, the positive contribution of para bromine for all three types of activity can be distinguished. The results of the interpretation were used for molecular design of potential dual VEGFR-2/HDAC inhibitors. For comparative QSAR research we used physicochemical descriptors calculated by the program HYBOT, the method of Random Forest (RF), and on-line version of the expert system OCHEM (https://ochem.eu). In the modeling of OCHEM PyDescriptor descriptors and extreme gradient boosting was chosen. In addition, the models obtained with the help of the expert system OCHEM were used for virtual screening of 300 compounds to select promising VEGFR-2/HDAC inhibitors for further synthesis and testing.

В статье предлагается ряд подходов к обработке изображений в системе поддержки принятия решений (СППР) центра автоматизированной фиксации административных правонарушений дорожного движения (ЦАФАП). Основной задачей данной СППР является помощь человеку-оператору в получении точной информации о государственном регистрационном знаке (ГРЗ) и модели транспортного средства (ТС) на основании изображений, полученных с комплексов фотовидеофиксации (ФВФ). В статье предложены подходы к распознаванию ГРЗ и марки/модели ТС на изображении, основанные на современных нейросетевых моделях. Для распознавания ГРЗ использована нейросетевая модель LPRNet с дополнительно введенным Spatial Transformer Layer для предобработки изображения. Для автоматического определения марки/модели ТС на изображении использована нейросетевая архитектура ResNeXt-101-32x8d. Предложен подход к формированию обучающей выборки для нейросетевой модели распознавания ГРЗ, основанный на методах компьютерного зрения и алгоритмах машинного обучения. В данном подходе использован алгоритм SIFT для нахождения ключевых точек изображения с ГРЗ и вычисления их дескрипторов, а для удаления точек-выбросов использован алгоритм DBSCAN. Точность распознавания ГРЗ на тестовой выборке составила 96 %. Предложен подход к повышению производительности процедур дообучения и распознавания марки/модели ТС, основанный на использовании новой архитектуры сверточной нейронной сети с «заморозкой» весовых коэффициентов сверточных слоев, дополнительным сверточным слоем распараллеливания процесса классификации и множеством бинарных классификаторов на выходе. Применение новой архитектуры позволило на несколько порядков уменьшить время дообучения нейросетевой модели распознавания марки/модели ТС с итоговой точностью классификации, близкой к 99 %. Предложенные подходы были апробированы и внедрены в СППР ЦАФАП Республики Татарстан.

We suggested some approaches for solving image processing tasks in the decision support system (DSS) of the Center for Automated Recording of Administrative Offenses of the Road Traffic (CARAO). The main task of this system is to assist the operator in obtaining accurate information about the vehicle registration plate and the vehicle brand/model based on images obtained from the photo and video recording systems. We suggested the approach for vehicle registration plate recognition and brand/model classification on the images based on modern neural network models. LPRNet neural network model supplemented by Spatial Transformer Layer was used to recognize the vehicle registration plate. The ResNeXt-101-32x8d neural network model was used to classify for vehicle brand/model. We suggested the approach to construct the training set for the neural network of vehicle registration plate recognition. The approach is based on computer vision methods and machine learning algorithms. The SIFT algorithm was used to detect and describe local features on images with the vehicle registration plate. DBSCAN clustering was used to detect and delete outliers in such local features. The accuracy of vehicle registration plate recognition was 96% on the testing set. We suggested the approach to improve the efficiency of using the ResNeXt-101-32x8d model at additional training and classification stages. The approach is based on the new architecture of convolutional neural networks with “freezing” weight coefficients of convolutional layers, an additional convolutional layer for parallelizing the classification process, and a set of binary classifiers at the output. This approach significantly reduced the time of additional training of neural network when new vehicle brand/model classification was needed. The final accuracy of vehicle brand/model classification was 99% on the testing set. The proposed approaches were tested and implemented in the DSS of the CARAO of the Republic of Tatarstan.

В работе рассматривается задача поиска в научной статье фрагментов с недостающими библиографическими ссылками с помощью автоматической бинарной классификации. Для обучения модели предложен метод контрастного семплирования, новшеством которого является рассмотрение контекста ссылки с учетом границ фрагмента, максимально влияющего на вероятность нахождения в нем библиографической ссылки. Обучающая выборка формировалась из автоматически размеченных семплов — фрагментов из трех предложений с метками классов «без ссылки» и «со ссылкой», удовлетворяющих требованию контрастности: семплы разных классов дистанцируются в исходном тексте. Пространство признаков строилось автоматически по статистике встречаемости термов и расширялось за счет конструирования дополнительных признаков — выделенных в тексте сущностей ФИО, чисел, цитат и аббревиатур.

Проведена серия экспериментов на архивах научных журналов «Правоприменение» (273 статьи) и «Журнал инфектологии» (684 статьи). Классификация осуществлялась моделями Nearest Neighbours, RBF SVM, Random Forest, Multilayer Perceptron, с подбором оптимальных гиперпараметров для каждого классификатора.

Эксперименты подтвердили выдвинутую гипотезу. Наиболее высокую точность показал нейросетевой классификатор (95%), уступающий по скорости линейному, точность которого при контрастном семплировании также оказалась высока (91–94 %). Полученные значения превосходят результаты, опубликованные для задач NER и анализа тональности на данных со сравнимыми характеристиками. Высокая вычислительная эффективность предложенного метода позволяет встраивать его в прикладные системы и обрабатывать документы в онлайн-режиме.

The paper studies the problem of searching for fragments with missing bibliographic links in a scientific article using automatic binary classification. To train the model, we propose a new contrast resampling technique, the innovation of which is the consideration of the context of the link, taking into account the boundaries of the fragment, which mostly affects the probability of presence of a bibliographic links in it. The training set was formed of automatically labeled samples that are fragments of three sentences with class labels «without link» and «with link» that satisfy the requirement of contrast: samples of different classes are distanced in the source text. The feature space was built automatically based on the term occurrence statistics and was expanded by constructing additional features — entities (names, numbers, quotes and abbreviations) recognized in the text.

A series of experiments was carried out on the archives of the scientific journals «Law enforcement review» (273 articles) and «Journal Infectology» (684 articles). The classification was carried out by the models Nearest Neighbors, RBF SVM, Random Forest, Multilayer Perceptron, with the selection of optimal hyperparameters for each classifier.

Experiments have confirmed the hypothesis put forward. The highest accuracy was reached by the neural network classifier (95%), which is however not as fast as the linear one that showed also high accuracy with contrast resampling (91–94%). These values are superior to those reported for NER and Sentiment Analysis on comparable data. The high computational efficiency of the proposed method makes it possible to integrate it into applied systems and to process documents online.

В работе описывается метод распознавания авторов литературных текстов по близости фрагментов, на которые разделен отдельный текст, к эталону автора. Эталоном является эмпирическое распределение частот буквосочетаний, построенное по обучающей выборке, куда вошли экспертно отобранные достоверно известные произведения данного автора. Совокупность эталонов разных авторов образует библиотеку, внутри которой и решается задача об идентификации автора неизвестного текста. Близость между текстами понимается в смысле нормы в L1 для вектора частот буквосочетаний, который строится для каждого фрагмента и для текста в целом. Автором неизвестного текста назначается тот, эталон которого чаще всего выбирается в качестве ближайшего для набора фрагментов, на которые разделен текст. Длина фрагмента оптимизируется исходя из принципа максимального различия расстояний от фрагментов до эталонов в задаче распознавания «свой–чужой». Тестирование метода проведено на корпусе отечественных и зарубежных (в переводе) авторов. Были собраны 1783 текста 100 авторов суммарным объемом примерно 700 млн знаков. Чтобы исключить тенденциозность отбора авторов, рассматривались авторы, фамилии которых начинались на одну и ту же букву (в данном случае Л). Ошибка идентификации по биграммам составила 12%. Наряду с достаточно высокой точностью данный метод обладает еще одним важным свойством: он позволяет оценить вероятность того, что эталон автора рассматриваемого текста в библиотеке отсутствует. Эта вероятность может быть оценена по результатам статистики ближайших эталонов для малых фрагментов текста. В работе исследуются также статистические цифровые портреты писателей: это совместные эмпирические распределения вероятности того, что некоторая доля текста идентифицируется на заданном уровне доверия. Практическая важность этих статистик в том, что носители соответствующих распределений практически не пересекаются для своих и чужих эталонов, что позволяет распознать эталонное распределение буквосочетаний на высоком уровне доверия.

The paper describes a method for recognizing authors of literary texts by the proximity of fragments into which a separate text is divided to the standard of the author. The standard is the empirical frequency distribution of letter combinations, built on a training sample, which included expertly selected reliably known works of this author. A set of standards of different authors forms a library, within which the problem of identifying the author of an unknown text is solved. The proximity between texts is understood in the sense of the norm in L1 for the frequency vector of letter combinations, which is constructed for each fragment and for the text as a whole. The author of an unknown text is assigned the one whose standard is most often chosen as the closest for the set of fragments into which the text is divided. The length of the fragment is optimized based on the principle of the maximum difference in distances from fragments to standards in the problem of recognition of «friend–foe». The method was tested on the corpus of domestic and foreign (translated) authors. 1783 texts of 100 authors with a total volume of about 700 million characters were collected. In order to exclude the bias in the selection of authors, authors whose surnames began with the same letter were considered. In particular, for the letter L, the identification error was 12%. Along with a fairly high accuracy, this method has another important property: it allows you to estimate the probability that the standard of the author of the text in question is missing in the library. This probability can be estimated based on the results of the statistics of the nearest standards for small fragments of text. The paper also examines statistical digital portraits of writers: these are joint empirical distributions of the probability that a certain proportion of the text is identified at a given level of trust. The practical importance of these statistics is that the carriers of the corresponding distributions practically do not overlap for their own and other people’s standards, which makes it possible to recognize the reference distribution of letter combinations at a high level of confidence.

Рассматривается задача автоматизации коррекции документов в формате LaTeX. Каждый документ представляется в виде синтаксического дерева. С помощью модифицированного алгоритма Zhang-Shasha строится отображение вершин дерева изначального документа в вершины дерева отредактированного документа, соответствующее минимальному редактирующему расстоянию. Отображения вершины в вершину составляют обучающую выборку, по которой генерируются правила замены для автоматической коррекции. Для каждого правила собирается статистика его применимости к отредактированным документам. На ее основе производится оценка качества правил и их улучшение.

The problem is to automate the correction of LaTeX documents. Each document is represented as a parse tree. The modified Zhang-Shasha algorithm is used to construct a mapping of tree vertices of the original document to the tree vertices of the edited document, which corresponds to the minimum editing distance. Vertex to vertex maps form the training set, which is used to generate rules for automatic correction. The statistics of the applicability to the edited documents is collected for each rule. It is used for quality assessment and improvement of the rules.