I det här dokumentet tar vi upp problemet med att lära sig strukturen på en parvis grafisk modell från prover i en högdimensionell miljö. Vårt första huvudresultat studerar sparsistens, eller konsekvens i sparsamhet mönster återvinning, egenskaper hos en framåt-bakåt girig algoritm som tillämpas på allmänna statistiska modeller. Som ett specialfall använder vi sedan denna algoritm för att lära oss strukturen av en diskret grafisk modell via områdesuppskattning. Som en följd av vårt allmänna resultat, vi härleda tillräckliga villkor på antalet prover n, den maximala nodegrade d och problemet storlek p, liksom andra villkor på modellen parametrar, så att algoritmen återhämtar alla kanter med hög sannolikhet. Vårt resultat garanterar grafval för provskalning som n =  på (d 2 log(p)), i motsats till befintliga konvex-optimering baserade algoritmer som kräver ett prov komplexitet av.(d 3 log(p)). Dessutom kräver den giriga algoritmen endast ett begränsat starkt konvexitetstillstånd som är typiskt mildare än orepresenterbara antaganden. Vi bekräftar dessa resultat med hjälp av numeriska simuleringar i slutet.
Prestandan av en framåt-bakåt girig sökning efter Markov nätverk i en högdimensionell inställning studeras i REF.
On Learning Discrete Graphical Models Using Greedy Methods
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}