Positive definite of a kernel

15.12.2011, 11:35

Ibn Batuta

Positive definite of a kernel

Hallo,

ich verstehe folgenden Beweis nicht so ganz.

Theorem 1. Let $\begin{eqnarray*} X \end{eqnarray*}$ be a nonempty set and let $\begin{eqnarray*} K\colon X\times X \to \mathbb{R} \end{eqnarray*}$ be symmetric. Then $\begin{eqnarray*} K \end{eqnarray*}$ is conditionally positive definit if and only if $\begin{eqnarray*} \mathrm{e}^{uK} \end{eqnarray*}$ is positive for all $\begin{eqnarray*} u > 0 \end{eqnarray*}$ .

Proposition. If $\begin{eqnarray*} K\colon X\times X\to \mathbb{R} \end{eqnarray*}$ is conditionally positive definite and satisfies $\begin{eqnarray*} K(x,x) \le 0 \end{eqnarray*}$ for $\begin{eqnarray*} x\in X \end{eqnarray*}$ then it is $\begin{eqnarray*} -(-K)^{\beta} \end{eqnarray*}$ for $\begin{eqnarray*} 0 < \beta < 1 \end{eqnarray*}$ and of $\begin{eqnarray*} -\ln(1-K) \end{eqnarray*}$

___________

Proof. Considering a conditionally positive definite Kernel $\begin{eqnarray*} K \end{eqnarray*}$ such that $\begin{eqnarray*} K(x,y)\le 0 \end{eqnarray*}$ for any $\begin{eqnarray*} (x,y)\in X\times X \end{eqnarray*}$ , then it follows from Theorem 1 that $\begin{eqnarray*} \mathrm{e}^{uK} \end{eqnarray*}$ is positive definite and this conditionally positive definite. The constant kernel is obviously conditionally positive definite. Thus $\begin{eqnarray*} \mathrm{e}^{uK}-1 \end{eqnarray*}$ is conditionally positive definite as the sum of two conditionally positive definite kernels (warum?). For $\begin{eqnarray*} 0<\beta<1 \end{eqnarray*}$ and $\begin{eqnarray*} s<0 \end{eqnarray*}$ we can write:

(I)
$\begin{eqnarray*} -(-s)^{\beta} = \frac{\beta}{\Gamma(1-\beta)}\int_{0}^{+\infty} (\mathrm{e}^{uK}-1) \frac{du}{u^{\beta+1}} \end{eqnarray*}$

(II)
$\begin{eqnarray*} -\ln(1-s) = \int_{0}^{+\infty} (\mathrm{e}^{us}-1)\frac{\mathrm{e}^{-u}}{u}du \end{eqnarray*}$

Then, by replacing $\begin{eqnarray*} s \end{eqnarray*}$ with $\begin{eqnarray*} K \end{eqnarray*}$ , we can deduce that $\begin{eqnarray*} -(-K)^{\beta} \end{eqnarray*}$ and $\begin{eqnarray*} -\ln(1-K) \end{eqnarray*}$ are conditionally positive definite kernels as a sum of conditionally positive definite ones.

Fragen:

a) Oben schrieb ich einmal (warum?). Weiß jemand zufällig, warum das gilt?
b) Für mich fällt die Gamma-Funktion in (I) aus heiterem Himmel. Warum ist die linke Seite gleich der (komplizierten) rechten Seite?
c) Warum gilt (II)?

Ibn Batuta

15.12.2011, 12:15

ollie3

Auf diesen Beitrag antworten »

RE: Positive definite of a kernel
hallo ibn batuta,
habe mir das hier angeguckt.
Am einfachsten kann ich deine letzte frage beantworten (warum gilt II), das
ist einfach nur integralrechnung, wenn man e^u*s mit e^(-u) multipliziert,
kommt man schnell auf e^((-u)*(1-s)), und das u ist ja praktischerweise im
nenner vom integranden, und so kommt man schnell auf -ln(1-s).
Über die anderen fragen muss ich noch nachdenken.
gruss ollie3

15.12.2011, 12:29

Ibn Batuta

Auf diesen Beitrag antworten »

Hi ollie3,

vielen Dank für deine Antwort, das ging ja fix! Ich werde über deine Antwort nachdenken.

Das Paper, woher ich das habe, findet man übrigens hier: http://perso.lcpc.fr/tarel.jean-philippe.../jpt-icme05.pdf

Ibn Batuta

15.12.2011, 12:40

Ibn Batuta

Auf diesen Beitrag antworten »

Hey,

also ich verstehe das nicht, stelle ich fest und auch WolframAlpha zeigt mir für das Integral was anderes an:
http://www.wolframalpha.com/input/?i=%5C...-v%29%29%2Fv+dv

Wie komme ich überhaupt von $\begin{eqnarray*} -\ln(1-s) \end{eqnarray*}$ überhaupt auf ein solches Integral?

Ibn Batuta

15.12.2011, 13:38

ollie3

Auf diesen Beitrag antworten »

hallo ibn batuta,
also erstmal vielen dank für deine tolle quellenangabe mit der pdf-datei, jetzt
weiss ich auch, in welchem zusammenhang die ganzen sachen stehen.
Übrigens, bei deiner frage, warum wolframalfa was anderes angibt kann ich dir
sofort weiterhelfen, dir ist ein ganz einfaches missgeschick passiert, du hast
bei dem term im integral statt e^(u*s)-1 fälschlicherweise e^(u*s-1) eingegeben, und das hat zu dem falschen ergebnis geführt (denn wolframalfa
hat immer recht, hihi).
gruss ollie3

15.12.2011, 13:58

Ibn Batuta

Auf diesen Beitrag antworten »

Ja, das ganze ist in Zusammenhang mit Maschinellem Lernen, Mustererkennung und Prognosen zu sehen.

Mein dummer Fehler bei der Eingabe leuchtet mir ein. Allerdings zeigt WolframAlpha nun gleich gar nichts mehr an. Big Laugh

http://www.wolframalpha.com/input/?i=%5C...-v%29%29%2Fv+dv
"Computation timed out."

Wieso entspricht das Integral der rechten Seite gleich $\begin{eqnarray*} -\ln(1-s) \end{eqnarray*}$ ? Irgendwie verstehe ich das nicht. Stelle ich mich blöd an oder ist das wirklich nicht so trivial? verwirrt

Hat jemand noch zu den anderen beiden Fragen auch Ideen?

Ibn Batuta

15.12.2011, 15:02

Ibn Batuta

Auf diesen Beitrag antworten »

Vielleicht sollte ich mal die Definitionen noch nachlegen, eventuell wird es dann klarer. smile

Definition 1. Let $\begin{eqnarray*} X \end{eqnarray*}$ be a nonempty set. A function $\begin{eqnarray*} K\colon X\times X\to \mathbb{R} \end{eqnarray*}$ is called a positive definite kernel if and only if $\begin{eqnarray*} K \end{eqnarray*}$ is symmetric $\begin{eqnarray*} \forall x,x'\in X \end{eqnarray*}$ and $\begin{eqnarray*} \sum_{j,k=1}^n c_j,c_k K(x_j,x_k)\ge 0~\forall n\ge 1, c_1,...,c_n\in\mathbb{R} \end{eqnarray*}$ and $\begin{eqnarray*} x_1,...x_n\in X \end{eqnarray*}$ .

Definition 2. Let $\begin{eqnarray*} X \end{eqnarray*}$ be a nonempty set. A kernel $\begin{eqnarray*} K \end{eqnarray*}$ is called conditionally positive definite if and only if $\begin{eqnarray*} K \end{eqnarray*}$ is symmetric and $\begin{eqnarray*} \sum_{j,k=1}^n c_j,c_k K(x_j,x_k)\ge 0 \end{eqnarray*}$ for $\begin{eqnarray*} n\ge 1, c_1,...,c_n\in\mathbb{R} \end{eqnarray*}$ with $\begin{eqnarray*} \sum_{j=1}^n c_j=0 \end{eqnarray*}$ and $\begin{eqnarray*} x_1,...x_n\in X \end{eqnarray*}$ .

Ibn Batuta

15.12.2011, 15:19

Ibn Batuta

Auf diesen Beitrag antworten »

Ich möchte mir ein Beispiel konstruieren und stoße auf immer neuere Fragen. Big Laugh

Kann doch nicht sein, oder?

Nehmen wir folgende Abbildung:

Sei $\begin{eqnarray*} K\colon X\times X\to \mathbb{R}, (x,y)\to ||x-y||^2 \end{eqnarray*}$ .

Dann ist $\begin{eqnarray*} ||x-y||^2 = \left(\sqrt{\left< x-y , x-y \right>}\right)^2 = \left< x-y,x-y \right> = x^2+y^2-2xy = x^2+y^2-2\left<x,y\right> \end{eqnarray*}$ .

Das ist klar symmetrisch.

Zur zweiten Bedingung der Definition 2. Und wie überprüfe ich nun Bedingung 2? verwirrt

