Рассуждения на основе прецедентов

Прежде чем обсуждать рассуждения на основе прецедентов, важно определить контекст и задачи данной методики. Рассуждение на основе прецедентов (CBR) является разновидностью экспертных систем в искусственном интеллекте. Экспертная система — это система, имитирующая поведение эксперта для решения задач разной природы; она повторяет действия, которые бы предпринял сам человек, например, в случае диагностики поломок автомобиля. Преимуществами экспертных систем являются автоматизация деятельности экспертов, снижение затрат и повышение доступности консультационных услуг. Однако увеличение объёма информации в системах приводит к трудностям с обработкой больших массивов данных, что затрудняет или делает невозможным их практическое применение. Тем не менее, экспертные системы оказываются крайне полезными во многих случаях.

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

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

Стратегии работы экспертных систем можно разделить по типу используемого вывода:

Такой тип основывается на наборе правил, составляющих базу знаний эксперта, и позволяет получать новые знания «от фактов к цели» (прямой вывод) или «от цели к фактам» (обратный вывод).

Такие системы используют байесовские сети — вероятностные графовые модели, связывающие случайные переменные, и принимают решения исходя из теории вероятностей.

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

Рассуждения на основе прецедентов (CBR) — это разновидность экспертных систем, в которых ключевое понятие — «прецедент» (англ. case), понимаемый как минимальная единица опыта, представляющая конкретную ситуацию из прошлого. Прецедент содержит не только подробное описание происшедшего, но и контекст, в котором это произошло. То есть каждый случай не является абстрактным правилом, а базируется на реальном опыте.

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

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

Термин и метод рассуждений на основе прецедентов были разработаны в начале 1980-х в рамках работ Роджера Шенка и его учеников в Йельском университете. Его динамическая модель памяти^[2] положена в основу первых CBR-систем: CYRUS Джанет Колоднер^[3] и IPP Майкла Лебовица^[4]. В те же годы другая исследовательская школа изучала CBR в праве, работе с примерами на параллельных вычислительных машинах и комбинированных с другими видами рассуждений. В 1990-х вырос международный интерес к CBR, организована первая международная конференция по CBR в 1995 году и национальные семинары в Европе.

CBR-технологии дали ряд успешных промышленных решений: первая промышленная система — CLAVIER фирмы Lockheed^[5]. CBR внедрён во многих корпоративных приложениях (например, система поддержки Compaq SMART^[6]), а также реализован в коммерчески доступных инструментах:

• k-Commerce от eGain (ранее Inference Corporation)
• Kaidara Advisor от Kaidara (ранее AcknoSoft)
• SMART от Illation

Для обозначения CBR применяются и смежные понятия:

• Рассуждения на основе примеров: акцент на том, что прецеденты в базе знаний — это примеры ранее произошедших событий. Ключевая задача — правильно классифицировать добавляемые примеры, различая уже известные и действительно новые случаи.
• Рассуждения на основе экземпляров: специализация предыдущего подхода, ориентированная на синтаксический анализ сходства между прецедентами. Часто реализуется с помощью векторных представлений (исследования Киблера и Аха).
• Рассуждения на основе памяти: вся совокупность прецедентов рассматривается как память, а задача CBR — эффективный поиск и доступ к ней.
• Рассуждения на основе прецедентов: обычно используется как общий термин; подразумевает наличие богато структурированных, хорошо описанных случаев, которые могут быть адаптированы к новым ситуациям.
• Рассуждения по аналогии: термин-синквин для случаев, когда требуется перенос решения из другой предметной области при наличии структурных или ролевых сходств. Ключевой задачей является поиск и сопоставление доменных структур (mapping).

В дальнейших разделах под CBR подразумеваются все описанные выше варианты.

Существуют два основных подхода к организации рассуждений на основе прецедентов:

• Циклическая модель процесса (CBR-цикл)
• Декомпозиция по задачам

Оба подхода дополняют друг друга: первый отражает последовательность этапов — от поиска аналогов до обработки новых случаев, второй позволяет подробнее анализировать внутренние задачи на каждом этапе.

