Funktioniert der Satz von Mercer umgekehrt?

Ein Kollege hat eine Funktion $s$ und für unsere Zwecke ist es eine Blackbox. Die Funktion misst die Ähnlichkeit zweier Objekte. $s(a,b)$

Wir wissen sicher, dass diese Eigenschaften hat: $s$

Die Ähnlichkeitswerte sind reelle Zahlen zwischen 0 und einschließlich 1.
Nur die Objekte, die selbstidentisch sind, haben Punktzahlen von 1. Also impliziert und umgekehrt. $s(a,b)=1$ $a=b$
Wir sind garantiert, dass . $s(a,b) = s(b,a)$

Jetzt möchte er mit Algorithmen arbeiten, die Entfernungen als Eingaben erfordern und von den Eingaben abhängen, die die Axiome der Entfernung erfüllen.

Mein Gedanke war, dass wir die Ähnlichkeitsbewertungen so behandeln könnten, als wären sie das Ergebnis des RBF-Kernels mit einer gewissen Entfernung (es könnte eine euklidische Norm oder eine andere Entfernung sein), dh wir können einfach mit Algebra neu ordnen und annehmen, dass sich die Ähnlichkeitsbewertungen beziehen der RBF-Kernel für ein Punktpaar in einem (unbekannten) Koordinatensystem.

\begin{aligned} s (x_{i}, x_{j}) & = \exp (- \frac{d (m_{i}, m_{j})^{2}}{r}) \\ \sqrt{- r \log s (x_{i}, x_{j})} & = d (m_{i}, m_{j}) \end{aligned}

$\begin{align} s(x_i,x_j) &= \exp\left(-\frac{d( m_i, m_j)^2}{r}\right) \\ \sqrt{-r \log s(x_i,x_j) } &= d(m_i,m_j) \\ \end{align}$

Wobei ein unbekannter Vektor ist und das interessierende Objekt ist und eine gewisse Entfernung ist. $m_\alpha \in \mathbb{R}^n$ $x_\alpha$ $d$

Die offensichtlichen Eigenschaften zeigen sich in Bezug auf die Abstandsaxiome. Die Ergebnisse dürfen nicht negativ sein, und die Abstände für identische Objekte sind nur 0. Es ist jedoch nicht offensichtlich, dass diese eher allgemeinen Umstände ausreichen, um zu implizieren, dass die Dreiecksungleichheit respektiert wird.

Auf der anderen Seite klingt das irgendwie verrückt.

Meine Frage lautet also: "Gibt es ein so dass für eine Entfernungsmetrik ist, wenn diese Eigenschaften für , und was ist das ?" $f$ $f(s(a,b))=d(a,b)$ $d$ $s$ $f$

Wenn diesen allgemeinen Umständen auf nicht existiert , gibt es einen zusätzlichen Satz von Anforderungen, für die existiert? $f$ $s$ $f$

kernel-trick distance similarities rbf-kernel Sycorax sagt Reinstate Monica
quelle

Beachten Sie, dass selbst wenn Sie die Menge der paarweisen Abstände

, die die Axiome der Entfernung erfüllen, nicht garantiert werden kann, dass es einen euklidischen Raum mit Punkten gibt, die diese Abstände realisieren. Eine solche Einbettung ist nicht immer möglich. Siehe z . B. math.stackexchange.com/questions/1000006 .

d (a, b)

$d(a,b)$

Amöbe sagt Reinstate Monica

Dies ist ein sehr interessanter Thread! Vielen Dank für das Teilen. Es war nicht meine Absicht, mich auf eine bestimmte Entfernung zu beschränken. (Da man sich in die entgegengesetzte Richtung bewegt, könnte man den RBF-Kernel mit einem nichteuklidischen Abstand verwenden.)

Sycorax sagt Reinstate Monica

Ihre Frage ist also nur, wie man

umwandelt

so dass

die Dreiecksungleichung erfüllt? Ob diese Distanzmatrix in einen euklidischen Raum eingebettet werden kann, spielt für Sie keine Rolle. Richtig? Meine Intuition ist, dass es für ein beliebiges

nicht möglich ist.

s (a, b)

$s(a,b)$

d (a, b) = f (s (a, b))

$d(a,b)=f(s(a,b))$

d

$d$

s

$s$

Amöbe sagt Reinstate Monica

Das ist richtig. Ich vermute, dass dies nicht möglich ist, zumindest nicht ohne zusätzliche Einschränkungen für

s

$s$

Sycorax sagt Reinstate Monica

führt immer zur diskreten Metrik (en.wikipedia.org/wiki/Discrete_space), aber dies ist wahrscheinlich nicht beabsichtigt, daher sollten einige Bedingungen hinzugefügt werden (?)

f : f (x) = I_{x > 0}

$f: f(x) = I_{x>0}$

Juho Kokkala

Antworten:

Funktioniert der Satz von Mercer umgekehrt?

Nicht in allen Fällen.

Wikipedia: "In der Mathematik, insbesondere in der Funktionsanalyse, ist der Satz von Mercer eine Darstellung einer symmetrischen positiv-definitiven Funktion auf einem Quadrat als Summe einer konvergenten Folge von Produktfunktionen. Dieser in (Mercer 1909) vorgestellte Satz ist einer der folgenden Die bemerkenswertesten Ergebnisse der Arbeit von James Mercer: Es ist ein wichtiges theoretisches Werkzeug in der Theorie der Integralgleichungen, es wird in der Hilbert-Raumtheorie stochastischer Prozesse verwendet, zum Beispiel im Karhunen-Loève-Theorem, und es wird auch zur Charakterisierung verwendet ein symmetrischer positiver semi-definierter Kernel.

Es ist ein " Viele-zu-Eins-Mapping " auf einem Hilbert-Raum . - Eine grobe Vereinfachung wäre, es als Hash oder Prüfsumme zu beschreiben, die Sie anhand einer Datei testen können, um die Identität festzustellen oder nicht.

Technischere Erklärung: Zerfallsatz

"In der Mathematik ist der Desintegrationssatz ein Ergebnis der Maßtheorie und der Wahrscheinlichkeitstheorie. Er definiert die Idee einer nicht trivialen" Beschränkung "eines Maßes auf eine Teilmenge des fraglichen Maßraums von Maß Null rigoros Existenz von bedingten Wahrscheinlichkeitsmaßen. In gewissem Sinne ist "Zerfall" der entgegengesetzte Prozess zur Konstruktion eines Produktmaßes. "

Siehe auch: " Das Fubini-Tonelli-Theorem ", " Scharnierverlust ", " Verlustfunktion " und " Wie gut ist ein Kernel, wenn er als Ähnlichkeitsmaß verwendet wird? " (Juni 2007) von Nathan Srebro, die Zusammenfassung:

" Abstract. Kürzlich schlugen Balcan und Blum eine Theorie des Lernens vor, die auf allgemeinen Ähnlichkeitsfunktionen basiert, anstatt auf positiven semidefiniten Kerneln. Wir untersuchen die Lücke zwischen den Lerngarantien, die auf kernelbasiertem Lernen basieren, und denen, die durch Verwendung erhalten werden können Der Kernel als Ähnlichkeitsfunktion, der von Balcan und Blum offen gelassen wurde. Wir liefern eine deutlich verbesserte Grenze dafür, wie gut eine Kernelfunktion ist, wenn sie als Ähnlichkeitsfunktion verwendet wird, und erweitern das Ergebnis auch auf den praktisch relevanteren Scharnierverlust dann Null-Eins-Fehlerrate. Darüber hinaus zeigen wir, dass diese Grenze eng ist, und stellen daher fest, dass tatsächlich eine echte Lücke zwischen dem traditionellen kernelbasierten Begriff der Marge und dem neueren Ähnlichkeitsbegriff besteht. "

Ein Kollege hat eine Funktion und für unsere Zwecke ist es eine Blackbox. $s$

Siehe: Kernel und Ähnlichkeit (in R)

Da es sich um eine Black Box handelt, wissen Sie nicht genau, welcher Kernel verwendet wird, wenn er kernelbasiert ist, und Sie kennen die Details der Implementierung des Kernels nicht, wenn Sie glauben, zu wissen, um welchen es sich handelt. Siehe: Die Gleichung von rbfKernel in Kernlab unterscheidet sich vom Standard? .

Auf der anderen Seite klingt das irgendwie verrückt.

Es ist schnell und effektiv, unter bestimmten Umständen. Wie ein Hammer, wenn Sie einen Hammer mit sich führen, werden die Leute Sie verrückt nennen?

