Европа и Россия XVIII век Архитектура Рококо Скульптура Франсуа Буше Декоративно-прикладное искусство Севрский фарфор Бытовой жанр Собор Святого Павла Палладианство Пейзажный (английский) парк Британский музей в Лондоне Летний сад Зимний дворец

Рекомендуемая литература

Единственной книгой, в которой достаточно полно рассмотрена технология использования прецедентов в системах искусственного интеллекта, является [Kolodner, 1993]. В перечень кратких обзорных статей, которые можно рекомендовать для первого знакомства, я бы включил [Blade, 1991], [Harmon, 1992], [Kolodner, 1992] и [Watson and Marir, 1994]. Обзор инструментальных средств, предназначенных для работы с базами данных прецедентов, представлен в работе [Harmon and Hall, 1993].

Описания действующих систем, основанных на прецедентах, читатель найдет в работах [Acorn and Walden, 1992], [Allen, 1994], [Nguyen et al, 1993], [Hislop andPracht, 1994],-[Barren etal, 1993].

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

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

Механизм сопоставления должен быть достаточно эффективным, поскольку исчерпывающий поиск можно применять только при работе с базами прецедентов сравнительно небольшого объема. Одним из популярных методов эффективного индексирования является использование разделяемой сети свойств (shared feature network). При этом прецеденты, у которых какие-либо свойства совпадают, включаются в один кластер, в результате чего формируется таксономия типов прецедентов. Сопоставление в такой разделяемой сети свойств выполняется с помощью алгоритма поиска в ширину без обратного прослеживания. Поэтому время поиска связано с объемом пространства логарифмической зависимостью. Индивидуальное сопоставление, как правило, выполняется следующим образом.

Каждому свойству (или размерности) присваивается определенный вес, соответствующий степени "важности" этого свойства. Если, например, прецеденты включают счета пользователей, то имя пользователя, скорее всего, не имеет значения при поиске группы прецедентов с похожими счетами. Следовательно, свойство имя может иметь вес 0. А вот остаток на счете (в долларах) имеет очень существенное значение и ему следует придать вес 1.0. Чаще всего значения весов — это действительные числа в интервале [0,1].

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

Присвоить MATCH = 0.0;

Для каждого свойства в исходной спецификации

{

2. Найти соответственное свойство в хранимых прецедентах.

3. Сравнить два значения и вычислить степень близости т.

4. Умножить эту оценку на вес свойства с.

5. Присвоить MATCH = MATCH + cм.

}

Возвратить MATCH.

Базовая процедура называется сопоставлением с ближайшим соседом (Nearest-Neighbor matching), поскольку прецеденты, которые имеют близкие значения свойств, и концептуально ближе друг другу. Это может найти отражение и в структуре сети, где степень близости прецедентов будет соответствовать близости их свойств.

Вычисленное по этому алгоритму значение MATCH обычно называется агрегированной оценкой совпадения (aggregate match score). Естественно, что из базы прецедентов выбирается тот, который "заслужил" самую высокую оценку. Если же алгоритм работы системы предполагает и исследование альтернативных прецедентов, то оставшиеся должны быть ранжированы по полученным оценкам. Большинство доступных на рынке программ, имеющих дело с базами прецедентов, использует именно этот простой алгоритм. Применяемый на шаге (2) метод вычисления степени близости зависит от типа данных в каждом конкретном случае. При качественном сопоставлении свойств достаточно будет использовать двоичные оценки или вычислять расстояние в абстрактной иерархии. Так, в абстрактной иерархии ингредиентов кулинарных рецептов "брокколи" ближе к "горошку", чем к "цыплятам", и вычисленное значение должно отражать этот неоспоримый факт. Количественное сопоставление будет включать и шкалирование.

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

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

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

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

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

Решение типовых задач по математике и физике