De la théorie de la compression d’échantillons
aux algorithmes de méta-apprentissage(Adaptation d’une présentation de Pascal Germain)

Benjamin Leblanchttps://benthewhite.github.io/

Université Laval, département d’informatique et de génie logiciel
22 mars 2024

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

1 / 32

Plan

1Préambules

2Théorie de la compression des données
Définition et exemples
Borne de généralisation pour classificateurs binaires
Nouvelle borne de généralisation

3

Deep Reconstruction Machine
Le paradigme du méta-apprentissage
Résultats préliminaires - classification binaire

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

1 / 32

Définitions
Une observation z := (x, y ) ∈ X × Y = Z est une paire variables explicatives - étiquette.

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

2 / 32

Définitions
Une observation z := (x, y ) ∈ X × Y = Z est une paire variables explicatives - étiquette.

Distribution génératrice des données
Chaque observation provient d’une distribution D sur Z.

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

2 / 32

Définitions
Une observation z := (x, y ) ∈ X × Y = Z est une paire variables explicatives - étiquette.

Distribution génératrice des données
Chaque observation provient d’une distribution D sur Z.

Ensemble d’apprentissage
S := { z1 , z2 , . . . , zn } ∼ D n

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

2 / 32

Définitions
Une observation z := (x, y ) ∈ X × Y = Z est une paire variables explicatives - étiquette.

Distribution génératrice des données
Chaque observation provient d’une distribution D sur Z.

Ensemble d’apprentissage
S := { z1 , z2 , . . . , zn } ∼ D n

Algorithme d’apprentissage
A(S) −→ h

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

2 / 32

Définitions
Une observation z := (x, y ) ∈ X × Y = Z est une paire variables explicatives - étiquette.

Distribution génératrice des données
Chaque observation provient d’une distribution D sur Z.

Ensemble d’apprentissage
S := { z1 , z2 , . . . , zn } ∼ D n

Algorithme d’apprentissage

Prédicteur (où hypothèse)

A(S) −→ h

Benjamin Leblanch : X → Y,

Compression et meta-apprentissageh∈H

22 mars 2024

2 / 32

Définitions
Une observation z := (x, y ) ∈ X × Y = Z est une paire variables explicatives - étiquette.

Distribution génératrice des données
Chaque observation provient d’une distribution D sur Z.

Ensemble d’apprentissage
S := { z1 , z2 , . . . , zn } ∼ D n

Algorithme d’apprentissage

Prédicteur (où hypothèse)

A(S) −→ hh : X → Y,h∈HFonction de perteℓ : Y×Y → R
Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

2 / 32

ExempleTâche : prédire le loyer mensuel d’un appartement dans la ville de Québec

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

3 / 32

ExempleTâche : prédire le loyer mensuel d’un appartement dans la ville de Québec

S
ID
1
2
.
.
.
n

x1
Emplacement
Montcalm
Montcalm.
.
.
Sainte-Foy

x2
Nombre de pièce
3 1/2
4 1/2
.
.
.
2 1/2

Benjamin Leblancx3
Chauffé + Éclairé
Oui
Oui
.
.
.
Non

...
...
...
...
.
..
...

xd
Étage
3e
1er
.
.
.
2e

y
Prix
1000
1230
.
.
.
829

Compression et meta-apprentissage

22 mars 2024

3 / 32

ExempleTâche : prédire le loyer mensuel d’un appartement dans la ville de Québec

A(S) = h
S
ID
1
2
.
.
.
n

x1
Emplacement
Montcalm
Montcalm.
.
.
Sainte-Foy

x2
Nombre de pièce
3 1/2
4 1/2
.
.
.
2 1/2

Benjamin Leblancx3
Chauffé + Éclairé
Oui
Oui
.
.
.
Non

...
...
...
...
.
..
...

xd
Étage
3e
1er
.
.
.
2e

y
Prix
1000
1230
.
.
.
829

Compression et meta-apprentissage

22 mars 2024

3 / 32

ExempleTâche : prédire le loyer mensuel d’un appartement dans la ville de Québec

A(S) = h
S
ID
1
2
.
.
.
n

x1
Emplacement
Montcalm
Montcalm.
.
.
Sainte-Foy

x2
Nombre de pièce
3 1/2
4 1/2
.
.
.
2 1/2

x3
Chauffé + Éclairé
Oui
Oui
.
.
.
Non

...
...
...
...
.
..
...

