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

Question

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

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

Answer 1

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

где матрица составляет 300 тысяч строк и 1200 столбцов, вектор коэффициента IS 1200x1, а hrs -вектор 1200x1.

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

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

Answer 2

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

Если x - (nxk) матрица:

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

2. Матрица инверсия матрицы (KXK) занимает O (K^3) время

3. (X 'y) берет O (n*k^2) время и создает матрицу (kxk)

4. Последняя матричная умножение двух (KXK) матриц занимает O (K^3) время

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

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

Если вы становитесь причудливым, похоже, что вы можете преодолеть время до O (K^2*(n+k^0,376)) с алгоритмом Coppersmith - Winograd.

Answer 3

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

Rss (w) = -2h^t (y -hw)

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

-2h^t (y-hw) = 0

Тогда значение w

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

куда:W.: вектор ожидаемых весовЧАС: Матрица функций n*d, где n - количество наблюдений, а D - количество функцийу: это фактическое значение

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

H^t h is n d^2

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

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

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