memory_tree_ns Namespace Reference

Classes
struct	memory_tree
struct	node

Functions
template<typename T >
void	remove_at_index (v_array< T > &array, uint32_t index)
void	copy_example_data (example *dst, example *src, bool oas=false)
void	free_example (example *ec)
void	diag_kronecker_prod_fs_test (features &f1, features &f2, features &prod_f, float &total_sum_feat_sq, float norm_sq1, float norm_sq2)
int	cmpfunc (const void *a, const void *b)
void	diag_kronecker_product_test (example &ec1, example &ec2, example &ec, bool oas=false)
float	linear_kernel (const flat_example *fec1, const flat_example *fec2)
float	normalized_linear_prod (memory_tree &b, example *ec1, example *ec2)
void	init_tree (memory_tree &b)
uint64_t	insert_descent (node &n, const float prediction)
int	random_sample_example_pop (memory_tree &b, uint64_t &cn)
float	train_node (memory_tree &b, single_learner &base, example &ec, const uint64_t cn)
void	split_leaf (memory_tree &b, single_learner &base, const uint64_t cn)
int	compare_label (const void *a, const void *b)
uint32_t	over_lap (v_array< uint32_t > &array_1, v_array< uint32_t > &array_2)
uint32_t	hamming_loss (v_array< uint32_t > &array_1, v_array< uint32_t > &array_2)
void	collect_labels_from_leaf (memory_tree &b, const uint64_t cn, v_array< uint32_t > &leaf_labs)
void	train_one_against_some_at_leaf (memory_tree &b, single_learner &base, const uint64_t cn, example &ec)
uint32_t	compute_hamming_loss_via_oas (memory_tree &b, single_learner &base, const uint64_t cn, example &ec, v_array< uint32_t > &selected_labs)
int64_t	pick_nearest (memory_tree &b, single_learner &base, const uint64_t cn, example &ec)
float	get_overlap_from_two_examples (example &ec1, example &ec2)
float	F1_score_for_two_examples (example &ec1, example &ec2)
void	predict (memory_tree &b, single_learner &base, example &ec)
float	return_reward_from_node (memory_tree &b, single_learner &base, uint64_t cn, example &ec, float weight=1.f)
void	learn_at_leaf_random (memory_tree &b, single_learner &base, const uint64_t &leaf_id, example &ec, const float &weight)
void	route_to_leaf (memory_tree &b, single_learner &base, const uint32_t &ec_array_index, uint64_t cn, v_array< uint64_t > &path, bool insertion)
void	single_query_and_learn (memory_tree &b, single_learner &base, const uint32_t &ec_array_index, example &ec)
void	update_rew (memory_tree &b, single_learner &base, const uint32_t &ec_array_index, example &ec)
void	insert_example (memory_tree &b, single_learner &base, const uint32_t &ec_array_index, bool fake_insert=false)
void	experience_replay (memory_tree &b, single_learner &base)
void	learn (memory_tree &b, single_learner &base, example &ec)
void	end_pass (memory_tree &b)
void	save_load_example (example *ec, io_buf &model_file, bool &read, bool &text, std::stringstream &msg, bool &oas)
void	save_load_node (node &cn, io_buf &model_file, bool &read, bool &text, std::stringstream &msg)
void	save_load_memory_tree (memory_tree &b, io_buf &model_file, bool read, bool text)

Function Documentation

cmpfunc()

int memory_tree_ns::cmpfunc	(	const void *	a,
		const void *	b
	)

Definition at line 97 of file memory_tree.cc.

Referenced by diag_kronecker_product_test().

{ return *(char*)a - *(char*)b; }

collect_labels_from_leaf()

void memory_tree_ns::collect_labels_from_leaf	(	memory_tree &	b,
		const uint64_t	cn,
		v_array< uint32_t > &	leaf_labs
	)

Definition at line 553 of file memory_tree.cc.

References v_array< T >::clear(), memory_tree_ns::memory_tree::examples, memory_tree_ns::memory_tree::nodes, v_array< T >::push_back(), v_array< T >::size(), and v_array_contains().

Referenced by compute_hamming_loss_via_oas(), and train_one_against_some_at_leaf().

{
  if (b.nodes[cn].internal != -1)
    std::cout << "something is wrong, it should be a leaf node" << std::endl;

  leaf_labs.clear();
  for (size_t i = 0; i < b.nodes[cn].examples_index.size(); i++)
  {  // scan through each memory in the leaf
    uint32_t loc = b.nodes[cn].examples_index[i];
    for (uint32_t lab : b.examples[loc]->l.multilabels.label_v)
    {  // scan through each label:
      if (v_array_contains(leaf_labs, lab) == false)
        leaf_labs.push_back(lab);
    }
  }
}

compare_label()

int memory_tree_ns::compare_label	(	const void *	a,
		const void *	b
	)

Definition at line 517 of file memory_tree.cc.

Referenced by over_lap().

{ return *(uint32_t*)a - *(uint32_t*)b; }

compute_hamming_loss_via_oas()

uint32_t memory_tree_ns::compute_hamming_loss_via_oas ( memory_tree &  b, single_learner &  base, const uint64_t  cn, example &  ec, v_array< uint32_t > &  selected_labs  )

inline

Definition at line 588 of file memory_tree.cc.

References collect_labels_from_leaf(), v_array< T >::delete_v(), hamming_loss(), example::l, MULTILABEL::labels::label_v, memory_tree_ns::memory_tree::max_routers, prediction_type::multilabels, polylabel::multilabels, polyprediction::multilabels, example::pred, LEARNER::learner< T, E >::predict(), v_array< T >::push_back(), polyprediction::scalar, polylabel::simple, and v_array< T >::size().

Referenced by predict().

{
  selected_labs.delete_v();
  v_array<uint32_t> leaf_labs = v_init<uint32_t>();
  collect_labels_from_leaf(b, cn, leaf_labs);  // unique labels stored in the leaf.
  MULTILABEL::labels multilabels = ec.l.multilabels;
  MULTILABEL::labels preds = ec.pred.multilabels;
  ec.l.simple = {FLT_MAX, 1.f, 0.f};
  for (size_t i = 0; i < leaf_labs.size(); i++)
  {
    base.predict(ec, b.max_routers + 1 + leaf_labs[i]);
    float score = ec.pred.scalar;
    if (score > 0)
      selected_labs.push_back(leaf_labs[i]);
  }
  ec.pred.multilabels = preds;
  ec.l.multilabels = multilabels;

  return hamming_loss(ec.l.multilabels.label_v, selected_labs);
}

copy_example_data()

void memory_tree_ns::copy_example_data	(	example *	dst,
		example *	src,
		bool	oas = false
	)

Definition at line 43 of file memory_tree.cc.

References copy_array(), VW::copy_example_data(), v_array< T >::delete_v(), example::l, MULTICLASS::label_t::label, MULTILABEL::labels::label_v, polylabel::multi, and polylabel::multilabels.

Referenced by diag_kronecker_product_test(), and learn().

{
  if (oas == false)
  {
    dst->l = src->l;
    dst->l.multi.label = src->l.multi.label;
  }
  else
  {
    dst->l.multilabels.label_v.delete_v();
    copy_array(dst->l.multilabels.label_v, src->l.multilabels.label_v);
  }
  VW::copy_example_data(false, dst, src);
}

diag_kronecker_prod_fs_test()

void memory_tree_ns::diag_kronecker_prod_fs_test	(	features &	f1,
		features &	f2,
		features &	prod_f,
		float &	total_sum_feat_sq,
		float	norm_sq1,
		float	norm_sq2
	)

Definition at line 67 of file memory_tree.cc.

References features::delete_v(), f, features::indicies, features::push_back(), v_array< T >::size(), features::size(), and features::values.

Referenced by diag_kronecker_product_test().

{
  prod_f.delete_v();
  if (f2.indicies.size() == 0)
    return;

  float denominator = pow(norm_sq1 * norm_sq2, 0.5f);
  size_t idx1 = 0;
  size_t idx2 = 0;

  while (idx1 < f1.size() && idx2 < f2.size())
  {
    uint64_t ec1pos = f1.indicies[idx1];
    uint64_t ec2pos = f2.indicies[idx2];

    if (ec1pos < ec2pos)
      idx1++;
    else if (ec1pos > ec2pos)
      idx2++;
    else
    {
      prod_f.push_back(f1.values[idx1] * f2.values[idx2] / denominator, ec1pos);
      total_sum_feat_sq += f1.values[idx1] * f2.values[idx2] / denominator;  // make this out of loop
      idx1++;
      idx2++;
    }
  }
}

diag_kronecker_product_test()

void memory_tree_ns::diag_kronecker_product_test	(	example &	ec1,
		example &	ec2,
		example &	ec,
		bool	oas = false
	)

Definition at line 99 of file memory_tree.cc.

References v_array< T >::begin(), cmpfunc(), copy_example_data(), VW::dealloc_example(), diag_kronecker_prod_fs_test(), example_predict::feature_space, example_predict::indices, v_array< T >::size(), and example::total_sum_feat_sq.

Referenced by learn_at_leaf_random(), pick_nearest(), and return_reward_from_node().

{
  // copy_example_data(&ec, &ec1, oas); //no_feat false, oas: true
  VW::dealloc_example(nullptr, ec, nullptr);  // clear ec
  copy_example_data(&ec, &ec1, oas);

  ec.total_sum_feat_sq = 0.0;  // sort namespaces.  pass indices array into sort...template (leave this to the end)

  qsort(ec1.indices.begin(), ec1.indices.size(), sizeof(namespace_index), cmpfunc);
  qsort(ec2.indices.begin(), ec2.indices.size(), sizeof(namespace_index), cmpfunc);

  size_t idx1 = 0;
  size_t idx2 = 0;
  while (idx1 < ec1.indices.size() && idx2 < ec2.indices.size())
  // for (size_t idx1 = 0, idx2 = 0; idx1 < ec1.indices.size() && idx2 < ec2.indices.size(); idx1++)
  {
    namespace_index c1 = ec1.indices[idx1];
    namespace_index c2 = ec2.indices[idx2];
    if (c1 < c2)
      idx1++;
    else if (c1 > c2)
      idx2++;
    else
    {
      diag_kronecker_prod_fs_test(ec1.feature_space[c1], ec2.feature_space[c2], ec.feature_space[c1],
          ec.total_sum_feat_sq, ec1.total_sum_feat_sq, ec2.total_sum_feat_sq);
      idx1++;
      idx2++;
    }
  }
}

end_pass()

void memory_tree_ns::end_pass

(

memory_tree &

b

)

Definition at line 1074 of file memory_tree.cc.

References memory_tree_ns::memory_tree::current_pass, memory_tree_ns::memory_tree::examples, and v_array< T >::size().

{
  b.current_pass++;
  std::cout << "######### Current Pass: " << b.current_pass
            << ", with number of memories strored so far: " << b.examples.size() << std::endl;
}

experience_replay()

void memory_tree_ns::experience_replay	(	memory_tree &	b,
		single_learner &	base
	)

Definition at line 994 of file memory_tree.cc.

References memory_tree_ns::memory_tree::current_pass, v_array< T >::delete_v(), memory_tree_ns::memory_tree::dream_at_update, insert_example(), random_sample_example_pop(), and route_to_leaf().

Referenced by learn().

{
  uint64_t cn = 0;  // start from root, randomly descent down!
  int ec_id = random_sample_example_pop(b, cn);
  if (ec_id >= 0)
  {
    if (b.current_pass < 1)
      insert_example(b, base, ec_id);  // unsupervised learning
    else
    {
      if (b.dream_at_update == false)
      {
        v_array<uint64_t> tmp_path = v_init<uint64_t>();
        route_to_leaf(b, base, ec_id, 0, tmp_path, true);
        tmp_path.delete_v();
      }
      else
      {
        insert_example(b, base, ec_id);
      }
    }
  }
}

F1_score_for_two_examples()

float memory_tree_ns::F1_score_for_two_examples	(	example &	ec1,
		example &	ec2
	)

Definition at line 654 of file memory_tree.cc.

References f, get_overlap_from_two_examples(), example::l, MULTILABEL::labels::label_v, polylabel::multilabels, and v_array< T >::size().

Referenced by predict(), and return_reward_from_node().

{
  float num_overlaps = get_overlap_from_two_examples(ec1, ec2);
  float v1 = (float)(num_overlaps / (1e-7 + ec1.l.multilabels.label_v.size() * 1.));
  float v2 = (float)(num_overlaps / (1e-7 + ec2.l.multilabels.label_v.size() * 1.));
  if (num_overlaps == 0.f)
    return 0.f;
  else
    // return v2; //only precision
    return 2.f * (v1 * v2 / (v1 + v2));
}

free_example()

void memory_tree_ns::free_example ( example *  ec )

inline

Definition at line 58 of file memory_tree.cc.

References VW::dealloc_example().

Referenced by memory_tree_ns::memory_tree::~memory_tree().

{
  VW::dealloc_example(nullptr, *ec);
  free(ec);
}

get_overlap_from_two_examples()

float memory_tree_ns::get_overlap_from_two_examples	(	example &	ec1,
		example &	ec2
	)

Definition at line 648 of file memory_tree.cc.

References example::l, MULTILABEL::labels::label_v, polylabel::multilabels, and over_lap().

Referenced by F1_score_for_two_examples().

{
  return (float)over_lap(ec1.l.multilabels.label_v, ec2.l.multilabels.label_v);
}

hamming_loss()

uint32_t memory_tree_ns::hamming_loss ( v_array< uint32_t > &  array_1, v_array< uint32_t > &  array_2  )

inline

Definition at line 547 of file memory_tree.cc.

References over_lap(), and v_array< T >::size().

Referenced by compute_hamming_loss_via_oas().

{
  uint32_t overlap = over_lap(array_1, array_2);
  return (uint32_t)(array_1.size() + array_2.size() - 2 * overlap);
}

init_tree()

void memory_tree_ns::init_tree

(

memory_tree &

b

)

Definition at line 281 of file memory_tree.cc.

References memory_tree_ns::memory_tree::construct_time, memory_tree_ns::memory_tree::current_pass, memory_tree_ns::memory_tree::dream_repeats, memory_tree_ns::memory_tree::F1_score, memory_tree_ns::memory_tree::hamming_loss, memory_tree_ns::memory_tree::iter, memory_tree_ns::memory_tree::kprod_ec, memory_tree_ns::memory_tree::learn_at_leaf, memory_tree_ns::memory_tree::max_depth, memory_tree_ns::memory_tree::max_ex_in_leaf, memory_tree_ns::memory_tree::max_nodes, memory_tree_ns::memory_tree::max_num_labels, memory_tree_ns::memory_tree::max_routers, memory_tree_ns::memory_tree::nodes, memory_tree_ns::memory_tree::num_mistakes, memory_tree_ns::memory_tree::oas, v_array< T >::push_back(), memory_tree_ns::memory_tree::routers_used, v_array< T >::size(), memory_tree_ns::memory_tree::test_mode, memory_tree_ns::memory_tree::test_time, memory_tree_ns::memory_tree::top_K, and memory_tree_ns::memory_tree::total_num_queries.

