Jak zmienia się podobieństwo cosinus po transformacji liniowej?

9

Czy istnieje matematyczny związek między:

podobieństwo cosinus nazwa dwóch wektorów i oraz $\operatorname{sim}(A, B)$ $A$ $B$
cosinus podobieństwo z i , niejednorodnie skalowane poprzez danej matrycy ? Tutaj jest daną macierzą diagonalną z nierównymi elementami na przekątnej. $\operatorname{sim}(MA, MB)$ $A$ $B$ $M$ $M$

Próbowałem przejrzeć obliczenia, ale nie mogłem dotrzeć do prostego / interesującego linku (wyrażenia). Zastanawiam się, czy istnieje.

Np. Kąty nie są zachowywane w skalowaniu nierównomiernym, ale jaki jest związek między kątami pierwotnymi a kątami po skalowaniu nierównomiernym? Co można powiedzieć o związku między zbiorem wektorów S1 a innym zbiorem wektorów S2 - gdzie S2 uzyskuje się przez nierównomierne skalowanie S1?

linear-algebra cosine-similarity

— turdus-merula
źródło

@ whuber, dziękuję! Tak, M jest daną macierzą (macierzą skalowania - czyli macierzą diagonalną, bez innych ograniczeń). W pewnym sensie chciałem wiedzieć, co się dzieje (pod względem podobieństwa cosinus dla dowolnej pary wektorów) do przestrzeni wektorowej, która podlega skalowaniu nieliniowemu.

— turdus-merula

2

Warto zauważyć, że jeśli wszystkie współczynniki skalowania są nieujemne (jak można by naturalnie założyć), wówczas wszystkie symetryczne macierze o dodatniej wartości dodatniej można uznać za macierze „skalowane”. Szukana relacja jest szeroko stosowana, między innymi , w badaniu i opisie zniekształceń w rzutach mapy. Tam znajdują się centra zainteresowania w maksymalnych i minimalnych kątach na powierzchni ziemi, które byłyby powiązane z dwoma prostopadłymi kierunkami na mapie. Istnieje bezpośredni związek między tymi kątami a stosunkami dwóch czynników skali.

— whuber

8

Ponieważ jest dość ogólne, a zmiana podobieństwa kosinusowego zależy od konkretnych i i ich związku z , nie jest możliwe ustalenie konkretnego wzoru. Istnieją jednak praktycznie obliczalne granice, o ile podobieństwo cosinusa może się zmienić . Można je znaleźć, zwiększając kąt między a biorąc pod uwagę, że podobieństwo cosinus między i jest określoną wartością, powiedzmy (gdzie jest kątem między i ). Odpowiedź mówi nam, ile kąt $M$ $A$ $B$ $M$ $MA$ $MB$ $A$ $B$ $\cos(2\phi)$ $2\phi$ $A$ $B$ $2\phi$ może ewentualnie być zginane przez transformacji . $M$

Obliczenia grożą bałaganem. Niektóre sprytne wybory zapisu, a także pewne wstępne uproszczenia, zmniejszają wysiłek. Okazuje się, że rozwiązanie w dwóch wymiarach ujawnia wszystko, co musimy wiedzieć. Jest to problem możliwy do rozwiązania, zależny tylko od jednej rzeczywistej zmiennej , którą można łatwo rozwiązać za pomocą technik rachunku różniczkowego. Prosty argument geometryczny rozszerza to rozwiązanie na dowolną liczbę wymiarów . $\theta$ $n$

Wstęp do matematyki

Z definicji cosinus kąta między dowolnymi dwoma wektorami i uzyskuje się przez znormalizowanie ich do długości jednostkowej i pobranie ich iloczynu. A zatem, $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)$

i, pisząc , cosinus kąta między obrazami i pod transformacją wynosi $\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}$

Zauważ, że tylko znaczenie w analizie, a $\Sigma$ nie samoMożemy zatem wykorzystać Singular Value rozpadu (SVD) z uproszczenie problemu. Przypomnijmy, że wyraża to jako iloczyn (od prawej do lewej) macierzy ortogonalnej , macierzy diagonalnej i innej macierzy ortogonalnej : $M$ $M$ $M$ $V^\prime$ $D$ $U$

