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 portera entièrement sur les fondamentaux, ce qui manque selon moi à beaucoup de ressources en ligne sur le Machine Learning et les Réseaux Neuronaux.

Lorsque j’ai cherché à apprendre les réseaux neuronaux, je n’ai trouvé que des articles qui soit

Montraient quelques lignes de code Tensorflow pour charger des données d’entraînement, entraîner le modèle et faire 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 ne vous traînait à 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 maths
La traduire en code, entièrement en C, sans aucune bibliothèque pour qu’aucun détail d’implémentation ne soit caché

Connaissances prérequises

Je vais faire les hypothèses 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 ex. $\frac{d}{d x}$ ) et les dérivées partielles (par ex. $\frac{\partial}{\partial x}$ )

Introduction

Nous commençons donc par quelque chose d’aussi banal que la régression linéaire ; quel est le rapport avec l’apprentissage automatique ? En quoi cela m’aidera-t-il à créer le prochain ChatGPT ??

Pour être cliché, demandons à ChatGPT ce qu’il pense que l’apprentissage automatique est :

Quelle est la définition la plus fondamentale et minimale du terme “Apprentissage automatique” ?

L’apprentissage automatique est un processus par lequel 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. Autrement dit, nous voulons que notre modèle apprenne à prédire des résultats à partir de 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 chapeau
}

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 des maisons correspondants, 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éfinir “optimal” ? C’est le modèle le moins mauvais ou celui avec l’erreur la plus petite. Mais comment définir “erreur” ? Une façon est

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

Le problème avec cette définition est que minimiser l’erreur conduirait la prédiction optimale de notre modèle à être $- \infty$ , ce qui est l’erreur minimale, mais pas ce que nous recherchons. Nous voulons une fonction d’erreur qui soit convexe, c’est-à-dire qui ait 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$ . Minimiser cette fonction nous donnerait donc le modèle optimal. Désormais, 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-la la fonction d’erreur totale, $J_{w b}$ .

$$ J(w, b) = \frac{1}{m} \sum_{i=0}^{m-1} (\hat{y}^{(i)} - y^{(i)})^2


```c
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 amener ce nombre à zéro.

Minimiser l’Erreur

La Méthode Naïve

Une approche naïve pour réaliser cela serait de générer un grand nombre de linear_model avec une plage de w et de b, et de voir lequel présente la plus petite erreur pour notre jeu 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 l'erreur la plus faible
		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-la sur notre jeu de données :

Modèle d'optimisation par force brute : {w: 0.400000, b: 331.800000}
Erreur : 88068.508000

À quel point prédit-elle bien ?

Plutôt bien ! Et nous savons que l’optimum théorique se trouve à $\pm increment$ ou $\pm 0.2$ des valeurs données.

Mais soyons honnêtes : c’est une solution extrêmement sous-optimale. La complexité temporelle est en $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 en $O (n^{10})$ . Cela la rend extrêmement impraticable lorsque nous avons de multiples 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 deviner littéralement chaque nombre.

Attention : du calcul différentiel (😱) arrive

Je plaisante.

Imaginez ceci : vous êtes parachuté à un endroit aléatoire au milieu d’une région vallonnée. On vous a dit qu’il y avait une vallée quelque part. 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, vous ne pouvez donc voir qu’à un rayon d’un pied autour de vous. Comment pouvez-vous trouver la vallée, si tout ce que vous savez, c’est qu’elle se trouve au point le plus bas de la région ?

Stratégie :

Regardez autour de vous sur le sol
Dans quelle direction la pente descend-elle le plus abruptement ?
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. Rebondissement : la région vallonnée s’appelle en réalité les collines de l’erreur et votre stratégie s’appelle la descente de gradient ! C’est l’heure des maths.

Mathématiques

Nous devons d’abord voir l’effet d’une légère modification de $b$ sur l’erreur. C’est la dérivée de la fonction d’erreur par rapport à $b$ . En résolvant

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 modifier $w$ , calculons donc 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 ici les règles du produit et de la chaîne. Ainsi, ces deux dérivées répondent à la question : “Si j’augmente un peu la variable, de combien l’erreur augmente-t-elle ?”. Or, nous voulons que l’erreur diminue, nous devons donc prendre la direction opposée.

Algorithme :

Définir le point de départ : $w := 0, b := 0$
Déplacer 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}$
Aller à l’étape 2.

Ce qui finira par arriver, c’est que les dérivées approcheront de 0 lorsque $w$ et $b$ seront à leur minimum. En effet, à un minimum (ou au fond de la vallée), peu importe la direction que vous prenez, l’erreur ne changera pas significativement.

Code

Commençons par écrire 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 pour 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 une colline d’erreur, la vallée faisait un kilomètre de large et que vous ne pouviez vous déplacer que d’un kilomètre à la fois dans une seule direction. Vous n’atteindriez probablement pas le fond.

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

Modèle d'optimisation par descente de gradient : {w: 0.451677, b: 124.026882}
Erreur : 85341.496159

Super ! Nous avons obtenu une erreur bien plus faible avec cette méthode. Mais surtout, sa complexité algorithmique n’est pas démesurée. Elle est de $O (n \cdot d)$ pour $n$ itérations et $d$ paramètres.

Ceci—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 & Prochaines étapes

Comme vous pouvez le constater, la descente de gradient est assez logique, du moins avec un modèle aussi simple. Pour la partie suivante, les choses vont se compliquer un peu, mais resteront, je l’espère, gérables. Nous allons nous pencher sur la régression linéaire multivariée, où plus d’une variable affecte la valeur de sortie, c’est-à-dire le nombre de chambres, la taille du terrain, la distance du centre-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 de votre lecture.

Aller à la Partie 2

✦ Aucune IA n'a été utilisée dans la conception, la recherche, la rédaction ou l'édition de cet article.