MARGINAL Namespace Reference

Classes
struct	data
struct	expert

Typedefs
typedef std::pair< double, double >	marginal
typedef std::pair< expert, expert >	expert_pair

Functions
float	get_adanormalhedge_weights (float R, float C)
template<bool is_learn>
void	make_marginal (data &sm, example &ec)
void	undo_marginal (data &sm, example &ec)
template<bool is_learn>
void	compute_expert_loss (data &sm, example &ec)
void	update_marginal (data &sm, example &ec)
template<bool is_learn>
void	predict_or_learn (data &sm, LEARNER::single_learner &base, example &ec)
void	save_load (data &sm, io_buf &io, bool read, bool text)

Typedef Documentation

expert_pair

typedef std::pair<expert, expert> MARGINAL::expert_pair

Definition at line 17 of file marginal.cc.

marginal

typedef std::pair<double, double> MARGINAL::marginal

Definition at line 16 of file marginal.cc.

Function Documentation

compute_expert_loss()

template<bool is_learn>

void MARGINAL::compute_expert_loss	(	data &	sm,
		example &	ec
	)

Definition at line 132 of file marginal.cc.

References MARGINAL::data::alg_loss, MARGINAL::data::all, MARGINAL::data::average_pred, MARGINAL::data::feature_pred, loss_function::getLoss(), example::l, label_data::label, vw::loss, MARGINAL::data::net_feature_weight, MARGINAL::data::net_weight, example::partial_prediction, example::pred, polyprediction::scalar, vw::sd, and polylabel::simple.

{
  vw& all = *sm.all;
  // add in the feature-based expert and normalize,
  float label = ec.l.simple.label;

  if (sm.net_weight + sm.net_feature_weight > 0.)
    sm.average_pred += sm.net_feature_weight * sm.feature_pred;
  else
  {
    sm.net_feature_weight = 1.;
    sm.average_pred = sm.feature_pred;
  }
  float inv_weight = 1.0f / (sm.net_weight + sm.net_feature_weight);
  sm.average_pred *= inv_weight;
  ec.pred.scalar = sm.average_pred;
  ec.partial_prediction = sm.average_pred;

  if (is_learn)
  {
    sm.alg_loss += sm.net_feature_weight * all.loss->getLoss(all.sd, sm.feature_pred, label);
    sm.alg_loss *= inv_weight;
  }
}

get_adanormalhedge_weights()

float MARGINAL::get_adanormalhedge_weights	(	float	R,
		float	C
	)

Definition at line 48 of file marginal.cc.

References correctedExp.

Referenced by update_marginal().

{
  float Rpos = R > 0 ? R : 0.f;
  if (C == 0. || Rpos == 0.)
    return 0;
  return 2 * Rpos * correctedExp(Rpos * Rpos / (3 * C)) / (3 * C);
}

make_marginal()

template<bool is_learn>

void MARGINAL::make_marginal	(	data &	sm,
		example &	ec
	)

Definition at line 57 of file marginal.cc.

References MARGINAL::data::alg_loss, MARGINAL::data::all, MARGINAL::data::average_pred, example_predict::begin(), features::begin(), features::clear(), MARGINAL::data::compete, v_array< T >::empty(), example_predict::end(), features::end(), MARGINAL::data::expert_state, f, example_predict::ft_offset, loss_function::getLoss(), MARGINAL::data::id_features, MARGINAL::data::initial_denominator, MARGINAL::data::initial_numerator, example::l, label_data::label, vw::loss, MARGINAL::data::marginals, parameters::mask(), MARGINAL::data::net_feature_weight, MARGINAL::data::net_weight, v_array< T >::push_back(), features::push_back(), vw::sd, polylabel::simple, features::size(), features::space_names, MARGINAL::data::temp, and vw::weights.

