Top > 関連資料 > アナウンスメント > 若手研究者紹介3

関連資料

アナウンスメント

若手研究者紹介3

〜大規模データから直接的な相関を抽出する高速な数学的手法の設計〜
大学院情報理工学研究科 数理・計算科学専攻
山下 真


[要点]
<背景> 大規模データを短時間で解析するために、数理最適化問題を高速に求解する数学的手法への需要が高まっています
<内容> 直接的な相関の解析の計算に用いられる対数行列式半正定値計画問題という数理最適化問題に対する主要な計算時間を占める射影計算を2段階に分解し簡易化することで計算時間の短縮を実現しました
<発展> より大規模なデータや複数データを組み合わせたデータなどから直接的な相関の解析が容易に

[概要]
大規模なデータから本質的な因果関係を見出すグラフィカルモデリングは、「対数行列式半正定値計画問題」と呼ばれる数理最適化の問題と密接に関係しており、この問題を短時間で求解可能な計算手法は大規模データの解析に重要な手段となりつつあります。
山下真准教授・福田光浩准教授の研究グループでは、スペクトラル射影勾配法の主要な計算部分である射影計算を2段階に分解し簡易化することで、対数行列式半正定値計画問題の大幅な計算時間の短縮を実現しました。
本研究の数学的手法をほかの数理最適化問題や数学的手法にも活用することで、さらに大規模あるいは複雑なデータなどの解析を短時間で容易に行える数学的手法の設計に結びつきます。

○研究の背景
 近年では大量のデータを蓄積することが容易となり、このデータから有益な知見を抽出する計算手法が社会基盤を支える数学のひとつとなりつつあります。特にグラフィカルモデリングは、要素間の表面的な相関を取り除くことで、本質的な因果関係を見出す統計手法として研究が進んでいます。例えば、遺伝子間の相互作用のネットワークをグラフィカルモデリングで解析すると、乳がんの原因となっている遺伝子が他の多数の遺伝子の中でもどの遺伝子と影響しあいながら乳がんを進行させるのか、といった情報が得られます。また、音声認識の分野でも、録音した文章中の発音の因果関係を解析することで重点的に対象とする発音を見出し、認識精度を高める、などにも活用されています。
グラフィカルモデリングは、最尤推定を介して数学的には「対数行列式半正定値計画問題」という数理最適化問題と密接に関係しており、この数理最適化問題を高速に求解する数学的手法を設計することは大量データの解析にかかる計算時間の短縮、また、より大規模なデータを解析可能にすることへとつながります。
数理最適化の分野では内点法とよばれる手法がありますが、内点法は数値精度が極めて高い反面、大量データの解析では長時間の計算時間を必要とします。しかしながら、実データを解析するにあたっては内点法ほどの数値精度を必要としない場合が多く、実データに十分な精度の範囲で計算時間を短縮する数学的手法の研究の需要が高まっています。

○研究内容
スペクトラル射影勾配法は1階の微分情報のみで最適化計算を行う点で、2階の微分情報を必要とする内点法と比較して計算時間を抑えられる、という利点があり、研究が近年活発に行われています。しかしながら、従来のスペクトラル射影勾配法では対数行列式半正定値計画問題の制約条件に組み込める条件が簡易なものに限られ、より汎用性の高い条件を課した下で数学的な計算を行う手法が望まれていました。
本研究では、汎用的な線形制約条件を課した対数行列式半正定値計画問題に対する数学的な計算手法を設計しました。制約条件が複雑になると、スペクトラル射影勾配法では主要計算部分である射影計算を複雑に行う必要があったのですが、本研究では2種類の計算量の少ない射影計算を順次適用することで、大幅な計算時間の短縮を実現しました。
本研究で提案した手法と従来手法の計算時間を図示したのが以下のグラフであり、たとえば変数の数が1000の場合には、5356秒かかっていた計算が666秒に短縮され、大幅な高速化を達成しています。図を見ると分かるように、大規模な問題であるほど本研究の計算手法の高速化が著しくなります。


図1:


また、本研究の計算手法の理論的な特徴では、主アプローチとその対称構造を持つ双対アプローチという2つのアプローチを同時に検討することで正確な最適解が得られるという証明を確立しました。これまでの主アプローチあるいは双対アプローチの一方のみを証明する従来手法とは一線を画し、数理最適化の要である双対理論に基づく理論展開を基礎としています。


○今後の課題・波及効果
 本研究で提案した数学的手法により、データ解析を短時間にできるようになっただけでなく、汎用性の高い制約条件も利用できるようになりました。ほかの数理最適化問題や数学的手法と連携することで、さらに大規模なデータ、より複雑なデータを解析の実用化に近づくと考えています。
理論的な側面でも、スペクトラル射影勾配法に双対理論を導入するという新展開が見られ、さらなる発展を検討しています。



簡略図: こちら

譚ア莠ャ蟾・讌ュ螟ァ蟄ヲ