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?


1 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.

  • $\begingroup$ thanks for your answer, it makes full sense of course. Wrt part 1, of course the function is not known a priori, we only know it exists. Please if you may, consider the edit to my original post, trying to explain what my point really is, which I might have expressed quite too abstractly, if not badly! $\endgroup$
    – Smerdjakov
    Commented Oct 9, 2022 at 15:20
  • 1
    $\begingroup$ Regarding engineered features vs. raw features, Given other real-world constraints it's possible that a given model cannot learn the requried features in the space provided. If $\phi$ is a giant neural net with infinite layers and infinite examples then sure, it should be possible for the modle to learn what you want. But a linear model with some clever features might be needed to keep runtime down to some given real-time constraint, or a clever compression scheme could be used for memory and space purposes. $\endgroup$
    – juicedatom
    Commented Oct 11, 2022 at 4:58
  • 2
    $\begingroup$ Even large neural nets sometimes use larger hand-engineered features. For example look at point pillars, a seminal work in lidar object detection. It has a large set of hand-engineered features that improve mAP even though all the raw lidar points are provided. $\endgroup$
    – juicedatom
    Commented Oct 11, 2022 at 5:00
  • $\begingroup$ @juicedatom thanks those references are very interesting, I would accept it as an answer $\endgroup$
    – Smerdjakov
    Commented Oct 11, 2022 at 21:07
  • $\begingroup$ @juicedatom, your statement about $\phi$ being a giant model with infinite layers, that should be able to learn, is this anything that has been formally proven? Or is it more intuition-based? Thanks a lot $\endgroup$
    – Smerdjakov
    Commented Oct 11, 2022 at 21:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .