We consider the problem of estimating a good maximizer of a black-box function given noisy examples. We propose to fit a new type of function called a global optimization network (GON), defined as any composition of an invertible function and a unimodal function, whose unique global maximizer can be inferred in $\mathcal{O}(D)$ time, and used as the estimate. As an example way to construct GON functions, and interesting in its own right, we give new results for specifying multi-dimensional unimodal functions using lattice models with linear inequality constraints. We extend to conditional GONs that find a global maximizer conditioned on specified inputs of other dimensions. Experiments show the GON maximizers are statistically significantly better predictions than those produced by convex fits, GPR, or DNNs, and form more reasonable predictions for real-world problems.

The goal of active learning is to select the best examples from an unlabeled pool of data to label to improve a model trained with the addition of these labeled examples. We discuss a real-world use case for batch active sampling that works at larger scales. The standard margin algorithm has repeatedly been shown difficult to beat in practice for the classic active sampling set-up, but for larger batches and candidate pools, we show that margin sampling may not provide enough diversity. We present a simple variant of margin sampling for the batch setting that scores candidate samples by their minimum margin to a set of bootstrapped margins, and explain how this proposal increases diversity in a supervised and efficient way, and why it differs from the usual ensemble methods for active sampling. Experiments on benchmark datasets show that the proposed min-margin sampling consistently works better than margin as the batch size grows, and better than the five other diversity-encouraging active sampling methods we tested. Two real-world case studies illustrate the practical value, and help highlight challenges of applying and deploying batch active sampling.

Given a classifier ensemble and a dataset, many examples may be confidently and accurately classified after only a subset of the base models in the ensemble is evaluated. Dynamically deciding to classify early can reduce both mean latency and CPU without harming the accuracy of the original ensemble. To achieve such gains, we propose jointly optimizing the evaluation order of the base models and early-stopping thresholds. Our proposed objective is a combinatorial optimization problem, but we provide a greedy algorithm that achieves a 4-approximation of the optimal solution under certain assumptions, which is also the best achievable polynomial-time approximation bound. Experiments on benchmark and real-world problems show that the proposed Quit When You Can (QWYC) algorithm can speed up average evaluation time by 1.8–2.7 times on even jointly trained ensembles, which are more difficult to speed up than independently or sequentially trained ensembles. QWYC’s joint optimization of ordering and thresholds also performed better in experiments than previous fixed orderings, including gradient boosted trees’ ordering.

We present fast implementations of linear interpolation operators for piecewise linear functions and multi-dimensional look-up tables. These operators are common for efficient transformations in image processing and are the core operations needed for lattice models like deep lattice networks, a popular machine learning function class for interpretable, shape-constrained machine learning. We present new strategies for an efficient compiler-based solution using MLIR to accelerate linear interpolation. For real-world machine-learned multi-layer lattice models that use multidimensional linear interpolation, we show these strategies run 5-10× faster on a standard CPU compared to an optimized C++ interpreter implementation.

We present pairwise fairness metrics for ranking models and regression models that form analogues of statistical fairness notions such as equal opportunity, equal accuracy, and statistical parity. Our pairwise formulation supports both discrete protected groups, and continuous protected attributes. We show that the resulting training problems can be efficiently and effectively solved using existing constrained optimization and robust optimization techniques developed for fair classification. Experiments illustrate the broad applicability and trade-offs of these methods.

We demonstrate how easy it is for modern machine-learned systems to violate common deontological ethical principles and social norms such as “favor the less fortunate,” and “do not penalize good attributes.” We propose that in some cases such ethical principles can be incorporated into a machine-learned model by adding shape constraints that constrain the model to respond only positively to relevant inputs. We analyze the relationship between these deontological constraints that act on individuals and the consequentialist group-based fairness goals of one-sided statistical parity and equal opportunity. This strategy works with sensitive attributes that are Boolean or real-valued such as income and age, and can help produce more responsible and trustworthy AI.

Modern machine learning models are often trained on examples with noisy labels that hurt performance and are hard to identify. In this paper, we provide an empirical study showing that a simple $k$-nearest neighbor-based filtering approach on the logit layer of a preliminary model can remove mislabeled training data and produce more accurate models than many recently proposed methods. We also provide new statistical guarantees into its efficacy.

We propose new multi-input shape constraints across four intuitive categories: complements, diminishers, dominance, and unimodality constraints. We show these shape constraints can be checked and even enforced when training machine-learned models for linear models, generalized additive models, and the nonlinear function class of multi-layer lattice models. Real-world experiments illustrate how the different shape constraints can be used to increase explainability and improve regularization, especially for non-IID train-test distribution shift.

