[PYTHON] Ich habe versucht, ListNet of Rank Learning mit Chainer zu implementieren

Einführung

Wir werden ListNet in Chainer implementieren, eine Methode, um das Ranking zu lernen!

Dieser Artikel ist der 7. Tag von Chainer Adventskalender 2016.

Erläuterung der Methode

Zunächst schrieb sz_dr in Bezug auf das Ranglernen am 5. Tag des Adventskalenders einen großartigen Artikel. Schauen Sie bitte. Kurz gesagt, für diejenigen, die nicht die Zeit haben, "lernen Sie das Ordnen unter überwachten Bedingungen, wenn mehrere Daten in einem Satz (Abfrage) vorhanden sind und sie eine relative Skala erhalten." Es ist ein Problem. Der Unterschied zum normalen überwachten Lernen besteht darin, dass Labels zwischen Abfragen keine absoluten Zahlen annehmen.

Unterschied zum RankNet

Ich denke, RankNet ist das erste, woran viele Leute denken, wenn es um neuronales Netz + Ranglernen geht. Tatsächlich gibt es mehrere Methoden zum Formulieren des Ranglernens, mit dem Unterschied, dass RankNet eine paarweise Methode und ListNet eine listweise Methode ist.

Pairwise Listwise
pairwise_small.png listwise_small.png
Führen Sie unzählige Paare aus einer Abfrage aus Lernen Sie für jede Abfrage

Das Bild stammt aus DSIRNLP # 1 Ranking Learning Beginning

ListNet Grundidee

ListNet basiert auf der Idee der Permutationswahrscheinlichkeitsverteilung (PPD). Wie in der folgenden Abbildung gezeigt, ist PPD eine Wahrscheinlichkeitsverteilung der Wahrscheinlichkeit jeder Permutation von Daten. Die PPD kann aus der Punktzahl für jede Daten berechnet werden. Bei einer bestimmten Ordnung "G" ist die Ordnung PPD durch die folgende Gleichung gegeben.

P(\pi|\mathbf{s}) = \prod_{j}^n{\frac{exp(s_j)}{\sum_{i=j}^{n}{exp(s_i)}}}

$ S_j \ in \ mathbf {s} $ gibt jedoch die Punktzahl der Daten $ j $ an, $ n $ gibt die Anzahl der Daten pro Abfrage an und $ \ pi $ gibt die Reihenfolge an. Diese Formel wird zur folgenden Formel, wenn sie im Beispiel von $ n = 3 $ geschrieben wird.

P(\pi) = \frac{exp(s_0)}{exp(s_0) + exp(s_1) + exp(s_2)}\frac{exp(s_1)}{exp(s_1) + exp(s_2)}\frac{exp(s_2)}{exp(s_2)}

Permutation Probability Loss (PPL) nimmt die Kreuzentropie zweier PPDs an [^ 1],

PPL = -\sum{P(\pi|\bar{\mathbf{s}}) \log P(\pi|\mathbf{s})}

PPL hat den Vorteil, dass es im Vergleich zum Lernen mit quadratischem Verlust rein in der richtigen Reihenfolge gelernt werden kann, indem in regelmäßigen Abständen Zahlen zu den Lehrerdaten hinzugefügt werden, z. B. "(1,0, 0,9, 0,8, ..)".

permutation_probability_small.png

Das Bild stammt von Yan Liu, Lernen zu ranken: vom paarweisen Ansatz zum listweisen Ansatz Zitat.

Wenn Sie jedoch die Wahrscheinlichkeiten aller Sortierreihenfolgen berechnen, beträgt der Berechnungsbetrag $ L! $, Und eine praktische Berechnung ist nicht möglich. Daher wird der Berechnungsbetrag von $ L! / (L-k)! $ Im Allgemeinen festgelegt, indem nur die obersten $ k $ -Elemente berücksichtigt werden [^ 2].

P(\pi|\mathbf{s}) = \prod_{j}^k{\frac{exp(s_j)}{\sum_{i=j}^{n}{exp(s_i)}}}

Wenn beispielsweise $ k = 1 $ ist, was auch im Papier verwendet wird, entspricht PPL der Formel von softmax.

ListNet verwendet einfach PPL, und die Berechnung der Punktzahl für jede Daten kann mit jeder teilbaren Funktion implementiert werden. Das Originalpapier implementiert die Punkteberechnung mit Feed forward NN. ..

Implementierung

Erstens ist die Implementierung von PPL ($ k = 1 $).


def permutation_probability_loss(x, t, length):
    length = length.reshape(-1, 1)
    # log_p: (batch size, n)
    log_p_x = x - F.broadcast_to(F.expand_dims(F.logsumexp(x, axis=1), 1), x.shape)
    # p_t: (batch size, n)
    p_t = F.softmax(t)

    # loss normalized over all instances
    loss = p_t * log_p_x
    mask = np.tile(np.arange(x.shape[1]).reshape(1, -1), (x.shape[0],  1)) < length
    mask = chainer.Variable(mask)
    padding = chainer.Variable(np.zeros(x.shape, dtype=x.dtype))
    loss = F.where(mask, loss, padding)

    return -F.sum(loss / length) / p_t.shape[0]

