許多人，我對機器學習感興趣。我已經就這個話題開了一堂課，並且一直在閱讀一些論文。我有興趣找出什麼使機器學習難以解決問題。理想情況下，我想了解機器學習問題的複雜性如何量化或表達。顯然，如果一個模式非常嘈雜，人們可以看看不同算法的更新技術，並觀察到某些特定的機器學習算法錯誤地將自身更新爲錯誤的方向，這是由於有噪聲的標籤，但這是非常定性的爭論而不是一些分析/量化的推理。什麼使機器學習變得困難或「複雜」？關於模式的複雜性，不是計算上的
那麼，如何量化問題或模式的複雜性以反映機器學習算法面臨的困難？也許從信息理論等等，我真的不知道。
在機器學習的thery，域的VC dimension通常是用來區分「它有多難學！」
域說有k VC維，如果有一組k樣本，這樣無論他們的標籤如何，建議的模型都可以「粉碎它們」（使用模型的某些配置完美分割它們）。
維基百科頁面提供2D例如作爲域，具有線性分隔符作爲模型： 
上述嘗試證明存在點的2D的設置，使得一個無論標籤是什麼，都可以適合線性分隔符來分割它們。然而，對於在2D每4分，有標籤的一些分配，使得線性分隔符不能分割它們： 
因此，與線性分隔符2D空間中的VC維是3
另外，如果域和模型的VC維是infinty，據說，這個問題是不是可以學習
如果你有足夠強大的數學背景，感興趣的機器學習理論，你可以試試以下the lecture of Amnon Shashua about PAC