We address the problem of training models with black-box and hard-to-optimize metrics by expressing the metric as a monotonic function of a small number of easy-to-optimize surrogates. We pose the training problem as an optimization over a relaxed surrogate space, which we solve by estimating local gradients for the metric and performing inexact convex projections. We analyze gradient estimates based on finite differences and local linear interpolations, and show convergence of our approach under smoothness assumptions with respect to the surrogates. Experimental results on classification and ranking problems verify the proposal performs on par with methods that know the mathematical formulation, and adds notable value when the form of the metric is unknown.

Many existing fairness criteria for machine learning involve equalizing some metric across protected groups such as race or gender. However, practitioners trying to audit or enforce such group-based criteria can easily face the problem of noisy or biased protected group information. First, we study the consequences of naively relying on noisy protected group labels: we provide an upper bound on the fairness violations on the true groups $G$ when the fairness criteria are satisfied on noisy groups $\hat{G}$. Second, we introduce two new approaches using robust optimization that, unlike the naive approach of only relying on $\hat{G}$, are guaranteed to satisfy fairness criteria on the true protected groups $G$ while minimizing a training objective. We provide theoretical guarantees that one such approach converges to an optimal feasible solution. Using two case studies, we show empirically that the robust approaches achieve better true group fairness guarantees than the naive approach.

Set functions predict a label from a permutation-invariant variable-size collection of feature vectors. We propose making set functions more understandable and regularized by capturing domain knowledge through shape constraints. We show how prior work in monotonic constraints can be adapted to set functions, and then propose two new shape constraints designed to generalize the conditioning role of weights in a weighted mean. We show how one can train standard functions and set functions that satisfy these shape constraints with a deep lattice network. We propose a nonlinear estimation strategy we call the semantic feature engine that uses set functions with the proposed shape constraints to estimate labels for compound sparse categorical features. Experiments on real-world data show the achieved accuracy is similar to deep sets or deep neural networks, but provides guarantees on the model behavior, which makes it easier to explain and debug.

Classifiers can be trained with data-dependent constraints to satisfy fairness goals, reduce churn, achieve a targeted false positive rate, or other policy goals. We study the generalization performance for such constrained optimization problems, in terms of how well the constraints are satisfied at evaluation time, given that they are satisfied at training time. To improve generalization, we frame the problem as a two-player game where one player optimizes the model parameters on a training dataset, and the other player enforces the constraints on an independent validation dataset. We build on recent work in two-player constrained optimization to show that if one uses this two-dataset approach, then constraint generalization can be significantly improved. As we illustrate experimentally, this approach works not only in theory, but also in practice.

Real-world machine learning applications often have complex test metrics, and may have training and test data that are not identically distributed. Motivated by known connections between complex test metrics and cost-weighted learning, we propose addressing these issues by using a weighted loss function with a standard loss, where the weights on the training examples are learned to optimize the test metric on a validation set. These metric-optimized example weights can be learned for any test metric, including black box and customized ones for specific applications. We illustrate the performance of the proposed method on diverse public benchmark datasets and real-world applications. We also provide a generalization bound for the method.

Stochastic classifiers arise in a number of machine learning problems, and have become especially prominent of late, as they often result from constrained optimization problems, e.g. for fairness, churn, or custom losses. Despite their utility, the inherent randomness of stochastic classifiers may cause them to be problematic to use in practice for a variety of practical reasons. In this paper, we attempt to answer the theoretical question of how well a stochastic classifier can be approximated by a deterministic one, and compare several different approaches, proving lower and upper bounds. We also experimentally investigate the pros and cons of these methods, not only in regard to how successfully each deterministic classifier approximates the original stochastic classifier, but also in terms of how well each addresses the other issues that can make stochastic classifiers undesirable.

We present a general framework for solving a large class of learning problems with non-linear functions of classification rates. This includes problems where one wishes to optimize a non-decomposable performance metric such as the F-measure or G-mean, and constrained training problems where the classifier needs to satisfy non-linear rate constraints such as predictive parity fairness, distribution divergences or churn ratios. We extend previous two-player game approaches for constrained optimization to an approach with three players to decouple the classifier rates from the non-linear objective, and seek to find an equilibrium of the game. Our approach generalizes many existing algorithms, and makes possible new algorithms with more flexibility and tighter handling of non-linear rate constraints. We provide convergence guarantees for convex functions of rates, and show how our methodology can be extended to handle sums-of-ratios of rates. Experiments on different fairness tasks confirm the efficacy of our approach.

