Часть 4.

зависимые языки. Такой способ представления обладает некоторыми преимуществами по сравнению с контекстно-зависимыми грамматиками при разработке анализаторов.

13.3. Синтаксис и знания в ATN-анализаторах

Альтернативой для контекстно-зависимых грамматик является сохранение простой структуры правил контекстно-независимой грамматики и расширение этих правил за счет добавле­ния процедур, выполняющих необходимые контекстуальные проверки. Такие процедуры вы­полняются при использовании правила в процессе анализа. Вместо использования граммати­ки для представления таких понятий, как формы единственного и множественного числа, времена глаголов, одушевленные и неодушевленные предметы, их можно представлять с по­мощью средств (feature), связанных с терминальными и нетерминальными символами грам­матики. Связанные с правилами грамматики процедуры обращаются к этим средствам для присвоения значений и выполнения необходимых проверок. К грамматикам, использующим расширения контекстно-независимых грамматик для реализации контекстной зависимости, относятся расширенные грамматики фразовой структуры (augmented phrase structure) [Heidorn, 1975], [Sowa, 191 А], расширения логических грамматик (augmentation of logic gram­mar) [Allen, 1987] я расширенные сети переходов ATN (augmented transition network).

Этот раздел посвящен ATN-анализу и вопросам разработки простых ATN-анализаторов для предложений из "мира собак", о которых шла речь в подразделе 13.2.1. Будут выполне­ны первые два шага процедуры, проиллюстрированной на рис. 13.2: создание дерева раз­бора и его использование для построения представления смысла предложения. В этом при­мере будут использованы концептуальные графы, хотя ATN-анализаторы можно также строить на основе сценариев, фреймов и логических представлений.

13.3.1. Анализаторы на основе расширенных сетей переходов

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

Процедуры могут связываться как с терминальными, так и нетерминальными символами (в том числе verb, noun_phrase). Например, слово можно описывать с использо­ванием его морфологического корня, а с помощью процедуры задавать часть речи, един­ственное или множественное число, лицо и т.д. Нетерминальные символы грамматики описываются аналогично. Именная конструкция описывается артиклем, существитель­ным, его числом и лицом. Как терминальные, так и нетерминальные символы можно представить с помощью фреймоподобной структуры с именами ячеек и их значениями. Значения этих ячеек могут задавать процедуры или указатели на другие структуры. На­пример, первая ячейка фрейма предложения может содержать указатель на определение именной конструкции. На рис. 13.6 показаны фреймы для нетерминальных символов sentence, noun_phrase и verb_phrase в описанной выше простой грамматике.

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

576 Часть V. Дополнительные вопросы решения задач искусственного интеллекта

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

Глава 13. Понимание естественного языка

577

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

При обращении к сети нетерминального символа анализатор создает новый фрейм. Например, при входе в сеть nounjphrase создается фрейм noun_phrase. Ячейки фрейма заполняются функциями для этой сети. Этим ячейкам могут быть присвоены значения грамматических свойств или указатели на компоненты синтаксической структуры (т.е. символ verb_phrase может состоять из символов verb и noun_phrase). При достижении конечного состояния сеть возвращает полученную структуру.

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

На рис. 13.8 фреймы и ячейки обозначены идентификатором ФРЕЙМ.ЯЧЕЙКА, в частности ячейка числа фрейма глагола обозначена VERB. NUMBER. В процессе разбора каждая функция строит и возвращает фрейм, описывающий соответствующую синтаксическую структуру. В этой структуре содержатся указатели на структуры, возвращаемые сетями более низкого уровня. Функция самого высокого уровня (уровня предложения) возвращает структуру sentence, представляющую дерево разбора входного потока. Эта структура передается семантическому интерпретатору. На рис. 13.9 показано дерево грамматического разбора, возвращаемое для предложения "The dog likes man".

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

Глава 13. Понимание естественного языка 579

13.3.2. Объединение знаний о синтаксисе и семантике

Семантический интерпретатор строит представление значения входной строки, пере­мещаясь по дереву грамматического разбора от корневого узла sentence. В каждом узле он рекурсивно интерпретирует его дочерние узлы и объединяет полученные результаты в общем концептуальном графе. Например, семантический интерпретатор строит пред­ставление символа verb_phrase, формируя рекурсивные представления дочерних узлов verb и nounjphrase и объединяя их для представления глагольной конструкции. Ре­зультат передается узлу sentence и объединяется с представлением символа subject.

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

