авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 |
-- [ Страница 1 ] --

ПРАВИТЕЛЬСТВО РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное учреждение

высшего профессионального образования

НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ

УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

На правах рукописи

БАБИН

Михаил Александрович

МОДЕЛИ, МЕТОДЫ И КОМПЛЕКСЫ ПРОГРАММ

ПОСТРОЕНИЯ ЗАВИСИМОСТЕЙ, ОСНОВАННЫЕ НА

РЕШЕТКАХ ЗАМКНУТЫХ МНОЖЕСТВ Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ Диссертация на соискание учной степени е кандидата физико-математических наук

Научный руководитель доктор физико-математических наук C. О. Кузнецов Москва Оглавление Введение 1 Построение зависимостей в данных с помощью решеток замкнутых множеств: основные понятия и состояние пред­ метной области 1.1 Основные определения...................... 1.1.1 Частично упорядоченные множества и решетки... 1.1.2 Анализ формальных понятий.............. 1.1.3 Теория алгоритмов и вычислительная сложность... 1.2 Модели зависимостей и их вычисление............ 1.3 Минимальная модель знаний о предметной области: мини мальный базис импликаций................... 1.4 Задачи и алгоритмы построения гипотез........... 2 Базисы импликаций и функциональных зависимостей 2.1 Квазизамкнутые множества и псевдосодержания....... 2.2 Структура минимальных базисов импликаций........ 2.3 Функциональные зависимости и импликации......... 2.4 Распознавание псевдосодержаний................ 2.5 Лектически максимальные псевдосодержания и перечисле ние максимальных псевдосодержаний............. 2.6 Распознавание существенных содержаний........... 2.6.1 Посылка импликации из минимального базиса.... 2.7 Базис импликаций с двухэлементными посылками...... 2.8 Приближенный базис импликаций............... 2.8.1 Результаты экспериментов................ 3 Базисы импликаций и общие содержания 3.1 Связь базиса импликаций с общими содержаниями..... 3.2 Общий метод поиска минимального базиса импликаций через общие содержания........................ 3.2.1 Поиск собственных посылок через общие содержания 3.3 Интенсионально связанные понятия..

............ 3.4 Понятия с общими содержаниями............... 3.5 Сцепления и общие содержания................ 4 Обучение гипотезам 4.1 Теоретико-решеточная интерпретация гипотез и классифика ции................................. 4.2 Перечисление гипотез и дуализация монотонных булевых функций на решетках...................... 4.3 Распределенное обучение гипотезам.............. 4.4 Устойчивость понятий и гипотез................ 4.5 Приближенный подсчет числа замкнутых и незамкнутых множеств............................. 4.6 Индекс вероятностной устойчивости.............. 4.7 Анализ результатов вычислений индекса вероятностной устойчивости........................... 4.8 Устойчивые гипотезы: Результаты экспериментов с данными по токсичности химических соединений............ 5 Комплекс программ 5.1 Программный комплекс Cordiet................ 5.2 Программная реализация построения базисов импликаций. 5.3 Программная реализация алгоритма вычисления оператора замыкания общих содержаний................. 5.4 Программная реализация распределенного обучения гипотезам Заключение Литература Приложения 5.5 Приложение 1.1.......................... 5.6 Приложение 1.2.......................... 5.7 Приложение 1.3.......................... 5.8 Приложение 1.4.......................... 5.9 Приложение 1.5.......................... 5.10 Приложение 1.6.......................... 5.11 Приложение 2.1.......................... 5.12 Приложение 3.1.......................... Введение Актуальность работы. Стремительный рост объема данных раз ной природы, наблюдающийся в последние десятилетия, приводит к необ ходимости разработки эффективных методов их автоматического и интер активного анализа. Одной из распространенных математических моделей, позволяющих описывать методы и алгоритмы анализа данных, является анализ формальных понятий.

Анализ формальных понятий (АФП) является ветвью прикладной алгебраической теории решеток, широко используемой для описания мето дов анализа данных. АФП предлагает средства моделирования онтологий и таксономий предметных областей на основе решеток понятий, а также модели точных и приближенных зависимостей в данных.

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

Модели импликативных зависимостей, позволяющие более сжатое представление и эффективную алгоритмическую реализацию Эффективные алгоритмы порождения приближенных базисов им пликаций, множества минимальных ДСМ-гипотез Эффективные алгоритмы распознавания псевдосодержаний, задаю щих оптимальный базис импликаций Модели оценивания импликативных зависимостей и эффективное вы числение оценок этих зависимостей Так например, сложность распознавания псевдосодержаний, задаю щих оптимальный базис зависимостей (импликаций) была одной из основ ных открытых задач АФП на протяжении многих лет (список открытых задач АФП [89] задачи 2,8,9).

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

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

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

Научная новизна. В диссертации получены следующие основные новые научные результаты, которые выносятся на защиту:

1. Доказана трудноразрешимость задач, связанных с вычислением классического минимального базиса импликаций.

2. Предложена новая модель приближенного базиса импликаций фор мального контекста, алгоритм его вычисления и эффективная про граммная реализация.

3. Доказана трудноразрешимость вычисления минимальных гипотез в стандартной постановке 4. Предложена и экспериментально проверена модель распределенного обучения гипотезам – импликативным зависимостям для задачи ма шинного обучения.

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

6. Предложена и экспериментально проверена модель оценивания гипо тез и формальных понятий – вероятностный индекс устойчивости.

7. Теоретически и экспериментально исследована сложность вычисле ния вероятностного индекса устойчивости, предложен эффективный алгоритм и его программная реализация.

8. Решены давно сформулированные и остававшиеся открытыми задачи создания эффективных алгоритмов и оценки вычислительной слож ности распознавания псевдосодержаний и существенных содержаний.

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

10. Разработан комплекс программ, реализующий предложенные алго ритмы, который был встроен в коллективно разрабатываемый в От делении прикладной математики и информатики НИУ ВШЭ ком плекс программ.

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

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

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

Апробация результатов работы. Основные результаты работы докладывались и обсуждались на следующих научных конференциях:

1. 8-ой международной конференции по анализу формальных понятий (8th International Conference on Formal Concept Analysis), Агадир, Ма рокко, 2010.

2. 7-ой международной конференции по решеткам понятий и их прило жениям (7th International Confere6nce on Concept Lattices and Their Applications), Севилья, Испания, 2010. [Награда за лучшую ста­ тью] 3. 9-ой международной конференции по анализу формальных понятий (9th International Conference on Formal Concept Analysis), Никосия, Кипр, 2011.

4. 10-ой международной конференции по анализу формальных поня тий (8th International Conference on Formal Concept Analysis), Лёвен, Бельгия, 2012.

Публикации. Основные результаты работы изложены в 6 научных статьях из которых 4 опубликованы в рецензируемых трудах международ ных конференций (индексируемыми системами Web of Science и Scopus) и 2 опубликованы в журналах из списка ВАК. Также 1 статья принята к публикации в международный рецензируемый журнал.

1. Построение зависимостей в данных с помощью решеток замкнутых множеств: основные понятия и состояние предметной области 1.1. Основные определения 1.1.1. Частично упорядоченные множества и решетки Определение 1.1. Бинарное отношение на некотором множестве на зывается отношением (нестрогого) частичного порядка, если для,, :

1. (рефлексивность);

2. Если и, то = (антисимметричность);

3. Если и, то (транзитивность).

Множество S с определённым на нем отношением частичного порядка (частично упорядоченное множество) обозначается (, ). Если, то говорят, что элемент меньше, чем или равен ему. Если для не существует, такого что, то называют максимальным элементом (относительно ).

Если и =, то пишут и говорят, что строго меньше, чем.

Определение 1.2. Пусть (, ) частично упорядоченное множество. Эле мент называется соседом снизу элемента, если и ( ). В этом случае называется соседом сверху (обо значается ). Направленный граф отношения называется графом покрытия.

Графически конечное частично упорядоченное множество (, ) мо жет быть представлено с помощью диаграммы Хассе (или просто диаграм­ мы [4]). Элементы изображаются в виде точек. Если, то размеща ется “над” (вертикальная координата больше вертикальной координаты ), и две точки соединяются линией.

Определение 1.3. Верхней гранью подмножества в упорядоченном множестве называется элемент, такой что для всех.

Точная верхняя грань множества (называемая также наименьшей верх­ ней гранью или супремумом) множества (обозначается sup) есть верх няя грань такая, что 1 для любой верхней грани 1 подмножества.

Двойственным образом (с заменой на ) определяется понятие точной (наибольшей) нижней грани или инфимума inf.

Определение 1.4. Бинарная операция : называется полуре­ шёточной, если для некоторого и любых,, :

1. = (идемпотентность);

2. = (коммутативность);

3. ( ) = ( ) (ассоциативность);

4. =.

Для = {1,..., } и N мы пишем вместо 1....

Если = {}, то =.

Определение 1.5. Множество с определённой на нем полурешёточной операцией называется полурешёткой (, ).

Полурешёточная операция задает два частичных порядка и на (, ):

= и =.

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

Определение 1.6. Пусть (, ) — полурешётка. Множество на зывается системой замыканий[54] или семейством Мура[4] (относительно ), если, ( ).

Очевидно, что система замыканий (относительно ) с определённой на ней операцией, : и =, образует полурешётку.

Определение 1.7. Упорядоченное множество (, ) с определёнными на нем полурешёточными операциями и называется решёткой, если (, ) и (, ) являются, соответственно, нижней и верхней полурешётками (от носительно ).

Операции и называют операциями взятия точной нижней и верхней грани в решётке или инфимума и супремума, соответственно.

Определение 1.8. Подрешёткой решётки называется подмножество такое, что если,, то и.

Полурешёточные операции и удовлетворяют в решётках следую щему условию: ( ) = ( ) = (поглощение).

Из любой конечной полурешётки можно получить решётку добав лением одного (максимального или минимального в зависимости от типа полурешетки) элемента.

Решётка называется полной, если у каждого подмножества его эле ментов есть супремум и инфимум (всякая конечная решётка является пол ной).

Определение 1.9. Интервал [, ] состоит из всех элементов, ко торые удовлетворяют неравенствам. Порядковым фильтром (идеалом) решётки называется подмножество такое, что если, и, то (соответственно,, и, то ).

Элемент решётки называется инфимум-неразложимым или -неразложимым (или неразложимым в пересечение), если для любых = и =, не выполняется =. Элемент решётки называет ся супремум-неразложимым или -неразложимым (или неразложимым в объединение), если для любых = и =, не выполняется =.

Подмножество полной решётки называется инфимум-плотным, если = { | }, и супремум-плотным, если = { | }).

Определение 1.10. Пусть (, ) и (, ) — частично упорядоченные множества. Пара отображений : и : называется соответ­ ствием Галуа между частично упорядоченными множествами (, ) и (, ), если для любых и :

1. 1 2 (2 ) (1 );

2. 1 2 (2 ) (1 );

3. (()) и (()).

Приведённые условия эквивалентны одному: () () [4, 54].

1.1.2. Анализ формальных понятий Определение 1.11. Формальный контекст K есть тройка (,, ), где – конечное множество, называемое множеством объектов, – конечное множество, называемое множеством признаков, – бинарное отношение.

Отношение интерпретируется следующим образом: для, имеет место, если объект обладает признаком.

Для формального контекста K = (,, ) и произвольных и определена пара отображений:

:= { | для всех }, := { | для всех }, которые задают соответствие Галуа между частично упорядоченными множествами (2, ) и (2, ), а оператор (·) является оператором за­ мыкания на — дизъюнктном объединении и, т.е. для произ вольного или имеют место следующие соотношения [54]:

1. (экстенсивность), 2. = (идемпотентность), 3. если, то (изотонность).

Множество называется замкнутым, если = [54].

Определение 1.12. Формальное понятие формального контекста K = (,, ) есть пара (, ), где,, = и =. Множество называется объёмом, а — содержанием понятия (, ).

Очевидно, что объем и содержание произвольного формального по нятия являются замкнутыми множествами.

Множество формальных понятий контекста K, которое мы будем обо значать посредством B(,, ), частично упорядочено по вложению объ ёмов: формальное понятие = (, ) является менее общим (более част­ ным), чем понятие = (, ), (, ) (, ), если, что эквива лентно ( — обобщение ).

Подмножества произвольного множества, замкнутые относительно заданной на нем операции замыкания, образуют полную решётку [4, 54].

Множество всех понятий формального контекста K образует полную ре шётку [54].

Определение 1.13. Множество понятий контекста B(,, ) образует решётку B(,, ) := (B(,, ),, ), где (1, 1 ) (2, 2 ) = ( 2, (1 2 ) ). и (1, 1 ) (2, 2 ) = ((1 2 ), 1 2 ). Такие решётки называют решётками понятий или решётками Галуа[54].

Любая полная решётка изоморфна решётке понятий некоторого формального контекста [54]. В качестве объектов этого контекста нуж но выбрать -неразложимые элементы, а в качестве признаков — неразложимые элементы исходной решётки. Тогда объект в контексте будет обладать признаком, если элемент решётки, соответствующий, находится “под” элементом, соответствующим.

Определение 1.14. Строчно- (столбцево-)редуцированным называется такой формальный контекст, в котором всякое объектное (признаковое) понятие является -неразложимым (-неразложимым). Редуцированным называется формальный контекст, являющийся одновременно строчно- и столбцево-редуцированным.

Определение 1.15. Пусть дан K = (,, ) — формальный контекст и,, тогда выражение называется импликацией (на мно­ жествах признаков), если (или ), т.е. все объекты из, обладающие множеством признаков, обладают также множеством при знаков.

Аналогичным образом определяются импликации на множествах объ ектов. Наличие импликации в контексте K соответствует тому, что в диаграмме решётки B(K) формальное понятие (, ) находится ниже формального понятия (, ).

Импликации формального контекста удовлетворяют аксиомам Арм стронга [54] для произвольных,, :

1. ;

2. Если то ;

3. Если и то.

Помимо определённых выше однозначных (one-valued) формаль ных контекстов в анализе формальных понятий изучаются многозначные (many-valued) контексты:

Определение 1.16. Многозначный формальный контекст есть четвёрка (,,, ), где,, — множества (объектов, признаков и значений признаков, соответственно), а — тернарное отношение, задающее значение признака, причём:

(,, ) и (,, ) влечёт = Многозначные признаки могут рассматриваться как отображения, таким образом, можно обозначать () = вместо (,, ).

Процедура сведения многозначных контекстов к однозначным назы вается шкалированием (scaling). Для шкалирования каждый признак мно гозначного контекста представляется формальным контекстом, называе мым шкалой.

Определение 1.17. Шкала для признака многозначного контекста (,,, ) есть (однозначный) контекст S := (,, ) такой, что (). Объекты в шкале называются значениями шкалы, а признаки — признаками шкалы.

В нашей работе для построения таксономии алгоритмов использова лось два варианта шкалирования — порядковое шкалирование и номиналь­ ное шкалирование. Порядковая шкала O := (,, ) используется для признаков, значения которых упорядочены относительно некоторого по рядка, а обладание объектом некоторым значением признака влечёт об ладание всеми меньшими значениями признака. С помощью номинальной шкалы O := (,, =) представляют несравнимые между собой значения признаков, например, цвет.

Возможные виды шкалирования рассмотрены в [54].

1.1.3. Теория алгоритмов и вычислительная сложность Употребляя понятия из данного раздела мы будем использовать опре деления из книги [55] и ее русского перевода [8].

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

(1) общим списком всех ее параметров (2) формулировкой тех свойств, которым должен удовлетворять от­ вет или, другими словами, решение задачи.

Индивидуальная задача получается из массовой задачи, если всем параметрам задачи присвоить конкретные значения.

Теория NP-полных задач строится только для задач разрешения свойств (decision problems). Такие задачи имеют только два возможных решения - “да” или “нет”. Более формально, задача разрешения состоит просто из двух множеств: множества всех возможных индивидуальных задач (instances, в дальнейшем в формулировках задач, называемых для краткости входами) и множества индивидуальных задач с отве том “да” (yes-instances). Стандартная форма для описания задач состоит из двух частей. В первой части дается описание условия задачи, а во второй части в терминах условия формулируется вопрос, предполагающий один из двух ответов - да или нет. Следуя традиции, мы будем писать слова УСЛОВИЕ и ВОПРОС строчными буквами.

Индивидуальная задача принадлежит в том и только том случае, когда она может быть получена из стандартной формы описания подста новкой конкретных значений во все компоненты условия. Индивидуальная задача принадлежит в том и только том случае, когда ответом на вопрос задачи будет “да”. Задачи разрешения могут быть формально представле ны в виде языков. Для любого конечного множества символов через * обозначается множество всех конечных цепочек (слов), составленных из символов алфавита. Произвольное подмножество * называется языком в алфавите.

Соответствие между задачами разрешения и языками устанавлива ется с помощью схем кодирования (encoding schemes). Для данной задачи, схема кодирования описывает каждую индивидуальную задачу из подходящим словом в некотором фиксированном алфавите. Таким обра зом, задача и ее схема кодирования разбивают множество * на три класса: слова, не являющиеся кодами индивидуальных задач из, слова, являющиеся кодами индивидуальных задач из с ответом “нет"на вопрос и слова, являющиеся кодами индивидуальных задач из с ответом “да".

Третий класс слов и есть язык [, ], ставящийся в соответствие задаче при кодировании. С каждой задачей разрешения связана не завися щая от схемы кодирования формальная мера длины (размера) входа (input length). Она определяется как функция Length: Z+, которая при любой “разумной схеме кодирования” (подразумевающей “естественную краткость” или экспоненциальную несжимаемость и “декодируемость”, об суждение этих понятий можно найти в [8]) полиномиально эквивалентна длине кода индивидуальной задачи, т.е. существуют два полинома и такие, что если есть индивидуальная задача из и слово есть код при кодировании, то Length[] (||) и || ([]), где || длина слова.

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

Класс полиномиально вычислимых функций P определяется как мно жество языков:

= {: существует полиномиальная ДМТ-программа для кото рой = }.

Для определения классов NP и #P, которые мы будем использовать в дальнейшем, используется понятие недетерминированной машины Тью­ ринга (НДМТ), которая состоит из двух модулей: обычной ДМТ и модуля угадывания. Вычисление на НДМТ состоит из двух стадий - стадии уга­ дывания и стадии проверки:

1) на стадии угадывания, при получении индивидуальной задачи, происходит угадывание некоторой структуры(слова) * ;

2) и подаются на вход ДМТ на стадии проверки, которая выпол няется как обычная программа ДМТ и либо заканчивается ответом “да” (если есть решение задачи ) либо ответом “нет”, либо продолжается без остановки. Слово также называют свидетелем.

Недетерминированный алгоритм (НДА) определяется как пара угадай некоторое слово ;

проверь детерминированным алгоритмом.

НДА “решает"задачу разрешения, если следующие два свойства имеют место для всех индивидуальных задач :

1) Если, то существует такая структура, угадывание которой для входа приведет к тому, что стадия проверки, начиная работу на входе (, ) закончится ответом “да".

2) Если, то не существует такой структуры, угадывание которой для входа обеспечило бы окончание стадии на входе (, ) с ответом “да”.

Недетерминированный алгоритм, решающий задачу разрешения работает в течение “полиномиального времени”, если найдется полином такой, что для любой индивидуальной задачи найдется догадка, приводящая на стадии детерминированной проверки на входе (, ) к ответу “да"за время (Length ||).

Неформально, класс NP – это класс всех задач разрешения, кото рые при разумном кодировании могут быть решены недетерминирован ными алгоритмами за полиномиальное время или, другими словами, – это класс задач, для которых существует полиномиальное решение (сви детель), которое может быть проверено за полиномиальное время.

Полиномиальная сводимость (по Карпу) задачи разрешения 1 к за даче разрешения 2 (обозначается 1 2 ) означает наличие функции : 1 2, удовлетворяющая следующим двум условиям:

1. Существует полиномиальная ДМТ-программа, вычисляющая ;

2. Для всех 1 выполнение 1 имеет место тогда и только тогда, когда () 2.

Полиномиальная эквивалентность задачи разрешения 1 и задачи разрешения 2 имеет место, когда 1 2 и 2 1.

Задача разрешения называется NP-трудной, если к ней полиноми ально сводятся все задачи разрешения из класса NP. Задача разрешения называется NP-полной, если она лежит в классе NP и является NP-трудной.

Неформально, NP-полная задача - эта самая (неединственная) трудоемкая задача в классе NP. Классическим справочником по NP-полным задачам является книга [55] (см. русский перевод [8]), а также продолжающаяся серия статей “The ongoing guide of NP-complete problems”, которую ведет Д. Джонсон в Journal of Algorithms. В дальнейшем изложении нам пона добятся следующие полезные свойства (см. [8]), выполняющиеся для про извольных задач разрешения 1, 2, 3 :

1. Если 1 2, то 2 влечет 1.

2. Если 1 2 и 2 3, то 1 3.

3. Если 1 и 2 принадлежат NP, 1 NP-полна и 1 2, то NP-полна.

Класс coNP определяется как класс дополнений языков из NP. Фор мальное определение: язык принадлежит классу coNP, если существует ДМТ (, ) и полином такие, что = { |, || () (, ) = 0} (отметим, что в последним определении можно заменить (, ) = 0 на (, ) = 1). Полные в классе coNP задачи определяются аналогично пол ным в классе NP задачам. Каждая coNP-полная задача является дополне нием NP-полной задачи (и наоборот). Примером coNP-полной задачи мо жет служить задача разрешения – является ли данная булева формула (заданная в дизъюнктивной нормальной форме) тавтологией.

Теперь от задач разрешения мы перейдем к задачам подсчета, т.е.

таких, в которых поднимается вопрос “каково число...?”. Ответы на подоб ные вопросы важны для правильной организации вычислительных ресур сов, особенно в случае, когда число объектов, порождаемых алгоритмом, велико, например, экспоненциально от входа.

Задача поиска (search problem) состоит из множества конечных объектов, называемых индивидуальными задачами и, для каждой индиви дуальной задачи, соответствующего (возможно пустого) множе ства [] конечных объектов, называемых решениями. Алгоритм реша­ ет задачу поиска, если, получив на входе произвольную индивидуальную задачу, он либо отвечает “нет"всякий раз, когда множество [] пусто, либо выдает некоторое решение [].

Заметим, что произвольная задача разрешения может быть сфор мулирована как задача поиска (интуитивно понятно, что получить реше ние задачи труднее, чем установить его существование), если положить [] = {“”}, если, и [] =, в противном случае (т.е. если ).

Задача подсчета, основанная на задаче поиска, формулируется сле дующим образом: “дана индивидуальная задача, какова мощность мно жества (), т.е. сколько решений оно содержит?”. Мы будем записывать задачу подсчета следующим образом:

ВХОД (INPUT).

ВЫХОД (OUTPUT) | ()|.

Задача подсчета принадлежит классу #P, если существует неде терминированный алгоритм, такой что для каждой индивидуальной зада чи число различных “догадок”, приводящих к принятию, есть в точности | ()|, а длина самого длинного принимающего вычисления (проверки, выдающей на выходе “да”) ограничена сверху полиномом от ве личины Length[]. Класс #P может быть определен в терминах Считающих Машин Тьюринга, как это было сделано в работе [95].

Считающая машина Тьюринга, СМТ (Counting Turing Machine), есть НДМТ с дополнительной лентой выхода, на которой особая головка пи шет в двоичной записи число принимающих вычислений, соответствующих данному входу. СМТ имеет сложность () в худшем случае, если самое длительное принимающее вычисление (на обычной НДМТ) для входа раз мера осуществляется за () операций.

#P есть класс функций, которые могут быть вычислены считающими машинами Тьюринга с полиномиальной сложностью. В классе#P, также как и в классе NP, имеются полные задачи, но сводимость в классе #P определяется несколько иначе.

Полиномиальная сводимость по Тьюрингу задачи поиска 1 к задаче поиска 2 (обозначается 1 2 ) означает существование алгоритма, который решает 1, используя в качестве “подпрограммы” алгоритм для решения задачи 2, так что если был бы полиномиальным алгоритмом решения 2, то был бы полиномиальным алгоритмом для решения за дачи 1. Очевидно, что сводимость по Карпу является частным случаем сводимости по Тьюрингу, тем не менее справедливость обратного утвер ждения неизвестна.

Задача подсчета 1 называется #P-полной если 1 #P и для всех 2 #P, 2 1.

Задачи подсчета, соответствующие NP-полным задачам разрешения, #P-полны, однако множество задач подсчета, соответствующих полиноми альным задачам разрешения, также #P-полны. Очевидно, что проблема #P = P? установления истинности или ложности этого равенства может остаться нерешенной даже в случае положительного решения проблемы NP = P? Установление #P-полноты задачи подсчета говорит о том, что вычисление соответствующего числа довольно трудно, например не легче (в смысле полиномиальной сводимости по Тьюрингу) задачи определения числа всех наборов, выполняющих КНФ.

В дальнейшем нам будут необходимы определения эффективности алгоритмов, размер выхода которых может быть экспоненциален от раз мера входа. Следующее определение было предложено в работе [61]. Ал горитм, порождающий (перечисляющий) семейство объектов (называемых комбинаторными структурами, combinatorial structures, в [61]) имеет за­ держку (delay), если он удовлетворяет следующим условиям при работе со входом длины :

1. Он выполняет максимум () вычислительных шагов прежде чем выдаст первый объект, либо остановится ничего не выдав.

2. После выдачи объекта он либо выполнит не более () машинных операций прежде чем выдаст очередной объект, либо остановится. Алго ритм с задержкой, ограниченной сверху полиномом от размера входа на зывается алгоритмом с полиномиальной задержкой [61].

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

Вероятностная приближающая схема (Randomized approximation scheme) для задачи подсчета : * N (например, количество формаль ных понятий контекста) – это вероятностный алгоритм, который в качестве входа получает * (например формальный контекст K = (,, )), а также погрешность 0, и выдает число N такое что, для каждого входа, [(1 ) () (1 + ) ()] Если время работы вероятностной приближающей схемы полиноми ально от || и 1, то такой алгоритм называется Полностью полиноми­ альная приближающая схема (fully polynomial randomized approximation scheme), или FPRAS.

Для задач случайной генерации (Sampling) почти равномерным ге­ нератором(fully polynomial almost uniform sampler (AUS)) называют веро ятностный алгоритм, который, получая на вход задачу *, выдает ее случайное решение () в соответствии с некоторым распределением.

Причем, вариационное расcтояние между и равномерным распределени ем не больше, т.е.

|() ()|.

1.2. Модели зависимостей и их вычисление Машинное (автоматическое) обучение (Machine Learning) - одно из ос новных направлений искусственного интеллекта и анализа данных. Слож но дать точное формальное определение машинного обучения, хотя су ществует множество моделей машинного обучения, для каждой из кото рых такое определение дается. Можно сказать, что в самых общих чертах, идея машинного обучения заключается в порождении обобщенного описа ния объектов с целью его дальнейшего использования для классификации других объектов по их описаниями. Стадию классификации называют так же распознаванием (иногда слово “распознавание” используют в качестве синонима “машинного обучения”). Обобщенное описание может, к приме ру, соответствовать определенному состоянию множества весов если речь идет об обучении в нейронной сети по входящим и выходящим сигналам.

В нашей работе речь пойдет об обучении для данных, представимых в виде некоторых описаний в символьной форме. Обычно задача обучения при этом ставится следующим образом. Имеется конечное множество объ ектов (наблюдений), разделенное на несколько подмножеств (классов).

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

Одними из первых среди теоретических моделей обучаемости рекур сивным функциям стали исследования Соломонова [94] и Голда [56]. В об щих чертах модель обучения по Голду может быть представлена следую щим образом. Задана бесконечная последовательность примеров, т.е. пар вида (аргумент, значение) для некоторой неизвестной функции из класса. Можно ли построить алгоритм, который, получив первых входных пар, выдает функцию таким образом, что для некоторого,, = +1 =... = ? Класс функций называется обучаемым, если лю бая функция из этого класса обучаема. Возможны различные уточнения приведенных выше определений, касающиеся требования рекурсивности, частичной рекурсивности или предельной вычислимости, последователь ности представления примеров и др.

В.Н. Вапником и А.Я. Червоненкисом [5] была предложена следу ющая модель обучения. Пусть есть класс функций на, и для произвольной функции задано значение в точках из, каждая из которых выбирается случайно и независимо в соответствии с некоторым фиксированным, но неизвестным распределением вероятностей (). Зада ча обучения состоит в построении для произвольных и функции, для которой с вероятностью большей 1 математическое ожидание (от носительно ()) отклонения значений функции от значений функций не превышает. Аналогичные постановки возможны для других клас сов функций (например, булевых). Важнейшим результатом исследований данной модели явилось установление критериев сходимости и скорости схо димости эмпирических моделей к искомой функции для произвольных (бесконечных по размеру) классов функций.

Развитием модели Вапника стала модель Вэльянта [97] “вероятно при ближенно правильного” (Probably Approximately Correct, PAC) обучения, в которой алгоритм обучения, строящий искомую функцию должен исполь зовать “ограниченное” число обучающих примеров и иметь сложность по времени, ограниченную полиномом от входа.

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

Эти довольно сильные допущения позволяют строить красивые матема тические теории, но сами по себе трудно проверяемы и часто "навязыва ют"природе изучаемых явлений неоправданно сильные условия. В эмпи рических методах обучения (к которым, принадлежит, например, ДСМ метод) подобных допущений не делается. Каждый такой метод предлагает некоторый инструментарий построения “осмысленных обобщений”, кото рый по началу обосновывается некоторыми методологическими соображе ниями, а затем либо доказывает свою эффективность на практике (что сопровождается разработкой типологии ситуаций применения) либо нет.

Задача обучения часто формулируется для двух классов исходных объектов, и к такой постановке сводится случай с большим числом классов.

В нашей работе мы будем придерживаться постановки с двумя классами.

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

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

Поиск ассоциативных правил является популярным и хорошо изу ченным методом извлечения интересных зависимостей между признака ми в больших базах данных. В статье [87] Пятетский-Шапиро описал ана лиз и представление строгих правил, найденных в базе данных, используя различные меры интересности. Основываясь на концепции строгих правил Аграваль и др. в [26] ввели понятие ассоциативных правил для поиска зако номерностей в купленных продуктах, используя базу данных, продаж на кассах супермаркетов. Например правило {, } {}, найденное в данных по продажам, указывает на то, что, если покупатель покупает лук и картофель, то скорее всего он купит и мясо для гамбур гера. Такая информация может быть использована, как базис для различ ной маркетинговой деятельности, например скидочные акции или выбор способа расположения продуктов в магазине. В дополнение к описанно му примеру анализа рыночной корзины, в настоящее время ассоциативные правила используются и во многих других прикладных областях таких, как анализ пользования вебом и обнаружение взломов. Ассоциативные правила определяются как пара непересекающихся множеств признаков (, ), = и записывается как. Для того, чтобы выбрать ин тересные ассоциативные правила из всего множества ассоциативных пра вил, используются различные меры важности и интересности. Наиболее известные из них это достоверность и поддержка. Поддержка () множества признаков определяется, как доля транзакций(объектов) ба зы данных которые содержат. Достоверность ассоциативного правила определяется, как ( ) = ( )/(). Обыч но ищутся только те ассоциативные правила, которые обладают заданной поддержкой и достоверностью (заданными пользователем). Для поиска ас социативных правил было предложено множество алгоритмов. Некоторые из самых известных – Apriori [27], Eclat [82], FP-Growth [60].

В этой работе нас будут интересовать строгие правила, называемые импликациями. Импликацией можно считать ассоциативное правило с до стоверностью 1 (100%). В отличие от ассоциативных правил для имплика ций существует каноническое сжатое представление – минимальный набор импликаций (по количеству импликаций), из которого следуют все осталь ные импликации (см. аксиомы Армстронга). Такой называют минималь ным базисом импликаций. Строгие правила интересны для аналитических областей, таких как профилирование данных, а также в тех областях ана лиза реляционных баз данных, где имеют значение функциональные зави симости.

1.3. Минимальная модель знаний о предметной области: мини­ мальный базис импликаций Импликативные зависимости на признаках в объектно-признаковом представлении данных помогают эксперту лучше понимать суть скрытых в данных закономерностей. Методы анализа формальных понятий (АФП) [54] предлагают вместо всех возможных импликаций рассматривать толь ко минимальное подмножество импликаций, из которого все остальные им пликации могут быть выведены по правилам вывода Армстронга (см. Раз дел 2.1). Это минимальное подмножество импликаций называется канони ческим базисом импликаций (или базис Дюкена-Гига) [42, 54].

Для поиска базиса импликаций существует множество алгоритмов из различных научных сообществ. В сообществе АФП существует несколько алгоритмов для построения базисов импликаций. Алгоритм Гантера [50] основан на том, что множество псевдосодержаний вместе с множеством содержаний образуют систему замыканий поэтому, если научиться вычис лять оператор замыкания, то можно породить все множество псевдосодер жаний вместе с множеством содержаний. Время работы этого алгоритма (| |(||+||)(||+|B(,, )|)), где || – размер минимального базиса, а |B(,, )| – количество замкнутых множеств. Поскольку количество содержаний может быть больше в экспоненциальное число раз чем коли чество псевдосодержаний[70], то время работы этого алгоритма в худшем случае экспоненциально от размера выхода.

Алгоритм Объедкова-Дюкена [42] основан на той же идее, что и алго ритм Гантера, но за счет более быстрого способа вычисления оператора на сыщаения на практике их алгоритм может работать намного быстрее. Этот алгоритм начиная с пустого множества признаков добавляет новые при знаки по одному и пересчитывает текущее множество псевдосодержаний вместе с множеством содержаний. Оценка времени работы этого алгоритма такая же, как и у алгоритма Гантера – (| |(||+||)(||+|B(,, )|)).

Алгоритм Рисселя-Дистеля-Брокмана [37] ищет все собственные по сылки формального контекста за квазиполиномиальное от выхода время, используя алгоритм генерации минимальных трансверсалей гиперграфа.

Отметим, что для задачи поиска минимальных трансверсалей гиперграфа существует квазиполиномиальный от размера выхода алгоритм[49]. Соб ственные посылки задают базис импликаций (левые части импликаций), но не обязательно минимальный. Существуют примеры контекстов, когда размер минимального базиса импликаций в экспоненциальное число раз меньше, чем число собственных посылок [37]. В экспериментах на неко торых реальных данных этот алгоритм показал лучшие результаты чем алгоритм Гантера [37].

В сообществе реляционных баз данных импликации соответствуют функциональным зависимостям, минимальные базисы импликаций назы вают минимальными покрытиями функциональных зависимостей, а вместо формального контекста выступает реляционное отношение ([18, 69]). От метим, что в данном случае число объектов в соответствующем формаль ном контексте будет квадратичным по отношению к количеству кортежей (строчек) в реляционной таблице.

В отличие от случая, когда система замыканий задана формальным контекстом в случае, когда система замыканий задана набором импликаций (не минимальным) для поиска минимального базиса импликаций извест ны полиномиальные от выхода алгоритмы. Так например в [19] был пред ставлен квадратичный алгоритм (от размера входа) для построения ми нимального покрытия функциональных зависимостей для данного множе ства функциональных зависимостей. Похожий алгоритм в терминах АФП был предложен в [90].

Другой взгляд на ту же проблему предлагает теория хорновских мо делей. Хорновской моделью называют булев вектор, который выполняет данную хорновскую КНФ. Хорновские модели образуют системы замыка ний в том смысле, что булев вектор полученной покомпонентной операци ей конъюнкции (называют пересечением) также является моделью. В тер минах АФП хорновские модели соответствуют содержаниям формального контекста. Характеристической моделью называют такую модель, которая не может быть получения пересечением других моделей, в терминах АФП это соответствует строчке редуцированного контекста(содержание супре мум неразложимого элемента решетки).

В статье Англуин-Фрейзер-Питт [28] был предожен алгоритм, кото рый при наличии двух оракулов первый из которых может проверять эк вивалентность хорновских КНФ и выдавать контрпример (булев набор на котором первая КНФ не равна второй КНФ) в случае неэквивалентности, а второй оракул проверяет выполняется ли обучаемая(скрытая) хорновская КНФ на данном булевом наборе, может получить эквивалентную хорнов скую КНФ за полиномиальное от выхода время.

Позже, Хардон в статье [64] исследовал задачу поиска характери стических моделей по хорновской КНФ и задачу получения хорновской КНФ по заданным характеристическим моделям. Ссылаясь на результат Ангулин-Фрейзера-Питта, Хардон доказал, что эти задачи полиномиально эквивалентны, в том смысле, что, если одна(любая) из них может быть решена за полиномиальное время, то и другая тоже. Более того, Хардон показал, что эти задачи полиномиально эквивалентны задаче разрешения – по данной хорновской КНФ и набору характеристических моделей(данному как набор булевых векторов) нужно проверить задают ли они одну и ту же модель или нет. На языке АФП это означает, что задача поиска мини мального базиса импликаций (или базиса который в полиномиальное число раз больше минимального) формального контекста полиномиально эквива лентна задаче построения нередуцируемого контекста (супреумум неразло жимые элементы решетки понятий) по набору импликаций. И что обе эти задачи полиномиально эквиваленты задаче разрешения – по данному фор мальному контексту и данному набору импликаций определить задают ли они одну и ту же систему замыканий или нет. Также, Хардон показал, что эти задачи не проще, чем задача поиска минимальных трансверсалей простого гиперграфа (эквивалентно монотонной булевой дуализации).

Существует несколько работ связанных с приближенном поиском строгих зависимостей в данных. В [65] Кивинен и Маннила рассмотрели несколько мер ошибок функциональных зависимостей.

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

1.4. Задачи и алгоритмы построения гипотез Первая версия ДСМ-метода автоматического порождения гипотез была описана в работе [20]. Описание более поздних версий можно найти в [23], см. также обзор [12]. Правдоподобные рассуждения в ДСМ-методе формализованы в рамках бесконечнозначной логической теории первого порядка с кванторами по кортежам переменной длины. Логические аспек ты ДСМ-метода наиболее подробно освещены в [25, 23], вопросы об опре делимости правдоподобных ДСМ-рассуждений в логике первого порядка исследованы в [6], где показано, что определимость в логике первого по рядка возможна в случае конечных моделей и требует слабой логики пре дикатов второго порядка в случае бесконечных моделей. Как метод ана лиза данных, ДСМ-метод есть система автоматического обучения по поло жительным и отрицательным примерам [12, 16, 52]. Примеры суть объек ты, представляемые подмножествами некоторого множества 1. Свойства суть объекты, представляемые подмножествами некоторого множества 2, 1 2 =. Положительными относительно свойства 2 называются примеры, про которые известно, что они обладают свойством. Отрица­ тельные примеры - это примеры, про которые заведомо известно, что они не обладают свойством.

Основу метода составляют правила правдоподобного вывода, опре деляемые через предикаты сходства. Например, простой положительный предикат сходства + — аналог метода согласия (method of agreement), Дж.С. Милля — выглядит следующим образом:

+ + (, ), (,, ),, +, (,, ) 1... 1... ( & 1, ( 1 ) & = & (1, ( 1 ) )) & &(1... ) = & = & = & (( = ) & 1, ) = ) & & ((1, ( 1 ) & & (1, ( 1 ) ) & & )( &( ( = )))) & 2).

= Здесь соответствует простому предикату сходства (в ДСМ-методе есть и другие предикаты), обозначает шаг применения правил правдоподобного вывода к исходным примерам, есть оператор Россера-Тюркета, сопостав ляющей многозначной формуле классическое истинностное значение из множества {, }, так что () = если имеет многозначную оценку и () = в противном случае. 1 означает, что объект обладает свойством. Точные определения см. в [23].

Интуитивный смысл предиката сходства заключается в том, что пред положительная причина общности свойств объектов 1..., (положительных примеров) заключается в, сходстве струк тур этих объектов (представляемом в данном случае теоретико множественным пересечением описаний структур положительных приме ров, представленных множествами признаков).

Другие предикаты простого метода получаются из предиката сход ства конъюнктивным добавлением некоторых условий. Например преди­ кат с запретом на контрпример получается из предиката простого сход ства добавлением условия (1)+ :

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


Предикаты упорядочены по логическому следствию: предикат сильнее предиката 2 если 1 2. В работах [21, 23] приводится ре шетка предикатов, задаваемая отношением логического следствия.

Гипотезы, то есть объекты, удовлетворяющие тем или иным преди катам, могут использоваться для классификации недоопределенных приме­ ров, т.е. объектов, про которые неизвестно, обладают ли они свойством или нет. Правило положительной классификации (называемое правилом вывода II рода в [23]) выглядит следующим образом.

+ (, ) 1... [( & (+1, ( 2 ) & ) & = &( = ) & ((1, ( 2 ) & ) = ( ( = ))] & [( & = ) = ¬(1, ( 2 ) & ))].

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

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

По определению гипотез и классификации на их основе (ДСМ-метод) достаточно использовать только минимальные по вложению гипотезы. Та ким образом множество минимальных гипотез является полным множе ством гипотез (с помощью него можно произвести те же классификации, что и с помощью множества всех гипотез). В связи с этим встает вопрос о возможности порождения минимальных гипотез с полиномиальной за держкой (или хотя бы за полиномиальное от выхода время), как это имеет место для множества всех гипотез. Вопросы, связанные с обучением мини мальным гипотезам, исследованы в статье [68, 74]. Задача о вычислитель ной сложности порождения минимальных гипотез оставалась до сих пор открытой.

Особое место в ДСМ-методе занимают обобщенные гипотезы [22, 23], в определении которых варьируется основная идея: сходство положитель ных примеров как гипотетическая причина целевого свойства может тормозиться элементами отрицательных примеров, причем тормозами вы ступают минимальные сходства отрицательных примеров, содержащие в качестве подмножества. Ввиду громоздкости логической формулировки обобщенного метода, мы не приводим их здесь, а отсылаем за ними читате ля к работам [25, 22, 23, 24]. Формулировка обобщенного метода на языке АФП приводится в главе 2. Заметим, что обобщенная гипотеза является ги потезой в вышеуказанном смысле только если множество тормозов пусто.

Применение обобщенных гипотез основанно на более сильных допущени ях о природе причинности (ее тернарной природе: причина - блокиратор - следствие) и происходит обычно при отутствии или малом количестве “обычных” (простых в терминологии [23]) гипотез описанных выше.

На основе представления о тернарной причинности в [24] предложен также ситуационный ДСМ-метод, где ситуация, в отличии от блокира тора в обобщенном методе, может содействовать причине, а не противодей ствовать ей. В ситуационном методе возможно наличие противоречивости в исходных данных (что может приводить к противоречивым классифика циям без наличия положительных и отрицательных гипотез).

2. Базисы импликаций и функциональных зависимостей 2.1. Квазизамкнутые множества и псевдосодержания Подмножество удовлетворяет импликации, если из следует. Любое множество импликаций J на множестве определяет оператор замыкания (·)J на, где подмножество замкнуто тогда и только тогда, когда это множество удовлетворяет всем импликаци ям из J. Подмножество импликаций, из которого все остальные имплика ции контекста могут быть выведены по правилам Армстронга называется покрытием импликаций. Заметим, что J является покрытием импликаций контекста K тогда и только тогда, когда система замыканий, которую зада ет J, совпадает с системой замыканий контекста K. Одно из минимальных по мощности (далее будем писать просто минимальный) покрытие импли каций (минимальный базис импликаций) было приведено в [41]. Это под множество импликаций называется базисом Дюкена-Гига, каноническим базисом или stembase в литературе. Множество посылок импликаций в ка ноническом базисе является в точности множеством псевдосодержаний(см.

например [54]): множество называется псевдосодержанием, если = и для любого псевдосодержания. Для множества такого, что и является содержанием или псевдосодержа нием пересечение является содержанием (см. [54]). Таким образом, объединение множества псевдосодержаний с множеством содержаний обра зует систему замыканий. Множество называется квазизамкнутым (квазисодержанием), если для любого выполнено или =. Например, замкнутые множества – квазизамкнуты. Для квази содержания выполнено ( ) = ( ) для любого содержания такого, что. Мы также будем использовать другое эквивалентное определение псевдосодержания: незамкнутое множество является псевдосодержанием тогда и только тогда, когда квазизамкнуто и для любого квазизамкнутого подмножества (см. [41, 76, 78]). Мно жество называется существенным содержанием (существенно за­ мкнутое подмножество признаков), если существует псевдосодержание такое, что =.

Пусть = {1,..., } и = {1,..., } – множества одинако во мощности. Тогда контекст K = (,, = ) называется контраноми­ нальной шкалой, где = = {(1, 1 ),..., (, )}. У контраноми нальной шкалы есть следующее свойство, которое мы будем использовать дальше: любое подмножество признаков замкнуто ( = ) и = { |, 1 }.

/ 2.2. Структура минимальных базисов импликаций Пусть K = (,, ) – формальный контекст, а J – произвольный минимальный базис импликаций контекста K. Рассмотрим любую импли кацию J.

Сначала мы покажем, что = J() является квазизамыканием множества т.е. =. Заметим, что =, поскольку иначе система замыканий базиса J совпадает с системой замыканий базиса J ( ).

Рассмотрим произвольное подмножество. Если J(), то то гда = J = J =. Если (), то = J = J().

Таким образом, квазизамкнуто. Допустим существует другое квазиза мкнутое множество такое, что. Тогда существует импли кация J ( ) такая, что и, т.к. иначе = J(). Поэтому и, следовательно, = =, что противоречит тому, что.

Теперь мы покажем, что, если J – минимальный базис импликаций, то для любой импликации J квазизамыкание посылки явля ется псевдосодержанием. Рассмотрим псевдосодержание. Поскольку не замкнуто, то существует импликация J такая, что. Допустим, что для некоторой импликации J суще и ствует хотя бы два псевдосодержания 1 и 2 такие, что 1, 2. Тогда 1 2. Если 1 2, то 2, но и 2, это невозможно, поскольку. Аналогично, 2 1. Следователь но, 1 2 – замкнуто и 1 2, что невозможно. Поскольку |J| равно числу псевдосодержаний, мы получили, что для каждой имплика ции J найдется ровно псевдосодержание такое, что и. Рассмотрим любую импликацию J и соответствующее ей псевдосодержание. Если квазизамыкание = не совпадает с, то (т.к. каждое псевдосодержание квазизамкнуто), но = и следовательно =.

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

2.3. Функциональные зависимости и импликации Рассмотрим многозначный контекст K(,,, ). Признак на зывается полным, если для любого объекта, найдется та кое, что (,, ). В терминах теории баз данных, многозначный кон текст является отношением. Многозначный контекст называется полным, если все его признаки полны. Для полного многозначного контекста зна чение признака на объекте обозначается, как (), таким образом, (,, ()).

Функциональная зависимость выполнена в полном много значном контексте (,,, ), если каждая пара объектов,, : удо влетворяет условию ( () = ()) ( () = ()).

В [54] было показано, что для любого полного многозначного кон текста K = (,,, ), можно построить формальный контекст K := (2 (),, ), где 2 () – множество всех пар различных объектов из, а определяется как {, } () = ().

Тогда, множество функционально зависимо от множества в контексте K, если и только если в контексте K выполнена импликация.

В работе [70] было показано обратное сведение: для формального кон текста K = (,, ) можно построить многозначный контекст K такой, что импликация выполнена тогда и только тогда, когда функ ционально зависимо от в K. Для контекста K соответствующий мно гозначный контекст определяется, как K = (,, {}, ), где для любого, () =, если не выполнено и () =, если.


2.4. Распознавание псевдосодержаний В этом разделе мы обсудим вычислительную сложность задачи рас познавания псевдосодержания.

Задача 1. Распознавание псевдосодержания (PI) ВХОД: Формальный контекст K = (,, ) и подмножество признаков.

ВОПРОС: Является ли псевдосодержанием контекста K?

Чтобы доказать -трудность задачи PI, мы рассмотрим наиболее известную -полную задачу – выполнимость КНФ.

Задача 2. Выполнимость КНФ (SAT) ВХОД: Булева КНФ формула (1,..., ) = 1...

ВОПРОС: Выполнима ли ?

Рассмотрим произвольный вход задачи SAT – КНФ 1,..., с пе ременными 1,...,, где = (1... ) (1 ) – дизъюнкции и {1,..., } {¬1,..., ¬ } (1, 1 ) – некоторые перемнные или их отрицания, называемые литералами. По этой КНФ мы построим контекст K = (,, ). Определим = {, 1,...,, 1, ¬1,...,, ¬, } = {1, ¬1,...,, ¬,,, 1,..., } ¬ { | 1, 1 } { | 1, 1 } Для 1 мы определим множества = {1, ¬1,...,, ¬ } {, ¬ }. Также для 1 и 1 мы определим множества ¬ = { } и = {¬ }.

Теперь мы готовы определить отношение. Отношение состоит из двух частей. Первая часть определяется как:

{1, ¬1,...,, ¬ } = = = {(, ) |, 1, 1 } / {(¬, ) | ¬, 1, 1 } / = = {1, ¬1,...,, ¬ } {1, ¬1,...,, ¬ }, {(1, 1 ), (¬1, ¬1 ),..., (, ), (¬, ¬ )} следовательно {1, ¬1,...,, ¬ } это множество объектов, кото рые соответствуют не входящих в литералам (1 ), и = это отношение контраноминальной шкалы. Остальная часть определяется объектными содержаниями:

= {, } = {} {1,..., } = {}, 1 = {}, 1, 1 ¬ ¬ = {}, 1, 1 Отметим, что у контекста K есть некоторые объекты с одинаковыми со держаниями (например 1 и 1 ), но это не важно.

1 2 · · · 1 ¬1 · · · ¬ ¬.

. =.

¬ ······ ············ ······ 1 1 ¬1 ¬...

...

...

¬ ¬...

...

...

1 ¬1 ¬...

...

...

¬ ¬ Таблица 2.1. Контекст K.

Для любого подмножества {1, ¬1,...,, ¬ }, которое удо влетворяет условию {, ¬ } = для 1, мы определим Булево назначение переменных :

, if and ¬ ;

/ ( ) =, if ¬ and ;

/, otherwise ( and ¬ );

В случае и ¬ для некоторого 1, назначение / / не определено. Отметим, что для {1, ¬1,...,, ¬ } Булево назначение переменных (корректно) определено, если только если для всех 1.

Симметрично, для назначения, определим множество = {¬ | ( ) = } { | ( ) = }.

Перед тем, как доказать -трудность задачи PI мы докажем несколько вспомогательных утверждений. Следующая лемма является ключевой в SAT к дополнению задачи PI.

Лемма 1. Если подмножество {1, ¬1,...,, ¬ } замкнуто и для любого 1, то – определено и выполняет т.е. ( ) =. С другой стороны, если назначение выполняет, то замкнуто и для всех 1.

Доказательство. Пусть {1, ¬1,...,, ¬ } и не содержится ни в одном (1 ), тогда для всех 1 и следовательно (по определению ) корректно определено. Поскольку = это отношение контраноминальной шкалы и любое содержание может быть представлено как пересечение объектных содержаний, то мы получаем = { | / } {¬ | ¬ }, где {1, ¬1,...,, ¬ }. Поскольку / ¬ и для любого 1 мы также получаем для каждого 1 и 1. Таким образом, = { }.

Допустим – замкнуто т.е. =. Тогда {1,..., } = и следовательно для каждого 1 найдется некоторый объект такой, что. Поскольку и = { | } {¬ | ¬ / / / } { } последнее означает, что { | } {¬ | ¬ }.

/ / Тогда, по определению отношения, существует литерал или ¬ / /, который принадлежит дизъюнкции. Поэтому выполняет для всех 1.

Теперь пусть – Булево назначение переменных и () =.

для всех 1 (по определению ). То Очевидно, гда = { | } {¬ | ¬ } { }. Заметим, что / / {1, ¬1,...,, ¬ } = {1, ¬1,...,, ¬ } и. Сле довательно замкнуто тогда и только тогда, когда {1,..., } =.

Предположим, что {1,..., } для некоторого 1. Это означает, что и ¬ для всех и ¬. Отсюда / / и по определению отношения следует, что дизъюнкция не выполнена при назначении.

Утверждение 1. Если существует такое 1, что, то замкнуто.

Доказательство. Пусть и. Тогда = / ¬ =. В случае когда мы можем представить как ¬ / / = ( {}) =.

Теперь мы готовы доказать -трудность задачи PI.

Теорема 1. Задача PI co -трудна.

Доказательство. Мы сведем SAT к PI. По данному входу задачи SAT – = 1..., мы построим контекст K, который был описан выше (см.

Таблицу 2.1). Мы рассмотрим множество = {} как множество, про которое нужно узнать является ли оно псевдосодержанием. Таким образом, соответствующий вход задачи PI это (K, ) и нужно доказать, что КНФ выполнима тогда и только тогда, когда не является псевдосодержанием контекста K. Не ограничивая общности можно считать, что для любого 1 дизъюнкция ¬ входит в (добавление таких дизъюнкций не влияет на выполнимость).

() Пусть выполнима и пусть – булево назначение переменных, которое выполняет т.е. () =. Рассмотрим множество = {}.

Как мы позже увидим является псевдосодержанием, и =, а это значит, что – не может быть псевдосодержанием. Для начала проверим, что =. Поскольку нам следует проверить только, ¬, где {, 1,..., } { | 1, 1 } { | что 1, 1 }. Очевидно потому, что не пусто. По, поэтому Лемме 1 для любого 1,. Следовательно ¬ и (1, 1 ). Для того, чтобы доказать, что является псевдосодержанием мы покажем, что любое собственное подмножество замкнуто. Рассмотрим произвольное множество.

Если тогда (т.к. = ) найдется литерал {1, ¬1,...,, ¬ } такой, что и. Таким образом, по Утверждению 1 подмноже / ство замкнуто. Теперь пусть тогда, если = {} = по / Лемме 1 подмножество замкнуто. Если = {} тогда и по Утверждению 1 подмножество замкнуто.

() Теперь пусть псевдосодержание является собственным подмно жеством (т.е. ) и. Тогда не может быть подмножеством ни одного объектного содержания K. С учетом того, что квазизамкнуто следует, что замкнуто для любого. Заметим, что посколь ку иначе. Рассмотрим. Так как замкнуто и, то возможны только два варианта: = либо =. Допустим =. Тогда =, где {1, ¬1,...,, ¬ } и = (потому, что = и = ). Рассмотрим = {1,..., }.

Это множество должно быть замкнуто т.к. квазизамкнуто. Заметим, что, для всех 1 и {1,..., } {1,..., } (т.к.

= ). Следовательно ( ) {1, ¬1,...,, ¬ }. Поскольку ( ) =, то найдется литерал {1, ¬1,...,, ¬ } такой, что ( ). Тогда, по определению и поскольку некоторая дизъ юнкция содержит литерал мы получаем, что. Таким / образом = и {} = {1, ¬1,...,, ¬ }. Более для каждого 1, поскольку назначение = {} того, (корректно) определено. В виду того, что {} замкнуто и по Лемме 1, назначение выполняет.

В [76, 78] было показано, что coNP следовательно мы получаем Следствие 1. Задача PI co -полна.

2.5. Лектически максимальные псевдосодержания и перечисле­ ние максимальных псевдосодержаний Важная задача связанная с псевдосодержаниями это задача опреде ления является ли данное множество лектически максимальным псевдосо держанием.

Пусть = {1,..., } будет конечным линейно упорядоченным множеством (1 · · · ). Для пары множеств и мы будем говорить, что лектически меньше, чем (, лектически больше чем ), если : { | } = { | }. Не сложно понять, что лектический порядок является линейном порядком на подмножествах множества.

Задача 3. Распознавание лектически максимального псевдосодержания (LLPI) ВХОД: Контекст K = (,, ) с линейным порядком на и подмноже ство.

ВОПРОС: Является ли лектически максимальным псевдосодержанием контекста K?

Утверждение 2. Задача LLPI co -трудна.

Доказательство. Мы сведем SAT к дополнению задачи LLPI так же как в Теореме 5. Линейный порядок на определим как: 1... 1 ¬1... ¬. Поскольку = {} и замкнуто, лектически максимальное псевдосодержание тогда и только тогда, когда является псевдосодержанием.

Таким образом, невозможно найти лектически максимальное псевдосодер жание за полиномиальное время, если =.

В [38, 39] было показано, что псевдосодержания не могут быть пе речислены с полиномиальной задержкой в лектическом порядке (если = ). Утверждение 2 показывает, что псевдосодержания нельзя пере числить с полиномиальной задержкой и в обратом лектическом порядке, т.е., мы получили следующее следствие.

Следствие. Псевдосодержания не могут быть перечислены с полиноми альной задержкой, если =.

Также в [38, 39] было показано, что невозможно найти все минималь ные (по включению) псевдосодержания за полиномиальное от выхода вре мя, если =. Похожая задачу будет - задача перечисления макси мальных (по включению) псевдосодержаний.

Задача 4. Перечисление максимальных псевдосодержаний (EMPI) ВХОД: Контекст K = (,, ) ВЫХОД: Все максимальные псевдосодержания контекста K Утверждение 3. Задача EMPI не может быть решена за полиномиальное от выхода время, если =.

Доказательство. Предположим мы можем решить EMPI за полиноми альное от выхода время. Рассмотрим произвольный вход задачи SAT и соответствующий ему контекст K = (,, ) из доказательства Теоре мы 5. Заметим, что существует не более одного псевдосодержания, кото рое содержит, поскольку пересечение псевдосодержаний замкнуто, а не принадлежит ни одному содержанию кроме. Следовательно мы можем найти псевдосодержание {} за полиномиальное время. Очевидно, {} является псевдосодержанием, если и только если = {}. 2.6. Распознавание существенных содержаний Другая задача связанная с задачей распознавания псевдосодержаний это задача распознавания существенных содержаний.

Задача 5. Распознавание существенного содержания (EI) ВХОД: Контекст K = (,, ) и множество.

ВОПРОС: Является ли существенным содержанием контекста K?

Утверждение 4. Задача EI NP-полна.

Доказательство. 1. NP-трудность. Мы сведем SAT к EI, таким же обра зом как мы сводили SAT, к дополнению PI. Давайте построим контекст K2 = (, {}, ), где, и множество объектов, множество призна ков и отношение контекста K из доказательства Теоремы 5 (см. Таблицу 2.1). Очевидно, {} является существенным содержанием контекста K2 тогда и только тогда, когда {} не является псевдосодержанием контекста K.

2. Принадлежность классу NP. Множество является существенным содержанием контекста K = (,, ) тогда и только тогда, когда суще ствует псевдосодержание такое, что =. Поскольку псевдо содержания это максимальные по включение квазизамкнутые множества с одинаковым замыканием (см. [76]), множество – существенное содер жание, если и только если существует квазизамкнутое множество такое, что =. Квазизамкнутость может быть проверена за полиноми альное время (см. [41, 76, 78]). Следовательно свидетелем(доказательством) того, что является существенным содержанием может быть квазизамкну 2.

тое множество такое, что =.

2.6.1. Посылка импликации из минимального базиса Мы доказали, что задача распознавания посылки импликации из осо бого минимального базиса (а именно базиса Дюкена-Гига) coNP-полна.

Рассмотрим задачу распознавания посылки импликации из произвольного минимального базиса. Пусть K = (,, ) – формальный контекст и пусть J – произвольный минимальный базис импликаций контекста K. Поскольку J – минимальный базис импликаций контекста K, то для любой имплика ции J множество является псевдосодержанием контекста K, где (·) – оператор квазизамыкания. Рассмотрим следующую задачу Задача 6. Распознавание посылки импликации из минимального базиса (PMB) ВХОД: Контекст K = (,, ) и множество.

ВОПРОС: Существует ли минимальный базис импликаций J контекста K такой, что J для некоторого ?

Поскольку задача распознавания псевдосодержания лежит в и квазизамыкания возможно вычислять за полиномиальное время, задача PMB также лежит в. Теперь рассмотрим вход (K = (,, ), ) из сведения из доказательства Теоремы 5. Если квазизамыкание множества является псевдосодержанием, то тоже является псевдосодержанием, потому, что = или =, и – не псевдосодержание. Следова тельно, если – посылка импликации из некоторого минимального базиса контекста K, то – псевдосодержание контекста K. Если не существует ни одного минимального базиса контекста K с импликацией с посылкой, то не может быть псевдосодержанием. Таким образом, мы доказали следующе утверждение Утверждение 5. Задача PMB coNP-полна.

Поскольку импликации формального контекста эквивалентны функ циоанальным зависимостям (как показано выше), мы получаем следующее Следствие. Пусть дано – отношение базы данных с реляционной схе мой и подмножество. Задача разрешения – существует ли такое минимальное покрытие функциональных зависимостей J, что J для некоторого coNP-полна.

Задача 7. Генерация случайного псевдосодержания (RSP) ВХОД: Контекст K = (,, ).

ВЫХОД: Псевдосодержание контекста K такое, что было выбрано случайно с ненулевой вероятностью среди всех псевдосодержаний контек ста K.

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

Тогда для любого псевдосодержания контекста K, существует ненулевая вероятность быть сгенерированным. Рассмотрим произвольное псевдосо держание и случай когда наш алгоритм выдает это псевдосодержание. Мы можем записать все случайные шаги алгоритма и представить их как последовательность. Отметим, что || полиномиальна т.к. полино миален. Теперь рассмотрим следующий алгоритм (, ), который прове ряет является ли псевдосодержанием, используя свидетеля. Алгоритм запускает алгоритм используя случайные операции записанные в и если выданное множество совпадает с, то он возвращает ответ ДА, иначе от возвращает ответ НЕТ. Существование такого алгоритма озна чает, что задача распознавания псевдосодержания лежит в. Ранее мы показали, что эта задача -полна, поэтому, если существует полиноми альный алгоритм для RSP, то =. Следовательно мы доказали:

Утверждение 6. Не существует полиномиального алгоритма для генера ции случайного псевдосодержания, если =.

Известно, что задача подсчета псевдосодержаний #P-турдна [76], тем не мене многие #P-трудные задачи могут быть решены приближен но. Таким приближенные алгоритмы называются FPRAS (fully polynomial randomized approximation scheme) [59]. С другой стороны, FPAUS (fully polynomial almost uniform sampling) [59] – задача генерации случайного эле мента (количество которых FPRAS оценивает) с распределением -близким равномерному, с временной сложностью зависящей от как полином от log 1. В [59] было показано, что существование FPRAS эквивалентно существованию FPAUS. Таким образом, из Утверждения 6 следует, что для случайно генерации псевдосодержания не существует FPAUS, если = Утверждение 7. Не существует FPRAS для подсчета псевдосодержаний, если =.

2.7. Базис импликаций с двухэлементными посылками Поскольку задача поиска минимального базиса импликаций полино миально эквивалентна задаче разрешения совпадения систем замыканий заданного контекста K = (,, ) и набора импликаций, то возникает вопрос как решать данную задачу разрешения для некоторых частных слу чаев базисов импликаций. Так например, если все посылки импликаций из одноэлементные, то задает дистрибутивную решетку и данная задача решается за полиномиальное время, поскольку для контекста задающе го дистрибутивную решетку минимальный базиc импликаций может быть найден за линейное от выхода время [57]. Оказывается, что, если ограни читься только базисами, у которых все посылки мощности не больше двух, то это ограничение никак не упрощает данную задачу разрешения.

Задача 8. Эквивалентность систем замыканий (CSEQ) ВХОД: Формальный контекст K = (,, ) и набор импликаций.

ВОПРОС: Совпадают ли системы замыканий контекста K и набора им пликаций ?

Задача 9. Эквивалентность систем замыканий, когда у импликаций посыл ки мощности не больше двух (CSEQ2) ВХОД: Формальный контекст K = (,, ) и набор импликаций такой, что выполнено | | 2.

ВОПРОС: Совпадают ли системы замыканий контекста K и набора им пликаций ?

Теорема 2. CSEQ и CSEQ2 полиномиально эквивалентны.

Доказательство.

Очевидно, что 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,..., }} как (). Не сложно проверить, что множество замкнуто в тогда и только тогда, когда () замкнуто в. Более того, если замкнуто в, то = ( ). Следовательно, отображение () : задает биекцию между замкнутыми множествами и. Аналогично отображе ние () : задает биекцию между замкнутыми множествами 2.

