Представление многозначных линейных по структуре скрытых марковских моделей в виде алгебраических байесовских сетей
Ключевые слова:
скрытые марковские модели, алгебраические байесовские сети, линейные по структуре скрытые марковские модели, вероятностные графические моделиАннотация
Для моделирования различных процессов в таких областях как биоинформатика, распознавание речи, машинный перевод активно используются скрытые марковские модели (СММ). Алгебраические байесовские сети (АБС) являются активно развивающимся аппаратом с широкими возможностями. Цель данной работы — представление более широкого класса скрытых марковских моделей с помощью алгебраических байесовских сетей, чем в более ранних исследованиях. Предложено представление линейной по структуре СММ при помощи АБС и показана его корректность с точки зрения эквивалентности вероятностных семантик.Литература
Bunke H., Caelli T. Hidden Markov Models Applications in Computer Vision. Series in Machine Perception and Artificial Intelligence. – World Scientific, 2001. – V. 45. 244 p.
Cowell R.G., Dawid A.P., Lauritzen S.L., Spiegelhalter D.J. Probabilistic Networks and Expert Systems. NY.: Springer-Verlag, 1997. 370 p.
da-Silva C.Q. Hidden Markov models applied to a subsequence of the Xylella fastidiosa genome. Genet. Mol. Biol. São Paulo, Dec. 2003. V. 26. № 4. Р. 529–535
Gorodetsky V.I., Drozdgin V.V., Jusupov R.M. Application of Attributed Grammar and Algorithmic Sensitivity Model for Knowledge Representation and Estimation // Artificial Intelligence and Information, Control Systems of ROBOTSA. Amsterdam: Elsevier Science Publishers B. V., 1984, P. 232–237
Forney D.G. The Viterbi Algorithm // Proceedings of the IEEE. 1973. V. 61. № 3. Р. 268–278
Huang X., Acero A., Hsiao-Wuen Hon Spoken Language Processing. Prentice Hall, 2001. 1008 p.
Huang X., Jack M., Y. Ariki Hidden Markov Models for Speech Recognition. Edinburgh University Press, 1990. 276 p.
Jensen F. Bayesian Networks and Decision Graphs. NY.: Springer. 2001. 268 p.
Jurafsky D., Martin J.H. Speech and Language Processing: An Introduction to Natural Language Processing, Speech Recognition, and Computational Linguistics. 2nd edition. Prentice-Hall, 2009. – 944 p.
Korb K., Nicholson A. Bayesian Artificial Intelligence. NY.: Chapman and Hall/CRC. 2004. 364 p.
Li J., Gray R.M. Image Segmentation and Compression Using Hidden Markov Models. 1st edition. Springer, 2000. 141 p.
Pearl J. Distributed Revision of Composite Beliefs. // Artificial Intelligence, vol. 33. 1987. P. 173–215
Pearl J. Fusion, propagation, and structuring in belief networks. // Artificial Intelligence, vol. 29, 1986. P. 241–288
Pearl J. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, 1988. 552 p.
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.
Welch L.R. Hidden Markov Models and the Baum-Welch Algorithm // IEEE Information Theory Society Newsletter. – 2003. –V. 53. – № 4. – Р. 10–13
Момзикова М.П., Великодная О.И., Пинский М.Я., Сироткин А.В., Тулупьев А.Л., Фильченков А.А. Оценка вероятности наблюдаемой последовательности в бинарных линейных по структуре скрытых марковских моделях с помощью апостериорного вывода в алгебраических байесовских сетях // Труды СПИИРАН. СПб: Наука, 2010. Вып. 2. C. 122–142
Момзикова М.П., Великодная О.И., Пинский М.Я., Сироткин А.В., Тулупьев А.Л., Фильченков А.А. Представление бинарных линейных по структуре скрытых марковских моделей в виде алгебраических байесовских сетей // Труды СПИИРАН. СПб: Наука, 2010. Вып. 1. C. 134–150
Пинский М.Я., Сироткин А.В., Тулупьев А.Л., Фильченков А.А. Повышение быстродействия алгоритма оценки наблюдаемой последовательности в скрытых марковских моделях на основе алгебраических байесовских сетей // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2011. Вып. 5. C. 69–73
Опарин В.В., Тулупьев А.Л. Синтез графа смежности с минимальным числом ребер: формализация алгоритма и анализ его корректности // Труды СПИИРАН. 2009. Вып. 11. С. 142–157
Опарин В.В., Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Матроидное представление семейства графов смежности над набором фрагментов знаний // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2010. Вып. 4. C. 73–76
Сироткин А.В. Модели, алгоритмы и вычислительная сложность синтеза согласованных оценок истинности в алгебраических байесовских сетях // Информационно-измерительные и управляющие системы. 2009. №11. С. 32–37
Сироткин А.В., Тулупьев А.Л. Моделирование знаний и рассуждений в условиях неопределенности: матрично-векторная формализация локального синтеза согласованных оценок истинности // Труды СПИИРАН. 2011. Вып. 18. С. 108–136
Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. Пособие. СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. 40 с. (Сер. Элементы мягких вычислений)
Тулупьев А.Л. Алгебраические байесовские сети: логико-вероятностные графические модели баз фрагментов знаний с неопределенностью: Диссертация на соискание ученой степени д-ра физ.-мат. Наук. СПб. 2009. 670 с. (Санкт-Петербургский государственный университет)
Тулупьев А.Л. Алгебраические байесовские сети: локальный логико- вероятностный вывод: Учеб. пособие. СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. 80 с. (Сер. Элементы мягких вычислений)
Тулупьев А.Л. Ациклические алгебраические байесовские сети: логико- вероятностный вывод // Нечеткие системы и мягкие вычисления: Научный журнал Российской ассоциации нечетких систем и мягких вычислений. 2006. Том 1, № 1. С. 57–93
Тулупьев А.Л. Байесовские сети доверия и алгебраические байесовские сети: сравнительный анализ выразительной мощности // Информационные технологии и интеллектуальные методы. 1997. Вып. № 2. С. 121–147
Тулупьев А.Л. Байесовские сети: логико-вероятностный вывод в циклах. СПб.: Изд-во С.-Петербургского ун-та, 2008. 140 с. (Элементы мягких вычислений)
Тулупьев А.Л. Непротиворечивость оценок вероятностей в алгебраических байесовских сетях. Вестник СПбГУ. Сер. 10. 2009. Вып. 3. С. 144–151
Тулупьев А.Л. Основы теории алгебраических байесовских сетей: программа спецкурса для студентов старших курсов и аспирантов. СПб.: СПбГУ, 2007. 7 с.
Тулупьев А.Л. Преобразование ациклических байесовских сетей доверия в алгебраические байесовские сети // Известия высших учебных заведений: Приборостроение. 2009. № 3. С. 21–23
Тулупьев А.Л. Согласованность данных и оценка вероятности альтернатив в цикле стохастических предпочтений // Известия высших учебных заведений: Приборостроение. 2009. № 7. С. 3–8
Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
Тулупьев А.Л., Сироткин А.В. Алгебраические байесовские сети: принцип декомпозиции и логико-вероятностный вывод в условиях неопределенности // Информационно-измерительные и управляющие системы. 2008. № 10. т. 6. С. 85–87
Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. Ун-та, 2009, 400 с.
Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локальной и глобальной структуры алгебраической байесовской сети в Java-приложениях // Труды СПИИРАН. 2007. Вып. 5. СПб.: Наука, 2007. С. 71–99
Тулупьев А.Л., Фильченков А.А., Вальтман Н.А. Алгебраические байесовские сети: задачи автоматического обучения // Информационно-измерительные и управляющие системы. 2011. № 11, т. 9. С. 57-61
Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик // Труды СПИИРАН. 2010. Вып. 1 (12). С. 119–133
Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик-собственников // Труды СПИИРАН. 2010. Вып. 3 (14) С. 150–169
Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи клик владений // Труды СПИИРАН. 2010. Вып. 2 (13). С. 119–133
Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи клик-собственников владений // Труды СПИИРАН. 2010. Вып. 4 (15). С. 193–212
Фильченков А.А. Алгоритмы построения третичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2011. Вып. 17. С. 197–218
Фильченков А.А., Тулупьев А.Л. Алгоритм выявления ацикличности первичной структуры алгебраической байесовской сети по ее четвертичной структуре // Труды СПИИРАН. 2011. Вып. 4(19). С. 128–145
Фильченков А.А., Тулупьев А.Л. Анализ циклов в минимальных графах смежности алгебраических байесовских сетей // Труды СПИИРАН. 2011. Вып. 17. С. 151–173
Фильченков А.А., Тулупьев А.Л. Понятие торакса в применении к исследованию графов смежности алгебраических байесовских сетей // Труды СПИИРАН. 2011. Вып. 16. С. 186–205
Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности Труды СПИИРАН. 2009. Вып. 11. С. 104–127
Фильченков А.А., Тулупьев А.Л. Третичная структура алгебраической байесовской сети // Труды СПИИРАН. 2011. Вып. 3 (18). С. 164–187
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Компаративный анализ клик минимальных графов смежности алгебраических байесовских сетей // Труды СПИИРАН. 2010. Вып. 2 (13). С. 87–105
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Мощность множества минимальных графов смежности // Труды СПИИРАН. 2010. Вып. 4 (15). С. 136–161
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Особенности анализа вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2010. Вып. 1 (12). С. 97–118
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Ребра графов смежности в контексте компаративного анализа клик минимальных графов смежности алгебраических байесовских сетей // Труды СПИИРАН. 2010. Вып. 3 (14). С. 132–149
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Структурный анализ клик минимальных графов смежности // Вестник Тверского государственного университета. Сер. Прикладная математика. 2011. №20. С. 139–151
Ширяев А.Н. Вероятность. М.: Наука, 1989. 640 с.
Cowell R.G., Dawid A.P., Lauritzen S.L., Spiegelhalter D.J. Probabilistic Networks and Expert Systems. NY.: Springer-Verlag, 1997. 370 p.
da-Silva C.Q. Hidden Markov models applied to a subsequence of the Xylella fastidiosa genome. Genet. Mol. Biol. São Paulo, Dec. 2003. V. 26. № 4. Р. 529–535
Gorodetsky V.I., Drozdgin V.V., Jusupov R.M. Application of Attributed Grammar and Algorithmic Sensitivity Model for Knowledge Representation and Estimation // Artificial Intelligence and Information, Control Systems of ROBOTSA. Amsterdam: Elsevier Science Publishers B. V., 1984, P. 232–237
Forney D.G. The Viterbi Algorithm // Proceedings of the IEEE. 1973. V. 61. № 3. Р. 268–278
Huang X., Acero A., Hsiao-Wuen Hon Spoken Language Processing. Prentice Hall, 2001. 1008 p.
Huang X., Jack M., Y. Ariki Hidden Markov Models for Speech Recognition. Edinburgh University Press, 1990. 276 p.
Jensen F. Bayesian Networks and Decision Graphs. NY.: Springer. 2001. 268 p.
Jurafsky D., Martin J.H. Speech and Language Processing: An Introduction to Natural Language Processing, Speech Recognition, and Computational Linguistics. 2nd edition. Prentice-Hall, 2009. – 944 p.
Korb K., Nicholson A. Bayesian Artificial Intelligence. NY.: Chapman and Hall/CRC. 2004. 364 p.
Li J., Gray R.M. Image Segmentation and Compression Using Hidden Markov Models. 1st edition. Springer, 2000. 141 p.
Pearl J. Distributed Revision of Composite Beliefs. // Artificial Intelligence, vol. 33. 1987. P. 173–215
Pearl J. Fusion, propagation, and structuring in belief networks. // Artificial Intelligence, vol. 29, 1986. P. 241–288
Pearl J. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, 1988. 552 p.
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.
Welch L.R. Hidden Markov Models and the Baum-Welch Algorithm // IEEE Information Theory Society Newsletter. – 2003. –V. 53. – № 4. – Р. 10–13
Момзикова М.П., Великодная О.И., Пинский М.Я., Сироткин А.В., Тулупьев А.Л., Фильченков А.А. Оценка вероятности наблюдаемой последовательности в бинарных линейных по структуре скрытых марковских моделях с помощью апостериорного вывода в алгебраических байесовских сетях // Труды СПИИРАН. СПб: Наука, 2010. Вып. 2. C. 122–142
Момзикова М.П., Великодная О.И., Пинский М.Я., Сироткин А.В., Тулупьев А.Л., Фильченков А.А. Представление бинарных линейных по структуре скрытых марковских моделей в виде алгебраических байесовских сетей // Труды СПИИРАН. СПб: Наука, 2010. Вып. 1. C. 134–150
Пинский М.Я., Сироткин А.В., Тулупьев А.Л., Фильченков А.А. Повышение быстродействия алгоритма оценки наблюдаемой последовательности в скрытых марковских моделях на основе алгебраических байесовских сетей // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2011. Вып. 5. C. 69–73
Опарин В.В., Тулупьев А.Л. Синтез графа смежности с минимальным числом ребер: формализация алгоритма и анализ его корректности // Труды СПИИРАН. 2009. Вып. 11. С. 142–157
Опарин В.В., Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Матроидное представление семейства графов смежности над набором фрагментов знаний // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2010. Вып. 4. C. 73–76
Сироткин А.В. Модели, алгоритмы и вычислительная сложность синтеза согласованных оценок истинности в алгебраических байесовских сетях // Информационно-измерительные и управляющие системы. 2009. №11. С. 32–37
Сироткин А.В., Тулупьев А.Л. Моделирование знаний и рассуждений в условиях неопределенности: матрично-векторная формализация локального синтеза согласованных оценок истинности // Труды СПИИРАН. 2011. Вып. 18. С. 108–136
Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. Пособие. СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. 40 с. (Сер. Элементы мягких вычислений)
Тулупьев А.Л. Алгебраические байесовские сети: логико-вероятностные графические модели баз фрагментов знаний с неопределенностью: Диссертация на соискание ученой степени д-ра физ.-мат. Наук. СПб. 2009. 670 с. (Санкт-Петербургский государственный университет)
Тулупьев А.Л. Алгебраические байесовские сети: локальный логико- вероятностный вывод: Учеб. пособие. СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. 80 с. (Сер. Элементы мягких вычислений)
Тулупьев А.Л. Ациклические алгебраические байесовские сети: логико- вероятностный вывод // Нечеткие системы и мягкие вычисления: Научный журнал Российской ассоциации нечетких систем и мягких вычислений. 2006. Том 1, № 1. С. 57–93
Тулупьев А.Л. Байесовские сети доверия и алгебраические байесовские сети: сравнительный анализ выразительной мощности // Информационные технологии и интеллектуальные методы. 1997. Вып. № 2. С. 121–147
Тулупьев А.Л. Байесовские сети: логико-вероятностный вывод в циклах. СПб.: Изд-во С.-Петербургского ун-та, 2008. 140 с. (Элементы мягких вычислений)
Тулупьев А.Л. Непротиворечивость оценок вероятностей в алгебраических байесовских сетях. Вестник СПбГУ. Сер. 10. 2009. Вып. 3. С. 144–151
Тулупьев А.Л. Основы теории алгебраических байесовских сетей: программа спецкурса для студентов старших курсов и аспирантов. СПб.: СПбГУ, 2007. 7 с.
Тулупьев А.Л. Преобразование ациклических байесовских сетей доверия в алгебраические байесовские сети // Известия высших учебных заведений: Приборостроение. 2009. № 3. С. 21–23
Тулупьев А.Л. Согласованность данных и оценка вероятности альтернатив в цикле стохастических предпочтений // Известия высших учебных заведений: Приборостроение. 2009. № 7. С. 3–8
Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
Тулупьев А.Л., Сироткин А.В. Алгебраические байесовские сети: принцип декомпозиции и логико-вероятностный вывод в условиях неопределенности // Информационно-измерительные и управляющие системы. 2008. № 10. т. 6. С. 85–87
Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. Ун-та, 2009, 400 с.
Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локальной и глобальной структуры алгебраической байесовской сети в Java-приложениях // Труды СПИИРАН. 2007. Вып. 5. СПб.: Наука, 2007. С. 71–99
Тулупьев А.Л., Фильченков А.А., Вальтман Н.А. Алгебраические байесовские сети: задачи автоматического обучения // Информационно-измерительные и управляющие системы. 2011. № 11, т. 9. С. 57-61
Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик // Труды СПИИРАН. 2010. Вып. 1 (12). С. 119–133
Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик-собственников // Труды СПИИРАН. 2010. Вып. 3 (14) С. 150–169
Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи клик владений // Труды СПИИРАН. 2010. Вып. 2 (13). С. 119–133
Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи клик-собственников владений // Труды СПИИРАН. 2010. Вып. 4 (15). С. 193–212
Фильченков А.А. Алгоритмы построения третичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2011. Вып. 17. С. 197–218
Фильченков А.А., Тулупьев А.Л. Алгоритм выявления ацикличности первичной структуры алгебраической байесовской сети по ее четвертичной структуре // Труды СПИИРАН. 2011. Вып. 4(19). С. 128–145
Фильченков А.А., Тулупьев А.Л. Анализ циклов в минимальных графах смежности алгебраических байесовских сетей // Труды СПИИРАН. 2011. Вып. 17. С. 151–173
Фильченков А.А., Тулупьев А.Л. Понятие торакса в применении к исследованию графов смежности алгебраических байесовских сетей // Труды СПИИРАН. 2011. Вып. 16. С. 186–205
Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности Труды СПИИРАН. 2009. Вып. 11. С. 104–127
Фильченков А.А., Тулупьев А.Л. Третичная структура алгебраической байесовской сети // Труды СПИИРАН. 2011. Вып. 3 (18). С. 164–187
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Компаративный анализ клик минимальных графов смежности алгебраических байесовских сетей // Труды СПИИРАН. 2010. Вып. 2 (13). С. 87–105
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Мощность множества минимальных графов смежности // Труды СПИИРАН. 2010. Вып. 4 (15). С. 136–161
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Особенности анализа вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2010. Вып. 1 (12). С. 97–118
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Ребра графов смежности в контексте компаративного анализа клик минимальных графов смежности алгебраических байесовских сетей // Труды СПИИРАН. 2010. Вып. 3 (14). С. 132–149
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Структурный анализ клик минимальных графов смежности // Вестник Тверского государственного университета. Сер. Прикладная математика. 2011. №20. С. 139–151
Ширяев А.Н. Вероятность. М.: Наука, 1989. 640 с.
Опубликован
2012-03-01
Как цитировать
Ревзин, Л. М., Фильченков, А. А., & Тулупьев, А. Л. (2012). Представление многозначных линейных по структуре скрытых марковских моделей в виде алгебраических байесовских сетей. Труды СПИИРАН, 1(20), 186-199. https://doi.org/10.15622/sp.20.10
Раздел
Статьи
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
