[PYTHON] Versuchen Sie, die Daimyo-Matrix durch einen Singularwert zu zerlegen

Einführung

Die lineare Algebra hat eine Operation, die als Singularitätszerlegung bezeichnet wird. Es ist ein Prozess, der eine Matrix in singuläre Werte zerlegt und eine Matrix, die sie erzeugt. Diese Zerlegung ist ein reversibler Prozess, aber die ursprüngliche Matrix kann angenähert werden, indem nur die große Singularität genommen und die kleine Singularität ignoriert wird. In den letzten Jahren wurde die Informationskomprimierung unter Verwendung dieser Eigenschaft an verschiedenen Stellen aktiv eingesetzt. In meiner unmittelbaren Umgebung spielt die Singularitätszerlegung eine zentrale Rolle bei der Approximation von Quantenzuständen mit Tensornetzwerken.

Der Zweck dieses Papiers ist es, anhand einer einfachen Matrix herauszufinden, welche Art der Verarbeitung der Singularwertzerlegung ist, und zu erkennen, dass "ich sehe, es ist Informationskomprimierung".

Der Code ist unten.

https://github.com/kaityo256/daimyo_svd

Wenn Sie Jupyter Notebook in Google Colab öffnen möchten, klicken Sie hier (https://colab.research.google.com/github/kaityo256/daimyo_svd/blob/main/daimyo_svd.ipynb).

Versuchen Sie, einzelne Werte zu zerlegen

Lassen Sie uns zunächst bestätigen, dass Informationen durch Singularwertzerlegung komprimiert werden können. Im Folgenden wird davon ausgegangen, dass es in Google Colab ausgeführt wird. Lesen Sie bei der Ausführung in anderen Umgebungen die entsprechenden Informationen, z. B. wie der Pfad zur Schriftart angegeben wird.

Vorbereitung der Zielmatrix

Importieren wir zunächst das, was Sie benötigen.

from PIL import Image, ImageDraw, ImageFont
import numpy as np
from scipy import linalg

Installieren Sie als Nächstes die japanische Schriftart.

!apt-get -y install fonts-ipafont-gothic

Nach erfolgreicher Installation erstellen wir ein Schriftobjekt für "ImageFont".

fpath='/usr/share/fonts/opentype/ipafont-gothic/ipagp.ttf'
fontsize = 50
font = ImageFont.truetype(fpath, fontsize)

Schreiben Sie "Daimyo-Prozession" in Schwarz auf weißem Hintergrund.

LX = 200
LY = fontsize
img  = Image.new('L', (LX,LY),color=255)
draw = ImageDraw.Draw(img)
draw.text((0,0), "Daimyo-Prozession", fill=0, font=font)
img

Es war ein Erfolg, dass die "Daimyo-Prozession" so gezeigt wurde.

Lassen Sie uns nun die Matrix in Form eines NumPy-Arrays aus dem gezeichneten Bild erhalten. Essen Sie einfach img.getdata () on np.array, aber das würde zu einem eindimensionalen Array führen. Verwenden Sie also reshape, um eine Matrix zu erstellen.

data = np.array(img.getdata()).reshape((LY,LX))

Diese "Daten" sind die ursprüngliche Matrix. Das Matrixelement hat einen Wert von 0 bis 255 und repräsentiert die Helligkeit des Pixels.

Umgekehrt zeigen wir die Matrix als Bild an.

Image.fromarray(np.uint8(data))

Wenn die folgende Anzeige angezeigt wird, ist sie erfolgreich.

Lassen Sie uns hier auch den Rang dieser Matrix überprüfen. Sie können dies mit np.linalg.matrix_rank überprüfen.

np.linalg.matrix_rank(data) # => 47

Der maximale Rang der Matrix ist min (Zeile, Spalte). Da "Daten" eine 50 x 200-Matrix ist, beträgt der maximale Rang 50, aber aufgrund der Ränder über und unter der "Daimyo-Matrix" sinkt der Rang etwas auf 47. Lassen Sie uns dies mit einer Matrix mit niedrigerem Rang approximieren, bei der es sich um eine Komprimierung durch Singularwertzerlegung handelt.

Singularitätszerlegung und -komprimierung

Zerlegen wir nun die Matrix "Daten" in singuläre Werte. Es ist ein Schuss mit scipy.linalg.svd.

u, s, v = linalg.svd(data)

Lassen Sie uns auch jede Form überprüfen.

print(f"u: {u.shape}")
print(f"s: {s.shape}")
print(f"v: {v.shape}")

Das Ergebnis sieht so aus.

u: (50, 50)
s: (50,)
v: (200, 200)

"u" ist eine 50x50-Quadratmatrix und "v" ist eine 200x200-Quadratmatrix. Beachten Sie, dass s mathematisch eine Diagonalmatrix von 50 x 200 ist, aber scipy.linalg.svd ein eindimensionales Array zurückgibt, da es ohnehin nur diagonale Komponenten enthält. Dieses s ist ein singulärer Wert, alle sind nicht negative reelle Zahlen und scipy.linalg.svd ist in absteigender Reihenfolge angeordnet. "u" und "v" sind auch in der Reihenfolge angeordnet, die dem Singularwert entspricht.

Nachdem wir nun die Singularitätszerlegung haben, wollen wir eine Annäherung an die ursprüngliche Matrix mit niedrigem Rang vornehmen. Wir werden nur r Singularwerte von den größten belassen. Entsprechend "ur", das "r" -Spaltenvektoren von links von "u" nimmt, Sei "vr" eine Matrix, die "r" Zeilenvektoren von der Spitze von "v" nimmt. Die Spalten sind 50 Zeilen und r Spalten und r Zeilen bzw. 200 Spalten. Verwenden Sie für singuläre Werte eine diagonale Matrix aus r Zeilen und r Spalten. Da es sich um eine nicht negative reelle Zahl handelt, kann sie eine Quadratwurzel bilden. Sei dies "sr", sei "ur @ sr" "A" und "sr @ vr" sei "B".

Der folgende Code implementiert die obige Operation so wie sie ist. Hier wird "r = 10" gesetzt.

r = 10
ur = u[:, :r]
sr = np.diag(np.sqrt(s[:r]))
vr = v[:r, :]
A = ur @ sr
B = sr @ vr

Da A eine Matrix mit 50 Zeilen und r Spalten ist und B eine Matrix mit r Zeilen und 200 Spalten ist, ist das Produkt dasselbe wie die ursprüngliche Matrix "Daten", die 50 Zeilen und 200 Spalten umfasst.

print(f"A: {A.shape}")
print(f"B: {B.shape}")
print(f"AB: {(A @ B).shape}")

Ausführungsergebnis ↓

A: (50, 10)
B: (10, 200)
AB: (50, 200)

Während der Rang von "Daten" 47 war, hinterlässt "A @ B" nur 10 Singularwerte, so dass es sich um eine Matrix mit Rang 10 handelt.

np.linalg.matrix_rank(A @ B) # => 10

Sicher ist der Rang 10. Aus diesem Grund wird es als Annäherung mit niedrigem Rang bezeichnet.

Nun wurde die Matrix "Daten" durch zwei Matrizen "A" und "B" angenähert. Mal sehen, wie stark die Daten komprimiert wurden. Die Anzahl der Elemente in der Matrix kann mit "Größe" erhalten werden.

print((A.size + B.size)/data.size) # => 0.25

Wenn Sie 10 einzelne Werte belassen, wissen Sie, dass die Daten auf 25% komprimiert wurden.

Datenwiederherstellung

Lassen Sie uns nun das Bild erneut betrachten, um zu sehen, wie viele Informationen durch die Annäherung an einen niedrigen Rang verloren gegangen sind. Lassen Sie uns die durch "A @ B" angenäherten Daten im Bild wiederherstellen. Die Pixeldaten waren ursprünglich ein Wert von 0 bis 255, werden jedoch von "numpy.clip" von 0 auf 255 verschoben, da sie über die Näherung hinausgehen und das Bild seltsam wird.

b = np.asarray(A @ B)
b = np.clip(b, 0, 255)
Image.fromarray(np.uint8(b))

Es wurde so restauriert.

Was ist, wenn wir eine Annäherung an einen niedrigeren Rang vornehmen? Setzen wir r = 3.

r = 3
ur = u[:, :r]
sr = np.diag(np.sqrt(s[:r]))
vr = v[:r, :]
A = ur @ sr
B = sr @ vr
b = np.asarray(A @ B)
b = np.clip(b, 0, 255)
Image.fromarray(np.uint8(b))

Das Ergebnis sieht so aus.

Ich bin nicht gut in diagonalen Linien.

Zusammenfassung

Um zu bestätigen, wie die Singularwertzerlegung für die Informationskomprimierung verwendet wird, stellen Sie sich das als "Daimyo-Matrix" geschriebene Bild als Matrix, Singularwertzerlegung, Erstellen einer approximierten Matrix mit niedrigem Rang und Informationskomprimierungsrate vor. Ich habe die Daten überprüft und versucht, sie wiederherzustellen. Ich hoffe, Sie probieren diesen Code aus und denken: "Ich verstehe, es ist eine Annäherung mit niedrigem Rang."

Ergänzungsmaterial

Ich möchte die mathematischen Aspekte der obigen Operationen ergänzen.

Was ist ein singulärer Wert?

Betrachten Sie die folgende Zerlegung der quadratischen Matrix $ A $.

$ P $ ist jedoch eine reguläre Matrix und $ D $ ist eine diagonale Matrix. Wenn eine solche Zerlegung möglich ist, wird $ A $ als diagonal bezeichnet, $ D $ ist ein diagonales Element, bei dem die Eigenwerte von $ A $ angeordnet sind, und $ P $ ist der Eigenvektor von $ A $ als Spaltenvektor. Es wird nebeneinander angeordnet.

Ich habe auch geschrieben, dass die Eigenwerte und Eigenvektoren einer Matrix in [Warum lineare Algebra lernen] wichtig sind (https://qiita.com/kaityo256/items/872a2b2fdf977c0e3fbb). Die Art der Matrix wird durch die Eigenwerte und Eigenvektoren bestimmt. Und die Eigenvektoren sind für die Eigenschaften der ursprünglichen Matrix in absteigender Reihenfolge des Absolutwerts der Eigenwerte verantwortlich. Beispielsweise repräsentiert ein Eigenvektor mit dem größten absoluten Eigenwert den Gleichgewichtszustand, wenn die Matrix ein Zeitentwicklungsoperator ist, und den Grundzustand, wenn die Matrix den zeitunabhängigen Hamilton-Operator der Quantenmechanik darstellt. Wenn die Matrix eine Markov-Übergangsmatrix ist, ist der Eigenwert-Absolutwert mit dem maximalen Absolutwert 1, und der Eigenwert mit dem zweitgrößten Eigenwert bestimmt die Relaxationsrate zum stationären Zustand [^ markov].

[^ markov]: Ich konnte die Beziehung zwischen der Markov-Übergangsmatrix und der linearen Algebra seit mehreren Jahren nicht mehr schreiben, in der Hoffnung, sie eines Tages schreiben zu können. Wenn es eine starke Bitte zum "Schreiben!" Gibt, kann ich möglicherweise mein Bestes geben.

Nun können die Eigenwerte und Eigenvektoren einer Matrix nur in einer quadratischen Matrix definiert werden. Es gibt jedoch Zeiten, in denen Sie etwas Ähnliches wie eine allgemeine rechteckige Matrix tun möchten. In solchen Fällen wird eine Singularitätszerlegung verwendet.

Betrachten Sie die Matrix $ X $ in der Spalte $ m $ Zeile $ n $ ($ m <n $). Die Singularitätszerlegung ist die Zerlegung der Matrix $ X $ wie folgt.

$ U $ ist jedoch eine quadratische Matrix mit m Zeilen und m Spalten, und $ V $ ist eine quadratische Matrix mit n Zeilen und n Spalten, die beide einheitliche Matrizen sind. $ V ^ \ dagger $ ist eine kontingente Matrix von $ V $. $ \ Sigma $ ist eine diagonale Matrix aus $ m $ Zeilen und $ n $ Spalten, und diagonale Elemente werden als $ X $ Singularitäten bezeichnet. Der Singularwert ist eine nicht negative reelle Zahl, und die Anzahl der Elemente ist die mit den wenigsten Zeilen und Spalten von $ X $ und $ m $, wenn $ m <n $. Der Einfachheit halber werden $ \ Sigma $ in absteigender Reihenfolge der Singularität von oben aufgelistet.

Was ist Rang

Der Rang (die Reihenfolge) einer Matrix ist "die Anzahl linear unabhängiger Vektoren, wenn die Zeilenvektoren als ausgerichtet betrachtet werden" oder "die Anzahl linear unabhängiger Vektoren, wenn die Spaltenvektoren als ausgerichtet betrachtet werden". ist. Beide Definitionen stimmen überein. In einer rechteckigen Matrix mit $ m $ Zeilen und $ n $ Spalten ($ m <n $) gibt es $ n $ Spaltenvektoren mit der Dimension $ m $. Da ein $ m $ -Dimensionsraum erstellt werden kann, wenn $ m $ linear unabhängige Vektoren vorhanden sind, darf ein linear unabhängiger Spaltenvektor $ m $ nicht überschreiten. Gleiches gilt für $ m> n $. Aus dem oben Gesagten ergibt sich, dass der Rang der Matrix in der Spalte $ m $ Zeile $ n $ maximal $ \ min (m, n) $ beträgt. Intuitiv können Sie sehen, dass die Matrix umso weniger "wesentliche Informationsmenge" enthält, je mehr linear abhängige Vektoren die Matrix enthält.

Niedrige Rangnäherung

Wenn nun gemäß der Definition des Matrixprodukts die Matrix der Spalte $ m $ row $ r $ und die Matrix der Spalte $ r $ row $ n $ multipliziert werden, werden die mittleren $ r $ Beine zerquetscht und $ m $ row $ Es wird eine Matrix von n $ Spalten sein. Wenn Sie von hier aus $ r $ kleiner nehmen, kann die Matrix der Spalte $ m $ Zeile $ n $ durch die Matrix der Spalte $ m $ Zeile $ r $ und die Matrix der Spalte $ r $ Zeile $ n $ angenähert werden. Ich kann.

Der Rang der Matrix wird durch die kleinere der Zeilen und Spalten bestimmt. Wenn also $ r <m <n $ ist, haben sowohl die Spaltenmatrix $ m $ row $ r $ als auch die Spalte $ r $ row $ n $ einen maximalen Rang von $ r $. Das Multiplizieren einer Matrix von Rängen $ r $ erhöht den Rang nicht, daher ist der Rang der $ m $ Zeile $ n $ Spalte von $ AB $ auch $ r $.

Auf diese Weise ist es bei der Approximation einer Matrix durch das Produkt einer anderen kleinen Matrix eine Approximation mit niedrigem Rang, die eine Matrix mit einem niedrigeren Rang als die ursprüngliche Matrix approximiert. Es gibt verschiedene Möglichkeiten, eine so kleine Matrix zu erstellen, aber die beste Annäherung im Sinne der Frobenius-Norm ist die Annäherung unter Verwendung der Singularitätszerlegung.

Nun die Singularwertzerlegung der Matrix $ X $ in der Spalte $ m $ Zeile $ n $

Nehmen wir an, Sie bekommen. $ U $ und $ V $ sind quadratische Matrizen der Spalte $ m $ row $ m $ und der Spalte $ n $ row $ n $, die beide einheitliche Matrizen sind. $ V ^ \ dagger $ ist eine kontingente Matrix von $ V $ (transloziert, um ein komplexes Konjugat aufzunehmen). $ \ Sigma $ ist eine diagonale Matrix aus $ m $ Zeilen und $ n $ Spalten, wobei einzelne Werte auf den diagonalen Elementen aufgereiht sind. Ordnen Sie sie zu diesem Zeitpunkt in absteigender Reihenfolge von oben an (entscheiden Sie, dass auch $ U $ und $ V $ übereinstimmen).

Lassen Sie uns nun eine Annäherung mit niedrigem Rang unter Verwendung von nur $ r $ singulärer Werte vornehmen. Dies verwendet nur den quadratischen Matrixteil von $ r $ row $ column $ oben links von $ \ Sigma $, $ r $ column vectors von links und $ V ^ \ dagger $ row vector von oben. Es ist eine Form, die sich der ursprünglichen Matrix von $ r $ annähert. Da der Singularwert eine nicht negative reelle Zahl ist und $ \ Sigma $ eine diagonale Matrix ist, kann er von $ \ Sigma = \ sqrt {\ Sigma} \ sqrt {\ Sigma} $ getrennt werden. Kombinieren wir dies mit einer von $ U $ abgeleiteten Matrix und einer von $ V ^ \ dagger $ abgeleiteten Matrix. In der Abbildung sieht es so aus.

Von Oben,

Bekommen Somit wird die $ m $ Zeile $ n $ Spaltenmatrix $ X $ durch Singularitätszerlegung zur $ m $ Zeile $ r $ Spaltenmatrix $ A $ und zur $ r $ Zeile $ n $ Spaltenmatrix $ B $. Ich konnte es als Produkt annähern. Der Rang der ursprünglichen Matrix beträgt bis zu $ \ min (m, n) $, aber der Rang der so angenäherten Matrix beträgt bis zu $ r $. Die ursprünglichen $ m * n $ Matrixelemente sind jetzt $ r * (m + n) $. Wenn $ r $ klein ist, können Sie sehen, dass die Informationen komprimiert sind.