概率问题与贝叶斯推理示例解析

table {
border-collapse: collapse;
width: 100%;
margin-bottom: 1rem;
}
th, td {
border: 1px solid #ddd;
padding: 8px;
text-align: left;
}
th {
background-color: #f2f2f2;
}
tr:nth-child(even) {
background-color: #f9f9f9;
}
pre {
background-color: #f8f8f8;
padding: 15px;
border-radius: 4px;
overflow-x: auto;
}

22、证明邦弗朗尼不等式 p(a, b) ≥ p(a) + p(b) – 1

根据概率的基本性质来证明。

因为

P(A∪B)=P(A)+P(B)−P(A,B)P(A∪B)=P(A)+P(B)−P(A,B)

且

P(A∪B)≤1P(A∪B)≤1

所以

P(A)+P(B)−P(A,B)≤1P(A)+P(B)−P(A,B)≤1

移项可得

P(A,B)≥P(A)+P(B)−1P(A,B)≥P(A)+P(B)−1

23、有两个盒子。盒子1中有3个红球和5个白球，盒子2中有2个红球和5个白球。随机选择一个盒子，选到盒子1和盒子2的概率均为0.5，从所选盒子中随机取出一个球，结果是红球。那么这个红球来自盒子1的后验概率是多少？

可根据贝叶斯公式计算。设事件A为选到盒子1，事件B为取出红球。

已知：

$ P(A) = 0.5 $

$ P(
eg A) = 0.5 $

$ P(B|A) = frac{3}{8} $

$ P(B|
eg A) = frac{2}{7} $

根据贝叶斯公式：

P(A|B)=P(B|A)P(A)P(B|A)P(A)+P(B|¬A)P(¬A)P(A|B)=P(B|A)P(A)P(B|A)P(A)+P(B|¬A)P(¬A)

代入已知值：

P(A|B)=38×0.5(38×0.5)+(27×0.5)=3/163/16+1/7P(A|B)=38×0.5(38×0.5)+(27×0.5)=3/163/16+1/7

通分并计算：

P(A|B)=2137P(A|B)=2137

所以这个红球来自盒子1的后验概率是 $ frac{21}{37} $。

24、证明 p(a, (b 或 c)) = p(a, b) + p(a, c) – p(a, b, c)

根据概率的基本性质，事件 “

a 且 (b 或 c)

” 等价于事件 “

(a 且 b) 或 (a 且 c)

“。

由概率的加法公式，对于任意两个事件

X

和

Y

，有：

P(X 或 Y)=P(X)+P(Y)−P(X 且 Y)P(X 或 Y)=P(X)+P(Y)−P(X 且 Y)

令

– $ X = a 且 b $

– $ Y = a 且 c $

则有：

p(a, (b 或 c))=p((a 且 b) 或 (a 且 c))=p(a, b)+p(a, c)−p(a, b, c)p(a, (b 或 c))=p((a 且 b) 或 (a 且 c))=p(a, b)+p(a, c)−p(a, b, c)

25、证明 p(x|z) = ∑y p(x|y, z)p(y|z) = ∑y,w p(x|w, y, z)p(w|y, z)p(y|z)

证明如下：

证明 $ p(x|z) = sum_y p(x|y, z)p(y|z) $：

根据全概率公式和条件概率定义，

p(x,z)=∑yp(x,y,z)p(x,z)=∑yp(x,y,z)

又因为

p(x,y,z)=p(x|y,z)p(y,z)p(x,y,z)=p(x|y,z)p(y,z)

且

p(y,z)=p(y|z)p(z)p(y,z)=p(y|z)p(z)

所以

p(x,z)=∑yp(x|y,z)p(y|z)p(z)p(x,z)=∑yp(x|y,z)p(y|z)p(z)

则

p(x|z)=p(x,z)p(z)=∑yp(x|y,z)p(y|z)p(x|z)=p(x,z)p(z)=∑yp(x|y,z)p(y|z)

证明 $ p(x|z) = sum_{y,w} p(x|w, y, z)p(w|y, z)p(y|z) $：

同样根据全概率公式和条件概率定义，

p(x,z)=∑y,wp(x,y,w,z)p(x,z)=∑y,wp(x,y,w,z)

而

