Learning Weakly Convex Sets in Metric Spaces
  We introduce the notion of weak convexity in metric spaces, a generalization
of ordinary convexity commonly used in machine learning. It is shown that
weakly convex sets can be characterized by a closure operator and have a unique
decomposition into a set of pairwise disjoint connected blocks. We give two
generic efficient algorithms, an extensional and an intensional one for
learning weakly convex concepts and study their formal properties. Our
experimental results concerning vertex classification clearly demonstrate the
excellent predictive performance of the extensional algorithm. Two non-trivial
applications of the intensional algorithm to polynomial PAC-learnability are
presented. The first one deals with learning $k$-convex Boolean functions,
which are already known to be efficiently PAC-learnable. It is shown how to
derive this positive result in a fairly easy way by the generic intensional
algorithm. The second one is concerned with the Euclidean space equipped with
the Manhattan distance. For this metric space, weakly convex sets are a union
of pairwise disjoint axis-aligned hyperrectangles. We show that a weakly convex
set that is consistent with a set of examples and contains a minimum number of
hyperrectangles can be found in polynomial time. In contrast, this problem is
known to be NP-complete if the hyperrectangles may be overlapping.
