Viveckh's Notepad

# Computational Learning Theory

  • Defining learning problems
  • Showing specific algorithms work
  • Show these problems are fundamentally hard

# Resources that matter

  • time
  • space
  • samples

# Defining Inductive Learning

Learning from examples

  • Probability of successful training
  • Number of examples to train on
  • Complexity of hypothesis class
  • Accuracy to which target concept is approximated
  • Manner in which training examples presented
  • Manner in which training examples selected

# Selecting training examples

  • Learner asks questions to teacher
  • Teacher gives examples to help learner
  • Fixed distribution
  • Evil distribution

# VC Dimensions Playlist

# Infinite Hypothesis Spaces

Hypothesis spaces are infinite for Linear separators, artificial neural networks, and decision trees with continous inputs but finite for decision trees with discrete inputs.

← Randomized Optimization →