def show_SVM(data, target, clf, grid=None, show_borders=False):
    trained_clf = show_classifier(data,
                                  target,
                                  clf,
                                  grid=grid,
                                  proba=False);
    xx = np.linspace(data.x.min() - 1, data.x.max() + 1)
    w = trained_clf.coef_[0]
    a = -w[0] / w[1]
    yy = a * xx - (trained_clf.intercept_[0]) / w[1]
    plot(xx, yy, 'k-')
    if show_borders:
        b = trained_clf.support_vectors_[0]
        yy_down = a * xx + (b[1] - a * b[0])
        b = trained_clf.support_vectors_[-1]
        yy_up = a * xx + (b[1] - a * b[0])
        plot(xx, yy_down, 'k--')
        plot(xx, yy_up, 'k--')
    plt.scatter(trained_clf.support_vectors_[:, 0],
                trained_clf.support_vectors_[:, 1],
                s=80, facecolors='none');

from sklearn.svm import SVC # SVC использует libsvm для решения двойственной задачи SVM и поддерживает ядра
# можно было обойтись LinearSVC, но из него нельзя получить опорные векторы
random = np.random.RandomState(19)
n = 200
df1 = pd.DataFrame(data=random.multivariate_normal((0,0), [[1, 0.3], [0.3, 0.7]], n), columns=['x', 'y'])
df1['target'] = 0
df2 = pd.DataFrame(data=random.multivariate_normal((4,6), [[1, -0.5], [-0.5, 1.6]], n), columns=['x', 'y'])
df2['target'] = 1
separable_data = pd.concat([df1, df2], ignore_index=True)
separable_data.plot(kind='scatter', x='x', y='y', c='target', colormap='autumn', alpha=0.75, colorbar=False);

separable_grid = get_grid(separable_data, 0.03)
show_SVM(separable_data[['x', 'y']],
         separable_data.target, 
         SVC(kernel='linear'),
         grid=separable_grid,
         show_borders=True)

"""
Explanation: Линейные классификаторы
$$a(x) = sign(\left<x, w\right> - w_0)$$
SVM
$$ \sum_{i=0}^l (1-M_i(w, w_0))_+ + \frac{1}{2C} ||w||^2 \to min $$
Линейно разделимая выборка
$$\begin{cases}\frac{||w||^2}2\rightarrow\min \ M_i(w, w_0) \ge 1,\ i=1, \dots, l\end{cases}$$
End of explanation
"""


show_SVM(features,
         data.target, 
         SVC(kernel='linear'),
         grid=big_grid)

"""
Explanation: Линейно неразделимая выборка
$$\begin{cases} \frac{||w||^2}2+ C \sum_\limits{i=1}^l \xi_i \to \min  \ M_i(w, w_0) \ge 1-\xi_i,\ i=1, \dots, l \ \xi_i\geqslant 0,\ i=1, \dots, l\end{cases}$$
End of explanation
"""


n = 200
random = np.random.RandomState(17)
df1 = pd.DataFrame(data=random.multivariate_normal((0,0), [[1, 0.3], [0.3, 0.7]], n), columns=['x', 'y'])
df1['target'] = 0
df2 = pd.DataFrame(data=random.multivariate_normal((1,2), [[1, -0.5], [-0.5, 1.6]], n), columns=['x', 'y'])
df2['target'] = 1
data = pd.concat([df1, df2], ignore_index=True)
features = data[['x', 'y']]
data.plot(kind='scatter', x='x', y='y', c='target', colormap='autumn', alpha=0.75, colorbar=False);

figure(figsize=(15,15))
grid = get_grid(features, 0.05)
for i in range(1,4):
    for j in range(1,4):
        subplot(3, 3, 3 * (i - 1) + j)
        C = 10**(i-2)
        gamma = 10**(j-2)
        show_classifier(features, data.target, 
                        SVC(kernel='rbf', C=C, gamma=gamma),
                        proba=False,
                        grid=grid);        
        title('C={:.1f}; gamma={:.1f}'.format(C, gamma))

"""
Explanation: Двойственная задача
Перед нами по-прежнему задача выпуклого программирования. Ей эквивалентна двойственная задача (здесь она уже немного преобразована): $$ \begin{cases} -\sum\limits_{i=1}^l\lambda_i+\frac12\sum\limits_{i=1}^l\sum\limits_{j=1}^l\lambda_i\lambda_j y_i y_j\left<x_i, x_j\right>\rightarrow\min \ \forall i: 0 \le \lambda_i \le C \ \sum\limits_{i=1}^l\lambda_i y_i = 0 \end{cases} $$ $\lambda_i$ - двойственные переменные. Если $\lambda_i=0$, то ограничение на отступ $i$-го объекта неактивно (выполнено строгое неравенство), объект верно классифицируется «с запасом» и не влияет на разделяющую плоскость.
Классификатор можно выразить через решение двойственной задачи: $$\tilde y(x)=\operatorname{sign}(\mathscr{L}(\sum\limits_{i=1}^l\lambda_i y_i\left<x_i, x_j\right>-w_0\bigr)$$ $w_0$ можно найти, пользуясь равенством $1$ отступов опорных объектов.
Ядровой переход
Распространённые ядра:
Полиномиальные $$K(x_1,x_2)=\left<x_1, x_2\right>^d
\K(x_1,x_2)=(\left<x_1, x_2\right>+1)^d$$
Сигмоидное
$$K(x_1,x_2)=\operatorname{th}(\gamma\left<x_1, x_2\right>+r)$$
Ядро RBF(radial basis functions)
$$K(x_1,x_2)=e^{-\gamma||x_1-x_2||^2}$$
End of explanation
"""


