| Any efficient learning algorithm should at least take a brief look at each exam-ple. But all the examples shouldn’t be given equal attention. This paper proposestwo new algorithms for training support vector machines based on randomized sam-pling idea, one is a simple randomized sampling algorithm (SASVM) and the otheris a stratified randomized sampling algorithm (SS-SVM). When the original dataset israndomly divided into two equal parts, the support vectors from training on both subsetare probably more to be support vectors of the original dataset. Therefore, we get a newalgorithm SASVM by combining the two subsets’s support vectors as a sample set ofthe original dataset. While the above process can be realized recursively, so we can getanother algorithm SS-SVM. Our main work is:1. We develop a simple randomized sampling SVM algorithm SASVM and anal-ysis its approximate error bound and computing complexity, which testify thefeasibility of this sampling idea.2. Based on SASVM algorithm, we develop a stratified randomized sampling SVMalgorithm SS-SVM and analysis its error bound and complexity.3. Experiments done on standard datasets show that SASVM and SS-SVM are bothfeasible and effective when comparing the results with standard SVM and otherrandomized SVM algorithms. |
