Machine LearningInstructor: Rich [email protected]: Machine Learning, MitchellNotes based on Mitchell’s Lecture NotesCS 5751 Machine LearningChapter 1 Intro to Machine Learning 2What is Learning?Learning denotes changes in the system that are adaptive in the sense that they enable the system to do the same task or tasks drawn from the same population more effectively the next time. -- Simon, 1983Learning is making useful changes in our minds. -- Minsky, 1985Learning is constructing or modifying representations of what is being experienced. -- McCarthy, 1968Learning is improving automatically with experience. --Mitchell, 1997CS 5751 Machine LearningChapter 1 Intro to Machine Learning 3Why Machine Learning?• Data, Data, DATA!!!– Examples• World wide web• Human genome project• Business data (WalMart sales “baskets”)– Idea: sift heap of data for nuggets of knowledge• Some tasks beyond programming– Example: driving– Idea: learn by doing/watching/practicing (like humans)• Customizing software– Example: web browsing for news information– Idea: observe user tendencies and incorporateCS 5751 Machine LearningChapter 1 Intro to Machine Learning 4Typical Data Analysis TaskGiven– 9714 patient records, each describing a pregnancy and a birth– Each patient record contains 215 features (some are unknown)Learn to predict:– Characteristics of patients at high risk for Emergency C-SectionPatient103Age: 23FirstPregnancy: noAnemia: noDiabetes: noPreviousPrematureBirth: noUltrasound: ?Elective C-Section: ?Emergency C-Section: ?...time=1Patient103Age: 23FirstPregnancy: noAnemia: noDiabetes: YESPreviousPrematureBirth: noUltrasound: abnormalElective C-Section: noEmergency C-Section: ?...time=2Patient103Age: 23FirstPregnancy: noAnemia: noDiabetes: noPreviousPrematureBirth: noUltrasound: ?Elective C-Section: noEmergency C-Section: YES...time=nCS 5751 Machine LearningChapter 1 Intro to Machine Learning 5Credit Risk AnalysisRules learned from data:IF Other-Delinquent-Accounts > 2, ANDNumber-Delinquent-Billing-Cycles > 1THEN Profitable-Customer? = No [Deny Credit Application]IF Other-Delinquent-Accounts == 0, AND((Income > $30K) OR (Years-of-Credit > 3))THEN Profitable-Customer? = Yes [Accept Application]Customer103Years of credit: 9Loan balance: $2,400Income: $52KOwn House: YesOther delinquent accts: 2Max billing cycles late: 3Profitable customer: ?...time=10Customer103Years of credit: 9Loan balance: $3,250Income: ?Own House: YesOther delinquent accts: 2Max billing cycles late: 4Profitable customer: ?...time=11Customer103Years of credit: 9Loan balance: $4,500Income: ?Own House: YesOther delinquent accts: 3Max billing cycles late: 6Profitable customer: No...time=nCS 5751 Machine LearningChapter 1 Intro to Machine Learning 6Analysis/Prediction Problems• What kind of direct mail customers buy?• What products will/won’t customers buy?• What changes will cause a customer to leave a bank?• What are the characteristics of a gene?• Does a picture contain an object (does a picture of space contain a metereorite -- especially one heading towards us)?• … Lots moreCS 5751 Machine LearningChapter 1 Intro to Machine Learning 7Tasks too Hard to ProgramALVINN [Pomerleau] drives 70 MPH on highwaysCS 5751 Machine LearningChapter 1 Intro to Machine Learning 8Software that Customizes to UserCS 5751 Machine LearningChapter 1 Intro to Machine Learning 9Defining a Learning ProblemLearning = improving with experience at some task– improve over task T– with respect to performance measure P– based on experience EEx 1: Learn to play checkersT: play checkersP: % of games wonE: opportunity to play selfEx 2: Sell more CDsT: sell CDsP: # of CDs soldE: different locations/prices of CDCS 5751 Machine LearningChapter 1 Intro to Machine Learning 10Key QuestionsT: play checkers, sell CDsP: % games won, # CDs soldTo generate machine learner need to know:– What experience?• Direct or indirect?• Learner controlled?• Is the experience representative?– What exactly should be learned?– How to represent the learning function?– What algorithm used to learn the learning function?CS 5751 Machine LearningChapter 1 Intro to Machine Learning 11Types of Training ExperienceDirect or indirect?Direct - observable, measurable– sometimes difficult to obtain• Checkers - is a move the best move for a situation?– sometimes straightforward• Sell CDs - how many CDs sold on a day? (look at receipts)Indirect - must be inferred from what is measurable– Checkers - value moves based on outcome of game– Credit assignment problemCS 5751 Machine LearningChapter 1 Intro to Machine Learning 12Types of Training Experience (cont)Who controls?– Learner - what is best move at each point? (Exploitation/Exploration)– Teacher - is teacher’s move the best? (Do we want to just emulate the teachers moves??)BIG Question: is experience representative of performance goal?– If Checkers learner only plays itself will it be able to play humans?– What if results from CD seller influenced by factors not measured (holiday shopping, weather, etc.)?CS 5751 Machine LearningChapter 1 Intro to Machine Learning 13Choosing Target FunctionCheckers - what does learner do - make movesChooseMove - select move based on boardChooseMove(b): from b pick move with highest valueBut how do we define V(b) for boards b?Possible definition:V(b) = 100 if b is a final board state of a winV(b) = -100 if b is a final board state of a lossV(b) = 0 if b is a final board state of a drawif b not final state, V(b) =V(b´) where b´ is best final board reached by starting at b and playing optimally from thereCorrect, but not operationalℜ→→BoardVMoveBoardChooseMove::CS 5751 Machine LearningChapter 1 Intro to Machine Learning 14Representation of Target Function• Collection of rules?IF double jump available THENmake double jump• Neural network?• Polynomial function of problem features?)(#)(#)(#)(#)(#)(#6543210btenedblackThreawbnedredThreatewbredKingswbblackKingswbredPieceswbsblackPieceww++++++CS 5751 Machine LearningChapter 1 Intro to Machine Learning 15Obtaining Training Examples))((ˆ)( : values trainingestimatingfor rule One value training the:)(function learned the:)(ˆfunction target true the:)(bSuccessorVbVbVbVbVtraintrain←CS 5751 Machine LearningChapter 1 Intro to Machine Learning 16Choose Weight Tuning RuleLMS Weight update rule:learning of rate moderate to0.1,say