И.С. Гуз
ivanguz@mail.ru
Московский физико-технический институт
(государственный университет)
Построение интерпретируемых выпуклых
композиций логических закономерностей
для задач классификации
Для решения задач классификации объектов x ∈ X, описываю-
щихся числовыми или номинальными признаками f1, ..., fn, на два
непересекающихся класса из множества Y = {−1; +1}, разработа-
но огромное количество методов, условно разделяемых на два типа.
К первому типу относятся сложные модели классификации, такие,
как нейронные сети, композиции решающих деревьев, машины опор-
ных векторов с нелинейными ядрами и т. д. Как правило, они обеспе-
чивают высокое качество классификации, но сам алгоритм остаётся
«чёрным ящиком»и не подлежит содержательной интерпретации. Ко
второму типу относятся хорошо интерпретируемые модели, в частно-
сти, решающие деревья и композиции логических закономерностей.
Логическая закономерность — это сегмент пространства X, описы-
ваемый конъюнкцией вида ϕy(x) = β1(fi1 (x)) ∧ ... ∧ βk(fik (x)), где
βj(fi(x)) = {0; 1} — некоторое элементарное условие над i-м призна-
ком. Закономерность ϕy относит все покрываемые ею объекты только
к одному из классов. Если закономерности не пересекаются и имеют
простую структуру, как в случае с решающими деревьями, то постро-
енный алгоритм получается очень наглядным и интерпретируемым.
Недостатком методов этого типа является более низкое качество клас-
сификации по сравнению с алгоритмами первого типа.
Большой интерес для приложений представляют промежуточные
типы методов, позволяющие выбирать между качеством классифи-
кации и интерпретируемостью. Один из распространенных способов
построения данных алгоритмов заключается в генерации множества
пересекающихся закономерностей с помощью таких алгоритмов, как
КОРА или ТЭМП [1], а затем построения их выпуклой композиции,
например, с помощью алгоритма AdaBoost [2]. Чем больше правил в
композиции, тем меньше она будет интерпретируемой, но тем лучше
будет её качество классификации. Недостатком AdaBoost является
то, что для достижения необходимого качества классификации, как
правило, требуется слишком много (сотни или даже тысячи) зако-
номерностей. При этом композиция в целом полностью утрачивает
свойство интерпретируемости.
Для устранения этого недостатка алгоритма AdaBoost предлага-
ется методика построения выпуклых композиций закономерностей,
пересекающихся только попарно. При этом ограничении для каждой
закономерности может существовать несколько закономерностей, с
которыми она пересекается, но сами они уже не могут пересекать-
ся между собой, что обеспечивает интерпретируемость всей компози-
ции. Дадим формальное описание этой задачи.
Дана обучающая выборка объектов {X,Y } = {(x1,y1), ...(xl,yl)}.
Построено множество закономерностей Φ = {ϕi
y : i = 1, ..., m}, кото-
рые могут пересекаться только попарно, то есть ∀x ∈ X, ∀i = j = k:
ϕi
y(x)ϕj
y(x)ϕky
(x) = 0. Необходимо подобрать такие положительные
веса α1, ..., αm правил, чтобы минимизировать количество ошибок Q
на заданной выборке:
Q =
l
i=1

yi
m
k=1
αkϕky
(xi) < 0

→ min
α1, ..., αm
.
Обозначим через N число объектов, ошибочно покрытых только
одной закономерностью или двумя закономерностями одного клас-
са. Поскольку закономерности уже построены, то N не зависит от
α1, ..., αm. Для каждой области пересечения двух закономерностей
ϕi
y,ϕj
y : yi = yj определим число ошибок Ni>j , если αi > αj, и Ni<j , ес-
ли αi < αj . Тогда количество ошибок на контроле можно переписать в виде
Q = N +

∀i,j:∃x:ϕi(x)ϕj(x)=0;yi=yj
([αi > αj ]Ni>j + [αi < αj ]Ni<j) →
→ min
α1, ..., αm
.
Минимум будет достигаться в том случае, если для каждой области
пересечения число ошибок будет равно min(Ni>j ;Ni<j). Построим
алгоритм, определяющий веса α1, ..., αm, так, чтобы данное условие
было выполнено.
1. Строим направленный граф, в котором вершинами являются
закономерности.
2. Вершины i,j соединены дугой, если закономерности i,j пере-
секаются и голосуют за разные классы. Если Ni>j < Ni<j, то дуга
направлена из вершины i в j, то есть αi > αj. Если Ni<j < Ni>j, то
дуга направлена из вершины j в i. Пример: рис. 1.
Рис. 1
3. В силу специфики конъюнкций, из которых состоят закономер-
ности, построенный граф не может иметь циклов. Слой вершин 0 бу-
дет состоять из тех вершин, в которые не входят никакие дуги. Слой
вершин 1 будет состоять из тех вершин, в которые можно попасть из
слоя вершин 0 за 1 переход, двигаясь по направлению соединяющих
их дуг. Аналогично на основе слоя вершин 1 строится слой вершин 2
и т. д., пока не будут покрыты все вершины.
4. Закономерностям, которые являются вершинами в слое 0, в про-
извольном порядке присваиваем веса 1, 2, ..., r0, где ri — число вер-
шин в слое i. Правилам, которые являются вершинами в слое 1, в
произвольном порядке присваиваем веса r0 + 1, r0 + 2, ..., r0 + r1.
Повторяем эту процедуру для всех оставшихся слоев.
Эту же методику можно применять для перерасчёта всех весов
логических правил при добавлении очередного правила в компози-
цию. Таким образом, методика позволяет оптимальным образом наращивать композицию логических правил, одновременно оставляя её
интерпретируемой...