Inferensi, estimasi, dan pengambilan keputusan dari data
Statistik sejauh ini kebanyakan tentang rata-rata dan asimptotik. Ketidaksamaan konsentrasi bertanya pertanyaan lebih tajam, sampel-terbatas: seberapa mungkin kuantitas acak mendarat jauh dari meannya? Jawaban mereka adalah tulang punggung matematis mengapa machine learning bisa menawarkan jaminan sama sekali.
Paling dasar, hanya membutuhkan variabel non-negatif dan meannya, adalah ketidaksamaan Markov:
Ia mengatakan variabel non-negatif tidak bisa sering berada banyak kali rata-ratanya. Jika mean kecil, nilai besar harus langka. Kasar, tapi butuh hampir tidak ada apa-apa.
Di mana ini berlaku dalam MLBatas Hoeffding adalah jantung teori generalisasi: mengapa galat terukur model pada set tes terbatas terbukti dekat ke galat sejatinya, dengan probabilitas tinggi, justifikasi formal untuk mempercayai skor tes. Ini mesin PAC learning ("Probably Approximately Correct"): dengan cukup sampel, celah antara performa pelatihan dan sejati kecil dengan probabilitas tinggi. Ketidaksamaan konsentrasi…