INTERACTIONS Namespace Reference

Classes
struct	feature_gen_data

Functions
void	expand_namespaces_with_recursion (std::string const &ns, std::vector< std::string > &res, std::string &val, size_t pos)
std::vector< std::string >	expand_interactions (const std::vector< std::string > &vec, const size_t required_length, const std::string &err_msg)
bool	must_be_left_sorted (const std::string &oi)
void	sort_and_filter_duplicate_interactions (std::vector< std::string > &vec, bool filter_duplicates, size_t &removed_cnt, size_t &sorted_cnt)
size_t	factor (const size_t n, const size_t start_from=1)
void	eval_count_of_generated_ft (vw &all, example &ec, size_t &new_features_cnt, float &new_features_value)
constexpr bool	is_printable_namespace (const unsigned char ns)
template<class R , class S , void(*)(R &, float, S) T, bool audit, void(*)(R &, const audit_strings *) audit_func>
void	generate_interactions (vw &all, example_predict &ec, R &dat)
template<class R , class S , void(*)(R &, float, S) T>
void	generate_interactions (vw &all, example_predict &ec, R &dat)
int64_t	choose (int64_t n, int64_t k)
template<class R , void(*)(R &, const float, float &) T, class W >
void	call_T (R &dat, W &weights, const float ft_value, const uint64_t ft_idx)
template<class R , void(*)(R &, const float, const float &) T, class W >
void	call_T (R &dat, const W &weights, const float ft_value, const uint64_t ft_idx)
float	INTERACTION_VALUE (float value1, float value2)
template<class R , class S , void(*)(R &, float, S) T, bool audit, void(*)(R &, const audit_strings *) audit_func, class W >
void	inner_kernel (R &dat, features::iterator_all &begin, features::iterator_all &end, const uint64_t offset, W &weights, feature_value ft_value, feature_index halfhash)
template<class R , class S , void(*)(R &, float, S) T, bool audit, void(*)(R &, const audit_strings *) audit_func, class W >
void	generate_interactions (std::vector< std::string > &interactions, bool permutations, example_predict &ec, R &dat, W &weights)

Variables
constexpr int64_t	fast_factorial []
constexpr size_t	size_fast_factorial = sizeof(fast_factorial) / sizeof(*fast_factorial)
constexpr unsigned char	printable_start = ' '
constexpr unsigned char	printable_end = '~'
constexpr unsigned char	printable_ns_size = printable_end - printable_start
constexpr uint64_t	valid_ns_size
constexpr bool	feature_self_interactions = true

Function Documentation

call_T() [1/2]

template<class R , void(*)(R &, const float, float &) T, class W >

void INTERACTIONS::call_T ( R &  dat, W &  weights, const float  ft_value, const uint64_t  ft_idx  )

inline

Definition at line 31 of file interactions_predict.h.

Referenced by call_T().

{
  T(dat, ft_value, weights[ft_idx]);
}

call_T() [2/2]

template<class R , void(*)(R &, const float, const float &) T, class W >

void INTERACTIONS::call_T ( R &  dat, const W &  weights, const float  ft_value, const uint64_t  ft_idx  )

inline

Definition at line 37 of file interactions_predict.h.

References call_T().

{
  T(dat, ft_value, weights[ft_idx]);
}

choose()

int64_t INTERACTIONS::choose ( int64_t  n, int64_t  k  )

inline

Definition at line 69 of file interactions.h.

Referenced by eval_count_of_generated_ft().

{
  if (k > n)
    return 0;
  if (k < 0)
    return 0;
  if (k == n)
    return 1;
  if (k == 0 && n != 0)
    return 1;
  int64_t r = 1;
  for (int64_t d = 1; d <= k; ++d)
  {
    r *= n--;
    r /= d;
  }
  return r;
}

eval_count_of_generated_ft()

void INTERACTIONS::eval_count_of_generated_ft	(	vw &	all,
		example &	ec,
		size_t &	new_features_cnt,
		float &	new_features_value
	)

