Quelle est l'intuition derrière SVD?

J'ai lu sur la décomposition en valeurs singulières (SVD). Dans presque tous les manuels, il est mentionné que la matrice est divisée en trois matrices avec une spécification donnée.

Mais quelle est l'intuition derrière la division de la matrice sous une telle forme? La PCA et d’autres algorithmes de réduction de dimensionnalité sont intuitifs en ce sens qu’ils ont de bonnes propriétés de visualisation, mais ce n’est pas le cas avec SVD.

matrix linear-algebra svd intuition SHASHANK GUPTA
la source

Vous voudrez peut-être commencer par l’intuition de la décomposition de valeurs propres et de vecteurs propres, car la SVD en est une extension pour tous les types de matrices, au lieu de carrés.

JohnK

Il y a beaucoup de notes sur Internet et de réponses ici sur CV sur SVD et son fonctionnement.

Vladislavs Dovgalecs

SVD peut être considéré comme un algorithme de compression / apprentissage. C'est un décompresseur à compresseur linéaire. Une matrice M peut être représentée par la multiplication de SVD. S est le compresseur V détermine l’erreur que vous voudriez avoir (compression avec pertes) et D est le décompresseur. Si vous conservez toutes les valeurs diagonales de V, vous disposez d'un compresseur sans perte. Si vous commencez à jeter de petites valeurs singulières (en les mettant à zéro), vous ne pourrez pas reconstruire exactement la matrice initiale, mais resterez tout de même proches. Ici, le terme proche se mesure à la norme de Frobenius.

Cagdas Ozgenc

@ Cagdas, si vous faites cela, veuillez définir avec soin ce que vous prenez, "S", "V" et "D" comme étant mathématiquement. Je n'ai jamais vu les initiales surchargées dans la notation elle-même (qui contient les valeurs singulières, par exemple?). Cela semble être une source probable de confusion,

Glen_b

Savez-vous comment estimer l’ACP avec la maladie vésiculeuse du porc? Si vous le faites, pouvez-vous alors expliquer pourquoi vous pensez qu'il manque quelque chose à votre compréhension de la maladie vésiculeuse du porc? Voir ceci

Aksakal

Réponses:

Ecrivez le SVD de la matrice (réel, ) sous la forme où est , est la diagonale et est . En ce qui concerne les colonnes des matrices et , on peut écrire $X$ $n\times p$

X = U D V^{T}

$X = U D V^T$

U

$U$

n \times p

$n\times p$

D

$D$

p \times p

$p\times p$

V^{T}

$V^T$

p \times p

$p\times p$

U

$U$

V

$V$

X = \sum_{i = 1}^{p} d_{i} u_{i} v_{i}^{T}

$X=\sum_{i=1}^p d_i u_i v_i^T$ . Cela montre

écrit comme une somme de matrices

rang-1. À quoi ressemble une matrice de rang 1? Voyons:

Les lignes sont proportionnelles et les colonnes sont proportionnelles.

X

$X$

p

$p$

(\begin{matrix} 1 \\ 2 \\ 3 \end{matrix}) (\begin{matrix} 4 & 5 & 6 \end{matrix}) = (\begin{matrix} 4 & 5 & 6 \\ 8 & 10 & 12 \\ 12 & 15 & 18 \end{matrix})

$\begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix} \begin{pmatrix} 4 & 5 & 6 \end{pmatrix} = \begin{pmatrix} 4 & 5 & 6 \\ 8 & 10 & 12 \\ 12 & 15 & 18 \end{pmatrix}$

Pensez maintenant que contient les valeurs d'échelle de gris d'une image en noir et blanc, chaque entrée de la matrice représentant un pixel. Par exemple la photo suivante d'un babouin: $X$

Ensuite, lisez cette image dans R et récupérez la partie matrice de la structure résultante, en utilisant éventuellement la bibliothèque pixmap.

Si vous souhaitez un guide pas à pas sur la manière de reproduire les résultats, vous pouvez trouver le code ici .

Calculez le SVD:

baboon.svd  <-  svd(bab) # May take some time

$512 \times 512$ $512$ $512$ $1$ $20$

baboon.1  <-  sweep(baboon.svd$u[,1,drop=FALSE],2,baboon.svd$d[1],"*") %*%
                   t(baboon.svd$v[,1,drop=FALSE])

baboon.20 <-  sweep(baboon.svd$u[,1:20,drop=FALSE],2,baboon.svd$d[1:20],"*") %*%
                   t(baboon.svd$v[,1:20,drop=FALSE])

résultant en les deux images suivantes:

Sur la gauche, nous pouvons facilement voir les bandes verticales / horizontales dans l’image de rang 1.

$20$

Ce qui est assez intéressant: nous voyons les parties de l’image originale qui sont difficiles à représenter comme une superposition de lignes verticales / horizontales, principalement des poils en nez diagonaux et une certaine texture, ainsi que des yeux!

