Формирование рассуждений в условиях неопределенности

Размещено на http://www.allbest.ru/

Введение

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

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

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

Неопределенность становится проблемой, поскольку может помешать выработке наилучшего решения и даже стать причиной того, что будет принято низкокачественное решение. Поэтому, решение проблем в реальной жизни, требует учёта неопределённости.

Разработан целый ряд теорий, позволяющих успешно действовать в условиях неопределенности. Это теории основанные на:

- классическом определении вероятностей (теория Шеннона)

- байесовской вероятности

- классическом определении множеств (теория Хартли)

- теории Демпстера-Шефера

- марковские моделях

- теории нечетких множеств Заде.

Некоторые из них мы рассмотрим.

Основой некоторых теорий неопределенности является теория вероятностей, ниже мы приведём элементарные сведения о теории вероятностей, которые касаются применения вероятностной неопределенности и нечеткой логики в экспертных системах.

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

К сожалению, задача определения "наилучшего" способа решения может оказаться непростой. Предложен целый ряд различных способов организации действий в условиях неопределенности и средств, способствующих выбору наилучшего способа решения. Но если речь идет о том, как действовать в условиях неопределенности, то может потребоваться, чтобы мы довольствовались просто достаточно качественным решением, а не стремились к наилучшему решению. С другой стороны, качественное решение, достижимое на 99% в реальном времени, может оказаться более приемлемым, чем оптимальное решение, для вычисления которого потребуется миллион лет. Именно проектировщик экспертной системы отвечает за выбор метода, наиболее подходящего для данного конкретного приложения. Безусловно, есть такие инструментальные средства экспертных систем, в которых предусмотрены механизмы формирования рассуждений в условиях неопределенности, но, как правило, они не обладают достаточной гибкостью, чтобы дать возможность использовать другие методы.

Глава 1.

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

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

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

Фундаментальная формула классической вероятности определена как следующая вероятность:

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

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

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

В качестве примера можно указать такую ситуацию, когда у человека появляется головная боль. Чтобы попытаться вылечить головную боль, можно воспользоваться многими способами, а выбор конкретного способа зависит от состояния человека или от того, какие средства находятся в его распоряжении. В инструментальных средствах экспертных систем некоторых типов, таких как CLIPS, недетерминированность применяется для предотвращения преимущественного запуска одних и тех же правил. Если выполняются шаблоны многочисленных правил и отсутствуют явные предпочтения в отношении того, какое правило должно быть выполнено, то машина логического вывода осуществляет произвольный выбор правила, подлежащего запуску. Благодаря этому исключается тенденциозность, из-за которой всегда происходил бы запуск одного и того же правила, скажем, первого. Такая ситуация могла бы возникнуть, если бы все знания были представлены на обычном языке программирования в виде правил “IF-THEN ”, а программа просто выбирала бы эти правила в том порядке, в каком они были введены в исходном коде. В действительности в этом состоит одна из причин, по которым экспертные системы не разрабатываются на обычном языке программирования, -- в таких языках слишком трудно преодолеть детерминированность. Машина логического вывода экспертной системы в своей работе действует подобно человеку и не всегда принимает одно и то же решение при наличии нескольких правил с равным приоритетом.

Глава 2. Законы теории вероятностей

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

Эксперимент может быть связан также с непрерывным пространством событий.

Если в эксперименте, состоящем из n опытов, событие Е имело место m раз, то вероятность P{E} появления события Е математически определяется соотношением

Приведенное определение означает, что если эксперимент повторяется бесконечное число раз, то, искомая вероятность представляется граничным значение дроби m/n.

По определению , где вероятность P{E} равна 0, если событие E невозможно, и 1, если оно достоверно.

Законы сложения вероятностей

Для двух событий E и F запись E+F означает их объединение, а EF - пересечение. События E и F называются несовместными (взаимно исключающими), если они не пересекаются, т.е. наступление одного события исключает возможность реализации другого. При принятых определениях закон сложения вероятностей определяется соотношением

Первая строка системы в случае несовместности E и F, вторая - иначе.

Вероятность того, что события E и F произойдут одновременно, обозначается как P{EF}. Если эти события независимы, тогда

Условные вероятности

Для двух события E и F условная вероятность события E при условии, что наступило событие F, обозначается как P{E|F} и определяется по формуле

Если событие E содержится в событии F (т.е. множество исходов E является подмножеством исходов F), тогда

Два события E и F являются независимыми тогда и только тогда, когда выполняется равенство P{E|F}=P{E}. В этом случае формула условной вероятности сводится к следующему

Теорема умножения, если соответствующие условные вероятности определены

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

Формула полной вероятности для группы несовместных событий Bi

Глава 3. Формула Байеса

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

Доказательство следует из теоремы умножения и формулы полной вероятности.

Байесовские сети доверия

Байесовские сети доверия - Bayesian Belief Network - используются в тех областях, которые характеризуются наследованной неопределённостью. Эта неопределённость может возникать вследствие:

1. неполного понимания предметной области;

2. неполных знаний;

3. когда задача характеризуется случайностью.

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

