Classes
struct	action_cache

struct	action_repr

struct	auto_condition_settings

class	BaseTask

struct	final_item

struct	prediction

class	predictor

struct	scored_action

struct	search

struct	search_metatask

struct	search_private

struct	search_task

Enumerations
enum	SearchState { INITIALIZE, INIT_TEST, INIT_TRAIN, LEARN, GET_TRUTH_STRING }

enum	RollMethod { POLICY, ORACLE, MIX_PER_STATE, MIX_PER_ROLL, NO_ROLLOUT }

Functions
std::string	neighbor_feature_space ("neighbor")

std::string	condition_feature_space ("search_condition")

std::ostream &	operator<< (std::ostream &os, const scored_action &x)

std::ostream &	operator<< (std::ostream &os, const action_cache &x)

void	free_key (unsigned char *mem, scored_action)

void	clear_cache_hash_map (search_private &priv)

void	clear_memo_foreach_action (search_private &priv)

std::string	audit_feature_space ("conditional")

bool	need_memo_foreach_action (search_private &priv)

int	random_policy (search_private &priv, bool allow_current, bool allow_optimal, bool advance_prng=true)

int	select_learner (search_private &priv, int policy, size_t learner_id, bool is_training, bool is_local)

bool	should_print_update (vw &all, bool hit_new_pass=false)

bool	might_print_update (vw &all)

bool	must_run_test (vw &all, multi_ex &ec, bool is_test_ex)

float	safediv (float a, float b)

void	to_short_string (std::string in, size_t max_len, char *out)

std::string	number_to_natural (size_t big)

void	print_update (search_private &priv)

void	add_new_feature (search_private &priv, float val, uint64_t idx)

void	del_features_in_top_namespace (search_private &, example &ec, size_t ns)

void	add_neighbor_features (search_private &priv, multi_ex &ec_seq)

void	del_neighbor_features (search_private &priv, multi_ex &ec_seq)

void	reset_search_structure (search_private &priv)

void	search_declare_loss (search_private &priv, float loss)

template<class T >
void	cdbg_print_array (std::string str, v_array< T > &A)

template<class T >
void	cerr_print_array (std::string str, v_array< T > &A)

size_t	random (std::shared_ptr< rand_state > &rs, size_t max)

template<class T >
bool	array_contains (T target, const T *A, size_t n)

void	add_example_conditioning (search_private &priv, example &ec, size_t condition_on_cnt, const char condition_on_names, action_repr condition_on_actions)

void	del_example_conditioning (search_private &priv, example &ec)

size_t	cs_get_costs_size (bool isCB, polylabel &ld)

uint32_t	cs_get_cost_index (bool isCB, polylabel &ld, size_t k)

float	cs_get_cost_partial_prediction (bool isCB, polylabel &ld, size_t k)

void	cs_set_cost_loss (bool isCB, polylabel &ld, size_t k, float val)

void	cs_costs_erase (bool isCB, polylabel &ld)

void	cs_costs_resize (bool isCB, polylabel &ld, size_t new_size)

void	cs_cost_push_back (bool isCB, polylabel &ld, uint32_t index, float value)

polylabel &	allowed_actions_to_ld (search_private &priv, size_t ec_cnt, const action allowed_actions, size_t allowed_actions_cnt, const float allowed_actions_cost)

void	allowed_actions_to_label (search_private &priv, size_t ec_cnt, const action allowed_actions, size_t allowed_actions_cnt, const float allowed_actions_cost, const action *oracle_actions, size_t oracle_actions_cnt, polylabel &lab)

template<class T >
void	ensure_size (v_array< T > &A, size_t sz)

template<class T >
void	push_at (v_array< T > &v, T item, size_t pos)

action	choose_oracle_action (search_private &priv, size_t ec_cnt, const action oracle_actions, size_t oracle_actions_cnt, const action allowed_actions, size_t allowed_actions_cnt, const float *allowed_actions_cost)

action	single_prediction_notLDF (search_private &priv, example &ec, int policy, const action allowed_actions, size_t allowed_actions_cnt, const float allowed_actions_cost, float &a_cost, action override_action)

action	single_prediction_LDF (search_private &priv, example *ecs, size_t ec_cnt, int policy, float &a_cost, action override_action)

int	choose_policy (search_private &priv, bool advance_prng=true)

bool	cached_item_equivalent (unsigned char const &A, unsigned char const &B)

bool	cached_action_store_or_find (search_private &priv, ptag mytag, const ptag condition_on, const char condition_on_names, action_repr *condition_on_actions, size_t condition_on_cnt, int policy, size_t learner_id, action &a, bool do_store, float &a_cost)

void	generate_training_example (search_private &priv, polylabel &losses, float weight, bool add_conditioning=true, float min_loss=FLT_MAX)

bool	search_predictNeedsExample (search_private &priv)

void	foreach_action_from_cache (search_private &priv, size_t t, action override_a=(action) -1)

action	search_predict (search_private &priv, example ecs, size_t ec_cnt, ptag mytag, const action oracle_actions, size_t oracle_actions_cnt, const ptag condition_on, const char condition_on_names, const action allowed_actions, size_t allowed_actions_cnt, const float allowed_actions_cost, size_t learner_id, float &a_cost, float)

bool	cmp_size_t (const size_t a, const size_t b)

bool	cmp_size_t_pair (const std::pair< size_t, size_t > &a, const std::pair< size_t, size_t > &b)

size_t	absdiff (size_t a, size_t b)

void	hoopla_permute (size_t B, size_t end)

void	get_training_timesteps (search_private &priv, v_array< size_t > &timesteps)

void	free_final_item (final_item *p)

void	run_task (search &sch, multi_ex &ec)

void	verify_active_csoaa (COST_SENSITIVE::label &losses, v_array< std::pair< CS::wclass &, bool >> &known, size_t t, float multiplier)

void	advance_from_known_actions (search_private &priv)

template<bool is_learn>
void	train_single_example (search &sch, bool is_test_ex, bool is_holdout_ex, multi_ex &ec_seq)

void	adjust_auto_condition (search_private &priv)

template<bool is_learn>
void	do_actual_learning (search &sch, base_learner &base, multi_ex &ec_seq)

void	end_pass (search &sch)

void	finish_multiline_example (vw &all, search &sch, multi_ex &ec_seq)

void	end_examples (search &sch)

bool	mc_label_is_test (polylabel &lab)

void	search_initialize (vw *all, search &sch)

void	ensure_param (float &v, float lo, float hi, float def, const char *str)

void	handle_condition_options (vw &all, auto_condition_settings &acset)

void	search_finish (search &sch)

v_array< CS::label >	read_allowed_transitions (action A, const char *filename)

void	parse_neighbor_features (std::string &nf_string, search &sch)

base_learner *	setup (options_i &options, vw &all)

float	action_hamming_loss (action a, const action *A, size_t sz)

float	action_cost_loss (action a, const action act, const float costs, size_t sz)

bool	string_equal (std::string a, std::string b)

bool	float_equal (float a, float b)

bool	uint32_equal (uint32_t a, uint32_t b)

bool	size_equal (size_t a, size_t b)

Variables
search_task *	all_tasks []

search_metatask *	all_metatasks []

constexpr bool	PRINT_UPDATE_EVERY_EXAMPLE = false

constexpr bool	PRINT_UPDATE_EVERY_PASS = false

constexpr bool	PRINT_CLOCK_TIME = false

uint32_t	AUTO_CONDITION_FEATURES = 1

uint32_t	AUTO_HAMMING_LOSS = 2

uint32_t	EXAMPLES_DONT_CHANGE = 4

uint32_t	IS_LDF = 8

uint32_t	NO_CACHING = 16

uint32_t	ACTION_COSTS = 32

uint64_t	conditional_constant = 8290743

Enumeration Type Documentation

◆ RollMethod

enum Search::RollMethod

Enumerator
POLICY
ORACLE
MIX_PER_STATE
MIX_PER_ROLL
NO_ROLLOUT

Definition at line 59 of file search.cc.

 {
   POLICY,
   ORACLE,
   MIX_PER_STATE,
   MIX_PER_ROLL,
   NO_ROLLOUT
 };

◆ SearchState

enum Search::SearchState

Enumerator
INITIALIZE
INIT_TEST
INIT_TRAIN
LEARN
GET_TRUTH_STRING

Definition at line 51 of file search.cc.

 {
   INITIALIZE,
   INIT_TEST,
   INIT_TRAIN,
   LEARN,
   GET_TRUTH_STRING
 };

Function Documentation

◆ absdiff()

size_t Search::absdiff	(	size_t	a,
		size_t	b
	)

inline

Definition at line 1946 of file search.cc.

References a.

Referenced by average_diff(), and hoopla_permute().

1946 { return (a < b) ? (b - a) : (a - b); }

a

constexpr uint64_t a

Definition: rand48.cc:11

◆ action_cost_loss()

float Search::action_cost_loss	(	action	a,
		const action *	act,
		const float *	costs,
		size_t	sz
	)

Definition at line 2954 of file search.cc.

References THROW.

Referenced by Search::search::predict().

 {
   if (act == nullptr)
     return costs[a - 1];
   for (size_t i = 0; i < sz; i++)
     if (act[i] == a)
       return costs[i];
   THROW("action_cost_loss got action that wasn't allowed: " << a);
 }

◆ action_hamming_loss()

float Search::action_hamming_loss	(	action	a,
		const action *	A,
		size_t	sz
	)

Definition at line 2944 of file search.cc.

Referenced by Search::search::predict(), and Search::search::predictLDF().

 {
   if (sz == 0)
     return 0.;  // latent variables have zero loss
   for (size_t i = 0; i < sz; i++)
     if (a == A[i])
       return 0.;
   return 1.;
 }

◆ add_example_conditioning()

void Search::add_example_conditioning	(	search_private &	priv,
		example &	ec,
		size_t	condition_on_cnt,
		const char *	condition_on_names,
		action_repr *	condition_on_actions
	)

Definition at line 784 of file search.cc.

Referenced by generate_training_example(), and search_predict().

 {
   if (condition_on_cnt == 0)
     return;
 
   uint64_t extra_offset = 0;
   if (priv.is_ldf)
     if (ec.l.cs.costs.size() > 0)
       extra_offset = 3849017 * ec.l.cs.costs[0].class_index;
 
   size_t I = condition_on_cnt;
   size_t N = std::max(priv.acset.max_bias_ngram_length, priv.acset.max_quad_ngram_length);
   for (size_t i = 0; i < I; i++)  // position in conditioning
   {
     uint64_t fid = 71933 + 8491087 * extra_offset;
     if (priv.all->audit)
     {
       priv.dat_new_feature_audit_ss.str("");
       priv.dat_new_feature_audit_ss.clear();
       priv.dat_new_feature_feature_space = &condition_feature_space;
     }
 
     for (size_t n = 0; n < N; n++)  // length of ngram
     {
       if (i + n >= I)
         break;  // no more ngrams
       // we're going to add features for the ngram condition_on_actions[i .. i+N]
       uint64_t name = condition_on_names[i + n];
       fid = fid * 328901 + 71933 * ((condition_on_actions[i + n].a + 349101) * (name + 38490137));
 
       priv.dat_new_feature_ec = &ec;
       priv.dat_new_feature_idx = fid * quadratic_constant;
       priv.dat_new_feature_namespace = conditioning_namespace;
       priv.dat_new_feature_value = priv.acset.feature_value;
 
       if (priv.all->audit)
       {
         if (n > 0)
           priv.dat_new_feature_audit_ss << ',';
         if ((33 <= name) && (name <= 126))
           priv.dat_new_feature_audit_ss << name;
         else
           priv.dat_new_feature_audit_ss << '#' << (int)name;
         priv.dat_new_feature_audit_ss << '=' << condition_on_actions[i + n].a;
       }
 
       // add the single bias feature
       if (n < priv.acset.max_bias_ngram_length)
         add_new_feature(priv, 1., (uint64_t)4398201 << priv.all->weights.stride_shift());
       // add the quadratic features
       if (n < priv.acset.max_quad_ngram_length)
         GD::foreach_feature<search_private, uint64_t, add_new_feature>(*priv.all, ec, priv);
     }
   }
 
   if (priv.acset.use_passthrough_repr)
   {
     cdbg << "BEGIN adding passthrough features" << endl;
     for (size_t i = 0; i < I; i++)
     {
       if (condition_on_actions[i].repr == nullptr)
         continue;
       features& fs = *(condition_on_actions[i].repr);
       char name = condition_on_names[i];
       for (size_t k = 0; k < fs.size(); k++)
         if ((fs.values[k] > 1e-10) || (fs.values[k] < -1e-10))
         {
           uint64_t fid = 84913 + 48371803 * (extra_offset + 8392817 * name) + 840137 * (4891 + fs.indicies[k]);
           if (priv.all->audit)
           {
             priv.dat_new_feature_audit_ss.str("");
             priv.dat_new_feature_audit_ss.clear();
             priv.dat_new_feature_audit_ss << "passthrough_repr_" << i << '_' << k;
           }
 
           priv.dat_new_feature_ec = &ec;
           priv.dat_new_feature_idx = fid;
           priv.dat_new_feature_namespace = conditioning_namespace;
           priv.dat_new_feature_value = fs.values[k];
           add_new_feature(priv, 1., (uint64_t)4398201 << priv.all->weights.stride_shift());
         }
     }
     cdbg << "END adding passthrough features" << endl;
   }
 
   features& con_fs = ec.feature_space[conditioning_namespace];
   if ((con_fs.size() > 0) && (con_fs.sum_feat_sq > 0.))
   {
     ec.indices.push_back(conditioning_namespace);
     ec.total_sum_feat_sq += con_fs.sum_feat_sq;
     ec.num_features += con_fs.size();
   }
   else
     con_fs.clear();
 }

◆ add_neighbor_features()

void Search::add_neighbor_features	(	search_private &	priv,
		multi_ex &	ec_seq
	)

Definition at line 631 of file search.cc.

Referenced by do_actual_learning().

 {
   if (priv.neighbor_features.size() == 0)
     return;
 
   uint32_t stride_shift = priv.all->weights.stride_shift();
   for (size_t n = 0; n < ec_seq.size(); n++)  // iterate over every example in the sequence
   {
     example& me = *ec_seq[n];
     for (size_t n_id = 0; n_id < priv.neighbor_features.size(); n_id++)
     {
       int32_t offset = priv.neighbor_features[n_id] >> 24;
       size_t ns = priv.neighbor_features[n_id] & 0xFF;
 
       priv.dat_new_feature_ec = &me;
       priv.dat_new_feature_value = 1.;
       priv.dat_new_feature_idx = priv.neighbor_features[n_id] * 13748127;
       priv.dat_new_feature_namespace = neighbor_namespace;
       if (priv.all->audit)
       {
         priv.dat_new_feature_feature_space = &neighbor_feature_space;
         priv.dat_new_feature_audit_ss.str("");
         priv.dat_new_feature_audit_ss << '@' << ((offset > 0) ? '+' : '-') << (char)(abs(offset) + '0');
         if (ns != ' ')
           priv.dat_new_feature_audit_ss << (char)ns;
       }
 
       // std::cerr << "n=" << n << " offset=" << offset << endl;
       if ((offset < 0) && (n < (uint64_t)(-offset)))  // add <s> feature
         add_new_feature(priv, 1., (uint64_t)925871901 << stride_shift);
       else if (n + offset >= ec_seq.size())  // add </s> feature
         add_new_feature(priv, 1., (uint64_t)3824917 << stride_shift);
       else  // this is actually a neighbor
       {
         example& other = *ec_seq[n + offset];
         GD::foreach_feature<search_private, add_new_feature>(priv.all, other.feature_space[ns], priv, me.ft_offset);
       }
     }
 
     features& fs = me.feature_space[neighbor_namespace];
     size_t sz = fs.size();
     if ((sz > 0) && (fs.sum_feat_sq > 0.))
     {
       me.indices.push_back(neighbor_namespace);
       me.total_sum_feat_sq += fs.sum_feat_sq;
       me.num_features += sz;
     }
     else
       fs.clear();
   }
 }

◆ add_new_feature()

void Search::add_new_feature	(	search_private &	priv,
		float	val,
		uint64_t	idx
	)

Definition at line 596 of file search.cc.

References Search::search_private::all, vw::audit, cdbg, Search::search_private::dat_new_feature_audit_ss, Search::search_private::dat_new_feature_ec, Search::search_private::dat_new_feature_feature_space, Search::search_private::dat_new_feature_idx, Search::search_private::dat_new_feature_namespace, Search::search_private::dat_new_feature_value, example_predict::feature_space, features::indicies, v_array< T >::last(), parameters::mask(), v_array< T >::push_back(), features::push_back(), features::space_names, parameters::stride_shift(), features::values, and vw::weights.

Referenced by add_example_conditioning(), and add_neighbor_features().

 {
   uint64_t mask = priv.all->weights.mask();
   size_t ss = priv.all->weights.stride_shift();
 
   uint64_t idx2 = ((idx & mask) >> ss) & mask;
   features& fs = priv.dat_new_feature_ec->feature_space[priv.dat_new_feature_namespace];
   fs.push_back(val * priv.dat_new_feature_value, ((priv.dat_new_feature_idx + idx2) << ss));
   cdbg << "adding: " << fs.indicies.last() << ':' << fs.values.last() << endl;
   if (priv.all->audit)
   {
     std::stringstream temp;
     temp << "fid=" << ((idx & mask) >> ss) << "_" << priv.dat_new_feature_audit_ss.str();
     fs.space_names.push_back(audit_strings_ptr(new audit_strings(*priv.dat_new_feature_feature_space, temp.str())));
   }
 }

◆ adjust_auto_condition()

void Search::adjust_auto_condition ( search_private & priv )

inline

Definition at line 2364 of file search.cc.

References Search::search_private::acset, Search::search_private::auto_condition_features, Search::auto_condition_settings::feature_value, and Search::search_private::history_length.

Referenced by do_actual_learning().

 {
   if (priv.auto_condition_features)
   {
     // turn off auto-condition if it's irrelevant
     if ((priv.history_length == 0) || (priv.acset.feature_value == 0.f))
     {
       std::cerr << "warning: turning off AUTO_CONDITION_FEATURES because settings make it useless" << endl;
       priv.auto_condition_features = false;
     }
   }
 }

◆ advance_from_known_actions()

void Search::advance_from_known_actions ( search_private & priv )

Definition at line 2133 of file search.cc.

References Search::search_private::active_csoaa, Search::search_private::active_csoaa_verify, Search::search_private::active_known, cdbg, COST_SENSITIVE::label::costs, polylabel::cs, Search::search_private::done_with_all_actions, Search::search_private::learn_a_idx, Search::search_private::learn_losses, and Search::search_private::learn_t.

Referenced by train_single_example().

 {
   size_t t = priv.learn_t;
   if (!priv.active_csoaa)
     return;
   if (priv.active_csoaa_verify > 0.)
     return;
   if (t >= priv.active_known.size())
     return;
   cdbg << "advance_from_known_actions t=" << t << " active_known.size()=" << priv.active_known.size()
        << " learn_a_idx=" << priv.learn_a_idx << endl;
   // cdbg_print_array(" active_known[t]", priv.active_known[t]);
   if (priv.learn_a_idx >= priv.active_known[t].size())
   {
     cdbg << "advance_from_known_actions setting done_with_all_actions=true (active_known[t].size()="
          << priv.active_known[t].size() << ")" << endl;
     priv.done_with_all_actions = true;
     return;
   }
   // if (priv.active_known[t][priv.learn_a_idx] >= FLT_MAX) return;
   if (priv.active_known[t][priv.learn_a_idx].second)
     return;
   // return;
   // wow, we actually found something we were confident about!
   /*
   cs_cost_push_back(priv.cb_learner,
                     priv.learn_losses,
                     priv.is_ldf ? (uint32_t)(priv.learn_a_idx - 1) : (uint32_t)priv.learn_a_idx,
                     priv.active_known[t][priv.learn_a_idx],
                     true);
   */
   priv.learn_losses.cs.costs.push_back(priv.active_known[t][priv.learn_a_idx].first);
   cdbg << "  --> adding " << priv.learn_a_idx << ":" << priv.active_known[t][priv.learn_a_idx].first.x << endl;
   priv.learn_a_idx++;
   advance_from_known_actions(priv);
 }

◆ allowed_actions_to_label()

void Search::allowed_actions_to_label	(	search_private &	priv,
		size_t	ec_cnt,
		const action *	allowed_actions,
		size_t	allowed_actions_cnt,
		const float *	allowed_actions_cost,
		const action *	oracle_actions,
		size_t	oracle_actions_cnt,
		polylabel &	lab
	)

Definition at line 991 of file search.cc.

References Search::search_private::A, Search::search_private::cb_learner, cs_cost_push_back(), cs_costs_erase(), cs_get_costs_size(), cs_set_cost_loss(), f, Search::search_private::is_ldf, and Search::search_private::use_action_costs.

Referenced by search_predict().

 {
   bool isCB = priv.cb_learner;
   if (priv.is_ldf)  // LDF version easier
   {
     cs_costs_erase(isCB, lab);
     for (action k = 0; k < ec_cnt; k++)
       cs_cost_push_back(isCB, lab, k, array_contains<action>(k, oracle_actions, oracle_actions_cnt) ? 0.f : 1.f);
     // std::cerr << "lab = ["; for (size_t i=0; i<lab.cs.costs.size(); i++) cdbg << ' ' << lab.cs.costs[i].class_index
     // << ':'
     // << lab.cs.costs[i].x; cdbg << " ]" << endl;
   }
   else if (priv.use_action_costs)
   {
     // TODO: Weight
     if (allowed_actions == nullptr)
     {
       if (cs_get_costs_size(isCB, lab) != priv.A)
       {
         cs_costs_erase(isCB, lab);
         for (action k = 0; k < priv.A; k++) cs_cost_push_back(isCB, lab, k + 1, 0.);
       }
       for (action k = 0; k < priv.A; k++) cs_set_cost_loss(isCB, lab, k, allowed_actions_cost[k]);
     }
     else  // manually specified actions
     {
       cs_costs_erase(isCB, lab);
       for (action k = 0; k < allowed_actions_cnt; k++)
         cs_cost_push_back(isCB, lab, allowed_actions[k], allowed_actions_cost[k]);
     }
   }
   else  // non-LDF, no action costs
   {
     if ((allowed_actions == nullptr) || (allowed_actions_cnt == 0))  // any action is allowed
     {
       bool set_to_one = false;
       if (cs_get_costs_size(isCB, lab) != priv.A)
       {
         cs_costs_erase(isCB, lab);
         for (action k = 0; k < priv.A; k++) cs_cost_push_back(isCB, lab, k + 1, 1.);
         set_to_one = true;
       }
       // std::cerr << "lab = ["; for (size_t i=0; i<lab.cs.costs.size(); i++) cdbg << ' ' << lab.cs.costs[i].class_index
       // <<
       // ':' << lab.cs.costs[i].x; cdbg << " ]" << endl;
       if (oracle_actions_cnt <= 1)  // common case to speed up
       {
         if (!set_to_one)
           for (action k = 0; k < priv.A; k++) cs_set_cost_loss(isCB, lab, k, 1.);
         if (oracle_actions_cnt == 1)
           cs_set_cost_loss(isCB, lab, oracle_actions[0] - 1, 0.);
       }
       else
       {
         for (action k = 0; k < priv.A; k++)
           cs_set_cost_loss(isCB, lab, k, array_contains<action>(k + 1, oracle_actions, oracle_actions_cnt) ? 0.f : 1.f);
       }
     }
     else  // only some actions are allowed
     {
       cs_costs_erase(isCB, lab);
       float w = 1.;  // array_contains<action>(3, oracle_actions, oracle_actions_cnt) ? 5.f : 1.f;
       for (size_t i = 0; i < allowed_actions_cnt; i++)
       {
         action k = allowed_actions[i];
         cs_cost_push_back(
             isCB, lab, k, (array_contains<action>(k, oracle_actions, oracle_actions_cnt)) ? 0.f : w);  // 1.f );
       }
     }
   }
 }

◆ allowed_actions_to_ld()

polylabel& Search::allowed_actions_to_ld	(	search_private &	priv,
		size_t	ec_cnt,
		const action *	allowed_actions,
		size_t	allowed_actions_cnt,
		const float *	allowed_actions_cost
	)

Definition at line 937 of file search.cc.

References Search::search_private::A, Search::search_private::allowed_actions_cache, Search::search_private::cb_learner, cs_cost_push_back(), cs_costs_erase(), cs_costs_resize(), cs_get_costs_size(), cs_set_cost_loss(), Search::search_private::is_ldf, and Search::search_private::use_action_costs.

Referenced by choose_oracle_action(), and single_prediction_notLDF().

 {
   bool isCB = priv.cb_learner;
   polylabel& ld = *priv.allowed_actions_cache;
   uint32_t num_costs = (uint32_t)cs_get_costs_size(isCB, ld);
 
   if (priv.is_ldf)  // LDF version easier
   {
     if (num_costs > ec_cnt)
       cs_costs_resize(isCB, ld, ec_cnt);
     else if (num_costs < ec_cnt)
       for (action k = num_costs; k < ec_cnt; k++) cs_cost_push_back(isCB, ld, k, FLT_MAX);
   }
   else if (priv.use_action_costs)
   {
     // TODO: Weight
     if (allowed_actions == nullptr)
     {
       if (cs_get_costs_size(isCB, ld) != priv.A)
       {
         cs_costs_erase(isCB, ld);
         for (action k = 0; k < priv.A; k++) cs_cost_push_back(isCB, ld, k + 1, 0.);
       }
       for (action k = 0; k < priv.A; k++) cs_set_cost_loss(isCB, ld, k, allowed_actions_cost[k]);
     }
     else  // manually specified actions
     {
       cs_costs_erase(isCB, ld);
       for (action k = 0; k < allowed_actions_cnt; k++)
         cs_cost_push_back(isCB, ld, allowed_actions[k], allowed_actions_cost[k]);
     }
   }
   else  // non-LDF version, no action costs
   {
     if ((allowed_actions == nullptr) || (allowed_actions_cnt == 0))  // any action is allowed
     {
       if (num_costs != priv.A)  // if there are already A-many actions, they must be the right ones, unless the user did
                                 // something stupid like putting duplicate allowed_actions...
       {
         cs_costs_erase(isCB, ld);
         for (action k = 0; k < priv.A; k++) cs_cost_push_back(isCB, ld, k + 1, FLT_MAX);  //+1 because MC is 1-based
       }
     }
     else  // we need to peek at allowed_actions
     {
       cs_costs_erase(isCB, ld);
       for (size_t i = 0; i < allowed_actions_cnt; i++) cs_cost_push_back(isCB, ld, allowed_actions[i], FLT_MAX);
     }
   }
 
   return ld;
 }

◆ array_contains()

template<class T >

bool Search::array_contains	(	T	target,
		const T *	A,
		size_t	n
	)

Definition at line 773 of file search.cc.

Referenced by choose_oracle_action().

 {
   if (A == nullptr)
     return false;
   for (size_t i = 0; i < n; i++)
     if (A[i] == target)
       return true;
   return false;
 }

◆ audit_feature_space()

std::string Search::audit_feature_space ( "conditional" )

Referenced by Search::search::~search().

◆ cached_action_store_or_find()

bool Search::cached_action_store_or_find	(	search_private &	priv,
		ptag	mytag,
		const ptag *	condition_on,
		const char *	condition_on_names,
		action_repr *	condition_on_actions,
		size_t	condition_on_cnt,
		int	policy,
		size_t	learner_id,
		action &	a,
		bool	do_store,
		float &	a_cost
	)

Definition at line 1438 of file search.cc.

References Search::scored_action::a, Search::action_repr::a, Search::search_private::cache_hash_map, Search::search_private::no_caching, Search::scored_action::s, and uniform_hash().

Referenced by search_predict().

 {
   if (priv.no_caching)
     return do_store;
   if (mytag == 0)
     return do_store;  // don't attempt to cache when tag is zero
 
   size_t sz = sizeof(size_t) + sizeof(ptag) + sizeof(int) + sizeof(size_t) + sizeof(size_t) +
       condition_on_cnt * (sizeof(ptag) + sizeof(action) + sizeof(char));
   if (sz % 4 != 0)
     sz += 4 - (sz % 4);  // make sure sz aligns to 4 so that uniform_hash does the right thing
 
   unsigned char* item = calloc_or_throw<unsigned char>(sz);
   unsigned char* here = item;
   *here = (unsigned char)sz;
   here += sizeof(size_t);
   *here = mytag;
   here += sizeof(ptag);
   *here = policy;
   here += sizeof(int);
   *here = (unsigned char)learner_id;
   here += sizeof(size_t);
   *here = (unsigned char)condition_on_cnt;
   here += sizeof(size_t);
   for (size_t i = 0; i < condition_on_cnt; i++)
   {
     *here = condition_on[i];
     here += sizeof(ptag);
     *here = condition_on_actions[i].a;
     here += sizeof(action);
     *here = condition_on_names[i];
     here += sizeof(char);  // SPEEDUP: should we align this at 4?
   }
   uint64_t hash = uniform_hash(item, sz, 3419);
 
   if (do_store)
   {
     priv.cache_hash_map.put(item, hash, scored_action(a, a_cost));
     return true;
   }
   else  // its a find
   {
     scored_action sa = priv.cache_hash_map.get(item, hash);
     a = sa.a;
     a_cost = sa.s;
     free(item);
     return a != (action)-1;
   }
 }

◆ cached_item_equivalent()

bool Search::cached_item_equivalent	(	unsigned char *const &	A,
		unsigned char *const &	B
	)

Definition at line 1429 of file search.cc.

Referenced by search_initialize().

 {
   size_t sz_A = *A;
   size_t sz_B = *B;
   if (sz_A != sz_B)
     return false;
   return memcmp(A, B, sz_A) == 0;
 }

◆ cdbg_print_array()

template<class T >

void Search::cdbg_print_array	(	std::string	str,
		v_array< T > &	A
	)

Definition at line 754 of file search.cc.

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

Referenced by search_predict().

 {
   cdbg << str << " = [";
   for (size_t i = 0; i < A.size(); i++) cdbg << " " << A[i];
   cdbg << " ]" << endl;
 }

◆ cerr_print_array()

template<class T >

void Search::cerr_print_array	(	std::string	str,
		v_array< T > &	A
	)

Definition at line 761 of file search.cc.

References v_array< T >::size().

 {
   std::cerr << str << " = [";
   for (size_t i = 0; i < A.size(); i++) std::cerr << " " << A[i];
   std::cerr << " ]" << endl;
 }

◆ choose_oracle_action()

action Search::choose_oracle_action	(	search_private &	priv,
		size_t	ec_cnt,
		const action *	oracle_actions,
		size_t	oracle_actions_cnt,
		const action *	allowed_actions,
		size_t	allowed_actions_cnt,
		const float *	allowed_actions_cost
	)

Definition at line 1097 of file search.cc.

Referenced by search_predict().

 {
   action a = (action)-1;
   if (priv.use_action_costs)
   {
     size_t K = (allowed_actions == nullptr) ? priv.A : allowed_actions_cnt;
     cdbg << "costs = [";
     for (size_t k = 0; k < K; k++) cdbg << ' ' << allowed_actions_cost[k];
     cdbg << " ]" << endl;
     float min_cost = FLT_MAX;
     for (size_t k = 0; k < K; k++) min_cost = std::min(min_cost, allowed_actions_cost[k]);
     cdbg << "min_cost = " << min_cost;
     if (min_cost < FLT_MAX)
     {
       size_t count = 0;
       for (size_t k = 0; k < K; k++)
         if (allowed_actions_cost[k] <= min_cost)
         {
           cdbg << ", hit @ " << k;
           count++;
           if ((count == 1) || (priv._random_state->get_and_update_random() < 1. / (float)count))
           {
             a = (allowed_actions == nullptr) ? (uint32_t)(k + 1) : allowed_actions[k];
             cdbg << "***";
           }
         }
     }
     cdbg << endl;
   }
 
   if (a == (action)-1)
   {
     if ((priv.perturb_oracle > 0.) && (priv.state == INIT_TRAIN) &&
         (priv._random_state->get_and_update_random() < priv.perturb_oracle))
       oracle_actions_cnt = 0;
     a = (oracle_actions_cnt > 0)
         ? oracle_actions[random(priv._random_state, oracle_actions_cnt)]
         : (allowed_actions_cnt > 0) ? allowed_actions[random(priv._random_state, allowed_actions_cnt)]
                                     : priv.is_ldf ? (action)random(priv._random_state, ec_cnt)
                                                   : (action)(1 + random(priv._random_state, priv.A));
   }
   cdbg << "choose_oracle_action from oracle_actions = [";
   for (size_t i = 0; i < oracle_actions_cnt; i++) cdbg << " " << oracle_actions[i];
   cdbg << " ], ret=" << a << endl;
   if (need_memo_foreach_action(priv) && (priv.state == INIT_TRAIN))
   {
     v_array<action_cache>* this_cache = new v_array<action_cache>();
     *this_cache = v_init<action_cache>();
     // TODO we don't really need to construct this polylabel
     polylabel l = allowed_actions_to_ld(priv, 1, allowed_actions, allowed_actions_cnt, allowed_actions_cost);
     size_t K = cs_get_costs_size(priv.cb_learner, l);
     for (size_t k = 0; k < K; k++)
     {
       action cl = cs_get_cost_index(priv.cb_learner, l, k);
       float cost = array_contains(cl, oracle_actions, oracle_actions_cnt) ? 0.f : 1.f;
       this_cache->push_back(action_cache(0., cl, cl == a, cost));
     }
     assert(priv.memo_foreach_action.size() == priv.meta_t + priv.t - 1);
     priv.memo_foreach_action.push_back(this_cache);
     cdbg << "memo_foreach_action[" << priv.meta_t + priv.t - 1 << "] = " << this_cache << " from oracle" << endl;
   }
   return a;
 }

◆ choose_policy()

int Search::choose_policy	(	search_private &	priv,
		bool	advance_prng = `true`
	)

Definition at line 1401 of file search.cc.

References Search::search_private::allow_current_policy, INIT_TEST, INIT_TRAIN, LEARN, MIX_PER_ROLL, Search::search_private::mix_per_roll_policy, MIX_PER_STATE, NO_ROLLOUT, ORACLE, POLICY, random_policy(), Search::search_private::rollin_method, Search::search_private::rollout_method, Search::search_private::state, and THROW.

