recall_tree_ns Namespace Reference

Classes
struct	node
struct	node_pred
struct	predict_type
struct	recall_tree

Functions
float	to_prob (float x)
void	init_tree (recall_tree &b, uint32_t root, uint32_t depth, uint32_t &routers_used)
void	init_tree (recall_tree &b)
node_pred *	find (recall_tree &b, uint32_t cn, example &ec)
node_pred *	find_or_create (recall_tree &b, uint32_t cn, example &ec)
void	compute_recall_lbest (recall_tree &b, node *n)
double	plogp (double c, double n)
double	updated_entropy (recall_tree &b, uint32_t cn, example &ec)
void	insert_example_at_node (recall_tree &b, uint32_t cn, example &ec)
void	add_node_id_feature (recall_tree &b, uint32_t cn, example &ec)
void	remove_node_id_feature (recall_tree &, uint32_t, example &ec)
uint32_t	oas_predict (recall_tree &b, single_learner &base, uint32_t cn, example &ec)
bool	is_candidate (recall_tree &b, uint32_t cn, example &ec)
uint32_t	descend (node &n, float prediction)
bool	stop_recurse_check (recall_tree &b, uint32_t parent, uint32_t child)
predict_type	predict_from (recall_tree &b, single_learner &base, example &ec, uint32_t cn)
void	predict (recall_tree &b, single_learner &base, example &ec)
float	train_node (recall_tree &b, single_learner &base, example &ec, uint32_t cn)
void	learn (recall_tree &b, single_learner &base, example &ec)
void	save_load_tree (recall_tree &b, io_buf &model_file, bool read, bool text)

Function Documentation

add_node_id_feature()

void recall_tree_ns::add_node_id_feature	(	recall_tree &	b,
		uint32_t	cn,
		example &	ec
	)

Definition at line 221 of file recall_tree.cc.

References recall_tree_ns::recall_tree::all, example_predict::feature_space, example_predict::indices, parameters::mask(), node_id_namespace, recall_tree_ns::recall_tree::node_only, recall_tree_ns::recall_tree::nodes, v_array< T >::push_back(), features::push_back(), parameters::stride_shift(), and vw::weights.

Referenced by learn(), and oas_predict().

{
  vw* all = b.all;
  uint64_t mask = all->weights.mask();
  size_t ss = all->weights.stride_shift();

  ec.indices.push_back(node_id_namespace);
  features& fs = ec.feature_space[node_id_namespace];

  if (b.node_only)
  {
    fs.push_back(1., (((uint64_t)868771 * cn) << ss) & mask);
  }
  else
  {
    while (cn > 0)
    {
      fs.push_back(1., (((uint64_t)868771 * cn) << ss) & mask);
      cn = b.nodes[cn].parent;
    }
  }

  // TODO: audit ?
  // TODO: if namespace already exists ?
}

compute_recall_lbest()

void recall_tree_ns::compute_recall_lbest	(	recall_tree &	b,
		node *	n
	)

Definition at line 150 of file recall_tree.cc.

References v_array< T >::begin(), recall_tree_ns::recall_tree::bern_hyper, v_array< T >::end(), f, recall_tree_ns::recall_tree::max_candidates, recall_tree_ns::node::n, recall_tree_ns::node::preds, and recall_tree_ns::node::recall_lbest.

Referenced by insert_example_at_node(), and save_load_tree().

{
  if (n->n <= 0)
    return;

  double mass_at_k = 0;

  for (node_pred* ls = n->preds.begin(); ls != n->preds.end() && ls < n->preds.begin() + b.max_candidates; ++ls)
  {
    mass_at_k += ls->label_count;
  }

  float f = (float)mass_at_k / (float)n->n;
  float stdf = std::sqrt(f * (1.f - f) / (float)n->n);
  float diamf = 15.f / (std::sqrt(18.f) * (float)n->n);

  n->recall_lbest = std::max(0.f, f - std::sqrt(b.bern_hyper) * stdf - b.bern_hyper * diamf);
}

descend()

uint32_t recall_tree_ns::descend ( node &  n, float  prediction  )

inline

Definition at line 296 of file recall_tree.cc.

References recall_tree_ns::node::left, and recall_tree_ns::node::right.

{ return prediction < 0 ? n.left : n.right; }

find()

node_pred* recall_tree_ns::find	(	recall_tree &	b,
		uint32_t	cn,
		example &	ec
	)

Definition at line 126 of file recall_tree.cc.

References v_array< T >::begin(), v_array< T >::end(), example::l, MULTICLASS::label_t::label, recall_tree_ns::node_pred::label, polylabel::multi, and recall_tree_ns::recall_tree::nodes.

Referenced by find_or_create(), VW::move_feature_namespace(), vw_slim::namespace_copy_guard::namespace_copy_guard(), CCB::parse_label(), Context< audit >::PopNamespace(), VW::config::options_boost_po::replace(), reset_source(), updated_entropy(), and VW::config::options_boost_po::was_supplied().

{
  node_pred* ls;

  for (ls = b.nodes[cn].preds.begin(); ls != b.nodes[cn].preds.end() && ls->label != ec.l.multi.label; ++ls)
    ;

  return ls;
}

find_or_create()

node_pred* recall_tree_ns::find_or_create	(	recall_tree &	b,
		uint32_t	cn,
		example &	ec
	)

Definition at line 136 of file recall_tree.cc.

References v_array< T >::end(), find(), example::l, MULTICLASS::label_t::label, polylabel::multi, recall_tree_ns::recall_tree::nodes, and v_array< T >::push_back().

Referenced by insert_example_at_node().

{
  node_pred* ls = find(b, cn, ec);

  if (ls == b.nodes[cn].preds.end())
  {
    node_pred newls(ec.l.multi.label);
    b.nodes[cn].preds.push_back(newls);
    ls = b.nodes[cn].preds.end() - 1;
  }

  return ls;
}

init_tree() [1/2]

void recall_tree_ns::init_tree	(	recall_tree &	b,
		uint32_t	root,
		uint32_t	depth,
		uint32_t &	routers_used
	)

Definition at line 92 of file recall_tree.cc.

References init_tree(), recall_tree_ns::recall_tree::max_depth, recall_tree_ns::recall_tree::nodes, v_array< T >::push_back(), and v_array< T >::size().

{
  if (depth <= b.max_depth)
  {
    uint32_t left_child;
    uint32_t right_child;
    left_child = (uint32_t)b.nodes.size();
    b.nodes.push_back(node());
    right_child = (uint32_t)b.nodes.size();
    b.nodes.push_back(node());
    b.nodes[root].base_router = routers_used++;

    b.nodes[root].internal = true;
    b.nodes[root].left = left_child;
    b.nodes[left_child].parent = root;
    b.nodes[left_child].depth = depth;
    b.nodes[root].right = right_child;
    b.nodes[right_child].parent = root;
    b.nodes[right_child].depth = depth;

    init_tree(b, left_child, depth + 1, routers_used);
    init_tree(b, right_child, depth + 1, routers_used);
  }
}

init_tree() [2/2]

void recall_tree_ns::init_tree

(

recall_tree &

b

)

Definition at line 117 of file recall_tree.cc.

References init_tree(), recall_tree_ns::recall_tree::max_routers, recall_tree_ns::recall_tree::nodes, and v_array< T >::push_back().

{
  uint32_t routers_used = 0;

  b.nodes.push_back(node());
  init_tree(b, 0, 1, routers_used);
  b.max_routers = routers_used;
}

insert_example_at_node()

void recall_tree_ns::insert_example_at_node	(	recall_tree &	b,
		uint32_t	cn,
		example &	ec
	)

Definition at line 200 of file recall_tree.cc.

References v_array< T >::begin(), compute_recall_lbest(), find_or_create(), recall_tree_ns::node_pred::label_count, recall_tree_ns::recall_tree::nodes, updated_entropy(), and example::weight.

Referenced by learn().

{
  node_pred* ls = find_or_create(b, cn, ec);

  b.nodes[cn].entropy = updated_entropy(b, cn, ec);

  ls->label_count += ec.weight;

  while (ls != b.nodes[cn].preds.begin() && ls[-1].label_count < ls[0].label_count)
  {
    std::swap(ls[-1], ls[0]);
    --ls;
  }

  b.nodes[cn].n += ec.weight;

  compute_recall_lbest(b, &b.nodes[cn]);
}

is_candidate()

bool recall_tree_ns::is_candidate	(	recall_tree &	b,
		uint32_t	cn,
		example &	ec
	)

Definition at line 284 of file recall_tree.cc.

References v_array< T >::begin(), v_array< T >::end(), example::l, MULTICLASS::label_t::label, recall_tree_ns::recall_tree::max_candidates, polylabel::multi, and recall_tree_ns::recall_tree::nodes.

Referenced by learn().

{
  for (node_pred* ls = b.nodes[cn].preds.begin();
       ls != b.nodes[cn].preds.end() && ls < b.nodes[cn].preds.begin() + b.max_candidates; ++ls)
  {
    if (ls->label == ec.l.multi.label)
      return true;
  }

  return false;
}

