# Trouble understanding the nature of the learning problem

Coming from mathy background I feel it is very important to formalize a task well in order to solve it well. However, I currently feel unconfortable with my understanding of the essence of the supervised learning problem.

The primary goal of supervised learning is prediction. One has labelled data $$(x_1,y_1), ..., (x_m,y_m)$$ and one attempts to infer a pattern (a function) $$f: \mathcal{X} \to \mathcal{Y}$$ that generalizes well.

From what I gather, you can either assume there is a functional relation $$y=f(x)$$ and that the $$x$$ values are generated from a probabilistic source $$\mathcal{D}$$ over $$\mathcal{X}$$, or you can assume data is generated from a source over $$\mathcal{X}\times\mathcal{Y}$$ and that there is no functional relation between $$\mathcal{Y}$$ and $$\mathcal{X}$$ (but there is correlation, otherwise learning wouldn't be feasible).

Lets see some examples.

1. Computer Vision. Consider problems like handwritten digit recognition. To be specific, consider the MNIST task of recognizing 0-9 digits from 28x28 gray scale images. The domain here is clearly contained in $$[0,255]^{28\times 28}$$. Moreover, one can imagine there is a distribution $$\mathcal{D}$$ on this high-dimensional space that captures the fact we are only interested in images representing digits ($$\mathcal{D}$$ assigns very low probabilities to images that don't look like digits)

In this setting, it looks like there exists a function $$f: \mathcal{I} \to \{0,1,...,9\}$$, where $$\mathcal{I}$$ is the set of images that represent a digit, that capture the concept we are trying to learn. The task is then to find a complex-enough (but not too complex, otherwise learning guarantees become loose) hypothesis class $$\mathcal{H}$$ where we can perform empirical risk minimization over to find a good estimate $$h$$ for $$f$$.

1. Price prediction. Consider any problem where you have some features (like info about a house or other object with value) and you want to precify the object. The input space is something like $$\mathbb{R}^N$$, and $$\mathcal{Y} \subset \mathbb{R}$$.

This problem looks degenerate. You can fit a model to some available data, but I can't imagine there is a functional relation or even a general pattern between $$\mathcal{X}$$ and $$\mathcal{Y}$$. For me any function that interpolates the data well is a valid "price model".

1. There are many more possible applications for machine learning.

Having said that, is there a "right" framework for supervised learning (say deterministic or stochastic?), or it fundamentally depends on the problem you are dealing with? I've seen some places where people focus on the function estimation problem, see for instance this comment from Learning Theory: an Approximation Theory Viewpoint:

Broadly speaking, the goal of (mainstream) learning theory is to approximate a function (or some function features) from data samples, perhaps perturbed by noise. To attain this goal, learning theory draws on a variety of diverse subjects. It relies on statistics whose purpose is precisely to infer information from random samples. It also relies on approximation theory, since our estimate of the function must belong to a prespecified class, and therefore the ability of this class to approximate the function accurately is of the essence

Are such approaches inevitably restricted to some supervised learning tasks or (at least in classification problems) can we always strive for estimating the bayes classifier?

I imagine there is confusion in my words above, and so I would warmly receive extended comments and answers.

• Thinking as there being a conditional or feature-parameterized distribution of the outcome variable from which observations are drawn is a good place to start. The beginning of seeing this framework starts with seeing a classical linear model as an expected value plus an error term. Then, generalized linear models just model conditional distributions without necessarily having an error term. From GLMs, the jump to general conditional distributions was straightforward for me (in the sense that it just took a few years of postgraduate study to really sink in).
– Dave
Jun 7, 2023 at 18:52

There are many ways to classify machine learning models, but the distinction you are making is not the best one. First of all, we almost never assume that the relationship can be described as a deterministic function. The relationship is often thought as $$y = f(x)+\varepsilon$$, where $$\varepsilon$$ is a random noise. Moreover, correlation measures the linear relationship between variables, a linear function. All the relationships are considered stochastic. In the real world even if you measured a deterministic function, there would be measurement errors and other sources of noise that would make the data non-deterministic.