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

over het Small World Experiment van Stanley Milgram in de jaren zestig. Hij ontwierp een experiment waarbij een brief werd gegeven aan een vrijwilliger in de Verenigde Staten, met instructies om de brief door te sturen naar hun persoonlijke contacten die waarschijnlijk een andere persoon – het doelwit – in hetzelfde land kenden. Op zijn beurt wordt de ontvanger van de brief gevraagd de brief opnieuw door te sturen totdat de beoogde persoon is bereikt. Hoewel het merendeel van deze brieven nooit de beoogde ontvangers bereikt, is het gemiddelde aantal sprongen bij degenen die dat wel doen (overlevingsvooroordelen spelen hier een rol!), ongeveer zes. “Zes graden van scheiding” is een culturele verwijzing geworden naar de nauwe onderlinge verbondenheid van de samenleving.

Ik ben nog steeds verbaasd over de gedachte dat mensen met ~10² contact succesvol verbonden met willekeurige persoon op netwerk ~10⁸ mensen, via verschillende sprongen.

Hoe zou het kunnen? Heuristiek.

Stel dat mij wordt gevraagd een brief te sturen naar de geadresseerde in Finland¹.

Helaas heb ik geen contacten in Finland. Aan de andere kant ken ik iemand die jarenlang in Zweden heeft gewoond. Misschien kent hij mensen in Finland. Zo niet, dan heeft hij waarschijnlijk nog contacten in Zweden, een buurland. Hij is mijn beste keuze om dichter bij de doelgroep te komen. Het punt is dat zelfs als ik de topologie van sociale netwerken buiten mijn persoonlijke contacten niet ken, ik vuistregels kan gebruiken om de e-mail in de goede richting door te sturen.

Als we het standpunt van de netwerkknooppunten (mensen die betrokken zijn bij het experiment) innemen, is de beschikbare actie het doorsturen van het bericht (de brief) naar een van de uitgaande doelen (het persoonlijke contact). Het probleem om berichten in de goede richting te krijgen, biedt de mogelijkheid om plezier te hebben met machine learning!

Knooppunten begrijpen niet de gehele netwerktopologie. We kunnen een omgeving opzetten die hen beloont voor het routeren van berichten langs de kortst bekende paden, terwijl ze worden aangemoedigd om minder optimale kandidaatpaden te verkennen. Klinkt als een geweldige use case voor versterkend leren, toch?

Voor degenen die geïnteresseerd zijn in het uitvoeren van de code, kunt u hier toegang krijgen tot de repository.

Het probleem

We krijgen een gerichte grafiek waarin de randen tussen knooppunten schaars zijn, wat betekent dat het gemiddelde aantal randen dat uit een knooppunt komt veel 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 lettersprong 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, met de laagst mogelijke kosten, als zo’n pad bestaat. Er bestaat een deterministische oplossing voor dit probleem. Het algoritme van Dijkstra vindt bijvoorbeeld het kortste pad van een startknooppunt naar alle andere knooppunten in een gerichte graaf. Het zal nuttig zijn om de resultaten van ons versterkingsleeralgoritme te evalueren, wat niet garandeert dat de optimale oplossing wordt gevonden.

Q-Leren

Q-Learning is een versterkende leertechniek waarbij een agent een tabel bijhoudt van actie-statusparen, geassocieerd met verwachte verdisconteerde cumulatieve beloningen – de kwaliteitDaarom Q-Leren. Door herhaalde experimenten wordt de tabel bijgewerkt totdat aan het stopcriterium is voldaan. Na de training kan de agent acties selecteren (kolommen van matrix Q) die overeenkomen met de maximale kwaliteit, voor een bepaalde toestand (rijen van matrix Q).

Update regels, gegeven testacties a_Jresulterend in een staatsovergang s_I verklaren s_kcadeau ren de volgende beste schatting van de staatskwaliteit s_kis:

( Q(i, j) linkerpijl (1 – alpha) Q(i, j) + alpha left( r + gamma max_{l} Q(k, l) right) )

