Flokis_guy May 17 at 14:20

Интуитивное понимание пространств и ядер в машинном обучении: Часть 1

Hard

9 min

6.6K

Data Mining*Mathematics*Machine learning*Artificial Intelligence

Tutorial

При изучении темы ядер (kernel) в ML/DS программы вузов, роадмэпы и видео на YouTube обычно рассматривают её через призму SVM, не говоря уже о всеми любимых курсах:). Казалось бы, это неплохо: вот тебе краткое объяснение и модель, которая использует ядра. Но, увы, в этих областях желательно понимать многие процессы интуитивно, так сказать — «тяжело в учении, легко в бою». К тому же, эта тема нечто большее, чем просто метод; она позволяет связать многие вещи в машинном обучении в единую картину через пространство, что я и хочу показать в этой статье.

Ядра

Для начала я бы хотел поговорить про сами ядра. Слово «ядро» (kernel) означает центр, зерно чего‑то, к примеру, алгоритма, формулы, системы и так далее. В различных областях это разные вещи. В нашем случае мы условимся, что это просто функция сходства, и в этой статье будем рассматривать её между двумя векторами (хотя это не всегда так, может быть и больше, и можно сравнивать с их помощью даже функции, но тут это лишнее).

Возьмем самый простой пример — линейное ядро, оно же скалярное умножение, оно же внутренний продукт. У нас есть два вектора [3, 4] и [5, 6]. Мы их скалярн о перемножили:

3 ∗ 5 + 4 ∗ 6 и получили 39.

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

Трюк с подъемом

Итак, когда мы разобрались с концепцией ядра, можно перейти к манипуляциям с данными. Сам термин «трюк с подъемом» не является общепринятым, но он хорошо помогает отличить этот метод от трюка с ядром (который мы рассмотрим позже).

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

Трюк с подъемом для 2-мерного пространства признаков в 3-мерное

Итак, что же мы сделали? Мы взяли функцию 𝜑(𝑥):

$\varphi(\mathbf{x}) = \begin{bmatrix} x_1^2 \\ x_2^2 \\ \sqrt{2} x_1 x_2 \end{bmatrix}$

После этого перевели данные в 3-мерное пространство, просто подставив значения. Как видим, данные там линейно разделимы. Мы берем пространство R^D, используем трюк с подъемом в пространство R^J, где D < J, и затем применяем метод, вроде логистической регрессии, для линейной классификации. Однако это может быть дорогостоящим для функции φ(⋅). Для N точек данных, поднятых в J измерений, нам потребуется O(N × J) операций только для предварительной обработки данных. Но мы можем избежать вычисления φ(⋅) полностью, продолжая делать линейную классификацию в этом поднятом пространстве, если будем изобретательны. И этот второй трюк называется трюком с ядром.

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

Матрица Грама

Определение с Википедии:

В линейной алгебре матрица Грама для набора векторов v₁,…,v_n в гильбертовом пространстве представляет собой эрмитову матрицу скалярных произведений, элементы которой заданы скалярными произведениями G_ij= ⟨v_i,v_j⟩.

Нас она интересует, потому что если мы применим скалярное умножение (линейное ядро, внутренний продукт) попарно ко всем данным в нашем наборе, то получим матрицу Грама, которая отображает линейные зависимости между нашими данными, формируя наше исходное пространство признаков. Ибо наше ядро 𝑘(𝑥_𝑛, 𝑥_𝑚) = 𝜑(𝑥_𝑛) ⋅ 𝜑(𝑥_𝑚), где φ(x) = x.

Вот наглядный пример:

Возьмем 4 вектора в 2-х мерном пространстве и попарно найдем сходства построив матрицу Грама.

