Ειδικό Θέμα: Eπεξεργασία δεδομένων βίντεο προσώπου από πολλαπλές πόζες

Αξελός Χρήστος, ΑΕΜ 1814, 5ο έτος, 10ο Εξάμηνο

---

Σκοπός Ειδικού Θέματος

• Πειραματική εξέταση του Αλγορίθμου Random Forests στο πρόβλημα του Gaze Recognition

• Αναφορά των δυνατών και αδύνατων σημείων του αλγορίθμου

Αναφορά στο πρόβλημα του Gaze Recognition

• Gaze Recognition ή Gaze tracking είναι μια διαδικασία όπου προσπαθούμε να μετρήσουμε την διεύθυνση του βλέμματος ενός ματιού ή το σημείο που αυτό κοιτάζει

Πρακτικές εφαρμογές του Gaze Recognition

1) Χρήση της τεχνολογίας από άτομα με ειδικές ανάγκες. Το μάτι λειτουργεί ως χειριστής

• Για κάποιους ανθρώπους τα μάτια ίσως είναι το μοναδικό μέσο επικοινωνίας με το περιβάλλον

• Το μάτι θα μπορούσε να παίξει τον ρόλο απλών μέχρι και πιο πολύπλοκων λειτουργιών, όπως τον ρόλο που έχει το ποντίκι σε έναν υπολογιστή [7] ή ένας διάκοπτης

2) Χρήση της τεχνολογίας για να ελέγξουμε κατά πόσο κάποιος είναι συγκεντρωμένος σε κάτι

• Για παράδειγμα, μπορούμε να καταλάβουμε κατά πόσο οι θεατές μιας παράστασης βρίσκουν ενδιαφέρουσα την παράσταση [8]

• Μια ιστιοσελίδα που φιλοξενεί διαφημίσεις, θα μπορούσε να μετρά το αντίκτυπο της διαφήμισης με βάση το χρόνο που την κοιτάει το μάτι αντί για τον αριθμό των επισκέψεων της σελίδας

3) Χρήση της τεχνολογίας για να προβλέψουμε την δράση κάποιου ατόμου, με δεδομένο το Gaze

• Αν μελετήσουμε μια αλληλουχία κινήσεων των ματιών, μπορούμε να προβλέψουμε τις δράσεις ενός ατόμου

• Σύμφωνα με το [9], αυτό μπορεί να εφαρμοστεί σε καθημέρινες εργασίες(διάβασμα, σερφάρισμα στο internet)

4) Διάφορες άλλες εφαρμογές

• Gaze Tracking κατά τη διάρκεια κάθε είδους προσομοιώσεων

• Χρήση της τεχνολογίας του gaze tracking από συστήματα αυτοκινήτων με στόχο την πρόβλεψη δράσεων του οδηγού

• Χρήση της τεχνολογίας του gaze tracking από τη βιομηχανία ηλεκτρονικών παιχνιδιών

---

Δεδομένα

• Ως δεδομένα επέλεξα το MPIIGaze Dataset[3]. Ωστόσο υπάρχουν κι'άλλα dataset, όπως το Eyediap και το Multiview Dataset [2].

• Οι αρχικές εικόνες έχουνε κανονικοποιηθεί με τέτοιο τρόπο, ώστε να εξετάζονται όλες οι εικόνες υπό τις ίδιες συνθήκες .Επίσης κάθε μάτι εξετάζεται ανεξάρτητα από το άλλο.

• Τα δεδομένα που έχουμε στην διάθεση μας είναι:

  1. Οι εικόνες e του κάθε ματιού με διαστάσεις (W,H) = (60,36)

  2. Ηead Pose, 2d διάνυσμα γωνιών σε radians(γωνία Theta και γωνία Phi)

  3. Gaze(2d διάνυσμα επίσης σε radians) το όποιο προσπαθούμε να κάνουμε predict. Κάθε μάτι γίνεται predict ανεξάρτητα από το άλλο

  4. Η γωνία Theta εκφράζει την οριζόντια θέση του κεφαλιού. Για παράδειγμα αν το κεφάλι έχει προσανατολισμό προς τα δεξιά, θα έχει θετική τιμή, ενώ αν κοιτάει προς τα αριστερά, θα έχει αρνητική.

  5. Η γωνία Phi λειτουργεί σαν την Theta, αλλά για τον κάθετο άξονα. Για παράδειγμα, αν το κεφάλι έχει προσανατολισμό προς τα πάνω, θα έχει θετική τιμή, ενώ αν κοιτάει προς τα κάτω, θα έχει αρνητική

  6. Και οι 2 αυτές γωνίες κυμαίνονται στο διάστημα [-30, +30] σε μοίρες

