Интуитивное понимание пространств и ядер в машинном обучении: Часть 1
При изучении темы ядер (kernel) в ML/DS программы вузов, роадмэпы и видео на YouTube обычно рассматривают её через призму SVM, не говоря уже о всеми любимых курсах:). Казалось бы, это неплохо: вот тебе краткое объяснение и модель, которая использует ядра. Но, увы, в этих областях желательно понимать многие процессы интуитивно, так сказать — «тяжело в учении, легко в бою». К тому же, эта тема нечто большее, чем просто метод; она позволяет связать многие вещи в машинном обучении в единую картину через пространство, что я и хочу показать в этой статье.
Ядра
Для начала я бы хотел поговорить про сами ядра. Слово «ядро» (kernel) означает центр, зерно чего‑то, к примеру, алгоритма, формулы, системы и так далее. В различных областях это разные вещи. В нашем случае мы условимся, что это просто функция сходства, и в этой статье будем рассматривать её между двумя векторами (хотя это не всегда так, может быть и больше, и можно сравнивать с их помощью даже функции, но тут это лишнее).
Возьмем самый простой пример — линейное ядро, оно же скалярное умножение, оно же внутренний продукт. У нас есть два вектора [3, 4] и [5, 6]. Мы их скалярн о перемножили:
3 ∗ 5 + 4 ∗ 6 и получили 39.
Это и есть наша мера сходства. В контексте линейного ядра её сложно интерпретировать, ибо это проекция одного вектора на другой, умноженная на длину вектора, на который проецируется. Но чем больше само число (скаляр), тем более схожи вектора, и наоборот.
Трюк с подъемом
Итак, когда мы разобрались с концепцией ядра, можно перейти к манипуляциям с данными. Сам термин «трюк с подъемом» не является общепринятым, но он хорошо помогает отличить этот метод от трюка с ядром (который мы рассмотрим позже).
Задача классификации. В машинном обучении во многих моделях задача классификации сводится к поиску гиперплоскости, которая максимально точно разделит классы. Но не всегда в исходном пространстве признаков данные линейно разделимы, поэтому мы можем «поднять» данные в более высокое пространство признаков, где они, возможно, будут линейно разделимы, как показано на рисунке.
Итак, что же мы сделали? Мы взяли функцию ?(?):
После этого перевели данные в 3-мерное пространство, просто подставив значения. Как видим, данные там линейно разделимы. Мы берем пространство RD, используем трюк с подъемом в пространство RJ, где D < J, и затем применяем метод, вроде логистической регрессии, для линейной классификации. Однако это может быть дорогостоящим для функции φ(⋅). Для N точек данных, поднятых в J измерений, нам потребуется O(N × J) операций только для предварительной обработки данных. Но мы можем избежать вычисления φ(⋅) полностью, продолжая делать линейную классификацию в этом поднятом пространстве, если будем изобретательны. И этот второй трюк называется трюком с ядром.
Но, прежде чем перейти к трюку с ядром, я бы хотел поговорить о матрице Грама.
Матрица Грама
Определение с Википедии:
В линейной алгебре матрица Грама для набора векторов v1,…,vn в гильбертовом пространстве представляет собой эрмитову матрицу скалярных произведений, элементы которой заданы скалярными произведениями Gij = ⟨vi,vj⟩.
Нас она интересует, потому что если мы применим скалярное умножение (линейное ядро, внутренний продукт) попарно ко всем данным в нашем наборе, то получим матрицу Грама, которая отображает линейные зависимости между нашими данными, формируя наше исходное пространство признаков. Ибо наше ядро ?(??, ??) = ?(??) ⋅ ?(??), где φ(x) = x.
Вот наглядный пример:
Возьмем 4 вектора в 2-х мерном пространстве и попарно найдем сходства построив матрицу Грама.
Эта матрица не изменяет наше исходное пространство признаков: данные остаются в 2-мерном пространстве, несмотря на наличие 4 столбцов, поскольку каждый столбец является элементом, формирующим наше исходное пространство признаков.
Вернемся к нашей функции φ(⋅) и сделаем следующее: повысим наши предыдущие вектора в 3-мерное пространство, попарно вычислим их внутренний продукт и построим матрицу Грама.
Фактически формула каждого элемента матрицы будет выглядеть так:
Как вы догадались, выполнив каждый пункт, мы получим отображение наших данных в 3-мерном пространстве. Казалось бы, мало того что мы использовали трюк с подъемом, так мы еще и вычисляли скалярное произведение. Зачем? Поэтому мы переходим к трюку с ядром.
Трюк с Ядром
Мы вычисляем, как в нашем алгоритме, каждый элемент матрицы вот так:
Но теперь сделаем это с помощью полиномиального ядра:
Что сейчас произошло? Вместо того чтобы переносить наши данные в 3-мерное пространство и вычислять скалярное умножение, мы только что вычислили внутренний продукт в двумерном пространстве и затем возвели сумму в квадрат. Хотя оба варианта имеют одинаковое количество математических символов, фактическое количество операций для второго подхода намного меньше. Это происходит потому, что внутренний продукт в двумерном пространстве — это два умножения и сумма. Квадрат — это просто квадрат скаляра, поэтому всего 4 операции. Первый подход занимал 9 операций.
В этом и заключается трюк с ядром: мы можем избежать дорогостоящих операций перевода в большую размерность, найдя подходящую функцию ядра k(xn, xm), эквивалентную скалярному умножению в пространстве более высокого измерения. Это позволяет нам дешево построить матрицу Грама, заботясь только о её масштабировании. Полученная матрица Грама будет моделировать линейные зависимости, но уже в более высоком пространстве. Другими словами, трюк с ядром позволяет дешево выполнить трюк с подъемом.
Теорема Мерсера
Теорема Мерсера в работах о функциональном анализе дает условия для формирования ядерного трюка в машинном обучении.
Формальное определение:
Hidden text
Джеймс Мерсер доказал, что любая положительно определенная функция k( xn, xm) при xn,xm ∈ RD определяет скалярное произведение векторного пространства V. Таким образом, если у нас есть функция φ(⋅), такая что ⟨φ(xn),φ(xm)⟩V является допустимым скалярным произведением в V, мы знаем, что существует функция ядра, которая может выполнить трюк с подъемом дешево. В качестве альтернативы, если у нас есть положительно определенное ядро, мы можем реконструировать его неявную базисную функцию φ(⋅).
Пусть ? будет непустым множеством, иногда называемым индексным множеством. Симметричная функция ?: ? × ? → ? называется положительно полуопределённым ядром на ?, если:
То есть, если матрица Грама K, элементы которой определены как Kij=K(xi,xj), является положительно полуопределенной для всех наборов xi.
Это равнозначно тому, что собственные значения λi матрицы Грама K удовлетворяют условию:
Итак, ядро может выполнить трюк с ядром, если:
Ядро является непрерывной функцией.
Ядро является симметричным.
Собственные значения матрицы Грама, построенной с помощью ядра, неотрицательные.
Примеры положительно определенных ядер
Некоторые примеры положительно определенных ядер, определенных в евклидовом пространстве Rd, включают:
Линейное ядро:
Полиномиальное ядро:
Гауссовское ядро (RBF ядро):
Где σ и λ — это ширина ядра. В первом случае, чем меньше значение σ, тем меньше значение под экспонентой и тем более чувствительно ядро к изменениям. Во втором, наоборот, чем больше значение λ, тем более чувствительно.
Бесконечномерное пространство и Гауссово (RBF) ядро
Сейчас мы алгебраически поймём, в чём же «магия» гауссовского ядра относительно его способности возвращать скалярное умножение в бесконечномерном пространстве.
Исходное выражение для ядра RBF при λ = 1/2
Норма разности в виде скалярного произведения
Раскрытие скобок в скалярном произведении
Линейность и коммутативность скалярного произведения
выражение упрощается:
Подстановка в экспоненту
Разделение экспоненты
Определение ?
Представим первые два множителя как ?, так как в данном случае они нас не интересуют из-за того, что учитывают норму векторов, а не взаимосвязь между векторами x и y:
Обновлённое выражение для ядра RBF
Разложение экспоненты через ряд Тейлора
Применение ряда Тейлора к exp(⟨?,?⟩)
Полиномиальное ядро
Подстановка полиномиального ядра
Итоговое выражение для ядра RBF
Таким образом, RBF ядро можно рассматривать как бесконечную сумму полиномиальных ядер. Вот почему матрица Грама, построенная с их помощью, будет моделировать наши данные в бесконечномерном пространстве.
Обобщаем информацию
Итак, мы полностью разобрались с работой ядер, ядерного трюка и изменением пространства. Теперь перейдём к пониманию, о котором я говорил в начале статьи.
Пространство — это связующее звено между всеми алгоритмами в машинном обучении, позволяющее обобщить их понимание и обеспечить модульность.
В качестве первого примера рассмотрим классическую полносвязную нейронную сеть. Обычно её объясняют через связи, веса и прочее. Я предлагаю обобщить этот подход и сделать его более модульным — через пространство. В полносвязной нейронной сети (и не только) скрытый слой фактически выполняет трюк с подъемом данных в многомерное пространство. Мы подаем данные на вход, а затем рекурсивно поднимаем их от слоя к слою нашей сети (или понижаем размерность), где количество нейронов в каждом скрытом слое определяет размерность пространства. И фактически это и есть наша новая функция φ(⋅) для изменения пространства.
Для иллюстрации мы возьмем наш предыдущий датасет make_circles и обучим на нём полносвязную нейронную сеть без функций активации (2 входа, 3 нейрона в скрытом слое, 2 выхода) и отобразим данные после выхода из скрытого слоя.
Как мы можем заметить, без функций активации наша функция φ(⋅), которая представлена скрытым слоем, способна сделать трюк с подъемом, моделируя линейные зависимости между данными. Поэтому наш классификатор в виде выходного слоя нейросети не способен предсказать истинные метки.
Теперь рассмотрим случай с функциями активации (sigmoid). С ними наша нейронная сеть становится более сложной функцией φ(⋅), которая лучше обучается изменять пространство признаков так, чтобы в конце выходной слой мог правильно классифицировать векторы.
Вернёмся опять к нашей нейросети без функций активации. Так ли всё безнадежно, что нам нужно использовать функции активации? Нет! Никто нам не мешает добавить модульность и предварительно обработать данные, используя трюк с ядром. В данном случае мы будем использовать RBF ядро и представим наши данные в бесконечномерном пространстве, надеясь, что там нейросеть без функций активации сможет их классифицировать максимально точно.
Можно заявить: «Ок, с нейронной сетью и с многими архитектурами, использующими гиперплоскость и изменение пространства для выполнения задачи, всё понятно». Возьмём ещё одну популярную архитектуру — дерево решений. Само по себе оно никак не трансформирует пространство, что же с ним? Да, это верно, но при этом оно делит и структурирует его. Геометрически дерево решений разбивает пространство признаков на оси, перпендикулярные осям признаков.
Рассмотрим это на примере двухмерного пространства признаков с признаками ?1 и ?2:
Начальное состояние:
Пространство признаков представляет собой плоскость, где каждый точка соответствует определенным значениям ?1 и ?2.
Первое разбиение:
Дерево решений выбирает признак ?1 и пороговое значение ?1. Пространство разбивается на две части по линии ?1 = ?1:
Все точки, у которых ?1 ≤ ?1, находятся слева от линии.
Все точки, у которых ?1 > ?1, находятся справа от линии.
Геометрически это означает, что пространство делится вертикальной линией.
Второе разбиение:
Теперь каждая из двух частей пространства рассматривается отдельно. Предположим, что в левой части (?1 ≤ ?1) выбирается признак ?2 и пороговое значение ?2. Пространство теперь делится горизонтальной линией ?2 = ?2:
Все точки, у которых ?2 ≤ ?2, находятся ниже линии.
Все точки, у которых ?2 > ?2, находятся выше линии.
Геометрически это означает, что левая часть пространства теперь делится горизонтальной линией.
Вот наглядный геометрический пример работы дерева решений в двумерном пространстве признаков для классификации чая: вкусный или нет, на основе его температуры и сладости.
Вернёмся опять к нашему датасету с кругами и построим три дерева решений: первое будет работать с исходными данными, второе — с данными, предварительно преобразованными с помощью функции φ( x12, x22, sqrt(2)x1x2) а третье — с использованием предварительно ядра RBF. И посмотрим, как будет различаться структура дерева.
Как видим, даже несмотря на то, что алгоритм сам по себе не трансформирует пространство признаков и успешно справляется с нелинейной задачей в исходном, использование трюка с ядром или трюка с подъемом может упростить разделение данных для дерева решений и уменьшить структуру дерева.
Если мы рассматриваем задачи машинного обучения и анализа данных через призму пространственных преобразований, это позволяет нам не только уменьшить «переобучение» нашего мышления на отдельных методах, но и применять разнообразные подходы к решению задач, гибко адаптируя используемые методы и технологии.
Надеюсь, что я смог донести свою идею понимания работы с ядрами и пространствами. Это была первая часть, и здесь мы рассмотрели теорию. В скором времени я планирую выпустить вторую часть и показать различные алгоритмы, модели и архитектуры, использующие ядра, уже на практике, в том числе и из собственных разработок.
Дополнительные источники
Gregory Gundersen — Implicit Lifting and the Kernel Trick
Wikipedia — Positive-definite kernel
Wikipedia — Mercer's theorem