I det här dokumentet tar vi upp problemet med att lära sig oriktade grafiska modeller från data som genereras enligt Glauberdynamiken. Glauber dynamiken är en Markov kedja som gradvis uppdaterar enskilda noder (variabler) i en grafisk modell och det används ofta för att prov från den stationära fördelningen (till vilken den konvergerar ges tillräckligt med tid). Dessutom är Glauber dynamiken en naturlig dynamisk modell i en mängd olika miljöer. Detta arbete avviker från standardformuleringen av grafisk modellinlärning i litteraturen, där man förutsätter tillgång till i.i.d. Prover från distributionen. Mycket av forskningen om grafisk modellinlärning har riktats mot att hitta algoritmer med låga beräkningskostnader. Som det huvudsakliga resultatet av detta arbete, fastställer vi att problemet med att rekonstruera binära parvis grafiska modeller är beräkningsbart när vi observerar Glauber dynamik. Specifikt visar vi att en binär parvis grafisk modell på p noder med maximal grad d kan läras i tid f (d)p 3 log p, för en funktion f (d), med nästan den information-teoretiska minsta möjliga antal prover. Det finns ingen känd algoritm av jämförbar effektivitet för att lära godtyckliga binära parvisa modeller från i.i.d. Prover.
Den viktigaste observationen i REF är att problemet med att lära grafer genom att observera Glauber dynamik är beräkningsbart.
Learning graphical models from the Glauber dynamics
{'venue': '2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton)', 'journal': '2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}