Definition at line 228 of file interactions.cc.

References choose(), v_array< T >::delete_v(), example_predict::feature_space, example_predict::interactions, vw::permutations, PROCESS_SELF_INTERACTIONS, v_array< T >::push_back(), v_array< T >::size(), features::size(), and features::values.

Referenced by DepParserTask::extract_features(), is_printable_namespace(), and VW::setup_example().

{
  new_features_cnt = 0;
  new_features_value = 0.;

  v_array<float> results = v_init<float>();

  if (all.permutations)
  {
    // just multiply precomputed values for all namespaces
    for (std::string& inter : *ec.interactions)
    {
      size_t num_features_in_inter = 1;
      float sum_feat_sq_in_inter = 1.;

      for (namespace_index ns : inter)
      {
        num_features_in_inter *= ec.feature_space[ns].size();
        sum_feat_sq_in_inter *= ec.feature_space[ns].sum_feat_sq;
        if (num_features_in_inter == 0)
          break;
      }

      if (num_features_in_inter == 0)
        continue;

      new_features_cnt += num_features_in_inter;
      new_features_value += sum_feat_sq_in_inter;
    }
  }
  else  // case of simple combinations
  {
#ifdef DEBUG_EVAL_COUNT_OF_GEN_FT
    size_t correct_features_cnt = 0;
    float correct_features_value = 0.;
    eval_gen_data dat(correct_features_cnt, correct_features_value);
    generate_interactions<eval_gen_data, uint64_t, ft_cnt>(all, ec, dat);
#endif

    for (std::string& inter : *ec.interactions)
    {
      size_t num_features_in_inter = 1;
      float sum_feat_sq_in_inter = 1.;

      for (auto ns = inter.begin(); ns != inter.end(); ++ns)
      {
        if ((ns == inter.end() - 1) || (*ns != *(ns + 1)))  // neighbour namespaces are different
        {
          // just multiply precomputed values
          const int nsc = *ns;
          num_features_in_inter *= ec.feature_space[nsc].size();
          sum_feat_sq_in_inter *= ec.feature_space[nsc].sum_feat_sq;
          if (num_features_in_inter == 0)
            break;  // one of namespaces has no features - go to next interaction
        }
        else  // we are at beginning of a block made of same namespace (interaction is preliminary sorted)
        {
          // let's find out real length of this block
          size_t order_of_inter = 2;  // alredy compared ns == ns+1

          for (auto ns_end = ns + 2; ns_end < inter.end(); ++ns_end)
            if (*ns == *ns_end)
              ++order_of_inter;

          // namespace is same for whole block
          features& fs = ec.feature_space[(const int)*ns];

          // count number of features with value != 1.;
          size_t cnt_ft_value_non_1 = 0;

          // in this block we shall calculate number of generated features and sum of their values
          // keeping in mind rules applicable for simple combinations instead of permutations

          // let's calculate sum of their squared value for whole block

          // ensure results as big as order_of_inter and empty.
          for (size_t i = 0; i < results.size(); ++i) results[i] = 0.;
          while (results.size() < order_of_inter) results.push_back(0.);

          // recurrent value calculations
          for (size_t i = 0; i < fs.size(); ++i)
          {
            const float x = fs.values[i] * fs.values[i];

            if (!PROCESS_SELF_INTERACTIONS(fs.values[i]))
            {
              for (size_t i = order_of_inter - 1; i > 0; --i) results[i] += results[i - 1] * x;

              results[0] += x;
            }
            else
            {
              results[0] += x;

              for (size_t i = 1; i < order_of_inter; ++i) results[i] += results[i - 1] * x;

              ++cnt_ft_value_non_1;
            }
          }

          sum_feat_sq_in_inter *= results[order_of_inter - 1];  // will be explained in http://bit.ly/1Hk9JX1

          // let's calculate  the number of a new features

          // if number of features is less than  order of interaction then go to the next interaction
          // as you can't make simple combination of interaction 'aaa' if a contains < 3 features.
          // unless one of them has value != 1. and we are counting them.
          const size_t ft_size = fs.size();
          if (cnt_ft_value_non_1 == 0 && ft_size < order_of_inter)
          {
            num_features_in_inter = 0;
            break;
          }

          size_t n;
          if (cnt_ft_value_non_1 == 0)  // number of generated simple combinations is C(n,k)
          {
            n = (size_t)choose((int64_t)ft_size, (int64_t)order_of_inter);
          }
          else
          {
            n = 0;
            for (size_t l = 0; l <= order_of_inter; ++l)
            {
              // C(l+m-1, l) * C(n-m, k-l)
              size_t num = (l == 0) ? 1 : (size_t)choose(l + cnt_ft_value_non_1 - 1, l);

              if (ft_size - cnt_ft_value_non_1 >= order_of_inter - l)
                num *= (size_t)choose(ft_size - cnt_ft_value_non_1, order_of_inter - l);
              else
                num = 0;

              n += num;
            }

          }  // details on http://bit.ly/1Hk9JX1

          num_features_in_inter *= n;

          ns += order_of_inter - 1;  // jump over whole block
        }
      }

      if (num_features_in_inter == 0)
        continue;  // signal that values should be ignored (as default value is 1)

      new_features_cnt += num_features_in_inter;
      new_features_value += sum_feat_sq_in_inter;
    }

#ifdef DEBUG_EVAL_COUNT_OF_GEN_FT
    if (correct_features_cnt != new_features_cnt)
      all.trace_message << "Incorrect new features count " << new_features_cnt << " must be " << correct_features_cnt
                        << std::endl;
    if (fabs(correct_features_value - new_features_value) > 1e-5)
      all.trace_message << "Incorrect new features value " << new_features_value << " must be "
                        << correct_features_value << std::endl;
#endif
  }

  results.delete_v();
}

