内部决策树
这页将描述音素决策树代码的内部机制，这个是用通用的数据结构和算法来实现的。从更高层的解释整个算法是如何实现的和怎么在kaldi使用的，可以看How decision trees are used in Kaldi。
Event maps
决策树建立代码的核心概念就是the event map,用类EventMap来描述。不要被event这个词误认为这是发生在特定事件的。event仅仅代表一个(key,value)对的一个集合，没有key是重复的。从概念上讲，它是可以被类型std::map<int32,int32>来描述。事实上，为了更加有效的使用，我们把它表示为a sorted vector of pairs，通过typedef：
Typedef std::vector<std::pair<EventKeyType,EventValueType> > EventType;
这里，EventKeyType和EventValueType仅仅定义为int32，但是如果我们可以从他们的名字里区分，这个代码是非常容易理解的。想象一下一个Event（类型EventType）当做一个向量的集合，而且变量的名字和值都为整数。也有一个类型EventAnswerType，和它们也是int32，它是由EventMap返回的类型；事实上它是一个pdf标识符（声学状态索引）。获取EventType的函数期望你可以首先对它进行排序（比如：通过调用std::sort(e.begin(),e.end())）。
EventMap类的用意可以通过一个例子很好的阐述。假设我们的上下文音素是a/b/c；假设我们有一个标准的三音素拓扑结构；和假设在这个上下文中我们想问音素"b"的中心状态的pdf对应的索引是多少。这个问题里这个状态将是状态1，因为我们使用从0开始的索引。当我们说到"state"，我们将跳过一些细节；更多的细节你可以看Pdf-classes。假设音素a，b和c的整数索引分别为10，11和12。"event"对应的映射为：
(0 -> 10), (1 -> 11), (2 -> 12), (-1 -> 1)
在三音素窗"a/b/c"的0，1和2是位置，和-1是一个特殊的索引，我们用这个来编码state-id(请参照：常量kPdfClass = -1)的一个特殊的索引。用这种方式的话，我们的一个排好序的向量对是：
// caution: not valid C++.
EventType e = { {-1,1}, {0,10}, {1,11}, {2,12} };
假设相对应的声学状态的索引(pdf-id)是1000。然后如果我们有一个表示tree的EventMap"emap"，然后我们期望接下来的设置不会失效：
EventAnswerTypeans;
boolret = emap.Map(e, &ans); // emap is of type EventMap; e is EventType
KALDI_ASSERT(ret == true && ans == 1000);
因此当我们指出EventMap是从EventType映射到EventAnswerType，你可以认为这大概是一个从上下文音素到整数索引的一个映射。音素上下文是由(key-value)对的集合表示，和原则上我们可以添加新的keys和投入更多的信息。注意函数EventMap::Map()返回bool。这是因为它可能对于某些events来说，不映射到其他任何集(比如：考虑一个无效的音素，或者想象一下，当EventType不包含所有的EventMap查询的keys )。
EventMap是一个很被动的对象。它没有任何学习决策树的能力，它仅仅就是存储决策树。可以把它看成表示一个从EventType到EventAnswerType的函数的一个结构。EventMap是一个多态，纯虚类(比如： 它不能被实例化，因为它具有不实施虚拟功能)。实现EventMap接口需要三个具体的类：
- ConstantEventMap: 认为它是一个决策树叶子结点。这个类存储类型EventAnswerType 的一个整数和它的映射函数常常返回这个值。
- SplitEventMap: 认为它是一个决策树的非叶子结点，它查询一个特定的key，和根据问题的答案去"yes"或者"no"孩子结点。它的映射函数调用合适的孩子结点的映射函数。它存储对应"yes"孩子结点的类型kAnswerType的整数集(其他任何事情将对应到"no")。
- TableEventMap: 这个在一个特定的key上做一个完整的分裂。一个典型的例子就是：你也许首先完全分裂中心音素，然后你对这个音素的每一值有一个分离的决策树。内部地它存储EventMap*指针的一个向量。它查找对应分裂的key的值，和调用向量对应位置的EventMap的映射函数。
除了从EventType映射到EventAnswerType，EventMap的确不能够做很多其他事情。它的接口不能提供允许你遍历树的函数，无论是向上还是向下。这里仅仅有一个函数允许你修改EventMap,和这个函数就是EventMap::Copy()函数，这样的声明(作为一个类成员)：
virtualEventMap *Copy(const std::vector<EventMap*> &new_leaves) const;
这个与函数组合有一样的功能。如果你用一个空的向量"new_leaves"调用Copy()，它将仅仅返回整个对象的一个深度拷贝，拷贝它沿着树往下的所有的指针。然而，如果new_leaves不为空，每次函数Copy()到达一个叶子，如果这个叶子1是在(0, new_leaves.size()-1)范围内的和new_leaves[l]不为空， 函数Copy()将返回调用new_leaves[l]->Copy()的结果，而不是Copy()函数的叶子本身(将返回一个新的ConstantEventMap)。一个典型的例子就是当你决定对一个特定的叶子来分裂，比如叶子852。你将创建一个vector
Statistics for building the tree
用来建立音素决策树的统计量如下：
typedefstd::vector<std::pair<EventType, Clusterable*> > BuildTreeStatsType;
这种类型的一个对象的参考被传递到所有决策树建立过程中。这些统计量被期望包含相同的EventType成员的no duplicates，比如它们从概念上表示一个从EventType到Clusterable的映射。 在我们目前的代码中Clusterable对象是一个真正的类型GaussClusterable，但是树建立代码不知道这个，积累这些统计量的程序是acc-tree-stats.cc。
Classes and functions involved in tree-building
Questions (config class)
类Questions是一个与树建立代码相交互的类，行为有点像类"configuration"。它是一个从"key" 值(类型EventKeyType)到一个类型QuestionsForKey的configuration类的真正映射。
QuestionsForKey类有一个"questions"集，每一个是类型EventValueType的整数集他们大对数对应于音素集，或者如果key是-1，他们就是对应HMM状态索引集的一个典型例子，比如{0,1,2}的子集。QuestionsForKey 包含一个类型RefineClustersOptions的一个configuration 类。它在树建立代码中控制树建立的行为将试图在分裂的两边迭代的移动这些值(e.g. phones)来最大化似然比(as in K-means with K=2)。然而，这些可以通过设定"refining clusters"的迭代数目为0来关闭，相当于仅仅从一个固定列表的问题集中选择。这看起来效果要好点。
Lowest-level functions
一个完整的列表，可以看Low-level functions for manipulating statistics and event-maps；我们这里将总结一些重要的。
这些函数大多是涉及到类型BuildTreeStatsType的一些操作，作为我们下面看到的一个(EventType,Clusterable*)对的一个向量。最简单的一个是DeleteBuildTreeStats()，WriteBuildTreeStats()和ReadBuildTreeStats()。
函数PossibleValues()寻找在一个统计量集中一个特定的key对应的值(和通知用户这个值是否经常被定义)；SplitStatsByKey()将通过一个特定的key对应的值来分裂类型BuildTreeStatsType的一个对象为一个向量
SumStats()在一个BuildTreeStatsType对象里求统计量(i.e对象Clusterable)的和返回对应的Clusterable*对象。SumStatsVec()采用一个类型vector
给定一些统计量和EventMap，ObjfGivenMap()评估这个目标函数：它在每一个聚类中对所有的统计量求和(相对应EventMap::Map()函数的每一个不同的答案)，通过这些聚类来添加目标函数，和返回整个。
FindAllKeys() 将找到所有定义在统计量集合里的值，和根据不同的参数，它可以找到被定义为所有的event的所有keys，或者为其他一些event定义的所有的keys(比如采用定义的keys的交集或者并集)。
Intermediate-level functions
涉及到树建立的下一组函数被列在here 和对应树建立的不同阶段。我们现在将提一些有代表的。
首先，我们指出许多这些函数有一个参数int32 *num_leaves。这个指向的整数作为一个计数器来分配新的叶子。在树建立的开始阶段，这个caller被设定为0。每次一个新节点被需要时，树建立的代码采用当前的数字来指向作为新的leaf-id，和然后增加它。
一个重要的函数是GetStubMap()。这个函数返回一个没有分裂的树，比如pdfs 不根据上下文。这个函数的输入控制所有的音素要不是不同的要不他们的一些是共享决策树的根节点，和或者在一个特定的音素里所有的状态共享相同的决策树结点。
SplitDecisionTree()函数采用输入一个EventMap，对应有GetStubMap()创建的类型的一个分裂的"stub"决策树，和做决策树分裂，知道无论是叶子的最大数目达到了，还是分裂一个叶子的增益比特定的门限小。
函数ClusterEventMap()采用一个EventMap和一个门限，和只要这样做的成本小于阈值，合并EventMap的叶子。在SplitDecisionTree()后，这个函数正常的被调用。这里有一些操作限制的函数的不同版本 (e.g.从不同的音素里去避免合并叶子)。
Top-level tree-building functions
高层次树建立的函数被列在here。这些函数可以从命令行里直接调用。最重要的一个就是BuildTree()。它被赋予了一个Questionsconfiguration类，和音素集的一些信息，这些音素他们的根节点是共享的和(对于音素的每一个集合)无论是在单决策树的根节点共享还是对每一个pdf-class有一个分离的根节点。它去掉关于音素的长度的信息，加上不同的门限。它建立树和返回一个用来构建ContextDependency对象EventMap对象。
在这组里有一个重要的事是AutomaticallyObtainQuestions()，它用来获得通过自动对音素聚类的问题。它把音素聚类成树，和对树的每一个节点，从这个节点的所有叶子组成一个问题(问题等价于音素集)。这个(从cluster-phones.cc调用)使我们的脚本独立于人产生的音素集。
给定特征和transition-ids的一个序列的对齐，函数AccumulateTreeStats()为训练树来积累统计量(看Integer identifiers used by TransitionModel)。这个函数被定义在一个与树建立相关函数的不同的目录(hmm/ not tree/) ，它依赖于更多的代码(e.g.it knows about the theTransitionModel class),和我们更愿意保持对核心的树建立代码的依赖性更小。