Rui Castro Department of Electrical Engineering http://www.ee.columbia.edu/~rmcastro © Rui Manuel CastroMotivation select next sensing action Sense/Sample Observe / Infer How do we learn about the World? The learning process is in essence sequential and adaptive/active…More Motivation – Visual Perception Use previously collected data to guide the sampling process Ilya Repin. Unexpected Return (1884) (Eye tracking from Yarbus, 1967)Seven records of eye movements by the same subject. Each record lasted 3 minutes. 1) Free examination. Before subsequent recordings, the subject was asked to: 2) estimate the material circumstances of the family; 3) give the ages of the people; 4) surmise what the family had been doing before the arrival of the "unexpected visitor;" 5) remember the clothes worn by the people; 6) remember the position of the people and objects in the room; 7) estimate how long the "unexpected visitor" had been away from the family (from Yarbus 1967).“Is the person wearing a hat ?” “Does the person have blue eyes ?” How do we learn? - “Twenty Questions”!“Active Learning” works very well in simple conditions How about if the answers are not entirely reliable?Learning to Learn Sensing/ querying Observations Inference World Sampling strategy How can we take advantage of the feedback? How much can be gained? Sequential Sensing and Learning: learning using data collection procedures that use information gleaned from previous observations to guide the sensing process. Devise practical ways of using this feedback?Decided to make new astronomical measurements when “the discrepancy between prediction and observation [was] large enough to give a high probability that there is something new to be found.” Jaynes ‘86 Laplaceʼs Active Learning Discovery Observations Sampling strategy Bayesian approach: select new samples/experiments that are predicted to be maximally informative in discriminating models; “sample where the uncertainty is greatest”, Fedorov ’72, Mackay ‘92Challenges With feedback comes great responsibility!!! Sampling/ querying Observations World Sampling strategy If an active learning algorithm is “too aggressive” it might start focusing on the wrong questions... Curiosity can kill the cat!!! Strong dependencies among observations!!!cholesterol BMI Challenges - Classificationcholesterol BMI Does Active Learning Always Help?wireless sensor networks remote sensing Internet Monitoring Social Networks Why Do Active Learning?wireless sensor networks remote sensing Internet Monitoring Where, When and How to collect information? Social Networks Why Do Active Learning?Why do AL? - Human LearningSensing Computing Why do AL? - Human LearningHuge burden to the human in the loop Background Knowledge Experiment Outcome Experiment Selection Scientist Analysis “Towards 2020 Science” – 40 eminent scientists’ visions of the future of science Hypothesis Humans are unable to grasp the high-dimensional complexity of processes of interest There is a need for “autonomous experimentation” Why do AL? - Automating ScienceWired Magazine, April 2009: For the first time, a robotic system has made a novel scientific discovery with virtually no human intellectual input. Scientists designed "Adam" to carry out the entire scientific process on its own: formulating hypotheses, designing and running experiments, analyzing data, and deciding which experiments to run next. "It’s a major advance," says David Waltz of the Center for Computational Learning Systems at Columbia University. "Science is being done here in a way that incorporates artificial intelligence. It’s automating a part of the scientific process that hasn’t been automated in the past." Adam is the first automated system to complete the cycle from hypothesis, to experiment, to reformulated hypothesis without human intervention. www.aber.ac.uk/compsci/Research/bio/robotsci/Outline Binary Classification and the fundamental limits of active learning Algorithmic considerations, and active learning in practiceProbabilistic Framework for Classification! features label Goal: In words: given a feature vector we want to predict the label as well as possible… (generally unknown)!probability of error!Bayes Classifier!What is the “best” classification rule? Since we are considering binary labels any reasonable classification rule has the formrequires knowledge of!is the ½ level set of Bayes Classifier!The Bayes classifier says 1 if, given a feature , it is more likely that the corresponding label is 1 Classification is just a level-set estimation problemIn most problems is unknown. We have to rely on data Goal: We want to find a classifier “close” to ! Learning from Examples!Excess Risk How smooth is near!How easy is to approximate!“noise” characterization!Passive Learning!Cholesterol Level Body Mass Index Given n randomly selected examples how well can we do?many unlabeled examples (e.g., people, documents) labeling examples is expensive some examples are more informative than others Active Learning!Given n selectively chosen training examples, how well can we do? select Large pool of!unlabeled examples!cholesterol BMIThree Active Learning ParadigmsPassive vs. Active Sampling Passive Sampling: Active Sampling:The One Dimensional Threshold Problem!(unknown)!This can be made more general (bounded density)!Goal: Minimizing the excess risk boils down to constructing a good estimate ofunbounded noise noiseless bounded noise No strong cue about the location of the boundary How much does active learning help in each case? Various Scenarios!Passive Learning Sample locations must be chosen before any observations are made Too many wasted samples. Learning is limited by sampling resolutionActive Learning Sample locations are chosen as a function of previous observations The error decays much faster than in the passive scenario. No wasted samples…Active Learning Sample locations are chosen as a function of previous observations The error decays much faster than in the passive scenario. No wasted samples…Active Learning – Bounded Noise!Horstein, ‘63 Collect an erroneous label with probabilityActive Learning – Bounded Noise!Horstein, ‘63 Collect an erroneous label with probabilitysequentially take samples at posterior median Active Learning – Bounded Noise!Horstein, ‘63 Collect an erroneous label with probabilitysequentially take