tpOptimisation.md

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.