On the VC-dimension of univariate decision trees

dc.authorid0000-0001-5838-4615
dc.contributor.authorYıldız, Olcay Taneren_US
dc.date.accessioned2019-08-31T12:10:23Z
dc.date.accessioned2019-08-05T16:04:58Z
dc.date.available2019-08-31T12:10:23Z
dc.date.available2019-08-05T16:04:58Z
dc.date.issued2012
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.abstractIn this paper, we give and prove lower bounds of the VC-dimension of the univariate decision tree hypothesis class. The VC-dimension of the univariate decision tree depends on the VC-dimension values of its subtrees and the number of inputs. In our previous work (Aslan et al., 2009), we proposed a search algorithm that calculates the VC-dimension of univariate decision trees exhaustively. Using the experimental results of that work, we show that our VC-dimension bounds are tight. To verify that the VC-dimension bounds are useful, we also use them 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 VC-dimension bounds finds trees that are more accurate as those pruned using cross-validation.en_US
dc.description.versionPublisher's Versionen_US
dc.identifier.citationYıldız, O. T. (2012). On the VC-dimension of univariate decision trees. Paper present et the ICPRAM 2012 - Proceedings of the 1st International Conference on Pattern Recognition Applications and Methods, 205-210. doi:10.5220/0003777202050210en_US
dc.identifier.endpage210
dc.identifier.isbn9789898425980
dc.identifier.scopus2-s2.0-84862192969
dc.identifier.scopusqualityN/A
dc.identifier.startpage205
dc.identifier.urihttps://hdl.handle.net/11729/1934
dc.identifier.urihttp://dx.doi.org/10.5220/0003777202050210
dc.identifier.volume1
dc.indekslendigikaynakScopusen_US
dc.institutionauthorYıldız, Olcay Taneren_US
dc.institutionauthorid0000-0001-5838-4615
dc.language.isoenen_US
dc.peerreviewedYesen_US
dc.publicationstatusPublisheden_US
dc.relation.ispartofICPRAM 2012 - Proceedings of the 1st International Conference on Pattern Recognition Applications and Methodsen_US
dc.relation.publicationcategoryKonferans Öğesi - Uluslararası - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.subjectDecision treesen_US
dc.subjectVC-dimensionen_US
dc.subjectPattern recognitionen_US
dc.subjectCross validationen_US
dc.subjectLower boundsen_US
dc.subjectSearch algorithms
dc.subjectSubtreesen_US
dc.subjectUnivariateen_US
dc.titleOn the VC-dimension of univariate decision treesen_US
dc.typeConference Objecten_US
dspace.entity.typePublication

Dosyalar

Orijinal paket
Listeleniyor 1 - 1 / 1
Küçük Resim Yok
İsim:
1934.pdf
Boyut:
327.35 KB
Biçim:
Adobe Portable Document Format
Açıklama:
Publisher's Version