Многоклассовая и многометочная классификация

Каждый классификатор этого раздела, от логистической регрессии до ядерного SVM, разделяет два класса. В большинстве реальных задач их больше: десять цифр, несколько десятков категорий товаров, словарь из десятков тысяч слов у языковой модели. В других задачах одному объекту приписывают несколько меток: новостная статья может быть одновременно о политике и об экономике. В этой заметке разобраны три способа справиться с $K \gt 2$ классами в линейных моделях: разбить задачу на бинарные или обобщить логистическую регрессию до одной модели с $K$ выходами, softmax, который служит выходным слоем почти любого нейросетевого классификатора. Затем метрики из заметки о метриках классификации приспосабливаются к многим классам, и разбирается случай нескольких меток на пример.

Обозначения. Классы $1, \dots, K$; обучающая выборка $(x_i, y_i)$, $i = 1, \dots, n$, где $x_i \in \mathbb R^d$ и $y_i \in \{1, \dots, K\}$. One-hot-вектор метки — $\mathbf y \in \{0, 1\}^K$ с единственной единицей на позиции $y$. У линейной многоклассовой модели есть матрица весов $W$ со строками $w_1, \dots, w_K$ и смещения $b_k$; оценки (scores, логиты) равны $z_k = \langle w_k, x\rangle + b_k$, а $p = (p_1, \dots, p_K)$ — вектор предсказанных вероятностей классов. В многометочном случае целевая переменная — вектор $\mathbf y \in \{0, 1\}^K$ с любым числом единиц. $\mathrm{TP}_k$, $\mathrm{FP}_k$ и $\mathrm{FN}_k$ — число истинно положительных, ложноположительных и ложноотрицательных ответов для класса $k$ против остальных.

Сведение к бинарным задачам#

Один против всех#

Обучим $K$ бинарных классификаторов; классификатор $k$ отделяет класс $k$ (метка $+1$) от всех остальных (метка $-1$) и выдаёт оценку $f_k(x)$. Предсказываем класс с наибольшей оценкой, $\hat y = \arg\max_k f_k(x)$. Стоимость — $K$ бинарных обучений на всех $n$ примерах. Если вместо argmax брать знак каждого классификатора, остаются области, на которые не претендует ни один классификатор или претендуют несколько (Bishop, 2006, §4.1.2); argmax снимает неоднозначность, но приносит свои проблемы:

• Оценки в разных масштабах. Каждый классификатор обучается сам по себе, так что ничто не делает $f_3(x) = 2$ сравнимым с $f_7(x) = 2$. Для SVM, оценки которого не являются вероятностями, это реальная проблема; помогают откалиброванные вероятности.
• Несбалансированность по построению. При десяти сбалансированных классах каждая бинарная задача — 1 против 9.
• Класс между другими. Линейная оценка для «класса $k$ против остальных» не может быть высокой в полосе и низкой по обе стороны от неё, поэтому бинарная модель среднего класса задана неверно. Argmax нескольких линейных оценок всё равно может вырезать полосу; беда в том, что каждая оценка обучается отдельно, на своей бинарной задаче.

Последняя проблема не зависит от объёма данных. Возьмём три класса на прямой, где $x$ распределён нормально с дисперсией 1 вокруг $-2$, $0$ и $2$, и обучим оба подхода на самом распределении:

Рисунок

Один против всех и softmax на трёх классах

Лучший линейный логит для среднего класса постоянен, поэтому его модель «один против всех» везде предсказывает $1/3$, и класс 2 побеждает только там, где обе крайние модели опускаются ниже $1/3$, при $\lvert x\rvert \lt 0.70$ вместо оптимального $\lvert x\rvert \lt 1$. Его полнота падает с $0.68$ до $0.51$, а доля правильных ответов (accuracy) — с оптимальной $0.788$ до $0.774$. В высокой размерности такие конфигурации встречаются реже, и с хорошо регуляризованными бинарными классификаторами схема «один против всех» часто не уступает по доле правильных ответов ничему другому (Rifkin and Klautau, 2004); но пример показывает, в чём это сведение ошибается. Дело не в выразительности: argmax оценок «один против всех» действительно образует полосу, а то же семейство из трёх линейных оценок содержит оптимальное правило, ведь argmax $(-2x - 2,\ 0,\ 2x - 2)$ выбирает класс 2 ровно при $\lvert x\rvert \lt 1$. Подводит обучение. Каждая бинарная логистическая модель подгоняется отдельно к апостериорной вероятности, которая не логистична по $x$ (для среднего класса она растёт, а потом падает), и три неверно заданные подгонки не складываются в оптимальные границы.

Каждый против каждого#

Обучим классификатор для каждой пары классов, всего $K(K-1)/2$ классификаторов, каждый только на примерах своих двух классов; предсказываем голосованием большинства, а равенство голосов разрешаем по сумме оценок. Каждая задача мала и сбалансирована: около $2n/K$ примеров при сбалансированных классах. Если обучение на $m$ примерах стоит $m^a$, то «один против всех» стоит $K n^a$, а «каждый против каждого» — $\tfrac{K(K-1)}{2}(2n/K)^a$. Для алгоритма с линейным временем, $a = 1$, оба стоят около $Kn$; для ядерных SVM, где $a$ около 2, «каждый против каждого» стоит около $2n^2$ против $Kn^2$, в пять раз меньше при десяти классах. Поэтому LIBSVM и построенный на нём SVC из scikit-learn используют схему «каждый против каждого» (one-vs-one; Hsu and Lin, 2002). Платить приходится при предсказании: $K(K-1)/2$ вычислений, 45 для десяти классов, и к тому же каждый попарный классификатор голосует и за точки из остальных $K - 2$ классов, которых он никогда не видел.

На десяти цифрах из scikit-learn (1797 изображений $8 \times 8$ пикселей, половина для теста) с L2-регуляризованной логистической регрессией в качестве бинарного алгоритма схема «один против всех» с 10 моделями достигает доли правильных ответов на тесте $0.953$, а «каждый против каждого» с 45 моделями — $0.966$. Одна мультиномиальная модель, предмет следующего раздела, достигает $0.963$. Сведения не ограничиваются этими двумя схемами: коды, исправляющие ошибки (error-correcting output codes), сопоставляют каждому классу двоичное кодовое слово и обучают по классификатору на каждый бит (Dietterich and Bakiri, 1995), а совместные постановки, такие как многоклассовый SVM Crammer and Singer (2001), обучают все $K$ оценочных функций в одной задаче оптимизации.

Мультиномиальная логистическая регрессия#

Одна модель с $K$ линейными оценками, превращёнными в распределение вероятностей, избегает всех трёх проблем: оценки обучаются вместе, в одном масштабе, по одному правдоподобию.

Почему softmax от линейных функций. Форму апостериорного распределения даёт формула Байеса. Пусть классы имеют априорные вероятности $\pi_k$ и гауссовские условные плотности $N(\mu_k, \Sigma)$ с общей ковариацией. По формуле Байеса $P(y = k \mid x) \propto \pi_k \exp\big(-\tfrac12 (x - \mu_k)^\top \Sigma^{-1} (x - \mu_k)\big)$. Если раскрыть квадратичную форму, слагаемое $-\tfrac12 x^\top \Sigma^{-1} x$ одинаково для всех классов и сокращается при нормировке, и остаётся

$$P(y = k \mid x) = \frac{e^{z_k}}{\sum_{j} e^{z_j}}, \qquad z_k = \langle \Sigma^{-1}\mu_k,\ x\rangle - \tfrac12 \mu_k^\top \Sigma^{-1}\mu_k + \log \pi_k ,$$

нормированная экспонента линейных функций от $x$ (см. многомерное гауссовское распределение; Bishop, 2006, §4.2). Мультиномиальная логистическая регрессия сохраняет эту форму и подбирает веса напрямую, не предполагая гауссовости. Для трёх классов с рисунка $z_k = \mu_k x - \mu_k^2/2 = (-2x - 2,\ 0,\ 2x - 2)$, и обученная модель в точности воспроизводит это апостериорное распределение.

Модель и её функция потерь. Softmax переводит вектор оценок в вектор вероятностей:

$$p_k = \operatorname{softmax}(z)_k = \frac{e^{z_k}}{\sum_{j=1}^K e^{z_j}} .$$

Экспонента делает каждый элемент положительным, а деление — сумму равной 1; наибольшая оценка получает наибольшую вероятность, а оценка, сильно превышающая остальные, забирает почти всю вероятность — отсюда и название, мягкая версия argmax. Модель обучается методом максимального правдоподобия при категориальном распределении: отрицательный логарифм правдоподобия одного примера равен

$$L = -\log p_{y} = -\sum_{k} \mathbf y_k \log p_k = -z_y + \log \sum_{j} e^{z_j} ,$$

это кросс-энтропия (cross-entropy) между one-hot-меткой и предсказанным распределением в смысле заметки об энтропии курса генеративных моделей. При $K = 2$ это логистическая функция потерь.

Рисунок

Softmax, кросс-энтропия и градиент p − y

1. Линейный слой даёт по оценке на класс: при $x = (2, 1)$ и весах с рисунка $z = (2.0, 1.0, 0.1)$.
2. Softmax: $e^{z} = (7.389, 2.718, 1.105)$, в сумме $11.212$, так что $p = (0.659, 0.242, 0.099)$.
3. Верный класс — 1, и функция потерь равна $-\log 0.659 = 0.417$.
4. Градиент по оценкам равен $p - \mathbf y = (-0.341, 0.242, 0.099)$.

Градиент $p - \mathbf y$. Продифференцируем $L = -z_y + \log\sum_j e^{z_j}$ по $z_k$: первое слагаемое даёт $-[k = y]$, второе — $e^{z_k}/\sum_j e^{z_j} = p_k$. Значит,

$$\frac{\partial L}{\partial z} = p - \mathbf y, \qquad \frac{\partial L}{\partial W} = (p - \mathbf y)\, x^\top, \qquad \frac{\partial L}{\partial b} = p - \mathbf y ,$$

где вторая формула следует из $z = Wx + b$ по правилу дифференцирования сложной функции. Градиент — это «предсказанное минус наблюдаемое», тот же шаблон, что у остатка в методе наименьших квадратов и у $p - y$ в бинарной логистической регрессии. Шаг градиентного спуска повышает оценку верного класса пропорционально $1 - p_y$ и понижает каждую другую оценку пропорционально её вероятности; пример, который модель уже уверенно классифицирует верно, почти ничего не вносит.

Функция потерь выпукла по оценкам. Вторые производные равны $\partial p_k / \partial z_j = p_k([k = j] - p_j)$, так что гессиан равен $H = \operatorname{diag}(p) - pp^\top$, и для любого вектора $v$

$$v^\top H v = \sum_k p_k v_k^2 - \Big(\sum_k p_k v_k\Big)^2 = \operatorname{Var}(v_Y), \qquad Y \sim \text{Categorical}(p) ,$$

а это дисперсия, следовательно, она неотрицательна. Оценки линейны по $W$ и $b$, поэтому функция потерь на обучающей выборке выпукла и по параметрам, и градиентный спуск или метод Ньютона находит её минимум.

Инвариантность к сдвигу оценок. У гессиана есть одно направление нулевой кривизны: $v = (1, \dots, 1)$, для которого всегда $v_Y = 1$, и дисперсия равна 0. Прибавление одной и той же константы $c$ ко всем оценкам умножает числитель и знаменатель softmax на $e^c$:

$$\operatorname{softmax}(z + c\mathbf 1) = \operatorname{softmax}(z) .$$

Отсюда три следствия. Во-первых, параметры неидентифицируемы: прибавление одного и того же вектора $v$ к каждому $w_k$ и одного и того же числа к каждому $b_k$ сдвигает все оценки на $\langle v, x\rangle + c$ и не меняет ни одной вероятности. Поэтому один класс можно сделать опорным с $w_K = 0$, $b_K = 0$; при $K = 2$ это даёт $p_1 = e^{z_1}/(e^{z_1} + e^{z_2}) = \sigma(z_1 - z_2)$, бинарную логистическую регрессию. С L2-штрафом веса становятся единственными: из всех эквивалентных наборов весов штраф выбирает набор с наименьшей нормой, в котором веса классов в сумме дают ноль. scikit-learn не штрафует свободные члены, поэтому они по-прежнему определены лишь с точностью до общего сдвига, а его солверы возвращают тот представитель, у которого свободные члены в сумме дают ноль: L-BFGS стартует из нуля, а у градиента по свободным членам, суммы векторов $p - \mathbf y$ по примерам, компоненты всегда в сумме дают ноль, так что итерации не покидают это множество. Поэтому подобранные свободные члены на рисунке равны $(-0.667, 1.333, -0.667)$, а не $(-2, 0, -2)$: то же апостериорное распределение, сдвинутое на $4/3$. Во-вторых, сдвиг — стандартная численная защита. Для $z = (1000, 999)$ величина $e^{1000}$ переполняется, и наивная формула возвращает неопределённые значения; если сначала вычесть максимум, получится $\operatorname{softmax}(0, -1) = (0.731, 0.269)$, а функцию потерь вычисляют как $-z_y + \max_j z_j + \log\sum_j e^{z_j - \max_j z_j}$. В-третьих, значение имеют только разности оценок, поэтому гауссовское слагаемое $x^\top\Sigma^{-1}x$ выше можно было отбросить.

Softmax-регрессия — выходной слой нейросетевых классификаторов и языковых моделей. Языковая модель — это классификатор, у которого $K$ классов — токены словаря: заметка об n-граммных языковых моделях оценивает вероятности следующего токена подсчётом, а word2vec вычисляет их этим softmax по скалярным произведениям, где $K$ в сотни тысяч делает нормировку узким местом.

Многоклассовые метрики: микро- и макроусреднение#

Точность (precision), полнота (recall) и $F_1$ определены для одного класса против остальных. При $K$ классах таких таблиц $K$, и есть два способа их объединить (Manning, Raghavan and Schütze, 2008, §13.6):

• Макроусреднение (macro averaging) вычисляет метрику для каждого класса и усредняет $K$ чисел: каждый класс весит одинаково, как бы редок он ни был.
• Микроусреднение (micro averaging) суммирует $\mathrm{TP}_k$, $\mathrm{FP}_k$ и $\mathrm{FN}_k$ по классам и вычисляет метрику один раз по итоговым суммам: каждый пример весит одинаково.
• Взвешенное усреднение (weighted averaging) усредняет метрики по классам с весами, пропорциональными размерам классов.

В классификации с одной меткой микроусреднение ничего не добавляет: каждое неверное предсказание — это один ложноположительный ответ (для предсказанного класса) и один ложноотрицательный (для истинного), так что $\sum_k \mathrm{FP}_k = \sum_k \mathrm{FN}_k$ равно числу ошибок, а $\sum_k \mathrm{TP}_k$ — числу верных ответов. Микроточность, микрополнота и микро-$F_1$ все равны доле правильных ответов.

Разобранный пример. Игрушечный классификатор на 100 примерах с классами из 80, 15 и 5 примеров (строки — истинный класс, столбцы — предсказание):

истинный \ предсказанный	A	B	C
A (80)	76	3	1
B (15)	6	9	0
C (5)	3	0	2

Доля правильных ответов, а значит и микро-$F_1$, равна $87/100 = 0.87$. По классам $F_1 = 2\mathrm{TP}/(2\mathrm{TP} + \mathrm{FP} + \mathrm{FN})$ равна $152/165 = 0.921$ для A, $18/27 = 0.667$ для B и $4/8 = 0.5$ для C. Макро-$F_1$ равна $(0.921 + 0.667 + 0.5)/3 = 0.696$; взвешенная $F_1$, $0.8 \cdot 0.921 + 0.15 \cdot 0.667 + 0.05 \cdot 0.5 = 0.862$, близка к доле правильных ответов, потому что в обеих доминирует большой класс. Какое число сообщать — вопрос о задаче: если найти 5 примеров класса C так же важно, как 80 примеров класса A, макроусреднение говорит, что классификатор посредственный, а микроусреднение это скрывает. Заметка об оценке в NLP разбирает тот же эффект на текстовом примере с тремя темами. Метрики ранжирования тоже обобщаются: ROC-кривую и её AUC можно вычислить для каждого класса против остальных и усреднить по макросхеме.

Многометочная классификация#

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

$$P(\mathbf y \mid x) = \prod_{k=1}^K p_k^{\mathbf y_k} (1 - p_k)^{1 - \mathbf y_k}, \qquad p_k = \sigma(\langle w_k, x\rangle + b_k) .$$

