Calculating the VC-dimension of decision trees

Basit Öğe Kaydı
dc.authorid0000-0001-5838-4615
dc.authorid0000-0001-7506-0321
dc.contributor.authorAslan, Özlemen_US
dc.contributor.authorYıldız, Olcay Taneren_US
dc.contributor.authorAlpaydın, Ahmet İbrahim Ethemen_US
dc.date.accessioned2019-07-30T17:57:00Z
dc.date.available2019-07-30T17:57:00Z
dc.date.issued2009
dc.departmentIşık Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümüen_US
dc.departmentIşık University, Faculty of Engineering, Department of Computer Engineeringen_US
dc.description.abstractWe propose an exhaustive search algorithm that calculates the VC-dimension of univariate decision trees with binary features. The VC-dimension of the univariate decision tree with binary features depends on (i) the VC-dimension values of the left and right subtrees, (ii) the number of inputs, and (iii) the number of nodes in the tree. From a training set of example trees whose VC-dimensions are calculated by exhaustive search, we fit a general regressor to estimate the VC-dimension of any binary tree. These VC-dimension estimates are then used to get VC-generalization bounds for complexity control using SRM in decision trees, i.e., pruning. Our simulation results shows that SRM-pruning using the estimated VC-dimensions finds trees that are as accurate as those pruned using cross-validation.en_US
dc.description.sponsorshipMiddle East Technical University and IEEEen_US
dc.description.sponsorshipTurkish Sectionen_US
dc.description.versionPublisher's Versionen_US
dc.identifier.citationAslan, O., Yıldız, O. T. & Alpaydın, A. İ. E. (2009). Calculating the VC-dimension of decision trees. Paper presented at the 2009 24th International Symposium on Computer and Information Sciences, 193-198. doi:10.1109/ISCIS.2009.5291847en_US
dc.identifier.doi10.1109/ISCIS.2009.5291847
dc.identifier.endpage198
dc.identifier.isbn9781424450213
dc.identifier.scopus2-s2.0-73949117705
dc.identifier.scopusqualityN/A
dc.identifier.startpage193
dc.identifier.urihttps://hdl.handle.net/11729/1665
dc.identifier.urihttp://dx.doi.org/10.1109/ISCIS.2009.5291847
dc.identifier.wosWOS:000275024200035
dc.identifier.wosqualityN/A
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.indekslendigikaynakConference Proceedings Citation Index – Science (CPCI-S)en_US
dc.institutionauthorYıldız, Olcay Taneren_US
dc.institutionauthorid0000-0001-5838-4615
dc.language.isoenen_US
dc.peerreviewedYesen_US
dc.publicationstatusPublisheden_US
dc.publisherIEEEen_US
dc.relation.ispartof2009 24th International Symposium on Computer and Information Sciencesen_US
dc.relation.publicationcategoryKonferans Öğesi - Uluslararası - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.subjectRegressionen_US
dc.subjectMachineen_US
dc.subjectBinary featuresen_US
dc.subjectCross validationen_US
dc.subjectExhaustive searchen_US
dc.subjectExhaustive search algorithmsen_US
dc.subjectGeneralization bounden_US
dc.subjectSimulation resulten_US
dc.subjectSubtreesen_US
dc.subjectTraining setsen_US
dc.subjectUnivariateen_US
dc.subjectVC-dimensionen_US
dc.subjectDecision treesen_US
dc.subjectInformation scienceen_US
dc.subjectLearning algorithmsen_US
dc.subjectReluctance motorsen_US
dc.subjectBinary treesen_US
dc.subjectTraining dataen_US
dc.subjectVirtual colonoscopyen_US
dc.subjectTestingen_US
dc.subjectPredictive modelsen_US
dc.subjectAlgorithm design and analysisen_US
dc.subjectDesign optimizationen_US
dc.subjectRegression tree analysisen_US
dc.subjectMachine learningen_US
dc.subjectLearning (artificial intelligence)en_US
dc.subjectSearch problemsen_US
dc.subjectExhaustive search algorithmen_US
dc.subjectUnivariate decision treesen_US
dc.subjectGeneral regressoren_US
dc.subjectVC-generalization boundsen_US
dc.subjectComplexity controlen_US
dc.subjectSRMen_US
dc.subjectCross-validationen_US
dc.subjectVapnik-Chervonenkis theoryen_US
dc.subjectStructural risk minimizationen_US
dc.titleCalculating the VC-dimension of decision treesen_US
dc.typeConference Objecten_US
dspace.entity.typePublication

Dosyalar

Orijinal paket
Listeleniyor 1 - 1 / 1
Küçük Resim Yok
İsim:
1665.pdf
Boyut:
175.92 KB
Biçim:
Adobe Portable Document Format
Açıklama:
Publisher's Version
İndir
Lisans paketi
Listeleniyor 1 - 1 / 1
Küçük Resim Yok
İsim:
license.txt
Boyut:
1.71 KB
Biçim:
Item-specific license agreed upon to submission
Açıklama:
İndir

Koleksiyon

Bildiri Koleksiyonu | Bilgisayar Mühendisliği Bölümü
Scopus İndeksli Yayınlar Koleksiyonu
WoS İndeksli Yayınlar Koleksiyonu