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

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

■

[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)による方が効率が良い。

■

[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:といってもこの場合直線だが…

■

[AI] （1次元拡張した）KP式の評価関数×289個の表現能力は○棋の完全解析結果を記憶するのに十分である

余はこの定理の証明について真に驚くべき発見をしたので喜びのあまり書く、
ていうかKPというよりPでおk

P式の評価関数とはどんなものか

○棋の駒のとり得る状態は、置駒については駒の種類を14（成り不成りを区別）として、

14×81マス×(先後の区別) 2 = 14 * 81 * 2 = 2268種類

持駒については

(∑[x∈{生駒}]{xの最大枚数})×(先後の区別) = (18+4+4+4+4+2+2+0)*2 = 76種類

の計2344種類ありぬ*1、
これがいわゆるBonaPieceと言われるﾌﾞﾂの総数だる、

で、○棋の盤上（と駒台）には常に計40個の駒が存在し、かつ同一のBonaPieceにあたる駒は2個以上は存在しない（1個または0個）
すわなち盤上（と駒台）には40個のBonaPieceが常に存在する、と言い換えても良い*2

これらBonaPiece 1～2344のそれぞれに数値を割り当て、○棋の任意の局面を盤上（と駒台）に存在する40個のBonaPieceに割り当てられた整数の合計値の大小で局面の良し悪しを評価せんとするのがPによる（Pを評価因子とする）局面評価だる

以下、BonaPiece pに割り当てられた整数をpの重み、○棋の局面に対して局面に含まれるBonaPieceの重みの合計する式をP式の評価関数、与えられた局面xについてのP式の評価関数で具体的に計算した値をxの評価値と呼ぶ

さらに、BonaPieceの総数をB（=2344）、1個の局面が含むBonaPieceの数をN（=40）とおく。
後で見るように、学習データのNが定数、というのがジワリと効いてくる

P式の評価関数の表現能力

はっきり胃って入力ベクトルB次元のパーセプトロン1個とほぼ同じ

ていうか重みベクトルを入力ベクトルに1次元足したB+1次元ベクトルと考えればパーセプトロン1個にか、完全に一致……！

（1次元拡張した）KP式の評価関数×289個の表現能力は○棋の完全解析結果を記憶するのに十分であることの証明

以下パーセプトロンの入力ベクトルと重みベクトルをそれぞれ1行B列と1行B+1列の行列とみなし、要素を分ける「,」抜きで書く。
さらに、「[n]」はn個（0個以上）の列要素のDon't care、「*」を1個の列のDon't careの意味で使う。

補題1: 入力ベクトルの部分集合{ (1 0 [q]), (0 1 [q]) }と{ (0 0 [q]), (1 1 [q]) }は、全ての集合が値1の列を3個以上含み、(0 0 [q])がさらにもう一個値1の別の列を有するなら線形分離できる

パーセプトロンはXORを学習できないと言われるが、これは識別面の表側にある入力ベクトルを1、裏側にある入力ベクトルを0とラベリングするものとして、

入力ベクトルv1=(1 0)に対応する重みベクトル(w1 w2)の和 = w1
入力ベクトルv2=(0 1)に対応する重みベクトル(w1 w2)の和 = w2
入力ベクトルv3=(0 0)に対応する重みベクトル(w1 w2)の和 = 0
入力ベクトルv4=(1 1)に対応する重みベクトル(w1 w2)の和 = w1 + w2

というケースにおいてw1, w2を正負どちらに弄ってもv3以外の重みの和が同符号となり、v1とv2を正、v4を負（または0）にできないことによる。
ところが入力ベクトルv3以外に1次元、v3には2次元追加し、それらの値がいずれも0以外ならば、追加した次元の重みベクトルで重みの総和を正方向または負方向の必要な方向に任意にオフセットでき、線形分離できるようになる。
実際、重みをw1=-2、w2=-2、w3=w4=w5=w6=3、w4=-4として、簡単のため入力ベクトルのDon't care部分の重みを0と仮定したとき、次のように{ v1, v2 }と{ v3, v4 }を線形分離できる：

入力ベクトルv1=( 1  0 [a]  1 [b]       )に対応する
   重みベクトル(w1 w2 [a] w3 [b]       )の和 = w1 + w3 = (-2) + 3 = 1
入力ベクトルv2=( 0  1 [c]  1 [d]       )に対応する
   重みベクトル(w1 w2 [c] w4 [d]       )の和 = w2 + w4 = (-2) + 3 = 1
入力ベクトルv3=( 0  0 [e]  1 [f]  1 [g])に対応する
   重みベクトル(w1 w2 [e] w5 [f] w7 [g])の和 = w5 + w7 = 3 + (-4) = -1
入力ベクトルv4=( 1  1 [h]  1 [i]       )に対応する
   重みベクトル(w1 w2 [h] w6 [i]       )の和 = w1 + w2 + w6 = (-2) + (-2) + 3 = -1

ここで、Don't care記号 [a]～[i]は、追加した値1の列がベクトル毎にばらばらでも同じでも良いことを示す*3。

で、この場合w1とw2は符号のみが問題で絶対値はいくら大きくしても良く、w3～w7は任意のオフセットを与えられるから、以下の入力ベクトルのDon't care 部分の重みの和がどうなろうとも、やはり適当なw1, w2, w3～w7が存在し、線形分離でくる

■ 証明終わり

（びこう）
上記補題における重みの決め方においてDon't care部分が値0ばかりな入力ベクトル(* * [q])の出力が正負どちらになるかは定まらず、さらに（同じくDon't care部分が0ばかりな）{ (1 0 0 [q]), (0 1 0 [q]) }と{ (0 0 0 [q]), (1 1 0 [q]) }は線形分離不能なままだが、後で見るように今回の応用に限って言えば、これは全く問題を生じない。（[q]の中に必要なだけの個数の値1の存在が保証され、補題1の適用パターンへの回避が常に可能

補題2: 値1の列をN個（ただし4個以上）含み、その他の列が0のベクトルは、重みベクトルを1次元拡張したパーセプトロンで互いに線形分離できる

入力ベクトル(* * [q])について、パーセプトロンの性質の既知の議論によって、以下の線形分離は可能である
{ (1 1 [q]) } と { (1 0 [q]), (0 1 [q]), (0 0 [q]) } は問題無く線形分離でくる（AND論理）
{ (1 1 [q]), (1 0 [q]), (0 1 [q]) } と { (0 0 [q]) } は問題無く線形分離でくる（OR論理）

で、XOR論理についても補題1により線形分離でくる。
なぜなら、入力ベクトルの部分集合 { (1 0 [q]), (0 1 [q]) } と { (0 0 [q]), (1 1 [q]) } の分離を考えたとき、入力ベクトルの明記されている値1の列の個数がそれぞれ1, 1, 0, 2のため、仮定より、[q]部分にはそれぞれ3、3、4、2個の値1の列が存在する。よって、補題1より、それら該当列の重みには、線形分離可能とする値が必ず存在する。

で、あとは上記該当列を除いた列からなる部分空間の線形分離可能性のみの問題となるから、上記論法を再帰的に適用し、部分空間のサイズが4次元以上の間は、該当列の重みに線形分離可能とする値が存在することが言える。

で、3次元まで入力ベクトル空間が縮小されたとき、その部分空間に含まれ得る入力ベクトルは次の8通り：

(1の個数が0)
  A: ( 0 0 0 )
(1の個数が1)
  B: ( 0 0 1 )
  C: ( 0 1 0 )
  D: ( 1 0 0 )
(1の個数が2)
  E: ( 0 1 1 )
  F: ( 1 0 1 )
  G: ( 1 1 0 )
(1の個数が3)
  H: ( 1 1 1 )

もともとの1の個数がN個（定数）の仮定により、この時点で1の個数が相違するもの同士の線形分離の必要は生じない。

1の個数が1個同士または2個同士の線形分離については、もはや(0 0 0)との線形分離が問題になることは無く、かつ、該当するベクトルの個数が高々3であるため、1次元拡張した重みベクトルがもう1列あることからその重みでオフセットすることによりXOR論理であっても線形分離可能。

■ 証明終了

（1次元拡張した）KP式の評価関数×289個の表現能力は○棋の完全解析結果を記憶するのに十分である

上で導入したBonaPieceの個数をB（=2344）、局面に含まれる駒の個数をN（=40）により、局面の総数はB_C_N個。ここでn_C_rは例のコンビネーションの記号とす、

完全解析結果を記憶するには、局面の集合を、先手/後手のうちの必勝側に有利な順に並べればおk。よって、学習モデルが局面の集合（要素数B_C_N）を値域[0, B_C_N)の整数に全単射する任意の写像を表現し得るならば、その学習モデルは完全解析結果を記憶できうる、

で、この値域[0, B_C_N)の整数というのは、2進数で表すと、log(B_C_N) ≒288.15 bit、すわなち289個の0/1の組み合わせで表せる

一方1個のパーセプトロンの出力は1個の0/1であり、パーセプトロンの収束定理があるからB次元の入力の識別を（入力が確定しておりかつ線形分離可能な集合である以上）必ず有限ステップで学習できる

この場合の線形分離可能性が保証されることは補題2で示したある

よって、（1次元拡張した）KP式の評価関数を289個束ねたﾌﾞﾂは、局面の集合（要素数B_C_N）を値域[0～B_C_N)の整数に移す任意の写像を表現できる。

よって（1次元拡張した）KP式の評価関数×289個は、○棋の完全解析結果を記憶できる

■ 証明おわり

検算

ネットにはKPじゃあ次元が足りねえわバカじゃねえのﾌﾟｹﾞﾗｷﾞｬｰｽwwwwwwww
という系の反論（？）が散見されるような木がするので本当かどうか確認汁*4、

局面の集合（要素数B_C_N）を値域[0～B_C_N)の整数に移す全単写写像はB_C_N!通りだる、これはB^Nより小さいい

一方、入力B+1次元のパーセプトロンを289個束ねたﾌﾞﾂで表せる写像の個数だが、この場合は1個のパーセプトロンは局面の集合（要素数B_C_N）のべき集合（要素数2^(B_C_N)）に含まれる1個の元を学習していることになり、それが289個束になているわけなので

(2^(B_C_N))^289 = 2^(289*B_C_N) = (2^12)^(24.083*B_C_N) > B^((24.083*B_C_N) )通り

となり、後者の圧勝

後者がなんで圧勝するのかというと、後者はN個のBonaPieceからなる局面の集合から[0, B_C_N)の整数への全単写写像だけでなく、以下の写像の表現能力を有するから*5。

  1. N個のBonaPieceからなる局面の集合を値域[0, B_C_N)の整数に移す任意の（全単射とは限らない）写像
  2. BonaPieceの個数がN以外の局面も含む局面の集合のうち、線形分離可能性を満たすやつを値域[0, B_C_N)の整数に移す任意の（全単射とは限らない）写像*6

まとめ

○棋の完全解析の結果を記憶するのに宇宙の原子の個数より多くの記憶セルを必要とするという議論は何だったのか…

ていうかゲームが比較的低次元のパーセプトロンで完全に説明をつけられることがわかった今、もはや○棋はAI技術のテストヘッドとしての役割を終えたのではないか、

コンピュータ○棋は解かれた…！（ﾏﾃ；

■ 追記

2人零和ゲームの評価値は1、0、-1の3値あれば良く、局面の集合を{ 1, 0, -1 }に移す任意の写像を表現できれば完全解析結果を記憶できることになるから、よく考えたら局面の集合のどれが（先手か後手のうちの必勝側の）必勝局面か否かだけを記憶するだけでも必勝手順を記憶し切れる。ということは目標をそれにﾌﾟﾁ修正した場合は（1次元拡張した）P式の評価関数1個の表現能力で十分なのかﾏｼﾞか…

*1:TO、NY、NK、NGをKIとみなすなどのせこい同一化工夫はこの際やめるとして

*2:持駒について、先手（後手）の生駒xがn枚ある状況を先手（後手）のn枚目のxのBonaPieceただ1個で代表する、みたいなせこい同一化工夫はこの際やめるとして

*3:v3に追加した2列のうち片方は、v1、v2、v4への追加列とは必然的に相違する

*4:集中して考えるためにネット絶ちしていたら何とかちゃんねるの例のスレがdat落ちしてしまったorz

*5:要検証

*6:これは証明中で述べた学習が、N個のBonaPieceからなる局面のみをinputとする想定のためこうなる。学習時にinputとして与えていないパターンについては出力が規定されず、任意の出力が有り得る

【速報】826askaメジャーデビュー！！！！１１１！！１！！１！【スクープ】

life 826aska

826askaクリスマスライブ2018に行ってきたヾ（＞∀＜）ﾉ！*1
ずぼらなファンなものでいろいろ言い訳をしつつ結局ライブ出席1年ぶりになてしまったorz、、、
1年も会わざれば一体どこを刮目して見るべきなのか、正直不安と期待が入り混じった形で開演を迎えたのですが！
不安は全くの取り越し苦労でした！！
迫力と安定感と弾きこなしの力が圧倒的に進歩してた；；*2
開演とともに観客の意表をついてステージの中らへんからサンタコスで登場、クリスマストークを繰り広げつつ壇上に上がると劈頭クリスマス曲5曲ぐらいをメドレーで弾いたのですが、前回と違ってビデオ映像による導入演出無しで素の演奏開始だったので、かえって演奏スイッチの入り方の凄さがビシッと伝わってきて良かったわ
ホールの340席全部がもう一瞬で826askaゾーン。
前年は中島みゆきの「糸」について、チャレンジングな曲だけど弾いてみたんだけどどう？みたいな本人談でしたが今回のはしっとりした曲も演奏としてｽｹﾞｰきっちりハマっていた感じでﾒﾁｬ聞き応えがあった
大演奏家としてのオーラを着実に纏いつつあるｶﾝｼﾞ!

今回はアルコバレーノは無し。着替えの間にパパとのトークと熱唱*3をはさみつつも一人で2時間のステージを弾き切りました。
その中で重大発表が！
なんとCDとDVDがこの春大手音楽レーベルから発売になるそうです！ドンドンドン パフパフパフ！！！！*4
さらにさらに！2019年3月、東京公演決定！！その名も、

Live Tour 2019 〜Zephyr〜

震えて待て！

■ きょくもく
なんか今回はタイトルを言ってくれない曲が多かったので不正確death、
かなり記憶違いもあるかもしれんｽﾏﾝorz
DVD化を待つ、、
（サンタコス）
1. クリスマスソング5曲ぐらいメドレー
2. 「君の名は」メドレー
3. 宇宙戦艦ヤマト
（パパトーク、歌熱唱（不明））
（826aska再登場、白いドレス）
4. 美女と野獣
5. （ディズニーの雪にちなんだ曲）
6. （不明）
7. （不明）
（826aska再び登場、ミ○キー○ウ○コス？）
（ジャンケン大会で黒色紙抽選5名様プレゼント）
8. 天使のくれた奇跡（USJで冬かかるやつ）
9. （不明）
10. Canon Rock
（アンコール）
11.（不明）
12. 君の瞳に恋してる

最後の12番は間奏のときリズムパートをエレクトーンにまかせて本人立って手拍子、
会場をノリノリの渦に巻き込んだ後、そのまま立って演奏再開…ペダル操作もあるというのに立ったまま演奏続行…
12番の曲はもはや目隠ししても演奏できるレベルなのかもしれん…

このノリで目指せ、東京オリンピック開会式…！

*1:於 今池ガスホール＠名古屋

*2:今火力の単位をJKとしよう。落ち着いて考えれば上記事象は当然で、2 JKともなれば倍の火力、威力2倍なのである。

*3:音楽一家としての体裁を整えるためとのこと

*4:今回のライブはその関係者の方も客席にご臨席だったとのことのことなので、ある意味大舞台だったと言える。

数値的に安定な線形分離方法

lifehack

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

    n・x + b = 0  ・・・ (1)

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

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

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

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

と再定義することにより

    n・x = 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」の調整で、nのn+1次元目の軸に対するもともとの傾き（重要）を45度まで増幅（あるいは減衰）すればよろしいい*2

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

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

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

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

ここで「・」は内積、e_pは、もともとの特徴ベクトルになかった第n+1次元の正規直交基底ベクトル。
x'は、もともとの特徴ベクトルになかった第n+1次元を弄っただけなので、もともとの特徴ベクトルの情報（n次元）を完全に保持していることにちういせよ、

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

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

■ 証明:
n'・x' = α(x・n)。よって、x・n = 0ならn'・x' = 0。逆も真。
□

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

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

なのだる、

なお、式(8)の右辺を見たらﾜｶﾙ通り、n'はもとのnの約α倍される。ただし法線ベクトルnやn'は方向だけが意味を持つから、α倍したからといって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枚貼れば以下略

石川県でＥＣＫ！

life 826aska

※ ECK = エレクトーンコンサート開催*1

前回

来年からはきっと826askaのライブのスタイルはがらりと変わるであろう、

と書いた手前、石川県に出かける準備をしていたんである（これもお役目


が、急な仕事が入って行けんかったorz*2


というわけで情報無し。情報求む。


はーーーーーー------
なんかピッチドロップ実験の決定的瞬間を見逃したわ、みたいなｶﾝｼﾞ…


漏れは、歴史の証言者にはなれない…

*1:ここ参照。

*2:むむむ無職ちゃうわ！！！１１１！！！！１