TY - JOUR
T1 - An algorithm for constructing and searching spaces of alternative hypotheses
AU - Griffin, Christopher
AU - Testa, Kelly
AU - Racunas, Stephen
N1 - Funding Information:
Manuscript received February 12, 2009; revised November 22, 2009 and July 10, 2010; accepted October 31, 2010. Date of publication December 10, 2010; date of current version May 18, 2011. This work supported in part by the Intelligence Advanced Research Projects Agency under Department of Energy Project 0000-T435-08, in part by the Office of Naval Research under Award N00014-08-1-0485, in part by the National Science Foundation under Stanford University Contract 22468020, and in part by the National Institutes of Health under University of Colorado Contract 0818393. This paper was recommended by Associate Editor S. Shimony.
PY - 2011/6
Y1 - 2011/6
N2 - In this paper, we develop techniques for automated hypothesis-space exploration over data sets that may contain contradictions. To do so, we make use of the equivalence between two formulations: those of first-order predicate logic with prefix modal quantifiers under the finite-model hypothesis and those of mixed-integer linear programming (MILP) problems. Unlike other approaches, we do not assume that all logical assertions are true without doubt. Instead, we look for alternative hypotheses about the validity of the claims by identifying alternative optimal solutions to a corresponding MILP. We use a collection of slack variables in the derived linear constraints to indicate the presence of contradictory data or assumptions. The objective is to minimize contradictions between data and assertions represented by the presence of nonzero slack in the set of linear constraints. In this paper, we present the following: 1) a correspondence between first-order predicate logic with modal quantifier prefixes under the finite-model hypothesis and MILP problems and 2) an implicit enumeration algorithm for exploring the contradiction hypothesis space.
AB - In this paper, we develop techniques for automated hypothesis-space exploration over data sets that may contain contradictions. To do so, we make use of the equivalence between two formulations: those of first-order predicate logic with prefix modal quantifiers under the finite-model hypothesis and those of mixed-integer linear programming (MILP) problems. Unlike other approaches, we do not assume that all logical assertions are true without doubt. Instead, we look for alternative hypotheses about the validity of the claims by identifying alternative optimal solutions to a corresponding MILP. We use a collection of slack variables in the derived linear constraints to indicate the presence of contradictory data or assumptions. The objective is to minimize contradictions between data and assertions represented by the presence of nonzero slack in the set of linear constraints. In this paper, we present the following: 1) a correspondence between first-order predicate logic with modal quantifier prefixes under the finite-model hypothesis and MILP problems and 2) an implicit enumeration algorithm for exploring the contradiction hypothesis space.
UR - http://www.scopus.com/inward/record.url?scp=79957471822&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79957471822&partnerID=8YFLogxK
U2 - 10.1109/TSMCB.2010.2092762
DO - 10.1109/TSMCB.2010.2092762
M3 - Article
C2 - 21147596
AN - SCOPUS:79957471822
SN - 1083-4419
VL - 41
SP - 772
EP - 782
JO - IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
JF - IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
IS - 3
M1 - 5659971
ER -