最弱仮説の入出力モード解析に基づく論理プログラムの効率的帰納

DOI Web Site Web Site 参考文献24件

書誌事項

タイトル別名
  • Efficient Induction of Logic Programs based on the Mode Analysis of Most Specific Hypothesis
  • サイ ジャク カセツ ノ ニュウシュツリョク モード カイセキ ニ モトヅク ロンリ プログラム ノ コウリツテキ キノウ

この論文をさがす

抄録

Inductive Logic Programming(ILP) has been drawn a big attention as a new research area of inductive inference based on first order logic. The main advantages of ILP are the very rich expressive power and the capability of utilizing arbitrary background knowledge represented in Prolog programs. However ILP usually needs enormous computational time to obtain the hypotheses. To cope with this problem, an efficient algorithm is needed. In this paper, an ILP system Progol is adopted as the target system. Progol is one of the most successful ILP systems, which induces hypotheses by first constructing the most specific hypothesis(MSH) for a given example, and then searching through the subsumption lattice having empty clause and MSH as its top and bottom respectively. The second phase of Progol employes an A*-like search algorithm which is a kind of exhaustive search base on A* search strategy. In this paper, we show redundancy in A*-like algorithm from a viewpoint of imput/output relations amoung variables in the literals forming the MSH, and then propose a new search algorithm to remove the redundancy. The main advantage of the proposed algorithm is a substantial reduction of search space. By preprocessing the given search space, the redundant parts in the space can be removed. Since the search in the search space in which there is no answer can be avoided in this way, we have succeeded in reducing the number of candidate hypotheses to be generated as well as the whole computational time to induction.

収録刊行物

参考文献 (24)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