Содержание к диссертации
Введение
Глава 1: Теория решеток и анализ формальных понятий 8
1.1 Частично упорядоченные множества и решетки 8
1.2 Операторы замыкания 13
1.3 Операторы замыкания и системы замыкания в полурешетке 14
1.4 Импликации 20
1.5 Анализ формальных понятий 22
Глава 2: Решетки формальных понятий в автоматическом порождении гипотез 27
2.1 Импликации и ассоциативные правила 29
2.2 ДСМ-метод 34
2.2.1 ДСМ-метод в терминах анализа формальных понятий: Основные определения 34
2.2.2 О пользе итерации 36
2.2.3 Варианты ДСМ-гипотез 50
Глава 3: Алгоритмы построения решеток формальных понятий и их применение для порождения гипотез 59
3.1 О принципах сравнения 60
3.2 Обзор алгоритмов 66
3.2.1 Борда 66
3.2.2 Следующее замыкание 77
3.2.3 Замыкай по одном)' 80
3.2.4 Лпнднг 85
3.2.5 Шен 87
3.2.6 Нурпн 90
3.2.7 Норрпс 91
3.2.8 Годан 93
3.2.9 Добавь атом 96
3.2.10 Другие алгоритмы 103
3.3 Эксперименты 105
3.4 Алгоритмы порождения понятий в машинном обучении 115
Глава 4: Алгоритмы построения базиса импликаций 118
4.1 Алгоритм Гантера вычисления базиса Дгокенна-Гига 118
4. 2 Пошаговый алгоритм вычисления базиса Дюкенна—Гита 120
4.2.1 Типы импликаций 121
4.2.2 Описание алгоритма 126
4.2.3 Экспериментальное сравнение 132
Глава 5: Рассуждение в условиях частичной информации: Неполные контексты 134
5.1. Постановка задачи 134
5.2 Оценка формул с помощью логики Клини 138
5.3 Модальная логика для неполных контекстов 139
5.3.1 Модальная логика бессмыслицы 140
5.3.2. Применение модальной логики бессмыслицы для оценки формул в неполных контекстах 147
Заключение 151
Литература 153
- Операторы замыкания и системы замыкания в полурешетке
- ДСМ-метод в терминах анализа формальных понятий: Основные определения
- Алгоритмы порождения понятий в машинном обучении
- Пошаговый алгоритм вычисления базиса Дюкенна—Гита
Операторы замыкания и системы замыкания в полурешетке
Задача классификации может быть (грубо) сформулирована следующим образом. Дано множество объектов (а также описания этих объектов в некотором языке) и его разбиение на непересекающиеся классы. Есть некоторый «неклассифищгрованный» объект (и его описание), который требуется отнестп к одном) из классов. Предполагается, что решіггь эту задач)7 можно, проанализировав описания объектов, уже входящих в классификацию.
В дальнейшем мы будем использовать язык анализа формальных понятий. В частности, мы будем рассматрігвать ДСМ-метод в форлгулировке, близкой к той, что была предложена в работе (Ganter, Kuznetsov, 2000), где гипотезы ДСМ-метода определяются в терминах анализа формальных понятий. Оговоримся, что хотя в формальных контекстах мы имеем дело с объектами, описанными посредством признаковых множеств, ДСМ-метод способен работать не только с такими объектами, но с объектами произвольной структуры, для которой определена полурешеточная операция. Тем не менее, основная теорема анализа формальных понятий позволяет без особого труда перенести большую часть теоретических результатов, полученных для формальных контекстов, на произвольную решетку (и полурешетку).
Итак, пусть имеется обучающий контекст К — (Gm, Мш, LA с оператором Галуа . G„, = G, LJ ... VJ Gn для некоторого ;; 1, GtС\ G — 0 для любых г Ф], т.е. множество объектов разбито на классы (эквхгвалентности). Объекты из Gt будем называть положительными примерами класса /, а объекты из G \ G, — отрицательными примерами класса і. Будем также рассматрігвать контексты Если hid — {і}, то будем иногда опускать фигурные скобки: например, вместо Кщ будем писать К;.
Спрашивается: на основании каких признаков тот или иной объект относят к том}7 или иному классу? Более формально: нас интересуют зависимости вида А Ь і, интерпретируемые как «всякий объект, обладающий всеми признаками из A cz Мш, относится к классу г». Если зависимость А Ъ і принимается, то она (а также множество признаков А) называется гипотезой о принадлежности к классу і. Говорим, что гипотеза А і применима к объекту7 g или что гипотеза А входит в объект (описание объекта, содержание объекта) g, если А С g .
Позднее, такие зависимости могут быть использованы для классификации новых («педоопределенных») объектов. Возможны разные способы классификации. Самый простой вариант построения классификации таков: если к объекту7 применима гипотеза о принадлежности к классу і и не применима ни одна гипотеза о принадлежности к другому классу, то объект относят к классу /. Существуют и другие варианты: напрішер, для каждого класса можно подсчитать количество гипотез о принадлежности к этом)7 класс)7, применимых к классифицируемому объекту, и приписать его к классу, для которого число таких гипотез максимально (такой подход называется голосование . Вероятно, имеет смысл подсчитывать только минимальные гипотезы, т.е. такие А - /, что для любого В г А, В - / гипотезой не является. Представляется разумным также и такой подход: присвоить вес каждой гипотезе в зависимости от ее размера (У4; коэффициент надежности) и числа объектов в соответствующем объеме (\А ; ср. решетки-айсберги (Stumme et aL, 2000) и поддержка в ассоциативных правилах, о которых ниже (Agrawal et al, 1993)). Тогда, объект признают принадлежащим некотором}7 классу, если сумма весов применимых к нему гипотез о принадлежности к этом} классу7 больше, чем сумма весов применимых к нему гипотез о принадлежности к любом} другому классу (вариант: больше, чем сумма весов всех прочих применимых к нем}7 гипотез).
Каким образом порождаются гипотезы? На каком основании та или иная зависимость считается адекватной исходным данным? Разумеется, возможны разные подходы к этом} вопросу, что и определяет многообразие существующих определений гипотез и, соответственно, методов. Предметом настоящей работы в основном являются алгоритмические аспекты порождения гипотез для разных методов. При этом мы не станем подробно останавливаться на практических преимуществах того или иного метода с точки зрения оправданности порождаемых им гипотез.
Наверное, наиболее очевидным определением гипотезы является следующее: множество признаков Л с Ain считается гипотезой о принадлежности к класс) г, если всякий объект из G обладающий всеми признаками из А (т.е. g, такой что А с gJi), относится к классу /.
Будем называть такие гипотезы импликативными; импликатігеной является любая мыслимая гипотеза (т.е. любое выражение на языке описания гипотез), не имеющая контр-примеров (в данном наборе объектов).
Такое определение исходит из того, что все признаки взаимосвязаны. Действительно, если множество объектов G„ пусто, то любое подмножество признаков является гипотезой о принад\ежности к любому классу і (заметим в скобках, что в таком случае всякое G; = 0).
Постепенный отказ от изначальной установки на тотальную зависимость происходит при столкновении с реальными данными. Как только мы встречаемся с объектом, не принадлежащим класс) г, так тут же мы отказываемся от всех гипотез А і, где А — любое подмножество признаков, содержащігхся в данном объекте.
Итак, данный подход предполагает согласие с любым утверждением, не имеющим контр-примера в наблюдаемом мігое. Таким образом, множество А, не входящее в содержание ни одного объекта, будет считаться гипотезой о принадлежности к любом)7 классу. Пожалуй, лучше избегать подобных гипотез: с точки зрения здравого смысла, это и не гипотеза вовсе, ведь, по сути, она не добавляет шгчего к нашем}7 пониманию мира; напротив, она затрудняет классификацию, поскольку всякий объект, содержащий ее, автоматігчески содержит гипотезы, противоречащие друг другу. Поэтом)7 кажется естественным потребовать также, чтобы гипотеза подтверждалась хотя бы одним примером, хотя бы однігм наблюдением. В протігвном случае, определение гипотезы о принадлежности классу / зависит исключительно от отрицательных примеров класса / . Хотя такое определение через отрицание не обязательно должно быть «плохим» само по себе, все же, обучение только на отрицательных примерах вряд ли можно признать обоснованным.
ДСМ-метод в терминах анализа формальных понятий: Основные определения
ДСМ-метод был предложен как логическая теория правдоподобного вывода (Anshakov et al, 1989; Финн, 1991), формализующая идеи Джона Стюарта Милля (Mill, 1843). В работе (Ganter, Kuznetsov, 2000) фрагмент этой теоріпг изложен в терминах анализа формальных понятий. В дальнейшем мы будем использовать СХОДігую терминологию.
Милль определил несколько правил правдоподобного вывода, из которых наиболее активно в ДСМ-методе используется метод сходства:
«Если два или более случая исследуемого явления сходны лишь в одном обстоятельстве, это обстоятельство, в котором только и согласуются все случаи, есть причина (или следствие) данного явления»
Таким образом, ДСМ-ліетод как метод классификации принципиально применим к объектам, на множестве описаний которых определена полурешеточная операция, интерпретируемая как операция сходства. Анализ исходных данных включает в себя нахождение «сходств» объектов, т.е., фрагментов описания, получаемых применением операции сходства к описаниям двух или более объектов. При выполнении некоторых дополнительных условий, сходство объектов одного класса рассматривается как фрагмент описания, отвечающий за принадлежность объекта этому классу. Наиболее популярным из таких дополнительных условий является запрет на контрпример, т.е. на вхождение сходства в описание исходных объектов другого класса. Порожденные сходства используются для классификации неклассифицированных объектов.
Итак, ДСМ-ліетод способен работать с любыми описаниями объектов, для которых определена полурешеточная операция сходства. Однако из любой полурешетки легко получить решетку добавленіїем минимального (или максимального) элемента, а любая полная (в частном случае конечная) решетка представігма в виде решетки форліальньгх понятий. Поэтолгу мы будем использовать терлшнолошю анализа форліальньїх понятий (Ganter, Wille, 1999), предполагая, что описания объектов — это множества признаков из некоторого универсума. Операции сходства в данном случае соответствует теоретико-множественное пересечение, а вхождению фрагмента описания в описание объекта — теоретико-множественное вложение. Пршюдішьіе ниже определения и утверждения могут быть обобщены для произвольной решетки. Мы используем множества признаков для того, чтобы сделать изложение более простым и понятным, и чтобы яснее отобразить место ДСМ-метода гипотез среди гипотез, порождаемых прочими рассматриваемыми методами (такими как ассоциативные правила).
В простом ДСМ-методе, гипотеза о принадлежности к классу есть сходство двух или более объектов этого класса, не являющееся сходством никаких объектов за пределами этого класса. То есть:
Обычно ДСМ-метод излагают в применении к двум классам: положительных и отрицательных примеров. В такой постановке гипотезу о принадлежности к классу положительных примеров называют положительной гипотезой, а гипотезу о принадлежности к классу отрицательных примеров — отрицательной гипотезой. Тогда, например, положительная гипотеза есть содержание положительного контекста, не являющееся содержанием отрицательного контекста, входящее не менее чем в два положительных примера. Определение 2.4 можно переформ)глігровать, пользуясь только контекстом Кгп:
Множество А С М,ц называется простой АСМ-гипотезой о принадлежности к классу і в контексте Кш —
Простые ДСМ-пгаотезы слишком уж не надежны, они не накладывают никаких огранггчений на количество контр-примеров, поэтолгу их обычно комбинируют с дополнительными условиями. Так, наиболее часто используемым вариантом ДСМ-метода, по-видимому, является ДСМ-метод с запретом на контр-прпмер:
Определение 2.5. Множество Л С AfQ называется /\СМ-гипотезой с запретом на контр-пример (пли импликативной /\СМ-гипотезой) о принадлежности к классу і в контексте Кт = (GrJ, -М ю), если является одновременно простой ДСМ-гппотезой и нмпликативноіі гипотезой о принадлежности к классу /.Другими словами, Л С М является ДСМ-пшотезой с запретом на контр-прнмер о принадлежности к классу г, если Л — Л и А. с G7,
Получив гипотезы, их обычно используют для классификации. После того как классификация объекта совершилась, появляются новые данные: описание этого объекта и информация о принадлежности объекта к тому или иному классу. Эти данные можно использовать при дальнейшей классификации объектов. Когда классификация объекта приводит к возникновению, действительно, «полезной» информации, то есть, позволяющей определить класс объекта, для которого этого нельзя было сделать, располагая только исходными данными? Этом} посвящен следующий раздел.
В общем виде сформулируем проблем} так: появится ли новое сходство описаний объектов одного класса при добавлении к множеству исходных объектов нового объекта, приписанного к этолгу классу? Множество сходств описаний объектов образует полурешетку, что позволяет дать теоретико-решеточный ответ на поставленный вопрос.
Нас будет в основном интересовать решетка содержаний контекста К, которую мы обозначим как
Лз(К)- Диі решеткіг содержаний естественно использовать порядок, обратный порядку в решетке понятий. Решетку понятой мы будем рисовать тоже в соответствии с этим порядком, т.е., «вверх ногами».
Алгоритмы порождения понятий в машинном обучении
Не для всякой задачи обязательно порождение всех понятий. Например, алгоритмы порождения решеток понятий применяются к множеству объектов, разделенном} на подмножества положительных и отрицательных примеров некоторого свойства. В такой постановке, авторам оказываются необходимы только понятия, в определенном смысле, релевантные этому свойству. Релевантность определяется с помощью энтропии. При порождении ассоциативных правил интересны только понятия с размером объема не ниже заданного и т.д. (Pasquier et aL, 1999b, с). В простом варианте ДСМ-метода гипотеза о причине формулируется с использованием некоторого монотонного предиката, в частности, запрета на контрпример; иногда применяются более слабые статистические эвристики (Григорьев, 2000). Поэтом)7 бывает достаточно вычислить только наиболее общие понятия, удовлетворяющие предикату. Исследованные в данной работе алгоритмы вполне могут быть адаптированы для этой цели. Вариант алгоритма Борда, основанный на идее постепенного поиска минимальных пересечений, не порождающий надмножеств пересечений, удовлетворяющих некоторому предикату, приведен в (Объедков, 1999). Чтобы использовать алгоритм Норриса для порождения всех положительных (отрицательных) гипотез ДСМ-метода с запретом на контр-пример, достаточно на шаге 2 инициализировать CurG не пустым множеством объектов, а множеством отрицательных (соответственно, положительных) примеров, а процедуру Add выполнить только для положительных (соответственно, отрицательных) примеров. Этот алгоритм является главным в действующей ДСМ-снстеме (Панкратов, 2001). Помимо высокой производительности, его достоинством является универсальность: он может быть использован везде, где определена полурешеточная операция сходства.
Покажем, как аналопгчный алгоритм может быть использован для порождения гипотез метода разлігчия, описанного в Разделе 2.2.3.1. Конечно, можно напрямую использовать любой алгоритм порождения гипотез метода сходства, применив его к контекст)7 Ка. Однако, в некоторых случаях способ представления данных делает неэффекпгоным, а то и вовсе невозможным использование операции дополнения. Например, в экспериментах, результаты которых мы сообщили в (Grigoriev et ctL, 2002), данные были представлены в виде многозначного контекста. Мы могли воспользоваться шкалированием, но было решено рассматрігеать объекты как кортежи и реализовать операции сходства и различия непосредственно для кортежей. В такой ситуации вряд ли возможно предоставить эффекпгвную реализацию дополнения.
Итак, приведем алгоритм, основанный на идеях Норрпса, но вычисляющий положительные гипотезы метода различия для К+ и К_ с использованием только операций сходства и разлігчия (отрицательные гипотезы могут быть вычислены аналопгчно):
В отличие от алгоритмов построения решеток понятий, известно не так уж много алгоритмов построения базиса импликаций. Собственно говоря, в литературе упоминается лишь один претендующий на эффективность алгоритм, непосредственно строящий канонический базис импликаций (базис Дюкенна—Гига), именно, алгоритм Гантера, являющийся, по сути, модификацией его же алгоритма «Следующее замыкание». Помимо этого алгоритма, существуют алгоритмы построения других базисов импликаций: прямого базиса (Mannila, Raiha, 1992; Wild, 1994), собственного базиса (Taouil, Bastide, 2001) и т.д. К выходу этих алгоритмов можно применить процедуру, преобразующую базис к каноническому виду. Такой подход оправдан, если алгоритм быстр, размер его выхода невелик (относительно 2Л/ ), а процедура канонизации эффективна.
В данном разделе мы пред\агаем новый алгоритм построения базиса импликаций, который был разработан нами совместно с В. Дюкенном. Это пошаговый алгоритм, добавляющий на каждом шаге новый признак; он позволяет добиться значительного увеличения скорости по сравнению с алгоритмом Гантера. Однако сначала мы опишем алгоритм Гантера.
Алгоритм Гантера «Следующее замыкание» замечателен своей ушгверсалыгостью. Пусть S — некоторое множество, а с. 2s - 2s — произвольный оператор замыкания. Тогда алгоритм «Следующее замыкание» может быть использован для порождения всех с-замкнутых подмножеств S.
Напомним, что замкнутые и псевдозамкнутые множества (в нашем случае — содержания и псевдосодержания) вместе образуют новую систем) замыканий (см. Утверждение 1.31), которой соответствует новый оператор замыкания — оператор насыщения, в контексте данной главы обозначим его — определяемый следующим образом:
Таким образом, вычислить А можно, воспользовавппгсь каноническим базисом импликаций, и даже лишь теми его импликациями, посылки которых содержатся в А . Это дает возможность использовать «Следующее замыкание» для вычисления всех множеств, замкнутых относительно , т.е. всех содержаний и псевдосодержаний контекста. Если очередное порожденное множество А оказывается незамкнутым относительно ", то оно псевдозамкнуто, и в базис добавляется импликация А А". Алгоритм «Следующее замыкание» порождает множества в порядке А В С5 rnin((/3 \J В) \ (А О В)) є В; в частности подмножества порождаются раньше своих надмножеств. К моменту, когда алгоритму «Следующее замыкание» нужно будет вычислить А , он уже будет располагать всеми импликациями базиса вида В - В" с В (Z А и с их помощью сможет вычислить ./4 .
Как и при вычислении решетки понятий, здесь используется проверка каноничности, предполагающая линейный порядок на признаках1.
Для вычисления насыщения А, т.е. А мы используем «наивную» процедуру Saturate. Существуют и другие алгоритмы, вычисляющие замыкание множества по набору импликаций: широко известный в теории реляционных баз данных алгоритм LinClosure (Мейер, 1987), нелинейная по времени но, по утверждению автора, улучшенная версия LinClosure (Wild, 1994) и т.п.
Предлагаемый ниже алгоритм позволяет строить базис импликаций постепенно, добавляя признак за признаком. Понятно, что каждый следующий признак не отменяет прежние импликации, но только добавляет новые. Однако новый признак может произвольным образом изменить множество псевдозамкнутьгх элементов, поэтомлт неверно думать, что с добавлением признака размер канонического базиса непременно увеличится.
Без потери общности предположим, что контекст имеет вид К — (G, М = {1, ..., \М\ }, I). Д\я / є [О, М], К; — (G, М;— {т 0 т i], I n G х М) — контекст с оператором Галуа . Понятия, объемы, содержания, псевдосодержанпя и т.д. контекста Щ будем называть /-понятиями, /-объемами, /-содержаннями, /-псевдосодержаниями и т.д.
Пошаговый алгоритм вычисления базиса Дюкенна—Гита
Допустсшость (выполнимость) произвольной пропозициональной формулы в неполном контексте определяется аналопгчно том)г, как определяется допустимость импликации, а допустимость (выполнимость) множества произвольных пропозициональных формул определяется аналогично тому, как определяется допуспшость множества импликаций.
Важно суметь построить логику, которая по неполному контексту и пропозициональной формуле позволяла бы установить, выполняется ли эта формула в данном контексте и выполнима ли она в нем. Более того, такая логика должна предоставлять средства для оценки выполнимости множества формул. Другие связки определяются как обычно: л- V у — -і(-ілг & —у), х - у — —\(х & —у) и т.д. Импликация должна получить значенпе «+», если она выполняется, значенпе «?» — если она не выполняется, но допустима, н значение «—» — если она недопустима в данном контексте.
Каждой паре (g, да), g є G, т Є М, сопоставляется пропозициональная переменная, значение которой определяется функцией J(g, т). Значение импликации А $ В в контексте К — конъюнкция значений соответствуїощігх импликаций на объектах контекста: Однако, как отмечено в (Burmeister, Holzer, 2000), логика Клшш не всегда способна адекватно оценить значенпе импликации (впрочем, и любой другой формулы), если последняя содержит несколько вхождений некоторой пропозициональной переменной. Эту логику легко ввести в заблуждение, предложігв ей необходимую (или, напротив, невыполнимую) формулу, содержащую, по крайней мере, два вхождения одной переменной, которой присвоено значение «?»; логика Клинп не всегда способна справиться с такими формулами. В частности, импликация {т) - {да} получает значение «?» всякий раз, когда контекст содержит, по крайней мере, одни объект g, такой что J(g, т) — «?», вопреки тому, что такая импликация выполняется в любом неполном контексте.
Тем не менее, логика Клини корректно вычисляет истинностное значение пропозициональной формулы, в тех случаях, когда формула не содержит повторных вхождений пропозициональных переменных. Поэтому, если требуется только метод для оценки импликации А " В, мы вполне можем применить аппарат логики Клини к импликации А Ь В / А, эквшзалентной импликации А $ В. Таким образом, формула, соответствующая импликации А -$ В в контексте К принимает следующий вид:
К сожалению, не представляется возможным оценить выполнимость множества импликаций средствами логики Клини.
Пример 5.8. Рассмотрігм множество импликаций D — {с - d, d b} и контекст i Q, из Примера 5.3. Каждая импликация из D выполшгма в К ; однако, множество импликаций D невыполнимо в KQ, поскольку входящие в него импликации выполняются лишь в разных пополнениях D. В логике Клини, обе импликации получают истинностное значение «?», что правильно. Кажется, что множество импликаций наиболее естественно представлять в виде конъюнкции форлгул, соответствующих импликациям, содержащимся в этом множестве:
Однако в логике Клини данная форм)тла гарантированно принимает адекватное истинностное значение, только когда множество импликаций выполняется или когда оно содержит невыполнимую импликацию. Это объясняется тем, что вьініепрігаеденная формула не учитывает совместимость импликаций. Когда множество содержит несколько импликаций, в которых задействован один и тот же признак, данная формула обязательно содержит повторные вхождения этого признака. (На самом деле, это опасно только, когда одпн и тот же признак встречается в посылке одной и в заключении другой импликации.) Таким образом, логика Клини оказывается неспособной предоставить удовлетворительное решение задачи оценки выполнимости произвольной пропозициональной формулы и множества формул. Чтобы получить адекватное истинностное значение пропозициональной форм}тлы средствами логики Клини, необходимо преобразовать формулу так, чтобы она не содержала повторных вхождений одной и той же переменной.
Возможно, сложности, возникающие при применении трехзначных пропозициональных логик к оценке формул в неполных контекстах, связаны с принципиальным отлігчием истинностного значения «?» от «+» и «—»: это всего лишь замена одного из двух других значений. Напомним, что в неполных контекстах «?» интерпретируется как неизвестно , а не как, например, неприменимо ; «?» не имеет отношения к миру, описываемом}" контекстом, но только к нагнем}" знанию о нем. В «реальном» мире признаки не могут ггметь значение «?». Ячейка контекста, заполненная «?» лишь указывает на существование двух возможностей ее заполнения — «+» или «—» — но, «на самом деле», реализуется только одна из этих возможностей. Итак, зиаченне «?» относится к миру наших знаний о внешнем мире, описанном контекстом, но нас интересуют зависимости именно в этом последнем мггре.
Другая проблема заключается в том, что и формула, и ее отрицание могут быть невыполнимыми. Логики, строящие оценку формулы только на основе истинностных таблиц, не сумеют справиться с этим.
В основательной работе (Holzer, 2001), посвященной неполным контекстам, прігзодится непротиворечігвая и полная система вывода для необходимых импликаций, непротиворечігаая и полная система для выполшгмых импликаций и непротиворечивая н полная система для необходимых пропозициональных формул над заданным множеством признаков. Нет, однако, системы вывода для выполнимых пропозициональных форлгул. Такой механизм желателен, например, для того, чтобы уметь оценить совместимость форлгул (выполнимость несколькігх формул в одном и том же пополнении неполного контекста). Кроме того, чтобы применить систем\т вывода для импликаций, необходимо иметь некоторый начальный набор импликаций, не предоставляемый контекстом непосредственно.
