🎷 🛂 ㊙️ Deep (Learning + Random) Hutan dan artikel parsing 🤙 ⚛️ 👨‍👧

Kami terus berbicara tentang konferensi tentang statistik dan pembelajaran mesin AISTATS 2019. Dalam posting ini kami akan menganalisis artikel tentang model mendalam dari ansambel pohon, mencampur regularisasi untuk data yang sangat jarang, dan perkiraan waktu validasi silang yang hemat waktu.

Algoritma Hutan Dalam: Eksplorasi Model Non-NN Deep berdasarkan Modul Non-Diferensial

Zhi-Hua Zhou (Universitas Nanjing)
→ Presentasi
→ Artikel
Implementasi - di bawah ini

Seorang profesor dari Tiongkok berbicara tentang ansambel pohon, yang penulis sebut sebagai pelatihan mendalam pertama tentang modul yang tidak dapat dibedakan. Ini mungkin tampak seperti pernyataan yang terlalu keras, tetapi profesor ini dan indeks-H 95-nya diundang sebagai pembicara, fakta ini memungkinkan kita untuk menganggap pernyataan itu lebih serius. Teori dasar Deep Forest telah dikembangkan sejak lama, artikel aslinya sudah 2017 (hampir 200 kutipan), tetapi penulis menulis perpustakaan dan setiap tahun mereka meningkatkan algoritma dalam kecepatan. Dan sekarang, tampaknya, mereka telah mencapai titik di mana teori yang indah ini akhirnya dapat dipraktikkan.

Pandangan umum arsitektur Deep Forest

Latar belakang

Model mendalam, yang sekarang dipahami sebagai jaringan saraf dalam, digunakan untuk menangkap dependensi data yang kompleks. Selain itu, ternyata meningkatkan jumlah lapisan lebih efisien daripada meningkatkan jumlah unit pada setiap lapisan. Tetapi jaringan saraf memiliki kelemahan:

Dibutuhkan banyak data untuk tidak berlatih kembali,
Dibutuhkan banyak sumber daya komputasi untuk belajar dalam jumlah waktu yang wajar,
Terlalu banyak hiperparameter yang sulit dikonfigurasi secara optimal

Selain itu, elemen jaringan syaraf dalam adalah modul yang dapat dibedakan yang belum tentu efektif untuk setiap tugas. Terlepas dari kerumitan jaringan saraf, algoritma konseptual sederhana, seperti hutan acak, sering bekerja lebih baik atau tidak jauh lebih buruk. Tetapi untuk algoritma seperti itu, Anda perlu merancang fitur secara manual, yang juga sulit dilakukan secara optimal.

Para peneliti telah memperhatikan bahwa ansambel pada Kaggle: “sangat sempurna”, dan terinspirasi oleh kata-kata Scholl dan Hinton bahwa diferensiasi adalah sisi terlemah dari Deep Learning, mereka memutuskan untuk membuat ansambel pohon dengan properti DL.

Slide “Cara membuat ansambel yang bagus”

Arsitekturnya disimpulkan dari sifat-sifat ansambel: unsur-unsur ansambel tidak boleh sangat buruk dalam kualitas dan berbeda.

GcForest terdiri dari dua fase: Cascade Forest dan Multi-Grained Scanning. Selain itu, agar kaskade tidak berlatih kembali, terdiri dari 2 jenis pohon - salah satunya adalah pohon yang benar-benar acak yang dapat digunakan pada data yang tidak terisi. Jumlah lapisan ditentukan di dalam algoritma cross-validation.

Dua jenis pohon

Hasil

Selain hasil pada dataset standar, penulis mencoba menggunakan gcForest pada transaksi sistem pembayaran Cina untuk mencari penipuan dan mendapatkan F1 dan AUC jauh lebih tinggi daripada LR dan DNN. Hasil ini hanya dalam presentasi, tetapi kode untuk dijalankan pada beberapa dataset standar ada di Git.

Hasil substitusi algoritma. mdDF adalah optimal Margin Distribution Deep Forest, varian dari gcForest

Pro:

