Apprentissage Statistique - webia.lip6.frwebia.lip6.fr/...2017-Apprentissage-Statistique-M2.pdf · l'apprentissage statistique, l'agrégation de données hétérogènes, la visualisation - [PDF Document] (2024)

Apprentissage Statistique

Université Paris 6 - Master DAC et Master Math Spécialité Big Data - P. Gallinari, [emailprotected], http://www-connex.lip6.fr/~gallinar/

L. Denoyer, [emailprotected], Nicolas Baskiotis, [emailprotected], O. Schwandler, [emailprotected]

Année 2016-2017

Plan du cours

Apprentissage Statistique - P. Gallinari2

Introduction Apprentissage à partir d’exemples Exemple introductif : le perceptron

Formalisation du problème d’apprentissage Apprentissage supervisé

Réseaux de neurones Réseaux de neurones profonds (deep learning) et apprentissage de

représentations Réseaux récurrents Machines à noyaux, machines à vecteurs de support

Apprentissage non supervisé Algorithme EM et mélange de densités Clustering spectral Factorisation matricielle Autoencodeurs variationnels

Livres de référence

Apprentissage Statistique - P. Gallinari3

Les deux livres suivants couvrent la matière du cours Pattern recognition and Machine Learning, C. Bishop, Springer, 2006

En particulier les chapitres 3, 4, 5, 6, 7, 9,

Deep Learning, An MIT Press book, I. Goodfellow, Y. Bengio and A. Courville, Version pdf accessible : http://www.deeplearningbook.org/

Il existe de nombreux autres livres que l’on peut consulter avec profit, par exemple : The Elements of Statistical Learning: Data Mining, Inference, and Prediction,

Second Edition, T. Hastie, R. Tibshirani, J. Friedman, Springer, 2009 Version pdf accessible : http://statweb.stanford.edu/~tibs/ElemStatLearn/

Bayesian Reasoning and Machine Learning, D. Barber, Cambridge University Press, 2012 Version pdf accessible : http://www.cs.ucl.ac.uk/staff/d.barber/brml/

Introduction

Apprentissage à partir d'exemples

Apprentissage Statistique - P. Gallinari5

3 ingrédients de base Données {z1, ..., zN} Machine ou modèle Fθ Critère C (apprentissage et évaluation)

But Extraire de l'information à partir des données

Information pertinente pour la tâche étudiée pour d'autres données du même type

Utilisation Inférence sur de nouvelles données

Type d'apprentissage : Supervisé Non supervisé Semi supervisé Renforcement

Exemples - problèmes d'apprentissage

Apprentissage Statistique - P. Gallinari6

Parole / Ecriture Données : (signal, (transcription)) But : reconnaître signal Critère : # mots correctement reconnus

Conduite véhicule autonome Données : (images routes, (commande volant)) e.g. S. Thrun Darpa Challenge +

Google car But : suivre route Critère : distance parcourue

Recherche d'information textuelle Données : (texte + requête, (information pertinente)) – corpus d’apprentissage But : extraire l'information correspondant à la requête Critère : Rappel / Précision

Diagnostic dans systèmes complexes Données : (état capteurs + alarmes, (diagnostic)) But : diagnostic correct Critère : ?

Exemples - problèmes d'apprentissage

Apprentissage Statistique - P. Gallinari7

Modélisation d'utilisateur Données : (Traces utilisateur) But : analyser/ modéliser le comportement de l'utilisateur

Exemples : ciblage clientèle, aide navigation, publicité, recommandation, assistants personnels e.g. Google Now, etc

Critère : ? Evaluation : ? Example Google Now

Google Now keeps track of searches, calendar events, locations, and travel patterns. It then synthesizes all that info and alerts you—either through notifications in the menu bar or cards on the search screen—of transit alerts for your commute, box scores for your favorite sports team, nearby watering holes, and more. You can assume it will someday suggest a lot more.

Exemples - problèmes d'apprentissage

Apprentissage Statistique - P. Gallinari8

Plus complexe: Traduction Extraction d’information (e.g. Never-Ending Language/ Image Learning) Compréhension de texte / scène visuelle – extraction de sens Découverte dans bases de données ou bases de connaissances, web, etc

Données : i.e. représenter l'information ??

But ??

Critère ??

Evaluation ??

Données : diversité

Apprentissage Statistique - P. Gallinari9

Données : quantitésYahoo! Data – A league of its own… U. Fayyad KDD’07

Apprentissage Statistique - P. Gallinari10

Terrabytes of Warehoused Data

25 49 94 100500

1,000

5,000

Amaz

on

Kore

a

Teleco

m

AT&T

Y! L

iveS

tor

Y! P

anam

a

War

ehou

se

Walm

art

Y! M

ain

war

ehou

se

GRAND CHALLENGE PROBLEMS OF DATA PROCESSING

TRAVEL, CREDIT CARD PROCESSING, STOCK EXCHANGE, RETAIL, INTERNET

Y! PROBLEM EXCEEDS OTHERS BY 2 ORDERS OF MAGNITUDE

Millions of Events Processed Per Day

50 120 2252,000

14,000

SABRE VISA NYSE Y! Panama Y! DataHighway

Données : quantitésPetabytes (10^15) (chiffres 2012)

Apprentissage Statistique - P. Gallinari11

Google processes about 24 petabytes of data per day Google Street View Has Snapped 20 Petabytes of Street Photos Telecoms: AT&T transfers about 30 petabytes of data through its

networks each day Physics: The experiments in the Large Hadron Collider produce

about 15 petabytes of data per year Neurology: It is estimated that the human brain's ability to store

memories is equivalent to about 2.5 petabytes of binary data

Big Data: Volume, Velocity, Variety, and Veracity http://www-01.ibm.com/software/data/bigdata/

Apprentissage Statistique - P. Gallinari12

Volume: terabytes, petabytes Turn 12 terabytes of Tweets created each day into improved product sentiment

analysis Convert 350 billion annual meter readings to better predict power consumption

Velocity: streams Scrutinize 5 million trade events created each day to identify potential fraud Analyze 500 million daily call detail records in real-time to predict customer churn

faster Variety: Big data is any type of data - structured and unstructured data such

as text, sensor data, audio, video, click streams, log files and more. New insights are found when analyzing these data types together. Monitor 100’s of live video feeds from surveillance cameras to target points of

interest Exploit the 80% data growth in images, video and documents to improve customer

satisfaction Veracity: Establishing trust in big data presents a huge challenge as the

variety and number of sources grows.

Gartner Hype Cycle: Machine Learning

Apprentissage Statistique - P. Gallinari13

2015: 1ere apparition du Machine Learning qui ne serait déjà plus dans le Hype, Big Data sort de la figure …

Apprentissage Statistique - P. Gallinari14

Data driven science – le 4e paradigme (Jim Gray MSR – Prix Turing)

SNRI 2013 : https://www.allistene.fr/contribution-dallistene-et-des-poles-de-competitivite-a-la-strategie-nationale-de-recherche-sciences-et-technologie-du-numerique/

Extrait : « À l’heure actuelle, la science vit une révolution qui conduit à un nouveau paradigme selon lequel "la science est dans les données", autrement dit la connaissance émerge du traitement des données. »… » « Le traitement de données et la gestion de connaissances représentent ainsi le quatrième pilier de la science après la théorie, l'expérimentation et la simulation. L'extraction de connaissances à partir de grands volumes de données (en particulier quand le nombre de données est bien plus grand que la taille de l’échantillon) , l'apprentissage statistique, l'agrégation de données hétérogènes, la visualisation et la navigation dans de grands espaces de données et de connaissances sont autant d'instruments qui permettent d'observer des phénomènes, de valider des hypothèses, d'élaborer de nouveaux modèles ou de prendre des décisions en situation critique »

2015/01/29Apprentissage Automatique - P. Gallinari15

Place de l’apprentissage

Apprentissage Statistique - P. Gallinari16

L’apprentissage constitue une brique dans le processus de fouille / traitement de données qui arrive souvent à la fin du processus qui est intégré dans une application ou dans le SI de l’entreprise

Les différentes étapes de l’analyse des données Collecte des données / stockage Prétraitement des données, étiquetage éventuel Analyses des données par des techniques exploratoires Mise au point et test de différents modèles d’apprentissage Evaluation

Domaines d’application en Data MiningExemples

Apprentissage Statistique - P. Gallinari17

Web recherche d'information, filtrage d'information extraction d'information textuelle : e.g. recherche, bibliothèques virtuelles, veille

technologique, Question Answering , ... Multi-média

image + son, vidéo Données d’entreprise

infos produits, infos clients, ciblage clientèle ... Analyse comportement

e.g. telecoms : serveurs web, accès services commerciaux, internet - intranet, aide accès information, publicité

Distribué Mobiles : personnalisation, accès information Capteurs distribués, objets connectés

Biologie - analyse de séquences, de structures Automobile ...

4 Familles de problèmes

Apprentissage Statistique - P. Gallinari18

4 familles de problèmes d’apprentissage L’apprentissage propose des outils pour traiter des problèmes

génériques C’est un domaine transverse à des domaines « d’application »

comme la finance, la publicité, la vision, etc. Les 4 grandes familles de problèmes d’apprentissage

Supervisé Non supervisé Semi-supervisé Renforcement

Chaque famille traite d’un ensemble de problèmes génériques propres Exemple de problème générique

En supervisé : classification, regression, ordonnancement,

2015/01/29Apprentissage Automatique - P. Gallinari19

Apprentissage supervisé Ensemble d'apprentissage constitué de couples (entrée, sortie

désirée) , , … , , Objectif : apprendre à associer les entrées aux sorties

Avec une bonne généralisation, i.e. si hors de l'ensemble d'apprentissage mais généré par le même phénomène ou un phénomène proche

Utilisation : classification, regression, ordonnancement

2015/01/29Apprentissage Automatique - P. Gallinari20

sept

Apprentissage non supervisé Ensemble d'apprentissage

Uniquement des données d’entrée , … , , pas de sortie désirée associée

But Extraire des régularités des données

Similarités, relations entre données, facteurs sous jacent à la génération des données

Utilisation Estimation de densité, clustering, découverte de facteurs latents, …

2015/01/29Apprentissage Automatique - P. Gallinari21

Apprentissage semi supervisé Ensemble d’apprentissage

étiquetés – faible quantité , , … , , non étiquetés – grande quantité , … ,

But Extraire l’information des exemples non étiquetés, utile pour l’étiquetage Apprendre conjointement à partir des deux ensembles d’exemples

Utilisation grandes masses de données où l’étiquetage est possible mais coûteux,

classification et calcul de scores associés aux noeuds

Apprentissage Automatique - P. Gallinari22 2015/01/29

Apprentissage par Renforcement Ensemble d'apprentissage

Couples (entrée, sortie désirée qualitative) , , … , , Les xi peuvent être des séquences (temporal credit assignment), les di sont des réponses qualitatives

(e.g. 0,1), déterministes ou stochastiques.

Paradigme Système qui apprend à partir de l’exploration de son univers, à partir de récompense/ punitions On parle de paradigme exploration/ exploitation

Utilisation commande, décision séquentielle, robotique, jeux à 2 joueurs, jeux collectifs, programmation dynamique,

applications web ou sociales, ... Exemple backgammon (TD Gammon Thesauro 1992)

Entrainé sur 1.5 M partie Joue contre lui même

Apprentissage Automatique - P. Gallinari23

Algorithmes d'apprentissage numérique

Apprentissage Statistique - P. Gallinari24

Il existe un grand nombre d’algorithmes et de familles d’algorithmes pour les différents problèmes génériques abordés en apprentissage

Il existe de nombreuses implémentations sous forme de programmes dédiés ou de logiciels plus généralistes

Quelques exemples d’algorithmes populaires Données statiques

Supervisé Réseaux de neurones/ Deep learning Arbres décision / régression, random forest Fonctions noyau, machines à vecteurs supports Nombreux modèles pour l’estimation de densité paramétrique, non paramétrique

Non supervisé Modèles à variables latentes

Modèles latents probabilistes Factorisation matricielle Deep Learning

Données structurées Séquences

Réseaux de neurones récurrents, modèles Markoviens, noyaux Arbres et graphes

Modèles relationnels probabilistes, réseaux de neurones, noyaux

Des environnements de programmation pour l’apprentissage statistique

Apprentissage Statistique - P. Gallinari25

Prototypes universitaires Weka – Java based

Systèmes industriels Scikit-learn Python Mlib – Apache Spark Apache Mahout RapidMiner : environnement pour data mining, Machine learning, predictive analytics, text … R langage et environnement pour statistiques + visualisation KNIME environnement pour data mining, predictive analytics … Graphlab : environnement pour systèmes distribués MS Azure Machine Learning IBM Watson analytics …..

Plus de nombreux systèmes dédiés à une famille d’algorithmes Pour les réseaux de neurones

Torch (Facebook) Tensorflow (Google) Theano (Univ. Montreal) Caffe (Univ. Berkeley) …

Exemple introductif : Perceptron

Apprentissage Statistique - P. Gallinari26

Un exemple : Perceptron (1960 Rosenblatt)

Apprentissage Statistique - P. Gallinari27

(image from Perceptrons, Minsky and Papert 1969)

Le perceptron est utilisé pour la discrimination

La cellule de décision calcule une fonction à seuil :

∑ ∑ avec 1 Classe 1 : ∶ 1 Classe 2 : ∶ 1

Cellules d’association Cellule de décision

L'algorithme du perceptron (2 classes)

Apprentissage Statistique - P. Gallinari28

C'est un algorithme à correction d'erreur si est constant : règle à incrément fixe si est fonction du temps : règle à incrément variable

Donnéesbase d’apprentissage , , 1. . , ∈ , ∈ 1,1

Outputclassifieur ∈ , décision ∑

Initialiser w (0)Répeter (t)

choisir un exemple, ,Si . 0alors 1

Jusqu'à convergence

Fonction discriminante linéaire

Apprentissage Statistique - P. Gallinari29

Surface de décision: hyperplan d’équation 0 Quelques propriétés

est le vecteur normal de l'hyperplan, il défini son orientation distance de x à H : / 0 : H passe par l'origine

. ∑ avec 1

Géométrie de la discrimination linéaire

Apprentissage Statistique - P. Gallinari30

W

F(x) < 0

F(x) > 0wxF )( F(x) = 0

Le perceptron effectue une descente de gradient

Apprentissage Statistique - P. Gallinari31

Fonction de coût ∑ . ., é On veut minimiser

gradient , … , avec ∑ ., é

Règle d’apprentissage Règle d’apprentissage du perceptron : algorithme adaptatif pour optimiser cette fonction de coût

Demo http://lcn.epfl.ch/tutorial/english/

Cas multi-classes

Apprentissage Statistique - P. Gallinari32

Approche générale : one vs all p classes = p " problèmes 2 classes " : Ci contre le reste

construire p fonctions discriminantes Fi(x), i = 1 ... p

règle de décision: x Ci si Fi(x) > Fj(x) pour ji

crée une partition de l'espace d'entrée

chaque classe est un polygone avec au plus p -1 faces.

Régions convexes : limitation des classifieurs linéaires

Théorème de convergence du perceptron (Novikov 1962)

Apprentissage Statistique - P. Gallinari33

Si ∃ :∀ , R

les données peuvent être séparées avec une marge , i.e. supmin .

l'ensemble d'apprentissage est présenté au perceptron un nombre suffisant de fois

Alors après au plus / corrections, l'algorithme converge

Borne sur l'erreur de généralisation (Aizerman et al. 1964)

Apprentissage Statistique - P. Gallinari34

Si les données sont séparables elles sont en nombre infini règle arrêt : après la kème correction, les

données présentées sont reconnues correctement

alors le perceptron converge en l / /

étapes avec une probabilité 1 , l'erreur de test est <

Overtraining / généralisation en regression

Apprentissage Statistique - P. Gallinari35

Exemple (Bishop 06)

Necessité de controler lors de l’apprentissage la complexité des modèles Techniques de régularisation

Données dans la pratique de l’apprentissage

Apprentissage Statistique - P. Gallinari36

Distinguer les ensembles d’apprentissage

Mettre au point le modèle

de test Evaluer les performances du modèle appris

de validation Apprentissage de méta-paramètres

Remarque On fera en général l’hypothèse que toutes les données sont générées suivant une

même loi

Formalisation du problème de l'apprentissage

Formalisme probabiliste

Apprentissage Statistique - P. Gallinari38

Données vecteurs aléatoires générés suivant une densité

Machine d’apprentissage avec les paramètres du modèle à valeur dans un espace réel

Coût pour la machine et l’exemple

Risque théorique

Solution optimale ∗

Apprentissage à partir d'exemples

Apprentissage Statistique - P. Gallinari39

Données ..

Risque empirique ∑

Principe inductif Exemple : Minimisation du risque empirique

La fonction ∗ qui minimise le risque théorique est approximée par qui optimise le risque empirique

Est-ce un bon principe ?

Propriété de généralisation ?

Problèmes d'apprentissage : exemples

Apprentissage Statistique - P. Gallinari40

Discrimination , , ∈ 0,1 ensemble des fonctions à seuil R : probabilité de mauvaise classification C : fréquence des erreurs

Régression , , ∈R un ensemble de fonctions réelles R : espérance des erreurs quadratiques C : somme des erreurs quadratiques

Estimation de densité

ensemble de fonctions réelles R : espérance C : vraisemblance

0si 1sinon

Apprentissage supervisé

Préliminaires : gradient, regression, regression logistiqueModèles discriminants

- Réseaux de neurones et Deep Learning- Machines à noyaux et SVM

Apprentissage Statistique - P. Gallinari42

L’apprentissage supervisé recouvre un ensemble de problèmes génériques Regression Classification Ranking …

Dans le première partie du cours on examine des problèmes de régression et de classification

OptimisationAlgorithmes de gradient

Apprentissage Statistique - P. Gallinari43

Objectif Optimiser une fonction de coût C(w) dépendant de paramètres w Principe :

Initialiser w Itérer jusqu’à convergence

1 la direction de descente , le pas de gradient sont déterminés à partir d'informations

locales sur la fonction de coût , i.e. approximations au 1er ou 2nd ordre.

OptimisationAlgorithmes de gradient -Exemples

Apprentissage Statistique - P. Gallinari44

Plus grande pente (batch):

Stochastic Gradient Descent

Souvent utilisé dans les réseaux de neurones

Ensemble d’apprentissage :, , … , ,

Coût : ∑Direction de descente : t)

Initialiser Itérer

1 t)Critère d’arrêtAvec

Ensemble d’apprentissage :, , … , ,

Coût : est le coût sur l’exemple Direction de descente : x(t))

InitialiserIterer

choisir un exemple1

Critère d’arrêt

Autres procédures de minimisation basées sur le gradient

Apprentissage Statistique - P. Gallinari45

Approximation quadratique locale de la fonction à optimiser (on approxime C par une parabole)

Avec H le Hessien de C(.) :

En différentiant par rapport à w

On cherche le minimum de C

Méthode de Newton

Trop couteux en pratique ( pour l’inverse, + dérivées partielles)

)()(21)()()()( 00000 wwHwwwCwwwCwC TT

0)( wC

)( 01

0 wCHww

)()()( 00 wwHwCwC

Apprentissage Statistique - P. Gallinari46

En pratique on utilise des gradients du 1er ordre ou des approximations du 2nd ordre

Exemple approximation du 2nd ordre : Méthodes de quasi-Newton : approximation de itérativement.

Forme générale :

H' : approximation de sans calculer les dérivées secondes

))(),(,,,'('')('

001

00

wCwCwwHFHHwCHww

ttt

t

Regression

Apprentissage Statistique - P. Gallinari47

Regression simple Objectif : prédire une fonction réelle Ensemble d’apprentissage

, , … , , ∈ , ∈ : regression simple

Modèle linéaire . ∑ avec 1

Fonction de coût Moindres carrés

∑ .

Gradient de la plus grande pente

, , …,

∑ . ∑ .

∑ .

Regression

Apprentissage Statistique - P. Gallinari48

Géométrie des moindres carrés

5

10

15

20

50

100

150

200

0 2 4 6 8 10 12 14 16 18 20

Regression multi-variée

Apprentissage Statistique - P. Gallinari49

Le modèle s’étend directement au cas où ∈ On a alors p regressions linéaires indépendantes L’algorithme est identique

Interprétation probabiliste

Apprentissage Statistique - P. Gallinari50

Modèle statistique de la regression . , où est une v.a. qui modélise l’erreur

On suppose que est une v.a. i.i.d. gaussienne ~ 0, , exp

La distribution a posteriori de d est alors | ; exp .

Vraisemblance ∏ | ;

C’est une fonction de w, calculée pour un ensemble de données, ici les données d’apprentissage

Principe du maximum de vraisemblance Choisir le paramètre qui maximise ou toute fonction croissante de

on va maximiser la log vraisemblance qui donne des calculs plus adaptés en pratique

∑ . On retrouve le critère des moindres carrés

Sous les hyp. précédentes, on a une interprétation probabiliste de la régression

Regression logistique

Apprentissage Statistique - P. Gallinari51

La regression linéaire peut être utilisée pour des problèmes de regression ou de classification

Un modèle mieux adapté pour la classification (avec des sorties binaires) est celui de la régression logistique

..

Fonction logistique

La fonction

est appelée fonction logistique ou sigmoide

hint 1

0,2

0,4

0,6

0,8

1

-5 -4 -3 -2 -1 0 1 2 3 4 5

sigmoid

Regression logistiqueInterprétation probabiliste

Apprentissage Statistique - P. Gallinari52

Comme ∈ 0,1 , on va faire l’hypothèse d’une distribution conditionnellede Bernouilli

1 ; et 0 ; 1 En plus compact

; 1 avec ∈ 0,1

Vraisemblance

∏ 1

Log-vraisemblance ∑ 1 log 1

qui est une entropie croisée

Gradient de la plus grande pente

∑

∑ Algorithme

∑

Regression logistique multivariée

Apprentissage Statistique - P. Gallinari53

On suppose que l’on a un problème de classification à plusieurs classes 1…p On les code suivant la fonction indicatrice suivante

Classe 1: 1,0, … , 0 Classe 2 : 0,1, … , 0 … Classe 1: 0,0, … , 1 On a un vecteur de sorties à p dimensions – codage “one out of p”

La fonction est une fonction vectorielle à p dimensions La composante i sera une fonction softmax

.

∑ .

Attention : ici ∈ est un vecteur

Le modèle probabiliste sous jacent est un modèle multinomial pour les densitésconditionnelles

; = .∑ .

Algorithme d’apprentissage Comme précédement on peut utiliser un algorithme de gradient pour maximiser la log vraisemblance Si le nombre de classes est très grand l’estimation du softmax est couteuse

Différentes techniques pour limiter la complexité du calcul (vu plus tard)

Apprentissage supervisé

Réseaux de neurones

Réseaux de neurones

2015/01/29Apprentissage Automatique - P. Gallinari55

Les RN servent de métaphore pour réaliser des systèmes d’apprentissage

Ils constituent un paradigme important en apprentissage statistique Le cerveau humain est constitué par un réseau dense (10 ) d’unités simples, les

neurones. Chaque neurone est connecté en moyenne à 10 neurones. Concepts importants

Représentation et contrôle sont distribué

Apprentissage à partir d’exemples ou d’essais/ erreurs

Apports pluridisciplinaires

Apprentissage Statistique - P. Gallinari56

Domaines Neurosciences Sciences cognitive (AI, psychologie, linguistique) Informatique Maths Physique

Buts Modélisation (neurophysiologie, biologie.....) Modèle de calcul (applications, computational theory, apprentissage...)

Fondements biologiques

Apprentissage Statistique - P. Gallinari57

Le neurone Soma Arbre des dendrites Axone Flot d'information

axone : impulsions électriques

dendrites : transmission chimique avec le soma via synapses

Synapses contact : émission - réception Poids synaptique = modulation de l'information transmise vers le soma. Comportement du neurone + mémoire ?

Formal Model of the NeuronMcCulloch – Pitts 1943

2016/06/17From Neural Networks to Deep Learning58

x2

x1

xn

wn

w2

wn

w0

-1

A synchronous assembly of neurons is capable of universalcomputations (aka equivalent to a Turing machine)

1 0

Historique rapide des réseaux de neurones

Apprentissage Statistique - P. Gallinari59

43 Mc Culloch & Pitts : neurone formel "A logical calculus of the ideas immanent in nervous activities"

40 – 45 Wiener (USA) Kolmogorov (URSS) Türing (UK) Théorie de l'estimation et de la prédiction (contrôle batteries anti-aeriennes)

Boucle de rétro-action

48 – 50 Von Neuman : réseaux d'automates 49 Hebb rule (1949) (Neuropsychologist D. Hebb) - rephrased

If two neurons on either side of a synapse are activated simultaneously (synchronously), the the strength of the synapse is increased

Most famous rule of self organization

Apprentissage Statistique - P. Gallinari60

55 – 60 Rosenblatt : Perceptron

Widrow - Hoff : Adaline

70 – 80 Mémoires associatives, ART, SOM ... 90 – 95

Réseaux non linéaires Réseaux de Hopfield, Machine de Boltzmann Perceptron multicouches ...

2006 - .. Deep neural networks, restricted Boltzmann machines,… Representation learning

Le neurone formel

Apprentissage Statistique - P. Gallinari61

C'est un automate caractérisé par l’espace des signaux d'entrée , … , ∈ une fonction de transition

Fonctions de transition Historiquement, fonction à seuil (Neurone formel de McCulloch et Pitts)

En pratique on utilise des fonctions différentiables Soit ∑ , on considère des fonctions de la forme Fonction identité g

Fonction sigmoïde g

Fonction tangente hyperbolique g

On verra par la suite d’autres fonctions de transition

x2

x1

xn

y = F(x)

Adaline

Apprentissage Statistique - P. Gallinari62

Modèle Neurone linéaire Risque empirique : moindres carrés

∑ .

On suppose que l’on est dans un contexte « en ligne » Les données arrivent et sont traitées séquentiellement Les paramètres sont modifiés pour chaque donnée Algorithme d’apprentissage : gradient stochastique (Robbins-Monro, 1951),

popularisé pour les réseaux de neurones par (Widrow et Hoff, 1959)

Adaline : règle de Widrow-Hoff

Apprentissage Statistique - P. Gallinari63

x(t) est l'exemple présenté à l'instant t, le gradient est calculé sur le coût local A comparer avec le gradient classique qui calcule le gradient sur le risque empirique

initialiser 0Iterer

choisir un exemple 1 .

Critère d’arrêt

Plus grande penteinitialiser 0Iterer

1 ∑ .Critère d’arrêt

Apprentissage Statistique - P. Gallinari64

Apprentissage hors ligne vs apprentissage adaptatif

ck erreur sur la forme k de l'ensemble d'apprentissage

Gradient sur C Gradient adaptatif sur c

Q qk

W W

k

kcN

C 1

Adaline (Widrow - Hoff 1959)

Context Adaptive filtering, equalization, ect.

« Least Mean Square » algorithm Loss function : euclidean distance (target – computed output) Algorithm: stochastic gradient (Robbins – Monro (1951))

Workhorse algorithm of adaptive signal processing Simple, robust

2016/06/17From Neural Networks to Deep Learning65

Adaline example Adaptive noise cancelling

2016/06/17From Neural Networks to Deep Learning66

Widrow-Science in Action - YouTu

Optimisation dans les RNAlgorithmes de gradient

Apprentissage Statistique - P. Gallinari67

Les algorithmes d’optimisation pour les réseaux de neurones utilisent souvent ces techniques simples de gradient stochastique

Raisons Historique Complexité et taille de données Ces méthodes sont devenues populaires également pour de nombreux autres

modèles (complexité) Ils exploitent bien la redondance présente dans les données

Bien adaptés aux grandes dimensions

En pratique utilisation d’algorithmes « mini-batch » À chaque itération on considère un petit sous ensemble des données

Perceptron Multicouches

Apprentissage Statistique - P. Gallinari68

Réseau avec : des couches externes: entrée et sortie des couches internes dites cachées Les cellules sur les couches internes et la couche de sortie sont des fonctions

sigmoïdes ou tangente hyperbolique.

y

x

Input

Output

hidden layers

d

Perceptron Multicouches

Apprentissage Statistique - P. Gallinari69

Les exemples sont présentés séquentiellement Inférence : passe avant

Pour chaque exemple on calcule la sortie

Apprentissage : passe arrière On calcule l’erreur entre sortie désirée et sortie calculée. On propage cette erreur pour calculer le gradient des poids du réseau

Apprentissage Statistique - P. Gallinari70

Notations vecteur activation de la couche i

activation du neurone j de la couche i

matrice de poids de la couche i à la couche i+1

poids de la cellule k sur la couche i à la cellule j sur la couche i+1 vecteur de sortie

1 1

Inférence : passe avant

Apprentissage Statistique - P. Gallinari71

Pour un exemple x On calcule en parallèle les activités de la couche de neurones 1

puis )

Avec ,

On utilise les sorties de la couche 1 comme entrées de la couche 2 et on calcule en parallèle les activités de la couche 2

puis )

1 1

Apprentissage : passe arrière

Apprentissage Statistique - P. Gallinari72

On décrit l’algorithme dans le cas d’une fonction de coût moindre carrés

PMC à 1 couches ce cellules numérotées 0 (couche entrée), …, (couche sortie), couches de poids numérotées , … , On selectionne un exemple , , ∈ , d ∈ On calcule la sortie , ∈

Calculer la différence , … , Rétropropager cette erreur de la couche de poids de sortie vers la couche de

poids d’entrée :

∆ mise à jour des poids par sgd

∆ gradient pour

C’est cette quantité « » que l’on va rétropropager

′ si i est une cellule de sortie

′ ∑ si i n’est pas une cellule de sortie

Apprentissage Statistique - P. Gallinari73

Remarques Comme pour la passe avant, on modifie tous les poids d’une couche en parallèle C’est une implémentation particulière de l’algorithme du gradient stochastique

qui évite de dupliquer les calculs Elle peut être adaptée à toute fonction différentiable Fonctions de coût

Pour des tâches de regression : LMSE

Pour des tâches de classification, différentes fonctions employées Entropie croisée Hinge, logistique (cf slide suivant)

Fonctions de coût Différentes fonctions de coût sont

utilisées, suivant les problèmes, oules modèles

Mean Square Error Pour la regression

Mais souvent utilisé enclassification également

Classification, Hinge, logistic losses Classification loss

Number of classification errors Exemples

∈ , ∈ 1,1 Hinge, logistic losses sont ici des

approximations de l’erreur de classification

Apprentissage Statistique - P. Gallinari74

Figure from Bishop 2006

En abscisse : . (marge)

, | |, 1 . max 0,1 .

, ln 1 exp .

Contrôle de la complexité

Apprentissage Statistique - P. Gallinari75

En pratique, on n’optimise jamais le risque empirique seul On optimise le risque tout en controlant la complexité

cf partie théorique du cours

Nombreuses méthodes Régularisation (Hadamard …Tikhonov)

Théorie des problèmes mal posés

Minimisation du risque structurel (Vapnik) Estimateurs algébriques de l’erreur de généralisation (AIC, BIC, LOO, etc) Apprentissage bayesien

Fournit une interprétation statistique de la régularisation

Le terme de régularisation apparait comme un a priori sur les paramètres du modèle

Méthodes d’ensembles Boosting, bagging, etc

….

Regularisation

Apprentissage Statistique - P. Gallinari76

Hadamard Un problème est bien posé si

Il existe une solution Elle est unique La solution est stable

Exemple de problème mal posé (Goutte 1997)

Tikhonov Propose des méthodes pour transformer un problème mal posé en problème

bien posé

Régularisation

Apprentissage Statistique - P. Gallinari77

Principe: Contrôler la variance de la solution en contraignant la fonctionnelle F Optimiser C = C1 + C2(F) C est un compromis entre

C1 : mesure du but poursuivi e.g. MSE, Entropie, ... C2 : contraintes sur la forme de la solution (e.g. distribution des poids)

: poids de la contrainte Moindres carrés régularisés

On reprend le cas de la regression linéaire simple

∑ . ∑ 2 régularisation , 1 régularisation connu aussi sous le nom de « Lasso »

Fig. from Bishop 2006

Apprentissage Statistique - P. Gallinari78

Résoudre

∑ . ∑ , 0

Revient à résoudre le problème d’optimisation sous contrainte ∑ .

Sous contrainte ∑ s pour une certaine valeur de s

Effet de cette contrainte

Fig. from Bishop 2006

Apprentissage Statistique - P. Gallinari79

Penalisation Coût

∑

Gradient

Update 1 La pénalisation est proportionnelle à

Penalisation Coût

∑

Gradient

est le signe de appliqué à chaque composante de Update

La pénalisation est constante avec un signe

Régularisation empirique pour les réseaux de neurones

Apprentissage Statistique - P. Gallinari80

∑ biaise la solution en diminuant les poids inutiles

∑ 2 groupes de poids autour de c

∑ 1 ∑ cellules cachées h + poids

Utiliser des contraintes différentes suivant le rôle des poids Problème : détermination des "hyper-paramètres"

Autres idées pour le problème de la généralisation dans les réseaux de neurones

Apprentissage Statistique - P. Gallinari81

Arrêt de l'apprentissage Elagage : tuer les paramètres inutiles dans un réseau. Différentes mesures d'utilité

ont été proposées Bruiter les entrées (Matsuoka 1992 ; Grandvallet et Canu 1994 ; Bishop 1994) Réseaux à convolution

Exemple (Cibas et al, 95, 96)

Apprentissage Statistique - P. Gallinari82

Discriminer entre trois classes de "formes d’onde". Les trois formes de base pour la génération des formes d'onde :

3 classes C1, C2, C3 engendrées respectivement par :

u v. a. de densité uniforme sur [0,1], ~ N(0,I), Classes équiprobables Apprentissage = 10 ensembles disjoints, chacun de 300 exemples Test = 5000 exemples Algorithme : Rétropropagation

1 5 9 13 17 21

6 6 6

h 3

h 2h 1

26)(1

10)(1

2)(1

32

31

21

huuhx

huuhx

huuhx

Evolution des performances pendant l'apprentissage

Apprentissage Statistique - P. Gallinari83

Sans régularisation

Figure 1 a (left), b (right): evolution of the performances (mean square error) duringtraining for MLPs with a varying number of hidden units. (a) corresponds to a stochastic gradient descent and (b) to a conjugate gardient. Each curve corresponds to a two weight layer MLP, the number on the curve gives the size of the hiddenlayer.

5

10

15

35

60

5

10

15

3560

Evolution des performances pendant l'apprentissage

Apprentissage Statistique - P. Gallinari84

Avec régularisation

Comparaison de l’erreur en apprentissage (a) et en généralisation (b) pour les réseaux h=15 et h=60 en minimisant le coût ordinaire sans terme de régularisation (...-ord) et le coût avec la régularisation: avec détermination des paramètres à priori (...-WD) et en les estimant pendant l’apprentissage (...-estim)

h=60-WD

h=15-estim

h=60-estimh=15-ord

h=60-ord

h=60-ord

h=15-ord

h=15-estimh=60-estimh=60-WD

Fonctions à Base Radiale

Apprentissage Statistique - P. Gallinari85

Réseau à deux couches Notations

wi. = poids vers la cellule i, xi sortie de la cellule i, x entrée

Risque : moindres carrés

Couche de sortie

g = IdCouche intermédiaire

y

x

j jj xwwA 0

2wxA

2)( A

eAg

2

.0)( jj ijiii wxgwwxGy

La fonction sigmoïde

Apprentissage Statistique - P. Gallinari86

Distribution de la famille exponentielle :

q, f : paramètres de la loi, ( q paramètre de position , f paramètre de dispersion). Ex. de distributions exponentielles : normale, gamma, binomiale, poisson,

hypergéométrique ... Hypothèse : la distribution des données conditionnellement à chaque classe est

de la famille exponentielle, avec un paramètre de dispersion identique pour toutes les classes i.e. :

Alors

)),()())/(((),,( xcabxxp T exp

)),()())/((()/( xcabxCxp iT

ii exp

)(1

1)/(bxwi T

exCP

Capacités d'approximation des PMC

Apprentissage Statistique - P. Gallinari87

Résultats basés sur les théorèmes d'approximation de l'analyse fonctionnelle. (Cybenko (1989))

Théorème 1 (regression): Soit f une fonction saturante continue, alors l'espace des fonctions de la forme ∑ . . est dense dans l’espace des fonctions continues sur le cube unité C(I). i.e. ∀ ∈ ∀ 0, ∃ ∶ sur I

Théorème 2 (classification): Soit f une fonction saturante continue. Soit F une fonction de décision définissant une partition de I. Alors ∀ 0, il existe une fonction de la forme ∑ . . et un ensemble ⊂ tel que 1 (D)

sur D .

(Hornik et al., 1989) Théorème 3 : Pour toute fonction saturante croissante f, et toute mesure de

probabilité m sur , l'espace des fonctions de la forme ∑ . .est uniformément dense sur les compacts de - espace des fonctions continues sur

Apprentissage Statistique - P. Gallinari88

Fonctions radiales (Park & Sandberg, 1993) Théorème 4 : Si f, fonction réelle définie sur Rn est intégrable, alors l'espace des

fonctions de la forme :

est dense dans L1(Rn) ssi .

Nj

j

jj

wxfvxg 1

. )(.)(

nR

dxxf 0)(

Apprentissage Statistique - P. Gallinari89

Résultats basés sur le théorème de Kolmogorov Théorème sur la représentation (exacte) des fonctions réelles de Kolmogorov

Toute fonction h de C(I) peut s'écrire sous la forme

où les fonctions g et f sont des fonctions continues d'une variable.

Théorème 6 (Kurkova 1992) Soit h dans C(I), n 2 et R+, alors quelquesoit m vérifiant

m = 2n + 1n/(m-n) + v < / ||h||h(1/m) < v(m - n)/(2m - 3n)v > 0

h peut être approximée à une précision par un perceptron possédant deux couches cachées de fonctions saturantes et dont les sorties sont linéaires. La première couche comprend n.m(m+1) unités et la seconde m2(m+1)n. Les poids sont universels sauf ceux de la dernière couche, pour toutes les fonctions f vérifiant :

f(d)= sup{|f(x1, ..., xn) - f(y1, ..., yn)|, x, y I et |xp - yp| < p}.

))((),...,( 121 11

nq

np ppqqn xfgxxh

Interprétation probabiliste des sorties

Apprentissage Statistique - P. Gallinari90

Risque théorique ,

Le minimum de , Min , est obtenu pour ∗ | Le Risque théorique pour la famille de fonction se décompose de la

façon suivante :

,

, ,

Considérons Ce terme est indépendant du modèle choisi et dépend uniquement des caractéristiques

du problème (le bruit intrinsèque des données). Il représente l’erreur minimum que l’on peut attendre sur ces données ∗ | est bien la solution optimale au problème Min

Minimiser , est équivalent à minimiser ,

La solution optimale ∗ argmin , est la meilleure approximation au sens des moindres carrés de |

Interprétation probabiliste des sorties

Apprentissage Statistique - P. Gallinari91

Cas de la Classification On considère la classification multi-classes avec un codage des sorties

désirées «1vs all » i.e. d = (0,…, 0, 1, 0, …, 0) avec un 1 en ième position si la sortie désirée est la classe

classe i et 0 partout ailleurs

∗ 1. 0. 1 | i.e. ∗ est la meilleure approximation LMS de la fonction discriminante de

Bayes (solution optimale pour la classification avec coûts 0/1). de façon générale avec des sorties binaires

∗ 1

L’importance de la précision sur les sorties dépend de l'utilisation classification : la précision peut ne pas être importante estimation de probabilité conditionnelle : elle l’est

Décomposition biais-variance

Apprentissage Statistique - P. Gallinari92

Illustre la problématique du choix de modèle en mettant en évidence l’influence de la complexité du modèle On rappelle la décomposition de l’espérance du coût quadratique

, , ,

On note ∗ | la solution optimale à la minimisation de ce risque

En pratique on ne dispose pas d’une infinité de données permettant d’obtenir un bon estimateur de L’estimateur obtenu dépendra de l’ensemble d’apprentissage

L’incertitude sur l’estimateur liée au choix de l’ensemble d’apprentissage peut être mesurée comme suit : On tire une série d’ensembles d’apprentissage de taille : , , … apprend , sur chacun de ces ensembles On mesure la moyenne des coût empiriques sur chacun de ces ensembles

Examinons l’intuition derrière cette procédure

Décomposition biais-variance

Apprentissage Statistique - P. Gallinari93

On considère l’erreur quadratique ; ∗ pour une donnée et pour la solution ; obtenue avec un ensemble d’apprentissage On note ; l’espérance sur la distribution de de ces solutions

; ∗ se décompose en

; ∗ ; ; ; ∗

; ∗ ; ; ; ∗

2 ; ; ; ∗

L’espérance de ; ∗ par rapport à se décompose en

; ∗

; ∗ ; ; Intuition

Choisir le bon modèle nécessite un compromis flexibilité – simplicité (cf régularisation)

Modèle flexible : faible biais – forte variance

Modèle simple : fort biais – faible variance

The Bias-Variance Decomposition (Bishop PRML)

Example: 100 data sets from the sinusoidal, varying the degree of regularization Model: gaussian basis function, Learning set size = 25, is the regularization parameter

High values of correspond to simple models, low values to more complex models

Left 20 of the 100 models shown

Right : average of the 100 models (red), true sinusoid (green)

Figure illustrates high bias and low variance ( 13

The Bias-Variance Decomposition (Bishop PRML)

Example: 100 data sets from the sinusoidal, varying the degree of regularization Same setting as before

Figure illustrates low bias and high variance ( 0.09

Remark The mean of several complex models behaves well here (reduced variance)

leads to ensemble methods

The Bias-Variance Decomposition (Bishop PRML) From these plots, we note that an over-regularized model (large )

will have a high bias, while an under-regularized model (small ) will have a high variance.

Deep Neural Networksand Representation Learning

Apprentissage Statistique - P. Gallinari97

Brief history

Apprentissage Statistique - P. Gallinari98

Deep learning was popularized by Hinton 05 with a model called Restricted Boltzmann Machines

Idea Train several successive layers in an unsupervised way, stack them, stick a classifier at

the last layer and do back propagation

Developed by different actors Hinton 06, Bengio 06, LeCun 06, Ng 07 And many others now

Success story Very active domain, technology adopted by big actors (Google, Facebook, Msoft ..) Success in many different academic benchmarks for a large series of problems

Image / scene labeling

Speech recognition

Natural language processing

Translation

etc

Motivations

Apprentissage Statistique - P. Gallinari99

Learning representations Handcrafted versus learned representation

Very often complex to define what are good representations

General methods that can be used for different application domains

Multimodal data

Multi-task learning

Learning the latent factors behind the data generation Unsupervised feature learning

Useful for learning data/ signal rerpesentations

Several families of techniques Matrix factorization, dictionary learning, compressed sensing Latent probabilistic models (Deep) Neural networks are the focus of this course

Complement to the NN course

Apprentissage Statistique - P. Gallinari100

More units

Apprentissage Statistique - P. Gallinari101

In addition to the logistic or tanh units, already seen in the NN course, other forms may be used – some of the popular forms are: Rectifier linear units

max 0, . Rectifier units allow to draw activations to 0 (used for sparse representations)

Maxout max .

Generalizes the rectifier unit There are multiple weight vectors for each unit

Softmax Used for classification with a 1 out of p coding (p classes)

Ensures that the sum of predicted outputs sums to 1

∑

Mean square error and maximum likelihood

Apprentissage Statistique - P. Gallinari102

Remember the following result concerning minimization of MSE

Mean square loss

Min of R is obtained for ∗ | MSE for a family of function

C ,

C , ,

∗ | is the optimal solution to Minw C w* / R(w*) = Minw C minimizes simultaneously:

, LMSE

, best LMS approximation of |

Mean Square error maximum likelihood

Apprentissage Statistique - P. Gallinari103

Statistical model of the regression , where is a random variable modeling the error (variability)

Let be a i.i.d. Gaussian random variable

~ 0, , exp

The posterior distribution of d is | ; exp

Likelihood ∏ | ;

Maximum likelihood Choose the parameter maximizing or alternatively any increasing function of

such as

log likelihood ∑

Under normal hypothesis on | ; , maximizing the likelihood is equivalentto minimizing the MSE loss

Cross-entropy loss – 2 classes

Apprentissage Statistique - P. Gallinari104

2 classes classification problem Target is 1 ∈ , 0 ∈ We consider a discriminant function

Here we take, F

with . , i.e. logistic function

The posterior probability of a class is a Bernoulli distribution and can be written 1

target output, computed output

Likelihood

∏ 1 Loss: negative log-likelihood

∑ 1 log 1 ∑ log for the Bernoulli distribution y |

This is the cross entropy between the target and computed posterior class distributions The minimum is obtained for ∀ 1. . This cross entropy loss could be used also when the targets are not binary but in the range 0,1 It can be shown that the optimal solution to the minimization of L is 1| this

means that (with the logistic function F) the learned will approximate this posterior probability

Cross-entropy loss – multiple classes

Apprentissage Statistique - P. Gallinari105

p mutually exclusive classes One considers a 1 out of p target coding scheme

i.e. the target has a 1 at the position corresponding to the class and 0 elsewhere e.g. 0,1,0, … , 0 if ∈ 2

∏

log ∑ only 1 term is non 0 in this sum

Negative log likelihood ∑ ∑

Which is equivalent to ∑ ∗ with ∗ the output corresponding to ∗=1

Minimum when ∀ 1… Activation function: softmax

The outputs must be in 0,1 and sum to 1

∑ with . ,

Again this for is also suitable for targets in 0,1 that sum to unity This is called the multinoulli distribution

can be interpreted as the posterior probability of class k

Apprentissage Statistique - P. Gallinari106

More generally, a probabilistic interpretation of NNs (and otherparametric models) can be obtaind by considering for the lossfunction a negative log-likelihood , d log p d If d is a continuous variable and we make the hypothesis that it is conditionnally

gaussian with mean , we get the MSE loss If d is binary and we make the hypothesis that it is conditionnally Bernoulli with

probability 1| we get the cross entropy loss

For multiple outputs One has to specify the form of the joint distribution of the output variables

conditionally on e.g. conditional independence

, … , ∏ |

Auto-encoders

Apprentissage Statistique - P. Gallinari107

Auto-encoders

Apprentissage Statistique - P. Gallinari108

This is a neural network (MLP) trained to reproduce the inputs at the outputs Early attempts date back to the 80s with the auto-associative memories (Kohonen) Renewed interest since 2006 for learning representations and for deep learning

Basic scheme

Neurons in the hidden and output layers could be of any type In the following one will assume hat units are sigmoid (but any differentiable function could be

used) Note that when using saturating functions like sigmoids, the values shall be coded in a fixed

interval [0, 1] for sigmoids Otherwise use linear ouput units

encoder f

decoder gcode h

input

output

Auto-Encoders - Training

Apprentissage Statistique - P. Gallinari109

Training set , … , this is unsupervised learning

The transition function of the AE is ∘ is called the encoder, is the decoder, is the code of

Loss function different functions can be used such as Mean Square Error or cross Entropy for example

Algorithm Auto-Encoders can be trained with back propagation, using the s both as inputs and outputs The auto-encoder will try to reproduce the input, i.e. to learn the identity function

In order to avoid this trivial solution, one will impose constraints on the hidden layer Undercomplete representations

One possible constriant is to limit the number of hidden units The A-E will learn a compressed representation of the data by exploiting the correlation among the features, this is

called undercomplete representation rq: if all units are linear, AE trained with MSE performs a transformation similar to PCA, i.e. it will learn the

projection that maximizes the variance of the data (without the orthogonal property, of PCA but this can be easilysolved

Overcomplete representations More recently, other constraints have been used with a hidden layer that may be even larger than the input layer When the representation is larger than the input space, itis called overcomplete representation

Learning overcomplete representations

Apprentissage Statistique - P. Gallinari110

In order to learn overcomplete representations different constraints have been proposed either on the form of the learned F function or on the hidden units Sparse auto-encoders

A sparse representation is a representation such that for a given , only a small number of the values in are non zero

Sparse representations have some desirable properties e.g. it allows the mapping F to respond differently to different regions in the input space,

i.e. hidden units specialize on some input regions (see manifold interpretation) This corresponds to learning local mappings

This is usually implemented through constraints operating on the hidden units

Contractive auto-encoders

this encourages the derivative to be close to 0, so that h is not sensible to variations in x except in the directions where this is meaningful

Prior on the distribution of hidden units Under a probabilistic interpretation of the NN, priors can play the role of constraints

Dropout Specific heuristic effective for large NN

Sparsity for hidden units representation

Apprentissage Statistique - P. Gallinari111

Sparsity is often imposed using a regularization term in the loss function C = C1 + C2(F) With constraining the activation of towards 0

Different penalization terms may be used to enforce sparsity norm Kullback Leibler divergence penalty

C ∑ 1 log 1 The summation is over the hidden units the hidden units are assumed sigmoid (values in [0,1]) and is the activation of hidden unit i is the mean value of over the training examples s is a sparsity parameter, typically set at a low value e.g. 0.05 Kulback Leibler divergence between 2 discrete distributions P and Q is a dissimilarity

measure between these 2 distributions | ∑ log

| 1 log is KL divergence between 2 Bernoulli distributions of means s et h

Kullback Leibler divergence penalty forces the mean value of the hidden units to be close to sand thus to have a low mean value

Apprentissage Statistique - P. Gallinari112

Derivatives for back propagation Note that these sparsity terms are defined on the activations of the training data Computing them thus requires a forward pass through the training set in order

to compute the required average values Then these mean values can be used for computing the gradient of these loss

function

Visualizing hidden units activities

Apprentissage Statistique - P. Gallinari113

One way to understand what a hidden unit (or any unit) is doing isto look at its weight vector

We consider here unit activations based on dot products likesigmoid or tanh units

Example (image from A. Ng cite)

Auto-encoder trained on a small set of 10x10 images 100 hidden units Each square represents the (normalized) weights of a hidden unit Grey value indicates the weight value Each hidden unit has learned a feature detector

Here mostly image edges (gradient) detectors

at different angles and positions

Probabilistic interpretation of auto-encoders

Apprentissage Statistique - P. Gallinari114

The loss criteria can be given a probabilistic interpretation If we make the hypothesis of the existence of a conditional output

distribution,the training objective is log |

If the conditional distribution is gaussian we get MSE, if it is a Bernoulli, we get the cross entropy loss

For sparse auto-encoders A prior distribution on the hidden unit vector, corresponds to a regularization

term for the loss e.g. Laplace prior on corresponds to the regularization on the hidden units

activity

log ∑ log ∑ | | Note that all penalty terms do not need to have a prior interpretation (e.g. cross

entropy on h)

Combining auto-encoders with a classifier

Apprentissage Statistique - P. Gallinari115

The features learned can be used as inputs to any other system Instead of using the input features use Example for classification

1. train an autoencoder , … , → ,… ,

2. use the codes to train a classifier , , … , , Assuming here a 3 class problem

Both NN (encoder and classifier) can be trained separately using stochastic gradient descent

e.g. sigmoid units(logistic classifier)

Join training of the auto-encoder and the classifier

Apprentissage Statistique - P. Gallinari116

Fine tuning Separate training of each layer can be used as initialization Then stack the coding and classification layers one upon the other and fine tune

the new NN using back propagation as in a classical MLP

initialize

initialize

Deep auto-associators

Apprentissage Statistique - P. Gallinari117

Idea train successive layers of auto-associators in the hope of learning more complex

features of the inputs

Strategy (greedy layer wise training) Each auto-associator will be trained using the representation layer of a previous auto-

associator

The encoding layer of the different netwoks will then be stacked

After that fine tuning can be performed as before for a classification task

Why not learning all the layers at once Vanishing gradient

The gradients propagated backwards diminish rapidly in magnitude so that the first layers will not learn much

Non linear form of the loss function: many local minima

Deep architectures

Apprentissage Statistique - P. Gallinari118

autoassociators can be stacked Plus fine tuning using the last hidden layer if this is relevant for the task

Apprentissage Statistique - P. Gallinari119

Why using auto-association Unsupervised learning

Often easy to get very large quantities of unlabeled data

Allows the extraction of « meaningful » features

These features can be used as preprocessing for other learning machines (e.g. classification) and for other datasets (same type of data but with differentcharacteristics or another density distribution)

e.g extract meaningful image feature extractors on a large dataset that can be used for other image datasets

Supervised fine tuning Can be used with other datasets when labels are available for the latter

Today, there exists procedures for training deep NN architectures from scratch

CNN: Convolutional Neural Nets

Apprentissage Statistique - P. Gallinari120

Local connections

Apprentissage Statistique - P. Gallinari121

In many cases, data exhibit local properties, i.e. short term or spacedependencies between characteristics e.g. images, speech signal

Instead of computing global statistics via fully connected layers, one may use local connections This also allows the reduction of the number of parameters

Shared connections: convolutions

Apprentissage Statistique - P. Gallinari122

Local connections may be constrained to have the same weightvector This is called shared weights This is equivalent to convolve a unique weight vector with the input signal

Think of a local edge detector for images

This reduces even more the number of free parameters In the figure, colors indicate a weight value, here the 3 hidden units share the same

weight vector

Shared connections: convolutions

Apprentissage Statistique - P. Gallinari123

Several convolution filters can be learned simultaneously This corresponds to applying a set of local filters on the input signal

e.g edge detectors at different angles for an image Here colors indicate similar weight vectors

Pooling

Apprentissage Statistique - P. Gallinari124

The number of extracted features on the hidden layer can be verylarge if one uses several filters

In order to reduce this number, one may use pooling This consists in aggregating statistics for these features over a region of the signal Pooling operator : max, mean of the input units For an image or a spatial signal, pooling of features generated by the same

convolutional filter brings some invariance to small translations of the input signal

Convolutional features

Pooled feature (max or mean operator)

Convolutional nets

Apprentissage Statistique - P. Gallinari125

ConvNet architecture (Y. LeCun since 1988) Deployed e.g. at Bell Labs in 1989-90 Character recognition Convolution: non linear embedding in high dimension Pooling: average, max

Apprentissage Statistique - P. Gallinari126

In Convnet The first hidden layer consists in 64 different convolution kernels over the initial

input, resulting in 64 different mapping of the input The second hidden layer is a sub-sampling layer with 1 pooling tranformation is

applied to each matrix representation of the first hidden layer etc Last layer is a classification layer

Convolutional nets - visualization

Apprentissage Statistique - P. Gallinari127

Hand writing recognition (Y. LeCun Bell labs 1989)

Convolutional nets (Krizhevsky et al. 2012)

Apprentissage Statistique - P. Gallinari128

A landmark in object recognition Imagenet competition

Large ScaleVisual Recognition Challenge

1000 categories, 1.5 Million labeled training samples

Method: large convolutional net

650K neurons, 630M synapses, 60M parameters

Trained with backprop on GPU

Convolutional nets (Krizhevsky et al. 2012)

Apprentissage Statistique - P. Gallinari129

Details of learned weights

Labels True label under the image

Predicted label probability for

the 5 most probable labels

Lecun’s demohttps://youtu.be/ZJMtDRbqH40

Learning word vector representations(Mikolov et al. 2013a, 2013b)

Apprentissage Statistique - P. Gallinari130

Goal Learn language models

Learn robust vector representation of words that can be used in different Natural Language Processing or Information retrieval tasks

Learn word representations in phrase contexts

Learn using very large text corpora

Learn efficient, low complexity transformations

Successful and influential work gave rise to many developments and extensions

Learning word vector representations(Mikolov et al. 2013a, 2013b)

Apprentissage Statistique - P. Gallinari131

CBOW model Task

Predict the midle word of a sequence of words

Input and output word representations are learned jointly (random initialization)

The projection layer is linear followed by a sigmoid Word weight vectors in the projection layerare shared (all the weight vectors are the same) The output layer computes a hierarchical softmax

See later

This allows computing the output in

log instead of The context is typically 4 words before and 4 after

Learning word vector representations (Mikolov et al. 2013a, 2013b)

Apprentissage Statistique - P. Gallinari132

Skip Gram model Similar to the CBOW model, except that the context is predicted from the

central word instead of the reverse Input and outputs have different representations for the same word The output is computed using a hierarchical softmax classifier Output words are sampled less frequently if they arefar from the input word

i.e. if the context is C = 5 words each side, one selects ∈ 1;and use R words for the output context

Learning word vector representations (Mikolov et al. 2013a, 2013b)

Apprentissage Statistique - P. Gallinari133

Skip gram model Loss average log probability

∑ ∑ log |,

Where T is the number of words in the whole sequence used for training (roughlynumber of words in the corpus) and c is the context size

.

∑ .

Where is the learned representation of the w vector (the hidden layer), .is a dot product and V is the vocabulary size

Note that computing this softmax function is impractical since it is proportional to the size of the vocabulary

In practice, this can be reduced to a complexity proportional to log using a binary tree structure for computing the softmax Other alternatives are possible to compute the softmax in a reasonable time

cf negative sampling

Learning word vector representations(Mikolov et al. 2013a, 2013b)

Apprentissage Statistique - P. Gallinari134

Properties « analogical reasoning » This model learns analogical relationships between terms in the representation

space i.e. term pairs that share similar relations are share a similar geometric transformation

in the representation space Example for the relation « capital of » In the vector space

Paris – France + Italy = Rome At least approximatively i.e. Rome is the nearest vector toParis – France + Italy

Reasoning via more complex inferencesis however difficult:

Combination of transformationsto infer more complex facts is not effective

Learning word vector representations(Mikolov et al. 2013a, 2013b)

Apprentissage Statistique - P. Gallinari135

Paris – France + Italy = Rome

Image labeling at GoogleDeViSE: A Deep Visual-Semantic Embedding Model (Frome et al, NIPS 2013)

Apprentissage Statistique - P. Gallinari136

Goal Learn to label images

Approach Learn a language model from text

With the skip gram model of Mikolov et al. This models maps each word of a vocabulary onto a fixed vector space representation

This is called word representation Vectors are normalized to 1

Learn a visual model for image classification Similar to the convolutional model of Krizhevsky et al. 2012, trained with 1000 target classes The last layer of this network computes a representation of each image

This is called image representation Visual-semantic embedding

The language model is used to map the label terms onto the fixed word vector space representation A mapping is learned from the visual representation to the target words, word representation

This is a linear mapping with a ranking criterion This is called transformation mapping

Test time An image is

mapped onto its image representation This image representation is then mapped via the transformation mapping A nearest neighbor search produces a ranked list of potential labels

Image labeling at GoogleDeViSE: A Deep Visual-Semantic Embedding Model (Frome et al, NIPS 2013)

Apprentissage Statistique - P. Gallinari137

(image from Frome et al, NIPS 2013)

Image labeling at GoogleDeViSE: A Deep Visual-Semantic Embedding Model (Frome et al, NIPS 2013)

Apprentissage Statistique - P. Gallinari138

Loss function Ranking criterion ,

∑ max 0, Where

is the row vector of the text label representation (normalized to unit norm) is the matrix of the linear transformation is the column vector of the image representation is the row vector of another term representation (another text label also normalized to

unit norm) is a dot product (similarity) between and

This loss function was more efficient than an loss in the experiments

Training algorithm Stochastic gradient descent

Intersting properties Generalization to images with new labels (0 shot learning)

Image labeling at GoogleDeViSE: A Deep Visual-Semantic Embedding Model (Frome et al, NIPS 2013)

Apprentissage Statistique - P. Gallinari139

Modeling relational data (Bordes et al. 2013)

Apprentissage Statistique - P. Gallinari140

Objective Learn triplets (Subject, Predicate, Object) from multi-relational data Examples

Knowledge bases (S, P, O) = (Obama, president of, USA) e.g. Freebase 1.2 billion triplets, 80 million entities, thousands of relations

Social networks (A, friend of, B)

Infer new relations (S, P, ?) infer all objects in relation p with s

(S, ?, O) infer all relations between s and o

Any other inference task on the triplets

Modeling relational data (Bordes et al. 2013)

Apprentissage Statistique - P. Gallinari141

Method Learn representations for all occurrences of S, P and O so that (S, P, ?) and (S, ?,

O) questions can be answered Use the observations made in Word2Vec

When learning word representations from word sequences, some relations emerge as translations between s and o

Here the model will force the learning of translations in the representation space

Let , , ∈ the representations to be learned for S, P, O One wants if (S, P, O) holds

Representations are learned by optimizing a loss function representing this goal

Modeling relational data (Bordes et al. 2013)

Apprentissage Statistique - P. Gallinari142

The loss function is a margin based ranking function

∑ ∑ max 0, , , ,, , , , ,, , ∈

Where , is a disimilarity measure (e.g. distance)

, , is a corrupted version of , , , where either S has been replaced by a randomsubject S’ from the knowledge base or O has been replaced by O’

Margin is a positive scalar

This loss is a ranking based criterion i.e. it forces , , ,

Training It amounts at learning the representations , , by optimizing the loss Optimization is performed by stochastic gradient With the constraint 1

Modeling relational data (Bordes et al. 2013)

Apprentissage Statistique - P. Gallinari143

Examples (from Bordes et al. 2013)

Recurrent networks

Apprentissage Statistique - P. Gallinari144

Apprentissage Statistique - P. Gallinari145

Recurrent networks - Introduction Recurrent Neural Networks

They are NN with feedback loops They are dynamical systems

Dynamics Time limited

Stop the dynamic after a # time steps unlimited

Wait for convergence: stable state or limit cycle Input x :

Sixed size input x(t0), x(t) = 0, t t0 x(t) = x(t0), t

Sequential input x(t) : sequence

Supervision Defined in the time x units space {1,...T} x {units}

e.g. at each step, at some prespecified stpes x units, at the end of the sequence, … Recurrent neural networks are dynamic, non linear and continuous state

models

x(t)

di(t)

dj(t)

Apprentissage Statistique - P. Gallinari146

Recurrent networks - Introduction Tapezuneéquationici. Two types of formulation

Input – output

State models1 ,

State models include the input-output formulation as a special case

Algorithms Deux main families:

Local recurrences Global recurrences

Apprentissage Statistique - P. Gallinari147

Several formulations of RNN where proposed in the late 80s, early90s

They faced several limitations and were not successful for applications Recurrent NN are difficult to train They have a limited memory capacity

Recently (2012), new models where proposed which alleviate someof these limitations

In this course We briefly introduce key ideas of RNN We survey some of the developments from the 90s We introduce some recent developments

Local recurrences (1)

Apprentissage Statistique - P. Gallinari148

Fixed recurrent connexions Probably the simplest architecture Recurrent connections are fixed by hand Only the forward connections are learned like in classical back propagation

Can be used in two modes x fixed sequence generation

E.g. x is the first term of a sequence to be generated by the network x sequence 1 ,… , classification

y

xc

1

))(),(()())(),((1)(

txtcgtytxtcftc

Local recurrences (2)

Apprentissage Statistique - P. Gallinari149

Here the local connections may be learned are learned The figure illustrates the simple case of self connections in the hidden layer (i.e.

the connection matrix is diagonal) Extensions

Several time delays (1, 2, …) Non diagonal recurrent matrix

e.g. if delay = 1, the hidden state at time t is: 1 ∑

Where is the state of hiden cell i

Training: back-propagation for sequences Loss:

Where t are the supervision steps and 1is t is a supervision step and 0 otherwise

y

x

t-1

t-2

Tt pi

iit tdtyQ

1..

2)()(

Apprentissage Statistique - P. Gallinari150

Properties: Forgeting behavior: gradient vanishing:

Can only memorise short term dependencies

Can learn fixed size sequences up to the desired precision For unknown size sequences, there exists several limitations, e.g. cannot count the number of

occurrences in a sequence of unknown length

qj

iqtx

tx0

)()(

Dynamics of RNN

Apprentissage Statistique - P. Gallinari151

We consider different tasks corresponding to different dynamics They are illustrated for a simple RNN with loops on the hidden units This can be extended to more complex architectures

Basic architecture

x

s

y

U

V

W

Dynamics of RNN

Apprentissage Statistique - P. Gallinari152

Input and output are sequences of the same length

xt

st

yt

U

VW

xt+1

st+1

yt+1

U

VW

xt-1

st-1

yt-1

U

VW

Dynamics of RNN

Apprentissage Statistique - P. Gallinari153

Input is a sequence, output is a real value Used for classifying single sequences of length T

xt

st

U

W

xT

sT

yT

U

V

xt-1

st-1

U

W

Dynamics of RNN

Apprentissage Statistique - P. Gallinari154

Input is a fixed vector, output is a sequence

x

st

yt

U

VW st+1

yt+1

U

VWst-1

yt-1

VW

U

W

Dynamics of RNNFig from Cho et al. EMNLP 2014

Apprentissage Statistique - P. Gallinari155

Input and output are sequences of different length

Global recurrences

Apprentissage Statistique - P. Gallinari156

Training Targets are provided at specific steps

For sequences of limited size Network unfolding Algorithm

Back propagation through time (BPTT)

For general sequences Algorithm is n

x01 x02

j

ijiji txtxwftx ))()((1)( 0

Dynamics

w12

t = 1

t = 3

t = 2

w11

w11 w22

w22

w21

w12w21

Unfolded NN:note that weights are shared

Apprentissage Statistique - P. Gallinari157

Example : trajectory learning(Pearlmutter, 1995, IEEE Trans. on Neural Networks – nice review paper on RNN)

Globally recurrent net: 2 output units

Example – Global RNN: trajectory learning(Pearlmutter, 1995, IEEE Trans. on Neural Networks)

Apprentissage Statistique - P. Gallinari158

Recurrent net with 2 input units (sin q, cos q), 30 hidden units and 2 output units (x,y) :

Goal: learn a trajectory that depends on the inputs

0.50.5

/16/16

0.4tt

yx

cossin

cossinsincos

Recurrent neural networks with memory

Apprentissage Statistique - P. Gallinari159

Several attempts in order to limit or bypass the vanishing gradient problem

Here we present two families of models Reservoir computing Gated recurrent units

Add a memory to the recurrent cell, that enable to remember past states

Add a possibility to forget the past of the sequence during its processing

Allows to model several successive sub-sequences as independent sequences

Other recent developments not covered here Memory networks

Reservoir computing

Apprentissage Statistique - P. Gallinari160

Reservoir computing corresponds to differrent models based on a common idea In a RNN the input and the recurrent weights are fixed and assigned to random

values Their role is double

Perform a non linear projection of the inputs

Encode a dynamic model

Only the ouput weights will be trained This can be done using the classical optimization algorithms used for feed forward

networks

We present one model family: Echo State Networks - ESN

Reservoir computing: Echo State NetworksJaeger H. 2001

Apprentissage Statistique - P. Gallinari161

ESN principle ESN is a RNN Where input (U) and recurrent (W) weights are generated randomly Only the weights to the output (V and V’) are learned

x

s

y

U

V

WV’

Reservoir computing: Echo State Networks

Apprentissage Statistique - P. Gallinari162

ESN equations tanh - tanh is applied elementwise

The state is called a reservoir

Training Let

, … , , , … , be anassociated input– target sequence pairt , … , an output sequence computed by the ESN

Loss function

, ∑

Variant Leaky unit – to be defined

Reservoir computing: Echo State Networks

Apprentissage Statistique - P. Gallinari163

Parameter setting Size of the reservoir U and W are randomly generated W is generated sparse using typically a uniform distribution of weights on non

zero values U and V, V’ are generally dense the spectral radius of W (largest absolute eigenvalue) governs the behavior of

the memory – it is usually fixed around 1 In practice, W is generated, radius(W) is computed and . is used

Gated recurrent unit – GRU (Cho et al. 2014)

Apprentissage Statistique - P. Gallinari164

Let us start with a locally connected recurrent net with recurrent units on the hiddenlayer

The gated recurrent unit has been proposed to capture dependencies at different time scales

The forward computation for a gated recurrent unit is governed by the followingequations (explained on the next slide):

1 h

tanh ⨀

In these equations Bold characters ( , ) denote vectors is the value of hidden cell j at time t ⨀ is the elementwise multiplication

WU

Apprentissage Statistique - P. Gallinari165

1 tanh ∑ ∑

Gated recurrent unit (Cho et al. 2014)

Apprentissage Statistique - P. Gallinari166

The output of cell j is a weighted sum of the cell output at time 1, and a new value of the cell h 1 h z is a gating function

If 0 is a simple copy of

If 1 it takes the new value h w.r.t the classical recurrent unit formulation, this new form allows us to

remember the value of the hidden cell at a given time in the past and reducesthe vanishing gradient phenomenon

The gating function is a function of the current input at time t and the past value of the hidden cell

The new value is a classical recurrent unit where the values at time 1 are gated by a reset unit tanh ⨀

The reset unit allows us to forget the previous hidden state and to start again a new modeling of the sequence This is similar to a new state in a HMM (but it is soft)

h h’r

z1-z

⊕

⨂

⨂ ⨂

h

Gated recurrent unit (Cho et al. 2014)

Apprentissage Statistique - P. Gallinari167

There are two main novelties in this unit The z gating function and the + form of the cell value which acts for reducing

the vanishing gradient effect The r gating function which acts for forgeting the previous state and starting

again a new subsequence modeling with no memory

Each unit adapts its specific parameters, i.e. each may adapt its owntime scale and memory size

Training is performed using an adaptation of backpropagation for recurrent nets All the functions – unit states and gating functions are learned from the data

Long short term memory - LSTM

Apprentissage Statistique - P. Gallinari168

This was initially proposed in 1997 (Hochreiter et al.) and revisedlatter.

State of the art on several sequence prediction problems Speech, handwriting recognition, translation Used in conjontions with other models e.g. HMMs or in standalone recurrent

neural networks The presentation here is based on (Graves 2012)

Long short term memory

Apprentissage Statistique - P. Gallinari169

In the LSTM, there are 3 gating functions i: input gating o: output gating f: forget gating

Difference with the gated recurrent cell Similarities

Both use an additive form for computing the hidden cell state (c) here. This additive component reduces the vanishing gradient effect and allows us to keep

in memory past state values.

Both use a reset (called here forget (f)) gate The reset permits to start from a new « state » a subsequence prediction

Differences No output gating in the GRU

Reset does not play exactly the same role

c c’

o

if

⊕

⨂

⨂ ⨂

h

⨂

Long short term memory

Apprentissage Statistique - P. Gallinari170

For the forward pass, the different activations are computed as follows and the this order

⊙ ⊙ tanh tanh

is a memory of cell i at time t, is computed as for the GRU as a sum of and of the new memory content c tanh

o is an output gate

is a logistic function

, , are diagonal matrices

c c’

o

if

⊕

⨂

⨂ ⨂

h

⨂

Translation

Apprentissage Statistique - P. Gallinari171

NN have been used for a long time in translation systems (as an additional component, e.g. for reranking or as language model)

Recently translation systems have been proposed that are based on recurrent neural networks with GRU or LSTM units. Sutskever et al. 2014, Cho et al. 2014

General principle Sentence to sentence translation Use an encoder-decoder architecture Encoding is performed using a RNN on the input sentence (e.g. english) This transforms a variable length sequence into a fixed size vector which

encodes the whole sentence Starting with this encoding, another RNN generates the translated sentence (e.g.

French)

Translation

Apprentissage Statistique - P. Gallinari172

The encoder – decoder architecture

This is a sentence in English

Ceci est une phrase en Français

v: fixed size representation of the input sentence

Translation

Apprentissage Statistique - P. Gallinari173

Let , … , be an input sentence , … , be an output sentence Note that T and T’ might be different and that the word order in the two sentences is also

generally different

Objective Learn , … , | , … , ) Encoder

Reads each symbol of the input sentence sequentially using a RNN After each symbol the state of the RNN is changed according to , After reading the sentence, the final state is

Decoder Generates the output sequence by predicting the next symbol given the hidden state ,

and the vector : , , , … , , , ,

Training max ∑ log |

Translation

Apprentissage Statistique - P. Gallinari174

Architecture RNN with 1000 hidden cells Word embeddings of dimension between 100 and 1000 Softmax at the output for computing the word probabilities Of the order of 100 M parameters

Neural image caption generator (Vinyals et al. 2015)

Apprentissage Statistique - P. Gallinari175

Objective Learn a textual description of an image

i.e. using an image as input, generate a sentence that describes the objects and theirrelation!

Model Inspired by a translation approach but the input is an image

Use a RNN to generate the textual description, word by word, provided a learneddescription of an image via a deep CNN

Neural image caption generator (Vinyals et al. 2015)

Apprentissage Statistique - P. Gallinari176

Loss criterion max∑ log | ;,

Where ( , ) is an associated couple (Image, Sentence)

log | ; ∑ log , , … , , , … , is modeled with a RNN with , … , encoded into the

hidden state of the RNN Here , is modelled using a RNN with LSTM For encoding the image, a CNN is used

Neural image caption generator (Vinyals et al. 2015)

Apprentissage Statistique - P. Gallinari177

Apprentissage Statistique - P. Gallinari178

References Barak A. Pearlmutter, Gradient calculations for dynamic recurrent neural

networks: a survey. IEEE Transactions on Neural Networks 6(5): 1212-1228 (1995) (RNN before 1995)

Deep Learning, An MIT Press book, Ian Goodfellow, Yoshua Bengio and Aaron Courville: http://www.deeplearningbook.org, chapter 10 on recurrent NN (covers more recent developments, including GRU, LSTM etc)

Blog of A. Karpathy: The Unreasonable Effectiveness of Recurrent Neural Networks, http://karpathy.github.io/2015/05/21/rnn-effectiveness/

Apprentissage supervisé

Machines à noyaux

Apprentissage Statistique - P. Gallinari179

Introduction

Apprentissage Statistique - P. Gallinari180

Familles de machines d'apprentissage générales qui exploitent l'idée suivante : Projeter les données dans un espace de grande dimension - éventuellement infini

-où le problème sera facile à traiter Utiliser des "projections" non linéaires permettant des calculs "efficaces"

Exemples : Machines à Vecteurs Support (généralisent : hyperplan optimal, cadre Vapnik)

Processus Gaussien (généralisent : régression logistique, cadre Bayesien)

Cours Machines à Vecteurs Support

Perceptron : formulation dualehyp: 2 classes linéairement séparables, sorties désirées -1, 1

Apprentissage Statistique - P. Gallinari181

Perceptron primalInitialiser 0 0Répeter (t)

choisir un exemple, ,si . 0alors 1

Jusqu'à convergence

Fonction de décision

,

: nombre de fois où l’algorithme a rencontré une erreur de classification sur

Perceptron dualInitialiser , ∈Répeter (t)

choisir un exemple, ,soit :si ∑ . 0alors 1

Jusqu'à convergence

Fonction de décision

.

Matrice de Gram :matrice NxN de terme i, j : .matrice de similarité entre données

Représentation Duale

Apprentissage Statistique - P. Gallinari182

La plupart des machines à apprentissage linéaires ont une représentation duale Exemples

Adaline, regression, regression ridge, etc L’information sur les données est entièrement fournie par la matrice de

Gram : . , … , qui joue un rôle central

La fonction de décision F(x) s’exprime comme une combinaison linéaire de produits scalaires entre la donnée d’entrée x et les exemples d’apprentissage

Les machines à noyau généralisent ces idées Une fonction noyau K est définie sur x (on suppose ∈ ) par

, Φ , Φoù Φ est une fonction de dans un espace muni d’un produit scalaire

Produit Scalaire et Noyaux

Apprentissage Statistique - P. Gallinari183

Projection non linéaire dans un espace de grande dimension H (en général dim H >> n, et peut même être infinie) Φ: → avec ≫

Machine linéaire dans H - Primal : ∑ Φ

Machine linéaire dans H - Dual : ∑ Φ , F x ∑ Φ .Φ ,

Calculer les produits scalaires dans l'espace initial : choisir F / Φ .Φ , F x ∑ ,

avec K : fonction noyau (i.e. symétrique)

Apprentissage Statistique - P. Gallinari184

Généralise le produit scalaire dans l'espace initial Le calcul de F ne dépend pas directement de la taille de H : les

calculs sont faits dans l'espace initial. La machine linéaire dans H peut être construite à partir d'une

fonction K sans qu'il soit nécessaire de définir explicitement : en pratique, on spécifiera directement K.

Cette idée permet d'étendre de nombreuses techniques linéaires au non linéaire: il suffit de trouver des noyaux appropriés Exemples

ACP, analyse discriminante, regression, etc

Caractérisation des noyaux

Apprentissage Statistique - P. Gallinari185

Quand peut on utiliser cette idée ? Cas d'un espace fini

Soit , … , , , une fonction symétrique sur X, K est une fonction noyau ssi la matrice x dont l’élément (i, j) est , est positive semi-définie (valeurs propres 0 ou 0∀ , avec , ; , . . ))

Cas général : Conditions de Mercer (noyaux de Mercer) Il existe une application et un développement

Ssi :∀ / est fini et , 0

1)'(.)()',(

iii xxxxK

Caractérisation des noyauxEspace de Hilbert à noyau autoreproduisant Une fonction K: X ∗ X → R qui est soit continue soit définie sur un domaine fini peut

s’écrire sous la forme d’un produit scalaire :

avec Φ : x Φ(x) F espace de Hilbert

ssi c’est une fonction symétrique et toutes les matrices formées par la restriction de K à un échantillon fini sur X sont semi-définies positives).

Résultat à la base de la caractérisation effective des fonctions noyaux

Il permet de caractériser K comme un noyau sans passer par Φ C’est une formulation équivalente aux conditions de Mercer

)(),(),( zxzxK

Apprentissage Statistique - P. Gallinari186

L’espace de Hilbert associé au noyau K :

Le produit scalaire défini sur cet espace :

l

iiiii liRXxNlxKF

1..1,,,/,.)(

l

ijj

n

jii

l

ijiji

n

j

n

jjj

l

iii

zfxgzxKgf

xKgxKf

1 11 1

11

)()(),( ,

,.)((.) ,,.)((.)Soient

Apprentissage Statistique - P. Gallinari187

)(),( ,.)(,1

xfxxKxKfl

iii

Noyau auto-reproduisant

Si on prend . , . alors

Exemples de noyaux

Apprentissage Statistique - P. Gallinari189

2 d de polynomes des ensemble ss i.e.

),)2(,).(()(/ avec )().(),(

).(),(

21n

: 2 d de monomes les tousi.e.

).()(/)( avec )().(),(

).)(.(.),(

.),(

,1,1,,

2

,1,,

1,

2

1

2

ccxxxx(x)zxzxK

czxzxK

xxxxzxzxK

zzxxzxzxK

zxzxK

niinjijiji

njijiji

n

jijiji

n

iii

Exemples de noyaux (suite)

Apprentissage Statistique - P. Gallinari190

En pratique, on utilise souvent des noyaux Linéaires Gaussiens Polynomiaux

).(

gaussien noyau exp

d ordred' polynome )1.(

),(2

cxvxSigmoïde

xx

xx

xxK

i

i

di

i

Construction des noyaux en pratique

Apprentissage Statistique - P. Gallinari191

Les résultats de Mercer servent à prouver les propriétés des fonctions noyaux. En pratique, elles sont peu utiles

Pour construire des noyaux, on procède par combinaison à partir de noyaux connus

Si et sont des noyaux sur , défini sur F, les fonctionssuivantes sont des noyaux : , , , , , . , , , , , …..

Machines à vecteurs support

Apprentissage Statistique - P. Gallinari192

Exposé du cours : discrimination 2 classes Cas général : discrimination multi-classes, régression, densité Idées

Projeter -non linéairement- les données dans un espace de "très" grande taille H Faire une séparation linéaire de bonne qualité dans cet espace Raisonner dans H, mais résoudre le problème d'optimisation dans l'espace de

départ (noyaux)

Apprentissage Statistique - P. Gallinari193

Notion de marge Hyperplan H . 0

Marge géométrique pour

.

Marge de par rapport à un ensemble de données D

Hyperplan de marge maximale

wxF )(

w

wb

Marge géométrique vs marge fonctionnelle

Apprentissage Statistique - P. Gallinari194

Marge géométrique

Marge fonctionnelle .

Remplacer par ne change pas la fonction de décision ou la marge géométrique, mais change la marge fonctionnelle.

Pour les SVM, on fixera la marge fonctionnelle à 1 et on optimiserala marge géométrique.

Prémisses : Séparation linéaire à hyperplan optimal (1974)

Apprentissage Statistique - P. Gallinari195

Hyp : D linéairement séparable

Fonction de décision : F(x) = w.x + b Pb apprentissage :

trouver l'hyperplan optimal H* qui sépare D i.e. . 1, ∀

avec une marge maximale M =

i.e. : Problème Primal :

1 avec , ..1 i

Niii ddxD

wwxFd ii

i

1)(.min

1)(...

Minimiser 2

ii xFdCS

w

Apprentissage Statistique - P. Gallinari196

Dans le cas de noyaux linéaires, on résout en général le problème primal Il existe de nombreux algorithmes rapides

Dans le cas de noyaux non linéaires, on va en général résoudre une version duale du problème On introduit ensuite quelques notions d’optimisation sous contrainte pour

décrire la formulation duale du problème

Intermède

OptimisationProblèmes sous contraintes égalités, inégalités

Apprentissage Statistique - P. Gallinari197

OptimisationProblèmes sous contraintes égalités, inégalités

Apprentissage Statistique - P. Gallinari198

Soient , , ,…, , , ,…, des fonctions définies sur à valeur dans

On considère le problème primal suivant (pb. 0) :

Fonction objectif Région admissible ∈ Ω: 0, 0 , région de Ω où est définie

et les contraintes vérifiées

* est un minimum global si il n’existe pas d’autre point tel que ∗ , c’est un optimum local si ∃ 0: ∗ , sur la boule ∗

Une contrainte 0 est dite active si la solution w* vérifie ∗ 0 et inactive sinon

La valeur optimale de la fonction objectif (solution du pb. 0 est appelée la valeur du problème d’optimisation primal)

, ∈ Ω ⊂Sous contraintes

0, 1, … ,k noté 00, 1,… ,m noté 0

Apprentissage Statistique - P. Gallinari199

est convexe pour ∈ si ∀ ∈ 0,1 , ∀ , ∈ , ∀t ∈ [0,1], 1 1

Un ensemble Ω ⊂ est convexe si ∀ , ∈ , ∀t ∈ [0,1], 1 ∈Ω

Si une fonction est convexe, tout minimum local est un minimum global Un problème d’optimisation pour lequel Ω est convexe, la fonction objectif

et les contraintes sont convexes est dit convexe

Optimisation non contrainte

Apprentissage Statistique - P. Gallinari200

Th. Fermat

Une C.N. pour que w* soit un min. de , ∈ est ∗

Si est convexe c’est une Condition Suffisante

Optimisation avec contraintes égalitésLagrangien

Apprentissage Statistique - P. Gallinari201

Optimisation avec contraintes égalité (pb 1):

On définit le Lagrangien , associé à ce problème par, ∑

les sont les coefficients de Lagrange

Rq Si ∗ est une solution du problème d’optimisation sous contrainte, ll est possible

que ∗

, ∈ Ω ⊂Sous les contraintes

0, 1, … ,m noté 0

Optimisation avec contraintes égalitésTh. Lagrange

Apprentissage Statistique - P. Gallinari202

Th. Lagrange Une CN pour que ∗, soit solution de (pb. 1), avec , ∈ est

∗, ∗

∗, ∗

Si , ∗ est une fonction convexe de , c’est une condition suffisante

Rq La première condition donne un nouveau système d’équations

La seconde donne les contraintes

Optimisation sous contraintes égalité + inégalités - Lagrangien augmenté

De même, on définit le Lagrangien augmenté pour le pb. 0 :

, ,

Apprentissage Statistique - P. Gallinari204

Formulation duale du problème d’optimisation Le problème d’optimisation dual correspondant au problème primal pb 0 est :

, , min∈

, ,

sous contrainte 0

Max , estappelélavaleurdudual

Rq : inf∈

, , est une fonction de , uniquement

Propriété : la valeur du dual est bornée supérieurement par la valeur du primalmax, ,

min∈

, , min∈

max, ,

, ,

Dans certains cas, on a égalité, cf. dualité forte

Apprentissage Statistique - P. Gallinari205

Théorème de dualité forte Etant donné un problème d’optimisation

, ∈ Ω ⊂ convexe et ∈ convexeSous contraintes

0, 1, … ,k noté 00, 1,… ,m noté 0

où les et les sont affines (

alors les valeurs du primal et du dual sont égales

Les conditions d’existence d’un optimum sont données par le théorème de Kuhn et Tucker

OptimisationTh. Kuhn et Tucker

On considère (pb. 0) avec Ω convexe et f C1 convexe, gi, hj affines (h = A.w+ b)

Une CNS pour que w* soit un optimum est qu’il existe α* et β* :

Sous les hypothèses de convexité, la formulation duale est une alternative à la formulation primale qui peut se révéler plus simple à traiter (e.g. SVM non linéaires)

kikiwg

kiwg

wLw

wL

i

i

ii

..1,0*..1,0*)(

..1,0*)(*

0*)*,*,(

0*)*,*,(

Apprentissage Statistique - P. Gallinari206

Apprentissage Statistique - P. Gallinari207

Rq

La 3e condition dite condition complémentaire de Karush-Kuhn-Tucker implique que pour une contrainte active ∗ 0 alors que pour une contrainte inactive ∗ 0 Soit une contrainte est active ( ∗ 0 et gi(w*) = 0), w* est un point frontière de la

région admissible

Soit elle est inactive (αi* = 0) et w* est dans la région admissible

Si le point solution w* est dans la région admissible (contrainte inactive) alors les conditions d’optimalité sont données par le th. de Fermat et ∗ 0. Si il est sur la frontière (contrainte active), les conditions d’optimalité sont données par le th. de Lagrange avec ∗ 0.

Fin de l’intermède

SVM – formulations primale et dualeCas d’un noyau linéaire SVM

Ω, et les contraintes sont convexes, L est quadratique On étudie le cas, , … linéairement séparables,

∈ 1,1 Pb. Primal

Lagrangien primal

Lagrangien dual

Avec 0 dans les 2 cas

Nibxwd

wwMin

ii ..1,1).(scontrainte les sous

marge) lamax (i.e. ).(

Apprentissage Statistique - P. Gallinari208

N

i

iii bxwdwwbwL

1)1).((.

21),,(

N

i

jiji

jiN

ii xxddbwL

11).(

21),,(

SVM – formulations primale et duale Pb. Dual

C’est un problème d’optimisation quadratique sous contrainte

Ni

d

xxddL

i

N

ii

i

N

i

jiji

jiN

ii

..1,0

scontrainte les sous

).(21)(Max

1

11

Apprentissage Statistique - P. Gallinari209

Apprentissage Statistique - P. Gallinari210

Solution : w* dépend uniquement des points supports i.e. points sur la marge qui vérifient : ∗ 1

la fonction de décision prend la forme

Rq: Quelque soit la dimension de l'espace, le nombre de degrés de liberté est "égal" au nombre de points de support

F* dépend uniquement du produit scalaire xi.x

Marge

Vecteurs Supports

portivecteur

ii

i bxxdxFsup

*).(**)*,,(

Machines à vecteurs supportscas de noyaux non linéaires

Apprentissage Statistique - P. Gallinari211

Faire une séparation à marge max. dans un espace défini par une fonction noyau.

Tous les résultats sur le classifieur linéaire à marge max. se transposent en remplaçant par .xxi ),( xxK i

bxxKdxF

xxKxx

bxxdxFxdW

RR

SVx

ii

i

SVx SVx

ii

iii

i

pn

i

i i

..

.. ..

),()(

)',()'().(

)()()( )(

:

Apprentissage Statistique - P. Gallinari212

Apprentissage : On résout le problème d'optimisation dual :

Problème minimisation quadratique sous contraintes dans l ’espace de départ Difficile en pratique : différents algorithmes. Dans la solution optimale i > 0 uniquement pour les points support.

Seuls les produits scalaires K apparaissent, et pas les .

0et 0.

),()( Maximiser

ii

,

ii

ji

jijiji

ii

dCS

xxKddL

Propriétés de généralisation -exemples

Apprentissage Statistique - P. Gallinari213

Th 1 peu de points support meilleure généralisation indépendant de la taille de l'espace de départ

Th 2 Si l'hyperplan optimal passe par l'origine et a pour marge

Alors

Dans les 2 cas, E[P()] est l'espérance sur tous les ensembles de taille l-1, et E[membre droit] est l'espérance sur tous les ensembles d'apprentissage de taille l (leave one out).

1ageapprentissexemples#supports]vecteurs[#))](([

ExerreurPE

qxNiq i ,1../

N

][))](([

2

2

qExerreurPE

Cas non linéairement séparable

Apprentissage Statistique - P. Gallinari214

Marges molles L'algorithme est instable

Dans les cas non linéairement séparables Dans le cas de données réelles même linéairement séparables Solution adoptée en pratique

autoriser des erreurs, i.e. prendre pour contraintes :

ηi = 0, xi est correctement classifié et est du bon coté de la marge

0 < ηi <= 1, xi est correctement classifié, est à l’intérieur de la marge

ηi > 1, xi est mal classé

ηi : slack variable

1))(.(

i

iii bxWd

But Maximiser la marge tout en pénalisant les points qui sont mal classés

Formalisation Plusieurs expressions possibles du problème L’une des plus courantes :

C fixé par validation croisée joue le rôle de paramètre de régularisationNi

NibxwdCS

CwwMin

ii

N

i

..1,0 ..1,1).(

..

marge) lamax (i.e. ).(

i

i

1

i

Apprentissage Statistique - P. Gallinari215

Marges molles – formulation duale

0et 0.

),()( Maximiser

ii

,

ii

ji

jijiji

ii

dCCS

xxKddL

Apprentissage Statistique - P. Gallinari216

Algorithmes d’optimisation Algorithmes d’optimisation standard pour la programmation

quadratique sous contrainte e.g. Sequential Minimal Optimization (SMO)

Algorithmes stochastiques - SVM Results –(Bottou 2007) Task : Document classification - RCV1 documents belonging to the class

CCAT (2 classes classification task) Programs SVMLight and SVMPerf are well known SVM solvers written by Thorsten Joachims.

SVMLight is suitable for SVMs with arbitrary kernels. Similar results could be achieved using Chih-Jen Lin‘s LibSVM software. SVMPerf is a specialized solver for linear SVMs. It is considered to be one of the most efficient optimizer for this particular problem.

Algorithm (hinge loss) Training Time Primal cost Test Error

SVMLight 23642 secs 0.2275 6.02%

SVMPerf 66 secs 0.2278 6.03%

Stochastic Gradient (svmsgd) 1.4 secs 0.2275 6.02%

Stochastic Gradient (svmsgd2 1.4 secs 0.2275 6.01%Apprentissage Statistique - P. Gallinari217

Apprentissage non supervisé

Algorithme EM et mélange de densitésSpectral clustering

Non Negative Matrix Factorization

Applications

Apprentissage Statistique - P. Gallinari219

analyse des données quand il n'y a pas de connaissance sur la classe. e.g. pas d'étiquetage des données (problème nouveau)

trop de données ou étiquetage trop compliqué e.g. traces utilisateur (web), documents web, parole, etc

réduction de la quantité d'information e.g. quantification

découverte de régularités sur les données ou de similarités.

Apprentissage non supervisé

Algorithme Espérance Maximisation (EM)Application aux mélanges de densités

Algorithme E. M. (Espérance Maximisation) -Introduction

Apprentissage Statistique - P. Gallinari221

On dispose de données ; 1…

On n’a pas d’étiquette associée à

d’un modèle génératif, de paramètres

On veut trouver les paramètres du modèle qui expliquent au mieux la génération des données

On se donne un critère Ici on considère la vraisemblance des données qui est le critère le plus fréquent

; , … , ; D’autres critères sont également utilisés

On va essayer de déterminer les paramètres de façon à maximiser la vraisemblance

EM IntroductionExemple : mélange de deux populations

Apprentissage Statistique - P. Gallinari222

On recueille des données sur deux populations e.g. taille d’individus ; 1… Hypothèse : les données de chaque population sont gaussiennes à 1 dimension

, , ,

Problème Estimer les et les à partir des données

Si les sont connus, i.e. , ; 1… la solution est simple On a deux population séparées (2 classes) 1, 2 On utilise les estimateurs classiques de la moyenne et de la variance

Pour la moyenne | |

∑ ∈ , idem pour la variance

Ces estimateurs usuels sont les estimateurs du maximum de vraisemblance cf. slide suivant

EM Introduction - Mélange de deux populationsCas où l’appartenance est connue

Apprentissage Statistique - P. Gallinari223

Vraisemblance ∏ |∈ ∏ |∈

En pratique on maximise la log-vraisemblance log ∑ ∑ ∈∈

Cas des gaussiennes

exp

0 ⇔| |

∑ ∈ , idem pour la variance

EM Introduction - Mélange de deux populations Cas où la probabilité d’appartenance est connue

Apprentissage Statistique - P. Gallinari224

On connait les | , k = 1, 2 pour tous les de l’ensemble d’apprentissage

C’est un modèle de mélange de deux densités

Log-vraisemblance log ∑ log Cas des gaussiennes

0 ⇔∑ .

∑ |, idem pour la variance

EM Introduction - Mélange de densités gaussiennesLa probabilité d’appartenance est inconnue

Apprentissage Statistique - P. Gallinari225

On suppose que les données sont générées par le modèle suivant Tirer ~ 0, ∑ 1 Tirer / | ~ , i.e. est généré en choisissant d’abord ∈ 1,… , et ensuite en effectuant un

tirage suivant une gaussienne , si

C’est ce qu’on appelle un mélange de gaussienne la vraisemblance des données s’écrit

, , ∏ ; ∏ ∑ , ;

| ; , |

La log vraisemblance , , ∑ log ∑ | ; , |

Les deux exemples précédents (appartenance connue et probabilité d’appartenance connue sont des cas particuliers de ce modèle de mélange)

EM Introduction - Mélange de densités gaussiennes (suite)

Apprentissage Statistique - P. Gallinari226

Quand la probabilité d’appartenance est inconnue, on ne peut pas trouver une forme analytique pour les estimateurs du maximum de vraisemblance

L’algorithme E.M. apporte une solution à ce problème Il itère 2 étapes principales

Etape E (Espérance) On calcule une fonction auxiliaire qui est une borne inférieure de la vraisemblance des

données

Cette borne inférieure est l’espérance de la vraisemblance complète des données (voir plus loin)

Etape M (Maximisation) – estimation des paramètres des gaussiennes On estime les paramètres du modèle, i.e. les , , , 1,… , qui maximisent

cette fonction auxiliaire

Algorithme E.M. – Cas général

Apprentissage Statistique - P. Gallinari227

Problème On a un problème d’estimation pour lequel on connait un ensemble

d’apprentissage , … , On veut trouver les paramètres qui maximisent la (log) vraisemblance des

données L log ; On ne connait pas de formule analytique permettant d’estimer les paramètres

On postule l’existence de variables cachées z responsables de la génération des données

À chaque , on associe sa classe cachée; 1. .

l’existence d’une fonction densité jointe sur les données observées et cachées,

p , | sera appelé vraisemblance complète des données pour le modèle .

Remarque Les variables sont inconnues et sont considérées comme des variables

aléatoires , | sera donc elle même une variable aléatoire

Algorithme EM - Cas général

Apprentissage Statistique - P. Gallinari228

L’algorithme E.M. fournit une solution à notre problème C’est un algorithme itératif en 2 étapes

Etape E. Construire une borne inférieure de

Etape M. Déterminer les paramètres qui optimisent cette borne inférieure

La borne inférieure est construite de façon à garantir une optimisation de

Algorithme EM – Cas general

Apprentissage Statistique - P. Gallinari229

La borne inférieure est définie par une fonction auxiliaire Q Q est l’espérance de la log-vraisemblance des données complètes log , ; , connaissant le modèle courant à l’étape t ,

L’espérance est calculée par rapport à la distribution des variables cachées connaissant le modèle courant : ;

, log , ; ∑ log , ; | ;

Dans cette expression : et sont des constantes est une variable aléatoire de densité | ; , est l’ensemble des

variables représente les paramètres que l’on veut estimer

Algorithme EM – Cas general

Apprentissage Statistique - P. Gallinari230

On va montrer que , est une borne inférieure de Pour cela on utilisera l’inégalité de Jensen Théorème

Soit une fonction convexe définie sur et x une variable aléatoire réelle, alors

Si f est strictement convexe si et seulement si est une constante

Rq est convexe si 0∀ Pour une fonction concave, l’inégalité est vérifiée dans le sens opposé

Algorithme EM – Cas general

Apprentissage Statistique - P. Gallinari231

; ∑ log ;

∑ log∑ , ;

∑ log∑ ; , ;;

∑ log ~ ;, ;;

∑ ~ ; log , ;;

∑ ∑ ; , ;;

On a utilisé la concavité de la fonction log pour l’inégalité Comme dans l’étape M, on maximise par rapport à , on peut éliminer le

dénominateur du log dans l’expression précédente, on retrouve alors

Q , ∑ ∑ ; log , ; En maximisant Q, on maximise une borne inférieure de la vraisemblance

Algorithme EM – Cas general

Apprentissage Statistique - P. Gallinari232

On peut montrer ensuite la convergence de l'algorithme par : 1 , , ⇒ ; 1 ;

Algorithme EM - Cas général

Apprentissage Statistique - P. Gallinari233

L’algorithme converge vers un maximum local de la fonction Q et de ;

Initialiser 01. Etape E : Espérance

On calcule | ,On en déduit ;L'espérance est calculée par rapport à la distribution de Z pour

les paramètres courants2. Etape M : MaximisationEtant donnée la distribution courante sur Z, trouver les paramètres quimaximisent Q

1 ~ | ; log , ;

Algorithme EM - Cas général

Apprentissage Statistique - P. Gallinari234

Remarques Lors de l'étape E, on estime la distribution de Z : | ;

à partir des valeurs courantes des paramètres Au lieu d'essayer de maximiser directement, | , on utilise la

fonction auxiliaire Q. L'algorithme est utilisé pour

les algorithmes non supervisés, semi - supervisés les données manquantes ou les composantes manquantes dans les données les HMM ...

Algorithme EM - Mélange de densités – cas gaussien

Apprentissage Statistique - P. Gallinari235

On suppose que le modèle génératif des données est un mélange de densités gaussiennes On fixe a priori le nombre de composantes du mélange à k Pour simplifier, on suppose que les données x sont unidimensionnelles

∑ | , exp

Paramètres Coefficients du mélange , moyennes et écarts types :

, , ; 1…

Algorithme EM - Mélange de densités – cas gaussien

Apprentissage Statistique - P. Gallinari236

Log-vraisemblance log ; ∑ log∑ ; | ;

Vraisemblance complète log , ; ∑ log ; ; ∑ ∑ log ; ;

)

Fonction auxiliaire Q , E ~ | ; logp D, Z;

∑ …∑ log , ; ∏ | ; quelques réécritures conduisent à l’expression :

∑ ∑ ; log ; ; Qui sera utilisée dans la maximisation de l’étape M.

Algorithme EM - Mélange de densités – cas gaussien – Etapes E et M

Apprentissage Statistique - P. Gallinari237

Etape E

; ; ;∑ ; ;

∀ ,

Etape M , sous la contrainte ∑ ; 1 Équivalent à

, ∑ ; 1 Avec le coefficient de Lagrange associé

Remarque Dans l’étape E on n’a pas besoin de calculer explicitement , , il suffit de

calculer les ; (cf dérivation du résultat en cours)

Algorithme EM - Mélange de densités – cas gaussien – Reestimation dans l’étape M

Apprentissage Statistique - P. Gallinari238

à l’étape M à l’itération t, on obtient les formules de reestimationsuivantes ∑ ;

∑ ;

∑

∑ ;

∑

Algorithme EM - Mélange de densités – cas gaussien

Apprentissage Statistique - P. Gallinari239

Etape E Si on connait les lois de mélange (les , , ), on peut facilement calculer les

par

Etape M Si on connait les probabilités d’appartenance, on peut facilement estimer les

paramètres des lois de mélange comme vu dans l’exemple

Il suffit de partir d’une valeur initiale – pour les ou pour les paramètres des lois de mélange pour exécuter l’algorithme Celui ci converge vers un maximum local de la vraisemblance

Apprentissage non supervisé

Mélange de densitésApprentissage par échantillonnage de Gibbs

Les méthodes MCMCMarkov Chain Monte Carlo

Apprentissage Statistique - P. Gallinari241

Méthodes de calcul intensif basées sur la simulation pour Echantillonnage de variables aléatoires

.. qui suivent une certaine distribution

Calcul de l’espérance de fonctions suivant cette distribution

sera estimé par ∑

e.g. moyenne, marginales, …

Maximisation de fonctions

Echantillonneur de Gibbs

Apprentissage Statistique - P. Gallinari242

On veut estimer une densité , ∈ , avec , … , Hypothèse

On connait les lois conditionnelles , … , , , … , qui sera notée |

Algorithme Initialiser , 1, … , Itérer jusqu’à convergence (variable d’itération notée ) échantilloner

~ | ,… , …..

~ | ,… , Jusqu’à ce que la distribution jointe , … , ne change plus

Apprentissage Statistique - P. Gallinari243

Propriétés Sous certaines conditions de régularité, la procédure converge vers la

distribution cible Les échantillons résultants sont des échantillons de la loi jointe

On n’a pas besoin de connaitre la forme analytique des | maisuniquement de pouvoir échantillonner à partir de ces distributions Mais la forme analytique permet d’avoir de meilleurs estimés

Avant de retenir les points échantillons, on autorise souvent une période de “burn-in” pendant laquelle on fait simplement tourner l’algorithme “à vide”

Gibbs facile à implémenter, adapté aux modèles hierarchiques (cf LDA)

Cas du mélange de deux lois gaussiennes Modèle : ∑ |

On considère un mélange de deux gaussiennes à une dimension

On va considérer un modèle augmenté en ajoutant une variable cachée∈ 0,1

Les données complètes sont les , Les paramètres à estimer sont

Les paramètres des gaussiennes : , , ; 1,2 La variable cachée (qui est considérée comme un paramètre supplémentaire à estimer

dans la procédure de gibbs)

On va utiliser Gibbs en échantillonnant sur les densités conditionnelles des paramètres , | Pour simplifier on suppose dans l’example que les proportions et les

variances sont fixées, on estime juste les moyennes ,

Pour cela, on va échantillonner suivant la distribution jointe , , |

Apprentissage Statistique - P. Gallinari244

Echantillonneur de Gibbs pour le modèle de mélange de deux gaussiennes

Apprentissage Statistique - P. Gallinari245

Hyp: et , 1,2 sont supposés connus Choisir des valeurs initiales 0 , 0 Répéter ( 1,2, …) jusqu’à convergence (i.e. , 1,2 ne changent plus)

Pour 1… Générer ∈ 0,1 selon la distribution

1| | ; ,; , | ; ,

Rq: c’est une loi de Bernouilli de paramètre le membre droit de l’équation

Calculer

∑∑

∑

∑

Et générer ~ , , 1,2

Lien avec l’algorithme EM

Apprentissage Statistique - P. Gallinari246

Les étapes pour cet exemple sont les mêmes qu’avec EM Différence

Au lieu de maximiser la vraisemblance, aux étapes 1 et 2, on échantillonne Etape 1 : on simule les variables cachées z à partir de la distribution conditionnelle

, au lieu de calculer | , dans EM

Etape 2 : on simule à partir de 1, 2| , au lieu de calculer le max. vraisemblance 1, 2, | dans EM

Apprentissage Statistique - P. Gallinari247

Remarque 1 Pour simplifier on a supposé que les proportions et les variances , 1,2

étaient fixes. Dans le cas général où elles ne sont pas connues, on va

1. fixer des valeurs initiales de l’ensemble des paramètres , , ; 1,2 à partir de distribution a priori pour ces paramètres

2. échantillonner alternativement pour chaque paramètre selon sa distribution a posteriori, conditionnellement aux autres paramètres Par exemple on échantillonnera successivement pour ( , , , , puis ,

Remarque 2 Il existe d’autres méthodes pour estimer des densités de façon approchée quand

il n’existe pas de forme analytique conduisant à des calculs, e.g. méthodes variationnelles

Apprentissage non supervisé

Spectral Clustering

Apprentissage Statistique - P. Gallinari248

Spectral Clustering (after Von Luxburg 2007)

Apprentissage Statistique - P. Gallinari249

Intuition x1, …, xn data points, wij similarity between xi and xj

G = (V, E) undirected graph V = {v1, …, vn), vertex vi corresponds to data point xi

Edges are weighted, W = (wij)I, j = 1…n , wij ≥ 0 is the weight matrix

D : diagonal matrix with ∑

Clustering amounts at finding a graph partition such that Edges between clusters have low weights

Edges among points inside a cluster have high values

Spectral Clustering

Apprentissage Statistique - P. Gallinari250

Building similarity graphs from data points Different ways to build a similarity graph Build a locally connected graphs: k-nearest neighbor graphs

Two vertices are connected if one of them is among the k-nearest neighbor of the other

Or two vertices are connected if both are in the k-neighborhood of the other

Edges are then weighted using the similarity of the vertices

Build a fully connected graphs

exp /2 )

Spectral Clustering

Apprentissage Statistique - P. Gallinari251

Graph Laplacians Unnormalized graph Laplacian

Normalized graph Laplacians

I symmetric

interpretation : random walk on the graph

Spectral Clustering

Apprentissage Statistique - P. Gallinari252

Properties of the unnormalized graph Laplacian L Proposition 1- satisfies:

∀ ∈ , ∑ , is symmetric, positive semi-definite The smallest eigenvalue of is 0, the corresponding eigenvector is (vector with n

1s) has n non negative eigenvalues 0 …

Proof

∑ ∑ ∑, 2∑ , ∑

∑ ,

Symmetry follows from the symmetry of and , positive semi definiteness comes from 0

Obvious: a symmetric, positive semi-definite matrix has all its eigenvalues 0 Direct consequence of properties 1 and 3

Spectral Clustering

Apprentissage Statistique - P. Gallinari253

Proposition 2 (number of connected components and spectrum of L) Let G be an undirected graph with non negative weights. The multiplicity k of the

eigenvalue 0 of L equals the number of connected components in the graph. The eigenspace of eigenvalue 0 is spanned by the indicator vectors of these components.

This result provides intuition on spectral clustering algorithms Connected graph

Let us consider first 1. If is an eigenvector with eigenvalue 0 then 0∑ . Since 0 this is only possible if ∀ , . In a graph with 1connected component, 1 the constant vector filled with 1 is the eigenvector with eigenvalue 0. It is also the indicator vector of the connected component

Multiple components If there are connected components. The matrix and hence can be arranged in a block

diagonal form. The above result holds for each connected component . The corresponding eigenvectors are the 1 with 1 corresponding to the block and 0 everywhere else.

If one can identify these eigenvectors, one will identify the clusters This is only intuition, the situation is usually more complex (see Luxburg 2007)

Spectral Clustering

Apprentissage Statistique - P. Gallinari254

Properties of the normalized graph Laplacians

∀ ∈ , ∑ ,

Lsym and Lrw are positive semi-definite and have n non negative eigenvalues 0 …

is an eigenvalue of Lrw with eigenvector u iff is an eigenvalue of Lsym with eigenvector D1/2u

Unnormalized spectral clustering algorithm

Apprentissage Statistique - P. Gallinari255

Idea Project data points x ∈ , i 1…n, in a smaller dimensional space, say of

dimension k where clustering is performed

Input: n points 1, … , , similarity matrix

Output: clusters Construct similarity graph and corresponding weight matrix Compute unnormalized Laplacian Compute first eigenvectors of (corresponding to smallest eigenvalues): , … , : matrix with columns 1, … , For 1… , ∈ i-th row of Cluster the , 1… with k-means algorithm into clusters C1, …, Ck

clusters in the initial space: ’1, … , ’/ ’ /

Note: Similar algorithms with normalized Laplacians

Apprentissage non supervisé

Non Negative Matrix Factorization

Apprentissage Statistique - P. Gallinari256

Matrix Factorization

Apprentissage Statistique - P. Gallinari257

Idea Project data vectors in a latent space of dimension k < m size of the original

space Axis in this latent space represent a new basis for data representation Each original data vector will be approximated as a linear combination of k basis

vectors in this new space Data are assigned to the nearest axis This provide a clustering of the data

Matrix factorization

Apprentissage Statistique - P. Gallinari258

= {x.1,…, x.n}, ∈ m x n matrix with columns the .i s Low rank approximation of

Find factors U, V, / With U an m x k matrix, U a k x n matrix, k < m, n

x

m x n m x k k x n

Many differentdecompositions e.g. SingularValue Decomposition, Non Negative Matrix Factorization, Tri factorization, etc

X U V

MARAMI 2013 - Learning representations for social networks

259

Applications Recommendation (User x Item matrix)

Matrix completion

Link prediction (Adjacency matrix) …

MARAMI 2013 - Learning representations for social networks

260

. ∑ .

Columns ofU,u.j arebasisvectors,the arethecoefficientof . inthisbasis

X V

x.j v.ju.1u.2u.3

Original data Basis vectorsDictionnary

Representation

x

v.j

u.1

u.2

u.3

MARAMI 2013 - Learning representations for social networks

261

Interpretation If is a User x Item matrix

Users and items are represented in a common representation space of size k Their interaction is measured by a dot product in this space

x.jv.j

ui.

Original dataUser Representation

Item Representation

xUsers

Items

MARAMI 2013 - Learning representations for social networks

262

Interpretation If is a directed graph adjacency or weight matrix

x.jv.j

ui.

Original data Sender Representation

ReceiverRepresentation

xNodes

Nodes

MARAMI 2013 - Learning representations for social networks

263

Loss function - example Minimize ,

constraints on U, V: , e.g. Positivity (NMF)

Sparsity of representations, e.g. , group sparsity, …

Overcomplete dictionary U: k > m

Symmetry, e.g. trifactorisation

Bias on U and V e.g. biases of users (low scores) or item (popularity) for recommendation

Multiple graphs

Any a priori knowledge on U and V

Non Negative Matrix Factorization

Apprentissage Statistique - P. Gallinari264

Loss function Solve

, Underconstraints , 0

i.e.thefactors areconstrained tobe nonnegative Convex loss function in andin ,butnotinboth and

Apprentissage Statistique - P. Gallinari265

Algorithm Constrained optimization problem Can be solved by a Lagrangian formulation

Iterative multiplicative algorithm (Xu et al. 2003)

U, V initialized at random values Iterate until convergence

←

←

Or by projected gradient formulations The solution U, V is not unique, if U, V is solution, then UD, D-1V for D diagonal

positive is also solution

Apprentissage Statistique - P. Gallinari266

Using NMF for Clustering Normalize U as a column stochastic matrix (each column vector is of norm 1)

←∑

← ∑

U columns are cluster centroids, V columns are cluster membership indicators. Under the constraint “ normalized” the solution , is unique Associate to cluster if

Apprentissage Statistique - P. Gallinari267

Note Many different versions and extensions of NMF Different loss functions

e.g. different constraints on the decomposition

Different algorithms

Applications Clustering Recommendation Link prediction Etc

Specific forms of NMF can be shown equivalent to PLSA Spectral clustering

Illustration (Lee & Seung 1999)

Apprentissage Statistique - P. Gallinari268

Basis images for

NMF

Vector Quantization

Principal Component Analysis

Apprentissage Statistique - P. Gallinari269

Citations Ulrike Luxburg. 2007. A tutorial on spectral clustering. Statistics and Computing

17, 4 (December 2007), 395-416. Daniel D. Lee and H. Sebastian Seung (1999). "Learning the parts of objects by

non-negative matrix factorization". Nature 401 (6755): 788–791. W. Xu, X. Liu, and Y. Gong. (2003) Document clustering based on non-negative

matrix factorization. SIGIR ’03, page 267 Yang and E. Oja. Linear and nonlinear projective nonnegative matrix factorization.

IEEE Trans. on Neural Networks, 21:734–749, 2010.

Variational Auto-Encoders

After Kingma D., Welling M., Auto-EncodingVariational Bayes, ICLR 2015And

A. Courville Deep Learning Course

Apprentissage Statistique - P. Gallinari270

VAEs - Intuition

Apprentissage Statistique - P. Gallinari271

Generative latent variable model

Sample from ~ and generate | Given a simple distribution , e.g ~ 0, I , use a NN to learn a

possibly complex mapping

Z x

θ

Decoder NN

VAEs - Intuition

Apprentissage Statistique - P. Gallinari272

Examples (Kingma et al. 2015)

Images from https://blog.keras.io/building-autoencoders-in-keras.html (F. Chollet)

Apprentissage Statistique - P. Gallinari273

Exemple on MNIST digits

2 D latent space: color correspond to a digit latent representation

Digit reconstruction from the latent space representation

VAEs - Intuition

Apprentissage Statistique - P. Gallinari274

How to choose z? Inference model VAEs compute using a parametric function |

Zx

Φ

Encoder NN

g

VAEs - Intuition

Apprentissage Statistique - P. Gallinari275

Putting it all together

sampling deterministic

Encoder NN

g

Decoder NN

Z x

θ

Zx

Φ

VAEs - Intuition

Apprentissage Statistique - P. Gallinari276

What are they used for? Data reconstruction as classical auto-encoders Data generation (top part of the VAE), by sampling from the latent space Data encoding (low part of the VAE), by learning latent space probabilistic

representations

Learning Optimize data log likelihood log

For doing his, one will learn the and parameters Using stochastic gradient descent

VAEs - Intuition

Apprentissage Statistique - P. Gallinari277

Difficulties , and | may be intractable

, Computing the integral requires evaluating over all the configurations of latent variables, often

intractable

Same problem with the Rk: to learn the parameters in a latent model using max. likelihood, one needs to

compute | – remember E.M. Solutions

MCMC Variational methods → a special form of variational inference is used in VAE

Z x

θ

Prerequisite

Apprentissage Statistique - P. Gallinari278

Kullback Leibler divergence Measure of the difference between two distributions and Continuous variables

|| log

Discrete variables

|| ∑ log

Property || 0 | 0 iff

Rk: is asymmetric, symmetric versions exist

VAE description

Apprentissage Statistique - P. Gallinari279

Let us suppose available A set of observed variables Continuous latent variables Joint pdf , , model parameters, continuous and differentiable

Objective Learn the parameters using maximum likelihood on observed data , … ,

VAE Trained as an auto-encoder (end to end) Using stochastic gradient Problem

| intractable and is needed for max. likelihood estimation of the parameters

Solution Approximate | with

Using a variational approximation

Loss criterion – summary (details in the slides to follow)

Apprentissage Statistique - P. Gallinari280

Log likelihood for data point :

log || | , ; . | . 0, then , ; is a lower bound of log

in order to maximize log , we will maximize , ; Variational lower bound:

, ; | || log | Maximizing , ; is equivalent to minimizing D | ||

Remarks log | is a reconstruction term

Measures how well the datum can be reconstructed from latent representation

| || is a regularization term: Forces the learned distribution | to stay close to the prior p(z) p(z) has usually a simple form e.g. 0, , then | is also forced to remain simple

Because each representation is associated to a unique , the loss likelihood can be decomposed for each point –this is what we do here The global log likelihood is then the summation of these individual losses

Apprentissage Statistique - P. Gallinari281

log D || | , ; log log | ( log | 1

log log ,|

|

log log ,|

||

|

log log ,|

| log ||

|

log | log p x, z log | ||

log , ; D | ||with

, ; | logp , log Maximizing log is equivalent to maximizing , ; (and minimizing

D | || , ; is an Evidence Lower Bound (ELBO)

Apprentissage Statistique - P. Gallinari282

, ; | || log | , ; E | , log |

, ; E | | log log |

, ; D || E | | ]

This form provides a link with a NN implementation The generative and inference modules will be trained to

maximize the reconstruction error for each , : log |

The inference module will be constrained to remain close to the prior: D ||

Apprentissage Statistique - P. Gallinari283

Loss function in the NN model

Training performed via Stochastic gradient This requires an analytical expression for the loss functions and gradient

computations

Encoder NN Decoder NN

|

Regularization lossKL ||

Reconstruction lossE | | ]

Apprentissage Statistique - P. Gallinari284

Training with stochastic units: reparametrization trick Not possible to propagate the gradient through stochastic units (the zs and xs

are generated via sampling) Solution

Parametrize as a deterministic transformation of a random variable : ,with ~ independent of , e.g. ~ 0,1

Example If ~ , , it can be reparameterized by ⨀ , with ~ 0,1 , with ⨀

pointwise multiplication ( , are vectors here) For the NN implementation we have: ⨀

This will allow the derivative to « pass » through the

For the derivative, the sampling operation is regarded as a deterministic operation withan extra input , whose distribution does not involve variables needed in the derivation

Apprentissage Statistique - P. Gallinari285

Reparametrization (fig. from D. Kingma)

Apprentissage Statistique - P. Gallinari286

Special case: gaussian priors and posteriors Hyp:

0, , , diagonal matrix , , diagonal matrix

Variational lower bound , ; | || log | In this case, | || has an analytic expression

| | ∑ 1 log

log | is estimated using Monte Carlo sampling

log | ≃ ∑ log | ∑ log

i.e. samples with , , ∈

Apprentissage Statistique - P. Gallinari287

If ∈ : | || ∑ 1 log

| log

Consider the 1 dimensional case log ; , log ; 0,1

log log 2 Property of 2nd order moment of a Gaussian

log ; , log ; ,

log log 2 1 log

……

Since both ddp are diagonals, extension to J dimensions is straightforward, hence the result

Apprentissage Statistique - P. Gallinari288

Decoder: in the example is 1 dimensional and is 2 dimensional, f is a 1 hidden layer

MLP with gaussian output units and tanh hidden units full arrows: deterministic dashed arrows: sampling

Apprentissage Statistique - P. Gallinari289

Encoder in the example is 1 dimensional and is 2 dimensional, is a 1 hidden layer

MLP with gaussian output units and tanh hidden units

Apprentissage Statistique - P. Gallinari290

Putting it all together

Apprentissage Statistique - P. Gallinari291

Loss Regularization term

| || ∑ 1 log

Reproduction term

log ∑ log

Training Mini batch or pure stochastic

Repeat ← random point or minibatch ← sample from for each ← , ; , , ϕ← , ; , ,

Until convergence

Apprentissage Statistique - P. Gallinari292

Extension VAE offer a general ramework which can be extended to several situations

ConditionalVAE

RecurrentVAE

Semi-supervised ….

Some useful links

Apprentissage Statistique - P. Gallinari293

Books Closest to this course

Cornuéjols A and Miclet L.: Apprentissage Artificiel. Concepts et algorithmes (2nd ed.with revisions and additions - 2006 Eyrolles, Christopher M. Bishop, Pattern Recognition and Machine Learning, Springer (2006)

Most useful Hastie T, Tibshirani R, and Friedman J, (2009). The Elements of Statistical Learning (2nd edition), Springer-Verlag.

pdf version at http://statweb.stanford.edu/~tibs/ElemStatLearn/ David Barber, 2012, Bayesian Reasoning and Machine Learning, Cambridge Univ. Press.

Courses on the web Andrew Ng course on Coursera is one of the most popular

Caltech course: https://work.caltech.edu/telecourse.html

Oxford course; https://www.cs.ox.ac.uk/people/nando.defreitas/machinelearning/

And many others

Software General

Python libraries, e.g. Scikit-learn, http://scikit-learn.org/ and other languages (Matlab, R)

Weka 3: Data Mining Software in Java http://www.cs.waikato.ac.nz/ml/weka/

SVM http://www.csie.ntu.edu.tw/~cjlin/libsvm/

http://svmlight.joachims.org/

Neural networks http://torch.ch/

http://deeplearning.net/software/theano/ propose GPU codes

http://caffe.berkeleyvision.org/ initially proposed for vision applications

Tensorflow, Torch, keras, Big Sur hardware, DIGITS,and Caffe

Test sets UCI machine learning repository

Kaggle Site

…..