Cold start

La cold start (partenza a freddo) è un problema cui sono soggetti gli algoritmi informatici dei sistemi informativi che si basano su modellazione dei dati, quali i sistemi di raccomandazione, che si verifica quando il sistema non è in grado di fare alcuna inferenza per utenti o articoli (libri, film, prodotti...) sui quali non ha ancora raccolto sufficienti informazioni.

Sistemi coinvolti

La partenza a freddo è un problema ben noto e oggetto di significativa ricerca nel settore dei sistemi di raccomandazione. I sistemi di raccomandazione sono una specifica famiglia di sistemi per il filtraggio delle informazioni il cui scopo è presentare all'utente gli articoli (commercio elettronico, film, musica, libri, notizie, immagini, pagine internet) che più probabilmente risulteranno di suo interesse tra tutti quelli presenti nel catalogo. Solitamente un sistema di raccomandazione compara il profilo utente a dei dati di riferimento. Tali dati possono essere o attributi dell'articolo (filtraggio basato sul contenuto) oppure essere relativi alle passate interazioni e attività dell'utente (filtraggio collaborativo). A seconda della natura del sistema, l'utente può essere associato a diversi tipi d'interazione: votazione, articoli preferiti, acquisti, like, numero di visite alla pagina ecc.

Ci sono tre casi di partenza a freddo[1]:

  • Nuova comunità: si riferisce all'avvio del sistema di raccomandazione, laddove, sebbene un catalogo di articoli possa esistere, quasi nessun utente è presente e la mancanza di interazioni rende molto difficile fornire raccomandazioni in modo affidabile.
  • Nuovo articolo: un nuovo articolo è aggiunto al catalogo e, sebbene possa avere associate informazioni sul suo contenuto, non è stato oggetto di alcuna interazione da parte degli utenti.
  • Nuovo utente: un nuovo utente si registra al sistema e non ha ancora fornito alcuna interazione, pertanto non è possibile offrirgli raccomandazioni personalizzate.

Nuova comunità

La partenza a freddo nel caso di nuova comunità (o bootstrap del sistema) si riferisce al momento di avvio del sistema, laddove sostanzialmente nessun tipo di interazione o utenti siano presenti e il sistema di raccomandazione non ha alcuna informazione su cui basarsi. Questo caso accomuna gli svantaggi sia del caso di nuovi articoli sia del caso di nuovi utenti, poiché entrambi saranno privi di interazioni. A causa di ciò, alcune delle tecniche sviluppate per affrontare i nuovi utenti o articoli potrebbero non essere applicabili in questo caso.

Nuovo articolo

In caso di nuovo articolo la partenza a freddo si riferisce all'aggiunta di un articolo al catalogo, laddove esso abbia ottenuto poche o nessuna interazione. Ciò costituisce un problema principalmente nel caso del filtraggio collaborativo, poiché questa famiglia di algoritmi determina la rilevanza di un articolo proprio in base alle sue interazioni. Se nessuna interazione è disponibile allora un algoritmo collaborativo puro non sarà in grado di raccomandare l'articolo a nessuno; nel caso in cui invece siano disponibili solo alcune interazioni, sebbene un algoritmo collaborativo sarà in grado di raccomandarlo, la qualità di tali raccomandazioni sarà molto scarsa[2]. Ciò evidenzia un altro problema che non riguarda più i nuovi articoli strettamente parlando, ma tutti gli articoli poco popolari. In alcuni casi (p. es. raccomandazioni di film) capita che un limitato gruppo di articoli riceva un altissimo numero di interazioni, e la maggior parte degli altri ne riceva solo una piccola frazione: in letteratura questo sbilanciamento nel numero di interazioni è chiamato popularity bias[3].

Numero di interazioni associate a ciascun articolo nell'insieme di dati Movielens. Pochi articoli hanno raccolto molte interazioni, oltre 5000, laddove la maggior parte degli altri ne ha meno di 100.

In quest'ambito la popularity bias è importante poiché, sebbene un articolo sia stato nel catalogo per mesi, potrà comunque aver ricevuto solo poche interazioni: ciò crea un circolo vizioso nel quale articoli poco popolari saranno raccomandati male (quindi agli utenti sbagliati) e quindi avranno molta meno visibilità degli articoli popolari, rendendo difficile ricevano nuove interazioni[4]. Sebbene sia atteso che alcuni articoli risultino meno popolari di altri, la partenza a freddo si riferisce in modo specifico ai casi in cui il sistema di raccomandazione non abbia abbastanza dati per poter raccomandare tali articoli in modo affidabile[5].

I sistemi di raccomandazione, d'altro canto, sono in teoria molto meno soggetti al problema dei nuovi articoli. Poiché gli algoritmi basati sul contenuto scelgono quali articoli raccomandare sulla base dei loro attributi, anche se l'articolo non ha ricevuto nessuna interazione, i suoi attributi consentiranno di effettuare una raccomandazione[6]. Con ciò naturalmente si assume che i nuovi articoli siano descritti dai loro attributi, il che non sempre avviene: gli attributi editoriali (p. es. direttore, attori, titolo, anno) saranno sempre noti nel momento in cui l'articolo è aggiunto al catalogo, tuttavia altri tipi di attributi potrebbero non esserlo, per esempio quelli estratti dalle recensioni o dalle etichette fornite dagli utenti[7]. Algoritmi basati sul contenuto che si appoggino ad attributi forniti dall'utente saranno comunque soggetti alla partenza a freddo, poiché se nessuna (o poche) interazioni sono avvenute, nessuna (o poche) recensione o etichetta sarà stata inserita.

Nuovo utente

Questo caso di partenza a freddo si riferisce al momento in cui un nuovo utente si iscrive sul sistema e per un certo periodo di tempo il sistema di raccomandazione deve offrire raccomandazioni senza potersi affidare alle passate interazioni dell'utente, poiché nessuna è ancora avvenuta[1]. Questo problema è particolarmente delicato laddove il sistema di raccomandazione sia una parte importante del servizio offerto, poiché un utente che riceva raccomandazioni di scarsa qualità potrebbe rapidamente decidere di smettere di utilizzare il sistema prima che esso riesca a raccogliere le interazioni di cui ha bisogno per modellare gli interessi dell'utente e produrre raccomandazioni affidabili. La strategia principale che si adotta per gestire il caso del nuovo utente è di chiedere loro di fornire alcune preferenze iniziali per costruire il loro profilo utente e che saranno usate come riferimento. Un punto di incontro dev'essere individuato tra la lunghezza del processo di registrazione, che se troppo lungo potrebbe scoraggiare l'utente inducendone un numero troppo alto a rinunciare, e la quantità di informazioni di cui l'algoritmo di raccomandazione ha bisogno prima di poter funzionare adeguatamente[8].

Analogamente al caso del nuovo articolo, non tutti gli algoritmi ne sono affetti allo stesso modo. Algoritmi di raccomandazione articolo-articolo ne saranno soggetti in quanto si basano sul profilo per pesare quanto rilevanti sono le preferenze di altri utenti rispetto a quello corrente. Gli algoritmi di filtraggio collaborativo sono i maggiormente affetti, in quanto senza interazioni non sono in grado di produrre nessuna inferenza sulle preferenze dell'utente e quindi non possono produrre alcuna raccomandazione. Gli algoritmi utente-utente[9] invece si comportano in modo diverso: un algoritmo utente-utente che si basa sugli attributi dell'utente (per es. età, genere, provenienza) per individuare utenti simili e raccomandare gli articoli con cui essi hanno interagito in modo positivo, pertanto sarà robusto rispetto ai nuovi utenti e poco affetto dalla partenza a freddo. È utile ricordare che tutte queste informazioni devono essere raccolte durante il processo di registrazione, o richiedendole esplicitamente all'utente oppure sfruttando dati già disponibili in altre fonti, per esempio i suoi profili sulle reti sociali[10].

