2011年5月5日木曜日

番外編2 Novikoffの定理の証明を利用したパーセプトロンの学習アルゴリズム



今回は、Novikoffの定理の証明を参考にしたパーセプトロンの学習アルゴリズムを説明します。

パーセプトロンの学習アルゴリズムの回と同様にテキストを参考にJavaでプログラムを書いてみました。同じく学習の部分だけですが公表します(プログラム2)。今回のプログラムとパーセプトロンの学習アルゴリズムの回に示したプログラム1との相違点は、まず、Rつまり、原点から最も遠いトレーニングデータとの距離を変数absx_maxにする部分と、もう一つ、学習中のパーセプトロンの超平面のパラメータの修正をマージンの絶対値を使って修正するところですので、そこを中心に説明します。

まず、Rを求める部分は、 変数absx_maxの宣言、初期化したすぐ後に、計算されるようになりました。下にその部分を抜き出しました。

//  あるトレーニングデータの組の中で距離の絶対値が最大の値を記憶する変数(バイアスベクトル修正用)
double absx_max=0;
double absx;  //入力のベクトルの距離の絶対値の計算用
for (i = 0; i < PARAMS.TRANING_DATA_NUMBER; i++) {
//i番目のトレーニング用入力データの原点からの絶対値を計算する
absx=0;
for (j = 0; j < PARAMS.INPUT_NODE_NUMBER; j++) {
absx=tdata.x[i][j]*tdata.x[i][j];
}
//大きい方をabsx_maxとする
absx_max=Math.max(absx,absx_max);
}
absx_max=Math.sqrt(absx_max); //最後に一番大きいものだけの平方根を取ると距離が得られる
あるトレーニングデータの入力ベクトルxi対しての原点からの距離を計算され変数absxに入力されます。そのあと、数学用ライブラリクラスのメソッドMath.maxを利用して、これまで最も大きかった値を記憶している変数absx_maxと今回計算された変数absxの大きい方が、入力ベクトル大きさの最大値として変数absx_maxに入力されるということになります。

次に、yの絶対値を学習中のパーセプトロンの超平面パラメータの修正に使用するのでその部分をこれまでの入力ベクトルが内側か外側かという判定用の変数flagの宣言の後に変数absyを宣言しています。下に該当部分を抜き出しています。

// トレーニングデータを入力したときのパーセプトロンの出力
boolean flag;
// 入力ベクトルと計算中のパーセプトロンの超平面との距離の絶対値
double absy;
// 修正のための符号を付けた入力ベクトルと計算中のパーセプトロンの超平面との距離
double y;

ここでは同時に、後で変数absyの値に、どちらの向きに修正するかということの符号を付けた値を記憶する変数yも宣言しています。一方で、変数yに、どちらの方向に修正するかということも記憶することにしたため、以前あった変数sgnは変数yに吸収された形で消滅しています。

これら変数の宣言の後、学習結果にミスが無くなるまで学習を行うというための一番外側のdo ~while()構文がはじまります。さらに、その一つ内側の全ての学習用データ使うためのfor文があるところも以前のプログラム1と同様です。

ただし、その後、入力が学習中のパーセプトロンの内側か外側かを記憶する変数flagに値が入るところまでは同じですが、その下に距離(yの絶対値)を変数absyに入力する部分が挿入されています。(該当部を下に抜き出しています)

