介绍

MLlib中有两个lr实现。分别在mllib和ml中。此处分析的是ml,这也是后续mllib继续重点发展的一个库, mllib则会渐渐淡出历史舞台。ml的logistic回归,代码在org.apache.spark.ml.classification.LogisticRegression中实现。在详见代码之前,我们先简单地看下LR可调节的参数. [暂时修正至以1.6.1代码为参考.]

一、LR模型的参数

参数:

  • threshold: 如果label 1的概率>threshold,则预测为1,否则为0.
  • regParam:正则项参数(相当于lambda)
  • elasticNetParam:ElasticNet混合参数。如果alpha = 0, 惩罚项是一个L2 penalty。如果alpha = 1,它是一个L1 penalty。如果0 < alpha < 1,则是L1和L2的结果。缺省为0.0,为L2罚项。
  • maxIter: 缺省100次。
  • tol:迭代收敛的容忍度。值越小,会得到更高精度,同时迭代次数开销也大。缺省为1E-6.
  • fitIntercept: 是否要拟合截距项(intercept term),缺省为true.
  • standardization:在对模型进行fit前,是否对训练特征进行标准化(归一化)。模型的系数将总是返回到原始的scale上,它对用户是透明的。注意:当不使用正则化时,使用/不使用standardization,模型都应收敛到相同的解决方式上。在R的GLMNET包里,缺省行为也为true。缺省为true。
  • weightCol:如果没设置或空,所有实例为有为1的权重。如果设置,则相当于对unbalanced data设置不同的权重。缺省不设置。
  • treeAggregate:如果特征维度或分区数太大,该参数需要调得更大。缺省为2.

二、原理

logistic回归的原理,这里不详述。简单地写:y = logit(∑wx + b)。相应的loss和梯度如下所示(箭头表示向量):

$l_{model}$为cross-entropy;$l_{reg}$为正则项。

对于第一部分$l_{model}$的计算,依赖于训练数据;对于第二部分正则项,它不依赖于训练数据。因而这两部分在实现时是独立计算的。

每个训练样本的loss和gradient是独立的。

样本i的梯度:

样本的loss:

对于spark来说,ml的logistic回归实现通过treeAggregate来完成。在executors/workers上计算各RDD上的loss和gradient;在driver/controller上将它们进行reduce进行所有训练样本的求和,得到lossSum和gradientSum。

在单机的driver上完成Optimization; L1正则由OWLQN optimizer处理。L2由L-BFGS处理。这两个优化器都由Breeze库提供(Breeze库提供了Vector/Matrix的实现以及相应计算的接口Linalg)。

整个过程如图所示:

三、loss与gradient

主要在LogisticCostFun类中,具体见代码,这里仅把核心代码及注释帖出来。可以对应于上面的公式。

private class LogisticCostFun(
    instances: RDD[Instance],
    numClasses: Int,
    fitIntercept: Boolean,
    standardization: Boolean,
    featuresStd: Array[Double],
    featuresMean: Array[Double],
    regParamL2: Double) extends DiffFunction[BDV[Double]] {

  override def calculate(coefficients: BDV[Double]): (Double, BDV[Double]) = {
    val numFeatures = featuresStd.length
    val coeffs = Vectors.fromBreeze(coefficients)

    // step 1: cost部分.
    val logisticAggregator = {
      val seqOp = (c: LogisticAggregator, instance: Instance) => c.add(instance)
      val combOp = (c1: LogisticAggregator, c2: LogisticAggregator) => c1.merge(c2)

      // 先在rdd的每个分区上应用seqOp函数,做add操作(计算每个样本的loss/gradient)
      // 再在driver上应用comOp函数,做merge操作(求得总的loss/gradient)
      instances.treeAggregate(
        new LogisticAggregator(coeffs, numClasses, fitIntercept, featuresStd, featuresMean)
      )(seqOp, combOp)
    }

    // 求得总的gradientArray.
    val totalGradientArray = logisticAggregator.gradient.toArray

    // step 2: L2正则项部分 => regVal. 
    //  reg = lambda * ∑ regParamL2/2 wi^2 + (1-regParamL2) |wi| 
    // regVal is the sum of coefficients squares excluding intercept for L2 regularization.
    val regVal = if (regParamL2 == 0.0) {
      0.0
    } else {
      var sum = 0.0
      
      coeffs.foreachActive { (index, value) =>
        // If `fitIntercept` is true, the last term which is intercept doesn't
        // contribute to the regularization.
        if (index != numFeatures) {
          // The following code will compute the loss of the regularization; also
          // the gradient of the regularization, and add back to totalGradientArray.
          // gradientArray:  costFun项的梯度 + 正则项的梯度
          // sum: L2正则
          sum += {
             
            if (standardization) {
              
              totalGradientArray(index) += regParamL2 * value
              value * value
            } else {
              // 
              if (featuresStd(index) != 0.0) {
                // If `standardization` is false, we still standardize the data
                // to improve the rate of convergence; as a result, we have to
                // perform this reverse standardization by penalizing each component
                // differently to get effectively the same objective function when
                // the training dataset is not standardized.
                val temp = value / (featuresStd(index) * featuresStd(index))
                totalGradientArray(index) += regParamL2 * temp
                value * temp
              } else {
                0.0
              }
            }
          }
        }
      }

      0.5 * regParamL2 * sum
    }

    // 返回带L2正则的loss,以及带L2正则的梯度.
    (logisticAggregator.loss + regVal, new BDV(totalGradientArray))
  }
}

里面会涉及到另一个类:LogisticAggregator。它的作用,相当于做map/reduce运算,计算loss/gradient。

