生成式分类器（generative classifiers）

判定特征向量x是否属于某一类型

<script type="math/tex; mode=display" id="MathJax-Element-1">p(y=c|x)=\frac{p(y=c)p(x|y=c)}{\sum_{c'} p(y=c'|\theta)p(x|y=c')}</script>

为啥叫生成式判别器？因为它强调如何利用类条件概率密度（class-conditional desity） p(x|y=c) <script type="math/tex" id="MathJax-Element-2">p(x|y=c)</script>和类先验 p(y=c) <script type="math/tex" id="MathJax-Element-3">p(y=c)</script>。类条件密度定义了我们期望的每个类的数据（what kind of data we expect to see in each class），类别状态为c时，x的概率密度

数字游戏：选择一些概念C，给你一系列随机从某个概念中产涩会难过的正样本 D={x1,⋯,xN} <script type="math/tex" id="MathJax-Element-4">D=\{x_1,\cdots,x_N\}</script>，判断某个新测试用例 x~ <script type="math/tex" id="MathJax-Element-5">\tilde{x}</script>是否属于C。把这个事件看成是服从某个概率分布 p(x~|D) <script type="math/tex" id="MathJax-Element-6">p(\tilde{x}|D)</script>，即给定数据D，任意 x~∈{1,⋯,100} <script type="math/tex" id="MathJax-Element-7">\tilde{x}\in\{1,\cdots,100\}</script>的概率。这就是后验预测分布（posterior predictive distribution）

离散数据的生成式模型

似然（likelihood）

两个假设 h1 <script type="math/tex" id="MathJax-Element-8">h_1</script>，和 h2 <script type="math/tex" id="MathJax-Element-9">h_2</script>，为啥选择 h1 <script type="math/tex" id="MathJax-Element-10">h_1</script>？

假设样本是从它们各自组成的外延（extension）中均匀采样的。比如，偶数假设外延是 h1={2,4,⋯,100} <script type="math/tex" id="MathJax-Element-11">h_1=\{2,4,\cdots, 100\}</script>, 2的幂的假设外延是 h2={2,4,8,⋯,64} <script type="math/tex" id="MathJax-Element-12">h_2=\{2,4,8,\cdots, 64\}</script>。在这种强采样假设下（strong sampling assumption），独立采样N次得到观察样本D的概率是

p(D|h)=[1size(h)]N

<script type="math/tex; mode=display" id="MathJax-Element-13"> p(D|h)=[\frac{1}{size(h)}]^N</script>
这个式子隐含着：在保持数据一致性时，模型倾向于选择最简单（外延最小）的假设（奥卡姆剃刀）。这种倾向便可以用“似然”来描述

先验（prior）

主观上的信息，称为先验，一般代表了该问题的背景知识

对集合 D={16,8,2,64} <script type="math/tex" id="MathJax-Element-14">D=\{16, 8, 2, 64\}</script>，根据似然概率，假设 h′="2的幂，并排除32" <script type="math/tex" id="MathJax-Element-15">h'="2的幂，并排除32"</script>概率更大。但是从主观经验判断，这种假设不自然（conceptually unnatrual），因此可以给一个较低的先验概率。

后验（posterior）

<script type="math/tex; mode=display" id="MathJax-Element-16">p(h|D)=\frac{p(D|h)p(h)}{\sum_{h' \in H} p(D, h')}</script>

注意分母是类似归一化的作用，可以忽略， p(h|D)∝p(D|h)p(h) <script type="math/tex" id="MathJax-Element-17">p(h|D) \propto p(D|h)p(h)</script>

当数据足够多时，后验变成一个单概念峰值，也就是MAP估计（贝叶斯的点估计）。 p(h|D)→σhMAP(h) <script type="math/tex" id="MathJax-Element-18">p(h|D) \rightarrow \sigma_{h^{MAP}}(h)</script>。 其中 hMAP <script type="math/tex" id="MathJax-Element-19">h^{MAP}</script>是后验的众数（mode）,也可以是中位数、期望

<script type="math/tex; mode=display" id="MathJax-Element-20">h^{MAP}=\arg\max_{h} p(h|D)</script>

MAP估计还可以拆成最大似然（频率学派的点估计）和最大先验的log和：

<script type="math/tex; mode=display" id="MathJax-Element-21">h^{MAP}=\arg\max_{h} p(D|h)p(h) \propto \arg\max_{h} [log p(D|h) + log p(h)]</script>
因为 p(D|h) <script type="math/tex" id="MathJax-Element-22">p(D|h)</script>依赖于样本数N，而 p(h) <script type="math/tex" id="MathJax-Element-23">p(h)</script>是个常数（给定主观知识），那么随着样本数增加，MAP估计趋近于最大似然估计， hMAP→hMLE=argmaxhp(D|h)∝argmaxhlogp(D|h) <script type="math/tex" id="MathJax-Element-24">h^{MAP} \rightarrow h^{MLE} = \arg\max_{h} p(D|h) \propto \arg\max_{h} log p(D|h)</script>

也就是说，随着数据量的增加，“数据压倒了先验”

如果真假设在假设空间内，MAP估计会收敛到这个假设。因而，我们说贝叶斯推断是一致性估计，或者说，假设空间是有限可辨识的（identifiable in the limit）。这种情形下，意味着我们能够用有限数据恢复真实分布。然而，我们的假设空间很可能是不完备的（这反而是经常发生的），这时，我们只能做到收敛到尽可能接近真实。

后验预测分布（posterior predictive distribution）

我们用贝叶斯方法得到后验，然后对为观察到的数据进行预测推断。这时，后验预测分布：

<script type="math/tex; mode=display" id="MathJax-Element-25">p(\tilde{x} \in C|D) = \sum_h p(y=1|\tilde{x}, h)p(h|D)</script>
wiki的写法：
<script type="math/tex; mode=display" id="MathJax-Element-26">p(\tilde{{x}}|\mathcal{D})=\sum\limits_{h}p(\tilde{{x}}|h)p(h|\mathcal{D})</script>
这相当于对不同假设h的加权和，因此叫做BMA（Bayes model averaging）

贝叶斯预测：假设随机变量Z具有密度函数 g(z|h) <script type="math/tex" id="MathJax-Element-27">g(z|h)</script>（随机变量X的密度函数是 f(x|h) <script type="math/tex" id="MathJax-Element-28">f(x|h)</script>，当Z和X出自同一总体时，g=f），给定X（已观察到的样本）时，随机变量Z的条件边缘分布，也就是后验预测密度：

p(z0|D)=∫Hg(z0|h)p(h|D)dh

<script type="math/tex; mode=display" id="MathJax-Element-29">p(z_0|D)=\int_{H} g(z_0|h)p(h|D)dh</script>
Z和X都是同一总体时，

p(x0|D)=∫Hf(x0|h)p(h|D)dh

<script type="math/tex; mode=display" id="MathJax-Element-30">p(x_0|D)=\int_{H} f(x_0|h)p(h|D)dh</script>
离散形式即为：

p(Z=z0|D)=∑hp(Z=z0|h)p(h|D)

<script type="math/tex; mode=display" id="MathJax-Element-31">p(Z=z_0|D)=\sum_{h} p(Z=z_0|h)p(h|D)</script>
这个p(z_0|h) 在我理解是已知的，即假设空间已知，只不过h是超参数，未知的。例如，我们做伯努利实验，已经做了10次，赢了3次；那么未来5次能赢几次？这个未来的5次也是服从伯努利分布的。即f(z_0)|h)=P(Z=z_0|h)。

当数据集很小时，后验是含糊不定的，得到的预测分布也是平坦的（broad）。但是，数据足够多（消除掉“假”假设后），后验变成了一个脉冲函数（delta函数），中心即是MAP估计。这时，预测分布变为：

<script type="math/tex; mode=display" id="MathJax-Element-32">p(x_0=C|D)=\sum_{h \in H} p(x_0|h)p(h|D) = \sum_h p(x_0)|h) \delta_{h^{MAP}}(h) = p(x_0|h^{MAP})</script>
这个叫做plug-in approximation，即用对h的MAP估计 hMAP <script type="math/tex" id="MathJax-Element-33">h^{MAP}</script>替代了D。

数据足够多时，BMA变成了plug-in approximation。正常情况，这两个方法是不同的。BMA得到的预测分布更平滑（因为它是加权平均）。plug-in实现简单点，两步走，第一步，找h的MAP估计，然后替换。数据量少时，plug-in很容易over-fitting，因为它选择的是包含当前D的代价最小的h（likelihood），随着数据的增多，它不得不改变h以包容新出现的、之前的h解释不了的数据（但注意，它始终只有一个h，只不过中途会换，且越换越宽）；BMA则是做平均，因此自始至终考虑的都是整个H，但随着数据的增长，会越来越把mass集中在某些仍然和D保持一致的h上，不断有h被淘汰（weight变为0），即越来越窄。当D增长到足够多时，H中除了 hMAP <script type="math/tex" id="MathJax-Element-34">h^{MAP}</script>之外的所有h都被weight掉了，得到跟plug-in一样的结果。

先验分布的选取

先验分布的选取这里没有仔细提。实际上，先验分布有不同的选取方式。例如，无信息先验（简单理解就是均匀分布）；共轭先验分布（从理论角度出发，在已知样本分布的情况下，选参数的先验分布为共轭先验分布，方便计算。

设 F <script type="math/tex" id="MathJax-Element-35">F</script>是由h<script type="math/tex" id="MathJax-Element-36">h</script>的先验分布构成的分布族，如果对任取的先验分布及样本值，后验分布 p(h|D) <script type="math/tex" id="MathJax-Element-37">p(h|D)</script>仍然是属于 F <script type="math/tex" id="MathJax-Element-38">F</script>的，那么称F<script type="math/tex" id="MathJax-Element-39">F</script>是一个共轭先验分布族。
* 针对扔硬币问题（二项分布，binomial），选用Beta分布作为先验
* 针对掷骰子问题（多项分布，multinomia），选用Dirichlet分布作为先验
好处是方便计算，且估计的参数h有意义

朴素贝叶斯分类器（Naive Bayes classification）(未完待续）

这一节没有看太懂，也是希望和大家讨论一下，有没有更好的理解NBC的方法？总觉得它这里和前面的知识有点断裂。

如何对一个离散特征组成的向量进行分类？

输入： x⃗ ∈1,⋯,KD <script type="math/tex" id="MathJax-Element-40">\vec{x}\in{1, \cdots, K}^D</script>，K是每个特征的值的个数（每个特征的取值范围有K种），D是特征的维度（特征的种类数）

目标：确定一个类条件分布 p(x⃗ |y=c) <script type="math/tex" id="MathJax-Element-41">p(\vec{x}|y=c)</script>。

朴素贝叶斯分类器假设：给定类标签后，各特征之间是条件独立的，即 p(x⃗ |y=c)=∏Dj=1p(xj|y=c,θjc) <script type="math/tex" id="MathJax-Element-42">p(\vec{x}|y=c) =\prod_{j=1}^{D}p(x_j|y=c, \theta_{jc})</script>

这个化简的模型就是NBC

这个模型是“naive”的，因为实际上特征之间不太可能独立（即使给定类标签）。但是奇怪的是，它的分类效果挺好，而且简单（只有 D∗c <script type="math/tex" id="MathJax-Element-43">D*c</script>个参数 θjc <script type="math/tex" id="MathJax-Element-44">\theta_{jc}</script>），而且一定程度上对overfit免疫

类条件概率密度举例

• 实值特征，用高斯分布： p(x⃗ |y=c)=∏Dj=1N(xj;μjc,σ2jc) <script type="math/tex" id="MathJax-Element-45">p(\vec{x}|y=c)=\prod_{j=1}^{D} N(x_j; \mu_{jc}, \sigma_{jc}^2)</script>
• 二值特征，用伯努利分布： p(x⃗ |y=c)=∏Dj=1Ber(xj;θjc) <script type="math/tex" id="MathJax-Element-46">p(\vec{x}|y=c)=\prod_{j=1}^{D} Ber(x_j;\theta_{jc})</script>
• 多值特征（分类），用多努利分布： p(x⃗ |y=c)=∏Dj=1Cat(xj|μjc→) <script type="math/tex" id="MathJax-Element-47">p(\vec{x}|y=c)=\prod_{j=1}^{D} Cat(x_j|\vec{\mu_{jc}})</script>

伯努利分布（Bernoulli）独立同分布地重复多次，便是二项分布（Binomial）。二项分布推广到多值变量，就是多项分布（multinomial）

范畴分布（categorical distribution）或多努力分布（multinoulli）也是伯努利分布的一种推广，是多项分布的一种特例（给出一个drawing的概率，而不是多个drawing的概率，也就是n=1:

f(x|p)=∏i=1kp[x=i]i

<script type="math/tex; mode=display" id="MathJax-Element-48">f(x|p)=\prod_{i=1}^{k} p_i^{[x=i]}</script>

注意这里的 y=c <script type="math/tex" id="MathJax-Element-49">y=c</script>就是我们前面说的一种假设 h <script type="math/tex" id="MathJax-Element-50">h</script>

模型训练

模型训练就是计算所有参数的MAP或者MLE点估计。

给出后验p(θ|D)<script type="math/tex" id="MathJax-Element-51">p(\theta|D)</script>的计算方式：

• 基于MLE的后验计算（模型拟合）

对每个数据 (xi→,yi) <script type="math/tex" id="MathJax-Element-52">(\vec{x_i}, y_i)</script>, 有

p(xi→,yi)=p(yi|π)∏jp(xij|θj)=∏cπ[yi=c]c∏j∏cp(xij|θjc)[yi=c]

<script type="math/tex; mode=display" id="MathJax-Element-53">p(\vec{x_i}, y_i) = p(y_i|\pi)\prod_{j} p(x_{ij}|\theta_{j}) = \prod_c \pi_c^{[y_i=c]} \prod_j \prod_c p(x_{ij}|\theta_{jc})^{[y_i=c]}</script>

那么对所有样本数据，log似然为

logp(D|θ)=∑c=1CNclogπc+∑j=1D∑c=1C∑i:yi=clogp(xij|θjc)

<script type="math/tex; mode=display" id="MathJax-Element-54">logp(D|\theta) = \sum_{c=1}^{C} N_c log \pi_c + \sum_{j=1}^D \sum_{c=1}^C \sum_{i:y_i=c} log p(x_{ij}|\theta_{jc})</script>

π <script type="math/tex" id="MathJax-Element-55">\pi</script>和 θjc <script type="math/tex" id="MathJax-Element-56">\theta_{jc}</script>可以分别优化。第一项是类先验，可以用MLE得到 πc^=NcN <script type="math/tex" id="MathJax-Element-57">\hat{\pi_c} = \frac{N_c}{N}</script>， Nc <script type="math/tex" id="MathJax-Element-58">N_c</script>是类c种的样本数；第二项就是类条件概率，对参数 θjc <script type="math/tex" id="MathJax-Element-59">\theta_{jc}</script>的MLE估计依赖于概率密度的种类。假设所有的特征都是二元的，即符合伯努利分布 xj|y=c∼Ber(θjc) <script type="math/tex" id="MathJax-Element-60">x_j|y=c \sim Ber(\theta_{jc})</script>，MLE就是 θjc=NjcNc <script type="math/tex" id="MathJax-Element-61">\theta_{jc}=\frac{N_{jc}}{N_c}</script>