Вычислительная сложность алгоритмов локального апостериорного вывода в алгебраических байесовских сетях
Ключевые слова:
алгебраическая байесовская сеть, апостериорный вывод, фрагмент знанийАннотация
В статье рассматривается локальный апостериорный вывод в алгебраических байесовских сетях. Для трёх видов свидетельств (детерминированного, стохастического и неточного) описывается способ проведения вывода и доказываются оценки сложности предлагаемых вычислений. В случае, когда вывод сводится к решению задач линейного программирования, оценка сложности даётся в виде числа таких задач, а также оценки числа переменных и ограничений в них. В остальных случаях сложность описывается в числе арифметических операций.Литература
Гавурин М.К., Малоземов В.Н. Экстремальные задачи с линейными ограничениями: учебное пособие. Л.: ЛГУ, 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 с.
Опубликован
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).
