/*
* Copyright (C) 2015 Edward Raff
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see .
*/
package jsat.math.optimization;
import java.util.ArrayList;
import java.util.List;
import jsat.linear.Vec;
import jsat.math.Function;
import jsat.math.FunctionVec;
import jsat.utils.DoubleList;
import static java.lang.Math.*;
import jsat.linear.ConstantVector;
import jsat.linear.IndexValue;
/**
* This implements the Modified Orthant-Wise Limited memory
* Quasi-Newton(mOWL-QN) optimizer. This algorithm is an extension of
* {@link LBFGS}, and solves minimization problems of the form: f(x) +
* {@link #setLambda(double) λ} ||x||1. It requires the
* function and it's gradient to work.
*
* See:
*
* - Gong, P., & Ye, J. (2015). A Modified Orthant-Wise Limited Memory
* Quasi-Newton Method with Convergence Analysis. In The 32nd International
* Conference on Machine Learning (Vol. 37).
* - Andrew, G., & Gao, J. (2007). Scalable training of L1 -regularized
* log-linear models. In Proceedings of the 24th international conference on
* Machine learning - ICML ’07 (pp. 33–40). New York, New York, USA: ACM Press.
* doi:10.1145/1273496.1273501
*
*
*
* @author Edward Raff
*/
public class ModifiedOWLQN implements Optimizer
{
private int m = 10;
private double lambda;
private Vec lambdaMultipler = null;
private static final double DEFAULT_EPS = 1e-12;
private static final double DEFAULT_ALPHA_0 = 1;
private static final double DEFAULT_BETA = 0.2;
private static final double DEFAULT_GAMMA = 1e-2;
private double eps = DEFAULT_EPS;
private double alpha_0 = DEFAULT_ALPHA_0;
private double beta = DEFAULT_BETA;
private double gamma = DEFAULT_GAMMA;
private int maxIterations = 500;
/**
* Creates a new mOWL-QN optimizer with no regularization penalty
*/
public ModifiedOWLQN()
{
this(0.0);
}
/**
* Creates a new mOWL-QN optimizer
* @param lambda the regularization penalty to use
*/
public ModifiedOWLQN(double lambda)
{
setLambda(lambda);
}
/**
* copy constructor
* @param toCopy the object to copy
*/
protected ModifiedOWLQN(ModifiedOWLQN toCopy)
{
this(toCopy.lambda);
if(toCopy.lambdaMultipler != null)
this.lambdaMultipler = toCopy.lambdaMultipler.clone();
this.eps = toCopy.eps;
this.m = toCopy.m;
this.alpha_0 = toCopy.alpha_0;
this.beta = toCopy.beta;
this.gamma = toCopy.gamma;
this.maxIterations = toCopy.maxIterations;
}
/**
* Sets the regularization term for the optimizer
* @param lambda the regularization penalty
*/
public void setLambda(double lambda)
{
if(lambda < 0 || Double.isInfinite(lambda) || Double.isNaN(lambda))
throw new IllegalArgumentException("lambda must be non-negative, not " + lambda);
this.lambda = lambda;
}
/**
* This method sets a vector that will contain a separate multiplier for
* {@link #setLambda(double) lambda} for each dimension of the problem. This
* allows for each dimension to have a different regularization penalty.
*
* If set to {@code null}, all dimensions will simply use λ as their
* regularization value.
*
* @param lambdaMultipler the per-dimension regularization multiplier, or {@code null}.
*/
public void setLambdaMultipler(Vec lambdaMultipler)
{
this.lambdaMultipler = lambdaMultipler;
}
public Vec getLambdaMultipler()
{
return lambdaMultipler;
}
/**
* Sets the number of history items to keep that are used to approximate the
* Hessian of the problem
*
* @param m the number of history items to keep
*/
public void setM(int m)
{
if (m < 1)
throw new IllegalArgumentException("m must be positive, not " + m);
this.m = m;
}
/**
* Returns the number of history items that will be used
*
* @return the number of history items that will be used
*/
public int getM()
{
return m;
}
/**
* Sets the epsilon term that helps control when the gradient descent step
* is taken instead of the normal Quasi-Newton step. Larger values cause
* more GD steps. You shouldn't need to alter this variable
* @param eps tolerance term for GD steps
*/
public void setEps(double eps)
{
if(eps < 0 || Double.isInfinite(eps) || Double.isNaN(eps))
throw new IllegalArgumentException("eps must be non-negative, not " + eps);
this.eps = eps;
}
public double getEps()
{
return eps;
}
/**
* Sets the shrinkage term used for the line search.
* @param beta the line search shrinkage term
*/
public void setBeta(double beta)
{
if(beta <= 0 || beta >= 1 || Double.isNaN(beta))
throw new IllegalArgumentException("shrinkage term must be in (0, 1), not " + beta);
this.beta = beta;
}
public double getBeta()
{
return beta;
}
@Override
public void optimize(double tolerance, Vec w, Vec x0, Function f, FunctionVec fp, boolean parallel)
{
if(fp == null)
fp = Function.forwardDifference(f);
//Algorithm 2 mOWL-QN: modified Orthant-Wise Limited memory Quasi-Newton
Vec lambdaMul = lambdaMultipler;
if(lambdaMultipler == null)
lambdaMul = new ConstantVector(1.0, x0.length());
Vec x_cur = x0.clone();
Vec x_grad = x0.clone();
Vec x_gradNext = x0.clone();
Vec x_grad_diff = x0.clone();
/**
* This value is where <> f(x) lives
*/
Vec v_k = x0.clone();
Vec d_k = x0.clone();
Vec p_k = x0.clone();
Vec x_alpha = x0.clone();
/**
* Difference between x_alpha and x_cur
*/
Vec x_diff = x0.clone();
//history for implicit H
List Rho = new DoubleList(m);
List S = new ArrayList<>(m);
List Y = new ArrayList<>(m);
double[] alphas = new double[m];
double f_x = f.f(x_cur, parallel);
f_x += getL1Penalty(x_cur, lambdaMul);
x_grad = fp.f(x_cur, x_grad, parallel);
//2: for k = 0 to maxiter do
for(int k = 0; k < maxIterations; k++)
{
double v_k_norm = 0;
//3: Compute v_k ← - <> f(xk)
for(int i = 0; i < x_grad.length(); i++)
{
double x_i = x_cur.get(i);
double l_i = x_grad.get(i);
double lambda_i = lambda*lambdaMul.get(i);
double newVal;
if(x_i > 0)
newVal = l_i+lambda_i;
else if(x_i < 0)
newVal = l_i-lambda_i;
else if(l_i+lambda_i < 0)//x_i == 0 is implicit
newVal = l_i+lambda_i;
else if(l_i-lambda_i > 0)//x_i == 0 is implicit
newVal = l_i-lambda_i;
else
newVal = 0;
v_k.set(i, -newVal);
v_k_norm += newVal*newVal;
}
v_k_norm = Math.sqrt(v_k_norm);
//Ik = {i ∈ {1, · · · ,n} : 0 < |x^k_i | ≤ ϵk,xk i vk i < 0}, where ϵk = min(∥vk∥, ϵ);
//we only really need to know if the set I_k is empty or not, the indicies are never used
double eps_k = Math.min(v_k_norm, eps);
boolean doGDstep = false;
for(int i = 0; i < v_k.length() && !doGDstep; i++)
{
double x_i = x_cur.get(i);
double v_i = v_k.get(i);
boolean isInI = 0 < abs(x_i) && abs(x_i) < eps_k && x_i*v_i < 0;
if(isInI)
doGDstep = true;
}
//5: Initialize α←α0;
double alpha = alpha_0;
double f_x_alpha = 0;//objective value for new x
if(!doGDstep)//6:if Ik = ∅ then (QN-step)
{
//8: Compute dk ←Hkvk using L-BFGS with S, Y ;
LBFGS.twoLoopHp(v_k, Rho, S, Y, d_k, alphas);
//9: Alignment: pk ←π(dk;vk);
for (int i = 0; i < p_k.length(); i++)
if (Math.signum(d_k.get(i)) == Math.signum(v_k.get(i)))
p_k.set(i, d_k.get(i));
else
p_k.set(i, 0.0);
//10: while Eq. (7) is not satisfied do
double rightSideMainTerm = gamma*v_k.dot(d_k);
alpha/=beta;//so when we multiply below we get the correct startng value
do
{
//11: α←αβ;
alpha *= beta;
//12: x^k(α)←π(x^k +α p^k; ξ^k);
x_cur.copyTo(x_alpha);
x_alpha.mutableSubtract(-alpha, p_k);
//projection step
for (int i = 0; i < p_k.length(); i++)
{
double x_i = x_cur.get(i);
double v_i = v_k.get(i);
double toUse = x_i != 0 ? x_i : v_i;
if (Math.signum(x_alpha.get(i)) != Math.signum(toUse))
x_alpha.set(i, 0.0);
}
f_x_alpha = f.f(x_alpha, parallel);
f_x_alpha += getL1Penalty(x_alpha, lambdaMul);
}
while(f_x_alpha > f_x - alpha*rightSideMainTerm );
x_alpha.copyTo(x_diff);
x_diff.mutableSubtract(x_cur);
}
else//(GD-step)
{
alpha/=beta;
do
{
alpha*=beta;
/*
* see section 2.3 of below to solve problem
* Gong, P., Zhang, C., Lu, Z., Huang, J., & Ye, J. (2013).
* A general iterative shrinkage and thresholding algorithm
* for non-convex regularized optimization problems.
* International Conference on Machine Learning, 28, 37–45.
* Retrieved from http://arxiv.org/abs/1303.4434
*
*/
//first use def u(k) = w(k) − ∇l(w)/t , where t = 1/alpha
x_grad.copyTo(x_alpha);
x_alpha.mutableMultiply(-alpha);
x_alpha.mutableAdd(x_cur);
//x_alpha noew has the value of u(k)
//we can now modify it into the correct solution using
//w^(k+1) = sign(u)max(0, |u|−λ/t)
for(int i = 0; i < x_alpha.length(); i++)
{
final double u_i = x_alpha.get(i);
final double lambda_i = lambda*lambdaMul.get(i);
x_alpha.set(i, signum(u_i)*max(0, abs(u_i)-lambda_i*alpha));
}
x_alpha.copyTo(x_diff);
x_diff.mutableSubtract(x_cur);
f_x_alpha = f.f(x_alpha, parallel);
f_x_alpha += getL1Penalty(x_alpha, lambdaMul);
}
while(f_x_alpha > f_x - gamma/(2*alpha)*x_diff.dot(x_diff));//eq(8) f(x^k(α)) ≤ f(x^k)− γ/(2α) || x^k(α)−x^k||^2
}
//update history
S.add(0, x_diff.clone());
x_gradNext = fp.f(x_alpha, x_gradNext, parallel);
//convergence check
double maxGrad = 0;
for(int i = 0; i < x_gradNext.length(); i++)
maxGrad = max(maxGrad, abs(x_gradNext.get(i)));
if(maxGrad < tolerance || f_x < tolerance || x_diff.pNorm(1) < tolerance )
break;
x_gradNext.copyTo(x_grad_diff);
x_grad_diff.mutableSubtract(x_grad);
Y.add(0, x_grad_diff.clone());
Rho.add(0, 1/x_diff.dot(x_grad_diff));
if(Double.isInfinite(Rho.get(0)) || Double.isNaN(Rho.get(0)))
{
Rho.clear();
S.clear();
Y.clear();
}
while(Rho.size() > m)
{
Rho.remove(m);
S.remove(m);
Y.remove(m);
}
//prepr for next iterations
f_x = f_x_alpha;
x_alpha.copyTo(x_cur);
x_gradNext.copyTo(x_grad);
}
x_cur.copyTo(w);
}
private double getL1Penalty(Vec w, Vec lambdaMul)
{
if(lambda <= 0)
return 0;
double pen = 0;
for(IndexValue iv : w)
pen += lambda*lambdaMul.get(iv.getIndex())*abs(iv.getValue());
return pen;
}
@Override
public void setMaximumIterations(int iterations)
{
if(iterations < 1)
throw new IllegalArgumentException("Number of iterations must be positive, not " + iterations);
this.maxIterations = iterations;
}
@Override
public int getMaximumIterations()
{
return maxIterations;
}
@Override
public ModifiedOWLQN clone()
{
return new ModifiedOWLQN(this);
}
}
Ads help maintain this website.