We present sequential greedy algorithms that solve the optimization problem present in maximum entropy classification efficiently. We provide formal guarantees about the performance of our algorithms. First, we present an algorithm that assumes knowledge of ρ~* (the margin achievable by a combined classifier of functions belonging to a given class) and outputs a combined classifier that gives margins larger than the target margin minus a small tolerance, in a number of iterations that is logarithmic in the size of the function class. We then remove the separability assumption, and propose an algorithm that is able to achieve the same goal without knowledge of ρ~* with little extra computational cost.
展开▼
