## ＜テクニカルレポート＞Learning k-Variable Pattern Languages Efficiently Stochastically Finite on Average from Positive Data

作成者 作成者姓名 所属機関 所属機関名 Institut für Informatik Technische Universität München 作成者姓名 所属機関 所属機関名 Department of Informatics Kyushu University 英語 Department of Informatics, Kyushu University 九州大学大学院システム情報科学研究院情報理学部門 1998-01-17 145 accepted open access The present paper deals with the average-case analysis of the Lange-Wie- hagen (1991) algorithm learning the class of all pattern languages in the limit from positive data. Let $A$ = {0,1,cdots} be an...y non-empty finite alphabet containing at least two elements. Furthermore, let $X$ = {x_i mid　i　in $N$} be an infinite set of variables such that $A$　cap　$X$ = phi. Patterns are non-empty strings over $A$　cup　$X$. $L$(pi) , the language generated by pattern pi is the set of strings which can be obtained by substituting non-null strings from $A$ for the variables of the pattern pi. The Lange-Wiehagen (1991) algorithm is analyzed with respect to its total learning time, i.e., the overall time taken by the algorithm until convergence. The expectation of the total learning time is carefully analyzed and exponentially shrinking tail bounds for it are established for a large class of probability distributions. For every pattern pi containing k different variables it is shown that Lange and Wiehagen's algorithm possesses an expected total learning time of O($alpha$^k (log_$\frac{1}{$\beta $}(k) + 2)E[Lambda]), where$alpha $and$\beta $are two easy computable parameters arising naturally from the underlying probability distributions, and E[Lambda] is the expected example string length. In particular, for the uniform distribution the expected total learning time is O(2^k mid pi mid log_mid$A\$ (k)) which is a slight improvement over previously known results. Finally, we show how the improved analysis can be used to arrive at a new learning model. In this model, learning in the limit is transformed into finite learning with high confidence.続きを見る

### 本文情報を非表示

trcs145.ps gz 180 KB 36
trcs145 pdf 383 KB 30

### 詳細

レコードID 3013 査読無 DOI Technical Report || 145 http://www.i.kyushu-u.ac.jp/research/report.html テクニカルレポート 2009.04.22 2013.12.24