Что такое BigO линейной регрессии?

Насколько велика система, разумно ли пытаться выполнить линейную регрессию?

В частности: у меня есть система с ~ 300K примерными точками и ~ 1200 линейных членов. Является ли это возможным для вычисления?

Ответы

Ответ 1

Вы можете выразить это как матричное уравнение:

где матрица составляет 300K строк и 1200 столбцов, вектор коэффициентов равен 1200x1, а вектор RHS равен 1200x1.

Если вы умножаете обе стороны на транспонирование матрицы , у вас есть система уравнений для неизвестных, что 1200x1200. Вы можете использовать разложение LU или любой другой алгоритм, который вы хотите решить для коэффициентов. (Это то, что делают наименьшие квадраты.)

Таким образом, поведение Big-O является чем-то вроде O (mmn), где m = 300K и n = 1200. Вы учли бы транспонирование, матричное умножение, разложение LU и обратную замену, чтобы получить коэффициенты.

Ответ 2

Линейная регрессия вычисляется как (X'X) ^ - 1 X'Y.

Если X - матрица (n x k):

(X 'X) принимает O (n * k ^ 2) время и выдает матрицу (k x k)
Матричная инверсия матрицы (k x k) принимает O (k ^ 3) время
(X 'Y) принимает O (n * k ^ 2) время и выдает матрицу (k x k)
Окончательное матричное умножение двух (k x k) матриц принимает O (k ^ 3) время

Таким образом, время работы Big-O равно O (k ^ 2 * (n + k)).

Если вам кажется, что вы можете получить время до O (k ^ 2 * (n + k ^ 0.376)) с помощью алгоритма Coppersmith-Winograd.

Ответ 3

Линейная регрессия модели с закрытой формой вычисляется следующим образом: производная от

RSS (W) = -2H ^ t (y-HW)

Итак, мы решаем для

-2H ^ t (y-HW) = 0

Затем значение W равно

W = (H ^ t H) ^ - 1 H ^ 2 y

где: W: это вектор ожидаемых весов H: матрица признаков N * D, где N - количество наблюдений, а D - количество функций y: это фактическое значение

Тогда сложность

H ^ t H является n D ^ 2

Сложность транспонирования D ^ 3

Итак, сложность

(H^t H)^-1 is n * D^2 + D^3