Конкретная задача. 
Высокоуровневые эвристики для автоматизированного формирования базы знаний

Конкретизируем эти этапы для нашей задачи (фрагментарно).

1) Описание на ЯПЗ условия включает описание треугольника с вершинами A, B, C и основаниями высот A1, B1, C1, см. Рис. 1. При этом основания отмечены как известные объекты, а вершины как неизвестные. Задача решающей процедуры — выполнять преобразования над данной структурой ЯПЗ с целью означить вершины как известные объекты.

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

Основные действия по решения задачи выполняются в системе, реализованной на языке реляционной базы (4GL Progress). Именно в ней выполняется диалог по описанию условий задачи и формирование соответствующей структуры ЯПЗ и задания для Word-интерфейса. Использование векторной графики и сбалансированное распределение функций между Word и Progress позволяет существенно снизить нагрузку на базу знаний, Word используется фактически как рецептор относительно высокого уровня. В растровом варианте, когда на вход подается массив точек, ситуация была бы значительно сложнее. Некоторые примеры диалога и работы Word-интерфейса даны на HTML-странице [eia-dostup, 2010].

• 2) Поскольку попытка непосредственно получить ответ оканчивается неудачей, выполняется генерация конкретных структур ЯПЗ (множество экземпляров), удовлетворяющих описанию задачи. В результате формируются несколько треугольников, координаты которых получены системой случайным образом.
• 3) Над множеством экземпляров выполняется индуктивный поиск предположений, претендующих на доказательство. При этом поиске предполагается, что в системе имеется соответствующий алгоритмический базис: предикаты для сравнения координат точек, длин отрезков, величин углов и т. п. Не загромождая текст рядом неудачных попыток системы, отметим автоматически найденные эмпирические факты: равенство углов (Рис 1.). В отличие от типичного индуктивного вывода здесь трудности не столько в получении формулы (равенство определяется вызовом стандартного предиката), сколько в выборе объектов/атрибутов для сравнения.

Рис. 1. Произвольный остроугольный треугольник и его высоты.

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

Система предполагает, что элементы этих множеств аналогичны (сходство по признаку известны/неизвестны) В соответствии с вышеприведенной эвристикой для сравнения/анализа предлагается выбрать (за исключением тривиального случая множества всех известных объектов) треугольник типа A, B1, C1. Этот треугольник включает две известные и одну неизвестную вершины. После выбора система путем вызова стандартных формул эмпирически находит для экземпляра конкретные значения атрибутов (длин отрезков, величин углов и т. п.).

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

Процесс дальнейшего решения зависит от эмпирически найденных совпадений длин/пропорциональности отрезков или величин углов. Опишем один из типичных путей, автоматически полученных системой в ходе экспериментов. После выбора треугольника A, B1, C1 и эмпирического вычисления его углов и сторон, для анализа был выбран треугольник A, B, C, имеющий с A, B1, C1 общий угол (по соответствующей эвристике). Сравнение двух других углов выявляет их эмпирическое совпадение и позволяет выдвинуть предположение о подобии выбранных треугольников.

В данном случае подмножество аналогичных элементов является парой вершин B1 и C1, выбираемых из множества аналогичных (A1, B1, C1). Эмпирически найденное предположение о подобии передается для доказательства дедуктивному блоку. При этом в случае удачи фраза «аналогично получаем …» означает вывод по аналогии для треугольников A1, B, C1 и A1, B1, C, без обращения к дедуктивному блоку. Последний в свою очередь при неудаче обращается к эмпирическим данным, опираясь на известные признаки подобия треугольников (в частности — пропорциональность сторон с общим углом).

Эти эмпирические данные не имеют доказательной силы, но могут рассматриваться как контрпример (правда, не в данном случае). В рассматриваемом примере дедуктивный блок не смог непосредственно доказать догадку о подобии и обратился к индуктивному блоку за дальнейшими эмпирическими данными. Для целей иллюстрации взаимосвязи индуктивного и дедуктивного методов при автоматическом решении описание на данном уровне подробности достаточно. Опуская детали, отметим, что решение было найдено после эмпирического определения равенства углов б (B, A, A1 и B, C, C1), доказательства их равенства из подобия прямоугольных треугольников и доказательства подобия треугольников A, B, O и A1, B1, O.

И наконец доказательство (с использованием аналогии) равенства б углов B, B1, A1 и B, B1, C1 позволяет доказать, что в искомом треугольнике высоты являются биссектрисами известного треугольника. Путь к решению, очевидно, не является единственным и зависит от деталей взаимодействия индуктивного и дедуктивного блоков (в частности от ресурсов, выделяемых на организацию перебора). В процессе экспериментов было найдено несколько решений, некоторые технические подробности отражены на HTML-странице [eia-dostup, 2010]. На этой странице даны примеры, наглядно демонстрирующие действия системы с помощью упомянутого ранее интерфейса с Word. Следует отметить, что в этих примерах аналогия используется не только в случае успеха, но и при неудаче. Например, неудача при выборе треугольника A, C1, O позволяет отклонить выбор для анализа пяти аналогичных треугольников.

Подчеркнем, что предположение об аналогичности и о справедливости эмпирически найденных равенств для произвольного (остроугольного) треугольника носят правдоподобный характер, но доказательство подобия выполнено логически строго. В данном случае фраза «аналогично получаем …» распространяется на три треугольника (число сочетаний из 3 по 2), очевидно распространение на более общий случай. Очевидны также ориентировочные оценки выигрыша при использовании аналогии, зависящие как от мощности множества аналогичных объектов, так и от сложности доказательства для единичного случая.

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