OjaNewton.cc File Reference

#include <string>
#include "gd.h"
#include "vw.h"
#include "rand48.h"
#include "reductions.h"
#include <math.h>
#include <memory>

Go to the source code of this file.

Classes
struct	update_data
struct	OjaNewton

Macros
#define	NORM2   (m + 1)

Functions
void	keep_example (vw &all, OjaNewton &, example &ec)
void	make_pred (update_data &data, float x, float &wref)
void	predict (OjaNewton &ON, base_learner &, example &ec)
void	update_Z_and_wbar (update_data &data, float x, float &wref)
void	compute_Zx_and_norm (update_data &data, float x, float &wref)
void	update_wbar_and_Zx (update_data &data, float x, float &wref)
void	update_normalization (update_data &data, float x, float &wref)
void	learn (OjaNewton &ON, base_learner &base, example &ec)
void	save_load (OjaNewton &ON, io_buf &model_file, bool read, bool text)
base_learner *	OjaNewton_setup (options_i &options, vw &all)

Macro Definition Documentation

NORM2

#define NORM2   (m + 1)

Definition at line 17 of file OjaNewton.cc.

Referenced by compute_Zx_and_norm(), OjaNewton::initialize_Z(), make_pred(), update_normalization(), update_wbar_and_Zx(), and update_Z_and_wbar().

Function Documentation

compute_Zx_and_norm()

void compute_Zx_and_norm	(	update_data &	data,
		float	x,
		float &	wref
	)

Definition at line 415 of file OjaNewton.cc.

References OjaNewton::D, OjaNewton::m, NORM2, update_data::norm2_x, OjaNewton::normalize, update_data::ON, and update_data::Zx.

{
  float* w = &wref;
  int m = data.ON->m;
  if (data.ON->normalize)
    x /= std::sqrt(w[NORM2]);

  for (int i = 1; i <= m; i++)
  {
    data.Zx[i] += w[i] * x * data.ON->D[i];
  }
  data.norm2_x += x * x;
}

keep_example()

void keep_example	(	vw &	all,
		OjaNewton &	,
		example &	ec
	)

Definition at line 373 of file OjaNewton.cc.

References output_and_account_example().

Referenced by OjaNewton_setup().

{ output_and_account_example(all, ec); }

learn()

void learn	(	OjaNewton &	ON,
		base_learner &	base,
		example &	ec
	)

Definition at line 453 of file OjaNewton.cc.

References OjaNewton::all, OjaNewton::buffer, OjaNewton::check(), OjaNewton::cnt, OjaNewton::compute_AZx(), OjaNewton::compute_delta(), OjaNewton::data, OjaNewton::epoch_size, VW::finish_example(), loss_function::first_derivative(), update_data::g, example::in_use, example::l, label_data::label, vw::loss, OjaNewton::m, update_data::norm2_x, OjaNewton::normalize, example::pred, predict(), polyprediction::scalar, vw::sd, polylabel::simple, update_data::sketch_cnt, OjaNewton::t, OjaNewton::update_A(), OjaNewton::update_b(), OjaNewton::update_eigenvalues(), OjaNewton::update_K(), label_data::weight, OjaNewton::weight_buffer, and update_data::Zx.

Referenced by OjaNewton_setup().

{
  assert(ec.in_use);

  // predict
  predict(ON, base, ec);

  update_data& data = ON.data;
  data.g = ON.all->loss->first_derivative(ON.all->sd, ec.pred.scalar, ec.l.simple.label) * ec.l.simple.weight;
  data.g /= 2;  // for half square loss

  if (ON.normalize)
    GD::foreach_feature<update_data, update_normalization>(*ON.all, ec, data);

  ON.buffer[ON.cnt] = &ec;
  ON.weight_buffer[ON.cnt++] = data.g / 2;

  if (ON.cnt == ON.epoch_size)
  {
    for (int k = 0; k < ON.epoch_size; k++, ON.t++)
    {
      example& ex = *(ON.buffer[k]);
      data.sketch_cnt = ON.weight_buffer[k];

      data.norm2_x = 0;
      memset(data.Zx, 0, sizeof(float) * (ON.m + 1));
      GD::foreach_feature<update_data, compute_Zx_and_norm>(*ON.all, ex, data);
      ON.compute_AZx();

      ON.update_eigenvalues();
      ON.compute_delta();

      ON.update_K();

      GD::foreach_feature<update_data, update_Z_and_wbar>(*ON.all, ex, data);
    }

    ON.update_A();
    // ON.update_D();
  }

  memset(data.Zx, 0, sizeof(float) * (ON.m + 1));
  GD::foreach_feature<update_data, update_wbar_and_Zx>(*ON.all, ec, data);
  ON.compute_AZx();

  ON.update_b();
  ON.check();

  if (ON.cnt == ON.epoch_size)
  {
    ON.cnt = 0;
    for (int k = 0; k < ON.epoch_size; k++)
    {
      VW::finish_example(*ON.all, *ON.buffer[k]);
    }
  }
}