{
  // srand48(4000);
  // simple initilization: initilize the root only
  b.iter = 0;
  b.num_mistakes = 0;
  b.routers_used = 0;
  b.test_mode = false;
  b.max_depth = 0;
  b.max_ex_in_leaf = 0;
  b.construct_time = 0;
  b.test_time = 0;
  b.top_K = 1;
  b.hamming_loss = 0.f;
  b.F1_score = 0.f;

  b.nodes.push_back(node());
  b.nodes[0].internal = -1;  // mark the root as leaf
  b.nodes[0].base_router = (b.routers_used++);

  b.kprod_ec = &calloc_or_throw<example>();  // allocate space for kronecker product example

  b.total_num_queries = 0;
  b.max_routers = b.max_nodes;
  std::cout << "tree initiazliation is done...." << std::endl
            << "max nodes " << b.max_nodes << std::endl
            << "tree size: " << b.nodes.size() << std::endl
            << "max number of unique labels: " << b.max_num_labels << std::endl
            << "learn at leaf: " << b.learn_at_leaf << std::endl
            << "num of dream operations per example: " << b.dream_repeats << std::endl
            << "current_pass: " << b.current_pass << std::endl
            << "oas: " << b.oas << std::endl;
}

insert_descent()

uint64_t memory_tree_ns::insert_descent ( node &  n, const float  prediction  )

inline

Definition at line 316 of file memory_tree.cc.

References memory_tree_ns::node::left, memory_tree_ns::node::nl, memory_tree_ns::node::nr, and memory_tree_ns::node::right.

Referenced by insert_example(), route_to_leaf(), and split_leaf().

{
  // prediction <0 go left, otherwise go right
  if (prediction < 0)
  {
    n.nl++;  // increment the number of examples routed to the left.
    return n.left;
  }
  else
  {          // otherwise go right.
    n.nr++;  // increment the number of examples routed to the right.
    return n.right;
  }
}

insert_example()

void memory_tree_ns::insert_example	(	memory_tree &	b,
		single_learner &	base,
		const uint32_t &	ec_array_index,
		bool	fake_insert = false
	)

Definition at line 961 of file memory_tree.cc.

References memory_tree_ns::memory_tree::examples, insert_descent(), memory_tree_ns::memory_tree::max_ex_in_leaf, memory_tree_ns::memory_tree::max_leaf_examples, memory_tree_ns::memory_tree::max_nodes, memory_tree_ns::memory_tree::nodes, memory_tree_ns::memory_tree::oas, v_array< T >::push_back(), v_array< T >::size(), split_leaf(), train_node(), and train_one_against_some_at_leaf().

Referenced by experience_replay(), and learn().

{
  uint64_t cn = 0;                   // start from the root.
  while (b.nodes[cn].internal == 1)  // if it's internal node:
  {
    // predict and train the node at cn.
    float router_pred = train_node(b, base, *b.examples[ec_array_index], cn);
    uint64_t newcn = insert_descent(b.nodes[cn], router_pred);  // updated nr or nl
    cn = newcn;
  }

  if (b.oas == true)  // if useing oas as inference procedure, we just train oas here, as it's independent of the memory
                      // unit anyway'
    train_one_against_some_at_leaf(b, base, cn, *b.examples[ec_array_index]);

  if ((b.nodes[cn].internal == -1) && (fake_insert == false))  // get to leaf:
  {
    b.nodes[cn].examples_index.push_back(ec_array_index);
    if (b.nodes[cn].examples_index.size() > b.max_ex_in_leaf)
    {
      b.max_ex_in_leaf = b.nodes[cn].examples_index.size();
    }
    float leaf_pred = train_node(b, base, *b.examples[ec_array_index], cn);  // tain the leaf as well.
    insert_descent(b.nodes[cn], leaf_pred);  // this is a faked descent, the purpose is only to update nl and nr of cn

    // if the number of examples exceeds the max_leaf_examples, and not reach the max_nodes - 2 yet, we split:
    if ((b.nodes[cn].examples_index.size() >= b.max_leaf_examples) && (b.nodes.size() + 2 <= b.max_nodes))
    {
      split_leaf(b, base, cn);
    }
  }
}

learn()

void memory_tree_ns::learn	(	memory_tree &	b,
		single_learner &	base,
		example &	ec
	)

Definition at line 1020 of file memory_tree.cc.

References memory_tree_ns::memory_tree::construct_time, copy_example_data(), memory_tree_ns::memory_tree::current_pass, memory_tree_ns::memory_tree::dream_repeats, memory_tree_ns::memory_tree::examples, experience_replay(), memory_tree_ns::memory_tree::hamming_loss, insert_example(), memory_tree_ns::memory_tree::iter, memory_tree_ns::memory_tree::max_depth, memory_tree_ns::memory_tree::max_ex_in_leaf, memory_tree_ns::memory_tree::num_mistakes, memory_tree_ns::memory_tree::oas, memory_tree_ns::memory_tree::online, predict(), v_array< T >::push_back(), v_array< T >::size(), memory_tree_ns::memory_tree::test_mode, memory_tree_ns::memory_tree::test_time, memory_tree_ns::memory_tree::top_K, memory_tree_ns::memory_tree::total_num_queries, and update_rew().

Referenced by memory_tree_setup().

{
  if (b.test_mode == false)
  {
    b.iter++;
    predict(b, base, ec);

    if (b.iter % 5000 == 0)
    {
      if (b.oas == false)
        std::cout << "at iter " << b.iter << ", top(" << b.top_K << ") pred error: " << b.num_mistakes * 1. / b.iter
                  << ", total num queires so far: " << b.total_num_queries << ", max depth: " << b.max_depth
                  << ", max exp in leaf: " << b.max_ex_in_leaf << std::endl;
      else
        std::cout << "at iter " << b.iter << ", avg hamming loss: " << b.hamming_loss * 1. / b.iter << std::endl;
    }

    clock_t begin = clock();

    if (b.current_pass < 1)
    {  // in the first pass, we need to store the memory:
      example* new_ec = &calloc_or_throw<example>();
      copy_example_data(new_ec, &ec, b.oas);
      b.examples.push_back(new_ec);
      if (b.online == true)
        update_rew(b, base, (uint32_t)(b.examples.size() - 1), *b.examples[b.examples.size() - 1]);  // query and learn

      insert_example(b, base, (uint32_t)(b.examples.size() - 1));  // unsupervised learning.
      for (uint32_t i = 0; i < b.dream_repeats; i++) experience_replay(b, base);
    }
    else
    {  // starting from the current pass, we just learn using reinforcement signal, no insertion needed:
      size_t ec_id = (b.iter) % b.examples.size();
      update_rew(b, base, (uint32_t)ec_id, *b.examples[ec_id]);  // no insertion will happen in this call
      for (uint32_t i = 0; i < b.dream_repeats; i++) experience_replay(b, base);
    }
    b.construct_time += float(clock() - begin) / CLOCKS_PER_SEC;
  }
  else if (b.test_mode == true)
  {
    b.iter++;
    if (b.iter % 5000 == 0)
    {
      if (b.oas == false)
        std::cout << "at iter " << b.iter << ", pred error: " << b.num_mistakes * 1. / b.iter << std::endl;
      else
        std::cout << "at iter " << b.iter << ", avg hamming loss: " << b.hamming_loss * 1. / b.iter << std::endl;
    }
    clock_t begin = clock();
    predict(b, base, ec);
    b.test_time += float(clock() - begin) / CLOCKS_PER_SEC;
  }
}

learn_at_leaf_random()

void memory_tree_ns::learn_at_leaf_random	(	memory_tree &	b,
		single_learner &	base,
		const uint64_t &	leaf_id,
		example &	ec,
		const float &	weight
	)

Definition at line 800 of file memory_tree.cc.

References memory_tree_ns::memory_tree::_random_state, diag_kronecker_product_test(), memory_tree_ns::memory_tree::examples, memory_tree_ns::memory_tree::kprod_ec, example::l, MULTICLASS::label_t::label, LEARNER::learner< T, E >::learn(), memory_tree_ns::memory_tree::max_routers, polylabel::multi, memory_tree_ns::memory_tree::nodes, normalized_linear_prod(), memory_tree_ns::memory_tree::oas, polylabel::simple, v_array< T >::size(), memory_tree_ns::memory_tree::total_num_queries, and example::weight.

Referenced by single_query_and_learn().

{
  b.total_num_queries++;
  int32_t ec_id = -1;
  float reward = 0.f;
  if (b.nodes[leaf_id].examples_index.size() > 0)
  {
    uint32_t pos = uint32_t(b._random_state->get_and_update_random() * b.nodes[leaf_id].examples_index.size());
    ec_id = b.nodes[leaf_id].examples_index[pos];
  }
  if (ec_id != -1)
  {
    if (b.examples[ec_id]->l.multi.label == ec.l.multi.label)
      reward = 1.f;
    float score = normalized_linear_prod(b, &ec, b.examples[ec_id]);
    diag_kronecker_product_test(ec, *b.examples[ec_id], *b.kprod_ec, b.oas);
    b.kprod_ec->l.simple = {reward, 1.f, -score};
    b.kprod_ec->weight = weight;  //* b.nodes[leaf_id].examples_index.size();
    base.learn(*b.kprod_ec, b.max_routers);
  }
  return;
}

linear_kernel()

float memory_tree_ns::linear_kernel	(	const flat_example *	fec1,
		const flat_example *	fec2
	)

Definition at line 241 of file memory_tree.cc.

References f, flat_example::fs, features::indicies, features::size(), and features::values.

{
  float dotprod = 0;

  features& fs_1 = (features&)fec1->fs;
  features& fs_2 = (features&)fec2->fs;
  if (fs_2.indicies.size() == 0)
    return 0.f;

  for (size_t idx1 = 0, idx2 = 0; idx1 < fs_1.size() && idx2 < fs_2.size(); idx1++)
  {
    uint64_t ec1pos = fs_1.indicies[idx1];
    uint64_t ec2pos = fs_2.indicies[idx2];
    if (ec1pos < ec2pos)
      continue;

    while (ec1pos > ec2pos && ++idx2 < fs_2.size()) ec2pos = fs_2.indicies[idx2];

    if (ec1pos == ec2pos)
    {
      dotprod += fs_1.values[idx1] * fs_2.values[idx2];
      ++idx2;
    }
  }
  return dotprod;
}

normalized_linear_prod()

float memory_tree_ns::normalized_linear_prod	(	memory_tree &	b,
		example *	ec1,
		example *	ec2
	)

Definition at line 268 of file memory_tree.cc.

References memory_tree_ns::memory_tree::all, flatten_sort_example(), free_flatten_example(), linear_kernel(), and flat_example::total_sum_feat_sq.

Referenced by learn_at_leaf_random(), pick_nearest(), and return_reward_from_node().

{
  flat_example* fec1 = flatten_sort_example(*b.all, ec1);
  flat_example* fec2 = flatten_sort_example(*b.all, ec2);
  float norm_sqrt = pow(fec1->total_sum_feat_sq * fec2->total_sum_feat_sq, 0.5f);
  float linear_prod = linear_kernel(fec1, fec2);
  // fec1->fs.delete_v();
  // fec2->fs.delete_v();
  free_flatten_example(fec1);
  free_flatten_example(fec2);
  return linear_prod / norm_sqrt;
}

over_lap()

uint32_t memory_tree_ns::over_lap ( v_array< uint32_t > &  array_1, v_array< uint32_t > &  array_2  )

inline

Definition at line 519 of file memory_tree.cc.

References v_array< T >::begin(), compare_label(), and v_array< T >::size().

Referenced by get_overlap_from_two_examples(), and hamming_loss().

{
  uint32_t num_overlap = 0;

  qsort(array_1.begin(), array_1.size(), sizeof(uint32_t), compare_label);
  qsort(array_2.begin(), array_2.size(), sizeof(uint32_t), compare_label);

  uint32_t idx1 = 0;
  uint32_t idx2 = 0;
  while (idx1 < array_1.size() && idx2 < array_2.size())
  {
    uint32_t c1 = array_1[idx1];
    uint32_t c2 = array_2[idx2];
    if (c1 < c2)
      idx1++;
    else if (c1 > c2)
      idx2++;
    else
    {
      num_overlap++;
      idx1++;
      idx2++;
    }
  }
  return num_overlap;
}

pick_nearest()

int64_t memory_tree_ns::pick_nearest	(	memory_tree &	b,
		single_learner &	base,
		const uint64_t	cn,
		example &	ec
	)

Definition at line 611 of file memory_tree.cc.

References memory_tree_ns::memory_tree::current_pass, diag_kronecker_product_test(), memory_tree_ns::memory_tree::examples, memory_tree_ns::memory_tree::kprod_ec, example::l, memory_tree_ns::memory_tree::learn_at_leaf, memory_tree_ns::memory_tree::max_routers, memory_tree_ns::memory_tree::nodes, normalized_linear_prod(), memory_tree_ns::memory_tree::oas, example::partial_prediction, LEARNER::learner< T, E >::predict(), polylabel::simple, and v_array< T >::size().

Referenced by predict(), and return_reward_from_node().

{
  if (b.nodes[cn].examples_index.size() > 0)
  {
    float max_score = -FLT_MAX;
    int64_t max_pos = -1;
    for (size_t i = 0; i < b.nodes[cn].examples_index.size(); i++)
    {
      float score = 0.f;
      uint32_t loc = b.nodes[cn].examples_index[i];

      // do not use reward to update memory tree during the very first pass
      //(which is for unsupervised training for memory tree)
      if (b.learn_at_leaf == true && b.current_pass >= 1)
      {
        float tmp_s = normalized_linear_prod(b, &ec, b.examples[loc]);
        diag_kronecker_product_test(ec, *b.examples[loc], *b.kprod_ec, b.oas);
        b.kprod_ec->l.simple = {FLT_MAX, 0., tmp_s};
        base.predict(*b.kprod_ec, b.max_routers);
        score = b.kprod_ec->partial_prediction;
      }
      else
        score = normalized_linear_prod(b, &ec, b.examples[loc]);

      if (score > max_score)
      {
        max_score = score;
        max_pos = (int64_t)loc;
      }
    }
    return max_pos;
  }
  else
    return -1;
}

predict()

void memory_tree_ns::predict	(	memory_tree &	b,
		single_learner &	base,
		example &	ec
	)

Definition at line 666 of file memory_tree.cc.