private class LogisticAggregator(
    coefficients: Vector,
    numClasses: Int,
    fitIntercept: Boolean,
    featuresStd: Array[Double],
    featuresMean: Array[Double]) extends Serializable {

  private var weightSum = 0.0
  private var lossSum = 0.0

  // coefficients => coefficientsArray 数组.
  private val coefficientsArray = coefficients match {
    case dv: DenseVector => dv.values
    case _ =>
      throw new IllegalArgumentException(
        s"coefficients only supports dense vector but got type ${coefficients.getClass}.")
  }

  // 总的维度.
  private val dim = if (fitIntercept) coefficientsArray.length - 1 else coefficientsArray.length

  //gradientSumArray.
  private val gradientSumArray = Array.ofDim[Double](coefficientsArray.length)

  /**
   * 将一个训练样本添加到LogisticAggregator, 并更新目标函数的loss和gradient.
   * 
   * Add a new training instance to this LogisticAggregator, and update the loss and gradient
   * of the objective function.
   *
   * @param instance The instance of data point to be added.
   * @return This LogisticAggregator object.
   */
  def add(instance: Instance): this.type = {
    instance match { case Instance(label, weight, features) =>
      require(dim == features.size, s"Dimensions mismatch when adding new instance." +
        s" Expecting $dim but got ${features.size}.")
      require(weight >= 0.0, s"instance weight, $weight has to be >= 0.0")

      if (weight == 0.0) return this

      val localCoefficientsArray = coefficientsArray
      val localGradientSumArray = gradientSumArray

      numClasses match {
        case 2 =>
          // For Binary Logistic Regression.
          // step 1: 二分类,求得 z = ∑ w*x + b,取负号.
          val margin = - {
            var sum = 0.0

            // a.每个特征号上,单独做求和运算.  ∑ w*x + b
            // 此处是做 ∑ w*x 运算. (是否做了归一化)
            features.foreachActive { (index, value) =>
              if (featuresStd(index) != 0.0 && value != 0.0) {
                sum += localCoefficientsArray(index) * (value / featuresStd(index))
              }
            }

            // 此处是 + b的运算.
            sum + {
              if (fitIntercept) localCoefficientsArray(dim) else 0.0
            }
          }

          // 这里的label采用的是(1,0).
          // step 2: 乘以该样本所带的unbalanced weight(样本所占比重, 缺省weight=1).
          val multiplier = weight * (1.0 / (1.0 + math.exp(margin)) - label)

          // step 3: 更新localGradient.
          // gradient = 1/n ∑ multiplier * x
          features.foreachActive { (index, value) =>
            if (featuresStd(index) != 0.0 && value != 0.0) {
              localGradientSumArray(index) += multiplier * (value / featuresStd(index))
            }
          }

          if (fitIntercept) {
            localGradientSumArray(dim) += multiplier
          }

          // step 4: 如果label为正例, loss为cross-entropy: 1/n * ∑ ln(1+exp(-y*wx))
          // lossSum.
          if (label > 0) {
            // The following is equivalent to log(1 + exp(margin)) but more numerically stable.
            lossSum += weight * MLUtils.log1pExp(margin)
          } else {
            lossSum += weight * (MLUtils.log1pExp(margin) - margin)
          }
        case _ =>
          new NotImplementedError("LogisticRegression with ElasticNet in ML package " +
            "only supports binary classification for now.")
      }

      // 
      weightSum += weight
      this
    }
  }

  /**
   * 进行merge: 方便分布式计算.
   *
   * Merge another LogisticAggregator, and update the loss and gradient
   * of the objective function.
   * (Note that it's in place merging; as a result, `this` object will be modified.)
   *
   * @param other The other LogisticAggregator to be merged.
   * @return This LogisticAggregator object.
   */
  def merge(other: LogisticAggregator): this.type = {
    require(dim == other.dim, s"Dimensions mismatch when merging with another " +
      s"LeastSquaresAggregator. Expecting $dim but got ${other.dim}.")

    if (other.weightSum != 0.0) {
      weightSum += other.weightSum
      lossSum += other.lossSum

      var i = 0
      val localThisGradientSumArray = this.gradientSumArray
      val localOtherGradientSumArray = other.gradientSumArray
      val len = localThisGradientSumArray.length

      // 以local为准. 每列coff所对应梯度进行叠加.
      while (i < len) {
        localThisGradientSumArray(i) += localOtherGradientSumArray(i)
        i += 1
      }
    }
    this
  }

  // 求得最终loss.
  def loss: Double = {
    require(weightSum > 0.0, s"The effective number of instances should be " +
      s"greater than 0.0, but $weightSum.")
    lossSum / weightSum
  }

  // 求得最终gradient.
  def gradient: Vector = {
    require(weightSum > 0.0, s"The effective number of instances should be " +
      s"greater than 0.0, but $weightSum.")
    val result = Vectors.dense(gradientSumArray.clone())
    scal(1.0 / weightSum, result)
    result
  }
}

四、训练过程

  override protected def train(dataset: DataFrame): LogisticRegressionModel = {
    // 从数据集抽取列. 如果数据集是persisted,不需要persist oldDataset.  
    // Extract columns from data.  If dataset is persisted, do not persist oldDataset.
    val w = if ($(weightCol).isEmpty) lit(1.0) else col($(weightCol))

    // 选取labelCol, weightCol, featuresCol作为row
    val instances: RDD[Instance] = dataset.select(col($(labelCol)), w, col($(featuresCol))).map {
      case Row(label: Double, weight: Double, features: Vector) =>
        Instance(label, weight, features)
    }

    // 是否持久化. 如果持久化,将训练样本进行cache. (MEMORY_AND_DISK,如果内存不够,会存成disk)
    // 这里有可能影响性能.
    val handlePersistence = dataset.rdd.getStorageLevel == StorageLevel.NONE
    if (handlePersistence) instances.persist(StorageLevel.MEMORY_AND_DISK)

    // 统计.
    val (summarizer, labelSummarizer) = {
      val seqOp = (c: (MultivariateOnlineSummarizer, MultiClassSummarizer),
        instance: Instance) =>
          (c._1.add(instance.features, instance.weight), c._2.add(instance.label, instance.weight))

      val combOp = (c1: (MultivariateOnlineSummarizer, MultiClassSummarizer),
        c2: (MultivariateOnlineSummarizer, MultiClassSummarizer)) =>
          (c1._1.merge(c2._1), c1._2.merge(c2._2))

      instances.treeAggregate(
        new MultivariateOnlineSummarizer, new MultiClassSummarizer)(seqOp, combOp)
    }

    val histogram = labelSummarizer.histogram
    val numInvalid = labelSummarizer.countInvalid
    val numClasses = histogram.length
    val numFeatures = summarizer.mean.size

    if (numInvalid != 0) {
      val msg = s"Classification labels should be in {0 to ${numClasses - 1} " +
        s"Found $numInvalid invalid labels."
      logError(msg)
      throw new SparkException(msg)
    }

    if (numClasses > 2) {
      val msg = s"Currently, LogisticRegression with ElasticNet in ML package only supports " +
        s"binary classification. Found $numClasses in the input dataset."
      logError(msg)
      throw new SparkException(msg)
    }

    // 特征的mean和std.
    val featuresMean = summarizer.mean.toArray
    val featuresStd = summarizer.variance.toArray.map(math.sqrt)

    // L1, L2
    val regParamL1 = $(elasticNetParam) * $(regParam)
    val regParamL2 = (1.0 - $(elasticNetParam)) * $(regParam)

    // costFun.
    val costFun = new LogisticCostFun(instances, numClasses, $(fitIntercept), $(standardization),
      featuresStd, featuresMean, regParamL2)

    // optimizer: 优化器.
    // 如果 elasticNetParam = 0, 或者 regParam=0. 即使用L2正则,或者没有正则项. => 使用LBFGS.
    // 否则,L1+L2正则,以及L1正则 => 使用OWLQN
    val optimizer = if ($(elasticNetParam) == 0.0 || $(regParam) == 0.0) {
      new BreezeLBFGS[BDV[Double]]($(maxIter), 10, $(tol))
    } else {
      def regParamL1Fun = (index: Int) => {
        // Remove the L1 penalization on the intercept
        if (index == numFeatures) {
          0.0
        } else {
          if ($(standardization)) {
            regParamL1
          } else {
            // If `standardization` is false, we still standardize the data
            // to improve the rate of convergence; as a result, we have to
            // perform this reverse standardization by penalizing each component
            // differently to get effectively the same objective function when
            // the training dataset is not standardized.
            if (featuresStd(index) != 0.0) regParamL1 / featuresStd(index) else 0.0
          }
        }
      }
      new BreezeOWLQN[Int, BDV[Double]]($(maxIter), 10, regParamL1Fun, $(tol))
    }

    // 初始化cofficients为0.
    val initialCoefficientsWithIntercept =
      Vectors.zeros(if ($(fitIntercept)) numFeatures + 1 else numFeatures)

    // 对于二分类,当将coefficients初始化为0时,如果根据label的分布对intercept进行初始化,收敛会更快.
    // b = log(P(1)/P(0))
    if ($(fitIntercept)) {
      /*
         For binary logistic regression, when we initialize the coefficients as zeros,
         it will converge faster if we initialize the intercept such that
         it follows the distribution of the labels.

         
         P(0) = 1 / (1 + \exp(b)), and
         P(1) = \exp(b) / (1 + \exp(b))
         , hence
         
         b = \log{P(1) / P(0)} = \log{count_1 / count_0}
         
       */
      initialCoefficientsWithIntercept.toArray(numFeatures)
        = math.log(histogram(1) / histogram(0))
    }

    // 开始迭代.
    val states = optimizer.iterations(new CachedDiffFunction(costFun),
      initialCoefficientsWithIntercept.toBreeze.toDenseVector)

    // 获取迭代的结果.
    val (coefficients, intercept, objectiveHistory) = {
      /*
         Note that in Logistic Regression, the objective history (loss + regularization)
         is log-likelihood which is invariance under feature standardization. As a result,
         the objective history from optimizer is the same as the one in the original space.
       */
      val arrayBuilder = mutable.ArrayBuilder.make[Double]
      var state: optimizer.State = null
      while (states.hasNext) {
        state = states.next()
        arrayBuilder += state.adjustedValue
      }

      if (state == null) {
        val msg = s"${optimizer.getClass.getName} failed."
        logError(msg)
        throw new SparkException(msg)
      }

      // 当权重coefficients在归一化空间中训练时,我们需要将它们转回到原始空间.
      // 注意,归一化空间的intercept,和原始空间是一样的,不需要归一化.
      /*
         The coefficients are trained in the scaled space; we're converting them back to
         the original space.
         Note that the intercept in scaled space and original space is the same;
         as a result, no scaling is needed.
       */
      val rawCoefficients = state.x.toArray.clone()
      var i = 0
      while (i < numFeatures) {
        rawCoefficients(i) *= { if (featuresStd(i) != 0.0) 1.0 / featuresStd(i) else 0.0 }
        i += 1
      }

      // 
      if ($(fitIntercept)) {
        (Vectors.dense(rawCoefficients.dropRight(1)).compressed, rawCoefficients.last,
          arrayBuilder.result())
      } else {
        (Vectors.dense(rawCoefficients).compressed, 0.0, arrayBuilder.result())
      }
    }

    if (handlePersistence) instances.unpersist()

    // 统计状态.
    val model = copyValues(new LogisticRegressionModel(uid, coefficients, intercept))
    val logRegSummary = new BinaryLogisticRegressionTrainingSummary(
      model.transform(dataset),
      $(probabilityCol),
      $(labelCol),
      $(featuresCol),
      objectiveHistory)
    model.setSummary(logRegSummary)
  }

四、正则

  • L2 regularization -> ridge
  • L1 regularization -> lasso
  • mix L1 and L2 -> elastic Net

相应的公式:

对应到后面的代码里:

regPram = regParamL1+regParamL2
val regParamL1 = $(elasticNetParam) * $(regParam)
val regParamL2 = (1.0 - $(elasticNetParam)) * $(regParam)

