Browse Prior Art Database

Constrained Differential Optimization for Neural Networks

IP.com Disclosure Number: IPCOM000127960D
Original Publication Date: 1988-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 10 page(s) / 34K

Publishing Venue

Software Patent Institute

Related People

John C. Plat: AUTHOR [+4]

Abstract

Optimization is ubiquitous in the field of neural networks. Many learning algorithms, such as back-propagation [RUMELHART], optimize by minimizing the difference between expected solutions and observed solutions. Other neural algorithms use differential equations which minimize an energy to solve a specified computational problem, such as associative memory [HOPFIELD84], differential solution of the traveling salesman problem [DURBIN][HOPFiELD85], analog decoding [PLATT], and linear programming [TANK]. Furthermore, Lyapunov methods show that various models of neural behavior find minima of particular functions [COHEN][HOPFIELD84]. Solutions to a constrained optimization problem are restricted to a subset of the solutions of the corresponding unconstrained optimization problem. For example, a mutual inhibition circuit [ECCLES] requires one neuron to be "on" and the rest to be "off". Another example is the traveling salesman problem [SIN], where a salesman tries to minimize his travel distance, subject to the constraint that he must visit every city exactly once. A third example is the curve fitting problem, where elastic splines are as smooth as possible, while still going through data points [deBOOR]. Finally, when digital decisions are being made on analog data, the answer is constrained to be bits, either 0 or 1 [MEAD]. A constrained optimization problem can be stated as [Equation ommitted] where x_ is the state of the neural network, a position vector in a high-dimensional space; f (x) is a scalar energy, which can be imagined as the height of a landscape as a function of position x; g(x_) = o is a scalar equation describing a subspace of the state space. During constrained optimization, the state should be attracted to the subspace g(j) = o, then slide along the subspace until it reaches the locally smallest value of f (x) on g(x_) = 0. In section 2 of the paper, we describe classical methods of constrained optimization, such as the penalty method and Lagrange multipliers. Section 3 describes the basic differential multiplier method (BDMM) for constrained optimization, which calculates a good local minimum. If the constrained optimization problem is convex, then the local minimum is the global minimum; in general, finding the global minimum of non-convex problems is fairly difficult. In section 4, we describe a Lyapunov function for the BDMM. 1 In section 5, augmented Lagrangians, an idea from optimization theory, enhances the convergence properties of the BDMM. ` In section 6, we apply the differential algorithm to two neural problems, and discuss the insensitivity of BDMM to choice of parameters. Parameter sensitivity is a persistent problem in neural networks.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 13% of the total text.

Page 1 of 10

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Constrained Differential Optimization for Neural Networks

John C. Plat Alan H. Barr California Institute of Technology, Pasadena, CA 91125 T-R- 88-17 Abstract

Many optimization models of neural networks need constraints to restrict the space of outputs to a subspace which satisfies external criteria. Optimizations using energy methods yield "forces" which act upon the state of the neural network. The penalty method, in which quadratic energy constraints are added to an existing optimization energy, has become popular recently, but is not guaranteed to satisfy the constraint conditions when there are other forces on the neural model or when there are multiple constraints. In this paper, we present the basic differential multiplier method (BDMM), which satisfies constraints exactly; we create forces which gradually apply the constraints over time, using "neurons" that estimate Lagrange multipliers. The basic differential multiplier method is a system of differential equations first proposed by [ARROW] as an economic model. These differential equations locally converge to a constrained minimum. Examples of applications of the differential method of multipliers include enforcing permutation codewords in the analog decoding problem and enforcing valid tours in the traveling salesman problem.

1. Introduction

Optimization is ubiquitous in the field of neural networks. Many learning algorithms, such as back-propagation [RUMELHART], optimize by minimizing the difference between expected solutions and observed solutions. Other neural algorithms use differential equations which minimize an energy to solve a specified computational problem, such as associative memory [HOPFIELD84], differential solution of the traveling salesman problem [DURBIN][HOPFiELD85], analog decoding [PLATT], and linear programming [TANK]. Furthermore, Lyapunov methods show that various models of neural behavior find minima of particular functions [COHEN][HOPFIELD84]. Solutions to a constrained optimization problem are restricted to a subset of the solutions of the corresponding unconstrained optimization problem. For example, a mutual inhibition circuit [ECCLES] requires one neuron to be "on" and the rest to be "off". Another example is the traveling salesman problem [SIN], where a salesman tries to minimize his travel distance, subject to the constraint that he must visit every city exactly once. A third example is the curve fitting problem, where elastic splines are as smooth as possible, while still going through data points [deBOOR]. Finally, when digital decisions are being made on analog data, the answer is constrained to be bits, either 0 or 1 [MEAD]. A constrained optimization problem can be stated as

(Equation Omitted)

where x_ is the state of the neural network, a position vector in a high-dimensional space; f (x) is a scalar energy, which can be imagined as the height of a landscape as a functi...