AI Lab、理論計算機分野の国際会議「SODA 2024」に主著論文が採択

　サイバーエージェントは、AI技術の研究組織「AI Lab」の研究員、大坂直人氏による主著論文が理論計算機科学・離散アルゴリズム分野の国際会議「35th Annual ACM-SIAM Symposium on Discrete Algorithms（SODA 2024）」にて採択されたことを、12月25日に発表した。

　「SODA」は、 理論計算機科学分野でもっとも権威ある国際会議のひとつ。本会議に投稿される多くの論文には数十ページに及ぶ証明が含まれ、その数学的内容が広範なオーディエンスの興味を引くか、また影響力の大きさが評価される。

　「AI Lab」ではマーケティング全般に関わるさまざまなAI技術を研究・開発しており、産学連携にも取り組む。また、学術的な未解決問題にも注力をしており、今回の論文は理論計算機科学の「組合せ遷移」と呼ばれる領域に焦点を当てた、基礎研究である。

　「組合せ遷移問題」とは、ルービックキューブや15パズルのように「与えられた初期状態から特定の目標状態へと遷移する」タスクで、その遷移が可能かどうかを判定する問題。問題によっては目標状態へ到達するために多くの手数が必要で、判定が困難なものもある。難しさの程度や要因を計算複雑性理論の観点から解明するため、過去の研究では「PSPACE困難性」などが議論されてきた。

　今回発表された論文「Gap Amplification for Reconfiguration Problems」では、組合せ遷移問題における「近似可能性」を扱っている。「近似」とは、条件が複雑で厳密な解を求めることが困難な問題に対し、その難しい条件を緩和して新たな問題に変換し、解決の手がかりを見つける手段。また近似可能性は、厳密な解が難しい問題に対して、どれだけ近似できるかを示すもの。

　過去にAI Labが国際会議「STACS 2023」で発表した論文では、「組合せ遷移問題の近似がPSPACE困難であるかどうか」という未解決問題に対して、作業仮説（RIH）が提案され、RIHの下でさまざまな組合せ遷移問題の近似がPSPACE困難であることが証明された。しかし、このアプローチには「近似比」の明示的な値が不明確という欠点があった。今回の研究では、「ギャップ増幅」と呼ばれる技術を組合せ遷移問題に適応し、RIHのみの仮定で、PSPACE困難性を示す近似比の値を導出することに成功した。

　AI Labは、今回の結果を発展させることで、他の組合せ遷移問題の近似困難性の改善や、RIH自体の証明につながる可能性が期待できるとしている。