Эндрю Нг Машинное обучение: машины опорных векторов

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

В этих заметках к курсу объясняются основные идеи SVM, начиная сКлассификатор максимального интерваланачни, потом пройдиДвойственность Лагранжаполучить исходный вопросдвойственностьпроблема, чтобы мы могли применитьтрюк с ядром, решать многомерные задачи эффективным способом.

нажмитеВидео курсаВы сможете изучать курсы Нг без перерыва, код Python для курсовой работы выложен на Github, нажмитекод курсаВы можете перейти на Github для просмотра (если у вас нет доступа к Github, вы можете нажатьCodingПроверьте ), ошибки и улучшения в коде приветствуются.

Вот заметки с 6-й недели курса машинного обучения Нг.

Классификатор максимального интервала

учитыватьлогистическая регрессияизфункция предсказаниячас θ ( Икс ) знак равно г ( θ Т Икс )" роль="презентация"> $h_\theta(x)=g(\theta^Tx)$ . когда θ Т Икс ≫ 0" роль="презентация"> $\theta^Tx\gg0$ или θ Т Икс ≪ 0" роль="презентация"> $\theta^Tx\ll0$ , вы можете быть совершенно увереныфункция предсказанияклассификации, поскольку час θ ( Икс )" роль="презентация"> $h_\theta(x)$ близко к 1 и 0. Интуитивное выражение состоит в том, что чем дальше образецграница решения, тем увереннее он в своей классификации. Поэтому естественно думать, что если их несколькограница решениявыбирать между, мы выберем тот, который находится дальше от всех выборок (рассмотрим линейный случай ).
[分类问题]
Чтобы получить такую границу решения, мы сначала посмотрим, как сформулировать эту проблему математически. через несколько простыхвычислительная геометриязнания могут быть рассчитаны для каждой выборки, чтобыграница решениярасстояние(geometric margin), γ ( я ) "роль="презентация"> $\gamma^{(i)}$ . Для облегчения последующего вывода необходимо также определитьfunctional margin, γ ^ ( я ) "роль="презентация"> $\hat{\gamma}^{(i)}$ .

γ ^ ( я ) знак равно у ( я ) ( ж Т Икс ( я ) + б ) γ ( я ) знак равно у ( я ) ( ( ж | | ж | | ) Т Икс ( я ) + б | | ж | | ) " role="презентация">^γ(i)=y(i)(wTx(i)+b)γ(i)=y(i)((w||w||)Tx(i)+b| |w||)γ^(i)=y(i)(wTx(i)+b)γ(i)=y(i)((w||w||)Tx(i)+b||w ||)

В следующихSVMВ разговоре у ( я ) "роль="презентация"> $y^{(i)}$ значение { 1 , − 1 }" роль="презентация"> $\{1,-1\}$ (указывает, какая сторона границы решения находится на, и делает все вычисления расстояния положительными), когда θ Т Икс ≥ 0" роль="презентация"> $\theta^Tx\ge0$ время взять 1" роль="презентация">, θ Т Икс $\theta^Tx<0$ время взять − 1" роль="презентация">. также необходимо определить γ ^ "роль="презентация"> $\hat{\gamma}$ для всех γ ^ ( я ) "роль="презентация"> $\hat{\gamma}^{(i)}$ наименьшее значение в γ" роль="презентация"> $\gamma$ для всех γ ( я ) "роль="презентация"> $\gamma^{(i)}$ наименьшее значение в . Таким образом, краевая задача решения, требующая удаления от всех выборок, становится проблемой нахождения максимального значения при заданных ограничениях.

м а Икс γ , ж , б γ с . т . у ( я ) ( ж Т Икс ( я ) + б ) ≥ γ , я знак равно 1 , . . . , м | | ж | | знак равно 1. " role="презентация">maxγ,w,bγs.ty(i)(wTx(i)+b)≥γ,i=1,...,m||w||=1.maxγ,w,bγs .ty(i)(wTx(i)+b)≥γ,i=1,...,m||w||=1.

Однако указанная выше проблема не может быть решена напрямую.Оптимизация, его нужно преобразовать (идея состоит в том, чтобы преобразовать его в стандартныйЗадача выпуклой оптимизации). Сначала мы используемfunctional marginзаменитьgeometric margin, исходная проблема становится:

м а Икс γ ^ , ж , б γ ^ | | ж | | с . т . у ( я ) ( ж Т Икс ( я ) + б ) ≥ γ ^ , я знак равно 1 , . . . , м " role="presentation">max^γ,w,b^γ||w||sty(i)(wTx(i)+b)≥^γ,i=1,...,mmaxγ^,w, bγ^||w||sty(i)(wTx(i)+b)≥γ^,i=1,...,m

