Теоретически красивый алгоритм 🎆
До 1980-х годов почти все методы обучения изучали линейные поверхности решений, и они обладали хорошими теоретическими свойствами. В 1980-х годах деревья решений и нейронные сети позволили эффективно изучать нелинейные поверхности решений, но имели мало теоретической основы и страдали локальными минимумами. Когда дело доходит до 1990-х годов, была разработана машина опорных векторов (SVM), которая имеет хорошие теоретические свойства и может избегать локальных минимумов.
В этом посте я расскажу о форме соответствующей задачи выпуклой оптимизации, а затем о том, как использовать множитель Лагранжа для решения двойственной задачи. Кроме того, он представит хитрость ядра. Обратите внимание, что в данный момент я покажу только наивную версию (жесткая маржа). Я, вероятно, добавлю версию с мягкими краями в будущем.
Обзор
SVM — классический бинарный классификатор. Учитывая обучающий набор D = {(x1, x2), (x2, y2)…(xm, ym)}, yi ∈ {-1, 1}, мы хотим найти гиперплоскость в пространстве выборок для разделения разных классов. SVM определяет лучшую линию с максимальной маржой. Каждый образец должен выходить за пределы поля. Чем больше поле, тем больше мы уверены, что невидимые образцы будут правильно классифицированы.
В условном пространстве мы определяем делитель гиперплоскости как w’x + b = 0, где w — вектор нормали. Выберите любую точку x’ в образце пространства, расстояние от x’ до гиперплоскости равно
Доказательство
Выберите любую точку на гиперплоскости x, расстояние от x’ до гиперплоскости равно проекции (x’-x) на вектор нормали w.
Мы предполагаем, что гиперплоскость может правильно классифицировать выборки, тогда, если w’x +b ≥ 1, метка должна быть положительной; если w’x + b ≤ -1, метка должна быть отрицательной. Чтобы сделать эти два неравенства чище, мы введем переменную y так, что y = +1 для положительных выборок, y = -1 для отрицательных выборок. Таким образом, мы можем сделать наши неравенства для y(w’x +b) ≥1. Это наше предположение.
Опорные векторы определяются как образцы, находящиеся ближе всего к гиперплоскости. Поэтому мы масштабируем, чтобы образцы, наиболее близкие к гиперплоскости, удовлетворяли w’x +b = 1 и w’x + b = -1. (как показано слева)
После подстановки полученного нами уравнения расстояния расстояние между двумя векторами поддержки разных классов равно 2/||w||. Чтобы найти гиперплоскость с максимальным полем, нужно найти w и b, которые удовлетворяют
Мы можем переписать задачу максимизации в задачу минимизации.
И это основная форма машины опорных векторов, функция квадратичного программирования.
Оптимизация — проблема двойственности
- Проблема двойственности легче оптимизировать
- Мы можем получить форму внутреннего продукта, где мы можем применить метод ядра
По указанным выше причинам мы хотим преобразовать проблему в двойственную задачу. Мы можем сделать это, применив множитель Лагранжа
Подставим w = Σ αyx к исходной формуле гиперплоскости, получим
Из-за условия KKT нам нужно удовлетворить
Мы можем заметить, что для не опорных векторов их множитель Лагранжа должен быть равен 0. Таким образом, чтобы получить f (x), нам нужно только вычислить внутренний продукт между новыми выборками и опорными векторами.
Хитрости ядра
Внутренний продукт имеет здесь и другую большую силу!
Графически,
- Два очень похожих вектора xi, xj, которые предсказывают разные классы, стремятся максимизировать ширину поля.
2. Два похожих вектора, но предсказывающие один и тот же класс, избыточны.
3. Два непохожих (ортогональных) вектора вообще не считаются
Мы можем использовать Kernel Tricks для увеличения пространства признаков без явного обращения к многомерному пространству признаков. Это еще одно мощное преимущество, которое дает двойная форма: нам не нужны дополнительные тяжелые вычисления во время обучения и прогнозирования, и мы можем бесплатно увеличить пространство признаков!
Для демонстрационного пространства, которое не является линейно разделимым, как показано ниже, мы можем использовать трюк ядра для создания нелинейных классификаторов.
Исходная двойная проблема становится
Функция классификации становится
Некоторые распространенные ядра включают
Вопросы для интервью
- Объясните SVM нетехническому человеку.
- Можете ли вы объяснить SVM？
- Какая геометрическая интуиция стоит за SVM?
- Объясните двойную форму формулировки SVM?
- Объясните, что такое потеря шарнира?
- Что такое «уловка ядра» и чем она полезна?
- Следует ли использовать простую или двойственную форму задачи SVM для обучения модели на обучающем наборе с миллионами экземпляров и сотнями функций?
- Объясните о регрессии SVM?
- Приведите несколько ситуаций, в которых вы будете использовать SVM вместо алгоритма машинного обучения RandomForest.
- Можем ли мы применить трюк с ядром к логистической регрессии? Почему тогда это не используется на практике?
Спасибо за прочтение статьи! Надеюсь, это полезно. Если вам нужна дополнительная информация, дайте мне знать.
