«Ле Чунг Хьеу МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ МЕТОДОВ РАСПОЗНАВАНИЯ ОБРАЗОВ ПРИ ОБРАБОТКЕ ТЕКСТОВ НА ВЬЕТНАМСКОМ ЯЗЫКЕ 05.13.11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей ...»

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ

На правах рукописи

Ле Чунг Хьеу

МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ

МЕТОДОВ РАСПОЗНАВАНИЯ ОБРАЗОВ

ПРИ ОБРАБОТКЕ ТЕКСТОВ

НА ВЬЕТНАМСКОМ ЯЗЫКЕ

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

Научный руководитель д. ф.-м. н., проф. О.Н.Граничин Санкт-Петербург 2011 Оглавление Введение............................... 4 1 Особенности обработки вьетнамских текстов 1.1 Обработка естественного языка................ 1.2 Особенности вьетнамских текстов.............. 1.2.1 Вьетнамский язык................... 1.2.2 Проблемы обработки вьетнамских текстов..... 1.3 Программные продукты для обработки естественного языка 2 Методы распознавания образов при графематическом анализе 2.1 Извлечение графематических дескрипторов.......................... 2.1.1 Графематические дескрипторы............ 2.1.2 Модель извлечения графематических дескрипторов............ 2.1.3 Графематическая модель вьетнамского языка... 2.2 Распознавание слов и сегментация предложений.......................... 2.2.1 Вероятностная модель................. 2.2.2 Метод обучения без учителя............. 2.2.3 Метод распознавания фраз.............. 3 Оптимизация параметров скрытых марковских моделей при распознавании морфологической структуры 3.1 Морфологическая разметка корпусов текстов........................ 3.1.1 Основные понятия и формальная постановка задачи 3.2 Автоматический морфологический анализ.............................. 3.2.1 Постановка задачи................... 3.2.2 Процесс обучения.................... 4 Система автоматической обработки вьетнамских текстов 4.1 Описание функционирования программ........... 4.2 Состав программного обеспечения.............. 4.3 Результаты экспериментов.................. Заключение.............................. Литература.............................. Введение Актуальность темы. В последние десятилетия методы распознавания образов находят приложения в самых разнообразных областях. Многие из них активно используются при автоматической обработке текстов (AOT). АОТ достигла значительных успехов в лексико-грамматическом анализе, выявлении темы, в поиске информации и т. п. Большинство работ по АОТ были проведены для языков индоевропейской группы [58, 59, 75, 82, 83, 84, 94]. Их результаты не могут быть непосредственно применены к вьетнамскому языку, который, являясь разговорным языком (как китайский, японский и др.), оперирует слогами, а не словами.

Границы слова определяются контекстом. Для построения новых лексических единиц или слов используются сочетания различных слогов.

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

Проблемы распознавания образов слов и словосочетаний во вьетнамских текстах исследовались в современных работах Д. Дьена [68], X.H. Као [62, 63], Х.П. Ле [80], К.Т. Нгуена [89], Х. Нгуена [90], Л.А. Ха [76] и др. Основные задачи

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

Для вьетнамского языка серьезной проблемой для автоматической обработки является отсутствие достаточно полных словарей вьетнамских слов и вьетнамскоязычных корпусов текстов. На протяжении долгого времени вьетнамские, а также иностранные специалисты, решали эту проблему вручную. Однако построение списка слов вручную требует колоссальных усилий и все же не обеспечивает полноты словаря. Одна из причин этого широкое использование вьетнамского языка в различных сферах со специальными словами, которые редко используется. Другая в различных регионах используются разные диалекты и словосочетания. Кроме этого, условия жизни быстро меняются. С развитием новых технологий и увеличением объемов информации постоянно расширяется лексикон вьетнамского языка. Например, новые слова: Интернет, айфон и т. п. надо включать в словари как новые понятия. Все эти причины делают процесс построения списка вьетнамских слов вручную трудновыполнимым. По последним данным самый полный вьетнамский словарь содержит только 75 000 слов, но в реальности по оценке специалистов количество вьетнамских слов насчитывает уже более 200 000. Это означает, что более половины вьетнамских слов нигде не сохранены.

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

Цель достигается в диссертации через решение следующих задач:

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

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

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

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

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

Основные результаты. В работе получены следующие основные научные результаты:

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

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

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

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

Научная новизна. Все основные научные результаты диссертации являются новыми.

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

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

Апробация работы. Материалы диссертации докладывались на семинарах кафедры системного программирования математико-механического факультета СПбГУ и на международной конференции: The 2nd Asian Conference on Intelligent Information and Database Systems (Hue, Vietname, March 24 26, 2010).

Результаты диссертации были частично использованы в работе по НИР из средств бюджета “Математическая модель распознавания и процессинга текстов на восточных языках на основе сегментации релевантных составляющих”, выполняемой в СПбГУ.

Публикации. Основные результаты диссертации опубликованы в шести работах. Из них две публикации [24, 79] в изданиях из перечня ВАК. Работы [23, 24, 79] написаны в соавторстве. В работе [24] Граничину О.Н.

принадлежит общая постановка задачи, а Ле Ч.Х. реализации и обоснования описываемых методов, создание демонстрационных примеров и программных средств. В работах [23, 79] Ле Ч.Х. предложил новые статистические методы распознавания образов и теоретико-вероятностную модель для автоматической сегментации предложений на вьетнамском языке, а его соавторы участвовали в подготовке наборов текстовых данных для апробации новых методов и выполнили часть работы по созданию и доработке нового словаря вьетнамских слов.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 105 источников. Текст занимает 102 страниц, содержит 10 рисунков и 11 таблиц.

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

Одной из серьезных проблем организации человеко-машинного взаимодействия является лингвистический анализ предложения на естественном языке с последующим переводом его на машинный язык вычислительной системы [65, 56, 1, 6]. Общие подходы к решению этой задачи рассматриваются в п. 1.1. Обычно текст подвергается последовательной обработке графематическим, морфологическим, синтаксическим и семантическим анализаторами [15].

В п. 1.2 описываются лингвистические характеристики вьетнамского языка [74]: фонетика, слог, морфология, синтаксис, лексические категории и предложения. Особенностью вьетнамского языка является то, что он разговорный, и в нем самым важным элементом является слог, а не слово. Автоматический анализ текстов на вьетнамском языке затруднен нерешенностью проблемы делимитации слова. Границы слов могут меняться в зависимости от контекста, что приводит к трудностям их определения. Эти трудности восприятия иллюстрируются следующим примером. В предложении “h c sinh h c sinh h c”, которое по-русски означает “школьник учит биологию”, все комбинации “h c sinh”, “sinh h c”, “sinh”, “h c” являются вьетнамскими словами:

• “h c sinh” школьник, • “sinh h c” биология, • “sinh” родиться.

Для разделения предложения на слова важно содержание предложения. В рассматриваемом примере, учитывая его основную мысль, правильная расстановка границ такова: “h c sinh | h c | sinh h c”.

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

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

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

Графематический анализ представляет собой начальный этап обработки текста, представленного в виде цепочки ASCII символов, подготавливающий информацию, необходимую для дальнейшей обработки морфологическим и синтаксическим процессорами [35, 36]. При графематическом анализе вьетнамского языка решаются две основные задачи: первая выделение различных нестандартных элементов текста и присваивание им соответствующих графематических дескрипторов (например, знаков пунктуации, цифровых комплексов, собственных имен, сокращений и т. д.); вторая распознавание слов и словосочетаний, сегментация предложений на слова.

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

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

В п. 2.2 анализируются задачи распознавания слов и словосочетаний и сегментации предложений на слова, словосочетания и фразы [72, 93, 98, 99]. В задачи рассматриваются две проблемы:

• распознавание слов с вероятностной точки зрения;

• построение с помощью процесса обучения без учителя по большому набору предложений адекватной вероятностной модели [8, 13].

В третьей главе “Оптимизация параметров скрытых марковских моделей при распознавании морфологической структуры” предлагается и обосновывается новый метод распознавания для морфологического анализа. Цель морфологического анализа заключается в определении морфологических признаков слов для использования их на последующих этапах обработки текста [60, 67, 91, 92, 97].

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

1. морфологическая разметка корпуса вьетнамских текстов;

2. морфологический анализ вьетнамского предложения снятие морфологической омонимии.

