Как различные статистические методы (регрессия, PCA и т. Д.) Масштабируются в зависимости от размера и размера выборки?

10

Существует ли известная общая таблица статистических методов, объясняющих, как они масштабируются в зависимости от размера и размера выборки? Например, мой друг сказал мне на днях, что время вычисления простой быстрой сортировки одномерных данных размера n равно n * log (n).

Так, например, если мы регрессируем y против X, где X - это d-мерная переменная, то идет ли она как O (n ^ 2 * d)? Как оно масштабируется, если я хочу найти решение с помощью точного решения Гаусса-Маркова по сравнению с численным методом наименьших квадратов методом Ньютона? Или просто получить решение против использования значимых тестов?

Я думаю, что мне больше нужен хороший источник ответов (например, статья, в которой обобщается масштабирование различных статистических методов), чем хороший ответ здесь. Как, скажем, список, который включает масштабирование множественной регрессии, логистической регрессии, PCA, регрессии пропорционального риска Кокса, кластеризации K-средних и т. Д.

Bridgeburners
источник
Это хороший вопрос. Многие книги по статистике говорят о теоретических аспектах многомерных данных, а не о вычислительных аспектах.
Shadowtalker
Во многих случаях в оригинальной литературе будут обсуждаться сложности. Но зачастую теоретическая сложность бесполезна. QuickSort имеет наихудший случай O (n ^ 2), но часто самый быстрый - быстрее, чем HeapSort, который имеет наихудший случай O (n log n). Если вы проведете небольшое исследование, вы найдете результаты сложности для многих алгоритмов - если известны. Например , PCA является O (й ^ 3), к-значит быть O (НКИД) и т.д.
Имеет QUIT - Anony-мусс

Ответы:

6

Большинство эффективных (и не тривиальных) статистических алгоритмов по своей природе итеративны, поэтому анализ наихудшего случая не O()имеет значения, так как наихудший случай - «он не сходится».

Тем не менее, когда у вас много данных, даже линейные алгоритмы ( O(n)) могут быть медленными, и вам нужно сосредоточиться на постоянной «скрытой» за нотацией. Например, вычисление дисперсии одного варианта наивно выполняется путем сканирования данных дважды (один раз для вычисления оценки среднего, а затем один раз для оценки дисперсии). Но это также можно сделать за один проход .

Для итерационных алгоритмов, что более важно, это скорость сходимости и количество параметров как функция размерности данных, элемент, который сильно влияет на сходимость. Многие модели / алгоритмы увеличивают количество параметров, которое экспоненциально зависит от количества переменных (например, сплайнов), в то время как некоторые другие растут линейно (например, машины опорных векторов, случайные леса, ...)

damienfrancois
источник
Я не уверен, что согласен с этим: при разработке алгоритма для статистической задачи большое внимание уделяется сложности каждого итерационного шага (и обычно это документируется в рукописи). Но, как вы указываете, часто это не так просто подвести итог, так как два алгоритма с одинаковой сложностью на одну итерацию могут работать очень по-разному из-за необходимых итераций. При этом очень редко число требуемых итераций растет быстрее, чем O(log(n) ).
Клифф AB
5

Вы упомянули регрессию и PCA в названии, и для каждого из них есть определенный ответ.

Асимптотическая сложность линейной регрессии сводится к O (P ^ 2 * N), если N> P, где P - число признаков, а N - количество наблюдений. Подробнее о сложности вычисления операции наименьших квадратов .

Vanilla PCA - это O (P ^ 2 * N + P ^ 3), как в алгоритме Fastest PCA для многомерных данных . Однако существуют быстрые алгоритмы для очень больших матриц, объясненные в этом ответе и « Лучший алгоритм PCA для огромного числа функций?» ,

Однако я не думаю, что кто-то составил один освещенный обзор или справочник или книгу по этому вопросу. Не может быть плохим проектом для моего свободного времени ...

shadowtalker
источник
Спасибо, это очень полезно! Если вы сделаете обзор литературы по различным методам прогнозного моделирования, я уверен, что на него будут ссылаться много. Это было бы очень полезно для людей, которые хотят различать, какие алгоритмы использовать в больших n или больших p случаях, или для средних значений из них для более точных вычислений. Вы случайно не знаете, как масштабируются некоторые из самых непонятных техник? (Например, пропорциональная регрессия рисков Кокса или подтверждающий факторный анализ)
Бриджбернерс
К сожалению, нет, но если я когда-нибудь сделаю этот обзор, я постараюсь быть всеобъемлющим. Я бы вряд ли назвал регрессию Кокса «неясной», по крайней мере, в своей области.
Shadowtalker
5

Я дал очень ограниченный частичный ответ для пакета подтверждающего факторного анализа, который я разработал для Stata в этой статье в Stata Journal, основываясь на времени фактического моделирования. Подтверждающий факторный анализ был реализован как метод оценки максимального правдоподобия, и я очень легко видел, как время вычисления росло с каждым измерением (размер выборки n, количество переменных p, количество факторов k). Поскольку это сильно зависит от того, как Stata думает о данных (оптимизированных для вычисления по столбцам / наблюдениям, а не по строкам), я обнаружил, что производительностьO(n^{0.68} (k+p)^{2.4})где 2.4 - самая быстрая асимптотика обращения матриц (и это чертовски много в итеративном максимизации подтверждающего факторного анализа). Я не дал ссылку на последнее, но я думаю, что я получил это из Википедии .

X'X108

Stask
источник
2
Математическое форматирование не работает на DataScience? В самом деле? Может быть, мы должны попросить его получить.
СтасК
Хороший вопрос о точности чисел.
теневик