1 Support Vector Machines for Non-Linearly Separable Data {#tutorial_non_linear_svms}
2 =======================================================
7 In this tutorial you will learn how to:
9 - Define the optimization problem for SVMs when it is not possible to separate linearly the
11 - How to configure the parameters to adapt your SVM for this class of problems.
16 Why is it interesting to extend the SVM optimization problem in order to handle non-linearly separable
17 training data? Most of the applications in which SVMs are used in computer vision require a more
18 powerful tool than a simple linear classifier. This stems from the fact that in these tasks __the
19 training data can be rarely separated using an hyperplane__.
21 Consider one of these tasks, for example, face detection. The training data in this case is composed
22 by a set of images that are faces and another set of images that are non-faces (_every other thing
23 in the world except from faces_). This training data is too complex so as to find a representation
24 of each sample (_feature vector_) that could make the whole set of faces linearly separable from the
25 whole set of non-faces.
27 Extension of the Optimization Problem
28 -------------------------------------
30 Remember that using SVMs we obtain a separating hyperplane. Therefore, since the training data is
31 now non-linearly separable, we must admit that the hyperplane found will misclassify some of the
32 samples. This _misclassification_ is a new variable in the optimization that must be taken into
33 account. The new model has to include both the old requirement of finding the hyperplane that gives
34 the biggest margin and the new one of generalizing the training data correctly by not allowing too
35 many classification errors.
37 We start here from the formulation of the optimization problem of finding the hyperplane which
38 maximizes the __margin__ (this is explained in the previous tutorial (@ref tutorial_introduction_to_svm):
40 \f[\min_{\beta, \beta_{0}} L(\beta) = \frac{1}{2}||\beta||^{2} \text{ subject to } y_{i}(\beta^{T} x_{i} + \beta_{0}) \geq 1 \text{ } \forall i\f]
42 There are multiple ways in which this model can be modified so it takes into account the
43 misclassification errors. For example, one could think of minimizing the same quantity plus a
44 constant times the number of misclassification errors in the training data, i.e.:
46 \f[\min ||\beta||^{2} + C \text{(misclassification errors)}\f]
48 However, this one is not a very good solution since, among some other reasons, we do not distinguish
49 between samples that are misclassified with a small distance to their appropriate decision region or
50 samples that are not. Therefore, a better solution will take into account the _distance of the
51 misclassified samples to their correct decision regions_, i.e.:
53 \f[\min ||\beta||^{2} + C \text{(distance of misclassified samples to their correct regions)}\f]
55 For each sample of the training data a new parameter \f$\xi_{i}\f$ is defined. Each one of these
56 parameters contains the distance from its corresponding training sample to their correct decision
57 region. The following picture shows non-linearly separable training data from two classes, a
58 separating hyperplane and the distances to their correct regions of the samples that are
61 ![](images/sample-errors-dist.png)
63 @note Only the distances of the samples that are misclassified are shown in the picture. The
64 distances of the rest of the samples are zero since they lay already in their correct decision
67 The red and blue lines that appear on the picture are the margins to each one of the
68 decision regions. It is very __important__ to realize that each of the \f$\xi_{i}\f$ goes from a
69 misclassified training sample to the margin of its appropriate region.
71 Finally, the new formulation for the optimization problem is:
73 \f[\min_{\beta, \beta_{0}} L(\beta) = ||\beta||^{2} + C \sum_{i} {\xi_{i}} \text{ subject to } y_{i}(\beta^{T} x_{i} + \beta_{0}) \geq 1 - \xi_{i} \text{ and } \xi_{i} \geq 0 \text{ } \forall i\f]
75 How should the parameter C be chosen? It is obvious that the answer to this question depends on how
76 the training data is distributed. Although there is no general answer, it is useful to take into
79 - Large values of C give solutions with _less misclassification errors_ but a _smaller margin_.
80 Consider that in this case it is expensive to make misclassification errors. Since the aim of
81 the optimization is to minimize the argument, few misclassifications errors are allowed.
82 - Small values of C give solutions with _bigger margin_ and _more classification errors_. In this
83 case the minimization does not consider that much the term of the sum so it focuses more on
84 finding a hyperplane with big margin.
89 You may also find the source code in `samples/cpp/tutorial_code/ml/non_linear_svms` folder of the OpenCV source library or
90 [download it from here](https://github.com/opencv/opencv/tree/3.4/samples/cpp/tutorial_code/ml/non_linear_svms/non_linear_svms.cpp).
93 - **Downloadable code**: Click
94 [here](https://github.com/opencv/opencv/tree/3.4/samples/cpp/tutorial_code/ml/non_linear_svms/non_linear_svms.cpp)
97 @include samples/cpp/tutorial_code/ml/non_linear_svms/non_linear_svms.cpp
101 - **Downloadable code**: Click
102 [here](https://github.com/opencv/opencv/tree/3.4/samples/java/tutorial_code/ml/non_linear_svms/NonLinearSVMsDemo.java)
104 - **Code at glance:**
105 @include samples/java/tutorial_code/ml/non_linear_svms/NonLinearSVMsDemo.java
109 - **Downloadable code**: Click
110 [here](https://github.com/opencv/opencv/tree/3.4/samples/python/tutorial_code/ml/non_linear_svms/non_linear_svms.py)
112 - **Code at glance:**
113 @include samples/python/tutorial_code/ml/non_linear_svms/non_linear_svms.py
119 - __Set up the training data__
121 The training data of this exercise is formed by a set of labeled 2D-points that belong to one of
122 two different classes. To make the exercise more appealing, the training data is generated
123 randomly using a uniform probability density functions (PDFs).
125 We have divided the generation of the training data into two main parts.
127 In the first part we generate data for both classes that is linearly separable.
130 @snippet samples/cpp/tutorial_code/ml/non_linear_svms/non_linear_svms.cpp setup1
134 @snippet samples/java/tutorial_code/ml/non_linear_svms/NonLinearSVMsDemo.java setup1
138 @snippet samples/python/tutorial_code/ml/non_linear_svms/non_linear_svms.py setup1
141 In the second part we create data for both classes that is non-linearly separable, data that
145 @snippet samples/cpp/tutorial_code/ml/non_linear_svms/non_linear_svms.cpp setup2
149 @snippet samples/java/tutorial_code/ml/non_linear_svms/NonLinearSVMsDemo.java setup2
153 @snippet samples/python/tutorial_code/ml/non_linear_svms/non_linear_svms.py setup2
156 - __Set up SVM's parameters__
158 @note In the previous tutorial @ref tutorial_introduction_to_svm there is an explanation of the
159 attributes of the class @ref cv::ml::SVM that we configure here before training the SVM.
162 @snippet samples/cpp/tutorial_code/ml/non_linear_svms/non_linear_svms.cpp init
166 @snippet samples/java/tutorial_code/ml/non_linear_svms/NonLinearSVMsDemo.java init
170 @snippet samples/python/tutorial_code/ml/non_linear_svms/non_linear_svms.py init
173 There are just two differences between the configuration we do here and the one that was done in
174 the previous tutorial (@ref tutorial_introduction_to_svm) that we use as reference.
176 - _C_. We chose here a small value of this parameter in order not to punish too much the
177 misclassification errors in the optimization. The idea of doing this stems from the will of
178 obtaining a solution close to the one intuitively expected. However, we recommend to get a
179 better insight of the problem by making adjustments to this parameter.
181 @note In this case there are just very few points in the overlapping region between classes.
182 By giving a smaller value to __FRAC_LINEAR_SEP__ the density of points can be incremented and the
183 impact of the parameter _C_ explored deeply.
185 - _Termination Criteria of the algorithm_. The maximum number of iterations has to be
186 increased considerably in order to solve correctly a problem with non-linearly separable
187 training data. In particular, we have increased in five orders of magnitude this value.
191 We call the method @ref cv::ml::SVM::train to build the SVM model. Watch out that the training
192 process may take a quite long time. Have patiance when your run the program.
195 @snippet samples/cpp/tutorial_code/ml/non_linear_svms/non_linear_svms.cpp train
199 @snippet samples/java/tutorial_code/ml/non_linear_svms/NonLinearSVMsDemo.java train
203 @snippet samples/python/tutorial_code/ml/non_linear_svms/non_linear_svms.py train
206 - __Show the Decision Regions__
208 The method @ref cv::ml::SVM::predict is used to classify an input sample using a trained SVM. In
209 this example we have used this method in order to color the space depending on the prediction done
210 by the SVM. In other words, an image is traversed interpreting its pixels as points of the
211 Cartesian plane. Each of the points is colored depending on the class predicted by the SVM; in
212 dark green if it is the class with label 1 and in dark blue if it is the class with label 2.
215 @snippet samples/cpp/tutorial_code/ml/non_linear_svms/non_linear_svms.cpp show
219 @snippet samples/java/tutorial_code/ml/non_linear_svms/NonLinearSVMsDemo.java show
223 @snippet samples/python/tutorial_code/ml/non_linear_svms/non_linear_svms.py show
226 - __Show the training data__
228 The method @ref cv::circle is used to show the samples that compose the training data. The samples
229 of the class labeled with 1 are shown in light green and in light blue the samples of the class
233 @snippet samples/cpp/tutorial_code/ml/non_linear_svms/non_linear_svms.cpp show_data
237 @snippet samples/java/tutorial_code/ml/non_linear_svms/NonLinearSVMsDemo.java show_data
241 @snippet samples/python/tutorial_code/ml/non_linear_svms/non_linear_svms.py show_data
244 - __Support vectors__
246 We use here a couple of methods to obtain information about the support vectors. The method
247 @ref cv::ml::SVM::getSupportVectors obtain all support vectors. We have used this methods here
248 to find the training examples that are support vectors and highlight them.
251 @snippet samples/cpp/tutorial_code/ml/non_linear_svms/non_linear_svms.cpp show_vectors
255 @snippet samples/java/tutorial_code/ml/non_linear_svms/NonLinearSVMsDemo.java show_vectors
259 @snippet samples/python/tutorial_code/ml/non_linear_svms/non_linear_svms.py show_vectors
265 - The code opens an image and shows the training examples of both classes. The points of one class
266 are represented with light green and light blue ones are used for the other class.
267 - The SVM is trained and used to classify all the pixels of the image. This results in a division
268 of the image in a blue region and a green region. The boundary between both regions is the
269 separating hyperplane. Since the training data is non-linearly separable, it can be seen that
270 some of the examples of both classes are misclassified; some green points lay on the blue region
271 and some blue points lay on the green one.
272 - Finally the support vectors are shown using gray rings around the training examples.
274 ![](images/svm_non_linear_result.png)
276 You may observe a runtime instance of this on the [YouTube here](https://www.youtube.com/watch?v=vFv2yPcSo-Q).
278 @youtube{vFv2yPcSo-Q}