Kaldi 决策树状态绑定学习笔记（二）如何自动生成问题集？_

Kaldi决策树中使用的问题集并不是手工设计的，而是通过之前得到的统计量自动生成的。那么在Kaldi中是如何自动生成问题的？这就是本次笔记的主要内容。

在这个笔记中，我会首先介绍自动生成问题集所用到的主程序cluster-phones和主函数AutomaticallyObtainQuestions()，然后会穿插着介绍主函数用到的核心函数和完成具体工作的一些C++对象。最后再讲解程序compile-question。

建议学习Kaldi官方文档《Decision tree internals》的Classes and functions involved in tree-building部分，《How decision trees are used in Kaldi》的The tree building process部分。

若对似然这些名词和对应的公式感觉陌生，请参考论文《Tree-Based State Tying For High Accuracy Acoustic Modelling》S.J.Young的第三部分Tree-BasedClustering。

cluster-phones

Ø作用：Cluster phones (or sets of phones) into sets for various purpose.对多个音素或多个音素集进行聚类。

Ø输入：决策树相关统计量treeacc，多个音素集sets.int

Ø输出：自动生成的问题集（每个问题由多个音素组成）

Ø示例：

cluster-phones $context_opts $dir/treeacc $lang/phones/sets.int \

$dir/questions.int

Ø过程：

1.从treeacc中读取统计量到BuildTreeStatsType stats；读取vector pdf_class_list，该变量指定所考虑的HMM状态，默认为1，也就是只考虑三状态HMM的中间状态；从sets.int读取vector > phone_sets；默认的三音素参数N=3，P=1。

2.若指定的mode为questions，调用AutomaticallyObtainQuestions()自动生成问题集vector > phone_sets_out；若指定的model为k-means，调用KMeansClusterPhones()。此笔记只涉及questions模式。

3.将上述函数自动生成的phone_sets_out写到questions.int。

Ø文件说明：

下面以我们实验室所用的sets.int和sets.txt为例，来对sets.int文件有一个直观的感受：（左边是sets.txt，右边是sets.int，两图第一列均为行号）

AutomaticallyObtainQuestions()

Ø主要功能：AutomaticallyObtainQuestions()通过对音素自动进行聚类，从而获取问题集；它把音素聚类成一棵树，并且对树中的每一个结点，把从该结点可以到达的所有叶子结点合在一起构成一个问题（该树的一个叶子结点保存着一些音素，一个问题就是一个音素的集合）。（官方文档《Decision tree internals》的Classes and functions involved in tree-building中的Top-level tree-building functions部分如是说）。初看到这段描述可能并不是很清楚到底怎么一回事，在看明白代码之后就会明白这句话讲了什么。

Ø分块解析：

（在下面我会把不重要的代码删掉，比如错误检测代码，只留下主要部分）

1.读取sets.int中的所有音素，保存在phones中。phone_sets_in由sets.int得到。

1.调用FilterStatsByKey()把stats中只属于三音素第二个HMM状态的统计量留下。通过累积统计量部分我们知道，三音素的三个HMM状态可能都会有对应的统计量，但是这里只把与第二个HMM状态相关的统计量留下进行聚类，其他的都暂时扔掉不用。为什么是第二个？这是由向量all_pdf_class指定的，all_pdf_class就是程序cluster-phones中的参数pdf_class_list，该向量指定所考虑的HMM状态，默认为1，也就是只考虑三状态HMM的中间状态。至于为什么是第二个，暂时我也不是很清楚。kPdfClass=-1，指明过滤统计量的Key，也就是根据EventType的HMM状态进行过滤，只留下all_pdf_classes指定的HMM状态对应的stats。

2.调用SplitStatsByKey(),根据三音素的中间音素对retained_stats进行划分，把属于每个音素的统计量放在一个BuildTreeStatsType中。由参数P指定根据三音素的第几个音素进行划分，因为此处P是1，所以是三音素的中间音素。举个例子，我们实验室的所用的音素一共有215个，假设每个音素都出现在三音素的中间位置，对retained_stats进行划分之后，split_stats的元素个数是215，每一个元素保存着(中间音素都是x的所有三音素对应的所有统计量)。

3.调用SumStatsVec()把split_stats每个元素中的所有统计量加起来，得到每个中间音素的统计量，也就是summed_stats，其维数为音素个数。

从上一步我们知道，split_stats的每一个元素保存着中间音素都是x的所有三音素对应的所有统计量，因为音素x左右音素的不同，所以split_stats这个元素中保存的统计量有很多，现在把中间音素都是x的所有三音素对应的所有统计量累加起来（就是把这些GaussClusterable的count_相加、stats_相加）；对split_stats的每个元素都执行这样的操作后，就得到了summed_stats。

举个例子，我们实验室的所用的音素一共有215个，最终的summed_stats就只有215个元素，每个元素保存着某音素作为三音素中间音素、其HMM状态为第二个状态对应的所有统计量的累积。

4.根据sets.int指定的集合，累加同一个集合中音素的统计量。从上面sets.int文件的图片可以看出，该文件的一行就是一个音素的集合，这块代码的作用就是把属于sets.int文件同一行的音素的统计量累加在一起，所以最后summed_stats的维数就是sets.int的行数，一行对应一个统计量。

5.调用TreeCluster()，对summed_stats_per_set进行聚类，生成相关信息。TreeCluster()是AutomaticallyObtainQuestions()最核心的部分，该函数的具体解释独立出来放在后面，建议先阅读此部分的详细解释。

6.调用ObtainSetsOfPhones()，由上一步得到的信息，生成问题集。先解释下该函数的几个参数：

-phone_sets：由sets.int生成，每个元素代表sets.int中一行上的音素集

-assignments：phone_sets中每个元素所属的cluster。上一步生成了树，每个phone_sets的元素（一个点）都属于该树的一个叶子结点（或者称为一个cluster）

-clust_assignments：上一步生成的树的每个结点的父结点

-num_leaves：上一步生成的树的叶子个数

-question_out：生成的问题集

函数内容：

a)得到每个cluster（叶子结点）中的音素集；

b)将子结点的音素集加入到其父结点的音素集中（实现了“把从该结点可以到达的所有叶子结点合在一起构成一个问题”）；

c)把原始的phone_set插入到问题集；

d)过滤问题集的重复项、空项，生成最终的问题集。

TreeCluster()

BaseFloat TreeCluster(const std::vector &points,

int32 max_clust, // this is a max only.

std::vector *clusters_out,

std::vector *assignments_out,

std::vector *clust_assignments_out,

int32 *num_leaves_out,

TreeClusterOptions cfg)

在AutomaticallyObtainQuestions()中被调用时获得的参数：

该函数其实只包含两行代码：

这里很重要的点是面对对象的思想。设计一个对象，完成具体的工作。把函数的实现变简单，把工作的细节都放在对象的实现中。

该函数首先初始化一个TreeClusterer对象，把统计量points传给该对象；然后调用该对象的Cluster方法获取关于聚类结果的相关信息。ObtainSetsOfPhones()根据这些信息就可以生成问题集。下面就分三部分来解释TreeCluster()和TreeClusterer对象：

1-TreeClusterer对象和Node数据结构

TreeClusterer是使用自顶向下的树进行聚类的一个对象。有树的地方就有结点Node，我们先来看下Node数据结构中保存了什么信息。

1.Node保存着指向其双亲结点和孩子结点的指针。注意到children是一个Node指针的vector，vector的大小由TreeClusterOptions中的branch_factor参数指定，这个值默认为2，所以我们这里使用的树是二叉树，每个结点最多只有两个孩子结点。

2.保存着属于该结点的所有统计量之和node_total（统计量就是该结点中的音素对应的所有特征向量的出现次数count_、特征向量之和stats_(0)和特征向量的平方和stats_(1)，统计量用来计算该结点的似然L(s)）。

3.还保存着该结点是否是叶子结点，以及是叶子结点时在leaf_nodes_中的索引和不是叶子结点时在nonleaf_nodes_中的索引。

4.如果是叶子结点，保存着属于该叶子的那些点的统计量points，以及该叶子上拥有的那些点在所有点组成的vector中的索引（也就是在TreeClusterer对象points_成员中的索引）。用best_split保存着对该叶子结点进行最优划分时，获得的最大的似然提升。对该叶子结点划分意味着生成两个新的簇（或者说两个新的孩子结点），assignments中就保存着对该叶子结点进行最优划分后，该叶子结点中的点分别被划分到哪个簇（或者说分别被划分到哪个孩子结点），其元素值一般为0、1。

下面看一下TreeClusterer的数据成员都有哪些。

1.TreeClusterer中构造的树的结点分为两类：叶子结点和非叶子结点。叶子结点放在leaf_nodes_中，非叶子结点放在nonleaf_nodes_中，每个结点Node的数据结构中保存着该Node是否为叶子结点以及在这两个向量中的索引。

2.points_中保存着初始化TreeClusterer对象时传递进来的每个点的统计量，该对象的聚类过程，就是为了把这些点分成一簇簇(cluster)。

3.queue_是一个优先队列，队列中的每个元素是一个对，这个对的第二个数据保存着结点信息，这个对的第一个数据是对该结点进行划分时所获得的似然的最大提升。使用优先队列则说明，对似然提升最大的结点优先进行划分。（至于为什么要根据这种策略做，以及似然这些名词对应的公式，请参考论文《Tree-Based State Tying For High Accuracy Acoustic Modelling》S.J.Young的第三部分Tree-BasedClustering）

2-TreeClusterer对象初始化

这里我们使用下面这个构造函数对TreeClusterer对象进行初始化。首先初始化TreeClusterer对象的一些数据成员，然后调用Init()完成剩余的初始化工作。

