Опорные векторы: никогда не было так многим в долгу перед столь немногими

1. Проблема

Машины опорных векторов поставили перед собой задачу решить проблему «классификации». Если нам даны какие-то данные, они будут состоять из определенного количества записей / строк / точек. Теперь мы хотим разделить каждую из этих точек на несколько классов, которые мы имеем в виду. Для простоты мы предполагаем, что нас интересуют только два класса: «положительный» и «отрицательный». Примеры важных вопросов (на некоторые из них больше, чем на другие), на которые это может помочь:

  1. Погода или нет, на фотографии есть кошка (на которой кошка означает положительную метку) с учетом данных пикселей.
  2. Независимо от того, является ли электронное письмо спамом, учитывая его тему, отправителя, текст и т. Д.
  3. Определение наличия у пациента определенного заболевания.

Идея состоит в том, что мы придумываем какое-то правило для разделения данных на два класса, когда мы уже знаем правильные ответы (для SVM это правило состоит в том, чтобы рисовать плоскость и вызывать все точки с одной стороны положительными, а с другой. , отрицательный). Затем, когда мы сталкиваемся с новой точкой данных, ответ на которую мы не знаем, мы используем то же правило, которое мы (или наша машина) выучили, чтобы ее классифицировать. Эта тема в значительной степени опирается на теорию ограниченной оптимизации, о которой я писал в блоге некоторое время назад, и является прекрасным иллюстративным примером. Кроме того, мы будем ориентироваться на статью Эндрю Нг.

1.1. В картинках

Мне кажется, что я ничего не понимаю, пока не нарисую картинку. Также всем нравятся картинки. Итак, давайте посмотрим на некоторые.

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

Теперь, если я нарисовал фиолетовую линию, разделяющую два класса, станет намного яснее, к какому классу должна принадлежать каждая из желтых точек (все, что находится выше линии, является зеленым, а все, что ниже - красным).

Однако приведенная выше строка не уникальна. Есть несколько фиолетовых линий, которые идеально разделяют зеленую и красную точки. Некоторые из них показаны на рисунке ниже. Когда мы переключаемся между этими линиями, последствия для некоторых желтых точек становятся серьезными (они оказываются по разные стороны линии и, следовательно, меняют свои метки в зависимости от выбора линии).

Итак, из всех линий кандидатов вопрос в том, какая из них «лучшая»? Одна вещь, которую ясно видно на рисунке 3 выше, заключается в том, что когда фиолетовая линия приближается к красной точке в правом нижнем углу, не похоже, что она хорошо обобщается, в то время как когда она остается далеко от этой точки , это похоже на лучшую разделительную линию. Итак, похоже, что один момент диктует, насколько хороша линия, делая ее «критической». Можно сказать, что линии, которые держатся подальше от этой красной точки, находятся как можно дальше от всех обучающих примеров, в то время как те, которые приближаются излишне близко к ней, в конечном итоге выглядят не так хорошо, как классификаторы. Итак, строки, которые в конечном итоге отталкивают даже самые близкие обучающие образцы далеко от самих себя, являются хорошими классификаторами. Мы конкретизируем эту идею в разделе 3. Но сначала давайте научимся рисовать линии с помощью математики.

2. Рисование линий

Итак, мы хотим провести разделяющую (или просто общую) линию (в двумерном пространстве; это будет гиперплоскость в пространстве более высоких измерений). Итак, что такое линия? Это бесконечный набор точек, у которых есть что-то общее. Все они удовлетворяют определенному уравнению. Чтобы найти это уравнение, давайте начнем с простейшей линии - оси абсцисс. Что общего в векторах положения всех точек на нем? Все они выглядят так: v_x = [x, 0], что означает, что у них нулевые координаты y.

Другими словами, вектор положения каждой точки на ней ортогонален (перпендикулярен) вектору, указывающему в направлении оси y.

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

При изменении линии вектор, который оказывается перпендикулярным к ней, также изменяется, но тот факт, что вектор положения каждой точки на линии перпендикулярен некоторому вектору, является инвариантом, который сохраняется для всех линий. . Назовем этот вектор w для некоторой общей прямой, проходящей через начало координат. При изменении w мы захватим все такие строки.

Обратите внимание, что для каждой строки также существует несколько значений w. По сути, если мы увеличим или уменьшим масштаб на любое число, тот факт, что векторы положения каждой точки на линии перпендикулярны ей, не изменится.

Так почему бы не ограничиться только векторами w с величиной 1? С этого момента давайте просто будем считать, что всякий раз, когда мы говорим о векторе с именем w, предполагается, что он имеет величину 1.

Итак, теперь мы успешно параметризовали все линии, проходящие через начало координат. А как насчет тех, которые этого не делают? Мы можем получить такую ​​линию, переместив одну из линий, прошедших через начало координат, на некоторую величину, b, в направлении w, вектора нормали к линии. Теперь скалярное произведение w с любым вектором положения точки на линии не равно нулю. Но он по-прежнему остается постоянным, b. Это видно из рисунка 6 ниже. Вектор w - это единичный вектор, направленный от начала координат к линии (фиолетовой) и перпендикулярной ей. A - это точка на прямой, ближайшая к началу координат. Допустим, расстояние OA равно -b. Теперь рассмотрим две случайные точки B и C (зеленого и оранжевого цвета). Если вы возьмете скалярное произведение OB или OC с единичным вектором w, вы получите основание треугольников OAB и OAC соответственно. И в обоих случаях это просто OA, то есть -b. Поскольку эти две точки были произвольными на линии, мы можем заключить, что все точки на прямой будут удовлетворять условию w ^ T x + b = 0 (где x - вектор положения точки - OB и OC для двух приведенных выше примеров).

