[PYTHON] J'ai essayé d'implémenter ListNet d'apprentissage de rang avec Chainer

introduction

Nous allons implémenter ListNet, qui est une méthode d'apprentissage du classement, dans Chainer!

Cet article est le 7ème jour du Calendrier de l'Avent Chainer 2016.

Explication de la méthode

Tout d'abord, en ce qui concerne l'apprentissage des rangs, sz_dr a écrit un excellent article le 5ème jour du calendrier de l'Avent, veuillez donc le consulter. Regarde s'il te plait. En un mot, pour ceux qui n'ont pas le temps, «apprenez à commander dans des conditions supervisées lorsque vous avez plusieurs données dans un ensemble (requête) et qu'on leur attribue une échelle relative». C'est un problème. La différence par rapport à l'apprentissage supervisé normal est que les étiquettes ne prennent pas de nombres absolus entre les requêtes.

Différence par rapport à RankNet

Je pense que RankNet est la première chose à laquelle beaucoup de gens pensent quand il s'agit de l'apprentissage du réseau neuronal + rang. En fait, il existe plusieurs méthodes pour formuler l'apprentissage des classements, à la différence que RankNet est une méthode par paires et ListNet est une méthode par liste.

Pairwise	Listwise
Effectuer en échantillonnant d'innombrables paires à partir d'une requête	Apprenez pour chaque requête

L'image est tirée de DSIRNLP # 1 Ranking Learning Beginning

Idée de base ListNet

ListNet est basé sur l'idée de la distribution de probabilité de permutation (PPD). Comme le montre la figure ci-dessous, PPD est une distribution de probabilité de la probabilité de chaque permutation de données. Le PPD peut être calculé à partir du score de chaque donnée. Étant donné un certain ordre «G», l'ordre PPD est donné par l'équation suivante.

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

Cependant, $ s_j \ in \ mathbf {s} $ indique le score des données $ j $, $ n $ indique le nombre de données par requête et $ \ pi $ indique l'ordre. Cette formule devient la formule suivante lorsqu'elle est écrite dans l'exemple de $ n = 3 $.

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)}

La perte de probabilité de permutation (PPL) prend l'entropie croisée de deux PPD [^ 1],

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

PPL a l'avantage de pouvoir être appris purement dans l'ordre, par rapport à l'apprentissage avec perte de carré en ajoutant des nombres aux données de l'enseignant à intervalles réguliers, tels que «(1.0, 0.9, 0.8, ..)».

L'image est tirée de Yan Liu, Learning to Rank: from Pairwise Approach to Listwise Approach Citation.

Cependant, si vous calculez les probabilités de tous les ordres de tri, le montant du calcul sera de $ L! $, Et il ne sera pas possible de calculer en pratique. Par conséquent, en général, le montant du calcul de $ L! / (L-k)! $ Est fixé en ne considérant que les $ k $ premiers [^ 2].

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

Par exemple, si $ k = 1 $, qui est également utilisé dans l'article, PPL sera la même formule que softmax.

ListNet utilise simplement PPL, et le calcul du score pour chaque donnée peut être implémenté avec n'importe quelle fonction divisible. Le papier original implémente le calcul du score avec Feed forward NN. ..

la mise en oeuvre

Le premier est l'implémentation de 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]

Cette fois, je l'ai implémenté en supposant que L est variable. En masquant les données inutiles par la longueur, des données de différentes longueurs peuvent être envoyées au même lot. Comme Pitfall, si vous calculez la formule en fonction du papier, le calcul de la division et de l'exp devient instable, vous devez donc utiliser logsumexp qui est également préparé dans chainer.

Le score a été calculé par Perceptron, qui reçoit la quantité de caractéristiques «(B, L, M)» et produit le score «(B, L)». Puisque les données de la liste sont indépendantes les unes des autres, nous avons modifié (B, L, M) en (B, L * M) et l'avons finalement implémenté sous la forme originale.

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])

Toutes les implémentations peuvent être trouvées sur github.

Expérience

L'ensemble de données utilisé était MQ2007 de LETOR 4.0. Je n'ai pas eu beaucoup de temps, donc les paramètres sont fixes et je n'ai rien conçu d'autre qu'un arrêt prématuré.

La cible de l'évaluation est la précision moyenne moyenne (MAP).

résultat

TRAIN: 0.4693
DEV:   0.4767
TEST:  0.4877

(Corrigé le 29 août 2017: voir les commentaires)

~~ Article original ~~ Résultats des auteurs avec les mêmes données [^ 3].

TRAIN: 0.4526
DEV:   0.4790
TEST:  0.4884

~~ Eh bien, il y a beaucoup de différence. Dans l'article original, "Perceptron pour le calcul des scores" a été utilisé, et il a été écrit uniquement avec un certain degré de granularité, donc il peut y avoir eu une certaine ingéniosité. ~~ La performance est à peu près la même. Au lieu de moins régler, j'ai réussi à utiliser une technique qui n'existait pas à l'époque (c'est-à-dire optimiseur Adam, abandon, activation ReLU). (Corrigé le 29 août 2017)

Le plus grand avantage de ListNet est qu'il est de toute façon rapide. Je ne l'ai pas vraiment évalué, mais je pense que c'est environ 100 fois plus rapide que RankNet.

À la fin

J'ai utilisé Tensorflow et le chainer en deux cette année, mais je pense que le chainer est extrêmement plus rapide en vitesse de prototype et en débogage. De plus, Cupy est vraiment bon! En raison du nombre d'utilisateurs, il y a peu d'exemples d'implémentation, et je pense que Tensorflow a été un peu ces derniers temps, donc je voudrais l'exposer à l'excitation.

historique des modifications:

• 2016/12/7: C'était tellement dur que j'ai ajouté la formule.
• 2017/8/27: La source d'acquisition de référence ListNet est répertoriée.
• 29/08/2017: Les résultats expérimentaux ont été mis à jour. Voir les commentaires pour plus de détails. J'ai également publié un lien vers le référentiel.
• 22/12/2017: Ajouté car l'auteur a republié le benchmark.

[^ 1]: La figure montre la distance de divergence KL, mais il semble que l'entropie croisée soit effectivement utilisée. Puisque $ P (\ pi | \ bar {\ mathbf {s}}) $ est fixe, il semble que l'optimisation sera la même après tout. [^ 2]: Après tout, vous échantillonnez dans la liste! Sans le slogan. De plus, cela se fait généralement avec k = 1 ... [^ 3]: Je me souviens que les résultats du benchmark ont été publiés sur https://www.microsoft.com/en-us/research/project/letor-learning-rank-information-retrieval/, mais ~~ Au 27 août 2017, les résultats n'étaient pas divulgués. ~~ Quand j'ai envoyé un e-mail à l'auteur, il a republié.