Εκτίμηση του γενικευμένου σφάλματος ενός αλγόριθμου υπολογιστή με την μέθοδο cross validation
Creators: name: Ζαμανίδης, Κωνστατνίνος Σάββα
Publisher: name: Aristotle University of Thessaloniki
Year: 2021
Subjects: Επαναλαμβανόμενη μάθηση-τεστ διαδικασία ενδοεπικύρωσης
k-fold διαδικασία ενδοεπικύρωσης
Εκτίμηση γενικευμένου σφάλματος
Repeated training testing cross validation
k-fold cross validation
Estimation of generalization error

description: Στην παρούσα διπλωματική εργασία θα ασχοληθούμε με την διαδικασία ενδοεπικυρωσης, την οποία θα συμβολίζουμε εν συντομία με CV στο υπόλοιπό κομμάτι της εργασίας. Στην αρχή ορίζουμε τις συναρτήσεις απώλειας, που παίζουν σημαντικό ρόλο στις μεθόδους CV, και παρουσιάζουμε αυτές που χρησιμοποιούμε συνήθως σε προβλήματα CV. Ορίζουμε το σφάλμα γενίκευσης καθώς, επίσης, παρουσιάζουμε και το πλαίσιο της εργασίας. Θα εξετάσουμε ξεχωριστά τις δύο μεθόδους της διαδικασίας ενδοεπικύρωσης, την επαναλαμβανόμενη μάθησης-τεστ διαδικασία ενδοεπικύρωσης και την k-fold διαδικασία ενδοεπικύρωσης. Θα μελετήσουμε τις ιδιότητες κάθε μεθόδου ξεχωριστά, θα δούμε κάποιες βελτιώσεις αυτών των μεθόδων. Αντιμετωπίζουμε το πρόβλημα της εκτίμησης της διακύμανσης των εκτιμητών CV του σφάλματος γενίκευσης. Συγκεκριμένα προσεγγίζουμε το πρόβλημα της εκτίμησης της διακύμανσης των εκτιμητών CV του σφάλματος γενίκευσης ως πρόβλημα κατά προσέγγισης ροπών ενός στατιστικού. Η προσέγγιση δείχνει τον ρόλο των συνόλων εκπαίδευσης και δοκιμών στην απόδοση του αλγορίθμου. Παρέχει μια ικανοποιητική προσέγγιση για την αξιολόγηση διαφόρων μεθόδων που χρησιμοποιούνται για την απόκτηση συνόλων εκπαίδευσης και δοκιμών και λαμβάνει υπόψη την μεταβλητότητα λόγω διαφορετικών συνόλων εκπαίδευσης και δοκιμών. Θα εξετάσουμε τον κατάλληλο αριθμό της επανάληψης στην επαναλαμβανόμενη μάθηση-τεστ CV και τον βέλτιστο αριθμό k στην k-fold CV . Ορίζουμε τον εκτιμητή της αποτελεσματικότητας της επαναδειγματοληψίας της επαναλαμβανόμενης μάθησης- τεστ CV του σφάλματος γενίκευσης και μελετάμε την σχέση του με την επιλογή βέλτιστου μεγέθους δείγματος εκπαίδευσης. Στην συνέχεια ορίζουμε την βέλτιστη τιμή μέσω απλών στατιστικών κανόνων που μας επιτρέπουν να επιλέξουμε το βέλτιστο μέγεθος δείγματος εκπαίδευσης και τον αριθμό των folds. Βλέπουμε ότι υπάρχουν κανόνες απόφασης για τους οποίους μπορούν να ληφθούν λύσεις κλειστής μορφής για το βέλτιστο μέγεθος δείγματος εκπαίδευσης και τεστ και ότι σε μια ευρεία κατηγορία συναρτήσεων απώλειας το βέλτιστο μέγεθος δείγματος εκπαίδευσης ισούται με το μισό του συνολικού μεγέθους δείγματος, ανεξάρτητο από την κατανομή και την ανάλυση των δεδομένων. Μελετάμε την βέλτιστη επιλογή του αριθμού των folds στην k-fold CV και αντιμετωπίζουμε την περίπτωση της ταξινόμησης μέσω λογιστικής παλινδρόμησης και υποστηρικτικών διανυσμάτων μηχανής, τεκμηριώνοντας τους ισχυρισμούς μας και στα δύο, μικρά και μεγάλα δείγματα. Αντιπαραθέτουμε τα αποτελέσματα μας με την χρήση της συνήθης πρακτικής της CV
description: In this paper, we attempt to deal with Cross Validation (henceforth CV). Initially, we define the loss functions which play an important role in CV methods and then, we present the ones we usually use in CV problems. We define the generalization error and present the context of the work as well. We examine separately the two methods of the cross validation, specifically the repeated training testing cross validation and the k-fold cross validation. We will study the properties of each method separately and we will see some improvements of these methods. We address the problem of estimating the variance of CV estimators of the generalization error. In particular, we approach the problem of variance estimation of the CV estimators of generalization error as a problem in approximating the moments of a statistic. The approximation illustrates the role of training and test sets in the performance of the algorithm. It provides a unifying approach to the evaluation of various methods used in obtaining training and test sets and it takes into account the variability due to different training and test sets. We check the optimal number of repeating in repeating learning test CV and the optimal k in k-fold CV. We define the resampling effectiveness of the repeated train-test CV estimators of the generalization error and afterwards, study its relation with the optimal training sample size selection. Then, we define optimality via simple statistical rules that allow us to select the optimal training sample size and the number of folds. Our results indicated that decision rules exist for which closed form solutions of the optimal training/test sample size can be obtained, and in a broad class of loss functions the optimal training sample size equals half of the total sample size, independently of the data distribution and the data analytic task. We study optimal selection of the number of folds in k-fold CV and address the case of classification via logistic regression and support vector machines, substantiating our claims in both small and large sample size. We contrast our results with standard practice in the use of CV