Ibn Batuta

15.12.2011, 15:42

ollie3

Auf diesen Beitrag antworten »

hallo ibn batuta,
habe auch weiter über diese sache nachgedacht, also ich stelle mir unter diesem
"kernel", also unter K(x,y) sozusagen eine verallgemeinerte metrik, also eine
art abstandsfunktion vor, die sozusagen durch die koeffizienten c_j und c_k
"gewichtet" ist. Im einen fall sind die koeffizienten frei wählbar, im anderen
fall muss die summe der koeffizienten den wert 0 ergeben, was natürlich eine
einschränkung bedeutet.
Hoffe dir ist die sache jetzt etwas klarer. smile

gruss ollie3

15.12.2011, 16:23

gonnabphd

Auf diesen Beitrag antworten »

Hiho,

Zitat:

(I)
$\begin{eqnarray*} -(-s)^{\beta} = \frac{\beta}{\Gamma(1-\beta)}\int_{0}^{+\infty} (\mathrm{e}^{uK}-1) \frac{du}{u^{\beta+1}} \end{eqnarray*}$

Durch Substitution von $\begin{eqnarray*} x = -su \end{eqnarray*}$ und anschliessender einmaliger partiellen Integration kommst du auf

$\begin{eqnarray*} \int_{0}^{+\infty} (\mathrm{e}^{uK}-1) \frac{du}{u^{\beta+1}} = \frac{-(-s)^\beta}{\beta}\Gamma(1-\beta) \end{eqnarray*}$

Benutze dabei $\begin{eqnarray*} \Gamma(x) = \int_0^\infty t^{x -1} e^{-t}\, dt \end{eqnarray*}$ .

Zitat:

(II)
$\begin{eqnarray*} -\ln(1-s) = \int_{0}^{+\infty} (\mathrm{e}^{us}-1)\frac{\mathrm{e}^{-u}}{u}du \end{eqnarray*}$

Durch einmaliges partielles Inegrieren kommst du auf

$\begin{eqnarray*} \int_0^\infty (e^{us} - 1)e^{-u} \frac{\mathrm d u}u = \int_0^\infty (1-s)e^{-(1-s)u}\log u - e^{-u}\log u \, du \end{eqnarray*}$

Beide Summanden konvergieren hier einzeln. Wenn du beim ersten $\begin{eqnarray*} x = (1-s)u \end{eqnarray*}$ substituierst kommst du darauf, dass

$\begin{eqnarray*} \int_0^\infty (e^{us} - 1)e^{-u} \frac{\mathrm d u}u = -\log(1-s) \end{eqnarray*}$

Wie man auf solche Formeln kommt ist mir auch nicht so klar. Ich vermute jedoch, dass solche Formeln in Verbindung mit der Funktionentheorie mehr oder weniger natürlich auftreten.

[Addendum]

Ein Beispiel für einen positiv definiten Kern wäre übrigens beispielsweise gegeben durch $\begin{eqnarray*} X = \mathbb N \end{eqnarray*}$ und $\begin{eqnarray*} K(i,j) = \delta_{ij} \end{eqnarray*}$ .

Ein Beipsiel für einen conditionally positive kernel fällt mir im Moment nicht ein.

[weiterer Nachtrag]

@ollie:

Zitat:

habe auch weiter über diese sache nachgedacht, also ich stelle mir unter diesem "kernel", also unter K(x,y) sozusagen eine verallgemeinerte metrik, also eine art abstandsfunktion vor

Diese Vorstellung ist falsch. Es ist sogar vielmehr so, dass keine einzige nichttriviale Metrik ein positive definite kernel ist (falls ich die Definitionen richtig verstehe)! Betrachte $\begin{eqnarray*} c_1 = 1, c_2 = -1 \end{eqnarray*}$ , $\begin{eqnarray*} x_1 \ne x_2 \end{eqnarray*}$ . Dann ist

$\begin{eqnarray*} \sum_{i,j=1}^2 c_ic_j d(x_i,x_j) = c_1c_2 d(x_1, x_2) + c_2 c_1 d(x_2, x_1) = -2d(x_1, x_2) < 0 \end{eqnarray*}$

15.12.2011, 19:33

Ibn Batuta

Auf diesen Beitrag antworten »

Ah perfekt, gonnabphd rettet die Aufgabe und mir den Tag. Freude

Dankeschön!

Werde in Zukunft öfter fragen haben, was Richtung Funktionentheorie geht. :-/

Ibn Batuta

Neue Frage »

Antworten »

Positive definite of a kernel

Verwandte Themen