Часть 3.

12.6. Упражнения

Приведите предикаты, описанные в разделе 2.4, к дизъюнктивной форме и используйте процедуру опровержения разрешения для ответа на запрос о том, должен ли конкретный инвестор выполнять investment(combination)?

С помощью процедуры резолюции докажите утверждение из упражнения 12 к главе 2.

Используйте процедуру резолюции для ответа на запрос из примера 3.3.4.

В главе 5 представлена упрощенная форма игры "хода конем". Приведите правило

path3 к дизъюнктивной форме и с помощью процедуры резолюции получите ответ

на запрос path3(3, 6). Затем воспользуйтесь рекурсивным вызовом процедур в дизъюнктивной форме.

Как можно использовать процедуру резолюции для реализации поиска в продукционной системе?

Как с помощью резолюции реализовать рассуждения от данных? Используйте этот

метод для определения пространства поиска в упражнении 1. Какие проблемы могут

возникнуть в задачах, где пространство поиска достаточно велико?

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

волка, козы и капусты из раздела 14.3.

Воспользуйтесь методом резолюции для решения задачи из [Wos и др., 1984]. Условия задачи следующие. Четыре человека - Роберта, Тельма, Стив и Пит - работают на восьми различных работах. Каждый из них работает ровно на двух работах.

Они занимают следующие должности: руководитель, охранник, санитар, телефонист,

полицейский, учитель, актер и боксер. Санитар - это мужчина. Муж руководите

ля - телефонист. Роберта - не боксер. Пит не имеет высшего образования. Робер-

Глава 12. Автоматические рассуждения 559

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

9. Приведите два примера гиперрезолюции, где ядро состоит не менее чем из четырех литералов.

Напишите демодулятор для выражения sum, приводящий дизъюнктивные выражения вида equal(ans, sum(5, sum(6, minus(6)))) к виду equal(ans, sum(5, 0)). Разработайте демодулятор для приведения этого результата к виду equal(ans, 5).

Постройте "каноническое множество" из шести типов семейных отношений. Напишите демодуляторы для приведения различных форм отношений к канонической форме. Например, "брат матери" - это "дядя".

Примените три стратегии опровержения из подраздела 12.2.4 для решения задачи

"счастливого студента", проиллюстрированной на рис. 12.4.

Приведите следующее выражение из предикатной формы к дизъюнктивной

14. Создайте граф И/ИЛИ для решения следующей задачи на основе данных.

