第4章 朴素贝叶斯法

第4章 朴素贝叶斯法

习题4.1

  用极大似然估计法推出朴素贝叶斯法中的概率估计公式(4.8)及公式 (4.9)。

解答：

解答思路：

1. 极大似然估计的一般步骤（详见习题1.1第3步）
2. 证明公式4.8：根据输出空间\mathcal{Y}的随机变量Y满足独立同分布，列出似然函数，求解概率P(Y=c_k)的值；
3. 证明公式4.9：证明同公式4.8。

解答步骤：

第1步：极大似然估计的一般步骤

参考Wiki：https://en.wikipedia.org/wiki/Maximum_likelihood_estimation

1. 写出随机变量的概率分布函数；
2. 写出似然函数；
3. 对似然函数取对数，得到对数似然函数，并进行化简；
4. 对参数进行求导，并令导数等于0；
5. 求解似然函数方程，得到参数的值。

第2步：证明公式(4.8)

  根据书中第4章的第4.1节朴素贝叶斯法的基本方法：

  设输入空间\mathcal{X} \subseteq R^n为n维向量的集合，输出空间为类标记集合\mathcal{Y}=\{c_1,c_2,\ldots,c_k\}。输入为特征向量x \in \mathcal{X}，输出为类标记y \in \mathcal{Y}。X是定义在输入空间\mathcal{X}上的随机向量，Y是定义在输出空间\mathcal{Y}上的随机变量。P(X,Y)是X和Y的联合概率分布。训练数据集

T={(x_1,y_1),(x_2,y_2),\ldots,(x_N,y_N)}

\begin{aligned} L(p|Y) &= f(Y|p) \
&= C_N^m p^m (1-p)^{N-m}
\end{aligned}

\begin{aligned} \displaystyle \log L(p|Y) &= \log C_N^m p^m (1-p)^{N-m} \
&= \log C_N^m + \log(p^m) + \log\left( (1-p)^{N-m} \right) \
&= \log C_N^m + m\log p + (N-m)\log (1-p)
\end{aligned}

\begin{aligned}
\hat{p} &= \mathop{\arg\max} \limits_{p} L(p|Y) \
&= \mathop{\arg\max} \limits_{p} \left[\log C_N^m + m\log p + (N-m)\log (1-p) \right]
\end{aligned}

\begin{aligned}
\frac{\partial \log L(p)}{\partial p} &= \frac{m}{p} - \frac{N-m}{1-p} \
&= \frac{m(1-p) - p(N-m)}{p(1-p)} \
&= \frac{m-Np}{p(1-p)} = 0
\end{aligned}

  根据书中第4章朴素贝叶斯法的条件独立性假设：

  朴素贝叶斯法对条件概率分布作了条件独立性的假设。由于这是一个较强的假设，朴素贝叶斯法也由此得名。具体地，条件独立性假设是：

\begin{aligned}
P(X=x|Y=c_k) &= P(X^{(1)}=x^{(1)},\ldots,X^{(n)}=x^{(n)}|Y=c_k) \
&= \prod_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k)
\end{aligned} \tag{4.3}

\begin{aligned} L(p|X,Y) &= f(X,Y|p) \
&= C_m^q p^q (1-p)^{m-q}
\end{aligned}

\displaystyle P_\lambda(Y=c_k) = \frac{\displaystyle \sum_{i=1}^N I(y_i=c_k) + \lambda}{N+K \lambda}, \quad k= 1,2,\ldots,K

p(u|D,\alpha) \propto p(D|u)p(u|\alpha) \propto \prod_{k=1}^K u_k^{\alpha_k+m_k-1}

0 \leqslant u_k \leqslant 1, \quad \sum_{k=1}^K u_k = 1

\text{Dir}(u|\alpha) = C(\alpha) \prod_{k-1}^K u_k^{\alpha_k - 1} \
E(u_k) = \frac{\alpha_k}{\displaystyle \sum_{k=1}^K \alpha_k}

\displaystyle P(u)=P(u_1,u_2,\ldots,u_K) = C(\lambda) \prod_{k=1}^K u_k^{\lambda - 1}

P(m|u) = u_1^{m_1} \cdot u_2^{m_2} \cdots u_K^{m_K} = \prod_{k=1}^K u_k^{m_k}

P(u|m) = \frac{P(m|u)P(u)}{P(m)}

P(u|m,\lambda) \propto P(m|u)P(u|\lambda) \propto \prod_{k=1}^K u_k^{\lambda+m_k-1}

E(u_k) = \frac{\alpha_k}{\displaystyle \sum_{k=1}^K \alpha_k}

\begin{aligned}
E(u_k) &= \frac{\alpha_k}{\displaystyle \sum_{k=1}^K \alpha_k} \
&= \frac{\lambda+m_k}{\displaystyle \sum_{k=1}^K (\lambda + m_k)} \
&= \frac{\lambda+m_k}{\displaystyle \sum_{k=1}^K \lambda +\sum_{k=1}^K m_k} \quad(\because \sum_{k=1}^K m_k = N) \
&= \frac{\lambda+m_k}{\displaystyle K \lambda + N } \quad (\because m_k=\sum_{i=1}^N I(y_i=c_k)) \
&= \frac{\displaystyle \sum_{i=1}^N I(y_i=c_k) + \lambda}{N+K \lambda}
\end{aligned}

\displaystyle P_{\lambda}(X^{(j)}=a_{jl} | Y = c_k) = \frac{\displaystyle \sum_{i=1}^N I(x_i^{(j)}=a_{jl},y_i=c_k) + \lambda}{\displaystyle \sum_{i=1}^N I(y_i=c_k) + S_j \lambda}

\displaystyle P(u)=P(u_1,u_2,\ldots,u_{S_j}) = C(\lambda) \prod_{l=1}^{S_j} u_l^{\lambda - 1}

P(m|u) = u_1^{m_1} \cdot u_2^{m_2} \cdots u_{S_j}^{m_{S_j}} = \prod_{l=1}^{S_j} u_l^{m_l}

P(u|m) = \frac{P(m|u)P(u)}{P(m)}

P(u|m,\lambda) \propto P(m|u)P(u|\lambda) \propto \prod_{l=1}^{S_j} u_l^{\lambda+m_l-1}

E(u_k) = \frac{\alpha_l}{\displaystyle \sum_{l=1}^{S_j} \alpha_l}

\begin{aligned}
E(u_l) &= \frac{\alpha_l}{\displaystyle \sum_{l=1}^{S_j} \alpha_l} \
&= \frac{\lambda+m_l}{\displaystyle \sum_{l=1}^{S_j} (\lambda + m_l)} \
&= \frac{\lambda+m_l}{\displaystyle \sum_{l=1}^{S_j} \lambda +\sum_{l=1}^{S_j} m_l} \quad(\because \sum_{l=1}^{S_j} m_l = \sum_{i=1}^N I(y_i=c_k)) \
&= \frac{\lambda+m_l}{\displaystyle S_j \lambda + \sum_{i=1}^N I(y_i=c_k) } \quad (\because m_l=\sum_{i=1}^N I(x_i^{(j)}=a_{jl},y_i=c_k)) \
&= \frac{\displaystyle \sum_{i=1}^N I(x_i^{(j)}=a_{jl},y_i=c_k) + \lambda}{\displaystyle \sum_{i=1}^N I(y_i=c_k) + S_j \lambda}
\end{aligned}