Быстрое приближенное решение двухклассовой задачи SVM для больших обучающих совокупностей

Abstract

Метод опорных векторов (SVM) является удобным и надежным инструментом решения двухклассовой задачи распознавания, однако в условиях больших обучающих совокупностей он оказывается чрезвычайно трудоемким. В данной работе предлагается простой подход нахождения решения задачи SVМ, основанный на усреднении решающих правил, построенных по небольшим случайным, возможно пересекающимся подвыборкам исходной обучающей совокупности. Предлагаемый подход позволяет быстро найти приближенное (но не сильно отличающееся от точного) решение задачи SVM даже для больших обучающих совокупностей. При этом предлагаемый метод является экономичным по памяти (что обеспечивает возможность его применения для обучения на одной вычислительной машине) и, в то же время, обладает высокой степенью параллелизма, что дает возможность его эффективной реализации с применением технологий параллельных и распределенных вычислений. Support Vector Machines (SVM) is one of the most convenient and reliable tools for solving the two-class recognition problem, but it is very laborious in the case of large training sets. In this paper we propose a simple approach to finding a solution of the SVM problem, based on averaging the decision rules, which are constructed from small random, possibly intersecting subsamples of the initial training set. The proposed approach allows to quickly find an approximate (but not very different from the exact) solution of the SVM problem, even for large training sets. In addition, the proposed approach is memory-efficient and so provides the possibility of training on a single computer, and, at the same time, has a high degree of parallelism and can be effectively implemented using parallel and distributed computing technologies.