We show that many machine learning goals can be expressed as “rate constraints” on a model's predictions. We study the problem of training non-convex models subject to these rate constraints (or other non-convex or non-differentiable constraints). In the non-convex setting, the standard approach of Lagrange multipliers may fail. Furthermore, if the constraints are non-differentiable, then one cannot optimize the Lagrangian with gradient-based methods. To solve these issues, we introduce a new “proxy-Lagrangian” formulation. This leads to an algorithm that, assuming access to an optimization oracle, produces a stochastic classifier by playing a two-player non-zero-sum game solving for what we call a semi-coarse correlated equilibrium, which in turn corresponds to an approximately optimal and feasible solution to the constrained optimization problem. We then give a procedure that shrinks the randomized solution down to a mixture of at most $m+1$ deterministic solutions, given $m$ constraints. This culminates in a procedure that can solve non-convex constrained optimization problems with possibly non-differentiable and non-convex constraints, and enjoys theoretical guarantees. We provide extensive experimental results covering a broad range of policy goals, including various fairness metrics, accuracy, coverage, recall, and churn.

We introduce the problem of grouping a finite ground set into blocks where each block is a subset of the ground set and where: (i) the blocks are individually highly valued by a submodular function (both robustly and in the average case) while satisfying block-specific matroid constraints; and (ii) block scores interact where blocks are jointly scored highly, thus making the blocks mutually non-redundant. Submodular functions are good models of information and diversity; thus, the above can be seen as grouping the ground set into matroid constrained blocks that are both intra- and inter-diverse. Potential applications include forming ensembles of classification/regression models, partitioning data for parallel processing, and summarization. In the non-robust case, we reduce the problem to non-monotone submodular maximization subject to multiple matroid constraints. In the mixed robust/average case, we offer a bi-criterion guarantee for a polynomial time deterministic algorithm and a probabilistic guarantee for randomized algorithm, as long as the involved submodular functions (including the inter-block interaction terms) are monotone. We close with a case study in which we use these algorithms to find high quality diverse ensembles of classifiers, showing good results.

We investigate machine learning models that can provide diminishing returns and accelerating returns guarantees to capture prior knowledge or policies about how outputs should depend on inputs. We show that one can build flexible, nonlinear, multi-dimensional models using lattice functions with any combination of concavity/convexity and monotonicity constraints on any subsets of features, and compare to new shape-constrained neural networks. We demonstrate on real-world examples that these shape constrained models can provide tuning-free regularization and improve model understandability.

Knowing when a classifier's prediction can be trusted is useful in many applications and critical for safely using AI. While the bulk of the effort in machine learning research has been towards improving classifier performance, understanding when a classifier's predictions should and should not be trusted has received far less attention. The standard approach is to use the classifier's discriminant or confidence score; however, we show there exists an alternative that is more effective in many situations. We propose a new score, called the {\it trust score}, which measures the agreement between the classifier and a modified nearest-neighbor classifier on the testing example. We show empirically that high (low) trust scores produce surprisingly high precision at identifying correctly (incorrectly) classified examples, consistently outperforming the classifier's confidence score as well as many other baselines. Further, under some mild distributional assumptions, we show that if the trust score for an example is high (low), the classifier will likely agree (disagree) with the Bayes-optimal classifier. Our guarantees consist of non-asymptotic rates of statistical consistency under various nonparametric settings and build on recent developments in topological data analysis.

We propose learning deep models that are monotonic with respect to a user-specified set of inputs by alternating layers of linear embeddings, ensembles of lattices, and calibrators (piecewise linear functions), with appropriate constraints for monotonicity, and jointly training the resulting network. We implement the layers and projections with new computational graph nodes in TensorFlow and use the Adam optimizer and batched stochastic gradients. Experiments on benchmark and real-world datasets show that six-layer monotonic deep lattice networks achieve state-of-the art performance for classification and regression with monotonicity guarantees.

Minimizing empirical risk subject to a set of constraints can be a useful strategy for learning restricted classes of functions, such as monotonic functions, submodular functions, classifiers that guarantee a certain class label for some subset of examples, etc. However, these restrictions may result in a very large number of constraints. Projected stochastic gradient descent (SGD) is often the default choice for large-scale optimization in machine learning, but requires a projection after each update. For heavily-constrained objectives, we propose an efficient extension of SGD that stays close to the feasible region while only applying constraints probabilistically at each iteration. Theoretical analysis shows a compelling trade-off between per-iteration work and the number of iterations needed on problems with a large number of constraints.

