Диссертация (1137435), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

Неявно это отражено в алгоритме [85] для вычисления индекса устойчивости, основанного напринципе включения-исключения, как и стандартные алгоритмы вычисления функции Мёбиуса на решетке.4.5.Приближенный подсчет числа замкнутых и незамкнутыхмножествМногие задачи подсчета FCA являются #P-полными, но это не озна-чает, что они не могут быть решены приближенно.Ниже, для задачи мы будем обозначать количество решенийзадачи на соответствующем входе (который будет ясен из контекста) как |# |.Для данного гиперграфа = (, ℰ), ℰ = {1 , . .

. , }, подмножество ⊆ называется независимое множество, если * для любого1 ≤ ≤ и называетсяконезависимое множество, если * для любого 1 ≤ ≤ .Задача 14. Количество независимых множеств (#IS)ВХОД: Гиперграф .ВЫХОД: Количество независимых множеств гиперграфа 104Известно, что для задачи #IS в случае когда гиперграф являетсяобычным графом не существует FPRAS, если ̸= (см. [40]). Болеетого, несложно увидеть, что эта задача трудна даже, когда и {∅} немогут быть ребрами гиперграфа.Также нам понадобится формулировка следующей задачи:Задача 15. Количество конезависимых множеств (#CIS)ВХОД: Гиперграф = (, ℰ), ℰ = {1 , . .

. , }, ⊆ .ВЫХОД: Количество конезависимых множеств .Заметим, что множество ⊂ является независимым множествомгиперграфа = (, ℰ), ℰ = {1 , . . . , } тогда и только тогда, когда ∖является конезависимым множеством гиперграфа ′ = (, ℰ ′ ), ℰ ′ = { ∖1 , . . . , ∖ }. Следовательно, для задачи #CIS не существует FPRAS,если ̸= .Теперь мы готовы обсудить сложность задач подсчета незамкнутыхмножеств формального контекста, замкнутых и незамкнутых множеств системы замыканий заданной набором импликаций.Задача 16. Количество незамкнутых множеств (#NC)ВХОД: A Формальный контекст K = (, , )ВЫХОД: Количество множеств ⊂ таких, что ′′ ̸= Утверждение 19. Для задачи #NC не существует FPRAS, если ̸= Доказательство.

Рассмотрим произвольный вход (, ℰ), ={1 , . . . , } ℰ = {1 , . . . , } задачи #CIS. По этому входу мы построим формальный контекст K = (, , ) с объектными содержания⋃︀ми 1≤≤ ∪ { ∖ {1 }} ∪ { ∖ {2 }} ∪ . . . ∪ { ∖ { }}. Очевидно что,105множество ⊆ является конезависимым множеством гиперграфа (, ℰ),если и только если ′′ ̸= или = для контекста K. Следовательно|#| = |# | + 1.2Задача 17. Количество замкнутых множеств базиса импликаций (#J )ВХОД: Базис импликаций J = {1 → 1 , . . . , → }, , ⊆ ВЫХОД: Колчиство замкнутых множеств базиса J.Утверждение 20. Для задачи #J не существует FPRAS, если ̸= Доказательство. Рассмотрим произвольный вход (, ℰ), ℰ={1 , . . .

, } задачи #IS. По этому входу построим базис импликацийJ = {1 → , . . . , → } (импликации определены на множестве ).Очевидно, множество является независимым множеством гиперграфа(, ℰ), если и только, если – замкнуто в базисе J и ̸= . Следовательно |#| = |#J | − 12Поскольку замкнутое множество по отношению к базису может бытьпредставлено как выполняющий набор соответствующей Хорновской КНФ,мы получаемСледствие1. Для задачи подсчета числа решений ХорновскойКНФ(# ) не существует FPRAS, если ̸= Задача 18.

