un algorithme d’apprentissage parcimonieux maximisantle désaccord
Jean-Francis Roy
13 février 2015
Université Lavalintroductionintroduction

Nous nous attaquons au problème de classification binaire en apprentissage
automatique. Après une introduction au problème à résoudre, nous déduirons de bornes
un algorithme d’apprentissage. En utilisant des techniques d’optimisation, nous
rendrons cet algorithme parcimonieux.

2

plan de la présentation

Introduction
Motivation
Définitions de base et notation
Les méthodes d’ensemble
La C-borne
MinCq : Minimiser la C-borne
CqBoost : un algorithme de type Boosting
Conclusion
3

motivation

applications∙ Prédire si un courriel est un « spam » ou non (en fonction de son contenu)∙ Prédire si un client s’intéressera à un produit (en fonction de ses achats antérieurs)∙ Prédire si un utilisateur cliquera sur une publicité (en fonction de son comportement)∙ Prédire si une protéine et une molécule se lieront ensemble (en fonction de leurdescription)∙ Prédire si une application Android est un « malware » (en fonction de soncomportement)∙ En gros : apprendre une fonction qui catégorise un nouvel élément observé

5

propriété supplémentaire désirée

Cette fonction peut être plus ou moins complexe.
Lorsque le problème le permet, une solution simple (et interprétable) est préférable
dans plusieurs applications.

6

la tâche à résoudre

Est-ce suffisant de construire une fonction de prédiction performante sur les données
que nous avons ?

7

la tâche à résoudre8la tâche à résoudre

Ici, on ne fait aucune erreur.
9

la tâche à résoudre

Ici, on se permet quelques erreurs, mais on devrait mieux généraliser aux futurs
exemples observés.

10

la tâche à résoudre

Nous supposons que les données auxquelles nous avons accès proviennent toutes de lamême distribution.
Nous recherchons une fonction de classification performante sur cette distribution !

11

définitions de base et notation

définitions

Nous considérons les problèmes de classification binaire, où∙ Un exemple est une paire (x, y), où∙ x ∈ X , où X est l’espace d’entrée représentant sa description. Généralement, X = Rd
∙ y ∈ Y, où Y = {−1, +1} est l’étiquette de l’exemple∙ Chaque exemple est indépendamment et identiquement distribué (i.i.d.) d’une
distribution inconnue D sur X × Y.
∙ On dénote cette relation par (x, y) ∼ D∙ L’ensemble d’entraînement est S = {(x1 , y1 ), (x2 , y2 ), . . . , (xm , ym )} ∼ Dm .
∙ Un algorithme d’apprentissage reçoit en entrée l’ensemble S et produit unclassificateur h : X 7→ Y en sortie.
13

le processus

Distribution D

Ensembled’entraînement S

Algorithmed’apprentissage

Exemple x

Classificateur hPrédiction14

le risque

Nous voulons trouver un classificateur h qui minimise le risque, c’est à dire laprobabilité de faire une erreur sur un nouvel exemple tiré selon D.
RD (h) ,=Pr (h(x) 6= y)(x,y)∼DE(x,y)∼DI [h(x) 6= y] ,où I [a] est la fonction indicatrice, qui retourne 1 si le prédicat a est vrai, et 0 autrement.

∙ Mais nous ne connaissons pas D...

15

le risque empiririque

Nous connaissons S ! Le risque empirique est définit comme suit :RS (h) =E(x,y)∼S

I [h(x) 6= y]

1 ∑I [h(xk ) 6= yk ] .
m
m

=

k=1

Mais minimiser le risque empirique ne permet pas de bien généraliser (et c’est
NP-difficile).

16

les méthodes d’ensemble

le vote de majorité

Nous considérons les classificateurs qui prennent la forme d’un vote de majorité
Q-pondéré. Soit H un ensemble de votants de la forme f : X 7→ [−1, 1] et soit Q une
distribution sur H, le vote de majorité BQ est défini par[]
BQ (x) , sgn E f(x) ,f∼Qoù sgn [a] = 1 si a > 0 et −1 autrement.

18

les votes de majorité sont partout∙ Algorithmes de type Bagging∙ Algorithmes de type Boosting∙ Random Forests∙ Bayesian model averaging∙ Support Vector Machines

19exemple jouet

Voici un ensemble de données en deux dimensions. Chaque point rouge est un exemple
négatif, et chaque point bleu un exemple positif.

20

les votants

Voici la frontière de décision d’un ensemble H de 6 votants.

21

le vote de majorité

Combiner ces votants avec une distribution Q soigneusement choisie permet d’obtenir leclassificateur suivant :22

l’effet de groupe∙ Chaque votant est individuellement peu performant∙ Mais la combinaison Q-pondérée peu l’être !

23

en résumé

Étant donné une distribution D sur X × Y et un ensemble de votants H, nous cherchonsune une distribution Q sur H qui minimise
RD (BQ ) =E(x,y)∼DI [BQ (x) 6= y] .

Encore une fois, nous ne connaissons pas D, et minimiser le risque empirique n’est pas
une bonne idée. Cherchons un substitut (surrogate)...

24

la c-bornela marge

La marge MQ d’un vote de majorité sur un exemple (x, y) est définie comme la proportion
du vote accordée à la bonne classe, moins la proportion du vote accordée à la mauvaise
classe. Dans le cas de la classification binaire, on a
MQ (x, y) , y E f(x) .
f∼Q

Lorsque la marge est positive, le vote de majorité ne fait pas d’erreur. Si elle est
négative, celui-ci fait une erreur. Alors,
RD (BQ ) =Pr (MQ (x, y) ≤ 0) .

(x,y)∼D26

les moments de la marge

0

Soit D0 une distribution sur X × Y, posons MDQ la variable aléatoire qui retourne la marge
sur un exemple (x, y) tiré selon D0 .
Les deux premiers moments statistiques de cette variable aléatoire sont :0µ1 (MDQ ) ,0µ2 (MDQ ) ,E

MQ (x, y) ,E

MQ (x, y)2 .

(x,y)∼D0(x,y)∼D027

une borne classique

En appliquant l’inégalité de Markov sur la probabilité que la variable aléatoire MDQ soit
négative, nous obtenons l’inégalité suivante :RD (BQ ) ≤ 1 − µ1 (MDQ ) .

Autrement dit, si on veut un petit risque, les votants doivent être « confiants » en
moyenne, ce qui est possible avec des votants forts individuellement.

28

la c-borne

En appliquant l’inégalité de Cantelli-Chebyshev sur la probabilité qu’elle soit négative,
nous obtenons l’inégalité suivante.
Théorème (La C-borne (Lacasse et al., 2006 ; Laviolette, Marchand et Roy, 2011))
RD (BQ ) ≤ CQD , 1 −µ1 (MDQ )2.
µ2 (MDQ )En d’autres mots, si on veut un petit risque, les votants doivent être confiants en
moyenne et/ou il doivent avoir un grand désaccord (ils doivent faire leurs erreurs à desendroits différents). Également possible avec des votants faibles !
29évaluation empirique

Nous avons généré des votes de majorité en utilisant des ensembles de données, en lesséparant en un ensemble d’entraînement S et un ensemble de test T.
Nous avons exécuté l’algorithme AdaBoost sur S sur des votants faibles (des souches dedécision) et avons récupéré des votes de majorité pendant et après l’exécution del’algorithme.
Pour chaque vote de majorité, nous avons calculé le premier moment de la marge via lamétrique RT (GQ ) , 21 (1 − µ1 (MTQ )), la valeur de CQT , et le risque RT (BQ ).

30évaluation empirique

1.0

0.4

0.8

0.3

0.6

CQT

RT (GQ)

0.5

0.2

0.1

0.0
0.0

0.1

0.2

0.3

0.4

Letter:OQ
Liver
Mushroom
Sonar
Tic-tac-toe
USvotes
Waveform
Wdbc

Adult
BreastCancer
Credit-A
Glass
HabermanHeart
Ionosphere
Letter:AB
Letter:DO
0.4

0.2

0.5

0.0
0.0

0.1

0.2

0.3

0.4

RT (BQ)

