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

РОССИЙСКАЯ АКАДЕМИЯ НАУК САНКТ-ПЕТЕРБУРГСКИЙ ИНСТИТУТ ИНФОРМАТИКИ И АВТОМАТИЗАЦИИ

РГ8 ОД На правах рукописи

и »• - ,3

ТУЛУПЬЕВ Александр Львович

УДК 681.3

АЛГЕБРАИЧЕСКИЕ БАЙЕСОВСКИЕ СЕТИ ДЛЯ ПРЕДСТАВЛЕНИЯ И ОБРАБОТКИ ЗНАНИЙ С НЕОПРЕДЕЛЕННОСТЬЮ

Специальность 05.13.16 — Применение вычислительной техники,

математического моделирования и математических методов в научных исследованиях

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург — 1996

Работа выполнена в Санкт-Петербургском институте

информатики и автоматизации РАН

Научный руководитель: доктор технических наук,

профессор Городецкий В.И.

Официальные оппоненты:

— доктор физико-математических наук, профессор Хованов Н.В.

— кандидат технических наук Котенко И.В.

Ведущая организация: С.-Петербургский государственный

технический университет

(MsÜlbA- iqofi г « ■И

Защита состоится " илл. 199б Г- в ' ( ча_

сов на заседании диссертационного совета Д.003.62.01 при Санкт-Петербургском институте информатики и автоматизации РАН по адресу: 199178. Санкт-Петербург, 14-я линия В.О., д. 39.

С диссертацией можно ознакомиться в библиотеке диссертационного совета.

Автореферат разослан " U-LÜIaX. ig96 г_

Ученый секретарь диссертационного совета 'у

кандидат технических наук J \с~К-> — Копыльцов A.B.

Общая характеристика работы

Актуальность темы. Одной из самых важных проблем искусственного интеллекта является поиск адекватной модели представления данных и знаний человека о предметной области в системах, базирующихся ва электронных вычислительных машинах. Известно, что данные и знания о предметной области редко бывают вполне достоверными и точными. Неопределенность, присущая им, является следствием ряда причин: свойств объектов оредметвой области, яедостагочяой ее изученности, иевербализуемости, неточности методов исследования и проч. Лля описания различных видов неопределенности применяется широкий спектр формализмов, связи которых с традиционными математическим теориями не всегда установлены и зачастую носят интуитивный характер. Это затрудняет исследование свойств Саз знаний (БЗ) и методов манипулирования со знаниями (непротиворечивости ВЗ, обоснование корректности и сопоставление различных алгоритмов, соответствующих разным стратегиям вывода на знаниях), создает трудности при оценке качества функционирования систем, основанных на званиях.

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

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

Цель работы состоит в развитии модели неопределенности знаний ва основе теории алгебраических байесовских сетей (АБС) для создания теоретической базы построения систем, основанных на знаниях с неопределенностью, в частности, для представления знаний с неопределенностью, поддержания непротиворечивости БЗ и вывода заключений (рассуждений) на основе свидетельств.

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

Научная новизна. В работе получены следующие новы« научные результаты:

• дано формальное описание алгебраических байесовских сетей (АБС) как структуры для представления знавий с вероятностной моделью веопре-

делеивости и определено ее место в контексте существующих моделей неопределенности на освове вероятностных структур;

• разработаны теоретические основы и схемы алгоритмов оцевивавия я поддержания непротиворечивости баз знаний с неопределенностью, представленных структурой АБС;

• предложены стратегии и схемы алгоритмов априорного вывода в БЗ (вывода знаний, не содержащихся квво в БЗ);

• разработаны схемы алгоритмов апостериорного вывода ва освове детерминированных и недетерминированных свидетельств;

• показано, что выразительные возможности АБС как структуры представления знаний шире, чем выразительные возможности байесовских сетей доверия.

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

Практическая ценность. Разработанные в диссертации методы и алгоритмы могут быть использованы для:

• построения инструментария разработки баз знаний с неопределенностью и их верификации;

• формализации рассуждений, использующих качественные оценки ва освове линейно упорядоченных шкал и интервальные оценки неопределенности;

• строгой формализации, в рамках вероятностной модели, рассуждений на освове аргументации.

Реализация результатов работы. Разработано несколько программ в среде МаИхстаИса для анализа свойств алгоритмов априорного вывода и поддержания непротиворечивости АБС и апостериорного вывода на освове свидетельств.

Апробация работы. Главные результаты работы были представлены ва конференциях:

• Четвертая международная конференция "Региональная ивфорыатика-95", г. Санкт-Петербург,

• Международная конференция "КВ5-95", г. Ялта, Украина,

• Всероссийская конференция "Эливф-95", г. Москва,

• Международная конференция "Эволюция инфосферы-95", г. Москва,

а также на расширенном семинаре лаборатории прикладной информатики СПИИРАН в ноябре 1995 г.

Публикации. Освовяое содержание диссертации изложено в 15 публикациях.

Объем и структура диссертации. Диссертация состоит из Введении, четырех глав, Заключения-, списка литературы, списка принятых сокращений и обозначений и грех приложений. Общий объем работы — 260 страниц (рисунки, список литературы, список принятых сокращений и обозначений и три приложения занимают IIS страниц.)

Список сокращений; АБС— алгебраическая байесовская сеть, БЗ— база знаний, БСД— байесовская сеть доверия, ЗЛП— задача лияейвого программирования, СБЛ — случайная бинарная последовательность, СДНФ — совершенная нормальная дизъюнктивная форма, ФЗ — фрагмент званий, ЭВМ — электронная вычислительная машина.

Содержание работы

Нумерация теорем совпадает с таковой в диссертации.

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

В первой главе рассмотрены вопросы, характеризующие контекст исследований данной работы, и произведено обоснование ее цели.

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

Произведен анализ существующих систем и подходов к представлению и обработке знаний с неопределенностью: MYCIN, PROSPECTOR, INFERNO, теория Лэмпстера-Шеффера, подходы на основе теории возможностей, теории нечеткости, теории вероятностей, концепция байесовских сетей доверия (БСД). Анализ упомянутых подходов позволил сформировать список недостатков и ограничений, которыми не должна обладать новая модель представления и обработки знаний с неопределенностью. В качестве подхода, опирающегося на классическую теорию вероятностей, была выбрана модель АБС.

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

Аргументное м( сто — это церемонная, которая может принимать значение из фиксированного двухэлементного множества литер: »лементярной пропозиции (атома) и ее отрицания. Предполагается, что отрицание логической формулы обозначается чертой ' сверху. Логические формулы, содержащие аргументные места, трактуются как "сложные" переменные фиксированной структуры. Предполагается, что если аргументвое место встречается в разных частях формулы (ие обязательно логической), то вместо него во псех частях формулы одновременно может бить подставлено только одно и то же возможное значение, которое мы называем логическим означиванием аргументного места (или формулы).

Формулы типа Д ¿Е; — это цепочки кон«юнк%ий. Формулы типа г,,

х¡Хь, /\х, — это поиоэтппельио логически означенные цепочки коимонкций (по-

ложитемно означенные цепочки кониюнкций, положительно означенные кони-хткции). Цепочки конъюнкций аргументных мест обозначаются большими латинскими буквами конца латинского алфавита со знаком тильда, например Л', подразумевая, что Л' = Д т, = Т)... тпх. Соответствующее по-

■ =1(1)">х

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

Предполагается, что задано универсальное множество (конечное) элементарных пропозиций — «томов, оно обозначено символом Т ~ {*],...,<„}. Предполагается, что с помощью пропозициональных формул над Т можно представить все утверждения экспертов, касающиеся исследуемой предметной области. Т может быть разбито различными способами на подмножества Т — \JTit где I — множество индексов. Подмножества Т обозначаются также с помощью символов 5 или или подобным образом. На элементы из множества Т будем ссылаться, используя строчные буквы конца латинского алфавита. Множество ,Р(7) — это множество всех возможных пропозициональных формул над Т. Множество Р(Т) или просто Т — это множество классов эквивалентных формул, образованных над Т. Множество 0(Т) или (2 — это множество пропозиций (цепочек конъюнкций максмальной длины над данным Т), называемых квантами: С(7~) = {(й .../„),: V = 1(1)2"}.

Рассмотрены четыре известных подхода к введению вероятностей на пропозициональных формулах: подход, опирающийся на изоморфизм булевых алгебр, подход, опирающийся на введение нормы на булевой алгебре, подход, предложенный Хальперном, Фэджияом и Млджидо, и подход, выдвинутый Н. Нильссоном. Отмечается, что понятия точечной вероятности, предлагаемые этими четырмя подходами, совпадают. Понятие "интервальная вероятность" «е имеет однозначной трактовки, поэтому вместо пего в диссертации используется понятие "интервальной опенки точечной вероятности" |7. 12]. За основу изложения вцОрап подход Н. Ннльсоона. По теореме о СДНФ построим отображение ). ставящее в соответствие каждой пропозициональной формуле множество конъюнктивных членов ее СЛНФ (т.е. подмно-

жество множества квантов). Пусть задана функция р на множестве квантов Q, удовлетворяющая* условиям, которые позволяют ее распространить как вероятностную меру на 2°. Множество квантов интерпретируется в втом подходе как множество элементарных событий. Тогда вероятность произвольной пропозициональной формулы задаются так: p{j) = р(Яг(/]) [7].

