劣モジュラな2次擬似ブール関数の最小化問題 #1

劣モジュラな2次擬似ブール関数の最小化問題は、フローネットワークの最大フロー問題を介して効率的に解けるそうです。専門用語だらけでぎょっとしますが、概要をいくつかの記事で解説したいと思います。

概要をまとめようと思った理由ですが、この事実に関する分かりやすい解説や論文がウェブで見つけにくかったからです。(この事実に関して述べている論文は多数見つけたのですが、説明が載っているものはあまり無く、説明が載っているものもありましたが、それらはなかなか理解が難しかったです。自分の情報検索能力や理解力が低いだけなのですが。。)

因みに以下の講義資料がわかりやすく解説しています。(具体的には、下記資料のp.45からの解説)。これのお陰で理解できました。

https://www.cs.toronto.edu/~urtasun/courses/CV/lecture14.pdf

解説記事のラインアップ

「劣モジュラな2次擬似ブール関数の最小化問題は、フローネットワークの最大フロー問題を介して効率的に解ける」ことの概要を下記の順で記事にする予定です。
①2次疑似ブール関数とその劣モジュラ性
②劣モジュラな2次疑似ブール関数が持つ特徴
③劣モジュラな2次疑似ブール関数を表すフローネットワーク
④劣モジュラな2次疑似ブール関数を表すフローネットワークの最大フローと、元の関数の最小値の対応

この記事では、「①2次疑似ブール関数とその劣モジュラ性」を解説します。

2次擬似ブール関数

まずは2次疑似ブール関数を定義します。2次擬似ブール関数は、変数が0か1をとる2次式です。今回扱う2次疑似ブール関数を式で書きますと以下の形になります。

$$
f(X)=\sum_{i j} a_{i j}x_i x_j + c 
$$

ここで、$${X=x_1, \dots, x_n}$$は0か1をとる変数で、$${a_{i j}}$$と$${c}$$は整数とします。したがって、この関数は0と1で構成される列を受け取り整数値を返す関数となります。

例えば、$${f(x_1,x_2)=x_1 x_1 -x_2 x_2 - x_1 x_2 + 2}$$という関数$${f}$$は2次疑似ブール関数です。$${f}$$の引数を0,1とすると、$${f(0,1)=0\cdot 0-1\cdot 1-0\cdot 1+2=1}$$となります。

因みに、今回は簡単のために係数と定数項を整数に限定しましたが、一般的に2次疑似ブール関数は、係数$${a_{i j}}$$と定数項$${c}$$が実数でもよいそうで、それらを実数にしても今回解説したい事実「劣モジュラな2次擬似ブール関数の最小化問題は、フローネットワークの最大フロー問題を介して効率的に解ける」は成り立つそうです。

2次擬似ブール関数の劣モジュラ性

劣モジュラ性の定義を説明します。以下の性質を満たすとき$${n}$$個の変数を受取る2次擬似ブール関数$${f}$$は劣モジュラであるといいます。任意の0と1の列$${X}$$と$${Y}$$に対して、

$$
f(X)+f(Y)\ge f(X\wedge Y) + f(X\vee Y)
$$

を満たす場合です。ここで、$${X\wedge Y}$$は$${X}$$と$${Y}$$の各要素ごとに論理積をかけた後の列を意味し、具体的には$${X=x_1,\dots,x_n}$$と$${Y=y_1,\dots,y_n}$$としたとき、$${X\wedge Y=x_1 y_1, x_2 y_2,\dots, x_n y_n}$$となります。そして$${X\vee Y}$$は各要素ごとに論理和をかけた後の列を意味し、$${x_1+y_1-x_1y_1,\dots, x_n+y_n-x_ny_n}$$となります。すこし式が複雑ですが、$${x_i+x_i-x_i y_i}$$はただの論理和を表す式なので、$${x_i=1}$$か$${y_i=1}$$のとき1となり、その他の場合は0となるだけです。

因みに、先の例であげた関数$${f(x_1,x_2)=x_1 x_1 -x_2 x_2 - x_1 x_2 + 2}$$は劣モジュラです。$${x_1,x_2}$$の値の場合分けで証明できます。$${X=0,0}$$のとき、

$$
f(X)+f(Y)- (f(X\wedge Y) + f(X\vee Y))\\=f(0,0)+f(Y)-(f(0,0)+f(Y))= 0
$$

となり、劣モジュラの条件を満たします。$${X=1,1}$$のときは、

$$
f(1,1)+f(Y)-(f(Y)+f(1,1))= 0
$$

となり、劣モジュラの条件を満たします。次に$${X=0,1}$$のとき、

$$
\begin{array}{l}
f(0,1)+f(y_1,y_2)- (f(0,y_2) + f(y_1,1))\\
\;\;\;=-1+2+y_1 y_1 - y_2 y_2 -y_1 y_2 +2\\\;\;\;\;\;\; - (-y_2 y_2 +2 +y_1 y_1 -1 -y_1\cdot 1+2)\\
\;\;\;=-y_1 y_2 +y_1\cdot 1=y_1(1-y_2)\ge 0
\end{array}
$$

となり、劣モジュラの条件を満たします。$${X=1,0}$$のときは、

$$
\begin{array}{l}
f(1,0)+f(y_1,y_2)- (f(y_1,0) + f(1,y_2))\\
\;\;\;=1+2+y_1 y_1 - y_2 y_2 -y_1 y_2 +2\\\;\;\;\;\;\; - (y_1 y_1 +2 +1-y_2 y_2 -1\cdot y_2+2)\\
\;\;\;=-y_1 y_2 +1\cdot y_2=y_2(1-y_1)\ge 0
\end{array}
$$