В четвертой главе “Система автоматической обработки вьетнамских текстов” в п. 4.1 описана схема функционирования разработанной автором программной системы, которая представляет собой многоуровневый анализатор: графематический, сегментирующий и морфологический.

В п. 4.2 описано программное средство, которое обеспечивает загрузку и редактирование анализируемых текстов; анализ текста посредством автоматической системы, составленной из разработанных независимо компонентов: графематического, сегментирующего и морфологического анализаторов.

Система была реализована с использованием приложений на языке C# в среде операционной системы Microsoft Windows использовались ряд дополнений. Программируемый конвейер приложение, реализованное на основе технологии Microsoft Framework 3.5, предоставляет функциональность работы со стендом со стороны исследователя разработчика алгоритмов анализа реализуя такие возможности, как подключение модулей анализатора к программе, а также связывание их в единый конвейер.

В п. 4.3 анализируются результаты анализа текстов каждым из компонентов. Данные для экспериментов были взяты из 250 034 вьетнамских Интернет-документов с веб-сайта “http://www.tuoitre.com.vn/”. Начальные данные содержали 18 676 877 фраз и 131 318 974 слогов.

В заключении диссертации подведены итоги проведенного и завершенного в рамках поставленных задач исследования.

Глава Особенности обработки вьетнамских текстов 1.1 Обработка естественного языка Обеспечение взаимодействия с ЭВМ на естественном языке является важнейшей задачей исследований по искусственному интеллекту. Прогресс информационных технологий в не малой степени зависит от решения проблем обработки текстов естественного языка и их понимания [65].

Естественный язык сложная, многоплановая система, с множеством правил, внутренних связей, имеющая отношение ко всем аспектам деятельности человека. Он служит человеку для выражения собственных мыслей и для понимания мыслей других людей. Попытки формализовать интеллектуальную деятельность человека привели к постановке фундаментальной лингвистической задачи, состоящей в моделировании его языкового поведения, т. е. в построении функциональной модели естественного языка. Если обозначить множество текстов через {T }, а множество выражаемых ими смыслов через {C}, то модель естественного языка можно определить как транслятор, устанавливающий соответствие между этими двумя множествами: {T } {C} [9, 14, 29].

Цель анализа предложения на естественном языке перевод его на машинный язык вычислительной системы. При этом анализатор осуществляет следующие функции [14, 27, 28]:

• распознавание правильно построенных предложений естественного • декомпозиция (“разбивка”) предложения на составляющие (фрагменты) и построение соответствующей синтаксической структуры предложения;

• семантическая интерпретация фрагментов предложения естественного языка во фрагменты М-языка;

• композиция (“сборка”) фрагментов М-языка в структуру, описывающую ситуацию проблемной среды.

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

Лингвистический анализатор представляет собой преобразователь [5, 14, 35], состоящий из четырех уровней пофразного представления текста графематического, морфологического, синтаксического и семантического (см. рис. 1.1). На каждом из уровней предложение имеет формальный образ, именуемый в дальнейшем его соответствующей структурой [14].

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

Морфологическая структурой последовательность входящих в анализируемое предложение слов с указанием части речи и морфологических характеристик.

Синтаксическая структура дерево зависимостей, в узлах которого стоят слова естественного языка с указанием части речи и грамматических характеристик, а дуги соответствуют специфичным отношениям синтаксического подчинения [34, 47, 49].

Под семантической структурой понимается дерево зависимостей, в узлах которого стоят либо предметные имена, либо слова универсального семантического языка, а дуги соответствуют универсальным отношениям семантического подчинения, таким, как аргументное, атрибутивное, конъюнкция, дизъюнкция, равенство, неравенство, больше, меньше, принадлежит и т. п [48].

Реализация лингвистического анализатора требует разработки формальных языков для записи образов предложений на графематическом, морфологическом, синтаксическом, семантическом уровнях представления; формального определения структуры предложения для каждого из этих уровней, массивов правил для преобразования структур смежных уровней друг в друга; графематического, морфологического, синтаксического и семантического словарей, с включением в них всей информации о каждой лексеме, необходимой для осуществления соответствующего преобразования [14, 27, 28, 33, 34].

Важные прикладные аспекты области обработки естественного языка (Natural Language Processing, NLP) включают речевое понимание и речевую генерацию [51], интерфейсы естественного языка, управление беседой, понимание текста [27, 28, 96, 100] и текстовую генерацию, интерактивный машинный перевод [26] и умные помощники письма. Для речевой обработки естественных языков (распознавание, понимание, и генерация) широко используются следующие программные продукты: Apple’s Plain Talk, BBN’s Hark, Decipher, DECtalk, IBM VoiceType, Naturally Speaking, Phonetic Engine. Цель интерфейсов естественного языка состоит в сокращении разрыва между лингвистическим входом пользователя и лингвистической основной компьютерной системы. Примеры реализованных интерфейсов естественного языка включают Battelle’s Natural Language Query, BBN’s Parlance, EasyTalk, English Query Language, Intelligent Query, Natural Language, Symantec’s Q+A Intelligent Assistant [82, 83].

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

Символический подход [30, 61] базируется на методах обучения на основе объяснений, опирающихся на правила обучения (Rule-based learning), индуктивном логическом программировании, деревьях разрешений, концептуальной кластеризации и алгоритмах типа k-means.

При вероятностных подходах [8, 53, 55, 57, 64, 70, 71, 73, 81] используются различные математические методы и корпуса текстов, позволяющие разработать обобщенные модели языковых явлений, основываясь на реальных проявлениях этих явлений в корпусе текстов не используя дополнительных значительных знаний о языке. В отличие от символических подходов вероятностные опираются на наблюдаемые данные в качестве основного источника информации.

В рамках вероятностного подхода выделяются несколько направлений, среди которых особого внимания заслуживают модели, максимизирующие энтропию (см. гл. 2) [56] и скрытые марковские модели (СММ) (см. гл. 3) [104]. СММ является конечным автоматом, который имеет множество состояний с определенными вероятностями переходов между ними. Каждое состояние производит один из наблюдаемых результатов с определенной вероятностью. Хотя результаты являются видимыми, но состояние модели не наблюдается непосредственно (скрыто от внешнего наблюдения).

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

Подход установление связей основан на моделях массивных связанных наборов простых и нелинейных компонентов. Эти компоненты работают параллельно. Приобретенное в результате обработки знание сохраняется в образце весов взаимосвязи компонентов.

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

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

1.2 Особенности вьетнамских текстов 1.2.1 Вьетнамский язык Во вьетнамском письме за основу взята латиница[10, 12, 62, 63]. Буква является мельчайшей единицей слова. Вьетнамский алфавит состоит из 29 букв:

22 буквы английского алфавита без букв f, j, w и z, которые все же используются при написании иностранных названий и имен;

7 модифицированных букв с особыми диакритическими знаками:

Буквенные сочетания: ch, gh, gi, kh, ng, ngh, nh, ph, th, tr считаются отдельными буквами с их собственными разделами в словаре.

Вьетнамские гласные: a,,, e,, i, o,,,, y.

Вьетнамские согласные: b, c, d,, g, gh, gi, h, k, kh, l, m, n, ng, ngh, nh, ph, q, r, s, t, th, tr, v, x.

Вьетнамский язык является тональным языком. В орфографии, тон обозначается диакритическими знаками, записанными выше или ниже гласной, например,,,,, [31].

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

Вьетнамский язык является изолирующим слоговым [39, 46]. Слог в языках такого типа является основной фонетической единицей. Его строение подчиняется строгим закономерностям: в начале слога следует согласный звук, затем сонант, промежуточный и основной гласные и конечный согласный, причем все элементы, кроме основного гласного, необязательные [63, 69].

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

Каждый слог во вьетнамском языке произносится c определенным тоном. Примеры разных слогов: “thanh”, “thnh”, “thnh”.

Вьетнамские слова могут состоять из одного или более слогов. Около 80% вьетнамских слов состоит из двух слогов (“h c sinh”, “qu n o”, “my tnh”). Некоторые слова имеют три или четыре слога (“xe g n my”, “trng i h c”, “my tnh xch tay”). Кроме того, вьетнамское слово может состоять из одной или нескольких морферм. Полиморфные слова либо сложные слова, либо слова с аффиксами или редупликацией. Например:

