2012-11-03

BDD/ZDD

離散構造 ZDD BDD 集合シークエンス組合せ代数 Simpath

日本語総説はこちら
組合せ発散に対する、この方法の効果はこちらの動画と実行例コードで
BDD:binary decision diagram
- $k$ 個の２分岐が $2^k$ の場合を作る。それを表したのが二分決定木(binary decision tree)
- BDDは二分決定木を簡略したグラフ
- $\{a,b,c\}$ の３分岐の「○、×」が作る $2^3$ の場合のうち、 $(a(+)b(-)c(+),a(-)b(+)c(-))$ の２通りが「あり」だという情報があるとする。 $\{ac,b\}$ というように $\{a,b,c\}$ のべき集合の２つの要素の集合(『組み合わせ集合』)とみなすこともできる
ZDD:zero-suppressed bdd
- 二分決定木からBDDを作るのには、ルール(アルゴリズム)がある。それは「(ある目的に沿って)簡略化する方法」のこと
- 「簡略化する方法」は一つではない。ZDDはBDDと異なるルール(アルゴリズム)で簡略して作るダイアグラム
- 組合せ集合の取り扱いに効果的である方法である
seqBDD
- 組合せ集合に向いているのがZDDなら、順列集合に向いているものがあってもよい
- それがseqBDD
BDD/ZDD/seqBDDの代数系
- ダイアグラムができても、それをハンドリングするのが便利でないと、使いにくい
- 特に組合せ発散対策ならなおのこと
- そのための「ハンドリング」ツールが「BDD/ZDD/seqBDDの基本演算(とそれが作る代数構造)」
- いわゆる集合演算が、計算機処理的な色を付けて拡張されたもの
この話題の周辺のことで、メモしておきたいこと
- 空集合と、要素数がゼロの集合のこと
  - 『組み合わせ集合』を扱うと、上記２つの区別が必要となる。その表記は、(たとえば) $\phi,\{\lambda \}$ とできる
- 集合の演算
  - 結び集合、交わり集合、差集合、直積集合、商集合、剰余集合
- 集合取扱いのための処理
  - 集合の要素数を数える、「最上位」の取り出し・取り外し、要素集合の反転
- 出現頻度・出現組合せ情報の『組み合わせ集合』的取扱い
  - 頻度閾値に対して、その閾値以上の頻度の組み合わせを『組み合わせ集合』として保持する
- 要素の頻度をZDDで表す
  - 組合せ頻度表におけるZDDベクトル表記
BDD/ZDD/seqBDDの応用
- ZDDによるパス列挙
  - Kunuth先生によるSimpath
  - ZDD演算規則を介さずにZDDを作成(こちら)
- 言語解析にseqBDD(こちら)
- 単体のZDD
  - $\{a,b,c,d\}$ を要素全体としたときに $\Gamma(a,c,d)$ で表される単体に対応するZDD

- - $a,b,c,d$ の順序をうまく取ると、「最もシンプルな」ダイアグラムになる
- いかにもAncestral recombination graph的な絵も描ける
- 「0,1」を「ケース・コントロール」と読めば、ケース・コントロール解析。そのときの分岐要素は「遺伝的要素・環境的要素」
- たくさんのアイテムのうち、どのようなアイテムの組み合わせが関係するか、と考えれば、『兆候』を用語リストと関係づける仕組みであり、『診断名』と用語リストを関係づける仕組み
  - しかも、「頻度情報」を乗せられる