Computational Complexity of Hypothesis Assembly

Abstract

T h e p rob lem of f inding a best exp lana t ion of a set of da ta has been a top ic of m u c h interest in A r t i f i c i a l I n t e l l i gence. In th is paper we present an approach to th is p r o b l e m by hypothesis assembly. We present th is approach f o rma l l y so tha t we can examine the t ime comp lex i t y and correctness of the a lgo r i t hms . We then examine a system i m p l e m e n t e d using th is approach , w h i c h per fo rms red b lood a n t i b o d y iden t i f i ca t ion . We use th is d o m a i n to examine the r a m i f icat ions of the assumpt ions of the f o r m a l model in a real wo r l d s i t ua t i on . We also br ie f ly compare th is approach to other assembly approaches in te rms o f t i m e comp lex i t y and rel iance on assumpt ions. I . I n t r o d u c t i o n T h e p rob lem of abduc t i ve reasoning (as proposed by the phi losopher C.S. Peirce) has been a topic of m u c h recent interest in A r t i f i c i a l Inte l l igence ( M i l l e r 1982, Reggia 1983, Cha rn iak 1985). T h e general task faced by an abduc t i ve reasoning system is to find the best exp lana t ion of a set of da ta or observat ions, i.e., the best way to account for a set of da ta . Mos t of the work in A r t i f i c i a l Inte l l igence in th is area has focused on a specific k i nd of a b d u c t i o n , wh ich we cal l hypothes is assembly. T h e hypothesis assembly task assumes as g iven a set of hypotheses w i t h some knowledge about what sorts of da ta each can account for , and f inds the subset of these hypotheses tha t best accounts for the p rob lem da ta . A t the O h i o State Labo ra to ry for A r t i f i c i a l In te l l igence, Josephson et . a l . (1985) have been deve lop ing an approach for a b d u c t i o n based upon hypothesis assembly. In th is paper we w i l l begin by present ing a m a t h e m a t i cal idea l iza t ion of th is approach . F r o m th is we w i l l analyze the comp lex i t y and correctness o f the a l g o r i t h m . T h e n we w i l l examine how wel l th is idea l iza t ion matches w i t h real T h i s wo rk has been suppor ted by the N a t i o n a l L i b ra r y o f Med ic ine under g ran t LM-04298 , the N a t i o n a l Science F o u n d a t i o n t h r o u g h a Gradua te Fe l lowsh ip , and the Defense Advanced Research Pro jec ts Agency, R A D C cont rac t F30602-85-C-0010. C o m p u t e r faci l i t ies were enhanced t h r o u g h gi f ts f r o m Xe rox C o r p o r a t i o n . wor ld concepts o f abduc t i on . In pa r t i cu la r , we w i l l examine a system cal led R E D , based upon th is app roach , wh ich performs an t i body iden t i f i ca t i on in the d o m a i n o f red b lood cell t y p i n g , as descr ibed in (Josephson 1984), (Josephson 1985) and ( S m i t h 1985), and show how the general ma thema t i ca l results respond to quest ions t ha t have been raised ( M o s t o w 1985) about i ts comp lex i t y . I I . M a t h e m a t i c a l I d e a l i z a t i o n o f A b d u c t i o n D e f i n i t i o n s In order to mot i va te the fo l low ing de f in i t ions , we w i l l examine br ief ly the d o m a i n o f the cu r ren t i m p l e m e n t a t i o n o f R E D , the d o m a i n o f b l ood bank a n t i b o d y analysis. T h e p r i mary da ta consists of results of several lab tests on b l ood samples. T h e b lood bank technologist knows how antibodies can account for var ious react ions. T h e lab tests have the p roper ty t ha t i f a n t i b o d y A accounts for some react ion r, and an t i body B accounts for react ion q, then the presence of bo th ant ibod ies A and B accounts for b o t h react ions r and q. T h i s p rope r t y of a doma in w i l l be referred to as independence of hypotheses. More fo rma l l y , we define a d o m a i n for hypothes is assembly as a the t r i p l e (H, M,e) , where H is a finite set of hypotheses, M is a finite set of manifestations, and c is a map f r o m subsets of H to subsets of M. e(S) is i n te rpre ted as the explanatory power of a set of hypotheses, and is the set of mani fes ta t ions for wh i ch those hypo the ses can account . An assembly p rob lem is specif ied by a subset Mo M. Mo is i n te rp re ted as the set of observed mani fes ta t ions 1 . In these te rms, we have The Independence Assumption: If S and T are subsets of H, then A l t h o u g h m a n y domains satisfy the independence ass u m p t i o n , we w ish to s t rengthen ou r result by rep lac ing 1 In wha t fo l lows, we w i l l use the no ta t i on e(S) where we shou ld , s t r i c t l y speak ing , w r i t e for the res t r i c t i on of e(S) to the observed man i fes ta t ions .