GraphTask Namespace Reference

Classes
struct	task_data

Functions
bool	example_is_test (polylabel &l)
void	initialize (Search::search &sch, size_t &num_actions, options_i &options)
void	finish (Search::search &sch)
bool	example_is_edge (example *e)
void	run_bfs (task_data &D, multi_ex &ec)
void	setup (Search::search &sch, multi_ex &ec)
void	takedown (Search::search &sch, multi_ex &)
void	add_edge_features_group_fn (task_data &D, float fv, uint64_t fx)
void	add_edge_features_single_fn (task_data &D, float fv, uint64_t fx)
void	add_edge_features (Search::search &sch, task_data &D, size_t n, multi_ex &ec)
void	del_edge_features (task_data &, uint32_t n, multi_ex &ec)
float	macro_f (task_data &D)
void	run (Search::search &sch, multi_ex &ec)

Variables
Search::search_task	task = {"graph", run, initialize, finish, setup, takedown}

Function Documentation

add_edge_features()

void GraphTask::add_edge_features	(	Search::search &	sch,
		task_data &	D,
		size_t	n,
		multi_ex &	ec
	)

Definition at line 271 of file search_graph.cc.

References GraphTask::task_data::adj, GraphTask::task_data::cur_node, GraphTask::task_data::directed, Search::search::get_vw_pointer_unsafe(), GraphTask::task_data::K, neighbor_namespace, GraphTask::task_data::neighbor_predictions, GraphTask::task_data::numN, vw::pairs, GraphTask::task_data::pred, and GraphTask::task_data::use_structure.

Referenced by run().

{
  D.cur_node = ec[n];

  for (size_t i : D.adj[n])
  {
    for (size_t k = 0; k < D.numN; k++) D.neighbor_predictions[k] = 0.;

    float pred_total = 0.;
    uint32_t last_pred = 0;
    if (D.use_structure)
    {
      bool n_in_sink = true;
      if (D.directed)
        for (size_t j = 0; j < ec[i]->l.cs.costs.size() - 1; j++)
        {
          size_t m = ec[i]->l.cs.costs[j].class_index;
          if (m == 0)
            break;
          if (m - 1 == n)
          {
            n_in_sink = false;
            break;
          }
        }

      bool m_in_sink = false;
      for (size_t j = 0; j < ec[i]->l.cs.costs.size(); j++)
      {
        size_t m = ec[i]->l.cs.costs[j].class_index;
        if (m == 0)
        {
          m_in_sink = true;
          continue;
        }
        if (j == ec[i]->l.cs.costs.size() - 1)
          m_in_sink = true;
        m--;
        if (m == n)
          continue;
        size_t other_side = (D.directed && (n_in_sink != m_in_sink)) ? (D.K + 1) : 0;
        D.neighbor_predictions[D.pred[m] - 1 + other_side] += 1.;
        pred_total += 1.;
        last_pred = (uint32_t)D.pred[m] - 1 + (uint32_t)other_side;
      }
    }
    else
    {
      D.neighbor_predictions[0] += 1.;
      pred_total += 1.;
      last_pred = 0;
    }

    if (pred_total == 0.)
      continue;
    // std::cerr << n << ':' << i << " -> ["; for (size_t k=0; k<D.numN; k++) std::cerr << ' ' <<
    // D.neighbor_predictions[k]; std::cerr
    // << " ]" << std::endl;
    for (size_t k = 0; k < D.numN; k++) D.neighbor_predictions[k] /= pred_total;
    example& edge = *ec[i];

    if (pred_total <= 1.)  // single edge
    {
      D.neighbor_predictions[0] = (float)last_pred;
      GD::foreach_feature<task_data, uint64_t, add_edge_features_single_fn>(sch.get_vw_pointer_unsafe(), edge, D);
    }
    else  // lots of edges
      GD::foreach_feature<task_data, uint64_t, add_edge_features_group_fn>(sch.get_vw_pointer_unsafe(), edge, D);
  }
  ec[n]->indices.push_back(neighbor_namespace);
  ec[n]->total_sum_feat_sq += ec[n]->feature_space[neighbor_namespace].sum_feat_sq;
  ec[n]->num_features += ec[n]->feature_space[neighbor_namespace].size();

  vw& all = sch.get_vw_pointer_unsafe();
  for (std::string& i : all.pairs)
  {
    int i0 = (int)i[0];
    int i1 = (int)i[1];
    if ((i0 == (int)neighbor_namespace) || (i1 == (int)neighbor_namespace))
    {
      ec[n]->num_features += ec[n]->feature_space[i0].size() * ec[n]->feature_space[i1].size();
      ec[n]->total_sum_feat_sq += ec[n]->feature_space[i0].sum_feat_sq * ec[n]->feature_space[i1].sum_feat_sq;
    }
  }
}

