Автоматическое обучение фрагментов знаний в алгебраических байесовских сетях по данным с пропусками

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Автоматическое обучение фрагментов знаний в алгебраических байесовских сетях по данным с пропусками

Хотя проблема промышленного внедрения информационных систем, использующих и способных обрабатывать данные и знания с неопределенностью, становится все более актуальной, ее решению мешает, в частности, одно «узкое место» - дефицит данных и знаний (Knowledge Bottleneck) [1].

Такой дефицит весьма остр. Есть предметные области, для которых просто не существует человека-эксперта. Кроме того, не все эксперты готовы делиться своими знаниями. Наконец, при попытках организовать автоматическое (машинное) обучение по информации из баз данных вдруг обнаруживается, что эти данные неполны (т.е. имеют пропуски) и зачастую недостоверны.

Задача автоматического обучения в случае фрагмента знаний алгебраических байесовских сетей

В случае фрагмента знаний АБС его структура уже известна - это идеал конъюнктов, образованный над небольшим числом атомарных пропозициональных формул [2-9]. Требуется предложить подход к обработке обучающей выборки, возможно, содержащей пропуски, который бы позволил приписать конъюнктам из идеала скалярные или интервальные оценки вероятностей.

Таким образом, локальное обучение сводится преимущественно к одной задаче - формированию набора верятностных оценок истинности над фрагментом знаний с известной структурой по исходному набору совместных означиваний атомарных литералов. Для фрагмента знаний, построенного над идеалом конъюнктов, набор оценок вероятностей записывается в виде вектора ; для фрагмента знаний над набором квантов - в виде вектора . Эти два вектора оценок тесно связаны между собой [4, 6, 7, 9, 10].

Элементы обучающей выборки, с точки зрения теории АБС, являются квантами. Пусть задан фрагмент знаний над алфавитом из трех атомов . Набор квантов

алгебраический байесовский сеть литерал

служит примером выборки.

Для каждого отдельно взятого фрагмента знаний алфавит фиксирован, а порядок следования атомов в кванте может быть заранее оговорен, поэтому нет необходимости все время использовать буквенно-индексные обозначения для того, чтобы указать означивания того или иного атомарного литерала. Договоримся его отрицательному означиванию сопоставлять 0, а положительному - 1. Тогда та же самая выборка может быть записана как

что заметно короче. Еще несколько примеров обучающей выборки приведено в табл. 1.

Бинарные оценки вероятностей

Заметим, что предложенные значения 0 и 1 можно трактовать как вероятность положительного означивания случайного бинарного элемента, соответствующего атому. При таких вероятностях положительного означивания (а именно, при вероятностях со значениями 0 или 1) однозначно определяется вероятность любого конъюнкта, т.е. конъюнкции некоторого набора атомов. В результате, вероятность конъюнкта можно получить по любой из двух формул:

(1)

(2)

Более того, справа в формулах (1-2) может использоваться любая триангулярная норма (а не только произведение или минимум). Однако формулами (1-2) уже нельзя будет воспользоваться, если вероятность двух или более атомов не будет равна 0 или 1. В таком случае нельзя даже ожидать, что оценка вероятности останется скалярной; скорее всего, придется пользоваться интервальными оценками, если не прибегать к дополнительным предположениям. Это - весьма существенный момент.

Таблица 1. Вероятности конъюнктов в ФЗ над одним атомом

Таблица 2. Вероятности конъюнктов в ФЗ над двумя атомами

Таблица 3. Вероятности конъюнктов в ФЗ над тремя атомами

Таким образом, каждому кванту можно сопоставить фрагмент знаний с бинарными оценками вероятности истинности (табл. 1-3). Вероятность пустого конъюнкта не указана; она всегда равна 1.

Обучение по выборке: означивания без пропущенных элементов

Последовательность означиваний, из которых состоит выборка, нелегка для восприятия и труднообозрима, особенно если она большая. Однако выборку можно записать в более компактной форме: кванты упорядочить, повторы среди них исключить, каждому кванту сопоставить число - сколько раз он встречается в обучающей выборке. Если поделить каждое такое число на общее число элементов в выборке, то получим оценку вероятности истинности кванта. Таким образом будет сформирован вектор , задающий распределение вероятностей на квантах. Его можно преобразовать в вектор - особым образом упорядоченную совокупность вероятностей конъюнктов - с помощью уравнения [4, 6, 7, 9, 10].

Любой из векторов и может служить результатом локального обучения по имеющейся выборке. Как правило, число элементов во фрагменте знаний невелико; оно много меньше, чем объем выборки. Поэтому получившийся результат будет более обозрим, чем исходные данные.

Таблица 4. Примеры обучающих выборок S_i без пропусков

Формализуем описанную процедуру и обсудим ее некоторые особенности, не особенно заметные на первый взгляд.

Пусть выборка состоит из набора квантов , где - размер выборки. Каждому кванту можно сопоставить - вектор вероятностей квантов, построенных над соответствующим алфавитом. В векторе все элементы нули, за исключением того, который соответствует кванту : этот элемент вектора равен единице.

При введенных обозначениях и соглашениях процедура обучения выглядит совсем просто

. (3)

Такие вычисления очень удобно реализовать с использованием массивов небольшой размерности. Кроме того, формулу (3) легко адаптировать для ситуации, когда обучение происходит постепенно, т.е. элементы выборки доступны не все сразу, а поступают друг за другом. При этом требуется на каждом шаге иметь «обученный» уже поступившими сведениями вектор . Пусть у нас совершается -й шаг: - результат обучения вектора предшествующими элементами выборки, поступает элемент . Тогда рекуррентная процедура «дообучения» будет выглядеть как

(4)

Для простоты примем , поскольку на первой итерации он умножается на ноль и далее роли не играет.

Аналогичные соотношения можно записать и для вектора вероятностей конъюнктов:

(5)

(6)

Для удобства будем считать, что , т.е. все компоненты этого вектора нулевые, за исключением самой первой: она равна 1. На данном этапе с формальной точки зрения выбор исходного вектора несущественен: он все равно умножается на ноль. Однако в дальнейшем нам потребуется, чтобы этот вектор был бы непротиворечив.

Уравнения (4) и (6) можно переписать несколько иначе - так, чтобы четко было видно, что они определяют линейную комбинацию участвующих в них векторов.

(7)

(8)

Заметим, что векторы ,, , непротиворечивы. В теории АБС известно, что линейная комбинация непротиворечивых фрагментов знаний одинаковой структуры будет являться непротиворечивым фрагментом знаний; это же справедливо и для соответствующих им векторов оценок. Таким образом, в процессе обучения у нас формируются непротиворечивые фрагменты знаний, т.е. оказываются непротиворечивыми наборы оценок , .

Уравнения, записанные в виде (7) и (8), можно рассматривать как один из вариантов адаптации нашей системы знаний и к поступившим новым сведениям и . Кроме того, адаптивное обучение может строиться и на иных (но похожих) уравнениях; например, на следующих:

(9)

(10)

где , а векторы и непротиворечивы и представляют наши априорные знания или предположения о системе. Подход, представленный уравнениями (9) и (10), имеет глубокие теоретические основания [1].

Заметим, что выбор коэффициента сказывается на скорости «забывания» априорных знаний и на скорости «адаптации» к новым данным. Уравнения адаптации могут быть составлены и иначе; в частности, в них может комбинироваться вектор, представляющий априорные знания, и вектор (или соответственно). В этом случае адаптация «происходит сразу» по отношению ко всей обучающей выборке; каждый элемент выборки внесет одинаковый вклад в получившийся результат:

(11)

(12)

Означивания с пропущенными элементами

Обучение по «хорошей» выборке, в которой нет элементов с пропусками в означиваниях, идеологически просто - сводится к подсчету частот появления того или иного означивания. Затем полученные результаты могут быть дополнительно скомбинированы с некоторым объектом, представляющим априорные знания, однако и здесь проблем не возникает. К сожалению, не всегда оказывается так, что обучение проходит по «хорошим» (т.е. без пропусков) исходным данным. Общим случаем обработки данных «с дефектами» и восстановления их пропущенных элементов занимаются целые отрасли статистики и искусственного интеллекта [1,11,12]. Мы же рассмотрим возникающие проблемы в рамках и на языке логико-вероятностного подхода, которого придерживается теория алгебраических байесовских сетей.

