stagewise_poly.cc File Reference

#include <float.h>
#include <cassert>
#include "gd.h"
#include "accumulate.h"
#include "reductions.h"
#include "vw.h"
#include "vw_allreduce.h"

Go to the source code of this file.

Classes
struct	sort_data
struct	stagewise_poly

Functions
uint64_t	stride_shift (const stagewise_poly &poly, uint64_t idx)
uint64_t	stride_un_shift (const stagewise_poly &poly, uint64_t idx)
uint64_t	do_ft_offset (const stagewise_poly &poly, uint64_t idx)
uint64_t	un_ft_offset (const stagewise_poly &poly, uint64_t idx)
uint64_t	wid_mask (const stagewise_poly &poly, uint64_t wid)
uint64_t	wid_mask_un_shifted (const stagewise_poly &poly, uint64_t wid)
uint64_t	constant_feat (const stagewise_poly &poly)
uint64_t	constant_feat_masked (const stagewise_poly &poly)
size_t	depthsbits_sizeof (const stagewise_poly &poly)
void	depthsbits_create (stagewise_poly &poly)
bool	parent_get (const stagewise_poly &poly, uint64_t wid)
void	parent_toggle (stagewise_poly &poly, uint64_t wid)
bool	cycle_get (const stagewise_poly &poly, uint64_t wid)
void	cycle_toggle (stagewise_poly &poly, uint64_t wid)
uint8_t	min_depths_get (const stagewise_poly &poly, uint64_t wid)
void	min_depths_set (stagewise_poly &poly, uint64_t wid, uint8_t depth)
void	sanity_check_state (stagewise_poly &poly)
uint64_t	child_wid (const stagewise_poly &poly, uint64_t wi_atomic, uint64_t wi_general)
void	sort_data_create (stagewise_poly &poly)
void	sort_data_ensure_sz (stagewise_poly &poly, size_t len)
int	sort_data_compar_heap (sort_data &a_v, sort_data &b_v)
void	sort_data_update_support (stagewise_poly &poly)
void	synthetic_reset (stagewise_poly &poly, example &ec)
void	synthetic_decycle (stagewise_poly &poly)
void	synthetic_create_rec (stagewise_poly &poly, float v, uint64_t findex)
void	synthetic_create (stagewise_poly &poly, example &ec, bool training)
void	predict (stagewise_poly &poly, single_learner &base, example &ec)
void	learn (stagewise_poly &poly, single_learner &base, example &ec)
void	reduce_min (uint8_t &v1, const uint8_t &v2)
void	reduce_min_max (uint8_t &v1, const uint8_t &v2)
void	end_pass (stagewise_poly &poly)
void	finish_example (vw &all, stagewise_poly &poly, example &ec)
void	save_load (stagewise_poly &poly, io_buf &model_file, bool read, bool text)
base_learner *	stagewise_poly_setup (options_i &options, vw &all)

Variables
static constexpr uint32_t	parent_bit = 1
static constexpr uint32_t	cycle_bit = 2
static constexpr uint32_t	tree_atomics = 134
static constexpr float	tolerance = 1e-9f
static constexpr uint32_t	indicator_bit = 128
static constexpr uint32_t	default_depth = 127

Function Documentation

child_wid()

uint64_t child_wid ( const stagewise_poly &  poly, uint64_t  wi_atomic, uint64_t  wi_general  )

inline

Definition at line 205 of file stagewise_poly.cc.

References constant_feat_masked(), stride_shift(), stride_un_shift(), and wid_mask().

Referenced by synthetic_create_rec().

{
  assert(wi_atomic == wid_mask(poly, wi_atomic));
  assert(wi_general == wid_mask(poly, wi_general));
  assert((wi_atomic & (stride_shift(poly, 1) - 1)) == 0);
  assert((wi_general & (stride_shift(poly, 1) - 1)) == 0);

  if (wi_atomic == constant_feat_masked(poly))
    return wi_general;
  else if (wi_general == constant_feat_masked(poly))
    return wi_atomic;
  else
  {
    // This is basically the "Fowler–Noll–Vo" hash.  Ideally, the hash would be invariant
    // to the monomial, whereas this here is sensitive to the path followed, but whatever.
    // the two main big differences with FNV are: (1) the "*constant" case should also have
    // a big prime (so the default hash shouldn't be identity on small things, and (2) the
    // size should not just be a power of 2, but some big prime.
    return wid_mask(
        poly, stride_shift(poly, stride_un_shift(poly, wi_atomic) ^ (16777619 * stride_un_shift(poly, wi_general))));
  }
}

constant_feat()

uint64_t constant_feat ( const stagewise_poly &  poly )

inline

Definition at line 120 of file stagewise_poly.cc.

References stagewise_poly::all, constant, stride_shift(), and vw::wpp.

Referenced by constant_feat_masked().

{ return stride_shift(poly, constant * poly.all->wpp); }

constant_feat_masked()

uint64_t constant_feat_masked ( const stagewise_poly &  poly )

inline

Definition at line 122 of file stagewise_poly.cc.

References constant_feat(), and wid_mask().