expand_interactions()

std::vector< std::string > INTERACTIONS::expand_interactions	(	const std::vector< std::string > &	vec,
		const size_t	required_length,
		const std::string &	err_msg
	)

Definition at line 56 of file interactions.cc.

References expand_namespaces_with_recursion(), and THROW.

Referenced by is_printable_namespace(), and parse_feature_tweaks().

{
  std::vector<std::string> res;

  for (std::string const& i : vec)
  {
    const size_t len = i.length();
    if (required_length > 0 && len != required_length)
    // got strict requirement of interaction length and it was failed.
    {
      THROW(err_msg);
    }
    else if (len < 2)
      // regardles of required_length value this check is always performed
      THROW("error, feature interactions must involve at least two namespaces" << err_msg);

    std::string temp;
    expand_namespaces_with_recursion(i, res, temp, 0);
  }
  return res;
}

expand_namespaces_with_recursion()

void INTERACTIONS::expand_namespaces_with_recursion	(	std::string const &	ns,
		std::vector< std::string > &	res,
		std::string &	val,
		size_t	pos
	)

Definition at line 14 of file interactions.cc.

References printable_end, printable_start, and valid_ns().

Referenced by expand_interactions().

{
  assert(pos <= ns.size());

  if (pos == ns.size())
  {
    // we're at the end of interaction

    // and store it in res
    res.push_back(val);
    // don't free s memory as it's data will be used later
  }
  else
  {
    // we're at the middle of interaction
    if (ns[pos] != ':')
    {
      // not a wildcard
      val.push_back(ns[pos]);
      expand_namespaces_with_recursion(ns, res, val, pos + 1);
      val.pop_back();  // i don't need value itself
    }
    else
    {
      for (unsigned char j = printable_start; j <= printable_end; ++j)
      {
        if (valid_ns(j))
        {
          val.push_back(j);
          expand_namespaces_with_recursion(ns, res, val, pos + 1);
          val.pop_back();  // i don't need value itself
        }
      }
    }
  }
}