Referenced by search_predict(), and search_predictNeedsExample().

 {
   RollMethod method = (priv.state == INIT_TEST) ? POLICY
                                                 : (priv.state == LEARN)
           ? priv.rollout_method
           : (priv.state == INIT_TRAIN) ? priv.rollin_method : NO_ROLLOUT;  // this should never happen
   switch (method)
   {
     case POLICY:
       return random_policy(priv, priv.allow_current_policy || (priv.state == INIT_TEST), false, advance_prng);
 
     case ORACLE:
       return -1;
 
     case MIX_PER_STATE:
       return random_policy(priv, priv.allow_current_policy, true, advance_prng);
 
     case MIX_PER_ROLL:
       if (priv.mix_per_roll_policy == -2)  // then we have to choose one!
         priv.mix_per_roll_policy = random_policy(priv, priv.allow_current_policy, true, advance_prng);
       return priv.mix_per_roll_policy;
 
     case NO_ROLLOUT:
     default:
       THROW("internal error (bug): trying to rollin or rollout with NO_ROLLOUT");
   }
 }

◆ clear_cache_hash_map()

void Search::clear_cache_hash_map ( search_private & priv )

Definition at line 278 of file search.cc.

References Search::search_private::cache_hash_map, and free_key().

Referenced by train_single_example(), and Search::search::~search().

 {
   priv.cache_hash_map.iter(free_key);
   priv.cache_hash_map.clear();
 }

◆ clear_memo_foreach_action()

void Search::clear_memo_foreach_action ( search_private & priv )

Definition at line 284 of file search.cc.

References Search::search_private::memo_foreach_action.

Referenced by train_single_example(), and Search::search::~search().

 {
   for (size_t i = 0; i < priv.memo_foreach_action.size(); i++)
     if (priv.memo_foreach_action[i])
     {
       priv.memo_foreach_action[i]->delete_v();
       delete priv.memo_foreach_action[i];
     }
   priv.memo_foreach_action.clear();
 }

◆ cmp_size_t()

bool Search::cmp_size_t	(	const size_t	a,
		const size_t	b
	)

inline

Definition at line 1940 of file search.cc.

Referenced by get_training_timesteps(), and hoopla_permute().

1940 { return a < b; }

a

constexpr uint64_t a

Definition: rand48.cc:11

◆ cmp_size_t_pair()

bool Search::cmp_size_t_pair	(	const std::pair< size_t, size_t > &	a,
		const std::pair< size_t, size_t > &	b
	)

inline

Definition at line 1941 of file search.cc.

 {
   return ((a.first == b.first) && (a.second < b.second)) || (a.first < b.first);
 }

◆ condition_feature_space()

std::string Search::condition_feature_space ( "search_condition" )

Referenced by add_example_conditioning().

◆ cs_cost_push_back()

void Search::cs_cost_push_back	(	bool	isCB,
		polylabel &	ld,
		uint32_t	index,
		float	value
	)

inline

Definition at line 923 of file search.cc.

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

Referenced by allowed_actions_to_label(), allowed_actions_to_ld(), and train_single_example().

 {
   if (isCB)
   {
     CB::cb_class cost = {value, index, 0., 0.};
     ld.cb.costs.push_back(cost);
   }
   else
   {
     CS::wclass cost = {value, index, 0., 0.};
     ld.cs.costs.push_back(cost);
   }
 }

◆ cs_costs_erase()

void Search::cs_costs_erase	(	bool	isCB,
		polylabel &	ld
	)

inline

Definition at line 907 of file search.cc.

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

Referenced by allowed_actions_to_label(), and allowed_actions_to_ld().

 {
   if (isCB)
     ld.cb.costs.clear();
   else
     ld.cs.costs.clear();
 }

◆ cs_costs_resize()

void Search::cs_costs_resize	(	bool	isCB,
		polylabel &	ld,
		size_t	new_size
	)

inline

Definition at line 915 of file search.cc.

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

Referenced by allowed_actions_to_ld().

 {
   if (isCB)
     ld.cb.costs.resize(new_size);
   else
     ld.cs.costs.resize(new_size);
 }

◆ cs_get_cost_index()

uint32_t Search::cs_get_cost_index	(	bool	isCB,
		polylabel &	ld,
		size_t	k
	)

inline

Definition at line 889 of file search.cc.

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

Referenced by choose_oracle_action(), and single_prediction_notLDF().

 {
   return isCB ? ld.cb.costs[k].action : ld.cs.costs[k].class_index;
 }

◆ cs_get_cost_partial_prediction()

float Search::cs_get_cost_partial_prediction	(	bool	isCB,
		polylabel &	ld,
		size_t	k
	)

inline

Definition at line 894 of file search.cc.

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

Referenced by single_prediction_notLDF().

 {
   return isCB ? ld.cb.costs[k].partial_prediction : ld.cs.costs[k].partial_prediction;
 }

◆ cs_get_costs_size()

size_t Search::cs_get_costs_size	(	bool	isCB,
		polylabel &	ld
	)

inline

Definition at line 887 of file search.cc.

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

Referenced by allowed_actions_to_label(), allowed_actions_to_ld(), choose_oracle_action(), generate_training_example(), and single_prediction_notLDF().

887 { return isCB ? ld.cb.costs.size() : ld.cs.costs.size(); }

polylabel::cb

CB::label cb

Definition: example.h:31

CB::label::costs

v_array< cb_class > costs

Definition: cb.h:27

polylabel::cs

COST_SENSITIVE::label cs

Definition: example.h:30

COST_SENSITIVE::label::costs

v_array< wclass > costs

Definition: cost_sensitive.h:31

◆ cs_set_cost_loss()

void Search::cs_set_cost_loss	(	bool	isCB,
		polylabel &	ld,
		size_t	k,
		float	val
	)

inline

Definition at line 899 of file search.cc.

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

Referenced by allowed_actions_to_label(), and allowed_actions_to_ld().

 {
   if (isCB)
     ld.cb.costs[k].cost = val;
   else
     ld.cs.costs[k].x = val;
 }

◆ del_example_conditioning()

void Search::del_example_conditioning	(	search_private &	priv,
		example &	ec
	)

Definition at line 881 of file search.cc.

References conditioning_namespace, del_features_in_top_namespace(), example_predict::indices, v_array< T >::last(), and v_array< T >::size().

Referenced by generate_training_example(), and search_predict().

 {
   if ((ec.indices.size() > 0) && (ec.indices.last() == conditioning_namespace))
     del_features_in_top_namespace(priv, ec, conditioning_namespace);
 }

◆ del_features_in_top_namespace()

void Search::del_features_in_top_namespace	(	search_private &	,
		example &	ec,
		size_t	ns
	)

Definition at line 613 of file search.cc.

References features::clear(), v_array< T >::decr(), example_predict::feature_space, example_predict::indices, v_array< T >::last(), example::num_features, v_array< T >::size(), features::size(), features::sum_feat_sq, and example::total_sum_feat_sq.

Referenced by del_example_conditioning(), and del_neighbor_features().

 {
   if ((ec.indices.size() == 0) || (ec.indices.last() != ns))
   {
     return;
     // if (ec.indices.size() == 0)
     //{ THROW("internal error (bug): expecting top namespace to be '" << ns << "' but it was empty"); }
     // else
     //{ THROW("internal error (bug): expecting top namespace to be '" << ns << "' but it was " <<
     //(size_t)ec.indices.last()); }
   }
   features& fs = ec.feature_space[ns];
   ec.indices.decr();
   ec.num_features -= fs.size();
   ec.total_sum_feat_sq -= fs.sum_feat_sq;
   fs.clear();
 }

◆ del_neighbor_features()

void Search::del_neighbor_features	(	search_private &	priv,
		multi_ex &	ec_seq
	)

Definition at line 683 of file search.cc.

References del_features_in_top_namespace(), Search::search_private::neighbor_features, neighbor_namespace, and v_array< T >::size().

Referenced by do_actual_learning().

 {
   if (priv.neighbor_features.size() == 0)
     return;
   for (size_t n = 0; n < ec_seq.size(); n++) del_features_in_top_namespace(priv, *ec_seq[n], neighbor_namespace);
 }

◆ do_actual_learning()

template<bool is_learn>

void Search::do_actual_learning	(	search &	sch,
		base_learner &	base,
		multi_ex &	ec_seq
	)

Definition at line 2378 of file search.cc.

 {
   if (ec_seq.size() == 0)
     return;  // nothing to do :)
 
   bool is_test_ex = false;
   bool is_holdout_ex = false;
 
   search_private& priv = *sch.priv;
   priv.offset = ec_seq[0]->ft_offset;
   priv.base_learner = &base;
 
   adjust_auto_condition(priv);
   priv.read_example_last_id = ec_seq[ec_seq.size() - 1]->example_counter;
 
   // hit_new_pass true would have already triggered a printout
   // finish_example(multi_ex).  so we can reset hit_new_pass here
   priv.hit_new_pass = false;
 
   for (size_t i = 0; i < ec_seq.size(); i++)
   {
     is_test_ex |= priv.label_is_test(ec_seq[i]->l);
     is_holdout_ex |= ec_seq[i]->test_only;
     if (is_test_ex && is_holdout_ex)
       break;
   }
 
   if (priv.task->run_setup)
     priv.task->run_setup(sch, ec_seq);
 
   // if we're going to have to print to the screen, generate the "truth" std::string
   cdbg << "======================================== GET TRUTH STRING (" << priv.current_policy << ","
        << priv.read_example_last_pass << ") ========================================" << endl;
   if (might_print_update(*priv.all))
   {
     if (is_test_ex)
       priv.truth_string->str("**test**");
     else
     {
       reset_search_structure(*sch.priv);
       priv.state = GET_TRUTH_STRING;
       priv.should_produce_string = true;
       priv.truth_string->str("");
       run_task(sch, ec_seq);
     }
   }
 
   add_neighbor_features(priv, ec_seq);
   train_single_example<is_learn>(sch, is_test_ex, is_holdout_ex, ec_seq);
   del_neighbor_features(priv, ec_seq);
 
   if (priv.task->run_takedown)
     priv.task->run_takedown(sch, ec_seq);
 }

◆ end_examples()

void Search::end_examples ( search & sch )

Definition at line 2464 of file search.cc.

References Search::search_private::all, Search::search_private::current_policy, VW::config::options_i::get_typed_option(), vw::options, Search::search_private::passes_since_new_policy, Search::search::priv, VW::config::options_i::replace(), prediction_type::to_string(), Search::search_private::total_number_of_policies, and vw::training.

Referenced by setup().

 {
   search_private& priv = *sch.priv;
   vw* all = priv.all;
 
   if (all->training)
   {
     // TODO work out a better system to update state that will be saved in the model.
     // Dig out option and change it in case we already loaded a predictor which had a value stored for
     // --search_trained_nb_policies
     auto val = (priv.passes_since_new_policy == 0) ? priv.current_policy : (priv.current_policy + 1);
     all->options->replace("search_trained_nb_policies", std::to_string(val));
     all->options->get_typed_option<uint32_t>("search_trained_nb_policies").value(val);
     // Dig out option and change it in case we already loaded a predictor which had a value stored for
     // --search_total_nb_policies
     all->options->replace("search_total_nb_policies", std::to_string(priv.total_number_of_policies));
     all->options->get_typed_option<uint32_t>("search_total_nb_policies").value(priv.total_number_of_policies);
   }
 }

◆ end_pass()

void Search::end_pass ( search & sch )

Definition at line 2433 of file search.cc.

References Search::search_private::all, Search::search_private::current_policy, VW::config::options_i::get_typed_option(), Search::search_private::hit_new_pass, vw::options, Search::search_private::passes_per_policy, Search::search_private::passes_since_new_policy, Search::search::priv, Search::search_private::read_example_last_pass, VW::config::options_i::replace(), prediction_type::to_string(), Search::search_private::total_number_of_policies, and vw::training.

 {
   search_private& priv = *sch.priv;
   vw* all = priv.all;
   priv.hit_new_pass = true;
   priv.read_example_last_pass++;
   priv.passes_since_new_policy++;
 
   if (priv.passes_since_new_policy >= priv.passes_per_policy)
   {
     priv.passes_since_new_policy = 0;
     if (all->training)
       priv.current_policy++;
     if (priv.current_policy > priv.total_number_of_policies)
     {
       std::cerr << "internal error (bug): too many policies; not advancing" << endl;
       priv.current_policy = priv.total_number_of_policies;
     }
     // reset search_trained_nb_policies in options_from_file so it is saved to regressor file later
     // TODO work out a better system to update state that will be saved in the model.
     all->options->replace("search_trained_nb_policies", std::to_string(priv.current_policy));
     all->options->get_typed_option<uint32_t>("search_trained_nb_policies").value(priv.current_policy);
   }
 }

◆ ensure_param()

void Search::ensure_param	(	float &	v,
		float	lo,
		float	hi,
		float	def,
		const char *	str
	)

Definition at line 2534 of file search.cc.

Referenced by setup().

 {
   if ((v < lo) || (v > hi))
   {
     std::cerr << str << endl;
     v = def;
   }
 }

◆ ensure_size()

template<class T >

void Search::ensure_size	(	v_array< T > &	A,
		size_t	sz
	)

Definition at line 1066 of file search.cc.

References v_array< T >::begin(), v_array< T >::end(), v_array< T >::end_array, and v_array< T >::resize().

Referenced by search_predict().

 {
   if ((size_t)(A.end_array - A.begin()) < sz)
     A.resize(sz * 2 + 1);
   A.end() = A.begin() + sz;
 }

◆ finish_multiline_example()

void Search::finish_multiline_example	(	vw &	all,
		search &	sch,
		multi_ex &	ec_seq
	)

Definition at line 2458 of file search.cc.

References VW::finish_example(), print_update(), and Search::search::priv.

 {
   print_update(*sch.priv);
   VW::finish_example(all, ec_seq);
 }

◆ float_equal()

bool Search::float_equal	(	float	a,
		float	b
	)

◆ foreach_action_from_cache()

void Search::foreach_action_from_cache	(	search_private &	priv,
		size_t	t,
		action	override_a = `(action)-1`
	)

Definition at line 1634 of file search.cc.

References Search::BaseTask::_foreach_action, cdbg, Search::action_cache::cost, id(), Search::action_cache::is_opt, Search::action_cache::k, Search::search_private::memo_foreach_action, Search::search_private::meta_t, Search::search_private::metaoverride, Search::action_cache::min_cost, and Search::BaseTask::sch.

Referenced by search_predict().

 {
   cdbg << "foreach_action_from_cache: t=" << t << ", memo_foreach_action.size()=" << priv.memo_foreach_action.size()
        << ", override_a=" << override_a << endl;
   assert(t < priv.memo_foreach_action.size());
   v_array<action_cache>* cached = priv.memo_foreach_action[t];
   if (!cached)
     return;  // the only way this can happen is if the metatask overrode this action
   cdbg << "memo_foreach_action size = " << cached->size() << endl;
   for (size_t id = 0; id < cached->size(); id++)
   {
     action_cache& ac = (*cached)[id];
     priv.metaoverride->_foreach_action(*priv.metaoverride->sch, t - priv.meta_t, ac.min_cost, ac.k,
         (override_a == (action)-1) ? ac.is_opt : (ac.k == override_a), ac.cost);
   }
 }

◆ free_final_item()

void Search::free_final_item ( final_item * p )

Definition at line 2056 of file search.cc.

References Search::final_item::prefix.

 {
   p->prefix->delete_v();
   delete p->prefix;
   delete p;
 }

◆ free_key()

void Search::free_key	(	unsigned char *	mem,
		scored_action
	)

Definition at line 277 of file search.cc.

Referenced by clear_cache_hash_map().

277 { free(mem); } // sa.repr.delete_v(); }

◆ generate_training_example()

void Search::generate_training_example	(	search_private &	priv,
		polylabel &	losses,
		float	weight,
		bool	add_conditioning = `true`,
		float	min_loss = `FLT_MAX`
	)

Definition at line 1490 of file search.cc.

