Часть 5.

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

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

Разбор без учета грамматики дает достаточно хорошие результаты. В экспериментах по сравнению его эффективности с результатами работы грамматических анализаторов на одинаковом множестве предложений разбор без учета грамматики обеспечивает 78% эффективности, а с учетом - 69% [Magerman, 1994]. Эти результаты достаточно хороши, но их нельзя считать выдающимися. Гораздо важнее другое. Описание грамматики для тради­ционного анализатора требует примерно десяти лет педантичной работы грамотного лин­гвиста, в то время как анализатор без учета грамматики, не использующий жестко закоди­рованной лингвистической информации и основанный лишь на сложных математических моделях, может сам извлекать необходимую информацию из обучающих данных. Более подробная информация по этому вопросу содержится в [Manning и Schutze, 1999].

Понимание речи, преобразование речи в текстовую информацию и распознавание рукописного текста - это еще три области, имеющие богатую историю использования стохас­тических методов для моделирования языка. В этих областях для прогнозирования сле­дующего слова чаще всего используется статистический метод на основе модели триграмм. Эффективность этой модели объясняется ее простотой. С ее помощью можно предсказать следующее слово по двум предыдущим. В настоящее время специалисты в области стати­стической обработки языка стараются сохранить простоту и легкость использования этой модели при добавлении грамматических ограничений и более долгосрочных зависимостей. Этот новый подход получил название метода грамматических триграмм (grammatical tri-gram). Грамматические триграммы содержат информацию об основных связях между па­рами слов (такими как подлежащее-сказуемое, артикль-существительное или сказуемое-дополнение). Совокупность этих ассоциаций образует грамматику связей (link grammar). Такую грамматику построить гораздо легче, чем традиционную. При этом для нее доста­точно эффективными оказываются вероятностные методы.

В работе [Berger и др., 1994] описана статистическая программа Candide, осуществляющая перевод французского текста на английский язык. В ней для разработки вероят­ностной модели процесса перевода использованы как статистические методы, так и тео­рия информации. Для ее обучения требуется только большое множество пар предложе­ний на французском и английском языке. При этом результаты работы программы сопоставимы (а в некоторых случаях и превосходят их) с результатами коммерческой программы Systran [Berger и др., 1994]. Интересно отметить, что в процессе перевода система Candide не выполняет традиционного грамматического разбора. В ней исполь­зуются только грамматические триграммы и грамматика связей.

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

Можно указать несколько областей, в которых стохастические методы моделирования языка еще не применялись, но могут дать хорошие результаты. К таким областям относятся задачи извлечения информации или получения определенного количества конкретной информации из рукописного текста, а также поиск в Web. Статистический подход к обработке естественных языков более подробно описан в работах [Jurafsky и Martin, 2000] и [Manning и Schutze, 1999].

13.5. Приложения задачи анализа естественного языка

13.5.1. Обучение и ответы на вопросы

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

После построения расширенного представления текста программа может интеллектуально отвечать на вопросы о его содержании. Вопрос приводится к внутреннему представлению и проверяется его соответствие расширенному представлению текста. Рассмотрим пример, показанный на рис. 13.2. Эта программа может прочесть предложение 'Tarzan kissed Jane" (Тарзан поцеловал Джейн) и построить его расширенное представление.

Допустим, программе задан вопрос "Who loves Jane?" (Кто любит Джейн?). Вопросительное слово определяет сущность вопроса. При ответе на вопрос со словом who (кто) требуется указать агента действия. Вопросы what (что) требуют найти объект действия. Вопросы how (как) подразумевают определение средств выполнения действия и т.д. Граф для вопроса "Who loves Jane?" показан на рис. 13.14. Узел агента на этом графе помечен вопросительным знаком, указывающим на то, что целью вопроса является определение агента. Затем эта структура объединяется с расширенным представлением исходного текста. Понятие, связанное с понятием person: ? на графе запроса, дает ответ на этот вопрос: 'Tarzan loves Jane" (Тарзан любит Джейн). В качестве примера реализации этого подхода можно рассматривать анализатор на основе рекурсивной семантической сети спуска, реализованный на языке PROLOG и описанный в разделе 14.9.

