Voir la notice de l'article provenant de la source Numdam
We combine a new data model, where the random classification is subjected to rather weak restrictions which in turn are based on the Mammen-Tsybakov [E. Mammen and A.B. Tsybakov, Ann. Statis. 27 (1999) 1808-1829; A.B. Tsybakov, Ann. Statis. 32 (2004) 135-166.] small margin conditions, and the statistical query (SQ) model due to Kearns [M.J. Kearns, J. ACM 45 (1998) 983-1006] to what we refer to as PAC + SQ model. We generalize the class conditional constant noise (CCCN) model introduced by Decatur [S.E. Decatur, in ICML '97: Proc. of the Fourteenth Int. Conf. on Machine Learn. Morgan Kaufmann Publishers Inc. San Francisco, CA, USA (1997) 83-91] to the noise model orthogonal to a set of query functions. We show that every polynomial time PAC + SQ learning algorithm can be efficiently simulated provided that the random noise rate is orthogonal to the query functions used by the algorithm given the target concept. Furthermore, we extend the constant-partition classification noise (CPCN) model due to Decatur [S.E. Decatur, in ICML '97: Proc. of the Fourteenth Int. Conf. on Machine Learn. Morgan Kaufmann Publishers Inc. San Francisco, CA, USA (1997) 83-91] to what we call the constant-partition piecewise orthogonal (CPPO) noise model. We show how statistical queries can be simulated in the CPPO scenario, given the partition is known to the learner. We show how to practically use PAC + SQ simulators in the noise model orthogonal to the query space by presenting two examples from bioinformatics and software engineering. This way, we demonstrate that our new noise model is realistic.
@article{ITA_2014__48_2_209_0,
author = {Brodag, Thomas and Herbold, Steffen and Waack, Stephan},
title = {A {Generalized} {Model} of {PAC} {Learning} and its {Applicability}},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {209--245},
publisher = {EDP-Sciences},
volume = {48},
number = {2},
year = {2014},
doi = {10.1051/ita/2014005},
mrnumber = {3302485},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2014005/}
}
TY - JOUR AU - Brodag, Thomas AU - Herbold, Steffen AU - Waack, Stephan TI - A Generalized Model of PAC Learning and its Applicability JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2014 SP - 209 EP - 245 VL - 48 IS - 2 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2014005/ DO - 10.1051/ita/2014005 LA - en ID - ITA_2014__48_2_209_0 ER -
%0 Journal Article %A Brodag, Thomas %A Herbold, Steffen %A Waack, Stephan %T A Generalized Model of PAC Learning and its Applicability %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2014 %P 209-245 %V 48 %N 2 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2014005/ %R 10.1051/ita/2014005 %G en %F ITA_2014__48_2_209_0
Brodag, Thomas; Herbold, Steffen; Waack, Stephan. A Generalized Model of PAC Learning and its Applicability. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 2, pp. 209-245. doi: 10.1051/ita/2014005
Cité par Sources :