Hatena::ブログ(Diary)

思うだけで学ばない日記

2018-03-18

[]数値的に安定な線形分離方法 22:24

早速だがn次元特徴ベクトルx=(x_1, x_2, ..., x_n)が次の識別平面(n-1次元の超平面)で線形分離さるるとす:

    nx + b = 0  ・・・ (1)

ここでn識別平面の法線ベクトルであり、ここではnの要素表示を次の通りとする。

    n = (w_1, w_2, .., w_n)

式(1)は、nxを1次元拡張して、n+1次元ベクトル

    n = (w_1, w_2, ..., w_n, b) ・・・(2)
    x = (x_1, x_2, ..., x_n, 1) ・・・(3)

と再定義することにより

    nx = 0    ・・・(4)

と書ける。以下この式(4)の形式を使う。ここまでは導出方法はともかくだいたいどんなAI教本にも書いてある

で、式(3)の最後の次元の要素は1のままで本当に良いのか?というのが本日のお題だる。

結論は、カナーリマズー、である

式(4)に式(2), (3)を代入すると

       w_1*x_1 + w_2 *x_2 + ...+ w_n*x_n + b = 0
    ∴ x_i = ((w_1*x_1 + w_2 *x_2 + ...+ w_n*x_n + b) - w_i * x_i) / w_i
           = -(w_i * x_i) / w_i
    ∴ ∂x_i/∂w_i = w_i * x_i / ((w_i)^2)  ・・・(5)

を得るが、式(5)が言わんとするところは、(拡張された)特徴ベクトル空間を寸法dのn+1次元長立方体で区切って量子化するという想定の下で、法線ベクトルnや特徴ベクトルxの要素が全て幅dで量子化されるのに対し、nで決まる識別面の分解能が、|w_i|が小さくなった(=拡張された法線ベクトルnがx_i軸に近づいた)とき、たちまち

    |∂x_i/∂w_i|*|d| = |w_i * x_i / ((w_i)^2)|*|d| >> d

に劣化するということだる*1
これは特徴ベクトルxの線形分離性能に重大な影響を与う。

全てのi (i=1..n)について|∂x_i/∂w_i|≦1にする方法はあるか?-->これは無い。しかし、分解能が問題になるのは、識別面に対して直交する方向だけである。識別面に平行な方向については、いくらxの分解能が劣化しても識別結果に影響を与えない。

では識別面に対して直交する方向について、|∂x_i/∂w_i|≦1にする方法はあるか?-->ある! 式(3)におけるn+1次元目の「1」の調整で、nn+1次元目の軸に対するもともとの傾き(重要)を45度まで増幅(あるいは減衰)すればよろしいい*2

式(3)における「1」を「α」(α>0)に置き換えた

    x' = (x_1, x_2, ..., x_n, α)   ・・・(6)

とゆー特徴ベクトル'を考ゆる
今は特徴ベクトル識別面のどっちにあるか精密に識別する様が見たいので、もとの式(3)がぴったり識別面上にあったとしよう。
で、式(6)は要素表示をやめると次のように書ける、*3

    x' = x + (α-1)*((xe_p)e_p)   ・・・(7)

ここで「・」は内積e_pは、もともとの特徴ベクトルになかった第n+1次元の正規直交基底ベクトル

x'は、もともとの特徴ベクトルになかった第n+1次元を弄っただけなので、もともとの特徴ベクトルの情報(n次元)を完全に保持していることにちういせよ、

一方、式(7)に対応する(式(7)を識別面上の点とする)法線ベクトルは次式である

    n' = n + (α-1)*(n - (ne_p)e_p)
       = α*n - (α-1)(ne_p)e_p    ・・・(8)

■ 証明:

n'・x' = α(xn)。よって、xn = 0ならn'・x' = 0。逆も真。

とゆーわけで、式(8)を軸e_pに対して45度傾ければ(そうなるようなαを選択すれば)よろしいい。

すわなち、

       (n'/|n'|)・e_p = 1/√2
    ∴ 2 * (n'・e_p)^2 = n'・n'
    ∴ α = √{ (ne_p)^2 / (|n|^2 - (ne_p)^2) } ・・・(9)

なのだる、

なお、式(8)の右辺を見たらワカル通り、n'はもとのnの約α倍される。ただし法線ベクトルnn'は方向だけが意味を持つから、α倍したからといってn'の分解能が(dであって欲しいところが)α*dになる、とかそういう問題は起きない。むしろ|n'|はオーバーフローを起こさない範囲で大きいほうが分解能的には良い(ハズ、

■ 実装

上で「n+1次元目の軸に対するnのもともとの傾きを45度まで増幅すればよろしいい」と書いたがこれはnを変更して識別面を動かす都度行う。

識別面を動かすとは、例の誤差ベクトルを足しこむ処理においてということであり次の手順とする:

  1. 法線ベクトルn'と前回使ったαの値が既知とする。
  2. foreach ((x, label) ∈ { 学習データ })
    1. xの第n+1次元の要素をαに置換してx'を求める
    2. ipr := (n'・x')
    3. if (iprとlabelの符号が相違) {
      1. n'' = n' + (iprの符号)*(n' - x')
      2. n''から式(9)に従い新しいαを求める
      3. n' := n''
    4. }
  3. }

いじょ

*1:式(5)の右辺の分母はw_iの二乗なので、|w_i|が微小になれば莫大な量になる

*2:図を1枚貼れば幾何学的意味と正しさが一目瞭然なのだがそれをするには余白がせますぐる、

*3:図を1枚貼れば以下略