Différenciation du tri et généralisation du tri

0. Introduction

Cet article décrit comment «différencier» un «tri» et généraliser le tri. En considérant la généralisation du tri, la "différenciation" de la fonction quantile peut également être calculée.

De plus, nous expérimenterons en fait une tâche d'apprentissage automatique appelée régression des moindres quantiles en utilisant la différenciation et la généralisation des sortes.

Ceci est une introduction au contenu du prochain article récemment annoncé par Google et qui attire l'attention.

Differentiable Ranks and Sorting using Optimal Transport

Puisqu'il utilise une technique similaire à Article sur la différenciation des problèmes de transport, quelques explications seront données.

Différenciation de tri?

Lorsque nous utilisons le tri, nous l'utilisons souvent sous la forme des deux fonctions suivantes, la fonction de tri $ S (x) $ et la fonction de rang $ R (x) $.

x=(x_1,\dots ,x_n) \in R^n \\
S(x)=(x_{\sigma _1},\dots ,x_{\sigma _n}) \ \ \ \ \ \ x_{\sigma _1}\leq x_{\sigma_2}\leq \dots \leq x_{\sigma _n} \\
R(x)=(rank(x_1),\dots ,rank(x_n)) \ \ (=\sigma^{-1})

Par exemple, $ S ((3.4, 2.3, -1)) = (-1,2.3,3.4) $, $ R ((3.4, 2.3, -1)) = (3,2,1) $.

Dans cet article, en tant que "différenciation" du "tri"

Pensons à (quelque chose comme).

• $ S (x) et R (x) $ ne peuvent pas être différenciés tels quels.

Application de la différenciation de tri

Qu'est-ce qui serait bien de pouvoir "différencier" le genre?

Le principal avantage est que vous pouvez apprendre des tâches de bout en bout du type qui trient la sortie du réseau neuronal et résolvent quelque chose, comme mentionné dans l'article ci-dessus.

Par exemple

--Lorsque plusieurs images avec des nombres sont entrées, les identifiants des images sont renvoyés dans l'ordre décroissant des nombres.

• Donnez un score de recommandation au produit et apprenez le modèle de recommandation en différenciant directement la perte de classement. --Utilisez un décodeur de recherche de faisceau divisible pour les tâches NLP

Un tel problème peut être envisagé. De plus, si le tri peut être différencié, la fonction quantile peut également être différenciée comme décrit plus loin, de sorte que la tâche «minimiser la valeur n% de l'erreur de régression» est une méthode de descente de gradient qui différencie directement la fonction objectif. Vous pourrez le résoudre en utilisant.

symbole

• O^n
  \\\{ x|x\in R_n,x_1 \leq x_2 \leq \dots \leq x_n \\\}
• R^n_+
  \\\{ x|x\in R_n,x_i \geq 0,i=1,\dots ,n \\\}
• R^n_{+,*}
  \\\{ x|x\in R_n,x_i > 0,i=1,\dots ,n \\\}
• 1_n
  (1,...,1) \in R^n
• \Sigma_n
  \\\{x|x \in R^n_+, \sum x_i=1 \\\}
• U(a,b)
  $a \in R^n_+, b \in R^m_+, U(a,b)= $ $\{ P|P\in R^{n\times m}_+, P1_m=a, P^T1 _n=b \} $
• \langle P,Q\rangle
  P\in R^{n\times m},Q\in R^{n\times m},\langle P,Q\rangle=\sum_{i,j}P_{i,j}Q_{i,j}
• diag(a)
  $ a \ in R ^ n, diag (a): $ Matrice diagonale de $ n \ fois n $ dont la composante diagonale est $ a $

1. Tri, problèmes de transport et différenciation

À propos, $ S (x) et R (x) $ ne sont pas différentiables tels quels. De plus, par exemple, si $ x $ est échantillonné aléatoirement à partir de $ R ^ n $, $ rank (x_1) $ ne devrait pas changer en augmentant ou en diminuant légèrement $ x_1 $. En d'autres termes, même si "quelque chose comme la différenciation" peut être défini, il sera toujours égal à 0.

