Transductive Learning CS4780 Machine Learning Fall 2009 Thorsten Joachims Cornell University Outline Transductive Learning Setting Transduction via Graph Cuts Minimum s t cuts Minimum ratio cuts Transductive Support Vector Machines Co Training Transductive Learning Process Sampling Training data select random subset of l examples from DB of size n Z x 1 x l receive labels for these examples positive 1 negative 1 Z x 1 y 1 x l y l Document DB Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Sincerely R Nash Dear Sirs Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Sincerely R Nash Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Goal of Learner predict the labels of the remaining examples Z x x 1 x k Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Sincerely R Nash Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Dear Sirs Opportunity Learning algorithm can study the test examples Z x x 1 x k I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Transductive Learning Process Sampling Training data select random subset of l examples from DB of size n Z x 1 x l receive labels for these examples positive 1 negative 1 Z x 1 y 1 x l y l Document DB Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Sincerely R Nash Dear Sirs Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Sincerely R Nash Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Goal of Learner predict the labels of the remaining examples Z x x 1 x k I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Dear Sirs Sincerely R Nash Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Dear Sirs Opportunity Learning algorithm can study the test examples Z x x 1 x k I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Transductive Learning Process Sampling Training data select random subset of l examples from DB of size n Z x 1 x l receive labels for these examples positive 1 negative 1 Z x 1 y 1 x l y l Document DB Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Sincerely R Nash Dear Sirs Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Sincerely R Nash Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Goal of Learner predict the labels of the remaining examples Z x x 1 x k Sincerely R Nash Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Dear Sirs Opportunity Learning algorithm can study the test examples Z x x 1 x k I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Dear Sirs I am interested in your new inflatable surfboards Could you please send me product and pricing information Sincerely R Nash Example Exploiting the Test Set How would you classify the test set for Term document matrix A nuclear physics D1 1 D2 1 atom pepper basil salt and 1 1 D3 1 1 1 1 D4 1 D5 1 D6 1 1 1 1 1 1 1 Joachims 1999 training set D1 D6 test set D2 D3 D4 D5 Example Exploiting the Test Set How would you classify the test set for Term document matrix A nuclear physics D1 1 D2 1 atom pepper basil salt and 1 1 D3 1 1 1 1 D4 1 D5 1 D6 1 1 1 1 1 1 1 Joachims 1999 training set D1 D6 test set D2 D3 D4 D5 Transductive Support Vector Machines Vapnik Objective maximize margin on both training and test examples Training sample Z x 1 y 1 x l y l Test sample Z x x 1 x k 1 Find solution W y w of 2 min y 1 y k 1 1 subject to min d w w w y1 w x1 b 1 yl w xl b 1 y 1 w x 1 b 1 y k w x k b 1 Simulation Target concept