Referenced by search_predict(), and train_single_example().

 {
   // should we really subtract out min-loss?
   // float min_loss = FLT_MAX;
   if (priv.cb_learner)
   {
     if (min_loss == FLT_MAX)
       for (size_t i = 0; i < losses.cb.costs.size(); i++) min_loss = std::min(min_loss, losses.cb.costs[i].cost);
     for (size_t i = 0; i < losses.cb.costs.size(); i++) losses.cb.costs[i].cost = losses.cb.costs[i].cost - min_loss;
   }
   else
   {
     if (min_loss == FLT_MAX)
       for (size_t i = 0; i < losses.cs.costs.size(); i++) min_loss = std::min(min_loss, losses.cs.costs[i].x);
     for (size_t i = 0; i < losses.cs.costs.size(); i++)
       losses.cs.costs[i].x = (losses.cs.costs[i].x - min_loss) * weight;
   }
   // std::cerr << "losses = ["; for (size_t i=0; i<losses.cs.costs.size(); i++) std::cerr << ' ' <<
   // losses.cs.costs[i].class_index
   // << ':' << losses.cs.costs[i].x; std::cerr << " ]" << endl;
 
   if (!priv.is_ldf)  // not LDF
   {
     // since we're not LDF, it should be the case that ec_ref_cnt == 1
     // and learn_ec_ref[0] is a pointer to a single example
     assert(priv.learn_ec_ref_cnt == 1);
     assert(priv.learn_ec_ref != nullptr);
 
     example& ec = priv.learn_ec_ref[0];
     polylabel old_label = ec.l;
     ec.l = losses;  // labels;
     if (add_conditioning)
       add_example_conditioning(priv, ec, priv.learn_condition_on.size(), priv.learn_condition_on_names.begin(),
           priv.learn_condition_on_act.begin());
     for (size_t is_local = 0; is_local <= (size_t)priv.xv; is_local++)
     {
       int learner = select_learner(priv, priv.current_policy, priv.learn_learner_id, true, is_local > 0);
       ec.in_use = true;
       cdbg << "BEGIN base_learner->learn(ec, " << learner << ")" << endl;
       as_singleline(priv.base_learner)->learn(ec, learner);
       cdbg << "END   base_learner->learn(ec, " << learner << ")" << endl;
     }
     if (add_conditioning)
       del_example_conditioning(priv, ec);
     ec.l = old_label;
     priv.total_examples_generated++;
   }
   else  // is  LDF
   {
     assert(cs_get_costs_size(priv.cb_learner, losses) == priv.learn_ec_ref_cnt);
     size_t start_K = (priv.is_ldf && COST_SENSITIVE::ec_is_example_header(priv.learn_ec_ref[0])) ? 1 : 0;
 
     // TODO: weight
     if (add_conditioning)
       for (action a = (uint32_t)start_K; a < priv.learn_ec_ref_cnt; a++)
       {
         example& ec = priv.learn_ec_ref[a];
         add_example_conditioning(priv, ec, priv.learn_condition_on.size(), priv.learn_condition_on_names.begin(),
             priv.learn_condition_on_act.begin());
       }
 
     for (size_t is_local = 0; is_local <= (size_t)priv.xv; is_local++)
     {
       int learner = select_learner(priv, priv.current_policy, priv.learn_learner_id, true, is_local > 0);
 
       // create an example collection for
 
       multi_ex tmp;
       uint64_t tmp_offset = 0;
       if (priv.learn_ec_ref_cnt > start_K)
         tmp_offset = priv.learn_ec_ref[start_K].ft_offset;
       for (action a = (uint32_t)start_K; a < priv.learn_ec_ref_cnt; a++)
       {
         example& ec = priv.learn_ec_ref[a];
         CS::label& lab = ec.l.cs;
         if (lab.costs.size() == 0)
         {
           CS::wclass wc = {0., a - (uint32_t)start_K, 0., 0.};
           lab.costs.push_back(wc);
         }
         lab.costs[0].x = losses.cs.costs[a - start_K].x;
         ec.in_use = true;
         // store the offset to restore it later
         ec.ft_offset = priv.offset;
         // create the example collection used to learn
         tmp.push_back(&ec);
         cdbg << "generate_training_example called learn on action a=" << a << ", costs.size=" << lab.costs.size()
              << " ec=" << &ec << endl;
         priv.total_examples_generated++;
       }
 
       // learn with the multiline example
       as_multiline(priv.base_learner)->learn(tmp, learner);
 
       // restore the offsets in examples
       int i = 0;
       for (action a = (uint32_t)start_K; a < priv.learn_ec_ref_cnt; a++, i++)
         priv.learn_ec_ref[a].ft_offset = tmp_offset;
     }
 
     if (add_conditioning)
       for (action a = (uint32_t)start_K; a < priv.learn_ec_ref_cnt; a++)
       {
         example& ec = priv.learn_ec_ref[a];
         del_example_conditioning(priv, ec);
       }
   }
 }

◆ get_training_timesteps()

void Search::get_training_timesteps	(	search_private &	priv,
		v_array< size_t > &	timesteps
	)

Definition at line 1983 of file search.cc.

References Search::search_private::_random_state, Search::search_private::active_csoaa, Search::search_private::active_known, Search::search_private::active_uncertainty, v_array< T >::begin(), v_array< T >::clear(), cmp_size_t(), v_array< T >::end(), hoopla_permute(), Search::search_private::linear_ordering, v_array< T >::push_back(), v_array< T >::size(), Search::search_private::subsample_timesteps, Search::search_private::T, and v_array_contains().

Referenced by train_single_example().

 {
   timesteps.clear();
 
   // if there's active learning, we need to
   if (priv.subsample_timesteps <= -1)
   {
     for (size_t i = 0; i < priv.active_uncertainty.size(); i++)
       if (priv._random_state->get_and_update_random() > priv.active_uncertainty[i].first)
         timesteps.push_back(priv.active_uncertainty[i].second - 1);
     /*
     float k = (float)priv.total_examples_generated;
     priv.ec_seq[t]->revert_weight = priv.all->loss->getRevertingWeight(priv.all->sd, priv.ec_seq[t].pred.scalar,
     priv.all->eta / powf(k, priv.all->power_t)); float importance = query_decision(active_str, *priv.ec_seq[t], k); if
     (importance > 0.) timesteps.push_back(pair<size_t,size_t>(0,t));
     */
   }
   // if there's no subsampling to do, just return [0,T)
   else if (priv.subsample_timesteps <= 0)
     for (size_t t = 0; t < priv.T; t++)
     {
       uint32_t count = 99;
       if (priv.active_csoaa && (t < priv.active_known.size()))
       {
         count = 0;
         for (std::pair<CS::wclass&, bool> wcq : priv.active_known[t])
           if (wcq.second)
           {
             count++;
             if (count > 1)
               break;
           }
       }
       if (count > 1)
         timesteps.push_back(t);
     }
 
   // if subsample in (0,1) then pick steps with that probability, but ensuring there's at least one!
   else if (priv.subsample_timesteps < 1)
   {
     for (size_t t = 0; t < priv.T; t++)
       if (priv._random_state->get_and_update_random() <= priv.subsample_timesteps)
         timesteps.push_back(t);
 
     if (timesteps.size() == 0)  // ensure at least one
       timesteps.push_back((size_t)(priv._random_state->get_and_update_random() * priv.T));
   }
 
   // finally, if subsample >= 1, then pick (int) that many uniformly at random without replacement; could use an LFSR
   // but why? :P
   else
   {
     while ((timesteps.size() < (size_t)priv.subsample_timesteps) && (timesteps.size() < priv.T))
     {
       size_t t = (size_t)(priv._random_state->get_and_update_random() * (float)priv.T);
       if (!v_array_contains(timesteps, t))
         timesteps.push_back(t);
     }
     std::sort(timesteps.begin(), timesteps.end(), cmp_size_t);
   }
 
   if (!priv.linear_ordering)
     hoopla_permute(timesteps.begin(), timesteps.end());
 }

◆ handle_condition_options()

void Search::handle_condition_options	(	vw &	all,
		auto_condition_settings &	acset
	)

Definition at line 2543 of file search.cc.

References VW::config::option_group_definition::add(), VW::config::options_i::add_and_parse(), f, Search::auto_condition_settings::feature_value, VW::config::make_option(), Search::auto_condition_settings::max_bias_ngram_length, Search::auto_condition_settings::max_quad_ngram_length, vw::options, and Search::auto_condition_settings::use_passthrough_repr.

Referenced by setup().

 {
   option_group_definition new_options("Search Auto-conditioning Options");
   new_options.add(make_option("search_max_bias_ngram_length", acset.max_bias_ngram_length)
                       .keep()
                       .default_value(1)
                       .help("add a \"bias\" feature for each ngram up to and including this length. eg., if it's 1 "
                             "(default), then you get a single feature for each conditional"));
   new_options.add(make_option("search_max_quad_ngram_length", acset.max_quad_ngram_length)
                       .keep()
                       .default_value(0)
                       .help("add bias *times* input features for each ngram up to and including this length (def: 0)"));
   new_options.add(make_option("search_condition_feature_value", acset.feature_value)
                       .keep()
                       .default_value(1.f)
                       .help("how much weight should the conditional features get? (def: 1.)"));
   new_options.add(make_option("search_use_passthrough_repr", acset.use_passthrough_repr)
                       .keep()
                       .help("should we use lower-level reduction _internal state_ as additional features? (def: no)"));
   all.options->add_and_parse(new_options);
 }

◆ hoopla_permute()

void Search::hoopla_permute	(	size_t *	B,
		size_t *	end
	)

Definition at line 1948 of file search.cc.

References absdiff(), and cmp_size_t().

Referenced by get_training_timesteps().

 {
   // from Curtis IPL 2004, "Darts and hoopla board design"
   // first sort
   size_t N = end - B;
   std::sort(B, end, cmp_size_t);
   // make some temporary space
   size_t* A = calloc_or_throw<size_t>((N + 1) * 2);
   A[N] = B[0];                // arbitrarily choose the maximum in the middle
   A[N + 1] = B[N - 1];        // so the maximum goes next to it
   size_t lo = N, hi = N + 1;  // which parts of A have we filled in? [lo,hi]
   size_t i = 0, j = N - 1;    // which parts of B have we already covered? [0,i] and [j,N-1]
   while (i + 1 < j)
   {
     // there are four options depending on where things get placed
     size_t d1 = absdiff(A[lo], B[i + 1]);  // put B[i+1] at the bottom
     size_t d2 = absdiff(A[lo], B[j - 1]);  // put B[j-1] at the bottom
     size_t d3 = absdiff(A[hi], B[i + 1]);  // put B[i+1] at the top
     size_t d4 = absdiff(A[hi], B[j - 1]);  // put B[j-1] at the top
     size_t mx = std::max(std::max(d1, d2), std::max(d3, d4));
     if (d1 >= mx)
       A[--lo] = B[++i];
     else if (d2 >= mx)
       A[--lo] = B[--j];
     else if (d3 >= mx)
       A[++hi] = B[++i];
     else
       A[++hi] = B[--j];
   }
   // copy it back to B
   memcpy(B, A + lo, N * sizeof(size_t));
   // clean up
   free(A);
 }

◆ mc_label_is_test()

bool Search::mc_label_is_test ( polylabel & lab )

Definition at line 2484 of file search.cc.

References MULTICLASS::mc_label, polylabel::multi, and label_parser::test_label.

Referenced by search_initialize().

2484 { return MC::mc_label.test_label(&lab.multi); }

label_parser::test_label

bool(* test_label)(void *)

Definition: label_parser.h:22

MULTICLASS::mc_label

label_parser mc_label

Definition: multiclass.cc:93

polylabel::multi

MULTICLASS::label_t multi

Definition: example.h:29

◆ might_print_update()

bool Search::might_print_update ( vw & all )

Definition at line 461 of file search.cc.

References vw::bfgs, shared_data::dump_interval, vw::quiet, vw::sd, and shared_data::weighted_examples().

Referenced by do_actual_learning(), must_run_test(), and train_single_example().

 {
   // basically do should_print_update but check me and the next
   // example because of off-by-ones
 
   if (PRINT_UPDATE_EVERY_EXAMPLE)
     return true;
   if (PRINT_UPDATE_EVERY_PASS)
     return true;  // SPEEDUP: make this better
   return (all.sd->weighted_examples() + 1. >= all.sd->dump_interval) && !all.quiet && !all.bfgs;
 }

◆ must_run_test()

bool Search::must_run_test	(	vw &	all,
		multi_ex &	ec,
		bool	is_test_ex
	)

Definition at line 473 of file search.cc.

References vw::current_pass, vw::final_prediction_sink, vw::holdout_set_off, might_print_update(), vw::quiet, vw::raw_prediction, v_array< T >::size(), and vw::vw_is_main.

Referenced by train_single_example().

 {
   return (all.final_prediction_sink.size() > 0) ||  // if we have to produce output, we need to run this
       might_print_update(all) ||                    // if we have to print and update to stderr
       (all.raw_prediction > 0) ||                   // we need raw predictions
       ((!all.vw_is_main) && (is_test_ex)) ||        // library needs predictions
       // or:
       //   it's not quiet AND
       //     current_pass == 0
       //     OR holdout is off
       //     OR it's a test example
       ((!all.quiet || !all.vw_is_main) &&  // had to disable this because of library mode!
           (!is_test_ex) &&
           (all.holdout_set_off ||                          // no holdout
               ec[0]->test_only || (all.current_pass == 0)  // we need error rates for progressive cost
               ));
 }

◆ need_memo_foreach_action()

bool Search::need_memo_foreach_action ( search_private & priv )

inline

Definition at line 370 of file search.cc.

References INIT_TRAIN, Search::search_private::metaoverride, Search::search_private::metatask, and Search::search_private::state.

Referenced by choose_oracle_action(), search_predict(), single_prediction_LDF(), and single_prediction_notLDF().

 {
   return (priv.state == INIT_TRAIN) && (priv.metatask) && (priv.metaoverride);  // &&
   //        (priv.metaoverride->_foreach_action || priv.metaoverride->_post_prediction);
 }

◆ neighbor_feature_space()

std::string Search::neighbor_feature_space ( "neighbor" )

Referenced by add_neighbor_features().

◆ number_to_natural()

std::string Search::number_to_natural ( size_t big )

Definition at line 512 of file search.cc.

Referenced by print_update().

 {
   std::stringstream ss;
   if (big > 9999999999)
     ss << big / 1000000000 << "g";
   else if (big > 9999999)
     ss << big / 1000000 << "m";
   else if (big > 9999)
     ss << big / 1000 << "k";
   else
     ss << big;
 
   return ss.str();
 }

◆ operator<<() [1/2]

std::ostream& Search::operator<<	(	std::ostream &	os,
		const scored_action &	x
	)

Definition at line 97 of file search.cc.

References Search::scored_action::a, and Search::scored_action::s.

 {
   os << x.a << ':' << x.s;
   return os;
 }

◆ operator<<() [2/2]

std::ostream& Search::operator<<	(	std::ostream &	os,
		const action_cache &	x
	)

Definition at line 131 of file search.cc.

References Search::action_cache::cost, Search::action_cache::is_opt, and Search::action_cache::k.

 {
   os << x.k << ':' << x.cost;
   if (x.is_opt)
     os << '*';
   return os;
 }

◆ parse_neighbor_features()

void Search::parse_neighbor_features	(	std::string &	nf_string,
		search &	sch
	)

Definition at line 2627 of file search.cc.

References v_array< T >::clear(), int_of_substring(), Search::search_private::neighbor_features, Search::search::priv, v_array< T >::push_back(), and tokenize().

Referenced by setup().

 {
   search_private& priv = *sch.priv;
   priv.neighbor_features.clear();
   size_t len = nf_string.length();
   if (len == 0)
     return;
 
   char* cstr = new char[len + 1];
   strcpy(cstr, nf_string.c_str());
 
   char* p = strtok(cstr, ",");
   std::vector<substring> cmd;
   while (p != 0)
   {
     cmd.clear();
     substring me = {p, p + strlen(p)};
     tokenize(':', me, cmd, true);
 
     int32_t posn = 0;
     char ns = ' ';
     if (cmd.size() == 1)
     {
       posn = int_of_substring(cmd[0]);
       ns = ' ';
     }
     else if (cmd.size() == 2)
     {
       posn = int_of_substring(cmd[0]);
       ns = (cmd[1].end > cmd[1].begin) ? cmd[1].begin[0] : ' ';
     }
     else
     {
       std::cerr << "warning: ignoring malformed neighbor specification: '" << p << "'" << endl;
     }
     int32_t enc = (posn << 24) | (ns & 0xFF);
     priv.neighbor_features.push_back(enc);
 
     p = strtok(nullptr, ",");
   }
 
   delete[] cstr;
 }

◆ print_update()

void Search::print_update ( search_private & priv )

Definition at line 527 of file search.cc.

Referenced by finish_multiline_example().

 {
   vw& all = *priv.all;
   if (!priv.printed_output_header && !all.quiet)
   {
     const char* header_fmt = "%-10s %-10s %8s%24s %22s %5s %5s  %7s  %7s  %7s  %-8s\n";
     fprintf(stderr, header_fmt, "average", "since", "instance", "current true", "current predicted", "cur", "cur",
         "predic", "cache", "examples", "");
     if (priv.active_csoaa)
       fprintf(stderr, header_fmt, "loss", "last", "counter", "output prefix", "output prefix", "pass", "pol", "made",
           "hits", "gener", "#run");
     else
       fprintf(stderr, header_fmt, "loss", "last", "counter", "output prefix", "output prefix", "pass", "pol", "made",
           "hits", "gener", "beta");
     std::cerr.precision(5);
     priv.printed_output_header = true;
   }
 
   if (!should_print_update(all, priv.hit_new_pass))
     return;
 
   char true_label[21];
   char pred_label[21];
   to_short_string(priv.truth_string->str(), 20, true_label);
   to_short_string(priv.pred_string->str(), 20, pred_label);
 
   float avg_loss = 0.;
   float avg_loss_since = 0.;
   bool use_heldout_loss = (!all.holdout_set_off && all.current_pass >= 1) && (all.sd->weighted_holdout_examples > 0);
   if (use_heldout_loss)
   {
     avg_loss = safediv((float)all.sd->holdout_sum_loss, (float)all.sd->weighted_holdout_examples);
     avg_loss_since = safediv(
         (float)all.sd->holdout_sum_loss_since_last_dump, (float)all.sd->weighted_holdout_examples_since_last_dump);
 
     all.sd->weighted_holdout_examples_since_last_dump = 0;
     all.sd->holdout_sum_loss_since_last_dump = 0.0;
   }
   else
   {
     avg_loss = safediv((float)all.sd->sum_loss, (float)all.sd->weighted_labeled_examples);
     avg_loss_since = safediv((float)all.sd->sum_loss_since_last_dump,
         (float)(all.sd->weighted_labeled_examples - all.sd->old_weighted_labeled_examples));
   }
 
   auto const& inst_cntr = number_to_natural((size_t)all.sd->example_number);
   auto const& total_pred = number_to_natural(priv.total_predictions_made);
   auto const& total_cach = number_to_natural(priv.total_cache_hits);
   auto const& total_exge = number_to_natural(priv.total_examples_generated);
 
   fprintf(stderr, "%-10.6f %-10.6f %8s  [%s] [%s] %5d %5d  %7s  %7s  %7s  %-8f", avg_loss, avg_loss_since,
       inst_cntr.c_str(), true_label, pred_label, (int)priv.read_example_last_pass, (int)priv.current_policy,
       total_pred.c_str(), total_cach.c_str(), total_exge.c_str(),
       priv.active_csoaa ? priv.num_calls_to_run : priv.beta);
 
   if (PRINT_CLOCK_TIME)
   {
     size_t num_sec = (size_t)(((float)(clock() - priv.start_clock_time)) / CLOCKS_PER_SEC);
     std::cerr << " " << num_sec << "sec";
   }
 
   if (use_heldout_loss)
     fprintf(stderr, " h");
 
   fprintf(stderr, "\n");
   fflush(stderr);
   all.sd->update_dump_interval(all.progress_add, all.progress_arg);
 }

