---
author:
- Mathématiques en technologie de l'information
title: Travail pratique - Optimisation
autoSectionLabels: false
autoEqnLabels: true
eqnPrefix:
    - "éq."
    - "éqs."
chapters: true
numberSections: false
chaptersDepth: 1
sectionsDepth: 3
lang: fr
documentclass: article
papersize: A4
cref: false
urlcolor: blue
toc: false
include-before: <script src="css/prism.js"></script>
---
\newcommand{\dd}{\mathrm{d}}
\newcommand{\real}{\mathbb{R}}
\newcommand{\integer}{\mathbb{Z}}
\renewcommand{\natural}{\mathbb{N}}
\newcommand{\complex}{\mathbb{C}}
\newcommand{\vectwo}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}


# Objectif

Réaliser un programme permettant de réaliser une régression linéaire
à une dimension à l'aide de la méthode de la descente de gradient.
Tester ce programme sur des données synthétiques afin de valider
votre implémentation.

# Travail à réaliser

## La régression linéaire à une seule variable

### Solution analytique 

Afin de *valider* votre implémentation, il faut d'abord
étudier un cas simplifié où trouver la solution analytique
est aisé. 

On va chercher "la meilleure droite"
passant par un ensemble de points $\{(x_j, y_j)\}_{j=1}^N$.
Comme on l'a vu en cours, on cherche à minimiser la fonction
$$
E(a,b)=\sum_{j=1}^N(a\cdot x_j + b - y_j)^2.
$$
En résolvant, le système de deux équations à deux inconnues
$$
\vec\nabla E(a, b)=\vec 0,
$$
on peut trouver la valeur de $a$ et $b$ pour n'importe quel
ensemble de points $\{(x_j, y_j)\}_{j=1}^N$.

Votre premier exercice sera de trouver l'expression de $a$ 
et $b$ en fonction de $\{(x_j, y_j)\}_{j=1}^N$.

### Solution numérique

En prenant comme référence la solution ci-dessus,
il faut à présent implémenter la méthode de la descente de gradient
pour minimiser $E(a,b)$.
En partant d'une pente $a_0$ et d'une ordonnée à l'origine $b_0$,
il faut itérativement construire de meilleures approximations
$$
\vectwo{a_{i+1}}{b_{i+1}}=\vectwo{a_i}{b_i}-\lambda \cdot \vec\nabla E(a_i, b_i),
$$
avec $i\leq 1$ et $\lambda\in[0,1)$. On arrêtera les itérations
lorsque
$$
\left|\left|\vectwo{a_{i+1}}{b_{i+1}}-\vectwo{a_i}{b_i}\right|\right|<\varepsilon,
$$
où $\varepsilon>0$ est la précision souhaitée.

### Test

Afin de tester votre programme, vous devez générer un nuage de points.
Pour contrôler au mieux ce qui se passe, il est recommandé
de générer des points aléatoirement le long d'une droite,
et de bruiter un peu le résultat. Vous choisissez
$x_j$ entre deux bornes de votre choix (p.ex. 0 et 10)
puis tirez un certain nombre de $x_j$. A partir de là
vous construisez $y_j$ comme
$$
y_j=c\cdot x_j+d + r_j,
$$
où $|r_j|$ est un "petit" nombre aléatoire devant $(c\cdot x_j+d)$, et $c$ et $d$ 
(la pente et l'ordonnée à l'origine de votre droite) sont choisis par vos soins.

Il faut vous assurer que la solution analytique et la solution numérique
soient très proches (à $\varepsilon$ près) et qu'elles soient également assez proches
du $c$ et du $d$ que vous avez choisis.

Tester votre code sur différentes valeurs de $c$ et $d$. Est-ce
que vos résultats sont toujours cohérents? Quelle est la valeur
de l'erreur moyenne? Qu'est-ce que l'erreur signifie?
Faites également varier la valeur maximale de $|r_j|$. Que se passe-t-il
quand $|r_j|$ devient trop grand? N'hésitez pas à représenter
graphiquement vos résultats.

## Validation du modèle de régression

