Engineering topics

Cheeseman, Peter

Publications and source records attributed to Cheeseman, Peter.

At least 19 records

NASA NTRS2005

Generalized Maximum Entropy

A long standing mystery in using Maximum Entropy (MaxEnt) is how to deal with constraints whose values are uncertain. This situation arises when constraint values are estimated from data, because of finite sample sizes. One approach to this problem, advocated by E.T. Jaynes [1], is to ignore this uncertainty, and treat the empirically observed values as exact. We refer to this as the classic MaxEnt approach. Classic MaxEnt gives point probabilities (subject to the given constraints), rather than probability densities. We develop an alternative approach that assumes that the uncertain constraint values are represented by a probability density {e.g: a Gaussian), and this uncertainty yields a MaxEnt posterior probability density. That is, the classic MaxEnt point probabilities are regarded as a multidimensional function of the given constraint values, and uncertainty on these values is transmitted through the MaxEnt function to give uncertainty over the MaXEnt probabilities. We illustrate this approach by explicitly calculating the generalized MaxEnt density for a simple but common case, then show how this can be extended numerically to the general case. This paper expands the generalized MaxEnt concept introduced in a previous paper [3].

Cheeseman, Peter↗

NASA NTRS2004

On Bayesian Inductive Inference & Predictive Estimation

We investigate Bayesian inference and the Principle of Maximum Entropy (PME) as methods for doing inference under uncertainty. This investigation is primarily through concrete examples that have been previously investigated in the literature. We find that it is possible to do Bayesian inference and PME inference using the same information, despite claims to the contrary, but that the results are not directly comparable. This is because Bayesian inference yields a probability density function (pdf) over the unknown model parameters, whereas PME yields point estimates. If mean estimates are extracted from the Bayesian pdfs, the resulting parameter estimates can differ radically from the PME values and also from the Maximum Likelihood values. We conclude that these differences are due to the Bayesian inference not assuming anything beyond the given prior probabilities and the data, whereas PME implicitly assumes that the given constraints are the only constraints that are operating. Since this assumption can be wrong, PME values may have to be revised when subsequent data shows evidence for more constraints. The entropy concentration previously "proved" by E. T. Jaynes is shown to be in error. Further, we show that PME is a generalized form of independence assumption, and so can be a very powerful method of inference when the variables being investigated are largely independent of each other.

Cheeseman, Peter↗

NASA NTRS2001

The 3D Recognition, Generation, Fusion, Update and Refinement (RG4) Concept

This paper describes an active (real time) recognition strategy whereby information is inferred iteratively across several viewpoints in descent imagery. We will show how we use inverse theory within the context of parametric model generation, namely height and spectral reflection functions, to generate model assertions. Using this strategy in an active context implies that, from every viewpoint, the proposed system must refine its hypotheses taking into account the image and the effect of uncertainties as well. The proposed system employs probabilistic solutions to the problem of iteratively merging information (images) from several viewpoints. This involves feeding the posterior distribution from all previous images as a prior for the next view. Novel approaches will be developed to accelerate the inversion search using novel statistic implementations and reducing the model complexity using foveated vision. Foveated vision refers to imagery where the resolution varies across the image. In this paper, we allow the model to be foveated where the highest resolution region is called the foveation region. Typically, the images will have dynamic control of the location of the foveation region. For descent imagery in the Entry, Descent, and Landing (EDL) process, it is possible to have more than one foveation region. This research initiative is directed towards descent imagery in connection with NASA's EDL applications. Three-Dimensional Model Recognition, Generation, Fusion, Update, and Refinement (RGFUR or RG4) for height and the spectral reflection characteristics are in focus for various reasons, one of which is the prospect that their interpretation will provide for real time active vision for automated EDL.

Maluf, David A.↗

NASA NTRS1999

A Simulation to Study Speed Distributions in a Solar Plasma

We have carried out a numerical simulation of a plasma with characteristics similar to those found in the core of the Sun. Particular emphasis is placed on the Coulomb interaction between the ions and electrons, which could result in a relative velocity distribution different from the Maxwell-Boltzmann (MB) distribution generally assumed for a plasma. The fact that the distribution may not exactly follow the MB distribution could have very important consequences for a variety of problems in solar physics, especially the neutrino problem. Very briefly, the neutrino problem is that the observed neutrino detections from the Sun are smaller than what the standard solar theory predicts. In Section I we introduce the problem and in section II we discuss the approach to try to solve the problem: i.e., a molecular dynamics approach. In section III we provide details about the integration method, and any simplifications that can be applied to the problem. In section IV (the core of this report) we state our results. First for the specific case of 1000 particles and then for other cases with different number of particles. In section V we summarize our findings and state our conclusions. Sections VI VII and VIII provide the list of figures, reference material and acknowledgements respectively.

Cheeseman, Peter↗

NASA NTRS1999

A Simulation to Study Speed Distributions in a Solar Plasma

We (Peter Cheeseman of NASA Ames/Caelum Research) & Jose Luis Alvarellos of the SJSU Physics Department/SJSU Foundation.) have carried out a numerical simulation of a plasma with characteristics similar to those found in the core of the Sun. Particular emphasis is placed on the Coulomb interaction between the ions and electrons, which could result in a relative velocity distribution different from the Maxwell-Boltzmann (MB) distribution generally assumed for a plasma. The fact that the distribution may not exactly follow the MB distribution could have very important consequences for a variety of problems in solar physics, especially the neutrino problem. Very briefly. the neutrino problem is that the observed neutrino detections from the Sun are smaller than what the standard solar theory predicts. In Section 1 we introduce the problem and in section 2 we discuss the approach to try to solve the problem: i.e., a molecular dynamics approach. In section 3 we provide details about the integration method, and any simplifications that can be applied to the problem. In section 4 (the core of this report) we state our results, first for the specific case of 1000 particles and then for other cases with different number of particles. In section 5 we summarize our findings and state our conclusions. Sections 6 and 7 provide the list of figures, reference material and acknowledgments respectively.

Cheeseman, Peter↗

NASA NTRS1998

On-board Science Understanding: NASA Ames' Efforts

In the near future NASA intends to explore various regions of our solar system using robotic devices such as rovers, spacecraft, airplanes, and/or balloons. Such platforms will likely carry imaging devices, and a variety of analytical instruments intended to evaluate the chemical and mineralogical nature of the environment(s) that they encounter. Historically, mission operations have involved: (1) return of scientific data from the craft; (2) evaluation of the data by space scientists; (3) recommendations of the scientists regarding future mission activity; (4) commands for achieving these activities being transmitted to the craft; and (5) the activity being undertaken. This cycle is then repeated for the duration of the mission with command opportunities once or perhaps twice per day. In a rapidly changing environment, such as might be encountered by a rover traversing hundreds of meters a day or a spacecraft encountering an asteroid, this historical cycle is not amenable to rapid long range traverses, discovery of novelty, or rapid response to any unexpected situations. In addition to real-time response issues, the nature of imaging and/or spectroscopic devices are such that tremendous data volumes can be acquired, for example during a traverse. However, such data volumes can rapidly exceed on-board memory capabilities prior to the ability to transmit it to Earth. Additionally, the necessary communication band-widths are restrictive enough so that only a small portion of these data can actually be returned to Earth. Such scenarios clearly require the enabling of some crucial decisions to be made on-board by these robotic explorers. These decisions transcend the electromechanical control, health, and navigation issues associated with robotic operations. Instead they focus upon a long term goal of automating scientific discovery based upon data returned by sensors of the robot craft. Such an approach would eventually enable it to understand what is interesting because the data deviates from expectations generated by current theories/models of planetary processes that could have resulted in the observed data. Such interesting data and/or conclusions can then be selectively transmitted to Earth thus reducing memory and communications demands.

Roush, Ted L.↗

NASA NTRS1997

When Gravity Fails: Local Search Topology