p(x,y,w,z)=p(x|w,y,z)p(w|y,z)p(y,z)p(x,y,w,z)=p(x|w,y,z)p(w|y,z)p(y,z)

且

p(y,z)=p(y|z)p(z)p(y,z)=p(y|z)p(z)

所以

26、使用BRMLtoolbox实现软异或门，可利用condpot.m函数。

需根据BRMLtoolbox中condpot.m的功能和软异或门的原理进行代码编写。

27、使用BRMLtoolbox实现一个示例（类似汉堡示例）的两种情况。为此，需要定义联合分布p(变量A, 变量B)，其中dom(变量A) = dom(变量B) = {真, 假}。

可使用

condpot.m
，需定义联合分布 $ p( ext{变量A}, ext{变量B}) $，其中 $ ext{dom}( ext{变量A}) = ext{dom}( ext{变量B}) = { ext{tr}, ext{fa}} $。

28、使用BRMLtoolbox实现两个骰子示例，即模拟两个骰子投掷的概率问题

可使用

BRMLtoolbox
实现，该工具箱有用于操作离散变量分布的基本例程。

实现时可能需要用到如

condpot
等例程来定义和操作相关概率分布。

结合两个骰子问题的概率模型

p(t,sa,sb)=p(t|sa,sb)p(sa)p(sb)p(t,sa,sb)=p(t|sa,sb)p(sa)p(sb)

进行实现，其中需要定义好先验分布 $ p(sa) $、$ p(sb) $ 和似然项 $ p(t|sa, sb) $，并利用相关例程进行概率表的乘法和求和等操作以得到所需结果。

29、有一个重新分配的彩票游戏，需要从1到9中不重复地选出4个正确数字（例如3,4,4,1是不允许的），所选数字的顺序无关紧要。每周有100万人参与这个游戏，每人支付1英镑参赛。数字3、5、7、9是最受欢迎的，每100人中有1人选择这些数字。已知100万英镑的奖金将在中奖者之间平均分配，且任意4个不同数字随机产生。那么，每周选择3、5、7、9的每个玩家预期能赢得多少钱？最不受欢迎的数字组合是1、2、3、4，只有万分之一的人选择这个组合。他们平均每周能获利多少？你认为玩这个彩票有任何“技巧”吗？

计算选择3、5、7、9的玩家预期奖金，需先算出从9个数中选4个的组合数，再根据选该组合的人数和中奖概率计算。

选择1、2、3、4的玩家获利，用预期奖金减去1英镑参赛费。

由于数字随机产生，每个组合中奖概率相同，所以玩这个彩票没有技巧。

30、考虑一个邻接矩阵 A，若在一个时间步内可以从状态 j 到达状态 i，则元素 [A]ij = 1，否则为 0。证明矩阵 [Ak]ij 表示在 k 个时间步内从状态 j 到状态 i 的路径数量。并推导一个算法来找出从状态 j 到状态 i 的最小步数。

可根据邻接矩阵幂运算的性质证明 $[A^k]

{ij}$ 表示路径数量。对于求最小步数，可从 $k = 1$ 开始，依次计算 $A^k$，直到 $[A^k]

{ij}$ 非零，此时的 $k$ 即为最小步数。

31、证明对于一个单连通的连通图，边的数量 E 必须等于顶点数量减 1，即 E = V – 1。给出一个边数 E = V – 1 但不是单连通的图的例子。因此，条件 E = V – 1 是图为单连通的必要但不充分条件。

数学归纳法证明 $ E = V – 1 $

可使用

数学归纳法

证明 $ E = V – 1 $，具体步骤如下：

基础情况

考虑一个基础情况，例如：

一个顶点，零条边。

此时，边数 $ E = 0 $，顶点数 $ V = 1 $，满足公式 $ E = V – 1 $。

归纳假设

假设对于 $ n $ 个顶点的单连通图成立，即：

E=n−1E=n−1

归纳推导

接下来推导 $ n + 1 $ 个顶点的情况，验证公式是否仍然成立。

非单连通情况

对于

非单连通图

但满足 $ E = V – 1 $ 的情况，可以构造一个反例说明其非单连通性，例如：

三个顶点构成一个环；

去掉其中一条边，得到：

3 个顶点

2 条边