Dieses Mal habe ich es unter der Annahme implementiert, dass L variabel ist. Durch Maskieren unnötiger Daten mit der Länge können Daten unterschiedlicher Länge an denselben Stapel gesendet werden. Wenn Sie als Fallstrick die Formel gemäß dem Papier berechnen, wird die Berechnung von Division und Exp instabil, sodass Sie logsumexp verwenden müssen, das auch in chainer bereitgestellt wird.

Die Punktzahl wurde von Perceptron berechnet, das die Merkmalsmenge "(B, L, M)" empfängt und die Punktzahl "(B, L)" ausgibt. Da die Daten in der Liste unabhängig voneinander sind, haben wir "(B, L, M)" in "(B, L * M)" geändert und schließlich in der ursprünglichen Form implementiert.

class ListNet(chainer.Chain):
    def __init__(self, input_size, n_units, dropout):
        super(ListNet, self).__init__(
            l1=L.Linear(input_size, n_units),
            l2=L.Linear(n_units, 1))

        self.add_persistent("_dropout", dropout)

    def __call__(self, x, train=True):
        s = list(x.shape)
        n_tokens = np.prod(s[:-1])
        x = F.reshape(x, (n_tokens, -1))

        if self._dropout > 0.:
            x = F.dropout(x, self._dropout, train=train)
        o_1 = F.relu(self.l1(x))
        if self._dropout > 0.:
            o_1 = F.dropout(o_1, self._dropout, train=train)

        # o_2: (N*M, 1)
        o_2 = self.l2(o_1)

        return F.reshape(o_2, s[:-1])

Alle Implementierungen finden Sie unter github.

Experiment

Der verwendete Datensatz war MQ2007 aus LETOR 4.0. Ich hatte nicht viel Zeit, daher sind die Parameter festgelegt und ich habe nichts anderes als frühes Stoppen entwickelt.

Das Bewertungsziel ist die mittlere durchschnittliche Genauigkeit (MAP).

Ergebnis

TRAIN: 0.4693
DEV:   0.4767
TEST:  0.4877

(Korrigiert am 29. August 2017: Siehe Kommentare)

~~ Originalarbeit ~~ Ergebnisse der Autoren mit den gleichen Daten [^ 3].

TRAIN: 0.4526
DEV:   0.4790
TEST:  0.4884

~~ Nun, es gibt einen großen Unterschied. In der Originalarbeit wurde "Perceptron für die Berechnung der Punktzahl" verwendet, und es wurde nur mit einem gewissen Grad an Granularität geschrieben, so dass möglicherweise ein gewisser Einfallsreichtum vorhanden war. ~~ Die Leistung ist ungefähr gleich. Anstatt weniger zu tunen, war ich erfolgreich mit einer Technik, die zu diesem Zeitpunkt noch nicht existierte (d. H. Adam-Optimierer, Dropout, ReLU-Aktivierung). (Korrigiert am 29. August 2017)

Der größte Vorteil von ListNet ist, dass es sowieso schnell ist. Ich habe es nicht wirklich bewertet, aber ich denke, es ist ungefähr 100 Mal schneller als RankNet.

Am Ende

Ich habe Tensorflow und Chainer in der Hälfte dieses Jahres verwendet, aber ich denke, Chainer ist in Bezug auf Geschwindigkeit und Debugging von Prototypen überwältigend schneller. Cupy ist auch wirklich gut! Aufgrund der Anzahl der Benutzer gibt es nur wenige Implementierungsbeispiele, und ich bin der Meinung, dass Tensorflow in letzter Zeit ein wenig aufgetreten ist. Daher möchte ich es der Aufregung aussetzen.


Geschichte verändern:

[^ 1]: Die Abbildung zeigt die KL-Divergenzdistanz, aber es scheint, dass tatsächlich die Kreuzentropie verwendet wird. Da $ P (\ pi | \ bar {\ mathbf {s}}) $ festgelegt ist, scheint die Optimierung doch dieselbe zu sein. [^ 2]: Immerhin probieren Sie aus der Liste! Ohne den Slogan. Außerdem wird es normalerweise mit "k = 1" gemacht ... [^ 3]: Ich erinnere mich, dass die Benchmark-Ergebnisse unter https://www.microsoft.com/en-us/research/project/letor-learning-rank-information-retrieval/ veröffentlicht wurden, aber ~~ Zum 27. August 2017 wurden die Ergebnisse nicht bekannt gegeben. ~~ Als ich dem Autor eine E-Mail schickte, wurde er erneut veröffentlicht.

Recommended Posts

Ich habe versucht, ListNet of Rank Learning mit Chainer zu implementieren
Ich habe versucht, Autoencoder mit TensorFlow zu implementieren
Ich habe versucht, CVAE mit PyTorch zu implementieren
Ich habe versucht, das Lesen von Dataset mit PyTorch zu implementieren
Ich habe versucht, Deep Learning zu implementieren, das nicht nur mit NumPy tiefgreifend ist
Ich habe versucht, PCANet zu implementieren
Ich habe versucht, StarGAN (1) zu implementieren.
Ich habe versucht, die Sündenfunktion mit Chainer zu trainieren
Ich habe versucht, maschinelles Lernen (Objekterkennung) mit TouchDesigner zu verschieben
Ich habe versucht, Funktionen mit SIFT von OpenCV zu extrahieren
Ich habe versucht, DCGAN mit PyTorch zu implementieren und zu lernen
Ich habe versucht, künstliches Perzeptron mit Python zu implementieren
Ich habe versucht, Grad-CAM mit Keras und Tensorflow zu implementieren
Ich habe versucht, SSD jetzt mit PyTorch zu implementieren (Dataset)
Ich habe versucht, einen automatischen Nachweis der Sequenzberechnung zu implementieren
Ich habe versucht, Cifar10 mit der SONY Deep Learning Library NNabla [Nippon Hurra] zu implementieren.
Ich habe versucht, mit Quantx eine Linie mit gleitendem Durchschnitt des Volumens zu implementieren
Ich habe versucht, die Entropie des Bildes mit Python zu finden
Ich habe versucht, Deep VQE zu implementieren
Ich habe versucht, mit TensorFlow den Durchschnitt mehrerer Spalten zu ermitteln
Ich habe versucht, die Erkennung von Anomalien durch spärliches Strukturlernen zu implementieren
Ich habe maschinelles Lernen mit liblinear versucht
Ich habe versucht, mit Quantx einen Ausbruch (Typ der Täuschungsvermeidung) zu implementieren
Ich habe versucht, eine kontroverse Validierung zu implementieren
Mayungos Python Learning Episode 3: Ich habe versucht, Zahlen zu drucken
Ich habe versucht, Harry Potters Gruppierungshut mit CNN umzusetzen
[Maschinelles Lernen] Ich habe versucht, die Theorie von Adaboost zusammenzufassen
Ich habe versucht, Realness GAN zu implementieren
Ich habe versucht, Perceptron Teil 1 [Deep Learning von Grund auf neu] zu implementieren.
Ich habe versucht, das Blackjack of Trump-Spiel mit Python zu implementieren
Ich habe versucht, LightGBM mit Yellowbrick zu lernen
Ich habe versucht, in einem tief erlernten Sprachmodell zu schreiben
Ich habe versucht, SSD jetzt mit PyTorch zu implementieren (Modellversion)
Ich habe versucht, Othello AI zu machen, dass ich 7,2 Millionen Hände durch tiefes Lernen mit Chainer gelernt habe
Ich habe versucht, Deep Learning mit Spark × Keras × Docker skalierbar zu machen
Ich habe versucht, mit Python eine Liste von Primzahlen zu erstellen
Ich habe versucht zu beheben "Ich habe versucht, die Wahrscheinlichkeit eines Bingospiels mit Python zu simulieren"
Ich habe versucht, die Satzklassifizierung durch Self Attention mit PyTorch zu implementieren
Ich habe versucht, die Größe des logischen Volumes mit LVM zu erweitern
Ich habe versucht, den DNN-Teil von OpenPose mit Chainer-CPU auszuführen
Ich habe versucht, die Effizienz der täglichen Arbeit mit Python zu verbessern
Ich habe versucht, automatisch Bilder von Kanna Hashimoto mit Python zu sammeln! !!
Ich habe versucht, mit Go einen exklusiven Kontrollmechanismus zu erstellen
Ich habe versucht, PLSA in Python zu implementieren
Ich habe versucht, Permutation in Python zu implementieren
Ich habe versucht, AutoEncoder mit TensorFlow zu visualisieren
Ich habe versucht, mit Hy anzufangen
Ich habe versucht, PLSA in Python 2 zu implementieren
Ich habe versucht, ADALINE in Python zu implementieren
Ich habe versucht, PPO in Python zu implementieren
Ich habe versucht, TSP mit QAOA zu lösen
Ich habe versucht, Othello AI mit Tensorflow zu machen, ohne die Theorie des maschinellen Lernens zu verstehen ~ Einführung ~
Ich habe versucht, Othello AI mit Tensorflow zu erstellen, ohne die Theorie des maschinellen Lernens zu verstehen ~ Implementierung ~
Ich habe versucht, eine Blockchain zu implementieren, die tatsächlich mit ungefähr 170 Zeilen funktioniert
[Deep Learning von Grund auf neu] Ich habe versucht, Sigmoid Layer und Relu Layer zu implementieren
765 Ich habe versucht, die drei Berufsfamilien durch CNN zu identifizieren (mit Chainer 2.0.0).
Mayungos Python Learning Episode 2: Ich habe versucht, Zeichen mit Variablen zu löschen
Ich habe versucht, den Authentifizierungscode der Qiita-API mit Python abzurufen.
[Stärkung des Lernens] Endlich die Menschen übertroffen! ?? Ich habe versucht, Agent57 (Keras-RL) zu erklären / zu implementieren.