11.5 Support Vector Machines and Kernels

A support vector machine [16] is a supervised machine learning method that distributes instances into two classes (extensions with more than two classes are also available). Using a set of training examples, a hyperplane is calculated that separates data of the two different classes from each other and maximizes the margin of the hyperplane. This margin is defined by the instances that are located closest to the hyperplane. Usually, a complete separation is not possible. Therefore, vectors on the wrong side of the hyperplane are allowed but penalized. The support vector optimization problem is given by [22]

(11.1)

with the constraints

(11.2)

where , vector, orthographic to the hyperplane; , parameter; , feature vectors; y_i { − 1, + 1}, class labels; ., ., the scalar product; ξ_i, slack variables; , a positive constant.

This optimization problem stated in Formulas (11.1) and (11.2) is given in the so-called primal representation. It can be converted into the equivalent dual representation

(11.3)

with the constraints

(11.4)

where α, the vector to be determined by the optimization; ; , a positive constant.

In recent implementations of support vector machines, the scalar product x_i, x_j can be replaced by an arbitrary user-provided kernel function K. The only conditions on such a function are that the matrix of kernel values is positive-semidefinite and symmetric. The dual representation allows it to apply a support vector machine on problems where the vector representations x_i are unknown or represented in an infinite space. Only the kernel function K has to be defined. Thus, the dual representation makes it possible to compare graphs and trees that have no natural vector representation. In the next sections, we demonstrate how support vector machines and a graph kernel can be employed for hyponymy harvesting.