介绍

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 $ 。如果$ \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前,是否对训练特征进行标准化(归一化)。模型的系数将总是返回到原比例(origin scale)上,它对用户是透明的。注意:当不使用正则化时,使用/不使用standardization,模型都应收敛到相同的解(solution)上。在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文档

关于itemcf的topk问题,我们看下较老的一篇paper《Evaluation of Item-Based Top-N Recommendation Algorithms》中提到的:

3

在本paper中,我们研究了一种item-based topN推荐算法,它使用item-to-item相似度来计算items间的关系。在模型构建期间,对于每个item j,它具有k个计算好的最相似的items:,它们对应的相似度分值为:。接着,对于已经购买了商品集合U(购物篮:basket)的每个客户,可以使用上述信息来计算top-N items进行推荐。首先,我们通过对每个item 上对应的k个最相似items的联集(union),并移除已在U中存在的items,来标识候选推荐items集合C。接着,对于每个item ,我们会计算它与集合U的相似度,来作为在所有item 和c之间相似度的求和,使用只有j的k个最相似items。最终,在C中的items根据各自相似度以降序排序,选择前N个items作为top-N的推荐集合。

3.1 相似度选择

  • cosine-based
  • Conditional Probality-based

3.2 相似度归一化

第3节中,给定一个items集合(basket) U,通过以下的item-based top-N推荐算法决定着要推荐的items:通过计算不在U中的每个item和U中所有items间的相似度,并选择N个最相似的items作为推荐集合。集合U和一个item 间的相似度,通过在每个item 和v间添加相似度来决定(如果v不在u的k个最相似items中)

该方法的一个潜在缺点是,在每个item u和它的k个最相似items间的原始相似度(raw similarity)可能相当不同。也就是说,item的邻近点具有不同的密度。购买了那些不常购的items来说这是特别正确的,由于一个,这对于其它不常购买的items间存在一定适度的重合,可以产生相当高的相似度值。结果是,这些items在top-N items的选择时可以发挥相当强的影响力,有时会导致产生差的推荐。出于该原因,需要通过别的方法来替代3.1节描述的那些真实相似度,对于每个item u,我们首先会归一化相似度以便它们合计为1(add-up to one)。如第4节的实验所示,这通常会在top-N的推荐质量上产生明显提升。

4.实验

4.3 相似度归一化的效果

我们的第一个实验被设计成用来评估3.2节中相似度归一化的效果。图1展示了。由4种不同的item-based推荐算法的accuracy对比。其中两者使用cosine做为相似度函数,另两者使用条件概率(conditional probability)。每个算法对间的不同之处是,一个不会归一化相似度(被标记为“Cos-Sraw”和”CProb-Sraw”),另一个会进行归一化(被标记为”Cos-Snorm”和”CProb-Snorm”)。对于所有这4种算法,矩阵的行都会进行归一化,以便它们具有一致的长度,k(模型中最近邻items的数目)设置为10, “CProb-Sraw”和”CProb-Snorm”的设置为0.5.

图1: 相似度归一化在推荐质量上的效果

如图1所示,我们可以看到,使用相似度归一化的算法可以达到更高的推荐accuracies,对比起其它不使用的。实际的提升与数据库和算法有关。总之,基于条件概率的scheme相对提升要比cosine-based scheme要高。cosine-based scheme的效果提升有0%~ 6.5%,平均提升有3.1%,conditional probability-based scheme的提升会有3%-12%,平均提升7%。由于这个优点,在实验的其它地方总会使用相似度归一化。

参考

我们先来看下慕尼黑大学的paper:《CAPTCHA Recognition with Active Deep Learning》。

2.介绍

常用的方法是,以两个相互独立的步骤来检测图片中的文本:定位在文本中的词(words)或单个字符(characters)的区域,进行分割(segmenting)并接着对它们进行识别。另外,可以使用一个字典来排除不可能的词(words)。例如,Mori and Malik提出的方法来使用一个411个词的字典来识别CAPTCHAs。等等,然而,在现代CAPTCHAs中,单个字符不能轻易地使用矩形窗口进行分割,另外字符可以相互有交叠。这些CAPTCHAs与手写文本相类似,LeCun提出使用CNN来解决手写数字识别。这些CNNs被设计成用于构建layer by layer体系来执行分类任务。在2014年,Google fellow提出使用deep CNN来结合定位(localzation),分割(segmentation)以及多字符文本的识别。jaderberg等提出了一种在自然场景图片中的文本识别。然而,对于训练过程,它们人工模拟创建了一个非常大的文本图片的集合。相反的,我们则使用一个更小的训练集。通过探索Active Learning,我们在运行期对该神经网络进行微调(fine-tune),我们的网络接收已正确分好类但高度不确定的测试样本的前馈输入(feed)。

