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

劣モジュラ最適化による機械学習の概要

劣モジュラ関数は、離散的な変数に関する凸関数に対応する概念であり、組合せ最適化問題において重要な概念となる。「組み合わせ」とは「何らかの選択可能な集まりの中から、その一部を選択する」という手続き、およびそれに付随する種々の計算的な性質を意味する。劣モジュラ関数は、組合せ最適化問題において、以下のような特性を持つ関数のことを指す。

• 減少性 (Diminishing Returns): 劣モジュラ関数は、一つの要素を追加することによって、その関数の値が減少する性質を持つ。つまり、より多くの要素を選択するほど、その関数の値は小さくなる。
• 置換性 (Submodularity): 劣モジュラ関数は、ある要素を別の要素で置き換える操作によって関数の値が減少するか、変化しない性質を持つ。

劣モジュラ関数は、これらの性質を用いることで、最小化や最大化のような最適化問題において、効率的な解法を見つけるために利用され、情報理論、機械学習、経済学、社会科学など幅広い分野において応用されている。

劣モジュラ関数は最適化や意思決定問題において、効率的な解法を見つけるために重要なツールとして用いられる。具体的な応用例としては以下のようなものがある。

• ソーシャルネットワーク分析: ソーシャルネットワーク分析において、劣モジュラ関数は、情報の伝播や影響力の最大化などの問題に応用される。例えば、ある製品の宣伝戦略を最適に決定するために、限られた予算内で情報の拡散を最大化するためのユーザーの選択を行う問題などに用いられる。
• 画像セグメンテーション: 画像処理において、劣モジュラ関数は、画像のセグメンテーション（画像を複数の領域に分割する）の最適化に応用される。例えば、ある画像を異なる領域に分割する際に、領域間の境界を最小化するようなセグメンテーションを求める問題などに用いられる。
• クエリ最適化: 情報検索やデータベースのクエリ最適化において、劣モジュラ関数は、検索結果のランキングやクエリの最適化などの問題に応用される。例えば、検索結果のランキングを最適に並び替えるために、効果的に情報を提示する順序を決定する問題などに用いられる。
• 組合せ最適化: 劣モジュラ関数は、組合せ最適化問題において、効率的な解法を見つけるために広く利用されます。例えば、最小被覆問題(あるセンサーネットワークを効率的にカバーするための最小のセンサーの集合を見つける等のある条件を満たす最小の要素の集合を見つける問題)、最大重み付きセットカバー問題(ある広告を最小の予算で最大の効果を得るための広告配置問題等のある重み付きの要素の集合を選択することによって、最大の重みの合計を得る問題)、最大スパニング木問題(通信ネットワーク、電力ネットワーク、ソーシャルネットワーク、交通ネットワーク等のネットワーク最適化やクラスタリング)、最適なスケジューリング(ジョブスケジューリング、プロジェクトスケジューリング、リソース割り当て等)など、様々な組合せ最適化問題に応用される。

劣モジュラ関数を最適化するための一般的なアルゴリズムとしては、以下のようなものがある。

• グリーディ法: グリーディ法は、劣モジュラ関数を最適化するための単純で効果的なアルゴリズムとなる。グリーディ法では、各ステップで局所的に最適な選択を行いながら全体の最適解を求める。劣モジュラ関数の性質を利用し、各ステップで最大の効果を持つ要素を選択することで、効率的に最適解を求めることができる。
• ナイーブアルゴリズム: ナイーブアルゴリズムは、劣モジュラ関数を最適化するための基本的なアルゴリズムであり、全ての可能な解を列挙して最適解を求める方法となる。劣モジュラ関数の性質を利用せず、全ての組み合わせを試すため、計算コストが高いが、最適解を求めることができる。
• ソルバーを用いた方法: 劣モジュラ関数を最適化する問題に対しては、ソルバーを用いた最適化手法を利用することも一般的となる。例えば、整数線形計画法（ILP）や混合整数線形計画法（MILP）などの最適化ソルバーを用いることで、劣モジュラ関数を最適化する高性能なアルゴリズムを利用することができる。

本ブログではこれら劣モジュラ関数の理論と具体的な応用に関して以下に示す。

実装

• 劣モジュラ最適化の概要と適用事例および実装例

劣モジュラ最適化（Submodular Optimization）は、組合せ最適化の一種であり、特定の性質を持つ関数である劣モジュラ関数を最大化または最小化する問題を解決する手法となる。ここでは、この劣モジュラ最適化に関して、様々なアルゴリズム、適用事例、及びそれらの実装例について述べている。

• Submodular Diversificationの概要とアルゴリズム及び実装例について