Practical applications of machine learning often involve successive training iterations with changes to features and training examples. Ideally, changes in the output of any new model should only be improvements (wins) over the previous iteration, but in practice the predictions may change neutrally for many examples, resulting in extra net-zero wins and losses, referred to as unnecessary churn. These changes in the predictions are problematic for usability for some applications, and make it harder and more expensive to measure if a change is statistically significant positive. In this paper, we formulate the problem and present a stabilization operator to regularize a classifier towards a previous classifier. We use a Markov chain Monte Carlo stabilization operator to produce a model with more consistent predictions without adversely affecting accuracy. We investigate the properties of the proposal with theoretical analysis. Experiments on benchmark datasets for different classification algorithms demonstrate the method and the resulting reduction in churn.

For many machine learning problems, there are some inputs that are known to be positively (or negatively) related to the output, and in such cases training the model to respect that monotonic relationship can provide regularization, and makes the model more interpretable. However, flexible monotonic functions are computationally challenging to learn beyond a few features. We break through this barrier by learning ensembles of monotonic calibrated interpolated look-up tables (lattices). A key contribution is an automated algorithm for selecting feature subsets for the ensemble base models. We demonstrate that compared to random forests, these ensembles produce similar or better accuracy, while providing guaranteed monotonicity consistent with prior knowledge, smaller model size and faster evaluation.

The goal of minimizing misclassification error on a training set is often just one of several real-world goals that might be defined on different datasets. For example, one may require a classifier to also make positive predictions at some specified rate for some subpopulation (fairness), or to achieve a specified empirical recall. Other real-world goals include reducing churn with respect to a previously deployed model, or stabilizing online training. In this paper we propose handling multiple goals on multiple datasets by training with dataset constraints, using the ramp penalty to accurately quantify costs, and present an efficient algorithm to approximately optimize the resulting non-convex constrained optimization problem. Experiments on both benchmark and real-world industry datasets demonstrate the effectiveness of our approach.

Real-world machine learning applications may have requirements beyond accuracy, such as fast evaluation times and interpretability. In particular, guaranteed monotonicity of the learned function with respect to some of the inputs can be critical for user confidence. We propose meeting these goals for low-dimensional machine learning problems by learning flexible, monotonic functions using calibrated interpolated look-up tables. We extend the structural risk minimization framework of lattice regression to monotonic functions by adding linear inequality constraints. In addition, we propose jointly learning interpretable calibrations of each feature to normalize continuous features and handle categorical or missing data, at the cost of making the objective non-convex. We address large- scale learning through parallelization, mini-batching, and random sampling of additive regularizer terms. Case studies on real-world problems with up to sixteen features and up to hundreds of millions of training samples demonstrate the proposed monotonic functions can achieve state-of-the-art accuracy in practice while providing greater transparency to users.

Early classification of time series is important in time-sensitive applications. An approach is presented for early classification using generative classifiers with the dual objectives of providing a class label as early as possible while guaranteeing with high probability that the early class matches the class that would be assigned to a longer time series. We give a specific algorithm for early quadratic discriminant analysis (QDA), and demonstrate that this classifier meets the requirement of reliable early classification.

We present a multi-task learning approach to jointly estimate the means of multiple independent data sets. The proposed multi-task averaging (MTA) algorithm results in a convex combination of the single-task averages. We derive the optimal amount of regularization, and show that it can be effectively estimated. Simulations and real data experiments demonstrate that MTA both maximum likelihood and James-Stein estimators, and that our approach to estimating the amount of regularization rivals cross-validation in performance but is more computationally efficient.

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.

We show how to compute lower bounds for the supremum Bayes error if the class-conditional distributions must satisfy moment constraints, where the supremum is with respect to the unknown class-conditional distributions. Our approach makes use of Curto and Fialkow's solutions for the truncated moment problem. The lower bound shows that the popular Gaussian assumption is not robust in this regard. We also construct an upper bound for the supremum Bayes error by constraining the decision boundary to be linear.

When building a classifier from clean training data for a particular test environment, knowledge about the environmental noise and channel should be taken into account. We propose training a support vector machine (SVM) classifier using a modified kernel that is the expected kernel with respect to a probability distribution over channels and noise that might affect the test signal. We compare the proposed expected SVM to an SVM that ignores the environment, to an SVM that trains with multiple random samples of the environment, and to a quadratic discriminant analysis classifier that takes advantage of environment statistics (Joint QDA). Simulations classifying narrowband signals in a noisy acoustic reverberation environment indicate that the expected SVM can improve performance over a range of noise levels.

Although the Dirichlet distribution is widely used, the independence structure of its components limits its accuracy as a model. The proposed shadow Dirichlet distribution manipulates the support in order to model probability mass functions (pmfs) with dependencies or constraints that often arise in real world problems, such as regularized pmfs, monotonic pmfs, and pmfs with bounded variation. We describe some properties of this new class of distributions, provide maximum entropy constructions, give an expectation-maximization method for estimating the mean parameter, and illustrate with real data.

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.

The role of gradient estimation in global optimization is investigated. The concept of a regional gradient is introduced as a tool for analyzing and comparing different types of gradient estimates. The correlation of different estimated gradients to the direction of the global optima is evaluated for standard test functions. Experiments quantify the impact of different gradient estimation techniques in two population-based global optimization algorithms: fully-informed particle swarm (FIPS) and multiresolutional estimated gradient architecture (MEGA).

This work addresses the problem of classifying the genre of text, which is useful for a variety of language processing problems. We propose statistics of POS histograms as classification features, coupled with a quadratic discriminant classifier. In experiments on six different text and speech genres, we demonstrate enhanced performance compared to standard techniques using word frequency count features and POS trigram features. Experiments on genres that were not seen in training show intuitive overlaps with the training classes.

In language modeling for speech recognition, both the amount of training data and the match to the target task impact the goodness of the model, with the trade-off usually favoring more data. For conversational speech, having some genre-matched text is particularly important, but also hard to obtain. This paper proposes a new approach for genre detection and compares different alternatives for filtering Web text for genre to improve language models for use in automatic transcription of broadcast conversations (talk shows).

We consider the estimation of the locations of multiple transmitters based on received signal strength measurements at a network of randomly-placed receivers. We generalize the expectation-maximization (EM) method to create a quasi EM algorithm for localization under lognormal shadowing. Simulated performance is compared to a state-of-the-art global optimizer and to random guessing. Results reveal that the proposed quasi EM algorithm outperforms both alternatives in median and ninety-fifth percentile error, especially as the number of receivers increases.

Similarity measures in many real applications generate indefinite similarity matrices. In this paper, we consider the problem of classification based on such indefinite similarities. These indefinite kernels can be problematic for standard kernel-based algorithms as the optimization problems become non-convex and the underlying theory is invalidated. In order to adapt kernel methods for similarity-based learning, we introduce a method that aims to simultaneously find a reproducing kernel Hilbert space based on the given similarities and train a classifier with good generalization in that space. The method is formulated as a convex optimization problem. We propose a simplified version that can reduce overfitting and whose associated convex conic program can be solved efficiently. We compare the proposed simplified version with six other methods on a collection of real data sets.

We investigate parameter-based and distribution-based approaches to regularizing the generative, similarity-based classifier called local similarity discriminant analysis classifier (local SDA). We argue that regularizing distributions rather than parameters can both increase the model flexibility and decrease estimation variance while retaining the conceptual underpinnings of the local SDA classifier. Experiments with four benchmark similarity-based classification datasets show that the proposed regularization significantly improves classification performance compared to the local SDA classifier, and the distribution-based approach improves performance more consistently than the parameter-based approaches. Also, regularized local SDA can perform significantly better than similarity-based SVM classifiers, particularly on sparse and highly nonmetric similarities.

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.

We consider estimating multiple transmitter locations based on received signal strength measurements by a sensor network of randomly located receivers. This problem is motivated by the search for available spectrum in cognitive radio applications. We create a quasi expectation maximization (EM) algorithm for localization under lognormal shadowing. Simulated performance is compared to random guessing and to global optimization using constriction particle swarm (CPSO). Results show that the proposed quasi EM algorithm outperforms both alternatives given a fixed number of guesses, and the performance gap grows as the number of transmitters increases.

A multiresolutional regularization method is proposed for local linear regression that regularizes local mean squared-error by the mean squared-error of a larger neighborhood. The approach is similar in motivation to generalized Tikhonov regularization, but because the regularization trades-off between two like quantities, it is easier to interpret and specify the regularization parameter. Color management experiments with printers are used to compare the proposed regularized local linear regression to ridge regularization and generalized Tikhonov regularization. The local linear regressions use previously-validated adaptive neighborhoods. Results show that significant reductions in error can be achieved over the state-of-the-art.

For two-class classification, it is common to classify by setting a threshold on class probability estimates, where the threshold is determined by ROC curve analysis. An analog for multi-class classification is learning a new class partitioning of the multiclass probability simplex to minimize empirical misclassification costs. We analyze the interplay between systematic errors in the class probability estimates and cost matrices for multiclass classification. We explore the effect on the class partitioning of five different transformations of the cost matrix. Experiments on benchmark datasets with naive Bayes and quadratic discriminant analysis show the effectiveness of learning a new partition matrix compared to previously proposed methods. 1.

