我试图理解为什么朴素贝叶斯分类器在特征数量上的扩展性是线性的，而在不做朴素假设的情况下，扩展性却不同。我已经了解了分类器的工作原理以及为何被称为“朴素”。我还不清楚为什么朴素假设能带来线性扩展性，而取消这一假设则会导致指数级扩展。我希望通过一个示例来展示在“朴素”设置下的线性复杂度的算法，以及在取消这一假设后的同一个示例来展示指数级复杂度。

回答：

问题在于以下数量的估计

P(x1, x2, x3, ..., xn | y)

当你假设“朴素性”（特征独立性）时，你会得到

P(x1, x2, x3, ..., xn | y) = P(x1 | y)P(x2 | y) ... P(xn | y)

你可以独立地估计每个P(xi | y)。自然地，这种方法的扩展性是线性的，因为如果你增加了k个特征，你只需要估计另外k个概率，每个概率都可以使用一些非常简单的技术（如统计具有给定特征的对象）来估计。

然而，如果没有朴素假设，你就没有任何分解。因此，你必须跟踪所有形式的概率

P(x1=v1, x2=v2, ..., xn=vn | y)

对于vi的每个可能值。在最简单的情况下，vi只是“true”或“false”（事件发生或未发生），这已经给你带来了2^n个概率需要估计（每个可能的“true”和“false”分配到一系列n个布尔变量）。因此，算法复杂度呈指数增长。然而，最大的问题通常不是计算上的问题——而是数据的缺乏。因为有2^n个概率需要估计，你需要超过2^n个数据点来对所有可能的事件进行任何估计。在现实生活中，你永远不会遇到大小为10,000,000,000,000的数据集…而这是使用这种方法处理40个特征所需的（唯一！）数据点的数量。