图论 - 学习成本函数以找到最优路径

Question

这是一个有监督学习问题。

我有一个有向无环图（DAG）。每条边都有一个特征向量X，每个节点（顶点）都有一个标签0或1。任务是找到一个成本函数w（X），使得任何一对节点之间的最短路径具有1s与0s的最高比率（最小分类误差）。

解决方案必须具有良好的泛化能力。我尝试过逻辑回归，并且学习的逻辑函数相当准确地预测了给定传入边缘特征的节点的标签。但是，该方法没有考虑图的拓扑结构，因此整个图的解决方案是不最优的。换句话说，给定上述问题设置，逻辑函数不是一个好的权重函数。

尽管我的问题设置不是典型的二元分类问题设置，但这里有一个很好的介绍: http://en.wikipedia.org/wiki/Supervised_learning#How_supervised_learning_algorithms_work 以下是更多细节：

1.每个特征向量X都是实数的d维列表。

2.每条边都有一个特征向量。即，给定边缘集合E = {e1，e2，.. en}和特征向量集合F = {X1，X2... Xn}，则边缘ei与向量Xi相关联。

3.可以提出一个函数f（X），使得f（Xi）为边缘ei指向标有1的节点的可能性。这样的函数示例是我上面提到的，通过逻辑回归找到。但是，正如我上面提到的那样，这种函数是非最优的。

因此，问题是：给定图形、起始节点和终止节点，如何学习最优成本函数w（X），以便最大化节点1s与0s的比率（最小分类误差）？

- Diego

---

你能详细说明一下你尝试了什么，以及你所说的“它不起作用”是什么意思吗？ - carlosdc

这个图似乎只有两个节点，即标签0的节点和标签1的节点？！然而，这些节点是分开的，这意味着没有实际的图？您能否详细说明一下您的模型和所选的图表示方式？ - soufanom

@carlosdc。好的，我详细说明了我的逻辑回归方法，但它在我的玩具数据上没有起作用。谢谢。 - Diego

那是来自 Kaggle 竞赛，对吧？ - Daniel

1. 在您的逻辑方法中，如果一个节点有两个入边，您的输入特征会是什么样子？
2. 您说这是一个DAG，所以当您在任意一对节点之间进行最短路径时，路径必须遵循DAG拓扑结构（有向），对吗？
3. 您能详细说明一下成本函数及其目标吗？当前的陈述对我来说没有意义。谢谢。

- greeness

Answer 1

这并不是一个真正的答案，而是我们需要澄清问题。虽然我可能会稍后回来提供可能的答案。

下面是一个DAG示例。

假设红色节点是起始节点，黄色节点是结束节点。如何以“1的比例最高（分类误差最小）”来定义最短路径？ 编辑：我为每个节点添加了名称，并为前两个边提供了两个示例名称。

在我看来，您无法学习这样一个成本函数，它以特征向量作为输入，并且其输出（边权重？或其他任何东西）可以指导您朝着考虑图形拓扑的任何节点走最短路径。原因如下所述：

• 假设您没有所述的特征向量。给定上面的图形，如果您想根据1和0的比率找到所有对最短路径，那么使用Bellman方程或更具体地说是Dijkastra加上适当的启发式函数（例如路径中1的百分比）是完美的。另一个可能的无模型方法是使用q-learning，其中我们访问1节点时获得+1奖励，访问0节点时获得-1奖励。我们一次为每个目标节点学习一个查找q表。最后，当所有节点被视为目标节点时，我们拥有所有对最短路径。

• 现在假设您神奇地获得了特征向量。既然您能够在没有这些向量的情况下找到最优解，那么它们存在时如何帮助您呢？

• 有一种可能的情况是，您可以使用特征向量来学习优化边权重的成本函数，即特征向量依赖于图形拓扑（节点之间的链接和1和0的位置）。但我在您的描述中没有看到这种依赖关系。所以我猜它不存在。

- greeness

---

感谢提供这个例子。任何图中的最短路径通常使用成本函数w(.)来指定每个边缘的权重。我想知道如何找到一个成本函数w(X)，它依赖于每个边缘上的特征向量X，以便基于该权重函数的最短路径最大化1和0的比率（您可以快速看到，在上面的示例中有两条路径使得该比率最大）。请注意，我要找到的权重函数仅取决于每个边缘处的特征向量，而不“知道”每个节点的标签是什么。 - Diego

据我所知，你无法学习这样一个以边权重为输入的代价函数。正如我多次所述，代价函数以特征向量作为输入，而不是权重。现在，我知道我可以使用Dijkstra算法找到最大化1和0比率的路径，但这不是问题。问题是找到一个函数，它不使用每个节点的标签（0或1），而只使用特征向量，将权重分配给边，使得最短路径具有最大的1和0比率。在说它没有意义之前，请阅读并理解这个问题。 - Diego

您说“有趣。您在问题陈述中何时提到“仅使用节点上的标签而不使用标签”？？？您甚至提供了一个监督式学习示例来展示您尝试了什么，那么您如何在没有标签“1”和“0”的情况下进行？是的，我不理解您的问题，但我认为您自己也不理解您的问题，至少一开始没有清楚地陈述问题。”很抱歉，我不会修改原文的错误拼写和语法。这句话询问对方在什么地方提到了只使用节点上的标签而不使用标签，并且指出了对方在示例中提供了有标签的监督式学习示例，因此对方似乎没有遵循自己提出的问题要求。最后表达了自己对问题陈述不够清晰的看法。 - greeness

没错，我只是一个监督学习的初学者。我完全不应该在这里提供帮助。我会闭嘴的。 - greeness

Answer 2

这似乎是一个遗传算法具有巨大潜力的问题。如果您将所需函数定义为例如（但不限于）特征的线性组合（您可以添加二次项，然后是三次项，无限制），则基因是系数向量。变异器可以仅是在合理范围内的一个或多个系数的随机偏移量。评估函数只是根据当前突变的所有对的最短路径上的1和0的平均比率。在每一代中，选择最好的几个基因作为祖先，并进行突变以形成下一代。重复此过程，直到手头有超级基因。

- Gene

---

这是一个新的好主意。但显然需要使用标签（1和0）才能使评估函数正常工作。 - dvail

Answer 3

我相信你的问题与逆强化学习领域非常接近，其中您需要采取某些最佳路径的“专家演示”，并尝试学习一种成本函数，使得您的计划者（A *或某些强化学习代理）输出与专家演示相同的路径。这种训练是以迭代方式完成的。我认为在您的情况下，专家演示可以由您创建，以通过最大数量的1标记边缘的路径为例。这里有一篇关于此主题的好论文链接： Learning to Search: Functional Gradient Techniques for Imitation Learning。它来自机器人社区，其中运动规划通常被设置为图搜索问题，并且学习成本函数对于展示所需行为至关重要。

- mohakbh