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

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

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

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

2.2. Декомпозиция метода (основные фазы)

Хотя не все системы вывода, основанного на прецедентах, полностью включают этапы, приведенные ниже (Рис. 1), подход, основанный на прецедентах, в целом состоит из следующих компонентов [Aamodt 94]:

Рис 1. Цикл вывода на основе прецедентов

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

Эффективность поиска прецедентов для текущего случая во многом зависит от того, по каким признакам организован индекс в базе прецедентов. Это, в свою очередь, требует хороших знаний о предметной области и конечной цели решения проблемы. Однако выбор наилучшего индекса не может быть столь же прост, как это звучит, так как не имеется никаких общих рекомендаций для этого. Для ориентира, однако, можно привести четыре свойства хороших индексов [Kolodner 83]:

После того, как прецеденты извлечены, нужно выбрать "наиболее подходящий" из них. Это определяется сравнением признаков текущего случая и выбранных прецедентов. Определение метода, на котором будет основываться нахождение меры сходства прецедентов, решается во время создания системы ее разработчиками. Наиболее популярным и часто используемым является метод "ближайшего соседа" (nearest neighbour) [Anand 99]. В его основе лежит тот или иной способ измерения степени близости прецедента и текущего случая по каждому признаку (будь это текстовый, числовой или булевский), который пользователь сочтет полезным для достижения цели.

Говоря более строгим языком, вводится метрика на пространстве всех признаков, в этом пространстве определяется точка, соответствующая текущему случаю, и в рамках этой метрики находится ближайшая к ней точка из точек, представляющих прецеденты. Описанный здесь алгоритм очень прост – реально применяются некоторые его модификации. Обычно прогноз делается на основе нескольких ближайших точек, а не одной (K-nearest neighbours). Такой метод более устойчив, поскольку позволяет сгладить отдельные выбросы, случайный шум, всегда присутствующий в данных.

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

где w_j – вес j-го признака, sim – функция подобия (метрика), x_ij и x_ik – значения признака x_j для текущего случая и прецедента, соответственно. После вычисления степеней близости все прецеденты выстраиваются в единый ранжированный список.

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

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

Пусть имеются образцы X_i и X_k в N-мерном пространстве признаков. Основные метрики, традиционно используемые при выборе прецедентов, приводятся в таблице 1.

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

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

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

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

Не стоит, однако, рассчитывать, что экспертная система будет действительно принимать решения. Принятие решения всегда остается за человеком, а система лишь предлагает несколько возможных вариантов и указывает на самый "разумный" из них с ее точки зрения.

Наименование метрики	Тип признаков	Формула для оценки меры близости (метрики)
Эвклидово расстояние	Количественные
Манхэттенская метрика	Количественные
Мера сходства Хэмминга	Номинальные (качественные)	, где nik – число совпадающих признаков у образцов Xi и Xk.
Мера сходства Роджерса-Танимото	Номинальные шкалы	где – число совпадающих единичных признаков у образцов Xi и Xk; , – общее число еди-ничных признаков у образцов Xi и Xk соответственно.
Расстояние Махалонобиса	Количественные	W – ковариационная матрица выборки
Расстояние Журавлева	Смешанные	, где

Таблица 1. Основные типы метрик.

2.3. Примеры систем вывода на основе прецедентов

Вывод по прецедентам – не новая технология, ее возникновение прослеживается в работе Роджера Шанка по динамической памяти [Schank 82]. Изложенные этим исследователем идеи были далее расширены Джанет Колоднер, которая разработала систему CYRUS [Kolodner 83]. С 1988 года проводился ряд ежегодных семинаров под эгидой DARPA (Управление Перспективных Исследований Министерства Обороны США) [Kolodner 88, Hammond 89, Bareiss 91]. Интерес к методу вырос в последние годы, регулярно проводятся конференции и семинары типа широко известного Европейского семинара (EWCBR, в последующем – ECCBR) [Wess 93, Haton 94, Smith 96, Smyth 98, Blanzieri 00, Craw 02, Funk 04], семинара Соединенного Королевства (UKCBR) [UKCBR 04, UKCBR 05].

К ранним разработкам относят CHEF [Hammond 86] – систему, которая предназначалась для формирования кулинарных рецептов. Эта программа принимает информацию о целевых характеристиках блюда (тип, вкусовые качества, своеобразие) и формирует подходящий рецепт. Результатом работы программы должен быть рецепт – последовательность операций, позволяющая приготовить такое блюдо. Получив заказ, программа просматривает свою базу прецедентов, отыскивает в ней рецепт приготовления аналогичного блюда и адаптирует его в соответствии с особенностями текущего заказа.

