Abstract | ||
---|---|---|
k-Version spaces were introduced in [6] to handle noisy data. They were defined as sets of k-consistent hypotheses; i.e., hypotheses consistent with all but k instances. Although k-version spaces were applied, their implementation was intractable due to the boundary-set representation. This paper argues that to classify with k-version spaces we do not need an explicit representation. Instead we need to solve a general k-consistency problem and a general k0-consistency problem. The general k-consistency problem is to test the hypothesis space for classifier that is k-consistent with the data. The general k0-consistency problem is to test the hypothesis space for classifier that is k-consistent with the data and 0-consistent with a labeled test instance. Hence, our main result is that the k-version-space classification can be (tractably) implemented if we have (tractable) k-consistency-test algorithms and (tractable) k0-consistency-test algorithms. We show how to design these algorithms for any learning algorithm in multi-class classification setting. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1007/978-3-642-15939-8_18 | ECML/PKDD (3) |
Keywords | Field | DocType |
multi class classification,classification | Noisy data,Theoretical computer science,Artificial intelligence,Classifier (linguistics),Machine learning,Mathematics,Version space,Multiclass classification | Conference |
Volume | ISSN | ISBN |
6323 | 0302-9743 | 3-642-15938-9 |
Citations | PageRank | References |
1 | 0.35 | 13 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Evgueni N. Smirnov | 1 | 24 | 20.38 |
Georgi I. Nalbantov | 2 | 4 | 3.56 |
Nikolay Nikolaev | 3 | 88 | 8.85 |