Заметки о машинном обучении Python (7): Мягкий интервал машин опорных векторов

Это 3-й день моего участия в августовском испытании обновлений, подробности о событии:Испытание августовского обновления

7.1 Исходная проблема

Есть примерно два случая линейной неразделимости: только ребра линейно неразделимы (слева) и большинство выборок линейно неразделимы (справа). Для левого случая используеммягкий интервалметод решения.

75}}MB(_ZIWPDU%VT7HPTD.png

Давайте сначала рассмотрим шаги для поиска гиперплоскости классификации с использованием жестких полей:

Предположим, что функция гиперплоскости: $w^Tx+b=0$
Учитывая ограничения: $y_i(w^Tx_i+b) \ge 1$ (Указывает, что гиперплоскость может правильно классифицировать все образцы)
зум $w$ и $b$ Пусть опорный вектор $x_i$ удовлетворить $y_i(w^Tx_i+b)=1$ .
Вычислить сумму расстояний от неоднородных опорных векторов до гиперплоскости $\frac {2}{||w||}$ То есть жесткий интервал, нахождение гиперплоскости, которая делает ее наименьшей (чтобы гарантировать, что найденная гиперплоскость уникальна), является конечной требуемой гиперплоскостью классификации.

На шаге 2 мы обнаружили, что гиперплоскость, удовлетворяющая ограничениям, не существует. В этом случае лучше согласиться на следующий лучший выбор. Также хорошим выбором является поиск гиперплоскости, которая может правильно классифицировать большинство выборок. В конце концов, поиск идеальной гиперплоскости — это не обязательно проблема алгоритма, но также может быть проблемой шума самих данных.

Таким образом, мы ослабляем ограничение на $y_i(w^Tx_i+b) \ge 1-\delta_i$ , $\delta_i$ называетсярезервная переменная. После добавления переменной slack наш интервал выглядит следующим образом:

屏幕截图 2021-08-06 203950.png

Промежуток между двумя пунктирными линиями называетсямягкий интервал. Опорные векторы в это время являются векторами на границе интервала и внутри нее. каждый образец $x_i$ имеет соответствующую переменную резерва $\delta_i \ge 0$ , который представляет допуск гиперплоскости для неправильной классификации выборки. Например, для точки выборки $x_i$ , соответствующая категория $y_i=+1$ , результат классификации гиперплоскости $w^Tx_i+b=-5$ , явно неправильно классифицирован. но если $\delta_i=7$ Так $y_i(w^Tx_i+b) = -5 \gt 1-\delta_i=-6$ , мы можем принять эту гиперплоскость в качестве гиперплоскости классификации, даже если она неправильно классифицирует точку выборки.

Но наша терпимость ограничена, и мы должны $\delta_i$ Размер ограничен, иначе точность классификации будет слишком низкой. Хотя добиться 100% точности классификации невозможно, мы все же надеемся сделать классификацию гиперплоскости максимально точной, то есть дать гиперплоскости как можно меньше допусков:

min \sum^{m}_{i =1}\delta_i

Сочетание этого с проблемой с жесткими интервалами дает основную проблему с мягкими интервалами:

\begin{cases} min \frac {||w||^2}{2}+C\sum^{m}_{i =1}\delta_i\\ s.t.{\quad} 1-\delta_i-y_i(w^Tx_i+b) \le 0{\quad}i=1..m\\ s.t.{\quad} -\delta_i \le 0 \end{cases}

Уведомление $||w||^2$ и $\delta_i$ Связь в том, что одно увеличивается, а другое уменьшается, и взять минимум одновременно нельзя, поэтому здесь нужно контролировать пропорцию двух, которая является гиперпараметром $C$ эффект. когда $C$ Когда значение больше $\sum^{m}_{i =1}\delta_i$ Сделать его меньше $||w||^2$ Важно быть меньше, а это значит, что у нас более низкая терпимость к ошибкам классификации, и нам нужно уменьшить мягкий интервал (уменьшить способность к обобщению), чтобы повысить точность классификации. Наоборот, это означает, что мы имеем высокую устойчивость к ошибкам классификации и жертвуем точностью классификации, чтобы увеличить мягкую маржу.

7.2 Двойственная проблема

Можно видеть, что задача по-прежнему удовлетворяет сильной теореме двойственности, которая очень похожа на задачу о жестких интервалах, за исключением того, что ограничения и параметры увеличены. Уведомление $C$ — это гиперпараметры, которые мы определяем перед обучением, а не переменные. $\delta_i$ и $w$ и $b$ Это та же самая переменная, которую мы хотим минимизировать. Соответствующая функция:

\begin{aligned} L(w,b,\delta,\alpha,\beta) &= \frac {||w||^2}{2} +C\sum^{m}_{i =1}\delta_i+\sum^{m}_{i =1}{\alpha_i (1-\delta_i- y_i(w^Tx+b))} -\sum^{m}_{j =1}\beta_j\delta_j\\ \theta(\alpha,\beta) &= min_{w,b,\delta}L(w,b,\delta,\alpha,\beta) \end{aligned}

Двойная проблема:

\begin{case} max_{\alpha,\beta}\theta(\alpha,\beta)\\ st{\quad}\alpha_i \ge 0{\quad}i=1...m\\ st{\ quad}\beta_i \ge 0{\quad}i=1...m \end{cases}

сделать $L$ правильно $w,b,\delta_i$ Частная производная равна 0:

\begin{aligned} \frac{\partial L}{\partial w}&=w-\sum^{m}_{i =1}\alpha_iy_ix_i=0\\ \frac{\partial L}{\partial b}&=-\sum^{m}_{i =1}\alpha_iy_i=0\\ \frac{\partial L}{\partial \delta_i}&=C -\alpha_i-\beta_i =0\\ \end{aligned}

заменять $\theta(\alpha,\beta)$ Задний $\beta$ устранено, чтобы получить:

\theta(\alpha) = \sum^{m}_{i =1}\alpha_i - \frac{1}{2}\sum^{m}_{i =1}\sum^{m}_{j =1}\alpha_i\alpha_jy_iy_jx_i^Tx_j

В сочетании с условием kkt мы получаем последнюю задачу, которую хотим решить:

\begin{cases} max_\alpha (\sum^{m}_{i =1}\alpha_i - \frac{1}{2}\sum^{m}_{i =1}\sum^{m}_{j =1}\alpha_i\alpha_jy_iy_jx_i^Tx_j)\\ s.t.{\quad}\sum^{m}_{i =1}\alpha_iy_i=0\\ s.t.{\quad}0\le \alpha_i \le C,\beta_i \ge 0\\ s.t.{\quad}\alpha_i(y_i(w^Tx_i+b)-1+\delta_i)=0,{\quad}\beta_i\delta_i=0\\ s.t.{\quad}y_i(w^Tx_i+b)-1+\delta_i \ge 0\\ s.t.{\quad}\delta_i \ge 0\\ \end{cases}

Обратите внимание, потому что $C -\alpha_i-\beta_i =0$ и $\beta_i \ge 0$ так $0\le \alpha_i \le C$ .

Зависит от $\alpha_i(y_i(w^Tx_i+b)-1+\delta_i)=0$ Видно, что выбор гиперплоскости по-прежнему связан только с опорным вектором, а двойственная задача по-прежнему является задачей квадратичного программирования, и ее решение несложно.

использованная литература

«Машинное обучение», Чжоу Чжихуа, издательство Университета Цинхуа

«Подробное объяснение формул машинного обучения», авторы Се Вэньруй, Цинь Чжоу, издательство People's Posts and Tele Communications Publishing House

Курс машинного обучения преподавателя Ху Хаоджи из Чжэцзянского университета в МООК