ISSN:
1436-4646
Keywords:
Inductive inference
;
Boolean function synthesis
;
satisfiability
;
artificial intelligence
;
integer programming
;
interior point method
;
Riemannian geometry
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract In this paper we describe an interior point mathematical programming approach to inductive inference. We list several versions of this problem and study in detail the formulation based on hidden Boolean logic. We consider the problem of identifying a hidden Boolean functionℱ:{0, 1} n → {0, 1} using outputs obtained by applying a limited number of random inputs to the hidden function. Given this input—output sample, we give a method to synthesize a Boolean function that describes the sample. We pose the Boolean Function Synthesis Problem as a particular type of Satisfiability Problem. The Satisfiability Problem is translated into an integer programming feasibility problem, that is solved with an interior point algorithm for integer programming. A similar integer programming implementation has been used in a previous study to solve randomly generated instances of the Satisfiability Problem. In this paper we introduce a new variant of this algorithm, where the Riemannian metric used for defining the search region is dynamically modified. Computational results on 8-, 16- and 32-input, 1-output functions are presented. Our implementation successfully identified the majority of hidden functions in the experiment.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01581082
Permalink
