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 结构以返回图像的最高得分解析，但不存在多项式时间算法可以执行此操作!

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