Исследование и описание предметной области

На данном этапе выполняется следующее:

· определяется класс решаемых задач (целевое назначение системы);

· выделяются объекты предметной области и устанавливаются связи между ними;

· выявляются особенности предметной области.

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

1. Исправен ли автомобиль? Если нет, то что именно неисправно?

2. Как устранить неисправность?

3. Следует ли обратиться для устранения неисправности на станцию технического обслуживания?

4. Как предупредить подобную неисправность в будущем?

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

Например, исходную задачу «Исправен ли автомобиль?» можно разбить на подзадачи:

1. Исправна ли система питания?

2. Исправна ли система зажигания?

3. Исправна ли система охлаждения?

4. Исправна ли тормозная система?

и т.д. Это нисходящий метод описания — от абстрактного (общего) к конкретному.

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

· достаточно точное отражение реальности (адекватность модели);

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

Среди известных типов представления задач можно выделить следующие.

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

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

О ^* = о₁, о₂,..., о_к ,

 

порождающая s^* = о_к(о_к-1(... (о₂(о₁(s^o)))...)),

где s^* — некоторое состояние из множества целевых состояний;

s^o — некоторое состояние из множества начальных состояний.

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

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

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

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

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

Следующим шагом после определения и структуризации целевого назначения системы является выделение объектов предметной области и установление связей между ними. Эта фаза исследования и описания предметной области в наибольшей степени зависит от содержания предметной области и специфики рассматриваемых для нее задач. В качестве способов определения базовых понятий предметной области можно использовать введение их посредством интенсионала или экстенсионала [21].

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

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

Совокупность выделенных объектов (понятий) предметной области должна быть достаточно полной с точки зрения класса рассматриваемых задач и непротиворечивой. Связи между объектами должны быть выявлены по возможности все.

В качестве особенностей предметной области можно рассматривать:

· перекрытие некоторых признаков (фактов) другими;

· скачкообразное изменение отдельных признаков (в зависимости от внешних условий);

· трудность или невозможность анализа ряда признаков;

· вероятность сбоев используемого оборудования.

 

 

5.2. Организация модели представления
и формализация знаний

Любое «осмысленное» поведение искусственной системы в условиях реального мира требует наличия у нее определенным образом организованной модели этого мира. В надежной и гибкой ЭС в основе такой модели, очевидно, должны лежать различные виды представления знаний: продукционные правила, фреймовые структуры, семантические сети.

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

· структурная иерархия;

· причинно-следственная иерархия;

· функциональная иерархия.

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

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

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

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

 

Приобретение знаний

Знания системы могут формироваться на основе:

· рекомендаций эксперта;

· аналогий;

· примеров;

· наблюдений, открытий и экспериментов;

· умозаключений на базе глубинных представлений.

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

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

Указанным требованиям при описании знаний продукционного типа на инфологическом уровне в достаточной степени удовлетворяет традиционное дерево решений [13, 17]. Это бинарная древовидная структура с вершинами двух типов:

· вершины условий (типа «овал»), из которых могут исходить только две ветви (одна – по «Да», другая – по «Нет»);

· вершины выводов (типа «прямоугольник»), имеющие единственный выход (обязательно на вершину условия) для промежуточных выводов и не имеющие выхода (не продолжающие логику рассуждений) в случае окончательного вывода.

 

 

Каждая вершина условия содержит некоторое высказывание, которое может принимать значения «Истина» или «Ложь» (соответствует выходам по «Да» или «Нет»). Вершина вывода содержит одно или несколько предложений, описывающих некоторое промежуточное или окончательное заключение в виде набора фактов или ссылок на определенные действия. Корень дерева обозначается как вершина условия (овал), содержащая высказывание, с которого начинается процесс логических рассуждений.

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

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

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

· вершины-овалы до ближайшей вершины-прямоугольника, начиная с вершины-овала корня дерева;

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

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

В качестве примера приведем два правила из числа сгенерированных для фрагмента знаний, представленного на рис. 3:

ЕСЛИ Двигатель = не заводится И Искра = есть ТО Неисправна = система питания

