Как доказать, что радиальная базисная функция является ядром?

35

Как доказать, что радиальная базисная функция k(x,y)=exp(||xy||2)2σ2)ядро? Насколько я понимаю, чтобы доказать это, мы должны доказать одно из следующего:

  1. Для любого набора векторов x1,x2,...,xn матрица K(x1,x2,...,xn) = (k(xi,xj))n×n неотрицательно.

  2. Отображение Φ может быть представлен , например , как k(x,y) = Φ(x),Φ(y) .

Любая помощь?

Лео
источник
1
Просто чтобы связать это более очевидно: карта характеристик также обсуждается в этом вопросе , в частности , ответ Марка Клезена, основанный на моих рядах Тейлора, который обсуждает как RKHS, так и общую версию вложения L2 приведенную Дугласом ниже.
Дугал

Ответы:

26

Дзен использовал метод 1. Вот метод 2: Отображение x в сферически симметричное гауссово распределение с центром в x в гильбертовом пространстве L2 . Стандартное отклонение и постоянный коэффициент должны быть настроены для точной работы. Например, в одном измерении

exp[(xz)2/(2σ2)]2πσexp[(yz)2/(2σ2)2πσdz=exp[(xy)2/(4σ2)]2πσ.

Итак, используйте стандартное отклонение и масштабировать гауссово распределениечтобы получитьK(х,у)=Ф(х),Ф(г). Это последнее изменение масштаба происходит потому, чтонормаL2нормального распределенияв общем случаене равна1.σ/2k(x,y)=Φ(x),Φ(y)L21

Дуглас Заре
источник
2
@Zen, Дуглас Заре: спасибо за ваши великолепные ответы. Как мне теперь выбрать официальный ответ?
Лев
23

Я буду использовать метод 1. Проверьте ответ Дугласа Заре для доказательства, используя метод 2.

Я докажу случай , когда являются вещественными числами, поэтому к ( х , у ) = ехр ( - ( х - у ) 2 / 2 σ 2 ) . Общий случай вытекает mutatis mutandis из того же аргумента и заслуживает рассмотрения.x,yk(x,y)=exp((xy)2/2σ2)

Без ограничения общности предположим, что .σ2=1

Запишите , где h ( t ) = exp ( - t 2k(x,y)=h(xy)- характеристическая функция случайной величиныZсраспределениемN(0,1).

h(t)=exp(t22)=E[eitZ]
ZN(0,1)

Для действительных чисел и a 1 , , a n имеем n j , k = 1x1,,xna1,,an что влечет за собой то, что k - положительная полуопределенная функция, то есть ядро.

j,k=1najakh(xjxk)=j,k=1najakE[ei(xjxk)Z]=E[j,k=1najeixjZakeixkZ]=E[|j=1najeixjZ|2]0,
k

Чтобы понять этот результат в большей общности, ознакомьтесь с теоремой Бохнера: http://en.wikipedia.org/wiki/Positive-definite_function

Zen
источник
2
Это хорошее начало в правильном направлении с двумя оговорками: (a) не равно ожидаемому показанию (проверьте знак в показателе степени) и (b) это, по-видимому, ограничивает внимание случаем, когда х и у скаляры, а не векторы. Тем временем я проголосовал, потому что выставка хорошая и чистая, и я уверен, что вы быстро закроете эти небольшие пробелы. :-)h(t)xy
кардинал
1
Tks! Я спешу сюда. :-)
Zen
1
Извините, я действительно не понимаю, как вы управляете mutatis mutandis здесь. Если вы разрабатываете норму до перехода в форму , значит, у вас есть продукты, и вы не можете менять продукты и суммировать. И я просто не вижу, как разработать норму после перехода в форму h, чтобы получить хорошее выражение. Можете ли вы привести меня немного там? :)h
Alburkerk
23

Я добавлю третий метод, просто для разнообразия: сборка ядра из последовательности общих шагов, известных для создания ядер pd. Обозначим через область нижних ядер и φ отображения признаков.Xφ

  • κγκγ>0

    φκγφγκ

  • κ1κ2κ1+κ2

    φ1φ2x[φ1(x)φ2(x)]

  • κ1,κ2, are pd kernels, and κ(x,y):=limnκn(x,y) exists for all x,y, then κ is pd.

    Proof: For each m,n1 and every {(xi,ci)}i=1mX×R we have that i=1mciκn(xi,xj)cj0. Taking the limit as n gives the same property for κ.

  • Products: If κ1 and κ2 are pd kernels, so is g(x,y)=κ1(x,y)κ2(x,y).

    Proof: It follows immediately from the Schur product theorem, but Schölkopf and Smola (2002) give the following nice, elementary proof. Let

    (V1,,Vm)N(0,[κ1(xi,xj)]ij)(W1,,Wm)N(0,[κ2(xi,xj)]ij)
    be independent. Thus
    Cov(ViWi,VjWj)=Cov(Vi,Vj)Cov(Wi,Wj)=κ1(xi,xj)κ2(xi,xj).
    Covariance matrices must be psd, so considering the covariance matrix of (V1W1,,VnWn) proves it.
  • Powers: If κ is a pd kernel, so is κn(x,y):=κ(x,y)n for any positive integer n.

    Proof: immediate from the "products" property.

  • Exponents: If κ is a pd kernel, so is eκ(x,y):=exp(κ(x,y)).

    Proof: We have eκ(x,y)=limNn=0N1n!κ(x,y)n; use the "powers", "scalings", "sums", and "limits" properties.

  • Functions: If κ is a pd kernel and f:XR, g(x,y):=f(x)κ(x,y)f(y) is as well.

    Proof: Use the feature map xf(x)φ(x).

Now, note that

k(x,y)=exp(12σ2xy2)=exp(12σ2x2)exp(1σ2xTy)exp(12σ2y2).
Start with the linear kernel κ(x,y)=xTy, apply "scalings" with 1σ2, apply "exponents", and apply "functions" with xexp(12σ2x2).
Dougal
источник