Диссертация (1149691), страница 11
Текст из файла (страница 11)
С точки зрения программной имплементации, процесс распространения свидетельства можно распараллелитьза счет независимости апостериорных вероятностей в разных ветвях дерева.При таком подходе быстрее всего получится распространить свидетельствов дереве с наименьшей глубиной.2.7Выводы по главеВ данной главе введены основные определения, элементы и понятиятеории алгебраических байесовских сетей. Рассмотрены 2 множества, надкоторыми строятся фрагменты знаний — идеал конъюнктов и множествопропозиций квантов, а также указаны формулы, связывающие элементыданных множеств. В следующей главе мы рассмотрим альтернативнуюмодель фрагмента знаний (идеал дизъюнктов) и предложим матричныеуравнения для связи новой модели с указанными выше.В разделах 2.2–2.6 приведены основные результаты локального логико-вероятностного вывода, включая априорный вывод, апостериорныйвывод, проверку и поддержание непротиворечивости.
Рассмотренные матрично-векторные уравнения являются важным шагом, позволившим уйтиот функционального описания и упростить алгоритмы логико-вероятностного вывода. Приведенные уравнения логико-вероятностного выводаявляются базой для дальнейших исследований в данной области, проведенных в рамках диссертационного исследования и изложенных в следующейглаве.61Наконец, последний раздел данной главы посвящен глобальнымструктурам алгебраической байесовской сети, а именно первичной и вторичной структурам. Графы смежности находят применение во многих областях— СУБД, задачи удовлетворения ограничений и байесовских сетях доверия и являются объектом продолжающихся исследований по обучениюструктуры алгебраической байесовской сети.
В рамках 3й главы вторичнаяструктура выполняет роль своеобразного каркаса для проведения глобального вывода, а именно описания алгоритмы распространения виртуальногосвидетельства по сети.62Глава 3. Апостериорный вывод в фрагментах знанийалгебраических байесовских сетей3.1ВведениеВ разделах 2.2–2.6 описаны локальные и глобальные структуры алгебраической байесовской сети, а также введен математический аппарат,необходимый для обработки знаний с неопределенностью. Однако, несмотря на то что рассмотренные алгоритмы локального логико-вероятностноговывода предлагают частичный переход от функционального языка к матрично-векторной нотации, в них по прежнему присутствует избыточность.Особенно остро данный вопрос встает в случае неточных (интервальных)оценок вероятностей, являющихся наиболее общим и приближенным к реальным данным случаем.Логико-вероятностный вывод является одним из основополагающихаппаратов теории байесовских сетей, позволяя динамически вычислять иизменять оценки вероятности истинности элементов с учетом поступающихданных.
В предыдущей главе мы рассмотрели классические модели носителей ФЗ — идеал конъюнктов и набор пропозиций-квантов. Третья главаначинается с рассмотрения в параграфе 3.2 альтернативной модели ФЗ надидеалом дизъюнктов. Далее мы рассмотрим алгоритмы логико-вероятностного вывода, полученные переходом к использованию матрично-векторнойнотации в нормирующем множителе уравнений апостериорного вывода.Предложенные в главе 3.3 вектора позволяют сформулировать в параграфе 3.4 задачи линейного программирования для проведения вывода надданными с неопределенностью, а также дают возможность выполнять отложенные вычисления, описанные в разделе 3.5, что немаловажно с учетомработы с большими данными.Пользуясь новыми формулами, в разделе 3.7 рассмотрим анализ чувствительности задач апостериорного вывода и дадим грубую и точнуюоценки чувствительности для всех трех видов фрагментов знаний, а в параграфе и 3.6 дадим точные оценки сложности решения задач апостериорноговывода для различных видов оценок ФЗ и поступающего свидетельства.63Раздел 3.8 главы посвящен применению описанных результатов влогико-вероятном выводе к глобальному апостериорному выводу.
Сформулированные утверждения предлагают алгоритм передачи виртуальногосвидетельства из одного фрагмента сети в другой в матричной форме.Глобальный апостериорный вывод подразумевает развитие глобальныхструктур, над которыми и производится распространение свидетельства.Элементы синтеза глобальных структур рассматриваются в заключительном параграфе главы 3.9.3.2Альтернативные модели фрагментов знанийКак уже говорилось, выбор наиболее подходящей модели фрагментазнаний,а значит и уравнений ЛВВ, во многом зависит от области знаний,откуда извлекаются данные. Одним из рассматриваемых в рамках теорииАБС множеством является идеал дизъюнктов:{ 1∨2 ∨ . . .
∨ |0 6 1 < 2 < . . . < 6 − 1, 0 6 6 },где 1 ∨ 2 ∨ . . . ∨ означает дизъюнкцию соответствующих переменных.Идеал дизъюнктов содержит все возможные дизъюнкции атомов заданногоалфавита, в том числе пустую дизъюнкцию и сами атомы. Таким образомфрагменту знаний, построенному над идеалом дизъюнктов соответствуетвектор вероятностей идеала дизъюнктов — Pd . Аналогично идеалу конъюнктов и множеству пропозиций-квантов, над идеалом дизъюнктов задананумерация оп принципу, описанному в разделе 2.2. Ниже представленатаблица, иллюстрирующая нумерацию дизъюнктов, в фрагменте знаний,построенном над алфавитом из трех атомов.Теперь обратимся к вектору вероятностей дизъюнктов Pd и вспомо′гательному вектору Pd = 1 − Pd , где 1 — единичный вектор такой жедлины, как и вектор Pd .64Таблица 2 — Нумерация элементов идеала дизъюнктов№ №(двоичная система)Disjunct00001001201030114100510161107111121 ∨ 231 ∨ 32 ∨ 31 ∨ 2 ∨ 3Рассмотрим вид о отношение векторов Pd и 1 − Pd в случае фрагментазнаний над алфавитом 1 ,1 :⎛Pd =0⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝( 1) ( 2) ⎞⎛⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝и 1 − Pd =( 2 ∨ 1 )⎞1⎟⎟⎟⎟⎟⎟⎟.⎟⎟⎟⎠( 1) ( 2) (3.1)( 2 1) (Более детальный разбор такого вида примеров можно найти в [109].)Теперь воспользуемся соотношением, полученнымранее[150], для век⎛⎞тора 1− Pd: E I (1 − Pd ) = Pq , где E =0...⎜⎜⎜⎜⎜.
. .⎜⎝11⎟⎟⎟⎟. . .⎟⎟⎠— матрица, в1 ... 0которой на всех позициях кроме второй диагонали стоят нули, а втораядиагональ занята единицами. Введем новую матрицу [90; 91]⎛(︁L = E I = EI1[ ])︁⎜=⎜⎝⎞⎛0 0 ⎟ ⎜11 0⎟⎜⎠⎝0[ ]⎞ −11⎟⎟⎠⎛⎜=⎜⎝01[ ]⎞ 1⎟⎟⎠−1.(3.2)Тогда вектор вероятностей пропозиций-квантов можно выразить через вектор вероятностей идеала дизъюнктов как: Pq = L (1 − Pd ).Рассмотрим переход между вектором вероятностей элементов идеаладизъюнктов фрагмента знаний и вектором вероятностей идеала конъюнктов. Ранее было получено равенство Pc = J Pq .
Домножим обе части65ранее рассмотренного уравнения: E I (1 − Pd ) = Pq на J . Получим:J E I (1 − Pd ) = J Pq = Pc . Введем новую матрицу K :(︁K = J E I = J1 EI1⎜⎜[ ]⎞⎛⎞⎛⎛⎛⎜=⎜⎝⎝)︁1 1 ⎟ ⎜0 1 ⎟ ⎜ 1−1010 1⎟⎜⎠⎝1 0⎟⎜⎠⎝[ ]⎛⎛⎞⎞ ⎟⎟⎟⎟⎠⎠⎜⎜⎜=⎜⎝⎝11[ ]⎞⎞ 0 ⎟⎟⎟⎟⎠⎠−1.Выразим вектор вероятностей идеала конъюнктов посредством вектора вероятности идеала дизъюнктов: K (1 − Pd ) = Pc . Также заметим, что′K−1 = K . Введем обозначение: Pd = 1 − Pd .
Затем, используя введенноеранее обозначение, получим:′′Pq = L Pd и Pc = K Pd ,⎛где L =⎜⎜⎝011[ ]−13.3⎛⎞ ⎟⎟⎠,K =⎜⎜⎝110(3.3)[ ]⎞ ⎟⎟⎠−1.Обработка стохастического свидетельстваВ предыдущей главе мы показали, что фрагменты знаний классифицируются по двум признакам:– множество элементов, над которым построен ФЗ;– тип оценок вероятностей элементов ФЗ.Говоря об апостериорном выводе в разделе 2.5 мы рассматривали 3 видасвидетельств, рассматриваемые в рамках алгоритмов вывода — детерминированное, стохастическое и неточное. Случай пропагации свидетельства вфрагмент знаний с бинарными оценками вероятностей является тривиальным и был также рассмотрел в 2.5.
Таким образом, всего рассмотрению врамках данной главы подлежит 6 комбинаций свидетельств и оценок вероятностей в ФЗ [137; 166]:– детерминированное свидетельство и скалярные оценки вероятностей;– детерминированное свидетельство и интервальные оценки вероятностей;66–––––стохастическое свидетельство и скалярные оценки вероятностей;стохастическое свидетельство и интервальные оценки вероятностей;неточное свидетельство и скалярные оценки вероятностей;стохастическое свидетельство и интервальные оценки вероятностей;неточное свидетельство и интервальные оценки вероятностей.Ввиду различий в строении моделей, каждый из приведенных выше случаев мы рассмотрим для фрагментов знаний, построенных над каждым изтрех множеств элементов — идеалом конъюкнтов, идеалом дизъюнктов инабором пропозиций-квантов.3.3.1Фрагмент знаний над идеалом конъюнктовСущественным недостатком [124] предложенных ранее уравнений апостериорного вывода [158; 159; 161] описываемых уравнением 2.9 являетсянезавершенный анализ структуры выражений, стоящих в знаменателях и,таким образом, являющихся нормирующими множителями.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
