ハードマージンSupport Vector Machine
ハードマージンSVM(Support Vector Machine)の勉強のまとめ。以下の資料に基づく。
資料: http://cs229.stanford.edu/notes/cs229-notes3.pdf
1. はじめに
正例と負例を分割する識別平面を求める際、識別平面のマージン、つまり識別平面の両サイドで訓練データが存在しない領域が、なるべく大きくなるようにしたい。
SVMを使うと、訓練データが線形識別可能な場合、マージンを最大化する識別平面を求めることが出来る。
2. 記法
\(x\)を特徴ベクトル、\(y\)を特徴ベクトルが正例か負例かを表すラベルとする。正例の場合は\(y=+1\), 負例の場合は\(y=-1\).
重みベクトル\(w\)としきい値\(b\)をつかって、識別平面を\(w^Tx+b = 0\)と定義する。\(w^Tx+b\)の正負により正例か負例かを判定することになるので、識別器\(h_{w, b}\)は以下のように定義される。 $$ h_{w,b}(x) = \begin{cases} +1 & & (if\ w^Tx+b \geq 0)\\ -1 & & (otherwise) \end{cases} $$
訓練データとして与える特徴ベクトルを\(x^{(i)}\), そのラベルを\(y^{(i)}\)とする。
識別平面が訓練データを正しく識別することは、全ての\(i\)について \(y^{(i)}(w^Tx^{(i)}+b)\geq 0\)が成り立つことと同値である。
3. マージンの定義
訓練データと識別平面が与えられた時の"マージン"を定義する。
まずは訓練データ\(x^{(i)}\)と識別平面\(w^Tx+b = 0\)の距離\(\gamma^{(i)}\)について考えてみる。
訓練データ\(x^{(i)}\)が正例(\(y^{(i)}=+1\))である場合、 識別平面の垂直ベクトルは\(w/\|w\|\)であり、かつ正例の空間を向いていることから、 \(x^{(i)}\)から識別平面に垂線を下ろした時の交点は、\(x^{(i)}-\gamma^{(i)}\cdot w/\|w\|\)となる。 交点は識別平面上であることから、以下が成り立つ。 $$ w^T(x^{(i)}-\gamma^{(i)}\cdot w/\|w\|) - b = 0 $$ 従って、\(\gamma^{(i)}\)は以下のようになる。 $$ \gamma^{(i)} = \frac{w^Tx^{(i)}+b}{\|w\|} $$
一方で、訓練データが\(x^{(i)}\)が負例である場合は、 $$ \gamma^{(i)} = -\frac{w^Tx^{(i)}+b}{\|w\|} $$ となる。 従って、識別平面が訓練データを正しく識別する場合は、正例・負例を問わず、\(\gamma^{(i)}\)は以下のように書ける。 $$ \gamma^{(i)} = y^{(i)}\cdot\frac{w^Tx^{(i)}+b}{\|w\|} $$
ここで、"マージン"を\(\gamma^{(i)}\)の中で最小のもの、つまり\(\min_i \gamma^{(i)}\)と定義する。
4. マージンの最大化
マージンを最大化する\(w\)と\(b\), つまり、 $$ \begin{eqnarray} \max_{w, b}\min_i \gamma^{(i)} &=& \max_{w, b}\min_i y^{(i)}\cdot\frac{w^Tx^{(i)}+b}{\|w\|}\\ &=& \max_{w, b}\left(\frac{1}{\|w\|}\min_i y^{(i)}(w^Tx^{(i)}+b)\right) \end{eqnarray} $$ を与える\(w\)と\(b\)を求めていきたい。
ここで、\(w\)と\(b\)に任意の正の定数をかけても、識別平面の意味は変わらない。つまり、\(\min_i y^{(i)}(w^Tx^{(i)}+b)=1\)という条件を設けても構わない。すると、 $$ \begin{eqnarray} & &\max_{w, b}\frac{1}{\|w\|} \\ & & s.t.\ \ \forall i.\ y^{(i)}(w^Tx^{(i)}+b) \geq 1 \end{eqnarray} $$ という問題を解けばよいことになる。計算を解きやすくするために、以下の同値の問題に変換する。 $$ \begin{eqnarray} & &\min_{w, b}\frac{1}{2}\|w\|^2 \\ & &s.t.\ \ 1 - y^{(i)}(w^Tx^{(i)}+b) \leq 0\ \ (\forall i) \end{eqnarray} $$ この最適化問題の解となる\(w, b\)を求めていく。
ところで、\(\min_i y^{(i)}(w^Tx^{(i)}+b)=1\)を与える\(x^{(i)}\),つまり識別平面に最も近い訓練データをサポートベクターと呼び、このアルゴリズム名の由来となっている。
5. 双対問題への変換
上記の最適化問題をそのまま二次計画問題として解くこともできるが、より効率的に解くために、 ラグランジュの双対性を用いる。制約条件を\(g_i(w, b)=1 - y^{(i)}(w^Tx^{(i)}+b)\) と置いた上で、ラグランジュ乗数\(a_i\ (\geq 0)\)を用いてラグランジュ関数に変換する。 $$ L(w, b, a)=\frac{1}{2}\|w\|^2 + \sum_i a_i g_i(w, b) $$ すると、元々解こうとしていた最適化問題(primal; 主問題)は、 $$ \begin{eqnarray} & & \min_{w, b}\max_{a; a_i\geq 0}L(w, b, a)\\ & & s.t.\ \ g_i(w, b) \leq 0\ \ (\forall i) \end{eqnarray} $$ と書ける(\(g_i(w, b) = 1 - y^{(i)}(w^Tx^{(i)}+b) \leq 0\ \ (\forall i)\)の条件で \(\max_{a; a_i\geq 0}L(w, b, a)=\frac{1}{2}\|w\|^2\)であるから).
これの双対問題(dual)は、minとmaxを入れ替えたもの、つまり \(\max_{a; a_i\geq 0}\min_{w, b}L(w, b, a)\)と定義される。 主問題と双対問題の間では以下の関係が成り立つ(弱双対定理)。 $$ \max_{a; a_i\geq 0}\min_{w, b}L(w, b, a) \leq \min_{w, b}\max_{a; a_i\geq 0}L(w, b, a) $$ さらに、
- 目的関数(\(\frac{1}{2}\|w\|^2\))が凸であり、
- かつ各制約関数\(g_i\)がアフィン関数であり、
- かつ\(g_i\)が実行可能である(\(g_i(w, b)\leq 0\ \ (\forall i\)を満たす\(w, b\)が存在する; the weak Slater's condition)
場合、上記の式で等号が成り立つ(強双対定理)。実際にこれらの条件を満たすので、 主問題の代わりに双対問題を解けば、主問題の最適解が見つかったことになる。
6. 双対問題の最適解
そこで、双対問題\(\max_{a; a_i\geq 0}\min_{w, b}L(w, b, a)\)を解いていく。 まずは、\(L(w, b, a)\)を\(w\)と\(b\)に関して最小化する。 \(\nabla_w L(w, b, a)=0\)という条件から、 $$ w=\sum_i a_iy^{(i)}x^{(i)} $$ が導かれる。これを\(L(w, b, a)\)に代入すると以下の式が得られる。 $$ L(w, b, a)=\sum_i a_i - \frac{1}{2}\sum_{i, j}y^{(i)}y^{(j)}a_ia_j(x^{(i)})^Tx^{(j)} - b\sum_i a_iy^{(i)} $$
さらに\(\frac{\partial}{\partial b}=0\)という条件から $$ \sum_ia_iy^{(i)}=0 $$ が導かれる。そのため、上記\(L(w, b, a)\)の最後の項は\(0\)となる。 以上から、\(L(w, b, a)\)を\(w\)と\(b\)に関して最小化した結果は、 $$ L(w, b, a)=\sum_i a_i - \frac{1}{2}\sum_{i, j}y^{(i)}y^{(j)}a_ia_j(x^{(i)})^Tx^{(j)} $$ となる。
次のステップは、上記を\(a\)について最大化する。 $$ \begin{eqnarray} & & \max_a & & \sum_i a_i - \frac{1}{2}\sum_{i, j}y^{(i)}y^{(j)}a_ia_j(x^{(i)})^Tx^{(j)}\\ & & s.t. & & a_i \leq 0\ \ (\forall i)\\ & & & & \sum_i a_i y^{(i)} = 0 \end{eqnarray} $$ この双対問題はSMO(Sequential Minimall Optimization)というアルゴリズムで解ける。 基本的には、ベクトル\(a\)の中から2変数を選択し、\(\sum_i a_i y^{(i)} = 0\) を満たすように動かすことで最適解に近づいていく、というもののようだ。
SMOにより最適な\(a\)(\(a^\ast\)とする)が見つかったとすると、 \(w=\sum_i a_iy^{(i)}x^{(i)}\)という条件から、最適な\(w\)が以下のように求まる。 $$ w^\ast=\sum_i a_i^\ast y^{(i)}x^{(i)} $$
\(b\)については以下のように求まる。主問題での制約条件 \(1 - y^{(i)}(w^Tx^{(i)}+b) \leq 0\ \ (\forall i)\)から、\(b\)は $$ 1-w^{\ast T} x_{I^+}\leq b \leq -1-w^{\ast T}x_{I^-} $$ を満たさねければならない。 ここで、\(x_{I^+}=\arg\!\min_{x_i} \{w^{\ast T} x_i \mid y_i = +1\}\), \(x_{I^-}=\arg\!\max_{x_i} \{w^{\ast T} x_i \mid y_i = -1\}\)である。 そこで、上記の右辺と左辺の中間をとるのが最適なので、 $$ b^\ast = - \frac{1}{2}(w^{\ast T} x_{I^+} + w^{\ast T}x_{I^-}) $$ となる。
以上より、識別平面が求まった。 $$ \begin{eqnarray} w^{\ast T}x + b^\ast &=& (\sum_i a_i^\ast y^{(i)}x^{(i)})^T x + b^\ast \\ &=& \sum_i a_i^\ast y^{(i)}\langle x^{(i)}, x\rangle - \frac{1}{2}(w^{\ast T} x_{I^+} + w^{\ast T}x_{I^-}) \end{eqnarray} $$
7. KKT条件
強双対条件が成り立つ場合、最適解\(w^\ast, b^\ast, a^\ast\)に関して、 KKT条件と呼ばれるいくつかの条件式が成り立つ。 そのうちの1つが、KKT相補性条件と呼ばれる以下のものである。 $$ a_i^\ast g_i(w^\ast, b^\ast) = 0\ \ (\forall i)$$ この条件から、もし\(g_i(w^\ast, b^\ast) < 0\), つまり \(1 < y^{(i)}((w^\ast)^Tx^{(i)}+b^\ast)\)ならば、\(a_i^\ast = 0\)という 制約が導かれる。今、 \(\min_i y^{(i)}(w^Tx^{(i)}+b)=1\)という条件のもとで 問題を解いていた。つまり、最も識別平面に近い訓練データ (サポートベクター)ではない場合、 \(1 < y^{(i)}(w^Tx^{(i)}+b)\)のはずなので、 \(a_i^\ast = 0\)となる。つまり、サポートベクター以外の大多数の訓練データについて\(a_i^\ast = 0\)となるので、 求まった識別平面による判別は十分効率的である。
AWS: instance, volume, AMI, snapshotの関係
触り始めたもののちょっと用語がわかりづらかった。整理のためにメモ。
- instance: VMのこと(EC2 instanceともいう)
- volume: instanceにアタッチされるストレージ(EBS, EBS volumeともいう)
- AMI: instanceのバックアップ(Amazon Machine Imageあるいはimageともいう)
- shapshot: volumeのバックアップ
instanceには複数のvolumeをアタッチできる。逆に、1つのvolumeを複数のinstanceが共有する(同時にアタッチする)ことはできない。
マネージメントコンソールで起動中のinstanceを指定して'Create Image'すると、AMIが作成される。この際、instanceにアタッチされているvolumeも、snapshotとして保存される。
instance --- (Create Image) ---> AMI └ volume └ snapshot
また、コンソールでvolumeを指定して'Create Snapshot'すると、snapshotが作成される。
instance └ volume --- (Create Snapshot) ---> snapshot
Tesseract OCRで数字の認識
オープンソースで最も認識精度が高いと言われている文字認識エンジン、Tesseractで数字を認識してみる。名刺の中の電話番号を認識する、という想定。OSはMac OS X.
画像の準備
名刺っぽいプリントアウトをスマホのカメラで撮影。 画像サイズは2592x1944. 人名や住所などは全くデタラメw
tesseractのインストール
tesseractをMacPortsでインストール。
sudo port install tesseract
ソースコード
処理の流れとして、まず二値化を行い、次に文字認識を適用する。文字認識結果の出力とは別に、二値化の結果画像もtifファイルとして保存する。
文字認識では、数字といくつかの記号をホワイトリストとしている。なので、後に見るように、漢字やアルファベットなども無理やり数字として解釈してしまう。
認識結果の一文字ごとに確信度(confidence)が割り当てられる。認識結果を出力する際は、確信度が高いものと低いものを区別して出力する。低いものにはインデントを付けて出力する。
#include <iostream> #include <cstdlib> #include <tesseract/baseapi.h> #include <leptonica/allheaders.h> using namespace std; using namespace tesseract; int main(int argc, char **argv) { if(argc != 3){ cerr << "USAGE: " << argv[0] << " /path/to/image /path/to/bi-output-image" << endl; exit(1); } char* src = argv[1], *bi = argv[2]; // // 入力画像を二値化する // PIX *pixsrc = pixRead(src); PIX *pixgray = pixConvertRGBToLuminance(pixsrc); // グレイスケールに一度変換 PIX *pixbi = pixCreate(pixgray->w, pixgray->h, 2); // 二値化 pixOtsuAdaptiveThreshold(pixgray, pixgray->w, pixgray->h, 0, 0, 0.1, NULL, &pixbi); pixWrite(bi, pixbi, IFF_TIFF); // 要らないものをfinalize pixDestroy(&pixsrc); pixDestroy(&pixgray); // // 文字認識実行 // TessBaseAPI tess; if(tess.Init(NULL, "eng")){ cerr << "could not initialize tesseract" << endl; exit(1); } tess.SetVariable("save_blob_choices", "T"); // ホワイトリスト設定 tess.SetVariable("tessedit_char_whitelist", "0123456789 -:()"); tess.SetImage(pixbi); tess.Recognize(NULL); ResultIterator* ri = tess.GetIterator(); if(ri != 0){ // 一文字ずつ結果を見ていく do { const char* symbol = ri->GetUTF8Text(RIL_SYMBOL); if(symbol != 0){ float conf = ri->Confidence(RIL_SYMBOL); // 認識結果と確信度を出力 if(conf < 80) // 確信度が低ければインデントを付与 cout << " \'" << symbol << "\'" << " confidence: " << conf << endl; else cout << "\'" << symbol << "\'" << " confidence: " << conf << endl; // ChoiceIterator ci(*ri); // do { // const char* choice = ci.GetUTF8Text(); // cout << "\t\t\t" << "\'" << choice << "\': " // << ci.Confidence() << endl; // } while(ci.Next()); } delete[] symbol; } while((ri->Next(RIL_SYMBOL))); } tess.Clear(); tess.End(); pixDestroy(&pixbi); return 0; }
ビルド
g++ -o tess tess.cpp -O2 -I/opt/local/include -L/opt/local/lib -llept -ltesseract
実行
第一引数に入力画像を、第二引数に保存する二値化画像のファイル名を与える。結果は以下のとおり。
$ ./tess cap.jpg cap.tif '3' confidence: 55.7878 '5' confidence: 48.2515 '1' confidence: 74.4947 '2' confidence: 74.8571 '9' confidence: 65.7379 '4' confidence: 50.08 '0' confidence: 13.8199 '3' confidence: 66.5101 '0' confidence: 22.5098 '0' confidence: 6.99005 '0' confidence: 91.9207 '8' confidence: 93.2891 '5' confidence: 91.6527 '-' confidence: 94.7043 '0' confidence: 90.4132 '0' confidence: 91.5067 '3' confidence: 95.2874 '2' confidence: 92.9869 '1' confidence: 64.2396 '0' confidence: 49.9588 '5' confidence: 69.2291 '0' confidence: 16.5115 '5' confidence: 54.0336 '1' confidence: 63.1991 '5' confidence: 52.3447 '3' confidence: 56.4374 '1' confidence: 74.0782 '0' confidence: 44.8059 '0' confidence: 51.2802 '5' confidence: 56.8292 '5' confidence: 50.2101 '0' confidence: 58.1238 '0' confidence: 23.41 '0' confidence: 51.4877 '5' confidence: 67.2946 '0' confidence: 29.2511 '0' confidence: 41.8625 '0' confidence: 45.2179 '1' confidence: 73.9682 '7' confidence: 93.7799 '-' confidence: 96.4489 '1' confidence: 88.6481 '4' confidence: 91.9315 '-' confidence: 93.9458 '9' confidence: 90.9804 '0' confidence: 20.1172 '1' confidence: 69.0272 ':' confidence: 95.3482 '0' confidence: 88.9497 '1' confidence: 94.7421 '5' confidence: 91.4299 '4' confidence: 93.6259 '-' confidence: 96.483 '9' confidence: 90.8426 '7' confidence: 94.9449 '-' confidence: 90.6047 '4' confidence: 91.5667 '8' confidence: 90.4304 '9' confidence: 88.8301 '8' confidence: 94.6282 '0' confidence: 69.7327 '0' confidence: 64.6164 '1' confidence: 70.6974 '0' confidence: 67.1356 '0' confidence: 56.4117 ':' confidence: 92.6204 '1' confidence: 70.3545 '(' confidence: 79.365 '3' confidence: 73.291 '0' confidence: 28.9734 '5' confidence: 70.0992 '0' confidence: 57.6477 '0' confidence: 30.6046 '0' confidence: 74.5287 '5' confidence: 82.144 '0' confidence: 74.3088 '0' confidence: 72.9004 '0' confidence: 50.3754 '6' confidence: 51.6748 '0' confidence: 76.4664 '0' confidence: 16.0721 '0' confidence: 76.0345 '6' confidence: 68.1494 '0' confidence: 19.3069 '1' confidence: 64.2986 '0' confidence: 1.06659 '0' confidence: 75.0809
インデントされているのは確信度が80よりも小さい文字。名刺の中の漢字やアルファベットは、ほとんどが80より小さくなっている。逆に、数字の認識はいずれも確信度が高く、実際にすべて成功している。
従って、確信度の高いチャンクを切り出し、電話番号のフォーマットに合致しているものを取り出せば、今回は電話番号を特定できたことになる。
ちなみに以下が二値化された画像。良好に二値化されている。
文字認識エンジンTesseract OCRで学習
はじめに
Googleの文字認識エンジンTesseract 3.02での学習プロセスの備忘録。OSはMac OS X. jTessBoxEditorという、学習を省力化するツールを使ってみる。
題材として、デジタル時計や電卓のような文字を認識するための学習をする。文字は[0-9]
と:
に限定。
参考:
- TrainingTesseract3 - https://code.google.com/p/tesseract-ocr/wiki/TrainingTesseract3
- jTessBoxEditor - http://vietocr.sourceforge.net/training.html
フォントの取得
まずは上述したようなフォントがないと始まらない。
http://www.trojanbear.net/s/category/font の7barSPというフォントを使う。
ダウンロードしたら展開し、OS XのFont bookからインストールする。
tesseractのインストール
最初に、tesseractが依存する画像処理ライブラリleptonicaをインストール。
sudo port install leptonica
次に、tesseract 3.02をソースからインストール。まずパッケージの取得。
wget https://tesseract-ocr.googlecode.com/files/tesseract-ocr-3.02.02.tar.gz
tar xzf tesseract-ocr-3.02.02.tar.gz
cd tesseract-ocr
そしてビルド。配置先はホームディレクトリにする。
./configure --prefix=$HOME/tesseract LIBLEPT_HEADERSDIR=/opt/local/include/leptonica make make install
最後に、デフォルトの英語辞書をインストール。
wget https://tesseract-ocr.googlecode.com/files/tesseract-ocr-3.02.eng.tar.gz
tar xzf tesseract-ocr-3.02.eng.tar.gz
cp tesseract-ocr/tessdata/eng.* $HOME/tesseract/share/tessdata/
学習なしで試してみる
ここで試しに、学習なしで、7barSPフォントで15:39
と書かれたイメージを認識させてみる。
# ImageMagickでイメージを作成 convert -background white -fill black -font 7barSP -size 150x label:15:39 1539.png # 数値と':'のみをホワイトリストとするための制御ファイル echo 'tessedit_char_whitelist 0123456789:' > tess.conf # 実行 -> byeng.txtに結果が出力される $HOME/tesseract/bin/tesseract 1539.png byeng -l eng tess.conf
結果は以下のとおり。今のところ認識に失敗している。
$ less byeng.txt 35 35
学習 - 辞書の作成
ここから辞書を作成していく。
1. jTessBoxEditorのインストール
jTessBoxEditorを取得・起動する。
wget -O jTessBoxEditor-1.3.zip http://sourceforge.net/projects/vietocr/files/jTessBoxEditor/jTessBoxEditor-1.3.zip/download unzip jTessBoxEditor-1.3.zip cd jTessBoxEditor # 環境変数を設定 export TESSDATA_PREFIX=$HOME/tesseract/share # 起動 java -Xms128m -Xmx1024m -jar jTessBoxEditor.jar &
起動後に、GUIから、tesseractの実行ファイルの置かれたディレクトリを指定してやれば、とりあえずツール準備は完了。
2. 学習に必要なデータの準備
jTessBoxEditorを使った学習では、以下のファイルを用意する必要があるようだ。
- tifファイル: 文字データのイメージをtif形式として保存したもの。今回は
0123456789:
という文字列のイメージを準備 - boxファイル: tifファイルの中の一文字一文字の座標と大きさを記録したファイル
- font propertiesファイル: フォントの情報を与えたもの
- word listファイル: 単語のリスト。今回は空ファイルとする
- frequent word listファイル: 頻出単語のリスト。今回は空ファイルとする
以上のファイルを ~/train
に作っていく。
2-1. tifファイルとboxファイル
この2つは、jTessBoxEditorを使って生成する。
- ツールで、'TIFF/Box Generator'というタブを選択
- 'Output'にledと入力。3文字であれば基本的になんでもよいはず。今回は、フォントの形状がLEDサインを連想させるので、ledと名付ける
- フォントとして7barSPを選択。フォントサイズは48ptとした
- 下のペインに
0123456789:
と入力。本来は学習の精度を上げるために、もっと多くの単語を入力したほうが良いと思われる - 'generate'をクリック
すると、led.7barsp.exp0.tif
とled.7barsp.exp0.box
が生成される。これらを~/train
に移動する。
試しに、'Box Editor'というタブを開き、生成されたtifファイルを選択すると、一文字一文字がどのようにboxされているかを確認できる。
このように自動でboxファイルを作れることが、jTessBoxEditorの一番のメリットか。
2-2. font propertiesファイル
これはコマンドラインから作る。
1列目にフォント名7barsp
を与える(tif/boxファイル名の中の文字列に対応)。 2列目以降には、そのフォントが、italic, bold, fixed, serif, frakturに相当するか否かを、順に0/1で与える。
cd ~/train echo '7barsp 0 0 0 0 0' > led.font_properties
2-3. word listファイルとfrequent word listファイル
これらはいずれも空ファイルとする。
cd ~/train touch led.words_list led.frequent_words_list
3. 学習実行
jTessBoxEditorの'Trainer'タブを開き、'Training Data'で~/train
を、'Language'を'led'に設定する。そして、'Train with Existing Box'を指定して'Run'.
ズラズラとログが表示されるが、成功すれば上記5つ以外のファイルがいくつか生成されている。
最後にファイルを1つにまとめる。led
のあとのドットを忘れない。
cd ~/train $HOME/tesseract/bin/combine_tessdata led.
これで、目的となるled.traineddata
という辞書が生成された。$HOME/tesseract/share/tessdata/
に移動すれば完了。
cp -f led.traineddata $HOME/tesseract/share/tessdata/
テスト
$HOME/tesseract/bin/tesseract 1539.png byled -l led # 実行 -> byled.txtに結果が出力される
結果は以下の通り。ちゃんと認識できるようになった!
$ less byled.txt 15:39
ノイズの入ったイメージなどでも試してみたい。
MacPortsでMySQL 5.6
YosemiteでMacPortsでMySQL 5.6をインストールした時の備忘録。
# インストール sudo port install mysql56 mysql56-server # 初期化 sudo -u _mysql /opt/local/lib/mysql56/bin/mysql_install_db # 一度立ち上げる(/opt/localに移動しないと失敗) cd /opt/local ; sudo /opt/local/lib/mysql56/bin/mysqld_safe & # 管理者パスワード設定(コマンドラインでパスワード与えるな的なwaringが出る) /opt/local/lib/mysql56/bin/mysqladmin -u root password '********' # .bashrcでalias設定 cat >> ~/.bashrc <<EOF alias mysql_start='sudo -s "cd /opt/local; /opt/local/lib/mysql56/bin/mysqld_safe" &' alias mysql_stop='/opt/local/lib/mysql56/bin/mysqladmin shutdown -uroot -p' alias mysql_restart='mysql_stop; mysql_start' alias mysql='/opt/local/lib/mysql56/bin/mysql' EOF
Widrow-Hoffの学習規則
はじめに
前回、識別境界を求めるためのアルゴリズムとしてパーセプトロンを組んだが、その流れで"Widrow-Hoffの学習規則"を組んでみる。ほぼ勉強の備忘録。。
Widrow-Hoffの学習規則
パーセプトロンと同様、2値のラベルが与えられた多次元データを分類するための境界を 求めるアルゴリズム。
パーセプトロンは、与えた学習データが線形識別可能である場合、学習データを正しく分離する境界を必ず返す。一方で、与えたデータが線形識別可能でない場合、アルゴリズムが停止しない。
Widrow-Hoffの学習規則は、与えたデータが線形識別可能でない場合も、誤差をなるべく小さく抑える識別境界を求められる。その代わり、線形識別可能な場合でも、学習データを正しく識別しないことがある。
理論
\({\bf x}_1,\dots,{\bf x}_n\)を学習データ、\(b_1,\dots,b_n\)を各学習データに与えられたラベル(教師信号)とする(\(b_i \in \{-1,+1\}\)). \({\bf w}\)を 線形識別関数の重みベクトル(識別ベクトル)とする。
各学習データ\({\bf x}_i\)について、識別関数による識別結果\({\bf w}^t{\bf x}_i\)と教師信号\(b_i\)の誤差は、以下のようになる。$$\epsilon_i ={\bf w}^t {\bf x}_i - b_i$$
ここで、二乗誤差\(J_i\)を考える。$$J_i = \frac{1}{2}\epsilon_i^2 = \frac{1}{2}({\bf w}^t {\bf x}_i - b_i)^2$$
各学習データの二乗誤差\(J_i\)の和\(J\)は以下のようになる。$$J = \sum_i J_i = \sum_i\frac{1}{2}({\bf w}^t {\bf x}_i - b_i)^2 $$
\(J\)を最小化する\({\bf w}\)を求めることが目的となる。ランダムな\({\bf w}\)を初期値とし、最急降下法で反復的に\({\bf w}\)を更新していく。\({\bf w'}\)は1つ前(更新前)の識別関数である: $${\bf w} = {\bf w'} - \rho\frac{\partial J}{\partial {\bf w}}$$
ここで、$$ \frac{\partial J}{{\partial {\bf w}}} = \sum_i \frac{\partial J_i}{{\partial {\bf w}}} = \sum_i ({\bf w}^t{\bf x}_i - b_i){\bf x}_i$$ となるので、\({\bf w}\)の更新式は以下のとおり。 $${\bf w} = {\bf w'} - \rho \sum_i ({\bf w}^t{\bf x}_i - b_i){\bf x}_i$$
例
線形識別できない例を考える。
label | x | y |
---|---|---|
+1 | -2 | 1 |
+1 | -1 | 4 |
+1 | 1 | 3 |
+1 | 3 | 3 |
+1 | -1 | 3 |
-1 | -3 | 1 |
-1 | 0 | -1 |
-1 | 2 | 1 |
-1 | 3 | 2 |
-1 | 0 | 3 |
この例に対してパーセプトロンを適用しても停止しないが、Widrow-Hoffの学習規則であれば停止する。
サンプルのソースコード https://gist.github.com/danglingfarpointer/2d425339ea54d4140668 だと、0.402 * x + 1.713という解を出力した。
マッチ箱の脳(AI) -- パーセプトロン
はじめに
前回の「マッチ箱の脳(AI)」のネタで、今回は「パーセプトロン」を組んでみることにしました。
パーセプトロンとは
機械学習のアルゴリズムの1つで、ラベル付けされた多次元データを、ラベルごとに分類する境界を求めるアルゴリズムです。
以降は簡単のため、2次元データに対して2値のラベル(-1または+1)が付けられるケースに限定します。
例えば:
label | x | y |
---|---|---|
+1 | -2 | 1 |
+1 | -1 | 4 |
+1 | 1 | 3 |
+1 | 3 | 3 |
-1 | -3 | -1 |
-1 | 0 | -1 |
-1 | 2 | 1 |
-1 | 3 | 2 |
というデータに対しては、y = 0.5x + 1 が+1のデータと-1のデータを分類する境界となります。このような識別境界を求める手法の1つが、パーセプトロンです。
パーセプトロンのアルゴリズム
- \(ax + by + c = 0\) という直線を考える。\(a, b, c\)はランダムに初期化
- \(a, b, c\)が更新されなくなるまで、以下を行う:
- 各訓練データ\((x_i, y_i)\)について、
- \(k = ax_i + by_i + c \)を求める
- \(k\)が\(+\)だが訓練データのラベルが\(-\)である場合、\(a = a-x_i, b = b-y_i, c -= c-1\)と更新
- \(k\)が\(-\)だが訓練データのラベルが\(+\)である場合、\(a = a+x_i, b = b+y_i, c = c+1\)と更新
- 各訓練データ\((x_i, y_i)\)について、
上記が停止した時、\(ax + by + c = 0\)が識別境界となります。非常にシンプルです。なぜこの更新方法で良いのかについては、ちゃんとした理論があるようですが、正確に理解しているか怪しいので飛ばします- -;)
2次元データが「線形識別可能」、つまり直線により識別できるならば、上記のアルゴリズムは必ず停止し、答えが求まります。
例
上述した例に対してパーセプトロンを適用した結果です。5回の更新で識別境界を求めることが出来ました。ちなみにその境界は、 y = 0.581*x + 0.878.最終的な解に至る過程(cycle 0 -- cycle 4)も記しています(色で区別してるだけなので見難いかも)
補足
サンプルのJavaScriptソースコード(Node.js). https://gist.github.com/danglingfarpointer/2fa56b9359ec2e260f6b