for (i = 0; i < PARAMS.TRANING_DATA_NUMBER; i++) {
// パーセプトロンの超平面の内か外かを判定
flag = checkInputData.check(splane, tdata.x[i]);
//距離yを得る(上記のflagの計算の時に計算されているものを持ってくる)
absy=Math.abs(checkInputData.getY(splane, tdata.x[i]));


ここでは、同じクラスの別のメソッドをgetYを使っています。実は、その上の行で使われているcheckというメソッド、その処理の中でこのgetYメソッドを判定に用いています。

ところで、このメソッドgetYで得られた値が負であることと、教師信号と学習中のパーセプトロンで超平面の内か外かということが一致しないこととは同一ではありません。そこで、メソッドgetYで得られた値は絶対値のみを使うことにして、符号は、学習が成功失敗かというチェックの後、失敗の処理をするときに下のような形で付けることにしています。

if(!flag)
// 重みベクトルやバイアスの修正をするときにはyの絶対値分値を増やす
y = absy;
else
// 本当は内側
// 修正のときyの絶対値分、値を減らす
y = -absy;

ここまでが主なプログラムの修正の部分で、あとは、次のように、学習中パーセプトロンの超平面のパラーメータの補正を変数yを利用した形にしてしまえば、終了となります。

// 重みベクトルの修正(for(j=0...for文で)
for (j = 0; j < PARAMS.INPUT_NODE_NUMBER; j++) {
// 重みベクトルを修正
splane.w[j] = splane.w[j] + y*tdata.x[i][j]* PARAMS.MARGIN_H;
}// end for(...

//  バイアスデータの修正:重みデータと同じく
splane.b = splane.b + y*PARAMS.MARGIN_H * absx_max
* absx_max;

では、以前と同じように、学習結果の一例を挙げてみましょう。ここで、学習率ηを表わす変数PARAMS.MARGIN_H=1としています。

 トレーニングデータの超平面パラメータ
 w0=0.47749051088214955
 w1=0.4836372397113169
 w2=0.8900003656198667
 w3=0.359925073478623
 w4=0.9232138025880994
 b=-1.197057368073004

学習結果
 学習後のパーセプトロンの重みベクトルとバイアス
 w0=1.3009984557359189
学習後データ/トレーニングデータ=2.724658241547801
 w1=1.215038025678252
学習後データ/トレーニングデータ=2.512292118786197
 w2=2.3719841357120437
       学習後データ/トレーニングデータ=2.6651496194161743
 w3=0.9192196644433451
       学習後データ/トレーニングデータ=2.5539195020764236
 w4=2.403287382704314
       学習後データ/トレーニングデータ=2.6031753164511167
 b=-3.1585261511612073
       学習後データ/トレーニングデータ=2.6385754228686062

収束は、以前のプログラムよりもかなり早くなったと思います。もっともこれはこのプログラムの学習率の大きさにもよりますけどね。

最後に、この学習用クラスを利用される場合に一つだけ注意点を書いておきます。この学習プログラムでは、学習中のパーセプトロンの超平面パラメータを初期化するときに全て0にするのは避けて下さい。入力ベクトルに何を入れてもcheckInputData.getYメソッドで0という結果が帰ってくるため、y=0即ちパラメータの修正値も0となってしまい、無限ループに陥ることになってしまいます。老婆心ながらご忠告申し上げる次第。私は、バイアスbの初期値を0.1としています。この値に特に根拠は無くy=0となる無限ループに陥らないような初期値なら何でも良いと思われます。ご参考まで。


プログラム2

/**
 * パーセプトロンのトレーニング(Novikoffの定理証明型)の為のクラス
 * 
 * @author hondaetsurou
 */

/** 
 * メンバ
 *         フィールド splane メソッド training
 * 
 *       フィールド splane パーセプトロンが学習した後の超平面のパラメータ構造体 super_plane型の構造体変数
 * 
 *       メソッドtraining super_plane型 返値 splane パーセプトロンのトレーニングを行う
 * 
 */

public class trainingPerceptron {
// 重みベクトルとバイアスを持つ構造体クラスsuper_planeをパーセプトロンの学習にも使う
static super_plane splane = new super_plane();

/*  学習  */
static super_plane training(training_data tdata) {

// パーセプトロンの出す答が間違っているときのトレーニングデータの数
int missed = 0;
// ループカウンタ
int i, j;
//  あるトレーニングデータの組の中で距離の絶対値が最大の値を記憶する変数(バイアスベクトル修正用)
double absx_max=0;
double absx;  //入力のベクトルの距離の絶対値の計算用
for (i = 0; i < PARAMS.TRANING_DATA_NUMBER; i++) {
//i番目のトレーニング用入力データの原点からの絶対値を計算する
absx=0;
for (j = 0; j < PARAMS.INPUT_NODE_NUMBER; j++) {
absx=tdata.x[i][j]*tdata.x[i][j];
}
//大きい方をabsx_maxとする
absx_max=Math.max(absx,absx_max);
}
absx_max=Math.sqrt(absx_max); //最後に一番大きいものだけの平方根を取ると距離が得られる
// トレーニングデータを入力したときのパーセプトロンの出力
boolean flag;
// 入力ベクトルと計算中のパーセプトロンの超平面との距離の絶対値
double absy;
// 修正のための符号を付けた入力ベクトルと計算中のパーセプトロンの超平面との距離
double y;

// トレーニングデータによる学習
do {

// 変数の初期化
missed = 0;

for (i = 0; i < PARAMS.TRANING_DATA_NUMBER; i++) {
// パーセプトロンの超平面の内か外かを判定
flag = checkInputData.check(splane, tdata.x[i]);
//距離yを得る(上記のflagの計算の時に計算されているものを持ってくる)
absy=Math.abs(checkInputData.getY(splane, tdata.x[i]));
if (flag!=tdata.t[i]) {
// トレーニングデータと答えが違うとき
missed++; // 失敗の数の変数をインクリメント
// 超平面の重みベクトルととバイアスを変える

if(!flag)
// 重みベクトルやバイアスの修正をするときにはyの絶対値分値を増やす
y = absy;
else
// 本当は内側
// 修正のときyの絶対値分、値を減らす
y = -absy;

// 重みベクトルの修正(for(j=0...for文で)
for (j = 0; j < PARAMS.INPUT_NODE_NUMBER; j++) {
// 重みベクトルを修正
splane.w[j] = splane.w[j] + y*tdata.x[i][j]* PARAMS.MARGIN_H;
}// end for(...

//  バイアスデータの修正:重みデータと同じく
splane.b = splane.b + y*PARAMS.MARGIN_H * absx_max
* absx_max;

}// end if
}// end for(i...
System.out.println("missed"+missed);
} while (missed > 0);
return splane;
}

}

2011年5月4日水曜日

番外編2 Novikoffの定理 その3


Novikoffの定理の証明の2回目です。

今回は、テキストで言う[二つ目の不等式]の説明をします。

さて、まず、ノルムという概念を説明しましょう。これは、数学の専門用語で、簡単に言ってしまえば、以前説明した距離(ユークリッド距離)と同じ意味です。距離は次のように定義されているのでしたね。


ベクトルの大きさと思ってもらえば結構です。わざわざノルムと言い換える理由は良く分かりませんが、数学は抽象化を目的とした学問でもあるので、より抽象化された言い方になっているのだと思います。

さて、下の不等式では、ノルムの二乗が使われていますが、二乗をすると、ノルムの定義式からルートが取れますよね。あと、二乗されると、その式の符号が必ず正になります。そのような意味もあって二乗が使われているのだと理解して下さい。(数式の図が小さいときはクリックで拡大します)



これら二つの不等式を使うと、下のような不等式が出てきます。少し見にくいですが、解説も数式の図に書いています(Webでの表記上の問題です)。ちなみに下の不等式の第一項と第二項の関係は[二つ目の不等式]を、まず一つ目と同様にt回演繹した不等式を作り、そのあとその両端を平方根を取った関係です。





この不等式はその両端の項の関係とwtwoptを正規化したベクトルであるとしたことから、失敗の回t上限が次のような不等式で表せることを示唆しています。

       

これは、すでに書いているようにwoptが正規化したベクトルであること、拡張した時に付け加えられる新たな次元の数bopt/R1であることを利用しています。つまり

w’opt‖‖w’opt‖≦‖wopt‖‖wopt‖+1≦2

となることを利用しています。

以上、証明終わり

2011年5月3日火曜日

番外編2 Novikoffの定理 その2




Novikoffの定理の証明に入ります。テキストp.18-19に相当する部分をできるだけ分かりやすく説明します。ただし、テキストと異なり、Webでの文章の表記の問題と説明の都合上、ベクトル行列転置について説明せず、また、後に出てくる拡張入力ベクトルをxi、拡張重みベクトルをwtと表記することにします。

※このブログの性質上、正確さよりもわかりやすさを優先するためです。ご専門の方や高度な教育を受けられている方にはご不満もおありでしょうが、ご理解頂きますよう宜しくお願いします。

まず、入力ベクトルxiを1次元増やしRというデータを付け加えます。入力ベクトルはn次元のデータでしたが、このRを付け加えた新しい入力ベクトル(これをxiとしましょう)はn+1次元のベクトルとなりますよね。これを、拡張入力ベクトルと呼ぶことにします。拡張入力ベクトルは入力ベクトルxiを使って表記すると、次のように表せます。

    xi’=((xi1,xi2,………,xin),R)
     (注:数学的には正確な表記でありませんが、
        意味的には理解できると思われるのでこの表記にします)

同じように重みベクトルwに関しても一次元増やし、そこにはバイアスbを取り入れ次のように拡張することにし、これを拡張重みベクトルw’と呼ぶことにします。

    w’=((w1,w2,………,wn),b/R)
     (注:xi’と同様に数学的には正確な表記でありませんが、
        意味的には理解できると思われるのでこの表記にします)

また、t回目の失敗により、補正された拡張重みベクトルをwtと表わすことにします。一つ前の拡張重みベクトルはwt−1と表わされ、これから、t回目の失敗の時に修正される値は、関数マージンの定義、

     γi=yi (<wxi>+b)=yi <w’xi>

を用いて、次のように修正されるとします。

  wt’ =wt−1’+η|yi <w’xi>| (ただしηは学習率を表わす)


この修正の式の意味は、t-1回目で入力ベクトルxiで関数マージンyiが負ならば、失敗という事であるので、拡張重みベクトルを(η|yi <w’xi>|)分、正の方向に増やしておけば、t回目で同じ入力が入ったときに、関数マージンyiが0以上に成り、正しく分類されるだろう、ということを表わしています。拡張重みベクトルには、バイアスも含まれていますので、当然バイアスに関しても修正されます。


(注:ここでは、xi’=((xi1,xi2,………,xin),R)w’=((w1,w2,………,wn),b/R)を使って展開して問題ないということの証明は省きます。まずは、およその流れを理解することを主眼にしたいからです。

 また、以前(パーセプトロンの学習アルゴリズムの回)に紹介したプログラムとは重みベクトルの修正の仕方が違いますが、今回の証明で使われる修正のやり方に基づいたアルゴリズムのプログラムは証明の説明が終わった後、改めて説明します。)

上記の式と、トレーニングデータの元々の超平面の拡張重みベクトルwoptとの内積を取ると修正されるときは、マージンyiが負の時、つまり、パーセプロンが出す答えが失敗したときで、最大マージンγがトレーニングデータの超平面とトレーニングデータの集合Sとの間の最も小さいマージンであった、ということを思い出して頂くとと次のような不等式が得られる事が分かると思います。

    <wtwopt> = <wt-1wopt >+η|yi <xiwopt>|
  <wt-1wopt > + ηγ
  <wt-2wopt > + ηγ + ηγ
  ………
  <w1wopt > + (t-1)ηγ
tηγ

   2011/05/04:一行目の等式の右辺第2項が間違っていた為、
    修正しました。)

   
