グレブナー基底と統計への応用

グレブナー基底と統計への応用
経済学研究科岡島匡宏
グレブナー基底とは
◦ 1960年代に廣中平祐とBruno Buchbergerの論文によって独立に導入
された概念
◦ 当初は純粋に数学的な目的から発展
◦ 1980年代後半には計算機理論や応用数学が見られはじめる
1998年Diaconis, Sturmfelsの論文でMCMCへの応用が行われるよう
になった
→ 本発表のテーマ
グレブナー基底とは
多項式環𝐾𝐾 𝕩𝕩 = 𝐾𝐾[𝑥𝑥1 , 𝑥𝑥2 , ⋯ , 𝑥𝑥𝑛𝑛 ]の単項式順序＜を固定し、𝐼𝐼を𝐾𝐾 𝕩𝕩 の0
でないイデアルとする。
グレブナー基底とは、多項式の集合{𝑔𝑔1 , 𝑔𝑔2 , ⋯ , 𝑔𝑔𝑛𝑛 } ∈ 𝐼𝐼となるもので、
{𝑖𝑖𝑖𝑖< 𝑔𝑔1 , 𝑖𝑖𝑖𝑖< 𝑔𝑔2 , ⋯ , 𝑖𝑖𝑖𝑖< 𝑔𝑔𝑛𝑛 }がイニシャルイデアル𝑖𝑖𝑖𝑖< 𝐼𝐼 の生成系と
なるもの。
グレブナー基底の計算
Buchberger判定法とBuchbergerアルゴリズムを用いる。
定理(Buchberger判定法)
多項式環𝐾𝐾 𝕩𝕩 の、 0 とは異なるイデアル𝐼𝐼の生成系{𝑔𝑔1 , 𝑔𝑔2 , ⋯ , 𝑔𝑔𝑠𝑠 }が𝐼𝐼のグレブ
ナー基底となるためには、次の条件が必要十分
任意の𝑖𝑖 ≠ 𝑗𝑗について、𝑔𝑔𝑖𝑖 , 𝑔𝑔𝑗𝑗 のS多項式𝑆𝑆(𝑔𝑔𝑖𝑖 , 𝑔𝑔𝑗𝑗 )は𝑔𝑔1 , 𝑔𝑔2 , ⋯ , 𝑔𝑔𝑠𝑠 に関して割った
ときに余りが0になる (0に簡約可能)
グレブナー基底の計算
Buchbergerアルゴリズム
1, 多項式環𝐾𝐾 𝕩𝕩 の 0 とは異なるイデアル𝐼𝐼の生成系 𝑔𝑔1 , 𝑔𝑔2 , ⋯ , 𝑔𝑔𝑠𝑠 があり、そ
の生成系すべてのS多項式が𝑔𝑔1 , 𝑔𝑔2 , ⋯ , 𝑔𝑔𝑠𝑠 に関して0に簡約可能であれば、
𝑔𝑔1 , 𝑔𝑔2 , ⋯ , 𝑔𝑔𝑠𝑠 はグレブナー基底である。
2,そうでない場合S多項式を𝑔𝑔1 , 𝑔𝑔2 , ⋯ , 𝑔𝑔𝑠𝑠 で割った余りを𝑔𝑔𝑠𝑠+1 とする。余り𝑔𝑔𝑠𝑠+1
は𝐼𝐼に含まれることから 𝑔𝑔1 , 𝑔𝑔2 , ⋯ , 𝑔𝑔𝑠𝑠 , 𝑔𝑔𝑠𝑠+1 を𝐼𝐼の生成系と考え、Buchberger判
定法を適用する。
3,上記のプロセスを繰り返すことで、グレブナー基底を計算することができる。
グレブナー基底と統計
Diaconis, Sturmfels(1998)で提案されたマルコフ連鎖モンテカルロ法
へのグレブナー基底の応用が始まった。
この論文ではI×Jの分割表における行と列の独立性の検定におけ
るp値をMCMCによって求める際の、新手法を提案した。
マルコフ連鎖の推移行列を構成す際に、その推移行列の基底をマ
ルコフ基底として定義し、マルコフ基底をグレブナー基底の理論に
よって計算することで、グレブナー基底を統計へと応用する手法を
確立した。
マルコフ連鎖の構成
MCMCでは定常分布が帰無分布に一致するような,つまり
𝜋𝜋 = 𝜋𝜋𝑄𝑄
となるようなマルコフ連鎖の推移行列Qを構成する必要がある。
そこで、マルコフ基底の概念を導入する。
マルコフ基底
分割表それ自体の行列を𝐼𝐼𝐼𝐼 × 1 の列ベクトル𝕩𝕩 として扱う。ここで、
相似検定において固定される、十分統計量を、
𝕥𝕥 = 𝐴𝐴𝕩𝕩
と書く。ここで𝐴𝐴は整数を成分とする行列で、配置行列と呼ぶ。
このとき、𝕥𝕥 , 𝐴𝐴が与えられたときのマルコフ連鎖の状態空間は
ℱ𝕥𝕥 = 𝕩𝕩|𝐴𝐴𝕩𝕩 = 𝕥𝕥, 𝕩𝕩 の成分 ∈ {0,1,2, ⋯ }
とできる。これを𝕥𝕥-ファイバーと呼ぶ。
マルコフ基底
また、Aから定まる集合を以下で定義する。
ℳ 𝐴𝐴 = 𝕫𝕫| 𝐴𝐴𝕫𝕫 = 0, 𝕫𝕫の成分 ∈ 0, ±1, ±2, ⋯
この集合はマルコフ連鎖の推移ステップに対応しており、この集合の要
素をAに関するmoveと呼ぶ。
マルコフ基底
定義
ℬ ⊂ ℳ 𝐴𝐴 が𝐴𝐴に対するマルコフ基底であるとは、任意の𝕥𝕥に対して、ℱ𝕥𝕥 の任意の要
素がℬによって相互に到達可能であることをいう。
これによってマルコフ基底が定義されたが、これがグレブナー基底
の理論と強い結びつきを持つ。
マルコフ基底とグレブナー基底
定理
ℬ = 𝕫𝕫1 , ⋯ , 𝕫𝕫𝐿𝐿 ⊂ ℳ 𝐴𝐴
+
−
𝕫𝕫
𝕫𝕫
𝑖𝑖
が𝐴𝐴に対するマルコフ基底であることは、{𝕦𝕦 − 𝕦𝕦 𝑖𝑖 , 𝑖𝑖 = 1,2, ⋯ }
が𝐴𝐴に関するイデアル𝐼𝐼𝐴𝐴 の生成系であることと必要十分である
これにより、グレブナー基底を計算することでマルコフ基底を構成するこ
とができる。
マルコフ連鎖の構成
求めたマルコフ基底に対し、マルコフ連鎖を以下のように構成する
◦ 連鎖の各状態𝕩𝕩 + 𝜀𝜀𝜀𝜀 ∈に対して、マルコフ連鎖の要素𝕫𝕫 ∈ ℬと符号𝜀𝜀 =
{−1. +1}をランダムに選び、𝕩𝕩 + 𝜀𝜀𝜀𝜀 ∈ ℱ𝕥𝕥 であればそこに移動する、𝕩𝕩 + 𝜀𝜀𝜀𝜀 ∉
ℱ𝕥𝕥 であれば𝕩𝕩にとどまる
このように構成されたマルコフ連鎖は既約で、対称となる。
以上でグレブナー基底を用いたマルコフ連鎖の構成を行うことができる。
まとめ
本日発表した手法はグレブナー基底の統計への応用法の中でもっ
とも基礎的なもので、「計算代数統計」という分野を拓いた。
しかし、課題も多い。実際にコンピュータにBuchbergerアルゴリズム
を実装する際には、計算量が多いことが問題となる。
また、今回は2次元の分割表を取り扱ったが、3次元以上となるとマ
ルコフ基底の計算が困難となることが知られている。

Download Report