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

42

Я обычно слышу о "обычных наименьших квадратах". Это наиболее широко используемый алгоритм, используемый для линейной регрессии? Есть ли причины использовать другой?

Belmont
источник
@hxd, за исключением какой-либо специальной структуры в матрице проектирования, это все алгоритмы , отличающиеся только постоянным множителем. Декомпозиционный подход - это хорошая привычка, унаследованная от традиции числовой линейной алгебры. O(mn2)
JM не является статистиком
@hxd, и именно поэтому мой ответ был составлен так, чтобы представлять собой описание используемых алгоритмов. Если у вас есть вопросы, не охваченные этой веткой, подумайте над тем, чтобы задать новый вопрос.
JM не является статистиком

Ответы:

32

Что касается вопроса в заголовке, о том, какой алгоритм используется:

В перспективе линейной алгебры алгоритм линейной регрессии - это способ решения линейной системы с большим количеством уравнений, чем неизвестных. В большинстве случаев нет решения этой проблемы. И это потому, что вектор не принадлежит пространству столбцов , .Ax=bbAC(A)

Это best straight lineта, которая делает общую ошибку настолько маленькой, насколько это необходимо. И удобно считать малой квадратичную длину , потому что она неотрицательна и равна 0 только тогда, когда b \ in C (\ mathbf {A}) .e=Axbe2bC(A)

Проецирование (ортогонально) вектора на ближайшую точку в пространстве столбцов дает вектор который решает систему (ее компоненты лежат на лучшей прямой линии) с минимальной ошибкой.bAb

ATAx^=ATbx^=(ATA)1ATb

и спроецированный вектор определяется как:b

b=Ax^=A(ATA)1ATb

Возможно, метод наименьших квадратов не используется исключительно, потому что он squaring компенсирует выбросы.

Позвольте мне привести простой пример в R, который решает проблему регрессии с помощью этого алгоритма:

library(fBasics)