• Για τον αλγόριθμο Random Forest, κάνουμε reshape τις εικόνες των ματιών από (W,H) = (60,36) σε (15,9) τόσο για το training, όσο και για το testing

---

Υλοποίηση Αλγορίθμου

• Για την υλοποίηση του αλγορίθμου, βασίστηκα στην αρχική υλοποίηση του Breiman[1], κάνοντας κάποιες αλλαγές στον τρόπο που διαλέγουμε τα features κατά το split

• Πραγματοποιήσα όμως κάποιες αλλαγές σύμφωνα με τον Sugano [2], ο οποίος χρησιμοποίησε μια παραλλαγή των Random Forests που λέγεται Redundant Random Forests

• Αντίθετα με τον κλασσικό αλγόριθμο των Random Forests του Breiman [1], όπου υπάρχει ένα δάσος και κάθε δέντρο ανήκει σε ένα δάσος, στα Redundant Random forests δημιουργούνται πολλά δάση και ένα δέντρο ανήκει σε παραπάνω από ένα δάση

• Παρακάτω εξηγώ αναλυτικά τον αλγόριθμο αυτόν

---

Ομαδοποίηση των δεδομένων με βάση τα Head Poses

• Για την υλοποίηση του αλγορίθμου, αρχικά ομαδοποιούμε τα training samples σε P pose clusters, με βάση το Head Pose

• Κάθε Cluster έχει ένα κέντρο, το οποίο αποτελείται από ένα διάνυσμα (theta, phi)

• Για να θεωρηθεί ένα διανύσμα (theta, phi) ως κέντρο ενός Cluster, θα πρέπει να μην απέχει απόσταση μικρότερη από Χ από τα ήδη υπάρχοντα κέντρα(πχ στο παρακάτω σχήμα χρησιμοποιώ Χ=0.08 και δημιουργούνται 106 Clusters).

• Όσο μικρότερο το Χ, τόσο πιο πολλά Clusters δημιουργούνται
  

Εικόνα 1: Διάγραμμα που απεικονίζει τα Head Poses όλων των σημείων του Training Phase. Με πράσινο χρώμα απεικονίζονται τα κέντρα των Clusters, ενώ με μπλέ χρώμα τα υπόλοιπα σημεία. Η παραπάνω εικόνα χρησιμοποιεί 44640 training δείγματα, ενώ τα κέντρα απέχουν μεταξύ τους απόσταση μεγαλύτερη των 0.03 radians(1.718873) μοίρες)

---

Κατασκευή του δάσους μέσα από Regression Decision Trees

• Χρησιμοποιώ την bootstrap διαδικασία, επιλέγοντας τυχαία inputs

• Δημιουργούμε τόσα δέντρα, όσα και τα Pose Clusters, δηλαδή P

• Κάθε δέντρο παίρνει training data από τα R-nearest Clusters. Δηλαδή R Clusters με τα κοντινότερα Head Poses

• Ως error παίρνουμε το μέσο gaze error από όλα τα regression trees.

Εικόνα 2: Παράδειγμα όπου γειτονικά Clusters συνεισφέρουν στην κατασκευή ενός δέντρου. Στα Clusters ανοίκουν δείγματα με παρόμοια Head Poses

---

Πώς εκπαιδεύεται το κάθε δέντρο του δάσους

• Σε κάθε κόμβο ενός δέντρου, προσπαθούμε να μάθουμε συναρτήσεις της μορφής

$$ f = px1 - px2 $$

• Τα px1, px2 είναι οι Gray τιμές από 2 pixel της eye Image (W=15,H=9).

• Τα pixels αυτά μαθαίνονται μέσα από το training.

• Επίσης προσπαθούμε να "μάθουμε" το βέλτιστο threshold τ για κάθε κόμβο, όπου:

  1. αν $ f < τ $, τότε το training sample κατευθύνεται στο αριστερό υποδέντρο

  2. αν $ f >= τ $, τότε κατευθύνεται στο δεξιό υποδέxντρο

• Ο αλγόριθμος με τον οποίο υπολογίζουμε ποια είναι τα βέλτιστα pixels και το βέλτιστο threshold για το split σε κάθε κόμβο του δέντρου είναι το minimum residual sum of squares

