2.1.12
Orthogonal Matching Pursuit (OMP)
Σύνοψη
- Ο αλγόριθμος Orthogonal Matching Pursuit (OMP) επιλέγει σε κάθε βήμα το χαρακτηριστικό με τη μεγαλύτερη συσχέτιση με το τρέχον υπόλοιπο, κατασκευάζοντας ένα αραιό γραμμικό μοντέλο.
- Ο αλγόριθμος λύνει ένα πρόβλημα ελαχίστων τετραγώνων περιορισμένο στα επιλεγμένα χαρακτηριστικά, διατηρώντας τους συντελεστές ερμηνεύσιμους.
- Αντί να ρυθμίζετε μια ισχύ κανονικοποίησης, ελέγχετε άμεσα την αραιότητα καθορίζοντας τον αριθμό χαρακτηριστικών που θα διατηρηθούν.
- Η τυποποίηση χαρακτηριστικών και ο έλεγχος πολυσυγγραμμικότητας βοηθούν τη μέθοδο να παραμένει σταθερή κατά την ανάκτηση αραιών σημάτων.
Εισαγωγή #
Αυτή η μέθοδος πρέπει να ερμηνεύεται μέσω των υποθέσεών της, των συνθηκών δεδομένων και του τρόπου με τον οποίο οι επιλογές παραμέτρων επηρεάζουν τη γενίκευση.
Αναλυτική Επεξήγηση #
Μαθηματική Διατύπωση #
Αρχικοποιήστε το υπόλοιπο ως \(\mathbf{r}^{(0)} = \mathbf{y}\). Για κάθε επανάληψη \(t\):
- Υπολογίστε το εσωτερικό γινόμενο μεταξύ κάθε χαρακτηριστικού \(\mathbf{x}_j\) και του υπολοίπου \(\mathbf{r}^{(t-1)}\), και επιλέξτε το χαρακτηριστικό \(j\) με τη μεγαλύτερη απόλυτη τιμή.
- Προσθέστε το \(j\) στο ενεργό σύνολο \(\mathcal{A}_t\).
- Λύστε το πρόβλημα ελαχίστων τετραγώνων περιορισμένο στο \(\mathcal{A}t\) για να λάβετε \(\hat{\boldsymbol\beta}{\mathcal{A}_t}\).
- Ενημερώστε το υπόλοιπο \(\mathbf{r}^{(t)} = \mathbf{y} - \mathbf{X}_{\mathcal{A}t} \hat{\boldsymbol\beta}{\mathcal{A}_t}\).
Σταματήστε μόλις φτάσετε στην επιθυμητή αραιότητα ή το υπόλοιπο γίνει αρκετά μικρό.
Πειράματα σε Python #
Το παρακάτω απόσπασμα κώδικα συγκρίνει τον OMP και τη μέθοδο Lasso σε δεδομένα με αραιό διάνυσμα πραγματικών συντελεστών.
| |
Ερμηνεία αποτελεσμάτων #
- Η ρύθμιση του
n_nonzero_coefsστην πραγματική αραιότητα βοηθά τον OMP να ανακτήσει αξιόπιστα τα σχετικά χαρακτηριστικά. - Σε σύγκριση με τη Lasso, ο OMP παράγει ακριβώς μηδενικούς συντελεστές για τα μη επιλεγμένα χαρακτηριστικά.
- Όταν τα χαρακτηριστικά είναι πολύ συσχετισμένα, η σειρά επιλογής μπορεί να διακυμανθεί, οπότε η προεπεξεργασία και η μηχανική χαρακτηριστικών παραμένουν σημαντικές.
Αναφορές #
- Pati, Y. C., Rezaiifar, R., & Krishnaprasad, P. S. (1993). Orthogonal Matching Pursuit: Recursive Function Approximation with Applications to Wavelet Decomposition. In Conference Record of the Twenty-Seventh Asilomar Conference on Signals, Systems and Computers.
- Tropp, J. A. (2004). Greed is Good: Algorithmic Results for Sparse Approximation. IEEE Transactions on Information Theory, 50(10), 2231–2242.