Un algorithme glouton python sélectionne goulûment le meilleur choix à chaque étape. Il espère que ces choix mènent à la solution globale optimale du problème. Ainsi, un algorithme glouton ne donne pas toujours la meilleure solution. Cependant dans de nombreux problèmes c’est le cas.
Algorithme glouton : Introduction
Le problème du rendu de monnaie est formulé de la façon suivante. Comment rendre une somme donnée avec un minimum de pièces et billets ?
Voici un exemple en python de la résolution du problème :
Si on considère le système monétaire Euro sans les centimes on a l’ensemble
EURO = (1, 2, 5, 10, 20, 50, 100, 200, 500)
Algorithme glouton rendu de monnaie python
Maintenant, pour rendre la monnaie sur une valeur x de en utilisant ces pièces et billets, alors nous vérifierons le premier élément du tableau. Et si il est supérieur à x, nous passons à l’élément suivant. Sinon le gardons. Maintenant, après avoir pris une pièce ou un billet de valeur issu du tableau de pieceEtBillet [i], la valeur totale x que nous devons faire deviendra x – pieceEtBillet [i].
Voici l’algorithme glouton python associé :
def renduMonnaieGlouton(x):
pieceEtBillets = [500,200,100,50,20,10,5,2,1]
i = 0
while(x>0):
if(pieceEtBillets[i] > x):
i = i+1
else:
print(str(pieceEtBillets[i]))
x -= pieceEtBillets[i];
renduMonnaieGlouton(33)#Exemple sur 33 euros
La sortie pour 33 euro est alors :
20
10
2
1
Autre exemple avec 55 euro d’algorithme glouton python :
def renduMonnaieGlouton(x):
pieceEtBillets = [500,200,100,50,20,10,5,2,1]
i = 0
while(x>0):
if(pieceEtBillets[i] > x):
i = i+1
else:
print(str(pieceEtBillets[i]))
x -= pieceEtBillets[i];
renduMonnaieGlouton(55)#Exemple sur 55 euros
La sortie est alors :
50
5
Conclusion
Le problème du rendu de monnaie est NP-difficile relativement au nombre de pièce et billet du système monétaire considéré (euro dans cet exemple). Pour aller plus loin on pourra démontrer que pour certains systèmes de monnaie dits canoniques, l’utilisation d’un algorithme glouton est optimal. Un système monétaire est dit canonique si pour toute somme s l’algorithme glouton conduit à une décomposition minimale.
La difficulté NP est la propriété déterminante d’une classe de problèmes informellement « au moins aussi difficiles que les problèmes les plus difficiles de NP ».
Un exemple simple de problème NP-hard est le problème de somme de sous-ensembles. Si P est différent de NP alors il est peu probable de trouver un algorithme en temps polynomial qui résout de façon exact ce problème.
Voici l’implémentation en python de l’algorithme de Wagner & Fischer (Wagner-Fischer). Il permet de calculer la distance de Levenshtein (distance entre deux chaines de caractères).
Premièrement le but de l’algorithme est de trouver le coût minimal. Coût minimal pour transformer une chaîne en une autre. Alors une fonction récursive permet de retourner le nombre minimal de transformation. Et pour transformer une sous-chaine de A avec n caractères en une sous-chaine de B avec le même nombre de caractères. La solution est donnée. Il faut calculer la distance entre les 2 lettres à la même position dans la chaine A et B. Alors Soit les lettres et la lettre précédentes sont identiques. Soit il y a une différence et dans ce cas on calcule 3 côuts. Alors le premier est de supprimer une lettre le la chaine A. Et d’insérer une lettre dans la chaine A pour substituer une lettre de la chaine A. Alors On peut alors trouver le cout minimal.
import numpy as np
def levenshtein(chaine1, chaine2):
taille_chaine1 = len(chaine1) + 1
taille_chaine2 = len(chaine2) + 1
levenshtein_matrix = np.zeros ((taille_chaine1, taille_chaine2))
for x in range(taille_chaine1):
levenshtein_matrix [x, 0] = x
for y in range(taille_chaine2):
levenshtein_matrix [0, y] = y
for x in range(1, taille_chaine1):
for y in range(1, taille_chaine2):
if chaine1[x-1] == chaine2[y-1]:
levenshtein_matrix [x,y] = min(
levenshtein_matrix[x-1, y] + 1,
levenshtein_matrix[x-1, y-1],
levenshtein_matrix[x, y-1] + 1
)
else:
levenshtein_matrix [x,y] = min(
levenshtein_matrix[x-1,y] + 1,
levenshtein_matrix[x-1,y-1] + 1,
levenshtein_matrix[x,y-1] + 1
)
return (levenshtein_matrix[taille_chaine1 - 1, taille_chaine2 - 1])
print("distance de levenshtein = " + str(levenshtein("Lorem ipsum dolor sit amet", "Laram zpsam dilir siy amot")))
Pour calculer la distance de Levenshtein avec un algorithme non récursif. On utilise une matrice qui contient les distances de Levenshtein. Alors Ce sont les distances entre tous les préfixes de la première chaîne et tous les préfixes de la seconde chaîne de caractères.
Aussi on peut calculer dynamiquement les valeurs dans cette matrice. La dernière valeur calculée sera la distance de Levenshtein entre les deux chaînes entières.
Enfin il y a de nombreux cas d’utilisation de la distance de Levenshtein. La distance de Levenshtein est utilisée dans des domaines. La linguistique informatique, la biologie moléculaire. Et encore la bioinformatique, le machine learning. Également le deep learning, l’analyse de l’ADN. De plus, un programme qui fait de la vérification orthographique utilise par exemple la distance de Levenshtein.
Liens sur l’algorithme de Wagner & Fischer (Wagner-Fischer) et la distance de Levenshtein en Python ou d’autre langage :
Dans cet article je vous propose un algorithme de tri quantique qui permet de trier une liste d’entier codés sur deux qubits. Cet algorithme peut être utilisé et peut servir de base pour résoudre des problèmes de tri sur une liste non triée d’entiers.
Introduction
Nous considérons le problème suivant : Étant donné une liste de quatre entiers compris entre 0 et 3 strictement différents, trier la liste :
Figure 1 : Problem to solve with Quantum sorting algorithm
Un algorithme de tri classique comme par exemple le tri fusion permet de résoudre le problème, voir plus en détail mon article sur le sujet :
Le tri fusion suit le paradigme diviser pour régner qui consiste à diviser la tâche initiale en deux tâches similaires plus petites.
Quelques concepts d’algorithme quantique
Je rappelle ici quelques concepts que nous allons utiliser dans notre algorithme de tri quantique, aussi je vous conseille de consulter le site IBM Qiskit pour en savoir plus https://qiskit.org/textbook/what-is-quantum.html et le très bon livre « Programming Quantum Computers: Essential Algorithms and Code Samples »de Eric R. Johnston , Nic Harrigan , Mercedes Gimeno-Segovia :
Circuits
Le principe en algorithme quantique est de manipuler des qubits, le processus peut être représenté sous forme de circuit (entrées à gauche, sortie à droite). Nous pouvons effectuer différentes opérations au moyen de portes quantiques (qui agissent sur les qubits de manière similaire en algorithme classique aux portes logiques comme ET, OU, OU Exclusif …).
Dans cet article je vais m’appuyer sur Qiskit qui est le framework IBM pour l’informatique quantique.
from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi
qreg_qubit = QuantumRegister(2, 'qubit')
creg_classic = ClassicalRegister(2, 'classic')
circuit = QuantumCircuit(qreg_qubit, creg_classic)
circuit.reset(qreg_qubit[0])
circuit.reset(qreg_qubit[1])
circuit.x(qreg_qubit[0])
circuit.measure(qreg_qubit[0], creg_classic[0])
circuit.measure(qreg_qubit[1], creg_classic[1])
Dans ce premier algorithme on initialise un registre quantique à l’état |01> . On mesure dans un registre classique à 2 bits l’état quantique d’un registre quantique de 2 qubits. Le circuit peut être dessiné au moyen de l’instruction circuit.draw() ou via Circuit Composer de IBM Quantum Experience : https://quantum-computing.ibm.com/
Etat quantique d’un qubit seul :
L’état d’un qubit peut s’exprimer sous la forme d’un vecteur d’état si on passe en forme trigonométrique et exponentielle on a avec θ and ϕ qui sont des nombres réels :
Avec alpha et beta qui sont des nombres complexes (c’est à dire une partie réelle et imaginaire) dans ce cas il existe la relation (rappel mathématique sur les nombres complexes : https://www.maths-cours.fr/cours/nombres-complexes-geometrie/) :
Ainsi si on mesure un qubit q on a :
C’est à dire qu’il existe une probabilité de mesurer le qubit dans l’état |0> et une probabilité de mesurer le qubit dans l’état |1>. La mesure d’un qubit révèle si celui-ci est dans l’état 1 ou dans l’état 0, en général la mesure est placée en fin de circuit car elle affecte l’état du qubit en conséquence.
Portes quantiques
Voici quelques portes quantiques à connaitre et que nous allons utiliser dans l’algorithme de tri quantique :
Porte X (Pauli-X) :
La porte X permet de retourner l’état du qubit sans modifier la phase :
<
Voir l’exemple ci-dessus avec l’utilisation de qiskit.
Porte Y (Pauli-Y) :
La porte de pauli Y permet de retourner la phase et l’état du qubit en même temps :
Exemple si on considère ici l’état initialisé |0> du qubit et sa phase de 0, il y a alors 100% de chance de mesurer l’état |0>.
L’application de la porte quantique Y a l’effet suivant sur l’état et la phase du qubit (voir la sphère de bloch) :
Il y a alors 100% de chance de mesurer l’état 1 et la phase se retrouve inversée (voir la sphère de bloch ci-dessus)
from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi
qreg_qubit = QuantumRegister(1, 'qubit')
creg_classic = ClassicalRegister(1, 'classic')
circuit = QuantumCircuit(qreg_qubit, creg_classic)
circuit.reset(qreg_qubit[0])
circuit.y(qreg_qubit[0])
circuit.measure(qreg_qubit[0], creg_classic[0])
Porte Z (Pauli-Z) :
La porte Z est utilisée pour retourner uniquement la phase et non l’état du qubit.
A noter que les portes Y et Z peuvent être représentées par les matrices suivantes :
La porte Hadamard (porte H) est une porte quantique importante qui permet de créer une superposition de | 0⟩ et | 1⟩.
La matrice de cette porte est :
Porte de SWAP
Une porte SWAP permet d’échange l’état de deux qubits :
Exemple SWAP de l’état | 1⟩ du qubit 0 vers le qbit 2
Et SWAP de l’état | 0⟩ du qubit 1 vers le qbit 2
En Python avec le framework Qiskit on a :
from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi
qreg_qubit = QuantumRegister(3, 'qubit')
creg_classic = ClassicalRegister(1, 'classic')
circuit = QuantumCircuit(qreg_qubit, creg_classic)
circuit.reset(qreg_qubit[0])
circuit.reset(qreg_qubit[1])
circuit.reset(qreg_qubit[2])
circuit.x(qreg_qubit[0])
circuit.swap(qreg_qubit[1], qreg_qubit[2])
circuit.measure(qreg_qubit[2], creg_classic[0])
Porte de Toffoli
La porte quantique Toffoli est à trois qubits (deux commandes et une cible). Il effectue un retournement de phase (porte quantique X sur la cible) uniquement si les deux contrôles sont dans l’état | 1⟩. Un Toffoli est équivalent à une porte NON contrôlée (on l’appelle aussi la porte CCX).
Exemple ci-dessous avec 2 qubits de commande en état | 1⟩ on a alors 100% de chance de mesurer l’état | 1⟩ sur le qubit cible de la porte de Toffoli qui était au départ initialisé à l’état | 0⟩ (soit un retournement de l’état).
Exemple ci-dessous dans le cas inverse (on a alors 0% de chance de mesurer l’état | 1⟩ soit 100% de chance de mesurer l’état | 0⟩):
Porte classique porte ET, porte OU équivalence en porte quantique
On voit ici comment combiner des porte pour créer un comportement équivalent à ce qu’on a l’habitude d’utiliser en circuit classique.
Porte ET :
A partir de Qbit a et b et d’un qubit avec une initialisation forcée à l’état | 0⟩ on peut obtenir l’opération a ET b en utilisant une porte quantique de Toffoli et une pote SWAP.
Le circuit suivant effectue un classique ET sur un algorithme quantique
Il faut noter qu’à la fin de ce circuit on retrouve l’état A ET B sur le qubit B l’état du qubit B se trouve au final sur le qubit C.
Nous utiliserons cette porte pour effectuer notre tri quantique de liste, voici quelques tests :
Pour | 0⟩ ET | 0⟩ vous avez | 0⟩ sur le qubit B :
Pour | 0⟩ ET | 1⟩ vous avez | 0⟩ sur le qubit B :
Pour | 1⟩ ET | 0⟩ vous avez | 0⟩ sur le qubit B :
Enfin pour | 1⟩ ET | 1⟩ vous avez bien | 1⟩ sur le qubit B avec une probabilité de 100% :
Porte OU :
Pour réaliser une porte OU on combine 4 portes quantiques X, une porte de Toffoli et une porte quantique SWAP, également l’état de C doit être initialisé à l’état | 1> :
OPENQASM 2.0;
include "qelib1.inc";
qreg a[1];
qreg b[1];
qreg c[1];
creg aORb[1];
creg aState[1];
creg bState[1];
reset a[0];
reset b[0];
x b[0];
x c[0];
x a[0];
ccx a[0],b[0],c[0];
x a[0];
x b[0];
swap b[0],c[0];
measure b[0] -> aORb[0];
measure a[0] -> aState[0];
measure c[0] -> bState[0];
Si on teste on obtient bien une porte OU :
Ici pour | 0⟩ OU | 0⟩ vous avez bien | 0⟩ sur le qubit B avec une probabilité de 100% :
Ici pour | 0⟩ OU | 1⟩ vous avez bien | 1⟩ sur le qubit B avec une probabilité de 100% :
Pour | 1⟩ OU | 0⟩ vous avez bien | 1⟩ sur le qubit B avec une probabilité de 100% :
Finalement pour | 1⟩ OU | 1⟩ vous avez bien | 1⟩ sur le qubit B avec une probabilité de 100% :
Algorithme de tri quantique
Pour résoudre ce problème nous allons créer tout d’abord un circuit quantique qui permet de mesurer si un chiffre est inférieur à un autre, pour cela l’intuition est de se baser sur un circuit similaire à un circuit classique de comparaison de magnitude à 2 bits.
Comparateur de magnitude quantique :
On considère un chiffre A stocké dans un registre à 2 qubits (A0, A1) et un chiffre B stocké dans un autre registre (B0,B1) :
Pour savoir si A > B avec 2 registre de 2 Qubits il faut appliquer l’équation :
Le circuit équivalent pour créer cela est :
Ici dans l’exemple les 2 bits comparés par ce circuit sont dans le registre a et le registre B
Quantum qubit magnitude comparator
Le code équivalent pour ce comparateur en OpenQASM est :
J’ai créé une GATE comparator4 qui a le code équivalent OPENQASM suivant :
gate comparator4 a, b, c, d, f, g, i, j, k, l {
x d;
x j;
x l;
andG1 b, d, f;
andG2 a, b, g;
andG3 a, f, i;
orG1 b, f, j;
x c;
andG4 c, f, k;
x c;
orG2 d, f, l;
swap d, i;
x d;
swap b, g;
}
Ainsi on voit que cette custom quantum gate est consitué de porte quantum AND et porte quantum OR custom que j’ai créé de la façon suivante. Si on déplie les portes andG1, andG2, andG3, orG1, orG2 on a :
Le code équivalent OpenQASM pour écrire les différentes porte andG1, andG2, andG3, orG1, orG2 pour créer le comparator 4 est :
gate andG1 a, b, c {
ccx a, b, c;
swap b, c;
}
gate andG2 a, b, c {
ccx a, b, c;
swap b, c;
}
gate andG3 a, b, c {
ccx a, b, c;
swap b, c;
}
gate orG1 a, b, c {
x a;
x b;
ccx a, b, c;
x a;
x b;
swap b, c;
}
gate andG4 a, b, c {
ccx a, b, c;
swap b, c;
}
gate orG2 a, b, c {
x a;
x b;
ccx a, b, c;
x a;
x b;
swap b, c;
}
Circuit de vérification d’une liste triée
Si on considère ici une liste de 4 chiffres stockés dans les 4 registres de 2 qubits : a, b, m, n. Le circuit ci-dessur permet de tester si la liste en entrée est triée ou non. Pour cela j’ai mis en cascade 3 comparateurs de magnitude quantique (vu en détails dans le paragraphe précédent). Ainsi le circuit obtenu va tester si a > b et mettre le résulta sur le qbit c puis vérifier si b>m et stocker le résultat sur le qbit o et enfin il teste si m > n et stocke le résultat sur le qubit q.
La dernière porte quantique andOnCompare permet d’appliquer une parte ET mutliple :si c ET o ET q sont à l’état quantique |1> alors le qubit q est mis à l’état quantique |1> sinon il est à l’état quantique |0> :
Ci-dessous le code de la porte andOnCompare en openQASM :
gate andOnCompare a, b, c, d, f {
ccx a, b, d;
swap b, d;
ccx b, c, f;
swap c, f;
}
Nous avons créé un circuit qui vérifie qu’une liste de 4 chiffres stocké dans les registres a,b,m,n est triée de façon décroissante ou non. Le résultat est stocké dans le qubit q qui a 100% de chance d’être mesuré à l’état | 1> si la liste est triée sinon 100% d’être à | 0> si la liste a,b,m,n n’est pas en ordre décroissante.
Dans le schéma général ci-dessus on remarque que dans l’exemple :
a=0,b=2,m=3,n=1
dans ce cas ce circuit retournera l’état quantique |0 > sur le qubit q
Création d’un circuit de permutations
L’idée de notre algorithme est de permuter ces 4 chiffres en utilisant des qubits de commande qui seront en état de superposition.
Le circuit de permutation est le suivant :
Un registre de 6 Qubit « control » permet de piloter la permutation de la liste sachant qu’il y a pour 4 éléments : 4*3*2*1 permutations possibles soit 24 possibilités les 6 qubits permettent de générer ces différents états.
4 portes quantique de Hadamard sont utilisées pour mettre en oeuvre ces permutations et tirer parti de la superposition du registre de Qubit ‘control’
En d’autre terme dans le circuit ci-dessus on voit que l’on démarre le circuit en initialisant les registres a,b,m,n avec sa liste de chiffre non triée, ici (a=0,b=2,m=3,n=1).
Le circuit de permutation qui est contrôlé par un registre de qubit en superposition permet de permuter la liste en superposition quantique.
Ainsi on obtient sur le qubit q0 l’état quantique | 1> si la liste permutée est triée de façon décroissante sinon l’état quantique | 0>.
Le code OpenQASM de l’algorithme quantique permettant d’effectuer des permutation est le suivant :
gate permuter a, b, c, d, f, g, i, j, k, l, m, n, o, p {
cswap k, a, c;
cswap l, a, f;
cswap m, a, i;
cswap k, b, d;
cswap l, b, g;
cswap m, b, j;
cswap n, c, f;
cswap o, c, i;
cswap n, d, g;
cswap o, d, j;
cswap p, f, i;
cswap p, g, j;
}
Amplification du résultat
Je vais appeler cette partie de mon algorithme l’amplification : l’idée est de mettre les qubit a,b,m,n à |00>,|00>,|00>,|00> si la liste est non triée. Si la liste est triée alors l’état quantique de a,b,m,n ne doit pas être modifié.
Ainsi on devrait mesurer le résultat suivant : |00>,|00>,|00>,|00> lorsque la liste est non trié et a,b,m,n avec les chiffre d’entrée en ordre trié (dans le cas de notre exemple cela signifie qu’il y a une probabilité de mesurer l’état |11>,|10>,|01>,|00> soit 3,2,1,0 soit la liste triée).
Le circuit de l’amplificateur quantique est le suivant :
Le circuit se base sur une série de porte quantique AND appliqué à l’état de sortie q0 ET le chiffre de la liste. Lorsque le qubit q0 indique que la liste est triée il est à |1> et laisse l’état des qubit a,b,m,n à leur état d’entrée (ou permuté par superposition) . Lorsque le qubit q0 indique que la liste est non triée il est à l’état | 0> l’application de la porte AND va ainsi mettre les qubit a,b,m,n à | 0>.
Le code de l’amplificateur est le suivant selon un algorithme quantique codé en OpenQASM :
gate amplifier2 a, b, c, d, f, g, i, j, k, l, m, n, o, p, q, r, v {
ccx a, k, l;
swap a, l;
ccx b, k, m;
swap b, m;
ccx c, k, n;
swap c, n;
ccx d, k, o;
swap d, o;
ccx f, k, p;
swap f, p;
ccx g, k, q;
swap g, q;
ccx i, k, r;
swap i, r;
ccx j, k, v;
swap j, v;
}
Algorithme quantique complet pour le tri décroissant d’une liste de quatre chiffres :
Voici le circuit utilisé pour trié la liste suivante : a=0,b=2,m=3,n=1.
Il est possible facilement d’initialiser le circuit avec une autre liste en modifiant l’initialisation des registre a,b,m,n. Aussi l’algorithme actuel permet de trier des chiffres codés sur 2 qubits il reste possible de modifier l’algorithme selon le même principe pour trier des nombres stockés sur 3 qubits et considérer une liste de plus de 4 éléments (il faut alors multiplier le nombre de registres de qubits pour stocker la liste d’entrée).
Le code complet est le suivant en openQASM :
OPENQASM 2.0;
include "qelib1.inc";
gate andG1 a, b, c {
ccx a, b, c;
swap b, c;
}
gate andG2 a, b, c {
ccx a, b, c;
swap b, c;
}
gate andG3 a, b, c {
ccx a, b, c;
swap b, c;
}
gate orG1 a, b, c {
x a;
x b;
ccx a, b, c;
x a;
x b;
swap b, c;
}
gate andG4 a, b, c {
ccx a, b, c;
swap b, c;
}
gate orG2 a, b, c {
x a;
x b;
ccx a, b, c;
x a;
x b;
swap b, c;
}
gate comparator a, b, c, d, f, g, i, j, k, l {
x d;
x j;
x l;
andG1 b, d, f;
andG2 a, b, g;
andG3 a, f, i;
orG1 b, f, j;
x c;
andG4 c, f, k;
orG2 d, f, l;
}
gate comparator2 a, b, c, d, f, g, i, j, k, l {
x d;
x j;
x l;
andG1 b, d, f;
andG2 a, b, g;
andG3 a, f, i;
orG1 b, f, j;
x c;
andG4 c, f, k;
orG2 d, f, l;
x d;
swap b, g;
}
gate comparator3 a, b, c, d, f, g, i, j, k, l {
x d;
x j;
x l;
andG1 b, d, f;
andG2 a, b, g;
andG3 a, f, i;
orG1 b, f, j;
x c;
andG4 c, f, k;
orG2 d, f, l;
swap d, i;
x d;
swap b, g;
}
gate comparator4 a, b, c, d, f, g, i, j, k, l {
x d;
x j;
x l;
andG1 b, d, f;
andG2 a, b, g;
andG3 a, f, i;
orG1 b, f, j;
x c;
andG4 c, f, k;
x c;
orG2 d, f, l;
swap d, i;
x d;
swap b, g;
}
gate permutation a, b, c, d, f, g, i, j, k, l, m, n, o, p {
ccx a, c, k;
ccx a, f, l;
ccx a, i, m;
ccx b, d, k;
ccx b, g, l;
ccx b, j, m;
ccx c, f, n;
ccx c, i, o;
ccx d, g, n;
ccx d, j, o;
ccx f, i, p;
ccx g, j, p;
}
gate andOnCompare a, b, c, d, f {
ccx a, b, d;
swap b, d;
ccx b, c, f;
swap c, f;
}
gate permuter a, b, c, d, f, g, i, j, k, l, m, n, o, p {
cswap k, a, c;
cswap l, a, f;
cswap m, a, i;
cswap k, b, d;
cswap l, b, g;
cswap m, b, j;
cswap n, c, f;
cswap o, c, i;
cswap n, d, g;
cswap o, d, j;
cswap p, f, i;
cswap p, g, j;
}
gate amplifier a, b, c, d, f, g, i, j, k, l, m, n, o, p, q, r, v {
ccx l, a, m;
swap a, m;
ccx l, b, n;
swap b, n;
ccx l, c, o;
swap c, o;
ccx l, d, p;
swap d, p;
ccx l, f, q;
swap f, q;
ccx l, f, q;
swap f, q;
ccx l, g, r;
swap g, r;
ccx l, i, v;
swap i, v;
ccx l, j, k;
swap j, k;
}
gate amplifier1 a, b, c, d, f, g, i, j, k, l, m, n, o, p, q, r, v {
ccx a, l, m;
swap a, m;
ccx b, l, n;
swap b, n;
ccx c, l, o;
swap c, o;
ccx d, l, p;
swap d, p;
ccx f, l, q;
swap f, q;
ccx f, l, q;
swap f, q;
ccx g, l, r;
swap g, r;
ccx i, l, v;
swap i, v;
ccx j, k, l;
swap j, k;
}
gate amplifier2 a, b, c, d, f, g, i, j, k, l, m, n, o, p, q, r, v {
ccx a, k, l;
swap a, l;
ccx b, k, m;
swap b, m;
ccx c, k, n;
swap c, n;
ccx d, k, o;
swap d, o;
ccx f, k, p;
swap f, p;
ccx g, k, q;
swap g, q;
ccx i, k, r;
swap i, r;
ccx j, k, v;
swap j, v;
}
qreg a[2];
qreg b[2];
qreg m[2];
qreg n[2];
qreg c[1];
qreg o[1];
qreg q[1];
qreg d[1];
qreg g[1];
qreg j[1];
qreg k[1];
qreg l[1];
qreg r[1];
qreg uu[1];
qreg zz[1];
qreg control[6];
creg sorted[8];
reset a[0];
reset a[1];
reset b[0];
reset b[1];
reset m[0];
reset m[1];
reset n[0];
reset n[1];
reset c[0];
reset o[0];
reset q[0];
reset d[0];
reset g[0];
reset j[0];
reset k[0];
reset l[0];
reset r[0];
reset uu[0];
h control[0];
h control[1];
h control[2];
h control[3];
h control[4];
h control[5];
reset a[0];
reset a[1];
reset b[0];
x b[1];
x m[0];
x m[1];
reset n[1];
reset c[0];
reset d[0];
reset g[0];
reset j[0];
reset k[0];
reset l[0];
x n[0];
permuter a[0],a[1],b[0],b[1],m[0],m[1],n[0],n[1],control[0],control[1],control[2],control[3],control[4],control[5];
comparator4 a[0],a[1],b[0],b[1],c[0],d[0],g[0],j[0],k[0],l[0];
reset zz[0];
reset d[0];
reset g[0];
reset j[0];
reset k[0];
reset l[0];
comparator4 b[0],b[1],m[0],m[1],o[0],d[0],g[0],j[0],k[0],l[0];
reset d[0];
reset g[0];
reset j[0];
reset k[0];
reset l[0];
comparator4 m[0],m[1],n[0],n[1],q[0],d[0],g[0],j[0],k[0],l[0];
andOnCompare c[0],o[0],q[0],r[0],uu[0];
reset d[0];
reset g[0];
reset j[0];
reset k[0];
reset l[0];
reset r[0];
reset uu[0];
amplifier2 a[0],a[1],b[0],b[1],m[0],m[1],n[0],n[1],q[0],d[0],g[0],j[0],k[0],l[0],r[0],uu[0],zz[0];
measure a[0] -> sorted[0];
measure a[1] -> sorted[1];
measure b[0] -> sorted[2];
measure b[1] -> sorted[3];
measure m[0] -> sorted[4];
measure m[1] -> sorted[5];
measure n[0] -> sorted[6];
measure n[1] -> sorted[7];
Voici le code Python Qiskit pour mon algorithme de tri quantique :
Les test s’effectuent en démarrant l’algorithme sur le simulateur quantique :
Pour démarrer l’algorithme quantique il faut au préalable initialiser :
%matplotlib inline
# Importing standard Qiskit libraries
from qiskit import QuantumCircuit, execute, Aer, IBMQ
from qiskit.compiler import transpile, assemble
from qiskit.tools.jupyter import *
from qiskit.visualization import *
from iqx import *
# Loading your IBM Q account(s)
provider = IBMQ.load_account()
Et pour effectuer le test par exemple en exécutant 100 fois le circuit quantique et afficher la probabilité de mesure sous forme d’histogramme :
On obtient le résultat qui confirme qu’on a plus de change de mesurer l’état quantique de la liste trié que les autres combinaison (dans mon test 5%) :
Quand j’ai écris ce billet de blog à propos du pytorch tutorial, je me suis souvenu du challenge que je me suis fixé en début d’année d’apprendre le deep learning, je ne connaissais alors même pas Python. Ce qui rends les choses difficiles ce n’est pas forcément la complexité des concepts, mais cela commence par des questions du type : Quel framework utiliser pour le Deep learning ? Quel fonction d’activation est ce que je dois choisir ? Quel est la fonction de côut la mieux adaptée pour mon problème ?
Mon expérience personnelle a été d’étudier le framework PyTorch et surtout pour la théorie le cours en ligne mis à disposition gratuitement par Yan LeCun que je remercie (lien ici https://atcold.github.io/pytorch-Deep-Learning/). Il me reste encore à apprendre et travailler sur le domaine mais par ce billet de blog, j’aimerais partager et vous donner un panorama de ce que j’ai appris sur le deep learning cette année.
Deep Learning : Quelle fonction d’activation et de coût choisir ?
L’objectif de cet article est de balayer ce sujet central en DeepLearning du choix la fonction d’activation et de coût (loss) en fonction du problème que vous cherchez à résoudre au moyen d’un algorithme de DeepLearning.
On parle ici de la fonction d’activation de la dernière couche de votre modèle c’est à dire celle qui vous donne le résultat.
Ce résultat est utilisé dans l’algorithme qui vérifie à chaque apprentissage la différence entre le résultat prédit par le réseau de neurones et le résultat réel (algorithme de descente du gradient), pour cela on applique au résultat une fonction de coût (loss function) qui représente cette différence et que vous cherchez à minimiser au fil des entrainement afin de réduire l’erreur. (Voir cet article ici pour en savoir plus : https://machinelearnia.com/descente-de-gradient/)
Source https://upload.wikimedia.org/wikipedia/commons/6/68/Gradient_descent.jpg : L’algorithe de descente de Gradient permet de trouver le minimum de n’importe quelle fonction convexe pas à pas.
Pour rappel la machine apprends en minimisant la fonction de coût, itérativement par étapes d’entrainement successif, le résultat de la fonction de coût et pris en compte pour l’ajustement des paramètres des neurones (poids et biais par exemple pour les couches linéaires).
Ce choix de fonction d’activation sur la dernière couche et la fonction de coût à minimiser (loss function) est donc crucial puisque ces deux éléments combinés vont déterminer comment vous allez résoudre un problème au moyen de votre réseau de neurones.
Cet article présente également des exemples simples qui utilisent le framework Pytorch d’après moi un très bon outil pour le machine learning.
La question ici à se poser est la suivante :
Est ce que je cherche à créer un modèle qui effectue une classification binaire ? (Vous cherchez dans ce cas à prédire une probabilité que le résultat d’une entrée soit 0 ou 1)
Est ce que je cherche à calculer/prédire une valeur numérique avec mon réseau de neurones ? (Vous cherchez dans ce cas à prédire une valeur par exemple décimale en sortie qui corresponds à votre entrée)
Est ce que je cherche à créer un modèle qui effectue une classification d’un label simple ou multiple pour un ensemble de classes ? (Vous cherchez dans ce cas à prédire pour chaque classe en sortie la probabilité qu’une entrée corresponde à cette classe)
Est ce que je cherche à créer un modèle qui effectue la recherche de plusieurs classes dans un ensemble de classes possibles ? (Vous cherchez dans ce cas à prédire pour chaque classe en sortie son taux de présence dans l’entrée).
Problème de classification binaire :
Vous cherchez à prédire au moyen de votre algorithme de DeepLearning qu’un résultat est vrai ou faux, et plus précisément c’est une probabilité qu’un résultat soit 1 ou qu’un résultat soit 0 que vous allez obtenir.
La taille de sortie de votre réseau de neurone est 1 (couche finale) et vous cherchez à obtenir un résultat entre 0 et 1 qui sera assimilé à la probabilité que le résultat soit 1 (exemple en sortie du réseau si vous obtenez 0.65 cela correspondra à 65% de chance que le résultat soit vrai). Exemple d’application : Prédiction de la probabilité que l’équipe à domicile d’un match de football gagne. Plus la valeur est proche de 1 plus l’équipe à domicile a des chances de gagner, et inversement plus le résultat se rapproche de 0 plus l’équipe à domicile a des chance de perdre. Il est possible de qualifier ce résultat en utilisant un seuil, par exemple en admettant que si la sortie est > 0.5 alors le résultat est vrai sinon faux.
Pytorch tutorial – Fonction d’activation finale (cas classification binaire) :
La fonction d’activation finale doit retourner un résultat entre 0 et 1, le bon choix dans ce cas peut être la fonction sigmoïde. La fonction sigmoïde permettra de traduire facilement un résultat entre 0 et 1 et donc est idéal pour traduire la probabilité qu’on cherche.à prédire.
import math
import numpy as np
import matplotlib.pyplot as plt
def sigmoid(x):
a = []
for item in x:
a.append(1/(1+math.exp(-item)))
return a
x = np.arange(-10., 10., 0.2)
sig = sigmoid(x)
plt.plot(x,sig)
plt.show()
Tracé de la fonction sigmoid, fonction utilisée comme fonction d’activation finale dans le cas d’un algorithme de Deep Learning
La fonction de coût – Loss function (cas classification binaire) :
Il faut déterminer lors de l’entrainement la différence entre la probabilité que le modèle prédit (traduite via la fonction finale sigmoid) et la réponse vraie et connue (0 ou 1). La fonction à utiliser est Binary Cross Entrropy car cette fonction permet de calculer la différence entre 2 probabilité. L’optimiseur va ensuite utiliser ce résultat pour ajuster les poids et biais dans votre modèle (ou les autres paramètres selon l’architecture de votre modèle).
Exemple :
Dans cet exemple je vais créer un réseau de neurones avec 1 couche linéaire et une fonction d’activation finale sigmoïde.
Dans un premier temps, au travers de ce pytorch tutorial, j’effectue tous les imports que nous allons utiliser dans ce billet :
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from collections import OrderedDict
import math
from random import randrange
import torch
from torch.autograd import Variable
import torch.nn as nn
from torch.autograd import Function
from torch.nn.parameter import Parameter
from torch import optim
import torch.nn.functional as F
from torchvision import datasets, transforms
from echoAI.Activation.Torch.bent_id import BentID
from sklearn.model_selection import train_test_split
import sklearn.datasets
from sklearn.metrics import accuracy_score
import hiddenlayer as hl
import warnings
warnings.filterwarnings("ignore")
from torchviz import make_dot, make_dot_from_trace
Les lignes suivantes permettent de ne pas afficher les warning en python :
import warnings
warnings.filterwarnings("ignore")
Je vais générer 1000 échantillons générés par la librairie sklearn me permettant d’avoir un jeu de tests pour un problème de classification binaire. Le jeu de tests porte sur 2 entrées décimales et une sortie binaire (0 ou 1). J’affiche également le résultat sous forme d’un nuage de point :
Création de 1000 échantillons avec un résultat 0 ou 1 via sklearn
Le jeu de test ici généré correspond à un jeu de données avec 2 classes (classe 0 et 1).
L’objectif de mon réseau de neurone est donc une classification binaire de l’input.
Je vais prendre 20% de ce jeu de test comme donnée de test et les 80% restant comme données d’entrainement. Je split à nouveau le jeu de test pour créer un jeu de validation sur le jeu de données d’entrainement.
Dans mon exemple je vais créer un réseau avec une architecture quelconque ce qui nous intéresse c’est de montrer le fonctionnement de la dernière couche :
couche d’entrée (input layer) : fonction d’activation linéaire
Dans le cadre de ce pytorch tutorial, J’utilise l’optomizer Adam avec un learning rate de 0.01 : Les optimiseurs en deep learning sont des algorithmes ou des méthodes utilisés pour modifier les attributs de votre réseau neuronal tels que les poids et le biais de tel manière que la fonction de cout (loss function) soit minimisée.
Le taux d’apprentissage est un hyperparamètre qui contrôle dans quelle mesure le modèle doit être modifié en réponse à l’erreur estimée chaque fois que les poids du modèle sont mis à jour.
J’ai préalablement splits une seconde fois les données d’entrainement pour prendre 20% des données comme des données de validations. Elle nous permettent à chaque entrainement de valider que nous ne faisons pas de surraprentissage (sur-ajustement, ou encore surinterprétation, ou simplement en anglais overfitting) .
Dans cet exemple j’ai choisi d’implémenter le EarlyStopping algorithme avec une patience de 5. Cela signifie que si la fonction de cout des données de validation augmente durant 15 entrainements (soit la distance entre la prédiction et les données vraies). Après 15 entrainements avec une distance qui augmente on recharge les données précédentes qui représente la configuration du réseau de neurone produisant une distance de la fonction de cout minimale (dans le cas de notre exemple cela consiste à recharger le poids et le biais pour les 2 couches linéaires). Tant que la fonction diminue on sauvegarde la configuration du réseau de neurones (poids et biais des couches linéaire dans notre exemple).
Ici j’ai choisi d’afficher les poids et le biais des 2 couches linéaire tous les 10 entrainements, pour vous donner une idée de comment fonctionne l’algorithme d’optimisation Adam :
J’ai utilisé https://github.com/waleedka/hiddenlayer pour afficher divers graphique autour des métriques de training et validation. Les graphiques sont ainsi rafraîchi en cours d’utilisation.
history1 = hl.History()
canvas1 = hl.Canvas()
Ici le code principal de la boucle d’apprentissage :
bestvalidloss = np.inf
saveWeight1 = fc1.weight
saveWeight2 = fc2.weight
saveBias1 = fc1.bias
saveBias2 = fc2.bias
wait = 0
for epoch in range(1000):
model.train()
optimizer.zero_grad()
result = model(torch.tensor(X_train,dtype=torch.double))
lossoutput = loss(result, torch.tensor(y_train,dtype=torch.double))
lossoutput.backward()
optimizer.step()
print("EPOCH " + str(epoch) + "- train loss = " + str(lossoutput.item()))
if((epoch+1)%10==0):
#AFFICHE LES PARAMETRES DU RESEAU TOUT LES 10 entrainements
print("*************** PARAMETERS WEIGHT & BIAS *********************")
print("weight linear1= " + str(fc1.weight))
print('Bias linear1=' + str(fc1.bias))
print("weight linear2= " + str(fc2.weight))
print('bias linear2=' + str(fc2.bias))
print("**************************************************************")
model.eval()
validpred = model(torch.tensor(X_valid,dtype=torch.double))
validloss = loss(validpred, torch.tensor(y_valid,dtype=torch.double))
print("EPOCH " + str(epoch) + "- valid loss = " + str(validloss.item()))
# Store and plot train and valid loss.
history1.log(epoch, trainloss=lossoutput.item(),validloss=validloss.item())
canvas1.draw_plot([history1["trainloss"], history1["validloss"]])
if(validloss.item() < bestvalidloss):
bestvalidloss = validloss.item()
#
saveWeight1 = fc1.weight
saveWeight2 = fc2.weight
saveBias1 = fc1.bias
saveBias2 = fc2.bias
wait = 0
else:
wait += 1
if(wait > 15):
#Restauration des mailleurs parametre et early stopping
fc1.weight = saveWeight1
fc2.weight = saveWeight2
fc1.bias = saveBias1
fc2.bias = saveBias2
print("##############################################################")
print("stop valid because loss is increasing (EARLY STOPPING) afte EPOCH=" + str(epoch))
print("BEST VALID LOSS = " + str(bestvalidloss))
print("BEST PARAMETERS WHEIGHT AND BIAS = ")
print("FIRST LINEAR : WEIGHT=" + str(saveWeight1) + " BIAS = " + str(saveBias1))
print("SECOND LINEAR : WEIGHT=" + str(saveWeight2) + " BIAS = " + str(saveBias2))
print("##############################################################")
break
else:
continue
Voici un aperçu du résultat, l’entraînement s’arrête au bout d’environ 200 epoch (une « epoch » est un terme utilisé en machine learning pour désigner un passage du jeu de donnée d’entrainement complet). Dans mon exemple je n’ai pas utilisé de batch pour charger les données le nombre d’epoch est donc le nombre d’itérations.
Evolution de la fonction de cout sur le test d’entrainement et le test de validation (pytorch tutorial)
Résultats : Le premier graphique montre la réponse « vraie » la seconde montre la réponse prédite (la couleur varie en fonction de la probabilité prédite) – pytorch tutorial
Pour afficher l’architecture du réseau de neurone j’ai utilisé la librairie hidden layer qui nécessite l’installation de graphviz pour éviter l’erreur suivante :
RuntimeError: Make sure the Graphviz executables are on your system's path
Hidden Layer architecture pour le classifier binaire
J’ai également utilisé PyTorchViz https://github.com/szagoruyko/pytorchviz/blob/master/examples.ipynb pour afficher un graphe des opérations de Pytorch pendant le forward d’une entrée et on peut voir ainsi clairement ce qui va se passer lors du backward (c’est à dire l’application le calcul de la différentiel dols/dx pour tout les paramètres x du réseau qui a requires_grad=True).
Diagramme d’architecture du réseau de neurone créé avec PyTorch tuorial
Problème de régression (calcul de valeur numérique/décimale) :
Vous cherchez dans ce cas à prédire au moyen de votre algorithme de DeepLearning une grandeur numérique continue. Dans ce cas l’algorithme de descente du gradient consiste a comparer la différence entre la valeur numérique prédite par le réseau et la valeur vraie. La taille de sortie du réseau sera 1 puisqu’il y a une seule valeur à prédire.
Fonction d’activation finale (cas valeur décimale ou numérique) :
La fonction d’activation à utiliser dans ce cas dépend de la plage dans laquelle votre donnée est située.
Pour une donnée entre -infinie et + infinie alors vous pouvez utiliser une fonction linéaire en sortie de votre réseau.
Fonction graphe de fonction Linear. https://pytorch.org/docs/stable/generated/torch.nn.Linear.html. La particularité est que cette fonction linéaire (du type y = ax + b)contient des paramètres apprenable (weight and bias qui sont modifiés par l’optimizer au fil des entrainements soit y = weight * x + bias).
Vous pouvez également utiliser la fonction Relu si votre valeur à prédire est strictement positive la sortie de ReLu est la valeur maximale entre zéro et la valeur d’entrée. Une sortie est égale à zéro lorsque la valeur d’entrée est négative et la valeur d’entrée lorsque l’entrée est positive. A noter que contrairement à la fonction d’activation linéaire rectifiée Relu ne possède pas de paramètre ajustable (learnable).
La fonction de coût (cas régression, calcul de valeur numérique) :
La fonction de cout qui permet de déterminer la distance entre la valeur prédite et la valeur réelle est la moyenne de la distance au carré entre les 2 prédictions. La fonction à utiliser est mean squared error (MSE):https://pytorch.org/docs/stable/generated/torch.nn.MSELoss.html
Voici un exemple simple qui illustre l’utilisation de chacune des fonctions finales :
Je suis parti au départ de l’exemple du prix des maisons que j’ai ensuite adapté pour faire le test avec chacune des fonctions.
Exemple : Chargement des données de tests
Dans un premier temps j’importe les librairies nécessaires :
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from collections import OrderedDict
import math
from random import randrange
import torch
from torch.autograd import Variable
import torch.nn as nn
from torch.autograd import Function
from torch.nn.parameter import Parameter
from torch import optim
import torch.nn.functional as F
from torchvision import datasets, transforms
from echoAI.Activation.Torch.bent_id import BentID
from echoAI.Activation.Torch.soft_exponential import SoftExponential
from sklearn.model_selection import train_test_split
import sklearn.datasets
from sklearn.metrics import accuracy_score
import hiddenlayer as hl
import warnings
warnings.filterwarnings("ignore")
from torchviz import make_dot, make_dot_from_trace
from sklearn.datasets import make_regression
from torch.autograd import Variable
Je crée le jeu de données qui est assez simple et je l’affiche :
Le réseau éxecute donc ici la fonction f(x) = -0.0408 * x + 8.1321
J’affiche ensuite le résultat prédit pour le comparer avec le résultat réel :
result = model(house_price_tensor)
plt.scatter(house_prices_array, house_size_np)
plt.title("True")
plt.show()
plt.scatter(house_prices_array,result.detach().numpy())
plt.title("predicted")
plt.show()
Voici un aprerçu du diagramme d’architecture pour un simple réseau de neurone Pytorch avec fonction Linéaire, on voit l’opérateur de multiplication et l’opérateur d’addition pour executer y = ax + b.
Fonction d’activation ReLu (Résolution problème de régression):
ReLu n’étant pas une fonction d’activation avec des paramètres « apprenables » (modifié par l’optimiseur) j’ajoute donc une couche linéaire en amont pour le test :
Le résultat est identique, ce qui est logique puisque dans mon cas reLu ne fait que passer le résultat qui est strictement positif
Dans l’exemple précédent il faut ajouter une couche ReLu en sortie après la couche linéaire :
fc1 = nn.Linear(1, 1)
model = nn.Sequential(OrderedDict([
('lin', fc1),
('relu',nn.ReLU())
]))
model = model.float()
fc1.weight.data.fill_(-0.01)
fc1.bias.data.fill_(8)
Architecture du modèle avec couche linéaire + couche ReLu – pytorch tutorial
De même pour PrRelu dans mon cas: Ces Deux fonctions font simplement un passe plat entre la fonction linéaire et la sortie. ReLu reste intéressant si vous souhaitez mettre à 0 tout les sortie concernant une entrée négative.
Fonction Bent Identity (Résolution problème de régression) :
Bent identity il n’y a pas de paramètre apprenante mais la fonction ne fait pas que forwarder l’entrée elle y applique la fonction identité courbée qui modifie légèrement le résultat :
fc1 = nn.Linear(1, 1)
model = nn.Sequential(OrderedDict([
('lin', fc1),
('BentID',BentID())
]))
model = model.float()
fc1.weight.data.fill_(-0.01)
fc1.bias.data.fill_(8)
Dans notre cas après 100 entrainements le réseau a trouvé les poids suivant pour la fonction linéaire en amont de bent identity le loss final est de 0.78 donc moin bon qu’avec la fonction linéaire (le réseau converge moins vite) :
Dans notre cas la fonction appliquée par le réseau sera donc :
Fonction exponentielle douce (Soft Exponential) – (Résolution de problème de régression)
Soft Exponential possède un paramètre entrainable alpha nous allons placer une fonction linéaire en amont et softExponential en sortie et vérifier l’approximation effectuée dans ce cas :
fc1 = nn.Linear(1, 1)
fse = SoftExponential(1,torch.tensor([-0.9],dtype=torch.float))
model = nn.Sequential(OrderedDict([
('lin', fc1),
('SoftExponential',fse)
]))
model = model.float()
fc1.weight.data.fill_(-0.01)
fc1.bias.data.fill_(8)
Après 100 entrainements le résultats sur les paramètre de la couche linéaire et les paramètre de la couche soft exponential sont les suivants :
Le résultat n’est pas vraiment bon puisque l’approximation ne se fait pas dans le bon sens,
On remarque donc qu’on pourrait inverser la fonction dans notre cas définir une fonction d’activation customize de Soft Exponential avec un critère de biais et c’est ce que nous allons faire ici.
Fonction Custom – (Résolution de problème de régression)
On déclare une fonction d’activation custom à PyTorch par rapport au soft exponential d’origine j’ai ajouté le critère de biais beta ainsi que l’inversion torch.div(1,…)
class SoftExponential2(nn.Module):
def __init__(self, in_features, alpha=None,beta=None):
super(SoftExponential2, self).__init__()
self.in_features = in_features
# initialize alpha
if alpha is None:
self.alpha = Parameter(torch.tensor(0.0)) # create a tensor out of alpha
else:
self.alpha = Parameter(torch.tensor(alpha)) # create a tensor out of alpha
if beta is None:
self.beta = Parameter(torch.tensor(0.0)) # create a tensor out of alpha
else:
self.beta = Parameter(torch.tensor(beta)) # create a tensor out of alpha
self.alpha.requiresGrad = True # set requiresGrad to true!
self.beta.requiresGrad = True # set requiresGrad to true!
def forward(self, x):
if self.alpha == 0.0:
return x
if self.alpha < 0.0:
return torch.add(torch.div(1,(-torch.log(1 - self.alpha * (x + self.alpha)) / self.alpha)),self.beta)
if self.alpha > 0.0:
return torch.add(torch.div(1,((torch.exp(self.alpha * x) - 1) / self.alpha + self.alpha)),self.beta)
On a maintenant 2 paramètres entrainable dans cette fonction custom à Pytorch.
En abaissant également le taux d’apprentissage learning rate à 0.01 au bout de 100 entrainement et en initialisant alpha = 0 .1 et beta = 0.7 j’arrive à un loss < 5
fse = SoftExponential2(1,torch.tensor([0.1],dtype=torch.float),torch.tensor([7.0],dtype=torch.float))
model = nn.Sequential(OrderedDict([
('SoftExponential',fse)
]))
model = model.float()
fc1.weight.data.fill_(-0.01)
fc1.bias.data.fill_(8)
Architecture du réseau appliqué pour ma fonction custom inversion de soft exponentialt avec ajout d’un critère de biais.
Problème de catégorisation (prédire une classe parmi plusieurs classes possible) – single-label classifier avec pytorch
Vous cherchez à prédire la probabilité que votre entrée corresponde à une classe unique en sortie paris plusieurs classes possible. Par exemple vous souhaitez prédire le type de véhicule sur une image permis les classes : voiture, camion, train
Le dimensionnement de votre réseau en sortie correspond à n neurones pour n classes. Et pour chaque neurones de sortie correspondant à une classe possible à prédire on obtiendra une probabilité entre 0 et 1 qui représentera la probabilité que l’entrée correspondent à cette classe en sortie. Ainsi pour chaque classe cela revient à une résolution d’un problème de classification binaire dans la partie 1 mais en plus duquel il faut considérer qu’une entrée ne peut correspondre qu’à une seule classe en sortie.
Fonction d’activation Problème de catégorisation (prédire une classe parmi plusieurs classes possibles) :
La fonction d’activation à utiliser sur la couche finale est une fonction Softfmax avec n dimensions correspondant au nombre de classe à prédire. Softmax est une fonction mathématique qui convertit un vecteur de nombres (tensor) en un vecteur de probabilités, où les probabilités de chaque valeur sont proportionnelles à l’échelle relative de chaque valeur dans le vecteur. (Cf https://machinelearningmastery.com/softmax-activation-function-with-python/)
En d’autres terme pour un tensor de sortie il va retourner une probabilité pour chaque classe en échelonnant chacune d’elle pour que leur somme soit égale à un.
Fonction de cout – Problème de catégorisation (prédire une classe parmi plusieurs classes possibles) :
La fonction de cout à utiliser est proche de celle utilisée dans le cas de la classification binaire mais avec cette notion de vecteur de probabilité. Cross Entropy va evéluer la différence entre 2 distributions de probabilité. On va donc l’utiliser pour comparer la valeur prédite et la valeur vraie.
Dans notre exemple on va dans un premier temps récupérer le jeu de données en entrée Le dataset utilisé est CIFAR-10, plus d’information ici : https://www.cs.toronto.edu/~kriz/cifar.html
Celui-ci est déjà intégré à Pytorch pour nous permettre d’effectuer certain test.
Un réseau de neurones convolutifs (ConvNet ou CNN) est un algorithme de DeepLearning qui peut prendre une image en entrée, il fixe un score (poids et biais qui sont des paramètres apprenables) à divers aspects / objets de l’image et être capable de différencier l’un de l’autre.
L’architecture d’un réseau de neurone convolutif est proche de celle du modèle de connectivité des neurones dans le cerveau humain et a été inspirée par l’organisation du cortex visuel.
Les neurones individuels ne répondent aux stimuli que dans une région restreinte du champ visuel connue sous le nom de champ récepteur. Une collection de ces champs se chevauchent pour couvrir toute la zone visuelle.
Dans notre cas nous allons utiliser avec Pytorch une couche Conv2d et une couche de pooling.
Un filtre dans une couche conv2D a une hauteur et une largeur. Ils sont souvent plus petits que l’image d’entrée. Ce filtre se déplace donc sur toute l’image au fil de l’entrainement (cette zone est appelée champ réceptif).
La couche de Max Pooling est un processus d’échantillonage. L’objectif est de sous-échantillonner une représentation d’entrée (image par exemple), en réduisant sa dimension et en faisant des hypothèses sur les caractéristiques contenues dans les sous-régions regroupées.
Dans mon exemple avec PyTorch la déclaration se fait :
import torch.nn as nn
import torch.nn.functional as F
class Net(nn.Module):
def __init__(self):
super(Net, self).__init__()
self.conv1 = nn.Conv2d(3, 6, 5)
self.pool = nn.MaxPool2d(2, 2)
self.conv2 = nn.Conv2d(6, 16, 5)
self.fc1 = nn.Linear(16 * 5 * 5, 120)
self.fc2 = nn.Linear(120, 84)
self.fc3 = nn.Linear(84, 10)
def forward(self, x):
x = self.pool(F.relu(self.conv1(x)))
x = self.pool(F.relu(self.conv2(x)))
x = x.view(-1, 16 * 5 * 5)
x = F.relu(self.fc1(x))
x = F.relu(self.fc2(x))
x = self.fc3(x)
return x
net = Net()
Définir le critère de la fonction de cout avec CrossEntropyLoss, ici on utilise l’opimizer SGD plutot que adam (plus d’info ici sur les comparaison entre optimizer https://ruder.io/optimizing-gradient-descent/)
for epoch in range(2): # loop over the dataset multiple times
running_loss = 0.0
for i, data in enumerate(trainloader, 0):
# get the inputs; data is a list of [inputs, labels]
inputs, labels = data
# zero the parameter gradients
optimizer.zero_grad()
# forward + backward + optimize
outputs = net(inputs)
loss = criterion(outputs, labels)
loss.backward()
optimizer.step()
# print statistics
running_loss += loss.item()
if i % 2000 == 1999: # print every 2000 mini-batches
print('[%d, %5d] loss: %.3f' %
(epoch + 1, i + 1, running_loss / 2000))
running_loss = 0.0
print('Finished Training')
Dans cet exemple les labels « vrai » sont « Cat, ship, ship, plane », on lance alors le réseau pour faire une prédiction :
net = Net()
net.load_state_dict(torch.load(PATH))
outputs = net(images)
_, predicted = torch.max(outputs, 1)
print('Predicted: ', ' '.join('%5s' % classes[predicted[j]]
for j in range(4)))
Voici un aperçu de l’architecture de ce réseau de convolution.
import hiddenlayer as hl
from torchviz import make_dot, make_dot_from_trace
make_dot(net(images), params=dict(net.named_parameters()))
Problème de catégorisation (prédire plusieurs classe parmi plusieurs classes possible) – multiple-label classifier avec pytorch
Globalement il s’agit de prédire plusieurs probabilités pour chacune des classes pour indiquer leurs probabilités de présence dans l’entrée. Une utilisation possible est d’indiquer la présence d’un objet dans une image.
Le problème revient alors à un problème de classification binaire pour n classes.
La fonction d’activation finale est sigmoid et la fonction loss est Binary cross entropy
Dans ce dataset de données, il y a 200K images avec 40 étiquettes de classe différentes et chaque image a un encombrement d’arrière-plan différent et il y a beaucoup de variations différentes, ce qui rend difficile pour un modèle de classer efficacement chaque étiquette de classe.
Step3 : En ouvrant le fichier des annotations vous pouvez consultez les 40 étiquettes : 5_o_Clock_Shadow Arched_Eyebrows Attractive Bags_Under_Eyes Bald Bangs Big_Lips Big_Nose Black_Hair Blond_Hair Blurry Brown_Hair Bushy_Eyebrows Chubby Double_Chin Eyeglasses Goatee Gray_Hair Heavy_Makeup High_Cheekbones Male Mouth_Slightly_Open Mustache Narrow_Eyes No_Beard Oval_Face Pale_Skin Pointy_Nose Receding_Hairline Rosy_Cheeks Sideburns Smiling Straight_Hair Wavy_Hair Wearing_Earrings Wearing_Hat Wearing_Lipstick Wearing_Necklace Wearing_Necktie Young Pour chacune des image présente dans le jeu de test il y a une valuer 1 ou -1 précisant pour image si la classe est présente dans l’image. L’objectif ici sera de prédire pour chacune des classe la probabilité de sa présence dans l’image.
Un aperçu de l’architecture du réseau (pytorch tutorial) :
SYNTHESE :
Voici une fiche de synthèse que j’ai créé pour vous permettre de plus rapidement choisir la bonne fonction d’activation et la bonne fonction de coût en fonction de votre problème à résoudre.
Pytorch tutorial – LES 5 MEILLEURS LIENS SUR LE DEEP LEARNING
L’algorithme d’apprentissage des k plus proches voisins (KNN) est utilisé pour effectuer de la classification de données.
Pour prédire la classification d’une nouvelle donnée, l’algorithme se base sur les k enregistrements issus de l’ensemble de données d’apprentissage sont alors localisés les plus similaires à ce nouvel enregistrement.
La similitude entre les enregistrements peut être mesurée de différentes manières. Généralement un bon point de départ est la distance euclidienne.
L’algorithme est le suivant :
Pour une entrée x quelle est sa classe y si je me base sur les k voisins les plus proches de x ?
Trouver les k entrée partie les données d’entrainement qui sont les plus « proches » de mon entrée x (ici on utilisera par exemple la distance euclidienne)
Faire voter chacune de ces données d’entrainement pour sa classe y.
Retourner la classe majoritaire
Le succès de l’algorithme va reposer sur la quantité de donnée d’entrainement et sur la qualité de la mesure de la distance entre 2 vecteurs x.
Voici un exemple d’utilisation et d’implémentation Python sur la base de données qui concerne l’accord d’un crédit en fonction de l’age et du montant demandé. La classe correspond à la réponse OUI ou NON.
from math import sqrt
# Faire une predicition de la classification
def predire_classification(donnee_test, entrainement, nombre_voisins_vote):
voisins = recherche_voisins(entrainement, donnee_test, nombre_voisins_vote)
sortie = [vecteur[-1] for vecteur in voisins]
prediction = max(set(sortie), key=sortie.count)
return prediction
#Distance euclidienne de 2 vecteurs
def distance_euclidienne(vecteur1, vecteur2):
distance = 0.0
for i in range(len(vecteur1)-1):
distance += (vecteur1[i] - vecteur2[i])**2
return sqrt(distance)
# Recherche les voisins
def recherche_voisins(entrainement, donnee_test, nbVoisins):
distances = list()
for ligneEntrainement in entrainement:
dist = distance_euclidienne(donnee_test, ligneEntrainement)
distances.append((ligneEntrainement, dist))
distances.sort(key=lambda tup: tup[1])
kVoisins = list()
for i in range(nbVoisins):
kVoisins.append(distances[i][0])
return kVoisins
# Données d'entrainement
donneesApprentissage = [[25,40000,'NON'],
[30,60000,'OUI'],
[35,80000,'NON'],
[45,50000,'NON'],
[20,60000,'NON'],
[60,15000,'NON'],
[70,5000,'OUI'],
[80,1000,'NON'],
[33,80000,'OUI'],
[32,10000,'NON']]
prediction = predire_classification(donneesApprentissage[1], donneesApprentissage, 3)
print('On devrait trouver %s, la prediction est : %s.' % (donneesApprentissage[1][-1], prediction))
Je traite ici des bases du langage Python pour l’apprendre rapidement. En France ces bases sont enseignées en lycée aux classes de seconde SNT, première et terminale NSI. Elles font également partie du programme de connaissance pour le CAPES NSI.
Regroupement de fonctions :
Un module est un fichier qui contient un ensemble de fonctions que vous souhaitez inclure dans votre application.
La fonction dir est une fonction intégrée pour répertorier tous les noms de fonction (ou noms de variable) dans un module.
import platform
res = dir(platform)
print(res)
Il est possible de n’importer que des parties d’un module, en utilisant le mot-clé from.
from monmodule import salutations
salutations("Jean")
Packages :
Les packages permettent une structuration hiérarchique de l’espace de noms du module.
Les packages aident à éviter les collisions entre les noms de modules.
La création d’un package est assez simple, car elle utilise la structure en répertoire du système d’exploitation.
Si on considère un répertoire nommé pkg qui contient deux modules, module1.py et module2.py.
Le contenu des modules est:
def test():
print('test module 1')
class Toto:
pass
def test2():
print('test module 2')
class Joe:
pass
Avec cette structure, si le répertoire pkg est dans un emplacement où il peut être trouvé (càd un des répertoires contenus dans sys.path).
Il est possible de se référer aux deux modules (pkg.module1, pkg.module2) et de les importer :
import pkg.module1, pkg.module2
pkg.module1.test()
x = pkg.module2.Joe()
Valeurs aléatoires (random value) :
import random
print(random.random()) #Retourne un nombre décimal aléatoirement entre 0 et 1
print(random.randint(10,20)) #Retourne un entier dans l'écart défini
membre = ["Seb","Jean","Louise"]
print(random.choice(membre)) #Retourne un élément de la liste aléatoirement
Je traite ici des bases du langage Python pour l’apprendre rapidement. En France ces bases sont enseignées en lycée aux classes de seconde SNT, première et terminale NSI. Elles font également partie du programme de connaissance pour le CAPES NSI.
Exceptions :
Lorsqu’une erreur se produit, (une exceptions) elle peut être gérée à l’aide de l’instruction try:
try:
print(r)
except NameError:
print("variable r non définie")
except:
print("Autre exception")
Commentaires :
#Ceci est un commentaire
#sur
#plusieurs ligne
print("Bonjour Python")
"""
Ceci est un commentaire
sur
plusieurs ligne
"""
print("Bonjour Python")
Classes :
Les classes sont comme un constructeur d’objet, cela permet de modeler des concepts réels.
class Personne:
def __init__(self, nom, age):
self.nom = nom
self.age = age
def ma_fonction(self):
print("Nom de la personne : " + self.name)
p1 = Personne("Sébastien", 36)
print(p1.nom)
print(p1.age)
p1.ma_fonction()
p1.age = 40 #Modification des propriétés de l'objet
del p1.age #supprime la propriété de l'objet
del p1 #supprime l'objet
self est une référence à l’instance actuelle de la classe et est utilisé pour accéder aux variables qui appartiennent à la classe. Il peut être nommé autrement que self, mais ce doit être obligatoirement le premier paramètre de toute fonction de la classe.
Héritage :
L’héritage permet de définir une classe qui hérite de toutes les méthodes et propriétés d’une autre classe.
class Animal :
def marcher():
print('marche')
class Chien(Animal)
pass
c1 = Chien()
c1.marcher()
Constructeur :
La fonction __init __ () est appelée automatiquement chaque fois qu’un nouvel objet est créé.
super () fera que la classe enfant héritera de toutes les méthodes et propriétés de son parent.
class Etudiant(Personne):
def __init__(self, nom, prenom):
super().__init__(nom, prenom)
Je traite ici des bases du langage Python pour l’apprendre rapidement. En France ces bases sont enseignées en lycée aux classes de seconde SNT, première et terminale NSI. Elles font également partie du programme de connaissance pour le CAPES NSI.
Tuples :
Un tuple est une collection ordonnée comme les listes et immuable (qui ne change pas).
exempleTuple = ("pomme", "poire", "fraise")
print(exempleTuple)
print(exempleTuple[1])
print(exempleTuple[-1]) #L'indexation négative signifie à partir de la fin, -1 se réfère au dernier élément, -2 se réfère à l'avant-dernier élément, etc.
print(exempleTuple[1:2]) #Vous pouvez spécifier une plage d'index en spécifiant par où commencer et où terminer la plage.
z = list(exempleTuple) #conversion tuple en liste
z[1] = "banane"
x = tuple(z) #conversion liste en tuple
for x in exempleTuple: #Boucle sur un tuple
print(x)
if "poire" in exempleTuple: #test d'existence dans un tuple
print("Oui")
Un dictionnaire est une collection non ordonnée, modifiable et indexée.
client = {
"nom": "Elodie",
"age": "45",
"annee": 1980
}
print(client["age"])
client["nouvelleCle"] = "nouvelleValeur" #ajoute une nouvelle clé et valeur
client.get("solde") #renvoi 'None' car la clé n'existe pas
Fonctions :
Les fonctions permettent d’organiser le code en morceau réutilisables. En Python, une fonction est définie à l’aide du mot clé def.
Les données peuvent être passées aux fonctions en tant que paramètre. Vous pouvez ajouter autant de paramètres que vous le souhaitez, il suffit de les séparer par une virgule.