此时，图不是单连通的，但仍满足 $ E = V – 1 $。

32、文件WikiAdjSmall.mat包含随机选取的1000名维基作者，若两名作者“认识”彼此，则他们之间存在连接（可参考snap.stanford.edu/data/wiki-Vote.html了解相关信息）。基于1到20的间隔，绘制所有用户之间间隔（对应邻接矩阵的图中两个用户之间的路径长度）的直方图。也就是说，直方图中的第n(s)个区间包含间隔为s的用户对的数量。

可按以下步骤解决：

加载

WikiAdjSmall.mat
文件获取邻接矩阵；

计算所有用户对之间的最短路径长度；

统计间隔从1到20的用户对数量；

绘制直方图展示统计结果。

33、文件cliques.mat包含在一个有10个节点的图上定义的100个非最大团的列表。你的任务是返回一组唯一的最大团，消除完全包含在另一个团中的团。找到一个团后，你可以将其用二进制形式表示，例如(1110011110)，这表示该团从左到右包含变量1、2、3、6、7、8、9。将此二进制表示转换为十进制（最右边的位为个位，最左边的位为2的9次方），这对应于数字926。使用这种十进制表示，写出按十进制表示从低到高排序的唯一团的列表。详细描述你用于找到这些唯一团的算法步骤。

解决此问题的一般步骤如下：

读取文件

cliques.mat
中的非最大团列表。

将每个非最大团转换为二进制表示，再转换为十进制表示。

对这些十进制表示进行排序。

遍历排序后的列表，检查每个团是否完全包含在其他团中，如果是则排除。

输出剩余的唯一最大团的十进制表示列表。

34、考虑马尔可夫网络p(a, b, c) = φab(a, b)φbc(b, c)。名义上，对b求和后，变量a和c是相关的。对于二进制的b，请解释一种情况，在这种情况下并非如此，即从边际上看，a和c是独立的。

当φ
_ab
(a, b)和φ
_bc
(b, c)满足特定的函数形式，使得在对b求和时出现代数抵消的情况，就可能让a和c边际独立。例如，当φ
_ab
(a, b)和φ
_bc
(b, c)的乘积在对b求和后得到的结果可以分解为只与a有关的函数和只与c有关的函数的乘积时，a和c边际独立。

35、考虑一个定义在二元变量上的成对马尔可夫网络：p(x) = φ(x1, x100) ∏(i = 1 到 99) φ(xi, xi+1)。是否可以高效地计算 argmax(x1,…,x100) p(x) ？

可以。该成对马尔可夫网络结构是一个链状结构（虽然有一个额外的边连接 $x_1$ 和 $x_{100}$，但本质上可以通过一些图的处理方法转化为可高效处理的形式）。

对于这种结构，可以使用动态规划（如

最大和算法

，也称为

信念传播算法

在求最大值情况下的变体）来高效地计算：

argmax(x1,…,x100)p(x)argmax(x1,…,x100)⁡p(x)

动态规划通过将全局的最优解问题分解为一系列局部的最优子问题，避免了对所有可能的 $(x_1, …, x_{100})$ 组合进行穷举搜索，从而将计算复杂度从

指数级

降低到

多项式级

，实现高效计算。

36、考虑隐马尔可夫模型：p(v1, … , vT , h1, … , hT ) = p(h1)p(v1|h1) ∏(t = 2 到 T) p(vt|ht)p(ht|ht−1)，其中对于所有 t = 1, … , T，dom(ht) = {1, … , H} 且 dom(vt) = {1, … , V }。1. 画出上述分布的信念网络表示。2. 画出上述分布的因子图表示。3. 使用因子图推导求和 – 积算法来计算边缘分布 p(ht|v1, … , vT )。解释在你的因子图上传递消息的顺序。4. 解释如何计算 p(ht, ht+1|v1, … , vT )。5. 证明 p(h1, … , hT ) 的信念网络是一个简单的线性链，而 p(v1, … , vT ) 是一个完全连接的级联信念网络。

信念网络表示

：

隐状态节点 $ h_1 $ 指向可见状态节点 $ v_1 $，$ h_1 $ 指向 $ h_2 $，$ h_2 $ 指向 $ v_2 $，以此类推，形成一个链式结构，每个隐状态节点指向对应时刻的可见状态节点。

