Сб. Фев 24th, 2024

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

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

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

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

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

Рис. 1.1. Переход из начального состояния в конечное в игре «8»

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

Такие оценки, по сути дела, тоже представляют собой эвристические знания. Для поиска в пространстве состояний ис­пользуются дерево поиска и методы горизонтального (в ширину) и вертикального (в глубину) поиска на этом дереве. Основные шаги и понятия алгоритма рассмотрим на примере игры в «8», яв­ляющейся усеченной версией ифы в «15». Целью игры является переход из некоторого начального состояния в конечное, как по­казано на рис. 1.1.

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

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

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

Ads Blocker Image Powered by Code Help Pro

Обнаружен блокировщик рекламы! Пожалуйста, обратите внимание на эту информацию.

We\'ve detected that you are using AdBlock or some other adblocking software which is preventing the page from fully loading.

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

Пожалуйста, добавьте tehnar.info к вашему белому списку блокирования объявлений или отключите программное обеспечение, блокирующее рекламу.

Powered By
Best Wordpress Adblock Detecting Plugin | CHP Adblock