flink-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "ASF GitHub Bot (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (FLINK-1807) Stochastic gradient descent optimizer for ML library
Date Wed, 29 Apr 2015 15:27:11 GMT

    [ https://issues.apache.org/jira/browse/FLINK-1807?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14519552#comment-14519552
] 

ASF GitHub Bot commented on FLINK-1807:
---------------------------------------

Github user tillrohrmann commented on a diff in the pull request:

    https://github.com/apache/flink/pull/613#discussion_r29347156
  
    --- Diff: flink-staging/flink-ml/src/main/scala/org/apache/flink/ml/optimization/GradientDescent.scala
---
    @@ -0,0 +1,237 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +
    +package org.apache.flink.ml.optimization
    +
    +import org.apache.flink.api.common.functions.RichMapFunction
    +import org.apache.flink.api.scala._
    +import org.apache.flink.configuration.Configuration
    +import org.apache.flink.ml.common._
    +import org.apache.flink.ml.math._
    +import org.apache.flink.ml.optimization.IterativeSolver.{Iterations, Stepsize}
    +import org.apache.flink.ml.optimization.Solver._
    +
    +/** This [[Solver]] performs Stochastic Gradient Descent optimization using mini batches
    +  *
    +  * For each labeled vector in a mini batch the gradient is computed and added to a partial
    +  * gradient. The partial gradients are then summed and divided by the size of the batches.
The
    +  * average gradient is then used to updated the weight values, including regularization.
    +  *
    +  * At the moment, the whole partition is used for SGD, making it effectively a batch
gradient
    +  * descent. Once a sampling operator has been introduced, the algorithm can be optimized
    +  *
    +  * @param runParameters The parameters to tune the algorithm. Currently these include:
    +  *                      [[Solver.LossFunction]] for the loss function to be used,
    +  *                      [[Solver.RegularizationType]] for the type of regularization,
    +  *                      [[Solver.RegularizationParameter]] for the regularization parameter,
    +  *                      [[IterativeSolver.Iterations]] for the maximum number of iteration,
    +  *                      [[IterativeSolver.Stepsize]] for the learning rate used.
    +  */
    +class GradientDescent(runParameters: ParameterMap) extends IterativeSolver {
    +
    +  import Solver.WEIGHTVECTOR_BROADCAST
    +
    +  var parameterMap: ParameterMap = parameters ++ runParameters
    +
    +  // TODO(tvas): Use once we have proper sampling in place
    +//  case object MiniBatchFraction extends Parameter[Double] {
    +//    val defaultValue = Some(1.0)
    +//  }
    +//
    +//  def setMiniBatchFraction(fraction: Double): GradientDescent = {
    +//    parameterMap.add(MiniBatchFraction, fraction)
    +//    this
    +//  }
    +
    +  /** Performs one iteration of Stochastic Gradient Descent using mini batches
    +    *
    +    * @param data A Dataset of LabeledVector (label, features) pairs
    +    * @param currentWeights A Dataset with the current weights to be optimized as its
only element
    +    * @return A Dataset containing the weights after one stochastic gradient descent
step
    +    */
    +  private def SGDStep(data: DataSet[(LabeledVector)], currentWeights: DataSet[WeightVector]):
    +    DataSet[WeightVector] = {
    +
    +    // TODO: Sample from input to realize proper SGD
    +    data.map {
    +      new GradientCalculation
    +    }.withBroadcastSet(currentWeights, WEIGHTVECTOR_BROADCAST).reduce {
    +      (left, right) =>
    +        val (leftGradientVector, leftCount) = left
    +        val (rightGradientVector, rightCount) = right
    +
    +        BLAS.axpy(1.0, leftGradientVector.weights, rightGradientVector.weights)
    +        (new WeightVector(
    +          rightGradientVector.weights,
    +          leftGradientVector.intercept + rightGradientVector.intercept),
    +          leftCount + rightCount)
    +    }.map {
    +      new WeightsUpdate
    +    }.withBroadcastSet(currentWeights, WEIGHTVECTOR_BROADCAST)
    +  }
    +
    +  /** Provides a solution for the given optimization problem
    +    *
    +    * @param data A Dataset of LabeledVector (label, features) pairs
    +    * @param initWeights The initial weights that will be optimized
    +    * @return The weights, optimized for the provided data.
    +    */
    +  override def optimize(data: DataSet[LabeledVector], initWeights: Option[DataSet[WeightVector]]):
    +  DataSet[WeightVector] = {
    +    // TODO: Faster way to do this?
    +    val dimensionsDS = data.map(_.vector.size).reduce((a, b) => b)
    +
    +    val numberOfIterations: Int = parameterMap(Iterations)
    +
    +
    +    val initialWeightsDS: DataSet[WeightVector] = initWeights match {
    +      //TODO(tvas): Need to figure out if and where we want to pass initial weights
    +      case Some(x) => x
    +      case None => createInitialWeightVector(dimensionsDS)
    +    }
    +
    +    // We need the weights vector to initialize the regularization value.
    +    val initWeightsVector = initialWeightsDS.collect()(0).weights
    +
    +    val initRegVal = parameterMap(RegularizationType)
    +      .applyRegularization(initWeightsVector, 0.0, parameterMap(RegularizationParameter))._2
    +
    +    // TODO: Is there a way to initialize the regularization parameter without collect()?
    +    // The following code should give us a dataset with the initial reg. parameter, but
we still
    +    // need to call collect to retrieve it. Question is: call collect here, or on the
weights as we
    +    // currently do?
    +    //val initRegValue: DataSet[Double] = initialWeights.map {x => parameterMap(RegularizationType)
    +    //  .applyRegularization(x.weights, 0.0, parameterMap(RegularizationParameter))._2}
    +    //  .reduce(_ + _)
    +
    +    // Perform the iterations
    +    // TODO: Enable convergence stopping criterion, as in Multiple Linear regression
    +    initialWeightsDS.iterate(numberOfIterations) {
    +      weightVector => {
    +        SGDStep(data, weightVector)
    +      }
    +    }
    +  }
    +
    +  /** Mapping function that calculates the weight gradients from the data.
    +    *
    +    */
    +  private class GradientCalculation extends
    +  RichMapFunction[LabeledVector, (WeightVector, Int)] {
    +
    +    var weightVector: WeightVector = null
    +
    +    @throws(classOf[Exception])
    +    override def open(configuration: Configuration): Unit = {
    +      val list = this.getRuntimeContext.
    +        getBroadcastVariable[WeightVector](WEIGHTVECTOR_BROADCAST)
    +
    +      weightVector = list.get(0)
    +    }
    +
    +    override def map(example: LabeledVector): (WeightVector, Int) = {
    +
    +      val lossFunction = parameterMap(LossFunction)
    +      //TODO(tvas): Should throw an error if Dimensions has not been defined
    +      val dimensions = example.vector.size
    +      // TODO(tvas): Any point in carrying the weightGradient vector for in-place replacement?
    +      // The idea in spark is to avoid object creation, but here we have to do it anyway
    +      val weightGradient = new DenseVector(new Array[Double](dimensions))
    +
    +      val (loss, lossDeriv) = lossFunction.lossAndGradient(example, weightVector, weightGradient)
    +
    +      // Restrict the value of the loss derivative to avoid numerical instabilities
    +      val restrictedLossDeriv: Double = {
    +        if (lossDeriv < -IterativeSolver.MAX_DLOSS) {
    +          -IterativeSolver.MAX_DLOSS
    +        }
    +        else if (lossDeriv > IterativeSolver.MAX_DLOSS) {
    +          IterativeSolver.MAX_DLOSS
    +        }
    +        else {
    +          lossDeriv
    +        }
    +      }
    +
    +      (new WeightVector(weightGradient, restrictedLossDeriv), 1)
    +    }
    +  }
    +
    +  /** Performs the update of the weights, according to the given gradients and regularization
type.
    +    *
    +    */
    +  private class WeightsUpdate() extends
    +  RichMapFunction[(WeightVector, Int), WeightVector] {
    +
    +
    +    var weightVector: WeightVector = null
    +
    +    @throws(classOf[Exception])
    +    override def open(configuration: Configuration): Unit = {
    +      val list = this.getRuntimeContext.
    +        getBroadcastVariable[WeightVector](WEIGHTVECTOR_BROADCAST)
    +
    +      weightVector = list.get(0)
    +    }
    +
    +    override def map(gradientsAndCount: (WeightVector, Int)): WeightVector = {
    +      val regularizationType = parameterMap(RegularizationType)
    +      val regularizationParameter = parameterMap(RegularizationParameter)
    +      val stepsize = parameterMap(Stepsize)
    +      val weightGradients = gradientsAndCount._1
    +      val count = gradientsAndCount._2
    +
    +      // Scale the gradients according to batch size
    +      BLAS.scal(1.0/count, weightGradients.weights)
    +
    +      val weight0Gradient = weightGradients.intercept / count
    +
    +      val iteration = getIterationRuntimeContext.getSuperstepNumber
    +
    +      // Scale initial stepsize by the inverse square root of the iteration number
    +      // TODO(tvas): There are more ways to determine the stepsize, possible low-effort
extensions
    +      // here
    +      val effectiveStepsize = stepsize/math.sqrt(iteration)
    +
    +      val newWeights = weightVector.weights.copy
    +      // Take the gradient step
    +      BLAS.axpy(-effectiveStepsize, weightGradients.weights, newWeights)
    +      val newWeight0 = weightVector.intercept - effectiveStepsize * weight0Gradient
    +
    +      // Apply the regularization
    +      val (updatedWeights, regVal) = regularizationType.applyRegularization(
    --- End diff --
    
    For what do we need the `regVal` value?


> Stochastic gradient descent optimizer for ML library
> ----------------------------------------------------
>
>                 Key: FLINK-1807
>                 URL: https://issues.apache.org/jira/browse/FLINK-1807
>             Project: Flink
>          Issue Type: Improvement
>          Components: Machine Learning Library
>            Reporter: Till Rohrmann
>            Assignee: Theodore Vasiloudis
>              Labels: ML
>
> Stochastic gradient descent (SGD) is a widely used optimization technique in different
ML algorithms. Thus, it would be helpful to provide a generalized SGD implementation which
can be instantiated with the respective gradient computation. Such a building block would
make the development of future algorithms easier.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

Mime
View raw message