Memahami tidak ada teorema makan siang gratis di Klasifikasi Pola Duda et al

Saya memiliki beberapa pertanyaan tentang notasi yang digunakan dalam Bagian 9.2. Kurangnya Keunggulan Inheren dari Setiap Klasifikasi di Duda, Hart dan Stork's Pattern Classification . Pertama-tama izinkan saya mengutip beberapa teks yang relevan dari buku ini:

• Untuk kesederhanaan pertimbangkan masalah dua kategori, di mana set pelatihan terdiri dari pola x ^ i dan label kategori terkait y_i = ± 1 untuk i = 1, ..., n yang dihasilkan oleh fungsi target yang tidak diketahui untuk dipelajari, F ( x) , di mana y_i = F (x ^ i) .$D$$x^i$i = 1 , . . . , n F ( x ) y i = F ( x i$y_i = ± 1$$i = 1,..., n$$F(x)$$y_i = F(x^i)$
• Biarkan $H$ menunjukkan set hipotesis (diskrit), atau set parameter yang mungkin untuk dipelajari. Hipotesis tertentu $h(x) \in H$ dapat digambarkan dengan bobot terkuantisasi dalam jaringan saraf, atau parameter 0 dalam model fungsional, atau set keputusan dalam pohon, dan seterusnya.
• Selanjutnya, $P(h)$ adalah probabilitas sebelumnya bahwa algoritma akan menghasilkan hipotesis $h$ setelah pelatihan; perhatikan bahwa ini bukan probabilitas bahwa $h$ benar.
• Berikutnya, $P(h|D)$ menunjukkan probabilitas bahwa algoritma akan menghasilkan hipotesis $h$ ketika dilatih pada data $D$ . Dalam algoritma pembelajaran deterministik seperti tetangga terdekat dan pohon keputusan, $P(h|D)$ akan berada di mana-mana nol kecuali untuk hipotesis tunggal $h$ . Untuk metode stokastik (seperti jaringan saraf dilatih dari bobot awal acak), atau pembelajaran Boltzmann stokastik, $P(h|D)$ dapat menjadi distribusi yang luas.
• Biarkan $E$ menjadi kesalahan untuk fungsi kehilangan nol-satu atau lainnya.

Kesalahan klasifikasi off-training-set yang diharapkan ketika fungsi sebenarnya adalah $F(x)$ dan probabilitas untuk algoritma pembelajaran kandidat $k$ adalah $P_k(h(x)|D)$ diberikan oleh

$$\mathcal{E}_k(E|F,n) = \sum_{x\notin D} P(x) [1-\delta(F(x), h(x))] P_k(h(x)|D)$$

Teorema 9.1. (Tanpa Makan Siang Gratis) Untuk dua algoritma pembelajaran apa pun $P_1 (h |D)$ dan $P_2(h|D)$ , berikut ini adalah benar, independen dari distribusi sampel $P(x)$ dan jumlah $n$ poin pelatihan:

1. Rata-rata seragam untuk semua fungsi target ,$F$$\mathcal{E}_1 (E|F, n) — \mathcal{E}_2(E|F, n) = 0$

2. Untuk setiap set pelatihan tetap , rata-rata seragam di atas , $D$$F$$\mathcal{E}_1 (E|F, D) — \mathcal{E}_2(E|F, D) = 0$

Bagian 1 sebenarnya mengatakan

$$\sum_F \sum_D P(D|F) [\mathcal{E}_1 (E|F, n) — \mathcal{E}_2(E|F, n)] = 0$$

Bagian 2 sebenarnya mengatakan

$$\sum_F [\mathcal{E}_1 (E|F, D) — \mathcal{E}_2(E|F, D)] = 0$$

Pertanyaan saya adalah

1. Dalam rumus , yaitu dapatkah saya mengganti dengan dan memindahkannya ke luar jumlah , karena ini adalah distribusi lebih dari diberikan untuk algoritma pembelajaran stokastik ?$\mathcal{E}_k(E|F,n)$ $$\mathcal{E}_k(E|F,n) = \sum_{x\notin D} P(x) [1-\delta(F(x), h(x))] P_k(h(x)|D),$$ $P_k(h(x)|D)$$P_k(h|D)$$\sum_{x \notin D}$$h$$H$$D$$k$
2. Mengingat bahwa algoritma pembelajaran kandidat ke- adalah metode stokastik, mengapa dalam rumus , tidak ada jumlah lebih dari , yaitu ?$k$$\mathcal{E}_k(E|F,n)$$h$$\sum_{h \in H}$

3. Apa dan ? E i (E | F,n$\mathcal{E}_i (E|F, D)$$\mathcal{E}_i (E|F, n)$

   Apakah berarti tingkat kesalahan off-training yang diberikan pada set pelatihan ?$\mathcal{E}_i (E|F, D)$$D$

   Apakah berarti tingkat kesalahan di luar pelatihan, rata-rata di atas semua set pelatihan yang diberikan ukuran pelatihan ? Jika ya, mengapa bagian 1 dalam teorema NFL rata-rata lebih dari set pelatihan lagi dengan menulis , dan mengapa dalam rumus untuk , tidak ada rata-rata dari semua pelatihan yang diberikan ukuran pelatihan ?n E i (E | F,n) ∑ D E k (E | F,n)$\mathcal{E}_i (E|F, n)$$n$$\mathcal{E}_i (E|F, n)$$\sum_D$$\mathcal{E}_k(E|F,n)$$n$

4. Pada bagian 1 dari teorema NFL, apakah berarti menjumlahkan semua set pelatihan dengan ukuran pelatihan tetap ?$\sum_D$$n$
5. Jika lebih lanjut menjumlahkan semua nilai yang mungkin di dari ukuran pelatihan di bagian 1, hasilnya masih 0, kan?$\mathbb{N}$$n$
6. Dalam rumus , jika saya mengubah menjadi , yaitu tidak harus dibatasi di luar set pelatihan, akankah kedua bagian dalam Teorema NFL masih benar? ∑ x ∉ D ∑ x$\mathcal{E}_k(E|F,n)$$\sum_{x \notin D}$$\sum_x$$x$
7. Jika hubungan sebenarnya antara dan tidak dianggap sebagai fungsi deterministik sebagai , tetapi sebaliknya distribusi kondisional , atau distribusi bersama yang setara dengan mengetahui dan (juga melihat pertanyaan saya yang lain ), maka saya dapat mengubah menjadi (dengan aneh ditunjukkan dalam bagian 1 dan 2). Apakah kedua bagian dalam teorema NFL masih benar?y F y = F ( x ) P ( y | x ) P ( x , y ) P ( y | x ) P ( x ) E k ( E | F , n ) E k ( E | P ( x , y ) , n ) = E x , y [ $x$$y$$F$$y=F(x)$$P(y|x)$$P(x,y)$$P(y|x)$$P(x)$$\mathcal{E}_k (E|F,n)$P k ( h ( x ) | D $$\mathcal{E}_k(E|P(x,y),n) = \mathcal{E}_{x,y} [1-\delta(y, h(x))] P_k(h(x)|D)$$ $P_k(h(x)|D)$

Terima kasih dan salam!

Saya akan menjawab pertanyaan yang saya pikir saya tahu jawabannya.

1. Jawaban ini tidak karena Anda memilih yang bukan bagian dari set dan jadi tergantung pada .D h $x$$D$$h$$x$
2. x H $h$ hanya dievaluasi pada nilai dalam set uji untuk mendapatkan tingkat kesalahan yang diharapkan sehingga tidak dievaluasi pada seluruh set tetapi hanya pada set diskrit di set tes.$x$$H$$x$
3. FD E i (E | F,n)n$\mathcal{E}_i(E|F, D)$ adalah diharapkan untuk tarif kesalahan pelatihan himpunan fungsi dan pelatihan set . Tapi saya pikir berbeda karena Anda hanya mengkondisikan pada jumlah poin pelatihan dan bukan nilai sebenarnya . Tapi ini membingungkan mengingat pernyataan berikut.$F$$D$$\mathcal{E}_i(E|F, n)$$n$$x$
4. n D n D $D$ adalah himpunan vektor pelatihan. Ada pelatihan vektor di . Jadi Anda menjumlahkan selama tetap vektor pelatihan di . Hanya ada satu set .$n$$D$$n$$D$$D$
5. Saya pikir jawaban 5 adalah tidak. Notasi itu agak membingungkan.

Tidak dapat mengomentari 6 dan 7.