The Delaunay Triangulation Learner

We propose a new base learner, called the Delaunay triangulation learner (DTL), which can significantly improve the performance over the standard tree-based ensem-ble methods, under high-dimensional and highly interactive settings. The innovation of the DTL arises from discrete differential geometry, in which Delaunay triangulation is applied as a surface reconstruction algorithm that can accurately describe the prop- erties of a surface using a linear interpolation function. Compared with other triangle meshes, a Delaunay triangle mesh is considered as a near-optimal way to construct a linear interpolation function to approximate the target function with minimal er-ror. Thus, we construct the DTL by applying Delaunay triangulation on the training dataset and fit the model with a linear interpolation function. Furthermore, we pro-pose two appropriate regularization functions to penalize the roughness of the DTL and improve its predictability on the testing dataset. In ensemble learning applica- tions, we propose the bagging DTL and random crystal, where the DTLs are assigned to the subspaces of the feature space, and the feature interactions are captured by Delaunay triangle meshes. Compared with the tree-based approaches, the DTL shows substantial performance enhancement, especially when feature interactions are deeply covered by some weak partial dependencies.