To characterize the differences between two positive functions or two distributions, a class of distortion functions has recently been defined termed the functional Bregman divergences. The class generalizes the standard Bregman divergence defined for vectors, and includes total squared difference and relative entropy. Recently a key property was discovered for the vector Bregman divergence: that the mean minimizes the average Bregman divergence for a finite set of vectors. In this paper the analog result is proven: that the mean function minimizes the average Bregman divergence for a set of positive functions that can be parameterized by a finite number of parameters. In addition, the relationship of the functional Bregman divergence to the vector Bregman divergence and pointwise Bregman divergence is stated, as well as some important properties.

Estimating the entropy of a Gaussian distribution from samples drawn from the distribution is a difficult problem when the number of samples is smaller than the number of dimensions. A new Bayesian entropy estimator is proposed using an inverted Wishart distribution and a data-dependent prior that handles the small-sample case. Experiments for six different cases show that the proposed estimator provides good performance for the small-sample case compared to the standard nearest-neighbor entropy estimator. Additionally, it is shown that the Bayesian estimate formed by taking the expected entropy minimizes expected Bregman divergence.

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 class of distortions termed functional Bregman divergences is defined, which includes squared error and relative entropy. A functional Bregman divergence acts on functions or distributions, and generalizes the standard Bregman divergence for vectors and a previous pointwise Bregman divergence that was defined for functions. A recent result showed that the mean minimizes the expected Bregman divergence. The new functional definition enables the extension of this result to the continuous case to show that the mean minimizes the expected functional Bregman divergence over a set of functions or distributions. It is shown how this theorem applies to the Bayesian estimation of distributions. Estimation of the uniform distribution from independent and identically drawn samples is presented as a case study.

For many sensing modalities such as sonar, received signals are corrupted by multipath and can be challenging for automatic classification systems. An approach to jointly deconvolve and classify such signals is proposed. Specifically, a filter is estimated that minimizes the distortion between the received signal and a set of training signals, then the received signal is assigned to the class that corresponds to the training signal whose estimated filter is most sparse. Simulations compare the new method with blind deconvolution using Cabrelli's algorithm followed by a correlation-based nearest neighbor classifier. Results indicate that joint deconvolution and classification performs similarly to blind deconvolution in the presence of severe noise, and outperforms blind deconvolution at low and moderate noise levels.

Signals acquired through a microphone array are typically beamformed to combine channels and improve the signal-to-noise ratio (SNR). However, it has been previously shown that alternative methods for handling multi-channel systems can outperform beamforming for speech recognition applications. In this paper, we implemented a comprehensive set of classification tests using multiple classifiers and feature extraction techniques to determine whether the alternative methods generalize beyond speech recognition applications. We show that applying the alternative methods (in a slightly simpler form) outperforms beamforming when used for classifying transient acoustic projectile weapon signals. Furthermore, an additional technique is introduced which outperforms both beamforming and previously proposed alternatives in certain classification scenarios. For the majority of classification tests, the improvements seen through the use of these alternative methods are statistically significant.

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.

A set of three fixed basis functions is proposed for the linear projection of hyperspectral images into a set of three images that can be displayed on the red, green, and blue channels of a standard display. The proposed basis functions were designed to meet specific criteria for maximizing interpretability of the visualization and correspondence of the perceived visualization to the original hyperspectral data. The constraints of the standardized display-device colorspace sRGB were taken into account, and the design was optimized using the perceptual colorspace CIELab. This work improves upon a previous fixed basis function method, the stretched CMF basis functions. A method for taking into account the different SNR of each frequency band is also proposed. Example visualizations are shown for AVIRIS hyperspectral imagery.

We propose a local, generative model for similarity-based classification. The method is applicable to the case that only pairwise similarities between samples are available. The classifier models the local class-conditional distribution using a maximum entropy estimate and empirical moment constraints. The resulting exponential class conditional-distributions are combined with class prior probabilities and misclassification costs to form the local similarity discriminant analysis (local SDA) classifier. We compare the performance of local SDA to a non-local version, to the local nearest centroid classifier, the nearest centroid classifier, k-NN, and to the recently-developed potential support vector machine (PSVM). Results show that local SDA is competitive with k-NN and the computationally-demanding PSVM while offering the advantages of a generative classifier.

A generative model for similarity-based classification is proposed using maximum entropy estimation. First, a descriptive set of similarity statistics is assumed to be sufficient for classification. Then the class conditional distributions of these descriptive statistics are estimated as the maximum entropy distributions subject to empirical moment constraints. The resulting exponential class conditional distributions are used in a maximum a posteriori decision rule, forming the similarity discriminant analysis (SDA) classifier. The relationship between SDA and the quadratic discriminant analysis classifier is discussed. An example SDA classifier is given that uses the class centroids as the descriptive statistics. Compared to the nearest-centroid classifier, which is also based only on the class centroids, simulation and experimental results show SDA consistently improves performance.

Many remote-sensing applications produce large sets of images, such as hyperspectral images or time-indexed image sequences. We explore methods to display such image sets by linearly projecting them onto basis functions designed for the red, green, and blue (RGB) primaries of a standard tristimulus display, for the human visual system, and for the signal-to-noise ratio of the dataset, creating a single color image. Projecting the data onto three basis functions reduces the information but allows each datapoint to be rendered by a single color. Principal components analysis is perhaps the most commonly used linear projection method, but it is data adaptive and, thus, yields inconsistent visualizations that may be difficult to interpret. Instead, we focus on designing fixed basis functions based on optimizing criteria in the perceptual colorspace CIELab and the standardized device colorspace sRGB. This approach yields visualizations with rich meaning that users can readily extract. Example visualizations are shown for passive radar video and Airborne Visible/Infrared Imaging Spectrometer hyperspectral imagery. Additionally, we show how probabilistic classification information can be layered on top of the visualization to create a customized nonlinear representation of an image set.

In this paper we present a novel optimization algorithm that estimates gradients over regions to search for optima of a non-convex function on both a local and global scale. The proposed architecture is based on three concepts: using the memory of previously evaluated points, multiresolutional search, and the estimation of gradients at these different resolutions to direct the search. This multiresolution estimated gradient architecture (MEGA) shows promise to perform competitively when compared to standard global searches. Comparisons on the Rosenbrock, Griewank, and sinusoidal test functions show that MEGA can converge faster than particle swarm optimization, particularly as dimensionality of a problem increases.

We investigate reducing the dimensionality of image sets by using principal component analysis on wavelet coefficients to maximize edge energy in the reduced dimension images. Large image sets, such as those produced with hyperspectral imaging, are often projected into a lower dimensionality space for image processing tasks. Spatial information is important for certain classification and detection tasks, but popular dimensionality reduction techniques do not take spatial information into account. Dimensionality reduction using principal components analysis on wavelet coefficients is investigated. Equivalences and differences to conventional principal components analysis are shown, and an efficient workflow is given. Experiments on AVIRIS images show that the wavelet energy in any given subband of the reduced dimensionality images can be increased with this method.

We introduce a definition of similarity based on Tversky's set-theoretic linear contrast model and on information-theoretic principles. The similarity measures the residual entropy with respect to a random object. This residual entropy similarity strongly captures context, which we conjecture is important for similarity-based statistical learning. Properties of the similarity definition are established and examples illustrate its characteristics. We show that a previously-defined information-theoretic similarity is also set-theoretic, and compare it to the residual entropy similarity. The similarity between random objects is also treated

This paper considers a distribution-based Bayesian estimation for classification by quadratic discriminant analysis, instead of the standard parameter-based Bayesian estimation. This approach also yields closed form solutions, but removes the parameter-based restriction of requiring more training samples than feature dimensions. We investigate how to define a prior so that it has an adaptively regularizing effect: yielding robust estimation when the number of training samples are small compared to the number of feature dimensions, but converging as the number of data points grows large. Comparative performance on a suite of simulations shows that the distribution-based Bayesian discriminant analysis is advantageous in terms of average error

Nonparametric neighborhood methods for learning entail estimation of class conditional probabilities based on relative frequencies of samples that are "near-neighbors" of a test point. We propose and explore the behavior of a learning algorithm that uses linear interpolation and the principle of maximum entropy (LIME). We consider some theoretical properties of the LIME algorithm: LIME weights have exponential form; the estimates are consistent; and the estimates are robust to additive noise. In relation to bias reduction, we show that near-neighbors contain a test point in their convex hull asymptotically. The common linear interpolation solution used for regression on grids or look-up-tables is shown to solve a related maximum entropy problem. LIME simulation results support use of the method, and performance on a pipeline integrity classification problem demonstrates that the proposed algorithm has practical value.

Summary form only given. We propose a new approach to segmenting mixed raster content images for compression by wavelet encoders and binary compressors. Though wavelets are efficient at modeling edges in natural images, text and sharp edges can be more effectively represented by a binary mask than with wavelets. A common approach to mixed raster content documents is to segment images from text, and separately compress images and a binary mask that defines the segmentation. We propose that the segmentation be done jointly with a projection-onto-convex-sets (POCS) smoothing, with the design goal of segmented images that have a minimal number of nonzero wavelet coefficients. Our goal is a document segmentation that is easy to compress. Knowing that the image encoder will be a lossy wavelet coder, we approximate the above goal as minimizing the number of nonzero wavelet coefficients. We attempt to achieve this goal by jointly choosing the mask and data-filling.

