劣モジュラ関数最大化に対する貪欲アルゴリズム

劣モジュラ関数最大化問題と、貪欲アルゴリズムの近似比 $\left(1-\dfrac{1}{e}\right)$ について。

問題設定

要素数が $k$ である集合の中で、関数 $f$ を最大にするような集合を求める問題を考えます。

ただし、$f$ は集合関数で、単調で非負値の劣モジュラ関数とします(意味は後述)。

この問題を劣モジュラ関数最大化問題と呼ぶことにします。

考える関数

単調で非負値の劣モジュラ関数 $f$ の意味を説明します。

・まず、$f$ は集合関数です。つまり、集合 $X=\{x_1,\dots,x_n\}$ の部分集合を入力として、実数値を返す関数とします。

・単調というのは「大きい集合の方が値が大きい」という意味です。
つまり、$A\subseteq B\subseteq X$ を満たす任意の $A$ と $B$ に対して、$f(A)\leq f(B)$ とします。

・非負というのは、出力が非負という意味です。
つまり、任意の $A\subseteq X$ に対して $f(A)\geq 0$ とします。

・劣モジュラ関数とは、任意の $A,B\subseteq X$ に対して
$f(A)+f(B)\geq f(A\cap B)+f(A\cup B)$
を満たす関数です。 劣モジュラ関数は、組合せ最適化の文脈などでしばしば登場します。

劣モジュラ関数最大化問題の難しさ

・劣モジュラ関数最大化問題は、NP困難です。最適な集合 $S^*$ を求めるのは非常に難しいです。

・貪欲アルゴリズムが、近似比 $\left(1-\dfrac{1}{e}\right)\fallingdotseq 0.63$ を達成します。つまり、最適値の $63$%以上の出力を保証する集合 $S$ を求めるのは簡単です。

ただし、貪欲アルゴリズム(Greedy Algorithm)とは、
・空集合から始めて
・要素を順々に1つずつ追加していく
・その際、各段階で関数が最大になるようにする
アルゴリズムです。

近似比1-1/eの証明

貪欲アルゴリズムが近似比 $\left(1-\dfrac{1}{e}\right)$ を達成することの証明がおもしろいので紹介します。

参考文献:When Greedy Algorithms are Good Enough

・貪欲アルゴリズムの各段階で得られる集合を $S_1,\dots,S_k$ と書きます。
・$S_i=\{s_1,\dots,s_i\}$ と書きます。

目標は、
$f(S_k)\geq \left(1-\dfrac{1}{e}\right)f(S^*)$
を示すことです。

また、$a_i=f(S^*)-f(S_i)$ とします。
(最適値と、貪欲アルゴリズムの途中までの出力値の差です)

証明は2段階からなります。
前半:$a_{i+1}\leq\left(1-\dfrac{1}{k}\right)a_i$ を示す。
後半:前半の不等式を使って、目標の式を示す。

証明の前半

前半が難しいです。

青い不等式は「貪欲アルゴリズムで一歩進むと、最適値までの距離が、今までの $\left(1-\dfrac{1}{k}\right)$ 倍よりは近くなる」ことを表しています。

まず、単調性より、各 $i=1,\dots,k$ に対して
$f(S^*)\leq f(S^*\cup S_i)$
です。

ここで、$S^*=\{x_1,\dots,x_k\}$ とし、上式の右辺を「分解」していきます:
$f(S^*\cup S_i)\\
=f(S_i)+\displaystyle\sum_{t=1}^k\{f(S_i\cup\{x_1,\dots,x_t\})-f(S_i\cup\{x_1,\dots,x_{t-1}\})\}$

上式のシグマの中身に劣モジュラの不等式(を移項したもの)を使うと、
$\leq f(S_i)+\displaystyle\sum_{t=1}^k\{f(S_i\cup\{x_t\})-f(S_i)\}$
とつなげます。

さらに、貪欲アルゴリズムの定義より、
$\leq f(S_i)+\displaystyle\sum_{t=1}^k\{f(S_{i+1})-f(S_i)\}$
とつなげます。

以上を全てつなげると、
$f(S^*)\leq kf(S_{i+1})-(k-1)f(S_i)$

これを変形する($a_i$ を使って表す)と、
$a_{i+1}\leq\left(1-\dfrac{1}{k}\right)a_i$
となります。

証明の後半

後半は簡単です。

前半の不等式を繰り返し使うと、
$a_k\leq \left(1-\dfrac{1}{k}\right)^ka_0$
となりますが、

・$a_k=f(S^*)-f(S_k)$
・$a_0=f(S^*)-f(\phi)\leq f(S^*)$
・$1-\dfrac{1}{k}\leq e^{-\frac{1}{k}}$

なので、
$f(S^*)-f(S_k)\leq\dfrac{1}{e}f(S^*)$
となります。

これを整理すると
$f(S_k)\geq \left(1-\dfrac{1}{e}\right)f(S^*)$
となります。

次:一様な棒の慣性モーメントの計算方法と考察
前:最急降下法のイメージと例

スポンサーリンク

スポンサーリンク

誤植がございましたら @mathwordsnet までご連絡をお願いいたします。
ページ上部へ戻る