On the Relationship Between Generalization Error, Hypothesis Complexity, and Sample Complexity for Radial Basis Functions

In this paper, we bound the generalization error of a class of Radial Basis Function networks, for certain well defined function learning tasks, in terms of the number of parameters and number of examples. We show that the total generalization error is partly due to the insufficient representational capacity of the network (because of its finite size) and partly due to insufficient information about the target function (because of finite number of samples). We make several observations about generalization error which are valid irrespective of the approximation scheme. Our result also sheds light on ways to choose an appropriate network architecture for a particular problem.

Computing Upper and Lower Bounds on Likelihoods in Intractable Networks

We present techniques for computing upper and lower bounds on the likelihoods of partial instantiations of variables in sigmoid and noisy-OR networks. The bounds determine confidence intervals for the desired likelihoods and become useful when the size of the network (or clique size) precludes exact computations. We illustrate the tightness of the obtained bounds by numerical experiments.

The Essential Dynamics Algorithm: Essential Results

This paper presents a novel algorithm for learning in a class of stochastic Markov decision processes (MDPs) with continuous state and action spaces that trades speed for accuracy. A transform of the stochastic MDP into a deterministic one is presented which captures the essence of the original dynamics, in a sense made precise. In this transformed MDP, the calculation of values is greatly simplified. The online algorithm estimates the model of the transformed MDP and simultaneously does policy search against it. Bounds on the error of this approximation are proven, and experimental results in a bicycle riding domain are presented. The algorithm learns near optimal policies in orders of magnitude fewer interactions with the stochastic MDP, using less domain knowledge. All code used in the experiments is available on the project's web site.

Robust 2-D Model-Based Object Recognition

Techniques, suitable for parallel implementation, for robust 2D model-based object recognition in the presence of sensor error are studied. Models and scene data are represented as local geometric features and robust hypothesis of feature matchings and transformations is considered. Bounds on the error in the image feature geometry are assumed constraining possible matchings and transformations. Transformation sampling is introduced as a simple, robust, polynomial-time, and highly parallel method of searching the space of transformations to hypothesize feature matchings. Key to the approach is that error in image feature measurement is explicitly accounted for. A Connection Machine implementation and experiments on real images are presented.

Error Detection and Recovery for Robot Motion Planning with Uncertainty

Robots must plan and execute tasks in the presence of uncertainty. Uncertainty arises from sensing errors, control errors, and uncertainty in the geometry of the environment. The last, which is called model error, has received little previous attention. We present a framework for computing motion strategies that are guaranteed to succeed in the presence of all three kinds of uncertainty. The motion strategies comprise sensor-based gross motions, compliant motions, and simple pushing motions.

The effect of the product cost factor on error handling in industrial robots

N.W. Hardy and M.H. Lee. The effect of the product cost factor on error handling in industrial robots. In Maria Gini, editor, Detecting and Resolving Errors in Manufacturing Systems. Papers from the 1994 AAAI Spring Symposium Series, pages 59-64, Menlo Park, CA, March 1994. The AAAI Press. Technical Report SS-94-04, ISBN 0-929280-60-1.

Research into error recovery for sensory robots

Lee, M., Barnes, D. P., Hardy, N. (1985). Research into error recovery for sensory robots. Sensor Review, 5 (4), 194-197.

Research into automatic error recovery

Lee, M., Hardy, N., & Barnes, D. P. (1984). Research into automatic error recovery. 65-69. Paper presented at 4th International Conference on Robot Vision and Sensory Controls, London, London, United Kingdom.

Error recovery in robot applications

Lee, M., Hardy, N., & Barnes, D. P. (1983). Error recovery in robot applications. 217-222. Paper presented at 6th British Robot Association Annual Conference, Birmingham, Birmingham, United Kingdom.

Knowledge based error recovery in industrial robots

M. H. Lee, D. P. Barnes, and N. W. Hardy. Knowledge based error recovery in industrial robots. In Proc. 8th. Int. Joint Conf. Artificial Intelligence, pages 824-826, Karlsruhe, FDR., 1983.

Automatic Error Recovery in Behaviour-Based Assistive Robots with Learning from Experience

Meng Q. and Lee M.H., Automatic Error Recovery in Behaviour-Based Assistive Robots with Learning from Experience, in Proc. INES 2001, 5th IEEE Int. Conf. on Intelligent Engineering Systems, Helsinki, Finland, Sept 2001, pp291-296.

A general model of error-prone PCR

Pritchard, L., Corne, D., Kell, D.B., Rowland, J. & Winson, M. (2005) A general model of error-prone PCR. Journal of Theoretical Biology 234, 497-509.

Error-driven active learning in growing radial basis function networks for early robot learning

Q. Meng and M.H. Lee, 'Error-driven active learning in growing radial basis function networks for early robot learning', 2006 IEEE International Conference on Robotics and Automation (IEEE ICRA 2006), 2984-90, Orlando, Florida, USA.

Quantum Lower Bounds for Fanout

We prove several new lower bounds for constant depth quantum circuits. The main result is that parity (and hence fanout) requires log depth circuits, when the circuits are composed of single qubit and arbitrary size Toffoli gates, and when they use only constantly many ancillae. Under this constraint, this bound is close to optimal. In the case of a non-constant number of ancillae, we give a tradeoff between the number of ancillae and the required depth.

A New Lower Bound Technique for Quantum Circuits without Ancillae

We present a technique to derive depth lower bounds for quantum circuits. The technique is based on the observation that in circuits without ancillae, only a few input states can set all the control qubits of a Toffoli gate to 1. This can be used to selectively remove large Toffoli gates from a quantum circuit while keeping the cumulative error low. We use the technique to give another proof that parity cannot be computed by constant depth quantum circuits without ancillæ.