Представление знаний в ИС (стр. 4 )

Управляющая структура - это механизм применения правил в заданной модели с целью получения решений.

Язык логического программирования PROLOG

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

Язык FORLOG.

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

5. Правила продукции

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

Функция - это элементарное предложение, простое для обработки и понимания его экспертом.

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

5.5.  Стратегии поиска решений

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

·  задание метоправил по поиску решений;

·  использование специфических эвристик;

·  механизм, который позволяет усовершенствовать метод поиска

решений.

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

 

Рис.4.2

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

Выборка осуществляется двумя фазами:

·  синтаксическая фаза выборки;

·  семантическая фаза выборки.

Результат выборки - совокупность активных правил из базы знаний.

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

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

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

 

Рис.4.3.

 

Память системы (рис.4.2) содержит сведения о всех сеансах интерпретации при поиске решения.

Данная последовательность шагов (рис.4.3) может быть реализована в экспертных системах, представляемых двумя архитектурами:

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

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

В системах с архитектурой второго состояния рабочей области памяти сравнивается:

1) с данными, представленными на классной доске( в базе данных или информационной базе);

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

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

В традиционных языках программирования при вызове модуля или процедуры используется имя процедуры. При разработке экспертных систем выбор модуля (образца или правила) осуществляется на основе текущих правил.

Приведем классификацию стратегий принятия решений:

1. Локальная и глобальная классификации.

Локальная стратегия используется для частных правил, глобальная стратегия - для общих правил;

2. Скрытая и открыта.;

Открытая стратегия позволяет вмешиваться в процесс поиска принятия решения, стратегия закрытая является жестко заданной для предметной области;

3. По форме принятия решения:

стратегия поиска принятия решения вглубь и поиска принятия решения вширь:

- факт

 

Методы поиска, реализованные в экспертных системах

Методы поиска различаются:

·  по определению предметной области;

·  по представлению результатов.

Методы по определению предметной области классифицируются следующим образом:

n  по размерности пространства;

n  по количеству пространств и определению места и времени;

n  по модели, описывающих предметную область;

n  по совокупности моделей;

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

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

n  количество представленных результатов(один, несколько, все);

n  полнота представления информации и результат.

6.  Методы поиска решений в пространстве задач

6.1.  Общие стратегии поиска

1. Слепой поиск.

Используются следующие стратегии:

n  стратегии поиска «вглубь»;

n  стратегии поиска «вширь»,

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

Пример.

вширь		вглубь

 

		9	10	11			8

 

 

Конечные вершины графа - результат.

2. Метод редукции.

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

Различают :

n  дизъюнктивные ветви(или дуги ИЛИ);

n  конъюнктивные дуги (И);

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

Конъюнктивные дуги на графе объединяются душкой. При поиске результата в «И/ ИЛИ» графе можно воспользоваться стратегией поиска «вширь» и стратегией поиска «вглубь».

Пример.

Жертва знала убийцу

 

 

Жертва не сопративля-лась	Признаков вторжения нет	События произошли в доме жертвы

 

Признаков насилия нет	Следов борьбы нет	Двери и окна не взломаны	От окон нет следов
В спальне

n  Каким образом должен определен результат(обязательно),

n  каждый раз он определен и один,

n  ветви «И» предполагают наличие всех составляющих решения в правилах вывода, а ветви «ИЛИ» - наличие хотя бы одного решения.

3. Эвристический метод поиска.

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

4. Метод поиска с помощью генерации и проверки.

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

5. Метод поиска в иерархических пространствах.

В данном случае рассматривается не одно пространство поиска. Модель предметной области может представлять комбинацию моделей.

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

6.2.  Решение задач методом поиска в пространстве состояний

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

Основой метода являются следующие этапы.

