Pengambilan sampel PAC agnostik batas bawah

Sudah terkenal bahwa untuk pembelajaran PAC klasik, diperlukan untuk mencapai batas kesalahan whp, di mana adalah dimensi VC dari kelas konsep. $\Omega(d/\varepsilon)$ $\varepsilon$ $d$

Apakah diketahui bahwa diperlukan dalam kasus agnostik? $\Omega(d/\varepsilon^2)$

lg.learning machine-learning Aryeh
sumber

Saya tidak yakin seperti apa batas bawah, seseorang harus ada jika batas Hoefding ketat (dan saya pikir itu benar). Batas ini menyatakan bahwa untuk 1 fn, jika probabilitas kesalahan adalah p, maka Anda membutuhkan paling banyak

sampel untuk memperkirakan p sampai dalam kesalahan + -

whp Jadi pertimbangkan kelas konsep dengan 2 konsep,

dan

dan VC-dimensi 2. Ambil distribusi di atas contoh sehingga

(atau sebaliknya) - ini dimungkinkan karena VC-dimensi adalah 2. Tampaknya algoritma hanya menggunakan

m = O (1 / ϵ^{2})

$m = O(1/\epsilon^2)$

ϵ

$\epsilon$

f_{1}

$f_1$

f_{2}

$f_2$

p_{1} = p_{2} + ϵ

$p_1 = p_2 + \epsilon$

contoh akan menyiratkan peningkatan batas Hoefding.

O (1 / ϵ)

$O(1/\epsilon)$

Aaron Roth

Yaitu, saya pikir Hoeffding terikat ketat di

untuk

. Saya pikir alasan di atas secara umum diketahui ...

p = 1 / 2

$p=1/2$

O (1 / ϵ^{2})

$O(1/\epsilon^2)$

Lev Reyzin

OK - sepertinya saya mendapatkan latihan lain untuk kursus ML ... :) Terima kasih atas masukannya, Aaron dan Lev!

Aryeh

@ Harun, mungkin ini seharusnya jawaban.

Suresh Venkat

Jawaban:

Saya sekarang menyadari bahwa batas bawah memang telah dibangun oleh Anthony dan Bartlett (lihat presentasi di sini ).

Edit 24-Sep-2018. Pertanyaan ini telah membuat saya sibuk selama bertahun-tahun, dan baru-baru ini, saya. Pinelis dan saya telah memperoleh konstanta optimal yang tepat dalam PAC agnostik yang cenderung muncul di Ann. Stat .

Aryeh
sumber

Dalam makalah Anda, Anda tidak mengutip karya ini ( jmlr.org/papers/volume17/15-389/15-389.pdf ). Apakah kompleksitas sampel optimal upperbound dalam kasus yang dapat disadari bukan dari koneksi ke pekerjaan Anda? Apakah kompleksitas sampel optimal yang sesuai ini diketahui untuk kasus agnostik?

gradstudent

Saya tidak berpikir kasus yang dapat diwujudkan adalah semua yang terkait. Dalam kasus yang dapat direalisasikan, ERM tidak menjamin tingkat yang optimal - karenanya semua kerja keras yang harus dikeluarkan Hanneke dan yang lainnya untuk menghapus faktor log, dan masih belum diketahui apakah pelajar yang tepat dapat mencapai tingkat yang optimal. Sebaliknya, dalam kasus agnostik, telah lama diketahui bahwa ERM mencapai tingkat optimal.

Aryeh