Bagaimana seseorang secara resmi membuktikan bahwa kesalahan OOB di hutan acak tidak bias?

Saya sudah membaca pernyataan ini berkali-kali tetapi tidak pernah menemukan bukti. Saya ingin mencoba membuatnya sendiri tetapi saya bahkan tidak yakin dengan notasi apa yang digunakan. Adakah yang bisa membantu saya dengan ini?

mathematical-statistics random-forest unbiased-estimator proof JEquihua
sumber

OOB tidak hampa bias. Satu-satunya - sering: paling penting - komponen bias yang dihilangkan oleh OOB adalah "optimisme" yang dialami oleh sampel yang masuk dalam sampel. Misalnya OOB secara bias pesimis karena didasarkan pada prediksi rata-rata saja

\approx 36.8 %

$\approx 36.8 \%$ pohon di hutan. EDIT: seperti yang ditunjukkan dalam jawaban oleh @cbeleites di bawah ini.

Jim

Jawaban:

Saya tidak tahu apakah ini jawaban terakhir, tetapi hal-hal itu tidak dapat dikomentari.

Pernyataan bahwa kesalahan OOB tidak bias sering digunakan, tetapi saya tidak pernah melihat demonstrasi. Setelah banyak pencarian, saya akhirnya memberikan setelah membaca dengan seksama halaman Breiman for RF yang terkenal : Perkiraan kesalahan out-of-bag (oob) . Jika Anda tidak memperhatikan (seperti yang saya lewatkan selama beberapa waktu), proposisi terakhir adalah yang penting: Ini telah terbukti tidak bias dalam banyak tes . Jadi, tidak ada tanda derivasi formal.

Lebih dari itu, tampaknya terbukti bahwa untuk kasus ketika Anda memiliki lebih banyak variabel daripada contoh, penaksir ini bias. Lihat di sini .

Untuk kesalahan dalam tas ada derivasi formal. Kesalahan di dalam tas adalah kesalahan bootstrap dan ada banyak literatur yang dimulai dengan "Pengantar Bootsrap, oleh Efron dan Tibshirani". Namun demonstrasi paling bersih yang saya lihat ada di sini .

Jika Anda ingin mulai menemukan bukti, saya pikir titik awal yang baik adalah perbandingan estimasi ini dengan validasi silang N-fold. Dalam ESTL dinyatakan bahwa ada identitas dalam batas, karena jumlah sampel masuk hingga tak terbatas.

rapaio
sumber

Saya melihat sekilas pada kertas Mitchell, dan sejauh ini saya tidak terlalu suka (saya pikir itu

n ≪ p

$n \ll p$ adalah suatu kebetulan: bahkan hutan secara acak bukanlah peluru ajaib terhadap terlalu sedikit kasus. Pada titik tertentu juga kinerja mereka rusak dan saya kira ini adalah penyebab yang mendasari pengamatan yang dilaporkan). Namun, pengamatan bias pesimistis tidak mengherankan bagi saya, lihat jawaban saya. Sebenarnya saya berpikir bahwa pemikiran yang saya uraikan dalam jawaban saya mungkin menawarkan penjelasan yang agak sederhana secara konseptual tentang apa yang terjadi di sana.

cbeleites tidak senang dengan SX

Mengapa Anda berharap kesalahan oob tidak bias?

Ada (setidaknya) 1 kasus pelatihan yang kurang tersedia untuk pohon-pohon yang digunakan di hutan pengganti dibandingkan dengan hutan "asli". Saya berharap ini mengarah pada bias pesimistis kecil yang secara kasar sebanding dengan validasi silang keluar-keluar-satu.
Ada kira-kira $\frac{1}{e} \approx \frac{1}{3}$ dari jumlah pohon di hutan "asli" di hutan pengganti yang sebenarnya dievaluasi dengan kasus yang ditinggalkan. Jadi, saya mengharapkan varians yang lebih tinggi dalam prediksi, yang akan menyebabkan bias pesimis lebih lanjut.

Kedua pemikiran terkait erat dengan kurva pembelajaran dari pengklasifikasi dan aplikasi / data yang dipertanyakan: yang pertama sampai kinerja rata-rata sebagai fungsi dari ukuran sampel pelatihan dan yang kedua dengan varians di sekitar kurva rata-rata ini.

Secara keseluruhan, saya berharap paling banyak Anda dapat menunjukkan secara formal bahwa oob adalah penduga yang tidak bias dari kinerja hutan acak yang mengandung $\frac{1}{e} \approx \frac{1}{3}$ dari jumlah pohon di hutan "asli", dan sedang dilatih $n - 1$ kasus data pelatihan asli.

Perhatikan juga bahwa Breiman menggunakan "tidak bias" untuk out-of-bootstrap dengan cara yang sama seperti ia menggunakannya untuk validasi silang, di mana kami juga memiliki bias pesimistis (kecil). Berasal dari bidang eksperimental, saya setuju dengan mengatakan bahwa keduanya praktis tidak bias karena bias biasanya jauh lebih sedikit masalah daripada varians (Anda mungkin tidak menggunakan hutan acak jika Anda memiliki kemewahan memiliki banyak kasus) .

cbeleites tidak senang dengan SX
sumber

Saya tidak berharap itu terjadi. Disebutkan oleh orang-orang di banyak tempat jadi saya hanya menerimanya. Sekarang saya telah memikirkannya, itulah mengapa saya ingin membuktikannya. Saya suka Anda menjawab, biarkan saya bermain-main dengan info Anda sedikit untuk melihat apa yang bisa saya simpulkan.

JEquihua

@JEquihua: Saya pasti akan tertarik dengan hasilnya.

cbeleites tidak senang dengan SX

Hutan oob sekitar 1/3 dari yang asli, bukan 2/3 (jadi lebih banyak alasan untuk kesalahan oob menjadi pesimis!). Peluang mengambil pohon T yang diberikan untuk hutan oob dari pengamatan yang diberikan (x, y) adalah probabilitas (x, y) yang tidak berada di T, yaitu ((N-1) / N) ^ N = ( 1 + (-1) / N) ^ N -> exp (-1) = ~ 1/3. Jadi ukuran yang diharapkan dari hutan oob untuk (x, y) adalah sekitar B / 3, jika B adalah ukuran hutan asli.

memeplex

@memeplex: tentu saja - terima kasih telah melihat. Memperbaikinya.

cbeleites tidak senang dengan SX