CS231n: линейная классификация — SVM и Softmax (перевод конспекта)

О переводе

Перевод страницы Linear Classification из конспектов Stanford CS231n. Тексты конспектов открыты по лицензии MIT (репозиторий cs231n/cs231n.github.io, © 2015 Andrej Karpathy). Рисунки мы не копируем: вместо каждого — перевод подписи и описание; сами картинки смотрите по ссылке на оригинал. Примечания переводчика выделены отдельно. Путеводитель по курсу — здесь.

Линейная классификация

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

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

Обзор. Теперь мы построим более мощный подход к классификации изображений, который потом естественно расширится до целых нейронных сетей и свёрточных нейронных сетей. У подхода два главных компонента: функция оценок (score function), отображающая сырые данные в оценки классов, и функция потерь (loss function), измеряющая согласие предсказанных оценок с истинными метками. Затем мы сформулируем задачу оптимизации: минимизировать функцию потерь по параметрам функции оценок.

Параметрическое отображение изображений в оценки классов

Первый компонент подхода — функция оценок, переводящая значения пикселей изображения в оценки уверенности для каждого класса. Разберём на конкретном примере. Как и раньше, пусть есть обучающая выборка изображений $x_i \in R^D$, каждому сопоставлена метка $y_i$. Здесь $i = 1 \dots N$ и $y_i \in \lbrace 1 \dots K \rbrace$. То есть у нас N примеров (каждый размерности D) и K различных категорий. Например, в CIFAR-10 обучающая выборка содержит N = 50 000 изображений, у каждого D = 32 × 32 × 3 = 3072 пикселя, и K = 10, поскольку классов десять (собака, кошка, автомобиль и т. д.). Определим функцию оценок $f: R^D \mapsto R^K$, переводящую сырые пиксели в оценки классов.

Линейный классификатор. В этом модуле начнём, пожалуй, с самой простой функции — линейного отображения:

$$f(x_i, W, b) = W x_i + b$$

Здесь мы считаем, что все пиксели изображения $x_i$ вытянуты в один вектор-столбец размера [D × 1]. Матрица W (размера [K × D]) и вектор b (размера [K × 1]) — параметры функции. В CIFAR-10 $x_i$ содержит все пиксели $i$-го изображения, вытянутые в столбец [3072 × 1], W имеет размер [10 × 3072], а b — [10 × 1]: на вход функции поступают 3072 числа (сырые значения пикселей), на выходе — 10 чисел (оценки классов). Параметры в W часто называют весами, а b — вектором сдвига (bias), потому что он влияет на выходные оценки, но не взаимодействует с данными $x_i$. Впрочем, слова веса и параметры часто употребляют как синонимы.

Несколько замечаний:

• Одно матричное умножение $W x_i$ фактически вычисляет 10 отдельных классификаторов параллельно (по одному на класс): каждый классификатор — это строка W.
• Входные данные $(x_i, y_i)$ мы считаем заданными и неизменными, а параметры W, b можем настраивать. Наша цель — подобрать их так, чтобы вычисленные оценки соответствовали истинным меткам на всей обучающей выборке. Как именно — подробно разберём дальше, но интуитивно мы хотим, чтобы оценка правильного класса была выше оценок неправильных.
• Преимущество подхода: обучающие данные используются, чтобы выучить параметры W, b, но после обучения выборку можно выбросить и хранить только выученные параметры. Новое тестовое изображение просто прогоняется через функцию и классифицируется по вычисленным оценкам.
• Наконец, классификация тестового изображения — это одно умножение матрицы и одно сложение, что гораздо быстрее, чем сравнивать его со всеми обучающими изображениями.

Забегая вперёд: свёрточные нейронные сети будут отображать пиксели в оценки ровно так же, но отображение $f$ будет сложнее и будет содержать больше параметров.

Интерпретация линейного классификатора

Линейный классификатор вычисляет оценку класса как взвешенную сумму всех значений пикселей во всех трёх цветовых каналах. В зависимости от значений весов функция может «любить» или «не любить» (в зависимости от знака веса) определённые цвета в определённых местах изображения. Например, можно представить, что класс «корабль» вероятнее, если по краям изображения много синего (это может быть вода). Тогда классификатор «корабля», скорее всего, будет иметь много положительных весов в синем канале (синий цвет увеличивает оценку корабля) и отрицательные веса в красном и зелёном (красный и зелёный её уменьшают).

