劣モジュラ性は組合せ最適化における基本的な概念の一つであり、効率的に計算できる組合せ最適化問題の多くに現れる性質である。劣モジュラ関数を最大化する問題は文書要約やクラスタリングなど多くの応用を持つことから、機械学習や知識発見など情報科学分野で注目を集め、これまでに様々な計算手法が提案されてきた。しかし、これらの応用では大規模なデータを扱う必要があり、メモリサイズや計算時間の両面において従来の計算手法では解決できない困難な状況が生じている。
本研究課題では、基本的な制約の下で劣モジュラ関数を最大化する問題に対して、入力データを全て保持せずに計算するストリーミング計算手法を設計した。提案アルゴリズムは入力データを定数回しか見ずに効率的に近似解を計算するものであり、メモリ効率が高くデータが大規模な場合に有用である。まず、サイズ制約のもと劣モジュラ関数を最大化する問題に対して(1-1/e)近似解を計算する手法を提案した。この近似比率は理論的に最適であり、計算時間も従来手法より高速である。さらに、ナップサック制約付の問題について初めて非自明な近似比解析を与えた。この成果は、フランス・パリのENSのChien-Chung Huang氏との共同研究である。情報処理学会のアルゴリズム研究会で口頭発表を行ない、査読付論文誌に投稿中である。
上記の結果の他にも、RIKEN AIP宮内敦史氏との共同研究によって、劣モジュラ構造を利用したコミュニティ検出問題に対する新しいモデルと解法の提案を行なった。これは、CIKMという知識発見分野の査読付国際会議に採択されている。
Submodularity is one of the most important notion in combinatorial optimization. It is known that submodularity appears in many efficiently-solvable combinatorial optimization problems. Recently, submodular functions have attracted much attention in machine learning and knowledge discovery. In particular, the problem of maximizing submodular functions has been studied extensively because it has many practical applications such as text summarization and clustering. Although there are efficient algorithms for the problem, in such practical applications, we face difficulties in space complexity and computational time, as we have to manage huge input data and we cannot store every input data on RAM.
In this project, we focus on the problem of maximizing submodular functions under fundamental constraints, and design efficient streaming algorithms for the problem. Our proposed algorithms read the input data only a constant number of times, and are effective in space as the space required is independent of the input data size. Specifically, we propose a streaming algorithm that finds a (1-1/e)-approximate solution for the cardinality-constrained problem. This approximation ratio is theoretically optimal, and it runs faster than the previous algorithms. Moreover, we design the first streaming algorithm that finds a nontrivial-ratio-approximate solution for the knapsack-constrained problem. This is joint work with Chien-Chung Huang in ENS Paris. We gave a talk on this result in Workshop on Algorithms held by Special Interest Group on Algorithms (SIGAL) of Information Processing Society of Japan (IPSJ), and a journal version was submitted.
Besides, we propose a new optimization model with submodular structure for detecting a community in a social network, which is a collaboration with Atsushi Miyauchi from RIKEN AIP, and this result is published in the refereed conference on knowledge discovery named CIKM.