Metode Least Square

Dipublikasi: September 13th, 2021

Pernah gak nemuin masalah, di mana suku persamaannya lebih sedikit ketimbang informasi pasangan (x, y)-nya?

Memang awalnya terlihat aneh, tapi semua ini mampu diselesaikan kok menggunakan metode least square.

Daftar Isi

Least Square
- Tolak Ukur Hasil Estimasinya
Meminimalisir Error
Penerapan Least Square

Least Square

Intinya, apa yang bakal kita lakukan di sini adalah melakukan estimasi terhadap keseluruhan hasil pemetaan garis/fungsi lainnya.

Jadi dengan metode least square, sulit banget didapat model persamaan yang sama persis karakteristiknya sesuai persebaran datanya.

Maksudnya, apabila variabel dari persamaannya disubstitusikan oleh pasangannya (misal x-nya), nilai y-nya belum tentu sama seperti data aslinya.

Berbeda cerita kalau emang hanya terdapat dua data (dua pasangan titik x, y). Kalau kasusnya ini gak perlu pakai least square kayaknya deh.

Kenapa sampai ada cara khusus untuk menyelesaikan masalah ini, alasan utamanya adalah kita gak bisa langsung menyelesaikannya dengan Ax = b.

Inget lagi, salah satu alternatif penyelesaian masalah itu dapat diselesaikan dengan x = A^-1b.

Tapi mengingat matriks A-nya bukanlah matriks persegi (jumlah baris dan kolomnya sama), mau dicari inversnya melalui cara apapun tentu gak mungkin.

Contoh sederhananya, asumsikan terdapat tiga titik (2,0), (3,1), (4,3), lalu ingin dimodelkan menggunakan persamaan linear l = Mk + N.

Jika diekspresikan ke dalam matriks, kurang lebih seperti ini:

$\begin{align*}M\cdot2 + N &= 0\\M\cdot3 + N &= 1\\M\cdot4 + N &= 3\end{align*}$

$\begin{bmatrix}2&&1\\3&&1\\4&&1\end{bmatrix}\begin{bmatrix}M\\N\end{bmatrix}=\begin{bmatrix}0\\1\\3\end{bmatrix}\quad \text{(I)}$

Dari situ jelas, bahwa cara eleminasi biasa atau invers belum mampu mencari "solusinya". Biar lebih gampang kita gantikan dengan variabel:

$Ax=b$

Tolak Ukur Hasil Estimasinya

Ide penyelesaiannya yakni dengan meminimalisir error terhadap hasil pasangan yang dihasilkan oleh hasil prediksi persamaannya.

Misalnya diperoleh estimasi persamaannya l = Mk + N, terus titiknya (x,y). Error-nya yaitu hasil estimasinya l̂_i (ada tanda topinya) dengan aslinya y_i:

$e_i = \hat l_i - y_i$

Rumus tersebut dapat diartikan juga kalau ukurannya adalah jarak vertikal antara data asli dengan hasil estimasi.

Sehubung kita harus meminimalisir error secara keseluruhan, gak hanya terhadap satu titik saja, maka digunakan ekspresi matriks menjadi:

$e = \hat l - b$

Cuman sekarang yang jadi pertanyaan, itu kan bentuknya matriks, nah kita butuh suatu "ukuran" yang menyatakan "besar" matriks error itu.

Dalam matriks, besarannya bisa dinyatakan dalam norm. Kalian sudah pada tahu kan, pada sebuah vektor (v) panjangnya bisa diukur oleh:

$\|v\|^2 = x_1^2 + x_2^2 +\cdots+x_n^2$

Nah ukuran itu merupakan salah satu jenis norm, yakni norm-2. Kali ini, norm-2 tersebut bakal digunakan sebagai ukuran besar-kecilnya error.

Meminimalisir Error

Supaya lebih gampang, error terhadap hasil estimasi dengan nilai aslinya diukur dapat dibayangin menggunakan bantuan geometri.

Ibaratnya ada sebuah titik dan garis, jarak antara keduanya lah merupakan nilai error yang perlu diperkecil.

Sehingga objektif utama dalam permasalahan least square yaitu meminimalisir besar (norm-2) vektor error-nya.

Caranya yakni dengan mencari nilai koefisien M dan konstanta N, sehingga:

$\min\limits_{M,N} \|e\|^2$

