Learning from data with uncertain labels by boosting credal classifiers

ABSTRACT

In this article, we investigate supervised learning when training data are associated with uncertain labels. We tackle this problem within the theory of belief functions. Each training pattern x_i is thus associated with a basic belief assignment, representing partial knowledge of its actual class. Here, we propose to use the approach known as boosting to solve the classification problem. We propose a variant of the AdaBoost algorithm where the outputs of the classifiers are interpreted as belief functions. During training, our algorithm estimates the reliability of each classifier to identify patterns from the various classes. During test phase, the outputs of the classifiers are first discounted according to these reliabilities, and then combined using a suitable rule. Experiments conducted on classical datasets show that our algorithm is comparable to AdaBoost in accuracy. Processing EEG data with imperfect labels clearly demonstrates the interest of taking into account the reliability of the labelling, and thus the relevance of our approach.

REFERENCES

• 1: Y. Bi, J. Guan, and D. Bell. The combination of multiple classifiers using an evidential reasoning approach. Artificial Intelligence, 172:1731--1751, 2008.
• 2: L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth, 1984.
• 3: E. Côme, L. Oukhellou, T. Denœux, and P. Aknin. Learning from partially supervised data using mixture models and belief functions. Pattern Recognition, 42:334--348, 2009.
• 4: T. Denœux. A k-nearest neighbor classification rule based on dempster-shafer theory. IEEE Transactions on System, Man and Cybernetics, 25:804--813, 1995.
• 5: T. Denœux. Conjunctive and disjunctive combination of belief functions induced by non-distinct bodies of evidence. Artificial Intelligence, 172:234--264, 2008.
• 6: T. Denœux and M. Skarstein-Bjanger. Induction of decision trees from partially classified data using belief functions. In Proceedings of SMC'2000, Nashville, TN, 2000.
• 7: T. Denœux and L. M. Zouhal. Handling possibilistic labels in pattern classification using evidential reasoning. Fuzzy Sets and Systems, 122:47--62, 2001.
• 8: T. Dietterich. Approximate statistical tests for comparing supervised classification algorithms. Neural Computation, 10:1895--1923, 1998.
• 9: D. Dubois and H. Prade. The principle of minimum specificity as a basis for evidential reasoning. Uncertainty in Knowledge-based Systems, pages 75--84, 1987.
• 10: D. Dubois, H. Prade, and P. Smets. A definition of subjective possibility. International Journal of Approximate Reasoning, 48:352--364, 2008.
• 11: J. François, Y. Grandvalet, T. Denoeux, and J.-M. Roger. Resample and combine: An approach to improving uncertainty representation in evidential pattern classification. Information Fusion, 4:75--85, 2003.
• 12: Y. Freund. Boosting a weak learning algorithm by majority. Information and Computation, 121(2):256--285, 1995.
• 13: Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119--139, 1997.
• 14: E. P. Klement, R. Mesiar, and E. Pap. Triangular norms. Kluwer Academic Publishers, Dordrecht, 2000.
• 15: D. Mercier, B. Quost, and T. Denœux. Refined modeling of sensor reliability in the belief function framework using contextual discounting. Information Fusion, 9:246--258, 2008.
• 16: R. Quinlan. C4.5: Programs for machine learning. Morgan Kaufman Publishers, 1993.
• 17: B. Quost, T. Denœux, and M.-H. Masson. Pairwise classifier combination using belief functions. Pattern Recognition Letters, 28:644--653, April 2007.
• 18: B. Quost, T. Denœux, and M.-H. Masson. Adapting a combination rule to non-independent information sources. In L. Magdalena, M. Ojeda-Aciego, and J. Verdegay, editors, Proceedings of the 12th IPMU Conference, pages 448--455, Málaga, Spain, 2008.
• 19: B. Quost, M.-H. Masson, and T. Denœux. Refined classifier combination using belief functions. In Proceedings of the 10th International Conference on Information Fusion, pages 776--782, Cologne, Germany, 2008.
• 20: M. Reformat and R. Yager. Building ensemble classifiers using belief functions and owa operators. Soft Computing, 12:543--558, 2008.
• 21: C. Richard. Une méthodologie pour la détection à structure imposée. Applications au plan temps-fréquence. PhD thesis, Université de Technologie de Compiègne, 1998.
• 22: R. Schapire, Y. Freund, P. Bartlett, and W. Lee. Boosting the margin: a new explanation for the effectiveness of voting methods. Annals of statistics, 26(5):1651--1686, 1998.
• 23: G. Shafer. A mathematical theory of evidence. Princeton University Press, Princeton, NJ, 1976.
• 24: P. Smets. Combining non-distinct evidences. In Proceedings of the International Conference of the North American Fuzzy Information Processing Society (NAFIPS '86), pages 544--549, New Orleans, USA, 1986.
• 25: P. Smets. The combination of evidence in the transferable belief model. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12:447--458, 1990.
• 26: P. Smets. Belief functions: the disjunctive rule of combination and the generalized bayesian theorem. International Journal of Approximate Reasoning, 9:1--35, 1993.
• 27: P. Smets. Data fusion in the transferable belief model. In Proceedings of the 3rd International Conference on Information Fusion, pages 21--33, Paris, France, 2000.
• 28: P. Smets and R. Kennes. The transferable belief model. Artificial Intelligence, 66:191--234, 1994.
• 29: P. Vannoorenberghe and T. Denœux. Handling uncertain labels in multiclass problems using belief decision trees. In Proceedings of the 5th IPMU Conference, pages 1919--1926, Annecy, France, 2002.
• 30: L. M. Zouhal and T. Denœux. An evidence-theoretic k-nn rule with parameter optimization. IEEE Transactions on System, Man and Cybernetics, 28:263--271, 1998.

INDEX TERMS

Keywords:
AdaBoost, Dempster-Shafer theory, classification, classifier combination, theory of belief functions, theory of evidence, uncertainty