Вводятся определения вероятностной независимости и вероятностной ус-лонной независимости СБП, сходные с соответствующими определениями для случайны* величин. Формулируются теоремы о необходимых и достаточных условиях вероятностной независимости и вероятностной условной независимости СВП.

Пусть цепочки X, Y и Z не имеют общих элементов, имеется три набора бинарных последовательностей V = А'У", W = YZ и U = XYZ, на которых заданы распределения вероятностей p\(V), Pj(IV), U, причем

= MZ),

Wp(V) = p,(K),

vfVp(lV) = pa(l V).

Тогда распределение вероятностей p{U) будем называть композицией распределений вероятностей Pi{V) и pj(IV).

Теорема 3 Пусть 0 — XZY, V = XZ, IV = ZY, даны распределения вероятностей Pi(V) над {Г} и P2(1V) над {IV}, причел выполнены, следующие условия: цепочки X, Y и Z не имеют общиз мементов и VZ pi{Z) = Pi{Z). Тогда

!0, ecjiupi(Z)=0

если p,(Z) ф 0 (1)

Pi\Z)

является композицией распределений вероятностей p\{V) upj(iV) ¡11]. •

(Эта теорема является основой многих формальных результатов настоящей работы.)

Пусть дав конечный набор элементарных пропозиций Т. Рассмотрим его непустое подмножество S = Над ним построим множество S* =