ЕСЛИ Неисправна = система питания И Бензин = есть И Бензин в карбюратор = не поступает ТО Неисправность = в бензонасосе

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

Избавиться от указанных недостатков позволяет введение понятия графа решений [5].

Граф решений представляет собой ориентированный помеченный граф с вершинами двух типов:

· вершины условий (типа «овал»), из которых могут исходить несколько ребер (по «Да» или «Нет» со своими коэффициентами уверенности, помечающими эти ребра);

· вершины выводов (типа «прямоугольник»), имеющие один вход и один выход (обязательно на вершину условия) для промежуточных выводов и не имеющие выхода (не продолжающие логику рассуждений) в случае окончательного вывода.

Каждая вершина условия (вершина-овал) содержит некоторое высказывание, которое может принимать значения «Истина» или «Ложь» с различными коэффициентами уверенности (каждому коэффициенту уверенности соответствует помеченный им выход).

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

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

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

Пример описания в виде графа решений фрагмента знаний из проблемной области представления задач в нейросетевом базисе приведен на рис. 4.

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

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

 

 

ВОПРОСЫ И ЗАДАНИЯ ДЛЯ САМОКОНТРОЛЯ

 

1. Из каких основных этапов складывается циклический процесс построения базы знаний?

2. Какая последовательность действий выполняется на этапе исследования и описания предметной области?

3. Какими основными критериями руководствуются при выборе того или иного представления задач, на которые ориентируется система?

4. Какие типы представления задач Вы знаете? В чем состоит их суть?

5. При выделении объектов предметной области и установлении связей между ними необходимые понятия могут вводиться посредством интенсионала или экстенсионала. Чем различаются эти два способа определения понятий?

6. Что может рассматриваться в качестве особенностей предметной области?

7. Какие виды иерархий могут приниматься за основу при структуризации целевого назначения системы и организации модели представления знаний? В чем суть этих иерархий?

8. Какие источники приобретения знаний Вы можете назвать?

9. Что собой представляет дерево решений как формализм описания знаний на инфологическом уровне?

10. Изложите основные принципы трансформации дерева решений в эквивалентный набор продукционных правил.

11. В чем состоит суть понятия графа решений как обобщения понятия дерева решений?

12. Какие технологии могут быть использованы для приобретения знаний на основе аналогий, примеров, наблюдений, экспериментов и умозаключений на базе глубинных представлений?

 

 

6. МЕХАНИЗМЫ ИНТЕРПРЕТАЦИИ ЗНАНИЙ

 

6.1. Интерпретация логических моделей представления знаний,
основанных на исчислениях

 

Автоматическое доказательство теорем в исчислениях высказываний и предикатов первого порядка как одно из направлений исследований в области искусственного интеллекта [20] берет свое начало в работах французского математика Ж. Эрбрана. В 1930 году он предложил механическую процедуру доказательства общезначимости для формул, которые действительно общезначимы. Однако шестью годами позже американский математик А. Чёрч показал, что в случае произвольной функции эффективной процедуры решения данной проблемы не существует. Поэтому исчисления высказываний и предикатов первого порядка называют полуразрешимыми.

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

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

Теорема 1. Формула является логическим следствием формул тогда и только тогда, когда формула

(6.1)

общезначима. При этом формула (6.1) называется теоремой, а – заключением теоремы.

Теорема 2. Формула является логическим следствием формул тогда и только тогда, когда формула

(6.2)

противоречива (невыполнима).

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

Надо заметить, что с практической точки зрения удобнее доказывать невыполнимость формулы (6.2), которая, как правило, и берется за основу. Однако в случае использования исчисления предикатов первого порядка, прежде чем перейти к этому, необходимо привести (6.2) к так называемой Сколемовской стандартной форме (ССФ) [8], т.е. конъюнкции дизъюнктов, объединенных кванторами общности:

, (6.3)

где — дизъюнкты;

— предметные переменные, входящие в дизъюнкты.