kjetil b halvorsen
la source

Je pense que vous vouliez parler de reconstruction de bas rang, pas de gamme basse. Ça ne fait rien. C'est une très bonne illustration (+1). C'est pourquoi il s'agit d'un décompresseur à compresseur linéaire. L'image est approximée avec des lignes. Si vous effectuez un autoencodeur similaire avec un réseau de neurones avec des fonctions d'activation linéaires, vous verrez qu'il autorise également les lignes avec une pente quelconque, non seulement les lignes verticales et horizontales, ce qui le rend légèrement plus puissant que la SVD.

Cagdas Ozgenc

X = U Σ V^{*}

$X = U \Sigma V^*$

n \times p

$n \times p$

X

$X$

U

$U$

n \times n

$n \times n$

Σ

$\Sigma$

n \times p

$n \times p$

V

$V$

p \times p

$p \times p$

Voir math.stackexchange.com/questions/92171/… pour d'autres exemples

kjetil b halvorsen

@ kjetil-b-halvorsen Je souhaiterais savoir en quoi la description serait modifiée si j'avais utilisé PCA pour refuser une application. Je vous serais reconnaissant de bien vouloir répondre à ma question ici stats.stackexchange.com/questions/412123/…

Dushyant Kumar Le

Observation intéressante @ CowboyTrader. Ma compréhension de l'apprentissage machine / réseau de neurones est assez limitée. Alors, je ne comprends pas que, si on a une seule image bruyante et qu’il n’ya rien d’autre sur lequel s’entraîner, comment le réseau de neurones fonctionnerait-il?

Dushyant Kumar le

$A$ $m \times n$ $m \geq n$ $v$ $A$

\begin{aligned} (1) & v_{1} = & \arg max_{v \in R^{n}} ‖ A v ‖_{2} \\ subject to ‖ v ‖_{2} = 1. \end{aligned}

$\begin{align} \tag{1}v_1 = \,\,& \arg \max_{v \in \mathbb R^n} \quad \| A v \|_2 \\ & \text{subject to } \, \|v\|_2 = 1. \end{align}$

v_{1}

$v_1$

A

$A$

\begin{aligned} v_{2} = & \arg max_{v \in R^{n}} ‖ A v ‖_{2} \\ subject to ⟨ v_{1}, v ⟩ = 0, \\ ‖ v ‖_{2} = 1. \end{aligned}

$\begin{align} v_2 = \,\,& \arg \max_{v \in \mathbb R^n} \quad \| A v \|_2 \\ & \text{subject to } \,\langle v_1, v \rangle = 0, \\ & \qquad \qquad \, \, \, \, \|v\|_2 = 1. \end{align}$

v_{1}, \dots, v_{n}

$v_1, \ldots, v_n$

R^{n}

$\mathbb R^n$

R^{n}

$\mathbb R^n$

A

$A$

Soit (donc quantifie le pouvoir explosif de dans la direction ). Supposons que les vecteurs unitaires soient définis de telle sorte que Les équations (2) peuvent être exprimées de manière concise en utilisant la notation matricielle sous la forme où est la matrice dont la ème colonne est , est la matrice dont e colonne est , et $\sigma_i = \|A v_i \|_2$ $\sigma_i$ $A$ $v_i$ $u_i$

\begin{matrix} (2) & A v_{i} = σ_{i} u_{i} for i = 1, \dots, n . \end{matrix}

$\tag{2} A v_i = \sigma_i u_i \quad \text{for } i = 1, \ldots, n.$

\begin{matrix} (3) & A V = U Σ, \end{matrix}

$\tag{3} A V = U \Sigma,$

V

$V$

n \times n

$n \times n$

i

$i$

v_{i}

$v_i$

U

$U$

m \times n

$m \times n$

i

$i$

u_{i}

$u_i$

Σ

$\Sigma$ est la matrice diagonale dont la ème entrée est . La matrice étant orthogonale, nous pouvons multiplier les deux côtés de (3) par pour obtenir Il peut sembler que nous ayons maintenant calculé la SVD de avec un effort presque nul. Aucune des étapes jusqu'à présent n'a été difficile. Cependant, il manque un élément crucial de la photo: nous ne savons pas encore que est orthogonal.

n \times n

$n \times n$

i

$i$

σ_{i}

$\sigma_i$

V

$V$

V^{T}

$V^T$

A = U Σ V^{T} .

$A = U \Sigma V^T.$

A

$A$

U

$U$

Voici le fait crucial, la pièce manquante: il s’avère que est orthogonal à : Je déclare que si ce n’était pas vrai, alors ne serait pas optimal pour le problème (1). En effet, si (4) n'était pas satisfait, alors il serait possible d' améliorer en le perturbant un peu dans la direction . $A v_1$ $A v_2$

