Catene di Markov e il compromesso tra esplorazione e sfruttamento in Python

Il concetto in parole semplici

L'IA deve spesso agire nell'incertezza. Una catena di Markov modella come un sistema passa da uno stato all'altro con probabilità fisse, e un multi-armed bandit mostra la scelta centrale dell'apprendimento per rinforzo: provare qualcosa di nuovo o usare ciò che finora ha funzionato meglio.

Prevedi gli stati futuri con una catena di Markov e bilancia esplorazione e sfruttamento con un bandit epsilon-greedy.

Idee chiave

In una catena di Markov lo stato successivo dipende solo dallo stato attuale.
Le probabilità di transizione che escono da uno stato sommano sempre a 1.
Esplorare trova opzioni migliori; sfruttare ottiene ricompense dall'opzione migliore conosciuta.
Epsilon regola l'equilibrio: un epsilon più grande esplora di più.

Quando si usa?

Capire cosa succede dentro le reti neurali e le librerie di IA.
Imparare l'idea prima di implementarla nelle sfide corrispondenti.
Prepararti a corsi di machine learning, colloqui e progetti.

Guardalo in azione

Cambia le probabilità di transizione del meteo per vedere dove si stabilizza la catena. Premi Avvia per far imparare al bandit quale macchina paga di più.

Codice di esempio

Esegui codice →

main.py

import random

# Markov chain: tomorrow's weather depends only on today's.
transitions = {"sunny": {"sunny": 0.8, "rainy": 0.2}, "rainy": {"sunny": 0.4, "rainy": 0.6}}
dist = {"sunny": 1.0, "rainy": 0.0}
for day in range(1, 4):
    dist = {s: sum(dist[p] * transitions[p][s] for p in dist) for s in dist}
    print(f"day {day}:", {s: round(v, 3) for s, v in dist.items()})

# Epsilon-greedy bandit: usually pick the best arm so far, sometimes explore.
random.seed(1)
true_payouts = [0.3, 0.7]
counts, totals = [0, 0], [0.0, 0.0]
epsilon = 0.1
for _ in range(500):
    if random.random() < epsilon or 0 in counts:
        arm = random.randrange(2)                                  # explore
    else:
        arm = max(range(2), key=lambda a: totals[a] / counts[a])  # exploit
    reward = 1 if random.random() < true_payouts[arm] else 0
    counts[arm] += 1
    totals[arm] += reward
print("pulls per arm:", counts)
print("estimated payouts:", [round(t / c, 2) for t, c in zip(totals, counts)])

Output previsto

day 1: {'sunny': 0.8, 'rainy': 0.2}
day 2: {'sunny': 0.72, 'rainy': 0.28}
day 3: {'sunny': 0.688, 'rainy': 0.312}
pulls per arm: [25, 475]
estimated payouts: [0.16, 0.7]

Come funziona

Ogni giorno le nuove probabilità sono quelle vecchie moltiplicate per le probabilità di transizione, quindi «sereno» scende da 1.0 a 0.688 in tre giorni. Il bandit sceglie un braccio a caso il 10% delle volte e altrimenti tira il braccio con la media migliore finora; presto dedica quasi tutti i tentativi al braccio migliore e ne stima la vincita intorno a 0.7.

Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.

Esercizi pratici

Modifica gli input e verifica i casi limite prima di usare dataset più grandi.

Cambia gli input o i pesi e prevedi l'output prima di eseguire.
Stampa i valori intermedi per seguire ogni passo del calcolo.
Risolvi le sfide collegate qui sotto per implementare l'idea da solo.

Esegui nell’IDE Python →

Esercitati con una sfida

Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.

Tutte le sfide