◆ push_at()

template<class T >

void Search::push_at	(	v_array< T > &	v,
		T	item,
		size_t	pos
	)

Definition at line 1074 of file search.cc.

References v_array< T >::begin(), v_array< T >::end(), v_array< T >::end_array, v_array< T >::resize(), and v_array< T >::size().

Referenced by Search::search::predict(), Search::search::predictLDF(), and search_predict().

 {
   if (v.size() > pos)
     v.begin()[pos] = item;
   else
   {
     if (v.end_array > v.begin() + pos)
     {
       // there's enough memory, just not enough filler
       memset(v.end(), 0, sizeof(T) * (pos - v.size()));
       v.begin()[pos] = item;
       v.end() = v.begin() + pos + 1;
     }
     else
     {
       // there's not enough memory
       v.resize(2 * pos + 3);
       v.begin()[pos] = item;
       v.end() = v.begin() + pos + 1;
     }
   }
 }

◆ random()

size_t Search::random	(	std::shared_ptr< rand_state > &	rs,
		size_t	max
	)

Definition at line 768 of file search.cc.

Referenced by choose_oracle_action().

 {
   return (size_t)(rs->get_and_update_random() * (float)max);
 }

◆ random_policy()

int Search::random_policy	(	search_private &	priv,
		bool	allow_current,
		bool	allow_optimal,
		bool	advance_prng = `true`
	)

Definition at line 376 of file search.cc.

References Search::search_private::_random_state, Search::search_private::beta, Search::search_private::current_policy, f, and ldamath::powf().

Referenced by choose_policy().

 {
   if (priv.beta >= 1)
   {
     if (allow_current)
       return (int)priv.current_policy;
     if (priv.current_policy > 0)
       return (((int)priv.current_policy) - 1);
     if (allow_optimal)
       return -1;
     std::cerr << "internal error (bug): no valid policies to choose from!  defaulting to current" << endl;
     return (int)priv.current_policy;
   }
 
   int num_valid_policies = (int)priv.current_policy + allow_optimal + allow_current;
   int pid = -1;
 
   if (num_valid_policies == 0)
   {
     std::cerr << "internal error (bug): no valid policies to choose from!  defaulting to current" << endl;
     return (int)priv.current_policy;
   }
   else if (num_valid_policies == 1)
     pid = 0;
   else if (num_valid_policies == 2)
     pid = (advance_prng ? priv._random_state->get_and_update_random() : priv._random_state->get_random()) >= priv.beta;
   else
   {
     // SPEEDUP this up in the case that beta is small!
     float r = (advance_prng ? priv._random_state->get_and_update_random() : priv._random_state->get_random());
     pid = 0;
 
     if (r > priv.beta)
     {
       r -= priv.beta;
       while ((r > 0) && (pid < num_valid_policies - 1))
       {
         pid++;
         r -= priv.beta * powf(1.f - priv.beta, (float)pid);
       }
     }
   }
   // figure out which policy pid refers to
   if (allow_optimal && (pid == num_valid_policies - 1))
     return -1;  // this is the optimal policy
 
   pid = (int)priv.current_policy - pid;
   if (!allow_current)
     pid--;
 
   return pid;
 }

◆ read_allowed_transitions()

v_array<CS::label> Search::read_allowed_transitions	(	action	A,
		const char *	filename
	)

Definition at line 2579 of file search.cc.

References c, f, v_array< T >::push_back(), and THROW.

Referenced by setup().

 {
   FILE* f = fopen(filename, "r");
   if (f == nullptr)
     THROW("error: could not read file " << filename << " (" << strerror(errno)
                                         << "); assuming all transitions are valid");
 
   bool* bg = calloc_or_throw<bool>(((size_t)(A + 1)) * (A + 1));
   int rd, from, to, count = 0;
   while ((rd = fscanf(f, "%d:%d", &from, &to)) > 0)
   {
     if ((from < 0) || (from > (int)A))
     {
       std::cerr << "warning: ignoring transition from " << from << " because it's out of the range [0," << A << "]"
                 << endl;
     }
     if ((to < 0) || (to > (int)A))
     {
       std::cerr << "warning: ignoring transition to " << to << " because it's out of the range [0," << A << "]" << endl;
     }
     bg[from * (A + 1) + to] = true;
     count++;
   }
   fclose(f);
 
   v_array<CS::label> allowed = v_init<CS::label>();
 
   for (size_t from = 0; from < A; from++)
   {
     v_array<CS::wclass> costs = v_init<CS::wclass>();
 
     for (size_t to = 0; to < A; to++)
       if (bg[from * (A + 1) + to])
       {
         CS::wclass c = {FLT_MAX, (action)to, 0., 0.};
         costs.push_back(c);
       }
 
     CS::label ld = {costs};
     allowed.push_back(ld);
   }
   free(bg);
 
   std::cerr << "read " << count << " allowed transitions from " << filename << endl;
 
   return allowed;
 }

◆ reset_search_structure()

void Search::reset_search_structure ( search_private & priv )

Definition at line 690 of file search.cc.

Referenced by do_actual_learning(), and train_single_example().

 {
   // NOTE: make sure do NOT reset priv.learn_a_idx
   priv.t = 0;
   priv.meta_t = 0;
   priv.loss_declared_cnt = 0;
   priv.done_with_all_actions = false;
   priv.test_loss = 0.;
   priv.learn_loss = 0.;
   priv.train_loss = 0.;
   priv.num_features = 0;
   priv.should_produce_string = false;
   priv.mix_per_roll_policy = -2;
   priv.force_setup_ec_ref = false;
   if (priv.adaptive_beta)
   {
     float x = -log1pf(-priv.alpha) * (float)priv.total_examples_generated;
     static constexpr float log_of_2 = (float)0.6931471805599453;
     priv.beta = (x <= log_of_2) ? -expm1f(-x) : (1 - expf(-x));  // numerical stability
     // float priv_beta = 1.f - powf(1.f - priv.alpha, (float)priv.total_examples_generated);
     // assert( fabs(priv_beta - priv.beta) < 1e-2 );
     if (priv.beta > 1)
       priv.beta = 1;
   }
   for (Search::action_repr& ar : priv.ptag_to_action)
   {
     if (ar.repr != nullptr)
     {
       ar.repr->delete_v();
       delete ar.repr;
     }
   }
   priv.ptag_to_action.clear();
 
   if (!priv.cb_learner)  // was: if rollout_all_actions
   {
     priv._random_state->set_random_state((uint32_t)(priv.read_example_last_id * 147483 + 4831921) * 2147483647);
   }
 }

◆ run_task()

void Search::run_task	(	search &	sch,
		multi_ex &	ec
	)

Definition at line 2098 of file search.cc.

References GET_TRUTH_STRING, Search::search_private::metatask, Search::search_private::num_calls_to_run, Search::search::priv, Search::search_task::run, Search::search_metatask::run, Search::search_private::state, and Search::search_private::task.

Referenced by do_actual_learning(), and train_single_example().

 {
   search_private& priv = *sch.priv;
   priv.num_calls_to_run++;
   if (priv.metatask && (priv.state != GET_TRUTH_STRING))
     priv.metatask->run(sch, ec);
   else
     priv.task->run(sch, ec);
 }

◆ safediv()

float Search::safediv	(	float	a,
		float	b
	)

Definition at line 491 of file search.cc.

References f.

Referenced by print_update().

 {
   if (b == 0.f)
     return 0.f;
   else
     return (a / b);
 }

◆ search_declare_loss()

void Search::search_declare_loss	(	search_private &	priv,
		float	loss
	)

Definition at line 730 of file search.cc.

References cdbg, INIT_TEST, INIT_TRAIN, LEARN, Search::search_private::learn_loss, loss(), Search::search_private::loss_declared_cnt, Search::search_private::rollout_num_steps, Search::search_private::state, Search::search_private::test_loss, and Search::search_private::train_loss.

Referenced by Search::search::loss().

 {
   priv.loss_declared_cnt++;
   switch (priv.state)
   {
     case INIT_TEST:
       priv.test_loss += loss;
       break;
     case INIT_TRAIN:
       priv.train_loss += loss;
       break;
     case LEARN:
       if ((priv.rollout_num_steps == 0) || (priv.loss_declared_cnt <= priv.rollout_num_steps))
       {
         priv.learn_loss += loss;
         cdbg << "priv.learn_loss += " << loss << " (now = " << priv.learn_loss << ")" << endl;
       }
       break;
     default:
       break;  // get rid of the warning about missing cases (danger!)
   }
 }

◆ search_finish()

void Search::search_finish ( search & sch )

Definition at line 2565 of file search.cc.

References Search::search_private::active_csoaa, cdbg, Search::search_task::finish, Search::search_metatask::finish, Search::search_private::metatask, Search::search_private::num_calls_to_run, Search::search::priv, and Search::search_private::task.

Referenced by setup().

 {
   search_private& priv = *sch.priv;
   cdbg << "search_finish" << endl;
 
   if (priv.active_csoaa)
     std::cerr << "search calls to run = " << priv.num_calls_to_run << endl;
 
   if (priv.task->finish)
     priv.task->finish(sch);
   if (priv.metatask && priv.metatask->finish)
     priv.metatask->finish(sch);
 }

◆ search_initialize()

void Search::search_initialize	(	vw *	all,
		search &	sch
	)

Definition at line 2486 of file search.cc.

Referenced by setup().

 {
   search_private& priv = *sch.priv;  // priv is zero initialized by default
   priv.all = all;
   priv._random_state = all->get_random_state();
 
   priv.active_csoaa = false;
   priv.label_is_test = mc_label_is_test;
 
   priv.num_learners = 1;
   priv.state = INITIALIZE;
   priv.mix_per_roll_policy = -2;
 
   priv.pred_string = new std::stringstream();
   priv.truth_string = new std::stringstream();
   priv.bad_string_stream = new std::stringstream();
   priv.bad_string_stream->clear(priv.bad_string_stream->badbit);
 
   priv.rollout_method = MIX_PER_ROLL;
   priv.rollin_method = MIX_PER_ROLL;
 
   priv.allow_current_policy = true;
   priv.adaptive_beta = true;
 
   priv.total_number_of_policies = 1;
 
   priv.acset.max_bias_ngram_length = 1;
 
   priv.acset.feature_value = 1.;
 
   scored_action sa((action)-1, 0.);
   new (&priv.cache_hash_map) v_hashmap<unsigned char*, scored_action>();
   priv.cache_hash_map.set_default_value(sa);
   priv.cache_hash_map.set_equivalent(cached_item_equivalent);
 
   sch.task_data = nullptr;
 
   priv.active_uncertainty = v_init<std::pair<float, size_t>>();
   priv.active_known = v_init<v_array<std::pair<CS::wclass&, bool>>>();
 
   CS::cs_label.default_label(&priv.empty_cs_label);
 
   new (&priv.rawOutputString) std::string();
   priv.rawOutputStringStream = new std::stringstream(priv.rawOutputString);
   new (&priv.test_action_sequence) std::vector<action>();
   new (&priv.dat_new_feature_audit_ss) std::stringstream();
 }

◆ search_predict()

action Search::search_predict	(	search_private &	priv,
		example *	ecs,
		size_t	ec_cnt,
		ptag	mytag,
		const action *	oracle_actions,
		size_t	oracle_actions_cnt,
		const ptag *	condition_on,
		const char *	condition_on_names,
		const action *	allowed_actions,
		size_t	allowed_actions_cnt,
		const float *	allowed_actions_cost,
		size_t	learner_id,
		float &	a_cost,
		float
	)

Definition at line 1652 of file search.cc.

