Мультиклассовая классификация (Multiclass classification) Скачать в PDF

Синонимы: Мультиноминальная классификация

Разделы: Алгоритмы

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

Задача формулируется следующим образом. Пусть задан обучающий набор данных $S = (x_{i}, y_{i})$ , $i = 1, . . ., n$ , где $n$ — число примеров, $x_{i}$ — вектор признаков, $y_{i}$ — метка класса $i$ -го примера. Требуется построить классификатор, который для каждого $x$ будет правильно предсказывать $y$ , причем не только на обучающем множестве $S$ , но и для любых наблюдений, в него не входящих (т.е. классификатор должен обладать обобщающей способностью).

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

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

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

Один против всех (One-versus-all, OvA или один против остальных, One-versus-rest, OvR). Для каждого класса строится один бинарный классификатор. При этом примеры класса определяются как «положительные», а всех других — как «отрицательные». Итоговый результат формируется по принципу «победитель получает все»: объект будет отнесен к классу, для которого бинарный классификатор даст большее число «положительных» примеров.

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

Один против одного (One versus One, OvO). Строится $k (k - 1)$ классификаторов, позволяющих различить любую пару примеров разных классов. Алгоритм просматривает все пары примеров с разными метками классов и для каждой решает бинарную задачу $f_{i j}$ . В каждом случае для пар $(i, j)$ положительные — все примеры с метками $i$ , а отрицательными — с $j$ . Решение при этом имеет вид:

$ˆ y = a r g m a x x \in X \sum i f_{i j} (x)$ .

Недостатком метода является высокая трудоемкость: число классификаторов растет квадратично к числу примеров, в то время как у метода «один против всех» зависимость линейная.

Метод корректирующих кодов (Error-Correcting Output Codes — ECOC). Позволяет сократить число классификаторов с $k$ (как в методе OvA) до $l o g_{2} k$ . Каждый класс кодируется в виде битовой последовательности, называемой кодовым словом. Однако при наличии даже одного некорректного бита в нем метка класса будет неверной. Чтобы избежать этого, вводится избыточность в виде нескольких дополнительных битов, называемых корректирующими.

Пусть каждый класс $c_{i}$ ( $i = 1, . ., k$ ) связан с кодовым словом $w_{i} \in {0, 1}^{n}$ длиной $n$ . Обозначим $j$ -й бит $i$ -го кодового слова $b_{i j}$ . Тогда набор кодовых слов можно представить в виде кодовой матрицы $m_{i j} \in {0, 1}^{k \times n}$ , где каждая $i$ -я строка описывает кодовое слово $w_{i}$ , а столбец соответствует бинарному классификатору $f_{j}$ . Множество классификаторов обозначим как $C = (f_{1}, f_{2}, . . ., f_{n})$ .

Кодовая матрица, таким образом, описывает схему исходной мультиклассовой задачи. В каждом $j$ -м столбце $i$ -я строка содержат 1 для тех классов, обучающие примеры которых используются как положительные, и 0 — для тех, которые считаются отрицательными для данного классификатора $f_{j}$ . Например, для задачи с 4-мя классами и 6-ю классификаторами, кодовая матрица может иметь вид:

Класс	$f_{1}$	$f_{2}$	$f_{3}$	$f_{4}$	$f_{5}$	$f_{6}$
1	1	1	1	0	0	0
2	1	0	0	1	1	0
3	0	0	0	1	0	1
4	0	0	1	0	1	1

Из таблицы видно, что первый классификатор использует классы 1 и 2 как положительные примеры, а для классов 3 и 4 — как отрицательные.

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

Таким образом, для примера $x$ все бинарные классификаторы формируют предсказания, образующие вектор $y = (f_{1} (x), f_{2} (x), . . ., f_{n} (x))$ , который сравнивается с кодовыми словами для классов. Класс ${^c}_{i}$ , кодовое слово которого окажется наиболее близким к $y$ в смысле некоторой метрики $d (\cdot)$ , и будет служить общим предсказанием мультиклассового классификатора:

$^c = argmin c d (w_{c}, y)$ .

Мерой близости между двоичными векторами может служить расстояние Хемминга, определяемое как число битовых позиций, в которых предсказанный вектор $y$ отличается от кодового слова класса $w_{i}$ , т.е.

$d_{h} (w_{i}, y) = n \sum j = 1 ∣ ∣ m_{i j} - y_{j} ∣ ∣$ .

Число классификаторов превосходит количество классов, т.е. $m > k$ , что позволяет использовать более длинные кодовые слова. Поэтому сопоставление предсказанного вектора не будет искажено ошибками отдельных бинарных классификаторов.

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

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

Для этого используется дискриминационный порог: если рейтинг выше его значения, то объект относится к «положительному» классу, в противном случе — к «отрицательному».

В основе работы модели лежит функция, называемая softmax обобщение логистической функции для многомерного случая. Она преобразует вектор $z$ размерности $k$ в вектор той же размерности, каждый элемент в интервале $[0, 1]$ , сумма которых равна 1. Элементы нового вектора интерпретируются как вероятности принадлежности объекта к соответствующему классу.

Softmax-регрессия — это алгоритм машинного обучения с учителем, используемый в задачах многоклассовой классификации. В отличие от обычной логистической регрессии, в нем используется не сигмоидальная функция активации $s (z)$ , а векторная $Ψ : R^{K} \to (0, 1)^{K}$

$Ψ (z_{1}, z_{2}, . . ., z_{K}) = ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ \begin{matrix} ψ_{1} (z_{1}, z_{2}, . . . z_{K}) ψ_{2} (z_{1}, z_{2}, . . ., z_{K}) . . . . ψ_{K} (z_{1}, z_{2}, . . ., z_{K}) \end{matrix} ⎤ ⎥ ⎥ ⎥ ⎥ ⎦$ ,

где $ψ_{k} : R^{K} \to (0, 1)^{K}$ скалярная функция вида:

$ψ_{k} (z_{1}, z_{2}, . . . z_{K}) = \frac{e x p (z_{k})}{K \sum i = 1 e x p (z_{i})}$ .

Несложно увидеть, что благодаря нормирующим свойствам знаменателя $0 < ψ_{k} (z_{1}, z_{2}, . . . z_{K}) < 1$ . Кроме того, $K \sum i = 1 ψ (z_{1}, z_{2}, . . ., z_{k}) = 1$ . Эти два свойства позволяют интерпретировать данную величину как вероятность $i$ ‐го класса.

Более подробно с описанными методами можно ознакомиться в статье «Мультиклассовая классификация в машинном обучении».