Collaboration diagram for DecisionTreeSplitter:

Public Member Functions
EventMap *	GetMap ()

BaseFloat	BestSplit ()

void	DoSplit (int32 *next_leaf)

	DecisionTreeSplitter (EventAnswerType leaf, const BuildTreeStatsType &stats, const Questions &q_opts)

	~DecisionTreeSplitter ()

Private Member Functions
void	DoSplitInternal (int32 *next_leaf)

void	FindBestSplit ()

Private Attributes
const Questions &	q_opts_

BaseFloat	best_split_impr_

DecisionTreeSplitter *	yes_

DecisionTreeSplitter *	no_

EventAnswerType	leaf_

BuildTreeStatsType	stats_

EventKeyType	key_

std::vector< EventValueType >	yes_set_

Detailed Description

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

Constructor & Destructor Documentation

◆ DecisionTreeSplitter()

DecisionTreeSplitter	(	EventAnswerType	leaf,
		const BuildTreeStatsType &	stats,
		const Questions &	q_opts
	)

inline

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

References DecisionTreeSplitter::FindBestSplit().

Referenced by DecisionTreeSplitter::DoSplitInternal(), and kaldi::SplitDecisionTree().

                                               : q_opts_(q_opts), yes_(NULL), no_(NULL), leaf_(leaf), stats_(stats) {
     // not, this must work when stats is empty too. [just gives zero improvement, non-splittable].
     FindBestSplit();
   }

◆ ~DecisionTreeSplitter()

~DecisionTreeSplitter ( )

inline

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

References DecisionTreeSplitter::no_, and DecisionTreeSplitter::yes_.

                           {
     delete yes_;
     delete no_;
   }

Member Function Documentation

◆ BestSplit()

BaseFloat BestSplit ( )

inline

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

References DecisionTreeSplitter::best_split_impr_.

Referenced by DecisionTreeSplitter::DoSplit(), DecisionTreeSplitter::DoSplitInternal(), and kaldi::SplitDecisionTree().

438 { return best_split_impr_; } // returns objf improvement (>=0) of best possible split.

kaldi::DecisionTreeSplitter::best_split_impr_

BaseFloat best_split_impr_

Definition: build-tree-utils.cc:516

◆ DoSplit()

void DoSplit ( int32 * next_leaf )

inline

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

References DecisionTreeSplitter::best_split_impr_, DecisionTreeSplitter::BestSplit(), DecisionTreeSplitter::DoSplitInternal(), DecisionTreeSplitter::no_, and DecisionTreeSplitter::yes_.

                                  {
     if (!yes_) {  // not already split; we are a leaf, so split.
       DoSplitInternal(next_leaf);
     } else {  // find which of our children is best to split, and split that.
       (yes_->BestSplit() >= no_->BestSplit() ? yes_ : no_)->DoSplit(next_leaf);
       best_split_impr_ = std::max(yes_->BestSplit(), no_->BestSplit());  // may have changed.
     }
   }

◆ DoSplitInternal()

void DoSplitInternal ( int32 * next_leaf )

inlineprivate

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

References kaldi::ApproxEqual(), DecisionTreeSplitter::best_split_impr_, DecisionTreeSplitter::BestSplit(), DecisionTreeSplitter::DecisionTreeSplitter(), Clusterable::Distance(), KALDI_ASSERT, KALDI_ERR, KALDI_WARN, DecisionTreeSplitter::key_, DecisionTreeSplitter::leaf_, EventMap::Lookup(), DecisionTreeSplitter::no_, DecisionTreeSplitter::q_opts_, DecisionTreeSplitter::stats_, kaldi::SumStats(), DecisionTreeSplitter::yes_, and DecisionTreeSplitter::yes_set_.