两种正则化方法L1和L2。L2正则化假设模型参数服从高斯分布,L2正则化函数比L1更光滑,所以更容易计算;L1假设模型参数服从拉普拉斯分布,L1正则化具备产生稀疏解的功能,从而具备Feature Selection的能力。

LBFGS和OWLQN

ok,我们知道,模型本身基本上核心代码就落在了这两个方法上:LBFGS和OWLQN。两者都是牛顿法的变种,核心思想是:

关于Hessian矩阵的计算,此处不做过多解释,如果你有兴趣想深究下数学实现。也可以再看一下breeze库里的这两个方法实现:

L-BFGS: Limited-memory BFGS。其中BFGS代表4个人的名字:broyden–fletcher–goldfarb–shanno OWL-QN: (Orthant-Wise Limited-Memory Quasi-Newton)算法。

关于breezey库,这里再简单提一下:

breeze库用于数值处理。它的目标是通用、简洁、强大,不需要牺牲太多性能。当前版本0.12。我们所熟悉的spark中的MLlib(经常见到的线性算法库:breeze.linalg、最优化算法库:breeze.optimize)就是在它的基础上构建的。另外它还提供了图绘制的功能(breeze.plot)。

总结

整个过程基本都ok了。L1还是L2的选择,看你的具体调参。另外再提一些注意事项。

  • 缺省会对特征做归一化,对于一些场景(比如推荐),离散化的特征,归一化没啥意义。反倒可能会影响结果好坏。
  • 对于截距b,会使用正负样本比例,进行log(P(1)/P(0))初始化。收敛会更快。
  • cache机制(StorageLevel.MEMORY_AND_DISK)。当内存不够用,可能会影响性能,这一点不好。

参考:

1.LogisticRegression源码 2.breeze 3.breeze文档

机器学习中的许多模型中,对类别型变量,常作的处理是,将它们编码成one-hot。但是对于树模型来说,将类别型变量编码成one-hot,这样作是否有意义呢?像一些机器学习工具包(比如:spark gbm实现),你可以指定为类别型变量,内部自己去做one-hot实现。而像xgboost,则将输入全认为是数值型特征去处理。

一、要不要one-hot?

这在机器学习界也有争论。理论上,树模型如果够深,也能将关键的类别型特型切出来。

关于这个,xgboost的作者tqchen在某个issues有提到过:

I do not know what you mean by vector. xgboost treat every input feature as numerical, with support for missing values and sparsity. The decision is at the user

So if you want ordered variables, you can transform the variables into numerical levels(say age). Or if you prefer treat it as categorical variable, do one hot encoding.

在另一个issues上也提到过(tqchen commented on 8 May 2015):

One-hot encoding could be helpful when the number of categories are small( in level of 10 to 100). In such case one-hot encoding can discover interesting interactions like (gender=male) AND (job = teacher).

While ordering them makes it harder to be discovered(need two split on job). However, indeed there is not a unified way handling categorical features in trees, and usually what tree was really good at was ordered continuous features anyway..

总结起来的结论,大至两条:

  • 1.对于类别有序的类别型变量,比如age等,当成数值型变量处理可以的。对于非类别有序的类别型变量,推荐one-hot。但是one-hot会增加内存开销以及训练时间开销。
  • 2.类别型变量在范围较小时(tqchen给出的是[10,100]范围内)推荐使用

二、one-hot的一致性问题

当你进行one-hot编码时,有些机器学习工具包内置的one-hot编码工具会帮你做这些事,但是真实的情况是,我们有数据集有如下分类:训练集、测试集、预测集(真实数据)等。

这些数据集并不会统一,比如:

训练集上A特征有: a,b,c,d,测试集上A特征有:a,b,d,预测集上可能有b,c,e,f

因此,你需要做的是,将它们统一使用one-hot编码,而非分开做不同的one-hot编码.

参考

部分是翻译,部分是个人的理解.

目录

线性模型

非线性模型

树模型

1.介绍

Fackbook提出的gbdt+LR来预测广告点击,本文简单重温下相应的paper。

在付费搜索广告领域(sponsored search advertising),用户query被用于检索候选广告(candidate ads),这些广告可以显式或隐式与query相匹配。在Facebook上,广告不与query相关联,但可以通过人口统计学(demographic)和兴趣(interest)来定向(targeting)。因而,当一个用户访问Facebook时,适合展示的广告容量(the volume of ads),比付费搜索中的要大。

为了应付每个请求上非常大量的候选广告,当用户访问Facobook时触发广告请求,我们会首先构建一连串的分类器,它们会增加计算开销。在本文中主要放在点击预测模型上,它会对最终的候选广告产生预测。

2.实验Setup

取2013年第4季度,某一个周的数据。为了在不同条件下维护相同的训练/测试数据,我们准备了离线训练数据,它与线上观测到的数据相似。我们将这些保存下来的离线数据划分成:训练数据和测试数据,并使用它们来模拟在线训练和预测的streaming数据。

评估的metrics: 使用预测的accuracy,而非利润和回报。我们使用归一化熵(NE: Normalized Entropy)作为主要的评测指标。

NE,或者更准确地被称为NCE:归一化的Cross-Entropy,等价于每次曝光(impression)的平均log loss,再除以如果一模型为每个曝光预测了相应后台CTR(backgroud CTR),所对应的每个曝光的log loss平均。换句话说,预测的log loss通过backgroud CTR的熵进行归一化。backgroud CTR是训练数据集的平均期望CTR(average empirical CTR)。它可能更多描述是指关于归一化log loss(Normalized Logarithmic Loss)。值越低,通过该模型预测的效果越好。使用该归一化的原因是,backgroud CTR越接近0或1,也容易达到一个更好的log loss。除以backgroud CTR的熵,使得NE对于backgroud CTR不敏感。假设一个给定的数据集,具有N个样本,对应的labels为: $ yi \in {-1,+1} $,点击概率pi,其中i=1,2,…,N。平均期望CTR为p:

……(1)

NE是一个必需单元,用于计算相关的信息增益(RIG: Relative Information Gain). RIG=1-NE

