在 Java 中计算互信息以选择训练集

Question

场景

---

我正在尝试对 Java GUI 应用程序中的数据集实施监督学习。用户将获得要检查的项目或“报告”列表，并根据一组可用标签对其进行标记。一旦监督学习完成，标记的实例将被提供给学习算法。这将尝试根据用户想要查看其余项目的可能性对它们进行排序。

为了充分利用用户的时间，我想预先选择将提供有关整个报告集合的最多信息的报告，并让用户对它们进行标记。据我了解，要计算此值，有必要找到每个报告的所有互信息值的总和，并按该值对它们进行排序。然后，来自监督学习的标记报告将用于形成贝叶斯网络，以查找每个剩余报告的二进制值的概率。

示例

---

在这里，一个人为的示例可能有助于解释，并且当我无疑使用了错误的术语时可能会消除混乱:-) 考虑一个应用程序向用户显示新闻报道的示例。它根据用户显示的偏好选择首先显示哪些新闻报道。具有相关性的新闻报道的特征是原产国、类别或日期。因此，如果用户将来自苏格兰的单个新闻报道标记为有趣，它就会告诉机器学习者来自苏格兰的其他新闻报道对该用户感兴趣的可能性会增加。对于诸如“体育”之类的类别或诸如 2004 年 12 月 12 日之类的日期，类似。

可以通过为所有新闻报道选择任何顺序（例如按类别、按日期）或随机排序它们，然后随着用户的进行计算偏好来计算此偏好沿着。我想做的是让用户查看少量特定的新闻报道并说出他们是否对它们感兴趣（监督学习部分），从而在该排序上获得某种“领先优势”。要选择向用户展示哪些故事，我必须考虑整个故事集。这就是互信息的用武之地。对于每个故事，我想知道当用户对其进行分类时，它可以告诉我多少关于所有其他故事的信息。例如，如果有大量来自苏格兰的故事，我想让用户对其中（至少）其中一个进行分类。其他相关功能（例如类别或日期）也类似。目标是找到分类后能提供有关其他报告最多信息的报告示例。

问题

---

因为我的数学有点生疏，而且我是机器学习的新手，所以在将互信息的定义转换为 Java 中的实现时遇到了一些麻烦。维基百科将互信息方程描述为：

但是，我不确定如果这实际上可以在没有任何分类并且学习算法还没有计算任何内容的情况下使用。

正如在我的示例中，假设我有大量此类的新的、未标记的实例：

public class NewsStory {
    private String countryOfOrigin;
    private String category;
    private Date date;
    // constructor, etc.
}

在我的特定场景中，字段/特征之间的相关性基于完全匹配，因此，例如，一个天和 10 年的日期差异在不平等上是等效的。

相关性因素（例如，日期比类别更相关吗？）不一定相等，但它们可以是预定义的且恒定的。这是否意味着函数 p(x,y) 的结果是预定义值，还是我混淆了术语？

问题 （最后）

---

考虑到这个（假的）新闻故事示例，我该如何实施互信息计算？库、javadoc、代码示例等都是受欢迎的信息。此外，如果这种方法从根本上来说是有缺陷的，那么解释为什么会出现这种情况也将是一个同样有价值的答案。

---

附言。我知道 Weka 和 Apache Mahout 等库，所以仅仅提及它们对我来说并没有多大用处。我仍在搜索这两个库的文档和示例，专门寻找有关互信息的内容。真正对我有帮助的是指向资源（代码示例、javadoc），这些库可以在其中提供相互信息。

Answer 1

我猜你的问题是这样的......

“给定一个未标记示例的列表，按照如果用户标记示例并将其添加到训练集中模型的预测准确性将提高多少来对列表进行排序。”

如果是这种情况，我认为互信息不是正确的选择，因为您无法计算两个实例之间的 MI。 MI 的定义是随机变量，单个实例不是随机变量，它只是一个值。

特征和类别标签可以被视为随机变量。也就是说，它们在整个数据集中具有值分布。您可以计算两个特征之间的互信息，以查看一个特征与另一个特征之间的“冗余”程度，或者计算一个特征与类标签之间的互信息，以了解该特征对预测的帮助程度。这就是人们通常在监督学习问题中使用互信息的方式。

我认为 ferdystschenko 关于主动学习方法的建议是一个很好的建议。

---

为了回应 Grundlefleck 的评论，我将通过使用他的 Java 对象类比思想来更深入地了解术语......

总的来说，我们使用术语“实例”、“事物”、“报告”和“示例”来指的是被分类的对象。让我们将这些东西视为 Java 类的实例（我省略了样板构造函数）：

class Example
{ String f1;
  String f2;
}

Example e1 = new Example("foo", "bar");
Example e2 = new Example("foo", "baz");

机器学习中的常用术语是 e1 是一个示例，所有示例都有两个特征 f1 和 f2，对于 e1，f1 的值为“foo”，f2 的值为“bar”。示例的集合称为数据集。

取数据集中所有样本的f1的所有值，这是一个字符串列表，也可以认为是一个分布。我们可以将该特征视为随机变量，并且列表中的每个值都是从该随机变量中获取的样本。例如，我们可以计算 f1 和 f2 之间的 MI。伪代码类似于：
<代码>

mi = 0
for each value x taken by f1:
{  sum = 0
   for each value y taken by f2:
   {  p_xy = number of examples where f1=x and f2=y
      p_x = number of examples where f1=x
      p_y = number of examples where f2=y
      sum += p_xy * log(p_xy/(p_x*p_y))
   }
   mi += sum
}

然而你不能计算 e1 和 e2 之间的 MI，它只是没有这样定义。

Answer 2

我知道信息增益仅与决策树（DT）有关，在决策树的构造中，对每个节点进行的分割是最大化信息增益的分割。 DT 是在 Weka 中实现的，因此您可以直接使用它，尽管我不知道 Weka 是否允许您计算 DT 节点下任何特定分割的信息增益。

除此之外，如果我理解正确的话，我认为您想要做的事情通常被称为

---

通过您编辑后的问题，我想我开始明白您的目标是什么。如果你想要的是计算 MI，那么在我看来，StompChicken 的答案和伪代码再清楚不过了。我还认为 MI 不是您想要的，您正在尝试重新发明轮子。

让我们概括一下：您希望训练一个可由用户更新的分类器。这是主动学习的经典案例。但为此，您需要一个初始分类器（您基本上可以只给用户随机数据进行标记，但我认为这不是一个选项）并且为了训练您的初始分类器，您至少需要一些少量的标记训练用于监督学习的数据。但是，您拥有的只是未标记的数据。你能用这些做什么？

好吧，您可以使用提供的标准聚类算法之一将它们聚类到相关实例组中通过 Weka 或某些特定的聚类工具，例如 Cluto。如果您现在获取每个集群的 x 个最中心的实例（x 取决于集群的数量和用户的耐心），并让用户将其标记为感兴趣或不感兴趣，您可以为其他实例采用此标签该集群也是如此（或者至少对于中心集群而言）。瞧，现在您有了训练数据，您可以使用这些数据来训练您的初始分类器，并通过每次用户将新实例标记为有趣或不感兴趣时​​更新分类器来启动主动学习过程。我认为你试图通过计算 MI 来实现的目标本质上是相似的，但可能只是你的收费方式错误。

不知道您的场景的详细信息，我应该认为您甚至可能根本不需要任何标记数据，除非您对标签本身感兴趣。只需对数据进行一次聚类，让用户从所有聚类的中心成员中选择一个他/她感兴趣的项目，并建议所选聚类中可能也有趣的其他项目。还建议来自其他集群的一些随机实例，这样，如果用户选择其中之一，您可能会认为相应的集群通常也很有趣。如果存在矛盾，并且用户喜欢集群中的某些成员，但不喜欢同一集群中的其他成员，那么您会尝试将数据重新集群到更细粒度的组中，以区分好与坏的组。甚至可以通过从一开始就使用分层聚类并在每个矛盾的用户输入原因时沿着聚类层次结构向下移动来避免重新训练步骤。