状态绑定之决策树似然公式

对于一般决策树而言，每一次的最优划分，是要找到一个标准，使得在这种标准之下进行的划分获取的信息增益最大，这里的信息增益一般表示划分之后信息熵的增量。在ASR中，决策树的划分标准是获取最大似然提升，在GMM模型中，对于一个状态集合$S$，其似然表示为：

$$\begin{aligned} L(S) & = \sum_t\sum_{s \in S}\log \mathcal{N}(o_t;\mu(S), \Sigma(S))\gamma_s^t \\ & = \sum_t\left[\log \mathcal{N}(o_t;\mu(S), \Sigma(S))\sum_{s \in S}\gamma_s^t\right] \end{aligned}$$

其中

$$\begin{aligned} \log \mathcal{N}(o_t;\mu(S), \Sigma(S)) & = \log \frac{1}{(2\pi)^{D/2}|\Sigma|^{1/2}}\exp\left(\frac{-(o_t - \mu(S))\Sigma^{-1}(o_t - \mu(S))^T}{2}\right) \\ & = -\frac{1}{2}\left[D\log 2\pi + \log|\Sigma| + (o_t - \mu(S))\Sigma^{-1}(o_t - \mu(S))^T \right] \end{aligned}$$

方差的定义为

$$\begin{aligned} \Sigma &= \frac{\sum_t \left\{(\sum_{s \in S}\gamma_s^t) (o_t - \mu(S))(o_t - \mu(S))^T )\right\} }{\sum_t \sum_{s \in S} \gamma_s^t} \\ & = \frac{\sum_t \left\{\gamma^t(o_t - \mu(S))(o_t - \mu(S))^T )\right\} }{\sum_t \gamma^t} \end{aligned}$$

对于$\gamma_s^t$，有如下两种理解：

1. 时刻t的state occupancy，由于一个时刻只能由一个状态生成，所以值为${0, 1}$
2. 时刻t的观测由状态s生成的概率

为了计算出$L(S)$，需要得到$\Sigma^{-1}$，由上式：

$$\begin{aligned} \sum_t \gamma^t \cdot I & = \sum_t \left\{\gamma^t(o_t - \mu(S))(o_t - \mu(S))^T )\right\} \Sigma^{-1} \\ & = \sum_t \left(\gamma^t(o_t - \mu(S))\left[(o_t - \mu(S))^T \Sigma^{-1}\right]\right) \\ & = \sum_t \gamma^t A_t^{D \times 1}B_t^{1 \times D} \end{aligned}$$

其中$A_t^{D \times 1} = o_t - \mu(S), B_t^{1 \times D} = (o_t - \mu(S))^T \Sigma^{-1}$

由$B_t^{1 \times D}A_t^{D \times 1} = \text{tri}(A_t^{D \times 1}B_t^{1 \times D})$：

$$\begin{aligned} \sum_t\left(\gamma^tB_t^{1 \times D}A_t^{D \times 1}\right) & = \text{tr}\left\{\sum_t \gamma^t A_t^{D \times 1}B_t^{1 \times D}\right\} \\ & = \text{tr}\sum_t \gamma^t \cdot I = D\sum_t \gamma^t \\ & = \sum_t (o_t - \mu(S))^T \Sigma^{-1}(o_t - \mu(S))\gamma^t \end{aligned}$$

带回$L(S)$：

$$\begin{aligned} L(S) & = \sum_t\left[\log \mathcal{N}(o_t;\mu(S), \Sigma(S))\sum_{s \in S}\gamma_s^t\right] \\ & = \sum_t\left\{-\frac{1}{2}\left[D\log 2\pi + \log|\Sigma| + (o_t - \mu(S))\Sigma^{-1}(o_t - \mu(S))^T \right]\gamma^t\right\} \\ & = -\frac{1}{2}\left(D\log 2\pi + \log|\Sigma|\right) \sum_t \gamma^t - \frac{1}{2}D \sum_t \gamma^t\\ & = -\frac{1}{2}\left(D\log 2\pi + \log|\Sigma| + D \right)\sum_t \sum_{s \in S} \gamma_s^t \end{aligned}$$

得证