LOCAL HYPERPLANE CLASSIFIERS

摘要: The concept of margin (distance between the decision surface and the closest training point) proved to be a useful approach in machine learning, and led to new classifiers that have good generalization capabilities. The most famous ones are Support Vector Machines (SVMs)[1] that produce a linear decision surface with maximal margin for linearly separable problems. For the non-linearly separable case SVMs map the input into a higher (possibly infinite) dimensional feature space with some nonlinear transformation and build a maximal margin hyperplane there. The trick is that this mapping is never computed directly but implicitly induced by a kernel. While non-linear SVMs can solve any separable classification problem with zero training error, the large margin in the feature space does not necesserily translate into a large margin in the input space [2]. A natural idea is to try and build a large margin decision surface directly in the input space. Would it be possible to find an algorithm that produces a non-linear decision surface which correctly separates the classes and maximizes the margin in the input space? Surprisingly the plain old Nearest Neighbor (NN) algorithm does precisely this. But NN classifiers have too much capacity (VC-dimension) therefore they are often outperformed by SVMs in practice. Figure 1 shows a geometrical explanation of this phenomenon. A possible approach to improve the generalization capability of NN classifiers is to somehow fantasize the missing training samples based on the local linear approximation of the manifold of each class [3]. This paper presents a new algorithm for defining the local hyperplanes …