2011-11-14

駆け足で読む『Lectures on Algebraic Statistics』再び２ 1. Markov Bases(2)

駆け足で読むシリーズ代数統計統計 Algebraic Statistics

目次はこちら
こちらでm次元分割表の正確確率検定の話、そして、そのp値計算のために、与えられた周辺度数を満足するテーブルの集合があった
そして、その集合を動き回るための基底としてのマルコフ基底が登場した
ここで、「テーブル集合」はマルコフ基底によって、網羅的に動き回ることができる
この閉じていること、動き回れることが「代数的」なので、Algebraic statisticsの内容としてこの話題が登場している
この記事は1. Markov Basesの後半
２次元分割表の「動き」は
- 行の和がゼロ、列の和がゼロになるような動き
- それを「単位」に分解すると、２行、２列を取り出し、分配方法を取り換える、という動きが、最小単位
- すべての動きはその組合せで表せる
- ここで言う動きは、 $A^Tv=A^Tu$ が同じ周辺度数を持つ表(を１次元ベクトルにしたもの)の関係を定める行列 $A$ を使って考えれば、 $Aw=0$ を満足するような $w$ の例になっている
m次元分割表の「動き」は
- $Aw=0$ を満足する $w$ に属する。 $Ker(A)=\{w:Aw=0\}$ (Aのカーネル・核空間・零空間)→Wiki
- ここで、きちんと書くために、表記法を書いておく
  - $T(n)=\{u \in \mathbf{N}^R | \sum_{i \in R} u_i=n\}$ は、m次元 $R=\prod_{i=1}^m r_i$ であるようなテーブルのすべてのセルの値の和が $n$ であるようなテーブルに対応したベクトルの集合
  - このようなテーブル集合の１要素 $u$ に対して $F(u)=\{v \in \mathbf{N}^R | Av = Au\}$ は「 $A$ によって $M_A=\{p=(pi)\in int(\Delta_{R-1}) | \log(p) \in rowspan(A)\}$ と定義される「モデル $M_A$ 」に関する $m$ 次元分割表 $u\in T(n)$ のfiber」
  - 言い換えると、総サンプル数 $n$ なるm次元分割表の集合を扱う。その集合の１例 $u$ があったときに、 $u$ と $A$ を用いて、ある関係になるようなm次元分割表の集合が $u$ のfiber。ただし、 $A$ はなんでもよいわけではなくて、制約を入れておく。この場合には、生起確率の積でうまくいくような関係に対応させた定義を用いており、そのことの意味は、m次元が相互に独立な確率変数であることである。また、そのことは、定義を表現するときに、対数の１次線形和になるので、log-linearモデルと呼んでいる。
- ,を使った「動き」の定義とは
  - $u\in T(n)$ もそのfiber $F(u)$ も表の形になったベクトル(の集合)
  - これらを足し算で移動したい。その足し算に制約を持たせる
    - 足し算の「足される側」と「足す側」と、その「答」のすべてがこの集合に含まれること(和について閉じている)
    - 足し算を要素の積み重ねとして表したときに、その途中の経路も集合に含まれている
  - これを数式で書くと
    - $\forall u \in T(n)$ に関して、 $\forall v,v' \in F(u)$ があったとき
    - $v'=v+\sum_{k=1}^L u_k$ , $v+\sum_{k=1}^l u_k \ge 0;l=1,2,...,L$ を満足するような
    - $u_1,...,u_L\in B$ を要素とする有限部分集合 $\in B \subset Ker(A)=\{w:Aw=0\}$ がMarkob basis と呼ばれ、 $u_1,...,u_L$ は $B$ の(定める)「動き」の要素と呼ばれる
- その例として $m$ 次元分割表の場合には、２次元間の取り換え、３次元間のぐるり、…、m次元間のぐるり、を集めたものもある(これは、2,3,...,m次の置換群)になるが、これは格子基底(lattice bases)と呼ばれMarkov bases に含まれるらしい…
こんな感じの「動きの基底」であるが、定義を広げたり縮めたりすることでいろいろある
- lattice basis $\subset$ Markov basis $\subset$ Grobner basis $\subset$ universal Grobner basis $\subset$ Graver basis