Init()生成树的根结点top_node，根结点包含传递给该对象的所有点points_，初始化根top_node的信息，包括is_leaf=true、index=0、parent=NULL、node_total和leaf中的成员，并把该根top_node放进leaf_nodes_中。（末尾带下划线的是TreeClusterer的数据成员，若末尾不带下划线，则一般为Node的数据成员，可以使用这种命名规范进行区分，防止混乱）

每当创建新结点的时候（一般为叶子结点），应该总是调用FindBestSplit(Node*node)函数。该函数的作用是找到对参数node的最优划分，即采取该划分时，获得的似然提升最大；并把最优划分时获得的似然提升记录在该node的leaf.best_split中。若该best_split超过cfg_指定的似然阈值thresh，则把对(best_split, node)放进优先队列queue_中。该函数调用ClusterKMeans()找到对属于该node的点的最优的划分和对应的似然提升，ClusterKMeans()的细节我们在后面再提及，这里可以先略过。

因为top_node是新建的且唯一的叶子结点，所以在Init()的末尾，调用FindBestSplit(top_node)，找到对top_node的最优划分，将属于top_node的点划分成两簇，每一簇对应一个孩子结点，同时将该划分的最大似然提升记录在top_node->leaf.best_split中，并把对pairleaf.best_split, top_node>放进优先队列queue_中（此时queue_只包含这一个对）。

3-TreeClusterer.Cluster()

在完成对TreeCluster对象的初始化工作之后，对传递给该对象的所有点，该成员方法根据统计量构造树，实现对点的聚类，将点分成一簇簇，该树的一个叶子结点代表一个簇，每一簇都包含几个点。

回到AutomaticallyObtainQuestions()对TreeCluster()的调用，这些点就是sets.int中的音素集的集合，一个点就是sets.int中的一行，也就是说一个点就是一个音素集。以我们实验室的sets.int为例，sets.int一共有63行，所以就有63个点。用树对这63个点进行聚类后，树的每个叶子结点都有几个点，其中一个点是一个音素集。

回忆之前官方文档所说的：“AutomaticallyObtainQuestions()把音素聚类成一棵树，并且对树中的每一个结点，把从该结点可以到达的所有叶子结点合在一起构成一个问题”。对于构建好的树，从每个结点都可以访问到一个（该结点就是叶子结点）或多个叶子结点，把这些叶子结点中的点合在一起，也就是把多个音素集合合在一起，形成一个更大的音素的集合，这个更大的音素集合就构成了一个问题。

下面看一下该成员方法的具体代码：

1.构建树。queue_是一个优先队列，每个元素是pair，该pair中，第一个数据是对第二个数据Node进行最优化分所得的最大似然提升。对当前树的每个叶子结点都可以进行划分（注意刚开始时该树只有一个top_node），每个叶子结点都有一个最优划分，也就能得到对该叶子结点进行最优划分后的最大似然提升。queue_的队首就是对当前所有叶子结点划分后似然提升最大的一个叶子结点，调用TreeClusterer.DoSplit(Node *node)对该叶子结点进行划分（所有叶子中似然提升最大的叶子结点，和每个叶子结点的最优划分得到最大似然提升，这两个最大不一样），重复对队首的划分，直到queue_为空。。

DoSplit(Node *node)对node执行具体的划分，生成两个新的孩子结点，把node的index给第一个孩子，并把leaf_nodes_该index对应的Node替换成第一个孩子，为第二个孩子生成新的index并加入leaf_nodes_，根据划分时计算的assignments，把node的点划分到两个子孩子中；把node加入到nonleaf_nodes_；最后对两个孩子结点（两个新的叶子结点）分别调用FindBestSplit()，得到两个孩子结点的最优划分，更新queue_。

2.生成ObtainSetsOfPhones()要用到的信息。由上一步完成了对点的划分，构建好了树。

a)调用CreateAssignmentsOutput(assignments_out)，计算传递给TreeClusterer的每个点分别属于哪个叶子结点。在对树完成划分后，每个叶子结点都包含几个点，把这些点属于的叶子结点编号写到assignments_out中。

b)调用CreateClustAssignmentsOutput(clust_assignments_out)，计算树的每个结点的双亲结点的编号。因为对叶子结点和非叶子结点分开编号，所以为了避免重复，对非叶子结点进行重新编号，接着叶子结点的号进行编号。

c)调用CreateClustersOutput(clusters_out)，因为TreeCluster()不使用这个输出，所以略过。

最好能够自己举一个具体的例子来理解生成输出信息的过程，后面我会附加自己学习笔记的草稿图片来给出一个例子。请参考下面五幅图的第二幅图，我在左下角画了一个划分的例子，并且把生成输出的过程大致也画在这个图上了，希望其能有一些借鉴意义。ObtainSetsOfPhones()就是要用a)、b)生成的信息来得到问题集。