Fondamentaux du Machine Learning en C, Partie 1Draft

9 août 2023

Bienvenue dans ma série en N parties (N à déterminer) sur les Fondamentaux du Machine Learning en C. Cette série sera entièrement axée sur les fondamentaux, ce qui, selon moi, manque dans de nombreuses ressources en ligne concernant le Machine Learning et les réseaux de neurones.

Lorsque j’ai commencé à m’intéresser aux réseaux de neurones, tout ce que j’ai trouvé, ce sont des articles qui soit

Montraient quelques lignes de code Tensorflow pour récupérer des données d’entraînement, entraîner le modèle et exécuter des prédictions, ou
Des tutoriels de bas niveau qui donnaient des détails d’implémentation, mais me laissaient avec plus de questions que de réponses

Aucun d’entre eux ne vous guidait à travers les concepts élémentaires (plutôt ennuyeux) qui mènent à Le Neurone. C’est ce que je vise à faire avec cette série. Elle va

Construire une intuition, avec une quantité raisonnable de mathématiques
La traduire en code, entièrement en C, avec zéro bibliothèque pour qu’aucun détail d’implémentation ne soit caché

Connaissances prérequises

Je vais supposer les choses suivantes à votre sujet

Vous êtes familier avec le C, ou un langage de type C (C++, Java, C#, etc.)
Vous comprenez les dérivées (par exemple $\frac{d}{d x}$ ) et les dérivées partielles (par exemple $\frac{\partial}{\partial x}$ )

Introduction

Nous commençons donc avec quelque chose d’aussi banal que la régression linéaire ; en quoi cela a-t-il un rapport avec le machine learning ? Comment cela m’aidera-t-il à créer le prochain ChatGPT ??

Pour être cliché, demandons à ChatGPT ce qu’il pense du machine learning :

Quelle est la définition la plus fondamentale et minimale du terme “Machine learning” ?

Le machine learning est un processus où les ordinateurs apprennent à partir de données pour améliorer leurs performances sur des tâches sans être explicitement programmés (c’est moi qui souligne).

La tâche sur laquelle cette série se concentrera est la prédiction. C’est-à-dire que nous voulons que notre modèle apprenne à prédire des résultats à partir de certaines données d’entrée. Et à mesure que nous lui fournissons plus de données, il devrait, sans programmation explicite, devenir meilleur pour faire des prédictions sur des données qu’il n’a jamais vues.

Commençons par définir un modèle simple.

Le modèle linéaire à une variable

Code pour la partie 1

Ce modèle est conçu pour une tâche de prédiction qui a) n’a qu’une seule variable d’entrée, b) n’a qu’une seule variable de sortie, et c) la relation entre les variables d’entrée et de sortie est approximativement linéaire. Il est défini comme suit.

\overset{y}{^} = w x + b

Et en code :

struct linear_model {
	double w;
	double b;
};

double predict(struct linear_model m, double x) {
	return m.w * x + m.b; // y hat
}

Comme vous pouvez le voir, le modèle lui-même est défini par deux paramètres, $w$ et $b$ , qui déterminent comment la sortie prédite $\overset{y}{^}$ est liée à l’entrée $x$ . Pour tester le modèle, fabriquons quelques données.

// Tailles des maisons, en pieds carrés. Notre variable x
static double xs[] = {2360, 5272, 4592, 1966, 5926, 4944, 4671, 4419, 1630, 3185};
// Prix correspondants des maisons, en milliers de dollars. Notre variable y
static double ys[] = {1359, 2576, 2418, 655, 2531, 2454, 2657, 1541, 1057, 1657};

Notre tâche est maintenant de prédire les prix des maisons en fonction de leur taille, nous devons donc trouver un $w$ et un $b$ qui définissent un modèle “optimal”. Mais comment définissons-nous “optimal” ? C’est le modèle le moins mauvais ou le modèle avec la plus petite erreur. Mais comment définissons-nous “erreur” ? Une façon est

erreur = valeur pr \overset{e}{ˊ} dite - valeur r \overset{e}{ˊ} elle

Le problème avec cela est que minimiser l’erreur ferait que la prédiction optimale pour notre modèle serait $- \infty$ , ce qui est l’erreur minimale, mais pas ce que nous recherchons. Ce que nous voulons, c’est une fonction d’erreur qui soit concave, ce qui signifie qu’elle a une valeur minimale bornée qui reflète réellement une bonne performance.

erreur = (valeur pr \overset{e}{ˊ} dite - valeur r \overset{e}{ˊ} elle)^{2}

La valeur minimale de cette fonction est $0$ , et si $erreur \approx 0$ alors $valeur pr \overset{e}{ˊ} dite \approx valeur r \overset{e}{ˊ} elle$ . Donc, minimiser cette fonction nous donnerait le modèle optimal. À partir de maintenant, nous appellerons cela la fonction de perte.

double loss(double y_hat, double y) {
	double diff = y_hat - y;
	return diff * diff;
}

Mais nous voulons minimiser la perte sur tous les échantillons de données que nous avons. Prenons donc la perte moyenne sur tous les $m$ échantillons, et appelons cela la fonction d’erreur totale, $J_{w b}$ .

J (w, b) = \frac{1}{m} i = 0 \sum m - 1 (\overset{y}{^}^{(i)} - y^{(i)})^{2}

double error(struct linear_model model, double *xs, double *ys, int m) {
	double sum = 0.0;
	for (int i = 0; i < m; i++) {
		double y_hat = predict(model, xs[i]);
		double _loss = loss(y_hat, ys[i]);
		sum += _loss;
	}
	return sum / ((double) m);
}

Cela nous donne un seul nombre qui nous indique à quel point le modèle est mauvais. Maintenant, nous devons réduire ce nombre à zéro.

Minimisation de l’erreur

La méthode naïve

Une approche naïve pour y parvenir serait de générer un grand nombre de linear_model avec une plage de w et de b, et de voir lequel a la plus petite erreur pour notre ensemble de données.

struct linear_model
optimize_brute_force(double *xs, double *ys, int m)
{
		const double min = -1000.0, max = 1000.0;
		const int num_samples = 1e4;
		const double increment = (max - min) / ((double)num_samples);

		double min_error = 1e10;
		struct linear_model curr;
		struct linear_model optimal;
		// Itérer à travers (w, b) dans [min, max] x [min, max]
		// et trouver la paire avec la plus petite erreur
		for (int i = 0; i < num_samples; i++) {
				curr.w = min + increment * i;
				for (int j = 0; j < num_samples; j++) {
						curr.b = min + increment * j;

						double err = error(curr, xs, ys, m);
						if (err < min_error) {
								min_error = err;
								optimal = curr;
						}
				}
		}
		return optimal;
}

Exécutons-le sur notre ensemble de données :

Optimisation par force brute : {w: 0.400000, b: 331.800000}
Erreur : 88068.508000

À quel point prédit-il bien ?

Plutôt bien ! Et nous savons que l’optimum théorique est à $\pm incr \overset{e}{ˊ} ment$ ou $\pm 0.2$ des valeurs données.

Mais soyons honnêtes : c’est une solution extrêmement sous-optimale. Le temps d’exécution est $O (n^{2})$ par rapport au nombre d’échantillons, ce qui n’est pas terrible si nous n’avons que deux paramètres $w$ et $b$ . Mais si nous en avions, disons 10, ce serait $O (n^{10})$ . Cela le rend extrêmement impraticable lorsque nous avons plusieurs variables d’entrée, ce qui est le cas de presque tous les problèmes du monde réel.

Descente de gradient

Nous devons donc trouver une méthode plus intelligente que de simplement deviner chaque nombre.

Attention : du calcul (😱) vous attend

JK.

Imaginez ceci : vous êtes largué à un endroit aléatoire au milieu d’une région vallonnée. On vous a dit auparavant que quelque part, il y a une vallée. Et dans cette vallée, il y a de la nourriture et de l’eau. Et si vous ne trouvez pas la vallée, vous mourrez. De plus, il y a un brouillard extrêmement épais, donc vous ne pouvez voir qu’à un rayon de 1 pied autour de vous. Comment pouvez-vous trouver la vallée, si tout ce que vous savez, c’est qu’elle est au point le plus bas de la région ?

Stratégie :

Regardez autour de vous sur le sol
Dans quelle direction y a-t-il la descente la plus raide ?
Déplacez-vous d’un pied dans cette direction
Retournez à l’étape 1

Tant que la vallée existe, cela vous mènera au fond. Twist : la région vallonnée s’appelle en fait les collines d’erreur et votre stratégie s’appelle la descente de gradient ! C’est l’heure des maths.

Maths

Nous devons d’abord voir l’effet qu’un petit changement de $b$ a sur l’erreur. C’est la dérivée de la fonction d’erreur par rapport à $b$ . Résolvons

J (w, b) = \frac{1}{m} i = 0 \sum m - 1 (\overset{y}{^}^{(i)} - y^{(i)})^{2} = \frac{1}{m} i = 0 \sum m - 1 (w x^{(i)} + b - y^{(i)})^{2}

