1、A Quick Romp Through Probabilistic Relational Models,Teg Grenager NLP Lunch February 13, 2003,Agenda,Bayesian Networks Probabilistic Relational Models Learning PRMs Expressivity Applications to NLP,Agenda,Bayesian Networks Probabilistic Relational Models Learning PRMs Expressivity Applications to NL
2、P,Propositional Logic,Ontological commitment: the world consists of propositions, or facts, which are either true or false: HighPaperRating Set of 2n possible worlds one for each truth assignment to the n propositions Propositional logic allows us to compactly represent restrictions on possible worl
3、ds: If HighPublicationRating then HighPaperRating Means that we have eliminated the possible worlds where HighPublicationRating is true but HighPaperRating is false.,Propositional Uncertainty,To model uncertainty we would like to represent a probability distribution over possible worlds. To represen
4、t the full joint distribution we would need 2n-1parameters (infeasible) Insight: the value of most propositions isnt affected by the value of most other propositions! More formally, some propositions are conditionally independent of each other given the value of other propositions,Bayesian Networks,
5、We use a directed acyclic graph to encode these independence assumptionsThis model encodes the assumption that each variable is independent of its non-descendents given its parents,AuthorInstitution,PaperRating,AuthorRating,JournalRating,PaperCited,Factorization,If a BN encodes the true independence
6、 assumptions of a distribution, we can use a factored representation for the distribution:To specify the full joint we need only the conditional probabilities of a variable given its parents,Bayesian Networks,The full joint over these five binary variables would need 25-1=31 parameters, but this fac
7、tored representation only needs 10!,AuthorInstitution,PaperRating,AuthorRating,JournalRating,PaperCited,Inference in Bayes Nets,Query types (given evidence z): Conditional probability query: what is the probability distribution over the values of subset y? Most probable explanation query: what is th
8、e most likely assignment of values to all remaining variables x-z? Maximum a posteriori query: what is the most likely assignment of values to subset y? Worst case, inference is NP-hard In practice, much easier,Variable Elimination,AuthorInstitution,PaperRating,AuthorRating,JournalRating,PaperCited,
9、Learning Bayes Nets,We want to learn a BN from a dataset D that consists of m tuples, each of the form x(m), specifying the value of all variables xi Two problems: Given a graphical model G, estimate the the conditional probability distribution at each node (parameter estimation) Select the best gra
10、phical model (structure learning),Parameter Estimation,Note that we can decompose this and estimate the parameters separately:Can also take a Bayesian approach,Structure Learning,Hypothesis space: Exponential number of possible structures over the variables Scoring function (minimum description leng
11、th or Bayesian) includes: Likelihood of the structure given the data and the maximum likelihood parameters Description length of the graph and CPDs Search algorithm: Operators: add, delete, and reverse an edge Greedy hill-climbing with random restart,Agenda,Bayesian Networks Probabilistic Relational
12、 Models Learning PRMs Expressivity Applications to NLP,Bayes Net Shortcomings,BNs lack the concept of an object Cannot represent general rules about the relations between multiple similar objects For example, if we wanted to represent the probabilities over multiple papers, authors, and journals: We
13、 would need an explicit random variable for each paper/author/journal The distributions would be separate, so knowledge about one wouldnt impart any knowledge about the others,Relational Models,Relational models make a stronger ontological commitment: the world consists of objects, and relations ove
14、r them There are many possible relational models (more on this later) PRMs are based on a particular “relational logic” borrowed from databases:,Relational Schema,We define a relational schema to consist of A set of n classes X = X1,Xn Given a class X, a set of attributes A(X) Attribute A of class X
15、 is denoted X.A, and its space of values is denoted V(X.A) Given a class X, a set of reference slots R(X) Reference slot of class X is denoted X., with domain type X and range type of some class Y Each reference slot has an inverse slot -1 A slot chain is a sequence of slots 1, k such that for all i
16、, Range(i)=Domain(I+1),Relational Model Example,Modeling Uncertainty,Given a schema, a possible world specifies: A set of objects in each class An assignment of objects to reference slots An assignment of values to attributes The set of possible worlds is infinite, hard to define a distribution over
17、 Thus a PRM only specifies a distribution over the possible assignment of values to attributes given a set of ground objects and the relations between them,Modeling Uncertainty,More formally, we define: A relational skeleton, , to be a set of objects and relations between them (defined as reference
18、slot values) An instance, , to be an assignment of values to attributes A PRM defines a probability distribution over possible completions of a skeleton Let x.A be the value of x.A in instance ,Relational Model Example,Paper,Publication,Rating,Title,Author,Institution,Rating,Name,Authorship,Paper,Au
19、thor,Citation,From,To,Publication,Rating,Name,Paper,Proc. IJCAI,Publication,5,Rating,OOBNs,Title,Author,U. Maryland,Institution,3,Rating,D. Koller,Name,Authorship,Learning in PRMs,Paper,D. Koller,Author,Publication,3,Rating,Proc. UAI,Name,Author,Institution,Rating,L. Getoor,Name,Authorship,Learning
20、in PRMs,Paper,D. Koller,Author,Authorship,Learning in PRMs,Paper,L. Getoor,Author,Paper,Proc. IJCAI,Publication,Rating,Learning in PRMs,Title,Publication,Rating,Proc. IJCAI,Name,Citation,Learning in PRMs,From,OOBNs,To,PRM Dependency Structure,PRMs assume that the attribute values of objects are each
21、 influenced by only a few other attribute values (as in a BN) Thus we associate with each attribute X.A a set of parents Pa(X.A) These are formal parents; they will be instantiated differently for different objects These sets of parents (one for each attribute) define the dependency structure S of t
22、he PRM,Types of Parents,We define two types of parents for X.A: Another attribute X.B of the same class X E.g., Author.Rating could depend on Author.Institution An attribute of a related object X.B where is a slot chain E.g., Paper.Rating could depend on Paper.Publication.Rating,Relational Model Exa
23、mple,Multisets as Parents,But what if X.B points to more than one value? E.g., Paper.Authorship.Author.Rating points to the ratings of all coauthors of the paper We define an aggregate function, , to map from a multiset of attributes to a summary value (e.g., sum, mean, max, cardinality) We allow X.
24、A to have as a parent (X.B) E.g., Paper.Rating depends on mean(Paper.Authorship.Author.Rating),Relational Model Example,PRM Parameters,As in a BN, for each attribute we define a conditional probability distribution (CPD) over the values of the attribute given the values of the parents More precisely
25、, let U = Pa(X.A) be the set of parents, V(U) be the possible values of U, and uV(U) be some tuple of of values Then we can define a distribution P(X.A|u) parameterized by X.A|u Let S be the union of all X.A|u,Joint Probability Distribution,Now we can use the following factored representation for th
26、e joint probability distribution over possible instances consistent with skeleton :Where O(X) denotes the set of objects in skeleton whose class is X,Acyclicity,Problem: Distribution is not coherent when dependency structure S has cycles Nave approach: Require acyclic class dependency graph This wou
27、ld prohibit a dependency of the genotype of a person (child) on the genotype of a person (parent), even though it is clearly acyclic Better: require certain guaranteed acyclic slots The parent slot above is guaranteed acyclic Graph coloring algorithm for checking legality of dependency structures,St
28、ructural Uncertainty,Reference Uncertainty Uncertainty over values of reference slots R(X) for each object in class X (but range is given) Nave approach: if range of X. has range Y, use distribution over all objects O(Y) Too large, not general Better: use a partition over objects O(Y) Base partition
29、 on a subset of attributes Partition A(Y) Create a selector attribute S which takes a value in the space of values V(Partition) Define parents and a CPD for S,Structural Uncertainty (2),Existence Uncertainty Uncertainty over number of objects in a class Distinguish between determined and undetermine
30、d classes Undetermined classes are typically those representing many-many relations like Citation Place distribution over objects in undetermined classes Consider all “possible” objects in class Create special existence attribute X.E whose values V(E) = true, false Define parents and a CPD for X.E,I
31、nference in PRMs,Given a skeleton (set of objects and relations), a PRM defines a distribution over possible instances (assignments of values to attributes) Same query types as in BNs To answer queries, we compile the PRM to its associated BN, and use BN inference as described earlier (thats it!),Ag
32、enda,Bayesian Networks Probabilistic Relational Models Learning PRMs Expressivity Applications to NLP,Learning PRMs,Training set consists of a fully specified instance: a set of objects, the relations between them, and the values of all attributes In other words, a database! As in BNs, we split into
33、 two problems: Given a dependency structure S, estimate the the conditional probability distribution at each node (parameter estimation) Select the best dependency structure (structure learning),Parameter Estimation,We do maximum likelihood estimation for the BN induced by the structure given the sk
34、eletonParameters are tied for nodes of same class As in BNs, the likelihood function can be decomposed and learned separately As in BNs, can also take a Bayesian approach,Structure Learning,We need a hypothesis space: A hypothesis is a dependency structure, specifying parents for each attribute X.A.
35、 Hypothesis space is infinite because the length of the slot chain leading to the parent attribute is unbounded No problem, we let the search algorithm decide how long to make slot chains We must ensure that the dependency structures we learn is acyclic No problem, just test each dependency structur
36、e before we consider it,Structure Learning (2),We need a scoring function to evaluate the “goodness“ of each candidate hypothesis: We use Bayesian model selection, where the score of a structure S is defined as the posterior probability of the structure given the data :The second component of the sc
37、ore P(S|) = P(S) is a prior over structures To penalize length of slot chains we set logP(S) to be proportional to the total length of the chains in S,Structure Learning (3),The first component of the score is the marginal likelihood:If we use a parameter independent Dirichlet prior (over parameters
38、), this integral decomposes into a product of integrals each of which has a simple closed form solution E.g., uniform Dirichlet prior over parameters Asymptotically equivalent to explicit penalization, such as the MDL score,Structure Learning (4),Finally we need a search algorithm: Greedy hill-climb
39、ing with random restart? Problems: Infinitely many possible structures Process of computing sufficient statistics at each search step requires expensive database joins Heuristic search: Series of phases. At phase k we identify a set of potential parents Potk(X.A) for each attribute X.A We do standar
40、d structure search restricted to space of structures in which each attribute X.A has parents in Potk(X.A) Allows us to precompute database views,Agenda,Bayesian Networks Probabilistic Relational Models Learning PRMs Expressivity Applications to NLP,Relational Models,The most general relational model
41、: the world consists of objects and relations over them First order logic is perhaps the most basic relational setting: Syntax Constants and quantified variables (representing objects) Predicates (representing relations), stated in terms of constants and variables, composed with logical connectives
42、Semantics: Set of possible worlds, one for each possible extent of each relation,Relational Models,Different relational paradigms: First-order logic (from math, phil) Relational algebra (from DB) Entity/Relation models (from DB) Frame-relational systems (from KR) How do they relate to each other? FO
43、L makes the fewest assumptions E/R models add classes (of objects), attributes (of objects), and typed relations FRS add class hierarchies FOL can represent E/R, FRS (of course) E/R, FRS can represent FOL (awkwardly),Relational Models,PRMs as currently defined cannot represent uncertainty in general
44、 FOL Cannot represent uncertainty about whether or not a relation exists between a given tuple of objects Even when we add “structural uncertainty” as proposed PRMs are too specialized The probability of a relation between objects would conditioned on the values of some of their attributes, not on t
45、heir participation in other relations,Alternative Models,Taskar, Abbeel, Koller. Discriminative Probabilistic Models for Relational Data. UAI 2002. Muggleton, S. Stochastic logic programs. Journal of Logic Programming. 2001. Kersting, K. and De Raedt, L. Bayesian logic programs. Work-in-progress Tra
46、ck at the 10th International Conference on ILP. 2000. Poole, D. Probabilistic Horn abduction and Bayesian networks. Halpern, J. An analysis of first-order logics of probability,Agenda,Bayesian Networks Probabilistic Relational Models Learning PRMs Expressivity Applications to NLP,Applications to NLP
47、,Can use it anywhere you want to have parameter tying E.g., Nave Bayes can be represented by PRM Two classes: Document and Feature A(Document) = Document.Class A(Feature) = Feature.Value R(Feature) = Feature.Document Dependency structure: Feature.Value depends on Feature.Document.Class,Relational Cl
48、assification,Hypertext classification, using text and links Previously, iterative labeling algorithms that reassigns labels based on neighbors labels PRMs with “existence uncertainty” provide unified framework for links and text Classes: Page, Anchor, Link (undetermined) A(Page) = Category, Hub, Wor
49、d1,Wordn A(Link) = Exists, V(Link) = From-Page, To-Page A(Anchor) = Word, V(Anchor) = In-Link Learn PRM using Bayesian parameter est. Predict using belief propagation,Relational Clustering,Clustering in a relational domain: e.g., Papers and Citations They use multi-valued reference slots Classes: Paper, Author A(Paper) = Class, Word1,Wordn V(Author) = Cited, Wrote A(Author) = Class Dependency structure has aggregation ops Pa(Paper.Class) = Stoch-Mode(Wrote.Class), Stoch-Mode(Cited.Class) Pa(Paper.Wordi) = Paper.Class Learn with EM, using belief prop for E-step,