Что происходит, когда мы подставляем точку, которая не лежит на линии, в уравнение линии, полученное нами выше? Конечно, мы получаем число, которое не равно нулю, но это также перпендикулярное расстояние от точки до линии (поэтому для точек на линии это ноль, как и ожидалось). Важно отметить, что этот вывод верен, только если | w | = 1, как мы и требовали. Рисунок ниже должен прояснить этот результат. Возьмем произвольную точку, B не на прямой. Затем мы опускаем перпендикуляры из точки B на фиолетовую линию B ’’ и линию, представляющую вектор w, B ’. Расстояние по перпендикуляру от B до линии указано BB ’’ на рисунке. Но поскольку A-B’-B-B ’’ образуют прямоугольник, это расстояние равно AB ’= OB’-OA. Теперь OB ’- это просто скалярное произведение вектора положения B (OB) на w. Итак, если x - вектор положения B, то | OB ’| = ш ^ Т х. Это означает | AB ’| = w ^ T x - (- b) (напомним, что OA = -b). Таким образом, перпендикулярное расстояние от точки до линии становится: | AB ’| = w ^ T x + b, что является уравнением прямой.

Обратите внимание, что все точки на той стороне линии, к которой указывает w (например, точка B на рисунке 7), получают положительное перпендикулярное расстояние при подключении, в то время как точки на другой стороне получают отрицательное перпендикулярное расстояние. .

Но тогда все точки, лежащие на той стороне, где w точек, имеют положительную метку (t_i = 1), а те, что на другой стороне, имеют отрицательную метку (t_i = -1 ). Итак, если мы умножим метки на перпендикулярные расстояния, скорректированные перпендикулярные расстояния станут положительными для всех точек, пока эти точки правильно классифицируются линией (то есть точки с положительными метками лежат на одной стороне, а точки с отрицательными метками на Другие).

3. Оптимальная линия

Теперь наступает изюминка для SVM. Назовем скорректированное перпендикулярное расстояние от любой точки до линии границей этой точки. Любая заданная линия будет иметь некоторые поля для всех точек (эти поля будут положительными, если точка правильно классифицирована по линии, в противном случае - отрицательными). Нам нужны линии, которые хорошо отделяют позитивное от негативного. Другими словами, поля должны быть как можно больше, даже для точек, ближайших к границе (разделяющей плоскости). Это соответствует идее, которую мы обсуждали в конце раздела 1.1.

Итак, самолеты, которые максимизируют даже худшую маржу, должны хорошо справляться с разделением точек. Теперь, учитывая комбинацию (w, b), запас для i-й точки будет равен (x_i - вектор положения в пространстве признаков и t_i - метка: 1 для положительного и -1 для отрицательного):

И минимальная маржа по всем пунктам становится:

Нам нужна пара (w, b), которая максимизирует эту минимальную маржу. Другими словами, мы хотим:

Другими словами, нам нужна пара (w, b), которая удовлетворяет | w | = 1 и максимизирует маржу:

Обратите внимание: если линия не разделяет данные, то для этой комбинации (w, b) термин:

будет отрицательным для некоторых точек. И одна из этих точек выиграет при первой минимизации. Это будет означать, что эти (w, b) комбинации никогда не смогут «выиграть» во втором максимальном аргументе. Таким образом, это гарантирует, что выигрышная (w, b) комбинация всегда будет разделять данные, если данные разделимы.

Уравнение (2) - это задача оптимизации, которая включает в себя минимизацию, а затем максимизацию (мини-максимум). Намного проще решать задачи, предполагающие оптимизацию всего одного уровня вместо двух. Итак, давайте попробуем преобразовать это в задачу ограниченной оптимизации.

Вернемся к обозначению минимального запаса по всем точкам как γ.

Окончательная проблема оптимизации становится такой:

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

А теперь давайте посмотрим, сможем ли мы его еще больше упростить. Оказывается, есть способ избавиться от γ. За это придется заплатить - нам придется отказаться от требования, чтобы w ^ T w = 1. Но с учетом упрощения это того стоит. Давайте разделим на него ограничения с обеих сторон. Мы получаем:

Теперь установите:

Взяв модуль с обеих сторон,

Но мы требовали, чтобы | w | = 1. Это означает:

Кроме того, уравнение (3) теперь принимает следующий вид:

Уравнения (5) и (6) составляют задачу оптимизации в уравнении (4):

Пока что задача оптимизации имеет некрасивую целевую функцию. Но максимизировать 1 / | w | - это то же самое, что минимизировать | w |, что то же самое, что минимизировать | w | ². А добавление 1/2 облегчит жизнь в будущем.

Итак, мы можем переформулировать это как:

Теперь это задача оптимизации с квадратичной целевой функцией и линейными ограничениями (квадратичная программа с линейными ограничениями или LCQP). Ее можно решить с помощью решателей квадратичного программирования, доступных на разных языках.

Теперь мы знаем, как найти оптимальную линию с помощью решения задачи оптимизации. Если заглянуть под поверхность в реальную механику решения таких задач оптимизации (с помощью множителей Лагранжа), это даст нам четкое понимание и интуитивное понимание проблемы. Следите за обновлениями части 2 (я опубликую здесь ссылку, когда она будет готова), где мы делаем именно это, а также проходим процесс для некоторых игрушечных примеров.