読者です 読者をやめる 読者になる 読者になる

(OCW)機械学習の授業のめもその4

KKT条件、双対問題、カーネル関数が登場。前半の講義最後の山場っぽい。

関連する文献

黄色いのがいいです。

第六回のめも


(OCW)機械学習の授業のめもその3 - 雑なメモ



第七回授業メモ


最適マージン分類器の同値な問題定義の方法

一つ目の定義

{
 max_{\gamma,w,b} \gamma \\
 s.t. y^{(i)} (w^T x^{(i)} + b) \geq \gamma \\
 || w || = 1
}

二つ目の定義

{
 max_{\gamma,w,b} \frac{\hat{\gamma}}{|| w ||} \\
 s.t. y^{(i)} (w^T x^{(i)} + b) \geq \hat{\gamma} \\
}

三つ目の定義

{
 min_{\gamma,w,b} {|| w ||}^2 \\
 s.t. y^{(i)} (w^T x^{(i)} + b) \geq 1
}

三つ目の定義は他の二つと違い、目的関数を最小化する。だけどこの式はどこから出てきたのかが問題。

Lagrange multiplier(ラグランジュ未定乗数法)とDual Problem(双対問題)


 講義資料cs229-notes3.pdfの八ページからの内容。明らかに重要な箇所。ラグランジュ未定乗数法*1を導入する。省略。

そして双対問題の考え方も導入する。

が参考資料としていいかもしれない。

KKT条件を講義27:30ころから紹介。しかし以前以下の記事にメモしたのでここでは省略。

最適化:非線形計画+組み合わせ最適化のまとめのメモ - 雑なメモ


 以下のような形の最適化問題を考えるとする。
{
 {min}_w f(w) \\
 s.t. h_i (w) = 0, i \in \{0,\dots,n\}
}
このときにLagrangianと呼ばれる式Lを

{
 L = L(w,\beta) = f(w) + \sum_i^n \beta_i h_i (w)
}

と定義する。特にこの式の中の係数{\beta_i}ラグランジュ乗数と呼ばれる。この式を偏微分して

{
\frac{dL}{d w_i} = 0 , \frac{d L}{d \beta_i} = 0
}

とするように{w,\beta}を求める。結局、制約条件{h_i (w)}に対してLagrange multiplier {\beta_i}を与えてこれらを係数とする線形結合である新しい関数{L}を作れば、元の問題の「最適解を求める問題」は「関数{L}極値を求める問題」に置き換えられるということ。しかしこれでは等式の制約条件だけを持つ最適化問題しか解けないから、不等式の制約条件を持つ問題も解けるように一般化する必要がある..。そのためには何をすればいいだろうか。

 以下のような問題を定義してそれをprimal optimization problem(主最適化問題)と呼ぶことにする。
{
 {min}_w f(w) \\
 s.t. g_i (w) \leq 0 , i = 1 , \dots,k \\
 h_i (w) = 0 , i = 1 , \dots, l 
}
つまりkこの不等式制約とl個の等式制約条件がある一般的な最適問題を書いたのがこの式。そして一般化ラグランジュ関数Lを

{
 L = L(w,\alpha, \beta) = f(w) + \sum_i^k \alpha_i g_i(w) +  \sum_j^l \beta_j h_j(w)
}

と記述する。{\alpha_i,\beta_i}ラグランジュ乗数と呼ばれる係数。 そして以下の式

{
 \theta_{primal} (w) = {max}_{\alpha,\beta,\alpha_i \geq 0} L(w,\alpha,\beta)
}

を考える。


書きかけです。講義44:22頃まで。


情報源及び出典、参照元

※上記のページおよびpdf、上記以外の参考文献や関連ページを注釈の形でページ末尾に改めて記載します。