Как вычислить максимальное количество итераций, взятых алгоритмом обучения персептрона?

Question

Я считаю, что алгоритм обучения персептрона имеет верхнюю границу числа итераций, необходимых для сходимости для линейных разделимых данных. Я искал, чтобы найти точную формулу, которая поможет мне узнать количество итераций, которые это займет, но этого не было в Википедии.

Я читал онлайн, что этот объект зависит от количества выборок данных, поэтому, если у меня есть n (скажем 5000) выборок, сколько итераций потребуется для персептрона, чтобы сходиться (предположим, что данные линейно отделимы). Или это не так просто и зависит от самих данных?

P.S. Очень новое для машинного обучения, следовательно, простой вопрос.

Answer 1

Wikipedia относится к доказательству Novikoff, A. B. (1962), один из ранних результатов в области статистического обучения.

Вот некоторые немного другая форма дали результат для интернет-среды обучения:

Когда ||x_i|| ≤ D for all i (интуиция: радиус подготовки экземпляров) и margin >= γ:

• итераций, необходимых ограничены сверху : (D/γ)^2.

Интересные последствия:

• конвергенции результат не зависит от количества образцов!
• результат конвергенции, независимый от входного измерения!