$$ \begin{align} error =\sum_{\substack{i:f_{j}\lt{thres}}}^{nleft} (g_{i} - \hat{ m_{left} } )^2 + \sum_{\substack{i:f_{j}\ge{thres}}}^{nright} (g_{i} - \hat{ m_{right} } )^2\end{align} $$

• Τα $nleft$ και $nright$ είναι ο αριθμός των δειγμάτων που θα είχε κάθε υποδέντρο, σε περίπτωση που γινόταν το split με βάση τα $px1$,$px2$,$thres$

• Τα $\hat{ m_{right} }$ και $\hat{ m_{left} }$ είναι η μέση τιμή των gazes που ανήκουν στο δεξί και αριστερό υποδέντρο

• Διαλέγουμε τα $px1$,$px2$,$thres$ που ελαχιστοποιούν το παραπάνω άθροισμα

Εικόνα 3:Στιγμιότυπο υποδέντρου 10 δειγμάτων. Ανάλογα με τις τιμές των Pixel του δείγματος, το τελευταίο θα οδηγηθεί σε έναν τερματικό κόμβο(φύλλο)

• Γενικότερα στα random forests(Breiman 1984, regression and classification trees), σε προβλήματα regression, προτιμάται ο αλγόριθμος των resindual sum of squares. Αντίθετα με τα regression forests, στα classification προβλήματα η κατασκευή των δέντρων βασίζεται σε άλλες μεθόδους όπως το tree entropy/gain ή το Gini impurity index

• Στόχος των sum of squares είναι να δημιουργηθεί το split, ώστε να πετυχαίνεται στα υποδέντρα το μικρότερο δυνατό variance

• Ο τρόπος μάθησης των στοιχείων διαχωρισμού περιγράφεται παρακάτω:

Εικόνα 4:Στιγμιότυπο υποδέντρου 10 δειγμάτων. Ανάλογα με τις τιμές των Pixel του δείγματος, το τελευταίο θα οδηγηθεί σε έναν τερματικό κόμβο(φύλλο)

• Οπότε έτσι μαθαίνουμε τα minPx1, minPx2, minThreshold κάθε κόμβου

---

Πώς γίνεται το testing

• Μόλις θέλουμε να ελέγξουμε ένα testing sample, δεν το στέλνουμε σε όλα τα δέντρα, αλλά στα R-nearest δέντρα με βάσει το head pose

• Τότε υπολογίζουμε το average error από τα R-nearest regression δέντρα.

• Μας ενδιαφέρει ωστόσο να γνωρίζουμε και την τυπική απόκλιση(standard deviation), για να βλέπουμε πόσο κοντά είναι οι προβλέψεις μας στο mean error

---

Πειραματική Αξιολόγηση Αλγορίθμου

• Κατά την αναλυτική αξιολόγηση του Αλγορίθμου θα πρέπει να απαντήσουμε τα εξής ερωτήματα:

  1. Ποιός είναι ο βέλτιστος αριθμός από Clusters ή ισοδύναμα ποιά θα είναι η μικρότερη δυνατή απόσταση μεταξύ 2 κέντρων

  2. Ποιός είναι ο βέλτιστος αριθμός γειτόνων κάθε Cluster

  3. Ποιός είναι ο βέλτιστος αριθμός δειγμάτων εκπαίδευσης

  4. Κατά τη διαδικασία δημιουργίας υποδέντρων σε ένα δέντρο, πόσες μεταβλητές διαχωρισμού χρησιμοποιούμε?

  5. Πόσο βάθος πρέπει να έχει το κάθε δέντρο

  6. Αν σε ένα δέντρο καταλήξουμε σε φύλλο όπου υπάρχουν παραπάνω από ένα δείγματα, πώς προσδιορίζεται η 2d-gaze του συγκεκριμένου δέντρου

Ερώτημα 1ο: Εύρεση μικρότερης απόστασης Κέντρων/Αριθμός Clusters

• Επειδή δεν έχουμε υπολογίσει ακόμα τον βέλτιστο αριθμό γειτόνων, θεωρώ αρχικά πως R = 5 γείτονες.

• Επίσης, για να μειώσω τον χρόνο εκπαίδευσης, χρησιμοποιώ αρχικά 10,000 training samples

• Ο αριθμός των μεταβλητών διαχωρισμού που θα χρησιμοποιούσαμε είναι WIDTH * HEIGHT * THRESHOLD_RANGE = 15 * 16 * 255. Επειδή ο αριθμός αυτός είναι υπερβολικά μεγάλος, σύμφωνα με το paper του Breiman αρκεί χρησιμοποιήσουμε την τετραγωνική ρίζα αυτού του αριθμού