Strategie di mitigazione

A causa del vasto numero di algoritmi di raccomandazione disponibili così come della grande variabilità nelle caratteristiche del servizio e delle interazioni, diverse strategie sono state sviluppate per mitigare il problema del cold start. Solitamente ci si affida ad algoritmi di raccomandazione ibridi, in modo da combinare due o più categorie di algoritmi per mitigare i reciproci svantaggi.[11][12][13]

Tutte le tre categorie di cold-start (nuova community, nuovo, item, nuovo utente) sono accomunati dalla mancanza di interazioni e pertanto in alcuni casi possono essere affrontati con strategie simili.

Una strategia comune utilizzata per gestire i nuovi item è associare ad un collaborative filtering, per item già noti, un content-based filtering, per nuovi item. I due algoritmi possono essere combinati in molti modi, tuttavia il limite più forte di queste tecniche è legato alla scarsa qualità delle raccomandazioni prodotte dall'algoritmo content-based laddove sia difficile ottenere una descrizione accurata dell'articolo. Nel caso di nuovi utenti, se non sono disponibili informazioni demografiche (es. età, sesso, professione, stato) o la loro qualità è scarsa, una scelta comune è di sostituire l'algoritmo content effettuando raccomandazioni non personalizzate. Ciò vuol dire, ad esempio, raccomandare gli item più popolari globalmente o per paese, lingua...

Arricchimento del profilo

