Lehrstuhl Mathematik & InformatikHierarchical Design of Fast Minimum Disagreement Algorithms
Abstract. We compose a toolbox for the design of Minimum Disagreement algorithms. This box contains general procedures which transform (without much loss of efficiency) algorithms that are successful for some d-dimensional (geometric) concept class C into algorithms which are successful for a (d+1)-dimensional extension of C. An iterative application of these transformations has the potential of starting with a base algorithm for a trivial problem and ending up at a smart algorithm for a non-trivial problem. In order to make this working, it is essential that the algorithms are not proper, i.e., they return a hypothesis that is not necessarily a member of C. However, the ``price'' for using a super-class H of C is so low that the resulting time bound for achieving accuracy epsilon in the model of agnostic learning is significantly smaller than the time bounds achieved by the up to date best (proper) algorithms. We evaluate the transformation technique for d=2 on both artificial and real-life data sets and demonstrate that it provides a fast algorithm, which can successfully solve practical problems on large data sets.