Мощность множества минимальных графов смежности
Ключевые слова:
алгебраические байесовские сети, вторичная структура, машинное обучение, вероятностно-графические модели систем знаний, глобальная структураАннотация
Алгебраические байесовские сети (АБС), представляющие собой логико-вероятностную графическую модель систем знаний с неопределенностью и позволяют работать в том числе с интервальными оценками вероятности. Работа алгоритмов АБС во многом опирается на вторичную структуру, представляемую графов смежности. Особую роль играет множество минимальных графов смежности, которое содержат наиболее «эффективные» вторичные структуры. Цель данной статьи — оценить мощность указанного множества. Введено понятие объема, характеризующее число вершин, входящих в компоненты связности строго сужения. Использование понятия объема позволила выразить коэффициент раздробленности клик — ее численную характеристику, через которую была выражена мощность множества минимальных графов смежности.Литература
Городецкий В.И. Алгебраические байесовские сети — новая парадигма экспертно-вычислительных систем // Юбилейный сборник трудов институтов Отделения информатики, вычислительной техники и автоматизации РАН. Т. 2. М.: РАН, 1993, С. 120–141.
Городецкий В.И., Тулупьев А.Л. Формирование непротиворечивых баз знаний с неопределенностью // Известия РАН. Сер. Теория и системы управления. 1997. №5. С. 33–42.
Опарин В.В., Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Матроидное представление семейства графов смежности над набором фрагментов знаний // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2010. Вып. 4. C. 73–76.
Павельчук А.В., Тулупьев А.Л., Тотмянина С.А. Подход к объектно-ориентированному представлению данных алгебраических байесовских сетей в java-коде и реляционных СУБД // Региональная информатика-2008 (РИ-2008). XI Санкт-Петербургская международная конференция. Санкт-Петербург, 22–24 октября, 2008 г.: Материалы конференции / СПОИСУ. СПб.: 2009. С. 68–76.
Сироткин А.В. Модели, алгоритмы и вычислительная сложность синтеза согласованных оценок истинности в алгебраических байесовских сетях // Информационно-измерительные и управляющие системы. 2009. №11. С. 32–37.
Тотмянина С.А., Павельчук А.В., Тулупьев А.Л. Алгебраические байесовские сети: структуры данных в СУБД и Java- коде // Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте. Научно-практическая конференция студентов, аспирантов, молодых ученых и специалистов (Коломна, 26–27 мая 2009 г.). Научные доклады. В 2-х т. Т. 2. М.: Физматлит, 2009, С. 123–131.
Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. пособие. СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. 40 с. (Сер. Элементы мягких вычислений).
Тулупьев А.Л. Алгебраические байесовские сети: реализация логико-вероятностного вывода в комплексе java-программ // Труды СПИИРАН. СПб.: Наука, 2009. Вып. 8. С. 191–232.
Тулупьев А.Л. Ациклические алгебраические байесовские сети: логико-вероятностный вывод // Нечеткие системы и мягкие вычисления: Научный журнал Российской ассоциации нечетких систем и мягких вычислений. 2006. Том 1, № 1. С. 57–93.
Тулупьев А.Л. Байесовские сети: логико-вероятностный вывод в циклах. СПб.: Изд-во С.-Петербургского ун-та, 2008. 140 с. (Элементы мягких вычислений.)
Тулупьев А.Л. Непротиворечивость оценок вероятностей в алгебраических байесовских сетях. Вестник СПбГУ. Сер. 10. 2009. Вып. 3. С. 144–151.
Тулупьев А.Л. Преобразование ациклических байесовских сетей доверия в алгебраические байесовские сети // Известия высших учебных заведений: Приборостроение. 2009. № 3. С. 21–23.
Тулупьев А.Л. Согласованность данных и оценка вероятности альтернатив в цикле стохастических предпочтений // Известия высших учебных заведений: Приборостроение. 2009. № 7. С. 3–8.
Тулупьев А.Л, Николенко С.И., Сироткин А.. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
Тулупьев А., Сироткин А.В. Алгебраические байесовские сети: принцип декомпозиции и логико-вероятностный вывод в условиях неопределенности // Информационно-измерительные и управляющие системы. 2008. № 10. т. 6. С. 85–87.
Тулупьев А.Л, .Николенко С.И., Сироткин А.В. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. ун-та, 2009, 400 с.
Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локальной и глобальной структуры алгебраической байесовской сети в Java-приложениях. // Труды СПИИРАН. 2007. Вып. 5. СПб.: Наука, 2007. С. 71–99.
Фильченков А.А Алгоритм построения множества минимальных графов смежности при помощи клик владений// Труды СПИИРАН. 2010. Вып. 2 (13). [в печати]
Фильченков А.А Алгоритм построения множества минимальных графов смежности при помощи клик-собственников владений// Труды СПИИРАН. 2010. Вып. 4 (15). [в печати]
Фильченков А.А Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик // Труды СПИИРАН. 2010. Вып. 1 (12). С. 119–133.
Фильченков А.А Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик-владений // Труды СПИИРАН. 2010. Вып. 3 (14). [в печати]
Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности Труды СПИИРАН. 2009. Вып. 11. С. 104–127.
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Компаративный анализа клик минимальных графов смежности // Труды СПИИРАН. 2010. Вып. 2 (13). [в печати]
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Компаративный анализа клик минимальных графов смежности // Труды СПИИРАН. 2010. Вып. 2 (13). [в печати]
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Ребра графов смежности в контексте компаративного анализа клик минимальных графов смежности // Труды СПИИРАН. 2010. Вып. 3 (14). [в печати]
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Структурный анализ клик минимальных графов смежности // Вестник Тверского государственного университета. Сер. Прикладная математика. 2010. [в печати].
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.
Prüfer H Neuer Beweis eines Satzes über Permutationen.// Arch. Math. Phys. 27, S. 742–744, 1918.
Городецкий В.И., Тулупьев А.Л. Формирование непротиворечивых баз знаний с неопределенностью // Известия РАН. Сер. Теория и системы управления. 1997. №5. С. 33–42.
Опарин В.В., Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Матроидное представление семейства графов смежности над набором фрагментов знаний // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2010. Вып. 4. C. 73–76.
Павельчук А.В., Тулупьев А.Л., Тотмянина С.А. Подход к объектно-ориентированному представлению данных алгебраических байесовских сетей в java-коде и реляционных СУБД // Региональная информатика-2008 (РИ-2008). XI Санкт-Петербургская международная конференция. Санкт-Петербург, 22–24 октября, 2008 г.: Материалы конференции / СПОИСУ. СПб.: 2009. С. 68–76.
Сироткин А.В. Модели, алгоритмы и вычислительная сложность синтеза согласованных оценок истинности в алгебраических байесовских сетях // Информационно-измерительные и управляющие системы. 2009. №11. С. 32–37.
Тотмянина С.А., Павельчук А.В., Тулупьев А.Л. Алгебраические байесовские сети: структуры данных в СУБД и Java- коде // Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте. Научно-практическая конференция студентов, аспирантов, молодых ученых и специалистов (Коломна, 26–27 мая 2009 г.). Научные доклады. В 2-х т. Т. 2. М.: Физматлит, 2009, С. 123–131.
Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. пособие. СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. 40 с. (Сер. Элементы мягких вычислений).
Тулупьев А.Л. Алгебраические байесовские сети: реализация логико-вероятностного вывода в комплексе java-программ // Труды СПИИРАН. СПб.: Наука, 2009. Вып. 8. С. 191–232.
Тулупьев А.Л. Ациклические алгебраические байесовские сети: логико-вероятностный вывод // Нечеткие системы и мягкие вычисления: Научный журнал Российской ассоциации нечетких систем и мягких вычислений. 2006. Том 1, № 1. С. 57–93.
Тулупьев А.Л. Байесовские сети: логико-вероятностный вывод в циклах. СПб.: Изд-во С.-Петербургского ун-та, 2008. 140 с. (Элементы мягких вычислений.)
Тулупьев А.Л. Непротиворечивость оценок вероятностей в алгебраических байесовских сетях. Вестник СПбГУ. Сер. 10. 2009. Вып. 3. С. 144–151.
Тулупьев А.Л. Преобразование ациклических байесовских сетей доверия в алгебраические байесовские сети // Известия высших учебных заведений: Приборостроение. 2009. № 3. С. 21–23.
Тулупьев А.Л. Согласованность данных и оценка вероятности альтернатив в цикле стохастических предпочтений // Известия высших учебных заведений: Приборостроение. 2009. № 7. С. 3–8.
Тулупьев А.Л, Николенко С.И., Сироткин А.. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
Тулупьев А., Сироткин А.В. Алгебраические байесовские сети: принцип декомпозиции и логико-вероятностный вывод в условиях неопределенности // Информационно-измерительные и управляющие системы. 2008. № 10. т. 6. С. 85–87.
Тулупьев А.Л, .Николенко С.И., Сироткин А.В. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. ун-та, 2009, 400 с.
Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локальной и глобальной структуры алгебраической байесовской сети в Java-приложениях. // Труды СПИИРАН. 2007. Вып. 5. СПб.: Наука, 2007. С. 71–99.
Фильченков А.А Алгоритм построения множества минимальных графов смежности при помощи клик владений// Труды СПИИРАН. 2010. Вып. 2 (13). [в печати]
Фильченков А.А Алгоритм построения множества минимальных графов смежности при помощи клик-собственников владений// Труды СПИИРАН. 2010. Вып. 4 (15). [в печати]
Фильченков А.А Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик // Труды СПИИРАН. 2010. Вып. 1 (12). С. 119–133.
Фильченков А.А Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик-владений // Труды СПИИРАН. 2010. Вып. 3 (14). [в печати]
Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности Труды СПИИРАН. 2009. Вып. 11. С. 104–127.
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Компаративный анализа клик минимальных графов смежности // Труды СПИИРАН. 2010. Вып. 2 (13). [в печати]
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Компаративный анализа клик минимальных графов смежности // Труды СПИИРАН. 2010. Вып. 2 (13). [в печати]
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Ребра графов смежности в контексте компаративного анализа клик минимальных графов смежности // Труды СПИИРАН. 2010. Вып. 3 (14). [в печати]
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Структурный анализ клик минимальных графов смежности // Вестник Тверского государственного университета. Сер. Прикладная математика. 2010. [в печати].
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.
Prüfer H Neuer Beweis eines Satzes über Permutationen.// Arch. Math. Phys. 27, S. 742–744, 1918.
Опубликован
2010-12-01
Как цитировать
Фильченков, А. А., Тулупьев, А. Л., & Сироткин, А. В. (2010). Мощность множества минимальных графов смежности. Труды СПИИРАН, 4(15), 136-161. https://doi.org/10.15622/sp.15.8
Раздел
Статьи
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
