8

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

我有一个有向无环图（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)，使节点 1 与 0 的比率最大化（最小分类错误）？

4

3 回答 3

5

这不是一个真正的答案，但我们需要澄清这个问题。不过，我可能稍后会回来寻找可能的答案。

下面是一个示例 DAG。

在此处输入图像描述

假设红色节点是起始节点，黄色节点是结束节点。你如何定义最短路径

1s 与 0s 的最高比率（最小分类错误） ?

编辑：我为每个节点添加名称，并为前两个边缘添加两个示例名称。

在我看来，您无法学习这样一种成本函数，它将特征向量作为输入，其输出（边权重？或其他）可以引导您在考虑图拓扑的情况下采取最短路径前往任何节点。原因如下：

  • 假设您没有您所说的特征向量。给定如上图，如果您想找到与1s 与0s 的比率相关的所有对最短路径，最好使用Bellman 方程或更具体地说是Dijkastra加上适当的启发式函数（例如，1s 在路径）。另一种可能的无模型方法是使用q-learning，其中访问节点获得奖励 +1，访问1节点获得奖励 -1 0。我们一次为每个目标节点学习一个查找 q-table。最后，当所有节点都被视为目标节点时，我们得到了全对最短路径。

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

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

于 2012-11-15T01:46:29.520 回答
1

这看起来像是遗传算法具有巨大潜力的问题。如果您将所需的函数定义为例如（但不限于）特征的线性组合（您可以添加二次项，然后是三次项，无限次），那么基因就是系数向量。mutator可以只是一个或多个系数在合理范围内的随机偏移。评估函数只是根据当前突变，所有对的最短路径上 1 与 0 的平均比率。在每一代，挑选最好的少数基因作为祖先，并变异形成下一代。重复直到 ueber 基因在手边。

于 2012-11-21T05:04:56.760 回答
1

我相信您的问题与逆强化学习领域非常接近，您可以在其中对最佳路径进行某些“专家演示”并尝试学习成本函数，以便您的规划器（A* 或某些强化学习代理）输出相同的路径作为专家示范。这种训练是以迭代的方式完成的。我认为在您的情况下，您可以创建专家演示作为通过最大数量的 1 个标记边缘的路径。这是一篇关于同一篇好论文的链接：学习搜索：模仿学习的功能梯度技术。它来自机器人社区，其中运动规划通常设置为图形搜索问题，学习成本函数对于展示所需行为至关重要。

于 2017-06-06T19:52:31.937 回答