Fonction objectif de l'ACP: quel est le lien entre maximiser la variance et minimiser l'erreur?

L'algorithme PCA peut être formulé en termes de matrice de corrélation (supposons que les données ont déjà été normalisées et que nous ne considérons que la projection sur le premier PC). La fonction objectif peut s'écrire: $X$

max_{w} (X w)^{T} (X w) s.t. w^{T} w = 1.

$\max_w (Xw)^T(Xw)\; \: \text{s.t.} \: \:w^Tw = 1.$

C'est très bien, et nous utilisons des multiplicateurs lagrangiens pour le résoudre, c'est-à-dire le réécrire comme:

max_{w} [(X w)^{T} (X w) - λ w^{T} w],

$\max_w [(Xw)^T(Xw) - \lambda w^Tw],$

ce qui équivaut à

max_{w} \frac{(X w)^{T} (X w)}{w^{T} w},

$\max_w \frac{ (Xw)^T(Xw) }{w^Tw},$

et donc ( voir ici sur Mathworld ) semble être égal à

max_{w} \sum_{i = 1}^{n} {(distance from point x_{i} to line w)}^{2} .

$\max_w \sum_{i=1}^n \text{(distance from point $x_i$ to line $w$)}^2.$

Mais cela dit de maximiser la distance entre le point et la ligne, et d'après ce que j'ai lu ici , c'est incorrect - ce devrait être $\min$ , pas $\max$ . Où est mon erreur?

Ou, quelqu'un peut-il me montrer le lien entre maximiser la variance dans l'espace projeté et minimiser la distance entre le point et la ligne?

pca optimization Cam.Davidson.Pilon
la source

Je pense que la distance minimale est utilisée pour répondre au critère d'orthogonalité pour les composants. Les points sont projetés dans les PC orthogonaux entre eux mais dans chaque composante successive la variance restante est maximisée.

Michael R. Chernick

Astuce: que se passe-t-il lorsque vous considérez d'abord la plus petite valeur propre, plutôt que la plus grande?

whuber

@whuber La plus petite valeur propre a probablement le PC qui est la solution à la fonction objectif finale. Mais ce PC ne maximise pas la fonction objectif d'origine.

Cam.Davidson.Pilon

Je ne sais pas trop ce que vous entendez par fonction d'objectif "finale" et "originale", Cam. PCA n'est pas (conceptuellement) un programme d'optimisation. Sa sortie est un ensemble de directions principales, pas seulement une. C'est un théorème mathématique (intéressant) que ces directions peuvent être trouvées en résolvant une séquence de programmes quadratiques contraints, mais ce n'est pas fondamental pour les concepts ou la pratique de l'ACP. Je suggère seulement qu'en se concentrant sur la plus petite valeur propre plutôt que sur la plus grande, vous pouvez concilier les deux idées de (1) minimiser les distances et (2) adopter une vue d'optimisation de l'ACP.

whuber

Ça va - votre réponse était la version sans erreur de ce que j'essayais de faire.

Cam.Davidson.Pilon

Réponses:

Soit une matrice de données centrée avec observations en lignes. Soit sa matrice de covariance. Soit un vecteur unitaire spécifiant un axe dans l'espace variable. Nous voulons que soit le premier axe principal. $\newcommand{\X}{\mathbf X}\X$ $n$ $\newcommand{\S}{\boldsymbol \Sigma}\S=\X^\top\X/(n-1)$ $\newcommand{\w}{\mathbf w}\w$ $\w$

Selon la première approche, le premier axe principal maximise la variance de la projection (variance de la première composante principale). Cette variance est donnée par le $\X \w$

V a r (X w) = w^{⊤} X^{⊤} X w / (n - 1) = w^{⊤} Σ w .

$\mathrm{Var}(\X\w)=\w^\top\X^\top \X \w/(n-1)=\w^\top\S\w.$

Selon la deuxième approche, le premier axe principal minimise l'erreur de reconstruction entre et sa reconstruction , c'est-à-dire la somme des distances au carré entre les points d'origine et leurs projections sur . Le carré de l'erreur de reconstruction est donné par $\X$ $\X\w\w^\top$ $\w$

\begin{aligned} ‖ X - X w w^{⊤} ‖^{2} & = t r ((X - X w w^{⊤}) (X - X w w^{⊤})^{⊤}) \\ = t r ((X - X w w^{⊤}) (X^{⊤} - w w^{⊤} X^{⊤})) \\ = t r (X X^{⊤}) - 2 t r (X w w^{⊤} X^{⊤}) + t r (X w w^{⊤} w w^{⊤} X^{⊤}) \\ = c o n s t - t r (X w w^{⊤} X^{⊤}) \\ = c o n s t - t r (w^{⊤} X^{⊤} X w) \\ = c o n s t - c o n s t \cdot w^{⊤} Σ w . \end{aligned}

$\begin{align}\newcommand{\tr}{\mathrm{tr}} \|\X-\X\w\w^\top\|^2 &=\tr\left((\X-\X\w\w^\top)(\X-\X\w\w^\top)^\top\right) \\ &=\tr\left((\X-\X\w\w^\top)(\X^\top-\w\w^\top\X^\top)\right) \\ &=\tr(\X\X^\top)-2\tr(\X\w\w^\top\X^\top)+\tr(\X\w\w^\top\w\w^\top\X^\top) \\ &=\mathrm{const}-\tr(\X\w\w^\top\X^\top) \\ &=\mathrm{const}-\tr(\w^\top\X^\top\X\w) \\ &=\mathrm{const} - \mathrm{const} \cdot \w^\top \S \w. \end{align}$

Remarquez le signe moins avant le terme principal. Pour cette raison, minimiser l'erreur de reconstruction revient à maximiser , qui est la variance. Ainsi, minimiser l'erreur de reconstruction équivaut à maximiser la variance; les deux formulations donnent le même . $\w^\top \S \w$ $\w$

l'amibe dit de réintégrer Monica
la source

Quelque chose que j'ai remarqué, n'est-ce pas une fonction convexe (En ce qui concerne as is PSD? Comment se fait-il que nous essayions de le maximiser?

w^{T} Σ w

${w}^{T} \Sigma w$

w

$w$

Σ

$\Sigma$

Royi

@amoeba pouvez-vous expliquer comment vous passez de tr () à const dans la dernière étape?

alberto

@alberto Ce qui se trouve à l'intérieur de la trace est un nombre (matrice 1x1); une trace d'un nombre est ce nombre lui-même, de sorte que la trace peut être supprimée. La constante apparaît parce que est égal à , donc il y a ce facteur .

Σ

$\Sigma$

X^{⊤} X / n

$X^\top X/n$

1 / n

$1/n$

amibe dit Réintégrer Monica le

@Leullame Le calcul tiendra compte textuellement de s'il s'agit d'une matrice avec des colonnes orthonormées. Vous avez besoin de pour passer de la ligne # 3 à la ligne # 4. Si la matrice a des colonnes orthonormées, alors en effet sera une projection de sur le sous-espace couvert par les colonnes de (ici est un vecteur ligne).

W

$W$

W^{⊤} W = I

$W^\top W = I$

W

$W$

x W W^{⊤}

$xWW^\top$

x

$x$

W

$W$

x

$x$

amoeba dit Reinstate Monica

@ DanielLópez Eh bien, nous recherchons un sous-espace unidimensionnel minimisant l'erreur de reconstruction. Un sous-espace unidimensionnel peut être défini par un vecteur de norme unitaire pointant dans sa direction, ce qui est considéré comme . Il a la norme d'unité par construction.

w

$w$

amoeba dit Reinstate Monica