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

Смысл термина нечеткость многозначен. Трудно претендо­вать на исчерпывающее определение этого понятия, поэтому рассмотрим лишь основные его компоненты, к которым относят­ся следующие:

• недетерминированность выводов;
• многозначность;
• ненадежность;
• неполнота;
• неточность.

Недетерминированность выводов. Это характерная черта боль­шинства систем искусственного интеллекта. Недетерминирован­ность означает, что заранее путь решения конкретной задачи в пространстве ее состояний определить невозможно. Поэтому в большинстве случаев методом проб и ошибок выбирается неко­торая цепочка логических заключений, согласующихся с имею­щимися знаниями, а в случае если она не приводит к успеху, ор­ганизуется перебор с возвратом для поиска другой цепочки и т.д. Такой подход предполагает определение некоторого первона­чального пути. Для решения подобных задач предложено множе­ство эвристических алгоритмов. Рассмотрим один из них — классический алгоритм А* , разработанный на этапах становления искусственного интеллекта.

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

В этой игре в качестве основного объекта удобнее рассматри­вать не передвигаемые шашки, а перемещение пустого квадрата. При этом можно определить четыре основных оператора, выпол­няемых над пустым квадратом:

• перемещение пустого квадрата влево;
• перемещение пустого квадрата вверх;
• перемещение пустого квадрата вниз
• перемещение пустого квадрата вправо.

Оценочная функциябудет формироваться как стоимость оптимального пути к цели из начального состояния через п вер­шин дерева поиска. Дерево поиска для данного примера показа­но на рис. 3.2. Значение оценочной функции в n-й вершине мож­но представить как сумму двух составляющих, где g(n) — стоимость оптимального пути от первой вершины до  — стоимость оптимального пути от n-й вершины до це­ли. Для простоты будем считать, что стоимость перемещения од­ной шашки (или пустого квадрата) равна 1. Оптимальным будет путь, имеющий минимальную стоимость. Точное значение невозможно знать в процессе поиска, поэтому введем априорную оценку значения функции:— глубина пройденного пути на дереве поиска от 1 -й до n-й вершины;-априорное значение h(n).

Основная проблема заключается в определении второй ком­поненты , так как этот путь еще не пройден.

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

1. Рассматриваем все возможные операторы над пустым квад­ ратом в начальном состоянии и выбираем вариант с наименьшим значением h(n).
2. Применяем выбранный оператор, в результате получаем новое состояние.
3. Создаем вершины следующего уровня иерархии, анализи­ руя применение всех возможных операторов для перехода в новое состояние.
4. Выбираем состояние с наименьшим значением
5. Повторяем перечисленные действия до тех пор, пока не до­стигнем цели.

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

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

Таким образом, недетерминированность выводов — черта, орга­нически присущая интеллектуальным системам, т.е. неустрани­мая компонента нечеткости знаний. Ее следует учитывать при выработке эффективных способов представления и хранения знаний, а также при построении алгоритмов поиска и обработки знаний, которые позволяют получить решение задачи за наи­меньшее число шагов. Для построения таких алгоритмов обычно применяются эвристические метазнания (знания о знаниях).

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

Устранение многозначности достигается с помощью цикли­ческих операций фильтрации. Рассмотрим пример: Пусть имеет­ся черно-белое изображение (рис 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 г. Этому ученому принадлежат сло­ва: «Фактически нечеткость может быть ключом к пониманию способности человека справляться с задачами, которые слишком сложны для решения на ЭВМ». Развитие исследований в области нечеткой математики привело к появлению нечеткой логики и нечетких выводов, которые выполняются с использованием зна­ний, представленных нечеткими множествами, нечеткими отно­шениями, нечеткими соответствиями и т. д.