ect.cc File Reference

#include <iostream>
#include <fstream>
#include <ctime>
#include <numeric>
#include "reductions.h"

Go to the source code of this file.

Classes
struct	direction
struct	ect

Functions
bool	exists (v_array< size_t > db)
size_t	final_depth (size_t eliminations)
bool	not_empty (v_array< v_array< uint32_t >> const &tournaments)
void	print_level (v_array< v_array< uint32_t >> const &level)
size_t	create_circuit (ect &e, uint64_t max_label, uint64_t eliminations)
uint32_t	ect_predict (ect &e, single_learner &base, example &ec)
void	ect_train (ect &e, single_learner &base, example &ec)
void	predict (ect &e, single_learner &base, example &ec)
void	learn (ect &e, single_learner &base, example &ec)
base_learner *	ect_setup (options_i &options, vw &all)

Function Documentation

create_circuit()

size_t create_circuit	(	ect &	e,
		uint64_t	max_label,
		uint64_t	eliminations
	)

Definition at line 104 of file ect.cc.

References ect::all_levels, ect::directions, final_depth(), ect::final_nodes, id(), v_array< T >::last(), ect::last_pair, not_empty(), v_array< T >::push_back(), v_array< T >::size(), and ect::tree_height.

Referenced by ect_setup().

{
  if (max_label == 1)
    return 0;

  v_array<v_array<uint32_t>> tournaments = v_init<v_array<uint32_t>>();
  v_array<uint32_t> t = v_init<uint32_t>();

  for (uint32_t i = 0; i < max_label; i++)
  {
    t.push_back(i);
    direction d = {i, 0, 0, 0, 0, 0, false};
    e.directions.push_back(d);
  }

  tournaments.push_back(t);

  for (size_t i = 0; i < eliminations - 1; i++) tournaments.push_back(v_array<uint32_t>());

  e.all_levels.push_back(tournaments);

  size_t level = 0;

  uint32_t node = (uint32_t)e.directions.size();

  while (not_empty(e.all_levels[level]))
  {
    v_array<v_array<uint32_t>> new_tournaments = v_init<v_array<uint32_t>>();
    tournaments = e.all_levels[level];

    for (size_t t = 0; t < tournaments.size(); t++)
    {
      v_array<uint32_t> empty = v_init<uint32_t>();
      new_tournaments.push_back(empty);
    }

    for (size_t t = 0; t < tournaments.size(); t++)
    {
      for (size_t j = 0; j < tournaments[t].size() / 2; j++)
      {
        uint32_t id = node++;
        uint32_t left = tournaments[t][2 * j];
        uint32_t right = tournaments[t][2 * j + 1];

        direction d = {id, t, 0, 0, left, right, false};
        e.directions.push_back(d);
        uint32_t direction_index = (uint32_t)e.directions.size() - 1;
        if (e.directions[left].tournament == t)
          e.directions[left].winner = direction_index;
        else
          e.directions[left].loser = direction_index;
        if (e.directions[right].tournament == t)
          e.directions[right].winner = direction_index;
        else
          e.directions[right].loser = direction_index;
        if (e.directions[left].last)
          e.directions[left].winner = direction_index;

        if (tournaments[t].size() == 2 && (t == 0 || tournaments[t - 1].empty()))
        {
          e.directions[direction_index].last = true;
          if (t + 1 < tournaments.size())
            new_tournaments[t + 1].push_back(id);
          else  // winner eliminated.
            e.directions[direction_index].winner = 0;
          e.final_nodes.push_back((uint32_t)(e.directions.size() - 1));
        }
        else
          new_tournaments[t].push_back(id);
        if (t + 1 < tournaments.size())
          new_tournaments[t + 1].push_back(id);
        else  // loser eliminated.
          e.directions[direction_index].loser = 0;
      }
      if (tournaments[t].size() % 2 == 1)
        new_tournaments[t].push_back(tournaments[t].last());
    }
    e.all_levels.push_back(new_tournaments);
    level++;
  }

  e.last_pair = (uint32_t)((max_label - 1) * eliminations);

  if (max_label > 1)
    e.tree_height = final_depth(eliminations);

  return e.last_pair + (eliminations - 1);
}

ect_predict()

uint32_t ect_predict	(	ect &	e,
		single_learner &	base,
		example &	ec
	)

Definition at line 193 of file ect.cc.

References ect::class_boundary, ect::directions, ect::errors, ect::final_nodes, id(), ect::k, example::l, ect::last_pair, LEARNER::learner< T, E >::learn(), example::pred, polyprediction::scalar, polylabel::simple, and ect::tree_height.

Referenced by predict().

{
  if (e.k == (size_t)1)
    return 1;

  uint32_t finals_winner = 0;

  // Binary final elimination tournament first
  ec.l.simple = {FLT_MAX, 0., 0.};

  for (size_t i = e.tree_height - 1; i != (size_t)0 - 1; i--)
  {
    if ((finals_winner | (((size_t)1) << i)) <= e.errors)
    {
      // a real choice exists
      uint32_t problem_number = e.last_pair + (finals_winner | (((uint32_t)1) << i)) - 1;  // This is unique.

      base.learn(ec, problem_number);

      if (ec.pred.scalar > e.class_boundary)
        finals_winner = finals_winner | (((size_t)1) << i);
    }
  }

  uint32_t id = e.final_nodes[finals_winner];
  while (id >= e.k)
  {
    base.learn(ec, id - e.k);

    if (ec.pred.scalar > e.class_boundary)
      id = e.directions[id].right;
    else
      id = e.directions[id].left;
  }
  return id + 1;
}

ect_setup()

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

Definition at line 340 of file ect.cc.

References VW::config::option_group_definition::add(), add(), VW::config::options_i::add_and_parse(), LEARNER::as_singleline(), create_circuit(), LEARNER::init_multiclass_learner(), learn(), LEARNER::make_base(), VW::config::make_option(), vw::p, predict(), setup_base(), and VW::config::options_i::was_supplied().

Referenced by parse_reductions().

{
  auto data = scoped_calloc_or_throw<ect>();
  std::string link;
  option_group_definition new_options("Error Correcting Tournament Options");
  new_options.add(make_option("ect", data->k).keep().help("Error correcting tournament with <k> labels"))
      .add(make_option("error", data->errors).keep().default_value(0).help("errors allowed by ECT"))
      // Used to check value. TODO replace
      .add(make_option("link", link)
               .default_value("identity")
               .keep()
               .help("Specify the link function: identity, logistic, glf1 or poisson"));
  options.add_and_parse(new_options);

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

  size_t wpp = create_circuit(*data.get(), data->k, data->errors + 1);

  base_learner* base = setup_base(options, all);
  if (link == "logistic")
    data->class_boundary = 0.5;  // as --link=logistic maps predictions in [0;1]

  learner<ect, example>& l = init_multiclass_learner(data, as_singleline(base), learn, predict, all.p, wpp);

  return make_base(l);
}

ect_train()

void ect_train	(	ect &	e,
		single_learner &	base,
		example &	ec
	)

Definition at line 230 of file ect.cc.

References v_array< T >::begin(), ect::class_boundary, v_array< T >::clear(), ect::directions, v_array< T >::empty(), v_array< T >::end(), id(), label_data::initial, ect::k, example::l, label_data::label, MULTICLASS::label_t::label, v_array< T >::last(), ect::last_pair, LEARNER::learner< T, E >::learn(), label_type::mc, polylabel::multi, example::pred, v_array< T >::push_back(), polyprediction::scalar, polylabel::simple, v_array< T >::size(), ect::tournaments_won, ect::tree_height, label_data::weight, and example::weight.

Referenced by learn().

