Sumber:
Regresi linier adalah salah satu algoritma dasar untuk banyak bidang yang berkaitan dengan analisis data. Alasannya jelas. Ini adalah algoritme yang sangat sederhana dan mudah dipahami, yang telah berkontribusi pada penggunaannya secara luas selama puluhan, bahkan ratusan tahun. Idenya adalah kita mengasumsikan ketergantungan linier dari satu variabel pada sekumpulan variabel lain, dan kemudian mencoba memulihkan ketergantungan ini.
Namun artikel ini bukan tentang penggunaan regresi linier untuk memecahkan masalah praktis. Di sini kita akan mempertimbangkan fitur menarik dari implementasi algoritma terdistribusi untuk pemulihannya, yang kita temui saat menulis modul pembelajaran mesin . Sedikit matematika dasar, pembelajaran mesin, dan komputasi terdistribusi dapat membantu Anda mengetahui cara melakukan regresi linier bahkan ketika data Anda didistribusikan ke ribuan node.
Apa yang kita bicarakan?
Kita dihadapkan pada tugas memulihkan ketergantungan linier. Sebagai data masukan, diberikan sekumpulan vektor variabel bebas, yang masing-masing dikaitkan dengan nilai tertentu dari variabel terikat. Data ini dapat direpresentasikan dalam bentuk dua matriks:
Sekarang, karena ketergantungan diasumsikan, dan terlebih lagi linier, kita akan menuliskan asumsi kita sebagai hasil kali matriks (untuk menyederhanakan pencatatan, di sini dan di bawah ini diasumsikan bahwa suku bebas persamaan tersebut tersembunyi di balik , dan kolom terakhir matriks berisi satuan):
Kedengarannya sangat mirip dengan sistem persamaan linear, bukan? Tampaknya, kemungkinan besar, tidak akan ada solusi untuk sistem persamaan seperti itu. Alasannya adalah noise, yang terdapat di hampir semua data nyata. Alasan lain mungkin adalah kurangnya ketergantungan linier, yang dapat diatasi dengan memasukkan variabel tambahan yang bergantung secara nonlinier pada variabel asli. Perhatikan contoh berikut:
Sumber:
Ini adalah contoh sederhana regresi linier yang menunjukkan hubungan suatu variabel (sepanjang sumbu ) dari variabel lain (sepanjang sumbu ). Agar sistem persamaan linier yang sesuai dengan contoh ini mempunyai penyelesaian, semua titik harus terletak tepat pada garis lurus yang sama. Tapi itu tidak benar. Namun keduanya tidak terletak pada garis lurus yang sama justru karena adanya gangguan (atau karena asumsi hubungan linier yang keliru). Jadi, untuk memulihkan hubungan linier dari data nyata, biasanya perlu diperkenalkan satu asumsi lagi: data masukan mengandung derau dan derau ini memiliki . Anda dapat membuat asumsi tentang jenis distribusi kebisingan lainnya, namun dalam sebagian besar kasus, distribusi normallah yang dipertimbangkan, yang akan dibahas lebih lanjut.
Metode kemungkinan maksimum
Jadi, kami mengasumsikan adanya kebisingan acak yang terdistribusi normal. Apa yang harus dilakukan dalam situasi seperti ini? Untuk kasus ini dalam matematika ada dan digunakan secara luas . Singkatnya, esensinya terletak pada pilihan dan maksimalisasi selanjutnya.
Kami kembali memulihkan hubungan linier dari data dengan noise normal. Perhatikan bahwa asumsi hubungan linier adalah ekspektasi matematis distribusi normal yang ada. Pada saat yang sama, kemungkinannya adalah mengambil satu nilai atau lainnya, tergantung pada kehadiran yang dapat diamati , sebagai berikut:
Mari kita gantikan sekarang ΠΈ Variabel yang kita butuhkan adalah:
Yang tersisa hanyalah mencari vektornya , di mana probabilitas ini maksimum. Untuk memaksimalkan suatu fungsi, akan lebih mudah jika kita mengambil logaritmanya terlebih dahulu (logaritma dari fungsi tersebut akan mencapai maksimum pada titik yang sama dengan fungsi itu sendiri):
Yang, pada gilirannya, berarti meminimalkan fungsi berikut:
Omong-omong, ini disebut metode . Seringkali semua pertimbangan di atas dihilangkan dan metode ini digunakan begitu saja.
Dekomposisi QR
Nilai minimum dari fungsi di atas dapat dicari dengan mencari titik di mana gradien fungsi tersebut adalah nol. Dan gradiennya akan ditulis sebagai berikut:
adalah metode matriks untuk menyelesaikan masalah minimalisasi yang digunakan dalam metode kuadrat terkecil. Sehubungan dengan hal ini, kami menulis ulang persamaan tersebut dalam bentuk matriks:
Jadi kami menguraikan matriksnya ke matriks ΠΈ dan melakukan serangkaian transformasi (algoritme dekomposisi QR itu sendiri tidak akan dipertimbangkan di sini, hanya penggunaannya dalam kaitannya dengan tugas yang ada):
matriks adalah ortogonal. Hal ini memungkinkan kita untuk menyingkirkan pekerjaan :
Dan jika Anda menggantinya pada , maka itu akan berhasil . Mengingat bahwa adalah matriks segitiga atas, tampilannya seperti ini:
Hal ini dapat diselesaikan dengan menggunakan metode substitusi. Elemen terletak sebagai , elemen sebelumnya terletak sebagai dan sebagainya.
Perlu dicatat di sini bahwa kompleksitas algoritma yang dihasilkan karena penggunaan dekomposisi QR adalah sama . Selain itu, meskipun operasi perkalian matriks diparalelkan dengan baik, tidak mungkin untuk menulis versi terdistribusi yang efektif dari algoritma ini.
Penurunan Gradien
Ketika berbicara tentang meminimalkan suatu fungsi, selalu ada baiknya mengingat metode penurunan gradien (stokastik). Ini adalah metode minimalisasi yang sederhana dan efektif berdasarkan penghitungan gradien suatu fungsi pada suatu titik secara berulang dan kemudian menggesernya ke arah yang berlawanan dengan gradien. Setiap langkah tersebut membawa solusi mendekati titik minimum. Gradiennya masih terlihat sama:
Metode ini juga diparalelkan dan didistribusikan dengan baik karena sifat linier dari operator gradien. Perhatikan bahwa dalam rumus di atas, di bawah tanda penjumlahan terdapat suku-suku independen. Dengan kata lain, kita dapat menghitung gradien secara mandiri untuk semua indeks dari pertama hingga , bersamaan dengan ini, hitung gradien untuk indeks dengan untuk . Kemudian tambahkan gradien yang dihasilkan. Hasil penjumlahannya akan sama seperti jika kita langsung menghitung gradien untuk indeks dari pertama hingga . Jadi, jika suatu data tersebar di antara beberapa bagian data, maka gradiennya dapat dihitung secara terpisah pada masing-masing bagian, kemudian hasil perhitungan tersebut dapat dijumlahkan untuk memperoleh hasil akhir:
Dari segi implementasi, hal ini sesuai dengan paradigma . Pada setiap langkah penurunan gradien, tugas dikirim ke setiap node data untuk menghitung gradien, kemudian gradien yang dihitung dikumpulkan bersama, dan hasil penjumlahannya digunakan untuk meningkatkan hasilnya.
Terlepas dari kemudahan implementasi dan kemampuan mengeksekusi paradigma MapReduce, penurunan gradien juga memiliki kekurangan. Secara khusus, jumlah langkah yang diperlukan untuk mencapai konvergensi jauh lebih tinggi dibandingkan metode lain yang lebih terspesialisasi.
LSQR
adalah metode lain untuk menyelesaikan masalah, yang cocok untuk memulihkan regresi linier dan untuk menyelesaikan sistem persamaan linier. Fitur utamanya adalah menggabungkan keunggulan metode matriks dan pendekatan berulang. Implementasi metode ini dapat ditemukan di kedua perpustakaan , dan masuk . Penjelasan tentang metode ini tidak akan diberikan di sini (dapat ditemukan di artikel ). Sebaliknya, sebuah pendekatan akan ditunjukkan untuk mengadaptasi LSQR untuk dieksekusi di lingkungan terdistribusi.
Metode LSQR didasarkan pada . Ini adalah prosedur berulang, setiap iterasi terdiri dari langkah-langkah berikut:
Tetapi jika kita berasumsi bahwa matriksnya dipartisi secara horizontal, maka setiap iterasi dapat direpresentasikan sebagai dua langkah MapReduce. Dengan cara ini, transfer data dapat diminimalkan selama setiap iterasi (hanya vektor dengan panjang yang sama dengan jumlah yang tidak diketahui):
Pendekatan inilah yang digunakan ketika menerapkan regresi linier .
Kesimpulan
Ada banyak algoritma pemulihan regresi linier, namun tidak semuanya dapat diterapkan di semua kondisi. Jadi dekomposisi QR sangat baik untuk solusi akurat pada kumpulan data kecil. Penurunan gradien mudah diterapkan dan memungkinkan Anda menemukan solusi perkiraan dengan cepat. Dan LSQR menggabungkan properti terbaik dari dua algoritma sebelumnya, karena dapat didistribusikan, konvergen lebih cepat dibandingkan dengan penurunan gradien, dan juga memungkinkan penghentian awal algoritma, tidak seperti dekomposisi QR, untuk menemukan solusi perkiraan.
Sumber: www.habr.com