Faculty of Physical and Chemical Engineering

Метод опорных векторов, классический линейный вариант

Содержание: постановка задачи нахождения линейного классификатора для разделения двух классов объектов, которые описываются векторами n-мерного проостранства. Метод опорных векторов, который вычисляет гиперплоскость коразмерности 1, разделяющую два класса точек; различные функции потери. Графическая программа на Python+tkinter, иллюстрирующая метод опорных векторов: "svm.py" (программа использует также модуль R2Graph.py, архив всех файлов: "svm.zip").

Описание метода опорных векторов (Support Vector Machine)

Нелинейный метод опорных векторов

Содержание: Идея нелинейного метода опорных векторов: добавление некоторого набора базовых функций от исходных признаков объекта и расширение описания объекта с их помощью. Построение линейного классификатора в пространстве более высокой размерности.

В классическом методе опорных векторов мы имеем два класса объектов, каждый объект описывается n признаками, представляемыми вещественными числами. Таким образом, объекты x₁, x₂, … x_k представляются точками n-мерного пространства; координаты такой точки равны значениям признаков объекта. В тренировочной выборке объекты x_i первого класса отмечены значением y_i = 1, объекты x_j второго класса — значением y_j = -1. В методе опорных векторов SVM (Support Vector Machine) строится линейный классификатор f(x), который определяется как гиперплоскость, разделяющая два класса точек:

f(x) = ⟨w, x⟩ − b,
x, w ∈ Rⁿ, b ∈ R.

(угловые скобки здесь обозначают скалярное произведение векторов). Если f(x) ≥ 0, то классификатор относит точку x к первому классу, если f(x) < 0, то ко второму. Разделяющая гиперплоскость задается уравнением

⟨w, x⟩ − b = 0.

Здесь w — вектор нормали к гиперплоскости, число b задает смещение гиперплоскости относительно начала координат. Таким образом, линейный классификатор f(x) = f_w,b(x) задается параметрами w, b.

В классическом методе опорных векторов далеко не всегда можно разделить гиперплоскостью два класса точек в n-мерном пространстве:

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

Итак, пусть отображение

φ: Rⁿ → R^m, m > n,
φ(x) = (φ₁(x), φ₂(x), … φ_m(x)), где x = (x₁, x₂, … x_n),

переводит исходный набор признаков x = (x₁, x₂, … x_n) в расширенный набор (φ₁(x), φ₂(x), … φ_m(x)). Пусть нам удалось построить хороший линейный классификатор F(t) в пространстве расширенных признаков, где t∈R^m:

F(t) = ⟨W, t⟩ − B, где W, t∈R^m, B∈R.

Тогда классификатор в исходном пространстве (уже нелинейный!) задается формулой

f(x) = F(φ(x)) = ⟨W, φ(x)⟩ − B.

В простейшем случае в качестве функций φ₁(x₁, … x_n), φ₂(x₁, … x_n), …, φ_m(x₁, … x_n) можно взять всевозможные мономы степени не выше d от переменных x₁, x₂, … x_n (то есть от исходных признаков).

Пусть, например, d = 2. Пусть число исходных признаков n = 2, т.е. объекты представляются точками плоскости R². Тогда расширенный набор признаков представляется всеми мономами степени не выше 2 от переменных x₁, x₂:

φ(x₁, x₂) = (1, x₁, x₂, x₁², x₁x₂, x₂²),

и размерность пространства расширенных признаков равна 6.

Программа "svmNonlinear.py" иллюстрирует использование нелинейного метода опорных векторов. Исходные объекты представляются точками плоскости двух цветов, отмечаемые кликами левой и правой клавиш мыши. В качестве расширенных признаков используются все мономы степени не выше d от координат x и y очередной точки; степень d задается с помощью слайдера в пределах от 1 до 5. Программа после построения нелинейного классификатора f(x) изображает линию нулевого уровня функции

f(x) = 0,

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

Классический случай: степень 1

Квадратичные мономы: степень 2

Кубический многочлен: степень 3

Многочлен степени 4

Многочлен степени 5

В случае полинома высокой степени 5 мы, скорее всего, наблюдаем переобучение. Также форма разделяющей кривой сильно заисит от гиперпараметра С и от функции потери.