Рисунок (в оригинале). Пример отображения изображения в оценки классов. Для наглядности считаем, что в изображении всего 4 пикселя (4 монохромных пикселя, цветовые каналы для краткости не рассматриваем) и есть 3 класса (красный — кошка, зелёный — собака, синий — корабль). (Уточнение: цвета здесь просто обозначают 3 класса и не связаны с каналами RGB.) Пиксели вытягиваются в столбец, и матричное умножение даёт оценки каждого класса. Этот конкретный набор весов W совсем плох: изображению кошки он даёт очень низкую оценку кошки. Похоже, эти веса уверены, что видят собаку.

Изображения как точки в многомерном пространстве. Поскольку изображения вытянуты в многомерные векторы-столбцы, каждое изображение можно считать точкой в этом пространстве (например, каждое изображение CIFAR-10 — точка в 3072-мерном пространстве пикселей 32 × 32 × 3). Тогда весь набор данных — (размеченное) множество точек.

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

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

Как мы видели, каждая строка $W$ — классификатор одного из классов. Геометрически: если менять строку $W$, соответствующая прямая в пространстве пикселей поворачивается. Сдвиги $b$ позволяют прямым смещаться. В частности, без сдвигов при $x_i = 0$ оценка всегда была бы нулевой независимо от весов, и все прямые были бы вынуждены проходить через начало координат.

Линейный классификатор как сравнение с шаблонами. Другая интерпретация весов $W$: каждая строка $W$ соответствует шаблону (иногда говорят прототипу) одного из классов. Оценка класса для изображения получается сравнением изображения с каждым шаблоном через скалярное произведение, чтобы найти шаблон, который «подходит» лучше всего. В этих терминах линейный классификатор сопоставляет изображение с шаблонами, причём шаблоны выучиваются. Можно сказать и так: мы по-прежнему делаем что-то вроде поиска ближайшего соседа, но вместо тысяч обучающих изображений используем одно изображение на класс (его мы выучиваем, и оно не обязано совпадать ни с одним изображением выборки), а в качестве расстояния берём (отрицательное) скалярное произведение вместо расстояния L1 или L2.

Рисунок. Немного забегая вперёд: пример весов, выученных к концу обучения на CIFAR-10. Шаблон корабля, как и ожидалось, содержит много синих пикселей. Поэтому скалярное произведение этого шаблона с изображениями кораблей в океане будет большим.

Заметьте также, что шаблон лошади похож на двухголовую лошадь: в наборе данных есть лошади, смотрящие и влево, и вправо. Линейный классификатор сливает эти две моды данных в один шаблон. Похожим образом классификатор автомобилей, по-видимому, слил несколько мод в один шаблон, который должен распознавать машины со всех сторон и всех цветов. В частности, шаблон получился красным — намёк на то, что в CIFAR-10 красных машин больше, чем машин любого другого цвета. Линейный классификатор слишком слаб, чтобы как следует учесть машины разных цветов, но, как мы увидим, нейронные сети это умеют. Забегая вперёд: нейронная сеть может вырастить в скрытых слоях промежуточные нейроны, распознающие конкретные типы машин (например, «зелёная машина, смотрит влево», «синяя машина, вид спереди»), а нейроны следующего слоя могут объединить их во взвешенную сумму и получить более точную оценку «машины».

Трюк со сдвигом. Прежде чем двигаться дальше, упомянем распространённый трюк, позволяющий представить два параметра $W, b$ как один. Напомним функцию оценок:

$$f(x_i, W, b) = W x_i + b$$

Дальше по ходу материала отслеживать два набора параметров (сдвиги $b$ и веса $W$) по отдельности несколько неудобно. Распространённый трюк — объединить их в одну матрицу, дополнив вектор $x_i$ ещё одним измерением, в котором всегда стоит константа $1$ — «измерение сдвига». С этим измерением функция оценок упрощается до одного матричного умножения:

$$f(x_i, W) = W x_i$$

В примере с CIFAR-10 $x_i$ теперь имеет размер [3073 × 1] вместо [3072 × 1] (лишнее измерение хранит константу 1), а $W$ — [10 × 3073] вместо [10 × 3072]. Дополнительный столбец $W$ теперь соответствует сдвигу $b$.

Рисунок. Иллюстрация трюка со сдвигом. Умножить на матрицу и прибавить вектор сдвига (слева) — то же самое, что добавить ко всем входным векторам измерение с константой 1 и расширить матрицу весов на один столбец — столбец сдвига (справа). Так что если в предобработке дописать единицу ко всем векторам, учить придётся одну матрицу весов вместо двух (весов и сдвигов).

