Реализация извлечения и сохранения прецедентов в CBR-системах на основе распределенных библиотек прецедентов

Размещено на http://www.allbest.ru/

РЕАЛИЗАЦИЯ ИЗВЛЕЧЕНИЯ И СОХРАНЕНИЯ ПРЕЦЕДЕНТОВ В CBR-СИСТЕМАХ НА ОСНОВЕ РАСПРЕДЕЛЕННЫХ БИБЛИОТЕК ПРЕЦЕДЕНТОВ

К.Н. Бредихин

П.Р. Варшавский

Московский Энергетический Институт, Москва

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

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

Вывод на основе прецедентов (Case-Based Reasoning, CBR) - это метод принятия решений, в котором используются знания о предыдущих ситуациях или случаях (прецедентах). Как правило, подобные методы рассуждений включают в себя четыре основных этапа, образующие так называемый цикл рассуждения на основе прецедентов или CBR-цикл (рис.1):

· Retrieve - извлечение наиболее подобного прецедента (или прецедентов) для сложившейся ситуации из библиотеки прецедентов (БП);

· Reuse - повторное использование извлеченного прецедента (прецедентов) для попытки решения текущей проблемы;

· Revise - пересмотр полученного решения и адаптация его, в случае необходимости, в соответствии с текущей проблемой;

· Retain - сохранение вновь принятого решения как части нового прецедента.

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

Рис. 1. CBR-цикл

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

До недавнего времени основное направление в области распределенного вывода на базе прецедентов (DistributedCBR, DCBR) заключалось в распределении ресурсов системы (как вычислительных, так и ресурсов данных в виде накопленного опыта) с целью повышения общей производительности CBR-системы, но распределенный характер БП также может быть обусловлен требованиями безопасности, предъявляемыми к системе (пользователи, обладающие информацией о некоторых прецедентах, не хотят «делиться» этой информацией с другими пользователями). Сами источники прецедентов могут быть распределены территориально и динамически дополнять локальные БП новыми прецедентами.

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

В данной работе основное внимание уделяется процедурам извлечения (retrieve) и сохранения (retain) вновь принятых решений в БП.

1. Вывод на основе распределенных библиотек прецедентов

Как уже упоминалось, вместе с распространением CBR-систем появляются новые возможности по использованию существующих БП, содержащих накопленный опыт в смежных предметных областях. Область исследований, получившая название MultipleCase-BasedReasoning (MCBR, вывод на основе множества БП), является одной из наиболее перспективных на сегодняшний день областей, связанных с распределенным выводом на основе прецедентов.

Основная идея MCBR-подхода заключается в том, что для решения некоторой задачи могут использоваться БП, сформированные в смежных или аналогичных областях, которые ко всему прочему могут отличаться по структуре. Помимо вывода на основе прецедентов в данном подходе используются методы на основе аналогий [Варшавский, 2004].

На рис.2 представлен пример базовой MCBR-архитектуры, доработанной с целью ограничения распространения прецедентов из отдельных библиотек за пределами локального сетевого узла. Получая на входе задачу, диспетчер прецедентов выбирает те БП, из которых необходимо извлечь прецеденты, а также определяет стратегию извлечения прецедентов из БП. Далее, агенты-аналитики, взаимодействующие непосредственно каждый со своей БП, согласно заданной стратегии производят извлечение прецедентов из локальных библиотек,при необходимости производя адаптацию (с целью приведения прецедентов из разных БП к общей структуре и составу) и слияние решений из разных БП.

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

Рис. 2. Пример MCBR-архитектуры

2. Извлечение прецедентов из множества распределенных библиотек

Рассмотрим процесс извлечения прецедентов в распределенной CBR-системе на базе интеллектуальных агентов. Формально мультиагентная система

M = {(A_i, C_i)}, i=1,2,…,n

включает в себя nавтономных агентов A_i, каждый из которых взаимодействует с отдельной библиотекой прецедентовC_i. Для простоты рассмотрим задачу, заключающуюся в выборе решения из конечного множества решений K = {S₁, …, S_K}. Таким образом, библиотека прецедентов C_i = {(P_j, S_k)} представляет собой коллекцию пар задача-решение. Каждый из агентов работает автономно и способен обучаться в ходе работы, то есть может пополнять свою локальную БП новыми прецедентами.

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

Когда агент A_i обращается к агенту A_j за «помощью» в решении текущей задачи, протокол взаимодействия между ними выглядит следующим образом.

Сначала A_i отсылает A_j описание задачи P_i.

A_j пытается найти решение для P, используя свою БП C_j и отсылает ответное сообщение либо о том, что он не смог найти решение (no_solution), либо запись заданной структуры с информацией о найденных решениях (solution endorsement record, SER):

SER = { {(S_k, E_k^j)}, P, A_j}.

