Routing in een schaarse grafiek: een gedistribueerde Q-Learning-aanpak

over het Small-World Experiment, uitgevoerd door Stanley Milgram in de jaren zestig. Hij bedacht een experiment waarbij een brief werd gegeven aan een vrijwilliger in de Verenigde Staten, met de instructie om de brief door te sturen naar hun persoonlijke contactpersoon die hoogstwaarschijnlijk een andere persoon – het doelwit – in hetzelfde land kende. Op zijn beurt werd de persoon die de brief ontving, gevraagd de brief opnieuw door te sturen totdat de beoogde persoon was bereikt. Hoewel de meeste brieven nooit de beoogde persoon bereikten, lag het gemiddelde aantal hops onder degenen die dat wel deden (hier speelt overlevingsvooroordeel!) 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 ~10² contacten slagen erin verbinding te maken met een willekeurig persoon in een netwerk van ~10⁸ mensen, via een paar sprongen.

Hoe is dat mogelijk? Heuristiek.

Laten we aannemen dat mij wordt gevraagd een brief te sturen naar een doelpersoon in Finland¹.

Helaas heb ik geen contacten in Finland. Aan de andere kant ken ik iemand die jarenlang in Zweden heeft gewoond. Misschien kent ze mensen in Finland. Zo niet, dan heeft ze waarschijnlijk nog contacten in Zweden, een buurland. Zij is mijn beste keuze om dichter bij de doelgroep te komen. Het punt is dat ik, hoewel ik de topologie van het sociale netwerk buiten mijn eigen persoonlijke contacten niet ken, 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 uitgaande randen (persoonlijke contacten). Dit probleem van het in de goede richting overbrengen van de boodschap biedt de mogelijkheid om plezier te hebben met machinaal leren!

Knooppunten nemen niet de hele netwerktopologie waar. We kunnen een omgeving opzetten die hen beloont voor het routeren van de boodschap langs het kortst bekende pad, terwijl ze worden aangemoedigd om suboptimale kandidaatpaden te verkennen. Dat 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 uitgaande randen van een knooppunt aanzienlijk kleiner is dan het aantal knooppunten. Bovendien zullen de randen bijbehorende kosten met zich meebrengen. Deze extra functie generaliseert het geval van het Small-World Experiment, waarbij elke sprong van de letter telde voor een prijs van 1.

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. Voor dit probleem bestaan ​​deterministische oplossingen. Het algoritme van Dijkstra vindt bijvoorbeeld het kortste pad van een startknooppunt naar alle andere knooppunten in een gerichte graaf. Dit zal nuttig zijn om de resultaten van ons versterkingsleeralgoritme te evalueren, dat niet gegarandeerd de optimale oplossing zal vinden.

Q-Leren

Q-Learning is een versterkende leertechniek waarbij een agent een tabel bijhoudt van staat-actieparen, gekoppeld aan de verwachte verdisconteerde cumulatieve beloning – de kwaliteitvandaar 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 proefactie a_Jresulterend in de overgang van de staat s_i te verklaren s_keen beloning ren een beste schatting van de kwaliteit van de volgende staat s_kis:

( 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 hoeveel toekomstige beloningen zich verhouden tot onmiddellijke beloningen.
• Q is de kwaliteitsmatrix. De rij-index i is de index van de oorsprongsstatus en de kolomindex j is de index van de geselecteerde actie.

Kortom, vergelijking 1 stelt dat de kwaliteit van (staat, 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 volgende staat ten opzichte van mogelijke acties.

Voor onze probleemstelling zou een mogelijke formulering voor de toestand het paar zijn (huidig ​​knooppunt, doelknooppunt), en de reeks acties zou de reeks knooppunten zijn. De statusset zou dan bevatten N² waarden, en de actieset zou bevatten N waarden, waar N is het aantal knooppunten. Omdat de grafiek echter schaars is, heeft een bepaald oorsprongsknooppunt slechts een kleine subset van knooppunten als uitgaande randen. Deze formulering zou resulteren in een Q-matrix waar de grote meerderheid van de N³ vermeldingen worden nooit bezocht, waardoor onnodig geheugen wordt verbruikt.

Gedistribueerde agenten

Een beter gebruik van de middelen is het verdelen van de agenten. Elk knooppunt kan worden gezien als een agent. De status van de agent is het doelknooppunt, vandaar zijn Q-matrix heeft N rijen en N_uit kolommen (het aantal uitgaande randen voor dit specifieke knooppunt). Met N agenten, het totale aantal matrixinvoer is N²N_uitwat lager is dan N³.

Samenvattend:

• We gaan trainen N agenten, één voor elk knooppunt in de grafiek.
• Elke agent leert a Q-matrix van afmetingen (N x N_uit). Het aantal uitgaande randen (N_uit) kan variëren van knooppunt tot knooppunt. Voor een schaars verbonden grafiek, N_uit .
• De rij-indexen van de Q-matrix komt overeen met de status van de agent, dat wil zeggen het doelknooppunt.
• De kolomindexen van de Q-matrix komt overeen met de uitgaande rand die door een agent is geselecteerd om een ​​bericht naar het doelknooppunt te routeren.
• Q(i, j) vertegenwoordigt de inschatting van een knooppunt van de kwaliteit van het doorsturen van het bericht naar zijn knooppunt j^e uitgaande rand, gegeven het doelknooppunt i.
• Wanneer een knooppunt een bericht ontvangt, wordt het doelknooppunt daarin opgenomen. Omdat de afzender van het vorige bericht niet nodig is om de routering van het volgende bericht te bepalen, wordt dit niet in dit laatste opgenomen.

Code

De kernklasse, 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_nodes

De 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 beloningen uit het milieu zullen het negatieve zijn van de randkosten. De kwaliteitswaarden zullen dus allemaal negatief zijn. Om deze reden is initialiseren met nullen een optimistische initialisatie.

Wanneer een bericht een QNode object, selecteert het een van de uitgaande randen via de epsilon-hebzuchtig algoritme. Als ε klein is, selecteert het epsilon-greedy-algoritme meestal de uitgaande flank met de hoogste 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 lijst met knooppunten en de reeks randkosten. Merk op dat de werkelijke randen deel uitmaken van de QNode klasse, als een lijst met uitgaande knooppunten.

Wanneer we een pad willen genereren van een startknooppunt naar een doelknooppunt, noemen we de QGraph.trajectory() methode, die de 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() methode retourneert de lijst met bezochte knooppunten langs het pad en de lijst met kosten die zijn gekoppeld aan de randen die zijn gebruikt.

Het laatste ontbrekende stukje is de updateregel van vergelijking 1, geïmplementeerd door de 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, doorlopen we de paren iteratief (start_node, target_node) met een binnenlus over de aangrenzende knooppunten van start_nodeen wij bellen update_Q().

Experimenten en resultaten

Laten we beginnen met een eenvoudige grafiek van 12 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 naast deze twee knooppunt-1 en knooppunt-7 bereiken. Wanneer een ander knooppunt de taak krijgt een bericht naar knooppunt 1 of knooppunt 7 te sturen, stuitert het bericht door de grafiek totdat het maximale aantal hops is bereikt. We verwachten een groot negatief resultaat 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 knooppunt 4 naar bijvoorbeeld knooppunt 11 kan worden verkregen door de trajectory() methode, instelling epsilon=0 voor de hebzuchtige deterministische oplossing: (4, 3, 5, 11) voor een totale niet-gedisconteerde prijs van 0,9 + 0,9 + 0,3 = 2,1. Het Dijkstra-algoritme retourneert hetzelfde pad.

In enkele zeldzame gevallen werd het optimale pad 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 (6, 0, 4, 10, 2, 9) retourneerde voor een totale niet-gedisconteerde prijs van 3,4. Zoals we eerder hebben aangegeven, wordt dit verwacht van een iteratief algoritme

Conclusie

We formuleerden het Small-World Experiment als een probleem van het vinden van het pad met minimale kosten tussen elk paar knooppunten in een schaars gerichte 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 lieten we zien dat de training tot een oplossing leidde die dicht bij de optimale lag.

Bedankt voor uw tijd en experimenteer gerust met de code. Heb jij ideeën voor leuke toepassingen voor Q-Learning, laat het mij weten!

¹ 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