Алгоритм автоматического перевода текстов с помощью дерева модели мира

Размещено на http://www.allbest.ru/

Алгоритм автоматического перевода текстов с помощью дерева модели мира

Курьян В.Е.

Kuryan V.E.

AUTOMATIC TEXT TRANSLATION ALGORITHM USING THE WORLD MODEL TREE

Annotation

The paper describes an approach to modeling human learning by constructing a graph of a world model using the example of teaching a system to translate from one natural language to another. Building a model of the world is made automatically based on the processing of an array of pairs of texts in the input and output languages. The approach is based on the representation of the situation described in the input text as a subtree of the general model of the world in the input language. From this subtree in the input language, select the subtree of the world model in the output language. The subtree in the output language is converted into plain text, which is the translation of the source text.

Keywords

World model tree, machine translation, text generation.

Введение

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

Другим важным примером важности решения проблемы автоматического перевода является задача рас шифровки генома. Молекулу ДНК можно рассматривать как текст, записанный четырьмя буквами. Этот текст содержит информацию о строении организма. Предсказание строения организма по известной ДНК можно рассматривать как задачу перевода с языка текста последовательности букв в молекуле ДНК на язык свойств биологического организма.

Целью настоящей работы является построение алгоритма, моделирующего процесс обучения человека на примере обучения переводу с одного языка на другой. В предыдущей работе [2] был описан пример построения графа модели мира на русском и английском языках и приведены получившиеся в результате графы. Эти графы приведены для удобства на рисунках 1 и 2. В этой работе мы покажем, как с помощью этих моделей можно переводить тексты с одного естественного языка на другой.

Перевод с помощью графа модели мира

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

Коля бегает в зоопарк. перевод текст графа язык

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

Активизация дерева на входном языке

В графе модели мира будем каждой вершине выставлять признак активизации, если она используется при выполнении перевода текущего предложения. На самом нижнем уровне (уровне слов) будем устанавливать этот признак в состояние активно, если слово входит во введенное предложение. У вершин типа P признак активности устанавливается в состояние активно, если ее ссылка D -типа указывает на уже активизированную вершину (то есть такую, у которой признак активизации находится в состоянии активно. У вершин K-типа признак активизации устанавливается в состоянии активно, если хотя бы одна из ссылок D-типа из этой вершины указывает на активизирован

ную вершину. У вершин S-типа признак активности будет устанавливаться в состояние активно только тогда, когда все ссылки D -типа из этой вершины указывают на активизированные вершины.

Вначале будут активизированы только вершины нижнего уровня, соответствующие введенному набору слов: «Коля», «Бегает», «В», «Зоопарк» (см. рис. 1). На следующем шаге признак активности установится у вершин с номерами 8, 31, 4, 23. Потом активизируются вершины с номерами 17, 30, 29, 26. Применяя вышеописанное правило активизации вершин входного графа модели мира, получим, что признак активности будет установлен в состояние активно и у вершин 15, 27, 28, 18, 16, 14.

На рисунке 3 в графе модели мира оставлены только активизированные вершины в графе модели мира на входном языке. На вершину S-типа 14 нет ссылок D -типа из других активизированных вершин, и ее нижнее поддерево содержит входное предложение. Такую вершину S-типа будем называть TOP- вершиной (вершиной самого высокого уровня для рассматриваемого предложения). Полученный граф соответствует введенному предложению. Этот граф содержит как информацию обо всех введенных словах, так и об их порядке во входном предложении. По этому графу на входном языке строим выходной граф.

Активизация дерева на выходном языке

Активизация выходного дерева выполняется в несколько этапов. На первом этапе в графе модели мира на выходном языке отмечаются все те вершины, на которые есть ссылки ^ типа из активизированных вершин во входном дереве. На втором этапе выделяем среди отобранных вершин на выходном языке те, на которые есть ссылки T-типа из TOP-вершин дерева на входном языке. На третьем этапе проверяем отобранные таким образом TOP- вершины в выходном дереве на возможность активизации ссылок D-типа, выходящих из этих вершин. Для вершин S-типа требуется, чтобы все ссылки D-типа, выходящие из этой вершины, указывали на отмеченные на первом этапе вершины. Если при такой проверке выяснится, что не все ссылки D-типа могут быть активизированы, то рассматриваемую вершину исключаем из дальнейшего рассмотрения, так как она не может входить в выходное дерево. Если все ссылки могут быть активизированы, то переходим к проверке возможности активизации ссылок D-типа из нижележащих вершин, на которые ссылалась рассмотренная вершина. Для вершин P-типа и K-типа достаточно, чтобы хотя бы одна ссылка D-типа указывала на отобранную на первом этапе вершину. Таким способом проверяем все вершины, отмеченные на первом этапе. Вершины, не удовлетворившие критериям проверки, исключаем из дальнейшего рассмотрения. В результате такой проверки из отмеченных на первом этапе активизации выходного дерева могут быть исключены некоторые вершины, поэтому с оставшимися вершинами проводим аналогичный цикл проверок, но только теперь учитываем оставшиеся после проверки вершины. Повторяем такой цикл проверок до тех пор, пока при прохождении такого цикла будет меняться число оставшихся вершин. Если по окончании этих циклов не останется ни одной вершины в выходном дереве, то перевод невозможен и алгоритм завершил свою работу. Если осталось хотя бы одна вершина, то проверяем, остались ли среди них те (TOP-вершины в выходном дереве), на которые ссылались TOP-вершины из входного дерева ссылками T-типа. Если таких вершин не осталось, то перевод невозможен и алгоритм завершил свою работу. Если TOP-вершины в выходном дереве остались, то проверяем следующее необходимое условие возможности перевода. Это условие можно сформулировать следующим образом: для каждой из вершин нижнего уровня входного дерева существует хотя бы одна из оставшихся после предыдущего отбора вершин нижнего уровня в выходном дереве проверяемой TOP-вершины выходного дерева, связанная ссылкой T- типа с рассматриваемой вершиной входного дерева. Если это условие выполнено, то перевод входного предложения существует и описывается найденным выходным деревом.

В результате выполнения описанной процедуры получим активизированное дерево на выходном языке, представленное на рисунке 4.

По этому дереву очевидным образом получается перевод входного предложения Nickrunstothezoo.

Такое предложение тоже не встречалось системе в процессе обучения.

Генерация осмысленных текстов с помощью дерева модели мира

Проиллюстрируем возможность генерации осмысленных предложений из набора слов на более сложном примере. Пусть граф модели мира, полученный в результате обучения системы, изображен на рисунках 5 и 6 (его части на входном и выходном языке). Ссылки T- типа связывают вершины с одинаковыми обозначениями (эти ссылки не приведены на рисунке, чтобы не загромождать изображение). Пусть нам дан набор слов на выходном языке: Pit, zoo, nearest, the, to,goes. Требуется построить из этих слов осмысленное предложение.

Рисунок 4 - Активированная часть графа модели мира на выходном языке

Рисунок 5 - Граф модели мира на входном языке

Рисунок 6 - Граф модели мира на выходном языке

С точки зрения грамматики можно построить несколько правильных вариантов:

Pit goes to the nearest zoo.

Nearest Pit goes to the zoo.

Zoo goes to the nearest Pit.

Nearest zoo goest to the Pit.

Из правильных с точки зрения грамматики осмысленным является только первый вариант.

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

этой процедуры получим результат, показанный на рисунке 7 (там оставлены только активизированные вершины графа модели мира).

Получившемуся активизированному дереву графа модели мира как раз и соответствует единственное в данном случае осмысленное предложение: Pitgoestothenearestzoo.

Обратим внимание, что граф описывает разные по своей сложности и структуре ситуации. Примеру входного предложения «Коля бегает в зоопарк» соответствует граф, описанный ранее в разделе «Активизация дерева на входном языке». Активизированные вершины графа, соответствующего входному предложению «Петя ходит в ближайший зоопарк и магазин», изображены на рисунке 8.

Рисунок 7 - Активированная часть графа на входном языке

Рисунок 8 - Активированная часть графа на выходном языке

Возможно возникновение ситуаций, когда заданного набора слов недостаточно для построения осмысленного предложения (пропущены некоторые детали описания реальной ситуации). Например, пусть задано множество слов: Петя, ходит, ближайший, зоопарк, и, магазин (пропущено предлог «в»). В этом случае из изображенных на рисунке 8 вершин останутся неактивизиро- ванными вершины s1, р2, р3, р4, кб, р9. Это означает, что из заданного множества слов невозможно составить осмысленное предложение, которое включало бы все заданные входные слова. Но входное множество можно дополнить словом «в». После такого дополнения получается законченное осмысленное предложение, включающее все заданные входные слова и дополнительное слово (пропущенную деталь описания реальной ситуации). Таким образом, имеющийся граф модели мира позволяет дополнять пропущенные детали таким образом, чтобы получалось осмысленное описание реальной ситуации.

Благодаря тому, что построение графа модели мира происходит на обработке реальных осмысленных ситуаций, система будет выдавать осмысленные результаты. В приведенных примерах система работала с отдельными предложениями и не учитывала контекст. Если при обучении системы на вход подавать не отдельные предложения, а более длинные фрагменты текстов, то в результате использования изложенных выше подходов система построит граф модели мира, учитывающий контекст.

Оценка порядка размера обучающей выборки

В рассмотренной в предыдущей статье [2] ситуации с обучением приготовления чая один язык (входной) - это язык поручений ребенку (приготовить чай или приготовить обед), второй язык (выходной) - это действия ребёнка. Переводом поручения в этой модели является последовательность действий, приводящая к выполнению поручения. Число всех возможных вариантов действий растет очень быстро с увеличением сложности модели (как произведение числа ссылок Б-типа во всех вершинах К-типа), при этом число необходимых примеров для обучения растет пропорционально сумме числа ссылок D-типа во всех вершинах К-типа. Для случая обучения перевода с одного естественного языка на другой это означает, что размер обучающей выборки должен быть пропорционален числу всех словоформ языка. Естественный язык содержит обычно порядка 100000 - 1000 о0о словоформ, будем считать, что типичное предложение содержит порядка 100 букв, поэтому размер обучающей выборки получается порядка 10-100 Мбайт и она содержит порядка 1 млн предложений. Если предположить, что время обработки одного предложения составляет 1 сек, то для обучения системы потребуется порядка 1 млн секунд. Что составляет по порядку величины 10 суток. Это грубая оценка порядка величины обучающей выборки примерно соответствует размеру переработанной информации при обучении человека иностранному языку за время обучения 2-3 года. При этом процесс обучения может быть значительно ускорен при использовании специальной последовательности обучающих примеров (как при обучении человека от простого к сложному).

При обучении системы переводу с одного язык на другой требуется произвести перевод обучающего текста на новый язык. Перевод текста порядка 100 Мбайт потребует порядка 10 человеко-лет работы переводчика, что является довольно небольшой величиной по сравнению с затратами на обучение с использованием других подходов.

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

Заключение

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

Библиографический список

1. Zijian Feng et al. The Epidemiological Characteristics of an Outbreak of 2019 Novel Coronavirus Diseases (COVID-19) // China CDC Weekly. -

2020. - Vol. 2. - No. 8. - Р. 113

2. Курьян В.Е. Моделирование процесса обучения человека с помощью построения графа модели мира // Учет и статистика. - 2019. - No. 4 (56).

Bibliographic list

1. Zijian Feng et al. The Epidemiological Characteristics of an Outbreak of 2019 Novel Coronavirus Diseases (COVID-19) // China CDC Weekly. - 2020. - Vol. 2. - No. 8. - P. 113.

2. Kuryan V.E. Modeling the process of human learning by constructing a graph model of the world // Accounting and Statistics. - 2019. - No. 4 (56).

Размещено на Allbest.ru