Рисование линий с помощью Лагранжа

1. Обзор

В этом блоге будет исследована механика машин опорных векторов. Во-первых, давайте сделаем обзор этой статьи со скоростью 100 миль в час (настоятельно рекомендуем вам просмотреть ее, прежде чем читать эту). По сути, нам даны некоторые точки в n-мерном пространстве, где каждая точка имеет двоичную метку и мы хотим разделить их гиперплоскостью. Обозначим любую точку в этом пространстве через x. Тогда любую гиперплоскость можно представить в виде: w ^ T x + b = 0. Поясним терминологию.

  1. x ^ i: i-я точка в d-мерном пространстве, указанном выше. Итак, это вектор длины d, и все его элементы являются действительными числами (x ∈ R ^ d).
  2. t ^ i: двоичная метка этой i-й точки. Это может быть 1 или 0.
  3. w: для гиперплоскости, разделяющей пространство на две области, коэффициент вектора x.
  4. b: для гиперплоскости, разделяющей пространство на две области, постоянный член.

В предыдущем блоге мы вывели задачу оптимизации, которая в случае ее решения дает нам w и b, описывающие разделяющую плоскость (отсюда мы продолжим нумерацию нашего уравнения, γ была фиктивной переменной), которая максимизирует маржу или расстояние до ближайшей точки от плоскости. Обратите внимание, что для каждой точки данных существует одно ограничение неравенства.

Затем мы сделали несколько ниндзюцу, чтобы избавиться даже от γ и свести к следующей задаче оптимизации:

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

2. Решение с использованием множителей Лагранжа.

В предыдущем блоге этой серии мы получили две задачи оптимизации с ограничениями (уравнения (4) и (7) выше), которые можно использовать для получения плоскости, которая максимизирует запас. Существует общий метод решения задач оптимизации с ограничениями (метод множителей Лагранжа). Чтобы все было сфокусировано, мы просто сформулируем здесь рецепт и воспользуемся им, чтобы разобраться в проблеме SVM. О том, почему этот рецепт работает, читайте этот блог, где подробно рассматриваются множители Лагранжа. Если у нас есть общая проблема оптимизации,

Шаг 1: Определите функцию Лагранжа:

Где α_i и β_i - дополнительные переменные, называемые множителями Лагранжа. Множители, соответствующие неравенствам α_i, должны быть ≥0, а множители, соответствующие равенствам, β_i могут быть любыми действительными числами. Опять же, некоторая визуальная интуиция, почему это так, дается здесь. Тогда условия, которые должны быть выполнены для того, чтобы w было оптимальным (называемые условиями KKT), следующие:

Уравнение 10-e называется условием комплементарности и гарантирует, что если ограничение неравенства не является «жестким» (g_i (w) ›0, а не = 0), то множитель Лагранжа, соответствующий этому ограничению, должен быть равен нулю. Оказывается, это так, потому что множители Лагранжа можно интерпретировать как определяющие, насколько сильно ограничение неравенства «давится» в оптимальной точке. Если ограничение даже не жесткое (активное), мы вообще не противодействуем ему в решении и, следовательно, соответствующем множителе Лагранжа, α_i = 0. Уравнения 10b и 10c довольно тривиальны, поскольку они просто заявляют, что ограничения исходной задачи оптимизации должны выполняться в оптимальной точке (почти тавтология).

2.1. Замечание о SVM

Вернемся к поддержке векторных машин. В уравнениях (4) и (7) мы указали ограничение в виде неравенства для каждой из точек с точки зрения их перпендикулярного расстояния от разделяющей линии (полей). Точка с минимальным расстоянием от линии (поля) будет той, ограничение которой будет равенством. Если есть несколько точек, которые разделяют это минимальное расстояние, все они будут иметь свои ограничения в соответствии с уравнениями (4) или (7), которые станут равенствами. Такие точки называются «опорными векторами», поскольку они «поддерживают» линию между ними (как мы увидим). Из геометрии задачи легко увидеть, что должно быть по крайней мере два опорных вектора (точки, которые имеют минимальное расстояние от линии и, следовательно, имеют «жесткие» ограничения), один с положительной меткой, а другой - с меткой. отрицательная этикетка. Предположим, что это не так и есть только одна точка с минимальным расстоянием d. Без ограничения общности можно считать, что эта точка имеет положительную метку. Затем есть еще одна точка с отрицательной меткой на другой стороне линии, расстояние до которой d + δd. Можно переместить линию на расстояние δd / 2 вдоль вектора w в сторону отрицательной точки и увеличить минимальный запас на это же расстояние (и теперь как ближайшие положительные, так и самые близкие отрицательные точки становятся опорными векторами). Это означает, что другая линия, с которой мы начали, была лжепророком; На самом деле это не могло быть оптимальной маржой, поскольку мы легко улучшили маржу.

Но это полностью зависело от геометрической интерпретации задачи. Если бы вместо этого нам были даны только задачи оптимизации (4) или (7) (мы предположим, что знаем, как получить одно из другого), могли бы мы прийти к такому же выводу? Для задачи в уравнении (4) лагранжиан, определенный в уравнении (9), принимает следующий вид:

Взяв производную по γ, получим

И взяв производную по b,

Если мы рассматриваем {I} как набор положительных меток, а {J} - как набор отрицательных меток, мы можем переписать приведенное выше уравнение:

Уравнения (11) и (12) вместе с тем фактом, что все α имеют ≥0, подразумевают, что должен быть по крайней мере один ненулевой α_i в каждом из положительных и отрицательных классов. И поскольку α_i представляет, насколько «жестким» является ограничение, соответствующее i-й точке (где 0 означает, что оно совсем не жесткое), это означает, что должно быть не менее двух точек из каждого из двух классов с активными ограничениями. и, следовательно, с минимальным запасом (по точкам).

2.2 Что вообще означает «опорный вектор»?

В предыдущем разделе мы сформулировали лагранжиан для системы, заданной в уравнении (4), и взяли производную по γ. Теперь давайте сформируем лагранжиан для формулировки, задаваемой уравнением (10), поскольку это намного проще:

Взяв производную по w согласно 10-a и установив ноль, мы получим:

Как и раньше, каждая точка будет иметь ограничение неравенства, которому она соответствует, а также множитель Лагранжа α_i. Кроме того, кроме точек, которые имеют минимально возможное расстояние от разделяющей линии (для которых ограничения в уравнениях (4) или (7) активны), у всех остальных их α_i равны нулю (поскольку ограничения неактивны) .

Из уравнения (14) мы видим, что такие точки (для которых α_i’s = 0) не имеют вклада в лагранжиан и, следовательно, в w оптимальной прямой. Точно так же легко увидеть, что они также не влияют на b оптимальной линии. Таким образом, только точки, которые находятся ближе всего к линии (и, следовательно, их ограничения неравенства становятся равенствами), имеют значение при ее определении. Поэтому такие точки называют «опорными векторами». Как правило, их всего несколько, и все же они поддерживают разделяющую плоскость между ними.

3. Простейшая классификационная задача.

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

Совершенно ясно, что лучшее место для разделения этих двух точек - это фиолетовая линия, обозначенная следующим образом: x + y = 0.

Теперь давайте посмотрим, как математика, которую мы изучили до сих пор, сообщает нам то, что мы уже знаем об этой проблеме. Зачем это делать? Чтобы завтра он мог рассказать нам то, чего мы не знаем.

Поскольку t⁰ = 1 и t¹ = -1, из уравнения (12) получаем α_0 = α_1 = α. Подставляя это в уравнение (14) (которое является векторным уравнением), мы получаем w_0 = w_1 = 2 α. Отсюда сразу получаем, что прямая должна иметь равные коэффициенты для x и y. Мы также знаем, что, поскольку точек всего две, соответствующие им множители Лагранжа должны быть ›0, а соответствующие им ограничения-неравенства должны стать« жесткими »(равенства; см. Последнюю строку раздела 2.1). Это означает,

Вычитая два уравнения, получаем b = 0. Итак, разделяющая плоскость в данном случае - это линия: x + y = 0, как и ожидалось.

3.1. Добавление третьей плавающей запятой

Чтобы сделать задачу более интересной и охватить диапазон возможных типов поведения SVM, давайте добавим третью плавающую точку. Поскольку (1,1) и (-1, -1) лежат на прямой y-x = 0, пусть эта третья точка также лежит на этой прямой. Положим это в x = y = u. Кроме того, дадим этой точке положительный ярлык (точно так же, как зеленая (1,1) точка).

Теперь интуиция относительно опорных векторов подсказывает нам:

  1. Если u ›1, оптимальная линия SVM не изменится, так как опорные векторы по-прежнему (1,1) и (-1, -1).
  2. Если u∈ (-1,1), линия SVM движется вместе с u, поскольку опорный вектор теперь переключается с точки (1,1) на (u, u).
  3. Если u

Давайте посмотрим, как множители Лагранжа могут помочь нам прийти к такому же выводу. Из уравнения (14),

Кроме того, взяв производную уравнения (13) по b и установив ноль, мы получим:

И для нашей задачи это означает: α_0-α_1 + α_2 = 0 (поскольку первая и третья точки - (1,1) и (u, u) принадлежат положительному классу, а вторая точка - (-1, - 1) относится к отрицательному классу).

Далее, уравнения 10-b просто означают, что должны выполняться неравенства. Для нашей задачи мы получаем три неравенства (по одному на точку данных). Все указано в (согласно уравнению (7)):

для наших трех точек данных мы получаем:

Но из уравнения (15) мы знаем, что w_0 = w_1. Далее, вторая точка - единственная в отрицательном классе. Значит, соответствующее ему неравенство должно быть равенством. Используя это и вводя новые переменные резерва, k_0 и k_2, чтобы преобразовать вышеуказанные неравенства в равенства (квадраты гарантируют, что три неравенства выше по-прежнему ≥0):

И наконец, у нас есть условия дополнительности:

Из уравнения (17) получаем: b = 2w-1. Далее, поскольку нам нужны α_0 ›0 и α_2› 0, давайте заменим их на α_0² и α_2². Из уравнений (15) и (16) получаем:

Подставляя b = 2w-1 в первое из уравнения (17),

и в треть уравнения (17),

Теперь уравнения (18) - (21) трудно решить вручную. К счастью, существует общая структура для решения систем полиномиальных уравнений, называемая алгоритмом Бухбергера, а описанные выше уравнения в основном представляют собой систему полиномиальных уравнений. Я написал подробный блог об алгоритме Бухбергера для решения систем полиномиальных уравнений здесь. Его можно использовать для упрощения системы уравнений в терминах интересующих нас переменных (упрощенная форма называется базисом Грёбнера). И этот алгоритм реализован в библиотеке python sympy. Посмотрим, как это работает.

Порядок переменных в приведенном выше коде важен, поскольку он сообщает sympy об их «важности». Он пытается получить уравнения в конце базиса Грёбнера, выраженные через переменные из конца. В этом случае у нас было шесть переменных, но только пять уравнений. И поскольку k_0 и k_2 были двумя последними переменными, последнее уравнение базиса будет выражено только через них (если бы было шесть уравнений, последнее уравнение было бы только через k2). Мы получаем:

Это означает, что k_0 k_2 = 0 и поэтому хотя бы один из них должен быть равен нулю. Однако мы знаем, что оба они не могут быть равны нулю (в общем случае), поскольку это означало бы, что ограничения, соответствующие (1,1) и (u, u), жесткие; это означает, что они оба находятся на минимальном расстоянии от линии, что возможно только при u = 1. Тот факт, что один или другой должен быть равен 0, имеет смысл, поскольку ровно одно из (1,1) или (u, u) должно быть ближе всего к разделяющей линии, поэтому соответствующее k = 0.

Выполняя аналогичное упражнение, но с последним уравнением, выраженным через u и k_0, мы получаем:

Отсюда следует, что либо k_0 = 0, либо

Аналогично, извлекая уравнение через k_2 и u, мы получаем:

что, в свою очередь, означает, что либо k_2 = 0, либо

Это означает, что если u ›1, то мы должны иметь k_0 = 0, поскольку другая возможность сделает его мнимым. Следовательно, k_2 не может быть 0 и превратится в (u-1) ^. 5. Другими словами, уравнение, соответствующее (1,1), станет равенством, а уравнение, соответствующее (u, u), будет «проигрышным» (строгое неравенство). И это имеет смысл, поскольку если u ›1, точка (1,1) будет ближе к гиперплоскости.

И аналогично, если u ‹1, k_2 будет принудительно становиться 0 и, следовательно, k_0 будет вынуждено принять положительное значение. Мы видим две точки; (u, u) и (1,1) переключают роль опорного вектора при переходе u от меньшего чем к большему 1. Если u ‹0, с другой стороны, невозможно найти k_0 и k_2, которые как ненулевые, так и действительные числа, и, следовательно, уравнения не имеют реального решения.