factor()

size_t INTERACTIONS::factor ( const size_t  n, const size_t  start_from = 1  )

inline

Definition at line 214 of file interactions.cc.

{
  if (n <= 0)
    return 1;
  if (start_from == 1 && n < size_fast_factorial)
    return (size_t)fast_factorial[n];

  size_t res = 1;
  for (size_t i = start_from + 1; i <= n; ++i) res *= i;
  return res;
}

generate_interactions() [1/3]

template<class R , class S , void(*)(R &, float, S) T, bool audit, void(*)(R &, const audit_strings *) audit_func>

void INTERACTIONS::generate_interactions ( vw &  all, example_predict &  ec, R &  dat  )

inline

Definition at line 45 of file interactions.h.

References parameters::dense_weights, example_predict::interactions, vw::permutations, parameters::sparse, parameters::sparse_weights, and vw::weights.

Referenced by audit_regressor().

{
  if (all.weights.sparse)
    generate_interactions<R, S, T, audit, audit_func, sparse_parameters>(
        *ec.interactions, all.permutations, ec, dat, all.weights.sparse_weights);
  else
    generate_interactions<R, S, T, audit, audit_func, dense_parameters>(
        *ec.interactions, all.permutations, ec, dat, all.weights.dense_weights);
}

generate_interactions() [2/3]

template<class R , class S , void(*)(R &, float, S) T>

void INTERACTIONS::generate_interactions ( vw &  all, example_predict &  ec, R &  dat  )

inline

Definition at line 57 of file interactions.h.

References parameters::dense_weights, vw::interactions, vw::permutations, parameters::sparse, parameters::sparse_weights, and vw::weights.

{
  if (all.weights.sparse)
    generate_interactions<R, S, T, sparse_parameters>(
        all.interactions, all.permutations, ec, dat, all.weights.sparse_weights);
  else
    generate_interactions<R, S, T, dense_parameters>(
        all.interactions, all.permutations, ec, dat, all.weights.dense_weights);
}

generate_interactions() [3/3]

template<class R , class S , void(*)(R &, float, S) T, bool audit, void(*)(R &, const audit_strings *) audit_func, class W >

void INTERACTIONS::generate_interactions ( std::vector< std::string > &  interactions, bool  permutations, example_predict &  ec, R &  dat, W &  weights  )

inline

Definition at line 98 of file interactions_predict.h.

References v_array< T >::begin(), features::features_value_index_audit_range::begin(), v_array< T >::delete_v(), v_array< T >::end(), features::features_value_index_audit_range::end(), example_predict::feature_space, FNV_prime, INTERACTIONS::feature_gen_data::ft_arr, example_predict::ft_offset, INTERACTIONS::feature_gen_data::hash, features::indicies, INTERACTION_VALUE(), INTERACTIONS::feature_gen_data::loop_end, INTERACTIONS::feature_gen_data::loop_idx, features::nonempty(), PROCESS_SELF_INTERACTIONS, v_array< T >::push_back(), INTERACTIONS::feature_gen_data::self_interaction, v_array< T >::size(), features::space_names, features::values, features::values_indices_audit(), and INTERACTIONS::feature_gen_data::x.

