We introduce a technique for dimensionality estimation based on the notion ofquantization dimension, which connects the asymptotic optimal quantization error for a probability distribution on a manifold to its intrinsic dimension.The definition of quantization dimension yields a family of estimation algorithms, whose limiting case is equivalent to a recent method based on packing numbers. Using the formalism of high-rate vector quantization, we address issues of statistical consistency and analyze thebehavior of our scheme in the presence of noise.

This paper presents a non-asymptotic statistical analysis of Kernel-PCA with a focus different from the one proposed in previous work on this topic. Here instead of considering the reconstruction error of KPCA we are interested in approximation error bounds for the eigenspaces themselves. Weprove an upper bound depending on the spacing between eigenvalues but not on the dimensionality of the eigenspace. As a consequence thisallows to infer stability results for these estimated spaces.

For this purpose, we propose a stochastic procedure, the mirror descent, which performs gradient descent inthe dual space. The generated estimates are additionally averaged in a recursive fashion with specific weights. Mirror descent algorithms havebeen developed in different contexts and they are known to be particularly efficient in high dimensional problems. Moreover their implementation is adapted to the online setting. The main result of the paper is the upper bound on the convergence rate for the generalization error.

A general analysis of the limiting distribution of neural network functions is performed, with emphasis on non-Gaussian limits. We show that with i.i.d.

We present a method for nonparametric regression that performs bandwidth selectionand variable selection simultaneously. The approach is based on the technique of incrementally decreasing the bandwidth in directions wherethe gradient of the estimator with respect to bandwidth is large. When the unknown function satisfies a sparsity condition, our approach avoids the curse of dimensionality, achieving the optimal minimax rateof convergence, up to logarithmic factors, as if the relevant variables wereknown in advance. The method--called rodeo (regularization of derivative expectation operator)--conducts a sequence of hypothesis tests, and is easy to implement. A modified version that replaces hard with soft thresholding effectively solves a sequence of lasso problems.

Active learners alleviate the burden of labeling large amounts of data by detecting and asking the user to label only the most informative examples in the domain. We focus here on active learning for multi-view domains, in which there are several disjoint subsets of features (views), each of which is sufficient to learn the target concept. In this paper we make several contributions. First, we introduce Co-Testing, which is the first approach to multi-view active learning. Second, we extend the multi-view learning framework by also exploiting weak views, which are adequate only for learning a concept that is more general/specific than the target concept. Finally, we empirically show that Co-Testing outperforms existing active learners on a variety of real world domains such as wrapper induction, Web page classification, advertisement removal, and discourse tree parsing.

Efficient representations and solutions for large decision problems with continuous and discrete variables are among the most important challenges faced by the designers of automated decision support systems. In this paper, we describe a novel hybrid factored Markov decision process (MDP) model that allows for a compact representation of these problems, and a new hybrid approximate linear programming (HALP) framework that permits their efficient solutions. The central idea of HALP is to approximate the optimal value function by a linear combination of basis functions and optimize its weights by linear programming. We analyze both theoretical and computational aspects of this approach, and demonstrate its scale-up potential on several hybrid optimization problems.

We present a novel framework for integrating prior knowledge into discriminative classifiers. Our framework allows discriminative classifiers such as Support Vector Machines (SVMs) to utilize prior knowledge specified in the generative setting. The dual objective of fitting the data and respecting prior knowledge is formulated as a bilevel program, which is solved (approximately) via iterative application of second-order cone programming. To test our approach, we consider the problem of using WordNet (a semantic database of English language) to improve low-sample classification accuracy of newsgroup categorization. WordNet is viewed as an approximate, but readily available source of background knowledge, and our framework is capable of utilizing it in a flexible way.

TEXTAL is a computer program that automatically interprets electron density maps to determine the atomic structures of proteins through X-ray crystallography. Electron density maps are traditionally interpreted by visually fitting atoms into density patterns. This manual process can be time-consuming and error prone, even for expert crystallographers. To automate the process, TEXTAL employs a variety of AI and pattern-recognition techniques that emulate the decision-making processes of domain experts.

TEXTAL is a computer program that automatically interprets electron density maps to determine the atomic structures of proteins through X-ray crystallography. Electron density maps are traditionally interpreted by visually fitting atoms into density patterns. This manual process can be time-consuming and error prone, even for expert crystallographers. Noise in the data and limited resolution make map interpretation challenging. To automate the process, TEXTAL employs a variety of AI and pattern-recognition techniques that emulate the decision-making processes of domain experts. In this article, we discuss the various ways AI technology is used in TEXTAL, including neural networks, case-based reasoning, nearest neighbor learning and linear discriminant analysis. The AI and pattern-recognition approaches have proven to be effective for building protein models even with medium resolution data. TEXTAL is a successfully deployed application; it is being used in more than 100 crystallography labs from 20 countries.