Referenced by child_wid(), sort_data_update_support(), and synthetic_create().

{ return wid_mask(poly, constant_feat(poly)); }

cycle_get()

bool cycle_get ( const stagewise_poly &  poly, uint64_t  wid  )

inline

Definition at line 150 of file stagewise_poly.cc.

References cycle_bit, stagewise_poly::depthsbits, stride_shift(), and wid_mask_un_shifted().

Referenced by sanity_check_state(), synthetic_create_rec(), and synthetic_decycle().

{
  // note: intentionally leaving out ft_offset.
  assert(wid % stride_shift(poly, 1) == 0);
  if ((poly.depthsbits[wid_mask_un_shifted(poly, wid) * 2 + 1] & cycle_bit) > 0)
    return true;
  else
    return false;
}

cycle_toggle()

void cycle_toggle ( stagewise_poly &  poly, uint64_t  wid  )

inline

Definition at line 160 of file stagewise_poly.cc.

References cycle_bit, stagewise_poly::depthsbits, stride_shift(), and wid_mask_un_shifted().

Referenced by synthetic_create_rec(), and synthetic_decycle().

{
  // note: intentionally leaving out ft_offset.
  assert(wid % stride_shift(poly, 1) == 0);
  poly.depthsbits[wid_mask_un_shifted(poly, wid) * 2 + 1] ^= cycle_bit;
}

depthsbits_create()

void depthsbits_create

(

stagewise_poly &

poly

)

Definition at line 126 of file stagewise_poly.cc.

References stagewise_poly::all, default_depth, stagewise_poly::depthsbits, indicator_bit, and vw::length().

Referenced by stagewise_poly_setup().

{
  poly.depthsbits = calloc_or_throw<uint8_t>(2 * poly.all->length());
  for (uint64_t i = 0; i < poly.all->length() * 2; i += 2)
  {
    poly.depthsbits[i] = default_depth;
    poly.depthsbits[i + 1] = indicator_bit;
  }
}

depthsbits_sizeof()

size_t depthsbits_sizeof ( const stagewise_poly &  poly )

inline

Definition at line 124 of file stagewise_poly.cc.

References stagewise_poly::all, and vw::length().

Referenced by end_pass(), and save_load().

{ return (2 * poly.all->length() * sizeof(uint8_t)); }

do_ft_offset()

uint64_t do_ft_offset ( const stagewise_poly &  poly, uint64_t  idx  )

inline

Definition at line 91 of file stagewise_poly.cc.

References example_predict::ft_offset, stagewise_poly::original_ec, and stagewise_poly::synth_ec.

Referenced by min_depths_get(), min_depths_set(), parent_get(), and parent_toggle().

{
  // std::cout << poly.synth_ec.ft_offset << "  " << poly.original_ec->ft_offset << std::endl;
  assert(!poly.original_ec || poly.synth_ec.ft_offset == poly.original_ec->ft_offset);
  return idx + poly.synth_ec.ft_offset;
}

end_pass()

void end_pass

(

stagewise_poly &

poly

)

Definition at line 581 of file stagewise_poly.cc.

References accumulate_scalar(), stagewise_poly::all, vw::all_reduce, stagewise_poly::batch_sz, stagewise_poly::depthsbits, depthsbits_sizeof(), stagewise_poly::num_examples, stagewise_poly::num_examples_sync, stagewise_poly::numpasses, vw::numpasses, sanity_check_state(), stagewise_poly::sum_input_sparsity, stagewise_poly::sum_input_sparsity_sync, stagewise_poly::sum_sparsity, stagewise_poly::sum_sparsity_sync, and stagewise_poly::update_support.

{
  if (!!poly.batch_sz || (poly.all->all_reduce != nullptr && poly.numpasses > 1))
    return;

  uint64_t sum_sparsity_inc = poly.sum_sparsity - poly.sum_sparsity_sync;
  uint64_t sum_input_sparsity_inc = poly.sum_input_sparsity - poly.sum_input_sparsity_sync;
  uint64_t num_examples_inc = poly.num_examples - poly.num_examples_sync;

#ifdef DEBUG
  std::cout << "Sanity before allreduce\n";
  sanity_check_state(poly);
#endif  // DEBUG

  vw &all = *poly.all;
  if (all.all_reduce != nullptr)
  {
    /*
     * The following is inconsistent with the transplant code in
     * synthetic_create_rec(), which clears parent bits on depth mismatches.
     * But it's unclear what the right behavior is in general for either
     * case...
     */
    all_reduce<uint8_t, reduce_min_max>(all, poly.depthsbits, depthsbits_sizeof(poly));

    sum_input_sparsity_inc = (uint64_t)accumulate_scalar(all, (float)sum_input_sparsity_inc);
    sum_sparsity_inc = (uint64_t)accumulate_scalar(all, (float)sum_sparsity_inc);
    num_examples_inc = (uint64_t)accumulate_scalar(all, (float)num_examples_inc);
  }

  poly.sum_input_sparsity_sync = poly.sum_input_sparsity_sync + sum_input_sparsity_inc;
  poly.sum_input_sparsity = poly.sum_input_sparsity_sync;
  poly.sum_sparsity_sync = poly.sum_sparsity_sync + sum_sparsity_inc;
  poly.sum_sparsity = poly.sum_sparsity_sync;
  poly.num_examples_sync = poly.num_examples_sync + num_examples_inc;
  poly.num_examples = poly.num_examples_sync;

#ifdef DEBUG
  std::cout << "Sanity after allreduce\n";
  sanity_check_state(poly);
#endif  // DEBUG

  if (poly.numpasses != poly.all->numpasses)
  {
    poly.update_support = true;
    poly.numpasses++;
  }
}

