株式会社サイバーエージェント（本社：東京都渋谷区、代表取締役：藤田晋、東証プライム市場：証券コード4751）は、人工知能技術の研究開発組織「AI Lab」に所属する研究員の大坂直人による主著論文が理論計算機科学・アルゴリズム分野の国際ジャーナル「Algorithmica」※1にて採択されたことをお知らせいたします。
「Algorithmica」は理論計算機科学分野・アルゴリズム分野における主要な論文誌の一つです。今回採択された論文は理論計算機科学分野の国際会議「ISAAC 2022」※2で発表された65本の論文の中から特集号に選ばれたものです。
「Algorithmica」は理論計算機科学分野・アルゴリズム分野における主要な論文誌の一つです。今回採択された論文は理論計算機科学分野の国際会議「ISAAC 2022」※2で発表された65本の論文の中から特集号に選ばれたものです。
■研究背景：多様性と行列式最大化
「AI Lab」ではマーケティング全般に関わる幅広いAI技術を研究・開発しており、大学・学術機関との産学連携を強化しながら様々な技術課題に取り組んでいます。また、応用研究だけでなく学術的に未解決な問題に対して貢献をする基礎研究にも注力をしており、本論文の提案は理論計算機科学の中の「パラメータ化計算量理論」 と呼ばれる領域に属する基礎研究に該当しています。
大量のアイテムの集合からそれらを代表する少数のアイテムを選択するというタスクは機械学習・人工知能などの分野における基礎的な問題です。選択されたアイテム達には、しばしば互いに似通っていない「多様性」が求められます。
このような多様性を行列式の値で表現する確率モデル「行列式点過程」※3や最も多様なアイテム集合を選択する「行列式最大化問題」※4は様々な領域で応用されています。一方で、行列式最大化問題は計算量理論の観点からは非常に難しい※5ことが知られていました。
大量のアイテムの集合からそれらを代表する少数のアイテムを選択するというタスクは機械学習・人工知能などの分野における基礎的な問題です。選択されたアイテム達には、しばしば互いに似通っていない「多様性」が求められます。
このような多様性を行列式の値で表現する確率モデル「行列式点過程」※3や最も多様なアイテム集合を選択する「行列式最大化問題」※4は様々な領域で応用されています。一方で、行列式最大化問題は計算量理論の観点からは非常に難しい※5ことが知られていました。
■論文の概要
今回採択された論文「On the Parameterized Intractability of Determinant Maximization」では、行列式最大化問題のパラメータ化計算量を研究し、入力を制限または要求を緩和することで、「固定パラメータ容易性」※6が達成されうるかを解析しました。
その結果以下の場合についても行列式最大化問題が（ある計算量理論の仮定のもとで）固定パラメータ容易となりえないことを証明しました。
(1) 入力行列が非常に疎な（非ゼロ要素が少ない）場合
(2) 入力行列のランクをパラメータとした場合
(3) 近似解を許す場合
これらの結果は、上記のような実用上想定されうる特殊ケースにおいても、行列式最大化問題を効率的に解くことは本質的に困難であることを示唆しています。
その結果以下の場合についても行列式最大化問題が（ある計算量理論の仮定のもとで）固定パラメータ容易となりえないことを証明しました。
(1) 入力行列が非常に疎な（非ゼロ要素が少ない）場合
(2) 入力行列のランクをパラメータとした場合
(3) 近似解を許す場合
これらの結果は、上記のような実用上想定されうる特殊ケースにおいても、行列式最大化問題を効率的に解くことは本質的に困難であることを示唆しています。
■今後
本研究の成果は理論研究の発展に寄与し得る基礎研究成果であり、多様性を表現する行列式点過程の社会応用を促進することが期待されます。
今後も「AI Lab」では事業に近い応用研究をすすめるとともに、基礎研究への学術貢献を見据えた研究・開発に努めてまいります。
※1 Algorithmica
※2 The 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
※3 Alex Kuleszaand Ben Taskar. “Determinantal Point processes for machine learning.” Foundations and Trends® in Machine Learning 5.2–3 (2012), pp. 123–286.
※4 サイズn×nの半正定値行列と整数kを入力として、行列式の値が最大となるサイズk×kの主小行列を計算する問題
※5 行列式最大化問題はNP困難というだけではなく、その近似解の計算がNP困難であると証明されている
※6 入力サイズとは異なるパラメータに関してのみ指数関数かつ入力サイズについては多項式関数で抑えられるような計算時間で解ける問題を「固定パラメータ容易」と呼び、それを達成するアルゴリズムを「固定パラメータアルゴリズム」と呼ぶ
今後も「AI Lab」では事業に近い応用研究をすすめるとともに、基礎研究への学術貢献を見据えた研究・開発に努めてまいります。
※1 Algorithmica
※2 The 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
※3 Alex Kuleszaand Ben Taskar. “Determinantal Point processes for machine learning.” Foundations and Trends® in Machine Learning 5.2–3 (2012), pp. 123–286.
※4 サイズn×nの半正定値行列と整数kを入力として、行列式の値が最大となるサイズk×kの主小行列を計算する問題
※5 行列式最大化問題はNP困難というだけではなく、その近似解の計算がNP困難であると証明されている
※6 入力サイズとは異なるパラメータに関してのみ指数関数かつ入力サイズについては多項式関数で抑えられるような計算時間で解ける問題を「固定パラメータ容易」と呼び、それを達成するアルゴリズムを「固定パラメータアルゴリズム」と呼ぶ