テキストに習って、これを、[一つ目の不等式]と呼びましょう。

つぎに、[二つ目の方程式]というものを説明し、この二つを使って、最終的に修正の回数の上限が求められるのですが、ここまでやや難解で長くなったことを考慮して、証明を二度に分けて説明しようと思います。どうぞご了承下さい。

以上、次回は[二つ目の方程式]から最終的な結論までの説明となります。

2011年5月2日月曜日

番外編2 Novikoffの定理 その1

番外編2 Novikoffの定理 その1
線型分離可能であるようなトレーニングデータがパーセプトロンの学習段階でどれくらいの失敗(言い換えれば、重みとバイアスを書き換える)回数があるかということを示すNovikoffの定理を今回と次回に分けて説明します。今回は定理の説明だけを簡単にして、次回は、証明を説明しようかと思います。証明はどうしても長くなりがちなので2回に分けることにしました。そのあと、この定理の証明で行われているようにあらためて、パーセプトロンの学習方法のプログラムを若干修正して、そのときにうまく学習できているかどうかを示します。

ネットでちょっと調べると、収束定理と言っているサイトもあります。その名の通り、トレーニングデータが線型分離可能であるならば、パーセプトロンの学習はNovikoffの定理で示されるように必ず収束することが保証されている、と考えることもできます。