learn()

void recall_tree_ns::learn	(	recall_tree &	b,
		single_learner &	base,
		example &	ec
	)

Definition at line 376 of file recall_tree.cc.

References recall_tree_ns::recall_tree::_random_state, add_node_id_feature(), recall_tree_ns::recall_tree::all, v_array< T >::begin(), descend(), v_array< T >::end(), insert_example_at_node(), is_candidate(), example::l, MULTICLASS::label_t::label, LEARNER::learner< T, E >::learn(), recall_tree_ns::recall_tree::max_candidates, recall_tree_ns::recall_tree::max_routers, label_type::mc, polylabel::multi, polyprediction::multiclass, recall_tree_ns::recall_tree::nodes, example::pred, predict(), recall_tree_ns::recall_tree::randomized_routing, remove_node_id_feature(), polylabel::simple, stop_recurse_check(), to_prob(), train_node(), and vw::training.

Referenced by recall_tree_setup().

{
  predict(b, base, ec);

  if (b.all->training && ec.l.multi.label != (uint32_t)-1)  // if training the tree
  {
    uint32_t cn = 0;

    while (b.nodes[cn].internal)
    {
      float which = train_node(b, base, ec, cn);

      if (b.randomized_routing)
        which = (b._random_state->get_and_update_random() > to_prob(which) ? -1.f : 1.f);

      uint32_t newcn = descend(b.nodes[cn], which);
      bool cond = stop_recurse_check(b, cn, newcn);
      insert_example_at_node(b, cn, ec);

      if (cond)
      {
        insert_example_at_node(b, newcn, ec);
        break;
      }

      cn = newcn;
    }

    if (!b.nodes[cn].internal)
      insert_example_at_node(b, cn, ec);

    if (is_candidate(b, cn, ec))
    {
      MULTICLASS::label_t mc = ec.l.multi;
      uint32_t save_pred = ec.pred.multiclass;

      add_node_id_feature(b, cn, ec);

      ec.l.simple = {1.f, 1.f, 0.f};
      base.learn(ec, b.max_routers + mc.label - 1);
      ec.l.simple = {-1.f, 1.f, 0.f};

      for (node_pred* ls = b.nodes[cn].preds.begin();
           ls != b.nodes[cn].preds.end() && ls < b.nodes[cn].preds.begin() + b.max_candidates; ++ls)
      {
        if (ls->label != mc.label)
          base.learn(ec, b.max_routers + ls->label - 1);
      }

      remove_node_id_feature(b, cn, ec);

      ec.l.multi = mc;
      ec.pred.multiclass = save_pred;
    }
  }
}

oas_predict()

uint32_t recall_tree_ns::oas_predict	(	recall_tree &	b,
		single_learner &	base,
		uint32_t	cn,
		example &	ec
	)

Definition at line 254 of file recall_tree.cc.

References add_node_id_feature(), v_array< T >::begin(), v_array< T >::end(), example::l, recall_tree_ns::recall_tree::max_candidates, recall_tree_ns::recall_tree::max_routers, label_type::mc, polylabel::multi, polyprediction::multiclass, recall_tree_ns::recall_tree::nodes, example::partial_prediction, example::pred, LEARNER::learner< T, E >::predict(), remove_node_id_feature(), and polylabel::simple.

Referenced by predict_from().

{
  MULTICLASS::label_t mc = ec.l.multi;
  uint32_t save_pred = ec.pred.multiclass;

  uint32_t amaxscore = 0;

  add_node_id_feature(b, cn, ec);
  ec.l.simple = {FLT_MAX, 0.f, 0.f};

  float maxscore = std::numeric_limits<float>::lowest();
  for (node_pred* ls = b.nodes[cn].preds.begin();
       ls != b.nodes[cn].preds.end() && ls < b.nodes[cn].preds.begin() + b.max_candidates; ++ls)
  {
    base.predict(ec, b.max_routers + ls->label - 1);
    if (amaxscore == 0 || ec.partial_prediction > maxscore)
    {
      maxscore = ec.partial_prediction;
      amaxscore = ls->label;
    }
  }

  remove_node_id_feature(b, cn, ec);

  ec.l.multi = mc;
  ec.pred.multiclass = save_pred;

  return amaxscore;
}

plogp()

double recall_tree_ns::plogp	(	double	c,
		double	n
	)

Definition at line 169 of file recall_tree.cc.

Referenced by updated_entropy().

{ return (c == 0) ? 0 : (c / n) * log(c / n); }

predict()

