/*
* Copyright (C) 2016 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.stochastic;
import java.util.Arrays;
import jsat.linear.*;
/**
* Normalized AdaGrad provides an adaptive learning rate for each individual
* feature, and is mostly scale invariant to the data distribution. NAdaGrad is
* meant for online stochastic learning where the update is obtained from one
* dataum at a time, and it relies on the gradient being a scalar multiplication
* of the training data. If the gradient given us a {@link ScaledVector}, where
* the base vector is the datum, then NAdaGrad will work. If not the case,
* NAdaGrad will degenerate into something similar to normal {@link AdaGrad}.
*
* The current implementation assumes that the bias term is always scaled
* correctly, and does normal AdaGrad on it.
*
* See: Ross, S., Mineiro, P., & Langford, J. (2013). Normalized online
* learning. In Twenty-Ninth Conference on Uncertainty in Artificial
* Intelligence. Retrieved from
* here
*
* @author Edward Raff
*/
public class NAdaGrad implements GradientUpdater
{
private static final long serialVersionUID = 5138675613579751777L;
private double[] G;
private double[] S;
private double N;
private double biasG;
private long t;
/**
* Creates a new NAdaGrad updater
*/
public NAdaGrad()
{
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
public NAdaGrad(NAdaGrad toCopy)
{
if(toCopy.G != null)
this.G = Arrays.copyOf(toCopy.G, toCopy.G.length);
if(toCopy.S != null)
this.S = Arrays.copyOf(toCopy.S, toCopy.S.length);
this.biasG = toCopy.biasG;
this.N = toCopy.N;
this.t = toCopy.t;
}
@Override
public void update(Vec w, Vec grad, double eta)
{
update(w, grad, eta, 0, 0);
}
@Override
public double update(Vec w, Vec grad, double eta, double bias, double biasGrad)
{
if(grad instanceof ScaledVector)
{
t++;
//decompone our gradient back into parts, the multipler and raw datum
Vec x = ((ScaledVector)grad).getBase();
for(IndexValue iv : x)
{
final int indx = iv.getIndex();
final double abs_x_i = Math.abs(iv.getValue());
if(abs_x_i > S[indx])//(a)
{
w.set(indx, (w.get(indx)*S[indx])/abs_x_i);
S[indx] = abs_x_i;
}
//skip step (b) for simplicity since grad was already given to us
//(c)
N += abs_x_i*abs_x_i/(S[indx]*S[indx]);
}
double eta_roled = -eta*Math.sqrt(t/(N+1e-6));
for(IndexValue iv : grad)
{
final int indx = iv.getIndex();
final double grad_i = iv.getValue();
G[indx] += grad_i*grad_i;
final double g_ii = G[indx];
w.increment(indx, eta_roled*grad_i/(S[indx]*Math.sqrt(g_ii)));
}
double biasUpdate = eta*biasGrad/Math.sqrt(biasG);
biasG += biasGrad*biasGrad;
return biasUpdate;
}
else//lets degenerate into something at least similar to AdaGrad
{
double eta_roled = -eta*Math.sqrt((t+1)/Math.max(N, t+1));
for(IndexValue iv : grad)
{
final int indx = iv.getIndex();
final double grad_i = iv.getValue();
G[indx] += grad_i*grad_i;
final double g_ii = G[indx];
w.increment(indx, eta_roled*grad_i/(Math.max(S[indx], 1.0)*Math.sqrt(g_ii)));
}
double biasUpdate = eta*biasGrad/Math.sqrt(biasG);
biasG += biasGrad*biasGrad;
return biasUpdate;
}
}
@Override
public NAdaGrad clone()
{
return new NAdaGrad(this);
}
@Override
public void setup(int d)
{
G = new double[d];
S = new double[d];
biasG = 1;
t = 0;
}
}
Ads help maintain this website.