1CS 559: Machine Learning Fundamentals and Applications1stSet of NotesInstructor: Philippos MordohaiWebpage: www.cs.stevens.edu/~mordohaiE-mail: [email protected]: Lieb 215Pattern Classification, Chapter 11Objectives• Hands-on experience with fundamental algorithms– Useful for everyday problems• Exposure to state of the art in machine learning and pattern recognitionPattern Classification, Chapter 1 2Logistics• Office hours ?• Evaluation:– 4 homework sets (20%)– Project (40%)– Final exam (40%)• Project presentations ?• Pre-requisites: probability theory basics, Matlab or C/C++ programmingPattern Classification, Chapter 1 32Pattern ClassificationA lot of material in these slides was taken fromPattern Classification (2nd ed) by R. O. Duda, P. E. Hart and D. G. Stork, John Wiley & Sons, 2000with the permission of the authors and the publisherChapter 1: Introduction to Pattern Recognition (Sections 1.1-1.6)•Machine Perception•An Example•Pattern Recognition Systems•The Design Cycle•Learning and Adaptation•ConclusionPattern Classification, Chapter 1 5Machine Perception• Build a machine that can recognize patterns:– Speech recognition– Computer Vision: object recognition, face detection– Fingerprint identification– OCR (Optical Character Recognition)– DNA sequence identification Pattern Classification, Chapter 1 63An Example• “Sorting incoming Fish on a conveyor according to species using optical sensing”Sea bassSpeciesSalmonPattern Classification, Chapter 1 7• Problem Analysis– Set up a camera and take some sample images to extract features• Length• Lightness• Width• Number and shape of fins• Position of the mouth, etc…• This is the set of features to explore for use in our classifierPattern Classification, Chapter 1 8• Preprocessing– Use a segmentation operation to isolate fishes from one another and from the background• Information from a single fish is sent to a feature extractor whose purpose is to reduce the data by measuring certain features• The features are passed to a classifier Pattern Classification, Chapter 1 94Pattern Classification, Chapter 1 10• Classification– Select the length of the fish as a possible feature for discriminationPattern Classification, Chapter 1 11Pattern Classification, Chapter 1 125The length is a poor feature alone!Select the lightness as a possible feature.Pattern Classification, Chapter 1 13Pattern Classification, Chapter 1 14• Threshold decision boundary and cost relationship – Move our decision boundary toward smaller values of lightness in order to minimize the cost (reduce the number of sea bass that are classified as salmon!)Task of decision theoryPattern Classification, Chapter 1 156• Adopt the lightness and add the width of the fishFishxT= [x1, x2]Pattern Classification, Chapter 1 16LightnessWidthPattern Classification, Chapter 1 17• We may add other features that are not correlated with the ones we already have• Intuitivelly, the best decision boundary should be the one which provides an optimal performance such as in the following figure:Pattern Classification, Chapter 1 187Pattern Classification, Chapter 1 19• However, our satisfaction is premature because the central aim of designing a classifier is to correctly classify novel input Issue of generalization!Pattern Classification, Chapter 1 20Pattern Classification, Chapter 1 218Pattern Recognition Systems• Sensing– Use of a transducer (camera or microphone)– PR system depends of the bandwidth, the resolution sensitivity distortion of the transducer• Segmentation and grouping– Patterns should be well separated and should not overlapPattern Classification, Chapter 1 22• Feature extraction– Discriminative features– Invariant features with respect to translation, rotation and scale.• Classification– Use a feature vector provided by a feature extractor to assign the object to a category• Post Processing– Exploit context dependent information other than the target pattern itself to improve performancePattern Classification, Chapter 1 23Pattern Classification, Chapter 1 249The Design Cycle• Data collection• Feature Choice• Model Choice• Training• Evaluation• Computational ComplexityPattern Classification, Chapter 1 25Pattern Classification, Chapter 1 26• Data Collection– How do we know when we have collected an adequately large and representative set of examples for training and testing the system?Pattern Classification, Chapter 1 2710• Feature Choice– Depends on the characteristics of the problem domain. Simple to extract, invariant to irrelevant transformations, insensitive to noise.Pattern Classification, Chapter 1 28• Model Choice– Unsatisfied with the performance of our fish classifier and want to jump to another class of model. How can we know that a hypothesized model differs significantly from the true model?Pattern Classification, Chapter 1 29• Training– Use data to determine the classifier. Many different procedures for training classifiers and choosing modelsPattern Classification, Chapter 1 3011• Evaluation– Measure the error rate (or performance and switch from one set of features to another onePattern Classification, Chapter 1 31• Computational Complexity– What is the trade-off between computational ease and performance?– How does an algorithm scale as a function of the number of features, patterns or categories?Pattern Classification, Chapter 1 32Learning and Adaptation• Supervised learning– A teacher provides a category label or cost for each pattern in the training set• Unsupervised learning– The system forms clusters or “natural groupings” of the input patternsPattern Classification, Chapter 1 3312End of fish example. Back to business…Pattern Classification, Chapter 1 34Probability Theory ReviewSee DHS Appendix A.4Pattern Classification, Chapter 135Overview• Discrete Random Variables• Expected Value• Pairs of Discrete Random Variables– Conditional Probability– Bayes Rule• Continuous Random Variables3613Discrete Random Variables• A Random Variable is a measurement on a outcome of a random experiment—denoted by r.v. x•Discreteversus Continuous random variable: ar.v. xis discrete if it can assume a finite or countably infinite number of values. A r.v. xis continuous if it can assume all values in an interval.Pattern Classification, Chapter 1 37Examples• Which of the