{
  uint64_t mask = sm.all->weights.mask();
  float label = ec.l.simple.label;
  vw& all = *sm.all;
  sm.alg_loss = 0.;
  sm.net_weight = 0.;
  sm.net_feature_weight = 0.;
  sm.average_pred = 0.;

  for (example::iterator i = ec.begin(); i != ec.end(); ++i)
  {
    namespace_index n = i.index();
    if (sm.id_features[n])
    {
      std::swap(sm.temp[n], *i);
      features& f = *i;
      f.clear();
      for (features::iterator j = sm.temp[n].begin(); j != sm.temp[n].end(); ++j)
      {
        float first_value = j.value();
        uint64_t first_index = j.index() & mask;
        if (++j == sm.temp[n].end())
        {
          std::cout << "warning: id feature namespace has " << sm.temp[n].size()
                    << " features. Should be a multiple of 2" << std::endl;
          break;
        }
        float second_value = j.value();
        uint64_t second_index = j.index() & mask;
        if (first_value != 1. || second_value != 1.)
        {
          std::cout << "warning: bad id features, must have value 1." << std::endl;
          continue;
        }
        uint64_t key = second_index + ec.ft_offset;
        if (sm.marginals.find(key) == sm.marginals.end())  // need to initialize things.
        {
          sm.marginals.insert(std::make_pair(key, std::make_pair(sm.initial_numerator, sm.initial_denominator)));
          if (sm.compete)
          {
            expert e = {0, 0, 1.};
            sm.expert_state.insert(std::make_pair(key, std::make_pair(e, e)));
          }
        }
        float marginal_pred = (float)(sm.marginals[key].first / sm.marginals[key].second);
        f.push_back(marginal_pred, first_index);
        if (!sm.temp[n].space_names.empty())
          f.space_names.push_back(sm.temp[n].space_names[2 * (f.size() - 1)]);

        if (sm.compete)  // compute the prediction from the marginals using the weights
        {
          float weight = sm.expert_state[key].first.weight;
          sm.average_pred += weight * marginal_pred;
          sm.net_weight += weight;
          sm.net_feature_weight += sm.expert_state[key].second.weight;
          if (is_learn)
            sm.alg_loss += weight * all.loss->getLoss(all.sd, marginal_pred, label);
        }
      }
    }
  }
}

predict_or_learn()

template<bool is_learn>

void MARGINAL::predict_or_learn	(	data &	sm,
		LEARNER::single_learner &	base,
		example &	ec
	)

Definition at line 200 of file marginal.cc.

References LEARNER::learner< T, E >::learn(), example::pred, LEARNER::learner< T, E >::predict(), polyprediction::scalar, undo_marginal(), and update_marginal().

{
  make_marginal<is_learn>(sm, ec);
  if (is_learn)
    if (sm.update_before_learn)
    {
      base.predict(ec);
      float pred = ec.pred.scalar;
      if (sm.compete)
      {
        sm.feature_pred = pred;
        compute_expert_loss<is_learn>(sm, ec);
      }
      undo_marginal(sm, ec);
      update_marginal(sm, ec);  // update features before learning.
      make_marginal<is_learn>(sm, ec);
      base.learn(ec);
      ec.pred.scalar = pred;
    }
    else
    {
      base.learn(ec);
      if (sm.compete)
      {
        sm.feature_pred = ec.pred.scalar;
        compute_expert_loss<is_learn>(sm, ec);
      }
      update_marginal(sm, ec);
    }
  else
  {
    base.predict(ec);
    float pred = ec.pred.scalar;
    if (sm.compete)
    {
      sm.feature_pred = pred;
      compute_expert_loss<is_learn>(sm, ec);
    }
  }

  // undo marginalization
  undo_marginal(sm, ec);
}

save_load()

void MARGINAL::save_load	(	data &	sm,
		io_buf &	io,
		bool	read,
		bool	text
	)

Definition at line 244 of file marginal.cc.

References MARGINAL::data::all, bin_text_read_write_fixed(), bin_text_read_write_fixed_validated(), MARGINAL::data::compete, MARGINAL::data::expert_state, io_buf::files, MARGINAL::data::marginals, v_array< T >::size(), stride_shift(), parameters::stride_shift(), and vw::weights.

Referenced by marginal_setup().