Вьетнамские слова Фонологическая форма Морфологическая форма v i v i vng vng мнолосложный полиморфный (редупликация) Вьетнамский язык характеризуется отсутствием словоизменения и наличием аналитических форм. Слова во вьетнамском языке не изменяются по падежам, а для выражения синтаксических отношений используются служебные слова и порядок следования слов в составе словосочетания и предложения.

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

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

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

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

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

Морфологические признаки категории слов языка, имеющие 1. одно и то же обобщенное лексическое значение;

2. одно и то же обобщенное грамматическое значение;

3. одни и те же синтаксические функции.

В морфологической системе вьетнамского языка выделяется девять основных морфологических признаков:

1. [NN] Существительные указывают на отдельные предметы, лица, имена людей, мест или организаций. Например, “my tnh”, 2. [JJ] Прилагательные обозначающие качественные признаки предмета. Например, “ p”, “xinh x n”, “d thng”, “x u x ”;

3. [PP] Местоимения лишенные собственного лексического значения и употребляемые вместо имени существительного, прилагательного, имени числительного или наречия, не называя предмет или его характеристику, а лишь указывая на них. Некоторые основные местоимения во вьетнамском языке:

• Личные местоимения: “ti”, “chng ti ”, “mnh”;

• Указательные местоимения: “y”, “ y”, “ ”;

• Определительные местоимения: “m i”, “c ”;

• Вопросительные местоимения: “ai”, “g ”, “no”;

• Неопределенные местоимения: “no ”, “m t s ”.

4. [VB] Глаголы обозначают действие, процесс, состояние или качество. Например, “vi t”, “ c”, “nghe”, “i d o”, “mua s m”;

5. [AD] Наречия обозначающие признаки действия, признаки признака предмета. Принято говорить, что слова этого класса отвечают на вопросы “как?”, “где?”, “куда?”, “когда?”, “зачем?”, “с какой целью?”, “в какой степени?”. Некоторые основные наречии во вьетнамском языке:

• Качественные наречия: “d n d n”, “b ng”, “o o”;

• Наречия времени: “ban ngy”, “ban m”, “bu i sng”;

• Наречия места: “y”, “ y”, “ ”, “ y”, “ y”;

• Указательные наречия: “th ny”, “nh th ”, “nh v y”;

• Наречие степени: “r t”.

6. [IN] Предлоги выражающие синтаксическую зависимость имен существительных, местоимений, числительных от других слов в словосочетаниях и предложениях. Например, “b ng”, “ci”, “c a”, “ang”, “d i”, “g n”, “qua”, “theo”, “thnh”, “trong”, “tr c”, “t i”, “vo”, “v i”, “r i”, “xong”;

7. [CC] Союзы служебные слова, выражающие смысловые отношения между однородными членами простого предложения или между частями сложного предложения. Например, “v ”, “c... c ”, “khng nh ng... m cn”;

• Сочинительный союз: “v ”, “hay”, “nhng”, “m ”;

• Коррелативный союз: “v ”;

• Подчинительный союз: “l ”, “r ng”;

8. [IN] Частицы служебная часть речи вносят различные значения, оттенки в предложение или служит для образования форм слова, например, “ ”, “ang”, “s ”;

9. [NC] Аффикс морфема, которая присоединяется к корню и служит для образования слов, например, “ci”, “s ”, “ban”;

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

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

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

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

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

Текстовые корпуса давно и плодотворно используются в компьютерной лингвистике. Существует несколько десятков крупных аннотированных корпусов для основных европейских языков, самый большой из них содержит несколько сотен миллионов словоупотреблений. Первые электронные лингвистические корпусы текстов появились в 60-е гг. прошлого столетия [16]. В 1963 г. в Брауновском университете (США) впервые был создан большой корпус текстов на машинном носителе (Brown Corpus, БК). Первая версия корпуса была представлена простым текстовым форматом (с небольшим количеством структурной разметки для выделения абзацев, заголовков, цитируемых фрагментов и т. п.). Позднее корпус был дополнен разметкой частей речи и морфологических признаков слов. В настоящее время корпусы созданы для многих языков мира. Среди современных корпусов английского языка наиболее известны Британский национальный корпус (British National Corpus), Международный корпус английского языка (International Corpus of English), лингвистический Банк английского языка (Bank of English) и др. Известный представительный корпус русского языка объемом примерно в один млн слов был создан в университете Упсалы (Швеция).

1.2.2 Проблемы обработки вьетнамских текстов Работы по автоматической обработке вьетнамских текстов стали появляться в последние десять лет. Среди них исследования Д. Дьена [68], X.H. Као [62, 63], Х.П. Ле [80], К.Т. Нгуена [89], Х. Нгуена [90], Л.А. Ха [76] и др.

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

Вьетнамский язык является разговорным языком (как китайский, японский и др.), в котором самый важный элемент является слогом, а не словом. Границы слова определяются контекстом. Сочетание различных слогов является единственным способом для построения новых лексических единиц или слов. Во вьетнамском языке не существуют приставок и суффиксов, их роль выполняют слоги, что еще более запутывает процесс анализа текста. Например, слоги “h c”, “sinh” и их сочетание “h c sinh” также являются словами в вьетнамском языке.

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

Не существует алгоритма, который сегментирует вьетнамское предложение на слова точно в соответствии с его смыслом, если предложение считается изолированным. Для примера рассмотрим следующее предложение: “Ci bn l c a ti ”, которое имеет два совершенно разных смысла в зависимости от различной сегментации: (i) “Это мой утюг” по сегментации “Ci | bn l | c a | ti”, (ii) “Это мой стол” по сегментации “Ci | bn | l | c a | ti”. Отсутствие алгоритма сегментации на слова, который работал бы в этом предложении, объясняется тем, что каждый слог может быть частью разных слов. Кроме того, вьетнамское предложение является последовательностью слогов, а не последовательностью слов, и его смысл не может быть определен без контекста.

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

В настоящее время вьетнамские лингвисты еще обсуждают и не пришли к согласию в вопросе: “Что такое определение слова во вьетнамском языке? ”. Например, “my tnh xch tay” (ноутбук), “my bay ln th ng” (вертолет), “xe g n my” (мотоцикл), “m t d y” (грубый) и др. не имеют официального определения, чем они являются: отдельными словами или комбинацией из двух слов.

Не существует полного словаря вьетнамского языка и хороших вьетнамскоязычных корпусов текстов. На протяжении долгого времени вьетнамские, а также иностранные специалисты, разрешали эту проблему вручную. Однако построение словаря или хороших аннотированных корпусов текстов вручную требует колоссальных усилий и все же не обеспечивает полноты словаря вьетнамских слов [23, 24, 79]. Одна из причин этого широкое использование вьетнамского языка в различных сферах со специальными словами, которые редко используется. Другая во вьетнамских документах появилось много новых слов, являющихся иностранными словами (“avatar ”, “sms”,...), трудности возникают и со словами наиболее часто используемых подростками (“mn”, “x tin”,...), которые не содержатся ни в одном из вьетнамских словарей. Кроме этого, условия жизни быстро меняются. С развитием новых технологий и увеличением объемов информации постоянно расширяется лексикон вьетнамского языка. Например, новые слова Интернет, айфон и т. п. надо включать в словари как новые понятия. Кроме того, по сведениям автора, нет полного вьетнамского словаря собственных имен и названий мест и организаций. Еще одна причина отсутствия полного словаря заключается в том, что в различных регионах используются разные диалекты и словосочетания. Все эти причины делают процесс построения списка вьетнамских слов вручную трудновыполнимым. Согласно [68], крупнейшие вьетнамские словари содержат менее 33 000 слов, но во втором издании Оксфордского словаря английского языка содержится более 250 000 слов. По последним данным самый полный вьетнамский словарь содержит только 75 000 слов, но в реальности по оценке специалистов количество вьетнамских слов насчитывает уже более 200 000.

Это означает, что более половины вьетнамских слов нигде не сохранены.

Сегментация предложений на слова, словосочетания и фразы В исследованиях по распознаванию во вьетнамских текстах образов слов, словосочетаний и фраз (сегментации предложений) используются три основных способа: словарный (обычно с применением алгоритма максимального соответствия), статистический и комбинированный, сочетающий в себе оба предыдущих. Проблема сегментации вьетнамского предложения на слова исследовалась в [68, 76, 80, 89, 90]. Выделяются два основных подхода: подход на основе множества [68, 80, 89], относящийся к типу обучения с учителем, и подход на основе обучения без учителя [76, 90].

