Algorithmes de modèle de requête statistique?

13

J'ai posé cette question dans des questions- réponses validées de manière croisée, mais il semble qu'elle soit beaucoup plus liée à CS qu'aux statistiques.

Pouvez-vous me donner des exemples d'algorithmes d'apprentissage automatique qui apprennent des propriétés statistiques de l'ensemble de données et non des observations individuelles elles-mêmes, c'est-à-dire qui utilisent le modèle de requête statistique ?

Deyaa
la source
1
quel est le modèle de requête statistique?
Suresh Venkat
de Kearns paper portal.acm.org/citation.cfm?doid=293347.293351 : "dans ce modèle, un algorithme d'apprentissage est interdit d'examiner des exemples individuels de la fonction cible inconnue, mais il est donné accès à un oracle fournissant des estimations des probabilités sur l'échantillon espace d'exemples aléatoires. ". désolé si ce n'est pas évident, j'ai mis à jour ma question avec le lien vers le papier
Deyaa

Réponses:

14

Presque tous les algorithmes qui fonctionnent dans le modèle PAC (à l'exception des algorithmes d'apprentissage de parité) peuvent être conçus pour fonctionner dans le modèle SQ. Voir par exemple cet article de Blum et al. dans lequel plusieurs algorithmes populaires sont traduits dans leurs équivalents SQ ( Practical Privacy: le framework SuLQ ). Le papier s'intéresse en principe à la "confidentialité", mais vous pouvez l'ignorer - il s'agit vraiment d'implémenter des algorithmes avec des requêtes SQ.

L'apprentissage agnostique, d'autre part, est beaucoup plus difficile dans le modèle SQ: les problèmes de calcul mis à part (bien qu'ils soient importants), la complexité de l'échantillon requise pour l'apprentissage agnostique est à peu près la même que celle requise pour l'apprentissage exact, si vous avez réellement accès à les points de données. D'un autre côté, l'apprentissage agnostique devient beaucoup plus difficile dans le modèle SQ - vous devrez généralement effectuer de nombreuses requêtes superpolynomiales, même pour des classes aussi simples que des disjonctions monotones. Voir cet article de Feldman ( Une caractérisation complète de l'apprentissage des requêtes statistiques avec des applications à l'évolutivité ) ou cet article récent de Gupta et al. ( Conjonctions à libération privée et barrière de requête statistique )

Aaron Roth
la source
vraiment belle réponse Aaron :) merci beaucoup :)
Deyaa
7

Le modèle SQ a été conçu pour analyser l'apprentissage tolérant au bruit - à savoir un algorithme qui fonctionne en faisant des requêtes statistiques fonctionnera sous le bruit de classification. Comme l'a dit Aaron, la plupart des algorithmes PAC que nous avons se révèlent avoir des équivalents dans le modèle SQ. La seule exception est l'élimination gaussienne, qui est utilisée dans l'apprentissage des parités (on peut même en utiliser une application intelligentepour apprendre les parités de taille log (n) loglog (n) dans le modèle de bruit de classification). Nous savons également que les parités ne peuvent pas être apprises avec des requêtes statistiques, et il s'avère que les classes les plus intéressantes comme les arbres de décision peuvent simuler des fonctions de parité. Donc, dans notre quête pour obtenir des algorithmes d'apprentissage PAC pour de nombreuses classes intéressantes (comme les arbres de décision, DNF, etc.), nous savons que nous avons besoin d'algorithmes d'apprentissage fondamentalement nouveaux qui ne fonctionnent pas dans le modèle de requête statistique.

Lev Reyzin
la source
Intéressant. Avez-vous une référence selon laquelle les parités ne peuvent pas être apprises dans le modèle SQ?
M. Alaggan
1
cela a été prouvé par Kearns dans son article original définissant le modèle: portal.acm.org/citation.cfm?doid=293347.293351 , puis montré à nouveau par Blum et al où ils ont défini la dimension SQ d'une classe portal.acm.org/citation .cfm? id = 195058.195147 . Fondamentalement, l'argument est le suivant: les parités sont "indépendantes par paire" par rapport à la distribution uniforme, donc vous devez à peu près deviner la parité correcte pour apprendre quoi que ce soit, et il y a beaucoup de parités possibles ...
Lev Reyzin
5

Je voudrais clarifier légèrement la réponse d'Aaron. Presque tous les algorithmes agnostiques (encore une fois, à l'exception de tout ce qui utilise l'élimination gaussienne) peuvent fonctionner pour fonctionner dans le modèle SQ. Naturellement, l'apprentissage agnostique est plus difficile que l'apprentissage non agnostique, mais c'est une question indépendante.

user5591
la source
/ϵ2