Estimating the Hessian Matrix of Ranking Objectives for Stochastic Learning to Rank with Gradient Boosted Trees

• URL: http://arxiv.org/abs/2404.12190v2
• Date: Thu, 9 May 2024 10:07:47 GMT
• Title: Estimating the Hessian Matrix of Ranking Objectives for Stochastic Learning to Rank with Gradient Boosted Trees
• Authors: Jingwei Kang, Maarten de Rijke, Harrie Oosterhuis,
• Abstract summary: We introduce the first learning to rank method for Gradient Boosted Decision Trees (GBDTs) Our main contribution is a novel estimator for the second-order derivatives, i.e., the Hessian matrix. We incorporate our estimator into the existing PL-Rank framework, which was originally designed for first-order derivatives only.
• Score: 63.18324983384337
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Stochastic learning to rank (LTR) is a recent branch in the LTR field that concerns the optimization of probabilistic ranking models. Their probabilistic behavior enables certain ranking qualities that are impossible with deterministic models. For example, they can increase the diversity of displayed documents, increase fairness of exposure over documents, and better balance exploitation and exploration through randomization. A core difficulty in LTR is gradient estimation, for this reason, existing stochastic LTR methods have been limited to differentiable ranking models (e.g., neural networks). This is in stark contrast with the general field of LTR where Gradient Boosted Decision Trees (GBDTs) have long been considered the state-of-the-art. In this work, we address this gap by introducing the first stochastic LTR method for GBDTs. Our main contribution is a novel estimator for the second-order derivatives, i.e., the Hessian matrix, which is a requirement for effective GBDTs. To efficiently compute both the first and second-order derivatives simultaneously, we incorporate our estimator into the existing PL-Rank framework, which was originally designed for first-order derivatives only. Our experimental results indicate that stochastic LTR without the Hessian has extremely poor performance, whilst the performance is competitive with the current state-of-the-art with our estimated Hessian. Thus, through the contribution of our novel Hessian estimation method, we have successfully introduced GBDTs to stochastic LTR.

Related papers

• Ranking-based Adaptive Query Generation for DETRs in Crowded Pedestrian Detection [49.27380156754935]
  We find that the number of DETRs' queries must be adjusted manually, otherwise, the performance would degrade to varying degrees. We propose Rank-based Adaptive Query Generation (RAQG) to alleviate the problem. Our method is simple and effective, which can be plugged into any DETRs to make it query-adaptive in theory.
  arXiv  Detail & Related papers  (2023-10-24T11:00:56Z)
• Inference-time Stochastic Ranking with Risk Control [19.20938164194589]
  Learning to Rank methods are vital in online economies, affecting users and item providers. We propose a novel method that performs ranking at inference time with guanranteed utility or fairness given pretrained scoring functions.
  arXiv  Detail & Related papers  (2023-06-12T15:44:58Z)
• Enhancing Few-shot NER with Prompt Ordering based Data Augmentation [59.69108119752584]
  We propose a Prompt Ordering based Data Augmentation (PODA) method to improve the training of unified autoregressive generation frameworks. Experimental results on three public NER datasets and further analyses demonstrate the effectiveness of our approach.
  arXiv  Detail & Related papers  (2023-05-19T16:25:43Z)
• Safe Deployment for Counterfactual Learning to Rank with Exposure-Based Risk Minimization [63.93275508300137]
  We introduce a novel risk-aware Counterfactual Learning To Rank method with theoretical guarantees for safe deployment. Our experimental results demonstrate the efficacy of our proposed method, which is effective at avoiding initial periods of bad performance when little data is available.
  arXiv  Detail & Related papers  (2023-04-26T15:54:23Z)
• Training Discrete Deep Generative Models via Gapped Straight-Through Estimator [72.71398034617607]
  We propose a Gapped Straight-Through ( GST) estimator to reduce the variance without incurring resampling overhead. This estimator is inspired by the essential properties of Straight-Through Gumbel-Softmax. Experiments demonstrate that the proposed GST estimator enjoys better performance compared to strong baselines on two discrete deep generative modeling tasks.
  arXiv  Detail & Related papers  (2022-06-15T01:46:05Z)
• Distributionally Robust Models with Parametric Likelihood Ratios [123.05074253513935]
  Three simple ideas allow us to train models with DRO using a broader class of parametric likelihood ratios. We find that models trained with the resulting parametric adversaries are consistently more robust to subpopulation shifts when compared to other DRO approaches.
  arXiv  Detail & Related papers  (2022-04-13T12:43:12Z)
• Doubly-Robust Estimation for Unbiased Learning-to-Rank from Position-Biased Click Feedback [13.579420996461439]
  We introduce a novel DR estimator that uses the expectation of treatment per rank instead of IPS estimation. Our results indicate it requires several orders of magnitude fewer datapoints to converge at optimal performance.
  arXiv  Detail & Related papers  (2022-03-31T15:38:25Z)
• Towards Flexible Sparsity-Aware Modeling: Automatic Tensor Rank Learning Using The Generalized Hyperbolic Prior [24.848237413017937]
  rank learning for canonical polyadic decomposition (CPD) has long been deemed as an essential yet challenging problem. The optimal determination of a tensor rank is known to be a non-deterministic-time hard (NP-hard) task. In this paper, we introduce a more advanced generalized hyperbolic (GH) prior to the probabilistic modeling model, which is more flexible to adapt to different levels of sparsity.
  arXiv  Detail & Related papers  (2020-09-05T06:07:21Z)
• Learning Rates as a Function of Batch Size: A Random Matrix Theory Approach to Neural Network Training [2.9649783577150837]
  We study the effect of mini-batching on the loss landscape of deep neural networks using spiked, field-dependent random matrix theory. We derive analytical expressions for the maximal descent and adaptive training regimens for smooth, non-Newton deep neural networks. We validate our claims on the VGG/ResNet and ImageNet datasets.
  arXiv  Detail & Related papers  (2020-06-16T11:55:45Z)
• Proximal Gradient Temporal Difference Learning: Stable Reinforcement Learning with Polynomial Sample Complexity [40.73281056650241]
  We introduce proximal gradient temporal difference learning, which provides a principled way of designing and analyzing true gradient temporal difference learning algorithms. We show how gradient TD reinforcement learning methods can be formally derived, not by starting from their original objective functions, as previously attempted, but rather from a primal-dual saddle-point objective function.
  arXiv  Detail & Related papers  (2020-06-06T21:04:21Z)

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.