2008-03-27

置換多面体(permutahedron)とランクテスト

Permutahedron Rank test

PDF
順列(permutation)と、その関係を共通する半順序を用いて集合的に表すことについて
- 1,2,...,nなる、n個の自然数の並べ方(順列,permutation)は $n!$ 通り
- ある順列を次の３通りの表現で表す
  - 例。３つの値のセット{11,7,13}。これは、第１の要素が２番目に小さく(２番目に大きく)、２番目の要素が１番小さく(３番目に大きく)、３番目の要素が３番目に小さい(１番大きい)
    - 小さい順で考えたときの順序は $\rho = (2,1,3)$
    - 大きい順で考えたときの順序は $\delta = (3,1,2)$
    - ３個の要素が作る $\frac{3\times 2}{2}=3$ ペアのそれぞれの大小関係を用いて表すと $\pi=\{(2,1),(1,3),(2,3)\}$ =第２番目の要素は、第１番目の要素より小さい、第１番目の要素は第３番目の要素より小さい、第２番目の要素は第３番目の要素より小さい、という３つのペアにおける大小関係を記したもの
- 順列の交わりとしての半順序
  - 今、という順列とという順列を考える
    - $\pi =\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\}$ , $\pi '=\{(1,2),(1,3),(1,4),(3,2),(2,4),(3,4)\}$
    - ととを自然数ペアの集合とみなせば、その交わりはと表せる
      - この関係は、2,3の関係が定義されていないだけで、それ以外は定義された関係(半順序)になっている
ランクテストを順列の分割(partition)として捉えることについて
- 今、観測数nの観測を考える
- このn個の観測の並べ方(順列)は $n!$ とおりある。それを $\pi_1,\pi_2,...,\pi_{n!}$ とする
- 今、あるテストがあって、それは、 $\pi_i$ についてある統計量を与えるものとし、その統計量を $\tau(\pi_i)$ と表すことにする
- $n!$ とおりある並べ方のそれぞれに統計量が与えられ、その値はmとおり( $m \le n$ である
- mとおりの値が観測される確率は、その統計量に対応する順列がいくつあって、その順列がそれぞれどのくらいの確率で生起するかによって決まる。このようにしてmとおりの値のそれぞれについて生起確率が算出できる
- mとおりの統計量のそれぞれについて、その生起確率の大小に応じて、正確確率検定のP値算出の論理を当てはめたものを、このテストのP値とする
- このとき、このテストは、 $n!$ とおりの順列をmとおりの値に対応づける、その対応づけによって定まることがわかる
- この対応づけは、 $n!$ とおりのものを、m群に分割することである
- したがって、観測数nのデータについてのノンパラメトリックな検定は、生起確率によってP値を算出するとき、 $n!$ とおりの順列の分割のとり方であることがわかる
- 今、要素数kの集合の分割は、ベル数として知られるから、それを $B(k)$ で表すことにすると、ノンパラメトリックな検定は、 $B(n!)$ 種類が存在しうることになる
Permutohedron(順列多面体)の導入
- 順列は、Permutohedron(順列多面体)として幾何学的に捉えることができる
- Permutohedronにおいて、半順序でPoset(partial order set)のようなもので順列を分割する(「丸め」「くくり」)作業は、Permutohedron上の低次元多面体に対応させること
- Permutohedron上の低次元多面体を一塊として扱うということは、それらを区分している壁(仕切り)をないものとみなすことに相当するから、その「取り払うべき壁」をリストアップすることが、「分割」に相当する
- これは、別の角度から見ると、次のように表現できる
  - Permutohedronは、扇(fan)構造で捉えることが出来る。Permutohedronそのものに対応するfanに対して、「壁をとりはらったPermkutohedron」は、Coarsened fanという構造に対応させることができる
- 壁のとりはらい、Coasened は条件付独立を順列にあてはめることにも対応させることができる。この条件付独立はsemi-graphoid と呼ばれる形式での表現も可能であることが知られている
- Permutohedronは多次元多面体であって、３次元に生きる身としては時として、イメージするのに困難が伴うが、その隣接条件等は、順列同士の関係を定める上で有用である
- またSemi-graphoicな捉え方は、グラフ的取り扱いを許し、次元が２次元になった分の複雑さの増加はあるが、「くくり」や「多次元での位置に関する情報を『表現ルール』として取り扱うことができる利点があり、それはさらに、アルゴリズム化する方向への親和性が上がり、実際にアルゴリズムに下ろすことが試されている。
- その過程でさらに登場してくる考え方に、劣モジュラ関数などがある
Permutahedronの図