Какие предикаты обычно используются для представления свойств объектов
Для того чтобы манипулировать всевозможными знаниями из реального мира с помощью компьютера, необходимо осуществить их моделирование.
При проектировании модели представления знаний следует учесть два требования: однородность представления; простоту понимания.
Выполнение этих требований позволяет упростить механизм логического вывода и процессы приобретения знаний и управления ими, однако, как правило, создателям интеллектуальной системы приходится идти на некоторый компромисс в стремлении обеспечить одинаковое понимание знаний и экспертами, и инженерами знаний, и пользователями.
Классификация методов моделирования знаний с точки зрения подхода к их представлению в ЭВМ показана на рис. 13.1.
Дадим общую характеристику основных методов представления знаний.
Модели на основе эвристического подхода.Представление знаний тройкой «объект — атрибут — значение». Один из первых методов моделирования знаний. Как правило, используется для представления фактических знаний в простейших системах.
Примеры.
Очевидно, что для моделирования знаний даже об одном объекте (например, о «студенте» или «доме») из предметной области необходимо хранить значительное число «троек».
Продукционная модель. Модель правил; модель продукций — от англ. production — изготовление, выработка. В настоящее время наиболее проработанная и распространенная модель представления знаний, в частности в ЭС.
Модель предусматривает разработку системы продукционных правил (правил продукций), имеющих вид:
ЕСЛИ А1И А2 И … И Аn, ТО B1ИЛИ В2ИЛИ … ИЛИ Вт,
где Аiи Bj — некоторые высказывания, к которым применены логические операции И и ИЛИ. Если высказывания в левой части правила (ее часто называют антецедент — условие, причина) истинно, истинно и высказывание в правой части (консеквент — следствие).
Полнота базы знаний (базы правил) определяет возможности системы по удовлетворению потребностей пользователей. Логический вывод в продукционных системах основан на построении прямой и обратной цепочек заключений, образуемых в результате последовательного просмотра левых и правых частей соответствующих правил, вплоть до получения окончательного заключения.
Пусть в некоторой области памяти (базе знаний) хранятся следующие правила (суждения):
· правило 1: ЕСЛИ в стране происходит падение курса национальной валюты, ТО материальное положение населения ухудшается;
· правило 2: ЕСЛИ объемы производства в стране падают, ТО курс национальной валюты снижается;
· правило 3: ЕСЛИ материальное положение населения ухудшается, ТО уровень смертности в стране возрастает.
Если на вход системы поступит новый факт (факт 1) «В стране высокий уровень падения объемов производства», то из правил можно построить цепочку рассуждений и сформулировать два заключения:
где заключение 1 (промежуточный вывод) — «Материальное положение населения ухудшается»; заключение 2 (окончательный вывод) — «В стране возрастает уровень смертности».
Отметим, что в современных ЭС в базе знаний могут храниться тысячи правил, а коммерческая стоимость одного невыводимого (нового, дополнительного) правила весьма высока.
Главными достоинствами продукционных систем являются простота пополнения и изъятия правил; простота реализации механизма логического вывода и наглядность объяснений результатов работы системы.
Основной недостаток подобных систем — трудность обеспечения непротиворечивости правил при их большом числе, что требует создания специальных правил (так называемых метаправил) разрешения возникающих в ходе логического вывода противоречий. Кроме того, время формирования итогового заключения может быть достаточно большим.
Фреймовая модель. Сравнительно новая модель представления знаний. Само понятие «фрейм» (англ. frame — рама, рамка, скелет, сгусток, сруб и т.д.) было введено в 1975 г. М.Минским (M.Minsky, США).
Фрейм — это минимальная структура информации, необходимая для представления знаний о стереотипных классах объектов, явлений, ситуаций, процессов и др. С помощью фреймов можно моделировать знания о самых разнообразных объектах интересующей исследователя предметной области — важно лишь, чтобы эти объекты составляли класс концептуальных (повторяющихся: стереотипных) объектов, процессов и т. п. Примерами стереотипных жизненных ситуаций могут служить собрание, совещание; сдача экзамена или зачета; защита курсовой работы и др. Примеры стереотипных бытовых ситуаций: отъезд в отпуск, встреча гостей, выбор телевизора, ремонт и др. Примеры стереотипных понятий: алгоритм; действие; методика и др. На рис. 13.2 представлен фрейм технологической операции «соединять» [21].
Данный фрейм описывает ситуацию «Субъект X соединяет объект Y с объектом Z способом W».
Наполняя слоты конкретным содержанием, можно получить фрейм конкретной ситуации, например: «Радиомонтажник соединяет микросхему с конденсатором способом пайки». Заполнение слотов шанциями называют активизацией фрейма.
С помощью фреймов можно моделировать как процедурные, так и декларативные знания. На рис. 13.2 представлен пример представления процедурных знаний.
На рис. 13.3 приведен пример фрейма «технологическая операция», иллюстрирующий представление декларативных знаний для решения задачи проектирования технологического процесса.
По содержательному смыслу фрейма выделяют [21]:
· фреймы-понятия;
· фреймы-меню;
· фреймы с иерархически вложенной структурой.
Фрейм-понятие — это фрейм типа И. Например, фрейм «операция» содержит объединенные связкой И имена слотов «что делать», «что это дает», «как делать», «кто делает», «где делать» и т.д., а фрейм «предмет» — слоты с именами «назначение», «форма», «вес», «цвет» и т.д.
Фрейм-меню — это фрейм типа ИЛИ. Он служит для организации процедурных знаний с помощью оператора «выбрать». Например, фрейм «что делать» может состоять из объединенных связкой ИЛИ слотов «решить уравнение», «подставить данные», «уточнить задачу» и т.д., причем каждый из этих слотов может иметь несколько значений.
Фрейм с иерархически вложенной структурой предполагает, что в нем в качестве значений слотов можно использовать имена других фреймов, слотов и т.д., т. е. использовать иерархическую структуру, в которой комбинируются другие виды фреймов (в итоге получают так называемые фреймы-сценарии).
Значения слотов могут содержать ссылки на так называемые присоединенные процедуры. Различают два вида присоединенных процедур: процедуры-демоны; процедуры-слуги.
Процедуры-демоны присоединяются к слоту и активизируются при изменении информации в этом слоте (выполняют вспомогательные операции — например, автоматически корректируют информацию во всех других структурах, где используется значение данного слота).
1. Процедура «Если — добавлено» (IF —ADDED) выполняется, когда новая информация помещается в слот.
2. Процедура «Если — удалено» (IF —REMOVED) выполняется, когда информация удаляется из слота.
3. Процедура «Если —нужно» (IF —NEEDED) выполняется, когда запрашивается информация из пустого слота.
Процедуры-слуги активизируются при выполнении некоторых условий относительно содержимого слотов (часто по запросу). Данные процедуры определяются пользователем при создании фрейма. Например, во фрейме «Учебная аудитория» можно предусмотреть слоты «Длина» и «Ширина», а по их значениям вычислять значение слота «площадь».
Фреймы позволяют использовать многие свойства знаний и достаточно широко употребляются. Их достоинства и недостатки схожи с достоинствами и недостатками семантических сетей, которые будут рассмотрены ниже.
Модель семантической сети (модель Куилиана). Семантическая сеть — это направленный граф с поименованными вершинами и дугами, причем узлы обозначают конкретные объекты, а дуги — отношения между ними [21]. Как следует из определения, данная модель представления знаний является более общей по отношению к фреймовой модели (иными словами, фреймовая модель — частный случай семантической сети). Семантическую сеть можно построить для любой предметной области и для самых разнообразных объектов и отношений.
В семантических сетях используют три типа вершин:
· вершины-понятия (обычно это существительные);
· вершины-события (обычно это глаголы);
· вершины-свойства (прилагательные, наречия, определения).
Дуги сети (семантические отношения) делят на четыре класса:
· лингвистические (падежные, глагольные, атрибутивные);
· логические (И, ИЛИ, НЕ);
· теоретико-множественные (множество — подмножество, отношения целого и части, родовидовые отношения);
· квантифицированные (определяемые кванторами общности и существования ).
(Кванторы — это логические операторы, переводящие одну высказывательную форму в другую и позволяющие указывать объем тех значений предметных переменных, для которых данная выcказывателъная форма истинна).
Приведем два примера.
На рис. 13.4 представлена семантическая сеть для предложения (ситуации) «студент Табуреткин добросовестно изучает новый план счетов на 2002 г. перед сдачей экзамена по дисциплине «Бухгалтерский учет».
Рис. 13.5 содержит фрагмент семантической сети для понятия «автомобиль».
Из приведенных примеров понятно, почему многие специалисты по ИИ считают фрейм частным случаем семантической сети со строго структурированными знаниями.
Основное достоинство методов моделирования знаний с помощью семантических сетей и фреймов — универсальность, удобство представления как декларативных, так и процедуральных знаний. Существует и два недостатка:
· громоздкость, сложность построения и изменения;
· потребность в разнообразных процедурах обработки, связанная с разнообразием типов дуг и вершин.
Модели на основе теоретического подхода.В рамках реализации теоретического подхода применяют логические модели, прежде всего использующие представления знаний в системе логики предикатов. Преимущества такого подхода очевидны: единственность теоретического обоснования и возможность реализации системы путем введения формально точных определений и правил получения выводов. Однако в полной мере претворить в жизнь данный подход даже для «простых» задач оказалось весьма сложно. Поэтому появились попытки перейти от формальной логики к так называемой человеческой логике (модальной логике, многозначной логике и др.), модели которой в большей или меньшей степени учитывают «человеческий фактор», т.е. являются в определенном смысле компромиссными в плане использования и теоретического, и эвристического подходов.
Очень коротко остановимся на ставшей классической предикатной модели представления знаний. Первые попытки использовать такую модель относятся к 50-м гг. прошлого века. Дадим несколько определений.
Пусть имеется некоторое множество объектов, называемое предметной областью. Выражение P(x1, x2, …, хn), где х1…xn — предметные переменные, а Р принимает значения 0 или 1, и называется логической функцией, или предикатом.
Предикат Р(х1, х2, …, хn) задает отношение между элементами х1 х2, …, хnи обозначает высказывание, что «х1, х2, …, хnнаходятся между собой в отношении Р». Например, если А — множество целых чисел, а Р(а) — высказывание «а — положительное число», то Р(а) = 1 при а > 0 и Р(а) = 0 при а £0.
Из подобного рода элементарных высказываний с помощью логических связок образуют более сложные высказывания, которые могут принимать те же значения — «истина» и «ложь». В качестве связок используются конъюнкция, дизъюнкция, импликация, отрицание, эквивалентность.
Предикат от п переменных называют n-местным.
Одноместные (унарные) предикаты отражают свойства определенного объекта или класса объектов. Многоместные предикаты позволяют записывать отношения, которые существуют между группой элементов.
Если а — тоже предикат, то Р(а) — предикат 2-го порядка и далее до n-го порядка.
Приведем примеры различных предикатов.
1. Унарный предикат (высказывание) «река впадает в Каспийское море» имеет значение 1, если «река» = «Волга», и значение 0, если «Река» = «Днепр».
2. Двухместный предикат «x1не меньше х2» может иметь значение 1 или 0 в зависимости от значений х1и х2. Если значение предиката тождественно равно 1 при любых значениях предметных переменных, он называется тавтологией.
В аппарат исчисления предикатов входят также символы функций (обычно обозначаемые латинскими буквами f, g, h и т.д.), задаваемых на множестве предметных переменных, и кванторы общности и существования .
3. Представление с помощью предиката знаний, заключенных в теореме Пифагора: P{g[f(x),f(y)],f(z)}, где предикат Р— «быть равным», функция g(x, у) = х + у; функция f(х) = х2.
Иногда используется такая форма записи:
РАВНЫ [СУММА (КВАДРАТ(х), КВАДРАТ(y)), КВАДРАТ (z)].
Предикат Р равен 1, если х, у, z — соответственно длины катетов и гипотенузы прямоугольного треугольника.
Как уже отмечалось, предикаты удобны для описания декларативных знаний (фактов, событий и т.п.). Их главные достоинства — возможность реализации строгого вывода знаний (исчисления предикатов) и сравнительная компактность модели. К сожалению, предикаты мало пригодны для записи процедуральных знаний. Кроме того, опыт показал, что человеческое знание по своей структуре много сложнее структуры языков предикатного типа, поэтому требуются специальные навыки «подгонки» структуры реального знания под структуру модели (как правило, значительно обедняющей исходные знания).
Для представления математического знания в математической логике пользуются логическими формализмами — исчислением высказываний и исчислением предикатов. Эти формализмы имеют ясную формальную семантику и для них разработаны механизмы вывода. Поэтому исчисление предикатов было первым логическим языком, который применяли для формального описания предметных областей, связанных с решением прикладных задач.
Логические модели представления знаний реализуются средствами логики предикатов.
Предикатом называется функция, принимающая два значения (истина или ложь) и предназначенная для выражения свойств объектов или связей между ними. Выражение, в котором утверждается или отрицается наличие каких-либо свойств у объекта, называется высказыванием. Константы служат для именования объектов предметной области. Логические предложения или высказывания образуют атомарные формулы. Интерпретация предиката — это множество всех допустимых связываний переменных с константами. Связывание представляет собой подстановку констант вместо переменных. Предикат считается общезначимым, если он истинен во всех возможных интерпретациях. Говорят, что высказывание логически следует из заданных посылок, если оно истинно всегда, когда истинны посылки.
Описания предметных областей, выполненные в логических языках, называются логическими моделями.
Пример.
ДАТЬ (МИХАИЛ, ВЛАДИМИРУ, КНИГУ);
($x) (ЭЛЕМЕНТ (x, СОБЫТИЕ-ДАТЬ) ? ИСТОЧНИК (x, МИХАИЛ) ? АДРЕСАТ ? (x, ВЛАДИМИР) ОБЪЕКТ(x, КНИГА).
Здесь описаны два способа записи одного факта: «Михаил дал книгу Владимиру».
Логический вывод осуществляется с помощью силлогизма (если из A следует B, а из B следует C, то из A следует C).
В общем случае в основе логических моделей лежит понятие формальной теории, задаваемой четверкой:
S = <B, F, A< R>,
где B — счетное множество базовых символов (алфавит) теории S;
F — подмножество выражений теории S, называемые формулами теории (под выражениями понимаются конечные последовательности базовых символов теории S);
A — выделенное множество формул, называемые аксиомами теории S, то есть множество априорных формул;
R — конечное множество отношений {r1, …, rn} между формулами, называемые правилами вывода.
Преимущество логических моделей представления знаний заключается в возможности непосредственно запрограммировать механизм вывода синтаксически правильных высказываний. Примером такого механизма служит, в частности процедура вывода, построенная на основе метода резолюций.
Покажем метод резолюций.
В методе используется несколько понятий и теорем.
Понятие тавтологии, логической формулы, значением которой будет «истина» при любых значениях входящих в них атомов. Обозначается ?, читается как «общезначимо» или «всегда истинно».
Теорема 1. А?В тогда и только тогда, когда ?А
В.
Теорема 2. А1, А2, …, Аn? В тогда и только тогда, когда ? (A1?A2?A3?…?An) В.
Символ ? читается как «верно, что» или «можно вывести».
В основе метода лежит доказательство тавтологии
? (X?A)?(Y??A)?(X?Y) .
Теоремы 1 и 2 позволяют записать это правило в следующем виде:
(X?A), (Y??A) ? (X?Y),
что дает основания утверждать: из посылок 
и 
можно вывести 
.
В процессе логического вывода с применением правила резолюции выполняются следующие шаги.
1. Устраняются операции эквивалентности и импликации:
;
.
2. Операция отрицания продвигается внутрь формул с помощью законов де Моргана:
3. Логические формулы приводятся к дизъюнктивной форме: 
.
Правило резолюции содержит в левой части конъюнкцию дизъюнктов, поэтому приведение посылок, используемых для доказательства, к виду, представляющему собой конъюнкции дизъюнктов, является необходимым этапом практически любого алгоритма, реализующего логический вывод на базе метода резолюции. Метод резолюции легко программируется, это одно из важнейших его достоинств.
Предположим, нужно доказать, что если истинны соотношения 
и 
, то можно вывести формулу 
. Для этого нужно выполнить следующие шаги.
1.Приведение посылок к дизъюнктивной форме: 
, 
, 
.
2.Построение отрицания выводимого заключения 
. Полученная конъюнкция справедлива, когда 
и 
одновременно истинны.
3.Применение правила резолюции:
;
;
;
(противоречие или «пустой дизъюнкт»).
Итак, предположив ложность выводимого заключения, получаем противоречие, следовательно, выводимое заключение является истинным, т.е. , выводимо из исходных посылок.
Именно правило резолюции послужило базой для создания языка логического программирования PROLOG. По сути дела, интерпретатор языка PROLOG самостоятельно реализует вывод, подобный вышеописанному, формируя ответ на вопрос пользователя, обращенный к базе знаний.
В логике предикатов для применения правила резолюции предстоит осуществить более сложную унификацию логических формул в целях их приведения к системе дизъюнктов. Это связано с наличием дополнительных элементов синтаксиса, в основном кванторов, переменных, предикатов и функций.
Алгоритм унификации предикатных логических формул включает следующие шаги.
- Исключение операций эквивалентности.
- Исключение операций импликации.
- Внесение операций отрицания внутрь формул.
- Исключение кванторов существования. Это может произойти на шаге 3 вследствие применения законов де Моргана, а именно; в результате отрицания
меняется на 
, но при этом может произойти и обратная замена. Тогда для исключения поступают следующим образом; все вхождения некоторой переменной, связанной квантором существования, например 
, заменяются в формуле на новую константу, например а. Эта константа представляет собой некоторое (неизвестное) значение переменной X, для которого утверждение, записанное данной формулой, истинно. При этом важно то, что на все места, где присутствует X, будет подставлено одно и то же значение а, пусть оно и является неизвестным в данный момент. Такие константы называются сколемовскими, а операция — сколемизацией (по имени известного математика Сколема). - Кванторы общности выносятся на первые места в формулах. Это также не всегда является простой операцией, иногда при этом приходится делать переименование переменных.
- Раскрытие конъюнкций, попавших внутрь дизъюнкций.
После выполнения всех шагов описанного алгоритма унификации можно применять правило резолюции, Обычно при этом осуществляется отрицание выводимого заключения, и алгоритм вывода можно кратко описать следующим образом: Если задано несколько аксиом (теория Тh) и предстоит сделать заключение о том, выводима ли некоторая формула Р из аксиом теории Тh, строится отрицание Р и добавляется к Тh, при этом получают новую теорию Тh1. После приведения 
и аксиом теории к системе дизъюнктов можно построить конъюнкцию и аксиом теории Тh. При этом существует возможность выводить из исходных дизъюнктов дизъюнкты — следствия. Если Р выводимо из аксиом теории Тh, то в процессе вывода можно получить некоторый дизъюнкт Q, состоящий из одной литеры, и противоположный ему дизъюнкт 
. Это противоречие свидетельствует о том, что Р выводимо из аксиом Тh. Вообще говоря, существует множество стратегий доказательства, нами рассмотрена лишь одна из возможных — нисходящая.
Пример: представим средствами логики предикатов следующий текст:
«Если студент умеет хорошо программировать, то он может стать специалистом в области прикладной информатики».
«Если студент хорошо сдал экзамен по информационным системам, значит, он умеет хорошо программировать».
Представим этот текст средствами логики предикатов первого порядка. Введем обозначения: X — переменная для обозначения студента; хорошо — константа, соответствующая уровню квалификации; Р(Х) — предикат, выражающий возможность субъекта X стать специалистом по прикладной информатике; Q(Х, хорошо) — предикат, обозначающий умение субъекта X программировать с оценкой хорошо; R(Х, хорошо) — предикат, задающий связь студента X с экзаменационной оценкой по информационным системам.
Теперь построим множество правильно построенных формул:
Q(Х, хорошо)
.
R(Х, хорошо)Q(Х, хорошо).
Дополним полученную теорию конкретным фактом
R(иванов, хорошо).
Выполним логический вывод с применением правила резолюции, чтобы установить, является ли формула Р(иванов) следствием вышеприведенной теории. Другими словами, можно ли вывести из этой теории факт, что студент Иванов станет специалистом в прикладной информатике, если он хорошо сдал экзамен по информационным системам.
Доказательство
1. Выполним преобразование исходных формул теории в целях приведения к дизъюнктивной форме:
(Х,хорошо)
Р(Х);
(Х,хорошо)
(Х,хорошо);
R(иванов, хорошо).
2. Добавим к имеющимся аксиомам отрицание выводимого заключения
(иванов).
3. Построим конъюнкцию дизъюнктов
(Х,хорошо)Р(Х)??P(иванов, хорошо)??Q(иванов, хорошо), заменяя переменную X на константу иванов.
Результат применения правила резолюции называют резольвентой. В данном случае резольвентой является (иванов).
4. Построим конъюнкцию дизъюнктов с использованием резольвенты, полученной на шаге 3:
(Х, хорошо)(Х, хорошо)
(иванов, хорошо) 
(иванов, хорошо).
5. Запишем конъюнкцию полученной резольвенты с последним дизъюнктом теории:
(иванов, хорошо)
(иванов, хорошо) 
(противоречие).
Следовательно, факт Р(иванов) выводим из аксиом данной теории.
Для определения порядка применения аксиом в процессе вывода существуют следующие эвристические правила:
- На первом шаге вывода используется отрицание выводимого заключения.
- В каждом последующем шаге вывода участвует резольвента, полученная на предыдущем шаге.
Однако с помощью правил, задающих синтаксис языка, нельзя установить истинность или ложность того или иного высказывания. Это распространяется на все языки. Высказывание может быть построено синтаксически правильно, но оказаться совершенно бессмысленным. Высокая степень единообразия также влечет за собой еще один недостаток логических моделей — сложность использования при доказательстве эвристик, отражающих специфику конкретной предметной проблемы. К другим недостаткам формальных систем следует отнести их монотонность, отсутствие средств для структурирования используемых элементов и недопустимость противоречий. Дальнейшее развитие баз знаний пошло пути работ в области индуктивных логик, логик «здравого смысла», логик веры и других логических схем, мало что имеющих общего с классической математической логикой.