Intermediate-level functions used in building the tree

These functions are are used in top-level tree-building code (Top-level tree-building functions); see Decision tree internals for documentation. More...

Collaboration diagram for Intermediate-level functions used in building the tree:

Functions
EventMap *	TrivialTree (int32 *num_leaves)
	Returns a tree with just one node. More...
EventMap *	DoTableSplit (const EventMap &orig, EventKeyType key, const BuildTreeStatsType &stats, int32 *num_leaves)
	DoTableSplit does a complete split on this key (e.g. More...
EventMap *	DoTableSplitMultiple (const EventMap &orig, const std::vector< EventKeyType > &keys, const BuildTreeStatsType &stats, int32 *num_leaves)
	DoTableSplitMultiple does a complete split on all the keys, in order from keys[0], keys[1] and so on. More...
int	ClusterEventMapGetMapping (const EventMap &e_in, const BuildTreeStatsType &stats, BaseFloat thresh, std::vector< EventMap * > *mapping)
	"ClusterEventMapGetMapping" clusters the leaves of the EventMap, with "thresh" a delta-likelihood threshold to control how many leaves we combine (might be the same as the delta-like threshold used in splitting. More...
EventMap *	ClusterEventMap (const EventMap &e_in, const BuildTreeStatsType &stats, BaseFloat thresh, int32 *num_removed)
	This is as ClusterEventMapGetMapping but a more convenient interface that exposes less of the internals. More...
EventMap *	ClusterEventMapRestrictedByKeys (const EventMap &e_in, const BuildTreeStatsType &stats, BaseFloat thresh, const std::vector< EventKeyType > &keys, int32 *num_removed)
	This is as ClusterEventMap, but first splits the stats on the keys specified in "keys" (e.g. More...
EventMap *	ClusterEventMapRestrictedByMap (const EventMap &e_in, const BuildTreeStatsType &stats, BaseFloat thresh, const EventMap &e_restrict, int32 *num_removed)
	This version of ClusterEventMapRestricted restricts the clustering to only allow things that "e_restrict" maps to the same value to be clustered together. More...
EventMap *	ClusterEventMapToNClustersRestrictedByMap (const EventMap &e_in, const BuildTreeStatsType &stats, int32 num_clusters, const EventMap &e_restrict, int32 *num_removed)
	This version of ClusterEventMapRestrictedByMap clusters to get a specific number of clusters as specified by 'num_clusters'. More...
EventMap *	RenumberEventMap (const EventMap &e_in, int32 *num_leaves)
	RenumberEventMap [intended to be used after calling ClusterEventMap] renumbers an EventMap so its leaves are consecutive. More...
EventMap *	MapEventMapLeaves (const EventMap &e_in, const std::vector< int32 > &mapping)
	This function remaps the event-map leaves using this mapping, indexed by the number at leaf. More...
EventMap *	ShareEventMapLeaves (const EventMap &e_in, EventKeyType key, std::vector< std::vector< EventValueType > > &values, int32 *num_leaves)
	ShareEventMapLeaves performs a quite specific function that allows us to generate trees where, for a certain list of phones, and for all states in the phone, all the pdf's are shared. More...
EventMap *	SplitDecisionTree (const EventMap &orig, const BuildTreeStatsType &stats, Questions &qcfg, BaseFloat thresh, int32 max_leaves, int32 *num_leaves, BaseFloat *objf_impr_out, BaseFloat *smallest_split_change_out)
	Does a decision-tree split at the leaves of an EventMap. More...
void	CreateRandomQuestions (const BuildTreeStatsType &stats, int32 num_quest, Questions *cfg_out)
	CreateRandomQuestions will initialize a Questions randomly, in a reasonable way [for testing purposes, or when hand-designed questions are not available]. More...
BaseFloat	FindBestSplitForKey (const BuildTreeStatsType &stats, const Questions &qcfg, EventKeyType key, std::vector< EventValueType > *yes_set)
	FindBestSplitForKey is a function used in DoDecisionTreeSplit. More...
EventMap *	GetStubMap (int32 P, const std::vector< std::vector< int32 > > &phone_sets, const std::vector< int32 > &phone2num_pdf_classes, const std::vector< bool > &share_roots, int32 *num_leaves)
	GetStubMap is used in tree-building functions to get the initial to-states map, before the decision-tree-building process. More...

Detailed Description

These functions are are used in top-level tree-building code (Top-level tree-building functions); see Decision tree internals for documentation.

Function Documentation

ClusterEventMap()

EventMap * ClusterEventMap	(	const EventMap &	e_in,
		const BuildTreeStatsType &	stats,
		BaseFloat	thresh,
		int32 *	num_removed
	)

This is as ClusterEventMapGetMapping but a more convenient interface that exposes less of the internals.

It uses a bottom-up clustering to combine the leaves, until the log-likelihood decrease from combinging two leaves exceeds the threshold.

Definition at line 699 of file build-tree-utils.cc.

References kaldi::ClusterEventMapGetMapping(), EventMap::Copy(), and kaldi::DeletePointers().

Referenced by kaldi::TestClusterEventMap(), and kaldi::TestClusterEventMapRestricted().

                                                                    {
  std::vector<EventMap*> mapping;
  int32 num_removed = ClusterEventMapGetMapping(e_in, stats, thresh, &mapping);
  EventMap *ans = e_in.Copy(mapping);
  DeletePointers(&mapping);
  if (num_removed_ptr != NULL) *num_removed_ptr = num_removed;
  return ans;

}

ClusterEventMapGetMapping()

int ClusterEventMapGetMapping	(	const EventMap &	e_in,
		const BuildTreeStatsType &	stats,
		BaseFloat	thresh,
		std::vector< EventMap * > *	mapping
	)

"ClusterEventMapGetMapping" clusters the leaves of the EventMap, with "thresh" a delta-likelihood threshold to control how many leaves we combine (might be the same as the delta-like threshold used in splitting.

Definition at line 599 of file build-tree-utils.cc.

References kaldi::ClusterBottomUp(), kaldi::DeletePointers(), rnnlm::i, KALDI_ASSERT, KALDI_VLOG, KALDI_WARN, kaldi::SplitStatsByMap(), kaldi::SumClusterableNormalizer(), and kaldi::SumStatsVec().

Referenced by kaldi::ClusterEventMap(), kaldi::ClusterEventMapRestrictedByMap(), kaldi::ClusterEventMapRestrictedHelper(), kaldi::TestClusterEventMapGetMappingAndRenumberEventMap(), and kaldi::TestClusterEventMapGetMappingAndRenumberEventMap2().

                                                             {
  // First map stats
  KALDI_ASSERT(stats.size() != 0);
  std::vector<BuildTreeStatsType> split_stats;
  SplitStatsByMap(stats, e_in, &split_stats);
  std::vector<Clusterable*> summed_stats;
  SumStatsVec(split_stats, &summed_stats);

  std::vector<int32> indexes;
  std::vector<Clusterable*> summed_stats_contiguous;
  size_t max_index = 0;
  for (size_t i = 0;i < summed_stats.size();i++) {
    if (summed_stats[i] != NULL) {
      indexes.push_back(i);
      summed_stats_contiguous.push_back(summed_stats[i]);
      if (i > max_index) max_index = i;
    }
  }
  if (summed_stats_contiguous.empty()) {
    KALDI_WARN << "ClusterBottomUp: nothing to cluster.";
    return 0;  // nothing merged.
  }

  std::vector<int32> assignments;
  BaseFloat normalizer = SumClusterableNormalizer(summed_stats_contiguous),
      change;
  change = ClusterBottomUp(summed_stats_contiguous,
                           thresh,
                           0,  // no min-clust: use threshold for now.
                           NULL,  // don't need clusters out.
                           &assignments);  // this algorithm is quadratic, so might be quite slow.


  KALDI_ASSERT(assignments.size() == summed_stats_contiguous.size() && !assignments.empty());
  size_t num_clust = * std::max_element(assignments.begin(), assignments.end()) + 1;
  int32 num_combined = summed_stats_contiguous.size() - num_clust;
  KALDI_ASSERT(num_combined >= 0);

  KALDI_VLOG(2) <<  "ClusterBottomUp combined "<< num_combined
                << " leaves and gave a likelihood change of " << change
                << ", normalized = " << (change/normalizer)
                << ", normalizer = " << normalizer;
  KALDI_ASSERT(change < 0.0001);  // should be negative or zero.

  KALDI_ASSERT(mapping != NULL);
  if (max_index >= mapping->size()) mapping->resize(max_index+1, NULL);

  for (size_t i = 0;i < summed_stats_contiguous.size();i++) {
    size_t index = indexes[i];
    size_t new_index = indexes[assignments[i]];  // index assigned by clusterig-- map to existing indices in the map,
    // that we clustered from, so we don't conflict with indices in other parts
    // of the tree.
    KALDI_ASSERT((*mapping)[index] == NULL || "Error: Cluster seems to have been "
                 "called for different parts of the tree with overlapping sets of "
                 "indices.");
    (*mapping)[index] = new ConstantEventMap(new_index);
  }
  DeletePointers(&summed_stats);
  return num_combined;
}

ClusterEventMapRestrictedByKeys()

EventMap * ClusterEventMapRestrictedByKeys	(	const EventMap &	e_in,
		const BuildTreeStatsType &	stats,
		BaseFloat	thresh,
		const std::vector< EventKeyType > &	keys,
		int32 *	num_removed
	)

This is as ClusterEventMap, but first splits the stats on the keys specified in "keys" (e.g.

typically keys = [ -1, P ]), and only clusters within the classes defined by that splitting. Note– leaves will be non-consecutive at output, use RenumberEventMap.

Definition at line 822 of file build-tree-utils.cc.

References kaldi::ClusterEventMapRestrictedHelper(), EventMap::Copy(), and kaldi::DeletePointers().

Referenced by kaldi::TestClusterEventMapRestricted().

                                                              {
  std::vector<EventMap*> leaf_mapping;  // For output of ClusterEventMapGetMapping.

  int32 nr = ClusterEventMapRestrictedHelper(e_in, stats, thresh, keys, &leaf_mapping);
  if (num_removed != NULL) *num_removed = nr;

  EventMap *ans = e_in.Copy(leaf_mapping);
  DeletePointers(&leaf_mapping);
  return ans;
}

ClusterEventMapRestrictedByMap()

EventMap * ClusterEventMapRestrictedByMap	(	const EventMap &	e_in,
		const BuildTreeStatsType &	stats,
		BaseFloat	thresh,
		const EventMap &	e_restrict,
		int32 *	num_removed
	)

This version of ClusterEventMapRestricted restricts the clustering to only allow things that "e_restrict" maps to the same value to be clustered together.

Definition at line 838 of file build-tree-utils.cc.

References kaldi::ClusterEventMapGetMapping(), EventMap::Copy(), kaldi::DeletePointers(), rnnlm::i, and kaldi::SplitStatsByMap().

Referenced by kaldi::BuildTree(), kaldi::BuildTreeTwoLevel(), and kaldi::TestClusterEventMapRestricted().

                                                                 {
  std::vector<EventMap*> leaf_mapping;

  std::vector<BuildTreeStatsType> split_stats;
  int num_removed = 0;
  SplitStatsByMap(stats, e_restrict, &split_stats);
  for (size_t i = 0; i < split_stats.size(); i++) {
    if (!split_stats[i].empty())
      num_removed += ClusterEventMapGetMapping(e_in, split_stats[i], thresh,
                                               &leaf_mapping);
  }

  if (num_removed_ptr != NULL) *num_removed_ptr = num_removed;

  EventMap *ans = e_in.Copy(leaf_mapping);
  DeletePointers(&leaf_mapping);
  return ans;
}

ClusterEventMapToNClustersRestrictedByMap()

EventMap * ClusterEventMapToNClustersRestrictedByMap	(	const EventMap &	e_in,
		const BuildTreeStatsType &	stats,
		int32	num_clusters_required,
		const EventMap &	e_restrict,
		int32 *	num_removed_ptr
	)

This version of ClusterEventMapRestrictedByMap clusters to get a specific number of clusters as specified by 'num_clusters'.

Definition at line 861 of file build-tree-utils.cc.

References kaldi::ClusterBottomUpCompartmentalized(), EventMap::Copy(), kaldi::DeletePointers(), rnnlm::i, rnnlm::j, KALDI_ASSERT, KALDI_VLOG, KALDI_WARN, kaldi::SplitStatsByMap(), kaldi::SumClusterableNormalizer(), and kaldi::SumStatsVec().

Referenced by kaldi::BuildTree().

                            {
  std::vector<BuildTreeStatsType> split_stats;
  SplitStatsByMap(stats, e_restrict, &split_stats);

  if (num_clusters_required < split_stats.size()) {
    KALDI_WARN << "num-clusters-required is less than size of map. Not doing anything.";
    if (num_removed_ptr) *num_removed_ptr = 0;
    return e_in.Copy();
  }

  std::vector<std::vector<int32> > indexes(split_stats.size());
  std::vector<std::vector<Clusterable*> > summed_stats_contiguous(split_stats.size());

  BaseFloat normalizer = 0.0;

  size_t max_index = 0;

  int32 num_non_empty_clusters_required = num_clusters_required;

  int32 num_non_empty_clusters_in_map = 0;
  int32 num_non_empty_clusters = 0;

  for (size_t i = 0; i < split_stats.size(); i++) {
    if (!split_stats[i].empty()) {
      num_non_empty_clusters_in_map++;

      std::vector<BuildTreeStatsType> split_stats_i;
      SplitStatsByMap(split_stats[i], e_in, &split_stats_i);
      std::vector<Clusterable*> summed_stats_i;
      SumStatsVec(split_stats_i, &summed_stats_i);

      for (size_t j = 0; j < summed_stats_i.size(); j++) {
        if (summed_stats_i[j] != NULL) {
          num_non_empty_clusters++;
          indexes[i].push_back(j);
          summed_stats_contiguous[i].push_back(summed_stats_i[j]);
          if (j > max_index) max_index = j;
        }
      }

      normalizer += SumClusterableNormalizer(summed_stats_contiguous[i]);
    } else {
      // Even if split_stats[i] is empty, a cluster will be assigned to
      // that. To compensate, we decrease the num-clusters required.
      num_non_empty_clusters_required--;
    }
  }

  KALDI_VLOG(1) << "Number of non-empty clusters in map = " << num_non_empty_clusters_in_map;
  KALDI_VLOG(1) << "Number of non-empty clusters = " << num_non_empty_clusters;

  if (num_non_empty_clusters_required > num_non_empty_clusters) {
    KALDI_WARN << "Cannot get required num-clusters " << num_clusters_required
               << " as number of non-empty clusters required is larger than "
               << " number of non-empty clusters: " << num_non_empty_clusters_required
               << " > " << num_non_empty_clusters;
    if (num_removed_ptr) *num_removed_ptr = 0;
    return e_in.Copy();
  }

  std::vector<std::vector<int32> > assignments;
  BaseFloat change = ClusterBottomUpCompartmentalized(
      summed_stats_contiguous,
      std::numeric_limits<BaseFloat>::infinity(),
      num_non_empty_clusters_required,
      NULL,  // don't need clusters out.
      &assignments);  // this algorithm is quadratic, so might be quite slow.

  KALDI_ASSERT(assignments.size() == split_stats.size());

  int32 num_combined = 0;
  for (size_t i = 0; i < split_stats.size(); i++) {
    KALDI_ASSERT(assignments[i].size() == summed_stats_contiguous[i].size());
    if (assignments[i].size() == 0) continue;
    size_t num_clust_i = *std::max_element(assignments[i].begin(),
                                           assignments[i].end()) + 1;
    num_combined += summed_stats_contiguous[i].size() - num_clust_i;
  }

  KALDI_VLOG(2) << "ClusterBottomUpCompartmentalized combined " << num_combined
                << " leaves and gave a likelihood change of " << change
                << ", normalized = " << (change / normalizer)
                << ", normalizer = " << normalizer;
  KALDI_ASSERT(change < 0.0001);  // should be negative or zero.

  std::vector<EventMap*> leaf_mapping(max_index + 1, NULL);

  for (size_t i = 0; i < split_stats.size(); i++) {
    for (size_t j = 0; j < summed_stats_contiguous[i].size(); j++) {
      size_t index = indexes[i][j];
      size_t new_index = indexes[i][assignments[i][j]];
      // index assigned by clusterig-- map to existing indices in the map,
      // that we clustered from, so we don't conflict with indices in other parts
      // of the tree.
      KALDI_ASSERT(leaf_mapping[index] == NULL || "Error: Cluster seems to have been "
                   "called for different parts of the tree with overlapping sets of "
                   "indices.");
      leaf_mapping[index] = new ConstantEventMap(new_index);
    }
    DeletePointers(&summed_stats_contiguous[i]);
  }

  if (num_removed_ptr) *num_removed_ptr = num_combined;

  EventMap *ans = e_in.Copy(leaf_mapping);
  DeletePointers(&leaf_mapping);
  return ans;
}

CreateRandomQuestions()

void kaldi::CreateRandomQuestions	(	const BuildTreeStatsType &	stats,
		int32	num_quest,
		Questions *	cfg_out
	)

CreateRandomQuestions will initialize a Questions randomly, in a reasonable way [for testing purposes, or when hand-designed questions are not available].

e.g. num_quest = 5 might be a reasonable value if num_iters > 0, or num_quest = 20 otherwise.

DoTableSplit()

EventMap * DoTableSplit	(	const EventMap &	orig,
		EventKeyType	key,
		const BuildTreeStatsType &	stats,
		int32 *	num_leaves
	)

DoTableSplit does a complete split on this key (e.g.

might correspond to central phone (key = P-1), or HMM-state position (key == kPdfClass == -1). Stats used to work out possible values of the event. "num_leaves" is used to allocate new leaves. All stats must have this key defined, or this function will crash.

Definition at line 126 of file build-tree-utils.cc.

References EventMap::Copy(), kaldi::DeletePointers(), KALDI_ASSERT, kaldi::PossibleValues(), and kaldi::SplitStatsByMap().

Referenced by kaldi::DoTableSplitMultiple(), kaldi::TestClusterEventMap(), kaldi::TestClusterEventMapGetMappingAndRenumberEventMap(), kaldi::TestClusterEventMapGetMappingAndRenumberEventMap2(), and kaldi::TestDoTableSplit().

                                          {
  // First-- map the stats to each leaf in the EventMap.
  std::vector<BuildTreeStatsType> split_stats;
  SplitStatsByMap(stats, orig, &split_stats);
  // Now for each leaf that has stats in it, do the table split according to the given name.
  std::vector<EventMap*> splits(split_stats.size(), NULL);
  for (EventAnswerType leaf = 0; leaf < (EventAnswerType)split_stats.size(); leaf++) {
    if (!split_stats[leaf].empty()) {
      // first work out the possible values the name takes.
      std::vector<EventValueType> vals;  // vals are put here, sorted.
      bool all_present = PossibleValues(key, split_stats[leaf], &vals);
      KALDI_ASSERT(all_present);  // currently do not support mapping undefined values.
      KALDI_ASSERT(!vals.empty() && vals.front() >= 0);  // don't support mapping negative values
      // at present time-- would need different EventMap type, not TableEventMap.
      std::vector<EventMap*> table(vals.back()+1, (EventMap*)NULL);
      for (size_t idx = 0;idx < vals.size();idx++) {
        EventValueType val = vals[idx];
        if (idx == 0) table[val] = new ConstantEventMap(leaf);  // reuse current leaf.
        else table[val] = new ConstantEventMap( (*num_leaves)++ );  // else take new leaf id.
      }
      // takes ownershipof stats.
      splits[leaf] = new TableEventMap(key, table);
    }
  }
  EventMap *ans = orig.Copy(splits);
  DeletePointers(&splits);
  return ans;
}

DoTableSplitMultiple()

EventMap * DoTableSplitMultiple	(	const EventMap &	orig,
		const std::vector< EventKeyType > &	keys,
		const BuildTreeStatsType &	stats,
		int32 *	num_leaves
	)

DoTableSplitMultiple does a complete split on all the keys, in order from keys[0], keys[1] and so on.

The stats are used to work out possible values corresponding to the key. "num_leaves" is used to allocate new leaves. All stats must have the keys defined, or this function will crash. Returns a newly allocated event map.

Definition at line 156 of file build-tree-utils.cc.

References EventMap::Copy(), kaldi::DoTableSplit(), and rnnlm::i.

Referenced by kaldi::TestClusterEventMapRestricted(), and kaldi::TestShareEventMapLeaves().

                                                                                                                                               {

  if (keys.empty()) return orig.Copy();
  else {
    EventMap *cur = NULL;  // would make it &orig, except for const issues.
    for (size_t i = 0; i < keys.size(); i++) {
      EventMap *next = DoTableSplit( (cur ? *cur : orig), keys[i], stats, num_leaves);
      delete cur;  // delete intermediate maps.
      cur = next;
    }
    return cur;
  }
}

FindBestSplitForKey()

BaseFloat FindBestSplitForKey	(	const BuildTreeStatsType &	stats,
		const Questions &	qcfg,
		EventKeyType	key,
		std::vector< EventValueType > *	yes_set
	)

FindBestSplitForKey is a function used in DoDecisionTreeSplit.

It finds the best split for this key, given these stats. It will return 0 if the key was not always defined for the stats.

Definition at line 348 of file build-tree-utils.cc.

References kaldi::AddToClusters(), kaldi::ApproxEqual(), kaldi::ComputeInitialSplit(), kaldi::DeletePointers(), kaldi::EnsureClusterableVectorNotNull(), Questions::GetQuestionsOf(), rnnlm::i, KALDI_ASSERT, KALDI_WARN, RefineClustersOptions::num_iters, kaldi::PossibleValues(), QuestionsForKey::refine_opts, kaldi::RefineClusters(), kaldi::SplitStatsByKey(), and kaldi::SumStatsVec().

Referenced by DecisionTreeSplitter::FindBestSplit().

                                                                      {
  if (stats.size()<=1) return 0.0;  // cannot split if only zero or one instance of stats.
  if (!PossibleValues(key, stats, NULL)) {
    yes_set_out->clear();
    return 0.0;  // Can't split as key not always defined.
  }
  std::vector<Clusterable*> summed_stats;  // indexed by value corresponding to key. owned here.
  {  // compute summed_stats
    std::vector<BuildTreeStatsType> split_stats;
    SplitStatsByKey(stats, key, &split_stats);
    SumStatsVec(split_stats, &summed_stats);
  }

  std::vector<EventValueType> yes_set;
  BaseFloat improvement = ComputeInitialSplit(summed_stats,
                                               q_opts, key, &yes_set);
  // find best basic question.

  std::vector<int32> assignments(summed_stats.size(), 0);  // assigns to "no" (0) by default.
  for (std::vector<EventValueType>::const_iterator iter = yes_set.begin(); iter != yes_set.end(); ++iter) {
    KALDI_ASSERT(*iter>=0);
    if (*iter < (EventValueType)assignments.size()) {
      // this guard necessary in case stats did not have all the
      // values present in "yes_set".
      assignments[*iter] = 1;  // assign to "yes" (1).
    }
  }
  std::vector<Clusterable*> clusters(2, (Clusterable*)NULL);  // no, yes.
  kaldi::AddToClusters(summed_stats, assignments, &clusters);

  EnsureClusterableVectorNotNull(&summed_stats);
  EnsureClusterableVectorNotNull(&clusters);

  // even if improvement == 0 we continue; if we do RefineClusters we may get further improvement.
  // now do the RefineClusters stuff.  Note that this is null-op if
  // q_opts.GetQuestionsOf(key).refine_opts.num_iters == 0.  We could check for this but don't bother;
  // it happens in RefineClusters anyway.

  if (q_opts.GetQuestionsOf(key).refine_opts.num_iters > 0) {
    // If we want to refine the questions... (a bit like k-means w/ 2 classes).
    // Note: the only reason we introduced the if-statement is so the yes_set
    // doesn't get modified (truncated, actually) if we do the refine stuff with
    // zero iters.
    BaseFloat refine_impr = RefineClusters(summed_stats, &clusters, &assignments,
                                           q_opts.GetQuestionsOf(key).refine_opts);
    KALDI_ASSERT(refine_impr > std::min(-1.0, -0.1*fabs(improvement)));
    // refine_impr should always be positive
    improvement += refine_impr;
    yes_set.clear();
    for (size_t i = 0;i < assignments.size();i++) if (assignments[i] == 1) yes_set.push_back(i);
  }
  *yes_set_out = yes_set;

  DeletePointers(&clusters);
#ifdef KALDI_PARANOID
  {  // Check the "ans" is correct.
    KALDI_ASSERT(clusters.size() == 2 && clusters[0] == 0 && clusters[1] == 0);
    AddToClusters(summed_stats, assignments, &clusters);
    BaseFloat impr;
    if (clusters[0] == NULL || clusters[1] == NULL) impr = 0.0;
    else impr = clusters[0]->Distance(*(clusters[1]));
    if (!ApproxEqual(impr, improvement) && fabs(impr-improvement) > 0.01) {
      KALDI_WARN << "FindBestSplitForKey: improvements do not agree: "<< impr
                 << " vs. " << improvement;
    }
    DeletePointers(&clusters);
  }
#endif
  DeletePointers(&summed_stats);
  return improvement; // objective-function improvement.
}

GetStubMap()

EventMap * GetStubMap	(	int32	P,
		const std::vector< std::vector< int32 > > &	phone_sets,
		const std::vector< int32 > &	phone2num_pdf_classes,
		const std::vector< bool > &	share_roots,
		int32 *	num_leaves
	)

GetStubMap is used in tree-building functions to get the initial to-states map, before the decision-tree-building process.

It creates a simple map that splits on groups of phones. For the set of phones in phone_sets[i] it creates either: if share_roots[i] == true, a single leaf node, or if share_roots[i] == false, separate root nodes for each HMM-position (it goes up to the highest position for any phone in the set, although it will warn if you share roots between phones with different numbers of states, which is a weird thing to do but should still work. If any phone is present in "phone_sets" but "phone2num_pdf_classes" does not map it to a length, it is an error. Note that the behaviour of the resulting map is undefined for phones not present in "phone_sets". At entry, this function should be called with (*num_leaves == 0). It will number the leaves starting from (*num_leaves).

Definition at line 975 of file build-tree-utils.cc.

References rnnlm::i, kaldi::IsSortedAndUniq(), rnnlm::j, KALDI_ASSERT, KALDI_WARN, and kaldi::kPdfClass.

Referenced by kaldi::BuildTree(), kaldi::MonophoneContextDependency(), and kaldi::MonophoneContextDependencyShared().

                                            {

  {  // Checking inputs.
    KALDI_ASSERT(!phone_sets.empty() && share_roots.size() == phone_sets.size());
    std::set<int32> all_phones;
    for (size_t i = 0; i < phone_sets.size(); i++) {
      KALDI_ASSERT(IsSortedAndUniq(phone_sets[i]));
      KALDI_ASSERT(!phone_sets[i].empty());
      for (size_t j = 0; j < phone_sets[i].size(); j++) {
        KALDI_ASSERT(all_phones.count(phone_sets[i][j]) == 0);  // check not present.
        all_phones.insert(phone_sets[i][j]);
      }
    }
  }

  // Initially create a single leaf for each phone set.

  size_t max_set_size = 0;
  int32 highest_numbered_phone = 0;
  for (size_t i = 0; i < phone_sets.size(); i++) {
    max_set_size = std::max(max_set_size, phone_sets[i].size());
    highest_numbered_phone =
        std::max(highest_numbered_phone,
                 * std::max_element(phone_sets[i].begin(), phone_sets[i].end()));
  }

  if (phone_sets.size() == 1) {  // there is only one set so the recursion finishes.
    if (share_roots[0]) {  // if "shared roots" return a single leaf.
      return new ConstantEventMap( (*num_leaves_out)++ );
    } else {  // not sharing roots -> work out the length and return a
             // TableEventMap splitting on length.
      EventAnswerType max_len = 0;
      for (size_t i = 0; i < phone_sets[0].size(); i++) {
        EventAnswerType len;
        EventValueType phone = phone_sets[0][i];
        KALDI_ASSERT(static_cast<size_t>(phone) < phone2num_pdf_classes.size());
        len = phone2num_pdf_classes[phone];
        KALDI_ASSERT(len > 0);
        if (i == 0) max_len = len;
        else {
          if (len != max_len) {
            KALDI_WARN << "Mismatching lengths within a phone set: " << len
                       << " vs. " << max_len << " [unusual, but not necessarily fatal]. ";
            max_len = std::max(len, max_len);
          }
        }
      }
      std::map<EventValueType, EventAnswerType> m;
      for (EventAnswerType p = 0; p < max_len; p++)
        m[p] = (*num_leaves_out)++;
      return new TableEventMap(kPdfClass,  // split on hmm-position
                               m);
    }
  } else if (max_set_size == 1
            && static_cast<int32>(phone_sets.size()) <= 2*highest_numbered_phone) {
    // create table map splitting on phone-- more efficient.
    // the part after the && checks that this would not contain a very sparse vector.
    std::map<EventValueType, EventMap*> m;
    for (size_t i = 0; i < phone_sets.size(); i++) {
      std::vector<std::vector<int32> > phone_sets_tmp;
      phone_sets_tmp.push_back(phone_sets[i]);
      std::vector<bool> share_roots_tmp;
      share_roots_tmp.push_back(share_roots[i]);
      EventMap *this_stub = GetStubMap(P, phone_sets_tmp, phone2num_pdf_classes,
                                       share_roots_tmp,
                                       num_leaves_out);
      KALDI_ASSERT(m.count(phone_sets_tmp[0][0]) == 0);
      m[phone_sets_tmp[0][0]] = this_stub;
    }
    return new TableEventMap(P, m);
  } else {
    // Do a split.  Recurse.
    size_t half_sz = phone_sets.size() / 2;
    std::vector<std::vector<int32> >::const_iterator half_phones =
        phone_sets.begin() + half_sz;
    std::vector<bool>::const_iterator half_share =
        share_roots.begin() + half_sz;
    std::vector<std::vector<int32> > phone_sets_1, phone_sets_2;
    std::vector<bool> share_roots_1, share_roots_2;
    phone_sets_1.insert(phone_sets_1.end(), phone_sets.begin(), half_phones);
    phone_sets_2.insert(phone_sets_2.end(), half_phones, phone_sets.end());
    share_roots_1.insert(share_roots_1.end(), share_roots.begin(), half_share);
    share_roots_2.insert(share_roots_2.end(), half_share, share_roots.end());

    EventMap *map1 = GetStubMap(P, phone_sets_1, phone2num_pdf_classes, share_roots_1, num_leaves_out);
    EventMap *map2 = GetStubMap(P, phone_sets_2, phone2num_pdf_classes, share_roots_2, num_leaves_out);

    std::vector<EventKeyType> all_in_first_set;
    for (size_t i = 0; i < half_sz; i++)
      for (size_t j = 0; j < phone_sets[i].size(); j++)
        all_in_first_set.push_back(phone_sets[i][j]);
    std::sort(all_in_first_set.begin(), all_in_first_set.end());
    KALDI_ASSERT(IsSortedAndUniq(all_in_first_set));
    return new SplitEventMap(P, all_in_first_set, map1, map2);
  }
}

MapEventMapLeaves()

EventMap * MapEventMapLeaves	(	const EventMap &	e_in,
		const std::vector< int32 > &	mapping
	)

This function remaps the event-map leaves using this mapping, indexed by the number at leaf.

Definition at line 689 of file build-tree-utils.cc.

References EventMap::Copy(), kaldi::DeletePointers(), and rnnlm::i.

Referenced by kaldi::BuildTreeTwoLevel().

                                                                {
  std::vector<EventMap*> mapping(mapping_in.size());
  for (size_t i = 0; i < mapping_in.size(); i++)
    mapping[i] = new ConstantEventMap(mapping_in[i]);
  EventMap *ans = e_in.Copy(mapping);
  DeletePointers(&mapping);
  return ans;
}

RenumberEventMap()

EventMap * RenumberEventMap	(	const EventMap &	e_in,
		int32 *	num_leaves
	)

RenumberEventMap [intended to be used after calling ClusterEventMap] renumbers an EventMap so its leaves are consecutive.

It puts the number of leaves in *num_leaves. If later you need the mapping of the leaves, modify the function and add a new argument.

Definition at line 664 of file build-tree-utils.cc.

References EventMap::Copy(), kaldi::DeletePointers(), KALDI_ASSERT, EventMap::MultiMap(), and kaldi::SortAndUniq().

Referenced by kaldi::BuildTree(), kaldi::BuildTreeTwoLevel(), kaldi::ShareEventMapLeaves(), kaldi::TestClusterEventMapGetMappingAndRenumberEventMap(), and kaldi::TestClusterEventMapGetMappingAndRenumberEventMap2().

                                                                    {
  EventType empty_vec;
  std::vector<EventAnswerType> initial_leaves;  // before renumbering.
  e_in.MultiMap(empty_vec, &initial_leaves);
  if (initial_leaves.empty()) {
    KALDI_ASSERT(num_leaves);
    if (num_leaves) *num_leaves = 0;
    return e_in.Copy();
  }
  SortAndUniq(&initial_leaves);
  EventAnswerType max_leaf_plus_one = initial_leaves.back() + 1;  // will typically, but not always, equal *num_leaves.
  std::vector<EventMap*> mapping(max_leaf_plus_one, (EventMap*)NULL);
  std::vector<EventAnswerType>::iterator iter = initial_leaves.begin(), end = initial_leaves.end();
  EventAnswerType cur_leaf = 0;
  for (; iter != end; ++iter) {
    KALDI_ASSERT(*iter >= 0 && *iter<max_leaf_plus_one);
    mapping[*iter] = new ConstantEventMap(cur_leaf++);
  }
  EventMap *ans = e_in.Copy(mapping);
  DeletePointers(&mapping);
  KALDI_ASSERT((size_t)cur_leaf == initial_leaves.size());
  if (num_leaves) *num_leaves = cur_leaf;
  return ans;
}

ShareEventMapLeaves()

EventMap * ShareEventMapLeaves	(	const EventMap &	e_in,
		EventKeyType	key,
		std::vector< std::vector< EventValueType > > &	values,
		int32 *	num_leaves
	)

ShareEventMapLeaves performs a quite specific function that allows us to generate trees where, for a certain list of phones, and for all states in the phone, all the pdf's are shared.

Each element of "values" contains a list of phones (may be just one phone), all states of which we want shared together). Typically at input, "key" will equal P, the central-phone position, and "values" will contain just one list containing the silence phone. This function renumbers the event map leaves after doing the sharing, to make the event-map leaves contiguous.

Definition at line 710 of file build-tree-utils.cc.

References EventMap::Copy(), kaldi::DeletePointers(), rnnlm::i, rnnlm::j, KALDI_ASSERT, KALDI_WARN, kaldi::MakeEventPair(), EventMap::MultiMap(), kaldi::RenumberEventMap(), and kaldi::SortAndUniq().

Referenced by kaldi::TestShareEventMapLeaves().

                                                 {
  // the use of "pdfs" as the name of the next variable reflects the anticipated
  // use of this function.
  std::vector<std::vector<EventAnswerType> > pdfs(values.size());
  for (size_t i = 0; i < values.size(); i++) {
    EventType evec;
    for (size_t j = 0; j < values[i].size(); j++) {
      evec.push_back(MakeEventPair(key, values[i][j]));
      size_t size_at_start = pdfs[i].size();
      e_in.MultiMap(evec, &(pdfs[i]));  // append any corresponding pdfs to pdfs[i].
      if (pdfs[i].size() == size_at_start) {  // Nothing added... unexpected.
        KALDI_WARN << "ShareEventMapLeaves: had no leaves for key = " << key
                   << ", value = " << (values[i][j]);
      }
    }
    SortAndUniq(&(pdfs[i]));
  }
  std::vector<EventMap*> remapping;
  for (size_t i = 0; i < values.size(); i++) {
    if (pdfs[i].empty())
      KALDI_WARN << "ShareEventMapLeaves: no leaves in one bucket.";  // not expected.
    else {
      EventAnswerType map_to_this = pdfs[i][0];  // map all in this bucket
      // to this value.
      for (size_t j = 1; j < pdfs[i].size(); j++) {
        EventAnswerType leaf = pdfs[i][j];
        KALDI_ASSERT(leaf>=0);
        if (remapping.size() <= static_cast<size_t>(leaf))
          remapping.resize(leaf+1, NULL);
        KALDI_ASSERT(remapping[leaf] == NULL);
        remapping[leaf] = new ConstantEventMap(map_to_this);
      }
    }
  }
  EventMap *shared = e_in.Copy(remapping);
  DeletePointers(&remapping);
  EventMap *renumbered = RenumberEventMap(*shared, num_leaves);
  delete shared;
  return renumbered;
}

SplitDecisionTree()

EventMap * SplitDecisionTree	(	const EventMap &	orig,
		const BuildTreeStatsType &	stats,
		Questions &	qcfg,
		BaseFloat	thresh,
		int32	max_leaves,
		int32 *	num_leaves,
		BaseFloat *	objf_impr_out,
		BaseFloat *	smallest_split_change_out
	)

Does a decision-tree split at the leaves of an EventMap.

Parameters

orig	[in] The EventMap whose leaves we want to split. [may be either a trivial or a non-trivial one].
stats	[in] The statistics for splitting the tree; if you do not want a particular subset of leaves to be split, make sure the stats corresponding to those leaves are not present in "stats".
qcfg	[in] Configuration class that contains initial questions (e.g. sets of phones) for each key and says whether to refine these questions during tree building.
thresh	[in] A log-likelihood threshold (e.g. 300) that can be used to limit the number of leaves; you can use zero and set max_leaves instead.
max_leaves	[in] Will stop leaves being split after they reach this number.
num_leaves	[in,out] A pointer used to allocate leaves; always corresponds to the current number of leaves (is incremented when this is increased).
objf_impr_out	[out] If non-NULL, will be set to the objective improvement due to splitting (not normalized by the number of frames).
smallest_split_change_out	If non-NULL, will be set to the smallest objective-function improvement that we got from splitting any leaf; useful to provide a threshold for ClusterEventMap.

Returns

The EventMap after splitting is returned; pointer is owned by caller.

Definition at line 532 of file build-tree-utils.cc.

References DecisionTreeSplitter::BestSplit(), EventMap::Copy(), count, DecisionTreeSplitter::DecisionTreeSplitter(), DecisionTreeSplitter::GetMap(), rnnlm::i, KALDI_ASSERT, KALDI_LOG, and kaldi::SplitStatsByMap().

Referenced by kaldi::BuildTree(), kaldi::BuildTreeTwoLevel(), kaldi::TestClusterEventMapRestricted(), kaldi::TestShareEventMapLeaves(), and kaldi::TestSplitDecisionTree().

                                                                  {
  KALDI_ASSERT(num_leaves != NULL && *num_leaves > 0);  // can't be 0 or input_map would be empty.
  int32 num_empty_leaves = 0;
  BaseFloat like_impr = 0.0;
  BaseFloat smallest_split_change = 1.0e+20;
  std::vector<DecisionTreeSplitter*> builders;
  {  // set up "builders" [one for each current leaf].  This array is never extended.
    // the structures generated during splitting remain as trees at each array location.
    std::vector<BuildTreeStatsType> split_stats;
    SplitStatsByMap(stats, input_map, &split_stats);
    KALDI_ASSERT(split_stats.size() != 0);
    builders.resize(split_stats.size());  // size == #leaves.
    for (size_t i = 0;i < split_stats.size();i++) {
      EventAnswerType leaf = static_cast<EventAnswerType>(i);
      if (split_stats[i].size() == 0) num_empty_leaves++;
      builders[i] = new DecisionTreeSplitter(leaf, split_stats[i], q_opts);
    }
  }

  {  // Do the splitting.
    int32 count = 0;
    std::priority_queue<std::pair<BaseFloat, size_t> > queue;  // use size_t because logically these
    // are just indexes into the array, not leaf-ids (after splitting they are no longer leaf id's).
    // Initialize queue.
    for (size_t i = 0; i < builders.size(); i++)
      queue.push(std::make_pair(builders[i]->BestSplit(), i));
    // Note-- queue's size never changes from now.  All the alternatives leaves to split are
    // inside the "DecisionTreeSplitter*" objects, in a tree structure.
    while (queue.top().first > thresh
          && (max_leaves<=0 || *num_leaves < max_leaves)) {
      smallest_split_change = std::min(smallest_split_change, queue.top().first);
      size_t i = queue.top().second;
      like_impr += queue.top().first;
      builders[i]->DoSplit(num_leaves);
      queue.pop();
      queue.push(std::make_pair(builders[i]->BestSplit(), i));
      count++;
    }
    KALDI_LOG << "DoDecisionTreeSplit: split "<< count << " times, #leaves now " << (*num_leaves);
  }

  if (smallest_split_change_out)
    *smallest_split_change_out = smallest_split_change;

  EventMap *answer = NULL;

  {  // Create the output EventMap.
    std::vector<EventMap*> sub_trees(builders.size());
    for (size_t i = 0; i < sub_trees.size();i++) sub_trees[i] = builders[i]->GetMap();
    answer = input_map.Copy(sub_trees);
    for (size_t i = 0; i < sub_trees.size();i++) delete sub_trees[i];
  }
  // Free up memory.
  for (size_t i = 0;i < builders.size();i++) delete builders[i];

  if (obj_impr_out != NULL) *obj_impr_out = like_impr;
  return answer;
}

TrivialTree()

EventMap* kaldi::TrivialTree ( int32 *  num_leaves )

inline

Returns a tree with just one node.

Used @ start of tree-building process. Not really used in current recipes.

Definition at line 152 of file build-tree-utils.h.

Referenced by kaldi::TestClusterEventMap(), kaldi::TestClusterEventMapGetMappingAndRenumberEventMap(), kaldi::TestClusterEventMapGetMappingAndRenumberEventMap2(), kaldi::TestClusterEventMapRestricted(), kaldi::TestDoTableSplit(), kaldi::TestShareEventMapLeaves(), kaldi::TestSplitDecisionTree(), and kaldi::TestTrivialTree().

                                                {
  KALDI_ASSERT(*num_leaves == 0);  // in envisaged usage.
  return new ConstantEventMap( (*num_leaves)++ );
}