论文 机器学习 朴素贝叶斯

论文阅读--The Optimality of Naive Bayes

朴素贝叶斯的可行性分析

Posted by JAYLEE on April 15, 2019

论文阅读–The Optimality of Naive Bayes

​ image title image title

写在前面（直接忽略:runner:）

  • 这篇论文是加拿大New Brunswick大学教授Harry Zhang的一篇论文。是有关朴素贝叶斯的可行性分析的一篇文章。
  • 论文来源–厦门大学人工智能课程的汇报作业

Abstract

  • Naive Bayes 属于 Generative Learning Algorithms，或者是Probabilistic Generative Model 。它在机器学习和数据挖掘方面都有很显著的效果，特别是在分类任务方面有十分优秀的表现。但是它的前提条件——条件独立性假设，几乎在实际应用中是不存在的。一个Open Question的问题是，Naive Bayes 在分类方面的优异表现背后的真正原因究竟是什么呢？
  • 这篇文章引入了一种关于朴素贝叶斯在分类方面的优异表现的全新的解释。文中表示出了数据特征之间的相关性分布启到了十分重要的作用。例如每个类别的局部关联性（==均匀或者不均匀？==） 和当所有的特征结合起来后的局部关联效果，（与原来效果一致或者打破原来的相关性）。因此无论数据特征之间的相关性强度有多大，如果，特征之间的独立性分布==是均匀分布==，或者是特征之间的关联性被总体效果所打破，朴素贝叶斯仍然能够保持最理想的表现。文中提出并证明了一种朴素贝叶斯最优性的充分必要条件。并且在文章的最后研究了数据在高斯分布下的最优性原则。并提出并证明了在特征之间的相关性存在的情况下，朴素贝叶斯的充分条件。而这项探究也表明了在多个数据特征联合起作用时，存在于特征之间原本的相关性可能会消失！另外，论文还探究出了==朴素贝叶斯works well 的时候==

Naive Bayes and Augmented Naive Bayes

  • 分类任务是机器学习和数据挖掘领域的一个基本的话题。在分类任务中，学习算法的目标是构造器基于带有标签的训练数据集的分类器。这里以E代表数据特征值组（）。代表的是特征 的值。C代表的是分类变量。c表示C的值。在文中提出的是二分类任务，因此只有+，-标签。

  • 分类器是赋予数据与标签的函数，从概率的角度上来讲，对于数据E（）,它被分类成c的概率由以下公式表示：

  • E被分类为C = +,当且仅当

  • 就是贝叶斯分类器

  • 而朴素贝叶斯基于特征之间的独立性前提，因此

  • 而贝叶斯分类器的表示基于如下表示：

  • 对应的朴素贝叶斯图模型如下：

navie-bayes 概率图

  • 朴素贝叶斯是贝叶斯网络的最简单的形式，它的各个特征之间均相互独立，而这基本上是很少存在于实际当中的，而一种最直接的解决方法就是拓展它的结构，使用ANB（ augmented naive Bayes）替代它。它的概率图如下表示：

an example of ANB

  • 可以看出他的类别节点C指向所有的节点。并且特征节点时间有连接关系。依概率的角度上来讲，ANB G 可以表示成如下的联合概率分布表示：

  • 其中，
  • 文中提出作者本人在2001年的一篇文章中指出任何的贝叶斯网络都能够用ANB来表示，因此任何的联合概率分布都能够用ANB来表示。
  • 由于

  • 已经有研究表明（D. P. 1997）尽管分类准确率不依赖于热衷之间的相关性，例如朴素贝叶斯在强相关的特征存在的条件下依然能够表现出好的分类效果。

  • D.P.将朴素贝叶斯归因于它的损失函数—<0-1损失函数>,这个损失函数 的定义如下表示：

    Zero-one loss is a common loss function used with classification learning. It assigns 0 to loss for a correct classification and 1 for an incorrect classification.

  • 损失函数记录了错误的次数，它不像均方差等其他函数一样，把不正确的概率估计作为惩罚项，只要正确的类别有最大的概率就可以了。这就意味着朴素贝叶斯经常会改变类别的后验概率，但是最终的分类效果其实是不变的。当然这也意味这朴素贝叶斯用来做回归分析效果可能会很差。例如如果原来的正确分类概率是+1;90%,-1:10,而使用朴素贝叶斯可能计算出的后验概率是0.6和0.4，但是它的分类效果依然达成，但是概率估计就很差劲了。
  • 但是D.P.等人的发现依然是十分浅显的，因为他们没有说明，为什么在强相关的数据集下，朴素贝叶斯的分类结果没有变差。而我们需要知道的是数据之间的相关性是如何影响到分类的结果，并且下什么条件下，相关性会影响到分类结果。当前文献（基于作者写作），没有提出朴素贝叶斯最优性的确切条件。
  • 文中所提最关键点在于，朴素贝叶斯事实上受到数据间的相关性分布的影响而不是数据之间相关性，这句话怎么理解呢？例如有两个特征是相关的，但是当所有的数据联合时，这种相关性就会消失。文中还提出了在高斯分布的情况下，朴素贝叶斯最优性的充分条件，并且提出了朴素贝叶斯的works well 的条件。

A New Explanation on the Superb Classification Performance of Naive Bayes

  • 在给定数据集中，两个变量具有相关性，但是相关分布在每个类别中是均匀的。在这种情况下，数据的独立性条件显然是不存在啊的，但是朴素贝叶斯仍然可以做好很好的分类效果。并且，可以说最终影响分类效果的是所有特征相关性的结合。如果我们仅仅观察两个特征的相关性关系，可以说他们确实可能会影响到分类的效果，但是当所有的特征结合到一起，数据之间的相关性可能会因此消失并不再影响最终的分类情况。因此文章提出，是包含所有数据的相关性分布影响了朴素贝叶斯的分类效果，而不是单独的相关性导致的。
  • Definition 1
    • 给条数据E,两个分类器在0-1损失函数的条件下等价的条件是。当 ，并且如果在整个数据空间中，所有的数据E都能够满足 ,就用 来表示。

Local Dependence Distribution

  • 前文中提到ANB可以表示成所有的联合概率分布，因此我们可以选择ANB作为潜在的概率分布来表示。我们要探究的是，在什么条件下，朴素贝叶斯和ANB是等价的效果

  • 我们假定ANB G 只有两个类别，并且特征之间的相关性用节点之间的有向弧来表示。对于每个节点，它的父节点对它的影响是用对用的条件概率来衡量的。我们称节点和父节点之间的相关性为局部相关性 那么如何去衡量每个节点的局部相关性呢？基于父节点条件下的节点的条件概率和不包含父节点的条件概率的比值将能够衡量父节点对于子节点在分类的效果影响程度，并且有了以下的定义：

  • Definition 2

    • 对于ANB G 中的节点X，它的局部独立性在正负类上的表现可以用以下两个算式表示：

  • 反应出了节点X在+类别上的相关性强度，用以衡量X的局部相关性在分类出+的影响程度。而是类似的，进一步可以得出以下的结果

    • 当节点X没父节点的情况下

    • 当$$dd^-_G(x pa(x)) \geq 1dd^-_G(x pa(x))\geq 1$$ 就是在类别-下支持分了出类别C= -,否则支持分类出C = +.直观上来说，当从两个类别导出的局部相关性支持不同类别的分类结果。在两个类别的局部相关性将会相互抵消。而另外一种请求就是局部相关性将会联合支持分类的结果。

  • 以上的讨论显示出了从两个类别导出的局部相关性的比值将最终决定了每个节点的局部相关性支持的分类结果。因此有以下的定义

  • Definition 3

    • 对于ANB G 中的一个节点X,在节点X的局部相关性导出率，用 表示，如下所示：
    • 在以上的定义中， 衡量了X的局部相关性在分类结果上的影响。更进一步，我么得到以下的结果。
      1. 如果X没有父节点，
      2. 如果$$dd^+_G(x pa(x)) = dd^-_G(x pa(x)) 得出 ddr_G(x) = 1$$ 这意味着x的局部相关分布在类别-和类别+是均匀的。因此无论相关性的强度多大，局部相关性都不会影响最后的分类的效果。
      3. 如果 X在类别+的局部相关性将会比在类别-上面的局部相关性强，如果 将会得到相反的结果。

Global Dependence Distribution

  • 现在我们来探究在什么样的情况下ANB将会和naive bayes 得到一样的分类结果。下面的定理建立起了一个ANB 和naive bayes的关系

Theorem 1

给定一个 基于特征（）ANB 概率模型图G，和它对应的朴素贝叶斯概率图 ,假定 对于给定的特征数据E() 以下等式是恒成立的。 其中 被称为特征数据E的相关分布因素，用 来表示。

==证明过程（未）==

  • 从定理1中可以看出，相关性分布因素 决定了ANB和它对应的朴素贝叶斯在分类任务上的差异。更进一步， 是所有节点的局部相关导出率的产物。因此它反映出了全局相关分布（在每个类别上局部相关性分布，以及所有局部相关性的结合效果）。例如，当 ,G将会和 有一样的分类效果。事实上，这里并不一定要求 为了使得ANB G 与对应的朴素贝叶斯 有一样的效果，给出了以下的定理

Theorem 2

给定特征数据E() 一个ANB G 在0-1损失函数的条件下，与对应的朴素贝叶斯 等价。例如 当且仅当 或者当

  • 对于定理2 如果特征中的相关性分布满足确切的条件，朴素贝叶斯将与潜在的ANB效果是一致的。（即使存在强大的相关性），更进一步，我们可以得出以下的结果。
    1. 当 ANB G 的相关性将不会影响到分类效果。也就是G的分类效果将会和 的分类效果是一样的。以下展示出的是3种 的情况
      • 特征之间没有相关性
      • 对于G图上的每个节点X， ,也就是说，每个节点的局部相关性分布在两个类别上是平均的。
      • 一些支持对E分类成C = +的局部相关因素被其他支持E分类成C= - 的局部相关因素所抵消
    2. 并不要求 定理2的准确性条件解释了为什么在数据特征之间存在强相关性的数据集下，朴素贝叶斯依然能够有很好地分类效果。
    3. 当且仅当定理2的条件非真的条件下，ANB的相关性将会导致对应的朴素贝叶斯分类结果的改变。（也就是G和的分类结果将会不同）
  • 定理2提出了基于特征数据E下，朴素贝叶斯最优性的充分必要条件。对于数据空间中的每个数据E, 朴素贝叶斯将具有全局最优性。

Conditions for the Optimality of Naive Bayes

  • 这一小节中，我们将提出如果数据特征之间的相关性被相互抵消，朴素贝叶斯能够达到最优性。也就是即使在相关性存在的条件下，朴素贝叶斯仍然能够达到最优性表现。在这一节中，将研究特征在多元高斯分布的环境下，假定特征之间的相关性存在，朴素贝叶斯最优性的充分条件。这给我们提供了特征之间的相关性可能会相互抵消的理论依据。

  • 这里限制讨论的范围在特征 下，并且假定类别的概率密度函数是一个多元高斯分布。也就是如下算式表示：

CATALOG
    FEATURED TAGS