With the increasing volume of data, the best approach for learning from this data is to exploit an online learning algorithm. Online ensemble methods take advantage of an ensemble of classifiers to predict labels of data. Prediction with expert advice is a well-studied problem in the online ensemble learning literature. The weighted majority and the randomized weighted majority (RWM) algorithms are two well-known solutions to this problem, aiming to converge to the best expert. Since among some expert, the best one does not necessarily have the minimum error in all regions of data space, defining specific regions and converging to the best expert in each of these regions will lead to a better result. In this paper, we aim to resolve this problem by proposing a novel online ensemble algorithm to the problem of prediction with expert advice. We propose a cascading version of RWM to achieve not only better experimental results but also a better error bound for sufficiently large datasets.
SchafferC., Selecting a classification method by cross-validation, Machine Learning13(1) (1993), 135-143.
2.
BauerE. and KohaviR., An empirical comparison of voting classification algorithms: Bagging, boosting, and variants, Machine Learning36(1-2) (1999), 105-139.
GamaJ. and BrazdilP., Cascade generalization, Machine Learning41(3) (2000), 315-343.
5.
ChernovA., KalnishkanY., ZhdanovF. and VovkV.G., Supermartingales in prediction with expert advice, Theoretical Computer Science411(29) (2010), 2647-2669.
6.
Cesa-BianchiN., Prediction, Learning, and Games, Cambridge University Press, 2006.
7.
VovkV.G. and ZhdanovF., Prediction with expert advice for the brier game, The Journal of Machine Learning Research10 (2009), 2445-2471.
8.
VovkV.G., A game of prediction with expert advice, in: Proceedings of the Eighth Annual Conference on Computational Learning Theory, ACM (1995), 51-60.
9.
SaeedianM.F. and BeigyH., Learning to filter spam e-mails: An ensemble learning approach, International Journal of Hybrid Intelligent Systems9(1) (2012), 27-43.
10.
YangZ., NieX., XuW. and GuoJ., An approach to spam detection by naive bayes ensemble based on decision induction, in: The Sixth International Conference on Intelligent Systems Design and Applications (ISDA'06), IEEE 2 (2006), 861-866.
11.
NeumayerR., Clustering based ensemble classification for spam filtering, in: The 7th Workshop on Data Analysis (WDA 06), (2006), 11-22.
12.
MukkamalaS., SungA.H. and AbrahamA., Intrusion detection using an ensemble of intelligent paradigms, Journal of Network and Computer Applications28(2) (2005), 167-182.
13.
FanW. and StolfoS.J., Ensemble-based adaptive intrusion detection, in: The 2nd SIAM International Conference on Data Mining (SDM 2002), SIAM, (2002).
14.
ChebroluS., AbrahamA. and ThomasJ.P., Feature deduction and ensemble design of intrusion detection systems, Computers & Security24(4) (2005), 295-307.
TianM., ZhangW. and LiuF., On-line ensemble svm for robust object tracking, volume 4843 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2007, pp. 355-364.
17.
SadeghiS. and BeigyH., A new ensemble method for feature ranking in text mining, International Journal on Artificial Intelligence Tools22(3) (2013).
FreundY. and SchapireR.E., Experiments with a new boosting algorithm, in: ICML96 (1996), 148-156.
20.
QuinlanJ.R., Bagging, boosting, and C4.5, in: the Thirteenth National Conference on Artificial Intelligence (AAAI 1996), AAAI Press, (1996), 725-730.
21.
OzaN.C., Online bagging and boosting, in: IEEE International Conference on Systems, Man and Cybernetics, IEEE 3 (2005), 2340-2345.
22.
SobhaniP. and BeigyH., New drift detection method for data streams, in: Lecture Notes in Computer Science, Springer 6943 (2011), 88-97.
23.
AhmadiZ. and BeigyH., Semi-supervised ensemble learning of data streams in the presence of concept drift, in: Lecture Notes in Computer Science, Springer 7209 (2012), 526-537.
24.
HosseiniM., AhmadiZ. and BeigyH., New management operations on classifiers pool to track recurring concepts, in: Lecture Notes in Computer Science, Springer 7448 (2012), 327-339.
25.
HosseiniM.J., AhmadiZ. and BeigyH., Using a classifier pool in accuracy based tracking of recurring concepts in data stream classification, Evolving Systems4(1) (2013), 43-60.
26.
JacobsR.A., JordanM.I., NowlanS.J. and HintonG.E., Adaptive mixtures of local experts, Neural Computation3(1) (1991), 79-87.
27.
JordanM.I. and JacobsR.A., Hierarchical mixtures of experts and the em algorithm, Neural Computation6(2) (1994), 181-214.
28.
DeSantisA., MarkowskyG. and WegmanM.N., Learning probabilistic prediction functions, in: The 29th Annual Symposium on Foundations of Computer Science, 1988, IEEE (1988), 110-119.
29.
LittlestoneN. and WarmuthM.K., The weighted majority algorithm, Information and Computation108(2) (1994), 212-261.
30.
VovkV.G., Aggregating strategies, in: Third Workshop on Computational Learning Theory, Morgan Kaufmann (1990), 371-383.
31.
Cesa-BianchiN., MansourY. and StoltzG., Improved second-order bounds for prediction with expert advice, Machine Learning66(2-3) (2007), 321-352.
32.
BlumA., On-line algorithms in machine learning, in: Online Algorithms, FiatA. and WoegingerG., eds, volume 1442 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 1998, pp. 306-325.
33.
BacheK. and LichmanM., UCI machine learning repository, 2013.
34.
BifetA., HolmesG., KirkbyR. and PfahringerB., MOA: massive online analysis, Journal of Machine Learning Research11(5) (2010), 1601-1604.
35.
DietterichT., An experimental comparison of three methods for constructing ensembles of decision trees: Bagging, boosting, and randomization, Machine Learning40(1) (2000), 139-158.
