Introduction to Machine Learning - Carnegie Mellon School ...

1 1 Introduction to Machine LearningActive LearningBarnab s P czos2 CreditsSome of the slides are taken from Nina applications: massive amountsof raw a tiny fractioncan be annotated by human of webpagesImagesClassic Supervised Learning Paradigm is Insufficient NowadaysSensor measurements4 Modern applications: massive amountsof raw need techniques that minimize need for expert/human intervention=> Active LearningModern ML: New Learning ApproachesThe Large Synoptic Survey Telescope15 Terabytes of data .. every night5 Active Learning Intro Batch Active Learning vs Selective Sampling Active Learning Exponential Improvement on # of labels Sampling bias: Active Learning can hurt performance Active Learning with SVM Gaussian Processes Regression Properties of Multivariate Gaussian distributions Ridge regression GP = Bayesian Ridge Regression + Kernel trick Active Learning with Gaussian ProcessesContents6 Two faces of active Learning .

2 SanjoyDasgupta. 2011. Active Learning . Bur Settles. 2012. Active Learning . Balcan-Urner. Encyclopedia of Algorithms. 2015 Additional resources7A Label for that ExampleRequest for the Label of an ExampleA Label for that ExampleRequest for the Label of an ExampleData SourceA set of Unlabeled examples.. Algorithm outputs a classifier DLearning AlgorithmExpert Learner can choose specific examples to be labeled. Goal:use fewer labeled examples[pick informativeexamples to be labeled].Underlying data distr. Active Learning8 Unlabeled example 3 Unlabeled example 1 Unlabeled example 2 Request for label or let it go?Data SourceLearning AlgorithmExpert Request labelA label 1for example 1 Let it goAlgorithm outputs a classifier DRequest labelA label 3for example 3 Selective sampling AL (Online AL): stream of unlabeled examples, when each arrives make a decision to ask for label or not.

3 Goal: use fewer labeled examples[pick informativeexamples to be labeled].Underlying data distr. Sampling Active Learning9 Need to choose the label requests carefully, to get informativelabels. Guaranteed to output a relatively good classifier for most Learning problems. Doesn t make too many label a lot less than passive Makes a Good Active Learning Algorithm?10 YES! (sometimes) We often need far fewer labels for active Learning than for passive. This is predicted by theory and has been observed in adaptive querying really do better than passive/random sampling?11 Thresholdfnson the real line:w+-Exponential (x) = 1(x w),C = {hw: w 2R} How can we recover the correct labels with Nqueries?- Do binary search (query at half)! Active:only O(log1/ ) supervised: (1/ )labels to find an -accurate threshold.

4 +-Active AlgorithmJust need O(log N)labels! N=O(1/ )we are guaranteed to get a classifier of error . Get N unlabeledexamples Output a classifier consistent with the N inferred adaptive querying help? [CAL92, Dasgupta04]12 Uncertainty sampling in SVMs common and quite useful in practice. At any time during the alg., we have a current guess wtof the separator: the max-margin separator of all labeled points so far. Request the label of the example closest to the current , [Tong & Koller, ICML 2000; Jain, Vijayanarasimhan& Grauman, NIPS 2010; SchohonCohn, ICML 2000]Active SVM AlgorithmActive SVM13 Active SVMseems to be quite useful in practice. Find the max-margin separator of all labeled points so far. Request the label of the example closest to the current separator: minimizing.

5 [Tong & Koller, ICML 2000; Jain, Vijayanarasimhan& Grauman, NIPS 2010]Algorithm (batch version)InputSu={x1, ..,xmu} drawn fromthe underlying source DStart: query for the labels of a few random = , ..,(highest uncertainty)Active SVM14 Uncertainty sampling works However, we need to be very veryverycareful!!! Myopic, greedy techniques can suffer from sampling bias.(The active Learning algorithm samples from a different (x,y) distribution than the true data) A bias created because of the querying strategy; as time goes on the sample is less and less representative of the true data source.[Dasgupta10]DANGER!!!15 DANGER!!! Main tension: want to choose informative points, but also want to guarantee that the classifier we output does well on true random examples from the underlying distribution.

6 Observed in practice too!!!!16 Interesting open question to analyze under what conditions they are Interesting Active Learning Techniques used in Practice17 Centroid of largest unsampledcluster[Jaime G. Carbonell]Density-Based Sampling18 Closest to decision boundary (Active SVM)[Jaime G. Carbonell]Uncertainty Sampling19 Maximally distant from labeled x s[Jaime G. Carbonell]Maximal Diversity Sampling20 Uncertainty + Diversity criteriaDensity + uncertainty criteria[Jaime G. Carbonell]Ensemble-Based Possibilities21 Active Learning could be really helpful, could provide exponential improvements in label complexity (both theoretically and practically)! Need to be very careful due to sampling bias. Common heuristics ( , those based on uncertainty sampling). What You Should Knowso far22 Gaussian Processes for Regression23 of these slides are taken from D.

7 Lizotte, R. Parr, C. GuesterinAdditional resources24 Nonmyopic Active Learning of Gaussian Processes: An Exploration Exploitation Approach. C. Guestrin, ICML 2007 Near-Optimal Sensor Placements in Gaussian Processes: Theory, Efficient Algorithms and Empirical , A. Singh, and C. Guestrin, Journal of Machine Learning Research 9 (2008) Bayesian Active Learning for Posterior Estimation, Kandasamy, K., Schneider, J., and Poczos, B, International Joint Conference on Artificial Intelligence (IJCAI), 2015 Additional resources25 Why GPs for Regression?Motivation:All the above regression method give point estimates. We would like a method that could also provide confidence during the methods:Linear regression, multilayer precpetron, ridge regression, support vector regression, kNNregression, Application in Active Learning :This method can be used for active Learning : query the next point and its label where the uncertainty is the highest26 Here s where the function will most likely be.

8 (expected function) Here are some examplesof what it might look like. (sampling from the posterior distribution [blue, red, green functions) Here is a prediction of what you ll see if you evaluate your function at x , with confidenceGPs can answer the following questions:Why GPs for Regression?27 Properties of Multivariate Gaussian Distributions281D Gaussian DistributionParameters Mean, Variance, 229 Multivariate Gaussian30 A 2-dimensional Gaussian is defined by a mean vector = [ 1, 2] a covariance matrix:where i,j2= E[ (xi i) (xj j) ]is (co)variance Note: is symmetric, positive semi-definite : x: xT x 0 22,222,121,221,1 Multivariate Gaussian31 Multivariate Gaussianexamples = (0,0) Gaussianexamples = (0,0) Marginal distributions of Gaussians are Gaussian Given:The marginal distribution is: bbbaabaababaxxx),(),,( Useful Properties of Gaussians34 Marginal distributions of Gaussians are Gaussian35 Block Matrix InversionTheoremDefinition: Schurcomplements36 Conditional distributions of Gaussians are Gaussian Notation.]

9 Conditional Distribution: bbbaabaa1 bbbaabaaUseful Properties of Gaussians37 Higher Dimensions Visualizing > 3 dimensional Gaussian random variables difficult Means and variances of marginal variable s are practical, but then we don t see correlations between those variables Marginalsare Gaussian, , f(6) ~ N( (6), 2(6))Visualizing an 8-dimensional Gaussian variable f: (6) 2(6)6543217838 Yet Higher DimensionsWhy stop there?39 Getting RidiculousWhy stop there?40 Gaussian Process Probability distribution indexed byan arbitrary set (integer, real, finite dimensional vector, etc) Each element (indexed by x) is a Gaussian distribution over the reals with mean (x) These distributions are dependent/correlated as defined by k(x,z) Any finite subset of indices defines a multivariate Gaussian distributionDefinition of GP:41 Gaussian Process Distribution over our regression model is a GP, then it won t be a point estimate anymore!

10 It can provide regression estimates with confidence Domain (index set) of the functions can be pretty much whatever Reals Real vectors Graphs Strings Sets ..42 Bayesian Updates for GPs How can we do regression and learn the GP from data? We will be Bayesians today: Start with GP prior Get some data Compute a posterior43 Samples from the prior distributionPicture is taken from Rasmussen and Williams44 Samples from the posterior distributionPicture is taken from Rasmussen and Williams45 PriorZero mean Gaussians with covariance k(x,z)46 Data47 Posterior48 Ridge RegressionLinear regression:Ridge regression:The Gaussian Process is a Bayesian Generalization of the kernelizedridge regression49 Weight Space ViewGP = Bayesian ridge regression in feature space+ Kernel trick to carry out computationsThe training data50 Bayesian Analysis of Linear Regression with Gaussian noiseLinear regression:Linear regressionwith noise:51 Bayesian Analysis of Linear Regression with Gaussian noiseThe likelihood.