思うだけで学ばない日記 2.0

思うだけで学ばない日記から移転しました☆!よろしくお願いします。

[AI]証明2.0

先日の証明は巨大な誤りがあり、入力ベクトルの部分空間への再帰的分割がまずいやり方でやったため、分割の都度部分空間別の重みセット一式が新たに必要になるというミスを犯してた*1;orz

しかし間違っていたのは証明方法だけであり、結論は変わらないのである。
GMA0BNに定理2.0は無い!(キリ

補題1: 要素数Bの0と1からなるベクトルの集合は、1の個数が同じかつ1の出現位置に共通部分と相違部分がある限り、任意の部分集合とその補集合に必ず線形分離できる

■ 証明
ベクトル内の1の個数が同じであることから、2つのベクトル間に1箇所相違があれば、もう一箇所0/1反転した相違箇所が必ずある。(相違箇所は必ず偶数。)
つまり、2つのベクトルv1とv0の最小の相違は次のように表せる。

列:        j     k
------------------------
v1 = ( [p] 1 [q] 0 [r] )
v2 = ( [p] 0 [q] 1 [r] )

ここで、[ ]という記号は要素列を表し、中の記号が同じアルファベットの[]同士は同じ要素の並びとする。(空の場合も許す。例えば[q]が空なら、j, k列は隣接していることを表す。)なお、左から右に見ていったときの1、0の出現順は逆順もありえるが、列を入れ替えても以下の議論は一般性を失わないので以下上記出現順をベースとする。

さて、適当に重みを与えた結果、識別面に対し、'1'にラベル付けされたベクトルが裏側、'0'にラベル付けされたベクトルが表側に来てしまうこと(誤識別)がある。
例えば、[p], [q], [r]の重みが全て0だとして、次のベクトルv10、v20はいずれも誤識別である。

列:                 j     k
------------------------------------
重みw_j, w_k:      -3     2
------------------------------------
       v10 = ( [p]  1 [q] 0 [r] )   : Labeled as '1'
       v20 = ( [p]  0 [q] 1 [r] )   : Labeled as '0'
--> 要素と重みの積和は以下となり、期待符合とは逆である。
        v1'が-3 * 1 + 2 * 0 = -3 < 0
        v2'が-3 * 0 + 2 * 1 =  2 > 0

こういったアウトライヤーを、他のベクトルにミソをつけることなく(誤識別に向かわせるバイアスを生じることなく)識別面の正しい側に移動させられたら問題解決する。

さて、v1とv2に戻り、j, k列要素がなす部分空間において最大限のマージンで識別することを考える。
v1とv2の要素のj列同士、k列同士をそれぞれ抜き出すと(1 0)^T, (0 1)^Tであり、両者は直交する(1 * 0 + 0 * 1 = 0)。ここで、([*])^Tはベクトル([*])の転置。
よって、v1とv2を次元j、kにおいて最大マージンで識別するのは、j-k空間を斜め45°にぶった切る平面*2である。
すなわち、法線ベクトル(-1 1)で表される平面であり、これが重みとして最善となる:

列:                j     k
------------------------------------
重みw_j, w_k:     -1     1
------------------------------------
        v1 = ( [p] 1 [q] 0 [*] )
        v2 = ( [p] 0 [q] 1 [*] )

次に、集合内の第3のベクトルv3との関係を考える。v1、v2に対して行った上記調整によって、v3にどのようなミソがつくか。
v3を、要素の伏字a, bを使って次のように書く。

列:                j     k
------------------------------------
重みw_j, w_k:     -1     1
------------------------------------
        v1 = ( [p] 1 [q] 0 [*] )
        v2 = ( [p] 0 [q] 1 [*] )
        v3 = ( [p] a [q] b [*] )

v3のj, k列の内容(a b)としては、次の4通りが有り得る:

  1. (a, b)=(0, 0) --> w_j * a + w_k * b = -1 * 0 + 1 * 0 = 0
  2. (a, b)=(1, 0) --> w_j * a + w_k * b = -1 * 1 + 1 * 0 = -1
  3. (a, b)=(0, 1) --> w_i * a + w_k * b = -1 * 0 + 1 * 1 = 1
  4. (a, b)=(1, 1) --> w_i * a + w_k * b = -1 * 1 + 1 * 1 = 0

それぞれの後ろに重み(w_j, w_k)と要素(a, b)の積和を書いた。1と4のケースはv3と識別面との関係を変えないため、v3の識別に関して中立である。すなわち、重みw_j、w_kは、v3の識別にミソをつけることなくひとまず決定された。

一方、2と3のケースは中立とは言い切れない。
まず2のケース(a, b)=(1, 0)をとり、仮定に戻って考えると、j, k列がv3とv1は一致、v3とv2は相違するため、v1との相違箇所(0/1反転)が少なくとも([*]内に)2列あるはずである。(さもなくば、v3はv1と一致してしまい、1の出現位置に相違があるという仮定に反する。)
このとき問題なのは、新たな相違箇所(s, t列の要素c, dとする)の重みがj, k列におけるw_j, w_kみたいにお行儀のよい値とは限らないということである。
例えば、s, t列の重みがたまたま(0, -1)だったりすると、j, k, s, t列の要素と重みの積和は

  w_j * a + w_k * b + w_s * c + w_t *  d
 = -1 * 1 +   1 * 0 +   0 * 0 +  -1 *  1 = -2

という具合で、このオフセットがv3を識別面の裏側に移動させるバイアスとして働き得るため、v3の識別に関して中立ではない。

どうするかというと、次を順次適用する。

  1. 上記オフセットの下でv3が正しく識別されているなら、何もしない。例えばv3が'0'にラベル付けされているなら、負のオフセット量-2は問題無い。
  2. 1が成立しなければ、バイアスと反対の符号をもつ項の重み(上の例ではw_k)の絶対値を、符号を変えずに増す。

2によって、v3のバイアスを任意にキャンセルし、マージンに転換できる。一方、これはj-k空間の識別面の法線ベクトル(w_j, w_k)がk軸に近づく=当該識別面が横に寝るだけであるため、v1とv2に関してはj-k空間の識別結果の符号は引き続きv1とv2が正しく識別される方向であり、新たなバイアスを生じない。

v1、v2、v3以外のベクトルについては識別結果に影響が出るが、その出方は、2の調整を行った列の重み(上の例ではw_k)の重みが0に近いことに依存して正しく識別されていたベクトルが、当該重みの絶対値増大の結果、識別面の反対側に移動する(要素と重みの全体の積和の符号が反転する)という形で現れる。

そのようなベクトルをv4とおくと、v4は、j, k, s, t列以外の列に1個以上値1の要素を有し、その列の重みがw_kと反対符号である。(さもなくば、w_kの絶対値増大によるオフセットはv4の全体の積和の符号を変えず、誤識別バイアスにならない。)さらに、1個以上値0の要素も有する。(j, k, s, t列内にあるか、さもなくば他の列にあると仮定せねば、値0の要素が現れたv1、v2、v3と1の数が相違してしまう。)よって、v4もまた、上記2の調整により、バイアスを任意にキャンセルできる。(拮抗するところまでは少なくとも可能)

よって、存在が仮定されている1の出現位置の共通部分(v3とv4の間にも存在する)の重みを通して、正しく識別されているベクトルのマージンをわずかに取り崩してバイアスのキャンセルを分担させることにより、v4についても2の調整を完了させられる。

■ 証明終わり

補題2: 要素数B+1の0と1からなり1の個数が同じかつ末尾要素が1のべクトルの集合は、任意の部分集合とその補集合に必ず線形分離できる

■ 証明
'1'とラベル付けされたベクトルv1と、'0'とラベル付けされたベクトルv2は、1の出現位置に必ず共通部分があるから、補題1により線形分離できる。
(前半B要素の全てが0/1反転の関係にあっても、末尾1要素が1であることから、共通部分の存在が保証される。)

■ 証明終わり

というわけで、○棋の局面を表す集合Pは任意の部分集合とその補集合に線形分離可能であるから、先のエントリの証明のとおり、(1次元拡張した)KP式の評価関数×289個の表現能力は○棋の完全解析結果を記憶するのに十分であることは確定的に明らか、

電波リプ

クイックソートの最悪の計算量がO(N*log(N))であることをもって、○棋の完全解析結果記憶する(任意の順序に解釈する)手間がO(log(N))で済むはずがないという批判は2つの誤謬を含んでゐる、

  1. 任意の順序に解釈するというのは並べ替えではなく検索のアルゴリズムである。後者であれば、例えばN語のRAMのアクセス1回の手間はO(log(N))で済む。
  2. 当手法においても、パーセプトロンの識別面の設定過程(検索器の設計にあたる)においてO(N)を超える計算量が必要であるから、全体を見れば計算量は不合理なまでに小さいわけではない。(ただし補題2は、現実に遂行可能な計算量でありうることを示唆している。)

また、検索のアルゴリズムといえども検索対象N個を「任意の順序で」解釈するには高さlog(N)の2分木が必要であり、順序の大小比較器がそのノード数分必要なのではないか(よって記憶の手間がO(log(N))で済むのはおかしい)とまで考えた人はある意味鋭いのかもしれないが、今回の場合は高さ1の2分木が289個並ぶだけの話であり、批判はあたらない。

いじょ

*1:これでは結局高さlog2(B)の二分木の全ノード数のオーダーで記憶が要るから全く空間の省略にならない

*2:といってもこの場合直線だが…