Probably Almost Bayes Decisions

Publication: Research - peer-reviewJournal article – Annual report year: 1996

View graph of relations

In this paper, we investigate the problem of classifying objects which are given by feature vectors with Boolean entries. Our aim is to "(efficiently) learn probably almost optimal classifications" from examples. A classical approach in pattern recognition uses empirical estimations of the Bayesian discriminant functions for this purpose. We analyze this approach for different classes of distribution functions of Boolean features:kth order Bahadur-Lazarsfeld expansions andkth order Chow expansions. In both cases, we obtain upper bounds for the required sample size which are small polynomials in the relevant parameters and which match the lower bounds known for these classes. Moreover, the learning algorithms are efficient.
Original languageEnglish
JournalInformation and Computation
Publication date1996
Volume129
Journal number1
Pages63-71
ISSN0890-5401
StatePublished
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 2701080