xd
Étage
3e
1er
.
.
.
2e

y
Prix
1000
1230
.
.
.
829

H : les différents arbres de décision qui existent
Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

3 / 32

Le problème de la généralisation
L’algorithme d’apprentissage se sert uniquement de l’ensemble d’entrainement S :n1X
LbS (h) :=ℓ(h(xi ), yi )ni=1Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

4 / 32

Le problème de la généralisation
L’algorithme d’apprentissage se sert uniquement de l’ensemble d’entrainement S :n1X
LbS (h) :=ℓ(h(xi ), yi )ni=1

Le but : Minimiser la perte en moyenne sur D
LD (h) := E ℓ(h(xi ), yi )z∼DBenjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

4 / 32

Le problème de la généralisation
L’algorithme d’apprentissage se sert uniquement de l’ensemble d’entrainement S :n1X
LbS (h) :=ℓ(h(xi ), yi )ni=1

Le but : Minimiser la perte en moyenne sur D
LD (h) := E ℓ(h(xi ), yi )z∼D

Bornes de généralisation PAC (Probablement Approximativement Correct)

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

4 / 32

Le problème de la généralisation
L’algorithme d’apprentissage se sert uniquement de l’ensemble d’entrainement S :n1X
LbS (h) :=ℓ(h(xi ), yi )ni=1

Le but : Minimiser la perte en moyenne sur D
LD (h) := E ℓ(h(xi ), yi )z∼D

Bornes de généralisation PAC (Probablement Approximativement Correct)≪

Avec probabilité au moins “ 1−δ ”, la perte de h sera au plus “ ε(·, . . . , ·) ” ≫Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

4 / 32

Le problème de la généralisation
L’algorithme d’apprentissage se sert uniquement de l’ensemble d’entrainement S :n1X
LbS (h) :=ℓ(h(xi ), yi )ni=1

Le but : Minimiser la perte en moyenne sur D
LD (h) := E ℓ(h(xi ), yi )z∼D

Bornes de généralisation PAC (Probablement Approximativement Correct)≪

Avec probabilité au moins “ 1−δ ”, la perte de h sera au plus “ ε(·, . . . , ·) ” ≫Pr n LD (h) ≤ ε(LbS (h), n, δ, . . .) ≥ 1−δS∼DBenjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

4 / 32

Apprentissage PAC - En bref
PAC (Probablement Approximativement Correct)
Avec probabilité au moins “ 1−δ ”, la perte de h sera au plus “ ε(·, . . . , ·) ”b≤
Pr n LD (h)ε(LS (h), n, δ, . . .) ≥ 1−δ
S∼D

Hypothèse unique h :Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

5 / 32

Apprentissage PAC - En bref
PAC (Probablement Approximativement Correct)
Avec probabilité au moins “ 1−δ ”, la perte de h sera au plus “ ε(·, . . . , ·) ”b≤
Pr n LD (h)ε(LS (h), n, δ, . . .) ≥ 1−δ
S∼D

Hypothèse unique h :LD (h) ≤ LbS (h) +Benjamin Leblanc

Compression et meta-apprentissageq

22 mars 2024

12n log1
δ

.

5 / 32

Apprentissage PAC - En bref
PAC (Probablement Approximativement Correct)
Avec probabilité au moins “ 1−δ ”, la perte de h sera au plus “ ε(·, . . . , ·) ”b≤
Pr n LD (h)ε(LS (h), n, δ, . . .) ≥ 1−δ
S∼D

Hypothèse unique h :LD (h) ≤ LbS (h) +q12n log1
δ.

Classe finie d’hypothèses H :Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

5 / 32

Apprentissage PAC - En bref
PAC (Probablement Approximativement Correct)
Avec probabilité au moins “ 1−δ ”, la perte de h sera au plus “ ε(·, . . . , ·) ”b≤
Pr n LD (h)ε(LS (h), n, δ, . . .) ≥ 1−δ
S∼D

Hypothèse unique h :LD (h) ≤ LbS (h) +q12n log

1
δ



|H|
δ



.

Classe finie d’hypothèses H :r∀h ∈ H, LD (h) ≤ LbS (h) +Benjamin Leblanc

Compression et meta-apprentissage

1
2n log

22 mars 2024



5 / 32

