Декодирование последовательности состояний бинарной скрытой марковской модели, представленной в виде алгебраической байесовской сети, по последовательности наблюдений
Ключевые слова:
вероятностные графические модели, скрытые марковские модели, алгебраические байесовские сети,Аннотация
Скрытые марковские модели, байесовские сети и другие вероятностные графические модели зарекомендовали себя как одно из наиболее эффективных средств представления знаний с неопределенностью с активно развивающимся теоретическим и алгоритмическим аппаратом средств машинного обучения и нашли множество приложений в распознавании речи, обработке сигналов, биоинформатике, математической лингвистике, компьютерной криминалистике и пр. В статье предложен алгоритм декодирования последовательности скрытых состояний для бинарных линейных по структуре скрытых марковских моделей, представленных в виде алгебраических байесовских сетей, и доказана его корректность. Приведённый метод дополняет набор средств работы с такими моделями.Литература
Cowell R.G., Dawid A.P., Lauritzen S.L., Spiegelhalter D.J. Probabilistic Networks and Expert Systems. NY.: Springer-Verlag, 1997. 370 p.
Nilsson N.J. Probabilistic Logic // Artificial Intelligence. 1986. Vol. 28. P. 71–87
Rabiner L. A A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition // IEEE Proceedings. 1989. Vol. 77. No. 2. Pp. 257–286
Stengel M. Introduction to Graphical Models, Hidden Markov Models and Bayesian Networks. Department of Information and Computer Sciences Toyohashi University of Technology Toyohashi, 441-8580. Japan. 2003. 46 p.
Viterbi A. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm // IEEE Transactions on Information Theory. 1967. Vol.13. No.2. Pp. 260–269
Welch L.R. Hidden Markov Models and the Baum-Welch Algorithm // IEEE Information Theory Society Newsletter. 2003. Vol. 53. No 4. Рp. 10–13
Момзикова М.П., Великодная О.И., Пинский М.Я., Сироткин А.В., Тулупьев А.Л., Фильченков А.А. Оценка вероятности наблюдаемой последовательности в бинарных линейных по структуре скрытых марковских моделях с помощью апостериорного вывода в алгебраических байесовских сетях // Труды СПИИРАН. СПб: Наука, 2010. Вып. 2. C. 122–142
Момзикова М.П., Великодная О.И., Пинский М.Я., Сироткин А.В., Тулупьев А.Л., Фильченков А.А. Представление бинарных линейных по структуре скрытых марковских моделей в виде алгебраических байесовских сетей // Труды СПИИРАН. СПб: Наука, 2010. Вып. 1. C. 134–150
Опарин В.В., Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Матроидное представление семейства графов смежности над набором фрагментов знаний // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2010. Вып 4. С. 73–76
Ревзин Л.М. Комплекс программ для представления и обработки ациклических скрытых марковских моделей на основе алгебраических байесовских сетей: Дипломная работа. Математико-механический факультет СПбГУ. 2012. 39 с. (Санкт-Петербургский государственный университет)
Ревзин Л.М., Фильченков А.А., Тулупьев А.Л. Представление многозначных линейных по структуре скрытых марковских моделей в виде алгебраических байесовских сетей // Труды СПИИРАН. СПб: Наука, 2012. Вып. 20. С. 186–199
Ромашова М.Н., Тулупьев А.Л. Эмпирическая оценка устойчивости априорного вывода в вероятностной модели фрагмента знаний с неопределенностью // VII Санкт-Петербургская международная конференция «Региональная информатика-2000 (РИ-2000)»: Тезисы докладов. Секция «Теоретические проблемы информатизации», подсекция «Теоретические основы информационных технологий» (Санкт-Петербург, 5–8 декабря 2000 г.), СПб, 2000. C. 7
Сироткин А.В. Проверка и поддержание непротиворечивости алгебраических байесовских сетей: вычислительная сложность алгоритмов. // Труды СПИИРАН. СПб: Наука, 2010. Вып. 15. С. 162–192
Тулупьев А.Л. Алгебраические байесовские сети. Логико-вероятностный подход к моделированию баз знаний с неопределенностью, СПИИРАН, СПб, 2000, 292 с.
Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. пособие. СПбГУ, СПб; ООО Издательство «Анатолия», 2007. 40 с.
Тулупьев А.Л. Алгебраические байесовские сети: логико-вероятностная модель баз фрагментов знаний с неопределенностью. Всероссийская научная конференция по нечетким системам и мягким вычислениям НСМВ-2006. Труды (Тверь, 20–22 сентября 2006 г.), Тверь, 2006. C. 31–47
Тулупьев А.Л. Алгебраические байесовские сети: логико-вероятностные графические модели баз фрагментов знаний с неопределенностью: Диссертация на соискание ученой степени д-ра физ.-мат. наук. СПб., 2009. 670 с. (Санкт-Петербургский государственный университет)
Тулупьев А.Л. Алгебраические байесовские сети: локальный логико-вероятностный вывод: Учеб. пособие. СПбГУ, СПб; ООО Изда-тельство «Анатолия», 2007. 80 с.
Тулупьев А.Л. Алгебраические байесовские сети: теоретические основы и непротиворечивость, СПИИРАН, СПб, 1995, 76 с.
Тулупьев А.Л. Апостериорные оценки вероятностей в идеале конъюнктов. // Вестник СПбГУ. Серия 10. 2010. Вып. 1. С. 95–104
Тулупьев А.Л. Ациклические алгебраические байесовские сети: логико-вероятностный вывод. // Нечеткие системы и мягкие вычисления: Научный журнал Российской ассоциации нечетких систем и мягких вычислений. 2006. Вып. 1:1. C. 57–93
Тулупьев А.Л. Байесовские сети: логико-вероятностный вывод в циклах. СПб.: Изд-во С.-Петербургского ун-та, 2008. 140 с.
Тулупьев А.Л. Непротиворечивость оценок вероятностей в алгебраических байесовских сетях. // Вестник СПбГУ. Сер. 10. 2009. Вып. 3. С. 144–151
Тулупьев А.Л. Непротиворечивость оценок вероятностей в идеалах конъюнктов и дизъюнктов // Вестник СПбГУ. Сер. 10. 2009. Вып. 2. С. 121–131
Тулупьев А.Л. Поддержание непротиворечивости фрагмента знаний с интервальной нечеткой мерой оценки неопределенности // Теоретические основы и прикладные задачи интеллектуальных информационных технологий: Сб. трудов СПИИРАН, СПб.: СПИИРАН, 1998. C. 82–92
Тулупьев А.Л. Преобразование ациклических байесовских сетей доверия в алгебраические байесовские сети // Известия высших учебных заведений: Приборостроение. 2009. Вып. 3. С. 21–23
Тулупьев А.Л., Никитин Д.А., Ромашова М.Н., Лакомов Д.П., Тишков А.В. Априорный и апостериорный вывод на элементе структурированной сети фрагментов знаний, геометрическое представление фрагментов знаний // VII Санкт-Петербургская международная конференция «Региональная информатика-2000 (РИ-2000)» : Труды конференции (Санкт-Петербург, 5-8 декабря 2000 г.), СПб, 2001. С. 112–116
Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. ун-та, 2009, 400 с.
Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локальной и глобальной структуры алгебраической байесовской сети в Java-приложениях // Труды СПИИРАН. СПб: Наука, 2007. Вып. 5. С. 71–99
Тулупьев А.Л., Фильченков А.А., Вальтман Н.А. Алгебраические байесовские сети: задачи автоматического обучения // Информационно-измерительные и управляющие системы. 2011. Вып. 11. С. 57–61
Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности // Труды СПИИРАН. СПб: Наука, 2009. Вып. 11. С. 104–127
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Особенности анализа вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. СПб: Наука, 2010. Вып. 12. С. 97–118
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Ребра графов смежности в контексте компаративного анализа клик минимальных графов смежности алгебраических байесовских сетей. // Труды СПИИРАН. СПб: Наука, 2010, Вып. 3 (14). С. 132–149
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Структурный анализ клик максимальных графов смежности алгебраических байесовских сетей // Вестн. Тверск. гос. ун-та. Сер.: Прикладная математика. 2011. Вып. 20. С. 139–151
Nilsson N.J. Probabilistic Logic // Artificial Intelligence. 1986. Vol. 28. P. 71–87
Rabiner L. A A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition // IEEE Proceedings. 1989. Vol. 77. No. 2. Pp. 257–286
Stengel M. Introduction to Graphical Models, Hidden Markov Models and Bayesian Networks. Department of Information and Computer Sciences Toyohashi University of Technology Toyohashi, 441-8580. Japan. 2003. 46 p.
Viterbi A. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm // IEEE Transactions on Information Theory. 1967. Vol.13. No.2. Pp. 260–269
Welch L.R. Hidden Markov Models and the Baum-Welch Algorithm // IEEE Information Theory Society Newsletter. 2003. Vol. 53. No 4. Рp. 10–13
Момзикова М.П., Великодная О.И., Пинский М.Я., Сироткин А.В., Тулупьев А.Л., Фильченков А.А. Оценка вероятности наблюдаемой последовательности в бинарных линейных по структуре скрытых марковских моделях с помощью апостериорного вывода в алгебраических байесовских сетях // Труды СПИИРАН. СПб: Наука, 2010. Вып. 2. C. 122–142
Момзикова М.П., Великодная О.И., Пинский М.Я., Сироткин А.В., Тулупьев А.Л., Фильченков А.А. Представление бинарных линейных по структуре скрытых марковских моделей в виде алгебраических байесовских сетей // Труды СПИИРАН. СПб: Наука, 2010. Вып. 1. C. 134–150
Опарин В.В., Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Матроидное представление семейства графов смежности над набором фрагментов знаний // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2010. Вып 4. С. 73–76
Ревзин Л.М. Комплекс программ для представления и обработки ациклических скрытых марковских моделей на основе алгебраических байесовских сетей: Дипломная работа. Математико-механический факультет СПбГУ. 2012. 39 с. (Санкт-Петербургский государственный университет)
Ревзин Л.М., Фильченков А.А., Тулупьев А.Л. Представление многозначных линейных по структуре скрытых марковских моделей в виде алгебраических байесовских сетей // Труды СПИИРАН. СПб: Наука, 2012. Вып. 20. С. 186–199
Ромашова М.Н., Тулупьев А.Л. Эмпирическая оценка устойчивости априорного вывода в вероятностной модели фрагмента знаний с неопределенностью // VII Санкт-Петербургская международная конференция «Региональная информатика-2000 (РИ-2000)»: Тезисы докладов. Секция «Теоретические проблемы информатизации», подсекция «Теоретические основы информационных технологий» (Санкт-Петербург, 5–8 декабря 2000 г.), СПб, 2000. C. 7
Сироткин А.В. Проверка и поддержание непротиворечивости алгебраических байесовских сетей: вычислительная сложность алгоритмов. // Труды СПИИРАН. СПб: Наука, 2010. Вып. 15. С. 162–192
Тулупьев А.Л. Алгебраические байесовские сети. Логико-вероятностный подход к моделированию баз знаний с неопределенностью, СПИИРАН, СПб, 2000, 292 с.
Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. пособие. СПбГУ, СПб; ООО Издательство «Анатолия», 2007. 40 с.
Тулупьев А.Л. Алгебраические байесовские сети: логико-вероятностная модель баз фрагментов знаний с неопределенностью. Всероссийская научная конференция по нечетким системам и мягким вычислениям НСМВ-2006. Труды (Тверь, 20–22 сентября 2006 г.), Тверь, 2006. C. 31–47
Тулупьев А.Л. Алгебраические байесовские сети: логико-вероятностные графические модели баз фрагментов знаний с неопределенностью: Диссертация на соискание ученой степени д-ра физ.-мат. наук. СПб., 2009. 670 с. (Санкт-Петербургский государственный университет)
Тулупьев А.Л. Алгебраические байесовские сети: локальный логико-вероятностный вывод: Учеб. пособие. СПбГУ, СПб; ООО Изда-тельство «Анатолия», 2007. 80 с.
Тулупьев А.Л. Алгебраические байесовские сети: теоретические основы и непротиворечивость, СПИИРАН, СПб, 1995, 76 с.
Тулупьев А.Л. Апостериорные оценки вероятностей в идеале конъюнктов. // Вестник СПбГУ. Серия 10. 2010. Вып. 1. С. 95–104
Тулупьев А.Л. Ациклические алгебраические байесовские сети: логико-вероятностный вывод. // Нечеткие системы и мягкие вычисления: Научный журнал Российской ассоциации нечетких систем и мягких вычислений. 2006. Вып. 1:1. C. 57–93
Тулупьев А.Л. Байесовские сети: логико-вероятностный вывод в циклах. СПб.: Изд-во С.-Петербургского ун-та, 2008. 140 с.
Тулупьев А.Л. Непротиворечивость оценок вероятностей в алгебраических байесовских сетях. // Вестник СПбГУ. Сер. 10. 2009. Вып. 3. С. 144–151
Тулупьев А.Л. Непротиворечивость оценок вероятностей в идеалах конъюнктов и дизъюнктов // Вестник СПбГУ. Сер. 10. 2009. Вып. 2. С. 121–131
Тулупьев А.Л. Поддержание непротиворечивости фрагмента знаний с интервальной нечеткой мерой оценки неопределенности // Теоретические основы и прикладные задачи интеллектуальных информационных технологий: Сб. трудов СПИИРАН, СПб.: СПИИРАН, 1998. C. 82–92
Тулупьев А.Л. Преобразование ациклических байесовских сетей доверия в алгебраические байесовские сети // Известия высших учебных заведений: Приборостроение. 2009. Вып. 3. С. 21–23
Тулупьев А.Л., Никитин Д.А., Ромашова М.Н., Лакомов Д.П., Тишков А.В. Априорный и апостериорный вывод на элементе структурированной сети фрагментов знаний, геометрическое представление фрагментов знаний // VII Санкт-Петербургская международная конференция «Региональная информатика-2000 (РИ-2000)» : Труды конференции (Санкт-Петербург, 5-8 декабря 2000 г.), СПб, 2001. С. 112–116
Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. ун-та, 2009, 400 с.
Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локальной и глобальной структуры алгебраической байесовской сети в Java-приложениях // Труды СПИИРАН. СПб: Наука, 2007. Вып. 5. С. 71–99
Тулупьев А.Л., Фильченков А.А., Вальтман Н.А. Алгебраические байесовские сети: задачи автоматического обучения // Информационно-измерительные и управляющие системы. 2011. Вып. 11. С. 57–61
Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности // Труды СПИИРАН. СПб: Наука, 2009. Вып. 11. С. 104–127
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Особенности анализа вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. СПб: Наука, 2010. Вып. 12. С. 97–118
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Ребра графов смежности в контексте компаративного анализа клик минимальных графов смежности алгебраических байесовских сетей. // Труды СПИИРАН. СПб: Наука, 2010, Вып. 3 (14). С. 132–149
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Структурный анализ клик максимальных графов смежности алгебраических байесовских сетей // Вестн. Тверск. гос. ун-та. Сер.: Прикладная математика. 2011. Вып. 20. С. 139–151
Опубликован
2013-02-01
Как цитировать
Тулупьев, А. Л., Фильченков, А. А., & Алексеев, А. М. (2013). Декодирование последовательности состояний бинарной скрытой марковской модели, представленной в виде алгебраической байесовской сети, по последовательности наблюдений. Труды СПИИРАН, 1(24), 165-177. https://doi.org/10.15622/sp.24.11
Раздел
Статьи
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