13.5.2. Интерфейс для базы данных

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

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

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

Задача такого интерфейса - перевести вопрос с естественного языка в формат стандартного запроса на языке базы данных. Например, с помощью такого интерфейса во­прос "Who hired John Smith?" (Кто нанял на работу Джона Смита?) можно перевести в запрос на языке SQL [Ullman, 1982] следующего вида.

SELECT MANAGER

FROM MANAGER_OF_HIRE

WHERE EMPLOYEE='John Smith'

При выполнении такого преобразования программа должна не просто выполнить исходный запрос. Ей также необходимо решить, где выполнять поиск в базе данных (отношение MANAGER_OF_HIRE), выбрать имя поля (MANAGER) и ограничения для дан­ного запроса (EMPLOYEE= 'John Smith'). Эта информация не содержится в исходном вопросе. Ее требуется найти в базе данных на основе сведений об организации этой базы и понимания содержания вопроса.

В реляционной базе данных (relational database) данные связаны отношениями между сущностями различных доменов. Предположим, что необходимо построить базу данных сотрудников, в которой нужно будет находить зарплату каждого сотрудника и определять, кто принял его на работу. Эта база данных должна состоять из трех доменов (domain) или наборов сущностей: менеджеров, сотрудников и зарплат. Эти данные мож­но связать двумя отношениями: employee_salary, связывающим сотрудника с его зарплатой, и manager_of _hire, связывающим сотрудника с его менеджером. В реляционной базе данных отношения обычно представляются в виде таблиц, в которых пере­числены экземпляры реализации отношения. Столбцам таблицы при этом присваиваются имена, которые называются атрибутами (attribute) отношения. На рис. 13.15 показаны таблицы для отношений employee_salary и manager_of_hire. Отношение man-ager_of_hire имеет два атрибута - employee и manager. Значения отношения - это пары сотрудник-менеджер.

Рис. 13.15. Два отношения из базы данных сотрудников

Если предположить, что каждому сотруднику соответствует уникальное имя, менеджер и зарплата, то имя сотрудника можно использовать в качестве ключа (key)

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

для атрибутов salary и manager. Один атрибут может выступать ключом для другого атрибута, если он уникальным образом определяет значения элементов это­го второго атрибута. В корректном запросе указывается целевой атрибут и задается значение или множество ограничений. База данных возвращает указанное значение целевого атрибута. Взаимосвязь между ключами и другими атрибутами можно изобразить графически разными способами, включая диаграммы "сущность-связь" (entity-relationship diagram) [Ullman, 1982] и диаграммы потоков данных (data flow diagram) [Sowa, 1984]. Оба эти подхода позволяют представить связь ключей с атрибутами в виде направленного графа.

Концептуальные графы можно расширить за счет включения диаграмм этих взаимосвязей [Sowa, 1984]. Отношение в базе данных, определяющее эту связь, обозначается с помощью ромба с меткой имени отношения. Атрибуты отношения - это понятия в кон­цептуальном графе, а стрелки направлены от ключей к другим атрибутам. Графы "сущность-отношение" для отношений employee_salary и manager_of_hire показаны на рис. 13.16.

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

Интерфейс взаимодействия с базой данных должен разобрать и интерпретировать запрос, представив его в виде концептуального графа, как было описано выше в этой главе. Затем этот граф объединяется с информацией из базы знаний с помощью операций объединения и ограничения. В нашем примере необходимо обрабатывать запросы вида: "Who hired John Smith?" (Кто нанял на работу Джона Смита) или "How much does John Smith earn?" (Сколько зарабатывает Джон Смит). Для каждого потенциаль­ного запроса нужно хранить граф, определяющий его сказуемое, и все связанные с этим вопросом диаграммы "сущность-связь". Запись базы знаний для глагола hire по­казана на рис. 13.17.

