Low-level functions for manipulating statistics and event-maps

See Decision tree internals and specifically Classes and functions involved in tree-building for context. More...

Collaboration diagram for Low-level functions for manipulating statistics and event-maps:

Functions
void	DeleteBuildTreeStats (BuildTreeStatsType *stats)
	This frees the Clusterable* pointers in "stats", where non-NULL, and sets them to NULL. More...
void	WriteBuildTreeStats (std::ostream &os, bool binary, const BuildTreeStatsType &stats)
	Writes BuildTreeStats object. This works even if pointers are NULL. More...
void	ReadBuildTreeStats (std::istream &is, bool binary, const Clusterable &example, BuildTreeStatsType *stats)
	Reads BuildTreeStats object. More...
bool	PossibleValues (EventKeyType key, const BuildTreeStatsType &stats, std::vector< EventValueType > *ans)
	Convenience function e.g. More...
void	SplitStatsByMap (const BuildTreeStatsType &stats_in, const EventMap &e, std::vector< BuildTreeStatsType > *stats_out)
	Splits stats according to the EventMap, indexing them at output by the leaf type. More...
void	SplitStatsByKey (const BuildTreeStatsType &stats_in, EventKeyType key, std::vector< BuildTreeStatsType > *stats_out)
	SplitStatsByKey splits stats up according to the value of a particular key, which must be always defined and nonnegative. More...
bool	ConvertStats (int32 oldN, int32 oldP, int32 newN, int32 newP, BuildTreeStatsType *stats)
	Converts stats from a given context-window (N) and central-position (P) to a different N and P, by possibly reducing context. More...
void	FilterStatsByKey (const BuildTreeStatsType &stats_in, EventKeyType key, std::vector< EventValueType > &values, bool include_if_present, BuildTreeStatsType *stats_out)
	FilterStatsByKey filters the stats according the value of a specified key. More...
Clusterable *	SumStats (const BuildTreeStatsType &stats_in)
	Sums stats, or returns NULL stats_in has no non-NULL stats. More...
BaseFloat	SumNormalizer (const BuildTreeStatsType &stats_in)
	Sums the normalizer [typically, data-count] over the stats. More...
BaseFloat	SumObjf (const BuildTreeStatsType &stats_in)
	Sums the objective function over the stats. More...
void	SumStatsVec (const std::vector< BuildTreeStatsType > &stats_in, std::vector< Clusterable * > *stats_out)
	Sum a vector of stats. More...
BaseFloat	ObjfGivenMap (const BuildTreeStatsType &stats_in, const EventMap &e)
	Cluster the stats given the event map return the total objf given those clusters. More...
void	FindAllKeys (const BuildTreeStatsType &stats, AllKeysType keys_type, std::vector< EventKeyType > *keys)
	FindAllKeys puts in *keys the (sorted, unique) list of all key identities in the stats. More...

Detailed Description

See Decision tree internals and specifically Classes and functions involved in tree-building for context.

Function Documentation

ConvertStats()

bool ConvertStats	(	int32	oldN,
		int32	oldP,
		int32	newN,
		int32	newP,
		BuildTreeStatsType *	stats
	)

Converts stats from a given context-window (N) and central-position (P) to a different N and P, by possibly reducing context.

This function does a job that's quite specific to the "normal" stats format we use. See Phonetic context windows for background. This function may delete some keys and change others, depending on the N and P values. It expects that at input, all keys will either be -1 or lie between 0 and oldN-1. At output, keys will be either -1 or between 0 and newN-1. Returns false if we could not convert the stats (e.g. because newN is larger than oldN).

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

References rnnlm::i, rnnlm::j, KALDI_ASSERT, and KALDI_WARN.