1.  Определяется конечное число состояний, одно из состояний принимается за начальное и одно или несколько состояний определяются как искомое (конечное, или терминальное). Обозначим состояние S тройкой S = (x, y,z), где x - число миссионеров, y - число людоедов на левом берегу, z = {L, R}- положение лодки на левом (L ) или правом (R ) берегах. Итак, начальное состояние S0 = (3,3, L ) и конечное (терминальное) состояние Sk = (3,3, R ).

2.  Заданы правила перехода между группами состояний. Введем понятие действия M: [u: v] w, где u - число миссионеров в лодке, v - число людоедов в лодке, w - направление движения лодки (R или L ).

3.  Для каждого состояния заданы определенные условия допустимости (оценки) состояний: x >= y; 3 - x >= 3 - y; u + v <= 2.

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

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

Рис. 5.1. Переходы из исходного состояния

Такой метод поискаS0 => Sk называется прямым методом поиска. Поиск Sk => S0 называют обратным поиском. Поиск в двух направлениях одновременно называют двунаправленным поиском.

6.3.  Решение задач на основе продукций

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

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

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

P1: If (конь в поле 1) then (ход конем в поле 8)

P2: If (конь в поле 1) then (ход конем в поле 6)

P3: If (конь в поле 2) then (ход конем в поле 9)

P4: If (конь в поле 2) then (ход конем в поле 7)

P5: If (конь в поле 3) then (ход конем в поле 4)

P6: If (конь в поле 3) then (ход конем в поле 8)

P7: If (конь в поле 4) then (ход конем в поле 9)

P8: If (конь в поле 4) then (ход конем в поле 3)

P9: If (конь в поле 6) then (ход конем в поле 1)

P10: If (конь в поле 6) then (ход конем в поле 7)

P11: If (конь в поле 7) then (ход конем в поле 2)

P12: If (конь в поле 7) then (ход конем в поле 6)

P13: If (конь в поле 8) then (ход конем в поле 3)

P14: If (конь в поле 8) then (ход конем в поле 1)

P15: If (конь в поле 9) then (ход конем в поле 2)

P16: If (конь в поле 9) then (ход конем в поле 4)

Рис. 5.2. Шахматная доска 3х3 для задачи хода конем

Допустим, необходимо из исходного состояния (поле 1) перейти в целевое состояние (поле 2). Итерации продукционной системы для этого случая игры показаны в таблице 5.1.

Таблица 5.1. Итерации для задачи хода конем
№ итерации	Текущее поле	Целевое поле	Конфликтное множество	Активация правила
1	1	2	1, 2	2
2	6	2	1, 7	10
3	7	2		Выход

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

Перечислим основные преимущества продукционных систем:

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

6.4.  Решение задач на основе семантических сетей

Алгоритм наискорейшего спуска по дереву решений

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

Рис. 5.3. Граф переходов

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

Рис. 5.4. Поиск минимального пути на графе

Такой алгоритм поиска решения получил название алгоритма наискорейшего спуска.

Алгоритм минимакса

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

Рис. 5.5. Дерево ходов

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

Алгори́тм Де́йкстры — алгоритм на графах, изобретенный Э. Дейкстрой. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов. Известен также под названием кратчайший путь — первый.

Рассмотрим два примера применения алгоритма Дейкстры на практике.

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

Вариант 2. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула.

Определение алгоритма

Дан простой взвешенный граф G(V,E) без петель и дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины a графа G до всех остальных вершин этого графа.

1.  Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

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

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

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

Кружками обозначены вершины, линиями — пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначена их «цена» — длина пути. Рядом с каждой вершиной красным обозначена метка — длина кратчайшего пути в эту вершину из вершины 1.

Первый шаг. Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Ее соседями являются вершины 2, 3 и 6.

Первый по очереди сосед вершины 1 — вершина 2, потому что длина пути до нее минимальна. Длина пути в нее через вершину 1 равна кратчайшему расстоянию до вершины 1 + длина ребра, идущего из 1 в 2, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, поэтому новая метка 2-й вершины равна 7. На графике изначально рассмотрена вершина №3.

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины — 3-й и 6-й.

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

Второй шаг'. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.