{
  if (e.k == 1)  // nothing to do
    return;
  MULTICLASS::label_t mc = ec.l.multi;

  label_data simple_temp;

  simple_temp.initial = 0.;

  e.tournaments_won.clear();

  uint32_t id = e.directions[mc.label - 1].winner;
  bool left = e.directions[id].left == mc.label - 1;
  do
  {
    if (left)
      simple_temp.label = -1;
    else
      simple_temp.label = 1;

    ec.l.simple = simple_temp;
    base.learn(ec, id - e.k);
    float old_weight = ec.weight;
    ec.weight = 0.;
    base.learn(ec, id - e.k);  // inefficient, we should extract final prediction exactly.
    ec.weight = old_weight;

    bool won = (ec.pred.scalar - e.class_boundary) * simple_temp.label > 0;

    if (won)
    {
      if (!e.directions[id].last)
        left = e.directions[e.directions[id].winner].left == id;
      else
        e.tournaments_won.push_back(true);
      id = e.directions[id].winner;
    }
    else
    {
      if (!e.directions[id].last)
      {
        left = e.directions[e.directions[id].loser].left == id;
        if (e.directions[id].loser == 0)
          e.tournaments_won.push_back(false);
      }
      else
        e.tournaments_won.push_back(false);
      id = e.directions[id].loser;
    }
  } while (id != 0);

  if (e.tournaments_won.empty())
    std::cout << "badness!" << std::endl;

  // tournaments_won is a bit vector determining which tournaments the label won.
  for (size_t i = 0; i < e.tree_height; i++)
  {
    for (uint32_t j = 0; j < e.tournaments_won.size() / 2; j++)
    {
      bool left = e.tournaments_won[j * 2];
      bool right = e.tournaments_won[j * 2 + 1];
      if (left == right)  // no query to do
        e.tournaments_won[j] = left;
      else  // query to do
      {
        if (left)
          simple_temp.label = -1;
        else
          simple_temp.label = 1;
        simple_temp.weight = (float)(1 << (e.tree_height - i - 1));
        ec.l.simple = simple_temp;

        uint32_t problem_number = e.last_pair + j * (1 << (i + 1)) + (1 << i) - 1;

        base.learn(ec, problem_number);

        if (ec.pred.scalar > e.class_boundary)
          e.tournaments_won[j] = right;
        else
          e.tournaments_won[j] = left;
      }
      if (e.tournaments_won.size() % 2 == 1)
        e.tournaments_won[e.tournaments_won.size() / 2] = e.tournaments_won[e.tournaments_won.size() - 1];
      e.tournaments_won.end() = e.tournaments_won.begin() + (1 + e.tournaments_won.size()) / 2;
    }
  }
}

exists()

bool exists

(

v_array< size_t >

db

)

Definition at line 69 of file ect.cc.

{
  for (unsigned long i : db)
    if (i != 0)
      return true;
  return false;
}

final_depth()

size_t final_depth

(

size_t

eliminations

)

Definition at line 77 of file ect.cc.

Referenced by create_circuit().

{
  eliminations--;
  for (size_t i = 0; i < 32; i++)
    if (eliminations >> i == 0)
      return i;
  std::cerr << "too many eliminations" << std::endl;
  return 31;
}

learn()

void learn	(	ect &	e,
		single_learner &	base,
		example &	ec
	)

Definition at line 328 of file ect.cc.

References ect_train(), example::l, MULTICLASS::label_t::label, label_type::mc, polylabel::multi, polyprediction::multiclass, example::pred, and predict().

Referenced by ect_setup().

{
  MULTICLASS::label_t mc = ec.l.multi;
  predict(e, base, ec);
  uint32_t pred = ec.pred.multiclass;

  if (mc.label != (uint32_t)-1)
    ect_train(e, base, ec);
  ec.l.multi = mc;
  ec.pred.multiclass = pred;
}

not_empty()

bool not_empty

(

v_array< v_array< uint32_t >> const &

tournaments

)

Definition at line 87 of file ect.cc.

Referenced by create_circuit().

{
  auto const first_non_empty_tournament = std::find_if(
      tournaments.cbegin(), tournaments.cend(), [](v_array<uint32_t>& tournament) { return !tournament.empty(); });
  return first_non_empty_tournament != tournaments.cend();
}

predict()

void predict	(	ect &	e,
		single_learner &	base,
		example &	ec
	)

Definition at line 319 of file ect.cc.

References ect_predict(), ect::k, example::l, MULTICLASS::label_t::label, label_type::mc, polylabel::multi, polyprediction::multiclass, and example::pred.

Referenced by ect_setup(), and learn().

{
  MULTICLASS::label_t mc = ec.l.multi;
  if (mc.label == 0 || (mc.label > e.k && mc.label != (uint32_t)-1))
    std::cout << "label " << mc.label << " is not in {1," << e.k << "} This won't work right." << std::endl;
  ec.pred.multiclass = ect_predict(e, base, ec);
  ec.l.multi = mc;
}

print_level()

void print_level

(

v_array< v_array< uint32_t >> const &

level

)

Definition at line 94 of file ect.cc.

{
  for (auto const& t : level)
  {
    for (auto i : t) std::cout << " " << i;
    std::cout << " | ";
  }
  std::cout << std::endl;
}