CF帰納法の理論的再構築について(「自動化:推論,発見,学習,データマイニング」及び一般) Towards a logical reconstruction of CF-Induction

本稿では,帰納論理プログラミングにおける逆伴意法による仮説発見手続きの一手法であるCF帰納法の一般化手続きについて考察する.CF帰納法は一般節理論の仮説発見に対して健全かつ完全な手続きであり,その理論面での優位性から現在システム生物学等の実問題への応用が期待されている.一方,構成手続き中の一般化手続きについては,いくつかの適用可能な技法が紹介されているだけであり,どの技法をどのように用いるかはユーザが適宜選択する必要があるため,アルゴリズムとしては非決定性がかなり大きく組織的に構成されているとは言い難い.そこで本論文では,これまでの手法を体系的に整備し,健全かつ完全な一般化手続きを提案する.

CF-Induction is a sound and complete hypothesis finding procedure for full clausal logic. Given a background theory and examples, it uses the principle of Inverse Entailment to deductively compute an intermediate bridge formula which is then inductively generalised in order to return a hypothesis. The procedure makes use of several generalisation operators, such as least generalisation and inverse resolution, each of which can be applied in many possible ways. In this paper we propose an alternative generalisation approach for CF-Induction whereby the hypothesis is derived using a single deductive operator followed by anti-instantiat ion. We show that our simplified procedure retains its soundness and completeness.