over het kleine wereldexperiment, uitgevoerd door Stanley Milgram in de jaren zestig. Hij ontwierp een experiment waarbij een brief werd afgeleverd bij een vrijwilliger in de Verenigde Staten, met instructies om de brief door te sturen naar zijn persoonlijke contactpersoon die hoogstwaarschijnlijk een andere persoon – het doelwit – in hetzelfde land kende. Op zijn beurt wordt de persoon die de brief ontvangt, gevraagd de brief opnieuw door te sturen totdat de beoogde persoon is bereikt. Hoewel het merendeel van de brieven de beoogde persoon nooit bereikte, lag het gemiddelde aantal hops onder de brieven die dat wel deden (hier is sprake van overlevingsvooroordelen!) rond de zes. De ‘zes graden van scheiding’ zijn een culturele verwijzing geworden naar de nauwe onderlinge verbondenheid van de samenleving.
Ik ben nog steeds verbaasd over de gedachte dat mensen met ~102 contacten kunnen verbinding maken met een willekeurig persoon in een netwerk van ~108 mensen, door een paar sprongen.
Hoe is dit mogelijk? Heuristiek.
Stel dat mij wordt gevraagd een brief te sturen naar een doelpersoon in Finland1.
Helaas heb ik geen contacten in Finland. Aan de andere kant ken ik iemand die al jaren in Zweden woont. Misschien kent hij mensen in Finland. Zo niet, dan heeft hij waarschijnlijk nog contacten in Zweden, een buurland. Zij is de beste oplossing om mij dichter bij de doelgroep te brengen. Het punt is dat zelfs als ik de topologie van het sociale netwerk buiten mijn persoonlijke contacten niet ken, ik enkele vuistregels kan gebruiken om de brief in de goede richting door te sturen.
Als we het standpunt van de knooppunten van het netwerk innemen (de mensen die bij het experiment betrokken zijn), zijn hun beschikbare acties het doorsturen van het bericht (de brief) naar een van hun achterranden (persoonlijke contacten). Dit probleem om de boodschap in de goede richting te krijgen, biedt de mogelijkheid om plezier te hebben met machine learning!
Knooppunten nemen niet de gehele topologie van het netwerk waar. We kunnen een omgeving creëren die hen beloont voor het doorgeven van de boodschap langs het kortst bekende pad, terwijl we hen aanmoedigen om suboptimale kandidaatpaden te verkennen. Klinkt als een geweldige use case voor versterkend leren, vind je niet?
Voor degenen die geïnteresseerd zijn in het uitvoeren van de code, kunt u de repository hier bereiken.
Het probleem
We krijgen een gerichte grafiek waarin de randen tussen knooppunten schaars zijn, wat betekent dat het gemiddelde aantal randen dat een knooppunt verlaat aanzienlijk minder is dan het aantal knooppunten. Bovendien brengen de grenzen kosten met zich mee. Deze extra functie generaliseert het geval van het Small World Experiment, waarbij elke lettersprong 1 kostte.
Het probleem dat we zullen overwegen is het ontwerpen van een versterkend leeralgoritme dat een pad vindt van een willekeurig startknooppunt naar een willekeurig doelknooppunt in een dun gerichte graaf, tegen zo laag mogelijke kosten, als zo’n pad bestaat. Er zijn deterministische oplossingen voor dit probleem. Het algoritme van Dijkstra vindt bijvoorbeeld het kortste pad van een aanvankelijk knooppunt naar alle andere knooppunten in een gerichte graaf. Dit zal nuttig zijn om de resultaten van ons versterkingsleeralgoritme te evalueren, dat niet garandeert dat de optimale oplossing wordt gevonden.
Q-Leren
Q-Learning is een versterkende leertechniek waarbij een agent een tabel met status-actieparen bijhoudt, gekoppeld aan de verwachte cumulatieve kortingsbeloning: de kwaliteitdaarom de Q-Leren. Door middel van iteratieve experimenten wordt de tabel bijgewerkt totdat aan een stopcriterium wordt voldaan. Na de training kan de agent de actie kiezen (de kolom van de Q-matrix) die overeenkomt met de maximale kwaliteit, voor een bepaalde toestand (de rij van de Q-matrix).
De updateregel, gegeven een testactie aJresulterend in een overgang van de staat sI verklaren skeen beloning ren een betere inschatting van de kwaliteit van de volgende staat skEN:
( Q(i, j) linkerpijl (1 – alpha) Q(i, j) + alpha left( r + gamma max_{l} Q(k, l) right) )
Vergelijking 1: De updateregel voor Q-Learning.
In vergelijking 1:
αis de leersnelheid, die bepaalt hoe snel nieuwe resultaten oude kwaliteitsschattingen zullen uitwissen.- γ is de kortingsfactor, die bepaalt hoe toekomstige premies zich verhouden tot directe premies.
Qhet is de matrix van kwaliteit. De rij-indexiis de bronstatusindex en de kolomindexjis de index van de geselecteerde actie.
Kortom, vergelijking 1 stelt dat de kwaliteit van (toestand, actie) gedeeltelijk moet worden bijgewerkt met een nieuwe kwaliteitswaarde, bestaande uit de som van de onmiddellijke beloning en de verdisconteerde schatting van de maximale kwaliteit van de daaropvolgende toestand over de mogelijke acties.
Voor onze probleemformulering zou een mogelijke formulering voor de toestand het paar zijn (huidig knooppunt, bestemmingsknooppunt) en de reeks acties zou de reeks knooppunten zijn. De statusset zou dan bevatten N2 waarden en de reeks acties zouden bevatten N waarden, waar N is het aantal knooppunten. Omdat de grafiek echter schaars is, heeft een bepaald bronknooppunt slechts een kleine subset van knooppunten als uitvoerranden. Deze formulering zou resulteren in een Q-matrix waar de grote meerderheid van N3 vermeldingen worden nooit bezocht, waardoor onnodig geheugen wordt verbruikt.
Gedistribueerde agenten
Een beter gebruik van hulpbronnen is het distribueren van agenten. Elk knooppunt kan worden gezien als een agent. De status van de agent is het bestemmingsknooppunt en dus zijn Q-de matrix heeft N lijnen en Nuit kolommen (het aantal uitgaande randen voor dit specifieke knooppunt). Met N agenten, het totale aantal vermeldingen in de matrix is N2Nuitwat minder is dan N3.
Samenvattend:
- Wij zullen trainen
Nagenten, één voor elk knooppunt van de grafiek. - Elke agent zal het leren
Q-groottematrix(N x Nuit). Het aantal uitgaande bogen (Nuit) kan variëren van knooppunt tot knooppunt. Voor een schaars verbonden grafiek,Nuit. - De rij-indexen van de
Q-matrix komt overeen met de status van de agent, d.w.z. het bestemmingsknooppunt. - De kolomindexen van
Q-array komt overeen met de uitgaande rand die door een agent is geselecteerd om een bericht naar het bestemmingsknooppunt te routeren. Q(i, j)vertegenwoordigt de schatting van een knooppunt van de kwaliteit van het doorsturen van berichten naar zijn knooppuntje uitgaande rand, gegeven dat het bestemmingsknooppunt dat isi.- Wanneer een knooppunt een bericht ontvangt, wordt het bestemmingsknooppunt daarin opgenomen. Omdat de afzender van het vorige bericht niet nodig is om de route van het volgende bericht te bepalen, wordt dit niet in het volgende bericht opgenomen.
Code
De hoofdklasse, het knooppunt, krijgt een naam QNode.
class QNode:
def __init__(self, number_of_nodes=0, connectivity_average=0, connectivity_std_dev=0, Q_arr=None, neighbor_nodes=None,
state_dict=None):
if state_dict is not None:
self.Q = state_dict('Q')
self.number_of_nodes = state_dict('number_of_nodes')
self.neighbor_nodes = state_dict('neighbor_nodes')
else: # state_dict is None
if Q_arr is None:
self.number_of_nodes = number_of_nodes
number_of_neighbors = connectivity_average + connectivity_std_dev * np.random.randn()
number_of_neighbors = round(number_of_neighbors)
number_of_neighbors = max(number_of_neighbors, 2) # At least two out-connections
number_of_neighbors = min(number_of_neighbors, self.number_of_nodes) # Not more than N connections
self.neighbor_nodes = random.sample(range(self.number_of_nodes), number_of_neighbors) # (1, 4, 5, ...)
self.Q = np.zeros((self.number_of_nodes, number_of_neighbors)) # Optimistic initialization: all rewards will be negative
# q = self.Q(state, action): state = target node; action = chosen neighbor node (converted to column index) to route the message to
else: # state_dict is None and Q_arr is not None
self.Q = Q_arr
self.number_of_nodes = self.Q.shape(0)
self.neighbor_nodes = neighbor_nodesDe klas QNode heeft drie velden: het aantal knooppunten in de grafiek, de lijst met uitgaande randen en de Q-matrix. DE Q-matrix wordt geïnitialiseerd met nullen. De voordelen uit het milieu zullen het negatieve zijn van de marginale kosten. De kwaliteitswaarden zullen dus allemaal negatief zijn. Om deze reden is initialisatie met nullen een optimistische initialisatie.
Wanneer een bericht een QNode object, selecteer een van de randen die door het object naar buiten komt epsilon-hebzuchtig algoritme. Als ε klein is, selecteert het epsilon-greedy-algoritme meestal de voorrand met de grootste waarde Q-waarde. Af en toe selecteert het willekeurig een uitgaande rand:
def epsilon_greedy(self, target_node, epsilon):
rdm_nbr = random.random()
if rdm_nbr De andere klasse is de grafiek, genaamd QGraph.
class QGraph:
def __init__(self, number_of_nodes=10, connectivity_average=3, connectivity_std_dev=0, cost_range=(0.0, 1.0),
maximum_hops=100, maximum_hops_penalty=1.0):
self.number_of_nodes = number_of_nodes
self.connectivity_average = connectivity_average
self.connectivity_std_dev = connectivity_std_dev
self.cost_range = cost_range
self.maximum_hops = maximum_hops
self.maximum_hops_penalty = maximum_hops_penalty
self.QNodes = ()
for node in range(self.number_of_nodes):
self.QNodes.append(QNode(self.number_of_nodes, self.connectivity_average, self.connectivity_std_dev))
self.cost_arr = cost_range(0) + (cost_range(1) - cost_range(0)) * np.random.random((self.number_of_nodes, self.number_of_nodes))
De belangrijkste velden zijn de knooppuntenlijst en de randkostenarray. Merk op dat de werkelijke randen deel uitmaken van de QNode klasse, zoals een lijst met uitgaande knooppunten.
Wanneer we een route willen genereren van een startknooppunt naar een bestemmingsknooppunt, noemen we de QGraph.trajectory() methode, die de methode aanroept QNode.epsilon_greedy() methode:
def trajectory(self, start_node, target_node, epsilon):
visited_nodes = (start_node)
costs = ()
if start_node == target_node:
return visited_nodes, costs
current_node = start_node
while len(visited_nodes) DE trajectory() retourneert de lijst met bezochte knooppunten langs het pad en de lijst met kosten die verband houden met de gebruikte randen.
Het laatste ontbrekende stukje is de updateregel van vergelijking 1, geïmplementeerd door QGraph.update_Q() methode:
def update_Q(self, start_node, neighbor_node, alpha, gamma, target_node):
cost = self.cost_arr(start_node, neighbor_node)
reward = -cost
# Q_orig(target, dest) Om onze agenten te trainen, voeren we iteratief paren uit (start_node, target_node) met een binnenlus op de aangrenzende knooppunten van start_nodeen wij bellen update_Q().
Experimenten en resultaten
Laten we beginnen met een eenvoudige grafiek met twaalf knooppunten, met gerichte gewogen randen.
We kunnen uit Figuur 1 zien dat het enige binnenkomende knooppunt naar Knooppunt-1 Knooppunt-7 is, en het enige binnenkomende knooppunt naar Knooppunt-7 Knooppunt-1 is. Daarom kan geen enkel ander knooppunt dan deze twee knooppunt 1 en knooppunt 7 bereiken. Wanneer een ander knooppunt de taak heeft een bericht naar knooppunt 1 of knooppunt 7 te sturen, stuitert het bericht op de grafiek totdat het maximale aantal hops is bereikt. We verwachten een groot negatief punt te zien Q-waarden in deze gevallen.
Wanneer we onze grafiek trainen, krijgen we statistieken over de kosten en het aantal hops als functie van het tijdperk, zoals in figuur 2:
Na de training is dit de Q-matrix voor Knooppunt-4:
Het traject van bijvoorbeeld knooppunt 4 naar knooppunt 11 kan worden verkregen door het bestand op te roepen trajectory() methode, instelling epsilon=0 voor de hebzuchtige deterministische oplossing: (4, 3, 5, 11) voor een totale niet-verdisconteerde prijs van 0,9 + 0,9 + 0,3 = 2,1. Het Dijkstra-algoritme retourneert hetzelfde pad.
In enkele zeldzame gevallen werd de optimale route niet gevonden. Om bijvoorbeeld van Knooppunt 6 naar Knooppunt 9 te gaan, retourneerde een specifiek exemplaar van de getrainde Q-graph (6, 11, 0, 4, 10, 2, 9) voor een totale niet-gedisconteerde prijs van 3,5, terwijl het Dijkstra-algoritme retourneerde (6, 0, 4, 10, 2, 9) voor een totale niet-gedisconteerde prijs van 3,4. Zoals we eerder hebben aangegeven, wordt dit voorspeld door een iteratief algoritme
Conclusie
We formuleerden het kleine-wereldexperiment als het probleem van het vinden van het pad met minimale kosten tussen elk paar knooppunten in een gerichte dunne graaf met gewogen randen. We hebben de knooppunten geïmplementeerd als Q-Learning-agents, die via de updateregel leren om de minst kostbare actie te ondernemen, gegeven een doelknooppunt.
Met een eenvoudige grafiek hebben we aangetoond dat de training resulteerde in een oplossing die dicht bij de optimale oplossing lag.
Bedankt voor je tijd en experimenteer gerust met de code. Heb jij ideeën voor leuke Q-Learning apps, laat het ons weten!
1 Oké, ik ga verder dan het oorspronkelijke Small World Experiment, dat het Small Country Experiment zou moeten heten.
Referenties
Versterkingsleren, Richard S. Sutton, Andrew G. Barto, MIT Press, 1998
