Точно Не проект 2 / Не books / Источник_1

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

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

Рисунок 3.5 – Прямой вывод: поиск в глубину (а) и поиск в ширину (б).

Безусловно, возможны и смешанные стратегии вывода, когда объединяются оба вида поиска – поиск в ширину и поиск в глубину, а также различные эвристические стратегии, рассмотренные в главе 2. Поскольку эти стратегии в продукционных системах связаны с правилами разрешения конфликтов, то ниже мы рассмотрим их подробнее.

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

Процесс вывода начинается с того, что в рабочую память помещается целевое утверждение Goal, истинность которого необходимо подтвердить или опровергнуть, а также множество исходных фактов {L, M, N}, которые считаются истинными утверждениями.

Удобно рассматривать переменные правил как многозначные объекты, характеризуемые тремя возможными значениями: “не определено”, “ложь”, “истина”. В этом случае начальное значение переменной Goal – “не определено”, а факты L, M, и N имеют значение “истина”.

Обратная цепочка рассуждений для рассматриваемого примера изображена на рисунке 3.6 . Здесь факты, имеющие значение “истина”, выделены курсивом. Вывод начинается с утверждения Goal, которое рассматривается как текущая подцель. Все продукционные правила, заключение которых сопоставимо с текущей подцелью, добавляются в конфликтное множество правил. На каждом шаге активизируется первое правило конфликтного множества. Посылки данного правила добавляются в рабочую память и на следующем шаге выступают в качестве новой подцели системы. Такая стратегия разрешения конфликтов соответствует поиску в ширину.

Рисунок 3.6 – Обратный вывод в продукционных системах

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

На рисунке 3.6 при активизации правила 3 устанавливается, что его посылки L и M являются фактами. Следовательно, фактом является и заключение Е. Далее, если верно Е, то верно и В (правило 8). И наконец, если верно В, то справедливо и целевое утверждение Goal (правило 11).

Рассмотренные примеры показывают, что вывод в продукционных системах в общем случае соответствует поиску решений в И-ИЛИ графах. В частном случае, когда правила-продукции не содержат в условной части конъюнкций, вывод в продукционных системах будет соответствовать поиску решений в пространстве состояний. Поэтому рассмотренные ранее методы поиска решений в пространстве состояний и в И-ИЛИ графах успешно применяются в продукционных системах. Часто в продукционных системах применяют комбинированные методы поиска решений. Например, применяют двунаправленный поиск. В этом случае сначала поиск ведут в прямом направлении до тех пор, пока число состояний не станет большим. Затем выполняется обратный поиск уже достигнутых состояний (подцелей). При такой организации поиска имеется одна опасность. Если применяются методы эвристического поиска, то, возможно, что подграфы, обследуемые в прямом и обратном направлении, окажутся разными и не “встретятся”. Это приведет к увеличению времени поиска, по сравнению с однонаправленным поиском. Этой опасности нет, если применяются методы “слепого” поиска. Тогда комбинированный метод значительно сокращает время поиска [77].

Отметим, что ситуация, когда в рабочую память заранее вносятся все известные факты, встречается редко. Обычно в рабочей памяти изначально содержится только часть фактов, необходимых для вывода. Остальные сведения продукционная система выясняет сама, задавая вопросы пользователю, опрашивая измерительные или иные подсистемы, сопряженные с ней. Например, следуя цепочке обратных рассуждений, изображенной на рисунке 3.6, система направляет поиск от цели к фактам. Когда будет активизировано правило 1, то система пытается установить, являются ли высказывания G и H фактами, т.е. приписано ли им значение “истина”. Так как значения высказываний G и H неизвестны, то система может задать пользователю вопрос, относительно истинности высказываний G и H. Получен-

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

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

Управление разрешением конфликтов. Как отмечалось выше, раз-

решение конфликтов – важная проблема, связанная с управлением порядком применения правил, образующих конфликтное множество.

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

Другими принципами, используемыми при разрешении конфликтов, являются [21]:

-принцип “стопки книг”;

-принцип наиболее длинного условия;

-принцип метапродукций;

-принцип приоритетного выбора.

Принцип “стопки книг” заключается в том, что список конфликтую-

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

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

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

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

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

3.4.Семантические сети

3.4.1.Общее понятие о семантических сетях

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

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

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

Индивидный объект – это каким-то образом выделенный единичный представитель (экземпляр) класса. Например, “сотрудник Петров И.Н.”

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

Введенная классификация объектов является относительной. В зависимости от решаемой задачи один и тот же объект может рассматриваться как обобщенный или индивидный, как агрегатный или неагрегатный.

Типы связей между объектами семантических сетей могут быть любыми. Но чаще всего применяются следующие основные связи (отношения): “род-вид”, “является представителем”, “является частью”. Наличие связи типа “род-вид” между обобщенными объектами А и В означает, что понятие А более общее, чем понятие В. Любой объект, отображаемый понятием В, отображается и понятием А, но не наоборот. Например, понятие “животное” – это родовое понятие для объекта “птица”. Все свойства родового объекта А, как правило, присущи и видовому объекту В. Иными словами, объект В наследует свойства объекта А.

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

Вряде случаев между связями “род-вид” и “является представителем” не делают различий, отмечая, что эти связи задают отношение “общеечастное” (рисунок 3.7). Иногда это приводит к недоразумениям. Поэтому для формализации таких связей будем использовать отношения ako (от англ. a-kind-of – разновидность) и is_a (от англ. is a member of the class –

быть представителем класса) [94].

Не менее важно отношение “является частью” (англ. part of). Данное отношение связывает агрегатный объект с его составными частями. Оно позволяет отражать в базе знаний структуру объектов предметной области. Иногда данное отношение обозначают меткой “имеет” (англ. has).

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

Данная сеть была разработана А.М. Коллинзом и М.Р. Куиллианом (1969) и использовалась для моделирования механизмов памяти человека. Благодаря отношениям ako сеть представляет собой некоторую иерархическую структуру и позволяет отвечать на такие вопросы, как: “Является ли канарейка птицей?”, “Может ли канарейка летать?” и т.д. В ходе экспериментов с представленной моделью было установлено, что человек стремится запоминать информацию, соответствующую наиболее абстрактному уровню. Например, вместо того, чтобы непосредственно запоминать факт “канарейка умеет летать”, человек представляет этот факт в виде свойства

исвязывает его с понятием “птица”. Аналогично свойства: “дышать”, “принимать пищу”, “перемещаться” – связываются с понятием “животное”. Такой способ запоминания информации позволяет исключить её дублирование в базе знаний благодаря наследованию свойств в соответствии с

ako иерархией. Например, свойство “иметь крылья” присуще птицам, следовательно, оно присуще и канарейке.

Рисунок 3.7 – Мир животных в виде семантической сети

Впервые семантические сети появились в области машинной лингвистики как средство анализа смысла (семантики) естественного языка. В 1967 году М.Р. Куиллианом была разработана программа, фиксирующая смысл английских слов, построенная по принципу толкового словаря. В этой программе некоторое слово английского языка определяется в терминах, выражаемых другими словами. Каждое слово определяется множеством указателей на другие слова. Совокупность указателей образует сеть, “путешествуя” в которой можно выяснить смысл того или иного слова. В семантической сети Куиллиана вершины соответствуют определяемому понятию и снабжаются указателями на другие слова, раскрывающие данное понятие. База знаний организованна в виде страниц (плоскостей), на каждой из которых представляется граф, определяющий одно слово. На рисунке 3.8 изображены три различных определения английского слова “plant”. Указатели, обозначенные на рисунке 3.8 сплошными стрелками, формируют следующие определения слова “plant”:

1)живая (live) структура (structure), которая не относится к животным (animal), часто имеет листья (leaf), получает (get) питание (food) из

(from) воздуха (air), воды (water) и почвы (earth);

2)оборудование (аппаратура – apparatus), используемое (use) для (for) реализации любого процесса (process) в (in) промышленности (industry);

3)помещать (put) нечто (seed – семя, plant – растение и т.п.) в почву

(earth) для (for) выращивания (grow).

Рисунок 3.8 – Определение слова “plant”

Первое определение (plant 1) соответствует существительному “растение”, второе (plant 2) – существительному “завод”, третье (plant 3) – глаголу “садить”. Указатели, обозначенные на рисунке штриховыми линиями, ссылаются на слова-понятия, представленные на других страницах.