3.用于CAPTCHA识别的Deep CNN

图2. 用于captcha识别的卷积神经网络。该CNN由三个conv layer,三个pooling layer,两个fully-connected layer组成。最后的layer会输出所有数字的概率分布,我们可以由此计算预测数据(prediction)以及它的不确定度

我们提出了一种deep CNN来解决CAPTCHA问题。我们的方法在识别整个sequence时没有预分割(pre-segmentation)。我们使用如图2所示的网络结构。我们主要关注6数字的CAPTCHAs。每个数字(digit)在output layer中由62个神经元表示。我们定义了一个双向映射函数(bijection):$\sigma(x) $,它将一个字符 $ x \in { ‘0’ … ‘9’ , ‘A’ … ‘Z’, ‘a’ … ‘z’ } $映射到一个整数$ l \in { 0 , … , 61 }$上。

我们分配第一个62输出神经元(output neurons)到第一个序列数字上,第二个62神经元到第二个数字上,以此类推。这样,对于一个数字 $x_i$神经元索引n被计算成 $ n=i * 62 + \theta(x_i) $,其中$ i \in {0,…,5} $是数字索引,例如,output layer具有$ 6 * 62 = 372 $个神经元。为了预测一个数字,我们考虑相应的62个神经元,并将它们归一化成总和(sum)为1. 图4展示了一个神经网络输出的示例。这里,对于首个数字的预测字符索引(predicted character index)是$c_0=52$,预测标签为$ x=\theta^{-1}(c_0)=’q’$。

图4. 对于CAPTCHA “qnnivm”的神经网络样本输出. 左图:每个数字有62个输出。黑箱展示了第一个数字的输出。右图:第一个数字的概率分布。总和归一化为1.

4.使用 Active Learning来减少所需训练数据

为了获得一个好的分类accuracy,CNNs通常需要一个非常大的训练集。然而,收集数百万的人工标注的CAPTCHAs是不可行的。因而,我们提出了使用Active Learning(见图3)。主要思想是,只有在必要时才添加新的训练数据,例如,如果样本的信息量足够用于重新训练(re-learning)。这个决定是基于预测文本的不确定性,它会使用best-versus-secnond-best的策略来计算。

图3. Active Learning流程图. 我们首先在一个小的数据集上训练。接着,分类器被应用到一些新数据上,产生一个label prediction和一个相关的不确定度。有了该不确定度,分类器可以决定是否请求一个ground truth。在我们的case中,该query的完成通过使用prediction来解决给定的CAPTCHA,以及使用正确分类的样本。接着训练数据会增加,learning会被再次执行。在我们的方法中,我们使用一个deep CNN,它可以使用新加的训练样本被更有效的重训练。

4.1 获取不确定性

如上所述,通过将相应的网络输出的求和归一化为1,我们可以估计每个数字的预测分布。这样我们可以使用”best-vs-second-best”来计算整体的不确定度$ \eta $:

…(2)

其中,$P(x_i)$是数字$d_i$所对应的所有网络输出集。这样,我们通过对每个数字的最佳预测(best prediction)来分割第二佳预测(second-best)。

4.2 查询groud truth信息

我们的CAPTCHA识别问题是场景独特的:无需人工交互就可以执行学习。我们通过只使用这些数据样本进行重新训练(re-training)即可完成这一点:分类器已经为它们提供了一个正常label。然而,简单使用所有这些正确分类的样本进行re-training将非常低效。事实上,训练会越来越频繁,因为分类器越来越好,因而会将这些样本正确分类。为了避免这一点,我们使用不确定值来表示上述情况:在每个learning round通过预测不确定度来区分正确分类的测试样本,以及使用最不确定的样本来进行retraining。我们在试验中发现,这种方法会产生了一个更小规模的训练样本,最不确定的样本对于学习来说信息量越大。

5.实验评估

我们在自动生成CAPTCHAs上试验了我们的方法。所有实验都使用caffe框架在NVIDIA GeForce GTC 750 Ti GPU上执行。

5.1 数据集生成

由于没有人工标注好的CAPTCHA数据集,我们使用脚本来生成CAPTCHAs。在自动生成期间,我们确保它在数据集上没有重复。

我们使用Cool PHP CAPTHCA框架来生成CAPTCHAs。它们由固定长度6个歪曲文本组成,类似于reCAPTCHA。它们具有size:180 x 50. 我们修改了该框架让它生成黑白色的图片。另外,我们已经禁止了阴影(shadow)和贯穿文本的线。我们也没有使用字典词,而是使用随机字符。因此,我们已经移除了该规则:每个第二字符必须是元音字符(vowel)。我们的字体是:“AntykwaBold”。图5展示了生成的一些样本。

图5: 实验中所使用的CAPTCHAs样本

5.2 网络的设计

我们使用如图2所示的网络。

  • 卷积层(conv layers)具有的size为:48, 64和128. 它们具有一个kernel size: 5x5,padding size:2。
  • pooling layers的window size为2x2。
  • 第一个和第三个pooling layers,还有第一个conv layer的stride为2.
  • 该网络有一个size=3072的fully connected layer,还有一个二级的fully connected layer(分类器)具有output size=372.

我们也在每个卷积层和第一个fully conntected layer上添加了ReLU和dropout。每次迭代的batch size为:64.

5.3 量化评估

我们使用SGD来训练网络。然而,对比其它方法,我们以独立的方式为所有数字训练该网络。learning rate通过$ \alpha = \alpha_{0} * (1+\gamma * t)^{-\beta} $的方式变更,其中,基础的learning rate为$ \alpha_{0} = 10 ^{-2}$,$ \beta=0.75, \gamma=10^{-4}$,其中,t为当前迭代轮数。我们设置momentum $ \mu=0.9 $,正则参数$\lambda=5 * 10^{-4} $。

最昂贵的部分是获取训练样本,我们的方法的目标是,降小初始训练集所需的size。因而,我们首先使用一个非常小的初始训练集(含10000张图片)来进行 $5 * 10^4$迭代。我们只达到9.6%的accuracy(迭代越大甚至会降低accuracy)。因而,我们希望使用Active Learning。

首先,我们再次使用含10000张图片的初始训练集进行 $5 * 10^4$迭代。然后,我们分类 $5 * 10^4$ 张测试图片。接着,我们从正确分类的数据中选取新的训练样本。我们可以全取,或者基于不确定度(uncertainty)只取$5 * 10^3$个样本:即有最高的不确定度,最低的不确定度,或者随机。不确定度的计算如4.1节所述。一旦新的选中的样本被添加到训练集中,我们重新训练该网络$5 * 10^4$迭代。接着,我们遵循相同的过程。我们在总共20次Active learning rounds rounds(epoch)中应用该算法。在每次$5 * 10^3$迭代后,在一个固定的验证集上计算accuracy。我们在正确但不确定的预测上获取了最好的表现(见图6)。所有的结果是两种运行的平均。

图6: Active Deep Learning的学习曲线. 上图:训练集在每次迭代后随样选中样本的增加而增加。当使用所有正确的样本时(黑色曲线),在$ 50 \dot 10^4 $我们停止向训练集添加新的图片,因为训练集的size已经超过了 $ 3 \dot 10^6 $。 下图:只在新样本上重新训练该网络。竖直的黑线表示每轮Active Learning epoch的结束。

然而,在训练集上增加样本数需要存储。再者,增加迭代次数可以从累积的集合上受益,但它会占据更长的训练时间。对于所有这些原因,我们建议:在每次迭代进行重训练网络时,只使用选中的样本。因而,我们再次使用使用含10000张图片的初始训练集进行 $5 \dot 10^4$迭代训练。接着,对$10^5$次测试图片进行分类,使用$10^4$正确分类的图片进行替换,并再训练$2.5 \dot 10^5$。接着,我们遵循该过程,根据下面的规则来减小迭代次数:在6轮前使用$2.5 \dot 10^4$,在6-11轮使用$2 \dot 10^4$,在11-16轮使用$1.5 \dot 10^4$,在16-21轮使用$ 1 \dot 10^4$,在21-40轮使用$5 \dot 10^3$。我们再次使用正确但不确定的预测来获取最好的表现(见图6)。这是合理的,因为该网络会正确分类图片,仍对预测仍非常不确定。因而,它可以事实上学到:它对于分类确定是正确的。一旦有争议:误分类样本的学习应产生更好的结果。事实上应该如此,然而实际上并不可能。

参考

在google 发表的paper: 《Label Partitioning For Sublinear Ranking》中,有过介绍:

一、介绍