Pour résoudre ces problèmes et calculer le différentiel du tri, procédez comme suit:

1. Considérez le tri comme une sorte de problème de transport.
2. Considérez le problème de l'ajout d'un terme de régularisation à ce problème de transport. (Il n'y a qu'une seule solution optimale.)
3. Pour les problèmes de transport avec des termes de régularisation, il existe un algorithme d'approximation (algorithme Shinkhorn) qui trouve la solution optimale sous une forme différenciable.
4. Résolvez 2 avec l'algorithme Shinkhorn pour différencier la sortie.

Les explications sont données ci-dessous dans l'ordre.

Problèmes de tri et d'expédition

Problèmes de transport

Comme son nom l'indique, le problème du transport est le problème de la détermination du moyen optimal de transporter les produits de plusieurs usines à plusieurs magasins. La livraison entre chaque usine et magasin coûte selon les frais d'expédition, et chaque volume de transport est déterminé pour minimiser le coût d'expédition total.

En termes mathématiques, étant donné $ a \ in R ^ n_ +, b \ in R ^ m_ +, C \ in R ^ {n \ times m} _ + $, $ \ langle P, C \ rangle Trouver $ P \ dans U (a, b) $ qui minimise $. Dans cet article

L_C(a,b)=min_{P\in U(a,b)}\langle P,C\rangle

Écrire.

$ a $ est l'offre de l'usine, $ b $ est la demande du magasin, $ C_ {i, j} $ est le coût de transport par unité de montant entre l'usine $ i $ et le magasin $ j $, $ P_ {i, j } $ Est le montant du transport entre l'usine $ i $ store $ j $, et $ \ angle P, C \ rangle $ est le coût total du transport. Le coût total d'un transport optimal est de $ L_C (a, b) $.

Traitement des problèmes d'expédition et de tri spéciaux

Considérons maintenant le problème de transport simple suivant.

• Le nombre d'usines et de magasins est le même, $ n $ pièces
• L'usine et le magasin sont alignés en ligne droite -Définir $ x, y \ dans R _n $ comme coordonnées de l'usine et du magasin, respectivement.
• Supposons que l'emplacement de chaque magasin satisfasse la relation $ y _1 <y _2 <\ dots <y _n . ( y \ dans O ^ n $)
• Le coût de livraison augmente à mesure que la distance entre les magasins d'usine augmente. Multipliez $ C _ {i, j} = h (y _j -x _i) $ en utilisant la fonction convexe au sens étroit non négatif différenciable $ h $.
• L'offre de l'usine et la demande du magasin sont toutes les mêmes, 1 $ / n $, c'est-à-dire $ a = b = 1 _n / n $

À l'heure actuelle, la proposition suivante qui relie les problèmes de tri et de transport tient.

Proposition 1.

Dans les circonstances ci-dessus, l'une des solutions optimales pour le problème de transport $ L_C (a, b) = min_ {P \ in U (a, b)} \ angle P, C \ rangle $ est $ P _ * $. Faire. À ce stade, ce qui suit est vrai.

R(x)=n^2 P_* \hat{b} \\
S(x)=n P_*^T x \\

Où $ \ hat {b} = (b_1, b_1 + b_2, \ dots, \ sum b) ^ T = (1 / n, 2 / n, \ dots, 1) ^ T $

En fait, considérez le problème de transport suivant:

Coût du transport (= carré de la distance)

Le volume de transport optimal doit être:

Remplaçons-les par l'équation de la proposition.

3^2 \left(
    \begin{array}{ccc}
      0 & 0 & 1/3 \\
      0 & 1/3 & 0 \\
      1/3 & 0 & 0
    \end{array}
  \right)
  \left(
    \begin{array}{ccc}
      1/3   \\
      2/3   \\
      1 
    \end{array}
  \right) = 
  \left(
    \begin{array}{ccc}
      3   \\
      2   \\
      1 
    \end{array}
  \right) = R(
\left(
    \begin{array}{ccc}
      2   \\
      1   \\
      0 
    \end{array}
  \right)
  )

