DocumentCode
477773
Title
NP-Hard Problems of Learning from Examples
Author
Chen, Bin ; Quan, Guangri
Author_Institution
Sch. of Software, Harbin Inst. of Technol., Weihai
Volume
2
fYear
2008
fDate
18-20 Oct. 2008
Firstpage
182
Lastpage
186
Abstract
As designing practical algorithms of learning from examples, one has to deal with some optimization problems. The major optimization problems are: the smallest feature subset selection, the smallest decision tree induction, and the smallest k-DNF induction. In this paper, we show that all these optimization problems listed as above are NP-hard, and we present new greedy algorithms for solving these problems.
Keywords
decision trees; greedy algorithms; learning (artificial intelligence); optimisation; NP-hard problems; greedy algorithms; learning; optimization; smallest decision tree induction; smallest feature subset selection; smallest k-DNF induction; Algorithm design and analysis; Decision trees; Design optimization; Fuzzy systems; Greedy algorithms; Matrices; NP-hard problem; Software algorithms; Space technology; Training data; Learning from examples; NP-hard; decision trees; feature subset selection; greedy algorithms; optimization problems; rules;
fLanguage
English
Publisher
ieee
Conference_Titel
Fuzzy Systems and Knowledge Discovery, 2008. FSKD '08. Fifth International Conference on
Conference_Location
Shandong
Print_ISBN
978-0-7695-3305-6
Type
conf
DOI
10.1109/FSKD.2008.406
Filename
4666104
Link To Document