第１０回助教の会

　第１０回助教の会は、生産技術研究所　最先端数理モデル連携研究センター　特任助教の永野清仁さんにお話してもらいました。永野さんは、数理第２研究室のご出身で、２００８年３月に博士号を取得され、離散アルゴリズムの研究に従事しておられます。最近は、機械学習と関連した離散最適化問題などを扱っているそうです。

　今回は、永野さんの研究テーマである、「劣モジュラ制約下の凸最適化」について、理論および応用の両側面での研究についてそれぞれ話していただきました。

　劣モジュラ関数とは、集合を引数に取る関数fで、「大きな集合に要素を加えるよりも、小さな集合に要素を加えたほうが影響が大きい」という性質を（数式では、∀S, T⊆V, f(S)+f(T)≧f(S∪T)+f(S∩T)と表される）持つもので、この劣モジュラ関数の理論は、グラフ、ネットワーク、ゲーム理論、オークション理論、機械学習など、様々な場面で使われているそうです。

　劣モジュラ関数fの例として、集合に対する２つのコスト関数の例を説明していただきました。一つは、「ホットドックの代金」、例えば「Aさんが2個、Bさんが4個、Cさんが8個のホットドックを食べるときに、必要なお金」であり、これは、それぞれの代金の和となります。（f(AさんとBさん)=f(Aさん)+f(Bさん）、など。）もう一つは、「コピーフリーのCDの代金」、例えば、「Aさんが2枚、Bさんが4枚、Cさんが8枚のCDを手に入れる時に、必要なお金」であり、これは、どの場合でも、CD1枚分の値段のままになります。（f(AさんとBさん)=f(Aさん)=f(Bさん)=定数。）いずれのfも劣モジュラ関数ですが、さらに、この両極端の場合の中間にも、様々なコスト関数を定義することができます。

　このようなfが決まると、それに対して「基多面体」B(f)と呼ばれるものが定義でき、この基多面体の上で、「もっとも良い点」（良さは、B(f)上の各点に対する関数g(x)で決まる）を見つけるのがすなわち「劣モジュラ制約下の凸最適化」ということです。

　g(x)には様々なものがあり、例えばLexicographically optimal bases (Fujishige,80)という有名な問題（これは、「なるべく中心に近い点を見つける」という問題で、様々なタスクが、この形式で表現できるそうです。）があるのですが、永野さんらは、α-カーブというアイデアに基づいて、このLexicographically optimal basesの問題が、Submodluar Utility Allocation (SUA)という、一見別の問題設定と、最適解が一致するということを発見したそうです。

　発表の後半では、この理論を、実際にネットワークの分析に応用した例を紹介していただきました。応用するのは、「最密部分グラフ問題」すなわち、「与えられたノード数の部分グラフの中で、最もエッジ重みの合計が大きいもの」を見つける問題です。この「与えられたノード数」というのが厄介で、これがなければ簡単に（多項式時間で）解けるのに、この制約があるととたんに難しく（NP-hardに）なるそうです。永野さんらは、制約なしの場合に使われる「Fujishige-Wolfe法」を拡張することで、「さまざまなノード数について、もしも最適解が見つかれば、それを出力する」というアルゴリズムを設計しました。Fujishige-Wolfe法では活用しきれていなかった情報をより「しゃぶりつくす」ことで、Fujishige-Wolfe法では出せていなかった答を出力させることができるそうです。必ず最適解が見つかるわけではありませんが、もし見つかれば高速に答えを見つけることができます。

　このFujishige-Wolfe法は、まさに前半のお話にあった、「基多面体上での最適化」に基づくアルゴリズムであり、通常の多項式時間アルゴリズムでは現実的には解けないような大きな問題まで解くことができるそうです。「最適解がもしも見つかれば、それを出力する」というアルゴリズムはなかなか変わっていて、面白いと思いました。

　劣モジュラの理論は、頭の普段使わない部分を使う感じで難しかったのですが、永野さんの力強い発表のおかげで、なんとなくやりたいことの気持ちがわかってきたような気がします。構造の複雑そうなグラフの問題が、きれいな理論で表現できる様子が魅力的でした。

情報基盤センター　助教　吉田稔

Nagano jokyoukai

View more presentations from kiyohito_nagano.