Pembelajaran agnostik atas distribusi yang sewenang-wenang

Biarkan menjadi distribusi lebih dari bitstring / pasangan label dan biarkan menjadi kumpulan fungsi bernilai boolean . Untuk setiap fungsi , misalkan: dan biarkan: Katakan bahwa suatu algoritma agnostik mempelajari atas distribusi apa pun, jika untuk setiap ia dapat dengan probabilitas menemukan fungsi sedemikian rupa sehingga , diberikan waktu dan sejumlah sampel dari $D$ $\{0,1\}^d\times \{0,1\}$ $C$ $f:\{0,1\}^d\rightarrow\{0,1\}$ $f \in C$

e r r (f, D) = \underset{(x, y) \sim D}{Pr} [f (x) \neq y]

$err(f,D) = \Pr_{(x,y) \sim D}[f(x) \neq y]$

O P T (C, D) = min_{f \in C} e r r (f, D)

$OPT(C,D) = \min_{f \in C}\ err(f,D)$

A

$A$

C

$C$

D

$D$

2 / 3

$2/3$

f

$f$

e r r (f, D) \leq O P T (C, D) + ϵ

$err(f,D) \leq OPT(C,D) + \epsilon$

D

$D$ yang dibatasi oleh polinomial dalam

d

$d$ dan

1 / ϵ

$1/\epsilon$ .

Pertanyaan: Apa kelas fungsi $C$ yang diketahui dapat dipelajari secara agnostik dari distribusi yang sewenang-wenang?

Tidak ada kelas yang terlalu sederhana! Saya tahu bahwa konjungsi monoton pun tidak diketahui dapat dipelajari secara agnostik melalui distribusi yang sewenang-wenang, jadi saya hanya mencari kelas fungsi nontrivial.

reference-request machine-learning lg.learning Aaron Roth
sumber

Layak menunjukkan bagi yang belum tahu bahwa pembelajaran agnostik difokuskan pada kasus ketika OPT (C, D)> 0 (yaitu Anda memiliki kelas hipotesis yang salah

Suresh Venkat

Poin bagus. Dalam kasus khusus ketika OPT (C, D) = 0, ini adalah pembelajaran PAC, dan jauh lebih mudah. Untuk pembelajaran agnostik, jaminan harus berlaku tidak peduli apa OPT (C, D).

Aaron Roth

Ada juga kasus "PAC w / Klasifikasi Kebisingan" di mana OPT (C, D)> 0, dan meskipun Anda memiliki kelas hipotesis yang tepat (pengaturan dapat direalisasikan) ada beberapa kesalahan karena label dibalik secara acak karena kebisingan ... Saya Semoga nama pengaturan yang berbeda tidak membingungkan.

Lev Reyzin

yang terdengar seperti pembelajaran agnostik dengan batas atas pada OPT (C, D)

Suresh Venkat

Tidak cukup, karena noise tidak diperbolehkan sembarang dalam model noise klasifikasi. Jadi jika ada beberapa pola kebisingan permusuhan yang membuat pembelajaran (atau menemukan minimizer risiko empiris) sulit dalam model agnostik, itu mungkin tidak sering terjadi dalam model kebisingan klasifikasi (yaitu jatuh ke dalam parameter delta PAC).

Lev Reyzin

Jawaban:

Jika tidak ada kelas yang terlalu sederhana, maka di sini ada beberapa kelas yang dapat dipelajari secara agnostik PAC. Menanggapi komentar, kelas-kelas dengan banyak hipotesis secara acak dicoret:

~~pohon keputusan kedalaman konstan (dan kelas lainnya hanya memiliki banyak hipotesis)~~
~~hiperplanes dalam hipotesis (hanya menghasilkan label berbeda) $R^2$ $O(n^2)$~~
serikat interval (pemrograman dinamis)
paritas pada beberapa dari bit (lihat ini dan ini ) $\log(k)\log\log(k)$ $n$
~~kelas hipotesis lain dalam pengaturan dimensi rendah.~~

Hampir semua yang lain adalah NP-Hard untuk (setidaknya dengan benar) belajar PAC secara agnostik.

Tutorial Adam Kalai tentang pembelajaran agnostik juga mungkin menarik bagi Anda.

Lev Reyzin
sumber

Terima kasih. Jadi pohon keputusan kedalaman konstan, hyperplanes 2 dimensi, (saya menganggap pengaturan dimensi rendah lain yang Anda maksudkan) semuanya termasuk dalam kategori hanya memiliki banyak fungsi secara polinomi, yang dapat dipelajari dengan kelelahan. Paritas pada log (k) loglog (k) bit dan serikat interval menarik karena mengandung banyak fungsi superpolynomially. Apakah ada yang lain seperti ini?

Aaron Roth

Benar, meskipun ada banyak hiperplanes dalam R ^ 2, hanya O (n ^ 2) yang mengklasifikasikan titik data secara berbeda. Saya tidak tahu kelas menarik lainnya dari atas kepala saya, tetapi jika saya memikirkan / menemukan, saya akan mengedit jawaban saya.

Lev Reyzin

jadi Anda ingin kelas dimensi VC yang tidak terbatas?

Suresh Venkat

Dimensi VC tanpa batas pasti akan menarik, tetapi kelas terbatas (untuk fixed d) sudah sangat menarik (dan tampaknya jarang)

Aaron Roth

@LevReyzin Tautan kuliah Kalai tidak berfungsi. Bisakah Anda memperbaiki ini? Saya mencari di internet tetapi tidak bisa menemukan ini juga.

Anirbit