В табл. 5 приведены примеры обучающих выборок с пропусками. В них знак * стоит на месте пропущенного элемента данных (заметим, что можно выбрать и другое обозначение, например U от Uncertain, Undefined, Undetected, либо NULL, либо -, либо ^, либо еще какой-нибудь символ).

Предложенные в табл. 5 выборки демонстрируют разную степень «некачественности» доступных сведений для обучения фрагментов знаний.

Таблица 5. Примеры обучающих выборок c пропусками

Для обучения ничего не дадут примеры S₁₁ и S₁₃. Кроме числа реализаций, они не позволят определить вообще ничего.

Выборка S₁₄ более информативна, однако в ней не встречается ни одного элемента, который бы содержал означивания обоих атомарных литералов. По этой выборке мы можем строить предположения о вероятности истинности каждого отдельного атома, но не о вероятностной связи их совместных означиваний. Аналогичная ситуация наблюдается и в случае выборки S₁₆.

В выборке S₁₇ имеется более тонкий дефект. На ее основе можно строить оценки вероятности истинности атомов, их попарных конъюнкций, однако в ней не встречается ни одной реализации, по которой мы могли бы судить о связи означиваний сразу всех трех атомарных литералов.

Выборки S₁₅ и S₁₈ отличаются от остальных в лучшую сторону: в них меньше пропусков и присутствуют элементы с известными означиваниями сразу всех атомарных литералов.

Наличие или отсутствие закономерности, которой подчиняются места расположения пропущенных означиваний, играет существенную роль. Классификация такого рода закономерностей предлагается в соответствующей литературе [11,13,14].

Таблица 6. Выборки без пропусков, не противоречащие выборке с пропусками

Чтобы двинуться дальше, требуется исследовать семантику * - пропущенного означивания. На самом деле, на месте знака * могли стоять либо 0, либо 1. Таким образом, выборке с пропущенными означиваниями может соответствовать несколько различающихся выборок без пропущенных значений (или возможных выборок, или выборок, не противоречащих исходной, или выборок, соответствующих исходной). В табл. 6 приведен соответствующий пример.

Если сохранять порядок следования элементов выборки, то в нашем случае при пропущенных означиваниях существует 2^k выборок без пропусков, соответствующих (не противоречащих) исходной. Можно говорить о семействе выборок без пропусков, не противоречащих исходной выборке с пропусками. Таким образом, выборка с пропусками задает семейство распределений вероятностей, а значит фрагмент знаний, построенный на ее основе, не может содержать лишь скалярные оценки истинности. Без дополнительных предположений, гипотез или соглашений невозможно оправдать выбор одного распределения вероятностей из многих для того, чтобы обеспечить каждый элемент фрагмента знаний скалярной оценкой вероятности истинности. Следовательно, открывается два выбора: 1) либо допустить нескалярные оценки истинности, 2) либо предложить принцип выбора или формирования одного распределения при условиях, что имеются несколько возможных.

Обучение интервальных оценок в условиях неопределенности

Знаку * можно дать две разные интерпретации. Ему можно сопоставить либо множество их двух элементов {0; 1}, либо замкнутый промежуток [0; 1]. В первом случае подразумевается, что на позиции, занимаемой знаком *, должен был бы стоять либо 0, либо 1. Во втором случае предполагается, что запись со * лучше всего представляется (замещается) набором записей, часть которого содержит 0 вместо *, а другая часть - 1 вместо *. Анализ соотношения этих частей позволяет говорить о вероятности положительного (т.е. 1) означивания той позиции, где в исходном данном стоит *; причем эта вероятность как раз может принять любое значение из [0; 1].

Как уже было отмечено, мы не можем ожидать, что по выборке с пропусками нам удастся получить фрагмент знаний со скалярными оценками истинности, не прибегая к дополнительным гипотезам. Однако мы можем попытаться построить (обучить) интервальные оценки, если всякий раз, когда встречается знак *, будем рассматривать оба допустимых случая его означивания (0 и 1) и вести подсчет нижней и верхней оценки частоты встречаемости положительного означивания. В табл. 7 рассмотрен простейший случай - обучается вероятностная оценка истинности одного атома , а интерпретации поступающих означиваний для фрагмента знаний над алфавитом из двух элементов приведены в табл. 8.

Используя табл. 8 и принципы суммирования и умножения по Минковскому, мы можем обработать обучающую выборку и получить верхнюю и нижнюю оценку вероятности каждого конъюнкта из фрагмента знаний.

Таблица 7. Обучение одного параметра по выборке с пропусками

Таблица 8. Связь означиваний квантов в выборке и конъюнктов

Если нас устраивают интервальные оценки, то задачи автоматического обучения по выборке с пропущенными элементами означиваний в случае алфавита из трех или более атомов решаются аналогичным образом. Однако интервальные оценки могут нас и не устраивать.

Обучение точечных оценок в условиях неопределенности

В этом разделе подход, предложенный Н.В. Ховановым [12], адаптируется для применения к объектам теории алгебраических байесовских сетей.

Чтобы получить скалярные оценки элементов фрагмента знаний, построенного либо над идеалом конъюнктов, либо над набором квантов, необходимо выбрать какое-то одно распределение вероятностей, причем в условиях дефицита информации, то есть в случае, когда обучающая выборка содержит означивания с пропусками элементов. Такой выбор может быть осуществлен на основе явных или неявных дополнительных предположений, осознанных или неосознанных, выраженных алгоритмически или аналитически.

Мы будем, в основном, строить именно процедуры перехода и отмечать, где в них возникает «произвол» или «свобода выбора». Вопросы содержательной интерпретации сделанного выбора мы оставим в стороне, но подчеркнем, что они важны и пользуются заслуженным вниманием исследователей [1, 11, 13, 14].

Таблица 9. Выборки без пропусков, не противоречащие выборке с пропусками

Вернемся к табл. 6. Поскольку, вообще говоря, порядок следования означиваний в выборке нам не важен (вот - одно из предположений), произведем их переупорядочение, чтобы было удобнее сравнивать между собой возможные выборки. Затем посчитаем частоту встречаемости означиваний в каждой их них (табл. 9).

Поделив частоту встречаемости каждого означивания на 10 (число элементов в выборке), мы получим для каждой выборки () обученный вектор вероятностей квантов , а за счет преобразования  - обученный вектор вероятностей конъюнктов. Мы можем прибегнуть и к другим рассмотренным выше способам обучения этих векторов; главное - обученные векторы будут содержать скалярные оценки вероятностей. Мало того, они будут соответствовать непротиворечивым фрагментам знаний.

На данном этапе снова возникает возможность выбора. От совокупности векторов требуется перейти к вектору , который бы являлся результатом обучения по исходной выборке, содержащей означивания с пропущенными элементами.

Заметим, что у нас нет никаких априорных причин оказать предпочтение одним возможным выборкам вида перед другими. Если это так, то каждой из них можно сопоставить одинаковый неотрицательный вес так, чтобы сумма всех весов была равна 1. В рассматриваемом конкретном случае вес (). Воспользуемся операцией линейной комбинации за счет равенства весов в данном случае получится более того, проведя необходимые подсчеты, мы получим

Таким образом, перебрав все возможные выборки (не противоречащие исходной выборке с пропусками), предположив, что они равноценны (равновероятны), мы смогли обучить векторы и так, что у них оказались скалярные оценки. Более того, соответствующие им фрагменты знаний оказались непротиворечивыми.

У предложенной процедуры есть два очевидных недостатка. Во-первых, если пропусков много, то такая процедура, исполненная, как описано, будет вычислительно дорогостоящей: пространство возможных выборок растет экспоненциально от числа пропущенных элементов в означиваниях. Во-вторых, мы не можем быть уверены, что возможные выборки равноценны с точки зрения предметной области: ведь могут существовать какие-то факторы, которые потребуют выбрать иное распределение весов, а не равномерное, которым мы воспользовались.

Восстановление пропущенных значений

Кроме работы с возможными выборками, вполне оправданным было бы рассмотреть и альтернативный путь - каким-то образом восстановить пропущенные значения [1,11,13,14] или разумным образом подменить означивания с пропусками набором полноценных означиваний, каждому из которых приписан вес. Сумма этих весов должна быть равна весу исходного означивания с пропуском. Как мы помним, в выборке все означивания равноценны, поэтому вес каждого элемента можно посчитать равным 1 (или , где  - число элементов в выборке, если соблюсти условие нормировки).

Рассмотрим в качестве иллюстрации конкретный пример. Пусть на основе уже проанализированных означиваний из выборки, которые были без пропусков, обучен вектор вероятностей квантов

На вход поступает очередное означивание из выборки, которое содержит пропуск и имеет вид 1*. Ему не противоречат два означивания: 10 и 11.

Для замены (а значит, для восстановления пропущенного значения) поступившего 1* можно использовать означивание 11, как имеющее наибольшую вероятность. Такой подход приведет к контрастированию вероятностей элементов по принципу: растет вероятность того означивания, у которого она и так больше.

Но можно поступить иначе. Заменить 1* набором полных означиваний: внести в выборку означивание 10 с весом и означивание 11 с весом . Этот подход будет поддерживать сохранение соотношений вероятностей. Следует заметить, однако, что на получаемый результат может повлиять порядок поступления элементов обучающей выборки.

В работе были рассмотрены подходы к локальному автоматическому обучению алгебраических байесовских сетей, т.е. формированию означиваний параметров фрагмента знаний (иначе формированию численных оценок истинности конъюнктов или квантов) по выборке означиваний совокупности случайных бинарных элементов.

В случае исходных данных без пропусков на основе частотного подхода удается рассчитать скалярные оценки вероятностей. Расчет оценок может опираться либо на частотный подход, либо на подход, учитывающий не только частоту встречаемости в выборке, но и заданное априорное распределение. Формулы для обучения можно также модифицировать таким образом, чтобы оно стало адаптивным.

В случае исходной выборки с пропусками можно получить интервальные оценки вероятностей, не используя дополнительных предположений. Однако можно предложить процедуры расчетов, которые обеспечат нам получение скалярных оценок и в этом случае. Хотя часть таких процедур является адаптацией известных подходов [1,11,13-15], в целом они нуждаются в расширенном исследовании, поскольку опираются на дополнительные, зачастую неявные предположения, что требует впоследствии проверки применимости указанных процедур к конкретной ситуации.

Литература

1. Korb K.B., Nicholson A.E. Bayesian Artificial Intelligence. - New York: Chapman and Hall/CRC, 2004.

2. Тулупьев А.Л. Алгебраические байесовские сети: теоретические основы и непротиворечивость. - СПб.: СПИИРАН, 1995.

3. Тулупьев А.Л. Алгебраические байесовские сети: логико-вероятностный подход к моделированию баз знаний с неопределенностью. - СПб.: СПИИРАН, Анатолия, 2000.

4. Тулупьев А.Л. Алгебраические байесовские сети: локальный логико-вероятностный вывод. - СПб.: СПбГУ, Анатолия, 2007.

5. Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод. СПб.: СПбГУ; Анатолия, 2007.

6. Тулупьев А.Л. Байесовские сети: логико-вероятностный вывод в циклах. - СПб.: СПбГУ, 2008.

7. Тулупьев А.Л., Сироткин А.В. Байесовские и марковские сети: логико-вероятностный вывод в базах фрагментов знаний с неопределенностью // Труды научной конференции «Информационные технологии и системы - 2008». - М.: ИППИ РАН, 2008. - С. 440-456.

8. Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локальной и глобальной структуры алгебраической байесовской сети в Java-приложениях // Труды СПИИРАН. Вып.5. - СПб.: Наука, 2007. - С. 71-99.

9. Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. - СПб.: Наука, 2006.

10. Сироткин А.В., Тулупьев А.Л. Матрично-векторные уравнения локального логико-вероятностного вывода в алгебраических байесовских сетях // Труды СПИИРАН. Вып.6. - СПб.: Наука, 2008. - С. 131-149.

11. Загоруйко Н.Г. Прикладные методы анализа данных и знаний. - Новосибирск: Издательство Института математики, 1999.

12. Хованов Н.В. Анализ и синтез показателей при информационном дефиците. - СПб.: СПбГУ, 1996.

13. Allison P.D. Missing Data. - London: Sage Publications, 2001.

14. Little R.J.A., Rubin D. Statistical Analysis with Missing Data: - Wile, 2002.

15. Косовский Н.К., Тишков А.В. Логики конечнозначных предикатов на основе неравенств. - СПб.: СПбГУ, 2000.

16. Pearl J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. - San Mateo CA: Morgan Kaufmann Publications, 1994.

Размещено на Allbest.ru