信息增益和信息熵

Question

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

如果我们有一个由7枚硬币组成的袋子，其中一枚比其他硬币重，另一枚比其他硬币轻，我们知道较重的硬币+较轻的硬币与两个普通硬币相同，那么随机挑选两个硬币并相互称重会带来什么信息增益？

我们的目标是识别这两个奇怪的硬币。我已经考虑这个问题有一段时间了，并且不能在决策树中正确地构建它，或者其他任何方式。有什么帮助吗？

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

编辑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:更多的东西。

假设比例不平衡，赔率是(10/11)只有一个硬币是H或L硬币，以及(1/11)两个硬币都是H/L硬币

因此，我们可以得出结论：

(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枚硬币时，你可以得到(包括顺序) 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。如果你在实验之前随机地做了，你的概率是多少?随机选择H的概率是1/7；假设L的选择成功了1/6 --总体上是1/ 42。

实验结束后，你做得怎么样？如果C，你可以排除这两个硬币，你只剩下一个神秘的H，一个神秘的L和三个毫秒--所以如果你随机选择，你会有五分之一的机会选择H，如果成功的话选择L的概率是1/4，总体来说是20的1 --你的成功几率增加了一倍多。对于A(等同于B)的情况，更难看到“下一步是什么”，因为它们是几个，如上所述(不太明显，不是等价的……)，但显然你不会为H选择已知较轻的硬币(反之亦然)，如果你为H(或L)选择5个未称重的硬币中的一个，那么只有一个称重的硬币是另一个角色的候选者(分别是L或H)。为了简单起见，忽略“不等概率”问题(这真的有点棘手)，你能计算出你猜测的概率(随机选择与实验结果不一致)是...？