¿El teorema de Mercer funciona a la inversa?

Un colega tiene una función para nuestros propósitos es una caja negra. La función mide la similitud de dos objetos. $s$ $s(a,b)$

Sabemos con certeza que tiene estas propiedades: $s$

Los puntajes de similitud son números reales entre 0 y 1, inclusive.
Sólo los objetos que son idénticos tienen puntuaciones de 1. Entonces implica , y viceversa. $s(a,b)=1$ $a=b$
Tenemos la garantía de que . $s(a,b) = s(b,a)$

Ahora quiere trabajar con algoritmos que requieren distancias como entradas, y dependen de las entradas que satisfacen los axiomas de la distancia.

Pensé que podríamos tratar los puntajes de similitud como si fueran el resultado del núcleo RBF con cierta distancia (podría ser una norma euclidiana u otra distancia), es decir, podemos reorganizar con álgebra y asumir que los puntajes de similitud se refieren a el núcleo RBF para un par de puntos en algún sistema de coordenadas (desconocido).

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

Donde es un vector desconocido, y es el objeto de interés es cierta distancia. $m_\alpha \in \mathbb{R}^n$ $x_\alpha$ $d$

Las propiedades obvias funcionan, en términos de respetar los axiomas de distancia. Los resultados tienen que ser no negativos, y las distancias son solo 0 para objetos idénticos. Pero no es obvio que este conjunto bastante general de circunstancias sea suficiente para implicar que se respeta la desigualdad del triángulo.

Por otro lado, esto suena un poco loco.

Entonces mi pregunta es "¿existe una tal que para alguna distancia métrica dadas estas propiedades en , y cuál es esa ?" $f$ $f(s(a,b))=d(a,b)$ $d$ $s$ $f$

Si no existe en estas circunstancias generales en , ¿existe un conjunto adicional de requisitos para los cuales existe ? $f$ $s$ $f$

kernel-trick distance similarities rbf-kernel Sycorax dice reinstalar a Mónica
fuente

Tenga en cuenta que incluso si se le da el conjunto de distancias por pares

que satisface los axiomas de la distancia, se no garantiza que hay un espacio euclidiano con puntos realizando estas distancias. Tal inserción no siempre es posible. Ver, por ejemplo, math.stackexchange.com/questions/1000006 .

d (a, b)

$d(a,b)$

ameba dice Reinstate Monica

Este es un hilo muy interesante! Gracias por compartirlo. No era mi intención limitarme a una distancia particular. (Dado que, moviéndose en la dirección opuesta, uno podría usar el núcleo RBF con una distancia no euclidiana).

Sycorax dice Reinstate Monica

s (a, b)

$s(a,b)$

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

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

d

$d$

s

$s$

s

$s$

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

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

Respuestas:

¿El teorema de Mercer funciona a la inversa?

No en todos los casos.

Wikipedia: "En matemáticas, específicamente en el análisis funcional, el teorema de Mercer es una representación de una función simétrica positiva definida en un cuadrado como la suma de una secuencia convergente de funciones de producto. Este teorema, presentado en (Mercer 1909), es uno de los resultados más notables del trabajo de James Mercer. Es una herramienta teórica importante en la teoría de ecuaciones integrales; se usa en la teoría espacial de Hilbert de procesos estocásticos, por ejemplo el teorema de Karhunen-Loève; y también se usa para caracterizar un núcleo simétrico positivo semi-definido.

Es un ' mapeo de muchos a uno ' en un espacio de Hilbert . - un bruto simplificación sería describirlo como un hash o suma de comprobación que se puede probar en contra de un archivo para determinar la identidad o no.

Explicación más técnica: teorema de desintegración

"En matemáticas, el teorema de la desintegración es el resultado de la teoría de la medida y la teoría de la probabilidad. Define rigurosamente la idea de una " restricción "no trivial de una medida a un subconjunto de medida cero del espacio de medida en cuestión. Está relacionado con el existencia de medidas de probabilidad condicional. En cierto sentido, "desintegración" es el proceso opuesto a la construcción de una medida de producto ".

Ver también: " El teorema de Fubini-Tonelli ", " Pérdida de bisagra ", " Función de pérdida " y " ¿Qué tan bueno es un núcleo cuando se usa como medida de similitud? " (Junio de 2007) por Nathan Srebro, el resumen:

" Resumen. Recientemente, Balcan y Blum sugirieron una teoría del aprendizaje basada en funciones de similitud generales, en lugar de núcleos positivos semi-definidos. Estudiamos la brecha entre las garantías de aprendizaje basadas en el aprendizaje basado en el núcleo y las que pueden obtenerse utilizando el núcleo como una función de similitud, que fue dejada abierta por Balcan y Blum. Proporcionamos un límite significativamente mejorado sobre cuán buena es una función del núcleo cuando se usa como una función de similitud, y ampliamos el resultado también a la pérdida de bisagra más relevante en la práctica. luego tasa de error cero uno. Además, mostramos que este límite es estrecho y, por lo tanto, establecemos que de hecho existe una brecha real entre la noción tradicional de margen basada en el núcleo y la noción más reciente basada en la similitud ".

$s$

Ver: granos y similitud (en R)

Es un recuadro negro, por lo que no sabe con certeza qué kernel se utiliza, si está basado en el kernel, y no conoce los detalles de la implementación del kernel una vez que cree saber cuál es. Ver: ¿La ecuación de rbfKernel en kernlab es diferente del estándar? .

Por otro lado, esto suena un poco loco.

Es rápido y efectivo, bajo un conjunto restringido de circunstancias. Como un martillo, si llevas un martillo, ¿la gente te llamará loco?

"Los métodos del núcleo deben su nombre al uso de las funciones del núcleo, que les permiten operar en un espacio de características implícitas de alta dimensión sin calcular las coordenadas de los datos en ese espacio, sino simplemente calculando los productos internos entre las imágenes de todos los pares de datos en el espacio de características. Esta operación es a menudo computacionalmente más barata que el cálculo explícito de las coordenadas. Este enfoque se llama "truco del núcleo". Se han introducido funciones del núcleo para datos de secuencia, gráficos, texto, imágenes, como bien como vectores ".

Lección: Usted (a veces) obtiene lo que paga.

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

Muchos, vea los enlaces anteriores, " Funciones populares del núcleo ", RBF , y aquí hay un ejemplo (costoso): " Una medida de distancia de relación de probabilidad para la similitud entre la serie de transformadas de Fourier " (2005), por Janacek, Bagnall y Powell.

Si f no existe en estas circunstancias generales en s , ¿existe un conjunto adicional de requisitos para los cuales existe f $f$ $s$ $f$

Los diferentes espacios y métodos pueden orientar mejor la comparación (y la desintegración) de problemas específicos, existen muchos métodos solo para el espacio de Hilbert .

Sí, la lista es grande, vea los enlaces de arriba y (por ejemplo): reproducción del espacio de Hilbert del núcleo .

Robar
fuente

-1

Pero no es obvio que este conjunto bastante general de circunstancias sea suficiente para implicar que se respeta la desigualdad del triángulo.

$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)$

Kodiólogo
fuente

No veo cómo esto prueba nada.

ameba dice Reinstate Monica

d

$d$

f (α) = 1 - α

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

s

$s$

f

$f$

d

$d$

f

$f$

m

$m$

s

$s$

d

$d$

f

$f$

m

$m$

1 - s (a, b)

$1-s(a,b)$

x_{α}

$x_\alpha$

m_{α}

$m_\alpha$

s

$s$