$\mathbf{v}_1 = \begin{bmatrix} 1 \\ 2 \end{bmatrix}, \quad \mathbf{v}_2 = \begin{bmatrix} 3 \\ 6 \end{bmatrix}, \quad \mathbf{v}_3 = \begin{bmatrix} 1 \\ 10 \end{bmatrix}, \quad \mathbf{v}_4 = \begin{bmatrix} -100 \\ -100 \end{bmatrix}$ $G = \begin{bmatrix} \mathbf{v}_1 \cdot \mathbf{v}_1 & \mathbf{v}_1 \cdot \mathbf{v}_2 & \mathbf{v}_1 \cdot \mathbf{v}_3 & \mathbf{v}_1 \cdot \mathbf{v}_4 \\ \mathbf{v}_2 \cdot \mathbf{v}_1 & \mathbf{v}_2 \cdot \mathbf{v}_2 & \mathbf{v}_2 \cdot \mathbf{v}_3 & \mathbf{v}_2 \cdot \mathbf{v}_4 \\ \mathbf{v}_3 \cdot \mathbf{v}_1 & \mathbf{v}_3 \cdot \mathbf{v}_2 & \mathbf{v}_3 \cdot \mathbf{v}_3 & \mathbf{v}_3 \cdot \mathbf{v}_4 \\ \mathbf{v}_4 \cdot \mathbf{v}_1 & \mathbf{v}_4 \cdot \mathbf{v}_2 & \mathbf{v}_4 \cdot \mathbf{v}_3 & \mathbf{v}_4 \cdot \mathbf{v}_4 \\ \end{bmatrix}$ $\mathbf{v}_1 \cdot \mathbf{v}_1 = 1 \cdot 1 + 2 \cdot 2 = 1 + 4 = 5 \\ \mathbf{v}_1 \cdot \mathbf{v}_2 = 1 \cdot 3 + 2 \cdot 6 = 3 + 12 = 15 \\ \mathbf{v}_1 \cdot \mathbf{v}_3 = 1 \cdot 1 + 2 \cdot 10 = 1 + 20 = 21 \\ \mathbf{v}_1 \cdot \mathbf{v}_4 = 1 \cdot (-100) + 2 \cdot (-100) = -100 - 200 = -300 \\ \mathbf{v}_2 \cdot \mathbf{v}_2 = 3 \cdot 3 + 6 \cdot 6 = 9 + 36 = 45 \\ \mathbf{v}_2 \cdot \mathbf{v}_3 = 3 \cdot 1 + 6 \cdot 10 = 3 + 60 = 63 \\ \mathbf{v}_2 \cdot \mathbf{v}_4 = 3 \cdot (-100) + 6 \cdot (-100) = -300 - 600 = -900 \\ \mathbf{v}_3 \cdot \mathbf{v}_3 = 1 \cdot 1 + 10 \cdot 10 = 1 + 100 = 101 \\ \mathbf{v}_3 \cdot \mathbf{v}_4 = 1 \cdot (-100) + 10 \cdot (-100) = -100 - 1000 = -1100 \\ \mathbf{v}_4 \cdot \mathbf{v}_4 = (-100) \cdot (-100) + (-100) \cdot (-100) = 10000 + 10000 = 20000$ $G = \begin{bmatrix} 5 & 15 & 21 & -300 \\ 15 & 45 & 63 & -900 \\ 21 & 63 & 101 & -1100 \\ -300 & -900 & -1100 & 20000 \end{bmatrix}$

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

Вернемся к нашей функции φ(⋅) и сделаем следующее: повысим наши предыдущие вектора в 3-мерное пространство, попарно вычислим их внутренний продукт и построим матрицу Грама.

Фактически формула каждого элемента матрицы будет выглядеть так:

$\varphi(\mathbf{x}_n)^\top \varphi(\mathbf{x}_m) = \begin{bmatrix} x_{n,1}^2 & x_{n,2}^2 & \sqrt{2} x_{n,1} x_{n,2} \end{bmatrix} \cdot \begin{bmatrix} x_{m,1}^2 \\ x_{m,2}^2 \\ \sqrt{2} x_{m,1} x_{m,2} \end{bmatrix} \\ = x_{n,1}^2 x_{m,1}^2 + x_{n,2}^2 x_{m,2}^2 + 2 x_{n,1} x_{n,2} x_{m,1} x_{m,2}$

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

Трюк с Ядром

Мы вычисляем, как в нашем алгоритме, каждый элемент матрицы вот так:

$\varphi(\mathbf{x}_n)^\top \varphi(\mathbf{x}_m) = \begin{bmatrix} x_{n,1}^2 & x_{n,2}^2 & \sqrt{2} x_{n,1} x_{n,2} \end{bmatrix} \cdot \begin{bmatrix} x_{m,1}^2 \\ x_{m,2}^2 \\ \sqrt{2} x_{m,1} x_{m,2} \end{bmatrix} = \\ x_{n,1}^2 x_{m,1}^2 + x_{n,2}^2 x_{m,2}^2 + 2 x_{n,1} x_{n,2} x_{m,1} x_{m,2}$

