超矩形による貪欲被覆学習の効率的実装と実データによる性能評価  [in Japanese] Efficient Implementation of Greedy Cover Learning by Hyper-Rectangles and Its Classification Performance Evaluation Using Real Data  [in Japanese]

Search this Article

Author(s)

    • 大内 康治 OUCHI Koji
    • 北海道大学 大学院情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University
    • 工藤 峰一 KUDO Mineichi
    • 北海道大学 大学院情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University

Abstract

固定された自然数dに対し,軸に平行な有限個のd次元超矩形の和集合で表現される概念クラスが多項式時間PAC学習可能であることはBlumerらにより示されている.証明に用いられたアルゴリズムは,概念に含まれる事例(正例)全体を被覆する超矩形の集合を,貪欲手続きで求めるというものである.本稿では,Blumerらのアルゴリズムの効率的な実装について検討する.また,このアルゴリズムを実際のnクラス識別問題(n≧2)に通用し,同じく超矩形の和集合を用いる確率的サブクラス法との比較を行う.UCI機械学習レポジトリのデータセットを用いた実験では,ほぼ同等の識別性能となりながらも,貪欲な手法によって生成される超矩形の数が確率的サブクラス法のものよりも少なくなり,多くのデータで7割以上の削減がみられた,

Blumer et al. showed that the class of concepts represented by finite unions of hyper-rectangles in d-dimensional Euclidean space is polynomial-time PAC learnable for a fixed natural number d. In their proof, they constructed an algorithm which conducts a greedy covering of a given positive instances by hyper-rectangles that never cover any one of given negative instances. In this paper, we discuss the efficient implementation of their algorithm. According to our experimental results on n-class classification problems using UCI datasets, Blumer's covering algorithm, in most cases, outputs a hypothesis whose number of component hyper-rectangles is at most 30% of that outputed by randomized subclass method (RSM) using hyper-rectangles as its subclasses while its classification performance is almost the same as RSM.

Journal

  • IEICE technical report

    IEICE technical report 110(265), 99-104, 2010-10-28

    The Institute of Electronics, Information and Communication Engineers

References:  13

Codes

  • NII Article ID (NAID)
    110008153967
  • NII NACSIS-CAT ID (NCID)
    AA12482480
  • Text Lang
    JPN
  • Article Type
    REV
  • ISSN
    09135685
  • NDL Article ID
    10914852
  • NDL Source Classification
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL Call No.
    Z16-940
  • Data Source
    CJP  NDL  NII-ELS 
Page Top