Die objektive Funktion der Hauptkomponentenanalyse (PCA) ist die Minimierung des Rekonstruktionsfehlers in der L2-Norm (siehe Abschnitt 2.12 hier) . Eine andere Ansicht versucht, die Varianz bei der Projektion zu maximieren. Wir haben auch hier einen ausgezeichneten Beitrag: Was ist die objektive Funktion der PCA? ? ).
Meine Frage ist, dass die PCA-Optimierung konvex ist? (Ich habe hier einige Diskussionen gefunden , aber ich wünschte, jemand könnte hier im Lebenslauf einen netten Beweis erbringen).
machine-learning
pca
optimization
convex
Haitao Du
quelle
quelle
Antworten:
Nein, die üblichen Formulierungen von PCA sind keine konvexen Probleme. Sie können jedoch in ein konvexes Optimierungsproblem umgewandelt werden.
Die Einsicht und der Spaß daran besteht darin, die Abfolge der Transformationen zu verfolgen und zu visualisieren, anstatt nur die Antwort zu erhalten: Sie liegt in der Reise, nicht im Ziel. Die Hauptschritte auf diesem Weg sind
Erhalten Sie einen einfachen Ausdruck für die Zielfunktion.
Vergrößern Sie seine nicht konvexe Domäne in eine solche.
Ändern Sie das nicht konvexe Ziel in eines, das offensichtlich die Punkte, an denen es seine optimalen Werte erreicht, nicht verändert.
Wenn Sie genau hinschauen, können Sie die SVD- und Lagrange-Multiplikatoren lauern sehen - aber sie sind nur eine Nebenschau, da für landschaftliches Interesse, und ich werde sie nicht weiter kommentieren.
Die standardmäßige varianzmaximierende Formulierung von PCA (oder zumindest dessen Schlüsselschritt) ist
wobei die Matrix A eine symmetrische, positiv-semidefinite Matrix ist, die aus den Daten aufgebaut ist (üblicherweise ihre Summe aus Quadraten und Produktmatrix, ihre Kovarianzmatrix oder ihre Korrelationsmatrix).n × n EIN
(Entsprechend können wir versuchen, das nicht beschränkte Ziel zu maximieren . Dies ist nicht nur ein unangenehmerer Ausdruck - es ist keine quadratische Funktion mehr -, sondern die grafische Darstellung von Sonderfällen zeigt schnell, dass es keine konvexe Funktion ist Normalerweise beobachtet man, dass diese Funktion bei Neuskalierungen x → λ x invariant ist und reduziert sie dann auf die eingeschränkte Formulierung ( ∗ ) .)x′A x / x′x x → λ x ( ∗ )
Jedes Optimierungsproblem kann abstrakt formuliert werden als
Denken Sie daran, dass ein Optimierungsproblem konvex ist, wenn es zwei separate Eigenschaften aufweist:
Die Domäne ist konvex.X⊂ Rn Dies kann auf viele Arten formuliert werden. Eine ist, dass, wann immer und y ∈ X und 0 ≤ λ ≤ 1 , λ x + ( 1 - λ ) y ∈x ∈ X y∈ X 0≤λ≤1 auch. Geometrisch: wenn zwei Endpunkte eines Liniensegments liegen in X , das gesamte Segment liegt in X .λx+(1−λ)y∈X X X
Die Funktion ist konvex.f Dies kann auch auf viele Arten formuliert werden. Einer ist , dass , wenn und y ∈ X und 0 ≤ λ ≤ 1 , f ( λ x + ( 1 - λ ) y ) ≥ λ f ( x ) + ( 1 - λ ) f ( y ) . (Wir brauchten Xx∈X y∈X 0≤λ≤1
Der Archetyp einer konvexen Funktion ist lokal überall parabolisch mit nicht positivem Leitkoeffizienten: Auf jedem Liniensegment kann er in der Form y → a y 2 + ausgedrückt werden mit a ≤ 0 .y→ay2+by+c a≤0.
Eine Schwierigkeit bei ist, dass X die Einheitskugel S n - 1 ⊂ R n ist , die entschieden nicht konvex ist.(∗) X Sn−1⊂Rn Wir können dieses Problem jedoch ändern, indem wir kleinere Vektoren einbeziehen. Das liegt daran, dass wenn wir mit einem Faktor λ skalieren , f mit λ 2 multipliziert wird . Wenn 0 < x ' x < 1 ist , können wir skalierenx λ f λ2 0<x′x<1 durch Multiplizieren mit λ = 1 / √ auf Einheitslängex , wodurchErhöhungfaber innerhalb der Einheitskugel bleibtDn={x∈ R n|x'x≤1}. Lasst uns also(∗)umformulierenalsλ=1/x′x−−−√>1 f Dn={x∈Rn∣x′x≤1} (∗)
Seine Domäne ist was eindeutig konvex ist, also sind wir auf halber Strecke. Es bleibt die Konvexität des Graphen von f zu berücksichtigen .X=Dn f
Ein guter Weg, um über das Problem nachzudenken - auch wenn Sie nicht vorhaben, die entsprechenden Berechnungen durchzuführen - ist der Spektralsatz.(∗∗) Es heißt, dass man mittels einer orthogonalen Transformation mindestens eine Basis von R n finden kann, in der A diagonal ist:P Rn A
wobei alle nicht diagonalen Einträge von Null sind. Eine solche Wahl von P kann so verstanden werden, dass sie überhaupt nichts an A ändert, sondern nur die Art und Weise, wie Sie es beschreiben : Wenn Sie Ihren Standpunkt drehen, werden die Achsen der Ebenenhyperseiten der Funktion x → x ′ A x (welche waren immer Ellipsoide) mit den Koordinatenachsen ausgerichtet.Σ P A x→x′Ax
SinceA is positive-semidefinite, all the diagonal entries of Σ must be non-negative. We may further permute the axes (which is just another orthogonal transformation, and therefore can be absorbed into P ) to assure that
If we letx=P′y be the new coordinates x (entailing y=Px ), the function f is
Diese Funktion ist definitiv nicht konvex! Sein Graph sieht aus wie ein Teil eines Hyperparaboloids: An jedem Punkt im Inneren von führt die Tatsache, dass alle σ i nicht negativ sind, dazu, dass es sich eher nach oben als nach unten kräuselt .X σi
Allerdings können wir uns wenden in ein konvexes Problem mit einer sehr nützlicher Technik.(∗∗) Das Wissen , dass die maximal auftreten wird , wo , lassen Sie sich die Konstante subtrahiert σ 1 aus F , zumindest für die Punkte an der Grenze von X . Dadurch werden die Positionen von Punkten auf der Grenze, an denen f optimiert wird, nicht geändert , da alle Werte von f auf der Grenze um denselben Wert σ 1 gesenkt werden . Dies schlägt vor, die Funktion zu untersuchenx′x=1 σ1 f X f f σ1
This indeed subtracts the constantσ1 from f at boundary points, and subtracts smaller values at interior points. This will assure that g , compared to f , has no new global maxima on the interior of X .
Let's examine what has happened with this sleight-of-hand of replacing−σ1 by −σ1y′y . Because P is orthogonal, y′y=x′x . (That's practically the definition of an orthogonal transformation.) Therefore, in terms of the x coordinates, g can be written
Becauseσ1≥σi for all i , each of the coefficients is zero or negative. Consequently, (a) g is convex and (b) g is optimized when x2=x3=⋯=xn=0 . (x′x=1 then implies x1=±1 and the optimum is attained when y=P(±1,0,…,0)′ , which is--up to sign--the first column of P .)
Let's recapitulate the logic. Becauseg is optimized on the boundary ∂Dn=Sn−1 where y′y=1 , because f differs from g merely by the constant σ1 on that boundary, and because the values of g are even closer to the values of f on the interior of Dn , the maxima of f must coincide with the maxima of g .
quelle
No.
Rankk PCA of matrix M can be formulated as
(∥⋅∥F is Frobenius norm). For derivation see Eckart-Young theorem.
Though the norm is convex, the set over which it is optimized is nonconvex.
A convex relaxation of PCA's problem is called Convex Low Rank Approximation
(∥⋅∥∗ is nuclear norm. it's convex relaxation of rank - just like ∥⋅∥1 is convex relaxation of number of nonzero elements for vectors)
You can see Statistical Learning with Sparsity, ch 6 (matrix decompositions) for details.
If you're interested in more general problems and how they relate to convexity, see Generalized Low Rank Models.
quelle
Disclaimer: The previous answers do a pretty good job of explaining how PCA in its original formulation is non-convex but can be converted to a convex optimization problem. My answer is only meant for those poor souls (such as me) who are not so familiar with the jargon of Unit Spheres and SVDs - which is, btw, good to know.
My source is this lecture notes by Prof. Tibshirani
For an optimization problem to be solved with convex optimization techniques, there are two prerequisites.
Most formulations of PCA involve a constraint on the rank of a matrix.
In these type of PCA formulations, condition 2 is violated. Because, the constraint thatrank(X)=k, is not convex. For example, let J11 , J22 be 2 × 2 zero matrices with a single 1 in the upper left corner and lower
right corner respectively. Then, each of these have rank 1, but their average has rank 2.
quelle