Системы продукций: структура, технология, применение

Системы продукций начали развиваться с середины 70-х годов в связи с появлением при­кладных программных систем специальной архитектуры, предназначен­ных для решения задач в плохо формализованных областях, таких как медицина, геология, понимание естественного языка. В первых работах [ 83, 85, 87] дается содержательное описание продукционного подхода.

Наиболее полное исследование данного представления в виде фор­мальных моделей дал А.С.Клещев [23, 24], В.Е.Кузнецов [26], Т.М.Яхно [70, 74 ], S.Vere [128], M.Georgeff [98, 99]. Особенности каждой модели опре­делялись классами решаемых задач и технологическим базисом.

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

2.5.1. Неформальное введение в системы про­дукций

Для того чтобы очертить концептуальные рамки понятия " системы про­дукций" (СП), используемого сейчас в области искусственного интел­лекта, попытаемся проследить из каких понятий оно складывалось и как эволюционировало.

Алгоритмические модели

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

По существу, все математические процедуры, приводящие к решению тех или иных задач, основаны на алгоритмах. Попытка уйти от интуи­тивного понимания алгоритма привела к ряду математических уточне­ний этого понятия. Наиболее известные среди них — машина Тьюринга, машина Поста и нормальные алгоритмы Маркова [30]. Для нас наиболь­ший интерес представляет формальное определение алгоритма, данное А.А.Марковым. Рассмотрим его более подробно. Нормальный ал­горитм задается упорядоченным списком вида

Q₁ ® R₁, Q₂ ®R₂, …, Qn ®R_n.

 

Выражение Qi ®Ri, называется подстановкой. Пусть дано некото­рое слово L. Подстановка Qi ®Ri, применяется к слову L следующим образом. Если слово Qi, входит в состав слова L, то его самое левое вхождение заменяется на Ri. Подстановки упорядочены в записи нор­мального алгоритма, и существует жесткий порядок их выполнения. К исходному слову L сначала всегда применяется первая по порядку под­становка. Если она изменила слово, то оно рассматривается как новое, и к нему вновь применяется первая подстановка. Если же подстановки, образующие нормальный алгоритм, не меняют слова, то оно считается окончательным, и применение подстановок прекращается.

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

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

Обе отмеченные алгоритмические процедуры представляют собой образцы ясности и четкости. Жесткие правила применения подста­новок обеспечиваютдетерминированность процедуры, задаваемой нор­мальным алгоритмом. Это характерно и для машин Тьюринга. Детер­минированность и результативность, свойственные им, регламентируют получение однозначных результатов при одинаковых исходных данных.

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

Логический вывод

Наиболее полно изученными исчислениями в математической логике являются исчисления высказываний и исчисления предикатов первого порядка [62]. С каждой формулой в этих исчислениях связывается поня­тие интерпретации (приписывание истинностных значений), через кото­рое определяются такие понятия, как противоречивость, непротиворечи­вость и общезначимость формул. Логическое следствие определяется следующим образом. Формула G есть логическое следствие формул F₁, F₂,..., F_n, тогда и только тогда, ко­гда для любой интерпретации I, если формула F₁& F₂&...& F_n истинна в I, то G также в ней истинна [62].

Логическое следствие получается в результате применения логиче­ских правил вывода. Такие правила вывода обладают универсальной истинностью и могут применяться либо для установления истинности некоторого утверждения, либо для порождения новых заключений. В ис­числении предикатов первого порядка зафиксировано несколько правил вывода (примером может служить известное правило — modus ponens).

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

Такие исчисления с фиксированным набором логических правил вы­вода обычно называют чистыми, или логическими, а вывод в них — логическим выводом.

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

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

И тем не менее именно логические исчисления положили основу логи­ческому программированию и сделали популярным язык Пролог [25].

Прикладные модели

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

Система подстановок задается некоторым алфавитом С = {ci, c2,..., сn} и базисными подстановками a®b где a, b — некоторые (возможно, пустые) слова в алфавите С. Каждую подстановку можно рассматри­вать как правило вывода Р (х, у), считая, что Р (х, у) истинно, если слово у получается из слова х посредством подстановки в х слова b вместо какого-либо вхождения слова a. Этот класс исчислений привел к актив­но развиваемым системам переписывания термов [102].

К данному классу можно отнести исчисление, введенное Э.Постом, которое он назвал системами продукций [118]. Система продукций Поста задается своим алфавитом и системой под­становок каждая, из которых называется продукцией и имеет вид

a_i W ® Wb_i, (i = 1... n),

где ai, bi — слова в алфавите С. Пусть некоторое слово L начинает­ся словом аi. Выполнить над L продукцию — это значит вычеркнуть из L начальный отрезок аi, и к оставшемуся слову приписать справа слово bi. Например, применяя к слову aba продукцию abW —> Wc, полу­чим слово ас. Существуют теоремы, показывающие, что любую систему подстановок можно " вложить" в систему продукций [28]. Характер­ным для систем продукций Поста является ограничение на форму самих подстановок.

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

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

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

условие —> действие

в которых левая часть описывает некоторую ситуацию, а правая — те действия или заключения, которые надо сделать, если имеет место опи­сываемая ситуация.

Общая постановка задач при использовании множества правил фор­мулируется следующим образом. Задается исходное и целевое состояние задачи. Система сама на основе заложенных в нее правил ищет возмож­ные пути решения перевода исходного состояния в целевое. Знания о предметной области задают множество возможных преобразований в пространстве ситуаций, каждое из которых ограничено соответствую­щими условиями применимости данного преобразования в той или иной ситуации. Такие правила стали называть продукциями, а системы, ис­пользующие их для описания знаний — системами продукций [83].

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

