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

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

ORる世界 [最終章]

昨日のアルゴリズミも盛大に間違いやったorz

なお、y(n+1)をw(t)のサポートベクトルs(1)~s(m)のどれかと交換すると、s(1)~s(m)の中に勝手にサポートベクトルでなくなるものが生じるので、

mがd-1以下であるかぎり全てのサポートベクトルがサポートベクトルのままで居られるから外れたりするベクトルは生じない。気のせい。

そういったケース以外で、w(t)のサポートベクトルからわざと2個以上外すパターンを試さなくても良いのは、サポートベクトルを減らすことは識別面を規定する(重みを与える)連立一次方程式の式が減るということなので、サポートベクトルを減らす前の重み(線形分離失敗)も引き続き解に含まれるためである。わざわざ試さずとも、線形分離に失敗する解が含まれる以上、その方程式で求めた重みでは線形分離に失敗する。

これも成立しない
式の数が減ったら重みベクトル=識別面の法線ベクトルがいろんな方向を取り得るということで、その中に正しい識別面が含まれない保証は無い

で、Lから採ったサポートベクトルを減らした結果自由な向きに向けるようになった識別面は何に制約されるかというと、Lの他のベクトルを正しく識別することと、Hの全てのベクトルを正しく識別すること、これに尽きる。
つまり、Lの上に一方的に勝手にとったサポートベクトルを適当に追加したり取り除いたりしてみても、「全部のサンプルを正しく識別すること」といういっぱい存在する他のサンプル1個1個が押し被せてくる制約条件の仕分けとは関係が無い。

こういう大量の制約条件が存在する状況をうまく捌けるアルゴリズムっていやーやっぱアレしかないから、アレのメンテに戻るしかないということを1週間かけて再確認すた、、、。n_

唯一収穫があったとすれば、無意味として捨てた

max{ 式(1)~(3)の最左辺 } < -w6 < min{ 式(1)~(3)の最右辺 } --- (4)

やがこれはアレの高速化には使える

ORる世界 [ゼロトラスト]

昨日の真打ちの方法で線形分離問題が解けると思って安心して寝たら夢のお告げで反例が見つかった、
しかし考察を重ねてついに完璧なアルゴリズムに到達すた、

記号

d
サンプルの次元
x[i]
i番目のサンプル
b[i]
i番目のサンプルのラベル(-1または+1)
H
ラベル+1のサンプルの集合
L
ラベル-1のサンプルの集合

前提

  1. H、Lともに要素に重複無し
  2. 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個だとして、次に従う。

  1. 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)の識別確認に進む。
  2. s(1), s(2), ..., s(m)から1個抜き、 y(n+1) を加えたベクトルをサポートベクトルとする(つまりサポートベクトルを交換した)識別面w_1(m通り) で正しく線形分離できるか試す。線形分離できればw_1 をw(t+1)としてy(t+2)の識別確認に進む。
  3. 線形分離できないままここまで来たら、線形分離不能として終了する。

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を正しく識別する識別面には、一般にサポートベクトルが異なる複数種類が有り得るが、どれかには必ず行きつく、
と思うが証明方法はわからん、、、
考え中

*1:ベクトルに重複が無いことから、暫定識別面に接するベクトルを常にd-1個までは選べる。 たまたま同一平面上により多いベクトルがあれば増えることもある。また、暫定識別面をLに接したまま傾けると減ることもある。そもそもLの要素数がd-1未満ならその要素数までとなる。

ORる世界[増補改訂版]

今日わ直交の日、

のっけから何だが前回のエントリは全て撤回死体orz、

意味が無かったmin/max

max{ 式(1)~(3)の最左辺 } < -w6 < min{ 式(1)~(3)の最右辺 } --- (4)

これは拡張次元も含めたときの調整途中の識別面の原点を回転中心とする回転を-w6だけオフセットして眺めてみたという以上の意味はない
調整途中の識別面とか超空間中をいかようにでも回転するので、そんなあやふやな仮の超平面からの距離が最大だったり最小だったりしても隠れた規則性の何か特別な表象である可能性は無限に小さいorz

真打の方法

そのかわりまず間違いのない方法を思いついた、
サンプルx[i]のラベルをy[i] (値は+1か-1)として、ラベルが+1のサンプルの集合をH、-1のサンプルの集合をLとする。HとLが識別されるためには、
任意にとったベクトルx∈H、y∈Lに対し、識別面はxとyが張る3角形の中を通らねばならない
そこで内積 < x, y >が昇順となるように2ベクトルのペアを並べかえ、*1、その先頭d組のペアを選び、その全てのペアの中点を通る超平面を暫定識別面w(t)とする。
ここでdはサンプルを表す最小の次元(BonaPieceベクトルの識別なので この場合は(2344+1))。
さらに、d組のペアとして選ばなかったベクトルについて、暫定識別面(法線ベクトルw(t))で識別されているかチェックしていく。
Hの要素xなのに < w(t), x > が負でしたりとか、Lの要素yなのに < w(t), y > が正だったりすると識別されていないので、そのようなxかyが識別されるように識別面を最小限動かす。
つまり、w(t)とx(かy)が張る三角形に沿って超平面を、ちょうどx(かy)が識別されるに足るだけ回転させ、それをw(t+1)とする
w(t+1)が決まったら、今度はd組およびその他のw(t)で識別済だった全てのサンプルが、w(t+1)でも識別さるるかチェックする。
識別されないものが生じたら線形分離不能、でFA
そうならずに全サンプル識別し切ったら、最後のw(t+1)で線形分離さるる、

パーセプトロンの収束定理との関係