Local search algorithms for combinatorial search problems frequently encounter a sequence of states in which it is impossible to improve the value of the objective function; moves through these regions, called {\em plateau moves), dominate the time spent in local search. We analyze and characterize {\em plateaus) for three different classes of randomly generated Boolean Satisfiability problems. We identify several interesting features of plateaus that impact the performance of local search algorithms. We show that local minima tend to be small but occasionally may be very large. We also show that local minima can be escaped without unsatisfying a large number of clauses, but that systematically searching for an escape route may be computationally expensive if the local minimum is large. We show that plateaus with exits, called benches, tend to be much larger than minima, and that some benches have very few exit states which local search can use to escape. We show that the solutions (i.e. global minima) of randomly generated problem instances form clusters, which behave similarly to local minima. We revisit several enhancements of local search algorithms and explain their performance in light of our results. Finally we discuss strategies for creating the next generation of local search algorithms.

Frank, Jeremy↗

NASA NTRS1994

An Improved Automatic Classification of a Landsat/TM Image from Kansas (FIFE)

This research note shows the results of applying a new massively parallel version of the automatic classification program (AutoClass IV) to a particular Landsat/TM image. The previous results for this image were produced using a "subsampling" technique because of the image size. The new massively parallel version of AutoClass allows the complete image to be classified without "subsampling", thus yielding improved results. The area in question is the FIFE study area in Kansas, and the classes AutoClass found show many interesting subtle variations in types of ground cover. Displays of the spatial distributions of these classes make up the bulk of this report. While the spatial distribution of some of these classes make their interpretation easy, most of the classes require detailed knowledge of the area for their full interpretation. We hope that some who receive this document can help us in understanding these classes. One of the motivations of this exercise was to test the new version of AutoClass (IV) that allows for correlation among the variables within a class. The scatter plots associated with the classes show that this correlation information is important in separating the classes. The fact that the spatial distribution of each of these classes is far from uniform, even though AutoClass was not given information about positions of pixels, shows that the classes are due to real differences in the image.

Kanefsky, Bob↗

NASA NTRS1994

Subpixel resolution from multiple images

Multiple images taken from similar locations and under similar lighting conditions contain similar, but not identical, information. Slight differences in instrument orientation and position produces mismatches between the projected pixel grids. These mismatches ensure that any point on the ground is sampled differently in each image. If all the images can be registered with respect to each other to a small fraction of a pixel accuracy, then the information from the multiple images can be combined to increase linear resolution by roughly the square root of the number of images. In addition, the gray-scale resolution of the composite image is also improved. We describe methods for multiple image registration and combination, and discuss some of the problems encountered in developing and extending them. We display test results with 8:1 resolution enhancement, and Viking Orbiter imagery with 2:1 and 4:1 enhancements.

Cheeseman, Peter↗

NASA NTRS1994

AutoClass: A Bayesian Approach to Classification

We describe a Bayesian approach to the untutored discovery of classes in a set of cases, sometimes called finite mixture separation or clustering. The main difference between clustering and our approach is that we search for the "best" set of class descriptions rather than grouping the cases themselves. We describe our classes in terms of a probability distribution or density function, and the locally maximal posterior probability valued function parameters. We rate our classifications with an approximate joint probability of the data and functional form, marginalizing over the parameters. Approximation is necessitated by the computational complexity of the joint probability. Thus, we marginalize w.r.t. local maxima in the parameter space. We discuss the rationale behind our approach to classification. We give the mathematical development for the basic mixture model and describe the approximations needed for computational tractability. We instantiate the basic model with the discrete Dirichlet distribution and multivariant Gaussian density likelihoods. Then we show some results for both constructed and actual data.

Stutz, John↗

NASA NTRS1992

Bayesian Classification Scheme

Scheme derived via statistical approach identifies classes in sets of data. Determines probable number of classes, probabilistic descriptions of classes, and probability that each object is member of each class. Scheme applicable to real-valued, discrete or continuous data presented in form of parameter vectors representing attributes of objects.

Stutz, John↗

NASA NTRS1991

Autoclass: An automatic classification system

