PAC Learning vs. Learning on Uniform Distribution

Question

La classe di funzione $ \ Mathcal {f} $ è PAC-Legreable se esiste un algoritmo $ a $ tale che per qualsiasi distribuzione $ d $ , qualsiasi funzione sconosciuta $ f $ e qualsiasi classe $ \ Epsilon, \ delta $ It tiene che esiste $ m $ che su un ingresso di $ m $ campioni IID $ (x, f (x)) $ dove < Span Class="Math-Container"> $ x \ SIM D $ , $ a $ ritorna, con probabilità più grande di $ 1- \ delta $ , una funzione che è $ \ epsilon $ -cly -cly to $ f $ (rispetto a $ d $ ). La classe $ \ Mathcal {f} $ è efficientemente PAC Intereabile se è PAC Intereabile, e $ A $ Esegui in tempo $ \ text {poly} (1 / \ Epsilon, 1 / \ delta, n) $ (dove $ | x |= n $ ) e la descrizione di $ f $ .

C'è un caso in cui una classe $ \ Mathcal {f} $ non è in modo efficiente Pac Learning, ma è in modo efficiente apprensibile sulla distribuzione uniforme?

Answer 1

.

C'è un caso in cui una classe $ \ Mathcal {f} $ non è in modo efficiente Pac Learning, ma è in modo efficiente apprensibile sulla distribuzione uniforme?

Questo è stato chiesto Tcs.se . Sembra che la risposta breve sia sì - Aaron Roth dà l'esempio di larghezza- $ k $ congiunzioni per $ k \ GG \ log n $ . E nei commenti, Avrim Blum è citato come la risposta di $ 2 $ -Term DNF.

Non capisco totalmente gli esempi lì - deve richiedere un po 'più di lavoro per derivare davvero il risultato (aggiornerò questa risposta se troverò una prova autonoma). Ma il problema generale qui con la distribuzione uniforme è che se la funzione di destinazione $ f $ è "sparse", il che significa che le etichette le siano le etichette al massimo a $ \ delta $ frazione della distribuzione di ingresso con $ 1 $ , quindi è facile imparare semplicemente indovinare Joinding $ 0 $ .

---

.

Oltre un apprendimento PAC del PAC efficiente (polinomiale), ci sono altri esempi in cui la distribuzione uniforme sembra aiutare. Ad esempio, un classico problema duro per l'apprendimento PAC è DNF, un problema che è congetturato per non essere PAC Intereabile, e piuttosto difficile. D'altra parte DNF DNF sulla distribuzione uniforme è quasi PAC LearnAble: abbiamo un algoritmo temporale qaussi per esso. Vedi Queste note e queste note .

In sintesi, sembra esserci molto lavoro sull'apprendimento sotto la distribuzione uniforme (Cerca "apprendimento PAC in una distribuzione uniforme" per ulteriori riferimenti). E sembra che questo problema sia più facile di studiare l'apprendimento del Pac, dove non siamo in grado di dimostrare molto. Citando le note di Ryan O'Donnell sopra:

.

General Pac-Learning insiste che un algoritmo funziona contemporaneamente per tutte le distribuzioni. Infatti, la comunità di apprendimento della macchina interessata alle applicazioni del mondo reale trova l'impostazione uniforme discutibile: "Ti assoceranno nel naso se si tenta di dire loro di algoritmi in questo Framework. "--Ryan. Ma, in un quadro più generale, nessuno può davvero dimostrare qualcosa.