{г>1... TV : Г],..., v, € S, г = 0(1 )£} всех возможных положительно-означенных конъюнкций. Исключив из гтого множества пустую цепочку, отвечающую тождественной истине, получим множество: S^ = S" \ {е}. Будем называть это множество полным конусом положительно-означенных конъюнкций над семейством элементарных пропозиций 5 или просто полным конусом над S. Порядок полного конуса равен мощности семейства элементарных пропозипий, над которым он построен. На вновь введенных множествах S* и 5й определено отношение частичного строгого порядка и частичного порядка, задаваемое отношением множеств элементов цепочек по включению [7].

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

Рисунок 1: Полные конусы {гьх5}Л, {та,х4,х5}л-

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

Рассмотрим семейство множеств атомов Агт° — {75,... ,Т„}, причем множества элементарных пропозиций могут пересекаться, а семейство множеств не разделимо па два подсемейства так, что любое мпожество одного семейства не пересекается с каким-нибудь другим множеством второго. Это требование связности. Над каждым множеством элементарных пропозиций построим полный конус: V/ = 1(1 )п С; = 7^, = и С",. Тогда множество с при-

,>*1<1)п

писанной каждой формуле вероятностью назовем алгебраической байесовской сетью (АБС).

Вслед за Дж. Пиарл предполагаем, что эксперт способен учитывать правила, связывающие ограниченное число простых утверждений о предметной области. Наиболее полно ®тот элемент званий вксперта может быть отражен в характеристике вероятностных взаимосвязей над небольшой совокупностью пропозициональных формул. Предлагается в качестве соответствия такому фрагменту знаний (ФЗ) эксперта взять полный конус над 2-3 элементарными пропозициями. Если па элементах ФЗ задано распределение вероятностей, то тогда определена вероятность и каждой пропозициональной формулы, которую можно построить над атомарными пропозициями, входящими в рассматриваемый ФЗ. Далее по тексту работы понятия "фрагмента знаний" и "полного конуса" считаются полностью совпадающими по объему.

Совокупность знаний эксперта организуется в базу знаний. В теории АБС БЗ соответствует алгебраическая байесовская сеть. Мы исключаем из рассмотрения несвязные сети формул, поскольку их компоненты будут соответствовать независимым наборам зияний эксперта и, следовательно, могут Сыть интерпретированы как отдельные БЗ, представленные разными АБС. АБС, как и ФЗ. могут бить представлены > виде диаграмм Хассе. Любую АБС можно достроить до ФЗ, ее содержащего. АБС обычно элдает по одно рпс-пределение вероятностей на пропозициональных формулах, а класс распреде-

лений, возможно, пустой.

Введены понятия линейной (выпуклой) комбинации и линейной (выпуклой) оболочки семейства АБС одинаковой структуры (7). Определение обоих объектов опирается на построение линейной выпуклой комбинации оценок вероятностей соответствующих элементов двух или нескольких АБС одинаковой структуры. Введены понятия линейной цепи ФЗ и цикла ФЗ. Схематически линейная цепь ФЗ представляется незамкнутой последовательностью стоящих рядом ФЗ, в которой никакой ФЗ не может иметь общих влементов с другим ФЗ, которые бы не принадлежали непосредственному соседу исходного ФЗ. Цикл ФЗ получается при замыкании линейной цепи ФЗ.

В третьей главе рассмотрены и решены задачи поддержания непротиворечивости БЗ, представленных в виде АБС, и априорного вывода в них.

Пусть построен ФЗ С = 5й, над элементами которого определена точечная функция которая, как предполагается, задает распределение вероятностей над конъюнкциями из ФЗ, которое можно распространить до распределения р° на множестве квантов Q(S), а с него — на распределение р над множеством всех пропозициональных формул F°(S): jp* : С —► [0,1], р° : Q —> [0,1], р : —► [0,1]. Будем говорить, что функция jf* действительно задает распределение вероятностей на ФЗ С, или задает непротиворечивое назначение вероятностей на этом ФЗ, или что ФЗ С — непротиворечив, и обозначать этот факт квантором Cousis [С, j^], если соответствующая индуцируемая функция р° удовлетворяет следующим условиям: VS € й : p°{S) > 0 и J^p'lS) = 1.

i

Эти условия вытекают из аксиоматики вероятности.

X

Пусть теперь задана функция с интервальными значениями jf* над элементе

тами ФЗ С, такая, что: С —► {|a,6¡ : в, Ь 6 |0,1],а < Ь}. Будем говорить, что

ж

эта функция р^ задает непротиворечивое назначение вероятностей ва этом ФЗ или что ФЗ С — интервально непротиворечив, и обозначать этот факт

квантором Consis

если выполнено следующее условие:

У/еСУ*, € ;£(/)

| — [0,1]} :(/(/) = С: Л*) Ы)&Сою5в [С.^].

Хальперн, Фаджин, Миджидо предложили свести проблему определения непротиворечивости интервальных вероятностей к задачам линейного программирования (ЗЛП), яо конкретные способы формирования ЗЛП для решения на ЭВМ были лишь намечены. В диссертации предложен следующий способ. Вероятности кваптов из набора, соответствующего рассматриваемому ФЗ, выражаются через значения вероятностей элементов ФЗ. Полученные выражения должны бить неотрицательны. На основе »того условия формируется первое множество линейных неравенств (¿Г1''). Второг множество Р1'' линейных неравенств формируется па основе зналий о предметной области.

Объединение множеств »тих неравенств обозначается 72'"', где i — порядок ФЗ. Тогда ЗЛП, которые нужно Судет решить для каждой формулы ФЗ /, чтобы получить ее новые, согласованны с остальными нижнюю и верхнюю оценхи вероятности, примут следующий вид:

Р (Л nto>»(/), ? (/) :=шгосРС/). (2)

Itü) uCj)

Бели хотя бы для одного влемента ФЗ ЗЛП (2) не имеет решения, то вто означает, что ве существует ни одного вероятностного означивания элементов ФЗ, которое удовлетворяет аксиомам вероятности при заданных условиях. Этот факт соответствует противоречивости ФЗ.