Соединения методом причин и следствий позволяют более просто оценивать вероятности событий. В реальном мире оценивание наиболее часто делается в направлении от “наблюдателя” к “наблюдению”, или от “эффекта” к “следствию”, которое в общем случае более сложно оценить, чем направление “следствие -> эффект”, то есть в направлении от следствии.

Рис.1. Пример простейшей байесовской сети доверия.

Рассмотрим пример сети (рис.1), в которой вероятность пребывания вершины «e» в различных состояниях (ek) зависит от состояний (ci , dj) вершин «c» и «d» и определяется выражением:

где p(ek|ci, dj) - вероятность пребывания в состоянии ek в зависимости от состояний ci, dj. Так как события, представленные вершинами «c» и «d» независимы, то

экспертный неопределенность вероятность доверие

p(ek |ci , dj) = p(ci) *p(dj).

Рис.2. Двухуровневая БСД.

Рассмотрим пример более сложной сети (рис.2). Данный рисунок иллюстрирует условную независимость событий. Для оценки вершин «c» и «d» используются те же выражения, что и для вычисления p(e_k), тогда:

,

.

Из этих выражений видно, что вершина «e» условно не зависит от вершин A1, A2, B1, B2, так как нет стрелок непосредственно соединяющих эти вершины.

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

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

2. все вершины, связанные с “родительскими” определяются таблицей условных вероятностей (ТУВ) или функцией условных вероятностей (ФУВ);

3. для вершин без “родителей” вероятности её состояний являются безусловными ( маргинальными).

Другими словами, в байесовских сетях доверия вершины представляют собой случайные переменные, а дуги - вероятностные зависимости, которые определяются через таблицы условных вероятностей. Таблица условных вероятностей каждой вершины содержит вероятности состояний этой вершины при условии состояний её “родителей”.

Пример построения простейшей байесовской сети доверия

Рассматриваем небольшую яблочную плантацию «яблочного Джека». Однажды Джек обнаружил, что его яблочное дерево лишилось листвы. Теперь он хочет выяснить, почему это случилось. Он знает, что листва часто опадает, если:

дерево засыхает в результате недостатка влаги; или дерево болеет.

Данная ситуация может быть смоделирована байесовской сетью доверия, содержащей 3 вершины: «Болеет», «Засохло» и «Облетело».

Рис.1. Пример байесовской сети доверия с тремя событиями.

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

Вершина “Болеет” говорит о том, что дерево заболело, будучи в состоянии «болеет», в противном случае она находится в состоянии «нет». Аналогично для других двух вершин. Рассматриваемая байесовская сеть доверия, моделирует тот факт, что имеется причинно-следственная зависимость от события “Болеет” к событию “Облетело” и от события “Засохло” к событию “Облетело”. Это отображено стрелками на байесовской сети доверия.

Когда есть причинно-следственная зависимость от вершины А к другой вершине B, то мы ожидаем, что когда A находится в некотором определённом состоянии, это оказывает влияние на состояние B. Следует быть внимательным, когда моделируется зависимость в байесовских сетях доверия. Иногда совсем не очевидно, какое направление должна иметь стрелка.

Например, в рассматриваемом примере, мы говорим, что имеется зависимость от “Болеет” к “Облетело”, так как когда дерево болеет, это может вызывать опадание его листвы. Опадание листвы является следствием болезни, а не болезнь - следствием опадания листвы.

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

Таблица условных вероятностей p(“Облетело”)

Приведенные таблицы иллюстрируют ТУВ для трёх вершин байесовской сети доверия. Заметим, что все три таблицы показывают вероятность пребывания некоторой вершины в определённом состоянии, обусловленным состоянием её родительских вершин. Но так как вершины Болеет и Засохло не имеют родительских вершин, то их вероятности являются маргинальными, т.е. не зависят (не обусловлены) ни от чего.

На данном примере мы рассмотрели, что и как описывается очень простой байесовской сетью доверия. Современные программные средства (такие как MSBN, Hugin и др.) обеспечивают инструментарий для построения таких сетей, а также возможность использования байесовских сетей доверия для введения новых свидетельств и получения решения (вывода) за счёт пересчёта новых вероятностей во всех вершинах, соответствующих вновь введенным свидетельствам.

В нашем примере пусть известно, что дерево сбросило листву. Это свидетельство вводится выбором состояния «да» в вершине “Облетело”. После этого можно узнать вероятности того, что дерево засохло. Для приведенных выше исходных данных, результаты вывода путем распространения вероятностей по БСД будут:

p( “Болеет” = «болеет» | “Облетело” = «да») = 0,47; p( “Засохло” = «засохло» | “Облетело” = «да») = 0,49.

Глава 4.

Нечёткая логика (“Логика возможностей ”- автор Лотфи Заде ) распространяет булеву логику на действительные числа, а именно используются: “1”, ”0”, все дроби между ними- указывающие частичную истину. Так запись: р(высокий(Х))=0,75, в некотором говорит о том, что предположение "X -- высокий", в некотором смысле на три четверти истинно. Точно так же оно на одну четверть ложно. Для комбинирования нецелочисленных значений истинности в нечеткой логике определяются эквиваленты операций И, ИЛИ и НЕ:

