Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Neural Computing and Applications
Erschienen in: Neural Computing and Applications 15/2021

26.02.2021 | Original Article

DCA for online prediction with expert advice

verfasst von: Hoai An Le Thi, Vinh Thanh Ho

Erschienen in: Neural Computing and Applications | Ausgabe 15/2021

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We investigate DC (Difference of Convex functions) programming and DCA (DC Algorithm) for a class of online learning techniques, namely prediction with expert advice, where the learner’s prediction is made based on the weighted average of experts’ predictions. The problem of predicting the experts’ weights is formulated as a DC program for which an online version of DCA is investigated. The two so-called approximate/complete variants of online DCA based schemes are designed, and their regrets are proved to be logarithmic/sublinear. The four proposed algorithms for online prediction with expert advice are furthermore applied to online binary classification. Experimental results tested on various benchmark datasets showed their performance and their superiority over three standard online prediction with expert advice algorithms—the well-known weighted majority algorithm and two online convex optimization algorithms.
Vorheriger Artikel An adaptive regeneration framework based on search space adjustment for differential evolution
Nächster Artikel Neural adaptive appointed-time control for flexible air-breathing hypersonic vehicles: an event-triggered case

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
Literatur
1.
Alexander L, Das SR, Ives Z, Jagadish H, Monteleoni C (2017) Research challenges in financial data modeling and analysis. Big Data 5(3):177–188CrossRef
2.
3.
Azoury K, Warmuth MK (2001) Relative loss bounds for on-line density estimation with the exponential family of distributions. Mach Learn 43(3):211–246MATHCrossRef
4.
Barzdin JM, Freivald RV (1972) On the prediction of general recursive functions. Sov Math Doklady 13:1224–1228MATH
5.
6.
Cesa-Bianchi N, Freund Y, Haussler D, Helmbold DP, Schapire RE, Warmuth MK (1997) How to use expert advice. J ACM 44(3):427–485MathSciNetMATHCrossRef
7.
Cesa-Bianchi N, Lugosi G (2003) Potential-based algorithms in on-line prediction and game theory. Mach Learn 51(3):239–261MATHCrossRef
8.
Cesa-Bianchi N, Lugosi G (2006) Prediction, learning, and games. Cambridge University Press, New YorkMATHCrossRef
9.
Cesa-Bianchi N, Mansour Y, Stoltz G (2007) Improved second-order bounds for prediction with expert advice. Mach Learn 66(2):321–352MATHCrossRef
10.
Chung TH (1994) Approximate methods for sequential decision making using expert advice. In: Proceedings of the seventh annual conference on computational learning theory, COLT ’94, pp 183–189. ACM, New York, NY, USA
11.
Collobert R, Sinz F, Weston J, Bottou L (2006) Large scale transductive SVMs. J Mach Learn Res 7:1687–1712MathSciNetMATH
12.
Collobert R, Sinz F, Weston J, Bottou L (2006) Trading convexity for scalability. In: Proceedings of the 23rd international conference on machine learning, ICML ’06, pp 201–208. New York, NY, USA
13.
Conover WJ (1999) Pratical nonparametric statistics, 3rd edn. Wiley, Hoboken
14.
Crammer K, Dekel O, Keshet J, Shalev-Shwartz S, Singer Y (2006) Online passive-aggressive algorithms. J Mach Learn Res 7:551–585MathSciNetMATH
15.
Dadkhahi H, Shanmugam K, Rios J, Das P, Hoffman SC, Loeffler TD, Sankaranarayanan S (2020) Combinatorial black-box optimization with expert advice. In: Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery and data mining, pp 1918–1927. Association for Computing Machinery, New York, NY, USA
16.
Demšar J (2006) Statistical comparisons of classifiers over multiple data sets. J Mach Learn Res 7:1–30MathSciNetMATH
17.
DeSantis A, Markowsky G, Wegman MN (1988) Learning probabilistic prediction functions. In: Proceedings of the first annual workshop on computational learning theory, COLT’88, pp. 312–328. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA
18.
Devaine M, Gaillard P, Goude Y, Stoltz G (2013) Forecasting electricity consumption by aggregating specialized experts. Mach Learn 90(2):231–260MathSciNetMATHCrossRef
19.
Freund Y, Schapire RE (1997) A decision-theoretic generalization of on-line learning and an application to boosting. J Comput Syst Sci 55(1):119–139MathSciNetMATHCrossRef
20.
Friedman M (1937) The use of ranks to avoid the assumption of normality implicit in the analysis of variance. J Am Stat Assoc 32(200):675–701MATHCrossRef
21.
Friedman M (1940) A comparison of alternative tests of significance for the problem of \(m\) rankings. Ann Math Stat 11(1):86–92MathSciNetMATHCrossRef
22.
García S, Herrera F (2009) An extension on “statistical comparisons of classifiers over multiple data sets” for all pairwise comparisons. J Mach Learn Res 9:2677–2694MATH
23.
Gentile C (2002) A new approximate maximal margin classification algorithm. J Mach Learn Res 2:213–242MathSciNetMATH
24.
Gentile C (2003) The robustness of the \(p\)-norm algorithms. Mach Learn 53(3):265–299MATHCrossRef
25.
Gollapudi S, Panigrahi D (2019) Online algorithms for rent-or-buy with expert advice. In: Chaudhuri K, Salakhutdinov R (eds) Proceedings of the 36th International Conference on Machine Learning, vol. 97, pp 2319–2327. PMLR, Long Beach, California, USA
26.
Gramacy RB, Warmuth MKK, Brandt SA, Ari I (2003) Adaptive caching by refetching. In: Becker S, Thrun S, Obermayer K (eds) Advances in neural information processing systems, vol 15. MIT Press, Cambridge, pp 1489–1496
27.
Grove AJ, Littlestone N, Schuurmans D (2001) General convergence results for linear discriminant updates. Mach Learn 43(3):173–210MATHCrossRef
28.
Hao S, Hu P, Zhao P, Hoi SCH, Miao C (2018) Online active learning with expert advice. ACM Trans Knowl Discov Data 12(5):1–22CrossRef
29.
Haussler D, Kivinen J, Warmuth MK (1995) Tight worst-case loss bounds for predicting with expert advice. In: Vitányi P (ed) Computational learning theory, lecture notes in computer Science, vol 904. Springer, Berlin, pp 69–83
30.
Hazan E (2016) Introduction to online convex optimization. Found Trends Optim 2(3–4):157–325CrossRef
31.
Ho VT, Le Thi HA, Bui DC (2016) Online DC optimization for online binary linear classification. In: Nguyen TN, Trawiński B, Fujita H, Hong TP (eds) Intelligent information and database systems: 8th Asian conference, ACIIDS 2016, proceedings, Part II. Springer, Berlin, pp 661–670
32.
Hoi SCH, Wang J, Zhao P (2014) LIBOL: a library for online learning algorithms. J Mach Learn Res 15(1):495–499MATH
33.
Jamil W, Bouchachia A (2019) Model selection in online learning for times series forecasting. In: Lotfi A, Bouchachia H, Gegov A, Langensiepen C, McGinnity M (eds) Advances in computational intelligence systems. Springer, Cham, pp 83–95CrossRef
34.
35.
Kivinen J, Warmuth MK (2001) Relative loss bounds for multidimensional regression problems. Mach Learn 45(3):301–329MATHCrossRef
36.
Kveton B, Yu JY, Theocharous G, Mannor S (2008) Online learning with expert advice and finite-horizon constraints. In: Proceedings of the twenty-third AAAI conference on artificial intelligence, AAAI 2008, pp 331–336. AAAI Press
37.
Le Thi HA (1994) Analyse numérique des algorithmes de l’optimisation d. C. Approches locale et globale. Codes et simulations numériques en grande dimension. Applications. Ph.D. thesis, University of Rouen, France
38.
Le Thi HA (2020) DC programming and DCA for supply chain and production management: state-of-the-art models and methods. Int J Prod Res 58(20):6078–6114CrossRef
39.
Le Thi HA, Ho VT, Pham Dinh T (2019) A unified DC programming framework and efficient DCA based approaches for large scale batch reinforcement learning. J Glob Optim 73(2):279–310MathSciNetMATHCrossRef
40.
Le Thi HA, Le HM, Phan DN, Tran B (2020) Stochastic DCA for minimizing a large sum of DC functions with application to multi-class logistic regression. Neural Netw 132:220–231CrossRef
41.
Le Thi HA, Moeini M, Pham Dinh T (2009) Portfolio selection under downside risk measures and cardinality constraints based on DC programming and DCA. Comput Manag Sci 6(4):459–475MathSciNetMATHCrossRef
42.
Le Thi HA, Pham Dinh T (2001) DC programming approach to the multidimensional scaling problem. In: Migdalas A, Pardalos PM, Värbrand P (eds) From local to global optimization. Springer, Boston, pp 231–276MATH
43.
Le Thi HA, Pham Dinh T (2003) Large-scale molecular optimization from distance matrices by a D.C. optimization approach. SIAM J Optim 14(1):77–114MathSciNetMATHCrossRef
44.
Le Thi HA, Pham Dinh T (2005) The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann Oper Res 133(1–4):23–48MathSciNetMATH
45.
Le Thi HA, Pham Dinh T (2014) DC programming in communication systems: challenging problems and methods. Vietnam J Comput Sci 1(1):15–28CrossRef
46.
Le Thi HA, Pham Dinh T (2018) DC programming and DCA: thirty years of developments. Math Program Spec Issue DC Program Theory Algorithms Appl 169(1):5–68MathSciNetMATH
47.
Li Y, Long P (2002) The relaxed online maximum margin algorithm. Mach Learn 46(1–3):361–387MATHCrossRef
48.
49.
Nayman N, Noy A, Ridnik T, Friedman I, Jin R, Zelnik-Manor L (2019) XNAS: neural architecture search with expert advice. In: Advances in neural information processing systems 32: annual conference on neural information processing systems 2019, NeurIPS 2019, pp 1975–1985
50.
Novikoff AB (1963) On convergence proofs for perceptrons. In: Proceedings of the symposium on the mathematical theory of automata 12:615–622
51.
Ong CS, Le Thi HA (2013) Learning sparse classifiers with difference of convex functions algorithms. Optim Methods Softw 28(4):830–854MathSciNetMATHCrossRef
52.
Pereira DG, Afonso A, Medeiros FM (2014) Overview of Friedman’s test and post-hoc analysis. Commun Stat Simul Comput 44(10):2636–2653MathSciNetCrossRef
53.
Pham Dinh T, Le HM, Le Thi HA, Lauer F (2014) A difference of convex functions algorithm for switched linear regression. IEEE Trans Autom Control 59(8):2277–2282MathSciNetMATHCrossRef
54.
Pham Dinh T, Le Thi HA (1997) Convex analysis approach to D.C. programming: theory, algorithm and applications. Acta Math Vietnam 22(1):289–355MathSciNetMATH
55.
Pham Dinh T, Le Thi HA (1998) DC optimization algorithms for solving the trust region subproblem. SIAM J Optim 8(2):476–505MathSciNetMATHCrossRef
56.
Pham Dinh T, Le Thi HA (2014) Recent advances in DC programming and DCA. In: Nguyen NT, Le Thi HA (eds) Transactions on computational intelligence XIII, vol 8342. Springer, Berlin, pp 1–37CrossRef
57.
Rosenblatt F (1958) The perceptron: a probabilistic model for information storage and organization in the brain. Psychol Rev 65(6):386–408CrossRef
58.
Shalev-Shwartz S (2007) Online learning: theory, algorithms, and applications. Ph.D. thesis, The Hebrew University of Jerusalem
59.
Shalev-Shwartz S (2012) Online learning and online convex optimization. Found Trends Mach Learn 4(2):107–194MATHCrossRef
60.
Shor NZ (1985) Minimization methods for non-differentiable functions, 1 edn. Springer Series in Computational Mathematics 3. Springer, Berlin
61.
Valadier M (1969) Sous-différentiels d’une borne supérieure et d’une somme continue de fonctions convexes. CR Acad. Sci. Paris Sér. AB 268:A39–A42MATH
62.
Van Der Malsburg C (1986) Frank rosenblatt: principles of neurodynamics: perceptrons and the theory of brain mechanisms. In: Palm G, Aertsen A (eds) Brain theory. Springer, Berlin, pp 245–248CrossRef
63.
Vovk V (1990) Aggregating strategies. In: Proceedings of the third annual workshop on computational learning theory. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, pp 371–386
64.
65.
Wang W, Carreira-Perpiñán MÁ (2013) Projection onto the probability simplex: an efficient algorithm with a simple proof, and an application. arxiv:​ 1309.​1541
66.
Wilcoxon F (1945) Individual comparisons by ranking methods. Biometr Bull 1(6):80–83CrossRef
67.
Wu P, Hoi SCH, Zhao P, Miao C, Liu Z (2016) Online multi-modal distance metric learning with application to image retrieval. IEEE Trans Knowl Data Eng 28(2):454–467CrossRef
68.
Yaroshinsky R, El-Yaniv R, Seiden SS (2004) How to better use expert advice. Mach Learn 55(3):271–309MATHCrossRef
69.
Zinkevich M (2003) Online convex programming and generalized infinitesimal gradient ascent. In: Fawcett T, Mishra N (eds) Proceedings of the 20th international conference on machine learning (ICML-03), pp 928–936
Metadaten
Titel
DCA for online prediction with expert advice
verfasst von
Hoai An Le Thi
Vinh Thanh Ho
Publikationsdatum
26.02.2021
Verlag
Springer London
Erschienen in
Neural Computing and Applications / Ausgabe 15/2021
Print ISSN: 0941-0643
Elektronische ISSN: 1433-3058
DOI
https://doi.org/10.1007/s00521-021-05709-0

Weitere Artikel der Ausgabe 15/2021

Neural Computing and Applications 15/2021 Zur Ausgabe

Original Article

Signals classification based on IA-optimal CNN

Original Article

ID-Net: an improved mask R-CNN model for intrusion detection under power grid surveillance

Original Article

Similarity measures for type-2 fuzzy sets and application in MCDM

Review

Harris hawks optimization: a comprehensive review of recent variants and applications

Original Article

Self-guided deep deterministic policy gradient with multi-actor

Original Article

Application of artificial intelligence based on deep learning in breast cancer screening and imaging diagnosis