Логические системы представления знаний

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

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

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

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

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

• • логические модели;
• • системы продукций;
• • семантические сети;
• • фреймы;
• • объектно-ориентированные представления;
• • сценарии и ряд других представлений.

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

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

К основным логическим операциям относят конъюнкцию “а” (другие обозначения: “&”, “and”), дизъюнкцию “v” (другое обозначение: “or”), отрицание “-1” (другие обозначения: “ ”, “not”) и импликацию “=>”

• (другие обозначения: “о”, “then”). Таким образом,
• • всякая пропозициональная переменная есть пропозициональная формула;
• • если А - пропозициональная формула, то —>(Л) - также пропозициональная формула;
• • если А и В - пропозициональные формулы, то (А) а (В), (A) v (5), (А) => (5) - также пропозициональные формулы.

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

Таким же образом можно описать и любую формулу. То есть формула, включающая п пропозициональных переменных - это отображение {0,1}^/г —> {0,1}, которое однозначно определяется таблицей истинности, содержащей 2" строк.

Таблица 1.

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

Например, если мы знаем, что два высказывания эквивалентны: «некоторое число рационально» и «некоторое число представимо в виде дроби целых чисел», и если мы знаем, что число 3,(3) представимо в виде дроби, то мы можем заключить, что число 3,(3) - рационально. Таким образом, зная истинность некоторого правила вида Ао В и зная факт А, мы может сделать заключение об истинности В.

Рассмотрим более подробно следующую тавтологию: ((А => В) л А)^> В. Она означает следующее: если из А следует В, и А истинно, то истинно также и В. К примеру, пусть истинна импликация «Некто является человеком (А) =^> он смертен (5)». И пусть Сократ -человек (то есть А применительно к Сократу истинно), тогда истинно и В, то есть Сократ смертен. Это правило, называемое modus ponens, было примером правильных логических рассуждений еще со времен Аристотеля.

Здесь, правда, видно, что при применении логики высказываний к реальным высказываниям приходится идти на некоторую хитрость, связанную с тем, что мы говорили об истинности высказывания А применительно к Сократу, но могли говорить и про любого другого человека, то есть делали неявную подстановку. Если говорить строго, то нужно было бы сказать, что А = «Сократ - человек», В = «Сократ смертен», а тогда наш логический вывод превратился бы в следующее: мы знаем, что если «Сократ - человек», то «Сократ смертен». Мы также знаем, что «Сократ - человек». Следовательно, «Сократ смертен». Подобный вывод не представляет особого интереса в отличие от случая, когда правило А => В означает «Любой человек смертен».

Эта проблема решается в исчислении предикатов. Рассмотрим основные понятия исчисления предикатов первого порядка. Пусть М -некоторое непустое множество. Множество состоит из всех последовательностей (т,..., т^ длины к. Назовем к-местной функцией

(или функцией к аргументов) на множестве М любое отображение множества M^k в множество М.

Назовем к-местным предикатом на множестве М отображение множества M^k в множество {0,1}. То есть предикат истинен для одних последовательностей вида (т,..т^) и ложен для других.

Из переменных, обозначающих элементы множества М, а также из функций формируются термы. Формулы в исчислении предикатов формируются на основе логических операций и предикатов от термов. Например, если / и /₂ - двуместные функции (точнее, функциональные символы), то /1 (/2 (wi,^2), W3 ) - терм. Если А, В - двуместные предикаты (точнее, предикатные символы), то А(^(уп,т2),тт,}=> ^(/2(^wl,^w2)>^w3) ^_ формула.

Помимо этого в исчислении предикатов используются кванторы существования “3” и всеобщности “V”. Поясним смысл этих кванторов на примере. Пусть М - множество произвольных объектов. И пусть Человек(ти), где т&М, - это одноместный предикат, который определяется как истинный, если т - человек, и ложный в противном случае. Пусть Смертен(ти) - это тоже одноместный предикат, который может быть ложным для «вечных» объектов, а для других объектов он истинен.

Теперь запишем: Человек(т)=>Смертен(т). Это формула с одной свободной переменной т, то есть истинность формулы зависит от конкретного значения т. Если же мы хотим сказать, что данная импликация истинна для любого т, то в записи следует использовать квантор всеобщности: (/м)Человек(щ)=>Смертен(щ). Теперь на языке предикатов приведенный вывод на основе правила «modus ponens» можно представить более строго: выражение

((V/и) Человек(ти) => Смертен(лг)) л Человек(Сократ) => Смертен(Сократ) имеет истинное значение.

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

• 1. Общий факт: (7т)Человек(т)=>Смертен(т).
• 2. Частный факт: Человек(Сократ).
• 3. Вывод: Смертен(Сократ).

На языке исчисления предикатов можно представлять достаточно разнообразные знания. Рассмотрим следующий пример. Пусть М - это множество людей. И пусть заданы следующие предикаты: Родитель(/И1,»12), который истинен, если т - родитель т₂, и Мужчина(ги), который истинен, если т - мужчина, и ложен, если т - женщина. Тогда можно определить истинность для некоторых других предикатов:

• 1. (Vmj, m2 ) (Родитель(щ i ,т₂) л Мужчина(т,) <=> Отец(т i ,т₂)).
• 2. (Vт, m2 ) (Родитель(т i ,/и₂) л -iМужчина(/и i) <=> Мать(т i ,m₂))•

• 3. (Vт, m2) ((3тт,) Родител ь(тi ,mi) а Родитель(и7з,ти₂) а Мужчинами i) <=> Внук(т₂,т1)).
• 4. Аналогичным образом можно определить и все другие родственные отношения: BpaT(wi,w₂), Тетя(/П1,пг₂) и т.д.

