nach oben

Knowledge and Information Systems

Erschienen in:

01.08.2015 | Regular Paper

Bounds on the moments for an ensemble of random decision trees

verfasst von: Amit Dhurandhar

Erschienen in: Knowledge and Information Systems | Ausgabe 2/2015

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

An ensemble of random decision trees is a popular classification technique, especially known for its ability to scale to large domains. In this paper, we provide an efficient strategy to compute bounds on the moments of the generalization error computed over all datasets of a particular size drawn from an underlying distribution, for this classification technique. Being able to estimate these moments can help us gain insights into the performance of this model. As we will see in the experimental section, these bounds tend to be significantly tighter than the state-of-the-art Breiman’s bounds based on strength and correlation and hence more useful in practice.

Vorheriger Artikel A masking index for quantifying hidden glitches

Nächster Artikel Reconstructing individual mobility from smart card transactions: a collaborative space alignment approach

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 "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

These probabilities and \( P\left[ Y(x)\!\ne \!y \right] \) are conditioned on \(x\). We omit explicitly writing the conditional since it improves readability and is obvious from the context.

For further details refer to [3] and [5].

This is after splitting the continuous attributes.

Partitioned into 3 categories high, medium and low.

Anandkumar A, Foster D, Hsu D, Kakade S, Liu Y (2012) A spectral algorithm for latent dirichlet allocation. In: NIPS. Lake Tahoe, USA, pp 926–934

Boots B, Gordon G (2012) Two manifold problems with applications to nonlinear system identification. In: ICML. Edinburgh, Scotland, UK, p 338

Breiman L (2001) Random forests. Mach Learn 45(1):5–32CrossRef

Bshouty N, Long P (2010) Finding planted partitions in nearly linear time using arrested spectral clustering. In: ICML. Haifa, Israel, pp 135–142

Buttrey S, Kobayashi I (2003) On strength and correlation in random forests. In : Proceedings of the 2003 joint statistical meetings, section on statistical computing

Connor-Linton J (2003) Chi square tutorial. http://www.georgetown.edu/faculty/ballc/webtools/web_chi_tut.html

Dhurandhar A, Dobra A (2008) Probabilistic characterization of random decision trees. J Mach Learn Res 9:2321–2348

Dhurandhar A, Dobra A (2009) Semi-analytical method for analyzing models and model selection measures based on moment analysis. ACM Trans Knowl Discov Data Min

Dhurandhar A, Dobra A (2012) Distribution free bounds for relational classification. Knowl Inf Syst

10.

Dhurandhar A, Dobra A (2012) Probabilistic characterization of nearest neighbor classifiers. Int J Mach Learn Cybern

11.

Duda RO, Hart PE, Stork DG (2001) Pattern classification, 2nd edn. Wiley, New York, p 654

12.

Fan W, Wang H, Yu PS, Ma S (2003) Is random model better? On its accuracy and efficiency. In: ICDM ’03: proceedings of the third IEEE international conference on data mining, IEEE Computer Society, Washington, DC, USA, pp 51–58

13.

Geurts P, Ernst D, Wehenkel L (2006) Extremely randomized trees. Mach Learn 63(1):3–42CrossRef

14.

Hastie T, Tibshirani R, Friedman J (2001) Elements of statistical learning, 2nd edn. Springer, BerlinCrossRef

15.

Langford John (December 2005) Tutorial on practical prediction theory for classification. J Mach Learn Res 6:273–306

16.

Liu F, Ting K, Fan W (2005) Maximizing tree diversity by building complete-random decision trees. In: PAKDD, pp 605–610

17.

McAllester D (1999) Pac-bayesian model averaging. In: Proceedings of the twelfth annual conference on computational learning theory. ACM Press, pp 164–170

18.

Mcallester D (2003) Simplified pac-bayesian margin bounds. In COLT, pp 203–215

19.

Roy S, Bose R (1953) Simultaneous confidence interval estimation. Ann Math Stat 24(3):513–536CrossRef

20.

Sison C, Glaz J (1995) Simultaneous confidence intervals and sample size determination for multinomial proportions. JASA 90(429):366–369CrossRef

21.

Tong Y (1980) Probabilistic inequalities for multivariate distributions, 1st edn. Academic Press, Waltham

22.

Zhang K, Fan W (2008) Forecasting skewed biased stochastic ozone days: analyses, solutions and beyond. Knowl Inf Syst 14(3):299–326CrossRef

23.

Zhang X, Yuan Q, Zhao S, Fan W, Zheng W, Wang Z (2010) Multi-label classification without the multi-label cost. In: SDM ’10: proceedings of the siam conference on data mining, pp 778–789

Titel: Bounds on the moments for an ensemble of random decision trees
verfasst von: Amit Dhurandhar
Publikationsdatum: 01.08.2015
Verlag: Springer London
Erschienen in: Knowledge and Information Systems / Ausgabe 2/2015
Print ISSN: 0219-1377
Elektronische ISSN: 0219-3116
DOI: https://doi.org/10.1007/s10115-014-0768-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2015

A robust one-class transfer learning method with uncertain data

Compressed vertical partitioning for efficient RDF management

The Author-Topic-Community model for author interest profiling and community discovery

Biclustering neighborhood-based collaborative filtering method for top-n recommender systems

Mining sequential patterns from probabilistic databases

AGraP: an algorithm for mining frequent patterns in a single graph using inexact matching