TL;DR
This paper introduces a new class of multiresolution (MR) models that capture complex dependencies in data by combining sparse inter-scale graphical structures with sparse in-scale conditional covariance. This novel approach leads to more accurate modeling and significantly faster inference algorithms, particularly for data with long-range correlations.
What Problem Does This Paper Address?
Many real-world datasets exhibit hierarchical structures and dependencies that span multiple scales. Multiresolution (MR) models are designed to capture these by using coarser-scale variables to explain dependencies among finer-scale variables. Traditional MR models often rely on tree structures, which enforce conditional independence between variables at the same scale once their neighbors at coarser scales are known. This is a significant limitation, as it can miss important correlations within a scale (e.g., between two companies in the same industry but different branches of a hierarchical tree). Existing methods to address this often result in overly dense graphical models, hindering efficient inference. The paper aims to bridge this gap by developing MR models that explicitly capture sparse correlations within each scale, while maintaining efficient inference.
Methods
The core contribution is the Sparse In-scale Conditional Covariance Multiresolution (SIM) model. This model decomposes the information matrix (inverse covariance) into two parts:
- Sparse inter-scale structure ($J_h$): This represents the hierarchical connections between different scales, typically forming a tree structure.
- Sparse in-scale conditional covariance ($(\Sigma_c)^{-1}$): This captures the residual correlations within each scale, conditioned on variables at other scales. The key innovation is that this in-scale covariance is modeled as sparse, meaning only a few variables at the same scale are correlated with each other after accounting for coarser scales. This is represented using a "conjugate graph" where edges indicate conditional independence.
The paper also proposes an efficient inference algorithm for SIM models. It leverages a matrix splitting technique, alternating between:
- Tree Inference: Exploiting the sparse inter-scale tree structure for efficient computation.
- In-scale Inference: Exploiting the sparse in-scale conditional covariance structure for efficient updates within each scale.
For learning, the paper proposes a three-step procedure:
- Learn an initial MR tree model for the inter-scale structure.
- Compute a target information matrix that ensures the finest scale covariance matches the empirical data.
- Learn the sparse in-scale conditional covariances by solving a convex optimization problem (log-determinant maximization) for each scale independently.
Datasets
The paper evaluates its methods on three types of data:
- Stock Returns: Monthly returns of 84 companies from the S&P 100 index, using the Standard Industrial Classification (SIC) system for hierarchical structure.
- Fractional Brownian Motion (fBm): A synthetic dataset with known covariance properties, used to test the model's ability to capture long-range correlations.
- Polynomially Decaying Covariance for a 2-D Field: A synthetic dataset of 256 Gaussian variables arranged on a grid, designed to mimic processes with long-range correlations that are difficult for standard sparse models.
Key Insights and Ideas
- The "Aha!" Moment: The core insight is that while inter-scale dependencies might form a sparse tree, the residual dependencies within a scale (after conditioning on coarser scales) can also be sparse. This is a more nuanced view than simply assuming conditional independence at the same scale.
- Bridging the Gap: SIM models offer a principled way to model complex, non-tree-like dependencies within scales without resorting to dense graphical models, thus enabling efficient inference.
- Analogy to Physics: The inference algorithm is likened to multipole methods in computational physics, which use hierarchical decomposition to speed up calculations. This highlights the general applicability of the underlying principles.
- Conjugate Graphs: The introduction of "conjugate graphs" provides a clear visual and conceptual tool for understanding and representing the sparse in-scale conditional covariance structure.
Key Results
- Stock Returns: The SIM model achieved the smallest divergence (a measure of approximation accuracy) compared to single-scale, sparse MR, and tree-structured MR models. It also demonstrated a more natural representation of industry/company relationships.
- Fractional Brownian Motion (fBm): The SIM model's covariance approximation was close to the original, outperforming single-scale and tree models which exhibited blocky artifacts and failed to capture long-range correlations.
- Polynomially Decaying Covariance: The SIM model showed a significant gain in convergence rate for inference compared to single-scale, sparse MR, and tree models, and achieved a smaller divergence with fewer parameters than the sparse MR model.
- Inference Speed: The proposed inference algorithm for SIM models is significantly faster than standard methods for dense graphical models, achieving faster convergence rates.
Limitations and Future Work
- Gaussian Assumption: The current work focuses on Gaussian models. The authors suggest that applying similar principles to discrete models is a promising direction for future research.
- Learning Complexity: While the inference is efficient, the learning procedure involves solving convex optimization problems, which can still be computationally intensive for very large datasets, though generally more tractable than dense model learning.
- Heuristic Regularization Parameter: The regularization parameter in the learning step is chosen by a heuristic method, which could potentially be improved with more systematic approaches.
Summary updated