Research On Some Problems Of Statistical Relational Learning

Contents: Traditional data mining algorithms are based on an attribute-valuesetting which restricts their use to datasets consisting of a single table (or relation), but mostexisting databases in different domains are stored as relational databases containing severalrelations. The task of learning from relational data or (multi-)relational learning has begun toreceive significant attention in Artificial Intelligence.Statistical Relational Learning (SRL), also known as Multi-Relational Data Mining,combines relational/first-order logic representations, Probabilistic reasoning mechanisms,and machine learning/data mining principles together, to capture the likelihood model fromthe relational data. The Statistical Relational Learning algorithms consist of the relationallikelihood model and learning algorithms. The relational likelihood model is the likelihoodform of relational data, and learning is the process to adjust the likelihood model based ondata, including parameters learning and structures learning.Statistical Relational Learning has been used to accomplish the tasks such asclassification, clustering, link predication, social network modeling and object identification,and also applied successfully in fields like bio-information, web navigation, social networks,GIS, natural language understanding, etc.The main contributions and results included in the thesis are as follows:Firstly, the thesis summarizes and analyses the state of arts in Statistical RelationalLearning methods.Relational data being everywhere makes Statistical Relational Learning the highlight ofartificial intelligence. As more and more new SRL methods are proposed, survey on currentSRL methods is necessary.The thesis analyses the background of Statistical Relational Learning. According to therelational likelihood models, we classify the SRL methods into 4 types: SRL methods basedon Bayesian networks, based on (hidden) Markov models, based on stochastic grammars, andbased on Markov networks. The relational likelihood models, parameters learning methods,structure learning methods, and current research of each type are discussed, and theapplications of SRL on internet, bio-information, web navigation, social networks, GIS,natural language understanding are also summarized.Secondly, the thesis studies the theory of Markov Logic Networks.Markov Logic Network (MLN) is a method combining first-order logic and Markovnetwork together. MLN could compute the probability distribution of worlds, and serve forinferring.This thesis discusses the graph models, and ensures the feasibility to import first-orderlogic into Markov networks. We verify the necessity of the three assumptions as uniquenames, domain closure and known functions, and prove the possibility of deleting the threeassumptions. It is concluded that the ground Markov Logic Network generated from theMLN template is effective relational likelihood model of the first-order knowledge bases.Thirdly, the thesis studies the parameter learning methods of Markov Logic Networks.How to learning the structure and parameters of MLN effectively is important for MLN.The parameters of MLN are the weights of formulas in Knowledge base. The higher theweight is, the stronger the formula is, i.e. the greater the difference in probability between aworld that satisfies the formula and one that does not.All the current parameters learning methods for MLN are based on the maximumlikelihood estimation (MLE), which learns parameters from data, ignoring the priorknowledge of humans. A maximum pseudo-posterior estimation based on Bayesian methodis proposed in this thesis, mean Gaussian distribution is used as prior of each weight,likelihood is replaced by pseudo-likelihood, and the pseudo-posterior distribution ismaximized to learn the weights. Experiments show maximum pseudo-posterior estimationcould learn MLNs model effectively, which performs inference better compared to maximumpseudo-likelihood estimation.Fourthly, the thesis studies the classification based on Relational Markov Networks.The objects of traditional classification methods is flat data, and suppose that data areindependent identically distributed (IID), but real data sets consist of entities with differenttypes, which have complicated relations with each other. Classification with the relationaldata is an important research task for Statistical Relational Learning.Relational Markov Network (RMN) is Statistical Relational Learning method, whichcombines Markov networks and the relational representation of data together, to solve theclassification with relational data. Rather than classifying each document separately, RMNprovides a form of collective classification.By analyzing, we find that RMN model is feasible, and the collective classification doesimprove the accurateness of classification. We summarize the applications of RMN,including object identification, collective information extraction, regression, relationsexplanation in GPS, etc. We also compare RMN with MLN, and find RMN is a MLN inessence, and MLN can also used to solve classification.Fifthly, this thesis studies the knowledge representation based on context lattice.Learning the relational likelihood model is the important researching content of SRL,and relational learning system ILP is always used to learn structures of models. Contextknowledge is important concept in ILP, and context lattice is an efficient knowledgerepresentation, which is a lattice structure to represent the relations between worlds.We explain the relationship between lattice and formal lattice, summarize theconstruction process of context lattice, provide six properties of context lattice, and prove thecompleteness of context lattice.Lastly, this thesis studies the multi-relational Web mining based on game theory.Statistical Relational Learning could mine the complex link structure of Web, and theproblems on user of internet almost use multi-agent techniques to simulate the users'activities. If a Nash Equilibrium exists in the game between multi-agents and how to computethis Nash Equilibrium, are very important to multi-relational Web mining.Supposing that users share a single communication link problem, taking advantage ofthe continuity of allocated rate function and other properties, applying Rosen's existencetheorem, we prove that a Nash Equilibrium exists for rate allocation game.We also propose a searching method for finding Nash Equilibrium, which uses the rankand the number of conditionally dominant rows of payoff matrixes, to limit the strategy space,and find a simple NE by searching in this limited space. This algorithm is based on thealgorithm proposed by Porter, but we reduce the size of searching space. Severalcomparisons are committed between the performance of our algorithm and that of theLemke-Howson algorithm implemented in Gambit to assess our algorithm;the result showsthat our algorithm performs better.To sum up, the study results of the thesis are of both theoretical and practical benefit tofurther researches in Statistical Relational Learning.