M = U D V^{'} .

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

Innymi słowy, nie jest podstawą uprzywilejowanych wektorów (kolumny ), w którym działa przez przeskalowanie co osobno przez przekątnej wejściowej od (które będzie wywoływać ), a następnie stosując obrót (lub anty-obrót) do wyniku. Ten końcowy obrót nie zmieni żadnych długości ani kątów, a zatem nie powinien wpływać na . Możesz to zobaczyć formalnie z obliczeniami $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.$

W związku z tym, aby zbadać możemy dowolnie zastąpić dowolną inną macierzą, która daje te same wartości w . Po zamówieniu taki sposób, aby wielkość zmniejszyła się (i zakładając, że nie jest identycznie zerowe), dobrym wyborem jest $\Sigma$ $M$ $(1)$ $e_i$ $d_i$ $M$ $M$

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

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

Ukośne elementy to $(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.$

W szczególności wpływ (czy to w postaci oryginalnej, czy zmienionej) na wszystkie kąty jest całkowicie zdeterminowany przez to, że $M$

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

$M e_i = \lambda_i e_i.$

Analiza przypadku specjalnego

Niech . Ponieważ zmiana długości wektorów nie zmienia kąta między nimi, możemy założyć, że i są wektorami jednostkowymi. W płaszczyźnie wszystkie takie wektory mogą być oznaczone kątem, który tworzą z , co pozwala nam pisać $n=2$ $A$ $B$ $e_1$

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

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

W związku z tym

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

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

(Zobacz rysunek poniżej.)

Zastosowanie jest proste: naprawia pierwsze współrzędne i i mnoży ich drugie współrzędne przez . Dlatego kąt od do wynosi $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)).$

Ponieważ jest funkcją ciągłą, ta różnica kątów jest funkcją ciągłą . W rzeczywistości jest różniczkowalny. To pozwala nam znaleźć skrajne kąty poprzez sprawdzenie zer pochodnej . Ta pochodna jest łatwa do obliczenia: jest to stosunek funkcji trygonometrycznych. Zera mogą występować tylko między zerami jego licznika, więc nie zawracajmy sobie głowy obliczeniem mianownika. Otrzymujemy $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)}{*}.$

Szczególne przypadki , i są łatwe do zrozumienia: odpowiadają sytuacjom, w których ma niższą rangę (a więc zgniata wszystkie wektory do linii); gdzie jest wielokrotnością macierzy tożsamości; i gdzie i są równoległe (stąd kąt między nimi nie może się zmienić, niezależnie od ). Przypadek jest wykluczony przez warunek . $\lambda_2=0$ $\lambda_2=1$ $\phi=0$ $M$ $M$ $A$ $B$ $\theta$ $\lambda_2=-1$ $\lambda_2 \ge 0$

Oprócz tych szczególnych przypadków, zera występują tylko wtedy, gdy : to znaczy, lub . Oznacza to, że linia wyznaczona przez przecina kąt . Wiemy teraz, że skrajne wartości kąta między i muszą znajdować się wśród wartości , więc obliczmy je: $\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)). }$

Odpowiednie cosinusy to

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

i

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

Często wystarczy zrozumieć, jak zniekształca kąty proste. W tym przypadku , co prowadzi do , które możesz podłączyć do poprzednich formuł. $M$ $2\phi=\pi/2$ $\tan(\phi) = \cot(\phi) = 1$

Zauważ, że im mniejsze , tym bardziej ekstremalne stają się te kąty i tym większe jest zniekształcenie. $\lambda_2$

Ta rycina pokazuje cztery konfiguracje wektorów i oddzielonych kątem . Okrąg jednostki i jego eliptyczny obraz pod są cieniowane dla odniesienia (z działaniem równomiernie przeskalowanym, aby ). Nagłówki cyfra wskazuje wartość , środek i . Najbliższe takie i mogą się pojawić po transformacji przez to konfiguracja taka jak ta po lewej z $A$ $B$ $2\phi = \pi/3$ $M$ $M$ $\lambda_1=1$ $\theta$ $A$ $B$ $A$ $B$ $M$ $\theta=0$ . Najbardziej oddalone od siebie mogą być konfiguracje takie jak ta po prawej stronie z . Pokazane są dwie możliwości pośrednie. $\theta=\pi/2$

Rozwiązanie dla wszystkich wymiarów

Widzieliśmy, jak działa , rozszerzając każdy wymiar o współczynnik . Spowoduje to zniekształcenie sfery jednostkowej w elipsoidę. W określić swoje główne osie. Do są odległości od pochodzenia, wzdłuż tych osi, do elipsoidy. W konsekwencji najmniejsza, , jest najkrótszą odległością (od dowolnego kierunku) od początku do elipsoidy, a największa, , jest najdalszą (od dowolnego kierunku) odległości od początku do elipsoidy. $M$ $i$ $\lambda_i$ $\{A\,|\, A^\prime A = 1\}$ $e_i$ $\lambda_i$ $\lambda_n$ $\lambda_1$

W większych wymiarach , i znajdują się w dwuwymiarowej podprzestrzeni. odwzorowuje koło jednostki w tej podprzestrzeni na przecięcie elipsoidy z płaszczyzną zawierającą i . To skrzyżowanie, będące liniowym zniekształceniem koła, jest elipsą. Oczywiście największa odległość do tej elipsy wynosi nie więcej niż a najkrótsza odległość nie jest mniejsza niż . $n\gt 2$ $A$ $B$ $M$ $MA$ $MB$ $\lambda_1=1$ $\lambda_n$

