[БЕЗ_ЗВУКА] Давайте познакомимся поближе с еще одним методом, который не вошел в основную часть курса, а именно с методом опорных векторов. Конечно, в каком-то виде вы с ним уже знакомы. Это просто линейный классификатор, использующий кусочно-линейную функцию потерь и L2-регуляризатор. Но на самом деле метод был придуман не из общего вида линейных классификаторов и не из обобщения с функциями потерь и регуляризаторами. Он был придуман из других довольно простых соображений. Давайте представим себе линейно разделимую выборку, то есть выборку, которую можно разделить на 2 класса (мы будем рассматривать случай бинарной классификации) с помощью гиперплоскости. Понятно, что эту гиперплоскость можно провести по-разному. И можно провести ее так, что она разделит выборку, и при этом могут быть небольшие изменения в коэффициентах плоскости, и она продолжит разделять выборку. Возникает вопрос: каким же образом ее провести так, чтобы это было более-менее оптимально? Естественная мысль — рассмотреть разделяющую полосу, ну то есть конструкцию, которая получается, если гиперплоскость подвинуть максимально к одному классу и максимально к другому классу. Тогда можно задуматься вот о чем: какие значения будет принимать скалярное произведение вектора весов w на x минус коэффициент сдвига в тех точках, которые относятся к одному классу и к другому классу и через которые проходят границы разделяющей полосы. Ну то есть получается, это самые крайние точки каждого из классов. Дело в том, что если мы возьмем и умножим вектор w и коэффициент w0 на какое-то число, то разделяющая поверхность совершенно не поменяется. В самом деле, мы как смотрели на знак некоторого выражения, так и будем смотреть — просто выражение будет умножено на константу. Тогда мы можем потребовать, чтобы значение вот этой функции (скалярное произведение w на x минус w0) на крайних объектах по модулю было равно 1. Ну то есть, для класса +1 было равно 1, а для класса −1 было равно −1. Ну это означает, что если мы просто домножим на yi-тое, то тогда значение будет просто 1. Итак, потребовав такой нормировки, мы можем подсчитать ширину разделяющей полосы. Для этого нам нужно просто взять направление, задающее нормаль к разделяющей поверхности, то есть w, и посмотреть проекцию вектора разности крайних элементов каждого класса на это направление. Найти проекцию совсем несложно, нужно просто взять скалярное произведение разностей x с плюсом и x с минусом на вектор w, отнормированный на свою длину. Ну давайте распишем это скалярное произведение. Тогда в числителе мы получим разность скалярных произведений вектора w на x с плюсом и вектора w на x с минусом. Но в то же время мы знаем, что для этих крайних объектов выполнено некоторое соотношение, получающееся из нормировки. Воспользуемся им и тогда получим в числителе (w0 + 1) и (w0 − 1). В итоге ширина разделяющей полосы получается 2 делить на длину вектора w. Что это значит? Ну это значит, что теперь мы можем записать задачу, которая будет описывать максимизацию ширины разделяющей полосы. Давайте минимизировать скалярное произведение вектора w на себя (как мы знаем, его длина — это просто корень из этой величины) при условии, что отступ на этом объекте должен быть больше либо равен 1. Это наше ограничение, которое обеспечивает значение отступа 1 на крайних объектах класса. Теперь нам нужно рассмотреть случай линейно неразделимой выборки. Действительно, если до этого мы могли потребовать, чтобы отступ был больше либо равен 1, а 1 — это положительная величина (а отступ положителен тогда, когда классификация верная), то теперь, в случае линейно неразделимой выборки, у нас в любом случае будут объекты, которые неверно отнесены к классу нашим классификатором. Это означает, что мы должны позволить нашему алгоритму ошибаться, то есть позволить допускать отступ, который будет не больше либо равен 1, ну а, например, больше либо равен (1 − ξi). ξi-тое будет ошибкой на i-том объекте. Но тогда нам нужно добавить в минимизируемую функцию штрафы за эти ошибки. Ведь если мы их не добавим, то можно будет делать классификатор с любым произвольным отступом. Итак, добавить ошибки можно очень просто. Просто давайте напишем к исходному функционалу плюс константа умножить на сумму этих ошибок. Также обратите внимание: у нас появилась 1/2 перед скалярным произведением вектора w на себя, ну это просто из соображений удобства для дифференцирования. По сути, это ни на что не влияет. Смотрите, как у нас изменилась наша оптимизационная задача. Теперь у нас есть и переменные w, и переменные ξ. При этом на переменной ξ есть два условия. Одно ограничивает снизу отступ, а другое условие — это то, что ξi больше либо равны нулю. Ну действительно, зачем нам ошибки, которые будут отрицательны? Это просто означает, что где-то мы смогли сделать отступ положительным, но это и так все будет нормально получаться, даже если мы возьмем неотрицательные ξi-тые. Ну и теперь мы получили оптимизационную задачу для метода опорных векторов, ну или, проще говоря, SVM. Возникает вопрос: при чем же здесь линейный классификатор в привычном нам виде? Давайте посмотрим на эту задачу внимательнее. Действительно, мы хотим минимизировать сумму ξi-тых, при том, что ξi-тые должны быть больше либо равны 0 и больше либо равны единице минус отступ. Что это означает? Это означает, что ξi-тое будет уж во всяком случае больше либо равно максимума из двух величин (0 и единица минус отступ), и, с другой стороны, так как сумма ξi-тых минимизируется, то ξi-тая будет в точности равна этой величине, то есть максимуму из 0 и (1 − Mi). В таком случае мы можем просто подставить эти ξi-тые в нашу оптимизационную задачу, ну а именно в первое выражение. И тогда мы получим безусловную оптимизационную задачу в SVM, то есть задачу оптимизации без дополнительных условий. Смотрите, здесь уже четко прослеживается и функция потерь (она кусочно-линейная или, как говорят в англоязычной литературе, hinge loss), и регуляризатор — обычный L2-регуляризатор. Итак, метод опорных веторов — это просто линейный классификатор с кусочно-линейной функцией потерь и L2-регуляризатором. Придуман метод был из соображений максимизации зазора между классами. В случае линейно разделимой выборки это означает просто максимизацию ширины разделяющей полосы. А в случае линейно неразделимой выборки просто добавляется возможность попадания объектов в полосу и штрафы за эти попадания.