Contents

• Review of Machine Learning from 365
  • Organizational Issues
  • 415.706FC Web Page
  • Textbook
  • Introduction
  • Datamining versus Machine Learning
  • Success Stories
  • Definition of Learning
  • Example Learning Problems
  • Definition Continued
  • Designing a Learning System
  • Direct versus Indirect Learning
  • Teacher or not?
  • Choose Training Experience
  • Choose a Target Function
  • Choose a Target Function cont.
  • Choose Rep. for Target Func.
  • Expressibility Tradeoff
  • Choose a SIMPLE Representation
  • Design So Far
  • Choose Function Approx. Algo.
  • Choose Learning Algorithm
  • Least Mean Squares
  • LMS Algorithm
  • Design Methodology
  • Design Choices
  • Summary of Design Choices
  • Other Approaches
  • Learning as Search
  • Research Issues
  • Summary
  • Summary cont.
• Concept Learning
  • Concept Learning
  • Concept Learning Example
  • Hypothesis Representation
  • Notation
  • Our Example
  • The Inductive Hypothesis
  • Concept Learning as Search
  • Size of Search Space
  • General-to-Specific Ordering
  • Hypothesis Search Space
  • Hypothesis Partial Ordering
  • Maximally Specific Hypothesis
  • Find-S Algorithm
  • Questions Remain
  • Version Spaces
  • List-then-Eliminate Algorithm
  • Compact Rep. for Version Spaces
  • General and Specific Boundaries
  • Candidate Elimination Algorithm
  • Training Examples 1 & 2
  • Training Example 3
  • Training Example 4
  • Another Version Spaces Example
  • Version Spaces with Disjuncts
  • Properties of Candidate-Elim. Algo.
  • Requesting Training Examples
  • Partially Learned Concepts
  • Classifying with Partially Learned Concepts
  • Inductive Bias
  • A Unbiased Learner
  • Futility of Bias-Free Learning
  • Inductive Bias
  • Inductive Biases of Algorithms
  • Summary
• Decision Tree Learning
  • Decision Tree Learning
  • Decision Tree
  • Learned Rules
  • When to use Decision Tree Learning
  • ID3 Algorithm
  • What Attribute is the Best Classifier?
  • Information Gain
  • Information Gain Example
  • Decision Tree Example
  • Partially Grown Tree
  • Final Tree
  • Searching in Decision Trees
  • ID3 Hypothesis Space
  • Inductive Bias in Decision Tree Learning
  • Restriction Biases and Preference Biases
  • Occam's razor
  • Avoiding Overfitting
  • Overfitting in Decision Trees
  • Approaches to Overfitting
  • Reduced Error Pruning
  • Impact of Reduced Error Pruning
  • Rule Post Pruning
  • Improved Estimated Accuracy
  • Why convert to rules?
  • Continuous Valued Attributes?
  • Example
  • Other Measures for Picking Attributes
  • Problems with Gain Ratio
  • Missing Attribute Values in Train. Ex.
  • Attributes with Differing Costs
  • Summary
  • Summary continued
• Neural Network Learning
  • Artificial Neural Networks
  • Human Brain
  • Neural Network Representations
  • ALVINN Neural Network
  • Backpropagation Network Representations
  • Appropriate Problems for ANN
  • Perceptrons
  • A Perceptron
  • Linearly Separable
  • Representational Power of Perceptrons
  • Perceptron Learning Algorithms
  • Perceptron Training Rule
  • Intuition for Perceptron Training Rule
  • Gradient Descent Algorithm
  • Weight Update Rule
  • Training Error
  • Gradient-Descent Algorithm
  • Problems with Gradient Descent
  • Stochastic Gradient Descent
  • Differences between GD and SGD
  • Delta Rule vs. Perceptron Training Rule
  • Multilayer Networks & Nonlinear Surfaces
  • Multilayer Networks
  • Sigmoid Threshold Unit
  • Properties of the Backpropagation Algo.
  • Backpropagation Algorithm
  • Backpropagation Weight Training Rule
  • Termination Conditions for Backprop
  • Momentum
  • Arbitrary Acyclic Networks
  • Convergence and Local Minima
  • Heuristics to Overcome Local Minima
  • Representational Power of Feedforward Networks
  • Hypothesis Space & Inductive Bias
  • Hidden Layer Representations
  • Backprop in Action
  • Overfitting and Stopping Criteria
  • Error Plots
  • Face Recognition Task
  • Input Encoding
  • Output Encoding
  • Network Graph Structure
  • Other Algorithm Parameters
  • Learned Hidden Representations
  • Advanced Topics
  • Summary
• Instance-Based Learning
  • Instance-Based Learning
  • K-Nearest Neighbor Learning
  • K-Nearest Neighbor Algorithm
  • K-Nearest Neighbor Hypothesis Space
  • Distance Weighted Nearest Neighbor Algo
  • Remarks on k-nearest neighbor
  • Locally Weighted Regression
  • Remarks on Locally Weighted Regression
  • Radial Basis Functions
  • Radial Basis Function Network
  • Case Based Reasoning
  • CADET system
  • Problems with Case Based Reasoning
  • Lazy Versus Eager Learning
  • Summary
• Evaluating Hypothesis and Experimental Design
  • Evaluating Hypothesis
  • Estimating Hypothesis Accuracy
  • Problems with Estimating Accuracy
  • Four Important Sources of Error
  • Dealing with Error
  • Statistical Questions in Machine Learning?
  • Question Assumptions
  • Question 1
  • Confid. Intervals for Disc. Val. Hyp.
  • Question 3
  • Comparing Learning Algorithms
  • Problems with McNemar
  • Question 5
  • Question 6
  • 10-fold Cross Validation
  • Question 7
  • Question 8
  • Comparing Algorithms w/ Small Samples
  • Question 9
  • Why or When Accuracy?
  • Four Spurious Effects?
  • Summary
• Genetic Algorithms
  • Motivation
  • Popularity
  • Genetic Algorithms
  • General Method
  • Genetic Algorithm
  • Algorithm Properties
  • Additional Algorithm Properties
  • Representing Hypotheses
  • Representations II
  • Representations III
  • Genetic Operators
  • Crossover & Mutation
  • Fitness Function and Selection
  • GABIL System
  • GABIL Representation
  • GABIL Genetic Operators
  • Genetic Operator Example
  • GABIL Fitness Function
  • GABIL Extensions
  • Evolving Search Methods
  • Hypothesis Space Search
  • Crowding
  • Population Evolution
  • Schema Theorem
  • Schema Theorem Intuition
  • Genetic Programming
  • Crossover of Program Trees
  • Genetic Programming Example
  • Primitive Functions
  • Experiment Results
  • Models of Evolution
  • Baldwin Effect
  • Parallelizing Genetic Algorithms
  • Summary
  • Summary Cont.
• Bayesian Learning
  • Introduction
  • Bayes Theorem
  • A General Example
  • Bayes Theorem & Concept Learning
  • MAP Hypotheses and Consistent Learners
  • Maximum Likelihood & Least-Squared Error
  • Maximum Likelihood for Predicting Probabilities
  • Gradient Search to Maximize Likelihood in ANN
  • Minimum Description Length
  • Bayes Optimal Classifier
  • Gibbs Algorithm
  • Naive Bayes Classifier
  • An Example
  • Estimating Probabilities
  • Learning to Classify Text
  • Learn Naive Bayes Text Algorithm
  • Experimental Results
  • Bayesian Belief Networks
  • A Bayesian Belief Network
  • Representation
  • Inference
  • Learning BBNs
  • Gradient Ascent Training of BBN
  • Learning BBN Structure
  • EM Algorithm
  • Estimating Means of Gaussians
  • -means Problem Visualization
  • Practical Implementation for -means EM
  • Summary
• Reinforcement Learning
  • Agents
  • General Problem
  • Reinforcement Learning Problems
  • Learning Task
  • Optimal Policy
  • Grid-world
  • Finding Optimal Policies
  • Q Learning
  • Q Learning Properties
  • Q learning Algorithm
  • Illustrative Example
  • Convergence
  • Experimentation Strategies
  • Updating Sequence
  • Nondeterministic Rewards and Actions
  • Temporal Difference Learning
  • Generalizing from Examples
  • Relationship to Dynamic Programming
  • Summary
• Learning Sets of Rules
  • Motivation
  • Sequential Covering
  • Sequential Covering Algorithm
  • How to Learn-One-Rule
  • General to Specific Beam Search
  • Variation
  • Design Choices in Learning Rule Sets
  • Exhaustive Rule Learning - Brute
  • Other Brute Features
  • Learning First Order Rules
  • First Order Horn Clauses
  • Terminology
  • FOIL
  • FOIL Algorithm
  • Differences between FOIL & Sequential COvering
  • Generating Candidate Specializations
  • Example
  • Guiding Search in FOIL
  • Evaluation Function
  • Learning Recursive Rule Sets
  • Summary of FOIL
  • Induction as Inverted Deduction
  • Example
  • Inverse Entailment Operators
  • Inverting Resolution
  • Resolution
  • First Order Resolution
  • Example
  • 1st Order Resolution Rule
  • Inverting First Order Resolution
  • Inverse Example
  • Summary Inverse Resolution
  • Generalization,Subsumption,Entailment
  • Inverse Example
  • Progol
  • Summary
• Ensembles
  • Ensembles of Classifiers
  • Probability that Majority Vote is Wrong
  • Constructing Ensembles
  • Manipulating the Input Features
  • Manipulating the Output Target
  • Injecting Randomness
  • Algorithm Specific Methods
  • Combining Different Algorithms
  • Combining Classifiers
  • Why Ensembles Work
  • Decision Boundary
  • Open Problems
• About this document ...