如何計算感知器學習算法的最大迭代次數？

Question

我認爲感知器學習算法對於收斂線性可分數據所需的迭代次數有一個上限。我期待找到能夠幫助我找出需要的迭代次數的確切公式，但它並不在維基百科上。

我在網上讀到這個實體依賴於數據樣本的數量，所以如果我有n個（比如說5000個）樣本，感知器會收斂多少次迭代（假設數據是線性可分的）。或者它不那麼簡單，取決於數據本身？

P.S.機器學習非常新穎，因此是一個簡單的問題。

Answer 1

Wikipedia指的是Novkovoff，A.B.（1962）的證明，這是統計學習的早期結果之一。

這裏給出了在線學習環境，因此，一些稍微不同的形式：

當||x_i|| ≤ D for all i（直覺：訓練情況的半徑）和margin >= γ：

• 迭代需要被上界：(D/γ)^2。

有趣的結果：獨立的樣品數

• 匯聚的結果！
• 融合結果獨立於輸入維度！