Instanced Based Learning

Content

• Parzen windows

  • Basic idea (smoothing over empirical average)
  • Kernels

• Model selection

  • Overfitting and underfitting
  • Crossvalidation and leave-one-out estimation
  • Bias-variance tradeoff
  • Curse of dimensionality

• Watson-Nadaraya estimators

  • Regression
  • Classification

• Nearest neighbor estimator

  • Limit case via Parzen
  • Fast lookup

Supplementary material

Slides available in PDF and Keynote. If you want to extract the equations from the slides you can do so by using LaTeXit, simply by dragging the equation images into it.

• Cover tree homepage
• Kd-trees paper
• Andrew Moore’s tutorial https://www.ri.cmu.edu/pub_files/pub1/moore_andrew_1991_1/moore_andrew_1991_1.pdf on Kd-trees
• Nadaraya’s paper from 1964
• Watson’s paper from 1964
• Watson-Nadaraya regression package R
• Stone’s k-NN regression consistency proof
• Cover and Hart’s k-NN classification consistency proof
• Sanjoy Dasgupta’s analysis for k-NN estimation with selective sampling
• Multiedit and Condense by Dasarathy, Sanchez, Townsend
• Geometric approximation via core sets

Videos

This is unedited video straight from a Lumix GH2 with a 12-42mm kit lens and built in microphone (which should explain the sound) … But it should help as a supplement with the slides.