// doc/tree_internals.dox


// Copyright 2009-2011 Microsoft Corporation

// See ../../COPYING for clarification regarding multiple authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at

//  http://www.apache.org/licenses/LICENSE-2.0

// THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
// WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
// MERCHANTABLITY OR NON-INFRINGEMENT.
// See the Apache 2 License for the specific language governing permissions and
// limitations under the License.

namespace kaldi {
/**
 \page tree_internals Decision tree internals

  This page describes the internals of the phonetic decision-tree clustering
  code, which are implemented as quite generic structures and algorithms.  For a
  higher-level view that explains the overall algorithm being implemented and how it
  is used by the toolkit, see \ref tree_externals.

  \section treei_event_map Event maps

  The central concept in the decision-tree building code is the event map,
  represented by type EventMap.  Don't be misled by the term "event" to think
  that this is something happening at a particular time.  An event is just a set
  of (key,value) pairs, with no key repeated.  Conceptually, it could be represented by 
  the type std::map<int32,int32>.  In fact, for efficiency we represent it as a
  sorted vector of pairs, via the typedef:
\code
  typedef std::vector<std::pair<EventKeyType,EventValueType> > EventType; 
\endcode
  Here, EventKeyType and EventValueType are just typedefs to int32, but the code is
  easier to understand if we use distinct names for them.  Think of an Event
  (type EventType) as being like a collection of variables, except that the
  names and values of the variables are both integers.   There is also the type 
  \ref EventAnswerType, and this is also int32.  It is the type returned by the EventMap;
  in practice it is a pdf identifier (acoustic-state index).
  Functions that require EventType expect you to have sorted it first (e.g. by calling
  std::sort(e.begin(),e.end()); )

  The purpose of the EventMap class is best illustrated via an example.  Suppose our phone-in-context is a/b/c;
  suppose we have the standard 3-state topology; and suppose we want to ask what is the index of the pdf
  for the central state of phone "b" in this context.  The state in question would be
  state 1, since we use zero-based indexing.
  We are skimming over a few details here when we refer to "state"; see \ref pdf_class for more information.
  Suppose the integer indices of phones a, b and c are 10, 11 and 12 respectively.
  The "event" would correspond to the mapping:
 \verbatim
   (0  -> 10), (1  -> 11), (2  -> 12), (-1 -> 1)
 \endverbatim
  where 0, 1 and 2 are the positions in the 3-phone window "a/b/c", and -1 is a special
  index we use to encode the state-id (c.f. the constant \ref kPdfClass = -1).  The way this
  would be represented as a sorted vector of pairs is:
 \code
   // caution: not valid C++.
   EventType e = { {-1,1}, {0,10}, {1,11}, {2,12} }; 
 \endcode
  Suppose we that the acoustic-state index (pdf-id) corresponding to this
  acoustic state happens to be 1000.  Then if we have an
  EventMap "emap" representing the tree, then we would expect the following assert
  not to fail:
 \code
   EventAnswerType ans;
   bool ret = emap.Map(e, &ans); // emap is of type EventMap; e is EventType
   KALDI_ASSERT(ret == true && ans == 1000);
 \endcode
  So when we state that an EventMap is a map from EventType to EventAnswerType, you can think of
  this roughly as a map from a phone-in-context to an integer index.  The phone-in-context
  is represented as a set of (key-value) pairs, and in principle we could add new keys and
  put in more information.  Notice that the EventMap::Map() function returns bool.  This is
  because it's possible for certain events not to map to any answer at all (e.g. consider
  an invalid phone, or imagine what happens when the EventType doesn't contain all the keys
  that the EventMap is querying).

  The EventMap is a very passive object.  It does not have any
  capability to learn decision-trees, it is just a means to store decision-trees.
  Think of it as a structure that represents a function from EventType to EventAnswerType.
  EventMap is a polymorphic, pure-virtual class (i.e. it cannot be instantiated because it
  has virtual functions that are not implemented).  There are three concrete classes
  that implement the EventMap interface:
      - ConstantEventMap:  Think of this as a decision-tree leaf node. 
          This class stores an integer of type EventAnswerType and its Map function always returns that value.  
      - SplitEventMap: Think of this as a decision-tree non-leaf node that queries a certain
         key and goes to the "yes" or "no" child node depending on the answer.  Its Map
         function calls the Map function of the appropriate child node.  It stores a set of
         integers of type kAnswerType that correspond to the "yes" child (everything else goes to "no").
      - TableEventMap: This does a complete split on a particular key.  A typical example is:
         you might first split completely on the central phone and then have a separate 
         decision tree for each value of that phone.  Internally it stores a vector of
         EventMap* pointers.  It looks up the value corresponding to the key that it
         is splitting on, and calls the Map function of the EventMap at the corresponding
         position in the vector.
  
  The EventMap cannot really do very much apart from map EventType to EventAnswerType.  
  Its interface does not provide functions that allow you to traverse the tree, either 
  up or down.  There is just one function that allows you to modify the EventMap, and this
  is the EventMap::Copy() function, declared like this (as a class-member):
 \code
  virtual EventMap *Copy(const std::vector<EventMap*> &new_leaves) const;
 \endcode
 This has an effect similar to function composition.  
 If you call Copy() with an empty vector "new_leaves", it will just return a deep copy
 of the entire object, copying all the pointers as it goes down the tree.  However,
 if new_leaves is nonempty, each time the Copy() function reaches a leaf, if that leaf
 \c l is within the range (0, new_leaves.size()-1) and \c new_leaves[\c l] is non-NULL,
 the Copy() function will return the result of calling \c new_leaves[\c l]->\c Copy(), rather
 than the \c Copy() function of the leaf itself (which would have returned a new ConstantEventMap).
 A typical example is where you decide to split a particular leaf, say leaf 852.
 You could create an object of type vector<EventMap*> whose only non-NULL member is
 as position 852.  It would contain a pointer to an object whose real type is
 SplitEventMap, and the "yes" and "no" pointers would be to type ConstantEventMap with
 leaf values, say, 852 and 1234 (we reuse the old leaf-node id for the new leaf).  The real
 tree-building code is not this inefficient. 
 
  \section treei_stats Statistics for building the tree
 
 The statistics used to build the phonetic decision tree are of the following type:
 \code
  typedef std::vector<std::pair<EventType, Clusterable*> > BuildTreeStatsType;
 \endcode
 A reference to an object of this type is passed to all the decision-tree
 building routines.  These statistics are expected to contain no duplicates with
 the same EventType member, i.e. they conceptually represent a map from \ref EventType
 to Clusterable.  In our current code the Clusterable objects are really of type
 GaussClusterable, but the tree-building code doesn't know this.  A program that
 accumulates these statistics is acc-tree-stats.cc. 
     
  \section treei_func Classes and functions involved in tree-building

  \subsection treei_func_questions Questions (config class)

  The class Questions is a class that in its interaction with the
  tree-building code, behaves a little bit like a "configuration" class.
  It is really a map from the "key" value (of type \ref EventKeyType),
  to a configuration class of type QuestionsForKey.  

  Class QuestionsForKey
  has a set of "questions", each of which is just a set of integers of
  type \ref EventValueType; these mostly correspond to sets of
  phones, or if the key is -1, they would in the typical case correspond to
  sets of HMM-state indices, i.e. subsets of {0,1,2}.  QuestionsForKey also contains
  a configuration class
  of type RefineClustersOptions.  This controls tree-building behaviour in that
  the tree-building code will attempt to iteratively move values (e.g. phones) between
  the two sides of the split in order to maximize likelihood (as in K-means
  with K=2).  However, this can be turned off by setting the number
  of iterations of "refining clusters" to zero, which corresponds to just choosing
  from among a fixed list of questions.  This seems to work a bit better.

  \subsection treei_func_low Lowest-level functions
       
  See \ref tree_group_lower for a complete list; 
  we summarize some important ones here.

  These functions mostly involve manipulations of objects of type BuildTreeStatsType, which as
  we saw above is a vector of pairs of (EventType, Clusterable*).  The simplest ones
  are DeleteBuildTreeStats(), WriteBuildTreeStats() and ReadBuildTreeStats().

  The function PossibleValues() finds out which values a particular key takes within
  a collection of statistics (and informs the user whether or not the key was always
  defined);  SplitStatsByKey() will split up an object of type
  BuildTreeStatsType into a vector<BuildTreeStatsType> according to the value taken by
  a particular key (e.g. splitting on the central phone); SplitStatsByMap() does the
  same but the index is not the value for that key, but the answer returned by an EventMap
  that is provided to the function.  

  SumStats() sums up the statistics (i.e. the Clusterable objects) in an object
  of BuildTreeStatsType and returns corresponding Clusterable* object.
  SumStatsVec() takes an object of
  type vector<BuildTreeStatsType> and outputs something of type vector<Clusterable*>,
  i.e. it's like SumStats() but for a vector; it's useful in processing the output of
  SplitStatsByKey() and SplitStatsByMap().
 
  ObjfGivenMap() evaluates the objective function given some statistics and an EventMap:
  it sums up all the statistics within each cluster (corresponding to each distinct answer
  of the EventMap::Map() function), adds up the objective functions across the clusters,
  and returns the total.

  FindAllKeys() will find all the keys that are defined in a collection of statistics, and
  depending on the arguments it can find all keys that are defined for all the events, or
  all the keys that are defined for any event (i.e. take the intersection or union of sets of
  defined keys).

  \subsection treei_func_intermediate Intermediate-level functions

  The next group of functions involved in tree building are listed \ref
  tree_group_intermediate "here" and correspond to various stages of tree building.
  We will now only mention some representative ones.

  Firstly, we point out that a lot of these functions have a parameter int32
  *num_leaves.  The integer which this points to acts as a counter to allocate new
  leaves.  At the start of tree building the caller would set it to zero.
  Aach time a new leaf is required, the tree-building code takes the number it
  currently points to as the new leaf-id, and then increments it.

  One important function is GetStubMap().  This function returns a tree that has
  not yet been split, i.e. the pdfs do not depend on the context.  The input to this
  function controls whether all the phones are distinct or some of them share 
  decision-tree roots, and whether all the states within a particular phone share
  the same decision-tree root.

  The function SplitDecisionTree() takes as input an EventMap that would normally
  correspond to a non-split "stub" decision tree of the type created by GetStubMap(),
  and does the decision-tree splitting until either the maximum number of leaves
  has been reached, or the gain from splitting a leaf is less than a specified threshold.

  The function ClusterEventMap() takes an EventMap and a threshold, and merges the
  leaves of the EventMap as long as the cost of doing so is less than the threshold.
  This function would normally be called after SplitDecisionTree().
  There are other versions of this function that operate with restrictions (e.g. to
  avoid merging leaves from distinct phones). 

  \subsection treei_func_top Top-level tree-building functions

  The top-level tree-building functions are listed  \ref tree_group_top "here".
  These functions are called directly from the command-line programs.
  The most important one is BuildTree().  It is given a Questions configuration class,
  and some information about sets of phones whose roots to share and (for each 
  set of phones) whether to share the \ref pdf_class "pdf-classes" in a single decision
  tree root or to have a separate root for each pdf-class.  It is also passed information
  about the lengths of the phones, plus various thresholds.  It builds the tree and
  returns the EventMap object which is used to construct the ContextDependency object.
 
 Another important routine in this group is
 AutomaticallyObtainQuestions(),  which used to obtain questions via automatic clustering of
 phones.  It clusters the phones into a tree, and for each node in the tree, all leaves
 accessible from that node form one question (questions are equivalent to sets of phones).
 This (called from cluster-phones.cc) makes our recipes independent of human-generated
 phone sets.

 The function AccumulateTreeStats() accumulates statistics for training the tree, given
 features and an alignment that is a sequence of transition-ids (see \ref transition_model_identifiers).
 This function is defined in a different directory from the other tree-building-related functions 
 (hmm/ not tree/) as it depends on more code (e.g. it knows about the the TransitionModel class), 
 and we preferred to keep the dependencies of the core tree-building code to a minimum.
  
*/

/**
  \defgroup tree_group Modules involved in tree building
  See \page tree_internals for documentation.
*/
}