许多任务的目标是:对一个巨大的items、documents 或者labels进行排序,返回给其中少量的top K给用户。例如,推荐系统任务,比如:通过协同过滤,需要对产品(比如:电影或音乐)的一个大集合,根据给定的user profile进行排序。对于注解任务(annotation),比如:对图片进行关键词注解,需要通过给定的图片像素,给出的可能注解的一个大集合进行排序。最后,在信息检索中,文档的大集合(文本、图片or视频)会基于用户提供的query进行排序。该paper会涉及到实体(items, documents, 等),被当作labels进行排序,所有上述的问题都看成是标签排序问题(label ranking problem)。在机器学习界中,提出了许多强大的算法应用于该领域。这些方法通常会通过对每个标签(label)依次进行打分(scoring)后根据可能性进行排序,可以使用比如SVM, 神经网络,决策树,其它流行方法等。我们将这些方法称为标签打分器(label scorers)。由于对标签打分是独立进行的,许多这些方法的开销与label的数量上是成线性关系的。因而,不幸的是,当标签数目为上百万或者更多时变得不实际,在serving time时会很慢。

本paper的目标是:当面临着在现实世界中具有海量的labels的情况时,让这些方法变得实用。这里并没有提出一种新方法来替换你喜欢的方法,我们提出了一个”wrapper”方法,当想继续维持(maintaining)或者提升(improve) accuracy时,这种算法能让这些方法更容易驾驭。(注意,我们的方法会改善测试时间,而非训练时间,作为一个wrapper方法,在训练时实际不会更快)

该算法首先会将输入空间进行划分,因而,任意给定的样本可以被映射到一个分区(partition)或者某分区集合(set of partitions)中。在每个分区中,只有标签的一个子集可以由给定的label scorer进行打分。我们提出该算法,用于优化输入分区,以及标签如何分配给分区。两种算法会考虑选择label scorer,来优化整体的precision @ k。我们展示了如何不需考虑这些因素,比如,label scorer的分区独立性,会导致更差的性能表现。这是因为当标签分区时(label partitioning),对于给定输入,最可能被纠正(根据ground truth)的是labels的子集,原始label scorer实际上表现也不错。我们的算法提供了一个优雅的方式来捕获这些期望。

本paper主要:

  • 引入通过label partitioning,在一个base scorer上进行加速的概念
  • 对于输入划分(input partitioning),我们提供了一个算法来优化期望的预测(precision@K)
  • 对于标签分配(label assignment),我们提供了一个算法来优化期望的预测(precision@K)
  • 应用在现实世界中的海量数据集,来展示该方法

二、前置工作

有许多算法可以用于对标签进行打分和排序,它们与label set的size成线性时间关系。因为它们的打分操作会依次对每个label进行。例如,one-vs-rest方法,可以用于为每个label训练一个模型。这种模型本身可以是任何方法:线性SVM,kernel SVM,神经网络,决策树,或者其它方法。对于图片标注任务,也可以以这种方法进行。对于协同过滤,一个items的集合可以被排序,好多人提出了许多方法应用于该任务,也是通常依次为每个item进行打分,例如:item-based CF,latent ranking模型(Weimer et al.2007),或SVD-based系统。最终,在IR领域,会对一个文档集合进行排序,SVM和神经网络,以及LambdaRank和RankNet是流行的选择。在这种情况下,不同于注解任务通常只会训练单个模型,它对输入特征和要排序的文档有一个联合表示,这样可以区别于one-vs-test训练法。然而,文档仍然会在线性时间上独立打分。本paper的目标是,提供一个wrapper方法来加速这些系统。

有许多算法用来加速,这些算法取决于对输入空间进行hashing,比如通过局部敏感哈希(LSH: locality-sensitive hashing),或者通过构建一棵树来完成。本文则使用分区的方法来加速label scorer。对于该原因,该方法可以相当不同,因为我们不需要将样本存储在分区上(来找到最近邻),我们也不需要对样本进行划分,而是对label进行划分,这样,分区的数目会更小。

在sublinear classification schemes上,近期有许多方法。我们的方法主要关注点在ranking上,而非classification上。例如:label embedding trees(bengio et al.,2010)可以将label划分用来正确分类样本,(Deng et al.,2011)提出一种相似的改进版算法。其它方法如DAGs,filter tree, fast ECOC,也主要关注在快速分类上。尽管如此,我们的算法也可以运行图片标注任务。

3.Label Partitioning

给定一个数据集: pairs $(x_i, y_i), i=1, …, m $. 在每个pair中,$ x_i $是输入,$ y_i $是labels的集合(通常是可能的labels D的一个子集)。我们的目标是:给定一个新的样本 $ x^{*} $, 为整个labels集合D进行排序,并输出top k给用户,它们包含了最可能相关的结果。注意,我们提到的集合D是一个”labels”的集合,但我们可以很容易地将它们看成是一个关于文档的集合(例如:我们对文本文档进行ranking),或者是一个items的集合(比如:协同过滤里要推荐的items)。在所有情况下,我们感兴趣的问题是:D非常大,如果算法随label集合的size规模成线性比例,那么该算法在预测阶段并不合适使用。

假设用户已经训练了一个label scorer: $f(x,y)$, 对于一个给定的输入和单个label,它可以返回一个real-valued型的分值(score)。在D中对这些labels进行ranking,可以对所有$ y \in D$,通过简单计算f(x,y)进行排序来执行。这对于D很大的情况是不实际的。再者,在计算完所有的f(x,y)后,你仍会另外做sorting计算,或者做topK的计算(比如:使用一个heap)。

我们的目标是:给定一个线性时间(或更差)的label scorer: f(x,y),能让它在预测时更快(并保持或提升accuracy)。我们提出的方法:label partitioning,有两部分构成:

  • (i)输入分区(input partititoner): 对于一个给定的样本,将它映射到输入空间的一或多个分区上
  • (ii)标签分配(label assignment): 它会为每个分区分配labels的一个子集

对于一个给定的样本,label scorer只会使用在相对应分区的labels子集,因此它的计算更快。

在预测时,对这些labels进行ranking的过程如下:

  • 1.给定一个测试输入x,input partitioner会将x映射到partitions的某一个集合中: $ p=g(x) $
  • 2.我们检索每个被分配到分区 $ p_j $上的标签集合(label sets):$$ L = \bigcup_{j=1}^{ p } \mathscr{L}{p_j} \mathscr{L}{p_j} \subseteq D $$是分配给分区 $ p_j $的标签子集。
  • 3.使用label scorer函数$ f(x,y) $对满足$ y \in L $的labels进行打分,并对它们进行排序来产生我们最终的结果

在预测阶段ranking的开销,已经被附加在将输入分配到对应分区(通过计算$ p=g(x) $来得到)上的开销;以及在相对应的分区上计算每个label(计算: $ f(x,y), y \in L $)。通过使用快速的input partitioner,就不用再取决于label set的size大小了(比如:使用hashing或者tree-based lookup)。提供给scorer的labels set的大小是确定的,相对小很多(例如:$ |L| « |D| $),我们可以确保整个预测过程在$ |D| $上是亚线性(sublinear)的。

3.1 输入分区(Input Partitioner)

我们将如何选择一个输入分区(input partitioner)的问题看成是:$ g(x) \rightarrow p \subseteq \mathcal{P} $,它将一个输入点x映射到一个分区p的集合中,其中P是可能的分区:$ \mathcal{P} = \lbrace 1,…,P \rbrace $。g总是映射到单个整数上,因而,每个输入只会映射到单个分区,但这不是必须的。

有许多文献适合我们的input partitioning任务。例如:可以使用最近邻算法作为input partitioner,比如,对输入x做hashing(Indyk & Motwani, 1998),或者tree-based clustering和assignment (e.g. hierarchical k-means (Duda et al., 1995),或者KD-trees (Bentley, 1975),这些方法都可行,我们只需关注label assignment即可。然而,注意,这些方法可以对我们的数据有效地执行完全非监督式划分分区(fully unsupervised partitioning),但不会对我们的任务的唯一需求考虑进去:即我们希望在加速的同时还要保持accuracy。为了达到该目标,我们将输入空间进行分区:让具有相似相关标签(relevant labels:它们通过label scorer进行高度排序)的相应样本在同一个分区内

我们提出了一种层次化分区(hierarchical partitioner)的方法,对于:

  • 一个标签打分函数(label scorer):$f(x,y)$
  • 一个训练集:$(x_i,y_i), i=\lbrace 1,…,m \rbrace $,(注:x为input,y为label)
  • 之前定义的label集合D

它尝试优化目标:precision@k。对于一个给定的训练样本$(x_i,y_i)$以及label scorer,我们定义了:

accuracy的measure(比如:precision@k)为:

以及最小化loss为:

注意,上述的f(x)是对所有labels的得分向量(f(x)与f(x,y)不同):

其中$ D_i $是整个label set上的第i个label。然而,为了衡量label partitioner的loss,而非label scorer,我们需要考虑$l(f_{g(x_i)}(x_i), y_i)$,该值为ranking时$x_i$对应的分区上的label set的loss。比如:$ f_{g(x)}(x)=(f(x,L_1),…,f(x,L_{|L|)})) $

