Третичная структура алгебраической байесовской сети
Ключевые слова:
алгебраические байесовские сети, третичная структура, машинное обучение, вероятностно-графические модели систем знаний, глобальная структураАннотация
Третичная структура алгебраической байесовской сети (АБС) требуется для построения как случайного минимального графа смежности, так и всего множества минимальных графов смежности. Помимо этого она требуется для нахождения лучшей или оптимальной вторичной структуры для заданной первичной структуры АБС. Целью работы является формирование четко определенного понятия третичной структуры АБС и связанных с ней объектов на основе синтеза существующих подходов, а также исследование их свойств. Рассмотрены все существующие подходы к определению понятий«клика», «множество клик» и «граф клик», а также классификация клик максимального графа смежности. Построена единая терминологическая база для описания сопутствующих объектов, удовлетворяющая критериям неизбыточности и полноты систематизации. Третичная полиструктура определена как семейство графов, построенных над подмножествами множества сужений максимального графа смежности, ребра которых соответствуют тем или иным родственным отношениям, определенным в статье. Третичная структура определена как ориентированный граф, ребра которого проведены от родительских вершин к сыновьем, а вершинами являются сужения максимального графа смежности на веса ребер и вершин, а также на пустой вес (родительский граф над расширенным множеством значимых клик).Литература
Конфуций Беседы и суждения. Ростов-на-Дону: Феникс. 2006. 304 с.
Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. 2-е изд. М.: Вильямс, 2005. 1296 с.
Опарин В.В., Тулупьев А.Л. Синтез графа смежности с минимальным числом ребер: формализация алгоритма и анализ его корректности // Труды СПИИРАН. 2009. Вып. 11. С. 142–157.
Опарин В.В., Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Матроидное представление семейства графов смежности над набором фрагментов знаний // Науч- но-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2010. Вып. 4. C. 73–76.
Сироткин А.В. Модели, алгоритмы и вычислительная сложность синтеза согласованных оценок истинности в алгебраических байесовских сетях // Информационно-измерительные и управляющие системы. 2009. №11. С. 32–37.
Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. Пособие. СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. 40 с. (Сер. Элементы мягких вычислений).
Тулупьев А.Л. Алгебраические байесовские сети: локальный логико-вероятностный вывод: Учеб. Пособие. СПб.: СПбГУ; ООО Издательство «Анатолия», 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.
Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик // Труды СПИИРАН. 2010. Вып. 1 (12). С. 119–133.
Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик-собственников // Труды СПИИРАН. 2010. Вып. 3 (14) С. 150–169.
Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи клик владений // Труды СПИИРАН. 2010. Вып. 2 (13). С. 119–133.
Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи клик-собственников владений // Труды СПИИРАН. 2010. Вып. 4 (15). С. 193–212.
Фильченков A.A. Алгоритмы построения третичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2011. Вып. 17. С. 197–218.
Фильченков А.А., Тулупьев А.Л. Анализ циклов в минимальных графах смежности алгебраических байесовских сетей // Труды СПИИРАН. 2011. Вып. 17. С. 151–173.
Фильченков А.А., Тулупьев А.Л. Понятие торакса в применении к исследованию графов смежности алгебраических байесовских сетей // Труды СПИИРАН. 2011. Вып. 16. С. 186–205.
Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности Труды СПИИРАН. 2009. Вып. 11. С. 104–127.
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Компаративный анализ клик минимальных графов смежности алгебраических байесовских сетей // Труды СПИИРАН. 2010. Вып. 2 (13). С. 87–105.
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Мощность множества минимальных графов смежности // Труды СПИИРАН. 2010. Вып. 4 (15). С. 136–161.
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Особенности анализа вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2010. Вып. 1 (12). С. 97–118.
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Ребра графов смежности в контексте компаративного анализа клик минимальных графов смежности алгебраических байесовских сетей // Труды СПИИРАН. 2010. Вып. 3 (14). С. 132–149.
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Структурный анализ клик минимальных графов смежности // Вестник Тверского государственного университета. Сер. Прикладная математика. 2011. №20. С. 139–151.
Харари Ф. Теория графов. М.: УРСС. 2003, 296 с.
Bayes T., Price R. An Essay towards solving a Problem in the Doctrine of Chances. Philosophical Transactions of the Royal Society of London, 53. 1763, 370–418 pp.
Bron C., Kerbosh J. Algorithm 457 — Finding all cliques of an undirected graph // Comm. Of ACM, 16. 1973. p. 575—577.
Cowell R.G., Dawid A.P., Lauritzen S.L., Spiegelhalter D.J. Probabilistic Networks and Expert Systems. NY.: Springer-Verlag, 1997. 370 p.
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.
Jensen F. Bayesian Networks and Decision Graphs. NY.: Springer. 2001. 268 p.
Karp R.M., Miller R.E., Thatcher J.W. Reducibility Among Combinatorial Problems // The Journal of Symbolic Logic, Vol. 40, No. 4 (Dec., 1975), pp. 618-619.
Korb K., Nicholson A. Bayesian Artificial Intelligence. NY.: Chapman amnd Hall/CRC. 2004. 364 p.
Kuratowski K. Sur le probléme des courbes gauches en Topologie // Fundamenta Mathematicae 15. 1930. P. 271–283.
Laplace P. Essai philosophique sur les probabilités. 6e édition, 1840. Paris: Bachelier. 282 p.
Neyman J. First Course in Probability and Statistics. 1950. Henry Holt & Co. 350 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.
Venn J. The Logic of Chance. 1866. General Books LLC. 184 p.
Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. 2-е изд. М.: Вильямс, 2005. 1296 с.
Опарин В.В., Тулупьев А.Л. Синтез графа смежности с минимальным числом ребер: формализация алгоритма и анализ его корректности // Труды СПИИРАН. 2009. Вып. 11. С. 142–157.
Опарин В.В., Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Матроидное представление семейства графов смежности над набором фрагментов знаний // Науч- но-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2010. Вып. 4. C. 73–76.
Сироткин А.В. Модели, алгоритмы и вычислительная сложность синтеза согласованных оценок истинности в алгебраических байесовских сетях // Информационно-измерительные и управляющие системы. 2009. №11. С. 32–37.
Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. Пособие. СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. 40 с. (Сер. Элементы мягких вычислений).
Тулупьев А.Л. Алгебраические байесовские сети: локальный логико-вероятностный вывод: Учеб. Пособие. СПб.: СПбГУ; ООО Издательство «Анатолия», 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.
Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик // Труды СПИИРАН. 2010. Вып. 1 (12). С. 119–133.
Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик-собственников // Труды СПИИРАН. 2010. Вып. 3 (14) С. 150–169.
Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи клик владений // Труды СПИИРАН. 2010. Вып. 2 (13). С. 119–133.
Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи клик-собственников владений // Труды СПИИРАН. 2010. Вып. 4 (15). С. 193–212.
Фильченков A.A. Алгоритмы построения третичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2011. Вып. 17. С. 197–218.
Фильченков А.А., Тулупьев А.Л. Анализ циклов в минимальных графах смежности алгебраических байесовских сетей // Труды СПИИРАН. 2011. Вып. 17. С. 151–173.
Фильченков А.А., Тулупьев А.Л. Понятие торакса в применении к исследованию графов смежности алгебраических байесовских сетей // Труды СПИИРАН. 2011. Вып. 16. С. 186–205.
Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности Труды СПИИРАН. 2009. Вып. 11. С. 104–127.
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Компаративный анализ клик минимальных графов смежности алгебраических байесовских сетей // Труды СПИИРАН. 2010. Вып. 2 (13). С. 87–105.
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Мощность множества минимальных графов смежности // Труды СПИИРАН. 2010. Вып. 4 (15). С. 136–161.
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Особенности анализа вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2010. Вып. 1 (12). С. 97–118.
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Ребра графов смежности в контексте компаративного анализа клик минимальных графов смежности алгебраических байесовских сетей // Труды СПИИРАН. 2010. Вып. 3 (14). С. 132–149.
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Структурный анализ клик минимальных графов смежности // Вестник Тверского государственного университета. Сер. Прикладная математика. 2011. №20. С. 139–151.
Харари Ф. Теория графов. М.: УРСС. 2003, 296 с.
Bayes T., Price R. An Essay towards solving a Problem in the Doctrine of Chances. Philosophical Transactions of the Royal Society of London, 53. 1763, 370–418 pp.
Bron C., Kerbosh J. Algorithm 457 — Finding all cliques of an undirected graph // Comm. Of ACM, 16. 1973. p. 575—577.
Cowell R.G., Dawid A.P., Lauritzen S.L., Spiegelhalter D.J. Probabilistic Networks and Expert Systems. NY.: Springer-Verlag, 1997. 370 p.
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.
Jensen F. Bayesian Networks and Decision Graphs. NY.: Springer. 2001. 268 p.
Karp R.M., Miller R.E., Thatcher J.W. Reducibility Among Combinatorial Problems // The Journal of Symbolic Logic, Vol. 40, No. 4 (Dec., 1975), pp. 618-619.
Korb K., Nicholson A. Bayesian Artificial Intelligence. NY.: Chapman amnd Hall/CRC. 2004. 364 p.
Kuratowski K. Sur le probléme des courbes gauches en Topologie // Fundamenta Mathematicae 15. 1930. P. 271–283.
Laplace P. Essai philosophique sur les probabilités. 6e édition, 1840. Paris: Bachelier. 282 p.
Neyman J. First Course in Probability and Statistics. 1950. Henry Holt & Co. 350 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.
Venn J. The Logic of Chance. 1866. General Books LLC. 184 p.
Опубликован
2011-09-01
Как цитировать
Фильченков, А. А., & Тулупьев, А. Л. (2011). Третичная структура алгебраической байесовской сети. Труды СПИИРАН, 3(18), 164-187. https://doi.org/10.15622/sp.18.7
Раздел
Статьи
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
