is learning feasible

18 Dec, 2025

Recap

You can perform ML without a pattern as well
Say we can pin down a mathematical function for a task - then ML is not the recommended technique, but it will still work.
But we cannot perform ML without data - ML is learning from data
Even though the target function is unknown, it is known on the data that will be used for training - in case of supervised learning, you have the targets explicitly mentioned.
The perceptron learning algorithm works with linearly separable data, and hence for such data classification is guaranteed.

#Outline (answering - can we say something about data outside the sample that we have?)

1. Probability to the rescue

Consider a bin with red or green marbles.
P(picking a red marble) = meu
P(picking a green marble) = 1-meu
The value of meu is unknown to us
We pick N marbles independently (N=data points)
The fraction of red marbles from a sample of the bin = neu
Does neu say anything about meu?
No, because sample can be mostly green while bin is mostly red.
But YES - because if the sample is big enough, the sample frequency (neu) is likely to resemble population (meu)
possible vs probable
From a probabilistic point of view, meu (out-sample) says something about neu (in-sample)
Hoeffding's inequality meu = neu (PAC statement) probably approximately correct
Tradeoff
Meu (out-sample a.k.a bin) affects neu (in-sample) and not the other way around, but since the form of the probability is symmetric - hence, instead of saying meu tends to be closely related to neu (which is the accurate logical statement), we say neu tends to be close to meu.
Collapsing between our hypothesis and the target function - each ball in the bin (red or green)
h(x) = f(x) [green - hypothesis matched with target function]
h(x) != f(x) [green - hypothesis did not match with target function]
P (probability) not going to restrict the prob distributions over x
We don't even need to know what P is - the