Решая ЗЛП (2), можно получать опенки вероятностей елеыентов ФЗ и других пропозициональных формул. Этот процесс называется априорным выводом. Априорный вывод > данном контексте — вто вывод знаний, ве содержащихся в БЗ в явном виде. Процессы поддержания непротиворечивости и априорного вывода тесво связаны.

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

Описан важный, с точки зрения упрощения вычислений, частный случай априорного вывода, касающийся получения оценок вероятностей цепочек конъюнкций атомов с разными логическими означиваниями.

Описан подход к определению понятия непротивречивости АБС. Пусть дава АБС Лге и ФЗ С, содержащий эту сеть. Пусть также над элементами Л/с определена точечная функция р^, которая, как предполагается, задает распределение вероятвостей над этой сетью: р^ : ,\гс —> £0, X]. Будем говорить, что функция действительно задает распределение вероятвостей на АБС или задает непротиворечиво назначение вероятностей на »той АБС, или что ABC Л^ — непротиворечива, и обозначать этот факт квантором Consis [.Vc,pA], если выполнено следующее условие:

3/ € {ф: С —> [0,11} : (Vf 6 Л'с : ЛЯ = pÄ(/))&(Consis [С.р*])

Пусть дана АБС Л'с и минимальный ФЗ С, содержащий эту сеть. Пусть

также над элементами Av определена интервальная функция ркоторая задает назначение интервальных оценок вероятностей над этой сетью:

р*: Л'с —' {М]: о, fc е |0, l],e < b)

Будем говорить, что функция рл задает непротиворечивое назначение интервальных вероятностей иа втой АБС или что АБС Ме — интервально непротиворечива, и обозначать этот факт квантором Соп515 , если выполнено следующее условие:

З^е {у>|* : С —> {¡а,Ь] : а,Ь 6 |0,1],в < I}} : (V/ 6 К'с Ф (/) (/))&(Сопби

В [3, 8] показано, что следует различать следующие три степени непротиворечивости АБС:

• внутренняя непротиворечивость — когда выполняется требование о непротиворечивости вероятности в каждом отдельном ФЗ, образующем АБС; здесь еще даже нельзя говорить о самой АБС — не рассматривается требование согласованности, если только АБС не состоит из одного ФЗ;

• внешняя непротиворечивость — когда выполнено требование внутренней непротиворечивости, а также условие согласованности оценок вероятностей элементов АБС;

• непротиворечивость в целом — когда выполнено требование внешней непротиворечивости и второе, более сильное, требование непротиворечивости распределения вероятности.

Существует и другое основание для деления степеней непротиворечивости АБС на классы. Рассмотрим семейство всех подмножеств мощности Л множества всех атомов, входящих в АБС. Надстроим над каждым таким подмножеством ФЗ и потребуем выполнения условия внешней непротиворечивости АБС с добавленными вновь образованными ФЗ. Если удается удовлетворить условие внешней непротиворечивости пополненной АБС, то назовем такую АБС ^-непротиворечивой.

Теорема 4 Пусть даны две непротиворечивые в целом АБС с одинаковой структурой и Л^, два действительны! -числа а и (3, такие, что: о, ,3 £ [0,1] и а + в — 1. Тогда АБС Л^э = аЛ/1 + /ЗЛ'а будет также непротиворечива в целом /7/.•

Теорема 5 Пусть Л" — семейство непротиворечивых в целом АБС. Тогда любая АБС.V., 6 Sp.ni [Л*] также является непротиворечивой в целом /7/.»

Теорема 6 Если праста-я АБС внешне непротиворечиво, то она также непротиворечива в целом /?/.•

Теорема 7 Если простая АБС внешне интервально непротиворечива, то она также интервально непротиворечива в целом /7/. •

Приводятся схемы алгоритмов априорного вывода и поддержания непротиворечивости, сводящиеся к определению условий 3ЛП, решаемых для получения новых оцевок вероятностей влемевгов АБС, и последовательности их решения [3, 7, 8).

Теорема 8 Алгоритм поддержания непротиворечивости АБС сходится и имеет на выходе один из двух результатов: оценки вероятностей влемеьтов данной АБС иди сообщение о противоречивости исходных оценок вероятностей элементов данной АБС /7/.»

Теорема 9 Оценки вероятностей элементов АБС, полученные в результате применения алгоритма поддержания непротиворечивости, являются непустыми замкнутыми промежутками ¡7).»

Теорема 10 Оценки вероятностей элементов АБС, полученные в результате применения алгоритма поддержания непротиворечивости, являются непротиворечивыми в соответствии с той степенью непротиворечивости, требования которой описывают множества £ и V ¡7].*

