×

Aggregating algorithm for prediction of packs. (English) Zbl 1493.68288

Summary: This paper formulates a protocol for prediction of packs, which is a special case of on-line prediction under delayed feedback. Under the prediction of packs protocol, the learner must make a few predictions without seeing the respective outcomes and then the outcomes are revealed in one go. The paper develops the theory of prediction with expert advice for packs by generalising the concept of mixability. We propose a number of merging algorithms for prediction of packs with tight worst case loss upper bounds similar to those for Vovk’s Aggregating Algorithm. Unlike existing algorithms for delayed feedback settings, our algorithms do not depend on the order of outcomes in a pack. Empirical experiments on sports and house price datasets are carried out to study the performance of the new algorithms and compare them against an existing method.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68W27 Online algorithms; streaming algorithms
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adamskiy, D., Koolen, W. M., Chernov, A., & Vovk, V. (2016). A closer look at adaptive regret. The Journal of Machine Learning Research, 17(23), 1-21. · Zbl 1360.68663
[2] Bellotti, A. Reliable region predictions for automated valuation models: supplementary material for Ames housing data. Retrieved 20 December 2018, from http://wwwf.imperial.ac.uk/ abellott/publications.htm.
[3] Bellotti, A. (2017). Reliable region predictions for automated valuation models. Annals of Mathematics and Artificial Intelligence, 81, 71-74. · Zbl 1377.62195 · doi:10.1007/s10472-016-9534-6
[4] Cesa-Bianchi, N., & Lugosi, G. (2006). Prediction, learning, and games. Cambridge: Cambridge University Press. · Zbl 1114.91001 · doi:10.1017/CBO9780511546921
[5] De Cock, D. (2011). Ames, Iowa: Alternative to the Boston housing data as an end of semester regression project. Journal of Statistics Education, 19(3). https://doi.org/10.1080/10691898.2011.11889627.
[6] Joulani, P., Gyorgy, A., & Szepesvári, C.: Online learning under delayed feedback. In Proceedings of the 30th international conference on machine learning (ICML-13), (pp. 1453-1461).
[7] Kalnishkan, Y., Vovk, V., & Vyugin, M. V. (2004). Loss functions, complexities, and the Legendre transformation. Theoretical Computer Science, 313(2), 195-207. · Zbl 1069.68055 · doi:10.1016/j.tcs.2003.11.005
[8] Kalnishkan, Y., Adamskiy, D., Chernov, A., & Scarfe, T.: Specialist experts for prediction with side information. In 2015 IEEE international conference on data mining workshop (ICDMW), (pp. 1470-1477). IEEE, (2015).
[9] Littlestone, N., & Warmuth, M. K. (1994). The weighted majority algorithm. Information and Computation, 108, 212-261. · Zbl 0804.68121 · doi:10.1006/inco.1994.1009
[10] Loève, M. (1977). Probability theory I (4th ed.). New York: Springer. · Zbl 0359.60001 · doi:10.1007/978-1-4684-9464-8
[11] Quanrud, K., Khashabi, D. (2015). Online learning with adversarial delays. In Advances in neural information processing systems, (pp. 1270-1278).
[12] Vovk, V. (1990). Aggregating strategies. In Proceedings of the 3rd annual workshop on computational learning theory, (pp. 371-383), San Mateo, CA: Morgan Kaufmann.
[13] Vovk, V. (1998). A game of prediction with expert advice. Journal of Computer and System Sciences, 56, 153-173. · Zbl 0945.68528 · doi:10.1006/jcss.1997.1556
[14] Vovk, V. (2001). Competitive on-line statistics. International Statistical Review, 69(2), 213-248. · Zbl 1211.62200 · doi:10.1111/j.1751-5823.2001.tb00457.x
[15] Vovk, V., & Zhdanov, F. (2009). Prediction with expert advice for the Brier game. Journal of Machine Learning Research, 10, 2445-2471. · Zbl 1235.91027
[16] Weinberger, M. J., & Ordentlich, E. (2002). On delayed prediction of individual sequences. IEEE Transactions on Information Theory, 48(7), 1959-1976. · Zbl 1061.94518 · doi:10.1109/TIT.2002.1013136
[17] Zinkevich, M. (2003). Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (ICML-03), (pp. 928-936).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.