A continuous approach to inductive
inference
Anil P. Kamath, Narendra K. Karmarkar,
K.G. Ramakrishnan, Mauricio G.C. Resende
Mathematical Programming, vol.
57, pp. 215-238, 1992
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 F: (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.
PostScript file of full paper
Go back
Mauricio G.C. Resende's Home Page
Last modified: 28 June 2002
Copyright Notice