Calibration(校准)是一个关于平均估计CTR和期望CTR的比值。该比值相当于:期望点击数与实际观察点击数。Calibration是一个非常重要的指标,因为关于CTR的准确(accurate)和well-calibrated预测,对于在线竞价和拍卖的成功很重要。Calibration离1越小,模型越好。

注意,对于评估ranking的质量(不考虑Calibration),AUC也是一个相当好的指标。真实环境下,我们希望预测够准,而非仅仅获取最优的rank顺序,以避免欠拟合(under-delivery)或过拟合(overdelivery)。NE可以权衡预测的好坏,并隐式地影响calibration。例如,如果一个模型过度预测2倍,我们可以使用一个全局的乘子0.5来修正calibration,对应的NE也会提升,即使AUC仍相同。详见paper[12]

3.预测模型结构

本部分我们提出了一种混合模型结构:将GBDT与一个概率稀疏的线性分类器相串联,如图1所示。在3.1中,决策树对于输入特征的转换十分强大,可以极大增加概率线性分类器的accuracy。在3.2中,会展示训练数据的新鲜度是如何影响更准确的预测。这激发了我们使用一个在线学习方法来训练线性分类器。在3.3中,我们比较一些在线学习变种。

图1: 混合模型结构。输入特征通过boosted决策树的方式进行转换,每棵树的输出作为一个类别型输入特征,输入到一个稀疏的线性分类器上。Boosted决策树提供了非常强的特征转换.

我们评估的在线学习模式,是基于SGD算法的,应用于稀疏线性分类器。在特征转换后,给定一个ad的曝光,具有一个vector形式:$ x=(e_{i1},…,e_{in}) $,其中ei表示第i个unit vector,$i_1,…,i_n$是n种类别输入特征的值。在训练阶段,我们假设,给定一个二元标签 $y \in {-1,+1}$,用于表示点击or未点击。

给定一个加上label的广告曝光:(x,y),我们将激活权重的线性组合表示成:

……(2)

其中w是线性点击分值的weight vector。

对于概率回归(BOPR),目前最state-of-art的Bayesian在线学习scheme在[7]中有描述,似然和先验如下:

3.1 决策树特征转换

为了提升accuracy,有两种简单的方法,来对线性分类器的输入特征进行转换。对于连续型特征,用于学习非线性变换的一个简单的trick是,将特征二值化(bin),将将二值索引(bin index)看成是一个类别型特征。线性分类器可以有效地为该特征学到一个分段(piece-wise)常量的非线性映射。学到有用的二值边界很重要,有许多方法。

第二个简单但有效地转换包含在构建tuple型输入特征中。对于类别型特征,在笛卡尔积中采用的暴力搜索方法,比如,创建一个新的类别型特征,将它看成是原始特征的所有可能值。并不是所有的组合都有用,那些不管用的可以对其进行剪枝。如果输入特征是连续的,可以做联合二值化(joint binning),使用k-d tree。

我们发现boosted决策树很强大,非常便于实现非线性和上面这种tuple型转换。我们将每棵树看成是一个类别型特征,它把值看成是将叶子的索引。对于这种类型的特征,我们使用1-of-K的编码。例如,考虑图1中的boosted tree模型,有2棵子树,其中第1棵子树具有3个叶子,第2棵具有2个叶子。如果一个实例在第1棵子树的叶节点2上结束,在第2棵子树的叶节点1上结束,那么整体的输入到线性分类器上的二元向量为:[0,1,0,1,0],其中前3个实体对应于第1棵子树的叶子,后2个对应于第2棵子树。我们使用的boosted决策树为:Gradient Boosting Machine(GBM)[5],使用的是经典的L2-TreeBoost算法。在每个学习迭代中,会对前面树的残差进行建模创建一棵新树。我们可以将基于变换的boosted决策树理解成一个监督型特征编码(supervised feature encoding),它将一个实数值向量(real-valued vector)转换成一个压缩的二值向量(binary-valued vector)。从根节点到某一叶子节点的路径,表示在特定特征上的一个规则。在该二值向量上,再fit一个线性分类器,可以本质上学到这些规则的权重。Boosted决策树以batch方式进行训练。

我们开展实验来展示将tree features作为线性模型的效果。在该实验中,我们比较了两个logistic regression模型,一个使用tree feature转换,另一个使用普通的(未转换)特征。我们也加了一个单独的boosted决策树模型作为对比。所表1所示:

相对于没有树特征转换的模型,树特征变换可以帮助减小3.4%的NE。这是非常大的相对提升。作为参考,一个典型的特征工程实验,可减小20-30%左右的相对NE。LR和树模型以独立方式运行下的比较也很有意思(LR的预测accuracy更好一点点),但它们组合起来会有大幅提升。预测acuracy的增益是很大;作为参考,特征工程的好坏可以影响NE更多。

3.2 数据新鲜度

点击预测系统经常被部署在动态环境上,数据分布随时间变化。我们研究了训练数据的新鲜度对于预测效果的提升情况。我们在特定的某一天训练了一个模型,并在连续的数天对该模型进行测试。我们同时运行boosted决策树模型,以及一个使用树转换的LR模型。

在该实验中,我们训练了一天的数据,在后面的6天进行评估,计算每天的NE。结果如图2所示。

图2: 预测accuracy和时间关系

随着训练集与测试集间的时延的增长,预测accuracy明显下降。一周内两种模型的NE都下降大概1%左右。

该发现表明,需要以天为基础重新训练模型。一种选择是:使用一个周期天级任务,以batch方式重新训练模型。重新训练boosted决策树的时间各有不同,具体依赖于训练样本数,树的数目,每棵树的叶子,cpu,内存等。对于单核cpu,1亿左右的样本,有可能会超过24小时来构建一个上百棵树的boosting模型。实际情况中,训练过程可以在多核机器上,内存量足够存储整个训练集,通过足够的并发,使用几个小时来完成。下一部分,我们可以使用另一种方法。boosted决策树,可以每天或者每两天进行训练,但是线性分类器可以通过在线学习方式,接近实时进行训练。

