Algoritma apa yang digunakan dalam regresi linier?

Saya biasanya mendengar tentang "kotak paling tidak biasa". Apakah itu algoritma yang paling banyak digunakan digunakan untuk regresi linier? Apakah ada alasan untuk menggunakan yang berbeda?

Mengenai pertanyaan pada judul, tentang apa algoritma yang digunakan:

Dalam perspektif aljabar linier, algoritma regresi linier adalah cara untuk menyelesaikan sistem linear dengan lebih banyak persamaan daripada yang tidak diketahui. Dalam sebagian besar kasus tidak ada solusi untuk masalah ini. Dan ini karena vektor tidak termasuk dalam ruang kolom , .$\mathbf{A}x=b$$b$$\mathbf{A}$$C(\mathbf{A})$

Ini best straight lineadalah salah satu yang membuat kesalahan keseluruhan sekecil yang diperlukan. Dan nyaman untuk berpikir kecil sebagai panjang kuadrat, , karena itu tidak negatif, dan sama dengan 0 hanya ketika b \ dalam C (\ mathbf {A}) .$e=\mathbf{A}x-b$$\lVert e \rVert^2$$b\in C(\mathbf{A})$

Memproyeksikan (secara orthogonal) vektor ke titik terdekat dalam ruang kolom memberikan vektor yang memecahkan sistem (komponennya terletak pada garis lurus terbaik) dengan kesalahan minimum.$b$$\mathbf{A}$$b^*$

$\mathbf{A}^T\mathbf{A}\hat{x}=\mathbf{A}^Tb \Rightarrow \hat{x}=(\mathbf{A}^T\mathbf{A})^{-1}\mathbf{A}^Tb$

dan vektor yang diproyeksikan diberikan oleh:$b^*$

$b^*=\mathbf{A}\hat{x}=\mathbf{A}(\mathbf{A}^T\mathbf{A})^{-1}\mathbf{A}^Tb$

Mungkin metode kuadrat terkecil tidak secara eksklusif digunakan karena squaring kelebihan kompensasi untuk pencilan.

Biarkan saya memberikan contoh sederhana dalam R, yang memecahkan masalah regresi menggunakan algoritma ini:

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])

Untuk menjawab surat pertanyaan, "kuadrat terkecil" bukan merupakan algoritma; melainkan merupakan jenis masalah dalam aljabar linear komputasi, yang salah satu contohnya adalah regresi linier. Biasanya seseorang memiliki data dan fungsi sementara ("model") agar sesuai dengan data, dari bentuk . The disebut "fungsi dasar" dan dapat berupa apa saja dari monomial hingga fungsi trigonometrik (misalnya , ) dan fungsi eksponensial ( ). Istilah "linear" dalam "regresi linier" di sini tidak merujuk pada fungsi dasar,$\{(x_1,y_1),\dots,(x_m,y_m)\}$$f(x)=c_1 f_1(x)+\dots+c_n f_n(x)$$f_j(x)$$x^j$$\sin(jx)$$\cos(jx)$$\exp(-jx)$$c_j$, dalam mengambil turunan parsial model sehubungan dengan salah satu dari memberi Anda faktor mengalikan ; yaitu, .$c_j$$c_j$$f_j(x)$

Satu sekarang memiliki matriks persegi panjang ("matriks desain") yang (biasanya) memiliki lebih banyak baris daripada kolom, dan setiap entri berbentuk , menjadi indeks baris dan menjadi indeks kolom. OLS sekarang tugas untuk menemukan vektor yang meminimalkan kuantitas (dalam notasi matriks, ; di sini, biasanya disebut "vektor respons").$m\times n$$\mathbf A$$f_j(x_i)$$i$$j$$\mathbf c=(c_1\,\dots\,c_n)^\top$$\sqrt{\sum\limits_{j=1}^{m}\left(y_j-f(x_j)\right)^2}$$\|\mathbf{A}\mathbf{c}-\mathbf{y}\|_2$$\mathbf{y}=(y_1\,\dots\,y_m)^\top$

Setidaknya ada tiga metode yang digunakan dalam praktik untuk menghitung solusi kuadrat-terkecil: persamaan normal, dekomposisi QR, dan dekomposisi nilai singular. Secara singkat, mereka adalah cara untuk mengubah matriks menjadi produk dari matriks yang mudah dimanipulasi untuk memecahkan untuk vektor .$\mathbf{A}$$\mathbf{c}$

George sudah menunjukkan metode persamaan normal dalam jawabannya; satu hanya memecahkan set persamaan linear$n\times n$

$\mathbf{A}^\top\mathbf{A}\mathbf{c}=\mathbf{A}^\top\mathbf{y}$

untuk . Karena kenyataan bahwa matriks adalah simetris positif (semi) pasti, metode yang biasa digunakan untuk ini adalah dekomposisi Cholesky, yang merupakan faktor ke dalam formulir , dengan matriks segitiga lebih rendah. Masalah dengan pendekatan ini, terlepas dari keuntungan karena dapat mengompres matriks desain menjadi matriks (biasanya) jauh lebih kecil matriks, adalah bahwa operasi ini rentan terhadap kehilangan angka-angka signifikan (ini memiliki sesuatu untuk lakukan dengan "nomor kondisi" dari matriks desain).$\mathbf{c}$$\mathbf{A}^\top\mathbf{A}$$\mathbf{A}^\top\mathbf{A}$$\mathbf{G}\mathbf{G}^\top$$\mathbf{G}$$m\times n$$n\times n$

Cara yang sedikit lebih baik adalah dekomposisi QR, yang langsung bekerja dengan matriks desain. Itu faktor sebagai , di mana adalah matriks ortogonal (mengalikan matriks tersebut dengan transposnya memberikan matriks identitas) dan adalah segitiga atas. selanjutnya dihitung sebagai . Untuk alasan saya tidak akan masuk (hanya melihat teks aljabar linear numerik yang layak, seperti ini ), ini memiliki sifat numerik yang lebih baik daripada metode persamaan normal.$\mathbf{A}$$\mathbf{A}=\mathbf{Q}\mathbf{R}$$\mathbf{Q}$$\mathbf{R}$$\mathbf{c}$$\mathbf{R}^{-1}\mathbf{Q}^\top\mathbf{y}$

Salah satu variasi dalam menggunakan dekomposisi QR adalah metode persamaan seminormal . Secara singkat, jika seseorang memiliki dekomposisi , sistem linear yang harus dipecahkan mengambil bentuk$\mathbf{A}=\mathbf{Q}\mathbf{R}$

Secara efektif, seseorang menggunakan dekomposisi QR untuk membentuk segitiga Cholesky dari dalam pendekatan ini. Ini berguna untuk kasus di mana jarang, dan penyimpanan eksplisit dan / atau pembentukan (atau versi yang difaktorkan) tidak diinginkan atau tidak praktis.$\mathbf{A}^\top\mathbf{A}$$\mathbf{A}$$\mathbf{Q}$

Akhirnya, cara memecahkan OLS yang paling mahal, namun paling aman adalah dekomposisi nilai singular (SVD). Kali ini, diperhitungkan sebagai , di mana dan keduanya ortogonal , dan$\mathbf{A}$$\mathbf{A}=\mathbf{U}\mathbf \Sigma\mathbf{V}^\top$$\mathbf{U}$$\mathbf{V}$$\mathbf{\Sigma}$adalah matriks diagonal, yang entri diagonalnya disebut "nilai singular". Kekuatan dekomposisi ini terletak pada kemampuan diagnostik yang diberikan kepada Anda oleh nilai-nilai singular, di mana jika seseorang melihat satu atau lebih nilai-nilai singular kecil, maka kemungkinan Anda telah memilih set basis yang tidak sepenuhnya independen, sehingga memerlukan reformulasi model Anda. ("Angka kondisi" yang disebutkan sebelumnya sebenarnya terkait dengan rasio nilai singular terbesar dengan yang terkecil; rasio tentu saja menjadi besar (dan matriksnya dengan demikian tidak terkondisi) jika nilai singular terkecil adalah "kecil" .)

Ini hanyalah sketsa dari ketiga algoritma ini; buku bagus apa pun tentang statistik komputasi dan aljabar linear numerik harus dapat memberi Anda detail yang lebih relevan.

Tautan wiki: Metode Estimasi untuk Regresi Linier memberikan daftar metode estimasi yang cukup komprehensif termasuk OLS dan konteks di mana metode estimasi alternatif digunakan.

Sangat mudah untuk bingung antara definisi dan terminologi. Kedua istilah tersebut digunakan, terkadang secara bergantian. Pencarian cepat di Wikipedia akan membantu:

• kotak terkecil biasa
• dekat regresi

Ordinary Least Squares (OLS) adalah metode yang digunakan untuk menyesuaikan model regresi linier. Karena konsistensi dan efisiensi yang dapat dibuktikan (dengan asumsi tambahan) dari metode OLS, itu adalah pendekatan yang dominan. Lihat artikel untuk petunjuk lebih lanjut.

Saya cenderung menganggap 'kuadrat terkecil' sebagai kriteria untuk menentukan garis regresi pas terbaik (yaitu, yang membuat jumlah dari 'kuadrat' residu 'paling sedikit') dan 'algoritma' dalam konteks ini sebagai serangkaian langkah yang digunakan untuk menentukan koefisien regresi yang memenuhi kriteria itu. Perbedaan ini menunjukkan bahwa dimungkinkan untuk memiliki algoritma yang berbeda yang akan memenuhi kriteria yang sama.

Saya ingin tahu apakah orang lain membuat perbedaan ini dan terminologi apa yang mereka gunakan.

Sebuah buku tua, namun saya menemukan diri saya berulang kali beralih ke, adalah

Lawson, CL dan Hanson, RJ Memecahkan Masalah Kuadrat Terkecil , Prentice-Hall, 1974.

Ini berisi diskusi terinci dan sangat mudah dibaca dari beberapa algoritma yang telah disebutkan sebelumnya. Anda mungkin ingin melihatnya.