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

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

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


linear-regression big-o gsl blas
person BCS    schedule 23.12.2009    source источник
comment
Какой алгоритм? Наименьших квадратов?   -  person Jon Seigel    schedule 23.12.2009
comment
Да, метод наименьших квадратов. Я не знала, что есть еще какие-то.   -  person BCS    schedule 23.12.2009

Ответы (4)


arrow_upward
5
arrow_downward

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

альтернативный текст

где матрица alt textсоставляет 300 тыс. строк и 1200 столбцов, вектор коэффициентов alt text имеет размер 1200x1, а вектор RHS альтернативный текст 1200x1.

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

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

person duffymo    schedule 23.12.2009
comment
Итак, если я правильно это читаю (и IIRC), генерация A будет O (n m) ~ = O (m ^ 2) (в моем случае n/m=C), а умножение будет O (n < /i>n*m)~=O(n^3) и инверсия будет O(n^3) Теперь просто вычислить постоянный член. - person BCS; 24.12.2009

arrow_upward
8
arrow_downward

Линейная регрессия рассчитывается как (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_алгебра

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

person Emiller    schedule 03.12.2010
comment
Алгоритм Копперсмита-Винограда практически непригоден, так как коэффициент настолько велик, что требуется такая большая матрица, чтобы увидеть преимущество асимптотической эффективности, что это нереально: en.m.wikipedia.org/wiki/Coppersmith–Winograd_algorithm - person JStrahl; 03.08.2017

arrow_upward
2
arrow_downward

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

Насколько я понял, y — это вектор результатов (или, другими словами, зависимые переменные).

Таким образом, если X — матрица (n × m), а y — матрица (n × 1):

  1. Транспонирование матрицы (n × m) занимает O(n⋅m) времени и дает матрицу (m × n)
  2. (X' X) занимает O(n⋅m²) времени и создает матрицу (m × m)
  3. Инверсия матрицы (m × m) занимает O(m³) время
  4. (X' y) занимает O(n⋅m) время и создает матрицу (m × 1)
  5. Окончательное умножение матриц (m × m) и матриц (m x 1) занимает O(m²) времени.

Таким образом, время работы Big-O составляет O(n⋅m + n⋅m² + m³ + n⋅m + m²).

Теперь мы знаем, что:

  • m² ≤ m³
  • n⋅m ≤ n⋅m²

поэтому асимптотически фактическое время работы Big-O составляет O(n⋅m² + m³) = O(m²(n + m)).

И это то, что мы получили из http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_алгебра< /а>

Но мы знаем, что между случаями n → ∞ и m → ∞ есть существенная разница. https://en.wikipedia.org/wiki/Big_O_notation#Multiple_variables

Итак, какой из них мы должны выбрать? Очевидно, что скорее всего будет расти количество наблюдений, а не количество атрибутов. Итак, мой вывод таков: если мы предположим, что количество атрибутов остается постоянным, мы можем игнорировать m членов, и это облегчение, потому что временная сложность многомерной линейной регрессии становится простой линейной O(n). . С другой стороны, мы можем ожидать, что наше вычислительное время резко увеличится, когда количество атрибутов существенно возрастет.

person Alessandro Villa    schedule 06.05.2020
comment
Хорошо аргументированный ответ, но со скрытым предположением: вы предполагаете, что рассматриваемая реализация является наиболее эффективным решением (что, как я подозреваю, на самом деле вероятно, но я не видел доказательств этого). - person BCS; 06.05.2020

arrow_upward
0
arrow_downward

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

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 is n D^2

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

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

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

person Wesam Na    schedule 01.03.2016
comment
Разве это не просто сложность этой реализации? Есть ли доказательства того, что это самая быстрая реализация? - person BCS; 04.03.2016