Submodular Diversificationは、情報検索やランキングのタスクにおいて、多様性を持った上位k件の選択を行うための手法の一つであり、この手法は、選択されたアイテム間の相互作用を考慮し、多様性を最大化しつつ効率的に上位k件を選択することを目指すものとなる。Submodular Diversificationの基盤となるのが、”劣モジュラ最適化と機械学習“でも述べているSubmodular 関数で、これは、集合関数 \( f: 2^V \rightarrow \mathbb{R} \) で、以下の性質を持つ関数となる。

理論

• 機械学習プロフェッショナルシリーズ「劣モジュラ最適化と機械学習」読書メモ
• 劣モジュラ最適化と機械学習 – 学習における劣モジュラ性

劣モジュラ関数とその最適化の理論は、組み合わせ最適化分野での中心話題であり、
劣モジュラ関数は、離散的な変数に関する凸関数に対応する概念で、1970年のエドモンズによる論文により始まる。

劣モジュラー最適化は、有用そうな一部のデータを選択して用いることが重要になり、それらをシステマチックに抽出するアプローチとなり、このような選択可能な対象の集まりからその一部を選択するという計算は、「集合関数(set function)」と呼ばれる離散的な関数の最適化を行っていると捉えることができる。

• 劣モジュラ最適化の基礎(1)劣モジュラ関数の定義と具体例

劣モジュラ関数は、最適化を考えた時の性質の良さと、応用を考えたときの適用範囲の広さを併せ持った関数となる。ここでは、劣モジュラ最適化の考え方について述べ、劣文字なら最適化において重要となる基本概念を導入する。さらに、劣モジュラ関数と凸関数の関係についても述べる。

関数が連続的な値をとる場合の最適化について、凸関数(convex function)と凹関数(concave function)は重要な役割を果たす概念となる。

ここで具体的な劣モジュラ関数について、以下に述べる3つの関数(1)カバー関数、ゅふょグラフのカット関数、(3)凹関数が生成する関数がある。それらについて述べる。

• 劣モジュラ最適化の基礎(2) 劣モジュラ関数の基本性質

劣モジュラ最適化において、現在扱っている関数fが劣モジュラ性に加えてどのような性質をもっているかは非常に重要となる。関数fの持つ性質によって、厳密に最適化する際の計算効率や近似アルゴリズムが保証できる精度が大きく異なってくることもある。ここでは劣モジュラ関数をタイプ分けする際に重要となる基本概念について述べ、さらに劣モジュラ関数と関連する概念、優モジュラ関数とモジュラ関数についても定義する。

まず3つのタイプとして(1)正規化、(2)非負、(3)対称がありそれらを有向・無向のグラフカットの最小化・最大化に適用したケースのアルゴリズムと計算時間について述べる。

• 劣モジュラ最適化の基礎(3)基多面体の最小ノルム点を利用した劣モジュラ関数最小化問題アルゴリズム

正規化された劣モジュラ関数では、関数によって2つの多面体、劣モジュラ多面体と基多面体が定義される。劣モジュラ関数最小化問題や劣モジュラ関数の凸性について議論するためには、これらの多面体は重要な役割を果たす。ここでは、劣モジュラ関数最小化問題に対する、基多面体の最小ノルム点を利用したアルゴリズムについて述べる。

• 劣モジュラ最適化の基礎(4)基多面体上の線形最適化とノルム最適化によるアプローチ

多面体上で線形関数を最適化(最大化または最小化)する問題は一般に線形最適化問題(linear optimization problem)あるいは線形計画問題(linear programming problem)と呼ばれる。実行可能領域を有界な多面体とする線形最適化問題には端点であるような最適解、端点最適解が必ず存在する。

また基多面体上のL2ノルム最小化問題が解ければ、劣モジュラ関数最小化問題が解けることになる。多項式時間アルゴリズムと比較して、高速な劣モジュラ関数最小化アルゴリズムとして知られている最小ノルム点アルゴリズムはこの性質に基づいたアルゴリズムとなる。

• 劣モジュラ最適化の基礎(5) ロヴァース拡張と多重線形拡張

劣モジュラ関数と凸性について。V={1,…,n}とf:2^V→ℝを正規化されたモジュラ関数とする。劣モジュラ関数と凸性についてはある種の等価性が成立し、この凸性は最適化アルゴリズムの設計上でも重要な役割を果たす。劣モジュラ関数が離散領域{0,1}ⁿの上で凸関数であるとみなせることについて、その意味を正確に述べるためにはロヴァース拡張(Lovaz extension)の概念を導入する必要がある。

