劣モジュラ性を用いた特徴集合列挙

摘要

Selecting relevant features is a fundamental task in machine learning. Although many approaches have been investigated so far, regularized-learning with sparsity-inducing norms, such as LASSO, would be one of the most promising ones. In this paper, we investigate a challenging problem beyond feature selection — feature-set enumeration, where we try to enumerate all ∈-optimal feature-sets in the l_0-regularized feature selection with sub-modular measures. We develop a novel algorithm for this problem based on the branch-and-bound framework, where bounding and cutting are performed using the structure of binary decision diagrams (BDDs) and the submodularity of selection measures. The performance of the proposed algorithm is investigated through experiments with artificial datasets.%特徴選択は，所与の特徴（パラメータや属性，関数などの集合）の中から問題解決に有効なその一部を取り出すタスクであり，機械学習や統計科学，データマイニングなどにおける最も重要な課題の一つである．この問題は近年，解釈性や計算効率の有用性から，疎な解を誘導しやすいノルムを用いた正則化損失関数最小化の枠組みで議論される場合が多い．損失関数の多くは集合関数として見た場合，劣モジュラ性を有するため，本稿では，特徴選択を劣モジュラ関数最適化として定式化する．これは，最も疎な解を誘導しやすいl_0ノルムを用いた正則化損失関数最小化を直接扱っている事に相当する．著者らは，2分決定図（Binary Decision Diagram；BDD）を用いた解空間の表現，及び，特徴を選択する評価関数の劣モジュラ性を用いた効率的な探索により，厳密解を含む最適性の高い解を列挙する方法を提案する．さらに，提案手法の有用性に関する検証例を示す．