CMSC 5724 Data Mining and Knowledge Discovery - Lecture 03
- An alternative way to describe the Bayes method
- Bayesian network
An alternative way to describe the Bayes method
接下来会提供一种代替方法来描述贝叶斯方法（朴素贝叶斯为例）。这个描述方法会阐明分类器集合 H 的实际含义，这可以使用 generalization theorem 来限定获得的分类器的 generalization error (err_D(h))。
这里的 placeholders 就是决策树中的一个参数，每一个 placeholder 可以用 64 位来表述，因为有 1/-1，因此是 2^64，那么就有 2^(64 * #placeholder)。
Bayesian network
我们定义 Bayesian network 为一个 acyclic directed graph (DAG) 非循环有向图 G，G 满足以下条件：
- G 有 d + 1 个节点，包括一个表示 label 的的节点跟表示每个 attribute 的节点
- G 有一个单独的根节点，该节点就是 label
- 如果 attribute u 没有到 attribute v1, …, vx（x ≥ 1可以为任意整数） 的路径，那么 u 和（v1, …, vx）是条件独立于 parents(u)
e.g.
- A3 跟 (y, A5)，(y, A5) 是一个联合，因此只能以 A3 为 u，那么就是条件独立于 A3 的父节点 A1。
- A4 跟 A5 条件独立于 A1，A2，但是不能说 A4 跟 A5 条件独立于 A1，因为 A4 跟 A5 都可以作为 u
- A3 跟 A2，当A3 为 u 时，它们条件独立于 A1；当 A2 为 u 时，它们条件独立于 y
定理
给定 Bayesian network G 描述的条件独立性假设，我们有
e.g.
引理
如果 A 跟 B 是条件独立于 C，那么
第一行是条件独立的定义，第二行可以证明
证明
拓扑排序：对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。
e.g.
第一行中 A2 出现在了 A4 跟 A5 后面，所以不是拓扑排序。
在不失一般性的情况下，假设 y，A1，… ，Ad 是 G 的拓扑顺序（即，从顶点 u 到 u 之前任何顶点的路径都不存在）
最后的等式使用了 G 隐含的条件独立属性和下面的事实
e.g.
e.g. 1
如果我们给定 Bayesian network 如图，
那么 Pr[30+, undergrad, programmer | y = -1] 会计算为
e.g. 2
如果我们给定 Bayesian network 如图，
那么 Pr[30+, undergrad, programmer | y = -1] 会计算为
