Билет №51. Опишите архитектуру доски объявлений. Каким образом можно осуществить параллельные вычисления, используя данный подход?

Глобальная

«доска объявлений»

 

…

 

…

 

 

Схема архитектуры доски объявлений.

С точки зрения организации процесса вычислений, в системе можно выделить следующие структурные компоненты (Рисунок Архитектура доски объявлений.). Знания о предметной области разделены между независимыми источниками знаний (KSi – knowledge sources), которые работают под управлением планировщика (scheduler). Решение формируется в некоторой глобально доступной структуре – доске объявлений (blackboard). Функции доски объявлений во многом сходны с функциями рабочей памяти в продукционных системах, но ее организационная структура значительно сложнее. Как правило, доска объявлений разделяется на несколько уровней описания, причем каждый уровень соответствует определенной степени детализации. Данные в пределах отдельных уровней доски объявлений представляют иерархии объектов или графы. В самых современных системах может быть даже несколько досок объявлений. Источники знаний формируют объекты на доске объявлений, но это выполняется посредством планировщика. Активированные правила помещаются в специальный список выбора (agenda), откуда их извлекает планировщик. Источники знаний общаются между собой только через

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

друга: взаимодействие проходит через рабочую память. Доска объявлений работает по асинхронному принципу – каждый источник знаний KSi начинает свою работу, когда находит

соответствующие входные данные на доске объявлений. Закончив работу, он возвращает на доску полученные результаты и ожидает новых входных данных.

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

 

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

задач в рамках единой глобальной структуры.

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

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

Такая методика совместного решения проблем будет эффективна, если выполняются следующие требования:

• Различные модули правил должны иметь сходные синтаксис обозначений, имена объектов и пр., чтобы обеспечить передачу знаний между модулями. Хотя при записи результатов на доске

могут использоваться и разные схемы обозначений.

• Должен существовать протокол определения очередности выполнения правил, который вступает в силу в ситуации, когда сразу несколько альтернативных модулей готовы изменить

содержимое доски объявлений.

 

Билет №52. Назовите основные источники неопределенности знаний, встречающиеся при разработке экспертных систем. Каким образом применяются коэффициенты уверенности в системе MYCIN? По какому закону комбинируются коэффициенты уверенности для различных правил?

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

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

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

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

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

проверить, не дополнить не получить повторно.

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

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

«старый», «высокий» и т.п. Кроме того, теория вероятности подразумевает значительное количество вычислений, для обновления вероятностных оценок. Широкое распространение получили также аппараты нечеткой логики теории и функций доверия. Однако в последние годы внимание исследователей все больше привлекает теория вероятностей, с ее развитым и строго формализованным аппаратом.

 

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

Если условие 1 и…и условие m,

то прийти со степенью уверенности x к заключение 1 и … и к

заключение n.

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

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

Если условие 1 удовлетворяется с истинностью x₁ и … и условие m

удовлетворяется с истинностью x_m,

то прийти к заключению 1 со степенью уверенности y₁ и … и к

заключению n со степенью уверенности y_n.

В системе MYCIN коэффициенты уверенности (степени уверенности, истинность условий) – CF (certainty factor) – могут принимать значения в диапазоне от -1 до 1. В общем случае можно использовать любой диапазон значений. Положительные значения выражают уверенность эксперта в фактах, заключениях и пр. Отрицательные значения, напротив, выражают ошибочность утверждений. Окончательный коэффициент уверенности всего правила вычисляется как произведение: CF (заключение) = CF (предпосылки) ⋅ CF (правила).

Если в БЗ найдется несколько правил для данной предпосылки, то в системе MYCIN заключения этих правил объединяются. Пусть X и Y –коэффициенты уверенности одинаковых заключений, полученные при применении разных правил, тогда

 

X + Y – XY, при X, Y > 0

C, F (X, Y) = X + Y + XY, при X, Y < 0

(X + Y) / (1 – min(⎪X⎨, ⎪Y⎨)), при (X > 0 и Y< 0) или (X > 0 и Y< 0)

 

Очевидно, что формула обладает свойством коммутативности, и порядок следования гипотез не имеет значения.

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

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

Если условие 1,

то прийти со степенью уверенности x1 к заключение.

…

Если условие m,

то прийти со степенью уверенности xn к заключение.

Следует использовать одно правило вида:

Если условие 1 и … и условие m,

то прийти со степенью уверенности x к заключение.

В основе этой идеи лежит одно из следствий теории вероятностей, гласящее, что P (H | E1, E2) не может быть простой функцией от P (H | E1) и P (H | E2).