Formal conditions on mappings that can NOT be learned from data

Question

I am new to machine learning and would appreciate some help on the following question. I have observed the literature is focused on algorithms, how one learning does better compared to others for a given data set and remarkable progress have been made on that front. However, I have not been able to find references that discuss the underlying structure of the data space as related to limits of what "can" and "can NOT" be learned from a specific data set/type.

My specific question is as follows: are there formal conditions on a mapping (will settle for examples) f:X→Y , with y∈Y⊂Rn and x∈X⊂Rm, to indicate that f can NOT be "learned" from a finite set of training data : X^={x1,x2,...,xT}⊂X and Y^={y1,y2,...,yT}⊂Y, regardless of the size, T, or choice of the training data?

Answer 1

You can apply statistical techniques that check if there is a functional (possibly non-linear) dependence between $x$ and $y$ variables.

These techniques include (apart from the simplest Pearson and Spearman correlation coefficients)

1. The maximal information coefficient (link) originally defined by Wassily Hoeffding in 1948 (link). See also here and here.

2. Alternating Conditional Expectations by Breiman and Friedman (1985 link, Fortran, R).

3. Distance correlation by Gábor J. Székely (2005, link, R).

4. Probably many other techniques as none of them is perfect.

There may be a situation when $y$ is totally uncorrelated with each $x_i$ individually but has functional dependence on subsets $x_{i_1},..., x_{i_k}$. Example: XOR problem (link).

Answer 2

According to the universal approximation theorems mappings that satisfy these criteria are, in principle, learnable.

One should note that these theorems are not constructive, thus provide no algorithm for constructing the model or verifying the conditions. They only state that if the conditions hold, a task is theoretically learnable by some (ANN) architecture.

Linear mappings are also constructively and demonstrably learnable by linear models.

Furthermore, Probably Approximately Correct (PAC) learning theory and VC theory specify conditions under which data can lead to selecting (learning) some function $h^*$ in a set $H$ of possible functions (hypotheses), which most probably fit the data. These approaches attempt to characterize learnability in both statistical and computational terms.

Now, whether a certain task is about a mapping that satisfies these criteria, or is outside the scope of these theoretical results, does not necessarily imply that it is unlearnable, although theoretically it is an open question (eg universal inductive inference theory is uncomputable).

Assuming that a (ML) model for a certain mapping provides a shorter algorithmic description of that mapping than the explicit mapping itself (eg as sequence of input/output pairs), then one way to formalize unlearnability would be to claim that there can be no shorter algorithmic description of the mapping except the possibly infinite explicit mapping itself. In other words, if the mapping is algorithmically random then it is unlearnable. In this respect one can employ concepts, for example, such as Kolmogorov complexity and algorithmic randomness (see, for example, On the impossibility of discovering a formula for primes using AI). There is a (approximate) relation between algorithmic randomness and statistical randomness, as there is a (approximate) relation between algorithmic information and statistical information (eg for large enough sequences). This means that statistical notions of randomness can be used as criteria for (un)learnability similarly to algorithmic randomness criteria.

Still another way to approach unlearnability is as inefficiency in computational complexity terms when any algorithm to learn/approximate a mapping is provably or likely to be superpolynomial/exponential. In this sense a mapping is unlearnable if it is inefficient. As such, the randomness leading to unlearnability is not the algorithmic/statistical randomness, as above, but rather the cryptographic pseudorandomness of pseudorandom generators and one-way functions.

---

The above analysis is related to the No Free Lunch Theorems (NFL) for optimization and machine learning, in the sense that when a mapping is so random (in some sense of randomness as mentioned above), then this means that there is no structure that can be used and/or learned, thus no algorithm performs any better, on average, than random guessing (NFL theorem). Thus, effectively, the mapping is as unlearnable as it can be since it exhibits the minimum structure possible, and is thus maximally random.