Guide-linked quiz · Hard Level

VC Dimension and PAC Learning Quiz

Tests shattering, VC dimension, agnostic PAC sample complexity, and why worst-case guarantees can be looser than observed model performance.

Question 1 of 8

For three points to be shattered by a binary hypothesis class, what must the class be able to realize?

Preview every question8 questions

Answers and explanations appear as you take the quiz.

  1. For three points to be shattered by a binary hypothesis class, what must the class be able to realize?
    • The class can correctly classify all n points on unseen test data
    • The class contains exactly n hypotheses
    • The points are linearly separable by exactly one hypothesis
    • For every one of the 2^n possible labelings of those points, some hypothesis in the class reproduces it exactly
  2. For straight-line binary classifiers in a two-dimensional plane, how many points can be shattered at most?
    • 1
    • 3
    • 2
    • 4
  3. In the agnostic PAC setting described in the guide, how does a standard worst-case sample bound depend on VC dimension and epsilon?
    • Sample size needed scales roughly with VC-dimension divided by epsilon squared
    • Sample size needed decreases as VC dimension increases
    • Sample size needed is independent of VC dimension
    • Sample size needed depends only on the number of features, never on VC dimension
  4. Why is a single-threshold classifier on the real line said to have VC dimension 1?
    • It has one parameter, t, so its VC dimension equals its parameter count
    • It can only classify positive examples
    • It can shatter exactly one point but not every arrangement of two points
    • It has an infinite VC dimension since t can be any real number
  5. Is VC dimension the same thing as the number of parameters in a model, according to the guide?
    • Yes, they are always identical
    • Yes, but only for linear models
    • No, VC dimension only applies to neural networks
    • No; some infinite-parameter classes have finite VC dimension and some low-parameter models can have high VC dimension
  6. What theoretical result explains why the growth function becomes only polynomial in n once n exceeds the VC dimension?
    • Sauer's lemma
    • The central limit theorem
    • Bayes' theorem
    • The law of large numbers
  7. Why do classical VC-dimension-based PAC bounds struggle to explain deep neural network generalization?
    • Neural networks have zero VC dimension
    • PAC theory does not apply to any parametric models
    • Neural networks' VC dimension is often far larger than practical training set sizes, yet they still generalize well
    • Neural networks cannot be represented as hypothesis classes
  8. What kind of guarantee does PAC learning provide about a learned hypothesis?
    • That it will have exactly zero error
    • That with high probability its error is within some epsilon of the best hypothesis in the class
    • That it will always outperform every other hypothesis class
    • That it requires no training data at all

Keep testing yourself

More quizzes picked for your level.

View all quizzes