Referenced by kaldi::InitAmGmmFromOld(), and kaldi::TestConvertStats().

                                             {
  bool warned = false;
  KALDI_ASSERT(stats != NULL && oldN > 0 && newN > 0 && oldP >= 0
               && newP >= 0 && newP < newN && oldP < oldN);
  if (newN > oldN) {  // can't add unseen context.
    KALDI_WARN << "Cannot convert stats to larger context: " << newN
               << " > " << oldN;
    return false;
  }
  if (newP > oldP) {
    KALDI_WARN << "Cannot convert stats to have more left-context: " << newP
               << " > " << oldP;
  }
  if (newN-newP-1 > oldN-oldP-1) {
    KALDI_WARN << "Cannot convert stats to have more right-context: " << (newN-newP-1)
               << " > " << (oldN-oldP-1);
  }
  // if shift < 0, this is by how much we "shift down" key
  // values.
  int32 shift = newP - oldP;  // shift <= 0.

  for (size_t i = 0; i < stats->size(); i++) {
    EventType &evec = (*stats)[i].first;
    EventType evec_new;
    for (size_t j = 0; j < evec.size(); j++) {
      EventKeyType key = evec[j].first;
      if (key >= 0 && key < oldN) {  //
        key += shift;
        if (key >= 0 && key < newN) // within new context window...
          evec_new.push_back(std::make_pair(key, evec[j].second));
      } else {
        if (key != -1) {
          // don't understand this key value but assume for now
          // it's something that doesn't interact with the context window.
          if (!warned) {
            KALDI_WARN << "Stats had keys defined that we cannot interpret";
            warned = true;
          }
        }
        evec_new.push_back(evec[j]);
      }
    }
    evec = evec_new;  // Assign the modified EventVector with possibly
    // deleted keys.
  }
  return true;
}

DeleteBuildTreeStats()

void DeleteBuildTreeStats

(

BuildTreeStatsType *

stats

)

This frees the Clusterable* pointers in "stats", where non-NULL, and sets them to NULL.

Does not delete the pointer "stats" itself.

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

References KALDI_ASSERT.

Referenced by kaldi::GenRandContextDependency(), kaldi::GenRandContextDependencyLarge(), main(), kaldi::TestBuildTree(), kaldi::TestClusterEventMap(), kaldi::TestClusterEventMapGetMappingAndRenumberEventMap(), kaldi::TestClusterEventMapGetMappingAndRenumberEventMap2(), kaldi::TestClusterEventMapRestricted(), kaldi::TestGenRandStats(), kaldi::TestShareEventMapLeaves(), and kaldi::TestSplitDecisionTree().

                                                     {
  KALDI_ASSERT(stats != NULL);
  BuildTreeStatsType::iterator iter = stats->begin(), end = stats->end();
  for (; iter!= end; ++iter) if (iter->second != NULL) { delete iter->second; iter->second = NULL; } // set to NULL for extra safety.
}

FilterStatsByKey()

void FilterStatsByKey	(	const BuildTreeStatsType &	stats_in,
		EventKeyType	key,
		std::vector< EventValueType > &	values,
		bool	include_if_present,
		BuildTreeStatsType *	stats_out
	)

FilterStatsByKey filters the stats according the value of a specified key.

If include_if_present == true, it only outputs the stats whose key is in "values"; otherwise it only outputs the stats whose key is not in "values". At input, "values" must be sorted and unique, and all stats in "stats_in" must have "key" defined. At output, pointers to Clusterable* in stats_out are not newly allocated– they are the same as the ones in stats_in.

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

References kaldi::EventTypeToString(), kaldi::IsSortedAndUniq(), KALDI_ASSERT, KALDI_ERR, and EventMap::Lookup().

Referenced by kaldi::AutomaticallyObtainQuestions(), kaldi::BuildTree(), kaldi::BuildTreeTwoLevel(), and kaldi::KMeansClusterPhones().

                                                     {
  KALDI_ASSERT(IsSortedAndUniq(values));
  BuildTreeStatsType::const_iterator iter, end = stats_in.end();
  KALDI_ASSERT(stats_out != NULL);
  stats_out->clear();

  for (iter = stats_in.begin(); iter != end; ++iter) {
    const EventType &evec = iter->first;
    EventValueType val;
    if (! EventMap::Lookup(evec, key, &val)) // no such key. // HERE.
      KALDI_ERR << "SplitStats: key "<< key << " is not present in event vector " << EventTypeToString(evec);
    bool in_values = std::binary_search(values.begin(), values.end(), val);
    if (in_values == include_if_present)
      stats_out->push_back(*iter);
  }
}

FindAllKeys()

void FindAllKeys	(	const BuildTreeStatsType &	stats,
		AllKeysType	keys_type,
		std::vector< EventKeyType > *	keys
	)

FindAllKeys puts in *keys the (sorted, unique) list of all key identities in the stats.

If type == kAllKeysInsistIdentical, it will insist that this set of keys is the same for all the stats (else exception is thrown). if type == kAllKeysIntersection, it will return the smallest common set of keys present in the set of stats if type== kAllKeysUnion (currently probably not so useful since maps will return "undefined" if key is not present), it will return the union of all the keys present in the stats.

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

