Boosting grammatical inference with confidence oracles

ABSTRACT

In this paper we focus on the adaptation of boosting to grammatical inference. We aim at improving the performance of state merging algorithms in the presence of noisy data by using, in the update rule, additional information provided by an oracle. This strategy requires the construction of a new weighting scheme that takes into account the confidence in the labels of the examples. We prove that our new framework preserves the theoretical properties of boosting. Using the state merging algorithm RPNI*, we describe an experimental study on various datasets, showing a dramatic improvement of performances.

REFERENCES

• 1: Avrim Blum , Tom Mitchell, Combining labeled and unlabeled data with co-training, Proceedings of the eleventh annual conference on Computational learning theory, p.92-100, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279962]
• 2: Cover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE Trans. on Information Theory, 13, 21--27.
• 3: de la Higuera, C. (2004). A bibliographic survey on grammatical inference. Pattern Recognition. To appear.
• 4: Carlos Domingo , Osamu Watanabe, MadaBoost: A Modification of AdaBoost, Proceedings of the Thirteenth Annual Conference on Computational Learning Theory, p.180-189, June 28-July 01, 2000
• 5: Yoav Freund, An Adaptive Version of the Boost by Majority Algorithm, Machine Learning, v.43 n.3, p.293-318, June 2001 [doi>10.1023/A:1010852229904]
• 6: Freund, Y., & Schapire, R. E. (1996). Experiments with a new boosting algorithms. Thirteenth Int. Conf. on Machine Learning (pp. 148--156).
• 7: Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, v.55 n.1, p.119-139, Aug. 1997 [doi>10.1006/jcss.1997.1504]
• 8: Friedman, J., Hastie, T., & Tibshirani, R. (1998). Additive logistic regression: a statistical view of boosting (Technical Report).
• 9: Michael J. Kearns , Umesh V. Vazirani, An introduction to computational learning theory, MIT Press, Cambridge, MA, 1994
• 10: Jyrki Kivinen , Manfred K. Warmuth, Boosting as entropy projection, Proceedings of the twelfth annual conference on Computational learning theory, p.134-144, July 07-09, 1999, Santa Cruz, California, United States [doi>10.1145/307400.307424]
• 11: Kevin J. Lang , Barak A. Pearlmutter , Rodney A. Price, Results of the Abbadingo One DFA Learning Competition and a New Evidence-Driven State Merging Algorithm, Proceedings of the 4th International Colloquium on Grammatical Inference, p.1-12, July 12-14, 1998
• 12: Oncina, J., & Garcíía, P. (1992). Inferring regular languages in polynomial update time, vol. 1 of Machine Perception and Artificial Intelligence, 49--61. World Scientific.
• 13: Robert E. Schapire , Yoram Singer, Improved Boosting Algorithms Using Confidence-rated Predictions, Machine Learning, v.37 n.3, p.297-336, Dec. 1999 [doi>10.1023/A:1007614523901]
• 14: Sebban, M., & Janodet, J. (2003). On state merging in grammatical: a statistical approach for dealing with noisy data. Twentieth Int. Conf. on Machine Learning (pp. 688--695).