2015-04-14

Cet article a fait l'objet d'une traduction automatique.

Série de tests

Formation au jambage descendant dégradé avec C#

James McCaffrey Ma définition informelle de machine learning (ML) est un système qui utilise les données pour faire des prédictions. Toute personne qui commence à enquêter sur ML rapidement rencontre l'expression un peu mystérieuse « descente de gradient ». Dans cet article, je vais expliquer quelle descente de gradient est et montrent comment l'utiliser pour former un système de classification de la régression logistique.

Pour avoir une idée d'où va cet article, jetez un oeil sur le programme de démonstration en Figure 1. La démo commence par générer 10 000 éléments de données synthétiques. À l'aide de données artificielles plutôt que des données réelles est souvent utile dans les enquêtes sur les ML parce que vous pouvez contrôler les caractéristiques des données. Chaque élément de données possède huit predictor variables valeurs (souvent appelés caractéristiques dans la terminologie de ML) suivies d'une seule variable dépendante, qui peut être 0 ou 1. Les données ont été générées à l'aide de huit valeurs de poids aléatoires (-7.78,-0.65... -7.97) plus une constante supplémentaire (-5.02).

Figure 1 un classifieur de régression logistique à l'aide de descente de Gradient de formation

Vous pouvez imaginer que les données synthétiques correspondant à un problème lorsque vous essayez de prédire le sexe (male = 0, femelle = 1) d'une personne basée sur huit caractéristiques comme l'âge, revenu annuel, pointage de crédit et ainsi de suite, où les valeurs de la fonction ont tous été mis à l'échelle afin qu'ils tombent entre-10, 0 et + 10,0.

Après avoir généré les éléments de données de 10 000, la démo divise au hasard que les données dans un ensemble de 8 000-point pour être utilisé pour former un classificateur et un ensemble de 2 000 éléments à utiliser pour estimer la valeur prédictive du modèle qui en résulte. Ensuite, la démo crée un classifieur binaire de la régression logistique et puis se prépare pour la descente de gradient formation en définissant des valeurs pour les variables maxEpochs (1 000) et l'apprentissage des taux (0,01). Descente de gradient est un processus itératif et maxEpochs variable définit une limite sur le nombre d'itérations. Je vais vous expliquer l'apprentissage taux paramètre plus tard, mais pour maintenant, vous pouvez considérer le taux d'apprentissage comme une valeur qui contrôle combien le changement se produit dans le modèle de régression logistique classifieur dans chaque itération de la formation.

La démo s'entraîne le classifieur et affiche l'erreur du modèle sur les données d'apprentissage, chaque 100 itérations. Descente de gradient peut être utilisé de deux façons différentes pour former un classifieur de régression logistique. L'approche de la première, plus courante, est appelée « stochastique » ou « en ligne » ou « progressive ». (Vocabulaire de ML est chaotique). La deuxième approche est appelée « lot » ou « hors ligne ». Je vais décrire les deux approches plus tard, mais le programme de démonstration utilise l'approche de formation descente stochastique de gradient.

En fin de formation, la démo affiche les meilleures valeurs poids trouvés (-9.84,-14.88... -15.09). Notez les poids du modèle sont tous sur deux fois plus grand que les poids utilisés pour générer les données aléatoires. Le programme de démonstration calcule la précision du modèle qui en résulte sur les données d'apprentissage (99,88 %, soit 7 990 sur 8 000 correct) et l'exactitude des données de test (99,80 %, ou 1 996 de 2.000 correct).

Classification de la régression logistique

Classification de la régression logistique est mieux expliquée à l'aide d'un exemple concret. Supposons que vous souhaitez prédire le sexe d'une personne (male = 0, femelle = 1) fondée sur l'âge (x 1), niveau de revenu annuel (x 2) et l'éducation (x 3). Si Y est la valeur prédite, un modèle de régression logistique pour ce problème prendrait la forme :

Z = b0 + b1(x1) + b2(x2) + b3(x3)
Y = 1.0 / (1.0 + e^-Z)

Ici, b0, b1, b2 et b3 sont poids, qui sont des valeurs numériques juste qui doivent être déterminées. Dans les mots, vous calculer une valeur intermédiaire Z qui est la somme des valeurs d'entrée fois b-poids, ajoutez une constante b0, puis passez la valeur de Z à l'équation qui utilise les mathématiques e constante. L'équation est appelée la fonction sigmoïde logistique. Notez que chaque variable d'entrée (xi) a un poids associé (bi), et que n'est pas un poids supplémentaire (b0) associé à n'importe quelle entrée.

Il s'avère Y sera toujours comprise entre 0 et 1. Si Y est inférieur à 0,5 (proche de 0), vous concluez la sortie prévue est 0 et si Y est supérieur à 0,5, vous concluez que la sortie est 1. S'il y a n éléments, il y aura n + 1 b-poids. Pas toutes les données peuvent être modélisées à l'aide de la régression logistique, mais parce que c'est une des techniques plus simples de classification, régression logistique est un bon point de départ.

Supposons qu'une personne a un âge à l'échelle de x 1 = +0.80 (plus vieux que la moyenne), le revenu annuel de x 2 =-0.50 (légèrement inférieure à la moyenne) et niveau de scolarité x 3 =-1.00 (inférieure à la moyenne). Et supposons que b0 = 3.0, b1 =-2.0, b2 = 2.0 et b3 = 1,5. Alors Z = 3.0 + (-2.0)(0.80) + (2.0)(-0.50) + (1.5)(-1.00) =-1.10 et donc Y = 1,0 / (1. 0 + e^-(-1.10)) = 0,25. Parce que Y est plus proche de 0 (moins de 0,5) que sur 1, vous prédirait que la personne est de sexe masculine.

Voici le code de démo qui implémente informatique sortie de régression logistique :

public double ComputeOutput(double[] dataItem, double[] weights)
{
  double z = 0.0;
  z += weights[0]; // Add b0 constant
  for (int i = 0; i < weights.Length - 1; ++i)
    z += (weights[i + 1] * dataItem[i]); // Skip b0
  return 1.0 / (1.0 + Math.Exp(-z)); // Logistic sigmoid
}

La question est, d'où proviennent les b-poids ? Le processus de détermination des valeurs des b-poids s'appelle le modèle de formation. L'idée est d'utiliser un ensemble de données d'apprentissage qui a connu d'entrée et les valeurs de sortie, puis essayez différentes valeurs pour les b-poids jusqu'à ce que vous trouviez un ensemble de valeurs qui minimise l'erreur entre sorties calculées et les valeurs de sortie correcte connue (souvent appelés les valeurs cibles ou les valeurs souhaitées).

Il est difficile de trouver les valeurs de poids qui minimise l'erreur et il existe de nombreux algorithmes d'optimisation numérique vous pouvez utiliser. Chaque algorithme a différentes forces et faiblesses. Algorithmes d'optimisation les plus courants incluent simplex optimisation, optimisation de L-BFGS, optimisation essaim de particules, itérées de Newton-Raphson, plus une douzaine d'autres. L'algorithme d'optimisation plus fondamental est appelée descente de gradient.

Descente de Gradient de compréhension

Je voudrais essayer d'expliquer la descente du gradient du point de vue du développeur logiciel. Je vais prendre des libertés avec mon explication et la terminologie afin de rendre les idées aussi clair que possible. Regardez le graphique en Figure 2. Le graphique trace l'erreur en fonction de la valeur de certains poids. Comme la valeur d'une variation de poids, erreur du classifieur résultant de la régression logistique va changer. L'objectif est de trouver la valeur de poids lorsque l'erreur est au minimum. Pour Figure 2, ce serait w = 5, 0. Ici, j'utilise w pour indiquer un des b-poids. Notez qu'il y aurait un graphique semblable à celui de Figure 2 pour chaque poids.

Figure 2 dérivées partielles et descente de Gradient

Si vous saviez la forme de tous les graphes d'erreur, déterminer que chaque poids serait facile. Mais, malheureusement, vous ne savez pas la forme d'un graphique de l'erreur. Vous pensez que vous pourriez juste essayer chaque valeur possible de poids et pour en calculer l'erreur qui en résulte, mais il y a un nombre infini de valeurs de poids possible.

