0

好奇什么被认为是判断有向无环图强度的可靠算法/方法 - 特别是某些节点的强度。我对此的主要问题可以归结为以下两个图表：

达格力量（如果图表未显示，请单击此处或访问此链接：http ://www.flickr.com/photos/86396568@N00/2893003041/

在我看来，A 的地位比 A 强。我判断强度的依据是如果一个链接被击倒，一个节点可以保持多强。我称第一个为细“高跷”，第二个为粗“茎”。

以下是我目前考虑的判断节点强度的方法：

1）计算下面的节点数，减去上面的节点数。

  • A=7, a=7, B=5, b=1

2）计算每个节点的完整路径（到终止）的数量，将它们的长度相加。

  • A=17 (1+5+5+5+1), B=12 (4+4+4), a=9 (3+3+3), b=2
  • 这使高跷更坚固，而不是茎。

3）计算每条可能的路径，将每个节点视为目的地。

  • A=9 (A->B, A->C, A->D, A->E, A->G, 2xA->F, 2xA->H), B=6, a=9, b= 2

到目前为止，3 似乎是最好的选择，但有没有更好的、适用于 DAG 的通用选项？这是具有已知最佳方法的东西吗？原则是在图表中使用尽可能多的信息，并以直观的方式解释解决方案。

4

4 回答 4

2

这真的取决于你所说的力量。由于 DAG 在表示信息方面的多功能性，您可以讨论从多结果控制流到非状语话语连接词的论据子句，甚至是句子中不同单词之间的全套依赖关系。

所有这些都会以不同的方式查看节点强度。例如，控制流可能会认为具有最多结果（因此最向外的弧）的节点是最强的，因为它对图表的最终结果具有最大的权力。在话语中，最强的节点是话语连接词，但它在语音和文本中出现在第一个连接词之后和第三个之前。一个句子的词汇“头”的选择与直接与之交互的弧的数量没有直接关系。

我的意思是，由于“强度”一词的多义性和 DAG 适合的数据类型，在这种数据类型中计算“强度”并没有真正的灵丹妙药。我想说，在机器学习问题中，所有这三种方法在为分类或排序问题选择特定类型的节点时都会提供非常丰富的信息，但最终，答案取决于数据类型的实际应用。

于 2008-09-28T00:52:55.360 回答
1

我认为您需要更清楚地定义“强度”。这与最大流量问题有关吗？

于 2008-09-28T00:53:13.860 回答
0

好的，实际应用是运动队。每个节点都是一个团队，每个环节都是对另一个团队的胜利。假设没有循环的胜利路径，如 A->B->C->A。目的是得到一个不与图表冲突的实力排名，并按照团队的实力对团队进行排名。有问题的网站是我的（有点半开玩笑的）足球网站，http://beatpaths.com/，您可以在其中每周查看整个 NFL 赛季的完整图表。（和其他运动。）我基本上是在寻找我上面列出的排名算法之外的排名算法，这些算法可能更有意义，并且可以被辩护为使用图表中的所有信息。目标不一定是在未来选秀方面更准确（尽管可能会使用更强大的算法），而是尽可能合理地描述本赛季到目前为止。

您可以在网站上看到 NFL 赛季的第 3 周。我删除了两个模棱两可的“beatloops”（长篇故事），依靠图表的其余部分来确定啄食顺序。

于 2008-09-28T07:23:55.967 回答
0

如果您要进行预测，最好的选择可能是最大熵排名算法。问题是为你的学习者开发一个足够大的数据集——越多越好。听起来您可以将每周比赛的排名用作单个排名实例。

于 2008-09-29T01:32:39.093 回答