图论 - 学习成本函数以找到最优路径
Die*_*ego 8 graph-theory classification machine-learning
这是一个有监督的学习问题.
我有一个有向无环图(DAG).每个边都有一个特征向量X,每个节点(顶点)有一个标签0或1.任务是找到一个成本函数w(X),这样任何一对节点之间的最短路径具有最高的比率1s到0s(最小分类错误).
解决方案必须很好地概括.我尝试了逻辑回归,并且学习的逻辑函数很好地预测了给出传入边缘特征的节点的标签.但是,该方法不考虑图形的拓扑,因此整个图形中的解决方案不是最优的.换句话说,考虑到上面的问题设置,逻辑函数不是一个好的权重函数.
虽然我的问题设置不是典型的二进制分类问题设置,但这里有一个很好的介绍:http: //en.wikipedia.org/wiki/Supervised_learning#How_supervised_learning_algorithms_work
以下是一些更多细节:
- 每个特征向量X是实数的d维列表.
- 每条边都有一个特征向量.也就是说,给定边缘集合E = {e1,e2,... en}和特征向量集合F = {X1,X2 ... Xn},则边缘ei与向量Xi相关联.
- 有可能得出一个函数f(X),因此f(Xi)给出了边ei指向标有1的节点的可能性.这种函数的一个例子是我上面提到的,通过逻辑找到的回归.但是,正如我上面提到的,这种功能是非最佳的.
问题是:给定图形,起始节点和结束节点,如何学习最优成本函数w(X),以便节点1s与0s的比率最大化(最小分类误差)？
这不是一个真正的答案,但我们需要澄清这个问题.我可能会稍后回来寻找可能的答案.
以下是DAG的示例.
假设红色节点是起始节点,黄色节点是结束节点.你是如何定义的最短路径来讲
1s到0s的最高比率(最小分类误差)？
编辑:我为每个节点添加名称,为前两个边缘添加两个示例名称.
在我看来,你无法学习这样的成本函数,它将特征向量作为输入,其输出(边缘权重？或其他)可以指导您在考虑图形拓扑的情况下走向任何节点的最短路径.原因如下:
假设您没有所述的特征向量.给出如上图,如果你想找到对应于
1s与0s 的比率的所有对最短路径,那么使用Bellman方程或更具体地说Dijkastra加上适当的启发函数(例如,1s的百分比)是完美的.路径).另一种可能的无模型方法是使用q-learning,其中我们获得访问1节点的奖励+1和访问节点的-10.我们一次一个地学习每个目标节点的查找q表.最后,当所有节点都被视为目标节点时,我们拥有全对最短路径.现在假设,你神奇地获得了特征向量.既然你能够找到没有这些向量的最优解决方案,那么当它们存在时它们将如何帮助你呢？
有一种可能的条件是,您可以使用特征向量来学习优化边权重的成本函数,也就是说,特征向量取决于图拓扑(节点之间的链接以及
1s和0s 的位置).但我根本没有在你的描述中看到这种依赖性.所以我猜它不存在.
- 有趣.你在哪里声明`在你的问题陈述中没有使用每个节点上的标签,而只是......` 你甚至提供了一个监督学习的例子来展示你曾尝试过的东西,如果没有标签"1"和"0",你怎么能这样做...是的,我不明白你的问题,但我不认为你提出你自己的问题,至少你没有在第一时间以明确的方式陈述问题. (4认同)
这看起来是一个遗传算法具有巨大潜力的问题。如果您将所需的函数定义为（但不限于）特征的线性组合（您可以添加二次项，然后添加三次项，无限），那么基因就是系数向量。变异器可以只是一个或多个系数在合理范围内的随机偏移。评估函数只是根据当前突变，所有对沿最短路径的 1 与 0 的平均比率。在每一代中，选择最好的几个基因作为祖先并变异形成下一代。重复此操作，直到获得 ueber 基因。