Произведение означает, что метки условно независимы при данном $x$, а его отрицательный логарифм — сумма $K$ бинарных кросс-энтропий, по одной на метку. Отличие от многоклассовой модели — в нормировке: softmax заставляет классы конкурировать за одну единицу вероятности, а независимые сигмоиды позволяют любому числу меток быть вероятными одновременно — или ни одной. Каждой метке нужен свой порог решения, подобранный на валидационных данных под важную метрику, потому что метка, встречающаяся в 2% примеров, редко заслуживает порога 0.5 по умолчанию. Такой подход называется бинарной релевантностью (binary relevance). Он всё же отражает метки, которые встречаются вместе, потому что зависят от одних и тех же свойств $x$, но игнорирует зависимость, остающуюся при известном $x$ («экономика» делает «политику» более вероятной для той же статьи). Цепочки классификаторов (classifier chains) подают предсказания для первых меток как дополнительные признаки в классификаторы следующих (Read et al., 2011); сеть с общим скрытым слоем и $K$ сигмоидными выходами даёт меткам общее представление, что помогает, когда они зависят от одних и тех же признаков (Zhang and Zhou, 2014). Её выход — всё то же произведение, так что при данном $x$ метки остаются независимыми; для зависимости, остающейся при данном $x$, нужны цепочки или модель совместного распределения вектора меток.

Многометочные метрики сравнивают предсказанное множество с истинным. Пусть $Y_i$ — истинные множества, а $Z_i$ — предсказанные:

• потери Хэмминга (Hamming loss): доля неверных решений по меткам, $\frac{1}{nK}\sum_i \lvert Y_i \,\triangle\, Z_i\rvert$, где $\triangle$ — симметрическая разность;
• доля полностью верных множеств (subset accuracy, exact match): доля примеров, у которых всё множество угадано, — жёсткая метрика при большом $K$;
• метрики по примерам (example-based), усреднённые по примерам: индекс Жаккара $\lvert Y_i \cap Z_i\rvert / \lvert Y_i \cup Z_i\rvert$ или $F_1$ для каждого примера;
• микро- и макроусреднение по меткам, как в многоклассовом случае. Микро-$F_1$ здесь уже не равна никакой доле правильных ответов, поскольку один пример может дать несколько истинно положительных ответов.

Разобранный пример. Четыре примера и три метки, истинные множества $\{1, 3\}, \{2\}, \{1, 2\}, \{3\}$ и предсказанные $\{1\}, \{2\}, \{1, 2, 3\}, \{2, 3\}$. Неверны три из 12 решений по меткам, так что потери Хэмминга равны $0.25$; полностью верен только второй пример, так что доля полностью верных множеств тоже равна $0.25$. Индексы Жаккара равны $1/2, 1, 2/3, 1/2$, их среднее — $0.667$. В сумме по меткам $\mathrm{TP} = 5$, $\mathrm{FP} = 2$, $\mathrm{FN} = 1$, так что микро-$F_1 = 10/13 = 0.769$; по меткам $F_1$ равна $1$, $0.8$ и $0.5$, и макроусреднение даёт $0.767$. На синтетической задаче с 5 метками, примерно по две на пример, у независимых логистических регрессий потери Хэмминга равны $0.216$, но всё множество меток угадано лишь для $0.351$ тестовых примеров: эти две метрики измеряют очень разные вещи.

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

Иерархическая и экстремальная классификация#

Иерархическая классификация. Классы часто образуют таксономию: категории товаров, разделы библиотечного каталога, биологические виды. Плоский классификатор игнорирует дерево; подход сверху вниз обучает в каждом внутреннем узле классификатор, выбирающий среди его потомков. Каждая задача при этом остаётся маленькой, но ошибка наверху распространяется на всё, что ниже. Ошибки можно взвешивать по расстоянию в дереве, чтобы спутать две породы собак стоило меньше, чем спутать собаку с автомобилем (Silla and Freitas, 2011). То же дерево даёт быстрый softmax: если классы — листья бинарного дерева, вероятность листа — произведение бинарных решений на пути к нему, что стоит $\log_2 K$ сигмоид вместо суммы по $K$ классам. Этот иерархический softmax (hierarchical softmax) был предложен для языковых моделей (Morin and Bengio, 2005) и используется в word2vec.

Экстремальная классификация (extreme classification). Когда $K$ достигает $10^5$–$10^7$ (все категории Википедии, все товары магазина, все токены словаря), softmax стоит $O(Kd)$ на пример и для оценок, и для градиента, а у большинства меток лишь горстка примеров. Тогда при обучении нормировку приближают, сэмплируя несколько негативных классов на пример (sampled softmax, Jean et al., 2015; негативное сэмплирование в заметке о word2vec), или используют деревья меток, а при оценке переходят к метрикам ранжирования, таким как точность на $k$ (precision at k): доля верных меток среди $k$ меток с наибольшими оценками.

Что изменилось#

	Бинарная классификация	Многоклассовая и многометочная
Выход	одна оценка, её знак	$K$ оценок: argmax или множество меток
Вероятностная модель	Бернулли, $\sigma(z)$	категориальная, $\operatorname{softmax}(z)$; или $K$ независимых бернуллиевских величин
Функция потерь	логистическая	кросс-энтропия $-\log p_y$; или сумма $K$ бинарных кросс-энтропий
Градиент по оценкам	$p - y$	$p - \mathbf y$, вектор
Сведения	не нужны	«один против всех» ($K$ моделей), «каждый против каждого» ($K(K-1)/2$ моделей)
Идентифицируемость	веса единственны	оценки определены с точностью до общего сдвига; зафиксировать опорный класс или использовать L2
Метрики	точность, полнота, $F_1$	по классам, затем микро-, макро- или взвешенное усреднение; потери Хэмминга и точное совпадение для множеств меток

Ограничения#

• Сведения не видят задачу целиком. «Один против всех» обучает каждую линейную оценку отдельно, поэтому класс между другими получает неверно заданную бинарную модель и неоптимальные границы, хотя argmax всё же может образовать полосу; «каждый против каждого» спрашивает классификаторы о классах, которых они никогда не видели. Их оценки не являются откалиброванными вероятностями.
• Softmax заставляет выбирать. Вероятности в сумме дают 1 по известным классам, так что вход ни из одного из них всё равно распределяется между ними. Ответ может быть излишне уверенным или почти равномерным: вынужденный выбор известного класса и уверенность — разные вещи; обнаружение таких входов — тема заметки о поиске аномалий.
• Независимые сигмоиды игнорируют зависимость меток при данном $x$, даже с общим скрытым слоем, а доля точных совпадений быстро падает с ростом числа меток.
• Стоимость растёт с $K$. Оценки и градиенты стоят $O(Kd)$ на пример; при очень большом $K$ нормировку приходится приближать.
• По-прежнему линейно. Каждая оценка $z_k$ линейна по $x$, поэтому области решений — выпуклые многогранники; класс из двух отдельных кластеров не может быть одной областью.

Что нужно запомнить#

• «Один против всех» обучает $K$ классификаторов на всех данных; «каждый против каждого» обучает $K(K-1)/2$ на парах классов, что дешевле для алгоритмов со сверхлинейной стоимостью, таких как ядерные SVM. Их оценки не приведены к общему масштабу.
• Мультиномиальная логистическая регрессия: $p = \operatorname{softmax}(Wx + b)$, функция потерь $-\log p_y$ — отрицательный логарифм категориального правдоподобия. Это точное апостериорное распределение для гауссовских классов с общей ковариацией.
• Градиент по оценкам равен $p - \mathbf y$, по весам — $(p - \mathbf y)x^\top$. Гессиан $\operatorname{diag}(p) - pp^\top$ — ковариационная матрица, поэтому функция потерь выпукла.
• Прибавление константы ко всем оценкам ничего не меняет: нужно зафиксировать опорный класс или регуляризовать модель, а перед возведением в экспоненту вычитать максимальную оценку.
• В задаче с одной меткой микро-$F_1$ равна доле правильных ответов; макроусреднение придаёт классам равный вес и выявляет редкие классы. Многометочная задача: независимые сигмоиды, пороги для каждой метки, потери Хэмминга, точное совпадение, микро- и макро-$F_1$.

Код#

Softmax и его градиент, «один против всех» против мультиномиальной модели на трёх классах, три стратегии на цифрах, многоклассовые и многометочные метрики:

import numpy as np
from scipy.stats import norm
from sklearn.datasets import load_digits, make_multilabel_classification
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.linear_model import LogisticRegression
from sklearn.multiclass import OneVsRestClassifier, OneVsOneClassifier
from sklearn.metrics import f1_score, accuracy_score, hamming_loss, jaccard_score

# softmax, кросс-энтропия и её градиент для оценок z = (2, 1, 0.1), верный класс 1
def softmax(z):
    e = np.exp(z - z.max())            # вычитание максимума ничего не меняет и предотвращает переполнение
    return e / e.sum()
z = np.array([2.0, 1.0, 0.1]); y = np.array([1, 0, 0])
p = softmax(z)
print(p.round(3), round(-np.log(p[0]), 3), (p - y).round(3))   # [0.659 0.242 0.099] 0.417 [-0.341  0.242  0.099]
print(softmax(z + 100).round(3))                                # [0.659 0.242 0.099]: прибавление константы ничего не меняет
with np.errstate(over='ignore', invalid='ignore'):
    big = np.array([1000.0, 999.0])
    print(np.exp(big) / np.exp(big).sum(), softmax(big).round(3))   # [nan nan] [0.731 0.269]
eps = 1e-6; L = lambda z: -np.log(softmax(z)[0])
print(np.array([(L(z + eps * np.eye(3)[k]) - L(z - eps * np.eye(3)[k])) / (2 * eps) for k in range(3)]).round(3))   # [-0.341  0.242  0.099]

# три класса на прямой, N(-2, 1), N(0, 1), N(2, 1): «один против всех» и мультиномиальная модель, обученные на распределении (мелкая взвешенная сетка)
x = np.arange(-8, 8.0001, 0.01); X = np.tile(x, 3)[:, None]; c = np.repeat([0, 1, 2], len(x))
w = np.concatenate([norm.pdf(x, m) for m in (-2, 0, 2)])
fit = lambda target: LogisticRegression(C=1e8, tol=1e-12, max_iter=10000).fit(X, target, sample_weight=w)
ovr = [fit((c == k).astype(int)) for k in range(3)]
print([(round(float(m.coef_[0, 0]), 3), round(float(m.intercept_[0]), 3)) for m in ovr])   # [(-2.114, -2.169), (0.0, -0.693), (2.114, -2.169)]
t = (np.log(1 / 2) - ovr[0].intercept_[0]) / ovr[0].coef_[0, 0]            # где левая модель опускается до 1/3
print(round(-t, 3), round((2 * norm.cdf(2 + t) + 2 * norm.cdf(-t) - 1) / 3, 3), round(2 * norm.cdf(-t) - 1, 3))   # 0.698 0.774 0.515
mn = fit(c)
print(mn.coef_.ravel().round(3), mn.intercept_.round(3), round((4 * norm.cdf(1) - 1) / 3, 3), round(2 * norm.cdf(1) - 1, 3))
# [-2.  0.  2.] [-0.667  1.333 -0.667] 0.788 0.683: байесовское апостериорное распределение, сдвинутое так, что свободные члены в сумме дают ноль

# десять цифр: «один против всех», «каждый против каждого» и мультиномиальная логистическая регрессия
Xd, yd = load_digits(return_X_y=True)
Xtr, Xte, ytr, yte = train_test_split(Xd, yd, test_size=0.5, random_state=0, stratify=yd)
sc = StandardScaler().fit(Xtr); Xtr, Xte = sc.transform(Xtr), sc.transform(Xte)
base = LogisticRegression(C=0.1, max_iter=5000)
for name, m in (('ovr', OneVsRestClassifier(base)), ('ovo', OneVsOneClassifier(base)), ('multinomial', base)):
    m.fit(Xtr, ytr)
    n_models = len(m.estimators_) if hasattr(m, 'estimators_') else 1
    print(name, n_models, round(m.score(Xte, yte), 3))
# ovr 10 0.953 | ovo 45 0.966 | multinomial 1 0.963
print(np.abs(base.coef_.sum(axis=0)).max() < 1e-6)   # True: с L2-штрафом веса классов в сумме дают ноль

# микро- и макроусреднение: 100 примеров, классы из 80, 15 и 5
cm = np.array([[76, 3, 1], [6, 9, 0], [3, 0, 2]])     # строки — истинный класс, столбцы — предсказание
yt = np.repeat(np.repeat([0, 1, 2], 3), cm.ravel()); yp = np.tile([0, 1, 2], 3).repeat(cm.ravel())
print(accuracy_score(yt, yp), f1_score(yt, yp, average=None).round(3), [round(f1_score(yt, yp, average=a), 3) for a in ('micro', 'macro', 'weighted')])
# 0.87 [0.921 0.667 0.5  ] [0.87, 0.696, 0.862]

# многометочная задача: четыре примера, три метки
Yt = np.array([[1, 0, 1], [0, 1, 0], [1, 1, 0], [0, 0, 1]]); Yp = np.array([[1, 0, 0], [0, 1, 0], [1, 1, 1], [0, 1, 1]])
print(hamming_loss(Yt, Yp), accuracy_score(Yt, Yp), round(jaccard_score(Yt, Yp, average='samples'), 3),
      [round(f1_score(Yt, Yp, average=a), 3) for a in ('micro', 'macro')], f1_score(Yt, Yp, average=None).round(3))
# 0.25 0.25 0.667 [0.769, 0.767] [1.  0.8 0.5]

# независимые сигмоиды на синтетической многометочной задаче (5 меток)
Xm, Ym = make_multilabel_classification(n_samples=2000, n_features=20, n_classes=5, n_labels=2, random_state=0)
Xtr, Xte, Ytr, Yte = train_test_split(Xm, Ym, test_size=0.5, random_state=0)
P = OneVsRestClassifier(LogisticRegression(max_iter=5000)).fit(Xtr, Ytr).predict_proba(Xte)
Yhat = (P >= 0.5).astype(int)
print(Ytr.mean(axis=0).round(2), round(hamming_loss(Yte, Yhat), 3), round(accuracy_score(Yte, Yhat), 3),
      [round(f1_score(Yte, Yhat, average=a), 3) for a in ('micro', 'macro')], round(f1_score(Yte, Yhat, average='samples', zero_division=0), 3))
# [0.38 0.43 0.39 0.36 0.33] 0.216 0.351 [0.695, 0.695] 0.619: доли меток, потери Хэмминга, точное совпадение, микро-, макро- и F1 по примерам

Дальше#

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

Литература#

• C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006. §4.1.2 (несколько классов и неоднозначные области схем «один против всех» и «каждый против каждого»), §4.2 (генеративные модели с гауссовскими условными распределениями классов дают softmax от линейных функций), §4.3.4 (многоклассовая логистическая регрессия), §7.1.3 (многоклассовые SVM).
• R. Rifkin, A. Klautau. In Defense of One-Vs-All Classification. JMLR, 5, pp. 101–141, 2004.
• C.-W. Hsu, C.-J. Lin. A Comparison of Methods for Multiclass Support Vector Machines. IEEE Transactions on Neural Networks, 13(2), pp. 415–425, 2002.
• T. G. Dietterich, G. Bakiri. Solving Multiclass Learning Problems via Error-Correcting Output Codes. Journal of Artificial Intelligence Research, 2, pp. 263–286, 1995.
• K. Crammer, Y. Singer. On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines. JMLR, 2, pp. 265–292, 2001.
• C. D. Manning, P. Raghavan, H. Schütze. Introduction to Information Retrieval. Cambridge University Press, 2008. §13.6 (оценка классификации текстов: макро- и микроусреднение).
• J. Read, B. Pfahringer, G. Holmes, E. Frank. Classifier Chains for Multi-label Classification. Machine Learning, 85(3), pp. 333–359, 2011.
• M.-L. Zhang, Z.-H. Zhou. A Review on Multi-Label Learning Algorithms. IEEE Transactions on Knowledge and Data Engineering, 26(8), pp. 1819–1837, 2014.
• C. N. Silla Jr., A. A. Freitas. A Survey of Hierarchical Classification across Different Application Domains. Data Mining and Knowledge Discovery, 22(1–2), pp. 31–72, 2011.
• F. Morin, Y. Bengio. Hierarchical Probabilistic Neural Network Language Model. AISTATS, 2005. Иерархический softmax.
• S. Jean, K. Cho, R. Memisevic, Y. Bengio. On Using Very Large Target Vocabulary for Neural Machine Translation. ACL, 2015. Sampled softmax по большому словарю.
• T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning, 2nd ed. Springer, 2009. §4.2 (маскирование среднего класса линейной регрессией на индикаторы), §4.4 (многоклассовая логистическая регрессия).
• E. Sokolov et al. Машинное обучение (HSE), конспекты лекций: лекция 6 (многоклассовая классификация, «один против всех» и «все против всех», мультиномиальная логистическая регрессия, микро- и макроусреднение, многометочная классификация и её метрики).