Question

1. 朴素贝叶斯法是基于贝叶斯定理与特征条件独立假设的分类方法。

   对给定的训练集：

   • 首先基于特征条件独立假设学习输入、输出的联合概率分布。
   • 然后基于此模型，对给定的输入 $ MathJax-Element-93 $ ，利用贝叶斯定理求出后验概率最大的输出 $ MathJax-Element-132 $ 。

2. 朴素贝叶斯法不是贝叶斯估计，贝叶斯估计是最大后验估计。

2.1 原理

1. 设输入空间 $ MathJax-Element-46 $ 为 $ MathJax-Element-47 $ 维向量的集合 ，输出空间为类标记集合 $ MathJax-Element-48 $ 。

   令 $ MathJax-Element-49 $ 为定义在 $ MathJax-Element-50 $ 上的随机向量， $ MathJax-Element-132 $ 为定义在 $ MathJax-Element-52 $ 上的随机变量。

   令 $ MathJax-Element-58 $ 为 $ MathJax-Element-54 $ 和 $ MathJax-Element-132 $ 的联合概率分布，假设训练数据集 $ MathJax-Element-80 $ 由 $ MathJax-Element-58 $ 独立同分布产生。

   朴素贝叶斯法通过训练数据集学习联合概率分布 $ MathJax-Element-58 $ 。具体的学习下列概率分布：

   • 先验概率分布： $ MathJax-Element-108 $ 。
   • 条件概率分布： $ MathJax-Element-60 $ 。

2. 朴素贝叶斯法对条件概率做了特征独立性假设： $ MathJax-Element-113 $ 。

   • 这意味着在分类确定的条件下，用于分类的特征是条件独立的。
   • 该假设使得朴素贝叶斯法变得简单，但是可能牺牲一定的分类准确率。

3. 根据贝叶斯定理：

   $ p(y\mid \mathbf {\vec x})=\frac{p( \mathbf {\vec x}\mid y)p(y)}{\sum_{y^\prime} p( \mathbf {\vec x}\mid y^\prime)p(y^\prime)} $

   考虑分类特征的条件独立假设有：

   $ p(y\mid \mathbf {\vec x})=\frac{p(y)\prod_{i=1}^{n}p(x_i\mid y)}{\sum_{y^\prime} p( \mathbf {\vec x}\mid y^\prime)p(y^\prime)} $

   则朴素贝叶斯分类器表示为：

   $ f(\mathbf {\vec x})=\arg \max_{y \in \mathcal Y}\frac{p(y)\prod_{i=1}^{n}p(x_i\mid y)}{\sum_{y^\prime} p( \mathbf {\vec x}\mid y^\prime)p(y^\prime)} $

   由于上式的分母 $ MathJax-Element-62 $ 与 $ MathJax-Element-132 $ 的取值无关，则分类器重写为： $ MathJax-Element-64 $ 。

2.2 期望风险最小化

1. 朴素贝叶斯分类器是后验概率最大化，等价于期望风险最小化。

2. 令损失函数为：

   $ L(y,f(\mathbf{\vec x}))= \begin{cases} 1, & y \ne f(\mathbf{\vec x}) \\ 0, & y=f(\mathbf{\vec x}) \end{cases} \\ R_{exp}(f)=\mathbb E[L(y,f(\mathbf{\vec x}))]=\sum_{\mathbf {\vec x} \in \mathcal X}\sum_{y \in \mathcal Y}L(y,f(\mathbf {\vec x}))p(\mathbf {\vec x}, y) $

3. 根据 $ MathJax-Element-65 $ 有：

   $ R_{exp}(f)=\mathbb E[L(y,f(\mathbf{\vec x}))]=\sum_{\mathbf {\vec x} \in \mathcal X}\sum_{y \in \mathcal Y}L(y,f(\mathbf {\vec x}))p(\mathbf {\vec x}, y) =\mathbb E_X[\sum_{y\in \mathcal Y} L(y,f(\mathbf {\vec x}))p(y\mid \mathbf {\vec x})] $

   为了使得期望风险最小化，只需要对 $ MathJax-Element-66 $ 中的元素极小化。

   令 $ MathJax-Element-67 $ ，则有：

   $ \arg\min_{\hat y} \sum_{y\in \mathcal Y}L(y,\hat y) p(y\mid \mathbf{\vec x})=\arg\min_{\hat y} \sum_{y\in \mathcal Y}p(y\ne \hat y\mid \mathbf{\vec x} )\\ =\arg\min_{\hat y}( 1-p( \hat y\mid \mathbf{\vec x} )) = \arg\max_{\hat y}p( \hat y\mid \mathbf{\vec x} ) $

   即：期望风险最小化，等价于后验概率最大化。

