1 Machine Learning Overview Sargur N. Srihari University at Buffalo, State University of New York USA2 Outline 1. What is Machine Learning (ML)? 2. Types of Problems Solved 1. Regression 2. Classification 3. Responses to Probabilistic Queries 3. Probability and Statistics 1. Frequentist Approach 2. Bayesian Approach3 What is Machine Learning? • Programming computers to: – Perform tasks that humans perform well but difficult to specify algorithmically • Principled way of building high performance information processing systems – Probabilistic responses to queries—IR – Adaptive user interfaces, personalized assistants (information systems) – Scientific/engineering applications4 Example Problem: Handwritten Digit Recognition • Handcrafted rules will result in large no of rules and exceptions • Better to have a machine that learns from a large training set • Handwriting recognition cannot be done without machine learning! Wide variability of same numeral5 Most Successful Application of ML • Learning to recognize spoken words – Speaker-specific strategies for recognizing primitive sounds (phonemes) and words from speech signal – Neural networks and methods for learning HMMs for customizing to individual speakers, vocabularies and microphone characteristics – Recently Google increased accuracy for Android by 25% Ta b l e 1 . 16 ML Example: Self-Driving Vehicle • Learning to drive an autonomous vehicle – Train computer-controlled vehicles to steer correctly – Drive at 25 mph – Associate steering commands with image sequences Google Prototype Deployment: Taxi Courier Service ALVINN: Drive at 70mph for 90 miles on public highways7 ML Example: Cursive Handwriting • Task T – recognizing and classifying handwritten words within images • Performance measure P – percent of words correctly classified • Training experience E – a database of handwritten words with given classificationsML Example: Personalization • Facebook: improve relevance of posts it shows you • Persado: advertising copywriting 89 The ML Approach Generalization (Training) Data Collection Samples Model Selection Probability distribution to model process Parameter Estimation Values/distributions Inference Find responses to queries Decision (Inference OR Testing)10 ML History • ML has origins in Computer Science • PR has origins in Engineering • They are different facets of the same field • Methods around for over 50 years • Information ExplosionML as a subfield of AI 11Engineering Classification Problem • Off-shore oil transfer pipelines • Non-invasive measurement of proportion of • oil,water and gas • Called Three-phase Oil/Water/Gas FlowDual-energy gamma densitometry • Beam of gamma rays passed through pipe • Attenuation in intensity provides information on density of material • Single beam insufficient • Two degrees of freedom: fraction of oil, fraction of water Detector One beam of Gamma rays of two energies (frequencies or wavelengths)14 Three classes 1. Low Velocity: Stratified configuration – Oil floats on top of water, gas above oil 2. Medium Velocity: Annular configuration – Concentric cylinders of Water, oil, gas 3. High-Turbulence: Homogeneous – Intimately mixed • Single beam is insufficient – Horizontal beam thru stratified indicates only oilMultiple dual energy gamma densitometers 15 • Six Beams • 12 measurements • attenuation16 Prediction Problems 1. Predict Volume Fractions of oil/water/gas 2. Predict geometric configuration of three phases • Twelve Features – Fractions of oil and water along the paths • Learn to classify from data17 Feature Space • Three classes (Stratified,Annular,Homogeneous) • Two variables shown • 100 points Which class should x belong to?18 Cell-based Classification • Naïve approach of cell based voting will fail – exponential growth of cells with dimensionality – 12 dimensions discretized into 6 gives 3 million cells • Hardly any points in each cell19 Rules of Probability • Given random variables X and Y • Sum Rule gives Marginal Probability • Product Rule: joint probability in terms of conditional and marginal • Combining we get Bayes Rule NccnXpXYpNnYXpiiijij×=== )()|(),(NcyYxXpxXpiLjjii=====∑=1),()()()()|()|(XpYpYXpXYp =∑=YYpYXpXp )()|()(where Viewed as Posterior a likelihood x prior20 Popular Statistical Models • Generative – Naïve Bayes – Mixtures of multinomials – Mixtures of Gaussians – Hidden Markov Models (HMM) – Bayesian networks – Markov random fields • Discriminative – Logistic regression – SVMs – Traditional neural networks – Nearest neighbor – Conditional Random Fields (CRF)Regression Problems 21 Forward problem data set Red curve is result of fitting a two-layer neural network by minimizing sum-of-squared error Corresponding inverse problem by reversing x and t Very poor fit to data: GMMs used hereForward and Inverse Problems • Kinematics of a robot arm 22 Forward problem: Find end effector position given joint angles Has a unique solution Inverse kinematics: two solutions: Elbow-up and elbow-down • Forward problems correspond to causality in a physical system have a unique solution e.g., symptoms caused by disease • If forward problem is a many-to-one mapping, inverse has multiple solutions23 Bayesian Representation of Uncertainty • Use of probability to represent uncertainty is not an ad-hoc choice • If numerical values represent degrees of belief, – then simple axioms for manipulating degrees of belief leads to sum and product rules of probability • Not just frequency of random, repeatable event • It is a quantification of uncertainty • Example: Whether Arctic ice cap will disappear by end of century – We have some idea of how quickly polar ice is melting – Revise it on the basis of fresh evidence (satellite observations) – Assessment will affect actions we take (to reduce greenhouse gases) • Handled by general Bayesian interpretation24 The Fully Bayesian Approach • Bayes Rule • Bayesian Probabilities • Concept of Conjugacy • Monte Carlo Sampling25