14.2.3. Дедуктивный процесс ответов на вопросы с использованием резолюций

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

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

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

В системе и ее производных и факты, и вопросы выражаются в виде предложений. Это хорошо заметно для простых форм. Предложение

выражает мысль о том, что (Джордж дома).

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

означает (Где Джордж?), при этом утверждается, что существует место х, для которого высказывание истинно. Чтобы доказать истинность предложения (53), возьмем его отрицание и покажем, что оно ведет к противоречию. Отрицанием для (53) будет

что при соответствующей подстановке противоречит (52) и тем самым доказывает истинность (53).

В большинстве случаев нам нужно не просто знать, что ответ на наш вопрос существует, но и каков он. Чтобы запоминать ответы, Грин предложил ввести литерал Пусть — множество фактов, заданных в форме предложений, — запрос об этих фактах. Запрос тоже имеет форму предложения и содержит переменных. Ответом на служит такое множество значений переменных, что выполнимо. Если А существует, то множество будет невыполнимо. А можно определить, найдя подстановочный частный случай, необходимый для опровержения Можно резюмировать эту достаточно формальную ситуацию, сказав, что правильный ответ является контрпримером к предположению о

том, что правильного ответа не существует. Остается задача построить контрпример. Грин предложил с помощью введенного им прямого механизма — литерала ANSWER — запоминать необходимые подстановочные частные случаи. С тех пор были разработаны более эффективные методы запоминания решающих подстановок (Лак-хэм, Нильсон, 1971), но здесь трудно всех их описать.

Первый шаг метода литерала ANSWER — добавить специальный литерал к литералу

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

Рассмотрим пример:

Вопрос: Is there an animal?

Найдем отрицание для (57) и добавим литерал ANSWER:

Это следует понимать как „Либо нет животного, либо есть ответ". Ответ дает последовательность

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

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

и вопрос имеет вид

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

где сколемовские функции. Заметим, что функция без переменных, т. е. константа. Разрешая два предложения (62), получаем

Буквально (63) означает, что существует такая константа что ее функции есть ответ. Для пользователя это имеет смысл только в случае, если известно происхождение сколемовских функций. обеспечивает это, позволяя пользователю запрашивать дисплей о предложении, участвовавшем в построении конкретной сколемовской функции. Таким образом, видя (63), пользователь может спросить о происхождении функции или приведшей к или к в (62). Чтобы показать, как это сказывается на процессе ответа на вопросы, Грин приводит следующий пример. Определим как

Человек и находится на работе и — его стол.

Задача такова:

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

Если в х есть элементов у, а в у есть элементов то в х есть элементов

выражается в виде

где понимается как

обозначает произведение Вопрос

записывается как

что означает: „существует ли такое что можно вывести

Чтобы продемонстрировать возможность ответа на этот нетривиальный вопрос, Грин (1969а) применил к примерам, взятым из более специализированной системы Купера (1963) для ответа на вопросы о химических соединениях. Ее база данных состояла из 38 фактов либо из химии (например, магний — металл), либо относящихся к равенству и подстановке (например, симметрия равенства записывается в виде Примером проверки простого вопроса служит ответ на вопрос

Ответ таков:

Программа ответила на все 23 вопроса, которые задал Купер с целью продемонстрировать свою специализированную систему, в том числе и на более трудные, чем в нашем примере.

Грин (1969в) и Нильсон (1971) распространили метод резолюции из вопросно-ответной области на решение задач в пространстве состояний. Заметим, что это отличается от применения STRIPS (гл. И), где резолюция используется для доказательства факта о конкретном состоянии. Основная идея такого применения — ввести аксиомы, устанавливающие, что одно состояние можно достичь из другого с помощью оператора. Рассмотрим предложение

где — свойства состояний. (68) можно прочесть так:

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

В другой формулировке участвуют аксиомы вида

Это интерпретируется так:

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

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

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