Article ID Journal Published Year Pages File Type
4950865 Information Processing Letters 2017 11 Pages PDF
Abstract
In this paper, we study the problem of constructing an oblivious decision tree that incurs at most k classification errors, where k is a given integer. We present a randomized rounding algorithm that, given a parameter 0<ϵ<1/2, builds an oblivious decision tree with cost at most (3/(1−2ϵ))ln⁡(n)OPT(I) and produces at most (k/ϵ) errors, where OPT(I) is the optimal cost and n is the number of objects. The probability of failure of this algorithm is at most (n−1)/2n2. The logarithmic factor in the cost of the tree is the best possible attainable, even for k=0, unless P=NP.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,