Сложность обучения для методов логистической регрессии с градиентной оптимизацией: O ((f + 1) csE), где:
- f - количество объектов (+1 из-за смещения). Умножение каждой функции на ее вес (
f операций, +1 для смещения). Еще f + 1 операций по суммированию всех их (получение прогноза). Используя метод градиента для улучшения весов, рассчитывается для одного и того же числа операций, так что в итоге мы получаем 4 * (f + 1) (два для прямого прохода, два для обратного), что просто O (F + 1) .
- c - количество классов (возможных выходов) в вашей логистической регрессии. Для двоичной классификации это единица, поэтому этот термин исключается. Каждый класс имеет соответствующий набор весов.
- s - количество выборок в вашем наборе данных, я думаю, этот довольно интуитивно понятен.
- E - количество эпох, которые вы хотите выполнить градиентным спуском (целые проходы через набор данных)
Примечание: эта сложность может меняться в зависимости от таких вещей, как регуляризация (еще одна операция c), но идея, стоящая за ней, выглядит следующим образом.
Сложность прогнозов для одной выборки: O ((f + 1) c)
- f + 1 - вы просто умножаете каждый вес на значение характеристики, добавляете смещение и суммируете все это вместе в конце.
- c - вы делаете это для каждого класса, 1 для двоичных предсказаний.
Сложность прогнозов для многих выборок: O ((f + 1) cs)
- (f + 1) c - см. Сложность для одного образца
- с - количество образцов
Разница между логистической и линейной регрессией с точки зрения сложности: функция активации.
Для мультиклассовой логистической регрессии это будет softmax , тогда как линейная регрессия, как следует из названия, имеет линейную активацию (фактически без активации). Это не меняет сложности, используя большие обозначения O, но это еще одна операция c * f во время тренировки (не хотелось загромождать картинку дальше), умноженная на 2 для backprop.