22.4. Сравнение систем, основанных на правилах и прецедентах
Рекомендуемая литература
Упражнения
В главе 2 мы отмечали, что в ранних программах искусственного интеллекта отчетливо прослеживалась тенденция использовать по возможности единообразные методы решения проблем. Логические рассуждения строились на основе небольшого количества предположений или аксиом, а множество правил, применяемых для формирования нового состояния проблемы, также было невелико. Такие классические области искусственного интеллекта, как игры и доказательство теорем, являются формальными системами, которые по самой своей сути годятся для подобной комбинации логического анализа и эвристического поиска. Хотя в подавляющем большинстве экспертных систем применяется большое количество правил, специфичных для определенной предметной области, и используются разнообразные методы решения проблем, способы поиска и организации логического вывода, по сути, не очень отличаются от тех, что использовались в ранних программах искусственного интеллекта.
Например, в процессе работы производящей системы представление состояния проблемы в рабочей памяти последовательно изменяется, все более приближаясь к состоянию, характеризующему искомое решение. Такой пошаговый процесс очень напоминает последовательность ходов, дозволенных правилами игры, а отличие заключается в основном в семантике используемых правил. Программа игры в шахматы, основанная на знаниях, должна опираться не только на правила выполнения ходов, но и на информацию о стратегии, типовых ситуациях на доске, способах распознавания стадий игры (дебют, миттельшпиль или эндшпиль) и т.д.
Существует, однако, множество рутинных задач, выполняемых человеком, которые не вписываются в эту парадигму. Трудно себе представить, что, решая задачу, куда пойти сегодня вечером (в какой ресторан или кинотеатр), человек сознательно или подсознательно выполняет логический анализ или эвристический поиск. Если обратиться к менее тривиальным примерам, то также трудно поверить, будто судья, архитектор или ваш шеф, принимая решение, всегда прибегают к логическому анализу. Скорее всего, в большинстве случаев в основе наших действий в повседневных ситуациях лежит другой механизм рассуждений и принятия решения.
В отличие от большинства машин, человек почти всегда чем-то занят или озабочен, а потому при решении повседневных проблем уже на подсознательном уровне стремится сэкономить время и силы. И здесь на помощь всегда приходят память и прежний опыт — для человека проще распознать ситуацию и найти для нее аналог, чем заново формировать решение.
Но как все это можно реализовать в компьютерной модели рассуждений? Мы уже знаем, что воспоминания и приобретенный опыт не так просто свести к набору правил, но можно представить себе некоторую "библиотеку" ситуаций, встречавшихся в прошлом, которые имеют отношение к возникшей проблеме, например "репертуар" указаний шефа, или судебные решения, принятые в прошлом по аналогичным делам, или наброски архитектурных планов для сооружений аналогичного назначения и т.п. Естественно, что такая библиотека должна быть индексирована каким-то разумным способом, чтобы в массиве хранящихся описаний ситуаций можно было довольно быстро распознать аналогичную текущей. Кроме того, понадобится также и некоторый механизм, который позволит адаптировать ранее принятое решение к новой проблеме (текущей ситуации).
Описанный подход получил наименование рассуждение, основанное на прецедентах (case-based reasoning). Мы рассмотрим эту новую технологию на трех примерах, взятых из разных предметных областей, — кулинарии, юриспруденции и делопроизводства. После этого мы вновь вернемся к сравнению рассуждений, основанных на прецедентах, с более привычной технологией логического вывода в экспертных системах и покажем, что эти технологии не противоречат, а дополняют друг друга. В главе 23 этот тезис будет подкреплен примерами и дальнейшим анализом.
22.1. База прецедентов
Приведенная выше аналогия с библиотекой удобна, но является далеко не полной. Прецеденты — это не книги; хотя их и связывают с книгами некоторые общие абстрактные свойства, имеются и существенные отличия.
Прецеденты напоминают книги (конечно же, не из разряда беллетристики) тем, что содержат определенную специфическую информацию, "вставленную" в некоторый контекст. Содержимое прецедента — это знание, а контекст описывает некоторое состояние внешнего мира, в котором это знание применяется. Однако прецедент содержит знание в такой форме, которая может быть воспринята программой. Другими словами, знания, содержащиеся в описании прецедента, "готовы к употреблению" в том же смысле, в каком порождающие правила готовы к применению.
Прецедент должен представлять решение проблемы в определенном контексте и описывать то состояние мира, которое получится, если будет принято предлагаемое в нем решение. Это свойство часто можно встретить и в содержимом книг, но, опять же, разница состоит в том, что информация не представлена в форме, удобной для восприятия программой.
Хотя описания прецедентов и варьируются по размеру, они все-таки значительно уступают книгам в этом смысле. Информация в описаниях прецедентов значительно более сжата и представляется на каком-либо формальном языке.
Если прецедент — это модуль знаний, который может быть считан программой, то в чем его отличие от других способов представления знаний, множество которых мы уже рассмотрели в этой книге? Самый короткий ответ на этот вопрос — прецедент, как правило, реализуется в виде фрейма (см. главу 6), в котором структурированы информация о проблеме, решение и контекст. Так же, как фрейм или порождающее правило, описание прецедента может быть сопоставлено с данными или описанием цели. Но для извлечения описания прецедента из базы таких описаний используется совсем другой механизм, чем для извлечения фрейма или порождающего правила. Первое, что делается в процессе применения прецедента, — его адаптируют к текущей ситуации. Поэтому поиск описания прецедента требует использования достаточно сложного механизма индексирования.
22.1.1. Программа CHEF
Для демонстрации возможностей экспертной системы, базирующейся на прецедентах, рассмотрим систему CHEF, которая предназначалась для формирования кулинарных рецептов [Hammond, 1986]. Эта программа принимает информацию о целевых характеристиках блюда (тип, вкусовые качества, своеобразие) и формирует подходящий рецепт. Например, программа может получить следующий "заказ":
блюдо из баранины (beef);
включает брокколи (broccoli);
использует поджаривание (stir-fry);
блюдо должно получиться хрустящим (crisp).
Заказ оформляется в виде выражения на специальном формальном языке:
Результатом работы программы должен быть рецепт— последовательность операций, позволяющая приготовить такое блюдо.
Получив заказ, программа просматривает свою базу прецедентов, отыскивает в ней рецепт приготовления аналогичного блюда и адаптирует его в соответствии с особенностями текущего заказа (проблемы). Например, если в базе уже имеется рецепт для баранины с зеленым горошком, его можно скопировать и вместо горошка вставить брокколи. Этим, правда, адаптация не исчерпывается, поскольку горошек варится, а не жарится, как указано в заказе. Раз блюдо будет жариться, значит, брокколи придется сначала измельчить (если бы нужно было варить, то качанчики брокколи можно было бросать в воду целиком), следовательно, первоначальный план придется дополнить еще одной операцией. Кроме того, если кусочки баранины и броколли жарить вместе, то броколли, вероятно, пропитается соком. Значит, в системе нужно иметь правило, которое определит этот факт и изменит первоначальный простой план, — предложит сначала обжарить брокколи, а затем вынуть их.
На рис. 22.1 представлена упрощенная схема той части программы CHEF, которая имеет отношение к манипуляциям с базой прецедентов.
Рис. 22.1. Архитектура программы CHEF
Модель извлечения отыскивает в базе прецедентов рецепты, наиболее близкие к текущему заказу. Очевидно, что этот модуль должен обладать способностью обращаться к базе прецедентов как к памяти, адресуемой по содержанию, оценивать степень соответствия между набором входных спецификаций и характеристиками выбранного прецедента и ранжировать отобранные прецеденты на основании этой оценки.
Модуль модификации затем копирует и переименовывает выбранный прецедент и пытается скорректировать его в соответствии с полученной целевой спецификацией. В приведенном выше примере подстановка "брокколи" вместо "зеленый горошек" и модификация плана выполняются именно этим модулем.
После выполнения всех необходимых коррекций новый рецепт записывается модулем сохранения в базу прецедентов.
В программе CHEF корректировка неудачного плана (рецепта) в действительности выполняется отдельным модулем, который имеет доступ к специальному словарю термов, описывающих отказы, и индексированному множеству стратегий восстановления. Имеется также и специальный "симулятор", который позволяет "проиграть" сформированный рецепт и выявить в нем подводные камни, не заметные на первый взгляд. По основные модули работы с прецедентами выполняют именно те функции, которые мы описали выше.
22.1.2. Методы извлечения и адаптации прецедентов
В системах формирования суждений на основе прецедентов используются разные схемы извлечения прецедентов и их адаптации к новым проблемам.
В таких программах, как 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.
