Диссертация (1137435), страница 13
Текст из файла (страница 13)
У AMH есть решение тогда и только тогда, когда у SAT естьрешение.Доказательство.(⇒) Пусть – дополнительная минимальная гипотезаобучающего контекста K± . Для начала заметим, что по Утверждению 1495и Утверждению 15 назначение корректно определено. Поскольку – непустое содержание контекста K+ , из Утверждения 14 и того, что ̸=– отношение контраноминальной шкалы следует, что + = { | ∈} ∪ {¬ | ¬ ∈ }.
Теперь ++ ∩ {1 , 2 , . . . , } = ∅, отсюда длялюбого (1 ≤ ≤ ) найдется некоторый ∈ + такой, что ∈/ + . Поопределению ℐ последнее означает, что литерал принадлежит . Такимобразом ( ) = .(⇐) Пусть – булево назначение переменных и () = . Тогда = . Заметим, что + = { | ∈ } ∪ {¬ | ¬ ∈ }, потомучто ℐ̸= это отношение контраноминальной шкалы и ∩ + = ∅, 1 ≤ ≤ .Предположим, что ∈ ++ для некоторого 1 ≤ ≤ .
Это эквивалентно тому, что + ⊆ + . Следовательно, по определению отношения ℐ , несуществует литерала ∈ такого, что ∈ . Поэтому, дизъюнкция не выполнена, а это противоречит тому, что выполняет КНФ . Такимобразом ++ = и – гипотеза. Поскольку не содержит ни одного { }, оно должно содержать дополнительную минимальную гипотезу(нестрого).2Утверждение 16. MHE не может быть решена за полиномиальное от выхода время, если ̸= .Доказательство. Пусть нашелся полиномиальный от выхода алгоритм , который генерирует все минимальные гипотезы за время(|+ |, | |, |ℐ+ |, |− |, |ℐ− |, ), где – количество минимальных гипотез.По этому алгоритму построим алгоритм ′ , который выполняется первые(|+ |, | |, |ℐ+ |, |− |, |ℐ− |, + 1) шагов алгоритма . Очевидно, если существует более, чем минимальных гипотез, то ′ сделает как минимум96Рис.
4.3. ∙ - максимальные нули, ∘ - минимальные единицы(|+ |, | |, |ℐ+ |, |− |, |ℐ− |, + 1) шагов (и наоборот) – следовательно мыможем решить AMH за полимномиальное время.2Важность этого результата для вычислительных наук определяетсятем, что задача перечисления минимальных гипотез эквивалентна специальной форме задачи дуализации монотонной булевой функции на решетке.Пусть B - полная конечная решетка и - монотонная булева функция на ней. Любая полная конечная решетка изоморфна решетке понятий[54], поэтому без ограничения общности можно считать, что B это решетка понятий B(, , ) для некоторого контекста K(, , ). Тогда для, ⊆ имеет место ⊆ ⇒ ((, ′ )) ≤ ((, ′ )).
Известно, чтолюбая монотонная булева функция на решетке однозначно определяетсясвоими минимальными единицами, т.е. множеством {(, ′ ) | (, ′ ) ∈B, ((, ′ )) = 1, ((, ′ )) = 0 ∀ ⊂ }. Мы можем представить мно-97жество минимальных единиц монотонной булевой функции как множествоминимальных гипотез контекста обучения, заданного контекстами K+ иK− , где K+ = K и объектные содержания контекста K− являются в точности всеми минимальными нулями . Аналогично, контекст обучения K±определяет монотонную булеву функцию на решетке понятий контекста K+ такую, что нули – это максимальные (по включению) объектныесодержания K− (см.
рис. 2). Таким образом, мы получили следующую задачу:Задача 12. Дуализация монотонной булевой функции на решетке (MBDL1)ВХОД: Формальный контекст K и множество нулевых значений булевойфункции на решетке понятий контекста K.ВЫХОД: Множество минимальных единиц .Симметричная этой задаче будетЗадача 13. Дуализация монотонной булевой функции на решетке (MBDL2)ВХОД: Формальный контекст K и множество единичных значений булевойфункции на решетке понятий контекста K.ВЫХОД: Множество максимальных нулей .ПосколькуперечислениеминимальныхгипотезэквивалентноMBDL1, MBDL1 не может быть решена за время полиномиальное отвыхода, если ̸= .
Заметим, что в случае булевой решетки эта задачаполиномиально эквивалентна Монотонной булевой дуализации (MonotoneBoolean Dualism) (см. [49]) и минимальные гипотезы в этом случае могутбыть построены за квазиполиномиальное от выхода время ((log ) ),где – сумма размера входа и длины записи множества минимальных98гипотез.Мы уже писали, что гипотезы контекста обучения K± находятсяво взаимно-однозначном соответствии с объемами контекста K = (− ∪+ , , ℐ+ ∪ ℐ− ), которые не содержат ни одного объекта из − . Более того, минимальные гипотезы соответствуют максимальным объемам и наоборот.
Рассмотрим контексты K′ + = (, + ∪ − , + ∪ − ) и K′ − = (− , + ∪− , =− ), где + = {(, ) | (, ) ∈ + }, − = {(, ) | (, ) ∈ − },⋃︀=− ∈− (, ). Множество содержаний контекста K′ + совпадает с множеством объемов контекста K. Заметим, что контекст K′ + задает решеткуB(K′ + ) , объектные содержания контекста K′ − задают единицы некоторойбулевой функции на решетке B(K′ + ), а максимальные нули этой функции являются максимальными содережаниями контекста K′ + , которые несодержат объектных содержаний контекста K′ − .
Таким образом, задачаMBDL2 эквивалентна задаче MHE.Как мы показали выше, в случае, когда решетка B задана формальным контекстом задача MBDL трудна, поэтому разумно рассмотреть другие способы задания решеток. Второй наиболее известный способ заданиярешетки понятий – задание системы замыканий посредством набора импликаций (базисом импликаций).
В работе [62] показано, что невозможнонайти все максимальные (по включению) супремум-неразложимые элементы за полиномиальное от выхода время, если ̸= , когда система замыканий задана базисом импликаций. Если рассмотреть задачу дуализации столько одним отрицательным примером – , то мы получимУтверждение 17. В случае, когда решетка B задана базисом импликаций,MBDL2 не может быть решена за полиномиальное от выхода время, если99 ̸= .Отметим, что, если немного изменить сведение из [62], то мы получим:Утверждение 18.
В случае, когда решетка B задана базисом импликаций,MBDL1 не может быть решена за полиномиальное от выхода время, если ̸= .4.3.Распределенное обучение гипотезамЧасто бывает ситуация, когда ДСМ-гипотез слишком много (дажеминимальных), что затрудняет обучение гипотезам и последующую классификацию. Пусть есть несколько обучающих контекстов с одинаковыммножеством признаков: K1± , . . . , K± . В качестве гипотез будем использовать только те гипотезы, которые являются гипотезами в каждом из контекстов.
Формально:SharedHypotheses(K± 1 , K± 2 , . . . , K± )1 C ← AllIntents(GetClosure(·), K+ 1 , K+ 2 , . . . , K+ )2 H ← { | ∈ C , * ∀ ∈ K− 1 ∪ K− 2 ∪ . . . ∪ K− }3 Minimize(H )4 return HГде – оператор замыкания общих содержаний, а – любой алгоритм АФП поиска всех замкнутых множеств, использующий оператор замыканий (например Next Closure)Условиями применения данной модели обучения могут служить следующие ситуации:1001. Несколько исследовательских групп проводят один и тот же эксперимент.2. Несколько наборов данных с одинаковым набором признаков описывают одну и ту же задачу, но объекты отличаются по своей природе.3. Общих содержаний намного меньше, чем содержаний в каждом изположительных контекстов.Ниже приводятся результаты экспериментов по классификации токсичности химических соединений ДСМ-методом с использованием общихгипотез.
Входные данные для тестирования были взяты из материаловPredictive Toxicology Challenge и получены следующим образом:1. Обучающая выборка представляет несколько сотен химических соединений с указанием токсичности или нетоксичности каждого соединения.2. Химические соединения представлены соответствующими молекулярными графами (графами с метками вершин и ребер).3. Строятся все частые замкнутые подграфы молекулярных графов (споддержкой не ниже заданной).4.
Строятся положительный и отрицательный контексты, признакамикоторых являются частые замкнутые подграфы, а объекты - химические соединения.Всего было 4 базы данных по токсичности химических соединений({мыши, крысы} × {самки, самцы}).101support Err. Err. Mis. Mis. #Hyp. #Hyp.304,610,0 65,9 54,61324,02012,7 12,1 35,6 45,852134,01014,6 10,5 18,3 45,4104270,0516,0 10,4 15,1 45,8151389,75∙ Err. – процент ошибочной классификации при использовании общих гипотез∙ Err.
– процент ошибочной классификации при использовании классических гипотез∙ Mis. – процент неклассифицируемых объектов при использовании общих гипотез∙ Mis. - процент неклассифицируемых объектов при использовании классических гипотез∙ #Hyp. – количество минимальных общих гипотез∙ #Hyp. – среднее количество минимальных классических гипотез по 4 базам данных.Таблица 4.1.
Результаты классификации токсичности молекул.4.4.Устойчивость понятий и гипотезПодходы анализа данных использующие решетки понятий для кла-стеризации и инженерии онтологий часто встречают проблему слишкомбольшого количества понятий формального контекста. Было предложенонесколько индексов для измерения устойчивости понятий, таких как понятийная устойчивость [68, 75, 77], вероятность и разделение [66]. Индексыустойчивости использовалась во многих приложениях для выбора понятийкак бикластеров похожих объектов, например, в планировании медицинского лечения [58] или в группировании французских глаголов [45]. В [66]102авторы сравнили фильтрацию, основанную на различных индексах и их линейных комбинациях для восстановления данных. Линейные комбинациииндексов, которые показали наилучшие результаты в компьютерных экспериментах фильтрации понятий, использовали устойчивость с большимикоэффициентами.
Тем не менее, потенциальное ограничение, примененияустойчивости для больших данных это сложность ее вычисления (в [68, 75]было показано, что эта задача #P-полна). С.А. Объедков предложил [85]алгоритм для вычисления индекса устойчивости всех формальных понятий, используя решетку понятий.
Этот алгоритм был достаточно хорош впрактических применениях, но в худшем случае его сложность квадратична относительно размера решетки(которая сама может быть экспоненциальной относительно размера контекста). В этом разделе мы рассмотримзадачу приближенного подсчета устойчивости.Понятие устойчивости формального понятия впервые было былопредставлено в [68, 75] и используется в настоящее время, в слегка измененной форме из [77, 85].Определение 6. Пусть K = (, , ) – формальный контекст и (, ) –формальное понятие контекста K. Индекс (интенсиональной) устойчивости (, ), или (), определяется следующим образом: (, ) =| ⊆ | ′ = |2||Индекс экстенсиональной устойчивость определяется двойственным образом: (, ) = () =|⊆| ′′ =|.2||водит к неправильному пониманию, индексыОбычно, когда это не прииопускаются.Числитель индекса интенсиональной устойчивости (, ) = | ⊆103 | ′ = | равняется количеству генераторов формального понятия(, ), таким образом∑︁2|| =(, )(,)≤(,)и(, ) =∑︁2|| ((, ), (, )),(,)≤(,)где (, ) – это функция Мёбиуса решетки понятий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