Рассматриваются модификации алгоритмов поддержания непротиворечивости АБС и априорного вывода в них.

Четвертая глава содержит изложение вопросов, касающихся апостериорного вывода в АБС.

Свидетельство — вто апостериорная точечвая оценка вероятности атомарной пропозициональной формулы, входящей в ФЗ или БЗ. Кортеж свидетельств состоит из вабора свидетельств. Говоря об апостериорном выводе, мы прежде всего предполагаем, что уже существует одна или несколько АБС, непротиворечивых в заданной степени, и свидетельство или кортеж свидетельств, описывающий произошедшие события. Апостериорный вывод имеет целью вычисление апостериорной вероятности некоторых СБП, случайных величин, формул и т.п., семантика и состав которых определяются конкретной прикладной задачей. Можно показать, что эти апостериорные вероятности легко вычисляются, если получены опенки вероятностей кортежей свидетельств и построена АБСе апостериорными значениями вероятности ее элементов (теорема Байеса). Поэтому апостериорный вывод имеет в общем случае две взаимосвязанные цели: оценить вероятность свидетельства или кортежа свидетельств над АБС и пересчитать вероятности цепочек конъюнкций, входящих в АБС, исходя из поступивших свидетельств. Полученвые в результате апостериорного вывода оценки могут быть применены, в частности, для отнесения явления, характеризуемого кортежом свидетельств, к какому-либо классу явлевий. Другим применением полученных оценок может стать прогноз наиболее вероятного события при заданном кортеже свидетельств и т.п.

Концепция апостериорного вывода рассмотрена посредством анализа последовательности возможных варирантов структур БЗ: от самой простой.

когда БЗ представлена в виде единственного ФЗ с точечными оценками вероятностей его элементов, до самого сложного, когда БЗ представлена в виде АБС с интервальными оценками вероятностей ее элементов. Кроме того, сначала рассматривается случай детерминированного свидетельства, потом кортежа детерминированных свидетельств, затем случай недетерминированного свидетельства и, наконец, кортежа недетерминированных свидетельств. Такой порядок изложения определяется тем, что АБС и кортежи недетерминированных свидетельств, как сразило, задают класс распределений вероятностей, в отличие от ФЗ с точечными оценками вероятностей и кортежей детерминированных свидетельств. Если задан класс распределений, то однозначный вывод в принципе невозможен, и следует либо определить класс возможных результатов, либо сделать содержательный обоснованный приложением выбор одного результата из этого класса. Некоторые из возможных вариантов выбора исследованы в работе.

Свидетельство является детерминированным, если оно представляет собой оценку суждения как ложного или истинного. Недетерминированное свидетельство допускает оценку истинности суждения вероятностью, принимающей значения в промежутке [0,1].

В случае детерминированных свидетельств вычисления сводятся к поиску вероятности в ФЗ означивания случайной бинарной последоватедльности (СБП), задаваемого детерминированным свидетельством или их последовательностью, а также к оценке условных вероятностей элементов ФЗ при заданном кортеже недетерминированных свидетельств. Обе задачи решаются с помощью специального алгоритма, схема котрого описана в диссертации. Интервальные оценки, которые присутствуют в вычислениях, если некоторые элементы ФЗ обладали интервальными оценками своей истинности, обрабатываются с помощью приемов интервальной математики. Это приводит к решению задач поиска максимумов и минимумов значений формул, в которых появляются интервальные величины. Таким образом, формируются две оценки: апостериорной вероятности элементов ФЗ при заданвом кортеже детерминированных свидетельств и априорной вероятности кортежа детерминированных свидетельств в заданном ФЗ.

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

