Принцип повышения размерности пространства. Метод опорных векторов. Понятие и свойства ядра. Метод Kernel-Trick.
Принцип повышения размерности пространства. Это концепция, используемая в машинном обучении для преобразования данных из более низкой размерности в более высокую, где их легче разделить гиперплоскостью, что особенно полезно в задачах классификации.
Метод опорных векторов (SVM). SVM предлагает найти некоторую гиперплоскость, кривую или линию, которая бы разделяла два класса или более. Разделяющая гиперплоскость должна пролегать таким образом, чтобы максимизировать расстояние между крайними точками подмножеств или, иначе говоря, опорными векторами. Для простоты рассуждений остановимся на решении задачи классификации нового объекта между двумя классами: «зеленый» и «синий» в пространстве двух признаков.
Нотации Г1, Г2 и Г3 обозначают гиперплоскости и их порядковые номера. В приведенном примере оптимальное разделение достигается только линией Г3, т.к. Г1 в принципе не дает корректного разделения, а Г2 имеет сравнительно небольшую величину полосы разделения. Так, если бы мы выбрали в качестве оптимальной разделяющей плоскости Г2, серая метка на графике была бы классифицирована как «зеленый» класс, в то время как она очевидно принадлежит к «синему» классу.
Классификация происходит на основании вычисления отступа наблюдений от разделяющей классы границы:
где – метка класса, может принимать значения и ; – объект наблюдения;
и
– искомые гиперпараметры модели,
характеризующие положение разделяющей
гиперплоскости, при этом
и
.
В случае если
,
исследуемый объект находится на удалении
или непосредственно на границе
получившейся разделяющей полосы и
классифицируется правильно. Все
отрицательные значения
соответствуют ошибкам в работе алгоритма
классификации.
Если же объект попадает внутрь разделяющей полосы, величина зазора принимает значение между и , а само наблюдение объявляется выбросом в классическом понимании работы SVM.
Для объяснения работы
алгоритма в случае линейной неразделимости
вводится поправка на величину ошибки
.
Задача, стоящая перед SVM,
обновляется и теперь состоит в том,
чтобы найти такую гиперплоскость,
которая одновременно обеспечит наибольшую
полосу разделения и наименьшую сумму
остатков
:
где
– норма вектора, перпендикулярного к
разделяющей плоскости;
– регулируемый параметр модели, задается
вручную;
– величина отклонения
-ого
наблюдения от допустимой области вокруг
расчетной функции;
– число экстремальных значений.
Через настройку опционального параметра модели можно добиться того, чтобы экстремальные наблюдения практически не влияли на конечный результат прогнозирования.
Понятие и свойства ядра. Метод Kernel-Trick. Ядро – это функция, которая вычисляет точечное произведение двух векторов в высокоразмерном пространстве. Подобный тип операций получил название Kernel-Trick, потому что дает всю необходимую информацию о взаимном расположении наблюдений и геометрии пространства без вычисления фактических координат данных в новом более высокомерном пространстве. Во-первых, это вычислительно дешевле, во-вторых, это позволяет работать в потенциально «бесконечномерном» пространстве.
Не каждое ядро может быть использовано в методе Kernel-Trick. Свойства, которыми должно обладать ядро, определяются исходя из требований теоремы Мерсера:
Симметричность:
;Положительная полуопределенность:
,
где
–весовые функции,
– функция ядра.
Говоря формальным языком, матрица Грама, формируемая при оценке функции ядра на любом множестве точек, должна быть положительно полуопределенной. Практический смысл заключается в том, чтобы быть уверенными, что вычисление расстояний между точками в пространстве большей размерности, следует те же законам геометрии Гильбертового и, в частности, Евклидового пространства, что и в исходном пространстве.
Свойства гарантируют, что
,
где
– функция, ставящая в соответствие
координатам точки из меньшего пространства,
ее же координаты в большем пространстве.
Расстояние между двумя точками в гиперпространстве:
За счет использования различных ядер SVM получает возможность вычислять линейные и нелинейные закономерности в данных:
Линейное –
,
и полиномиальное –
,
ядра;Радиальное ядро:
.