3 \left(
    \begin{array}{ccc}
      0 & 0 & 1/3 \\
      0 & 1/3 & 0 \\
      1/3 & 0 & 0
    \end{array}
  \right)
  \left(
    \begin{array}{ccc}
      2   \\
      1   \\
      0 
    \end{array}
  \right) = 
  \left(
    \begin{array}{ccc}
      0   \\
      1   \\
      2 
    \end{array}
  \right) = S(
\left(
    \begin{array}{ccc}
      2   \\
      1   \\
      0 
    \end{array}
  \right)
  )

Vous pouvez voir que la formule de la proposition tient.

Problèmes de transport et différenciation

Dans le chapitre précédent, nous avons confirmé que $ S (x) et R (x) $ peuvent être écrits en utilisant la solution d'un problème de transport spécial. Par conséquent, si la différenciation de la solution du problème de transport ($ P _ \ * $ de la proposition 1) par $ C _ {i, j} $ peut être calculée, elle dépend de $ x _i $ de $ S (x), R (x) $. Le différentiel peut également être calculé. Ce $ P _ \ * $ lui-même n'est pas divisible, mais il existe un moyen de trouver une solution approximative de $ P _ \ * $ sous une forme divisible.

Autrement dit, considérons d'abord le problème de transport suivant avec un «terme de régularisation». En d'autres termes, l'entropie du volume de transport

H(P)=-\sum_{i,j}P_{i,j}(log(P_{i,j})-1)

Au lieu du problème d'origine

L_C^{\epsilon}(a,b)=min_{P\in U(a,b)}\langle P,C\rangle - \epsilon H(P)　★

Penser à. À $ \ epsilon \ à 0 $, la solution de ce problème de transport régularisé converge vers la solution du problème de transport original.

De plus, l'algorithme Shinkhorn suivant peut être utilisé pour trouver une solution approximative sous une forme divisible.

Algorithme Shinkhorn

init u=u^0,v=v^0,l=0, calc K;

while l < MAX_ITER: \ \ \ \ u=a/(Kv) \ \ \ \ v=b/(K^Tu) \ \ \ \ l++

P=diag(u)Kdiag(v)

return P

MAX_ITER $ \ to \ infty $ fera converger la sortie de l'algorithme Shinkhorn vers la solution optimale de ★. À propos de cet algorithme Shinkhorn

Différencier les problèmes de transport

J'ai expliqué en détail dans.

Implémentation par PyTorch

Implémentons l'algorithme Shinkhorn dans PyTorch et utilisons-le pour calculer le différentiel du tri.

import torch
from torch import nn

#Algorithme Shinkhorn
class OTLayer(nn.Module):
    def __init__(self, epsilon):
        super(OTLayer,self).__init__()
        self.epsilon = epsilon

    def forward(self, C, a, b, L):
        K = torch.exp(-C/self.epsilon)
        u = torch.ones_like(a)
        v = torch.ones_like(b)
        l = 0
        while l < L:
            u = a / torch.mv(K,v)
            v = b / torch.mv(torch.t(K),u)
            l += 1
                
        return u, v, u.view(-1,1)*(K * v.view(1,-1))

# sort & rank
class SortLayer(nn.Module):
    def __init__(self, epsilon):
        super(SortLayer,self).__init__()
        self.ot = OTLayer(epsilon)
        
    def forward(self, x, L):
        l = x.shape[0]
        y = (x.min() + (torch.arange(l, dtype=torch.float) * x.max() / l)).detach()
        C = ( y.repeat((l,1)) - torch.t(x.repeat((l,1))) ) **2
        a = torch.ones_like(x) / l
        b = torch.ones_like(y) / l
        _, _, P = self.ot(C, a, b, L)
        
        b_hat = torch.cumsum(b, dim=0)
        
        return l**2 * torch.mv(P, b_hat), l * torch.mv(torch.t(P), x)

sl = SortLayer(0.1)
x = torch.tensor([2., 8., 1.], requires_grad=True)
r, s = sl(x, 10)
print(r,s)

tensor([2.0500, 3.0000, 0.9500], grad_fn=<MulBackward0>) tensor([1.0500, 2.0000, 8.0000], grad_fn=<MulBackward0>)

(Calcul de la différenciation)

r[0].backward()
print(x.grad)

tensor([ 6.5792e-06,  0.0000e+00, -1.1853e-20])

2. Généralisation de tri et fonction quantile

Généralisation du tri

Dans le chapitre précédent, nous avons vu que la fonction de tri et les fonctions de classement $ S (x) et R (x) $ peuvent être écrites en utilisant la solution d'un problème de transport spécial. Le problème d'expédition spécial qui correspond à ce type est

• Le nombre d'usines et le nombre de magasins sont les mêmes ――La quantité d'approvisionnement de l'usine et la quantité de demande du magasin sont toutes les mêmes

Je disais. Cependant, en général, les problèmes de transport peuvent être envisagés même si le nombre d'usines et de magasins est différent, ou si l'offre et la demande sont différentes selon les usines et les magasins. En considérant $ S (x), R (x) $ correspondant aux solutions de ces problèmes généraux de transport, nous devrions pouvoir trier et généraliser les rangs.

Sur la base de cette idée, dans Ranks Differentiable and Sorting using Optimal Transport, K (Kantorovich) est une fonction de tri généralisée et une fonction de classement comme suit. ) Le tri et le rang K ont été introduits.

Définition 1. tri K et rang K

Problèmes de transport pour tout $ x \ in R ^ n, y \ in O ^ n, a \ in \ Sigma_n, b \ in \ Sigma_m $ et la fonction étroitement convexe $ h $

Soit $ P _ * $ l'une des solutions optimales pour. À ce stade, le tri K et le rang K de $ x $ sont définis comme suit.

\hat{S} (a,x,b,y)=diag(b^{-1})P^T _* x \\
\hat{R} (a,x,b,y)=n* diag(a^{-1})P_* \hat{b}

Ici, $ a ^ {-1} et b ^ {-1} $ représentent l'inverse de chaque élément du vecteur.

$ P_ * \ dans U (a, b) $

P_* 1_n = a \\
P^T_* 1_m = b

Rencontrer. Par conséquent, $ diag (b ^ {-1}) P ^ T _ \ * $ et $ diag (a ^ {-1}) P de $ \ hat S, \ hat R $ La partie _ \ * $ peut être considérée comme normalisée de sorte que la somme des lignes de $ P ^ T _ \ *, P _ \ * $ est tout 1. De plus, si $ a = b = 1 _n / n $, l'original $ S, R $ sera obtenu, qui est une extension naturelle de la fonction de tri et de la fonction de classement.

Notez également que lorsque $ b = 1_n / n $, $ n \ hat b $ sera $ (1,2, \ dots, n) $ dans l'ordre de "rang". Par conséquent, $ \ hat b $ correspondant au général $ b $ peut être considéré comme une généralisation du "rang" et prend une valeur réelle. En tenant compte de cela

• $ \ hat S _i $ est une combinaison linéaire de $ x _i $ affectée au $ i $ ème rang.
• $ \ hat R _j $ est une combinaison linéaire de rangs généralisés (rang = $ \ hat b $) auxquels $ x _j $ est affecté

Vous pouvez également confirmer que c'est le cas.

J'ai essayé de montrer la différence entre le tri normal, le rang et le tri K et le rang K dans le diagramme schématique ci-dessous. Le tri K et le rang K représentent le cas de $ a = 1 _5 / 5, b = (0.48, 0.16, 0.36) $.

fonction quantile

Quelle est la fonction quantile?

Est la fonction $ q $. En fait, vous pouvez utiliser le tri K $ \ hat S $ pour calculer efficacement la fonction quantile. Par exemple, $ x \ in R ^ n $ est un ensemble de points de données, et K tri dans la situation où $ a = 1_n / n, y = (0,1 / 2,1), b = (0.29,0.02,0.69) $ Considérons $ \ hat S (a, x, b, y) $.

Comme le montre la figure ci-dessus, vous pouvez imaginer que les 30% inférieurs de x sont associés à $ y_1 $, les 60% supérieurs sont associés à $ y_3 $, et seuls les points proches du point 30% de x sont associés à $ y_2 $. ..

