ORる世界 [ゼロトラスト]
昨日の真打ちの方法で線形分離問題が解けると思って安心して寝たら夢のお告げで反例が見つかった、
しかし考察を重ねてついに完璧なアルゴリズムに到達すた、
記号
- d
- サンプルの次元
- x[i]
- i番目のサンプル
- b[i]
- i番目のサンプルのラベル（-1または+1）
- H
- ラベル+1のサンプルの集合
- L
- ラベル-1のサンプルの集合
前提
- H、Lともに要素に重複無し
- H∩L＝∅
昨日の真打ちの方法の反例
x1, x2∈H、y1, y2∈L、（簡単のため）x1、y1、x2、y2が全て同一平面上にあるとする。
位置ベクトルとして見たx1とy1の中点の位置ベクトルをm1、同じくx2とy2の中点の位置ベクトルをm2とする。
m1、x2、m2を結んでできる3角形に対し、y1が内側、x1が頂点m1をはさんで反対側の外側（三角形の辺m1-x2の延長線と、辺m1-m2の延長線に挟まれた領域）にあるとする。
昨日のエントリのアルゴリズムに従い中点m1、m2を通る（超）平面を識別面とすると、x1、y1がともに誤識別となるためアルゴリズムの約束に従い「線形分離不能」で終了する。
しかし、実際には中点m1とx2を通る（超）平面によって、x1、y1も線形分離できる。
つまり昨日のアルゴリズムは線形分離可能なケースを見逃すことがある。
昨日の真打ちの方法の修正版、
中点に注目するのはやめてサポートベクトル（的なベクトル）に注目汁、
もうHとLの元のペアを考えたり、内積 < x1, y1>の大きさの順でソートするのはやめゆ。
識別面にぴったり乗るサンプルの存在を、Lのみについて認め、Lに接する識別面のみを探す。
（HとLを線形分離する識別面は何であれ線形分離する状態を保ったままLと接するまで平行移動できるので、そうしても一般性を失わない。）
以下、超平面wに接するLの元をwのサポートベクトルと呼ぶ。
この約束の下で、調整中の識別面w(t)は、常に1個以上のサポートベクトルを有することになる*1。
いま、識別面w(t)でHの全要素と、Lの一部（y(1), y(2), ..., y(t)）が正しく識別（線形分離）できているものとして、Lに含まれるt+1個目のベクトルy(t+1)が識別できているか確かめる。
w(t)でy(t+1)が正しく識別できてれば、w(t)をそのままw(t+1)としてLの次のベクトルy(t+2)の識別確認に進む。
w(t)でy(t+1)が正しく識別できていなかったら、w(t)のサポートベクトルがs(1), s(2), ..., s(m)のm個だとして、次に従う。
- m < d-1なら、{ s(1), s(2), ..., s(m) } に y(n+1) を加えたベクトルをサポートベクトルとする識別面w_0 で（Hの全要素とy(1), y(2), ..., y(n), y(n+1)を）正しく線形分離できるか試す。線形分離できればw_0 をw(t+1)としてy(t+2)の識別確認に進む。
- s(1), s(2), ..., s(m)から1個抜き、 y(n+1) を加えたベクトルをサポートベクトルとする（つまりサポートベクトルを交換した）識別面w_1（m通り） で正しく線形分離できるか試す。線形分離できればw_1 をw(t+1)としてy(t+2)の識別確認に進む。
- 線形分離できないままここまで来たら、線形分離不能として終了する。
y(t+2)が無い（Lの全要素と、Hの全要素を正しく識別し切った）なら、そのときのw(t+1)で線形分離成功として終了する。
なお、y(n+1)をw(t)のサポートベクトルs(1)～s(m)のどれかと交換すると、s(1)～s(m)の中に勝手にサポートベクトルでなくなるものが生じるので、そういったベクトルを外す操作は省略して良い。
（サポートベクトルでないベクトルは、外しても外さなくても識別面を変えず、線形分離結果に影響しない。）
そういったケース以外で、w(t)のサポートベクトルからわざと2個以上外すパターンを試さなくても良いのは、サポートベクトルを減らすことは識別面を規定する（重みを与える）連立一次方程式の式が減るということなので、サポートベクトルを減らす前の重み（線形分離失敗）も引き続き解に含まれるためである。わざわざ試さずとも、線形分離に失敗する解が含まれる以上、その方程式で求めた重みでは線形分離に失敗する。
y(1), y(2), ..., y(t)の選ぶ順序に依存しないのか？
HとLを正しく識別する識別面には、一般にサポートベクトルが異なる複数種類が有り得るが、どれかには必ず行きつく、
と思うが証明方法はわからん、、、
考え中
