Skip to content

21 Perceptron Algorithm and Logistic Regression

from last lecture

Overfitting

  • the different models that we have, you can always have a model that always fits the training data exactly
  • follows the data curve, etc.

dont want to underfit (horizontal line) underfit (15 degree polynomial)

underfit: horizontal line          overfit: 15-degree polynomial

   ·    ·   ·    ·                     ·    ·   ·    ·
  ──────────────────                   \  /\      /\  /
   ·   ·    ·   ·                        \/  \__ /  \/
 (misses the pattern)                  (chases every point)

assume we are trying to classify this digit, where if we are determining between a 2 or a 3 given that the number is 2, the label would be 3 all the way till the bottom, because of one extra pixel turned on at the end, the probability of being classified as label 3 is 0 even though before that pixel it was so important

# why one unseen pixel zeroes the whole class score
# naive bayes multiplies P(Y) by every P(F_i | Y)
p_y = 0.1
# this pixel value was never seen with label 3 in training -> count 0 -> prob 0
p_pixel_unseen = 0
# one zero factor collapses the entire product
p_y * 0.8 * 0.7 * 0.9 * p_pixel_unseen =>

Generalization and overfitting

parameter estimation

  • estimating the distribution of a random variable
  • Elicitation: as a human (why is this hard?)
  • Empirically: use training data (learning!)
  • eg. for each outcome \(x\), look at the empirical rate of that value
  • Maximum likelihood estimate
  • \(P_{ML} = \dfrac{\text{count}(x)}{\text{total samples}}\)
  • this estimate maximizes the likelihood of data
# maximum likelihood = count / total
# e.g. rain observed on 18 of 30 days
count_rain = 18
total = 30
count_rain / total =>

Maximum Likelihood?

  • relative frequencies are the maximum likelihood estimates
  • \(\theta_{ML} = \arg\max_\theta P(X|\theta)\)
  • \(= \arg\max_\theta \prod_i P_\theta(X_i)\)
  • another option is to consider the most likely parameter given the data
  • \(\theta_{MAP} = \arg\max_\theta P(\theta|X)\)
  • \(= \arg\max_\theta P(X|\theta)P(\theta)\)
\[P(p_{0:N-1} \mid r_{0:N-1}, c_{0:N-1}) = \frac{P(p_{0:N-1}, r_{0:N-1}, c_{0:N-1})}{P(r_{0:N-1}, c_{0:N-1})}\]
\[P(p_{0:N-1}, r_{0:N-1}, c_{0:N-1}) = \sum_{w} \sum_{s_{0:N-1}} \sum_{a_{0:N-1}} P(w, s_{0:N-1}, p_{0:N-1}, r_{0:N-1}, c_{0:N-1}, a_{0:N-1})\]
  • Perceptron — same perceptron update rule, extended to logistic regression

Two flags: your fit line reads "underfit (horizontal line) underfit (15 degree polynomial)" — the second should be overfit (a 15-degree polynomial is the classic overfit case). And I completed the MAP line to \(\arg\max_\theta P(X|\theta)P(\theta)\) — without the \(P(\theta)\) prior term, MAP collapses back into plain MLE, so the prior is the whole point of the distinction.