Efficient Coding

• sparse code / representation: Repräsentation, bei der nur wenige Komponenten ≠ 0 sind

• xSC = Wx = Vxwht

  • finde W / V so, dass Anzahl der Nullkomponenten in xSC maximiert wird

• liefert ähnliche Ergebnisse wie ICA

  • je sparser die Repräsentation, desto höher die Kurtosis

• lineare Version selten verwendet, da nichtlineare Implementierungen i.Allg. effizienter sind und (vgl. mit ICA) kompaktere Repräsentationen liefern

• Minimierungsproblem: E = -E(preserve information) - λE(sparseness)

• E(preserve information):

  • mittlerer Rekonstruktionsfehler

  • E_pi = - || W^-1 xSC - x||^2

• E(sparseness):

  • bevorzuge kleine Werte für die Komponenten von xSC

  • E_s = - sum(S(xSCi / σ))

  • σ: Skalierungsfaktor, S(x) z.B. |x|, log(1+x^2),…

• Ziel: lerne Repräsentation xSC und Basisfunktionen (Zeilen von W^-1)

• => Optimierungsproblem: min_W^-1 (min_xSC (E))

• geschachteltes Optimierungsproblem (hochgradig nichtkonvex, schwierig das globale Optimum zu finden)

  • Lösug z B mit SPARSENET-Algorithmus

• Rekonstruktion W^-1 x_SC wird durch lineare Transformation erhalten, aber die Repräsentation xSC ist (i.Allg.) nicht linear

  • für jeden neuen Datenpunkt wird für Berechnung von xSC wieder minimiert

• Unterschied zu PCA und ICA:

  • nichtlinear

  • PCA / ICA: gefundene Transformation kann einfach auf jeden neuen Datenpunkt angewandt werden; SC: Lernprozess für jeden neuen Datenpunkt durchgeführt werden

• Menge der gefundenen Basisfunktionen kann over-complete sein

  • Anzahl höher als Dimension des Input Space

• Basisfunktionen müssen nicht orthogonal sein (wie bei PCA)

• originaler Algorithmus zur Lüsung des SC Problems

• für jeden einzelnen Vektor x, minimiere E bzgl der Koeffizienten xSC (starte mit zufälligen Basisfunktionen)

  • Koeffizienten wechseln für jedes x

• mittle E über z.B. 100 Bilder, dann ändere die Basisfunktionen (im gleichen Optimierungsprozess)

• x_RP = R x

• verwandt mit Compressive Sensing

• R: MxN-Matrix (M<N)

  • zufällige Gaussian Matrix mit Zeilen der Länge 1

• wenn x und R bestimmte Bedingungen erfüllen, enthält x_RP fast gesamte Information aus x

  • x muss sparse sein

• weiteres Kriterium: wenn x k-sparse ist, brauchen wir i.d.R.

  • M≥cklog(N/k), wobei c kleine Konstante

  • -> für sehr große N brauchen wir deutlich weniger als N features (M<<N)

SIgnal ist k-sparse, wenn es eine Basis gibt, in der die Repräsentation des Signals nur k<N nicht-Null-Komponenten hat

• Compressive Sensing: versuche, x aus xRP zu rekonstruieren

  • dafür muss ein unterbestimmtes LGS gelöst werden (M Gleichungen, N unbekannte)

• für Feature Extraction: ausreichend zu wissen, dass xRP gesamte Information aus x enthält

  • mit geeigneter Matrix R reicht es aus zu wissen, dass x sparse ist

• Problem: durch RP erhaltene Merkmale sind nicht notwendigerweise gut

  • können es aber sein (v.a. wenn x zuvor in geeigneter Basis repräsentiert ist)

• Voraussetzung: f: Ω->R^2 Bildfunktion

• intrinsische Dimension:

  a) i0D: f(u,v) = c für alls (u,v) (konstant)

  b) i1D: f(u,v) = g(au+bv)

  c) i2D: f variiert entlang allen Richtungen

• Problemstellung: suche y=F(x) sodass y=0<=>x i0D oder i1D

  • x: Vektor mit allen Pixelwerten f(u,v) in Ω

  • Transformation F heißt i2D-Transformation

• Bilder werden vollständig durch die i2D-Regionen beschrieben

  • i2D-Transformationen können so bestimmt werden, dass x ≈ G(y) (Rekonstruktion)

• lineare Transformationen können keine i2D-Transformationen sein

  • => lineare Transformationen können nicht alle i0D-/i1D-Eingaben ohne Informationsverlust auf 0 abbilden

• i0D-/i1D-Regionen treten sehr häufig in Bildern auf

  • i2D-Transformationen produzieren höheren Grad an Sparsity als lineare Transformationen