Apprentissage semi-supervisé Extrait de : jye02 jye02

Apprentissage semi-supervisé

Extrait de : http://www.public.asu.edu/~jye02

Position du Problème

m

n

Labels des données(0 ou 1)

Données avec labels

Données sans labels

But : prédire les labels des données sans labels

X y

Apprentissage semi-supervisé

Apprentissage semi-supervisé pour améliorer les performances en combinant les données avec labels (peu) et sans labels (beaucoup)

Classification semi-supervisée (discrimination) : entraîner sur des données avec labels et exploiter les données (beaucoup) sans labels pour améliorer les performances

Clustering semi-supervisé : clustering des données sans labels en s'aidant des données avec labels ou paires de contraintes

ClusteringApprentissageSemi-supervisé

Classification

Hypothèse de classe

Hypothèse de base pour la plupart des algorithmes d'apprentissage semi-supervisés Points proches ont probablement le même label de classe Deux points qui sont connectés par un chemin traversant des régions

de forte densités doivent avoir le même label. Autrement dit les frontières de décision doivent appartenir à des régions de faible densité.

Classification Inductive vs.Transductive

Transductive : Fournit le label uniquement pour les données disponibles non labellisées

La sortie de la méthode n'est pas un classifieur

Inductive: Produit non seulement des labels pour données non labellisées, mais aussi produit un classifieur

Exemple de Classification Semi-Supervisée

.

..

.

.

Exemple de Classification Semi-Supervisée

.

...

. .. ..

.

.

....

.

...

.

Exemple de Classification Semi-Supervisée

.

...

. .. ..

.

.

....

.

...

Deux approches algorithmiques

Méthodes à base de classifieur. On part de l'état initial d'un classifieur et on l'améliore d'une manière itérative : EM semi-supervisé Co-Training Mélange d'information complet ou incomplet de données

Méthodes à base de données. Découvrir la géométrie inhérente dans les données et l'exploiter pour rechercher un bon classifieur : Algorithmes à base de graphes Régularisation manifold Mélange harmonique Régularisation d'information

hypothèses: Connu : un ensemble de classes de données avec labels But : améliorer la classification des exemples dans ces catégories

connues

Clustering Semi-Supervisé

Connaissance du domaine Information partielle Appliquer certaines contraintes (must-links et cannot links)

Approches Search-based Semi-Supervised Clustering

Modifier l'algorithme clustering en y intégrant les contraintes (must-links, cannot-links)

Similarity-based Semi-Supervised Clustering Modifier la mesure de similarités basée sur les contraintes

Combinaison des deux.

.

Clustering Semi-Supervisé : Exemple 1

.

...

. .. ..

.

.

....

.

...

.

Clustering Semi-Supervisé : Exemple 1

.

...

. .. ..

.

.

....

.

...

.

Clustering Semi-Supervisé : Exemple 2

.

...

. .. ..

.

.

....

.

...

.

Clustering Semi-Supervisé : Exemple 2

.

...

. .. ..

.

.

....

.

...

Clustering semi-supervisé :

Entrée : Un ensemble d'objets sans labels, chacun est décrit par un

ensemble d'attributs (numériques ou catégoriels) Une faible connaissance du domaine

Sortie : Partitionnement des objets en k classes

Objectif : Similarité intra-cluster maximum Similarité inter-cluster minimum Une grande consistance entre partition et connaissances du

domaine

Pourquoi clustering semi-supervisé ?

Pourquoi clustering seul insuffiant ? Les classes obtenues peuvent ne pas être ceux demandées Parfois, il y a plusieurs choix de groupements

Pourquoi discrimination seule insuffisante ? Parfois on n'a pas assez de données avec labels

Applications potentielles Bioinformatique (clustering gêne et protéine) Construction de hiérarchies de documents Catégorisation de News/email catégorisation d'Images

Classification semi-supervisée c'est quoi ?

Utilise un faible nombre de données avec labels pour labelliser un grand nombre de données sans labels Labelliser est coûteux

Idée de base Données similaires doivent avoir le même label de classe

Exemples Classification pages Web Classification de documents Classification de protéines

K-Means Semi-Supervisé Seeded K-Means:

Labeled data provided by user are used for initialization: initial center for cluster i is the mean of the seed points having label i.

Seed points are only used for initialization, and not in subsequent steps.

Constrained K-Means: Labeled data provided by user are used to initialize K-Means

algorithm. Cluster labels of seed data are kept unchanged in the cluster

assignment steps, and only the labels of the non-seed data are re-estimated.