void recall_tree_ns::predict	(	recall_tree &	b,
		single_learner &	base,
		example &	ec
	)

Definition at line 335 of file recall_tree.cc.

References recall_tree_ns::predict_type::class_prediction, polyprediction::multiclass, example::pred, and predict_from().

Referenced by learn(), and recall_tree_setup().

{
  predict_type pred = predict_from(b, base, ec, 0);

  ec.pred.multiclass = pred.class_prediction;
}

predict_from()

predict_type recall_tree_ns::predict_from	(	recall_tree &	b,
		single_learner &	base,
		example &	ec,
		uint32_t	cn
	)

Definition at line 311 of file recall_tree.cc.

References descend(), example::l, label_type::mc, polylabel::multi, polyprediction::multiclass, recall_tree_ns::recall_tree::nodes, oas_predict(), example::partial_prediction, example::pred, LEARNER::learner< T, E >::predict(), polylabel::simple, and stop_recurse_check().

Referenced by predict().

{
  MULTICLASS::label_t mc = ec.l.multi;
  uint32_t save_pred = ec.pred.multiclass;

  ec.l.simple = {FLT_MAX, 0.f, 0.f};
  while (b.nodes[cn].internal)
  {
    base.predict(ec, b.nodes[cn].base_router);
    uint32_t newcn = descend(b.nodes[cn], ec.partial_prediction);
    bool cond = stop_recurse_check(b, cn, newcn);

    if (cond)
      break;

    cn = newcn;
  }

  ec.l.multi = mc;
  ec.pred.multiclass = save_pred;

  return predict_type(cn, oas_predict(b, base, cn, ec));
}

remove_node_id_feature()

void recall_tree_ns::remove_node_id_feature	(	recall_tree &	,
		uint32_t	,
		example &	ec
	)

Definition at line 247 of file recall_tree.cc.

References features::clear(), example_predict::feature_space, example_predict::indices, node_id_namespace, and v_array< T >::pop().

Referenced by learn(), and oas_predict().

{
  features& fs = ec.feature_space[node_id_namespace];
  fs.clear();
  ec.indices.pop();
}

save_load_tree()

void recall_tree_ns::save_load_tree	(	recall_tree &	b,
		io_buf &	model_file,
		bool	read,
		bool	text
	)

Definition at line 433 of file recall_tree.cc.

References recall_tree_ns::node::base_router, v_array< T >::clear(), compute_recall_lbest(), recall_tree_ns::node::depth, recall_tree_ns::node::entropy, io_buf::files, recall_tree_ns::node::internal, recall_tree_ns::recall_tree::k, recall_tree_ns::node_pred::label, recall_tree_ns::node_pred::label_count, recall_tree_ns::node::left, recall_tree_ns::recall_tree::max_candidates, recall_tree_ns::recall_tree::max_depth, recall_tree_ns::node::n, recall_tree_ns::recall_tree::node_only, recall_tree_ns::recall_tree::nodes, recall_tree_ns::node::parent, recall_tree_ns::node::passes, recall_tree_ns::node::preds, v_array< T >::push_back(), recall_tree_ns::node::recall_lbest, recall_tree_ns::node::right, v_array< T >::size(), writeit, and writeitvar.

{
  if (model_file.files.size() > 0)
  {
    std::stringstream msg;

    writeit(b.k, "k");
    writeit(b.node_only, "node_only");
    writeitvar(b.nodes.size(), "nodes", n_nodes);

    if (read)
    {
      b.nodes.clear();
      for (uint32_t j = 0; j < n_nodes; ++j)
      {
        b.nodes.push_back(node());
      }
    }

    writeit(b.max_candidates, "max_candidates");
    writeit(b.max_depth, "max_depth");

    for (uint32_t j = 0; j < n_nodes; ++j)
    {
      node* cn = &b.nodes[j];

      writeit(cn->parent, "parent");
      writeit(cn->recall_lbest, "recall_lbest");
      writeit(cn->internal, "internal");
      writeit(cn->depth, "depth");
      writeit(cn->base_router, "base_router");
      writeit(cn->left, "left");
      writeit(cn->right, "right");
      writeit(cn->n, "n");
      writeit(cn->entropy, "entropy");
      writeit(cn->passes, "passes");

      writeitvar(cn->preds.size(), "n_preds", n_preds);

      if (read)
      {
        cn->preds.clear();

        for (uint32_t k = 0; k < n_preds; ++k)
        {
          cn->preds.push_back(node_pred(0));
        }
      }

      for (uint32_t k = 0; k < n_preds; ++k)
      {
        node_pred* pred = &cn->preds[k];

        writeit(pred->label, "label");
        writeit(pred->label_count, "label_count");
      }

      if (read)
      {
        compute_recall_lbest(b, cn);
      }
    }
  }
}

stop_recurse_check()

bool recall_tree_ns::stop_recurse_check	(	recall_tree &	b,
		uint32_t	parent,
		uint32_t	child
	)

Definition at line 306 of file recall_tree.cc.

References recall_tree_ns::recall_tree::bern_hyper, and recall_tree_ns::recall_tree::nodes.

Referenced by learn(), and predict_from().

{
  return b.bern_hyper > 0 && b.nodes[parent].recall_lbest >= b.nodes[child].recall_lbest;
}

to_prob()

float recall_tree_ns::to_prob

(

float

x

)

Definition at line 85 of file recall_tree.cc.

References f.

Referenced by learn().

{
  static const float alpha = 2.0f;
  // http://stackoverflow.com/questions/2789481/problem-calling-stdmax
  return std::max(0.f, std::min(1.f, 0.5f * (1.0f + alpha * x)));
}

train_node()

float recall_tree_ns::train_node	(	recall_tree &	b,
		single_learner &	base,
		example &	ec,
		uint32_t	cn
	)

Definition at line 342 of file recall_tree.cc.

References example::l, LEARNER::learner< T, E >::learn(), label_type::mc, polylabel::multi, polyprediction::multiclass, recall_tree_ns::recall_tree::nodes, example::pred, LEARNER::learner< T, E >::predict(), polyprediction::scalar, polylabel::simple, updated_entropy(), and MULTICLASS::label_t::weight.

{
  MULTICLASS::label_t mc = ec.l.multi;
  uint32_t save_pred = ec.pred.multiclass;

  // minimize entropy
  // better than maximize expected likelihood, and the proofs go through :)
  double new_left = updated_entropy(b, b.nodes[cn].left, ec);
  double new_right = updated_entropy(b, b.nodes[cn].right, ec);
  double old_left = b.nodes[b.nodes[cn].left].entropy;
  double old_right = b.nodes[b.nodes[cn].right].entropy;
  double nl = b.nodes[b.nodes[cn].left].n;
  double nr = b.nodes[b.nodes[cn].right].n;
  double delta_left = nl * (new_left - old_left) + mc.weight * new_left;
  double delta_right = nr * (new_right - old_right) + mc.weight * new_right;
  float route_label = delta_left < delta_right ? -1.f : 1.f;
  float imp_weight = fabs((float)(delta_left - delta_right));

  ec.l.simple = {route_label, imp_weight, 0.};
  base.learn(ec, b.nodes[cn].base_router);

  // TODO: using the updated routing seems to help
  // TODO: consider faster version using updated_prediction
  // TODO: (doesn't play well with link function)
  base.predict(ec, b.nodes[cn].base_router);

  float save_scalar = ec.pred.scalar;

  ec.l.multi = mc;
  ec.pred.multiclass = save_pred;

  return save_scalar;
}

updated_entropy()

double recall_tree_ns::updated_entropy	(	recall_tree &	b,
		uint32_t	cn,
		example &	ec
	)

Definition at line 171 of file recall_tree.cc.

References v_array< T >::end(), find(), recall_tree_ns::node_pred::label_count, recall_tree_ns::recall_tree::nodes, plogp(), and example::weight.

Referenced by insert_example_at_node(), and train_node().

{
  node_pred* ls = find(b, cn, ec);

  // entropy = -\sum_k (c_k/n) Log[c_k/n]
  // c_0 <- c_0 + 1, n <- n + 1
  // entropy <- + (c_0/n) Log[c_0/n]
  //            - n/(n+1) \sum_{k>0} (c_k/n) Log[c_k/n]
  //            - Log[n/(n+1)] \sum_{k>0} (c_k/(n+1))
  //            - ((c_0+1)/(n+1)) Log[(c_0+1)/(n+1)]

  double c0 = (ls == b.nodes[cn].preds.end()) ? 0 : ls->label_count;
  double deltac0 = ec.weight;
  double n = b.nodes[cn].n;

  double novernp1 = n / (deltac0 + n);
  double lognovernp1 = (novernp1 == 0) ? 0 : log(novernp1);
  double nminusc0overnp1 = (n - c0) / (n + deltac0);

  double newentropy = b.nodes[cn].entropy;

  newentropy += plogp(c0, n);
  newentropy *= novernp1;
  newentropy -= lognovernp1 * nminusc0overnp1;
  newentropy -= plogp(c0 + deltac0, n + deltac0);

  return newentropy;
}