株式会社サイバーエージェント（本社：東京都渋谷区、代表取締役：藤田晋、東証プライム市場：証券コード4751）は、人工知能技術の研究開発組織「AI Lab」に所属する研究員の大坂直人による主著論文が理論計算機科学・離散アルゴリズム分野の国際会議「35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)」※1にて採択されたことをお知らせいたします。
「SODA」は世界中の研究者たちによって開催される国際会議で、 理論計算機科学分野でもっとも権威ある国際会議のひとつです。
「SODA」に投稿される多くの論文には数十ページの証明が含まれ、その数学的内容が幅広いオーディエンスの興味を惹きインパクトを与えうるかを評価されています。
このたび採択された本論文は、2024年1月にアメリカのバージニアで開催される「SODA 2024」にて発表されます。
「SODA」は世界中の研究者たちによって開催される国際会議で、 理論計算機科学分野でもっとも権威ある国際会議のひとつです。
「SODA」に投稿される多くの論文には数十ページの証明が含まれ、その数学的内容が幅広いオーディエンスの興味を惹きインパクトを与えうるかを評価されています。
このたび採択された本論文は、2024年1月にアメリカのバージニアで開催される「SODA 2024」にて発表されます。
■研究背景：組合わせ遷移
「AI Lab」ではマーケティング全般に関わる幅広いAI技術を研究・開発しており、大学・学術機関との産学連携を強化しながら様々な技術課題に取り組んでいます。また、応用研究だけでなく学術的に未解決な問題に対して貢献をする基礎研究にも注力をしており、本論文の提案は理論計算機科学の中の「組合せ遷移」※2 と呼ばれる領域に属する基礎研究に該当しています。
組合せ遷移問題とは、ルービックキューブや15パズルのように「与えられた初期状態から特定の目標状態へと遷移する」ようなタスクで、目標状態に到達する事ができるかどうかを判定する問題です。
しかし、問題によっては目標状態へ到達するために必要な手数が非常に大きく、判定が「難しい」ものがあります。このときに、その難しさはどの程度なのか・また難しくする要因は何か、を計算複雑性理論の観点から解明するために、PSPACE困難性※3の証明をはじめとする様々な研究が行われてきました。
※2 組合せ遷移＠学術変革領域研究(B) ：https://core.dais.is.tohoku.ac.jp/
※3 PSPACE困難性：多項式量のメモリを使って解ける任意の問題と比べて、少なくとも同等以上に難しいという性質
■論文の概要
「Gap Amplification for Reconfiguration Problems」
Naoto Ohsaka（CyberAgent）
著者：大坂直人（サイバーエージェント）
本論文では、組合せ遷移問題における「近似可能性」を扱っています。「近似」とは、条件が複雑で厳密な解を求めることが困難な問題に対し、その難しい条件を緩和することにより、元とは違う近しい問題に変換し、解決の糸口を探し出すための手段です。また近似可能性とは、このように厳密な解を得ることが難しい問題に対して、近似がどれほど可能かを示すものです。
過去にAI Labから国際会議「STACS 2023」で発表した論文※4では、「組合せ遷移問題の近似がPSPACE困難であるかどうか」という未解決問題の解決を目指して、作業仮説(Reconfiguration Inapproximability Hypothesis ・以下RIH)を提案し、RIHの下で様々な組合せ遷移問題の近似がPSPACE困難であることを証明しました。
しかしながら、このアプローチには、近似可能性および困難性の度合いを表す「近似比」の明示的な値が分からない、という欠点がありました。
例えば、ある組合せ遷移問題において実は厳密解より0.000…001%だけしか劣らないほぼ最適な近似解が効率的に計算できるという可能性を排除することが出来ないという点です。
この欠点を打破するために、本研究では、「ギャップ増幅」※5と呼ばれる既存の技術を組合せ遷移問題に適応させる技法を開発しました。
その成果として、RIHのみを仮定し、いくつかの組合せ遷移問題に対してPSPACE困難性を証明可能な近似比の具体的な値を導出することに成功しました。
この結果を発展させることで、その他の組合せ遷移問題の近似困難性の改善やRIH自体の証明に繋がる可能性が期待できます。
■今後
本研究の成果は理論研究の発展に寄与し得る基礎研究成果であり、当社内に限らず組合せ遷移問題の社会応用を促進することが期待されます。
今後も「AI Lab」では事業に近い応用研究をすすめるとともに、基礎研究への学術貢献を見据えた研究・開発に努めてまいります。
※1 「35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)」
※4 https://www.cyberagent.co.jp/news/detail/id=28556
※5 Irit Dinur. The PCP Theorem by gap amplification. Journal of the ACM, 54(3):12, 2007. https://doi.org/10.1145/1236457.1236459
「ギャップ増幅」とはあるギャップ問題のギャップを拡大させる変換を意味します。ある最適化問題の「ギャップ問題」とは、目的関数の最適値がある閾値以上かもう一方の閾値未満のどちらであるかを判定する問題です。これら2つの閾値の差を「ギャップ」と呼び、ギャップが大きいほど相対的に易しい問題となります。本研究では、ある組合せ遷移問題について、任意に小さいギャップをある定数ギャップへ拡大することで相対的に易しいギャップ問題の困難性及び近似困難性を証明しています。
「AI Lab」ではマーケティング全般に関わる幅広いAI技術を研究・開発しており、大学・学術機関との産学連携を強化しながら様々な技術課題に取り組んでいます。また、応用研究だけでなく学術的に未解決な問題に対して貢献をする基礎研究にも注力をしており、本論文の提案は理論計算機科学の中の「組合せ遷移」※2 と呼ばれる領域に属する基礎研究に該当しています。
組合せ遷移問題とは、ルービックキューブや15パズルのように「与えられた初期状態から特定の目標状態へと遷移する」ようなタスクで、目標状態に到達する事ができるかどうかを判定する問題です。
しかし、問題によっては目標状態へ到達するために必要な手数が非常に大きく、判定が「難しい」ものがあります。このときに、その難しさはどの程度なのか・また難しくする要因は何か、を計算複雑性理論の観点から解明するために、PSPACE困難性※3の証明をはじめとする様々な研究が行われてきました。
※2 組合せ遷移＠学術変革領域研究(B) ：https://core.dais.is.tohoku.ac.jp/
※3 PSPACE困難性：多項式量のメモリを使って解ける任意の問題と比べて、少なくとも同等以上に難しいという性質
■論文の概要
「Gap Amplification for Reconfiguration Problems」
Naoto Ohsaka（CyberAgent）
著者：大坂直人（サイバーエージェント）
本論文では、組合せ遷移問題における「近似可能性」を扱っています。「近似」とは、条件が複雑で厳密な解を求めることが困難な問題に対し、その難しい条件を緩和することにより、元とは違う近しい問題に変換し、解決の糸口を探し出すための手段です。また近似可能性とは、このように厳密な解を得ることが難しい問題に対して、近似がどれほど可能かを示すものです。
過去にAI Labから国際会議「STACS 2023」で発表した論文※4では、「組合せ遷移問題の近似がPSPACE困難であるかどうか」という未解決問題の解決を目指して、作業仮説(Reconfiguration Inapproximability Hypothesis ・以下RIH)を提案し、RIHの下で様々な組合せ遷移問題の近似がPSPACE困難であることを証明しました。
しかしながら、このアプローチには、近似可能性および困難性の度合いを表す「近似比」の明示的な値が分からない、という欠点がありました。
例えば、ある組合せ遷移問題において実は厳密解より0.000…001%だけしか劣らないほぼ最適な近似解が効率的に計算できるという可能性を排除することが出来ないという点です。
この欠点を打破するために、本研究では、「ギャップ増幅」※5と呼ばれる既存の技術を組合せ遷移問題に適応させる技法を開発しました。
その成果として、RIHのみを仮定し、いくつかの組合せ遷移問題に対してPSPACE困難性を証明可能な近似比の具体的な値を導出することに成功しました。
この結果を発展させることで、その他の組合せ遷移問題の近似困難性の改善やRIH自体の証明に繋がる可能性が期待できます。
■今後
本研究の成果は理論研究の発展に寄与し得る基礎研究成果であり、当社内に限らず組合せ遷移問題の社会応用を促進することが期待されます。
今後も「AI Lab」では事業に近い応用研究をすすめるとともに、基礎研究への学術貢献を見据えた研究・開発に努めてまいります。
※1 「35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)」
※4 https://www.cyberagent.co.jp/news/detail/id=28556
※5 Irit Dinur. The PCP Theorem by gap amplification. Journal of the ACM, 54(3):12, 2007. https://doi.org/10.1145/1236457.1236459
「ギャップ増幅」とはあるギャップ問題のギャップを拡大させる変換を意味します。ある最適化問題の「ギャップ問題」とは、目的関数の最適値がある閾値以上かもう一方の閾値未満のどちらであるかを判定する問題です。これら2つの閾値の差を「ギャップ」と呼び、ギャップが大きいほど相対的に易しい問題となります。本研究では、ある組合せ遷移問題について、任意に小さいギャップをある定数ギャップへ拡大することで相対的に易しいギャップ問題の困難性及び近似困難性を証明しています。