Seeded K-Means

Use labeled data to find the initial centroids andthen run K-Means.

The labels for seeded points may change.

Constrained K-Means

Use labeled data to find the initial centroids andthen run K-Means.

The labels for seeded points will not change.

Constrained K-Means Example

Constrained K-Means ExampleInitialize Means Using Labeled Data

xx

Constrained K-Means ExampleAssign Points to Clusters

xx

Constrained K-Means ExampleRe-estimate Means and Converge

xx

COP K-Means COP K-Means [Wagstaff et al.: ICML01] is K-Means with must-link

(must be in same cluster) and cannot-link (cannot be in same cluster) constraints on data points.

Initialization: Cluster centers are chosen randomly, but as each one is chosen any must-link constraints that it participates in are enforced (so that they cannot later be chosen as the center of another cluster).

Algorithm: During cluster assignment step in COP-K-Means, a point is assigned to its nearest cluster without violating any of its constraints. If no such assignment exists, abort.

Illustration

xx

Must-link

Determineits label

Assign to the red class

Illustration

xx

Cannot-link

Determineits label

Assign to the red class

Illustration

xx

Cannot-link

Determineits label

The clustering algorithm fails

Must-link

COP K-Means Algorithm

Other search-based algorithms

Kernel-based semi-supervised clustering, Kulis, et al.

Kernel K-Means

PC K-Means, Basu, et al.

w is the penalty matrix

reward

Overview of spectral clustering

1. Compute the similarity matrix W and D.2. Form 3. Form the matrix Y consisting of the first K

eigenvectors of 4. Normalize Y so that all the rows have unit

lengths.5. Run K-Means on the rows to get the K

clusters. (Ng, Jordan, and Weiss , NIPS’02) or Apply an iterative optimization to get the

partition matrix. (Yu and Shi, ICCV’03)

5.05.0 WDD

5.05.0 WDD

Semi-supervised spectral clustering

0 jiij WW

1 jiij WW

5.05.0 WDD

1. Compute the similarity matrix W and D.2. For each pair of must-link (i,j), assign 3. For each pair of cannot-link (i,j), assign 4. Form the matrix5. Form the matrix Y consisting of the first K

eigenvectors of 6. Normalize Y so that all the rows have unit

lengths.7. Run K-Means on the rows to get the K clusters.

(Ng, Jordan, and Weiss , NIPS’02) or Apply an iterative optimization to get the

partition matrix. (Yu and Shi, ICCV’03)

5.05.0 WDD

Harmonic approach

Paper: Semi-Supervised Learning Using Gaussian Fields and Harmonic functions. Zhu and et al.

Basics Build the weighted graph The labels on the labeled data are fixed Determine the labels of the unlabeled data based on the cluster

Assumption

Intuition

Define a real-valued function f: V R on G with certain properties. Goal: determine the label of unlabeled data by f.

Intuition: Nearby points in the graph have the same label.

ijwLarge weight )()( jfif is small

Optimization problem: Compute optimal f such that E(f) is minimized,subject to the constraint that the values of f on labeled data are fixed.

Intuition

ji

jfifjiwfE,

)()(),()(

1,0:

)()(),()(,

2

Vf

jfifjiwfEji

]1,0[:

)()(),()(,

2

Vf

jfifjiwfEji

Non-differentiable

f: discrete

Determine the labels via thresholding

The values of f on labeled data are fixed.

Main idea

Define a real-valued function f: V R on G with certain properties. Goal: determine the label of unlabeled data by f.

Intuition: Nearby points in the graph have the same label.

ijwLarge weight )()( jfif is small

Optimization problem: Compute optimal f such that E(f) is minimized,subject to the constraint that the values of f on labeled data are fixed.

Harmonic function

0)()(

)()(

fWDfEdf

d

fWDffE T

The optimization problem: The optimal solution f is harmonic:

0f

)(minarg | fEflL ff

WD where is the combinatorial laplacian.

on unlabeled points

Optimal solution in matrix form

uuul

lull

WW

WWW

uu

ll

D

DD

0

0

u

l

f

ff

luluuuuu

uuuuulul

u

l

uuuuul

lullll

fWDWf

fDWfW

f

f

DWW

WDWfDW

1)(

0)(

0)(

Conclusion

Domaine assez vaste : Clustering : K-means, Mixture, HMRF, Kernel K-means Projection : LLE, ISOMAP, Kernel PCA, ...

On doit se consacrer à un champ particulier selon sa sensibilité

Passer aux applications pour mettre en exergue la validité des approches