Αποσύνθεση μοναδικής τιμής έναντι παραγοντοποίησης μήτρας σε Συστήματα Συστάσεων

Πρόσφατα, αφού παρακολούθησα το μάθημα Συστημάτων Συστημάτων του μαθήματος Μηχανικής Εκμάθησης του καθηγητή Andrew Ng, βρήκα τον εαυτό μου πολύ ανήσυχο να μην καταλάβω πώς λειτουργεί το Matrix Factorization.

Ξέρω ότι μερικές φορές τα μαθηματικά στη Μηχανική Μάθηση είναι πολύ σκοτεινά. Είναι καλύτερο αν το σκεφτόμαστε ως μαύρο κουτί, αλλά αυτό το μοντέλο ήταν πολύ «μαγικό» για τα πρότυπα μου.

Σε τέτοιες καταστάσεις, συνήθως προσπαθώ να ψάχνω στο Google για περισσότερες αναφορές για καλύτερη κατανόηση της έννοιας. Αυτή τη φορά μπερδεύτηκα ακόμη περισσότερο. Ενώ ο καθηγητής Ng κάλεσε τον αλγόριθμο ως (Low Factor) Matrix Factorization, βρήκα μια διαφορετική ονοματολογία στο Διαδίκτυο: Singular Value Decomposition.

Αυτό που με μπερδεύει περισσότερο ήταν ότι η Αποσύνθεση Μοναδικής Αξίας ήταν πολύ διαφορετική από αυτό που είχε διδάξει ο καθηγητής Ng. Οι άνθρωποι συνέχισαν να προτείνουν ότι ήταν και οι δύο το ίδιο πράγμα.

Σε αυτό το κείμενο, θα συνοψίσω τα ευρήματά μου και θα προσπαθήσω να ξεκαθαρίσω κάποια από τη σύγχυση που μπορούν να προκαλέσουν οι όροι αυτοί.

Συστήματα προτάσεων

Τα Συστήματα Συστάσεων (RS) είναι μόνο αυτοματοποιημένοι τρόποι για να προτείνουν κάτι σε κάποιον. Τέτοια συστήματα χρησιμοποιούνται ευρέως από εταιρείες ηλεκτρονικού εμπορίου, υπηρεσίες ροής και ιστότοπους ειδήσεων. Βοηθά στη μείωση της τριβής των χρηστών όταν προσπαθούν να βρουν κάτι που τους αρέσει.

Η RS σίγουρα δεν είναι καινούργιο πράγμα: έχουν εμφανιστεί τουλάχιστον από το 1990. Στην πραγματικότητα, μέρος της πρόσφατης διαφημιστικής εκστρατείας Machine Learning μπορεί να αποδοθεί στο ενδιαφέρον της RS. Το 2006, η Netflix έκανε μια βουτιά όταν χρηματοδότησε έναν διαγωνισμό για να βρει την καλύτερη RS για τις ταινίες τους. Όπως θα δούμε σύντομα, αυτό το γεγονός σχετίζεται με το χάος της ονοματολογίας που ακολούθησε.

Η αναπαράσταση του πίνακα

Υπάρχουν πολλοί τρόποι με τους οποίους ένα άτομο μπορεί να σκεφτεί να προτείνει μια ταινία σε κάποιον. Μία στρατηγική που αποδείχθηκε πολύ καλή είναι να αντιμετωπίζετε τις αξιολογήσεις ταινιών ως πίνακας Χρήστες x Ταινίες ως εξής:

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

Παραγοντοποίηση Matrix

Μια πραγματικά έξυπνη συνειδητοποίηση που έγινε από τα παιδιά που μπήκαν στον διαγωνισμό του Netflix (κυρίως ο Simon Funk) ήταν ότι οι αξιολογήσεις των χρηστών δεν ήταν απλώς τυχαίες υποθέσεις Οι βαθμολογητές πιθανότατα ακολουθούν κάποια λογική όπου σταθμίζουν τα πράγματα που τους αρέσουν σε μια ταινία (μια συγκεκριμένη ηθοποιός ή ένα είδος) σε σχέση με πράγματα που δεν τους αρέσουν (μεγάλη διάρκεια ή κακά αστεία) και στη συνέχεια καταλήγουν σε ένα σκορ.