add_edge_features_group_fn()

void GraphTask::add_edge_features_group_fn	(	task_data &	D,
		float	fv,
		uint64_t	fx
	)

Definition at line 249 of file search_graph.cc.

References GraphTask::task_data::cur_node, example_predict::feature_space, GraphTask::task_data::mask, GraphTask::task_data::multiplier, neighbor_namespace, GraphTask::task_data::neighbor_predictions, and GraphTask::task_data::numN.

{
  example* node = D.cur_node;
  uint64_t fx2 = fx / (uint64_t)D.multiplier;
  for (size_t k = 0; k < D.numN; k++)
  {
    if (D.neighbor_predictions[k] == 0.)
      continue;
    node->feature_space[neighbor_namespace].push_back(
        fv * D.neighbor_predictions[k], (uint64_t)((fx2 + 348919043 * k) * D.multiplier) & (uint64_t)D.mask);
  }
}

add_edge_features_single_fn()

void GraphTask::add_edge_features_single_fn	(	task_data &	D,
		float	fv,
		uint64_t	fx
	)

Definition at line 262 of file search_graph.cc.

References GraphTask::task_data::cur_node, example_predict::feature_space, GraphTask::task_data::mask, GraphTask::task_data::multiplier, neighbor_namespace, GraphTask::task_data::neighbor_predictions, and features::push_back().

{
  example* node = D.cur_node;
  features& fs = node->feature_space[neighbor_namespace];
  uint64_t fx2 = fx / (uint64_t)D.multiplier;
  size_t k = (size_t)D.neighbor_predictions[0];
  fs.push_back(fv, (uint32_t)((fx2 + 348919043 * k) * D.multiplier) & (uint64_t)D.mask);
}

del_edge_features()

void GraphTask::del_edge_features	(	task_data &	,
		uint32_t	n,
		multi_ex &	ec
	)

Definition at line 357 of file search_graph.cc.

References features::clear(), neighbor_namespace, features::size(), and features::sum_feat_sq.

Referenced by run().

{
  ec[n]->indices.pop();
  features& fs = ec[n]->feature_space[neighbor_namespace];
  ec[n]->total_sum_feat_sq -= fs.sum_feat_sq;
  ec[n]->num_features -= fs.size();
  fs.clear();
}

example_is_edge()

bool GraphTask::example_is_edge ( example *  e )

inline

Definition at line 145 of file search_graph.cc.

References COST_SENSITIVE::label::costs, polylabel::cs, and example::l.

Referenced by setup().

{ return e->l.cs.costs.size() > 1; }

example_is_test()

bool GraphTask::example_is_test ( polylabel &  l )

inline

Definition at line 94 of file search_graph.cc.

References COST_SENSITIVE::label::costs, and polylabel::cs.

Referenced by initialize().

{ return l.cs.costs.size() == 0; }

finish()

void GraphTask::finish

(

Search::search &

sch

)

Definition at line 136 of file search_graph.cc.

References GraphTask::task_data::confusion_matrix, Search::search::get_task_data(), GraphTask::task_data::neighbor_predictions, and GraphTask::task_data::true_counts.