make_pred()

void make_pred	(	update_data &	data,
		float	x,
		float &	wref
	)

Definition at line 375 of file OjaNewton.cc.

References OjaNewton::b, OjaNewton::D, OjaNewton::m, NORM2, OjaNewton::normalize, update_data::ON, and update_data::prediction.

{
  int m = data.ON->m;
  float* w = &wref;

  if (data.ON->normalize)
  {
    x /= std::sqrt(w[NORM2]);
  }

  data.prediction += w[0] * x;
  for (int i = 1; i <= m; i++)
  {
    data.prediction += w[i] * x * data.ON->D[i] * data.ON->b[i];
  }
}

OjaNewton_setup()

base_learner* OjaNewton_setup	(	options_i &	options,
		vw &	all
	)

Definition at line 535 of file OjaNewton.cc.

References OjaNewton::_random_state, OjaNewton::A, VW::config::option_group_definition::add(), add(), VW::config::options_i::add_and_parse(), OjaNewton::all, OjaNewton::alpha, update_data::AZx, OjaNewton::b, OjaNewton::buffer, OjaNewton::cnt, OjaNewton::D, OjaNewton::data, update_data::delta, OjaNewton::epoch_size, OjaNewton::ev, f, vw::get_random_state(), LEARNER::init_learner(), OjaNewton::K, keep_example(), learn(), OjaNewton::learning_rate_cnt, OjaNewton::m, LEARNER::make_base(), VW::config::make_option(), OjaNewton::normalize, update_data::ON, predict(), OjaNewton::random_init, save_load(), LEARNER::learner< T, E >::set_finish_example(), LEARNER::learner< T, E >::set_save_load(), parameters::stride(), parameters::stride_shift(), OjaNewton::t, OjaNewton::tmp, OjaNewton::vv, VW::config::options_i::was_supplied(), OjaNewton::weight_buffer, vw::weights, OjaNewton::zv, and update_data::Zx.

Referenced by parse_reductions().

{
  auto ON = scoped_calloc_or_throw<OjaNewton>();

  bool oja_newton;
  float alpha_inverse;

  // These two are the only two boolean options that default to true. For now going to do this hack
  // as the infrastructure doesn't easily support this possibility at the same time providing the
  // ease of bool switches elsewhere. It seems that the switch behavior is more critical because
  // of the positional data argument.
  std::string normalize = "true";
  std::string random_init = "true";
  option_group_definition new_options("OjaNewton options");
  new_options.add(make_option("OjaNewton", oja_newton).keep().help("Online Newton with Oja's Sketch"))
      .add(make_option("sketch_size", ON->m).default_value(10).help("size of sketch"))
      .add(make_option("epoch_size", ON->epoch_size).default_value(1).help("size of epoch"))
      .add(make_option("alpha", ON->alpha).default_value(1.f).help("mutiplicative constant for indentiy"))
      .add(make_option("alpha_inverse", alpha_inverse).help("one over alpha, similar to learning rate"))
      .add(make_option("learning_rate_cnt", ON->learning_rate_cnt)
               .default_value(2.f)
               .help("constant for the learning rate 1/t"))
      .add(make_option("normalize", normalize).help("normalize the features or not"))
      .add(make_option("random_init", random_init).help("randomize initialization of Oja or not"));
  options.add_and_parse(new_options);

  if (!options.was_supplied("OjaNewton"))
    return nullptr;

  ON->all = &all;
  ON->_random_state = all.get_random_state();

  ON->normalize = normalize == "true";
  ON->random_init = random_init == "true";

  if (options.was_supplied("alpha_inverse"))
    ON->alpha = 1.f / alpha_inverse;

  ON->cnt = 0;
  ON->t = 1;
  ON->ev = calloc_or_throw<float>(ON->m + 1);
  ON->b = calloc_or_throw<float>(ON->m + 1);
  ON->D = calloc_or_throw<float>(ON->m + 1);
  ON->A = calloc_or_throw<float*>(ON->m + 1);
  ON->K = calloc_or_throw<float*>(ON->m + 1);
  for (int i = 1; i <= ON->m; i++)
  {
    ON->A[i] = calloc_or_throw<float>(ON->m + 1);
    ON->K[i] = calloc_or_throw<float>(ON->m + 1);
    ON->A[i][i] = 1;
    ON->K[i][i] = 1;
    ON->D[i] = 1;
  }

  ON->buffer = calloc_or_throw<example*>(ON->epoch_size);
  ON->weight_buffer = calloc_or_throw<float>(ON->epoch_size);

  ON->zv = calloc_or_throw<float>(ON->m + 1);
  ON->vv = calloc_or_throw<float>(ON->m + 1);
  ON->tmp = calloc_or_throw<float>(ON->m + 1);

  ON->data.ON = ON.get();
  ON->data.Zx = calloc_or_throw<float>(ON->m + 1);
  ON->data.AZx = calloc_or_throw<float>(ON->m + 1);
  ON->data.delta = calloc_or_throw<float>(ON->m + 1);

  all.weights.stride_shift((uint32_t)ceil(log2(ON->m + 2)));

  learner<OjaNewton, example>& l = init_learner(ON, learn, predict, all.weights.stride());
  l.set_save_load(save_load);
  l.set_finish_example(keep_example);
  return make_base(l);
}

predict()

void predict	(	OjaNewton &	ON,
		base_learner &	,
		example &	ec
	)

Definition at line 392 of file OjaNewton.cc.

References OjaNewton::all, OjaNewton::data, GD::finalize_prediction(), example::partial_prediction, example::pred, update_data::prediction, polyprediction::scalar, and vw::sd.

Referenced by learn(), and OjaNewton_setup().

{
  ON.data.prediction = 0;
  GD::foreach_feature<update_data, make_pred>(*ON.all, ec, ON.data);
  ec.partial_prediction = (float)ON.data.prediction;
  ec.pred.scalar = GD::finalize_prediction(ON.all->sd, ec.partial_prediction);
}

save_load()

void save_load	(	OjaNewton &	ON,
		io_buf &	model_file,
		bool	read,
		bool	text
	)

Definition at line 511 of file OjaNewton.cc.

References OjaNewton::all, bin_text_read_write_fixed(), io_buf::files, initialize_regressor(), OjaNewton::initialize_Z(), GD::save_load_online_state(), GD::save_load_regressor(), vw::save_resume, v_array< T >::size(), and vw::weights.

Referenced by OjaNewton_setup().

{
  vw& all = *ON.all;
  if (read)
  {
    initialize_regressor(all);
    ON.initialize_Z(all.weights);
  }

  if (model_file.files.size() > 0)
  {
    bool resume = all.save_resume;
    std::stringstream msg;
    msg << ":" << resume << "\n";
    bin_text_read_write_fixed(model_file, (char*)&resume, sizeof(resume), "", read, msg, text);

    double temp = 0.;
    if (resume)
      GD::save_load_online_state(all, model_file, read, text, temp);
    else
      GD::save_load_regressor(all, model_file, read, text);
  }
}

update_normalization()

void update_normalization	(	update_data &	data,
		float	x,
		float &	wref
	)

Definition at line 445 of file OjaNewton.cc.

References update_data::g, OjaNewton::m, NORM2, and update_data::ON.

{
  float* w = &wref;
  int m = data.ON->m;

  w[NORM2] += x * x * data.g * data.g;
}

update_wbar_and_Zx()

void update_wbar_and_Zx	(	update_data &	data,
		float	x,
		float &	wref
	)

Definition at line 429 of file OjaNewton.cc.

References OjaNewton::alpha, OjaNewton::D, update_data::g, OjaNewton::m, NORM2, OjaNewton::normalize, update_data::ON, and update_data::Zx.

{
  float* w = &wref;
  int m = data.ON->m;
  if (data.ON->normalize)
    x /= std::sqrt(w[NORM2]);

  float g = data.g * x;

  for (int i = 1; i <= m; i++)
  {
    data.Zx[i] += w[i] * x * data.ON->D[i];
  }
  w[0] -= g / data.ON->alpha;
}

update_Z_and_wbar()

void update_Z_and_wbar	(	update_data &	data,
		float	x,
		float &	wref
	)

Definition at line 400 of file OjaNewton.cc.

References update_data::bdelta, OjaNewton::D, update_data::delta, OjaNewton::m, NORM2, OjaNewton::normalize, update_data::ON, and update_data::sketch_cnt.

{
  float* w = &wref;
  int m = data.ON->m;
  if (data.ON->normalize)
    x /= std::sqrt(w[NORM2]);
  float s = data.sketch_cnt * x;

  for (int i = 1; i <= m; i++)
  {
    w[i] += data.delta[i] * s / data.ON->D[i];
  }
  w[0] -= s * data.bdelta;
}