Αυτή η διαδικασία μπορεί να αναπαρασταθεί με έναν γραμμικό τύπο του ακόλουθου είδους:

όπου xₘ είναι ένα διάνυσμα στήλης με τις αξίες των στοιχείων της ταινίας m και θᵤ είναι ένα άλλο διάνυσμα στήλης με τα βάρη ώστε ο χρήστης u δίνει σε κάθε χαρακτηριστικό. Κάθε χρήστης έχει ένα διαφορετικό σύνολο βαρών και κάθε ταινία έχει ένα διαφορετικό σύνολο τιμών για τα χαρακτηριστικά του.

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

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

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

Εντάξει, τώρα έχουμε έναν κατά προσέγγιση πίνακα. Αλλά πώς μας βοηθά να προβλέψουμε τις ελλείπουσες βαθμολογίες; Να θυμάστε ότι για να δημιουργήσουμε το νέο πίνακα, δημιουργήσαμε έναν τύπο για να συμπληρώσουμε όλες τις τιμές, συμπεριλαμβανομένων εκείνων που λείπουν στον αρχικό πίνακα. Επομένως, αν θέλουμε να προβλέψουμε την ελλείπουσα βαθμολογία ενός χρήστη σε μια ταινία, παίρνουμε όλες τις τιμές χαρακτηριστικών αυτής της ταινίας, πολλαπλασιάζοντας με όλα τα βάρη αυτού του χρήστη και αθροίζουμε τα πάντα. Έτσι, στο παράδειγμά μου, αν θέλω να προβλέψω την βαθμολογία του χρήστη 2 για την ταινία 1, μπορώ να κάνω τον ακόλουθο υπολογισμό:

Για να κάνουμε τα πράγματα πιο ξεκάθαρα, μπορούμε να αποσυνδέσουμε τα θ και x και να τα βάλουμε στους δικούς τους πίνακες (ας πούμε P και Q ). Αυτό είναι ουσιαστικά ένα Matrix Factorization, εξ ου και το όνομα που χρησιμοποιείται από τον καθηγητή Ng.

Αυτό το Matrix Factorization είναι βασικά αυτό που έκανε ο Funk. Πήρε την τρίτη θέση στον διαγωνισμό του Netflix, προσελκύοντας πολλή προσοχή (που είναι μια ενδιαφέρουσα περίπτωση μιας τρίτης θέσης να είναι πιο διάσημη από τους νικητές). Η προσέγγισή του έχει αναπαραχθεί και τελειοποιηθεί από τότε και εξακολουθεί να χρησιμοποιείται σε πολλές εφαρμογές.

Μοναδική Αποσύνθεση Αξίας

Εισαγάγετε αποσύνθεση μοναδικής τιμής (SVD) Το SVD είναι ένας φανταχτερός τρόπος να παραγοντοποιηθεί μια μήτρα σε τρεις άλλους πίνακες ( A = UΣVᵀ ). Ο τρόπος με τον οποίο γίνεται το SVD εγγυάται ότι οι 3 πίνακες έχουν μερικές ωραίες μαθηματικές ιδιότητες.

Υπάρχουν πολλές εφαρμογές για SVD. Ένα από αυτά είναι η Ανάλυση Κύριων Συστατικών (PCA), η οποία απλώς μειώνει ένα σύνολο δεδομένων της διάστασης n σε διάσταση k ( k <n ).

Δεν θα σας δώσω περισσότερες λεπτομέρειες σχετικά με τα SVDs επειδή δεν ξέρω τον εαυτό μου. Το θέμα είναι ότι δεν είναι το ίδιο πράγμα που κάναμε με το Matrix Factorization. Η μεγαλύτερη απόδειξη είναι ότι το SVD δημιουργεί 3 πίνακες ενώ το Funk's Matrix Factorization δημιουργεί μόνο 2.

Γιατί λοιπόν το SVD συνεχίζει να εμφανίζεται κάθε φορά που ψάχνω για Συστήματα Πρότασης; Έπρεπε να σκάψω λίγο, αλλά τελικά, βρήκα μερικούς κρυμμένους πολύτιμους λίθους. Σύμφωνα με τον Luis Argerich:

Οι αλγόριθμοι παραγοντοποίησης μήτρας που χρησιμοποιούνται για συστήματα προτεινόμενων προσπαθούν να βρουν δύο πίνακες: P, Q όπως το P * Q ταιριάζει με τις ΓΝΩΡΙΖΕΣ τιμές του βοηθητικού πίνακα. Αυτή η αρχή εμφανίστηκε στο διάσημο έγγραφο SVD ++ "Factorization meet the γειτονιά" που δυστυχώς χρησιμοποίησε το όνομα "SVD ++" για έναν αλγόριθμο που δεν έχει απολύτως καμία σχέση με το SVD .

Για την ιστορία, νομίζω ότι ο Funk, όχι οι συγγραφείς του SVD ++, πρότεινε για πρώτη φορά την αναφερθείσα παραγοντοποίηση του matrix για συστήματα συνιστώμενων. Στην πραγματικότητα, το SVD ++, όπως υποδηλώνει το όνομά του, αποτελεί επέκταση της δουλειάς του Funk.

Ο Xavier Amatriain μας δίνει μια μεγαλύτερη εικόνα:

Ας ξεκινήσουμε επισημαίνοντας ότι η μέθοδος που συνήθως αναφέρεται ως «SVD» που χρησιμοποιείται στο πλαίσιο των συστάσεων δεν μιλά αυστηρά τη μαθηματική αποσύνθεση τιμής μιας μήτρας, αλλά μάλλον έναν κατά προσέγγιση τρόπο υπολογισμού της χαμηλής κατάταξης προσέγγισης του πίνακα ελαχιστοποιώντας την τετραγωνική απώλεια σφάλματος. Ένας πιο ακριβής, αν και πιο γενικός, τρόπος να το καλέσετε αυτό θα ήταν το Matrix Factorization. Η αρχική έκδοση αυτής της προσέγγισης στο πλαίσιο του Βραβείου Netflix παρουσιάστηκε από τον Simon Funk στο διάσημο ιστολόγιο του Try This at Home. Είναι σημαντικό να σημειωθεί ότι η προσέγγιση «αληθινή SVD» είχε πράγματι εφαρμοστεί στην ίδια εργασία χρόνια πριν, με όχι τόσο πρακτική επιτυχία.

Η Βικιπαίδεια έχει επίσης ανάλογες πληροφορίες στο άρθρο του Matrix factorization (Συστήματα σύστασης):

Ο αρχικός αλγόριθμος που πρότεινε ο Simon Funk στη δημοσίευση του ιστολογίου του παραμόρφωσε τον πίνακα βαθμολογίας χρήστη-στοιχείου ως προϊόν δύο πινάκων χαμηλότερης διάστασης, ο πρώτος έχει μια σειρά για κάθε χρήστη, ενώ ο δεύτερος έχει μια στήλη για κάθε στοιχείο. Η σειρά ή η στήλη που σχετίζεται με έναν συγκεκριμένο χρήστη ή στοιχείο αναφέρεται ως λανθάνων συντελεστών. Σημειώστε ότι, παρά το όνομά του, στο FunkSVD δεν εφαρμόζεται αποσύνθεση μοναδικής τιμής.

Να συνοψίσουμε:

1. Το SVD είναι μια κάπως περίπλοκη μαθηματική τεχνική που παραγοντοποιεί τους πίνακες μεταξύ τριών νέων πινάκων και έχει πολλές εφαρμογές, συμπεριλαμβανομένων των PCA και RS.

2. Ο Simon Funk εφάρμοσε μια πολύ έξυπνη στρατηγική στον διαγωνισμό του Netflix το 2006, παραγοντοποιώντας μια μήτρα σε δύο άλλες και χρησιμοποιώντας κλίση κλίσης για να βρει βέλτιστες τιμές των δυνατοτήτων και των βαρών. Δεν είναι SVD , αλλά χρησιμοποίησε τον όρο αυτό ούτως ή άλλως για να περιγράψει την τεχνική του.

3. Ο πιο κατάλληλος όρος για αυτό που έκανε ο Funk είναι το Matrix Factorization.

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

Ελπίζω ότι αυτό βοηθά να ξεκαθαρίσουμε λίγο τα πράγματα.