／var／logmarcus chiu

Graphical Models

Created on · Last Modified on

Graphical Models

  • are graphs used to model a specific problem/domain in which one can answer domain-specific queries and/or extract information from the graphical model itself
  • the structure can capture the dependencies and independencies in the knowledge base

Formal Definition

A graphical model 𝒢 is a tuple 𝒢 = ⟨𝐗, 𝐃, 𝐒, 𝐅, 𝐂⟩ where:

  • 𝐗 = {𝑋1, …, 𝑋𝑛} set of ordered variables
  • 𝐃 = {𝐷1, …, 𝐷𝑛} set of corresponding domains of each variable 𝑋𝑖 (e.g. if 𝑋1is a boolean variable then 𝐷1= {true, false}). The size of each 𝐷𝑖corresponds to the cardinality of variable 𝑋𝑖
  • 𝐒 = {𝑆1, …, 𝑆𝑚} set of variable scopes, where each variable scope 𝑆𝑖is a subset of 𝐗 (i.e. 𝑆𝑖 ⊆ 𝐗)
  • 𝐅 = {𝐹1, …, 𝐹𝑚} set of factors/functions, where each factor/function 𝐹𝑖 is defined over its corresponding variable scope 𝑆𝑖and maps any assignment over its scope to a real value
  • 𝐂 is a set of combination operators which defines how functions are combined. common combination operators are:
    • summation operator (𝛴)
    • multiplication operator (𝛱)
    • AND operator (∧) - for Boolean functions
    • relational join operator (⨝) - when the functions are relation
    • marginalization operator - for reasoning queries
    • max operator - e.g. = argmax𝑦[ 𝐹𝑖(𝑥,𝑦) ] = 𝐹𝑗(𝑥) where 𝐹𝑗is a new function with scope over variable 𝑥

the set of local functions can be combined in a variety of ways (e.g. combination operators) to generate a new local function or even a global function

Problem Domains that Uses Graphical Models

Problem Domain & Query Types

Graphical Model Types

modeling costs

finding optimal solution given costs:

  • minimum
  • maximum

Cost Networks - defined by costs functions

Optimization

modeling constraints

finding a solution given constraints:

Constraint Networks (Constraint Satisfaction Problems (CSP)) - defined by relations of allowed tuples

modeling probabilities:

Probabilistic Networks (Probabilistic Graphical Models (PGM) - Structured Probabilistic Models (SPM)) - defined by conditional probability tables over a subset of variables or by a set of potentials

modeling knowledge base:

modeling linear inequalities

…

modeling a mixture of:

  • probabilities
  • constraints
  • costs
  • knowledge base

Mixed Networks - a graphical model with probabilistic information and deterministic constraints

Main Tasks For Using Graphical Models

  1. building the graphical model that accurately describes the problem domain
  2. extracting information or answering questions, schemes:
    • inference-based schemes
      • performs a deductive step repeatedly while maintaining a single view of the model. By doing this, inference-based algorithms augment the original model specification making it more explicit (i.e. less implicit)
      • are good at exploiting the independencies displayed by the underlying graphical model and in avoiding redundant computation
      • algorithm type:
        • exact inference
        • approximate inference
      • some example algorithms:
        • resolution
        • variable-elimination
        • join-tree clustering
      • have worst-case time guarantee which is exponential in the treewidth of the graph. Unfortunately, any inference-based method that is time-exponential in the treewidth is also space exponential in the treewidth and therefore, not feasible for models that have large treewidth
    • search-based schemes
      • perform repeatedly a conditioning step, namely, fixing the value of a variable to a constant, and thus restrict the attention to a subproblem. Search methods are more naturally poised to exploit the internal structure of the functions themselves, namely, their local structure
      • search requires only an implicit, generative, specification of the functions (given in a procedural or functional form) while inference schemes often rely on an explicit tabular representation over the (discrete) variables. For these reasons search algorithms are the only choice available for models with large treewidth, large domains, and implicit representation
      • algorithm types:
    • search & inference schemes
      • when combined they enable improved performance by flexibly trading-off time and space
    • re-parameterization schemes
      • a type of inference-based scheme that induces an equivalent specification of the problem from which answers can be produced more easily

Subpages