## ＜テクニカルレポート＞Lange and Wiehagen's Pattern Language Learning Algorithm: An Average-Case Analysis with respect to its Total Learning Time

作成者 作成者名 所属機関 所属機関名 Research Institute of Fundamental Information Science Kyushu University 英語 Research Institute of Fundamental Information Science, Kyushu University 九州大学理学部附属基礎情報学研究施設 1995-04 111 Accepted Manuscript open access RIFIS Technical Report || 111 http://www.i.kyushu-u.ac.jp/research/report.html RIFIS Technical Report || 111 http://www.i.kyushu-u.ac.jp/research/report.html RIFIS Technical Report || 111 http://www.i.kyushu-u.ac.jp/research/report.html The present paper deals with the best-case, worst-case and average-case behavior of Lange and Wiehagen's (1991) pattern language learning algorithm with respect to its total learning time. Pattern lan...guages have been introduced by Angluin (1980) and are defined as follows: Let \$A = { 0,1,..}\$ be any non-empty finite alphabet containing at least two elements. Furthermore, let \$X = { x_i mid i in IN}\$ be an infinite set of variables such that \$A cap X = phi\$. Patterns are non-empty strings from \$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. Lange and Wiehagen's (1991) algorithm learns the class of all pattern languages from text in the limit. We analyze this algorithm with respect to its total learning time behavior, i.e., the overall time taken by the algorithm until convergence. For every pattern \$pi\$ containing \$k\$ different variables it is shown that the total learning time is \$O(log _mid A mid (mid A mid + k) mid pi mid ^2)\$ in the best-case and unbounded in the worst-case. Furthermore, we estimate the expectation of the total learning time. In particular, it is shown that Lange and Wiehagen's algorithm possesses an expected total learning time of \$O(2^kk^2 mid A mid mid pi mid ^2 log _mid A mid (k mid A mid))\$ with respect to the uniform distribution.続きを見る

### 本文ファイル

111.ps tgz 128 KB 15
111.ps.tar pdf 305 KB 316

### 詳細

レコードID 3085 査読無 Annals of Mathematics and Artificial Intelligence || 23(1-2) || p117-145 テクニカルレポート 2009.04.22 2018.08.31