A practical approximation algorithm for the LMS line estimator

The problem of fitting a straight line to a finite collection of points in the plane is an important problem in statistical estimation. Robust estimators are widely used because of their lack of sensitivity to outlying data points. The least median-of-squares (LMS) regression line estimator is among the best known robust estimators. Given a set of n points in the plane, it is defined to be the line that minimizes the median squared residual or, more generally, the line that minimizes the residual of any given quantile q, where 0<q?1. This problem is equivalent to finding the strip defined by two parallel lines of minimum vertical separation that encloses at least half of the points.The best known exact algorithm for this problem runs in O(n²) time. We consider two types of approximations, a residual approximation, which approximates the vertical height of the strip to within a given error bound ε_r?0, and a quantile approximation, which approximates the fraction of points that lie within the strip to within a given error bound ε_q?0. We present two randomized approximation algorithms for the LMS line estimator. The first is a conceptually simple quantile approximation algorithm, which given fixed q and ε_q>0 runs in O(nlogn) time. The second is a practical algorithm, which can solve both types of approximation problems or be used as an exact algorithm. We prove that when used as a quantile approximation, this algorithm's expected running time is . We present empirical evidence that the latter algorithm is quite efficient for a wide variety of input distributions, even when used as an exact algorithm.     

On classification with incomplete data

We address the incomplete-data problem in which feature vectors to be classified are missing data (features). A (supervised) logistic regression algorithm for the classification of incomplete data is developed. Single or multiple imputation for the missing data is avoided by performing analytic integration with an estimated conditional density function (conditioned on the observed data). Conditional density functions are estimated using a Gaussian mixture model (GMM), with parameter estimation performed using both expectation-maximization (EM) and variational Bayesian EM (VB-EM). The proposed supervised algorithm is then extended to the semisupervised case by incorporating graph-based regularization. The semisupervised algorithm utilizes all available data-both incomplete and complete, as well as labeled and unlabeled. Experimental results of the proposed classification algorithms are shown     

Globally maximizing, locally minimizing: unsupervised discriminant projection with applications to face and palm biometrics

This paper develops an unsupervised discriminant projection (UDP) technique for dimensionality reduction of high-dimensional data in small sample size cases. UDP can be seen as a linear approximation of a multimanifolds-based learning framework which takes into account both the local and nonlocal quantities. UDP characterizes the local scatter as well as the nonlocal scatter, seeking to find a projection that simultaneously maximizes the nonlocal scatter and minimizes the local scatter. This characteristic makes UDP more intuitive and more powerful than the most up-to-date method, locality preserving projection (LPP), which considers only the local scatter for clustering or classification tasks. The proposed method is applied to face and palm biometrics and is examined using the Yale, FERET, and AR face image databases and the PolyU palmprint database. The experimental results show that UDP consistently outperforms LPP and PCA and outperforms LDA when the training sample size per class is small. This demonstrates that UDP is a good choice for real-world biometrics applications     

Some Statistical-Estimation Methods for Stochastic Finite-State Transducers

Formal translations constitute a suitable framework for dealing with many problems in pattern recognition and computational linguistics. The application of formal transducers to these areas requires a stochastic extension for dealing with noisy, distorted patterns with high variability. In this paper, some estimation criteria are proposed and developed for the parameter estimation of regular syntax-directed translation schemata. These criteria are: maximum likelihood estimation, minimum conditional entropy estimation and conditional maximum likelihood estimation. The last two criteria were proposed in order to deal with situations when training data is sparse. These criteria take into account the possibility of ambiguity in the translations: i.e., there can be different output strings for a single input string. In this case, the final goal of the stochastic framework is to find the highest probability translation of a given input string. These criteria were tested on a translation task which has a high degree of ambiguity.     

Maintaining Case-Based Reasoners: Dimensions and Directions

Experience with the growing number of large-scale and long-term case-based reasoning (CBR) applications has led to increasing recognition of the importance of maintaining existing CBR systems. Recent research has focused on case-base maintenance (CBM), addressing such issues as maintaining consistency, preserving competence, and controlling case-base growth. A set of dimensions for case-base maintenance, proposed by Leake and Wilson, provides a framework for understanding and expanding CBM research. However, it also has been recognized that other knowledge containers can be equally important maintenance targets. Multiple researchers have addressed pieces of this more general maintenance problem, considering such issues as how to refine similarity criteria and adaptation knowledge. As with case-base maintenance, a framework of dimensions for characterizing more general maintenance activity, within and across knowledge containers, is desirable to unify and understand the state of the art, as well as to suggest new avenues of exploration by identifying points along the dimensions that have not yet been studied. This article presents such a framework by (1) refining and updating the earlier framework of dimensions for case-base maintenance, (2) applying the refined dimensions to the entire range of knowledge containers, and (3) extending the theory to include coordinated cross-container maintenance. The result is a framework for understanding the general problem of case-based reasoner maintenance (CBRM). Taking the new framework as a starting point, the article explores key issues for future CBRM research.     

Empirical Evaluation of User Models and User-Adapted Systems

Empirical evaluations are needed to determine which users are helped or hindered by user-adapted interaction in user modeling systems. A review of past UMUAI articles reveals insufficient empirical evaluations, but an encouraging upward trend. Rules of thumb for experimental design, useful tests for covariates, and common threats to experimental validity are presented. Reporting standards including effect size and power are proposed.     

Ernest Lepore and Zenon Pylyshyn,What is Cognitive Science?

Minds and Machines -     

The Influence of Evolutionary Selection Schemes on the Iterated Prisoner's Dilemma

Many economic and social systems are essentially large multi-agent systems.By means of computational modeling, the complicated behavior of such systemscan be investigated. Modeling a multi-agent system as an evolutionary agentsystem, several important choices have to be made for evolutionary operators.Especially, it is to be expected that evolutionary dynamics substantiallydepend on the selection scheme. We therefore investigate the influence ofevolutionary selection mechanisms on a fundamental problem: the iteratedprisoner's dilemma (IPD), an elegant model for the emergence of cooperationin a multi-agent system. We observe various types of behavior, cooperationlevel, and stability, depending on the selection mechanism and the selectionintensity. Hence, our results are important for (1) the proper choice andapplication of selection schemes when modeling real economic situations and(2) assessing the validity of the conclusions drawn from computer experimentswith these models. We also conclude that the role of selection in theevolution of multi-agent systems should be investigated further, for instanceusing more detailed and complex agent interaction models.     

Shape Morphing-Based Control of Robotic Visual Servoing

We present an approach for controlling robotic interactions with objects, using synthetic images generated by morphing shapes. In particular, we attempt the problem of positioning an eye-in-hand robotic system with respect to objects in the workspace for grasping and manipulation. In our formulation, the grasp position (and consequently the approach trajectory of the manipulator), varies with each object. The proposed solution to the problem consists of two parts. First, based on a model-based object recognition framework, images of the objects taken at the desired grasp pose are stored in a database. The recognition and identification of the grasp position for an unknown input object (selected from the family of recognizable objects) occurs by morphing its contour to the templates in the database and using the virtual energy spent during the morph as a dissimilarity measure. In the second step, the images synthesized during the morph are used to guide the eye-in-hand system and execute the grasp. The proposed method requires minimal calibration of the system. Furthermore, it conjoins techniques from shape recognition, computer graphics, and vision-based robot control in a unified engineering amework. Potential applications range from recognition and positioning with respect to partially-occluded or deformable objects to planning robotic grasping based on human demonstration.     

Approximation algorithm for hotlink assignment in the greedy model

Link-based information structures such as the web can be enhanced through the addition of hotlinks. Assume that each node in the information structure is associated with a weight representing the access frequency of the node by users. In order to access a particular node, the user must follow a path leading to it from the root. By adding new hotlinks to the tree, it may be possible to reduce the access cost of the system, namely, the expected number of steps needed to reach a leaf from the root, assuming the user can decide which hotlinks to follow in each step. The hotlink assignment   problem involves finding a set of hotlinks (with at most K=O(1)$K=O\left(1\right)$ hotlinks emanating from every node) maximizing the gain in the expected cost. The paper addresses this problem in two user models, namely, the traditional clairvoyant user model employed in [P. Bose, J. Czyzowicz, L. Gasieniec, E. Kranakis, D. Krizanc, A. Pelc, M.V. Martin, Strategies for hotlink assignments, in: Proc. 11th Symp. on Algorithms and Computation, 2000, pp. 23–34; E. Kranakis, D. Krizanc, S. Shende, Approximating hotlink assignments, in: Proc. 12th Symp. on Algorithms and Computation, 2001, pp. 756–767; P. Bose, D. Krizanc, S. Langerman, P. Morin, Asymmetrical communication protocols via hotlink assignments, in: Proc. 9th Colloq. on Structural Information and Communication Complexity, 2002, pp. 33–39; R. Matichin, D. Peleg, Approximation algorithm for hotlink assignments in web directories, in: Proc. Workshop on Algorithms and Data Structures, 2003, pp. 271–280] and the more realistic greedy user model recently introduced in [O. Gerstel, S. Kutten, R. Matichin, D. Peleg, Hotlink enhancement algorithms for web directories, in: Proc. 14th Symp. on Algorithms and Computation, 2003, pp. 68–77], and presents a polynomial time 2-approximation algorithm for the hotlink assignment problem on rooted directed trees.