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 215PollPoll•Were the summary slides for Weeks1-7Were the summary slides for Weeks 17 useful for the midterm?2Project PresentationsProject Presentations•Present project in class onDecember 9Present project in class on December 9– Send me PPT/PDF file by 5pm or bring your own laptopown laptop– 8 projects * 15 min = 120 minutes –12min presentation +3min Q&A–12 min presentation + 3 min Q&A• Counts for 10% of total gradePattern Classification, Chapter 1 3Project 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 4CS Department Project Poster DayCS Department Project Poster Day•December 7 12-2pmDecember 7, 122pm• Lieb third floor conference room and corridorscorridors• 5% of total grade as bonusNliibl–Not negligible– Not unfair for those who cannot make it• Suggestion: 6-12 printed pages 5CS 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 results6Final ReportFinal Report•DueDecember 14 (23:59)Due December 14 (23:59)• 6-10 pages including figures, tables and referencesreferences• Counts for 15% of total grade• NO LATE SUBMISSIONS7Instructions 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 computations8OverviewOverview•Unsupervised Learning (slides by OlgaUnsupervised Learning (slides by Olga Veksler)Supervised vs unsupervised learning–Supervised vs. unsupervised learning– Unsupervised learningFlat clustering (kmeans)–Flat clustering (k-means)– Hierarchical clustering (also see DHS Ch. 10)9Supervised vs. Unsupervised LearningSupervised vs. Unsupervised Learning• Up to now we considered supervised learning ih iscenarios, where we are given1. samples x1,…, xn2. class labels for all samples– This is also called learning with teacher, since the correct answer (the true class) is provided• Today we consider unsupervised learning scenarios, where we are only given1.samples x1,…, xnsa p es1,,n– This is also called learning without teacher, since the correct answer is not provided–Do not split data into training and test setspg10Unsupervised LearningUnsupervised Learning• Data is not labeled •Parametric Approach•Parametric Approach– Assume parametric distribution of data–Estimate parameters of this distributionp– Remember Expectation Maximization?• Non-Parametric ApproachGhdilhl–Group the data into clusters, each cluster (hopefully) says something about classes present in the data11Why Unsupervised Learning?Why Unsupervised Learning?• Unsupervised learning is harder– How do we know if results are meaningful? No answer (labels) is available• Let the expert look at the results (external evaluation)Dfi bjti f ti lti (it l lti)•Define an objective function on clustering (internal evaluation)• We nevertheless need it because1. Labeling large datasets is very costly (speech recognition object detection in images)recognition, object detection in images) • Sometimes can label only a few examples by hand2. May have no idea what/how many classes there are (data mining)mining)3. May want to use clustering to gain some insight into the structure of the data before designing a classifier• Clustering as data descriptiongp12ClusteringClustering• Seek “natural” clusters in the data• What is a good clustering?– internal (within the cluster) distances should be small–external (intra-cluster) should be large• Clustering is a way to discover new categories (classes)(classes)13What we need for ClusteringWhat we need for Clustering1. Proximity measure, either iilit()lifiil–similarity measure s(xi,xk): large if xi,xkare similar– dissimilarity(or distance) measure d(xi,xk): small if xi,xkare similar2. Criterion function to evaluate a clustering3Algorithm to compute clustering3.Algorithm to compute clustering– For example, by optimizing the criterion function14How Many Clusters?How Many Clusters?• Possible approaches1. Fix the number of clusters to k2. Find the best clustering according to the criterion function (number of clusters may vary)criterion function (number of clusters may vary)15Proximity MeasuresProximity Measures• A good proximity measure is VERY application dependentdependent– Clusters should be invariant under the transformations “natural” to the problem– For example for object recognition, we should have invariance to rotation– For character recognition, no invariance to rotation16Distance MeasuresDistance Measures• Euclidean distance– translation invariant•Manhattan (city block) distanceManhattan (city block) distancei ti t E lid–approximation to Euclidean distance, cheaper to compute• Chebyshev distance– approximation to Euclidean distance cheapest to computedistance, cheapest to compute17Feature ScalingFeature Scaling• Old problem: how to choose appropriate relative scale for features?scale for features?– [length (in meters or cms?), weight (in grams or kgs?)]• In supervised learning, can normalize to zero supe sed ea g, ca o a e to e omean unit variance with no problems• In clustering this is more problematic•If variance in data is due to cluster presence, then normalizing features is not a good thing18Simple Clustering AlgorithmSimple Clustering