{
  task_data* D = sch.get_task_data<task_data>();
  free(D->neighbor_predictions);
  free(D->confusion_matrix);
  free(D->true_counts);
  delete D;
}

initialize()

void GraphTask::initialize	(	Search::search &	sch,
		size_t &	num_actions,
		options_i &	options
	)

Definition at line 96 of file search_graph.cc.

References VW::config::option_group_definition::add(), add(), VW::config::options_i::add_and_parse(), GraphTask::task_data::confusion_matrix, COST_SENSITIVE::cs_label, GraphTask::task_data::directed, example_is_test(), GraphTask::task_data::K, VW::config::make_option(), GraphTask::task_data::neighbor_predictions, GraphTask::task_data::num_loops, GraphTask::task_data::numN, GraphTask::task_data::separate_learners, Search::search::set_label_parser(), Search::search::set_num_learners(), Search::search::set_options(), Search::search::set_task_data(), GraphTask::task_data::true_counts, GraphTask::task_data::true_counts_total, and GraphTask::task_data::use_structure.

{
  task_data* D = new task_data();

  option_group_definition new_options("search graphtask options");
  new_options
      .add(make_option("search_graph_num_loops", D->num_loops).default_value(2).help("how many loops to run [def: 2]"))
      .add(make_option("search_graph_no_structure", D->use_structure).help("turn off edge features"))
      .add(make_option("search_graph_separate_learners", D->separate_learners)
               .help("use a different learner for each pass"))
      .add(make_option("search_graph_directed", D->directed)
               .help("construct features based on directed graph semantics"));
  options.add_and_parse(new_options);

  D->use_structure = !D->use_structure;

  if (D->num_loops <= 1)
  {
    D->num_loops = 1;
    D->separate_learners = false;
  }

  D->K = num_actions;
  D->numN = (D->directed + 1) * (D->K + 1);
  std::cerr << "K=" << D->K << ", numN=" << D->numN << std::endl;
  D->neighbor_predictions = calloc_or_throw<float>(D->numN);

  D->confusion_matrix = calloc_or_throw<uint32_t>((D->K + 1) * (D->K + 1));
  D->true_counts = calloc_or_throw<float>(D->K + 1);
  D->true_counts_total = (float)(D->K + 1);
  for (size_t k = 0; k <= D->K; k++) D->true_counts[k] = 1.;

  if (D->separate_learners)
    sch.set_num_learners(D->num_loops);

  sch.set_task_data<task_data>(D);
  sch.set_options(0);  // Search::AUTO_HAMMING_LOSS
  sch.set_label_parser(COST_SENSITIVE::cs_label, example_is_test);
}

macro_f()

float GraphTask::macro_f

(

task_data &

D

)

Definition at line 368 of file search_graph.cc.

References GraphTask::task_data::confusion_matrix, IDX, and GraphTask::task_data::K.

Referenced by run().

{
  float total_f1 = 0.;
  float count_f1 = 0.;
  for (size_t k = 1; k <= D.K; k++)
  {
    float trueC = 0.;
    float predC = 0.;
    for (size_t j = 1; j <= D.K; j++)
    {
      trueC += (float)D.confusion_matrix[IDX(k, j)];
      predC += (float)D.confusion_matrix[IDX(j, k)];
    }
    if (trueC == 0)
      continue;
    float correctC = (float)D.confusion_matrix[IDX(k, k)];
    count_f1++;
    if (correctC > 0)
    {
      float pre = correctC / predC;
      float rec = correctC / trueC;
      total_f1 += 2 * pre * rec / (pre + rec);
    }
  }
  return total_f1 / count_f1;
}

run()

void GraphTask::run	(	Search::search &	sch,
		multi_ex &	ec
	)

Definition at line 395 of file search_graph.cc.

