In many applications of regression, one is concerned with the efficiency of the estimated function in addition to the accuracy of the regression. For efficiency, it is common to represent the estimated function as a rectangular lattice of values-a lookup table (LUT)-that can be linearly interpolated for any needed value. Typically, a LUT is constructed from data with a two-step process that first fits a function to the data, then evaluates that fitted function at the nodes of the lattice. We present an approach, termed lattice regression, that directly optimizes the values of the lattice nodes to minimize the post-interpolation training error. Additionally, we propose a second-order difference regularizer to promote smoothness. We demonstrate the effectiveness of this approach on two image processing tasks that require both accurate regression and efficient function evaluations: inverse device characterization for color management and omnidirectional super-resolution for visual homing.

Local classifiers are sometimes called lazy learners because they do not train a classifier until presented with a test sample. However, such methods are generally not completely lazy because the neighborhood size k (or other locality parameter) is usually chosen by cross validation on the training set, which can require significant preprocessing and risks overfitting. We propose a simple alternative to cross validation of the neighborhood size that requires no preprocessing: instead of committing to one neighborhood size, average the discriminants for multiple neighborhoods. We show that this forms an expected estimated posterior that minimizes the expected Bregman loss with respect to the uncertainty about the neighborhood choice. We analyze this approach for six standard and state-of-the-art local classifiers, including discriminative adaptive metric kNN (DANN), a local support vector machine (SVM-KNN), hyperplane distance nearest neighbor (HKNN), and a new local Bayesian quadratic discriminant analysis (local BDA). The empirical effectiveness of this technique versus cross validation is confirmed with experiments on seven benchmark data sets, showing that similar classification performance can be attained without any training.

We present a new empirical risk minimization framework for approximating functions from training samples for low-dimensional regression applications where a lattice (look-up table) is stored and interpolated at run-time for an efficient hardware implementation. Rather than evaluating a fitted function at the lattice nodes without regard to the fact that samples will be interpolated, the proposed lattice regression approach estimates the lattice to minimize the interpolation error on the given training samples. Experiments show that lattice regression can reduce mean test error compared to Gaussian process regression for digital color management of printers, an application for which linearly interpolating a look-up table (LUT) is standard. Simulations confirm that lattice regression performs consistently better than the naive approach to learning the lattice, particularly when the density of training samples is low.

Local learning methods, such as local linear regression and nearest neighbor classifiers, base estimates on nearby training samples, neighbors. Usually, the number of neighbors used in estimation is fixed to be a global "optimal" value, chosen by cross validation. This paper proposes adapting the number of neighbors used for estimation to the local geometry of the data, without need for cross validation. The term enclosing neighborhood is introduced to describe a set of neighbors whose convex hull contains the test point when possible. It is proven that enclosing neighborhoods yield bounded estimation variance under some assumptions. Three such enclosing neighborhood definitions are presented: natural neighbors, natural neighbors inclusive, and enclosing k-NN. The effectiveness of these neighborhood definitions with local linear regression is tested for estimating lookup tables for color management. Significant improvements in error metrics are shown, indicating that enclosing neighborhoods may be a promising adaptive neighborhood definition for other local learning tasks as well, depending on the density of training samples.

A popular color management standard for controlling color reproduction is the ICC color profile. The core of the ICC profile is a look-up-table which maps a regular grid of device-independent colors to the printer colorspace. To estimate the look-up-table from sample input-output colors, local linear regression has been shown to work better than other methods. An open problem in local linear regression is how to define the locality or neighborhood for each of the local linear regressions. In this paper, new adaptive neighborhood definitions and regularized local linear regression are proposed to address this problem. The adaptive neighborhood definitions enclose the test sample, and are motivated by a result showing they yield bounded estimation variance. An experiment shows that both regularization and the proposed neighborhoods can lead to a significant reduction in error.