An Experimental Study on Number of Support Vectors in N-bit Parity Problem

Support vector machine (SV machine, SVM) is a genius invention with many merits, such as the non-existence of local minima, the largest separating margins of different clusters, as well as the solid theoretical foundation. However, it is also well-noted that SVMs are frequently with a large number of SVs. In this paper, we investigate the number of SVs in a benchmark problem, the parity problem experimentally. With a large variety of kernel functions, the exhaustive experiments using LibSVM discover that for the N-bit parity problems all 2^N points are created as SVs. The study in this paper indicates that the SMO-based LibSVM training candidly incorporate every point in the parity problem. Since any two neighbored points in the N-bit parity problem are with the opposite signs, the SMO creates an SV each time in iterations for fast satisfying the Lagrangian conditions. As a corollary, the SMO-based SVM training is pretty much entangled into the local information and is therefore a greedy algorithm.