Machine Learning: Generative and Discriminative ModelsOutline of Presentation1. Machine LearningProblems Too Difficult To Program by HandExample Problem: Handwritten Digit RecognitionOther Applications of Machine LearningML as Searching Hypotheses SpaceML Methodologies are increasingly statisticalThe Statistical ML Approach2. Generative and Discriminative Models: An analogyTaxonomy of ML ModelsSlide Number 12Successes of Generative MethodsSlide Number 14Support Vector Machines3. Generative-Discriminative PairsGraphical Model RelationshipGenerative Classifier: BayesNaïve Bayes ClassifierDiscriminative Classifier: Logistic RegressionLogistic Regression versus Generative Bayes ClassifierLogistic Regression ParametersMulti-class Logistic RegressionGraphical Model for Logistic Regression4. Sequence ModelsGenerative Model: HMM Discriminative Model for Sequential DataMarkov Random Field (MRF)MRF with Input-Output VariablesMRF Local FunctionFrom HMM to CRFCRF definitionFunctional ModelsNLP: Part Of Speech TaggingTable ExtractionShallow ParsingHandwritten Word RecognitionDocument Analysis (labeling regions) error rates 5. Advantage of CRF over Other ModelsDisadvantages of Discriminative ClassifiersBridging Generative and Discriminative6. Summary 7. ReferencesMachine Learning: Generative and Discriminative ModelsSargur N. [email protected] Learning Course: http://www.cedar.buffalo.edu/~srihari/CSE574/index.htmlMachine Learning Srihari2Outline of Presentation1. What is Machine Learning?ML applications, ML as Search2. Generative and Discriminative Taxonomy3. Generative-Discriminative PairsClassifiers: Naïve Bayes and Logistic RegressionSequential Data: HMMs and CRFs4. Performance Comparison in Sequential ApplicationsNLP: Table extraction, POS tagging, Shallow parsing, Handwritten word recognition, Document analysis5. Advantages, disadvantages6. Summary7. ReferencesMachine Learning Srihari31. Machine Learning• Programming computers to use example data or past experience• Well-Posed Learning Problems– A computer program is said to learn from experience E – with respect to class of tasks T and performance measure P, – if its performance at tasks T, as measured by P, improves with experience E.Machine Learning Srihari4Problems Too Difficult To Program by Hand• Learning to drive an autonomous vehicle– Train computer-controlled vehicles to steer correctly– Drive at 70 mph for 90 miles on public highways– Associate steering commands with image sequencesTask T: driving on public, 4-lane highway using vision sensorsPerform measure P: average distance traveled before error (as judged by human overseer)Training E: sequence of images and steering commands recorded while observing a human driverMachine Learning Srihari5Example 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 setWide variability of same numeralMachine Learning Srihari6Other Applications of Machine Learning• Recognizing spoken words– Speaker-specific strategies for recognizing phonemes and words from speech – Neural networks and methods for learning HMMs for customizing to individual speakers, vocabularies and microphone characteristics• Search engines– Information extraction from text• Data mining– Very large databases to learn general regularities implicit in data– Classify celestial objects from image data– Decision tree for objects in sky survey: 3 terabytesMachine Learning Srihari7ML as Searching Hypotheses Space• Very large space of possible hypotheses to fit:– observed data and– any prior knowledge held by the observerMethod Hypothesis SpaceConcept Learning Boolean ExpressionsDecision Trees All Possible TreesNeural Networks Weight SpaceMachine Learning Srihari8ML Methodologies are increasingly statistical• Rule-based expert systems being replaced by probabilistic generative models• Example: Autonomous agents in AI– ELIZA : natural language rules to emulate therapy session– Manual specification of models, theories are increasingly difficult• Greater availability of data and computational power to migrate away from rule-based and manually specified models to probabilistic data-driven modesMachine Learning Srihari9The Statistical ML Approach1. Data CollectionLarge sample of data of how humans perform the task2. Model SelectionSettle on a parametric statistical model of the process3. Parameter EstimationCalculate parameter values by inspecting the dataUsing learned model perform:4. SearchFind optimal solution to given problemMachine Learning Srihari102. Generative and Discriminative Models: An analogy• The task is to determine the language that someone is speaking • Generative approach:– is to learn each language and determine as to which language the speech belongs to• Discriminative approach:– is determine the linguistic differences without learning any language– a much easier task!Machine Learning Srihari11Taxonomy of ML Models• Generative Methods– Model class-conditional pdfs and prior probabilities– “Generative” since sampling can generate synthetic data points– Popular models• Gaussians, Naïve Bayes, Mixtures of multinomials• Mixtures of Gaussians, Mixtures of experts, Hidden Markov Models (HMM)• Sigmoidal belief networks, Bayesian networks, Markov random fields• Discriminative Methods– Directly estimate posterior probabilities – No attempt to model underlying probability distributions– Focus computational resources on given task– better performance– Popular models• Logistic regression, SVMs• Traditional neural networks, Nearest neighbor• Conditional Random Fields (CRF)Generative Models (graphical)Parent nodeselects betweencomponentsMarkov RandomFieldQuick Medical Reference -DTDiagnosingDiseases from SymptomsMachine Learning Srihari13Successes of Generative Methods• NLP– Traditional rule-based or Boolean logic systems (eg Dialog and Lexis-Nexis) are giving way to statistical approaches (Markov models and stochastic context free grammars)• Medical Diagnosis– QMR knowledge base, initially a heuristic expert systems for reasoning about diseases and symptoms has been augmented with decision theoretic formulation• Genomics and Bioinformatics– Sequences represented as generative HMMsMachine Learning