Misalkan estimasi M; dan N terbaiknya diwakili oleh vektor sebut saja x̂:

$\hat x = \begin{bmatrix}M\\N\end{bmatrix}$

Demikian, vektor error-nya menjadi:

$\begin{align*}e &=\hat l-b \\ &= A\hat x-b\\ &=\begin{bmatrix}Mx_1 + N - y_1\\Mx_2 + N - y_2\\ \vdots\\Mx_2 + N - y_n\end{bmatrix}\end{align*}$

Pendekatan Kalkulus

Bila dianggap ukuran error-nya ialah sebuah fungsi, maka alternatifnya bisa diselesaikan menggunakan kalkulus, yakni turunan.

Sebuah fungsi akan bernilai optimal saat turunannya bernilai nol, konsep nilai optimal ini bakal kita gunakan sekarang.

Norm dari vektor di atas ini yaitu:

$\|e\|^2 = (Mx_1 + N - y_1)^2 + (Mx_2 + N - y_2)^2 +\cdots+(Mx_n + N - y_n)^2$

Mengingat variabelnya gak cuman satu, maka yang dilakukan adalah turunan parsial. Sehingga, diturunkan ekspresinya terhadap M dan N secara terpisah.

$\frac{\delta \|e\|^2}{\delta M} = 2x_1(Mx_1 + N - y_1) + 2x_2(Mx_2 + N - y_2)+\cdots+2x_n(Mx_n + N - y_n) = 0$

$\frac{\delta \|e\|^2}{\delta N} = 2(Mx_1 + N - y_1) + 2(Mx_2 + N - y_2)+\cdots+2(Mx_n + N - y_n) = 0$

Sekarang, langsung dicoba aja contoh sebelum-sebelumnya. Tiga titik tersebut apabila disubstitusikan, besar error-nya:

$\|e\|^2 = (M(2) + N - 0)^2+(M(3) + N - 1)^2+(M(4) + N - 3)^2\quad \text{(II)}$

Kedua turunan parsialnya:

$\frac{\delta \|e\|^2}{\delta M} = 2(2)(M(2) + N - 0) + 2(3)(M(3) + N - 1)+2(4)(M(4) + N - 3) = 0$

$\frac{\delta \|e\|^2}{\delta N} = 2(M(2) + N - 0)+2(M(3) + N - 1)+2(M(4) + N - 3) = 0$

Setelah itu, kedua nilai tersebut ditentukan dengan melakukan eleminasi terhadap kedua persamaan yang didapat. Hasilnya:

$\begin{align*}M&=1.5\\N&=-3.166668\end{align*}$

Pendekatan Aljabar Linear

Alternatif lainnya, bisa dimanfaatkan prinsip aljabar linear guna mencari persamaannya. Bisa dibayangkan sebagai proses proyeksi.

Di sini, vektor yang ingin diproyeksikan adalah b. Tapi saat ini bukan sekedar memproyeksikan kepada vektor lainnya, tapi kepada sebuah ruang vektor, berupa matriks.

Maksudnya, sebuah matriks itu bisa diibaratkan sekumpulan vektor, yang jika dikombinasi linearkan, menghasilkan sebuah himpunan vektor.

Maka dari itu, error yang dimaksud haruslah tegak lurus terhadap ruang tersebut. Karena ingin dicari "jarak" terpendeknya.

Sehingga perkalian dot antara keduanya bernilai nol:

$\begin{align*}A\cdot e &= 0\\ A\cdot (A\hat x - b) &= 0\\ A\cdot A \hat x - A\cdot b & = 0\\\hat x &= (A^TA)^{-1}A^Tb\end{align*}$

Catatan: Ingat! Perkalian dot, a·b setara dengan a^Tb.

Perlu diamati juga, kalau A^TA menghasilkan matriks persegi. Kemudian, selagi vektor kolom penyusun matriksnya saling independent, A^TA bersifat invertible (mampu diinvers).

Buat contoh, kita pakai lagi titik-titik sebelumnya. Mengacu ke persamaan (I), demikian diketahui matriks A dan vektor b:

$\begin{align*}A &= \begin{bmatrix}2&&1\\3&&1\\4&&1\end{bmatrix}\\b &= \begin{bmatrix}0\\1\\3\end{bmatrix}\end{align*}$

Hitung dahulu, matriks-matriks yang dibutuhkan:

