Chapter 15 - Probabilistic Reasoning Systems

Front 1

Belief Network

Back 1

Gives a precise description of the joint probability distribution by representing dependence between variables.

Also called Bayesian network, probabilistic network, causal network or knowledge map

Front 2

What are the four elements that must hold in a belief network?

Back 2

1. A set of random variables make up the nodes

2. Nodes connected by arrows that imply direct influence

3. Each node has a conditional probability table quantifying the effects of the parents on the node

4. Graph has no directed cycles (directed, acyclic graph)

Front 3

Conditional Probability Table

Back 3

Table where each row contains conditional probability for each node value of a conditional case

Front 4

Conditional Case

Back 4

A possible combination of values of parent node (atomic event)

Front 5

What two things are required for a belief network to be a correct representation of a domain?

Back 5

1. Each node must be conditionally independent of it's predecessors given it's parents.

2. It should contain no redundant probability values

Front 6

What is the general procedure for incremental network construction?

Back 6

1. Choose a set of relevant variables that describe the domain

2. Choose an ordering, starting from the root causes

3. Set the parents of each node to the minimal set already in the net such that it has conditional independence, then define its conditional probabilities

Front 7

Locally Structured/Sparse Systems

Back 7

One where each sub-component interacts directly with only a bounded number of other components, regardless of the total number of components

Front 8

Canonical Distribution

Back 8

A standard pattern for relationships between nodes

Front 9

Deterministic Node

Back 9

Node where the value is specified exactly by the value of the parent node (e.g. disjunct, min, sum)

Front 10

What does Noisy-OR do and what are it's three assumptions?

Back 10

Adds uncertainty to logical OR
1. Each cause has an independent chance of causing the effect
2. All possible causes are listed (can add misc node to cover additional causes)
3. Assumes whatever inhibits a cause is independent (e.g. 1 - cause chance)

Front 11

Leak Node

Back 11

Node designed to cover miscellaneous causes as an aggregator

Front 12

Dependency Directed Separation

Back 12

Method for determining if a set of nodes X is independent of Y given evidence nodes E

Front 13

What are three causes of a blocked path?

Back 13

1. Z is in E and has one arrow leading in, and one leading out
2. Z is in E and both arrows lead out
3. Neither Z nor its descendants are in E and both paths lead in to Z

Front 14

D-Seperation

Back 14

A set of nodes E d-separates two sets of nodes X and Y if every undirected path from a node in X to a node in Y is blocked given E.

Means X and Y are conditional independent

Front 15

What are the four types of inference?

Back 15

Diagnostic Inference - From effects to causes

Causal Inference - From causes to effects

Inter-causal Inference - Between causes of a common effect

Mixed Inference - Combining two or more of the above

Front 16

What are 5 uses of beliefs networks?

Back 16

1. Calculating the belief in a query variable given definite values for evidence variables

2. Making decisions based on network probabilities and agent utilities

3. Deciding which additional variables should be observed to gain useful information

4. Performing sensitivity analysis, how much a node's correctness impacts the graph

5. Explaining the results of probabilistic inference to the user

Front 17

Polytree

Back 17

A single connected network in which there is at most one undirected path between any two nodes in the network

Front 18

What is the notation for evidence nodes?

Back 18

Front 19

Multiply Connected Graph

Back 19

One in which two nodes can be connected by more than one path

Front 20

What are the three classes of algorithm that can be used for evaluating multiply connected networks?

Back 20

Clustering - Transforms the network into a probabilistically equivalent polytree

Conditioning - Instantiate variables to definite values and evaluate a polytree for each instantiation

Stochastic Simulation - Generate a large number of concrete models and generate an approximation of the exact evaluation

Front 21

Meganode

Back 21

Combines nodes so their is a single path (polytree).

Can have many more states, e.g. TT, TF, FF, FT

Front 22

Cutset Conditioning

Back 22

Transforms the network into several simpler polytrees in which one of more variables are instantiated

Front 23

Cutset

Back 23

The set of variables that can be instantiated to yield a polytree

Front 24

Bounded Cutset Conditioning

Back 24

Evaluates tree in decreasing order of likelihood until an accepted threshold is reached

Front 25

Logic Sampling

Back 25

Runs repeated simulations and estimates probabilities based on frequencies

Front 26

Likelihood Weighting

Back 26

Instead of initialising random variables based on conditional probabilities, use the conditional probability weight as the likelihood of an outcome

Front 27

Default Reasoning

Back 27

Alternative to probabilistic reasoning where reasoning is handled with default rules and retraction of beliefs.

Examples include default logic, non-monotonic logic, and circumscription

Front 28

What are four issues with default reasoning systems?

Back 28

1. What is the semantic status of default rules?

2. What happens when the evidence matches the premise of two default rules with conflicting resolutions?

3. How does the system keep track of conclusions that need to be retracted? (TMS's)

4. How can beliefs with a default value be used to make decisions?

Front 29

Specificity Preference

Back 29

Where special case rules take precedence over the general case

Front 30

What are four properties logical reasoning systems have over probabilistic ones?

Back 30

1. Monotonicity

2. Locality - Can conclude ideas without worrying about any other rules

3. Detachment - Once a proof is found for a proposition it can be used regardless of how it was derived

4. The truth of complex sentences can be computed from the truth of the components

Front 31

Dempster-Shafer Theory

Back 31

Compute the probability that the evidence supports a proposition to distinguish between uncertainty and ignorance.

Called a belief function and written as Bel(X)

Front 32

Fuzzy Set Theory

Back 32

A means of specifying ow well an object satisfies a vague description

Front 33

Fuzzy Logic

Back 33

Takes a complex sentence and determines its truth value as a function of the truth values of its components

T(A AND B) = min(T(A), T(B))

T(A OR B) = max(T(A), T(B))

T(-A) = 1 - T(A)