Такая форма представления информации была принята в некоторых психологических моделях мышления человека. Исследования процессов принятия решений человеком показали, что, рассуждая, человек исполь­зует правила вида условие —> действие. А.Ньюэлл первым предложил использовать такое представление знаний для моделирования на ЭВМ процесса принятия решений [114].

Легко заметить, что предлагаемая форма для представления знаний выглядит необычайно похожей на системы подстановок. Поскольку раз­работки в области ИИ всегда связаны с созданием программных систем, то и для систем, поддерживающих представление знаний в виде пра­вил, потребовалось название. Первоначально такие системы назывались по-разному: rewriting-rules systems, rule-based systems, pattern-directed inference systems, production systems. Больше всех повезло термину " си­стемы продукций". С середины 70-х годов этот термин прочно закре­пился за программными системами искусственного интеллекта, знания в которых представлялись в виде правил указанного вида.

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

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

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

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

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

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

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

- относительно низкая эффективность по сравнению с традиционны­ми методами программирования. Однако этот разрыв в эффектив­ности быстро сокращается за счет повышения уровня традицион­ных средств программирования (и соответствующего понижения " нормы эффективности" ) — с одной стороны, и прогрессом работ по развитию структуры самих систем продукций и оптимизации соответствующих базовых процессов — с другой. Кроме того, при современной мощности рядовой ЭВМ для многих приложений это различие в эффективности перестает быть значимым;

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

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

Что касается программных реализации систем продукций, то не ставится задача сделать полный обзор существующих си­стем. В настоящее время существует большое количество монографий, подробно описывающих как широко известные системы продукций типа MYCIN [121], PROSPECTOR [87], HEARSAY [60], так и менее известные, но достаточно интересные как с точки зрения технологии, так и с точки зрения представления знаний. Среди этих монографий следует отметить [49, 53, 61, 69].

Метамодель систем продукций

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

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

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

Основные подсистемы

Рассмотрим схему функционирования систем продукций. Анализ этой схемы позволяет выделить три тесно связанные подсистемы, которые можно считать основными структурными компонентами ПСМ: модуль базы данных, модуль правил и модуль управления (интерпретатор) (рис. 1.1).

 

Рис. 1.1. Основные компоненты ПСМ

Модуль базы данных представляет собой ассоциативную память, ори­ентированную на размещение и обработку структур какого-либо опреде­ленного типа. В базе хранятся данные, которые обрабатывает ПСМ, и это определяет основной набор реализуемых в базе данных операций. К этим операциям относятся:

- поиск фрагмента данных (подструктуры) по образцу,

- исключение подструктуры,

- добавление подструктуры.

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

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

< имя, условие применимости, оператор>,

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

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

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

m) с точки зрения процесса, ограничивая совокупность правил, до­ступных на каждом этапе, позволяет:

- повысить эффективность процедуры проверки условий применимости правил,

- сократить объем необходимой оперативной памяти,

- упростить условия применимости правил.

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

- глобальную, относящуюся ко всей системе правил;

- локальную, относящуюся к данной группе правил;

- индивидуальную, т.е. спецификацию самого правила.

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

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

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

- различных результатов;

- путей вычисления одного и того же результата.

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

Как правило, пути решения, ведущие к разным результатам, не бы­вают совершенно разными. Чаще всего они могут быть в той или иной степени совмещены, начиная с входного состояния базы данных. Исполь­зуя это, можно строить процесс вывода так, чтобы вести одновременно несколько вариантов на одной базе. При этом для каждой пары вариан­тов некоторые фрагменты в базе данных будут общими, а другие — раз­личными. Это требует локального расслоения содержания базы данных. Каждое такое расслоение представляет собой совокупность альтернатив­ных состояний соответствующего участка базы данных. Фрагменты ба­зы данных, входящие в одну такую совокупность, несовместимы меж­ду собой, поскольку относятся к разным " конкурирующим" вариантам обработки. Таким образом, процесс вывода, осуществляемый интерпре­татором, может быть одно- или многовариантным. В последнем случае в структуру базы данных вводится специальный аппарат, устанавлива­ющий совместимость и несовместимость ее фрагментов друг с другом. При завершении многовариантного процесса в базе данных остаются ре­зультаты всех вариантов вывода.

⇐ Предыдущая11121314151617181920Следующая ⇒

Поделиться:

Популярное:

1. F. ЦИФРОВЫЕ СИСТЕМЫ РАСПРОСТРАНЕНИЯ
2. II. Проверка и устранение затираний подвижной системы РМ.
3. II.2. Локальные геосистемы – морфологические единицы ландшафта
4. IV. 7.Применение физических методов охлаждения.
5. IV. Падение отработочной системы.
6. А. Бытовая рознь и признаки личной или племенной системы в истории нашего права. - Черты прошлого в современном праве. - Сходство и общность права
7. Автоматизированные информационные системы органов прокуратуры РФ
8. Автоматизированные информационные системы судов и органов юстиции
9. Автоматизированные обучающие системы
10. Автоматизированные системы управления затратами
11. АВТОМАТИКА И АВТОМАТИЗИРОВАННЫЕ СИСТЕМЫ УПРАВЛЕНИЯ ТЕХНОЛОГИЧЕСКИМИ ПРОЦЕССАМИ
12. АГЕНТЫ, МНОГОАГЕНТНЫЕ СИСТЕМЫ, ВИРТУАЛЬНЫЕ