Par conséquent, la fonction quantile utilise le tri K et une valeur t raisonnablement petite,

Vous pouvez vous attendre à appeler. Comme expliqué dans le chapitre précédent, l'algorithme Shinkhorn peut être utilisé pour obtenir une approximation divisible de $ \ hat S $, de sorte que la différenciation de la fonction quantile peut également être calculée.

Notez également que le tri K ci-dessus peut être effectué dans l'ordre de $ O (nl) $ ($ l $ est le nombre d'itérations de l'algorithme Shinkhorn).

Implémentation par PyTorch

Implémentons en fait le tri K dans PyTorch et calculons la fonction quantile. Utilisez l'OTLyer du chapitre précédent.

class QuantileLayer(nn.Module):
    def __init__(self, epsilon):
        super(QuantileLayer,self).__init__()
        self.ot = OTLayer(epsilon)
        self.y = torch.Tensor([0.,0.5,1.])
        
    def forward(self, x, tau, t, L):
        l = x.shape[0]
       
        C = ( self.y.repeat((l,1)) - torch.t(x.repeat((3,1))) ) **2
        a = torch.ones_like(x) / l
        b = torch.Tensor([tau-t/2, t, 1-tau-t/2])
        
        _, _, P = self.ot(C, a, b, L)
        
        b_hat = torch.cumsum(b, dim=0)
        
        return (torch.mv(torch.t(P), x) / b)[1]

(Demandez 30% de points)

import numpy as np

np.random.seed(47)

x = np.random.rand(1000)

quantile = QuantileLayer(0.1)
print(quantile(torch.tensor(x,dtype=torch.float), 0.3, 0.1, 10))

tensor(0.3338)

3. Application de la différenciation et de la généralisation du tri

En tant qu'application simple de la différenciation de tri et de la généralisation à l'apprentissage automatique, nous résoudrons la tâche de régression des moindres quantiles en différenciant directement la fonction objectif à l'aide de la fonction quantile et en exécutant la méthode du gradient.

least quantile regression Alors que la régression linéaire ordinaire optimise le modèle pour minimiser la «moyenne» de l'erreur de prédiction, la régression de moindre quantile entraîne le modèle pour minimiser la «valeur n%» de l'erreur. Cela inclut la tâche de minimiser la valeur médiane, qui est la «valeur à 50%» de l'erreur. Par exemple

• Le bruit des données n'est pas une distribution gaussienne et la valeur de l'enseignant change de manière significative dans une direction spécifique.

Cela est utile lorsque vous souhaitez minimiser la «valeur centrale» de l'erreur en ignorant les données aberrantes.

Dans cet article, nous expérimenterons la régression la moins quantile en utilisant les données de revenu annuel, qui sont souvent utilisées pour expliquer la différence entre «moyenne» et «médiane». Créons un modèle qui prédit le revenu annuel à partir de l'âge en utilisant des données sur l'âge moyen et le revenu annuel moyen des sociétés cotées. Le modèle est formé en différenciant directement «l'erreur médiane» et en exécutant la méthode de descente de gradient à l'aide de la méthode décrite dans cet article.

Pour les données, j'ai utilisé publié par yutakikuchi sur github.

Expérience

Les entreprises âgées en moyenne de 45 ans ou moins sont extraites des données et utilisées. (Pour faciliter l'observation de la différence par rapport à la régression linéaire normale.)

La répartition des données est la suivante.

Il semble que l'âge et le revenu annuel soient à peu près proportionnels, mais il peut être confirmé que le bruit n'est pas une distribution normale et que la dispersion se propage dans le sens d'un revenu annuel plus élevé. Vous pouvez vous attendre à ce qu'un modèle de régression linéaire normal soit déplacé par les valeurs aberrantes et surestime le dégradé.

Le code pour apprendre un modèle linéaire en différenciant directement la «valeur médiane» (= 50% point) de l'erreur à l'aide de la méthode développée dans cet article est le suivant. (La partie de mise en forme des données est omise.)

(Couche qui exécute l'algorithme Sinkhorn)

import torch
from torch import nn
import torch.optim as optim


class OTLayer(nn.Module):
    def __init__(self, epsilon):
        super(OTLayer,self).__init__()
        self.epsilon = epsilon

    def forward(self, 
                C, # batch_size, n, m 
                a, # batch_size, n
                b, # batch_size, m
                L):
        bs = C.shape[0]
        K = torch.exp(-C/self.epsilon) # batch_size, n, m
        u = torch.ones_like(a).view(bs,-1,1) # batch_size, n, 1
        v = torch.ones_like(b).view(bs,-1,1) # batch_size, m, 1
        l = 0
            u = a.view(bs,-1,1) / (torch.bmm(K,v) + 1e-8) # batch_size, n, 1
            v = b.view(bs,-1,1) / (torch.bmm(torch.transpose(K, 1, 2),u) + 1e-8)# batch_size, m, 1
            l += 1
                
        return u * K * v.view(bs,1,-1) # batch_size, n, m

(couche qui calcule la fonction quantile)

class QuantileLayer(nn.Module):
    def __init__(self, epsilon, y):
        super(QuantileLayer,self).__init__()
        self.ot = OTLayer(epsilon)
        self.y = y.detach()
        
    def forward(self, x, # batch_size, seq_len
                tau, t, L):
        bs = x.shape[0]
        seq_len = x.shape[1]
        C = ( self.y.repeat((bs,seq_len,1)) - x.unsqueeze(-1).expand(bs,seq_len,3) ) **2 # batch_size, seq_len, 3
        
        a = torch.ones_like(x) / seq_len  # batch_size, seq_len
        b = torch.Tensor([tau-t/2, t, 1-tau-t/2]).expand([bs, 3]) # batch_size, 3
        
        P = self.ot(C, a, b, L) # batch_size, seq_len, 3
        
        k_sort =  torch.bmm(
            torch.transpose(P,1,2), # batch_size, 3, seq_len 
            x.unsqueeze(-1) # batch_size, seq_len, 1
        ).view(-1) / b.view(-1) # 3, 

        return k_sort[1]

(Préparation des données âge = âge et revenu annuel = revenu)

import pandas as pd

data = pd.DataFrame({"age":ages, "income":incomes})
data_2 = data[data.age <= 45]
ppd_data = (data_2- data_2.mean(axis=0))/data_2.std(axis=0)

X = torch.Tensor(ppd_data.age.values.reshape(-1,1))
ans =  torch.Tensor(ppd_data.income.values.reshape(-1,1))

(Exécution d'apprentissage)

model = nn.Linear(1,1)
loss = nn.MSELoss(reduction='none')

y = [0, ppd_data.income.max()/4., ppd_data.income.max()/2.]
quantile = QuantileLayer(0.1, torch.Tensor(y))

optimizer = optim.Adam(model.parameters(), lr=0.1)

MAX_ITER = 100
for i in range(MAX_ITER):
    optimizer.zero_grad()
    
    pred = model(X)
    loss_value = loss(pred, ans).view(1,-1) # 1, seq_len( = data size)
    
    #Calculer l'erreur médiane
    quantile_loss = quantile(loss_value, 0.5, 0.1, 10)
    print(quantile_loss)
    quantile_loss.backward()
    optimizer.step()

Voici une comparaison des résultats d'ajustement du modèle entraîné et du modèle de régression régulier qui minimise la «moyenne» de l'erreur: Il peut être confirmé que le modèle avec la valeur médiane minimisée (= quantile) est moins susceptible d'être entraîné par les données aberrantes.

4. Résumé

Dans cet article, j'ai expliqué comment différencier le tri et comment calculer la fonction quantile sous une forme divisible comme une généralisation du tri. En tant qu'application simple, nous avons résolu la tâche de régression des moindres quantiles par la méthode du gradient et observé la différence entre le modèle qui minimise la «valeur moyenne» et le modèle qui minimise la «valeur médiatique» de l'erreur.

Telle qu'introduite au début, la différenciation de tri devrait avoir un plus large éventail d'applications telles que la différenciation de recherche de faisceau, et peut être vue dans divers articles à l'avenir.