Apprentissage PAC - En bref
PAC (Probablement Approximativement Correct)
Avec probabilité au moins “ 1−δ ”, la perte de h sera au plus “ ε(·, . . . , ·) ”b≤
Pr n LD (h)ε(LS (h), n, δ, . . .) ≥ 1−δ
S∼D

Hypothèse unique h :LD (h) ≤ LbS (h) +q12n log

1
δ



|H|
δ



.

Classe finie d’hypothèses H :r∀h ∈ H, LD (h) ≤ LbS (h) +12n logClasse dénombrable d’hypothèses hi , avec avec probabilité a priori p(hi ) :Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

5 / 32

Apprentissage PAC - En bref
PAC (Probablement Approximativement Correct)
Avec probabilité au moins “ 1−δ ”, la perte de h sera au plus “ ε(·, . . . , ·) ”b≤
Pr n LD (h)ε(LS (h), n, δ, . . .) ≥ 1−δ
S∼D

Hypothèse unique h :LD (h) ≤ LbS (h) +q12n log

1
δ



|H|
δ



1
p(h)δ





.

Classe finie d’hypothèses H :r∀h ∈ H, LD (h) ≤ LbS (h) +Classe dénombrable d’hypothèses hi , avec avec probabilité a priori p(hi ) r:∀h ∈ H, LD (h) ≤ LbS (h) +Benjamin Leblanc

Compression et meta-apprentissage

1
2n log1
2n log

22 mars 2024



5 / 32

Apprentissage PAC - En bref
PAC (Probablement Approximativement Correct)
Avec probabilité au moins “ 1−δ ”, la perte de h sera au plus “ ε(·, . . . , ·) ”b≤
Pr n LD (h)ε(LS (h), n, δ, . . .) ≥ 1−δ
S∼D

Hypothèse unique h :LD (h) ≤ LbS (h) +q12n log

1
δ



|H|
δ



1
p(h)δ





.

Classe finie d’hypothèses H :r∀h ∈ H, LD (h) ≤ LbS (h) +Classe dénombrable d’hypothèses hi , avec avec probabilité a priori p(hi ) r:∀h ∈ H, LD (h) ≤ LbS (h) +12n log1
2n logClasse indénombrable d’hypothèses : Dimension VC, Complexité de Rademacher,
PAC-Bayes...
Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

5 / 32

Plan

1Préambules

2Théorie de la compression des données
Définition et exemples
Borne de généralisation pour classificateurs binaires
Nouvelle borne de généralisation

3

Deep Reconstruction Machine
Le paradigme du méta-apprentissage
Résultats préliminaires - classification binaire

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

5 / 32

Plan

1Préambules

2Théorie de la compression des données
Définition et exemples
Borne de généralisation pour classificateurs binaires
Nouvelle borne de généralisation

3

Deep Reconstruction Machine
Le paradigme du méta-apprentissage
Résultats préliminaires - classification binaire

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

5 / 32

Généalogie
Initialisation :Littlestone et Warmuth 1986 :“Relating Data Compression and Learnability”

The Set Covering Machine (SCM) et ses variants
Marchand et Shawe-Taylor 2002 : “The Set Covering Machine”
Marchand et Sokolova 2005 : “Learning with Decision Lists of Data-Dependent Features”
Laviolette et al. 2005 : “Margin-Sparsity Trade-Off for the Set Covering Machine”
Drouin et al. 2014 : “Learning interpretable models of phenotypes from whole genome sequences with
the Set Covering Machine”
Godon et al. 2022 : “RandomSCM: interpretable ensembles of sparse classifiers tailored for omics
data”

AutresCampi et Garatti 2023 : “Compression, Generalization and Learning”
Paccagnan et al. 2023 : “The Pick-to-Learn Algorithm: Empowering Compression for Tight
Generalization Bounds and Improved Post-training Performance”
Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

6 / 32

Motivations

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

7 / 32

Motivations

Classe indénombrable d’hypothèses : nouvel angle d’attaque

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

7 / 32

Motivations

Classe indénombrable d’hypothèses : nouvel angle d’attaqueClasse dénombrable d’hypothèses : le terme |H| peut être très pénalisantBenjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

7 / 32

Motivations

Classe indénombrable d’hypothèses : nouvel angle d’attaqueClasse dénombrable d’hypothèses : le terme |H| peut être très pénalisant
r
 
1
b
∀h ∈ H, LD (h) ≤ LS (h) + 2nlog |H|δ

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

7 / 32

Motivations

