SelectiveBranchingMT Namespace Reference

Classes
struct	task_data

Typedefs
typedef std::pair< action, float >	act_score
typedef v_array< act_score >	path
typedef std::pair< float, path >	branch

Functions
void	run (Search::search &sch, multi_ex &ec)
void	initialize (Search::search &sch, size_t &num_actions, options_i &options)
void	finish (Search::search &sch)
std::ostream &	operator<< (std::ostream &os, const std::pair< unsigned int, float > &v)

Variables
Search::search_metatask	metatask = {"selective_branching", run, initialize, finish, nullptr, nullptr}

Typedef Documentation

act_score

typedef std::pair<action, float> SelectiveBranchingMT::act_score

Definition at line 52 of file search_meta.cc.

branch

typedef std::pair<float, path> SelectiveBranchingMT::branch

Definition at line 54 of file search_meta.cc.

path

typedef v_array<act_score> SelectiveBranchingMT::path

Definition at line 53 of file search_meta.cc.

Function Documentation

finish()

void SelectiveBranchingMT::finish

(

Search::search &

sch

)

Definition at line 108 of file search_meta.cc.

References Search::search::get_metatask_data().

{ delete sch.get_metatask_data<task_data>(); }

initialize()

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

Definition at line 90 of file search_meta.cc.

References VW::config::option_group_definition::add(), VW::config::options_i::add_and_parse(), VW::config::make_option(), and Search::search::set_metatask_data().

{
  size_t max_branches = 2;
  size_t kbest = 0;
  option_group_definition new_options("selective branching options");
  new_options
      .add(make_option("search_max_branch", max_branches)
               .default_value(2)
               .help("maximum number of branches to consider"))
      .add(make_option("search_kbest", kbest)
               .default_value(0)
               .help("number of best items to output (0=just like non-selectional-branching, default)"));
  options.add_and_parse(new_options);

  task_data* d = new task_data(max_branches, kbest);
  sch.set_metatask_data(d);
}

operator<<()

std::ostream& SelectiveBranchingMT::operator<<	(	std::ostream &	os,
		const std::pair< unsigned int, float > &	v
	)

Definition at line 56 of file search_meta.cc.

{
  os << v.first << '_' << v.second;
  return os;
}

run()

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

Definition at line 110 of file search_meta.cc.

References a, Search::search::base_task(), v_array< T >::begin(), SelectiveBranchingMT::task_data::branches, cdbg, v_array< T >::clear(), copy_array(), SelectiveBranchingMT::task_data::cur_branch, v_array< T >::delete_v(), v_array< T >::end(), SelectiveBranchingMT::task_data::final, Search::BaseTask::foreach_action(), Search::search::get_metatask_data(), SelectiveBranchingMT::task_data::kbest, SelectiveBranchingMT::task_data::kbest_out, SelectiveBranchingMT::task_data::max_branches, SelectiveBranchingMT::task_data::output_string, v_array< T >::push_back(), Search::BaseTask::Run(), v_array< T >::size(), SelectiveBranchingMT::task_data::total_cost, and SelectiveBranchingMT::task_data::trajectory.

{
  task_data& d = *sch.get_metatask_data<task_data>();

  // generate an initial trajectory, but record possible branches
  d.branches.clear();
  d.final.clear();
  d.trajectory.clear();
  d.total_cost = 0.;
  d.output_string = nullptr;

  cdbg << "*** INITIAL PASS ***" << std::endl;
  sch.base_task(ec)
      .foreach_action([](Search::search& sch, size_t t, float min_cost, action a, bool taken, float a_cost) -> void {
        cdbg << "==DebugMT== foreach_action(t=" << t << ", min_cost=" << min_cost << ", a=" << a << ", taken=" << taken
             << ", a_cost=" << a_cost << ")" << std::endl;
        if (taken)
          return;  // ignore the taken action
        task_data& d = *sch.get_metatask_data<task_data>();
        float delta = a_cost - min_cost;
        path branch = v_init<act_score>();
        push_many<act_score>(branch, d.trajectory.begin(), d.trajectory.size());
        branch.push_back(std::make_pair(a, a_cost));
        d.branches.push_back(std::make_pair(delta, branch));
        cdbg << "adding branch: " << delta << " -> " << branch << std::endl;
      })
      .post_prediction([](Search::search& sch, size_t /*t*/, action a, float a_cost) -> void {
        task_data& d = *sch.get_metatask_data<task_data>();
        d.trajectory.push_back(std::make_pair(a, a_cost));
        d.total_cost += a_cost;
      })
      .with_output_string([](Search::search& sch, std::stringstream& output) -> void {
        sch.get_metatask_data<task_data>()->output_string = new std::string(output.str());
      })
      .Run();

  // the last item the trajectory stack is complete and therefore not a branch
  // if (! d.branches.empty())
  //  d.branches.pop().second.delete_v();

  {
    // construct the final trajectory
    path original_final = v_init<act_score>();
    copy_array(original_final, d.trajectory);
    d.final.push_back(std::make_pair(std::make_pair(d.total_cost, original_final), d.output_string));
  }

  // sort the branches by cost
  stable_sort(
      d.branches.begin(), d.branches.end(), [](const branch& a, const branch& b) -> bool { return a.first < b.first; });

  // make new predictions
  for (size_t i = 0; i < std::min(d.max_branches, d.branches.size()); i++)
  {
    d.cur_branch = i;
    d.trajectory.clear();
    d.total_cost = 0.;
    d.output_string = nullptr;

    cdbg << "*** BRANCH " << i << " *** " << d.branches[i].first << " : " << d.branches[i].second << std::endl;
    sch.base_task(ec)
        .foreach_action([](Search::search& /*sch*/, size_t /*t*/, float /*min_cost*/, action /*a*/, bool /*taken*/,
                            float /*a_cost*/) -> void {})
        .maybe_override_prediction([](Search::search& sch, size_t t, action& a, float& a_cost) -> bool {
          task_data& d = *sch.get_metatask_data<task_data>();
          path& path = d.branches[d.cur_branch].second;
          if (t >= path.size())
            return false;
          a = path[t].first;
          a_cost = path[t].second;
          return true;
        })
        .post_prediction([](Search::search& sch, size_t /*t*/, action a, float a_cost) -> void {
          task_data& d = *sch.get_metatask_data<task_data>();
          d.trajectory.push_back(std::make_pair(a, a_cost));
          d.total_cost += a_cost;
        })
        .with_output_string([](Search::search& sch, std::stringstream& output) -> void {
          sch.get_metatask_data<task_data>()->output_string = new std::string(output.str());
        })
        .Run();

    {
      // construct the final trajectory
      path this_final = v_init<act_score>();
      copy_array(this_final, d.trajectory);
      d.final.push_back(std::make_pair(std::make_pair(d.total_cost, this_final), d.output_string));
    }
  }

  // sort the finals by cost
  stable_sort(d.final.begin(), d.final.end(),
      [](const std::pair<branch, std::string*>& a, const std::pair<branch, std::string*>& b) -> bool {
        return a.first.first < b.first.first;
      });

  d.kbest_out = nullptr;
  if (d.output_string && (d.kbest > 0))
  {
    d.kbest_out = new std::stringstream();
    for (size_t i = 0; i < std::min(d.final.size(), d.kbest); i++)
      (*d.kbest_out) << *d.final[i].second << "\t" << d.final[i].first.first << std::endl;
  }

  // run the final selected trajectory
  cdbg << "*** FINAL ***" << std::endl;
  d.cur_branch = 0;
  d.output_string = nullptr;
  sch.base_task(ec)
      .foreach_action([](Search::search& /*sch*/, size_t /*t*/, float /*min_cost*/, action /*a*/, bool /*taken*/,
                          float /*a_cost*/) -> void {})
      .maybe_override_prediction([](Search::search& sch, size_t t, action& a, float& a_cost) -> bool {
        task_data& d = *sch.get_metatask_data<task_data>();
        path& path = d.final[d.cur_branch].first.second;
        if ((t >= path.size()) || (path[t].first == (action)-1))
          return false;
        a = path[t].first;
        a_cost = path[t].second;
        return true;
      })
      .with_output_string([](Search::search& sch, std::stringstream& output) -> void {
        task_data& d = *sch.get_metatask_data<task_data>();
        if (d.kbest_out)
        {
          output.str("");
          output << d.kbest_out->str();
        }
      })
      .final_run()
      .Run();

  // clean up memory
  for (size_t i = 0; i < d.branches.size(); i++) d.branches[i].second.delete_v();
  d.branches.clear();
  for (size_t i = 0; i < d.final.size(); i++)
  {
    d.final[i].first.second.delete_v();
    delete d.final[i].second;
  }
  d.final.clear();
  delete d.kbest_out;
  d.kbest_out = nullptr;
}

Variable Documentation

metatask

Search::search_metatask SelectiveBranchingMT::metatask = {"selective_branching", run, initialize, finish, nullptr, nullptr}

Definition at line 50 of file search_meta.cc.