187014 (Искусственный интеллект)

Искусственный интеллект.

Принцип аналогии в морфологии

В работе Белоногова Г. Г. и Зеленкова Ю. Г. описывается принцип построения алгоритма морфологического анализа текстов на основе принципа аналогии. Данный принцип используется в системах орфографического контроля русских текстов, системах автоматического индексирования документов и системах машинного перевода текстов с русского языка на английский и с английского языка на русский. Производительность программы на компьютере с процессором от 386 и выше составляет около 400 слов/с.

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

Для того, чтобы определить грамматические характеристики слов без словаря, Белоногов предложил принцип аналогии. Он основан на том, что существует сильная корреляционная связь между грамматическими характеристиками слов и буквенным составом их концов. Например: организация, приватизация, концентрация имеют ж. р., им. п. и ед. ч.; работают, понимают, привлекают - это глаголы в 3-ем лице мн. ч. и т. д.

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

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

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

масштаба 01/001/01

служба 01/056/01

возникшие 02/105/10

батальон 00/021/01

рассчитывая 00/152/10

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

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

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

аба 01/001/01

еба 01/044/01

неба 01/071/01

авшие 02/105/10

тальон 00/021/01

тывая 00/152/10

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

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

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

В настоящее время вероятность правильного анализа слов при обработке текстов любой тематики превышает 99%.

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

ГРАММАТИКА, ПОСТРОЕННАЯ НА ОПРЕДЕЛЕННЫХ ПРЕДЛОЖЕНИЯХ (DEFINITE-CLAUSE GRAMMAR или DCG)

Проведение работ по исследованию построения грамматик для понимания естественного языка (далее ЕЯ) приобрело большую популярность после введения Колмеройером в 1975 году грамматических формализмов, основанных на предложениях Хорна. Так называемые метаморфозные грамматики (metamorphosis grammars или MGs) определили рост заинтересованности в области выражения лингвистических понятий в логике (qv) и заложили основу для создания качественных блоков предварительной обработки данных (процессоров ввода-вывода) и интерфейсов. Основное применение результаты этих исследовательских работ нашли в консультировании и создании баз данных на основе ЕЯ, выработке вопросов и ответов, переводе текстов и синтезе текстов, исходя из надлежащим образом оформленных спецификаций.

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

Техника экстрапозиционных грамматик (extraposition grammars или XGs) была предложена Перейрой для описания определенных глобальных отношений или экстрапозиций, таких как связь между относительным местоимением и его записью. В конечном итоге разработки наподобие грамматик структуры определений (modifier structure grammars или MSGs) Даля и МакКорда, древовидных грамматик (tree grammars или TGs) Колмеройера и усложненных грамматик (puzzle grammars или PGs) Сабатье увеличили силу выражения лингвистических понятий.

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

ЛОГИЧЕСКИЕ ГРАММАТИКИ

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

sentence -> noun-phrase verb-phrase

устанавливается связь между тремя нетерминальными символами: предложение может состоять из именной группы и следующей за ней глагольной группы.

Такие правила могут быть отображены в PROLOGе следующим образом:

sentence (S1, S3): - noun-phrase (S1, S2), verb-phrase (S2, S3).

verb-phrase (S1, S2): - connects (S1, writes, S2).

connects (1, each, 2).

connects (2, author, 3).

connects (3, writes, 4).

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

В нижеследующей записи числа обозначают начало и конец каждого слова:

₁each₂ author₃ writes₄

Чтобы проверить правильность построения предложения, необходимо указать цель

? - sentence (1, 4).

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

? - sentence ([each, author, writes]. [ ]).

Грамматики, построенные на определенных предложениях, являются объемом понятия контекстно-свободных грамматик, которые также могут быть транслированы на язык PROLOG. Грамматики, построенные на определенных предложениях, позволяют любому логическому выражению стать нетерминальным, они построены на логических символах: константах, переменных, выражениях, - а не только на одних константах. Также они имеют только один нетерминальный символ в левой части каждого правила. Контекстные зависимости (контекстные отношения подчинения) описываются логическими переменными в рамках параметров (или независимых переменных) грамматических символов.

У правила грамматики, построенной на определенных предложениях, следующая форма:

nonterminal symbol -> body (основная часть программы).

где “body” (“основная часть”) является последовательностью одного или более элементов данных, отделенных друг от друга запятыми. Каждый элемент данных является либо нетерминальным символом, либо последовательностью терминальных символов. Значение правила состоит в том, что "основная часть"- это возможная форма для группы типа “нетерминальный символ”. В PROLOGе нетерминальный символ записывается как выражение (а не как список), а последовательность терминальных символов - в виде списка.

В правой части правила наряду с нетерминальными символами и списком терминальных символов могут находиться последовательности вызовов процедур, записываемых в фигурных скобках ({and}). Они используются для выражения дополнительных условий, которые в обязательном порядке должны выполнятся, чтобы правило действовало. Нетерминальный символ преобразуется в (N + 2)-местный предикат (имеющий идентичное название), чьи первые N параметры полностью описаны в нетерминальном символе и чьи последние два параметра являются такими же, как и при трансляции контекстно-свободного нетерминального символа. Вызовы процедур в правой части правила транслируются так, как они есть.

Каждое грамматическое правило, типа

p(X) -> q(X).

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

p(X, S0, S): - q(X, S0, S).

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

Когда в правиле содержатся терминальные символы, они транслируются со сказуемым "connects". К примеру,

connects(S1, X, S2)

означает, что суть S1 связана через X с сутью S2.

Правило

p(X) -> (older), q(X), (high).

преобразуется в

АНАЛИЗ ЕЯ

В 1977 году Колмеройер ввел общую схему анализа ЕЯ, что явилось решающим шагом вперед и вызвало огромный интерес в области использования логических грамматик как альтернативы прочно утвердившимся грамматикам расширенных сетей переходов (augmented transition network grammars). С исторической точки зрения, это можно признать поворотным пунктом, так как был указан метод преобразования предложений ЕЯ в логические структуры. Метод заключался в рассмотрении простейших высказываний, содержащих собственные имена существительные, какой бы то ни было артикль в виде квантора (кванторного слова) с тремя операциями перехода и четыре приоритетных правила, для разрешения проблемы иерархии квантования (количественного измерения качественных признаков).

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

Chomsky is (a) writer