Из других систем можно отметить PROTOS [Bareiss 88] для классификации и диагностирования нарушений слуха, MEDIATOR [Simpson 85] для области посредничества в спорных судебных вопросах.

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

В основу программы HYPO [Ashley 88, Ashley 90], которая была создана для обучения студентов-юристов методике ведения судебных дел, положена абстрактная модель процесса прения сторон. И расследования, и рассуждения в юриспруденции направляются аргументацией, а более точно – аргументами, выражающими противоположные интересы, с помощью которых стороны процесса пытаются склонить на свою сторону судью или присяжных, убедить их в том, что именно предлагаемая интерпретация закона и фактов является корректной в данном случае.

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

Ходы и контрходы можно анализировать в терминах суждений, основанных на прецедентах. Авторы системы считают, что в основе такой модели аргументации лежит следующий процесс [Ashley 90]:

Эта модель аргументации реализована в системе HYPO, в которой процесс формирования аргумента выполняется за шесть шагов.

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

Что касается доступности коммерческих систем и успеха в информационных приложениях – это система SMART [Acorn 92], которая дала импульс этой технологии. Система SMART предназначена для технической поддержки заказчиков корпорации COMPAQ. Когда заказчик сталкивается с проблемой (например, печать принтера блекнет), подробности передаются в систему. Выполняется начальный поиск в библиотеке прецедентов, чтобы найти случаи с подобными признаками. При недостатке информации система задает дополнительные вопросы. Как только определенный порог достигнут (скажем, прецедент совпадает не менее, чем на 80%), предлагается решение от прецедента. В дополнение к этому, система может быть использована как инструмент обучения.

В дальнейшем COMPAQ расширила эту систему, продвинув ее непосредственно к покупателям. Система QUICKSOURCE [Nguyen 93] позволяет пользователю самому справляться с проблемами и обращаться в центр поддержки в качестве последнего прибежища.

В системе KATE TOOLS компании Acknosoft (Франция) [Althof 95/1] поддерживается упрощенный взгляд на процесс вывода. Входная информация для KATE – это файл, который содержит описания признаков и их значения на специальном языке CASUAL [Althof 95/2]. KATE может работать со сложными данными, представленными в виде структурированных объектов, отношениями или даже общими знаниями о проблемной области. Но для выявления сходства между прецедентами используется одна простая метрика.

Основной акцент делается на отбор прецедентов с помощью алгоритма "ближайшего соседа". KATE использует версию алгоритма ближайшего соседа для вычисления метрики подобия. Близость между двумя случаями x и y, имеющими p признаков вычисляется по формуле:

Similarity(x,y)= -, где f определяется как

Алгоритм работы системы может быть описан следующим образом:

  Classified Data = 0

 for each Case x in Casebase do

1. for each y in Classified Data do

Sim(y) = Similarity(y,x)

2. y_max = (y_1,...,y_k) such that

Sim(y_k)= max(K-nearest neighbors)

3. if class(y_max) = class(x)

then classification is correct

Classified Data = Classified Data + {x}

else classification is incorrect

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

В настоящее время на рынке программных продуктов реально предлагается лишь несколько коммерческих продуктов, реализующих технологию вывода, основанного на прецедентах. Это объясняется, в первую очередь, сложностью алгоритмов и их эффективной программной реализации. Наиболее успешные и известные из присутствующих на рынке продуктов – CBR Express и Case Point (Inference Corp.), Apriori (Answer Systems), DP Umbrella (VYCOR Corp.) [Althof 96].

CBR Express и CasePoint – продукты, предназначенные для разработки экспертных систем, основанных на прецедентах. CBR Express тоже накапливает "опыт", обеспечивая ввод, сопровождение и динамическое добавление прецедентов, а также простой доступ к ним с помощью вопросов и ответов. Обе системы используются при автоматизации информационно-справочных служб и "горячих линий", а также при создании интеллектуальных программных продуктов, систем доступа к информации, систем публикации знаний и т. д.

При общении с системой сначала вводится простой запрос, например: "Мой компьютер не работает". Далее происходит выделение ключевых слов, поиск в базе прецедентов, и генерируется перечень потенциальных решений. Пользователю могут быть также заданы уточняющие вопросы. Предлагаемые варианты решения проблемы могут включать в себя видео- или фотоматериалы. Технология вывода по прецедентам представляет собой основу для практически безграничных приложений, которые наращиваются за счет постоянного сбора информации (причем обеспечивается совмещение структурированных и неструктурированных данных, включая мультимедиа). По мнению компаний, активно использующих эту технологию, таких как Nippon Steel, Lockheed и некоторых других, создается самообучающаяся коллективная память, исключительно удобная для накопления и передачи профессионального опыта.

Назад   Оглавление   Вперёд