Vi anser att problemet med att rekonstruera grafen bakom en Ising modell från i.i.d. Prover. Under de senaste femton åren har detta problem varit av stort intresse för statistik, maskininlärning och statistiska fysiksamhällen, och mycket av arbetet har inriktats på att hitta algoritmer med låga beräkningskostnader för olika begränsade klasser av modeller. Icke desto mindre, för att lära Ising modeller på allmänna grafer med p noder av grad som mest d, är det inte känt om det är möjligt att förbättra p d beräkning behövs för att uttömmande söka i alla möjliga bostadsområden för varje nod. I detta papper visar vi att en enkel girig procedur gör det möjligt att lära sig strukturen av en Ising modell på en godtycklig begränsad grad graf i tid i storleksordningen p 2. Vi gör inga antaganden om parametrarna förutom vad som är nödvändigt för att identifiera modellen, och i synnerhet resultaten håller vid låga temperaturer samt för mycket icke-uniforma modeller. Beviset vilar på en ny strukturell egendom av Ising modeller: vi visar att för varje nod finns det åtminstone en granne med vilken det har en hög ömsesidig information.
Deras algoritm generaliserar Breslers tillvägagångssätt för lärande Ising-modeller REF.
Efficiently Learning Ising Models on Arbitrary Graphs
{'venue': "STOC '15", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}