Решение этой задачи такое же, как и исходной, разница в том, что в этой задаче мы можем ж , б" роль="презентация"> w,b Не стесняйтесь удваивать, не думая | | ж | | "роль="презентация"> ||w|| увеличить размер. чтобы удалить γ ^ "роль="презентация"> $\hat{\gamma}$ термин интерференция, мы выбираем соответствующим образом ж , б" роль="презентация"> w,b кратные такие, что γ ^ знак равно 1" роль="презентация"> $\hat{\gamma}=1$ , плюс максимизация 1 | | ж | | "роль="презентация"> $\frac{1}{||w||}$ эквивалентно минимизации | | ж | | 2 "роль="презентация"> ||w||^2 ,тогдаОптимизацияОкончательная форма может быть преобразована в:

м я н γ , ж , б 1 2 | | ж | | 2 с . т . у ( я ) ( ж Т Икс ( я ) + б ) ≥ 1 , я знак равно 1 , . . . , м " role="презентация">minγ,w,b12||w||2s.ty(i)(wTx(i)+b)≥1,i=1,...,mminγ,w,b12||w ||2s.ty(i)(wTx(i)+b)≥1,i=1,...,m

Для такой задачи уже можно использовать известнуюОптимизацияалгоритм решения. Но дляSVM, рассмотрим соответствующую задачу. Чтобы получить этот вопрос, нам нужно понятьДвойственность Лагранжа.

Двойственность Лагранжа

заДвойственность ЛагранжаЕсть много вопросов, связанных с конкретными деталями, я рекомендую всем прочитать конспекты лекций C299 иэтот блог. считать общимЗадача выпуклой оптимизации:

м я н ж ф ( ж ) с . т . г я ≤ 0 , я знак равно 1 , . . . , к час я ( ж ) знак равно 0 , я знак равно 1 , . . . , л " role="презентация">minwf(w)stgi≤0,i=1,...,khi(w)=0,i=1,...,lminwf(w)stgi≤0,i= 1, ...,khi(w)=0,i=1,...,l

установить егофункция Лагранжаза:

л ( ж , альфа , бета ) знак равно ф ( ж ) + ∑ я знак равно 1 к альфа я г я ( ж ) + ∑ я знак равно 1 л бета я час я ( ж )" role="презентация">L(w,α,β)=f(w)+k∑i=1αigi(w)+l∑i=1βihi(w)L(w,α,β)=f( w)+∑i=1kαigi(w)+∑i=1lβihi(w)

Рассмотрим функцию:

θ п ( ж ) знак равно Максимум альфа , бета : альфа я ≥ 0 л ( ж , альфа , бета )" роль="представление">θP(w)=maxα,β:αi≥0L(w,α,β)θP(w)=maxα,β:αi≥0L(w,α,β)

существует w" роль="презентация">когда ограничения соблюдены θ п ( ж ) знак равно ф ( ж )" роль="презентация"> $\theta_{\mathcal{P}}(w)=f(w)$ , когда не устраивает θ п ( ж ) знак равно ∞" роль="презентация"> $\theta_{\mathcal{P}}(w)=\infty$ . Итак, в следующей формуле п * "роль="презентация"> p^* Результат аналогичен исходной проблеме.

п * знак равно мин ж θ п ( ж )" роль="презентация">p*=minwθP(w)p*=minwθP(w)

Интересно, что для такой задачи всегда есть соответствующая задача (двойная проблема) и одинаковы при определенных условиях. получитьдвойная проблема, нам просто нужно обменять м я н , м а х" роль="презентация"> min,max порядок, рассмотрим функцию:

θ Д ( альфа , бета ) знак равно мин ж л ( ж , альфа , бета )" роль="представление">θD(α,β)=minwL(w,α,β)θD(α,β)=minwL(w,α,β)

двойная проблемарезультат г * "роль="презентация"> d^* удовлетворяет следующему уравнению, и из неравенства видно, что оно является нижней границей исходной задачи.

г * знак равно Максимум альфа , бета : альфа я ≥ 0 θ Д ( альфа , бета ) ≤ мин ж θ п ( ж ) знак равно п * " роль = "представление"> d * = maxα, β: αi ≥ 0θD (α, β) ≤ minwθP (w) = p * d * = max α, β: αi ≥ 0θD (α, β) ≤ minwθP (w) =р*

Наконец см.двойная проблемаПри каких обстоятельствах решение относится коригинальный вопростакой же. если функция ф , г" роль="презентация"> f,g обавыпуклая функция, ч" роль="презентация">даФункция излучения(линейный), и есть w" роль="презентация">сделать г я ( ж ) g_i(w)<0 , то задача оптимизации имеет решение ж * , альфа * , бета * "роль="презентация"> $w^*,\alpha^*,\beta^*$ , И г * знак равно п * знак равно л ( ж * , альфа * , бета * )" роль="презентация"> $d^*=p^*=\mathcal{L}(w^*,\alpha^*,\beta^*)$ . Тогда наше решение удовлетворяетKKTсостояние, в остальном устраиваетKKTРешение условия является также решением задачи оптимизации (KKTусловия следующие).

∂ ∂ ж я л ( ж * , альфа * , бета * ) знак равно 0 , я знак равно 1 , . . . , м " роль="презентация">∂∂wiL(w∗,α∗,β∗)=0,i=1,...,m∂∂wiL(w∗,α∗,β∗)=0,i= 1,...,м ∂ ∂ бета я л ( ж * , альфа * , бета * ) знак равно 0 , я знак равно 1 , . . . , л " роль="презентация">∂∂βiL(w∗,α∗,β∗)=0,i=1,...,l∂∂βiL(w∗,α∗,β∗)=0,i= 1,...,л альфа я * г я ( ж * ) знак равно 0 , я знак равно 1 , . . . , к " role="презентация">α∗igi(w∗)=0,i=1,...,kαi∗gi(w∗)=0,i=1,...,k г я ( ж * ) ≤ 0 , я знак равно 1 , . . . , к " role="презентация">gi(w*)≤0,i=1,...,kgi(w*)≤0,i=1,...,k альфа я ≥ 0 , я знак равно 1 , . . . , к " роль="презентация">αi≥0,i=1,...,kαi≥0,i=1,...,k

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

пройти черезДвойственность ЛагранжаМы узнали, что у предыдущей задачи о максимальном интервале есть аналог.двойственностьпроблема. Далее мы проходимДвойственность Лагранжачтобы получить этот вопрос.
Для предыдущего порядка вопросов г я ( ж ) знак равно − у ( я ) ( ж Т Икс ( я ) + б ) + 1 ≤ 0" роль="презентация"> $g_{i}(w)=-y^{(i)}(w^Tx^{(i)}+b)+1 \le0$ , и установитефункция Лагранжаза:

л ( ж , б , альфа ) знак равно 1 2 | | ж | | 2 − ∑ я знак равно 1 м альфа я [ у ( я ) ( ж Т Икс ( я ) + б ) − 1 ]" role="презентация">L(w,b,α)=12||w||2−m∑i=1αi[y(i)(wTx(i)+b)−1]L(w, b,α)=12||w||2−∑i=1mαi[y(i)(wTx(i)+b)−1]

Согласно определению двойственной задачи, сначала имеем ж , б" роль="презентация"> w,b попрошайничество л ( ж , б , альфа )" роль="презентация"> $\mathcal{L}(w,b,\alpha)$ минимальное значение , т.е. соответственно w" роль="презентация">и б" роль="презентация">Выведите его, чтобы получить:

ж знак равно ∑ я знак равно 1 м альфа я у ( я ) Икс ( я ) ∑ я знак равно 1 м альфа я у ( я ) знак равно 0" role="презентация">w=m∑i=1αiy(i)x(i)m∑i=1αiy(i)=0w=∑i=1mαiy(i)x(i)∑i=1mαiy(i )=0

будет w" роль="презентация">принести л ( ж , б , альфа )" роль="презентация"> $\mathcal{L}(w,b,\alpha)$ Упростите, чтобы получить:

л ( ж , б , альфа ) знак равно ∑ я знак равно 1 м альфа я − 1 2 ∑ я , Дж знак равно 1 м у ( я ) у ( Дж ) альфа я альфа Дж ( Икс ( я ) ) Т Икс ( Дж ) " role="презентация">L(w,b,α)=m∑i=1αi−12m∑i,j=1y(i)y(j)αiαj(x(i))Tx(j)L(w ,b,α)=∑i=1mαi−12∑i,j=1my(i)y(j)αiαj(x(i))Tx(j)

Плюс альфа я ≥ 0" роль="презентация"> $\alpha_i\ge0$ и ∑ я знак равно 1 м альфа я у ( я ) знак равно 0" роль="презентация"> $\sum\limits_{i=1}^{m}\alpha_iy^{(i)} = 0$ ограничения, мы получаем окончательныйдвойственностьпроблема:

м а Икс альфа Вт ( альфа ) знак равно ∑ я знак равно 1 м альфа я − 1 2 ∑ я , Дж знак равно 1 м у ( я ) у ( Дж ) альфа я альфа Дж ⟨ Икс ( я ) , Икс ( Дж ) ⟩ с . т . альфа я ≥ 0 , я знак равно 1 , . . . , м ∑ я знак равно 1 м альфа я у ( я ) знак равно 0 " role="презентация">maxαW(α)=m∑i=1αi−12m∑i,j=1y(i)y(j)αiαj⟨x(i),x(j)⟩stαi≥0, i = 1,...,mm∑i=1αiy(i)=0maxαW(α)=∑i=1mαi−12∑i,j=1my(i)y(j)αiαj⟨x(i),x(j ) ⟩stαi≥0, i=1,...,m∑i=1mαiy(i)=0

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

Функция ядра

Предположим, что каждый образец имеет три функции Икс 1 , Икс 2 , Икс 3 "роль="презентация"> x_1,x_2,x_3 , часто необходимо отобразить их в более высокие измерения, чтобы соответствовать более сложным функциям, допустимфункция отображенияза:

ф ( Икс ) знак равно [ Икс 1 Икс 1 Икс 1 Икс 2 Икс 1 Икс 3 Икс 2 Икс 1 Икс 2 Икс 2 Икс 2 Икс 3 Икс 3 Икс 1 Икс 3 Икс 2 Икс 3 Икс 3 ] «Роль =« презентация »> φ (x) = ⎡⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢⎣ ⎢⎣ 1 1 1 1 ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 1 11x1x2x1x3x2x1x2x2x2x3x3x1x3x2x3x3 ⎤⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥⎦ ⎥⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥⎦ ⎥⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥⎦ ⎥⎦ ⎥⎦ (x) = [x1x1x1x2x1x2x3x3x2x3x2x3x3]

Внутренний продукт между двумя разными образцами после отображения:

⟨ ф ( Икс ) , ф ( г ) ⟩ знак равно ∑ я , Дж знак равно 1 3 ( Икс я Икс Дж ) ( г я г Дж ) знак равно ∑ я знак равно 1 3 ∑ Дж знак равно 1 3 Икс я Икс Дж г я г Дж знак равно ( ∑ я знак равно 1 3 Икс я г я ) ( ∑ Дж знак равно 1 3 Икс Дж г Дж ) знак равно ( Икс Т г ) 2 " role="презентация">⟨ϕ(x),ϕ(z)⟩=3∑i,j=1(xixj)(zizj)=3∑i=13∑j=1xixjzizj=(3∑i=1xizi) (3∑j=1xjzj)=(xTz)2⟨ϕ(x),ϕ(z)⟩=∑i,j=13(xixj)(zizj)=∑i=13∑j=13xixjzizj=(∑i= 13xizi)(∑j=13xjzj)=(xTz)2

Нетрудно найти, что внутренний продукт между 9 функциями после отображения равен квадрату внутреннего продукта между исходными 3 функциями. В самом деле, последнее из уравнения ( Икс Т г ) 2 "роль="презентация"> (x^Tz)^2 этоФункция ядраодин из. за то н" роль="презентация">характерный случайФункция ядра K ( x , z ) = ( x T z ) 2 " role="presentation"> K(x,z)=(x^Tz)^2 Вычисленное значение равно карте признаков как н 2 "роль="презентация"> n^2 стоимость внутреннего продукта времени. Для исходного нужно рассчитать н 2 "роль="презентация"> n^2 внутренний продукт времени,Функция ядрапросто посчитай н" роль="презентация">Второсортный. В более общем смысле,Функция ядраК ( Икс , г ) знак равно ( Икс Т г + с ) г знак равно ⟨ ф ( Икс ) , ф ( г ) ⟩" роль="презентация"> $K(x,z)=(x^Tz+c)^d=\langle \phi(x),\phi(z) \rangle$ эквивалентно сопоставлению функций с ( н + г г ) "роль="презентация"> ${n+d \choose d}$ измерение.Функция ядраесть очень интересноГауссово ядро, что эквивалентно отображению объектов в бесконечные измерения.

К ( Икс , г ) знак равно е Икс п ( − | | Икс − г | | 2 2 о 2 ) " role="презентация">K(x,z)=exp(-||x−z||22σ2)K(x,z)=exp(-||x−z||22σ2)

