Discussion of: Treelets—An adaptive multi-scale basis for sparse unordered data

Peter J. Bickel, Ya’acov RitovThe Annals of Applied Statistics 2008 · DOI

TL;DR

This paper discusses "Treelets," a novel adaptive multi-scale basis for analyzing sparse, unordered data. The authors critically examine its application in unsupervised learning (data representation) and supervised learning (linear regression), highlighting both its potential and limitations compared to existing methods like sparse PCA.

What Problem Does This Paper Address?

The paper addresses the challenge of effectively representing and analyzing high-dimensional data where the underlying structure is sparse and the order of observations might be arbitrary (unordered). Traditional methods often assume a fixed basis or ordered data, which can fail to capture the true underlying patterns. The authors specifically discuss how "Treelets," an adaptive basis construction method, performs in two key scenarios: unsupervised learning (finding structure in data without a target variable) and supervised learning (predicting a target variable from other variables).

Methods

The authors discuss "Treelets" as an adaptive basis construction method. In unsupervised learning, they relate it to wavelet representations but for permuted time points. They introduce a model where data is represented as a sum of unobservable vectors scaled by fixed unknown vectors, plus Gaussian noise. In supervised learning, they consider a linear regression setting and discuss how Treelets can be used for variable selection. They also compare Treelets to other sparse PCA methods and discuss a potential alternative approach that directly models the factor loadings.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Treelets as a Clustering Tool: The authors suggest that Treelets can be viewed as a clustering method, providing reasonable answers in their examples for data representation.
  • Identifiability Issues: A significant concern raised is the identifiability of the underlying population structure when the data is assumed to be Gaussian. The authors argue that the tree structure might not be uniquely identifiable in such cases, similar to issues in factor analysis.
  • Theoretical Burden: The authors emphasize the need for theoretical justification for using Treelets over other sparse PCA methods, especially for covariance matrices where eigenvectors have disjoint support.
  • Goal of Treelets: They question the authors' statement that inferring the tree structure (T(Σ)) is not the goal, suggesting that if it's not the goal, then the purpose of the method needs clearer definition.
  • Supervised Learning Nuances: In supervised learning, they note that while the tempting answer to variable selection is "yes" (e.g., using PCA), the theoretical answer is "no," and the practical answer is a cautious "yes."
  • LASSO vs. Treelets: They discuss that LASSO handles sparsity in a given basis, but a sparse representation might exist in another basis, which Treelets aim to address by providing a richer collection of vectors.
  • Algorithmic Complexity: The Treelets algorithm's serial optimization approach is compared to standard model selection methods, with a question raised about why variables are selected from one level rather than their union.
  • Model Limitations: The authors point out that the restriction to a basis of a relatively small collection of transform variables can be a limitation.

Key Results

  • In unsupervised learning, Treelets can provide reasonable answers for data representation, analogous to clustering.
  • The authors conjecture that if the number of predictors and samples grow large, and the factor loadings are sparse, their proposed alternative method can recover the underlying structure up to scale and permutation.
  • For a specific errors-in-variables model, simulations suggest that while PCA might perform better for smaller values of a key parameter (Cp), Treelets work surprisingly well for larger values.

Limitations and Future Work

  • Identifiability: The paper highlights concerns about the identifiability of the population tree structure, particularly when assuming Gaussian data.
  • Theoretical Justification: The authors call for more theoretical work to demonstrate when Treelets are superior to other sparse PCA methods, especially for certain classes of covariance matrices.
  • Unclear Goal: The precise goal of inferring the tree structure (T(Σ)) needs further clarification.
  • Algorithmic Choices: Questions are raised about the specific variable selection strategy within the Treelets algorithm.
  • Basis Restriction: The limitation of relying on a small collection of transform variables is acknowledged.
  • Future Work: The authors mention ongoing work on their conjecture regarding recovering sparse factor loadings in a high-dimensional setting. They also suggest that a general methodology for constructing rich collections of basis functions is needed.

Summary updated

Abstract

We divide our comments on this very interesting paper into two parts following its own structure:
BibTeX
@article{bickel2008discussion,
  author = {Peter J. Bickel and Ya’acov Ritov},
  title = {{Discussion of: Treelets—An adaptive multi-scale basis for sparse unordered data}},
  journal = {The Annals of Applied Statistics},
  year = {2008},
  doi = {10.1214/08-aoas137b},
}
Figure