劣モジュラ性を用いた特徴集合列挙 Enumerating Feature-Sets with Submodularity

この論文をさがす

著者

    • 河原 吉伸 KAWAHARA Y.
    • 大阪大学産業科学研究所 The Institute of Scientific and Industrial Research (ISIR), Osaka University
    • 津田 宏治 TSUDA K.
    • 産業技術総合研究所生命情報工学研究センター National Institute of Advanced Industrial Science and Technology (AIST)
    • 湊 真一 MINATO S.
    • 北海道大学大学院情報科学研究科 Division of Computer Science, Hokkaido University

抄録

特徴選択は,所与の特徴(パラメータや属性,関数などの集合)の中から問題解決に有効なその一部を取り出すタスクであり,機械学習や統計科学,データマイニングなどにおける最も重要な課題の一つである.この問題は近年,解釈性や計算効率の有用性から,疎な解を誘導しやすいノルムを用いた正則化損失関数最小化の枠組みで議論される場合が多い.損失関数の多くは集合関数として見た場合,劣モジュラ性を有するため,本稿では,特徴選択を劣モジュラ関数最適化として定式化する.これは,最も疎な解を誘導しやすいl_0ノルムを用いた正則化損失関数最小化を直接扱っている事に相当する.著者らは,2分決定図(Binary Decision Diagram; BDD)を用いた解空間の表現,及び,特徴を選択する評価関数の劣モジュラ性を用いた効率的な探索により,厳密解を含む最適性の高い解を列挙する方法を提案する.さらに,提案手法の有用性に関する検証例を示す.

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.

収録刊行物

  • 電子情報通信学会技術研究報告. IBISML, 情報論的学習理論と機械学習 = IEICE technical report. IBISML, Information-based induction sciences and machine learning

    電子情報通信学会技術研究報告. IBISML, 情報論的学習理論と機械学習 = IEICE technical report. IBISML, Information-based induction sciences and machine learning 110(476), 63-68, 2011-03-21

    一般社団法人電子情報通信学会

参考文献:  14件中 1-14件 を表示

各種コード

  • NII論文ID(NAID)
    110008688727
  • NII書誌ID(NCID)
    AA12482480
  • 本文言語コード
    JPN
  • 資料種別
    ART
  • ISSN
    09135685
  • NDL 記事登録ID
    11047075
  • NDL 雑誌分類
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL 請求記号
    Z16-940
  • データ提供元
    CJP書誌  NDL  NII-ELS 
ページトップへ