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

Основной характеристикой ИИ-систем является способность подобно человеку рассуждать и делать разумные выводы. Это свойство обусловлено, прежде всего, наличием информационной компоненты, именуемой базой знаний (БЗ), и содержащей в некотором формализованном виде знания человека о предметной области. Существует несколько определений знания: 1. По Поспелову: З. – это данные, обладающие свойствами: Активности (данные пассивны, знания сами выбирают метод для обработки самих себя), Внутренней интерпретируемости (Знания поименованы), Структурированности (Знания определены отношениями: Часть-Целое, Абстрактное- Конкретное), Связности (Знания определены причинно-следственными отношениями: ЕСЛИ-ТО), Семантической определенности (Знания имеют смысловое содержание). Ж.-Л. Лорьер (J.-L. Lauriere) выделяет восемь основных уровней знаний по следующим признакам: 1. Базовые элементы, объекты реального мира. Они связаны с непосредственным восприятием, не требуют обсуждения и добавляются к базе фактов в том виде, в котором они получены. 2. Утверждения и определения. Основаны на базовых элементах и рассматриваются как достоверные. 3. Концепции. Знания этого уровня представляют собой обобщения базовых объектов. То есть, пользуясь терминологией объектно-ориентированного программирования, их можно определить как классы объектов реального мира, обладающих некоторой общностью свойств. 4. Отношения. Посредством знаний данного уровня выражаются отношения между объектами, а также концепциями. Кроме того, к свойствам отношений относятся их большее или меньшее правдоподобие, большая или меньшая связь с данной ситуацией. 5. Теоремы и правила перезаписи. С точки зрения формальной логики теоремой называется формула Mn, являющаяся последней в цепи формул M1, M2,... Mn, причем формула Mi является либо аксиомой (утверждением, определением), либо логически выводима из предшествующей ей формулы Mj (j<i). Фактически теоремы являются частным случаем продукционных правил. 6. Алгоритмы решений. Они необходимы для выполнения определенных задач. Это знания особого типа, где определяемая алгоритмом последовательность действий оформлена в отдельный модуль. Использование чистых алгоритмов ограничено очень частными случаями, большая часть которых имеет дело с обработкой числовой информации. 7. Стратегии и эвристики. Этот тип представляет собой врожденные или приобретенные правила поведения, которые позволяют в конкретной ситуации принимать решения о необходимых действиях. 8. Метазнания. Сюда относятся вопросы организации каждого типа знаний и указания, как и когда они могут быть использованы. Кроме того, метазнания присутствуют на многих уровнях и определяют значения коэффициента доверия того или иного знания. Необходимость использования знаний человека-эксперта ставит вопрос о составе и методах представления знаний. Можно выделить следующие основные методы (формы) представления знаний: представление знаний в виде продукционных правил; формальные логики (исчисление высказываний и исчисление предикатов первого порядка); представление знаний в виде семантических сетей; фреймовые системы.. Методы представления знаний. Существует много способов представления знаний. Фундаментальное различие между ними в простоте модификации знания. Представление знаний в виде продукций: На языке искусственного интеллекта термин правило имеет более узкое значение, чем в обычном словоупотреблении. Он относится к популярному способу представления знаний, то есть способу представления знаний, основанному на правилах, или иначе, на правилах продукции, на продукциях. Правила обеспечивают формальный способ представления рекомендаций, указаний и стратегий; они часто подходят в тех случаях, когда предметные знания возникают из эмпирических ассоциаций, накопленных за годы работы по решению задач в данной области. Правила выражаются в виде утверждений типа ЕСЛИ - ТО. Продукционное правило представляет собой выражение вида: УСЛОВИЕ --> ДЕЙСТВИЕ, в котором левая часть (антецедент) описывает определенную ситуацию, а правая (консеквент) - действие, выполнение которого предполагается в случае обнаружения ситуации. В системах, основанных на правилах, предметные знания представляются набором правил, которые проверяются на группе фактов о текущей ситуации. Когда часть правила ЕСЛИ удовлетворяет фактам, выполняется действие, указанное в части ТО. Сопоставление фактов с предпосылками, содержащимися в первой части правила ЕСЛИ, порождает цепочку логического вывода (часто предпосылки называют образцами, а сам процесс - сопоставлением с образцами). Существует два способа использования правил; один называется прямой цепочкой вывода (иначе, поиск от данных), другой - обратной цепочкой вывода (поиск от целей). При организации прямой цепочки вывода в качестве действия правила (ТО) могут использоваться процедурные знания, именуемые модулями, управляемыми образцами. При обратной цепочке вывода приемлемы только декларативные знания, а такую организацию поиска решения можно назвать эвристикой. Продукционную систему можно представить следующим образом: Рабочая Память содержит предпосылки (факты) о конкретной ситуации, База Правил – правила, описывающие предметную область. Различают конкретные и абстрактные правила. В первом случае, предпосылка правила представляет собой указание конкретного факта рабочей памяти, во втором - любого факта, свойства которого удовлетворяют условиям правила. В этом случае, факты о предметной области представляются в виде объект-атрибут-значение, что является некоторым подобием предиката. К отличительным свойствам продукционных правил относятся возможности учета разнообразных коэффициентов уверенности (мер доверия) как самих правил, так и используемых фактов.Достоинства: Модульность (знания не упорядочены), Простота модифицируемости (правило легко корректировать), Простота объяснения (цепочка правил), Эффективность. Недостатки:Трудность составления правила – человек не мыслит так конкретно.Представление знаний в виде неточных продукционных правил: Пусть имеется H = { Hi } - множество целей (гипотез), которые необходимо оценить и C = { Cj } - множество понятий или условий (свидетельств), на базе которых производится эта оценка.Тогда в качестве базы знаний используется множество правил вида:Cj --> Cj+1 и Cj+1 --> Hi.Такие правила очень похожи на теоремы, а цепочка правил, связанных через посылки и заключения (Cj-->Cj+1 и Cj+1-->Hi), напоминает дедуктивное доказательство. Можно считать, что способом получения логического вывода является правило modus ponens:(C,C-->H ==> H).В качестве достоинств продукционных систем отмечается возможность использования вероятностных характеристик, задающих коэффициент уверенности или меру доверия правила. При этом значение любой логической переменной: гипотезы или факта, в общем случае, есть вероятностная величина и лежит в диапазоне [0,1]. Использование неточных знаний предполагает наличие специальных математических механизмов.Такие механизмы должны отражать следующие моменты:A. Выбор свидетельства.B. Выполнение продукционных правил, содержащих в качестве предпосылки выбранное свидетельство.C. Проверка окончания логического вывода.Итак, имеется:{ Hi } - множество гипотез (i=1,n). После выполнения k правил продукции (k шагов, итераций) Hi можно охарактеризовать значением Pк(Hi), которое представляет собой вероятность i-ой гипотезы после k итераций. Значение Po(Hi), то есть на нулевом шаге, является априорной информацией о гипотезе и устанавливается на этапе создания базы знаний.{ Cj } - множество свидетельств (j=1,m), каждое из которых характеризуется вероятностью P(Cj).Метод 1. В основе данного метода лежит теорема Байеса, в соответствие с которой и происходит вычисление апостериорных вероятности гипотезы Hi в случае наступления событий (подмножества свидетельств { Cj }), которые подтверждают или опровергают правильность указанной гипотезы.Каждой импликации Cj-->Hi ставится в соответствие пара значений, характеризующих "силу" этого отношения:R(Cj:Hi) - статистическая частота появления j-го свидетельства при свершении гипотезы i.R(Cj:~Hi) - статистическая частота появления j-го свидетельства при отсутствие гипотезы i.A. Выбор свидетельства. Используется подход, известный как метод цен свидетельств (ЦС). Согласно ему наилучшим считается свидетельство, имеющее наибольшее значение показателя ЦС, который определяется как сумма влияний свидетельства на все множество гипотез. Влияние на гипотезу вычисляется как абсолютная разность между вероятностями гипотезы при наличие и отсутствие свидетельства:¦ Pк+1(Hi:Cj) - Pк+1(Hi:~Cj) ¦, где Pк+1(Hi:Cj), Pк+1(Hi:~Cj) - значения вероятностей, которые будут достигнуты i-ой гипотезой на следующем (k+1) шаге в случае наличия и отсутствия j-го свидетельства соответственно (формулы 1 и 2). Тогда ЦСк(Cj) = å_i ê Pк+1(Hi:Cj) - Pк+1(Hi:~Cj) ê, где ЦСк(Cj) - цена j-го свидетельства на текущем (k) шаге. А индекс наилучшего свидетельства: j = index max (ЦСк(Cj)). B. Выполнение всех правил продукции, содержащих в качестве антецедента свидетельство j, осуществляется по cледующим формулам.1.Вычисляется вероятность гипотезы i при наличие свидетельства j, 2.Вычисляется вероятность гипотезы i при отсутствие свидетельства j, 3.Учитывается вероятность наличия свидетельства j. C. Установление факта окончания логического вывода происходит в случае, если выполняется одно из правил: 1. Все множество свидетельств определено. 2. Имеется такая гипотеза, наименьшая достижимая вероятность PPmin которой не меньше наибольшей достижимой вероятности PPmax любой другой гипотезы, а также заданной пороговой величины. Метод 2. В ЭС MYCIN Шортлиф (Shortliffe) предложил использовать в качестве коэффициента уверенности правила некоторую вероятностную величину q. При этом после применения правила новое значение вероятности объекта доказательства вычислялось по формуле p + (1 - p) * q. Эта нестрогая, в смысле научного обоснования, формула тем не менее является одним из вариантов учета неточных продукционных отношений. Для этого каждому продукционному правилу соответствует некоторая эмпирическая величина Q(Hi:Cj), которая может быть интерпретирована как вероятность подтверждения i-ой гипотезы при наличие j-го свидетельства. A. Выбор свидетельства представляет собой подход с ценами свидетельств и аналогичен процедуре выбора по методу 1. B. Выполнение всех правил продукции, содержащих в качестве антецедента свидетельство j, осуществляется аналогично с предыдущим методом. C. Установление факта окончания логического вывода происходит в случае, если выполняется одно из правил: 1. Все множество свидетельств означено. 2. Имеется такая гипотеза, текущая вероятность Pк которой не меньше наибольшей достижимой вероятности PPmax любой другой гипотезы, а также заданной пороговой величины. Оба метода аналогичны по своим возможностям. Отличие состоит в том, что в первом случае для учета неточности правил необходимы достоверные статистические данные, получить которые в общем случае довольно затруднительно. Упрощенный характер второго метода предполагает использование эмпирических зависимостей. Представление знаний с использованием семантических сетей. В основе сетевых моделей этого типа лежит конструкция, названная семантической сетью. Сетевые модели формально можно задать в виде Н = < I, C1, C2,..., Cn, Г>. Здесь I есть множество информационных единиц, С1, С2,... - мн-во типов связей между информационными единицами. Отображение Г задает между информационными единицами, входящими в I, связи из заданного набора типов связей. В зависимости от типов связей, используемых в моделях, различают классифицирующие сети, функциональные сети и сценарии. В классифицирующих сетях используется отношение структуризации. Такие сети позволяют в базах знаний вводить иерархические отношения между информационными единицами (абстрактное-конкретное, часть-целое). Функциональные сети часто называют вычислительными моделями, так как они позволяют описывать процедуры "вычислений" одних информационных единиц через другие. В сценариях используются отношения типа "средство-результат", "орудие-действие". Если в сетевой модели допускаются связи различного типа, ее называют семантической сетью. Основным недостатком сетей является сложность обработки исключений, что связано с проблемой управления наследованием. Семантика (в общеупотребимом понимании) есть значение, смысл слова или действия, переданное с помощью каких-либо представлений и выражений. Семантика (в ИИ) означает определенные отношения между символами и объектами, представленными этими символами. Семантическая сеть задумана как модель структуры долговременной памяти Человека (принятой в психологии). Теория фреймов. В 1975 году Минский дал подробное изложение теории фреймов. Теория фреймов относится к психологическим понятиям, касающихся понимания того, как мы видим и слышим. Для того, чтобы идентифицировать информацию, полученную человеком извне, человеческая память должна быть способна увязывать эту информацию со специальными концептуальными объектами. В основе теории фреймов лежит восприятие фактов посредством сопоставления полученной информации с конкретными элементами и значениями в рамках, ограничивающих некий концептуальный объект в человеческой памяти. Структура, представляющая эти рамки, получила название фрейм. Поскольку между различными элементами имеются некоторые аналогии, то образуется иерархическая структура отношений "абстрактное-конкретное". Сложные концептуальные объекты могут быть определены комбинацией нескольких фреймов. В этом случае, можно сказать, что объект представлен фреймовой сетью. Суть теории заключается в следующем. Когда человек попадает в новую ситуацию, он вызывает в своей памяти основную структуру, именуемую фреймом. Фрейм – это единица представления знаний, запомненная в прошлом, детали которой при необходимости могут быть изменены согласно текущей ситуации. Фрейм представляет собой структуру данных, с помощью которой можно, например, описать обстановку в комнате. Каждый фрейм может быть дополнен различной информацией. Эта информация может касаться: способов применения данного фрейма, последствий этого применения, действий, которые надо выполнить, если прогноз не оправдался. Каждый фрейм можно представить как сеть, состоящую из нескольких вершин и отношений. На верхнем уровне находится фиксированная информация. На последующих уровнях располагаются терминальные вершины, именуемые слотами, которые обязательно должны быть определены конкретными значениями. Значением слота могут быть любые данные (числа, соотношения, тексты, ссылки на другие слоты). В качестве значения слота может выступать набор слотов более низкого уровня. В качестве значений слотов могут использоваться не только численные значения, но и указатели на другие фреймы, присоединенные процедуры и т.д. Так, фреймовые системы часто используют для анализа видимого объекта. При этом, различные фреймы одной системы описывают некий объект с различных углов зрения. И переход от одного фрейма к другому означает переход от одного угла зрения к другому. Здесь, рассматривая арку с точки зрения справа, видны только перекрытие и один столб. Отсутствие второго столба можно компенсировать, вызвав из памяти точку зрения анфас. Отличие фреймовых моделей в том, что в них фиксируется жесткая структура информационных единиц, которая называется протофреймом. В состав протофрейма входят несколько слотов, имеющих определенные значения. Значением слота могут быть любые данные (числа, соотношения, тексты, ссылки на другие слоты). В качестве значения слота может выступать набор слотов более низкого уровня. При конкретизации фрейма происходит присвоение ему и его слотам конкретных имен и происходит заполнение слотов. На этом этапе из протофреймов получаются фреймы - экземпляры. Переход от протофрейма к экземпляру может быть пошаговым, путем последовательного уточнения значений слотов. Управление выводом во фреймовых системах осуществляется с помощью механизма управления наследованием, базирующегося на отношениях "абстрактное-конкретное". Кроме того, допустимо для этой цели использовать присоединенные процедуры: демоны и методы.