Relational Data Mining Using Probabilistic Relational Models -- Design, Implementation and Test
Authors
Gade, Morten ; Nielsen, Michael Gade
Term
4. term
Education
Publication year
2005
Abstract
Dette speciale præsenterer design, implementering og test af Probabilistic Relational Models (PRM’er), en grafisk statistisk metode til at modellere relationelle data i Relational Language. En PRM består af to dele: (1) en afhængighedsstruktur, der angiver hvilke attributter der afhænger af andre, og (2) parametre, der kvantificerer disse afhængigheder. Til strukturlæring søger vi over mulige modeller ved hjælp af “potentielle forældre”, dvs. kandidat-forældre (mulige afhængigheder). Vi sammenligner fire søgestrategier: en grådig algoritme (vælger det lokalt bedste), to tilfældige algoritmer og en hybrid, der blander grådige og tilfældige skridt. Til parameterlæring bruger vi sufficient statistics og håndterer eksplicit interne og eksterne afhængigheder, mens vi holder styr på kontekst. Gennem fem tests viser vi, at straftermen i scorefunktionen kan justeres for at balancere tilpasning (maksimum likelihood) mod modelkompleksitet. En begrænset skaleringsundersøgelse indikerer, at vores implementering skalerer næsten lineært, om end yderligere optimering er mulig. I søgeeksperimenter er tilfældighed gavnlig, når den kombineres med grådighed: den grådige metode finder den bedste model, og hybriden kommer tæt på på kortere tid. Sammenlignet med vores tidligere arbejde er PRM’er et stærkt beskrivende alternativ til propositionel data mining.
This thesis presents the design, implementation, and testing of Probabilistic Relational Models (PRMs), a graphical statistical method for modeling relational data in the Relational Language. A PRM has two parts: (1) a dependency structure that specifies which attributes depend on others, and (2) parameters that quantify these dependencies. For structure learning, we search over candidate models using “potential parents,” i.e., possible parent dependencies. We compare four search strategies: a greedy algorithm (choosing the locally best option), two random algorithms, and a hybrid that mixes greedy and random steps. For parameter learning, we use sufficient statistics and explicitly handle internal and external dependencies while tracking context. Through five tests, we show that the penalty term in the score function can be tuned to balance goodness of fit (maximum likelihood) against model complexity. A limited scalability study indicates our implementation scales nearly linearly, though further optimization is possible. In search experiments, adding randomness is beneficial when combined with greediness: the greedy method finds the best model, and the hybrid comes close in less time. Compared with our prior work, PRMs are a strong descriptive alternative to propositional data mining.
[This abstract was generated with the help of AI]
Documents