因子图表示

：

有对应于 $ p(h_1) $、$ p(v_1|h_1) $、$ p(v_t|h_t) $、$ p(h_t|h_{t-1}) $ 的因子节点，与隐状态和可见状态节点相连。

求和 – 积算法

：

通过从左到右和从右到左传递消息，先计算 $ alpha(h_t) $ 和 $ eta(h_t) $ 消息，再计算边缘分布

p(ht|v1,…,vT)∝α(ht)β(ht)p(ht|v1,…,vT)∝α(ht)β(ht)

消息传递顺序为先从左到右计算 $ alpha $ 消息，再从右到左计算 $ eta $ 消息。

计算 $ p(h_t, h_{t+1}|v_1, dots, v_T) $

：

可以通过联合边缘分布 $ p(h_t, h_{t+1}, v_1, dots, v_T) $ 除以 $ p(v_1, dots, v_T) $ 得到，联合边缘分布可通过因子图求和 – 积算法计算。

对于 $ p(h_1, dots, h_T) $

：

由于 $ h_t $ 仅依赖于 $ h_{t-1} $，形成简单线性链；对于 $ p(v_1, dots, v_T) $，每个 $ v_t $ 都通过隐状态与其他 $ v $ 存在间接联系，所以是完全连接的级联信念网络。

37、1. 画出分布 p(a, b, c, d, e, f, g, h, i) = p(a)p(b|a)p(c|a)p(d|a)p(e|b)p(f|c)p(g|d)p(h|e, f)p(i|f, g) 的信念网络。2. 画出道德化后的图。3. 画出三角剖分图。你的三角剖分图应包含尽可能小的团。4. 画出上述图的联合树，并验证它满足运行交集属性。5. 描述合适的团势初始化方法。6. 描述吸收过程并写出合适的消息更新时间表。

一般步骤为：

根据分布中变量的条件依赖关系绘制信念网络；

按照道德化定义，为每个变量的所有父节点添加无向边并将有向边改为无向边得到道德化图；

对道德化图进行三角剖分以得到含最小团的三角剖分图；

从三角剖分图构建联合树并验证运行交集属性；

可根据变量的先验分布或初始条件初始化团势；

吸收过程是在联合树中传递消息以更新团势，消息更新时间表可根据联合树结构确定。

38、1. 为分布 p(a, b, c, d, e, f) = p(a)p(b|a)p(c|b)p(d|c)p(e|d)p(f|a, e) 绘制信念网络。2. 绘制道德化图。3. 绘制三角化图。你的三角化图应包含尽可能小的团。4. 为上述图绘制一个联合树，并验证它满足运行交集属性。5. 描述合适的团势初始化方法。6. 描述吸收过程和合适的消息更新时间表。7. 证明该分布可以表示为 p(a|f)p(b|a, c)p(c|a, d)p(d|a, e)p(e|a, f)p(f) 的形式。

绘制信念网络

：以节点代表变量 a、b、c、d、e、f，根据条件概率关系绘制有向边，如从 a 到 b 有向边表示 p(b|a) 等。

绘制道德化图

：根据道德化定义，为每个变量的所有父节点添加无向边，并将有向边替换为无向边。

绘制三角化图

：通过添加边使图中不存在长度大于 3 的无环圈，且团大小尽可能小。

绘制联合树

：找到团图的最大权重生成树作为联合树，验证运行交集属性即任意两个包含共同变量的节点间路径上的团都包含该变量。

团势初始化

：可将团势初始化为相关条件概率的乘积。

吸收过程和消息更新时间表

：吸收过程是在联合树节点间传递消息以更新团势，消息更新时间表可采用从叶子节点向根节点再从根节点向叶子节点的顺序。

证明分布形式

：利用概率的链式法则和条件概率公式进行推导。

39、1. 使用BRMLtoolbox，为diseaseNet.mat文件中的分布（包含20种疾病d1, …, d20和40种症状s1, …, s40，每种疾病和症状都是二元变量，且每种症状连接3种父疾病）构建一个联合树，并使用它计算所有症状的边缘概率p(si = 1)。2. 解释如何以比使用联合树形式更高效的方式计算边缘概率p(si = 1)。通过实现此方法，将其结果与联合树算法的结果进行比较。3. 症状1到5存在（状态1），症状6到10不存在（状态2），其余未知。计算所有疾病的边缘概率p(di = 1|s1:10)。

