離散最適化によるスパースガウスグラフィカルモデル：計算的および統計的観点

要旨: 本稿では、無向ガウスグラフィカルモデルの背後にある疎なグラフを学習する問題、すなわち統計的機械学習における重要な課題を考察する。変数数がpである多変量ガウス分布からn個のサンプルが与えられたとき、p imes pの逆共分散行列（いわゆる精度行列）を推定することが目的である。ただし精度行列は疎（すなわち非ゼロ要素が少ない）であると仮定する。そこで本稿では、擬似尤度関数に対するell_0ペナルティ版に基づく新しい推定量GraphL0BnBを提案する。一方、従来の多くのアプローチはell_1緩和に基づいている。本推定量は凸な混合整数計画法（MIP）として定式化できるが、市販の汎用ソルバを用いる場合p
gtrsim 100あたりを超えると計算が困難になり得る。そこでMIPを解くために、各ノードの緩和問題を、専用の一次（first-order）手法で解くカスタムな非線形分岐限定法（BnB）フレームワークを提案する。BnBフレームワークの重要な構成要素として、独立して興味の対象となる、高品質な原始解（primal solutions）を得るための大規模ソルバを提案する。本推定量に対して、統計的な新規保証（推定と変数選択）を導出し、既存の推定量に対して本アプローチがどのように改善するかを議論する。実データおよび合成データに対する数値実験の結果から、提案するBnBフレームワークは市販の汎用ソルバに比べて大きな優位性を持つこと、また本アプローチは最先端の疎グラフィカルモデル学習手法と比べて、計算時間と統計性能の両面で好ましい性能を示すことが示唆される。