pi И р2 = min(pl, р2) (т.е. меньшее),

pi ИЛИ р2 = max(pl, р2) (т. е. большее),

НЕ pi = 1 -- pi (т. е. "обратное значение").

Таким образом, обрывочные сведения можно комбинировать на основе

строгих и согласованных методов.

Слабым моментом в применениях нечеткой логики является

отображение или функция принадлежности. Предположим, что мне 35, насколько истинно предложение, что я старый? Равна ли эта величина 0,5, поскольку я прожил примерно полжизни? Или что-то вроде 0,4 или 0,6 будет более реалистичным? Или например: проблема взвешивания отдельных

сведений. Предположим, например, что мы располагаем некоторой совокупностью противоречивых значений истинности: 0,8 и 0,25, полученным для одного и того же предложения? Следует брать минимальное или максимальное или среднее из них или взять какую-то иную функцию от двух чисел?

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

Частично решает проблему разработанная Шортлифом схема основанная на так называемых “коэффициентах уверенности”, которые он ввел для измерения степени доверия к любому данному заключению, являющемуся результатом полученных к этому моменту свидетельств. Коэффициент уверенности -- это разность между двумя мерами:

КУ[h : е] =МД[h : е] -МНД[h : е].

В этом выражении КУ [h : е] -- уверенность в гипотезе h с учетом свидетельств е ; МД [h : е] - мера доверия h при заданном е, тогда как МНД [h : е] - мера недоверия гипотезе h при свидетельствах е.

КУ может изменяться от --1 (абсолютная ложь) до +1 (абсолютная истина) , принимая также все промежуточные значения, причем 0 означает полное незнание. Значения же МД и МНД, с другой стороны, могут изменяться лишь от 0 до 1. Таким образом, КУ -- это простой способ взвешивания свидетельств "за"и "против". Заметим, что эта формула не позволяет отличить случай противоречащих свидетельств (и МД, и МНД обе велики) от случая недостаточной информации (и МД, и МНД обе малы), что иногда было бы полезно.

Заметим также, что ни КУ, ни МД, ни МНД не являются вероятностными мерами. МД и МНД подчиняются некоторым аксиомам теории вероятности, но не являются выборками из какой-нибудь популяции, и, следовательно, им нельзя дать статистическую интерпретацию. Они просто позволяют упорядочить гипотезы в соответствии с той степенью обоснованности, которая у них есть. То, что было добавлено Шортлиффом, -- это формула уточнения, по которой новую информацию можно было непосредственно сочетать со старыми результатами. Она применяется к мерам доверия и недоверия, связанным с каждым предположением. Формула для МД выглядит следующим образом:

МД[h : е1,е2] = МД[h : е1] + МД[h : е2] (1 - МД[h : е1]),

где запятая между e1 и е2 означает, что е2 следует за e1. Аналогичным образом уточняются значения МНД.

Смысл формулы состоит в том, что эффект второго свидетельства (е2) на гипотезу h при заданном свидетельстве e1 сказьшается в смещении МД в сторону полной определенности на расстояние, зависящее от второго свидетельства. Эта формула имеет два важных свойства:

1.0на симметрична в том смысле, что порядок el и е2 не существен.

2. По мере накопления подкрепляющих свидетельств МД (или МНД) движется к определенности.

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

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

Каждое правило снабжено "коэффициентом ослабления", числом от 0 до 1, показывающим надежность этого правила.

Заключение

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

Но у них есть свои критики. Некоторые возражают против изъятия из теории нечетких множеств "закона исключения третьего" на том основании, что этот закон является основным законом формальной логики. Или факторы уверенности Шортлиффа: в его подходе вносятся ничем не обоснованные корректировки, не вдаваясь в суть возникающих при этом проблем. И теорема Байеса является уже в течение 200 лет центром разногласий между статистиками. Быть точным в отношении неопределенности может оказаться задачей, у которой никогда не будет окончательного решения. Но несмотря на все трудности, мы не можем тем не менее, уклониться от того, чтобы как-то работать с неопределенностью. Эвристические знания никогда нельзя считать выделенными и фиксированными. Если мы будем настаивать на использовании лишь бесспорных "фактов", мы выбросим все интересные задачи. Грамотный специалист по использованию знаний обязательно столкнется с необходимостью встраивания в экспертную систему какой-то взвешивающей процедуры, возможно, основанной на одной из схем, рассмотренных нами. Он должен также себе представлять, что любая процедура связана с некоторыми ограничениями. Это соображение говорит в пользу внесения в программу каких-то проверок на согласованность и других мер предосторожности.

Список литературы

1) Д. Джарратано, Г. Райли ,Экспертные системы, М., СПб., К., 2007.

2) Терехов С.А., Лекции по нейроинформатике, МИФИ, М., 2003.

3) Р. Форсайт , Экспертные системы, принципы работы и примеры, М., 1987.

4) Бобков А. И.,Макаренко В. Н.,Экспертные системы: Учеб, пособие, ЛИАП СПб., 1992.

Размещено на Allbest.ru