| 作成者 |
|
|
|
|
|
| 本文言語 |
|
| 出版者 |
|
|
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
|
|
| 関連URI |
|
|
|
| 関連情報 |
|
|
|
| 概要 |
An elementary formal system (EFS) is a logic program consisting of definite clauses whose arguments have patterns instead of first-order terms. We investigate EFSs for polynomial-time PAC-learnability... and show by experiments on protein data that PAC-learning is very useful for discovering knowledge. A definite clause of an EFS is hereditary if every pattern in the body is a subword of a pattern in the head. With this new notion, we show that H-EFS (m, k, t, r) is polynomial- time learnable, which is the class of languages definable by EFSs consisting of at most m hereditary definite clauses with predicate symbols of arity at most $ ganmma $, where k and t bound the number of variable occurrences in the head and the number of atoms in the body, respectively. The class defined by all finite unions of EFSs in H-EFS(m, k, t, r) is also polynomial-time learnable. We also show an interesting series of NC-learnable classes of EFSs. As hardness results, the class of regular pattern languages is shown not polynomial-time learnable unless RP=NP. Furthermore, the related problem of deciding whether there is a common subsequence which is consistent with given positive and negative examples is shown NP-complete. As a practical application of our learning algorithm, we made experiments on learning transmembrane domains in proteins from amino acid sequences. The experimental results were quite successful.続きを見る
|
Mendeley出力
rifis-tr-37