Una delle possibili strategie per gestire nuovi item o user è cercare di acquisire rapidamente dati relativi alle loro preferenze. Ci sono vari modi per farlo a seconda della quantità di dati richiesti, queste tecniche sono chiamate in letteratura preference elicitation.[14][15] La raccolta di interazioni può essere fatta sia in modo esplicito (es. chiedendo all'utente) oppure in modo implicito (es. osservando il suo comportamento). In entrambi i casi ciò implica che l'utente dovrà dedicare un certo tempo ad utilizzare il sistema di raccomandazione, per lui ancora non affidabile, in modo da fornirgli le informazioni necessarie.[16]

Sebbene le strategie di questo tipo siano semplici ed efficaci per la raccolta dei dati, esse rendono il processo di registrazione più lungo e laborioso per l'utente. Inoltre la qualità dei dati ottenuti potrebbe non essere ottimale, in quanto l'utente potrebbe indicare rating per film che ha visto mesi o anni prima, oppure fornirli in modo quasi casuale per poter completare la registrazione velocemente.

La costruzione del profilo utente può anche essere automatizzata integrando informazioni da altre attività, quali piattaforme social o navigazione internet. Ad esempio un utente che abbia cercato informazioni su uno specifico musicista su un portale potrà automaticamente ricevere raccomandazioni relative a quell'artista quando visiterà un servizio che offra musica.[17]

Una variante del precedente approccio è di assegnare automaticamente i rating ai nuovi item in base ai rating che la community di utenti ha assegnato ad item simili. La similarità sarà determinata in base agli attributi content dell'item.

È anche possibile creare il profilo iniziale dell'utente in base a delle informazioni sulla personalità.[18][19] dell'utente, che possono essere identificate e rappresentante tramite modelli quali il five factor model (FFM).

Un'altra delle possibili tecniche è l'applicare l'active learning. Lo scopo principale dell'active learning è di guidare l'utente in modo che esprima delle preferenze/interazioni che siano le più informative possibile per il sistema di raccomandazione. Ciò richiede di analizzare i dati disponibili e stimare l'utilità dei dati non ancora disponibili (es., rating, interazioni).[20] Ad esempio, poniamo di voler dividere una certa nuvola di punti in due cluster. Una volta che abbiamo individuato due punti appartenenti ciascuno ad un diverso cluster, qual è il punto più informativo che possiamo andare a verificare? Se scegliessimo un punto vicino a quelli che conosciamo probabilmente lo scopriremmo appartenere allo stesso cluster. Invece, scegliendo un punto a metà strada tra i due potremmo riuscire ad individuare dove si colloca il confine tra i due cluster potendo classificare un gran numero di altri punti senza bisogno di osservarli.

Il cold-start è un problema presente anche nel caso di agenti intelligenti. Poiché questi agenti tipicamente imparano le preferenze dell'utente osservando il suo comportamento, impiegherebbero tempo prima che l'agente sia in grado di personalizzarsi. A quel punto, la sua efficacia sarebbe comunque limitata ai casi ed attività che ha già potuto osservare tramite l'utente.[21] Il problema del cold start può essere mitigato introducendo una forma di collaborazione tra agenti relativi a diversi utenti. In questo modo, nuove situazioni possono essere gestite condividendo quanto imparato da altri agenti tramite i rispettivi utenti.

Mappatura delle feature

Recentemente sono state proposte diverse strategie che si appoggiano al machine learning con l'obiettivo di fondere informazioni di tipo content e collaborativo in un singolo modello. A titolo di esempio uno di questi approcci è chiamato attribute to feature mapping[22] sviluppato per algoritmi di matrix factorization.[23] L'idea alla base è la seguente. Un sistema di raccomandazione che usi la fattorizzazione di matrice rappresenta le interazioni utente-item sotto forma del prodotto di due matrici rettangolari il cui contenuto è imparato tramite machine learning. Ogni utente sarà associato ad una riga della prima matrice ed ogni item ad una colonna della seconda matrice. La riga o colonna associata ad un utente o item è chiamata fattori latenti.[24] Quando viene aggiunto un nuovo item esso non è associato ad alcun fattore latente e la mancanza di interazioni non permette di impararli come è stato fatto per gli altri item già noti. Se ogni item è associato ad alcune feature (es. autore, anno, casa editrice, attori, titolo) è possibile definire una funzione che, date le feature dell'item, stimi i suoi fattori latenti. La funzione può assumere molte forme e sarà addestrata sui dati degli item già noti. La stessa idea si può applicare nel caso di nuovi utenti, poiché se essi hanno fornito alcune informazioni (es. età, nazionalità, genere) allora anche i loro fattori latenti possono essere stimati.

Pesi delle feature ibridi

Un altro approccio che presenta delle similarità con la mappatura delle feature, riguarda la creazione di un algoritmo content-based filtering ibrido nel quale le feature dell'item o dell'utente siano pesate in base alla sua percezione dell'importanza che hanno nella scelta. Quando l'utente deve scegliere un film o item di suo interesse, diverse feature (e.g. attori, paese di origine, regista, titolo) avranno diversa importanza. Per esempio si considerino i film su James bond, l'attore principale è cambiato molte volte nel corso degli anni, mentre altri no, come ad esempio Lois Maxwell. Per questo motivo la sua presenza sarà probabilmente una caratteristica di maggiore importanza per identificare quel tipo di film rispetto alla presenza di uno dei vari attori principali.[25][26] Sebbene esistano molte tecniche per calcolare i pesi delle feature in sistemi di raccomandazione, molti di questi metodi sono stati sviluppati per l'information retrieval quali tf–idf, Okapi BM25, solo pochi sono stati pensati specificamente per i sistemi di raccomandazione.[27]

Le tecniche per individuare i pesi delle feature ibride usate in ambito cold-start, in particolare, sono state sviluppate espressamente per i sistemi di raccomandazione. Alcune di esse imparano i pesi delle feature basandosi direttamente sulle interazioni effettuate dall'utente, come FBSM.[26] Altre si appoggiano ad un modello collaborativo intermedio, addestrato sugli item già noti, ed imparano i pesi delle feature in modo da approssimare il modello collaborativo al meglio, pur usando un algoritmo content.[25]

Molto di questi metodi ibridi possono essere considerati come casi speciali di factorization machines.[28][29]

Note

  1. ^ a b Jesús Bobadilla, Fernando Ortega, Antonio Hernando e Jesús Bernal, A collaborative filtering approach to mitigate the new user cold start problem, in Knowledge-Based Systems, vol. 26, febbraio 2012, pp. 225-238, DOI:10.1016/j.knosys.2011.07.021.
  2. ^ Blerina Lika, Kostas Kolomvatsos e Stathes Hadjiefthymiades, Facing the cold start problem in recommender systems, in Expert Systems with Applications, vol. 41, n. 4, marzo 2014, pp. 2065-2073, DOI:10.1016/j.eswa.2013.09.005.
  3. ^ Lei Hou, Xue Pan e Kecheng Liu, Balancing the popularity bias of object similarities for personalised recommendation, in The European Physical Journal B, vol. 91, n. 3, 7 marzo 2018, DOI:10.1140/epjb/e2018-80374-8.
  4. ^ Himan Abdollahpouri, Robin Burke e Bamshad Mobasher, Controlling Popularity Bias in Learning-to-Rank Recommendation, ACM, 27 agosto 2017, pp. 42-46, DOI:10.1145/3109859.3109912.
  5. ^ Yoon-Joo Park e Alexander Tuzhilin, The long tail of recommender systems and how to leverage it, ACM, 23 ottobre 2008, pp. 11-18, DOI:10.1145/1454008.1454012.
  6. ^ (EN) Michael J. Pazzani e Daniel Billsus, Content-Based Recommendation Systems, in The Adaptive Web, Springer Berlin Heidelberg, 2007, pp. 325-341, DOI:10.1007/978-3-540-72079-9_10.
  7. ^ Li Chen, Guanliang Chen e Feng Wang, Recommender systems based on user reviews: the state of the art, in User Modeling and User-Adapted Interaction, vol. 25, n. 2, 22 gennaio 2015, pp. 99-154, DOI:10.1007/s11257-015-9155-5.
  8. ^ Al Mamunur Rashid, George Karypis e John Riedl, Learning preferences of new users in recommender systems, in ACM SIGKDD Explorations Newsletter, vol. 10, n. 2, 20 dicembre 2008, p. 90, DOI:10.1145/1540276.1540302.
  9. ^ J. Bobadilla, F. Ortega, A. Hernando e A. Gutiérrez, Recommender systems survey, in Knowledge-Based Systems, vol. 46, luglio 2013, pp. 109-132, DOI:10.1016/j.knosys.2013.03.012.
  10. ^ Zi-Ke Zhang, Chuang Liu, Yi-Cheng Zhang e Tao Zhou, Solving the cold-start problem in recommender systems with social tags, in EPL (Europhysics Letters), vol. 92, n. 2, 1º ottobre 2010, p. 28002, DOI:10.1209/0295-5075/92/28002.
  11. ^ Zan Huang, Hsinchun Chen e Daniel Zeng, Applying associative retrieval techniques to alleviate the sparsity problem in collaborative filtering, in ACM Transactions on Information Systems, vol. 22, n. 1, 1º gennaio 2004, pp. 116-142, DOI:10.1145/963770.963775.
  12. ^ J. Salter e N. Antonopoulos, CinemaScreen Recommender Agent: Combining Collaborative and Content-Based Filtering, in IEEE Intelligent Systems, vol. 21, n. 1, gennaio 2006, pp. 35-41, DOI:10.1109/MIS.2006.4.
  13. ^ (EN) Robin Burke, Hybrid Web Recommender Systems, in The Adaptive Web, Springer Berlin Heidelberg, 2007, pp. 377-408, DOI:10.1007/978-3-540-72079-9_12.
  14. ^ Mehdi Elahi, Francesco Ricci e Neil Rubens, Active Learning in Collaborative Filtering Recommender Systems, Springer International Publishing, pp. 113-124, ISBN 978-3-319-10491-1.
  15. ^ Mehdi Elahi, Francesco Ricci e Neil Rubens, A survey of active learning in collaborative filtering recommender systems, Computer Science Review, 2016. Ospitato su Elsevier.
  16. ^ Andrew I. Schein, Alexandrin Popescul, Lyle H. Ungar e David M. Pennock, Methods and Metrics for Cold-Start Recommendations, Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 2002), New York City, New York, ACM, 2002, pp. 253-260, ISBN 1-58113-561-0. URL consultato il 2 febbraio 2008.
  17. ^ Vendor attempts to crack 'cold start' problem in content recommendations (PDF), in Mobile Media, United Kingdom, Informa Telecoms & Media, 29 giugno 2007, p. 18. URL consultato il 2 febbraio 2008 (archiviato dall'url originale il 1º agosto 2008).
  18. ^ Marko Tkalcic e Li Chen, Personality and Recommender Systems, in Francesco Ricci, Lior Rokach e Bracha Shapira (a cura di), Recommender Systems Handbook, 2nd, Springer US, 2016, ISBN 978-1-4899-7637-6.
  19. ^ Ignacio Fernández-Tobías, Matthias Braunhofer, Mehdi Elahi, Francesco Ricci e Iván Cantador, Alleviating the new user problem in collaborative filtering by exploiting personality information, in User Modeling and User-Adapted Interaction, 2016, DOI:10.1007/s11257-016-9172-z.
  20. ^ Neil Rubens, Mehdi Elahi, Masashi Sugiyama e Dain Kaplan, Active Learning in Recommender Systems, in Francesco Ricci, Lior Rokach e Bracha Shapira (a cura di), Recommender Systems Handbook, 2nd, Springer US, 2016, ISBN 978-1-4899-7637-6.
  21. ^ Yezdi Lashkari, Max Metral e Pattie Maes, Collaborative Interface Agents, Proceedings of the Twelfth National Conference on Artificial Intelligence, Seattle, Washington, AAAI Press, 1994, pp. 444-449, ISBN 0-262-61102-3. URL consultato il 2 febbraio 2008.
  22. ^ Zeno Gantner, Lucas Drumond e Cristoph Freudenthaler, Learning Attribute-to-Feature Mappings for Cold-Start Recommendations, 20 gennaio 2011, DOI:10.1109/ICDM.2010.129.
  23. ^ Yehuda Koren, Robert Bell e Chris Volinsky, Matrix Factorization Techniques for Recommender Systems, in Computer, vol. 42, n. 8, agosto 2009, pp. 30-37, DOI:10.1109/MC.2009.263.
  24. ^ Deepak Agarwal e Bee-Chung Chen, Regression-based latent factor models, ACM, 28 giugno 2009, pp. 19-28, DOI:10.1145/1557019.1557029.
  25. ^ a b Leonardo Cella, Stefano Cereda, Massimo Quadrana e Paolo Cremonesi, Deriving Item Features Relevance from Past User Interactions, in UMAP '17 Proceedings of the 25th Conference on User Modeling, Adaptation and Personalization, 2017, pp. 275-279, DOI:10.1145/3079628.3079695.
  26. ^ a b Mohit Sharma, Jiayu Zhou, Junling Hu e George Karypis, Feature-based factorized Bilinear Similarity Model for Cold-Start Top-n Item Recommendation, in Proceedings of the 2015 SIAM International Conference on Data Mining, 2015, DOI:10.1137/1.9781611974010.22.
  27. ^ (EN) Panagiotis Symeonidis, Alexandros Nanopoulos e Yannis Manolopoulos, Feature-Weighted User Model for Recommender Systems, in User Modeling 2007, Springer Berlin Heidelberg, 25 luglio 2007, pp. 97-106, DOI:10.1007/978-3-540-73078-1_13.
  28. ^ Steffen Rendle, Factorization Machines with libFM, in ACM Transactions on Intelligent Systems and Technology, vol. 3, n. 3, 1º maggio 2012, pp. 1-22, DOI:10.1145/2168752.2168771.
  29. ^ Steffen Rendle, Factorization Machines, IEEE, 2010, ISBN 978-1-4244-9131-5.

Voci correlate

Collegamenti esterni

  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica