Содержание к диссертации
Введение
1. Введение 4
1.1. Теория упорядоченных множеств и теория решеток 8
1.2. Анализ формальных понятий (АФП) 10
1.3. Машинное обучение 13
1.4. ДСМ-метод 17
1.5. Теория алгоритмической сложности 20
2. Гипотезы и классификации: теоретико- решеточная и теоретико-графовая интерпретации, связь с родственными понятиями 27
2.1. Основные определения: гипотезы и классификации 27
2.2. Теоретико-решеточная интерпретация гипотез и классификаций 34
2.3. Теоретико-графовая интерпретация гипотез 37
2.4. Теоретико-графовая интерпретация классификаций — 41
2.5. Гипотезы и родственные понятия из анализа данных и искусственного интеллекта 44
2.5.1. Гипотезы и импликации в АФП 45
2.5.2. Импликации и зависимости в реляционных базах данных 47
2.5.3. Пространство версий между минимальными гипотезами и минимальными посылками 49
2.5.4. Гипотезы, решетки понятий и деревья решений 54
3. Алгоритмические проблемы порождения понятий, гипотез и классификаций 58
3.1. Число всех формальных понятий 58
3.2. Число минимальных гипотез 60
3.3. Задачи распознавания для понятий с ограничениями на размер 61
3.4. Задачи распознавания для гипотез с ограничениями на размер 68
3.5. Сложность классификации и проверки критерия достаточного основания 73
3.6. Алгоритмы порождения формальных понятий,
решеток понятий, гипотез и классификаций 78
3.6.1. Алгоритм Замыкай-по-Одному 78
3.6.2. Алгоритм порождения решетки понятий 82
3.6.3. Алгоритмы порождения гипотез и минимальных гипотез 87
3.6.4. Пошаговый алгоритм для вычисления минимальных гипотез 89
3.6.5. Вычисление классификаций и проверка критерия достаточного основания 92
3.6.6. Вычисление предгипотез и обобщенных гипотез 93
4. Устойчивость формальных понятий и гипотез 95
4.1. Мотивация и прецеденты 95
4.2. Индексы устойчивости: определения и основные свойства 96
4.3. Изменение устойчивости с ростом числа примеров 99
4.4. Алгоритмическая сложность вычисления индексов устойчивости 105
4.5. Алгоритм с полиномиальной задержкой для вычисления индексов устойчивости 108
4.6. Приближенное вычисление индексов устойчивости 110
5. Узорные структуры и их проекции 117
5.1. Узорные структуры: определение и связь с формальными контекстами 117
5.2. Вычисления в узорных структурах 120
5.3. Проекции узорных структур 121
5.4. Порождение гипотез в проекциях 124
5.5. Приложения в области графов 128
6. Заключение 133
7. Список литературы
- Машинное обучение
- Теоретико-графовая интерпретация классификаций
- Задачи распознавания для гипотез с ограничениями на размер
- Изменение устойчивости с ростом числа примеров
Машинное обучение
Отметим еще одно родственное направление в области формализации понятий с помощью решеток. В работе [52] А.В. Чечкин вводит определение сведения как обобщенного признака объектов. В отличии от анализа формальных понятий, здесь рассматриваются не только замкнутые множества признаков и объектов, в результате чего совокупность возможных сведений образует булевую решетку понятий относительно операций пересечения, объединения и разности на множествах объектов, соответствующих признакам. В целях моделирования информационных процессов и систем автором исследуются произведения решеток понятий, их разложения, представления с помощью базовых множеств (шкал), характеризация с помощью фильтров.
Машинное (автоматическое) обучение (Machine Learning) - одно из основных направлений искусственного интеллекта и анализа данных [?], [30]. Представляется крайне затруднительным дать точное формальное определение машинного обучения, хотя существует множество моделей машинного обучения, для каждой из которых такое определение дается. Например, в современном учебнике по машинному обучению (МО) [100] дается следуещее квази-определение: "МО - это область обработки данных, которая занимается программами, экстраполирующими данными из прошлого и соответственно изменяющими свое поведение". Можно также сказать, что в самых общих чертах, идея машинного обучения заключается в порождении обобщенного описания объектов с целью его дальнейшего использования для классификации других объектов по их описаниями. Стадию классификации называют также распознаванием (иногда слово "распознавание" используют в качестве синонима "машинного обучения").
Обобщенное описание может, к примеру, соответствовать определенному состоянию множества весов если речь идет об обучении в нейронной сети по входящим и выходящим сигналам. В нашей работе речь пойдет об обучении для данных, представимых в виде некоторых описаний в символьной форме. Обычно задача обучения при этом ставится следующим образом. Имеется конечное множество объектов (наблюдений) Е, разделенное на несколько подмножеств (классов). Все объекты имеют описание в некотором формальном языке L. По описаниям объектов из Е необходимо породить осмысленное правило, сформулированное в языке L , которое по описанию объекта из Е выдавало бы номер его класса. Осмысленность правила может определяться, например, через оптимальность в смысле некоторого численного "функционала качества обучения" (часто являющегося функцией от длины правила: чем короче правило - тем лучше) или через какие-либо другие формальные условия. Требование "осмысленности" при этом должно обеспечивать то, что порождаемое правило не сводится просто к прямому использованию списка всех пар (объект, класс), а является некоторым их "обобщением".
Одними из первых среди теоретических моделей обучаемости рекурсивным функциям стали исследования Соломонова [137] и Голда [90]. В общих чертах модель обучения по Голду может быть представлена следующим образом. Задана бесконечная последовательность примеров, т.е. пар вида (аргумент, значение) для некоторой неизвестной функции из класса К. Можно ли построить алгоритм, который, получив п первых входных пар, выдает функцию fn таким образом, что для некоторого N, Vra N, fn = /n+i = ... = д? Класс функций К называется обучаемым, если любая функция д из этого класса обучаема. Возможны различные уточнения приведенных выше определений, касающиеся требования рекурсивности, частичной рекурсивно-сти или предельной вычислимости, последовательности представления примеров и др.
В.Н. Вапником и А.Я. Червоненкисом [6] была предложена следующая модель обучения. Пусть G есть класс функций на Rn х R, и для произвольной функции / задано значение в / точках из Rn, каждая из которых выбирается случайно и независимо в соответствии с некоторым фиксированным, но неизвестным распределением вероятностей Р{х). Задача обучения состоит в построении для произвольных г] is. є функции д G, для которой с вероятностью большей 1 — ту математическое ожидание (относительно Р(х)) отклонения значений функции д от значений функций / не превышает є. Аналогичные постановки возможны для других классов функций (например, булевых). Важнейшим результатом исследований данной модели явилось установление критериев сходимости и скорости сходимости эм лирических моделей к искомой функции д для произвольных (бесконечных по размеру) классов функций.
Развитием модели Вапника стала модель Вэльянта [141] "вероятно приближенно правильного" (Probably Approximately Correct, РАС) обучения, в которой алгоритм обучения, строящий искомую функцию должен использовать "ограниченное" число обучающих примеров и иметь сложность по времени, ограниченную полиномом от входа.
В теоретических моделях обучения ключевым является допущение о том, что данные подчиняются некоторой (неизвестной) функции из определенного класса, а сами данные (в моделях Вапника и Вэльянта) возникают в соответствии с некоторым (неизвестным) распределением вероятности. Эти довольно сильные допущения позволяют строить красивые математические теории, но сами по себе трудно проверяемы и часто "навязывают" природе изучаемых явлений неоправданно сильные условия. В эмпирических методах обучения (к которым, принадлежит, например, ДСМ-метод, см. разделы 1.4, 2.1) подобных допущений не делается. Каждый такой метод прелагает некоторый инструментарий построения "осмысленных обобщений", который по началу обосновывается некоторыми методологическими соображениями, а затем либо доказывает свою эффективность на практике (что сопровождается разработкой типологии ситуаций применения) либо нет.
Задача обучения часто формулируется для двух классов исходных объектов, и к такой постановке сводится случай с большим числом классов. В нашей работе мы будем придерживаться постановки с двумя классами. При этом один из классов обычно называется положительным, а другой - отрицательным относительно целевого признака. Исходные объекты, принадлежащие данным классам, называются, соответственно, положительными или отрицательными примерами.
Одним из самых распространенных и самых естественных способов описания объектов являются объектно-признаковые матрицы - матрицы, строки которых соответствуют объектам, а столбцы - признакам, принимающим некоторые значения. При этом элемент матрицы ац указывает на то, какое значение принимает признак с номером г для объекта с номером j. В простейшем случае признаки принимают значение из двухэлемент
Теоретико-графовая интерпретация классификаций
В этом разделе мы обсуждаем гипотезы и основанные на них классификации с точки зрения теории решеток. В частности, мы используем представление решетки с помощью диаграммы как это делается в [86].
Попытаемся проинтерпретировать определения гипотез и классификаций в терминах решеток понятий.
Во-первых, из определения предгипотез непосредственно следует, что положительная предгипотеза h+ соответствует такому элементу решетки s(i +), для которого не существует элемента решетки %$(К-) с тем же формальным содержанием. Тем самым, вопрос о существовании предгипотез становится эквивалентен вопросу об изоморфизме решетки подрешетке другой решетки. Более точно, имеет место следующее
Утверждение 2.1 Пусть даны положительный контекст К+ = (G+, М,1+) и отрицательный контекст К- = (G-, М,/_). Положительные предгипотезы отсутствуют тогда и только тогда когда существует изоморфизм решетки $ї(К+) в подре-шетку решетки В(К-), отображающий каждое формальное понятие контекста К+ (элемент решетки Ч${К+)) в формальное понятие контекста К- (элемент решетки Ъ(К-)) с тем же формальным содержанием.
Доказательство. 1. Положим, что положительных предгипотез нет, тогда всякое положительное содержание (содержание контекста К+) является также и отрицательным содержанием (содержанием контекста KJ), а так как множество положительных содержаний образует решетку, то и множество соответствующих отрицательных содержаний образует решетку, являющуюся подрешеткой решетки (JC_). Следовательно, %$(К+) изоморфна подрешетке решетки %(К-) с элементами, имеющими те же формальные содержания что и элементы решетки В(К+).
Обратно, если изоморфизм указанного вида существует, то всякое положительное формальное содержание является также и отрицательным содержанием и положительных предгипотез не существует.
С гипотезами дело обстоит несколько сложнее. Каждый отрицательный пример вырезает из решетки положительных по нятий Ч$(К+) некий порядковый фильтр, состоящий из фальсифицированных гипотез. Множество всех положительных гипотез, будучи дополнением множества фальсифицированных гипотез до множества положительных понятий, есть множество, замкнутое по отношению супремума решетки положительных понятий. Конечно, двойственное утверждение (с заменой + на -) имеет место для решетки Ъ$.(К-).
Ситуация выглядит иначе в решетке понятий !8(К±). Выделим в этой решетке следующие три типа понятий: во-первых, понятия вида (А, В U {го}), где В есть формальное содержание контекста К+, во-вторых, понятия вида (А, В), где В есть формальное содержание контекста К_, и есть формальные понятия, чьи содержания не являются ни формальными содержаниями контекств К+ ни контекста К— Это понятия вида (А, В), для которых А = Е+ U Е_, Е+ С G+, Е- CG-,B Е+, В ф El.
Утверждение 2.2 Положительная гипотеза соответствует формальному понятию контекста К±, которое имеет вид (A, B\j{w}), и для которого не существует ни одного формального понятия К± с формальным содержанием В. Доказательство. Пусть существует формальное понятие кон текста К± с содержанием В. Тогда существуют примеры, обла дающие всеми признаками из множества В, но не обладающие признаком и , а это означает, что положительное формальное содержание В есть подмножество формального содержания по крайней мере одного отрицательного примера. о
Отрицательная гипотеза соответствует формальному понятию контекста К±, которое имеет вид (А, В), w 0 В, причем не существует понятия контекста К± с формальным содержанием, включающем В U {w} (т.е. совпадающим или лежащим ниже соответствующей вершины в диаграмме решетке).
В решетке понятий %(К±) формальные понятия, соответствующие положительным и отрицательным гипотезам находятся ниже (в смысле отношения порядка на формальных понятиях) понятий, которые не являются гипотезами.
В терминах этой решетки проблема классификации недоопре-деленного примера дТ Є GT выглядит следующим образом. Рассмотрим порядковый фильтр решетки &(К±), заданный макси мальными подмножествами множества {дт}т U {ад}, являющимися формальными содержаниями контекста К±. Если суще-стует формальное понятие (А, В U {ад}), лежащее в этом порядковом фильтре, такое что w Ви (В1, В) не является элементом решетки В(К+)) vi , то В есть гипотеза в пользу положительной классификации недоопределенного примера дт. Отсутствие гипотезы в пользу отрицательной классификации примера дт означает, что для любого формального понятия (А, В) решетки 2(.К±), такого что ад $ В и (А, В) лежит в порядковом фильтре решетки В(К±), соответствующем неопределенному при-меРУ 9т (задаваемыми наибольшими подмножествами множества {дтУ U {го}, которые являются содержаниями Ъ(К±)), существует формальное понятие, лежащее ниже (A, BU {w}).
Ситуация выглядит несколько иначе в решетке классификационного контекста Кс. Утверждение 2.3 Если дан формальный контекст Кс и неопределенный пример дТ, то гипотеза в пользу положительной классификации неопределенного примера дТ существует тогда и только тогда, когда существуют некоторые А,В,АТ, для которых выполняются следующие условия
Доказательство. Пусть В - гипотеза в пользу положительной классификации недоопределенного примера дт. Это означает, во-первых, что существует множество положительных примеров А такое, что пересечение формальных содержаний примеров из Л в контексте Кс равно В U {ад}. Поскольку формальные содержания недоопределенных и отрицательных примеров не содержат ад, объем формального понятия контекста Кс, имеющего формальное содержание BU{w}, совпадает с А и первое утверждение доказано.
Далее, В должно содержаться в {дт}т- Поскольку пример дт не имеет признака ад, это означает, что В есть формальное понятие контекста Кс и существует некоторое множество Ат: дт Є Ат С GT такое что формальное содержание, соответствующее формальному содержанию В должно содержать
Задачи распознавания для гипотез с ограничениями на размер
В нашей постановке задача классификации объектов из GT сходна с постановкой в модели абдукции из работы [66], где однако предполагается, что множество гипотез Н не вычисляется, а задано заранее внешним образом. Помимо гипотез имеется еще множество фактов D. Между гипотезами и классифицируемыми объектами задано отношение I С D х Н, причем (d, К) Є / означает, что гипотеза h "объясняет" факт d. Задача заключается в нахождении "минимального" объяснения всех фактов (считается, что объяснение устроено аддитивно - объяснение множества разных фактов есть множество объяснений этих фактов). Модель абдукции естественным образом описывается в терминах двудольных графов, где гипотезы и факты представляются вершинами разных долей, отношение соответствует ребрам этого графа, а минимальное объяснение соответствует минимальному подмножеству множества Н, доминирующему множество D. Определения "минимальности" могут варьироваться.
Определение классификации (Определение 2.2) может быть легко реализовано как алгоритм: вначале порождаются множества (+)- и (-)-гипотез, затем проверяется вложение результирующих гипотез в объектное понятие {дт}т. Однако такая реализация имеет существенный недостаток: если число гипотез экспоненциально по отношению к размеру входа, то время и память необходимые для классификации всего лишь одного объекта из GT также экспоненциально. Может ли классификация данного недоопределенного примера быть реализована без вычисления множества всех минимальных гипотез? Этот вопрос соответствует следующей задаче распознавания:
Мотивация к изучению этой задачи становится еще более сильной если рассмотреть случай когда G- = 0. При этом положительные гипотезы суть просто положительные понятия, а минимальные гипотезы суть множества вида {т}++, где т Є М. Их порождение осуществляется за время 0{\G+\ \М2). Проверка вложенности признаковых содержаний в множество {дт}т осуществляется за время \М\. Если существует m Є М такое что {т}++ С {дТ}Т, то классификация реализована. Если нет, то другие положительные формальные содержания также не являются подмножествами множества {дт}т и положительная классификация невозможна. Таким образом задача классификации осуществляется за время 0((7+М2) даже если число всех гипотез экспоненциально по отношению к размеру входа.
Чтобы ответить на этот вопрос мы используем теоретико-графовую интерпретацию задачи классификации из главы 2.
Мы покажем, что для произвольной классификационного контекста и произвольного недоопределейного примера дт Є Gr, задача распознавания "(+)-гипотезы в пользу положительной классификации недоопределенного примера дт" NP-полна. В силу симметрии (—)- и (+)-гипотез, из этого следует, что задача "существует ли (—)-гипотеза в пользу отрицательной классификации дт" также NP-полна.
Эквивалентность, установленная в Лемме 2.6 позволяет нам переформулировать проблему классификации как задачу относительно четырехдольных графов, введенную в разделе 2.4. Теорема 3.10 Задача NP-полна.
Доказательство. Рассмотрим следующий частный случай задачи ДПДП. Пусть \V2\ = V3I Е тогда и только тогда когда г ф j, и двудольные подграфы, индуцированные множеством вершин V2 U Vi и У3 U V4 изоморфны как непомеченные графы (этот изоморфизм задается установлением взаимнооднозначных соответствий между вершинами из множеств V2 и У3) У\ и 4 соответственно). В этом случае множество максимальных по вложению полных двудольных подграфов двудольного графа В2 состоит из графов вида ({и?,..., v,?t}U{u}1,..., v?J, {и? ,..., v\} х . множество индексов вершин из множества V2 дополнительно к множеству индексов вершин из множества Vs. Учитывая то, что двудольные графы, индуцируемые множествами вершин V2 и Vi, V3 и V , соответственно, изоморфны, этот частный случай задачи ДПДП эквивалентен следующей задаче "доминирование взаимно дополнительными множествами вершин" (ДВМВ):
В множестве вершин Vi вершина vix ставится во взаимооднозначное соответствие литералу ХІ, а вершина Vi2 ставится во взаимооднозначное соответствие литералу -I:EJ. В множестве вершин V2 каждой дизъюнкции Dj взаимнооднозначно сопоставляется вершина Vj, п. Помимо этих 1т вершин в V\ есть еще дополнительная вершина v2m+i. Каждая переменная ХІ сопоставляется вершине vn+i Є V2, 1 і т. Пара вершин (v},Vj), где vj Є Vi, vj Є V2, смежна (связана ребром) тогда и только тогда когда имеет место один из следующих случаев:
Покажем, что булев вектор, удовлетворяющий КНФ С, существует тогда и только тогда когда граф В содержит множество вершин W\ С V\ такое что оба множества Wx и Vi\Wi доминирует над V2, т.е. соответствующая задача ДВМВ имеет решение.
Изменение устойчивости с ростом числа примеров
Представление данных с помощью формальных контекстов соответствует описанию объектов с помощью множества признаков. В случае, когда объекты имеют сложную структуру, описываемую с помощью функций и отношений на подобъектах, использование представления на основе формальных контекстов может приводить к информационным потерям.
В настоящем разделе мы рассмотрим представление данных, на которых операция сходства, позволяющая определять обобщение описания нескольких объектов, задана как полурешеточная операция. При этом данные могут иметь самую разную природу, например, быть графами или числами (числовыми интервалами). Такое представление данных было предложено в работе [28] (см. также [107]) и впоследствии рассматривалось другими авторами (см., например, [93], [111]). Ряд авторов [59], [68], [77] рассматривают конструкции, в которых, вместо признаков, объекты характеризуются некоторыми логическими формулами, которым они удовлетворяют. В таком случае, роль общих признаков нескольких объектов играют логические формулы, субсумирующие (поглощающие) формулы, соответствующие объектам. В этой главе мы покажем как наш подход, основанный на полурешетке данных, представим в рамках АФП, опишем модель обучения из главы 2 в его терминах, рассмотрим аппроксимацию гипотез, основанную на проекции и предложим процедуры точного и приближенного вычисления понятий и гипотез в рамках данного представления.
Доказательство. Для двух множеств А\ С А2 С. G в силу того, что П есть операция инфимума, имеет место А\ С А\, и условие 1 определения соответствия Галуа из раздела 1.1 выполняется: здесь в качестве оператора ф из определения соответствия Галуа выступает оператор (-)0 на подмножествах множества объектов G.
С другой стороны, для d\, di Є D таких что d\ С. d2, имеет место с?2 Е 5(g) =Ф- dx С. 5(g), и, следовательно, d\ С d\, что показывает выполнение условия 2 определения. Здесь в качестве оператора -ф из определения соответствия Галуа выступает оператор () на элементах множества называются узорными понятиями структуры (G,D, 5), с объемом А и узорным содержанием d. Для элементов а, Ь D имеет место узорная импликация а —у Ъ если а С Ь. Сходным образом, объектная импликация С —» D имеет место для C,DCG еслиСПП.
Каждая полная полурешетка имеет наибольший и наименьший элементы, которые мы будем обозначать, соответственно, О и 1. Поскольку полурешетка (Ду, П) полна, существует (единственная) операция U такая что (Д;, П, U) есть полная решетка. Эта операция задается соотношением
Для заданной узорной структуры все понятия могут быть вычислены с помощью алгоритма из главы 3, в котором оператор замыкания ()" должен быть заменен на оператор замыкания ()0 . Такой алгоритм был описан в работе [107]. Отличие вычислений в узорных структурах от вычислений в формальных контекстах заключается, во-первых, в том, что множество признаков в исходных данных в явном виде отсутствует, и вычисление узорных понятий возможно лишь в стратегии "снизу-вверх" (т.е., в смысле отношения порядка на узорных понятиях, от минимальных объемов и максимальных содержаний к максимальным объемам и минимальным содержаниям). Вторым существенным отличием является вычислительная сложность. Например, уже задача вычисления отношения С. для помеченных графов является NP-полной (в силу NP-полноты задачи ИЗОМОРФИЗМ ПОДГРАФУ [14]), а вычисление операции X П Y NP-трудно, тогда как вычисление аналогичного отношения С и операции П в формальных контекстах связано с выполнением элементарных операций на битовых строках. Таким образом, оценка сложности алгоритмов на узорных структурах должна учитывать различие в вычислениях П, С, и операциях на битовых строках.
Когда алгоритм ЗО используется для вычисления узорных понятий, то в худшем случае его временная сложность составляет 0((a+f3\G\)\G\\L\), а необходимый объем памяти 0((7GI/)), где а есть время, необходимое для вычисления операции П, fi есть время необходимое для вычисления отношения С, а 7 есть объем памяти, необходимый для хранения наибольшего объекта из D$. Вычисление диаграммы решетки в худшем случае требует 0((a\G\ +J3\G\2)\L\) времени и 0((7СЬ) памяти [107]. В случае когда операция П и отношение С суть, соответственно, теоретико-множественные операция Г) и отношение С (т.е. узорная структура становится обычным формальным контекстом) данные оценки сложности алгоритмов переходят в оценки, указанные в главе 3.
Как говорилось выше, вычисление узорных понятий может оказаться сложным не только в силу их возможного экспоненциального числа, но и в силу трудновычислимости единичного понятия. В таких случаях естественна постановка вопроса о приближении узорных структур и узорных понятий.
Приближение формализуется на основе отображения ip-.D-ї D, сопоставляющего каждому узору d Є D узор ф(й), а узорной структуре (G, 22,8) — узорная структура (G, Ц,фо8). При этом мы рассматриваем одновременно две узорные структуры. В дальнейшем символ будет всегда относится к узорной структуре (G,D, 8), а не к (G,D, ф о 8).