Факт: -,d(F)v[b(0Ac(0].

Правила: -,d(X)->->a(X) и Ь(У)->е(У) и д(И/)<-с(И/). Доказать: -,a(Z)ve(Z).

Докажите, что стратегия линейной входной формы не является полной в смысле оп

ровержения.

Создайте граф И/ИЛИ для решения следующей задачи и объясните, почему невозможно получить целевое выражение.

Используйте процедуры факторизации и резолюции для опровержения следующих

выражений p(X)vp(f(Y)) и -p(W)v-ip(f(Z)). Постарайтесь построить опровержение

без факторизации.

Альтернативной семантической моделью для логического программирования является Flat Concurrent PROLOG [Shapiro, 1987]. Сравните эту модель с семантикой языка PROLOG, описанной в разделе 12.3.

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

Понимание

естественного

языка

Чем объяснить потребность в словах? - Теренс (Terence)

До меня доходит

Какой-то ураган в твоих словах,

Но не слова.

- Вильям Шекспир (William Shakespeare), Отелло

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

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

Например, рассмотрим следующие строки из восемнадцатого сонета Шекспира.

"Сравню ли с летним днем твои черты? Но ты милей, умеренней и краше. Ломает буря майские цветы, И так недолговечно лето наше!"

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

Чем объясняется необычайная притягательность произведений Шекспира? Чтобы по

нять эти строки, необходимо знать, что такое человеческая любовь и каковы ее соци

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

Почему Шекспир сравнивает свою возлюбленную с летним днем? Означает ли это,

что она длится 24 часа и при общении с ней кожа покрывается летним загаром, или

она ассоциируется у автора с ощущением тепла и летней красоты?

Какие выводы можно сделать из этого фрагмента? Смысл сказанного явно не от

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

Например, буря и скоротечность лета ассоциируются с перипетиями человеческой

жизни и любви.

Как человек понимает метафоры? Слова не просто описывают совокупность объ

ектов, как ячейки в таблице. Смысл этих стихов состоит в сопоставлении характе

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

писаны обоим объектам, а какие нет, и главное, почему некоторые свойства под

черкиваются, а другие даже не упоминаются?

И, наконец, должна ли компьютерная система понимания языка знать, что такое

"ямб"? Как компьютер ответит на вопрос, о чем эти стихи?

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

Рассмотрим второй пример, взятый из объявления о вакансиях на факультете компьютерных наук.

"Факультет компьютерных наук университета Нью-Мексико... проводит конкурс на замещение двух должностей профессора. Требуются специалисты в следующих областях: программное обеспечение, в том числе анализ, проектирование и средства разработки...; системы, включая архитектуру, компиляторы, сети...

Кандидаты должны иметь степень доктора наук по специальности...

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

В связи с этим объявлением возникает несколько вопросов.

Как читатель узнает, что это объявление касается вакантных должностей именно

этого факультета?

Какие языки и средства программирования необходимо знать для работы в универ

ситете (они явно не указаны в объявлении)? Человек, хорошо знакомый с процес

сом преподавания в университете, сможет понять, что речь идет о языках Cobol,

PROLOG и UML.

Какое отношение к этому объявлению имеют сведения о международных проектах

и связях с другими лабораториями?

Как компьютер поймет, о чем это объявление? Что ему необходимо знать, чтобы

направить объявление по Internet кандидату наук, который занимается поиском ра

боты в Web?

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

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

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

В первых системах искусственного интеллекта разработчики старались ограничить предметную область системы (поскольку для успешной работы системы требуется знание предметной области) и создавали приложения, работающие в минимальной предметной области. К числу таких систем относится SHRDLU [Winograd, 1972], которая могла работать с блоками различной формы и цвета и с помощью "руки" перемещать указанный блок (рис. 13.1).

Система SHRDLU могла отвечать на заданные на английском языке вопросы типа "Что находится на красном блоке?" или выполнять запросы вида "Поместите зеленую пирамиду на красный брусок". Она понимала местоимения, например, могла обработать запрос: "Есть ли здесь красный блок? Подними его". Она даже понимала эллипсис, в частности "Какого цвета блок находится на синем бруске? Какой формы?". Поскольку мир блоков очень прост, то система была снабжена полной базой знаний о нем. Взаимодействие с этим "миром" не требует знания таких общих понятий, как время, возможности, убеждения и разработки приемов представления этих знаний. Благодаря ограниченности предметной области в системе SHRDLU достигнута интеграция синтаксиса и семантики. Ее пример доказывает, что при достаточных знаниях о предметной области компьютерная система может эффективно работать с естественным языком.

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

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

В разделе 13.1 представлен символьный подход к пониманию языка. Раздел 13.2 посвящен синтаксическому анализу, в разделе 13.3 рассматриваются вопросы моделирования синтаксиса и семантики. В разделе 13.4 представлен стохастический подход к выявлению закономерностей в языковых выражениях. И наконец в разделе 13.5 рассматриваются несколько приложений для систем понимания естественного языка: ответы на вопросы, получение информации из базы данных, выполнение Web-запросов и анализ текстовой информации.

13.1. Разбор языка: символьный анализ

13.1.1. Введение

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

Просодия (prosody), к которой относятся анализ ритма и интонации языка. Этот

уровень анализа достаточно сложно формализуем, поэтому им зачастую пренебре

гают. Однако его значение очевидно. Сила ритма и интонации наиболее ярко про

является в поэзии и религиозных песнопениях. Ритмика языка играет важную роль

также в детских играх и колыбельных.

Фонология (phonology) - наука о звуках и их комбинациях в языковых структурах.

Эта область лингвистики играет важную роль в компьютерном распознавании и

генерации речи.

Морфология (morphology) - анализ компонентов (морфем), из которых состоят

слова. К этой области относятся вопросы правил формирования слов, в том числе

использования префиксов (в английском языке ип-, поп-, anti- и др.) и суффиксов (-

ing, -ly и др.) для модификации значения корня слова. Морфологический анализ

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

времени глагола, числа и части речи.

Синтаксический анализ (syntax) связан с изучением правил сочетания слов в от

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

и генерации предложений. Эта область наиболее формализована, и поэтому ус

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

Семантика (semantics) изучает значение слов, фраз и предложений, а также спосо

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

Прагматика (pragmatics) - наука о способах использования языка и его воздейст

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

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

слово "Да" является неудовлетворительным ответом на вопрос "Знаете ли вы, который час?".

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

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

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

13.1.2. Стадии анализа языка

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

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

Вторая стадия - это семантическая интерпретация (semantic interpretation), в результате которой формируется представление содержания текста. На рис. 13.2 этот процесс показан в виде концептуального графа. К другим наиболее часто используемым представлениям относятся концептуальные зависимости, фреймы и логические представления. В процессе семантической интерпретации используются знания о значении слов и лингвистической структуре, в том числе синонимы существительных или глаголов. На рис. 13.2 показано, что в программе используется знание значения слова kiss (целовать) для добавления в качестве используемого по умолчанию инструмента значения lips (губы). На этой стадии также выполняется проверка семантической согласованности. Например, определение глагола kiss может включать ограничения, связанные с тем, что человек может целовать только человека, т.е. Тарзан целует Джейн и (обычно) не целует обезьяну Читу.

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

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

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

Эти стадии присутствуют во всех системах, хотя могут быть по-разному реализованы в виде программных модулей. Например, во многих программах дерево разбора не строится в явном виде. Вместо этого напрямую генерируется внутреннее семантическое представление. Тем не менее оно неявно участвует в разборе предложения. Инкрементальный синтаксический разбор (incremental parsing) [Allen, 1987] - это типичный при-

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

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

13.2. Синтаксический анализ

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

В главах 3 и 14 вводится понятие правил вывода (rewrite rule), используемых для определения грамматики. Перечисленные ниже правила определяют грамматику для простых транзитивных предложений типа "Человек любит собаку". Для удобства эти правила перенумерованы.

sentence?noun_phrase verbjphrase

nounj3hrase«noun

noun_phrase«article noun

verb_phrase«verb

verb_phrase«verb noun_phrase

article«a

article«the

noun«man

noun«dog

verb«likes

verb«bites

В правой части правил 6-11 содержатся английские слова. Эти правила формируют словарь доступных слов, которые могут появляться в предложении. Эти слова являются терминалами (terminal) грамматики и определяют лексикон (lexicon). Термины, определяющие лингвистические понятия более высокого уровня (sentence, noun_phrase), называются нетерминальными и выделяются стилем формул. Заметим, что терминалы не встречаются в левой части правил.

Корректное предложение - эта любая строка терминалов, которую можно разделить на части с помощью этих правил. Трансформация начинается с нетерминального символа sentence и в результате серии последовательных подстановок, определенных правилами грамматики, приводит к формированию строки терминалов. Корректная подстановка - это замена символа, соответствующего левой части правила, символом из правой части этого правила. На промежуточных стадиях вывода строки могут включать как терминалы, так и нетерминальные выражения. Такое представление называется сентенциальной формой (sentential form). Трансформация предложения 'The man bites the dog" выглядит следующим образом (табл. 13.1).

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

Это пример трансформации сверху вниз (top-down derivation). Она начинается с символа sentence и завершается строкой терминалов. Трансформация снизу вверх начинается со строки терминалов, включает замену элементов правой части правила соответствующими элементами из левой части и завершается символом sentence.

Трансформацию можно представить в виде дерева, получившего название дерева грамматического разбора (parse tree), в котором каждый узел - это символ из набора правил грамматики. Внутренние узлы дерева - нетерминальные. Каждый узел и его потомки - это левая и правая части некоторого правила грамматики соответственно. Листовые узлы - это терминалы, а символ sentence - корень дерева. Дерево разбора для предложения "The man bites the dog" показано на рис. 13.3.

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

Разбор предложений - это задача построения трансформации или дерева грамматического разбора для входной строки на основе формального определения грамматики. Алгоритмы грамматического разбора делятся на два класса: анализаторы сверху вниз (top-down parser), которые начинают свою работу с высокоуровневого символа sentence и строят дерево, листья которого составляют целевое предложение, и анализаторы снизу вверх (down-top parser), работа которых начинается со слов предложения (терминалов), и в результате последовательных операций формируется символ sentence.

Основная трудность решения задачи грамматического разбора состоит в выборе из существующего набора правила, которое следует использовать на каждом шаге трансформации. При неправильном выборе анализатор может не распознать корректно предложение. Например, при разборе предложения "The dog bites" методом снизу вверх в результате применения правил 7, 9 и 11 будет получена строка article noun verb. После этого ошибочное применение правила 2 генерирует строку article noun_prhase verb, которую нельзя привести к символу sentence. На самом деле анализатор должен использовать правило 3. Аналогичные проблемы возникают и при разборе сверху вниз.

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

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

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

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

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

Анализатор на основе сети переходов представляет грамматику в виде набора конечных автоматов или сетей переходов. Каждая сеть соответствует одному нетерминальному элементу грамматики. Дуги в таких сетях помечены терминальными или нетерминальными символами. Все пути в такой сети, ведущие от начального состояния к конечному, соответствуют некоторому правилу для нетерминальных элементов. Последовательность меток дуг такого пути - это последовательность символов в правой части правила. Грамматика, рассмотренная в подразделе 13.2.1, может быть описана с помощью сетей переходов, показанных на рис. 13.4. Если грамматика содержит несколько правил для нетерминальных элементов, то в соответствующей сети содержится несколько путей от начала к цели. Например, правила noun_phrase«noun и nounjphrase«article noun изображаются в виде различных путей в сети noun_phrase на рис. 13.4.

569

Рис. 13.4. Определение сети переходов простой грамматики английского языка

Поиск успешного перехода в сети для нетерминального элемента состоит в замене этого элемента содержимым правой части грамматического правила. Например, для разбора предложения анализатор должен найти переход в сети предложения sentence. Он начинается с исходного состояния (Sinitial), включает переход noun_phrase, затем пере­ход verbjDhrase и завершается в конечном состоянии Sfinal. Этот процесс эквивалентен замене исходного символа sentence парой символов noun_phrase и verb_phrase.

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

Рассмотрим простое предложение "Dog bites" ("Собака кусается"). Первые шаги разбора этого предложения показаны на рис. 13.5.

570

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

4S 4. Вызвать 6. Вернуть

Анализатор начинает свою работу с сети sentence и пытается совершить переход

по дуге с меткой noun_phrase. Для этого он переходит к сети noun_phrase.

В сети noun_phrase анализатор сначала пытается совершить переход по дуге

article. Для этого он переходит к сети article.

В сети article нельзя найти путь к конечному узлу, поскольку ни одна из дуг не

помечена первым словом предложения "dog". В результате безуспешной попытки

поиска пути анализатор возвращается к сети noun_phrase.

Анализатор пытается пройти по дуге noun в сети noun_phrase и переходит к

сети noun.

Проход по дуге с меткой "dog" завершается успешно, а именно она соответствует

первому слову входного потока.

Результат поиска в сети noun положителен. Это значит, что дуга с меткой noun в

сети noun_phrase ведет к конечному состоянию.

Сеть nounjphrase возвращает успешный результат сети самого верхнего уровня,

разрешая переход по дуге noun_phrase.

Аналогичная последовательность шагов приводит к разбору части предложения

verb_phrase.

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

571

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

function parse(символ_грамматики);

begin

сохранить указатель на текущую позицию во входном потоке;

case

символ_грамматики является терминальным:

if символ_грамматики соответствует следующему слову во

входном потоке

then return(success)

else begin

переустановить входной поток;

return(failure)

end;

символ_грамматики является нетерминальным:

begin

перейти к сети переходов, соответствующей символу

грамматики;

состояние:=начальное состояние сети;

if transition(состояние) возвращает success

then return(success)

else begin

переустановить входной поток;

return(failure)

end

end;

end end.

function transition(текущее_состояние);

begin

case

текущее_состояние - это конечное состояние:

return(success)

текущее_состояние - это не конечное состояние:

while существуют непроверенные переходы из текущего состояния

do begin

символ_грамматики:= метка следующего непроверенного

перехода;

if parse(символ_грамматики) возвращает success

then begin

следующее_состояние:=состояние в конце

перехода;

if transition(следующее_состояние)

возвращает success

then return(success)

end

end

572

return(failure)

end

end.

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

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

При каждом вызове функции parse, параметром которой является терминальный

символ, соответствующий следующему символу входного потока, она должна воз­

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

Если функция parse вызывается для нетерминального значения параметра

символ_грамматики, она вызывает функцию transition. При успешном завер­

шении функции transition она возвращает упорядоченный набор поддеревьев

(который будет описан ниже). Функция parse строит на их основе дерево, корнем ко­

торого является символ_грамматики, а дочерними элементами- поддеревья, воз­

вращаемые функцией transition.

При поиске пути в сети функция transition вызывает функцию parse для

метки каждой дуги. При успешном завершении функция parse возвращает дере­

во, являющееся результатом разбора соответствующего символа. Функция tran­

sition сохраняет эти поддеревья в виде упорядоченного набора и при нахожде­

нии пути в сети возвращает упорядоченный набор деревьев разбора, соответст­

вующий последовательности меток дуг этого пути.

13.2.3. Иерархия Хомского и контекстно-зависимые грамматики

В подразделе 13.2.1 была определена малая часть правил английского языка на осно­ве контекстно-независимой грамматики (context-free grammar). В такой грамматике в левой части правил может содержаться только по одному нетерминальному символу. Следовательно, правило можно применять к любому вхождению этого символа, независимо от контекста. Хотя контекстно-независимые грамматики зарекомендовали себя как мощное средство определения языков программирования и других формализмов в ком­пьютерных науках, есть основания считать, что сами по себе они недостаточно эффек­тивны для представления правил построения естественного языка. Например, рассмот­рим, что произойдет, если добавить к описанной в подразделе 13.2.1 грамматике сущест­вительные и глаголы не только в единственном, но и во множественном числе:

Noun«men noun«dogs, verb«bite, vегЬ«like.

С помощью полученной грамматики можно осуществлять грамматический разбор предложений вида "The dogs like the men" и "A men likes a dogs", в которых артикли и множественное число употребляются некорректно. Анализатор допускает такие предло-

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

жения, поскольку существующие правила не используют контекст для координации применимости единственного и множественного числа. Например, правило, определяющее предложение sentence как именную конструкцию noun_phrase, за которой следу­ет глагольная verbjphrase, не требует согласованности числа существительного и гла­гола. Та же проблема согласованности возникает при использовании артиклей.

Языки, определяемые контекстно-независимыми грамматиками, составляют лишь один из классов иерархии формальных языков. Такая иерархия называется иерархией Хомского (Chomsky hierarchy) [Hopcroft и Ullman, 1979], [Chomsky, 1965]. На нижнем уровне этой ие­рархии находится класс регулярных языков (regular language). Регулярным называется язык, грамматика которого может быть определена с использованием конечных автоматов. Хотя регулярные языки активно используются в компьютерных науках, они недостаточно эффек­тивны для представления синтаксиса большинства языков программирования.

Контекстно-независимые языки (context-free language) в иерархии Хомского расположены на уровень выше регулярных языков. Они определяются с помощью правил вы­вода (подраздел 13.2.1). В левой части контекстно-независимых правил может распола­гаться только один нетерминальный символ. Класс контекстно-независимых языков можно анализировать с помощью сетей переходов. Интересно отметить, что если в ана­лизаторе на основе сетей переходов не допускать рекурсии (т.е. дуги помечать только терминальными символами, не приводящими к "вызову" другой сети), то класс таких языков будет соответствовать множеству регулярных выражений. Таким образом, регу­лярные языки - это строгое подмножество контекстно-независимых языков.

Контекстно-зависимые языки (context-sensitive language) составляют строгое супермно­жество контекстно-независимых языков. Они определяются с помощью контекстно-зависимых грамматик, которые допускают использование нескольких символов в левой час­ти правила для определения контекста применения этого правила. Таким образом, гаранти­руются глобальные ограничения, в частности, согласованность единственного и множествен­ного числа. Единственным ограничением для правил контекстнозависимой грамматики явля­ется непревышение правой части правила размера его левой части [Hopcroft и Ullman, 1979].

Четвертым классом, составляющим супермножество контекстно-зависимых языков, является класс рекурсивно-перечислимых языков (recursively enumerable language). Такие языки определяются с помощью неограниченных продукционных правил. Поскольку эти правила не такие жесткие, как контекстно-зависимые, класс рекурсивно-перечислимых языков является строгим супермножеством контекстно-зависимых языков. Этот класс не представляет интереса для определения синтаксиса естественного языка, хотя тоже играет важную роль в теории компьютерных наук. Остальная часть этой главы будет посвя­щена анализу английского языка, как относящегося к классу контекстно-зависимых.

Простая контекстно-независимая грамматика для предложений вида article noun verb (артикль существительное глагол), в которых согласовано единственное и множественное число артиклей и существительных, а также существительных и глаголов, имеет вид

sentence<->noun_phrase verb_phrase,

noun_phrase<->article number noun,

noun _phrase<->number noun,

number<->singular,

number<-> plural,

article singular<->a singular,

article singular«the singular,

article plural<->some plural,

article plural<->the plural,

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

singular noun<->man singular,

singular noun<->dog singular,

plural noun<->men plural,

plural noun<->dogs plural,

singular verb_phrase<->singular verb,

plural verb_phrase<->riplural verb,

singular verbi«likes,

singular verfo<->b/fes,

plural verb<->like,

plural verbir<->bite.

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

sentence.

nounjphrase verb_phrase.

article plural noun verb_phrase.

The plural noun verb_phrase.

The dogs plural verb_phrase.

The dogs plural verb.

The dogs bite.

Аналогично контекстно-зависимую грамматику можно использовать для проверки выполнения синтаксических соглашений. Например, добавив к данной грамматике нетерминальный символ act_of_biting, можно запретить использование предложений вида "Man bites dog" (человек кусает собаку). Этот нетерминальный символ можно использовать для предотвра­щения построения предложений, в которых действие bites выполняет существительное man.

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

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

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

зависимой грамматики, необходимой для описания форм числа (единственного и

множественного) и лица (первого, второго и третьего), а также всех остальных

форм соглашений, принятых в английском языке.

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

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

При попытке описать более сложные соглашения и обеспечить семантическую со­

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

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

Контекстно-зависимые грамматики не решают проблемы построения семантиче­

ского представления значения текста. Анализатор, который просто принимает или

отвергает предложение, никому не нужен. Он должен возвращать эффективное

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

В следующем разделе будут рассмотрены расширенные сети переходов ATN (augmented transition network), с помощью которых можно определять контекстно-