Обзор методов формирования баз знаний | Статья в сборнике международной научной конференции

Библиографическое описание:

Логунова Е. А. Обзор методов формирования баз знаний [Текст] // Технические науки: теория и практика: материалы Междунар. науч. конф. (г. Чита, апрель 2012 г.). — Чита: Издательство Молодой ученый, 2012. — С. 62-64. — URL https://moluch.ru/conf/tech/archive/7/2191/ (дата обращения: 22.10.2018).

Во многих предметных областях используются системы, основанные на знаниях. Они нашли широкое применение для решения большого количества неформализованных или плохо формализованных задач, таких как обучение, диагностика, управление, прогнозирование и др. [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.

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

Похожие статьи

Использование логических блоков Дьенеша в интеллектуальном...

Формировать представления о математических понятиях (алгоритм, кодирование и

При этом в одном и том же упражнении всегда можно варьировать правила выполнения

Развивать умение раскодировать блоки с помощью знаков – символов, учить сравнивать и обобщать.

Создание криптографии с помощью модулярной математики

Ключевые слова: криптография, шифр, алгоритм шифрования, модулярная арифметика, шифр Цезаря.

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

Правила оформления статей.

Применение машины Тьюринга для реализации алгоритмов...

Правила выполнения программы.

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

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

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

На втором этапе в базу заносится векторное представление каждого вопроса, построенное по алгоритму

Правила оформления статей.

Использование тестового контроля на примере системы Moodle...

5) для каждого задания разрабатывается правило выставления оценки

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

В данной ситуации в создании эталонного ответа используют специальный символ (*), который...

Анализ поисковых алгоритмов при решении задач идентификации...

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

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

Оптимизация алгоритма выравнивания биологических...

Если в формуле (1) выбран , то сравниваются 2 элемента последовательностей, иначе если выбран или то удаляется j-й символ второй последовательности или i-й символ первой соответственно.

Правила оформления статей.

Реализация алгоритма Metaphone для кириллических фамилий...

Усовершенствованный алгоритм Soundex также обрабатывает исходную фамилию и возвращает код из четырех символов.

Алгоритм Metaphone более точен, чем Soundex, потому что использует больший набор правил английского произношения.

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

• Гибридизация с генетическими алгоритмами; • Использование базы нечётких правил. • Снижение зависимости от устанавливаемых параметров

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Использование логических блоков Дьенеша в интеллектуальном...

Формировать представления о математических понятиях (алгоритм, кодирование и

При этом в одном и том же упражнении всегда можно варьировать правила выполнения

Развивать умение раскодировать блоки с помощью знаков – символов, учить сравнивать и обобщать.

Создание криптографии с помощью модулярной математики

Ключевые слова: криптография, шифр, алгоритм шифрования, модулярная арифметика, шифр Цезаря.

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

Правила оформления статей.

Применение машины Тьюринга для реализации алгоритмов...

Правила выполнения программы.

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

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

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

На втором этапе в базу заносится векторное представление каждого вопроса, построенное по алгоритму

Правила оформления статей.

Использование тестового контроля на примере системы Moodle...

5) для каждого задания разрабатывается правило выставления оценки

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

В данной ситуации в создании эталонного ответа используют специальный символ (*), который...

Анализ поисковых алгоритмов при решении задач идентификации...

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

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

Оптимизация алгоритма выравнивания биологических...

Если в формуле (1) выбран , то сравниваются 2 элемента последовательностей, иначе если выбран или то удаляется j-й символ второй последовательности или i-й символ первой соответственно.

Правила оформления статей.

Реализация алгоритма Metaphone для кириллических фамилий...

Усовершенствованный алгоритм Soundex также обрабатывает исходную фамилию и возвращает код из четырех символов.

Алгоритм Metaphone более точен, чем Soundex, потому что использует больший набор правил английского произношения.

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

• Гибридизация с генетическими алгоритмами; • Использование базы нечётких правил. • Снижение зависимости от устанавливаемых параметров

Задать вопрос