finish_example()

void finish_example	(	vw &	all,
		stagewise_poly &	poly,
		example &	ec
	)

Definition at line 630 of file stagewise_poly.cc.

References VW::finish_example(), example::num_features, output_and_account_example(), and stagewise_poly::synth_ec.

Referenced by stagewise_poly_setup().

{
  size_t temp_num_features = ec.num_features;
  ec.num_features = poly.synth_ec.num_features;
  output_and_account_example(all, ec);
  ec.num_features = temp_num_features;
  VW::finish_example(all, ec);
}

learn()

void learn	(	stagewise_poly &	poly,
		single_learner &	base,
		example &	ec
	)

Definition at line 506 of file stagewise_poly.cc.

References stagewise_poly::all, vw::all_reduce, stagewise_poly::batch_sz, stagewise_poly::batch_sz_double, example::example_counter, example::l, label_data::label, stagewise_poly::last_example_counter, LEARNER::learner< T, E >::learn(), stagewise_poly::next_batch_sz, stagewise_poly::numpasses, stagewise_poly::original_ec, example::partial_prediction, example::pred, predict(), polyprediction::scalar, polylabel::simple, sort_data_update_support(), stagewise_poly::synth_ec, synthetic_create(), vw::training, stagewise_poly::update_support, and example::updated_prediction.

Referenced by stagewise_poly_setup().

{
  bool training = poly.all->training && ec.l.simple.label != FLT_MAX;
  poly.original_ec = &ec;

  if (training)
  {
    if (poly.update_support)
    {
      sort_data_update_support(poly);
      poly.update_support = false;
    }

    synthetic_create(poly, ec, training);
    base.learn(poly.synth_ec);
    ec.partial_prediction = poly.synth_ec.partial_prediction;
    ec.updated_prediction = poly.synth_ec.updated_prediction;
    ec.pred.scalar = poly.synth_ec.pred.scalar;

    if (ec.example_counter
        // following line is to avoid repeats when multiple reductions on same example.
        // XXX ideally, would get all "copies" of an example before scheduling the support
        // update, but how do we know?
        && poly.last_example_counter != ec.example_counter && poly.batch_sz &&
        ((poly.batch_sz_double && !(ec.example_counter % poly.next_batch_sz)) ||
            (!poly.batch_sz_double && !(ec.example_counter % poly.batch_sz))))
    {
      poly.next_batch_sz *= 2;  // no effect when !poly.batch_sz_double
      poly.update_support = (poly.all->all_reduce == nullptr || poly.numpasses == 1);
    }
    poly.last_example_counter = ec.example_counter;
  }
  else
    predict(poly, base, ec);
}

min_depths_get()

uint8_t min_depths_get ( const stagewise_poly &  poly, uint64_t  wid  )

inline

Definition at line 167 of file stagewise_poly.cc.

References stagewise_poly::depthsbits, do_ft_offset(), stride_shift(), and stride_un_shift().

Referenced by sanity_check_state(), and synthetic_create_rec().

{
  assert(wid % stride_shift(poly, 1) == 0);
  assert(do_ft_offset(poly, wid) % stride_shift(poly, 1) == 0);
  return poly.depthsbits[stride_un_shift(poly, do_ft_offset(poly, wid)) * 2];
}

min_depths_set()

void min_depths_set ( stagewise_poly &  poly, uint64_t  wid, uint8_t  depth  )

inline

Definition at line 174 of file stagewise_poly.cc.

References stagewise_poly::depthsbits, do_ft_offset(), stride_shift(), and stride_un_shift().

Referenced by synthetic_create_rec().

{
  assert(wid % stride_shift(poly, 1) == 0);
  assert(do_ft_offset(poly, wid) % stride_shift(poly, 1) == 0);
  poly.depthsbits[stride_un_shift(poly, do_ft_offset(poly, wid)) * 2] = depth;
}

parent_get()

bool parent_get ( const stagewise_poly &  poly, uint64_t  wid  )

inline

Definition at line 136 of file stagewise_poly.cc.

References stagewise_poly::depthsbits, do_ft_offset(), parent_bit, stride_shift(), and wid_mask_un_shifted().

Referenced by sanity_check_state(), sort_data_update_support(), and synthetic_create_rec().

{
  assert(wid % stride_shift(poly, 1) == 0);
  assert(do_ft_offset(poly, wid) % stride_shift(poly, 1) == 0);
  return poly.depthsbits[wid_mask_un_shifted(poly, do_ft_offset(poly, wid)) * 2 + 1] & parent_bit;
}

