Learning by Smoothing: A Morphological Approach

Abstract

We establish PAC-learnabilities for algorithms that are based on the Smoothing Principle which says that a point in R m belongs to the hypothesis set only if that point is in a sufficiently small neighborhood of a known positively labelled example point. Incorporating techniques from Mathematical Morphology and PAC-Learnability Theory, we formally model smoothing as set-dilation operation and rigorously demonstrate that the corresponding Smoothing Algorithms have many virtues. In particular, we show that the concept class consisting of all bounded and finite surface area subsets of R m is Valiantsense learnable if we allow for some plausible restrictions on the behaviors of the concepts and the underlying probability distributions. A formal analysis of the Smoothing Algorithm reveals their robustness with respect to the choice of smoothing element, their ties to the Nearest Neighbor Rule, and their potential for implementation in cellular automata as growing neural nets.