liu.seSök publikationer i DiVA
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
On the Complexity of Discrete Feature Selection for Optimal Classification
Linköpings universitet, Institutionen för datavetenskap, IISLAB - Laboratoriet för intelligenta informationssystem. Linköpings universitet, Tekniska högskolan. (ADIT)
Harvard University.
2010 (Engelska)Ingår i: IEEE Transaction on Pattern Analysis and Machine Intelligence, ISSN 0162-8828, E-ISSN 1939-3539, Vol. 32, nr 8, s. 1517-U1522Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Consider a classification problem involving only discrete features that are represented as random variables with some prescribed discrete sample space. In this paper, we study the complexity of two feature selection problems. The first problem consists in finding a feature subset of a given size k that has minimal Bayes risk. We show that for any increasing ordering of the Bayes risks of the feature subsets (consistent with an obvious monotonicity constraint), there exists a probability distribution that exhibits that ordering. This implies that solving the first problem requires an exhaustive search over the feature subsets of size k. The second problem consists of finding the minimal feature subset that has minimal Bayes risk. In the light of the complexity of the first problem, one may think that solving the second problem requires an exhaustive search over all of the feature subsets. We show that, under mild assumptions, this is not true. We also study the practical implications of our solutions to the second problem.

Ort, förlag, år, upplaga, sidor
IEEE Institute of Electrical and Electronics , 2010. Vol. 32, nr 8, s. 1517-U1522
Nyckelord [en]
Feature evaluation and selection; classifier design and evaluation; machine learning
Nationell ämneskategori
Teknik och teknologier
Identifikatorer
URN: urn:nbn:se:liu:diva-58348DOI: 10.1109/TPAMI.2010.84ISI: 000278858600012OAI: oai:DiVA.org:liu-58348DiVA, id: diva2:343352
Anmärkning
©2009 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. Jose M Pena and Roland Nilsson, On the Complexity of Discrete Feature Selection for Optimal Classification, 2010, IEEE Transaction on Pattern Analysis and Machine Intelligence, (32), 8, 1517-U1522. http://dx.doi.org/10.1109/TPAMI.2010.84 Tillgänglig från: 2010-08-13 Skapad: 2010-08-11 Senast uppdaterad: 2017-12-12

Open Access i DiVA

fulltext(281 kB)416 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 281 kBChecksumma SHA-512
1cee7bed21b8d60f601e9e17f9a07166f36a4e6d0936accc4538d5100d865b9cc6a1b8900454302fb71135812e10adf977e450f3a76c16367e0d83eadd014cf9
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltext

Personposter BETA

Pena, Jose M

Sök vidare i DiVA

Av författaren/redaktören
Pena, Jose M
Av organisationen
IISLAB - Laboratoriet för intelligenta informationssystemTekniska högskolan
I samma tidskrift
IEEE Transaction on Pattern Analysis and Machine Intelligence
Teknik och teknologier

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 416 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 213 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf