Ядерный трюк (Kernel Trick)

Ядерный трюк (Kernel Trick, Kernel Function, уловка с ядром) – способ классификации, позволяющий работать в исходном пространстве Признаков (Feature), не вычисляя координаты данных в пространстве более высокой размерности.

Метод опорных векторов

Чтобы помочь вам понять, что такое ядерный трюк ​​и почему он важен, я сначала познакомлю вас с основами Метода опорных векторов (SVM).

SVM – это Алгоритм (Algorithm) Машинного обучения (ML) с учителем, который в основном используется для Классификации (Classification). Он учится разделять группы Наблюдений (Observation), формируя границы принятия решений.

На графике выше мы замечаем, что существует два класса наблюдений: синие и сиреневые точки. Есть множество способов разделить эти два класса, как показано на графике слева. Однако мы хотим найти «лучшую» Гиперплоскость (Hyperplane), которая могла бы максимизировать расстояние между этими двумя классами, что означает, что расстояние между гиперплоскостью и ближайшими точками данных с каждой стороны является наибольшим. В зависимости от того, на какой стороне гиперплоскости находится новая точка данных, мы могли бы причислить ее к тому или иному классу.

В приведенном выше примере это звучит просто. Однако не все данные можно разделить линейно. Фактически, в реальном мире почти все данные распределены случайным образом, что затрудняет линейное разделение.

Почему так важно использовать уловку с ядром? Как вы можете видеть на картинке выше, если мы найдем способ сопоставить данные из двухмерного пространства в трехмерном, то сможем найти способ принятия решений, который четко разделяет точки на классы. Моя первая мысль об этом процессе преобразования данных состоит в том, чтобы сопоставить все точки данных с более высоким измерением (в данном случае с третьим), найти границу и провести классификацию.

Однако, когда появляется все больше и больше измерений, вычисления в этом пространстве становятся все более дорогими. Вот тут-то и появляется уловка с ядром. Она позволяет нам работать в исходном пространстве функций, не вычисляя координаты данных в пространстве более высокой размерности.

Обучение классификатора линейных опорных векторов, как и почти любая проблема в машинном обучении и в жизни, является проблемой оптимизации. Мы максимизируем Поле (Margin) – расстояние, разделяющее ближайшую пару точек данных, принадлежащих противоположным классам:

Эти точки называются опорными векторами, потому что они представляют собой данные наблюдений, которые «поддерживают» или определяют границу принятия решения. Чтобы обучить классификатор опорных векторов, мы находим гиперплоскость с максимальным запасом или оптимальную разделяющую гиперплоскость, которая разделяет два класса, чтобы сделать точные прогнозы классификации.

Опорные векторы – это точки на пунктирных линиях. Расстояние от пунктирной линии до сплошной линии – это поле, представленное стрелками.

Машины опорных векторов гораздо труднее интерпретировать в более высоких измерениях. Намного сложнее визуализировать, как данные могут быть линейно разделены и как будет выглядеть граница принятия решения. В трехмерном пространстве гиперплоскость – это обычная двумерная плоскость.

Классификация опорных векторов основана на этом понятии линейно разделяемых данных. Классификация с Мягким полем (Soft Margin) может компенсировать некоторые ошибки классификации обучающих данных в случае, когда данные не являются идеально линейно разделимыми. Однако на практике данные часто очень далеки от линейного разделения, и нам нужно преобразовать их в пространство более высокой размерности, чтобы соответствовать классификатору опорных векторов.

Нелинейные преобразования

Если данные нельзя линейно разделить в исходном или входном пространстве, мы применяем преобразования, которые конвертируют данные из исходного пространства в пространство признаков более высокого измерения. Цель состоит в том, чтобы после преобразования в пространство более высокой размерности классы теперь линейно разделялись в этом пространстве функций более высокой размерности. Затем мы можем установить границу решения, чтобы разделить классы и сделать прогнозы. Решение о границах будет гиперплоскостью.

Ядерный трюк и Scikit-learn

Давайте посмотрим, как уловка реализована в SkLearn. Для начала импортируем необходимые библиотеки:

import pandas as pd
import numpy as np

import matplotlib
import matplotlib.pyplot as plt

import seaborn as sns

import sklearn as sk
from sklearn.datasets import make_classification
from sklearn.datasets import make_circles
from sklearn import preprocessing

Сгенерируем игрушечный Датасет (Dataset) на тысячу наблюдений, причем точки обоих классов формируют эллипсы:

x, y = make_circles(n_samples = 1000, noise = 0.09)
x = preprocessing.scale(x)

# Разделение набора на тренировочную и тестовую части 
x_test = x[:500]
y_test = y[:500]
x = x[500:]
y = y[500:]

# Фильтруем точки по оси y – выбираем только равные [0, -1, 1]
y = np.where(y == 0, -1, 1)
y_test = np.where(y_test == 0, -1, 1)

sns.scatterplot(x[:, 0], x[:, 1], hue = y.reshape(-1))

Одно кольцо "опоясывает" другое, и реализован какой-никакой Шум (Noise), делающий картину чуть реалистичнее:

Теперь нам предстоит создать собственный класс метода опорных векторов: научить модель использовать т.н. Гауссово ядро. Ядро для сглаживания определяет, как вычисляется среднее значение между соседними точками. Ядро Гаусса имеет форму кривой Нормального распределения (Normal Distribution). sigma_sq (sigma squared – сигма в квадрате) – квадрат распределения Остатков (Residual), который рассматривается как показатель Дисперсии (Variance) распределения Целевой переменной (Target Variable) y. Действительно, это распределение необходимо для метода максимального правдоподобия.

class support_vector_machine:
    def __init__(self, C = 10, features = 2, sigma_sq = 0.1, kernel = "None"):
        self.C = C
        self.features = features
        self.sigma_sq = sigma_sq
        self.kernel = kernel
        self.weights = np.zeros(features)
        self.bias = 0.
        
    # Определяем меру схожести эллипсов
    def __similarity(self, x, l):
        # Вычисляем экспоненциальную функцию
        return np.exp(-sum((x - l) ** 2) / (2 * self.sigma_sq))

    # Усредняем границу классов
    def gaussian_kernel(self, x1, x):
        m = x.shape[0]
        n = x1.shape[0]
        op = [[self.__similarity(x1[x_index], x[l_index]) for l_index in range(m)] for x_index in range(n)]
        return np.array(op)

    # Вычисляем потери классификации
    def loss_function(self, y, y_hat):
        sum_terms = 1 - y * y_hat
        sum_terms = np.where(sum_terms < 0, 0, sum_terms)
        return (self.C * np.sum(sum_terms) / len(y) + sum(self.weights ** 2) / 2)

    # Обучаем модель
    def fit(self, x_train, y_train, epochs = 1000, print_every_nth_epoch = 100, learning_rate = 0.01):
        y = y_train.copy()
        x = x_train.copy()
        self.initial = x.copy()
        
        assert x.shape[0] == y.shape[0] , "Samples of x and y don't match."
        assert x.shape[1] == self.features , "Number of Features don't match"
        
        if(self.kernel == "gaussian"):
            x = self.gaussian_kernel(x, x)
            m = x.shape[0]
            self.weights = np.zeros(m)

        n = x.shape[0]
        
        for epoch in range(epochs):
        	# np.dot – скалярное произведение двух массивов
            y_hat = np.dot(x, self.weights) + self.bias 
            grad_weights = (-self.C * np.multiply(y, x.T).T + self.weights).T
            
            for weight in range(self.weights.shape[0]):
                grad_weights[weight] = np.where(1 - y_hat <= 0, self.weights[weight], grad_weights[weight])
            
            grad_weights = np.sum(grad_weights, axis = 1)
            self.weights -= learning_rate * grad_weights / n
            grad_bias = -y * self.bias
            grad_bias = np.where(1 - y_hat <= 0, 0, grad_bias)
            grad_bias = sum(grad_bias)
            self.bias -= grad_bias * learning_rate / n
            if((epoch + 1) % print_every_nth_epoch == 0):
                print("Эпоха {} --> Потери = {}".format(epoch + 1, self.loss_function(y, y_hat)))
    
    # Оцениваем предсказание
    def evaluate(self, x, y):
        pred = self.predict(x)
        pred = np.where(pred == -1, 0, 1)
        diff = np.abs(np.where(y == -1, 0, 1) - pred) # np.abs вычисляет абсоюлтное значение (модуль числа)
        return((len(diff) - sum(diff)) / len(diff))

    # Предсказываем класс для новых наблюдений
    def predict(self, x):
        if(self.kernel == "gaussian"):
            x = self.gaussian_kernel(x, self.initial)
        return np.where(np.dot(x, self.weights) + self.bias > 0, 1, -1)

Ну что же, самая громоздкая ячейка пройдена, дело за малым – создадим функцию визуализации результата классификации:

def visualize(model, title):
    print("Тестовая точность = {}".format(model.evaluate(x_test, y_test)))
    # Для наглядности точки заливаются в двумерный график, где x находится в пределах от -5 до 6, а y – от -5 до 4
    x1 = np.arange(-5, 6, 0.3) # np.arange возвращает равномерно раскиданные значения с шагом 0.3 в интервале от -5 до 6
    x2 = np.arange(-5, 4, 0.3)
    
    for i in range(len(x1)):
        for j in range(len(x2)):
        	# Генерируем предсказания классов точек
            pred = model.predict(np.array([np.array(np.array([x1[i], x2[j]]))]))[0]
            if(pred > 0.5):
                plt.scatter(x1[i], x2[j], c = "r")
            else:
                plt.scatter(x1[i], x2[j], c = "b")
    plt.title(title)
    plt.show()

Создадим модель – экземпляр класса support_vector_machine и обучим модель в 20 эпох:

model = support_vector_machine(C = 10, kernel = "gaussian", sigma_sq = 0.01)
model.fit(x, y, epochs = 20, print_every_nth_epoch = 2, learning_rate = 0.01)
print("Точность обучения = {}".format(model.evaluate(x, y)))

Само по себе значение Функции потерь (Loss Function) по-настоящему начинает "играть", когда рассматривается в сравнении с предыдущими итерациями обучения. В нашем случае, к двадцатой эпохе потери значительно снижаются:

Эпоха 2 --> Потери = 9.975194749508915
Эпоха 4 --> Потери = 9.9268022983303
Эпоха 6 --> Потери = 9.880306978905201
Эпоха 8 --> Потери = 9.835634230178764
Эпоха 10 --> Потери = 9.792712425248418
Эпоха 12 --> Потери = 9.751472755823215
Эпоха 14 --> Потери = 9.711849121234396
Эпоха 16 --> Потери = 9.673778021817862
Эпоха 18 --> Потери = 9.637198456496362
Эпоха 20 --> Потери = 9.602051824395948
Точность обучения = 0.876

Классифицирующее предсказание готово. Визуализируем результат собственной функцией visualize():

visualize(model, "Метод опорных векторов с гауссовым ядром")

На графике ниже не упорядоченные вдруг случайные точки, а их плотность их распределения относительно друг друга. В результате усреднения границ зона малого эллипсоида была как бы ужата. На стадии  

Ноутбук, не требующий дополнительной настройки на момент написания статьи, можно скачать здесь.

Авторы оригинальных статей: Drew Wilimitis, Grace Zhang, Prathamesh Bhalekar