$\begin{align*}A^T &=\begin{bmatrix}2&&3&&4\\1&&1&&1\end{bmatrix}\\A^T A &=\begin{bmatrix}29&&9\\9&&3\end{bmatrix}\\ (A^T A)^{-1} &= \begin{bmatrix}0.5&&-1.5\\-1.5&&4.83333\end{bmatrix}\end{align*}$

Langsung aja dipakai rumus yang sudah diperoleh, didapat:

$\hat x =\begin{bmatrix}M\\N\end{bmatrix} = \begin{bmatrix}0.5&&-1.5\\-1.5&&4.83333\end{bmatrix}\begin{bmatrix}2&&3&&4\\1&&1&&1\end{bmatrix}\begin{bmatrix}0\\1\\3\end{bmatrix}$

$\begin{bmatrix}M\\N\end{bmatrix} = \begin{bmatrix}0.5&&-1.5\\-1.5&&4.83333\end{bmatrix}\begin{bmatrix}2&&3&&4\\1&&1&&1\end{bmatrix}\begin{bmatrix}0\\1\\3\end{bmatrix}$

$\begin{bmatrix}M\\N\end{bmatrix} = \begin{bmatrix}1.5\\-3.166668\end{bmatrix}$

Bisa dilihat juga kalau hasilnya sama seperti menggunakan turunan. Sehingga, persamaan garis yang paling cocok mewakili ketiga titik tersebut adalah:

$y = 1.5x - 3.166668$

Setelah diketahui persamaannya, sekarang kita dapat mengetahui seberapa melenceng garis tersebut terhadap data aslinya.

Tinggal menghitung ||e|| dari persamaan (II):

$\|e\|= 0.408248291$

Apa jadinya apabila error-nya bernilai nol? Jika situasi ini terjadi, artinya persamaan tersebut secara tepat melalui titik-titiknya. Bisa dikatakan bahwa itulah persamaan sesungguhnya.

Apabila garisnya digambar, maka akan seperti ini wujudnya:

Dapat disimpulkan kalau garis dengan error yang kecil bukan berarti harus tepat melalui satu atau dua titiknya. Tapi lebih ke jarak terhadap titiknya secara keseluruhan.

Bisakah persamaan yang didapat bener-bener sesuai dengan titik-titiknya? Di beberapa kondisi sangat bisa.

Tetapi biasanya gak cukup kalau hanya persamaan linear. Umumnya dipakai bentuk yang pangkatnya lebih tinggi (polinomial).

Tapi kalau memang datanya sudah gak mampu dimodelin pakai polinomial, inilah kendalanya. Jika sebatas 2 hingga 3 data, masih bisa didapat persamaan aslinya.

Cara pengerjaannya sendiri bakal tetap sama, cuman nanti nambah variabel yang dicarinya. Gak cuman M sama N aja.

Data Penyebab Matriks Singular

Sebelumnya kalian telah melihat terlibatnya operasi invers saat mencari solusinya. Masih ingat kan kalau invers ini ada aturannya.

Aturan pertama harus matriks persegi, yakni ordonya NxN, alias jumlah kolom dan barisnya sama.

Pada metode least square, hal itu dapat terjadi apabila terdapat dua hasil pemetaan berbeda (y) berasal dari input (x) yang sama.

Sebab matriks baris penyusun A tidak saling independent, alhasil matriks A^TA menjadi singular.

Penerapan Least Square

Pokoknya segala macam permasalahan mengenai fitting data itu bisa digunakan least square.

Setelah modelnya diperoleh, persamaannya dapat digunakan untuk memprediksi data selanjutnya.

Beberapa bidang yang menggunakan metode least square:

Ekonomi
Robotika
Statistika
Meteorologi

Least square ini juga merupakan dasar dari kecerdasan buatan. Konsepnya sama-sama mencari koefisien dari sebuah sistem yang perilakunya mirip seperti datanya.

Kalau pengalaman saya dulu ngebikin program untuk prediksi arah bolah pakai metode ini, suku paling tinggi persamaan berpangkat dua.

Bola yang terdeteksi oleh robot saya sampling sesuai frame rate program deteksi bolanya.

Saya pakai beberapa sampel supaya lebih akurat, sekitar 6 sampai 10. Karena itu prediksinya dilakukan setiap 6 sampai 10 iterasi sekali.

Implementasinya programnya silahkan kalian lihat di video berikut: