Алгебраические байесовские сети: изолированное слияние фрагментов знаний в условиях дефицита информации
Предмет исследования
При машинном обучении вероятностных графических моделей нередки ситуации, в которых одному объекту оказываются сопоставлены две или более модели, обученные на различных, но пересекающихся наборах данных. Предметом данного исследования является операция слияния таких моделей, представленных фрагментами знаний алгебраической байесовской сети. Целью данного исследования является описание и формализация способов слияния алгебраических байесовских сетей, представленных в виде фрагментов знаний.
Метод
Построены модели слияния, семантика которых четко эксплицируется предположениями о соотношении вероятностных семантик рассматриваемых фрагментов знаний.
Основные результаты
Определены и систематизированы способы слияния фрагментов знаний, при которых не происходит генерации новых элементов сети. Приведено и доказано утверждение о числе атомов в получаемой сети и теорема о сложности поддержания ее интернальной непротиворечивости. Продемонстрирован пример слияния двух сетей на выборке с шумом. При этом для проведения компаративного анализа теоретическое распределение выборки задано, а сама выборка генерируется методом Монте-Карло.
Практическая значимость
Предложенные в исследовании способы слияния алгебраических байесовских сетей могут найти применение при работе с двумя или более обученными сетями, описывающими различные свойства одного объекта. Использование данных способов позволит построить, агрегирующую все данные об исследуемом объекте, оказавшиеся доступными, в комплексную сеть и проводить в ней операции логико-вероятностного вывода.
Введение
При сборе данных нередки случаи их частичной потери, искажения, отсутствия части информации. Такие данные называются неполными данными, или, в ряде случаев неполной (несовершенной) информацией (imperfect information) [1, 2]. Существуют различные математические модели для работы с ней, в том числе алгебраические байесовские сети, относящиеся к классу вероятностных графических моделей [3-6].
При этом различные наборы данных (в том числе частично пересекающиеся) могут содержать сведения об одном и том же явлении, объекте, процессе или их аспектах, полученные из различных источников, либо различными путями (каналами). Таким образом, при работе с моделями, обучающимися на этих данных, может возникнуть ситуация, при которой построено две модели одного и того же объекта или более, имеющие частичные пересечения по структуре. Разумно предположить, что при анализе ситуации, подготовке и принятии решений, построении прогнозов, оценке последствий вмешательств или иных действиях целесообразно использовать все построенные модели совместно, т.е. как единую систему — более сложную и богатую модель. Таким образом, представляется актуальной проблема слияния уже обученных на различных наборах данных моделей одного и того же объекта.
Настоящая работа преследует базовую цель — предложить и формализовать способы слияния алгебраических байесовских сетей, каждая из которых представлена в виде фрагмента знаний.
Релевантные работы
К вероятностным графическим моделям [5, 6] применяется своя система алгоритмов машинного обучения, которая отличается и построена на других принципах, чем алгоритмы машинного обучения нейронных сетей [7, 8].
К классу вероятностных графических моделей относятся байесовские сети доверия [9-11], марковские сети [12], алгебраические байесовские сети [3, 4] и др. Все эти модели работают со знаниями с неопределенностью.
В работе [13] рассмотрена двойственность байесовских сетей доверия и нейронных сетей с прямой связью, в то время как [14] посвящена их объединению с другими моделями. Ряд работ посвящен использованию байесовских сетей доверия в различных областях, таких как здоровье, инженерия, экология [9-11].
Значительная часть теории алгебраических байесовских сетей (в ее текущем состоянии) подробно изложена в монографиях [15, 16] и учебнике [17]. Структурно алгебраические байесовские сети разделяются на фрагменты знаний, которые могут быть представлены в виде идеала конъюнктов, дизъюнктов или квантов. Операции логико-вероятностного вывода в сетях позволяют получать вероятность истинности формулы (априорный вывод схематично представлен на рис. 1), изменять оценки в сети на основе поступившего свидетельства (апостериорный вывод). Кроме того, при работе с алгебраическими байесовскими сетями выделяется понятие их непротиворечивости, характеризующее корректность (совместность и согласованность с аксиомами вероятности) представленных в сети оценок вероятности истинности [18]. При этом непротиворечивость может быть как подпирающей, т.е. находящей наибольшие интервалы оценок, содержащиеся в имеющихся, так и накрывающей, т.е. находящей наименьшие интервалы оценок, содержащие имеющиеся [19].
Рис. 1. Схема априорного вывода (p — вероятность формулы; x1, x2, x3, x4 — атомарные пропозициональные формулы, над которыми построена сеть)
Ранее в работе [20] были выдвинуты тезисы о возможности слияния алгебраических байесовских сетей. Однако, насколько известно авторам, теоретических исследований в области слияния алгебраических байесовских сетей, построенных над данными, полученными из различных источников и имеющими пересечения по элементам сети, не производились, исключая вопросы инкрементального синтеза вторичной структуры [4, 21].
Знания с неопределенностью
В рамках исследования делается предположение о наличии выборки некоторого числа логических означиваний набора пропозициональных переменных. В идеальной ситуации каждая из переменных имеет означивание true (истина) или false (ложь). Однако в большинстве реальных задач в элементах выборки имеются пропуски: например, если значение элемента получается на основании утверждения «x1 -> x2 истинно», то однозначно можно установить истинность только переменной x2, в то время как x1 может принимать как значение true, так и значение false. Пример такой выборки представлен в табл. 1.
Таблица 1. Пример набора значений переменных x1, x2 с пропусками. Значение x1^x2 получено путем применения операции конъюнкции к данным с пропусками.
Таким образом, фактически речь идет о трехзначной логике Клини [22], где помимо констант true (1) и false (0) рассматривается третья константа unknow (*). Ниже приведены таблицы истинности над этими переменными для основных логических операций (отрицание, конъюнкция и дизъюнкция) (табл. 2).
Таблица 2. Таблицы истинности в трехзначной логике Клини
Фактически за набором данных об означивании логических переменных стоит информация о вероятности их истинности. При этом различные модели позволяют по-разному обработать имеющуюся информацию. В данной работе будут рассмотрены алгебраические байесовские сети (рис. 2).
Как уже было сказано выше, одним из представлений алгебраических байесовских сетей является граф, в котором вершинами являются фрагменты знаний, представимые в виде идеала конъюнктов. При этом каждому конъюнкту приписывается скалярная или интервальная оценка вероятности. Последняя особенность сети позволяет учитывать пропущенные значения, за счет чего и появляются интервалы истинности (подробнее описано в работе [16]). Возможны альтернативные модели алгебраических байесовских сетей, в которых элементами являются пропозиции-дизъюнкты или пропозиции-кванты [15-17]...
Рис. 3. Байесовская сеть доверия v, w, х, у, z — атомарные пропозициональные формулы, над которыми построена сеть, v', w', х' — их отрицания)
Байесовская сеть доверия (рис. 3) представляет собой направленный граф, в котором каждой вершине соответствует случайный элемент. Связь между элементами базируется на условных вероятностях, находящих свое отражение в графической структуре сети.
Особенности структуры байесовских сетей доверия, в том числе скалярные оценки и условные зависимости от вершин-предков, делают процесс изолированного слияния таких сетей невозможным.
Слияние алгебраических байесовских сетей
Формализуем задачу слияния в рамках теории алгебраических байесовских сетей.
Предположим, что имеется некоторый объект (источник информации), данные о котором поступают по различным каналам (рис. 4). На основе полученных данных строятся две алгебраические байесовские сети. Для того чтобы сконцентрироваться на проблемах слияния, а не структурного синтеза, в контексте данной статьи эти сети представлены в виде фрагментов знаний. При этом часть информации, получаемой как по первому, так и по второму каналу, характеризует одни и те же свойства объекта. Поскольку оба фрагмента знаний частично описывают один объект, возникает желание построить на их основе единую алгебраическую байесовскую сеть. Данная задача решается в представленной работе путем выделения и формализации трех способов слияния алгебраических байесовских сетей...
Рис. 4. Схематичное изображение каналов информации
<•••>
Заключение
Одной из основных задач машинного обучения является построение наиболее точных и корректных суждений с максимальным учетом доступной информации. Вопросы слияния моделей, обученных на неполной информации из различных каналов данных, тесно ассоциированы с данной задачей.
В статье были сформулированы подходы к изолированным слияниям фрагментов знаний, утверждения о числе элементов в получаемой сети и сложности поддержания ее интернальной непротиворечивости. Дальнейшими работами в данном направлении является изучение путей слияния структурно более сложных сетей, а также возможности использования описанных подходов в рамках применения алгебраических байесовских сетей в исследованиях, посвященных социоинженерным атакам [23, 24].
Харитонов Н.А., Тулупьев А.Л. Алгебраические байесовские сети: изолированное слияние фрагментов знаний в условиях дефицита информации // Научно-технический вестник информационных технологий, механики и оптики. 2019. Т. 19. № 4. с.641-649
17. Тулупьев А.Л., Николенко С.И., Сироткин А.В. Основы теории байесовских сетей: учебник. СПб.: СПбГУ, 2019. 399 с.
pdf содержание