知識メディア特論（後半第１回）
北海道大学 大学院 情報科学研究科
情報理工学専攻
知識メディア研究室 湊 真一
知識メディア特論 今年度講義予定
• 前半 （担当：瀧川 准教授）
– 確率分布の概念と統計モデリング技法
– 種々の統計モデルとその推論アルゴリズム
• 後半 （担当：湊 教授）
– 大規模離散構造データ処理の技法
– BDD/ZDDおよびその応用
2015.11.27
知識メディア特論
2
後半の講義内容（予定）
•
•
•
•
•
•
•
第１回 (2015.11.27)
第２回 (2015.12.02)
第３回 (2015.12.11)
第４回 (2015.12.16)
第５回 (2015.12.21)
第６回 (2016.01.08)
第７回 (2016.01.22)
知識表現と二分決定グラフ（BDD）
BDD処理系の実装技術
BDDの変数順序づけ
ゼロサプレス型BDD（ZDD)
ZDDの応用
文字列や順列を扱うZDDの拡張
ZDDとグラフ列挙索引化
講義スライドURL：
http://art.ist.hokudai.ac.jp/~minato/km2015.html
2015.11.27
知識メディア特論
3
次回の講義
• 来週12/4(金)は、情報理工学専攻の修論中間発表会と
重なるため、講義日時を変更します。
12/2(水) ３限 講義室：A13
• その他の変更予定（まだ確定ではありません）
– 12/18(金) 12/16(水) ３限？（講師出張のため）
– 12/25(金) 12/21(月) ５限（集中講義と重なるため）
– 1/29(金) 休講 （集中講義と重なるため）
2015.11.27
知識メディア特論
4
本日（第１回）の内容
知識表現と二分決定グラフ（BDD）
• 論理関数と知識表現
– 論理関数を扱う場面、論理式と論理関数、命題論理と述語論理
• 論理関数の処理とは
– 論理式/回路からの論理関数データ生成、各種論理演算
– 恒真/恒偽判定、等価性判定、包含性判定、充足解探索
• 論理関数の表現法
– 求められる性質
– 関数の総数・情報理論的ビット量
– カルノー図、真理値表、積和形、BDD
• 二分決定グラフ（BDD）の基本構造とその性質
2015.11.27
知識メディア特論
5
論理関数とは
• 関数(Function)：
集合A（定義域）から集合B（値域）への写像、かつ
Aの要素に対してBの要素がただ１つに定まる関係のことをいう。
• 論理関数（Logic Function / Boolean Function）：
B={0,1}のとき、 f: Bn→B という関数 f を論理関数
（正確には二値論理関数。Switching Functionとも呼ぶ）
• 一般には多値論理関数(Multi-valued Boolean Function)もある。
X
x1
x2
論理関数
f(X)
xn
入力(input)
2015.11.27
出力(output)
知識メディア特論
6
論理関数とは
• 関数(Function)：
集合A（定義域）から集合B（値域）への写像、かつ
Aの要素に対してBの要素がただ１つに定まる関係のことをいう。
• 論理関数（Logic Function / Boolean Function）：
B={0,1}のとき、 f: Bn→B という関数 f を論理関数
計算機が扱う知識表現の中で、
（正確には二値論理関数。Switching
Functionとも呼ぶ）
最も基本的・汎用的なモデルの１つ
• 一般には多値論理関数(Multi-valued
Boolean Function)もある。
X
x1
x2
論理関数
f(X)
xn
入力(input)
2015.11.27
出力(output)
知識メディア特論
7
論理関数を扱う場面（１）：論理回路設計
• VLSIの論理回路の設計・最適化
– 携帯電話の小型化・低電力化
– マイクロプロセッサの高速化・低電力化
• 設計検証
– 設計に誤りがないことを数学的に証明
X
x1
x2
論理関数
f(X)
xn
入力(input)
2015.11.27
出力(output)
知識メディア特論
8
論理関数を扱う場面（２）：機械学習
• データを分類する装置の設計・最適化
– 任意の入力のビットパタンに対して、Yes/No のいずれかを
返す装置を設計する。
– 学習データ（入力データと模範解答）を与えて、論理関数
を徐々に変化させて、理想的な分類をする機械を自動的に
作り出そうというアプローチ
X
x1
x2
論理関数
f(X)
xn
入力(input)
2015.11.27
出力(output)
知識メディア特論
9
論理関数を扱う場面（３）：データマイニング
• 大量のデータを処理して、興味深い知識を発見
– 例えば、商店のレジのデータを分析して、来店者が頻繁に
購入する商品の組合せを抽出する。
– 商品の種類をnとし、顧客のカゴに入っている商品組合せを
0,1のビットパタンで表現し、頻出かどうか（または興味深
いパタンかどうか）をYes/Noで出力する。
X
x1
x2
論理関数
f(X)
xn
入力(input)
2015.11.27
出力(output)
知識メディア特論
10
論理関数を扱う場面（４）：制約充足問題
• 世の中の様々な問題は、ある制約条件を満たすよう
な入力パタンを求めよ、という問題に翻訳できる。
– ある入力パタン（0,1のビット列）が問題の解に含まれるか
どうかをYes/Noで答える論理関数となる。
– 与えられた問題を解くためにその部分問題を考えることが
しばしばあり、様々な論理関数を扱う必要が生じる。
X
x1
x2
論理関数
f(X)
xn
入力(input)
2015.11.27
出力(output)
知識メディア特論
11
論理関数と命題論理・述語論理
• 命題論理(Propositional Logic)：
真/偽を表す命題(proposition)変数とそれらの論理演算からなる式。
二値論理関数と等価な概念
（例） 大学生ならば人間である
（Student⇒Human) ≡ （~Student + Human）
• 述語論理(Predicate Logic):
述語(predicate)とそれらの論理演算からなる式。述語は主語に当
たる変数（二値とは限らない）を持つ。二値論理関数よりも高度な
概念
（例） X が大学生ならば X は人間である：
(Student(X)⇒Human（X）) ≡ (~Student(X) + Human(X))
2015.11.27
知識メディア特論
12
論理式(Boolean Expression)と論理関数
• 論理式（Boolean Expression）： 論理変数と論理演算
（AND,OR,NOT等）の組合せで書かれた数式
１つの論理式は１つの論理関数を表現している
(例) F = a b + a ~c + ~a b c + d
a
abcd F
b
11-- 1
a
~c
1-0- 1
~a
b
011- 1
c
---1 1
d
F
複数の異なる論理式が同じ論理関数を表す場合がある
(例) F1 = x ~y + x z + ~x y + ~x ~z
F2 = x ~y + ~x y + y z + ~y ~z
F3 = x ~y + ~x ~z + y z
2015.11.27
知識メディア特論
13
論理演算子の記法の例
• 論理演算子には様々な書き方があり、
教科書によって異なる。
xy
x・y
x∧y
x+y
x|y
x∨y
AND（論理積）：
OR（論理和）：
NOT（否定）：
~x
￢x
!x
EXOR（排他的論理和）： x + y
2015.11.27
知識メディア特論
x&y
x
x↑y
x^y
14
論理関数の処理とは（１）
現実の様々な知識処理の中で必要となる論理関数の操作
• 論理式/論理回路から論理関数データを作る操作
（２つの論理関数データ同士の演算）
XY: F
00: 0
10: 1
01: 0
11: 1
XY: F
00: 1
10: 1
01: 0
11: 0
XY: F
00: 1
10: 0
01: 1
11: 1
XY: F
00: 0
10: 1
01: 1
11: 0
X
Y
XY: F
00: 0
10: 0
01: 1
11: 1
2015.11.27
XY: F
00: 1
10: 0
01: 1
11: 0
XY: F
00: 1
10: 1
01: 0
11: 1
知識メディア特論
15
論理関数の処理とは（２）
• 恒真/恒偽判定 （ co-NP完全問題）
（例） x y + ~x + ~y ~z + z
• 等価性判定 (F≡G) ⇔ (F G + ~F~G ≡ 1)
x~y + x z + ~x y + ~x~z
x~y + ~x y + y z + ~y ~z
x~y + ~x~z + y z
• 包含性判定 (F⇒G) ⇔ (~F + G ≡ 1)
• 充足解探索:
– 与えられた論理関数が１になるような変数値の組合せをどれか
１つ求める問題 （ NP完全問題）
– 最適化問題：充足解の中で最もコストが小さい（または大きい）
解を求める問題 （ NP完全問題）
2015.11.27
知識メディア特論
16
小規模な論理関数を表現する方法
xy
zw
00
01
11
10
00
1
1
0
0
01
0
1
1
1
11
1
1
1
1
x
y
10
1
0
0
0
z
カルノー図表現
F
論理回路図表現
• 人間の目で見通しが良い図的表現が
多く使われていた。
2015.11.27
知識メディア特論
17
計算機上での論理関数表現の要求条件
• 表現がコンパクトであること
n
通り存在。
→ 固定長データで識別するには
n
少なくとも2 ビットは必要。（例：真理値表）
– 現実には全ての論理関数が均等に現れる訳ではない。
→ よく現れる関数がコンパクトに表現できる
可変長データが使われる。
–
n入力の論理関数は22
• 論理演算処理が高速に行えること
– ２つの論理関数データの等価性判定が高速に行えるか
– AND, OR, NOT等の論理演算が効率よく実行できるか
• 人間が見やすいことはあまり重要でない。
2015.11.27
知識メディア特論
18
真理値表表現
x1x2x3 … xn
F1
F2
F3
000 … 0
100 … 0
010 … 0
110 … 0
001 … 0
101 … 0
011 … 0
1
0
1
0
1
0
1
0
1
1
0
1
1
1
1
0
0
0
0
0
0
111 … 1
1
0
0
2015.11.27
• カルノー図と本質的には同じだが、
見やすく並べる必要はない
（単純１次元配列）
• ベクトル計算・並列計算に向く
• どんな簡単な論理関数にも、入
力数に対して指数の記憶量と時
間を要する（30変数程度が限界）
• どんな複雑な（ランダムな）論理
関数でも同じ時間で処理できる
知識メディア特論
19
積和形論理式
ab + ac + abc + d
a
b
a
c
a
b
c
d
F
abcd
11-1-0011---1
2015.11.27
F
1
1
1
1
• 肯定・否定の２種類の入力変数を
用いた積和２段の論理式で表す
方法。
• 記憶量は論理式に現れる文字数
にほぼ比例。
• 簡単な式でかける論理関数は効
率よく処理できる。
• 表現が一意でなく等価性判定に
時間がかかる。
• 否定演算やXOR演算が苦手
• BDDが出現するまでは最も多く使
われた（今も使われている）
知識メディア特論
20
BDD（二分決定グラフ）
「論理関数」の表現と
演算処理の技法
a
1
簡約化
（圧縮）
0
0
c
1
0
b
a
0
1986年に画期的なBDD演算
アルゴリズムを提案。以後急速
にBDD技術が発達。
（長期間、情報科学の全分野
Bryant (CMU) での最多引用文献となった）
1
b
b
1
c
c
0
1
（BDD）
1
0
1
0
1
BDD
BDD
c
c
0
1
1
（場合分け二分木）
・ 場合分け二分木グラフを簡約化（圧縮）
・ 多くの実用的な論理データをコンパクト
かつ一意に表現。
（数百倍以上の圧縮率が得られる例も）
21
2015.11.27
知識メディア特論
BDD
BDD
AND
BDD
BDD
BDD同士の論理演算
（圧縮データ量にほぼ
比例する計算時間）
近年のPC主記憶の大規模化により、
BDDの適用範囲が拡大
（特に2000年以降）
BDD（Binary Decision Diagram)
（二分決定グラフ）の例
a
a
a
1
0
b
b
c
c
1
0
1
0
c
c
0
1
0
1
真理値表と等価なBDD
(Binary Decision Tree)
2015.11.27
c
1
1
0
0
1
1
0
0
1
0
b
c
1
既約な順序付きBDD
(Reduced Ordered BDD)
知識メディア特論
c
b
b
1
0
1
0
0
1
1
既約でも順序付き
でもないBDD
(Unordered BDD)
22
BDDの節点(node)と枝(edge)
•
•
•
•
•
分岐節点（decision node)
終端節点(terminal node)
0-枝(0-edge)
1-枝(1-edge)
部分グラフ(sub-graph)
シャノンの展開(Shannon’s expansion)
a
b
c
1
0
0
1
F
0
v
1
F(v, X) = ~v F(0, X) + v F(1, X)
F0
2015.11.27
知識メディア特論
F1
23
ROBDD (Reduced Ordered BDD)
• 同じ論理を表すBDDは複数存在
• 順序付きBDD：
– 変数に全順序関係が定義されている
– 根(root)から定数節点に至るすべてのパスについて
変数の出現順序が、全順序関係に矛盾しない
• 既約なBDD
– BDDの２つの簡約化規則がこれ以上適用できなくなるまで
適用されている形
• 重要な性質を持つのは既約な順序付きBDD(ROBDD)
– 以後、特に断らない限り、ROBDDのことを単にBDDと呼ぶ。
2015.11.27
知識メディア特論
24
BDDの簡約化規則
(a)
x
（削除）
(a) 冗長な節点を全て削除
(b) 等価な節点を全て共有
f
f
既約なBDDが得られる
(b)
x
f0
2015.11.27
x
f1
x
f0
（共有）
f1
参考：
(b)の規則だけを可能な限り適用した形を
「準既約」(Quasi-reduced)なBDD
と呼ぶこともある。
知識メディア特論
25
BDDの簡約化の例
• どの部分から簡約化を行っても最終形は同じ
• 論理関数に対する一意な表現（標準形）となる
– ただし変数順序が異なると同じ論理でも違う形になる
（偶然一致する場合もあるが）
c
1
0
2015.11.27
1
0
1
c
c
c
0
1
b
b
b
b
b
c
a
a
a
1
1
c
c
0
知識メディア特論
1
1
0
1
26
BDDの節点数
n
2
2 種類存在する。
• n入力の論理関数は
これを識別するには少なくとも 2nビットの記憶量が必要。
• BDDでも例外ではない。n変数論理関数を表現するための
最悪の場合の節点数は O(2n/n)となる。
– 1個の節点を記憶するのにO(n)ビット必要なので、
全体としてはO(2n)ビットとなる。
• ただし、実用上よく用いられる多くの論理関数について、
nの多項式に比例する節点数になることが示されている。
2015.11.27
知識メディア特論
27
n変数の論理積・論理和・パリティ
x2
x2
x3
x3
0
x1
x1
x1
x4
x4
1
0
論理積(AND)
1
論理和(OR)
x2
x2
x3
x3
x4
x4
0
1
排他的論理和・
パリティ(EXOR)
• いずれも、nに比例する節点数 O(n) で表現可能
• 0と1の定数節点を入れ替えるとそれぞれの否定論理になる
2015.11.27
知識メディア特論
28
nビット２進数の算術加算
３ビット加算器の論理関数のBDD
（変数は a2, b2, a1, b1, a0, b0, c0 の順）
S2
C
S1
S0
• nが増えてもBDDは縦方向に伸びるだけで幅は一定
→ 節点数は O(n)
• 減算も同じく O(n) となる。２進数の大小比較も O(n)
2015.11.27
知識メディア特論
29
BDDの圧縮効果
• 8入力データセレクタ
制御入力を上位にした場合
データを上位にした場合
O(n)
2015.11.27
O(2n)
知識メディア特論
30
BDDの生成アルゴリズム
a
a
b
b
c
c
1
0
簡約化
1
0
1
c
c
0
0
0
c
1
1
1
F = a b + ~c
1
直接生成
b
1
0
0
1
• 真理値表に対応する二分木を簡約化する方法では、
常に指数オーダの記憶量と処理時間がかかってしまう。
実用的には、論理式からBDDを直接生成
するアルゴリズム[Bryant86]を用いる
2015.11.27
知識メディア特論
31
論理式からのBDD生成
a
ab
a
0
1
a
1
0
b
AND
演算
1
0
0
b
1
b
0
1
0
1
0
NOT
演算
c
OR
演算
a
1
0
0
c
0
1
0
0
1
1
2015.11.27
a b + ~c
1
~c
c
• ２つのBDDの間の二項論
理演算を繰り返して任意の
BDDを生成
（圧縮データ量にほぼ比例
する計算時間で実行可能）
c
1
1
0
知識メディア特論
0
b
1
0
1
32
BDDの特徴
• 論理関数に対してグラフの形が一意に定まる。
– 等価性判定が非常に容易
• 多くの実用的な論理関数がコンパクトに表現できる。
– パリティ関数や加減算回路も効率よく表現
– 性質の良い関数では数百入力まで扱える
• 論理関数同士の演算が、グラフのサイズにほぼ比例す
る計算時間で実行できる。
– 否定演算も容易
• グラフのサイズが小さくならない場合もある。
– 乗算回路のBDDは指数サイズ
• 変数の順序づけが悪いとグラフが大きくなる。
– 比較的良い順序づけを得る方法がいくつか実用化
（厳密最小化はNP完全問題）
2015.11.27
知識メディア特論
33
BDDパッケージ
• BDD処理系は世界各地の研究機関で1990年頃から盛んに
開発された。
– BDDパッケージとして無料配布されている物もいくつかある。
• 多くの場合、CまたはC++のライブラリとして提供されている。
– BDDへのポインタを引数としてライブラリ関数を呼び出すと、
メモリ上にBDDが生成され、新しいBDDへのポインタが
返り値として戻ってくる。
– ユーザはBDDの論理演算を呼び出すメインプログラムを書き、
BDDパッケージをリンクしてコンパイルすると、BDD処理アプリ
ケーションを作ることができる。
• BDDパッケージの実装技術については次回詳しく解説する。
2015.11.27
知識メディア特論
34
今回のまとめ
知識表現と二分決定グラフ（BDD）
• 論理関数と知識表現
– 論理関数を扱う場面、論理式と論理関数、命題論理と述語論理
• 論理関数の処理とは
– 論理式/回路からの論理関数データ生成、各種論理演算
– 恒真/恒偽判定、等価性判定、包含性判定、充足解探索
• 論理関数の表現法
– 求められる性質
– 関数の総数・情報理論的ビット量
– カルノー図、真理値表、積和形、BDD
• 二分決定グラフ（BDD）の基本構造とその性質
2015.11.27
知識メディア特論
35
演習問題
1. 4入力パリティ関数
（１の個数が奇数個のときに１を出力する関数）
を、カルノー図および積和形論理式で表現せよ。
2. 以下の３つの論理式が等価であるかどうかを、
なるべく効率よく判定するにはどうしたら良いか、
考えよ。
x~y + x z + ~x y + ~x~z
x~y + ~x y + y z + ~y ~z
x~y + ~x~z + y z
2015.11.27
知識メディア特論
36
© Copyright 2024 ExpyDoc
