СОГЛАСОВАННОСТЬ ДАННЫХ И ОЦЕНКА ВЕРОЯТНОСТИ АЛЬТЕРНАТИВ В ЦИКЛЕ СТОХАСТИЧЕСКИХ ПРЕДПОЧТЕНИЙ
ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ И СИСТЕМЫ
УДК 004.8
А. Л. ТУЛУПЬЕВ
СОГЛАСОВАННОСТЬ ДАННЫХ И ОЦЕНКА ВЕРОЯТНОСТИ АЛЬТЕРНАТИВ В ЦИКЛЕ СТОХАСТИЧЕСКИХ ПРЕДПОЧТЕНИЙ
Рассматривается подход к проверке согласованности данных и вычислению оценок вероятности альтернатив на основе преобразования цикла стохастических предпочтений во фрагмент знаний алгебраической байесовской сети и последующего логико-вероятностного вывода. Предлагаемый подход может быть использован при разработке систем поддержки принятия решений.
Ключевые слова: байесовские сети, стохастические предпочтения, принятие решений, вероятностная семантика, модели знаний с неопределенностью, логико-вероятностный вывод.
Введение. Одна из наиболее распространенных функций систем поддержки принятия решений (СППР) — представление и хранение структуры предпочтений, используемых лицом (или группой лиц, или экспертами), принимающим решения (ЛПР) [1]. Такие системы позволяют на основе имеющихся данных ранжировать возможные решения [2] или оценивать вероятность реализации двух или более альтернатив (посредством сравнения их значимости и возможности реализации) [3].
Лицо, принимающее решение, обладая достаточными познаниями в предметной области, как правило, не имеет специальной математической подготовки для того, чтобы учесть все особенности и ограничения различных формальных подходов, применяющихся в СППР. Кроме того, далеко не всегда элементы в том объеме знаний, которым располагает опрашиваемый специалист, идеально согласованы. Это приводит к тому, что полученные сведения о его системе предпочтений могут оказаться в какой-то части непригодными для представления или обработки с помощью СППР. Например, система предпочтений может быть противоречивой, при этом противоречия в различных подходах могут проявляться поразному. Один из основных их видов — цикл предпочтений, который в простейшем детерминированном случае выглядит как, например, следующая система утверждений: „A важнее, чем B“; „В важнее, чем C“; „C важнее, чем A“. В этом случае определить, что важнее, невозможно.
Читателю противоречивость приведенного фрагмента системы предпочтений очевидна, поскольку число противоречащих друг другу элементов невелико, они сведены вместе, изолированы от других сведений и, наконец, читатель понимает то, что написано. Программа же, используемая в СППР, может распознать противоречие только по формальным признакам.
Как правило, при появлении столь жестко детерминированных циклов в предпочтениях не остается ничего иного, как вернуться к опросу ЛПР и в диалоге с ним модифицировать систему предпочтений [2]. Однако высказывания о предметной области не всегда столь
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 7
4 А. Л. Тулупьев
однозначны. В них может присутствовать доля неопределенности, которую удается представить в виде оценки доверия к истинности высказывания [3—5]. Одним из примеров таких оценок является вероятность истинности высказывания, а цель настоящей статьи состоит в описании цикла стохастических (или вероятностных) предпочтений, его формализации, результатов его анализа и способа обработки. Такие циклы нередко возникают при обработке мнений большой группы экспертов, при ранжировании большого числа альтернатив, а также при голосовании в группе.
Измерения (и иные процедуры), направленные на выявление системы предпочтений, свойственны ряду предметных областей и наук. Например, в маркетинге „средством измерений“ является опросный лист клиента (покупателя), в психологии — тестовая методика, в социологии — анкета, в инженерии знаний — формализованное интервью эксперта или ЛПР, при голосовании — избирательный бюллетень. При этом возможность использования в большинстве областей электронных средств хранения данных обеспечивает доступность сведений о реализации предпочтений. В каждой из перечисленных областей используется соответствующий ей терминологический аппарат, сложились свои способы формализации и описания решения задач, связанных с исследованиями предпочтений, выработаны определенные методы измерений.
В настоящей статье в качестве иллюстрационной задачи предлагается использовать пример, связанный с оценкой (или прогнозом) результатов голосования, проведенного группой (комитетом) из трех человек. Такой пример позволит достаточно ясно и доступно отобразить все особенности проблемы принятия решения в условиях цикла стохастических предпочтений.
Исходная задача. Комитет состоит из трех равноправных членов. Каждый из них голосует „за“ или „против“ относительно проекта решения, вынесенного в повестку дня заседания. Среди членов комитета сложились достаточно устойчивые отношения: выбор, производимый первым членом комитета, зависит от выбора, производимого третьим, выбор второго — от выбора первого, а выбор третьего — от выбора второго. Предпочтения членов комитета отличаются достаточной степенью неопределенности и поэтому формально представляются условными вероятностями вида p(xi | x j ) , i, j = 1, 2, 3 [4—6].
Введем дополнительные обозначения. Пусть x1 соответствует утверждению «первый член комитета голосует „за“», x2 — утверждению «второй член комитета голосует „за“», x3 — утверждению «третий член комитета голосует „за“»; индекс j = i − 1 соответствует значению j, предшествующему значению i, а для i = 1 считается, что j = 3 . Символ x означает
отрицание высказывания x , а символ x называется литералом и может принимать значения
из множества {x, x} .
Таким образом, предпочтения голосующих могут быть формально представлены совокупностью значений шести условных вероятностей: p(x1 | x3 ) , p(x1 | x3 ) , p(x2 | x1) , p(x2 | x1) , p(x3 | x2 ) , p(x3 | x2 ) — иначе говоря, известна вероятность истинности высказываний вида «первый член комитета голосует „за“ при условии, что третий голосует „против“», «первый член комитета голосует „за“ при условии, что третий тоже голосует „за“» и т.д. Заметим, что исходя из теории вероятностей также известны величины p(xi | x j ) = 1 − p(xi | x j ) .
Для завершения спецификации исходной задачи предположим, что вследствие устойчивых отношений между голосующими они, скорее, склонны поддержать проект решения, нежели отвергнуть его. Оценки, описывающие такую ситуацию, приведены в таблице,
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 7
Согласованность данных и оценка вероятности альтернатив в цикле стохастических предпочтений 5
пример 1; предположение о том, что члены комитета придерживаются разных точек зрения, представлено примером 2.
Индекс оценки
i
1 2 3
Результат
Оценка вероятности
(пример 1)
условной
совместной
xi | x j xi | x j
xi
xi x j
0,96 0,75 0,957 0,946 0,97 0,8 0,963 0,928 0,99 0,88 0,986 0,953
p(x1x2 x3 ) p( x1 ∨ x2 ∨ x3 )
[0,918; 0,921] [0,079; 0,082]
Оценка вероятности
(пример 2)
условной
совместной
xi | x j xi | x j
xi
xi x j
0,4 0,05 0,119 0,079 0,5 0,75 0,720 0,060 0,1 0,45 0,198 0,072
p(x1x2 x3 ) p( x1 ∨ x2 ∨ x3 )
[0,020; 0,060] [0,940; 0,980]
Оценка вероятности (пример 3)
условной совместной
xi | x j
0,75 0,25 0,75
xi | x j
0,167 0,5
0,167
xi
0,400 0,400 0,400
xi x j
0,300 0,100 0,300
Исходные данные содержат противоречие [4]
Пусть требуется найти вероятности трех исходов:
— вероятность консенсусного голосования „за“;
— вероятность того, что хотя бы один член комитета проголосует против;
— вероятность того, что первый член комитета проголосует „за“.
Консенсусному голосованию „за“ соответствует логическая формула x1 ∧ x2 ∧ x3 (далее
будем писать x1x2 x3 , опуская знаки конъюнкции); второму исходу соответствует x1 ∨ x2 ∨ x3 ,
а третьему — x1. Обобщение и формализация [4, 6]. В обобщенной версии этой задачи исходные дан-
ные представляют собой направленный цикл (см. рисунок), который для краткости назовем
БСД-циклом (БСД — байесовские сети доверия). Каждому узлу цикла приписаны p(xi | x j ) — тензоры условных вероятностей,
x0=xn
характеризующие неопределенность и силу [4] связи между утверждениями xi и x j , i, j = 1, n. Речь идет о вероятностях приня-
x1
xn–1
тия литералом того или иного означивания в зависимости от означивания литерала в узле-родителе. Индекс j предшествует i.
x2
xn–2
Как правило, j = i − 1, но для i = 1 предшествующим индексом
будет j = n . Будем считать j = n и j = 0 одним и тем же значе-
нием индекса, что приводит, например, к совпадению x0 = xn . Определим величину ri = p(xi | x j ) − p(xi | x j ) .
xi–2
xi+2
На первый взгляд, получившаяся конструкция является ча-
стным случаем БСД, аппарат которых и базовые алгоритмы логико-вероятностного вывода известны и хорошо изучены [5, 7].
xi–1
xi+1
Для решения исходной задачи как раз и требуется по известным исходным оценкам истинности получить другие оценки, которые
xi
не заданы явно. Это и есть один из видов логико-вероятностного вывода.
Однако БСД — это не просто направленный граф с тензорами условных вероятностей в
узлах. БСД (как направленный граф) должна быть еще и ациклической — в ней не должно
быть направленных циклов. Имеющиеся исходные данные (см. рисунок) именно такой цикл и
образуют, что делает невозможным применение существующих БСД-исчислений [7].
Алгоритмы обработки. Возможность обработать БСД-цикл все же существует. Преоб-
разуем имеющуюся совокупность условных вероятностей в совокупность совместных веро-
ятностей [4, 6] и рассмотрим ее как оценки вероятностей элементов идеала конъюнктов —
фрагмент знаний алгебраической байесовской сети (АБС) [5]. Алгоритмы логико-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 7
6 А. Л. Тулупьев
вероятностного вывода для названного фрагмента знаний известны [5, 6], что позволяет най-
ти требующиеся оценки вероятностей.
По формуле полной вероятности можно рассчитать вероятность истинности p(xi ) ут-
верждения xi , если известна вероятность истинности p(x j ) утверждения x j из предыдущего
узла: p(xi ) = p(xi | x j ) p(x j ) + p(xi | x j ) p(x j ) . С учетом ri получим p(xi ) = ri p(x j ) + p(xi | x j ) .
Определив p(xi ) , можно аналогичным образом вычислить p(xi+1) , а затем p(xi+2 ) , p(xi+3 ) и т. д., пока цикл не замкнется на p(xi−1) . На основании p(xi−1) = p(x j ) и в соответствии с оп-
ределением условной вероятности рассчитываются вероятности конъюнкций утверждений
p(xi x j ) = p(xi | x j ) p(x j ) .
Таким образом, если известна маргинальная вероятность [4] хотя бы одного утвержде-
ния из узла цикла, то можно восстановить все остальные маргинальные вероятности вида
p(x j ) , p(xi x j ) , а следовательно, и p(xi x j ) .
Пусть p(x0 ) = ν . Тогда согласно приведенным формулам через неизвестное значение ν
можно выразить последовательно маргинальные вероятности утверждений p(xi ) = pi (ν) .
Неизвестное значение ν определяется из уравнения ν = pn (ν) , которое может иметь единственное решение или бесконечно много решений [4, 6] в зависимости от исходных данных.
Вычислив значение ν, можно, в свою очередь, вычислить значения маргинальных вероятно-
стей вида p(x j ) , p(x j xi ) и, вообще говоря, все вероятности p(xi x j ) .
Определим векторы
P0
=
⎛ ⎝⎜1
ν −
ν
⎞ ⎟ ⎠
=
⎛ ⎝⎜1
p(x0 ) − p(x0
)
⎞ ⎟ ⎠
и
Pi
=
⎛ ⎜⎝1
pi (ν) − pi (ν)
⎞ ⎟ ⎠
=
⎛ ⎜⎝1
p(xi ) − p(xi
)
⎞ ⎟ ⎠
,
а также матрицу
Wj
⎛ = ⎝⎜⎜
p(xi p(xi
| |
xj) xj)
p( xi p( xi
| |
xj xj
)⎞ ) ⎠⎟⎟
.
При этом уравнение ν = pn (ν) эквивалентно матрично-векторному уравнению
P0 = WP0 , где W = Wn × Wn−1 ×…× W1 × W0 , согласно которому вектор P0 есть собственный
вектор произведения матриц W. Вектору P0 должно соответствовать собственное число
λ = 1. Заметим, что матрицы Wi и, следовательно, их произведение W являются стохастиче-
скими, а P0 — вектор вероятностей (его компоненты неотрицательны и в сумме дают едини-
цу) [8]. Значения компонент вектора P0 можно определить по формулам Крамера или методом последовательных приближений [6].
Совокупность вычисленных вероятностей p(x j ) , p(xi x j ) , где 1 ≤ i ≤ n , можно внести в
качестве исходных данных во фрагмент знаний алгебраической байесовской сети. Такой
фрагмент обрабатывается с помощью известных алгоритмов поддержания непротиворечиво-
сти и априорного вывода [4—6]. Эти алгоритмы, в частности, позволяют получить оценки
искомых величин p(x1x2 x3 ) , p(x1 ∨ x2 ∨ x3 ) и p(x1) .
Результаты расчетов по предложенным выше формулам (в частности, оценка p(x1) ), а также результаты логико-вероятностного вывода во фрагменте знаний АБС — искомые
оценки альтернатив p(x1x2 x3 ) и p(x1 ∨ x2 ∨ x3 ) — представлены в таблице. Заметим, что в процессе вывода по исходным данным примера 3 была выявлена их противоречивость [4].
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 7
Согласованность данных и оценка вероятности альтернатив в цикле стохастических предпочтений 7
Выводы. Математической моделью цикла стохастических предпочтений является направленный цикл в байесовской сети доверия. Его невозможно обработать с помощью известных алгоритмов логико-вероятностного вывода в БСД. Однако такой направленный цикл можно преобразовать во фрагмент знаний алгебраической байесовской сети, решив соответствующее матрично-векторное уравнение. Алгоритмы логико-вероятностного вывода для фрагмента знаний известны, что позволяет проверить согласованность (непротиворечивость) исходных данных и оценить вероятности альтернатив с учетом отношений, заданных циклом стохастических предпочтений.
Некоторые результаты, представленные в данной статье, получены в рамках проекта, поддержанного Российским фондом фундаментальных исследований (грант № 09-01-00861-а).
СПИСОК ЛИТЕРАТУРЫ
1. Саати Т. Принятие решений. Метод анализа иерархий. М.: Радио и связь, 1993. 316 с.
2. Абакаров А. Ш., Сушков Ю. А. Программная система поддержки принятия рациональных решений „MPRIORITY 1.0“ [Электронный ресурс]: Электронный науч. журн. „Исследовано в России“. 2005: . С. 2130—2146.
3. Хованов Н. В. Анализ и синтез показателей при информационном дефиците. СПб.: Изд-во С.-Петербург. гос. унта, 1996. 196 с.
4. Тулупьев А. Л., Николенко С. И., Сироткин А. В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
5. Тулупьев А. Л., Сироткин А. В., Николенко С. И. Синтез согласованных оценок истинности утверждений в интеллектуальных информационных системах // Изв. вузов. Приборостроение. 2006. Т. 49, № 7. С. 20—26.
6. Сироткин А. В., Тулупьев А. Л. Локальный априорный вывод в алгебраических байесовских сетях: комплекс основных алгоритмов // Тр. СПИИРАН. 2007. Вып. 5. С. 100—111.
7. Jensen F. V. Bayesian Networks and Decision Graphs. N.Y.: Springer-Verlag, 2001. 268 p.
8. Беллман Р. Введение в теорию матриц. М.: Наука, 1969. 368 с.
Александр Львович Тулупьев
Сведения об авторе — канд. физ.-мат. наук, доцент; Санкт-Петербургский институт инфор-
матики и автоматизации РАН, лаборатория прикладной информатики; E-mail: alt@iias.spb.su
Рекомендована кафедрой технологий программирования СПбГУ ИТМО
Поступила в редакцию 15.02.08 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 7
УДК 004.8
А. Л. ТУЛУПЬЕВ
СОГЛАСОВАННОСТЬ ДАННЫХ И ОЦЕНКА ВЕРОЯТНОСТИ АЛЬТЕРНАТИВ В ЦИКЛЕ СТОХАСТИЧЕСКИХ ПРЕДПОЧТЕНИЙ
Рассматривается подход к проверке согласованности данных и вычислению оценок вероятности альтернатив на основе преобразования цикла стохастических предпочтений во фрагмент знаний алгебраической байесовской сети и последующего логико-вероятностного вывода. Предлагаемый подход может быть использован при разработке систем поддержки принятия решений.
Ключевые слова: байесовские сети, стохастические предпочтения, принятие решений, вероятностная семантика, модели знаний с неопределенностью, логико-вероятностный вывод.
Введение. Одна из наиболее распространенных функций систем поддержки принятия решений (СППР) — представление и хранение структуры предпочтений, используемых лицом (или группой лиц, или экспертами), принимающим решения (ЛПР) [1]. Такие системы позволяют на основе имеющихся данных ранжировать возможные решения [2] или оценивать вероятность реализации двух или более альтернатив (посредством сравнения их значимости и возможности реализации) [3].
Лицо, принимающее решение, обладая достаточными познаниями в предметной области, как правило, не имеет специальной математической подготовки для того, чтобы учесть все особенности и ограничения различных формальных подходов, применяющихся в СППР. Кроме того, далеко не всегда элементы в том объеме знаний, которым располагает опрашиваемый специалист, идеально согласованы. Это приводит к тому, что полученные сведения о его системе предпочтений могут оказаться в какой-то части непригодными для представления или обработки с помощью СППР. Например, система предпочтений может быть противоречивой, при этом противоречия в различных подходах могут проявляться поразному. Один из основных их видов — цикл предпочтений, который в простейшем детерминированном случае выглядит как, например, следующая система утверждений: „A важнее, чем B“; „В важнее, чем C“; „C важнее, чем A“. В этом случае определить, что важнее, невозможно.
Читателю противоречивость приведенного фрагмента системы предпочтений очевидна, поскольку число противоречащих друг другу элементов невелико, они сведены вместе, изолированы от других сведений и, наконец, читатель понимает то, что написано. Программа же, используемая в СППР, может распознать противоречие только по формальным признакам.
Как правило, при появлении столь жестко детерминированных циклов в предпочтениях не остается ничего иного, как вернуться к опросу ЛПР и в диалоге с ним модифицировать систему предпочтений [2]. Однако высказывания о предметной области не всегда столь
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 7
4 А. Л. Тулупьев
однозначны. В них может присутствовать доля неопределенности, которую удается представить в виде оценки доверия к истинности высказывания [3—5]. Одним из примеров таких оценок является вероятность истинности высказывания, а цель настоящей статьи состоит в описании цикла стохастических (или вероятностных) предпочтений, его формализации, результатов его анализа и способа обработки. Такие циклы нередко возникают при обработке мнений большой группы экспертов, при ранжировании большого числа альтернатив, а также при голосовании в группе.
Измерения (и иные процедуры), направленные на выявление системы предпочтений, свойственны ряду предметных областей и наук. Например, в маркетинге „средством измерений“ является опросный лист клиента (покупателя), в психологии — тестовая методика, в социологии — анкета, в инженерии знаний — формализованное интервью эксперта или ЛПР, при голосовании — избирательный бюллетень. При этом возможность использования в большинстве областей электронных средств хранения данных обеспечивает доступность сведений о реализации предпочтений. В каждой из перечисленных областей используется соответствующий ей терминологический аппарат, сложились свои способы формализации и описания решения задач, связанных с исследованиями предпочтений, выработаны определенные методы измерений.
В настоящей статье в качестве иллюстрационной задачи предлагается использовать пример, связанный с оценкой (или прогнозом) результатов голосования, проведенного группой (комитетом) из трех человек. Такой пример позволит достаточно ясно и доступно отобразить все особенности проблемы принятия решения в условиях цикла стохастических предпочтений.
Исходная задача. Комитет состоит из трех равноправных членов. Каждый из них голосует „за“ или „против“ относительно проекта решения, вынесенного в повестку дня заседания. Среди членов комитета сложились достаточно устойчивые отношения: выбор, производимый первым членом комитета, зависит от выбора, производимого третьим, выбор второго — от выбора первого, а выбор третьего — от выбора второго. Предпочтения членов комитета отличаются достаточной степенью неопределенности и поэтому формально представляются условными вероятностями вида p(xi | x j ) , i, j = 1, 2, 3 [4—6].
Введем дополнительные обозначения. Пусть x1 соответствует утверждению «первый член комитета голосует „за“», x2 — утверждению «второй член комитета голосует „за“», x3 — утверждению «третий член комитета голосует „за“»; индекс j = i − 1 соответствует значению j, предшествующему значению i, а для i = 1 считается, что j = 3 . Символ x означает
отрицание высказывания x , а символ x называется литералом и может принимать значения
из множества {x, x} .
Таким образом, предпочтения голосующих могут быть формально представлены совокупностью значений шести условных вероятностей: p(x1 | x3 ) , p(x1 | x3 ) , p(x2 | x1) , p(x2 | x1) , p(x3 | x2 ) , p(x3 | x2 ) — иначе говоря, известна вероятность истинности высказываний вида «первый член комитета голосует „за“ при условии, что третий голосует „против“», «первый член комитета голосует „за“ при условии, что третий тоже голосует „за“» и т.д. Заметим, что исходя из теории вероятностей также известны величины p(xi | x j ) = 1 − p(xi | x j ) .
Для завершения спецификации исходной задачи предположим, что вследствие устойчивых отношений между голосующими они, скорее, склонны поддержать проект решения, нежели отвергнуть его. Оценки, описывающие такую ситуацию, приведены в таблице,
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 7
Согласованность данных и оценка вероятности альтернатив в цикле стохастических предпочтений 5
пример 1; предположение о том, что члены комитета придерживаются разных точек зрения, представлено примером 2.
Индекс оценки
i
1 2 3
Результат
Оценка вероятности
(пример 1)
условной
совместной
xi | x j xi | x j
xi
xi x j
0,96 0,75 0,957 0,946 0,97 0,8 0,963 0,928 0,99 0,88 0,986 0,953
p(x1x2 x3 ) p( x1 ∨ x2 ∨ x3 )
[0,918; 0,921] [0,079; 0,082]
Оценка вероятности
(пример 2)
условной
совместной
xi | x j xi | x j
xi
xi x j
0,4 0,05 0,119 0,079 0,5 0,75 0,720 0,060 0,1 0,45 0,198 0,072
p(x1x2 x3 ) p( x1 ∨ x2 ∨ x3 )
[0,020; 0,060] [0,940; 0,980]
Оценка вероятности (пример 3)
условной совместной
xi | x j
0,75 0,25 0,75
xi | x j
0,167 0,5
0,167
xi
0,400 0,400 0,400
xi x j
0,300 0,100 0,300
Исходные данные содержат противоречие [4]
Пусть требуется найти вероятности трех исходов:
— вероятность консенсусного голосования „за“;
— вероятность того, что хотя бы один член комитета проголосует против;
— вероятность того, что первый член комитета проголосует „за“.
Консенсусному голосованию „за“ соответствует логическая формула x1 ∧ x2 ∧ x3 (далее
будем писать x1x2 x3 , опуская знаки конъюнкции); второму исходу соответствует x1 ∨ x2 ∨ x3 ,
а третьему — x1. Обобщение и формализация [4, 6]. В обобщенной версии этой задачи исходные дан-
ные представляют собой направленный цикл (см. рисунок), который для краткости назовем
БСД-циклом (БСД — байесовские сети доверия). Каждому узлу цикла приписаны p(xi | x j ) — тензоры условных вероятностей,
x0=xn
характеризующие неопределенность и силу [4] связи между утверждениями xi и x j , i, j = 1, n. Речь идет о вероятностях приня-
x1
xn–1
тия литералом того или иного означивания в зависимости от означивания литерала в узле-родителе. Индекс j предшествует i.
x2
xn–2
Как правило, j = i − 1, но для i = 1 предшествующим индексом
будет j = n . Будем считать j = n и j = 0 одним и тем же значе-
нием индекса, что приводит, например, к совпадению x0 = xn . Определим величину ri = p(xi | x j ) − p(xi | x j ) .
xi–2
xi+2
На первый взгляд, получившаяся конструкция является ча-
стным случаем БСД, аппарат которых и базовые алгоритмы логико-вероятностного вывода известны и хорошо изучены [5, 7].
xi–1
xi+1
Для решения исходной задачи как раз и требуется по известным исходным оценкам истинности получить другие оценки, которые
xi
не заданы явно. Это и есть один из видов логико-вероятностного вывода.
Однако БСД — это не просто направленный граф с тензорами условных вероятностей в
узлах. БСД (как направленный граф) должна быть еще и ациклической — в ней не должно
быть направленных циклов. Имеющиеся исходные данные (см. рисунок) именно такой цикл и
образуют, что делает невозможным применение существующих БСД-исчислений [7].
Алгоритмы обработки. Возможность обработать БСД-цикл все же существует. Преоб-
разуем имеющуюся совокупность условных вероятностей в совокупность совместных веро-
ятностей [4, 6] и рассмотрим ее как оценки вероятностей элементов идеала конъюнктов —
фрагмент знаний алгебраической байесовской сети (АБС) [5]. Алгоритмы логико-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 7
6 А. Л. Тулупьев
вероятностного вывода для названного фрагмента знаний известны [5, 6], что позволяет най-
ти требующиеся оценки вероятностей.
По формуле полной вероятности можно рассчитать вероятность истинности p(xi ) ут-
верждения xi , если известна вероятность истинности p(x j ) утверждения x j из предыдущего
узла: p(xi ) = p(xi | x j ) p(x j ) + p(xi | x j ) p(x j ) . С учетом ri получим p(xi ) = ri p(x j ) + p(xi | x j ) .
Определив p(xi ) , можно аналогичным образом вычислить p(xi+1) , а затем p(xi+2 ) , p(xi+3 ) и т. д., пока цикл не замкнется на p(xi−1) . На основании p(xi−1) = p(x j ) и в соответствии с оп-
ределением условной вероятности рассчитываются вероятности конъюнкций утверждений
p(xi x j ) = p(xi | x j ) p(x j ) .
Таким образом, если известна маргинальная вероятность [4] хотя бы одного утвержде-
ния из узла цикла, то можно восстановить все остальные маргинальные вероятности вида
p(x j ) , p(xi x j ) , а следовательно, и p(xi x j ) .
Пусть p(x0 ) = ν . Тогда согласно приведенным формулам через неизвестное значение ν
можно выразить последовательно маргинальные вероятности утверждений p(xi ) = pi (ν) .
Неизвестное значение ν определяется из уравнения ν = pn (ν) , которое может иметь единственное решение или бесконечно много решений [4, 6] в зависимости от исходных данных.
Вычислив значение ν, можно, в свою очередь, вычислить значения маргинальных вероятно-
стей вида p(x j ) , p(x j xi ) и, вообще говоря, все вероятности p(xi x j ) .
Определим векторы
P0
=
⎛ ⎝⎜1
ν −
ν
⎞ ⎟ ⎠
=
⎛ ⎝⎜1
p(x0 ) − p(x0
)
⎞ ⎟ ⎠
и
Pi
=
⎛ ⎜⎝1
pi (ν) − pi (ν)
⎞ ⎟ ⎠
=
⎛ ⎜⎝1
p(xi ) − p(xi
)
⎞ ⎟ ⎠
,
а также матрицу
Wj
⎛ = ⎝⎜⎜
p(xi p(xi
| |
xj) xj)
p( xi p( xi
| |
xj xj
)⎞ ) ⎠⎟⎟
.
При этом уравнение ν = pn (ν) эквивалентно матрично-векторному уравнению
P0 = WP0 , где W = Wn × Wn−1 ×…× W1 × W0 , согласно которому вектор P0 есть собственный
вектор произведения матриц W. Вектору P0 должно соответствовать собственное число
λ = 1. Заметим, что матрицы Wi и, следовательно, их произведение W являются стохастиче-
скими, а P0 — вектор вероятностей (его компоненты неотрицательны и в сумме дают едини-
цу) [8]. Значения компонент вектора P0 можно определить по формулам Крамера или методом последовательных приближений [6].
Совокупность вычисленных вероятностей p(x j ) , p(xi x j ) , где 1 ≤ i ≤ n , можно внести в
качестве исходных данных во фрагмент знаний алгебраической байесовской сети. Такой
фрагмент обрабатывается с помощью известных алгоритмов поддержания непротиворечиво-
сти и априорного вывода [4—6]. Эти алгоритмы, в частности, позволяют получить оценки
искомых величин p(x1x2 x3 ) , p(x1 ∨ x2 ∨ x3 ) и p(x1) .
Результаты расчетов по предложенным выше формулам (в частности, оценка p(x1) ), а также результаты логико-вероятностного вывода во фрагменте знаний АБС — искомые
оценки альтернатив p(x1x2 x3 ) и p(x1 ∨ x2 ∨ x3 ) — представлены в таблице. Заметим, что в процессе вывода по исходным данным примера 3 была выявлена их противоречивость [4].
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 7
Согласованность данных и оценка вероятности альтернатив в цикле стохастических предпочтений 7
Выводы. Математической моделью цикла стохастических предпочтений является направленный цикл в байесовской сети доверия. Его невозможно обработать с помощью известных алгоритмов логико-вероятностного вывода в БСД. Однако такой направленный цикл можно преобразовать во фрагмент знаний алгебраической байесовской сети, решив соответствующее матрично-векторное уравнение. Алгоритмы логико-вероятностного вывода для фрагмента знаний известны, что позволяет проверить согласованность (непротиворечивость) исходных данных и оценить вероятности альтернатив с учетом отношений, заданных циклом стохастических предпочтений.
Некоторые результаты, представленные в данной статье, получены в рамках проекта, поддержанного Российским фондом фундаментальных исследований (грант № 09-01-00861-а).
СПИСОК ЛИТЕРАТУРЫ
1. Саати Т. Принятие решений. Метод анализа иерархий. М.: Радио и связь, 1993. 316 с.
2. Абакаров А. Ш., Сушков Ю. А. Программная система поддержки принятия рациональных решений „MPRIORITY 1.0“ [Электронный ресурс]: Электронный науч. журн. „Исследовано в России“. 2005: . С. 2130—2146.
3. Хованов Н. В. Анализ и синтез показателей при информационном дефиците. СПб.: Изд-во С.-Петербург. гос. унта, 1996. 196 с.
4. Тулупьев А. Л., Николенко С. И., Сироткин А. В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
5. Тулупьев А. Л., Сироткин А. В., Николенко С. И. Синтез согласованных оценок истинности утверждений в интеллектуальных информационных системах // Изв. вузов. Приборостроение. 2006. Т. 49, № 7. С. 20—26.
6. Сироткин А. В., Тулупьев А. Л. Локальный априорный вывод в алгебраических байесовских сетях: комплекс основных алгоритмов // Тр. СПИИРАН. 2007. Вып. 5. С. 100—111.
7. Jensen F. V. Bayesian Networks and Decision Graphs. N.Y.: Springer-Verlag, 2001. 268 p.
8. Беллман Р. Введение в теорию матриц. М.: Наука, 1969. 368 с.
Александр Львович Тулупьев
Сведения об авторе — канд. физ.-мат. наук, доцент; Санкт-Петербургский институт инфор-
матики и автоматизации РАН, лаборатория прикладной информатики; E-mail: alt@iias.spb.su
Рекомендована кафедрой технологий программирования СПбГУ ИТМО
Поступила в редакцию 15.02.08 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 7