PAC Learning and VC Dimension
1. Who introduced the PAC Learning model?
A) Geoffrey Hinton
B) Leslie Valiant
C) Yann LeCun
D) Andrew Ng
Answer: B
Explanation: Leslie Valiant introduced the Probably Approximately Correct framework in his 1984 paper “A Theory of the Learnable.”
2. In PAC learning, what does “Probably” refer to?
A) Accuracy of hypothesis
B) Training time
C) Confidence (1−δ)
D) Error rate
Answer: C
Explanation: “Probably” means the guarantee holds with probability at least 1−δ over the random draw of training samples.
3. In PAC learning, the “Approximately” refers to:
A) Training samples
B) Model complexity
C) Error bound (ε)
D) Model runtime
Answer: C
Explanation: “Approximately correct” means the learned hypothesis has true error at most ε, not necessarily zero error.
4. The instance space in PAC learning is commonly defined as:
A) Real numbers
B) Text data
C) Binary vectors of length n
D) Images
Answer: C
Explanation: In the classical Boolean formulation, instances are vectors in {0,1}ⁿ, i.e., assignments to n Boolean variables.
5. What is the range of the concept function c: X → ?
A) {−1, 1}
B) {0, 1}
C) {0, ∞}
D) ℝ
Answer: B
Explanation: A concept is a Boolean function labeling each instance as positive (1) or negative (0).
6. What kind of distribution are training examples drawn from in PAC learning?
A) Gaussian distribution
B) Unknown but fixed distribution
C) Uniform distribution
D) Zipf distribution
Answer: B
Explanation: PAC guarantees are distribution-free: examples come i.i.d. from an arbitrary but fixed distribution D that the learner does not know.
7. What is the meaning of a hypothesis being “PAC correct”?
A) Exact match with the concept
B) Zero error
C) Approximately correct with high probability
D) Derived through a neural net
Answer: C
Explanation: The hypothesis has error ≤ ε with probability ≥ 1−δ — the two relaxations that make learning feasible.
8. What is the full form of PAC in PAC learning?
A) Precise and Clear
B) Probably Accurate Concept
C) Probably Approximately Correct
D) Practically Accurate Classification
Answer: C
Explanation: PAC = Probably (confidence 1−δ) Approximately (error ≤ ε) Correct.
9. Which of the following classes did Valiant show to be efficiently learnable in his framework (membership queries permitted)?
A) General DNF
B) Boolean Circuits
C) Monotone DNF
D) RSA Functions
Answer: C
Explanation: Valiant’s 1984 paper gives a polynomial-time algorithm for monotone DNF using membership queries, while general DNF and Boolean circuits remain hard.
10. The VC dimension quantifies:
A) Runtime of algorithm
B) Number of training epochs
C) Complexity of hypothesis class
D) Dimensionality of features
Answer: C
Explanation: VC dimension is the size of the largest instance set the hypothesis class can shatter — a combinatorial measure of the class’s expressive capacity.
11. What is the output of a PAC learning algorithm?
A) A neural network
B) A set of training data
C) A hypothesis from the hypothesis class
D) A random classifier
Answer: C
Explanation: The learner must output some h ∈ H whose error is bounded; the framework is about hypothesis selection, not any specific model type.
12. The EXAMPLES routine provides:
A) Noisy examples
B) Human-labeled inputs
C) Random labeled examples
D) Negative-only examples
Answer: C
Explanation: EXAMPLES draws a random instance from distribution D and returns it with its correct label under the target concept.
13. A hypothesis class H is said to “shatter” a set of points if:
A) H contains exactly one hypothesis for the set
B) Hypotheses in H can realize every possible labeling (dichotomy) of those points
C) All hypotheses in H misclassify the set
D) The set has more points than |H|
Answer: B
Explanation: Shattering means that for all 2ᵐ ways of labeling m points, some hypothesis in H produces that labeling — the concept on which VC dimension is defined.
14. Sample complexity in PAC learning is mainly influenced by:
A) Number of layers in model
B) VC dimension
C) Number of CPUs
D) Type of activation function
Answer: B
Explanation: The fundamental theorem of PAC learning shows required sample size grows essentially linearly with the VC dimension (plus terms in 1/ε and ln(1/δ)).
15. What is the key assumption in standard PAC learning?
A) Noise in labels
B) Non-linear data
C) i.i.d. sampled examples
D) Deep learning model
Answer: C
Explanation: Training and future examples must be drawn independently from the same fixed distribution; without i.i.d., the error guarantee has no meaning.
16. The VC dimension of the class of linear classifiers (halfspaces) in ℝ² is:
A) 2
B) 3
C) 4
D) Infinite
Answer: B
Explanation: A line in the plane can shatter some set of 3 points (in general position) but no set of 4 (e.g., the XOR labeling of 4 points is unrealizable), and in general halfspaces in ℝᵈ have VC dimension d+1.
17. What does the ORACLE routine allow a learning algorithm to do?
A) Predict labels
B) Query whether an instance is positive
C) Delete hypotheses
D) Return VC dimension
Answer: B
Explanation: The membership oracle answers, for any instance the learner constructs, whether the target concept labels it positive — an active query, unlike passive EXAMPLES.
18. The VC dimension of axis-aligned rectangles in the plane is:
A) 2
B) 3
C) 4
D) 5
Answer: C
Explanation: Four points in a diamond arrangement can be shattered by axis-aligned rectangles, but for any 5 points the labeling that marks the four extreme points positive and the enclosed fifth negative is unrealizable.
19. In agnostic PAC learning, the learner’s goal changes to:
A) Achieving zero training error
B) Finding a hypothesis whose error is close to the best achievable within the hypothesis class, without assuming the target is in the class
C) Learning without any samples
D) Memorizing the training set
Answer: B
Explanation: Agnostic learning drops the realizability assumption: no hypothesis may fit the data perfectly, so the benchmark becomes the minimum error over H rather than zero.
20. What happens to sample complexity as VC-dim increases?
A) Decreases
B) Remains constant
C) Increases
D) Becomes independent of error
Answer: C
Explanation: Richer hypothesis classes can fit more sample patterns spuriously, so more examples are needed to pin down a hypothesis with the same ε, δ guarantee.
21. Which condition implies that some Boolean functions are not PAC-learnable?
A) VC-dim = 0
B) Neural net is shallow
C) Cryptographic hardness assumptions
D) Finite sample space
Answer: C
Explanation: If one-way functions (e.g., RSA-style assumptions) exist, then classes like Boolean circuits encode cryptographic secrets and cannot be learned in polynomial time.
22. Why is the general DNF class not known to be PAC-learnable?
A) Requires infinite data
B) Algorithm doesn’t exist
C) It’s NP-hard in general
D) No hypothesis class defined
Answer: C
Explanation: Finding a small consistent DNF formula is computationally intractable (NP-hard), so no polynomial-time proper learner is known despite decades of effort.
23. The presence of noise in data led to the development of which PAC extension?
A) Incremental PAC
B) Bayesian PAC
C) Noisy PAC
D) Approximate PAC
Answer: C
Explanation: Noise-tolerant PAC models (e.g., random classification noise, agnostic learning) relax the assumption that labels are perfectly consistent with the target concept.
24. For PAC learning, which of the following guarantees is false?
A) Output hypothesis is always 100% accurate
B) Hypothesis has error ≤ ε with probability ≥ 1−δ
C) Uses i.i.d. samples
D) Time and sample bounds are polynomial
Answer: A
Explanation: PAC explicitly abandons the demand for perfect accuracy — only approximate correctness with high probability is guaranteed.
25. In a concept class with infinite VC-dimension:
A) Learning is guaranteed
B) Sample complexity becomes unbounded
C) Only one-sided error is allowed
D) ORACLE queries are unnecessary
Answer: B
Explanation: The fundamental theorem states finite VC dimension is necessary and sufficient for PAC learnability, so infinite VC dimension means no finite sample size suffices.
Regression: Foundations and Scatterplots
26. What kind of regression is most widely used due to its simplicity and interpretability?
A) Logistic Regression
B) Polynomial Regression
C) Linear Regression
D) Ridge Regression
Answer: C
Explanation: Linear regression’s parameters have direct interpretations (change in Y per unit X), making it the default first model in applied statistics.
27. Which of the following is a key visual tool used before applying regression?
A) Line graph
B) Scatterplot
C) Pie chart
D) Histogram
Answer: B
Explanation: Plotting (x, y) pairs as a scatterplot reveals linearity, spread, outliers, and leverage points before any model is fitted.
28. Which element in regression is usually denoted by β₀?
A) Slope
B) Residual
C) Intercept
D) Mean
Answer: C
Explanation: β₀ is the intercept — the expected value of Y when the predictor x equals zero.
29. What is the slope in the linear equation E(Y | X = x) = β₀ + β₁x?
A) β₀
B) β₁
C) X
D) Y
Answer: B
Explanation: β₁ multiplies x, so it is the slope — the change in the expected response per one-unit increase in the predictor.
30. Which type of points strongly influence the regression line due to extreme X-values?
A) Outliers
B) Leverage points
C) Influential residuals
D) Mean points
Answer: B
Explanation: Points far from the mean of X have high leverage: the fitted line pivots toward them because their extreme x-position gives them outsized weight.
31. Why was jittering used in the scatterplot of mother–daughter heights?
A) To show non-linearity
B) To reduce variance
C) To prevent point overlapping
D) To remove outliers
Answer: C
Explanation: Heights were recorded to rounded values, so many identical pairs would overprint; adding small random displacement makes each observation visible.
32. In the bass growth study, what does the mean function describe?
A) Maximum fish size
B) Average length by age
C) Fastest growing fish
D) Fish with anomalies
Answer: B
Explanation: The mean function E(length | age = x) traces the average fish length at each age, summarizing the trend across ages.
33. What kind of regression line would best represent a perfect positive correlation?
A) Curved upward
B) Horizontal
C) Downward-sloping
D) 45-degree upward sloping line
Answer: D
Explanation: With standardized/equally-scaled axes, a perfect positive linear relationship places all points exactly on an upward line — the 45-degree line.
34. In the regression formula, which variable is usually plotted on the Y-axis?
A) Predictor
B) Independent variable
C) Response variable
D) Constant
Answer: C
Explanation: Convention places the response (dependent) variable on the vertical axis and the predictor on the horizontal axis.
35. Which historical dataset showed a poor linear fit until transformed?
A) Galton height data
B) Turkey weight data
C) Forbes’s boiling point data
D) Flagstaff snowfall data
Answer: C
Explanation: Forbes’s boiling-point/pressure data showed curvature and non-constant spread until pressure was log-transformed, after which the fit became nearly perfectly linear.
36. In the height study, what does a slope less than 1 in the regression line suggest?
A) No variation
B) Negative correlation
C) Regression to the mean
D) High randomness
Answer: C
Explanation: A slope below 1 means daughters of unusually tall (or short) mothers are, on average, less extreme than their mothers — Galton’s regression to the mean.
37. Which variable in E(Y | X = x) represents the expected average of Y?
A) Y
B) X
C) E(Y | X = x)
D) β₁
Answer: C
Explanation: The whole expression E(Y | X = x) is the conditional expectation — the population average of Y among cases with predictor value x.
38. What is the effect of assuming constant variance in a regression model?
A) It increases complexity
B) It avoids outliers
C) It simplifies calculations
D) It distorts predictions
Answer: C
Explanation: Homoscedasticity lets ordinary least squares weight all observations equally, greatly simplifying estimation and inference formulas.
39. Which of the following is NOT a common goal of regression analysis?
A) Making predictions
B) Measuring central tendency
C) Identifying relationships
D) Testing hypotheses
Answer: B
Explanation: Central tendency (mean/median of a single variable) is univariate description; regression’s goals concern the relationship between variables.
40. In regression, what does an outlier typically affect the most?
A) Mean of predictor
B) Linearity
C) Slope accuracy
D) Variance of X
Answer: C
Explanation: A response outlier pulls the least-squares line toward itself, biasing the estimated slope — the coefficient practitioners most rely on.
41. What does the variance function Var(Y | X = x) measure?
A) The number of observations
B) Spread of Y for fixed X
C) Growth rate of Y
D) Constant term in the model
Answer: B
Explanation: It quantifies how much individual Y values scatter around their conditional mean at each particular value of X.
42. What is the term for visual representations showing each data pair as a point?
A) Dot matrix
B) Correlation map
C) Scatterplot
D) Area graph
Answer: C
Explanation: A scatterplot marks one point per (x, y) observation, making it the fundamental display of bivariate data.
43. In regression, a residual is defined as:
A) The predicted value of Y
B) The difference between the observed value and the fitted (predicted) value of Y
C) The slope of the regression line
D) The variance of X
Answer: B
Explanation: Residual eᵢ = yᵢ − ŷᵢ measures how far each observation falls from the fitted line, and residual analysis is the primary tool for checking model assumptions.
44. What concept explains that tall mothers may have slightly shorter daughters?
A) Linearity
B) Equal scaling
C) Regression to the mean
D) High leverage
Answer: C
Explanation: Extreme values of an imperfectly correlated trait tend to be followed by values closer to the population average in the next generation.
45. What does “E” stand for in the expression E(Y | X = x)?
A) Error
B) Expected
C) Equal
D) Estimate
Answer: B
Explanation: E denotes mathematical expectation — the (conditional) mean of the random variable Y.
46. What insight does a good scatterplot provide before modeling?
A) Median
B) Model accuracy
C) Data coding
D) Strength and direction of relationship
Answer: D
Explanation: The point cloud’s tightness shows strength and its tilt shows direction (positive/negative), guiding the choice and form of the model.
47. If the slope β₁ of a simple linear regression equals zero, it means:
A) Y is always zero
B) The predictor X provides no linear information about the mean of Y
C) The intercept must also be zero
D) The variance of Y is zero
Answer: B
Explanation: With β₁ = 0 the mean function reduces to E(Y|X=x) = β₀, a horizontal line — the expected response is the same regardless of x.
48. Which kind of regression would you use if the data shows a curved trend?
A) Simple linear regression
B) Log-transformed regression
C) Constant regression
D) Slope-normalized regression
Answer: B
Explanation: Transforming a variable (commonly with logarithms) can straighten a curved relationship so linear methods apply — exactly the remedy used for Forbes’s data.
49. What is one benefit of plotting equal axes when predictor and response have similar scales?
A) Better coloring
B) Better visibility of noise
C) Fair visual comparison
D) Removal of outliers
Answer: C
Explanation: Equal axis scaling means a slope of 1 appears as 45 degrees, so departures from exact correspondence (like regression to the mean) are judged fairly by eye.
50. Which statistical method forms the base for many advanced predictive models?
A) Chi-square test
B) Clustering
C) Linear regression
D) t-test
Answer: C
Explanation: Generalized linear models, regularized methods, and even neural networks build conceptually on the linear regression framework of a parameterized mean function.
Mean Function and Variance Function
51. What does the mean function E(Y|X=x) represent?
A) The maximum value of Y for given X
B) The expected (average) value of Y given X = x
C) The variance of Y given X = x
D) The slope of the relationship between X and Y
Answer: B
Explanation: It is the conditional average of the response among all cases sharing the predictor value x — the central object regression models.
52. In the linear mean function E(Y|X=x)=β₀+β₁x, what does β₀ represent?
A) The slope of the line
B) The intercept (value of Y when X = 0)
C) The variance of Y
D) The residual error
Answer: B
Explanation: Setting x = 0 leaves only β₀, so it is the expected response at predictor value zero — the line’s intercept.
53. In the Galton height data, if height were perfectly inherited, what slope would the mean function have?
A) 0
B) 0.5
C) 1
D) Greater than 1
Answer: C
Explanation: Perfect inheritance means each daughter’s expected height equals her mother’s, i.e., E(Y|X=x)=x — a line of slope exactly 1.
54. What does a slope less than 1 in the regression line between mother’s and daughter’s heights indicate?
A) Perfect inheritance of height
B) Regression to the mean
C) No relationship between mother and daughter height
D) Random variation
Answer: B
Explanation: Daughters of extreme mothers average closer to the population mean than their mothers, which mathematically manifests as a fitted slope below 1.
55. What phenomenon explains why children of very tall or very short parents tend to be closer to average height?
A) Genetic drift
B) Regression to the mean
C) Environmental effect
D) Measurement error
Answer: B
Explanation: With imperfect correlation between generations, extreme parental values are partly due to chance that does not repeat, pulling offspring toward the mean.
56. Which variable is typically called the predictor in a regression model?
A) Y
B) X
C) β₀
D) The residual
Answer: B
Explanation: X is the predictor (independent/explanatory variable) used to explain or predict the response Y.
57. What does the variance function Var(Y|X=x) describe?
A) The average value of Y at X = x
B) The spread or variability of Y around its mean at X = x
C) The slope of the mean function
D) The intercept of the mean function
Answer: B
Explanation: At each fixed x, individual responses scatter around E(Y|X=x); the variance function measures the magnitude of that scatter.
58. What assumption about variance is commonly made in simple linear regression models?
A) Variance increases with X
B) Variance decreases with X
C) Variance remains constant for all X values
D) Variance is zero
Answer: C
Explanation: The standard model assumes Var(Y|X=x) = σ², the same for every x — the constant-variance (homoscedasticity) assumption.
59. If a fish’s length at age x is described by the mean function, what does the curve connecting average lengths at each age represent?
A) The variance function
B) The mean function E(length|age=x)
C) The residuals
D) The random noise
Answer: B
Explanation: Joining the average length at each age traces out exactly the estimated conditional mean — the mean function of length given age.
60. What does the slope β₁ in the mean function indicate?
A) The expected change in Y when X increases by one unit
B) The expected change in X when Y increases by one unit
C) The intercept value
D) The variance of Y
Answer: A
Explanation: Differentiating β₀+β₁x with respect to x gives β₁: each one-unit rise in the predictor shifts the expected response by β₁.
61. Why do we estimate β₀ and β₁ from data rather than knowing them beforehand?
A) Because they are constants
B) Because we never collect data
C) Because the exact relationship is usually unknown and must be learned from data
D) Because they represent random error
Answer: C
Explanation: The population parameters describe an unknown real-world relationship, so they must be inferred from sampled observations (e.g., by least squares).
62. Which of the following best describes “regression to the mean”?
A) Extreme values become more extreme over time
B) Extreme values tend to move closer to the average on subsequent measurements
C) Mean values never change
D) Variance always increases
Answer: B
Explanation: Because extremeness is partly luck, a repeat measurement or the next generation tends to be less extreme — closer to the population average.
63. In the Galton height example, what does the dashed line with slope 1 represent?
A) Actual data trend
B) Perfect inheritance where daughters’ heights equal mothers’ heights exactly
C) Random variation
D) Regression line estimated from data
Answer: B
Explanation: The slope-1 reference line marks the hypothetical case y = x; the actual fitted line’s shallower slope is what reveals regression to the mean.
64. What is the main purpose of the mean function in regression?
A) To describe the spread of data
B) To predict the average response Y for each predictor value X
C) To calculate residuals
D) To measure data skewness
Answer: B
Explanation: Regression’s central task is modeling how the average of Y changes with X, which is precisely what the mean function encodes.
65. When variance is constant across all values of X, the model is said to have:
A) Heteroscedasticity
B) Homoscedasticity
C) Nonlinearity
D) Autocorrelation
Answer: B
Explanation: Homoscedasticity (“same scatter”) is the term for equal conditional variance at every predictor value; unequal variance is heteroscedasticity.
K-Nearest Neighbors (K-NN)
66. In K-NN, what happens to the decision boundary as K increases?
A) Becomes more complex
B) Becomes smoother
C) Remains unchanged
D) Becomes discontinuous
Answer: B
Explanation: Larger K averages over more neighbors, reducing sensitivity to individual noisy points, producing smoother boundaries (lower variance, higher bias).
67. Why is feature scaling essential before applying K-NN?
A) It speeds up training
B) Distance metrics get dominated by large-range features without it
C) K-NN cannot handle negative values
D) It reduces the number of neighbors needed
Answer: B
Explanation: K-NN relies on distance computation, so an unscaled feature with a large numeric range (e.g., salary vs. age) dominates the distance and distorts neighbor selection.
68. K-NN is called a “lazy learner” because:
A) It has high test-time error
B) It builds no explicit model during training and defers all computation to prediction time
C) It converges slowly
D) It ignores some training samples
Answer: B
Explanation: K-NN simply stores training data; all distance computation happens at query time, unlike “eager” learners that fit a model up front.
69. For a 1-NN classifier, the training error is:
A) Always 0 (assuming no duplicate points with different labels)
B) Always equal to test error
C) Always 50%
D) Undefined
Answer: A
Explanation: Each training point’s nearest neighbor is itself (distance 0), so it is always classified by its own label, giving zero training error.
70. Choosing an even value of K in binary K-NN classification is discouraged because:
A) Computation doubles
B) Ties can occur in voting
C) The model underfits
D) Distance becomes negative
Answer: B
Explanation: With an even K, the two classes can receive equal votes, requiring an arbitrary tie-breaking rule.
Perceptron and Multi-Layer Perceptron
71. The perceptron learning algorithm is guaranteed to converge only when:
A) Data is normalized
B) The learning rate decays
C) The data is linearly separable
D) Weights start at zero
Answer: C
Explanation: The perceptron convergence theorem guarantees a finite number of mistakes only for linearly separable data; otherwise it cycles forever.
72. A single-layer perceptron cannot learn the XOR function because:
A) XOR needs more than two inputs
B) XOR is not linearly separable
C) The step function is non-differentiable
D) Weights cannot be negative
Answer: B
Explanation: XOR’s positive and negative examples cannot be divided by any single hyperplane, which is the only decision boundary a single-layer perceptron can represent.
73. In the perceptron update rule w ← w + η(y − ŷ)x, no update occurs when:
A) The learning rate is 1
B) The prediction is correct
C) The input is zero
D) Both A and C
Answer: B
Explanation: When y = ŷ, the error term (y − ŷ) is zero, so the weight vector remains unchanged.
74. What enables a multi-layer perceptron to model non-linear decision boundaries?
A) More training data
B) Non-linear activation functions in hidden layers
C) A larger learning rate
D) Weight initialization
Answer: B
Explanation: Without non-linear activations, any stack of layers collapses algebraically into a single linear transformation, so non-linearity in activations is what creates non-linear boundaries.
Support Vector Machines (SVM)
75. In SVM, the “support vectors” are:
A) All training points
B) The points lying closest to (or on) the margin boundaries that determine the hyperplane
C) Misclassified points only
D) The class centroids
Answer: B
Explanation: Only the margin-defining points have non-zero Lagrange multipliers; removing any non-support vector leaves the hyperplane unchanged.
76. The SVM optimization objective of minimizing ||w||²/2 corresponds to:
A) Minimizing training error
B) Maximizing the margin 2/||w|| between classes
C) Reducing the number of support vectors
D) Minimizing kernel complexity
Answer: B
Explanation: The geometric margin equals 2/||w||, so minimizing ||w|| is mathematically equivalent to maximizing the separation margin.
77. In soft-margin SVM, a very large value of C causes:
A) A wider margin with more violations tolerated
B) A narrower margin with fewer misclassifications tolerated, risking overfitting
C) All points to become support vectors
D) The kernel to become linear
Answer: B
Explanation: C is the penalty on slack variables, so large C punishes margin violations heavily, forcing the boundary to fit training points tightly (low bias, high variance).
78. The “kernel trick” in SVM allows:
A) Faster gradient descent
B) Computing dot products in high-dimensional feature space without explicitly mapping the data
C) Reducing support vectors
D) Avoiding regularization
Answer: B
Explanation: Kernels compute K(x, z) = φ(x)·φ(z) directly, giving the power of (possibly infinite-dimensional) feature spaces at the cost of only the kernel evaluation.
79. The RBF (Gaussian) kernel with a very small γ behaves like:
A) A nearly linear model, since each point’s influence extends very far
B) A nearest-neighbor model
C) A decision tree
D) An unstable model
Answer: A
Explanation: Small γ means large kernel bandwidth, so similarity decays slowly and the decision boundary becomes smooth and close to linear (high bias); large γ does the opposite.
Evaluation Metrics
80. A model predicts 90 of 100 actual positives correctly and produces 30 false positives. Its precision and recall are:
A) 0.75 and 0.90
B) 0.90 and 0.75
C) 0.90 and 0.90
D) 0.75 and 0.75
Answer: A
Explanation: Precision = TP/(TP+FP) = 90/120 = 0.75; Recall = TP/(TP+FN) = 90/100 = 0.90.
81. For a cancer-screening classifier where missing a positive case is far costlier than a false alarm, the metric to prioritize is:
A) Precision
B) Accuracy
C) Recall
D) Specificity
Answer: C
Explanation: Recall = TP/(TP+FN) directly measures the fraction of true positives captured, so maximizing it minimizes dangerous false negatives.
82. Why is accuracy a misleading metric on a dataset with 99% negative class?
A) Accuracy cannot exceed 99%
B) A trivial model predicting all-negative achieves 99% accuracy while detecting nothing
C) Accuracy requires balanced classes to compute
D) It ignores true negatives
Answer: B
Explanation: Accuracy weights all predictions equally, so the majority class swamps it, hiding total failure on the minority class; precision/recall/F1 expose this.
83. F1-score is the harmonic (not arithmetic) mean of precision and recall because:
A) It is easier to compute
B) The harmonic mean is dominated by the lower value, punishing imbalance between the two
C) It is always larger
D) Arithmetic mean is undefined for ratios
Answer: B
Explanation: Harmonic mean 2PR/(P+R) drops sharply when either P or R is low, so a model can’t score well by excelling at one and failing the other.
84. An AUC-ROC value of 0.5 indicates:
A) Perfect classification
B) Performance equivalent to random guessing
C) Perfectly inverted predictions
D) An imbalanced dataset
Answer: B
Explanation: AUC is the probability that a random positive is ranked above a random negative, and 0.5 means the ranking is no better than chance.
Clustering: Paradigms, K-Means, K-Mode, DBSCAN
85. Which pair correctly matches clustering paradigms with algorithms?
A) Partitional–DBSCAN, Density–K-Means
B) Partitional–K-Means, Hierarchical–Agglomerative, Density–DBSCAN
C) Hierarchical–K-Means, Density–SOM
D) Partitional–EM only
Answer: B
Explanation: K-Means partitions data into flat clusters, agglomerative clustering builds a merge hierarchy (dendrogram), and DBSCAN grows clusters from density-connected regions.
86. K-Means clustering is guaranteed to:
A) Find the globally optimal clustering
B) Converge to a local optimum of the within-cluster sum of squares
C) Produce identical results for any initialization
D) Handle non-convex clusters
Answer: B
Explanation: Each assignment/update step monotonically decreases WCSS, ensuring convergence, but the result depends on initialization and may be only locally optimal (hence K-Means++).
87. K-Mode clustering replaces K-Means’ mean and Euclidean distance with:
A) Median and Manhattan distance
B) Mode and a matching (dissimilarity count) measure, for categorical data
C) Centroid and cosine similarity
D) Mean and Hamming distance
Answer: B
Explanation: Categorical attributes have no meaningful mean, so K-Mode uses the most frequent category (mode) as the cluster representative and counts attribute mismatches as distance.
88. In DBSCAN, a “border point” is one that:
A) Has at least MinPts neighbors within ε
B) Has fewer than MinPts neighbors within ε but lies within ε of a core point
C) Belongs to no cluster
D) Lies exactly on the cluster boundary hyperplane
Answer: B
Explanation: Border points lack the density to be core points themselves but are absorbed into a cluster through their proximity to a core point; points satisfying neither condition are noise.
89. The key advantage of DBSCAN over K-Means is:
A) Faster runtime always
B) It discovers arbitrarily-shaped clusters and labels outliers as noise without pre-specifying cluster count
C) It works only in 2D
D) It guarantees global optimum
Answer: B
Explanation: Density-based growth follows any cluster shape (e.g., crescents), identifies noise explicitly, and infers the number of clusters from data — three things K-Means cannot do.
Self-Organizing Maps (SOM)
90. In a Self-Organizing Map, the “neighborhood function” serves to:
A) Select the winning neuron
B) Update not just the winner but nearby neurons on the grid, preserving topological structure of input space
C) Normalize inputs
D) Prevent overfitting
Answer: B
Explanation: Pulling grid-neighbors of the Best Matching Unit toward the input makes physically close neurons respond to similar inputs, giving SOM its topology-preserving mapping property.
91. In SOM training, learning rate and neighborhood radius are typically:
A) Held constant
B) Gradually decreased over iterations
C) Increased over iterations
D) Randomized each epoch
Answer: B
Explanation: Early large values allow global ordering of the map; later small values fine-tune local weights — annealing both is essential for convergence.
Expectation-Maximization (EM)
92. The Expectation-Maximization algorithm’s E-step for Gaussian mixtures computes:
A) New means and covariances
B) Posterior probabilities (responsibilities) of each component for each data point
C) The gradient of the likelihood
D) The number of clusters
Answer: B
Explanation: The E-step evaluates γ(z) = P(component | point) using current parameters; the M-step then re-estimates parameters weighted by these responsibilities.
93. EM differs from K-Means primarily in that:
A) EM performs hard assignments
B) EM performs soft (probabilistic) assignments and models cluster covariance, with K-Means being a special limiting case
C) EM needs no initialization
D) EM maximizes distance rather than likelihood
Answer: B
Explanation: EM assigns fractional membership via responsibilities and fits full Gaussians; K-Means emerges as the limit of spherical Gaussians with vanishing variance and hard assignment.
94. Each EM iteration is guaranteed to:
A) Increase or maintain the data log-likelihood
B) Decrease the log-likelihood
C) Reach the global maximum
D) Reduce cluster count
Answer: A
Explanation: EM monotonically improves a lower bound on the log-likelihood, ensuring non-decreasing likelihood, though it may converge to a local (not global) maximum.
Principal Component Analysis (PCA)
95. PCA finds directions that:
A) Maximize class separability
B) Maximize variance of projected data, obtained as eigenvectors of the covariance matrix
C) Minimize reconstruction of noise
D) Are randomly oriented but orthogonal
Answer: B
Explanation: The first principal component is the covariance matrix’s top eigenvector; successive orthogonal eigenvectors capture maximal remaining variance (equivalently, minimize reconstruction error).
96. Data must be mean-centered (and often standardized) before PCA because:
A) Eigenvalues become negative otherwise
B) Uncentered data makes the first component point toward the data mean, and unscaled features let high-variance units dominate components
C) PCA fails on positive data
D) Centering removes outliers
Answer: B
Explanation: PCA analyzes the covariance structure around the origin, so centering is mathematically required, and standardization prevents a feature’s measurement unit from dictating the components.
97. The proportion of variance explained by the i-th principal component equals:
A) λᵢ / Σλⱼ (its eigenvalue over the sum of all eigenvalues)
B) 1/λᵢ
C) λᵢ²
D) λᵢ / λ₁
Answer: A
Explanation: Each eigenvalue measures the variance along its eigenvector, so its share of total variance is that eigenvalue divided by the eigenvalue sum — the basis of scree-plot selection.
Kernel PCA
98. Kernel PCA extends standard PCA by:
A) Adding L2 regularization
B) Performing eigendecomposition on the kernel matrix, capturing non-linear structure that linear PCA misses
C) Using more components
D) Whitening the data first
Answer: B
Explanation: Kernel PCA implicitly maps data into a high-dimensional feature space via a kernel and extracts principal components there, so curved manifolds become linearly describable.
99. A known practical difficulty of Kernel PCA versus standard PCA is:
A) It cannot reduce dimensions
B) Exact reconstruction of points back in input space (the pre-image problem) is generally not possible
C) It only works with linear kernels
D) It requires labels
Answer: B
Explanation: Since the feature mapping is implicit and non-invertible, finding the input-space point corresponding to a feature-space projection has no exact solution — the pre-image problem.
t-SNE (t-Distributed Stochastic Neighbor Embedding)
100. t-SNE is primarily designed for:
A) Feature selection for classifiers
B) Low-dimensional visualization that preserves local neighborhood structure
C) Speeding up training
D) Removing multicollinearity
Answer: B
Explanation: t-SNE matches pairwise similarity distributions (Gaussian in high-D, Student-t in low-D) via KL divergence minimization, faithfully preserving local clusters mainly for 2D/3D visualization.
101. t-SNE uses a Student-t distribution (heavy-tailed) in the low-dimensional space to:
A) Speed up convergence
B) Alleviate the crowding problem by letting moderately distant points sit farther apart in the embedding
C) Guarantee convexity
D) Normalize the similarities
Answer: B
Explanation: The t-distribution’s heavy tails allow moderate high-D distances to map to larger low-D distances, preventing all points from crushing together at the embedding’s center.
102. Which statement about interpreting t-SNE plots is CORRECT?
A) Cluster sizes in the plot reflect true cluster variances
B) Distances between well-separated clusters are directly meaningful
C) Neither inter-cluster distances nor cluster sizes are reliably meaningful; only local grouping is
D) The axes correspond to principal components
Answer: C
Explanation: t-SNE adapts its bandwidth per point (perplexity) and optimizes a non-convex local objective, so global geometry — inter-cluster gaps and apparent sizes — is an artifact, not evidence.
Bias–Variance Tradeoff
103. The expected prediction error of a model decomposes into:
A) Bias + Variance
B) Bias² + Variance + Irreducible error
C) Bias × Variance
D) Variance − Bias²
Answer: B
Explanation: The classical decomposition of expected squared error is squared bias (systematic error), variance (sensitivity to training sample), and irreducible noise inherent in the data.
104. As model complexity increases, typically:
A) Bias and variance both increase
B) Bias decreases while variance increases
C) Bias increases while variance decreases
D) Both remain constant
Answer: B
Explanation: Complex models can fit the true function closely (low bias) but change drastically across training samples (high variance) — the tradeoff that optimal complexity balances.
Bagging and Random Forest
105. Bagging reduces which component of error, and why?
A) Bias, by fitting deeper models
B) Variance, by averaging predictions of models trained on bootstrap resamples
C) Irreducible error, by cleaning noise
D) Bias, by reweighting hard examples
Answer: B
Explanation: Averaging approximately independent high-variance estimators shrinks the variance of the ensemble while leaving bias essentially unchanged, which is why bagging suits unstable learners like deep trees.
106. What distinguishes Random Forest from plain bagging of decision trees?
A) It uses boosting internally
B) At each split, it considers only a random subset of features, decorrelating the trees
C) It prunes all trees
D) It trains on the full data without resampling
Answer: B
Explanation: Random feature selection at each split prevents dominant predictors from making all trees similar, and decorrelated trees give a greater variance reduction upon averaging.
107. In Random Forest, the out-of-bag (OOB) error is:
A) Error on a held-out validation file
B) An internal generalization estimate computed from predictions of trees that did not see each sample in their bootstrap
C) Training error
D) Error on the hardest 10% of samples
Answer: B
Explanation: Each bootstrap sample omits ~36.8% of data (since (1−1/n)ⁿ → e⁻¹), and evaluating each point only with trees that excluded it gives a nearly unbiased test-error estimate without a validation set.
AdaBoost
108. AdaBoost adapts across iterations by:
A) Removing easy examples from data
B) Increasing weights of misclassified samples so subsequent weak learners focus on them
C) Randomly reweighting all samples
D) Growing deeper trees each round
Answer: B
Explanation: After each round, AdaBoost multiplies misclassified samples’ weights upward (and normalizes), forcing the next weak learner to concentrate on previously hard cases.
109. In AdaBoost, a weak learner’s contribution weight α = ½ln((1−ε)/ε) implies:
A) All learners contribute equally
B) Learners with error near 0 get large positive weight, error 0.5 gets zero weight, and error above 0.5 gets negative weight
C) Higher-error learners dominate
D) α is always 1
Answer: B
Explanation: The log-odds formula rewards accuracy, nullifies coin-flip learners (ε=0.5 → α=0), and effectively inverts worse-than-random learners via negative weight.
110. In AdaBoost, if a weak learner achieves weighted error ε = 0.25, its α (using natural log) is approximately:
A) 0.55
B) 1.10
C) 0.25
D) 0.75
Answer: A
Explanation: α = ½ln(0.75/0.25) = ½ln(3) ≈ ½(1.0986) ≈ 0.549.
111. Boosting primarily reduces which error component (in contrast to bagging)?
A) Variance only
B) Bias, by sequentially fitting learners to the residual mistakes of the ensemble
C) Irreducible error
D) Neither
Answer: B
Explanation: Boosting builds an additive model where each stage corrects its predecessors’ systematic errors, driving bias down (though it can also affect variance and may overfit noisy data).
XGBoost and Shrinkage
112. XGBoost differs from classical gradient boosting notably by:
A) Using bootstrap sampling only
B) Adding explicit regularization terms on tree complexity and using second-order (Hessian) gradient information in its objective
C) Training trees in parallel independently like a forest
D) Requiring no learning rate
Answer: B
Explanation: XGBoost’s objective includes penalties on leaf count and leaf weights (γ, λ) and expands the loss to second order, yielding regularized, principled split decisions plus engineering optimizations.
113. The “shrinkage” (learning rate η) in boosting:
A) Scales each tree’s contribution, requiring more trees but improving generalization when small
B) Shrinks the dataset each round
C) Prunes leaves after training
D) Has no effect on overfitting
Answer: A
Explanation: Multiplying each stage’s output by small η makes the ensemble take conservative steps toward the target, a regularization effect that typically improves test performance at the cost of more iterations.
Class Imbalance and SMOTE
114. Why does class imbalance harm standard classifier training?
A) Loss functions dominated by the majority class produce models biased toward predicting it, starving the minority class of decision influence
B) Gradient descent diverges
C) Imbalanced data cannot be shuffled
D) Cross-validation becomes invalid
Answer: A
Explanation: When 99% of loss terms come from one class, minimizing average loss favors majority-class predictions, so the minority class — usually the class of interest — is systematically under-predicted.
115. SMOTE generates synthetic minority samples by:
A) Duplicating minority points exactly
B) Interpolating between a minority point and one of its randomly chosen minority-class K nearest neighbors
C) Adding Gaussian noise to majority samples
D) Deleting majority samples
Answer: B
Explanation: SMOTE creates new points along the line segment x_new = x + rand(0,1)×(x_neighbor − x), which expands the minority region rather than merely replicating points as random oversampling does.
116. A critical procedural rule when using SMOTE with cross-validation is:
A) Apply SMOTE before splitting the data
B) Apply SMOTE only within each training fold, never to validation/test data, to avoid synthetic-sample leakage and inflated scores
C) Apply SMOTE to the test set for fairness
D) Use SMOTE only with linear models
Answer: B
Explanation: Oversampling before splitting lets synthetic points derived from validation-fold originals leak into training, producing over-optimistic performance estimates; the test distribution must remain untouched.
117. A known weakness of SMOTE is:
A) It cannot generate more than 100 samples
B) Blind interpolation near class boundaries or noisy points can create ambiguous samples inside the majority region, worsening overlap
C) It only works on images
D) It removes genuine minority samples
Answer: B
Explanation: SMOTE ignores the majority class’s location, so interpolating from borderline/noisy minority points can plant synthetic samples in majority territory — motivating variants like Borderline-SMOTE.
One-Class SVM
118. One-Class SVM is appropriate when:
A) Both classes are equally represented
B) Training data contains (essentially) only normal-class examples and the task is to detect deviations — novelty/anomaly detection
C) There are more than two classes
D) Labels are perfectly balanced
Answer: B
Explanation: One-Class SVM learns a boundary enclosing the normal data’s support region and flags points falling outside it, requiring no anomalous examples during training.
119. In One-Class SVM, the parameter ν (nu) controls:
A) Kernel width
B) An upper bound on the fraction of training points treated as outliers and a lower bound on the fraction of support vectors
C) The number of classes
D) Learning rate decay
Answer: B
Explanation: ν ∈ (0,1] simultaneously bounds outlier fraction from above and support-vector fraction from below, directly setting how “tight” the learned normal region is.
Hyperparameter Tuning
120. Compared to grid search, random search for hyperparameter tuning is often more efficient because:
A) It always finds the global optimum
B) When only a few hyperparameters truly matter, random sampling explores more distinct values of each important parameter within the same budget
C) It requires no search space definition
D) It evaluates fewer models for the same coverage of every dimension
Answer: B
Explanation: Grid search wastes trials repeating identical values of important parameters across grid lines, while random search gives every trial a fresh value of each parameter (Bergstra & Bengio, 2012).
Reinforcement Learning
121. The defining feature that separates reinforcement learning from supervised learning is:
A) RL uses neural networks
B) The agent learns from evaluative reward signals through trial-and-error interaction rather than from labeled correct answers
C) RL requires less data
D) RL has no training phase
Answer: B
Explanation: In RL no oracle provides the correct action; the agent only receives a scalar reward indicating how good its chosen action was, and must discover good behavior through exploration.
122. In the RL framework, a “policy” π is:
A) The reward function
B) A mapping from states to actions (or action probabilities) that defines the agent’s behavior
C) The environment’s transition rule
D) The list of visited states
Answer: B
Explanation: The policy π(a|s) is precisely what the agent is trying to learn — a rule specifying which action to take (or with what probability) in each state.
123. The Markov property in an MDP states that:
A) Rewards are always positive
B) The next state and reward depend only on the current state and action, not on the full history
C) All states are equally likely
D) The environment is deterministic
Answer: B
Explanation: Formally P(s′,r | s,a, history) = P(s′,r | s,a); the current state is a sufficient statistic of the past, which is what makes Bellman recursions valid.
124. An MDP is formally defined by the tuple:
A) (S, A, P, R, γ) — states, actions, transition probabilities, reward function, discount factor
B) (S, A) only
C) (P, R) only
D) (S, A, Q)
Answer: A
Explanation: These five components fully specify the sequential decision problem: what situations exist, what can be done, how the world moves, what is rewarded, and how future rewards are weighted.
125. The discount factor γ ∈ [0,1) serves two purposes:
A) Speeding computation and reducing memory
B) Keeping infinite-horizon return sums finite and expressing preference for immediate over delayed rewards
C) Normalizing rewards and preventing negative values
D) Encouraging exploration and penalizing large actions
Answer: B
Explanation: Geometric discounting bounds Σγᵗrₜ for bounded rewards, and γ<1 makes a reward received sooner worth more than the same reward later.
126. With γ = 0.9, a reward of 10 received 3 steps in the future contributes how much to the current return?
A) 10
B) 7.29
C) 9.0
D) 2.7
Answer: B
Explanation: Contribution = γ³ × 10 = 0.9³ × 10 = 0.729 × 10 = 7.29.
127. The state-value function Vπ(s) represents:
A) The immediate reward at s
B) The expected cumulative discounted return starting from s and following policy π thereafter
C) The best action at s
D) The probability of reaching s
Answer: B
Explanation: Vπ(s) = Eπ[Σγᵗrₜ | s₀=s], measuring how good it is to be in state s under the given behavior policy.
128. The difference between V(s) and Q(s,a) is:
A) None; they are identical
B) Q additionally commits to a specific first action a before following the policy, so Vπ(s) = Σₐ π(a|s)Qπ(s,a)
C) V is for deterministic environments only
D) Q ignores future rewards
Answer: B
Explanation: Q(s,a) evaluates “take action a now, then follow π,” which is exactly why Q-functions enable action selection without a model: argmax over a needs no transition probabilities.
129. The Bellman expectation equation for Vπ expresses:
A) V as an average of all rewards
B) Vπ(s) as immediate expected reward plus discounted expected value of the successor state under π — a recursive self-consistency condition
C) V as the maximum over actions
D) V as independent of π
Answer: B
Explanation: Vπ(s) = Σₐ π(a|s) Σₛ′ P(s′|s,a)[R + γVπ(s′)]; value today equals expected reward now plus discounted value tomorrow.
130. The Bellman optimality equation differs from the expectation equation by:
A) Removing the discount factor
B) Replacing the policy-weighted average over actions with a max over actions
C) Adding a learning rate
D) Using rewards only
Answer: B
Explanation: V*(s) = maxₐ Σₛ′ P(s′|s,a)[R + γV*(s′)]; the max operator makes the equation non-linear and encodes acting optimally rather than following a fixed π.
131. The exploration–exploitation dilemma refers to the tension between:
A) Speed and memory
B) Trying new actions to discover potentially better rewards versus choosing the currently best-known action to maximize immediate return
C) Training and testing
D) Model-based and model-free methods
Answer: B
Explanation: Pure exploitation can lock the agent into suboptimal behavior discovered early, while pure exploration wastes reward — every RL algorithm needs a mechanism balancing the two.
132. In an ε-greedy policy with ε = 0.1 and 4 actions, the probability of selecting the greedy action is:
A) 0.90
B) 0.925
C) 0.10
D) 0.25
Answer: B
Explanation: The greedy action is chosen with probability (1−ε) plus its share of random selection: 0.9 + 0.1/4 = 0.925.
133. A common ε schedule in practice is to:
A) Keep ε = 1 throughout
B) Start with high ε (heavy exploration) and decay it over time toward a small value as knowledge accumulates
C) Start at 0 and increase
D) Alternate between 0 and 1 each step
Answer: B
Explanation: Early on, estimates are unreliable so exploration is valuable; as Q-estimates converge, exploiting them more (small ε) maximizes return — hence decaying schedules.
134. Q-learning is called an “off-policy” method because:
A) It requires no policy
B) It learns the optimal Q-function using the max over next actions in its update, regardless of the (e.g., ε-greedy) behavior policy actually generating the data
C) It works offline only
D) It never explores
Answer: B
Explanation: The update target r + γ maxₐ′ Q(s′,a′) evaluates the greedy policy while the agent may behave differently, decoupling learned policy from behavior policy.
135. The Q-learning update rule is:
A) Q(s,a) ← r
B) Q(s,a) ← Q(s,a) + α[r + γ maxₐ′ Q(s′,a′) − Q(s,a)]
C) Q(s,a) ← max Q(s′,a′)
D) Q(s,a) ← Q(s,a) − αr
Answer: B
Explanation: The bracketed term is the temporal-difference error — the gap between the bootstrapped target and the current estimate — and α controls how far the estimate moves toward it.
136. In the Q-learning update, the term [r + γ max Q(s′,a′) − Q(s,a)] is called:
A) The advantage
B) The temporal-difference (TD) error
C) The Bellman residual reward
D) The eligibility trace
Answer: B
Explanation: It measures the discrepancy between predicted value and the one-step lookahead target; zero TD error everywhere means the Bellman optimality equation is satisfied.
137. Tabular Q-learning converges to Q* under which key conditions?
A) Deterministic environment only
B) Every state-action pair is visited infinitely often and the learning rate satisfies the stochastic approximation conditions (Σα = ∞, Σα² < ∞)
C) γ = 1 exactly
D) The policy is always greedy
Answer: B
Explanation: Convergence proofs (Watkins & Dayan, 1992) require persistent exploration of all (s,a) pairs and appropriately decaying step sizes; failing either breaks the guarantee.
138. Given Q(s,a)=5, observed r=2, γ=0.9, maxₐ′Q(s′,a′)=10, α=0.5, the updated Q(s,a) is:
A) 8.0
B) 5.5
C) 11.0
D) 6.5
Answer: A
Explanation: Target = 2 + 0.9×10 = 11; TD error = 11 − 5 = 6; new Q = 5 + 0.5×6 = 8.0.
139. SARSA differs from Q-learning in that SARSA:
A) Uses no learning rate
B) Is on-policy — its target uses the action a′ actually selected by the current (e.g., ε-greedy) policy instead of the max
C) Ignores the reward
D) Cannot converge
Answer: B
Explanation: SARSA’s target r + γQ(s′,a′) evaluates the behavior policy itself (including its exploration), which is why SARSA learns “safer” paths near hazards (classic cliff-walking example) while Q-learning learns the optimal-but-risky path.
140. Model-free methods like Q-learning are so called because they:
A) Use no function approximation
B) Learn value functions directly from experienced transitions without learning or using the environment’s transition probabilities P(s′|s,a)
C) Have no parameters
D) Skip the reward signal
Answer: B
Explanation: The agent never estimates the dynamics model; sampled transitions (s,a,r,s′) serve as stochastic samples of the Bellman backup, in contrast to model-based planning like value iteration on known P.