К виду (6.3) может быть приведена любая синтаксически правильная формула исчисления предикатов первого порядка. Делается это последовательным применением алгоритма приведения исходной формулы к равносильной пренексной нормальной форме (ПНФ), алгоритма Сколема приведения ПНФ к "-формуле с сохранением свойства ее невыполнимости (если исходная формула была таковой) и алгоритма приведения бескванторной составляющей "-формулы к конъюнктивной нормальной форме (КНФ).

Далее при доказательстве невыполнимости формулы (6.3) можно оперировать понятием множества дизъюнктов , понимая под невыполнимым множеством невыполнимость формулы (6.3).

С помощью предложенной Ж. Эрбраном механической процедуры [8, 16, 20] проверка невыполнимости множества дизъюнктов осуществляется на множестве интерпретаций, называемом универсумом Эрбрана. Это множество, формируемое в виде последовательности по следующему закону: — множество констант, появляющихся в множестве дизъюнктов (если таковых нет, то в включается некоторая константа , т.е. ); где — все встречающиеся в n -местные функциональные символы, — элементы множества ; — i -й уровень , — универсум Эрбрана.

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

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

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

Надо заметить, что число генерируемых и исследуемых фундаментальных примеров дизъюнктов экспоненциально растет с увеличением номера i задействованного уровня универсума Эрбрана. Кроме того, использованный Гилмором в реализации процедуры мультипликативный метод приведения КНФ к ДНФ (для исследования формируемых множеств фундаментальных примеров на невыполнимость) оказывается чрезвычайно неэффективным.

Сформулированный в 1965 году Дж. Робинсоном принцип резолюции определил по сути новое направление развития теории автоматического доказательства теорем. В качестве отправной посылки данного направления можно рассматривать лемму: если в КНФ входят дизъюнкты и , представимые в виде , , то логическим следствием этих дизъюнктов является дизъюнкт , называемый резольвентой формул и .

Вхождения атома в и называются контрарными. Резольвентой однолитерных дизъюнктов и является пустой (ложный) дизъюнкт, обозначаемый символом «».

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

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

Являясь более эффективным по сравнению с процедурой Эрбрана, принцип резолюции отличается сложностью реализации механизмов выделения контрарных пар и формирования нужных (не бесполезных) резольвент. В его многочисленных модификациях [8, 16] для рационального управления выводом стараются использовать всевозможные эвристические приемы, семантику рассматриваемой предметной области, удаление порождаемых общезначимых дизъюнктов, вычеркивание поглощенных и чистых (состоящих из литер, отрицания которых отсутствуют в ) дизъюнктов.

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

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

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

Как способ повышения эффективности линейной резолюции, не нарушающий ее полноты, можно рассматривать упорядочение литер в дизъюнктах в виде последовательности, определяющей их старшинство в порядке возрастания слева направо. Вывод на упорядоченных дизъюнктах с фиксацией информации о резольвированных литерах (линейный упорядоченный вывод – OL-вывод) [8] отличается простотой его организации из-за отсутствия на каждом шаге неопределенности в выборе одного из резольвируемых дизъюнктов и исключения потребности хранения промежуточных дизъюнктов, получаемых в процессе вывода.

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

В отличие от рассмотренных модификаций метода резолюции, имеющих экспоненциальную верхнюю оценку временной вычислительной сложности, принцип резолюции на хорновских дизъюнктах (дизъюнктах, каждый из которых содержит не более одной позитивной литеры) позволяет построить алгоритм, реализующий линейную упорядоченную входную резолюцию (так называемую SLD-резолюцию), с полиномиальной оценкой вычислительной сложности. Именно она используется в универсальном языке логического программирования ПРОЛОГ.

Получить более детальное представление о рассмотренных и многих других алгоритмах доказательства теорем на основе метода резолюций можно обратившись к источникам [8, 16].

 

6.2. Интерпретация знаний
в экспертных системах продукционного типа

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

Причинами высокой популярности ЭС продукционного типа являются:

· совпадение во многом схемы их функционирования со схемой мышления специалиста при решении задач;

· единообразие структуры (возможность построения и использования оболочек);

· модульность базы знаний.

Структура экспертной системы продукционного типа представлена на рис. 5.

Основные информационные и программные сос