Machine Learning / Progetti
Come usare il Machine Learning per costruire un motore di ricerca per Pokémon — pt. 1
Ovvero: come abbiamo unito la passione per i Pokémon e quella per il Machine Learning in un solo progetto — from scratch!
Questo articolo è un adattamento abbastanza fedele (solo lievemente più corto) del workshop che con Datamasters.it abbiamo proposto all’edizione 2022 del Pycon Italia, l’edizione italiana della conferenza tech dedicata al linguaggio Python. Essere responsabili del Beginners’Day, il workshop dedicato a chi vuole avvicinarsi per la prima volta al mondo di Python, è stato un onore e un vero piacere. Non vediamo l’ora che arrivi la prossima edizione!
Ad ogni modo, il progetto che abbiamo deciso di proporre ai neofiti di Python è stato lo sviluppo from scratch (cioè da zero) di un motore di ricerca di Pokémon, che al suo interno sfrutti l’algoritmo di Machine Learning KNN, anch’esso implementato from scratch. Come funzionerà il nostro motore di ricerca? Be’innanzitutto chiedendo un input all’utente, poi prendendo quegli input e cercando quale pokemon somiglia di più a quell’input, infine mostrando all’utente i risultati della ricerca. Facile, no?
In realtà le cose sono un po’meno semplici di così. La frase descrittiva del nostro motore di ricerca è super generica e quindi super ambigua, e oltretutto si potrebbe riferire ad un programma qualsiasi (il classico flusso di un programma dopotutto è: acquisizione input — elaborazione dell’input — restituzione dell’output). Prima di iniziare a sviluppare qualcosa di concreto dobbiamo capire meglio alcune cose. Per fare questo dovremo prima rispondere ad un paio di domande:
- Cosa è un Pokémon?
- Quale input dovrà inserire l’utente?
- Qual è l’output che ci aspettiamo?
- Come facciamo a capire quali sono i Pokémon che somigliano di più all’input dell’utente?
- Cosa vogliamo mostrare all’utente? Come facciamo ad ordinare per “somiglianza” i Pokémon?
Procediamo dunque con ordine, prima di capire come sviluppare il nostro motore di ricerca, e cerchiamo una risposta alla prima domanda:
Cosa è un Pokémon?
Nella remota ipotesi in cui non sappiate che cos’è un Pokémon, ecco la pagina di Wikipedia a loro dedicata, la homepage della loro fandom, il loro sito ufficiale, la pagina facebook ufficiale con 7.5 milioni di follower. Insomma, c’è davvero tanto in giro se volete documentarvi. Molto più probabile che conosciate i Pokémon per l’anime o per i fantastici videogiochi per Game Boy, sui quali mi fregio di aver passato svariate ore della mia ormai andata adolescenza e giovinezza (*sigh*). Ad ogni modo, la cosa che ci interessa è che un Pokémon è una specie di mostriciattolo che è possibile catturare, allenare, far evolvere e (soprattutto) far combattere con altri Pokémon per renderlo più forte. Più forte, eh? E di quanto? E che significa far evolvere un Pokémon? Approfondiamo la questione. Dopo aver cliccato sul rispettivo pulsante dal loro sito ufficiale, ci imbattiamo nel Pokédex, un vero e proprio database in cui troviamo informazioni su tutti i Pokémon disponibili. Clicchiamo su un Pokémon a caso (Bulbasaur, ad esempio) e verrà fuori che ad un Pokémon sono associati dei dati come peso, altezza, tipologia (Erba, Terra, Psico, Fuoco, Lotta, etc; molti Pokémon hanno anche una tipologia secondaria), e dei punteggi:
- HP (punti vita)
- Punti attacco
- Punti difesa
- Punti attacco speciale
- Punti difesa speciale
- Velocità
Dopo una rapida occhiata ad altri Pokémon salta subito fuori che questi dati (ovviamente con valori diversi) sono associati a tutti i Pokémon. Bene! Siamo adesso in grado di capire meglio cosa è un Pokémon, quali sono i suoi attributi fondamentali e — soprattutto — quali sono i suoi punteggi. Potremmo chiederci, a questo punto: ok, ma dove prendo tutti i dati di tutti i Pokémon esistenti (che sono più di 800)? Potremmo immaginare che ci sia una dolce scimmietta che clicca su ciascuna delle voci presenti nel Pokédex presenti nel sito ufficiale, ma — hey — siamo nel 2022, e grazie al cielo esistono soluzioni molto più rapide. Su Kaggle, una piattaforma che chi mastica un po’di Machine Learning conosce a menadito, esistono decine di dataset liberamente scaricabili contenenti tutti i dati di tutti i Pokémon, comodamente in formato CSV (per chi non conoscesse il formato, CSV sta per Comma Separated Values, ed è semplicemente un modo “universale” per rappresentare dei dati in forma tabellare all’interno di un file di testo semplice, uno di quelli che create con Blocco Note, per intenderci). Ne scegliamo uno: questo. Le colonne presenti nel dataset (detti nel mondo del machine learning anche features) sono:
- #: ID nel Pokédex (molto importante: è un attributo univoco, cioè diverso per ogni Pokémon)
- Name: Nome
- Type 1: Ogni pokémon ha almeno 1 tipo, che determina resistenze o debolezze a certi tipi di attacchi
- Type 2: Alcuni pokémon hanno 2 tipi
- Total: somma di tutti i punteggi successivi
- HP: hit points
- Attack: il modificatore di base per gli attacchi di tipo normale
- Defense: la resistenza agli attacchi di tipo normale
- SP Atk: un modificatore di base per gli attacchi speciali
- SP Def: indica la resistenza agli attacchi speciali
- Speed: serve a capire chi attacca per primo
- Generation: numero di generazione di appartenenza (ci sono 7 generazioni di Pokémon)
Possiamo andare oltre e rispondere alla prossima domanda.
Quale input dovrà inserire l’utente?
Ora che sappiamo come è fatto un Pokémon possiamo iniziare a capire meglio come dovrebbe funzionare il nostro motore di ricerca. Potremmo chiedere in input all’utente delle informazioni come ad esempio un nome, oppure una tipologia, e far restituire al nostro motore di ricerca i Pokémon il cui nome somiglia a quello inserito dall’utente, o tutti i Pokémon di una determinata categoria; tuttavia decidiamo di chiedere all’utente 6 numeri. Questi numeri rappresenteranno valori corrispondenti ai punteggi di cui ciascun Pokémon dispone già, e che sono diversi da Pokémon a Pokémon: HP, attacco, difesa, attacco speciale, difesa speciale e velocità. Il motore di ricerca quindi cercherà i Pokémon con i punteggi più vicini ai 6 valori inseriti in input dall’utente.
Qual è l’output che ci aspettiamo?
Un motore di ricerca funziona mostrando una serie ordinata di risultati. Rileggiamo: una serie ordinata di risultati. Nel nostro caso un singolo risultato potrebbe essere un singolo Pokémon. Se facessimo in questa maniera, il nostro motore di ricerca restituirebbe come output una serie di Pokémon. Pensateci, ha senso: l’utente inserisce dei numeri, che rappresentano dei punteggi particolari per HP, attacco, etc etc, e riceve in output una serie di Pokémon, i più simili ai valori appena inseriti. E per quanto riguarda la parte di ordinamento? Stiamo lavorando con dei numeri, quindi il primo risultato sarà il Pokémon più simile ai valori inseriti, il secondo risultato sarà il secondo Pokémon più simile ai valori inseriti, e così via. Altra questione: quanti risultati vogliamo? Ovvero: quanti Pokémon vogliamo mostrare all’utente? Tutti e 800? Be’, se così facessimo il nostro motore di ricerca sarebbe quantomeno scomodo da utilizzare: 800 Pokémon non ci entrano in uno schermo. Meglio limitare i risultati. Meglio mostrare una lista di lunghezza predefinita di Pokémon. Una lista di lunghezza `K`, dove K è un numero intero. Ad esempio, se K = 5, ecco uno schema riassuntivo di quello che dovrebbe fare il nostro motore di ricerca:
Facile, no? L’utente inserisce 6 valori numerici, il nostro algoritmo fa cose™, in output riceviamo una lista di K Pokémon. Ci sta. Andiamo avanti.
Come facciamo a capire quali sono i Pokémon che somigliano di più all’input dell’utente?
Ora viene il bello. Rispondere a questa domanda sostanzialmente significa progettare l’algoritmo del nostro motore di ricerca. Va da sè che questa è la parte più corposa del nostro progetto, quindi tanto vale partire subito. Cosa abbiamo, in mano? Fissiamo i concetti. Abbiamo:
- un input formato da 6 numeri
- un algoritmo che fa cose™
- un output formato da una serie ordinata di Pokémon
O, se preferiamo, possiamo dire che il nostro utente inserisce dei dati di un Pokémon fittizio, che per pura assonanza con il nome dell’autore chiameremo Pepposaur, un Pokémon selvatico di cui abbiamo una rarissima foto:
Il nostro algoritmo che finora fa cose™ diventa quindi: come facciamo a trovare i K Pokémon più simili a Pepposaur?
È qui che entra in gioco l’algoritmo che abbiamo menzionato prima, e che sembra fatto apposta per rispondere a queste domande (che combinazione!): il KNN. KNN sta per K-Nearest Neighbors.
K-Nearest Neighbors
In Machine Learning KNN è un algoritmo di apprendimento supervisionato che viene utilizzato sia per le regressioni (cioè per la previsione di valori continui) che per le classificazioni (cioè per la previsione di classi o label di uscita). Si basa su un concetto molto semplice, eppure abbastanza efficace. Supponiamo di avere un elenco di persone, e supponiamo che per ciascuna persona conosciamo il peso e la circonferenza ai fianchi (valori numerici continui che chiameremo feature). Supponiamo che per ciascuna persona abbiamo un indicatore “sì/no” che ci dica se la persona è obesa o no. Supponiamo di mettere a grafico queste informazioni, per esempio mettendo sull’asse X la circonferenza ai fianchi, sull’asse Y il peso e colorando i pallini di colore diverso a seconda che la persona sia obesa (pallino rosso) oppure no (pallino celeste). Otterremmo un grafico di questo tipo:
Supponiamo inoltre di avere un’altra osservazione, di cui conosciamo le due feature (circonferenza e peso), e per la quale vogliamo prevedere il flag obeso/non obeso. Supponiamo che la nuova osservazione si collochi in questa maniera nel grafico (pallino verde):
L’algoritmo KNN prende una decisione sull’osservazione di turno semplicemente prendendo i K vicini più vicini e vedendo quale classe è la più rappresentata in questi K vicini. Nel nostro caso, se K = 5:
I 5 vicini più vicini sono a maggioranza celeste (non obeso). Quindi viene predetta per la nuova osservazione la classe “non obeso”. That’s it. Tutto qui. Semplice, no? In realtà KNN può usare metriche diverse per calcolare la distanza fra le osservazioni, chi vuole può approfondire qui, ma per quello ci serve la semplice distanza euclidea andrà più che bene.
Ora: vediamo di applicare al nostro caso d’uso lo stesso algoritmo. La chiave che ci consentirà di risolvere il nostro problema è la banale sostituzione di una parola: da “Pokémon più simili a Pepposaur” il nostro motore di ricerca dovrà cercare i “Pokémon più vicini a Pepposaur”.
Abbiamo da un lato le caratteristiche di Pepposaur, dall’altro il nostro dataset di Pokémon. Supponiamo, per semplicità, di considerare solo una caratteristica, gli HP, e diciamo che l’utente ha inserito il numero 67 come valore di HP di Pepposaur. Proviamo a costruire un grafico (monodimensionale, visto che stiamo considerando solo una grandezza) con gli HP di Pepposaur e quelli dei Pokémon del nostro dataset otterremmo qualcosa del genere:
Ad occhio nudo è evidente capire quali sono i K Pokémon più simili a Pepposaur. Ad esempio, se volessimo capire quali sono i 2 Pokémon più vicini a Pepposaur (cioè se K = 2), è evidente che questi sarebbero Ivysaur e Charmeleon. Se K = 3 invece dovremmo includere alla lista anche Charizard. Se K = 4 dovremmo includere anche Venusaur e così via. Ma formalmente come è possible arrivare a fornire questa soluzione? Una semplice formula che potremmo utilizzare potrebbe essere semplicemente la differenza in valore assoluto fra gli HP di Pepposaur e gli HP dei rispettivi Pokèmon:
Se calcoliamo questa differenza per tutti i Pokémon otterremo una tabella di questo tipo:
In grassetto i Pokémon con distanza minore, ovvero i Pokémon più vicini (e quindi più simili) a Pepposaur. Notiamo una cosa: dire che ci interessa il valore assoluto equivale a dire che facciamo la differenza fra le due osservazioni, la eleviamo al quadrato e ne calcoliamo la radice quadrata:
Ok, ora aggiungiamo un asse. Aggiungiamo cioè un altro punteggio, per esempio i punti attacco, e facciamo la stessa cosa di prima, cioè costruiamo un grafico. Diciamo che stavolta l’utente ha inserito come punteggi di Pepposaur i valori 54 e 55, rispettivamente per HP e punti attacco. Il grafico questa volta sarà bidimensionale proprio perchè consideriamo solo 2 feature, due assi:
Le distanze “ad occhio” ci dicono stavolta che i 3 Pokémon più vicini sono Bulbasaur, Ivysaur e Charmeleon, ma come formalizzare la cosa? Be’, siamo in un grafico bidimensionale, possiamo pensare al teorema di Pitagora e applicare la formula della distanza euclidea per calcolare la distanza fra 2 punti:
La formula da usare è la seguente:
Notiamo una cosa: rispetto alla precedente formula (in cui facevamo la radice quadrata del quadrato della differenza fra gli HP) abbiamo semplicemente aggiunto un termine: la differenza fra le coordinate y dei due punti fra cui vogliamo calcolare la distanza.
Anche in questo caso, quindi, abbiamo la possibilità di formalizzare il grado di “vicinanza” fra 2 punti su un grafico cartesiano e quindi di calcolare la distanza per ogni coppia Pepposaur/Pokemon del dataset:
Anche in questo caso in grassetto i 3 Pokémon più vicini a Pepposaur.
Rendiamo ancora più complessa (e completa) la cosa. Aggiungiamo un altro asse, contenente i punteggi dei punti di difesa. In questo caso andremmo a costruire un grafico tridimensionale (x: HP, y: Attacco, z: difesa), ma il succo non cambierebbe: la formula della distanza euclidea in un contesto tridimensionale sarebbe:
Potremmo quindi costruire la solita tabella con le distanze fra Pepposaur e i vari Pokémon.
Il bello della distanza euclidea è che funziona con un numero di assi che non è limitato al visibile. Se continuiamo ad aggiungere assi, anche se non potremo “visualizzare” i dati (perchè la nostra percezione è limitata alle sole 3 dimensioni) potremo comunque calcolare la distanza euclidea. La generalizzazione della distanza euclidea è:
in cui, semplicemente, per ogni dimensione (per ogni asse, o per ogni feature) differenza fra i rispettivi componenti delle 2 osservazioni fra le quali vogliamo calcolare la distanza, la eleviamo al quadrato, e la sommiamo agli altri componenti. Dopodichè mettiamo sotto radice il numero risultante, e -voilà- ecco la nostra distanza. Facciamo un esempio con 2 osservazioni:
# HP At Df SA SD Sppepposaur = [54, 55, 60, 42, 49, 25]bulbasaur = [45, 49, 49, 65, 65, 45]
La formula da applicare prevede:
ovvero:
Ed ecco la nostra distanza euclidea fra Pepposaur e Bulbasaur. Dobbiamo applicare questa formula agli 800 e passa Pokémon del dataset per calcolare la distanza euclidea fra il Pokémon inserito dall’utente e tutti i Pokemon del dataset.
Cosa vogliamo mostrare all’utente? Come facciamo ad ordinare per “somiglianza” i Pokémon?
Al momento, dunque, abbiamo i valori inseriti dall’utente per il Pokémon fittizio, e le distanze euclidee (cioè un numero) fra il Pokémon fittizio e tutti i Pokémon presenti nel dataset. È arrivato adesso il momento di far visualizzare i risultati del nostro motore di ricerca all’utente. Sappiamo benissimo che un motore di ricerca mostra i risultati in ordine di rilevanza. Prima i risultati più rilevanti, poi via via quelli meno rilevanti. Nel nostro caso cosa identifichiamo come “risultato”? E come facciamo ad ordinarli?
La risposta alla prima domanda è molto semplice. Basta una stringa con contenuti presi dal dataset come numero del pokedex nome, generazione, tipologia, punteggi. Ad esempio:
1 — Bulbasaur, type Grass, scores: …24 — Entei (legendary), type Fire, scores: …425 — Drifloon, type Ghost, Flying, scores: …
Ok, bene. Ma come li ordiniamo? Ricordiamo che abbiamo una struttura dati in cui per ogni Pokémon presente nel dataset abbiamo un’indicazione della distanza con il Pokémon fittizio dell’utente; con i calcoli fatti finora è come se avessimo aggiunto una colonna al nostro dataset, la colonna “Distanza da Pepposaur”; possiamo inoltre sfruttare la posizione nel dataset di ogni Pokémon (praticamente il numero di riga però iniziando a contare da 0), che è univoco per ogni Pokémon, e che quindi può essere utilizzato per distinguere i vari Pokémon gli uni dagli altri.
Possiamo allora memorizzare i nostri risultati in una struttura dati in cui per ogni Pokémon memorizziamo la posizione della riga nel dataset e la distanza con Pepposaur. Non abbiamo realmente bisogno di altro:
Per mostrare correttamente gli output del nostro motore di ricerca ci basterà ordinare questa struttura dati, basandosi sulla distanza presente in ogni elemento della nostra struttura dati. L’output di questo processo di ordinamento sarà:
E voilà! Ecco che abbiamo a questo punto la possibilità di accedere ai K (in questo caso K = 3) elementi più vicini a Pepposaur! In questo caso il motore di ricerca quindi restituirà 3 risultati (dato che K = 3) ordinati per vicinanza:
- al primo posto il Pokémon con indice 1, Ivysaur
- al secondo posto il Pokémon con indice 4, Charmender
- al terzo posto il Pokémon con indice 0, Bulbasaur
Quindi, ricapitolando, il nostro motore di ricerca funzionerà in questo modo:
- Il programma chiederà all’utente di inserire dei valori
- L’utente inserirà 6 valori, che saranno poi associati ad un Pokémon fittizio (che noi chiameremo Pepposaur)
- Il programma utilizzerà l’aloritmo KNN per cercare i K Pokémon più vicini a Pepposaur; in particolare:
userà la distanza euclidea per calcolare la distanza fra ogni Pokémon e Pepposaur
memorizzerà per ogni Pokémon in una lista a parte il numero di riga del Pokémon del quale ha appena calcolato la distanza da Pepposaur e la distanza stessa
ordinerà la lista appena creata per distanza - il programma mostrerà come output della ricerca i primi K risultati, che sono già ordinati per distanza
Ecco, ora che abbiamo capito come funzionerà il nostro programma, tempo di sporcarsi le mani e scrivere un po’di codice — ma nel prossimo articolo :).
