The structural inference problem is an offshoot of the basic problem of Reliability
Theory. We are presented with an n-component reliability system whose structure
function is completely unknown to us, except that we know it is monotonic. We are able
to test individual Boolean vectors and find out whether the system functions or fails. The
goal is to develop an efficient way to choose vectors for testing, so that we can learn
the entire structure function quickly. The many practical applications and areas of study
from which reliability systems occur, for example, game theory (Ramamurthy, 1990),
logical analysis (Kovalerchuk et al., 1996), or data mining (Torvik and Triantaphyllou,
2005), have kept focus on this problem.1
Previous investigation has focused on learning the structure incrementally (for
example, Triantaphyllou, 1996; and Sanchez et al., 2002). This approach gives an
estimate of the structure function, updating this estimate whenever a vector is tested,
and the results do not agree with the current estimate.
Torvik and Triantaphyllou (2002)—see also, Torvik and Triantaphyllou (2005)—focus
on learning a structure function while minimizing the number of vectors actually tested,
noting that the cost of testing a vector is often much higher than the cost of a slowly
running algorithm. They completely solve this problem in the case of small n. For larger
problems, they determine vectors to be tested by picking a vector x
from the set of
unknown vectors that minimizes the difference between the number of vectors that
would be learned if x
is functioning and the number of vectors that would be learned
if x
is not functioning. We emphasize here that since only the number of actually tested
vectors is important for them, they evaluate this difference for all of the vectors in the
unknown set on every iteration.
|
