Embed Size (px)
Citation preview
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