Аналогичным образом рассмативается и случай с кортежом недетерминированных свидетельств. Предполагается, что на всем наборе возможных истинностных означиваний свидетельств из кортежа задано распределение вероятности. Каждое означивание кортежа недетерминированных свидетельств может рассматриваться как кортеж детерминированных свидетельств. Поэтому для каждого означивания производится апостериорный вывод в ФЗ, а

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

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

Апостериорвый вывод в АБС сводится к апостериорному выводу в ФЗ посредством погружения АБС в соответствующий ФЗ. Эта операция может быть выполнена как непосредственно, если АБС обладает малым количеством элементов, так и косвенно, когда недостающие оценки вероятностей вычисляются по мере необходимости.

Заметную роль в рассмотрении вопросов апостериорного вывода занимают его частные случаи, в которых получение оценок априорной вероятности кортежа свидетельств в данной АБС и апостериорных вероятвостей алементов АБС в данном кортеже упрощается за счет учета структуры конкретной АБС или наличия сведений о вероятностных связях между ФЗ данной АБС.

Особый интерес представляют АБС, не содержащие циклов ФЗ, так называемые простые АБС. Апостериорный вывод в вих сводится к апостериорному выводу в линейных цепях ФЗ. Для апостериорного вывода в линейных цепях ФЗ приводятся схемы двух алгоритмов распространения влияния свидетельств. Первый, условно названный "алгоритмом апостериорного вывода посредством вычисления математических ожиданий", реализуется достаточно просто, во математический смысл получаемых в нем результатов неочевиден. Второй, наоборот, имеет четкую трактовку математического смысла результатов — он основан на продолжении распределения вероятвостей с цепи ФЗ ва ФЗ, ее содержащий, по теореме о композиции распределений СБП, — но не имеет аффективной реализации. Сформулированы теоремы 11-18 [14], которые позволяют утверждать, в частности, что эти алгоритмы дают одинаковые оценки априорной вероятности кортежа фактов в соответствующей линейной цепи ФЗ, и апостериорной вероятности ее влементов при заданном кортеже фактов.

Рассмотрены способы обработки циклов ФЗ в АБС в процессе апостериорного вывода.

Приводихшй ниже результат дает основапие для сравнения выразительных мощностей аппарата АБС и его "освовяого конкурента" байесовских сетей доверия (БСЛ).

Теорема 14 Любая БСЛ может быть преобразована в простую АБС, ФЗ которой имеют в пересечении не более одного элемента ¡9, 15].*

Заключение

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

1. Показано, что существующие количественные модели неопределенности знаний не только, по словам Н. Нильссоаа, "делают (иногда неявные и непризнаваемые) дополнительные предположения о лежащих в их основе распределениях вероятностей,'' но и зачастую игнорируют противоречивость исходных данных. Кроме того, эти модели обладают другими недостатками и ограничениями. В качестве основы нового метода количественного представления неопределенности знаний эксперта в интеллектуальных системах выбрана модель алгебраических байесовских сете": (АБС).

2. Предложен новый способ формирования ограничений для ЗЛП, решаемых в процессе поддержания непротиворечивости ФЗ и БЗ, а также априорного вывода в них. Предложены схемы алгоритмов этих процессов и описаны некоторые их модификации. Показано, что алгоритм поддержания непротиворечивости сходится и результаты его корректны. Поддержание непротиворечивости БЗ позволяет уменьшить неопределенность внесенных в вее знаний за счет их согласования.

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

4. Выделен класс БЗ, представимых в виде простых АБС. поддержание непротиворечивости в целом которых упрощено благодаря их структуре. Предложены подходы к обработке циклов ФЗ в БЗ, в частности, сводящиеся к разбиению БЗ на простые АБС и заданию критерия согласованности результатов апостериорного вывода по свидетельствам, влияние которых распространяется различными путями. Кроме того, доказано, что байесовские сети доверия (БСД) трансформируются в простые АБС, ФЗ которых имеют в пересечении не более одного элемента. Показано, что аппарат АБС обладает большей выразительной мощностью, чем аппарат БСЛ.

Предложенная и исследованная в диссертации модель представления и манипулирования неопределенностью знаний позволяет работать с качественными и интервальными оценками вероятностных связей, различать представление "незнания" и противоречия, не накладывает неоправданных ограничений на структуру БЗ, опираясь на строгий теоретико-вероятностный подход, поддерживает механизмы контроля непротиворечивости БЗ. допускает на локальном уровне (яа уровне ФЗ) представление произвольного распределения вероятностей, различает разные виды вывода: априорный и апостериорный (ва основе свидетельств).

