Source-linked AI summary
Ridge Regression, Hubness, and Zero-Shot Learning
Yutaro Shigeto, Ikumi Suzuki, Kazuo Hara, Masashi Shimbo, Yuji Matsumoto
TL;DR
Zero-shot learning can suffer from hub labels when ridge regression maps examples into label space, biasing subsequent nearest-neighbor prediction. This paper analyzes that mechanism and reverses the mapping direction; the proposed approach reduces hubness and outperforms existing regression- and CCA-based approaches, with limitations identified for broader distributions and methods.
Problem
The paper investigates how the regression step and subsequent nearest-neighbor search interact in ZSL, where conventional example-to-label ridge regression promotes hub labels and affects prediction accuracy.
Method
The paper analyzes hubness under a simple multivariate-normal model and uses ridge regression to map labels into example space instead of mapping examples into label space.
Results
The proposed RidgeY→X approach reduced hubness and outperformed existing regression-based and CCA-based ZSL approaches across the evaluated tasks.
Takeaways & Limitations
Reversing the mapping direction is a supported way to suppress hub labels in the subsequent nearest-neighbor step while improving ZSL prediction performance.
Takeaways & Limitations
The analysis remains to be extended to multimodal distributions and other similarity measures, and mapping-direction effects remain open for neural networks and CCA.
Abstract
from arXiv · showhide
This paper discusses the effect of hubness in zero-shot learning, when ridge regression is used to find a mapping between the example space to the label space. Contrary to the existing approach, which attempts to find a mapping from the example space to the label space, we show that mapping labels into the example space is desirable to suppress the emergence of hubs in the subsequent nearest neighbor search step. Assuming a simple data model, we prove that the proposed approach indeed reduces hubness. This was verified empirically on the tasks of bilingual lexicon extraction and image labeling: hubness was reduced with both of these tasks and the accuracy was improved accordingly.
1 Introduction
Zero-shot learning predicts labels absent from the training set by representing labels in a metric space and learning a regression-based mapping. This paper investigates how that mapping interacts with hubness and seeks to suppress hubs while improving accuracy.
- Motivation: Zero-shot learning predicts unknown labels for new examples, unlike standard classification, where test labels come from those observed during training.In ZSL, test labels are outside the training-label set.
- Motivation: Labels are embedded in a metric space so distances or similarities can support prediction.Label representations may use background knowledge or external resources, including vector representations of image-label keywords.
- Existing approach: A natural ZSL pipeline learns a regression mapping from examples to labels, then applies nearest-neighbor search in label space.The nearest label to the mapped example is output as the prediction.
- Problem: Hubness causes a small number of high-dimensional objects to become nearest neighbors for many queries, reducing nearest-neighbor utility.In ZSL, hub labels can bias predictions when examples are mapped into label space.
- Contribution: The paper analyzes hub emergence and proposes reversing the regression direction, mapping labels into example space to suppress hubs and improve ZSL accuracy.It attributes hubness partly to the conventional use of ridge regression and to differing mapped-example and label distributions.
2 Zero-Shot Learning as a Regression Problem
In zero-shot learning, examples and labels are vectors in source and target spaces, with test labels excluded from the training-label set. Regression projects new examples into target space for nearest-neighbor prediction.
- Representation: Examples and labels are represented as vectors in source and target spaces, respectively.The source space is Rc and the target space is Rd; the target-label set may be very large.
- Zero-shot setting: The training labels form a strict subset of all labels, and test examples have labels outside that training subset.This is the defining distinction from standard classification in the stated setup.
- Regression formulation: Because direct mapping from an example to an unseen label is difficult, ZSL learns a projection m: Rc → Rd using regression.The projection maps examples into the target space rather than directly selecting labels.
- Prediction: After projection, prediction becomes nearest-neighbor search in target space, with the closest label selected for the new example.The mapped point m(x) is compared against target-space labels.
3 Hubness Phenomenon and the Variance of Data
Hubness in nearest-neighbor search can arise from differences in object distributions and variance, not only dimensionality. The analysis compares query and data distributions and shows why variance and distance from the origin matter.
- Hubness: Hubness reduces nearest-neighbor utility when the same database objects repeatedly appear as results for different queries.High-dimensional spaces are known to produce hubs, which occur across real datasets and distance measures.
- Analytical setting: Existing hubness theory is inadequate for ZSL because it mainly compares spaces with different dimensionalities, whereas ZSL compares distributions in the same space.The paper therefore distinguishes query and data distributions and analyzes variance differences.
- Proposition: The proposition models target vectors as d-dimensional samples from N(0,s^2I) and measures expected differences between squared distances from a query to two target objects.The query has zero mean, while the compared target objects differ in squared norm by a standardized amount.
- Comparison scale: The standard deviation σ provides a common yardstick for comparing similarly located object pairs across distributions.Pairs are treated as similar when their separation is the same multiple γσ within their respective distributions.
- Mechanism: For a zero-mean query, an object closer to the origin is more likely to be nearer than an object farther from the origin.The expected squared-distance difference increases with the factor describing the target objects’ norm difference.
- Variance effect: For fixed query distributions, choosing a target distribution with smaller component variance is preferable for reducing hubness.The analysis compares Y1 = N(0,s1^2I) and Y2 = N(0,s2^2I) with s1^2 < s2^2.
4 Hubness in Regression-Based Zero-Shot Learning
The analysis shows that conventional ridge-regression ZSL promotes hubness by shrinking mapped examples toward the origin, while reversing the mapping direction is theoretically preferable for nearest-neighbor search. Under distributional assumptions, mapping target objects into source space yields a lower-variance configuration that is more likely to suppress hubs, though those assumptions do not describe real data.
- 4.2 Influence of Shrinkage on Nearest Neighbor Search: The proposed approach reverses the regression direction by projecting target objects into source space and searching for nearest neighbors there.In this configuration, mapped target objects are expected to be shorter than source objects, contrary to existing work.
- 4.1 Shrinkage of Projected Objects: Ridge regression and ordinary least squares shrink mapped observations toward the origin relative to response objects.This makes the mapped source objects tend to have smaller norms and lower variance along the principal axis than target responses.
- 4.1 Shrinkage of Projected Objects: In conventional ZSL, this shrinkage places projected source objects closer to the origin than target objects, a configuration associated with hubness.The regression objective does not explicitly account for the nearest-neighbor geometry needed to reduce hubs.
- 4.2 Influence of Shrinkage on Nearest Neighbor Search: Under isotropic normality, independence, equal dimensions, and variance-only shrinkage, the reversed configuration has a smaller effective target variance and is more likely to suppress hubs.Equal scaling preserves nearest-neighbor relations while allowing the two configurations to be compared under a common source-object distribution.
- 4.3 Additional Argument for Placing Target Objects Closer to the Origin: For radially decreasing densities, an object farther from the origin is more likely to be the nearest neighbor at equal distance from a query, supporting placement of source objects outside target objects.Proposition 3 formalizes this comparison through probability mass in equal-radius balls centered at the candidate objects.
- 4.4 Summary of the Proposed Approach: The theoretical argument relies on strong distributional assumptions such as normality, which do not apply to real data.The paper therefore relies on empirical verification with real data to assess the proposal outside those assumptions.
5 Related Work
Related work situates ridge regression, CCA, and neural mappings as approaches to zero-shot learning, while highlighting hubness reduction and structured-output alternatives.
- Ridge regression is a standard ZSL approach, especially in phrase generation and bilingual lexicon extraction, alongside newer neural mappings.
- Existing regression-based methods map source objects into the target space.
- CCA and kernelized CCA have been applied to image labeling, with CCA also used as a baseline in the paper’s experiments.
- Prior work reduced ZSL hubness through cosine-similarity reweighting and hubness-based instance weighting for CCA, under a different setting from this paper.
- Structured output learning addresses a similar setting with complex target objects, while kernel dependency estimation avoids explicit vector-space embedding through kernels.
6 Experiments
The experiments compare reverse-direction ridge regression with existing regression, CCA, and distance-based variants on synthetic and two real ZSL tasks. RidgeY→X achieved the strongest prediction results and lowest hubness across the tested tasks.
- Experimental tasks: The approach was tested on synthetic data, bilingual lexicon extraction across six source languages, and AwA image labeling.The bilingual task used English as the target language; the image task mapped images to word labels.
- Compared methods: The compared methods included RidgeX→Y, proposed RidgeY→X, and CCA, with Euclidean distance and selected NICDM combinations.Hyperparameters were calibrated by cross-validation on the training set.
- Evaluation criteria: The experiments evaluated prediction correctness and hubness using MAP, Acck, and Nk skewness.MAP and Acck assess ranking correctness; higher Nk skewness indicates stronger hub formation.
- Prediction results: RidgeY→X outperformed the other methods in both MAP and Acck across all tested tasks.RidgeX→Y and CCA improved with NICDM but still remained below RidgeY→X, even with NICDM.
- Hubness results: RidgeY→X produced lower Nk skewness than the compared methods, while RidgeX→Y produced high skewness alongside poor prediction accuracy.The results indicate effective suppression of hub labels and an inverse relationship between hubness and ranking correctness.
- Image-labeling comparison: RidgeY→X achieved 40.0% Acc1 on AwA in a setting comparable to a published 39.7% result.The setups were not exactly identical, so the values are not directly comparable.
7 Conclusion
The conclusion presents reverse-direction regression as a theoretically motivated alternative for reducing hubness in ZSL and reports that it outperformed existing regression- and CCA-based approaches. Future work would extend the analysis to broader distributions, distances, regression methods, and CCA.
- Conclusion: The paper formulates ZSL as mapping target objects into source space, contrary to existing regression-based formulations.The proposed direction is intended to address hub emergence in the subsequent nearest-neighbor search.
- Conclusion: Under a multivariate normal model, the analysis explains why the proposed mapping direction is preferable for hubness reduction.The conclusion ties the theoretical explanation to the emergence of hubs in nearest-neighbor search.
- Conclusion: The proposed approach outperformed existing regression-based and CCA-based ZSL approaches in the experiments.The conclusion states the empirical outcome at the paper level rather than reporting a task-specific metric.
- Future work: Future work includes multimodal distributions, alternative distances such as cosine, neural-network mapping directions, and hubness in CCA.These topics define the stated scope for extending the paper’s analysis.