{"action":"created","comment":{"url":"https://api.github.com/repos/apache/spark/pulls/comments/75349924","id":75349924,"diff_hunk":"@@ -0,0 +1,611 @@\n+/*\n+ * Licensed to the Apache Software Foundation (ASF) under one or more\n+ * contributor license agreements.  See the NOTICE file distributed with\n+ * this work for additional information regarding copyright ownership.\n+ * The ASF licenses this file to You under the Apache License, Version 2.0\n+ * (the \"License\"); you may not use this file except in compliance with\n+ * the License.  You may obtain a copy of the License at\n+ *\n+ *    http://www.apache.org/licenses/LICENSE-2.0\n+ *\n+ * Unless required by applicable law or agreed to in writing, software\n+ * distributed under the License is distributed on an \"AS IS\" BASIS,\n+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n+ * See the License for the specific language governing permissions and\n+ * limitations under the License.\n+ */\n+\n+package org.apache.spark.ml.classification\n+\n+import scala.collection.mutable\n+\n+import breeze.linalg.{DenseVector => BDV}\n+import breeze.optimize.{CachedDiffFunction, LBFGS => BreezeLBFGS, OWLQN => BreezeOWLQN}\n+import org.apache.hadoop.fs.Path\n+\n+import org.apache.spark.SparkException\n+import org.apache.spark.annotation.{Experimental, Since}\n+import org.apache.spark.internal.Logging\n+import org.apache.spark.ml.feature.Instance\n+import org.apache.spark.ml.linalg._\n+import org.apache.spark.ml.param._\n+import org.apache.spark.ml.param.shared._\n+import org.apache.spark.ml.util._\n+import org.apache.spark.mllib.linalg.VectorImplicits._\n+import org.apache.spark.mllib.stat.MultivariateOnlineSummarizer\n+import org.apache.spark.rdd.RDD\n+import org.apache.spark.sql.{Dataset, Row}\n+import org.apache.spark.sql.functions.{col, lit}\n+import org.apache.spark.sql.types.DoubleType\n+import org.apache.spark.storage.StorageLevel\n+\n+/**\n+ * Params for multinomial logistic (softmax) regression.\n+ */\n+private[classification] trait MultinomialLogisticRegressionParams\n+  extends ProbabilisticClassifierParams with HasRegParam with HasElasticNetParam with HasMaxIter\n+    with HasFitIntercept with HasTol with HasStandardization with HasWeightCol {\n+\n+  /**\n+   * Set thresholds in multiclass (or binary) classification to adjust the probability of\n+   * predicting each class. Array must have length equal to the number of classes, with values >= 0.\n+   * The class with largest value p/t is predicted, where p is the original probability of that\n+   * class and t is the class' threshold.\n+   *\n+   * @group setParam\n+   */\n+  def setThresholds(value: Array[Double]): this.type = {\n+    set(thresholds, value)\n+  }\n+\n+  /**\n+   * Get thresholds for binary or multiclass classification.\n+   *\n+   * @group getParam\n+   */\n+  override def getThresholds: Array[Double] = {\n+    $(thresholds)\n+  }\n+}\n+\n+/**\n+ * :: Experimental ::\n+ * Multinomial Logistic (softmax) regression.\n+ */\n+@Since(\"2.1.0\")\n+@Experimental\n+class MultinomialLogisticRegression @Since(\"2.1.0\") (\n+    @Since(\"2.1.0\") override val uid: String)\n+  extends ProbabilisticClassifier[Vector,\n+    MultinomialLogisticRegression, MultinomialLogisticRegressionModel]\n+    with MultinomialLogisticRegressionParams with DefaultParamsWritable with Logging {\n+\n+  @Since(\"2.1.0\")\n+  def this() = this(Identifiable.randomUID(\"mlogreg\"))\n+\n+  /**\n+   * Set the regularization parameter.\n+   * Default is 0.0.\n+   *\n+   * @group setParam\n+   */\n+  @Since(\"2.1.0\")\n+  def setRegParam(value: Double): this.type = set(regParam, value)\n+  setDefault(regParam -> 0.0)\n+\n+  /**\n+   * Set the ElasticNet mixing parameter.\n+   * For alpha = 0, the penalty is an L2 penalty. For alpha = 1, it is an L1 penalty.\n+   * For 0 < alpha < 1, the penalty is a combination of L1 and L2.\n+   * Default is 0.0 which is an L2 penalty.\n+   *\n+   * @group setParam\n+   */\n+  @Since(\"2.1.0\")\n+  def setElasticNetParam(value: Double): this.type = set(elasticNetParam, value)\n+  setDefault(elasticNetParam -> 0.0)\n+\n+  /**\n+   * Set the maximum number of iterations.\n+   * Default is 100.\n+   *\n+   * @group setParam\n+   */\n+  @Since(\"2.1.0\")\n+  def setMaxIter(value: Int): this.type = set(maxIter, value)\n+  setDefault(maxIter -> 100)\n+\n+  /**\n+   * Set the convergence tolerance of iterations.\n+   * Smaller value will lead to higher accuracy with the cost of more iterations.\n+   * Default is 1E-6.\n+   *\n+   * @group setParam\n+   */\n+  @Since(\"2.1.0\")\n+  def setTol(value: Double): this.type = set(tol, value)\n+  setDefault(tol -> 1E-6)\n+\n+  /**\n+   * Whether to fit an intercept term.\n+   * Default is true.\n+   *\n+   * @group setParam\n+   */\n+  @Since(\"2.1.0\")\n+  def setFitIntercept(value: Boolean): this.type = set(fitIntercept, value)\n+  setDefault(fitIntercept -> true)\n+\n+  /**\n+   * Whether to standardize the training features before fitting the model.\n+   * The coefficients of models will be always returned on the original scale,\n+   * so it will be transparent for users. Note that with/without standardization,\n+   * the models should always converge to the same solution when no regularization\n+   * is applied. In R's GLMNET package, the default behavior is true as well.\n+   * Default is true.\n+   *\n+   * @group setParam\n+   */\n+  @Since(\"2.1.0\")\n+  def setStandardization(value: Boolean): this.type = set(standardization, value)\n+  setDefault(standardization -> true)\n+\n+  /**\n+   * Sets the value of param [[weightCol]].\n+   * If this is not set or empty, we treat all instance weights as 1.0.\n+   * Default is not set, so all instances have weight one.\n+   *\n+   * @group setParam\n+   */\n+  @Since(\"2.1.0\")\n+  def setWeightCol(value: String): this.type = set(weightCol, value)\n+\n+  @Since(\"2.1.0\")\n+  override def setThresholds(value: Array[Double]): this.type = super.setThresholds(value)\n+\n+  override protected[spark] def train(dataset: Dataset[_]): MultinomialLogisticRegressionModel = {\n+    val w = if (!isDefined(weightCol) || $(weightCol).isEmpty) lit(1.0) else col($(weightCol))\n+    val instances: RDD[Instance] =\n+      dataset.select(col($(labelCol)).cast(DoubleType), w, col($(featuresCol))).rdd.map {\n+        case Row(label: Double, weight: Double, features: Vector) =>\n+          Instance(label, weight, features)\n+      }\n+\n+    val handlePersistence = dataset.rdd.getStorageLevel == StorageLevel.NONE\n+    if (handlePersistence) instances.persist(StorageLevel.MEMORY_AND_DISK)\n+\n+    val instr = Instrumentation.create(this, instances)\n+    instr.logParams(regParam, elasticNetParam, standardization, thresholds,\n+      maxIter, tol, fitIntercept)\n+\n+    val (summarizer, labelSummarizer) = {\n+      val seqOp = (c: (MultivariateOnlineSummarizer, MultiClassSummarizer),\n+       instance: Instance) =>\n+        (c._1.add(instance.features, instance.weight), c._2.add(instance.label, instance.weight))\n+\n+      val combOp = (c1: (MultivariateOnlineSummarizer, MultiClassSummarizer),\n+        c2: (MultivariateOnlineSummarizer, MultiClassSummarizer)) =>\n+          (c1._1.merge(c2._1), c1._2.merge(c2._2))\n+\n+      instances.treeAggregate(\n+        new MultivariateOnlineSummarizer, new MultiClassSummarizer)(seqOp, combOp)\n+    }\n+\n+    val histogram = labelSummarizer.histogram\n+    val numInvalid = labelSummarizer.countInvalid\n+    val numFeatures = summarizer.mean.size\n+    val numFeaturesPlusIntercept = if (getFitIntercept) numFeatures + 1 else numFeatures\n+\n+    val numClasses = MetadataUtils.getNumClasses(dataset.schema($(labelCol))) match {\n+      case Some(n: Int) =>\n+        require(n >= histogram.length, s\"Specified number of classes $n was \" +\n+          s\"less than the number of unique labels ${histogram.length}\")\n+        n\n+      case None => histogram.length\n+    }\n+\n+    instr.logNumClasses(numClasses)\n+    instr.logNumFeatures(numFeatures)\n+\n+    val (coefficients, intercepts, objectiveHistory) = {\n+      if (numInvalid != 0) {\n+        val msg = s\"Classification labels should be in {0 to ${numClasses - 1} \" +\n+          s\"Found $numInvalid invalid labels.\"\n+        logError(msg)\n+        throw new SparkException(msg)\n+      }\n+\n+      val labelIsConstant = histogram.count(_ != 0) == 1\n+\n+      if ($(fitIntercept) && labelIsConstant) {\n+        // we want to produce a model that will always predict the constant label\n+        (Matrices.sparse(numClasses, numFeatures, Array.fill(numFeatures + 1)(0), Array(), Array()),\n+          Vectors.sparse(numClasses, Seq((numClasses - 1, Double.PositiveInfinity))),\n+          Array.empty[Double])\n+      } else {\n+        if (!$(fitIntercept) && labelIsConstant) {\n+          logWarning(s\"All labels belong to a single class and fitIntercept=false. It's\" +\n+            s\"a dangerous ground, so the algorithm may not converge.\")\n+        }\n+\n+        val featuresStd = summarizer.variance.toArray.map(math.sqrt)\n+\n+        val regParamL1 = $(elasticNetParam) * $(regParam)\n+        val regParamL2 = (1.0 - $(elasticNetParam)) * $(regParam)\n+\n+        val bcFeaturesStd = instances.context.broadcast(featuresStd)\n+        val costFun = new LogisticCostFun(instances, numClasses, $(fitIntercept),\n+          $(standardization), bcFeaturesStd, regParamL2, multinomial = true)\n+\n+        val optimizer = if ($(elasticNetParam) == 0.0 || $(regParam) == 0.0) {\n+          new BreezeLBFGS[BDV[Double]]($(maxIter), 10, $(tol))\n+        } else {\n+          val standardizationParam = $(standardization)\n+          def regParamL1Fun = (index: Int) => {\n+            // Remove the L1 penalization on the intercept\n+            val isIntercept = $(fitIntercept) && ((index + 1) % numFeaturesPlusIntercept == 0)\n+            if (isIntercept) {\n+              0.0\n+            } else {\n+              if (standardizationParam) {\n+                regParamL1\n+              } else {\n+                val featureIndex = if ($(fitIntercept)) {\n+                  index % numFeaturesPlusIntercept\n+                } else {\n+                  index % numFeatures\n+                }\n+                // If `standardization` is false, we still standardize the data\n+                // to improve the rate of convergence; as a result, we have to\n+                // perform this reverse standardization by penalizing each component\n+                // differently to get effectively the same objective function when\n+                // the training dataset is not standardized.\n+                if (featuresStd(featureIndex) != 0.0) {\n+                  regParamL1 / featuresStd(featureIndex)\n+                } else {\n+                  0.0\n+                }\n+              }\n+            }\n+          }\n+          new BreezeOWLQN[Int, BDV[Double]]($(maxIter), 10, regParamL1Fun, $(tol))\n+        }\n+\n+        val initialCoefficientsWithIntercept = Vectors.zeros(numClasses * numFeaturesPlusIntercept)\n+\n+        if ($(fitIntercept)) {\n+          /*\n+             For multinomial logistic regression, when we initialize the coefficients as zeros,\n+             it will converge faster if we initialize the intercepts such that\n+             it follows the distribution of the labels.\n+             {{{\n+               P(0) = \\exp(b_0) / (\\sum_{k=1}^K \\exp(b_k))\n+               ...\n+               P(K) = \\exp(b_K) / (\\sum_{k=1}^K \\exp(b_k))\n+             }}}\n+             The solution to this is not identifiable, so choose the solution with minimum\n+             L2 penalty (i.e. subtract the mean). Hence,\n+             {{{\n+               b_k = \\log{count_k / count_0}\n+               b_k' = b_k - \\frac{1}{K} \\sum b_k\n+             }}}\n+           */\n+          val referenceCoef = histogram.indices.map { i =>\n+            if (histogram(i) > 0) {\n+              math.log(histogram(i) / (histogram(0) + 1)) // add 1 for smoothing\n+            } else {\n+              0.0\n+            }\n+          }\n+          val referenceMean = referenceCoef.sum / referenceCoef.length\n+          histogram.indices.foreach { i =>\n+            initialCoefficientsWithIntercept.toArray(i * numFeaturesPlusIntercept + numFeatures) =\n+              referenceCoef(i) - referenceMean\n+          }\n+        }\n+        val states = optimizer.iterations(new CachedDiffFunction(costFun),\n+          initialCoefficientsWithIntercept.asBreeze.toDenseVector)\n+\n+        /*\n+           Note that in Multinomial Logistic Regression, the objective history\n+           (loss + regularization) is log-likelihood which is invariant under feature\n+           standardization. As a result, the objective history from optimizer is the same as the\n+           one in the original space.\n+         */\n+        val arrayBuilder = mutable.ArrayBuilder.make[Double]\n+        var state: optimizer.State = null\n+        while (states.hasNext) {\n+          state = states.next()\n+          arrayBuilder += state.adjustedValue\n+        }\n+\n+        if (state == null) {\n+          val msg = s\"${optimizer.getClass.getName} failed.\"\n+          logError(msg)\n+          throw new SparkException(msg)\n+        }\n+        bcFeaturesStd.destroy(blocking = false)\n+\n+        /*\n+           The coefficients are trained in the scaled space; we're converting them back to\n+           the original space.\n+           Note that the intercept in scaled space and original space is the same;\n+           as a result, no scaling is needed.\n+         */\n+        var interceptSum = 0.0\n+        var coefSum = 0.0\n+        val rawCoefficients = Vectors.fromBreeze(state.x)\n+        val (coefMatrix, interceptVector) = rawCoefficients match {\n+          case dv: DenseVector =>\n+            val coefArray = Array.tabulate(numClasses * numFeatures) { i =>\n+              val flatIndex = if ($(fitIntercept)) i + i / numFeatures else i\n+              val featureIndex = i % numFeatures\n+              val unscaledCoef = if (featuresStd(featureIndex) != 0.0) {\n+                dv(flatIndex) / featuresStd(featureIndex)\n+              } else {\n+                0.0\n+              }\n+              coefSum += unscaledCoef\n+              unscaledCoef\n+            }\n+            val interceptVector = if ($(fitIntercept)) {\n+              Vectors.dense(Array.tabulate(numClasses) { i =>\n+                val coefIndex = (i + 1) * numFeaturesPlusIntercept - 1\n+                val intercept = dv(coefIndex)\n+                interceptSum += intercept\n+                intercept\n+              })\n+            } else {\n+              Vectors.sparse(numClasses, Seq())\n+            }\n+            (new DenseMatrix(numClasses, numFeatures, coefArray, isTransposed = true),\n+              interceptVector)\n+          case sv: SparseVector =>\n+            throw new IllegalArgumentException(\"SparseVector is not supported for coefficients\")\n+        }\n+\n+        /*\n+          When no regularization is applied, the coefficients lack identifiability because\n+          we do not use a pivot class. We can add any constant value to the coefficients and\n+          get the same likelihood. So here, we choose the mean centered coefficients for\n+          reproducibility. This method follows the approach in glmnet, described here:\n+\n+          Friedman, et al. \"Regularization Paths for Generalized Linear Models via\n+            Coordinate Descent,\" https://core.ac.uk/download/files/153/6287975.pdf\n+         */\n+        if ($(regParam) == 0.0) {\n+          val coefficientMean = coefSum / (numClasses * numFeatures)\n+          coefMatrix.update(_ - coefficientMean)\n+        }\n+        /*\n+          The intercepts are never regularized, so we always center the mean.\n+         */\n+        val interceptMean = interceptSum / numClasses\n+        interceptVector match {\n+          case dv: DenseVector => (0 until dv.size).foreach { i => dv.toArray(i) -= interceptMean }\n+          case sv: SparseVector =>\n+            (0 until sv.numNonzeros).foreach { i => sv.values(i) -= interceptMean }\n+        }\n+        (coefMatrix, interceptVector, arrayBuilder.result())\n+      }\n+    }\n+    if (handlePersistence) instances.unpersist()\n+\n+    val model = copyValues(\n+      new MultinomialLogisticRegressionModel(uid, coefficients, intercepts, numClasses))\n+    instr.logSuccess(model)\n+    model\n+  }\n+\n+  @Since(\"2.1.0\")\n+  override def copy(extra: ParamMap): MultinomialLogisticRegression = defaultCopy(extra)\n+}\n+\n+@Since(\"2.1.0\")\n+object MultinomialLogisticRegression extends DefaultParamsReadable[MultinomialLogisticRegression] {\n+\n+  @Since(\"2.1.0\")\n+  override def load(path: String): MultinomialLogisticRegression = super.load(path)\n+}\n+\n+/**\n+ * :: Experimental ::\n+ * Model produced by [[MultinomialLogisticRegression]].\n+ */\n+@Since(\"2.1.0\")\n+@Experimental\n+class MultinomialLogisticRegressionModel private[spark] (\n+    @Since(\"2.1.0\") override val uid: String,\n+    @Since(\"2.1.0\") val coefficients: Matrix,\n+    @Since(\"2.1.0\") val intercepts: Vector,\n+    @Since(\"2.1.0\") val numClasses: Int)\n+  extends ProbabilisticClassificationModel[Vector, MultinomialLogisticRegressionModel]\n+    with MultinomialLogisticRegressionParams with MLWritable {\n+\n+  @Since(\"2.1.0\")\n+  override def setThresholds(value: Array[Double]): this.type = super.setThresholds(value)\n+\n+  @Since(\"2.1.0\")\n+  override def getThresholds: Array[Double] = super.getThresholds\n+\n+  @Since(\"2.1.0\")\n+  override val numFeatures: Int = coefficients.numCols\n+\n+  /** Margin (rawPrediction) for each class label. */\n+  private val margins: Vector => Vector = (features) => {\n+    val m = intercepts.toDense.copy\n+    BLAS.gemv(1.0, coefficients, features, 1.0, m)\n+    m\n+  }\n+\n+  /** Score (probability) for each class label. */\n+  private val scores: Vector => Vector = (features) => {\n+    val m = margins(features).toDense\n+    val maxMarginIndex = m.argmax\n+    val maxMargin = m(maxMarginIndex)\n+\n+    // adjust margins for overflow\n+    val sum = {\n+      var temp = 0.0\n+      if (maxMargin > 0) {\n+        for (i <- 0 until numClasses) {\n+          m.toArray(i) -= maxMargin\n+          temp += math.exp(m(i))\n+        }\n+      } else {\n+        for (i <- 0 until numClasses ) {\n+          temp += math.exp(m(i))\n+        }\n+      }\n+      temp\n+    }\n+\n+    var i = 0\n+    while (i < m.size) {\n+      m.values(i) = math.exp(m.values(i)) / sum\n+      i += 1\n+    }\n+    m\n+  }\n+\n+  /**\n+   * Predict label for the given feature vector.\n+   * The behavior of this can be adjusted using [[thresholds]].\n+   */\n+  override protected def predict(features: Vector): Double = {\n+    if (isDefined(thresholds)) {\n+      val thresholds: Array[Double] = getThresholds\n+      val scaledProbability: Array[Double] =\n+        scores(features).toArray.zip(thresholds).map { case (p, t) =>\n+          if (t == 0.0) Double.PositiveInfinity else p / t\n+        }\n+      Vectors.dense(scaledProbability).argmax\n+    } else {\n+      scores(features).argmax\n+    }\n+  }\n+\n+  override protected def raw2probabilityInPlace(rawPrediction: Vector): Vector = {\n+    rawPrediction match {\n+      case dv: DenseVector =>\n+        val size = dv.size\n+\n+        // get the maximum margin\n+        val maxMarginIndex = rawPrediction.argmax\n+        val maxMargin = rawPrediction(maxMarginIndex)\n+\n+        if (maxMargin == Double.PositiveInfinity) {\n+          for (j <- 0 until size) {\n+            if (j == maxMarginIndex) {\n+              dv.values(j) = 1.0\n+            } else {\n+              dv.values(j) = 0.0\n+            }\n+          }\n+        } else {\n+          val sum = {\n+            var temp = 0.0\n+            if (maxMargin > 0) {\n+              // adjust margins for overflow\n+              for (j <- 0 until numClasses) {\n+                dv.values(j) -= maxMargin\n+                temp += math.exp(dv.values(j))\n+              }\n+            } else {\n+              for (j <- 0 until numClasses) {\n+                temp += math.exp(dv.values(j))\n+              }\n+            }\n+            temp\n+          }\n+\n+          // update in place\n+          var i = 0\n+          while (i < size) {\n+            dv.values(i) = math.exp(dv.values(i)) / sum\n+            i += 1\n+          }\n+        }\n+        dv\n+      case sv: SparseVector =>\n+        throw new RuntimeException(\"Unexpected error in MultinomialLogisticRegressionModel:\" +\n+          \" raw2probabilitiesInPlace encountered SparseVector\")\n+    }\n+  }\n+\n+  override protected def predictRaw(features: Vector): Vector = margins(features)\n+\n+  @Since(\"2.1.0\")\n+  override def copy(extra: ParamMap): MultinomialLogisticRegressionModel = {\n+    val newModel =\n+      copyValues(\n+        new MultinomialLogisticRegressionModel(uid, coefficients, intercepts, numClasses), extra)\n+    newModel.setParent(parent)\n+  }\n+\n+  /**\n+   * Returns a [[org.apache.spark.ml.util.MLWriter]] instance for this ML instance.\n+   *\n+   * This does not save the [[parent]] currently.\n+   */\n+  @Since(\"2.1.0\")\n+  override def write: MLWriter =\n+    new MultinomialLogisticRegressionModel.MultinomialLogisticRegressionModelWriter(this)\n+}\n+\n+\n+@Since(\"2.1.0\")\n+object MultinomialLogisticRegressionModel extends MLReadable[MultinomialLogisticRegressionModel] {\n+\n+  @Since(\"2.1.0\")\n+  override def read: MLReader[MultinomialLogisticRegressionModel] =\n+    new MultinomialLogisticRegressionModelReader\n+\n+  @Since(\"2.1.0\")\n+  override def load(path: String): MultinomialLogisticRegressionModel = super.load(path)\n+\n+  /** [[MLWriter]] instance for [[MultinomialLogisticRegressionModel]] */\n+  private[MultinomialLogisticRegressionModel]\n+  class MultinomialLogisticRegressionModelWriter(instance: MultinomialLogisticRegressionModel)\n+    extends MLWriter with Logging {\n+\n+    private case class Data(\n+        numClasses: Int,\n+        numFeatures: Int,\n+        intercept: Vector,\n+        coefficients: Matrix)\n+\n+    override protected def saveImpl(path: String): Unit = {\n+      // Save metadata and Params\n+      DefaultParamsWriter.saveMetadata(instance, path, sc)\n+      // Save model data: numClasses, numFeatures, intercept, coefficients\n+      val data = Data(instance.numClasses, instance.numFeatures, instance.intercepts,\n+        instance.coefficients)\n+      val dataPath = new Path(path, \"data\").toString\n+      sqlContext.createDataFrame(Seq(data)).repartition(1).write.parquet(dataPath)\n+    }\n+  }\n+\n+  private class MultinomialLogisticRegressionModelReader\n+    extends MLReader[MultinomialLogisticRegressionModel] {\n+\n+    /** Checked against metadata when loading model */\n+    private val className = classOf[MultinomialLogisticRegressionModel].getName\n+\n+    override def load(path: String): MultinomialLogisticRegressionModel = {\n+      val metadata = DefaultParamsReader.loadMetadata(path, sc, className)\n+\n+      val dataPath = new Path(path, \"data\").toString\n+      val data = sqlContext.read.format(\"parquet\").load(dataPath)\n+        .select(\"numClasses\", \"numFeatures\", \"intercept\", \"coefficients\").head()\n+      val numClasses = data.getInt(0)\n+      val intercepts = data.getAs[Vector](2)","path":"mllib/src/main/scala/org/apache/spark/ml/classification/MultinomialLogisticRegression.scala","position":null,"original_position":602,"commit_id":"0c851d7548f6fdc6589544e8d3ba7db4a6dafbf9","original_commit_id":"f02b226e1170c8cc1c2d1c6acade950e0be44962","user":{"login":"sethah","id":7275795,"avatar_url":"https://avatars.githubusercontent.com/u/7275795?v=3","gravatar_id":"","url":"https://api.github.com/users/sethah","html_url":"https://github.com/sethah","followers_url":"https://api.github.com/users/sethah/followers","following_url":"https://api.github.com/users/sethah/following{/other_user}","gists_url":"https://api.github.com/users/sethah/gists{/gist_id}","starred_url":"https://api.github.com/users/sethah/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sethah/subscriptions","organizations_url":"https://api.github.com/users/sethah/orgs","repos_url":"https://api.github.com/users/sethah/repos","events_url":"https://api.github.com/users/sethah/events{/privacy}","received_events_url":"https://api.github.com/users/sethah/received_events","type":"User","site_admin":false},"body":"done","created_at":"2016-08-18T17:19:28Z","updated_at":"2016-08-18T17:19:28Z","html_url":"https://github.com/apache/spark/pull/13796#discussion_r75349924","pull_request_url":"https://api.github.com/repos/apache/spark/pulls/13796","_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/comments/75349924"},"html":{"href":"https://github.com/apache/spark/pull/13796#discussion_r75349924"},"pull_request":{"href":"https://api.github.com/repos/apache/spark/pulls/13796"}}},"pull_request":{"url":"https://api.github.com/repos/apache/spark/pulls/13796","id":74546117,"html_url":"https://github.com/apache/spark/pull/13796","diff_url":"https://github.com/apache/spark/pull/13796.diff","patch_url":"https://github.com/apache/spark/pull/13796.patch","issue_url":"https://api.github.com/repos/apache/spark/issues/13796","number":13796,"state":"open","locked":false,"title":"[SPARK-7159][ML] Add multiclass logistic regression to Spark ML","user":{"login":"sethah","id":7275795,"avatar_url":"https://avatars.githubusercontent.com/u/7275795?v=3","gravatar_id":"","url":"https://api.github.com/users/sethah","html_url":"https://github.com/sethah","followers_url":"https://api.github.com/users/sethah/followers","following_url":"https://api.github.com/users/sethah/following{/other_user}","gists_url":"https://api.github.com/users/sethah/gists{/gist_id}","starred_url":"https://api.github.com/users/sethah/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sethah/subscriptions","organizations_url":"https://api.github.com/users/sethah/orgs","repos_url":"https://api.github.com/users/sethah/repos","events_url":"https://api.github.com/users/sethah/events{/privacy}","received_events_url":"https://api.github.com/users/sethah/received_events","type":"User","site_admin":false},"body":"## What changes were proposed in this pull request?\r\n\r\nThis patch adds a new estimator/transformer `MultinomialLogisticRegression` to spark ML. \r\n\r\nJIRA: [SPARK-7159](https://issues.apache.org/jira/browse/SPARK-7159)\r\n\r\n## How was this patch tested?\r\n\r\nAdded new test suite `MultinomialLogisticRegressionSuite`.\r\n\r\n## Approach\r\n\r\n### Do not use a \"pivot\" class in the algorithm formulation\r\n\r\nMany implementations of multinomial logistic regression treat the problem as K - 1 independent binary logistic regression models where K is the number of possible outcomes in the output variable. In this case, one outcome is chosen as a \"pivot\" and the other K - 1 outcomes are regressed against the pivot. This is somewhat undesirable since the coefficients returned will be different for different choices of pivot variables. An alternative approach to the problem models class conditional probabilites using the softmax function and will return uniquely identifiable coefficients (assuming regularization is applied). This second approach is used in R's glmnet and was also recommended by @dbtsai. \r\n\r\n### Separate multinomial logistic regression and binary logistic regression\r\n\r\nThe initial design makes multinomial logistic regression a separate estimator/transformer than the existing LogisticRegression estimator/transformer. An alternative design would be to merge them into one. \r\n\r\n**Arguments for:**\r\n\r\n* The multinomial case without pivot is distinctly different than the current binary case since the binary case uses a pivot class. \r\n* The current logistic regression model in ML uses a vector of coefficients and a scalar intercept. In the multinomial case, we require a matrix of coefficients and a vector of intercepts. There are potential workarounds for this issue if we were to merge the two estimators, but none are particularly elegant. \r\n\r\n**Arguments against:**\r\n\r\n* It may be inconvenient for users to have to switch the estimator class when transitioning between binary and multiclass (although the new multinomial estimator can be used for two class outcomes).\r\n* Some portions of the code are repeated.\r\n\r\nThis is a major design point and warrants more discussion.\r\n\r\n### Mean centering\r\n\r\nWhen no regularization is applied, the coefficients will not be uniquely identifiable. This is not hard to show and is discussed in further detail [here](https://core.ac.uk/download/files/153/6287975.pdf). R's glmnet deals with this by choosing the minimum l2 regularized solution (i.e. mean centering). Additionally, the intercepts are never regularized so they are always mean centered. This is the approach taken in this PR as well.\r\n\r\n### Feature scaling\r\n\r\nIn current ML logistic regression, the features are always standardized when running the optimization algorithm. They are always returned to the user in the original feature space, however. This same approach is maintained in this patch as well, but the implementation details are different. In ML logistic regression, the unregularized feature values are divided by the column standard deviation in every gradient update iteration. In contrast, MLlib transforms the entire input dataset to the scaled space _before_ optimizaton. In ML, this means that `numFeatures * numClasses` extra scalar divisions are required in every iteration. Performance testing shows that this has significant (4x in some cases) slow downs in each iteration. This can be avoided by transforming the input to the scaled space ala MLlib once, before iteration begins. This does add some overhead initially, but can make significant time savings in some cases. \r\n\r\nOne issue with this approach is that if the input data is already cached, there may not be enough memory to cache the transformed data, which would make the algorithm _much_ slower. The tradeoffs here merit more discussion. \r\n\r\n### Specifying and inferring the number of outcome classes\r\n\r\nThe estimator checks the dataframe label column for metadata which specifies the number of values. If they are not specified, the length of the `histogram` variable is used, which is essentially the maximum value found in the column. The assumption then, is that the labels are zero-indexed when they are provided to the algorithm. \r\n\r\n## Performance\r\n\r\nBelow are some performance tests I have run so far. I am happy to add more cases or trials if we deem them necessary.\r\n\r\nTest cluster: 4 bare metal nodes, 128 GB RAM each, 48 cores each\r\n\r\nNotes:\r\n\r\n* Time in units of seconds\r\n* Metric is classification accuracy\r\n\r\n| algo   |   elasticNetParam | fitIntercept   |   metric |   maxIter |   numPoints |   numClasses |   numFeatures |    time | standardization   |   regParam |\r\n|--------|-------------------|----------------|----------|-----------|-------------|--------------|---------------|---------|-------------------|------------|\r\n| ml     |                 0 | true           | 0.746415 |        30 |      100000 |            3 |        100000 | 327.923 | true              |          0 |\r\n| mllib  |                 0 | true           | 0.743785 |        30 |      100000 |            3 |        100000 | 390.217 | true              |          0 |\r\n\r\n| algo   |   elasticNetParam | fitIntercept   |   metric |   maxIter |   numPoints |   numClasses |   numFeatures |    time | standardization   |   regParam |\r\n|--------|-------------------|----------------|----------|-----------|-------------|--------------|---------------|---------|-------------------|------------|\r\n| ml     |                 0 | true           | 0.973238 |        30 |     2000000 |            3 |         10000 | 385.476 | true              |          0 |\r\n| mllib  |                 0 | true           | 0.949828 |        30 |     2000000 |            3 |         10000 | 550.403 | true              |          0 |\r\n\r\n| algo   |   elasticNetParam | fitIntercept   |   metric |   maxIter |   numPoints |   numClasses |   numFeatures |    time | standardization   |   regParam |\r\n|--------|-------------------|----------------|----------|-----------|-------------|--------------|---------------|---------|-------------------|------------|\r\n| mllib  |                 0 | true           | 0.864358 |        30 |     2000000 |            3 |         10000 | 543.359 | true              |        0.1 |\r\n| ml     |                 0 | true           | 0.867418 |        30 |     2000000 |            3 |         10000 | 401.955 | true              |        0.1 |\r\n\r\n| algo   |   elasticNetParam | fitIntercept   |   metric |   maxIter |   numPoints |   numClasses |   numFeatures |    time | standardization   |   regParam |\r\n|--------|-------------------|----------------|----------|-----------|-------------|--------------|---------------|---------|-------------------|------------|\r\n| ml     |                 1 | true           | 0.807449 |        30 |     2000000 |            3 |         10000 | 334.892 | true              |       0.05 |\r\n\r\n| algo   |   elasticNetParam | fitIntercept   |   metric |   maxIter |   numPoints |   numClasses |   numFeatures |    time | standardization   |   regParam |\r\n|--------|-------------------|----------------|----------|-----------|-------------|--------------|---------------|---------|-------------------|------------|\r\n| ml     |                 0 | true           | 0.602006 |        30 |     2000000 |          500 |           100 | 112.319 | true              |          0 |\r\n| mllib  |                 0 | true           | 0.567226 |        30 |     2000000 |          500 |           100 | 263.768 | true              |          0 |e           | 0.567226 |        30 |     2000000 |          500 |           100 | 263.768 | true              |          0 |\r\n\r\n## References\r\n\r\nFriedman, et al. [\"Regularization Paths for Generalized Linear Models via Coordinate Descent\"](https://core.ac.uk/download/files/153/6287975.pdf)\r\n[http://web.stanford.edu/~hastie/glmnet/glmnet_alpha.html](http://web.stanford.edu/~hastie/glmnet/glmnet_alpha.html)\r\n\r\n## Follow up items\r\n* Consider using level 2 BLAS routines in the gradient computations\r\n* Add model summary for MLOR\r\n* Add initial model to MLOR and add test for intercept priors\r\n* Consider changing the tree aggregation level for MLOR/BLOR or making it user configurable to avoid memory problems with high dimensional data - [SPARK-17090](https://issues.apache.org/jira/browse/SPARK-17090)\r\n* Refactor helper classes out of `LogisticRegression.scala`","created_at":"2016-06-21T03:22:36Z","updated_at":"2016-08-18T17:19:29Z","closed_at":null,"merged_at":null,"merge_commit_sha":"0b5ab3c5fc3c9abe03058a75f1eaee0bc8484899","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/apache/spark/pulls/13796/commits","review_comments_url":"https://api.github.com/repos/apache/spark/pulls/13796/comments","review_comment_url":"https://api.github.com/repos/apache/spark/pulls/comments{/number}","comments_url":"https://api.github.com/repos/apache/spark/issues/13796/comments","statuses_url":"https://api.github.com/repos/apache/spark/statuses/0c851d7548f6fdc6589544e8d3ba7db4a6dafbf9","head":{"label":"sethah:SPARK-7159_M","ref":"SPARK-7159_M","sha":"0c851d7548f6fdc6589544e8d3ba7db4a6dafbf9","user":{"login":"sethah","id":7275795,"avatar_url":"https://avatars.githubusercontent.com/u/7275795?v=3","gravatar_id":"","url":"https://api.github.com/users/sethah","html_url":"https://github.com/sethah","followers_url":"https://api.github.com/users/sethah/followers","following_url":"https://api.github.com/users/sethah/following{/other_user}","gists_url":"https://api.github.com/users/sethah/gists{/gist_id}","starred_url":"https://api.github.com/users/sethah/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sethah/subscriptions","organizations_url":"https://api.github.com/users/sethah/orgs","repos_url":"https://api.github.com/users/sethah/repos","events_url":"https://api.github.com/users/sethah/events{/privacy}","received_events_url":"https://api.github.com/users/sethah/received_events","type":"User","site_admin":false},"repo":{"id":38016887,"name":"spark","full_name":"sethah/spark","owner":{"login":"sethah","id":7275795,"avatar_url":"https://avatars.githubusercontent.com/u/7275795?v=3","gravatar_id":"","url":"https://api.github.com/users/sethah","html_url":"https://github.com/sethah","followers_url":"https://api.github.com/users/sethah/followers","following_url":"https://api.github.com/users/sethah/following{/other_user}","gists_url":"https://api.github.com/users/sethah/gists{/gist_id}","starred_url":"https://api.github.com/users/sethah/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sethah/subscriptions","organizations_url":"https://api.github.com/users/sethah/orgs","repos_url":"https://api.github.com/users/sethah/repos","events_url":"https://api.github.com/users/sethah/events{/privacy}","received_events_url":"https://api.github.com/users/sethah/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/sethah/spark","description":"Mirror of Apache Spark","fork":true,"url":"https://api.github.com/repos/sethah/spark","forks_url":"https://api.github.com/repos/sethah/spark/forks","keys_url":"https://api.github.com/repos/sethah/spark/keys{/key_id}","collaborators_url":"https://api.github.com/repos/sethah/spark/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/sethah/spark/teams","hooks_url":"https://api.github.com/repos/sethah/spark/hooks","issue_events_url":"https://api.github.com/repos/sethah/spark/issues/events{/number}","events_url":"https://api.github.com/repos/sethah/spark/events","assignees_url":"https://api.github.com/repos/sethah/spark/assignees{/user}","branches_url":"https://api.github.com/repos/sethah/spark/branches{/branch}","tags_url":"https://api.github.com/repos/sethah/spark/tags","blobs_url":"https://api.github.com/repos/sethah/spark/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/sethah/spark/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/sethah/spark/git/refs{/sha}","trees_url":"https://api.github.com/repos/sethah/spark/git/trees{/sha}","statuses_url":"https://api.github.com/repos/sethah/spark/statuses/{sha}","languages_url":"https://api.github.com/repos/sethah/spark/languages","stargazers_url":"https://api.github.com/repos/sethah/spark/stargazers","contributors_url":"https://api.github.com/repos/sethah/spark/contributors","subscribers_url":"https://api.github.com/repos/sethah/spark/subscribers","subscription_url":"https://api.github.com/repos/sethah/spark/subscription","commits_url":"https://api.github.com/repos/sethah/spark/commits{/sha}","git_commits_url":"https://api.github.com/repos/sethah/spark/git/commits{/sha}","comments_url":"https://api.github.com/repos/sethah/spark/comments{/number}","issue_comment_url":"https://api.github.com/repos/sethah/spark/issues/comments{/number}","contents_url":"https://api.github.com/repos/sethah/spark/contents/{+path}","compare_url":"https://api.github.com/repos/sethah/spark/compare/{base}...{head}","merges_url":"https://api.github.com/repos/sethah/spark/merges","archive_url":"https://api.github.com/repos/sethah/spark/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/sethah/spark/downloads","issues_url":"https://api.github.com/repos/sethah/spark/issues{/number}","pulls_url":"https://api.github.com/repos/sethah/spark/pulls{/number}","milestones_url":"https://api.github.com/repos/sethah/spark/milestones{/number}","notifications_url":"https://api.github.com/repos/sethah/spark/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/sethah/spark/labels{/name}","releases_url":"https://api.github.com/repos/sethah/spark/releases{/id}","deployments_url":"https://api.github.com/repos/sethah/spark/deployments","created_at":"2015-06-24T23:36:53Z","updated_at":"2016-01-14T16:52:52Z","pushed_at":"2016-08-18T17:18:41Z","git_url":"git://github.com/sethah/spark.git","ssh_url":"git@github.com:sethah/spark.git","clone_url":"https://github.com/sethah/spark.git","svn_url":"https://github.com/sethah/spark","homepage":null,"size":166304,"stargazers_count":0,"watchers_count":0,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"apache:master","ref":"master","sha":"fffb0c0d19a2444e7554dfe6b27de0c086112b17","user":{"login":"apache","id":47359,"avatar_url":"https://avatars.githubusercontent.com/u/47359?v=3","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"repo":{"id":17165658,"name":"spark","full_name":"apache/spark","owner":{"login":"apache","id":47359,"avatar_url":"https://avatars.githubusercontent.com/u/47359?v=3","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/apache/spark","description":"Mirror of Apache Spark","fork":false,"url":"https://api.github.com/repos/apache/spark","forks_url":"https://api.github.com/repos/apache/spark/forks","keys_url":"https://api.github.com/repos/apache/spark/keys{/key_id}","collaborators_url":"https://api.github.com/repos/apache/spark/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/apache/spark/teams","hooks_url":"https://api.github.com/repos/apache/spark/hooks","issue_events_url":"https://api.github.com/repos/apache/spark/issues/events{/number}","events_url":"https://api.github.com/repos/apache/spark/events","assignees_url":"https://api.github.com/repos/apache/spark/assignees{/user}","branches_url":"https://api.github.com/repos/apache/spark/branches{/branch}","tags_url":"https://api.github.com/repos/apache/spark/tags","blobs_url":"https://api.github.com/repos/apache/spark/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/apache/spark/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/apache/spark/git/refs{/sha}","trees_url":"https://api.github.com/repos/apache/spark/git/trees{/sha}","statuses_url":"https://api.github.com/repos/apache/spark/statuses/{sha}","languages_url":"https://api.github.com/repos/apache/spark/languages","stargazers_url":"https://api.github.com/repos/apache/spark/stargazers","contributors_url":"https://api.github.com/repos/apache/spark/contributors","subscribers_url":"https://api.github.com/repos/apache/spark/subscribers","subscription_url":"https://api.github.com/repos/apache/spark/subscription","commits_url":"https://api.github.com/repos/apache/spark/commits{/sha}","git_commits_url":"https://api.github.com/repos/apache/spark/git/commits{/sha}","comments_url":"https://api.github.com/repos/apache/spark/comments{/number}","issue_comment_url":"https://api.github.com/repos/apache/spark/issues/comments{/number}","contents_url":"https://api.github.com/repos/apache/spark/contents/{+path}","compare_url":"https://api.github.com/repos/apache/spark/compare/{base}...{head}","merges_url":"https://api.github.com/repos/apache/spark/merges","archive_url":"https://api.github.com/repos/apache/spark/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/apache/spark/downloads","issues_url":"https://api.github.com/repos/apache/spark/issues{/number}","pulls_url":"https://api.github.com/repos/apache/spark/pulls{/number}","milestones_url":"https://api.github.com/repos/apache/spark/milestones{/number}","notifications_url":"https://api.github.com/repos/apache/spark/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/apache/spark/labels{/name}","releases_url":"https://api.github.com/repos/apache/spark/releases{/id}","deployments_url":"https://api.github.com/repos/apache/spark/deployments","created_at":"2014-02-25T08:00:08Z","updated_at":"2016-08-18T16:33:46Z","pushed_at":"2016-08-18T17:18:43Z","git_url":"git://github.com/apache/spark.git","ssh_url":"git@github.com:apache/spark.git","clone_url":"https://github.com/apache/spark.git","svn_url":"https://github.com/apache/spark","homepage":null,"size":506335,"stargazers_count":9705,"watchers_count":9705,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":9026,"mirror_url":"git://git.apache.org/spark.git","open_issues_count":475,"forks":9026,"open_issues":475,"watchers":9705,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/13796"},"html":{"href":"https://github.com/apache/spark/pull/13796"},"issue":{"href":"https://api.github.com/repos/apache/spark/issues/13796"},"comments":{"href":"https://api.github.com/repos/apache/spark/issues/13796/comments"},"review_comments":{"href":"https://api.github.com/repos/apache/spark/pulls/13796/comments"},"review_comment":{"href":"https://api.github.com/repos/apache/spark/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/apache/spark/pulls/13796/commits"},"statuses":{"href":"https://api.github.com/repos/apache/spark/statuses/0c851d7548f6fdc6589544e8d3ba7db4a6dafbf9"}}}}
{"actor":{"display_login":"sethah"}}