となり、劣モジュラとなります。結果、すべての場合で劣モジュラの条件を満たすので、関数$${f}$$は劣モジュラとなります。

劣モジュラな関数の振る舞い

劣モジュラ性の定義を紹介しましたが、この性質がどんなものなのかの理解をより深めたいと思います。そのためにこの節では劣モジュラな2次擬似ブール関数の振る舞いを調べてみます。

具体的には、入力列の要素の1をひとつ増やしたとき関数の値がどれくらい増えるかを見ます。そうしますと、「入力列に1をひとつ増やしたときの増加分」は入力列の1が多くなるとペースダウンすることが示せます。

式で見ましょう。入力列として、$${i}$$番目の要素が$${0}$$である数列$${X=x_1,\dots,x_n}$$を考えますと、入力列$${X}$$の$${i}$$番目の要素を$${1}$$としたときの増加分は式で、$${f(X\vee I_i)-f(X)}$$となります。ここで$${I_i}$$は$${i}$$番目だけ1で他が0の数列とします、そしてしたがって、$${X\vee I_i}$$はi番目が1でそれ以外は$${X}$$と同じ数列となります。

関数$${f}$$が劣モジュラなとき上の増加分がどうなるか見てみましょう。ここで、0と1の列$${A=a_1,\dots,a_n}$$と$${B=b_1,\dots,b_n}$$を考え、これらが$${A\vee B = B}$$と$${a_i=b_i=0}$$と「$${A}$$の中1の数$${<}$$$${B}$$の中の1の数」を満たすとします。このことは$${A}$$と$${B}$$は$${i}$$番目の要素が0で、$${A}$$の1の要素の数は$${B}$$の1の要素の数より少ないことを意味します。

これら$${A}$$と$${B}$$を劣モジュラの条件である式に代入します。具体的には、$${X=A\vee I_i}$$と$${Y=B}$$としますと、

$$
\begin{array}{l}
{f(X)+f(Y)\ge f(X\wedge Y) + f(X\vee Y)}\\
\;\;\;\Leftrightarrow f(A\vee I_i)+f(B)\ge f((A\vee I_i)\wedge B)+f((A\vee I_i)\vee B)\\
\;\;\;\Leftrightarrow f(A\vee I_i)-f((A\vee I_i)\wedge B)\ge f((A\vee I_i)\vee B)-f(B)\\
\;\;\;\Leftrightarrow f(A\vee I_i) - f(A) \ge f(B\vee I_i) - f(B)
\end{array}
$$

が導出できます。この導出された式から、入力列$${A}$$の1をひとつ増やしたときの関数$${f}$$の値の増加分は、$${B}$$の増加分よりも同じか大きくなることがわかります。$${A}$$よりも$${B}$$の方が1の数が多いため、「入力列に1をひとつ増やしたときの増加分」は入力列の1が多くなるとペースダウンした(正確に言うと、増えなかった)ことがわかります。これが劣モジュラな2次擬似ブール関数の振る舞いとなります。

唐突ですが実は、この劣モジュラな関数の振る舞いは、限界効用逓減の法則と呼ばれる、普段の生活でもよくある現象を表すことができます。

普段の生活の例として、ドーナツを食べたときの得られる満足感の話をします。ドーナツ屋さんが半額セールだということで、あなたは普段買わない種類も含め色々なドーナツを買ったとします。

色々な種類のドーナツ (いらすとやより)

そしてそれらを食べます。ここで「一番はじめにドーナツを食べたときに得る満足感」「2個目を食べたときの満足感」「3個目…」(経験上)だんだんと得られる満足感は減る気がしませんか？

この直感は劣モジュラな関数の振る舞いで表現できます。そのために劣モジュラ性を表す式に解釈を与えます。数列$${X}$$が食べたドーナツの種類を表し、$${f(X)}$$が$${X}$$が表すドーナツを食べたときの満足感とします。したがって、$${f(X\vee I_i) - f(X)}$$は$${X}$$が表すドーナツを食べた後に追加で$${x_i}$$が表すドーナツを食べたときに得られる満足感です。

この解釈のもと、上で導出できた式を何度も使うと以下の式が導けます。

$$
\begin{array}{l}
「ドーナツ1個目を食べたときに得る満足感」\\
\ge「2個目を食べたときに得る満足感」\\
\ge「3個目を食べたときに得る満足感」\\
\dots
\end{array}
$$

ドーナツを食べた続けたときに得られる満足感がペースダウンしていくという、普段の生活でもある現象が、劣モジュラな関数の振る舞いで表せているのがわかります。興味深いですね。

この節では劣モジュラ性の振る舞いを紹介しました。数式と解釈が行ったり来たりしてわかりにくかったかもしれません。。もっと分かりやすい劣モジュラ性の解説は以下にあります。おすすめです。

プリキュアで学ぶ劣モジュラ関数 - むしゃくしゃしてやった，今は反省している日記

まとめ

この記事では、2次擬似ブール関数の定義、その劣モジュラ性の定義を紹介しました。そして、劣モジュラな2次疑似ブール関数の直感を説明しました。

次回は、劣モジュラな2次疑似ブール関数が持つ特徴を紹介します。具体的には、2次疑似ブール関数$${\sum_{i j} a_{i j}x_i x_j + c}$$が劣モジュラなとき、そしてそのときだけ、異なる変数の積の係数すべてが0以下となること(つまり、$${\forall_{i,j : i\not=j}\; a_{i j}\le 0}$$)を示します。

次の記事