I detta dokument ger vi nya komplexa resultat för algoritmer som lär sig diskret variabel Bayesian nätverk från data. Våra resultat gäller när lärande algo ritm använder ett poängkriterium som gynnar den enklaste modellen som kan representera den generativa fördelningen exakt. Våra resultat där fore hålla när någonsin inlärningsalgoritmen använder ett konsekvent poängkriterium och är aplyed till en tillräckligt stor dataset. Vi visar att identifiera hög-skorning strukturer är NP-hård, även när vi får en independence oracle, ett inference oracle, och / eller en information oracle. Våra negativa resultat gäller också när man lär sig diskret-variabla Bayesianska nätverk där varje nod har som mest k föräldrar, för alla k 2: 3. Forskare i UAI samhället har allmänt accepterat att utan restriktiva antaganden, lärande Bayesian nätverk från data är NP-hård, och consely en stor mängd arbete i denna gemenskap har ägnats åt heuristic-search tekniker för att identifiera bra modeller. Ett antal nedslående komplicerande resultat har dykt upp under de senaste åren som visar att denna tro är välgrundad. Chick ering (1996) visar att för en allmän (och allmänt använd) klass av Bayesian scoring kriterier, identifiera den högsta-scoring struktur från små urvalsdata är svårt, även när varje nod har högst två parents. Dasgupta (1999) visar att det är svårt att hitta polytree med högsta maximal-likelihood poäng. Även om vi kan identifiera den högsta skärande trädstruktur med hjälp av ett polynom antal anrop till poängkriteriet, Meek (2001) visar att identifiera den bästa vägen struktur - det vill säga ett träd där varje nod har grad som mest två-är svårt. Bouckaert (1994) visar att för självständighetsbaserade inlärningsalgoritmer, hitta den enklaste modellen som överensstämmer med ett beroende orakel är svårt. I detta dokument är vi intresserade av den stora urvalsversionen av det inlärningsproblem som Chick ering (1996) tog upp. Den metod som används av Chickering (1996) för att minska ett känt NP-komplett problem till prob lem av lärande är att konstruera en komplicerad tidigare nätarbete som definierar Bayesian score, och sedan skapa en datauppsättning som består av en enda post. Även om resultatet är nedslående, den bevisteknik lämnar öppen hopp om att, i scenarier där nätverket poäng är mer "väluppfostrade", lärande är mycket lättare. Eftersom antalet poster i de observerade data växer stort, de flesta poängkriterier kommer överens om samma par tiala rangordning av modeller; i synnerhet, alla konsekventa poängkriteriet will-in gränsen för stora data-favor en modell som kan representera den generativa fördelningen över en modell som inte kan, och när man jämför två modeller som båda kan representera den generativa distribution, kommer att gynna modellen med färre parametrar. Nästan alla poängkriterier som används i praktiken är consistält, inklusive 1) varje Bayesianskt kriterium som inte utesluter modeller apriori, 2) kriteriet för minsta angivna längd och 3) bayesisk-informationskriteriet. I det här dokumentet tar vi hänsyn till scenariot när en inlärningsalgoritm använder ett konsekvent poängkriterium med en stor datauppsättning. Vi antar att inlärningsalgoritmen har direkt tillgång till själva den generativa distributionen; inlärningsproblemet är alltså att identifiera den enklaste modellen som kan representera denna distribution exakt. Det finns scenarier där vi kan åstadkomma ett stort urval lärande effektivt. Om (1) det finns en DAG modell lösning där all självständighet och depen dence relationer underförstått av den modellen hålla i den generativa fördelningen (dvs, den generativa distribut är DA G perfekt med avseende på den observerbara
Speciellt eftersom det är NP-hård REF, exponentiellt öka sökutrymmet med antalet variabler.
Large-Sample Learning of Bayesian Networks is NP-Hard
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}