_{Vergelijking 1: 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 de toekomstige beloning zich verhoudt tot de onmiddellijke beloning.
• Q is de kwaliteitsmatrix. Rij-index i is de thuislandindex en de kolomindex j is de index van de geselecteerde actie.

Kortom, vergelijking 1 stelt dat de kwaliteit (staat, actie) gedeeltelijk moet worden bijgewerkt met een nieuwe kwaliteitswaarde, die bestaat uit de som van de onmiddellijke beloningen en de geschatte maximale kwaliteitskorting van de volgende staat ten opzichte van de mogelijke acties.

Voor onze probleemstelling zijn de mogelijke toestandsformuleringen paren (huidig ​​knooppunt, doelknooppunt) en is de actieset een verzameling knooppunten. De statusset bevat dan N² waarde, en de actieset zal bevatten N waarde, waar N is het aantal knooppunten. Omdat de grafiek echter schaars is, heeft een bepaald oorsprongspunt slechts een klein deel van de hoekpunten als uitgaande randen. Deze formulering zal een Q-matrix waar de meeste N³ inzendingen worden nooit bezocht, waardoor onnodig geheugen wordt verspild.

Gedistribueerde agenten

Een beter gebruik van middelen is het distribueren van agenten. Elk knooppunt kan als een agent worden beschouwd. De agentstatus is daarom het doelknooppunt Q-matrix heeft N rij en N_{ga naar buiten} kolom (aantal uitgaande randen voor dit specifieke knooppunt). Met N agent, het totale aantal matrixinvoeren is N²N_{ga naar buiten}wat lager is dan N³.

Samenvattend:

• We zullen oefenen N agenten, één voor elk knooppunt in de grafiek.
• Elke agent leert a Q-dimensionale matrix (N x N_{ga naar buiten}). Aantal uitgaande randen (N_{ga naar buiten}) kan variëren van knooppunt tot knooppunt. Voor een schaars verbonden grafiek, N_{ga naar buiten} << N.
• Rij-index van Q-matrix komt overeen met de status van de agent, namelijk het doelknooppunt.
• Kolomindex van Q-matrix komt overeen met de uitgaande rand die door de agent is gekozen om berichten naar het doelknooppunt te routeren.
• Q(i, j) vertegenwoordigt de schatting van een knooppunt van de kwaliteit van het doorsturen van berichten naar dat knooppunt j^e de uitgaande rand, rekening houdend met 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 de afzender van dat bericht niet opgenomen in het volgende bericht.

Code

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

Klas QNode heeft drie velden: aantal knooppunten in de grafiek, lijst met uitgaande randen, en Q-matrix. Dat Q-matrix wordt geïnitialiseerd met nul. De beloning uit het milieu zal de negatieve waarde van de meerkosten zijn. Daarom zullen de kwaliteitswaarden allemaal negatief zijn. Daarom is initialisatie met nul een optimistische initialisatie.

Wanneer een bericht een QNode object, selecteert het een van zijn uitgangsranden epsilon-hebzuchtig algoritme. Als ε klein is, kiest het epsilon-greedy-algoritme vaak de uitgangsrand met de hoogste waarde. Q-markering. Zo nu en dan kiest het een willekeurige uitgangsrand:

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

Een andere klasse is graphics, 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 rand er eigenlijk deel van uitmaakt QNode klasse, als een lijst met exit-knooppunten.

Wanneer we een pad willen creëren van het startknooppunt naar het 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

Dat trajectory() De methode retourneert een lijst met bezochte knooppunten langs het pad en een 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) <- (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 agent te trainen, herhalen we de paren iteratief (start_node, target_node) met binnenlussen over aangrenzende knooppunten start_nodeen wij belden 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 knooppunt dat naar Knooppunt 1 gaat Knooppunt 7 is, en het enige knooppunt dat naar Knooppunt 7 gaat, Knooppunt 1 is. Daarom kan geen enkel ander knooppunt naast deze twee knooppunt-1 en knooppunt-7 bereiken. Wanneer een ander knooppunt is toegewezen om een ​​bericht naar knooppunt 1 of knooppunt 7 te sturen, stuitert het bericht door de grafiek totdat het maximale aantal hops is bereikt. Wij verwachten grote negatieve gevolgen Q-waarde in dit geval.

Wanneer we de 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 het zover Q-matrix voor Knooppunt-4:

Het pad van Knooppunt-4 naar bijvoorbeeld Knooppunt-11 kan worden verkregen door te bellen 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 algoritme van Dijkstra retourneert hetzelfde pad.

In sommige zeldzame gevallen wordt het optimale pad niet gevonden. Om bijvoorbeeld van knooppunt 6 naar knooppunt 9 te gaan, retourneert het specifieke exemplaar van de getrainde Q-grafiek (6, 11, 0, 4, 10, 2, 9) met een totale niet-gedisconteerde kosten van 3,5, terwijl het algoritme van Dijkstra retourneert (6, 0, 4, 10, 2, 9) met een totale niet-gedisconteerde kosten van 3,4. Zoals we eerder hebben aangegeven, wordt dit verwacht van een iteratief algoritme

Conclusie

We formuleren het Small World Experiment als het probleem van het vinden van het pad met minimale kosten tussen elk paar knooppunten in een dun gerichte graaf met gewogen randen. We implementeren de knooppunten als Q-Learning-agents, die via updateregels leren om de meest kosteneffectieve actie te ondernemen, op basis van het doelknooppunt.

Met een eenvoudige grafiek laten we zien dat training een oplossing oplevert die bijna optimaal is.

Bedankt voor uw tijd en experimenteer gerust met deze code. Heb jij een idee voor een leuke app 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.

Referentie

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