• Τέλος, αν ένα φύλλο ενός δέντρου περιέχει παραπάνω από ένα training samples, υπολογίζω απλώς τον μέσο όρο των 2-d gazes και προκύπτει ένα 2d-gaze διάνυσμα

• Δεν περιορίζουμε το βάθος του κάθε δέντρου

• Με βάση τα παραπάνω, υπολογίζουμε το mean error και το standard deviation

Εικόνα 5:Διάγραμμα με οριζόντιο άξονα την ελάχιστη απόσταση σε rad ανάμεσα σε 2 κέντρα των γειτονικών Cluster συναρτήσει του μέσου σφάλματος και της τυπικής απόκλισης. Για απόσταση d=0.05 rad παρατηρούμε το ελάχιστο μέσο σφάλμα. H τυπική απόκλιση είναι υψηλή(=5.31 μοίρες)

• Από το γράφημα παρατηρούμε πως το mean error γίνεται ελάχιστο για όταν η minimum απόσταση ανάμεσα στα κέντρα είναι 0.05 degrees(οριζόντια + κάθετα)

• Ωστόσο η τυπική απόκλιση είναι αρκετά μεγάλη(5.38 μοίρες), πράγμα που σημαίνει πως οι προβλέψεις έχουν αρκετή διαφορά μεταξύ τους ως προς τον μέσο όρο

• Κρατάμε ως απόσταση το 0.05 μεταξύ των κεντρών. Θέτοντας την απόσταση των κεντρών(των Cluster) 0.05, για 10,000 δείγματα εκπαίδευσης προκύπτουν 238 κέντρα

Ερώτημα 2ο: Βέλτιστος Αριθμός γειτονικών Cluster/ αριθμός δέντρων

• Ο συνολικός αριθμός των Cluster είναι ίσος με τον συνολικό αριθμό δέντρων

• Κρατάμε ως δεδομένα την minimum απόσταση μεταξύ 2 κέντρων(=0.05 rads) που βρήκαμε στο προηγούμενο ερώτημα και συνεχίζουμε τις μετρήσεις, αναζητώντας τον ιδανικό αριθμό γειτονικών Cluster που θα συνεισφέρουν στην εκπαίδευση ενός δέντρου.

• Όπως και στο προηγούμενο ερώτημα, ο αριθμός των δειγμάτων εκπαίδευσης παραμένει 10,000

Εικόνα 6:Διάγραμμα με οριζόντιο άξονα τον αριθμό γειτόνων που συνεισφέρουν στην εκπαίδευση ενός δέντρου συναρτήσει του μέσου σφάλματος και της τυπικής απόκλισης. Το ελάχιστο μέσο σφάλμα παρατηρείται για R = 30. Από το σημείο αυτό και μετά η μείωση θεωρείται αμελητέα. H τυπική απόκλιση εξακολουθεί να παραμένει αρκετά υψηλή(περίπου 5 μοίρες)

• Παρατηρούμε πως η αύξηση του αριθμού των γειτόνων(μέχρι ένα σημείο) προκαλεί μείωση του σφάλματος

• Αυτό συμβαίνει διότι καθώς αυξάνουμε τον αριθμό γειτόνων, περισσότερα δέντρα συνεισφέρουν στο τελικό αποτέλεσμα που θέλουμε να προβλέψουμε

• Έτσι, παίρνοντας ως αποτέλεσμα την μέση πρόβλεψη όλων των δέντρων, μικραίνει η πιθανότητα να έχουμε λανθασμένες προβλέψεις

• Αυτό είναι το σημείο που υπερτερούν τα random forests σε σχέση με τα decision trees. Τα decision trees από την φύση τους μπορούν εύκολα να κάνουν μία λάθος πρόβλεψη. Στα random forests, αν ένα δέντρο κάνει μια "κακή πρόβλεψη", τα υπόλοιπα δέντρα είναι σε θέση να διορθώσουν την πρόβλεψη αυτή, αφού παίρνουμε τον μέσο όρο όλων των δέντρων

• Γενικά, όσο πιο πολλά είναι τα δέντρα τόσο πιο καλή θα είναι η πρόβλεψη. Απλά από ένα σημείο και μετά δεν θα έχει νόημα να αυξάνουμε τα δέντρα, γιατί η αύξυση θα γίνεται ελάχιστη σε σχέση με τον επιπρόσθετο χρόνο εκπαίδευσης που χρειαζόμαστε(συγκλίνει δηλαδή σε κάποιο αριθμό η επίδοση)

