The paper suggests the on-line multi-class classier with a sublinear computational complexity relative to the number of training objects. The proposed approach is based on the combining of two-class probabilistic classiers. Pairwise coupling is a popular multi-class classication method that combines all comparisons for each pair of classes. Unfortunately pairwise coupling suers in many cases from incompatibility in that some regions of its input space the sum of probabilities are not equal to one. In this paper we propose the optimal approximation for probabilities in each point of object space. This paper proposes a new probabilistic interpretation of the Support Vector Machine for obtaining class probabilities. We show how the SVM can be viewed as a maximum likelihood estimate of a class of probabilistic models. As a computational method for big data we use the stochastic gradient descent approach minimizing directly the primal SVM objective. Unfortunately the hinge loss of the true SVM classier did not allow to use SGD procedure for determining the classier bias. In this paper we propose the piece-wise quadratic loss that helps to overcome this obstacle and gives an instrument to obtain the bias from SGD procedure.
into one of k classes. Most of the real world classication applications, such as image search and text recognition, involve many classes. Thus, the user needs to select from amongst a large class of labels in addition to handling a huge data set.
rized into two main categories: "Single Machine approaches" that try to solve a single optimization problem that trains many binary classiers simultaneously and approaches based on combining independent binary classiers. Weston and
ables a multi class problem to be solved in a single optimization criterion. Lee, Lin and Wahba [2] propose the multicategory support vector machine (MSVM), which extends the binary SVM to the multicategory case. The proposed method provides a unifying framework when there are either equal or unequal misclassication costs. Both Weston and Lee formulations have many dummy variables, have no decomposition method and could not be used in the case of big training samples. Crammer and Singer [3] describe the algorithmic implementation of multiclass kernel-based vector machines with ecient iterative decomposition scheme. But proposed algorithm use a lot of memory to cache kernel products.
which are not discussed here but will be documented in the code that we will shortly make available. But the code was never made available.
The dominating approach for solving multiclass problems has been based on reducing a single multiclass problems into multiple binary problems. Constructing of all-versus-all (AVA) or one-versus-all (OVA) classiers is a popular approach in this strategy [4,5,6]. As can be seen from the literature, AVA seems faster and more memory ecient in the case of big sample. It requires O(m2) classiers instead of O(m) (m - number of classes), but each classier is (on average) much smaller. If the time to build a classier is superlinear in the number of data points, AVA is a better choice.
structs a rule for discriminating between every pair of classes and then selecting the class with the most winning two-class decisions. The voting procedure only predicts a class label. In many cases, however, probability estimates are desired.
Machine for obtaining class probabilities. We show how the SVM can be viewed as a maximum likelihood estimate of a class of probabilistic models. As a computational method for big data we use the stochastic gradient descent approach minimizes directly the primal SVM objective. Unfortunately the hinge loss of the true SVM classier did not allow to use SGD procedure for determining the classier bias. The bias term often plays a crucial role when the distribution of the labels is uneven as is typically the case in text processing applications.
This approach simply amounts to adding one more feature to each instance and incorporating the bias into direction vector. The disadvantage of this approach is that we solve a relatively dierent optimization problem, not SVM. Second approach consist in optimizing the non-convex SVM loss as is. But in this case the algorithm has slower convergence rate. In this paper we propose the piecewise quadratic loss that helps to overcome this obstacle and gives an instrument to obtain the bias from SGD procedure.
for pair-wise probabilities dening the pairwise coupling approach. Section 3 reviews the binary SVM. Section 4 presents a numerical study for illustration.
2
The paper considers the classical formulation of the learning pattern recognition problem. We suppose that there are many real-world objects . We also assume that each object ! 2 may be characterized by the label y 2 f0; 1; ::; m 1g, m > 2, and by vector x 2 Rn. In other words, each object is most fully represented by triple (!i; yi; xi); i = 1; ::; N , where N is the count of objects in current set. The number yi in this case is called the class of the object !i, vector xi is a feature vector. The number n, is the dimension of the feature space, indicates the length of vectors xi. Usually we often know only the feature vector xi for each object !i, and doesn’t know its class yi. The recognition problem is to build a function, which requires the feature vector xi and returns the class of an object y^i, and it has to make mistakes as little as possible.
This problem is unsolvable without some additional information about objects. Suppose that we have some set of objects !train; i = 1; ::; N , for which a i feature vector xi is known as well as their class labels yi. The whole set of such objects called the training set that consists of N objects. Say at once that the number N in the case of the large data sets analysis is large enough. For clarity we determine N 10000. 2.1
pairs of classes equals to Cm2 = m(m 1) 2
other classes are not considered when constructing pairwise condence function. Note that it’s necessary to make calculation only for k < l. If k = l the problem does not make sense, and if k > l we can make a simple and obvious transition P lk = 1 P kl.
to construct the general classication rule (z).
agreed with all pairwise probabilities P kl(z). Actually, strictly speaking, this is not always true, since pairwise probabilities P kl(z) are obtained independently.
(
k(z) l(z) = 1
P kl(z) k(z); l 6= k: P kl(z) m X k(z) = 1 k=1 k(z) = 1 m X l(z) = 1 l=1 l6=k
signing an object to its own class is 0:5, it becomes
We have to note that if at least one of the probabilities P kl in the
original formula (
rewritten using the limit
P kq ! +0, q 6= k. Then the formula (
is a hyperplane, which correctly classies almost all objects from the training sample (X; Y ) = f(xj ; yj ); j = 1; :::; N g, d(xj j a; b) = (aT xj + b) for all j = 1; :::; N
q(x; y; a; b) = fmax [0; 1
yd(x; a; b)]g :
(
to be equal to one. However, this leads to fracture of the loss function and, consequently, nondierentiability at the break point. In this paper we use the gradient method, which involves the procedure of dierentiation of the original
in the area between the hyperplane and the gap. It’s so-called support objects, and vector features, describing these objects, are called the support vectors. We need the loss function which is dierentiable at all points, so we take = 2:
of training set in the sense of the Euclidean metric in Rn is maximum yj d(xj j a; b) = yj (aT xj + b) "; " ! max; aT a = 1:
J (a; b) = aT a + C
X j:yj(aT xj+b) 1 1 yj (aT xj + b) 2 ! min(a; b):
Usually an SVM criterion is optimized in a dual form. It gives the exact solution, but the high computational complexity and the need of loading the whole training objects into the memory at the same time prohibit the using of this method on a large training sets. We need the method for online learning, which would produce the adjustment of decision rule over the time on the basis of single or few random training objects for each iteration. In this paper we propose to solve the primal SVM objective using an iterative approximation method of stochastic gradient descent. It allows the on-line training without loading the entire training set to the memory.
for solving the primal SVM objective [11,13,14,17]. However, they only allow us to estimate the normal vector of hyperplane, while ignoring the bias value. In order to estimate the bias methods based on ROC-analysis are usually used, which signicantly aects the nal computational complexity and eliminates the advantage in speed. This paper proposes the method for optimizing the original SVM criterion with a quadratic loss function using the stochastic gradient descent method. This simple method combines high performance, capacity for additional training and simultaneous assessment of the normal vector and bias of the hyperplane.
Let us go to the expanded feature space via introducing new designations: 8 >> c = > > > > < A = > > > >>>: zj = a b
I 0
0T 0
xj
1
yj zjT c)2:
(
Let us denote by cs = abss 2 Rn+1 an approximation of the solution on the s-th iteration of the algorithm. The next approximation is calculated by the formula cs+1 = cs sg (J (cs)) :
8 exph C(1 zT c)2i >>>> 1+ exp[ C(1 zT c)2] ; zT c < P kl = < exph C(1 zT c)2i 1; P lk = 1 >> exp[ C(1 +zT c)2] + exp[ C(1 zT c)2] ; :>> exp[ C(1 +1 zT c)2] + 1 ; zT c > 1; P kl: 1 zT c 1; (21) 4
in opposition to Hastie and Tibshirani method. There were 3 datasets used.
scheme. It’s pretty easy to implement, but it has good recognition abilities.
scent SVM method that have sublinear computational complexity relative to the number of training objects. The main drawback of the original SGD SVM method is inability of evaluating the bias as well as the normal vector of hyperplane. To overcome it we proposed to use the piecewised quadratic loss function.