3.3 在线线性分类器

为了最大化数据的新鲜度,一个选择是,当广告曝光数据到达标注后,直接在线训练线性分类器。在下面的第4部分,我们会描述一些基础,用来生成实时训练数据。在这部分,我们评估了许多方式,为基于SGD的LR在线学习设置不同的learning-rate。我们接着比较BOPR模型的在线学习最好变种。

在语术(6)中,我们可以有以下选择:

1.Per-coordinate学习率。该learning rate对于特征i在第t次迭代可设置成:

α, β 是两个可调的参数。

2.Per-weight均方根学习率。

3.Per-weight学习率:

4.全局学习率:

5.常数学习率:

前三种scheme可以为每个feature独立设置learning rate。后两种为所有feature使用相同的learning rate。所有可调的参数可以通过grid search进行优化。

对于连续学习(continuous learning),我们可以将learning rate设置为一个较低的边界0.00001. 我们使用上述的learning rate scheme来在相同的数据上训练和测试LR模型。相应的试验结果如图3所示。

图3: 不同learning rate schema的实验. X表示不同的learning rate。左侧为calibration,y轴右侧为NE.

从上面的结果可知,使用per-coordinate learning rate的SGD可以达到最好的预测accuracy,它可以降低5%的NE,比使用per weight learning rate要低(这种最差)。该结果的结论在[8]。per-weight square root学习率和常数学习率,几乎相同。另两种则比前面的都要差很多。global学习率失败的原因主要是因为训练实例的数目在每个特征上是不平衡的(imbalance)。由于每个训练实例可能包含不同的feature,一些流行的feature比起其它feature会具有更多的训练实例。在global学习率scheme下,具有更少训练实例的features的learning rate,会降得更快,以阻止最优weight(optimum weight)的收敛。尽管per-weight的learning rate的scheme也有相同的问题,它仍会失败,因为对于所有features,它会很快地减小learning rate。训练会过早终结,而模型会收敛到一个次优的点(sub-optimal point)。这解释了为什么该scheme在所有选择中具有最差的performance。

有意思的是,需要注意BOPR更新式(3),意味着最接近LR SGD的per-coordinate learning rate版本。BOPR的有效学习率可以指定到每个coordinate上,取决于权重的后验variance,与每个单独的coordinate相关。

。。

4.Online data JOINER

前面的部分确定了训练数据中新鲜度会增加预测accuracy。同时也介绍了一个简单的模型架构,其中的线性分类器这一层是在线方式训练的。

本部分介绍一个实验系统,它生成实时训练数据,通过online learning来训练线性分类器。我们将该系统看成是”online joiner”,因为它的临界操作(critical operation)是将labels(click/no-click)和训练输入(ad impressions)以在线方式join起来。相同的基础设施可以用于流式学习(stream learning),例如Google Advertising System[1]。该online joiner会输出一个实时的训练数据流到一个称为“Scribe”的基础设施上[10]。而positive labels(clicks)是定义良好的,它没有提供给用户”no click”按钮。出于该原因,如果用户看到该广告后,在一个确定的,足够长的时间周期上没有点击该广告,那么这次曝光(impression)可以认为是具有一个negative的no-click label。等待的时间窗口需要小心调节。

使用太长的时间窗口(time window),会延迟实时训练数据,并增加内存分配开销来缓存要等待点击信号的impressions。一个过短时间的时间窗口,会造成一些点击丢失,因为相应的impression可以会被冲掉,并当成no-clicked label来对待。这种负面影响称为”点击覆盖(click coverage)”,它是一个关于所有成功的clicks与impressions相join的一个分数。作为结果,online joiner系统必须在最新性(recency)和点击覆盖(click coverage)间做出一个平衡。

不具有完整的点击覆盖,意味着实时训练集是有偏差的(bias):经验CTR(empirical CTR)会比ground truth要低。这是因为,一部分被标注为未点击(no-clicked)的曝光(impressions),如果等待时间足够长,会有可能会被标注成点击数据。实际上,我们会发现,在内存可控范围内,随着等待窗口的size的变大,很容易减小bias到小数范围内。另外,这种小的bias是可衡量和可纠正的。关于window size的研究可以见[6]。online joiner被设计成执行一个在ad impressions和ad clicks之间的分布式stream-to-stream join,使用一个请求ID(request ID)作为join的主键。每一时刻当一个用户在Facebook上执行一个动作时,都会生成一个请求ID,会触发新鲜的内容曝光给他们。图4展示了online joiner和online learning的数据和模型流。当用户访问Facebook时,会生成初始的数据流,会发起一个请求给ranker对候选广告进行排序。广告会被传给用户设备,并行的,每个广告、以及和它相关的用于ranking的features,会并行地添加到曝光流(impression stream)中。如果用户选择点击该广告, 那么该点击(click)会被添加到点击流中(click stream)。为了完成stream-to-stream join,系统会使用一个HashQueue,它包含了一个先入先出的队列(FIFO queue)作为一个缓存窗口;以及一个hashmap用于快速随机访问label曝光。一个HashQueue通常在kv-pair上具有三种类型的操作:enqueue, dequeue和lookup。例如,为了enqueue一个item,我们添加该item到一个队列的前面,并在hashmap中创建一个key,对应的值指向队列中的item。只有在完整的join窗口超期后(expired),会触发一个标注的曝光(labelled impression)给训练流。如果没有点击join,它会触发一个negative的标注样本。

在该实验设置中,训练器(trainer)会从训练流中进行持续学习,并周期性发布新模型给排序器(Ranker)。这对于机器学习来说,最终会形成一个紧的闭环,特征分布的变更,或者模型表现的变更都能被捕获,学到,并在后续得到修正。