\begin{matrix} (4) & ⟨ A v_{1}, A v_{2} ⟩ = 0. \end{matrix}

$\tag{4} \langle A v_1, A v_2 \rangle = 0.$ $v_1$

v_{1}

$v_1$

v_{2}

$v_2$

Supposons (pour une contradiction) que (4) n'est pas satisfait. Si est légèrement perturbé dans la direction orthogonale , la norme de ne change pas (ou du moins, le changement de la norme de est négligeable). Lorsque je marche à la surface de la Terre, ma distance par rapport au centre de la Terre ne change pas. Toutefois, lorsque est perturbé dans la direction , le vecteur est perturbée dans le non-orthogonal direction , et ainsi la modification de la norme est non négligeable . La norme de $v_1$ $v_2$ $v_1$ $v_1$ $v_1$ $v_2$ $A v_1$ $A v_2$ $A v_1$ $A v_1$ peut être augmenté d'un montant non négligeable. Cela signifie que n'est pas optimal pour le problème (1), ce qui est une contradiction. J'aime cet argument pour les raisons suivantes: 1) l'intuition est très claire; 2) l'intuition peut être convertie directement en une preuve rigoureuse. $v_1$

Un argument similaire montre que est orthogonal à et , et ainsi de suite. Les vecteurs sont deux à deux orthogonaux. Cela signifie que les vecteurs unitaires peuvent être choisis orthogonaux deux à deux, ce qui signifie que la matrice ci-dessus est une matrice orthogonale. Ceci termine notre découverte du SVD. $A v_3$ $A v_1$ $A v_2$ $A v_1, \ldots, A v_n$ $u_1, \ldots, u_n$ $U$

Pour convertir l'argument intuitif ci-dessus en une preuve rigoureuse, nous devons confronter le fait que si est perturbé dans la direction , le vecteur perturbé n'est pas vraiment un vecteur unitaire. (Sa norme est .) Pour obtenir une preuve rigoureuse, définissez Le vecteur est vraiment un vecteur unitaire. Mais comme vous pouvez facilement le constater, si (4) n’est pas satisfait, alors pour des valeurs suffisamment petites de nous avons (en supposant que le signe de $v_1$ $v_2$

{\tilde{v}}_{1} = v_{1} + ϵ v_{2}

$\tilde v_1 = v_1 + \epsilon v_2$

\sqrt{1 + ϵ^{2}}

$\sqrt{1 + \epsilon^2}$

{\bar{v}}_{1} (ϵ) = \sqrt{1 - ϵ^{2}} v_{1} + ϵ v_{2} .

$\bar v_1(\epsilon) = \sqrt{1 - \epsilon^2} v_1 + \epsilon v_2.$

{\bar{v}}_{1} (ϵ)

$\bar v_1(\epsilon)$

ϵ

$\epsilon$

f (ϵ) = ‖ A {\bar{v}}_{1} (ϵ) ‖_{2}^{2} > ‖ A v_{1} ‖_{2}^{2}

$f(\epsilon) = \| A \bar v_1(\epsilon) \|_2^2 > \| A v_1 \|_2^2$

ϵ

$\epsilon$ est choisi correctement). Pour montrer cela, vérifiez que . Cela signifie que n'est pas optimal pour le problème (1), ce qui est une contradiction.

f^{'} (0) \neq 0

$f'(0) \neq 0$

v_{1}

$v_1$

(Soit dit en passant, je vous recommande de lire l'explication de Qiaochu Yuan du SVD ici . En particulier, jetez un oeil à « lemme Key # 1 », qui est ce que nous avons discuté ci - dessus. Comme le dit Qiaochu, lemme clé # 1 est « le coeur technique décomposition en valeurs singulières ".)

petit o
la source

Mec prend une heure de ta journée et regarde cette conférence: https://www.youtube.com/watch?v=EokL7E6o1AE

Ce mec est super simple, il est important de ne rien oublier car tout finit bien. Même si cela peut sembler un peu lent au début, il essaie de cerner un point critique, ce qu’il fait!

Je vais résumer pour vous, plutôt que de simplement vous donner les trois matrices que tout le monde fait (parce que cela me confondait lorsque je lisais d'autres descriptions). D'où viennent ces matrices et pourquoi les mettons-nous comme cela? La conférence le cloue! Chaque matrice (toujours dans l'histoire de l'Everness) peut être construite à partir d'une matrice de base ayant les mêmes dimensions, puis la faire pivoter et l'étirer (c'est le théorème fondamental de l'algèbre linéaire). Chacune de ces trois matrices que l’on jette représente une matrice initiale (U), une matrice d’échelle (sigma) et une matrice de rotation (V).

La matrice de mise à l'échelle vous indique quels sont les vecteurs de rotation qui dominent, ce sont les valeurs singulières. La décomposition est résolue pour U, sigma et V.

Tim Johnsen
la source