Learning (from) Deep Hierarchical Structure among Features

Yu Zhang, Lei HanAAAI 2019 · DOI

Abstract

This paper introduces Deep Hierarchical Structure (DHS), a novel framework for supervised learning designed to exploit complex, multi-layered relationships between data features. Unlike existing methods that are often restricted to shallow, two-level hierarchies, DHS accommodates structures of arbitrary depth while maintaining a convex objective function. Furthermore, the authors propose Learning Deep Hierarchical Structure (LDHS), an extension that can automatically discover the underlying hierarchical organization of features when it is not known a priori. Empirical evaluations on synthetic and real-world datasets demonstrate that DHS-based methods consistently outperform traditional regularization techniques like Lasso and Group Lasso.

Introduction

In many high-dimensional datasets, features are not independent but are instead organized into inherent hierarchies. For instance, genes function within nested biological pathways, and sensors in a traffic network are grouped by location and road type. While traditional regularization methods like the Group Lasso or Hierarchical Penalization (HP) attempt to incorporate such structures, they are typically limited to "shallow" hierarchies (usually height-2). Moreover, these methods often require the hierarchy to be predefined, which is a significant hurdle when the true structure is unknown or complex.

This research addresses these limitations by introducing a framework that supports deep hierarchies and provides a mechanism to learn these structures directly from data, breaking the "height-2" barrier in hierarchical feature selection.

Methodology

The proposed framework consists of three primary approaches:

1. Deep Hierarchical Structure (DHS)

DHS utilizes a known hierarchy of arbitrary height. It penalizes feature weights based on the product of edge weights along the path from the root to the leaf (feature). A key theoretical contribution is the proof that if the exponents of these edge weights sum to 1, the optimization problem remains convex. This allows for efficient global optimization using the Fast Iterative Soft-Thresholding Algorithm (FISTA).

Deep Hierarchical Structure notation and height levels.

2. DHSe (DHS with learned exponents)

DHSe is a variant of DHS that treats the exponents associated with different tree heights as learnable parameters. This allows the model to automatically determine the relative importance of different levels in the hierarchy.

3. Learning Deep Hierarchical Structure (LDHS)

LDHS is designed for scenarios where the hierarchical structure is unknown. It employs a layer-wise generalized fused-Lasso regularizer to encourage features to "fuse" at various heights. To ensure the resulting structure is a valid tree, LDHS enforces a sequential inequality constraint: if two features are fused at a level closer to the leaves, they must remain fused at all subsequent levels closer to the root.

Experimental Results

The researchers evaluated the proposed methods against standard baselines, including Lasso, Group Lasso (GLasso), and Hierarchical Penalization (HP), using both synthetic and real-world benchmarks.

Synthetic Data Performance

The models were tested on synthetic datasets generated from full binary trees of heights 3, 4, and 5. As shown in the table below, LDHS and DHS consistently achieved lower Mean Square Error (MSE) compared to traditional methods, with the performance gap often widening as the tree height increased.

Mean Square Error (MSE) comparison on synthetic data across different tree heights ($m$).

Real-World Benchmarks

  • Traffic Volume: DHS/LDHS outperformed baselines in 4 out of 5 prediction tasks involving 136 traffic sensors.
  • Breast Cancer Metastasis: On gene expression data from 295 tumors, the proposed methods demonstrated higher accuracy and sensitivity than Lasso or Group Lasso, effectively identifying relevant gene clusters.
  • Forest Cover Type (Covtype): In a large-scale classification task (over 580,000 examples), LDHS achieved the highest overall accuracy of 75.60%.

Conclusion

The DHS framework represents a significant advancement in hierarchical feature learning by enabling the use of deep structures and providing a robust method for structure discovery. While LDHS introduces non-convexity due to its sequential constraints, its ability to recover meaningful feature relationships makes it a powerful tool for interpretable machine learning in complex domains. Future work will focus on optimizing the computational efficiency of structure learning and integrating exponent-learning directly into the LDHS process.

Summary updated

BibTeX
@inproceedings{zhang2019learning,
  author = {Yu Zhang and Lei Han},
  title = {{Learning (from) Deep Hierarchical Structure among Features}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33015837},
}
Figure