stochastic_linear_ranker/native/stochastic_linear_ranker.h

/*
 * Copyright (C) 2012 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

// Stochastic Linear Ranking algorithms.
// This class will implement a set of incremental algorithms for ranking tasks
// They support both L1 and L2 regularizations.


#ifndef LEARNING_STOCHASTIC_LINEAR_STOCHASTIC_LINEAR_RANKER_H_
#define LEARNING_STOCHASTIC_LINEAR_STOCHASTIC_LINEAR_RANKER_H_

#include <sys/types.h>

#include <cmath>
#include <string>
#include <unordered_map>

#include "cutils/log.h"
#include "common_defs.h"
#include "learning_rate_controller-inl.h"
#include "sparse_weight_vector.h"

namespace learning_stochastic_linear {

// NOTE: This Stochastic Linear Ranker supports only the following update types:
// SL: Stochastic Linear
// CS: Constraint Satisfaction
template<class Key = std::string, class Hash = std::unordered_map<std::string, double> >
class StochasticLinearRanker {
 public:
  // initialize lambda_ and constraint to a meaningful default. Will give
  // equal weight to the error and regularizer.
  StochasticLinearRanker() {
    iteration_num_ = 0;
    lambda_ = 1.0;
    learning_rate_controller_.SetLambda(lambda_);
    mini_batch_size_ = 1;
    learning_rate_controller_.SetMiniBatchSize(mini_batch_size_);
    adaptation_mode_ = INV_LINEAR;
    learning_rate_controller_.SetAdaptationMode(adaptation_mode_);
    update_type_ = SL;
    regularization_type_ = L2;
    kernel_type_ = LINEAR;
    kernel_param_ = 1.0;
    kernel_gain_ = 1.0;
    kernel_bias_ = 0.0;
    rank_loss_type_ = PAIRWISE;
    acceptence_probability_ = 0.1;
    mini_batch_counter_ = 0;
    gradient_l0_norm_ = -1;
    norm_constraint_ = 1.0;
  }

  ~StochasticLinearRanker() {}
  // Getters and setters
  double GetIterationNumber() const {
    return iteration_num_;
  }
  double GetNormContraint() const {
    return norm_constraint_;
  }
  RegularizationType GetRegularizationType() const {
    return regularization_type_;
  }
  double GetLambda() const {
    return lambda_;
  }
  uint64 GetMiniBatchSize() const {
    return mini_batch_size_;
  }
  int32 GetGradientL0Norm() const {
    return gradient_l0_norm_;
  }
  UpdateType GetUpdateType() const {
    return update_type_;
  }
  AdaptationMode GetAdaptationMode() const {
    return adaptation_mode_;
  }
  KernelType GetKernelType() const {
    return kernel_type_;
  }
  // This function returns the basic kernel parameter. In case of
  // polynomial kernel, it implies the degree of the polynomial.  In case of
  // RBF kernel, it implies the sigma parameter. In case of linear kernel,
  // it is not used.
  double GetKernelParam() const {
    return kernel_param_;
  }
  double GetKernelGain() const {
    return kernel_gain_;;
  }
  double GetKernelBias() const {
    return kernel_bias_;
  }
  RankLossType GetRankLossType() const {
    return rank_loss_type_;
  }
  double GetAcceptanceProbability() const {
    return acceptence_probability_;
  }
  void SetIterationNumber(uint64 num) {
    iteration_num_=num;
  }
  void SetNormConstraint(const double norm) {
    norm_constraint_ = norm;
  }
  void SetRegularizationType(const RegularizationType r) {
    regularization_type_ = r;
  }
  void SetLambda(double l) {
    lambda_ = l;
    learning_rate_controller_.SetLambda(l);
  }
  void SetMiniBatchSize(const uint64 msize) {
    mini_batch_size_ = msize;
    learning_rate_controller_.SetMiniBatchSize(msize);
  }
  void SetAdaptationMode(AdaptationMode m) {
    adaptation_mode_ = m;
    learning_rate_controller_.SetAdaptationMode(m);
  }
  void SetKernelType(KernelType k ) {
    kernel_type_ = k;
  }
  // This function sets the basic kernel parameter. In case of
  // polynomial kernel, it implies the degree of the polynomial. In case of
  // RBF kernel, it implies the sigma parameter. In case of linear kernel,
  // it is not used.
  void SetKernelParam(double param) {
    kernel_param_ = param;
  }
  // This function sets the kernel gain. NOTE: in most use cases, gain should
  // be set to 1.0.
  void SetKernelGain(double gain) {
    kernel_gain_ = gain;
  }
  // This function sets the kernel bias. NOTE: in most use cases, bias should
  // be set to 0.0.
  void SetKernelBias(double bias) {
    kernel_bias_ = bias;
  }
  void SetUpdateType(UpdateType u) {
    update_type_ = u;
  }
  void SetRankLossType(RankLossType r) {
    rank_loss_type_ = r;
  }
  void SetAcceptanceProbability(double p) {
    acceptence_probability_ = p;
  }
  void SetGradientL0Norm(const int32 gradient_l0_norm) {
    gradient_l0_norm_ = gradient_l0_norm;
  }
  // Load an existing model
  void LoadWeights(const SparseWeightVector<Key, Hash> &model) {
    weight_.LoadWeightVector(model);
  }
  // Save current model
  void SaveWeights(SparseWeightVector<Key, Hash> *model) {
    model->LoadWeightVector(weight_);
  }
  // Scoring
  double ScoreSample(const SparseWeightVector<Key, Hash> &sample) {
    const double dot = weight_.DotProduct(sample);
    double w_square;
    double s_square;
    switch (kernel_type_) {
      case LINEAR:
        return dot;
      case POLY:
        return pow(kernel_gain_ * dot + kernel_bias_, kernel_param_);
      case RBF:
        w_square = weight_.L2Norm();
        s_square = sample.L2Norm();
        return exp(-1 * kernel_param_ * (w_square + s_square - 2 * dot));
      default:
      ALOGE("unsupported kernel: %d", kernel_type_);
    }
    return -1;
  }
  // Learning Functions
  // Return values:
  // 1 :full update went through
  // 2 :partial update went through (for SL only)
  // 0 :no update necessary.
  // -1:error.
  int UpdateClassifier(const SparseWeightVector<Key, Hash> &positive,
                       const SparseWeightVector<Key, Hash> &negative);

 private:
  SparseWeightVector<Key, Hash> weight_;
  double norm_constraint_;
  double lambda_;
  RegularizationType regularization_type_;
  AdaptationMode adaptation_mode_;
  UpdateType update_type_;
  RankLossType rank_loss_type_;
  KernelType kernel_type_;
  // Kernel gain and bias are typically multiplicative and additive factors to
  // the dot product while calculating the kernel function. Kernel param is
  // kernel-specific. In case of polynomial kernel, it is the degree of the
  // polynomial.
  double kernel_param_;
  double kernel_gain_;
  double kernel_bias_;
  double acceptence_probability_;
  SparseWeightVector<Key, Hash> current_negative_;
  LearningRateController learning_rate_controller_;
  uint64 iteration_num_;
  // We average out gradient updates for mini_batch_size_ samples
  // before performing an iteration of the algorithm.
  uint64 mini_batch_counter_;
  uint64 mini_batch_size_;
  // Specifies the number of non-zero entries allowed in a gradient.
  // Default is -1 which means we take the gradient as given by data without
  // adding any new constraints. positive number is treated as an L0 constraint
  int32 gradient_l0_norm_;
  // Sub-Gradient Updates
  // Pure Sub-Gradient update without any reprojection
  // Note that a form of L2 regularization is built into this
  void UpdateSubGradient(const SparseWeightVector<Key, Hash> &positive,
                         const SparseWeightVector<Key, Hash> &negative,
                         const double learning_rate,
                         const double positive_score,
                         const double negative_score,
                         const int32 gradient_l0_norm);

};
}  // namespace learning_stochastic_linear
#endif  // LEARNING_STOCHASTIC_LINEAR_STOCHASTIC_LINEAR_RANKER_H_