Реализация нелинейного метода опорных векторов на Питоне

Ниже приведен скрипт на Питоне в среде Jupyter-Lab, реализующий нелинейный метод опорных векторов. В программе генерируются два множества случайных точек, синие точки принадлежат первому классу, зеленые второму. Признаки объектов, т.е. две координаты точек, дополняются всеми мономами от координат степени не выше d. Разделяющая гиперплоскость, т.е. линейный классификатор

f(x) = ⟨x', W⟩ - B,

строится в расширенном пространстве R^k. Здесь x∈R² — исходная точка, x'∈R^k — точка расширенного пространства, координаты которой представляют собой все произведения (мономы) степени не выше d от координат исходной точки (их число равно k); W∈R^m — вектор нормали к гиперплоскости в расширенном пространстве, B∈R — свободный член.

После построения классификатора программа рисует линию нулевого уровня

f(x) = ⟨x', W⟩ - B = 0,

которая разделяет два класса точек.

import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import minimize
import random
from math import sin, cos, pi
import itertools
from skimage import measure

plt.axes(aspect="equal")
xmin = -10; xmax = 14
ymin = -10; ymax = 14
plt.xlim(xmin, xmax)
plt.ylim(ymin, ymax)
plt.grid()
m = 100
m2 = m//2

v1 = np.array([2., 1.])
v1 /= np.linalg.norm(v1)
n1 = np.array([-v1[1], v1[0]])
class1 = [
    v1*random.normalvariate(2., 2.) +
    n1*random.normalvariate(0., 1.)
    for i in range(m2)
]
plt.scatter(
    [c1[0] for c1 in class1],
    [c1[1] for c1 in class1],
    color="blue"
)

class2 = []
ex = np.array([1., 0])
ey = np.array([0., 1.])
for i in range(m2):
    phi = random.normalvariate(0., pi/2)
    r = random.normalvariate(8., 1.)
    p = ex*cos(phi)*r + ey*sin(phi)*r
    class2.append([p[0], p[1]])

plt.scatter(
    [c2[0] for c2 in class2],
    [c2[1] for c2 in class2],
    color="green"
)
    
classes = class1 + class2
x = np.array([[c[0], c[1]] for c in classes])
y = [1.]*m2 + [-1.]*m2
y = np.array(y)

# Shuffle training data
perm = np.random.permutation(m)
x = x[perm]
y = y[perm]

def monomials(x, degree=2):
    res = [1.]
    for d in range(1, degree + 1):
        for p in itertools.combinations_with_replacement(x, d):
            res.append(np.prod(p))
    return res        

C = 10.  # Hyperparameter
degree = 3

xext = [ monomials(xx, degree) for xx in x ]
xext = np.array(xext)
k = len(xext[0])
wb0 = np.array([0.]*(k + 1))
wb0[0] = 1.

def hingeLoss(c):
    return max(1. - c, 0.)

def lossFunction(wb):
    w = wb[:-1]
    b = wb[-1]
    w2 = w @ w
    s = 0.
    for i in range(m):
        c = y[i]*(w @ xext[i] - b)
        s += hingeLoss(c)
    return w2 + (C/m)*s
    
res = minimize(lossFunction, wb0)
# print(res)
wb = res.x
w = wb[:-1]
b = wb[-1]

print("w =", w)
print("b =", b)

def classifierFunction(x):
    x_ext = monomials(x, degree)
    return w @ x_ext - b

# Draw a line that separate two classes:
# This is the iso-line defined by the equation
#    classifierFunction([x, y]) == 0. 
rows = 50
cols = 50
dx = (xmax - xmin)/cols
dy = (ymax - ymin)/rows
def coordX(j):
    return xmin + j*dx
def coordY(i):
    return ymin + i*dy

a = [[0.]*cols for i in range(rows)]
a = np.array(a)
for i in range(rows):
    yy = coordY(i)
    for j in range(cols):
        xx = coordX(j)
        v = classifierFunction([xx, yy])
        a[i, j] = v

# Draw the iso-line of zero level
contours = measure.find_contours(a, 0.)
for c in contours:
    xx = []
    yy = []
    for p in c:
        xx.append(coordX(p[1]))
        yy.append(coordY(p[0]))
    plt.plot(xx, yy, color="red")    