Таким образом, запись SER представляет собой коллекцию подтверждающих пар (S_k, E_k^j), означающих, что агент A_j нашел E_k^j прецедентов в БП C_j, подтверждающих решение S_k - то есть существует E_k^j прецедентов, подтверждающих, что S_k является решением текущей задачи P. Каждый агент может высылать одну или несколько подтверждающих пар в одной SER-записи в качестве ответа на запрос другого агента.

С целью формирования окончательного решения на основе SER-записей, полученных от разных агентов, в рамках данной работы используется схема голосования BOUNDED-WEIGHTED APPROVAL VOTING (BWAV) [Plaza et al., 2001], заключающаяся в том, что агенты голосуют за решения, в зависимости от числа найденных прецедентов, подтверждающих эти решения.

Далее, для ограничения количества «голосов» у агента, введем нормализующую функцию Vote(S_k, A_j). Обозначим A^t как множество агентов, отославших свои SER-записи для текущей задачи P агенту A_i. При этом будем считать, что результат попытки решения задачи P агентом A_i также сформирован в виде SER-записи, и таким образом, A_iA^t. Тогда, функция голосования агентом A_jA^t за решение S_k будет выглядеть следующим образом:

,

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

Имея совокупность голосов за решение S_k, полученных от разных агентов, мы можем определить итоговую функцию голосования за это решение множеством агентов A^t:

.

В результате, итоговое решение будет определяться как решение, набравшее в сумме наибольшее количество голосов:

.

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

3. Сохранение вновь принятого решения в качестве нового прецедента

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

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

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

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

Агент A_i производит рассылку нового прецедента между остальными агентами A_j, i?j, которые, в свою очередь, проверяют этот прецедент на своих локальных БП аналогично первому этапу.

В качестве ответа A_j отсылает сообщение либо о том, что решения совпадают (success), либо о том, что они не совпадают (failure) и данный прецедент необходимо добавить в локальную БП агента A_j.

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

Стоит отметить, что помимо проблем с избыточностью, сохранение более чем одной копии нового прецедента в системе может понизить качество получаемых решений из-за снижения «субъективности» библиотек отдельных агентов. Так как в данном случае, со временем разница, между локальными БП отдельных агентов будет уменьшаться, то и распределения голосов между классами решений, сформированные отдельными агентами на базе их локальных БП, также будут все меньше отличаться друг от друга.

В работе были рассмотрены этапы извлечения прецедентов из распределенных библиотек прецедентов и последующего сохранения вновь принятых решений в качестве новых прецедентов. Описаны стратегии взаимодействия агентов друг с другом при поиске решения на основе голосования за решения. Приведена двухэтапная схема сохранения в БП системы вновь принятых решений как части новых прецедентов в зависимости от требований к безопасности и выбранной стратегии борьбы с избыточностью. алгоритм программный прецендент

Приведенные выше алгоритмы и стратегии извлечения и сохранения прецедентов были реализованы и протестированы в рамках разрабатываемой авторами программной системы поиска решений на основе прецедентов (CBR-системы) для распределенных интеллектуальных систем [Бредихин и др., 2010]. Программная реализация основных модулей системы, проведена на базе платформы. NET Framework 3.5 с использованием языков C# и F#. Тестирование проводилось на трех тестовых базах из набора с медицинскими данными, относящимися к диагностике сердечных заболеваний (источник - кафедра информатики и вычислительной техники Калифорнийского университета UCI Machine Learning Repository [Merzetal., 1998]).

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

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

Благодарности. Работа выполнена при финансовой поддержке грантов РФФИ (проекты № 08-01-00437-а и № 09-01-00076-а).

Список литературы

1. Бредихин К.Н., Варшавский П.Р. Распределенный вывод на основе прецедентов в интеллектуальных системах поддержки принятия решений // Теория и практика системного анализа. Труды I Всероссийской научной конференции молодых ученых. - Т. 1. - Рыбинск: РГАТА имени П. А. Соловьева, 2010.

2. Варшавский П.Р. Применение метода аналогий в рассуждении на основе прецедентов для интеллектуальных систем поддержки принятия решений // Труды девятой национальной конференции по ИИ с международным участием КИИ-2004. В 3-х т. Т.1. - М.: Физматлит, 2004.

3. Варшавский П.Р. Механизмы правдоподобных рассуждений на основе прецедентов (накопленного опыта) для систем экспертной диагностики // Труды 11-ой национальной конференции по ИИ с международным участием (КИИ-2008). В 3-х т., Т. 2. -М: ЛЕНАНД, 2008.

4. Варшавский П.Р., Еремеев А.П. Моделирование рассуждений на основе прецедентов в интеллектуальных системах поддержки принятия решений // Искусственный интеллект и принятие решений.2009. №2.

5. Plaza E., Ontaтon S. Ensemble case-based reasoning: Collaboration policies for multiagent cooperative CBR // Proceedings of the Fourth International Conference on Case-Based Reasoning, Berlin: Springer, 2001.

Размещено на Allbest.ru