Ερώτημα 3ο: Ποιός είναι ο βέλτιστος αριθμός δειγμάτων εκπαίδευσης

• Θεωρώντας δεδομένο τον αριθμό γειτόνων(R=5) και την ελάχιστη απόσταση των κέντρων των Clusters(dist=0.05), προσπαθούμε να βρούμε τον βέλτιστο αριθμό δειγμάτων εκπαίδευσης.

Εικόνα 6:Διάγραμμα με οριζόντιο άξονα τον αριθμό δειγμάτων εκπαίδευσης συναρτήσει του μέσου σφάλματος και της τυπικής απόκλισης. Το μέσο σφάλμα συγκλίνει στην τιμή 6.49 μοίρες, ενώ η τυπική απόκλιση παραμένει γύρω στις 4.7 μοίρες

• Σύμφωνα με τον Breiman, τα random forests αποφεύγουν το overfitting καθώς αυξάνεται το training sample

• Οπότε παίρνουμε ως ολικό μέσο σφάλμα 6.49247 μοίρες με τυπική απόκλιση ως προς αυτό 4.70 μοίρες

Ερώτημα 4ο: Εύρεση αριθμού μεταβλητών διαχωρισμού(split features)

• Μεταβλητές διαχωρισμού(split features) είναι μεταβλητές οι οποίες καθορίζουν πώς θα γίνει το split(διαχωρισμός training samples) σε κάθε κόμβο του δέντρου.

• Στο συγκεκριμένο πρόβλημα, χρησιμοποιούμε τις εξής μεταβλητές διαχωρισμού:

  1. Τις συντεταγμένες(height,width) του pixel 1

  2. Τις συντεταγμένες(height,width) του pixel 2

  3. Την απόσταση(threshold) ανάμεσα στις gray τιμές(0 -> 255 εύρος) αυτών των 2 pixel

• Υπάρχουν height*width πιθανές τιμές που μπορούν να πάρουν η 1η και η 2η μεταβλητή

• Η μεταβλητή threshold έχει εύρος τιμών(thres_range) από 0 μέχρι 50(αυθαίρετο το 50)

• Κατά την διαδικασία της εκμάθησης, είπαμε πως προσπαθούμε να μάθουμε τί τιμή θα έχουν αυτές οι μεταβλητές σε κάθε μή-τερματικό κόμβο του κάθε δέντρου

• Ωστόσο, υπολογιστικά θα ήταν δύσκολο να δοκιμάσω $thresholdRange * (heightwidth)^2 = 50(9*15)^2 = 911,250$ διαφορετικές παραμέτρους, ώστε να τις χρησιμοποιήσω στον τύπο για τον υπολογισμό του minimum square error

• Αυτό λύνεται σύμφωνα με τον Breiman(2001), o oποίος αναφέρει πως δεν χρειάζεται να δοκιμάσουμε όλους τους συνδιασμούς των παραμέτρων. Αρκεί να χρησιμοποιήσουμε την τετραγωνική ρίζα αυτών, επιλέγοντας τυχαίους συνδιασμούς(στην εικόνα 4, o αλγόριθμος ανταποκρίνεται για τους 911,250 συνδιασμούς. Στην πράξη όμως χρησιμοποιούμε την τετραγωνική ρίζα αυτών)

• Πράγματι, παρόλο που δεν πραγματοποιούμε όλους τους συνδιασμούς, η απόδοση του αλγορίθμου παραμένει η υψηλότερη όταν χρησιμοποιούμε την τετραγωνική ρίζα των συνδιασμών

Ερώτημα 5ο: Βέλτιστο βάθος κάθε δέντρου

• Ο πιο διαδεδομένος τρόπος για περιορισμό του βάθους ενός δέντρου είναι να θεωρήσουμε πως σε ένα φύλλο πρέπει να υπάρχουν τουλάχιστον N δείγματα, με N >= 1.

• Έτσι μπορούμε να περιορίσουμε το μέγεθος ενός δέντρου, καθώς και να μειώσουμε τον χρόνο εκπαίδευσης του

• Πραγματοποίησα μετρήσεις όπου πείραζα τον αριθμό Ν. Παρατήρησα όμως ότι για Ν <= 7 η απόδοση ήταν ίδια, ενώ για Ν > 7 η απόδοση χειροτέρευε

• Σύμφωνα με τον Breiman(2001), στα random forests το βάθος κάθε δέντρου δεν θα πρέπει να περιορίζεται

• Αντίθετα με τα δέντρα αποφάσεως όπου χωρίς περιορισμό του βάθους υπάρχει κίνδυνος overfitting [5], στα random forests δεν είναι τόσο σημαντίκος

• Ο λόγος είναι το ότι αν περιορίσουμε το μέγεθος των δέντρων, τότε τα δέντρα θα αρχίσουν να μοιάζουν μεταξύ τους, οπότε δεν έχει νόημα το έχουμε πολλά όμοια δέντρα

• Πολλά όμοια δέντρα σημαίνει ότι όλα τα δέντρα παίρνουν την ίδια απόφαση, οπότε ο αλγόριθμος μετατρέπεται στον αλγόριθμο των decision trees αλλά με πολλά ίδια δέντρα

Ερώτημα 6ο: Πώς προσδιορίζουμε την 2-gaze ενός δέντρου, αν σε ένα φύλλο υπάρχουν παραπάνω από ένα training samples

• Στους παραπάνω υπολογισμούς, χρησιμοποίησα τον μέσο όρο των 2d-gazes από όλα τα training samples που βρισκόντουσαν σαυτό το φύλλο του δέντρου

• Υπάρχουν όμως κιάλλοι μέθοδοι, όπως αρκετά διαδεδόμενο στην περίπτωση αυτή logistic regression τις οποίες τις αναφέρω ως εναλλακτικές/βελτιστοποιήσεις

---

Σύγκριση σε σχέση με τις μετρήσεις των Sugano, Zhang

• Συγκεντρώνωντας όλες τις μετρήσεις που κάναμε, βρήκαμε πως το ελάχιστο μέσο error είναι 6.49247 μοίρες με τυπική απόκλιση 4.79 μοίρες και πετυχαίνεται για αριθμό γειτόνων R = 30 αριθμό δειγμάτων 80,000

• O Sugano στο [2], χρησιμοποιώντας διαφορετικό database απο εμας(Multiview Dataset), υπολογίζει παρόμοιο με μας ελάχιστο σφάλμα(=6.5) μοίρες.

• Ωστόσο η τυπική απόκλιση κυμαίνεται πολύ χαμηλότερα από τους υπολογισμούς που πραγματοποιήσαμε(=1.5 μοίρες), πράγμα που κάνει τις προβλέψεις του πιο σταθερές ως προς την ορθότητα.

• Τους βέλτιστους υπολογισμούς τους πετυχαίνει χρησιμοποιώντας R = 5 δέντρα, ενώ ο αριθμός των δειγμάτων εκπαίδευσης που χρησιμοποιεί έχει την ίδια επίδοση με τις μετρήσεις που πραγματοποιήσαμε προηγουμένως

• Από την άλλη ο Zhang στο [3] χρησιμοποιεί το ίδιο database με μας(MPIIGaze). Πετυχαίνει και αυτός παρόμοιο με μας mean error(=6.5 μοίρες) ενώ ως τυπική απόκλιση πετυχαίνει κιαυτός γύρω στην 1.5 μοίρα. Πολύ χαμηλότερη από το δικό μας

• Στα paper [2,3] περιέχονται αναλυτικά διαγράμματα που δείχνουν τα σφάλματα των Sugano και Zhang(Sugano [2], εικόνα 2, cross-subject και Zhang [3], εικόνα 8)

---

Πιθανές βελτιώσεις του αλγορίθμου

• Υπάρχουν κάποιες πιθανές βελτιστοποιήσεις τις οποίες δεν δοκίμασα, αλλά θα μπορούσαν να επιφέρουν βελτίωση στην απόδοση

1) Εισαγωγή μεθόδων για hyperparameter tuning(cross-validation, grid-random search)

• Σύμφωνα με τον Breiman(2001), δεν είναι απαραίτητο το cross-validation στα Random Forests, λόγω του Bagging που μειώνει την διασπορά

• Εφαρμόζοντας όμως K-fold Evaluation μπορούμε να μειώσουμε την διασπορά(σύμφωνα με το [6]), πράγμα που αποτελεί το πρόβλημα στους υπολογισμούς μας.

• Από την άλλη πλευρά, στο συγκεκριμένο πρόβλημα ο αριθμός των features είναι πολύ μεγάλος σε σχέση με τα training data για να εφαρμόσουμε το grid search, λόγω του ότι και απαιτεί πολύς χρόνος.

• Λόγω της τυχαιότητας και του ότι κάθε φορά χρησιμοποιούμε την τετραγωνική ρίζα όλων των πιθανών αναζητήσεων(=911,250 χιλιάδες) για την κατασκευή ενός κόμβου, μπορούμε να πούμε πως εφαρμόζουμε το random search

• Τέλος, σύμφωνα με το [6], η μέθοδος Sequential model-based optimization(SMBO) αποτελεί μία μέθοδο λύσης προβλημάτων βελτιστοποίησης( πακέτο TuneRanger στην γλώσσα R),

2) Μείωση του αριθμού των features

• Όπως αναφέραμε και στο ερώτημα 4, ο αριθμός των features που χρησιμοποιούμε είναι αρκετά μεγάλος(=911,250).

• Αν και ο Breiman(2001) θεωρεί πως η εισαγωγή της τυχαιότητας κατά την επιλογή των features σε συνδιασμό με τον μεγάλο αριθμό δέντρων(γειτόνων στο δικό μας πρόβλημα) μπορεί να εξαλείψει το πρόβλημα του μεγάλου αριθμού από features, θα μπορούσαμε ωστόσο πειραματικά να εφαρμόσουμε αλγορίθμους που μειώνουν τον αριθμό των features(dimensionality reduction) πριν τρέξουμε τον αλγόριθμο μας(πχ. PCA, LDA) και να ελέγξουμε κατά πόσο οι αλγόριθμοι αυτοί μειώνουν το ολικό error.

• Με αυτόν τον τρόπο, θα μπορούσαμε κατά την κατασκευή ενός μη-τερματικού κόμβου να κάνουμε απαλοιφή κάποιων features ώστε να επικεντρωθούμε σε σημαντικά features

• Υπάρχει ωστόσο ο κίνδυνος να δημιουργούνται κατά το training όμοια δέντρα, πράγμα που αφαιρεί το νόημα του αλγορίθμου(καταλήγουμε στα decision trees, όπου η διακύμανση είναι μεγάλη)

3) Κάθε πρόβλεψη ενός δέντρου έχει έναν συντελεστή "αυτοπεποίθησης"

• Η τεχνική αυτή παρουσιάζεται στο [4], όπου κάθε πρόβλεψη ενός μεμονωμένου δέντρου, συνοδεύεται από έναν συντελεστή όμοιο με την τυπική απόκλιση

• Αν στο τερματικό φύλλο ενός δέντρου ανήκουν παραπάνω από 1 training samples, υπολογίζουμε την τυπική απόκλιση των training samples αυτών ως προς την μέση τιμή

• Αν η τιμή της τυπικής απόκλισης ξεπερνά μια προκαθορισμένη τιμή, τότε η πρόβλεψη θεωρείται αναξιόπιστη και το δάσος απορρίπτει την πρόβλεψη αυτού του δέντρου.

• Ο τελικός μέσος όρος στην περίπτωση αυτή υπολογίζεται χωρίς να λαμβάνουμε υπ'όψη το δέντρο αυτό

• Με αυτόν τον τρόπο, απορρίπτουμε προβλέψεις οι οποίες είναι αμφίβολες, καθώς δεν αντικατοπτρίζεται ο μέσος όρος από τα training samples

4) Χρήση κάποιας συνάρτησης αντί του μέσου όρου στα φύλλα των δέντρων

• Στις περιπτώσεις όπου το φύλλο ενός δέντρου περιέχει παραπάνω από ένα training samples, θα μπορούσαμε να χρησιμοποιήσουμε για τον προσδιορισμό του τελικού 2d-gaze διανύσματος κάποια συνάρτηση, αντί για τον υπολογισμού του μέσου gaze

• Ανάλογα με την κατανομή των δεδομένων, θα μπορούσαμε να επιλέξουμε την κατάλληλη συνάρτηση, όπως για παράδειγμα logistic regression, SVMs, ή non-linear συναρτήσεις

---

Λογισμικό που σχετίζεται με τα random forests

• Για να πραγματοποιηθούν οι παραπάνω μετρήσεις, υλοποίησα τον αλγόριθμο των Random Forests αρχικά σε Matlab. Ωστόσο επειδή η απόδοση δεν ήταν η αναμενόμενη, προχώρησα στην υλοποίηση του αλγορίθμου σε C/C++ ώστε να στοχεύσω στην χρονική απόδοση

• Ο λόγος που προχώρησα στην υλοποίηση του αλγορίθμου αντί να χρησιμοποιήσω κάποια από τα παρακάτω έτοιμα πακέτα είναι πως μέσα από την υλοποίηση θα υπήρχε καλύτερη κατανόηση του αλγορίθμου. Επιπλέον επειδή είναι ένας σχετικά εύκολα υλοποιήσιμος αλγόριθμος σε σχέση με άλλους αλγορίθμους, η υλοποίηση έγινε σε λογικά χρονικά πλαίσια

• Το λογισμικό που υλοποιεί τον αρχικό σχεδιασμό των random forests όπως ο Breiman(2001) είχε ορίσει, βρίσκεται στην ιστιοσελίδα του Berkeley και είναι γραμμένο σε Fortran

• Αρκετά δημοφιλές είναι το πακέτο Random Forests σε γλώσσα R

• Υπάρχει επίσης για Python, από το πακέτο Scikit-learn συναρτήσεις για τα Random Forests

• Σε Matlab, υπάρχει η συνάρτηση TreeBagger

• Τέλος, υπάρχει η κλάση RandomTrees της OpenCV για υλοποίηση σε C++

---

Συμπεράσματα

• Τα Random Forests, φαίνεται να έχουν μια σχετικά καλή απόδοση

• Μεγάλο τους πλεονέκτημα είναι το γεγονός ότι μπορούν να εκπαιδευτούν πολύ γρήγορα. Η εκπαίδευση του κάθε δέντρου είναι ανεξάρτητη από τα άλλα, πράγμα που δίνει μεγάλα περιθώρια για παραλληλοποίηση

• Η υλοποίηση τους είναι σχετικά εύκολη σε σχέση με άλλους αλγορίθμους.

• Σύμφωνα με τους υπολογισμούς του Zhang[3], η χρήση ενός CNN(Convolutional Neural Network) θα μπορούσε να πετύχει μεγαλύτερη ορθότητα(6.2 degree error σε σχέση με το 6.5 των Random Forests με παρόμοια τυπική απόκλιση(=1.5 μοίρες)

• Ο μεγάλος αριθμός των features αποτελεί την κύρια αιτία μείωσης της απόδοσης του αλγορίθμου

• Φαίνεται πως η γλώσσα R παρέχει τις περισσότερες δυνατότητες για την χρήση αυτού του αλγορίθμου. Εξίσου καλά μπορεί όμως να αποδώσει και η Python

---

Μελλοντική εργασία

• Ενδιαφέρον παρουσιάζει η διαδικασία με την οποία έγινε η συλλογή των δεδομένων, καθώς και το Normalization(κανονικοποίηση) των δεδομένων. Ο Sugano [2] παρουσιάζει λεπτομερώς την διαδικασία όπου κανονικοποιεί τα δεδομένα(Normalization) καθώς και την αντιστοίχιση των Pixel από τον 3d στον 2d χώρο( Camera Calibration )

• Θα μπορούσε επίσης να γίνει η παρουσίαση μια λεπτομερούς εφαρμογής, όπως αυτές που ανέφερα, όπου η χρήση της τεχνολογίας του Gaze Recognition θα ήταν χρήσιμη

• Επιπλέον, λόγω του ότι ο Zhang [3] παρουσιάσε μια λύση με μικρότερο μέσο σφάλμα χρησιμοποιώντας το ίδιο database με μας, θα μπορούσαμε να εξετάσουμε το πρόβλημα με την χρήση των CNNs(Convolutional Neural Networks)

---

Aναφορές σε βιβλιογραφίες/δημοσιεύσεις

1. Breiman, L., Friedman, J.,Olshen, R., and Stone, C. [1984] Classification and Regression Trees, Wadsworth
2. Y. Sugano, Y. Matsushita, and Y. Sato. [2014] Learning-by-synthesis for appearance-based 3d gaze estimation.
3. Z. Zhang, Y.Sugano, M.Fritz, A. Bulling [2015] Appearance-Based Gaze Estimation in the Wild
4. M. Dantone, J. Gall, G. Fanelli, L. Van Gool [2013]: Real-time facial feature detection using conditional regression forests.
5. Mansour, Y. [1997], Pessimistic decision tree pruning based on tree size
6. Philipp Probst, Marvin Wright and Anne-Laure Boulesteix. [2018], Hyperparameters and Tuning Strategies for Random Forest
7. P. Majaranta, A. Bulling [2014] Eye Tracking and Eye-Based Human–Computer Interaction
8. Z. Zhang, Y.Sugano, A. Bulling [2016] AggreGaze: Collective Estimation of Audience Attention on Public Displays
9. H. Sattar, S. Müller, M. Fritz, A. Bulling [2015] Prediction of Search Targets From Fixations in Open-World Settings