Но теперь сделаем это с помощью полиномиального ядра:

$\left( \mathbf{x}_n^\top \mathbf{x}_m \right)^2 = \left( \begin{bmatrix} x_{n,1} & x_{n,2} \end{bmatrix} \cdot \begin{bmatrix} x_{m,1} \\ x_{m,2} \end{bmatrix} \right)^2 = \\ \left( x_{n,1} x_{m,1} + x_{n,2} x_{m,2} \right)^2 = \\ \left( x_{n,1} x_{m,1} \right)^2 + \left( x_{n,2} x_{m,2} \right)^2 + 2 \left( x_{n,1} x_{m,1} \right) \left( x_{n,2} x_{m,2} \right) = \varphi(\mathbf{x}_n)^\top \varphi(\mathbf{x}_m)$

Что сейчас произошло? Вместо того чтобы переносить наши данные в 3-мерное пространство и вычислять скалярное умножение, мы только что вычислили внутренний продукт в двумерном пространстве и затем возвели сумму в квадрат. Хотя оба варианта имеют одинаковое количество математических символов, фактическое количество операций для второго подхода намного меньше. Это происходит потому, что внутренний продукт в двумерном пространстве — это два умножения и сумма. Квадрат — это просто квадрат скаляра, поэтому всего 4 операции. Первый подход занимал 9 операций.

В этом и заключается трюк с ядром: мы можем избежать дорогостоящих операций перевода в большую размерность, найдя подходящую функцию ядра k(x_n, x_m), эквивалентную скалярному умножению в пространстве более высокого измерения. Это позволяет нам дешево построить матрицу Грама, заботясь только о её масштабировании. Полученная матрица Грама будет моделировать линейные зависимости, но уже в более высоком пространстве. Другими словами, трюк с ядром позволяет дешево выполнить трюк с подъемом.

Теорема Мерсера

Теорема Мерсера в работах о функциональном анализе дает условия для формирования ядерного трюка в машинном обучении.

Формальное определение:

Hidden text

Джеймс Мерсер доказал, что любая положительно определенная функция k( x_n, x_m) при x_n,x_m ∈ R^D определяет скалярное произведение векторного пространства V. Таким образом, если у нас есть функция φ(⋅), такая что ⟨φ(x_n),φ(x_m)⟩^V является допустимым скалярным произведением в V, мы знаем, что существует функция ядра, которая может выполнить трюк с подъемом дешево. В качестве альтернативы, если у нас есть положительно определенное ядро, мы можем реконструировать его неявную базисную функцию φ(⋅).

Пусть 𝑋 будет непустым множеством, иногда называемым индексным множеством. Симметричная функция 𝐾: 𝑋 × 𝑋 → 𝑅 называется положительно полуопределённым ядром на 𝑋, если:

$\sum_{i=1}^{n} \sum_{j=1}^{n} c_i c_j K(x_i, x_j) \geq 0 \\ \text{где } x_1, \ldots, x_n \in \mathcal{X}, n \in \mathbb{N}, c_1, \ldots, c_n \in \mathbb{R}.$

То есть, если матрица Грама K, элементы которой определены как K_ij=K(x_i,x_j), является положительно полуопределенной для всех наборов x_i.

Это равнозначно тому, что собственные значения λ_i матрицы Грама K удовлетворяют условию:

$\lambda_i \geq 0 \quad \text{для всех } i$

Итак, ядро может выполнить трюк с ядром, если:

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

Примеры положительно определенных ядер

Некоторые примеры положительно определенных ядер, определенных в евклидовом пространстве R^d, включают:

Линейное ядро:

$K(\mathbf{x}, \mathbf{y}) = \mathbf{x}^T \mathbf{y}, \quad \mathbf{x}, \mathbf{y} \in \mathbb{R}^d$

Полиномиальное ядро:

$K(\mathbf{x}, \mathbf{y}) = (\mathbf{x}^T \mathbf{y} + r)^n, \quad \mathbf{x}, \mathbf{y} \in \mathbb{R}^d, \, r \geq 0, \, n \geq 1$

Гауссовское ядро (RBF ядро):

$K(\mathbf{x}, \mathbf{y}) = e^{-\frac{\|\mathbf{x} - \mathbf{y}\|^2}{2\sigma^2}}, \quad \mathbf{x}, \mathbf{y} \in \mathbb{R}^d, \, \sigma > 0, \\ \text{или} \\ K(\mathbf{x}, \mathbf{y}) = e^{-\lambda \|\mathbf{x} - \mathbf{y}\|^2}, \quad \mathbf{x}, \mathbf{y} \in \mathbb{R}^d, \, \lambda > 0$

Где σ и λ — это ширина ядра. В первом случае, чем меньше значение σ, тем меньше значение под экспонентой и тем более чувствительно ядро к изменениям. Во втором, наоборот, чем больше значение λ, тем более чувствительно.

Бесконечномерное пространство и Гауссово (RBF) ядро

Сейчас мы алгебраически поймём, в чём же «магия» гауссовского ядра относительно его способности возвращать скалярное умножение в бесконечномерном пространстве.

Исходное выражение для ядра RBF при λ = 1/2

$k_{\text{RBF}}(x, y) = \exp \left( -\frac{1}{2} \| x - y \|^2 \right)$

Норма разности в виде скалярного произведения

$\| x - y \|^2 = (x - y) \cdot (x - y)$

Раскрытие скобок в скалярном произведении

$(x - y) \cdot (x - y) = \langle x - y, x - y \rangle$

Линейность и коммутативность скалярного произведения

$\langle x - y, x - y \rangle = \langle x, x \rangle - \langle x, y \rangle - \langle y, x \rangle + \langle y, y \rangle$

выражение упрощается:

$\langle x - y, x - y \rangle = \langle x, x \rangle - 2\langle x, y \rangle + \langle y, y \rangle$

Подстановка в экспоненту

$k_{\text{RBF}}(x, y) = \exp \left( -\frac{1}{2} \left( \langle x, x \rangle - 2\langle x, y \rangle + \langle y, y \rangle \right) \right)$

Разделение экспоненты

$\exp \left( -\frac{1}{2} \left( \langle x, x \rangle - 2\langle x, y \rangle + \langle y, y \rangle \right) \right) = \\ \exp \left( -\frac{1}{2} \langle x, x \rangle \right) \cdot \exp \left( -\frac{1}{2} \langle y, y \rangle \right) \cdot \exp \left( \langle x, y \rangle \right)$

Определение 𝐶

Представим первые два множителя как 𝐶, так как в данном случае они нас не интересуют из-за того, что учитывают норму векторов, а не взаимосвязь между векторами x и y:

$C = \exp \left( -\frac{1}{2} \| x \|^2 \right) \cdot \exp \left( -\frac{1}{2} \| y \|^2 \right)$

Обновлённое выражение для ядра RBF

$k_{\text{RBF}}(x, y) = C \cdot \exp \left( \langle x, y \rangle \right)$

Разложение экспоненты через ряд Тейлора

$\exp(x) = \sum_{r=0}^{\infty} \frac{x^r}{r!}$

Применение ряда Тейлора к exp⁡(⟨𝑥,𝑦⟩)

$\exp \left( \langle x, y \rangle \right) = \sum_{r=0}^{\infty} \frac{\langle x, y \rangle^r}{r!}$

Полиномиальное ядро

$k_{\text{poly}(r)}(x, y) = (\langle x, y \rangle)^r$

Подстановка полиномиального ядра

$\exp \left( \langle x, y \rangle \right) = \sum_{r=0}^{\infty} \frac{k_{\text{poly}(r)}(x, y)}{r!}$

Итоговое выражение для ядра RBF

$k_{\text{RBF}}(x, y) = C \cdot \sum_{r=0}^{\infty} \frac{k_{\text{poly}(r)}(x, y)}{r!} \\ \text{где} \quad C = \exp \left( -\frac{1}{2} \| x \|^2 \right) \cdot \exp \left( -\frac{1}{2} \| y \|^2 \right)$

Таким образом, RBF ядро можно рассматривать как бесконечную сумму полиномиальных ядер. Вот почему матрица Грама, построенная с их помощью, будет моделировать наши данные в бесконечномерном пространстве.

Обобщаем информацию

Итак, мы полностью разобрались с работой ядер, ядерного трюка и изменением пространства. Теперь перейдём к пониманию, о котором я говорил в начале статьи.

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

В качестве первого примера рассмотрим классическую полносвязную нейронную сеть. Обычно её объясняют через связи, веса и прочее. Я предлагаю обобщить этот подход и сделать его более модульным — через пространство. В полносвязной нейронной сети (и не только) скрытый слой фактически выполняет трюк с подъемом данных в многомерное пространство. Мы подаем данные на вход, а затем рекурсивно поднимаем их от слоя к слою нашей сети (или понижаем размерность), где количество нейронов в каждом скрытом слое определяет размерность пространства. И фактически это и есть наша новая функция φ(⋅) для изменения пространства.

Для иллюстрации мы возьмем наш предыдущий датасет make_circles и обучим на нём полносвязную нейронную сеть без функций активации (2 входа, 3 нейрона в скрытом слое, 2 выхода) и отобразим данные после выхода из скрытого слоя.

Примечание: цвет означает предсказание модели на принадлежность определенному классу.

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

Теперь рассмотрим случай с функциями активации (sigmoid). С ними наша нейронная сеть становится более сложной функцией φ(⋅), которая лучше обучается изменять пространство признаков так, чтобы в конце выходной слой мог правильно классифицировать векторы.

Вернёмся опять к нашей нейросети без функций активации. Так ли всё безнадежно, что нам нужно использовать функции активации? Нет! Никто нам не мешает добавить модульность и предварительно обработать данные, используя трюк с ядром. В данном случае мы будем использовать RBF ядро и представим наши данные в бесконечномерном пространстве, надеясь, что там нейросеть без функций активации сможет их классифицировать максимально точно.

Можно заявить: «Ок, с нейронной сетью и с многими архитектурами, использующими гиперплоскость и изменение пространства для выполнения задачи, всё понятно». Возьмём ещё одну популярную архитектуру — дерево решений. Само по себе оно никак не трансформирует пространство, что же с ним? Да, это верно, но при этом оно делит и структурирует его. Геометрически дерево решений разбивает пространство признаков на оси, перпендикулярные осям признаков.

Рассмотрим это на примере двухмерного пространства признаков с признаками 𝑥₁ и 𝑥₂:

Начальное состояние:
- Пространство признаков представляет собой плоскость, где каждый точка соответствует определенным значениям 𝑥₁ и 𝑥₂.
Первое разбиение:
- Дерево решений выбирает признак 𝑋1 и пороговое значение 𝑥1. Пространство разбивается на две части по линии 𝑋1 = 𝑥1:
  - Все точки, у которых 𝑋1 ≤ 𝑥1, находятся слева от линии.
  - Все точки, у которых 𝑋1 > 𝑥1, находятся справа от линии.
  Геометрически это означает, что пространство делится вертикальной линией.
Второе разбиение:
- Теперь каждая из двух частей пространства рассматривается отдельно. Предположим, что в левой части (𝑋1 ≤ 𝑥1) выбирается признак 𝑋2 и пороговое значение 𝑥2. Пространство теперь делится горизонтальной линией 𝑋2 = 𝑥2:
  - Все точки, у которых 𝑋2 ≤ 𝑥2, находятся ниже линии.
  - Все точки, у которых 𝑋2 > 𝑥2, находятся выше линии.
  Геометрически это означает, что левая часть пространства теперь делится горизонтальной линией.

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

Зеленый цвет означает что чай вкусный, красный - что чай не вкусный. Пороговое значение для температуры - 30 градусов, сладость является бинарным признаком

Вернёмся опять к нашему датасету с кругами и построим три дерева решений: первое будет работать с исходными данными, второе — с данными, предварительно преобразованными с помощью функции φ( x₁², x₂², sqrt(2)x₁x₂) а третье — с использованием предварительно ядра RBF. И посмотрим, как будет различаться структура дерева.

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

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

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

Дополнительные источники

Gregory Gundersen — Implicit Lifting and the Kernel Trick

Wikipedia — Positive-definite kernel

Wikipedia — Mercer's theorem

Tags:

Hubs: