Некорректные задачи существуют практически в любой проблемной области. Там, где есть некорректные и слабоструктурированные задачи, можно ожидать эффекта от применения интеллектуальных систем.
Смысл термина нечеткость многозначен. Трудно претендовать на исчерпывающее определение этого понятия, поэтому рассмотрим лишь основные его компоненты, к которым относятся следующие:
- недетерминированность выводов;
- многозначность;
- ненадежность;
- неполнота;
- неточность.
Недетерминированность выводов. Это характерная черта большинства систем искусственного интеллекта. Недетерминированность означает, что заранее путь решения конкретной задачи в пространстве ее состояний определить невозможно. Поэтому в большинстве случаев методом проб и ошибок выбирается некоторая цепочка логических заключений, согласующихся с имеющимися знаниями, а в случае если она не приводит к успеху, организуется перебор с возвратом для поиска другой цепочки и т.д. Такой подход предполагает определение некоторого первоначального пути. Для решения подобных задач предложено множество эвристических алгоритмов. Рассмотрим один из них — классический алгоритм А* , разработанный на этапах становления искусственного интеллекта.
Рис. 1.1. Переход из начального состояния в конечное в игре «8» |
В алгоритме А* используются оценочные функции, построенные на основе априорных оценок стоимости пути до целевого состояния.
В этой игре в качестве основного объекта удобнее рассматривать не передвигаемые шашки, а перемещение пустого квадрата. При этом можно определить четыре основных оператора, выполняемых над пустым квадратом:
- перемещение пустого квадрата влево;
- перемещение пустого квадрата вверх;
- перемещение пустого квадрата вниз
- перемещение пустого квадрата вправо.
Оценочная функциябудет формироваться как стоимость оптимального пути к цели из начального состояния через п вершин дерева поиска. Дерево поиска для данного примера показано на рис. 3.2. Значение оценочной функции в n-й вершине можно представить как сумму двух составляющих, где g(n) — стоимость оптимального пути от первой вершины до — стоимость оптимального пути от n-й вершины до цели. Для простоты будем считать, что стоимость перемещения одной шашки (или пустого квадрата) равна 1. Оптимальным будет путь, имеющий минимальную стоимость. Точное значение невозможно знать в процессе поиска, поэтому введем априорную оценку значения функции:— глубина пройденного пути на дереве поиска от 1 -й до n-й вершины;-априорное значение h(n).
Основная проблема заключается в определении второй компоненты , так как этот путь еще не пройден.
В качестве априорной оценки h(n) можно, например, взять число шашек, находящихся не на своих местах на шаге поиска. Сформировав таким образом оценочную функцию, определим стратегию выбора вершин (применения операторов), в которых значения функции минимальны. Результат поиска показан на рис. 3.2, где цифры в кружках показывают последовательность переходов из начального состояния в конечное. Проанализируем основные шаги алгоритма.
- Рассматриваем все возможные операторы над пустым квад ратом в начальном состоянии и выбираем вариант с наименьшим значением h(n).
- Применяем выбранный оператор, в результате получаем новое состояние.
- Создаем вершины следующего уровня иерархии, анализи руя применение всех возможных операторов для перехода в новое состояние.
- Выбираем состояние с наименьшим значением
- Повторяем перечисленные действия до тех пор, пока не достигнем цели.
В данном случае важно, чтотак как если априорная оценка стоимости оптимального пути не превышает истинной стоимости, то нахождение оптимального пути гарантировано. Это условие можно интерпретировать следующим образом: цель поиска не будет достигнута, пока число перемещений меньше числа шашек, находящихся не на своих местах.
Есливыбрать по-другому, напримерто будем осуществлять горизонтальный поиск на дереве состояний задачи, при котором раскрываются все вершины нижележащего уровня.
Таким образом, недетерминированность выводов — черта, органически присущая интеллектуальным системам, т.е. неустранимая компонента нечеткости знаний. Ее следует учитывать при выработке эффективных способов представления и хранения знаний, а также при построении алгоритмов поиска и обработки знаний, которые позволяют получить решение задачи за наименьшее число шагов. Для построения таких алгоритмов обычно применяются эвристические метазнания (знания о знаниях).
Многозначность. Многозначность интерпретации — обычное явление в задачах распознавания. При понимании естественного языка серьезными проблемами становятся многозначность смысла слов, их подчиненности, порядка слов в предложении и т. п. Проблемы понимания смысла возникают в любой системе, взаимодействующей с пользователем на естественном языке. Распознавание фафических образов также связано с решением проблемы многозначной интерпретации. При компьютерной обработке знаний многозначность необходимо устранять путем выбора правильной интерпретации, для чего разработаны специальные методы. Рассмотрим один из таких методов — метод релаксации, предназначенный для систематического устранения многозначности при интерпретации изображений.
Устранение многозначности достигается с помощью циклических операций фильтрации. Рассмотрим пример: Пусть имеется черно-белое изображение (рис 3.3), которое должен распознать компьютер.
Одним из этапов распознавания объекта является интерпретация смысла линий. Для идентификации фаней введем следующие метки:
(+) — выпуклая грань;
(—) — вогнутая грань;
(—>) — справа от стрелки находится видимая поверхность.
Первый цикл метода релаксации осуществляет «локальный взгляд» на каждую вершину, при этом будем иметь интерпретации вершин 1—7, показанные на рис. 3.4.
Если при интерпретации заданного контура рассматривать сразу две соседние вершины, то они должны иметь общую фань с одной и той же меткой, при этом число вариантов интерпретации уменьшается. Интерпретация вершин, для которых число вариантов изменилось, приведена на рис. 3.5.
Подобную операцию называют фильтрацией. Ее можно применять неоднократно в целях устранения многозначности. В рассматриваемом примере после однократной фильтрации число интерпретаций вершин сократилось, поэтому фильтрацию можно применить еще раз (критерием окончания итерационного цикла в данном методе является неизменность вариантов интерпретации на двух последовательных итерациях). Результат вторичного применения фильтрации показан на рис. 3.6.
Дальнейшее применение фильтрации не приводит к сокращению числа вершин—кандидатов для интерпретации. Оставшиеся кандидаты позволяют составить четыре варианта прямоугольного параллелепипеда:
• 1 — не прилегающий ни к одной из поверхностей (висячий);
• 2, 3, 4 — прилегающий к поверхности одной из трех невидимых граней.
Рис. 3.4. Локальные интерпретации вершин изображения
Ненадежность знаний и выводов. Ненадежность знаний означает, что для оценки их достоверности нельзя применить двухбалльную шкалу (1 — абсолютно достоверные; 0 — недостоверные знания). Для более тонкой оценки достоверности знаний применяется вероятностный подход, основанный на теореме Байеса, и другие методы.
118
Рис. 3.5. Локальные интерпретации вершин изображения с учетом связей между ними
Например, в экспертной системе MYSIN, предназначенной для диагностики и выбора метода лечения инфекционных заболеваний, разработан метод вывода с использованием коэффициентов уверенности. Широкое применение на практике получили нечеткие выводы, строящиеся на базе нечеткой логики, ведущей свое происхождение от теории нечетких множеств.
В системах с ненадежными знаниями на И-ИЛИ-фафе появляется еще один тип связи КОМБ — комбинированная связь. Фрагмент структуры такого фафа показан на рис. 3.7. Если ненадежные знания объединены связкой И, то степень надежности заключения традиционно выбирается как минимальное значение, при объединении связкой ИЛИ — как максимальное значение степени надежности. Связь КОМБ означает, что заключение, основанное на фактах, объединяемых этим видом связи, будет получено с оценкой достоверности, вычисляемой тем или иным способом. Одним из видов оценки достоверности знаний являются коэффициенты уверенности, используемые в экспертной системе MYSIN, которые могут принимать значения, принадлежащие отрезку [-1,1], при этом 1 соответствует истинному, а (-1) — ложному утверждению.
Рис. 3.6. Результат вторичной операции фильтрации
Цель |
Рис. 3.7. Фрагмент структуры И-ИЛИ-графа для системы с ненадежными знаниями
Коэффициент уверенности (CF), характеризующий связь КОМБ при выводе заключения А на основе посылок X и Y, вычисляется по одной из следующих формул:
120
Несмотря на отсутствие строгого теоретического обоснования, коэффициенты уверенности находят широкое применение в экспертных системах продукционного типа благодаря простоте восприятия и интерпретации получаемых результатов, которые неплохо согласуются с реальностью.
Вероятностный метод оценки надежности знаний получил в инженерии знаний широкое развитие. Рассмотрим один из таких подходов, субъективный байесовский метод. В данном подходе связи между элементами знаний не разделяются на типы; вместо этого каждому элементарному фрагменту знаний (факту, представленному парой атрибут — значение или утверждением) ставится в соответствие минимальное или максимальное значение байесовской вероятности, после чего степени надежности выводимых заключений рассчитываются как апостериорные (условные) вероятности по формулам, полученным на базе формулы Байеса.
Пусть Р{Н) — вероятность некоторой гипотезы (заключения) при отсутствии каких-либо свидетельств (т.е. априорная вероятность, назначаемая экспертом) и пусть Р(Н: Е) — апостериорная вероятность гипотезы Н при наличии свидетельства (факта) Е, вычисляемая по формуле
где Р(Е) — вероятность свидетельства Е, которая вычисляется по формуле
— вероятность наличия свидетельства Е при условии истинности гипотезы Н (например, вероятность наличия высокой температуры при заболевании гриппом);— вероятность свидетельства Е при условии ложности заключения Н (вероятность высокой температуры у пациента, не болеющего гриппом).
Значения этих вероятностей, как правило, определяются экспертами и хранятся в базе знаний.
Субъективный байесовский подход получил широкое распространение благодаря своей простоте. К тому же он достаточно обоснован теоретически. Однако этот подход, как и предыдущий, имеет нерешенные проблемы: например, сумма вероятностей опровергающих друг друга событий может оказаться больше 1. Сложной задачей для экспертов является назначение априорных вероятностей условных событий. Теоретические исследования в данном направлении активно продолжаются, и в распоряжении проектировщиков экспертных систем уже имеются такие мощные средства, как вероятностная логика, нечеткая логика, теория Демпстера-Шафера и т.п.
Неполнота знаний и немонотонная логика. Абсолютно полных знаний не бывает, поскольку процесс познания бесконечен. В связи с этим состояние базы знаний должно изменяться с течением времени. В отличие от простого добавления информации, как в базах данных, при добавлении новых знаний возникает опасность получения противоречивых выводов, т.е. выводы, полученные с использованием новых знаний, могут опровергать те, что были получены ранее. Еще хуже, если новые знания будут находиться в противоречии со «старыми», тогда механизм вывода может стать неработоспособным. Многие экспертные системы первого поколения были основаны на модели закрытого мира, обусловленной применением аппарата формальной логики для обработки знаний. Модель закрытого мира предполагает жесткий отбор знаний, включаемых в базу, а именно: БЗ заполняется исключительно верными понятиями, а все, что ненадежно или неопределенно, заведомо считается ложным. Другими словами, все, что известно базе знаний, является истиной, а остальное — ложью. Такая модель имеет офаниченные возможности представления знаний и таит в себе опасность получения противоречий при добавлении новой информации. Тем не менее эта модель достаточно распространена; например, на ней базируется язык PROLOG. Недостатки модели закрытого мира связаны с тем, что формальная логика исходит из предпосылки, согласно которой набор определенных в системе аксиом (знаний) является полным (теория является полной, если каждый ее факт можно доказать, исходя из аксиом этой теории). Для полного набора знаний справедливость ранее полученных выводов не нарушается с добавлением новых фактов. Это свойство логических выводов называется монотонностью. К сожалению, реальные знания, закладываемые в экспертные системы, крайне редко бывают полными.
Рассмотрим простой пример. Допустим, в БЗ содержатся следующие утверждения:
«Птицы летают». «Пингвин не летает». «Лоло — птица».
На основе этих знаний можно получить заключение «Лоло летает» и сделать вывод о том, что «Пингвин не является птицей».
Если в БЗ добавить факт «Лоло — пингвин», то получим противоречащие предыдущим заключения: «Лоло не летает» и «Лоло не является птицей».
В качестве средств формальной обработки неполных знаний, для которых необходимы немонотонные выводы, разрабатываются методы немонотонной логики: немонотонная логика Макдер-мотта и Доула, в которой вводятся условные логические операции, логика умолчания Рейтера, немонотонная логика Маккарти и т.п. Многие из этих теорий еще не полностью отработаны, но предложенные в них элементы уже нашли применение в практических разработках (проверка и учет непротиворечивости элементов знаний, установление значений по умолчанию во фреймовых системах и т.п.). Так, пример с пингвином не вызывает противоречий при использовании фреймового представления знаний (рис. 3.8).
Рис. 3.8. Установка значений по умолчанию в системах фреймов
Для организации логических выводов в интеллектуальных системах с неполными знаниями вместо традиционной дедукции применяется абдукция. Абдукцией называется процесс формирования объясняющей гипотезы на основе заданной теории и имеющихся наблюдений (фактов). Рассмотрим простейший пример абдуктивного вывода. Предположим, теория содержит правило: «ЕСЛИ студент отлично знает математику, ТО он может стать хорошим инженером» и факт: «Студент Иванов отлично знает математику». Кроме того, имеется наблюдение: «Студент Иванов стал хорошим экономистом», которое не выводится из заданной теории. Для того чтобы его вывести, необходимо сформировать абдуктивную (объясняющую) гипотезу, которая не будет противоречить вышеприведенной теории. Такой гипотезой может быть, например, следующая: «Хороший математик может стать хорошим экономистом».
Целью абдуктивного вывода является формирование одного (или более) объяснения Д наблюдаемого факта G на основе информации, хранящейся в БЗ интеллектуальной системы (теория Т). Объяснение А должно быть таким, чтобыи чтобыбыло непротиворечиво. Другими словами, наблюдение G можно вывести из теориилишь при ее расширении некоторым множеством гипотез. В большинстве случаев абдуктивные гипотезы выбираются из заранее определенного множества предложений, отражающих определенный аспект знаний конкретной предметной области. Теорию T можно рассматривать как основу всех возможных расширенийдля каждой абдуктивной гипотезы А.
Абдуктивные выводы используются в задачах диагностики для обнаружения причин наблюдаемого неправильного поведения систем, в задачах, связанных с пониманием естественного языка, для решения проблем накопления и усвоения знаний и т.д.
Для работы с неполными знаниями предназначена также система поддержания значений истинности, в которой все знания делятся на достоверные и недостоверные, при этом предусматривается систематическое упорядочение БЗ в целях устранения недостоверных знаний. Достоверные на данный момент знания относят к классу IN, а сомнительные и недостоверные — к классу OUT. Если при добавлении новых знаний возникает противоречие, то выполняется проверка классов знаний, при этом возможны мифации из класса в класс.
Исследования в области немонотонных выводов — это попытки расширить границы формальной логики, в которые не вписываются реальные знания, необходимые интеллектуальным системам.
Неточность знаний. Известно, что количественные данные (знания) могут быть неточными, при этом существуют количественные оценки такой неточности (доверительный интервал, уровень значимости, степень адекватности и т.д.). Лингвистические знания также могут быть неточными. Для учета неточности лингвистических знаний используется теория нечетких множеств, предложенная Л. Заде в 1965 г. Этому ученому принадлежат слова: «Фактически нечеткость может быть ключом к пониманию способности человека справляться с задачами, которые слишком сложны для решения на ЭВМ». Развитие исследований в области нечеткой математики привело к появлению нечеткой логики и нечетких выводов, которые выполняются с использованием знаний, представленных нечеткими множествами, нечеткими отношениями, нечеткими соответствиями и т. д.