Un dérivé de calcul d'une fonction à un moment donné est la pente de la tangente au point. Une pente a un signe (+ ou -) qui indique la direction de la ligne tangente et une ampleur qui indique la pente de la tangente. Par exemple, dans Figure 2, quand w = 7.0, la pente de la tangente (en d'autres termes, la dérivée) est +2.15 (à partir de supérieure droite à inférieur gauche et raide). Quand w =-5.0, le dérivé est-0.90 (du haut gauche au bas à droite et pas trop raide).

Chaque dérivé individuel est appelée une dérivée partielle (ou juste un « partielle » par souci de concision) parce qu'il existe des dérivés pour chaque poids. Un dégradé est la collection de toutes les dérivées partielles. Dans l'usage occasionnel, le gradient de termes et les dérivées partielles sont souvent utilisés indifféremment, surtout parce qu'une phrase comme, "la dérivée partielle de la fonction d'erreur en ce qui concerne les poids b2," est beaucoup plus difficile de dire ou d'écrire que, « le gradient ». Dérivées partielles sont souvent indiquées en utilisant un symbole spécial math qui ressemble à un 6 vers l'arrière.

Alors, quel est le point ? Si vous regardez attentivement Figure 2, vous verrez qu'une dérivée partielle permet de passer d'une valeur de poids donné vers la valeur de poids où l'erreur est réduit au minimum. Le signe de la partielle indique la direction pour se déplacer, et l'ampleur de la partielle donne un soupçon de comment bien se déplacer ; une plus grande ampleur signifie que vous pouvez envisager de déplacer plus loin que d'une magnitude plus petite. Cette technique s'appelle descente de gradient, parce que vous allez vers le bas de la fonction d'erreur vers une valeur minimale.

OK, bien, mais comment cette idée se traduit-il en code utilisable ? Ou, autrement dit, ce qui est le pseudo-code pour mettre à jour un poids de régression logistique ? Il existe de nombreuses ressources sur Internet qui montrent certains calcul assez sophistiqué pour dériver la règle du poids-mise à jour. Le résultat final est :

wj = wj + a * (target - computed) * xj

Dans les mots, "pour le poids jth, la nouvelle valeur de poids est le poids de vieux plus le produit d'une constante « a, » fois la différence entre la valeur de la cible dans les données d'apprentissage et de la valeur calculée, fois la valeur de (d'entrée) de fonctionnalité associée à la masse jth. » La règle de mise à jour est souvent écrit à l'aide de lettres grecques avec thêta (θ) pour le poids et alpha (α) pour la constante. La constante « a » est souvent appelé le taux d'apprentissage.

Supposons que vous travaillez avec un poids où j = 2, b2. Et supposons que la valeur actuelle de b2 est de 0,50. Si, pour quelque élément de données de formation, la valeur cible connue est 1 et la valeur calculée (en utilisant toutes les valeurs x) est de 0,80 et x 2 (la valeur d'entrée unique qui correspond au poids b2) a la valeur 3 et le taux d'apprentissage est de 0,10, puis le nouveau poids de b2 est :

b2 = 0.50 + 0.10 * (1 - 0.80) * 3.0
b2 = 0.50 + 0.06
b2 = 0.56

La règle de mise à jour est appliquée de manière itérative jusqu'à ce qu'une condition d'arrêt est remplie. C'est presque trop simple. Notez que la sortie calculée (0,80) était trop petite par rapport à la sortie de la cible (1.0), donc la règle de mise à jour de poids a augmenté la valeur du poids. Cela aura pour effet d'augmenter la valeur de sortie calculée sur l'itération suivante de la formation. Si la sortie calculée avait été trop grande par rapport à la sortie de la cible, la règle de mise à jour de poids serait avez réduit le poids. Très soignée !

Il y a deux principales façons de tirer à la règle de mise à jour de poids. L'approche la plus courante que vous verrez dans les références sur Internet commence par définir la probabilité d'obtenir un ensemble de données d'apprentissage pour un ensemble donné de valeurs pondérales et utilise ensuite une technique de calcul assez complexe appelée espérance de maximum de vraisemblance pour trouver les valeurs des paramètres qui optimisent la probabilité des données observées.

Une autre approche commence par définir ce que l'on entend par erreur, en utilisant soit deux définitions d'erreur commune — la somme des écarts au carré erreur ou l'entropie croisée. Cette approche utilise ensuite le calcul pour trouver l'ensemble des valeurs de poids qui minimise l'erreur. Lors du démarrage avec croix erreur de l'entropie, la règle de mise à jour de poids qui en résulte est identique à la règle générée en maximisant la probabilité. Lorsque vous démarrez avec la somme d'erreur des écarts au carré, la règle résultant de la mise à jour a deux conditions supplémentaires :

wj = wj + a * (target - computed) * xj * computed * (1 - computed)

Dans la règle de mise à jour de rechange, car le terme calculé est toujours comprise entre 0 et 1, le produit de calculé et (1 - calculé) sera toujours comprise entre 0 et 0,25, ce qui signifie que la mise à jour de poids en utilisant la règle de mise à jour remplaçant juste prend des étapes plus petites que la forme plus simple. Dans la pratique, les deux règles de mise à jour donnent des résultats semblables pour la forme la plus simple est presque toujours utilisée. Heureusement, vous n'avez pas besoin de savoir comment dériver la règle de mise à jour de poids afin de former un classifieur de régression logistique.

L'approche de probabilité-dérivation maximise une probabilité en remontant une pente, elle est appelée gradient ascension. L'approche de dérivation erreur minimise une erreur en descendant une pente et s'appelle descente de gradient. Le point est que vous verrez un classifieur de régression logistique à l'aide d'un gradient de formation dénommé aussi bien la technique de descente de gradient et la technique de l'ascension de gradient. Les deux termes désignent la même règle de mise à jour de poids.

Structure de programme démo

La structure du programme de démonstration, avec quelques modifications mineures pour économiser l'espace, est présentée dans Figure 3. Pour créer la démo, j'ai lancé Visual Studio et sélectionné le modèle Application Console c#. J'ai nommé le projet LogisticGradient. La démo n'a aucune dépendance .NET significatif et ne peut fonctionner n'importe quelle version de Visual Studio . La démo est trop longue pour présenter dans son intégralité, mais tout le code source est disponible dans le téléchargement qui accompagne cet article. J'ai enlevé la vérification pour garder les idées principales et aussi clair que possible d'erreur normal tous.

Figure 3 Structure de programme démo

using System;
namespace LogisticGradient
{
  class LogisticGradientProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin classification demo");
      Console.WriteLine("Demonstrating gradient descent");
      ...
      Console.WriteLine("End demo");
      Console.ReadLine();
    }
    static double[][] MakeAllData(int numFeatures,
      int numRows, int seed) { . . }
    static void MakeTrainTest(double[][] allData, int seed,
      out double[][] trainData, out double[][] testData) { . . }
    static void ShowData(double[][] data, int numRows,
      int decimals, bool indices) { . . }
    static void ShowVector(double[] vector,
      int decimals, bool newLine) { . . }
  }
  public class LogisticClassifier
  {
    private int numFeatures;
    private double[] weights;
    private Random rnd;
    public LogisticClassifier(int numFeatures) { . . }
    public double[] Train(double[][] trainData,
      int maxEpochs, double alpha) { . . }
    private void Shuffle(int[] sequence) { . . }
    private double Error(double[][] trainData,
      double[] weights) { . . }
    private double ComputeOutput(double[] dataItem,
      double[] weights) { . . }
    private int ComputeDependent(double[] dataItem,
      double[] weights) { . . }
    public double Accuracy(double[][] trainData,
      double[] weights) { . . }
  }
}

Une fois le code du modèle chargé, dans la fenêtre de l'Explorateur de solutions, je clic droit sur le fichier Program.cs et rebaptisé à la LogisticGradientProgram.cs plus descriptif et Visual Studio renommé automatiquement la classe Program pour moi. Dans la fenêtre de l'éditeur, en haut du code source, j'ai supprimé tous les inutiles à l'aide de déclarations, laissant juste celui qui référence l'espace de noms System de niveau supérieur.

La classe LogisticGradientProgram contient des méthodes d'assistance MakeAllData, MakeTrainTest, ShowData et ShowVector, qui créer et afficher les données synthétiques. Toute la logique de classement figure dans la classe défini par le programme LogisticClassifier. La méthode Main crée les données synthétiques avec ces déclarations :

int numFeatures = 8;
int numRows = 10000;
int seed = 1; // Arbitrary
double[][] allData = MakeAllData(numFeatures, numRows, seed);

MakeAllData méthode est essentiellement de régression logistique classification en sens inverse. La méthode génère de caractères aléatoires et puis par itération génère des valeurs d'entrée aléatoires, combine les poids et les valeurs d'entrée à l'aide de la fonction sigmoïde logistique et calcule la valeur de sortie correspondante. La méthode n'ajoute pas de bruit aléatoire aux données, ce qui signifie que, en théorie, prédiction 100 % précision est possible. Les données synthétiques sont divisées entre formation et test ensembles, comme suit :

double[][] trainData;
double[][] testData;
MakeTrainTest(allData, 0, out trainData, out testData);
ShowData(trainData, 3, 2, true);
ShowData(testData, 3, 2, true);

Méthode MakeTrainTest utilise une scission de train-test de 80 à 20 pour cent en dur. Vous pouvez passer le pourcentage de la formation en tant que paramètre. Le classificateur de régression logistique est créé et formé avec :

LogisticClassifier lc = new LogisticClassifier(numFeatures);
int maxEpochs = 1000;
double alpha = 0.01; // Learning rate
double[] weights = lc.Train(trainData, maxEpochs, alpha);
ShowVector(weights, 4, true);

Les valeurs de formation paramètres maxEpochs et alpha (le taux d'apprentissage) ont été déterminées par essai et erreur. Mise au point des méthodes de formation ML plus généralement nécessite quelques essais pour obtenir la justesse des prédictions bon. La qualité du modèle formé est évaluée comme suit :

double trainAcc = lc.Accuracy(trainData, weights);
Console.WriteLine(trainAcc.ToString("F4"));
double testAcc = lc.Accuracy(testData, weights);
Console.WriteLine(testAcc.ToString("F4"));

La précision du modèle sur les données de test est le plus pertinent de ces deux valeurs de précision. Il vous donne une estimation approximative du degré de précision le modèle serait quand présenté avec les nouvelles données avec les valeurs de sortie inconnu.

Mise en œuvre de la formation de descente de Gradient

La définition de méthode Train commence par :

public double[] Train(double[][] trainData, int 
  maxEpochs, double alpha)
{
  int epoch = 0;
  int[] sequence = new int[trainData.Length];
  for (int i = 0; i < sequence.Length; ++i)
    sequence[i] = i;
...

Epoch variable est la variable de compteur de boucle de formation. Le tableau nommé la séquence est initialisé avec les indices dans les données d'apprentissage. L'idée ici est que les données d'apprentissage seront traitées dans un ordre différent, au hasard à chaque itération. Ensuite, la boucle principale poids-mise à jour commence :

while (epoch < maxEpochs)
{
  ++epoch;
  if (epoch % 100 == 0 && epoch != maxEpochs)
  {
    double mse = Error(trainData, weights);
    Console.Write("epoch = " + epoch);
    Console.WriteLine(" error = " + mse.ToString("F4"));
  }
  Shuffle(sequence); // Process data in random order
...

Une mesure d'erreur est calculée et affichée chaque 100 époques. Erreur de méthode renvoie l'erreur quadratique moyenne, qui est la moyenne de la somme des différences quadratiques entre calculées et les valeurs de sortie cible. Notez que c'est un peu différente de la définition de l'erreur qui est le fondement de la règle de mise à jour de poids de descente de gradient. Lorsque vous utilisez entraînement de descente de gradient, l'erreur est implicitement utilisée, mais n'est pas utilisée directement. Autres techniques de formation, en optimisation essaim de particules particulières, utilisent l'erreur explicitement. Méthode Shuffle brouille les indices de données de formation contenus dans le tableau de séquence à l'aide de l'algorithme de Fisher-Yates.

Le cœur de l'entraînement de descente de gradient est court :

for (int ti = 0; ti < trainData.Length; ++ti)
{
  int i = sequence[ti];
  double computed = ComputeOutput(trainData[i], weights);
  int targetIndex = trainData[i].Length - 1;
  double target = trainData[i][targetIndex];
  weights[0] += alpha * (target - computed) * 1;
  for (int j = 1; j < weights.Length; ++j)
    weights[j] += alpha * (target - computed) * trainData[i][j - 1];
}

Tout d'abord, l'ordre du jour un ordre aléatoire formation est identifié en utilisant le tableau de séquence brouillés. Méthode ComputeOutput utilise les poids actuels pour calculer la sortie pour le jeu actuel des valeurs de poids, qui sera une valeur comprise entre 0,0 et 1,0. La valeur cible, 0 ou 1, est extraite de l'élément actuel de la formation. Le poids de b0 est tout d'abord mis à jour. Rappelons que la règle de mise à jour de poids utilise la valeur d'entrée associée à la masse en cours de modification. Cependant, le poids de b0 n'est pas associé à n'importe quelle entrée réelle. Pour gérer cela, poids de b0 de régression logistique sont dit d'avoir une valeur d'entrée factice toujours égale à 1.0. Le code de démo multiplie par la 1,0 valeur, ce qui évidemment n'a pas d'effet, pour illustrer la similitude entre la mise à jour de b0 et mise à jour de n'importe quel autre b-poids. Mise à jour régulières b-poids est assez simple et exige seulement une attention aux détails d'indexation. Train de la méthode se termine par :

...
} // While loop
  return this.weights;
} // Train

La méthode retourne une référence aux poids réels dans le tableau de poids LogisticClassifier. Pour la sécurité, vous pouvez envisager la création d'un tableau de résultats, puis copier les poids dans ce tableau et retourne une référence au tableau.

Tel que mentionné précédemment, la démonstration utilise la descente stochastique de gradient. Comme chaque élément de la formation est rencontrée, le gradient pour cet élément d'une formation est calculé et utilisé pour mettre à jour tous les poids. Dans la descente de gradient de lot, en revanche, à chaque itération, dégradés sont accumulées au fil de tous les éléments de la formation tout d'abord, et puis les pondérations sont mises à jour. Pour utiliser la formation du lot, au cœur de la méthode Train allait devenir le code indiqué dans Figure 4.

Figure 4 la méthode de Train lors de l'utilisation de formation lot

double[] accumulatedGradients = new double[weights.Length];
for (int i = 0; i < trainData.Length; ++i)  // Accumulate
{
  double computed = ComputeOutput(trainData[i], weights);
  int targetIndex = trainData[i].Length - 1;
  double target = trainData[i][targetIndex];
  accumulatedGradients[0] += (target - computed) * 1; // For b0
  for (int j = 1; j < weights.Length; ++j)
    accumulatedGradients[j] += (target - computed) * trainData[i][j - 1];
}
for (int j = 0; j < weights.Length; ++j) // Update all wts
  weights[j] += alpha * accumulatedGradients[j];

Avec formation de lot, parce que tous les éléments de formation sont traités avant que les masses sont mises à jour, n'a aucun intérêt à traiter les données de formation dans un ordre aléatoire.

Lors de l'entraînement de descente de gradient a été conçu tout d'abord, l'approche de traitement par lots a été jugé théoriquement préférable parce que cette technique utilise toutes les informations disponibles pour trouver le gradient de poids. Cependant, praticiens ML vite rendu compte que la vitesse de formation pourrait être augmentée en utilisant le gradient pour juste un élément de formation unique comme une estimation pour la pente globale. En d'autres termes, stochastiques (qui signifie déterminé aléatoirement) descente de gradient utilise un dégradé pour estimer la pente globale.

Récapitulation

Deux variations connexes de base descente de gradient qui sont souvent utilisées avec les classificateurs de régression logistique sont appelées BFGS et L-BFGS. Ces deux algorithmes sont une tentative pour améliorer sur base descente de gradient, au détriment de la complexité accrue de façon significative.

En plus de la classification de la régression logistique, descente de gradient peut être utilisé avec plusieurs autres techniques de ML. En particulier, la descente de gradient peut être utilisé pour former un réseau de neurones. Descente de gradient est utilisée avec des réseaux de neurones, la technique est appelée rétropropagation.

Dr. James McCaffrey travaille pour Microsoft Research à Redmond, Washington Il a travaillé sur plusieurs produits Microsoft, y compris Internet Explorer et Bing. Dr. McCaffrey est joignable au jammc@microsoft.com.

Grâce à l'expert technique suivante Microsoft Research pour avoir relu cet article : Richard Hughes

Partager via