Classe indénombrable d’hypothèses : nouvel angle d’attaqueClasse dénombrable d’hypothèses : le terme |H| peut être très pénalisant
Permet de n’utiliser qu’un sous-ensemble des observations
r
 
1
b
∀h ∈ H, LD (h) ≤ LS (h) + 2nlog |H|δ

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

8 / 32

Définitions

Un prédicteur h peut être compressé hiµ si obtenu par un nouvel algorithme R dépendant dedeux sources d’informations complémentaires :Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

9 / 32

Définitions

Un prédicteur h peut être compressé hiµ si obtenu par un nouvel algorithme R dépendant dedeux sources d’informations complémentaires :Un ensemble de compression Si , un sous-ensemble de S :Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

9 / 32

ExempleTâche : prédire le loyer mensuel d’un appartement dans la ville de Québec

A(S) = h
S
ID
1
2
.
.
.
n

x1
Emplacement
Montcalm
Montcalm.
.
.
Sainte-Foy

x2
Nombre de pièce
3 1/2
4 1/2
.
.
.
2 1/2

Benjamin Leblancx3
Chauffé + Éclairé
Oui
Oui
.
.
.
Non

...
...
...
...
.
.
.
...

xd
Étage
3e
1er
.
.
.
2e

y
Prix
1000
1230
.
.
.
829

Compression et meta-apprentissage

22 mars 2024

10 / 32

ExempleTâche : prédire le loyer mensuel d’un appartement dans la ville de Québec

A(S) = hS i = S {1,29,263,1902}
ID
1
29
263
1902

x1
Emplacement
Montcalm
Montcalm
Montcalm
Sainte-Foy

x2
Nombre de pièce
3 1/2
4 1/2
4 1/2
2 1/2

Benjamin Leblancx3
Chauffé + Éclairé
Oui
Oui
Oui
Non

...
...
...
...
...
...

xd
Étage
3e
1er
1er
2e

y
Prix
1442
1227
1003
832

Compression et meta-apprentissage

22 mars 2024

11 / 32

Definitions

Un prédicteur compressé hiµ est un prédicteur obtenu par un algorithme R dépendant dedeux sources d’informations complémentaires :Un ensemble de compression Si , un sous-ensemble de S :Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

12 / 32

Definitions

Un prédicteur compressé hiµ est un prédicteur obtenu par un algorithme R dépendant dedeux sources d’informations complémentaires :Un ensemble de compression Si , un sous-ensemble de S :Un message µ ∈ Mi qui contient de l’information additionnelle pour décrire hiµ .

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

12 / 32

Profondeur ?
Nombre de feuilles ?

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

13 / 32

ExempleTâche : prédire le loyer mensuel d’un appartement dans la ville de Québec

A(S) = hS i = S {1,29,263,1902}
ID
1
29
263
1902

x1
Emplacement
Montcalm
Montcalm
Montcalm
Sainte-Foy

x2
Nombre de pièce
3 1/2
4 1/2
4 1/2
2 1/2

Benjamin Leblancx3
Chauffé + Éclairé
Oui
Oui
Oui
Non

...
...
...
...
...
...

xd
Étage
3e
1er
1er
2e

y
Prix
1442
1227
1003
832

Compression et meta-apprentissage

22 mars 2024

14 / 32

Definitions

Un prédicteur compressé hiµ est un prédicteur obtenu par un algorithme R dépendant dedeux sources d’informations complémentaires :Un ensemble de compression Si , un sous-ensemble de S :Un message µ ∈ Mi qui contient de l’information additionnelle pour décrire hiµ .

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

15 / 32

Definitions

Un prédicteur compressé hiµ est un prédicteur obtenu par un algorithme R dépendant dedeux sources d’informations complémentaires :Un ensemble de compression Si , un sous-ensemble de S :Un message µ ∈ Mi qui contient de l’information additionnelle pour décrire hiµ .
Étant donné Si ∈ Z |i| et µ ∈ Mi , une fonction de reconstruction R donne un prédicteur :hiµ = R(Si , µ) .

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

15 / 32

ExempleTâche : prédire le loyer mensuel d’un appartement dans la ville de Québec

A(S) = hR(S i ,µ) = h

S i = S {1,29,263,1902}
ID
1
29
263
1902

x1
Emplacement
Montcalm
Montcalm
Montcalm
Sainte-Foy

x2
Nombre de pièce
3 1/2
4 1/2
4 1/2
2 1/2

