On learning guarantees to unsupervised concept drift detection on data streams. (1st March 2019)

• Record Type: Journal Article
• Authors: de Mello, Rodrigo F.; Vaz, Yule; Grossi, Carlos H.; Bifet, Albert
• Is Part Of: Expert systems with applications. Volume 117(2019)
• Page Start: 90
• Page End: 102
• Publication Date: 2019-03-01
• Subjects: Data streams -- Concept drift -- Algorithmic stability -- McDiarmid's inequality; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2018.08.054
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: We present an approach to detect concept drifts on data streams. Our approach provides theoretical learning guarantees. McDiarmid's inequality is employed to formalize model divergences. Abstract: Motivated by the Statistical Learning Theory (SLT), which provides a theoretical framework to ensure when supervised learning algorithms generalize input data, this manuscript relies on the Algorithmic Stability framework to prove learning bounds for the unsupervised concept drift detection on data streams. Based on such proof, we also designed the Plover algorithm to detect drifts using different measure functions, such as Statistical Moments and the Power Spectrum. In this way, the criterion for issuing data changes can also be adapted to better address the target task. From synthetic and real-world scenarios, we observed that each data stream may require a different measure function to identify concept drifts, according to the underlying characteristics of the corresponding application domain. In addition, we discussed about the differences of our approach against others from literature, and showed illustrative results confirming the usefulness of our proposal.