Recursive and Adjacency Algorithms for Ranking Hypotheses

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++.