对于一个给定的分区,我们定义它的整个loss为:

不幸的是,当训练输入分区(input partitioner)时,L(label assignments)是未知的,它会让上述的目标函数不可解(infeasible)。然而,该模型发生的errors可以分解成一些成分(components)。对于任意给定的样本,如果发生以下情况,它的precision@k会收到一个较低值或是0:

  • 在一个分区里,相关的标签不在该集合中
  • 原始的label scorer在排第一位的分值就低

当我们不知道label assignment时,我们将会把每个分区上labels的数目限制在一个相对小的数($ |L_j|«|D| $)。实际上,我们会将考虑两点来定义标签分区(label partitioner):

  • 对于共享着高度相关标签的样本,应被映射到相同的分区上
  • 当学习一个partitioner时,对于label scorer表现好的样本,应被优先(prioritized)处理

基于此,我们提出了方法来进行输入分区(input partitioning)。让我们看下这种情况:假如定义了分区中心(partition centroids) $c_i, i=1,…,P$,某种划分,它使用最接近分配的分区:

这可以很容易地泛化到层次化的情况中(hierarchical case),通过递归选择子中心(child centroids)来完成,通常在hierarchical k-means和其它方法中使用。

加权层次化分区(Weighted Hierarchical Partitioner) ,这是一种来确保输入分区(input partitioner)对于那些使用给定label scorer表现较好的样本(根据precision)进行优先处理的简单方法。采用的作法是,对每个训练样本进行加权:

实际上,一个基于该目标函数的层次化分区(hierarchical partitioner),可以通过一个“加权(weighted)”版本的 hierarchical k-means来完成。在我们的实验中,我们简单地执行一个”hard”版本:我们只在训练样本集合 $ \lbrace (x_i,y_i): \hat{l}(f(x_i),y_i) \geq \rho \rbrace $上运行k-means,取ρ = 1。

注意,我们没有使用 $ l(f_{g(x_i)}(x_i), y_i) $, 而是使用$ l(f(x_i),y_i) $,但它是未知的。然而,如果$ y_i \in L_{g(x_i)}$,则:$ l(f_{g(x_i)}(x_i), y_i) \leq l(f_D(x_i),y_i) $,否则,$ l(f_{g(x_i)}(x_i), y_i)=1$。也就是说,我们使用的proxy loss,上界逼近真实值,因为比起完整的集合,我们只有很少的label,因而precision不能降低——除非真实label不在分区中。为了阻止后面的情况,我们必须确保具有相似label的样本在同一个分区中,我们可以通过学习一个合适的metrics来完成。

加权嵌入式分区(Weighted Embedded Partitioners), 在上述构建加权层次式分区器(weighted hierarchical partitioner)时,我们可以更进一步,引入约束(constraint):共享着高度相关labels的样本会被映射到同一个分区(partitioner)上。编码这些constraint可以通过一种metric learning阶段来完成(Weinberger et al., 2006).。

接着,你可以学习一个input partitioner,通过使用上面的weighted hierarchical partitioner目标函数,在要学的”embedding”空间上处理:

然而,一些label scorer已经学到了一个latent “embedding” space。例如,SVD和LSI等模型,以及一些神经网络模型(Bai et al., 2009). 在这样的case中,你可以在隐空间(latent space)上直接执行input partitioning,而非在输入空间上;例如:如果label scorer模型的形式是:$ f(x,y)= \Phi_{x}(x)^T \Phi_{y}(y) $,那么partitioning可以在空间 $ \Phi_x(x) $上执行。这同样可以节省计算两个embeddings(一个用于label partitioning,一个用于label scorer)的时间,在特征空间中的进一步分区则为label scorer调整。

3.2 Label Assignment

本节将来看下如何选择一个L(label assignment)。

  • 训练集$ (x_i,y_i), i=1,…,m $,label set为:D
  • input partitioner: g(x),使用之前的方式构建
  • 线性时间label scorer: f(x,y)

