Об автоматной аппроксимации реальных языков

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

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

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

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

Предметом исследования является формализованная модель естественного языка и её основные свойства.

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

Работа состоит из пяти глав, введения и списка литературы.

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

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

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

В этой главе рассматриваются:

• дискретные модели: регулярные языкиконтекстно-свободные языкиt системы, основанные на использовании лингвистических экспертных систем и систем понимания и учёта смысла;

• вероятностные модели: п-граммысистемы, основанные на деревьях решенийвероятностные обобщения контекстно-свободных грамматик.

Здесь показаны преимущества и недостатки каждого из этих подходов, а также приведена общепринятая на сегодняшний день оценка качества модели, так называемый коэффициент неопределённости (perplexity coefficient).

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

Во второй главе рассмотрен подход, основанный на использовании дискретных моделей, а именно — регулярных и контекстно-свободных языков.

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

Задача формулируется следующим образом.

Пусть дано обобщённое слово, а и некоторая грамматика Г. Требуется найти в обобщённом слове путь, ведущий из начальной вершины в конечную и обладающий двумя свойствами:

1. слово, полученной конкатенацией букв, записанных вдоль этого пути должно быть допустимым словом в грамматике Г;

2. сумма весов, стоящих на рёбрах пути должна быть минимальна.

В работе показано, что в случае, если грамматика Г задаётся конечным автоматом, то данная задача может быть решена за время 0(п2), где п — количество вершин в графе обобщённого слова. В том случае, если грамматика Г является контекстно-свободной, то данная задача может быть решена за время 0(п3), где п — количество вершин в графе обобщённого слова.

Описанные во второй главе работы алгоритмы также позволяют несколько обобщить задачу, а именно — перечислить все пути, удовлетворяющие первому условию, либо найти такой путь, который может быть представлен в виде конкатенации произвольного числа слов, допустимых в грамматике Г.

Кроме того, в данной главе приведены также два примера применения построенной техники: в задаче коррекции результатов оптического распознавания символов и в задаче поиска минимального исправления ошибочно написанного слова (так называемая задача зреПсЬескег’а).

В третьей главе рассматриваются вероятностью модели для систем распознавания русской речи.

В настоящее время в задачах распознавания слитной речи чаще всего используются вероятностные модели, построенные на принципе независимости от «далёкой» истории, так называемые п-граммные модели.

Р (афг1щ2. (ц.г) ъ Р (аф{.п+1а{.п+7. а£.1).

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

Каждая из этих моделей была построена и обучена на материале российской периодики. При этом было показано, что полученные характеристики языковых моделей примерно соответствуют среднестатистическим характеристикам моделей для английского языка (коэффициент неопределённости в модели, основанной на леммах, составил около 230- для моделей па английском языке этот коэффициент обычно оказывается в районе 100). Коэффициент неопределённости в категорной модели (построенной исключительно па морфологической информации) оказался около 20.

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

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

В четвёртой главе вводится обобщение понятия п-граммной модели на бесконечные формальные языки. А именно, вводится частота встречаемости слова т на я-ом месте, а затем рассматривается предельная частота встречаемости слова и) как предел при 5 —оо. Аналогичным образом вводится понятие п-граммы. Если в языке? существуют все п-граммы для некоторого фиксированного числа п, то такой язык в работе называется марковским языком порядка п. В том случае, если в языке существуют все п-граммы для всех натуральных чисел п, то этот язык называется марковским языком.

Показано, что даже в классе регулярных языков существуют языки, не являющиеся марковскими. Тем не менее, число марковских регулярных языков достаточно велико. А именно, как доказано в Теореме 4.4, отношение количества марковских языков, задаваемых автоматами с N состояниями, к общему количеству регулярных языков, задаваемых автоматами с N состояниями, для достаточно больших N не меньше, чем (1 —.

Оказывается, что классы марковских языков строго вкладываются друг в друга. А именно, как доказано в Теореме 4.2, из того, что язык является марковским порядка к, с необходимостью следует, что он является марковским для всех порядков меньше к. Но при этом для любого числа п можно указать такой регулярный язык, который являлся бы марковским языком порядка п, но не являлся бы марковским языком порядка п + 1.

С другой стороны, если язык? фиксирован, то для ситуация становится обратной. А именно, справедлива Теорема 4.3: если язык является марковским языком порядка 2^', где Ц — множество состояний задающего данный язык автомата, то язык? является марковским языком любого порядка (и, соответственно, является просто марковским языком).

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

Более точно, для этого необходимо выделить так называемый активный граф автомата 21, то есть подмножество рёбер диаграммы переходов, которые входят хотя бы в один путь из начального состояния в одно из финальных. Активной матрицей автомата 21 называется матрица инцедентности его активного графа.

Теорема 4.5 утверждает, что в том случае, если активная матрица автомата 21 имеет единственное максимальное по модулю собственное значение, то задаваемый этим автоматом язык является марковским.

К сожалению, класс марковских языков не замкнут относительно основных теоретико-языковых операций: объединения, пересечения и дополнения, поэтому в пятой главе рассматривается новый класс языков — каскадно-дефинитные языки.

Понятие дефинитных языков (то есть таких языков, функция переходов которых «забывает» далёкую предысторию) является прямым переносом идеологии марковских языков непосредственно на теорию автоматов. Однако это свойство оказывается слишком жестким: любой дефинитный язык является марковским языком и все его п-граммы (для любого фиксированного п) равны между собой. Поэтому сами по себе дефинитные языки не очень интересны в свете рассмотрения марковских языков. Тем не менее, из них можно получить новый класс языков, с одной стороны небольшой (его доля среди всех языков, задаваемых автоматами с N состояниями стремится к нулю с ростом А/"), а с другой стороны — в некотором смысле «всюду плотный» в множестве марковских языков. В работе вводится операция склейки двух автоматов по паре состояний, позволяющая получить два интересных класса регулярных языков из простейших «кирпичиков» — дефинитных языков, а также циклов и деревянных автоматов.

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

Более точно, как утверждает Теорема 5.1, для произвольной биграммной матрицы с рациональными коэффициентами существует автомат 21, имеющий в точности такое же множество биграмм, который может быть получен путём применения операции склейки к простейшим автоматам — деревянным автоматам и циклам.

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

Научная новизна работы заключается в следующем:

• предложены новые алгоритмы и подходы для работы с дискретными моделями естественных языков, позволяющие интегрировать их в небольшие системы распознавания в качестве дополнительных блоков, контролирующих и корректирующих результаты распознавания;

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

• основные положения п-граммной модели перенесены на бесконечные регулярные языки, выделены новые нетривиальные классы регулярных, языков (в работе они названы марковскими языками), изучены их свойства.

• найден класс «просто устроенных» регулярных языков, позволяющий промоделировать произвольный марковский язык порядка 2 с любой наперёд заданной точностью.

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

Я выражаю глубокую и искреннюю благодарность своему научному руководителю — доктору физико-математических наук, профессору Дмитрию Николаевичу Бабину за постановку задач, постоянную поддержку и внимание к работе.

Я благодарю научного сотрудника лаборатории Проблем теоретической кибернетики, кандидата физико-математических наук Ивана Леонидовича Мазуренко за ценные обсуждения.

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

1. Хомский Н. Синтаксические структуры. // Новое в лингвистике. Вып. И. М., 1962.

2. Вудс В. А. Сетевые грамматики для анализа естественных языков // Кибернетический сборник. Новая серия. Вып. 13. -М.: Мир, 1978. С. 120 158.

3. Бухараев Р. Г. Основы теории вероятностных автоматовМ.: Наука, 1985.

4. Daniel Sleator and Davy Temperley. 1991. Parsing English with a Link Grammar. Carnegie Mellon University Computer Science technical report CMU-CS-91−196, October 1991.

5. Мельчук И. А. Опыт теории лингвистических моделей «Смысл •(-> Текст». -М.: Наука, 1974.

6. Yu. Kosarev, I. Machovikova, A. Machovikov, R. Piotrowski, S. Tseitlin. Language Perception Modeling Based on Analysis of Children’s Speech // Speech and computer, St .-Petersburg, Russia, 26−28 October 1998.

7. EAGLES. «HANDBOOK of Standards and Resources for Spoken Language Systems», Mouton de Gruyter, 1997.

8. Ахо А. и Ульман Дж. Теория синтаксического анализа, перевода и компиляции. -М.: Мир, 1978.

9. Кудрявцев В. В., Алёшин С. В., Подколзин А. С.

Введение

в теорию автоматов. -М.: Наука, 1985.

10. R. Rosenfeld. A maximum entropy approach to adaptive statistical language modeling. Computer Speech and Language, 10. pp. 187−228, 1996.

11. R. Rosenfeld, Adaptive statistical language modeling: A maximum entropy approach, Ph.D. dissertation, Comput. Sci. Dept., Carnegie-Mellon Univ., Pittsburgh, PA, Apr. 1994.

12. I. J. Good. The population frequencies of species and the estimation of population parameters. Biometrika, vol. 40, no.¾, pp. 237−264, 1953.

13. I. H. Witten and T. C. Bell. The zero-frequency problem: Estimating the probabilities of novel events in adaptive text compression. IEEE Transactions on Information Theory, vol. 37, no. 4, pp. 1085−1094, July 1991.

14. S. M. Katz. Estimation of probabilities from sparse data for the language model component of a speech recognizer. IEEE Transactions on Acoustics, Speech and Signal Processing, vol. 35, no. 3, pp. 400−401, March 1987.

15. H. Ney, U. Essen, and R. Kneser. On structuring probabilistic dependences in stochastic language modeling. Computer Speech and Language, vol. 8. pp. 1−38, 1994.

16. R. Kneser and H. Ney. Improved backing-off for m-gram language modeling. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, volume I, Detroit, Michigan, May 1995, pp. 181−184.

17. F. Jelinek and R. L. Mercer. Interpolated estimation of Markov source parameters from sparse data. In Proceedings of the Workshop on Pattern Recognition in Practice, pages 381−397, Amsterdam, The Netherlands: North-Holland, May 1980.

18. D. Ron, Y. Singer, and N. Tishby. The power of amnesia. In J. Cowan, G. Tesauro, and J. Alspector, editors, Advances in Neural Information Processing Systems, vol. 6, pp. 176−183. Morgam Kaufmann, San Mateo, CA, 1994.

19. I. Guyon and F. Pereira. Design of a linguistic postprocessor using variable memory length Markov models. In Proceedings of the 3rd ICDAR, pp. 454 457, 1995.

20. R. Kneser. Statistical language modeling using a variable context length. In Proceedings of ICSLP, vol. 1, pp. 494−497, Philadelphia, October 1996.

21. T. Niesler and P. Woodland. Variable-length category n-gram language models. Computer Speech and Language, vol. 21, pp. 1−26, 1999.

22. M.-H. Siu and M. Ostendorf. Variable n-gram and extensions for conversational speech language modeling. IEEE Transactions on Speech and Audio Processing, vol. 8, no. 1, pp. 63−75, Jan. 2000.

23. P. J. Price. Evaluation of spoken language systems: the atis domain. In Proceedings of the DARPA Speech and Natural Language Workshop, June 1990.

24. W. H. Ward. The emu air travel information service: understanding spontaneous speech. In Proceedings of the DARPA Speech and Natural Language Workshop, pp. 127−129, June 1990.

25. P. F. Brown, V. J. Delia Pietra, P.V. deSouza, J.C. Lai, and R.L. Mercer. Classbased n-gram models of natural language. Computational Linguistics, vol. 18, no. 4, pp. 467−479, December 1992.

26. R. Kneser and H. Ney. Improved clustering techniques for class-based statistical language modeling. In Proceedings of the European Conference on Speech Communication and Technology (Eurospeech), 1993.

27. L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, California, 1984.

28. L. R. Bahl, P. F. Brown, P. V. de Souza, and R. L. Mercer. A tree-based statistical language model for natural language speech recognition. IEEE Transactions on Acoustics, Speech and Signal Processing, vol. 37, pp. 10 011 008, July 1989.

29. J. K. Baker. Trainable grammars for speech recognition. In Proceedings of the Spring Conference of the Acoustical Society of America, pp. 547−550, Boston, MA, June 1979.

30. J. D. Lafferty, D. Sleator, and D. Temperley. Grammatical trigrams: a probabilistic model of link grammar. In Proceedings of the AAAI Fall Symposium on Probabilistic Approaches to Natural language, Cambridge, MA, October 1992.

31. L. R. Bahl, J. K. Baker, F. Jelinek, and R.L. Mercer. Perplexity a measure of the difficulty of speech recognition tasks. Program of the 94th Meeting of the Acoustical Society of America J. Acoust. Soc. Am., vol. 62 p. S63, 1977. Suppl. no. 1.

32. Соколова E. H. Алгоритмы лемматизации для русского языка. // Рабочий проект многоязычного автоматического словаря на 60 тыс. словарных статей. Т.1. Лингвистическое обеспечение. -М. 1984. Стр. 45−62.

33. Кулагина О. С. Об автоматическом синтаксическом анализе русских текстов. Препринт / ИПМ АН СССР. -М. 1987. № 205.

34. The CMU Statistical Language Modeling (SLM) Toolkit chttp://www.speech.cs.emu.edu/SLMinfo.html>

35. D. Kanevsky, M. Monkowsky, J. Sedivy. Large Vocabulary Speaker-Independent Continuous Speech Recognition in Russian Language. Proc. SPECOM'96, St.-Petersburg, October 28−31, 1996.

36. S. Manhung и др. «Integrating a context-dependent phrase grammar in the variable n-gram framework». In Proceeding of ICASSP. 2000. Работы автора по теме диссертации.

37. Холоденко A.B. Лексический анализатор в распознавании последовательных образов. // Информационные технологии в инновационных проектах: Материалы докладов. Международная конференция, 20−22 апреля 1999 г. -Ижевск: ИжГТУ, 1999, с. 43−44.

38. Холоденко A.B. Использование лексических и синтаксических анализаторов в задачах распознавания для естественных языков. // Интеллектуальные системы. Т.4, вып. 1−2, 1999, с. 185−193.

39. Холоденко A.B. Исправление ошибок в формальных языках. // Нейрокомпьютеры и их применение: Сборник докладов. IV Всероссийская конференция, Москва. 16−18 февраля 2000 г. -М.: Издательское предприятие редакции журнала «Радиотехника», 2000, с. 627−630.

40. Kholodenko А. То the creating of the language models for Russian. // V International Congress on mathematical modeling. September 30 October 6, 2002, Dubna, Moscow Region. Book of abstracts, V. 2, -M.:" Janus-K", 2002, p. 97.

41. Холоденко A.B. О построении статистических языковых моделей для систем распознавания русской речи. // Интеллектуальные системы. Т.6, вып. 1−4, 2002, с.381−394.

42. Холоденко A.B. О языковых моделях для систем распознавания русской речи. // Интеллектуальные системы в производстве: Периодический научно-практический журнал 2003. — № 1 -Ижевск: Изд-во ИжГТУ, 2003. с. 146−155.

43. Холоденко A.B. О марковских регулярных языках. // Материалы IX Международного семинара «Дискретная математика и её приложения», 18−23 июня 2007 годаМ., Изд-во механико-математического факультета МГУ, 2007. с.358−361.