Research on logic and computation in hypothesis finding
Yoshitaka Yamamoto · Institutional Repositories DataBase (IRDB) · 2010
The thesis studies the logical mechanism and its computational proce-dures in hypothesis finding. Given a background theory and an observationthat is not logically derived by the prior theory, we try to find a hypothesisthat explains the observation with respect to the background theory. Thehypothesis may contradict with a newly observed fact. That is why the logicin hypothesis finding is often regarded as ampliative inference. In first-order logic, the principle of inverse entailment (IE) has been ac-tively used to find hypotheses. Previously, many IE-based hypothesis findingsystems have been proposed, and several of them are now being applied topractical problems in life sciences concerned with the study of living or-ganisms, like biology. However, these state-of-the-art systems have somefundamental limitation on hypothesis finding: They make the search spacerestricted due to computational efficiency. For the sake of incompleteness inhypothesis finding, there is an inherent possibility that they may fail to findsuch sufficient hypotheses that are worth examining. The thesis first provides such a practical problem, where those incompleteprocedures cannot work well. In contrast, this motivating problem is solvedby CF-induction, which is an IE-based procedure that enables us to findevery hypothesis. On the other hand, complete procedures like CF-inductionhave to deal with a huge search space, and thus, are usually achieved byconsisting of many non-deterministic procedures. The thesis next shows an alternative approach for finding hypotheses,which is based on the inverse relation of subsumption, instead of entailment.The proposed approach is used to simplify the IE-based procedures by reduc-ing their non-determinisms without losing completeness in hypothesis finding.Together with this result, we logically reconstruct the current procedure ofCF-induction into a more simplified one, while it ensures the completeness.Through the thesis, we will see underlying nature and insights to overcomelimitations in the current lE-based hypothesis finding procedures.