Logic of Machine Learning
This work addresses a core philosophical and theoretical problem in machine learning, offering a novel logical framework that unifies diverse learners and extends to data analysis beyond traditional ML, though it is incremental in building on existing concepts.
The paper tackles the foundational question of why and how prediction from finite samples is possible, proposing that learning involves minimizing violations of predictability beliefs, formalized as incongruity in a modal logic framework, and demonstrates that many standard learners implicitly minimize their own version of incongruity.
The main question is: why and how can we ever predict based on a finite sample? The question is not answered by statistical learning theory. Here, I suggest that prediction requires belief in "predictability" of the underlying dependence, and learning involves search for a hypothesis where these beliefs are violated the least given the observations. The measure of these violations ("errors") for given data, hypothesis and particular type of predictability beliefs is formalized as concept of incongruity in modal Logic of Observations and Hypotheses (LOH). I show on examples of many popular textbook learners (from hierarchical clustering to k-NN and SVM) that each of them minimizes its own version of incongruity. In addition, the concept of incongruity is shown to be flexible enough for formalization of some important data analysis problems, not considered as part of ML.