" Kernel-Methoden verdanken ihren Namen der Verwendung von Kernelfunktionen, die es ihnen ermöglichen, in einem hochdimensionalen, impliziten Merkmalsraum zu arbeiten, ohne jemals die Koordinaten der Daten in diesem Raum zu berechnen, sondern indem sie einfach die inneren Produkte zwischen den Bildern berechnen alle Paare von Daten im Merkmalsraum. Dieser Vorgang oft rechnerisch günstiger ist als die explizite Berechnung der Koordinaten. Dieser Ansatz des „Kernel - Trick“. genannt Kernel - Funktionen für Sequenzdaten, Grafiken, Texte, Bilder eingeführt wurden, als sowie Vektoren. ".

Lektion: Sie bekommen (manchmal) das, wofür Sie bezahlen.

Meine Fragen lauten also: "Gibt es ein so dass für eine Entfernungsmetrik ist, wenn diese Eigenschaften für , und was ist das ?" $f$ $f(s(a,b))=d(a,b)$ $d$ $s$ $f$

Viele finden Sie unter den obigen Links, " Popular Kernel Functions ", RBF , und hier ist ein (teures) Beispiel: " Ein Likelihood Ratio Distance Measure für die Ähnlichkeit zwischen der Fourier-Transformation von Zeitreihen " (2005) von Janacek, Bagnall und Powell.

Wenn diesen allgemeinen Umständen auf nicht existiert , gibt es einen zusätzlichen Satz von Anforderungen, für die existiert? $f$ $s$ $f$

Verschiedene Räume und Methoden können den Vergleich (und die Auflösung) spezifischer Probleme verbessern. Es gibt viele Methoden allein für den Hilbert-Raum .

Ja, die Liste ist groß, siehe die obigen Links und (für ein Beispiel): Reproduzieren des Kernel-Hilbert-Space .

rauben
quelle

-1

Es ist jedoch nicht offensichtlich, dass diese eher allgemeinen Umstände ausreichen, um zu implizieren, dass die Dreiecksungleichheit respektiert wird.

In der Tat ist es nicht ausreichend. Arbeiten wir mit . Wenn es drei Punkte mit $d(a, b) = 1 - s(a, b)$ $x, y, z$ , $d(x, y) = \frac{1}{3}$ und, dann versagt die Dreiecksungleichung, weil. $d(y, z) = \frac{1}{3}$ $d(x, z) = 1$ $d(x, z) > d(x, y) + d(y, z)$

Kodiologe
quelle

Ich sehe nicht, wie das etwas beweist.

Amöbe sagt Reinstate Monica

@amoeba Sie sehen nicht, wie es beweist, dass

die Dreiecksungleichung nicht erfüllen muss?

d

$d$

Kodiologe

Ich denke, dies zeigt, dass die Wahl von

nicht funktioniert, aber ich bin mir nicht sicher, warum dies zeigt, dass die Dreiecksungleichung bei einer alternativen Funktionswahl wie der (seltsamen) I nicht berücksichtigt wird Umriss in meinem Beitrag.

f (α) = 1 - α

$f(\alpha)=1-\alpha$

Sycorax sagt Reinstate Monica

Die Frage ist, ob die aufgelisteten Eigenschaften von

für die Existenz eines

ausreichen, so dass

eine Metrik ist, und insbesondere, ob ein solches

mit dem RBF-Kernel mit einer gewissen Abbildung

. Diese Antwort scheint zu fragen, ob die aufgelisteten Eigenschaften von

ausreichen, um

eine Metrik mit einem beliebigen

s

$s$

f

$f$

d

$d$

f

$f$

m

$m$

s

$s$

d

$d$

f

$f$

Juho Kokkala

@Kodiologist, aber soweit ich weiß, enthält bereits die allererste Version im Bearbeitungsverlauf den Teil über RBF mit einem unbekannten Mapping

, sodass ich die Relevanz der Arbeit mit

nicht sehe . Und Ihre vorherigen Kommentar in Bezug auf , wie ich die Frage lesen, wird man eigentlich nicht „wissen“ etwas darüber , wie die

s Karte zu

s - ein Gegenbeispiel soll zeigen , dass eine solche Zuordnung kann für die counterexample- konstruiert werden

m

$m$

1 - s (a, b)

$1-s(a,b)$

x_{α}

$x_\alpha$

m_{α}

$m_\alpha$

s

$s$

Juho Kokkala