Список публикаций по теме диссертации

[1] Городецкий В.И., Тулупьев A.JI. Алгебраические байесовские сети для представления и обработки званий с неопределенностью. // 4-я Санкт-Петербургская конференция Региональная информатика-95: Тезисы докладов, ч. 1. — СПб., 1995. — с. 51-52.

[2] Городецкий В.И., Тулупьев A.JI. Генерация выборки с заданным распределением зависимых случайных событий на основе алгебраической байесовской сети. // 4-я Санкт-Петербургская конференция Региональная ивформатика-95: Тезисы докладов, ч. 1. — СПб., 1995. — с. 50-51.

[3] Городецкий В.И., Тулупьев А.Л. Непротиворечивость баз знаний с интервальной мерой вероятности. // 4-я Санкт-Петербургская конференция Региональная ивформатика-95: Труды. — СПб., 1996. — с. 85-91.

[4] Лобацевич A.B., Тулупьев А.Л. Применение методов индуктивного обучения и аппарата алгебраических байесовских сетей для решения задач классификации текстовой информации. ]/ 4-я Санкт-Петербургская конференция Региональная инфорыатика-95: Тезисы докладов, ч. 1. — СПб., 1995. — с. 73-74.

[5] Лобацевич A.B., Тулупьев А.Я. Использование методологии машинного обучения для создания интеллектуальных посредников. // Международная конференция Эволюция инфосферы-ЭЗ: Тезисы. (В печати).

[6] Лобацевич A.B., Тулупьев А.Л. Классификация текстовой информации с использованием индуктивного обучения и аппарата алгебраических байесовских сетей. Ц Информационные технологии и интеллектуальные методы. — СПб., СПИИРАН, 1993. — с. 120-124.

[7] Тулупьев А.Л. Алгебраические байесовские сети: теоретические основы и непротиворечивость. — СПб., СПИИРАН, 1395. — 76 с.

JS] Тулупьев А.Л., Городецкий В.И. Алгебраические байесовские сети: поддержание непротиворечивости баз знаний. // Международная конференция ЗЕания-Диалог-Решение (KDS-95): Доклады. — Ялта, 1995. — с. 151-159.

¡9] Тулупьев А.Л. Непротиворечивость знаний с неопределенностью и вывод га них. // Всероссийская ЕгучЕО-техническая конференция ЭлектроЕкка и информатика: Тезисы. — М.. 1995. — с. 309-310.

[¡0] Тулупьев А.Л. Эволюция моделей неоаределенности. // Международная конференция Эволюция инфосферы-95: Тезисы. (В печати.)

[11] Тулупьев А.Л. Композиция распределений случайных бинарных последовательностей. // Информационные технологии и интеллектуальные методы. — СПб., СПИИРАН, 1996. — с. 105-112.

[12] Тулупьев А.Л. Структуры вероятностей на пропозициональных формулах. // Информационнее технологии и интеллектуальные методы. — СПб., СПИИРАН, 1996. — с. 61-70.

[13] Лобацевич A.B., Тулупьев А.Л. Концепция функционирования интеллекту-альвого агента, основанная на генерации баз знаний с неопределенностью. // 5-я СаЕкт-Петербургская конференция Региональная информатика-96: Тезисы докладов. Т.1. — СПб., 1996. — с. 61-62.

[14] Тулупьев А.Л. Апостериорный вывод в базах знаний интеллектуальных систем. // 5-я Санкт-Петербургская конференция Региональная ивформатика-96: Тезисы докладов. Т.1. — СПб., 1996. — с. 73-74.

[15] Тулупьев А.Л. Представление неопределенности званий в байесовских сетях доверия и алгебраических байесовских сетях. // 5-я Санкт-Петербургская конференция Региональная информатика-96: Тезисы докладов. Т.1. — СПб.. 19&6. — с. 72-73. У " ' '

Подписано s аечеть 8.05.&6. Офсетный уос-о* гИНВЭКО-про=кт Зак. 795. T:ip. 70. Бесплатно.