rank_objective.hpp 7.97 KB
Newer Older
Guolin Ke's avatar
Guolin Ke committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#ifndef LIGHTGBM_OBJECTIVE_RANK_OBJECTIVE_HPP_
#define LIGHTGBM_OBJECTIVE_RANK_OBJECTIVE_HPP_

#include <LightGBM/objective_function.h>
#include <LightGBM/metric.h>

#include <cstdio>
#include <cstring>
#include <cmath>

#include <vector>
#include <algorithm>
#include <limits>

namespace LightGBM {
/*!
17
* \brief Objective function for Lambdrank with NDCG
Guolin Ke's avatar
Guolin Ke committed
18
19
20
21
*/
class LambdarankNDCG: public ObjectiveFunction {
public:
  explicit LambdarankNDCG(const ObjectiveConfig& config) {
22
    sigmoid_ = static_cast<double>(config.sigmoid);
Guolin Ke's avatar
Guolin Ke committed
23
24
25
    // initialize DCG calculator
    DCGCalculator::Init(config.label_gain);
    // copy lable gain to local
Guolin Ke's avatar
Guolin Ke committed
26
    for (auto gain : config.label_gain) {
27
      label_gain_.push_back(static_cast<double>(gain));
Guolin Ke's avatar
Guolin Ke committed
28
    }
Guolin Ke's avatar
Guolin Ke committed
29
    label_gain_.shrink_to_fit();
Guolin Ke's avatar
Guolin Ke committed
30
31
    // will optimize NDCG@optimize_pos_at_
    optimize_pos_at_ = config.max_position;
Guolin Ke's avatar
Guolin Ke committed
32
33
    sigmoid_table_.clear();
    inverse_max_dcgs_.clear();
Guolin Ke's avatar
Guolin Ke committed
34
    if (sigmoid_ <= 0.0) {
35
      Log::Fatal("Sigmoid param %f should be greater than zero", sigmoid_);
Guolin Ke's avatar
Guolin Ke committed
36
37
38
    }
  }
  ~LambdarankNDCG() {
Guolin Ke's avatar
Guolin Ke committed
39

Guolin Ke's avatar
Guolin Ke committed
40
41
42
43
44
45
46
47
48
49
  }
  void Init(const Metadata& metadata, data_size_t num_data) override {
    num_data_ = num_data;
    // get label
    label_ = metadata.label();
    // get weights
    weights_ = metadata.weights();
    // get boundries
    query_boundaries_ = metadata.query_boundaries();
    if (query_boundaries_ == nullptr) {
50
      Log::Fatal("Lambdarank tasks require query information");
Guolin Ke's avatar
Guolin Ke committed
51
52
    }
    num_queries_ = metadata.num_queries();
Hui Xue's avatar
Hui Xue committed
53
    // cache inverse max DCG, avoid computation many times
Guolin Ke's avatar
Guolin Ke committed
54
    inverse_max_dcgs_.resize(num_queries_);
Guolin Ke's avatar
Guolin Ke committed
55
#pragma omp parallel for schedule(guided)
Guolin Ke's avatar
Guolin Ke committed
56
    for (data_size_t i = 0; i < num_queries_; ++i) {
57
      inverse_max_dcgs_[i] = DCGCalculator::CalMaxDCGAtK(optimize_pos_at_,
Guolin Ke's avatar
Guolin Ke committed
58
        label_ + query_boundaries_[i],
59
        query_boundaries_[i + 1] - query_boundaries_[i]);
Guolin Ke's avatar
Guolin Ke committed
60
61
62
63
64
65
66
67
68

      if (inverse_max_dcgs_[i] > 0.0) {
        inverse_max_dcgs_[i] = 1.0f / inverse_max_dcgs_[i];
      }
    }
    // construct sigmoid table to speed up sigmoid transform
    ConstructSigmoidTable();
  }

69
  void GetGradients(const double* score, score_t* gradients,
Guolin Ke's avatar
Guolin Ke committed
70
71
72
73
74
75
76
                    score_t* hessians) const override {
    #pragma omp parallel for schedule(guided)
    for (data_size_t i = 0; i < num_queries_; ++i) {
      GetGradientsForOneQuery(score, gradients, hessians, i);
    }
  }

77
  inline void GetGradientsForOneQuery(const double* score,
Guolin Ke's avatar
Guolin Ke committed
78
79
80
81
82
83
              score_t* lambdas, score_t* hessians, data_size_t query_id) const {
    // get doc boundary for current query
    const data_size_t start = query_boundaries_[query_id];
    const data_size_t cnt =
      query_boundaries_[query_id + 1] - query_boundaries_[query_id];
    // get max DCG on current query
84
    const double inverse_max_dcg = inverse_max_dcgs_[query_id];
Guolin Ke's avatar
Guolin Ke committed
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
    // add pointers with offset
    const float* label = label_ + start;
    score += start;
    lambdas += start;
    hessians += start;
    // initialize with zero
    for (data_size_t i = 0; i < cnt; ++i) {
      lambdas[i] = 0.0f;
      hessians[i] = 0.0f;
    }
    // get sorted indices for scores
    std::vector<data_size_t> sorted_idx;
    for (data_size_t i = 0; i < cnt; ++i) {
      sorted_idx.emplace_back(i);
    }
    std::sort(sorted_idx.begin(), sorted_idx.end(),
             [score](data_size_t a, data_size_t b) { return score[a] > score[b]; });
    // get best and worst score
103
    const double best_score = score[sorted_idx[0]];
Guolin Ke's avatar
Guolin Ke committed
104
105
106
107
    data_size_t worst_idx = cnt - 1;
    if (worst_idx > 0 && score[sorted_idx[worst_idx]] == kMinScore) {
      worst_idx -= 1;
    }
108
    const double wrost_score = score[sorted_idx[worst_idx]];
Guolin Ke's avatar
Guolin Ke committed
109
110
111
112
    // start accmulate lambdas by pairs
    for (data_size_t i = 0; i < cnt; ++i) {
      const data_size_t high = sorted_idx[i];
      const int high_label = static_cast<int>(label[high]);
113
      const double high_score = score[high];
Guolin Ke's avatar
Guolin Ke committed
114
      if (high_score == kMinScore) { continue; }
115
116
117
118
      const double high_label_gain = label_gain_[high_label];
      const double high_discount = DCGCalculator::GetDiscount(i);
      double high_sum_lambda = 0.0;
      double high_sum_hessian = 0.0;
Guolin Ke's avatar
Guolin Ke committed
119
120
121
122
123
124
      for (data_size_t j = 0; j < cnt; ++j) {
        // skip same data
        if (i == j) { continue; }

        const data_size_t low = sorted_idx[j];
        const int low_label = static_cast<int>(label[low]);
125
        const double low_score = score[low];
Guolin Ke's avatar
Guolin Ke committed
126
127
128
        // only consider pair with different label
        if (high_label <= low_label || low_score == kMinScore) { continue; }

129
        const double delta_score = high_score - low_score;
Guolin Ke's avatar
Guolin Ke committed
130

131
132
        const double low_label_gain = label_gain_[low_label];
        const double low_discount = DCGCalculator::GetDiscount(j);
Guolin Ke's avatar
Guolin Ke committed
133
        // get dcg gap
134
        const double dcg_gap = high_label_gain - low_label_gain;
Guolin Ke's avatar
Guolin Ke committed
135
        // get discount of this pair
136
        const double paired_discount = fabs(high_discount - low_discount);
Guolin Ke's avatar
Guolin Ke committed
137
        // get delta NDCG
138
        double delta_pair_NDCG = dcg_gap * paired_discount * inverse_max_dcg;
Guolin Ke's avatar
Guolin Ke committed
139
140
141
142
143
        // regular the delta_pair_NDCG by score distance
        if (high_label != low_label && best_score != wrost_score) {
          delta_pair_NDCG /= (0.01f + fabs(delta_score));
        }
        // calculate lambda for this pair
144
145
        double p_lambda = GetSigmoid(delta_score);
        double p_hessian = p_lambda * (2.0f - p_lambda);
Guolin Ke's avatar
Guolin Ke committed
146
147
148
149
150
        // update
        p_lambda *= -delta_pair_NDCG;
        p_hessian *= 2 * delta_pair_NDCG;
        high_sum_lambda += p_lambda;
        high_sum_hessian += p_hessian;
151
152
        lambdas[low] -= static_cast<score_t>(p_lambda);
        hessians[low] += static_cast<score_t>(p_hessian);
Guolin Ke's avatar
Guolin Ke committed
153
154
      }
      // update
155
156
      lambdas[high] += static_cast<score_t>(high_sum_lambda);
      hessians[high] += static_cast<score_t>(high_sum_hessian);
Guolin Ke's avatar
Guolin Ke committed
157
158
159
160
161
162
163
164
165
166
167
    }
    // if need weights
    if (weights_ != nullptr) {
      for (data_size_t i = 0; i < cnt; ++i) {
        lambdas[i] *= weights_[start + i];
        hessians[i] *= weights_[start + i];
      }
    }
  }


168
  inline double GetSigmoid(double score) const {
Guolin Ke's avatar
Guolin Ke committed
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
    if (score <= min_sigmoid_input_) {
      // too small, use lower bound
      return sigmoid_table_[0];
    } else if (score >= max_sigmoid_input_) {
      // too big, use upper bound
      return sigmoid_table_[_sigmoid_bins - 1];
    } else {
      return sigmoid_table_[static_cast<size_t>((score - min_sigmoid_input_) * sigmoid_table_idx_factor_)];
    }
  }

  void ConstructSigmoidTable() {
    // get boundary
    min_sigmoid_input_ = min_sigmoid_input_ / sigmoid_ / 2;
    max_sigmoid_input_ = -min_sigmoid_input_;
Guolin Ke's avatar
Guolin Ke committed
184
    sigmoid_table_.resize(_sigmoid_bins);
Guolin Ke's avatar
Guolin Ke committed
185
186
187
188
189
    // get score to bin factor
    sigmoid_table_idx_factor_ =
      _sigmoid_bins / (max_sigmoid_input_ - min_sigmoid_input_);
    // cache
    for (size_t i = 0; i < _sigmoid_bins; ++i) {
190
      const double score = i / sigmoid_table_idx_factor_ + min_sigmoid_input_;
Guolin Ke's avatar
Guolin Ke committed
191
192
193
194
      sigmoid_table_[i] = 2.0f / (1.0f + std::exp(2.0f * score * sigmoid_));
    }
  }

Guolin Ke's avatar
Guolin Ke committed
195
196
  const char* GetName() const override {
    return "lambdarank";
Guolin Ke's avatar
Guolin Ke committed
197
198
199
200
  }

private:
  /*! \brief Gains for labels */
201
  std::vector<double> label_gain_;
Guolin Ke's avatar
Guolin Ke committed
202
  /*! \brief Cache inverse max DCG, speed up calculation */
203
  std::vector<double> inverse_max_dcgs_;
Guolin Ke's avatar
Guolin Ke committed
204
  /*! \brief Simgoid param */
205
  double sigmoid_;
Guolin Ke's avatar
Guolin Ke committed
206
207
208
209
210
211
212
213
214
215
216
217
218
  /*! \brief Optimized NDCG@ */
  int optimize_pos_at_;
  /*! \brief Number of queries */
  data_size_t num_queries_;
  /*! \brief Number of data */
  data_size_t num_data_;
  /*! \brief Pointer of label */
  const float* label_;
  /*! \brief Pointer of weights */
  const float* weights_;
  /*! \brief Query boundries */
  const data_size_t* query_boundaries_;
  /*! \brief Cache result for sigmoid transform to speed up */
219
  std::vector<double> sigmoid_table_;
Guolin Ke's avatar
Guolin Ke committed
220
221
222
  /*! \brief Number of bins in simoid table */
  size_t _sigmoid_bins = 1024 * 1024;
  /*! \brief Minimal input of sigmoid table */
223
  double min_sigmoid_input_ = -50;
Guolin Ke's avatar
Guolin Ke committed
224
  /*! \brief Maximal input of sigmoid table */
225
  double max_sigmoid_input_ = 50;
Guolin Ke's avatar
Guolin Ke committed
226
  /*! \brief Factor that covert score to bin in sigmoid table */
227
  double sigmoid_table_idx_factor_;
Guolin Ke's avatar
Guolin Ke committed
228
229
230
};

}  // namespace LightGBM
Guolin Ke's avatar
Guolin Ke committed
231
#endif   // LightGBM_OBJECTIVE_RANK_OBJECTIVE_HPP_