O teorema de Mercer funciona ao contrário?

Um colega tem uma função e para os nossos propósitos é uma caixa-preta. A função mede a semelhança de dois objetos. $s$ $s(a,b)$

Temos certeza de que tem essas propriedades: $s$

As pontuações de similaridade são números reais entre 0 e 1, inclusive.
Somente os objetos que são auto-idênticos têm pontuações de 1. Então implica vice-versa. $s(a,b)=1$ $a=b$
Temos a garantia de que . $s(a,b) = s(b,a)$

Agora ele quer trabalhar com algoritmos que requerem distâncias como entradas e dependem das entradas que satisfazem os axiomas da distância.

Meu pensamento era que poderíamos tratar as pontuações de similaridade como se fossem o resultado do kernel da RBF a alguma distância (poderia ser uma norma euclidiana ou outra distância), ou seja, podemos apenas reorganizar a álgebra e assumir que as pontuações de similaridade se referem a o kernel RBF para um par de pontos em algum sistema de coordenadas (desconhecido).

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

Onde é um vetor desconhecido, e é o objeto de interesse é alguma distância. $m_\alpha \in \mathbb{R}^n$ $x_\alpha$ $d$

As propriedades óbvias funcionam, em termos de respeitar os axiomas da distância. Os resultados devem ser não negativos e as distâncias são apenas 0 para objetos idênticos. Mas não é óbvio que esse conjunto geral de circunstâncias seja suficiente para implicar que a desigualdade do triângulo seja respeitada.

Por outro lado, isso parece meio louco.

Portanto, minhas perguntas são "existe um tal que para alguma métrica de distância, dadas essas propriedades em , e qual é esse ?" $f$ $f(s(a,b))=d(a,b)$ $d$ $s$ $f$

Se não existir nessas circunstâncias gerais em , existe um conjunto adicional de requisitos para os quais existe? $f$ $s$ $f$

kernel-trick distance similarities rbf-kernel Sycorax diz restabelecer Monica
fonte

Note-se que mesmo se você é dado o conjunto de distâncias entre pares que satisfazem os axiomas da distância, ele é não garantiu que há um espaço euclidiano com pontos percebendo estas distâncias. Essa incorporação nem sempre é possível. Veja, por exemplo, math.stackexchange.com/questions/1000006 .

d (a, b)

$d(a,b)$

ameba diz Restabelecer Monica

É uma linha muito interessante! Obrigado por compartilhar isso. Não era minha intenção me limitar a uma distância específica. (Desde que, seguindo a direção oposta, pode-se usar o kernel RBF com uma distância não euclidiana.)

Sycorax diz Reinstate Monica

Portanto, sua pergunta é apenas sobre como converter em forma que satisfaça a desigualdade do triângulo? Se essa matriz de distâncias é incorporável em um espaço euclidiano, não importa para você. Corrigir? Minha intuição é que, para uma arbitrária que não vai ser possível.

s (a, b)

$s(a,b)$

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

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

d

$d$

s

$s$

ameba diz Restabelecer Monica

Isto está correto. Suspeito que isso não seja possível, pelo menos não sem restrições adicionais sobre .

s

$s$

Sycorax diz Restabelecer Monica

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

$f: f(x) = I_{x>0}$ sempre leva a métrica discreta ( en.wikipedia.org/wiki/Discrete_space ), mas isso provavelmente não se destina portanto, algumas condições devem ser adicionados (?)

Juho Kokkala

Respostas:

O teorema de Mercer funciona ao contrário?

Nem em todos os casos.

Wikipedia: "Em matemática, especificamente análise funcional, o teorema de Mercer é uma representação de uma função positiva definida simétrica em um quadrado como a soma de uma sequência convergente de funções do produto. Esse teorema, apresentado em (Mercer 1909), é um dos resultados mais notáveis do trabalho de James Mercer.É uma ferramenta teórica importante na teoria das equações integrais; é usada na teoria espacial de Hilbert dos processos estocásticos, por exemplo, o teorema de Karhunen – Loève; e também é usada para caracterizar um núcleo semi-definido positivo simétrico.

É um mapeamento " muitos para um " em um espaço de Hilbert . - uma simplificação grosseira seria descrevê-lo como um hash ou soma de verificação que você pode testar em um arquivo para determinar a identidade ou não.

Explicação mais técnica: Teorema da desintegração

"Em matemática, o teorema da desintegração é um resultado na teoria das medidas e na teoria das probabilidades. Ele define rigorosamente a idéia de uma " restrição "não trivial de uma medida a um subconjunto de medidas zero do espaço de medidas em questão. Está relacionado ao existência de medidas condicionais de probabilidade. Em certo sentido, "desintegração" é o processo oposto à construção de uma medida de produto ".

Veja também: " O teorema de Fubini-Tonelli ", " Perda de dobradiça ", " Função de perda " e " Quão bom é um núcleo quando usado como uma medida de similaridade? " (Junho de 2007) por Nathan Srebro, o resumo:

