Page cover image

#2: Feasibility of Learning

  • 4 min

#2: Feasibility of Learning content

Created
Topics
🎯
Feasibility of Learning
Previous Lecture Recap

Components of a Learning System

Goal of learning uses the dataset to find gg that approximates the target function ff

Perception Learning Algorithm (PLA)

notion image

Why is the feasibility of learning questionable?

Problem of Learning

Candidates functions converges on seen input & outputs
But diverges on unseen examples

Learning Theory

We cannot find a function gg that deterministically replicates ff
We can only give probability estimates:
  • gg approximates ff with probability if unseen examples are drawn in the same way

The Bin Experiment

Given a bin of red & blue balls where P(red)=μP(\text{red})=\mu and P(blue)=1−μP(\text{blue})=1-\mu
  • μ\mu is unknown
Experiment: perform random sampling & record the sample proportion
  • Let νν denote the fraction of red balls in sample of size NN

Hoeffding Inequality

P[∣ν−μ∣>ϵ]≤2e−2ϵ2N\mathbb{P}[|\nu-\mu|>\epsilon] \leq 2 e^{-2 \epsilon^{2} N}

Interpretation

  • For large NN , probability that μ\mu and νν being close to each other is high
  • Tradeoff between sample size NN and closeness of approximation ϵ \epsilon
    • N↑\uparrow ⇒ right↓\downarrow ⇒ probability↓\downarrow ⇒ closeness ↓\downarrow
  • Not dependent on μ\mu

Connection to Learning

Consider some pre-selected hypothesis h∈Hh\in \mathscr{H}
μ=P[h(x)≠f(x)]≡Eout (h) Out-of-sample error ν=1N∑i=1N[h(xi)≠f(xi)]≡Ein(h) In-sample error \begin{aligned}&\mu=\mathbb{P}[h(x) \neq f(x)] \equiv E_{\text {out }}(h) & \text { Out-of-sample error } \\&\nu=\frac{1}{N} \sum_{i=1}^{N}\left[h\left(x_{i}\right) \neq f\left(x_{i}\right)\right] \equiv E_{i n}(h) & \text { In-sample error }\end{aligned}
Then for some fixed hh:
P[∣Ein(h)−Eout(h)∣>ϵ]≤2e−2ϵ2N\mathbb{P}\left[\left|E_{i n}(h)-E_{o u t}(h)\right|>\epsilon\right] \leq 2 e^{-2 \epsilon^{2} N}
For a hypothesis hh fixed before looking at the data, the probability of the in-sample error deviating from out-of-sample error is low, if samples are independent using some probability distribution PP
  • Single fixed hypothesis
  • Hypothesis space H\mathscr{H}
  • Verification, not learning
  • hh must be selected b4 seeing data
  • Need to guarantee g∈Hg\in \mathcal{H} obtained after seeing data

Generalization to Multiple Hypotheses

Estimates for a function g∈{h1,h2,…,hM}=Hg \in\left\{h_{1}, h_{2}, \ldots, h_{M}\right\}=\mathscr{H}
P[∣Ein(g)−Eout (g)∣]≤∑m=1MP[∣Ein(hm)−Eout (hm)∣>ϵ]≤∑m=1M2e−2ϵ2N≤2Me−2ϵ2N\begin{aligned}\mathbb{P}\left[\left|E_{i n}(g)-E_{\text {out }}(g)\right|\right] & \leq \sum_{m=1}^{M} \mathbb{P}\left[\left|E_{i n}\left(h_{m}\right)-E_{\text {out }}\left(h_{m}\right)\right|>\epsilon\right] \\& \leq \sum_{m=1}^{M} 2 e^{-2 \epsilon^{2} N} \\ & \leq 2 M e^{-2 \epsilon^{2} N}\end{aligned}
The bound on the right-side is loose by MM

Summary

Goal: approximate the unknown function ff
Steps
  1. Provide a finite training set
    • Assume each example independent
    • Population has distribution PP
  1. Identify a hypothesis set H\mathscr{H} to pick gg
  1. Bound the difference between in-sample and out-of-sample errors
    • Assuming unseen samples are drawn with same distribution
    • Hoeffding Inequality: if we can bring the in-sample error towards zero we can probabilistically guarantee that out-of-sample error will not be far either
    • ⇒ gg will probabilistically approximate ff
 

Two primary questions in learning

notion image

Complexity of H\mathscr{H}

MM = complexity of hypothesis space

Notes

Neural networks can approxiamate all functions
If complex enough & has enough data ⇒ Ein(g)≈0E_{in}(g)\approx 0

If Complexity of H\mathscr{H} is too high: Overfitting Occurs

notion image

Measuring Complexity of H\mathscr{H}

VC Dimension (Not covered)
  • Bias-Variance (Next Lecture Sep 9, 2021)

ML in Practice

Training Set

Use to tune the parameters of the model (search for the hypothesis)

Validation Set

Test the goodness of the running hypothesis
  • Used to track the performance throughout learning
  • Surrogate of the performance on unseen examples
  • Information in this set is still being used to update the modal, though not used directly

Test Set

test data is used to measure the final performance of the model
  • No going back after this

Assumption

Dataset is representative of the real world

Error Measures (Loss Functions)

Goodness of a model is measured by classification error
E(h,f)=∑i=1Ne(h(xi),f(xi))2E(h, f)=\sum_{i=1}^{N} e\left(h\left(x_{i}\right), f\left(x_{i}\right)\right)^{2}

Other Error Measures

Binary classification error: e(h,f)=[h(x)≠f(x)]e(h, f)=[h(x) \neq f(x)]
Squared error: e(h,f)=(h(x)−f(x))2e(h, f)=(h(x)-f(x))^{2}
Cross-entropy loss: −[ylog⁡p+(1−y)log⁡(1−p)]-[y \log p+(1-y) \log (1-p)]

In Practice

Defined by the user
Problem dependent
Decides which hypothesis gets selected at the end
Different error measures can lead to different hypothesis

Example

notion image
Notion: use the loss function to penalize the most costly mistakes

Noisy Targets

In reality, the mapping x→yx → y is rarely deterministic
  • A data point (x,y)(x, y) is now generated by a joint distribution P(x,y)=P(x)P(y∣x)P(x, y) = P(x)P(y|x)
  • P(x)P(x) = Input Distribution: relative importance of the input samples
  • P(y∣x)P(y|x) = Target Distribution: interested in finding out
  • Probabilistic, not deterministic

Conclusion: Components of a Learning System

notion image