Abstract-Problemet med grafiskt modellval är att uppskatta grafstrukturen i ett Markov slumpmässigt fält ges prover från det. Vi analyserar informations-teoretiska begränsningar av problemet med grafval för binära Markov slumpmässiga fält under högdimensionell skalning, där grafens storlek och antalet kanter, och / eller maximal nodgrad, tillåts öka till oändlighet som en funktion av provets storlek. För parvis binära Markov slumpmässiga fält, vi härleda både nödvändiga och tillräckliga villkor för korrekt graf val över klassen av grafer på hörn med de flesta kanter, och över klassen av grafer på hörn med maximal grad som mest. För klassen, Vi fastställer förekomsten av konstanter och sådan att Om, Varje metod har fel sannolikhet minst enhetligt över familjen, och vi visar en graf dekoder som lyckas med hög sannolikhet jämnt över familjen för provstorlekar. På samma sätt, för klassen, Vi uppvisar konstanter och sådan att för, Varje metod misslyckas med sannolikhet minst Och vi visar en graf dekoder som lyckas med hög sannolikhet för. Index Terms-High dimensional inference, KL divergens mellan Ising modeller, Markov slumpmässiga fält, prov komplexitet, struktur av Ising modeller.
Santhanam och Wainwright REF erhöll nödvändiga och tillräckliga villkor för att lära sig pairwise binära MRFs.
Information-Theoretic Limits of Selecting Binary Graphical Models in High Dimensions
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Computer Science', 'Mathematics']}