References compute_hamming_loss_via_oas(), memory_tree_ns::memory_tree::examples, memory_tree_ns::memory_tree::F1_score, F1_score_for_two_examples(), memory_tree_ns::memory_tree::hamming_loss, example::l, MULTICLASS::label_t::label, example::loss, label_type::mc, polylabel::multi, polyprediction::multiclass, prediction_type::multilabels, polylabel::multilabels, polyprediction::multilabels, memory_tree_ns::memory_tree::nodes, memory_tree_ns::memory_tree::num_mistakes, memory_tree_ns::memory_tree::oas, pick_nearest(), example::pred, LEARNER::learner< T, E >::predict(), polyprediction::scalar, polylabel::simple, and example::weight.

Referenced by learn(), and memory_tree_setup().

{
  MULTICLASS::label_t mc;
  uint32_t save_multi_pred = 0;
  MULTILABEL::labels multilabels;
  MULTILABEL::labels preds;
  if (b.oas == false)
  {
    mc = ec.l.multi;
    save_multi_pred = ec.pred.multiclass;
  }
  else
  {
    multilabels = ec.l.multilabels;
    preds = ec.pred.multilabels;
  }

  uint64_t cn = 0;
  ec.l.simple = {-1.f, 1.f, 0.};
  while (b.nodes[cn].internal == 1)
  {  // if it's internal{
    base.predict(ec, b.nodes[cn].base_router);
    uint64_t newcn = ec.pred.scalar < 0 ? b.nodes[cn].left : b.nodes[cn].right;  // do not need to increment nl and nr.
    cn = newcn;
  }

  if (b.oas == false)
  {
    ec.l.multi = mc;
    ec.pred.multiclass = save_multi_pred;
  }
  else
  {
    ec.pred.multilabels = preds;
    ec.l.multilabels = multilabels;
  }

  int64_t closest_ec = 0;
  if (b.oas == false)
  {
    closest_ec = pick_nearest(b, base, cn, ec);
    if (closest_ec != -1)
      ec.pred.multiclass = b.examples[closest_ec]->l.multi.label;
    else
      ec.pred.multiclass = 0;

    if (ec.l.multi.label != ec.pred.multiclass)
    {
      ec.loss = ec.weight;
      b.num_mistakes++;
    }
  }
  else
  {
    float reward = 0.f;
    closest_ec = pick_nearest(b, base, cn, ec);
    if (closest_ec != -1)
    {
      reward = F1_score_for_two_examples(ec, *b.examples[closest_ec]);
      b.F1_score += reward;
    }
    v_array<uint32_t> selected_labs = v_init<uint32_t>();
    ec.loss = (float)compute_hamming_loss_via_oas(b, base, cn, ec, selected_labs);
    b.hamming_loss += ec.loss;
  }
}

random_sample_example_pop()

int memory_tree_ns::random_sample_example_pop ( memory_tree &  b, uint64_t &  cn  )

inline

Definition at line 332 of file memory_tree.cc.

References memory_tree_ns::memory_tree::_random_state, memory_tree_ns::memory_tree::nodes, remove_at_index(), and v_array< T >::size().

Referenced by experience_replay().

{
  cn = 0;  // always start from the root:
  while (b.nodes[cn].internal == 1)
  {
    float pred = 0.;              // deal with some edge cases:
    if (b.nodes[cn].nl < 1)       // no examples routed to left ever:
      pred = 1.f;                 // go right.
    else if (b.nodes[cn].nr < 1)  // no examples routed to right ever:
      pred = -1.f;                // go left.
    else if ((b.nodes[cn].nl >= 1) && (b.nodes[cn].nr >= 1))
      pred = b._random_state->get_and_update_random() < (b.nodes[cn].nl * 1. / (b.nodes[cn].nr + b.nodes[cn].nl)) ? -1.f
                                                                                                                  : 1.f;
    else
    {
      std::cout << cn << " " << b.nodes[cn].nl << " " << b.nodes[cn].nr << std::endl;
      std::cout << "Error:  nl = 0, and nr = 0, exit...";
      exit(0);
    }

    if (pred < 0)
    {
      b.nodes[cn].nl--;
      cn = b.nodes[cn].left;
    }
    else
    {
      b.nodes[cn].nr--;
      cn = b.nodes[cn].right;
    }
  }

  if (b.nodes[cn].examples_index.size() >= 1)
  {
    int loc_at_leaf = int(b._random_state->get_and_update_random() * b.nodes[cn].examples_index.size());
    uint32_t ec_id = b.nodes[cn].examples_index[loc_at_leaf];
    remove_at_index(b.nodes[cn].examples_index, loc_at_leaf);
    return ec_id;
  }
  else
    return -1;
}

remove_at_index()

template<typename T >

void memory_tree_ns::remove_at_index	(	v_array< T > &	array,
		uint32_t	index
	)

Definition at line 23 of file memory_tree.cc.

References v_array< T >::pop(), and v_array< T >::size().

Referenced by random_sample_example_pop().

{
  if (index >= array.size())
  {
    std::cout << "ERROR: index is larger than the size" << std::endl;
    return;
  }
  if (index == array.size() - 1)
  {
    array.pop();
    return;
  }
  for (size_t i = index + 1; i < array.size(); i++)
  {
    array[i - 1] = array[i];
  }
  array.pop();
  return;
}

return_reward_from_node()

float memory_tree_ns::return_reward_from_node	(	memory_tree &	b,
		single_learner &	base,
		uint64_t	cn,
		example &	ec,
		float	weight = 1.f
	)

learn the inference procedure anyway

Definition at line 733 of file memory_tree.cc.

References diag_kronecker_product_test(), memory_tree_ns::memory_tree::examples, F1_score_for_two_examples(), memory_tree_ns::memory_tree::kprod_ec, example::l, MULTICLASS::label_t::label, LEARNER::learner< T, E >::learn(), memory_tree_ns::memory_tree::learn_at_leaf, memory_tree_ns::memory_tree::max_routers, label_type::mc, polylabel::multi, polyprediction::multiclass, prediction_type::multilabels, polylabel::multilabels, polyprediction::multilabels, memory_tree_ns::memory_tree::nodes, normalized_linear_prod(), memory_tree_ns::memory_tree::oas, pick_nearest(), example::pred, LEARNER::learner< T, E >::predict(), polyprediction::scalar, polylabel::simple, memory_tree_ns::memory_tree::total_num_queries, train_one_against_some_at_leaf(), and example::weight.

Referenced by single_query_and_learn().

{
  // example& ec = *b.examples[ec_array_index];
  MULTICLASS::label_t mc;
  uint32_t save_multi_pred = 0;
  MULTILABEL::labels multilabels;
  MULTILABEL::labels preds;
  if (b.oas == false)
  {
    mc = ec.l.multi;
    save_multi_pred = ec.pred.multiclass;
  }
  else
  {
    multilabels = ec.l.multilabels;
    preds = ec.pred.multilabels;
  }
  ec.l.simple = {FLT_MAX, 1., 0.0};
  while (b.nodes[cn].internal != -1)
  {
    base.predict(ec, b.nodes[cn].base_router);
    float prediction = ec.pred.scalar;
    cn = prediction < 0 ? b.nodes[cn].left : b.nodes[cn].right;
  }

  if (b.oas == false)
  {
    ec.l.multi = mc;
    ec.pred.multiclass = save_multi_pred;
  }
  else
  {
    ec.pred.multilabels = preds;
    ec.l.multilabels = multilabels;
  }

  // get to leaf now:
  int64_t closest_ec = 0;
  float reward = 0.f;
  closest_ec = pick_nearest(b, base, cn, ec);  // no randomness for picking example.
  if (b.oas == false)
  {
    if ((closest_ec != -1) && (b.examples[closest_ec]->l.multi.label == ec.l.multi.label))
      reward = 1.f;
  }
  else
  {
    if (closest_ec != -1)
      reward = F1_score_for_two_examples(ec, *b.examples[closest_ec]);
  }
  b.total_num_queries++;

  if (b.learn_at_leaf == true && closest_ec != -1)
  {
    float score = normalized_linear_prod(b, &ec, b.examples[closest_ec]);
    diag_kronecker_product_test(ec, *b.examples[closest_ec], *b.kprod_ec, b.oas);
    b.kprod_ec->l.simple = {reward, 1.f, -score};
    b.kprod_ec->weight = weight;
    base.learn(*b.kprod_ec, b.max_routers);
  }

  if (b.oas == true)
    train_one_against_some_at_leaf(b, base, cn, ec);  

  return reward;
}

route_to_leaf()

void memory_tree_ns::route_to_leaf	(	memory_tree &	b,
		single_learner &	base,
		const uint32_t &	ec_array_index,
		uint64_t	cn,
		v_array< uint64_t > &	path,
		bool	insertion
	)

Definition at line 824 of file memory_tree.cc.

References v_array< T >::clear(), memory_tree_ns::memory_tree::examples, insert_descent(), example::l, memory_tree_ns::memory_tree::max_leaf_examples, memory_tree_ns::memory_tree::max_nodes, label_type::mc, polylabel::multi, polyprediction::multiclass, prediction_type::multilabels, polylabel::multilabels, polyprediction::multilabels, memory_tree_ns::memory_tree::nodes, memory_tree_ns::memory_tree::oas, example::pred, LEARNER::learner< T, E >::predict(), v_array< T >::push_back(), polyprediction::scalar, polylabel::simple, v_array< T >::size(), and split_leaf().

Referenced by experience_replay(), and single_query_and_learn().

{
  example& ec = *b.examples[ec_array_index];

  MULTICLASS::label_t mc;
  uint32_t save_multi_pred = 0;
  MULTILABEL::labels multilabels;
  MULTILABEL::labels preds;
  if (b.oas == false)
  {
    mc = ec.l.multi;
    save_multi_pred = ec.pred.multiclass;
  }
  else
  {
    multilabels = ec.l.multilabels;
    preds = ec.pred.multilabels;
  }

  path.clear();
  ec.l.simple = {FLT_MAX, 1.0, 0.0};
  while (b.nodes[cn].internal != -1)
  {
    path.push_back(cn);  // path stores node id from the root to the leaf
    base.predict(ec, b.nodes[cn].base_router);
    float prediction = ec.pred.scalar;
    if (insertion == false)
      cn = prediction < 0 ? b.nodes[cn].left : b.nodes[cn].right;
    else
      cn = insert_descent(b.nodes[cn], prediction);
  }
  path.push_back(cn);  // push back the leaf

  if (b.oas == false)
  {
    ec.l.multi = mc;
    ec.pred.multiclass = save_multi_pred;
  }
  else
  {
    ec.pred.multilabels = preds;
    ec.l.multilabels = multilabels;
  }

  // std::cout<<"at route to leaf: "<<path.size()<< std::endl;
  if (insertion == true)
  {
    b.nodes[cn].examples_index.push_back(ec_array_index);
    if ((b.nodes[cn].examples_index.size() >= b.max_leaf_examples) && (b.nodes.size() + 2 < b.max_nodes))
      split_leaf(b, base, cn);
  }
}

save_load_example()

void memory_tree_ns::save_load_example	(	example *	ec,
		io_buf &	model_file,
		bool &	read,
		bool &	text,
		std::stringstream &	msg,
		bool &	oas
	)

Definition at line 1084 of file memory_tree.cc.

References v_array< T >::clear(), features::clear(), v_array< T >::delete_v(), example_predict::feature_space, example_predict::ft_offset, example_predict::indices, features::indicies, example::l, MULTICLASS::label_t::label, MULTILABEL::labels::label_v, example::loss, polylabel::multi, polylabel::multilabels, example::num_features, v_array< T >::push_back(), features::push_back(), v_array< T >::size(), features::size(), example::tag, example::total_sum_feat_sq, features::values, MULTICLASS::label_t::weight, example::weight, writeit, and writeitvar.

Referenced by save_load_memory_tree().

{  // deal with tag
   // deal with labels:
  writeit(ec->num_features, "num_features");
  writeit(ec->total_sum_feat_sq, "total_sum_features");
  writeit(ec->weight, "example_weight");
  writeit(ec->loss, "loss");
  writeit(ec->ft_offset, "ft_offset");
  if (oas == false)
  {  // multi-class
    writeit(ec->l.multi.label, "multiclass_label");
    writeit(ec->l.multi.weight, "multiclass_weight");
  }
  else
  {  // multi-label
    writeitvar(ec->l.multilabels.label_v.size(), "label_size", label_size);
    if (read)
    {
      ec->l.multilabels.label_v.clear();
      for (uint32_t i = 0; i < label_size; i++) ec->l.multilabels.label_v.push_back(0);
    }
    for (uint32_t i = 0; i < label_size; i++) writeit(ec->l.multilabels.label_v[i], "ec_label");
  }

  writeitvar(ec->tag.size(), "tags", tag_number);
  if (read)
  {
    ec->tag.clear();
    for (uint32_t i = 0; i < tag_number; i++) ec->tag.push_back('a');
  }
  for (uint32_t i = 0; i < tag_number; i++) writeit(ec->tag[i], "tag");

  // deal with tag:
  writeitvar(ec->indices.size(), "namespaces", namespace_size);
  if (read)
  {
    ec->indices.delete_v();
    for (uint32_t i = 0; i < namespace_size; i++)
    {
      ec->indices.push_back('\0');
    }
  }
  for (uint32_t i = 0; i < namespace_size; i++) writeit(ec->indices[i], "namespace_index");

  // deal with features
  for (namespace_index nc : ec->indices)
  {
    features* fs = &ec->feature_space[nc];
    writeitvar(fs->size(), "features_", feat_size);
    if (read)
    {
      fs->clear();
      fs->values = v_init<feature_value>();
      fs->indicies = v_init<feature_index>();
      for (uint32_t f_i = 0; f_i < feat_size; f_i++)
      {
        fs->push_back(0, 0);
      }
    }
    for (uint32_t f_i = 0; f_i < feat_size; f_i++) writeit(fs->values[f_i], "value");
    for (uint32_t f_i = 0; f_i < feat_size; f_i++) writeit(fs->indicies[f_i], "index");
  }
}

save_load_memory_tree()

void memory_tree_ns::save_load_memory_tree	(	memory_tree &	b,
		io_buf &	model_file,
		bool	read,
		bool	text
	)

Definition at line 1167 of file memory_tree.cc.

References memory_tree_ns::memory_tree::all, v_array< T >::clear(), memory_tree_ns::memory_tree::examples, io_buf::files, memory_tree_ns::memory_tree::learn_at_leaf, memory_tree_ns::memory_tree::max_nodes, memory_tree_ns::memory_tree::max_num_labels, memory_tree_ns::memory_tree::nodes, memory_tree_ns::memory_tree::oas, v_array< T >::push_back(), save_load_example(), save_load_node(), v_array< T >::size(), parameters::stride_shift(), memory_tree_ns::memory_tree::test_mode, vw::weights, writeit, and writeitvar.

Referenced by memory_tree_setup().

