Given an approach to a machine learning problem, how do we know it’s correct? In what sense does it need to be correct? A theoretician’s answer: It needs to be PAC correct, i.e. “probably approximately” correct.
Machine learning starts with data and ends with the machine having formed a concept of the data or, more informally speaking, having understood the data, so that the machine can make decisions based on that concept. Generally speaking, it would be too much to ask, to require that a machine learner must never be wrong about such a decision. If the concept is approximately correct, so that, say, 80% of all decisions are right, that’s good enough. Also, it would be too much to ask, to require that a machine learner must be able to form a concept of the data that is approximately correct, regardless of the data. So, if the machine learner is probably correct, in the sense that on, say, 80% of all inputs of data, it will form a concept that’s approximately correct, then that’s good enough.
In this video lecture, I describe the theoretical framing of machine learning problems in general, as well as the theoretical underpinnings of formally rigorous correctness claims pertaining to any kind of a machine learning solution, following from these basic ideas.
>> read more