Generalizing Boundary Points

Tapio Elomaa, University of Helsinki; Juho Rousu, VTT Biotechnology

The complexity of numerical domain partitioning depends on the number of potential cut points. For a large family of attribute evaluation functions only boundary points need to be considered as candidates. We prove that an even more general property holds for many commonly-used functions. They do not obtain their optimal value within a segment of examples in which the relative class frequency distribution of examples is static. The borders of such segments are a subset of boundary points. Thus, even less cut points need to be examined for these functions. The results shed a new light on the splitting properties of common attribute evaluation functions and they have practical value as well. The functions that are examined also include non-convex ones. Hence, the property introduced is not just another consequence of the convexity of a function.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.