2.3 算法

1. 在朴素贝叶斯法中，学习意味着估计概率： $ MathJax-Element-108 $ ， $ MathJax-Element-95 $ 。

2. 可以用极大似然估计相应概率。

   • 先验概率 $ MathJax-Element-108 $ 的极大似然估计为： $ MathJax-Element-71 $

   • 设第 $ MathJax-Element-99 $ 个特征 $ MathJax-Element-119 $ 可能的取值为 $ MathJax-Element-101 $ ，则条件概率 $ MathJax-Element-75 $ 的极大似然估计为：

     $ p(x_j=a_{j,l}\mid y=c_k)=\frac{\sum_{i =1}^{N}I(x_{i ,j}=a_{j,l},\tilde y_{i }=c_k)}{\sum_{i =1}^{N}I(\tilde y_{i }=c_k)}\\ j=1,2,\cdots,n; \;l=1,2,\cdots,s_j; \;k=1,2,\cdots,K $

     其中： $ MathJax-Element-76 $ 为示性函数， $ MathJax-Element-77 $ 表示第 $ MathJax-Element-78 $ 个样本的第 $ MathJax-Element-99 $ 个特征。

3. 朴素贝叶斯算法 ：

   • 输入 ：

     • 训练集 $ MathJax-Element-80 $ 。

       $ MathJax-Element-81 $ , $ MathJax-Element-82 $ 为第 $ MathJax-Element-121 $ 个样本的第 $ MathJax-Element-99 $ 个特征。其中 $ MathJax-Element-85 $ ， $ MathJax-Element-86 $ 为第 $ MathJax-Element-99 $ 个特征可能取到的第 $ MathJax-Element-88 $ 个值。

     • 实例 $ MathJax-Element-93 $ 。

   • 输出 ：实例 $ MathJax-Element-93 $ 的分类

   • 算法步骤：

     • 计算先验概率以及条件概率：
     $ p(y=c_k)=\frac {1}{N} \sum_{i=1}^{N}I(\tilde y_i=c_k),k=1,2,\cdots,K\\ p(x_j=a_{j,l}\mid y=c_k)=\frac{\sum_{i =1}^{N}I(x_{i ,j}=a_{j,l},\tilde y_{i }=c_k)}{\sum_{i =1}^{N}I(\tilde y_{i }=c_k)}\\ j=1,2,\cdots,n; \;l=1,2,\cdots,s_j; \;k=1,2,\cdots,K $
     • 对于给定的实例 $ MathJax-Element-91 $ ，计算： $ MathJax-Element-92 $ 。
     • 确定实例 $ MathJax-Element-93 $ 的分类： $ MathJax-Element-94 $ 。

2.4 贝叶斯估计

1. 在估计概率 $ MathJax-Element-95 $ 的过程中，分母 $ MathJax-Element-96 $ 可能为 0 。这是由于训练样本太少才导致 $ MathJax-Element-111 $ 的样本数为 0 。而真实的分布中， $ MathJax-Element-111 $ 的样本并不为 0 。

   解决的方案是采用贝叶斯估计（最大后验估计）。

2. 假设第 $ MathJax-Element-99 $ 个特征 $ MathJax-Element-119 $ 可能的取值为 $ MathJax-Element-101 $ ，贝叶斯估计假设在每个取值上都有一个先验的计数 $ MathJax-Element-104 $ 。即：

   $ p_{\lambda}(x_j=a_{j,l}\mid y=c_k)=\frac{\sum_{i =1}^{N}I(x_{i ,j}=a_{j,l},\tilde y_{i }=c_k)+\lambda}{\sum_{i=1}^{N}I(\tilde y_i=c_k)+s_j\lambda}\\ j=1,2,\cdots,n; \;l=1,2,\cdots,s_j; \;k=1,2,\cdots,K $

   它等价于在 $ MathJax-Element-103 $ 的各个取值的频数上赋予了一个正数 $ MathJax-Element-104 $ 。

   若 $ MathJax-Element-111 $ 的样本数为0，则它假设特征 $ MathJax-Element-119 $ 每个取值的概率为 $ MathJax-Element-107 $ ，即等可能的。

3. 采用贝叶斯估计后， $ MathJax-Element-108 $ 的贝叶斯估计调整为:

   $ p_\lambda(y=c_k)=\frac{\sum_{i=1}^{N}I(\tilde y_i=c_k)+\lambda}{N+K\lambda} $
   • 当 $ MathJax-Element-109 $ 时，为极大似然估计当 $ MathJax-Element-110 $ 时，为拉普拉斯平滑
   • 若 $ MathJax-Element-111 $ 的样本数为 0，则假设赋予它一个非零的概率 $ MathJax-Element-112 $ 。