Предобработка изображений. Небольшое замечание: в примерах выше мы использовали сырые значения пикселей (от 0 до 255). В машинном обучении принято всегда нормализовать входные признаки (для изображений признаком считается каждый пиксель). Особенно важно центрировать данные, вычитая из каждого признака его среднее. Для изображений это значит: посчитать среднее изображение по обучающей выборке и вычесть его из каждого изображения, получив пиксели примерно в диапазоне от −127 до 127. Ещё одна распространённая предобработка — масштабировать каждый признак так, чтобы его значения лежали в $[-1, 1]$. Из этих двух шагов центрирование, пожалуй, важнее, но обосновать его мы сможем, только когда разберёмся в динамике градиентного спуска.

Функция потерь

В предыдущем разделе мы определили функцию из значений пикселей в оценки классов, зависящую от весов $W$. Мы также видели, что данные $(x_i, y_i)$ нам не подвластны (они заданы и фиксированы), а веса — подвластны, и мы хотим настроить их так, чтобы предсказанные оценки согласовались с истинными метками обучающих данных.

Например, вернёмся к изображению кошки и его оценкам для классов «кошка», «собака» и «корабль». Набор весов в том примере был совсем плох: на вход подали пиксели с кошкой, а оценка кошки вышла очень низкой (−96,8) по сравнению с другими классами (собака — 437,9, корабль — 61,95). Наше «недовольство» такими результатами мы будем измерять функцией потерь (иногда её называют функцией стоимости или целевой функцией). Интуитивно потери высокие, если мы плохо классифицируем обучающие данные, и низкие, если хорошо.

Многоклассовая функция потерь SVM

Детали функции потерь можно определить по-разному. Первым примером разберём распространённую функцию — многоклассовые потери машины опорных векторов (Multiclass Support Vector Machine, SVM). Потери SVM устроены так, что SVM «хочет», чтобы у правильного класса каждого изображения оценка была выше оценок неправильных классов хотя бы на фиксированный зазор $\Delta$. Иногда полезно очеловечивать функции потерь, как мы только что сделали: SVM «хочет» определённого исхода в том смысле, что этот исход даёт меньшие потери (что хорошо).

Теперь точнее. Для $i$-го примера даны пиксели изображения $x_i$ и метка $y_i$ — индекс правильного класса. Функция оценок берёт пиксели и вычисляет вектор оценок классов $f(x_i, W)$, который мы сократим до $s$ (от scores). Например, оценка $j$-го класса — $j$-й элемент: $s_j = f(x_i, W)_j$. Многоклассовые потери SVM для $i$-го примера:

$$L_i = \sum_{j \neq y_i} \max(0, s_j - s_{y_i} + \Delta)$$

Пример. Разберём на примере. Пусть три класса получили оценки $s = [13, -7, 11]$, и первый класс — правильный (то есть $y_i = 0$). Пусть также $\Delta$ (гиперпараметр, о котором подробнее скоро) равна 10. Выражение суммирует по всем неправильным классам ($j \neq y_i$), так что получаем два слагаемых:

$$L_i = \max(0, -7 - 13 + 10) + \max(0, 11 - 13 + 10)$$

Первое слагаемое равно нулю: $-7 - 13 + 10$ отрицательно и обрезается до нуля функцией $\max(0, -)$. Для этой пары потери нулевые, потому что оценка правильного класса (13) больше оценки неправильного (−7) как минимум на зазор 10. На самом деле разница 20 — гораздо больше 10, но SVM важно лишь, чтобы она была не меньше 10; всё, что сверх зазора, обрезается до нуля операцией max. Второе слагаемое: $11 - 13 + 10 = 8$. То есть хотя оценка правильного класса выше оценки неправильного ($13 > 11$), она выше не на нужный зазор 10, а лишь на 2 — поэтому потери равны 8 (настолько разница должна быть больше, чтобы зазор выполнялся). Итак, функция потерь SVM хочет, чтобы оценка правильного класса $y_i$ была больше оценок неправильных классов хотя бы на $\Delta$ (дельту). Если это не так, мы накапливаем потери.

Поскольку в этом модуле мы работаем с линейными функциями оценок ($f(x_i; W) = W x_i$), функцию потерь можно переписать в эквивалентном виде:

$$L_i = \sum_{j \neq y_i} \max(0, w_j^T x_i - w_{y_i}^T x_i + \Delta)$$

где $w_j$ — $j$-я строка $W$, записанная как столбец. Впрочем, для более сложных функций оценок $f$ так уже не будет.

