What 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 kd f h l i ff i l htasksdrawnfrom the same population more effectively thenext 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 8751 ML & KDD Chapter 1 Introduction 1Mitchell,1997Why 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 programmingEldii–Example:driving– Idea: learn by doing/watching/practicing (like humans)•Customizing softwareCustomizing software– Example: web browsing for news information– Idea: observe user tendencies and incorporateCS 8751 ML & KDD Chapter 1 Introduction 2Analysis/Prediction Problems• What kind of direct mail customers buy?•What products will/won’t customers buy?What products will/won t customers buy?• What changes will cause a customer to leave a bank?bank?• What are the characteristics of a gene?iibj(dif•Does a picture contain an object(does a picture ofspace contain a metereorite -- especially one hdi t d )?headingtowards us)?•… Lots moreCS 8751 ML & KDD Chapter 1 Introduction 3Tasks too Hard to ProgramALVINN [Pomerleau] drives 70 MPH hi h70 MPH on highwaysCS 8751 ML & KDD Chapter 1 Introduction 4STANLEY: Stanford Racing• http://www.stanfordracing.orgpgg• Sebastian Thrun’s Stanley Racing program• Winner of the DARPA grand challenge• Incorporated learning/learned components with planning and vision componentsCS 8751 ML & KDD Chapter 1 Introduction 5Software that Customizes to UserCS 8751 ML & KDD Chapter 1 Introduction 6Some Areas of Machine Learning• Inductive Learning: inferring new knowledge from observations (not guaranteed correct)–Concept/Classification Learning - identify characteristics of class members (e.g., what makes a CS class fun, what makes a customer buy, etc.)– Unsupervised Learning - examine data to infer new characteristics (e.g., break chemicals into similar groups, infer new mathematical rule, etc.)groups, infer new mathematical rule, etc.)– Reinforcement Learning - learn appropriate moves to achieve delayed goal (e.g., win a game of Checkers, perform a robot task etc )perform a robot task,etc.)• Deductive Learning: recombine existing knowledge to more effectively solve problemsCS 8751 ML & KDD Chapter 1 Introduction 7gypClassification/Concept Learning• What characteristic(s) predict a smile?Variation on Sesame Street game:why are these things a lot like–Variation on Sesame Street game:why are these things a lot likethe others (or not)?• ML Approach: infer model (characteristics that indicate) of CS 8751 ML & KDD Chapter 1 Introduction 8why a face is/is not smilingUnsupervised Learning• Clustering -grouppoints into “classes”ggpp• Other ideas:– look for mathematical relationships between featuresl k f li i d t b (d t th t d t fit)CS 8751 ML & KDD Chapter 1 Introduction 9–lookfor anomaliesindatabases(datathatdoes not fit)Reinforcement LearningS - startGProblem PolicyG - goalPossible actions: up leftG down rightS•Problem: feedback (reinforcements) are delayedhow to•Problem: feedback (reinforcements) are delayed -how tovalue intermediate (no goal states)• Idea: online dynamic programming to produce policy function• Policy: action taken leads to highest future reinforcement (if policy followed)CS 8751 ML & KDD Chapter 1 Introduction 10(if policy followed)Analytical LearningS1 S3S2Problem!Backtrack!Init GoalS7 S8S6S5S4S9 S0• During search processes (planning, etc.) remember work involved in solving tough problems• Reuse the acquired knowledge when presented with similar problems in the future (avoid bad decisions)CS 8751 ML & KDD Chapter 1 Introduction 11The Present in Machine LearningThe tip of the iceberg:•Firstgeneration algorithms: neural netsdecision•First-generation algorithms: neural nets,decisiontrees, regression, support vector machines, …• Composite algorithms - ensembles• Significant work on assessing effectiveness, limits• Applied to simple data bases•Budding industry (especially in data mining)•Budding industry (especially in data mining)CS 8751 ML & KDD Chapter 1 Introduction 12The Future of Machine LearningLots of areas of impact:•Learn across multiple data bases as well as webLearn across multiple data bases,as well as weband news feeds•Learn across multimedia data•Learn across multi-media data• Cumulative, lifelong learningAihlibddd•Agents withlearning embedded• Programming languages with learning embedded?• Learning by active experimentationCS 8751 ML & KDD Chapter 1 Introduction 13What is Knowledge Discovery in Databases (i e Data Mining)?Databases (i.e.,Data Mining)?• Depends on who you ask•General idea: the analysis of large amounts of dataGeneral idea: the analysis of large amounts of data(and therefore efficiency is an issue)• Interfaces several areas, notably machine learning,y gand database systems• Lots of perspectives:pp– ML: learning where efficiency matters– DBMS: extended techniques for analysis of raw data, idifkldautomatic production ofknowledge• What is all the hubbub?C i k l t f ith it ( W lM t)CS 8751 ML & KDD Chapter 1 Introduction 14–Companies makelots of money with it (e.g.,WalMart)Related Disciplines• Artificial Intelligence• Statistics• Psychology and neurobiology• Bioinformatics and Medical Informatics• Philosophy• Computational complexity theory• Control theory• Information theory• Database Systems• ...CS 8751 ML & KDD Chapter 1 Introduction 15Issues in Machine Learning• What algorithms can approximate functions well (and when)?• How does number of training examples influence accuracy?Hd litfhthi tti•Howdoes complexity ofhypothesis representationimpact it?•How does noisy data influence accuracy?How does noisy data influence accuracy?• What are the theoretical limits of learnability?•How can prior knowledge of learner help?How can prior knowledge of learner help?• What clues can we get from biological learning systems?CS 5541: AI - ML Chapter 1 Introduction