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
Erschienen in:
Chervonenkis’s Recollections Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

21. Bounding Embeddings of VC Classes into Maximum Classes

verfasst von : J. Hyam Rubinstein, Benjamin I. P. Rubinstein, Peter L. Bartlett

Erschienen in: Measures of Complexity

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

One of the earliest conjectures in computational learning theory—the Sample Compression conjecture—asserts that concept classes (equivalently set systems) admit compression schemes of size linear in their VC dimension.

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

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

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"

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
Vorheriges Kapitel PAC-Bayes Bounds for Supervised Classification
Nächstes Kapitel Strongly Consistent Detection for Nonparametric Hypotheses
Fußnoten
1
As discussed below, we consider concept classes evaluated on finite samples. Such projections are equivalent to subsets of the n-cube. Thus we discuss concept classes as such subsets without loss of generality.
 
2
We use \(\mathbf {1}\left[ p\right] \) to denote the indicator function on predicate p, and [n] to denote integers \(\{1,\ldots ,n\}\).
 
Literatur
1.
Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: VC-dimension and shortest path algorithms. In: ICALP’11. Lecture Notes in Computer Science, vol. 6755, pp. 690–699. Springer, Berlin (2011)
2.
Angluin, D.: Computational learning theory: survey and selected bibliography. In: STOC’92, pp. 351–369. ACM (1992)
3.
Anthony, M., Bartlett, P.L.: Neural Network Learning: Theoretical Foundations. Cambridge University Press, Cambridge (1999)
4.
Ben-David, S., Litman, A.: Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes. Discret. Appl. Math. 86(1), 3–25 (1998)MathSciNetCrossRefMATH
5.
Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.: Learnability and the Vapnik-Chervonenkis dimension. J. ACM 36(4), 929–965 (1989)MathSciNetCrossRefMATH
6.
Brönnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discret. Comput. Geom. 14(1), 463–479 (1995)CrossRefMATH
7.
Devroye, L., Györfi, L., Lugosi, G.: A Probabilistic Theory of Pattern Recognition. Springer, Berlin (1996)
8.
Doliwa, T., Simon, H.U., Zilles, S.: Recursive teaching dimension, learning complexity, and maximum classes. In: ALT’10. Lecture Notes in Computer Science, vol. 6331, pp. 209–223 (2010)
9.
Ehrenfeucht, A., Haussler, D., Kearns, M.J., Valiant, L.G.: A general lower bound on the number of examples needed for learning. Inf. Comput. 82(3), 247–261 (1989)MathSciNetCrossRefMATH
10.
Floyd, S.: On space-bounded learning and the Vapnik-Chervonenkis dimension. Technical report TR-89-061, ICSI, UC Berkeley (1989)
11.
Guruswami, V., Hastad, J., Kopparty, S.: On the list-decodability of random linear codes. In: STOC’10, pp. 409–416. ACM (2010)
12.
Haussler, D.: Probably approximately correct learning. In: AAAI’90, pp. 1101–1108 (1990)
13.
Haussler, D.: Sphere packing numbers for subsets of the boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension. J. Comb. Theory Ser. A 69(2), 217–232 (1995)MathSciNetCrossRefMATH
14.
Haussler, D., Littlestone, N., Warmuth, M.: Predicting \(\{0,1\}\) functions on randomly drawn points. Inf. Comput. 115(2), 284–293 (1994)MathSciNetCrossRef
15.
Haussler, D., Welzl, E.: Epsilon-nets and simplex range queries. In: SOGC’86, pp. 61–71. ACM (1986)
16.
Kleinberg, J.M.: Two algorithms for nearest-neighbor search in high dimensions. In: STOC’97, pp. 599–608. ACM (1997)
17.
Kuzmin, D., Warmuth, M.: Unlabeled compression schemes for maximum classes. J. Mach. Learn. Res. 8, 2047–2081 (2007)MathSciNetMATH
18.
19.
Livni, R., Simon, P.: Honest compressions and their application to compression schemes. In: COLT’13 (2013)
20.
Matoušek, J.: Geometric range searching. ACM Comput. Surv. 26(4), 421–461 (1994)
21.
Procaccia, A.D., Rosenschein, J.S.: Exact VC dimension of monotone formulas. Neural Inf. Process. Lett. Rev. 10(7), 165–168 (2006)
22.
Rubinstein, B.I.P., Bartlett, P.L., Rubinstein, J.H.: Shifting: one-inclusion mistake bounds and sample compression. J. Comput. Syst. Sci.: Spec. Issue Learn. Theory 2006 75(1), 37–59 (2009)
23.
Rubinstein, B.I.P., Rubinstein, J.H.: Geometric & topological representations of maximum classes with applications to sample compression. In: COLT’08, pp. 299–310 (2008)
24.
Rubinstein, B.I.P., Rubinstein, J.H.: A geometric approach to sample compression. J. Mach. Learn. Res. 13(1), 1221–1261 (2012)MathSciNetMATH
25.
Sauer, N.: On the density of families of sets. J. Comb. Theory Ser. A 13(1), 145–147 (1972)
26.
Shelah, S.: A combinatorial problem; stability and order for models and theories in infinitary languages. Pac. J. Math. 41(1), 247–261 (1972)CrossRefMATH
27.
Trudeau, R.J.: Introduction to Graph Theory. Dover, New York (1994)
28.
van der Vaart, A.W., Wellner, J.A.: Weak Convergence and Empirical Processes. Springer, Berlin (1996)
29.
Vapnik, V.N., Chervonenkis, A.Y.: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16(2), 264–280 (1971) (This volume, Chap. 3)
30.
von Luxburg, U., Bousquet, O., Schölkopf, B.: A compression approach to support vector model selection. J. Mach. Learn. Res. 5, 293–323 (2004)
31.
Warmuth, M.K.: Compressing to VC dimension many points. In: COLT’03, Learning Theory and Kernel Machines. Lecture Notes in Computer Science, vol. 2777, pp. 743–744 (2003)
32.
Welzl, E.: Complete range spaces (1987) (Unpublished notes)
33.
Welzl, E., Wöginger, G.: On Vapnik-Chervonenkis dimension one (1987) (Unpublished notes)
Metadaten
Titel
Bounding Embeddings of VC Classes into Maximum Classes
verfasst von
J. Hyam Rubinstein
Benjamin I. P. Rubinstein
Peter L. Bartlett
Copyright-Jahr
2015
Buch
Measures of Complexity

Print ISBN: 978-3-319-21851-9

Electronic ISBN: 978-3-319-21852-6

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-21852-6_21