Orthogonal Matching Pursuit (OMP)

Ενημέρωση 2020-07-01 Ανάγνωση 3 λεπτά

Σύνοψη

Ο αλγόριθμος 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 σε δεδομένα με αραιό διάνυσμα πραγματικών συντελεστών.

from __future__ import annotations

import japanize_matplotlib
import matplotlib.pyplot as plt
import numpy as np
from sklearn.linear_model import Lasso, OrthogonalMatchingPursuit
from sklearn.metrics import mean_squared_error

def run_omp_vs_lasso(
    n_samples: int = 200,
    n_features: int = 40,
    sparsity: int = 4,
    noise_scale: float = 0.5,
    xlabel: str = "feature index",
    ylabel: str = "coefficient",
    label_true: str = "true",
    label_omp: str = "OMP",
    label_lasso: str = "Lasso",
    title: str | None = None,
) -> dict[str, object]:
    """Compare OMP and lasso on synthetic sparse regression data.

    Args:
        n_samples: Number of training samples to generate.
        n_features: Total number of features in the dictionary.
        sparsity: Count of non-zero coefficients in the ground truth.
        noise_scale: Standard deviation of Gaussian noise added to targets.
        xlabel: Label for the coefficient plot x-axis.
        ylabel: Label for the coefficient plot y-axis.
        label_true: Legend label for the ground-truth bars.
        label_omp: Legend label for the OMP bars.
        label_lasso: Legend label for the lasso bars.
        title: Optional title for the bar chart.

    Returns:
        Dictionary containing recovered supports and MSE values.
    """
    japanize_matplotlib.japanize()
    rng = np.random.default_rng(0)

    X = rng.normal(size=(n_samples, n_features))
    true_coef = np.zeros(n_features)
    true_support = rng.choice(n_features, size=sparsity, replace=False)
    true_coef[true_support] = rng.normal(loc=0.0, scale=3.0, size=sparsity)
    y = X @ true_coef + rng.normal(scale=noise_scale, size=n_samples)

    omp = OrthogonalMatchingPursuit(n_nonzero_coefs=sparsity)
    omp.fit(X, y)
    lasso = Lasso(alpha=0.05)
    lasso.fit(X, y)

    omp_pred = omp.predict(X)
    lasso_pred = lasso.predict(X)

    fig, ax = plt.subplots(figsize=(10, 5))
    indices = np.arange(n_features)
    ax.bar(indices - 0.3, true_coef, width=0.2, label=label_true, color="#2ca02c")
    ax.bar(indices, omp.coef_, width=0.2, label=label_omp, color="#1f77b4")
    ax.bar(indices + 0.3, lasso.coef_, width=0.2, label=label_lasso, color="#d62728")
    ax.set_xlabel(xlabel)
    ax.set_ylabel(ylabel)
    if title:
        ax.set_title(title)
    ax.legend()
    fig.tight_layout()
    plt.show()

    return {
        "true_support": np.flatnonzero(true_coef),
        "omp_support": np.flatnonzero(omp.coef_),
        "lasso_support": np.flatnonzero(np.abs(lasso.coef_) > 1e-6),
        "omp_mse": float(mean_squared_error(y, omp_pred)),
        "lasso_mse": float(mean_squared_error(y, lasso_pred)),
    }

metrics = run_omp_vs_lasso()
print("True support:", metrics['true_support'])
print("OMP support:", metrics['omp_support'])
print("Lasso support:", metrics['lasso_support'])
print(f"OMP MSE: {metrics['omp_mse']:.4f}")
print(f"Lasso MSE: {metrics['lasso_mse']:.4f}")

Ερμηνεία αποτελεσμάτων #

Η ρύθμιση του 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.