氏名: ガイベ アハマド アンマール (289934095)

論文題目: A Generalization of Majority Vote Boosting Algorithm in the Agnostic Learning Model


論文概要

In this research we have studied and developed a Boosting algorithm that can work in the agnostic learning model. The agnostic learning model is a generalization of the basic PAC-learning model. It aims to overcome the shortcomings of the PAC-learning model such as the strong assumption of the target concept. We can model the learning process as consisting of two phases, a training phase and a performance process. In the training phase the learner is presented with labeled instances (called examples), drawn from the input space according to an arbitrary but fixed distribution. Based on these examples the learner must devise a hypothesis of the learned phenomenon (usually called the target concept). In the performance phase the hypothesis is used to classify instances from the input space, and the accuracy of the hypothesis is evaluated. Under this scenario Boosting algorithms aim to improve the accuracy of weak learning algorithms. A weak learning algorithm is an efficient algorithm whose hypothesis is only slightly better than a random guessing. By slightly better than random guessing we mean a hypothesis that correctly classify an instance with probability just exceeding 1/2 by a small value \gamma (0 < \gamma < 1/2). As normal Boosting algorithms our algorithm works by running the weak algorithm several times, each time on a different distribution of instances, to generate several different hypotheses. Each of these hypotheses has an accuracy very closed to the random guess. We will call these hypotheses weak hypotheses. These weak hypotheses are combined by the boosting algorithm into a single more complex and more accurate hypothesis. The different distributions are generated using “filtering” process by which part of the random examples that are presented to the boosting algorithm are discarded, and only a subset of the examples are passed to the weak learning algorithms. The aim of this process is to force the learner to concentrate on the difficult to learn examples.


目次に戻る


提出時刻:2001/02/06 16:40:51