Basic Tools

Content

• Linear regression

  • Optimization problem
  • Examples
  • Overfitting

• 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

Video

Annotated video is here.

Also see the first part of lecture 3.

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