Referenced by DecisionTreeSplitter::DoSplit().

                                          {
     // Does the split; applicable only to leaf nodes.
     KALDI_ASSERT(!yes_);  // make sure children not already set up.
     KALDI_ASSERT(best_split_impr_ > 0);
     EventAnswerType yes_leaf = leaf_, no_leaf = (*next_leaf)++;
     leaf_ = -1;  // we now have no leaf.
     // Now split the stats.
     BuildTreeStatsType yes_stats, no_stats;
     yes_stats.reserve(stats_.size()); no_stats.reserve(stats_.size());  //  probably better than multiple resizings.
     for (BuildTreeStatsType::const_iterator iter = stats_.begin(); iter != stats_.end(); ++iter) {
       const EventType &vec = iter->first;
       EventValueType val;
       if (!EventMap::Lookup(vec, key_, &val)) KALDI_ERR << "DoSplitInternal: key has no value.";
       if (std::binary_search(yes_set_.begin(), yes_set_.end(), val)) yes_stats.push_back(*iter);
       else no_stats.push_back(*iter);
     }
 #ifdef KALDI_PARANOID
     {  // Check objf improvement.
       Clusterable *yes_clust = SumStats(yes_stats), *no_clust = SumStats(no_stats);
       BaseFloat impr_check = yes_clust->Distance(*no_clust);
       // this is a negated objf improvement from merging (== objf improvement from splitting).
       if (!ApproxEqual(impr_check, best_split_impr_, 0.01)) {
         KALDI_WARN << "DoSplitInternal: possible problem: "<< impr_check << " != " << best_split_impr_;
       }
       delete yes_clust; delete no_clust;
     }
 #endif
     yes_ = new DecisionTreeSplitter(yes_leaf, yes_stats, q_opts_);
     no_ = new DecisionTreeSplitter(no_leaf, no_stats, q_opts_);
     best_split_impr_ = std::max(yes_->BestSplit(), no_->BestSplit());
     stats_.clear();  // note: pointers in stats_ were not owned here.
   }

◆ FindBestSplit()

void FindBestSplit ( )

inlineprivate

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

References DecisionTreeSplitter::best_split_impr_, kaldi::FindBestSplitForKey(), Questions::GetKeysWithQuestions(), Questions::HasQuestionsForKey(), rnnlm::i, KALDI_WARN, DecisionTreeSplitter::key_, DecisionTreeSplitter::q_opts_, DecisionTreeSplitter::stats_, and DecisionTreeSplitter::yes_set_.

Referenced by DecisionTreeSplitter::DecisionTreeSplitter().

                        {
     // This sets best_split_impr_, key_ and yes_set_.
     // May just pick best question, or may iterate a bit (depends on
     // q_opts; see FindBestSplitForKey for details)
     std::vector<EventKeyType> all_keys;
     q_opts_.GetKeysWithQuestions(&all_keys);
     if (all_keys.size() == 0) {
       KALDI_WARN << "DecisionTreeSplitter::FindBestSplit(), no keys available to split on (maybe no key covered all of your events, or there was a problem with your questions configuration?)";
     }
     best_split_impr_ = 0;
     for (size_t i = 0; i < all_keys.size(); i++) {
       if (q_opts_.HasQuestionsForKey(all_keys[i])) {
         std::vector<EventValueType> temp_yes_set;
         BaseFloat split_improvement = FindBestSplitForKey(stats_, q_opts_, all_keys[i], &temp_yes_set);
         if (split_improvement > best_split_impr_) {
           best_split_impr_ = split_improvement;
           yes_set_ = temp_yes_set;
           key_ = all_keys[i];
         }
       }
     }
   }

◆ GetMap()

EventMap* GetMap ( )

inline

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

References DecisionTreeSplitter::GetMap(), DecisionTreeSplitter::key_, DecisionTreeSplitter::leaf_, DecisionTreeSplitter::no_, DecisionTreeSplitter::yes_, and DecisionTreeSplitter::yes_set_.

Referenced by DecisionTreeSplitter::GetMap(), and kaldi::SplitDecisionTree().

                      {
     if (!yes_) {  // leaf.
       return new ConstantEventMap(leaf_);
     } else {
       return new SplitEventMap(key_, yes_set_, yes_->GetMap(), no_->GetMap());
     }
   }