Support Vector Machines
This chapter gives a short introduction to support vector machines, the basic learning method used, extended, and analyzed for text classification throughout this work. Support vector machines [Cortes and Vapnik, 1995][Vapnik, 1998] were developed by Vapnik et al. based on the Structural Risk Minimization principle [Vapnik, 1982] from statistical learning theory. The idea of structural risk minimization is to find a hypothesis h from a hypothesis space H for which one can guarantee the lowest probability of error Err(h) for a given training sample S 
 
$$({\vec x_1},{y_1}), \ldots ,({\vec x_n},{y_n}) {\vec x_i} \in {\Re ^N},{y_i} \in \{ - 1, + 1\}$$ 
 
(3.1) 
 
of n examples. The following upper bound connects the true error of a hypothesis h with the error Err train (h) of h on the training set and the complexity of h [Vapnik, 1998] (see also Section 1.1).