# Uncomment for standalone application
# plt.show()

Результат работы программы:

Ядровые методы и их использование в нелинейном методе опорных векторов

Содержание: ядровой метод опорных векторов использует следующую идею. Классический метод опорных векторов сводится к задаче минимизации функции при заданных ограничениях типа неравенств, которая решается применением теоремы Куна–Таккера. При этом минимизируемая функция потерь выражается через попарные скалярные произведения векторов-признаков объектов из тренировочной выборки. Таким образом строится линейный классификатор.

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

Описание ядрового варианта метода опорных векторов

Вот несколько скриншотов оконной программы на Python+tkinter, иллюстрирующей применение ядрового метода опорных векторов:
Гауссовское ядро (RBF)

Полиномиальное ядро, степень 2

Полиномиальное ядро, степень 3

В этой программе используется модуль sklearn и его подмодуль svm, в котором реализован ядровый метод опорных векторов. В программе кликами мыши задается массив точек points, при этом точки, отмеченные кликом левой клавиши мыши, относятся к первому классу, другой клавишей — ко второму, номера клавиш мыши содержится в массиве mouseButtons. Вот как выглядит код, вызывающий метод опорных векторов.

Описания и глобальные переменные:

import numpy as np
from sklearn.svm import SVC

classifier = SVC(kernel="rbf")

Обучение классификатора на тренировочной выборке:

        global classifier
        . . .
        if kernel == "rbf":
            classifier = SVC(C=c, kernel="rbf")
        else:
            classifier = SVC(C=c, kernel="poly", degree=polynomialDegree)

        data = [
            [points[i].x, points[i].y]
            for i in range(len(points))
        ]
        data = np.array(data)

        y = [
            (1. if mouseButtons[i] == 1 else (-1.))
            for i in range(len(points))
        ]
        y = np.array(y)

        classifier.fit(data, y)

Для определения класса точки p можно использовать два метода классификатора:
1) метод classifier.predict(x) возвращает 1 для первого класса и -1 для второго;
2) метод decision_function(x) возвращает значение, пропорциональное расстоянию со знаком от точки x до разделяющей гиперплоскости. Для более точного рисования линия уровня естественно использовать именно этот метод.

def classifierValue(p):
    x = np.array([[p.x, p.y]])
    # return classifier.predict(x)
    return classifier.decision_function(x)

Используя значения, возвращаемые классификатором для точек плоскости, программа рисует линию нулевого уровня этой функции, заданную уравнением

classifierValue(p) = 0.

Пример применения ядрового метода опорных векторов в среде Jupyter-Lab

В среде Jupyter-Lab мы сначала генерируем на плоскости случайные точки двух классов так, чтобы их невозможно было разделить прямой линией. Затем мы применяем ядровый метод опорных векторов с Гауссовским ядром "rbf" (Radial Basis Function) и рисуем линию, которая разделяет два класса. Вот код программы (в среде Jupyter-Lab):

# Kernel Support Vector Machine

from scipy.optimize import minimize
import numpy as np
import random
from math import sin, cos
import matplotlib.pyplot as plt
from skimage import measure

from sklearn.svm import SVC

plt.axes(aspect="equal")

m1 = 100
class1 = [ np.array([
    random.normalvariate(1., 1.5), random.normalvariate(1., 0.5)
]) for i in range(m1) ]

m2 = m1
angle1 = -np.pi*2/3
angle2 = np.pi*2/3
ex = np.array([1., 0.]); ey = np.array([0., 1.])
class2 = []
for i in range(m2):
    phi = random.normalvariate(0., 1.)
    r = random.normalvariate(5., 0.5)
    p = ex*cos(phi)*r + ey*sin(phi)*r
    class2.append(p.copy())
    
x = class1 + class2
x = np.array(x)
y = [1.]*len(class1) + [-1.]*len(class2)
y = np.array(y)
m = len(x)
perm = np.random.permutation(m)
x = x[perm]
y = y[perm]

plt.scatter(
    [c[0] for c in x], [c[1] for c in x],
    color=[ "r" if yy > 0. else "g" for yy in y ]
)

degree = 3
C = 2.    # Hyperparameter

# classifier = SVC(C=C, kernel="poly", degree=degree)
classifier = SVC(C=C, kernel="rbf")
classifier.fit(x, y)

def classifierValue(x):
    xx = np.array([  [x[0], x[1]]  ])
    # return classifier.predict(xx)
    return classifier.decision_function(xx)

# Draw the separating line
xmin = min([xx[0] for xx in x]) - 1.
xmax = max([xx[0] for xx in x]) + 1.
ymin = min([xx[1] for xx in x]) - 1.
ymax = max([xx[1] for xx in x]) + 1.
steps = 100

def xcoord(j):
    dx = (xmax - xmin)/steps
    return xmin + j*dx
def ycoord(i):
    dy = (ymax - ymin)/steps
    return ymin + i*dy

# a is a matrix of dimension (steps, steps)
a = np.array([[0.]*steps for iy in range(steps)])
for i in range(steps):
    for j in range(steps):
        xx = np.array([xcoord(j), ycoord(i)])
        a[i, j] = classifierValue(xx)
nullContours = measure.find_contours(a, 0.)
for c in nullContours:
    plt.plot(
        [xcoord(cc[1]) for cc in c], 
        [ycoord(cc[0]) for cc in c],
        color="blue"
    )

# Uncomment the following line for a standalone application
# plt.show()

Вот результат работы этой программы (запущенной в среде Jupyter-Lab):

Исходный код программы: "svmKernel.ipynb".

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

Факульте́т фундаментальной физико-химической инженерии

Информатика, численные методы и программирование

2024-25 учебный год

Материалы 1-го курса

Материалы 2-го курса

1-й курс

1-й семестр (2024-25 уч. год)

Домашнее задание 1

Представление матриц в компьютере и метод Гаусса

Список задач

2-й семестр

Задачи на тему "Вычисление стандартных функций с помощью суммирования рядов"

Матрицы и метод Гаусса

Сортировка

Задачи по теме "Сортировка"

Численное интегрирование

Задачи по теме "Интегрирование"

Использование Qt в графических приложениях

Примеры графических задач на Qt

Задачи на тему "Графика на плоскости с использованием Qt"

Список задач

Задачи на тему "Множества точек на плоскости"

Список задач

2-й курс

3-й семестр

Тема 1: классы в С++

1.1. Классы для поддержки двумерной и трехмерной графики и их использование для решения геометрических задач

Трехмерная геометрия: координаты на поверхности Земли и на карте

Задачи на использование классов в R3-графике

1.2. Реализация классов на C++

Список задач по теме "Реализация классов"

Проект "Стековый калькулятор"

Контейнерные классы в стандартной библиотеке C++

Алгоритмы в стандартной библиотеке C++

Обработка текстов

Классическая криптография

Список задач на тему "Обработка текстов"

Программирование в среде Qt

Задачи на тему Qt

Список задач

4-й семестр (весна 2022)

Домашнее задание 1 (прошлый год)

Кодирование с открытым ключом и элементы теории чисел

Список задач

Классы в Python'е

Операции с векторами и точками

Конструирование собственных классов в Python'е

Примеры классов в Python'е

Задачи по теме "Классы в Python'е"

Работа с матрицами в Python'е

Из программы прошлых лет

Модуль numpy

Задачи на работу с матрицами в Python'е

Графика и оконное программирование на языке Python

Примеры программ

Задачи по геометрии (прошлый год)

Элементы машинного обучения и искусственного интеллекта

Задача линейной регрессии и метод наименьших квадратов

Описание метода наименьших квадратов

Домашнее задание

Метод опорных векторов, классический линейный вариант

Описание метода опорных векторов (Support Vector Machine)

Нелинейный метод опорных векторов

Классический случай: степень 1

Квадратичные мономы: степень 2

Кубический многочлен: степень 3

Многочлен степени 4

Многочлен степени 5

Реализация нелинейного метода опорных векторов на Питоне

Ядровые методы и их использование в нелинейном методе опорных векторов

Описание ядрового варианта метода опорных векторов

Пример применения ядрового метода опорных векторов в среде Jupyter-Lab

Домашнее задание по теме "Машинное обучение"

Сетевые приложения на языке Python, интерфейс сокетов

Примеры программ

Факульте́т фундаментальной
физико-химической инженерии

Задачи на использование классов в R³-графике