En ny løser til omtrentlig marginal kortslutning

Der er en dyb forbindelse mellem planlægning og slutning, og i løbet af det sidste årti, flere forskere har introduceret eksplicitte reduktioner, der viser, hvordan stokastisk planlægning kan løses ved hjælp af sandsynlige inferens med applikationer inden for robotteknologi, planlægning, og miljøproblemer. Imidlertid, heuristiske metoder og søgning er stadig de bedst ydende tilgange til planlægning i store kombinatoriske tilstands- og handlingsrum. Mine medforfattere og jeg tager en ny tilgang i vores papir, "Fra Stokastisk Planlægning til Marginal MAP" (forfattere:Hao Cui, Radu Marinescu, Roni Khardon), på 2018 Conference on Neural Information Processing Systems (NeurIPS) ved at vise, hvordan ideer fra planlægning kan bruges til slutninger.

Vi udviklede Algebraic Gradient-based Solver (AGS), en ny solver til omtrentlig marginal MAP-inferens. Algoritmen bygger en tilnærmet algebraisk beregningsgraf, der fanger marginaler af tilstands- og belønningsvariabler under uafhængighedsantagelser. Den bruger derefter automatisk differentiering og gradientbaseret søgning for at optimere handlingsvalg. Vores analyse viser, at værdien beregnet af AGS-beregningsgrafen er identisk med løsningen af ​​Belief Propagation (BP), når den er betinget af handlinger. Dette giver en eksplicit forbindelse mellem heuristiske planlægningsalgoritmer og omtrentlig inferens.

Mere specifikt, vi gentager sammenhængen mellem stokastisk planlægning og sandsynlighedsafslutning. Vi foreslår for første gang at bruge en effektiv heuristisk algoritme, som oprindeligt blev designet til at løse planlægningsproblemer for at tackle en central slutningsopgave for probabilistiske grafiske modeller, nemlig den marginale maksimum a posteriori sandsynlighed (MMAP) opgave.

Probabilistiske grafiske modeller såsom Bayesianske netværk eller Markov-netværk giver en meget kraftfuld ramme for ræsonnement om betingede afhængighedsstrukturer over mange variabler. For sådanne modeller, MMAP-slutningsforespørgslen er en særlig vanskelig, men vigtig opgave, svarende til at finde den mest sandsynlige konfiguration (eller maksimere sandsynligheden) over en delmængde af variable, kaldet MAP variabler, efter at have marginaliseret (eller summeret over) resten af ​​modellen.

MMAP-slutning opstår i mange situationer, især i diagnose- og planlægningsopgaver, hvor den mest naturlige specifikation af modellen indeholder mange variabler, hvis værdier vi er ligeglade med at forudsige, men som skaber indbyrdes afhængighed mellem variablerne af interesse. For eksempel, i en modelbaseret diagnoseopgave, givet observationer, vi søger at optimere over en undergruppe af diagnosevariabler, der repræsenterer potentielt svigtende komponenter i et system.

Til illustration, overvej det bayesianske netværk vist i figur 1, som viser et simpelt diagnoseproblem for et computersystem. Modellen fanger direkte kausale afhængigheder mellem seks tilfældige variabler, der bruges til at beskrive dette problem. Specifikt, et systemnedbrud kan være forårsaget af en hardwarefejl, en OS-fejl, eller tilstedeværelsen af ​​malware i systemet. Tilsvarende et strømsvigt kan være almindelig årsag til hardware- og OS-fejl, og stormfuldt vejr kan forårsage strømsvigt. En mulig MMAP-forespørgsel ville være at beregne den mest sandsynlige konfiguration af hardware- og OS-fejl, givet at vi observerer stormfuldt vejr, uanset tilstanden af ​​de andre variabler (malware, Systemnedbrud, eller strømsvigt).

Stokastiske planlægningsrammer såsom Markov-beslutningsprocesser er meget brugt til at modellere og løse planlægningsopgaver under forhold med usikkerhed. Endelig horisontplanlægning kan fanges ved hjælp af et dynamisk Bayesiansk netværk (DBN), hvor tilstands- og handlingsvariabler på hvert tidstrin er repræsenteret eksplicit, og de betingede sandsynlighedsfordelinger af variable er givet af overgangssandsynligheder. I off-line planlægning, opgaven er at beregne en politik, der optimerer den langsigtede belønning. I modsætning, i on-line planlægning får vi en fast begrænset tid t pr. trin og kan ikke beregne en politik på forhånd. I stedet, givet den nuværende tilstand, algoritmen skal beslutte sig for næste handling inden for tid t. Derefter udføres handlingen, en overgang og belønning observeres, og algoritmen præsenteres med den næste tilstand. Denne proces gentages, og algoritmens langsigtede ydeevne evalueres.

Til illustration, overvej figur 2, som viser DBN svarende til et hypotetisk planlægningsproblem, hvor de orange knudepunkter repræsenterer handlingsvariablerne, de blå noder angiver tilstandsvariablerne, og den grønne knude angiver den kumulative belønning, der skal maksimeres. Derfor, at beregne den optimale politik for planlægningsproblemet svarer til at løse en MMAP-forespørgsel over DBN, hvor vi maksimerer over handlingsvariablerne og marginaliserer tilstandsvariablerne.

Vores eksperimentelle evaluering af vanskelige MMAP-problemforekomster viser endegyldigt, at AGS-skemaet forbedrer sig i forhold til når som helst ydeevnen af ​​state-of-the-art algoritmer på MMAP-problemer med hårde summeringsunderproblemer, nogle gange med op til en størrelsesorden. Vi mener, at disse forbindelser mellem planlægning og konklusioner kan udforskes yderligere for at give forbedringer på begge områder.

Denne historie er genudgivet med tilladelse fra IBM Research. Læs den originale historie her.