Tight Lower Bounds on Worst-Case Guarantees for Zero-Shot Learning with Attributes

• URL: http://arxiv.org/abs/2205.13068v1
• Date: Wed, 25 May 2022 22:30:33 GMT
• Title: Tight Lower Bounds on Worst-Case Guarantees for Zero-Shot Learning with Attributes
• Authors: Alessio Mazzetto, Cristina Menghini, Andrew Yuan, Eli Upfal, Stephen H. Bach
• Abstract summary: We develop a rigorous analysis of zero-shot learning with attributes. We show that our analysis can be predictive of how standard zero-shot methods behave in practice.
• Score: 12.022775363029218
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We develop a rigorous mathematical analysis of zero-shot learning with attributes. In this setting, the goal is to label novel classes with no training data, only detectors for attributes and a description of how those attributes are correlated with the target classes, called the class-attribute matrix. We develop the first non-trivial lower bound on the worst-case error of the best map from attributes to classes for this setting, even with perfect attribute detectors. The lower bound characterizes the theoretical intrinsic difficulty of the zero-shot problem based on the available information -- the class-attribute matrix -- and the bound is practically computable from it. Our lower bound is tight, as we show that we can always find a randomized map from attributes to classes whose expected error is upper bounded by the value of the lower bound. We show that our analysis can be predictive of how standard zero-shot methods behave in practice, including which classes will likely be confused with others.

Related papers

• Causal Effect Regularization: Automated Detection and Removal of Spurious Attributes [13.852987916253685]
  In many classification datasets, the task labels are spuriously correlated with some input attributes. We propose a method to automatically identify spurious attributes by estimating their causal effect on the label. Our method mitigates the reliance on spurious attributes even under noisy estimation of causal effects.
  arXiv  Detail & Related papers  (2023-06-19T17:17:42Z)
• Exploiting Semantic Attributes for Transductive Zero-Shot Learning [97.61371730534258]
  Zero-shot learning aims to recognize unseen classes by generalizing the relation between visual features and semantic attributes learned from the seen classes. We present a novel transductive ZSL method that produces semantic attributes of the unseen data and imposes them on the generative process. Experiments on five standard benchmarks show that our method yields state-of-the-art results for zero-shot learning.
  arXiv  Detail & Related papers  (2023-03-17T09:09:48Z)
• Characterizing the Optimal 0-1 Loss for Multi-class Classification with a Test-time Attacker [57.49330031751386]
  We find achievable information-theoretic lower bounds on loss in the presence of a test-time attacker for multi-class classifiers on any discrete dataset. We provide a general framework for finding the optimal 0-1 loss that revolves around the construction of a conflict hypergraph from the data and adversarial constraints.
  arXiv  Detail & Related papers  (2023-02-21T15:17:13Z)
• Polar Encoding: A Simple Baseline Approach for Classification with Missing Values [1.7205106391379026]
  polar encoding is a representation of $[0,1]$-valued attributes with missing values. It does not require imputation, ensures that missing values are equidistant from non-missing values, and lets decision tree algorithms choose how to split missing values. We show that, in terms of the resulting classification performance, polar encoding performs better than the state-of-the-art strategies "multiple imputation by chained equations" and "multiple imputation with denoising autoencoders"
  arXiv  Detail & Related papers  (2022-10-04T20:56:24Z)
• Spread Spurious Attribute: Improving Worst-group Accuracy with Spurious Attribute Estimation [72.92329724600631]
  We propose a pseudo-attribute-based algorithm, coined Spread Spurious Attribute, for improving the worst-group accuracy. Our experiments on various benchmark datasets show that our algorithm consistently outperforms the baseline methods. We also demonstrate that the proposed SSA can achieve comparable performances to methods using full (100%) spurious attribute supervision.
  arXiv  Detail & Related papers  (2022-04-05T09:08:30Z)
• Make an Omelette with Breaking Eggs: Zero-Shot Learning for Novel Attribute Synthesis [65.74825840440504]
  We propose Zero Shot Learning for Attributes (ZSLA), which is the first of its kind to the best of our knowledge. Our proposed method is able to synthesize the detectors of novel attributes in a zero-shot learning manner. With using only 32 seen attributes on the Caltech-UCSD Birds-200-2011 dataset, our proposed method is able to synthesize other 207 novel attributes.
  arXiv  Detail & Related papers  (2021-11-28T15:45:54Z)
• Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures [100.55816326422773]
  We study the phenomenon of the maximum margin classifier for linear classification problems. Our results precisely characterize the condition under which benign overfitting can occur.
  arXiv  Detail & Related papers  (2021-04-28T08:25:16Z)
• Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View [82.80085730891126]
  We provide the first modernally precise analysis of linear multiclass classification. Our analysis reveals that the classification accuracy is highly distribution-dependent. The insights gained may pave the way for a precise understanding of other classification algorithms.
  arXiv  Detail & Related papers  (2020-11-16T05:17:29Z)
• Explaining Predictions by Approximating the Local Decision Boundary [3.60160227126201]
  We present a new procedure for local decision boundary approximation (DBA) We train a variational autoencoder to learn a Euclidean latent space of encoded data representations. We exploit attribute annotations to map the latent space to attributes that are meaningful to the user.
  arXiv  Detail & Related papers  (2020-06-14T19:12:42Z)

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.