Multi-group Learning for Hierarchical Groups

• URL: http://arxiv.org/abs/2402.00258v3
• Date: Wed, 12 Jun 2024 12:23:37 GMT
• Title: Multi-group Learning for Hierarchical Groups
• Authors: Samuel Deng, Daniel Hsu,
• Abstract summary: We extend the study of multi-group learning to the natural case where the groups are hierarchically structured. We design an algorithm for this setting that outputs an interpretable and deterministic decision tree predictor with near-optimal sample complexity.
• Score: 12.473780585666768
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The multi-group learning model formalizes the learning scenario in which a single predictor must generalize well on multiple, possibly overlapping subgroups of interest. We extend the study of multi-group learning to the natural case where the groups are hierarchically structured. We design an algorithm for this setting that outputs an interpretable and deterministic decision tree predictor with near-optimal sample complexity. We then conduct an empirical evaluation of our algorithm and find that it achieves attractive generalization properties on real datasets with hierarchical group structure.

Related papers

• Group-wise oracle-efficient algorithms for online multi-group learning [12.664869982542895]
  We study the problem of online multi-group learning, a learning model in which an online learner must simultaneously achieve small prediction regret on a large collection of subsequences corresponding to a family of groups. In this paper, we design such oracle-efficient algorithms with sublinear regret under a variety of settings, including adversarial and adversarial transductive settings.
  arXiv  Detail & Related papers  (2024-06-07T23:00:02Z)
• A structured regression approach for evaluating model performance across intersectional subgroups [53.91682617836498]
  Disaggregated evaluation is a central task in AI fairness assessment, where the goal is to measure an AI system's performance across different subgroups. We introduce a structured regression approach to disaggregated evaluation that we demonstrate can yield reliable system performance estimates even for very small subgroups.
  arXiv  Detail & Related papers  (2024-01-26T14:21:45Z)
• How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Model [47.617093812158366]
  We introduce the Random Hierarchy Model: a family of synthetic tasks inspired by the hierarchical structure of language and images. We find that deep networks learn the task by developing internal representations invariant to exchanging equivalent groups. Our results indicate how deep networks overcome the curse of dimensionality by building invariant representations.
  arXiv  Detail & Related papers  (2023-07-05T09:11:09Z)
• Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
  In this paper we offer a new perspective on the well established agglomerative clustering algorithm, focusing on recovery of hierarchical structure. We recommend a simple variant of the standard algorithm, in which clusters are merged by maximum average dot product and not, for example, by minimum distance or within-cluster variance. We demonstrate that the tree output by this algorithm provides a bona fide estimate of generative hierarchical structure in data, under a generic probabilistic graphical model.
  arXiv  Detail & Related papers  (2023-05-24T11:05:12Z)
• HiPerformer: Hierarchically Permutation-Equivariant Transformer for Time Series Forecasting [56.95572957863576]
  We propose a hierarchically permutation-equivariant model that considers both the relationship among components in the same group and the relationship among groups. The experiments conducted on real-world data demonstrate that the proposed method outperforms existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2023-05-14T05:11:52Z)
• Group conditional validity via multi-group learning [5.797821810358083]
  We consider the problem of distribution-free conformal prediction and the criterion of group conditional validity. Existing methods achieve such guarantees under either restrictive grouping structure or distributional assumptions. We propose a simple reduction to the problem of achieving validity guarantees for individual populations by leveraging algorithms for a problem called multi-group learning.
  arXiv  Detail & Related papers  (2023-03-07T15:51:03Z)
• Structurally Diverse Sampling Reduces Spurious Correlations in Semantic Parsing Datasets [51.095144091781734]
  We propose a novel algorithm for sampling a structurally diverse set of instances from a labeled instance pool with structured outputs. We show that our algorithm performs competitively with or better than prior algorithms in not only compositional template splits but also traditional IID splits. In general, we find that diverse train sets lead to better generalization than random training sets of the same size in 9 out of 10 dataset-split pairs.
  arXiv  Detail & Related papers  (2022-03-16T07:41:27Z)
• Natural Hierarchical Cluster Analysis by Nearest Neighbors with Near-Linear Time Complexity [0.0]
  We propose a nearest neighbor based clustering algorithm that results in a naturally defined hierarchy of clusters. In contrast to the agglomerative and divisive hierarchical clustering algorithms, our approach is not dependent on the iterative working of the algorithm.
  arXiv  Detail & Related papers  (2022-03-15T16:03:42Z)
• Simple and near-optimal algorithms for hidden stratification and multi-group learning [13.337579367787253]
  This paper studies the structure of solutions to the multi-group learning problem. It provides simple and near-optimal algorithms for the learning problem.
  arXiv  Detail & Related papers  (2021-12-22T19:16:24Z)
• Group Heterogeneity Assessment for Multilevel Models [68.95633278540274]
  Many data sets contain an inherent multilevel structure. Taking this structure into account is critical for the accuracy and calibration of any statistical analysis performed on such data. We propose a flexible framework for efficiently assessing differences between the levels of given grouping variables in the data.
  arXiv  Detail & Related papers  (2020-05-06T12:42:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.