一个重要的考虑是,当使用实时训练数据生成系统进行试验时,需要构建保护机制来处理在线学习系统崩溃时引发的异常。给一个简单示例。由于某些数据基础设施的原因,点击流(click stream)过期了,那么online joiner将产生这样的数据:它具有非常小或近乎0的经验CTR(empirical CTR)。作为结果,该实时训练器会开始以非常低、或近乎0的点击概率来进行错误的预测。一个广告的期望值会自然的决策于估计的点击概率,不正确预测成非常低的CTR的一个结果是,系统会降低广告曝光数。异常检测机制在这里就很有用。例如,如果实时训练数据分布突然发生变更,你可以从online joiner上自动断开online trainer。

5.内存与延迟

5.1 boosting trees的数目

模型中树越多,训练时间越长。这部分会研究树的数目在accuracy上的影响。

我们区分了树的数目,从1到2000棵,在一个完整天的数据上训练模型,并在下一天预测效果。我们限制了每棵树的叶子节点不超过12个。与之前的试验类似,我们使用NE作为评测的metric。试验结果如图5所示。NE会随着boosted trees的数目增加而增加。然而,通过添加树获得的增益,所获得的回归会减少。几乎所有的NE提升,都来自于前500棵树。最后的1000棵树减少的NE比0.1%还要少。另外,我们看到,NE对于子模型2(submodel 2), 会在1000棵树后开始倒退。这种现象的可能原因是overfitting。因为子模型2的训练数据比子模型0和1的要小。

图5: boosting tree的数目的实验。不同系统对应着不同的子模型。x轴表示boosting trees的数目。Y轴表示NE.

5.2 Boosting feature importance

特征数(feature count)是另一个模型特性,它可以影响估计的accuracy和计算性能。为了更好理解特征数的影响,我们首先为每个特征应用一个特征重要性(feature importance)。

为了衡量一个特征的重要性,我们使用statistic Boosting Feature Importance,它可以捕获一个feature的累积loss衰减属性(cumulative loss reduction)。在每个树节点构建中,会选择最好的feature,并将它进行split,来达到最大化平方误差衰减(squared error reduction)。由于一个feature可以被用在多棵树中,每个feature的(Boosting Feature Importance)可以通过在所有树上对一个指定feature做总的reduction的求和。

通常,只有少量的特征对可解释性(explanatory power)有主要贡献,对可解释性,而其余的特征则只有少量贡献。我们可以看到,当绘制特征数 vs. 累积特征重要性时(如图6所示),这种现象。

图6: Boosting feature importance。x轴表示特征数。在y轴左侧表示log scale中抽取了特征重要性,而y轴右侧表示累积特征重要性。

从上面的结果看来,top 10的特征占握着总的特征重要性的一半,而最后300个特征只贡献了少于1%的feature importance。基于该发现,我们进一步试验,只保留top 10,20,50,100,200个特征,并评估是如何影响表现的。试验的结果如图7所示。从图中可知,我们可以看到,当增加更多的特征时,NE的回报很少。

图7: 对于top features,Boosting模型的结果. 我们在y轴的左边,抽取了calibration,而在右边的y轴对应于NE.

下面,我们将研究,历史特征(historical feature)和上下文特征(contextual feature)是否有用。由于数据敏感性,我们不能展示实际使用的特征细节。一些上下文特征举例:一天里的local time,week里的天等。历史特征可以是:在一个广告上的点击累计,等。

5.3 历史型特征

Boosting模型中使用的特征可以归类为两类:上下文型特征(contextual features)和历史型特征( historical features)。上下文特征的值仅仅取决于取决于一个广告所处的上下文当前信息,比如,用户使用的设备,或者用户停留的当前页面。相反的,历史特征则取决于广告(ad)或用户(user)之前的交互,例如,该广告在上周的点击通过率(click through rate),或者该用户的平均点击通过率。

图8: 历史型特征百分比的结果。X轴表示特征数。Y轴表示历史型特征在top-k个重要特征中的占比。

在这一部分,我们研究了该系的表现是如何受这两种特征影响的。首先,我们检查了两种类型的相对重要性。我们通过将所有特征按重要性进行排序,接着计算在top-k个重要的特征中,历史特征的占比。结果如图8所示,从该结果看,我们可以看到,比起上下文型特征,历史型特征更具可解释性。通过重要性排序的top 10个特征全部都是历史型特征。在top 20个特征间,只有2个上下文特征,尽管历史型特征在数据集上占据着75%的特征。为了更好地理解在aggregate中每种类型的比较值,我们训练了两种Boosting模型:一种只使用上下文型特征,另一种只使用历史型特征,接着将两个模型与带所有特征的完整模型相比较。结果如表4所示。

[表4]

从该表中,我们可以再次验证,历史型特征比上下文型特征更重要。如果只有上下文型特征,我们在预测accuracy上计算4.5%的loss。相反地,没有上下文型特征,我们在预测accuracy上有1%的loss。

需要注意到,上下文型特征对于处理冷启动问题很重要。对于新用户和新广告,上下文型特征对于合理的点击率预测是必不可少的。

在下一步,我们会评估在连续几周中,只使用历史型特征的训练模型,或者只使用上下文特征的训练模型,来测试在数据新鲜度上的特征依赖性。结果如图9所示。

图9: 不同类型特征对数据新鲜度的结果。X轴表示评估时期,Y表示NE.

从该图看到,比起历史型特征,使用上下文型特征的模型更依赖于数据新鲜度。这与我们的直觉相符合,因为历史型特征描述了长期累积的用户行为,它比起上下文型特征更稳定。

6.大规模训练数据

Facebook的一整天的广告曝光数据是海量的。注意,我们不会展示实际数量。但一天的一定比例的数据可以有几百万的实例。一个常用的技术来控制训练开销是,减少训练数据的量。在本节中,我们评估了两种方法用于下采样:均均子抽样(uniform subsampling)和负下采样(negative down sampling)。在每个case上,我们会训练一个使用600棵树的boosted tree模型的集合,然后使用calibration和NE进行评估。

6.1 均匀子抽样