我们希望学到label assignment: $ L_j \subseteq D $,第j个分区对应的label set。我们提出的label assignment方法会应用到每个分区中。首先,来考虑下优化precision@1的情况,这种简化版的case中,每个样本只有一个相关的label。这里我们使用索引t来索引训练样本,相关的label为$ y_t $。我们定义:$ \alpha \in \lbrace 0,1 \rbrace^{|D|}$,其中$ \alpha_{i} $决定着一个label $ D_i $是否会被分配到该分区上($ \alpha_{i}=1 $),或不分配($ \alpha_{i}=0 $)。这里的$ \alpha_{i} $就是我们希望优化的变量。接下去,我们通过给定的label scorer对rankings进行编码:

  • $ R_{t,i} $是对于样本t的label i的rank分值:
  • $ R_{t,y_t} $是样本t的true label的rank分值

我们接着将需要优化的目标函数写出来:

…(1)

服从:

…(2)

…(3)

其中,C是分配给该分区的label数。对于一个给定的样本t,为了最大化precision@1,需满足两个条件:

  • (1) true label必须被分配给该分区
  • (2) true label必须是所有被分配labels上排序分值最高的

我们可以看到,等式1可以精确计算precision@1,因为项$ \alpha_{y_t} $和$ (1-max_{R_{t,i}<R_{t,y_t}} \alpha_{i}) $ 会对这两个条件各自进行measure。我们的目标函数会统计训练样本数precision@1。

有意思的是,注意,label partitioning的性质意味着:

  • (i) 如果训练样本t在原始的label scorer上标记不正确,但由于高度不相关的label不会被分配到该分区上,会被label partitioner正确标注
  • (ii) 原始的label scorer可以正确标注样本,但由于相关的label没有被分配到该分区上,会被label partitioner标注不正确

该优化问题,尽可能地将多个相关的label放在同一分区中,并且尽可能消除尽可能混淆的labels(高排序值但不正确),如果通过移除它们,更多的样本会被正确标注。如图1所示:

图1: 如何从D中选择2个labels的label assignment问题,只考虑它的precision@1。这里的$ R_i $是样本排序后的labels(粗体为true labels)。当选择为sky时,会正确预测样本1和2;而对于样本3-5,sky比true labels的排序还要高。最优的选择是car和house,它们在样本3-5中可以被正确预测,因为所有有更高排序但不相关labels(higher-ranked irrelevant labels)会被抛弃掉。这种选择问题就是我们在label assignment任务中要面临的挑战。

不幸的是,等式2的二元限制(binary constraint)致使等式(1)的最优化变得很难,但我们可以将约束放松些:

…(4)

$ \alpha $的值不再离散(discrete),我们不会使用等式(3)的约束,但在训练后会对连续值$ \alpha_{i}$做排序,会采用最大的C label作为分区的成员。

我们将上述泛化成pricision@k(k>1)的情况。如果至少一个“不相关(violating)”的label排在相关label之上,我们必须统计排在相关label之上的violations的数目。回到未放松约束的最优化问题上,我们有:

…(5)

服从:

…(6)

这里对于precision@k的优化,如果 r<k,我们可以简单地取$ \Phi(r) = 0 $,否则取1。

我们已经讨论了具有一个相关标签的情况,但在许多情况下,样本具有多个相关标签的情况是很常见的,它可以使得loss的计算变得稍微更具挑战性些。我们回到precision@1的情况。在这种情况下,原始的目标函数(等式(1))将返回为:

…(7)

服从:

…(8)

这里,$ y_t $包含着许多相关标签 $ y \in y_t $,如果它们中的所有都是排在前面的(top-ranked),那么会得到一个precision@1为1,这样我们可以取 $ max_{y \in y_t}$

我们可以结合等式(5)和等式(7)来形成一个关于precision@k的cost function,用于multi-label的训练样本上。为了更适合优化,我们使用一个sigmoid来将在等式(7)中的约束$max_{y \in y_t}$放松到一个均值和近似值 $ \Phi(r) $:

我们的目标接着变成:

…(9)

服从:

…(10)

对于单个样本,期等的目标是一个相关label出现在top k中。然而,当penalty不会影响真实排序位置的情况下不成立(例如:我们原始的cost等价于在位置k+1的排序,或者在位置$|D|$的位置)。早前我们希望那些label scorer的执行很差的样本降低其重要性。为了达到该目的,我们引入了一个带加权项(term weighting)的样本,通过使用原始label scorer得到的相关label排序的反序来实现,等式(4)和等式(9)变为:

这里我们作了简化:$w(R_{t,y}) = (R_{t,y})^{\lambda}, \lambda \geq 0 $,在我们的试验中,设置$\lambda=1$(该值越高会抑制具有更低排序的相关label的样本)。这些等式表示了label assignment objective的放宽条件版本的最终形式,可以使用SGA(随机梯度上升:A: ascent)进行优化。

