■
[AI]証明3.0~どうだ明らかになったろう~
証明2.0は小難しく考えすぎたためほとんどたわごとと化していたので直す……!
実は今考えているベクトルの集合は非常に素性の良いブツであり、目的の定理は実は全く簡単に示せるのである。1つの列の重み調整で生じる他の列への影響の限界について、せいぜいもう3列追加でトレースしただけで結論が出せる。
というわけで、やっぱ証明方法がまずかっただけであり、結論は変わらないのである。GMA0BNに定理2.0は無(ry*1
補題1: 要素数B+1の0と1からなるベクトルの集合は、1の個数が同じでありかつ末尾要素の値が共通の値である限り、任意の部分集合とその補集合に必ず線形分離できる
■ 証明
ベクトル内の1の個数が同じであることから、2つのベクトル間に1箇所相違があれば、もう一箇所0/1反転した相違箇所が必ずある。(相違箇所は必ず偶数。)
つまり、2つのベクトルv1とv0の最小の相違は次のように表せる。
列: j k ------------------------ v1 = ( [p] 1 [q] 0 [r] ) v0 = ( [p] 0 [q] 1 [r] )
ここで、[ ]という記号は要素列を表し、中の記号が同じアルファベットの[ ]同士は同じ要素の並びとする。(空の場合も許す。例えば[q]が空なら、j, k列は隣接していることを表す。)なお、左から右に見ていったときの1、0の出現順は逆順もありえるが、列を入れ替えても以下の議論は一般性を失わないので以下上記出現順をベースとする。
で、天下りだが上記j, k列に次のように重みを与えてみる:
列: j k ------------------------------------ 重み: 1 -1 ------------------------------------ v1 = ( [*p] 1 [*q] 0 [*r] ) v0 = ( [*p] 0 [*q] 1 [*r] )
ここで、記号[* ]は、列数のみ同じで、要素の並びが同一とは限らない要素の並びを表し、中の記号が同じアルファベットの[* ]同士は同じ列を占めるものとする。
すると、v1、v0とも(j-k部分空間において)識別面からのマージン=-1/√2
これらv1のマージンは、重みw_jの正数倍によって任意に増やせる(他方は減少する)。反対も同様で、v0のマージンは、重みw_kの正数倍によって任意に増やせる(他方は減少する)。また、w_jとw_iを同時に増やせば、v1、v2のマージンも同時に増す。これを以下j-k基本調整、当該調整が成立するj, k列の要素のパターンを基本調整成立パターンと呼ぶ。
申し遅れたが、v1、v0はそれぞれ'1'、'0'とラベル付けされているものとする。すなわち、v1が識別面の表側、v0が裏側に来れば識別完了となる状況を想定している。
(例えば、[p]、[q]、[r]部分の重みが仮に0なら、上記v1, v0は識別完了である。)
次に、j列、k列の隣に来る要素のパターンを考える。それらを伏字a, b, c, dで表すと、次のように書ける:
列 j j+1 k k+1 ---------------------------------------- v1 = ( [*p] 1 a [*q'] 0 c [*r'] ) v0 = ( [*p] 0 b [*q'] 1 d [*r'] )
このとき、(a, b, c, d)の組み合わせ別に、次の調整が可能である。
No. a b c d 追加で可能な調整 ------------------------------------------------------------------------ 0. 0 0 0 0 なし(j-k基本調整が全て) 1. 0 0 0 1 w_(k+1)を負数とすることでv0のマージンを任意に増やせる。 2. 0 0 1 0 w_(k+1)を正数とすることでv1のマージンを任意に増やせる。 3. 0 0 1 1 w_(k+1)により片方のマージンを増やし、他方を減らせる。 4. 0 1 0 0 w_(j+1)を負数とすることでv0のマージンを任意に増やせる。 5. 0 1 0 1 No.4とNo.1のmix 6. 0 1 1 0 No.4とNo.2のmix 7. 0 1 1 1 No.4の調整(v0のマージン増)+ No.3の調整 ※1 8. 1 0 0 0 w_(j+1)を正数とすることでv1のマージンを任意に増やせる。 9. 1 0 0 1 No.8とNo.1のmix 10. 1 0 1 0 No.8とNo.2のmix 11. 1 0 1 1 No.8の調整(v1のマージン増)+ No.3の調整 ※2 12. 1 1 0 0 w_(j+1)により片方のマージンを増やし、他方を減らせる。 13. 1 1 0 1 No.12の調整 + No.1の調整(v0のマージン増) ※3 14. 1 1 1 0 No.12の調整 + No.2の調整(v1のマージン増) ※4 15. 1 1 1 1 No.12とNo.3のmix ※5
No.3とNo.12の調整は、w_(k+1)やw_(j+1)の調整によりv1とv0が識別面に対して同方向に動いてしまうので一見厄介だが、j-k基本調整によりv1とv0のマージンを任意に増減できる状況なので、実は問題にならない。(そのような列のw_(k+1)やw_(j+1)は0でも最悪問題無い。ただし、ラベル'1'とラベル'0'とでベクトルの個数に大差がある場合、v1とv2に共通のオフセットを与えたほうがw_kとw_jのダイナミックレンジを押さえ得る*2。)
まとめると、j, k列の要素がj-k基本調整成立パターンである限り、j, j+1, k, k+1の4列だけで識別面からの任意のマージンをv1とv0に対し独立に付与できる。さらに、重みの絶対値の増加のみでマージンを任意に増加し得る。
識別面からのマージンは、増やす分には線形分離に関して何の害もないことに注意しよう。j, j+1列を共有する次の3ベクトルの線形分離も、k+1列とk'列が重ならない限り、また上と同じ議論で成立する。
列: j j+1 k k+1 k' k'+1 -------------------------------------------------------- v1 = ( [*p] 1 a [*q'] 0 c [*r''] 0 c' [*r'''] ) v0 = ( [*p] 0 b [*q'] 1 d [*r''] ? ? [*r'''] ) v0'= ( [*p] 0 b' [*q'] ? ? [*r''] 1 d' [*r'''] )
ここで、?という記号は、0か1の任意の値を意味する。また、v0'は'0'とラベル付けされたベクトルとする。
j, k'列はj-k'基本調整成立パターンであるからv1とv0'は線形分離可能であり、v1とv0'のマージンを重みの絶対値の増加のみで任意に増加させられることから、j, j+1列の重みの絶対値を減少させない形でj, j+1, k', k'+1列の重みを調整すれば良い。
k+1列とk'列が重なる場合はどうするか?これは、重みw_(k+1)(=w_k')について、v1-v0の分離が要請する符号と、v1-v0'の分離が要請する符号が同一の場合は上の議論により問題無いと言える。(重みの絶対値を増加させて調整可能。)
2つの分離が要請する符合が相違する場合は、v0とv0'がともに'0'とラベル付けされているため、基本的には有り得ない。(重みw_(k+1)(=w_k')は負数一択。)例外として、j, j+1, k, k+1列の調整におけるNo.3かNo.12に該当し、全体をシフトさせたときは異符号が要請され得るが、その場合はシフト量の方を調整すれば同符号(負)にできる。(または最初からシフトさせなければ良い。)
ではさらに、k, k+1列とk', k'+1列がぴったり重なるケースはどうするか?これは、仮定よりv0、v0'は要素の並びに必ず相違があるため、v0'においてぴったりとは重ならない別のk', k'+1列を(直下に述べるケースを除き)必ず見出し得るから回避可能。
残るは…k'列がベクトルの末尾にあたり、k'+1列が存在しない場合はどうするか?これを避けるために、ベクトルの末尾に、同じ値の要素を追加しておけば良い。値は0でも良いが、1にしておけば、重みw_(k'+1)で全体のシフトに役立つ。
■ 証明終わり
というわけで、○棋の局面を表す集合Pは任意の部分集合とその補集合に線形分離可能であるから、先のエントリの証明のとおり、(1次元拡張した)KP式の評価関数×289個の表現能力は○棋の完全解析結果を記憶するのに十分である。
いじょ
*1:『証明がまずかったり間違ったりしているものは「予想」であって「定理」ではない。訂正を要求する!』という強い電波を130億光年ぐらいの宇宙の彼方から受信したが、当ブログはGMA0BNが日々考えたことを(不定期に)報道するのが使命なので、彼がxを定理であると信じたならばその事実を報道することになんら間違いはないのである。
*2:w_kとw_jは1増やしても識別面に対するマージンが1未満増えるだけ(典型的には1/√2とか、あるいは最悪0に漸近)なのに対し、w_(k+1)やw_(j+1)は1足したらストレートに片方のマージンが1増す(他方のマージンは1減る)ので、識別面に対して全体をシフトさせたい場合はw_(k+1)やw_(j+1)による方が効率が良い。