Att hitta den mest troliga uppgiften (MAP) i en allmän grafisk modell är känt för att vara NP hårt men bra approximationer har uppnåtts med max produkt tro förökning (BP) och dess varianter. I synnerhet är det känt att använda BP på en encykel graf eller träd omvägd BP på en godtycklig graf kommer att ge MAP-lösningen om övertygelsen inte har några band. I detta dokument utvidgar vi den inställning under vilken BP kan användas för att på ett tydligt sätt extrahera MAP. Vi definierar Convex BP som BP algoritmer baserade på en konvex fri energi approximation och visar att denna klass inkluderar vanliga BP med enkel-cykel, träd reviktade BP och många andra BP varianter. Vi visar att när det inte finns några band kommer fasta punkter av konvex maxprodukt BP att ge MAP-lösningen. Vi visar också att konvex summa-produkt BP vid tillräckligt små temperaturer kan användas för att lösa linjära program som uppstår genom att koppla av MAP-problemet. Slutligen härleder vi ett nytt tillstånd som gör att vi kan härleda MAP-lösningen även om vissa konvexa BP övertygelser har band. I experiment, visar vi att våra teorem tillåter oss att hitta MAP i många verkliga fall av grafiska modeller där exakt slutsats med hjälp av korsningsträd är omöjligt.
I synnerhet, för alla konvexa max-produkt BP algoritmer som beskrivs i REF, är det lätt att utforma region-pursuit metoder.
MAP Estimation, Linear Programming and Belief Propagation with Convex Free Energies
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}