Modellering af afhængigheder imellem variable ved brug af grafiske modeller - Introduktion til bayesianske netwærk og t-kirsebærtræer
Oversat titel
Modeling Dependencies between Variables with Graphical Models - Intruduction to Bayesian Networks and t-Cherry Trees
Forfattere
Kirkeby, Katrine Engilbertsdottir ; Knudsen, Maria ; Vihrs, Ninna
Semester
4. semester
Uddannelse
Udgivelsesår
2019
Afleveret
2019-05-20
Antal sider
134
Resumé
Dette speciale undersøger, hvordan afhængigheder mellem kategoriske variable kan modelleres med grafiske modeller, med en kort introduktion til bayesianske netværk og hovedfokus på en klasse af uorienterede modeller kaldet k'te ordens t-kirsebærtræer, som generaliserer Chow-Liu-træer ved at tillade interaktioner mellem op til k variable. Vi udleder udtryk for likelihood og Kullback–Leibler-afstand for t-kirsebærtræer og viser, at begge kriterier kan optimeres ved at maksimere en strukturvægt. Med dette grundlag opstiller vi flere algoritmer til strukturlæring: grådige metoder, der tilføjer kliker trinvis, udtømmende afsøgning af alle mulige grafer samt strategier, der enten øger ordenen af et eksisterende t-kirsebærtræ eller konstruerer et k'te ordens træ direkte fra data. Algoritmerne implementeres og evalueres på simulerede og udvalgte datasæt med fokus på korrekthed af den fundne struktur, tilnærmelse af den sande fordeling, beregningstid og klassifikationspræstation. Numeriske resultater viser, at det er hurtigere at øge ordenen fra et lavere niveau end at konstruere direkte fra data, men at den direkte konstruktion bedre identificerer den sande struktur og giver den bedste tilnærmelse målt ved Kullback–Leibler-afstand. Grådige metoder finder ofte maksimal eller næsten maksimal vægt, især når flere kliker tilføjes pr. trin, dog på bekostning af længere køretid. I klassifikationsopgaver kan t-kirsebærtræer være meget præcise, når datasættet er tilstrækkeligt og ordenen vælges passende; høje ordener kan medføre overtilpasning. For at afbøde dette udvikles en kant-udtyndingsalgoritme baseret på likelihood-ratio-test, som succesfuldt forenkler modeller og kan bevare eller forbedre præstationen. Arbejdet er afgrænset til kategoriske variable og strukturlæring ud fra observerede data.
This thesis examines how dependencies among categorical variables can be modeled with graphical models, offering a brief introduction to Bayesian networks and focusing on a class of undirected models called kth-order t-cherry trees, which generalize Chow–Liu trees by allowing interactions among up to k variables. We derive expressions for the likelihood and the Kullback–Leibler divergence for t-cherry trees and show that both criteria can be optimized by maximizing a structure weight. Building on this, we propose several structure-learning algorithms: greedy procedures that add cliques stepwise, exhaustive searches over candidate graphs, and strategies that either increase the order of an existing t-cherry tree or construct a kth-order tree directly from data. The algorithms are implemented and assessed on simulated and selected real data sets with attention to recovery of the true structure, approximation quality, runtime, and classification performance. Numerical results indicate that increasing the order from a lower-order tree is faster than constructing the structure directly from data, whereas direct construction better identifies the true graph and provides the closest approximation in terms of Kullback–Leibler divergence. Greedy approaches often find structures with maximal or near-maximal weight, further improved by adding multiple cliques per step at the cost of longer execution time. In classification tasks, t-cherry trees can be highly accurate when data are sufficient and the order is chosen appropriately; higher orders tend to overfit. To mitigate overfitting, we develop an edge-thinning algorithm based on likelihood-ratio tests that successfully simplifies high-order models and can maintain or improve performance. The scope is limited to categorical variables and structure learning from observed data.
[Dette resumé er genereret med hjælp fra AI direkte fra projektet (PDF)]
Emneord