Πηγή:
Η γραμμική παλινδρόμηση είναι ένας από τους βασικούς αλγόριθμους για πολλούς τομείς που σχετίζονται με την ανάλυση δεδομένων. Ο λόγος για αυτό είναι προφανής. Πρόκειται για έναν πολύ απλό και κατανοητό αλγόριθμο, ο οποίος έχει συμβάλει στην ευρεία χρήση του εδώ και πολλές δεκάδες, αν όχι εκατοντάδες χρόνια. Η ιδέα είναι ότι υποθέτουμε μια γραμμική εξάρτηση μιας μεταβλητής από ένα σύνολο άλλων μεταβλητών και στη συνέχεια προσπαθούμε να αποκαταστήσουμε αυτήν την εξάρτηση.
Αλλά αυτό το άρθρο δεν αφορά τη χρήση γραμμικής παλινδρόμησης για την επίλυση πρακτικών προβλημάτων. Εδώ θα εξετάσουμε ενδιαφέροντα χαρακτηριστικά της υλοποίησης κατανεμημένων αλγορίθμων για την ανάκτησή του, τα οποία συναντήσαμε κατά τη σύνταξη μιας ενότητας μηχανικής μάθησης στο . Λίγα βασικά μαθηματικά, η μηχανική μάθηση και ο κατανεμημένος υπολογισμός μπορούν να σας βοηθήσουν να καταλάβετε πώς να εκτελέσετε γραμμική παλινδρόμηση ακόμα και όταν τα δεδομένα σας διανέμονται σε χιλιάδες κόμβους.
Για τι πράγμα μιλάμε?
Είμαστε αντιμέτωποι με το καθήκον της αποκατάστασης της γραμμικής εξάρτησης. Ως δεδομένα εισόδου, δίνεται ένα σύνολο διανυσμάτων υποτιθέμενων ανεξάρτητων μεταβλητών, καθεμία από τις οποίες σχετίζεται με μια ορισμένη τιμή της εξαρτημένης μεταβλητής. Αυτά τα δεδομένα μπορούν να αναπαρασταθούν με τη μορφή δύο πινάκων:
Τώρα, δεδομένου ότι η εξάρτηση υποτίθεται και, επιπλέον, γραμμική, θα γράψουμε την υπόθεσή μας με τη μορφή ενός γινόμενου πινάκων (για να απλοποιήσουμε την καταγραφή, εδώ και παρακάτω υποτίθεται ότι ο ελεύθερος όρος της εξίσωσης κρύβεται πίσω από , και την τελευταία στήλη του πίνακα περιέχει μονάδες):
Ακούγεται πολύ σαν ένα σύστημα γραμμικών εξισώσεων, έτσι δεν είναι; Φαίνεται, αλλά πιθανότατα δεν θα υπάρξουν λύσεις σε ένα τέτοιο σύστημα εξισώσεων. Ο λόγος για αυτό είναι ο θόρυβος, ο οποίος υπάρχει σχεδόν σε όλα τα πραγματικά δεδομένα. Ένας άλλος λόγος μπορεί να είναι η απουσία γραμμικής εξάρτησης αυτή καθαυτή, η οποία μπορεί να καταπολεμηθεί με την εισαγωγή πρόσθετων μεταβλητών που εξαρτώνται μη γραμμικά από τις αρχικές. Εξετάστε το ακόλουθο παράδειγμα:
Πηγή:
Αυτό είναι ένα απλό παράδειγμα γραμμικής παλινδρόμησης που δείχνει τη σχέση μιας μεταβλητής (κατά μήκος του άξονα ) από άλλη μεταβλητή (κατά μήκος του άξονα ). Για να έχει λύση το σύστημα γραμμικών εξισώσεων που αντιστοιχούν σε αυτό το παράδειγμα, όλα τα σημεία πρέπει να βρίσκονται ακριβώς στην ίδια ευθεία. Αλλά αυτό δεν είναι αλήθεια. Αλλά δεν βρίσκονται στην ίδια ευθεία ακριβώς λόγω θορύβου (ή επειδή η υπόθεση μιας γραμμικής σχέσης ήταν λανθασμένη). Έτσι, για να αποκατασταθεί μια γραμμική σχέση από πραγματικά δεδομένα, είναι συνήθως απαραίτητο να εισαχθεί μια ακόμη υπόθεση: τα δεδομένα εισόδου περιέχουν θόρυβο και αυτός ο θόρυβος έχει . Μπορείτε να κάνετε υποθέσεις σχετικά με άλλους τύπους διανομής θορύβου, αλλά στη συντριπτική πλειοψηφία των περιπτώσεων εξετάζεται η κανονική κατανομή, η οποία θα συζητηθεί περαιτέρω.
Μέθοδος μέγιστης πιθανότητας
Έτσι, υποθέσαμε την παρουσία τυχαίου κανονικά κατανεμημένου θορύβου. Τι να κάνετε σε μια τέτοια κατάσταση; Για αυτή την περίπτωση στα μαθηματικά υπάρχει και χρησιμοποιείται ευρέως . Με λίγα λόγια, η ουσία του βρίσκεται στην επιλογή και την επακόλουθη μεγιστοποίησή του.
Επιστρέφουμε στην αποκατάσταση μιας γραμμικής σχέσης από δεδομένα με κανονικό θόρυβο. Σημειώστε ότι η υποτιθέμενη γραμμική σχέση είναι η μαθηματική προσδοκία υπάρχουσα κανονική κατανομή. Ταυτόχρονα, η πιθανότητα ότι παίρνει τη μία ή την άλλη αξία, με την επιφύλαξη της παρουσίας παρατηρήσιμων στοιχείων , ως εξής:
Ας αντικαταστήσουμε τώρα и Οι μεταβλητές που χρειαζόμαστε είναι:
Το μόνο που μένει είναι να βρούμε το διάνυσμα , στην οποία αυτή η πιθανότητα είναι μέγιστη. Για να μεγιστοποιήσετε μια τέτοια συνάρτηση, είναι βολικό να λάβετε πρώτα έναν λογάριθμό της (ο λογάριθμος της συνάρτησης θα φτάσει στο μέγιστο στο ίδιο σημείο με την ίδια τη συνάρτηση):
Το οποίο, με τη σειρά του, καταλήγει στην ελαχιστοποίηση της ακόλουθης συνάρτησης:
Παρεμπιπτόντως, αυτό ονομάζεται μέθοδος . Συχνά όλες οι παραπάνω σκέψεις παραλείπονται και αυτή η μέθοδος χρησιμοποιείται απλώς.
Αποσύνθεση QR
Το ελάχιστο της παραπάνω συνάρτησης μπορεί να βρεθεί βρίσκοντας το σημείο στο οποίο η κλίση αυτής της συνάρτησης είναι μηδέν. Και η κλίση θα γραφτεί ως εξής:
είναι μια μέθοδος πίνακα για την επίλυση του προβλήματος ελαχιστοποίησης που χρησιμοποιείται στη μέθοδο των ελαχίστων τετραγώνων. Από αυτή την άποψη, ξαναγράφουμε την εξίσωση σε μορφή πίνακα:
Έτσι αποσυνθέτουμε τη μήτρα σε πίνακες и και εκτελέστε μια σειρά μετασχηματισμών (ο ίδιος ο αλγόριθμος αποσύνθεσης QR δεν θα ληφθεί υπόψη εδώ, παρά μόνο η χρήση του σε σχέση με την εργασία που έχετε):
μήτρα είναι ορθογώνιο. Αυτό μας επιτρέπει να απαλλαγούμε από τη δουλειά :
Και αν αντικαταστήσετε επί , τότε θα λειτουργήσει . Λαμβάνοντας υπ 'όψιν ότι είναι ένας ανώτερος τριγωνικός πίνακας, μοιάζει με αυτό:
Αυτό μπορεί να λυθεί χρησιμοποιώντας τη μέθοδο αντικατάστασης. Στοιχείο βρίσκεται ως , προηγούμενο στοιχείο βρίσκεται ως και ούτω καθεξής.
Αξίζει να σημειωθεί εδώ ότι η πολυπλοκότητα του αλγορίθμου που προκύπτει λόγω της χρήσης της αποσύνθεσης QR είναι ίση με . Επιπλέον, παρά το γεγονός ότι η λειτουργία πολλαπλασιασμού του πίνακα είναι καλά παραλληλισμένη, δεν είναι δυνατό να γραφτεί μια αποτελεσματική κατανεμημένη έκδοση αυτού του αλγορίθμου.
Gradient Descent
Όταν μιλάμε για ελαχιστοποίηση μιας συνάρτησης, αξίζει πάντα να θυμόμαστε τη μέθοδο της (στοχαστικής) κλίσης κάθοδος. Αυτή είναι μια απλή και αποτελεσματική μέθοδος ελαχιστοποίησης που βασίζεται στον επαναληπτικό υπολογισμό της διαβάθμισης μιας συνάρτησης σε ένα σημείο και στη συνέχεια στη μετατόπισή της προς την αντίθετη κατεύθυνση από τη διαβάθμιση. Κάθε τέτοιο βήμα φέρνει τη λύση πιο κοντά στο ελάχιστο. Η κλίση εξακολουθεί να φαίνεται η ίδια:
Αυτή η μέθοδος είναι επίσης καλά παραλληλισμένη και κατανεμημένη λόγω των γραμμικών ιδιοτήτων του τελεστή κλίσης. Σημειώστε ότι στον παραπάνω τύπο, κάτω από το πρόσημο του αθροίσματος υπάρχουν ανεξάρτητοι όροι. Με άλλα λόγια, μπορούμε να υπολογίσουμε τη διαβάθμιση ανεξάρτητα για όλους τους δείκτες από την πρώτη έως , παράλληλα με αυτό, υπολογίστε την κλίση για τους δείκτες με να . Στη συνέχεια, προσθέστε τις προκύπτουσες διαβαθμίσεις. Το αποτέλεσμα της πρόσθεσης θα είναι το ίδιο σαν να υπολογίζαμε αμέσως τη διαβάθμιση για τους δείκτες από το πρώτο έως . Έτσι, εάν τα δεδομένα κατανέμονται μεταξύ πολλών τμημάτων δεδομένων, η διαβάθμιση μπορεί να υπολογιστεί ανεξάρτητα σε κάθε κομμάτι και στη συνέχεια τα αποτελέσματα αυτών των υπολογισμών μπορούν να αθροιστούν για να ληφθεί το τελικό αποτέλεσμα:
Από άποψη εφαρμογής, αυτό ταιριάζει στο παράδειγμα . Σε κάθε βήμα της κάθοδος διαβάθμισης, αποστέλλεται μια εργασία σε κάθε κόμβο δεδομένων για τον υπολογισμό της διαβάθμισης, στη συνέχεια οι υπολογισμένες διαβαθμίσεις συλλέγονται μαζί και το αποτέλεσμα του αθροίσματος τους χρησιμοποιείται για τη βελτίωση του αποτελέσματος.
Παρά την ευκολία υλοποίησης και την ικανότητα εκτέλεσης στο παράδειγμα MapReduce, η gradient descent έχει επίσης τα μειονεκτήματά της. Συγκεκριμένα, ο αριθμός των βημάτων που απαιτούνται για την επίτευξη σύγκλισης είναι σημαντικά υψηλότερος σε σύγκριση με άλλες πιο εξειδικευμένες μεθόδους.
LSQR
είναι μια άλλη μέθοδος για την επίλυση του προβλήματος, η οποία είναι κατάλληλη τόσο για την αποκατάσταση της γραμμικής παλινδρόμησης όσο και για την επίλυση συστημάτων γραμμικών εξισώσεων. Το κύριο χαρακτηριστικό του είναι ότι συνδυάζει τα πλεονεκτήματα των μεθόδων matrix και μια επαναληπτική προσέγγιση. Εφαρμογές αυτής της μεθόδου μπορούν να βρεθούν και στις δύο βιβλιοθήκες , και στο . Μια περιγραφή αυτής της μεθόδου δεν θα δοθεί εδώ (μπορεί να βρεθεί στο άρθρο ). Αντίθετα, θα παρουσιαστεί μια προσέγγιση για την προσαρμογή του LSQR στην εκτέλεση σε ένα κατανεμημένο περιβάλλον.
Η μέθοδος LSQR βασίζεται σε . Αυτή είναι μια επαναληπτική διαδικασία, κάθε επανάληψη αποτελείται από τα ακόλουθα βήματα:
Αν όμως υποθέσουμε ότι η μήτρα είναι οριζόντια διαμερισμένη, τότε κάθε επανάληψη μπορεί να αναπαρασταθεί ως δύο βήματα MapReduce. Με αυτόν τον τρόπο, είναι δυνατό να ελαχιστοποιηθούν οι μεταφορές δεδομένων κατά τη διάρκεια κάθε επανάληψης (μόνο διανύσματα με μήκος ίσο με τον αριθμό των αγνώστων):
Είναι αυτή η προσέγγιση που χρησιμοποιείται κατά την εφαρμογή της γραμμικής παλινδρόμησης σε .
Συμπέρασμα
Υπάρχουν πολλοί αλγόριθμοι ανάκτησης γραμμικής παλινδρόμησης, αλλά δεν μπορούν να εφαρμοστούν όλοι σε όλες τις συνθήκες. Έτσι, η αποσύνθεση QR είναι εξαιρετική για ακριβή λύση σε μικρά σύνολα δεδομένων. Το gradient descent είναι απλό στην εφαρμογή και σας επιτρέπει να βρείτε γρήγορα μια κατά προσέγγιση λύση. Και το LSQR συνδυάζει τις καλύτερες ιδιότητες των δύο προηγούμενων αλγορίθμων, καθώς μπορεί να διανεμηθεί, συγκλίνει γρηγορότερα σε σύγκριση με το gradient descent και επίσης επιτρέπει την πρώιμη διακοπή του αλγορίθμου, σε αντίθεση με την αποσύνθεση QR, για να βρεθεί μια κατά προσέγγιση λύση.
Πηγή: www.habr.com