reg.data <- read.table(textConnection("
   b      x
  12      0
  10      1
   8      2
  11      3
   6      4
   7      5
   2      6
   3      7
   3      8 "), header = T)

attach(reg.data)

A <- model.matrix(b~x)

# intercept and slope
inv(t(A) %*% A) %*% t(A) %*% b

# fitted values - the projected vector b in the C(A)
A %*% inv(t(A) %*%A ) %*% t(A) %*% b

# The projection is easier if the orthogonal matrix Q is used, 
# because t(Q)%*%Q = I
Q <- qr.Q(qr(A))
R <- qr.R(qr(A))

# intercept and slope 
best.line <- inv(R) %*% t(Q) %*% b

# fitted values 
Q %*% t(Q) %*% b

plot(x,b,pch=16)
abline(best.line[1],best.line[2])
Джордж Донтас
источник
Я получаю ошибку could not find inv?!
HHH
1
Загрузите пакет fBasics. finzi.psych.upenn.edu/R/library/fBasics/html/matrix-inv.html
Джордж Донтас
5
Есть ли причина для использования inv от fBasics, когда это просто синоним решения? Не лучше ли для ответа не требовать зависимости от внешних пакетов, если в этом нет необходимости?
Дейсон
@ Джордж Я люблю четкий ответ, однако, я думаю, что первоначальный вопрос задавал алгоритмы, и QR - только один из них. Как насчет ЛУ, СВД, разложения Холецкого? Кроме того, в R, метод для lmQR, есть причины для этого, не могли бы вы объяснить, почему?
Haitao Du
@ GeorgeDontas Обратите внимание, что, возможно, не обратим. Как объясняется в этом ответе , один из способов справиться с этим - удалить из столбцов линейные комбинации других столбцов. ATAA
Орен Мильман
70

Чтобы ответить на вопрос, «обычные наименьшие квадраты» не алгоритм; скорее это тип проблемы в вычислительной линейной алгебре, одним из примеров которой является линейная регрессия. Обычно каждый имеет данные и предварительную функцию («модель») для сопоставления данных в форме . называются "базисными функциями" и может быть что угодно , от одночленов для тригонометрических функций (например , ) и экспоненциальной функции ( ). Термин «линейный» в «линейной регрессии» здесь не относится к базисным функциям,{(x1,y1),,(xm,ym)}f(x)=c1f1(x)++cnfn(x)fj(x)xjsin(jx)cos(jx)exp(jx)cjв том, что взятие частной производной модели по любому из дает вам множитель ; то есть .cjcjfj(x)

Теперь у каждого есть прямоугольная матрица («матрица дизайна»), которая (обычно) имеет больше строк, чем столбцов, и каждая запись имеет форму , где - индекс строки, а - индекс индекс столбца. Задачей OLS теперь является поиск вектора который минимизирует количество (в матричной записи, ; здесь, обычно называется "вектором ответа").m×nAfj(xi)ijc=(c1cn)j=1m(yjf(xj))2Acy2y=(y1ym)

На практике для вычисления решений методом наименьших квадратов используются как минимум три метода: нормальные уравнения, QR-разложение и разложение по сингулярным числам. Вкратце, это способы преобразования матрицы в произведение матриц, которыми легко манипулировать, чтобы найти вектор .Ac

Джордж уже показал метод нормальных уравнений в своем ответе; можно просто решить систем линейных уравненийn×n

AAc=Ay

для . В связи с тем, что матрица является симметричной положительной (полу) определенной, для этого используется обычный метод разложения Холецкого, который учитывает в форму , с нижней треугольной матрицей. Проблема этого подхода, несмотря на то, что преимущество заключается в возможности сжать матрицу в (обычно) гораздо меньшую матрицу, состоит в том, что эта операция склонна к потере значительных цифр (в этом есть делать с «номером условия» матрицы проектирования).cAAAAGGGm×nn×n

Немного лучшим способом является декомпозиция QR, которая напрямую работает с матрицей дизайна. Он учитывает как , где - ортогональная матрица (умножение такой матрицы на ее транспонирование дает единичную матрицу) и является верхним треугольником. впоследствии вычисляется как . По причинам, в которые я не буду вдаваться (просто посмотрите любой текст приличной числовой линейной алгебры, как этот ), он обладает лучшими числовыми свойствами, чем метод нормальных уравнений.AA=QRQRcR1Qy

Одним из вариантов использования QR-разложения является метод полунормальных уравнений . Вкратце, если разложение имеет , линейная система, которая должна быть решена, принимает видA=QR

RRc=Ay

По сути, в этом подходе используется разложение QR для формирования треугольника Холецкого из . Это полезно для случая, когда является разреженным, и явное хранение и / или формирование (или его факторизованной версии) нежелательно или нецелесообразно.AAAQ

Наконец, самый дорогой, но самый безопасный способ решения OLS - это разложение по сингулярным числам (SVD). На этот раз учитывается как , где и являются ортогональными иAA=UΣVUVΣявляется диагональной матрицей, диагональные элементы которой называются «сингулярными значениями». Сила этого разложения заключается в диагностической способности, предоставленной вам единичными значениями, в том, что если вы видите одно или несколько крошечных единичных значений, то, вероятно, вы выбрали не совсем независимый базисный набор, что потребует переформулировки твоя модель («Условное число», упомянутое ранее, на самом деле связано с отношением наибольшего единственного значения к наименьшему; отношение, конечно, становится огромным (и матрица, таким образом, плохо обусловлена), если наименьшее единственное значение является «крошечным»). .)

Это просто набросок этих трех алгоритмов; любая хорошая книга по вычислительной статистике и числовой линейной алгебре должна быть в состоянии дать вам более важные детали.

JM не является статистиком
источник
3
Хорошее объяснение!
Майк Спиви
Как вы рассчитываете, R^{-1} Q^T yесли A не квадрат? Вы отбрасываете нулевые строки в R?
бхан
1
@bhan, я предполагаю «экономный» (или «тонкий») вариант QR-разложения, где - квадрат, а - те же размеры, что и матрица дизайна. Что-то для вас: посмотрите разницу между «полным QR» и «тонким QR». RQ
JM не является статистиком
@JM какие-нибудь рекомендации по "хорошей книге по вычислительной статистике и числовой линейной алгебре"? очень хочу узнать больше.
Haitao Du
1
@hxd, вне головы: Монахан для вычислительной статистики и Голуб / Ван Лоан для числовой линейной алгебры.
JM не статистика
6

Ссылка на вики: Методы оценки для линейной регрессии дает довольно полный список методов оценки, включая МНК и контексты, в которых используются альтернативные методы оценки.

user603
источник
1
Не отвечает на вопрос (на странице даже не упоминается QR)
user603
4

Легко запутаться между определениями и терминологией. Оба термина используются, иногда взаимозаменяемо. Быстрый поиск в Википедии должен помочь:

Обычные наименьшие квадраты (OLS) - это метод, используемый для подбора моделей линейной регрессии. Из-за очевидной последовательности и эффективности (при дополнительных допущениях) метода OLS это доминирующий подход. Смотрите статьи для дальнейшего ведет.

Дирк Эддельбюттель
источник
Правильно, именно поэтому я считаю OLS «алгоритмом», используемым в линейной регрессии ...
Belmont,
3
Обычные наименьшие квадраты - это оценка. Существует множество алгоритмов для вычисления оценки: обычно используется некоторый вид разложения ортогональной матрицы, такой как QR. См. En.wikipedia.org/wiki/…
Саймон Бирн
4

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

Мне было бы интересно узнать, делают ли другие это различие и какую терминологию они используют.

Джером англим
источник
Под алгоритмом я имею в виду примерно программную реализацию, используемую для подгонки линии для моделирования среднего распределения.
Belmont
3

Старая книга, к которой я постоянно обращаюсь,

Лоусон, CL и Хансон, Р. Дж. Решение проблем наименьших квадратов , Прентис-Холл, 1974.

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

Ф. Туселл
источник
1
Если вы читаете эту старую книгу, вам также следует изучить Численные методы Аке Бьорка для задач наименьших квадратов , в которых есть вещи, которые не обсуждались в работе Лоусона / Хансона. Процедуры, включенные в книгу Лоусона / Хансона, доступны в Netlib .
JM не является статистиком