594

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

Семантический интерпретатор строит граф для запроса пользователя и объединяет его с соответствующей записью из базы знаний. Если существует граф "сущностьотношение", отражающий связь ключей с целью вопроса, то этот граф можно использовать для формирования запроса к базе данных. На рис. 13.18 показан граф запроса для вопроса "Who hired John Smith?" ("Кто нанял на работу Джона Смита?") и результат его объединения с элементом базы знаний, показанным на рис. 13.17. На рис. 13.18 также показан запрос SQL, сформированный на основе этого графа. Заметим, что имя соответствующей записи, целевое поле и ключ для запроса в вопросе на естественном языке не указаны. Эти сведения извлекаются из базы знаний.

Как видно из рис. 13.18, в исходном вопросе об агенте и объекте не содержится никакой информации, за исключением того, что они оба относятся к типу person. Чтобы объединить этот граф с элементом базы знаний, соответствующим глаголу hire, эти символы сначала необходимо привести к типу manager и employee соответственно. Для выполнения проверки типов в исходном запросе можно использовать иерархию типов. Если John smith не относится к типу employee, то вопрос должен быть отнесен к разряду некорректных, и программа должна это автоматически определить.

После построения расширенного графа запроса программа проверяет целевое понятие, помеченное символом ?, и определяет, что отношение manager_of_hire связывает ключ с этим понятием. Поскольку ключу соответствует значение John smith, то вопрос является корректным, и программа может сформировать соответствующий запрос к базе данных. Преобразование графа "сущность-связь" в запрос SQL или запрос на любом другом языке выполняется достаточно просто.

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

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

13.5.3. Извлечение информации и системы автоматического резюмирования для Web

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

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

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

Пример объявления о вакансиях в области компьютерных наук

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

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

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

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

Пример частично заполненного шаблона

Организация: факультет компьютерных наук университета Нью-Мексико Город: Albuquerque Штат: NM 87131

Описание вакансии: должность профессора

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

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

Сведения об организации: (текст прилагается)

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

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

Текст: факультет компьютерных наук университета Нью-Мексико... проводит

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

следующих областях...

Разметка и тэгирование: факультет/noun компьютерных/adj наук/noun...

Анализ предложения: факультет/subj проводит/verb конкурс/obj...

Извлечение: Организация: факультет компьютерных наук...

Описание вакансии: должность профессора

Объединение: Нью-Мексико=NМ...

Генерация шаблона: результат приведен выше.

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

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

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

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

Несмотря на значительный прогресс в области развития искусственного интеллекта, современные системы извлечения информации тоже не лишены проблем. Во-первых, можно значительно улучшить точность и робастность этих систем. Ошибки в процессе извлечения информации скорее всего связаны с недостаточным пониманием исходного текста. Во-вторых, построение систем извлечения информации для новой предметной области может оказаться достаточно сложным и ресурсоемким процессом [Cardie, 1997].

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

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

Тем не менее в настоящее время существует множество интересных приложений описанной технологии. В работе [Glasgow и др., 1997] представлена система поддержки страхования жизни. В [Soderland и др., 1995] описана система анализа медицинских карточек пациентов, применяемая в системе страхования. Известна программы анализа га­зетных публикаций и их резюмирования [MUC-5, 1994], системы автоматической классификации юридических документов [Holowczak и Adam, 1997] и программы извлечения информации из компьютерных списков вакансий [Nahm и Моопеу, 2000].

13.5.4. Использование алгоритмов обучения для обобщения извлеченной информации

Рассмотрим приложение, в котором многие описанные в этой главе идеи объединены с алгоритмами машинного обучения, изложенными в разделах 9.3 и 15.13. В работах [Cardie и Моопеу, 1999] и [Nahm и Моопеу, 2000] высказана идея о том, что процесс извлечения ин­формации из текста можно обобщить за счет применения алгоритмов машинного обучения.

