<テクニカルレポート>
Analyzing the Average-Case Behavior of Conjunctive Learning Algorithms

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 We advocate to analyze the average complexity of learning problems. An appropriate framework for this purpose is introduced. Based on it we consider the problem of learning monomials and the special c...ase of learning monotone monomials in the limit and for on-line predictions in two variants: from positive data only, and from positive and negative examples. The well-known Wholist algorithm is completely analyzed with respect to its average-case behavior with respect to the class of binomial distributions. We consider different complexity measures: the number of mind changes, the number of prediction errors, and the total learning time. Tight hounds are obtained implying that worst case bounds are too pessimistic. On the average learning can be achieved exponentially faster. Furthermore, we study a new learning model, stochastic finite learning, in which, in contrast to PAC learning, some information about the underlying distribution is given and the goal is to find a correct (not only apprmimatively correct) hypothesis. We develop techniques to obtain good hounds for stochastic finite learning from a precise average case analysis of strategies for learning in the limit and illustrate our approach for the case of learning monomials.続きを見る

本文情報を非表示

trcs153.ps gz 195 KB 57  
trcs153 pdf 368 KB 51  

詳細

レコードID
査読有無
関連情報
タイプ
登録日 2009.04.22
更新日 2018.08.31