1CS 2750 Machine LearningCS 2750 Machine LearningMilos [email protected] Sennott Square, x4-8845http://www.cs.pitt.edu/~milos/courses/cs2750/Lecture 1Machine LearningCS 2750 Machine LearningAdministrationStudy material• Handouts, your notes and course readings• Primary textbook:– Duda, Hart, Stork. Pattern classification. 2ndedition. J Wiley and Sons, 2000.• Recommended book:– Friedman, Hastie, Tibshirani. Elements of statistical learning. Springer, 2001.• Other books:– C. Bishop. Neural networks for pattern recognition. Oxford U. Press, 1996.– T. Mitchell. Machine Learning. McGraw Hill, 1997– J. Han, M. Kamber. Data Mining. Morgan Kauffman, 2001.2CS 2750 Machine LearningAdministration• Lectures:– Random short quizzes testing the understanding of basic concepts from previous lectures• Homeworks: weekly– Programming tool: Matlab (CSSD machines and labs)– Matlab Tutorial: next week• Exams:– Midterm (March)• Final project: – Proposals (early March)– Written report + Oral presentation(end of the semester)CS 2750 Machine LearningTentative topics• Concept learning.• Density estimation. • Linear models for regression and classification. • Multi-layer neural networks.• Support vector machines. Kernel methods.• Learning Bayesian networks.• Clustering. Latent variable models.• Dimensionality reduction. Feature extraction.• Ensemble methods. Mixture models. Bagging and boosting.• Hidden Markov models.• Reinforcement learning3CS 2750 Machine LearningMachine Learning• The field of machine learning studies the design of computer programs (agents) capable of learning from past experience or adapting to changes in the environment• The need for building agents capable of learning is everywhere – predictions in medicine, – text and web page classification, – speech recognition,– image/text retrieval, – commercial software CS 2750 Machine LearningLearningLearning process:Learner (a computer program) processes data D representing past experiences and tries to either develop an appropriate response to future data, or describe in some meaningful way the data seen Example:Learner sees a set of patient cases (patient records) with corresponding diagnoses. It can either try:– to predict the presence of a disease for future patients– describe the dependencies between diseases, symptoms4CS 2750 Machine LearningTypes of learning• Supervised learning– Learning mapping between input x and desired output y– Teacher gives me y’s for the learning purposes• Unsupervised learning– Learning relations between data components– No specific outputs given by a teacher• Reinforcement learning– Learning mapping between input x and desired output y– Critic does not give me y’s but instead a signal (reinforcement) of how good my answer was• Other types of learning:– explanation-based learning, etc.CS 2750 Machine LearningSupervised learningData: a set of n examples is input vector, and y is desired output (given by a teacher)Objective: learn the mapping s.t.Two types of problems:• Regression: X discrete or continuousY is continuous• Classification: X discrete or continuousY is discrete},..,,{21 ndddD =>=<iiiyd ,xixYXf →:nixfyii,..,1allfor)( =≈5CS 2750 Machine LearningSupervised learning examples• Regression: Y is continuousDebt/equityEarnings company stock priceFuture product orders•Classification: Y is discreteHandwritten digit (array of 0,1s)Label “3”CS 2750 Machine LearningUnsupervised learning• Data:vector of valuesNo target value (output) y •Objective:– learn relations between samples, components of samplesTypes of problems:• ClusteringGroup together “similar” examples, e.g. patient cases•Density estimation– Model probabilistically the population of samples},..,,{21 ndddD =iid x=6CS 2750 Machine LearningUnsupervised learning example. • Density estimation. We want to build the probability model of a population from which we draw samples -2 -1.5 -1 -0.5 0 0.5 1 1.5 2-1-0.500.511.522.53iid x=CS 2750 Machine LearningUnsupervised learning. Density estimation• A probability density of a point in the two dimensional space– Model used here: Mixture of Gaussians7CS 2750 Machine LearningReinforcement learning• We want to learn:• We see samples of x but not y • Instead of y we get a feedback (reinforcement) from a criticabout how good our output was • The goal is to select outputs that lead to the best reinforcementLearnerinput sampleoutputCriticreinforcementYXf →:CS 2750 Machine LearningLearning• Assume we see examples of pairs (x , y) and we want to learn the mapping to predict future ys for values of x• We get the data what should we do?YXf →:-2.5 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2-10-8-6-4-20246810xy8CS 2750 Machine LearningLearning bias• Problem: many possible functions exists for representing the mapping between x and y • Which one to choose? Many examples still unseen!YXf →:-2.5 -2 -1.5 -1 -0.5 0 0.5 1 1. 5 2-10-8-6-4-20246810xyCS 2750 Machine LearningLearning bias• Problem is easier when we make an assumption about the model, say,• Restriction to a linear model is an example of learning bias ε++= baxxf )(- random (normally distributed) noise),0(σεN=-2.5 -2 -1.5 -1 -0. 5 0 0.5 1 1. 5 2-10-8-6-4-20246810xy9CS 2750 Machine LearningLearning bias• Bias provides the learner with some basis for choosing among possible representations of the function.•Forms of bias: constraints, restrictions, model preferences•Important: There is no learning without a bias!-2.5 -2 -1.5 -1 -0. 5 0 0.5 1 1. 5 2-10-8-6-4-20246810xyCS 2750 Machine LearningLearning bias• Choosing a parametric model or a set of models is not enough Still too many functions– One for every pair of parameters a, bε++= baxxf )(-2.5 -2 -1.5 -1 -0.5 0 0. 5 1 1.5 2-10-8-6-4-20246810),0(σεN=xy10CS 2750 Machine LearningFitting the data to the model• We are interested in finding the best set of model parametersObjective: Find the set of parameters that:• reduces the misfit between the model and observed data• Or, (in other words) that explain the data the bestError function:Measure of misfit between the data and the model• Examples of error functions:– Average square error– Average misclassification error21))((1iinixfyn−∑=Average # of