Рассуждения по прецедентам (case-based reasoning, CBR) — это метод формирования умозаключений, опирающийся не на логический вывод от исходных посылок (логические рассуждения), а на поиск и анализ случаев формирования подобных умозаключений в прошлом. Разумеется, такие умозаключения не являются достоверными и требуют верификации. Проверка корректности умозаключения может являться частью CBR-процесса.
С точки зрения решения задач, рассуждения по прецедентам — это метод получения решения путем поиска подобных проблемных ситуаций в памяти, хранящей прошлый опыт решения задач, и адаптации найденных решений к новым условиям. Применение CBR для решения задач оправдано в случае выполнения следующих условий, касающихся природы прикладной области [Leake, 1996]. Во-первых, подобные задачи должны иметь подобные решения (принцип регулярности). В этом случае накопленный опыт решения задач может служить отправной точкой процесса поиска решения для новых подобных задач. Во-вторых, виды задач, с которыми сталкивается решатель, должны иметь тенденцию к повторению. Это условие гарантирует, что для многих проблем в будущем будет существовать аналог в прошлом опыте.
Метод рассуждений по прецедентам имеет свои преимущества и недостатки по сравнению с другими методами получения решений. Среди преимуществ можно выделить следующее [Pal, Shiu, 2004].
Основными недостатками являются:
Рассмотрим в общих чертах, что собой представляет процесс рассуждений по прецедентам.
Ключевым понятием CBR-метода является прецедент. Прецедент (case, past case, previous case, stored case, retained case, precedent или episode) можно определить как единичную запись предыдущего опыта. То, какую именно информацию содержит такая запись, зависит от предметной области и целей использования прецедента. В случае применения CBR-метода для решения задач прецедент содержит, по меньшей мере, постановку задачи и способ ее решения. Множество всех прецедентов, накопленных в процессе работы CBR-метода, формируют информационное хранилище, называемое библиотекой прецедентов.
CBR в общем случае представляет собой циклический процесс: решение проблемы, запоминание этого решения в качестве прецедента, решение новой проблемы и так далее. CBR-цикл может быть описан следующими тремя процессами:
В литературе, как правило, процесс адаптации разделяют на повторное использование (reuse) и проверку (revise). Так как эти процессы часто оказываются сильно взаимосвязанными, разделение это весьма условно.
Таким образом, решение каждой задачи в CBR сводится к последовательному решению подзадач поиска схожих прецедентов, получения из них (путем адаптации) решения для новой задачи и сохранения нового случая решения задачи в библиотеке прецедентов. Графически, CBR-цикл можно представить в виде следующей диаграммы.
|
Для процессов, входящих в CBR-цикл, а также для самого прецедента (как хранилища информации) существует множество вариантов реализации. На уровне процессов уже нет каких-то универсальных решений; реализации процессов опираются на знания о предметной и проблемной области, то есть они специфичны в каждой конкретной прикладной системе. В частности, в индивидуальном порядке решаются такие вопросы, как:
Довольно подробный обзор различных вариантов практического решения этих вопросов приводится в [Aamodt, Plazа, 1994][Kolodner J., 1993][Leake, 1996][Pal, Shiu, 2004][Watson, Marir, 1994].
Планирование на базе рассуждений по прецедентам (case-based planning, CBP) — это повторное использование знаний о предыдущих эпизодах планирования для решения новых задач. В применении такого подхода существует множество положительных моментов. Во-первых, использование предыдущего опыта может повысить эффективность планировщика. Интуитивно ясно, что лучше начать с какого-то приблизительного решения, чем с нуля. Кроме того, возможность запоминания неудачных решений наравне с успешными позволяет избежать потенциальных проблем в будущем. Во-вторых, использование прецедентной информации может обеспечить более высокое качество решений в силу того, что прецедент описывает то, что действительно когда-то имело место, а не просто какое-то гипотетически возможное решение. В-третьих, когда устройство предметной области недостаточно понятно или ее описание неполно, использование обычных методов планирования становится невозможным. Однако CBP позволяет решать некоторые задачи и в такой ситуации.
Структура прецедента
В планировании прецедент типично включает в себя:
Постановка задачи может быть выражена различными способами: от множества фактов и множества атомарных подцелей (pure featural representation), до сложной ссылочной структуры (relational representation), возможно, опирающейся на модель предметной области. Решение задачи может храниться в виде плана (например, [Hanks, Weld, 1995]) или способа построения этого плана — последовательности принятых в процессе планирования решений, таких как выбор действия, выбор значения переменной и так далее (например, [Ihrig, Kambhampati, 1994]).
В библиотеке прецеденты могут храниться либо как конкретные примеры, либо в обобщенном виде. Обобщение может затронуть как описание задачи, так и описание решения (представленного в виде плана, но не трассы вывода). Хранение конкретных примеров привлекательно тем, что никакая информация не теряется. Но при этом библиотека становится громоздкой и замедляется поиск подходящего прецедента. С другой стороны, обобщение хоть и экономит память, но при этом происходит потеря информации и усложняется сохранение новых решений.
Кроме того, прецеденты могут храниться либо как отдельные единицы опыта, либо разделяться на части внутри библиотеки. В первом случае, каждый эпизод планирования приводит к появлению отдельного целостного описания для этого эпизода. Во втором — сохраняются решения подзадач исходной задачи. В результате в библиотеку попадает сразу множество решений для различных задач, что дает им больший шанс на повторное использование. Решение исходной задачи целиком может и не сохраняться или сохраняться, но с представлением плана в виде множества ссылок на получившиеся решения подзадач.
Поиск прецедента
Процесс поиска прецедента(ов), похожего на новую задачу, может быть ориентирован на различные цели, например:
Как правило, задачу поиска прецедента(ов) разделяют на три подзадачи:
Первая подзадача подразумевает выбор свойств, которые должны быть приняты во внимание при поиске лучшего прецедента. Обычно системы планирования, основанные на прецедентах, используют для этого цель, начальное состояние и, иногда, описание сложностей (failures), которые могут возникнуть при решении задачи.
Подзадача сопоставления заключается в поиске одного или более планов, которые (частично) совпадают по выбранным свойствам с текущей проблемой. Сопоставление может выполняться несколькими различными способами. Наиболее распространенными являются полное сопоставление и использование мер подобия (иногда, метрик подобия).
При полном сопоставлении выполняется поиск прецедентов, у которых выбранные свойства точно совпадают с соответствующими свойствами новой задачи. Если система не находит нужного решения, то выполняется обобщение выбранных свойств новой задачи и затем вновь выполняется попытка найти прецедент.
Мера подобия (similarity measure) — это функция, которая вычисляет степень сходства заданного прецедента и новой проблемы. Простейшую меру подобия можно определить как количество общих подцелей. Более гибкие меры подобия вычисляют взвешенную сумму общих подцелей и степень сходства начальных состояний. Веса служат для балансировки важности и полезности подцелей. Веса могут определяться константами для всех прецедентов сразу, но в более сложных предметных областях каждый прецедент имеет свой собственный вектор весов. Вообще, в случае с весами нужно разрешить следующие вопросы.
Одним из способов настройки весов является постепенное обучение важности подцелей, основанное на том, как часто прецедент успешно или неуспешно применялся (повторно).
Полезным побочным эффектом использования мер подобия является автоматическое ранжирование найденных решений, так как каждому найденному прецеденту сопоставляется его степень подобия новой задаче.
В результате решения подзадачи сопоставления может быть найдено несколько подходящих прецедентов. В этом случае планировщик должен выбрать один или несколько из них. При использовании мер подобия эта подзадача решается автоматически. Но могут использоваться и другие методы, основанные, например, на степени обобщенности прецедента (чем более конкретен прецедент, тем меньше потребуется усилий на адаптацию). Возможно также применение интерактивного способа.
Адаптация
Задача адаптации состоит:
После подмены цели и начальных условий план (готовый или полученный по трассе вывода) может потребовать изменений. Некоторые шаги плана могут оказаться ненужными, так как исчезла цель, достижению которой они служили. Могут появиться новые цели, а кроме того, изменение начальных условий может привести к неприменимости ряда шагов (то есть появлению подцелей). Корректировка плана может выполняться либо автоматически, либо пользователем.
Не всегда целесообразно выполнять адаптацию автоматически. Иногда адаптация вообще не нужна, даже если план некорректен. Например, когда полученные решения не применяются системой, а предъявляются пользователю в качестве подсказки, рекомендации (примерные планы действий). Даже если система применяет решения, то в некоторых предметных областях получение неверных решений является абсолютно недопустимым и требуется контроль со стороны человека. В этом случае, пользователь сам может вносить корректировки в план действий, предложенный системой.
Разработано несколько подходов автоматической адаптации.
Сохранение опыта
Результатом выполнения фаз поиска и адаптации является план для решения текущей проблемы. Чтобы замкнуть CBR-цикл и пополнить знания системы, необходимо сохранить текущий опыт планирования. Обучение осуществляется на основе наблюдения за ответной реакцией при исполнении плана. Планировщик может учиться как на положительных, так и на отрицательных примерах.
Однако сохранение знаний является необязательным шагом. Библиотека прецедентов может быть сформирована разработчиками заранее и содержать решения наиболее распространенных (в данной предметной области) задач планирования. В этом случае система будет не способна к адаптации. Но использование такого подхода может оказаться целесообразным в статичных предметных областях, когда нужно повысить лишь эффективность получения планов. Так как библиотека прецедентов заполняется экспертами в данной предметной области, то она, вероятно, будет содержать более эффективные решения, чем те, которые система сформировала бы автоматически. Кроме того, эксперт знает, какие задачи наиболее распространены в данной предметной области. Поэтому получаемая таким образом библиотека прецедентов с одной стороны должна быть более компактна, а с другой — содержать прецеденты, наиболее пригодные для повторного использования.
Хороший обзор по опыту применения рассуждений на основе прецедентов в планировании представлен в работах [Spalazzi, 2001] [Rousu, 1997].
Библиография.
Трофимов И.В.
июнь 2007