Диссертация (1137435), страница 9
Текст из файла (страница 9)
Существование такого алгоритма означает, что задача распознавания псевдосодержания лежит в . Ранее мыпоказали, что эта задача -полна, поэтому, если существует полиномиальный алгоритм для RSP, то = . Следовательно мы доказали:Утверждение 6. Не существует полиномиального алгоритма для генерации случайного псевдосодержания, если ̸= .Известно, что задача подсчета псевдосодержаний #P-турдна [76],тем не мене многие #P-трудные задачи могут быть решены приближенно.
Таким приближенные алгоритмы называются FPRAS (fully polynomialrandomized approximation scheme) [59]. С другой стороны, FPAUS (fullypolynomial almost uniform sampling) [59] – задача генерации случайного элемента (количество которых FPRAS оценивает) с распределением -близкимравномерному, с временной сложностью зависящей от как полином отlog −1 . В [59] было показано, что существование FPRAS эквивалентносуществованию FPAUS. Таким образом, из Утверждения 6 следует, чтодля случайно генерации псевдосодержания не существует FPAUS, если ̸= Утверждение 7. Не существует FPRAS для подсчета псевдосодержаний,если ̸= .602.7.Базис импликаций с двухэлементными посылкамиПоскольку задача поиска минимального базиса импликаций полино-миально эквивалентна задаче разрешения совпадения систем замыканийзаданного контекста K = (, , ) и набора импликаций , то возникаетвопрос как решать данную задачу разрешения для некоторых частных случаев базисов импликаций.
Так например, если все посылки импликаций из одноэлементные, то задает дистрибутивную решетку и данная задачарешается за полиномиальное время, поскольку для контекста задающего дистрибутивную решетку минимальный базиc импликаций может бытьнайден за линейное от выхода время [57]. Оказывается, что, если ограничиться только базисами , у которых все посылки мощности не большедвух, то это ограничение никак не упрощает данную задачу разрешения.Задача 8. Эквивалентность систем замыканий (CSEQ)ВХОД: Формальный контекст K = (, , ) и набор импликаций .ВОПРОС: Совпадают ли системы замыканий контекста K и набора импликаций ?Задача 9. Эквивалентность систем замыканий, когда у импликаций посылки мощности не больше двух (CSEQ2)ВХОД: Формальный контекст K = (, , ) и набор импликаций такой,что ∀ → ∈ выполнено | | ≤ 2.ВОПРОС: Совпадают ли системы замыканий контекста K и набора импликаций ?Теорема 2.
CSEQ и CSEQ2 полиномиально эквивалентны.Доказательство.61Очевидно, что CSEQ2 полиномиально сводима к CSEQ (т.к. являетсячастным случаем). Покажем полиномиальную сводимость CSEQ к CSEQ2.По контексту K = (, , ) и набору импликаций мы построим новыйконтекст K = ( , , ) и новый набор импликаций . Для каждойимпликации → ∈ , где = {1 , 2 , . . .
, } добавим в импликации {1 , 2 } → {2 }, {3 , 2 } → {3 }, . . . , { , −1 } → { }, а также{ → } и {2 } → {1 , 2 }, {3 } → {1 , 2 , 3 }, . . . , { } → {1 , . . . , }.⋃︀| |Таким образом = ∪ → ∈ {2 , 3 , . . . , }. Контекст K строится из контекста K таким образом, чтобы все его объектные содержанияудовлетворяли всем новым импликациям из . А именно: если для какойто импликации → ∈ , где = {1 , 2 , . .
. , } и какого-то ∈ выполнено, что {1 , 2 , . . . , } ⊆ ′ ( ′ в контексте K и ≤ ), то в ′ добавляется признак . Нужно доказать, что системы замыканий, заданныеK и , равны тогда и только тогда, когда равны системы замыканий K и . Для произвольного подмножества ⊆ будем обозначать множество ∪ { | → ∈ , {1 , . .
. , } ⊆ , = {1 , . . . , }} как (). Несложно проверить, что множество ⊆ замкнуто в тогда и толькотогда, когда () замкнуто в . Более того, если ⊆ замкнуто в ,то = ( ∩ ). Следовательно, отображение () : → задаетбиекцию между замкнутыми множествами и . Аналогично отображение () : → задает биекцию между замкнутыми множествамиконтекстов K и K .2.Заметим, что последнее сведение похоже на хорошо известное сведение SAT к 3-SAT, это объясняется тем, что замкнутые множества набораимпликаций соответствуют выполняющим наборам соответствующей Хор-62новской КНФ.2.8.Приближенный базис импликацийПоскольку вычисление точного базиса импликаций, скорее всего, яв-ляется вычислительно трудной задачей целесообразно рассмотреть новуюмодель базиса импликаций, позволяющую производить более эффективноевычисление:Определение 1.
Набор импликаций называется приближенным базисомформального контекста K, если для случайно и равномерно выбранногоподмножества ⊆ , ( ′′ = ) > 1 − .Преимущества предложенной модели по сравнению с точным базисом:∙ Существенно меньшее количество импликаций∙ Существенно более быстрое время построения, которое линейно от−1∙ Высокая точность приближения (1 − )Как мы увидим далее этот базис не только может быть построен намного быстрее, чем минимальный базис импликаций, но и содержит значительно меньшее количество импликаций.Алгоритм построения приближенного базиса импликаций основывается на результатах из [28].
Ниже приводится псевдокод алгоритма построения приближенного базиса импликаций:63UpdateBase(K, , )1 for each → ∈ 2do if * And ( ∩ )′′ ̸= ∩ then заменить в импликацию → 34на ∩ → ( ∩ )′′5return J6 ← ∪ { ← ′′ }7 return JApproximateImplicationBase(K, )1 J ←∅2 for ← 1 to 34do выбрать случайное замкнутое множество базиса if ′′ ̸= then J ← UpdateBase(K, , )56 return JЕсли сложность вычисления случайного замкнутого множества равна(()), то сложность работы этого алгоритма равна ( · () + · | | ·||| |), где приближенный базис, который нашел этот алгоритм после итераций.Отметим, что самая “сложная” часть этого алгоритма это выбор случайного замкнутого подмножества в базисе .
В разделе 4.6 данной работыдоказано, что эта задача не может быть решена за полиномиальное время,если ̸= . Не смотря на сложность этой задачи использование следующего алгоритма показало хорошие результаты на практических данных.64GenerateRandomClosedSet()1 X ← random subset of 2 X ← (, )3 return XЗдесь LinClosure – линейный алгоритм вычисления замыкания в базисеимпликаций (см.
[19, 90]).Длятого,чтобыоценитьдопустим,времячтоработыоператорыалгоритмазамыканияприближенного базиса и формального контекста K при выборе случайного подмножества ⊆ не совпадают с вероятностью как минимум (т.е. ( ̸= ′′ ) ≥ ). Тогда в среднем придется сделать не более −1(математическое ожидание геометрической случайной величины) шагов,пока не встретится подмножество ⊆ , на котором операторы замыкания не совпадают. Последнее означает, что, если операторы замыкания несовпадают с вероятностью больше , то математическое ожидание количества последовательных шагов алгоритма между вызовами функции не больше −1 .
Таким образом, мыполучили:Теорема3. Математическое ожидание времени работы алгоритма, до достижения точности 1− для контекстаK = (, , ), равно (| || | · (||| | + | || |) · −1 ), где – минимальный базис импликаций.Отметим, что на реальных данных ситуация, когда базис не обновляется в течении долгого времени возникает довольно быстро. Последнееозначает, что с большой вероятностью алгоритм быстро нашел небольшой65приближенный базис с маленьким (см.
результаты экспериментов).2.8.1.Результаты экспериментовПриведем результаты экспериментов вычисления приближенного базиса на реальных данных: базы данных Chess, Zoo и P.-Op. P (Post operativePatients) взяты с хранилища данных UCI [100]. База данных Grav. представляет описание британских гравюр из коллекции ГМИИ им. А.С. Пушкина. База данных Grav_a состоит из описаний гравюр для каждого конкретного автора и получена из базы данных Grav.||| |̂︁7643,10,998859528433,30,9999 1,8539025855,00,9989Grav70747353233,4 0,9999 3129Grav_a70715639286,6 0,9999 92,05база данных||| | | |Chess319739Zoo101P.-Op. P.2,06Таблица 2.2.
Результаты вычисления приближенного базиса.∙ – приближенный базис импликаций∙ – точный базис импликаций̂︁ – оценка вероятности ( ′′ = ) того, что для случайного∙ подмножества ⊆ замыкания совпадают∙ – время построения точного базиса алгоритмом Гантера∙ – время построения приближенного базиса66Как видно на практических данных приближенный базис дает намного более сжатое представление данных и требует меньшее время построения, чем минимальный базис импликаций. Несмотря на это оценкавероятности совпадения операторов замыкания приближенного базиса иформального контекста остается очень высокой.673.
Базисы импликаций и общие содержания3.1.Связь базиса импликаций с общими содержаниямиПусть даны два формальных контекста с общим множеством призна-ков: K1 = (1 , , 1 ) с базисом импликаций (не обязательно минимальным) J1 и контекст K2 = (2 , , 2 ) с базисом импликаций J2 . Очевидно,что множество их общих содержаний является системой замыканий [54].Поэтому мы можем рассмотреть контекст K = (, , ), объектные содержания, которого будут неразложимыми элементами системы замыканий общих содержаний. Будем называть контекст K, контекстом общихсодержаний. Рассмотрим набор импликаций J = J1 ∪ J2 . Ясно, что, есликакое-то подмножество замкнуто в контексте K1 , то оно удовлетворяет всемимпликациям из J1 , аналогично для K2 и J2 .
Таким образом, любое общеесодержание будет удовлетворять всем импликациям из J. В обратную сторону – пусть какое-то множество удовлетворяет всем импликациям из J,тогда оно будет замкнуто в базисе J1 и замкнуто в базисе J2 и следовательно будет общим содержанием. Такие же рассуждения можно обобщить наслучай нескольких контекстов, получая следующий важный результат:Теорема 4.
Пусть даны контексты K1 , K2 , . . . , K с общим множеством признаков и с базисами импликаций J1 , J2 , . . . , J , соответственно. Тогдамножество импликаций J1 ∪ J2 ∪ . . . J будет базисом импликаций контекста общих содержаний.683.2.Общий метод поиска минимального базиса импликаций через общие содержанияИспользуя теорему 4, можно предложить следующий общий алгоритмпостроения минимального базиса импликаций.FindMinBase(K = (, , ))1 Представить контекст K множеством контекстов K1 , K2 , . . . , K ,для которых K будет являться контекстом общих содержаний2 Для каждого контекста K найти минимальный базис импликаций J .3 J ← J1 ∪ J2 ∪ .
. . ∪ J4 J ← ()5 return JЗаметим, что шаг 1, является ключевым шагом этого алгоритма. Желательно реализовать этот шаг так, чтобы:1. Для каждого из контекстов K существует эффективный алгоритмпоиска минимального базиса.2. Суммарный размер базисов контекстов K не сильно больше (например в полиномиальное число раз) размера базиса контекста K.3.2.1.Поиск собственных посылок через общие содержанияВ статье [37] был предложен квазиполиномиальный алгоритм для поиска всех собственных посылок формального контекста. Собственные посылки задают базис импликаций (левые части импликаций будут собственными посылками, а правые их замыканиями).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