{
  std::stringstream msg;
  if (model_file.files.size() > 0)
  {
    if (read)
      b.test_mode = true;

    if (read)
    {
      uint32_t ss = 0;
      writeit(ss, "stride_shift");
      b.all->weights.stride_shift(ss);
    }
    else
    {
      size_t ss = b.all->weights.stride_shift();
      writeit(ss, "stride_shift");
    }

    writeit(b.max_nodes, "max_nodes");
    writeit(b.learn_at_leaf, "learn_at_leaf");
    writeit(b.oas, "oas");
    // writeit(b.leaf_example_multiplier, "leaf_example_multiplier")
    writeitvar(b.nodes.size(), "nodes", n_nodes);
    writeit(b.max_num_labels, "max_number_of_labels");

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

    // node
    for (uint32_t i = 0; i < n_nodes; i++)
    {
      save_load_node(b.nodes[i], model_file, read, text, msg);
    }
    // deal with examples:
    writeitvar(b.examples.size(), "examples", n_examples);
    if (read)
    {
      b.examples.clear();
      for (uint32_t i = 0; i < n_examples; i++)
      {
        example* new_ec = &calloc_or_throw<example>();
        b.examples.push_back(new_ec);
      }
    }
    for (uint32_t i = 0; i < n_examples; i++) save_load_example(b.examples[i], model_file, read, text, msg, b.oas);
    // std::cout<<"done loading...."<< std::endl;
  }
}

save_load_node()

void memory_tree_ns::save_load_node	(	node &	cn,
		io_buf &	model_file,
		bool &	read,
		bool &	text,
		std::stringstream &	msg
	)

Definition at line 1148 of file memory_tree.cc.

References memory_tree_ns::node::base_router, v_array< T >::clear(), memory_tree_ns::node::depth, memory_tree_ns::node::examples_index, memory_tree_ns::node::internal, memory_tree_ns::node::left, memory_tree_ns::node::nl, memory_tree_ns::node::nr, memory_tree_ns::node::parent, v_array< T >::push_back(), memory_tree_ns::node::right, v_array< T >::size(), writeit, and writeitvar.

Referenced by save_load_memory_tree().

{
  writeit(cn.parent, "parent");
  writeit(cn.internal, "internal");
  writeit(cn.depth, "depth");
  writeit(cn.base_router, "base_router");
  writeit(cn.left, "left");
  writeit(cn.right, "right");
  writeit(cn.nl, "nl");
  writeit(cn.nr, "nr");
  writeitvar(cn.examples_index.size(), "leaf_n_examples", leaf_n_examples);
  if (read)
  {
    cn.examples_index.clear();
    for (uint32_t k = 0; k < leaf_n_examples; k++) cn.examples_index.push_back(0);
  }
  for (uint32_t k = 0; k < leaf_n_examples; k++) writeit(cn.examples_index[k], "example_location");
}

single_query_and_learn()

void memory_tree_ns::single_query_and_learn	(	memory_tree &	b,
		single_learner &	base,
		const uint32_t &	ec_array_index,
		example &	ec
	)

Definition at line 879 of file memory_tree.cc.

References memory_tree_ns::memory_tree::_random_state, memory_tree_ns::memory_tree::alpha, v_array< T >::delete_v(), f, example::l, LEARNER::learner< T, E >::learn(), memory_tree_ns::memory_tree::learn_at_leaf, learn_at_leaf_random(), label_type::mc, polylabel::multi, prediction_type::multilabels, polylabel::multilabels, polyprediction::multilabels, memory_tree_ns::memory_tree::nodes, memory_tree_ns::memory_tree::oas, example::pred, return_reward_from_node(), route_to_leaf(), polylabel::simple, v_array< T >::size(), train_one_against_some_at_leaf(), and example::weight.

Referenced by update_rew().

{
  v_array<uint64_t> path_to_leaf = v_init<uint64_t>();
  route_to_leaf(b, base, ec_array_index, 0, path_to_leaf, false);  // no insertion happens here.

  if (path_to_leaf.size() > 1)
  {
    // uint32_t random_pos = merand48(b._random_state->get_current_state())*(path_to_leaf.size()-1);
    uint32_t random_pos = (uint32_t)(b._random_state->get_and_update_random() * (path_to_leaf.size()));  // include leaf
    uint64_t cn = path_to_leaf[random_pos];

    if (b.nodes[cn].internal != -1)
    {  // if it's an internal node:'
      float objective = 0.f;
      float prob_right = 0.5;
      float coin = b._random_state->get_and_update_random() < prob_right ? 1.f : -1.f;
      float weight = path_to_leaf.size() * 1.f / (path_to_leaf.size() - 1.f);
      if (coin == -1.f)
      {  // go left
        float reward_left_subtree = return_reward_from_node(b, base, b.nodes[cn].left, ec, weight);
        objective = (float)((1. - b.alpha) * log(b.nodes[cn].nl / b.nodes[cn].nr) +
            b.alpha * (-reward_left_subtree / (1. - prob_right)) / 2.);
      }
      else
      {  // go right:
        float reward_right_subtree = return_reward_from_node(b, base, b.nodes[cn].right, ec, weight);
        objective = (float)((1. - b.alpha) * log(b.nodes[cn].nl / b.nodes[cn].nr) +
            b.alpha * (reward_right_subtree / prob_right) / 2.);
      }

      float ec_input_weight = ec.weight;

      MULTICLASS::label_t mc;
      MULTILABEL::labels multilabels;
      MULTILABEL::labels preds;
      if (b.oas == false)
        mc = ec.l.multi;
      else
      {
        multilabels = ec.l.multilabels;
        preds = ec.pred.multilabels;
      }

      ec.weight = fabs(objective);
      if (ec.weight >= 100.f)  // crop the weight, otherwise sometimes cause NAN outputs.
        ec.weight = 100.f;
      else if (ec.weight < .01f)
        ec.weight = 0.01f;
      ec.l.simple = {objective < 0. ? -1.f : 1.f, 1.f, 0.};
      base.learn(ec, b.nodes[cn].base_router);

      if (b.oas == false)
        ec.l.multi = mc;
      else
      {
        ec.pred.multilabels = preds;
        ec.l.multilabels = multilabels;
      }
      ec.weight = ec_input_weight;  // restore the original weight
    }
    else
    {                      // if it's a leaf node:
      float weight = 1.f;  // float(path_to_leaf.size());
      if (b.learn_at_leaf == true)
        learn_at_leaf_random(
            b, base, cn, ec, weight);  // randomly sample one example, query reward, and update leaf learner

      if (b.oas == true)
        train_one_against_some_at_leaf(b, base, cn, ec);
    }
  }
  path_to_leaf.delete_v();
}

split_leaf()

void memory_tree_ns::split_leaf	(	memory_tree &	b,
		single_learner &	base,
		const uint64_t	cn
	)

Definition at line 431 of file memory_tree.cc.

References v_array< T >::delete_v(), memory_tree_ns::memory_tree::examples, insert_descent(), memory_tree_ns::memory_tree::max_depth, memory_tree_ns::memory_tree::max_ex_in_leaf, label_type::mc, prediction_type::multilabels, memory_tree_ns::memory_tree::nodes, memory_tree_ns::memory_tree::oas, LEARNER::learner< T, E >::predict(), v_array< T >::push_back(), memory_tree_ns::memory_tree::routers_used, prediction_type::scalar, v_array< T >::size(), and train_node().

Referenced by insert_example(), and route_to_leaf().

{
  // create two children
  b.nodes[cn].internal = 1;  // swith to internal node.
  uint32_t left_child = (uint32_t)b.nodes.size();
  b.nodes.push_back(node());
  b.nodes[left_child].internal = -1;  // left leaf
  b.nodes[left_child].base_router = (b.routers_used++);
  uint32_t right_child = (uint32_t)b.nodes.size();
  b.nodes.push_back(node());
  b.nodes[right_child].internal = -1;  // right leaf
  b.nodes[right_child].base_router = (b.routers_used++);

  if (b.nodes[cn].depth + 1 > b.max_depth)
  {
    b.max_depth = b.nodes[cn].depth + 1;
    std::cout << "depth " << b.max_depth << std::endl;
  }

  b.nodes[cn].left = left_child;
  b.nodes[cn].right = right_child;
  b.nodes[left_child].parent = cn;
  b.nodes[right_child].parent = cn;
  b.nodes[left_child].depth = b.nodes[cn].depth + 1;
  b.nodes[right_child].depth = b.nodes[cn].depth + 1;

  if (b.nodes[left_child].depth > b.max_depth)
    b.max_depth = b.nodes[left_child].depth;

  // rout the examples stored in the node to the left and right
  for (size_t ec_id = 0; ec_id < b.nodes[cn].examples_index.size(); ec_id++)  // scan all examples stored in the cn
  {
    uint32_t ec_pos = b.nodes[cn].examples_index[ec_id];
    MULTICLASS::label_t mc;
    uint32_t save_multi_pred = 0;
    MULTILABEL::labels multilabels;
    MULTILABEL::labels preds;
    if (b.oas == false)
    {
      mc = b.examples[ec_pos]->l.multi;
      save_multi_pred = b.examples[ec_pos]->pred.multiclass;
    }
    else
    {
      multilabels = b.examples[ec_pos]->l.multilabels;
      preds = b.examples[ec_pos]->pred.multilabels;
    }

    b.examples[ec_pos]->l.simple = {1.f, 1.f, 0.f};
    base.predict(*b.examples[ec_pos], b.nodes[cn].base_router);  // re-predict
    float scalar = b.examples[ec_pos]->pred.scalar;              // this is spliting the leaf.
    if (scalar < 0)
    {
      b.nodes[left_child].examples_index.push_back(ec_pos);
      float leaf_pred = train_node(b, base, *b.examples[ec_pos], left_child);
      insert_descent(b.nodes[left_child], leaf_pred);  // fake descent, only for update nl and nr
    }
    else
    {
      b.nodes[right_child].examples_index.push_back(ec_pos);
      float leaf_pred = train_node(b, base, *b.examples[ec_pos], right_child);
      insert_descent(b.nodes[right_child], leaf_pred);  // fake descent. for update nr and nl
    }

    if (b.oas == false)
    {
      b.examples[ec_pos]->l.multi = mc;
      b.examples[ec_pos]->pred.multiclass = save_multi_pred;
    }
    else
    {
      b.examples[ec_pos]->pred.multilabels = preds;
      b.examples[ec_pos]->l.multilabels = multilabels;
    }
  }
  b.nodes[cn].examples_index.delete_v();                                                 // empty the cn's example list
  b.nodes[cn].nl = std::max(double(b.nodes[left_child].examples_index.size()), 0.001);   // avoid to set nl to zero
  b.nodes[cn].nr = std::max(double(b.nodes[right_child].examples_index.size()), 0.001);  // avoid to set nr to zero

  if (std::max(b.nodes[cn].nl, b.nodes[cn].nr) > b.max_ex_in_leaf)
  {
    b.max_ex_in_leaf = (size_t)std::max(b.nodes[cn].nl, b.nodes[cn].nr);
    // std::cout<<b.max_ex_in_leaf<< std::endl;
  }
}

train_node()

float memory_tree_ns::train_node	(	memory_tree &	b,
		single_learner &	base,
		example &	ec,
		const uint64_t	cn
	)

Definition at line 377 of file memory_tree.cc.

References memory_tree_ns::memory_tree::alpha, example::l, LEARNER::learner< T, E >::learn(), label_type::mc, polylabel::multi, polyprediction::multiclass, prediction_type::multilabels, polylabel::multilabels, polyprediction::multilabels, memory_tree_ns::memory_tree::nodes, memory_tree_ns::memory_tree::oas, example::pred, LEARNER::learner< T, E >::predict(), polyprediction::scalar, polylabel::simple, and example::weight.

{
  // predict, learn and predict
  // note: here we first train the router and then predict.
  MULTICLASS::label_t mc;
  uint32_t save_multi_pred = 0;
  MULTILABEL::labels multilabels;
  MULTILABEL::labels preds;
  if (b.oas == false)
  {
    mc = ec.l.multi;
    save_multi_pred = ec.pred.multiclass;
  }
  else
  {
    multilabels = ec.l.multilabels;
    preds = ec.pred.multilabels;
  }

  ec.l.simple = {1.f, 1.f, 0.};
  base.predict(ec, b.nodes[cn].base_router);
  float prediction = ec.pred.scalar;
  // float imp_weight = 1.f; //no importance weight.

  float weighted_value =
      (float)((1. - b.alpha) * log(b.nodes[cn].nl / (b.nodes[cn].nr + 1e-1)) / log(2.) + b.alpha * prediction);
  float route_label = weighted_value < 0.f ? -1.f : 1.f;

  // ec.l.simple = {route_label, imp_weight, 0.f};
  float ec_input_weight = ec.weight;
  ec.weight = 1.f;
  ec.l.simple = {route_label, 1., 0.f};
  base.learn(ec, b.nodes[cn].base_router);  // update the router according to the new example.

  base.predict(ec, b.nodes[cn].base_router);
  float save_binary_scalar = ec.pred.scalar;

  if (b.oas == false)
  {
    ec.l.multi = mc;
    ec.pred.multiclass = save_multi_pred;
  }
  else
  {
    ec.pred.multilabels = preds;
    ec.l.multilabels = multilabels;
  }
  ec.weight = ec_input_weight;

  return save_binary_scalar;
}

train_one_against_some_at_leaf()

void memory_tree_ns::train_one_against_some_at_leaf ( memory_tree &  b, single_learner &  base, const uint64_t  cn, example &  ec  )

inline

Definition at line 570 of file memory_tree.cc.

References collect_labels_from_leaf(), example::l, label_data::label, MULTILABEL::labels::label_v, LEARNER::learner< T, E >::learn(), memory_tree_ns::memory_tree::max_routers, prediction_type::multilabels, polylabel::multilabels, polyprediction::multilabels, example::pred, polylabel::simple, v_array< T >::size(), and v_array_contains().

Referenced by insert_example(), return_reward_from_node(), and single_query_and_learn().

{
  v_array<uint32_t> leaf_labs = v_init<uint32_t>();
  collect_labels_from_leaf(b, cn, leaf_labs);  // unique labels from the leaf.
  MULTILABEL::labels multilabels = ec.l.multilabels;
  MULTILABEL::labels preds = ec.pred.multilabels;
  ec.l.simple = {FLT_MAX, 1.f, 0.f};
  for (size_t i = 0; i < leaf_labs.size(); i++)
  {
    ec.l.simple.label = -1.f;
    if (v_array_contains(multilabels.label_v, leaf_labs[i]))
      ec.l.simple.label = 1.f;
    base.learn(ec, b.max_routers + 1 + leaf_labs[i]);
  }
  ec.pred.multilabels = preds;
  ec.l.multilabels = multilabels;
}

update_rew()

void memory_tree_ns::update_rew	(	memory_tree &	b,
		single_learner &	base,
		const uint32_t &	ec_array_index,
		example &	ec
	)

Definition at line 954 of file memory_tree.cc.

References single_query_and_learn().

Referenced by learn().

{
  single_query_and_learn(b, base, ec_array_index, ec);
}