5.3 离散属性的参数估计
朴素贝叶斯分类器可以很容易地处理离散属性。
可估计为
然而，若某个属性值在训练集中没有与某个类同时出现过，则根据公式 82 估计得到 0。代入公式 75 得到 -1。因此，无论该样本的其他属性是什么，分类结果都不会是 y = c，这显然不太合理。
为了避免其他属性携带的信息被训练集中未出现的属性值“抹去”，在估计概率值时通常要进行平滑(smoothing)，常用拉普拉斯修正 (Laplacian correction)。具体的说，令 K 表示训练集 D 中可能的类别数，nj表示第 j 个属性可能的取值数，则概率估计修正为
拉普拉斯修正实际上假设了属性值与类别均匀分布，这是在朴素贝叶斯学习中额外引入的关于数据的先验。在训练集变大时，修正过程所引入的先验的影响也会逐渐变得可忽略，使得估值渐趋向于实际概率值。
在现实任务中朴素贝叶斯有多种实现方式。例如，若任务对预测速度要求较高，则对给定训练集，可将朴素贝叶斯分类器涉及的所有概率估值事先计算好存储起来，这样在进行预测时只需查表即可进行判别。若任务数据更替频繁，则可采用懒惰学习方式，先不进行任何训练，待收到预测请求时再根据当前数据集进行概率估值。若数据不断增加，则可在现有估值基础上，仅对新增样本的属性值所涉及的概率估值进行计数修正即可实现增量学习。
定义 3 (懒惰学习 (lazy learning))。这类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销是 0，待收到测试样本后再进行处理。相应的，那些在训练阶段就对样本进行学习处理的方法称为急切学习(eager learning)。
定义 4 (增量学习 (incremental learning))。在学得模型后，再接收到训练样例时，仅需根据新样例对模型进行更新，不必重新训练整个模型，并且先前学得的有效信息不会被“冲掉”。
5.4 朴素贝叶斯分类器的推广
朴素贝叶斯分类器采用了属性条件独立性假设，但在现实任务中这个假设往往很难成立。于是，人们尝试对属性条件独立性假设进行一定程度的放松，适当考虑一部分属性间的相互依赖关系，这样既不需要进行完全联合概率计算，又不至于彻底忽略了比较强的属性依赖关系，由此产生一类半朴素贝叶斯分类器 (semi-naive Bayes classifers) 的学习方法。
独依赖估计 (one-dependent estimator, ODE) 是最常用的一种策略，其假设每个属性在类别之外最多依赖于一个其他属性 (称为父属性)。问题的关键在于如何确定每个属性的父属性。SPODE (super-parent ODE) 假设所有属性都依赖于同一个属性，称为超父 (superparent)。TAN (tree augmented naive Bayes) [4] 以属性节点构建完全图，任意两结点之间边的权重设为这两个属性之间的条件互信息
。之后构建此图的最大带权生成树，挑选根变量，将边置为有向，以将属性间依赖关系约简为树形结构。最后加入类别结点 y，增加从 y 到每个属性的有向边。TAN 通过条件互信息刻画两属性的条件相关性，最终保留了强相关属性之间的依赖性。AODE (averaged ODE) [13] 尝试将每个属性作为超父来构建 SPODE，之后将那些具有足够训练数据支撑的 SPODE 集成作为最终结果。AODE 的训练过程也是“计数”，因此具有朴素贝叶斯分类器无需模型选择、可预计算节省预测时间、也能懒惰学习、并且易于实现增量学习。
能否通过考虑属性间高阶依赖进一步提升泛化性能? 相比 ODE, kDE 考虑最多 k 个父属性。随着依赖的属性个数 k 的增加，准确进行概率估计所需的训练样本数量将以指数级增加。因此，若训练数据非常充分，泛化性能有可能提升。但在有限样本条件下，则又陷入高阶联合概率的泥沼。
更进一步，贝叶斯网 (Bayesian network)，也称为信念网 (belief network)，能表示任意属性间的依赖性。贝叶斯网是一种概率图模型，借助有向无环图刻画属性间的依赖关系。
事实上，虽然朴素贝叶斯的属性条件独立假设在现实应用中往往很难成立，但在很多情形下都能获得相当好的性能 [2, 8]。一种解释是对分类任务来说，只需各类别的条件概率排序正确，无须精准概率值即可导致正确分类结果 [2]。另一种解释是，若属性间依赖对所有类别影响相同，或依赖关系能相互抵消，则属性条件独立性假设在降低计算开销的同时不会对性能产生负面影响 [15]。朴素贝叶斯分类器在信息检索领域尤为常用 [6]。
6 快问快答
随机梯度下降和标准梯度下降的优缺点各是什么?
• 参数更新速度。标准梯度下降需要遍历整个训练集才能计算出梯度，更新较慢。随机梯度下降只需要一个训练样例即可计算出梯度，更新较快。
• 冗余计算。当训练集样本存在冗余时，随机梯度下降能避免在相似样例上计算梯度的冗余。
• 梯度中的随机因素/噪声。标准梯度下降计算得到的梯度没有随机因素，一旦陷入局部极小将无法跳出。随机梯度下降计算得到的梯度有随机因素，有机会跳出局部极小继续优化。
实际应用时，常采用随机梯度下降和标准梯度下降的折中，即使用一部分样例进行小批量梯度下降。此外，相比随机梯度下降，小批量梯度下降还可以更好利用矩阵的向量化计算的优势。
梯度下降和牛顿法的优缺点各是什么?
• 导数阶数。梯度下降只需要计算一阶导数，而牛顿法需要计算二阶导数。一阶导数提供了方向信息(下降最快的方向)，二阶导数还提供了函数的形状信息。
• 计算和存储开销。牛顿法在参数更新时需要计算 Hessian 矩阵的逆，计算和存储开销比梯度下降更高。
• 学习率。梯度下降对学习率很敏感，而标准的牛顿法不需要设置学习率。
• 收敛速度。牛顿法的收敛速度比梯度下降更快。
• 牛顿法不适合小批量或随机样本。
实际应用时，有许多拟牛顿法旨在以较低的计算和存储开销近似 Hessian 矩阵。
线性回归的损失函数及梯度推导。
答案见上文。
为什么要使用正则化，ℓ1 和 ℓ2 正则化各自对应什么分布，各有什么作用?
答案见上文。
对数几率回归的损失函数及梯度推导。
答案见上文。
线性分类器如何扩展为非线性分类器?
答案见上文。
判别式模型和生成式模型各是什么，各自优缺点是什么，常见算法中哪些是判别式模型，哪些是生成式模型?
答案见上文。
贝叶斯定理各项的含义?
答案见上文。
朴素贝叶斯为什么叫“朴素”贝叶斯?
为了避开从有限的训练样本直接估计 p(x | y) 的障碍，朴素贝叶斯做出了属性条件独立假设，该假设在现实应用中往往很难成立。
References
[1] P. L. Combettes and V. R. Wajs. Signal recovery by proximal forward-backward splitting. Multiscale Modeling & Simulation, 4(4):1168–1200, 2005. 5
[2] P. M. Domingos and M. J. Pazzani. On the optimality of the simple bayesian classifer under zero-one loss. Machine Learning, 29(2-3):103–130, 1997. 12
[3] B. Efron. Bayesians, frequentists, and scientists. Journal of the American Statistical Association, 100(469):1–5, 2005. 1
[4] N. Friedman, D. Geiger, and M. Goldszmidt. Bayesian network classifers. Machine Learning, 29(2-3):131–163,1997. 12
[5] P. J. Huber. Robust estimation of a location parameter. Annals of Statistics, 53(1):492–518, 1964. 6
[6] D. D. Lewis. Naive (bayes) at forty: The independence assumption in information retrieval. In Proceedings of the 10th European Conference on Machine Learning(ECML), pages 4–15, 1998. 13
[7] K. P. Murphy. Machine Learning: A Probabilistic Perspective. MIT Press, 2012. 5, 6
[8] A. Y. Ng and M. I. Jordan. On discriminative vs. generative classifers: A comparison of logistic regression and naive bayes. In Advances in Neural Information Processing Systems 14 (NIPS), pages 841–848, 2001.12
[9] F. J. Samaniegos. A Comparison of the Bayesian and Frequentist Approaches to Estimation. Springer Science & Business Media, 2010. 1
[10] R. Tibshirani. Regression shrinkage and selection via the LASSO. Journal of the Royal Statistical Society. Series B (Methodological), pages 267–288, 1996. 4
[11] R. Tibshirani, M. Saunders, S. Rosset, J. Zhu, and K. Knight. Sparsity and smoothness via the fused lasso. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 67(1):91–108, 2005. 5
[12] A. N. Tikhonov and V. I. Arsenin. Solutions of Ill-posed Problems. Winston, 1977. 4
[13] G. I. Webb, J. R. Boughton, and Z. Wang. Not so naive bayes: Aggregating one-dependence estimators. Machine Learning, 58(1):5–24, 2005. 12
[14] M. Yuan and Y. Lin. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 68(1):49–67, 2006. 5
[15] H. Zhang. The optimality of naive bayes. In Proceedings of the Seventeenth International Florida Artifcial Intelligence Research Society Conference (FLAIRS), pages 562–567, 2004. 13
[16] H. Zou and T. Hastie. Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 67(2):301–320, 2005. 5
[17] 周志华. 机器学习. 清华大学出版社, 2016. 5, 7, 12