Так теперь понятноФункция ядразначение. из-задвойная проблемавключает только расчет внутреннего продукта функции, в то время какФункция ядраЗначение, вычисленное в более низком измерении, равно значению внутреннего продукта сопоставления признаков с более высоким измерением, поэтому мы можем получить довольно эффективный способ решения нашей проблемы. ( оФункция ядраСм. конспекты лекций для C299 для более подробного обсуждения)

Регуляризация

просто скажиSVMЧтобы решить линейную неразделимость набора данных, мы соответствующим образом корректируем исходную задачу, чтобы расстояние могло быть меньше 1, но, соответственно, добавляли определенную стоимость к цели оптимизации.

м я н γ , ж , б 1 2 | | ж | | 2 + С ∑ я знак равно 1 м ξ я с . т . у ( я ) ( ж Т Икс ( я ) + б ) ≥ 1 − ξ я , я знак равно 1 , . . . , м ξ я ≥ 0 , я знак равно 1 , . . . , м " role="презентация">minγ,w,b12||w||2+Cm∑i=1ξis.ty(i)(wTx(i)+b)≥1−ξi,i=1,..., mξi≥0,i=1,...,mminγ,w,b12||w||2+C∑i=1mξis.ty(i)(wTx(i)+b)≥1−ξi,i=1 ,...,mξi≥0,i=1,...,m

использовать то же самоеДвойственность ЛагранжаМожно найти соответствующую задачу, котораяSVMЗадача, которую необходимо решить по алгоритму:

м а Икс альфа Вт ( альфа ) знак равно ∑ я знак равно 1 м альфа я − 1 2 ∑ я , Дж знак равно 1 м у ( я ) у ( Дж ) альфа я альфа Дж ⟨ Икс ( я ) , Икс ( Дж ) ⟩ с . т . 0 ≤ альфа я ≤ С , я знак равно 1 , . . . , м ∑ я знак равно 1 м альфа я у ( я ) знак равно 0 " role="презентация">maxαW(α)=m∑i=1αi−12m∑i,j=1y(i)y(j)αiαj⟨x(i),x(j)⟩st0≤αi≤C , i=1,...,mm∑i=1αiy(i)=0maxαW(α)=∑i=1mαi−12∑i,j=1my(i)y(j)αiαj⟨x(i),x ( j)⟩st0≤αi≤C, i=1,...,m∑i=1mαiy(i)=0

Алгоритм SMO

Вот введениеSMOОсновная идея, конкретные детали алгоритма могут быть указаны в статье. Для задач оптимизации без ограничений Максимум альфа Вт ( альфа 1 , альфа 2 , . . . , альфа м )" роль="презентация"> $\max\limits_{\alpha} W(\alpha_1,\alpha_2,...,\alpha_m)$ , мы можем выбрать альфа я "роль="презентация"> $\alpha_i$ И зафиксируйте другие переменные, чтобы получить максимальное значение функции, и повторяйте, пока значение функции не сойдется (как показано ниже).
[coordinate ascent]
заSVMсерединадвойственностьПроблема, идея аналогична, выбирать каждый раз две переменные альфа я , альфа Дж "роль="презентация"> $\alpha_i,\alpha_j$ , исправить другие переменные. В силу определенных ограничений, альфа я "роль="презентация"> $\alpha_i$ может быть сделано альфа Дж "роль="презентация"> $\alpha_j$ выражать альфа я знак равно ( ζ − альфа Дж у ( Дж ) ) у ( я ) "роль="презентация"> $\alpha_i=(\zeta-\alpha_j y^{(j)})y^{(i)}$ . Таким образом, цель оптимизации может быть преобразована в альфа Дж "роль="презентация"> $\alpha_j$ квадратичный полином а альфа Дж 2 + б альфа Дж + c" роль="презентация"> $a\alpha_j^2+b\alpha_j+c$ Получите лучшее соотношение цены и качества. Конечно, также необходимо учитывать альфа Дж "роль="презентация"> $\alpha_j$ , результат обрезается. Наконец, этот процесс повторяется до тех пор, пока цель оптимизации не сойдется.

Итак~, на шестой неделе все, спасибо за терпение.

P.S. Содержание этой недели сильно сжато, поэтому рекомендуется внимательно прочитать раздаточный материал CSS229. Поскольку курс Эндрю Нг подходит к концу, я собираюсь начать делать несколько небольших проектов, чтобы практиковать свои руки. Для интересных вещей, которые я обычно вижу, любые интересные идеи будут размещены вВейбоВсе желающие могут учиться вместе (●—●)~

hertzcat

2018-05-13