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

Задача выбора распределения, отражающего вероятностную семантику алгебраической байесовской сети[1]

, аспирант кафедры информатики СПбГУ,
м. н.с. СПИИРАН, *****@***ru

Аннотация

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

Введение

Настоящий доклад посвящен одной из задач теории алгебраических байесовских сетей (АБС). АБС может быть использована для моделирования вероятностных взаимосвязей в сложных системах [4]. Такие системы представляются как наборы зависимых булевых случайных элементов, разбитые на поднаборы, образующие фрагменты знаний. АБС формализованы с помощью вероятностной логики [7], что позволяет говорить об оценках вероятностей пропозициональных формул, составленных на основе случайных элементов сети и о вероятностной семантике сети, то есть наборе совместных распределений данных элементов, задаваемом АБС.

Алгоритмы логико-вероятностного вывода [1], предоставленные инструментарием АБС, позволяют модифицировать параметры модели для её применения в конкретной ситуации, что осуществляется посредством передачи свидетельства в сеть. Для того чтобы ответить на вопрос, каким образом поступающее свидетельство меняет вероятностную семантику сети, необходимо предоставить метод её определения для случаев циклической и ациклической сети.

Описание модели

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

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

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

Подходы к выбору распределения

Случай ациклической сети

Для набора ФЗ , задающего непротиворечивую сеть можно построить [2] объемлющий ФЗ со следующими свойствами: , . Такой ФЗ обладает интервальными оценками вероятности и задаёт семейство всех возможных распределений, задаваемых сетями, содержащими заданный набор ФЗ.

Поскольку в теории АБС разработаны методы обработки интервальных вероятностей [3], возможно не разрешать неопределенность, присущую АБС, и определять её вероятностную семантику как набор всех возможных распределений, построенных с помощью алгоритма построения объемлющего ФЗ. Недостатком такого подхода является сложность операций по обработке интервальных вероятностей по сравнению с их эквивалентами для скалярного представления.

Другим подходом к определению семантики АБС является типичное [6] для вероятностных графических моделей использование предположений об условной независимости. Наборы таких предположений представляются с помощью графа. Данный граф в теории АБС называется графом смежности [5] и отражает структуру пересечений ФЗ. В вершинах такого графа располагаются ФЗ, а каждому из ребер сопоставлен сепаратор — множество переменных, содержащихся в ФЗ, инцидентных данному ребру. Для АБС набор таких предположений определяется правилом: если для двух случайных элементов и , не лежащих в одном ФЗ, и набора сепараторов верно , если любой путь из ФЗ, содержащего , до ФЗ, содержащего , проходит по ребру, соответствующему одному из сепараторов из . В случае ациклической сети построенный таким образом набор предположений позволяет полностью задать совместное распределение для всех переменных, входящих в сеть.

Случай циклической сети

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

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

Алгоритм поиска распределения.

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

1.  Из набора ФЗ , содержащихся в цикле, случайным образом выберем один.

2.  Так как сеть, состоящая из всех остальных ФЗ данного набора, является ацикличной, применим алгоритм выбора распределения на основе предположений об условной независимости, ФЗ — результат применения такого алгоритма — обозначим через .

3.  До тех пор, пока данное действие изменяет , передадим в один из фрагментов знаний в качестве свидетельства.

Данный алгоритм является адаптацией алгоритма IPFP [8], в котором фрагмент знаний АБС рассматривается как набор ограничений на совместное распределение.

Для проверки правильности работы описанного алгоритма была реализована программа на языке java. Для всех автоматически сгенерированных примеров циклов АБС верны свойства:

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

2.  Результат не зависит от выбора фрагмента знаний на шаге 1.

3.  Результат выполняет ограничения независимости, накладываемые сетью.

4.  Результат совпадает с ФЗ, полученным непосредственным решением оптимизационных задач.

Заключение

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

Литература

1.  Тулупьев  байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности. СПб.: СПбГУ; «Анатолия», 2007. 40 с. (Элементы мягких вычислений).

2.  , , Сироткин сети: логико-вероятностный подход. СПб.: Наука, 20с.

3.  Тулупьев А. Л., Сироткин А. В., Николенко  сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. ун-та. 20c.

4.  , , Николенко согласованных оценок истинности утверждений в интеллектуальных информационных системах // Известия высших учебных заведений: Приборостроение. 2006. №7. 20–26 с.

5.  , Тулупьев анализ систем минимальных графов смежности // Труды СПИИРАН. 2009. № 11. С. 104–129.

6.  Koller D., Friedman N. Probabilistic Graphical Models: Principles and Tech-niques. MA:MIT Press. 20p.

7.  Nilson N. J. Probabilistic logic // Artificial Intelligence. N. 28(P. 71-87.

8.  Vomlel. J. Methods of Probabilistic Knowledge Integration. PhD Thesis. Department of Cybernetics, Faculty of Electrical Engineering, Czech Technical University. December 1999.

[1] Работа выполнена при финансовой поддержке РФФИ, гранты № -a, -мол_а.