А. В. Гаврилов
 Скачать 0.52 Mb.
|
|
2.3. Модальные логики Первой попыткой расширить возможности логики 1-го порядка явилось появление множества модальных логик, в которых вводились различные кван- торы (модальности) и аксиомы, отражающие тот или иной аспект реального мира. Наиболее известны модальные логики "возможного-необходимого" (але- тическая логика), деонтическая логика (модальности "разрешено- обязательно"), эпистемическая логика (логика знания-веры), временная мо- дальная логика (модальности "всегда-никогда", "часто-иногда"). Для интерпретации модальных логик возможностей предикатов, имею- щих всего два значения (двузначной семантики), было недостаточно. Поэтому, сначала появилась трехзначная логика Лукасевича (логика Лукасевича), где ло- гические переменные могут принимать значения 0, 1, 2, а затем семантика воз- можных миров (4-значная логика). Ниже приведена четырехзначная семантика возможных миров (рис. 3). Но для представления нечетких знаний модальные логики не годятся, т.к. они базируются на детерминированной семантике и являются, по существу, 24 некоторым улучшением логики предикатов 1-го порядка со всеми ее недостат- ками как метода для представления знаний. Рис 3. Семантика возможных миров 2.4. Теория нечетких множеств и нечеткая логика Для представления нечетких понятий и оперирования с ними американ- ский ученый Л. Заде в 60-х годах придумал теорию нечетких множеств, а затем – нечеткую логику, базирующуюся на ней. В основе теории нечетких множеств лежит интерпретация факта принадлежности элемента a множеству A как фак- та, который может быть истинным или ложным с некоторой оценкой истинно- сти µ A (a), пробегающей значения от 0 до 1. Эта оценка истинности называется функцией принадлежности элемента a множеству A. Операции включения и равенства в теории нечетких множеств определя- ются обычно следующим образом (по Заде): ). ( ) ( , : ) ( ) ( , : a a a G F a a a G F G F G F µ = µ ∀ = µ ≤ µ ∀ ⊆ Дополнение множества F к G определяется так, что ). ( 1 ) ( , a a a G F µ − = µ ∀ Пересечение и объединение множеств определяются следующим образом: )). ( ), ( max( ) ( , )), ( ), ( min( ) ( , a a a a a a a a G F G F G F G F µ µ = µ ∀ µ µ = µ ∀ ∪ ∩ Эти определения не единственные, хотя они не противоречат интуитив- ным представлениям о соответствующих операциях над нечеткими множест- 3 2 1 0 Не нейтрально Не нейтрально Истинно Ложно Истинное выражение Ложное выражение Случайно истинно Необходимо ложно Необходимо истинно Случайно ложно 25 вами. Частным случаем теории нечетких множеств (при µ =1 или 0) является классическая теория множеств. Однако встречаются и другие определения опе- раций над нечеткими множествами. Так же как на основе классической теории множеств строится двоичная (булева) логика, так и на базе теории нечетких множеств строится теория не- четких множеств. Она оперирует с высказываниями, для которых функция принадлежности, описанная ранее, определена на множестве истинных выска- зываний. Функция принадлежности интерпретируется как мера истинности, уверенности или достоверности и отражает нечеткость знаний. Предположим, существуют следующие высказывания: "Иванов – хороший человек" с µ =0.8, "Политик – хороший человек" с µ =0.3. Тогда конъюнкция этих двух высказываний (имеющая смысл как уточнение мнения об Иванове, когда стало известно, что он – политик) определяется функцией принадлежности µ =0.3, а дизъюнкция – µ =0.8. Можно развить логику нечетких высказываний до логики нечетких преди- катов, которая обычно рассматривается в рамках псевдофизических логик (см. 2.5). В теории нечетких множеств функция принадлежности может интерпре- тироваться как субъективное представление об истинности высказываний или объективная нечеткость знаний (информации). В первом случае описание не- четких высказываний является как бы снимком состояния некоторой интеллек- туальной системы, обученной на примерах взаимодействия с внешней средой или заполненной субъективными знаниями экспертов. Во втором случае нечет- кость является следствием каких-либо помех при поступлении информации в систему и интерпретации ее в виде знаний. В обоих случаях функцию принад- лежности можно интерпретировать как вероятностную меру истинности и применять теорию вероятности к ее обработке и анализу. Это справедливо, т.к. интеллектуальная система работает с множеством разных субъектов, имеющих разные субъективные представления об истинности высказываний, или с мно- жеством разных ситуаций, в которых разные помехи создают вероятностное описание истинности информации (знаний). 2.5. Псевдофизические логики Недостатки классической логики и основанной на ней логики предикатов первого порядка как метода представления знаний об окружающем мире при- вели к появлению псевдофизических логик. В их основе лежит представление нечетких или размытых понятий в виде так называемых лингвистических пе- ременных, придуманных Заде [9] для того, чтобы приблизить семантику (смысл) денотата (знака) к семантике, которая вырабатывается в мозгу челове- ка в процессе его обучения (опыта). Для этого множество образов (десигнатов), с которыми должна оперировать интеллектуальная система, представляется в 26 виде точек на шкалах. Например, можно рассматривать шкалы "возраст" (в го- дах), "расстояние до объекта" (в м или км) и т.п. С каждой шкалой связано множество знаковых значений лингвистической переменной. Например, со шкалой "возраст" могут быть связаны следующие значения одноименной лин- гвистической переменной: "юный", "молодой", "зрелый", "пожилой", "старый", "дряхлый". Со шкалой "расстояние" – "вплотную", "очень близко", "близко", "рядом", "недалеко", "далеко", "очень далеко", "у черта на куличиках". Взаимо- связь между этими двумя представлениями (множеством точек на шкале и множеством знаковых значений) задается с помощью функции принадлежно- сти µ x(t), где x – значение лингвистической переменной, t – значение на шкале. Значение функции принадлежности интерпретируется как вероятность того, что значение t на шкале можно заменить знаком x или наоборот. Очевидно, что можно пронормировать значения функции принадлежности в соответствии с формулой 1 ) ( = µ ∑ x x t или в соответствии с 1 ) ( = µ ∑ t x t На рис. 4 приведен пример описания лингвистической переменной воз- раст. Здесь каждая кривая описывает ее одно символьное значение. Рис. 4. Описание лингвистической переменной "Возраст" Наиболее используемыми псевдофизическими логиками являются про- странственная, временная и каузальная (причинно-следственная). На рис. 5 показана структура составляющих пространственной логики. µ "юный" "старый" "пожилой" "молодой" 1,0 0.5 10 20 30 40 50 60 70 80 27 Логики взаимного расположения объектов, расстояний и направлений де- лятся на метрическую и топологическую логики. В отличие от метрической то- пологическая логика не связана с метрической шкалой. Рис. 5. Пространственная логика Метрические шкалы подразделяются на экзоцентрические и эндоцентри- ческие, относительные и абсолютные. Экзоцентрические шкалы имеют нача- лом координат точку, связанную с самой интеллектуальной системой. Приме- ром такой шкалы является шкала для описания лингвистической переменной "Расстояние до объекта" в логике расстояний. Ее символьными значениями мо- гут быть следующие: "совсем рядом", "рядом", "очень-очень близко", "очень близко", "близко", "не очень близко", "не близко", "недалеко", "не далеко, но и не очень близко", "не очень далеко", "неблизко", "далеко", "очень далеко" и т.п. Эндоцентрическая шкала имеет началом координат точку вне системы. Приме- ром такой шкалы является шкала для описания лингвистической переменной "расстояние между двумя объектами" в той же логике расстояний. Относитель- ные шкалы имеют изменяемую точку отсчета (начало координат), а абсолют- ные – неизменную (обычно, подразумеваемую, т.е. явно не заданную). Логика направлений оперирует с понятиями "справа", "слева", "впереди", "сзади" или "на восток", "на запад" и т.п. В логике взаимного расположения объектов описываются следующие ба- зовые отношения: унарные – "иметь горизонтальное положение", "иметь вер- тикальное положение", бинарные – "находиться внутри", "находиться вне", на- ходиться на поверхности", "находиться в центре", "находиться в середине", "быть там же, где..", "быть ненулевой проекцией", "находиться в ε - окрестности", "быть частью", "находиться на одной прямой", "находиться во- круг", "быть на краю", "быть параллельно", "быть перпендикулярно", "быть симметрично", "находиться в n единицах от..", "иметь точку опоры на..", "иметь точку подвеса на..", "соприкасаться", "быть выше", "быть ниже", "нахо- Пространственная логика Динамическая логика (логика движения) Статическая логика (логика положения) Логика взаимного расположения объектов Логика местоположения объектов в пространстве Логика расстояний Логика направлений 28 диться на одинаковом уровне", "быть дальше", "быть ближе", "быть равноуда- ленными", n-арное отношение – "быть между". Из базовых отношений с помощью логических связок строятся производ- ные отношения, такие как "не соприкасаться" (отрицание "соприкасаться"), "быть вместе.." (следствие от "находиться там же.."), "висеть" (конъюнкция "иметь вертикальное положение" и "висеть на…"), "стоять" (конъюнкция "иметь вертикальное положение" и "иметь точку опоры на..") и т.п. 2.6. Правила-продукции Правило-продукция (или просто правило) в общем случае можно предста- вить в виде B, F>, где : I S P A B F – – – – – – идентификатор правила (обычно порядковый номер); область применимости; условие применимости; посылка правила; заключение; постусловие правила. A → B является ядром правила-продукции и может по-разному интерпре- тироваться. Наиболее часто используемая форма интерпретации – логическая, при которой A является множеством элементарных условий, связанных логи- ческими связками "И", "ИЛИ" и "НЕТ", B – множеством элементарных заклю- чений. При этом правило считается сработавшим (выполняется заключение B), если посылка A истинна. Другой формой интерпретации ядра является вероят- ностная интерпретация, при которой правило срабатывает с некоторой вероят- ностью, зависящей от истинности посылки. В качестве заключения обычно применяется операция добавления факта в базу данных интеллектуальной системы с указанием меры достоверности по- лучаемого факта. В качестве постусловия могут использоваться какие-либо до- полнительные действия или комментарии, сопровождающие правило. Обычно при описании баз знаний или экспертных систем правила пред- ставляются в более наглядном виде, например: ПРАВИЛО 1: ЕСЛИ Образование=Высшее И Возраст=Молодой И Коммуникабельность=Высокая ТО Шансы найти работу=Высокие КД=0.9. При срабатывании этого правила в базу данных интеллектуальной систе- мы (например, экспертной системы) добавляется факт, означающий, что шансы 29 найти работу высоки с достоверностью 0.9 или 90% (значение коэффициента достоверности КД). Понятия "Образование", "Возраст", "Коммуникабельность" служат для задания условия (в данном случае, конъюнкции), при котором сра- батывает правило. Факты хранятся в базе данных продукционной системы в форме (Объект, значение, КД) или (Объект, атрибут, значение, КД). Но могут использоваться и другие структуры для хранения фактов, такие как семантические сети или фреймы (см. 2.6 и 2.7). В этом случае говорят о комбинации разных методов представления знаний или о гибридных интеллек- туальных (экспертных) системах. При интерпретации (выполнении) правила в ходе проверки условия система проверяет факты, находящиеся уже в базе дан- ных, и, если соответствующего факта нет, обращается за ним к источнику дан- ных (пользователю, базе данных и т.д.) с вопросом (или запросом). Кроме правил в продукционных базах знаний могут использоваться мета- правила для управления логическим выводом. Пример метаправила для гипо- тетической базы знаний, пример из которой был приведен ранее: ЕСЛИ Экономика = развивается ТО Увеличить приоритет правила 1 Для представления нечетких знаний факты и правила в продукционных системах снабжаются коэффициентами достоверности (или уверенности), ко- торые могут принимать значения из разных интервалов в разных системах (на- пример, <0,1>, <0, 100>, <-1,+1>). Во втором случае можно говорить об уве- ренности в процентах, а в последнем случае – о задании коэффициентом уве- ренности меры ложности или истинности факта. Существуют разные методы обработки нечеткости при интерпретации правил. Обычно для оценки истинности условия используются правила нечет- кой логики (см. 2.3). Для оценки истинности факта, полученного при срабаты- вании правила, обычно также используется правило из нечеткой логики для оценки конъюнкции, аргументами которой являются условие и факт в заклю- чении со своими коэффициентами достоверности. Более разнообразные подходы для оценки истинности используются при формировании правилом факта, уже существующего в базе данных интеллек- туальной системы. Ниже приводятся формулы, используемые в таком случае в экспертной системе MYCIN (в ней коэффициент принадлежности пробегает значения из интервала <-1,+1>): 30 < − + < − + − > − + = , 0 * ; |) | |, min(| 1 | | | | 0 , |); | 1 ( | | | (| 0 , ); 1 ( РП ИП РП ИП РП ИП РП ИП ИП РП ИП РП ИП ИП РП ИП КД где: КД – новое значение факта, ИП – показатель истинности уже существующего факта (исходный пока- затель), РП – показатель факта, формируемый исходя из истинности условия и заключения правила (результирующий показатель). Легко проверить, что получающиеся значения не входят в противоречие с интуитивным представлением, о том, как должна меняться истинность факта при срабатывании правила, подтверждающего или опровергающего его. Достоинствами продукционного метода представления знаний являются следующие. 1. Наглядность и понятность знаний (по крайней мере, на уровне одного правила). 2. Возможность реализации немонотонного логического вывода и обра- ботки противоречивых фактов. 3. Возможность введения различных модификаций в интерпретацию пра- вил в соответствии с особенностями решаемых системой задач. 4. Возможность легкого наращивания базы знаний путем добавления но- вых правил. Недостатками этого метода представления являются следующие. 1. Необозримость большой базы знаний и ее структуры. 2. Возможность легкого внесения серьезных искажений в базу знаний, приводящих к неправильному функционированию системы (если в системе нет развитых средств проверки целостности базы знаний). 3. Ориентация на последовательную обработку правил. 2.7. Семантические сети В третий раз забросил старик не- вод. Принес невод золотую рыбку. А.С. Пушкин. Сказка о рыбаке и рыбке Семантической сетью называется ориентированный граф с помеченными вершинами и дугами, где вершинам соответствуют конкретные объекты, дугам – отношения между ними. В семантических сетях используются три основных типа объектов: поня- тия, события и свойства. 31 Понятия представляют собой сведения об абстрактных или конкретных (физических) объектах предметной области. События – это действия, которые могут внести изменения в предметную область, т.е. изменить состояние предметной области. Свойства используются для уточнения понятий и событий. Применитель- но к понятиям свойства описывают их особенности или характеристики, на- пример – цвет, размер, качество. Применительно к событиям свойства – про- должительность, место, время и т.д. Семантические отношения условно делятся на четыре класса: лингвисти- ческие, логические, теоретико-множественные и квантифицированные. К наи- более распространенным лингвистическим отношениям относятся падежные и атрибутивные отношения. Падежными (или ролевыми) отношениями могут являться следующие: − агент, отношение между событием и тем, что (или кто) его вызывает, например, отношение между "завинчиванием" (гайки) и рукой; − объект, отношение между событием и тем, над чем производится дейст- вие, например, между "завинчиванием" и "гайкой"; − условие, отношение, указывающее логическую зависимость между со- бытиями, например, отношение между "завинчиванием" (гайки) и "сборкой" (узла); − инструмент, отношение между событием и объектом, с помощью кото- рого оно совершается, например, между "завинчиванием" и "верстаком". Атрибутивные отношения – это отношения между объектом и свойством, например, цвет, размер, форма, модификация и т.д. На рис. 6 приведен пример семантической сети с использованием атрибутивных отношений. Рис. 6. Пример атрибутивных отношений Логические отношения – это операции, используемые в исчислении вы- сказываний: дизъюнкция, конъюнкция, импликация, отрицание. Теоретико-множественные отношения – это отношения между элементом множества (подмножества) и множеством, отношение части и целого и т.п. Этот тип отношений используется для хранения в базе знаний сложных (со- ставных или иерархических) понятий. Этот тип отношений иллюстрируется рис. 7. Зеленый Огурец Продолговатый Съедобный Форма Цвет Польза 32 Квантифицированные отношения – это логические кванторы общности и существования. Они используются для представления знаний типа: "любой студент должен посещать лабораторные занятия", "существует хотя бы один язык программирования, который должен знать любой выпускник НГТУ". К базе знаний представленной семантической сетью, возможны следую- щие основные типы запросов: 1) запрос на существование; 2) запрос на перечисление. Рис. 7. Теоретико-множественные отношения При построении интеллектуальных банков знаний обычно используют разделение интенсиональных и экстенсиональных знаний. Экстенсиональная семантическая сеть (или К-сеть) содержит информацию о фактах, о конкрет- ных объектах, событиях, действиях. Интенсиональная семантическая сеть (или А-сеть) содержит информацию о закономерностях, потенциальных взаимосвя- зях между объектами, неизменяемую информацию об объектах, т.е. модель ми- ра. Экстенсиональные (конкретные) знания создаются и обновляются в процес- се работы с банком данных, а интенсиональные (абстрактные) изменяются ред- ко. Первые можно назвать экземпляром, а последние – моделью (схемой) базы данных. Запрос к банку знаний, обрабатываемый системой управления базой зна- ний, представляет собой набор фактов (ситуацию), при описании которого до- пускается использование переменных вместо значений атрибутов, имен поня- тий, событий и отношений. Запрос можно представить в виде графа, в котором вершины, соответствующие переменным, не определены. Поиск ответа сводится к задаче изоморфного вложения графа запроса (или его подграфа) в семантическую сеть. Запрос на существование не содержит переменных и требует ответа типа ДА, если изоморфное вложение графа запроса в семантическую сеть удалось, и НЕТ – в противоположном случае. При обработке запроса на перечисление происходит поиск всех возможных изоморфных графу запроса подграфов в Студент Человек Млекопитающее Преподаватель Осёл Экзамен Билет Оценка Эл-класс Часть-целое Эл-класс Эл-класс Часть-целое Часть-целое 33 семантической сети, а также присваивание переменным в запросе значений из найденных подграфов. Достоинством семантических сетей является их универсальность, дости- гаемая за счет выбора соответствующего применению набора отношений. В принципе с помощью семантической сети можно описать сколь угодно слож- ную ситуацию, факт или предметную область. Недостатком семантических сетей является их практическая необозри- мость при описании модели мира реального уровня сложности. При этом появ- ляется проблема размещения семантической сети в памяти ЭВМ. Если ее раз- мещать всю в оперативной (виртуальной) памяти, на ее сложность накладыва- ются жесткие ограничения. Если размещать во внешней памяти, появляется проблема, как подгружать необходимые для работы участки. Частично эта проблема структуризации семантических сетей решается вы- делением фрагментов семантической сети, называемых обычно высказывания- ми. Ниже приводится фрагмент семантической сети, состоящей из двух выска- зываний, связанных отношением импликации (следования). Смысл этого фраг- мента семантической сети можно выразить высказыванием (рис. 8): "Если студент учится в НГТУ, значит он – умный". Рис. 8. Пример представления двух высказываний, связанных импликацией Кроме того, в семантических сетях нельзя явно задавать наследование свойств, т.к. отношение "элемент класса – класс" является одним из многих ти- пов отношений и его обработка (участие в процедуре поиска подходящих фрагментов) ничем не отличается от обработки других отношений. Эта проблема структуризации семантических сетей и необходимости за- дания в них наследования свойств привела к идее структуризации семантиче- ских сетей, приведшей к появлению концепции фреймов. НГТУ Студент Умный Где учится A B Свойство Объект Объект |