Лекция 3

1.1.3  Модели знаний на основе продукций

В модели знаний на основе продукций знания представлены сово­купностью правил в формате "ЕСЛИ - ТО". Рассмотрим, например, правила порождения родительного падежа слов, задаваемые таблицей 1.1.

Для того, чтобы получить родительный падеж слова "Знахарь" отыскиваем первую подходящую строку, начиная с верхней, в левом ко­лонке табл.1.1. Строка будет подходящей, если указываемое в ней окончание совпадает с окончанием слова (в данном случае выбирается строка 5). Нетрудно, однако видеть, что строка 6 также подходит для нашей цели, хотя выдаваемый ею результат (правая колонка табл. 1.1.) не верен. Прежде чем мы рассмотрим более подробно это свойство сис­темы продукций, выясним их природу. Рассматривая структуру про­дукции, нетрудно видеть, что ее условная часть ("ЕСЛИ...") определяет ситуацию, в которой продукция применима. В примере со словом " знахарь" ситуация определяется его окончанием, т.е. либо окончанием "арь", либо ''-ь".

Таблица 1.1.

Если ситуация удовлетворяет продукции, то в результате ее применения может быть получен новый объект (состояние) согласно части " ТО ... " в структуре продукции. Так, применение продукции с номером 5 в табл.1.1. к слову "знахарь" порождает слово "знахаря", а применение продукции номер 6 дает слово "знахари". Таким образом, одним из основных вопросов в реализации продукционных систем является стратегия выбора альтернативных правил. В общем случае эта проблема нетривиальна. Условная часть продукции может иметь различные формы, такие например, как в следующих примерах:

² ЕСЛИ (идет - дождь) ²;

² ЕСЛИ (a > b² - b) ²;

² ЕСЛИ (P C Q) ².

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

МЕТКА: R26 Использование зонтика

УСЛОВИЕ: ЕСЛИ (идет дождь)

ДЕЙСТВИЕ: ТО (возьмите зонтик)

ОБЪЯСНЕНИЕ: (зонтик предохраняет от дождя)

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

<S⁰, S^f - ?>                                                                                              (1.5)

<S⁰ - ?, S^f>                                                                                              (1.6)

<S⁰, S^f, A - ?>                                                                                         (1.7)

<S⁰, S^f - ?, A - ?>                                                                                    (1.8)

где: S⁰ - начальная ситуация

S^f - конечная (желаемая, требуемая ситуация)

А - алгоритм (последовательность выполняемых продукций), переводящий систему из состояния S⁰ в состояние S^f

Задача (1.5) связана с определением ситуации (состояния) S^f, удо­влетворяющей некоторому критерию, которая может быть получена из заданной начальной ситуации.

Задача (1.6) является обратной по отношению к предыдущей.

Задача (1.7) заключается в отыскании алгоритма преобразования начальной ситуации в конечную.

Задача (1 .8) представляет обобщение задач (1 .5) и (1 .7).

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

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

                                                                                       (1.9)

где t₁, t₂, ..., t_n называются посылками, а t заключением продукции.

Применение схемы (1.9) основывается на подстановке цепочек зна­ков вместо всех переменных, причем вместо вхождений одной и той же переменной подставляется одна и та же цепочка.

В качестве других классических продукционных систем отметим нормальные алгоритмы Маркова и машину Тьюринга.

Развитием модели на основе правил является модель "доски объяв­лений". Эта модель реализована в системе распознавания разговорной речи HEARSAY - 2. Основной принцип организации модели доски объявлений заключается в разбиении продукций по уровням иерархии. При этом заключения продукций на нижних уровнях используются как входные условия для продукций более высокого уровня. На самом ниж­нем уровне модели доски объявлений представлены факты, на самом верхнем - результирующее заключение.

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

В рамках этой модели продукция определяется четверкой:

P = < L, C, N, A >,

где L – метка;

С – условие применимости;

N – ядро продукции, описываемое формулой (1.9);

А – постдействие.

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

Приведем алфавит:

G₁: А    И    Х

G₂: Б З Р     Ы Ь Я В

G₃: С О Э Ю

G₄: Е    Н П Т    Ш Г

G₅:      

G₆: Ц Ъ Щ

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

Таким образом получено следующее множество:

f₁’ – вертикальные наклонные (отвесные) прямые;

f₂’ – горизонтальные прямые;

f₃’ – полуовалы;

f₄’ – большие овалы;

f₅’ – вертикальные прямые;

f₆’ – короткие вертикальные наклонные отрезки;

f₇’ – хвостики.

Данная продукция может быть представлена в виде:

P = < L, C, N, A >, где L=L₁, а С – условие применимости данного шрифта.

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

На языке Prolog такая продукция выглядит так:

N₁:–G₁;G₂;G₃;G₄;G₅;G₆.

G₁:–P_f1’, P_f2’, P_f5’.

……………

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

f₁ – кривая замкнутая полная (на высоту кадра);

f₂ – кривая с левосторонней выпуклостью;

f₃ – кривая с правосторонней выпуклостью;

f₄ – кривая верхняя с правосторонней выпуклостью;

f₅ – кривая верхняя с левосторонней выпуклостью;

f₆ – кривая нижняя с правосторонней выпуклостью;

f₇ – кривая нижняя с левосторонней выпуклостью;

f₈ – вертикальный левый отрезок;

f₉ – вертикальный правый отрезок;

f₁₀ – вертикальный центральный отрезок;

f₁₁ – вертикальный левый верхний отрезок;

f₁₂ – вертикальный левый нижний отрезок;

f₁₃ – вертикальный правый верхний отрезок;

f₁₄ – вертикальный правый нижний отрезок;

f₁₅ – вертикальный центральный верхний отрезок;

f₁₆ – вертикальный центральный нижний отрезок;

f₁₇ – вертикальный отрезок с углом наклона менее 90°;

f₁₈ – вертикальный отрезок с углом наклона более 90°;

f₁₉ – вертикальный верхний отрезок с углом наклона менее 90°;

f₂₀ – вертикальный верхний отрезок с углом наклона более 90°;

f₂₁ – вертикальный нижний отрезок с углом наклона менее 90°;

f₂₂ – вертикальный нижний отрезок с углом наклона более 90°;

f₂₃ – горизонтальный верхний отрезок;

f₂₄ – горизонтальный нижний отрезок;

Если Вам понравилась эта лекция, то понравится и эта - 9. Итальянская журналистика в 1948 - 53.

f₂₅ – горизонтальный центральный отрезок;

f₂₆ – хвостик.

Рассмотрим символы из второй группы.

Постдействием для такой продукции будет процедура помещения распознанной буквы в какую-либо базу данных.