machine-learning - 如何解析具有任意数量邻居的 CFG？

Question

我正在开发一个项目，该项目试图使用上下文无关语法来解析图像。我们正在尝试构建图像片段树，然后使用机器学习使用这些视觉语法来解析图像。

我发现SVM-CFG看起来很理想，问题是它是为字符串解析而设计的，字符串中的每个终端最多有两个邻居（之前和之后的单词）。在我们的视觉语法中，每个片段可以紧挨着任意数量的其他片段。

解析这些视觉语法的最佳方法是什么？具体来说，我可以对我的数据进行编码以使用 SVM-CFG 吗？还是我必须编写自己的内核/解析库？

Answer 1

SVM-CFG 是 SVM-struct 中使用的切割平面优化算法的具体实现（在此处描述http://www.cs.cornell.edu/People/tj/publications/tsochantaridis_etal_04a.pdf，第 4 节）。

在每一步，切割平面算法都会调用一个函数来找到得分最高的结构化输出分配（在 SVM-CFG 中，这是得分最高的解析）。

对于一维字符串，SVM-CFG 运行动态规划算法以在多项式时间内找到得分最高的解析。

您可以扩展 SVM-struct 以返回图像的最高得分解析，但不存在多项式时间算法来执行此操作！

这是解析图像的最先进技术的参考：http: //www.socher.org/uploads/Main/SocherLinNgManning_ICML2011.pdf。他们在寻找图像分割的最高得分解析时遇到了同样的问题，因此他们使用贪婪算法来寻找近似解决方案（参见第 4.2 节）。您也许可以将类似的贪心算法合并到 SVM 结构中。