Суть подхода достаточно проста. Полностью или частично заполненные шаблоны собираются с соответствующих Web-узлов. Эта информация сохраняется в реляционной базе данных, на основе которой с использованием алгоритмов обучения наподобие ID3 или С4.5 строятся деревья решений. Как известно из раздела 9.3, подобные деревья ре­шений могут отражать неявные связи в наборе данных. (Этот прием называют "добычей " данных - data mining.) Предполагается, что эти вновь выявленные зависимо­сти можно использовать для уточнения исходных шаблонов и базы знаний, принимаю­щей участие в процессе извлечения информации. Приведем пример информации, кото­рая может быть извлечена в процессе анализа вакансий в области компьютерных наук. Если требуется специалист на факультет компьютерных наук, значит, опыт работы с конкретной платформой не обязателен. Или, если имеется вакансия профессора в уни­верситете, значит, кандидат должен иметь опыт исследовательской работы. Более под­робно эти вопросы освещены в [Nahm и Моопеу, 2000].

13.6. Резюме и дополнительная литература

Как следует из этой главы, существует множество подходов к определению грамматик и разбору предложений на естественном языке. В качестве типичных примеров таких подходов были рассмотрены марковские модели и ATN-анализаторы. Грамотные студенты должны быть знакомы и с другими возможностями. К ним относятся грамматики преобра­зований (transformational grammar), семантические грамматики (semantic grammar), па­дежные грамматики (case grammar) и функциональные грамматики (function grammar) [Winograd, 1983], [Allen, 1995]. В грамматиках преобразований для представления глубин­ной структуры или смысла предложения используются контекстно-независимые правила. Такую глубинную структуру можно представить в виде дерева грамматического разбора, состоящего не только из терминальных и нетерминальных элементов, но и включающего наборы символов, именуемых грамматическими маркерами (grammatical marker). С помо-

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

щью грамматических маркеров можно представить такие свойства, как число, время и другие контекстно-зависимые аспекты лингвистической структуры. Затем с помощью набора правил более высокого уровня (так называемых правил преобразования) эта глубинная структура трансформируется в поверхностную структуру (surface structure), более близкую к естественной форме предложения. Например, предложения "Tom likes Jane" (Том любит Джейн) и "Jane is liked by Tom" (Джейн любима Томом) имеют одинаковую глубинную, но различную поверхностную структуру.

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

Исчерпывающее описание грамматик и методов разбора естественного языка приводится в [Winograd, 1983]. В этой книге особое внимание уделено грамматикам преобра­зования. В [Allen, 1997] содержится обзор проектных решений программ понимания ес­тественного языка. Еще одним источником по вопросам обработки естественного языка, затронутым в этой главе, является книга [Harris, 1985]. Рекомендуем также ознакомиться с [Gazdar и Mellish, 1989]. В [Charniak, 1993] представлены материалы по применению статистических методов для анализа структуры языка.

Семантический анализ естественного языка связан с решением многих сложных вопросов, относящихся к представлению знаний (глава 6). Эти вопросы затрагиваются в [Charniak и Wilks, 1976]. Из-за сложности моделирования знаний и необходимости учета социального контекста в процессе анализа естественного языка многие авторы поднимают вопрос о возможности применения этой технологии за пределами ограниченных предметных областей [Searle, 1980], [Winograd и Flores, 1986], [Smith, 1996].

В работе [Schank и Riesbeck, 1981] задачи понимания естественного языка решаются на основе технологии концептуальной зависимости. В [Schank и Abelson, 1977] обсуждается роль структур организации знаний более высокого уровня в программах обработки естественного языка.

Значение контекстуальных знаний в моделировании рассуждений отмечается в [Searle, 1969]. В [Fass и Wilks, 1983] предложена теория семантического предпочтения (semantic preference theory), которая может стать основой моделирования семантики естественного язы­ка. Семантическое предпочтение - это обобщение падежной грамматики, допускающее пре­образования падежных фреймов. Это обеспечивает большую гибкость семантики представле­ния, а также возможность представления таких понятий, как метафора и аналогия.