parent_toggle()

void parent_toggle ( stagewise_poly &  poly, uint64_t  wid  )

inline

Definition at line 143 of file stagewise_poly.cc.

References stagewise_poly::depthsbits, do_ft_offset(), parent_bit, stride_shift(), and wid_mask_un_shifted().

Referenced by sort_data_update_support(), and synthetic_create_rec().

{
  assert(wid % stride_shift(poly, 1) == 0);
  assert(do_ft_offset(poly, wid) % stride_shift(poly, 1) == 0);
  poly.depthsbits[wid_mask_un_shifted(poly, do_ft_offset(poly, wid)) * 2 + 1] ^= parent_bit;
}

predict()

void predict	(	stagewise_poly &	poly,
		single_learner &	base,
		example &	ec
	)

Definition at line 496 of file stagewise_poly.cc.

References stagewise_poly::original_ec, example::partial_prediction, example::pred, LEARNER::learner< T, E >::predict(), polyprediction::scalar, stagewise_poly::synth_ec, synthetic_create(), and example::updated_prediction.

Referenced by learn(), and stagewise_poly_setup().

{
  poly.original_ec = &ec;
  synthetic_create(poly, ec, false);
  base.predict(poly.synth_ec);
  ec.partial_prediction = poly.synth_ec.partial_prediction;
  ec.updated_prediction = poly.synth_ec.updated_prediction;
  ec.pred.scalar = poly.synth_ec.pred.scalar;
}

reduce_min()

void reduce_min	(	uint8_t &	v1,
		const uint8_t &	v2
	)

Definition at line 542 of file stagewise_poly.cc.

References default_depth.

{
  if (v1 == default_depth)
    v1 = v2;
  else if (v2 != default_depth)
    v1 = (v1 <= v2) ? v1 : v2;
}

reduce_min_max()

void reduce_min_max	(	uint8_t &	v1,
		const uint8_t &	v2
	)

Definition at line 550 of file stagewise_poly.cc.

References default_depth, and indicator_bit.

{
  bool parent_or_depth;
  if (v1 & indicator_bit)
    parent_or_depth = true;
  else
    parent_or_depth = false;
  bool p_or_d2;
  if (v2 & indicator_bit)
    p_or_d2 = true;
  else
    p_or_d2 = false;
  if (parent_or_depth != p_or_d2)
  {
#ifdef DEBUG
    std::cout << "Reducing parent with depth!!!!!";
#endif  // DEBUG
    return;
  }

  if (parent_or_depth)
    v1 = (v1 >= v2) ? v1 : v2;
  else
  {
    if (v1 == default_depth)
      v1 = v2;
    else if (v2 != default_depth)
      v1 = (v1 <= v2) ? v1 : v2;
  }
}

sanity_check_state()

void sanity_check_state

(

stagewise_poly &

poly

)

Definition at line 182 of file stagewise_poly.cc.

References stagewise_poly::all, cycle_bit, cycle_get(), default_depth, parameters::dense_weights, stagewise_poly::depthsbits, indicator_bit, vw::length(), min_depths_get(), parent_bit, parent_get(), parameters::sparse, parameters::sparse_weights, stride_shift(), vw::weights, and wid_mask_un_shifted().

Referenced by end_pass(), and sort_data_update_support().

{
  for (uint64_t i = 0; i != poly.all->length(); ++i)
  {
    uint64_t wid = stride_shift(poly, i);

    assert(!cycle_get(poly, wid));

    assert(!(min_depths_get(poly, wid) == default_depth && parent_get(poly, wid)));

    if (poly.all->weights.sparse)
      assert(!(min_depths_get(poly, wid) == default_depth && fabsf(poly.all->weights.sparse_weights[wid]) > 0));
    else
      assert(!(min_depths_get(poly, wid) == default_depth && fabsf(poly.all->weights.dense_weights[wid]) > 0));
    // assert( min_depths_get(poly, wid) != default_depth && fabsf(poly.all->weights[wid]) < tolerance );

    assert(!(poly.depthsbits[wid_mask_un_shifted(poly, wid) * 2 + 1] & ~(parent_bit + cycle_bit + indicator_bit)));
  }
}

save_load()

void save_load	(	stagewise_poly &	poly,
		io_buf &	model_file,
		bool	read,
		bool	text
	)

Definition at line 639 of file stagewise_poly.cc.

References bin_text_read_write_fixed(), stagewise_poly::depthsbits, depthsbits_sizeof(), io_buf::files, and v_array< T >::size().

Referenced by stagewise_poly_setup().

{
  if (model_file.files.size() > 0)
  {
    std::stringstream msg;
    bin_text_read_write_fixed(
        model_file, (char *)poly.depthsbits, (uint32_t)depthsbits_sizeof(poly), "", read, msg, text);
  }
  // unfortunately, following can't go here since save_load called before gd::save_load and thus
  // weight vector state uninitialiazed.
  //#ifdef DEBUG
  //      std::cout << "Sanity check after save_load... " << flush;
  //      sanity_check_state(poly);
  //      std::cout << "done" << std::endl;
  //#endif //DEBUG
}

