Routing in een dunne 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 waarschijnlijk een andere persoon kent – ​​het doelwit – in hetzelfde land. In ruil daarvoor zou de persoon die de brief ontvangt, worden gevraagd de brief opnieuw door te sturen totdat de beoogde persoon is bereikt. Hoewel de meeste brieven de beoogde persoon nooit bereikten, was het gemiddelde aantal sprongen bij de brieven die dat wel deden (hier speelt overlevingsvooroordeel!) ongeveer 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 het idee 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 al jaren in Zweden woont. 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 zelfs als ik de topologie van het sociale netwerk buiten mijn eigen persoonlijke contacten niet ken, ik vuistregels kan gebruiken om de brief in de goede richting door te sturen.

Als we uitgaan van de knooppunten van het netwerk (de mensen die betrokken zijn bij het experiment), zijn hun beschikbare acties het doorsturen van het bericht (de brief) naar een van hun uitgaande randen (persoonlijke contacten). Dit probleem van het overbrengen van de boodschap in de goede richting biedt de mogelijkheid om plezier te hebben met machinaal leren!

Knooppunten nemen niet de gehele netwerktopologie 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 goed gebruiksscenario 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 waarbij de randen tussen knooppunten schaars zijn, wat betekent dat het gemiddelde aantal uitgaande randen van een knooppunt aanzienlijk minder 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 1 kost.

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

Q-Leren

Q-Learning is een versterkende leertechniek waarbij een agent een tabel bijhoudt met status-actieparen die zijn gekoppeld aan de verwachte verdisconteerde cumulatieve beloning – kwaliteitdaarom 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 informeren s_keen beloning ren een beste schatting van de kwaliteit van de volgende staat s_kis:

( Q(i, j) pijl naar links (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 worden vergeleken met onmiddellijke beloningen.
• Q is de kwaliteitsmatrix. De rij-index i is de index van de herkomststaat en de kolomindex j is de index van de geselecteerde actie.

In het kort zegt vergelijking 1 dat de kwaliteit van (staat, actie) gedeeltelijk moet worden bijgewerkt met een nieuwe kwaliteitswaarde, gemaakt op basis van de som van de onmiddellijke beloning en de verdisconteerde schatting van de maximale kwaliteit van de volgende staat in verhouding tot mogelijke acties.

Voor onze probleemformulering zou een mogelijke formulering voor de toestand het paar zijn (huidig ​​knooppunt, doelknooppunt) en de reeks acties zou de reeks knooppunten zijn. De set van de staat zou dan bevatten N² waarden en de actieset zouden 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 overgrote meerderheid van de N³ records worden nooit bezocht en verbruiken onnodig geheugen.

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 en dus het Q-matrix heeft N gelederen en N_uit kolommen (het aantal uitgaande randen voor dit specifieke knooppunt). Met N agenten, is het totale aantal matrixinvoeren N²N_uitwat lager is dan N³.

Samenvattend:

• Wij trainen N agenten, één voor elk knooppunt in de grafiek.
• Elke agent zal er één leren 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 << N.
• De rij-indexen voor Q-matrix komt overeen met de status van de agent, d.w.z. het doelknooppunt.
• De kolomindexen voor Q-matrix komt overeen met de uitgaande rand die door een agent is gekozen 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 ernaartoe 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 route 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 Q-matrix. De Q-matrix wordt geïnitialiseerd met nullen. De beloningen uit het milieu zullen de negatieve voordelen zijn. Daarom zullen de kwaliteitswaarden allemaal negatief zijn. Om deze reden is initialisatie met nullen een optimistische initialisatie.

Wanneer een bericht een QNode object, selecteert het een van de uitgaande randen er doorheen epsilon-hebzuchtig algoritme. Als ε klein is, kiest het epsilon-greedy-algoritme meestal de uitgaande flank met de hoogste Q-waarde. Af en toe zal het willekeurig een uitgaande kant kiezen:

def epsilon_greedy(self, target_node, epsilon):
        rdm_nbr = random.random()
        if rdm_nbr < epsilon:  # Random choice
            random_choice = random.choice(self.neighbor_nodes)
            return random_choice
        else:  # Greedy choice
            neighbor_columns = np.where(self.Q(target_node, :) == self.Q(target_node, :).max())(0)  # (1, 4, 5)
            neighbor_column = random.choice(neighbor_columns)
            neighbor_node = self.neighbor_node(neighbor_column)
            return neighbor_node

De tweede klasse is grafeen, 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 er deel van uitmaken QNode klasse, als een lijst met uitgaande knooppunten.

Wanneer we een pad willen genereren van een startknooppunt naar een doelknooppunt, bellen we QGraph.trajectory() methode die 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) < self.maximum_hops + 1:
            next_node = self.QNodes(current_node).epsilon_greedy(target_node, epsilon)
            cost = float(self.cost_arr(current_node, next_node))
            visited_nodes.append(next_node)
            costs.append(cost)
            current_node = next_node
            if current_node == target_node:
                return visited_nodes, costs
        # We reached the maximum number of hops
        return visited_nodes, costs

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 in 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) <- (1 - alpha) Q_orig(target, dest) + alpha * ( r + gamma * max_neigh' Q_dest(target, neigh') )
   Q_orig_target_dest = self.QNodes(start_node).Q(target_node, self.QNodes(start_node).neighbor_column(neighbor_node))
   max_neigh_Q_dest_target_neigh = np.max(self.QNodes(neighbor_node).Q(target_node, :))
   updated_Q = (1 - alpha) * Q_orig_target_dest + alpha * (reward + gamma * max_neigh_Q_dest_target_neigh)
   self.QNodes(start_node).Q(target_node, self.QNodes(start_node).neighbor_column(neighbor_node)) = updated_Q

Om onze agenten te trainen, doorlopen we iteratief de paren (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 met 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, springt het bericht rond in de grafiek totdat het maximale aantal hops is bereikt. Wij verwachten grote negatieve gevolgen Q-waarden in deze gevallen.

Wanneer we onze grafiek trainen, krijgen we statistieken van de kosten en het aantal hops als functie van het tijdperk, zoals in figuur 2:

Na de training is dit Q-matrix voor Knooppunt-4:

Het pad van Knooppunt-4 naar b.v. Node-11 kan worden verkregen door te bellen trajectory() methode, instelling epsilon=0 voor de hebzuchtige deterministische oplossing: (4, 3, 5, 11) voor een totale gereduceerde 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 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 korting van 3,5, terwijl het Dijkstra-algoritme terugkeerde (6, 0, 4, 10, 2, 3, 4, 10, 2, 9). Zoals we eerder vermeldden, 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 afnam tot een oplossing die dicht bij de optimale lag.

Bedankt voor je 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 had moeten heten.

Referenties

Versterkingsleren, Richard S. Sutton, Andrew G. Barto, MIT Press, 1998