Referenced by Search::search::predict(), and Search::search::predictLDF().

 {
   size_t condition_on_cnt = condition_on_names ? strlen(condition_on_names) : 0;
   size_t t = priv.t + priv.meta_t;
   priv.t++;
 
   // make sure parameters come in pairs correctly
   assert((oracle_actions == nullptr) == (oracle_actions_cnt == 0));
   assert((condition_on == nullptr) == (condition_on_names == nullptr));
   assert(((allowed_actions == nullptr) && (allowed_actions_cost == nullptr)) == (allowed_actions_cnt == 0));
   assert(priv.use_action_costs == (allowed_actions_cost != nullptr));
   if (allowed_actions_cost != nullptr)
     assert(oracle_actions == nullptr);
 
   // if we're just after the string, choose an oracle action
   if ((priv.state == GET_TRUTH_STRING) || priv.force_oracle)
   {
     action a = choose_oracle_action(
         priv, ec_cnt, oracle_actions, oracle_actions_cnt, allowed_actions, allowed_actions_cnt, allowed_actions_cost);
     // if (priv.metaoverride && priv.metaoverride->_post_prediction)
     //  priv.metaoverride->_post_prediction(*priv.metaoverride->sch, t-priv.meta_t, a, 0.);
     a_cost = 0.;
     return a;
   }
 
   // if we're in LEARN mode and before learn_t, return the train action
   if ((priv.state == LEARN) && (t < priv.learn_t))
   {
     assert(t < priv.train_trajectory.size());
     action a = priv.train_trajectory[t].a;
     a_cost = priv.train_trajectory[t].s;
     cdbg << "LEARN " << t << " < priv.learn_t ==> a=" << a << ", a_cost=" << a_cost << endl;
     if (priv.metaoverride && priv.metaoverride->_foreach_action)
       foreach_action_from_cache(priv, t);
     if (priv.metaoverride && priv.metaoverride->_post_prediction)
       priv.metaoverride->_post_prediction(*priv.metaoverride->sch, t - priv.meta_t, a, a_cost);
     return a;
   }
 
   // for LDF, # of valid actions is ec_cnt; otherwise it's either allowed_actions_cnt or A
   size_t valid_action_cnt = priv.is_ldf ? ec_cnt : (allowed_actions_cnt > 0) ? allowed_actions_cnt : priv.A;
 
   // if we're in LEARN mode and _at_ learn_t, then:
   //   - choose the next action
   //   - decide if we're done
   //   - if we are, then copy/mark the example ref
   if ((priv.state == LEARN) && (t == priv.learn_t))
   {
     action a = (action)priv.learn_a_idx;
     priv.loss_declared_cnt = 0;
 
     cdbg << "LEARN " << t << " = priv.learn_t ==> a=" << a << ", learn_a_idx=" << priv.learn_a_idx
          << " valid_action_cnt=" << valid_action_cnt << endl;
     priv.learn_a_idx++;
 
     // check to see if we're done with available actions
     if (priv.learn_a_idx >= valid_action_cnt)
     {
       priv.done_with_all_actions = true;
       priv.learn_learner_id = learner_id;
 
       // set reference or copy example(s)
       if (oracle_actions_cnt > 0)
         priv.learn_oracle_action = oracle_actions[0];
       priv.learn_ec_ref_cnt = ec_cnt;
       if (priv.examples_dont_change)
         priv.learn_ec_ref = ecs;
       else
       {
         size_t label_size = priv.is_ldf ? sizeof(CS::label) : sizeof(MC::label_t);
         void (*label_copy_fn)(void*, void*) = priv.is_ldf ? CS::cs_label.copy_label : nullptr;
 
         ensure_size(priv.learn_ec_copy, ec_cnt);
         for (size_t i = 0; i < ec_cnt; i++)
           VW::copy_example_data(priv.all->audit, priv.learn_ec_copy.begin() + i, ecs + i, label_size, label_copy_fn);
 
         priv.learn_ec_ref = priv.learn_ec_copy.begin();
       }
 
       // copy conditioning stuff and allowed actions
       if (priv.auto_condition_features)
       {
         ensure_size(priv.learn_condition_on, condition_on_cnt);
         ensure_size(priv.learn_condition_on_act, condition_on_cnt);
 
         priv.learn_condition_on.end() =
             priv.learn_condition_on.begin() + condition_on_cnt;  // allow .size() to be used in lieu of _cnt
 
         memcpy(priv.learn_condition_on.begin(), condition_on, condition_on_cnt * sizeof(ptag));
 
         for (size_t i = 0; i < condition_on_cnt; i++)
           push_at(priv.learn_condition_on_act,
               action_repr(((1 <= condition_on[i]) && (condition_on[i] < priv.ptag_to_action.size()))
                       ? priv.ptag_to_action[condition_on[i]]
                       : 0),
               i);
 
         if (condition_on_names == nullptr)
         {
           ensure_size(priv.learn_condition_on_names, 1);
           priv.learn_condition_on_names[0] = 0;
         }
         else
         {
           ensure_size(priv.learn_condition_on_names, strlen(condition_on_names) + 1);
           strcpy(priv.learn_condition_on_names.begin(), condition_on_names);
         }
       }
 
       if (allowed_actions && (allowed_actions_cnt > 0))
       {
         ensure_size(priv.learn_allowed_actions, allowed_actions_cnt);
         memcpy(priv.learn_allowed_actions.begin(), allowed_actions, allowed_actions_cnt * sizeof(action));
         cdbg_print_array("in LEARN, learn_allowed_actions", priv.learn_allowed_actions);
       }
     }
 
     assert((allowed_actions_cnt == 0) || (a < allowed_actions_cnt));
 
     a_cost = 0.;
     action a_name = (allowed_actions && (allowed_actions_cnt > 0)) ? allowed_actions[a] : priv.is_ldf ? a : (a + 1);
     if (priv.metaoverride && priv.metaoverride->_foreach_action)
     {
       foreach_action_from_cache(priv, t, a_name);
       if (priv.memo_foreach_action[t])
       {
         cdbg << "@ memo_foreach_action: t=" << t << ", a=" << a << ", cost=" << (*priv.memo_foreach_action[t])[a].cost
              << endl;
         a_cost = (*priv.memo_foreach_action[t])[a].cost;
       }
     }
 
     a = a_name;
 
     if (priv.metaoverride && priv.metaoverride->_post_prediction)
       priv.metaoverride->_post_prediction(*priv.metaoverride->sch, t - priv.meta_t, a, a_cost);
     return a;
   }
 
   if ((priv.state == LEARN) && (t > priv.learn_t) && (priv.rollout_num_steps > 0) &&
       (priv.loss_declared_cnt >= priv.rollout_num_steps))
   {
     cdbg << "... skipping" << endl;
     action a = priv.is_ldf ? 0 : ((allowed_actions && (allowed_actions_cnt > 0)) ? allowed_actions[0] : 1);
     if (priv.metaoverride && priv.metaoverride->_post_prediction)
       priv.metaoverride->_post_prediction(*priv.metaoverride->sch, t - priv.meta_t, a, 0.);
     if (priv.metaoverride && priv.metaoverride->_foreach_action)
       foreach_action_from_cache(priv, t);
     a_cost = 0.;
     return a;
   }
 
   if ((priv.state == INIT_TRAIN) || (priv.state == INIT_TEST) || ((priv.state == LEARN) && (t > priv.learn_t)))
   {
     // we actually need to run the policy
 
     int policy = choose_policy(priv);
     action a = 0;
 
     cdbg << "executing policy " << policy << endl;
 
     bool gte_here = (priv.state == INIT_TRAIN) && (priv.rollout_method == NO_ROLLOUT) &&
         ((oracle_actions_cnt > 0) || (priv.use_action_costs));
     a_cost = 0.;
     bool skip = false;
 
     if (priv.metaoverride && priv.metaoverride->_maybe_override_prediction &&
         (priv.state != LEARN))  // if LEARN and t>learn_t,then we cannot allow overrides!
     {
       skip = priv.metaoverride->_maybe_override_prediction(*priv.metaoverride->sch, t - priv.meta_t, a, a_cost);
       cdbg << "maybe_override_prediction --> " << skip << ", a=" << a << ", a_cost=" << a_cost << endl;
       if (skip && need_memo_foreach_action(priv))
         priv.memo_foreach_action.push_back(nullptr);
     }
 
     if ((!skip) && (policy == -1))
       a = choose_oracle_action(priv, ec_cnt, oracle_actions, oracle_actions_cnt, allowed_actions, allowed_actions_cnt,
           allowed_actions_cost);  // TODO: we probably want to actually get costs for oracle actions???
 
     bool need_fea = (policy == -1) && priv.metaoverride && priv.metaoverride->_foreach_action;
 
     if ((policy >= 0) || gte_here || need_fea)  // the last case is we need to do foreach action
     {
       int learner = select_learner(priv, policy, learner_id, false, priv.state != INIT_TEST);
 
       ensure_size(priv.condition_on_actions, condition_on_cnt);
       for (size_t i = 0; i < condition_on_cnt; i++)
         priv.condition_on_actions[i] = ((1 <= condition_on[i]) && (condition_on[i] < priv.ptag_to_action.size()))
             ? priv.ptag_to_action[condition_on[i]]
             : 0;
 
       bool not_test = priv.all->training && !ecs[0].test_only;
 
       if ((!skip) && (!need_fea) && not_test &&
           cached_action_store_or_find(priv, mytag, condition_on, condition_on_names, priv.condition_on_actions.begin(),
               condition_on_cnt, policy, learner_id, a, false, a_cost))
         // if this succeeded, 'a' has the right action
         priv.total_cache_hits++;
       else  // we need to predict, and then cache, and maybe run foreach_action
       {
         size_t start_K = (priv.is_ldf && COST_SENSITIVE::ec_is_example_header(ecs[0])) ? 1 : 0;
         priv.last_action_repr.clear();
         if (priv.auto_condition_features)
           for (size_t n = start_K; n < ec_cnt; n++)
             add_example_conditioning(
                 priv, ecs[n], condition_on_cnt, condition_on_names, priv.condition_on_actions.begin());
 
         if (((!skip) && (policy >= 0)) || need_fea)  // only make a prediction if we're going to use the output
         {
           if (priv.auto_condition_features && priv.acset.use_passthrough_repr)
           {
             if (priv.is_ldf)
             {
               THROW("search cannot use state representations in ldf mode");
             }
             if (ecs[0].passthrough)
             {
               THROW("search cannot passthrough");
             }
             ecs[0].passthrough = &priv.last_action_repr;
           }
           a = priv.is_ldf ? single_prediction_LDF(priv, ecs, ec_cnt, learner, a_cost, need_fea ? a : (action)-1)
                           : single_prediction_notLDF(priv, *ecs, learner, allowed_actions, allowed_actions_cnt,
                                 allowed_actions_cost, a_cost, need_fea ? a : (action)-1);
 
           cdbg << "passthrough = [";
           for (size_t kk = 0; kk < priv.last_action_repr.size(); kk++)
             cdbg << ' ' << priv.last_action_repr.indicies[kk] << ':' << priv.last_action_repr.values[kk];
           cdbg << " ]" << endl;
 
           ecs[0].passthrough = nullptr;
         }
 
         if (need_fea)
         {
           // TODO this
         }
 
         if (gte_here)
         {
           cdbg << "INIT_TRAIN, NO_ROLLOUT, at least one oracle_actions, a=" << a << endl;
           // we can generate a training example _NOW_ because we're not doing rollouts
           // allowed_actions_to_losses(priv, ec_cnt, allowed_actions, allowed_actions_cnt, oracle_actions,
           // oracle_actions_cnt, losses);
           allowed_actions_to_label(priv, ec_cnt, allowed_actions, allowed_actions_cnt, allowed_actions_cost,
               oracle_actions, oracle_actions_cnt, priv.gte_label);
           cdbg << "priv.gte_label = [";
           for (size_t i = 0; i < priv.gte_label.cs.costs.size(); i++)
             cdbg << ' ' << priv.gte_label.cs.costs[i].class_index << ':' << priv.gte_label.cs.costs[i].x;
           cdbg << " ]" << endl;
 
           priv.learn_ec_ref = ecs;
           priv.learn_ec_ref_cnt = ec_cnt;
           if (allowed_actions)
           {
             ensure_size(priv.learn_allowed_actions, allowed_actions_cnt);  // TODO: do we really need this?
             memcpy(priv.learn_allowed_actions.begin(), allowed_actions, allowed_actions_cnt * sizeof(action));
           }
           size_t old_learner_id = priv.learn_learner_id;
           priv.learn_learner_id = learner_id;
           generate_training_example(
               priv, priv.gte_label, 1., false);  // this is false because the conditioning has already been added!
           priv.learn_learner_id = old_learner_id;
         }
 
         if (priv.auto_condition_features)
           for (size_t n = start_K; n < ec_cnt; n++) del_example_conditioning(priv, ecs[n]);
 
         if (not_test && (!skip))
           cached_action_store_or_find(priv, mytag, condition_on, condition_on_names, priv.condition_on_actions.begin(),
               condition_on_cnt, policy, learner_id, a, true, a_cost);
       }
     }
 
     if (priv.state == INIT_TRAIN)
       priv.train_trajectory.push_back(scored_action(a, a_cost));  // note the action for future reference
 
     if (priv.metaoverride && priv.metaoverride->_post_prediction)
       priv.metaoverride->_post_prediction(*priv.metaoverride->sch, t - priv.meta_t, a, a_cost);
 
     return a;
   }
 
   THROW("error: predict called in unknown state");
 }

◆ search_predictNeedsExample()

bool Search::search_predictNeedsExample ( search_private & priv )

Definition at line 1601 of file search.cc.

References choose_policy(), GET_TRUTH_STRING, INIT_TEST, INIT_TRAIN, INITIALIZE, LEARN, Search::search_private::learn_t, Search::search_private::loss_declared_cnt, Search::search_private::meta_t, NO_ROLLOUT, Search::search_private::rollout_method, Search::search_private::rollout_num_steps, Search::search_private::state, and Search::search_private::t.

Referenced by Search::search::predictNeedsExample().

 {
   // this is basically copied from the logic of search_predict()
   switch (priv.state)
   {
     case INITIALIZE:
       return false;
     case GET_TRUTH_STRING:
       return false;
     case INIT_TEST:
       return true;
     case INIT_TRAIN:
       // TODO: do we need to do something here for metatasks?
       // if (priv.beam && (priv.t < priv.beam_actions.size()))
       //  return false;
       if (priv.rollout_method == NO_ROLLOUT)
         return true;
       break;
     case LEARN:
       if (priv.t + priv.meta_t < priv.learn_t)
         return false;  // TODO: in meta search mode with foreach feature we'll need it even here
       if (priv.t + priv.meta_t == priv.learn_t)
         return true;  // SPEEDUP: we really only need it on the last learn_a, but this is hard to know...
       // t > priv.learn_t
       if ((priv.rollout_num_steps > 0) && (priv.loss_declared_cnt >= priv.rollout_num_steps))
         return false;  // skipping
       break;
   }
 
   int pol = choose_policy(priv, false);  // choose a policy but don't advance prng
   return (pol != -1);
 }

◆ select_learner()

int Search::select_learner	(	search_private &	priv,
		int	policy,
		size_t	learner_id,
		bool	is_training,
		bool	is_local
	)

Definition at line 432 of file search.cc.

References Search::search_private::all, shared_data::example_number, Search::search_private::num_learners, vw::sd, and Search::search_private::xv.

Referenced by generate_training_example(), and search_predict().

 {
   if (policy < 0)
     return policy;  // optimal policy
   else
   {
     if (priv.xv)
     {
       learner_id *= 3;
       if (!is_local)
         learner_id += 1 + (size_t)(is_training ^ (priv.all->sd->example_number % 2 == 1));
     }
     int p = (int)(policy * priv.num_learners + learner_id);
     return p;
   }
 }

◆ setup()

LEARNER::base_learner * Search::setup	(	options_i &	options,
		vw &	all
	)

Definition at line 2671 of file search.cc.

References Search::search_private::A, VW::config::option_group_definition::add(), VW::config::options_i::add_and_parse(), CB::cb_label, cdbg, vw::check_holdout_every_n_passes, COST_SENSITIVE::cs_label, label_parser::default_label, parser::emptylines_separate_examples, end_examples(), LEARNER::end_pass(), ensure_param(), f, finish_multiline_example(), VW::config::options_i::get_typed_option(), handle_condition_options(), LEARNER::init_learner(), VW::config::options_i::insert(), vw::label_type, parser::lp, LEARNER::make_base(), VW::config::make_option(), label_type::mc, MULTICLASS::mc_label, MIX_PER_ROLL, MIX_PER_STATE, NO_ROLLOUT, vw::numpasses, vw::options, ORACLE, vw::p, parse_neighbor_features(), POLICY, read_allowed_transitions(), VW::config::options_i::replace(), search_finish(), search_initialize(), vw::searchstr, LEARNER::learner< T, E >::set_end_examples(), LEARNER::learner< T, E >::set_end_pass(), LEARNER::learner< T, E >::set_finish(), LEARNER::learner< T, E >::set_finish_example(), setup_base(), THROW, prediction_type::to_string(), vw::training, and VW::config::options_i::was_supplied().

Referenced by parse_reductions().

 {
   free_ptr<search> sch = scoped_calloc_or_throw<search>();
   search_private& priv = *sch->priv;
   std::string task_string;
   std::string metatask_string;
   std::string interpolation_string = "data";
   std::string neighbor_features_string;
   std::string rollout_string = "mix_per_state";
   std::string rollin_string = "mix_per_state";
 
   uint32_t search_trained_nb_policies;
   std::string search_allowed_transitions;
 
   priv.A = 1;
   option_group_definition new_options("Search options");
   new_options.add(
       make_option("search", priv.A).keep().help("Use learning to search, argument=maximum action id or 0 for LDF"));
   new_options.add(make_option("search_task", task_string)
                       .keep()
                       .help("the search task (use \"--search_task list\" to get a list of available tasks)"));
   new_options.add(
       make_option("search_metatask", metatask_string)
           .keep()
           .help("the search metatask (use \"--search_metatask list\" to get a list of available metatasks)"));
   new_options.add(make_option("search_interpolation", interpolation_string)
                       .keep()
                       .help("at what level should interpolation happen? [*data|policy]"));
   new_options.add(
       make_option("search_rollout", rollout_string)
           .help("how should rollouts be executed?           [policy|oracle|*mix_per_state|mix_per_roll|none]"));
   new_options.add(make_option("search_rollin", rollin_string)
                       .help("how should past trajectories be generated? [policy|oracle|*mix_per_state|mix_per_roll]"));
   new_options.add(make_option("search_passes_per_policy", priv.passes_per_policy)
                       .default_value(1)
                       .help("number of passes per policy (only valid for search_interpolation=policy)"));
   new_options.add(make_option("search_beta", priv.beta)
                       .default_value(0.5f)
                       .help("interpolation rate for policies (only valid for search_interpolation=policy)"));
   new_options.add(make_option("search_alpha", priv.alpha)
                       .default_value(1e-10f)
                       .help("annealed beta = 1-(1-alpha)^t (only valid for search_interpolation=data)"));
   new_options.add(make_option("search_total_nb_policies", priv.total_number_of_policies)
                       .help("if we are going to train the policies through multiple separate calls to vw, we need to "
                             "specify this parameter and tell vw how many policies are eventually going to be trained"));
   new_options.add(make_option("search_trained_nb_policies", search_trained_nb_policies)
                       .help("the number of trained policies in a file"));
   new_options.add(make_option("search_allowed_transitions", search_allowed_transitions)
                       .help("read file of allowed transitions [def: all transitions are allowed]"));
   new_options.add(make_option("search_subsample_time", priv.subsample_timesteps)
                       .help("instead of training at all timesteps, use a subset. if value in (0,1), train on a random "
                             "v%. if v>=1, train on precisely v steps per example, if v<=-1, use active learning"));
   new_options.add(
       make_option("search_neighbor_features", neighbor_features_string)
           .keep()
           .help("copy features from neighboring lines. argument looks like: '-1:a,+2' meaning copy previous line "
                 "namespace a and next next line from namespace _unnamed_, where ',' separates them"));
   new_options.add(make_option("search_rollout_num_steps", priv.rollout_num_steps)
                       .help("how many calls of \"loss\" before we stop really predicting on rollouts and switch to "
                             "oracle (default means \"infinite\")"));
   new_options.add(make_option("search_history_length", priv.history_length)
                       .keep()
                       .default_value(1)
                       .help("some tasks allow you to specify how much history their depend on; specify that here"));
   new_options.add(make_option("search_no_caching", priv.no_caching)
                       .help("turn off the built-in caching ability (makes things slower, but technically more safe)"));
   new_options.add(
       make_option("search_xv", priv.xv).help("train two separate policies, alternating prediction/learning"));
   new_options.add(make_option("search_perturb_oracle", priv.perturb_oracle)
                       .default_value(0.f)
                       .help("perturb the oracle on rollin with this probability"));
   new_options.add(make_option("search_linear_ordering", priv.linear_ordering)
                       .help("insist on generating examples in linear order (def: hoopla permutation)"));
   new_options.add(make_option("search_active_verify", priv.active_csoaa_verify)
                       .help("verify that active learning is doing the right thing (arg = multiplier, should be = "
                             "cost_range * range_c)"));
   new_options.add(make_option("search_save_every_k_runs", priv.save_every_k_runs).help("save model every k runs"));
   options.add_and_parse(new_options);
 
   if (!options.was_supplied("search_task"))
     return nullptr;
 
   search_initialize(&all, *sch.get());
 
   parse_neighbor_features(neighbor_features_string, *sch.get());
 
   if (interpolation_string.compare("data") == 0)  // run as dagger
   {
     priv.adaptive_beta = true;
     priv.allow_current_policy = true;
     priv.passes_per_policy = all.numpasses;
     if (priv.current_policy > 1)
       priv.current_policy = 1;
   }
   else if (interpolation_string.compare("policy") == 0)
     ;
   else
     THROW("error: --search_interpolation must be 'data' or 'policy'");
 
   if ((rollout_string.compare("policy") == 0) || (rollout_string.compare("learn") == 0))
     priv.rollout_method = POLICY;
   else if ((rollout_string.compare("oracle") == 0) || (rollout_string.compare("ref") == 0))
     priv.rollout_method = ORACLE;
   else if ((rollout_string.compare("mix_per_state") == 0))
     priv.rollout_method = MIX_PER_STATE;
   else if ((rollout_string.compare("mix_per_roll") == 0) || (rollout_string.compare("mix") == 0))
     priv.rollout_method = MIX_PER_ROLL;
   else if ((rollout_string.compare("none") == 0))
   {
     priv.rollout_method = NO_ROLLOUT;
     priv.no_caching = true;
   }
   else
     THROW("error: --search_rollout must be 'learn', 'ref', 'mix', 'mix_per_state' or 'none'");
 
   if ((rollin_string.compare("policy") == 0) || (rollin_string.compare("learn") == 0))
     priv.rollin_method = POLICY;
   else if ((rollin_string.compare("oracle") == 0) || (rollin_string.compare("ref") == 0))
     priv.rollin_method = ORACLE;
   else if ((rollin_string.compare("mix_per_state") == 0))
     priv.rollin_method = MIX_PER_STATE;
   else if ((rollin_string.compare("mix_per_roll") == 0) || (rollin_string.compare("mix") == 0))
     priv.rollin_method = MIX_PER_ROLL;
   else
     THROW("error: --search_rollin must be 'learn', 'ref', 'mix' or 'mix_per_state'");
 
   // check if the base learner is contextual bandit, in which case, we dont rollout all actions.
   priv.allowed_actions_cache = &calloc_or_throw<polylabel>();
   if (options.was_supplied("cb"))
   {
     priv.cb_learner = true;
     CB::cb_label.default_label(priv.allowed_actions_cache);
     priv.learn_losses.cb.costs = v_init<CB::cb_class>();
     priv.gte_label.cb.costs = v_init<CB::cb_class>();
   }
   else
   {
     priv.cb_learner = false;
     CS::cs_label.default_label(priv.allowed_actions_cache);
     priv.learn_losses.cs.costs = v_init<CS::wclass>();
     priv.gte_label.cs.costs = v_init<CS::wclass>();
   }
 
   ensure_param(priv.beta, 0.0, 1.0, 0.5, "warning: search_beta must be in (0,1); resetting to 0.5");
   ensure_param(priv.alpha, 0.0, 1.0, 1e-10f, "warning: search_alpha must be in (0,1); resetting to 1e-10");
 
   priv.num_calls_to_run = 0;
 
   // compute total number of policies we will have at end of training
   // we add current_policy for cases where we start from an initial set of policies loaded through -i option
   uint32_t tmp_number_of_policies = priv.current_policy;
   if (all.training)
     tmp_number_of_policies += (int)ceil(((float)all.numpasses) / ((float)priv.passes_per_policy));
 
   // the user might have specified the number of policies that will eventually be trained through multiple vw calls,
   // so only set total_number_of_policies to computed value if it is larger
   cdbg << "current_policy=" << priv.current_policy << " tmp_number_of_policies=" << tmp_number_of_policies
        << " total_number_of_policies=" << priv.total_number_of_policies << endl;
   if (tmp_number_of_policies > priv.total_number_of_policies)
   {
     priv.total_number_of_policies = tmp_number_of_policies;
     if (priv.current_policy >
         0)  // we loaded a file but total number of policies didn't match what is needed for training
       std::cerr << "warning: you're attempting to train more classifiers than was allocated initially. Likely to cause "
                    "bad performance."
                 << endl;
   }
 
   // current policy currently points to a new policy we would train
   // if we are not training and loaded a bunch of policies for testing, we need to subtract 1 from current policy
   // so that we only use those loaded when testing (as run_prediction is called with allow_current to true)
   if (!all.training && priv.current_policy > 0)
     priv.current_policy--;
 
   all.options->replace("search_trained_nb_policies", std::to_string(priv.current_policy));
   all.options->get_typed_option<uint32_t>("search_trained_nb_policies").value(priv.current_policy);
 
   all.options->replace("search_total_nb_policies", std::to_string(priv.total_number_of_policies));
   all.options->get_typed_option<uint32_t>("search_total_nb_policies").value(priv.total_number_of_policies);
 
   cdbg << "search current_policy = " << priv.current_policy
        << " total_number_of_policies = " << priv.total_number_of_policies << endl;
 
   if (task_string.compare("list") == 0)
   {
     std::cerr << endl << "available search tasks:" << endl;
     for (search_task** mytask = all_tasks; *mytask != nullptr; mytask++)
       std::cerr << "  " << (*mytask)->task_name << endl;
     std::cerr << endl;
     exit(0);
   }
   if (metatask_string.compare("list") == 0)
   {
     std::cerr << endl << "available search metatasks:" << endl;
     for (search_metatask** mytask = all_metatasks; *mytask != nullptr; mytask++)
       std::cerr << "  " << (*mytask)->metatask_name << endl;
     std::cerr << endl;
     exit(0);
   }
   for (search_task** mytask = all_tasks; *mytask != nullptr; mytask++)
     if (task_string.compare((*mytask)->task_name) == 0)
     {
       priv.task = *mytask;
       sch->task_name = (*mytask)->task_name;
       break;
     }
   if (priv.task == nullptr)
   {
     if (!options.was_supplied("help"))
       THROW("fail: unknown task for --search_task '" << task_string << "'; use --search_task list to get a list");
   }
   priv.metatask = nullptr;
   for (search_metatask** mytask = all_metatasks; *mytask != nullptr; mytask++)
     if (metatask_string.compare((*mytask)->metatask_name) == 0)
     {
       priv.metatask = *mytask;
       sch->metatask_name = (*mytask)->metatask_name;
       break;
     }
   all.p->emptylines_separate_examples = true;
 
   if (!options.was_supplied("csoaa") && !options.was_supplied("cs_active") && !options.was_supplied("csoaa_ldf") &&
       !options.was_supplied("wap_ldf") && !options.was_supplied("cb"))
   {
     options.insert("csoaa", std::to_string(priv.A));
   }
 
   priv.active_csoaa = options.was_supplied("cs_active");
   priv.active_csoaa_verify = -1.;
   if (options.was_supplied("search_active_verify"))
     if (!priv.active_csoaa)
       THROW("cannot use --search_active_verify without using --cs_active");
 
   cdbg << "active_csoaa = " << priv.active_csoaa << ", active_csoaa_verify = " << priv.active_csoaa_verify << endl;
 
   base_learner* base = setup_base(*all.options, all);
 
   // default to OAA labels unless the task wants to override this (which they can do in initialize)
   all.p->lp = MC::mc_label;
   all.label_type = label_type::mc;
   if (priv.task && priv.task->initialize)
     priv.task->initialize(*sch.get(), priv.A, options);
   if (priv.metatask && priv.metatask->initialize)
     priv.metatask->initialize(*sch.get(), priv.A, options);
   priv.meta_t = 0;
 
   if (options.was_supplied("search_allowed_transitions"))
     read_allowed_transitions((action)priv.A, search_allowed_transitions.c_str());
 
   // set up auto-history (used to only do this if AUTO_CONDITION_FEATURES was on, but that doesn't work for hooktask)
   handle_condition_options(all, priv.acset);
 
   if (!priv.allow_current_policy)  // if we're not dagger
     all.check_holdout_every_n_passes = priv.passes_per_policy;
 
   all.searchstr = sch.get();
 
   priv.start_clock_time = clock();
 
   if (priv.xv)
     priv.num_learners *= 3;
 
   cdbg << "num_learners = " << priv.num_learners << endl;
 
   learner<search, multi_ex>& l = init_learner(sch, make_base(*base), do_actual_learning<true>,
       do_actual_learning<false>, priv.total_number_of_policies * priv.num_learners);
   l.set_finish_example(finish_multiline_example);
   l.set_end_examples(end_examples);
   l.set_finish(search_finish);
   l.set_end_pass(end_pass);
   return make_base(l);
 }

◆ should_print_update()

bool Search::should_print_update	(	vw &	all,
		bool	hit_new_pass = `false`
	)

Definition at line 449 of file search.cc.

References vw::bfgs, shared_data::dump_interval, vw::quiet, vw::sd, and shared_data::weighted_examples().

Referenced by print_update().

 {
   // uncomment to print out final loss after all examples processed
   // commented for now so that outputs matches make test
 
   if (PRINT_UPDATE_EVERY_EXAMPLE)
     return true;
   if (PRINT_UPDATE_EVERY_PASS && hit_new_pass)
     return true;
   return (all.sd->weighted_examples() >= all.sd->dump_interval) && !all.quiet && !all.bfgs;
 }

◆ single_prediction_LDF()

action Search::single_prediction_LDF	(	search_private &	priv,
		example *	ecs,
		size_t	ec_cnt,
		int	policy,
		float &	a_cost,
		action	override_action
	)

Definition at line 1310 of file search.cc.

Referenced by search_predict().

 {
   bool need_partial_predictions = need_memo_foreach_action(priv) ||
       (priv.metaoverride && priv.metaoverride->_foreach_action) || (override_action != (action)-1);
 
   CS::cs_label.default_label(&priv.ldf_test_label);
   CS::wclass wc = {0., 1, 0., 0.};
   priv.ldf_test_label.costs.push_back(wc);
 
   // keep track of best (aka chosen) action
   float best_prediction = 0.;
   action best_action = 0;
 
   size_t start_K = (priv.is_ldf && COST_SENSITIVE::ec_is_example_header(ecs[0])) ? 1 : 0;
 
   v_array<action_cache>* this_cache = nullptr;
   if (need_partial_predictions)
   {
     this_cache = new v_array<action_cache>();
     *this_cache = v_init<action_cache>();
   }
 
   for (action a = (uint32_t)start_K; a < ec_cnt; a++)
   {
     cdbg << "== single_prediction_LDF a=" << a << "==" << endl;
     if (start_K > 0)
       LabelDict::add_example_namespaces_from_example(ecs[a], ecs[0]);
 
     polylabel old_label = ecs[a].l;
     ecs[a].l.cs = priv.ldf_test_label;
 
     multi_ex tmp;
     uint64_t old_offset = ecs[a].ft_offset;
     ecs[a].ft_offset = priv.offset;
     tmp.push_back(&ecs[a]);
     as_multiline(priv.base_learner)->predict(tmp, policy);
 
     ecs[a].ft_offset = old_offset;
     cdbg << "partial_prediction[" << a << "] = " << ecs[a].partial_prediction << endl;
 
     if (override_action != (action)-1)
     {
       if (a == override_action)
         a_cost = ecs[a].partial_prediction;
     }
     else if ((a == start_K) || (ecs[a].partial_prediction < best_prediction))
     {
       best_prediction = ecs[a].partial_prediction;
       best_action = a;
       a_cost = best_prediction;
     }
     if (this_cache)
       this_cache->push_back(action_cache(0., a, false, ecs[a].partial_prediction));
 
     priv.num_features += ecs[a].num_features;
     ecs[a].l = old_label;
     if (start_K > 0)
       LabelDict::del_example_namespaces_from_example(ecs[a], ecs[0]);
   }
   if (override_action != (action)-1)
     best_action = override_action;
   else
     a_cost = best_prediction;
 
   if (this_cache)
   {
     for (size_t i = 0; i < this_cache->size(); i++)
     {
       action_cache& ac = (*this_cache)[i];
       ac.min_cost = a_cost;
       ac.is_opt = (ac.k == best_action);
       if (priv.metaoverride && priv.metaoverride->_foreach_action)
         priv.metaoverride->_foreach_action(*priv.metaoverride->sch, priv.t - 1, ac.min_cost, ac.k, ac.is_opt, ac.cost);
     }
     if (need_memo_foreach_action(priv) && (override_action == (action)-1))
       priv.memo_foreach_action.push_back(this_cache);
     else
     {
       this_cache->delete_v();
       delete this_cache;
     }
   }
 
   // TODO: generate raw predictions if necessary
 
   priv.total_predictions_made++;
   return best_action;
 }

◆ single_prediction_notLDF()

action Search::single_prediction_notLDF	(	search_private &	priv,
		example &	ec,
		int	policy,
		const action *	allowed_actions,
		size_t	allowed_actions_cnt,
		const float *	allowed_actions_cost,
		float &	a_cost,
		action	override_action
	)

Definition at line 1163 of file search.cc.

Referenced by search_predict().

 {
   vw& all = *priv.all;
   polylabel old_label = ec.l;
   bool need_partial_predictions = need_memo_foreach_action(priv) ||
       (priv.metaoverride && priv.metaoverride->_foreach_action) || (override_action != (action)-1) || priv.active_csoaa;
   if ((allowed_actions_cnt > 0) || need_partial_predictions)
     ec.l = allowed_actions_to_ld(priv, 1, allowed_actions, allowed_actions_cnt, allowed_actions_cost);
   else
     ec.l.cs = priv.empty_cs_label;
 
   cdbg << "allowed_actions_cnt=" << allowed_actions_cnt << ", ec.l = [";
   for (size_t i = 0; i < ec.l.cs.costs.size(); i++)
     cdbg << ' ' << ec.l.cs.costs[i].class_index << ':' << ec.l.cs.costs[i].x;
   cdbg << " ]" << endl;
 
   as_singleline(priv.base_learner)->predict(ec, policy);
 
   uint32_t act = ec.pred.multiclass;
   cdbg << "a=" << act << " from";
   if (allowed_actions)
   {
     for (size_t ii = 0; ii < allowed_actions_cnt; ii++) cdbg << ' ' << allowed_actions[ii];
   }
   cdbg << endl;
   a_cost = ec.partial_prediction;
   cdbg << "a_cost = " << a_cost << endl;
 
   if (override_action != (action)-1)
     act = override_action;
 
   if (need_partial_predictions)
   {
     size_t K = cs_get_costs_size(priv.cb_learner, ec.l);
     float min_cost = FLT_MAX;
     for (size_t k = 0; k < K; k++)
     {
       float cost = cs_get_cost_partial_prediction(priv.cb_learner, ec.l, k);
       if (cost < min_cost)
         min_cost = cost;
     }
     v_array<action_cache>* this_cache = nullptr;
     if (need_memo_foreach_action(priv) && (override_action == (action)-1))
     {
       this_cache = new v_array<action_cache>();
       *this_cache = v_init<action_cache>();
     }
     for (size_t k = 0; k < K; k++)
     {
       action cl = cs_get_cost_index(priv.cb_learner, ec.l, k);
       float cost = cs_get_cost_partial_prediction(priv.cb_learner, ec.l, k);
       if (priv.metaoverride && priv.metaoverride->_foreach_action)
         priv.metaoverride->_foreach_action(*priv.metaoverride->sch, priv.t - 1, min_cost, cl, cl == act, cost);
       if (override_action == cl)
         a_cost = cost;
       if (this_cache)
         this_cache->push_back(action_cache(min_cost, cl, cl == act, cost));
     }
     if (this_cache)
     {
       assert(priv.memo_foreach_action.size() == priv.meta_t + priv.t - 1);
       priv.memo_foreach_action.push_back(this_cache);
       cdbg << "memo_foreach_action[" << priv.meta_t + priv.t - 1 << "] = " << this_cache << endl;
     }
   }
 
   if ((priv.state == INIT_TRAIN) && (priv.subsample_timesteps <= -1))  // active learning
   {
     size_t K = cs_get_costs_size(priv.cb_learner, ec.l);
     float min_cost = FLT_MAX, min_cost2 = FLT_MAX;
     for (size_t k = 0; k < K; k++)
     {
       float cost = cs_get_cost_partial_prediction(priv.cb_learner, ec.l, k);
       if (cost < min_cost)
       {
         min_cost2 = min_cost;
         min_cost = cost;
       }
       else if (cost < min_cost2)
       {
         min_cost2 = cost;
       }
     }
     if (min_cost2 < FLT_MAX)
       priv.active_uncertainty.push_back(std::make_pair(min_cost2 - min_cost, priv.t + priv.meta_t));
   }
   if ((priv.state == INIT_TRAIN) && priv.active_csoaa)
   {
     if (priv.cb_learner)
       THROW("cannot use active_csoaa with cb learning");
     size_t cur_t = priv.t + priv.meta_t - 1;
     while (priv.active_known.size() <= cur_t)
     {
       priv.active_known.push_back(v_array<std::pair<CS::wclass&, bool>>());
       priv.active_known[priv.active_known.size() - 1] = v_init<std::pair<CS::wclass&, bool>>();
       cdbg << "active_known length now " << priv.active_known.size() << endl;
     }
     priv.active_known[cur_t].clear();
     assert(ec.l.cs.costs.size() > 0);
     for (size_t k = 0; k < ec.l.cs.costs.size(); k++)
     {
       /* priv.active_known[cur_t].push_back( ec.l.cs.costs[k].pred_is_certain
                                           ? ec.l.cs.costs[k].partial_prediction
                                           : FLT_MAX );
                                           cdbg << "active_known[" << cur_t << "][" << (priv.active_known[cur_t].size() -
          1) << "] = certain=" << ec.l.cs.costs[k].pred_is_certain << ", cost=" << ec.l.cs.costs[k].partial_prediction <<
          "}" << endl; */
       CS::wclass& wc = ec.l.cs.costs[k];
       // Get query_needed from pred
       bool query_needed = v_array_contains(ec.pred.multilabels.label_v, wc.class_index);
       std::pair<CS::wclass&, bool> p = {wc, query_needed};
       // Push into active_known[cur_t] with wc
       priv.active_known[cur_t].push_back(p);
       // cdbg << "active_known[" << cur_t << "][" << (priv.active_known[cur_t].size() - 1) << "] = " << wc.class_index
       // << ':' << wc.x << " pp=" << wc.partial_prediction << " query_needed=" << wc.query_needed << " max_pred=" <<
       // wc.max_pred << " min_pred=" << wc.min_pred << " is_range_overlapped=" << wc.is_range_overlapped << "
       // is_range_large=" << wc.is_range_large << endl;
       // query_needed=" << ec.l.cs.costs[k].query_needed << ", cost=" << ec.l.cs.costs[k].partial_prediction << "}" <<
       // endl;
     }
   }
 
   // generate raw predictions if necessary
   if ((priv.state == INIT_TEST) && (all.raw_prediction > 0))
   {
     priv.rawOutputStringStream->str("");
     for (size_t k = 0; k < cs_get_costs_size(priv.cb_learner, ec.l); k++)
     {
       if (k > 0)
         (*priv.rawOutputStringStream) << ' ';
       (*priv.rawOutputStringStream) << cs_get_cost_index(priv.cb_learner, ec.l, k) << ':'
                                     << cs_get_cost_partial_prediction(priv.cb_learner, ec.l, k);
     }
     all.print_text(all.raw_prediction, priv.rawOutputStringStream->str(), ec.tag);
   }
 
   ec.l = old_label;
 
   priv.total_predictions_made++;
   priv.num_features += ec.num_features;
 
   return act;
 }

◆ size_equal()

bool Search::size_equal	(	size_t	a,
		size_t	b
	)

◆ string_equal()

bool Search::string_equal	(	std::string	a,
		std::string	b
	)

◆ to_short_string()

void Search::to_short_string	(	std::string	in,
		size_t	max_len,
		char *	out
	)

Definition at line 499 of file search.cc.

Referenced by print_update().

 {
   for (size_t i = 0; i < max_len; i++)
     out[i] = ((i >= in.length()) || (in[i] == '\n') || (in[i] == '\t')) ? ' ' : in[i];
 
   if (in.length() > max_len)
   {
     out[max_len - 2] = '.';
     out[max_len - 1] = '.';
   }
   out[max_len] = 0;
 }

◆ train_single_example()

template<bool is_learn>

void Search::train_single_example	(	search &	sch,
		bool	is_test_ex,
		bool	is_holdout_ex,
		multi_ex &	ec_seq
	)

Definition at line 2171 of file search.cc.

 {
   search_private& priv = *sch.priv;
   vw& all = *priv.all;
   bool ran_test = false;  // we must keep track so that even if we skip test, we still update # of examples seen
 
   // if (! priv.no_caching)
   clear_cache_hash_map(priv);
 
   cdbg << "is_test_ex=" << is_test_ex << " vw_is_main=" << all.vw_is_main << endl;
   cdbg << "must_run_test = " << must_run_test(all, ec_seq, is_test_ex) << endl;
   // do an initial test pass to compute output (and loss)
   if (must_run_test(all, ec_seq, is_test_ex))
   {
     cdbg << "======================================== INIT TEST (" << priv.current_policy << ","
          << priv.read_example_last_pass << ") ========================================" << endl;
 
     ran_test = true;
 
     // do the prediction
     reset_search_structure(priv);
     priv.state = INIT_TEST;
     priv.should_produce_string =
         might_print_update(all) || (all.final_prediction_sink.size() > 0) || (all.raw_prediction > 0);
     priv.pred_string->str("");
     priv.test_action_sequence.clear();
     run_task(sch, ec_seq);
 
     // accumulate loss
     if (!is_test_ex)
       all.sd->update(ec_seq[0]->test_only, !is_test_ex, priv.test_loss, 1.f, priv.num_features);
 
     // generate output
     for (int sink : all.final_prediction_sink) all.print_text((int)sink, priv.pred_string->str(), ec_seq[0]->tag);
 
     if (all.raw_prediction > 0)
       all.print_text(all.raw_prediction, "", ec_seq[0]->tag);
   }
 
   // if we're not training, then we're done!
   if ((!is_learn) || is_test_ex || is_holdout_ex || ec_seq[0]->test_only || (!priv.all->training))
     return;
 
   // SPEEDUP: if the oracle was never called, we can skip this!
 
   // do a pass over the data allowing oracle
   cdbg << "======================================== INIT TRAIN (" << priv.current_policy << ","
        << priv.read_example_last_pass << ") ========================================" << endl;
   // std::cerr << "training" << endl;
 
   clear_cache_hash_map(priv);
   reset_search_structure(priv);
   clear_memo_foreach_action(priv);
   priv.state = INIT_TRAIN;
   priv.active_uncertainty.clear();
   priv.train_trajectory.clear();  // this is where we'll store the training sequence
   run_task(sch, ec_seq);
 
   if (!ran_test)  // was  && !priv.ec_seq[0]->test_only) { but we know it's not test_only
     all.sd->update(ec_seq[0]->test_only, true, priv.test_loss, 1.f, priv.num_features);
 
   // if there's nothing to train on, we're done!
   if ((priv.loss_declared_cnt == 0) || (priv.t + priv.meta_t == 0) ||
       (priv.rollout_method == NO_ROLLOUT))  // TODO: make sure NO_ROLLOUT works with beam!
   {
     return;
   }
 
   // otherwise, we have some learn'in to do!
   cdbg << "======================================== LEARN (" << priv.current_policy << ","
        << priv.read_example_last_pass << ") ========================================" << endl;
   priv.T = priv.metatask ? priv.meta_t : priv.t;
   get_training_timesteps(priv, priv.timesteps);
   cdbg << "train_trajectory.size() = " << priv.train_trajectory.size() << ":\t";
   cdbg_print_array<scored_action>("", priv.train_trajectory);
   // cdbg << "memo_foreach_action = " << priv.memo_foreach_action << endl;
   for (size_t i = 0; i < priv.memo_foreach_action.size(); i++)
   {
     cdbg << "memo_foreach_action[" << i << "] = ";
     if (priv.memo_foreach_action[i])
       cdbg << *priv.memo_foreach_action[i];
     else
       cdbg << "null";
     cdbg << endl;
   }
 
   if (priv.cb_learner)
     priv.learn_losses.cb.costs.clear();
   else
     priv.learn_losses.cs.costs.clear();
 
   for (size_t tid = 0; tid < priv.timesteps.size(); tid++)
   {
     cdbg << "timestep = " << priv.timesteps[tid] << " [" << tid << "/" << priv.timesteps.size() << "]" << endl;
 
     if (priv.metatask && !priv.memo_foreach_action[tid])
     {
       cdbg << "skipping because it looks like this was overridden by metatask" << endl;
       continue;
     }
 
     priv.learn_ec_ref = nullptr;
     priv.learn_ec_ref_cnt = 0;
 
     reset_search_structure(priv);  // TODO remove this?
     bool skipped_all_actions = true;
     priv.learn_a_idx = 0;
     priv.done_with_all_actions = false;
     // for each action, roll out to get a loss
     while (!priv.done_with_all_actions)
     {
       priv.learn_t = priv.timesteps[tid];
       advance_from_known_actions(priv);
       if (priv.done_with_all_actions)
         break;
 
       skipped_all_actions = false;
       reset_search_structure(priv);
 
       priv.state = LEARN;
       priv.learn_t = priv.timesteps[tid];
       cdbg << "-------------------------------------------------------------------------------------" << endl;
       cdbg << "learn_t = " << priv.learn_t << ", learn_a_idx = " << priv.learn_a_idx << endl;
       // cdbg_print_array("priv.active_known[learn_t]", priv.active_known[priv.learn_t]);
       run_task(sch, ec_seq);
       // cerr_print_array("in GENER, learn_allowed_actions", priv.learn_allowed_actions);
       float this_loss = priv.learn_loss;
       cs_cost_push_back(priv.cb_learner, priv.learn_losses,
           priv.is_ldf ? (uint32_t)(priv.learn_a_idx - 1) : (uint32_t)priv.learn_a_idx, this_loss);
       //                          (priv.learn_allowed_actions.size() > 0) ?
       //                          priv.learn_allowed_actions[priv.learn_a_idx-1] : priv.is_ldf ? (priv.learn_a_idx-1) :
       //                          (priv.learn_a_idx),
       //                           priv.learn_loss);
     }
     if (priv.active_csoaa_verify > 0.)
       verify_active_csoaa(
           priv.learn_losses.cs, priv.active_known[priv.learn_t], ec_seq[0]->example_counter, priv.active_csoaa_verify);
 
     if (skipped_all_actions)
     {
       reset_search_structure(priv);
       priv.state = LEARN;
       priv.learn_t = priv.timesteps[tid];
       priv.force_setup_ec_ref = true;
       cdbg << "<<<<<" << endl;
       cdbg << "skipped all actions; learn_t = " << priv.learn_t << ", learn_a_idx = " << priv.learn_a_idx << endl;
       run_task(sch, ec_seq);  // TODO: i guess we can break out of this early
       cdbg << ">>>>>" << endl;
     }
     else
       cdbg << "didn't skip all actions" << endl;
 
     // now we can make a training example
     if (priv.learn_allowed_actions.size() > 0)
     {
       for (size_t i = 0; i < priv.learn_allowed_actions.size(); i++)
       {
         priv.learn_losses.cs.costs[i].class_index = priv.learn_allowed_actions[i];
       }
     }
     // float min_loss = 0.;
     // if (priv.metatask)
     //  for (size_t aid=0; aid<priv.memo_foreach_action[tid]->size(); aid++)
     //    min_loss = std::min(min_loss, priv.memo_foreach_action[tid]->get(aid).cost);
     cdbg << "priv.learn_losses = [";
     for (auto& wc : priv.learn_losses.cs.costs) cdbg << " " << wc.class_index << ":" << wc.x;
     cdbg << " ]" << endl;
     cdbg << "gte" << endl;
     generate_training_example(priv, priv.learn_losses, 1., true);  // , min_loss);  // TODO: weight
     if (!priv.examples_dont_change)
       for (size_t n = 0; n < priv.learn_ec_copy.size(); n++)
       {
         if (sch.priv->is_ldf)
           CS::cs_label.delete_label(&priv.learn_ec_copy[n].l.cs);
         else
           MC::mc_label.delete_label(&priv.learn_ec_copy[n].l.multi);
       }
     if (priv.cb_learner)
       priv.learn_losses.cb.costs.clear();
     else
       priv.learn_losses.cs.costs.clear();
   }
 
   if (priv.active_csoaa && (priv.save_every_k_runs > 1))
   {
     size_t prev_num = priv.num_calls_to_run_previous / priv.save_every_k_runs;
     size_t this_num = priv.num_calls_to_run / priv.save_every_k_runs;
     if (this_num > prev_num)
       save_predictor(all, all.final_regressor_name, this_num);
     priv.num_calls_to_run_previous = priv.num_calls_to_run;
   }
 }

◆ uint32_equal()

bool Search::uint32_equal	(	uint32_t	a,
		uint32_t	b
	)

◆ verify_active_csoaa()

void Search::verify_active_csoaa	(	COST_SENSITIVE::label &	losses,
		v_array< std::pair< CS::wclass &, bool >> &	known,
		size_t	t,
		float	multiplier
	)

Definition at line 2108 of file search.cc.

References cdbg, COST_SENSITIVE::wclass::class_index, COST_SENSITIVE::label::costs, and COST_SENSITIVE::wclass::x.

Referenced by train_single_example().

 {
   float threshold = multiplier / std::sqrt((float)t);
   cdbg << "verify_active_csoaa, losses = [";
   for (COST_SENSITIVE::wclass& wc : losses.costs) cdbg << " " << wc.class_index << ":" << wc.x;
   cdbg << " ]" << endl;
   // cdbg_print_array("verify_active_csoaa,  known", known);
   size_t i = 0;
   for (COST_SENSITIVE::wclass& wc : losses.costs)
   {
     if (!known[i].second)
     {
       float err = pow(known[i].first.partial_prediction - wc.x, 2);
       if (err > threshold)
       {
         std::cerr << "verify_active_csoaa failed: truth " << wc.class_index << ":" << wc.x << ", known[" << i
                   << "]=" << known[i].first.partial_prediction << ", error=" << err << " vs threshold " << threshold
                   << endl;
       }
     }
     i++;
   }
 }

Variable Documentation

◆ ACTION_COSTS

uint32_t Search::ACTION_COSTS = 32

Definition at line 50 of file search.cc.

Referenced by DepParserTask::initialize(), SequenceTaskCostToGo::initialize(), and Search::search::set_options().

◆ all_metatasks

search_metatask* Search::all_metatasks[]

Initial value:

= {

&DebugMT::metatask, &SelectiveBranchingMT::metatask, nullptr}

DebugMT::metatask

Search::search_metatask metatask

Definition: search_meta.cc:18

SelectiveBranchingMT::metatask

Search::search_metatask metatask

Definition: search_meta.cc:50

Definition at line 39 of file search.cc.

◆ all_tasks

search_task* Search::all_tasks[]

Initial value:

= {&SequenceTask::task, &SequenceSpanTask::task, &SequenceTaskCostToGo::task,
    &ArgmaxTask::task, &SequenceTask_DemoLDF::task, &MulticlassTask::task, &DepParserTask::task,
    &EntityRelationTask::task, &HookTask::task, &GraphTask::task, nullptr}

Definition at line 35 of file search.cc.

◆ AUTO_CONDITION_FEATURES

uint32_t Search::AUTO_CONDITION_FEATURES = 1

Definition at line 49 of file search.cc.

Referenced by SequenceTask::initialize(), DepParserTask::initialize(), SequenceSpanTask::initialize(), SequenceTaskCostToGo::initialize(), ArgmaxTask::initialize(), and SequenceTask_DemoLDF::initialize().

◆ AUTO_HAMMING_LOSS

uint32_t Search::AUTO_HAMMING_LOSS = 2

Definition at line 49 of file search.cc.

Referenced by SequenceTask::initialize(), SequenceSpanTask::initialize(), SequenceTaskCostToGo::initialize(), SequenceTask_DemoLDF::initialize(), and Search::search::set_options().

◆ conditional_constant

uint64_t Search::conditional_constant = 8290743

Definition at line 368 of file search.cc.

◆ EXAMPLES_DONT_CHANGE

uint32_t Search::EXAMPLES_DONT_CHANGE = 4

Definition at line 49 of file search.cc.

Referenced by SequenceTask::initialize(), SequenceSpanTask::initialize(), SequenceTaskCostToGo::initialize(), ArgmaxTask::initialize(), and Search::search::set_options().

◆ IS_LDF

uint32_t Search::IS_LDF = 8

Definition at line 49 of file search.cc.

Referenced by EntityRelationTask::initialize(), SequenceTask_DemoLDF::initialize(), and Search::search::set_options().

◆ NO_CACHING

uint32_t Search::NO_CACHING = 16

Definition at line 49 of file search.cc.

Referenced by DepParserTask::initialize(), and Search::search::set_options().

◆ PRINT_CLOCK_TIME

constexpr bool Search::PRINT_CLOCK_TIME = false

Definition at line 44 of file search.cc.

◆ PRINT_UPDATE_EVERY_EXAMPLE

constexpr bool Search::PRINT_UPDATE_EVERY_EXAMPLE = false

Definition at line 42 of file search.cc.

◆ PRINT_UPDATE_EVERY_PASS

constexpr bool Search::PRINT_UPDATE_EVERY_PASS = false

Definition at line 43 of file search.cc.

Classes

Enumerations

Functions

Variables

Enumeration Type Documentation

◆ RollMethod

◆ SearchState

Function Documentation

◆ absdiff()

◆ action_cost_loss()

◆ action_hamming_loss()

◆ add_example_conditioning()

◆ add_neighbor_features()

◆ add_new_feature()

◆ adjust_auto_condition()

◆ advance_from_known_actions()

◆ allowed_actions_to_label()

◆ allowed_actions_to_ld()

◆ array_contains()

◆ audit_feature_space()

◆ cached_action_store_or_find()

◆ cached_item_equivalent()

◆ cdbg_print_array()

◆ cerr_print_array()

◆ choose_oracle_action()

◆ choose_policy()

◆ clear_cache_hash_map()

◆ clear_memo_foreach_action()

◆ cmp_size_t()

◆ cmp_size_t_pair()

◆ condition_feature_space()

◆ cs_cost_push_back()

◆ cs_costs_erase()

◆ cs_costs_resize()

◆ cs_get_cost_index()

◆ cs_get_cost_partial_prediction()

◆ cs_get_costs_size()

◆ cs_set_cost_loss()

◆ del_example_conditioning()

◆ del_features_in_top_namespace()

◆ del_neighbor_features()

◆ do_actual_learning()

◆ end_examples()

◆ end_pass()

◆ ensure_param()

◆ ensure_size()

◆ finish_multiline_example()

◆ float_equal()

◆ foreach_action_from_cache()

◆ free_final_item()

◆ free_key()

◆ generate_training_example()

◆ get_training_timesteps()

◆ handle_condition_options()

◆ hoopla_permute()

◆ mc_label_is_test()

◆ might_print_update()

◆ must_run_test()

◆ need_memo_foreach_action()

◆ neighbor_feature_space()

◆ number_to_natural()

◆ operator<<() [1/2]

◆ operator<<() [2/2]

◆ parse_neighbor_features()

◆ print_update()

◆ push_at()

◆ random()

◆ random_policy()

◆ read_allowed_transitions()

◆ reset_search_structure()

◆ run_task()

◆ safediv()

◆ search_declare_loss()

◆ search_finish()

◆ search_initialize()

◆ search_predict()

◆ search_predictNeedsExample()

◆ select_learner()

◆ setup()

◆ should_print_update()