Reasoning Techniques - Dke

Front 1

Problem Types :

deterministic, fully observable

Back 1

single-state problem

agent knows the state and what do outcomes are, solution is a sequence

Front 2

Problem Types :

Deterministic, non-observable

Back 2

conformant problem

agent does not know where he is, solution (if it exists) is a sequence

Front 3

Problem Types :

Nondeterministic and/or partially observable

Back 3

contingency problem

gain more information through percepts, solution is tree or policy

Front 4

Unknown state space

Back 4

exploration problem

online learning

Front 5

Single-state problem formulation (components)

Back 5

state (initial state)

actions

goal-test

path cost definition

Front 6

State vs node

Back 6

state is representation of physical space

node is data strcture with parent, child, depth, path-cost

Front 7

fringe - tree search

Back 7

the list of currently open nodes, where an open node is one that has been reached, but not fully analysed

FIFO for BFS, LIFO for DFS

Front 8

Size of Graph

Back 8

b - maximum branching factor of the tree

d - depth of the least-cost solution

m - max-depth of the state space

Front 9

BFS

Back 9

Fifo fringe

complete if b is finite

time.complex: O(B^(d+1))

space.complex: O(b^(d+1))

optimal: yes, not generally

Front 10

Uniform-cost search

Back 10

fringe = ordered by path cost

complete if step cost >= e

time: O(b^(C/e)) where e is epsilon, C is the cost of optimal solution

space: O(b^(C/e))

optimal: yes - nodes are expanded in increasing order of path-cost

Front 11

DFS

Back 11

fringe = LIFO

complete: finite only

time: O(b^m), but practical in certain cases

space: O(bm)

optimal: no if prematurely terminated

Front 12

iterative deepending / depth limited

Back 12

limit to certain depth (DFS until there)

increase depth iteratively

complete: yes

time: O(b^d)

space: O(bd)

optimal: yes for step cost = 1

Front 13

Repeated state

Back 13

Trees fail exponentially

use graph search

Front 14

Best First search

Back 14

tree search, but with a strategy concerning expansion of nodes

rate nodes according to desirability

Front 15

Greedy search

Back 15

uses evaluation function h(n) as estimated cost from n to goal

complete: only with repeated-state checking

time: O(b^m) but heuristic can improve

space: O(b^m) - stores all nodes

optimal: no

Front 16

A* search

Back 16

avoids already expensive paths

f(n) = g(n) + h(n)

g(n) is cost so far, h(n) estimated cost

h(n) <= true cost, admissibility

A* is optimal

Front 17

A* optimality proof

Back 17

optimal, because for any suboptimal goal, f(n) is accurate

Then the final goal will have smaller cost than suboptimal, but since h is admissible, f(suboptimal) >= f(node on optimal path)

then suboptimal goal will never be expanded

A* is optimistic, so when least-cost solution is found, optimistic estimates could only be worse

Front 18

A* performance

Back 18

complete: yes unless infinitely smaller than goal

time: exponential in (rel.error of h x length of solution)

space: all nodes

optimal: yes

Front 19

Dominance of evaluation functions

Back 19

if a function h(n) dominates h2(n),

then for all n h(n) >= h2(n)

dominating functions preferred for search

Front 20

Iterative improvement algorithms

Back 20

path is irrelevant, goal state is solution

keep only current state, and improve it (instance based)

Front 21

Hill-climbing

Back 21

neighbour is highest value successor of currentNode

if neighbour is better than currentNode, then replace

Front 22

Simulated Annealing

Back 22

escaping local minima/maxima

time-temperature mapping

replace currentNode by Neighbour not only if bette,r but also when the probability of T allows

e^(D/T) where T is the time and D is the delta between neighbour and currentNode

Front 23

CSP (def)

Back 23

state is defined by variables X with values from a domain D

goal test is a set of constraints specifying the allowable combinations of values for given variables

solution to CSP is assignment of values to variables that satisfy constraints

Front 24

Constraint Graph

Back 24

graph where all edges show certain constraints, nodes are the variables

Front 25

Types of constraints

Back 25

unary: certain variables must have or cannot have certain values

binary: certain variables must be equal to each other or different

high-order: 3 or more variables

preferences: some form of cost for certain assignments

Front 26

basic CSP solution (backtracking search)

Back 26

provide empty initial assignment

attempt to assign value to given selected variable with no conflict

- if no legal assignment exists, terminate unsuccessfully

backtracking: return result only if not failure, try all combinations if necessary

Front 27

Improving backtracking

Back 27

select variable to test which is most constrained, or selectively the variable which is most constraining on others

use the least constraining value, such that most possibilities are provided for other variables

forward checking to eliminate options which creates impossible options

propagation (separate card)

Front 28

improving backtracking - constraint propagation

Back 28

arc consistency:

for every value of x, there is some allowed y

check in both directions and all directions, eliminating options that are not possible because of arcs. Then re-check neighbours

Front 29

Tree structured CSP

Back 29

can be solved in O(n * d^2) time.

Select root, order variables from root to leaves such that parents come before the children in the ordering

remove inconsistencies from n to 2

then assign from 1 to n, whatever is consistent with parent

Front 30

Iterative algorithms for CSP

Back 30

typically work with complete states, but can be modified

allow states to have unsatisfied constraints, variables are reassigned by operators

assign value that has fewest constraints

Front 31

Minimax

Back 31

min and max players, utility at leaves of tree

complete: yes if finite solution

optimal: yes against optimal opponent

time: O(b^m) exact solution pretty infeasible

space: O(bm)

Front 32

Evaluation functions

Back 32

function (linear, polynomial) to predict desirability of a state given features

act as orderings, exact values don't matter

Front 33

Cut-off search

Back 33

limiting depth of prediction

4 ply chess is a typical noobie

Front 34

ply

Back 34

depth of search

Front 35

alpha-beta pruning

Back 35

prune what cannot be used

can reach O(b^(m/2)) - twice the depth

Front 36

non-deterministic games (probabilities)

Back 36

introduce an additional chance layer between min and max

value of chance node, is average of children

Front 37

pruning in non-deterministic trees

Back 37

not really effective, if in exam, just deal with it

Front 38

Knowledge bases agent

Back 38

agent is given knowledge

can then ask itself what actions to pursue

knowledge is independent of implementation

Front 39

Entailment

Back 39

one thing follows form another

KB entails a, then a is true if KB is true

Front 40

Models

Back 40

m is a model of sentence a, if a is true in m

M(a) is the set of all models of a

then KB entails a IFF M(KB) subset M(a)

Front 41

Inference i

Back 41

i is a procedure with which a can be derived from KB

Front 42

Soundness of an inference

Back 42

i is sound if

whenever a can be inferred from KB, it holds true that KB entails a

Front 43

Completeness of an inference

Back 43

i is complete if

whenever KB entails a, a can also be inferred from KB

Front 44

Horn Form

Back 44

conjunction of atomics in single implication or basic atomics

used for forward and backward chaining

Front 45

forward chaining

Back 45

fire any rules whose premises are satisfied in KB and add conclusion to KB until query q

Front 46

backward chaining

Back 46

prove query q:

check if q is known, otherwise prove by backward-chaining the premises of a rule which concludes q

avoid loops

Front 47

FC vs BC (chaining for horn-clauses)

Back 47

FC is data-driven, may do unnecessary work

BC is goal-driven - may be less than linear

Front 48

Conjunctive Normal Form

Back 48

conjunction of disjunctions (with negations allowed)

so an AND chaining of clauses which are internally OR chained, and may have NOTs

Required for Resolution

Front 49

Resolution inference rule

Back 49

rule in which there exists a TRUE and NOT in a combination of two clauses, they can both be removed and the remainders are the result

sound and complete for propositional logic

Front 50

Conversion steps to CNF (propositional)

Back 50

1. remove IFF with two IF inferences

2. eliminate a->b with NOT(a) OR (b)

3. move NOT inwards with Morgan's rule or double-negation

Front 51

Resolution algorithm

Back 51

add negation of provable desired item,

if contradiction then it must hold

Front 52

Basics of Logic

Back 52

Front 53

Truth for FOL

Back 53

based on a model and interpretation

model contains >=1 objects and their relations

Front 54

Universal Quantifier and FOL

Back 54

usually used with "->" implication, not with AND

true in model m IFF predicate/function holds for every x in the model

Front 55

Existential Quantifier FOL

Back 55

usually used with "AND" connective

true if in the model, there is an object to make it satisfy

Front 56

Situation calculus

Back 56

method of recording change in FOL

adds a situation argument to non-eternal predicates

Front 57

Universal Instantiation for FOL

Back 57

For all objects / ground-terms for variable v apply certain rule

Front 58

Existential Instantiation

Back 58

we replace the variable v with a new constant symbol, a Skolem Constant

hence the term Skolemize

Front 59

propositionalizing FOL KB

Back 59

removing Existential and Universal Claims, only inferences and predicates-with-objects remain

Front 60

Unification

Back 60

propositionalization creates many instantiations, too many

get inference more quickly if we find substitution that matches premises required directly

Front 61

Generalized Modus Ponens

Back 61

just like normal MP

used where exactly one positive literal exists

Front 62

Forward Chaining for FOL

Back 62

sound and complete for first-order definite clauses

matching rules to new literals is expensive - NP-hard

Front 63

backwards chaining for FOL

Back 63

space is linear

incomplete (loops), and inefficient due to repetitions

used for logic programming

Front 64

Conversion to CNF (FOL)

Back 64

1. eliminate biconditionals and implications

2. move negations inwards

3. standardize variables: use different variables

4. Skolemize: remove existential quantifiers with function

5. Drop universal quantifiers

6. distribute ANDs and ORs

Front 65

Search vs Planning (systems)

Back 65

Search fails with complex, sequential tasks

Front 66

Planning System (3 points)

Back 66

1. open action and goal representation for selection

2. divide and conquer by creating sub-goals

3. relax requirements for sequential construction of solutions

Front 67

Strips Operator

Back 67

action (with parameters)

pre-conditions: must be conjunction of positive literals only

post-conditions/effect: conjunction of literals (can be negative)

must show all changes states for post-conditions

Front 68

Partial Order Plan

Back 68

has start, finish, causal links and temporal ordering

causal link between post and preconditions, temporal between steps

complete if every precondition is achieved

Front 69

Properties of POP

Back 69

sound, complete and systematic

heuristics can be applied to it

Front 70

Product Rule for Probabilities

Back 70

P( a + b ) = P(a|b) P(b) - reduction from simple conditional formula

Front 71

Chain rule for Probabilities

Back 71

recursively using the product rule to break down a string of conjunctions into product of conditionals

Front 72

Normalization

Back 72

removing the denominator of conditional with a factor of the entire solution

Front 73

Conditional Independence

Back 73

when some of the "given" terms do not affect the conditional probability of the "query" term

Front 74

Unit-preference Resolution strategy

Back 74

only resolving two variables if the resulting variable has less literals

Front 75

Bayes Rule

Back 75

P(a|b) = P(b|a)P(a) / P(b)

or in other words: P(cause | effect) = P(certain effect with given cause) / P(effect regardless of cause)

Front 76

Bayesian Network

Back 76

acyclic graph, directed

conditional distribution for each node given its parents

Front 77

Conditional Probability Table (CPT)

Back 77

All possible combinations of outcomes of parents and the probability of current node given that set

Front 78

Compactness of CPT and Bayesian Network

Back 78

2^k rows for k parents

Entire network thus n * 2^k values

Front 79

full joint distribution

Back 79

all possible combinations of variables - inefficient

Bayesian network uses less (linear for n)

Front 80

Local Semantics (M. blanket)

Back 80

every node is conditionally independent of non-descendents given its parents

(only dependent on parents)

Markov's blanket: conditionally independent of all nodes given: parents, children, parents of children

Front 81

Constructing Bayesian Net

Back 81

Iteratively add all variables

for every variable, add as parents if conditional probability is affected by potential parent

prefer causal - simpler to construct

Front 82

Compacting the CPT

Back 82

Noisy-OR

Independent Failure Probability is stored

the probability of the negation is stored for the instance where only one of the parents is true. Then all other combinations can be computed

Front 83

Cases of Continuous variables

Back 83

1: continuous variable with discrete+cont. parents

2: discrete variable, continuous parent(s)

Front 84

Continuous child in Bayesian Network

Back 84

create conditional density function for every assignment of discrete parents using continuous parents' value

linear Gaussian

Front 85

Discrete variable (cont. parents) in Bayesian

Back 85

using probit (similar to sigmoid, but sigmoid has longer tails)

Front 86

Inference by enumeration

Back 86

Sum all according probabilities

Where conditional is expanded into the conjunction of all terms

Then summed over all hidden (or unnecessary variables)

time O(d^n) with n=variables, d=branching

Front 87

Inference by variable elimination

Back 87

Inferencing (improvement over by enumeration): storing intermediate results (factors) by summations from right-to-left

summing out: combine factors as function of given variable. Then summed out variables are combined and marked as summed

Front 88

Irrelevant variables in Bayesian

Back 88

can be removed, and irrelevant if not in ancestors or evidence

Front 89

moral graph of Bayes

Back 89

all parents are married and the graph is undirected

Front 90

Stochastic Simulation

Back 90

drawing n samples from distribution S

compute approx. posterior prob P'

show that P' converges to P

Front 91

Rejection sampling

Back 91

only samples where all evidence variables hold true are selected

for small many variables, P(e) is exponentially small

Front 92

Likelihood weighting

Back 92

every sample is weighted according to its likelihood to correspond to evidence

Evidence variables are fixed, and their probability multiplied, originally with w=1

Front 93

Constraints of Rational Preferences

Back 93

agent must obey the following for pref. of actions:

orderability: one must exist

transitivity: by def

continuity: continuous range that can be balanced for item

substitutability: can be balanced with parameter

monotonicity: can force preference with unequal parameter

Front 94

Maximising Expected Utility (MEU)

Back 94

U(A) >= U(B) IFF A >= B

choose action for which the expected utility is maximised

Front 95

Examples of Utility

Back 95

Russian roulette, micromorts (1:1M of dying)

money not so great - people are risk-averse

Front 96

Dominance of Utility

Back 96

strict dominance: for any multi-attribute, choice A is preferred over B (so utility is preferable)

stochastic dominance: if for every value of integral better, then it dominates (and for every attribute)

can be shown on arcs in "graph"

Front 97

Preference Independence

Back 97

x3 is independent of x1 and x2 (preferentially) IFF for all values of x1 and x2, x3 does not affect the preference

Front 98

Value of Information

Back 98

E(bestAction|info) - E(bestAction|no-info)

Front 99

Qualitative Behaviour of value of Information

Back 99

distinct utilities: information worth little

much overlap, spread wide: information worth much

much overlap: tight spread: information worth little (cannot indicate much)