あんま無い
パーセプトロンの収束定理は識別面にぴったり乗るサンプルは想定していない。(それがあったらマージンγが0なので、サンプルの最大半径をRとして反復回数の上界R^2/γ^2が無限大になってしまうま、、、
しかるに上記方法論においては、HかLのどちらについて識別面に乗っていても良いか一貫性を持って定めたらば、識別面にちょうど乗る形でのサンプルの識別に対応しうる
後に見るようにこれは盤面を並べる際に地味に効いてくる

アレとは何だったのか

線形分離するアルゴリズムとしてはアレが真の一般的解法であり常識であることは健在である。
なんでそれを使うのを渋っているのかというと、これは前回のエントリに書いた通りで

  • 思ったより遅い
  • 有理数計算を大量にせねばならない

という理由があり、またさらに

  • 最後にメンテしたのが2年近く前のコード
  • 計算準備が些末とはいえそこそこあるので実装のどこかに落とし穴が無いとも限らない

という事情で要はもっと時間的に余裕のあるときに触りたいのであっる
   ('A`)
/ ̄ノ( ヘヘ ̄ ̄
時間がせめてあと10年ぐらいあったらナア、、、

*1:BonaPieceベクトルなので全てのx、yは同じノルムを持つから、内積の大小はなす角の大小に他ならない。

ORる世界 [完全版]

BonaPieceによる局面表現の集合の線形分離(重みベクトルの決定)を、デジタル回路において真理値表からデコーダを作るみたいなお手軽さでやる方法を思いついたのでここに書く、

任意の座標値を採り得る一般的なベクトルの線形分離となるとアレを使うのが常識なのですだが(アレを使うと線形分離できる場合もできない場合もそれなりに速い有限ステップで結果が出る)、後に述べるようにのBonaPieceによる将棋の盤面表現とかの2344次元(+拡張次元)もあるベクトルの線形分離ともなると、平均的に速い方法とは言えそれなりに時間がかかることと、しくみ的に直接得られる解(および途中経過における変数値)が整数にならないことが多いのでカナーリ使い勝手が悪い

一方BonaPieceによる局面表現のは、2344次元(+拡張次元)とはいえ別段任意の座標値を取ったりすることはなく、要素は0か1とゆー0-1ベクトル表現なわけで、これは見るからに単純なベクトルなのでアレを使わずに整数演算で済む単純な方法があるのではなかろうか、と思って考えたらあった、

BonaPieceとは

駒の種類×状態(味方/敵のどちらか、盤のどこにあるか、または駒台の同じ生駒の何piece目か)を整数で表したもの
例えば将棋であれば、

FU×1一、FU×1二、...、FU×9九、
vFU×1一、vFU×1二、...、vFU×9九、
KY×1一、...、 vOU×9九、
FU×駒台1枚目、FU×駒台2枚目、...、FU×駒台18枚目、...、
vFU×駒台1枚目、vFU×駒台2枚目、...、vFU×駒台18枚目、...、
HI×駒台1枚目、HI×駒台2枚目、
vHI×駒台1枚目、vHI×駒台2枚目

という具合に2344個ある。これに先頭から1~2344の整数を割り振っておく。

BonaPieceによる盤面の表現

BonaPieceを盤上の駒(将棋で駒落ち無しの場合40個)全てについて集めたら(ただし同じ位置に別の駒がある等の矛盾した選び方はしないものとして)これを盤上の駒全てについて集めたら盤面が1個定まる。(1対1対応が成立する。)

さらに、有限集合を表現する常套手段として0-1ベクトルによる表現があり、この場合2344次元(+拡張次元)のベクトル空間を用意して、各軸が個々のBonaPieceに対応し、

軸iが1ならBonaPiece iを含む、0なら含まない

と約束することで盤面を定めるBonaPieceの集まり(1つの盤面に含まれるBonaPieceの集合)を0-1ベクトルにより表すこともできる。(これももちろん盤面と1対1対応が成立する。)

以下0-1ベクトル表現された盤面を分割しようという話なのですだが、いちいち2344次元(+拡張次元)ものベクトルを書くのは嫌なので、BonaPieceの種類(駒の状態)が5で駒の総数が3という仮想的なチャトランガ系統のゲームの局面表現で説明す、

例:BonaPiece総数が1~5のゲームで、BonaPiece 2、3、4からなる(そのように3個の駒が配置された)盤面を表すベクトルv1:

v1 = (0 1 1 1 0)

積項の実現

まず手始めに、盤面を表すベクトルv=(a b c d e) (BonaPieceが1~5なので5次元)と重みベクトルwの内積が、v=v1のときのみ正、それ以外は負になるようにwを定めることを考える。
論理回路で言うところの、入力が「0 1 1 1 0」のときのみ「1」となるAND回路と同じようなものを線形分離でやる。
天下りだが、AND論理のためにはv、wともに拡張次元1次元が必要なのであらかじめ追加する*1

v1' = ( 0  1  1  1  0  1)       ※ サンプルのベクトルの拡張次元の値は常に1
w’ = (w1 w2 w3 w4 w5 w6)       ※ w6は拡張次元の重み

すなわち、ベクトルv'=(a b c d e 1)のうちの正確にb、c、dが全て1のときのみ*2 w'・v'>0、b、c、dのどれか1つでも0ならw'・v'<0になることが条件である。
と考えると次の条件と同値であることがワカル

w2、w3、w3が全て正かつ
(w2、w3、w4の上位2個の和) < -w6 < (w2、w3、w4の総和)    ---(1)

答えの一例は、

w' = (0  2  2  2  0  7)

であっる。w2、w3、w4を同じ値にする必要は無く、またw6には可能な値に式(1)に示す幅があり、そもそもw'をスカラー倍しても線形分離結果は変わらないので無数にある解のうちのあくまで一つであるが、正しいことは検算したらワカル

積項の和の実現(タイトル回収)

v1' = ( 0 1 1 1 0 1 )に対して式(1)が出てきたのと同様に、
v2' = ( 1 0 0 1 1 1 )や
v3' = ( 1 1 0 0 1 1)といったベクトルにも、それぞれを正確に識別する重みの条件として、変数の添え字が相違するだけの式(1)と同様の式を考えることができる。
すなわち、以下の具合となる:

v1'について: (w2、w3、w4の上位2個の和) < -w6 < (w2、w3、w4の総和)    ---(1) [再掲]
v2'について: (w1、w4、w5の上位2個の和) < -w6 < (w1、w4、w5の総和)    ---(2)
v3'について: (w1、w2、w5の上位2個の和) < -w6 < (w1、w2、w5の総和)    ---(3)

ベクトルv' がv1'~v3'のどれかであるときのみw'・v'>0、それ以外のとき(v1'~v3'のどれでもないとき)はw'・v'<0となるように重みベクトルw'を構成したら、v1'、v2'、v3'とそれ以外を識別する積和論理の完成である。
これが実現されるには以下が条件である:

max{ 式(1)~(3)の最左辺 } < -w6 < min{ 式(1)~(3)の最右辺 } --- (4)

つまり、式(4)が非成立である限り、非成立ならしめているサンプル(一般に同着複数)の重みの値を、式(4)の成立する方向に増やせば良い。
式(4)が満足されない状態から、どの重みを増やしても

min{ 式(1)~(3)の最右辺 } - max{ 式(1)~(3)の最左辺 } --- (5)

が増加しないならば、v1'、v2'、v3'のみとそれ以外を正確に識別する線形分離は不可能という結論になる*3

Don't care値の有効活用

実は上記アルゴリズムに馬鹿正直に従うと、サンプルが増えてくると即線形分離不能に行き当たる。
これはv1'、v2'、v3'のみとそれ以外を正確に識別するというのが線形分離というしくみに対して厳しすぎるからそうなる。
この問題はラベル付けされないサンプルの識別(Don't care値に相当する)を線形分離しやすいように(好きに)想定することで緩和できる。

BonaPieceによる盤面表現は、BonaPieceの総数をN、同時に存在する駒の数をRとして、(同じ位置に別の駒がある等の矛盾した選び方も数えれば)C(N, R)個ある。ここでC(n, r)は例のコンビネーションの記号。
一般にこのC(N, R)個の全ての要素が+ or -にラベル付けされることは少なく、どちらともラベル付けされないサンプルが常に大量に存在する。
このことから、上記線形分離アルゴリズムを次のように変形して適用する:

max{ (ラベル付け「-」サンプルにおける式(1)~(3)の最右辺に相当する値) } < -w6 <  min{ (ラベル付け「+」サンプルにおける式(1)~(3)の最右辺に相当する値) } 

式(1)~(3)の最左辺の計算は不要になってしまたorz
最初からこうすれば良かったんや……|||。n_

まとめ

この技術の完成をもって、盤面の学習をプログラムに論理式の操作として取り扱わせしめる道が開かれにけり、
ニューラルネットワークリバイバルしたものなら、
記号処理AIもリバイバルすべきものと信じる……!

*1:蛇足だが幾何学的にはサンプルが存在する5次元空間(a b c d e 0)に対してそれを見下ろす神の視座(0 0 0 0 0 1)を設け、神の視座を通る5次元の超平面とサンプルが存在する5次元空間(a b c d e 0)の交線(4次元の超平面)でサンプル(a b c d e 0)を分離する意味になる、

*2:拡張次元は常に正確に1なのでいちいち記さない。

*3:線形なのでローカルミニマムは無い。重みw_iを減らすことで式(5)が正になったとすると、減らした重みはmax{ 式(1)~(3)の最左辺 }のargであるベクトルの重みである。(w_iが式(5)を0以下にならしめているベクトルとは無関係の重みであれば、その場合はもともと式(5)が正である。)max{ 式(1)~(3)の最左辺 }のarg と min{ 式(1)~(3)の最右辺 } のarg は、BonaPieceベクトル表現の定義より1要素以上の相違が必ずあるため、両argが共有しない重みが存在し、w_iを減らす代わりにmin{ 式(1)~(3)の最右辺 } のarg のみが有する重みを増やしても式(5)を正にできる。

カタラン数はもう語らん……!

カタラン数Cn は、縦横 n マスずつの格子において、対角線を跨がずに格子点を通って、向かい合った点を最短距離で繋ぐ道順の総数と説明できるせいで1次元の酔歩問題との関連が深い
証拠に上記格子を45°回転したら、たちまち縦軸が時刻、横軸が位置xの平面となり、カタラン数はx軸上を0から出発してマイナス側にはみ出ることなく2×n手かけてまた0に戻って来る経路の総数に他な
らない
このせいで、x=0から出発してx≦-1の領域に接触することなくx=0に戻ってきて、最後にx=-1に至る、長さ2*n+1手の経路の総数もまたCn であることは確定的に明らか、

検算

以下、経路としては途中でx≦-1の領域に接触せず、最後にx=-1に至るものだけを考える。
0から出て1手で-1に至る経路の数は[ - ]の1種類、C_0 = 1 (一致)
0から出て3手で-1に至る経路の数は[ +- - ] の1種類、C_1 = 1(一致)
0から出て5手で-1に至る経路の数は
[++ -- - ]
[+- +- - ] の2種類、C_2 = 2 (一致)
0から出て7手で-1に至る経路の数は
[++ +- -- - ]
[++ -+ -- - ]
[++ -- +- - ]
[+- ++ -- - ]
[+- +- +- - ] の5種類、C_3 = 5(一致)

以下略、

数学的帰納法か何かによる証明も略(マテ

結論

x=0から出発してx≦-1の領域に接触することなく2*n+1手の移動の最後でx=-1に至る経路の総数はC_n

ということは、

x=0から出発してx≦-1の領域にはみ出すことなく最後にx=-1に至る経路すわなち
x=0から出発してx≦-1の領域に達するまでの経路の総数TはΣ[k=0..∞]{ C_k }

よって正の方向に確率pで移動するランダムウォークにおいて0から出発して最初に1以上の範囲に接触するまでの試行回数の気体値は
Σ[k=0..∞] { (2 * k + 1) * C_k * p^k * (1-p)^(k+1) } ェ、

控えめに言って完動した

きみは知っているか?
2^{64} 以上の直近10個の素数

[   1] 1152921504606847009 is prime number.
[   2] 1152921504606847067 is prime number.
[   3] 1152921504606847081 is prime number.
[   4] 1152921504606847123 is prime number.
[   5] 1152921504606847127 is prime number.
[   6] 1152921504606847189 is prime number.
[   7] 1152921504606847201 is prime number.
[   8] 1152921504606847229 is prime number.
[   9] 1152921504606847253 is prime number.
[  10] 1152921504606847291 is prime number.

だ。

2^{128} 以上だと

[   1] 340282366920938463463374607431768211507 is prime number.
[   2] 340282366920938463463374607431768211537 is prime number.
[   3] 340282366920938463463374607431768211621 is prime number.
[   4] 340282366920938463463374607431768211729 is prime number.
[   5] 340282366920938463463374607431768211841 is prime number.
[   6] 340282366920938463463374607431768211877 is prime number.
[   7] 340282366920938463463374607431768211919 is prime number.
[   8] 340282366920938463463374607431768212029 is prime number.
[   9] 340282366920938463463374607431768212081 is prime number.
[  10] 340282366920938463463374607431768212213 is prime number.

だ。

これがさらに2^{512}以上とかになると、

[   1] 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171 is prime number.
[   2] 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084241 is prime number.
[   3] 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084381 is prime number.
[   4] 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084823 is prime number.
[   5] 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006085201 is prime number.
[   6] 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006085243 is prime number.
[   7] 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006085369 is prime number.
[   8] 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006086839 is prime number.
[   9] 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006087273 is prime number.
[  10] 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006088009 is prime number.

だったりする*1

以上は、多倍長整数テンプレートクラスBigNum<桁数>を作成したのでデモンストレーションとして素数判定を行ってみたものだ。
2^{128}以下なら瞬殺だ。
2^{512}以上は、さすがに1分かかったorz

大量の桁の表現にはいくばくかのメモリーが要る。
やりたい計算に対して用意した配列では足りなかった場合はこうだ↓

■ 配列4要素で2^{64}以上の素数判定をしようとして128 bit+αの積の結果を格納できないとわかったケース:

(sz=4)          +0          +1          +0          +0
ERROR: Overflow.

 0x2d094641 0x2a2980b2 0x211f93eb 0x2bb7e9a8 0x00000000
y=907995832759952054134265850490340929
(sz=4)  +733473192  +555717611  +707362994  +755582529

t=1152921504606846982
(sz=4)          +0          +1          +0          +6


オーバーフローとアンダーフローのチェックは四則演算全てで行われ、いったんオーバーフローかアンダーフローが起きたらその結果は無効な数となる。
さらに無効な数を用いた演算結果もまた無効な数となり*2、最終的に必ずエラーとして検知できる。

以上のしくみは以下のネ申のウェブページ↓の情報にもとづき繰り上げ算方式*3多倍長整数演算を固定長配列行うように実装したものである。
■ 超高速!多倍長整数の計算手法【前編:大きな数の四則計算を圧倒的な速度で!】
ttps://qiita.com/square1001/items/1aa12e04934b6e749962

これを有理数クラスに組み込むことにより、精度リッチで比較的高速に動き、オーダー上もn個のベクトルの線形分離完了(または線形分離不能と判定)が大概のケースでO(n^{3})ぐらいで解ける線形分離エンジンが完成すた、

だがタッチの差で完成が遅かった、、、

今日わ、昨年よりちょっと進歩しましたよという風を装った動きをする機能を対戦プログラムにこれから組み込まねばならない|||。n_

*1:ミラー–ラビン素数判定法で100回づつ回したので多分間違い無い……

*2:これは算術演算か論理演算かを問わず全てでそのように伝搬する。

*3:これが論理回路ならルックアヘッドキャリー方式で多数桁のキャリーを物量に訴えて並列計算するところだが、ソフトウェアーというものは逐次処理しかできないために古式ゆかしいリップルキャリー式のキャリー伝搬の必要性がどこかしら出てくるが、繰り上げ算copy_and_fix()によりそれを極力後回し・必要最小限な回数に減らすことができる。これはメモリーの冗長な使用というコストを支払うことによって、アセンブラの動作速度(キャリーフラグ等を使って毎回リップルキャリーする多倍長超加算器を構成した場合)をも凌駕し得る。知らんけど。

ORる世界

前回のエントリまでで述べたことは、

BonaPieceによる局面表現の集合に線形分離可能な分割の仕方が必ずある

*1、というだけであって、

BonaPieceによる局面表現の集合を任意の分割の仕方で線形分離できる

、ではなかったorz
実際、反例が存在する。こんなやつ:

         ↓局面        ↓ラベル
[    0] ( 0 1 0 1 ) : -1
[    1] ( 0 1 1 0 ) : +1
[    2] ( 1 0 0 1 ) : +1
[    3] ( 1 0 1 0 ) : -1

これはBonaPieceの種類(駒の状態)が4で駒の総数が2という仮想的なチャトランガ系統のゲームの局面表現を線形分離しようとした例なのですだが、これを線形分離する単一の重みベクトルは存在しない。
よく見るとXORパターンなのがワカル。XOR、またお前か、、

少なくともラベル-1の要素とラベル+1の要素について共通に1であるBonaPieceばかりだと単一の重みベクトルで線形分離できない。

前回のエントリの議論では

f:{ BonaPieceによる局面 } → { 1, 2, ..., 2^2344 } (⊂N)

という写像は2344個の線形分離結果のORで実現できうる*2、という想定だったが{ BonaPieceによる局面 }に線形分離不可能なケースがあるということは積和論理の積項を1個の重みベクトルで実現でできない(ことがある)という話であって先行きに暗雲が立ち込めてきたorz

こうならない(線形分離できる)条件は一言では述べられないが、実験する限りはちょっとラベルをいじればたいてい線形分離できるっぽい*3

[    0] ( 1 1 0 0 0 0 ) : -1
[    1] ( 0 0 1 0 0 1 ) : -1
[    2] ( 0 0 0 0 1 1 ) : -1
[    3] ( 0 1 1 0 0 0 ) : -1
[    4] ( 1 0 0 0 1 0 ) : +1
[    5] ( 0 0 0 1 0 1 ) : +1
[    6] ( 0 1 0 0 0 1 ) : +1
Retrying... (1)
        |
        v
[    0] ( 1 1 0 0 0 0 ) : -1
[    1] ( 0 0 1 0 0 1 ) : -1
[    2] ( 0 0 0 0 1 1 ) : -1
[    3] ( 0 1 1 0 0 0 ) : -1
[    4] ( 1 0 0 0 1 0 ) : -1
[    5] ( 0 0 0 1 0 1 ) : +1
[    6] ( 0 1 0 0 0 1 ) : +1
[0] result=1

[    0] ( 0 0 0 0 1 1 ) : -1
[    1] ( 0 0 1 0 0 1 ) : -1
[    2] ( 1 0 0 1 0 0 ) : -1
[    3] ( 0 1 0 0 0 1 ) : -1
[    4] ( 0 0 1 1 0 0 ) : +1
[    5] ( 0 1 1 0 0 0 ) : +1
[    6] ( 1 0 1 0 0 0 ) : +1
[1] result=1

[    0] ( 0 0 0 0 1 1 ) : -1
[    1] ( 0 0 1 1 0 0 ) : -1
[    2] ( 0 0 1 0 0 1 ) : -1
[    3] ( 0 0 0 1 0 1 ) : -1
[    4] ( 0 0 0 1 1 0 ) : +1
[    5] ( 1 0 0 0 1 0 ) : +1
[    6] ( 1 0 1 0 0 0 ) : +1
[2] result=1

[    0] ( 0 0 0 0 1 1 ) : -1
[    1] ( 0 0 1 0 0 1 ) : -1
[    2] ( 0 0 1 1 0 0 ) : -1
[    3] ( 0 1 1 0 0 0 ) : -1
[    4] ( 0 1 0 0 1 0 ) : +1
[    5] ( 1 0 0 0 1 0 ) : +1
[    6] ( 0 0 0 1 0 1 ) : +1
[3] result=1

[    0] ( 1 0 0 0 1 0 ) : -1
[    1] ( 0 0 0 1 0 1 ) : -1
[    2] ( 0 0 1 1 0 0 ) : -1
[    3] ( 0 1 0 0 0 1 ) : -1
[    4] ( 1 1 0 0 0 0 ) : +1
[    5] ( 0 0 1 0 1 0 ) : +1
[    6] ( 1 0 0 0 0 1 ) : +1
[4] result=1

[    0] ( 1 1 0 0 0 0 ) : -1
[    1] ( 1 0 0 0 1 0 ) : -1
[    2] ( 1 0 0 1 0 0 ) : -1
[    3] ( 0 1 0 0 1 0 ) : -1
[    4] ( 0 1 1 0 0 0 ) : +1
[    5] ( 0 1 0 1 0 0 ) : +1
[    6] ( 0 0 1 0 0 1 ) : +1
[5] result=1

[    0] ( 0 1 0 0 0 1 ) : -1
[    1] ( 1 0 0 0 1 0 ) : -1
[    2] ( 1 1 0 0 0 0 ) : -1
[    3] ( 0 0 1 1 0 0 ) : -1
[    4] ( 0 1 0 0 1 0 ) : +1
[    5] ( 0 0 0 1 0 1 ) : +1
[    6] ( 1 0 0 1 0 0 ) : +1
[6] result=1

[    0] ( 0 0 1 1 0 0 ) : -1
[    1] ( 1 0 0 0 1 0 ) : -1
[    2] ( 0 0 0 1 0 1 ) : -1
[    3] ( 1 0 1 0 0 0 ) : -1
[    4] ( 1 1 0 0 0 0 ) : +1
[    5] ( 0 0 1 0 0 1 ) : +1
[    6] ( 0 1 1 0 0 0 ) : +1
[7] result=1

[    0] ( 0 0 0 1 0 1 ) : -1
[    1] ( 1 0 1 0 0 0 ) : -1
[    2] ( 0 0 0 0 1 1 ) : -1
[    3] ( 1 0 0 1 0 0 ) : -1
[    4] ( 1 0 0 0 0 1 ) : +1
[    5] ( 0 0 1 1 0 0 ) : +1
[    6] ( 0 1 0 0 0 1 ) : +1
Retrying... (1)
        |
        v
[    0] ( 0 0 0 1 0 1 ) : -1
[    1] ( 1 0 1 0 0 0 ) : -1
[    2] ( 0 0 0 0 1 1 ) : -1
[    3] ( 1 0 0 1 0 0 ) : -1
[    4] ( 1 0 0 0 0 1 ) : -1
[    5] ( 0 0 1 1 0 0 ) : +1
[    6] ( 0 1 0 0 0 1 ) : +1
[8] result=1

[    0] ( 1 1 0 0 0 0 ) : -1
[    1] ( 1 0 1 0 0 0 ) : -1
[    2] ( 0 0 0 0 1 1 ) : -1
[    3] ( 0 0 1 0 1 0 ) : -1
[    4] ( 0 1 0 0 0 1 ) : +1
[    5] ( 1 0 0 1 0 0 ) : +1
[    6] ( 0 0 0 1 1 0 ) : +1
[9] result=1

これはBonaPieceの種類(駒の状態)が6で駒の総数が2という仮想的なチャトランガ系統のゲームの局面表現を線形分離しようとした例なのですだが、result=1が線形分離成功を表し、Retrying...は1発で線形分離できなかったのでラベルをちょっと弄ったことを意味する*4

BonaPieceの数が増えたらベクトルが高次元になるということなので、普通線形分離しやすくなることが気体できるから、本将棋(BonaPiece数2344)とかだと写像fの実現に必要な重みベクトルの数やっぱ2344個を大きくは出ないのではないか、

そもそも写像fのように局面を自然数写像する必要があるのは勝ち方(手数の最短化)などにこだわるからで、ただ単に勝てれば良いとみなすなら、{ BonaPieceによる局面 }を単に必勝の局面とそうでない局面にただ2分すれば良いから、必要な重みベクトルの数はなんと1+α個で賄い得る。

やっぱ将棋の神様の必勝手順は、うまいことやったら一人の人間の脳に収まりうる可能性が微レ存、

*1:少なくともただ1つの局面表現xを他と線形分離可能なことは任意のxについて保証される

*2:なぜそれで可能そうかは論理回路を見たらワカル、

*3:つなみに線形分離は太古の昔に様々なテクニックが開拓されており、文献を当たったらチョー効率的なアルゴリズムが書いてあった\(^o^)/。
もはや令和の時代なので、パーセプロトロンの収束定理そのままのナイーブな実装でいつ線形分離が完了するのかしないのかわからないままかあてどもなくループを回してみたり、α=β^2/rの値をいくつにしたら良いんじゃ、みたいな原始人の議論は不要である。

*4:ラベルを動かしてしまってどうすんじゃ、というのは以下略