контекстов K и K.

Заметим, что последнее сведение похоже на хорошо известное сведе ние SAT к 3-SAT, это объясняется тем, что замкнутые множества набора импликаций соответствуют выполняющим наборам соответствующей Хор новской КНФ.

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

Определение 1. Набор импликаций называется приближенным базисом формального контекста K, если для случайно и равномерно выбранного подмножества, ( = ) 1.

Преимущества предложенной модели по сравнению с точным бази сом:

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

Алгоритм построения приближенного базиса импликаций основыва ется на результатах из [28]. Ниже приводится псевдокод алгоритма постро ения приближенного базиса импликаций:

UpdateBase(K,, ) 1 for each And ( ) = 2 do if then заменить в импликацию на ( ) 5 return J 6 { } 7 return J ApproximateImplicationBase(K, ) 1 J 2 for 1 to 3 do выбрать случайное замкнутое множество базиса if = then J UpdateBase(K,, ) 6 return J Если сложность вычисления случайного замкнутого множества равна (()), то сложность работы этого алгоритма равна ( · () + · | | · ||| |), где приближенный базис, который нашел этот алгоритм после итераций.

Отметим, что самая “сложная” часть этого алгоритма это выбор слу чайного замкнутого подмножества в базисе. В разделе 4.6 данной работы доказано, что эта задача не может быть решена за полиномиальное время, если =. Не смотря на сложность этой задачи использование следу ющего алгоритма показало хорошие результаты на практических данных.



Pages:   || 2 | 3 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.