2.10. Использование графических моделей в области искусственного интеллекта

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

2.10.1. Представление знаний при автоматическом доказательстве теорем

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

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

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

Рис. 2.12. Роль представления в математике.

На самом деле способ действий математика включает три различные фазы (Пастр, Пойа, Мериалдо): 1) понять теорему, заданную на формальном языке, т. е. перевести ее в некоторое внутреннее представление; 2) доказать теорему в этом внутреннем представлении, используя для этого все накопленные и адаптированные к этому внутреннему представлению знания; 3) перевести найденное еще неполное доказательство в строгое математическое доказательство, вновь введя символическую формализацию обычного математического языка. Роль представления в математике графически иллюстрируется рис. 2.12. Прежде чем переходить к примерам доказательств, отметим роль, которую играет в доказательстве теорем “хороший рисунок”.

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

дается графическое представление записи: (Банди, Пастр). При представлении простых алгоритмов обработки графические схемы могут быть использованы для эффективного отображения последовательности выводов (дедукций). Для транзитивного бинарного отношения например или или использование графического представления позволяет перевести выражение в форму из которой непосредственно получается При этом для получения доказательства в более компактной форме зрительно “очевидные” этапы могут быть опущены. Использование при доказательстве чертежа или рисунка часто позволяет отсекать ложные подцели. Если какое-либо свойство не находит подтверждения на чертеже, оно наверняка является ложным, и бесполезно терять время на попытку установить его. Более того, графическое представление помогает открытию. Если какое-то свойство проверено на. чертеже, можно предугадать доказательство соответствующей теоремы. Мы все используем этот способ при геометрических доказательствах. Чертеж полезен при определении симметрии переменных и является помощником в непосредственном выявлении эквивалентных ситуаций. Кроме того, наличие чертежа позволяет легко вводить в случае необходимости новые удобные элементы доказательства что широко используется в геометрии.

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

Рассмотрим несколько примеров графических представлений. На рис. 2.13, а и б приведено представление множеств в топологии (Мериалдо). Точки, обозначенные на рисунках цифрами, называются атомами. Каждый атом является представителем, подмножества, которому он принадлежит. Если атом соответствует пустому подмножеству, он удаляется. Таким образом, отношения принадлежности, включения, равенства представляются и запоминаются в сжатом виде. Кроме того, по диаграммам Венна легко составить простые алгоритмы, которые, основываясь на этом представлении, позволяют добавлять множество, получать пересечение множеств, приравнивать их, проверять правильность включения, определять дополнение множества.

Так, утверждение, что множество В включено в множество А тогда и только тогда, когда для каждого ребра,

связывающего вершину В с атомом существует ребро, связывающее также и вершину А с атомом представлено на рис. 2.13, б.

Рис. 2.13. Графические представления множества в топологии (а) и машинное представление диаграмм Венна (б).

Теперь рассмотрим теорему Т1 но прежде сделаем некоторые определения: запись А обозначает замыкание множества А (наименьшее замкнутое множество, содержащее множество А), а запись А обозначает границу множества

Теорема Т1:

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

Рис. 2.14. Построение множеств

Например, построение множеств показано на рис. 2.14. Затем программа конструирует множество пусть на рис. 2.14 это атомы 2 и 4. Аналогичным образом что и доказывает теорему.

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

теории множеств и топологии были доказаны этой программой за время с на ЭВМ типа ИБМ 4331.

Теперь рассмотрим пример из области геометрии (Buthion, 1979). “Задана окружность и две точки А и В вне окружности. Построить прямую проходящую через точку А, которая пересечет окружность в точках С и D, находящихся на равных расстояниях от заданной точки Для нас практически невозможно решить эту задачу, не построив чертеж. Мы предполагаем, что задача решена и строим соответствующий чертеж, как показано на рис. 2.15. Программа будет делать то же самое. Она называет и строит необходимые элементы: прямую находит точку — середину отрезка На самом деле в программе чертеж представляется в виде таблицы, где находятся имена элементов, отражена их сущность, их “степень свободы”, их возможные “представления”. Степень свободы элемента есть скаляр, который показывает, является ли элемент полностью известным, частично известным (здесь это прямая которая должна пройти через точку А) или совсем неизвестным. Представителями прямой являются все точки, принадлежащие ей. В начале решения строка таблицы будет выглядеть так

Рис. 2.15. Пример задачи с геометрическим построением.

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

Теперь рассмотрим пример на свойства функций (D. Pastre, 1978). Около 150 теорем элементарной теории множеств об образах и прообразах, функциях, конгруэнтностях, отношениях порядка, порядковых числах были доказаны программой которая работала почти как математик, и, в частности, ею была доказана приводимая ниже теорема

Теорема Пусть имеются три отображения .

Рис. 2.16. Пример графического построения, используемого программой DATE для доказательства теоремы Т2.

Если из трех функций две какие-либо функции являются сюръективными, а третья — инъективной, то и являются биективными.

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

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

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

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