sort_data_compar_heap()

int sort_data_compar_heap	(	sort_data &	a_v,
		sort_data &	b_v
	)

Definition at line 259 of file stagewise_poly.cc.

References sort_data::weightsal.

Referenced by sort_data_update_support().

{ return (a_v.weightsal > b_v.weightsal); }

sort_data_create()

void sort_data_create

(

stagewise_poly &

poly

)

Definition at line 228 of file stagewise_poly.cc.

References stagewise_poly::sd, and stagewise_poly::sd_len.

Referenced by stagewise_poly_setup().

{
  poly.sd = nullptr;
  poly.sd_len = 0;
}

sort_data_ensure_sz()

void sort_data_ensure_sz	(	stagewise_poly &	poly,
		size_t	len
	)

Definition at line 234 of file stagewise_poly.cc.

References stagewise_poly::all, vw::length(), stagewise_poly::sd, and stagewise_poly::sd_len.

Referenced by sort_data_update_support().

{
  if (poly.sd_len < len)
  {
    size_t len_candidate = 2 * len;
#ifdef DEBUG
    std::cout << "resizing sort buffer; current size " << poly.sd_len;
#endif  // DEBUG
    poly.sd_len = (len_candidate > poly.all->length()) ? poly.all->length() : len_candidate;
#ifdef DEBUG
    std::cout << ", new size " << poly.sd_len << std::endl;
#endif              // DEBUG
    free(poly.sd);  // okay for null.
    poly.sd = calloc_or_throw<sort_data>(poly.sd_len);
  }
  assert(len <= poly.sd_len);
}

sort_data_update_support()

void sort_data_update_support

(

stagewise_poly &

poly

)

Definition at line 274 of file stagewise_poly.cc.

References stagewise_poly::all, constant_feat_masked(), example_predict::ft_offset, vw::length(), vw::normalized_idx, stagewise_poly::num_examples, stagewise_poly::original_ec, parent_get(), parent_toggle(), sanity_check_state(), stagewise_poly::sched_exponent, stagewise_poly::sd, stagewise_poly::sd_len, sort_data_compar_heap(), sort_data_ensure_sz(), stride_shift(), stagewise_poly::sum_input_sparsity, stagewise_poly::synth_ec, tolerance, vw::weights, sort_data::weightsal, and sort_data::wid.

Referenced by learn().

{
  assert(poly.num_examples);

  // ft_offset affects parent_set / parent_get.  This state must be reset at end.
  uint64_t pop_ft_offset = poly.original_ec->ft_offset;
  poly.synth_ec.ft_offset = 0;
  assert(poly.original_ec);
  poly.original_ec->ft_offset = 0;

  size_t num_new_features = (size_t)pow(poly.sum_input_sparsity * 1.0f / poly.num_examples, poly.sched_exponent);
  num_new_features = (num_new_features > poly.all->length()) ? (uint64_t)poly.all->length() : num_new_features;
  sort_data_ensure_sz(poly, num_new_features);

  sort_data *heap_end = poly.sd;
  std::make_heap(poly.sd, heap_end, sort_data_compar_heap);  // redundant
  for (uint64_t i = 0; i != poly.all->length(); ++i)
  {
    uint64_t wid = stride_shift(poly, i);
    if (!parent_get(poly, wid) && wid != constant_feat_masked(poly))
    {
      float weightsal = (fabsf(poly.all->weights[wid]) * poly.all->weights[poly.all->normalized_idx + (wid)]);
      /*
       * here's some depth penalization code.  It was found to not improve
       * statistical performance, and meanwhile it is verified as giving
       * a nontrivial computational hit, thus commented out.
       *
       * - poly.magic_argument
       * sqrtf(min_depths_get(poly, stride_shift(poly, i)) * 1.0 / poly.num_examples)
       */
      ;
      if (weightsal > tolerance)
      {
        assert(heap_end >= poly.sd);
        assert(heap_end <= poly.sd + num_new_features);

        if (heap_end - poly.sd == (int)num_new_features && poly.sd->weightsal < weightsal)
        {
          std::pop_heap(poly.sd, heap_end, sort_data_compar_heap);
          --heap_end;
        }

        assert(heap_end >= poly.sd);
        assert(heap_end < poly.sd + poly.sd_len);

        if (heap_end - poly.sd < (int)num_new_features)
        {
          heap_end->weightsal = weightsal;
          heap_end->wid = wid;
          ++heap_end;
          std::push_heap(poly.sd, heap_end, sort_data_compar_heap);
        }
      }
    }
  }
  num_new_features = (uint64_t)(heap_end - poly.sd);

#ifdef DEBUG
  // eyeballing weights a pain if unsorted.
  qsort(poly.sd, num_new_features, sizeof(sort_data), sort_data_compar);
#endif  // DEBUG

  for (uint64_t pos = 0; pos < num_new_features && pos < poly.sd_len; ++pos)
  {
    assert(!parent_get(poly, poly.sd[pos].wid) && poly.sd[pos].weightsal > tolerance &&
        poly.sd[pos].wid != constant_feat_masked(poly));
    parent_toggle(poly, poly.sd[pos].wid);
#ifdef DEBUG
    std::cout << "Adding feature " << pos << "/" << num_new_features << " || wid " << poly.sd[pos].wid
              << " || sort value " << poly.sd[pos].weightsal << std::endl;
#endif  // DEBUG
  }

#ifdef DEBUG
  std::cout << "depths:";
  for (uint64_t depth = 0; depth <= poly.max_depth && depth < sizeof(poly.depths) / sizeof(*poly.depths); ++depth)
    std::cout << "  [" << depth << "] = " << poly.depths[depth];
  std::cout << std::endl;

  std::cout << "Sanity check after sort... " << flush;
  sanity_check_state(poly);
  std::cout << "done" << std::endl;
#endif  // DEBUG

  // it's okay that these may have been initially unequal; synth_ec value irrelevant so far.
  poly.original_ec->ft_offset = pop_ft_offset;
  poly.synth_ec.ft_offset = pop_ft_offset;
}

