Преобразование первичной структуры алгебраической байесовской сети к ациклической с сохранением вероятностной семантики
Ключевые слова:
алгебраическая байесовская сеть, первичная структура, графовая декомпозиция, вероятностная семантикаАннотация
В работе рассмотрена проблема преобразования первичной структуры алгебраической байесовской сети с интервальными оценками вероятности к первичной структуре такой сети, стохастически эквивалентной исходной в задаче преобразования первичной структуры такой сети к ацикличной. Показано, что такое преобразование допустимо лишь в том случае, когда гиперграф, соответствующий результирующий первичной структуре, пореберно содержит гиперграф, соответствующий исходной первичной структуре. Предложен способ построения вероятностных оценок результирующей первичной структуры, делающий ее стохастически эквивалентной исходной.Литература
Dechter R. Constraint processing. San Francisco: Morgan Kaufmann, 2003. 481 p.
Dechter R., Pearl J. Tree clustering for constraint networks // Artificial Intelligence. 1989. Vol. 38(3). P. 353–366
Fagin R. Degrees of acyclicity for hypergraphs and relational database schemes // Journal of the ACM (JACM). 1983. Vol. 30, no. 3. P. 514–550
Golumbic M.C. Algorithmic Graph Theory and Perfect Graphs. NY: Academic Press. 1980. 286 p.
Maier D. Theory of Relational Databases. Rockville, MD: Computer Science Press, 1983. 637 p.
Pearl J. Probabilistic Reasoning in Intelligent Systems. NY: Morgan Kaufmann, 1988. 552 p.
Быкова В.В. Рекуррентные методы вычисления древовидной ширины гиперграфа // Известия ТПУ. 2011. Вып. 5. С. 5–10
Вяткин А.В., Фильченков А.А., Тулупьев А.Л., Мусина В.Ф., Фроленков К.В. Подходы к устранению цикличности первичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2013. Вып. 3(26). С. 216--233
Зыков А.А. Основы теории графов. М.: Наука. 1987. 384 с.
Тулупьев А.Л. Алгебраические байесовские сети. Логико-вероятностный подход к моделированию баз знаний с неопределенностью, СПИИРАН, СПб, 2000, 292 с.
Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. пособие, Элементы мягких вычислений, СПбГУ, СПб; ООО Издательство «Анатолия», 2007, 40 с.
Тулупьев А.Л. Алгебраические байесовские сети: локальный логико-вероятностный вывод: Учеб. пособие, Элементы мягких вычислений, СПбГУ, СПб; ООО Издательство «Анатолия», 2007, 80 с.
Тулупьев А.Л. Алгебраические байесовские сети: теоретические основы и непротиворечивость, СПИИРАН, СПб, 1995, 76 с.
Тулупьев А.Л. Байесовские сети: логико-вероятностный вывод в циклах, Элементы мягких вычислений, Изд-во С.-Петербургского ун-та, СПб, 2008, 140 с.
Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. ун-та, 2009, 400 с.
Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локальной и глобальной структуры алгебраической байесовской сети в Java-приложениях. // Труды СПИИРАН. СПб: Наука, 2007. Вып. 5. С. 71–99
Тулупьев А.Л., Фильченков А.А., Вальтман Н.А. Алгебраические байесовские сети: задачи автоматического обучения. // Информационно-измерительные и управляющие системы. 2011. Вып. 11. С. 57–61
Фильченков А.А. Меры истинности и вероятностные графические модели для представления знаний с неопределенностью // Труды СПИИРАН. 2012. Вып. 4(23). С. 254–295
Фильченков А.А. Протоструктура алгебраической байесовской сети в контексте логико-вероятностного вывода: поддержание связности и ацикличности // Научная сессия НИЯУ МИФИ-2013. (1–6 февраля 2013 г., Москва). Аннотации докладов. В 3 т. Т.2 Проблемы фундаментальной науки. Стратегические информационные технологии. М.: НИЯУ МИФИ, 2013. С. 327
Фильченков А.А., Тулупьев А.Л. Связность и ацикличность первичной структуры алгебраической байесовской сети // Вестник Санкт-Петербургского государственного университета. Серия 1. Математика. Механика. Астрономия. 2013. Вып. 1. C. 110–119
Фильченков А.А., Тулупьев А.Л. Совпадение множеств минимальных и нередуцируемых графов смежности над первичной структурой алгебраической байесовской сети // Вестник Санкт-Петербургского государственного университета. Серия 1. Математика. Механика. Астрономия. 2012. Вып. 2. С. 69–78
Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности. // Труды СПИИРАН. СПб: Наука, 2009. Вып. 11. С. 104–127
Фильченков А.А., Фроленков К.В., Сироткин А.В., Тулупьев А.Л. Система алгоритмов синтеза подмножеств минимальных графов смежности // Труды СПИИРАН. 2013. Вып. 4(27). С. 200–244
Dechter R., Pearl J. Tree clustering for constraint networks // Artificial Intelligence. 1989. Vol. 38(3). P. 353–366
Fagin R. Degrees of acyclicity for hypergraphs and relational database schemes // Journal of the ACM (JACM). 1983. Vol. 30, no. 3. P. 514–550
Golumbic M.C. Algorithmic Graph Theory and Perfect Graphs. NY: Academic Press. 1980. 286 p.
Maier D. Theory of Relational Databases. Rockville, MD: Computer Science Press, 1983. 637 p.
Pearl J. Probabilistic Reasoning in Intelligent Systems. NY: Morgan Kaufmann, 1988. 552 p.
Быкова В.В. Рекуррентные методы вычисления древовидной ширины гиперграфа // Известия ТПУ. 2011. Вып. 5. С. 5–10
Вяткин А.В., Фильченков А.А., Тулупьев А.Л., Мусина В.Ф., Фроленков К.В. Подходы к устранению цикличности первичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2013. Вып. 3(26). С. 216--233
Зыков А.А. Основы теории графов. М.: Наука. 1987. 384 с.
Тулупьев А.Л. Алгебраические байесовские сети. Логико-вероятностный подход к моделированию баз знаний с неопределенностью, СПИИРАН, СПб, 2000, 292 с.
Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. пособие, Элементы мягких вычислений, СПбГУ, СПб; ООО Издательство «Анатолия», 2007, 40 с.
Тулупьев А.Л. Алгебраические байесовские сети: локальный логико-вероятностный вывод: Учеб. пособие, Элементы мягких вычислений, СПбГУ, СПб; ООО Издательство «Анатолия», 2007, 80 с.
Тулупьев А.Л. Алгебраические байесовские сети: теоретические основы и непротиворечивость, СПИИРАН, СПб, 1995, 76 с.
Тулупьев А.Л. Байесовские сети: логико-вероятностный вывод в циклах, Элементы мягких вычислений, Изд-во С.-Петербургского ун-та, СПб, 2008, 140 с.
Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. ун-та, 2009, 400 с.
Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локальной и глобальной структуры алгебраической байесовской сети в Java-приложениях. // Труды СПИИРАН. СПб: Наука, 2007. Вып. 5. С. 71–99
Тулупьев А.Л., Фильченков А.А., Вальтман Н.А. Алгебраические байесовские сети: задачи автоматического обучения. // Информационно-измерительные и управляющие системы. 2011. Вып. 11. С. 57–61
Фильченков А.А. Меры истинности и вероятностные графические модели для представления знаний с неопределенностью // Труды СПИИРАН. 2012. Вып. 4(23). С. 254–295
Фильченков А.А. Протоструктура алгебраической байесовской сети в контексте логико-вероятностного вывода: поддержание связности и ацикличности // Научная сессия НИЯУ МИФИ-2013. (1–6 февраля 2013 г., Москва). Аннотации докладов. В 3 т. Т.2 Проблемы фундаментальной науки. Стратегические информационные технологии. М.: НИЯУ МИФИ, 2013. С. 327
Фильченков А.А., Тулупьев А.Л. Связность и ацикличность первичной структуры алгебраической байесовской сети // Вестник Санкт-Петербургского государственного университета. Серия 1. Математика. Механика. Астрономия. 2013. Вып. 1. C. 110–119
Фильченков А.А., Тулупьев А.Л. Совпадение множеств минимальных и нередуцируемых графов смежности над первичной структурой алгебраической байесовской сети // Вестник Санкт-Петербургского государственного университета. Серия 1. Математика. Механика. Астрономия. 2012. Вып. 2. С. 69–78
Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности. // Труды СПИИРАН. СПб: Наука, 2009. Вып. 11. С. 104–127
Фильченков А.А., Фроленков К.В., Сироткин А.В., Тулупьев А.Л. Система алгоритмов синтеза подмножеств минимальных графов смежности // Труды СПИИРАН. 2013. Вып. 4(27). С. 200–244
Опубликован
2013-12-01
Как цитировать
Фильченков, А. А. (2013). Преобразование первичной структуры алгебраической байесовской сети к ациклической с сохранением вероятностной семантики. Труды СПИИРАН, 7(30), 156-168. https://doi.org/10.15622/sp.30.10
Раздел
Статьи
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
