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

Question

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

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

Answer 1

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

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

1. (X 'X) занимает время O (n * k ^ 2) и создает матрицу (k x k)

2. Инверсия матрицы (k x k) матрицы занимает O (k ^ 3) времени

3. (X 'Y) занимает O (n * k ^ 2) времени и создает (k x k) матрицу

4. Окончательное умножение матриц двух (k x k) матриц занимает O (k ^ 3) времени

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

Смотри также: http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra

Если вам кажется, что вы можете уменьшить время до O (k ^ 2 * (n + k ^ 0,376)) с помощью алгоритма Копперсмита-Винограда.

Answer 2

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

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

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

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

Answer 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