それでは、実際の定理を見てみましょう。



(注:図が小さい場合は、図をクリックすると拡大されます)

まず出てくるRですがこれは、原点を中心にトレーイングデータの集合Sのばらつきをみて、最も離れている入力データの距離としています。woptは正規化されたトレーニングデータの超平面と考えて良いでしょう。トレーニングデータの超平面とそれに最も近いトレーニングデータまでの距離である最大マージンをγとしたときに、パーセプトロンの学習は2Rγとの比の2乗の失敗の回数以内に収束する、という言い方で、言い換えられるのがこの定理です。

それでは、次回は、証明です。


2011年4月20日水曜日

番外編 ベクトルとか内積とかユークリッド距離とか正規化とか


単純パーセプトロンがn個の入力を持つとき、入力と重みベクトルにはn個のパラメータがあり、その内積を云々とか平気で書いていますけど、もう少しだけ詳しく説明しましょう。
まず、ベクトル。これは、長さと方向を持つという説明をしました。n個のパラメータを持つということは言い換えればn個の座標軸を持つベクトル空間によって表現されるわけです。
3以上のn個の座標軸を持つ空間のことを普通n次元空間という言い方をしますね。0次元が広がりを持たない点、1次元が線、2次元を面とかあるいは2次元から、2次元空間ともいったりもしますが、元々は3次元を空間ということの拡張(つまり縦横高さでどれか一つが0(通常高さ))と考えられます。我々の基本的な認識能力は3次元の空間であり、それ以下もそれ以上も空間の延長という形でしか我々は表現できないということかも知れません。
ところで、ベクトルはn次元空間においてもやっぱりベクトルと言いますよね。これは、ベクトルは2次元の時は二つの座標で原点からの距離と向きを決定することができる。これを3次元、そしてn次元へと拡張しても全く同様に考えられるということからベクトルは同様の概念でベクトルだと考えられる訳ですよね。
さて、超平面はどうして超平面に垂直な法線ベクトルと入力の内積で考えられるのでしょうか。内積とはなんなのか。
少しずつ考えていきましょう。まず、n次元空間のベクトルはn個の座標で原点からの距離と向きを表現できるのでした。たとえば、2次元で考えればx座標とy座標で表現できるのですね。これは、我々が平面を俯瞰できるからそのように考えるのであって、例えば、ある港から船でどこか魚釣りのポイントを目指しているなら方角と距離を指示してもらわないとたどり着けないでしょう。