We consider the problem of automatically learning color enhancements from a small set of sample color pairs, and then describing the enhancement by a three-dimensional look-up-table that can be stored and implemented as an ICC profile. We propose a new method for automatically learning a neighborhood for local statistical learning methods such as local linear regression, and show that this leads to relatively accurate descriptions of the desired color transformation and results in images that appear smooth and have natural depth of detail. In a previous work we showed that learning arbitrary color enhancements could result in colored specular highlights, causing images to look unnatural. We show that this can be solved by adding a null sample that maps white to white.

Design goals and solutions are proposed for the display of hyperspectral imagery on tristimulus displays. The requirements of a hyperspectral visualization depend on the task. We focus on creating consistent representations of hyperspectral data that can facilitate understanding and analysis of hyperspectral scenes, and may be used in conjunction with task-specific visualizations. Fixed linear spectral weighting envelopes are given which create natural looking imagery where hue, brightness, saturation and white-point have meanings consistent with the human visual system interpretation of natural scenes. For AVIRIS images, hue interpretation of water and vegetation is also preserved. The proposed designs avoid the pre-attentive distractions of PCA imagery, and provide comparable spectral and edge discriminability.

Design goals and solutions are proposed for the display of hyperspectral imagery on tristimulus displays. The requirements of a hyperspectral visualization depend on the task. We focus on creating consistent representations of hyperspectral data that can facilitate understanding and analysis of hyperspectral scenes, and may be used in conjunction with task-specific visualizations. Fixed linear spectral weighting envelopes are given, creating natural-looking imagery where hue, brightness, saturation, and whitepoint have meanings consistent with the human visual system interpretation of natural scenes. For Airborne Visible/Infrared Imaging Spectrometer images, hue interpretation of water and vegetation is also preserved. The proposed designs avoid the preattentive distractions of principal component analysis imagery, and appear to provide comparable or enhanced spectral and edge discriminability.

The problem of estimating a pmf q over a discrete and finite set of mutually exclusive events given prior (but incomplete) information does not generally have a unique solution, and a unique estimate is often determined by exercising a principle, such as the maximum likelihood principle, or the principle of maximum entropy. This paper proposes a nonparametric principle of minimum expected risk and explain why it might be an appropriate tool of inference for some applications.

Recently developed optical inspection tools provide images from the inside of natural gas pipelines to monitor pipeline integrity. The vast amount of data generated prohibits human inspection of the resulting images. We designed an image processing and classification method to identify ab- normal events. Non-overlapping image blocks are classified into twelve categories: normal, black line, grinder marks, magnetic flux leakage inspector marks, single dots, small black corrosion dots, osmosis blisters, corrosion dots, longitudinal weld, field joint, cavity at a weld and longitudinal weld too close to field joints. Results compare different types of statistical classifiers. Features extracted from the pipeline image are designed to mimic the features humans use to identify the different classes. Difficulties include the large number of classes, the uneven costs associated with different errors, and training on a limited amount of expert classified data. Classification results show this to be a useful tool for pipeline monitoring.

We propose a new estimation method using the maximum entropy principle and show that it is successfully used for the three-dimensional interpolation step involved in many color conversions. Color conversions are a key part of color management systems, and many device characterizations, especially for printers, rely on multidimensional interpolation to perform the conversion. Our method is a linear interpolation that is not limited in the number of sample points used to estimate new color values. We find a unique solution to the underdetermined inverse matrix problem by invoking the maximum entropy principle. We compare our approach to the standard technique of tetrahedral interpolation and demonstrate that more accurate and more robust approximations may result.

An important halftoning problem faced in the design of many color printers and copiers is to represent a 24-bit color image by a small number of preset output colors, generally at a higher spatial resolution. We propose dividing the input and output image into corresponding small blocks, calculating each input block's color average, and then determining a set of the printing colors for the corresponding output block to best render the input block's average color. Our method exploits the higher spatial resolution of the printing process and yields constrained local color optimality. Artifacts common with error diffusion methods do not occur. In an experimental comparison to vector color error diffusion halftoning, block color quantization yields superior rendering of graphics. For natural images, block color quantization may occasionally generate false contours, but due to the lack of texture artifacts, block color quantization halftones may be preferable to error diffusion halftones.