stagewise_poly_setup()

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

Definition at line 656 of file stagewise_poly.cc.

References VW::config::option_group_definition::add(), add(), VW::config::options_i::add_and_parse(), LEARNER::as_singleline(), depthsbits_create(), LEARNER::end_pass(), finish_example(), LEARNER::init_learner(), learn(), LEARNER::make_base(), VW::config::make_option(), predict(), save_load(), LEARNER::learner< T, E >::set_end_pass(), LEARNER::learner< T, E >::set_finish_example(), LEARNER::learner< T, E >::set_save_load(), setup_base(), and sort_data_create().

Referenced by parse_reductions().

{
  auto poly = scoped_calloc_or_throw<stagewise_poly>();
  bool stage_poly = false;
  option_group_definition new_options("Stagewise polynomial options");
  new_options.add(make_option("stage_poly", stage_poly).keep().help("use stagewise polynomial feature learning"))
      .add(make_option("sched_exponent", poly->sched_exponent)
               .default_value(1.f)
               .help("exponent controlling quantity of included features"))
      .add(make_option("batch_sz", poly->batch_sz)
               .default_value(1000)
               .help("multiplier on batch size before including more features"))
      .add(make_option("batch_sz_no_doubling", poly->batch_sz_double).help("batch_sz does not double"));
#ifdef MAGIC_ARGUMENT
  new_options.add(
      make_typed_option("magic_argument", poly->magic_argument).default_value(0.).help("magical feature flag"));
#endif  // MAGIC_ARGUMENT
  options.add_and_parse(new_options);

  if (!stage_poly)
    return nullptr;

  poly->all = &all;
  depthsbits_create(*poly.get());
  sort_data_create(*poly.get());

  poly->batch_sz_double = !poly->batch_sz_double;

  poly->sum_sparsity = 0;
  poly->sum_input_sparsity = 0;
  poly->num_examples = 0;
  poly->sum_sparsity_sync = 0;
  poly->sum_input_sparsity_sync = 0;
  poly->num_examples_sync = 0;
  poly->last_example_counter = -1;
  poly->numpasses = 1;
  poly->update_support = false;
  poly->original_ec = nullptr;
  poly->next_batch_sz = poly->batch_sz;

  learner<stagewise_poly, example> &l = init_learner(poly, as_singleline(setup_base(options, all)), learn, predict);
  l.set_save_load(save_load);
  l.set_finish_example(finish_example);
  l.set_end_pass(end_pass);

  return make_base(l);
}

stride_shift()

uint64_t stride_shift ( const stagewise_poly &  poly, uint64_t  idx  )

inline

Definition at line 81 of file stagewise_poly.cc.

References stagewise_poly::all, parameters::stride_shift(), and vw::weights.

Referenced by Search::add_neighbor_features(), GD::audit_feature(), child_wid(), constant_feat(), cycle_get(), cycle_toggle(), VW::export_example(), learn_with_metrics(), min_depths_get(), min_depths_set(), parent_get(), parent_toggle(), predict_or_learn(), MWT::predict_or_learn(), GD::print_lda_features(), sanity_check_state(), MARGINAL::save_load(), save_load(), sort_data_update_support(), sparse_parameters::stride_shift(), and synthetic_create_rec().

{
  return idx << poly.all->weights.stride_shift();
}

stride_un_shift()

uint64_t stride_un_shift ( const stagewise_poly &  poly, uint64_t  idx  )

inline

Definition at line 86 of file stagewise_poly.cc.

References stagewise_poly::all, parameters::stride_shift(), and vw::weights.

Referenced by child_wid(), min_depths_get(), min_depths_set(), and wid_mask_un_shifted().

{
  return idx >> poly.all->weights.stride_shift();
}

synthetic_create()

void synthetic_create	(	stagewise_poly &	poly,
		example &	ec,
		bool	training
	)

Definition at line 470 of file stagewise_poly.cc.

