A Probabilistic Algorithm for Calculating Structure: Borrowing from Simulated Annealing

From Tetherless World Wiki

Jump to: navigation, search

Citation: Russ B. Altman. (1993) A Probabilistic Algorithm for Calculating Structure: Borrowing from Simulated Annealing. In , 1993.

Publication techreport ( Edit )
type Technical Report
bibtype techreport
Bibtex basics
author Russ B. Altman
title A Probabilistic Algorithm for Calculating Structure: Borrowing from Simulated Annealing
number KSL-93-12
institution Knowledge Systems, AI Laboratory
address Washington D.C.
year 1993
Bibtex more
note June 1993.
Access Paper
abstract We have developed a general Bayesian algorithm for determining the coordinates of points in a three-dimensional space. The algorithm takes as input a set of probabilistic constraints on the coordinates of the points, and an a priori distribution for each point location. The output is a maximum likelihood estimate of the location of each point. We use the extended, iterated Kalman filter, and add a search heuristic for optimizing its solution under nonlinear conditions. This heuristic is based on the same principle as the simulated annealing heuristic for other optimization problems. Simply stated, we iteratively estimate the positions of the points using all available data; we allow the algorithm to leave local optima by resetting a variance-covariance matrix elements to high values. By increasing the variance of the elements, we allow unsatisfied (relatively low-variance) constraints to make large changes in the estimates of location, and thereby jump out of local optima. By iterating this process, we have been able to reliably identify sets of coordinates that satisfy the probabilistic constraints. Our method can use any probabilistic constraints that can be expressed as a general function of the point coordinates (e.g., distance, angles, dihedral angles, planarity etc...). It currently assumes that all constraints have gaussian noise. In this paper, we describe the algorithm and show its performance on a set of synthetic data to illustrate its convergence properties, and its applicability to domains such as molecular structure determination.

KSL Technical Report ID: KSL-93-12
Facts about A Probabilistic Algorithm for Calculating Structure: Borrowing from Simulated AnnealingRDF feed
Abstract We have developed a general Bayesian algor … We have developed a general Bayesian algorithm for determining the coordinates of points in a three-dimensional space. The algorithm takes as input a set of probabilistic constraints on the coordinates of the points, and an a priori distribution for each point location. The output is a maximum likelihood estimate of the location of each point. We use the extended, iterated Kalman filter, and add a search heuristic for optimizing its solution under nonlinear conditions. This heuristic is based on the same principle as the simulated annealing heuristic for other optimization problems. Simply stated, we iteratively estimate the positions of the points using all available data; we allow the algorithm to leave local optima by resetting a variance-covariance matrix elements to high values. By increasing the variance of the elements, we allow unsatisfied (relatively low-variance) constraints to make large changes in the estimates of location, and thereby jump out of local optima. By iterating this process, we have been able to reliably identify sets of coordinates that satisfy the probabilistic constraints. Our method can use any probabilistic constraints that can be expressed as a general function of the point coordinates (e.g., distance, angles, dihedral angles, planarity etc...). It currently assumes that all constraints have gaussian noise. In this paper, we describe the algorithm and show its performance on a set of synthetic data to illustrate its convergence properties, and its applicability to domains such as molecular structure determination. such as molecular structure determination.
Address Washington D.C.  +
Author Russ B. Altman  +
Bibtype techreport  +
Has author Russ B. Altman  +
Has identifier KSL-93-12  +
Has publishing details 1993  +
Has title A Probabilistic Algorithm for Calculating Structure: Borrowing from Simulated Annealing  +
Has year 1993  +
Institution Knowledge Systems, AI Laboratory  +
Ksl tr id KSL-93-12  +
Note June 1993.  +
Number KSL-93-12  +
Process note YES  +
Title A Probabilistic Algorithm for Calculating Structure: Borrowing from Simulated Annealing  +
Year 1993  +
Retrieved from "http://tw.rpi.edu/wiki/A_Probabilistic_Algorithm_for_Calculating_Structure:_Borrowing_from_Simulated_Annealing"
Personal tools