Продукционные модели. Работа машины вывода. Стратегии управления выводом
Способ представления знаний в виде продукционной модели основан на понятии «формальной системы продукций», которое в начале 50-х годов ввел в обращение американский логик Пост. Он показал, что любая формальная система может быть представлена как система продукций, т.е. как совокупность правил {Ri : Φi → Ψi }, где выражение Ri : Φi → Ψi означает, что в данной формальной системе по правилу Ri из посылки Φi непосредственно выводится заключение Ψi .
Сегодня продукционные модели являются наиболее популярными средствами представления знаний в системах искусственного интеллекта. Продукции, с одной стороны, близки к логическим моделям, что позволяет организовывать на них эффективные процедуры вывода, а с другой стороны, более наглядно отражают знания, чем классические логические модели. В них отсутствуют жесткие ограничения, характерные для логических исчислений, что дает возможность изменять интерпретацию элементов продукции.
Продукционная модель, или модель, основанная на правилах, позволяет представить знания в виде предложений типа «Если А (условие), то В (действие)».
Под «условием» понимается некоторое предложение-образец, по которому осуществляется поиск в базе знаний, а под «действием» — действия, выполняемые при успешном исходе поиска.
При использовании продукционных моделей для представления знаний создается продукционная система — набор продукций, организованный по определенному принципу. Для систем продукций создаются также определенные процедуры управления их функционированием, на которые обычно возлагается решение следующих задач:
|
|
|
¨ выявление совокупности активных правил — продукций, условия для применения которых выполнены (правил, которые могут действовать);
¨ разрешение конфликтов между правилами (с учетом приоритетов, эффективности, эвристик) и выбор правила для применения (правила, которое должно действовать);
¨ применение выбранного правила, то есть выполнение действий, предписываемых правой частью продукции (исполнение действия).
В самом общем виде продукционное правило представляет собой набор (I, Q, P, A→B, N) следующих компонент:
I — имя продукции, с помощью которого данная продукция выделяется из всего множества продукций (имя может выражать суть продукции, смысл выполняемого ей действия).
Q — область применения продукции — часто система продукций может быть разделена на подсистемы, каждая из которых связана с решением определенного типа задачи в комплексе задач, что позволяет экономить время на поиск нужных знаний.
P — условие применимости ядра продукции. Обычно Р представляет собой логическое выражение (когда Р принимает значение «истина», ядро продукции активизируется, а если Р — «ложно», то ядро продукции не может быть использовано).
|
|
|
A→B — ядро продукции — основной элемент продукционной системы.
N — постусловия применения продукции — другие последствия и изменения, обусловленные применением данного правила, не учтенные в правой части В его ядра. Они актуализируются только в том случае, если ядро продукции реализовалось. Постусловия продукции описывают действия и процедуры, которые необходимо выполнить после реализации В. Выполнение N может происходить сразу после реализации ядра продукции.
Ядра продукции можно классифицировать по различным основаниям. Прежде всего все ядра делятся на два больших типа:
¨ детерминированные — при актуализации ядра и при выполнимости А правая часть ядра выполняется обязательно, т.е. предложение реализуется с необходимостью;
¨ недетерминированные — при актуализации ядра и при выполнимости А правая часть ядра может выполняться или не выполняться, т.е. предложение реализуется с возможностью (интерпретация ядра в этом случае может, например, выглядеть так: «если А, то возможно В»).
|
|
|
Возможность может определяться некоторыми оценками реализации ядра. Например, если задана вероятность выполнения В при актуализации А, то продукция может быть такой: «если А, то с вероятностью р реализовать В». Оценка реализации ядра может быть лингвистической, связанной с понятием терм-множества лингвистической переменной, например: «если А, то с большей долей уверенности В». Возможны иные способы реализации ядра.
Детерминированные продукции могут быть однозначными и альтернативными. Во втором случае в правой части ядра указываются альтернативные возможности выбора, которые оцениваются специальными весами выбора. В качестве таких весов могут использоваться вероятностные оценки, лингвистические оценки, экспертные оценки и т.п.
Особым типом являются прогнозирующие продукции, описывающие последствия, ожидаемые при актуализации А, например: «если А, то с вероятностью р можно ожидать В».
Основными элементами продукционных систем являются следующие:
¨ База данных — структура данных (исходных фактов), используемая продукционной системой. В зависимости от конкретной задачи она может быть простой, как обычная матрица чисел, или сложной, как большая реляционная индексированная файловая структура.
|
|
|
¨ База знаний — множество правил (продукций).
¨ Машина вывода, которая формирует заключения, используя базу знаний и базу данных.
Работа машины вывода
Машина вывода является системой управления продукционной системы и выполняет функции просмотр существующих фактов из рабочей памяти (базы данных) и правил из базы знаний и добавление (по мере возможности) в рабочую память новых фактов, а также определение порядка просмотра и применения правил.
Машина вывода управляет процессом консультации, сохраняя для пользователя информацию о полученных заключениях, и запрашивает у него информацию, когда для срабатывания очередного правила в рабочей памяти оказывается недостаточно данных.
В подавляющем большинстве систем, основанных на знаниях, машина вывода представляет собой небольшую по объему программу и включает два компонента — один реализует собственно вывод, другой управляет этим процессом.
Компонент вывода действует на основании правила: «Если известно, что истинно утверждение А и существует правило вида “ЕСЛИ А, ТО В”, тогда утверждение В также истинно».
Правила срабатывают, когда находятся факты, удовлетворяющие их левой части: если истинна посылка, то должно быть и истинно и заключение.
Компонент вывода должен функционировать даже при недостатке информации. Полученное решение может быть и неточным, однако система не должна останавливаться из-за того, что отсутствует какая-либо часть входной информации.
Управляющий компонент определяет порядок применения правил и выполняет следующие функции:
¨ сопоставление — образец правила сопоставляется с имеющимися фактами;
¨ выбор — если в конкретной ситуации может быть применено сразу несколько правил, то из них выбирается одно, наиболее подходящее по заданному критерию (разрешение конфликта);
¨ срабатывание — если образец правила при сопоставлении совпал с какими-либо фактами из рабочей памяти, то правило срабатывает.
¨ действие — рабочая память подвергается изменению путем добавления в нее заключения сработавшего правила. Если в правой части правила содержится указание на какое-либо действие, то оно выполняется.
Машина вывода работает циклически. В каждом цикле она просматривает все правила, чтобы выявить те, посылки которых совпадают с известными на данный момент фактами из рабочей памяти. После выбора правило срабатывает, его заключение заносится в рабочую память, и затем цикл повторяется сначала.
В одном цикле может сработать одно правило. Если несколько правил успешно сопоставлены с фактами, то машина вывода производит выбор по определенному критерию единственного правила, которое срабатывает в данном цикле. Схема цикла работы машины вывода представлена на рис. 8.1.
Рис. 8.1. Цикл работы машины вывода
Информация из рабочей памяти последовательно сопоставляется с посылками правил для выявления успешного сопоставления. Совокупность отобранных правил составляет так называемое конфликтное множество. Для разрешения конфликта машина вывода имеет критерий, с помощью которого она выбирает единственное правило, после чего оно срабатывает. Это выражается в занесении фактов, образующих заключение правила, в рабочую память или в изменение критерия выбора конфликтующих правил. Если же в заключение правила входит название какого-нибудь действия, то оно выполняется.
Работа машины вывода зависит только от состояния рабочей памяти и от состава базы знаний. На практике обычно учитывается история работы, то есть поведение машины вывода в предшествующих циклах, информация об этом запоминается в памяти состояний (рис. 8.2), которая обычно содержит протокол системы.
Рис. 8.2. Схема работы машины вывода
Стратегии управления выводом в продукционной системе
От выбранного метода поиска, то есть стратегии вывода, будет зависеть порядок применения и срабатывания правил. Процедура выбора сводится к определению направления поиска и способа его осуществления. Процедура, реализующие поиск, обычно «зашиты» в машину вывода, поэтому в большинстве систем инженеры по знаниям не имеют к ним доступа и, следовательно, не могут в них ничего изменить по собственному желанию.
При разработке стратегии управления выводом важно определить два вопроса:
1. Какую точку в пространстве состояний принять в качестве исходной? От выбора этой точки зависит и метод осуществления поиска — в прямом или обратном направлении.
2. Какими методами можно повысить эффективность поиска решения? Эти методы определяются выбранной стратегией перебора — в глубину, в ширину, по подзадачам или иначе.
Существуют два метода осуществления поиска (способа вывода заключений):
¨ прямой вывод — путем построения прямой (от данных к цели поиска) цепочки рассуждений;
¨ обратный вывод — путем построения обратной (от цели, для ее подтверждения — к данным) цепочки рассуждений.
В прямых цепочках рассуждений вывод очередного заключения осуществляется путем сопоставления данных, содержащихся в базе данных, с левыми частями правил, и если находится правило, где сопоставление происходит, правая часть этого правила в качестве заключения по этому правилу помещается в базу данных (или исполняется предписываемое правой частью этого правила действие, соответствующим образом изменяющее содержимое базы данных).
В обратных цепочках рассуждений вывод начинается от поставленной цели, то есть выдвигается некоторая цель (гипотеза), а затем машина вывода как бы возвращается назад, переходя к правилам, пытаясь найти те, которые ее подтверждают. Если находится правило, правая часть (заключение) которого сопоставляется с этой целью, то левая часть (посылка) правила принимается за подцель. Этот процесс обратного вывода повторяется до тех пор, пока не будет получено совпадение подцелей с данными.
Обратный поиск обычно применяется в тех случаях, когда цели известны и их сравнительно немного.
Существуют системы, в которых вывод основывается на сочетании прямой и обратной цепочки рассуждений. Такой комбинированный метод получил название циклического.
В системах, базы знаний которых насчитывают сотни правил, желательным является использование стратегии управления выводом, позволяющей минимизировать время поиска решения и тем самым повысить эффективность вывода. К числу таких стратегий относятся: поиск в глубину, поиск в ширину, разбиение на подзадачи и альфа-бета алгоритм.
При поиске в глубину в качестве очередной подцели выбирается та, которая соответствует следующему, более детальному уровню описания задачи. Например, диагностирующая система, сделав на основе известных симптомов предложение о наличии определенного заболевания, будет продолжать запрашивать уточняющие признаки и симптомы этой болезни до тех пор, пока полностью не опровергнет выдвинутую гипотезу.
При поиске в ширину, напротив, система вначале проанализирует все симптомы, находящиеся на одном уровне пространства состояний, даже если они относятся к разным заболеваниям, и лишь за тем перейдет к симптомам следующего уровня детальности.
Разбиение на подзадачи — подразумевает выделение подзадач, решение которых рассматривается как достижение промежуточных целей на пути к конечной цели. Примером, подтверждающим эффективность разбиения на подзадачи, является поиск неисправностей в компьютере — сначала выявляется отказавшая подсистема (питание, память и т.д.), что сравнительно сужает пространство поиска. Если удается правильно понять сущность задачи и оптимально разбить ее на систему иерархически связанных целей-подцелей, то можно добиться того, что путь к ее решению в пространстве поиска будет минимальным.
Альфа-бета алгоритм позволяет уменьшить пространство состояний путем удаления ветвей, неперспективных для успешного поиска. Поэтому просматриваются только те вершины, в которые можно попасть в результате следующего шага, после чего неперспективные направления исключаются. Альфа-бета алгоритм нашел широкое применение в основном в системах, ориентированных на различные игры, например, в шахматных программах.
Продукционная модель привлекает разработчиков своей наглядностью, высокой модульностью, легкостью внесения дополнений и изменений и простотой механизма логического вывода.
В ряде систем искусственного интеллекта используют комбинации сетевых и продукционных моделей представления знаний. В таких моделях декларативные знания описываются в сетевом компоненте модели, а процедурные знания — в продукционном.
К достоинствам продукционной модели можно отнести: модульность структуры, естественность вывода (аналогия с рассуждениями человека-эксперта), простота модернизации и расширения (для внесения изменений в структуру, а, следовательно, и в процесс обработки, достаточно изменить правило).
Дата добавления: 2019-02-12; просмотров: 1042; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!