Benjamin Leblancx3
Chauffé + Éclairé
Oui
Oui
Oui
Non

...
...
...
...
...
...

xd
Étage
3e
1er
1er
2e

y
Prix
1442
1227
1003
832

Compression et meta-apprentissage

22 mars 2024

16 / 32

Examples de prédicteurs facile à compresser

SVM : Support Vector Machine (marge rigide)
L’algorithme d’apprentissage du SVM agit comme sa
propre fonction de reconstruction
SVM(S) = hiµ = SVM(Si )with Si = {vecteurs de support}
and µ = ∅Image : Wikipedia

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

17 / 32

Examples de prédicteurs facile à compresser
SCM : Set Covering Machine (Marchand et Shawe-Taylor 2002)→ conjonction variables explicatives booléennes créées
Le SCM apprend des features bi,j : X → {−1, +1}
Chaque variable explicative est une boule bi,j ∈ B définie parun centre (xi , yi ) et une bordure (xj , yj ) :(+yi if ∥x − xi ∥ ≤ ∥xi − xj ∥ + ϵ·yi ,bi,j (x) :=−yi sinon.
Le SCM apprend une conjonction comme classifieur :^hiµ (x) :=bi,j (x) (où +1 ≡ Vrai −1 ≡ Faux)bi,j ∈B

avec Si = {les points ≪ centre ≫ et ≪ bordure ≫}and µ = {les indices parmi Si }Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

18 / 32Plan

1Préambules

2Théorie de la compression des données
Définition et exemples
Borne de généralisation pour classificateurs binaires
Nouvelle borne de généralisation

3

Deep Reconstruction Machine
Le paradigme du méta-apprentissage
Résultats préliminaires - classification binaire

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

18 / 32

Bornes de généralisation pour des classifieurs binaires compressésµÉtant donné hiµ : X → {−1, +1}, et L01
D (hi ) =Benjamin LeblancE(x,y )∼D

I (hiµ (x) ̸= y ) la perte zéro-un.

Compression et meta-apprentissage

22 mars 2024

19 / 32

Bornes de généralisation pour des classifieurs binaires compressésµÉtant donné hiµ : X → {−1, +1}, et L01
D (hi ) =E
(x,y )∼D

I (hiµ (x) ̸= y ) la perte zéro-un.

Théorème (Marchand et Sokolova 2005 ; Laviolette et al. 2005)

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

19 / 32

Bornes de généralisation pour des classifieurs binaires compressésµÉtant donné hiµ : X → {−1, +1}, et L01
D (hi ) =E
(x,y )∼D

I (hiµ (x) ̸= y ) la perte zéro-un.

Théorème (Marchand et Sokolova 2005 ; Laviolette et al. 2005)
Soit R une fonction de reconstruction, PMi une distribution sur les messages, et δ ∈ (0, 1].
Avec forte probabilité (≥ 1 − δ) sur S ∼ D n :Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

19 / 32

Bornes de généralisation pour des classifieurs binaires compressésµÉtant donné hiµ : X → {−1, +1}, et L01
D (hi ) =E
(x,y )∼D

I (hiµ (x) ̸= y ) la perte zéro-un.

Théorème (Marchand et Sokolova 2005 ; Laviolette et al. 2005)
Soit R une fonction de reconstruction, PMi une distribution sur les messages, et δ ∈ (0, 1].
Avec forte probabilité (≥ 1 − δ) sur S ∼ D n : ∀i ∈ In , µ ∈ Mi :LD (hiµ ) ≤ 1− exp
01



 

 


−1
n−|i|
n
1
ln
+ ln
+ln
n−|i|−kSic
PMi (µ) · ξ(|i|) · δ
kSic
|i|

µ
6
−2
où kSic := |ic |Lb01
Sic (hi ) est le nombre d’erreurs sur Sic := S \ Si et ξ(a) := π 2 (a + 1) .

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

19 / 32

Bornes non-triviales !

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

20 / 32Plan

1Préambules

2Théorie de la compression des données
Définition et exemples
Borne de généralisation pour classificateurs binaires
Nouvelle borne de généralisation

3

Deep Reconstruction Machine
Le paradigme du méta-apprentissage
Résultats préliminaires - classification binaire

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

20 / 32

Motivation

La question
Peut-on apprendre une fonction de reconstruction R(i, µ) pour construire un réseau deneurones ?

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

21 / 32

Motivation

La question
Peut-on apprendre une fonction de reconstruction R(i, µ) pour construire un réseau deneurones ?
Il faudrait alors adapter nos résultats de telle sorte que :Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

21 / 32

Motivation

La question
Peut-on apprendre une fonction de reconstruction R(i, µ) pour construire un réseau deneurones ?
Il faudrait alors adapter nos résultats de telle sorte que :1

Les pertes à valeurs continues sont considérées

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

21 / 32

Motivation

La question
Peut-on apprendre une fonction de reconstruction R(i, µ) pour construire un réseau deneurones ?
Il faudrait alors adapter nos résultats de telle sorte que :1

Les pertes à valeurs continues sont considérées2

Une quantité indénombrable de message

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

21 / 32

Nouvelle borne pour une quantité indénombrable de mesages
PAC-Bayes à la rescousse !
On considère maintenant une distribution a posteriori QM sur l’ensemble (potentiellement
continu) des messages M.

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

22 / 32

Nouvelle borne pour une quantité indénombrable de mesages
PAC-Bayes à la rescousse !
On considère maintenant une distribution a posteriori QM sur l’ensemble (potentiellement
continu) des messages M.

Théorème
Soit R, une fonction de reconstruction, PM une distribution a priori sur les messages, etδ ∈ (0, 1]. Avec forte probabilité (≥ 1 − δ) sur S ∼ D n :Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

22 / 32

Nouvelle borne pour une quantité indénombrable de mesages
PAC-Bayes à la rescousse !
On considère maintenant une distribution a posteriori QM sur l’ensemble (potentiellement
continu) des messages M.

Théorème
Soit R, une fonction de reconstruction, PM une distribution a priori sur les messages, etδ ∈ (0, 1]. Avec forte probabilité (≥ 1 − δ) sur S ∼ D n :∀i ∈ In , QM sur M :E LD (hiµ )
µ∼Q
M


 


1
σ2
n
1
µ
b
KL(QM ∥PM ) ++ ln+ln≤ E LSic (hi ) + p
.
µ∼QM
2
|i|
ξ(|i|) · δn − |i|Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

22 / 32Plan

1Préambules

2Théorie de la compression des données
Définition et exemples
Borne de généralisation pour classificateurs binaires
Nouvelle borne de généralisation

3

Deep Reconstruction Machine
Le paradigme du méta-apprentissage
Résultats préliminaires - classification binaire

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

22 / 32Plan

1Préambules

2Théorie de la compression des données
Définition et exemples
Borne de généralisation pour classificateurs binaires
Nouvelle borne de généralisation

3

Deep Reconstruction Machine
Le paradigme du méta-apprentissage
Résultats préliminaires - classification binaire

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

22 / 32

Le méta-apprentissage ?

IdéeBenjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

23 / 32

Le méta-apprentissage ?

IdéeConsidérer plusieurs tâches simultanément

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

23 / 32

Le méta-apprentissage ?

IdéeConsidérer plusieurs tâches simultanément
Motivations

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

23 / 32

Le méta-apprentissage ?

IdéeConsidérer plusieurs tâches simultanément
Motivations
Partage de connaissance entre les tâches

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

23 / 32

Le méta-apprentissage ?

IdéeConsidérer plusieurs tâches simultanément
Motivations
Partage de connaissance entre les tâches
Davantage d’exemple par entrainement

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

23 / 32

Définitions
Méta-entrainement
S := {S (1) , S (2) , . . . , S (m) } tel que S (i) ∼ D (i)Benjamin Leblanc

Compression et meta-apprentissage

ni.

22 mars 2024

24 / 32

Définitions
Méta-entrainement
S := {S (1) , S (2) , . . . , S (m) } tel que S (i) ∼ D (i)ni.

AlgorithmeS ) −→ (C, R)
A (SBenjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

24 / 32

Définitions
Méta-entrainement
S := {S (1) , S (2) , . . . , S (m) } tel que S (i) ∼ D (i)ni.

AlgorithmeS ) −→ (C, R)
A (SFonction de compression
C(S) −→ (i, µ)Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

24 / 32

Définitions
Méta-entrainement
S := {S (1) , S (2) , . . . , S (m) } tel que S (i) ∼ D (i)ni.

AlgorithmeS ) −→ (C, R)
A (SFonction de compression
C(S) −→ (i, µ)Fonction de reconstruction
R(i, µ) −→ θBenjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

24 / 32

Définitions
Méta-entrainement
S := {S (1) , S (2) , . . . , S (m) } tel que S (i) ∼ D (i)ni.

AlgorithmeS ) −→ (C, R)
A (SFonction de compression
C(S) −→ (i, µ)Fonction de reconstruction
R(i, µ) −→ θPrédicteurhθ (x) −→ yBenjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

24 / 32

Définitions
Méta-entrainement
S := {S (1) , S (2) , . . . , S (m) } tel que S (i) ∼ D (i)ni.

AlgorithmeS ) −→ (C, R)
A (SFonction de compression

Combiner meta-learning et sample compression :C(S) −→ (i, µ)Fonction de reconstruction
R(i, µ) −→ θPrédicteurhθ (x) −→ yBenjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

24 / 32Plan

1Préambules

2Théorie de la compression des données
Définition et exemples
Borne de généralisation pour classificateurs binaires
Nouvelle borne de généralisation

3

Deep Reconstruction Machine
Le paradigme du méta-apprentissage
Résultats préliminaires - classification binaire

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

24 / 32Résultats préliminaires

Tâche #1

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

25 / 32Résultats préliminaires

Tâche #1
Non-linéairement séparable

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

25 / 32Résultats préliminaires

Tâche #1
Non-linéairement séparable
Translations / rotations /homothéties

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

25 / 32Résultats préliminaires

Tâche #1
Non-linéairement séparable
Translations / rotations /homothéties
Le prédicteur
h : réseau de neurones simple

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

25 / 32Résultats préliminaires

Tâche #1
Non-linéairement séparable
Translations / rotations /homothéties
Le prédicteur
h : réseau de neurones simple
θ = (w, b)

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

25 / 32Résultats préliminaires

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

26 / 32Résultats préliminaires

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

27 / 32Résultats préliminaires

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

28 / 32Résultats préliminaires

Tâche #2

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

29 / 32Résultats préliminaires

Tâche #2
Entrée de dimension 28x28

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

29 / 32Résultats préliminaires

Tâche #2
Entrée de dimension 28x28
Le prédicteur
h : séparateur linéaire
h(x) = sgn(w · x + b)

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

29 / 32Résultats préliminaires

Tâche #2
Entrée de dimension 28x28
Le prédicteur
h : séparateur linéaire
h(x) = sgn(w · x + b)
θ = (Wi , bi )2i=1

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

29 / 32Résultats préliminaires

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

30 / 32Résultats préliminaires

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

31 / 32

Conclusion

Merci de votre écoute :) !

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

