Bagaimana cara membuktikan bahwa fungsi basis radial adalah sebuah kernel?

Bagaimana untuk membuktikan bahwa fungsi dasar radial $k(x, y) = \exp(-\frac{||x-y||^2)}{2\sigma^2})$adalah sebuah kernel? Sejauh yang saya mengerti, untuk membuktikan ini kita harus membuktikan salah satu dari yang berikut:

1. Untuk setiap set vektor $x_1, x_2, ..., x_n$ matriks $K(x_1, x_2, ..., x_n)$ = $(k(x_i, x_j))_{n \times n}$ adalah semidefinite positif.

2. Sebuah pemetaan $\Phi$ dapat disajikan seperti $k(x, y)$ = $\langle\Phi(x), \Phi(y)\rangle$ .

Ada bantuan?

Metode Zen yang digunakan 1. Berikut adalah metode 2: Peta $x$ ke distribusi Gaussian simetris bola yang berpusat di $x$ di ruang Hilbert $L^2$ . Deviasi standar dan faktor konstan harus diubah agar ini berfungsi dengan tepat. Misalnya, dalam satu dimensi,

$$\int_{-\infty}^\infty \frac{\exp[-(x-z)^2/(2\sigma^2)]}{\sqrt{2 \pi} \sigma} \frac{\exp[-(y-z)^2/(2 \sigma^2)}{\sqrt{2 \pi} \sigma} dz = \frac{\exp [-(x-y)^2/(4 \sigma^2)]}{2 \sqrt \pi \sigma}.$$

Jadi, gunakan deviasi standar dan skala distribusi Gaussian untuk mendapatkank(x,y)=⟨Φ(x),Φ(y)⟩. Rescaling terakhir ini terjadi karenaL2norma dari distribusi normal tidak1pada umumnya.$\sigma/\sqrt 2$$k(x,y) = \langle \Phi(x), \Phi(y)\rangle$$L^2$$1$

Saya akan menggunakan metode 1. Periksa jawaban Douglas Zare untuk bukti menggunakan metode 2.

Saya akan membuktikan kasus ketika adalah bilangan real, sehingga k ( x , y ) = exp ( - ( x - y ) 2 / 2 σ 2 ) . Kasus umum mengikuti mutatis mutandis dari argumen yang sama, dan layak dilakukan.$x,y$$k(x,y)=\exp(-(x-y)^2/2\sigma^2)$

Tanpa kehilangan sifat umum, anggaplah bahwa .$\sigma^2=1$

Tulis , di mana h ( t ) = exp ( - t $k(x,y)=h(x-y)$adalah fungsi karakteristik dari variabel acakZdengandistribusiN(0,1).

$$h(t)=\exp\left(-\frac{t^2}{2}\right)=\mathrm{E}\left[e^{itZ}\right]$$ $Z$$N(0,1)$

$x_1,\dots,x_n$$a_1,\dots,a_n$

$$\sum_{j,k=1}^n a_j\,a_k\,h(x_j-x_k) = \sum_{j,k=1}^n a_j\,a_k\,\mathrm{E} \left[ e^{i(x_j-x_k)Z}\right] = \mathrm{E} \left[ \sum_{j,k=1}^n a_j\,e^{i x_j Z}\,a_k\,e^{-i x_k Z}\right] = \mathrm{E}\left[ \left| \sum_{j=1}^n a_j\,e^{i x_j Z}\right|^2\right] \geq 0 \, ,$$ $k$

Untuk memahami hasil ini secara umum, lihat Teorema Bochner: http://en.wikipedia.org/wiki/Positive-definite_function

$\mathcal X$$\varphi$

• $\kappa$$\gamma \kappa$$\gamma > 0$

  $\varphi$$\kappa$$\sqrt\gamma \varphi$$\gamma \kappa$

• $\kappa_1$$\kappa_2$$\kappa_1 + \kappa_2$

  $\varphi_1$$\varphi_2$$x \mapsto \begin{bmatrix}\varphi_1(x) \\ \varphi_2(x)\end{bmatrix}$

• $\kappa_1, \kappa_2, \dots$$\kappa(x, y) := \lim_{n \to \infty} \kappa_n(x, y)$$x, y$$\kappa$

  Bukti: Untuk setiap dan setiap kita memilikinya . Mengambil batas sebagai memberikan properti yang sama untuk .$m, n \ge 1$$\{ (x_i, c_i) \}_{i=1}^m \subseteq \mathcal{X} \times \mathbb R$$\sum_{i=1}^m c_i \kappa_n(x_i, x_j) c_j \ge 0$$n \to \infty$$\kappa$

• Produk: Jika dan adalah kernel pd, demikian juga .$\kappa_1$$\kappa_2$$g(x, y) = \kappa_1(x, y) \, \kappa_2(x, y)$

  Bukti: Ini mengikuti langsung dari teorema produk Schur , tetapi Schölkopf dan Smola (2002) memberikan bukti dasar yang bagus berikut ini. Biarkan independen. Dengan demikian Matriks kovarian harus psd, jadi pertimbangkan matriks kovarian dari membuktikannya.

  $$(V_1, \dots, V_m) \sim \mathcal{N}\left( 0, \left[ \kappa_1(x_i, x_j) \right]_{ij} \right) \\ (W_1, \dots, W_m) \sim \mathcal{N}\left( 0, \left[ \kappa_2(x_i, x_j) \right]_{ij} \right)$$ $$\mathrm{Cov}(V_i W_i, V_j W_j) = \mathrm{Cov}(V_i, V_j) \,\mathrm{Cov}(W_i, W_j) = \kappa_1(x_i, x_j) \kappa_2(x_i, x_j).$$ $(V_1 W_1, \dots, V_n W_n)$

• Powers: Jika adalah kernel pd, demikian juga untuk bilangan bulat positif .$\kappa$$\kappa^n(x, y) := \kappa(x, y)^n$$n$

  Bukti: langsung dari properti "produk".

• Eksponen: Jika adalah kernel pd, maka adalah .$\kappa$$e^\kappa(x, y) := \exp(\kappa(x, y))$

  Bukti: Kami memiliki ; gunakan properti "kekuatan", "skala", "jumlah", dan "batas".$e^\kappa(x, y) = \lim_{N \to \infty} \sum_{n=0}^N \frac{1}{n!} \kappa(x, y)^n$

• Fungsi: Jika adalah kernel pd dan , juga.$\kappa$$f : \mathcal X \to \mathbb R$$g(x, y) := f(x) \kappa(x, y) f(y)$

  Bukti: Gunakan peta fitur .$x \mapsto f(x) \varphi(x)$

Sekarang, perhatikan bahwa Mulai dengan kernel linear , terapkan "skala" dengan , terapkan "eksponen", dan terapkan "fungsi" dengan .

$$\begin{align*} k(x, y) &= \exp\left( - \tfrac{1}{2 \sigma^2} \lVert x - y \rVert^2 \right) \\&= \exp\left( - \tfrac{1}{2 \sigma^2} \lVert x \rVert^2 \right) \exp\left( \tfrac{1}{\sigma^2} x^T y \right) \exp\left( - \tfrac{1}{2 \sigma^2} \lVert y \rVert^2 \right) .\end{align*}$$ $\kappa(x, y) = x^T y$$\frac{1}{\sigma^2}$$x \mapsto \exp\left( - \tfrac{1}{2 \sigma^2} \lVert x \rVert^2 \right)$