Apa arti teori belajar PAC?

Saya baru dalam pembelajaran mesin. Saya belajar kursus dalam pembelajaran mesin (Stanford University) dan saya tidak mengerti apa yang dimaksud dengan teori ini dan apa kegunaannya. Saya bertanya-tanya apakah seseorang dapat merinci teori ini untuk saya.

Teori ini didasarkan pada persamaan ini.

Teori belajar kira-kira benar (PAC) membantu menganalisis apakah dan dalam kondisi apa seorang pelajar mungkin akan menghasilkan sebuah klasifikasi yang kira-kira benar. (Anda akan melihat beberapa sumber menggunakan A sebagai pengganti L. )$L$$A$$L$

Pertama, mari kita tentukan "perkiraan." Hipotesis kira - kira benar jika kesalahannya atas distribusi input dibatasi oleh beberapa ϵ , 0 ≤ ϵ ≤ $h \in H$Yaitu,errorD(h)<ϵ, di manaDadalah distribusi melalui input.$\epsilon, 0 \le \epsilon \le \frac{1}{2}.$$error_D(h)\lt \epsilon$$D$

Selanjutnya, "mungkin." Jika akan menampilkan penggolong seperti itu dengan probabilitas 1 - δ , dengan 0 ≤ δ ≤ $L$$1 - \delta$ , kami menyebut pengelompokan itumungkinkira-kira benar.$0 \le \delta \le \frac{1}{2}$

Mengetahui bahwa konsep target PAC-dapat dipelajari memungkinkan Anda untuk mengikat ukuran sampel yang diperlukan untuk mempelajari pengelompokan yang kira-kira benar, yang ditunjukkan dalam rumus yang telah Anda buat:

Untuk mendapatkan intuisi tentang ini, catat efek pada ketika Anda mengubah variabel di sisi kanan. Saat kesalahan yang diizinkan berkurang , ukuran sampel yang diperlukan bertambah. Demikian juga, tumbuh dengan probabilitas pelajar mendekati benar, dan dengan ukuran ruang hipotesis H . (Secara longgar, ruang hipotesis adalah sekumpulan classifier yang dipertimbangkan oleh algoritma Anda.) Lebih jelasnya, ketika Anda mempertimbangkan classifier yang lebih mungkin, atau menginginkan kesalahan yang lebih rendah atau probabilitas kebenaran yang lebih tinggi, Anda memerlukan lebih banyak data untuk membedakannya.$m$$H$

Untuk lebih lanjut, ini dan video terkait lainnya mungkin bermanfaat, seperti pendahuluan yang panjang ini atau salah satu dari banyak teks pembelajaran mesin, kata Mitchell , misalnya.

$(x_i, y_i)$ dan seseorang ingin menemukan hipotesis atau model yang akan, diberikan input $x_i$ kembali $y_i$atau sesuatu yang sangat dekat. Lebih penting lagi diberikan data baru$\tilde{x}$ model akan menghitung atau memprediksi yang sesuai $\tilde{y}$.
Benar-benar orang tidak tertarik pada seberapa akurat hipotesis pada data yang diberikan (pelatihan) kecuali bahwa sulit untuk percaya bahwa model yang dibuat menggunakan beberapa data tidak akan secara akurat mencerminkan kumpulan data itu, tetapi akan akurat di masa mendatang. set data. Dua peringatan penting adalah bahwa seseorang tidak dapat memprediksi data baru dengan akurasi 100% dan ada juga kemungkinan bahwa contoh data yang dilihatnya kehilangan sesuatu yang penting. Contoh mainan adalah bahwa jika saya memberi Anda 'data' 1,2,3,4 orang akan 'memperkirakan' bahwa 5 akan menjadi angka berikutnya. Jika Anda menguji ini dengan bertanya kepada orang berapa nomor berikutnya dalam urutan, kebanyakan orang akan mengatakan 5. Seseorang bisakatakan 1.000.000. Jika Anda diberi urutan 1,2,3, ... 999.999 orang akan lebih yakin bahwa angka berikutnya adalah 1.000.000. Namun angka berikutnya bisa 999.999,5, atau bahkan 5. Intinya adalah bahwa semakin banyak data yang dilihat, semakin yakin seseorang dapat menghasilkan model yang akurat, tetapi orang tidak pernah bisa benar-benar yakin.

Definisi mungkin kira-kira benar memberikan versi matematika yang tepat dari ide ini. Data yang diberikan$x_i, 1 \leq i \leq m$ dengan output $y_i$ dan kelas model $f_{\theta}$yang merupakan hipotesis, seseorang dapat mengajukan 2 pertanyaan. Bisakah kita menggunakan data untuk menemukan hipotesis tertentu$f_{\Theta}$ that is likely to be really accurate in predicting new values ? Further how likely is it that the model is as accurate as we expect it to be ? That is can we train a model that is highly likely to be very accurate. As in Sean Easter's answer, we say a class of hypotheses (class of models) is PAC if we can do an 'epsilon, delta' argument. That is we can say with probability $p >1-\delta$ that our model $f_{\Theta}$ is accurate to within $\epsilon$ . How much data one must see to satisfy a specific pair $(\delta,\epsilon)$ depends on the actual $(\delta,\epsilon)$ and how complex the given class of hypothesis are.

More precisely, a class of hypotheses $\mathcal{H}$ or models $f_{\theta}$ is PAC if for any pair $(\epsilon, \delta)$ with $0 < \epsilon,\delta , <.5$ ada model spesifik $f_{\Theta}$ sedemikian rupa sehingga ada data baru $\tilde{x}, \tilde{y}$, model ini akan memuaskan $Err(f_{\Theta}(\tilde{x}) ,\tilde{y} ) < \epsilon$ dengan probabilitas $p > 1-\delta$ jika model itu dipilih (dilatih) dengan setidaknya $m = m(\delta,\epsilon,\mathcal{H})$contoh pelatihan. Berikut Err adalah fungsi kerugian yang dipilih yang biasanya$(f_{\Theta}(\tilde{x}) -\tilde{y})^2$.

Diagram yang Anda berikan memberikan rumus tentang seberapa banyak data yang perlu dilatih untuk kelas hipotesis tertentu untuk memuaskan pasangan tertentu $(\delta,\epsilon)$. I could be wrong, but I believe that this definition was given by Valiant in a paper called "A Theory of the Learnable" and was in part responsible for Valiant winning the Turing prize.