Lorsqu'on réalise une régression, on *modélise*
notre nuage de points. Ici, on dit que le phénomène
qui a généré les points suit une droite plutôt qu'une parabole ou une exponentielle
ou n'importe quelle autre fonction. Afin de s'assurer
que notre modèle correspond relativement bien à notre
jeu de donnée, on peut faire ce qu'on appelle une *validation croisée*
(ou *cross validation* en bon français).
Cette technique est très utilisée en apprentissage automatique.
Il en existe un grand nombre de variantes, ici nous n'en verrons qu'une.

Il s'agit ici de vérifier si le $a$ et le $b$ que nous avons
déterminés sont des valeurs qui continueraient à être correctes
si on ajoutait de nouveaux points à notre ensemble $\{(x_j, y_j)\}_{j=1}^N$.
Il est souvent peu pratique de générer de nouveaux points, on se contente
donc de diviser notre jeu de données en plusieurs partie. Une partie
des points sera utilisée pour *entraîner* notre modèle (déterminer
un $a$ et un $b$) l'autre partie sera utilisée pour tester le modèle,
on calculera l'erreur effective $E(a,b)$ par rapport à cette seconde
partie des points.

Ici, pour simplifier on va séparer notre ensemble de $N$ points
en trois groupes de taille égale et en répartissant les points aléatoirement
dans les groupes. Nommons les groupes $G_1$, $G_2$, et $G_3$. Pour effectuer
la validation croisée, il faut réaliser les étapes suivantes:

* entraîner le modèle avec les groupes $G_1\cup G_2$ et tester sur $G_3$,
* entraîner le modèle avec les groupes $G_1\cup G_3$ et tester sur $G_2$,
* entraîner le modèle avec les groupes $G_2\cup G_3$ et tester sur $G_1$.

Pour les nuages de point générés à la section précédente,
quelle est la valeur de l'erreur pour chacun des groupes de tests?
(Donner les valeurs sous forme de tableau peut être une bonne idée.)
Comment interprétez vous ces résultats? N'hésitez pas à représenter
graphiquement vos résultats.

# Rendu

Il faut rendre un rapport de quelques pages (quelques: **plus petit** que 6).
Ce rapport doit être relativement bref et expliquer votre travail.
Il doit être composé de quatre parties principales:

1. Une introduction générale qui décrit le cadre général du travail (ce que vous essayez de réaliser, par quels moyens, etc) et donner la structure de votre rapport (que contient chaque autre partie).
2. Une partie "théorique" décrire les concepts et méthodes que vous utilisez si cela est nécessaire afin de permettre une bonne compréhension du reste de votre travail par le lecteur. Ceci est nécessaire pour comprendre comment vous arrivez aux résultats que vous présentez dans la partie suivante.
3. Une partie résultats, où vous donnez les résultats que vous avez obtenus. Par exemple, répondre aux différentes questions posées dans cet énoncé,
mais n'hésitez pas à développer. 
4. Une conclusion où vous résumez les résultats principaux de votre travail et éventuellement ouvrez sur comment vous pourriez améliorer votre travail ou l'étendre.

Le code doit être réalisé en C (afin de vous entraîner). La visualisation peut être
faite avec l'outil de votre choix. Python avec la librairie *matplotlib* peut-être un bon choix.

Vous **devez** faire ce travail par groupe de 2 et aucune exception ne sera faite.
Vous devez rendre le rapport sur `cyberlearn`. Le code doit être dans un repo git public
dont vous mettrez l'url sur `cyberlearn`. N'oubliez pas de bien spécifier le nom
des deux membres du groupe dans le rapport et dans le code. Je devrais pouvoir 
compiler et exécuter votre projet (pensez évidemment à créer un `Makefile`).

La note est une combinaison de la note du code et du rapport.


# Conseils et remarques

Ce travail est loin d'être simple à réaliser. Il demande de combiner
beaucoup de concept vu ou pas en détail en cours. Utilisez le temps à disposition
pendant les séance pour poser des questions et n'attendez pas le dernier moment.

La rédaction du rapport est également une tâche complexe et il s'agit de ne pas bâcler
sa réalisation. C'est un exercice qui vous sera utile lorsque vous devrez écrire votre
mémoire pour votre travail de bachelor.