Стратегии и алгоритмы поиска решений. Работа интерпретатора.

    С целью минимизации времени поиска решения и повышения эффективности, были разработаны следующие алгоритмы: поиск в глубину, поиск в ширину, разбиение на подзадачи и альфа-бета алгоритм [Таунсенд, Фохт, 1991; Уэно, Исидзука, 1989; справочник по ИИ, 1990].

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

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

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

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

    Альфа–бета алгоритм в основном ориентирован на различные игры, например, в шахматных программах.

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

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

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

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

    Действие компонента вывода основано на применении правила, называемого modus ponens.

    Правило modus ponens. Если известно, что истинно утверждение А и существует правило «ЕСЛИ А, ТО В», тогда утверждение В также истинно.

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

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

Управляющий компонент определяет порядок применения правил и выполняет четыре функции.

1) Сопоставление – образец правила (левая часть правила) сопоставляется с имеющимися фактами.

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

3) Срабатывание – если образец правила (левая часть правила) при сопоставлении совпадает с какими-либо фактами из рабочей памяти, то правило срабатывает.

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

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

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

    В одном цикле может сработать только одно правило. Если несколько правил успешно сопоставлены с фактами, то интерпретатор производит выбор по определенному критерию единственного правила, которое срабатывает в данном цикле. Цикл работы интерпретатора схематически представлен на рис. 1.

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

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

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

Рис. 2. Схема функционирования интерпретатора

    Далее необходимо аргументировать принятые решения. Разъяснение принятого экспертной системой (ЭС) решения важно по многим причинам.

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

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

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

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

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

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

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

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

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

– вывод на экран правил, активизированных на любой стадии консультации;

– запись и сохранение в процессе работы активизированных правил и связанных с ними событий, например, задаваемых вопросов и сформированных заключений;

– использование индексации правил, которая дает возможность извлечь определенное правило в ответ на вопрос, содержащийся в пользовательском запросе.

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

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

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

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

На рис. 3 представлена минимальная обобщенная структура ЭС.

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

Рис. 3. Структура экспертной системы

    Так как терминология в области разработки ЭС постоянно модифици­руется, определим основные термины в рамках данной работы.

    Пользователь - специалист предметной области, для которого предна­значена система. Обычно его квалификация недостаточно высока, и поэтому он нуждается в помощи и поддержке своей деятельности со стороны ЭС.

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

    Интерфейс пользователя - комплекс программ, реализующих диалог пользователя с ЭС как на стадии ввода информации, так и при получении результатов.

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

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

    Подсистема объяснений - программа, позволяющая пользователю получить ответы на вопросы: «Как была получена та или иная рекомендация?» и «Почему система приняла такое решение?»

    Ответ на вопрос «как» - это трассировка всего процесса получения решения с указанием использованных фрагментов БЗ, то есть всех шагов цепи умозаключений.

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

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

    Класс экспертных систем (ЭС) объединяет тысячи различных программных комплексов, которые можно классифицировать по различным критериям: по типу решаемых задач, по связям с реальным временем, по типу используемых ЭВМ.