32 / 32

References I
Campi, Marco C. et Simone Garatti (2023). “Compression, Generalization and Learning”. In : JMLR abs/2301.12767.
Drouin, Alexandre, Sébastien Giguere, Vladana Sagatovich, Maxime Déraspe, François Laviolette,
Mario Marchand et Jacques Corbeil (2014). “Learning interpretable models of phenotypes from whole genome
sequences with the Set Covering Machine”. In : arXiv preprint arXiv:1412.1074.
Godon, Thibaud, Pier-Luc Plante, Baptiste Bauvin, Elina Francovic-Fontaine, Alexandre Drouin et
Jacques Corbeil (2022). “RandomSCM: interpretable ensembles of sparse classifiers tailored for omics data”. In :CoRR abs/2208.06436. doi : 10.48550/ARXIV.2208.06436. arXiv : 2208.06436. url :https://doi.org/10.48550/arXiv.2208.06436.
Laviolette, François, Mario Marchand et Mohak Shah (2005). “Margin-Sparsity Trade-Off for the Set Covering
Machine”. In : ECML. T. 3720. Lecture Notes in Computer Science. Springer, p. 206-217.
Littlestone, Nick et Manfred K. Warmuth (1986). “Relating Data Compression and Learnability”. In : Technical
Report.
Marchand, Mario et John Shawe-Taylor (2002). “The Set Covering Machine”. In : JMLR 3.
Marchand, Mario et Marina Sokolova (2005). “Learning with Decision Lists of Data-Dependent Features”. In : JMLR
6.
Paccagnan, Dario, Marco C. Campi et Simone Garatti (2023). “The Pick-to-Learn Algorithm: Empowering
Compression for Tight Generalization Bounds and Improved Post-training Performance”. In : NeurIPS.

Benjamin Leblanc

Compression et meta-apprentissage

22 mars 2024

32 / 32