Персептрон, оптимизация, регуляризация, потеря шарнира, граница поля, SVM

Это мои учебные заметки о двух дискриминативных подходах к построению линейных классификаторов.

  • Настройка проблемы
  • Использование Perceptron для поиска линейного классификатора
  • Линейная классификация как задача оптимизации

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

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

Существует две основные категории методов машинного обучения (или большей области, к которой оно относится): дискриминационные и генеративные.

Короче говоря, дискриминационные методы полагаются исключительно на апостериорное распределение (P(Y|X), где X — наблюдаемые данные, а Y — целевая переменная), тогда как генеративные методы используют байесовский вывод, который требует предположений и оценок априорного распределения (P (Y)) и условное распределение (P(X|Y)).

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

Настройка проблемы

Я использую типичное двумерное пространство для простоты иллюстрации, но все в терминах векторов, поэтому их легко адаптировать к многомерному пространству. Здесь у нас есть две группы точек, помеченные как положительные и отрицательные (следовательно, это контролируемое обучение), и они линейно разделимы. Задача состоит в том, чтобы найти линию, разделяющую точки с разными метками.

На изображении выше показано одно решение. Мы можем выразить эту линию любым из следующих способов, где 𝛩 — вектор нормали к линии (т. е. 𝛩 перпендикулярен линии), а любая точка на линии удовлетворяет приведенному ниже уравнению. Если 𝛩 — вектор 3x1, то он представляет собой плоскость.

Это наша граница принятия решения.

Как это классифицировать? Если точка X находится на той же стороне, на которую указывает вектор нормали, то классификатор классифицирует ее как положительную; если другая сторона, то точка помечается как отрицательная. Правда, это объяснение не имеет особого смысла в многомерном пространстве (›3). Таким образом, математически мы полагаемся на знак левой части уравнения (θ₁x₁+θ₂x₂+θ₀). Если sign(θ₁x₁+θ₂x₂+θ₀) > 0, соответствующая точка считается положительной; и наоборот.

Учебная задача

Подводя итог, задача обучения состоит в том, чтобы найти границу решения, определяемую 𝛩 и масштабером смещения θ₀, чтобы результирующие классификации соответствовали наблюдаемым меткам.

Алгоритм перцептрона

Мне не стыдно признаться, что я никогда не слышал об этом алгоритме до недавнего времени, несмотря на то, что это базовый алгоритм обучения.

Алгоритм персептрона использует простое правило для обновления 𝛩 и θ₀ до тех пор, пока все точки не будут правильно классифицированы, то есть сходимость. Независимо от начальных значений 𝛩 и θ₀, пока проблема линейно разделима, обучение всегда будет сходиться. Инициализация, а также порядок итерации влияют только на количество ошибок/обновлений, которые происходят до сходимости.

Вот как это работает.

Сначала мы инициализируем 𝛩 и θ₀ всеми нулями. Вы можете использовать другие более разумные значения инициализации, если они доступны.

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

Если приведенное выше значение больше 0, классификация верна, поэтому мы переходим к следующей точке i + 1; если нет (≤0), мы обновляем 𝛩 и θ₀ (эта проверка всегда завершалась бы ошибкой с нулевыми значениями инициализации).

По сути, это вращение (если θ₁ и θ₂ не изменяются пропорционально) и изменение длины 𝛩, а также перемещение линии (изменение θ₀), чтобы сделать классификацию правильной в точке i.

Проблемы с линейными классификаторами, изученными с помощью персептрона

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

Другими словами, нас интересует не только то, как линейный классификатор работает с наблюдаемыми точками данных, но и то, как он работает с новыми точками данных (обобщение). Алгоритм персептрона не имеет какой-либо встроенной логики, которая помогла бы нам его оптимизировать; мы должны сформулировать эту задачу по-другому, чтобы рассмотреть оба исполнения.

Линейная классификация как задача оптимизации

Средняя потеря

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

где

Мы можем прочитать z как степень согласия между наблюдаемой меткой и результатом классификации. Если они совпадают, т. е. z ≥ 1, потерь нет; если они не совпадают, т. е. z ‹ 1, то мы определяем потери как 1-z. По мере того, как разногласия становятся больше, потери становятся больше.

Я объясню,почему z НЕ сравнивается с 0, а также что означает увеличение разногласий. Подводя итог, наша первая цель оптимизации состоит в том, чтобы минимизировать эти средние потери.

Поля

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

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

Мы устанавливаем две границы поля, параллельные границе решения (фактический линейный классификатор) на равном расстоянии (марже) от него. Цель оптимизации здесь состоит в том, чтобы максимально увеличить поля, чтобы линейный классификатор лучше обобщал невидимые данные.

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

Красное уравнение представляет собой положительную границу поля и состоит из всех точек, которые удовлетворяют θ₁x₁+θ₂x₂+θ₀=1. Точно так же синее уравнение представляет границу отрицательного поля, и все точки на линии удовлетворяют θ₁x₁+θ₂x₂+θ₀=-1.

Теперь я хочу вернуться к вопросу, почему z НЕ сравнивается с 0, а также к что означает увеличение разногласий.

Если положительная точка находится между границей решения и положительной границей, например, точка A, значение z будет где-то между 0 и 1. Значение z положительно, потому что линейная классифицирует точку A правильно, но z меньше 1, потому что она находится в между решением и положительными границами маржи. В таком случае мы по-прежнему штрафуем эту классификацию, давая ей положительный убыток, потому что граница решения находится слишком близко к точке данных. Вот почему z сравнивается с 1, а не с 0.

Точка C правильно классифицирована и также лежит за отрицательной границей. Следовательно, его z больше 1, и эта классификация получает нулевую потерю. Нетрудно заметить, что чем дальше точка от границы поля, тем больше абсолютное значение z. Если z положительно велико, это означает, что наблюдаемая метка и результат классификации во многом совпадают; если z отрицательно велико, наблюдаемая метка и результат классификации сильно расходятся.

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

Целевая функция

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

Это очень близко к настройке цели обучения для Машины опорных векторов.

В следующем посте я рассмотрю это, а также алгоритмы оптимизации на примере этой целевой функции.