{
  uint64_t stride_shift = sm.all->weights.stride_shift();

  if (io.files.size() == 0)
    return;
  std::stringstream msg;
  uint64_t total_size;
  if (!read)
  {
    total_size = (uint64_t)sm.marginals.size();
    msg << "marginals size = " << total_size << "\n";
  }
  bin_text_read_write_fixed_validated(io, (char*)&total_size, sizeof(total_size), "", read, msg, text);

  auto iter = sm.marginals.begin();
  for (size_t i = 0; i < total_size; ++i)
  {
    uint64_t index;
    if (!read)
    {
      index = iter->first >> stride_shift;
      msg << index << ":";
    }
    bin_text_read_write_fixed(io, (char*)&index, sizeof(index), "", read, msg, text);
    double numerator;
    if (!read)
    {
      numerator = iter->second.first;
      msg << numerator << ":";
    }
    bin_text_read_write_fixed(io, (char*)&numerator, sizeof(numerator), "", read, msg, text);
    double denominator;
    if (!read)
    {
      denominator = iter->second.second;
      msg << denominator << "\n";
    }
    bin_text_read_write_fixed(io, (char*)&denominator, sizeof(denominator), "", read, msg, text);
    if (read)
      sm.marginals.insert(std::make_pair(index << stride_shift, std::make_pair(numerator, denominator)));
    else
      ++iter;
  }

  if (sm.compete)
  {
    if (!read)
    {
      total_size = (uint64_t)sm.expert_state.size();
      msg << "expert_state size = " << total_size << "\n";
    }
    bin_text_read_write_fixed_validated(io, (char*)&total_size, sizeof(total_size), "", read, msg, text);

    auto exp_iter = sm.expert_state.begin();
    for (size_t i = 0; i < total_size; ++i)
    {
      uint64_t index;
      if (!read)
      {
        index = exp_iter->first >> stride_shift;
        msg << index << ":";
      }
      bin_text_read_write_fixed(io, (char*)&index, sizeof(index), "", read, msg, text);
      float r1, c1, w1, r2, c2, w2;
      if (!read)
      {
        r1 = exp_iter->second.first.regret;
        c1 = exp_iter->second.first.abs_regret;
        w1 = exp_iter->second.first.weight;
        r2 = exp_iter->second.second.regret;
        c2 = exp_iter->second.second.abs_regret;
        w2 = exp_iter->second.second.weight;
        msg << r1 << ":";
      }
      bin_text_read_write_fixed(io, (char*)&r1, sizeof(r1), "", read, msg, text);
      if (!read)
        msg << c1 << ":";
      bin_text_read_write_fixed(io, (char*)&c1, sizeof(c1), "", read, msg, text);
      if (!read)
        msg << w1 << ":";
      bin_text_read_write_fixed(io, (char*)&w1, sizeof(w1), "", read, msg, text);
      if (!read)
        msg << r2 << ":";
      bin_text_read_write_fixed(io, (char*)&r2, sizeof(r2), "", read, msg, text);
      if (!read)
        msg << c2 << ":";
      bin_text_read_write_fixed(io, (char*)&c2, sizeof(c2), "", read, msg, text);
      if (!read)
        msg << w2 << ":";
      bin_text_read_write_fixed(io, (char*)&w2, sizeof(w2), "", read, msg, text);

      if (read)
      {
        expert e1 = {r1, c1, w1};
        expert e2 = {r2, c2, w2};
        sm.expert_state.insert(std::make_pair(index << stride_shift, std::make_pair(e1, e2)));
      }
      else
        ++exp_iter;
    }
  }
}

undo_marginal()

void MARGINAL::undo_marginal	(	data &	sm,
		example &	ec
	)

Definition at line 121 of file marginal.cc.

References example_predict::begin(), example_predict::end(), MARGINAL::data::id_features, and MARGINAL::data::temp.

Referenced by predict_or_learn().

{
  for (example::iterator i = ec.begin(); i != ec.end(); ++i)
  {
    namespace_index n = i.index();
    if (sm.id_features[n])
      std::swap(sm.temp[n], *i);
  }
}

update_marginal()

void MARGINAL::update_marginal	(	data &	sm,
		example &	ec
	)

Definition at line 157 of file marginal.cc.

References MARGINAL::data::alg_loss, MARGINAL::data::all, example_predict::begin(), features::begin(), MARGINAL::data::compete, MARGINAL::data::decay, example_predict::end(), features::end(), MARGINAL::data::expert_state, MARGINAL::data::feature_pred, example_predict::ft_offset, get_adanormalhedge_weights(), loss_function::getLoss(), MARGINAL::data::id_features, example::l, label_data::label, vw::loss, MARGINAL::data::marginals, parameters::mask(), vw::sd, polylabel::simple, MARGINAL::data::temp, MARGINAL::data::unweighted_marginals, example::weight, and vw::weights.

Referenced by predict_or_learn().

{
  vw& all = *sm.all;
  uint64_t mask = sm.all->weights.mask();
  float label = ec.l.simple.label;
  float weight = ec.weight;
  if (sm.unweighted_marginals)
    weight = 1.;

  for (example::iterator i = ec.begin(); i != ec.end(); ++i)
  {
    namespace_index n = i.index();
    if (sm.id_features[n])
      for (features::iterator j = sm.temp[n].begin(); j != sm.temp[n].end(); ++j)
      {
        if (++j == sm.temp[n].end())
          break;

        uint64_t second_index = j.index() & mask;
        uint64_t key = second_index + ec.ft_offset;
        marginal& m = sm.marginals[key];

        if (sm.compete)  // now update weights, before updating marginals
        {
          expert_pair& e = sm.expert_state[key];
          float regret1 = sm.alg_loss - all.loss->getLoss(all.sd, (float)(m.first / m.second), label);
          float regret2 = sm.alg_loss - all.loss->getLoss(all.sd, sm.feature_pred, label);

          e.first.regret += regret1 * weight;
          e.first.abs_regret += regret1 * regret1 * weight;  // fabs(regret1);
          e.first.weight = get_adanormalhedge_weights(e.first.regret, e.first.abs_regret);
          e.second.regret += regret2 * weight;
          e.second.abs_regret += regret2 * regret2 * weight;  // fabs(regret2);
          e.second.weight = get_adanormalhedge_weights(e.second.regret, e.second.abs_regret);
        }

        m.first = m.first * (1. - sm.decay) + ec.l.simple.label * weight;
        m.second = m.second * (1. - sm.decay) + weight;
      }
  }
}