В рассматриваемом примере семантический интерпретатор использует базу зна­ний о "мире собак". К понятиям этой базы знаний относятся объекты dog и man, a также действия like и bite. Эти понятия описываются с помощью иерархии типов, показанной на рис. 13.10.

580 Часть V. Дополнительные вопросы решения задач искусственного интеллекта

Рис. 13.10. Иерархия типов для приме­ра из "мира собак"

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

Символ agent (агент) связывает понятие act (действие) с понятием типа animate

(одушевленный). Агент определяет отношение между действием и одушевленным

объектом, инициирующим это действие.

Символ experiencer (носитель состояния) связывает понятие state (состояние) с

понятием типа animate (одушевленный). Он определяет отношение между психическим состоянием и его носителем.

Символ instrument (инструмент) связывает понятие act (действие) с понятием entity

(сущность) и определяет инструмент, используемый для выполнения действия.

Символ object (объект) связывает понятие event (событие) или state (состояние)

с понятием entity (сущность) и представляет отношение "действие-объект".

Символ part (часть) связывает понятия типа physobj (физический объект) и определяет отношение между целым и его частью.

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

Лингвистические отношения (агент, объект, инструмент и т.д.), соответствующие

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

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

что агент должен относиться к типу dog. Тогда предложение "Man bites dog" будет

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

Используемые по умолчанию значения компонентов падежного фрейма. Во фрейме глагола "bites" для понятия, связанного с отношением instrument, по умолча­нию используется значение teeth.

Глава 13. Понимание естественного языка

581

Рис. 13.11. Падежные фреймы для глаголов "like" и "bite"

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

procedure sentence;

begin

вызвать процедуру noun_phrase для получения представления

подлежащего; вызвать процедуру verb_phrase для получения представления

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

существительного, возвращаемое для подлежащего, с агентом графа

для глагольной конструкции end

procedure noun phrase;

begin

вызвать процедуру noun для получения представления

существительного; case

неопределенный артикль и единственное число: понятие,

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

582

Часть V. Дополнительные вопросы решения задач искусственного интеллекта

end case end.

procedure verb_phrase;

begin

вызвать процедуру verb для получения представления глагола; if с глаголом связано дополнение then begin вызвать процедуру noun_phrase для получения представления

дополнения;

с помощью объединения и ограничения связать понятие, определяемое дополнением, с дополнением, соответствующим сказуемому end end.

procedure verb;

begin

получить падежный фрейм для глагола end.

procedure noun;

begin

получить понятие для существительного end.

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

С помощью этих процедур для иерархии понятий, показанной на рис. 13.10, и падежных фреймов, представленных на рис. 13.11, можно описать действия семантического интерпретатора, предпринимаемые для построения семантического представления предложения "The dogs like a man" на основе дерева грамматического разбора, изображенного на рис. 13.9. Последовательность этих действий проиллюстрирована на рис. 13.12.

Числа в скобках в следующем списке соответствуют порядковым номерам на рис. 13.12.

1. Сначала для узла, соответствующего предложению, вызывается процедура

sentence.

Процедура sentence вызывает процедуру noun__phrase.

Процедура noun_phrase вызывает процедуру noun.

Процедура noun возвращает понятие, связанное с существительным dog (1 на

рис. 13.12).

Поскольку артикль является определенным, процедура noun_phrase связывает маркер #1 с этим понятием (2) и возвращает данное понятие процедуре sentence.

Процедура sentence вызывает процедуру verb__phrase.

Глава 13. Понимание естественного языка 583

Рис. 13.12. Построение семантического представления на основе дерева грамматического разбора

Процедура verb_phrase вызывает процедуру verb, позволяющую получить падежный фрейм для глагола like (3).

Процедура verb_phrase вызывает процедуру noun_phrase, которая в свою

очередь вызывает процедуру noun для получения понятия, связанного с существительным man (4).

Поскольку артикль является неопределенным, процедура noun_phrase определяет это понятие как общее (5).

Процедура verb_phrase ограничивает понятие entity в падежной рамке и

объединяет его с понятием, соответствующим существительному man (6). Эта

структура возвращается процедуре sentence.

Процедура sentence объединяет понятие dog: #1 с узлом experiencer падежной рамки (7).

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

Генерация языковых конструкций - это связанная задача, решаемая с помощью программ понимания естественного языка. Генерация английских выражений требует построения семантически корректного выхода на основе внутреннего представления значе­ния. Например, отношение agent означает связь подлежащее-сказуемое между двумя понятиями. С помощью простых подходов соответствующие слова присоединяются к го­товым шаблонам (template) предложений. Эти шаблоны можно рассматривать в качестве образцов предложений или их фрагментов, в частности, глагольной и именной конструк-

584

Часть V. Дополнительные вопросы решения задач искусственного интеллекта

ций. Выходной результат строится путем прохода по концептуальному графу и комбинирования этих фрагментов. Более сложные подходы к генерированию языковых конст­рукций связаны с использованием грамматик преобразования для отображения значения в диапазон возможных предложений [Winograd, 1972], [Allen, 1987].

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

13.4. Стохастический подход к анализу языка

13.4.1. Введение

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

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

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

Большинство людей знакомы с этой задачей со времен изучения грамматики в школе. Для каждого слова в предложении необходимо определить, к какой части речи оно относится. Если слово является глаголом, то можно указать его наклонение, а также переход­ность. Для существительных нужно определить число. Сложности возникают при обработ­ке слов типа swing. В выражении "output potential swing" (перепад выходного напряжения) это слово выступает в роли существительного, а в выражении "swing at the ball" (ударить по мячу) - в роли глагола. Приведем фразу Пикассо и выделим в ней части речи.

Art is a lie that lets us see the truth.

Сущ. Глагол Артикль Сущ. Местоим. Глагол Местоим. Глагол Артикль Сущ.

Глава 13. Понимание естественного языка интеллекта 585

удастся сохранить все значения вероятностей, их достаточно трудно оценить. Оценка обычно делается эмпирически путем подсчета количества вхождений события в размечен­ном вручную обучающем множестве. Если это событие встречается лишь несколько раз, то оценка его вероятности будет неточной. Таким образом, легче оценить вероятность P(cat|the), чем P(cat|the dog chased the), поскольку последняя фраза встречается в обучающем множестве гораздо реже. И, наконец, нахождение цепочки дескрипторов, мак­симизирующей структуру вида (2), займет очень много времени (это будет показано ниже). Поэтому сначала найдем некоторую удовлетворительную аппроксимацию (2). Введем два основных предположения:

P(t1|t1,, ..., ti-1,w1,…,wi-1) соответствует P(t1| ti-1)

и

P(w1,|t, ti-1 w1, ..., wi-1) соответствует Р(w1|ti-1).

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

(3)

Соотношение (3) гораздо удобнее с практической точки зрения, поскольку входящие

в него вероятности можно легко оценить и хранить. Напомним, что (3) - это лишь аппроксимация выражения P(t1|t1, ... , tn|w1, … ,wn), которую необходимо максимизировать

путем выбора дескрипторов t1, ..., tn. К счастью, это можно сделать с помощью алгоритма динамического программирования, известного под названием алгоритма Витерби (Viterbi algorithm) [Viterbi, 1967], [Forney, 1973]. Алгоритм Витерби вычисляет вероят­ность последовательности дескрипторов t2 для каждого слова в предложении, где t - число возможных дескрипторов. На данном шаге рассматриваемая последовательность дескрипторов может быть записана в следующем виде.

article article {best tail} article verb {best tail}

…

article noun {best tail}

…

noun article {best tail}

…

noun noun {best tail},

где {best tail} - наиболее вероятная последовательность дескрипторов, найденная динамически для оставшихся n-2 слов и данного дескриптора n-1.

Для каждого возможного значения дескриптора под номером n-1 и дескриптора под номером л существует своя запись в этой таблице (получается t2 последовательностей дескрипторов). На каждом шаге алгоритм находит максимальные вероятности и добавляет по одному дескриптору к каждой последовательности {best tail}. Этот алгоритм гарантирует нахождение последовательности дескрипторов, максимизирующей соотно­шение (3) за время O(t2 s), где t - число дескрипторов, s - количество слов в предло­жении. Если вероятность Р(ti) обусловлена последними л дескрипторами, а не последни­ми двумя, то работа алгоритма Витерби завершится за время O(tn s). Отсюда видно, по­чему зависимость от слишком большого числа предыдущих значений увеличивает время нахождения максимума.

Глава 13. Понимание естественного языка 587

К счастью, аппроксимация (3) является удовлетворительной. Для 200 возможных дескрип­торов и большого обучающего множества, предназначенного для оценки вероятностей, с по­мощью этого метода можно расставить дескрипторы с точностью 97%, что сопоставимо с точностью работы человека. Удивительная точность марковской аппроксимации наряду с ее простотой делают эту модель пригодной для использования во многих приложениях. Напри­мер, в большинстве систем распознавания речи используются так называемые модели три­грамм (trigram), обеспечивающие некоторые "грамматические знания" для прогнозирования слов с учетом уже сказанного. Модель триграмм - это простая марковская модель, в которой вероятность текущего слова обусловлена двумя предыдущими словами. При работе с такими моделями используется алгоритм Витерби и другие описанные выше приемы. Более подроб­ная информация по этому вопросу содержится в [Jurafsky и Martin, 2000].