The task of inferring a set of classes and class descriptions most likely to explain a given data set can be placed on a firm theoretical foundation using Bayesian statistics. Within this framework, and using various mathematical and algorithmic approximations, the AutoClass System searches for the most probable classifications, automatically choosing the number of classes and complexity of class descriptions. A simpler version of AutoClass has been applied to many large real data sets, has discovered new independently-verified phenomena, and has been released as a robust software package. Recent extensions allow attributes to be selectively correlated within particular classes, and allow classes to inherit, or share, model parameters through a class hierarchy. The mathematical foundations of AutoClass are summarized.

Stutz, John↗

NASA NTRS1991

Bayesian classification theory

The task of inferring a set of classes and class descriptions most likely to explain a given data set can be placed on a firm theoretical foundation using Bayesian statistics. Within this framework and using various mathematical and algorithmic approximations, the AutoClass system searches for the most probable classifications, automatically choosing the number of classes and complexity of class descriptions. A simpler version of AutoClass has been applied to many large real data sets, has discovered new independently-verified phenomena, and has been released as a robust software package. Recent extensions allow attributes to be selectively correlated within particular classes, and allow classes to inherit or share model parameters though a class hierarchy. We summarize the mathematical foundations of AutoClass.

Hanson, Robin↗

NASA NTRS1990

Evolutionary tree reconstruction

It is described how Minimum Description Length (MDL) can be applied to the problem of DNA and protein evolutionary tree reconstruction. If there is a set of mutations that transform a common ancestor into a set of the known sequences, and this description is shorter than the information to encode the known sequences directly, then strong evidence for an evolutionary relationship has been found. A heuristic algorithm is described that searches for the simplest tree (smallest MDL) that finds close to optimal trees on the test data. Various ways of extending the MDL theory to more complex evolutionary relationships are discussed.

Cheeseman, Peter↗

NASA NTRS1989

Automatic classification of spectra from the Infrared Astronomical Satellite (IRAS)

A new classification of Infrared spectra collected by the Infrared Astronomical Satellite (IRAS) is presented. The spectral classes were discovered automatically by a program called Auto Class 2. This program is a method for discovering (inducing) classes from a data base, utilizing a Bayesian probability approach. These classes can be used to give insight into the patterns that occur in the particular domain, in this case, infrared astronomical spectroscopy. The classified spectra are the entire Low Resolution Spectra (LRS) Atlas of 5,425 sources. There are seventy-seven classes in this classification and these in turn were meta-classified to produce nine meta-classes. The classification is presented as spectral plots, IRAS color-color plots, galactic distribution plots and class commentaries. Cross-reference tables, listing the sources by IRAS name and by Auto Class class, are also given. These classes show some of the well known classes, such as the black-body class, and silicate emission classes, but many other classes were unsuspected, while others show important subtle differences within the well known classes.

Cheeseman, Peter↗

NASA NTRS1988

In defense of An inquiry into computer understanding

Cheeseman responds to responses to his previous essay 'An inquiry into computer understanding'. It is concluded that probability (not logic) is the best way to represent and reason about common sense in constructing an AI system.

Cheeseman, Peter↗

NASA NTRS1988

An inquiry into computer understanding

The paper examines issues connected with the choice of the best method for representing and reasoning about common sense. McDermott (1978) has shown that a direct translation of common sense reasoning into logical form leads to insurmountable difficulties. It is shown, in the present work, that if Bayesian probability is used instead of logic as the language of such reasoning, none of the technical difficulties found in using logic arise. Bayesian inference is applied to a simple example of linguistic information to illustrate the potential of this type of inference for artificial intelligence.

Cheeseman, Peter↗

NASA NTRS1988

Planning and scheduling in AI

An account is given of the many related activities employing AI that are classifiable as 'automatic planning and scheduling'. A human can form plans and successfully execute them, but no current automatic-planning AI system can match this robustness and generality; it is in fact suggested that automatic planning is unlikely to be achieved by a general-purpose planning system. It is judged likely that partially-specialized planners will emerge for the efficient solution of specific classes of problems. Current planners are also found to make unrealistic informational demands, especially in the requirement that the 'state of the world' be known at all times, and that the only changes that occur are under the planner's control.

Cheeseman, Peter↗