[PYTHON] Ableitung und Implementierung von Aktualisierungsgleichungen für die nicht negative Tensorfaktorzerlegung
Code, den ich geschrieben habe
Es ist ein kindisches Ergebnis, aber ich mache Code auf Github veröffentlichen.
Verweise
- [1] Hirokazu Kameoka: Einführung in die Zerlegung nicht negativer Matrixfaktoren - mit akustischer Signalverarbeitung als Subjekt - (Sie können NMF visuell verstehen)
- [2] Hiroshi Sawada: Grundlagen der nicht-negativen Matrixfaktor-Zerlegung NMF und ihre Anwendung auf die Daten- / Signalanalyse (Leicht verständlicher NMF-Kommentarartikel)
- [3] Fortsetzung / Leicht verständliche Mustererkennung - Einführung in das Lernen ohne Lehrer - (Vielen Dank, dass Sie die Formel abgeleitet haben)
- [4] Tatsufumi Matsubayashi et al.: Analyse der Markenauswahl im Kaufverhalten unter Verwendung einer nicht negativen Tensorfaktorzerlegung (Es beschreibt, wie NTF für tatsächliche Daten verwendet wird.)
- [5] Koh Takeuchi et al.: Non-negative Multiple Tensor Factorization (Obwohl es sich um ein erweitertes NTF-Papier handelt, ist es auch nützlich, um NTF zu verstehen.)
Die Literatur [1,2,4,5] ist derzeit kostenlos im Internet verfügbar, daher wird sie besonders für diejenigen empfohlen, die arm sind wie sie selbst (diejenigen, die keine Papiere frei herunterladen können). Insbesondere für diejenigen, die die nicht negative Matrixfaktorisierung (NMF) vor der nicht negativen Tensorfaktorisierung (NTF) nicht verstehen, steht die Literatur zur Verfügung [1] [2]. Es ist sehr leicht zu verstehen, daher empfehle ich, es vor diesem Artikel zu lesen. Referenz [3] ist sehr höflich in der Formelerweiterung und das am einfachsten zu verstehende Buch in der Bayes'schen Schätzung, das ebenfalls empfohlen wird.
Mein grobes Verständnis
Zersetzung des nicht negativen Tensorfaktors Der überarbeitete NTF ist eine Zersetzungsberechnung, die einen Tensor mit einem nicht negativen Tensorprodukt mit niedrigem Rang approximiert. Haben Sie keine Angst vor Missverständnissen. Auf der High School-Ebene können Sie eine große Matrix in eine kleine Matrix zerlegen, wobei jede Komponente größer oder gleich 0 ist. Tensole sind Erweiterungen der Konzepte von Skalaren, Vektoren und Matrizen, die als Tensoren 0. Ordnung, Tensoren 1. Ordnung bzw. Tensoren 2. Ordnung umschrieben werden können. NMF ist in verschiedenen Forschungsbereichen weit verbreitet und auf den Tensor im zweiten Stock beschränkt.
Selbst eine große Datenmenge, die Menschen auf den ersten Blick nicht verstehen können, kann durch Anwenden von NTF zum Extrahieren von Beziehungen zwischen mehreren Faktoren in niedrigrangige Tensoren zerlegt werden, wodurch das Datenformat für Menschen leicht verständlich wird. Zum intuitiven Verständnis ist das Folgende ein Lochbild, das zeigt, dass der Tensor $ X $ dritter Ordnung ungefähr in drei Tensoren $ T, U, V $ niedrigerer Ordnung (Matrix, Vektor usw.) zerlegt werden kann. ..
NMF konnte nur Beziehungen zwischen Faktoren in zweidimensionalen Daten extrahieren. Andererseits kann NTF die Beziehungen zwischen Faktoren durch die Anzahl der Ordnungen des Tensors extrahieren, so dass es möglich ist, kompliziertere Beziehungen zu analysieren. Dies bedeutet auch, dass Daten, die in vier oder mehr Dimensionen schwer zu visualisieren sind, indirekt in Form von Trends visualisiert werden können.
NTF basiert auf der Minimierung des Abstands (Kostenfunktion) zwischen dem ursprünglichen Tensor und dem Tensor, der aus dem Produkt der ungefähren Vektoren rekonstruiert wurde. Jede Methode kann verwendet werden, um diese Abstandsminimierung zu lösen. Die Lösung konvergiert jedoch effizient, indem die Berechnung des erwarteten Werts des ungefähren Tensors und die Minimierung der Kostenfunktion bei Verwendung wiederholt werden. Es ist bekannt (keine Notwendigkeit, die inverse Matrix zu berechnen, die zur Tensorzerlegung neigt!), Und dieser Ansatz wird häufig verwendet. Mit anderen Worten, wenn Sie diese Aktualisierungsformel kennen, können Sie in der Praxis Daten mit NTF analysieren.
Ableitung der Aktualisierungsformel
Für diejenigen, die maschinelles Lernen als bloßes Werkzeug wie NTF verwenden, wird der Prozess der Konvertierung der mathematischen Formeln hier eher vernachlässigt, aber die Erweiterung des Algorithmus durch Entwerfen und Modellieren der Kostenfunktion gemäß den Eigenschaften der Daten Es ist wesentliches Wissen zu handhaben. Also versuchte ich mein Bestes, um die Formel mit meinem eigenen Verständnis zu entwickeln.
Wenn die partielle Differenzierung der Kostenfunktion 0 wird, wird die Aktualisierungsformel grob abgeleitet, indem der Mindestwert der Kostenfunktion genommen wird.
Definition der Kostenfunktion
$ \ Beta $ -Divergenz wird häufig für Kostenfunktionen verwendet, aber dieses Mal konzentrieren wir uns auf die spezielle Form, die verallgemeinerte KL-Divergenz. Sei $ u_ {ki_ {r}} ^ {(r)} $ der Vektor, der durch Zerlegen des Tensors der $ R $ -Ordnung erhalten wird. $ (K = 1,2, ..., K)
\hat{x}_{\bf i} = \sum_{k=1}^{K} \prod_{r=1}^{R}
u_{ki_{r}}^{(r)}
\quad ({\bf i} = i_{1}i_{2}...i_{R} \in L) \quad (1)
Die Kostenfunktion basierend auf der verallgemeinerten KL-Divergenz ist wie folgt.
D(X, \hat{X})
= \sum_{{\bf i} \in L}(
x_{\bf i}\log\frac{x_{\bf i}}{\hat{x}_{\bf i}}
- x_{\bf i} + \hat{x}_{\bf i}) \quad (2)
Diese Kostenfunktion ist 0, wenn der zu approximierende Tensor $ X $ und der zu approximierende Tensor $ \ hat {X} $ genau übereinstimmen. Das Einsetzen von Gleichung (1) in Gleichung (2) und das Umwandeln des Bruchteils von $ \ log $ in die Summe ergibt die folgende Gleichung.
D(X, \hat{X})
= \sum_{{\bf i} \in L}(
x_{\bf i}\log x_{\bf i}
- x_{\bf i}\log \sum_{k=1}^{K}
\prod_{r=1}^{R} u_{ki_{r}}^{(r)}
- x_{\bf i} + \sum_{k=1}^{K}
\prod_{r=1}^{R} u_{ki_{r}}^{(r)}) \quad (3)
Teilweise Differenzierung der Kostenfunktion
Ich möchte eine schnelle partielle Differenzierung von Gleichung (3) mit $ u_ {ki_ {r}} ^ {(r)} $ vornehmen, aber der zweite Term ist log-sum ($ \ log \ sum_ {k} f_ {k}) Eine teilweise Differenzierung ist schwierig, da sie in Form von (u_ {k {\ bf i}}) $ vorliegt. Deshalb,
h_{k{\bf i}}^{0} = \frac{
\prod_{r=1}^{R} u_{ki_{r}}^{0(r)}
}{
\hat{x}_{\bf i}^{0}
} \quad (4)
Definieren Sie eine Variable mit der Eigenschaft $ \ sum_ {k = 1} ^ {K} h_ {k {\ bf i}} = 1, h_ {k {\ bf i}} \ geq 0 $. Hier zeigt 0 auf der rechten Schulter jeder Variablen an, dass sie vor der Aktualisierung liegt. * Jensen * ist die Summe von $ h_ {k {\ bf i}} / h_ {k {\ bf i}} (= 1) $ zusammengesetzt aus Gleichung (4) für den zweiten Term von Gleichung (3). Unter Verwendung der Ungleichung von hat die Obergrenze des zweiten Terms die Form eines Summenprotokolls ($ \ sum_ {k} \ log f_ {k} (u_ {k {\ bf i}}) $) wie folgt. Kann abgeleitet werden.
- x_{\bf i} \log \sum_{k=1}^{K}
h_{k{\bf i}}^{0}
\frac{\prod_{r=1}^{R} u_{ki_{r}}^{(r)}}
{h_{k{\bf i}}^{0}} \leq - x_{\bf i}
\sum h_{k{\bf i}}^{0} \log
\frac{\prod_{r=1}^{R} u_{ki_{r}}^{(r)}}
{h_{k{\bf i}}^{0}} \quad (5)
Durch Einsetzen von Gleichung (5) in Gleichung (3) kann die Obergrenze der Kostenfunktion abgeleitet werden, wie in der folgenden Gleichung gezeigt.
D(X, \hat{X}) \leq
\sum_{{\bf i} \in L}(
x_{\bf i}\log x_{\bf i}
- x_{\bf i} \sum h_{k{\bf i}}^{0} \log \frac{\prod_{r=1}^{R} u_{ki_{r}}^{(r)}}
{h_{k{\bf i}}^{0}}
- x_{\bf i} + \sum_{k=1}^{K}
\prod_{r=1}^{R} u_{ki_{r}}^{(r)}) \\
= \sum_{{\bf i} \in L}(
- x_{\bf i} \sum h_{k{\bf i}} \log \prod_{r=1}^{R} u_{ki_{r}}^{(r)}
+ \sum_{k=1}^{K}
\prod_{r=1}^{R} u_{ki_{r}}^{(r)}
+ C)
\quad (6)
Hier werden die Terme, die $ u_ {ki_ {r}} ^ {(r)} $ nicht enthalten, bei der nächsten partiellen Differenzierung zu 0, sodass sie durch den konstanten Term $ C $ zusammengefasst werden. Um die Obergrenze dieser Kostenfunktion zu minimieren, wird die folgende Gleichung erhalten, wenn Gleichung (6) teilweise durch $ u_ {ki_ {r}} ^ {(r)} $ differenziert und auf 0 gesetzt wird.
0 = \sum_{{\bf i} \in L_{-r}} (
- x_{\bf i}
\frac{h_{k{\bf i}}^{0}}{u_{ki_{r}}^{(r)}} +
\prod_{\substack{r=1 \\ \bar{r} \neq r} }^{R}
u_{ki_{\bar{r}}}^{(\bar{r})}
) \quad (7)
Wo $ L_ {-r} $ ist ($ \ bar {\ bf i} = i_ {1} ... i_ {r-1} i_ {r + 1} ... i_ {R} \ in L_ Es ist eine Menge namens {-r} $). Die folgende Aktualisierungsgleichung kann erhalten werden, indem Gleichung (7) für $ u_ {ki_ {r}} ^ {(r)} $ unter Verwendung von Gleichung (4) ebenfalls neu angeordnet wird.
u_{ki_{r}}^{(r)} = u_{ki_{r}}^{0(r)} \cdot
\frac{
\sum_{\bar{\bf i} \in L_{-r}}
(x_{\bar{\bf i}}
/ \hat{x}_{\bar{\bf i}}^{0})
\prod_{\substack{\bar{r}=1 \\ \bar{r} \neq r} }^{R}
u_{ki_{\bar{r}}}^{0(\bar{r})}
}{
\sum_{\bar{\bf i} \in L_{-r}}
\prod_{\substack{\bar{r}=1 \\ \bar{r} \neq r} }^{R}
u_{ki_{\bar{r}}}^{(\bar{r})}
} \quad (8)
$ U_ {ki_ {r}} ^ {(r)} $, das durch Minimieren der Obergrenze der Kostenfunktion erhalten wird, wird als $ h_ {k {\ bf i}} ^ {0} $ festgelegt, und die Obergrenze der Kostenfunktion wird weiter festgelegt. Eine sequentielle Aktualisierung, die den Wert minimiert, ergibt ein Minimum von $ D (X, \ hat {X}) $. $ {\ Bf u} _ {k} ^ {(r)} $ zu dem Zeitpunkt, zu dem der Minimalwert erhalten wird, ist ein ungefährer Tensor, der durch Faktorisieren des ursprünglichen Tensors erhalten wird.
Implementierung
Implementiert mit Python + Numpy. Verwenden Sie `` `pip```, um die fehlende Bibliothek zu löschen. Für diejenigen, die Python + Numpy noch nicht kennen, ist es schwierig, sich für Anaconda zu begeistern, das von Anfang an verschiedene Pakete enthält.
Wenn die einzugebenden Daten eine Matrix sind, ist auch die NTF des Tensors zweiter Ordnung, dh NMF, möglich. Ich werde den Code nur für den wichtigen Update-Ausdrucksteil anzeigen.
ntf.py
class NTF():
#Verschiedene andere Elementfunktionen usw. werden weggelassen...
def updateBasedOnGKLD(self, x, factor, index):
# Create tensor partly.
element = self.kronAlongIndex(factor, index)
# Summation
element = element.reshape(self.preshape[index])
estimation = self.createTensorFromFactors()
boost = x/(estimation + EPS)
numer = self.sumAlongIndex(boost*element, factor, index)
denom = np.sum(element)
return numer/(denom + EPS)
def kronAlongIndex(self, factor, index):
element = np.array([1])
for i1 in factor[:index]:
element = np.kron(element, i1)
for i1 in factor[index + 1:]:
element = np.kron(element, i1)
return element
def sumAlongIndex(self, value, factor, index):
for _ in np.arange(index):
value = np.sum(value, axis=0)
for _ in np.arange(index + 1, len(factor)):
value = np.sum(value, axis=1)
return value
def createTensorFromFactors(self):
tensor = self.composeTensor(self.factor)
tensor = np.sum(tensor, axis=0)
return tensor.reshape(self.shape)
#Die Funktion, die die Substanz von composeTensor ist.
def composeTensorSerially(self, element):
return map(self.kronAll, element)
def kronAll(self, factor):
element = np.array([1])
for i1 in factor:
element = np.kron(element, i1)
return element
Obwohl es Python ist, gibt es viele `` `for``` -Anweisungen und es fühlt sich schmutzig an, aber es ist heikel, hier zu bleiben, also lasse ich es in Ruhe. \ # Wenn Sie wissen, wie man schön schreibt oder wie man mit explosiver Geschwindigkeit schreibt, ziehen Sie die Anfrage.
Experiment
Ich habe ein Experiment (oder eher eine Demo) zum Clustering von Zufallszahlen durchgeführt, die aus einer Gaußschen Verteilung erstellt wurden.
Experimentelle Bedingungen
Wir haben jeweils 100 Proben im 3D-Raum gesprüht, basierend auf den folgenden zwei Gaußschen Verteilungen.
| ID | durchschnittlich | Verteilt |
|---|---|---|
| A | (10, 10, 20) | |
| B | (30, 30, 30) |
Es ist ein Körper, von dem bereits bekannt ist, dass Proben aus zwei Clustern ausgesät wurden, und obwohl es sich um eine Match-Pumpe handelt, beträgt die Anzahl der Basen 2. Mit anderen Worten wird der Tensor 3. Ordnung in einen ungefähren Vektor mit 2 Basen zerlegt.
Führen Sie zum erneuten Testen [run_ntf_demo_3rd_order_2bases.py] aus (https://github.com/drumichiro/nmf-and-ntf/blob/master/run_ntf_demo_3rd_order_2bases.py). Darüber hinaus ist Code mit einem Namen wie run_ntf_demo_ \ *. Py verfügbar, mit dem Sie dasselbe Experiment mit verschiedenen Parametern (z. B. Tensorreihenfolge, Basisnummer usw.) ausprobieren können. nmf-und-ntf / blob / master / run_ntf_demo_4th_order_2bases.py).
Ergebnis
Die Verteilung (Tensor) der vom Kronecker-Produkt aus dem ungefähren Vektor rekonstruierten Probe ist auf der rechten Seite der folgenden Abbildung dargestellt. Zum Vergleich ist links auch die Verteilung der Originalprobe dargestellt. Bitte beachten Sie, dass die jeder Achse zugewiesenen Werte Indizes für jeden unterteilten Behälter sind, sodass der in den Versuchsbedingungen angegebene Durchschnitt und der Bruchteil nicht übereinstimmen.
| Verteilung der Originalprobe | Verteilung von Proben, die aus Approximationsvektoren rekonstruiert wurden |
|---|---|
 |
 |
Sie können sehen, dass die Verteilungen beider Proben nahe beieinander liegen. Der zur Rekonstruktion der Probenverteilung verwendete Approximationsvektor ist wie folgt.
Die horizontale Achse ist die Faktorachse. Die vertikale Achse ist die Achse der Basis, aber Sie können sehen, dass eine Gaußsche Verteilung auf jede Basis verteilt ist. Mit diesem Gefühl konnte ich bestätigen, dass der Code so zusammengestellt wurde, wie er war.
Ergänzung
NTF auf Coupon-Kaufhistorie angewendet. Dies ist ein praktischeres Beispiel. Wenn Sie möchten, sehen Sie bitte hier nach.
Recommended Posts