A fast algorithm, Accelerated Kernel Feature Analysis (AKFA), that discovers salient features evidenced in a sample of n unclassified patterns, is presented. Like earlier kernel-based feature selection algorithms, AKFA implicitly embeds each pattern into a Hilbert space, H, induced by a Mercer kernel. An \ell-dimensional linear subspace of H is iteratively constructed by maximizing a variance condition for the nonlinearly transformed sample. This linear subspace can then be used to define more efficient data representations and pattern classifiers. AKFA requires O(\elln2) operations, as compared to 0(n^3) for Sch¨olkof, Smola, and M¨uller’s Kernel Principal Component Analysis (KPCA), and O(\ell^2 n^2) for Smola, Mangasarian, and Sch¨olkopf’s Sparse Kernel Feature Analysis (SKFA). Numerical experiments show that AKFA can generate more concise feature representations than both KPCA and SKFA, and demonstrate that AKFA obtains similar classification performance as KPCA for a face recognition problem.

Outcomes of a Puzzles-First computer science course, offered each Fall semester from 2003 to 2005 at the University of Vermont, indicate that this novel format, which uses mathematical puzzles and games to illustrate fundamental concepts, attracts both computer science majors and non-majors, including a significant number of females.

Query optimizers in object-relational database management systems typically require users to provide the execution cost models of user-defined functions (UDFs). Despite this need, however, there has been little work done to provide such a model. The existing approaches are static in that they require users to train the model a priori with pregenerated UDF execution cost data. Static approaches can not adapt to changing UDF execution patterns and thus degrade in accuracy when the UDF executions used for generating training data do not reflect the patterns of those performed during operation. This article proposes a new approach based on the recent trend of self-tuning DBMS by which the cost model is maintained dynamically and incrementally as UDFs are being executed online. In the context of UDF cost modeling, our approach faces a number of challenges, that is, it should work with limited memory, work with limited computation time, and adjust to the fluctuations in the execution costs (e.g., caching effect). In this article, we first provide a set of guidelines for developing techniques that meet these challenges, while achieving accurate and fast cost prediction with small overheads. Then, we present two concrete techniques developed under the guidelines. One is an instance-based technique based on the conventionalk-nearest neighbor (KNN) technique which uses a multidimensional index like the R*-tree. The other is a summary-based technique which uses the quadtree to store summary values at multiple resolutions. We have performed extensive performance evaluations comparing these two techniques against existing histogram-based techniques and the KNN technique, using both real and synthetic UDFs/data sets. The results show our techniques provide better performance in most situations considered.

As simulation is gaining popularity as an inexpensive means of experimentation in diverse fields of industry and government, the attention to the data generated by scientific simulation is also increasing. Scientific simulation generates mesh data, i.e. data configured in a grid structure, in a sequence of time steps. Its model is complex - understanding it involves mathematical topology and geometry in addition to fields (in the relational sense). Moreover, there is no query language developed on mesh data at all. We develop a comprehensive model of mesh data in an object-oriented manner, propose a set of primitive algebraic operators, show their object-oriented implementation and demonstrate that the well-known object query language OQL (from the ODMG) is powerful enough to express queries on mesh data, whether the queries are on a mesh topology, geometry, fields, or a combination of them. Finally, we discuss some physical implementation issues that are pertinent to executing queries efficiently.

A k-nearest-neighbor classifier is approximated by a labeled cell classifier that recursively labels the nodes of a hierarchically organized reference sample (e.g., a k-d tree) if a local estimate of the conditional Bayes risk is sufficiently small. Simulations suggest that the labeled cell classifier is significantly faster than k-d tree implementations for problems with small Bayes risk, and may be more accurate as a larger reference sample can be examined in a fixed amount of time.

The finite-sample risk of the k-nearest-neighbor classifier is analyzed for a family of two-class problems in which patterns are randomly generated from smooth probability distributions in an n-dimensional Euclidean feature space. First, an exact integral expression for the m-sample risk is obtained for a k-nearest-neighbor classifier that uses a reference sample of m labeled feature vectors. Using a multidimensional application of Laplace's method of integration, this integral can be represented as an asymptotic expansion in negative rational powers of m. The leading terms of this asymptotic expansion elucidate the curse of dimensionality and other properties of the finite-sample risk.

The finite sample performance of a nearest neighbor classifier is analyzed for a two-class pattern recognition problem. An exact integral expression is derived for the m-sample risk R/sub m/ given that a reference m-sample of labeled points is available to the classifier. The statistical setup assumes that the pattern classes arise in nature with fixed a priori probabilities and that points representing the classes are drawn from Euclidean n-space according to fixed class-conditional probability distributions. The sample is assumed to consist of m independently generated class-labeled points. For a family of smooth class-conditional distributions characterized by asymptotic expansions in general form, it is shown that the m-sample risk R/sub m/ has a complete asymptotic series expansion R/sub m//spl sim/R/sub /spl infin//+/spl Sigma//sub k=2//sup /spl infin//c/sub k/m/sup -k/n/ (m/spl rarr//spl infin/), where R/sub /spl infin// denotes the nearest neighbor risk in the infinite-sample limit and the coefficients c/sub k/ are distribution-dependent constants independent of the sample size m. The analysis thus provides further analytic validation of Bellman's curse of dimensionality. Numerical simulations corroborating the formal results are included, and extensions of the theory discussed. The analysis also contains a novel application of Laplace's asymptotic method of integration to a multidimensional integral where the integrand attains its maximum on a continuum of points.>

The finite sample performance of a nearest neighbor classifier is analyzed for a two-class pattern recognition problem. An exact integral expression is derived for the m-sample risk Rm given that a reference m-sample of labeled points, drawn independently from Euclidean n-space according to a fixed probability distri bution, is available to the classifier. For a family of smooth distributions, it is shown that the m-sample risk Rm has a complete asymptotic expansion ******, where ** denotes the nearest neighbor risk in the infinite sample limit. Explicit definitions of the expansion coefficents are given in terms of the underlying distribution. As the convergence rate of **** dramatically slows down as n increases, this analysis provides an analytic validation of Bellman's curse of dimensionality. Numerical simulations corroborating the formal results are included. The rates of convergence for less restrictive families of distributions are also discussed.

We study how certain smoothness constraints, for example, piecewise continuity, can be generalized from a discrete set of analog-valued data, by modifying the error backpropagation, learning algorithm. Numerical simulations demonstrate that by imposing two heuristic objectives — (1) reducing the number of hidden units, and (2) minimizing the magnitudes of the weights in the network — during the learning process, one obtains a network with a response function that smoothly interpolates between the training data.