Écrire un programme permettant à l'Ergo Jr de déterminer par apprentissage automatique la meilleure façon de lancer une balle pour atteindre une cible dans une direction fixée. La cible est posée à une distance aléatoire de l'Ergo Jr.
Une explication plutôt claire et simple des différentes catégories d'apprentissage
https://makina-corpus.com/blog/metier/2017/initiation-au-machine-learning-avec-python-theorie
La meilleur technique pour l'objectif envisagé semble être l'apprentissage par renforcement
Des références :
http://www.grappa.univ-lille3.fr/~coulom/Renforcement/
https://members.loria.fr/VThomas/mediation/ISN_2017_comportement/
Q-learning
https://studywolf.wordpress.com/2012/11/25/reinforcement-learning-q-learning-and-exploration/
reseau neurones
https://www.miximum.fr/blog/introduction-au-deep-learning-1/
http://mp.cpgedupuydelome.fr/document.php?doc=Article%20-%20Les%20r%C3%A9seaux%20de%20neurones.txt
Features en anglais ou variables explicatives en français sont les variables accessibles, que l'on peut mesurer. Elles correspondent aux données que l'on cherche à prédire. Dans notre cas les angles des moteurs pour réaliser un lancé gagnant.
Soit $f$ la fonction de transfert suivante : $$ \forall x\in\mathbb{R},\ f_H: x\mapsto \left\{ \begin{array}{cccl} 0 & \text{si} & x < 0 \\ 1 & \text{si} & x \geq 0 \\ \end{array}\right. $$
Perceptron : L'objectif est d'implanter un perceptron à seuil (neurone simple à seuil) pour résoudre les problèmes de tri entre deux classes (ensembles d'élement) linéairements séparables.
L'unique fonction de ce neurone est de fournir une sortie égale à $1$ ou $0$, on parle alors de neurone activé pour la valeur $1$ et de neurone non actif pour la valeur $0$.
Pour cela on effectue la somme $S = b + \sum\limits_{i=1}^n x_i\,\omega_i$, avec $b$ le poids associé à l'entrée de biais du neurone artificiel. La valeur de l'entrée de biais est fixée à 1. Connaissant cette somme on décide d'activer ou non notre neuron en fonction d'un seuil d'activation $\theta$, fixé au préalable.
Pour décider de l'activation de notre neurone on utilise la fonction de transfert HeavySide notée $f_H$ de type seuil qui renvoie
heaviside :$\hphantom{000000000000000000000000000}$ | Graphique : |
---|---|
$$ y_H=f_H(S)=\left\{\begin{array}{cccl}0 & \text{si} & S < 0 \\1 & \text{si} & S \geq 0 \\ \end{array}\right.$$ |
Remarques :
heaviside :$\hphantom{000000000000000000000000}$ | Graphique : |
---|---|
$$ y_H=\left\{\begin{array}{cccl}0 & \text{si} & S < \theta \\1 & \text{si} & S \geq \theta \\ \end{array}\right.$$ |
L'algorithme consiste à donner des valeurs d'apprentissage au perceptron et comparer la sortie de la fonction Heaviside notée $y_H$ à la sortie attendue que l'on peut lire dans les valeurs d'apprentissage notée $y_v$.
La différence $\Delta y = y_v - y_H$, introduit une notion d'erreur permettant par la suite de corriger (ou pas) les poids attribués à chaque valeur d'entrée du neurone
Afin de mesurer l’erreur commise sur l’ensemble d’un jeu de données, il est nécessaire de se fixer une fonction de perte qui mesure le coût d’une erreur lors de la prédiction d’un exemple.Pour cela nous allons nous intéresser à la fonction de perte liée à l'erreur quadratique $$E(y_v, f_H(b + \sum\limits_{i=1}^n x_i\,\omega_i)) = \dfrac{1}{2}(y_v-f_H(b + \sum\limits_{i=1}^n x_i\,\omega_i))^2=\dfrac{1}{2}(y_v-y_s)^2$$
La mise à jour des poids revient à minimiser la valeur de sortie de la fonction d'erreur que nous pouvons approcher grâce à la méthode de descente de gradient. Cet ajustement des poids se fera pour chaque n-uplet de valeurs en entrée du perceptron.
Commençons par évaluer $\dfrac{\partial E}{\partial \omega_i}$ pour une fonction d'activation quelconque de classe $\mathcal{C}^1$ notée $f$, nous reviendrons sur le cas particulier de la fonction HeavySide $f_H$ un peu plus loin.
$E = \dfrac{1}{2}(y_v-y_s)^2 = \dfrac{1}{2}\left(y_v-f\left(\sum\limits_{i=0}^n x_i\,\omega_i\right)\right)^2\quad\text{Pour simplifier les notations le biais est inclu dans la somme des }\omega_ix_i$
$\dfrac{\partial E}{\partial \omega_i} = 2\times\dfrac{1}{2}\left(y_v-f\left(\sum\limits_{i=0}^n x_i\,\omega_i\right)\right)\times\dfrac{\partial }{\partial \omega_i}\left(y_v-f\left(\sum\limits_{i=0}^n x_i\,\omega_i\right)\right)$
$\dfrac{\partial E}{\partial \omega_i} = (y_v-y_s)\times\dfrac{\partial }{\partial \omega_i}\left(f\left(\sum\limits_{i=0}^n x_i\,\omega_i\right)\right) \quad\text{avec}\quad (f\circ g)'(x) = f'(g(x))g'(x)$
$\dfrac{\partial E}{\partial \omega_i} = (y_v - y_s)\ f'\left(\sum\limits_{i=0}^n x_i\omega_i\right)\,x_i$
$\Delta \omega_i = -\eta\,(y_v - y_s)\,x_i\ f'\left(\sum\limits_{i=0}^n x_i\omega_i\right)$
Nous obtenons une relation de mise à jour des poids pour un n-uplet donné en entrée du perceptron. Pour le biais il suffit de fixer le $x_i$ correspondant à $1$ ou $-1$ suivant les cas.
Exemple d'apprentissage n° 1 : Imaginons une situation ou nous distinguons un territoire avec deux colonnies d'insectes (deux classes d'insectes). L'idée est d'écrire un programme qui va classer automatiquement tout nouvel insecte arrivant sur la carte dans une des colonnies en fonction de sa position.
Commençons par implanter nos colonnies
from random import randint
import numpy as np
import matplotlib.pyplot as plt
x1, y1 = [0.03, 0.14, 0.4], [0.08, 0.36, 0.17]
x2, y2 = [0.67, 0.53], [0.69, 0.67]
plt.grid()
plt.plot(x1, y1, '*')
plt.plot(x2, y2, 'ro')
plt.show()
Pour cet exemple l'idée est de réduire à son strict minimum le nombre de variables explicatives. Cela permet d'observer le fonctionnement du neurone de notre perceptron dans un plan.
La Table d'apprentissage correspondante aux variables explicatives qui serviront en entrées de notre neurone.
Soit $b = 0.5$, $\forall i\in\mathbb{N},\, \omega_i=0$ et $\eta = 0.2$
Pour les trois premières itérations $\Delta y = 0$ donc rien à faire.
À la quatrième itération, on observe que $\Delta y \neq 0$ donc une mise à jour des poids s'impose.
$$\begin{pmatrix} \omega_1\\ \omega_2\end{pmatrix}=\begin{pmatrix} 0\\ 0\end{pmatrix} + 0.2\times (-1)\times \begin{pmatrix} 0.67\\ 0.53\end{pmatrix} = \begin{pmatrix} -0.134\\ -0.106\end{pmatrix}\quad\quad\text{et}\quad b = 0.5 - 0.2 = 0.3$$Itération cinq, nouvelle mise à jour des poids
$$\begin{pmatrix} \omega_1\\ \omega_2\end{pmatrix}=\begin{pmatrix} -0.134\\ -0.106\end{pmatrix} + 0.2\times (-1)\times \begin{pmatrix} 0.69\\ 0.67\end{pmatrix} = \begin{pmatrix} -0.272\\ -0.24\end{pmatrix}\quad\quad\text{et}\quad b = 0.3 - 0.2 = 0.1$$Doit-on s'arréter à ce stade ? La réponse est non, les poids ont été modifiés à la cinquième itération mais sont-ils valables pour toutes les valeurs de la table d'apprentissage ? On recommence tant que ce n'est pas le cas.
À la septième itération, on observe que $\Delta y \neq 0$ donc une mise à jour des poids s'impose.
$$\begin{pmatrix} \omega_1\\ \omega_2\end{pmatrix}=\begin{pmatrix} -0.272\\ -0.24\end{pmatrix} + 0.2\times \begin{pmatrix} 0.14\\ 0.36\end{pmatrix} = \begin{pmatrix} -0.244\\ -0.168\end{pmatrix}\quad\quad\text{et}\quad b = 0.1 + 0.2 = 0.3$$À la neuvième itération, on observe que $\Delta y \neq 0$ donc une mise à jour des poids s'impose.
$$\begin{pmatrix} \omega_1\\ \omega_2\end{pmatrix}=\begin{pmatrix} -0.244\\ -0.168\end{pmatrix} + 0.2\times(-1)\times \begin{pmatrix} 0.67\\ 0.53\end{pmatrix} = \begin{pmatrix} -0.378\\ -0.274\end{pmatrix}\quad\quad\text{et}\quad b = 0.3 - 0.2 = 0.1$$Équation de la séparatrice : $b +\sum\limits_{i=1}^n x_i = 0$
Si on remplace par les valeurs que l'on a trouvé à l'itération 10 (on est pas sûr que ce soit fini) on peut écrire :
Essayons maintenant de tracer cette droite sur notre graphique.
def separatrice(x):
return (1/0.274)*(-0.378*x + 0.1)
x = np.linspace(0,0.6,100)
y = separatrice(x)
plt.grid()
plt.plot(x, y)
plt.plot(x1, y1, '*')
plt.plot(x2, y2, 'ro')
plt.show()
Le travail d'apprentissage n'est pas terminé, écrire toutes les étapes à la main serait bien trop long, il ne reste plus qu'à écrire une fonction Python qui fera le travail à notre place.
Comment classer un nombre de colonnie supérieur à 2 ?
from random import choice, uniform
# La fonction de transfert
def heavyside(x):
if x < 0:
return 0
return 1
def sigmoide(x, k=1):
return 1./(1+np.exp(-k*x))
def perceptron(f, e, n, eta, b, data):
'''
f -> function : fonction de transfert
e -> int : nombre d'entrées du perceptron
n -> int : nombre d'itérations pour l'apprentissage
eta -> int : le pas d'apprentissage (arbitraire : 0 < eta <= 1)
b -> int : poids du biais
data -> list : les données que l'on cherche à prédire
'''
errors = [] # liste des erreurs à la prédiction
w = np.zeros(e) # Tous les poids à zéro
w[-1] = b # poids du biais
fin = len(data)
for i in range(n):
#x, s = choice(data) # tirage aléatoire d'une des prédictions
if i >= fin:
x, s = data[i%fin] # lecture circulaire de la table d'apprentissage
else:
x, s = data[i]
result = np.dot(w, x) # somme pondérée
error = s - f(result) # différence entre prédiction et résultat
errors.append(error)
w += eta * error * x # mise à jour des poids (biais compris)
return w, errors
Revenons à notre Exemple d'apprentissage n° 1 :
# Les données que l'on cherche à prédire
data = [
(np.array([0.03, 0.08, 1]), 1),
(np.array([0.14, 0.36, 1]), 1),
(np.array([0.40, 0.17, 1]), 1),
(np.array([0.67, 0.53, 1]), 0),
(np.array([0.69, 0.67, 1]), 0),
]
Les tests
w, errors = perceptron(heavyside, 3, 20, 0.2, 0.5, data)
print(w)
for x, _ in data:
result = np.dot(x, w)
print("{}: {} -> {}".format(x[:], result, heavyside(result)))
Évaluation de l'erreur avec l'apprentissage
plt.ylim([-1,1])
plt.plot(errors)
plt.show()
x = np.linspace(min(x1), max(x2), 100)
def separator(x):
return -(w[0]/w[1]*x + w[2]/w[1])
plt.grid()
#plt.ylim([0,1])
plt.plot(x1, y1, '*')
plt.plot(x2, y2, 'ro')
for n in [10, 15]:
w, errors = perceptron(heavyside, 3, n, 0.2, 0.5, data)
y = separator(x)
plt.plot(x, y, label = str(n))
plt.legend(loc=4)
plt.show()
Arrivée de nouveaux insectes on positionne quelques insectes sur la carte, on calcul $\,f_H(S)\,$ avec les poids liés à l'apprentissage. La sortie indique à quelles catégories appartiennent nos insectes
insects = [np.array([0.30, 0.70, 1]), np.array([0.70, 0.80, 1]), np.array([0.4, 0.7, 1])]
for insect in insects:
result = np.dot(insect, w)
print("{}: {} -> {}".format(insect[:], result, heavyside(result)))
Le réseau de neurones du perceptron mono-couche permet de construire une méthode de classification en $N$ classes en considérant chaque neurone comme un indicateur d’une classe
Regardons maintenant ce qui ce passe quand on possède un entier $N>2$ de colonnies à classer toujours linéairement séparables 2 à 2.
def colonnie(X, Y, n, idc=1):
return np.array([np.random.uniform(X[0], X[1], n), np.random.uniform(Y[0], Y[1], n), np.ones(n)])
c1 = colonnie((0, 0.30), (0, 0.40), 4)
c2 = colonnie((0.30, 0.70), (0.50, 0.90), 4)
c3 = colonnie((0.60, 0.90), (0, 0.40), 4)
plt.grid()
plt.plot(c1[0], c1[1], 'bo')
plt.plot(c2[0], c2[1], 'ro')
plt.plot(c3[0], c3[1], 'go')
plt.show()
Il nous faut N neurones, le neurone $i\in[1, N]$ sépare la classe $i$ des autres classes
Reformulation du perceptron :
Pour un perceptron à 2 neurones, il y aura deux séparatrices
def perceptronMonoCouche(f, n, eta, b, data):
'''
f -> function : fonction de transfert
e -> int : nombre d'entrées du perceptron
n -> int : nombre d'itérations pour l'apprentissage
eta -> int : le pas d'apprentissage (arbitraire : 0 < eta <= 1)
data -> list : les données que l'on cherche à prédire
'''
errors = [] # liste des erreurs à la prédiction
entrees = len(data) # nombre d'entrées dans un neurone
neurones = len(data[-1]) # nombre de neurones dans la couche = nombre prédictions
w = np.zeros([neurones, len(data[0][0])]) # Tous les poids à zéro
w[:,-1] = 1 # poids du biais
for j in range(neurones):
e = []
for i in range(n):
if i >= entrees:
x, s = data[i%entrees] # lecture circulaire de la table d'apprentissage
else:
x, s = data[i]
result = np.dot(w[j], x)
error = s[j] - f(result)
e.append(error)
w[j] += eta*error*x
errors.append(e)
return w, errors
Mise en forme des données concernant nos insectes
def setData(c,ids):
transp = np.transpose(c)
data=[]
for elt in transp:
data.append((elt, ids))
return data
data1 = setData(c1, [0,0])
data2 = setData(c2, [1,0])
data3 = setData(c3, [1,1])
data = data1 + data2 + data3
w, errors = perceptronMonoCouche(heavyside, 300, 0.2, 0.5, data)
print(w)
Tracé des séparatrices
x = np.linspace(0, 1, 100)
def separator(x, w):
return -(w[0]/w[1]*x + w[2]/w[1])
plt.ylim([-0.5,1])
plt.plot(c1[0], c1[1], 'bo')
plt.plot(c2[0], c2[1], 'ro')
plt.plot(c3[0], c3[1], 'go')
y0 = separator(x, w[0])
y1 = separator(x, w[1])
plt.plot(x, y0)
plt.plot(x, y1)
plt.grid()
plt.show()
De nouveaux insectes
nuage = colonnie((0, 1.0), (0, 1.0), 6)
nuage = setData(nuage, [])
for insecte in nuage:
result = np.dot(insecte[0], w[0])
print("{}: {} -> {}".format(insecte[:], result, heavyside(result)))
result = np.dot(insecte[0], w[1])
print("{}: {} -> {}".format(insecte[:], result, heavyside(result)))
print
Il n'y a plus qu'à combiner les deux sorties pour déterminer l'appartenance à une colonnie
Exemple d'apprentissage n°2 : les variables explicatives sont plus nombreuses
Considérons un jeu de données définissant deux ensembles de n-uplets linéairements séparables, on aimerait par exemple pouvoir trier des caisses en fonction de la place restante. Les caisses pleines d'un coté et les caises avec encore au moins un emplacement vide de l'autre. Ci-dessous les valeurs des variables explicatives en fonction du remplissage des caisses.
0000 | 0100 | 1001 | 0101 | 1101 |
---|---|---|---|---|
Table d'apprentissage Jeu limité des combinaisons possibles
\begin{array}{|c|c|c|c|c|}\hline x_1 & x_2 & x_3 & x_4 & y_v \\\hline 0 & 0 & 0 & 0 & 1\\\hline 0 & 1 & 0 & 0 & 0\\\hline 1 & 0 & 0 & 1 & 0\\\hline 0 & 1 & 0 & 1 & 0\\\hline 1 & 1 & 0 & 1 & 0\\\hline \end{array}# Les données que l'on cherche à prédire
data = [
(np.array([0, 0, 0, 0]), 1), #0
(np.array([0, 0, 1, 0]), 0), #2
(np.array([0, 1, 0, 1]), 0), #5
(np.array([0, 1, 1, 0]), 0), #6
(np.array([1, 0, 0, 0]), 0), #8
(np.array([1, 0, 1, 0]), 0), #10
(np.array([1, 0, 1, 1]), 0), #11
(np.array([1, 1, 0, 0]), 0), #12
]
w, errors = perceptron(heavyside, 4, 100, 0.2, 0.5, data)
for x, _ in data:
result = np.dot(x, w)
print("{}: {} -> {}".format(x[:], result, heavyside(result)))
De nouvelles caisses
caisses = [np.array([0, 1, 0, 0]), #4
np.array([1, 1, 0, 1]), #13
np.array([1, 1, 1, 1]), #15
np.array([0, 0, 0, 0])] #0
for c in caisses:
result = np.dot(c, w)
print("{}: {} -> {}".format(c[:], result, heavyside(result)))
Exemple d'apprentissage n°3 : Régression linéaire avec un seul neurone (exemple tiré de la loi de Beer Lambert)
Soit une série de coordonnées, l'objectif est de tracer une régression linéaire liée à cette ensemble de données.
k = 100
C = [np.random.uniform(1e-3, 3e-2, 20), np.ones(20)]
A = k*C[0]+np.random.uniform(-0.3, 0.3, 20)
plt.plot(C[0],A, 'o')
plt.show()
Regréssion linéaire avec numpy
z = np.polyfit(C[0], A, 1)
p = np.poly1d (z)
print(p)
Régression linéaire avec le perceptron
data = []
x, ys = np.transpose(C), A.T
for i in range(len(x)):
data.append((x[i], ys[i]))
x = np.linspace(min(C[0]), max(C[0]), 100)
def separator(x):
return (w[0]*x + w[1])
plt.grid()
#plt.ylim([0,1])
plt.plot(C[0], A, 'o')
for n in [10, 1000, 10000, 100000, 1000000]:
w, errors = perceptron(lambda x: x , 2, n, 0.1, 0.5, data)
print(str(w[0]) + "*x + "+str(w[1]))
y = separator(x)
plt.plot(x, y, label = str(n))
plt.legend(loc=4)
plt.show()
On supperpose numpy et le perceptron
y_numpy = p(x)
plt.grid()
plt.plot(x, y_numpy)
plt.plot(x, y)
plt.show()
L'écart entre les deux
plt.grid()
plt.plot(x, abs(y_numpy-y))
plt.show()
Prenons pour simplifier les explications et les notations, un réseau de neurones avec 2 couches
Tous les neurones ont une fonction de transfert sigmoide du type : $$y_s = f_s(e) = \dfrac{L}{1+ \exp(-ke)}\quad\text{avec}\quad(L, k)\in\mathbb{N}^2\quad\text{et}\quad e = \sum\limits_{i=1}^n x_i\,\omega_i$$
Couche cachée : $k=1, L=1$
Sortie
Avec des matrices
Couche cachée
$$S_{\text{caché}} = D\times\ W_{\text{caché}}= \begin{pmatrix} 2.5 & 1\end{pmatrix}\times\begin{pmatrix} 0.5 & -1\\ 1.5 & -2\end{pmatrix} = \begin{pmatrix} 0.94 & 0.011\end{pmatrix}$$Sortie
$$S_{\text{sortie}} = S_{\text{caché}}\times W_{\text{sortie}} = \begin{pmatrix} 0.94 & 0.011\end{pmatrix}\times\begin{pmatrix} 1 \\ 3\end{pmatrix} \simeq 0.73$$def propagation_avant(f, data, neurones, poids):
'''
Cette fonction propage les données à travers les couches du réseau.
Depuis la première couche cachée jusqu'à la couche de sortie.
f -> function : fonction de transfert
data -> array(1D): les données d'entrée d'une couche
neurones -> list : nombre de neurones par couche
poids -> array : table des poids
'''
entrees = [np.copy(data)]
couches = len(neurones)
debut = 0
for i in range(couches):
fin = debut+neurones[i] # colonnes utilisées pour les calculs
e = len(entrees[i])
S = np.dot(entrees[i], poids[:e,debut:fin]) # somme pondérée sur une couche
result = f(S) # sortie de la couche i
debut = fin
entrees.append(result)
return entrees
D = np.array([2.5, 1])
W = np.array([[0.5, -1, 1],[1.5, -2, 3]])
couches_neurones = [2, 1]
S = propagation_avant(sigmoide, D, couches_neurones, W)
for result in S:
print result
Toujours à partir de l'exemple ci-dessus, nous avions comme données d'entrées $D = (2.5\ \ 1)$. Soit $y_v = 1$, la sortie attendue
def retroProp(f, data, neurones, poids):
x = data[0]
yv = data[1]
couches = len(neurones)-1
fin = len(poids[0])
# Erreur de sortie
ys = propagation_avant(f, x, neurones, poids)
deltas = [yv - ys[-1]]
# Erreur sur les couches cachées
for i in range(couches, 0, -1):
debut = fin - neurones[i]
produit_scalaire = np.dot(deltas[0], poids[:, debut:fin].T)
delta = (ys[i] * (1-ys[i]))*produit_scalaire
deltas.insert(0, delta)
fin = debut
return deltas
# Mise à jour des poids
D = (np.array([2.5, 1]), 1)
W = np.array([[0.5, -1, 1],[1.5, -2, 3]])
retroProp(sigmoide, D, [2, 1], W)
christophe.casseau@ensam.eu