Beberapa hiperparameter, jumlah lapisan disesuaikan secara otomatis di dalam algoritma
Pengaturan default dipilih untuk bekerja dengan baik pada banyak tugas.
Kompleksitas adaptif model, pada data kecil - model kecil
Tidak perlu mengatur fitur
Ini berfungsi sebanding dalam kualitas dengan jaringan saraf yang dalam, dan kadang-kadang lebih baik

Cons:

Tidak dipercepat pada GPU
Dalam gambar kehilangan DNN

Jaringan saraf memiliki masalah redaman gradien, sementara hutan yang dalam memiliki masalah “diversifikasi menghilang”. Karena ini adalah ansambel, semakin banyak elemen "berbeda" dan "baik" untuk digunakan, semakin tinggi kualitasnya. Masalahnya adalah bahwa penulis telah mencoba hampir semua pendekatan klasik (pengambilan sampel, pengacakan). Selama tidak ada penelitian dasar baru yang muncul pada topik “perbedaan”, akan sulit untuk meningkatkan kualitas hutan yang dalam. Tetapi sekarang mungkin untuk meningkatkan kecepatan komputasi.

Reproduksibilitas hasil

Saya tertarik oleh XGBoost pada data tabular, dan saya ingin mereproduksi hasilnya. Saya mengambil dataset Dewasa dan menerapkan GcForestCS (versi yang sedikit dipercepat dari GcForest) dengan parameter dari penulis artikel dan XGBoost dengan parameter default. Dalam contoh yang dimiliki penulis, fitur kategorikal sudah dipra-proses sebelumnya, tetapi tidak ditunjukkan caranya. Akibatnya, saya menggunakan CatBoostEncoder dan metrik lainnya - ROC AUC. Hasilnya berbeda secara statistik - XGBoost menang. Waktu operasi XGBoost dapat diabaikan, sementara gcForestCS memiliki 20 menit masing-masing cross-validasi pada 5 kali lipat. Di sisi lain, penulis menguji algoritma pada dataset yang berbeda, dan menyesuaikan parameter untuk dataset ini dengan preprocessing fitur mereka.

Kode dapat ditemukan di sini .

Implementasi

→ Kode resmi dari penulis artikel
→ Modifikasi yang ditingkatkan resmi, lebih cepat, tetapi tidak ada dokumentasi
→ Implementasi lebih sederhana

PcLasso: laso memenuhi regresi komponen utama

J. Kenneth Tay, Jerome Friedman, Robert Tibshirani (Universitas Stanford)

→ Artikel
→ Presentasi
→ Contoh penggunaan

Pada awal 2019, J. Kenneth Tay, Jerome Friedman, dan Robert Tibshirani dari Stanford University mengusulkan metode pengajaran baru dengan seorang guru, terutama cocok untuk data yang jarang.

Para penulis artikel memecahkan masalah menganalisis data pada studi ekspresi gen, yang dijelaskan dalam Zeng & Breesy (2016). Target adalah status mutasi gen p53, yang mengatur ekspresi gen dalam menanggapi berbagai sinyal stres seluler. Tujuan dari penelitian ini adalah untuk mengidentifikasi prediktor yang berkorelasi dengan status mutasi p53. Data terdiri dari 50 baris, 17 di antaranya diklasifikasikan sebagai normal dan 33 lainnya membawa mutasi pada gen p53. Menurut analisis dalam Subramanian et al. (2005) 308 set gen yang antara 15 dan 500 dimasukkan dalam analisis ini. Kit gen ini mengandung total 4.301 gen dan tersedia dalam paket grpregOverlap R. Saat memperluas data untuk memproses grup yang tumpang tindih, 13.237 kolom adalah output. Para penulis artikel menggunakan metode pcLasso, yang membantu meningkatkan hasil model.

Dalam gambar kita melihat peningkatan AUC saat menggunakan "pcLasso"

Esensi dari metode ini

Metode menggabungkan $l_1$ -regulasi dengan $l_2$ , yang mempersempit vektor koefisien ke komponen utama dari matriks fitur. Mereka menyebut metode yang diusulkan "komponen laso inti" ("pcLasso" tersedia di R). Metode ini bisa sangat kuat jika variabel sebelumnya dikelompokkan (pengguna memilih apa dan bagaimana mengelompokkan). Dalam hal ini, pcLasso memampatkan setiap grup dan mendapatkan solusi sesuai dengan komponen utama grup ini. Dalam proses penyelesaian, pemilihan kelompok yang signifikan di antara yang tersedia juga dilakukan.