RT (BQ))((a) Relation entre 21 1 − µ1 (MTQ ) et RT (BQ ).

(b) Relation entre CQT et RT (BQ ).

0.5

31

estimer la c-borne

La C-borne dépend des deux premiers moments de la marge du vrai risque du vote demajorité. Hors, nous ne pouvons pas calculer ces valeurs, nous devons les estimer
empiriquement.
Nous présentons comment borner ces valeurs en fonction de leur estimation empirique,uniformément pour toute distribution Q.

32

les bornes pac-bayésiennes

Les bornes PAC-bayésiennes permettent de borner le « vrai » risque du classificateur parvote de majorité à partir d’une estimation empirique.
Traditionnellement, le « vrai » premier moment de la marge est borné par son estimation
empirique, puis le résultat est obtenu par l’inégalité RD (BQ ) ≤ 1 − µ1 (MDQ ).
En présence de votants forts, ces bornes peuvent être très serrées.

33les bornes pac-bayésiennes

En présence de votants faibles, nous devons également considérer le second momentde la marge. Le théorème suivant borne le risque du classificateur par vote de majorité
en utilisant les estimations empiriques des deux premiers moments de la marge.

34

les bornes pac-bayésiennes

Théorème
Pour toute distribution D sur X × Y, pour tout ensemble H de votants f : X 7→ [−1, 1],
pour toute distribution a priori P sur H,et pour tout δ ∈ (0, 1], nous avons





Prm 
S∼D 



Pour toute distribution Q sur H,





√ [
)
(
2

√ ]

m
2
S
 ≥ 1−δ ,µ1 (MQ ) − m KL(QkP) + ln δ/2√ [RD (BQ ) ≤ 1 −
√ ] 
m
2
S
µ2 (MQ ) + m 2 KL(QkP) + ln δ/2où KL(QkP) est la divergence Kullback-Leibler entre les distributions Q et P.
35

minimiser la c-borne empirique

Ce résultat nous suggère que de trouver une distribution Q l’estimation empirique CQS dela C-borne devrait donner un vote de majorité ayant une bonne erreur de généralisation.1

1 Le terme KL(QkP) est ignoré dans cette présentation. Laviolette, Marchand et Roy (2011) présentent uneversion de cette borne qui, au prix d’une restriction supplémentaire sur les distributions Q considérées, necontiennent pas de terme KL(QkP).
36

mincq : minimiser la c-borne

minimiser la c-borne empirique

Minimiser la C-borne empirique pose problème : comme nous sommes en présenced’une faible marge, sa forme est très près d’une forme indéterminée 0/0.
CQS = 1 −µ1 (MSQ )2.
µ2 MSQ38

fixer le premier moment

Laviolette, Marchand et Roy (2011) ont montré que de forcer le premier moment µ1 (MSQ )à être égal à une petite valeur µ > 0 ne restreint pas l’ensemble des votes de majorité
possibles.
Pour minimiser la C-borne, nous pouvons donc fixer la marge moyenne à être égale à
une certaine valeur, puis se concentrer sur le deuxième moment (le désaccord).

39

mincq

MinCq2
Étant donné un ensemble H de votants, un ensemble d’entraînement S et une valeurµ > 0, MinCq consiste à trouver la distribution Q sur H dont µ1 (MSQ ) = µ qui minimiseµ2 (MSQ ).

2 La version de MinCq minimisant directement une borne PAC-bayésienne doit également considérer une
restriction supplémentaire sur Q, et nécessite également que H soit symétrique.

40

conversion en programme quadratique

Soit H un ensemble de votants f : X 7→ [−1, 1], H une matrice de m × n éléments telleque Hki = fi (xk ), q un vecteur de n éléments représentant les poids Q sur les votants et y
un vecteur de m éléments contenant les étiquettes sur chaque exemple de l’ensemble S.
Nous avonsm1 ∑µ1 (MSQ ) =MQ (xk , yk )
m
k=1
)
(
m
n
∑
1 ∑
qi fi (xk )
=
yk
m
k=1

=
=

m
n
1 ∑∑

m

i=1

yk qi Hki

k=1 i=1

1 >
y Hq,
m
41

conversion en programme quadratique

et
1 ∑ 2
=
MQ (xk , yk )
m
k=1
(
)2
n
m
∑
1 ∑
=
yk
qi fi (xk )mmµ2 (MSQ )

k=1

=
=

i=1

m
n
n
1 ∑∑∑

m

y2k qi qj Hki Hkj

k=1 i=1 j=1

1 > >q H Hq.
m42

mincq en tant que programme quadratique

Résoudre :argminqsous contraintes :1 > >q H Hqm

1 >y Hq = µ,mq  0,

où 0 est un vecteur de m zéros.

43

résultats empiriques

Nous considérons 45 ensembles de données de classification binaire tirés de la base dedonnées MNIST (Lecun et Cortes).
Nous comparons MinCq en utilisant comme votants de base des noyaux Radial Basis
Function (RBF) à l’algorithme Support Vector Machine (SVM) (Cortes et Vapnik, 1995), un
algorithme à noyaux dont la performance est état de l’art.
Nous comparons ensuite MinCq, cette fois-ci en utilisant des souches de décisionscomme votants de base, avec AdaBoost (E. Schapire et Singer, 1999).

44

résultats empiriques

0.08

0.035

0.07
Risk RT (BQ ) for StumpsAdaBoost

0.040

Risk RT (BQ ) for RbfSVM

0.030
0.025
0.020
0.015
0.010
0.005
0.000
0.000

0.06
0.05
0.04
0.03
0.02
0.01

0.005

0.010

0.015
0.020
0.025
Risk RT (BQ ) for RbfMinCq

0.030

0.035

0.040

0.00
0.00

0.01

0.02

0.03
0.04
0.05
0.06
Risk RT (BQ ) for StumpsMinCq

0.07

0.08

Fig. 2 : Comparaison de MinCq avec SVM (à gauche) et AdaBoost (à droite). Chaque point
représente une paire de risques sur l’ensemble de test. Un point au dessus de la diagonale indiqueune meilleure performance de MinCq.

45maintenant...

MinCq est performant, mais retourne un vote de majorité dense (tous les votants debase sont considérés, et ont pratiquement tous un poids non nul).
Nous désirons créer une version de MinCq qui choisit itérativement les votants à ajouterau vote de majorité, et qui s’arrête avec une solution parcimonieuse.

46

cqboost : un algorithme de type boostingidée

Nous désirons créer une version de MinCq qui choisit itérativement les votants à ajouterau vote de majorité, et qui s’arrête avec une solution parcimonieuse.
Pour ce faire, nous avons besoin d’une manière d’évaluer la qualité des votants (dupoint de vue de MinCq), pour décider d’un ordre dans lequel les considérer.
Nous avons également besoin d’une méthode d’optimisation correspondant à cetteidée : ajouter itérativement les votants dans le problème d’optimisation.

48

la génération de colonnes

La génération de colonnes (column generation) est une technique d’optimisation qui aété utilisée avec succès pour rendre des algorithmes de type Boosting plus « tractables ».
Elle a notamment été utilisée pour développer LPBoost (Demiriz, Kristin P Bennett etShawe-Taylor, 2002) dans le cadre de la programmation linéaire, et CG-Boost (Bi, Zhang
et Kristin P. Bennett, 2004) pour la programmation quadratique.

49

la génération de colonnes - motivation∙ Chaque colonne de la matrice de classification H correspond à un votant de base.
∙ Un sous-ensemble des colonnes de cette matrice pourrait être suffisant pour obtenirl’optimalité du problème d’optimisation sous-jacent.
∙ La pondération Q obtenue est alors plus parcimonieuse (« sparse »)∙ Plus rapide d’exécution∙ Plus facilement interprétable50

la génération de colonnes - idée générale

∙ Étant donné un problème d’optimisation primal, seulement un sous-ensemble desclassificateurs de base est considéré. On appelle ce problème le « restricted masterproblem »∙ Résoudre le problème primal restreint correspond à résoudre une relaxation duproblème dual, où les contraintes reliées aux classificateurs de base non considéréssont absentes∙ En ajoutant itérativement des colonnes à considérer, l’algorithme converge vers
l’optimum du problème d’optimisation original, possiblement avant d’avoir généré
toutes les colonnes∙ Si aucune colonne ne viole la contrainte du problème dual, l’algorithme s’arrête car on
a optimalité51

un problème dual ?

Plusieurs techniques d’optimisation existent pour obtenir une formulation duale d’unproblème d’optimisation.
Généralement, les variables du problème d’optimisation deviennent des contraintes
dans le problème dual, et vice-versa.
Une formulation duale intéressante peut nous aider à voir le problème d’un différent
point de vue.

52

un problème d’optimisation alternatif pour mincq

Construire une formulation duale d’un problème ne donne pas toujours un problèmed’optimisation intéressant. Il faut parfois transformer le problème primal pour obtenir
un dual intéressant.
Introduisons des variables γk égales aux marges sur chaque exemple k.

γk = MQ (xk , yk )= yk E f(x)
f∼Q

= yk

n
∑

qi Hki ,∀k ∈ {1, . . . , m} .

i=1

On a donc
γ = diag(y) H q .

53

un problème d’optimisation alternatif

Résoudre :argminγq,γsous contraintes :

1 >
γ γ
m

1 >
1 γ = µ,m
γ = diag(y) H q
q  0,

où 1 est un vecteur de m uns, et où 0 est un vecteur de m zéros.

54

la méthode de lagrange

Utilisons la méthode de Lagrange pour construire notre formulation duale.
En additionnant une somme pondérée des contraintes à la fonction objectif, nous
obtenons le Lagrangien du problème d’optimisation.
Λ(q, γ , α , β, ξ ) ,1 >γ γ + α > (γγ − diag(y)H q) + β
m

(

)
1 >
1 γ − µ − ξ >q .
m

Les variables α , β et ξ sont nommés les multiplicateurs de Lagrange, variables duales.

55le lagrangien dual

Le Lagrangien dual est le minimum du Lagrangien, en fonction des variables primales q
et γ .
α, β, ξ ) , inf Λ(q, γ , α , β, ξ ) .
ΛD (α
γ
q,γ

56

le problème d’optimisation dual

Le problème d’optimisation dual est obtenu en trouvant le maximum du Lagrangien
dual, sous contrainte que les multiplicateurs de Lagrange associés aux contraintesd’inégalité du problème primal soient non négatives.
Résoudre :α, β, ξ )argmax ΛD (αα ,β,ξξsous contraintes :ξ  0.

57

simplifions le lagrangien dual

Retournons à la définition du Lagrangien dual et évaluons sa valeur. Nous avons

α, β, ξ ) , inf Λ(q, γ , α , β, ξ )
ΛD (α
γ
q,γ
[
(
)
]
1 >
1 >
>
>
= inf
γ γ + α (γγ − diag(y)H q) + β
1 γ −µ −ξ q .
γ
q,γ
m
m
Le minimum en fonction de q et γ est caractérisé par les points où les gradients deΛ(q, γ , α, β, ξ ) par rapport à q et γ sont nuls.

58

de manière visuelle...

Fig. 3 : Graphique d’une fonction à maximiser et d’une contrainte d’égalité (en rouge). Source :Wikipédia.
59

de manière visuelle...

Fig. 4 : Courbes de niveaux (en bleu) d’une fonction à maximiser et d’une contrainte d’égalité (enrouge). Le point tangent où les courbes se recoupent est la solution optimale. Source : Wikipédia.

60

l’optimum du lagrangien

Le point optimal du Lagrangien en fonction de q et γ est donc caractérisé par :H> diag(y) α = −ξξ
et
γ =−

m
β
α − 1.
2
2

Nous connaissons donc maintenant une contrainte d’égalité qui doit être respectée àl’optimum, et la valeur optimale de γ et que nous pouvons remplacer dans l’expressiondu Lagrangien.

61

l’optimum du lagrangien

De laborieux (mais simples) calculs nous donne donc, sous contrainte
H> diag(y) α = −ξξ , que :α, β, ξ ) = inf Λ(q, γ , α , β, ξ )
ΛD (α
γ
q,γ

=−

m >
β
β2
α α − 1>α −− βµ .
42
462

le problème dual de mincq

Résoudre :argmax −α ,β,ξξsous contraintes :

m >
β
β2
α α − 1>α −
− βµ
4
2
4

H> diag(y) α = −ξξ ,ξ  0.

Les variables ξ ne faisant pas partie de la fonction objectif, celles-ci peuvent être retirées.

63le problème dual de mincq

Résoudre :argmax −α ,βsous contraintes :

m >
β
β2
α α − 1>α −
− βµ
4
2
4

>

H diag(y) α  0 .

64

le problème dual de mincq

Nous remarquons que le problème d’optimisation retourne maintenant un vecteur depoids sur les exemples plutôt que sur les votants. Une variable β contrôle un compromis
entre la partie quadratique et la partie linéaire de la fonction objectif.
Le terme de gauche H> diag(y) α de la contrainte d’inégalité peut être vue comme un« score » donné à chaque votant f. Cette mesure est appelée le « edge » d’un votant.
Pour chaque votant i ∈ {0, . . . , n}, nous avons :
m
m
∑
∑
( >
)
H diag(y) α i =αk yk Hki =αk yk fi (xk ) .
k=1

k=1

65

vers un algorithme de génération de colonnes

Cette valeur sera utilisée pour guider le choix du prochain votant à ajouter dans le votede majorité. Celle-ci apparaît également dans d’autres algorithmes de génération decolonne, tels que LPBoost (Demiriz, Kristin P Bennett et Shawe-Taylor, 2002) et
CG-Boost (Bi, Zhang et Kristin P. Bennett, 2004).

66

cqboost

Algorithm 1 CqBoost− Posons t = 0, q un vecteur de n zéros et α un vecteur de m éléments égaux à −1m .
− Soit Ĥ une matrice vide de m lignes.
loop∑m− Choisir la colonne i qui maximise k=1 αk yk Hki .
∑m− If la colonne i ne viole pas la contrainte dual
k=1 αk yk Hki ≤ 0 +  then break.
− Ajouter la colonne i à la matrice Ĥ.
− Mettre à jour q et α avec la solution primale et duale de MinCq.
end loop
return q

67

expérimentations

Sur plusieurs ensembles de données provenant du UCI Machine Learning
Repository (Blake et Merz, 1998), nous comparons CqBoost avec l’algorithme original
MinCq, mais également CqBoost avec LPBoost et CG-Boost.
Nous utilisons dans un premier temps des souches de décision comme votants de base,puis ensuite des noyaux RBF.

68

résultats empiriques : souches de décisions
CqBoost

MinCq

Ens. de données

RT (BQ )Colonnes

RT (BQ )Colonnes

Letter :AB
australianbalancebreastcar
cmc
creditcylinder
ecoli
glass
heart
hepatitishorse
ionosphere
monks
pima
tictactoe
titanic
wine
yeast
zoo

0.00390.18550.02560.04580.1516
0.27850.13910.38520.07140.24300.25930.24680.3696
0.1943
0.23610.25780.32150.22820.16850.30320.0200

160
70
17
83
16
36
84
224
54
80
65
78
152
179
12
74
20
6
95
67
20

0.00510.18550.02560.04580.1516
0.27850.13910.37410.07140.26170.25930.20780.35330.10290.23610.26560.32150.22820.04490.29650.0200

320
280
80
180
120
180
300
700
140
180
260
380
520
680
120
160
180
60
260
160
320

69

résultats empiriques : souches de décisions
CqBoostCG-Boost

LPBoostEns. de données

RT (BQ )Colonnes

RT (BQ )Colonnes

RT (BQ )Colonnes

Letter :AB
australianbalancebreastcar
cmc
creditcylinder
ecoli
glass
heart
hepatitishorse
ionosphere
monks
pima
tictactoe
titanic
wine
yeast
zoo

0.00390.18550.02560.04580.1516
0.27850.13910.38520.07140.24300.25930.24680.3696
0.1943
0.23610.25780.32150.22820.16850.30320.0200

160
70
17
83
16
36
84
224
54
80
65
78
152
179
12
74
20
6
95
67
20

0.0026
0.23480.03850.03720.25690.30840.17680.36300.08330.22430.22960.20780.36960.15430.23150.35940.37790.23090.05620.29920.1000

160
147
40
90
60
113
161
330
70
98
130
190
256
330
114
80
90
18
130
81
152

0.01290.14490.02880.04300.16780.30840.13330.36300.08930.36450.27410.18180.20650.10860.23150.24740.35490.23090.08990.37470.0400

51
1
16
24
14
35
1
1
25
1
38
1
1
63
21
40
1
1
1
1
10

70

résultats empiriques : noyaux rbf
CqBoost

MinCq

Ens. de données

RT (BQ )Colonnes

RT (BQ )Colonnes

Letter :AB
australianbalancebreastcar
cmc
creditcylinder
ecoli
glass
heart
hepatitishorse
ionosphere
monks
pima
tictactoe
titanic
wine
yeast
zoo

0.01030.14490.07370.04580.07180.30430.12750.30370.07140.19630.16300.20780.18480.14860.20370.24740.21290.21640.03370.27360.0400

20
14
10
38
34
9
72
59
40
21
3
39
15
14
43
5
19
15
9
23
18

0.01800.13330.05770.03720.28360.29080.13910.31480.08930.26170.14810.19480.17930.12570.3426
0.26300.34030.23090.02250.33690.0400

778
345
313
350
864
737
345
270
168
107
135
78
184
176
216
384
479
1101
89
742
51

71

résultats empiriques : noyaux rbf
CqBoostCG-Boost

LPBoostEns. de données

RT (BQ )Colonnes

RT (BQ )Colonnes

RT (BQ )Colonnes

Letter :AB
australianbalancebreastcar
cmc
creditcylinder
ecoli
glass
heart
hepatitishorse
ionosphere
monks
pima
tictactoe
titanic
wine
yeast
zoo

0.01030.14490.07370.04580.07180.30430.12750.30370.07140.19630.16300.20780.18480.14860.20370.24740.21290.21640.03370.27360.0400

20
14
10
38
34
9
72
59
40
21
3
39
15
14
43
5
19
15
9
23
18

0.01160.13330.02880.04300.07290.29480.13330.27410.10120.28040.48150.20780.20110.12000.25460.25520.38830.23090.41570.27490.1000

359
295
98
141
567
447
263
194
139
82
114
66
151
142
163
202
340
769
85
422
46

0.01420.14490.44550.04300.02430.30030.13330.27410.50600.21500.48150.19480.36410.14290.50930.25780.04800.32000.04490.27090.1000

26
33
1
9
90
98
62
116
1
44
1
12
8
41
1
69
170
1
20
66
12

72

résultats empiriques : android malware

Sur un ensemble de données de logiciels Android dont l’étiquette est maliciel ou
non-maliciel, nous exécutons CqBoost sur des votants représentant une permission ou
un comportement de l’application.
La figure suivante présente le risque sur l’ensemble d’entraînement ainsi que le risque
sur l’ensemble de test, en fonction du nombre de colonnes (votants) ajoutées dans levote de majorité.

73

résultats empiriques : android malware

0.96

CqBoost accuracy on Android Malware

0.94

Accuracy

0.92
0.90
0.88
0.86
0.84
0.82
0

Training accuracy
Testing accuracy
5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90
Number of features considered74

conclusion

conclusion∙ Nous avons introduit le problème de la classification binaire∙ Nous avons formalisé le problème à résoudre∙ Nous avons introduit les votes de majorité (les méthodes d’ensemble)∙ Nous avons présenté la C-borne, une borne supérieure du risque∙ Nous avons présenté MinCq, un algorithme minimisant cette borne∙ Nous avons présenté CqBoost, une méthode d’ensemble rendant les solutions plus
parcimonieuses

76Questions ?

77

références

Bi, Jinbo, Tong Zhang et Kristin P. Bennett (2004). “Column-generation boosting methods for mixture of kernels”. In :Proceedings of the 2004 ACM SIGKDD international conference on Knowledge discovery and data mining - KDD ’04, p. 521.
Blake, C.L. et C.J. Merz (1998). UCI Repository of machine learning databases.
http ://www.ics.uci.edu/∼mlearn/MLRepository.html : Department of Information et Computer Science, Irvine, CA :University of California.
Cortes, Corinna et Vladimir Vapnik (1995). “Support-Vector Networks”. In : Machine Learning 20.3, p. 273–297.
Demiriz, Ayhan, Kristin P Bennett et John Shawe-Taylor (2002). “Linear programming boosting via column generation”. In :Machine Learning 46.1-3, p. 225–254.
E. Schapire, Robert et Yoram Singer (1999). “Improved Boosting Using Confidence-rated Predictions”. In : Machine Learning
37.3, p. 297–336.
Lacasse, Alexandre et al. (2006). “PAC-Bayes Bounds for the Risk of the Majority Vote and the Variance of the Gibbs Classifier”.
In : NIPS, p. 769–776.
Laviolette, François, Mario Marchand et Jean-Francis Roy (2011). “From PAC-Bayes Bounds to Quadratic Programs for Majority
Votes”. In : ICML, p. 649–656.
Lecun, Yann et Corinna Cortes. “The MNIST database of handwritten digits”. In : url :http://yann.lecun.com/exdb/mnist/.
78