2

给定一个 ML 问题，例如计算机视觉或 NLP，这些问题的计算复杂度是多少？

我可以认为使用训练模型是解决“困难”问题（棘手）的有效方法吗？

4

2 回答 2

1

Natural Language Processing并且Computer Vision是存在数千种算法的计算机科学领域。因此，一般而言，可能无法给出如此广泛领域的计算复杂性。算法的复杂性范围从次线性到 NP Hard。例如sub string search，复杂度为 O(mn)，其中 m 是子字符串的大小，n 是要搜索的文本的大小。在Automatic summarizationNLP 中是一个AI-Complete问题，使其成为NLP.

对于您问题的第二部分，答案是否定的。使用训练模型不会降低解决困难（难处理）问题的复杂性。

于 2013-04-18T01:40:36.937 回答
0

NLP 的复杂性是相当模糊的：你究竟想达到什么目的？在词性标注的情况下，您需要指定您关注的输入是什么：句子的长度、词汇量的大小……您使用的是什么标注器？有些只是预训练模型，可以根据各种特征预测标签（单词在句子中的位置，是否以某些特定字符结尾......）

在这种情况下，您需要知道预测基础分类器的新数据点的复杂性。

但是，反过来，评估分类器（或回归器）的复杂性可能非常复杂，因为它们依赖于许多其他算法，这些算法可以通过多种方式实现（稀疏数据/密集数据......）。我在我的博客上写了一篇详细的文章：机器学习算法的计算复杂度。主要结论是理论复杂性与观察到的复杂性（或至少对于小样本）不匹配，即使对于“简单”算法也是如此。

现在，回到词性标注，让我们想象它是使用支持向量机（它可能基于隐马尔可夫模型，结论会完全不同）对长度为 的句子执行的n。请注意，特征提取包含恒定数量的步骤，每个步骤都在恒定时间内进行评估（相邻词，二元特征）。对于每个单词，特征评估是O(1)。

使用线性内核（预测方法的复杂性取决于您使用 SVM 选择的内核），您必须预测每个单词的类别。与每个有界词相关的特征数量（大约 40 个），您只是在评估两个（稀疏）向量之间的内积。同样，您可以将其视为0(1). 因此，基于线性 SVM 对一个词的句子执行词性标注n是一个O(n).

即使我专注于一个非常简单的例子，你也会看到这个话题有多大……

于 2018-06-01T13:38:35.443 回答