Главная | Обратная связь

Представление знаний

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

Если рассматривать знания с точки зрения проблем ИИ, то удобно выделить 2 категории знаний:

· Фактические знания (факты, известные при описании предметной области)

· Правила (знания о способах использования фактов для принятия решения)

Под фактами понимают высказывания, правила подразумевают логические выражения вида «если А то В».

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

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

При выборе модели представления знаний следует учитывать:

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

· Простота понимания, приводит к возможности оперативной модификации знаний.

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

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

Правило – это импликация, которой соответствует «если А истинно, то В истинно», т.е. A®B, где A - посылка, В – заключение.

Вывод заключается в применении дедуктивного метода, известного со времён Аристотеля:

«Если А и В истинные, то А может быть элементарным или составным. Составное высказывание может включать конъюнкцию, дизъюнкцию, либо отрицание (ØA₁ÚA₂ÙA₃). Высказывание В может быть только элементарным».

Пример: Выбор транспортного средства для поездки на отдых.

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

Правила:

1. Если намерение – отдых, и дорога ухабистая, то использовать джип.

2. Если место – горы, то дорога ухабистая.

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

1. y₁₁ Ù y₁₂ ® З₁

Y_ij = f_r,

Первому элементарному высказыванию соответствует факт в рабочей памяти

Y₁₁ = f₁

Y₁₂ ¹f₂ – для 2^ого нет факта в рабочей памяти.

1^ое заключение оказывается ложным. Соответствующий факт не включается в рабочую память. Для второго правила элемент высказывания имеет соответствие 2^ого факта.

 

2. Y₂₁=f₂, З₂ = true

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

Тогда, 1^ое правило также имеет истинную часть. В результате, на 3^ем шаге:

 

3. З₃ = true

Заключительной гипотезой будет использовать джип.

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

 

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

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

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

Лекция №5

 

В примере, рассмотренном ранее, можно добавить ещё одно правило -

3) Если намерение отдых, то одежда спортивная.

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

Если же применить стратегию обратного вывода ,то правило 3) не будет рассматриваться вообще ,так как его заключение не содержит основной цели, и не одной из подцелей правила 1). Если в БЗ будет содержаться правило 4),

4) Если место лес, то дорога ухабистая.

То возникает возможность для подтверждения подцели «дорога ухабистая» использовать правила 1) и 4).

Простейшим способом разрешения таких конфликтов является осмысленное расположение правил, то есть порядок их следования в БЗ.

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

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

Возникает желание использовать одно и тоже правило к некоторому множеству однотипных ситуаций.

Одним из методов достижения такой цели , является структурирование правил. Такой способ обеспечивает возможность более эффективного управления выводом. Распространённым методом структурирования является представление данных в виде триад О-А-З , где О-объект , А-атрибут, З-значение.

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

Можно создать правило, которое будет применимо ко всем собакам независимо от их кличек. Такой метод описания правил используется в OPS – инструментальное средство построения продукц. систем, с помощью которых разработаны такие ЭС , как XCON, которые применяются фирмой DEC для аппаратной конфигурации вычислительной техники.

Рабочая память содержит элементы WME (work memory element). Описание такого элемента имеет следующую структуру:

 

 

РП

_________________

WME

 

(объект ^ атрибут 1 значение ^ атрибут 2 значение … ^ )

Каждый такой элемент представляет собой образец для описания фактов, либо условий в продукционном правиле.

Правило продукции имеет структуру:

Р- название

условную часть WME1, WME2, …

заключительную часть WME . (консеквент)

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

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

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

Пример продукционного правила :

«Найти инструмент»

База знаний.(БЗ)

В качестве образцов элементов используется образец проект

(проект ^цель «х»)

который преследует достижение цели х. Имеется описание програмного средства с определённым именем (ПО ^ имя «у» ^ цель «х»), которое можно применить для достижения цели х.

Заключительная часть памяти создаёт в рабочей памяти элемент с именем «инструмент», который в качестве атрибута имеет имя програмного средства.

→ инструмент^ имя «у»

Рабочая память.(РП)

Внесём в РП элементы, которые описывают програмные средства:

1.ПО ^ имя OPS ^ цель ЭС

2.ПО ^ имя Clipper ^ цель БД

Внесём элемент с именем «проект»

3.Проект ^ цель ЭС

При рассмотрении правила продукции первого образца, будет сопоставлен элемент 3. из РП.

При рассмотрении правила продукции второго образца, из РП могут бытть найдены первый и второй элементы. Первый в качестве атрибута «цель» имеет описание «ЭС», что будет соответствовать использованному в правиле образцу. Этот элемент и будет выбран. Необходимо произвести подстановку элемента у в значение описания продукционного элемента. Будет сгенерирован в РП новый элемент называемый

4. инструмент ^имя OPS(описание продукции системы)

{ х / ЭС }

{ у / OPS}

При описании БЗ важное значение имеет правильное расположения порядка следования правилам и высказываниям условной части, так как такой порядок непосредственно влияет на эффективность логического вывода.

Одним из способов, позволяющих параллельно проектировать БЗ и будущую стратегию вывода, является визуальное представление схемы описания продукционных связей. Такая схема называется «И- ИЛИ- дерево».

Правило продукции – представляет собой отношения вывода, устанавливаемые между содержимым РП и заключениями.

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

 

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

 

 

На нижнем уровне расположены факты с помощью которых образован ряд правил. Первое и второе правила основаны на них. В результате доказываются гипотезы Н1 и Н2 , которые потом используются в правилах 3 и 4. На основании правил 3 и 4 доказывается заключение Y1, которых может быть множество.

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

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

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

Эта проблема состоит из нескольких частных проблем:

· анализ сигналов звуковых колебаний с датчика и выделение, на основании этого анализа фонем?

· анализ фонем и выделение слов

· анализ слов и выделение (построение) фраз, предложений.

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

 

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

Анализ звуковых сигналов происходит методом прямого вывода, в результате которого генерируется несколько фонем, которые затем используются при попытке определения слова. Если такая попытка оказывается неудачной, то происходит поиск обратным методом, и генерируются подцели в виде фонем. Т. е. Используя прямой и обратный поиск обеспечивается использование правил каждого из источников знаний. Такой метод реально реализован в системе распознавания речи Hearsay. Такая система была использована для вывода команд в систему управления боевыми операциями (сер. 80-х годов).

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