Метод опорных векторов для чайников в excel
Вектора и матрицы в электронной таблице хранятся в виде массивов.
Известно, что сумма векторов – это вектор, координаты которого равны суммам соответствующих координат исходных векторов:
Для вычисления суммы векторов нужно выполнить следующую последовательность действий:
- В диапазоны ячеек одинаковой размерности ввести значения числовых элементов каждого вектора.
- Выделить диапазон ячеек для вычисляемого результата такой же размерности, что и исходные векторы.
- Ввести в выделенный диапазон формулу перемножения диапазонов
- = Адрес_Вектора_1 + Адрес_Адрес_Вектора_2
- Нажать комбинацию клавиш [Ctrl] + [Shift] +[Enter].
Даны два вектора:
Требуется вычислить сумму этих векторов.
Решение:
- В ячейки диапазона А2:A4 введем значения координат вектора a1, а в ячейки диапазона С2:С4 – координаты вектора a2.
- Выделим ячейки диапазона, в которых будет вычисляться результирующий вектор С ( E2:E4 ) и введем в выделенный диапазон формулу:
- Нажмем комбинацию клавиш [Ctrl] + [Shift] +[Enter]. В ячейках диапазона E2:E4 будут вычислены соответствующие координаты результирующего вектора.
Как вычислить произведение вектора на число?
Произведением вектора на число является вектор, координаты которого получаются умножением соответствующих координат исходного вектора на это число:
Для вычисления произведения вектора на число нужно выполнить следующую последовательность операций:
- В диапазон ячеек рабочего листа ввести числовые значения элементов вектора.
- В ячейку ввести значение числа, на которое нужно умножить вектор - λ .
- Выделить диапазон ячеек такой же размерности, что и исходный вектор для вычисляемого результата.
- Ввести в выделенный диапазон формулу перемножения диапазонов:
- = Адрес_Вектора_1 * Адрес_Числа
- Нажать комбинацию клавиш [Ctrl] + [Shift] +[Enter].
Как вычислить скалярное произведение векторов?
Известно, что скалярное произведение векторов – это сумма произведений соответствующих координат этих векторов:
Для вычисления скалярного произведения векторов нужно применить следующую последовательность операций:
- В диапазоны ячеек одинаковой размерности ввести значения числовых элементов каждого вектора.
- Выделить диапазон ячеек для вычисляемого результата такой же размерности, что и исходные диапазоны.
- Ввести в выделенный диапазон формулу перемножения диапазонов:
= СУММ(Адрес_Вектора_1 * Адрес_Вектора_2)
Даны два вектора:
Требуется вычислить скалярное произведение этих векторов.
Решение:
- В ячейку, в которой нужно получить результат, например Е2, введем формулу =СУММ(A2:A4*C2:C4) и нажмем комбинацию клавиш [Ctrl] + [Shift] +[Enter]. В результате вычисления будет получен результат – 4.
Метод опорных векторов(SVM - support vector machine) — набор схожих алгоритмов обучения с учителем, использующихся для задач классификации и регрессионного анализа. Принадлежит семейству линейных классификаторов и может также рассматриваться как специальный случай регуляризации по Тихонову.
SVM используется как для линейно разделяемых данных, так и для нелинейных разделяемых данных.
Для нелинейных данных используются функции ядра.
Давайте узнаем о SVC (классификатор опорных векторов) в линейных разделяемых данных, который используется для задач классификации в этой статье.
Темы, затронутые в статье.
Линейно разделяемые данные
- SVM в линейно разделимых данных
- Что такое гиперплоскость?
- Что делает SVM?
- Важные термины, используемые в SVM
- Почему он назван машинами опорных векторов?
- Математика SVM
- Как найти лучшую гиперплоскость?
Линейно разделяемые данные
1. Одномерное пространство
Предположим, у нас есть два класса, красный и зеленый, и если мы можем найти границу, которая разделяет два класса, это называется линейно разделяемыми данными.
Здесь мы могли бы выделить одну точку, которая действует как граница между двумя классами. Точки данных ниже конкретной точки относятся к красному классу, а выше этой конкретной точки относятся к зеленому классу.
2. Двумерное пространство
Точно так же в двухмерном пространстве мы можем нарисовать линию, которая действует как граница между двумя классами.
Здесь точки данных так же линейно разделяются в данном измерении.
Основная идея метода — перевод исходных векторов в пространство более высокой размерности и поиск разделяющей гиперплоскости с максимальным зазором в этом пространстве. Две параллельных гиперплоскости строятся по обеим сторонам гиперплоскости, разделяющей классы. Разделяющей гиперплоскостью будет гиперплоскость, максимизирующая расстояние до двух параллельных гиперплоскостей. Алгоритм работает в предположении, что чем больше разница или расстояние между этими параллельными гиперплоскостями, тем меньше будет средняя ошибка классификатора.
Гиперплоскости - это границы решений, которые классифицируют данные
Постановка задачи
Часто в алгоритмах машинного обучения возникает необходимость классифицировать данные. Каждый объект данных представляется как вектор (точка) в p-мерном пространстве (упорядоченный набор p чисел). Каждая из этих точек принадлежит только одному из двух классов. Вопрос состоит в том, можно ли разделить точки гиперплоскостью размерности ). Это — типичный случай линейной разделимости. Искомых гиперплоскостей может быть много, поэтому полагают, что максимизация зазора между классами способствует более уверенной классификации. То есть, можно ли найти такую гиперплоскость, чтобы расстояние от неё до ближайшей точки было максимальным. Это эквивалентно тому, что сумма расстояний до гиперплоскости от двух ближайших к ней точек, лежащих по разные стороны от неё, максимальна. Если такая гиперплоскость существует, она называется оптимальной разделяющей гиперплоскостью, а соответствующий ей линейный классификатор называется оптимально разделяющим классификатором.
Алгоритм SVM находит лучшую гиперплоскость, которая находится посередине двух классов с максимальным отсупом с обеих сторон.
Точки данных, ближайшие к гиперплоскости в обоих классах, известны как опорные векторы.
Если точка данных, которая является опорным вектором, удаляется, положение гиперплоскости изменяется.
Если точка данных, не являющаяся опорным вектором, удаляется, это не влияет на модель.
Почему метод назван метод опорных векторов?
Гиперплоскость определяется опорными векторами. Если мы удалим точки данных, кроме опорных векторов, гиперплоскость не изменится. Если точка данных, которая является опорным вектором, удаляется, положение гиперплоскости изменяется.
Теперь перейдем к важным моментам.
Как найти лучшую гиперплоскость?
Как нам увеличить маржу?
Сначала давайте разберемся с математикой, лежащей в основе SVM, а затем мы перейдем к двум приведенным выше вопросам.
Математика SVM
Основной принцип SVM заключается в том, что мы хотим нарисовать гиперплоскость с максимальным отступом, разделяющим два класса. Предположим, мы хотим разделить два класса C1 и C2 с помощью SVC в двумерном пространстве. Затем мы хотим предсказать класс неизвестного вектора признаков X как класс C1 или класс C2.
Мы можем использовать линейное уравнение
w → обозначает вектор веса, перпендикулярный гиперплоскости. Он представляет ориентацию гиперплоскости в d-мерном пространстве, где d - размерность вектора признаков.
b → Он представляет положение гиперплоскости в d-мерном пространстве.
Это линейное уравнение в двух измерениях представляет собой прямую линию. Оно представляет собой плоскость в трехмерном пространстве и гиперплоскость в более чем трех измерениях.
Переходя к проблеме классификации. Для каждого вектора признаков мы должны вычислить линейную функцию таким образом, чтобы
1 Если вектор признаков лежит на положительной стороне гиперплоскости,
Метод опорных векторов (далее МОВ) — это техника машинного обучения с учителем. Она используется в классификации, может быть применена к регрессионным задачам.
Метод определяет границу принятия решения (далее ГПР) вместе с максимальным зазором, который разделяет почти все точки на два класса, оставляя место для неправильной классификации.
МОВ — улучшенная версия алгоритмов максимального зазора. Его преимущество заключается в том, что он может определять как линейную, так и нелинейную границу с помощью функций ядра, поэтому он подходит для реальных задач, где данные не всегда полностью разделимы прямой линией.
Разделяющие гиперплоскости
Цель МОВ — определить гиперплоскость (также называется “разделяющей” или “ГПР”), которая разделяет точки на два класса.
Для ее визуализации представим двумерный набор данных:
Гиперплоскостей, разделяющих точки, будет бесконечное множество, но поскольку мы работаем в двумерном пространстве, любая гиперплоскость всегда будет иметь (2–1) = 1 измерение (можно представить её простой линией регрессии).
В свою очередь, точки можно классифицировать, основываясь на том, где они находятся по отношению к ГПР:
Если вы работаете с более чем двумя измерениями, например вектор объектов X имеет более чем два объекта, вы классифицируете сами векторы, а не точки.
Все векторы, которые падают ниже ГПР, принадлежат классу -1, а если выше, то 1.
Зазоры для повышения достоверности прогноза
Мы использовали обучающие данные для определения ГПР. А что насчет качества предсказаний?
Если вектор находится далеко от границы, то можно быть уверенным в его классе, даже если модель в чем-то ошибочна. Но какой класс назначить в ином случае?
МОВ также рисует границу зазора вокруг ГПР. Цель — максимально отделить векторы от нее. Зазор дает больше уверенности в прогнозах: векторы находятся как минимум на расстоянии длины этого зазора от границы, поэтому картина становится более ясной.
Положение зазора определяется с помощью векторов, наиболее близких к границам. Поэтому те из них, что лежат на зазоре, являются опорными векторами .
С зазором в качестве буфера вектор можно классифицировать по его местонахождению относительно зазора, длина которого представлена M.
Пространство для неправильной классификации
Добавление зазора улучшает качество предсказаний, но этого недостаточно для реальных задач.
МОВ, как и классификаторы опорных векторов, использует важную характеристику, которая позволяет ошибаться и присваивать неверный класс некоторым векторам.
Вместо разделения векторов на два класса МОВ идет на компромисс, позволяя некоторым векторам попадать внутрь зазора и на неправильную сторону границы.
МОВ допускает неправильную классификацию в процессе обучения. Он лучше работает с большинством векторов в тестовом наборе.
Помимо зазора, модель теперь включает в себя слабые переменные, которые сообщат:
• классифицировано ли тестовое наблюдение правильно или нет;
• где наблюдение находится относительно ГПР и зазора.
Они могут иметь три возможных значения:
- 0 — классифицировано верно;
- >0 — неверная сторона границы зазора;
- >1 — неверная сторона гиперплоскости.
Число неправильно классифицированных векторов ограничено параметром C:
Эта модель точнее, но она все еще построена поверх классификаторов максимального зазора. Например, если C = 0 (то есть слабые переменные могут быть равны 0), модель возвращается к такому классификатору. Таким образом, есть линейная граница решения и максимально большой зазор, внутри которого не могут находиться векторы.
Рост числа слабых переменных влияет на количество допустимых ошибок, что, в свою очередь, затрагивает ширину зазора из-за выбора различных опорных векторов. Также он контролирует компромисс между смещением и дисперсией модели.
Большое число слабых переменных:
- Большой зазор.
- Низкий уровень дисперсии.
- Большое смещение.
- Больше опорных векторов.
Малое число слабых переменных:
- Малый зазор.
- Высокий уровень дисперсии.
- Низкое смещение.
- Меньше опорных векторов.
Наличие некоторого пространства для ошибок делает МОВ более гибким, но подход применим к ограниченному набору проблем.
В реальных задачах трудно разделить данные на два класса линейной границей.
Метод опорных векторов
Этот метод разделяет характеристики классификаторов запаса. Уникальность его в том, что он может определять как линейные, так и нелинейные ГПР.
Для второго МОВ использует функции для преобразования исходного пространства объектов в новое, которое может представлять эти нелинейные отношения.
Предположим, вы увеличиваете исходное пространство объектов возведением во вторую степень. Вы применили квадратичную функцию к исходному набору объектов. Теперь в этом расширенном пространстве есть оригинальная функция и ее квадратичная версия. Здесь неявно существует функция, которая сопоставляет эти два пространственных объекта.
Если вы попытаетесь нарисовать границу решения в исходном пространстве объектов, она будет иметь квадратичную форму. Но если вы тренируете модель в расширенном пространстве, то обнаружите линейную границу, которая разделяет два класса. Поскольку это является преобразованием, квадратичная граница в исходном пространстве объектов соответствует линейной в расширенном.
Функции выше называются ядрами . Они работают как функции сходства между наблюдениями в обучающих и тестовых наборах.
Граница решения и запасдля МОВ, наряду с соответствующими опорными векторами, используют линейное (справа) и полиномиальное ядро (слева).
Граница решения и запасдля МОВ, наряду с соответствующими опорными векторами, используют линейное (справа) и полиномиальное ядро (слева).
Когда есть модель, представленная внутренними результатами, можно подключить функцию ядра. Линейное ядро — это аналог применения линейных преобразований к пространству объектов. И в этом случае это то же, что и классификатор опорных векторов, потому что ГПР линейна.
С полиномиальными ядрами вы проецируете исходное пространство объектов в полиномиальное. Граница, разделяющая классы, определяется полиномом более высокого порядка.
Использование ядер отличает классификаторы от метода опорных векторов, что открывает путь к решению более сложных задач. Но увеличение пространства признаков означает рост вычислительных требований. При большомпространстве функций подгонка модели станет дорогостоящей с точки зрения времени и ресурсов.
Ядра добавляют преимущество. МОВ не вычисляет преобразование каждого наблюдения в расширенное пространство. Используется трюк с ядром — вычисляется внутреннийрезультат наблюдений в этом пространстве. Этот трюкгораздо менее требователен.
МОВ делает два важных допущения:
- Данные линейно разделимы. Даже если линейная граница находится в расширенном пространстве.
- Модель представлена с использованием внутренних результатов , что допускает применение ядер.
Примеры
Я сгенерировал случайный набор данных и разделил его на два разных класса:
В данной статье я хочу рассказать о проблеме классификации данных методом опорных векторов (Support Vector Machine, SVM). Такая классификация имеет довольно широкое применение: от распознавания образов или создания спам-фильтров до вычисления распределения горячих аллюминиевых частиц в ракетных выхлопах.
Сначала несколько слов об исходной задаче. Задача классификации состоит в определении к какому классу из, как минимум, двух изначально известных относится данный объект. Обычно таким объектом является вектор в n-мерном вещественном пространстве . Координаты вектора описывают отдельные аттрибуты объекта. Например, цвет c, заданный в модели RGB, является вектором в трехмерном пространстве: c=(red, green, blue).
Если классов всего два («спам / не спам», «давать кредит / не давать кредит», «красное / черное»), то задача называется бинарной классификацией. Если классов несколько — многоклассовая (мультиклассовая) классификация. Также могут иметься образцы каждого класса — объекты, про которые заранее известно к какому классу они принадлежат. Такие задачи называют обучением с учителем, а известные данные называются обучающей выборкой. (Примечание: если классы изначально не заданы, то перед нами задача кластеризации.)
Метод опорных векторов, рассматриваемый в данной статье, относится к обучению с учителем.
Итак, математическая формулировка задачи классификации такова: пусть X — пространство объектов (например, ), Y — наши классы (например, Y = ). Дана обучающая выборка: . Требуется построить функцию (классификатор), сопоставляющий класс y произвольному объекту x.
Метод опорных векторов
Данный метод изначально относится к бинарным классификаторам, хотя существуют способы заставить его работать и для задач мультиклассификации.
Идея метода
Идею метода удобно проиллюстрировать на следующем простом примере: даны точки на плоскости, разбитые на два класса (рис. 1). Проведем линию, разделяющую эти два класса (красная линия на рис. 1). Далее, все новые точки (не из обучающей выборки) автоматически классифицируются следующим образом:
точка выше прямой попадает в класс A,
точка ниже прямой — в класс B.
Такую прямую назовем разделяющей прямой. Однако, в пространствах высоких размерностей прямая уже не будет разделять наши классы, так как понятие «ниже прямой» или «выше прямой» теряет всякий смысл. Поэтому вместо прямых необходимо рассматривать гиперплоскости — пространства, размерность которых на единицу меньше, чем размерность исходного пространства. В , например, гиперплоскость — это обычная двумерная плоскость.
В нашем примере существует несколько прямых, разделяющих два класса (рис. 2):
С точки зрения точности классификации лучше всего выбрать прямую, расстояние от которой до каждого класса максимально. Другими словами, выберем ту прямую, которая разделяет классы наилучшим образом (красная прямая на рис.2). Такая прямая, а в общем случае — гиперплоскость, называется оптимальной разделяющей гиперплоскостью.
Вектора, лежащие ближе всех к разделяющей гиперплоскости, называются опорными векторами (support vectors). На рисунке 2 они помечены красным.
Немного математики
Пусть имеется обучающая выборка: .
Метод опорных векторов строит классифицирующую функцию F в виде ,
где — скалярное произведение, w — нормальный вектор к разделяющей гиперплоскости,b — вспомогательный параметр. Те объекты, для которых F(x) = 1 попадают в один класс, а объекты с F(x) = -1 — в другой. Выбор именно такой функции неслучаен: любая гиперплоскость может быть задана в виде для некоторых w и b.
Далее, мы хотим выбрать такие w и b которые максимизируют расстояние до каждого класса. Можно подсчитать, что данное расстояние равно . Проблема нахождения максимума эквивалентна проблеме нахождения минимума . Запишем все это в виде задачи оптимизации:
которая является стандартной задачей квадратичного программирования и решается с помощью множителей Лагранжа. Описание данного метода можно найти в Википедии.
Линейная неразделимость
На практике случаи, когда данные можно разделить гиперплоскостью, или, как еще говорят, линейно, довольно редки. Пример линейной неразделимости можно видеть на рисунке 3:
В этом случае поступают так: все элементы обучающей выборки вкладываются в пространство X более высокой размерности с помощью специального отображения . При этом отображение выбирается так, чтобы в новом пространстве X выборка была линейно разделима.
Классифицирующая функция F принимает вид . Выражение называется ядром классификатора. С математической точки зрения ядром может служить любая положительно определенная симметричная функция двух переменных. Положительная определенность необходимо для того, чтобы соответствующая функция Лагранжа в задаче оптимизации была ограничена снизу, т.е. задача оптимизации была бы корректно определена.
Точность классификатора зависит, в частности, от выбора ядра. На видео можно увидеть иллюстрирацию классификации при помощи полиномиального ядра:
Чаще всего на практике встречаются следующие ядра:
Полиномиальное:
Радиальная базисная функция:
Гауссова радиальная базисная функция:
Сигмоид:
Заключение и литература
Среди других классификаторов хочу отметить также метод релевантных векторов (Relevance Vector Machine, RVM). В отличие от SVM данный метод дает вероятности, с которыми объект принадлежит данному классу. Т.е. если SVM говорит "x принадлежит классу А", то RVM скажет "x принадлежит классу А с вероятностью p и классу B с вероятностью 1-p".
1. Christopher M. Bishop. Pattern recognition and machine learning, 2006.
В данной статье рассмотрим метод опорных векторов (англ. SVM, Support Vector Machine) для задачи классификации. Будет представлена основная идея алгоритма, вывод настройки его весов и разобрана простая реализация своими руками. На примере датасета будет продемонстрирована работа написанного алгоритма с линейно разделимыми/неразделимыми данными в пространстве и визуализация обучения/прогноза. Дополнительно будут озвучены плюсы и минусы алгоритма, его модификации.
Рисунок 1. Фото цветка ириса из открытых источников
Решаемая задача:
Будем решать задачу бинарной (когда класса всего два) классификации. Сначала алгоритм тренируется на объектах из обучающей выборки, для которых заранее известны метки классов. Далее уже обученный алгоритм предсказывает метку класса для каждого объекта из отложенной/тестовой выборки. Метки классов могут принимать значения . Объект — вектор c N признаками в пространстве . При обучении алгоритм должен построить функцию , которая принимает в себя аргумент — объект из пространства и выдает метку класса .
Общие слова об алгоритме:
Задача классификации относится к обучению с учителем. SVM — алгоритм обучения с учителем. Наглядно многие алгоритмы машинного обучения можно посмотреть в этой топовой статье (см. раздел «Карта мира машинного обучения»). Нужно добавить, что SVM может применяться и для задач регрессии, но в данной статье будет разобран SVM-классификатор.
Главная цель SVM как классификатора — найти уравнение разделяющей гиперплоскости
в пространстве , которая бы разделила два класса неким оптимальным образом. Общий вид преобразования объекта в метку класса : . Будем помнить, что мы обозначили . После настройки весов алгоритма и (обучения), все объекты, попадающие по одну сторону от построенной гиперплоскости, будут предсказываться как первый класс, а объекты, попадающие по другую сторону — второй класс.
Внутри функции стоит линейная комбинация признаков объекта с весами алгоритма, именно поэтому SVM относится к линейным алгоритмам. Разделяющую гиперплоскость можно построить разными способами, но в SVM веса и настраиваются таким образом, чтобы объекты классов лежали как можно дальше от разделяющей гиперплоскости. Другими словами, алгоритм максимизирует зазор (англ. margin) между гиперплоскостью и объектами классов, которые расположены ближе всего к ней. Такие объекты и называют опорными векторами (см. рис.2). Отсюда и название алгоритма.
Рисунок 2. SVM (основа рисунка отсюда)
Подробный вывод правил настройки весов SVM:
Чтобы разделяющая гиперплоскость как можно дальше отстояла от точек выборки, ширина полосы должна быть максимальной. Вектор — вектор нормали к разделяющей гиперплоскости. Здесь и далее будем обозначать скалярное произведение двух векторов как или . Давайте найдем проекцию вектора, концами которого являются опорные вектора разных классов, на вектор . Эта проекция и будет показывать ширину разделяющий полосы (см. рис.3):
Рисунок 3. Вывод правил настройки весов (основа рисунка отсюда)
Отступом (англ. margin) объекта x от границы классов называется величина . Алгоритм допускает ошибку на объекте тогда и только тогда, когда отступ отрицателен (когда и разных знаков). Если , то объект попадает внутрь разделяющей полосы. Если , то объект x классифицируется правильно, и находится на некотором удалении от разделяющей полосы. Т.е. алгоритм будет правильно классифицировать объекты, если выполняется условие:
Если объединить два выведенных выражения, то получим дефолтную настройку SVM с жестким зазором (hard-margin SVM), когда никакому объекту не разрешается попадать на полосу разделения. Решается аналитически через теорему Куна-Таккера. Получаемая задача эквивалентна двойственной задаче поиска седловой точки функции Лагранжа.
Всё это хорошо до тех пор, пока у нас классы линейно разделимы. Чтобы алгоритм смог работать и с линейно неразделимых данными, давайте немного преобразуем нашу систему. Позволим алгоритму допускать ошибки на обучающих объектах, но при этом постараемся, чтобы ошибок было поменьше. Введём набор дополнительных переменных , характеризующих величину ошибки на каждом объекте . Введём в минимизируемый функционал штраф за суммарную ошибку:
Будем считать количество ошибок алгоритма (когда M<0). Назовем это штрафом (Penalty). Тогда штраф для всех объектов будет равен сумме штрафов для каждого объекта , где — пороговая функция (см. рис.4):
Далее сделаем штраф чувствительным к величине ошибки (чем сильнее "уходит в минус" — тем больше штраф) и заодно введем штраф за приближение объекта к границе классов. Для этого возьмем функцию, которая ограничивает пороговую функцию ошибки (см. рис.4):
При добавлении к выражению штрафа слагаемое получаем классическую фукцию потерь SVM с мягким зазором (soft-margin SVM) для одного объекта:
— функция потерь, она же loss function. Именно ее мы и будем минимизировать с помощью градиентного спуска в реализации руками. Выведем правила изменения весов, где – шаг спуска:
Возможные вопросы на собеседованиях (основано на реальных событиях):
После общих вопросов про SVM: Почему именно Hinge_loss максимизирует зазор? – для начала вспомним, что гиперплоскость меняет свое положение тогда, когда изменяются веса и . Веса алгоритма начинают меняться, когда градиенты лосс-функции не равны нулю (обычно говорят: “градиенты текут”). Поэтому мы специально подобрали такую лосс-функцию, у которой начинают течь градиенты в нужное время. выглядит следующим образом: . Помним, что зазор . Когда зазор достаточно большой ( или более), выражение становится меньше нуля и (поэтому градиенты не текут и веса алгоритма никак не изменяются). Если же зазор m достаточно мал (например, когда объект попадает на полосу разделения и/или отрицательный (при неверном прогнозе классификации), то Hinge_loss становится положительной (), начинают течь градиенты и веса алгоритма изменяются. Резюмируя: градиенты текут в двух случаях: когда объект выборки попал внутрь полосы разделения и при неправильной классификации объекта.
Для проверки уровня иностранного языка возможны подобные вопросы: What are the similarities and differences between LogisticRegression and SVM? – firstly, we will talk about similarities: both of algorithms are linear classification algorithms in supervised learning. Some similarities are in their arguments of loss functions: for LogReg and for SVM (look at picture 4). Both of algorithms we can configure using gradient descent. Next let’s talk about differences: SVM return class label of object unlike LogReg, which return probability of class membership. SVM can’t work with class labels (without renaming classes) unlike LogReg (LogReg loss finction for : , where – real class label, – algorithm’s return, probability of belonging object to class). More than that, we can solve hard-margin SVM problem without gradient descent. The task of searching support vectors is reduced to search saddle point in the Lagrange function – this task refers to quadratic programming only.
Риcунок 4. Функции потерь
Простая имплементация классического soft-margin SVM:
Внимание! Ссылку на полный код вы найдете в конце статьи. Ниже будут представлены блоки кода, вырванные из контекста. Некоторые блоки можно запускать только после отработки предыдущих блоков. Под многими блоками будут размещены картинки, которые показывают, как отработал код, размещенный над ней.
Подробно рассмотрим работу каждого блока строчек:
1) создаем функцию add_bias_feature(a), которая автоматически расширяет вектор объектов, добавляя в конец каждого вектора число 1. Это нужно для того, чтобы «забыть» про свободный член b. Выражение эквивалентно выражению . Мы условно считаем, что единица — это последняя компонента вектора для всех векторов x, а . Теперь настройку весов и будем производить одновременно.
2) далее опишем сам классификатор. Он имеет внутри себя функции инициализации init(), обучения fit(), предсказания predict(), нахождения лосс функции hinge_loss() и нахождения общей лосс функции классического алгоритма с мягким зазором soft_margin_loss().
3) при инициализации вводятся 3 гиперпараметра: _etha – шаг градиентного спуска (), _alpha – коэффициент быстроты пропорционального уменьшения весов (перед квадратичным слагаемым в функции потерь ), _epochs – количество эпох обучения.
4) при обучении для каждой эпохи обучающей выборки (X_train, Y_train) мы будем брать по одному элементу из выборки, вычислять зазор между этим элементом и положением гиперплоскости в данный момент времени. Далее в зависимости от величины этого зазора мы будем изменять веса алгоритма с помощью градиента функции потерь . Заодно будем вычислять значение этой функции на каждой эпохе и сколько раз мы изменяем веса за эпоху. Перед началом обучения убедимся, что в функцию обучения пришло действительно не больше двух разных меток класса. Перед настройкой весов происходит их инициализация с помощью нормального распределения.
Проверка работы написанного алгоритма:
Проверим, что наш написанный алгоритм работает на каком-нибудь игрушечном наборе данных. Возьмем датасет Iris. Подготовим данные. Обозначим классы 1 и 2 как , а класс 0 как . С помощью алгоритма PCA (объяснение и применение тут) оптимальным образом сократим пространство 4-х признаков до 2-х с минимальными потерями данных (нам будет проще наблюдать за обучением и разультатом). Далее разделим на обучающую (трейн) выборку и отложенную (валидационную). Обучим на трейн выборке, прогнозируем и проверяем на отложенной. Подберем коэффициенты обучения таким образом, чтобы лосс функция падала. Во время обучения будем смотреть на лосс функцию обучающей и отложенной выборки.
Читайте также: