We analyze the performance of a class of manifold-learning algorithms that find their output by minimizing a quadratic form under some normalization constraints. This class consists of Locally Linear Embedding (LLE), Laplacian Eigenmap, Local Tangent Space Alignment (LTSA), Hessian Eigenmaps (HLLE), and Diffusion maps. We present and prove conditions on the manifold that are necessary for the success of the algorithms. Both the finite sample case and the limit case are analyzed. We show that there are simple manifolds in which the necessary conditions are violated, and hence the algorithms cannot recover the underlying manifolds. Finally, we present numerical results that demonstrate our claims.

Past research on probabilistic databases has studied the problem of answering queries on a static database. Application scenarios of probabilistic databases however often involve the conditioning of a database using additional information in the form of new evidence. The conditioning problem is thus to transform a probabilistic database of priors into a posterior probabilistic database which is materialized for subsequent query processing or further refinement. It turns out that the conditioning problem is closely related to the problem of computing exact tuple confidence values. It is known that exact confidence computation is an NP-hard problem. This has led researchers to consider approximation techniques for confidence computation. However, neither conditioning nor exact confidence computation can be solved using such techniques. In this paper we present efficient techniques for both problems. We study several problem decomposition methods and heuristics that are based on the most successful search techniques from constraint satisfaction, such as the Davis-Putnam algorithm. We complement this with a thorough experimental evaluation of the algorithms proposed. Our experiments show that our exact algorithms scale well to realistic database sizes and can in some scenarios compete with the most efficient previous approximation algorithms.

Advancing AI Research and Applications by Learning from What Went Wrong and Why

It is useful to note that many of the reasons why some otherwise meritorious AI applications fail have nothing to do with the AI per se, but rather, with systems engineering and organizational issues. Some embedded AI systems may work well for years on a software platform that is orphaned and porting it would be prohibitively expensive. The delivered application system might work well, but it could be hard to maintain internally. The system may work according to the sponsor's requirements, but it might not be applied to the part of the problem that delivers the largest economic results; or the system might not produce enough visible organizational benefits to protect it in subsequent budget battles.

Ten years ago I was a junior faculty member in a UK university, doing research into the theoretical foundations of multiagent systems. I enjoyed the research, but not the salary. The opportunity arose to work for a startup company at three times my university salary, and the company had already hired some excellent agent researchers that I knew, respected, and liked from conferences and workshops. The job seemed too good to be true; and of course, it was.

The third international conference on Human-Robot Interaction (HRI-2008) was held in Amsterdam, The Netherland, March 12-15, 2008. The theme of HRI-2008, "Living With Robots", highlights the importance of the technical and social issues underlying human-robot interaction with companion and assistive robots for long-term use in everyday life and work activities. More than two hundred and fifty researchers, practitioners, and exhibitors attended the conference, and many more contributed to the conference as authors or reviewers. HRI-2009 will be held in San Diego, California from March 11-13, 2009.

The goal of the Electric Elves project was to develop software agent technology to support human organizations. We developed a variety of applications of the Elves, including scheduling visitors, managing a research group (the Office Elves), and monitoring travel (the Travel Elves). The Travel Elves were eventually deployed at DARPA, where things did not go exactly as planned. In this article, we describe some of the things that went wrong and then present some of the lessons learned and new research that arose from our experience in building the Travel Elves.

When things go badly, we notice that something is amiss, figure out what went wrong and why, and attempt to repair the problem. Artificial systems depend on their human designers to program in responses to every eventuality and therefore typically don't even notice when things go wrong, following their programming over the proverbial, and in some cases literal, cliff. This article describes our past and current work on the Meta-Cognitive Loop, a domain-general approach to giving artificial systems the ability to notice, assess, and repair problems. The goal is to make artificial systems more robust and less dependent on their human designers.

(ESAS 2008).

I developed what I scored, and those with the lowest scores could be removed before running C4.5 to build a decision tree with the remainder. I ran an experiment in which I removed the bottom 10 percent of the instances in a University of California, Irvine (UCI) data set. The resulting tree was smaller and more accurate (as measured by 10-fold CV) than the tree built on the full data set. Then I removed the bottom 20 percent of the instances and got a tree that was smaller than the last one and just as accurate. At that point I had the feeling that this was going to make a great paper for the International Conference on Machine Learning (ICML).