A library of computer programs has been developed to solve the problem of parametric ranking of a set of hypotheses on the basis of incomplete and/or uncertain information. In general, the ranking must be learned by use of training examples in which one observes the values of random variables that depend on the hypotheses and adjusts the parameters accordingly. In addition, it is necessary to balance a potential increase in confidence in the ranking against the cost of additional examples. In these programs, the balance is struck by use of a combination of the "probably approximately correct" criterion from the theory of computational learning and the "expected loss" criterion from decision theory and gaming problems. The library offers the option to use a ranking algorithm that performs a recursive selection among the remaining unranked hypotheses, and/or one that performs only pairwise comparisons between adjacent hypotheses. These programs are written in ANSI C++.
This program was written by Steve A. Chien, Andre Stechert, and Darren Mutz of Caltech for NASA's Jet Propulsion Laboratory. NPO-20170
This Brief includes a Technical Support Package (TSP).
Recursive and adjacency algorithms for ranking hypotheses
(reference NPO20170) is currently available for download from the TSP library.
Don't have an account?
Overview
The document presents research conducted by the Jet Propulsion Laboratory (JPL) on algorithms for ranking hypotheses based on incomplete information, particularly in contexts where the cost of acquiring additional data is significant. The focus is on the hypothesis ranking problem, which generalizes the hypothesis selection problem. In hypothesis selection, an algorithm identifies the single best hypothesis, while in ranking, it orders multiple hypotheses based on expected utility derived from limited observations.
The paper introduces two algorithms designed to address the hypothesis ranking problem: a recursive hypothesis selection algorithm and an adjacency-based algorithm. These algorithms are evaluated against two decision criteria: probably approximately correct (PAC) and expected loss (EL). The PAC criterion provides a framework for determining how much information is necessary to make reliable decisions, while the EL criterion focuses on minimizing the expected loss associated with decisions made under uncertainty.
The authors emphasize the importance of efficiently utilizing available data, especially in scenarios where training data is scarce. They argue that learning systems must balance the expected utility of additional information against the costs of acquiring that information. This balance is crucial in applications such as medical treatment evaluation and spacecraft design optimization, where the implications of decisions can be significant.
Empirical tests are included to demonstrate the effectiveness of the proposed algorithms, showing improved performance over standard algorithms from the statistical ranking literature. The results indicate that the new algorithms can effectively rank hypotheses even with limited data, making them valuable tools in various machine learning applications.
The document also discusses related work and potential future extensions of the algorithms, highlighting the ongoing need for advancements in statistical machine learning techniques. Overall, the research contributes to the field by providing robust methods for hypothesis ranking that can enhance decision-making processes in data-poor environments.
In summary, this document outlines a significant advancement in the field of machine learning, focusing on the development and evaluation of algorithms that improve the ranking of hypotheses under constraints of limited information and high data acquisition costs.
