Como a semelhança de cosseno muda após uma transformação linear?

9

Existe uma relação matemática entre:

o co-seno similaridade $\operatorname{sim}(A, B)$ de dois vectores $A$ e $B$ , e
o co-seno similaridade $\operatorname{sim}(MA, MB)$ de $A$ e $B$ , não-uniformemente dimensionadas através de uma dada matriz de $M$ ? Aqui $M$ é uma matriz diagonal dada com elementos desiguais na diagonal.

Tentei revisar os cálculos, mas não consegui acessar um link simples / interessante (expressão). Gostaria de saber se existe um.

Por exemplo, os ângulos não são preservados na escala não uniforme, mas qual é a relação entre os ângulos originais e os que se seguem à escala não uniforme? O que pode ser dito sobre o vínculo entre um conjunto de vetores S1 e outro conjunto de vetores S2 - em que S2 é obtido pela escala não uniforme de S1?

linear-algebra cosine-similarity turdus-merula
fonte

@ whuber, obrigado! Sim, M é uma matriz dada (uma matriz de escala - portanto, uma matriz diagonal, sem outras restrições). Em certo sentido, eu queria saber o que acontece (em termos de semelhança de cosseno para qualquer par de vetores) com um espaço vetorial que sofre uma escala não linear.

turdus-merula

2

Vale a pena notar que, se todos os fatores de escala não forem negativos (como seria de se presumir naturalmente), todas as matrizes positivas simétricas definidas podem ser consideradas matrizes de "escala". O relacionamento que você procura é amplamente utilizado, entre outros , no estudo e na descrição da distorção nas projeções de mapas. Lá, os centros de interesse são os ângulos máximo e mínimo na superfície da Terra, que seriam associados a duas direções perpendiculares no mapa. Existe uma relação direta entre esses ângulos e as proporções dos dois fatores de escala.

whuber

8

Como é bastante geral, e a mudança na semelhança de cosseno depende dos e e de sua relação com , nenhuma fórmula definida é possível. No entanto, existem limites praticamente calculáveis para o quanto a similaridade do cosseno pode mudar . Eles podem ser encontrados extraindo o ângulo entre e dado que a semelhança de cosseno entre e é um valor especificado, por exemplo, (onde é o ângulo entre e $M$ $A$ $B$ $M$ $MA$ $MB$ $A$ $B$ $\cos(2\phi)$ $2\phi$ $A$ ) A resposta nos diz o quanto qualquer ângulo pode eventualmente ser dobrado pela transformação . $B$ $2\phi$ $M$

Os cálculos ameaçam ser confusos. Algumas escolhas inteligentes de notação, juntamente com algumas simplificações preliminares, reduzem o esforço. Acontece que a solução em duas dimensões revela tudo o que precisamos saber. Este é um problema tratável, dependendo apenas de uma variável real , que é prontamente resolvida usando técnicas de cálculo. Um argumento geométrico simples estende essa solução a qualquer número de dimensões . $\theta$ $n$

Preliminares matemáticas

Por definição, o cosseno do ângulo entre quaisquer dois vetores e é obtido normalizando-os em comprimento unitário e obtendo seu produto. Portanto, $A$ $B$