" Resumo. Recentemente, Balcan e Blum sugeriram uma teoria da aprendizagem baseada em funções gerais de semelhança, em vez de núcleos semi-definidos positivos. Estudamos a lacuna entre as garantias de aprendizagem baseadas na aprendizagem baseada em kernel e aquelas que podem ser obtidas usando o kernel como uma função de similaridade, que foi deixada em aberto por Balcan e Blum.Nós fornecemos um limite significativamente melhorado de quão boa é uma função do kernel quando usada como uma função de similaridade, e estendemos o resultado também à perda de dobradiça mais relevante na prática. depois, a taxa de erro zero 1. Além disso, mostramos que esse limite é rígido e, portanto, estabelecemos que existe de fato uma lacuna real entre a noção tradicional de margem baseada no kernel e a mais recente noção baseada em similaridade ".

Um colega tem uma função e para os nossos propósitos é uma caixa-preta. $s$

Veja: núcleos e similaridade (em R)

É uma caixa preta, então você não sabe ao certo qual kernel é usado, se for baseado em kernel, e você não conhece os detalhes da implementação do kernel depois de pensar que sabe qual é. Veja: A equação do rbfKernel no kernlab é diferente do padrão? .

Por outro lado, isso parece meio louco.

É rápido e eficaz, sob um conjunto restrito de circunstâncias. Como um martelo, se você carrega um martelo, as pessoas o chamam de louco?

"Os métodos do kernel devem seu nome ao uso de funções do kernel, que lhes permitem operar em um espaço de recurso implícito e de alta dimensão, sem nunca calcular as coordenadas dos dados naquele espaço, mas simplesmente computando os produtos internos entre as imagens de todos os pares de dados no espaço de recursos.Esta operação é geralmente computacionalmente mais barata que o cálculo explícito das coordenadas.Esta abordagem é chamada de "truque do kernel". As funções do kernel foram introduzidas para dados de seqüência, gráficos, texto, imagens, como bem como vetores. "

Lição: você (às vezes) recebe o que paga.

Portanto, minhas perguntas são "Existe um tal que para alguma métrica de distância, dadas essas propriedades em , e qual é esse ?" $f$ $f(s(a,b))=d(a,b)$ $d$ $s$ $f$

Muitos, consulte os links acima, " Popular Kernel Functions ", RBF , e aqui está um exemplo (caro): " Uma medida de distância da razão de verossimilhança para a semelhança entre a transformação de Fourier da série temporal " (2005), de Janacek, Bagnall e Powell.

Se não existir nessas circunstâncias gerais em , existe um conjunto adicional de requisitos para os quais existe? $f$ $s$ $f$

Diferentes espaços e métodos podem direcionar melhor a comparação (e a desintegração) de problemas específicos; existem muitos métodos apenas para o espaço de Hilbert .

Sim, a lista é grande, veja os links acima e (por exemplo): Reproduzindo o espaço Hilbert do kernel .

Roubar
fonte

-1

Mas não é óbvio que esse conjunto geral de circunstâncias seja suficiente para implicar que a desigualdade do triângulo seja respeitada.

De fato, não é suficiente. Vamos trabalhar com . Se existem três pontos , com , , e , a desigualdade do triângulo falha, porque . $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)$

Kodiologist
fonte

Não vejo como isso prova alguma coisa.

Ameba diz Reinstate Monica

@amoeba Você não vê como isso prova que não precisa satisfazer a desigualdade do triângulo?

d

$d$

Kodiologist

Acho que isso mostra que escolher não funciona, mas não sei por que isso mostra que a desigualdade do triângulo não é respeitada por uma opção alternativa de função, como a (estranha) um que eu descrevo no meu post.

f (α) = 1 - α

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

Sycorax diz Restabelecer Monica

A questão é se as propriedades listadas de são suficientes para a existência de um tal que é uma métrica e, especialmente, se esse pode ser representado com o kernel RBF com algum mapeamento . Essa resposta parece perguntar se as propriedades listadas de são suficientes para ser uma métrica com um arbitrário .

s

$s$

f

$f$

d

$d$

f

$f$

m

$m$

s

$s$

d

$d$

f

$f$

Juho Kokkala

@ Kodiologist, mas até onde eu entendo, até a primeira versão no histórico de edições contém a parte sobre RBF com um mapeamento desconhecido , então não vejo a relevância de trabalhar com . E com relação ao seu comentário anterior, enquanto eu lia a pergunta, não se deve "saber" nada sobre como o mapa s para s - um contra-exemplo deve mostrar que esse mapeamento não pode ser construído para o contra-exemplo - .

m

$m$

1 - s (a, b)

$1-s(a,b)$

x_{α}

$x_\alpha$

m_{α}

$m_\alpha$

s

$s$

Juho Kokkala