つまり、ベクトルには地図を見るように座標を示す示し方と、船に乗って海のどこかへたどり着こうとするとき場合のような基準から角度と長さを示す示し方と二通りあるわけです。(え?今時ならGPSあるだろって?そ、それは………)
しかし、3次元をこえたn次元空間で角度と距離なんて我々には想像もつかないからn個の座標で言うわけですが、言い方を変えれば、長さと角度(方向)のある一本の棒はn個の基本的なベクトル(単位ベクトルという)、例えば2次元ベクトルx(x1,x2)だったら(10)と(01)で表せる二つの単位ベクトルのそれぞれ、x1倍、x2倍と考えることもできます。あるベクトルxは基本ベクトルの合成されたものして考える訳です。

逆に、ベクトルxを単位ベクトルに分解することもできる。それが内積というものです。つまり、ベクトルx(x1,x2)x座標のみの単位ベクトル(10)の内積を取れば(x1,0)というベクトルが得られます。見方を変えれば、ベクトルx(x1,x2)をx軸に写像したものが内積という見方もできるでしょう。

では、どうして、超平面の方程式は入力ベクトルと法線ベクトルとの内積で表せるのでしょう。

まず、超平面上にある点があると言うことは、例えば、

w1x1+w2x2+………+wnxn+b=0  
という方程式が成り立つと言うことですよね。つまりは0になると言うことが大事なわけです。ところで、超平面に垂直な線は超平面に写像したとき大きさはないでしょう?大きさ0。実際はバイアスbがあるので少し話はややこしいですが、例えば、原点を通るような超平面は、

  w1x1+w2x2+………+wnxn=0  
で、これが原点からbだけ平行移動したものが求める超空間の方程式となるというわけです。従って、上記のような方程式がベクトルの内積を使うとすごく簡単にwx+b=0と表せるというわけなのです。
このような内積を定義できる空間のことをユークリッド空間と言います。難しい言い方ですが、単に直交座標系が成り立つ空間、と言って良いでしょう。

ユークリッド空間では、2つのn次元ベクトルa,bの距離(ユークリッド距離)は点aから点bへ向かうベクトルの大きさに等しく次のように定義されます。




最後に、正規化を説明しましょう。正規化とは、簡単に言えば、どんな長さも基準に対して相対的であるので、基準になるものが一番大きければ、全ては0から1の実数で表せるでしょう、と言うことです。例えば、直角三角形の斜辺の長さはほかの2辺より必ず大きいので、直角三角形の斜辺を基準とすれば、ほかの2辺は0から1の間の大きさで表せる、そういうことになりますよね。