最优化注意事项(Optimization Considerations) 我们考虑这样的情况,被选中的输入分区g(x),表示每个输入x映射到单个分区上。每个分区的label assignment问题是独立的,这允许它们可以并行的求解(例如:使用MapReduce框架)。为了进一步减小训练时间,对于每个分区我们在完整label set上的一个子集上进行优化(例如:选择 $ \hat{D} \subseteq D, C < |\hat{D}| < |D| $)。对于每个分区,我们选择$ \hat{D} $:它是在该分区的训练样本中使用原始label scorer进行排序的最高排序的相关label。在所有的实验中,我们设置$ | \hat{D} | = 2C $。注意,在我们的实验中,我们发现设置成$ | \hat{D} | = 2C $后减少参数集的size,影响可忽略不计。原因是,任何分区中在任何训练样本中,在D中大部分labels不会作为相关labels出现。因为这样的labels不会接受任何正值的梯度更新。

统计Heuristic baseline 通过比较我们提出的label assignment的最优化,在我们的实验中,我们也考虑了一个更简单的Heuristic:只考虑等式(1)的第一项,例如:$ max_{\alpha} \sum_{t} \alpha_{t_t}$。这种情况下,最优化可以简化为:只需统计在分区中的每个true label的出现次数,并让C保持为最多的labels。这种基于统计的assignment提供了一个很好的baseline,来对比我们提出的优化。

4.实验

4.1 图像注解

首先使用ImageNet数据集来测试图片注解任务。ImageNet是一个很大的图片数据集,它将人口验证通过的图片与WordNet的概念相绑定。我们使用Spring 2010的版本,它具有9M的images,我们使用:10%用于validation, 10%用于test,80%用于training。该任务会对15589个可能的labels做rank,它们的范围从animals(“white admiral butterfly”)到objects(“refracting telescope”).

…【略】

4.2 视频推荐

从一个大型在线视频社区给用户推荐视频。上百万最流行的视频被认为是集合D,我们的目标是,对一个给定用户排序这些视频,并提供给该用户相关的视频。训练数据的格式中每个训练pair都基于一个匿名用户。对于每个用户,输入$x_i$是表示他的偏好的一个特征集合。这些特征通过聚合每个用户所感兴趣的所有视频的主题来生成。这些主题集合接着被聚类成各特征列。有2069个这样的聚类特征列(clusters)来表示用户,其中任何时候有10个聚类特征列是表示活跃的(意思:每个用户大致都有10个以上的特征)。label $y_i$是已知相关视频的一个集合。该数据集包含了1亿的样本,每个样本具有2069个输入特征,平均接近有10个相关视频。我们设置另外50w的样本用于validation,1M样本用于test。

我们的baseline label scorer $W_{SABIE}$在P@10上对比于Naive Bayes,它给出了108%的提升。因而,baseline已经足够强了。我们接着使用hierarchical k-means,它具有10000个分区,以及许多种label assignment set sizes,结果如表2所示。我们的方法可以提速990x倍,而在label scorer上的P@10提升13%。该结果和我们见到的一样重要:我们使用的label scorer是一个线性模型,其中label partitioner在某种程度上是“非线性”的:它可以在输入空间的不同分区上更改label sets——这可以纠正原始scorer的错误(在某种程度上,这有点像个re-ranker)。注意基于最优化的label partitioner比counting heuristic效果要好。

表2

我们的label partitioner被用于视频推荐系统中,用来尝试提升一个比较强的baseline ML系统。在我们的上述实验中使用的是precision,但precision只是一个online metrics,而在观看期视频的ctr作为衡量更好。当在实际系统中评估label partitioner时,它可以在ctr和观看时长(接近2%)上获得极大的提升。注意,我们不会将它与原始的label scorer做比较,那种情况下使用它是不可行的。

5.结论

我们提出了一种“wrapper”方法来加速label scoring rankers。它使用一种新的优化法:通过学习一个input partitioning和label assignment,来胜过其它baseline。该结果与原始的label scorer效果相似(或者效果更好),同时运行更快。这使得该技术被用于现实的视频推荐系统中。最终,我们我们觉得提出的label assignment是解决该问题的好方法,input partitioners间的巨大性能差距意味着,将来还有重大问题需要解决。

参考

Label Partitioning For Sublinear Ranking

机器学习中的许多模型中,对类别型变量,常作的处理是,将它们编码成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编码.

参考