Which of the following models can NOT achieve training error of zero on any linearly separable dataset? (you can choose more than one option)多项选择题
A
a. Decision tree
B
b. Hard-margin SVM
C
c. 15-NN
D
d. Perceptron

Question

Which of the following models can NOT achieve training error of zero on any linearly separable dataset? (you can choose more than one option)

BlackTom AI · Accepted Answer

The question asks which models cannot achieve training error of zero on any linearly separable dataset, with the option to select more than one.
Option a: Decision tree. In principle, a decision tree can fit the training data exactly if allowed to grow without constraints (deep trees, no pruning), effectively yielding zero training error even on linearly separable data. The claim that it cannot achieve zero is incorrect because overfitting a sufficiently deep tree can perfectly classify the training samples.
Option b: Hard-margin SVM. On linearly separable data, a hard-margin SVM finds a separating hyperplane with maximum margin and no training errors, so zero training error is achievable. This option is incorrect as a statement of impossibility.
Option c: 15-NN. k-Nearest Neighbors with k = 15 does not guarantee zero training error. Even when the data are linearly separable, the local 15-neighbor vote for some training points could be mislabeled if the neighborhood contains enough points of the opposite class, especially near the boundary or in regions where class neighborhoods are mixed. Therefore, there exist linearly separable datasets for which 15-NN cannot classify every training point correctly, so zero training error is not guaranteed. This option is correct as a cannot-achieve scenario.
Option d: Perceptron. The perceptron learning algorithm converges to a solution with zero training error provided the data are linearly separable and there exists a weight vector that correctly separates the classes. Thus, zero training error is achievable here, making this option incorrect as a cannot-achieve claim.
In summary, the only model that cannot guaranteedly achieve zero training error on any linearly separable dataset is the 15-NN option, while the decision tree, hard-margin SVM, and perceptron can, under the right conditions or settings, attain zero training error. 
Note: Different explanations emphasize distinct aspects—global capacity (trees), optimization guarantees under separability (SVM, perceptron), and local neighborhood behavior (k-NN)—to highlight why each option does or does not meet the criterion.

Which of the following models can NOT achieve training error of zero on any linearly separable dataset? (you can choose more than one option)多项选择题

类似问题

Given are the following 2-dimensional examples from two classes - class1 and class2: class1: p1 = [1 2], p2 = [2 1] class2: p3 = [-2 1], p4 = [-2 -1] Can a perceptron learn to distinguish between them?