训练行的均匀子抽样(uniform subsampling)是一种减少数据量的好方法,因为它可以很容易实现,生成的模型不需要修改,就可以在抽样的训练数据上以及未抽样的测试数据上直接使用。在本部门,我们会评估抽样率会指数式增加。对于每个在基础数据集上进行抽样的rate,我们分别训练了一个boosted tree模型。subsampling rate为{0.001, 0.01, 0.1, 0.5, 1}。

图10: 数据量的实验结果。X轴表示训练实例数。y左表示calibration。y右表示NE.

数据量及结果如图10. 它与我们的直觉相一致,越多的数据会导致更好的表现。再者,数据量展示了预测accuracy的回报会越来越少。通过使用10%的数据,NE只有在表现上,相较于整个训练数据集只有1%的减少。在该sampling rate上calibration几乎没有减少。

6.2 负下采样

类别不均衡(class imbalance)问题,许多研究者都有研究,它会对学到的模型具有重大的影响。在该部分,我们探索了使用负下采样(Negative down sampling)来解决类别不均衡的问题。经验上,我们使用不同负下采样率,来测试学到模型的accuracy。相应的rate为:{0.1, 0.01, 0.001, 0.0001}。结果如图11所示。

图11: 负下采样的实验结果。X轴对应于不同的负下采样率。y左表示calibration,y右表示NE.

从结果上看,我们可知,负下采样率在训练模型的表现上具有极大的提升。当负下采样率设置在0.025时具有最好的表现。

6.3 模型Re-Calibration

负下采样可以加速训练,提升模型表现。注意,如果在一个数据集上使用负下采样来训练一个模型,它可以校正(calibrate)在下采样空间上的预测。例如,如果平均CTR在采样之前只有0.1%,我们做一个0.01的负下采样,经验CTR(empirical)大约有10%的提升。对于真实的流量实验(hive traffic experiment),我们需要重新校准模型,会获得0.1%的回报,$ q=\frac{p}{p+(1-p)/w} $。其中p是在下采样空间中的预测,w是负下采样率。

略.

参考:

1.Practical Lessons from Predicting Clicks on Ads at Facebook 2.kaggle:gbdt+libffm

在推荐系统中,用于测试模型性能,通常会选定随机选定部分用户,观察这些用户在推荐项上的行为。这就是我们常说的分桶测试(bucket tests)。

假定有两个推荐模型:模型A和模型B。我们可以创建两个不相交的样本:基于用户(用户id)的样本选择方式创建、或基于请求(用户访问行为)的样本选择方式创建。接着,对于第一个样本,使用模型A; 对于第二个样本,使用模型B。并持续服务一段时间。这里的每个样本,称为一个桶(bucket)。通常有两种常用的分桶方式:

  • 1.基于用户的分桶(User-based bucket):这样的桶,是一个随机选定用户的集合。一种简单的方式是,使用一个hash函数,为每个user id生成一个hash值,选择一个特定的范围指向一个桶。例如:Ron Rivest设计的md5。

  • 2.基于请求的分桶(Request-based bucket):这样的桶,是一个随机选择的请求的集合。常用的做法是,为每个请求生成一个随机数,然后将对应指定范围的请求随机数指定到某个桶内。注意,在这样的桶中,在实验期间,同一个用户不同的访问,有可能属于不同的分桶。

基于用户的分桶,通常比基于请求的分桶更简洁、更独立。例如,当使用基于请求的分桶时,一个用户使用模型A的响应(Response),可能会影响到模型B。但是,在基于用户的分桶中,这个现象不会发生。另外,任何长期用户行为都可以在基于用户的分桶中进行。然而,如果在基于用户的分桶中使用一个简单模型,该分桶的用户可能会收到不好的结果,这样也会导致较差的用户体验。而基于请求的分桶则对这种模型相对不敏感些,因为一个用户的所有请求不一样分配到相同的bucket中。总之,基于用户的分桶更受欢迎些。

在受控的实验中,分桶的所有设置应该一致,除了为每个分桶分配的模型不同;模型A用于服务分桶1;模型B用于服务分桶2。特别的,对于两个分桶来说,我们要使用相同的选择方式准则。例如,某一个分桶只包含登陆用户,那么另一个分桶也必须一致。

当使用基于用户的分桶时,对于不同的测试,最好使用独立的各不相同的hash函数,以保持正交性。例如,假设我们在一个web页面具有两个推荐模块,每个模块对应两个要测试的模型。两个对应的测试模块:test1和test2。对于每个test i,都有两个对应的推荐模型:Ai和Bi。如果我们在两组test上使用相同的hash函数为用户分配hash值,hash值低于某个阀值的使用模型Ai,剩下的使用模型Bi,这样,模型A1的用户与模型A2的用户相同;模型B1的用户与模型B2的用户相同。由于涉及到与A2和B2的交互,这会导致模型A1与模型B1之间的比较不够合理。解决这种问题的一个方法是,确保分配给A1模型的用户概率与test2中的A2或B2模型相互独立。这很容易实现,如果我们在test1中使用的将user id映射后的hash值与test2中相互统计独立即可。使用独立的hash函数,可以帮助我们控制当前测试与之前测试的独立性。

另一个有用的实践是,使用相同的模型服务两组分桶,并确认两个桶对应的性能指标是否统计上相似。这样的测试通常称为A/A test。它不仅为继承的统计变量提供了一个好的估计,而且还可以帮助在实验阶段发现明显错误。另一个有用的实践是,运行一个分桶测试至少需要一到两周,因为,用户行为通常有一周时间里有时间周期性上的不同。当一个新的推荐模型推荐对应在其它模型上完全不同的item时,由于新奇性效应(novelty effect),用户(user)可能倾向于在初始阶段点击更积极。为了减小因此造成的潜在偏差,当监控测试指标时,通常抛弃开始阶段的测试结果是很有用的。

标准的实验设计方法可以用来决定一个分桶所需要size以达到统计显著性(statistical significance)。拔靴法(Bootstrap sampling)在决定性能指标的方差时很管用,它可以用来帮助计算分桶的抽样size。详见:Montgomery(2012)、Efron和Tibshirani(1993).

参考: