Практическое исследование «уловки с ядром»

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

Но реальная жизнь никогда не будет такой простой, не так ли?

Начнем с пары контекстов. Я использовал сумму квадратов для моего предыдущего примера, что является хорошим и жизнеспособным примером расширения функций, но не тем, который действительно часто используется. Гораздо чаще берут продукт двух функций и рассматривают его как взаимодействие — отчасти потому, что такие технологии, как TPU и GPU, могут выполнять матричное умножение очень быстро в масштабе. Кроме того, мы на самом деле не знаем, какие комбинации признаков дадут нам наибольший сигнал с точки зрения классификации и разделимости, и вместо того, чтобы пытаться угадать, с алгоритмической точки зрения вы просто захотите попробовать каждую возможную комбинацию. И, наконец, вы добавляете к каждому вектору еще одно измерение, нейтральное в вычислительном отношении (то есть для целей умножения — 1). Мы бы указали, что эта операция была выполнена с нашим вектором, используя символ/термин фи ‹идентификатора вектора›.

Подразумевается, что наш двумерный вектор (назовем его A) будет преобразован из этого:

A = (x, y)

…к этому:

фи_А = (1, х, у, х*у)

Таким образом, двумерный вектор превращается в четырехмерный вектор. Что произойдет, если мы добавим третье измерение?

A = (x, y, z)

phi_A = (1, х, у, г, х * у, х * г, у * г, х * у * г)

От трех до восьми измерений. Еще один — четырехмерный вектор преобразуется так:

A = (x, y, z, q)

phi_A =
(1, x, y, z, q, x*y, x*z, x*q, y*z, y*q, z*q, x*y*z, x*y *д, х*г*д, у*г*д, х*у*г*д)

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

Это становится действительно сложным, когда вы пытаетесь создать классификатор, и особенно классификатор максимальной маржи. В рамках этого процесса вам необходимо математически определить расстояние между двумя векторами (и повторить для каждой возможной комбинации векторов), что может быть выполнено с использованием внутренних продуктов умножения матриц. Давайте начнем с малого и создадим фи-эквиваленты пары двумерных векторов, чтобы проиллюстрировать сложность здесь (изменив обозначение признаков для ясности):

фи_А = (1, а1, а2, а1а2)

фи_В = (1, b1, b2, b1b2)

Чтобы вычислить внутренний продукт этих двух векторов, математика выглядит так:

Расстояние_AB = 1+a1b1+a2b2+a1a2b1b2

Не так уж и плохо, правда? Давайте поднимемся на уровень выше и предположим, что у нас есть три функции:

фи_А = (1, а1, а2, а3, а1а2, а1а3, а2а3, а1а2а3)

phi_B = (1, b1, b2, b3, b1b2, b1b3, b2b3, b1b2b3)

И теперь наша формула выглядит так:

Distance_AB = 1+a1b1+a2b2+a3b3+a1a2b1b2+a1a3b1b3+a2a3b2b3+a1a2a3b1b2b3

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

Введите нашего старого друга, проклятие размерности.

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

Вам понадобится компьютер побольше.

Уловка ядра в помощь

Тогда возникает вопрос: «Есть ли другой способ вычислить относительные расстояния между векторами, не выполняя все ручные сложения?» А оказывается способ есть. На самом деле их очень много.

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

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

1+a1b1+a2b2+a1a2b1b2

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

(1+a1b1)(1+a2b2)

Этот «трюк» называется полиномиальным ядром. Назовем количество параметров «d». Полиномиальное ядро ​​сокращает количество необходимых вычислений от 2, возведенных в степень d задач на сложение, до просто d задач умножения. Наше трехмерное векторное расстояние:

1+a1b1+a2b2+a3b3+a1a2b1b2+a1a3b1b3+a2a3b2b3+a1a2a3b1b2b3

…упрощается до:

(1+a1b1)(1+a2b2)(1+a3b3)

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

В дополнение к полиномиальному ядру другим популярным подходом является радиальная базисная функция или ядро ​​RBF. Эта формула не является прямой корреляцией с внутренним продуктом, как полиномиальное ядро, но использует более сложный статистический подход, который дает аналогичную информацию. В зависимости от характера ваших данных (и особенно в более высоких измерениях) он может давать даже лучшие/более быстрые результаты, чем полиномиальное ядро. Вы также можете создать свое собственное ядро, если оно следует определенному набору правил (которые математически идут дальше, чем то, что я обычно иду в своих работах… дайте мне знать, если вам не терпится покопаться в этом).

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