Последний термин этого раздела: функцию с порогом в нуле $\max(0, -)$ часто называют hinge loss («потери-шарнир»). Иногда вместо неё используют SVM с квадратичным шарниром (L2-SVM) вида $\max(0, -)^2$, который штрафует нарушенные зазоры сильнее (квадратично, а не линейно). Неквадратичный вариант стандартнее, но на некоторых наборах данных квадратичный работает лучше. Это можно выяснить кросс-валидацией.

Функция потерь измеряет наше недовольство предсказаниями на обучающей выборке.

Рисунок. Многоклассовый SVM «хочет», чтобы оценка правильного класса была выше всех остальных оценок хотя бы на зазор дельта. Если оценка какого-то класса попадает в красную область (или выше), потери накапливаются. Иначе потери нулевые. Наша цель — найти веса, которые одновременно удовлетворяют этому ограничению для всех обучающих примеров и дают как можно меньшие суммарные потери.

Регуляризация. У описанной функции потерь есть один изъян. Пусть есть набор данных и параметры W, которые правильно классифицируют каждый пример (все оценки таковы, что все зазоры выполнены, и $L_i = 0$ для всех $i$). Проблема в том, что такой W не единственен: может быть много похожих W, правильно классифицирующих примеры. Простой способ это увидеть: если параметры W правильно классифицируют все примеры (потери каждого примера нулевые), то и любое кратное $\lambda W$ при $\lambda > 1$ тоже даёт нулевые потери, потому что такое преобразование равномерно растягивает все оценки, а значит, и их разности. Например, если разность оценок правильного класса и ближайшего неправильного была 15, то после умножения всех элементов W на 2 она станет 30.

Иначе говоря, мы хотим закодировать предпочтение одних весов W перед другими, чтобы убрать эту неоднозначность. Для этого расширим функцию потерь штрафом регуляризации $R(W)$. Самый распространённый штраф — квадрат нормы L2, который препятствует большим весам с помощью поэлементного квадратичного штрафа по всем параметрам:

$$R(W) = \sum_k \sum_l W_{k,l}^2$$

Здесь мы суммируем квадраты всех элементов $W$. Заметьте, что функция регуляризации не зависит от данных, только от весов. С ней получаются полные многоклассовые потери SVM из двух компонентов: потерь на данных (средние $L_i$ по всем примерам) и потерь регуляризации:

$$L = \underbrace{\frac{1}{N} \sum_i L_i}_{\text{потери на данных}} + \underbrace{\lambda R(W)}_{\text{потери регуляризации}}$$

Или в развёрнутом виде:

$$L = \frac{1}{N} \sum_i \sum_{j \neq y_i} \left[ \max(0, f(x_i; W)_j - f(x_i; W)_{y_i} + \Delta) \right] + \lambda \sum_k \sum_l W_{k,l}^2$$

где $N$ — число обучающих примеров. Как видно, штраф регуляризации добавляется к целевой функции с весом — гиперпараметром $\lambda$. Простого способа выбрать этот гиперпараметр нет; обычно его подбирают кросс-валидацией.

Помимо приведённой мотивации, у штрафа регуляризации много желательных свойств; ко многим мы вернёмся в следующих разделах. Например, оказывается, что штраф L2 приводит к привлекательному свойству максимального зазора у SVM (подробности, если интересно, — в конспекте CS229).

Самое привлекательное свойство в том, что штраф за большие веса обычно улучшает обобщение: ни одно входное измерение не может в одиночку сильно влиять на оценки. Пусть, например, есть входной вектор $x = [1,1,1,1]$ и два вектора весов $w_1 = [1,0,0,0]$ и $w_2 = [0{,}25; 0{,}25; 0{,}25; 0{,}25]$. Тогда $w_1^T x = w_2^T x = 1$: оба вектора дают одно и то же скалярное произведение, но штраф L2 у $w_1$ равен 1,0, а у $w_2$ — всего 0,25. Поэтому по штрафу L2 предпочтительнее $w_2$: его потери регуляризации меньше. Интуитивно — потому что веса $w_2$ меньше и «размазаны». Поскольку штраф L2 предпочитает меньшие и более размазанные векторы весов, итоговый классификатор поощряется учитывать все входные измерения понемногу, а не несколько — очень сильно. Как мы увидим дальше в курсе, это может улучшить качество классификатора на тестовых изображениях и уменьшить переобучение.

Заметьте, что у сдвигов такого эффекта нет: в отличие от весов, они не управляют силой влияния входного измерения. Поэтому обычно регуляризуют только веса $W$, но не сдвиги $b$. Впрочем, на практике разница обычно пренебрежимо мала. Наконец, из-за штрафа регуляризации мы никогда не получим потери ровно 0,0 на всех примерах: это возможно лишь в патологическом случае $W = 0$.