Полное описание иерархии Хомского читатель найдет в [Hopcroft и Ullman, 1979]. Концептуальные графы и их применение при моделировании семантики баз данных описаны в [Sowa, 1984].

Современное состояние технологии обработки языка описано в работах [Jurafsky и Martin, 2000], [Manning и Schutze, 1999], [Cole, 1997] и в зимнем номере журнала AI Magazine за 1997 год.

Новейшие исследования и тенденции в области понимания естественного языка как с традиционной, так и со стохастической точек зрения представлены в трудах ежегодных конференций по искусственному интеллекту и журнале Journal of the Association for Computational Linguistics.

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

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

1. Классифицируйте каждое из следующих предложений как синтаксически некоррект­

ное; синтаксически корректное, но бессмысленное; осмысленное, но неверное или вер­

ное. Когда в процессе понимания предложения выявляется каждая из этих проблем?

Colorless green ideas sleep furiously.

Fruit flies like a banana.

Dogs the bite man a.

George Washington was the fifth president of the USA.

This exercise is easy.

A want to be under the sea in an octopus's garden in the shade.

2. Опишите структуры представления и знания, необходимые для понимания следую­

щих предложений.

The brown dog ate the bone.

Attach the large wheel to the axle with the hex nut.

Mary watered the plants.

The spirit is willing but the flesh is weak.

My kingdom for a horse.

3. Выполните разбор следующих предложений с использованием грамматики из "мира собак", описанной в подразделе 13.2.1. Какие из этих предложений недопустимы? Почему?

The dog bites the dog. The big dog bites the man. Emma likes the boy. The man likes. Bite the man.

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

Выполните разбор каждого из предложений с использованием контекстно-зависимой

грамматики из подраздела 13.2.3.

The men like the dog. The dog bites the man.

6. Постройте дерево грамматического разбора для каждого из следующих предложе­

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

струкции. Если предложение допускает несколько вариантов разбора, постройте диа­

грамму для каждого из них и объясните, какая семантическая информация нужна для

выбора правильного варианта.

Time flies like an arrow but fruit flies like a banana. Tom gave the big, red book to Mary on Tuesday. Reasoning is an art and not a science. To err is human, to forgive divine.

7. Дополните грамматику из "мира собак", включив в нее прилагательные и именные

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

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

8. Добавьте следующие контекстно-независимые правила к грамматике из "мира собак"

из подраздела 13.2.1. Представьте результирующую грамматику в виде сетей перехода.

sentence«noun_phrase verb_phrase prepositional_phrase, prepositional_phrase«preposition noun_phrase,

prepositions« with,

prepositions«to preposition«on.

9. Разработайте ATN-анализатор для грамматики из "мира собак" с прилагательными

(упражнение 7) и вводными фразами (упражнение 8).

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

Дополните контекстно-зависимую грамматику из подраздела 13.2.3 для обеспечения

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

людей. Выполните соответствующую модификацию ATN-грамматики.

Дополните ATN-грамматику из подраздела 13.2.4, включив в нее вопросы who и what.

Объясните, как марковские модели из раздела 13.4 можно комбинировать с символьными подходами к пониманию языка, описанными в разделах 13.1-13.3.

Дополните пример интерфейса взаимодействия с базой данных из подраздела 13.6.2, что­

бы иметь возможность отвечать на вопросы вида "How much does Don Morrison earn?".

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

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

Допустим, что наряду с другими сотрудниками в отношении employee_salary

(подраздел 13.6.2) перечислены менеджеры. Дополните этот пример таким образом,

чтобы получить возможность обрабатывать запросы вида "Find any employee that

earns more than his or her manager" ("Найдите сотрудников, которые зарабатывают

больше, чем их работодатели").

Как стохастический подход из раздела 13.4 можно объединить с методами анализа

базы данных из раздела 13.5?

Использование стохастического подхода для изучения образов, содержащихся в реляционных базах данных, - важное современное направление исследований, которое иногда называют "добычей данных" (data mining) (см. раздел 13.3). Как можно использовать этот подход для ответов на запросы к реляционным базам данных, подобные приведенным в разделе 13.5?

На основе материала из раздела 13.5 разработайте систему извлечения информации

для некоторой области знаний, которую можно использовать в WWW.

601Часть VI

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

Карта - это не территория; имя - это не сам объект. - Альфред Коржибски (Alfred Korzybski)

Чему я научился, кроме корректного использования нескольких средств? - Гари Снайдер (Gary Snyder), Языки, их понимание и уровни абстракции

В части VI мы сначала обсудим вопросы, связанные с выбором языка программирования для задач искусственного интеллекта. Затем в главах, посвященных языкам LISP и PROLOG, будут рассмотрены многочисленные приемы программирования, которые можно использовать для построения интеллектуальных систем. Основная задача про­граммирования искусственного интеллекта- сформировать представление и управ­ляющие структуры, необходимые для решения интеллектуальной задачи. Требования к этим структурам во многом определяют необходимые свойства языка реализации. Во введении к этой части сначала перечисляются требования, выдвигаемые к языкам про­граммирования задач искусственного интеллекта, а затем вводятся языки программиро­вания LISP и PROLOG. Эти два языка чаще всего применяются для решения задач ис­кусственного интеллекта. Их синтаксис и семантика дают богатую почву для рассужде­ния о задачах и их решении. Эти языки оказали ощутимое влияние на историю развития искусственного интеллекта. Во многом это определяется их мощностью, а также воз­можностью их рассмотрения как "средства мышления".

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

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

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

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

В [Newell, 1982] выделены два уровня описания интеллектуальных систем: знаний (knowledge level) и символов (symbol level). Уровень символов связан с конкретными формализмами, применяемыми для представления знаний в процессе решения задач. Примером рассмотрения задачи на таком уровне является описание в главе 2 логики предикатов как языка представления. Выше расположен уровень знаний, связанный с содержанием информации и способами ее использования.

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

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

604

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

Рис. VI. 1. Уровни системы, основанной на знаниях из [Newell, 1982]

Уровень знаний определяет возможности интеллектуальной системы. Сами знания не зависят от формализмов, используемых для их представления, а также выразительности выбранного языка программирования. На уровне знаний решаются следующие вопросы. Какие запросы допустимы в системе? Какие объекты и отношения играют важную роль в данной предметной области? Как добавить в систему новые знания? Будут ли факты изменяться со временем? Как в системе будут реализованы рассуждения о знаниях? Обладает ли данная предметная область хорошо понятной систематикой? Имеется ли в ней непонятная или неполная информация? Важным шагом в разработке архитектуры про­граммы является внимательный анализ вопросов этого уровня и выбор конкретного спо­соба представления, используемого на символьном уровне.

На символьном уровне принимаются решения о структуре представления и организации знаний. Важнейшим вопросом является выбор языка программирования. Как из­вестно из глав 6-8, логика - это лишь один из многих формализмов представления знаний. Язык представления должен не только давать возможность выражать необходимые знания, но и быть согласованным, модифицируемым и вычислительно эффек­тивным. Он должен помогать программисту познакомиться с организацией базы зна­ний. Эти критерии зачастую противоречивы, что требует внимательного подхода к разработке языков представления.

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

Обзор языков PROLOG и LISP

605

Ниже уровня алгоритмов и структур данных располагается уровень языка. На этом уровне важную роль играет стиль программирования. Хотя хороший стиль программирования предполагает разделение конкретных свойств языка программирования и выше­стоящих уровней, специфика задач искусственного интеллекта требует их глубокой взаимосвязи. Кроме того, структура языка должна удовлетворять ограничениям, обу­словленным еще более низкими уровнями компьютерной архитектуры, включая опера­ционную систему, архитектуру аппаратных средств, объем памяти и быстродействие процессора. Языки LISP и PROLOG обеспечивают реализацию требований символьного уровня и учитывают архитектуру более низкого уровня. Этим объясняется их популяр­ность при решении задач искусственного интеллекта.

Рассмотрим основные свойства языков LISP и PROLOG.

Обзор языков PROLOG и LISP

PROLOG

PROLOG- это наиболее известный пример языка логического программирования (logic programming language). Логическая программа - это набор спецификаций в рамках формальной логики. PROLOG основан на теории предикатов первого порядка. Само имя этого языка программирования расшифровывается как Programming in Logic (Программирование в логике). При выполнении программы интерпретатор постоянно реализует вывод на основе логических спецификаций. Идея использования возможностей представления теории предикатов первого порядка - это одно из основных преимуществ применения языка PROLOG для компьютерных наук вообще и искусственного интеллекта в частности. Применение теории предикатов первого порядка в языке программирования обеспечивает прозрачный, элегантный синтаксис и хорошо определенную семантику.

Развитие языка PROLOG уходит корнями в исследования, связанные с доказательством теорем, а точнее, с разработкой алгоритмов опровержения резолюции [Robinson, 1965]. В этой работе разработана процедура доказательства, получившая название резолюции (resolution), которая и стала основным методом вычислений на языке PROLOG. В главе 12, посвященной вопросам автоматического доказательства теорем, описаны системы резолю­ции на основе опровержения (resolution refutation system) (см. разделы 12.2 и 12.3).

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

Первая PROLOG-программа была написана в начале 1970-х годов во Франции в рам­ках проекта по пониманию естественного языка [Colmerauer и др., 1973], [Roussel, 1975], [Kowalski, 1979a]. Теоретические основы этого языка описаны в работах [Kowalski,

606 Часть VI. Языки и технологии программирования для искусственного интеллекта

1979а, 19796], [Hayes, 1977], [Lloyd, 1984]. Основной этап развития языка PROLOG приходится на 1975-1979 годы, когда на кафедре искусственного интеллекта университета Эдинбурга Дэвид Уоррен (David H.D. Warren) и Фернандо Перейра (Fernando Pereira) от­вечали за реализацию этого языка. Они создали первый интерпретатор PROLOG, доста­точно робастный для предъявления его всей компьютерной общественности. Этот про­дукт базировался на системе DEC 10 и мог работать как в режиме интерпретатора, так и в режиме компилятора. Описание этого кода и результаты сравнения PROLOG с языком LISP приводятся в [Warren и др., 1977]. Эта версия стала первым стандартом языка PROLOG и была описана в книге [Clocksin и Mellish, 1984]. В нашей книге используется именно этот стандарт, который известен под названием эдинбургского синтаксиса.

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

LISP

Язык LISP был впервые предложен Джоном Маккарти (John McCarty) в конце 50-х годов. Вначале этот язык рассматривался как альтернативная модель вычислений на основе теории рекурсивных функций. В своей первой работе [McCarthy, 1960] автор языка сформулировал поставленную перед ним цель следующим образом. Требуется создать язык для символьных, а не числовых вычислений, реализующий модель вычислений на основе теории рекурсивных функций [Church, 1941]. При этом нужно обеспечить четкое определение синтаксиса и семантики этого языка и продемонстрировать формальную полноту этой вычислительной модели. Хотя LISP - это один из старейших компьютер­ных языков, все еще находящихся в использовании (наряду с языками FORTRAN и CO­BOL), при внимательном рассмотрении его истории развития становится ясно, что он постоянно идет в авангарде языков программирования. Эта модель программирования зарекомендовала себя столь хорошо, что на принципах функционального программиро­вания были основаны многие другие языки, в том числе SCHEME, ML и FP.

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

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

Обзор языков PROLOG и LISP 607