像许多人一样，我对机器学习很感兴趣。我已经上过这方面的课程，并且阅读了一些论文。我想了解是什么让一个问题在机器学习中难以解决。理想情况下，我想了解如何量化或表达一个问题在机器学习中的复杂性。

显然，如果一个模式非常嘈杂，人们可以观察不同算法的更新技术，并发现某些特定的机器学习算法由于嘈杂的标签而错误地更新到错误的方向，但这是一种非常定性的论证，而不是某种分析性/可量化的推理。

那么，如何量化一个问题或模式的复杂性，以反映机器学习算法面临的难度呢？也许是来自信息论的某些东西，我真的没有头绪。

回答：

在机器学习理论中，通常使用域的VC维度来分类“学习它的难度”。

如果存在一组k个样本，无论它们的标签如何，所建议的模型都能“粉碎它们”（使用模型的某种配置完美地分割它们），则该域被认为具有VC维度k。

维基百科页面以二维空间为域，以线性分隔器为模型提供了示例：

上述尝试展示了在二维空间中存在一组点，可以调整线性分隔器来分割它们，无论标签是什么。然而，对于二维空间中的每一个4个点，总有一些标签分配使得线性分隔器无法分割它们：

因此，二维空间与线性分隔器的VC维度为3。

此外，如果一个域和一个模型的VC维度是无穷大，则认为该问题是不可学习的。

如果你有足够强的数学背景，并且对机器学习理论感兴趣，你可以尝试关注Amnon Shashua关于PAC的讲座。