Kami menyajikan matriks diagonal dari dekomposisi singular dari matriks fitur terpusat $X$ sebagai berikut:

Kami mewakili dekomposisi singular kami dari matriks berpusat X (SVD) sebagai $X = UDV ^ T$ dimana $D$ Merupakan matriks diagonal yang terdiri dari nilai singular. Dalam bentuk ini $l_2$ - Regularisasi dapat diwakili:
$\ beta ^ T VZV ^ T \ beta$ dimana $Z$ - matriks diagonal yang berisi fungsi kuadrat dari nilai singular: $Z_ {11} = f_1 (d_1 ^ 2, d_2 ^ 2, ..., d_m ^ 2), ..., Z_ {22} = f_2 (d_1 ^ 2, d_2 ^ 2, ..., d_m ^ 2)$ .

Secara umum, dalam $l_2$ -regulasi $Z_ {jj} = 1$ untuk semua $j$ yang sesuai $\ beta ^ T \ beta$ . Mereka menyarankan meminimalkan fungsi berikut:

Di sini $D$ - matriks perbedaan elemen diagonal $d_1 ^ 2-d_1 ^ 2, d_1 ^ 2-d_2 ^ 2, ..., d_1 ^ 2-d_m ^ 2$ . Dengan kata lain, kami mengontrol vektor $\ beta$ menggunakan hyperparameter juga $\ theta$ .
Mengubah ungkapan ini, kami mendapatkan solusinya:

Tetapi "fitur" utama dari metode ini, tentu saja, adalah kemampuan untuk mengelompokkan data, dan atas dasar kelompok-kelompok ini untuk menyoroti komponen utama kelompok. Kemudian kami menulis ulang solusi kami dalam bentuk:

Di sini $\ beta_k$ - vektor subvektor $\ beta$ sesuai dengan grup k, $d_k = (d_ {k1}, ..., d_ {kmk})$ - nilai tunggal $X_k$ diatur dalam urutan menurun, dan $D_ {d_ {k1} ^ 2-d_ {kj} ^ 2}$ - matriks diagonal $d_ {k1} ^ 2-d_ {kj} ^ 2, j = 1,2, ..., m_k$

Beberapa catatan tentang solusi fungsional target:

Fungsi obyektif adalah cembung, dan komponen yang tidak halus dapat dipisahkan. Oleh karena itu, dapat dioptimalkan secara efektif menggunakan gradient descent.
Pendekatannya adalah dengan mengkomit banyak nilai $\ theta$ (termasuk nol, masing-masing, mendapatkan standar $l_1$ -regulasi), dan kemudian mengoptimalkan: mengambil $\ lambda$ . Dengan demikian, parameter $\ theta$ dan $\ lambda$ dipilih untuk validasi silang.
Parameter $\ theta$ sulit diartikan. Dalam perangkat lunak (paket pcLasso), pengguna sendiri menetapkan nilai parameter ini, yang termasuk dalam interval [0,1], di mana 1 sesuai dengan $\ theta$ = 0 (laso).

Dalam praktiknya, variasikan nilainya $\ theta$ = 0,25, 0,5, 0,75, 0,9, 0,95 dan 1, Anda dapat mencakup berbagai model.

Algoritma itu sendiri adalah sebagai berikut

Algoritma ini sudah ditulis dalam R, jika Anda mau, Anda sudah bisa menggunakannya. Perpustakaan itu disebut 'pcLasso'.

Jackknife Infinitesimal Tentara Swiss

Ryan Giordano (UC Berkeley); William Stephenson (MIT); Runjing Liu (UC Berkeley);
Michael Jordan (UC Berkeley); Tamara Broderick (MIT)

→ Artikel
→ Kode

Kualitas algoritma pembelajaran mesin sering diukur dengan multi-validasi silang (cross-validation atau bootstrap). Metode ini sangat kuat, tetapi lambat pada set data besar.

