Apa arti 'mungkin secara kira-kira benar'?

Ini berarti bahwa, dengan probabilitas tinggi atas sampel acak, pembelajar menghasilkan hipotesis yang kira-kira benar, yaitu, memiliki kesalahan kecil pada data di masa mendatang. Keterpelajaran mensyaratkan pencapaian ini dari sejumlah contoh dan jumlah komputasi yang hanya tumbuh secara polinomial.

Bagaimana teori pembelajaran mengarah pada boosting?

Para peneliti bertanya apakah pembelajar yang hanya sedikit lebih baik daripada tebakan acak dapat diubah menjadi pembelajar yang sangat akurat. Bukti bahwa keterpelajaran lemah dan kuat setara bersifat konstruktif, dan konstruksi tersebut menjadi algoritma boosting yang banyak digunakan dalam praktik.

Teori Pembelajaran Komputasional

Teori pembelajaran komputasional mengkaji konsep-konsep yang dapat dipelajari secara efisien dari contoh, memperlakukan pembelajaran sebagai masalah komputasi dan kompleksitas sampel.

Temukan Topik dengan PaperMindSegeraFind papers & topics

Tools & resources

Unduh salindia

Learn & explore

VideoSegera

Definition

Teori pembelajaran komputasional adalah studi tentang sumber daya, dalam data dan komputasi, yang diperlukan untuk mempelajari konsep dari contoh; dalam model mungkin secara kira-kira benar, kelas konsep dapat dipelajari jika suatu algoritma dapat, dari sejumlah sampel polinomial dan dalam waktu polinomial, menghasilkan hipotesis yang akurat dengan probabilitas tinggi.

Scope

Topik ini mencakup model formal keterpelajaran (learnability): model mungkin secara kira-kira benar (probably approximately correct) yang menanyakan kapan suatu konsep dapat dipelajari dengan akurasi tinggi dan probabilitas tinggi dari sejumlah contoh dan komputasi polinomial, model batas kesalahan dan pembelajaran daring (online-learning), keterpelajaran lemah versus kuat dan boosting, serta kaitannya dengan kompleksitas komputasional. Ini membahas kelayakan statistik dan algoritmik dari pembelajaran.

Core questions

Kelas konsep mana yang dapat dipelajari secara efisien dari contoh?
Berapa banyak data dan komputasi yang dibutuhkan untuk mempelajari suatu konsep?
Apa hubungan antara keterpelajaran lemah dan kuat?
Bagaimana keterpelajaran terhubung dengan kompleksitas komputasional?

Key theories

Pembelajaran mungkin secara kira-kira benar: Model Valiant mendefinisikan kelas konsep sebagai dapat dipelajari ketika algoritma yang efisien dapat menghasilkan, dengan probabilitas tinggi, hipotesis dengan kesalahan rendah dari sejumlah contoh polinomial, menjadikan keterpelajaran sebagai pertanyaan komputasional yang tepat.
Keterpelajaran lemah dan boosting: Hasil sentral menunjukkan bahwa setiap kelas yang dapat dipelajari sedikit lebih baik daripada kebetulan juga dapat dipelajari secara kuat, yang secara langsung mengarah pada algoritma boosting yang memperkuat pembelajar lemah menjadi pembelajar yang akurat.
Batas statistik dan komputasional: Keterpelajaran dibatasi baik oleh kompleksitas sampel, yang terkait dengan ukuran kapasitas, maupun oleh kekerasan komputasional, sehingga beberapa kelas dapat dipelajari secara statistik namun tidak dapat dipecahkan secara komputasional.

Clinical relevance

Teori pembelajaran komputasional memberikan dasar formal untuk apa yang dapat dan tidak dapat dicapai oleh algoritma pembelajaran dan secara langsung menginspirasi metode praktis, terutama boosting, yang muncul dari pertanyaan apakah pembelajar lemah dapat digabungkan menjadi pembelajar kuat; ini membingkai pembelajaran sebagai disiplin komputasional yang ketat.

History

Valiant memperkenalkan model mungkin secara kira-kira benar pada tahun 1984, memberikan definisi komputasional yang tepat untuk pembelajaran dan mendirikan bidang ini. Pekerjaan selanjutnya menetapkan karakterisasi kompleksitas sampel, kesetaraan keterpelajaran lemah dan kuat yang memotivasi boosting, dan hasil kekerasan yang menunjukkan batas komputasional pembelajaran.

Key figures

Leslie Valiant
Michael Kearns
Robert Schapire

Seminal works

valiant1984
kearns1994
vapnik1995

Frequently asked questions

Apa arti 'mungkin secara kira-kira benar'?: Ini berarti bahwa, dengan probabilitas tinggi atas sampel acak, pembelajar menghasilkan hipotesis yang kira-kira benar, yaitu, memiliki kesalahan kecil pada data di masa mendatang. Keterpelajaran mensyaratkan pencapaian ini dari sejumlah contoh dan jumlah komputasi yang hanya tumbuh secara polinomial.
Bagaimana teori pembelajaran mengarah pada boosting?: Para peneliti bertanya apakah pembelajar yang hanya sedikit lebih baik daripada tebakan acak dapat diubah menjadi pembelajar yang sangat akurat. Bukti bahwa keterpelajaran lemah dan kuat setara bersifat konstruktif, dan konstruksi tersebut menjadi algoritma boosting yang banyak digunakan dalam praktik.