{
  features* features_data = ec.feature_space.data();

  // often used values
  const uint64_t offset = ec.ft_offset;
  //    const uint64_t stride_shift = all.stride_shift; // it seems we don't need stride shift in FTRL-like hash

  // statedata for generic non-recursive iteration
  v_array<feature_gen_data> state_data = v_init<feature_gen_data>();

  feature_gen_data empty_ns_data;  // micro-optimization. don't want to call its constructor each time in loop.
  empty_ns_data.loop_idx = 0;
  empty_ns_data.x = 1.;
  empty_ns_data.loop_end = 0;
  empty_ns_data.self_interaction = false;

  // loop throw the set of possible interactions
  for (auto& ns : interactions)
  {  // current list of namespaces to interact.

#ifndef GEN_INTER_LOOP

    // unless GEN_INTER_LOOP is defined we use nested 'for' loops for interactions length 2 (pairs) and 3 (triples)
    // and generic non-recursive algorythm for all other cases.
    // nested 'for' loops approach is faster, but can't be used for interation of any length.

    const size_t len = ns.size();

    if (len == 2)  // special case of pairs
    {
      features& first = features_data[(uint8_t)ns[0]];
      if (first.nonempty())
      {
        features& second = features_data[(uint8_t)ns[1]];
        if (second.nonempty())
        {
          const bool same_namespace = (!permutations && (ns[0] == ns[1]));

          for (size_t i = 0; i < first.indicies.size(); ++i)
          {
            feature_index halfhash = FNV_prime * (uint64_t)first.indicies[i];
            if (audit)
              audit_func(dat, first.space_names[i].get());
            // next index differs for permutations and simple combinations
            feature_value ft_value = first.values[i];
            features::features_value_index_audit_range range = second.values_indices_audit();
            features::iterator_all begin = range.begin();
            if (same_namespace)
              begin += (PROCESS_SELF_INTERACTIONS(ft_value)) ? i : i + 1;

            features::iterator_all end = range.end();
            inner_kernel<R, S, T, audit, audit_func>(dat, begin, end, offset, weights, ft_value, halfhash);

            if (audit)
              audit_func(dat, nullptr);
          }  // end for(fst)
        }    // end if (data[snd] size > 0)
      }      // end if (data[fst] size > 0)
    }
    else if (len == 3)  // special case for triples
    {
      features& first = features_data[(uint8_t)ns[0]];
      if (first.nonempty())
      {
        features& second = features_data[(uint8_t)ns[1]];
        if (second.nonempty())
        {
          features& third = features_data[(uint8_t)ns[2]];
          if (third.nonempty())
          {  // don't compare 1 and 3 as interaction is sorted
            const bool same_namespace1 = (!permutations && (ns[0] == ns[1]));
            const bool same_namespace2 = (!permutations && (ns[1] == ns[2]));

            for (size_t i = 0; i < first.indicies.size(); ++i)
            {
              if (audit)
                audit_func(dat, first.space_names[i].get());
              const uint64_t halfhash1 = FNV_prime * (uint64_t)first.indicies[i];
              const float& first_ft_value = first.values[i];
              size_t j = 0;
              if (same_namespace1)  // next index differs for permutations and simple combinations
                j = (PROCESS_SELF_INTERACTIONS(first_ft_value)) ? i : i + 1;

              for (; j < second.indicies.size(); ++j)
              {  // f3 x k*(f2 x k*f1)
                if (audit)
                  audit_func(dat, second.space_names[j].get());
                feature_index halfhash = FNV_prime * (halfhash1 ^ (uint64_t)second.indicies[j]);
                feature_value ft_value = INTERACTION_VALUE(first_ft_value, second.values[j]);

                features::features_value_index_audit_range range = third.values_indices_audit();
                features::iterator_all begin = range.begin();
                if (same_namespace2)  // next index differs for permutations and simple combinations
                  begin += (PROCESS_SELF_INTERACTIONS(ft_value)) ? j : j + 1;

                features::iterator_all end = range.end();
                inner_kernel<R, S, T, audit, audit_func>(dat, begin, end, offset, weights, ft_value, halfhash);
                if (audit)
                  audit_func(dat, nullptr);
              }  // end for (snd)
              if (audit)
                audit_func(dat, nullptr);
            }  // end for (fst)

          }  // end if (data[thr] size > 0)
        }    // end if (data[snd] size > 0)
      }      // end if (data[fst] size > 0)
    }
    else  // generic case: quatriples, etc.

#endif
    {
      bool must_skip_interaction = false;
      // preparing state data
      feature_gen_data* fgd = state_data.begin();
      feature_gen_data* fgd2;  // for further use
      for (namespace_index n : ns)
      {
        features& ft = features_data[(int32_t)n];
        const size_t ft_cnt = ft.indicies.size();

        if (ft_cnt == 0)
        {
          must_skip_interaction = true;
          break;
        }

        if (fgd == state_data.end())
        {
          state_data.push_back(empty_ns_data);
          fgd = state_data.end() - 1;  // reassign as memory could be realloced
        }

        fgd->loop_end = ft_cnt - 1;  // saving number of features for each namespace
        fgd->ft_arr = &ft;
        ++fgd;
      }

      // if any of interacting namespace has 0 features - whole interaction is skipped
      if (must_skip_interaction)
        continue;  // no_data_to_interact

      if (!permutations)  // adjust state_data for simple combinations
      {                   // if permutations mode is disabeled then namespaces in ns are already sorted and thus grouped
        // (in fact, currently they are sorted even for enabled permutations mode)
        // let's go throw the list and calculate number of features to skip in namespaces which
        // repeated more than once to generate only simple combinations of features

        size_t margin = 0;  // number of features to ignore if namespace has been seen before

        // iterate list backward as margin grows in this order

        for (fgd = state_data.end() - 1; fgd > state_data.begin(); --fgd)
        {
          fgd2 = fgd - 1;
          fgd->self_interaction = (fgd->ft_arr == fgd2->ft_arr);  // state_data.begin().self_interaction is always false
          if (fgd->self_interaction)
          {
            size_t& loop_end = fgd2->loop_end;

            if (!PROCESS_SELF_INTERACTIONS((*fgd2->ft_arr).values[loop_end - margin]))
            {
              ++margin;  // otherwise margin can't be increased
              must_skip_interaction = loop_end < margin;
              if (must_skip_interaction)
                break;
            }

            if (margin != 0)
              loop_end -= margin;  // skip some features and increase margin
          }
          else if (margin != 0)
            margin = 0;
        }

        // if impossible_without_permutations == true then we faced with case like interaction 'aaaa'
        // where namespace 'a' contains less than 4 unique features. It's impossible to make simple
        // combination of length 4 without repetitions from 3 or less elements.
        if (must_skip_interaction)
          continue;  // impossible_without_permutations
      }              // end of state_data adjustment

      fgd = state_data.begin();     // always equal to first ns
      fgd2 = state_data.end() - 1;  // always equal to last ns
      fgd->loop_idx = 0;            // loop_idx contains current feature id for curently processed namespace.

      // beware: micro-optimization.
      /* start & end are always point to features in last namespace of interaction.
      for 'all.permutations == true' they are constant.*/
      size_t start_i = 0;

      feature_gen_data* cur_data = fgd;
      // end of micro-optimization block

      // generic feature generation cycle for interactions of any length
      bool do_it = true;
      while (do_it)
      {
        if (cur_data < fgd2)  // can go further threw the list of namespaces in interaction
        {
          feature_gen_data* next_data = cur_data + 1;
          size_t feature = cur_data->loop_idx;
          features& fs = *(cur_data->ft_arr);

          if (next_data->self_interaction)
          {  // if next namespace is same, we should start with loop_idx + 1 to avoid feature interaction with itself
            // unless feature has value x and x != x*x. E.g. x != 0 and x != 1. Features with x == 0 are already
            // filtered out in parce_args.cc::maybeFeature().

            next_data->loop_idx =
                (PROCESS_SELF_INTERACTIONS(fs.values[feature])) ? cur_data->loop_idx : cur_data->loop_idx + 1;
          }
          else
            next_data->loop_idx = 0;

          if (audit)
            audit_func(dat, fs.space_names[feature].get());

          if (cur_data == fgd)  // first namespace
          {
            next_data->hash = FNV_prime * (uint64_t)fs.indicies[feature];
            next_data->x = fs.values[feature];  // data->x == 1.
          }
          else
          {  // feature2 xor (16777619*feature1)
            next_data->hash = FNV_prime * (cur_data->hash ^ (uint64_t)fs.indicies[feature]);
            next_data->x = INTERACTION_VALUE(fs.values[feature], cur_data->x);
          }

          ++cur_data;
        }
        else
        {                     // last namespace - iterate its features and go back
          if (!permutations)  // start value is not a constant in this case
            start_i = fgd2->loop_idx;

          features& fs = *(fgd2->ft_arr);

          feature_value ft_value = fgd2->x;
          feature_index halfhash = fgd2->hash;

          features::features_value_index_audit_range range = fs.values_indices_audit();
          features::iterator_all begin = range.begin();
          begin += start_i;
          features::iterator_all end = range.begin();
          end += fgd2->loop_end + 1;
          inner_kernel<R, S, T, audit, audit_func, W>(dat, begin, end, offset, weights, ft_value, halfhash);

          // trying to go back increasing loop_idx of each namespace by the way

          bool go_further = true;

          do
          {
            --cur_data;
            go_further = (++cur_data->loop_idx > cur_data->loop_end);  // increment loop_idx
            if (audit)
              audit_func(dat, nullptr);
          } while (go_further && cur_data != fgd);

          do_it = !(cur_data == fgd && go_further);
          // if do_it==false - we've reached 0 namespace but its 'cur_data.loop_idx > cur_data.loop_end' -> exit the
          // while loop
        }  // if last namespace
      }    // while do_it
    }
  }  // foreach interaction in all.interactions

  state_data.delete_v();
}

inner_kernel()

template<class R , class S , void(*)(R &, float, S) T, bool audit, void(*)(R &, const audit_strings *) audit_func, class W >

void INTERACTIONS::inner_kernel ( R &  dat, features::iterator_all &  begin, features::iterator_all &  end, const uint64_t  offset, W &  weights, feature_value  ft_value, feature_index  halfhash  )

inline

Definition at line 74 of file interactions_predict.h.

References features_value_index_audit_iterator::audit(), features_value_index_iterator::index(), INTERACTION_VALUE(), and features_value_iterator::value().

{
  if (audit)
  {
    for (; begin != end; ++begin)
    {
      audit_func(dat, begin.audit().get());
      call_T<R, T>(dat, weights, INTERACTION_VALUE(ft_value, begin.value()), (begin.index() ^ halfhash) + offset);
      audit_func(dat, nullptr);
    }
  }
  else
  {
    for (; begin != end; ++begin)
      call_T<R, T>(dat, weights, INTERACTION_VALUE(ft_value, begin.value()), (begin.index() ^ halfhash) + offset);
  }
}

INTERACTION_VALUE()

float INTERACTIONS::INTERACTION_VALUE ( float  value1, float  value2  )

inline

Definition at line 66 of file interactions_predict.h.

Referenced by generate_interactions(), and inner_kernel().

{ return value1 * value2; }

is_printable_namespace()

constexpr bool INTERACTIONS::is_printable_namespace ( const unsigned char  ns )

inline

Definition at line 22 of file interactions.h.

References eval_count_of_generated_ft(), expand_interactions(), printable_end, and sort_and_filter_duplicate_interactions().

Referenced by CCB::calculate_and_insert_interactions().

{
  return ns >= printable_start && ns <= printable_end;
}

must_be_left_sorted()

bool INTERACTIONS::must_be_left_sorted ( const std::string &  oi )

inline

Definition at line 87 of file interactions.cc.

Referenced by sort_and_filter_duplicate_interactions().

{
  if (oi.size() <= 1)
    return true;  // one letter in std::string - no need to sort

  bool diff_ns_found = false;
  bool pair_found = false;

  for (auto i = std::begin(oi); i != std::end(oi) - 1; ++i)
    if (*i == *(i + 1))  // pair found
    {
      if (diff_ns_found)
        return true;  // case 'abb'
      pair_found = true;
    }
    else
    {
      if (pair_found)
        return true;  // case 'aab'
      diff_ns_found = true;
    }

  return false;  // 'aaa' or 'abc'
}

sort_and_filter_duplicate_interactions()

void INTERACTIONS::sort_and_filter_duplicate_interactions	(	std::vector< std::string > &	vec,
		bool	filter_duplicates,
		size_t &	removed_cnt,
		size_t &	sorted_cnt
	)

