Vi introducerar en probabilistisk formalism som subsumerar Markov slumpmässiga fält av avgränsad trädbredd och probabilistisk kontextfri grammatik. Våra modeller bygger på en representation av Booleska formler som vi kallar case-faktordiagram (CFD). CFDs liknar binära beslut diagram (BDDs) men är koncisa för kretsar med begränsad trädbredd (till skillnad från BDDs) och kan koncis representera uppsättningen av parse träd över en given sträng under en given sammanhangsfri grammatik (också till skillnad från BDDs). En probabilistisk modell består av en CFD som definierar en genomförbar uppsättning booleska uppdrag och en vikt (eller kostnad) för varje enskild boolesk variabel. Vi ger en insideoutside-algoritm för att samtidigt beräkna marginalen för varje boolesk variabel, och en Viterbi-algoritm för att hitta mininum kostnadsvariabeln uppdrag. Båda algoritmerna löper i tid i proportion till storleken på CFD.
McAllester REF introducerade fallfaktordiagram (CFD) som underställer Markov slumpmässiga fält med begränsad trädbredd och probabilistisk kontextfri grammatik (PCFG).
Case-Factor Diagrams for Structured Probabilistic Modeling
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}