1. Каково назначение метода опорных векторов?
Для SVM, используемых для классификации, при заданном наборе выборок, содержащем положительные и отрицательные примеры (положительные и отрицательные точки выборки), цель SVM состоит в том, чтобы найти гиперплоскость для сегментации выборок и разделения выборок Положительные и отрицательные примеры в разделены гиперплоскостью, а не просто,Принцип состоит в том, чтобы максимально увеличить интервал между положительными и отрицательными примерами.
Что такое гиперплоскость? Проще говоря, гиперплоскость — это обобщение прямой линии на плоскости в многомерном пространстве. Тогда для трехмерного пространства гиперплоскость — это плоскость. Для многомерных пространств мы можем использовать только формулы для выражения, но без интуитивной графики. Короче говоря, гиперплоскость в n-мерном пространстве является n-1-мерной.
Формула гиперплоскости. В формуле w — вектор регулируемых коэффициентов, а b — смещение. Обратите внимание на наши привычки выражения, все векторы являются векторами-столбцами, поэтому вектор w необходимо преобразовать в скалярное произведение первого члена.
Теперь рассмотрим выборку {xi,изi}, Иксiвходная функция, di— класс, соответствующий образцу. Теперь укажите, когда образец xiПри принадлежности к первой категории diравно 1, когда хiПри принадлежности ко второй категории diравно -1.
Тогда линейная разделимость означает, что гиперплоскость может полностью разделить два типа выборок. Формула:
Вы можете спросить сейчас, а что, если это не линейно разделимо? Дело в том, что этим займутся позже. Здесь мы сначала обсудим линейно сепарабельный случай, а затем распространим его на линейно несепарабельный случай.
Теперь предположим, что для линейно разделимого набора выборок у нас есть гиперплоскость разбиения, теперь мы хотим настроить w на0и б0Сохраняйте максимальное разделение между положительными и отрицательными образцами, которые он разделяет, чтобы мы получили оптимальную гиперплоскость. На самом деле в процессе эксплуатацииМы максимизируем расстояние от точки, ближайшей к гиперплоскости, до гиперплоскости.. То есть мы хотим держать гиперплоскость как можно дальше от ближайшей точки.Из рисунка видно, что расстояние от гиперплоскости до ближайшей точки положительного образца и расстояние от гиперплоскости до ближайшей точки отрицательного образца равны. Это совпадение?
Если предположить, что мы нашли гиперплоскость, расстояние от ближайшей точки к положительному образцу которой больше, чем расстояние до ближайшей точки к отрицательному образцу, то ближайшая точка к гиперплоскости является ближайшей точкой отрицательного образца. Учитывая наши цели, мы также корректируем положение гиперплоскости, чтобы сделать ее немного больше, даже за счет расстояния до ближайшей точки к положительному образцу. Следовательно, окончательный результат уравнивания должен заключаться в том, что расстояние между гиперплоскостью и ближайшими точками с обеих сторон равноудалено.
Чтобы более наглядно представить интервал между положительными и отрицательными выборками, мы можем определить две гиперплоскости H1 и H2 по обеим сторонам гиперплоскости сегментации (как показано пунктирными линиями на рисунке), которые проходят через положительные и отрицательные выборки соответственно. , Точки выборки, ближайшие к гиперплоскости сегментации (на рисунке добавлены внешние кружки). Из приведенного выше анализа можно узнать, что гиперплоскости H1 и H2 равноудалены от разделяющей гиперплоскости.
Определим точки над гиперплоскостями H1 и H2 как опорные векторы.Интервал между положительными и отрицательными выборками можно определить как интервал между гиперплоскостями H1 и H2, который представляет собой сумму расстояний между разделенной гиперплоскостью и ближайшей положительной точкой выборки и ближайшей отрицательной точкой выборки.
Как видно из рисунка, опорный вектор играет ключевую роль в положении гиперплоскости сегментации. После оптимизации положения гиперплоскости сегментации также выявляется опорный вектор, а точки выборки после опорного вектора не являются критическими для классификации. Почему ты так говоришь? Потому что даже если удалить все точки выборки, кроме опорного вектора, а затем найти оптимальную гиперплоскость сегментации, положение этой гиперплоскости будет таким же, как и у исходной гиперплоскости сегментации. Подвести итог:
Опорный вектор содержит всю информацию, необходимую для восстановления гиперплоскости сегментации!
2. Представление расстояния от точки выборки до гиперплоскости
Как найти расстояние от точки до гиперплоскости?
Теперь давайте посмотрим на вектор коэффициента W0Что это означает? помни, ж0на самом деле нормальный вектор гиперплоскости!
Тогда для любой точки выборки x это может быть выражено как:
где хp- проекция x на гиперплоскость, а r - геометрическое расстояние (геометрический интервал) x до гиперплоскости.
Предполагать,
теперь определяется G (xp) равно 0, то есть.
Теперь давайте посмотрим, g(x) на самом деле измеряет расстояние от точки отсчета x до гиперплоскости в ||w0Когда || постоянно, размер абсолютного значения g(x) отражает размер геометрического интервала r. Мы даем g(x) имя, называемое функциональным интервалом.Обратите внимание, что и геометрический интервал r, и функциональный интервал g(x) подписаны, представляя разные стороны гиперплоскости.
3. Максимизируйте интервалы
Мы уже знаем представление функции интервала и геометрического интервала, теперь вернемся к теме,Нам нужно максимизировать расстояние от опорного вектора до разделяющей гиперплоскости, конечно, мы не знаем, какие векторы являются опорными в начале.
Наша цель — максимизировать геометрический интервал r опорного вектора к разделяющей гиперплоскости, а не максимизировать функциональный интервал g(x), почему? Потому что коэффициенты уравнения гиперплоскости можно пропорционально увеличивать или уменьшать без изменения самой гиперплоскости. Итак, ||ш0|| не фиксируется, что влияет на размер интервала функции g(x).
Итак, нам нужно максимизировать геометрический интервал r, который эквивалентен нашему фиксированному ||w0||, то максимизируем интервал функции g(x). Но на практике мы этого не делаем, обычный подход состоит в том, чтобы зафиксировать абсолютное значение интервала функции g(x) равным 1, а затем минимизировать ||w0||.То есть мы устанавливаем абсолютное значение интервала функции g(x) от опорного вектора до разделяющей гиперплоскости равным 1, а затем минимизируем ||w0||.
4. Официальная презентация
Теперь мы можем формально сформулировать задачу. Нам нужно минимизировать ||w0||, который должен минимизировать весовой вектор гиперплоскости w0Евклидова норма . Но есть ли ограничения? Помните последнее предложение предыдущего раздела?
«То есть мы устанавливаем интервал функции g(x) от опорного вектора до разделяющей гиперплоскости равным 1, а затем минимизируем ||w0||”
Поэтому минимизируйте ||w0|| Есть ограничения, как выразить ограничения? Мы устанавливаем g(x), соответствующий опорному вектору, равным +1 или -1 (в зависимости от того, на какой стороне расщепленной гиперплоскости находится опорный вектор, то есть является ли это положительной выборкой или отрицательной выборкой), что означает что для всех положительных образцов для точки g(x) равно >=+1, а для отрицательных образцов g(x) равно
Напомним определение g(x):
,
Мы можем записать ограничения как:
Теперь мы можем записать приведенный выше вопрос более кратко:
Целевая функция:
лимит:
1/2 добавляется для удобства будущих расчетов, а N — количество точек выборки.
Теперь, когда наша первая задача решена, мы преобразуем задачу поиска оптимальной разделяющей гиперплоскости в задачу оптимизации с набором ограничений-неравенств. Эта задача оптимизации называется основной задачей. Мы не будем решать ее напрямую, а превратим в двойную задачу. Что касается того, как превратить это в двойственную проблему, то это содержание следующих нескольких разделов.
Ограничение равенства Минимальное условие оптимальности
Решение машины опорных векторов состоит в том, чтобы преобразовать исходную задачу, упомянутую в предыдущем разделе, в двойственную задачу для решения, и это содержание является содержанием курса оптимизации.
Напомним из предыдущего раздела, что наша цель — найти минимум функции при нескольких ограничениях.В исходной задаче предыдущего раздела ограничения содержат неравенства.В этом разделе мы сначала рассмотрим простую задачу, т. е.Рассмотрим задачу оптимизации, которая содержит только ограничения равенства:
(1)
где f(x) называется целевой функцией, а ниже приведен ряд ограничений равенства. Вспомните, как найти оптимум, когда ограничений нет? По фактуx*Необходимые условия для того, чтобы быть оптимальной точкой:
А если функция f(x) — выпуклая функция, это условие также является достаточным условием.
Вставьте утверждение, что если функция f(x) — вещественнозначная функция,x— n-мерный вектор, то f(x) к векторуxПроизводная определяется как:
Вернемся к текущей проблеме, когда мы ищем оптимальную точку, когда существуют ограничения, хотя наличие ограничений уменьшает область поиска, но усложняет задачу.Чтобы сделать проблему разрешимой, наш подход состоит в том, чтобы интегрировать целевую функцию и ограничения в новую функцию, функцию Лагранжа, а затем использовать эту функцию для поиска оптимальной точки.
Чтобы наглядно представить эту проблему, рассмотрим случай, когда целевая функция является функцией трех переменных и имеет только одно ограничение:
(2)
С геометрической точки зрения приведенная выше задача (2) с поверхностиподойти, чтобы найти функцию
минимальное значение . Предположим, что оптимальное решение задачи (2) есть
. Теперь сделаем любую проходную точку на поверхности ΩxГладкая кривая l:
(Поскольку кривая l лежит на поверхности Ω, естественно иметь
).
сделать лучший выводСоответствующее t есть t*. так какx*— оптимальная точка на поверхности Ω, поэтомуx*также является оптимальной точкой на кривой l, поэтому t*является унарной функцией
Оптимальная точка , поэтому ее производная равна 0 в этой точке. По цепному правилу получаем:
Эта формула показывает, что вx*это, функцияВектор градиента
и кривая l вx*Касательная в вертикальна. Поскольку кривая l произвольна, вектор градиента
перпендикулярна поверхности Ω.
Вспомним выводы высшей математики,Направление является нормальным направлением поверхности Ω, поэтому
и
должно быть в направлении той же прямой линии, поэтому должна быть постоянная μ*,имеют
.
Мы можем записать его в более утонченной форме. Если мы построим бинарную функцию, Из вышеприведенного выражения можно сделать вывод, что должно быть как постоянное μ*,сделать
.
Положим построенную функциюназывается функцией Лагранжа, а μ называется множителем Лагранжа.
Для введения функций Лагранжа только с ограничениями равенства вы также можете обратиться кВикипедияПример функции двух переменных в .
Вышеприведенный анализ представляет собой частный случай и содержит только одно ограничение. Тогда общий случай, связанный с ограничениями-равенствами, то есть задача (1), мы также можем построить функцию Лагранжа, но выражение немного отличается из-за включения нескольких ограничений-равенств:
.
Это,Каждое ограничение равенства соответствует множителю Лагранжа. Такx*Необходимым условием оптимальности точки является наличие соответствующего множителя Лагранжамю*, так что справедливы следующие две формулы:
(На самом деле ограничения исходной задачи (1) были записаны по-другому)
Эти два выражения являются необходимыми условиями оптимальной точки.Конечно, если функцияЕсли это выпуклая функция, эти два выражения также являются достаточными условиями.
Теперь наша цель достигнута, а именно объединить целевую функцию и ряд эквивалентных ограничений в одну функцию (функцию Лагранжа), так что нам нужно только решить два уравнения (3) и (4).Найти лучшее, преимущества очевидны. В следующем разделе мы обсудим задачи оптимизации, связанные с ограничениями неравенства.
Найдите нижнюю границу оптимального значения
Сначала мы вводим задачу оптимизации, включающую ограничения неравенства, стандартная форма которой выглядит следующим образом:
(1)
f(x) — целевая функция, за которой следует ряд ограничений в виде неравенства и ограничений в виде равенства соответственно.
Сначала определим несколько понятий:
Допустимые точки (возможные решения): все точки x, которые удовлетворяют ограничениям.
Возможная область: множество точек, состоящее из всех возможных точек, обозначаемое как R. Официально пишется так:
Оптимальная точка (оптимальное решение): точка, которая удовлетворяет ограничениям (то есть находится в допустимой области) и минимизирует целевую функцию, обозначаемую как x*.
Оптимальное значение: если x* найдено, p* = f(x*) является оптимальным значением.
После разъяснения этих понятий мы продолжим говорить о следующем содержании.
Как и в случае только с ограничениями равенства, упомянутыми в предыдущем разделе, мы определяем функцию Лагранжа следующим образом:
Давайте посмотрим, чем это отличается от функции Лагранжа в предыдущем разделе? Есть ряд членов, соответствующих ограничениям неравенства, поэтому есть также ряд множителей Лагранжа. Здесь следует подчеркнуть, что все λiДолжен быть больше или равен 0 (то есть множитель, соответствующий ограничению неравенства, требует больше или равно 0, мы записываем какλ≥0, что означает, что у каждого есть λi≥0). А зачем это нужно, естественно, будет видно позже.
Далее мы определяем важную функцию, мы определяемдвойная функция Лагранжаследующее:
(2)
Итак, двойственная функция Лагранжапросто поставь
Минимальное значение, найденное как функция x. Какой смысл искать этот минимум?
Сначала запишем заключение, которое очень важно и является целью этого раздела:
двойная функцияГенерируется нижняя граница оптимального значения p* исходной задачи (1), т. е. для любого λ ≥ 0 и любого µ имеются:
(3)
Итак, как доказать (3)?
Этот шаг доказательства очень прост. Предположим, что x* — оптимальное решение в исходной задаче (1), т. е. f(x*) = p*.
При выводе двух последних строк учитывается, что x* находится в допустимой области R, поэтому должно быть, при условии конечноλ≥ 0, поэтому это положение было сделано в начале.
Как понимать это неравенство (3)? Ниже приведены два интуитивных объяснения:
Объяснение 1: Объяснение линейной аппроксимации
Сначала перепишем задачу (1), которая должна выразить задачу (1) в более компактной форме, во-первых, определим индикативную функцию:
Мы также можем определить другую показательную функцию:
Теперь с помощью этих двух показательных функций мы можем переписать задачу (1) в форме без ограничений:
(4)
Посмотрим, эквивалентна ли эта оптимизационная задача (4) задаче (1)? Мы можем думать о последних двух членах (4) как о штрафной функции для x, нарушающего ограничения.Эффект состоит в том, чтобы наложить «бесконечный» штраф на x за нарушение ограничения неравенства, то есть один раз
, штраф равен бесконечности. и
Эффект состоит в том, чтобы наказать x за нарушение ограничений равенства, как только
, штраф бесконечен. Таким образом, оптимизация целевой функции в (4) аналогична оптимизации целевой функции в (1) при ограничениях, не так ли? То есть две задачи (1) и (4) эквивалентны, но в (4) ограничения включены в целевую функцию.
Теперь вернемся к (2), двойственной функции Лагранжа., это тоже задача оптимизации, мы сравниваем оптимизируемую им функцию с функцией, оптимизированной в (4), и перепишем их вместе:
(2) целевая функция
Целевая функция в (4)
Видно, что в задаче (2) и задаче (4) разница между оптимизируемыми целевыми функциями есть разница в штрафных членах. Штрафной член в (4) бесконечен, т. е. при нарушении ограничения налагается бесконечный штраф, а в (2) наш штрафной член является линейным, т. е. как gi(х) и чiВ отличие от (x), срок штрафа изменяется линейно. Таким образом, целевые функции, подлежащие оптимизации в (2) и (4), сильно различаются, и использовать (2) для аппроксимации (4) очень неточно. Но мы можем видеть, что для любого u, любогоλ≥0 и любоймюДля всех:
(Мы ограничиваем λ большим или равным 0)
Таким образом, в любой момент значение целевой функции в (2) меньше значения целевой функции в (4), поэтому оптимальное значение, найденное в (2), должно быть меньше, чем оптимальное значение, найденное в (4) . . . Объединение упомянутых выше (1) и (4) является эквивалентной задачей, поэтому неравенство (3) установлено.
Объяснение 2: поменяйте местами максимальный и минимальный порядок
Сначала мы можем увидеть, что:
Почему такой результат? Когда x удовлетворяет ограничению, то есть для всех i, мы имееми
, если мы хотим настроитьλимюпозволять
Как стать больше? только пустьλВсе 0 (примечаниеλможет быть только больше или равно 0), что исключает элементы меньше 0, как для
,несмотря ни на чтомюНеважно, как вы его измените. Таким образом, результатом приведенной выше формулы является f (x), когда x принадлежит допустимой области. Что делать, если x нарушает ограничение? При выполнении операции sup вам нужно только удовлетворить
и
Множитель, соответствующий термину, устанавливается равным +∞, а множитель, соответствующий другим терминам, устанавливается равным 0, так что результат всей формулы становится бесконечным.
Итак, мы видим, что задача условной оптимизации в задаче (1) и прямая оптимизациято же самое, то есть:
Теперь мы поменяем порядок двух операторов inf и sup, очевидно:
Перепишем уравнение (2):
(2)
Можно сделать вывод, чтоλПри ≥ 0 справедлива формула (3):
(3)
Ну а спустя долгое время мы объяснили проблему, то есть откуда берется неравенство (3).
Подводя итог, неравенство (3) формулируется словами так:
Если мы рассмотрим функцию Лагранжа как функцию от x, а затем возьмем оценку иммума (примечание: оценка иммума берется во всей области определения, а не только в допустимой области, т. е. возьмем оценку иммума). не является ограничением на x в оценке), то полученный результат является нижней границей оптимального значения исходной задачи оптимизации (1).
Что же касается использования этого результата, то об этом мы поговорим в следующем разделе.
Вспомним из предыдущего раздела, к следующему исходному вопросу:
(1)
Определим двойственную функцию Лагранжа:
Затем мы доказали:, где p* — оптимальное значение исходной задачи.
То есть мы нашли нижнюю границу оптимального значения исходной задачи.. Теперь, когда мы нашли Нижний мир, очевидно, мы собираемся найти его лучший Нижний мир. Что такое лучший Нетер? Очевидно, самое большое из всех низших миров. Так что мы будемМаксимизируйте, конечно, мы должны помнить, что нам нужно ограничить
. Мы формально записываем функции и ограничения, которые необходимо оптимизировать, как:
(2)
В соответствии с исходной задачей (1) мы называем указанную выше задачу (2) двойственной задачей Лагранжа.Очевидно, оптимальное значение d* двойственной задачи — это оптимальная нижняя граница p*, которую мы можем получить, то есть самая близкая к p* среди всех нижних оценок, и их соотношение таково:
(3)
Назовем это неравенствоСлабая двойственность.
Плывя по течению, мы можем ввести важное понятие, разрыв дуальности, который определяется как, которая представляет собой разницу между оптимальным значением исходной задачи и ее наилучшей (максимальной) нижней оценкой, полученной путем вытягивания двойственной функции Лангри. Из неравенства (3) видно, что двойной зазор должен быть больше или равен 0.
Так возможно ли, что при каких-то обстоятельствах разрыв дуальности исчезает? То есть оптимальное значение двойственной задачи равно оптимальному значению исходной задачи?
Мы собираемся описать условие Слейтера:
Состояние Слейтера:
Существует x такой, что:
Условие Следитена означает, что есть х, так что «меньше или равный знак» в ограничении неравенства должен быть строго взяты как «меньше, чем знак».
Можно показать, что для выпуклой оптимизации задач (для проблем выпуклой оптимизации, пожалуйста, обратитесь кВикипедия), если выполняется условие Слейтера, то:
Эта ситуация называетсяСильная двойственность.
Следующий вопрос: какое интересное явление произойдет, если разрыв дуальности исчезнет?
Если разрыв двойственности исчезнет, т.е. если будет оптимальная точка для задачи двойственностиλ*,мк*и сделать соответствующее ему оптимальное значениеравно p*, что тогда происходит? Помните, в предыдущем разделе мы доказали, что
Является ли процесс:
(4)
В случае, когда разрыв двойственности исчезает, все неравенства в середине становятся равными:
(5)
Обратите внимание, что в (5)λимюОба отмечены звездочкой, чтобы указать, что они являются оптимальными точками двойственной задачи. В (5) есть два важных знака равенства, которые отмечены.
Какой вывод мы можем сделать?
1. Давайте сначала посмотрим на знак равенства 1:
Это объясняет лучшую точку x * исходной задачи.Точка, в которой достигается минимальное значение.
2. Давайте снова посмотрим на знак равенства 2:
Здесь утверждается:
Поскольку мы ограничиваем каждое λi≥ 0, поэтому каждый член в приведенной выше формуле неположителен. Итак, мы можем сделать вывод:
(6)
Уравнение (6) называетсяусловие дополнительности, можно записать иначе:
Или запишите его эквивалентную форму (обратное отрицание предложения):
То есть, пока один не равен 0, другой должен быть равен 0!
Условия дополнительности имеют важные последствия. Это показывает, когда, x* находится внутри допустимой области, и ограничение неравенства не работает, то
;и
Точка заведомо является точкой границы допустимой области (
). Другими словами, только положительные ограничения имеют двойные переменные, отличные от 0. И это имеет большое значение в машинах опорных векторов. Вспоминая наш окончательный вывод в разделе 1, SVM, находящий гиперплоскость с максимальным запасом, можно свести к задаче оптимизации:
Целевая функция:
лимит:
Итак, какие ограничения неравенства соответствуют двойственным переменным, которые не равны нулю? Очевидно, только когдаКогда двойственная переменная, соответствующая этому ограничению, может быть не равна 0, и
Что это означает? означает точку выборки x, соответствующую этому ограничениюiявляется опорным вектором! Это:
Только опорные векторы соответствуют ненулевым множителям Лагранжа!