Le théorème de Mercer fonctionne-t-il à l'envers?

Un collègue a une fonction et pour nous c'est une boîte noire. La fonction mesure la similitude de deux objets. $s$ $s(a,b)$

Nous savons avec certitude que a ces propriétés: $s$

Les scores de similitude sont des nombres réels compris entre 0 et 1, inclus.
Seuls les objets qui sont auto-identiques ont des scores de 1. Donc implique , et vice-versa. $s(a,b)=1$ $a=b$
On nous garantit que . $s(a,b) = s(b,a)$

Maintenant, il veut travailler avec des algorithmes qui nécessitent des distances comme entrées et dépendent des entrées satisfaisant les axiomes de la distance.

Je pensais que nous pouvions traiter les scores de similitude comme s'ils étaient le résultat du noyau RBF avec une certaine distance (cela pourrait être une norme euclidienne ou une autre distance), c'est-à-dire que nous pouvons simplement réorganiser avec l'algèbre et supposer que les scores de similitude se réfèrent à le noyau RBF pour une paire de points dans un système de coordonnées (inconnu).

\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}$

Où est un vecteur inconnu, et est l'objet d'intérêt et est une certaine distance. $m_\alpha \in \mathbb{R}^n$ $x_\alpha$ $d$

Les propriétés évidentes fonctionnent, en termes de respect des axiomes de distance. Les résultats doivent être non négatifs et les distances ne sont que de 0 pour des objets identiques. Mais il n'est pas évident que cet ensemble de circonstances assez générales soit suffisant pour impliquer que l'inégalité du triangle est respectée.

D'un autre côté, cela semble un peu fou.

Donc ma question est "existe-t-il un tel que pour une certaine métrique de distance étant donné ces propriétés sur , et quel est ce ?" $f$ $f(s(a,b))=d(a,b)$ $d$ $s$ $f$

Si n'existe pas dans ces circonstances générales sur , existe-t-il un ensemble supplémentaire d'exigences pour lesquelles existe? $f$ $s$ $f$

kernel-trick distance similarities rbf-kernel Sycorax dit de réintégrer Monica
la source

Notez que même si l'on vous donne l'ensemble des distances par paires qui satisfont aux axiomes de distance, il n'est pas garanti qu'il existe un espace euclidien avec des points réalisant ces distances. Une telle intégration n'est pas toujours possible. Voir par exemple math.stackexchange.com/questions/1000006 .

d (a, b)

$d(a,b)$

amibe dit Réintégrer Monica

Ceci est un fil très intéressant! Merci de le partager. Ce n'était pas mon intention de me limiter à une distance particulière. (Depuis, en se déplaçant dans la direction opposée, on pourrait utiliser le noyau RBF avec une distance non euclidienne.)

Sycorax dit Reinstate Monica

Votre question est donc simplement de savoir comment convertir en telle sorte que satisfasse l'inégalité du triangle? Que cette matrice de distances soit embarquable dans un espace euclidien, peu importe pour vous. Correct? Mon intuition est que , pour un arbitraire qu'il ne sera pas possible.

s (a, b)

$s(a,b)$

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

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

d

$d$

s

$s$

amibe dit Réintégrer Monica

C'est correct. Je soupçonne que ce n'est pas possible, du moins pas sans restrictions supplémentaires à l' .

s

$s$

Sycorax dit Réintégrer Monica

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

$f: f(x) = I_{x>0}$ conduit toujours à la métrique discrète ( en.wikipedia.org/wiki/Discrete_space ), mais ce n'est probablement pas prévu donc certaines conditions doivent être ajoutées (?)

Juho Kokkala

Réponses:

Le théorème de Mercer fonctionne-t-il à l'envers?

Pas dans tous les cas.

Wikipedia: "En mathématiques, en particulier l'analyse fonctionnelle, le théorème de Mercer est une représentation d'une fonction symétrique définie positive sur un carré comme la somme d'une séquence convergente de fonctions de produit. Ce théorème, présenté dans (Mercer 1909), est l'un des résultats les plus notables des travaux de James Mercer. C'est un outil théorique important dans la théorie des équations intégrales; il est utilisé dans la théorie de l'espace de Hilbert des processus stochastiques, par exemple le théorème de Karhunen – Loève; et il est également utilisé pour caractériser un noyau semi-défini positif symétrique.

C'est une « cartographie plusieurs à un » sur un espace de Hilbert . - une simplification grossière excessive serait de le décrire comme un hachage ou une somme de contrôle que vous pouvez tester par rapport à un fichier pour déterminer l'identité ou non.

Explication plus technique: Théorème de désintégration

"En mathématiques, le théorème de désintégration est un résultat de la théorie des mesures et de la théorie des probabilités. Il définit rigoureusement l'idée d'une " restriction "non triviale d'une mesure à un sous-ensemble de mesure zéro de l'espace de mesure en question. Il est lié à la l'existence de mesures de probabilité conditionnelles. En un sens, la "désintégration" est le processus opposé à la construction d'une mesure de produit ".

Voir aussi: " Le théorème de Fubini – Tonelli ", " Hinge Loss ", " Loss Function " et " How Good Is a Kernel When Used as a Similarity Measure? " (Juin 2007) par Nathan Srebro, le résumé:

" Résumé. Récemment, Balcan et Blum ont suggéré une théorie de l'apprentissage basée sur des fonctions de similitude générales, au lieu de noyaux semi-définis positifs. Nous étudions l'écart entre les garanties d'apprentissage basées sur l'apprentissage basé sur le noyau, et celles qui peuvent être obtenues en utilisant le noyau en tant que fonction de similitude, qui a été laissée ouverte par Balcan et Blum. Nous fournissons une limite considérablement améliorée sur la qualité d'une fonction de noyau lorsqu'elle est utilisée comme fonction de similitude, et étendons également le résultat à la perte de charnière la plus pertinente. puis un taux d'erreur de zéro. De plus, nous montrons que cette limite est étroite, et établissons donc qu'il existe en fait un véritable écart entre la notion traditionnelle de marge basée sur le noyau et la nouvelle notion basée sur la similarité. ".

Un collègue a une fonction et pour nous c'est une boîte noire. $s$

Voir: noyaux et similitude (en R)

C'est une boîte noire, donc vous ne savez pas avec certitude quel noyau est utilisé, s'il est basé sur le noyau, et vous ne connaissez pas les détails de la mise en œuvre du noyau une fois que vous pensez que vous savez lequel il est. Voir: L' équation de rbfKernel dans kernlab est différente de la norme? .

D'un autre côté, cela semble un peu fou.

Il est rapide et efficace, dans un ensemble restreint de circonstances. Comme un marteau, si vous portez un marteau avec vous, les gens vous traiteront-ils de fou?

" Les méthodes du noyau doivent leur nom à l'utilisation des fonctions du noyau, qui leur permettent de fonctionner dans un espace caractéristique implicite de grande dimension sans jamais calculer les coordonnées des données dans cet espace, mais plutôt en calculant simplement les produits internes entre les images de toutes les paires de données dans l'espace d'entités. Cette opération est souvent moins coûteuse en termes de calcul que le calcul explicite des coordonnées. Cette approche est appelée "astuce du noyau". Les fonctions du noyau ont été introduites pour les données de séquence, les graphiques, le texte, les images, comme ainsi que des vecteurs. ".

Leçon: vous obtenez (parfois) ce que vous payez.

Donc, ma question est "Existe-t-il un tel que pour une métrique de distance étant donné ces propriétés sur , et quel est ce ?" $f$ $f(s(a,b))=d(a,b)$ $d$ $s$ $f$

Beaucoup, voir les liens ci-dessus, " Fonctions du noyau populaires ", RBF , et voici un exemple (coûteux): " Une mesure de distance du rapport de vraisemblance pour la similitude entre la transformation de Fourier des séries chronologiques " (2005), par Janacek, Bagnall et Powell.

Si n'existe pas dans ces circonstances générales sur , existe-t-il un ensemble supplémentaire d'exigences pour lesquelles existe? $f$ $s$ $f$

Différents espaces et méthodes peuvent mieux cibler la comparaison (et la désintégration) de problèmes spécifiques, il existe de nombreuses méthodes pour l'espace Hilbert seul.

Oui, la liste est grande, voir les liens ci-dessus et (pour un exemple): Reproduire l'espace Hilbert du noyau .

Rob
la source

-1

Mais il n'est pas évident que cet ensemble de circonstances assez générales soit suffisant pour impliquer que l'inégalité du triangle est respectée.

En fait, ce n'est pas suffisant. Travaillons avec . S'il y a trois points avec , et , alors l'inégalité du triangle échoue, car . $d(a, b) = 1 - s(a, b)$ $x, y, z$ $d(x, y) = \frac{1}{3}$ $d(y, z) = \frac{1}{3}$ $d(x, z) = 1$ $d(x, z) > d(x, y) + d(y, z)$

Kodiologue
la source

Je ne vois pas comment cela prouve quoi que ce soit.

amibe dit Réintégrer Monica

@amoeba Vous ne voyez pas comment cela prouve que n'a pas besoin de satisfaire l'inégalité triangulaire?

d

$d$

Kodiologue

Je pense que cela montre que choisir ne fonctionne pas, mais je ne sais pas pourquoi cela montre que l'inégalité du triangle n'est pas respectée pour un autre choix de fonction, comme le (bizarre) celui que je décris dans mon post.

f (α) = 1 - α

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

Sycorax dit Réintégrer Monica

La question est de savoir si les propriétés listées de sont suffisantes pour l'existence d'un tel que est une métrique, et surtout si un tel peut être représenté avec le noyau RBF avec un mappage . Cette réponse semble demander si les propriétés listées de sont suffisantes pour que soit une métrique avec un arbitraire .

s

$s$

f

$f$

d

$d$

f

$f$

m

$m$

s

$s$

d

$d$

f

$f$

Juho Kokkala

@Kodiologist mais pour autant que je comprends, même la toute première version de l'historique des modifications contient la partie sur RBF avec un mappage inconnu , donc je ne vois pas la pertinence de travailler avec . Et en ce qui concerne votre commentaire précédent, en lisant la question, on n'est pas censé "savoir" quoi que ce soit sur la façon dont la carte s vers s - un contre-exemple devrait montrer qu'aucune telle correspondance ne peut être construite pour le contre-exemple- .

m

$m$

1 - s (a, b)

$1-s(a,b)$

x_{α}

$x_\alpha$

m_{α}

$m_\alpha$

s

$s$

Juho Kokkala