Utilizzo di algoritmi evolutivi per la selezione rapida delle funzionalità con set di dati di grandi dimensioni
Questa è la parte finale di una serie in due parti sulla selezione delle funzionalità. Leggere parte 1 qui.
Breve riepilogo: quando si adatta un modello a un set di dati, è possibile che si desideri selezionare un sottoinsieme di funzionalità (invece di utilizzare tutte le funzionalità), per vari motivi. Ma anche se si ha una funzione obiettivo chiara per cercare la migliore combinazione di caratteristiche, la ricerca potrebbe richiedere molto tempo se il numero di caratteristiche N è molto grande. Trovare la combinazione migliore non è sempre facile. La ricerca a forza bruta generalmente non funziona oltre diverse dozzine di funzionalità. Gli algoritmi euristici sono necessari per eseguire una ricerca più efficiente.
Se hai N caratteristiche, quello che stai cercando è un vettore di N lunghezza (1, 1, 0, 0, 0, 1, ...) con valori da {0, 1} . Ogni componente del vettore corrisponde a una caratteristica. 0 significa che la funzionalità è rifiutata, 1 significa che la funzionalità è selezionata. Devi trovare il vettore che minimizzi la funzione costo/obiettivo che stai utilizzando.
Nell’articolo precedente, abbiamo esaminato un algoritmo classico, SFS (sequential feature search), e lo abbiamo confrontato con un efficiente algoritmo evolutivo chiamato CMA-ES. Abbiamo iniziato con il set di dati sui prezzi delle case su Kaggle che, dopo alcune elaborazioni, ha prodotto 213 caratteristiche con 1453 osservazioni ciascuna. Il modello che abbiamo cercato di adattare era statsmodels.api.OLS() e la funzione obiettivo era il BIC (Bayesian Information Criterion) del modello, una misura della perdita di informazioni. Un BIC inferiore significa un adattamento migliore, quindi stiamo cercando di ridurre al minimo l’obiettivo.
In questo articolo esamineremo un’altra tecnica evolutiva: gli algoritmi genetici. Il contesto (set di dati, modello, obiettivo) rimane lo stesso.
Gli algoritmi genetici si ispirano all’evoluzione biologica e alla selezione naturale. In natura, gli esseri viventi sono (in parole povere) selezionati per i geni (caratteri) che facilitano la sopravvivenza e il successo riproduttivo, nel contesto dell’ambiente in cui vivono.
Ora pensa alla selezione delle funzionalità. Hai N caratteristiche. Stai cercando di trovare vettori binari di lunghezza N (1, 0, 0, 1, 1, 1, ...) che selezionano le funzionalità (1 = funzionalità selezionata, 0 = funzionalità rifiutata) in modo da minimizzare una funzione costo/obiettivo.
Ciascuno di questi vettori può essere pensato come un “individuo”. Ogni componente del vettore (valore 0 o valore 1) diventa un “gene”. Applicando l’evoluzione e la selezione, potrebbe essere possibile far evolvere una popolazione di individui in modo tale da avvicinarsi al miglior valore per la funzione obiettivo a cui siamo interessati.
Ecco GA in poche parole. Inizia generando una popolazione di individui (vettori), ciascun vettore di lunghezza N. I valori dei componenti del vettore (geni) sono scelti casualmente da {0, 1}. Nel diagramma seguente, N=12 e la dimensione della popolazione è 8.
Dopo aver creato la popolazione, valutare ciascun individuo tramite la funzione obiettivo.
Ora esegui la selezione: mantieni gli individui con i migliori valori oggettivi e scarta quelli con i valori peggiori. Ci sono molte strategie possibili qui, dal ranking ingenuo (che, controintuitivamente, non funziona molto bene), alla selezione stocastica dei tornei, che è molto efficiente a lungo termine. Ricorda il dilemma esplora-sfrutta. Con GA è molto facile cadere in ingenue trappole di exploit che chiudono la porta a un’esplorazione potente. GA è incentrato sull’esplorazione. Ecco un breve elenco di tecniche di selezionee controlla i link alla fine per maggiori informazioni.
Una volta selezionati gli individui migliori e scartati quelli meno adatti, è il momento di introdurre la variazione nel pool genetico attraverso due tecniche: crossover e mutazione.
Il crossover funziona esattamente come in natura, quando due esseri viventi si accoppiano e producono prole: il materiale genetico di entrambi i genitori viene “mescolato” nei discendenti, con un certo grado di casualità.
La mutazione, ancora una volta, è più o meno ciò che accade in natura quando si verificano mutazioni casuali nel materiale genetico e nuovi valori vengono introdotti nel pool genetico, aumentandone la diversità.
Dopodiché l’algoritmo torna indietro: gli individui vengono nuovamente valutati tramite la funzione obiettivo, avviene la selezione, quindi l’incrocio, la mutazione, ecc.
Possono essere utilizzati vari criteri di arresto: il ciclo può interrompersi se la funzione obiettivo smette di migliorare per un certo numero di generazioni. Oppure potresti fissare un limite definitivo al numero totale di generazioni valutate. Oppure fai qualcosa basato sul tempo, o osserva un segnale esterno, ecc. Indipendentemente da ciò, gli individui con i migliori valori oggettivi dovrebbero essere considerati le “soluzioni” al problema.
Qualche parola sull’elitarismo: con le tecniche di selezione stocastica come i tornei, i migliori individui in assoluto di una generazione potrebbero effettivamente non essere selezionati, per puro caso: è improbabile, ma succede. L’elitarismo aggira questo ostacolo e decreta semplicemente che i migliori devono sopravvivere, qualunque cosa accada. L’elitarismo è una tecnica di exploit. Potrebbe far sì che l’algoritmo cada negli estremi locali, perdendo la soluzione globale. Ancora una volta, GA è incentrato sull’esplorazione. La mia esperienza piuttosto limitata con GA sembra confermare l’idea che un exploit bias non sia vantaggioso per GA. Ma il tuo chilometraggio può variare; se ti piace sperimentare varianti di algoritmi, GA ti offre molte opportunità per farlo.
GA ha diversi iperparametri che puoi ottimizzare:
- dimensione della popolazione (numero di individui)
- probabilità di mutazione (per individuo, per gene)
- probabilità di incrocio
- strategie di selezione, ecc.
L’esecuzione di prove manuali con vari valori di iperparametri è un modo per individuare il codice migliore. Oppure potresti incapsulare GA in Optuna e lasciare che Optuna lavori per trovare i migliori iperparametri, ma questo è computazionalmente costoso.
Ecco un semplice codice GA che può essere utilizzato per la selezione delle funzionalità. Utilizza la biblioteca mortache è molto potente, ma la curva di apprendimento potrebbe essere ripida. Questa versione semplice, tuttavia, dovrebbe essere abbastanza chiara.
# to maximize the objective
# fitness_weights = 1.0
# to minimize the objective
fitness_weights = -1.0# copy the original dataframes into local copies, once
X_ga = X.copy()
y_ga = y.copy()
# 'const' (the first column) is not an actual feature, do not include it
X_features = X_ga.columns.to_list()(1:)
try:
del creator.FitnessMax
del creator.Individual
except Exception as e:
pass
creator.create("FitnessMax", base.Fitness, weights=(fitness_weights,))
creator.create(
"Individual", array.array, typecode='b', fitness=creator.FitnessMax
)
try:
del toolbox
except Exception as e:
pass
toolbox = base.Toolbox()
# Attribute generator
toolbox.register("attr_bool", random.randint, 0, 1)
# Structure initializers
toolbox.register(
"individual",
tools.initRepeat,
creator.Individual,
toolbox.attr_bool,
len(X_features),
)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
def evalOneMax(individual):
# objective function
# create True/False selector list for features
# and add True at the start for 'const'
cols_select = (True) + (i == 1 for i in list(individual))
# fit model using the features selected from the individual
lin_mod = sm.OLS(y_ga, X_ga.loc(:, cols_select), hasconst=True).fit()
return (lin_mod.bic,)
toolbox.register("evaluate", evalOneMax)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutFlipBit, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)
random.seed(0)
pop = toolbox.population(n=300)
hof = tools.HallOfFame(1)
pop, log = algorithms.eaSimple(
pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=10, halloffame=hof, verbose=True
)
best_individual_ga_small = list(hof(0))
best_features_ga_small = (
X_features(i) for i, val in enumerate(best_individual_ga_small) if val == 1
)
best_objective_ga_small = (
sm.OLS(y_ga, X_ga(('const') + best_features_ga_small), hasconst=True)
.fit()
.bic
)
print(f'best objective: {best_objective_ga_small}')
print(f'best features: {best_features_ga_small}')
Il codice crea gli oggetti che definiscono un individuo e l’intera popolazione, insieme alle strategie utilizzate per la valutazione (funzione obiettivo), crossover/accoppiamento, mutazione e selezione. Si inizia con una popolazione di 300 individui, e poi si chiamano eaSimple() (una sequenza fissa di crossover, mutazione, selezione) che dura solo 10 generazioni, per semplicità. Viene definita la Hall of fame con una dimensione pari a 1, dove l’individuo migliore in assoluto viene preservato dall’essere mutato/saltato accidentalmente durante la selezione, ecc.
La Hall of Fame non è elitarismo. La Hall of Fame copia l’individuo migliore della popolazione e conserva solo la copia in un barattolo di latta. L’elitarismo preserva l’individuo migliore della popolazione da una generazione a quella successiva.
Questo semplice codice è facile da capire, ma inefficiente. Controlla il taccuino il deposito per una versione più complessa del codice GA, che non citerò qui. Tuttavia, l’esecuzione del codice più complesso e ottimizzato dal notebook per 1000 generazioni produce questi risultati:
best objective: 33705.569572544795
best generation: 787
objective runs: 600525
time to best: 157.604 sec
Ed ecco l’intera cronologia del codice GA completo e ottimizzato del notebook, in esecuzione per 1000 generazioni, cercando di trovare le migliori funzionalità. Da sinistra a destra, la mappa termica indica la popolarità di ciascuna caratteristica all’interno della popolazione attraverso le generazioni (tonalità più chiara = più popolare). Puoi vedere come alcune funzionalità sono sempre popolari, altre vengono rifiutate rapidamente, mentre altre ancora potrebbero diventare più popolari o meno popolari col passare del tempo.
Fonte: towardsdatascience.com
