Kernel regression is an essential and ubiquitous tool for non-parametric data analysis, particularly popular among time series and spatial data. However, the central operation which is performed many times, evaluating a kernel on the data set, takes linear time. This is impractical for modern large data sets. In this paper we describe coresets for kernel regression: compressed data sets which can be used as proxy for the original data and have provably bounded worst case error. The size of the coresets are independent of the raw number of data points, rather they only depend on the error guarantee, and in some cases the size of domain and amount of smoothing. We evaluate our methods on very large time series and spatial data, and demonstrate that they incur negligible error, can be constructed extremely efficiently, and allow for great computational gains.
The only non-parametric regression coreset we are aware of is a form of kernel regression @cite_24 related to the smallest enclosing ball. It predicts the value at a point @math as @math with loss function @math , for a parameter @math . Then it finds a set of @math non-zero @math parameters (corresponding with points in the coreset) so many points satisfy @math . No implementations were attempted.
@cite_24
1497808028 1992065791 1977263019 2951308445
A rigid coreset minimum enclosing ball training machine for kernel regression estimation was proposed. First, it transfers the kernel regression estimation machine problem into a center-constrained minimum enclosing ball representation form, and subsequently trains the kernel methods using the proposed MEB algorithm. The primal variables of the kernel methods are recovered via KKT conditions. Then, detailed theoretical analysis and main theoretical results of our new algorithm are given. It can be concluded that our proposed MEB training algorithm is independent of sample dimension and the time complexity is linear in sample numbers, which greatly cuts down the complexity level and is expected to speedup the learning process obviously. Finally, comments about the future development directions are discussed. We study the (constrained) least-squares regression as well as multiple response least-squares regression and ask the question of whether a subset of the data, a coreset, suffices to compute a good approximate solution to the regression. We give deterministic, low-order polynomial-time algorithms to construct such coresets with approximation guarantees, together with lower bounds indicating that there is not much room for improvement upon our results. Given a set of points P ⊂ Rd and value ∊ > 0, an ∊-core-set S ⊂ P has the property that the smallest ball containing S is an ∊-approximation of the smallest ball containing P. This paper shows that any point-set has an ∊-core-set of size [2 ∊]. We also give a fast algorithm that finds this core-set. These results imply the existence of small core-sets for solving approximate k-center clustering and related problems. The sizes of these core-sets are considerably smaller than the previously known bounds, and imply faster algorithms; one such algorithm needs O(dn ∊ + (l ∊)5) time to compute an ∊-approximate minimum enclosing ball (1-center) of n points in d dimensions. A simple gradient-descent algorithm is also given, for computing the minimum enclosing ball in O(dn ∊2) time. This algorithm also implies slightly faster algorithms for computing approximately the smallest radius k-flat fitting a set of points. Despite its importance, choosing the structural form of the kernel in nonparametric regression remains a black art. We define a space of kernel structures which are built compositionally by adding and multiplying a small number of base kernels. We present a method for searching over this space of structures which mirrors the scientific discovery process. The learned structures can often decompose functions into interpretable components and enable long-range extrapolation on time-series datasets. Our structure search method outperforms many widely used kernels and kernel combination methods on a variety of prediction tasks.