Jak zauważyliśmy na końcu poprzedniego rozdziału, najbardziej ekstremalną możliwością jest umieszczenie i w płaszczyźnie zawierającej dwa dla których stosunek odpowiednich jest tak mały, jak to możliwe. Stanie się to na płaszczyźnie . Mamy już rozwiązanie dla tej sprawy. $A$ $B$ $e_i$ $\lambda_i$ $e_1, e_n$

Wnioski

Ekstremalne podobieństwa cosinusów osiągalne przez zastosowanie do dwóch wektorów mających podobieństwo cosinusów podano w i . Osiąga się to poprzez umieszczenie i pod równymi kątami w kierunku, w którym maksymalnie wydłuża dowolny wektor (taki jak kierunek ) i rozdzielając je w kierunku, w którym minimalnie wydłuża dowolny wektor ( takie jak kierunek ). $M$ $\cos(2\phi)$ $(2)$ $(3)$ $A$ $B$ $\Sigma=M^\prime M$ $e_1$ $\Sigma$ $e_n$

Te skrajne mogą być obliczane w odniesieniu do metody SVD . $M$

— Whuber
źródło

To fantastyczna odpowiedź! Dziękuję bardzo za tę szczegółową dyskusję! Uważam, że masz błąd znaku w eqn (3), gdzie powinieneś mieć ogólny znak minus.

— LFH

Interesuje mnie przypadek, w którym kąt zbliża się do zera i chciałbym uzyskać nierówność między i . Czy to prawda, że w oparciu o twoje obliczenia po prostu muszę znaleźć najbardziej ekstremalny (to jest najmniejszy) iw tym przypadku asymptotyczną nierówność podaje jak ?

2 ϕ

$2\phi$

2 ϕ

$2\phi$

f

$f$

λ_{n}

$\lambda_n$

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

Prawdopodobnie jesteś zainteresowany:

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

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

Możesz diagonalizować (lub, jak to nazywacie, PCA), co mówi, że podobieństwo podczas transformacji zachowuje się poprzez rzutowanie na główne składniki, a następnie obliczanie podobieństwa w tej nowej przestrzeni. Aby jeszcze bardziej to , pozwól, aby główne składniki były z wartościami własnymi . Następnie $M^TM=U\Sigma U^T$ $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,$

co daje ci:

(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.$

Zauważ, że dzieje się tutaj skalowanie: rozciągają się / kurczą. Gdy są wektorami jednostkowymi i jeśli każdy , to odpowiada rotacji, a otrzymasz: , który jest jest równoważne stwierdzeniu, że produkty wewnętrzne są niezmienne pod rotacją. Zasadniczo kąt pozostaje taki sam, gdy jest transformacją konformalną, co w tym przypadku wymaga, aby był odwracalny, a rozkład biegunowy spełnia z , tj. . $\lambda_i$ $A,B$ $\lambda_i=1$ $M$ $\mbox{sim}(MA,MB)=\mbox{sim}(A,B)$ $M$ $M$ $M$ $M=OP$ $P=aI$ $M^TM=a^2I$

— Alex R.
źródło

1

Twoje wstępne stwierdzenie problemu pomija normalizację wektorów , , i wymaganych do obliczenia podobieństwa cosinus. Nie wydaje się również, aby późniejsza analiza dotyczyła tej normalizacji. Należy zauważyć w szczególności, że podobieństwa cosinus są zachowane, nawet jeśli wszystkie wartości własne są równe pewnej (dodatniej) wartości, która różni się od . To pokazuje, nawet w tym prostym przypadku, że można powiedzieć znacznie więcej.

A

$A$

B

$B$

M A

$MA$

M B

$MB$

1

$1$

— whuber

@ whuber: podobieństwo cosinus jest zachowane dokładnie wtedy, gdy jest transformacją konformalną, co w tym przypadku jest równoznaczne z wymaganiem, aby był odwracalny, a , wielokrotność tożsamości. Mówiąc inaczej, rozkład biegunowy spełnia , gdzie . Masz rację o normalizacji, ale wydaje się głupie mówić o cosinus podobieństwa nie znormalizowanych wektorów .

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

Wcale nie głupie! Ponieważ to „podobieństwo” wynika z cosinusa kąta między wektorami, ma sens dla dowolnych dwóch wektorów niezerowych. Co mam na myśli przez „dużo więcej można powiedzieć” jest to, że skuteczne granice kąta między obrazami i mogą być uzyskane w zakresie kąta między i oraz wartości własnych .

A

$A$

B

$B$

A

$A$

B

$B$

M

$M$

— whuber