References stagewise_poly::all, constant_feat_masked(), stagewise_poly::cur_depth, example_predict::feature_space, stagewise_poly::num_examples, example::num_features, stagewise_poly::original_ec, stagewise_poly::sum_input_sparsity, stagewise_poly::sum_sparsity, stagewise_poly::synth_ec, stagewise_poly::synth_rec_f, synthetic_decycle(), synthetic_reset(), example::total_sum_feat_sq, stagewise_poly::training, tree_atomics, feature::weight_index, and feature::x.

Referenced by learn(), and predict().

{
  synthetic_reset(poly, ec);

  poly.cur_depth = 0;

  poly.synth_rec_f.x = 1.0;
  poly.synth_rec_f.weight_index = constant_feat_masked(poly);  // note: not ft_offset'd
  poly.training = training;
  /*
   * Another choice is to mark the constant feature as the single initial
   * parent, and recurse just on that feature (which arguably correctly interprets poly.cur_depth).
   * Problem with this is if there is a collision with the root...
   */
  GD::foreach_feature<stagewise_poly, uint64_t, synthetic_create_rec>(*poly.all, *poly.original_ec, poly);
  synthetic_decycle(poly);
  poly.synth_ec.total_sum_feat_sq = poly.synth_ec.feature_space[tree_atomics].sum_feat_sq;

  if (training)
  {
    poly.sum_sparsity += poly.synth_ec.num_features;
    poly.sum_input_sparsity += ec.num_features;
    poly.num_examples += 1;
  }
}

synthetic_create_rec()

void synthetic_create_rec	(	stagewise_poly &	poly,
		float	v,
		uint64_t	findex
	)

Definition at line 415 of file stagewise_poly.cc.

References stagewise_poly::all, child_wid(), stagewise_poly::cur_depth, cycle_get(), cycle_toggle(), default_depth, example_predict::feature_space, min_depths_get(), min_depths_set(), example::num_features, stagewise_poly::original_ec, parent_get(), parent_toggle(), stride_shift(), stagewise_poly::synth_ec, stagewise_poly::synth_rec_f, stagewise_poly::training, tree_atomics, un_ft_offset(), feature::weight_index, wid_mask(), and feature::x.

{
  // Note: need to un_ft_shift since gd::foreach_feature bakes in the offset.
  uint64_t wid_atomic = wid_mask(poly, un_ft_offset(poly, findex));
  uint64_t wid_cur = child_wid(poly, wid_atomic, poly.synth_rec_f.weight_index);
  assert(wid_atomic % stride_shift(poly, 1) == 0);

  // Note: only mutate learner state when in training mode.  This is because
  // the average test errors across multiple data sets should be equal to
  // the test error on the merged dataset (which is violated if the code
  // below is run at training time).
  if (poly.cur_depth < min_depths_get(poly, wid_cur) && poly.training)
  {
    if (parent_get(poly, wid_cur))
    {
#ifdef DEBUG
      std::cout << "FOUND A TRANSPLANT!!! moving [" << wid_cur << "] from depth "
                << (uint64_t)min_depths_get(poly, wid_cur) << " to depth " << poly.cur_depth << std::endl;
#endif  // DEBUG
      // XXX arguably, should also fear transplants that occured with
      // a different ft_offset ; e.g., need to look out for cross-reduction
      // collisions.  Have not played with this issue yet...
      parent_toggle(poly, wid_cur);
    }
    min_depths_set(poly, wid_cur, poly.cur_depth);
  }

  if (!cycle_get(poly, wid_cur) &&
      ((poly.cur_depth > default_depth ? default_depth : poly.cur_depth) == min_depths_get(poly, wid_cur)))
  {
    cycle_toggle(poly, wid_cur);

#ifdef DEBUG
    ++poly.depths[poly.cur_depth];
#endif  // DEBUG

    feature temp = {v * poly.synth_rec_f.x, wid_cur};
    poly.synth_ec.feature_space[tree_atomics].push_back(temp.x, temp.weight_index);
    poly.synth_ec.num_features++;

    if (parent_get(poly, temp.weight_index))
    {
      feature parent_f = poly.synth_rec_f;
      poly.synth_rec_f = temp;
      ++poly.cur_depth;
#ifdef DEBUG
      poly.max_depth = (poly.max_depth > poly.cur_depth) ? poly.max_depth : poly.cur_depth;
#endif  // DEBUG
      GD::foreach_feature<stagewise_poly, uint64_t, synthetic_create_rec>(*(poly.all), *(poly.original_ec), poly);
      --poly.cur_depth;
      poly.synth_rec_f = parent_f;
    }
  }
}

synthetic_decycle()

void synthetic_decycle

(

stagewise_poly &

poly

)

Definition at line 405 of file stagewise_poly.cc.

References cycle_get(), cycle_toggle(), example_predict::feature_space, features::indicies, features::size(), stagewise_poly::synth_ec, and tree_atomics.

Referenced by synthetic_create().

{
  features &fs = poly.synth_ec.feature_space[tree_atomics];
  for (size_t i = 0; i < fs.size(); ++i)
  {
    assert(cycle_get(poly, fs.indicies[i]));
    cycle_toggle(poly, fs.indicies[i]);
  }
}

synthetic_reset()

void synthetic_reset	(	stagewise_poly &	poly,
		example &	ec
	)

Some comments on ft_offset.

The plan is to do the feature mapping dfs with weight indices ignoring the ft_offset. This is because ft_offset is then added at the end, guaranteeing local/strided access on synth_ec. This might not matter too much in this implementation (where, e.g., –oaa runs one after the other, not interleaved), but who knows.

(The other choice is to basically ignore adjusting for ft_offset when doing the traversal, which means synth_ec.ft_offset is 0 here...)

Anyway, so here is how ft_offset matters:

• synthetic_create_rec must "normalize it out" of the fed weight value
• parent and min_depths set/get are adjusted for it.
• cycle set/get are not adjusted for it, since it doesn't matter for them.
• operations on the whole weight vector (sorting, save_load, all_reduce) ignore ft_offset, just treat the thing as a flat vector.

Definition at line 363 of file stagewise_poly.cc.

References stagewise_poly::all, example::end_pass, example::example_counter, example_predict::feature_space, example_predict::ft_offset, example::in_use, example_predict::indices, example_predict::interactions, vw::interactions, example::l, example::num_features, v_array< T >::push_back(), v_array< T >::size(), example::sorted, stagewise_poly::synth_ec, example::tag, example::test_only, example::total_sum_feat_sq, tree_atomics, and example::weight.

Referenced by synthetic_create().

{
  poly.synth_ec.l = ec.l;
  poly.synth_ec.weight = ec.weight;
  poly.synth_ec.tag = ec.tag;
  poly.synth_ec.example_counter = ec.example_counter;
  poly.synth_ec.interactions = &poly.all->interactions;

  poly.synth_ec.ft_offset = ec.ft_offset;

  poly.synth_ec.test_only = ec.test_only;
  poly.synth_ec.end_pass = ec.end_pass;
  poly.synth_ec.sorted = ec.sorted;
  poly.synth_ec.in_use = ec.in_use;

  poly.synth_ec.feature_space[tree_atomics].clear();
  poly.synth_ec.num_features = 0;
  poly.synth_ec.total_sum_feat_sq = 0;

  if (poly.synth_ec.indices.size() == 0)
    poly.synth_ec.indices.push_back(tree_atomics);
}

un_ft_offset()

uint64_t un_ft_offset ( const stagewise_poly &  poly, uint64_t  idx  )

inline

Definition at line 98 of file stagewise_poly.cc.

References stagewise_poly::all, example_predict::ft_offset, vw::length(), stagewise_poly::original_ec, parameters::stride_shift(), stagewise_poly::synth_ec, and vw::weights.

Referenced by synthetic_create_rec().

{
  assert(!poly.original_ec || poly.synth_ec.ft_offset == poly.original_ec->ft_offset);
  if (poly.synth_ec.ft_offset == 0)
    return idx;
  else
  {
    while (idx < poly.synth_ec.ft_offset)
    {
      idx += poly.all->length() << poly.all->weights.stride_shift();
    }
    return idx - poly.synth_ec.ft_offset;
  }
}

wid_mask()

uint64_t wid_mask ( const stagewise_poly &  poly, uint64_t  wid  )

inline

Definition at line 113 of file stagewise_poly.cc.

References stagewise_poly::all, parameters::mask(), and vw::weights.

Referenced by child_wid(), constant_feat_masked(), and synthetic_create_rec().

{ return wid & poly.all->weights.mask(); }

wid_mask_un_shifted()

uint64_t wid_mask_un_shifted ( const stagewise_poly &  poly, uint64_t  wid  )

inline

Definition at line 115 of file stagewise_poly.cc.

References stagewise_poly::all, parameters::mask(), stride_un_shift(), and vw::weights.

Referenced by cycle_get(), cycle_toggle(), parent_get(), parent_toggle(), and sanity_check_state().

{
  return stride_un_shift(poly, wid & poly.all->weights.mask());
}

Variable Documentation

cycle_bit

constexpr uint32_t cycle_bit = 2

static

Definition at line 16 of file stagewise_poly.cc.

Referenced by cycle_get(), cycle_toggle(), and sanity_check_state().

default_depth

constexpr uint32_t default_depth = 127

static

Definition at line 20 of file stagewise_poly.cc.

Referenced by depthsbits_create(), reduce_min(), reduce_min_max(), sanity_check_state(), and synthetic_create_rec().

indicator_bit

constexpr uint32_t indicator_bit = 128

static

Definition at line 19 of file stagewise_poly.cc.

Referenced by depthsbits_create(), reduce_min_max(), and sanity_check_state().

parent_bit

constexpr uint32_t parent_bit = 1

static

Definition at line 15 of file stagewise_poly.cc.

Referenced by parent_get(), parent_toggle(), and sanity_check_state().

tolerance

constexpr float tolerance = 1e-9f

static

Definition at line 18 of file stagewise_poly.cc.

Referenced by sort_data_update_support().

tree_atomics

constexpr uint32_t tree_atomics = 134

static

Definition at line 17 of file stagewise_poly.cc.

Referenced by synthetic_create(), synthetic_create_rec(), synthetic_decycle(), synthetic_reset(), and stagewise_poly::~stagewise_poly().