Часть 1
Сегодня я расскажу об очень классической, но все еще широко используемой технике. Это называется «SVM (Машина опорных векторов)».
Это будет разделено на 2 части, в части 1 я расскажу о концепциях SVM и проведу некоторые математические операции, а во второй части я расскажу о ядрах и некоторых других концепциях.
Чтобы добавить, мы используем ядра для нелинейных границ решений, поэтому части 1 и 2 в основном разделены этим стандартом: является ли граница решения линейной или нелинейной.
В этой серии ML я в основном следую содержанию Coursera ML Эндрю Нг, но в этой серии SVM я собираюсь использовать некоторые объяснения MIT OCW, которые мне показались более простыми для понимания.
Давай начнем!
Основная концепция
Границы решения и маржа
Давайте предположим, что у нас есть несколько положительных и несколько отрицательных примеров, и мы собираемся провести линию, правильно разделяющую их, и назвать эту линию границей решения. Какое деление лучше?
Вторая картинка лучше. Но почему? Почему эта граница решения, по сравнению с первой, правильно разделяет примеры? Что значит «правильное» в данном случае?
Просто вторая граница более удалена от примеров (точки данных), чем первая. Опорные векторы — это примеры, близкие к границе решения.
Теперь давайте рассмотрим понятие маржи. Запас — это расстояние между опорными векторами и границей решения. Давайте посмотрим на картинку ниже.
Это маржа. Теперь мы знаем, что наиболее оптимальная граница решения максимизирует маржу. Это называется «Подход к самой широкой улице».
Общий
Основная проблема, которую SVM хочет решить: «Как мы разделим пространство с границами решения», и ответ на это: «Максимизируя поля».
Теперь есть основная концепция, давайте углубимся в некоторые подробные объяснения (математика).
Логическое объяснение
Правило принятия решения
Во-первых, мы должны определить правило принятия решения, чтобы установить границу принятия решения.
Мы хотим знать, принадлежит ли неизвестный пример U к положительной или к отрицательной группе. Таким образом, мы можем установить вектор w, который перпендикулярен границе решения, и установить наш единственный неизвестный пример как вектор u.
Итак, мы можем спроецировать наш вектор u на вектор w, и если эта проекция больше некоторой константы (границы решения), мы знаем, что неизвестный пример принадлежит положительной группе. Таким образом, правило принятия решения выглядит следующим образом:
Добавление дополнительных ограничений
Это было нашим решающим правилом, чтобы выяснить, является ли неизвестный пример положительным или отрицательным. Однако мы не знаем, какой вектор w использовать, поскольку существует множество векторов, перпендикулярных границе решения, и мы не знаем, что такое константа b.
Чтобы решить эту проблему, мы должны добавить некоторые ограничения.
Итак, давайте настаивать на том, чтобы наше правило принятия решений давало значение больше 1, когда данный пример является положительным, и значение меньше -1, когда дается отрицательный пример.
И для математического удобства мы собираемся ввести переменную yᵢ, которая представляет +1, когда пример положительный, и -1, когда пример отрицательный.
И добавьте yᵢ к нашему правилу принятия решений, и это упростит наше правило принятия решений.
Теперь мы собираемся добавить еще одно ограничение. Когда значение равно 0, мы предполагаем, что точки находятся на границе.
Но какова была наша первоначальная цель? Мы хотели максимизировать маржу. Таким образом, ширина между положительным примером на границе и отрицательным примером на границе должна быть максимальной.
Итак, как мы можем выразить ширину?
Мы можем умножить единичный вектор на разницу между x₊ и x₋.
Мы можем выразить первый член, используя это:
Итак, ширина:
Оптимизация
Итак, нам нужно максимизировать ширину, или:
мы можем минимизировать это. Весь этот процесс сделан для математического удобства.
Итак, у нас есть цель и некоторые ограничения.
У нас есть ограничение и цель. Мы можем использовать метод множителей Лагранжа для этой задачи.
*Проф. Патрик Уинстон говорит, что все альфы, за исключением случаев, когда пример находится на границе (+ или -), в конечном итоге становятся равными 0. Кроме того, если мы хотим применить это ко всем примерам, нам нужно использовать неравенство в качестве ограничения. Говорят, что нам нужно использовать условие KKT, но пока давайте просто продолжим.
Нам нужно найти производные и приравнять их к 0.
Производные следующие:
Здесь мы понимаем, что:
Чтобы узнать, что такое w, нам нужно только значение альфа.
Если мы заменим члены в нашем лагранжиане,
Затем,
Здесь профессор Патрик Уинстон говорит: «Теперь мы можем передать это нашим числовым аналитикам».
Теперь проблема превращается в проблему максимизации альфы. Если мы узнаем альфа, мы можем узнать значения w и b.
Кроме того, когда альфа не равна 0, как объяснялось ранее, пример находится на границе, и в SVM мы называем эти примеры «опорными векторами».
Также известно, что в L(a) первый член линеен относительно альфы, а второй член является квадратичным членом, мы можем применить методы квадратичного программирования и узнать альфу.
В любом случае, главное, что нам не нужно беспокоиться о попадании в локальные минимумы, он выпуклый.
Так что в любом случае SVM теоретически всегда дает нам оптимизированное решение.
