Orthogonal Matching Pursuit (OMP)

Atualizado 2020-07-01 Leitura 4 min

Resumo

O Orthogonal Matching Pursuit (OMP) seleciona em cada etapa a variável mais correlacionada com o resíduo atual para construir um modelo linear esparso.
O algoritmo resolve um problema de mínimos quadrados restrito às variáveis selecionadas, mantendo os coeficientes interpretáveis.
Em vez de ajustar a força de regularização, você controla diretamente a esparsidade especificando o número de variáveis a manter.
A padronização das variáveis e a verificação de multicolinearidade ajudam o método a permanecer estável na recuperação de sinais esparsos.

Intuição #

Este método deve ser interpretado através de suas suposições, condições dos dados e como as escolhas de parâmetros afetam a generalização.

Explicação Detalhada #

Formulação Matemática #

Inicialize o resíduo como \(\mathbf{r}^{(0)} = \mathbf{y}\). Para cada iteração \(t\):

Calcule o produto interno entre cada variável \(\mathbf{x}_j\) e o resíduo \(\mathbf{r}^{(t-1)}\), e selecione a variável \(j\) com o maior valor absoluto.
Adicione \(j\) ao conjunto ativo \(\mathcal{A}_t\).
Resolva o problema de mínimos quadrados restrito a \(\mathcal{A}t\) para obter \(\hat{\boldsymbol\beta}{\mathcal{A}_t}\).
Atualize o resíduo \(\mathbf{r}^{(t)} = \mathbf{y} - \mathbf{X}_{\mathcal{A}t} \hat{\boldsymbol\beta}{\mathcal{A}_t}\).

Pare ao atingir a esparsidade desejada ou quando o resíduo for suficientemente pequeno.

Experimentos em Python #

O trecho abaixo compara OMP e Lasso em dados com um vetor de coeficientes verdadeiros esparso.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
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}")

Interpretação dos resultados #

Definir n_nonzero_coefs com a esparsidade verdadeira ajuda o OMP a recuperar de forma confiável as variáveis relevantes.
Em comparação com o Lasso, o OMP produz coeficientes exatamente zero para as variáveis não selecionadas.
Quando as variáveis são altamente correlacionadas, a ordem de seleção pode oscilar, portanto o pré-processamento e a engenharia de variáveis continuam sendo importantes.

Referências #

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.