Код. Вот функция потерь (без регуляризации) на Python — в невекторизованном и наполовину векторизованном виде:

def L_i(x, y, W):
  """
  невекторизованная версия: многоклассовые потери SVM для одного примера (x, y)
  - x — вектор-столбец, представляющий изображение (например, 3073 x 1 в CIFAR-10)
    с дописанным измерением сдвига в позиции 3073 (трюк со сдвигом)
  - y — целое число, индекс правильного класса (например, от 0 до 9 в CIFAR-10)
  - W — матрица весов (например, 10 x 3073 в CIFAR-10)
  """
  delta = 1.0 # о выборе delta — дальше в этом разделе
  scores = W.dot(x) # scores имеет размер 10 x 1: оценки всех классов
  correct_class_score = scores[y]
  D = W.shape[0] # число классов, например 10
  loss_i = 0.0
  for j in range(D): # перебираем все неправильные классы
    if j == y:
      # пропускаем правильный класс, идём только по неправильным
      continue
    # накапливаем потери i-го примера
    loss_i += max(0, scores[j] - correct_class_score + delta)
  return loss_i

def L_i_vectorized(x, y, W):
  """
  Более быстрая, наполовину векторизованная реализация. «Наполовину» —
  потому что для одного примера циклов нет, но остаётся цикл по примерам
  (снаружи этой функции)
  """
  delta = 1.0
  scores = W.dot(x)
  # считаем зазоры для всех классов одной векторной операцией
  margins = np.maximum(0, scores - scores[y] + delta)
  # в позиции y scores[y] - scores[y] сократились и дали delta. Нам нужно
  # игнорировать позицию y и учитывать зазоры только неправильных классов
  margins[y] = 0
  loss_i = np.sum(margins)
  return loss_i

def L(X, y, W):
  """
  полностью векторизованная реализация:
  - X хранит все обучающие примеры в столбцах (например, 3073 x 50 000 в CIFAR-10)
  - y — массив целых чисел с правильными классами (например, массив длины 50 000)
  - W — веса (например, 10 x 3073)
  """
  # вычислите потери по всем примерам в X без циклов for
  # оставлено читателю как упражнение в задании

Вывод этого раздела: потери SVM — один из способов измерить, насколько предсказания на обучающих данных согласуются с истинными метками. Кроме того, хорошо предсказывать на обучающей выборке — то же самое, что минимизировать потери.

Осталось придумать способ найти веса, минимизирующие потери.

Практические соображения

Выбор дельты. Мы не обсудили гиперпараметр $\Delta$ и его выбор. Каким его взять и нужно ли подбирать его кросс-валидацией? Оказывается, во всех случаях можно спокойно взять $\Delta = 1{,}0$. Гиперпараметры $\Delta$ и $\lambda$ выглядят как два разных гиперпараметра, но на деле оба управляют одним и тем же компромиссом — между потерями на данных и потерями регуляризации в целевой функции. Ключ к пониманию в том, что масштаб весов $W$ напрямую влияет на оценки (а значит, и на их разности): если уменьшать все значения $W$, разности оценок уменьшаются, если увеличивать — растут. Поэтому конкретное значение зазора между оценками (например, $\Delta = 1$ или $\Delta = 100$) в некотором смысле бессмысленно: веса могут произвольно сжимать или растягивать разности. Единственный настоящий компромисс — насколько сильно мы позволяем весам расти (через силу регуляризации $\lambda$).

Связь с бинарным SVM. Возможно, вы пришли в курс, уже зная бинарный SVM, где потери $i$-го примера записываются так:

$$L_i = C \max(0, 1 - y_i w^T x_i) + R(W)$$

где $C$ — гиперпараметр, а $y_i \in \lbrace -1, 1 \rbrace$. Можно убедиться, что формулировка этого раздела содержит бинарный SVM как частный случай при двух классах: если классов всего два, потери сводятся к бинарному SVM выше. Кроме того, $C$ в этой формулировке и $\lambda$ в нашей управляют одним и тем же компромиссом и связаны обратной зависимостью $C \propto \frac{1}{\lambda}$.

Отступление: оптимизация в прямой форме. Если вы знакомы с SVM, вы могли слышать о ядрах, двойственной задаче, алгоритме SMO и т. д. В этом курсе (как и вообще с нейронными сетями) мы всегда работаем с целевыми функциями в их прямой форме без ограничений. Многие из этих функций формально не дифференцируемы (например, у $\max(x, y)$ есть излом при $x = y$), но на практике это не проблема: обычно используют субградиент.

Отступление: другие формулировки многоклассового SVM. Многоклассовый SVM из этого раздела — лишь один из способов обобщить SVM на много классов. Другой распространённый вариант — один против всех (One-Vs-All, OVA): для каждого класса обучается независимый бинарный SVM «этот класс против всех остальных». Родственная, но реже встречающаяся стратегия — все против всех (All-vs-All, AVA). Наша формулировка следует версии Weston and Watkins 1999 (pdf), которая мощнее OVA (в том смысле, что можно построить многоклассовые наборы данных, на которых эта версия достигает нулевых потерь на данных, а OVA — нет; подробности в статье). Последняя формулировка, которую вы можете встретить, — структурный SVM: он максимизирует зазор между оценкой правильного класса и оценкой самого высоко оценённого неправильного класса. Разбираться в различиях этих формулировок — за рамками курса. Версия из этих конспектов — надёжный выбор на практике, но и простейшая стратегия OVA, скорее всего, сработает не хуже (как утверждают и Рифкин и др. в 2004 году в статье In Defense of One-Vs-All Classification (pdf)).

Классификатор Softmax

Оказывается, SVM — один из двух наиболее распространённых классификаторов. Другой популярный выбор — классификатор Softmax с другой функцией потерь. Если вы слышали о бинарной логистической регрессии, то классификатор Softmax — её обобщение на много классов. В отличие от SVM, который считает выходы $f(x_i, W)$ (некалиброванными и, возможно, трудно интерпретируемыми) оценками классов, Softmax выдаёт немного более интуитивный результат (нормированные вероятности классов) и имеет вероятностную интерпретацию, которую мы скоро опишем. В классификаторе Softmax функция $f(x_i; W) = W x_i$ не меняется, но теперь мы считаем оценки ненормированными логарифмами вероятностей классов и заменяем hinge loss на потери кросс-энтропии вида:

$$L_i = -\log\left(\frac{e^{f_{y_i}}}{\sum_j e^{f_j}}\right) \qquad \text{или, что то же самое,} \qquad L_i = -f_{y_i} + \log\sum_j e^{f_j}$$

где $f_j$ — $j$-й элемент вектора оценок классов $f$. Как и раньше, полные потери на наборе данных — среднее $L_i$ по всем обучающим примерам плюс слагаемое регуляризации $R(W)$. Функция $f_j(z) = \frac{e^{z_j}}{\sum_k e^{z_k}}$ называется функцией softmax: она берёт вектор произвольных вещественных оценок $z$ и «сжимает» его в вектор значений от нуля до единицы с суммой один. Полные потери кросс-энтропии с функцией softmax могут поначалу пугать, но мотивировать их довольно легко.

Взгляд теории информации. Кросс-энтропия между «истинным» распределением $p$ и оценкой $q$ определяется так:

$$H(p, q) = -\sum_x p(x) \log q(x)$$

Значит, классификатор Softmax минимизирует кросс-энтропию между оценёнными вероятностями классов ($q = e^{f_{y_i}} / \sum_j e^{f_j}$, как выше) и «истинным» распределением, которое в этой интерпретации сосредоточено целиком на правильном классе (то есть $p = [0, \ldots, 1, \ldots, 0]$ содержит единственную единицу в позиции $y_i$). Более того, поскольку кросс-энтропию можно записать через энтропию и расхождение Кульбака — Лейблера как $H(p, q) = H(p) + D_{KL}(p \Vert q)$, а энтропия дельта-функции $p$ равна нулю, это равносильно минимизации KL-расхождения между двумя распределениями (меры расстояния). Иначе говоря, цель кросс-энтропии «хочет», чтобы предсказанное распределение сосредоточило всю массу на правильном ответе.

Вероятностная интерпретация. Посмотрим на выражение

$$P(y_i \mid x_i; W) = \frac{e^{f_{y_i}}}{\sum_j e^{f_j}}$$

Его можно понимать как (нормированную) вероятность правильной метки $y_i$ при данном изображении $x_i$ и параметрах $W$. Действительно, классификатор Softmax считает оценки в выходном векторе $f$ ненормированными логарифмами вероятностей. Возведение в экспоненту даёт (ненормированные) вероятности, а деление нормирует их, чтобы сумма была равна единице. В вероятностной интерпретации мы, следовательно, минимизируем отрицательный логарифм правдоподобия правильного класса, то есть выполняем оценку максимального правдоподобия (Maximum Likelihood Estimation, MLE). Приятная черта этого взгляда: слагаемое регуляризации $R(W)$ в полной функции потерь можно понимать как гауссово априорное распределение на матрице весов $W$, и тогда вместо MLE мы выполняем оценку апостериорного максимума (Maximum a posteriori, MAP). Мы упоминаем эти интерпретации для интуиции, но полный вывод выходит за рамки курса.

