Обзор методов формирования баз знаний

Во многих предметных областях используются системы, основанные на знаниях. Они нашли широкое применение для решения большого количества неформализованных или плохо формализованных задач, таких как обучение, диагностика, управление, прогнозирование и др. [3]

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

Методы реализации продукционных правил прошли эволюционный процесс с середины ХХ века.

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

В самом простом виде правила продукций близки по смыслу импликации «Если – то», поэтому для правил продукций можно принять обозначение или, раскрыв условие применимости, эта запись примет вид:

где – условия применимости, образующие конъюнкцию;

– заключение или действие, которое имеет место при истинности конъюнкции.

Например:

Если внутреннее тестирование прошло и имеет место многократная перезагрузка операционной системы, то залипание клавиш или сбой ОЗУ.

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

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

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

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

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

АхВ → ВхА

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

Решением этой проблемы является rete-алгоритм, разработанный Чарльзом Л. Форго в 1979 году. Rete-алгоритм функционирует как сеть, предназначенная для хранения большого объема знаний. Он основан на использовании динамической структуры данных, которая автоматически реорганизуется с целью оптимизации поиска аналогично В-дереву, который применяется при индексации структур реляционных баз данных.

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

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

• Структурное сходство – один и тот же шаблон часто находится в левой части более чем одного правила.

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

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

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

<sentence>:: = <subject> <verb> <end-mark>

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

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

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

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

<verb>:: = дорожает | дешевеет

<end-mark>:: =. |! |?

В данном метаязыке вертикальная черта означает «или».

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

Гривна дорожает. Доллар дешевеет! Евро дешевеет?

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

Евр одешевшаедешевшае

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

<sentence>::= \<subject> <verb> <object> <end-mark>

<object> ::=на 1% | на 5% | на 10%

Однако, несмотря на уровень достигнутой сложности грамматики, принцип системы определения продукции остается неизменным [4].

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

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

Литература:

1. Балашов О.В., Круглов В.В. Подход к извлечению продукционных правил для систем поддержки принятия решений [Электронный ресурс]. – Режим доступа: http://www.smolensk.ru/user/sgma/MMORPH/N-12-html/borisov/balashov-2/balashov-2.htm.

2. Иванов А.С. Математические модели и алгоритмы функционирования продукционных баз знаний: автореф. дис. … канд. физ.-мат. наук (05.13.18 – математическое моделирование, численные методы и комплексы программ) / А.С. Иванов; рук. работы Сперанский Д.В. – С., 2007. – 117 с.

3. Катасёв А.С. Нейронечеткая система обнаружения продукционных зависимостей в базах данных / А.С. Катасёв // Программные продукты и системы. – 2011. – №3. – с. 12.

4. Методы реализации продукционных правил [Электронный ресурс]. – Режим доступа: http://homehelper.in.ua/blog/expertsystems/110.html.