1Chapter 1: IntroductionCS 536: Machine LearningLittman (Wu, TA)Outline• Why Machine Learning?• What is a well-defined learning problem?• An example: Learning to play checkers• What questions should we ask aboutMachine Learning?2Why Machine Learning• Recent progress in algorithms and theory• Growing flood of online data• Computational power is available• Budding industryThree Niches for ML• Data mining: using historical data toimprove decisions– medical records Æ medical knowledge• Software applications we can't program byhand– autonomous driving– speech recognition• Self customizing programs– Newsreader that learns user interests3Typical Datamining TaskGiven:• 9714 patient records, each describing a pregnancyand birth• Each patient record contains 215 featuresLearn to predict:• Classes of future patients at high risk forEmergency Cesarean SectionPatient DataPatient103 time=1Age: 23FirstPregnancy: noAnemia: noDiabetes: noPreviousPrematureBirth: noUltrasound: ?Elective C-Section: ?Emergency C-Section: ?…Patient103 time=2Age: 23FirstPregnancy: noAnemia: noDiabetes: YESPreviousPrematureBirth: noUltrasound: abnormalElective C-Section: noEmergency C-Section: ?…Patient103 time=nAge: 23FirstPregnancy: noAnemia: noDiabetes: noPreviousPrematureBirth: noUltrasound: ?Elective C-Section: noEmergency C-Section: YES……4Datamining ResultOne of 18 learned rules:If No previous vaginal delivery, andAbnormal 2nd Trimester Ultrasound, andMalpresentation at admissionThen Probability of Emergency C-Sectionis 0.6• Over training data: 26/41 = .63,• Over test data: 12/20 = .60Credit Risk Analysis DataCust103 time=1Years of credit: 9Loan balance: $2,400Income: $52kOwn House: YesOtherDeliquentAccts: 2Max billing cycles late: 3Profitable customer?: ?…Cust103 time=2Years of credit: 9Loan balance: $3,250Income: ?Own House: YesOtherDeliquentAccts: 2Max billing cycles late: 4Profitable customer?: ?…Cust103 time=nYears of credit: 9Loan balance: $4,500Income: ?Own House: YesOtherDeliquentAccts: 3Max billing cycles late: 6Profitable customer?: No……5Datamining ResultRules learned from synthesized data:If Other-Delinquent-Accounts > 2, andNumber-Delinquent-Billing-Cycles > 1Then Profitable-Customer? = No[Deny Credit Card application]If Other-Delinquent-Accounts = 0, and(Income > $30k) OR (Years-of-Credit > 3)Then Profitable-Customer? = Yes[Accept Credit Card application]Customer Purchase BehaviorCust103 time=1Sex: MAge: 53Income: $50kOwn House: YesMS Products: WordComputer: 386 PCPurchase Excel?: ?…Cust103 time=2Sex: MAge: 53Income: $50kOwn House: YesMS Products: WordComputer: PentiumPurchase Excel?: ?…Cust103 time=nSex: MAge: 53Income: $50kOwn House: YesMS Products: WordComputer: PentiumPurchase Excel?: Yes……6Customer RetentionCust103 time=1Sex: MAge: 53Income: $50kOwn House: YesChecking: $5kSavings: $15kCurrent-customer?: yesCust103 time=2Sex: MAge: 53Income: $50kOwn House: YesChecking: $20kSavings: $0kCurrent-customer?: yesCust103 time=nSex: MAge: 53Income: $50kOwn House: YesChecking: $0kSavings: $0kCurrent-customer?: no…Process OptimizationProduct72 time=1Stage: mixMixing-speed: 60rpmViscosity: 1.3Fat content: 15%Density: 2.8Spectral peak: 2800Product underweight?: ?Product72 time=2Stage: cookTemperature: 325Viscosity: 3.2Fat content: 12%Density: 1.1Spectral peak: 3200Product underweight?: ?Product72 time=nStage: coolFan-speed: mediumViscosity: 1.3Fat content: 12%Density: 1.2Spectral peak: 3100Product underweight?: Yes…7Too Difficult to ProgramProblems too difficult to program by handALVINN [Pomerleau] drives 70mph on highwaysSoftware Customizes to Userhttp://www.wisewire.comApril 30, 1998Lycos Acquires WiseWireBy internetnews.com StaffLycos, Inc. today announced theacquisition of targeted-contentprovider WiseWire Corp. for around$39.75 million in Lycos shares.Under the acquisition, the three-yearold, Pittsburgh-based WiseWire'sautomated directory will beincorporated into Lycos’ searchpage. Lycos said it will be the firstonline service using the technologywhich is based on user input and anintelligent agent product.8Where Is This Headed?Today: tip of the iceberg• First-generation algorithms: neural nets, decisiontrees, regression ...• Applied to well-formated database• Budding industryLooking to TomorrowOpportunity for tomorrow: enormous impact• Learn across full mixed-media data• Learn across multiple internal databases, plus theweb and newsfeeds• Learn by active experimentation• Learn decisions rather than predictions• Cumulative, lifelong learning• Programming languages with learning embedded?9Relevant Disciplines• Articial intelligence• Bayesian methods• Computational complexity theory• Control theory• Information theory• Philosophy• Psychology and neurobiology• Statistics• …What is the Learning Problem?Learning = Improving with experience at some task• Improve over task T,• with respect to performance measure P,• based on experience E.E.g., Learn to play checkers• T: Play checkers• P: % of games won in world tournament• E: opportunity to play against self10Learning Curves• T: parsing Korean• P: “crossing brackets”• E: training sentencesFrom “Rapid ParserDevelopment: AMachine LearningApproach for Korea” byUlf HermjakobOther Kinds of “Learning”?"Tamagotchi is a tiny pet from cyberspace who needs your love to survive andgrow. If you take good care of your Tamagotchi pet, it will slowly grow bigger,healthier, and more beautiful every day. Bit if you neglect your little cybercreature, your Tamagotchi may grow up to be mean or ugly. How old willyour Tamagotchi be when it returns to its home planet? What kind of virtualcaretaker will you be?" - Bandaihttp://www.mimitchi.com/html/q1.htm11Learning to Play Checkers• T: Play checkers• P: Percent of games won in world tournament• What experience?• What exactly should be learned?• How shall it be represented?• What specific algorithm to learn it?Type of Training Experience• Direct or indirect?• Teacher or not?A problem: is training experience representative ofperformance goal?12Choose the Target Function• ChooseMove: Board Æ Move ??• V: Board Æ ¬ ??• …Possible Definition for V• if b is a final board state that is won, then V(b) = 100• if b is a final board state that is lost, then V(b) = -100• if b is a final board state that is drawn, then V(b) = 0• if b is a not a final state in the game, then