Какая функция может быть ядром?

В контексте машинного обучения и распознавания образов существует концепция Kernel Trick . Перед лицом проблем, когда меня просят определить, может ли функция быть функцией ядра или нет, что именно нужно сделать? Должен ли я сначала проверить, имеют ли они форму трех или четырех функций ядра, таких как полином, RBF и гауссов? Тогда что я должен делать? Должен ли я показать, что это положительно определенно? Может ли кто-нибудь решить пример, чтобы показать пошаговое решение таких проблем? Как, например, является функция ядра$f(x)=e^{x^tx'}$ (предположим , что мы не знаем , что это Gaussian ядро)?

Обычно функция является допустимой функцией ядра (в смысле трюка ядра), если она удовлетворяет двум ключевым свойствам:$k(x,y)$

• симметрия: $k(x,y) = k(y,x)$

• положительная полуопределенность.

Ссылка: страница 4 из http://www.cs.berkeley.edu/~jordan/courses/281B-spring04/lectures/lec3.pdf

Проверка симметрии обычно не вызывает затруднений при осмотре. Проверка положительной полуопределенности аналитически может иногда быть довольно волосатой. Я могу придумать две стратегии для проверки этого факта:

• (1) Проверка представления «внутреннего продукта»

Рассмотрим . Можем ли мы найти некоторые такие, что ? Небольшая математика показывает, что , поэтому пусть и все готово. ϕ ( a ) k ( x , y ) = ϕ ( x ) T ϕ ( y ) e x + y = e x e y ϕ ( a ) = e $k(x,y) = e^{x+y}$$\phi(a)$$k(x,y) = \phi(x)^T \phi(y)$$e^{x+y} = e^x e^y$$\phi(a)=e^a$

Если вам повезет, ваш будет поддаётся этому анализу. Если нет, вы можете прибегнуть к варианту (2):$k()$

• (2) Проверка положительной определенности путем случайного моделирования.

Рассмотрим функцию на дим-векторах , где каждый вектор должен быть неотрицательным и иметь сумму, равную единице. Это действительное ядро?$D$$k(\vec{x},\vec{y}) = \sum_{d=1}^D \min( x_d, y_d)$$\vec{x}, \vec{y}$

Мы можем проверить это с помощью симуляции. Нарисуйте набор из случайных векторов и постройте матрицу Грама где . Затем проверьте, является ли положительным (полу) определенным.$N$$\{\vec{x}_i\}_{i=1}^N$$K$$K_{ij} = k( \vec{x}_i , \vec{x}_j )$$K$

Лучший способ сделать это численно - найти собственные значения матрицы (используя хорошие существующие числовые библиотеки, такие как scipy или matlab) и убедиться, что наименьшее собственное значение больше или равно 0 . Если да, то матрица - это psd. В противном случае у вас нет действующего ядра.$K$

Пример кода MATLAB / Octave:

D=5;
N=100;

X = zeros(N,D);
for n = 1:N
   xcur = rand(1,D);
   X(n,:) = xcur/sum(xcur);
end

K = zeros(N,N);
for n = 1:N;  for m = 1:N
    K(n,m) = sum( min( X(n,:), X(m,:) ) );
end;  end;

disp( min( eig(K) ) );

Это очень простой тест, но будьте осторожны . Если тест не пройден, то вы можете быть уверены , что ядро не действует, но если она проходит ядро еще не может быть действительным.

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

Однако один и тот же тест для не удался при каждой попытке, которую я дал (не менее 20) , Так что это, безусловно, неверно, и довольно легко проверить.$k(\vec{x},\vec{y}) = \sum_{d=1}^D max( x_d, y_d)$

Мне очень нравится этот второй вариант, потому что он довольно быстрый и намного легче отлаживается, чем собранные формальные доказательства. Согласно слайду 19 Джитендры Малик , ядро ​​пересечения было введено в 1991 году, но до 2005 года не было проверено. Формальные доказательства могут быть очень сложными!