Ας δούμε ένα διαφορετικό παράδειγμα:
X = {0, 1, 2, 3}
Η D είναι η (άγνωστη) κατανομή πιθανοτήτων που περιγράφει πόσο συχνά εμφανίζεται κάθε είσοδος x στον πραγματικό κόσμο. Την D δεν την γνωρίζει ο learner.
Άρα το 2 εμφανίζεται στο 30% των περιπτώσεων.
Δηλαδή τα x= 0 και 1 έχουν label 0, ενώ τα x= 2 και 3 έχουν label 1. Την labeling function δεν την γνωρίζει ο learner.
Ταυτίζεται ακριβώς με τη f → Μηδενικό σφάλμα. Όπως στο πρώτο παράδειγμα με τον canvas στην προηγούμενη ενότητα (ML2), που όλα τα labels ήταν σωστά για το αστικό περιβάλλον.
Δεν ταυτίζεται ακριβώς με τη f → Όχι μηδενικό σφάλμα. Όπως στο δεύτερο παράδειγμα με τον canvas στην προηγούμενη ενότητα (ML2), που δεν ήταν όλα τα labels σωστά για το αστικό περιβάλλον. Είχαμε βάλει επίτηδες στον πίνακα δύο λάθος labels.
Κάνει λάθος μόνο όταν x = 2.
True Error: Πιθανότητα να κάνει λάθος σε νέο τυχαίο δείγμα. Είναι η πιθανότητα ο classifier να κάνει λάθος όταν του δώσουμε ένα νέο, τυχαίο παράδειγμα από την πραγματική κατανομή D.
Το Empirical Risk ή Training Error είναι το ποσοστό λαθών που κάνει μια υπόθεση πάνω στο training set S.
Ορισμός:
Empirical Risk = (Αριθμός λαθών του h στο S) / m
Έστω training set με m = 5:
S = {
(0,0),
(1,0),
(3,1),
(0,0),
(3,1)
}
Δεν υπάρχει καμία εμφάνιση του x = 2.
Δεν κάνει κανένα λάθος.
LS(h*) = 0 / 5 = 0
Κάνει λάθος μόνο όταν x = 2, αλλά στο S δεν υπάρχει x = 2.
LS(hwrong) = 0 / 5 = 0
S = {
(0,0),
(1,0),
(2,1),
(3,1),
(0,0)
}
Δεν κάνει κανένα λάθος.
LS(h*) = 0 / 5 = 0
Στο x = 2 προβλέπει 0 ενώ η σωστή ετικέτα είναι 1 → 1 λάθος.
LS(hwrong) = 1 / 5 = 0.2
Το empirical risk εξαρτάται από το συγκεκριμένο training set S. Γι’ αυτό γράφουμε hS, για να δείξουμε ότι η υπόθεση που μαθαίνουμε εξαρτάται από τα δεδομένα που παρατηρήσαμε.
ERM (Empirical Risk Minimization): Είναι η στρατηγική μάθησης όπου επιλέγουμε την υπόθεση h που ελαχιστοποιεί το training error Lₛ(h).
Στο πλαίσιο του Machine Learning, δεν μας ενδιαφέρει μόνο αν ένας αλγόριθμος βρίσκει μια υπόθεση με μικρό empirical error στο training set, αλλά αν αυτή η υπόθεση γενικεύει σωστά στον πραγματικό κόσμο. Το μοντέλο Probably Approximately Correct (PAC) εισάγει έναν αυστηρό μαθηματικό τρόπο για να ποσοτικοποιήσουμε αυτή τη γενίκευση, χρησιμοποιώντας δύο παραμέτρους: την ακρίβεια (ε) και την εμπιστοσύνη (δ).
Για να αναλύσουμε πότε ο ERM μπορεί να αποτύχει, χωρίζουμε τις υποθέσεις σε «καλές» και «κακές». Καλή είναι μια υπόθεση με πραγματικό σφάλμα μικρότερο ή ίσο από ε, ενώ κακή είναι μια υπόθεση με πραγματικό σφάλμα μεγαλύτερο από ε. Αν ο ERM επιλέξει κακή υπόθεση, τότε έχουμε αποτυχία μάθησης.
Με άλλα λόγια, στο μοντέλο PAC δεν απαιτούμε τέλεια πρόβλεψη. Επιτρέπουμε ένα μικρό πραγματικό σφάλμα ε, αρκεί η πιθανότητα να ξεπεραστεί αυτό το σφάλμα να είναι μικρότερη από δ. Ο στόχος είναι να εγγυηθούμε ότι: Η πιθανότητα αποτυχίας του learner είναι το πολύ δ.
Η βασική ιδέα της απόδειξης είναι η εξής: ακόμη κι αν μια υπόθεση είναι κακή στον πραγματικό κόσμο, υπάρχει μια μικρή πιθανότητα να φαίνεται τέλεια στο training set. Αυτό μπορεί να συμβεί αν το δείγμα δεν περιέχει σημεία όπου η υπόθεση κάνει λάθος. Υπολογίζουμε λοιπόν την πιθανότητα μια κακή υπόθεση να έχει μηδενικό empirical error.
Από τη θεωρία:
P(LS(h)=0) ≤ (1 - ε)m
Με ε = 0.2:
P(LS(hwrong)=0) ≤ (0.8)m
(0.8)5 = 0.32768
Υπάρχει έως και 32.7% πιθανότητα το training set να μην περιέχει το x=2 και ο ERM να επιλέξει λάθος υπόθεση.
(0.8)20 ≈ 0.0115
Μόνο ~1.1% πιθανότητα να γίνει overfitting.
Μέχρι τώρα εξετάσαμε μία συγκεκριμένη κακή υπόθεση. Όμως ο ERM επιλέγει από ολόκληρο το hypothesis class H. Για να εγγυηθούμε ότι καμία κακή υπόθεση δεν θα ξεγελάσει τον αλγόριθμο, εφαρμόζουμε το Union Bound. Έτσι προκύπτει το συνολικό άνω φράγμα:
Θέλουμε η πιθανότητα αποτυχίας να είναι μικρότερη από δ:
|H| e-εm ≤ δ
Λύνοντας ως προς m:
m ≥ ( log(|H|/δ) ) / ε
Στο παράδειγμά μας:
m ≥ log(2 / 0.05) / 0.2
m ≥ log(40) / 0.2
log(40) ≈ 3.69
m ≥ 3.69 / 0.2 = 18.45