3 - Exact and Perturbation Solutions for the Ensemble Dynamics

Summary

Abstract

This paper presents two approaches to characterize the dynamics of weight space probability density starting from a master equation. In the first, we provide a class of algorithms for which an exact evaluation of the integrals in the master equation is possible. This enables the time evolution of the density to be calculated at each time step without approximation. In the second, we expand earlier work on the small noise expansion to a complete perturbation framework. As an example application, we give a perturbative solution for the equilibrium density for the LMS algorithm. Finally, we use the perturbation framework to review annealed learning with schedules of the form μ(t) = μ₀/t^p.

Introduction

Several of the contributions to this volume apply order parameter techniques to describe the dynamics of on-line learning. In these approaches, the description assumes the form of a set of ordinary differential equations that describe the motion of macroscopic quantities, the order parameters, from which observables such as generalization error can be computed directly, without intermediate averaging. The (typically non-linear) differential equations are usually solved numerically to provide the dynamics throughout the training. Recently, this author and colleagues have obtained analytic results from the order parameter equations applied to the late time (asymptotic) convergence of annealed learning (Leen, Schottky and Saad, 1998). However, most of the application of these techniques has involved numerical integration. Indeed, the ability to track the ensemble dynamics at all times by solution of ordinary differential equations establishes an attractive analysis tool.