Вычислительная сложность алгоритмов локального апостериорного вывода в алгебраических байесовских сетях
Ключевые слова:
алгебраическая байесовская сеть, апостериорный вывод, фрагмент знанийАннотация
В статье рассматривается локальный апостериорный вывод в алгебраических байесовских сетях. Для трёх видов свидетельств (детерминированного, стохастического и неточного) описывается способ проведения вывода и доказываются оценки сложности предлагаемых вычислений. В случае, когда вывод сводится к решению задач линейного программирования, оценка сложности даётся в виде числа таких задач, а также оценки числа переменных и ограничений в них. В остальных случаях сложность описывается в числе арифметических операций.Литература
Гавурин М.К., Малоземов В.Н. Экстремальные задачи с линейными ограничениями: учебное пособие. Л.: ЛГУ, 1984. 175 с.
Городецкий В.И., Тулупьев А.Л. Формирование непротиворечивых баз знаний с неопределенностью // Изв. РАН. Сер. Теория и системы управления. 1997. Т. 5. С. 33–42.
Сироткин А.В., Тулупьев А.Л. Матричные уравнения локального логико-вероятностного вывода в алгебраических байесовских сетях // Труды СПИИРАН. 2008. Вып. 6. СПб.: Наука, 2008. С. 134–143.
Сироткин А.В., Тулупьев А.Л. Моделирование знаний и рассуждений в условиях неопределенности: матрично-векторная формализация локального синтеза согласованных оценок истинности. // Труды СПИИРАН. 2011. Вып. 3(18). [В настоящем выпуске].
Тулупьев А.Л. Алгебраические байесовские сети: теоретические основы и непротиворечивость. СПб.: СПИИРАН, 1995. 76 с.
Тулупьев А.Л. Алгебраические байесовские сети: логико-вероятностный подход к моделированию баз знаний с неопределенностью. СПб.: СПИИРАН, 2000. 282 с.
Тулупьев А.Л. Метод построения и исследования баз фрагментов знаний с неопределенностью // Труды СПИИРАН. Вып. 1. 2002. Т. 1. С. 258–271.
Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. пособие. Элементы мягких вычислений. СПб.: СПбГУ; ООО Издательство .Анатолия., 2007. 40 с.
Тулупьев А.Л. Алгебраические байесовские сети: локальный логико-вероятностный вывод: Учеб. пособие. Элементы мягких вычислений. СПб.: СПбГУ; ООО Издательство .Анатолия., 2007. 80 с.
Тулупьев А.Л. Байесовские сети: логико-вероятностный вывод в циклах. СПб.: Изд-во С.-Петербургского ун-та, 2008. 140 с. (Элементы мягких вычислений.)
Тулупьев А.Л. Алгебраические байесовские сети: система операций локального логико-вероятностного вывода // Информационно-измерительные и управляющие системы. 2009. № 4. С. 41–44.
Тулупьев А.Л. Непротиворечивость оценок вероятностей в идеалах конъюнктов и дизъюнктов. // Вестник СПбГУ. Сер. 10. 2009. Вып. 2.С. 121–131.
Тулупьев А.Л. Апостериорные оценки вероятностей в идеале конъюнктов // Вестник СПбГУ. 2010. Серия 10. Вып. 1. С. 95–104.
Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 608 с.
Тулупьев А.Л., Сироткин А.В. Алгебраические байесовские сети: принцип декомпозиции и логико-вероятностный вывод в условиях неопределенности // Информационно-измерительные и управляющие системы. 2008. №10, т. 6. С. 85–87.
Тулупьев А.Л., Сироткин А.В. Локальный апостериорный вывод в алгебраических байесовских сетях как система матрично-векторных операций // Интегрированные модели и мягкие вычисления в искусственном интеллекте. V-я Международная научно-практическая конференция. Сборник научных трудов. В 2-х т. Т. 1. СПб.: Наука, 2009. С. 425–434.
Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петербургского ун-та, 2009. 400 с.
Городецкий В.И., Тулупьев А.Л. Формирование непротиворечивых баз знаний с неопределенностью // Изв. РАН. Сер. Теория и системы управления. 1997. Т. 5. С. 33–42.
Сироткин А.В., Тулупьев А.Л. Матричные уравнения локального логико-вероятностного вывода в алгебраических байесовских сетях // Труды СПИИРАН. 2008. Вып. 6. СПб.: Наука, 2008. С. 134–143.
Сироткин А.В., Тулупьев А.Л. Моделирование знаний и рассуждений в условиях неопределенности: матрично-векторная формализация локального синтеза согласованных оценок истинности. // Труды СПИИРАН. 2011. Вып. 3(18). [В настоящем выпуске].
Тулупьев А.Л. Алгебраические байесовские сети: теоретические основы и непротиворечивость. СПб.: СПИИРАН, 1995. 76 с.
Тулупьев А.Л. Алгебраические байесовские сети: логико-вероятностный подход к моделированию баз знаний с неопределенностью. СПб.: СПИИРАН, 2000. 282 с.
Тулупьев А.Л. Метод построения и исследования баз фрагментов знаний с неопределенностью // Труды СПИИРАН. Вып. 1. 2002. Т. 1. С. 258–271.
Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. пособие. Элементы мягких вычислений. СПб.: СПбГУ; ООО Издательство .Анатолия., 2007. 40 с.
Тулупьев А.Л. Алгебраические байесовские сети: локальный логико-вероятностный вывод: Учеб. пособие. Элементы мягких вычислений. СПб.: СПбГУ; ООО Издательство .Анатолия., 2007. 80 с.
Тулупьев А.Л. Байесовские сети: логико-вероятностный вывод в циклах. СПб.: Изд-во С.-Петербургского ун-та, 2008. 140 с. (Элементы мягких вычислений.)
Тулупьев А.Л. Алгебраические байесовские сети: система операций локального логико-вероятностного вывода // Информационно-измерительные и управляющие системы. 2009. № 4. С. 41–44.
Тулупьев А.Л. Непротиворечивость оценок вероятностей в идеалах конъюнктов и дизъюнктов. // Вестник СПбГУ. Сер. 10. 2009. Вып. 2.С. 121–131.
Тулупьев А.Л. Апостериорные оценки вероятностей в идеале конъюнктов // Вестник СПбГУ. 2010. Серия 10. Вып. 1. С. 95–104.
Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 608 с.
Тулупьев А.Л., Сироткин А.В. Алгебраические байесовские сети: принцип декомпозиции и логико-вероятностный вывод в условиях неопределенности // Информационно-измерительные и управляющие системы. 2008. №10, т. 6. С. 85–87.
Тулупьев А.Л., Сироткин А.В. Локальный апостериорный вывод в алгебраических байесовских сетях как система матрично-векторных операций // Интегрированные модели и мягкие вычисления в искусственном интеллекте. V-я Международная научно-практическая конференция. Сборник научных трудов. В 2-х т. Т. 1. СПб.: Наука, 2009. С. 425–434.
Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петербургского ун-та, 2009. 400 с.
Computational complexity of local posteriori inference algorithms in algebraic Bayesian networks.
Abstract
The paper presents algorithmical complexity estimates for local posteriori inference in algebraic Bayesian networks. We consider the ways of implementing the inference for three types of evidence (deterministic, stochastic, and imprecise). If we need to solve linear programming tasks for inference, the comlexity estimations are given in numbers of such tasks and numbers of variables and constraints in each task. In other cases, complexity estimates are given in numbers of arithmetic operations.Опубликован
2011-09-01
Как цитировать
Сироткин, А. В. (2011). Вычислительная сложность алгоритмов локального апостериорного вывода в алгебраических байесовских сетях. Труды СПИИРАН, 3(18), 188-214. https://doi.org/10.15622/sp.18.8
Раздел
Статьи
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
