10,000倍以上の高速化された堅牢な部分集合選択 (ARSS)

大量データからのノイズを含む情報の部分集合選択は、さまざまな応用分野でますます注目を集めています。この問題は、現行の方法が一般的に速度が遅く、外れ値に対して敏感であるため、依然として非常に困難です。上記の2つの課題に対処するため、加速型ロバスト部分集合選択（ARSS: Accelerated Robust Subset Selection）手法を提案します。特に部分集合選択の領域において、本研究では表現損失の測定に $\ell_{p}(0<p\leq1)$-ノルムに基づく指標を初めて用いる試みを行いました。これにより、大きな誤差が目的関数を支配することを防ぎ、外れ値要素に対するロバスト性が大幅に向上しました。実際には、データサイズは通常特徴量の長さよりも遥かに大きい（$N \gg L$）という観察に基づき、計算コストを大幅に削減する高速化ソルバー（ALMと同値変形による）を開発しました。理論的には計算コストが $O(N^{4})$ から $O(N^{2}L)$ へと大きく削減されました。10つのベンチマークデータセットを用いた広範な実験結果は、当手法が最先端の手法を上回るだけでなく、最も関連性のある手法よりも10,000倍以上速いことを示しています。