Здесь мы говорим о математике, лежащей в основе численных алгоритмов SVM.
Установка сцены. Вы когда-нибудь задумывались, почему один алгоритм работает, а другой - нет? Эта история открывает новую серию статей, задуманных как полное руководство с целью не только научить вас писать несколько строк вызовов функций, но и сделать математику более понятной для тех, кто хотел бы принимать обоснованные решения. при выборе алгоритма. Кроме того, это также позволяет освежить свои навыки перед собеседованием по вопросам машинного обучения.
Наша самая первая серия разработана, чтобы познакомить вас с машинами опорных векторов (SVM), одним из хорошо известных алгоритмов контролируемого обучения. В этой серии статей основное внимание уделяется не линейной алгебре, которая стоит за разделяющими гиперплоскостями. Об этом много раз говорилось в многочисленных статьях и книгах по машинному обучению - хорошую можно найти здесь. Таким образом, мы решили взглянуть на SVM как на проблему оптимизации и представить два очень разных алгоритма, которые помогут нам решить эту проблему. Мы начнем с основ оптимизации с ограничениями, а затем перейдем к формулировкам задач с использованием двух эффективных методов оптимизации.
Вот наш план - вам не придется тратить дополнительное время на чтение того, что вы уже знали раньше.
- Говорящая математика: квадратичное программирование и разложение Холецкого
- Говоря о математике: Поддержка векторной машины как задача оптимизации с ограничениями
- Говорящие алгоритмы: использование методов внутренней точки для обучения SVM
- Говорящие алгоритмы: использование последовательной оптимизации для обучения SVM
В этой статье мы разберем общую форму задачи оптимизации с ограничениями, поговорим о лагранжиане, его двойственной форме и, наконец, обсудим факторизацию Холецкого.
Что такое выпуклость?
Мы начнем с некоторых математических идей, которые нам пригодятся в дальнейшем. Давайте сначала поговорим о выпуклости. У нас может быть выпуклое множество и выпуклая функция. Представим, что у нас есть набор элементов S (set). По сути, это когда вы можете нарисовать линию, соединяющую любые две точки, которые принадлежат нашему недавно созданному набору S, и сегмент линии будет лежать полностью ниже. Вогнутость - это то же самое, только перевернутая - теперь у вас есть отрезок линии, который лежит выше. Это неформальное определение, которое помогает представить вещи в своей голове. Нравится
Теперь поговорим о выпуклой функции. Все становится немного сложнее - нам нужно предоставить одно свойство выпуклых функций. Это - функция определяется как выпуклая, если ее область определения S является выпуклым множеством (как мы только что видели) и если для тех двух точек x и y, которые принадлежат нашему множеству S, выполняется следующее свойство.
Это также называется неравенством Дженсена, и это часто задаваемый вопрос на собеседовании . Интуитивно вы можете думать об ожидаемой стоимости - это поможет не забыть!
Что такое аффинные функции?
Мы обсудили самый первый инструмент, который необходим для полного понимания идеи, лежащей в основе ограниченной оптимизации. Второй строительный блок - аффинные функции. Самый простой способ задуматься о них - это начать с системы линейных уравнений. Помните эту концепцию из линейной алгебры?
Функция является аффинной, если она является суммой линейной функции и константы, т. Е. Если она имеет вид
Есть интересная особенность, связанная с численной оптимизацией и выпуклостью. Если мы предположим, что у нас есть f (S), где f аффинно, а S - выпуклое множество, тогда изображение под f будет выпуклым. Просто чтобы сэкономить ваше время, вспоминая, что это за изображение - это набор всех выходов.
Возникает естественный вопрос: почему мы беспокоимся?
Ограниченная оптимизация: лагранжиан и двойственность сочетаются
Чтобы найти оптимальную гиперплоскость для задачи SVM, нам нужно сформулировать ее как задачу ограниченной оптимизации. Это когда все, что мы до сих пор обсуждали, объединится в одну картину. Поехали 🚀
Задача выпуклой оптимизации имеет вид
и это требует
- Целевая функция должна быть выпуклой.
- Функции ограничения неравенства должны быть выпуклыми.
- Функции ограничения равенства должны быть аффинными.
В этой форме у нас все разделено, но что нам делать, если мы хотим собрать все вместе? Мы называем это лагранжевым!
Общая идея лагранжевой двойственности (L) состоит в том, чтобы учесть ограничение путем увеличения целевой функции взвешенной суммой функций ограничений.
И согласно приведенному выше описанию мы имеем следующие
Лямбда и nu - множители Лагранжа. Первый связан с ограничением-неравенством, а второй - с ограничением-равенством. Эту проблему можно преобразовать в двойную форму в надежде, что ее будет легче решить. Тогда у нас есть лагранжева двойственная форма
Он определяется как минимальное значение лагранжиана по всем x
У этой функции есть одно свойство, которое делает ее чрезвычайно полезной. Двойственная функция - это точечная нижняя грань (inf) семейства аффинных функций, и по построению (вы можете прочитать об этом здесь и здесь) она является вогнутой, даже если задача не является выпуклой. Таким образом, двойственная функция дает нижнюю границу оптимального значения p *.
Смущены последними предложениями? Я знаю, что мы тоже были там. Прежде чем мы покажем один пример, который проясняет это, мы должны отметить, что для некоторых задач оптимизации с ограничениями у нас есть нулевой разрыв двойственности. По сути, это означает, что оптимальные минимумы могут быть достигнуты, рассматривая либо прямую, либо двойную задачу. Это свойство проявляется (1), если у нас есть выпуклая квадратичная целевая функция и аффинные функции ограничений и (2) если матрица Гессе относительно (wrt) x равна полуопределенный или определенный. Хорошие новости! SVM - это как раз такая проблема 😄
Еще одна вещь, которую очень важно обсудить - в оптимальных минимумах должны выполняться условия Каруша-Куна-Таккера (KKT)! Не беспокойтесь об этом прямо сейчас, мы объясним, как включить их в проблему в будущем!
Отображение нулевого разрыва двойственности
Теперь мы вернемся к нулевому разрыву дуальности и покажем наглядно, что это означает на самом деле. Для репрезентативных целей мы выбираем очень известную функцию и одно линейное ограничение. Мы хотим найти точечную нижнюю грань, если мы сохраняем фиксированные лямбды.
Вдоль оси x, если мы зафиксируем лямбду, мы сможем увидеть поверхность, похожую на параболу. Хорошая особенность этого графика заключается в том, что мы можем ясно видеть, что, с другой стороны, если мы исправим x, лагранжиан будет линейная функция лямбда. Если ограничение нарушается, поэтому у нас есть ось x, которая является недопустимой, дает нам положительный наклон, тогда как для допустимого x наклон будет отрицательным. Мы построили лагранжиан, и его внешний вид будет общим. Чтобы взглянуть на двойственную функцию, поскольку этот лагранжиан является квадратичной функцией, мы знаем, как взять от нее inf, в данном случае минимум (вершину), а затем найти максимум. Как это соответствует лагранжиану? Мы разрезали параллельно x и каждый раз брали inf по x и назначали его двойной функции. Мы наносим на нашу поверхность точки, соответствующие функции inf для каждой отдельной лямбды. Вот где двойственная функция находится в лагранжиане.
Факторизация Холецкого
Теперь мы готовы сформулировать SVM как задачу квадратичного программирования. Мы сделаем это в двух следующих статьях! Теперь нам нужно обсудить последний математический инструмент, который необходим для полного понимания идеи, лежащей в основе методов внутренней точки - теперь мы поговорим о разложении Холецкого!
Каждую положительно определенную матрицу можно разложить на множители как
R - верхний треугольник с положительными диагональными элементами. Напомним также, что положительно определенная матрица является симметричной матрицей, когда
Это математические формулировки определенной матрицы и факторизация Холецкого.
Возникает естественный вопрос: зачем нам нужны все эти математические вычисления для SVM и как решать это численно? Мы ответим на все эти вопросы в следующих статьях 😜 🚀
Попробуй себя
- В чем неравенство Дженсена?
- Как определяются аффинные функции?
- Определите задачу оптимизации с ограничениями, лагранжиан и его двойственную форму
- Какую матрицу можно разложить на факторизацию Холецкого?