また、関連する概念として、ロヴァース拡張とは異なる連続化である多重線形拡張(multilinear etension)もしばしば用いられる。多重線形拡張\(\tilde{f}:¥0,1]^n\rightarrow\mathbb{R}\)の定義域はn次元単位超立方体{0,1}ⁿとなる。ロヴァース拡張\(\hat{f}\)が劣モジュラ関数fを凸関数として拡張する概念であるのに対し、多重線形拡張\(\tilde{f}\)は劣モジュラ関数fを「部分的に見れば凹関数」となるように拡張する概念となる。

• 劣モジュラ関数の最大化と貪欲法の適用(1) 貪欲法の概要と文書要約タスクへの適用

今回は、劣モジュラ関数を最大化する問題について述べる。ただし、通常、f:2V→ℝは単調な劣モジュラ関数である場合について述べる。また制約条件は、選択する部分集合の要素数が最大でk(>0)個であることを課している。前述した様に劣モジュラ関数は、種々の分野での何らかの利得を表すことが多いため、それを最大化したいという定式化が多くの場面で見られる。そのように、劣モジュラ関数の最大か問題は、応用上も非常に重要になってくる。

劣モジュラ関数の最大化問題は、これまでも機械学習などにおける様々な問題へ適用されている。ここではその例として、文書要約と、センサ配置問題、そして能動学習について述べる。

またアルゴリズムとしてはシンプルな近似アルゴリズムである貪欲法について述べる。

• 劣モジュラ関数の最大化と貪欲法の適用(2)センサ配置問題と能動学習問題

次の適用例として、ある空間内で何らかの物理量(たとえば室温など)をセンサを用いて観測するという状況において、できるだけその観測誤差が小さくなる様に、いくつかのセンサを配置する問題を考える。前述ではこれと類似した状況をカバー関数を使って検討したが、ここではこの問題をガウス過程(Gaussian process regression)によりモデル化し、最終的に劣モジュラ最大化へ帰着する。

もう一つの例として、能動学習の劣モジュラ関数最大化としての定式化を考える。能動学習は、教師あり学習においてラベル付けのコストが高い様な場合に、重要なサンプルのみを選択してラベル付けを行うための方法で、機械学習における重要な問題の一つとなる。

ここでは、一般にプールベース型と呼ばれる能動学習の設定を考える。プールベース型能動学習(pool-based active learning)では、ラベルのないサンプルが手元にある場合に、その中から学習に有用となるラベル付けを行うサンプルを選択するという問題を扱う

• 最大流とグラフカット(1) 最大量と最小s-tカット

劣モジュラ関数は効率的に最小化が行える。特に有向グラフのカット関数の最小化は、最大流アルゴリズムで行えるため、理論的/実用的に高速な計算が可能となる。ここでは最大流アルゴリズムの基本的事項と、そのような計算へ帰着される例として、マルコフ確率場での推論を取り上げ、実用的にもよく用いられる、高速に計算可能な劣モジュラ関数のクラスについて述べる。

グラフカットは、数万〜数百万のオーダーの問題に対しても実用的時間で適用可能なアルゴリズムであると知られているが、劣モジュラ関数の観点から見ると、おおよそ2次の劣モジュラ関数ともいえるカット関数の最小化を行なっているものと解釈できる。カット関数の最小化に関しては、最大流アルゴリズムと呼ばれる理論的/実用的に高速なアルゴリズムの適用が可能であることがしられている。このようなカット関数の最小化として記述できるかどうかは、実用的に組み合わせ計算を行うことができるかどうかをはかる一つの見方であるともいえる。

ここではこのような関係を理解するために、まずカット関数の最小化とネットワークにおける最大流の計算との関係、そして実際に最大流計算を行う具体的な方法について見ていく。

• 最大流とグラフカット(2)最大流アルゴリズム

今回は、最大流を求める代表的なアルゴリズムであるフロー増加法について述べ、さらに最大流アルゴリズムを用いた最小s-tカットの計算方法や最大流最小カット定理の証明について述べる。さらフロー増加法とは異なる原理に基づく、高速な最大流アルゴリズムであるブリフロー・ブッシュ法についても述べる。

• 最大流とグラフカット(3) マルコフ確率場における推論とグラフカット

多変数データを扱う際に、データの各変数が何らかの構造を持つ場合、その構造を用いてさまざまな推論アルゴリズムが再帰的に記述できる場合がある。マルコフ確率場はその代表的なモデルで、無向グラフを用いて変数間のマルコフ性を表す。ここでは、マルコフ確率場の最大事後確率推定(maximum-a-posteriori estimation)と列劣モジュラ最適化との関係について述べる。さらに、コンピューター・ビジョン分野などでさかんに用いられているグラフカットは、本質的には、s-tカットの最小化計算をしていると言うことについて述べる。

• 最大流とグラフカット(4)グラフ表現可能な劣モジュラ関数