\frac{A^{'} B}{\sqrt{(A^{'} A) (B^{'} B)}} = \cos (2 ϕ)

$\frac{A^\prime B}{\sqrt{(A^\prime A)\, (B^\prime B)}} = \cos(2\phi)$

e, escrevendo , o cosseno do ângulo entre as imagens de e sob a transformação é $\Sigma = M^\prime M$ $A$ $B$ $M$

\begin{matrix} (1) & \frac{(M A)^{'} (M B)}{\sqrt{((M A)^{'} (M A)) ((M B)^{'} (M B))}} = \frac{A^{'} Σ B}{\sqrt{(A^{'} Σ A) (B^{'} Σ B)}} . \end{matrix}

$\frac{(MA)^\prime (MB)}{\sqrt{((MA)^\prime (MA))\, ((MB)^\prime (MB))}} = \frac{A^\prime \Sigma B}{\sqrt{(A^\prime \Sigma A) (B^\prime \Sigma B)}}.\tag{1}$

Observe que apenas importa na análise, $\Sigma$ não o próprio Portanto, podemos explorar a Decomposição de Valor Singular (SVD) de para simplificar o problema. Lembre-se de que isso expressa como um produto (da direita para a esquerda) de uma matriz ortogonal , uma matriz diagonal e outra matriz ortogonal : $M$ $M$ $M$ $V^\prime$ $D$ $U$

M = U D V^{'} .

$M = U\,D\,V^\prime.$

Em outras palavras, existe uma base de vectores privilegiados (as colunas de ) em que actua por escalonamento de cada um separadamente pelo entrada diagonal de (que chamaremos ) e depois aplicar uma rotação (ou anti-rotação) ao resultado. Essa rotação final não mudará nenhum comprimento ou ângulo e, portanto, não deve afetar . Você pode ver isso formalmente com o cálculo $e_1, \ldots, e_n$ $V$ $M$ $e_i$ $i^\text{th}$ $D$ $d_i$ $U$ $\Sigma$

Σ = M^{'} M = (U D V^{'})^{'} (U D V^{'}) = V D (U^{'} U) D V^{'} = V D^{2} V^{'} .

$\Sigma = M^\prime M = (U D V^\prime)^\prime (U D V^\prime) = V D (U^\prime U) D V^\prime = V D^2 V^\prime.$

Conseqüentemente, para estudar podemos substituir livremente por qualquer outra matriz que produz os mesmos valores em . Ordenando o de modo que o diminuir em tamanho (e assumindo que não é idêntica zero), uma escolha agradável de é $\Sigma$ $M$ $(1)$ $e_i$ $d_i$ $M$ $M$

M = \frac{1}{d_{1}} D V^{'} .

$M = \frac{1}{{d_1}} D V^\prime.$

Os elementos diagonais de são $(1/{d_1})D$

1 = d_{1} / d_{1} \geq λ_{2} = d_{2} / d_{1} \geq λ_{3} = d_{3} / d_{1} \geq \dots \geq λ_{n} = d_{n} / d_{1} \geq 0.

$1 = d_1/d_1 \ge \lambda_2 = d_2/{d_1} \ge \lambda_3 = d_3/{d_1} \ge \cdots \ge \lambda_n = d_n/{d_1} \ge 0.$

Especificamente, o efeito de (seja na sua forma original ou alterada) em todos os ângulos é completamente determinado pelo fato de que $M$

M e_{i} = λ_{i} e_{i} .

$M e_i = \lambda_i e_i.$

Análise de um caso especial

Seja . Como alterar os comprimentos dos vetores não altera o ângulo entre eles, podemos assumir que e são vetores unitários. No plano, todos esses vetores podem ser designados pelo ângulo que fazem com , permitindo escrever $n=2$ $A$ $B$ $e_1$

A = \cos (θ - ϕ) e_{1} + \sin (θ - ϕ) e_{2} .

$A = \cos(\theta-\phi)e_1 + \sin(\theta-\phi)e_2.$

Portanto

B = \cos (θ + ϕ) e_{1} + \sin (θ + ϕ) e_{2} .

$B = \cos(\theta+\phi)e_1 + \sin(\theta+\phi)e_2.$

(Veja a figura abaixo.)

A aplicação de é simples: ela fixa as primeiras coordenadas de e e multiplica suas segundas coordenadas por . Portanto, o ângulo de a é $M$ $A$ $B$ $\lambda_2$ $MA$ $MB$

f (θ) = \arctan (λ_{2} \tan (θ + ϕ)) - \arctan (λ_{2} \tan (θ - ϕ)) .

$f(\theta) = \arctan(\lambda_2 \tan(\theta+\phi)) - \arctan(\lambda_2 \tan(\theta-\phi)).$

Como é uma função contínua, essa diferença de ângulos é uma função contínua de . De fato, é diferenciável. Isso nos permite encontrar ângulos extremos inspecionando os zeros da derivada . Essa derivada é simples de calcular: é uma razão de funções trigonométricas. Os zeros podem ocorrer apenas entre os zeros de seu numerador, portanto, não vamos nos preocupar em calcular o denominador. Nós obtemos $M$ $\theta$ $f^\prime(\theta)$

f^{'} (θ) = \frac{λ_{2} (1 - λ_{2}) (λ_{2} + 1) \sin (2 θ) \sin (2 ϕ)}{*} .

$f^\prime(\theta) = \frac{\lambda_2(1-\lambda_2)(\lambda_2+1)\sin(2\theta)\sin(2\phi)}{*}.$

Os casos especiais de , e são facilmente entendidos: eles correspondem às situações em que é de classificação reduzida (e, assim, esmaga todos os vetores em uma linha); onde é um múltiplo da matriz de identidade; e onde e são paralelos (de onde o ângulo entre eles não pode mudar, independentemente de ). O caso é excluído pela condição . $\lambda_2=0$ $\lambda_2=1$ $\phi=0$ $M$ $M$ $A$ $B$ $\theta$ $\lambda_2=-1$ $\lambda_2 \ge 0$

Além desses casos especiais, os zeros ocorrem apenas onde : ou seja, ou . Isto significa que a linha de determinados por bissecta o ângulo . Sabemos agora que os valores extremos do ângulo entre e deve situar-se entre os valores de , então vamos calcular-los: $\sin(2\theta)=0$ $\theta=0$ $\theta=\pi/2$ $e_1$ $AB$ $MA$ $MB$ $f(\theta)$

\begin{aligned} f (0) & = \arctan (λ_{2} \tan (ϕ)) - \arctan (λ_{2} \tan (- ϕ)) = 2 \arctan (λ_{2} \tan (ϕ)); \\ f (π / 2) & = \arctan (λ_{2} \tan (π / 2 + ϕ)) - \arctan (λ_{2} \tan (π / 2 - ϕ)) = 2 \arctan (λ_{2} \cot (- ϕ)) . \end{aligned}

$\eqalign{ f(0) &= \arctan(\lambda_2 \tan(\phi)) - \arctan(\lambda_2 \tan(-\phi)) = 2\arctan(\lambda_2\tan(\phi)); \\ f(\pi/2) &= \arctan(\lambda_2 \tan(\pi/2+\phi)) - \arctan(\lambda_2 \tan(\pi/2-\phi)) = 2\arctan(\lambda_2\cot(-\phi)). }$

Os cossenos correspondentes são

\begin{matrix} (2) & \cos (f (0)) = \frac{1 - λ_{2}^{2} \tan (ϕ)^{2}}{1 + λ_{2}^{2} \tan (ϕ)^{2}} \end{matrix}

$\cos(f(0)) = \frac{1 - \lambda_2^2 \tan(\phi)^2}{1 + \lambda_2^2 \tan(\phi)^2}\tag{2}$

e

\begin{matrix} (3) & \cos (f (π / 2)) = \frac{1 - λ_{2}^{2} \cot (ϕ)^{2}}{1 + λ_{2}^{2} \cot (ϕ)^{2}} = \frac{\tan (ϕ)^{2} - λ_{2}^{2}}{\tan (ϕ)^{2} + λ_{2}^{2}} . \end{matrix}

$\cos(f(\pi/2)) = \frac{1 - \lambda_2^2 \cot(\phi)^2}{1 + \lambda_2^2 \cot(\phi)^2} = \frac{\tan(\phi)^2 - \lambda_2^2 }{\tan(\phi)^2 + \lambda_2^2}.\tag{3}$

Muitas vezes, é suficiente entender como distorce os ângulos retos. Nesse caso, , levando a , que você pode conectar nas fórmulas anteriores. $M$ $2\phi=\pi/2$ $\tan(\phi) = \cot(\phi) = 1$

Observe que quanto menor se torna, mais extremos esses ângulos se tornam e maior é a distorção. $\lambda_2$

Esta figura mostra quatro configurações dos vetores e $A$ separados por um ângulo de . O círculo unitário e sua imagem elíptica sob são sombreados para referência (com a ação de redimensionada uniformemente para fazer ). As posições figura indicam o valor de , o ponto médio de e . O mais próximo que um desses e pode chegar quando transformado por é uma configuração como a da esquerda com $B$ $2\phi = \pi/3$ $M$ $M$ $\lambda_1=1$ $\theta$ $A$ $B$ $A$ $B$ $M$ . O mais distante que eles podem estar é uma configuração como a da direita com . Duas possibilidades intermediárias são mostradas. $\theta=0$ $\theta=\pi/2$

Solução para todas as dimensões

Vimos como age expandindo cada dimensão por um fator . Isso distorcerá a esfera unitária $M$ $i$ $\lambda_i$ em um elipsóide. O determinar seus eixos principais. O são as distâncias a partir da origem, ao longo desses eixos, ao elipsóide. Consequentemente, a menor, , é amenor distância(em qualquer direção) da origem ao elipsóide e a maior, , é amaior distância(em qualquer direção) da origem ao elipsóide. $\{A\,|\, A^\prime A = 1\}$ $e_i$ $\lambda_i$ $\lambda_n$ $\lambda_1$

Nas dimensões superiores , e fazem parte de um subespaço bidimensional. mapeia o círculo unitário neste subespaço na intersecção do elipsóide com um plano contendo e . Essa interseção, sendo uma distorção linear de um círculo, é uma elipse. Obviamente, a maior distância desta elipse não é maior que e a menor distância não é menor que . $n\gt 2$ $A$ $B$ $M$ $MA$ $MB$ $\lambda_1=1$ $\lambda_n$

Como foi observado no final da secção precedente, o mais possibilidade extrema é quando e estão situados num plano que contém dois dos para os quais a razão entre a correspondente é tão pequena quanto possível. Isso acontecerá no plano . Já temos a solução para esse caso. $A$ $B$ $e_i$ $\lambda_i$ $e_1, e_n$

Conclusões

Os extremos de semelhança de cosseno alcançáveis aplicando a dois vetores com semelhança de cosseno são dados por $M$ $\cos(2\phi)$ e . Eles são alcançados situando e em ângulos iguais a uma direção na qual alonga ao máximo qualquer vetor (como adireção ) e os separa em uma direção na qual alonga minimamente qualquer vetor (como o direcção). $(2)$ $(3)$ $A$ $B$ $\Sigma=M^\prime M$ $e_1$ $\Sigma$ $e_n$

Esses extremos pode ser calculado em termos da SVD de . $M$

whuber
fonte

Esta é uma resposta fantástica! Muito obrigado por esta discussão detalhada! Acredito que você tenha um erro de sinal na eqn (3), onde você deve apenas ter um sinal de menos geral.

LFH

Estou interessado no caso em que o ângulo

aproxima de zero e eu gostaria de obter uma desigualdade entre

e

. É verdade que, com base no seu cálculo, só preciso encontrar o mais extremo (o menor)

e, neste caso, a desigualdade assintótica é dada por

2 ϕ

$2\phi$

2 ϕ

$2\phi$

f

$f$

λ_{n}

$\lambda_n$

como

?

2 λ_{n} ϕ \leq f \leq 2 λ_{n}^{- 1} ϕ

$2\lambda_n\phi\leq f\leq 2\lambda_n^{-1}\phi$

ϕ \to 0

$\phi\to0$

LFH

6

Você provavelmente está interessado em:

(M A, M B) = A^{T} (M^{T} M) B,

$(MA,MB)=A^T(M^TM)B,$

Você pode diagonalizar (ou como você chama, PCA), o que indica que a semelhança de $M^TM=U\Sigma U^T$ na transformação se comporta projetando em seus componentes principais e subsequentemente calculando a similaridade neste novo espaço. Para concretizar este um pouco mais, deixe os principais componentes ser com valores próprios . Então $A,B$ $M$ $A,B$ $u_i$ $\lambda_i$

U B = \sum_{i} (u_{i}, b_{i}) u_{i}, U A = \sum_{i} (u_{i}, a_{i}) u_{i},

$UB=\sum_i(u_i,b_i)u_i, \ UA=\sum_i(u_i,a_i)u_i,$

o que lhe dá:

(M A, M B) = \sum_{i = 1}^{n} (u_{i}, a_{i}) (u_{i}, b_{i}) λ_{i} .

$(MA,MB)=\sum_{i=1}^n (u_i,a_i)(u_i,b_i)\lambda_i.$

Observe que há uma escala acontecendo aqui: o está se esticando / encolhendo. Quando são vetores unitários e se todo , é invertível e a decomposição polar de satisfaz $\lambda_i$ $A,B$ $\lambda_i=1$ $M$ corresponde a uma rotação, e você começa: , o que equivale a dizer que os produtos internos são invariantes em rotações. Em geral, o ângulo permanece o mesmo quando é uma transformação conforme, que neste caso exige que $\mbox{sim}(MA,MB)=\mbox{sim}(A,B)$ $M$ $M$ $M$ com , isto é, . $M=OP$ $P=aI$ $M^TM=a^2I$

Alex R.
fonte

11

Sua declaração inicial do problema negligencia a normalização dos vetores

,

e

necessários para calcular a similaridade do cosseno. Também não parece que a análise subsequente aborda essa normalização. Observe, em particular, que as semelhanças de cosseno são preservadas mesmo quando todos os autovalores são iguais a algum valor (positivo) que difere de

A

$A$

B

$B$

M A

$MA$

M B

$MB$

1

$1$ . Isso demonstra, mesmo neste caso simples, que muito mais pode ser dito.

whuber

@whuber: similaridade cosseno é preservado exactamente quando

é uma transformação conformacional, que neste caso é equivalente a requerendo

a ser invertida e

, um múltiplo da identidade. Dito de outro modo, a decomposição polar de

satisfaz

, onde

. Você está certo sobre a normalização, mas, ao que parece bobagem para falar sobre a similaridade do cosseno com vetores não normalizados

.

M

$M$

M

$M$

M^{T} M = a^{2} I

$M^TM=a^2I$

M

$M$

M = O P

$M=OP$

P = a I

$P=aI$

A, B

$A,B$

Alex R.

2

Não é bobo! Como essa "similaridade" é dada pelo cosseno do ângulo entre os vetores, faz sentido para quaisquer dois vetores diferentes de zero. O que eu quis dizer com "muito mais pode ser dito" é que limites efetivos no ângulo entre as imagens de

e

podem ser obtidos em termos do ângulo entre

e

A

$A$

B

$B$

A

$A$

B

$B$ e os valores próprios de

.

M

$M$

whuber

Como a semelhança de cosseno muda após uma transformação linear?

Respostas:

Preliminares matemáticas

Análise de um caso especial

Solução para todas as dimensões

Conclusões