Имея подобную систему утверждения, а также зная базовые факты Родитель(/>?1/и₂) и Мужчинами) о конкретных людях, можно логически вывести между ними прочие родственные отношения. Такой вывод обычно осуществляется методом резолюций, идея которого заключается в том, чтобы к имеющемуся набору фактов добавить отрицание утверждения, истинность которого нужно доказать, и попытаться вывести из получившегося расширенного набора фактов очевидно ложное утверждение (то есть прийти к противоречию). Резолюцией же называется тавтология

(A v С) л (В v—iC) => AvB, (8)

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

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

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

1. bool Father(Human ml, Human m2)

{ return Parent(ml,m2) && Male(ml); }

2. bool Mother(Human ml, Human m2)

{ return Parent(ml,m2) && !Male(ml); }

Однако уже реализация предиката Внук(/и₂,тИ1) не столь очевидна. Здесь либо требуется перебирать всех людей в поисках такого т^, для которого верно Родителb(mi,m₃) и Родитель(/и₃,/п₂), либо хранить в переменных, описывающих людей, некоторую дополнительную информацию, например, ссылки на родителей и детей. Иными словами, здесь оказывается необходимо в явном виде описывать процедуру получения конкретного результата.

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

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

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

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

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

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

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

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

• 1. (Vx) (Птица(х) л Обычный(х) => Летает(х))
• 2. (Vx) (Птица(х) л —i Небычный(х) => Летает(х))

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

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

Близкими к логическим представлениям, но несколько отличающимися от них, являются наборы правил, или продукционные системы. Хотя продукционные системы часто относят к представлениям знаний, под ними все же обычно подразумевают наборы правил, дополненные механизмами вывода (манипулирования знаниями). Наборы правил бывают разными, но их объединяет то, что знания в них представляются в форме продукций вида: А^>В. Здесь знак "=>" может означать логическое следование, но чаще он означает связку типа «условие-действие». При этом как условие, так и действие могут задаваться в весьма различной форме.

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

1. Х^Ху.

Это правило гласит, что для перевода в дательный падеж к данному слову нужно приписать букву "у": дом =>дому; сад => саду. Однако это правило не работает для существительных женского рода, заканчивающихся на букву "а". Для них можно ввести новую продукцию:

2. Ха^Хе.

Это правило говорит нам, что при встрече произвольной цепочки букв X, справа от которой стоит буква "а", эту цепочку нужно оставить неизменной, а букву "а" заменить буквой "е": лиса =>лисе; нора=>норе. Однако для слов женского рода, заканчивающихся на мягкий знак, эти два правила будут работать неверно. То есть нужно ввести следующую продукцию.

3. Хь^Хи.

Теперь для конкретных значений X получим: боль=>боли; соль=>соли. Но и здесь есть исключения, например, слово «рожь». Для этого слова необходимо ввести отдельную продукцию:

4. рожь => ржи.

Представим, что продукционной системе подается на вход слово «рожь». Какое из правил с истинной посылкой: первое, третье или четвертое, - к этому слову применять? Чтобы избежать неоднозначности, применяют самое первое подходящее правило из заданного набора. Однако если правило с наиболее общим условием находится выше всего, то правило с более частным условием никогда не будет применено. В связи с этим часто используется следующая эвристика: чем более частное условие у продукции, тем раньше ее нужно помещать в списке. В нашем примере порядок продукций следовало бы изменить на обратный.

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

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

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

• 1. Автомобиль не заводится и есть бензин => проверить зажигание.
• 2. Автомобиль не заводится => проверить наличие бензина.
• 3. ...

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

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

• 1. Зеленый, полосатый, вкусный => арбуз.
• 2. Желтый, кислый => лимон.
• 3. ...

Иными словами, в этом случае наборы правил служат для описания понятий из некоторой предметной области через совокупность дискретных признаков. Условия в левых частях правил могут принимать и более сложный вид, приближая эти правила к формулам исчисления предикатов. В частности, широко используются операции конъюнкции и дизъюнкции. Например, первое правило в предыдущем примере можно представить в виде: (Vx) (Зеленый(х) л Полосатый(х) л Вкусный(х) => Арбуз(х)). Однако произвольные предикаты в продукционных системах не реализуются, в частности, обычно не используется квантор существования.

Вопросы и упражнения

• 1. Перечислить основные типы представления знаний (не менее пяти).
• 2. В чем основные различия между знаниями и данными?
• 3. Какое основное преимущество имеет исчисление предикатов в качестве системы представления знаний?
• 4. Чем логика предикатов отличается от логики высказываний?
• 5. К какой проблеме искусственного интеллекта сводится проблема доказательства в рамках исчисления предикатов?
• 6. Какие задачи могут решаться с помощью наборов правил?