Contents of Report

[Data of Report]

Report Number:
TR0724
Date of Registration:
1992.01
English Title:
Algorithmic Learning Formal Languages and Decision Trees
Japanese Title:
***
English Author:
Y.Sakakibara
Japanese:
***
Name of Organization to which author belongs:
Fujitsu
PDF:
tr0724.pdf

[Contents]

Abstract.... 3
Acknowledegment.... 4
Contents.... 5
1Introduction.... 9
1.1Algorithmic Learning.... 9
1.2Learning Formal Languages from Queries.... 12
1.3Learning Decision Trees from Large Data in Noisy Environment.... 17
1.4Outline of Thesis.... 21
2Learning Context-Free Grammars from Possitive Strucutual Examples.... 25
2.1Identification in the Limit.... 25
2.2Learning from Structured Strings amd Related Works.... 26
2.3Basic Definication of Tree.... 28
2.4Tree Automaton and Context-Free Grammars.... 30
2.5Basic Idea of Learning.... 35
2.6Reversible Context-Free Grammars.... 37
2.7Learning Algorithms from Positive Presentations.... 43
2.8Examples Runs.... 56
3Learning Context-Free Grammars from Structural Queries.... 63
3.1Learning from Queries and Summary of Recent Results.... 63
3.2The Learning Algorithm using Queries.... 65
3.3An Examples Run.... 70
3.4Correctness and Time Complexity of CFGQ.... 73
3.5Application to Learning Logic Programs.... 77
4Learning Elementay Formal Systems from Queries.... 79
4.1Learning a Subclass Context-Sensitive Languages.... 79
4.2Smullyan's Elementary Formal Sysytems.... 80
4.3Extended Simple Formal Sysytems.... 81
4.4The Learning Algorith for ESFSs.... 89
5Probably Appoximately Correct Learning from Noisy Environment.... 103
5.1Probably Appoximately Correct Learning for Boolean Functions.... 103
5.2Classification Noise Process.... 105
5.3Previous Research Results.... 107
5.4Noise-tolerant Occam algorithm.... 108
6An Efficient Robust Algorithm for Learning Decision Lists.... 115
6.1Decision Lists.... 116
6.2Efficient Robust Learning of k-Dl.... 117
7An Efficient Robust Algorithm for Learning Decision Trees.... 123
7.1Decision Trees.... 124
7.2Efficient Robust Learning of Dicision Trees of rank r.... 125
8Conclusions.... 133
Bibliography.... 137
End.... 143

目次をクリックすると、PDFファイルが表示されます。

ICOT研究論文（TR）一覧に戻る / Back to the list of ICOT Technical Reports