はじめまして！ m_ishihata です！
TL を見ていると、文字列アルゴリズム Advent Calendar 2017 に空きが出ており、
担当者が見つからないようなのでかわいそうなので適当なネタを投稿することにしました。
慌てて書いたので品質はお察しください。
前置き
この記事は 文字列アルゴリズム Advent Calendar 2017 の 12/22 の記事です。
この内容は言うほど文字列ではないですが、１０日目の BDDとZDD -ブール関数と集合族の圧縮処理- の応用なので許されるはずです。
また、本内容は 情報系 Winter Festa Episode Ⅲ でも話す予定です。
一言概要
この記事の目的は 「Decision Diagram 上で効率的に計算できる量を考察する」 ことです。
※ Decision Diagram (DD) については この記事 を参照ください。
問題設定
この記事では 「制約が与えられた元で最適化や特定の量を計算する」 ことを目標とします。
例
例えば、あなたはこれから修学旅行に行くとします。
そうすると以下のような問題に直面するはずです。
(a) 300円という限られたお小遣いの中で、満足度を最大化したい。
(b) 自宅から集合場所への経路の中で、所要時間を最小化したい。
(c) バスで隣の席の A に「B は実は C が好き」という秘密を教えたとき、それが C まで伝わるリスクを求めたい。
実はこれらの全ての問題は、次の定式化で記述できます。
定式化
Given:
- 目的関数 $f : \{0,1\}^d \rightarrow \mathbb{R}$
- 確率分布 $p : \{0,1\}^d \rightarrow [0,1]$
- 制約関数 $c : \{0,1\}^d \rightarrow \{0,1\}$
Objective の例:
1. 制約付き最大化: $x^* := \arg\max \left\{f(x) : c(x) = 1 \right\}$
2. 制約充足確率: $p(c) := \sum \left\{p(x) : c(x) = 1 \right\}$
3. 制約付き期待値: $E_p[f|c] := \sum \left\{f(x)p(x|c) \right\}$
(a) おやつの例
おやつ候補が $d$ 個あり、各おやつの値段を $w_i$ ($i \in [d]:=\{1,\dots,d\}$)、それを食べて得られる満足度を $v_i$ とします。
また、許されているおやつ代を $B$ とします。
$x \in \{0,1\}^d$ において、$x_i = 1$ でおやつ $i$ を買うことを表すとします。
すると $f, c$ をそれぞれ以下のように定義すれば、問題(a)は上記の objective 1 を求める問題となります。
- $f(x) = \sum \left\{ v_i x_i : i \in [d] \right\}$
- $c(x) = \delta\left( \sum \left\{ w_i x_i : i \in [d] \right\} \leq B\right)$
ここで $\delta(z)$ は命題 $z$ が真であるときに 1 を、偽であるときに 0 を返す関数とします。
この問題は ナップサック問題 と呼ばれます。
(b) 経路の例
無向グラフ $G = \langle V, E \rangle$ を地図とし、$V$ を頂点（交差点)の集合、$E := \{e_1,\dots, e_d\}$ ($e_i \in V\times V$) を辺（道) の集合とします。
道 $e_i$ を通過するのに要する時間を $t_i$ とします。
$x \in \{0,1\}^d$ において、$x_i = 1$ で辺 $e_i$ を採用することを表し、$E(x) := \{e_i : x_i = 1\}$ とします。
すると $f, c$ をそれぞれ以下のように定義すれば、問題(b) は上記の objective 1 の最小化版となります。
- $f(x) = \sum \left\{ t_i x_i : i \in [d] \right\}$
- $c(x) = \delta\left( \text{$E(x)$ は自宅から集合場所への経路である} \right)$
この問題は 最短経路問題 と呼ばれます。
(c) 噂の例
有向グラフ $G = \langle V, E \rangle$ をクラスの友人関係ネットワークとします（有向であるところに多少闇を感じます。）
$V$ をクラスメートの集合、$E := \{e_1,\dots,e_d\}$ を有向辺の集合とします。
辺 $e_i = (u,v)$ において、$\theta_i$ を $u$ から $v$ に噂が流れる確率とします。
すると $p, c$ をそれぞれ以下のように定義すれば、問題(c) は上記の objective 2 を求める問題となります。
- $p(x) = \prod \left\{ \theta_i : e_i \in E(x) \right\} \prod \left\{ (1-\theta_i) : e_i \in E \backslash E(x) \right\}$
- $c(x) = \delta( \text{誘導グラフ $G[E(x)]$ において、A から C への有向パスが存在する} )$
この問題は ネットワークの信頼性評価問題 と同じです。
計算量
上記で定めた objective 1-3 は、一般の f, p, c に対しては NP-hard です。
しかし、f, p, c のクラスを限定することで効率的に解ける場合があります。
例えば、よく考えがちなクラスは以下のとおりです。
- f: 線形関数、劣モジュラ関数
- p: 対数線形モデル、独立変数モデル
- c: サイズ制約、ナップサック制約、マトロイド制約
例えば、 objective 1 に関しては以下のことが知られています。
- f:線形関数 × c:ナップサック制約 は NP-hard だが Dynamic Programming により効率的に解ける。
- f:劣モジュラ関数 × c:サイズ制約 は NP-hard だが Greedy 法により 1-1/e 近似解が得られる。
そしてやっと主題ですが、この記事では 「c が DD で与えられているとき」 を考えます。
これを Decision Diagram constraint (DDC) と呼びます。
そして DDC 下では objective 1-3 が効率的に解けることを示します。
Decision Diagrams
Decision Diagram (DD) とは、論理関数（または集合族）のDAGによる表現です。
詳しくは BDDとZDD -ブール関数と集合族の圧縮処理- を読んで下さい。
ここでは、今後の話に必要な Shannon Expansion について説明します。
論理関数版 Shannon Expansion
$x_{1:d} \in \{0,1\}^d$ とし、 $c(x_{1:d})$ を制約関数（論理関数)とします。
制約関数 $c$ を表現する DD を $\Delta(c)$ と表します。
$\Delta(c)$ は以下の Shannon Expansion を再帰的に適用することで構成できます。
$$c(x_{1:d}) = \delta(x_d=1) c_{d,1}(x_{1:d-1}) + \delta(x_d=0) c_{d,0}(x_{1:d-1})$$
ここで $c_{d,b}(x_{1:d-1}) := c(x_{1:d-1}, x_d=b)$ は Shannon Co-factor と呼ばれ、
$c(x_{1:d})$ の $x_d$ に値 $b$ を代入することで得られる部分関数を表します。
2つの Shannon Co-factor $c_{d,0}$ と $c_{d,1}$ を表現する DD $\Delta(c_{d,0})$ と $\Delta(c_{d,1})$ が与えられたとします。
すると $\Delta{c}$ はそれらの DD を新たな決定ノードでつなぐだけで得られます。(詳細略)
集合族版 Shannon Expansion
制約関数 $c$ は、集合族の表現型と捉えることもできます。
$I_x := \{i \in [d] : x_i = 1\}$ を $x$ が表す アイテムセット と呼びます。
$\Omega(c) := \{I_x : c(x) = 1\}$ を $c$ が表す アイテムセット集合 と呼びます。
すると shannon co-factor $\Omega(c_{d,b})$ は常に以下を満たします。
- $\Omega(c_{d,1}) = \{I - d : I \in \Omega(c), d \in I\}$
- $\Omega(c_{d,0}) = \{I : I \in \Omega(c), d \not\in I\}$
ここで $I - d := I \backslash \{d\}$ です。
これより、上記の Shannon Expansion を集合の言葉で書くと以下のようになります。
$$ \Omega(c) = d \times \Omega(c_{d,1}) \cup \Omega(c_{d,0}) $$
ここで $d \times \Omega(c_{d,1}) := \{I + d : I \in \Omega(c_{d,1})\}$、
$I + d := I \cup \{d\}$ です。
以後簡単のため、$x \in \Omega(c)$ と書いたとき、$I_x \in \Omega(c)$ を表すことにします。
Dynamic Programming on Decision Diagrams
制約関数 c を表現する Decision Diagram $\Delta(c)$ が与えられているとします。
これを Decision Diagram Constraint (DDC) と呼ぶことにします。
ではどのような量が DDC の元で効率的に計算できるのでしょうか？
実は、これを判定するのは容易で、計算したい量の定義式に上の Shannon Expansion の式をぶち込んで、
再帰式を得られればOKです。
問題設定
この記事では以下のクラスを考えることにします。
- $f(x_{1:d}) = \sum \left\{ w_i x_i : i \in [d] \right\}$
- $p(x_{1:d}) = \prod \left\{ \theta_i : x_i = 1\right\} \prod \left\{ (1-\theta_i) : x_i = 0 \right\}$
- $c(x_{1:d}) = \Delta(c)$ で定義される
つまり $f$ は線形関数、$p$ は $x_i$ が独立な確率変数であるようなモデルとします。
ここでは再帰をするので明示的に $x$ のインデックスを書くことにします。
このときに objective 1-3 が DD を用いて効率的に計算可能か確認してみましょう。
1. 制約付き最大化
記述を簡単にするため、以下の max を求める問題を説明します。
$$f^*(c) := \max \left\{f(x_{1:d}) : c(x_{1:d}) = 1 \right\}$$
まず、上式を $\Omega(c)$ を使って書いてみます。
$$f^*(c) := \max \left\{f(x_{1:d}) : x_{1:d} \in \Omega(c) \right\}$$
この左辺に集合版 Shannon Expansion を代入してみましょう。
\begin{align}
f^*(c)
&= \max \left\{ f(x_{1:d}) : x_{1:d} \in d \times \Omega(c_{d,1}) \cup \Omega(c_{d,0}) \right\}
\\
&=
\max
\left\{
\max \left\{f(x_{1:d}) : x_{1:d} \in d \times \Omega(c_{d,1}) \right\}
,~
\max \left\{f(x_{1:d}) : x_{1:d} \in \Omega(c_{d,0}) \right\}
\right\}
\end{align}
このように、$f^*(c)$ は Shannon Expansion により、２つの max の max の形で書けることがわかります。
ここで $f$ の線形性より以下を得ます。
\begin{align}
f^*(c)
&=
\max
\left\{
w_d + \max \{ f(x_{1:d-1}) : x_{1:d-1} \in \Omega(c_{d,1}) \}
,~
\max \{ f(x_{1:d-1}) : x_{1:d-1} \in \Omega(c_{d,0}) \}
\right\}
\\
&= \max \left\{w_d + f^*(c_{d,1}),~ f^*(c_{d,0}) \right\}
\end{align}
ということで無事に再帰式を得ることができました！
よって objective 1 の $f^*(c)$ は $\Delta(c)$ に比例する時間で計算可能です！
やったね！
2. 制約充足確率
同じ要領で Shannon Expansion を代入してみましょう！
\begin{align}
p(c)
&:=
\sum \left\{p(x_{1:d}) : x_{1:d} \in \Omega(c) \right\}
\\
&=
\sum \left\{p(x_{1:d}) : x_{1:d} \in d \times \Omega(c_{d,1}) \cup \Omega(c_{d,0}) \right\}
\\
&=
\sum \left\{p(x_{1:d}) : x_{1:d} \in d \times \Omega(c_{d,1}) \right\}
+
\sum \left\{p(x_{1:d}) : x_{1:d} \in \Omega(c_{d,0}) \right\}
\end{align}
今度は $p(c)$ は Shannon Expansion により、２つの sum の sum の形で表せることがわかります。
ここで $p$ の独立性より以下を得ます。
\begin{align}
p(c)
&=
\theta_d
\sum \left\{ p(x_{1:d-1}) : x_{1:d-1} \in \Omega(c_{d,1}) \right\}
+
(1-\theta_d)
\sum \left\{ p(x_{1:d-1}) : x_{1:d-1} \in \Omega(c_{d,0}) \right\}
\\
&= \theta_d p(c_{d,1}) + (1-\theta_d) p(c_{d,0})
\end{align}
ということでこちらも無事に再起式を得ることができました！
よって objective ２ の $p(c)$ も $\Delta(c)$ に比例する時間で計算可能です！
やったね！すごいぞDD！
応用編：
最後に応用として以下のトリッキーな量を考えてみましょう。
$$
E_p \left[\langle x_{1:d}, x_{1:d}' \rangle \mid c \right]
:=
\sum \left\{p(x_{1:d}|c)p(x_{1:d}'|c)\langle x_{1:d}, x_{1:d}'\rangle : x_{1:d}, x_{1:d}' \in \Omega(c) \right\}
$$
ここで$\langle x_{1:d}, x_{1:d}'\rangle := \sum_{i\in[d]} x_i x_i'$ です。
この量は $p(x_{1:d}|c) := c(x)p(x)/p(c)$ から独立に $x_{1:d}$ と $x_{1:d}'$ をサンプリングしたときに、
そのインターセクションのサイズ ($I_x \cap I_{x'}$) の期待値です。
この量は果たして DD を使って計算できるのでしょうか？
$\Omega(c) \times \Omega(c)$ の空間を使うのでかなり厳しい予感もしますが…
まず $g(c,c')$ を以下のように定めます。
$$
g(c,c')
:= \sum \left\{p(x_{1:d})p(x_{1:d}')\langle x_{1:d}, x_{1:d}'\rangle : x_{1:d} \in \Omega(c), x_{1:d}' \in \Omega(c') \right\}
$$
すると定義より $E_p[\langle x_{1:d}, x_{1:d}' \rangle \mid c] = g(c,c)/p^2(c)$ です。
分母の $p(c)$ はもう計算できるので、$g(c,c')$ が計算できればOKですね。
ではいつもの要領で Shannon Expansion を代入してみましょう。
ただし今回は $\Omega(c)$ と $\Omega(c')$ の２箇所に代入します。
\begin{align}
g(c,c')
&=
\sum \left\{
p(x_{1:d})p(x_{1:d}')\langle x_{1:d}, x_{1:d}'\rangle : x_{1:d} \in d \times \Omega(c_{d,1}), x_{1:d}' \in d \times \Omega(c_{d,1}')
\right\} \\
&+
\sum \left\{
p(x_{1:d})p(x_{1:d}')\langle x_{1:d}, x_{1:d}'\rangle : x_{1:d} \in d \times \Omega(c_{d,1}), x_{1:d}' \in \Omega(c_{d,0}')
\right\} \\
&+
\sum \left\{
p(x_{1:d})p(x_{1:d}')\langle x_{1:d}, x_{1:d}'\rangle : x_{1:d} \in \Omega(c_{d,0}), x_{1:d}' \in d \times \Omega(c_{d,1}')
\right\} \\
&+ \sum \left\{
p(x_{1:d})p(x_{1:d}')\langle x_{1:d}, x_{1:d}'\rangle : x_{1:d} \in \Omega(c_{d,0}), x_{1:d}' \in \Omega(c_{d,0}')
\right\}
\end{align}
今度は $g(c)$ は Shannon Expansion により、４つの sum の sum の形で書けることがわかります。
ここで $p$ の独立性と $\langle x_{1:d}, x_{1:d}' \rangle$ の $x_dx_d'$に対する線形性より以下を得ます。
\begin{align}
g(c)
&=
\theta_d^2 \sum \left\{
p(x_{1:d-1})p(x_{1:d-1}')(1+\langle x_{1:d-1}, x_{1:d-1}'\rangle) : x_{1:d-1} \in \Omega(c_{d,1}), x_{1:d-1}' \in \Omega(c_{d,1}')
\right\} \\
&+
\theta_d(1-\theta_d) \sum
\left\{p(x_{1:d-1})p(x_{1:d-1}')\langle x_{1:d-1}, x_{1:d-1}'\rangle : x_{1:d-1} \in \Omega(c_{d,1}), x_{1:d-1}' \in \Omega(c_{d,0}')
\right\} \\
&+
\theta_d(1-\theta_d) \sum \left\{
p(x_{1:d-1})p(x_{1:d-1}')\langle x_{1:d-1}, x_{1:d-1}'\rangle : x_{1:d-1} \in \Omega(c_{d,0}), x_{1:d-1}' \in \Omega(c_{d,1}')
\right\} \\
&+ (
1-\theta_d)^2 \sum \left\{
p(x_{1:d-1})p(x_{1:d-1}')\langle x_{1:d-1}, x_{1:d-1}'\rangle : x_{1:d-1} \in \Omega(c_{d,0}), x_{1:d-1}' \in \Omega(c_{d,0}')
\right\}
\end{align}
これをまとめると以下の再帰式を得ます。
\begin{align}
g(c)
&=
\theta_d^2 \left(1 + g(c_{d,1}, c_{d,1}')\right) \\
&+
\theta_d(1-\theta_d) g(c_{d,1}, c_{d,0}') \\
&+
\theta_d(1-\theta_d) g(c_{d,0},c_{d,1}') \\
&+ (
1-\theta_d)^2 g(c_{d,0},c_{d,0}') \\
\end{align}
とうこうとでなんとこちらも再帰式が無事に求まりました！
よってこの $E_p \left[\langle x_{1:d}, x_{1:d}' \rangle \mid c \right]$ は $\Delta(c)$ があれば再帰的に計算できることがわかりました！
計算量はちゃんと確認していませんが、おそらく $O(\text{ $\Delta(c)$ のサイズ × $\Delta(c)$ の幅} )$ くらいです。
一言まとめ
所望の量が Decision Diagram Constraint 下で計算できるか確認したいならば、
所望の量の定義式に Shannon Expansion を代入して、再帰が得られるか確認するだけ！
（とっても簡単！）
おわりに
この記事では Decision Diagram Constraint (DDC) がとっても便利であることを述べました。
繰り返しになりますが、DDC の元で所望の量が計算できるかは、Shannon Expansion を代入することで簡単に確認できます。
是非、みなさんも DDC を使いこなしてください！！