Для реализации процесса обучения с учителем Динь [68] использовал модели WFST (Weighted Finite State Transducers) и нейронных сетей, Нгуен [89] модели CRF (условных случайных полей) и SVM (метод главных векторов), Ле [80] гибридные алгоритмы с методом максимального сопоставления. Эти методы основаны на использовании словаря из 34 000 слов и примерно 1 400 аннотированных документов. Понятно, что при таком обучении используется ограниченное число различных слов. По утверждениям авторов точность этих методов более 90%, но только на небольших наборах аннотированных документов.

При втором подходе Ха [76] применял модель “три-граммы” над большим набором документов, Тхань [90] использовал формулы взаимной информации (MI) и модель N -граммы с генетическим алгоритмом.

Общими недостатками описанных методов являются: (i) отсутствие этапа процесса обучения для повышения точности статистической информации; (ii) выбор какой-то одной формулы для характеристики связи между слогами в одном слове, например, MI в [76] или максимальной вероятностью N -граммы в [90], в то время как желательно “гибко” использовать различными формулы; (iii) сравнительно малый объем наборов документов при обучении. Во второй и третьей главе диссертации будут предложены новые методы обучения, базирующиеся на существенно большем объеме обучающих данных. Проведенные сравнения показывают, что на этом большом объеме точность упомянутых выше методов была существенно меньшей, чем писали авторы: 50% для [76] и 80% для [90].

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

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

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

Программы анализа и лингвистической обработки текстов.

1. Link Grammar Parser (Jonh Laerty, Daniel Sleator, Davy Temperley, Carnegi Melon University, USA). Синтаксический парсер английского языка, 60.000 словарных форм. Реализован на C для Unix. Версия для Windows API32. Консольный интерфейс. Исходные предложения вводятся с клавиатуры или задаются в ASCII-файле для пакетной обработки.

2. Mystem Илья Сегалович, Виталий Титов компания Яndex. Компактный и быстрый морфологический пасер русскоязычных текстов на основе словаря Зализняка.

3. Программные продукты фирмы LingSoft, Финляндия. Компоненты грамматического разбора, морфологического анализа и лемматизации (нормализации) для английского, немецкого, финского, датского, норвежского, шведского, эстонского и русского языков.

4. Рабочее Место Лингвиста компания Dialing, Москва. Анализ текстов для построения систем автоматического перевода с русского на английский язык (и наоборот). Синтаксический анализатор текстов на русском языке; морфологический анализатор текстов на русском и на английском языках; построение конкордансов для заданной совокупности текстов. морфологические словари русского (80 тыс. слов) и английского (60 тыс. слов) языков.

5. NetXtract 2000 Relevant Software Inc. Компонента к Microsoft Internet Explorer (версии 5.0 и выше) позволяет быстро получить упорядоченный индекс слов в загруженном HTML документе. Индекс упорядочивается по алфавиту или частоте. Для каждого слова в индексе можно исследовать контекст, в котором это слово встречается. Выбранные слова по желанию заносятся в персональную базу знаний, систематизирующую найденные документы удобным образом.

6. Textual Analysis Computing Tools (TACT) Library Electronic Text Resource Service Indiana University, USA. Пакет программ обработки ASCII текстов, разработанный группой исследователей из Университета в Торонто. Для автоматизированной разметки текста; построения упорядоченных списков слов; анализа распределения слов в тексте по длине и частоте; построения конкорданса и 7. АОТ (автоматическая обработка текста) Алексей Сокирко и Со.

Разработки бывших сотрудников компании Диалинг: модуль графематического анализа текста; компоненты морфологического анализа для русского и английского языка; модуль автоматического уничтожения омонимии; модуль семантического анализа текста;

различные тезаурусы.

8. Технологии поиска и анализа текстовой информации Гарант-ПаркИнтернет. Анализ и классификация текстов, автоматическое реферирование; различные варианты поиска текста; морфологический, синтаксический и семантический анализ текста; средства навигации по большим массивам текстов; различные научные публикации авторов проекта.

Программы преобразования текстов.

1. HTML Batch Editor 2001 Lucersoft. Компактная утилита для Windows, осуществляет пакетные преобразования массивов текстовых или html-файлов с помощью набора заданных шаблонов.

2. XReplacer XDW Soft, 2000-2001. Программа для Windows 9x/ME/ NT/2000/XP, производит массовые операции поиска и замены в множестве текстовых файлов. В качестве поисковых шаблонов регулярные выражения. Понимает до 12 различных кодировок, их состав расширяется пользователем.

3. XMarkup v1.6.8 Логичев С.В., 1999-2002. Описание эксперементальной программы для выполнения сложных преобразований множества текстов. Консольная утилита для Windows 9x/NT/2000/XP.

изменяет, добавляет и удаляет заданные элементы обрабатываемых текстов.

Генераторы текстов и говорящие программы.

1. ALICE. Dr. Richard S. Wallace. ALICE AI Foundation, USA. Говорящая программа, получившая приз Лобнера (Loebner prize) в 2000 и 2001 г. развивается как open-source проект под эгидой некоммерческой организации зарегистрированной в США. В основе технологии лежит использование AIML (специализированного языка разметки для искусственного интеллекта).

2. The Dada Engine Andrew C. Bulha. Генератор случайных текстов на основе заданной грамматики (англ. яз.).

Работает на UNIXподобных системах, загружается исходный код. На его основе реализована on-line версия Генератора Постмодернистских Текстов.

3. Programmable Articial Intelligence (PAIv3.01) или Программируемый Искуственный интеллект Claudio Scordino, 2002. Общается с использователем на английском языке. Способность обучения пользователь постепенно может научить программу понимать нужные фразы, слова, глаголы и даже команды. На языке C++ для Linux, FreeBSD и Windows.

Системы обработки естественного языка.

1. NaturalLanguage Projects at ISI Univ. of Southern California/Information Science Inst., 1999-2001. Описание группы проектов по вычислительной лингвистике и машинному переводу. Webclopedia создание информационных агентов, способных генерировать ответы пользователю на основе анализа разнородных коллекций ресурсов, доступных в сети. ONTOSAURUS онтологический тезаурус, включающий 90.000 концептуальных сущностей (словарная база из проекта WordNet). SUMMARIST мультиязычная система реферирования текстовой информации. ReWrite система двуязычного перевода, основанная на статистическом анализе пар текстовых корпусов.

2. Следопыт3.0 MediaLingua Ltd., 2001. Интеллектуальная поисковая система для смыслового и нечеткого поиска документов на русском и/или английском языках. Учитывается морфология и изменение грамматических форм элементов поискового запроса. Понимает все основные форматы документов для Windows.

3. Поисковая система Алхимик ВЕЛТОН.SOFT, 2002. Анализ и поиск русскоязычных документов. Использует фрагменты семантического словаря профессора В.А.Тузова. Входными документами могут быть файлы в форматах MS Word, HTML и TXT.

4. ABBYY Retrieval & Morphology (ARM) Engine 4.0 ABBYY Software House, 2001. Коммерческая инструментальная система позволяет встраивать в разрабатываемые приложения функции полнотекстового поиска и морфологического анализа текстов. Поддерживает практически все европейские языки. Реализована в виде API с использованием технологии COM-объектов.

5. NeurOK Semantic Suite НейрOK Интелсофт, 2002. Программные продукты для поиска и анализа в текстовых массивах информации, реализованные с использованием технологии нейтронных сетей.

Глава Методы распознавания образов при графематическом анализе Графематический анализ представляет собой начальный этап обработки текста, представленного в виде цепочки ASCII символов, подготавливающий информацию, необходимую для дальнейшей обработки морфологическим и синтаксическим процессорами [35, 45]. В ходе этого этапа определяются элементы грамматической структуры: слова, знаки пунктуации, сокращения, имена с инициалами, даты, цифровые комплексы, формулы и т. д. На выходе каждому элементу текста присваивается графематический дескриптор. Кроме деления текста на элементы, компонент разбивает текст на абзацы и предложения.

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

Как указывалось в первой главе, для вьетнамского языка трудной является вторая задача распознавание слов и словосочетаний, сегментация предложении на слова [86]. Для ее решения в этой главе будут рассмотрены две проблемы:

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

2. Построение из большого набора предложений с помощью процесса обучения без учителя адекватной вероятностной модели. Процесс обучения сам по себе является алгоритмом сегментации предложении на слова.

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

2.1 Извлечение графематических дескрипторов Типичная задача извлечения фактов заключается в обработке текста на естественном языке с целью извлечения заданных элементов. На входе процесса извлечения слабоструктурированный или неструктурированный текст на естественном языке; на выходе заполненные структуры данных, позволяющие проводить дальнейшую автоматическую или ручную обработку информации [20, 21, 43, 44]. К настоящему времени обучаемые модели извлечения фактов из текстов, не привязанные к конкретному языку, развиты слабо и не обладают должным качеством извлечения [2]. Необходимо иметь возможность как точной ручной настройки модели, так и автоматической на основе обучающих примеров. Этому требованию в большей степени удовлетворяют символические модели.

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

Элементами графематического дескриптора являются:

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

• различные элементы текста, не являющиеся слогами (цифры и числа, даты в цифровых форматах, буквенно-цифровые комплексы, цифрово-знаковые комплексы и т. п.);

• собственные имена, названия, аббревиатуры;

• иностранные лексемы.

Основные трудности задачи:

1. Распознавание случаев использования знаков препинания в иных целях, а не в качестве разделителя фразы. Например, точка в сокращенном слове (“TP.HCM ”, “T. ”), точки и двоеточия в форме веб сайта (“http://www.google.com”) или дефис и другие знаки в форматах даты и времени (“2-9-2003”, “19:30”) и т. п;

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

3. Распознавание собственных имен, сокращений, технических терминов, аббревиатур и иностранных лексем.

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

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

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

В этом разделе предлагается и исследуется модель для извлечения графематических дескрипторов в системе обработки вьетнамского языка, основанная на символическом подходе с использованием методов, основанных на сопоставлении образцов [77], которые оперируют понятиями образцы и правилами их сопоставления с фрагментами текстов. Также представлены и обсуждены лингвистические характеристики и атрибуты вьетнамского языка, понятия и конструкции образцов и правил для построения наборов правил извлечения фактов из текстов на вьетнамском языке. Ключевым элементом модели является набор правил извлечения.

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

По структуре образец во многом схож с регулярным выражением и состоит из шаблона и атрибутов. Например, образец с имением “P-Date” описывает конструкции вида:

P-Date {/* ngy 12/07/1982 */ P : word Day/Month/Year;

C1 : IsVietnameseWord(word) & word = “ngy”;

C2 : Length(Day) = 2 & IsNumeric(Day);

C3 : Length(Month) = 2 & IsNumeric(Month);

C4 : Length(Year) = 4 & IsNumeric(Year);

Шаблон (секция с имением “P ” pattern) это регулярное выражение, записанное относительно его элементов. В шаблоне образца “PDate” конструкция состоит из четырех атомов: “word”, “Day”, “Month” и “Year”.

Атрибуты каждого из атомов формулируются в критерии (секции “C1 ”, “C2 ”, “C3 ”, “C4 ” criterion). По сути, атрибуты это функции с аргументами элементами шаблона “P ”. Например, в секции “C1 ” указано что, атом “word” является вьетнамским словом (IsVietnameseWord(word)), и “word” слово “ngy” (word = “ngy”). В секции “C4 ” указано что, атом “Year” состоит из четырех символов (Length(Year) = 4), и “Year” - число (IsNumeric(Year)).

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

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

Например, графематический дескриптор с имением “M-Date” описывает конструкции вида:

M-Date {/* 12/07/1982 [Date]*/ P : Day/Month/Year;

C1 : Length(Day) = 2 & IsNumeric(Day);

C2 : Length(Month) = 2 & IsNumeric(Month);

C3 : Length(Year) = 4 & IsNumeric(Year);

где дескриптор “[Date]” графематического дескриптора “M-Date” записан в секции с имением “M ”, шаблон и атрибуты дескриптора записаны в секциях “P ”, “C1 ”, “C2 ” и “C3 ”.

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

Правила представляются в виде “образец действие”, где “образец” образец для извлечения в узком контексте; “действие” набор действий, выполняемых при успешном сопоставлении образца.

В задаче извлечения графематических дескрипторов основная цель распознавание и приписывание дескрипторов. Действие правил состоит из распознавания фрагмента текста с шаблоном и приписывания ему дескриптора при успешном сопоставлении. Например, правило с имением “R-Date” описывает конструкции вида:

R-Date {/* ngy 12/07/1982 ngy “[Date]” */ A: M-Date.P M-Date.M;

В секции O образец “P-Date” для сопоставления фрагментов текста.

Действие (секция A action) выполняется при успешном сопоставлении образца в секции O. Оно представляет собой графематический дескриптор “M-Date”. При успешном сопоставлении фрагмента текста и образца (“ngy Day/Month/Year”) с шаблоном графематического дескриптора “M-Data” (“Day/Month/Year”) фрагменту текста приписывается дескриптор “[Date]”.

Процесс распознавания и приписывания дискрипторов проиллюстрируем следующим примером. Рассмотрим предложение “Ti sinh ngy 12/07/1982 ”. При извлечении с помощью правила “R-Date”, предложение сопоставляется с описанным выше образом правила “P-Date”. Фрагмент текста “ngy 12/07/1982 ” успешно сопоставляется с образцом. Далее следует действие правила, по которому этот фрагмент текста будет сопоставляться с шаблоном графематического дескриптора “M-Date” (“Day/Month/Year”), и в реультате распознается фрагмент “12/07/1982 ”.

После процесса приписывания дескриптора действия мы получим итоговый результат аннотированное предложение “Ti sinh ngy [12/07/1982] [Date] ”.

2.1.2 Модель извлечения графематических дескрипторов Прежде всего, дадим определение самому понятию распознавания графематических дескрипторов с точки зрения теории формальных языков.

Пусть = {i } алфавит (конечное упорядоченное множество символов);

над этим алфавитом.

Элемент текста последовательность симоволов алфавитов языка: w = 1 2... l, где l длина элемента текста w.

Текстовый сегмент языка L представляет собой некоторую последовательность текстовых элементов вида: s = w1 w2... wn, где s некоторый текстовый сегмент, wi i-ый текстовый элемент сегмента (слог, числа или знак препинания), n - длина текстового сегмента s.

Под сцеплением сегментов s1 = w1... wl1 и s2 = w1... wk будем подразумевать такой сегмент s = w1... wl1 w1... wk, что элементы с номерами 1... l совпадают с элементами сегмента s1, а элементы с номерами l + 1... l + k совпадают с элементами сегмента s2. Для отражения факта сцепления будем использовать запись где si текстовый сегмент и s сцепление сегментов s1, s2,..., sn. Набор p(s) = s1, s2,..., sn называется разбиением сегмента s.

Определим набор текстовых сегментов CL = {s1, s2,..., sN } как их конечную совокупность.

Множества элементарных атрибутов конечные совокупности A = {Ai }, Aj =, где Aj CL. Если текстовый сегмент s CL принадлежит Aj (s Aj ), то будем считать, что s удовлетворяется атрибутом класса Aj или атрибут класса Aj покрывает сегмент s.

Образец или набор элементарных атрибутов последовательность элементарных атрибутов вида: P = A1, A2,..., Ak, где k длина набора, Ai (класс атрибута) i-ый элемент набора. Для любой пары элементов образца (Ai, Aj ) элемент Ai предшествует элементу Aj, если i < j.

сегмента s назовем правым разбиением по образцу P, если l = k и j 1, k sj Aj. Будем считать, что s покрывается образцом P или образец P покрывает сегмент s. Образец P задает множество таких текстовых сегментов SP, что каждый сегмент s SP покрывается образцом P.

разумевать образец P = A1... Al A1... Ak. Для отражения факта сцепления будем использовать запись где Pi образец, и P сцепление образцов P1, P2,..., Pn.

Определим набор образцов CA = {P = Ai |Ai A} как их конечную совокупность.

Дескриптор представляет собой запись, в которой описываются характеристики и свойства одного объекта.

Пусть задано некоторое конечное множество дескрипторов Графематический дескриптор пара образца и дескриптора: Mi = (Pi, Ti ), где Pi CA образец, и Ti T дескриптор, в котором описываются характеристики и свойства образца “Pi ”.

Рассмотрим конечное множество классов графематических дескрипторов где Pi = Ai CA характеризуется структурой графематического дескриптора, а Ti дескриптор, в котором описываются характеристики и свойства графематического дескриптора. M0 CT класс нераспознанных графематических дескрипторов. Текстовый сегмент s CL принадлежит классу Mi (s Mi ), если существует правое разбиение сегмента s (p(s) = sj ) по набору Pi. В этом случае будем считать, что s является графемой класса Mi. Кроме того, если строка s не является графемой с точки зрения правил языка, то будем считать по определению, что Определим множество допустимых графем:

Правила извлечения представляют собой выражения вида где Pc образец для извлечения в узком контексте, Mo = (Po, To ) графематический дескриптор, Po образец для извлечения фрагмента текста и To дескриптор, который приписывается фрагменту. Правило говорит, что при успешном поиске в произвольном текстовом сегменте s фрагмента покрываемого образцом Pc, означающем, что существует разбиение сегмента p(s) = s1,..., so,... sn, в котором фрагмент текста so покрывается образцом Po, текстовому сегменту so ставится в соответствие дескриптор To (se Mo ).

Обозначим R = {R} множество правил извлечения.

классов графем, CT множество допустимых графем, R множество правил извлечения. Основной задачей распознавания графематических дескрипторов в условиях M будем называть задачу построения для произвольного текстового сегмента s CL ее набор классов графематических дескрипторов Ms.

2.1.3 Графематическая модель вьетнамского языка Отметим основные атрибуты модели распознавания графематических дескрипторов.

Буквенные атрибуты • Вьетнамский слог произвольная последовательность букв вьетнамского алфавита, удовлетворяет некоторым правилам вьетнамского образования слога;

• Иностранный слог произвольная последовательность Unicodeбукв, которые не являются вьетнамскими слогами;

• Слог объединение двух предыдущих классов;

• Регистр определен на множестве слогов и принимает одно из следующих значений:

– нижний все символы слога находятся в нижнем регистре;

– заголовочный первый символ слова находится в верхнем регистре, остальные в нижнем;

– верхний все символы слога находятся в верхнем регистре;

– смешанный любая другая комбинация регистров.

• Место расположения атрибуты слога зависят от места расположения слога во фразе:

– в начале фразы слог находится в начале предложения или после знаков разделителя фраз.

– в конце фразы слог находится в конце предложения или перед знаками разделителя фраз.

– в серединой фразы слог находится между другими слогами в предложении.

Цифровые атрибуты • Число произвольная последовательность цифр;

• Сложное Число произвольная последовательность цифр и символов точек, запятой, удовлетворяющая некоторым правилам образования чисел;

• Буквенно-цифровая последовательность произвольная последовательность Unicode-букв и цифр:

– начальные цифры начальная часть последовательности цифры, а последняя часть буквы;

– начальные буквы начальная часть последовательности буквы, а последняя часть цифры;

– смешанный любая другая буквенно-цифровая последовательность.

• Цифро-знаковый комплекс произвольная последовательность цифр и знаков:

– начальные цифры начальная часть последовательности цифры, а последняя часть знаки;

– начальные знаки начальная часть последовательности знаки, а последняя часть цыфры;

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

• Сложный комплекс произвольная последовательность, состоящая из цифр, букв и знаков;

Знаковые атрибуты • Разделитель фразы произвольная последовательность символов точек (.), двоеточий (:), запятых (,), точек с запятой (;), восклицательных (!) или вопросительных знаков (?).

• Признак начала фразы произвольная последовательность открывающих скобок и знаков разделителя фразы.

• Признак конца фразы произвольная последовательность закрывающих скобок и знаков разделителя фразы.

• Признак начала параграфа присваивается первой графеме параграфа.

• Формальные знаки знаки, которые используются в формуле математики, физики и т. п.

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

– [NamePerson] дескриптор описывает имя человека;

– [NameNational] дескриптор описывает имя страны;

– [NameCity] дескриптор описывает название города;

– [NameOrg] дескриптор описывает название организации;

– [NameStreet] дескриптор описывает название дороги.

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

– [AbbrevPerson] дескриптор описывает аббревиатуру имени человека, например, “N. T. Trung”; “O. N. Granhichin”.

– [AbbrevOrg] дескриптор описывает аббревиатуру названия организации, например, “SmartFly, L.L.C.”.

• Специальные слова и словосочетании, которые используются на специальных предметах (математика, физика, информатика и т. д.) – [WebAdd] комплекс, состоящий из букв, знаков и цифр, который удовлетворяет некоторым правилам образования формы Веб-адреса, например, “www.google.com”.

– [Email] комплекс, состоящий из букв, знаков и цифр, который удовлетворяет некоторым правилам образования формы Email адреса, например, “[email protected]”.

– [Dir] комплекс, состоящий из букв, знаков и цифр, который удовлетворяет некоторым правилам образования формы директории, например, “C:|test.txt”.

Цифровые дескрипторы • [Num] цифро-знаковый комплекс, состоящий из цифр и знаков, который описывает числа, например, “12”; “1.000.000”; “15,500,000”.

• [KeyNum] комплекс, состоящий из цифр, знаков и букв, который удовлетворяет некоторым особым правилам, например, “keynumber:

LMRP-1200-1111-1774”; “car’s number: 52N-1008”.

• [PhoneNum] цифро-знаковый комплекс, состоящий из цифр и знаков, который удовлетворяет некоторым правилам образования формы номера телефона, например, “054 820129”; “(04)84-873333”.

• [Date] цифро-знаковый комплекс, состоящий из цифр и знаков, который удовлетворяет некоторым правилам образования формы даты (число, месяц, год), например, “12/07/1982”; “20-01-2001”.

• [Time] комплекс, состоящий из букв, цифр и знаков, который удовлетворяет некоторым правилам образования формы времени, например, “12h”; “21h30ph”; “21:15:45”;“ 1’15”30”.

Знаковые дескрипторы • [MoP] дескриптор разделителя фразы, произвольная последовательность символов точек (.), двоеточий (:), запятых (,), точек с запятой (;), восклицательных (!) или вопросительных знаков (?);

• [BoP] дескриптор начала фразы произвольная последовательность открывающих скобок и знаков разделителя фразы.

• [EoP] дескриптор конца фразы произвольная последовательность закрывающих скобок и знаков разделителя фразы.

2.2 Распознавание слов и сегментация При автоматической обработке вьетнамского текста наиболее трудной является проблема делимитации слова в предложении.

При решении задачи распознавания слов рассматриваются две проблемы:

• распознавание слов с вероятностной точки зрения;

• построение по большому набору предложений с помощью процесса обучения без учителя адекватной вероятностной модели.

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

Поддержка S определяется как число появления события E, в котором являются частью некоторого предложения. Пусть H является гипотезой, согласно которой (, ) не является ни словом, ни частью слова.

Предполагая, что гипотеза H верна, используя вероятностные модели, получаются некоторые характеристики S и S, от отношения которых зависит вероятность того, что H неверна. Тогда достоверность пары (, ) определяется как величина пропорциональная числу появления события E, (S), и пропорциональности значений S и S, ( S ). Очевидно, что если пара (, ) поддержана и достоверна то (, ) является словом или частью слова.

Обучающая вероятностная модель строится итеративно по некоторому алгоритму обучения без учителя. Начальный набор предложений огромное множество вьетнамских предложений, которое было получено из электронных документов в Интернете. На каждой итерации обучения выполняются следующие шаги: (i) поиск локальных максимально достоверных последовательностей слогов в предложениях; (ii) соединение последовательностей слогов, которые являются локальными максимально достоверными; (iii) пересчет всех вероятностных значений нового набора предложений и возврат к шагу (i). На основе функций достоверности строятся функции распознавания, которые для пар слогов дают вероятности того, что они могут быть частью слова. Локальные максимально достоверные последовательности слогов определяются с помошью функции распознавания и процессов сравнения соседних пар слогов.

Перечисленные шаги восприятия иллюстрируются следующим примером. Рассмотрим предложение S “Cng vi c c a chng ti thnh cng”. В первой итерации, рассматриваемые пары это “cng vi c”, “vi c c a”, “c a chng”, “chng ti ”, “ti ”, “ thnh”, “thnh cng”. Функция распознавания показывает, что “chng ti ” и “thnh cng” являются частью слова, потому что значения достоверности соседей ниже. Предложение S было переписано как “Cng vi c c a chng_ ti thnh_cng” с двумя новыми слогами “chng_ti ” и “thnh_cng”. Рассматриваемые пары слогов во второй итерации это “cng vi c”, “vi c c a”, “c a chng_ti ”, “chng_ti ”, “ thnh_cng”. Пусть “cng vi c” является локальным максимально достоверной парой, тогда S будет переписано как “Cng_vi c c a chng_ti thnh_cng”.

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

2.2.1 Вероятностная модель Основные понятия Пусть L множество всех вьетнамских букв. Обозначим множество вьетнамских слогов. S L. Для всех s = l1 l2... lk S по определению положим l(s) = k - длина слога s.

Пусть, S слоги, обозначим:

• P re(), если является префиксом ;

• Suf (), если является суффиксом ;

Например, “cng” P re(“cng vi c”), “vi c” Suf (“cng_vi c”) и “c a” P re(“c a”) Suf (“c a”).

Вьетнамское слово и словосочетание является либо слогом, либо комбинацией слогов.

Обозначим множество вьетнамских слов. W S. Для всех w = s1 s2... sk W определим l(w ) = k - длина слова w.

Вьетнамское Предложение является последовательностью слогов.

Пусть множество вьетнамских предложений в исследуемом наборе данных, C S. Для всех c = s1 s2... sk C определим l(c) = k длина фразы c.

Предложение “cng_vi c c a chng_ti thnh_cng” обозначается как S = 1 2... 5, в котором 1 =“cng_vi c”, 2 =“c a”,..., и 5 =“thnh_cng”. Последовательность 1 2... l является частью предложения S = 1 2... k, (1 l k), если 1 i k l + 1 : j = i+j1 j = 1,..., l.

Вероятностная модель P определяется как тройка (C, C, FC ).

Набор предложений C={s1, s2,..., sn } является конечной совокупностью предложений. C множество слогов, которые являются частями некоторых предложений si, принадлежащих в наборе C.

FC является множеством вероятностных функций.

Вероятностная функция Fc FC : R, может быть постоянной ( R), функциями слога (C R) или функциями пары слогов (2 C R) и т. д.

Пусть, c. Обозначим через N () число появлений в C. Определим:

Вероятность появления в C в качестве независимого слога или префикса, суффикса некоторых слогов равна соответственно:

где N1 = c N ().

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

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

Функции достоверности вероятностные функции пары слогов, которые оценивают какова вероятность того, что данные упорядоченные пары слогов являются словом или частью слова. Пусть H является гипотезой о том, что не является частью никакого слова. На основе вероятностной модели M, в которой H предполагается истиной, мы вычислим вероятность P () того события E, что пара появляется в C.

Определение 1: Пусть c R является константой. Функция достоверности fc,M (, ) : 2 R над вероятностной моделью M и набором C определяется следующим образом:

Пусть A является событием, в котором случайно выбирают два соседних слога x1 x2 в некоторых предложениях, и x1 = является суффиксом некоторых слов в предложениях из тестового набора; B является событием, в котором случайно выбирают два соседних слога x1 x2 в некоторых предложениях, и x2 = является префиксом некоторых слов в предложениях из оптимального набора. Из гипотезы H следует, что для каждого появления в C: (i) должен быть суффиксом некоторых слов, и (ii) должен быть префиксом некоторых слов. Следовательно, P () = P (AB). Определим возможные различные модели для оценки P (AB):

Модель 1 : Если A, B являются независимыми событиями, P (A) = c1 P () и P (B) = c2 P () (c1, c2 константы), то P (AB) = c1 c2 P ()P () и для c = c11c2 :

В действительности, P ()P () намного меньше, чем P (AB). Так как в естественном языке, никогда не стоят рядом чисто случайно. Предположим P (AB) = P ()() P ()(). Эксперименты показывают, что () = c log N () является хорошей оценкой, в которой c является константой и вычисляется из набора предложений.

Модель 2 : Если P (AB) = c1 P ()() P ()() (c1 константа), то для c = c11 :

Модель 3 : Если A, B являются независимыми событиями с P (A) Ps () и P (B) Pp (), то P (AB) оценивается как Ps ()Pp () и для c = 1:

Независимые слова (например, “v ”. “th ”, “l ”, “c a” и т. д.) являются важными факторами во вьетнамском языке. Частота появления этих слов достаточно велика. Существует известное предположение [63] о распознавании вьетнамских слов, которое гласит, что является словом в данном предложении, если и только если нельзя разместить независимые слова между ними, не изменяя смысл предложения. Пусть W множество независимых слов. Пусть событие E3 является частью некоторых предложений в C. Тогда NW () число появления события E3, W, Suf () и P re(). N3 =,c NW (). Вероятность события E3 определяется как PW () = NW (). Число появлений события AB пропорционально вероятности события E3.

Модель 4 : Если P (AB) = c1 PW (), то для c = c11 :

P = (C, C, FC ) вероятностная модель, msup, Msup, mcon, Mcon FC постоянные функции, в которых 0 < msup Msup и mcon Mcon.

fc FC является функцией достоверности. Функция распознавания слов определяется следующим образом:

Определение 2: fR : 2 {1, 0, 1} является функцией распознаC вания слов над fc и P с параметрами (msup, Msup, mcon, Mcon ) если:

Если значение, возвращаемое функцией распознавания слов, равно 1, то входная пара слогов была поддержана и эта пара слогов, вероятно, является частью некоторого слова. Если возвращаемое значение равно 1, входная пара слогов принадлежит двум разным словам. У нас нет решения, когда функция возвращает значение 0. Очевидно, что если msup = Msup и mcon = Mcon, то значение функции распознавания слов не может равняться 0, и не существуют неразрешимые случаи. Мы используем различные функции достоверности и различные функции распознавания слов, которые можем объединить в одну универсальную функцию распознавания слов, fR. Эффективность различных функций достоверности и функций распознавания слов изучены в экспериментах.

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

2.2.2 Метод обучения без учителя Правила обучения и процесс обучения. Пусть P = (C, C, FC ) является вероятностной моделью; fc, fR FC функции достоверности и универсальная распознавания соответственно, Dcon FC положительная постоянная; s = 1 2... k C предложение в наборе, и w = l l+1... l+m является частью предложения s (1 l < k, 0 < m kl).

Определение 3: w является локальной максимальной достоверной последовательностью (ЛМДП) в s над P, fc, fR и Dcon, если удовлетворяются следующие условия:

(ii) если l > 1 :fR (l1, l ) = 1 или fR (l1, l ) = 0 and fc (l, l+1 ) > fc (l1, l ) + Dcon (iii) если l + m < k : fR (l+m, l+m+1 ) = 1 или fR (l+m, l+m+1 ) = 0 and fc (l+m1, l+m ) > fc (l+m, l+m+1 ) + Dcon В условии (ii) и (iii) соседние слоги у w (l1, l )(l > 1) и (l+m, l+m+1 ) (l + m < k) уже рассмотрены. Они гарантируют, что соседние слоги не влияют на достоверности у w. Таким образом, w является частью слов.

Пусть w = l 2... l+m является ЛМДП в некоторых предложениях (Tw раз). Будем рассматривать следующие правила обучения, упорядоченные по приоритету.

Правило 0. Если Link(w) C : Замените w на Link(w).

Link(w) c показывает, что в прошлом мы узнали, что w является частью некоторых слов.

Правило 1. Если m = 1: Замените w на Link(w).

Правило 2. Сортировка значений функции достоверности f(i i + 1), l + m 1 i l. Если для пары (i, i+1 ) является наибольшим и разности между максимальным и следующим за ним значениями функции достоверности больше Dcon : Замените i i+1 на Link(i i+1 ). Разности значений функций достоверности гарантируют, что i i+1 не принадлежат разным частя слова.

Правило 3. Если m = 3, 4 и Tw Msup и f (w) Mcon : Замените на Link().

Процесс соединения слогов для правил 0, 1 и 2 выглядит следующим образом:

1.Learning-Process- 2.repeat 3. repeat 4. for each sentence s 7. s is rewritten by replacing w with Link(w) statistical values 8. Update, create new necessary statistical values 9. until No linking pair is found 10. for each sentence s 11. for each w is LMC of s 12. if inx of w satises Rule2 then 13. s is rewritten by replacing with Link() 14. Update, create new necessary 15.until No linking pair of Rule 2 is found Правило 0 всегда рассматривается как естественное правило обучения. Правила 1 и 2 позволяют найти пару слогов, которые являются частью некоторого слова. Приоритет правила 1 выше, чем приоритет правила 2. Правило 1 помогает распознавать слова, состоящие из двух слогов. Правило 3 имеет самый низкий приоритет, поскольку оно очень трудоемко. Случай m > 4 не рассматривается, так как во вьетнамском языке существуют не много слов из 5 слогов.

Теорема 1. Процесс соединения слогов с определенными параметрами завершается за конечное число итераций.

Доказательство. На каждой итерации с номером k (цикл в строке 2), определим Nlink число соединений между оригинальными слогами.

В результате процесса получается последовательность чисел соединений {Nlink }, для которой k Nlink > Nlink. В силу конечности набора возможных соединенных слогов, процесс завершит работу, выполнив конечное число итераций.

Пусть Ns число всех предложений в наборе.

Ms константа, наибольшее число слогов в предложениях (Ms = 30).

Теорема 2. Cложность процесса соединения слогов равна O(Ns Ms ).

Доказательство. Циклы в строках 4 или 10 дают в сумме не более чем Ns итераций, а циклы в строках 5 или 11 дают в сумме не более чем Ms итераций.

При этом условие в строке 6 (строке 12), соединение в строке 7 (строке 13), пересчет вероятностных значений в строке 8 (строке 14) выполняются за время, равное константе. Таким образом, общая сложность процессов проверки правил 0, 1 и 2, а также процесса соединения слогов равна O(Ns Ms ).

Эксперименты показывают, что суммарное количество итераций цикла repeat в строке 2 или 3 можно оценить некоторой константой D.

Таким образом, общая сложность процесса равна O(Ns Ms ).

Стратегия обучения. Системные параметры (СП) (mcon, Mcon, msup,...) определяют характер процесса обучения. Например, чем выше значения Mcon, тем число новых слов меньше, но точность обучения выше.

Предлагаемая процедура обучения является примером стратерии “Медленно, но Верно”. Пусть (m, Mcon, m,...) является искомым СП для оптимального адекватного набора предложений. Создадим последовательности СП: (m1,con, M1,con, m1,sup,...),..., (mn,con, Mn,con, mn,sup,...) = (m, Mn,con, m,...), в которых: mi+1,con mi,con, Mi+1,con Mi,con,.... Процесс обучения с правилами 0, 1, 2, 3 и искомый СП (m, Mn,con, m,...):

1.Learning-Process 2. Computing necessary statistical values of syllable and pairs of syllables 4. Setting the parameters to (mi,con, Mi,con, mi,sup,...) 5. Learning-Process- 6.for each sentence s 7. for each local maximum condent sequence w of s 9. s is rewritten by replacing w with Link(w) Learning-Process-1 был выпонен n-раз (строки 3-5) с n системными параметрами (СП), которые сходятся к искомым. Выбор этих системных параметров является гарантией качества процесса обучения. Правило было выпонено в линии 6-9 для гаратирования того, что все слова из 3- слогов были распознаны.

Адекватный алгоритм сегментации и Словарь. Пусть P = (C,, FC ) является вероятностной моделью, которая была получена из процесса обучения. Msup FC C минимальное поддержанное число. Словарь D, сгенерированный с P, определяется так: D = {w |N1 (w) Msup }. Эксперименты показывают, что при выборе хороC ших системных параметров можно распознавать не только вьетнамские слова, но и также фразы, названия организаций и т. п.

Первоначальная версия описанного процесса обучения была опубликована в [24, 25]. Здесь был описан модернизированный алгоритм, представленный в [79].

Процесс обучения сам по себе является алгоритмом сегментации слов.

“Входящие” предложении были сегментированы по алгоритму обучения.

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

2.2.3 Метод распознавания фраз Пусть P = (C, C, FC ) является вероятностной моделью и задана фраза c = s1 s2... sl C. Выберем параметры P = (msup, Msup, mcon, Mcon ), fc FC функция достоверности и fR FC универсальная функция распознавания определяется над fc и P с параметрами P. Алгоритм разделения фраз выглядит следующим образом:

Алгоритм разделения фраз 2. На k-ом такте 3. вычислим значении fR (sk, sk+1 ) 9. else выход В результате получаются новые фразы, которые являются частями фразы c.

Определение 4: Пусть заданы наборы фраз C1, C2 и fR FC универсальная функция распознавания. Говорят, что C2 родится из C1 по fR и процессу разделения фраз, обозначая C1 = C2, если C2 получится из процесса разделения всех фраз в C1 по fR.

Обозначим N (C) число фраз в C.

Пусть задан набор начальных предложений C0. Выберем 0, параметры P = (msup, Msup, mcon, Mcon ). Процесс разделения набора фраз выглядит следующим образом:

Процесс разделения набора фраз 2. На k-ом такте 3. построим вероятностную модель Pk = (Ck, Ck, FC ) 4. рассчитываем значении функции fR с параметрами P 5. выполняем алгоритм разделения предложения 6. в результате получаем Ck = Ck+ Теорема 3. Процесс разделения набора фраз с определенными параметрами завершается за конечное число итераций.

Доказательство. В результате процесса получается последовательность наборов фраз {Cn }, для которой k N (Ck+1 ) N (Ck ) +. В силу конечности набора возможных фраз, алгоритм завершит работу, выполнив конечное число итераций.

Теоретическое обоснование сходимости последовательности {Cn } к набору C, в котором все фразы являются вьетнамскими словами или словосочетаниями, достаточно затруднительно. На качество работы алгоритма существенно влияет выбор конкретных значений параметров и P, зависящий как от общих характеристик вьетнамского языка, так и от выбранного набора начальных фраз C0.

Глава Оптимизация параметров скрытых марковских моделей при распознавании морфологической структуры Стадия морфологического анализа является наиболее проработанным лингвистическим этапом процесса обработки естественного текста [3, 14, 18, 19, 36, 37]. Цель морфологического анализа заключается в определении морфологических признаков слов для использования их на последующих этапах обработки текста. За последние два десятилетия создано, по крайней мере, несколько десятков алгоритмов для разных языков, например, английского, германского, русского и др. Как указывалось в первой главе, во вьетнамском языке проблемы морфологического анализа становятся более сложными из-за нерешенности проблемы делимитации слова.

Морфологический анализ обычно работает на уровне отдельных слов и возвращает морфологические характеристики данного слова. Задача морфологического анализа автоматически распознать, какой части речи принадлежит каждое слово тексте. Целью и результатом морфологического анализа является определение морфологических характеристик слова и его основная словоформа. В английском языке простой алгоритм, присваивающий каждому слову в тексте наиболее вероятный для данного слова морфологический класс работает с точностью около 90%, что обусловлено лексической многозначностью английского языка.

При морфологическом анализе вьетнамских текстов рассмотрим два основные проблемы.

1. морфологическая разметка корпуса вьетнамских текстов;

2. морфологический анализ вьетнамского предложения снятие морфологической омонимии.

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

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

Морфологическая разметка основой тип разметки в текстах, он рассматривается как основа для дальнейших этапов анализа синтаксического и семантического. Схема морфологической разметки предполагает наличие, во-первых, набора морфологических признаков, во-вторых, описания того, что каждый из них означает и, в-третьих, правил присвоения морфологических признаков единицам текста. Размер наборов морфологических признаков, применяемых в разных корпусах, варьируется. Несомненно, чем больше набор признаков, тем более детальный анализ текста осуществим с его помощью. Однако по мере увеличения объема корпусов наметилась тенденция к сокращению числа морфологических признаков. Упрощенная система кодировки способствует устранению лишних ошибок, противоречивости, морфологической неоднозначности и, в конечном итоге, повышает скорость разметки больших массивов текста, содержащих миллионы слов [16, 85, 87, 88, 101, 104].

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

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

Для снижения человеческих затрат рассмотрим следующий подход:

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

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

Тексты, включенные в корпус, относятся к разнообразным литературным жанрам.

3.1.1 Основные понятия и формальная постановка Слово оригинальный слог (“c a”, “ ”) или соединение слогов (“cng_ vi c”, “chng_ti ”, “thnh_cng”).

Тэг код морфологического признака, например, [NN] существительное, [VB] глагол.

T = {t1, t2,..., tm } конечный набор тэгов.

Помеченное слово слово с некоторыми пометками (тэгами) представляется в форме: w[T ], где T = {t} T является множеством тэгов слова w.