[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
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, ..)".

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:

• 07.12.2016: Ich habe die Formel hinzugefügt, weil sie zu grob war.
• 27.08.2017: Die ListNet-Benchmark-Akquisitionsquelle ist aufgeführt.
• 29.08.2017: Die experimentellen Ergebnisse wurden aktualisiert. Siehe Kommentare für Details. Ich habe auch einen Link zum Repository gepostet.
• 22.12.2017: Hinzugefügt, da der Autor den Benchmark erneut veröffentlicht hat.

[^ 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.