В типовой CBR-процесс выделяют четыре этапа:

1. Вспомнить похожие случаи.
2. Повторно использовать информацию и знания этих случаев для решения текущей задачи.
3. Проверить предложенное решение.
4. Сохранить релевантный опыт для будущих задач.

Каждый раз при столкновении с новой проблемой система или человек ищет наиболее похожие прецеденты в базе, адаптирует найденное решение к текущему контексту, испытывает вариант сценария в реальных или смоделированных условиях и сохраняет результат (и успешные, и ошибочные решения) в памяти для использования в будущем.

Помимо последовательной цепочки действий, процесс можно разложить на иерархию задач, каждая из которых реализуется определённым методом (например, поиск, адаптация, оценка, интеграция, обучение). Такое представление облегчает реализацию гибких и параллельных схем рассуждения, выделяя задачи по уровням подчинения и зависимости от подзадач.

Реализация CBR сопряжена с двумя основными группами проблем:

• поддержка, организация и масштабируемость базы знаний (структурирование прецедентов и индексов);
• разработка эффективных алгоритмов поиска и анализа аналогий.

Классические модели:

• Динамическая память (модель Шенка и Колоднер): группирует случаи с общими свойствами в обобщённые эпизоды (generalized episode) с разделением на общие характеристики (нормы), отдельные случаи и выделяющие различия индексы. Поддерживается иерархическая и избыточная структура, позволяющая быстро находить релевантные эпизоды.
• Модель категорий и примеров (Портер и Барейс): каждый случай рассматривается как реальный пример объекта, характеризуемого неравнозначными признаками и принадлежащего определённой категории. Связи между случаями, категориями и их характеристиками реализуются через разные типы индексов. Хранение новых случаев осуществляется с возможностью объединения, если различия несущественны.

Процесс поиска включает:

• Идентификация характеристик: сбор максимально полного набора признаков задачи и её контекста.
• Поиск первичных совпадений: формирование набора кандидатов на основе совпадающих признаков по индексам или путём последовательного перебора.
• Оценка и отбор: углублённый анализ и ранжирование кандидатов по степени соответствия; аргументация выбора в случае необходимости; формирование итогового списка для адаптации.

Адаптация найденных случаев бывает двух видов:

• Копирование: прямое перенесение релевантных характеристик в новую ситуацию (применяется при высокой схожести).
• Адаптация: изменение ранее использованного решения с учётом различий между старым и новым случаем, включая как транзакцию целевых значений, так и изменение стратегии.

Проверка состоит в:

• Оценке решения: проверка его работоспособности на практике или в симуляции и сравнение результата с ожидаемым;
• Исправлении ошибок: фиксации как правильных, так и ошибочных решений; провалившиеся случаи сохраняются в системе как примеры ошибок, помогающие избежать аналогичных ошибок в будущем.

Фаза приобретения нового опыта включает:

• Извлечение: сохранение всех значимых характеристик, описаний и обоснований решения (если оно было найдено без использования прецедентов, формируется новый случай).
• Индексация: выбор набора индексов — характеристик для быстрого доступа при поиске.
• Интеграция: корректное добавление нового или обновлённого случая в базу знаний без потери целостности и доступности.

Пример CBR-приложения — экспертная система для поддержки дистанционного образования. Система моделирует опыт взаимодействия преподавателей и студентов, выявляет общие и воспроизводимые процедуры и автоматизирует подбор материалов, составление стратегий обучения, рекомендации по дополнительным материалам, анализ активности учащегося и генерацию новых моделей обучения. Каждый элемент (учитель, ученик) представлен в виде агента, который взаимодействует с остальными в рамках единой цели — повышения эффективности и индивидуализации учебного процесса^[7].

Другой пример — система для проектирования бизнес-моделей на основе анализа и переформулирования известных решений для типовых задач. Использование CBR позволяет более гибко и качественно разрабатывать бизнес-решения в вариативных средах — преимущество перед системами на жёстких правилах для плохо структурированных областей.