Apprendimento per rinforzo: il problema decisionale di Markov per la selezione delle caratteristiche
È stato dimostrato che le tecniche di apprendimento per rinforzo (RL) possono essere molto efficienti per problemi come la risoluzione di giochi. Il concetto di RL si basa sul processo decisionale markoviano (MDP). Il punto qui non è definire profondamente l’MDP ma avere un’idea generale di come funziona e di come può essere utile al nostro problema.
L'idea ingenua alla base di RL è che un agente inizia in un ambiente sconosciuto. Questo agente deve intraprendere azioni per completare un'attività. In funzione dello stato attuale dell'agente e dell'azione che ha selezionato in precedenza, l'agente sarà più propenso a scegliere alcune azioni. Ad ogni nuovo stato raggiunto e azione intrapresa, l'agente riceve una ricompensa. Ecco quindi i parametri principali che dobbiamo definire ai fini della selezione delle funzionalità:
- Cos'è uno stato?
- Cos'è un'azione?
- Quali sono le ricompense?
- Come scegliamo un'azione?
In primo luogo, lo stato è semplicemente un sottoinsieme di caratteristiche esistenti nel set di dati. Ad esempio, se il set di dati ha tre caratteristiche (Età, Sesso, Altezza) più un'etichetta, ecco i possibili stati:
() --> Empty set
(Age), (Gender), (Height) --> 1-feature set
(Age, Gender), (Gender, Height), (Age, Height) --> 2-feature set
(Age, Gender, Height) --> All-feature set
In uno stato l'ordine delle caratteristiche non ha importanza e il motivo verrà spiegato più avanti nell'articolo. Dobbiamo considerarlo come un insieme e non un elenco di funzionalità.
Per quanto riguarda le azioni, da un sottoinsieme si può passare a qualsiasi altro sottoinsieme con una caratteristica non ancora esplorata in più rispetto allo stato corrente. Nel problema di selezione delle funzionalità, un'azione consiste quindi nel selezionare una funzionalità non ancora esplorata nello stato corrente e aggiungerla allo stato successivo. Ecco un esempio di azioni possibili:
(Age) -> (Age, Gender)
(Gender, Height) -> (Age, Gender, Height)
Ecco un esempio di azioni impossibili:
(Age) -> (Age, Gender, Height)
(Age, Gender) -> (Age)
(Gender) -> (Gender, Gender)
Abbiamo definito gli stati e le azioni ma non la ricompensa. La ricompensa è un numero reale che viene utilizzato per valutare la qualità di uno stato. Ad esempio, se un robot sta cercando di raggiungere l'uscita di un labirinto e decide di dirigersi verso l'uscita come azione successiva, la ricompensa associata a questa azione sarà “buona”. Se sceglie come azione successiva di cadere in una trappola, la ricompensa sarà “non buona”. La ricompensa è un valore che ha portato informazioni sull'azione precedente intrapresa.
Nel problema della selezione delle caratteristiche una ricompensa interessante potrebbe essere un valore di accuratezza che viene aggiunto al modello aggiungendo una nuova caratteristica. Ecco un esempio di come viene calcolata la ricompensa:
(Age) --> Accuracy = 0.65
(Age, Gender) --> Accuracy = 0.76
Reward(Gender) = 0.76 - 0.65 = 0.11
Per ogni stato che visitiamo per la prima volta verrà addestrato un classificatore con l'insieme di funzionalità. Questo valore viene memorizzato nello stato e l'addestramento del classificatore, che è molto costoso, avverrà una sola volta anche se lo stato verrà raggiunto nuovamente in seguito. Il classificatore non considera l'ordine della caratteristica. Questo è il motivo per cui possiamo vedere questo problema come un grafico e non come un albero. In questo esempio, il risultato dell'azione di selezionare Sesso come nuova funzionalità per il modello è la differenza tra l'accuratezza dello stato corrente e dello stato successivo.
Nel grafico sopra, ciascuna caratteristica è stata mappata su un numero (ad esempio, “Età” è 1, “Sesso” è 2 e “Altezza” è 3). È assolutamente possibile prendere altri parametri per massimizzare per trovare il set ottimale. In molte applicazioni aziendali il richiamo è più considerato della precisione.
La prossima domanda importante è come selezioniamo lo stato successivo dallo stato attuale o come esploriamo il nostro ambiente. Dobbiamo trovare il modo più ottimale per farlo poiché può rapidamente diventare un problema molto complesso. Infatti, se esplorassimo ingenuamente tutto il possibile insieme di caratteristiche in un problema con 10 caratteristiche, il numero di stati sarebbe
10! + 2 = 3 628 802 possible states
Il +2 è perché consideriamo uno stato vuoto e uno stato che contiene tutte le possibili funzionalità. In questo problema dovremmo addestrare lo stesso modello su tutti gli stati per ottenere l'insieme di funzionalità che massimizzano la precisione. Nell'approccio RL non dovremo andare in tutti gli stati e addestrare un modello ogni volta che andremo in uno stato già visitato.
Abbiamo dovuto determinare alcune condizioni di arresto per questo problema e verranno dettagliate in seguito. Per ora è stata scelta la scelta dello stato epsilon-avido. L'idea è che da uno stato attuale selezioniamo l'azione successiva in modo casuale con una probabilità di epsilon (tra 0 e 1 e spesso intorno a 0,2) e altrimenti selezioniamo l'azione che massimizza una funzione. Per la selezione delle caratteristiche, la funzione è la media della ricompensa che ciascuna caratteristica ha apportato all'accuratezza del modello.
L'algoritmo epsilon-greedy implica due passaggi:
- Una fase casuale: con probabilità epsilon, selezioniamo casualmente lo stato successivo tra i possibili vicini dello stato corrente (possiamo immaginare una selezione uniforme o softmax)
- Una fase avida: selezioniamo lo stato successivo in modo tale che la caratteristica aggiunta allo stato corrente abbia il massimo contributo di accuratezza al modello. Per ridurre la complessità temporale, abbiamo inizializzato un elenco contenente questi valori per ciascuna funzionalità. Questo elenco viene aggiornato ogni volta che viene scelta una funzionalità. L'aggiornamento è molto ottimale grazie alla seguente formula:
- AORf : Media della ricompensa apportata dalla funzione “f”
- K : numero di volte in cui è stata selezionata la lettera “f”.
- V(F) : valore dello stato dell'insieme di caratteristiche F (non dettagliato in questo articolo per ragioni di chiarezza)
L'idea globale è trovare quale caratteristica ha apportato la maggiore precisione al modello. Ecco perché dobbiamo esplorare diversi stati per valutare in molti ambienti diversi il valore più accurato e globale di una caratteristica per il modello.
Infine descriverò in dettaglio le due condizioni di stop. Poiché l’obiettivo è ridurre al minimo il numero di stati visitati dall’algoritmo, dobbiamo fare attenzione a loro. Meno stati mai visitati visiteremo, minore sarà il numero di modelli che dovremo addestrare con diversi set di funzionalità. Addestrare il modello per ottenere la precisione è la fase più costosa in termini di tempo e potenza di calcolo.
- L'algoritmo si ferma comunque allo stato finale che è l'insieme contenente tutte le caratteristiche. Vogliamo evitare di raggiungere questo stato poiché è il più costoso con cui addestrare un modello.
- Inoltre, interrompe la navigazione nel grafico se una sequenza di stati visitati vede i propri valori degradare successivamente. È stata impostata una soglia tale che, dopo la radice quadrata del numero di funzionalità totali nel set di dati, l'esplorazione viene interrotta.
Ora che è stata spiegata la modellazione del problema, descriveremo in dettaglio l'implementazione in Python.
Fonte: towardsdatascience.com