References kaldi::GetEventKeys(), KALDI_ASSERT, KALDI_ERR, kaldi::kAllKeysInsistIdentical, kaldi::kAllKeysIntersection, and kaldi::kAllKeysUnion.

Referenced by Questions::InitRand(), and kaldi::TestFindAllKeys().

                                                                                                            {
  KALDI_ASSERT(keys_out != NULL);
  BuildTreeStatsType::const_iterator iter = stats.begin(), end = stats.end();
  if (iter == end) return;  // empty set of keys.
  std::vector<EventKeyType> keys;
  GetEventKeys(iter->first, &keys);
  ++iter;
  for (; iter!= end; ++iter) {
    std::vector<EventKeyType> keys2;
    GetEventKeys(iter->first, &keys2);
    if (keys_type == kAllKeysInsistIdentical) {
      if (keys2 != keys)
        KALDI_ERR << "AllKeys: keys in events are not all the same [called with kAllKeysInsistIdentical and all are not identical.";
    } else if (keys_type == kAllKeysIntersection) {
      std::vector<EventKeyType> new_keys(std::max(keys.size(), keys2.size()));
      // following line relies on sorted order of event keys.
      std::vector<EventKeyType>::iterator end_iter =
          std::set_intersection(keys.begin(), keys.end(), keys2.begin(), keys2.end(), new_keys.begin());
      new_keys.erase(end_iter, new_keys.end());
      keys = new_keys;
    } else {  // union.
      KALDI_ASSERT(keys_type == kAllKeysUnion);
      std::vector<EventKeyType> new_keys(keys.size()+keys2.size());
      // following line relies on sorted order of event keys.
      std::vector<EventKeyType>::iterator end_iter =
          std::set_union(keys.begin(), keys.end(), keys2.begin(), keys2.end(), new_keys.begin());
      new_keys.erase(end_iter, new_keys.end());
      keys = new_keys;
    }
  }
  *keys_out = keys;
}

ObjfGivenMap()

BaseFloat ObjfGivenMap	(	const BuildTreeStatsType &	stats_in,
		const EventMap &	e
	)

Cluster the stats given the event map return the total objf given those clusters.

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

References kaldi::DeletePointers(), kaldi::SplitStatsByMap(), kaldi::SumClusterableObjf(), and kaldi::SumStatsVec().

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

                                                                              {
  std::vector<BuildTreeStatsType> split_stats;
  SplitStatsByMap(stats_in, e, &split_stats);
  std::vector<Clusterable*> summed_stats;
  SumStatsVec(split_stats, &summed_stats);
  BaseFloat ans = SumClusterableObjf(summed_stats);
  DeletePointers(&summed_stats);
  return ans;
}

PossibleValues()

bool PossibleValues	(	EventKeyType	key,
		const BuildTreeStatsType &	stats,
		std::vector< EventValueType > *	ans
	)

Convenience function e.g.

to work out possible values of the phones from just the stats. Returns true if key was always defined inside the stats. May be used with and == NULL to find out of key was always defined.

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

References kaldi::CopySetToVector(), and EventMap::Lookup().

Referenced by kaldi::DoTableSplit(), kaldi::FindBestSplitForKey(), Questions::InitRand(), main(), kaldi::TestPossibleValues(), and kaldi::TestShareEventMapLeaves().

                                                    {
  bool all_present = true;
  std::set<EventValueType> values;
  BuildTreeStatsType::const_iterator iter = stats.begin(), end = stats.end();
  for (; iter != end; ++iter) {
    EventValueType val;
    if (EventMap::Lookup(iter->first, key, &val))
      values.insert(val);
    else
      all_present = false;
  }
  if (ans)
    CopySetToVector(values, ans);
  return all_present;
}

ReadBuildTreeStats()

void ReadBuildTreeStats	(	std::istream &	is,
		bool	binary,
		const Clusterable &	example,
		BuildTreeStatsType *	stats
	)

Reads BuildTreeStats object.

The "example" argument must be of the same type as the stats on disk, and is needed for access to the correct "Read" function. It was organized this way for easier extensibility (so adding new Clusterable derived classes isn't painful)

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

References kaldi::ExpectToken(), rnnlm::i, KALDI_ASSERT, kaldi::ReadBasicType(), kaldi::ReadEventType(), and Clusterable::ReadNew().

Referenced by main(), and kaldi::TestBuildTreeStatsIo().

                                                                                                            {
  KALDI_ASSERT(stats != NULL);
  KALDI_ASSERT(stats->empty());
  ExpectToken(is, binary, "BTS");
  uint32 size;
  ReadBasicType(is, binary, &size);
  stats->resize(size);
  for (size_t i = 0; i < size; i++) {
    ReadEventType(is, binary, &((*stats)[i].first));
    bool nonNull;
    ReadBasicType(is, binary, &nonNull);
    if (nonNull) (*stats)[i].second = example.ReadNew(is, binary);
    else (*stats)[i].second = NULL;
  }
}

SplitStatsByKey()

void SplitStatsByKey	(	const BuildTreeStatsType &	stats_in,
		EventKeyType	key,
		std::vector< BuildTreeStatsType > *	stats_out
	)

SplitStatsByKey splits stats up according to the value of a particular key, which must be always defined and nonnegative.

Like MapStats. Pointers to Clusterable* in stats_out are not newly allocated– they are the same as the ones in stats_in. Generally they will still be owned at stats_in (user can decide where to allocate ownership).

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

References kaldi::EventTypeToString(), KALDI_ASSERT, KALDI_ERR, and EventMap::Lookup().

Referenced by kaldi::AutomaticallyObtainQuestions(), kaldi::ClusterEventMapRestrictedHelper(), kaldi::FindBestSplitForKey(), kaldi::GetToLengthMap(), kaldi::KMeansClusterPhones(), and kaldi::TestSplitStatsByKey().

                                                                                                                     {
  BuildTreeStatsType::const_iterator iter, end = stats_in.end();
  KALDI_ASSERT(stats_out != NULL);
  stats_out->clear();
  size_t size = 0;
  // This loop works out size of output vector.
  for (iter = stats_in.begin(); iter != end; ++iter) {
    const EventType &evec = iter->first;
    EventValueType val;
    if (! EventMap::Lookup(evec, key, &val)) // no such key.
      KALDI_ERR << "SplitStats: key "<< key << " is not present in event vector " << EventTypeToString(evec);
    size = std::max(size, (size_t)(val+1));
  }
  stats_out->resize(size);
  // This loop splits up the stats.
  for (iter = stats_in.begin(); iter != end; ++iter) {
    const EventType &evec = iter->first;
    EventValueType val;
    EventMap::Lookup(evec, key, &val);  // will not fail.
    (*stats_out)[val].push_back(*iter);
  }
}

SplitStatsByMap()

void SplitStatsByMap	(	const BuildTreeStatsType &	stats_in,
		const EventMap &	e,
		std::vector< BuildTreeStatsType > *	stats_out
	)

Splits stats according to the EventMap, indexing them at output by the leaf type.

A utility function. NOTE– pointers in stats_out point to the same memory location as those in stats. No copying of Clusterable* objects happens. Will add to stats in stats_out if non-empty at input. This function may increase the size of vector stats_out as necessary to accommodate stats, but will never decrease the size.

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

References kaldi::EventTypeToString(), KALDI_ASSERT, KALDI_ERR, and EventMap::Map().

Referenced by kaldi::ClusterEventMapGetMapping(), kaldi::ClusterEventMapRestrictedByMap(), kaldi::ClusterEventMapToNClustersRestrictedByMap(), kaldi::ComputeTreeMapping(), kaldi::DoTableSplit(), kaldi::GetOccs(), kaldi::InitAmGmm(), kaldi::InitAmGmmFromOld(), main(), kaldi::ObjfGivenMap(), kaldi::SplitDecisionTree(), and kaldi::TestSplitDecisionTree().

                                                                                                                   {
  BuildTreeStatsType::const_iterator iter, end = stats.end();
  KALDI_ASSERT(stats_out != NULL);
  stats_out->clear();
  size_t size = 0;
  for (iter = stats.begin(); iter != end; ++iter) {
    const EventType &evec = iter->first;
    EventAnswerType ans;
    if (!e.Map(evec, &ans)) // this is an error--could not map it.
      KALDI_ERR << "SplitStatsByMap: could not map event vector " << EventTypeToString(evec)
                << "if error seen during tree-building, check that "
                << "--context-width and --central-position match stats, "
                << "and that phones that are context-independent (CI) during "
                << "stats accumulation do not share roots with non-CI phones.";
    size = std::max(size, (size_t)(ans+1));
  }
  stats_out->resize(size);
  for (iter = stats.begin(); iter != end; ++iter) {
    const EventType &evec = iter->first;
    EventAnswerType ans;
    bool b = e.Map(evec, &ans);
    KALDI_ASSERT(b);
    (*stats_out)[ans].push_back(*iter);
  }
}

SumNormalizer()

BaseFloat SumNormalizer

(

const BuildTreeStatsType &

stats_in

)

Sums the normalizer [typically, data-count] over the stats.

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

References Clusterable::Normalizer().

Referenced by kaldi::BuildTree(), kaldi::BuildTreeTwoLevel(), kaldi::GetOccs(), and main().

                                                            {
  BaseFloat ans = 0.0;
  BuildTreeStatsType::const_iterator iter = stats_in.begin(), end = stats_in.end();
  for (; iter != end; ++iter) {
    Clusterable *cl = iter->second;
    if (cl != NULL) ans += cl->Normalizer();
  }
  return ans;
}

SumObjf()

BaseFloat SumObjf

(

const BuildTreeStatsType &

stats_in

)

Sums the objective function over the stats.

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

References Clusterable::Objf().

                                                      {
  BaseFloat ans = 0.0;
  BuildTreeStatsType::const_iterator iter = stats_in.begin(), end = stats_in.end();
  for (; iter != end; ++iter) {
    Clusterable *cl = iter->second;
    if (cl != NULL) ans += cl->Objf();
  }
  return ans;
}

SumStats()

Clusterable * SumStats

(

const BuildTreeStatsType &

stats_in

)

Sums stats, or returns NULL stats_in has no non-NULL stats.

Stats are newly allocated, owned by caller.

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

References Clusterable::Add(), and Clusterable::Copy().

Referenced by DecisionTreeSplitter::DoSplitInternal(), kaldi::InitAmGmmFromOld(), and kaldi::SumStatsVec().

                                                          {
  Clusterable *ans = NULL;
  BuildTreeStatsType::const_iterator iter = stats_in.begin(), end = stats_in.end();
  for (; iter != end; ++iter) {
    Clusterable *cl = iter->second;
    if (cl != NULL) {
      if (!ans)  ans = cl->Copy();
      else ans->Add(*cl);
    }
  }
  return ans;
}

SumStatsVec()

void SumStatsVec	(	const std::vector< BuildTreeStatsType > &	stats_in,
		std::vector< Clusterable * > *	stats_out
	)

Sum a vector of stats.

Leaves NULL as pointer if no stats available. The pointers in stats_out are owned by caller. At output, there may be NULLs in the vector stats_out.

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

References rnnlm::i, KALDI_ASSERT, and kaldi::SumStats().

Referenced by kaldi::AutomaticallyObtainQuestions(), kaldi::ClusterEventMapGetMapping(), kaldi::ClusterEventMapToNClustersRestrictedByMap(), kaldi::FindBestSplitForKey(), kaldi::InitAmGmm(), kaldi::KMeansClusterPhones(), and kaldi::ObjfGivenMap().

                                                                                                    {
  KALDI_ASSERT(stats_out != NULL && stats_out->empty());
  stats_out->resize(stats_in.size(), NULL);
  for (size_t i = 0;i < stats_in.size();i++) (*stats_out)[i] = SumStats(stats_in[i]);
}

WriteBuildTreeStats()

void WriteBuildTreeStats	(	std::ostream &	os,
		bool	binary,
		const BuildTreeStatsType &	stats
	)

Writes BuildTreeStats object. This works even if pointers are NULL.

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

References rnnlm::i, KALDI_ERR, kaldi::WriteBasicType(), kaldi::WriteEventType(), and kaldi::WriteToken().

Referenced by main(), kaldi::TestBuildTree(), kaldi::TestBuildTreeStatsIo(), and kaldi::TestGenRandStats().

                                                                                       {
  WriteToken(os, binary, "BTS");
  uint32 size = stats.size();
  WriteBasicType(os, binary, size);
  for (size_t i = 0; i < size; i++) {
    WriteEventType(os, binary, stats[i].first);
    bool nonNull = (stats[i].second != NULL);
    WriteBasicType(os, binary, nonNull);
    if (nonNull) stats[i].second->Write(os, binary);
  }
  if (os.fail()) {
    KALDI_ERR << "WriteBuildTreeStats: write failed.";
  }
  if (!binary) os << '\n';
}