可能需要使用

BRMLtoolbox
编写代码来解决。可利用相关函数如

jtree.m
来构建联合树，通过吸收或 Shafer-Shenoy 更新算法进行消息传递以计算边缘概率。更高效的计算方法可能需要根据分布的具体结构进行设计，比如利用变量之间的独立性等。

40、类似于 jtpot=absorption(jtpot,jtsep,infostruct) ，编写一个例程 [jtpot jtmess]=ShaferShenoy(jtpot,infostruct) ，该例程在 Shafer – Shenoy 更新下返回联合树的团边际和消息。修改 demoJTree.m ，使其除了输出使用吸收法得到的边际和条件边际结果外，还输出使用 Shafer – Shenoy 法得到的结果。

需要依据 Shafer – Shenoy 传播的原理进行代码编写。原理为：

对于有势函数 $psi(V_i)$ 的团 $i$ 及其相邻团 $j$，若已收到团 $i$ 其他相邻团的消息，可发送消息

λi→j=∑(Vi∖Vj)ψ(Vi)∏k≠jλk→iλi→j=∑(Vi∖Vj)ψ(Vi)∏k≠jλk→i

完成一轮消息传递后，任何团的边际由传入消息的乘积给出。

41、有人认为，金钱的效用并非基于其数量，而是基于我们相对于他人的财富拥有量。假设使用一个有10个区间的直方图来表示收入分布p(i)，其中i = 1, …, 10，每个区间代表一个收入范围。用这个直方图大致反映社会中的收入分布情况，即大多数人的收入接近平均值，极富和极贫的人很少。现在将收入x的效用定义为收入x高于随机选取的收入y的概率（在你所定义的分布下），并将其与p的累积分布联系起来。编写一个程序来计算这个概率，并绘制出所得效用随收入变化的函数图像。现在重复抛硬币打赌情景，即如果打赌获胜，新收入将处于直方图的最高区间；如果打赌失败，新收入将处于最低区间。比较在以下两种情况下的最优期望效用决策：（i）初始收入为平均水平；（ii）初始收入远高于平均水平。

可按以下步骤解决：

构建反映社会收入分布的直方图；

定义收入 $ x $ 的效用为高于随机收入 $ y $ 的概率并与累积分布联系；

编写程序计算概率并绘制效用 – 收入函数图像；

重复抛硬币打赌情景；

分别计算初始收入为平均水平和远高于平均水平时的最优期望效用决策并比较。

42、1. 绘制一个影响图来描述这个两阶段游戏。2. 一个赌徒需要决定是否应该进入这个两阶段游戏的第一阶段。证明基于做出最优的未来决策d2，基于第一个决策的期望效用为：U(d1 = 玩) = { p1(p2W2 – C2) + p1W1 – C1 若 p2W2 – C2 ≥ 0；p1W1 – C1 若 p2W2 – C2 ≤ 0 }

需按相关影响图绘制规则和期望效用计算逻辑完成。

影响图绘制要求

第一阶段决策

：d1

第一阶段结果

：x1

第二阶段决策

：d2

第二阶段结果

：x2

相关因素

：需体现相应成本和效用

期望效用证明要求

需分以下两种情况，根据已知概率和效用公式进行计算推导：

情况一

：p₂W₂ – C₂ ≥ 0

情况二

：p₂W₂ – C₂ ≤ 0

43、1. 假设效用由你银行账户中的英镑数量给出，写出参与赌局的期望效用公式U(bet)以及不参与赌局的期望效用公式U(no bet)。2. 上述情况可以有不同的表述。如果你赌局获胜，你将获得£(W – B)；如果你赌局失败，你将损失£(B – L)。计算参与赌局时你预期获得的金额Ugain(bet)以及不参与赌局时你预期获得的金额Ugain(no bet)。3. 证明U(bet) – U(no bet) = Ugain(bet) – Ugain(no bet)。

参与赌局的期望效用公式：

U(bet)=p(win)×U(win,bet)+p(lose)×U(lose,bet)U(bet)=p(win)×U(win,bet)+p(lose)×U(lose,bet)

其中：

$ U( ext{win}, ext{bet}) $ 为赌局获胜时的效用，即银行账户增加 £(W – B) 后的效用；

$ U( ext{lose}, ext{bet}) $ 为赌局失败时的效用，即银行账户减少 £(B – L) 后的效用。

不参与赌局时，银行账户金额不变，设初始效用为 $ U_0 $，则：

U(no bet)=U0U(no bet)=U0

参与赌局时预期获得的金额：

Ugain(bet)=p(win)×(W−B)−p(lose)×(B−L)Ugain(bet)=p(win)×(W−B)−p(lose)×(B−L)

不参与赌局时预期获得的金额：

Ugain(no bet)=0Ugain(no bet)=0

证明：

设初始银行账户金额为 $ M $，初始效用 $ U_0 = U(M) $。

赌局获胜时银行账户金额为 $ M + (W – B) $，效用为 $ U( ext{win}, ext{bet}) = U(M + (W – B)) $；

赌局失败时银行账户金额为 $ M – (B – L) $，效用为 $ U( ext{lose}, ext{bet}) = U(M – (B – L)) $。

因此：

U(bet)=p(win)×U(M+(W−B))+p(lose)×U(M−(B−L))U(bet)=p(win)×U(M+(W−B))+p(lose)×U(M−(B−L))

U(bet)−U(no bet)=p(win)×U(M+(W−B))+p(lose)×U(M−(B−L))−U(M)U(bet)−U(no bet)=p(win)×U(M+(W−B))+p(lose)×U(M−(B−L))−U(M)

Ugain(bet)−Ugain(no bet)=p(win)×(W−B)−p(lose)×(B−L)−0=p(win)×(W−B)−p(lose)×(B−L)Ugain(bet)−Ugain(no bet)=p(win)×(W−B)−p(lose)×(B−L)−0=p(win)×(W−B)−p(lose)×(B−L)

假设效用函数 $ U(x) $ 是线性函数，设 $ U(x) = kx + c $（$ k $、$ c $ 为常数）。

则：

U(bet)=p(win)×[k(M+(W−B))+c]+p(lose)×[k(M−(B−L))+c] =p(win)×(kM+k(W−B)+c)+p(lose)×(kM−k(B−L)+c) =kM(p(win)+p(lose))+p(win)×k(W−B)+p(lose)×(−k(B−L))+c(p(win)+p(lose)) =kM+p(win)×k(W−B)+p(lose)×(−k(B−L))+cU(bet)=p(win)×[k(M+(W−B))+c]+p(lose)×[k(M−(B−L))+c] =p(win)×(kM+k(W−B)+c)+p(lose)×(kM−k(B−L)+c) =kM(p(win)+p(lose))+p(win)×k(W−B)+p(lose)×(−k(B−L))+c(p(win)+p(lose)) =kM+p(win)×k(W−B)+p(lose)×(−k(B−L))+c

U(no bet)=kM+cU(no bet)=kM+c

U(bet)−U(no bet)=p(win)×k(W−B)+p(lose)×(−k(B−L))=k[p(win)×(W−B)−p(lose)×(B−L)]U(bet)−U(no bet)=p(win)×k(W−B)+p(lose)×(−k(B−L))=k[p(win)×(W−B)−p(lose)×(B−L)]

Ugain(bet)−Ugain(no bet)=p(win)×(W−B)−p(lose)×(B−L)Ugain(bet)−Ugain(no bet)=p(win)×(W−B)−p(lose)×(B−L)

当 $ k = 1 $ 时：

U(bet)−U(no bet)=Ugain(bet)−Ugain(no bet)U(bet)−U(no bet)=Ugain(bet)−Ugain(no bet)

44、一个训练集包含来自两个类别的一维示例。类别 1 的训练示例为 0.5、0.1、0.2、0.4、0.3、0.2、0.2、0.1、0.35、0.25，类别 2 的训练示例为 0.9、0.8、0.75、1.0。使用最大似然法为这两个类别分别拟合一个（一维）高斯分布。同时使用最大似然法估计类别概率 p1 和 p2。测试点 x = 0.6 属于类别 1 的概率是多少？

需使用最大似然估计的相关公式计算两个类别的均值和方差，以及类别概率 $ p_1 $ 和 $ p_2 $，再根据高斯分布概率密度函数和贝叶斯公式计算测试点属于类别 1 的概率。

45、编写一个 MATLAB 函数 A = ChowLiu(X)，其中 X 是一个 D × N 的数据矩阵，每列包含一个多元数据点，该函数返回 X 的 Chow – Liu 最大似然树。树结构以稀疏矩阵 A 的形式返回。使用 MATLAB 自带的 spantree 函数可以辅助实现。使用该函数对包含 10 个变量的数据矩阵进行处理，找到最大似然 Chow – Liu 树，并绘制结果有向无环图（DAG），边的方向从变量 1 向外。

计算所有变量对的互信息。

构建边权重为互信息的无向图。

使用

spantree
函数找到最大权重无向生成树。

选择一个任意节点作为根节点，将所有边的方向设置为远离根节点。

将树结构存储在稀疏矩阵

A
中并返回。

按照上述思路编写代码实现该函数，并使用相应数据进行测试和绘图。

46、这个问题与垃圾邮件过滤有关。每封电子邮件由一个向量x = (x1, …, xD)表示，其中xi ∈{0, 1}。向量的每个元素表示特定符号或单词是否出现在电子邮件中。这些符号/单词包括“money”“cash”“!!!”“viagra”等。因此，如果单词“cash”出现在电子邮件中，则x2 = 1。训练数据集由一组向量以及类别标签c组成，其中c = 1表示电子邮件是垃圾邮件，c = 0表示不是垃圾邮件。因此，训练集由一组对(xn, cn)组成，n = 1, …, N。朴素贝叶斯模型由p(c, x) = p(c) ∏(i = 1到D) p(xi|c)给出。1. 为这个分布绘制一个信念网络。2. 使用最大似然法，根据训练数据推导出该模型参数的表达式。假设数据是独立同分布的，p(c1, …, cN, x1, …, xN) = ∏(n = 1到N) p(cn, xn)。具体来说，参数是p(c = 1)、p(xi = 1|c = 1)、p(xi = 1|c = 0)，i = 1, …, D。3. 给定一个训练好的模型p(x, c)，解释如何形成一个分类器p(c|x)。4. 如果“viagra”从未出现在垃圾邮件训练数据中，讨论这将对包含单词“viagra”的新电子邮件的分类产生什么影响。5. 写出决策边界p(c = 1|x) = p(c = 0|x)的表达式，并证明它可以写成∑(d = 1到D) udxd – b = 0的形式，其中u和b是适当定义的。


1. **信念网络**：有一个根节点 `c`（类别标签），从 `c` 节点引出 `D` 条有向边分别指向 `x₁, x₂, ..., x_D` 节点。

2. **参数表达式**：
   - `p(c = 1) =` 训练集中 `c = 1` 的样本数 / `N`
   - `p(xᵢ = 1 | c = 1) =` 训练集中 `c = 1` 且 `xᵢ = 1` 的样本数 / 训练集中 `c = 1` 的样本数
   - `p(xᵢ = 1 | c = 0) =` 训练集中 `c = 0` 且 `xᵢ = 1` 的样本数 / 训练集中 `c = 0` 的样本数

3. **贝叶斯公式**：
   根据贝叶斯公式：
   $$
   p(c|x) = frac{p(x, c)}{p(x)}
   $$
   其中：
   $$
   p(x) = p(x|c = 1)p(c = 1) + p(x|c = 0)p(c = 0)
   $$
   可计算出 `p(c|x)`，比较 `p(c = 1|x)` 和 `p(c = 0|x)` 的大小进行分类。

4. **特征缺失问题**：
   如果“viagra”从未出现在垃圾邮件训练数据中，那么：
   $$
   p(x_{	ext{viagra}} = 1 | c = 1) = 0
   $$
   在分类新邮件时，会极大降低该邮件被分类为垃圾邮件的概率。

5. **分类边界推导**：
   由：
   $$
   p(c = 1|x) = p(c = 0|x)
   $$
   根据贝叶斯公式展开并化简，可得到：
   $$
   sum_{d=1}^{D} u_d x_d - b = 0
   $$
   其中 `u_d` 和 `b` 的具体表达式需根据展开化简过程确定。