References Search::predictor::add_condition(), add_edge_features(), GraphTask::task_data::adj, GraphTask::task_data::bfs, GraphTask::task_data::confusion_matrix, del_edge_features(), f, Search::search::get_task_data(), IDX, GraphTask::task_data::K, Search::search::loss(), macro_f(), GraphTask::task_data::N, GraphTask::task_data::num_loops, Search::search::output(), GraphTask::task_data::pred, Search::predictor::predict(), Search::search::predictNeedsExample(), GraphTask::task_data::separate_learners, Search::predictor::set_input(), Search::predictor::set_learner_id(), Search::predictor::set_oracle(), Search::predictor::set_weight(), and GraphTask::task_data::true_counts.

{
  task_data& D = *sch.get_task_data<task_data>();
  float loss_val = 0.5f / (float)D.num_loops;
  for (size_t n = 0; n < D.N; n++) D.pred[n] = D.K + 1;

  for (size_t loop = 0; loop < D.num_loops; loop++)
  {
    bool last_loop = loop == (D.num_loops - 1);
    int start = 0;
    int end = D.N;
    int step = 1;
    if (loop % 2 == 1)
    {
      start = D.N - 1;
      end = -1;
      step = -1;
    }  // go inward on odd loops
    for (int n_id = start; n_id != end; n_id += step)
    {
      uint32_t n = D.bfs[n_id];
      uint32_t k = (ec[n]->l.cs.costs.size() > 0) ? ec[n]->l.cs.costs[0].class_index : 0;

      bool add_features = /* D.use_structure && */ sch.predictNeedsExample();
      // add_features = false;

      if (add_features)
        add_edge_features(sch, D, n, ec);
      Search::predictor P = Search::predictor(sch, n + 1);
      P.set_input(*ec[n]);
      if (false && (k > 0))
      {
        float min_count = 1e12f;
        for (size_t k2 = 1; k2 <= D.K; k2++) min_count = std::min(min_count, D.true_counts[k2]);
        float w = min_count / D.true_counts[k];
        // float w = D.true_counts_total / D.true_counts[k] / (float)(D.K);
        P.set_weight(w);
        // std::cerr << "w = " << D.true_counts_total / D.true_counts[k] / (float)(D.K) << std::endl;
        // P.set_weight( D.true_counts_total / D.true_counts[k] / (float)(D.K) );
      }
      if (D.separate_learners)
        P.set_learner_id(loop);
      if (k > 0)  // for test examples
        P.set_oracle(k);
      // add all the conditioning
      for (size_t i = 0; i < D.adj[n].size(); i++)
      {
        for (size_t j = 0; j < ec[i]->l.cs.costs.size(); j++)
        {
          uint32_t m = ec[i]->l.cs.costs[j].class_index;
          if (m == 0)
            continue;
          m--;
          if (m == n)
            continue;
          P.add_condition(m + 1, 'e');
        }
      }

      // make the prediction
      D.pred[n] = P.predict();
      if (ec[n]->l.cs.costs.size() > 0)  // for test examples
        sch.loss((ec[n]->l.cs.costs[0].class_index == D.pred[n]) ? 0.f : (last_loop ? 0.5f : loss_val));

      if (add_features)
        del_edge_features(D, n, ec);
    }
  }

  for (uint32_t n = 0; n < D.N; n++) D.confusion_matrix[IDX(ec[n]->l.cs.costs[0].class_index, D.pred[n])]++;
  sch.loss(1.f - macro_f(D));

  if (sch.output().good())
    for (uint32_t n = 0; n < D.N; n++) sch.output() << D.pred[n] << ' ';
}

run_bfs()

void GraphTask::run_bfs	(	task_data &	D,
		multi_ex &	ec
	)

Definition at line 147 of file search_graph.cc.

References GraphTask::task_data::adj, GraphTask::task_data::bfs, id(), and GraphTask::task_data::N.

Referenced by setup().

{
  D.bfs.clear();
  std::vector<bool> touched;
  for (size_t n = 0; n < D.N; n++) touched.push_back(false);

  touched[0] = true;
  D.bfs.push_back(0);

  size_t i = 0;
  while (D.bfs.size() < D.N)
  {
    while (i < D.bfs.size())
    {
      uint32_t n = D.bfs[i];
      for (size_t id : D.adj[n])
        for (size_t j = 0; j < ec[id]->l.cs.costs.size(); j++)
        {
          uint32_t m = ec[id]->l.cs.costs[j].class_index;
          if ((m > 0) && (!touched[m - 1]))
          {
            D.bfs.push_back(m - 1);
            touched[m - 1] = true;
          }
        }
      i++;
    }

    if (D.bfs.size() < D.N)
      // we finished a SCC, need to find another
      for (uint32_t n = 0; n < D.N; n++)
        if (!touched[n])
        {
          touched[n] = true;
          D.bfs.push_back(n);
          break;
        }
  }
}

setup()

void GraphTask::setup	(	Search::search &	sch,
		multi_ex &	ec
	)

Definition at line 187 of file search_graph.cc.

References GraphTask::task_data::E, example_is_edge(), Search::search::get_task_data(), Search::search::get_vw_pointer_unsafe(), GraphTask::task_data::mask, parameters::mask(), GraphTask::task_data::multiplier, GraphTask::task_data::N, run_bfs(), GraphTask::task_data::ss, parameters::stride_shift(), THROW, GraphTask::task_data::true_counts, GraphTask::task_data::true_counts_total, vw::weights, GraphTask::task_data::wpp, and vw::wpp.

{
  task_data& D = *sch.get_task_data<task_data>();
  D.multiplier = D.wpp << D.ss;
  D.wpp = sch.get_vw_pointer_unsafe().wpp;
  D.mask = sch.get_vw_pointer_unsafe().weights.mask();
  D.ss = sch.get_vw_pointer_unsafe().weights.stride_shift();
  D.N = 0;
  D.E = 0;
  for (size_t i = 0; i < ec.size(); i++)
    if (example_is_edge(ec[i]))
      D.E++;
    else  // it's a node!
    {
      if (D.E > 0)
        THROW("error: got a node after getting edges!");

      D.N++;
      if (ec[i]->l.cs.costs.size() > 0)
      {
        D.true_counts[ec[i]->l.cs.costs[0].class_index] += 1.;
        D.true_counts_total += 1.;
      }
    }

  if ((D.N == 0) && (D.E > 0))
    THROW("error: got edges without any nodes (perhaps ring_size is too small?)!");

  D.adj = std::vector<std::vector<size_t>>(D.N, std::vector<size_t>(0));

  for (size_t i = D.N; i < ec.size(); i++)
  {
    for (size_t n = 0; n < ec[i]->l.cs.costs.size(); n++)
    {
      if (ec[i]->l.cs.costs[n].class_index > D.N)
        THROW("error: edge source points to too large of a node id: " << (ec[i]->l.cs.costs[n].class_index) << " > "
                                                                      << D.N);
    }
    for (size_t n = 0; n < ec[i]->l.cs.costs.size(); n++)
    {
      size_t nn = ec[i]->l.cs.costs[n].class_index;
      if ((nn > 0) &&
          (((D.adj[nn - 1].size() == 0) || (D.adj[nn - 1][D.adj[nn - 1].size() - 1] != i))))  // don't allow dups
        D.adj[nn - 1].push_back(i);
    }
  }

  run_bfs(D, ec);

  D.pred.clear();
  for (size_t n = 0; n < D.N; n++) D.pred.push_back(D.K + 1);
}

takedown()

void GraphTask::takedown	(	Search::search &	sch,
		multi_ex &
	)

Definition at line 240 of file search_graph.cc.

References GraphTask::task_data::adj, GraphTask::task_data::bfs, Search::search::get_task_data(), and GraphTask::task_data::pred.

{
  task_data& D = *sch.get_task_data<task_data>();
  D.bfs.clear();
  D.pred.clear();
  for (auto x : D.adj) x.clear();
  D.adj.clear();
}

Variable Documentation

task

Search::search_task GraphTask::task = {"graph", run, initialize, finish, setup, takedown}

Definition at line 63 of file search_graph.cc.