You are here

Algorithms watching (recommandation) algorithms

Team and supervisors
Department / Team: 
Team Web Site: 
https://www.inria.fr/equipes/wide
PhD Director
Erwan Le Merrer
Co-director(s), co-supervisor(s)
Contact(s)
PhD subject
Abstract

Les algorithmes de recommandation sont omniprésents dans nos
interactions en ligne. Ils personnalisent la navigation de
l'utilisateur et réduisent le flot d'information qui lui est
présenté. Ces algorithmes comptent e.g., pour 35% du revenu d'Amazon,
et sont donc des enjeux critiques pour ces entreprises. Par
conséquent, leur influence est majeure, et ils sont conservés comme
des secrets industriels (et ne sont disponible pour l'utilisateur que
via une interaction en "boite-noire"). De très nombreux travaux
académiques [6,7], ainsi qu'une conférence [8] ont été dédiés à
l'amélioration de ces algorithmes. A l'inverse, très peu de travaux
s'intéressent à l'envers du décors: quels sont les informations qu'un
utilisateur curieux ou consciencieux pourrait tirer de l'observation
et de l'analyse des recommandations qui lui sont faites?

Cette thèse va s'intéresser à l'automatisation de l'extraction
d'information des recommandations faites à un utilisateur ou groupe
d'utilisateurs. Des précédents ont montré la possibilité d'inférer des
données critiques sur des algorithmes s’exécutant chez des
fournisseurs de services, par de simples requêtes à la plateforme
[2,3,4].  Une fois ces recommandations stockées et représentées dans
une structure de donnée appropriée (comme une structure en graphe par
exemple [1,4]). L'étudiant pourra s'atteler à l'analyse de cette
structure, pour étudier les fuites d'information sur l'algorithme de
recommandation (e.g., les recommandations sont elles "biaisées" [1]?),
les informations personnelles contenues, la présence de bulles
informationnelles [5], etc. On pourra commencer l'étude par
simulation, en utilisant des jeux de données publics (e.g., Movielens)
et des algorithmes de recommandation présents dans une librairie
(e.g., surpr!se [9]), pour modéliser la boucle de feedback
clic/adaptation de la recommandation; la validation sur des

plateformes pourra ensuite voir lieu (YouTube, Amazon, ...).

L'on pourra alors cibler en finalité applicative la création de sondes
réparties sur un territoire, exécutant des algorithmes qui surveillent
l'état des recommandations faites aux utilisateurs d'un service donné.

/////// Problématiques scientifiques entrevues

* Peut on dériver une stratégie optimale de requétage de l'algorithme
  de recommandation, pour espérer limiter au maximum le coût de
  l'observation distante, au regard par exemple de requêtes purement
  aléatoires? La relation complexité-richesse de l'analyse semble
  cruciale pour limiter le nombre d'observations nécessaires pour
  fournir un résultat (approche d'observation parcimonieuse).

* Quelle structure de données est la mieux adaptée à la modélisation
  des recommandations à l'utilisateur? Est ce qu'une structure de type
  graphe [1] permettra des analyses suffisamment riches?

* Une fois une structure fixée, quels algorithmes pour l'analyser?

* Quelle information peut fuiter d'un petit nombre d'observations de
  sorties d'un algorithme de recommandation distant? Si de
  l'information fuite effectivement, en quoi cela pourrait aider à
  quantifier et à améliorer l'aspect vie privée des recommandations
  par le fournisseur de service?

* Peut on traiter le problème par des approches statistiques de type
  capture-recapture pour l'observation de recommandations précises?

* Preuves d'impossibilité: peut on prouver, en faisant e.g., le
  parallèle avec la confidentialité différentielle, qu'aucune fuite
  d'information ne peut se produire pour certaines classes
  d'algorithmes?

/////// Outils entrevus

* modélisation de comportement utilisateur
* extraction et fouille de données
* théorie des graphes
* probabilités / statistique
* Python et libraires pyppeteer, NetworkX, scikit learn, ...
- une base de code est déjà disponible pour le démarrage de la thèse

 

Bibliography

[1] The Topological Face of Recommendation, Erwan Le Merrer and Gilles
Trédan, Complex Networks 2017.

[2] Uncovering Influence Cookbooks : Reverse Engineering the Topological
Impact in Peer Ranking Services, Erwan Le Merrer and Gilles Trédan,
CSCW 2017.

[3] Stealing machine learning models via prediction APIs, Florian Tramèr
and Fan Zhang and Ari Juels and Michael K. Reiter and Thomas
Ristenpart, USENIX Security 2016.

[4] Inferring Networks From Random Walk-Based Node Similarities, Jeremy
Hoskins and Cameron Musco and Christopher Musco and Charalampos
Tsourakakis, NIPS 2019.

[5] Exploring the filter bubble: the effect of using recommender systems
on content diversity, Tien T. Nguyen and Pik-Mai Hui and F. Maxwell
Harper and Loren Terveen and Joseph A. Konstan, WWW 2014.

[6] Performance of Recommender Algorithms on Top-n Recommendation
Tasks, Cremonesi, Paolo and Koren, Yehuda and Turrin, Roberto, RecSys
2010.

[7] Collaborative Filtering Recommender Systems, Michael D. Ekstrand,
John T. Riedl and Joseph A. Konstan, Foundations and Trends in
Human–Computer Interaction: Vol. 4: No. 2, 2011.

[8] https://recsys.acm.org/

[9] http://surpriselib.com/

 

Work start date: 
dès que possible
Keywords: 
recommandations, vie privée, observations utilisateur, boite-noire, rétro-ingénierie, graphes, fuite d'information, audit sécurité.
Place: 
IRISA - Campus universitaire de Beaulieu, Rennes