Definition at line 116 of file interactions.cc.

References a, and must_be_left_sorted().

Referenced by is_printable_namespace(), and parse_feature_tweaks().

{
  // 2 out parameters
  removed_cnt = 0;
  sorted_cnt = 0;

  // interaction value sort + original position
  std::vector<std::pair<std::string, size_t>> vec_sorted;
  for (size_t i = 0; i < vec.size(); ++i)
  {
    std::string sorted_i(vec[i]);
    std::stable_sort(std::begin(sorted_i), std::end(sorted_i));
    vec_sorted.push_back(std::make_pair(sorted_i, i));
  }

  if (filter_duplicates)
  {
    // remove duplicates
    std::stable_sort(vec_sorted.begin(), vec_sorted.end(),
        [](std::pair<std::string, size_t> const& a, std::pair<std::string, size_t> const& b) {
          return a.first < b.first;
        });
    auto last = unique(vec_sorted.begin(), vec_sorted.end(),
        [](std::pair<std::string, size_t> const& a, std::pair<std::string, size_t> const& b) {
          return a.first == b.first;
        });
    vec_sorted.erase(last, vec_sorted.end());

    // report number of removed interactions
    removed_cnt = vec.size() - vec_sorted.size();

    // restore original order
    std::stable_sort(vec_sorted.begin(), vec_sorted.end(),
        [](std::pair<std::string, size_t> const& a, std::pair<std::string, size_t> const& b) {
          return a.second < b.second;
        });
  }

  // we have original vector and vector with duplicates removed + corresponding indexes in original vector
  // plus second vector's data is sorted. We can reuse it if we need interaction to be left sorted.
  // let's make a new vector from these two sources - without dulicates and with sorted data whenever it's needed.
  std::vector<std::string> res;
  for (auto& i : vec_sorted)
  {
    if (must_be_left_sorted(i.first))
    {
      // if so - copy sorted data to result
      res.push_back(i.first);
      ++sorted_cnt;
    }
    else  // else - move unsorted data to result
      res.push_back(vec[i.second]);
  }

  vec = res;
}

Variable Documentation

fast_factorial

constexpr int64_t INTERACTIONS::fast_factorial[]

Initial value:

= {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600,
    6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6402373705728000, 121645100408832000,
    2432902008176640000}

Definition at line 203 of file interactions.cc.

feature_self_interactions

constexpr bool INTERACTIONS::feature_self_interactions = true

Definition at line 23 of file interactions_predict.h.

printable_end

constexpr unsigned char INTERACTIONS::printable_end = '~'

Definition at line 17 of file interactions.h.

Referenced by expand_namespaces_with_recursion(), and is_printable_namespace().

printable_ns_size

constexpr unsigned char INTERACTIONS::printable_ns_size = printable_end - printable_start

Definition at line 18 of file interactions.h.

printable_start

constexpr unsigned char INTERACTIONS::printable_start = ' '

Definition at line 16 of file interactions.h.

Referenced by CCB::calculate_and_insert_interactions(), and expand_namespaces_with_recursion().

size_fast_factorial

constexpr size_t INTERACTIONS::size_fast_factorial = sizeof(fast_factorial) / sizeof(*fast_factorial)

Definition at line 206 of file interactions.cc.

valid_ns_size

constexpr uint64_t INTERACTIONS::valid_ns_size

Initial value:

=
    printable_end - printable_start - 1

Definition at line 19 of file interactions.h.