1CS 559: Machine LearningCS 559: Machine Learning Fundamentals and Applications13thSet of NotesInstructor: Philippos MordohaiWebpage: www.cs.stevens.edu/~mordohaiEmail:Philippos Mordohai@stevens eduE-mail: [email protected]: Lieb 215Project PresentationsProject Presentations•Present project in class on December8Present project in class on December 8– Send me PPT/PDF file by 5pm or bring your own laptopown laptop– 8 projects * 15 min = 120 minutes –12 min presentation + 3 min Q&A–12 min presentation + 3 min Q&A• Counts for 10% of total gradePattern Classification, Chapter 1 2Project PresentationsProject Presentations•Target audience: fellow classmatesTarget audience: fellow classmates• Content:–Define problemDefine problem – Show connection to class material • What is being classified, what are the classes etc.g,– Describe data• Train/test splits etc.– Show results• If additional experiments are in progress, describe themthemPattern Classification, Chapter 1 3CS Department Project Poster DayCS Department Project Poster Day•December6, 12-2pm*December 6, 122pm• Lieb third floor conference room and corridorscorridors• 5% of total grade as bonus–Not negligibleNot negligible– Not unfair for those who cannot make it•Suggestion: 6-12 printed pagesSuggestion: 612 printed pages *I will show up at 12:55 I will show up at 12:554CS Department Project Poster DayCS Department Project Poster Day• Your name, course number, project titlepj• Project objective: what are you trying to accomplish?•Method: which method(s) will be tested•Method: which method(s) will be tested– General description of method (not necessarily for the problem at hand)Dt td iti•Data set description– Include test/train split•Pre-and post-processing specific to this problemPreand postprocessing specific to this problem• Experiments• Conclusions on methods and experimental results5Final ReportFinal Report•Due December13(23:59)Due December 13 (23:59)• 6-10 pages including figures, tables and referencesreferences• Counts for 15% of total grade• NO LATE SUBMISSIONS6Instructions for FinalInstructions for Final•Emphasis on new material, not covered inEmphasis on new material, not covered in Midterm• Old material still in• Open book, open notes, open homeworksp,p ,pand solutions• No laptops, no cellphones• Calculators OK– No graphical solutions. Show all computations7OverviewOverview•Face Detection usingAdaBoostFace Detection using AdaBoost• Random Forests• Unsupervised Learning (slides by Olga Veksler)Veksler)– Supervised vs. unsupervised learning–Unsupervised learning–Unsupervised learning– Flat clustering (k-means)–Hierarchical clustering (also see DHS Ch 10)Hierarchical clustering (also see DHS Ch. 10)8Applications of BoostingApplications of BoostingReal time face detection using a classifier cascade (Viola and (Jones 2001 and 2004)9The Classical Face Detection ProcessLLargerScaleSmallestScale50,000 Locations/Scales10Classifier is Learned from Labeled Data• Training Datag– 5000 faces• All frontal– 108 non faces– Faces are normalized• Scale, translation• Many variationsAidiidl–Across individuals– IlluminationP (ttibthil dt)–Pose (rotation both in plane and out)11Key Properties of Face DetectionKey Properties of Face Detection•Each image contains10 000–50 000Each image contains 10,000 50,000 locations/scales•Faces are rare 050 per image•Faces are rare 0 -50 per image– 1000 times as many non-faces as faces• Extremely small rate of false negatives: 10-612“Support Vectors”Challenging negativeChallenging negative examples are extremely important13Classifier Cascade (Viola-Jones)Classifier Cascade (ViolaJones)• For real problems results are only as good as the fdfeatures used...– This is the main piece of ad-hoc (or domain) knowledge• Rather than the pixels, use a very large set of simple functions –Sensitive to edges and other critical features of the imageSensitive to edges and other critical features of the image– Computed at multiple scales•Introduce a threshold to yield binary features•Introduce a threshold to yield binary features – Binary features seem to work better in practice– In general, convert continuous features to binary by quantizingquantizing14Boosted Face Detection: Image FeaturesBoosted Face Detection: Image Features“R l fil ”“Rectangle filters”Similar to Haar wavelets )(iffotherwise )(if )(ttittitxfxh000,000,6100000,60Unique Binary FeaturestbxhxC )()(Unique Binary Featurest15Feature Selection• For each round of boosting:– Evaluate each rectangle filter on each example– Sort examples by filter values– Select best threshold for each filter– Select best filter/threshold (= Feature) – Reweight examples16Example Classifier for Face DetectionExample Classifier for Face DetectionA classifier with 200 rectangle features was learned using AdaBoost95% correct detection on test set with 1 in 14084false positives.ROC curve for 200 feature classifier17Building Fast ClassifiersBuilding Fast Classifiers• Given a nested set of classifier hypothesis classesvsfalse neg determined by% False Pos0 50 100 Detection •ComputationalRisk Minimization%50 Computational Risk MinimizationFACEIMAGESUB-WINDOWClassifier 1TClassifier 3TTClassifier 2TFNON-FACEFNON-FACEFNON-FACEFNON-FACE18Building Fast ClassifiersBuilding Fast Classifiers• In general, simple classifiers are more efficient, but hlkthey are also weaker•We could define a computational risk hierarchyWe could define a computational risk hierarchy– A nested set of classifier classes•The training process is reminiscent of boosting•The training process is reminiscent of boosting…– Previous classifiers reweight the examples used to train subsequent classifiers• The goal of the training process is different– Instead of minimizing errors minimize false positives19Cascaded ClassifierCascaded Classifier1 Feature5 Features50%20 Features20% 2%FACEIMAGESUBWINDOWFCNON-FACEFNON-FACEFNON-FACESUB-WINDOW•A 1-feature classifier achieves 100% detection rate and about 50% false positive raterate• A 5-feature classifier achieves 100% detection rate and 40% false positive rateidtf it–using data from previous stage• A 20-feature classifier achieve 100% detection