Classifier performance if data are deterministic

Question

so let us imagine one has a classification problem at hand, say objects with $n$ numeric features, to be classified as belonging to two classes ${0,1}$. Data could look like, for $n=3$

x_1 x_2 x_3 class
1.1 2.0 3.2 0
1.2 2.1 0.7 1
4.0 2.1 3.2 0

where the $x_i$ stand for numerical values for a given property.

This dataset could be already fed to any classifier, let us say a Random Forest one.

Now, let us imagine a human expert in this domain states that the classification problem is actually trivial. In fact there exist a scalar function, say $\phi(x_1,x_2, x_3)$ such that when

\begin{cases} \phi(x_1,x_2, x_3) < 3,\,\, \mbox{ instance belongs to class} \, 0\\ \phi(x_1,x_2, x_3) \geq 3,\,\, \mbox{ instance belongs to class} \, 1 \end{cases}

A person explicitly knowing the function $\phi$ would achieve perfect accuracy.

The question then is, are there any formal results clarifying (e.g.bounding) the accuracy achievable under conditions on the function $\phi$ (linearity, smoothness, etc.)?

For example, if $\Phi$ is linear, is there any result stating a classifier can achieve perfect accuracy as the number of datapoints goes to $\infty$? And what could be said if $\phi$ is nonlinear?

I am not an expert in this field at all as it can be easily grasped. I am looking for pointers on relevant literature.

Another point of view on my question is, if the underlying data are somehow deterministic, is it worth at all spending time in trying to make sense of the classification problem using human expertise, or is it guaranteed that under some condition a classifier will be anyhow be able to come up with a "good" answer?

EDIT Yet another more practical point, clarifying the real life problem I am trying to understand. Often one reads about the importance of data engineering, specifically coming up with additional, engineered features using human expertise. But what is the usefulness of this, or the necessity for that matters? Can there be that a classifier performs badly on the original dataset, and then somebody defined a "clever" new feature, function of other original feature values, and the performance grows significantly? At the end of the day, new engineered features do not contain original, new information. then one could say, there is no need to waste time in looking for engineered features, just let the classifier go on the original dataset.

The Data-processing inequality springs to mind, but then, can it be that the information present in the original dataset can be extracted only if feature engineering is performed? If that were the case, what is known about this interesting phenomenon?

Answer 1

This is an important question that goes back to the fundamentals of machine learning theory.

The primary objective of using machine learning to solve a problem is as the following:

• For a given set of data with inputs(features) and targets(classes), there exists some linear or non-linear relationship that maps the inputs to the target.
• Having known the physics behind the problem setting, the human expert does know there exists a function that maps the inputs to the target. The highlight here is that the function is actually unknown mathematically. The objective of ML is to discover/learn that mapping using data as examples.

Therefore if we have a problem where the data shows some relation between the features and targets, but is functionally not known, then it is a good setting to use ML to solve the problem. Having stated this, if one knows the exact function (similar to the one in the question) that explains the relationship then ML is not at all required. One can use the mathematical function itself to solve the problem if it's already known and does not need to go the expensive route of ML. Expensive because gathering (good) data, labeling them, and training take effort.

Regarding the second part of your question, the accuracy of a classifier mainly depends on the quality of your data points and not the quantity. So having a very large number of data points that are not at all good representatives of the problem will not help the classifier model achieve better accuracy whether the function is linear or nonlinear. The data points and features should be the best representative of the classes that you want to train for. For example, if you were building a model to classify rhinos and elephants, you want features of their heads rather than their legs - because their legs may look similar but the head does make a huge difference. Not the best example but, I think you may get the point. So in short the goodness of your data mostly determines the accuracy of the model more than the model itself.

There are plenty of sources on the quality of data for training. For good references, you may want to read the initial chapters of "Pattern Classification" by Richard Duda which covers in good detail the main two parts of your question.