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

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

По существу, все математические процедуры, приводящие к решению тех или иных задач, основаны на алгоритмах. Попытка уйти от интуи­тивного понимания алгоритма привела к ряду математических уточне­ний этого понятия. Наиболее известные среди них — машина Тьюринга, машина Поста и нормальные алгоритмы Маркова [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].