Homework disclaimer. We were given 10k rows of sample training data.
The task is to train some well-known classifiers (as listed below), test their performance and estimate the expected misclassification error using Hoeffding inequality for possible new cases. The aim is to achieve the best classification quality (understood as the lowest expected generalization error). This should be achieved by testing classifiers using the sample split and selecting the proper test sample size. When solving a task, do not use crossvalidation. It is not necessary to optimize the values of classifiers parameters while solving the task.
I fail to understand what is being asked here.
How can selecting the proper test sample size do any good with regard to achieving the best classification quality (understood as the lowest expected generalization error)?
To my understanding, the more data I use as training data the better classifier I am going to obtain - so if I am to, as the assignment asks, try to obtain the best classifier through manipulating the test sample size, the solution is as easy as it is absurd: use all data as training data and no data as testing data. But the tradeoff is that the more data I use as testing data, the better I can estimate the quality of the classifier (the smaller confidence interval I am going to obtain). So if I maximize the classifier's quality in the way described above I won't be able to estimate it!
Now the task mentions the Hoeffding's inequality. But Hoeffding's inequality can tell me how big of a test sample size I have to have to obtain a given confidence interval for a given estimated quality. But I still can't see how to use it: the task doesn't put a constraint like "you must be able to claim with at least 80% confidence that the actual accuracy of your classifier differs no more than 5 percent points from your estimated accuracy". If such a constraint was present then the task would make more sense to me.
Also, the tasks asks me to report the method I used to estimate the minimum generalization error.
Finally, just in case this is relevant: The three simple classifiers I have to use are: Naive Bayes, kNN and decision tree.
What am I failing to understand here?