Продукционные правила, продукционные системы. Марковский алгоритм

Методы реализации продукционных правил

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

Продукционная система Поста

Продукционные системы были впервые использованы в символической логике американским логиком Эмилем Постом (Emil Post), поэтому имя этого ученого вошло в названия указанных систем.

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

Это означает, что продукционное правило, после получения входной строки (антецедента), способно произвести новую строку (консеквент), например:

Клиент имеет постоянный доход → клиент кредитоспособный

В этом правиле стрелка означает, что одна символьная строка должна быть преобразована в другую. Указанное правило можно интерпретировать с помощью системы обозначений IF-THEN следующим образом:

IF клиент имеет постоянный доход THEN клиент кредитоспособный

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

Клиент имеет постоянный доход AND он владеет недвижимостью стоимостью 1000000 $ → выдать кредит

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

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

Марковские алгоритмы

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

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

Марковский алгоритм завершает свою работу после выявления одного из следующих условий:

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

Марковские алгоритмы могут также применяться к сегментам символьных строк, начиная слева. Например, продукционная система состоит из одного правила:

ЗА → ВЫ

После ее применения, к входной строки «ПРИВЛЕЧЬ» образуется новая строка «изъять». Поскольку теперь продукция применяется к новой строке, окончательным результатом становится строку «удалить». Марковские алгоритмы применяют специальные символы. В частности, специальный символ ^ обозначает пустую строку, не содержащую символов. Следующая продукция удаляет все вхождения символа А во входной строке:

А → ^

Другие специальные символы Марковского алгоритма могут представлять другие наборы символов и обозначаются буквами а, b, c, ..., y, z. Эти символы являются односимвольными переменными и представляют собой важную часть современных языков экспертных систем.

Например, следующее правило меняет местами символы А и В строке, если между ними находится любой единичный символ:

АхВ → ВХА

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

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

Rete-алгоритм

Решением этой проблемы является rete-алгоритм, разработанный Чарльзом Л. Форго (Charles L. Forgy) в 1979 году. Термин «rete-алгоритм» происходит от латинского слова rete, означающее сеть. Согласно названию, rete-алгоритм функционирует как сеть, предназначенная для хранения большого объема знаний.

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

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

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

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

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

Синтаксис языка определяет его форму, а семантика - значение ее слов. Одной из формальных систем обозначений, используемых для определения продукций, есть нормальная форма Бэкуса-Наура (Backus-Naur form - BNF). Для ее детального рассмотрения воспользуемся простым правилом грамматики английского языка, представленным в виде продукционного правила:

:: = 

Согласно системе обозначений формы Бэкуса-Наура предложения (sentence) состоит из подлежащего (subject) и сказуемого (verb), за которыми следует знак препинания, обозначающий конец предложения (end-mark). В этом правиле угловые скобки (<>) и символ «:: = - являются символами метаязыка. Символ «::=» означает «определен как". Он используется вместо символа «→», который применялся в Марковских алгоритмах продукционных правил.

Термы

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

Нетерминальный символ - это переменная, представляет другой терм. В свою очередь, в качестве такого «другого» терма может использоваться нетерминальный или терминальный символ.

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

:: = Гривна | Доллар | Евро

:: = дорожает | дешевеет :: =. |! |? В данной метаязыке вертикальная черта означает «или».

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

В качестве примера применения продукций данного языка можно привести такие предложения: Гривна дорожает. Доллар дешевеет! Евро дешевеет? Последовательность терминальных символов называется строкой символов языка.

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

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

Сложность грамматики увеличивается за счет различных дополнений, например: ::= < object> < object> ::=на 1% | на 5% | на 10% Однако, несмотря на уровень достигнутой сложности грамматики, принцип системы определения продукции остается неизменным.