13.4.3. Подход на основе дерева решений

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

The policy announced in December by the President guarantees lower taxes.

(Политика, провозглашенная в декабре президентом, гарантирует снижение налогов.)

На самом деле действующим лицом в данном случае является President, однако программа на основе марковской модели, вероятнее всего, назовет действующим лицом policy, a announced - глаголом в действительном залоге. Естественно, если бы программа могла задавать вопросы типа "Описывает ли данное существительное неодушев­ленный предмет?" или "Встречается ли слово by на несколько слов раньше рассматри­ваемого существительного?", то она определила бы действующее лицо гораздо точнее.

Напомним, что задача расстановки дескрипторов эквивалентна максимизации выражения (2), т.е.

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

Эту проблему можно решить несколькими путями. Во-первых, марковский подход можно комбинировать с методами грамматического разбора, описанными в предыдущих разделах этой главы. Во-вторых, можно находить вероятности, обусловленные ответами "Да" и "Нет", с помощью алгоритма ID3 (который подробно описан в разделе 9.3, а его реализация на языке LISP - в разделе 15.13) или подобного ему алгоритма. В алгоритме ID3 среди большого множества вопросов выбираются только те, которые обеспечивают хорошую оценку вероятности. В более сложных задачах обработки естественного языка, в том числе в задаче грамматического разбора, деревья решений, на которых основывается работа алгоритма ID3, оказываются более предпочтительными, чем марковские мо­дели. Далее будет показано, как использовать алгоритм ID3 для построения дерева ре­шений в задаче грамматического разбора.

588 Часть V. Дополнительные вопросы решения задач искусственного интеллекта

Выше уже упоминался вопрос "Описывает ли данное существительное неодушевленный предмет?". Подобные вопросы можно задавать только в том случае, если известно, какие существительные описывают одушевленные или неодушевленные предметы. На самом деле существует способ автоматического разделения множества слов на эти классы. Этот прием получил название кластеризации взаимной информации (mutual information clustering). Взаимная информация, распределенная между двумя случайными величинами X и Y, определяется следующим образом:

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

Например, пусть изначально существуют слова cat, kitten, run и green. На первом шаге алгоритма строятся множества

{cat}, {kitten}, {run}, {green}.

Скорее всего, вероятность появления некоторого слова после слова cat примерно равна вероятности появления этого слова после слова kitten. Другими словами,

P(eats | cat)»P(eat | kitten),

P{meows|cat}»P{meows|kitten).

Таким образом, для случайных величин XI, Х2, Y1, Y2, при которых

X1={{cat}, {kitten}, {run}, {green}},

Y1 =слово, следующее за Х1,

X2={{cat, kitten}, {run}, {green}}, Y2=слово, следующее за Х2.

Общей информации в Х2 и Y2 не намного меньше, чем в XI и Y1. Следовательно, слова cat и kitten с большой вероятностью можно сгруппировать. Если продолжить эту процедуру до получения комбинаций всех возможных классов, то получится бинарное дерево. Тогда словам, расположенным в листовых узлах этого дерева, можно присвоить двоичные коды (bit code), описывающие путь перемещения по дереву до достижения этого слова. Такие коды отражают семантическое значение слов. Например,

cat=01100011, kitten=01100010.

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

Такая новая кодировка слов словаря позволяет анализатору более эффективно задавать вопросы. Заметим, что при кластеризации контекст не принимается во внимание, поэтому слово book (книга) может быть классифицировано как "напоминающее сущест­вительное", хотя в предложении "book a flight" (заказать билет на самолет) его необхо­димо рассматривать как глагол.

Глава 13. Понимание естественного языка 589

13.4.4. Грамматический анализ и другие приложения стохастического подхода

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

Использование статистических методов в задачах грамматического разбора впервые было связано с проблемой неопределенности, возникающей в связи с существованием нескольких возможных интерпретаций данного предложения и необходимостью выбора наилучшей. Например, предложение "Print the file on the printer" (Напечатай файл на принтере) может быть представлено в виде двух деревьев, показанных на рис. 13.13.

Предложение

590 Часть V. Дополнительные вопросы решения задач искусственного интеллекта