Dalam pekerjaan ini, kolega menggunakan perkiraan bobot, menghasilkan hasil yang bekerja lebih cepat. Perkiraan linier ini dikenal dalam literatur statistik sebagai "pisau lipat kecil". Ini terutama digunakan sebagai alat teoritis untuk membuktikan hasil asimptotik. Hasil artikel ini berlaku terlepas dari apakah bobot dan data bersifat stokastik atau deterministik. Sebagai konsekuensinya, perkiraan ini secara berurutan memperkirakan validasi silang sebenarnya untuk setiap k tetap.

Penyajian Paper Award kepada penulis artikel

Esensi dari metode ini

Pertimbangkan masalah estimasi parameter yang tidak diketahui $\ theta \ in \ Omega _ {\ theta} \ subset R ^ {D}$ dimana $\ Omega _ {\ theta}$ Ringkas, dan ukuran dataset kami adalah $N$ . Analisis kami akan dilakukan pada kumpulan data tetap. Tentukan peringkat kami $\ theta \ in \ Omega _ {\ theta}$ sebagai berikut:

Untuk masing-masing $n = 1,2 ..., N$ diatur $g_n$ ( $\ theta$ ) Merupakan fungsi dari $\ Omega _ {\ theta} \ subset R ^ {D}$
$\ omega_n$ Adalah bilangan real, dan $\ omega$ Merupakan vektor yang terdiri dari $\ omega_n$

Lalu $\ hat {\ theta}$ dapat direpresentasikan sebagai:

Memecahkan masalah optimisasi ini dengan metode gradien, kami mengasumsikan bahwa fungsinya dapat dibedakan dan kita dapat menghitung Hessian. Masalah utama yang kami selesaikan adalah biaya komputasi yang terkait dengan evaluasi $\ hat {\ theta} ̂ (\ omega)$ untuk semua $\ omega∈W$ . Kontribusi utama penulis artikel adalah menghitung estimasi $\ hat {\ theta} _1 = \ hat {\ theta} _1 (1 _ {\ omega})$ dimana $1_ \ omega = (1,1, ..., 1)$ . Dengan kata lain, optimasi kami hanya akan bergantung pada turunannya $g_n (\ theta)$ yang kami anggap ada dan Hessian:

Selanjutnya, kita mendefinisikan persamaan dengan titik tetap dan turunannya:

Ini ada baiknya memperhatikan itu $G (\ theta ̂ (\ omega), w) = 0$ sejak itu $\ hat {\ theta} (\ omega)$ - solusi untuk $\ frac {1} {N} \ sum_ {n = 1} ^ {N} \ omega_n g_n (\ theta) = 0$ . Kami juga mendefinisikan: $H_1 = H (\ hat {\ theta} _1,1_ \ omega)$ , dan matriks bobot sebagai: $\ Delta \ omega = \ omega-1_ \ omega \ dalam R ^ {n}$ . Dalam hal kapan $H_1$ memiliki matriks terbalik, kita dapat menggunakan teorema fungsi implisit dan 'aturan rantai':

Derivatif ini memungkinkan kita untuk membentuk perkiraan linier $\ hat {\ theta} ̂ (\ omega)$ melalui $\ hat {\ theta} _1$ yang terlihat seperti ini:

Sejak $\ hat {\ theta} _ {IJ}$ hanya bergantung pada $\ hat {\ theta} _1$ dan $\ Delta \ omega$ , dan bukan dari solusi untuk nilai lainnya $\ omega$ , oleh karena itu, tidak perlu menghitung ulang dan menemukan nilai baru new. Sebagai gantinya, seseorang perlu menyelesaikan SLE (sistem persamaan linear).

Hasil

Dalam praktiknya, ini secara signifikan mengurangi waktu dibandingkan dengan validasi silang:

Deep (Learning + Random) Hutan dan artikel parsing

Algoritma Hutan Dalam: Eksplorasi Model Non-NN Deep berdasarkan Modul Non-Diferensial

PcLasso: laso memenuhi regresi komponen utama

Jackknife Infinitesimal Tentara Swiss

More articles: