Введение
Рассуждения по прецедентам (case-based reasoning, CBR) — это метод формирования умозаключений, опирающийся не на логический вывод от исходных посылок (логические рассуждения), а на поиск и анализ случаев формирования подобных умозаключений в прошлом. Разумеется, такие умозаключения не являются достоверными и требуют верификации. Проверка корректности умозаключения может являться частью CBR-процесса.
С точки зрения решения задач, рассуждения по прецедентам — это метод получения решения путем поиска подобных проблемных ситуаций в памяти, хранящей прошлый опыт решения задач, и адаптации найденных решений к новым условиям. Применение CBR для решения задач оправдано в случае выполнения следующих условий, касающихся природы прикладной области [Leake, 1996]. Во-первых, подобные задачи должны иметь подобные решения (принцип регулярности). В этом случае накопленный опыт решения задач может служить отправной точкой процесса поиска решения для новых подобных задач. Во-вторых, виды задач, с которыми сталкивается решатель, должны иметь тенденцию к повторению. Это условие гарантирует, что для многих проблем в будущем будет существовать аналог в прошлом опыте.
Метод рассуждений по прецедентам имеет свои преимущества и недостатки по сравнению с другими методами получения решений. Среди преимуществ можно выделить следующее [Pal, Shiu, 2004]. Легкость приобретения знаний (в противоположность системам, основанным на правилах). Создание системы, основанной на правилах, требует таких трудоемких этапов как получение, формализация и обобщение экспертных знаний, верификация системы на корректность и полноту. В CBR-системах приобретение знаний происходит путем формального описания случаев из практики (нет необходимости обобщения, и вытекающей отсюда угрозы переобобщения). Возможность объяснения полученного решения (в противоположность системам, основанным на нейронных сетях). CBR-система может объяснить полученное решение путем демонстрации успешного прецедента(ов) с отражением показателей сходства и рассуждений, использовавшихся при адаптации прецедента к новой ситуации. Такое объяснение может быть даже лучше, чем объяснения, выдаваемые системами, основанными на правилах. Последние иногда выдают очень длинные последовательности рассуждений, а сами правила конечному пользователю (в отличие от эксперта) могут казаться неочевидными или слишком сложными. Возможность работы в предметных областях, которые невозможно полностью понять, объяснить или смоделировать. Возможность обучения в процессе работы. Причем обучение будет происходить только в определенных направлениях, которые реально встречаются на практике и востребованы (нет избыточности). Возможность избежать повторения ошибки (обучение сбоям и их причинам для избегания их появления в дальнейшем). Возможность получения решений путем модификации прецедентов позволяет уменьшить объем вычислений в предметных областях, где генерация решения «с нуля» требует больших усилий.
Основными недостатками являются: Метод применим только в областях, где выполняется принцип регулярности и имеет место повторяемость видов задач. Если все время решаются принципиально новые задачи или если решения сходных задач различны, то CBR-метод неприемлем. Некомпактное (без обобщения) хранение знаний (опыта). Сложность и специфичность процессов поиска подобных случаев и адаптации решения. Рассуждения по прецедентам. Методология
Рассмотрим в общих чертах, что собой представляет процесс рассуждений по прецедентам.
Ключевым понятием CBR-метода является прецедент. Прецедент (case, past case, previous case, stored case, retained case, precedent или episode) можно определить как единичную запись предыдущего опыта. То, какую именно информацию содержит такая запись, зависит от предметной области и целей использования прецедента. В случае применения CBR-метода для решения задач прецедент содержит, по меньшей мере, постановку задачи и способ ее решения. Множество всех прецедентов, накопленных в процессе работы CBR-метода, формируют информационное хранилище, называемое библиотекой прецедентов.
CBR в общем случае представляет собой циклический процесс: решение проблемы, запоминание этого решения в качестве прецедента, решение новой проблемы и так далее. CBR-цикл может быть описан следующими тремя процессами: Поиск похожего прецедента(ов) (retrieve) — поиск прецедента(ов), у которых постановка задачи наиболее похожа на описание новой задачи. Адаптация (reuse + revise) — получение на базе найденного прецедента решения для новой задачи. Этот этап может также включать проверку полученного нового решения на корректность и толерантность к ошибкам и, возможно, дополнительную коррекцию решения. Сохранение прецедента (retain) — сохранение той части полученного опыта, которая может оказаться полезной для решения новых задач (пополнение или корректировка библиотеки прецедентов).
В литературе, как правило, процесс адаптации разделяют на повторное использование (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]).
В библиотеке прецеденты могут храниться либо как конкретные примеры, либо в обобщенном виде. Обобщение может затронуть как описание задачи, так и описание решения (представленного в виде плана, но не трассы вывода). Хранение конкретных примеров привлекательно тем, что никакая информация не теряется. Но при этом библиотека становится громоздкой и замедляется поиск подходящего прецедента. С другой стороны, обобщение хоть и экономит память, но при этом происходит потеря информации и усложняется сохранение новых решений.
Кроме того, прецеденты могут храниться либо как отдельные единицы опыта, либо разделяться на части внутри библиотеки. В первом случае, каждый эпизод планирования приводит к появлению отдельного целостного описания для этого эпизода. Во втором — сохраняются решения подзадач исходной задачи. В результате в библиотеку попадает сразу множество решений для различных задач, что дает им больший шанс на повторное использование. Решение исходной задачи целиком может и не сохраняться или сохраняться, но с представлением плана в виде множества ссылок на получившиеся решения подзадач.
Поиск прецедента
Процесс поиска прецедента(ов), похожего на новую задачу, может быть ориентирован на различные цели, например: найти такой прецедент, чтобы результирующий план оказался наиболее надежным; найти прецедент с планом, имеющим минимальное время исполнения; найти прецедент, для которого время получения нового решения окажется минимальным (минимум модификаций); найти прецедент, отражающий наиболее современный (поздний) опыт; и так далее.
Как правило, задачу поиска прецедента(ов) разделяют на три подзадачи: выбор свойств для сопоставления (feature identification); сопоставление (matching); выбор решения (selection или ranking).
Первая подзадача подразумевает выбор свойств, которые должны быть приняты во внимание при поиске лучшего прецедента. Обычно системы планирования, основанные на прецедентах, используют для этого цель, начальное состояние и, иногда, описание сложностей (failures), которые могут возникнуть при решении задачи.
Подзадача сопоставления заключается в поиске одного или более планов, которые (частично) совпадают по выбранным свойствам с текущей проблемой. Сопоставление может выполняться несколькими различными способами. Наиболее распространенными являются полное сопоставление и использование мер подобия (иногда, метрик подобия).
При полном сопоставлении выполняется поиск прецедентов, у которых выбранные свойства точно совпадают с соответствующими свойствами новой задачи. Если система не находит нужного решения, то выполняется обобщение выбранных свойств новой задачи и затем вновь выполняется попытка найти прецедент.
Мера подобия (similarity measure) — это функция, которая вычисляет степень сходства заданного прецедента и новой проблемы. Простейшую меру подобия можно определить как количество общих подцелей. Более гибкие меры подобия вычисляют взвешенную сумму общих подцелей и степень сходства начальных состояний. Веса служат для балансировки важности и полезности подцелей. Веса могут определяться константами для всех прецедентов сразу, но в более сложных предметных областях каждый прецедент имеет свой собственный вектор весов. Вообще, в случае с весами нужно разрешить следующие вопросы. Одинаково ли важны подцели? Важные подцели должны оказывать большее влияние при сопоставлении прецедента и новой проблемы. Одинаково ли трудно достичь подцели? Подцелям, которые легко достижимы, не следует уделять большого внимания на фазе поиска прецедента. Являются ли подцели независимыми? Если подцели зависимы, то количество подцелей, которые удовлетворяются прецедентом изначально (до адаптации), ничего не говорит о том, насколько сложно будет адаптировать прецедент. Даже неудовлетворение одной подцели может привести к бесполезности прецедента.
Одним из способов настройки весов является постепенное обучение важности подцелей, основанное на том, как часто прецедент успешно или неуспешно применялся (повторно).
Полезным побочным эффектом использования мер подобия является автоматическое ранжирование найденных решений, так как каждому найденному прецеденту сопоставляется его степень подобия новой задаче.
В результате решения подзадачи сопоставления может быть найдено несколько подходящих прецедентов. В этом случае планировщик должен выбрать один или несколько из них. При использовании мер подобия эта подзадача решается автоматически. Но могут использоваться и другие методы, основанные, например, на степени обобщенности прецедента (чем более конкретен прецедент, тем меньше потребуется усилий на адаптацию). Возможно также применение интерактивного способа.
Адаптация
Задача адаптации состоит: во-первых, в подмене цели и начальных условий выбранного прецедента целью и начальными условиями новой задачи; во-вторых, в обеспечении корректности плана после подмены.
После подмены цели и начальных условий план (готовый или полученный по трассе вывода) может потребовать изменений. Некоторые шаги плана могут оказаться ненужными, так как исчезла цель, достижению которой они служили. Могут появиться новые цели, а кроме того, изменение начальных условий может привести к неприменимости ряда шагов (то есть появлению подцелей). Корректировка плана может выполняться либо автоматически, либо пользователем.
Не всегда целесообразно выполнять адаптацию автоматически. Иногда адаптация вообще не нужна, даже если план некорректен. Например, когда полученные решения не применяются системой, а предъявляются пользователю в качестве подсказки, рекомендации (примерные планы действий). Даже если система применяет решения, то в некоторых предметных областях получение неверных решений является абсолютно недопустимым и требуется контроль со стороны человека. В этом случае, пользователь сам может вносить корректировки в план действий, предложенный системой.
Разработано несколько подходов автоматической адаптации. Простейшим случаем адаптации является наложение ограничений (constraint satisfaction). Суть этого подхода заключается в связывании переменных с конкретными объектами новой задачи без изменения структуры плана. Такой метод может работать только если план, полученный из прецедента, решает задачу, аналогичную (по стурктуре) новой, но оперирует другими объектами. Имеет смысл использовать этот метод совместно с каким-либо другим методом, который будет выполнять трансформации структуры плана.
Эвристические методы адаптации (heuristic-based adaptation) используют применение множества эвристических правил преобразования плана. Иногда эти преобразования описываются набором продукционных правил, определяющих изменения плана в зависимости от контекста. Обычно эвристический метод применяется в том случае, когда должна быть изменена структура плана. Можно привести множество примеров систем, опирающихся на эвристическую адаптацию: CHEF [Hammond, 1990a][Hammond, 1990b], PERSUADER [Sycara, 1988] и PLEXUS [Alterman, 1986].
Рекурсивная адаптация основывается на применении планирования по прецедентам для каждой из неудовлетворенных подцелей. Найденное решение некоторой подцели может породить множество открытых подцелей, которые достигаются тем же методом. В общем виде метод достаточно сложен, т.к. приходится выполнять объединение решений: текущего решения задачи и способа разрешения очередной подцели.
Генеративная адаптация предполагает удовлетворение еще недостигнутых целей методом, аналогичным порождению плана. Этот метод удобно использовать совместно с другими видами адаптации. Когда другой метод не может справиться с порождением необходимой части плана, то для этой цели применяется какой-либо алгоритм классического планирования. В качестве примеров систем, использующих этот вид адаптации, можно привести: SPA [Hanks, Weld, 1995], DerSNLP [Ihrig, Kambhampati, 1994], PRODIGY/NoLimit [Veloso, Carbonell, 1993].
Метод разделения и слияния. Для каждой неудовлетворенной цели выполняется поиск решения независимо. Затем полученные решения объединяются в единое решение задачи. Такая декомпозиция может повысить эффективность, если есть легкий способ выполнения слияния. Для поиска окончательного решения (слияния) может применяться любой метод (генерация, CBR).
Адаптация по прецедентам заключается в применении методологии CBR к случаям адаптации. То есть система составляет библиотеку случаев адаптации и затем пользуется этим опытом для осуществления новых адаптаций. Случай адаптации (как прецедент) может содержать в себе информацию о том, какими были цели адаптации, каким был изначальный план, и какие адаптирующие методы были использованы. Для заданной новой проблемы адаптации ищется прецедент адаптации, который имеет похожие цели адаптации и выполняется попытка применить найденные методы адаптации в текущей задаче. Примером системы, использующей такой тип адаптации, является DIAL [Leake et al., 1997].
Сохранение опыта
Результатом выполнения фаз поиска и адаптации является план для решения текущей проблемы. Чтобы замкнуть CBR-цикл и пополнить знания системы, необходимо сохранить текущий опыт планирования. Обучение осуществляется на основе наблюдения за ответной реакцией при исполнении плана. Планировщик может учиться как на положительных, так и на отрицательных примерах.
Однако сохранение знаний является необязательным шагом. Библиотека прецедентов может быть сформирована разработчиками заранее и содержать решения наиболее распространенных (в данной предметной области) задач планирования. В этом случае система будет не способна к адаптации. Но использование такого подхода может оказаться целесообразным в статичных предметных областях, когда нужно повысить лишь эффективность получения планов. Так как библиотека прецедентов заполняется экспертами в данной предметной области, то она, вероятно, будет содержать более эффективные решения, чем те, которые система сформировала бы автоматически. Кроме того, эксперт знает, какие задачи наиболее распространены в данной предметной области. Поэтому получаемая таким образом библиотека прецедентов с одной стороны должна быть более компактна, а с другой — содержать прецеденты, наиболее пригодные для повторного использования.