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

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

解説記事のラインアップ

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

この記事では、「②劣モジュラな2次疑似ブール関数が持つ特徴」を解説します。

前回のおさらいと前振り

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

この解説記事シリーズでは、2次疑似ブール関数が劣モジュラであるなら、関数の最小化問題は、フローネットワークの問題を介して、効率的に解けることを示します。

なるほど、2次疑似ブール関数が劣モジュラであるなら、最小化問題は効率的に解ける。ではどうやって2次疑似ブール関数が劣モジュラであるかを判定するのでしょうか？前回の記事でやったように関数ごとに証明するのも面倒です。

ご安心ください(?)。実は劣モジュラな2次疑似ブール関数には特徴があるため、2次疑似ブール関数が劣モジュラかどうかは簡単に判定できます。この記事では、その判定に使える特徴を紹介し、「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}$$)とき、そしてそのときだけ、関数は劣モジュラとなります。2次疑似ブール関数の係数の正負を見るだけで、劣モジュラかどうかを判定できるというわけです。簡単ですね。

証明の前に例を見てみます。関数$${f(x_1,x_2)=x_1 x_1 -x_2 x_2 - x_1 x_2 + 2}$$が劣モジュラであることは前回の記事で証明しました。この関数を見て頂ければわかりますが、$${x_1 x_2}$$の係数が$${-1}$$であり、0以下となっています。したがって、この関数は上で紹介した特徴を持っていることがわかります。

証明

まず、①2次疑似ブール関数$${f}$$が劣モジュラであるなら、「異なる変数の積の係数すべてが0以下」となることを示します。次にその逆、②2次疑似ブール関数$${f}$$の「異なる変数の積の係数すべてが0以下」であるなら、$${f}$$は劣モジュラとなることを示します。

①の対偶を示します。つまり、2次疑似ブール関数$${f(X)=\sum_{i j} a_{i j}x_i x_j + c}$$の$${a_{i j}>0}$$のとき、$${f}$$は劣モジュラでないことを示します。

$${X=x_1,\dots,x_n}$$と$${Y=y_1,\dots,y_n}$$は、$${x_i=1}$$、$${y_j=1}$$で、それ以外の要素は0とします。ここで、

$$
\begin{array}{l}
f(X)+f(Y)-(f(X\wedge Y) + f(X\vee Y))\\
\;\;\;=a_{i i}+a_{j j}-(0+ a_{i i} + a_{j j} + a_{i j})\\
\;\;\;=-a_{i j} <0
\end{array}
$$

よって、$${f}$$は劣モジュラでないことが示されます。

次に、②2次疑似ブール関数$${f}$$の「異なる変数の積の係数すべてが0以下」であるなら、$${f}$$は劣モジュラとなることを示します。劣モジュラ性の定義の左辺から右辺を引いた式にある関数$${f}$$を展開しますと、

$$
\begin{array}{l}
f(X)+f(Y)-(f(X\wedge Y) + f(X\vee Y))\\
\;\;\;=\sum_{i j} a_{i j}x_i x_j + c + \sum_{i j} a_{i j}y_i y_j + c\\
\;\;\;\;\;\;\;\;\; - (\sum_{i j} a_{i j}(x_i y_i)(x_j y_j)+ c\\
\;\;\;\;\;\;\;\;\;\;\;\;+ \sum_{i j} a_{i j}(x_i+y_i​−x_i ​y_i )(x_j+y_j​−x_j ​y_j )+c)\\
\;\;\;=\sum_{i j} a_{i j}x_i x_j + \sum_{i j} a_{i j}y_i y_j\\
\;\;\;\;\;\;\;\;\; - (\sum_{i j} a_{i j}(x_i y_i)(x_j y_j)\\
\;\;\;\;\;\;\;\;\;\;\;\;+ \sum_{i j} a_{i j}(x_i x_j + x_i y_j (1 - x_j) + y_i y_j + x_j y_i(1 - y_j)\\
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;- x_i y_i (x_j+y_j​−x_j ​y_j ))\\
\;\;\;=- (\sum_{i j} a_{i j}(x_i y_i)(x_j y_j)\\
\;\;\;\;\;\;\;\;\;+ \sum_{i j} a_{i j}( x_i y_j(1 - x_j) + x_j y_i (1 - y_j)- x_i y_i (x_j+y_j​−x_j ​y_j ))\\
\;\;\;=- \sum_{i j} a_{i j}(2 x_i y_i x_j y_j + x_i y_j(1 - x_j) + x_j y_i (1 - y_j)- x_i y_i x_j - x_i y_i y_j​)\\
\;\;\;=- \sum_{i j} a_{i j}( x_i y_j(1 - x_j) + x_j y_i (1 - y_j)\\\;\;\;\;\;\;\;\;\;- x_i y_i x_j (1-y_j) - x_i y_i y_j(1-x_j)​)\\
\;\;\;=- \sum_{i j} a_{i j}( x_i y_j(1 - x_j)(1-y_i)​+ x_j y_i (1 - y_j)(1- x_i))\\
\end{array}
$$

よって劣モジュラ性の定義の左辺から右辺を引いた式は、

$$
-a_{i j}( x_i y_j(1 - x_j)(1-y_i)​+ x_j y_i (1 - y_j)(1- x_i))
$$

の$${i,j}$$を変えてできる項の和であることがわかりました。これら項の大きさを見てみます。$${i\not=j}$$のときの項は$${a_{i j}\le 0}$$より、$${-a_{i j}( x_i y_j(1 - x_j)(1-y_i)​+ x_j y_i (1 - y_j)(1- x_i))\ge 0}$$となります。$${i=j}$$のときの項は

$$
\begin{array}{l}
-a_{i i}( x_i y_i(1 - x_i)(1-y_i)​+ x_i y_i (1 - y_i)(1- x_i))\\
\;\;\;= -a_{i i}( 2 x_i y_i(1 - x_i)(1-y_i))=0
\end{array}
$$

となります。すべての項が0以上なのでそれらの和も0以上です。よって、$${f(X)+f(Y)-(f(X\wedge Y) + f(X\vee Y))\ge 0}$$が示せました。結果、(雑多な)式変形を経て、$${f}$$が劣モジュラ性を持つことが示せました。

まとめ

この記事では、劣モジュラな2次疑似ブール関数が持つ特徴として、異なる変数の積の係数すべてが0以下となることを紹介しました。

次回は、劣モジュラな2次疑似ブール関数を表すフローネットワークを紹介します。そのためにフローネットワークとはなんぞやの説明と、2次疑似ブール関数からフローネットワークを構成する方法を説明する予定です。

おまけ

先日、以下の本を買いました。

劣モジュラ最適化と機械学習

この記事シリーズで説明したい、「劣モジュラな2次擬似ブール関数の最小化問題は、フローネットワークの最大フロー問題を介して効率的に解ける」ことを含め、機械学習への応用などの発展的な内容もわかりやすく説明されています。おすすめです。

次の記事