Количество незамкнутых множеств базиса импликаций (# J )ВХОД: Базис импликаций J = {1 → 1 , . . . , → }, , ⊆ ВЫХОД: Количество незамкнутых множеств базиса J.Утверждение 21. Для задачи # J существует FPRASДоказательство. Рассмотрим вход J = {1 → 1 , . . . , → }, , ⊆ задачи # J . Замкнутые множества базиса имплика-106ций J находятся во взаимно однозначном соответствии с выполняющиминаборами соответствующей Хорновской КНФ J .

Следовательно незамкнутые множества J находятся во взаимно однозначном соответствии с выполняющими наборами ДНФ ¬J . Для задачи подсчета числа решений ДНФ2известен FPRAS [83].Стоит отметить, что сложность приближенного подсчета замкнутыхмножеств неизвестна, но известно, что эта задача полна в классе #Π1[40]. Все вышесказанные результаты приведены в следующей таблице .#closed sets#nonclosed sets(K)#Π1 -complete̸ ∃ FPRAS, если ̸= (J)̸ ∃ FPRAS, если ̸= FPRASТаблица 4.2. Сложность подсчета замкнутых и незамкнутых множеств.(K) означает случай, когда система замыканий задана контекстом K.(J) означает случай, когда система замыканий задана базисом импликаций J.4.6.Индекс вероятностной устойчивостиИзвестно, что задача подсчета индекса устойчивости формальногопонятия #P-полна.

Более того, из результатов предыдущего раздела следует, что для этой задачи не существует FPRAS, если ̸= . Последнее означает, что индекс устойчивости нельзя приблизить за полиномиальное в среднем время с полиномиально ограниченной относительнойпогрешностью (если ̸= ). Чтобы это доказать, достаточно рассмот-107реть формальный контекст из доказательства Утверждения 19. Очевидно ( ) = (|# | + 1)/2| | . Поскольку приближенный подсчет индексаустойчивости с ограниченной относительной погрешностью за полиномиальное время невозможен, если ̸= и все известные алгоритмы точного подсчета индекса устойчивости, сразу для всех понятий, квадратичныот размера решетки, то далее мы сфокусируемся на том как аппроксимировать индекс устойчивости с ограниченной абсолютной погрешностью.По определению, индекс устойчивости содержания формальногоконтекста K = (, , ) равен вероятности того, что замыкание случайного подмножества равно , т.е.

() = ( ′′ = ), когда выбранослучайно и равномерно из 2 . Таким образом чтобы оценить () мы можем использовать метод Монте-Карло.Определим модель вероятностной устойчивости формального понятия, следующим образом:Определение 7 (Индекс вероятностной устойчивости). () =∑︀=1 (),где () – независимые и одинаково распределенные случайные величины,определяемые как: () =⎧⎪⎪⎨1, если ′′ = ;⎪⎪⎩0, если ′′ ̸= ;Когда ⊆ выбрано случайно и равномерноДля вычисления вероятностного индекса устойчивости () используем метод Монте-Карло:108GetStability(, )1 answer ← 02 for ← 1 to 34do Выбрать случайное подмножество ⊆ if ′′ = 5then answer ← answer +16 answer ←answer7 return answerНапомним теорему Чернова (Chernoff-Hoeffding) с упрощеннымиоценками[83], которая формулируется следующим образомТеорема 8 (Chernoff-Hoeffding).

Пусть 1 , 2 , . . . , – независимые и одинаково распределенные случайные величины с = ( ). Тогда1 ∑︁ ( ≤ − ) ≤ exp (−22 )Не сложно получить следующее утверждение, которое говорит, чтодля достаточно больших = (, ), вероятность | answer −()| ≥ небольше чем .Утверждение 22. Метод Монте-Карло аппроксимирует () с вероятностью не меньше 1 − и абсолютной погрешностью при условии, что>21ln22 Доказательство. Если мы возмем случайные величины равные 1 − , и подставим их в неравенство из теоремы Chernoff-Hoeffding, то =(1 − ) и мы получим (1 ∑︁ ≥ + ) ≤ exp (−22 ).109Следовательно1 ∑︁ − | ≥ ) ≤1 ∑︁1 ∑︁≤ ( ≤ − ) + ( ≥ + ) ≤ (|≤ 2 exp (−22 ).Рассмотрим случайные величины такие, что = 1, если и только если ′′ = на -ой итерации GetStability и = 0 иначе.

Та∑︀ким образом 1 = answer , где answer было возвращено функциейGetStability(A,N) на -ой итерации. Вероятность абсолютной ошибкиудовлетворяет (| answer −| ≥ ) ≤ 2 exp (−22 ) ≤ . Следовательно222 ≥ ln 2 .Мы можем использовать этот алгоритм, чтобы получить почти всеустойчивые понятия. Ниже псевдокод алгоритма для вычисления топаустойчивых понятийTopStableConcepts(K, 0 )1 answer ← ∅2 for каждого понятия = (, ′ ) контекста K34do if approxStability() > then answer ← answer ∪{(, ′ )}5 return answer4.7.Анализ результатов вычислений индекса вероятностнойустойчивостиВ этом разделе мы обсудим эксперементальные результаты вычисле-ния устойчивости понятий случайных формальных контекстов разных раз-110меров и плотности. Результаты приближенного вычисления устойчивостиприведены на графиках 1 и 2. Ось (помеченная как Error ) соответствуетотносительной ошибке|(K, ˜ , )∆(K, , )|/|(K, , )|.Здесь (K, , ) обозначает множество всех понятий с устойчивостью ≥ ; (K, ˜ , ) обозначает множество всех понятий с приближеннойустойчивостью ˜ ≥ , где – параметр (порог устойчивости).

Для каждой пары ∈ , ∈ случайного контекста K = (, , ) с вероятностью (называемой плотностью контекста выполнено (, ) ∈ .Рис. 4.4. Качество аппроксимации на случайном контексте 100 × 30 с плотностью 0.3111Рис. 4.5. Качество аппроксимации на случайном контексте 150 × 30 с плотностью 0.3Результаты экспериментов показывают, что индекс вероятностнойустойчивости имеет лучшую точность, когда граница устойчивости ниже.Такое поведение индекса, объясняется тем, что, когда порог устойчивости высокий количество устойчивых понятий невелико и небольшие отклонения от от этого порога могут приводить к значительному увеличению”устойчивых” понятий.

(т.е. понятий с приближенной устойчивостью больше чем порог).4.8.Устойчивые гипотезы: Результаты экспериментов с данны­ми по токсичности химических соединенийПриведем результаты экспериментов классификации токсичности хи-мических соединений на данных, которые мы использовали для тестирования распределенного обучения гипотезам в разделе 4.3. В данном тестировании для классификации мы выбирали только устойчивые гипотезы.112Гипотеза считалась устойчивой, если ее индекс вероятностной устойчивости 50 в соответствующем контексте (положительном, для положительнойгипотезы и отрицательном, для отрицательной гипотезы) больше заданного порога 0.65.support Err.

Характеристики

Список файлов диссертации