Detta dokument är det första i den serie som ägnas åt utvärdering av partitionsfunktionen i statistiska modeller på grafer med slingor i termer av integralerna Berezin/fermion. Papperet fokuserar på en representation av bestämningsfaktorn för en fyrkantig matris i termer av en ändlig serie, där varje term motsvarar en slinga på grafen. Representationen är baserad på en fermion version av Loop Calculus, som tidigare introducerades av författarna för grafiska modeller med finita alfabet. Vår konstruktion innehåller två nivåer. För det första representerar vi determinanten i termer av en integral över anti-kommuterande Grassman variabler, med vissa reparametrisering/gauge frihet gömd i formuleringen. För det andra visar vi att ett speciellt val av spårvidden, som kallas BP (Bethe-Peierls eller Belief Propagation), ger önskad slinga representation. Den uppsättning av mätare-fixing BP villkor är likvärdig med Gaussian BP ekvationer, diskuteras i det förflutna som effektiv (linjär skalning) heuristics för att uppskatta kovariansen av en gles positiv matris. PAC-nummer: 02.50. Tt, 64.60.Cn, 05.50.+q Serien i allmänhet, och denna uppsats i synnerhet, tillhör det nya framväxande området för statistisk inferens och grafiska modeller födda på tvärvägarna av statistisk/matematiska fysik, datavetenskap och informationsteori (se följande böcker nyligen som inledande granskningar [1, 2, 3] ). Ett typiskt problem inom området kan anges på följande sätt. Med tanke på en graf (träd, glesa grafer eller gitter är de tre mest populära exemplen), ändliga eller oändliga alfabet med de variabler som definieras på grafelementen (vanligtvis vertexer eller kanter) och en kostnadsfunktion (sannolikhet) i samband med en viss variabler konfiguration, bör man hitta marginaler, korrelationsfunktioner, eller lösa problemet med viktad räkning (beräkna partitionsfunktionen). De huvudsakliga problem som definierar fältet är a) att uppskatta effektiviteten av en exakt utvärdering för ett typiskt eller värsta fall problem för en klass när det gäller dess beroende av problemstorleken, och b) när en exakt utvärdering inte är möjlig, eftersom det krävs ett oacceptabelt stort antal steg, för att föreslå en approximation och ett motsvarande effektivt algoritmiskt genomförande. Ett kraftfullt tillvägagångssätt på statistikområdet är att bygga upp ett effektivt system baserat på ett enkelt fall eller en enkel gräns, där utvärderingen är enkel, dvs. Komplexitet är polynom i antalet variabler. Ett enkelt fall motsvarar träd, dvs. Grafer utan slingor. Efter den s.k. Bethe-Peierls-metoden inspirerad av [4, 5] kan man visa att den beräkningsmässiga ansträngningen för delningsfunktionen på ett träd är linjär i sin storlek. Dessutom förutser man att de trädbaserade metoderna och motsvarande algoritmer bör fungera någorlunda bra på glesa grafer med relativt få slingor. Detta tillvägagångssätt har återuppfunnits och framgångsrikt utforskats i kodningsteori [6] (se t.ex. [7] för en modern diskussion om de grafbaserade koderna) och artificiell intelligens [8], där motsvarande algoritm myntades Belief propagation (BP) och detta namn är nu allmänt accepterat inom alla discipliner. I en ny utveckling föreslog vi en strategi, kallad Loop Calculus (LC) [9, 10], som etablerar en uttrycklig relation mellan BP (tidigare tänkt som bara heuristik) och exakta resultat. Formellt uttrycker LC partition funktion av en grafisk modell i termer av en serie över vissa subgrafer (kallas generaliserade slingor), där varje enskild term (som motsvarar en generaliserad slinga) uttrycks explicit i termer av BP lösning (strikt talat, en fast punkt i motsvarande BP ekvationer). LC, ursprungligen formulerat för ett binärt alfabet, har utökats till ett godtyckligt finit alfabet i [11], och motsvarande tillvägagångssätt har kallats Loop Tower. Det finns också en klass av problem som är lätta trots ett stort antal slingor som finns i den underliggande grafiska strukturen. En så kallad Gaussian Graphical Model (GGM) som tillhör denna klass är nära relaterat till ämnet för denna uppsats. Överväga en grafisk modell med kontinuerliga variabler definieras på vertexes av en graf med en Gaussian par-wise interaktion. Motsvarande partitionsfunktion, som helt enkelt representeras av en flerdimensionell Gaussian integral, reduceras därför till att utvärdera kovariansen (omvänt) av interaktionsmatrisen (observera att denna operation är väl definierad endast om matrisen är positiv bestämd). För en godtycklig interaktion matris, uttryckt i termer av en tät graf, är detta ett problem av N 3 komplexitet, där N är antalet graf hörn. Men som visas i [12, 13], kan man också använda en mer effektiv, linjär i N, Gaussian Belief Propagation (GBP) algoritm för exakta beräkningar av marginalerna inom Gaussian kontinuerlig-alfabet modell. GBP kan också användas för att hitta kovariansen eller utvärdera bestämningsfaktorn för interaktionsmatrisen. Det ger dock inte ett exakt resultat, utan snarare en approximation, som antas vara en tämligen korrekt heuristik åtminstone för tillräckligt glesa grafer. En intuitiv (men också matematiskt sträng) förklaring till exaktheten av GBP i fråga om marginaler och dess insufficiens för kovariansen och tillhörande objekt har getts [14] via den så kallade Walk-Sum Approach (WSA). WSA relaterar det exakta resultatet för covariansen till summan över alla möjliga orienterade vägar på arXiv:0809.3479v2 [cond-mat.stat-mech] 21 Nov 2008 2 grafen, medan GBP (strikt talat asymptotic GBP, utvärderad på ett oändligt beräkningsträd) motsvarar summan över en särskild underfamilj av riktade promenader, särskilt bakåtgående riktade promenader. Detta tillvägagångssätt har också utvidgats för att utvärdera fördelningsfunktionen hos GGM (relaterad till bestämningsfaktorn för interaktionsmatrisen) i [15]. Majoriteten av dessa och andra nyligen genomförda studier av GGM har fokuserat på analysen av förutsättningarna för Gaussian BP konvergens [13, 14, 16, 17, 18, 19] eller praktiska genomföranden av GBP algoritm [17, 20]. Trots dessa viktiga framsteg och den praktiska betydelsen har dock en systematisk analys av noggrannheten hos GBP som en approximation och en möjlighet till systematiska förbättringar av GBP hittills i stor utsträckning lämnats outforskad. Även om vi fortfarande inte kan ge fullständiga svar, rapporterar detta dokument om vissa framsteg mot en framtida lösning av dessa viktiga frågor. I detta dokument introducerar vi en fermionbaserad version av Loop Calculus-metoden på [9, 10, 11 ] som ger en exakt representation för en bestämningsfaktor som en finit loop-serie, där den första termen motsvarar en fast punkt i GBP-algoritmen för motsvarande GGM (att vi också kommer att kalla en lösning av GBP-ekvationerna, eller helt enkelt GBP-lösning). Varje efterföljande term i Loop-serien är kopplad till en slinga på den underliggande grafen och uttrycks uttryckligen i termer av GBP-lösningen. Vårt tillvägagångssätt utforskar kraften i Berezin representation för en avgörande i termer av symboliska integraler över anti-commuting Grassman variabler [21, 22]. Observera, att en relation mellan några binära grafiska modeller på en planar graf och Grassman integraler diskuterades kortfattat i [23]. I denna och efterföljande artiklar i serien [24] tar vi bredare perspektiv och begränsar inte våra diskussioner till planar grafer. Tidningen är organiserad enligt följande. I Avsnitt I inleder vi vår diskussion med en omfattande introduktion (reminder) till Berezin integral approach, som kommer att kulminera i en Grassman integral representation för bestämningen av den underliggande korrelationsmatrisen. Avsnitt II är uppdelat i tre underavsnitt och utgör kärnan i pappret. Gauge transformationer som håller partition funktion av fermion modellen (de avgörande) invariant införs i avsnitt II A. I avsnitt II B tolkas trosförökning som ett villkor för fastsättning av spårvidden. Avsnitt II C slutför byggandet av Loop-serien. Manuskriptet innehåller också två tillägg. Bilaga A är en hjälp till avsnitt II C och innehåller vissa tekniska detaljer om Grassmans integrerade beräkningar. Bilaga B härleder BP-ekvationerna för standardrepresentationen (Bose). I avsnitt III sammanfattas resultaten och diskuteras kortfattat förhållandet mellan de resultat som redovisas i denna rapport och andra resultat och framtida riktningar, t.ex. relaterat till det andra papperet i serien [24].
Denna tolkning har framför allt lett till en bättre förståelse av planar grafiska modeller REF.
Fermions and Loops on Graphs. I. Loop Calculus for Determinant
{'venue': 'J.Stat.Mech.0812:P12011,2008', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Physics', 'Computer Science']}