\frac{\partial J}{\partial b} = 2 \frac{1}{m} i = 0 \sum m - 1 (w x^{(i)} + b - y^{(i)})

Nous devons aussi changer $w$ , donc calculons la dérivée de l’erreur par rapport à $w$ .

\frac{\partial J}{\partial w} = 2 \frac{1}{m} i = 0 \sum m - 1 (w x^{(i)} + b - y^{(i)}) x^{(i)}

Nous utilisons simplement les règles du produit et de la chaîne ici. Donc, ces deux dérivées répondent à la question : “Si j’augmente un peu la variable, de combien l’erreur augmente-t-elle ?”. Maintenant, nous voulons que l’erreur diminue, donc nous devrions prendre la direction opposée.

Algorithme :

Fixez le point de départ : $w := 0, b := 0$
Déplacez les variables dans la direction opposée aux dérivées, avec un pas de taille $α$ : $w := w - α \frac{\partial J}{\partial w}, b := b - α \frac{\partial J}{\partial b}$
Retournez à l’étape 2.

Ce qui finira par se produire, c’est que les dérivées approcheront 0 lorsque $w, b$ seront à leur minimum. C’est parce qu’à un minimum (ou au fond de la vallée), quelle que soit la direction dans laquelle vous allez, l’erreur ne changera pas de manière significative.

Code

Écrivons d’abord une fonction qui calcule les dérivées, que nous allons encapsuler dans une structure appelée gradient.

struct gradient {
		double dJ_dw;
		double dJ_db;
};

struct gradient
calculate_gradient(struct linear_model model, double *xs, double *ys, int m)
{
		double dJ_dw = 0.0, dJ_db = 0.0;
		for (int i = 0; i < m; i++) {
				double y_hat = predict(model, xs[i]);
				double diff = y_hat - ys[i];
				dJ_db += diff;
				dJ_dw += diff * xs[i];
		}
		// Nous allons intégrer ce facteur de 2 dans alpha pour économiser une multiplication
		dJ_dw /= ((double)m);
		dJ_db /= ((double)m);
		return (struct gradient){.dJ_dw = dJ_dw, .dJ_db = dJ_db};
}

Ensuite, utilisons cela pour exécuter notre algorithme de descente de gradient.

struct linear_model
optimize_gradient_descent(double *xs, double *ys, int m, int num_iterations, double alpha)
{
		struct linear_model model = {0.0, 0.0};
		for (int i = 0; i < num_iterations; i++) {
				struct gradient g = calculate_gradient(model, xs, ys, m);
				model.w -= alpha * g.dJ_dw;
				model.b -= alpha * g.dJ_db;
		}
		return model;
}

Les valeurs de num_iterations et alpha doivent être ajustées expérimentalement. alpha est le taux d’apprentissage. S’il est trop faible, l’algorithme nécessitera plus d’étapes (et plus de temps) pour atteindre la vallée d’erreur. S’il est trop élevé, l’algorithme ne convergera pas. C’est comme si, sur la colline d’erreur, la vallée faisait un demi-mile de large et que vous ne pouviez vous déplacer que d’un mile à la fois dans une direction. Vous n’atteindrez probablement pas le fond.

Essayons num_iterations = 1e8 et alpha = 1e-7

Optimisation par descente de gradient : {w: 0.451677, b: 124.026882}
Erreur : 85341.496159

Cool ! Nous avons obtenu une erreur beaucoup plus faible avec cette méthode. Mais plus important encore, elle n’a pas un temps d’exécution en O(n) fou. C’est $O (n \cdot d)$ pour $n$ itérations et $d$ paramètres.

Cela—la descente de gradient—est l’algorithme fondamental qui permet aux machines d’apprendre par elles-mêmes. Il indique au programme comment il doit ajuster son modèle interne pour mieux correspondre au résultat attendu.

Conclusion & La suite

Comme vous pouvez le voir, la descente de gradient est assez logique, du moins lorsque nous avons un modèle aussi simple. Pour la prochaine partie, les choses deviendront un peu plus compliquées, mais resteront, espérons-le, gérables. Nous examinerons la régression linéaire multivariée, où vous avez plus d’une variable affectant la valeur de sortie, c’est-à-dire le nombre de chambres, la taille du terrain, la distance de la ville, etc.

Si quelque chose dans l’article n’était pas clair, veuillez commenter ci-dessous et je ferai de mon mieux pour clarifier. Si vous avez des suggestions, faites-le moi savoir ! Merci d’avoir lu.

Aller à la partie 2

✦ No LLMs were used in the ideation, research, writing, or editing of this article.