Один из механизмов вывода, применяемый в рассматриваемой модели семантической сети, основан на поиске по пересечению. Он позволяет устанавливать отношения между двумя словами. Поиск выполняется методом в ширину по внешним указателям из двух исходных страниц до тех пор, пока не будет найдено общее понятие, соответствующее вершине пересечения двух направлений поиска. Найденные в результате поиска пути от исходных вершин к вершине пересечения и будут представлять отношение между исходными словами-понятиями. Например, слова-понятия “cry” (плачь, плакать) и “comfort” (утешение, утешать) приводят к пересечению путей поиска в вершине “sad” (печальный, унылый). В результате анализа путей поиска модель позволяет сделать следующее заключение:

“Плачь – это один из способов создания печальных звуков. Утешать –

делать нечто менее печальным”.

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

новые знания. Это позволяет строить системы понимания естественного языка, обладающие следующими возможностями [77]:

1)определять основной смысл текста путем поиска множества вершин пересечения;

2)осуществлять выбор необходимого значения многозначного слова на основе кратчайшего пути от этого слова к другим словам рассматриваемого предложения (своего рода семантическая метрика);

3)формировать ответы на различные запросы путем установления взаимосвязей между словами-понятиями запроса и словамипоня-

тиями, хранящимися в памяти системы.

Рассмотренный подход получил некоторое развитие в системе TLC (Teachable Language Comprehender: обучаемая система понимания языка),

разработанной Квиллианом. Однако практический успех TLC был ограничен. Это объяснялось тем, что набор используемых типов связок (отношений) между понятиями был недостаточен. Использовались только такие связки, как: “класс – экземпляр класса”, “атрибут – значение”. Кроме того, сам поиск не учитывал смысл связок. Представление знаний требует введения в рассмотрение более богатого набора отношений между понятиями (объектами, сущностями) предметной области. Дальнейшее развитие сетевых моделей представления знаний осуществлялось именно в этом направлении.

Работы Р.Симмонса и К.Филмора указали на важную роль глаголов при анализе смысла предложений естественного языка. Предложение можно представить вершиной-глаголом и различными падежными связками (отношениями). Такую структуру называют падежной рамкой. Среди падежных отношений выделяют следующие: агент – отношение между событием и тем кто (что) его совершает; объект – отношение между событием и тем, над чем выполняется действие; инструмент – объект, с помощью которого совершается действие; место – место совершения события; время

– время совершения события. При анализе предложения программа находит глагол и устанавливает соответствующие падежные отношения между частями предложения. В качестве примера на рисунке 3.9 изображена падежная рамка предложения: “Иван закрепил деталь клеем”. Падежная рамка фиксирует знания падежной (лингвистической) структуры естественных языков в виде сетевого формализма.

В соответствии с введенным ранее определением семантической сети, отсутствуют какие-либо ограничения как на типы отношений, так и на типы объектов, отображаемых в сети. В большинстве случаев многообразие объектов сети можно подразделить на три группы [29,16]:

1)объекты-понятия – сведения о физических и абстрактных объектах, предметной области;

2)объекты-события – абстрактные или конкретные действия, которые могут привести к изменению состояния предметной области;

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

Рисунок 3.9 – Падежная рамка

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

1)лингвистические отношения, которые, в свою очередь, подразделяются на падежные (агент, объект, инструмент, время, место), глагольные (наклонение, время, вид, число, залог) и атрибутивные (цвет, размер, форма и т.п.);

2)логические отношения (конъюнкция, дизъюнкция, отрицание, импликация);

3)теоретико-множественные отношения включают в себя отношения типа “множество-подмножество” (“род-вид”, “класс-подкласс”), “целое-часть”, “элемент множества” и др.

4)квантифицированные отношения, которые подразделяются на ло-

гические кванторы общности и существования, нечеткие кванторы (много, несколько, часто т.д.).

Таким образом, рассмотренные ранее отношения (“род-вид”, “быть представителем”, “быть частью”, падежные отношения) далеко не исчерпывают всего набора отношений, применяемых в семантических сетях. Но они образуют хорошую основу для построения прикладных баз знаний. Особое место при этом занимают теоретико-множественные отношения, обладающие транзитивными свойствами. Отношение R называется транзитивным, если для любых объектов , , таких, что находится в от-