Inductive Inference Scheme at a Finite Stage of Process from a View Point of Source Coding

Toshiyasu MATSUSHIMA  Joe SUZUKI  Hiroshige INAZUMI  Shigeichi HIRASAWA  

IEICE TRANSACTIONS (1976-1990)   Vol.E73   No.5   pp.644-652
Publication Date: 1990/05/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: Special Section PAPER (Special Issue on Information Theory and Its Applications)

Full Text: PDF(816.7KB)
>>Buy this Article

In this paper, the criterion for evaluating inductive inference is considered from the information theoretical concept, especially from the view points of source coding and decision theory. Although the finite behavior of the inductive inference methods is important in the application field, there is no theoretical criterion for evaluating hypotheses at a finite stage of process. In the previous paper, we have defined an amount of semantic information included in well-formed formulas (wff) and denoted an analogy between inference and source coding. Inductive inference is regarded as source encoding, assuming that observed facts are compressed into a hypothesis similar to the way a source sequence is compressed into a codeword. By using the above definition, we can apply the criterion of source coding especially Minimum Description Length (MDL) to inductive inference. Therefore, the description length for representing a hypothesis is suitable for the criterion for evaluating a hypothesis inference at the finite stage of the inductive inference process. Moreover, by using the relation between the MDL criterion and Bayes risk, inductive inference can be interpreted with Bayes decision theory. The algorithm for the inductive inference of Horn clause is shown as an application of the proposed criterion. In the algorithm, the search space of hypotheses is restricted by using a refinement relation for increasing efficiency.