The performance of regular and irregular Gallager-type errorcorrecting codeis investigated via methods of statistical physics. The transmitted codeword comprises products of the original message bitsselected by two randomly-constructed sparse matrices; the number of nonzero row/column elements in these matrices constitutes a family of codes. We show that Shannon's channel capacity may be saturated in equilibrium for many of the regular codes while slightly lower performance is obtained for others which may be of higher practical relevance. Decoding aspects are considered byemploying the TAP approach which is identical to the commonly used belief-propagation-based decoding. We show that irregular codes may saturate Shannon's capacity but with improved dynamical properties. 1 Introduction The ever increasing information transmission in the modern world is based on reliably communicatingmessages through noisy transmission channels; these can be telephone lines, deep space, magnetic storing media etc. Error-correcting codes play a significant role in correcting errors incurred during transmission; this is carried out by encoding the message prior to transmission and decoding the corrupted received code-word for retrieving the original message.

We present a class of approximate inference algorithms for graphical models of the QMR-DT type. We give convergence rates for these algorithms andfor the Jaakkola and Jordan (1999) algorithm, and verify these theoretical predictions empirically.

In this paper we discuss the semiparametric statistical model for blind deconvolution. First we introduce a Lie Group to the manifold of noncausal FIRfilters. Then blind deconvolution problem is formulated in the framework of a semiparametric model, and a family of estimating functions is derived for blind deconvolution. A natural gradient learning algorithmis developed for training noncausal filters. Stability of the natural gradient algorithm is also analyzed in this framework.

The idea of a large minimum margin [17] explains the good generalization performance ofAdaBoost in the low noise regime. However, AdaBoost performs worse on noisy tasks [10, 11], such as the iris and the breast cancer benchmark data sets [1]. On the latter tasks, a large margin on all training points cannot be achieved without adverse effects on the generalization error. This experimental observation was supported by the study of [13] where the generalization error of ensemble methods wasbounded by the sum of the fraction of training points which have a margin smaller than some value p, say, plus a complexity term depending on the base hypotheses andp. While this bound can only capture part of what is going on in practice, it nevertheless already conveys the message that in some cases it pays to allow for some points which have a small margin, or are misclassified, if this leads to a larger overall margin on the remaining points. To cope with this problem, it was mandatory to construct regularized variants of AdaBoost, which traded off the number of margin errors and the size of the margin 562 G.Riitsch, B. Sch6lkopf, A. J. Smola, K.-R.

An important issue in neural computing concerns the description of learning dynamics with macroscopic dynamical variables. Recent progresson online learning only addresses the often unrealistic case of an infinite training set. We introduce a new framework to model batch learning of restricted sets of examples, widely applicable toany learning cost function, and fully taking into account the temporal correlations introduced by the recycling of the examples. For illustration we analyze the effects of weight decay and early stopping during the learning of teacher-generated examples.

This article describes a methodology for programming robots known as probabilistic robotics. The probabilistic paradigm pays tribute to the inherent uncertainty in robot perception, relying on explicit representations of uncertainty when determining what to do. This article surveys some of the progress in the field, using in-depth examples to illustrate some of the nuts and bolts of the basic approach. My central conjecture is that the probabilistic approach to robotics scales better to complex real-world applications than approaches that ignore a robot's uncertainty.

In addition, to cope with conflicts caused by changes in actual operations, the airport authority also needs to make real-time problem-solving decisions on stand reassignments. the Hong Kong International Airport The stand-allocation system ( Figure world's busiest international airports in terms 1 is a snapshot of the The Although there were some initial hitches when system is installed and used in the Airport the new airport opened on 6 July 1998, operations Control Center (ACC), which is located in the quickly returned to normal within a control tower. Within a month, operational statistics management, and reactive scheduling capabilities surpassed those of the old airport--80 for stand management. The system supports percent of all flights were on time or within 15 concurrent use by multiple operators in minutes of schedule, all passengers cleared nonstop 24-hour-a-day operations because immigration within 15 minutes, and average HKIA is a 24-hour airport. Typically, a human operator must have several years of experience to acquire enough knowledge about airport operations before he/she can produce a "good" quality stand-assignment plan. Generating an allocation plan manually not only requires a highly experienced individual but is also very time consuming because it requires balancing many objectives against many possible alternatives.

Stochastic sampling algorithms, while an attractive alternative to exact algorithms in very large Bayesian network models, have been observed to perform poorly in evidential reasoning with extremely unlikely evidence. To address this problem, we propose an adaptive importance sampling algorithm, AIS-BN, that shows promising convergence rates even under extreme conditions and seems to outperform the existing sampling algorithms consistently. Three sources of this performance improvement are (1) two heuristics for initialization of the importance function that are based on the theoretical properties of importance sampling in finite-dimensional integrals and the structural advantages of Bayesian networks, (2) a smooth learning method for the importance function, and (3) a dynamic weighting function for combining samples from different stages of the algorithm. We tested the performance of the AIS-BN algorithm along with two state of the art general purpose sampling algorithms, likelihood weighting (Fung & Chang, 1989; Shachter & Peot, 1989) and self-importance sampling (Shachter & Peot, 1989). We used in our tests three large real Bayesian network models available to the scientific community: the CPCS network (Pradhan et al., 1994), the PathFinder network (Heckerman, Horvitz, & Nathwani, 1990), and the ANDES network (Conati, Gertner, VanLehn, & Druzdzel, 1997), with evidence as unlikely as 10^-41. While the AIS-BN algorithm always performed better than the other two algorithms, in the majority of the test cases it achieved orders of magnitude improvement in precision of the results. Improvement in speed given a desired precision is even more dramatic, although we are unable to report numerical results here, as the other algorithms almost never achieved the precision reached even by the first few iterations of the AIS-BN algorithm.

As the English striker Gary Lineker famously said, "Football is a very simple game. For 90 minutes, 22 men go running after the ball, and at the end, the Germans win." Although the game is simple, analyzing it can be hard. Just what makes one team better than another? How much difference do tactics make? Is there really such a thing as a "lucky win?" Here, we try to answer these questions in the context of RoboCup. We take the giant set of log data produced by the simulator tournaments from 1997 to 1999 and feed it to a data-munching program that produces statistics on important game features. Using these statistics, we identify precisely what has improved in RoboCup and what still requires further work. Plus, because the data muncher can work in real time, we can also release it as a proxy server for RoboCup. This proxy server gives all RoboCup developers instant access to statistics while a game is in progress and is a promising step toward an important goal: understanding RoboCup.

This work deals with designing simple behaviors to allow quadruped robots to play soccer. The robots are fully autonomous; they cannot exchange messages between each other. They are equipped with a charge-coupled-device camera that allows them to detect objects in the scene. In addition to vision problems such as changing lighting conditions and color confusion, legged robots must cope with "bouncing images" because of successive legs hitting the ground. When defining task-driven strategies, the designer has to take into account the influences of the locomotion and vision systems on the behavior. Locomotion and vision skills should be made as reliable as possible. Because it is not always possible to simulate the problems encountered in real situations, the behavior strategy should anticipate them. In this article, we describe all the behaviors used to play soccer games on a soccer field surrounded with landmarks. Experiments were carried out at the 1999 RoboCup in Stockholm using the Sony quadruped robots (Fujita 2000).