14.1.1. BASEBALL — простая вопросно-ответная система

Вскоре после появления в вычислительных науках метода обработки списков была написана (для иллюстрации того, как можно применить новые методы в вопросно-ответных системах) программа BASEBALL (Грин, Вулф, Хомский, Лафри, 1961; Грин, 1963). Эта программа предназначалась для ответа на вопросы об играх 1959 г. в американской бейсбольной лиге — отсюда и ее название. Хотя социальная ценность такого применения программы сомнительна, она дает хороший аппарат для проверки принципов программирования, которые нашли с тех пор широкое применение. Сообщения программе составлялись на простом подмножестве английского языка, на котором мы практически не будем останавливаться. Гораздо интереснее использованная здесь структура данных.

Данные программы BASEBALL были упорядочены в иерархическую систему. Эту структуру данных можно было бы эквивалентным образом представить в виде дерева. Самым высоким уровнем был ГОД (использовались данные только за 1959 г., но в программе предусматривались возможности и для нескольких лет), за ним, в порядке очередности, МЕСЯЦ и МЕСТО. После того как определялись ГОД, МЕСЯЦ и МЕСТО, последовательно указывались номер игры, день и счет (очков, выигранных командой).

В общих чертах формат структуры данных имел вид

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

Работу программы BASEBALL можно понять, рассмотрев два понятия: путь данных и список спецификаций.

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

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

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

Где (в каких местах) играла в июле команда „Редсокс“? (1) будет

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

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

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

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

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

Сколько игр в июле выиграно командами на своих полях? (2)

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

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

Ответ на вопрос составляется в результате просмотра основного списка. В случае (1) ответ получен простым перечислением значений МЕСТА в основном списке.

Рис. 14.1. (см. скан) Этапы ответа на вопросы в программе BASEBALL.

Ответ на несколько более сложный вопрос

В скольких местах играла команда Редсокс“ в июле? (3)

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

Схема этой процедуры ответа на вопросы изображена на рис. 14.1. Анализатор подмножества естественного языка

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

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

Как видно из блоков на рис. 14.1, программа BASEBALL не ограничена вопросами, на которые можно ответить, проходя через данные только один раз. Рассмотрим вопрос:

Сколько команд играли в 8 местах в июле? (4)

Исходный список спецификаций таков:

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

и на нельзя ответить сразу, поэтому нужен вспомогательный вопрос:

На также нельзя сразу ответить, поэтому он запоминается и порождается вопрос

На можно ответить с помощью вопросного процессора, дающего основной список

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

Развитие программы BASEBALL не пошло дальше рамок первоначального проекта — обычная судьба систем искусственного интеллекта. В самом деле, идея иерархической структуры данных, кажется, исчезла из программирования для машинного понимания. Это несколько удивляет, ибо иерархические структуры позволяют осуществить эффективное управление данными, особенно если большой объем информации необходимо держать частично в первичной памяти и частично в относительно медленно работающих, недорогих устройствах памяти (подробности см. в статье Сассенгута, 1963). Кроме того, иерархические структуры можно реализовать методами управления данными, совместимыми с более традиционными системами обработки информации (Хант и Килдалл, 1971; Лефковиц, 1969). Без сомнения, когда собираешься пользоваться „понимающими“ программами, надо на каком-то этапе поставить неизбежные практические вопросы стоимости и системной совместимости. Возможно, в будущем стоило бы вернуться к принципам, реализованным в этой довольно старой программе.