Практика: численная устойчивость. При вычислении функции Softmax в коде промежуточные величины $e^{f_{y_i}}$ и $\sum_j e^{f_j}$ могут быть очень большими из-за экспонент. Деление больших чисел численно неустойчиво, поэтому важен трюк с нормировкой. Если умножить числитель и знаменатель дроби на константу $C$ и внести её в сумму, получим (математически эквивалентное) выражение:

$$\frac{e^{f_{y_i}}}{\sum_j e^{f_j}} = \frac{C e^{f_{y_i}}}{C \sum_j e^{f_j}} = \frac{e^{f_{y_i} + \log C}}{\sum_j e^{f_j + \log C}}$$

Значение $C$ можно выбрать любым. Результат от этого не изменится, но можно улучшить численную устойчивость вычислений. Обычно берут $\log C = -\max_j f_j$: то есть сдвигают значения в векторе $f$ так, чтобы наибольшее стало нулём. В коде:

f = np.array([123, 456, 789]) # пример: 3 класса, у каждого большая оценка
p = np.exp(f) / np.sum(np.exp(f)) # Плохо: численная проблема, возможно переполнение

# вместо этого сначала сдвигаем f так, чтобы наибольшее значение стало 0:
f -= np.max(f) # f становится [-666, -333, 0]
p = np.exp(f) / np.sum(np.exp(f)) # безопасно, даёт правильный ответ

Примечание переводчика

В этом фрагменте np.array([123, 456, 789]) создаёт массив целых чисел, и f -= np.max(f) работает. Но если бы массив был целочисленным, а вычитали дробное число, NumPy выдал бы ошибку приведения типов. В реальном коде оценки — числа с плавающей точкой, и проблемы нет; на практике удобнее scipy.special.softmax или torch.softmax, которые делают этот сдвиг сами.

Возможная путаница в названиях. Точнее говоря, классификатор SVM использует hinge loss, которую иногда называют потерями максимального зазора (max-margin loss). Классификатор Softmax использует потери кросс-энтропии. Своё название он получил от функции softmax, которая сжимает сырые оценки классов в нормированные положительные значения с суммой один, чтобы к ним можно было применить кросс-энтропию. В частности, формально говорить «softmax-потери» бессмысленно: softmax — всего лишь сжимающая функция. Но это довольно распространённое сокращение.

SVM и Softmax: сравнение

Рисунок. Пример различия классификаторов SVM и Softmax для одной точки данных. В обоих случаях вычисляется один и тот же вектор оценок f (в этом разделе — матричным умножением). Разница в интерпретации оценок в f: SVM считает их оценками классов, и его функция потерь поощряет, чтобы оценка правильного класса (класс 2, синий) была выше остальных на зазор. Классификатор Softmax считает оценки (ненормированными) логарифмами вероятностей классов и поощряет, чтобы (нормированный) логарифм вероятности правильного класса был высоким (или, что то же, его минус — низким). Итоговые потери для этого примера — 1,58 у SVM и 1,04 у Softmax (натуральный логарифм, а не по основанию 2 или 10). Но эти числа несравнимы: они имеют смысл только относительно потерь того же классификатора на тех же данных.

Классификатор Softmax даёт «вероятности» каждого класса. В отличие от SVM, вычисляющего некалиброванные и трудно интерпретируемые оценки всех классов, Softmax позволяет вычислить «вероятности» всех меток. Например, для изображения SVM может выдать оценки $[12{,}5;\ 0{,}6;\ -23{,}0]$ для классов «кошка», «собака» и «корабль». Классификатор Softmax вместо этого может вычислить вероятности трёх меток $[0{,}9;\ 0{,}09;\ 0{,}01]$, по которым видно его уверенность в каждом классе. Слово «вероятности» мы взяли в кавычки потому, что то, насколько эти вероятности «острые» или «размазанные», напрямую зависит от силы регуляризации $\lambda$ — а её задаёте вы. Пусть, например, ненормированные логарифмы вероятностей трёх классов равны $[1, -2, 0]$. Функция softmax вычислит:

$$[1, -2, 0] \rightarrow [e^1, e^{-2}, e^0] = [2{,}71;\ 0{,}14;\ 1] \rightarrow [0{,}7;\ 0{,}04;\ 0{,}26]$$

Шаги — возвести в экспоненту и нормировать, чтобы сумма была единицей. Если бы сила регуляризации $\lambda$ была больше, веса $W$ штрафовались бы сильнее и стали бы меньше. Пусть, например, веса уменьшились вдвое ($[0{,}5;\ -1;\ 0]$). Теперь softmax вычислит:

$$[0{,}5;\ -1;\ 0] \rightarrow [e^{0{,}5}, e^{-1}, e^0] = [1{,}65;\ 0{,}37;\ 1] \rightarrow [0{,}55;\ 0{,}12;\ 0{,}33]$$

Вероятности стали более размазанными. Более того, в пределе, когда из-за очень сильной регуляризации веса стремятся к крошечным значениям, выходные вероятности будут почти равномерными. Поэтому вероятности классификатора Softmax лучше понимать как степени уверенности: как и у SVM, порядок оценок интерпретируем, а абсолютные значения (или их разности), строго говоря, — нет.

На практике SVM и Softmax обычно сопоставимы. Разница в качестве между SVM и Softmax обычно очень мала, и мнения о том, что лучше, расходятся. По сравнению с Softmax SVM — более локальная цель, что можно считать и недостатком, и достоинством. Возьмём пример с оценками $[10, -2, 3]$, где правильный — первый класс. SVM (с желаемым зазором, скажем, $\Delta = 1$) увидит, что оценка правильного класса уже выше остальных больше чем на зазор, и посчитает нулевые потери. Деталям отдельных оценок SVM безразличен: если бы они были $[10, -100, -100]$ или $[10, 9, 9]$, SVM было бы всё равно — зазор 1 выполнен, потери нулевые. Для классификатора Softmax эти сценарии не равнозначны: для $[10, 9, 9]$ он накопит гораздо больше потерь, чем для $[10, -100, -100]$. Иначе говоря, Softmax никогда до конца не доволен своими оценками: вероятность правильного класса всегда может быть выше, а неправильных — ниже, и потери всегда можно улучшить. SVM же доволен, как только зазоры выполнены, и не «микроменеджит» точные оценки сверх этого ограничения. Это можно считать достоинством: например, классификатор автомобилей, который тратит основные «силы» на трудную задачу отличить машины от грузовиков, не должен отвлекаться на примеры лягушек, которым он и так даёт очень низкие оценки и которые, скорее всего, сгруппированы совсем в другой части облака данных.

Интерактивное веб-демо

Рисунок-ссылка. Мы написали интерактивное веб-демо, чтобы развить интуицию о линейных классификаторах. Демо визуализирует обсуждённые функции потерь на игрушечной задаче классификации трёх классов на двумерных данных. Оно также немного забегает вперёд и выполняет оптимизацию, которую мы подробно обсудим в следующем разделе.

Итоги

• Мы определили функцию оценок из пикселей изображения в оценки классов (в этом разделе — линейную функцию, зависящую от весов W и сдвигов b).
• В отличие от kNN, преимущество этого параметрического подхода в том, что после обучения параметров обучающие данные можно выбросить. Кроме того, предсказание для нового изображения быстрое: оно требует одного умножения на матрицу W, а не полного сравнения с каждым обучающим примером.
• Мы ввели трюк со сдвигом, позволяющий включить вектор сдвига в матрицу весов, чтобы отслеживать только одну матрицу параметров.
• Мы определили функцию потерь (две распространённые для линейных классификаторов: SVM и Softmax), измеряющую, насколько данный набор параметров согласуется с истинными метками обучающей выборки. Мы также увидели, что функция потерь устроена так, что хорошие предсказания на обучающих данных равносильны малым потерям.

Итак, мы увидели один способ взять набор изображений и отобразить каждое в оценки классов на основе набора параметров и два примера функций потерь для оценки качества предсказаний. Но как эффективно найти параметры, дающие наилучшие (наименьшие) потери? Этот процесс — оптимизация, тема следующего раздела.

Дополнительное чтение

Эти материалы необязательны и содержат интересные ссылки.

• Deep Learning using Linear Support Vector Machines — Чарли Тан, 2013: результаты, согласно которым L2-SVM превосходит Softmax.

Словарик

EN	RU
score function	функция оценок
loss function, cost function, objective	функция потерь, функция стоимости, целевая функция
weights, bias	веса, сдвиг
bias trick	трюк со сдвигом
template matching	сопоставление с шаблоном
hinge loss, margin	потери-шарнир (hinge loss), зазор
data loss, regularization loss	потери на данных, потери регуляризации
cross-entropy loss	потери кросс-энтропии
maximum likelihood (MLE), maximum a posteriori (MAP)	максимальное правдоподобие, апостериорный максимум
One-vs-All	один против всех