ここまで述べた様に、有向グラフのs-tカット関数は、高速な最小化が可能な劣モジュラ関数の特殊クラスであるといえる。しかし、当然ながら、この関数のみではその記述力に限界があるため、さまざまな実用的な場面で十分であるとは言えない。したがって、有向グラフのs-tカット関数よりも記述力があり、一方でこの関数同様に高速に最小化できる関数が考えられれば、実用上極めて有用になる。ここでは、その答えの一つとして、グラフ表現可能な劣モジュラ関数(graph-representable submodular function)について述べる。グラフ表現可能な劣モジュラ関数としては、いくつかの補助的な頂点を加えれば有向グラフのs-tカット関数として表すことができる関数で、先述した様な実用上有用な関数のクラスであると言える。

次に、有向グラフのs-tカット関数最小化のための最大流計算を行う方法として、プリフロー・プッシュ法について述べる。前述の様に、最大流については、最近オルリンによる計算量O(nm)のアルゴリズムが提案されている。プリフロー・プッシュ法の場合、計算量はO(mnlogn²/m)ではあるが、実用的には高速な実装が知られており、依然応用上重要なアルゴリズムとなる。また、この方法はパラメトリック最適化へも拡張できるため、後述においても重要な役割を果たす。

実行可能フローは「容量制約」と「流量保存制約」の両方を満たす様なフローξ=(ξ_e)_e∈ℰであった。プリフロー・プッシュ法では、実行可能フローの代わりに、流量保存制約を緩和して得られるプリフロー(preflow)と呼ばれるフローを考え、このプリフローが流量保存速を徐々に満たしていくように反復的に更新し、最終的に実行可能フローを得ることで最大流を計算する。

• 劣モジュラ最適化を用いた構造正則化学習(1)正則化とp-ノルムの復習

構造正則化学習は、教師あり学習において、データ変数間の構造を利用するための枠組みちなる。ここでは、構造正則化と劣モジュラ関数の関係と、この関係を用いた劣モジュラ最適化による構造正則化のためのアルゴリズムについて述べる。

機械学習の手法を適用したいデータが手元にあるとき、そのデータの各変数が互いにまったく無関係であることはまずない。たとえば画像データを扱うときは、モデル中の変数が画像中の画素に対応するので、画素の隣接構造が変数間の関係として存在しているといえる。また、遺伝子データを扱うときは、各変数は遺伝子に対応するので、知られている遺伝子相互作用などが存在する。学習においては、こうした関係を考慮することで精度の向上が可能となったり、解釈しやすいモデルが得られることが期待できる。

ここでは、このようなデータ変数間の構造を未知いた機械学習手法である構造正則化について述べる。この様な構造は、いわば学習における事前情報となるので、うまく利用することで問題の実質的な次元を減らし学習性を向上させる。このため構造正則化はいわゆる疎性モデリングへのアプローチであるとも捉えられる。

近年では、構造正則化は、劣モジュラ最適化と密接な関係があることが指摘され注目されている。理論的な面白さだけではなく、実用的には、構造正則化学習が極めて高速に計算できるネットワークフローへと帰着できることも、この関係の重要な点となる。

• 劣モジュラ最適化を用いた構造正則化学習(2)劣モジュラ関数から得られる構造的疎性

ここで劣モジュラ関数から得られる構造的疎性について述べる。前述した𝓵pノルムによる正則化は、この形からわかる様に、各変数ω1,…,ωdについて一様な扱いをする形となっている。しかし、この一妖精は正則化においては必須ではない。ここでは、正則化を拡張し、データの変数間にある関係を明示的に利用する方法である構造正則化(structured regularization)について述べる。

正則化により得られる疎性には、大きく2つのタイプが存在する。まずぬつは、上記の𝓵1正則化のように、多くのパラメータを縮退させて0の値を取るという形の疎性となる。𝓵1正則化では疎性が促される単位は各変数であったが、後述する様にこれを拡張させて、事前に与えた変数上のグループ単位で考えることもできる。そして、もう一つのタイプは、性質の近い複数のパラメータが同じ値を取りやすい様な疎性となる。ここでは、前者のタイプをグループ型の正則化、そして後者のタイプを結合型の正則化と呼ぶこととする。

• 劣モジュラ最適化を用いた構造正則化学習(3)構造正則化問題の劣モジュラ最適化による定式化

離散情報の最適化手法である劣モジュラ関数最適化の構造正則化問題への適用と劣モジュラ最適化を用いた定式化(線形近似と最急効果法、加速近接勾配法、FISTA、パラメトリック劣モジュラ最小化、分割アルゴリズム)

実装

劣モジュラ関数に関する問題の為のライブラリは様々なものが開発されている。

• submodular-optimization

利用可能なライブラリのサイトをまとめたサイト。23のライブラリに対する情報がある。