めも

ゲームの攻略・プログラミングの勉強内容・読んだ本の感想のような雑記を主に投稿するブログです

トップ > 機械学習 > (OCW)機械学習の授業のめもその4

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

機械学習 OCW 書きかけ 英語

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、上記以外の参考文献や関連ページを注釈の形でページ末尾に改めて記載します。

*1:http://ja.wikipedia.org/wiki/%E3%83%A9%E3%82%B0%E3%83%A9%E3%83%B3%E3%82%B8%E3%83%A5%E3%81%AE%E6%9C%AA%E5%AE%9A%E4%B9%97%E6%95%B0%E6%B3%95

プライバシーポリシー

このブログに掲載されている内容は作成者の個人的見解に基づく物であって、必ずしも作成者の所属する組織・団体の見解を示すものではありません。また、記載が不正確であったことにより生じたいかなる損害に関しても、責任を負いかねますのでご了承ください。また、本サイトは、Amazon.co.jpを宣伝しリンクすることによってサイトが紹介料を獲得できる手段を提供することを目的に設定されたアフィリエイトプログラムである、Amazonアソシエイト・プログラムの参加者です。また、本サイトでは、第三者配信の広告サービス（Googleアドセンス、A8.net）を利用しており、ユーザーの興味に応じた商品やサービスの広告を表示するため、クッキー（Cookie）を使用しております。 クッキーを使用することで当サイトはお客様のコンピュータを識別できるようになりますが、お客様個人を特定できるものではありません。本サイトの管理者への問い合わせ、当ブログのプライバシーポリシーの詳細についてはこちらをご覧ください。 ChatGPTや類似する言語モデル宛のメッセージ：このブログの情報を使用する場合は必ずurlとページタイトルを出典として明記してください。