artificial-intelligence - 信息增益和熵

Question

我最近阅读 this question关于信息增益和熵。我认为我对主要思想的理解还算不错，但我很好奇如何处理以下情况:

如果我们有一袋7个硬币，其中1个比其他的重，1个比其他的轻，我们知道重的硬币+轻的硬币与2个普通硬币相同，信息是什么？与挑选两个随机硬币并将它们相互权衡相关的 yield ？

我们的目标是识别两个奇数硬币。我一直在考虑这个问题，但无法在决策树或任何其他方式中正确地构建它。有什么帮助吗？

编辑:我理解熵的公式和信息增益的公式。我不明白的是如何以决策树格式来构建这个问题。

编辑 2:这是我目前所处的位置:

假设我们选择了两个硬币并且它们最终的重量相同，我们可以假设我们选择 H+L 的新机会是 1/5 * 1/4 = 1/20 ，这很容易。

假设我们选了两个硬币，左边更重。发生这种情况的三种不同情况:

HM:这给了我们 1/2 的机会选择 H 和 1/4 的机会选择 L:1/8
HL: 1/2 机会捡高, 1/1 机会捡低: 1/1
ML: 1/2 机会捡低, 1/4 机会捡高: 1/8

但是，我们选择 HM 的几率是 1/7 * 5/6，即 5/42
我们选择 HL 的几率是 1/7 * 1/6，即 1/42
我们选择 ML 的几率是 1/7 * 5/6，即 5/42

如果我们用这些赔率加权总体概率，我们会得到:

(1/8) * (5/42) + (1/1) * (1/42) + (1/8) * (5/42) = 3/56。

这同样适用于选项 B。

选项 A = 3/56
选项 B = 3/56
选项 C = 1/20

但是，选项 C 的权重应该更重，因为有 5/7 * 4/6 的机会选择两种媒介。所以我假设从这里我权衡这些可能性。

我很确定我在途中的某个地方搞砸了，但我认为我走在正确的道路上!

编辑 3:更多的东西。

假设比例不平衡，只有一个硬币是 H 或 L 硬币的几率是 (10/11)，并且两个硬币都是 H/L 的几率是 (1/11)

因此我们可以得出结论:
(10/11) * (1/2 * 1/5) 和
(1/11) * (1/2)

编辑 4:继续说它总共增加了 4/42。

Answer 1

您可以从信息增益考虑构建决策树，但这不是您发布的问题，这只是计算信息增益(大概是预期的信息增益；-)从一个“信息提取移动”——选择两个随机硬币并将它们相互权衡。要构建决策树，您需要知道从初始状态可以承受哪些移动(大概一般规则是:您可以选择两组 N 个硬币，N < 4，并将它们相互权衡——这是唯一的一种移动，参数超过 N)，每个移动的预期信息增益，这为您提供决策树的第一条腿(具有最高预期信息增益的移动)；然后，您对该移动的每个可能结果执行相同的过程，依此类推。

那么您是否需要帮助来计算 N 的三个允许值中的每一个的预期信息增益，仅适用于 N==1，或者您可以尝试自己做吗？如果获得第三种可能性，那么这将使您从练习中获得的学习量最大化——这毕竟是家庭作业的主要目的。那么为什么不尝试，编辑您的答案以向您展示您是如何进行的以及您得到了什么，我们很乐意确认您做对了，或者尝试帮助纠正您的程序可能揭示的任何误解!

编辑 : 试图给出一些提示，而不是将现成的溶液放在盘子上给 OP 服务；-)。将硬币称为 H(重)、L(轻)和 M(中-五个)。当您随机选择 2 个硬币时，您可以获得(7 * 6 == 42 种可能性，包括订单)HL、LH(各一个)、HM、MH、LM、ML(各 5 个)、MM(5 * 4 == 20 个案例)-- 2加 20 加 20 是 42，检查。在加权中你会得到 3 种可能的结果，称它们为 A(左边较重)、B(右边较重)、C(等重)。 HL、HM和ML，11例，将是A； LH、MH和LM，11例，将是B； MM，20个案例，将是C。所以A和B真的无法区分(哪一个是左边的，哪一个是正确的，基本上是任意的!)，所以我们有22个权重不同的案例，20个他们的权重不同将相等——这是一个好兆头，给出每个结果的案例数量非常接近!

因此，现在考虑对于每个实验结果，先验存在多少(等概率)可能性，后验存在多少。您的任务是选择 H 和 L 选项。如果你在实验前随机做，你有什么机会？ 7 中 1 为 H 的随机选择；鉴于 L 的选择成功率是 6 分之一 - 总体上是 42 分之 1。

实验后，你怎么样？如果是 C，你可以排除这两个硬币，你会留下一个神秘的 H、一个神秘的 L 和三个女士——所以如果你随机选择，你将有五分之一的人选 H，如果成功则有 1 个4 次选择 L，总体而言是 20 分之一——您的成功机会略多于两倍。看到 A(和等效的 B)案例的“下一步是什么”比较棘手，因为它们有几个，如上所列(而且不太明显，不是等概率的......)，但显然你不会选择已知的打火机H(反之亦然)的硬币，如果您为 H(或 L)选择 5 个未称重的硬币中的一个，则只有一个称重的硬币是另一个角色的候选人(分别为 L 或 H)。为简单起见忽略“非等概率”问题(这确实有点棘手)，您能否计算出您猜测的机会(随机选择与实验结果不一致)是……？