Probability, MDPs & Decisions

Probability models (Chapter 13-15)

DTAgentProgram(belief_state)

[Figure 13.1] A decision-theoretic agent.

class ProbDist(var_name='?', freq=None)

Bases: object

A discrete probability distribution. You name the random variable in the constructor, then assign and query probability of values.

normalize()

Make sure the probabilities of all values sum to 1. Returns the normalized distribution. Raises a ZeroDivisionError if the sum of the values is 0.

show_approx(numfmt='{:.3g}')

Show the probabilities rounded and sorted by key, for the sake of portable doctests.

class JointProbDist(variables)

Bases: ProbDist

A discrete probability distribute over a set of variables.

values(var)

Return the set of possible values for a variable.

event_values(event, variables)

Return a tuple of the values of variables in event.

enumerate_joint_ask(X, e, P)

[Section 13.3] Return a probability distribution over the values of the variable X, given the {var:val} observations e, in the JointProbDist P.

enumerate_joint(variables, e, P)

Return the sum of those entries in P consistent with e, provided variables is P’s remaining variables (the ones not in e).

is_independent(variables, P)

Return whether a list of variables are independent given their distribution P P is an instance of JoinProbDist

gen_possible_events(vars, P)

Generate all possible events of a collection of vars according to distribution of P

class BayesNet(node_specs=None)

Bases: object

Bayesian network containing only boolean-variable nodes.

add(node_spec)

Add a node to the net. Its parents must already be in the net, and its variable must not.

variable_node(var)

Return the node for the variable named var.

variable_values(var)

Return the domain of var.

class DecisionNetwork(action, infer)

Bases: BayesNet

An abstract class for a decision network as a wrapper for a BayesNet. Represents an agent’s current state, its possible actions, reachable states and utilities of those states.

best_action()

Return the best action in the network

get_utility(action, state)

Return the utility for a particular action and state in the network

get_expected_utility(action, evidence)

Compute the expected utility given an action and evidence

class InformationGatheringAgent(decnet, infer, initial_evidence=None)

Bases: Agent

[Figure 16.9] A simple information gathering agent. The agent works by repeatedly selecting the observation with the highest information value, until the cost of the next observation is greater than its expected benefit.

integrate_percept(percept)

Integrate the given percept into the decision network

execute(percept)

Execute the information gathering algorithm

request(variable)

Return the value of the given random variable as the next percept

cost(var)

Return the cost of obtaining evidence through tests, consultants or questions

vpi_cost_ratio(variables)

Return the VPI to cost ratio for the given variables

vpi(variable)

Return VPI for a given variable

class BayesNode(X, parents, cpt)

Bases: object

A conditional probability distribution for a boolean variable, P(X | parents). Part of a BayesNet.

p(value, event)

Return the conditional probability P(X=value | parents=parent_values), where parent_values are the values of parents in event. (event must assign each parent a value.)

sample(event)

Sample from the distribution for this variable conditioned on event’s values for parent_variables. That is, return True/False at random according with the conditional probability given the parents.

class DiscreteBayesNode(X, parents, values, cpt)

Bases: object

A node of a discrete Bayesian network whose variable may take more than two values (unlike BayesNode, which is boolean).

values is the variable’s domain. cpt maps each tuple of parent values (ordered as in parents) to the probabilities over values – either a sequence in domain order or a {value: prob} dict. A root node uses the empty tuple () as its only key.

p(value, event)

Return P(X = value | parents = their values in event).

class DiscreteBayesNet(node_specs=None)

Bases: object

A Bayesian network of DiscreteBayesNodes (variables with arbitrary finite domains). Exact inference works through the generic enumeration_ask() / elimination_ask(), which rely only on node.p and variable_values and so work unchanged for multi-valued nodes.

add(node_spec)

Add a DiscreteBayesNode (or a (name, parents, values, cpt) spec); its parents must already be in the net and its variable must not.

variable_node(var)

variable_values(var)

Return the domain of var.

read_bif(source)

Parse a Bayesian network in BIF (Bayesian Interchange Format) into a DiscreteBayesNet. source is the BIF text or an open file object.

BIF is the format used by the Bayesian Network Repository (https://www.bnlearn.com/bnrepository/), so this lets aima load standard multi-valued networks such as the car-insurance (“Insurance”) model.

insurance()

Return the car-insurance (“Insurance”) Bayesian network as a DiscreteBayesNet, loaded from aima-data/insurance.bif.

This is the 27-variable discrete model of Binder, Koller, Russell & Kanazawa (1997) referenced by the AIMA 4e car-insurance case study (Section 16); the book notes the discrete conditional distributions are provided in the code repository, and this is them.

gaussian_probability(param, event, value)

Gaussian probability of a continuous Bayesian network node on condition of certain event and the parameters determined by the event

Parameters:

• param – parameters determined by discrete parent events of current node

• event – a dict, continuous event of current node, the values are used as parameters in calculating distribution

• value – float, the value of current continuous node

Returns:

float, the calculated probability

logistic_probability(param, event, value)

Logistic probability of a discrete node in Bayesian network with continuous parents, :param param: a dict, parameters determined by discrete parents of current node :param event: a dict, names and values of continuous parent variables of current node :param value: boolean, True or False :return: int, probability

class ContinuousBayesNode(name, d_parents, c_parents, parameters, type)

Bases: object

A Bayesian network node with continuous distribution or with continuous distributed parents

continuous_p(value, c_event, d_event)

Probability given the value of current node and its parents :param c_event: event of continuous nodes :param d_event: event of discrete nodes

enumeration_ask(X, e, bn)

[Figure 14.9] Return the conditional probability distribution of variable X given evidence e, from BayesNet bn.

enumerate_all(variables, e, bn)

Return the sum of those entries in P(variables | e{others}) consistent with e, where P is the joint distribution represented by bn, and e{others} means e restricted to bn’s other variables (the ones other than variables). Parents must precede children in variables.

elimination_ask(X, e, bn)

[Figure 14.11] Compute bn’s P(X|e) by variable elimination.

is_hidden(var, X, e)

Is var a hidden variable when querying P(X|e)?

make_factor(var, e, bn)

Return the factor for var in bn’s joint distribution given e. That is, bn’s full joint distribution, projected to accord with e, is the pointwise product of these factors for bn’s variables.

pointwise_product(factors, bn)

Multiply a sequence of factors together into a single factor over the union of their variables, using the Bayes net bn to enumerate variable values.

sum_out(var, factors, bn)

Eliminate var from all factors by summing over its values.

class Factor(variables, cpt)

Bases: object

A factor in a joint distribution.

pointwise_product(other, bn)

Multiply two factors, combining their variables.

sum_out(var, bn)

Make a factor eliminating var by summing over its values.

normalize()

Return my probabilities; must be down to one variable.

p(e)

Look up my value tabulated for e.

all_events(variables, bn, e)

Yield every way of extending e with values for all variables.

prior_sample(bn)

[Figure 14.13] Randomly sample from bn’s full joint distribution. The result is a {variable: value} dict.

rejection_sampling(X, e, bn, N=10000)

[Figure 14.14] Estimate the probability distribution of variable X given evidence e in BayesNet bn, using N samples. Raises a ZeroDivisionError if all the N samples are rejected, i.e., inconsistent with e.

consistent_with(event, evidence)

Is event consistent with the given evidence?

likelihood_weighting(X, e, bn, N=10000)

[Figure 14.15] Estimate the probability distribution of variable X given evidence e in BayesNet bn.

weighted_sample(bn, e)

Sample an event from bn that’s consistent with the evidence e; return the event and its weight, the likelihood that the event accords to the evidence.

gibbs_ask(X, e, bn, N=1000)

[Figure 14.16] Approximate P(X | e) by Gibbs sampling: from a random state consistent with the evidence, repeatedly resample each nonevidence variable from its Markov blanket and tally how often X takes each value.

markov_blanket_sample(X, e, bn)

Return a sample from P(X | mb) where mb denotes that the variables in the Markov blanket of X take their values from event e (which must assign a value to each). The Markov blanket of X is X’s parents, children, and children’s parents.

class HiddenMarkovModel(transition_model, sensor_model, prior=None)

Bases: object

A Hidden markov model which takes Transition model and Sensor model as inputs

sensor_dist(ev)

Return the sensor (observation) distribution corresponding to the evidence ev: the first row of the sensor model when ev is True, otherwise the second.

forward(HMM, fv, ev)

Perform one forward (filtering) step of an HMM: project the forward message fv through the transition model, weight it by the sensor distribution for evidence ev, and return the normalized next forward message. [Figure 15.4]

backward(HMM, b, ev)

Perform one backward step of an HMM: weight the backward message b by the sensor distribution for evidence ev and propagate it through the transition model, returning the normalized previous backward message. [Figure 15.4]

forward_backward(HMM, ev)

[Figure 15.4] Forward-Backward algorithm for smoothing. Computes posterior probabilities of a sequence of states given a sequence of observations.

viterbi(HMM, ev)

[Equation 15.11] Viterbi algorithm to find the most likely sequence. Computes the best path and the corresponding probabilities, given an HMM model and a sequence of observations.

baum_welch(HMM, observations, iterations=100)

[Section 20.3] Baum-Welch algorithm: the instance of EM that learns the parameters of a Hidden Markov Model (transition model, sensor model and prior) from a single sequence of boolean ‘observations’, starting from the initial guess in ‘HMM’. Each iteration runs a (scaled) forward-backward pass to compute the smoothed state marginals gamma_t(i) = P(X_t=i | e_1:T) and transition marginals xi_t(i,j) = P(X_t=i, X_t+1=j | e_1:T) (E-step), then re-estimates every parameter as the corresponding normalized expected count (M-step):

prior_i     = gamma_0(i)
A_ij        = sum_t xi_t(i, j) / sum_t gamma_t(i)
sensor_oi   = sum_{t: e_t = o} gamma_t(i) / sum_t gamma_t(i)

Returns a new HiddenMarkovModel with the learned parameters.

fixed_lag_smoothing(e_t, HMM, d, ev, t)

[Figure 15.6] Smoothing algorithm with a fixed time lag of ‘d’ steps. Computes the smoothed estimate P(X_{t-d} | e_{1:t}) for the slice that lies ‘d’ steps in the past, given the evidence sequence ev = [e_1, …, e_t]. Returns None when there is not yet enough evidence (t <= d).

particle_filtering(e, N, HMM)

Particle filtering considering two states variables.

class KalmanFilter(transition_model, sensor_model, transition_noise, sensor_noise)

Bases: object

[Section 15.4] Kalman filter for a linear-Gaussian dynamical system. The hidden state evolves and is observed according to the linear-Gaussian model

x_{t+1} = F x_t + noise, noise ~ N(0, Sigma_x) (transition model) z_t = H x_t + noise, noise ~ N(0, Sigma_z) (sensor model)

where F is the transition matrix, H the sensor matrix, Sigma_x the transition (process) noise covariance and Sigma_z the sensor (measurement) noise covariance. Because the family of Gaussians is closed under the Bayesian filtering update, the forward message stays Gaussian and is fully described by a mean vector and a covariance matrix at every step.

predict(mean, cov)

Time update: project the Gaussian estimate one step forward through F.

update(mean, cov, z)

Measurement update: condition the predicted Gaussian on observation z.

filter(mean, cov, z)

One predict-then-update cycle for a single new observation z.

kalman_filter(KF, mean0, cov0, observations)

[Section 15.4] Run the Kalman filter ‘KF’ over a sequence of ‘observations’, starting from the Gaussian prior N(mean0, cov0). Returns, for each time step, the filtered Gaussian estimate as a (mean, covariance) pair.

class DynamicBayesNet(prior, transition, sensors)

Bases: object

[Section 15.5] A dynamic Bayesian network for a stationary first-order Markov process. It is specified by a prior network over the state variables at slice 0 and a single transition + sensor network describing, for one time step, the distribution of each state variable (given the previous slice) and of each evidence variable (given the current slice). The DBN can be ‘unrolled’ into an ordinary BayesNet spanning any number of slices and then queried with the exact inference algorithms; in particular filtering is the query for the last state variable given the whole evidence sequence.

Each spec is a (variable, parents, cpt) triple as for a BayesNode. In a transition spec, a parent named ‘<var>_prev’ refers to state variable <var> at the previous slice; every other parent refers to the current slice.

unroll(steps)

Unroll the DBN into a BayesNet over slices 0..steps (evidence at 1..steps).

filter(evidence, query, infer=<function elimination_ask>)

Filtering: the posterior over ‘query’ at the last slice given the whole observation sequence. ‘evidence’ is a list of dicts, one per time step t = 1, 2, …, each mapping evidence variables to their observed values.

class MCLmap(m)

Bases: object

Map which provides probability distributions and sensor readings. Consists of discrete cells which are either an obstacle or empty

sample()

Returns a random kinematic state possible in the map

ray_cast(sensor_num, kin_state)

Returns distance to nearest obstacle or map boundary in the direction of sensor

monte_carlo_localization(a, z, N, P_motion_sample, P_sensor, m, S=None)

[Figure 25.9] Monte Carlo localization algorithm

class ContinuousMCLmap(width, height, obstacles=(), sensors=(0, 1.5707963267948966, 3.141592653589793, 4.71238898038469))

Bases: object

[Figure 25.10] A continuous 2-D map for Monte Carlo localization. The world is a rectangular arena [0, width] x [0, height] containing axis-aligned rectangular obstacles. A kinematic state is (x, y, heading) with x, y real-valued coordinates and heading an angle in radians, so the robot is no longer snapped to a grid. Range sensors cast rays from the robot to the nearest wall, returning continuous distances rather than the integer step counts of the discrete MCLmap. It exposes the same sample()/ray_cast(sensor_num, kin_state) interface as MCLmap, so it plugs straight into monte_carlo_localization.

in_free_space(x, y)

True if (x, y) lies inside the arena and outside every obstacle.

sample()

Return a random kinematic state (x, y, heading) in free space.

ray_cast(sensor_num, kin_state)

Distance from the robot to the nearest wall along the given sensor. Casts the ray (x, y) + t * (cos a, sin a), with a = heading + sensor offset, and returns the smallest positive intersection with any wall segment (infinity if the ray escapes the arena, which cannot happen for a robot inside a closed arena).

Markov Decision Processes (Chapter 17)

First we define an MDP, and the special case of a GridMDP, in which states are laid out in a 2-dimensional grid. We also represent a policy as a dictionary of {state: action} pairs, and a Utility function as a dictionary of {state: number} pairs. We then define the value_iteration and policy_iteration algorithms.

class MDP(init, actlist, terminals, transitions=None, reward=None, states=None, gamma=0.9)

Bases: object

A Markov Decision Process, defined by an initial state, transition model, and reward function. We also keep track of a gamma value, for use by algorithms. The transition model is represented somewhat differently from the text. Instead of P(s’ | s, a) being a probability number for each state/state/action triplet, we instead have T(s, a) return a list of (p, s’) pairs. We also keep track of the possible states, terminal states, and actions for each state. [Page 646]

R(state)

Return a numeric reward for this state.

T(state, action)

Transition model. From a state and an action, return a list of (probability, result-state) pairs.

actions(state)

Return a list of actions that can be performed in this state. By default, a fixed list of actions, except for terminal states. Override this method if you need to specialize by state.

get_states_from_transitions(transitions)

Return the set of all states mentioned in the transition model, both as source states and as reachable next states (or None if transitions is not a dict).

check_consistency()

Assert that the MDP is well formed: the states match those in the transitions, the initial and terminal states are valid, rewards are defined for every state, and each action’s outcome probabilities sum to 1.

class MDP2(init, actlist, terminals, transitions, reward=None, gamma=0.9)

Bases: MDP

Inherits from MDP. Handles terminal states, and transitions to and from terminal states better.

T(state, action)

Return a list of (probability, next-state) pairs for taking the action in the given state; a None action stays in place with probability 0.0.

class GridMDP(grid, terminals, init=(0, 0), gamma=0.9)

Bases: MDP

A two-dimensional grid MDP, as in [Figure 17.1]. All you have to do is specify the grid as a list of lists of rewards; use None for an obstacle (unreachable state). Also, you should specify the terminal states. An action is an (x, y) unit vector; e.g. (1, 0) means move east.

calculate_T(state, action)

Return the (probability, next-state) outcomes for the intended action: 0.8 of moving as intended and 0.1 each of veering to the right or left.

T(state, action)

Return the list of (probability, next-state) pairs for the action in the given state; a falsy action stays in place with probability 0.0.

go(state, direction)

Return the state that results from going in this direction.

to_grid(mapping)

Convert a mapping from (x, y) to v into a [[…, v, …]] grid.

to_arrows(policy)

Render a policy as a grid of arrow characters (>, ^, <, v, with . for a None action) laid out to match the grid.

gen_grid(n_rows=3, n_cols=4, terminals=((3, 2), (3, 1)), main_reward=-0.04, terminal_rewards=(1, -1), block_coords=((1, 1),))

Generate a grid (list of lists of rewards) of arbitrary size in the format accepted by GridMDP, e.g. GridMDP(gen_grid(…), terminals=[…]). n_rows, n_cols: grid dimensions. terminals: (x, y) coordinates of the terminal cells. main_reward: reward for every non-terminal, non-blocked cell. terminal_rewards: reward for each cell in terminals (paired by position). block_coords: (x, y) coordinates of obstacles (set to None / unreachable).

q_value(mdp, s, a, U)

Return the Q-value of taking action a in state s given the utility estimates U, i.e. the expected sum of the immediate reward and the discounted utility of the successor states. With no action it falls back to the reward of s.

value_iteration(mdp, epsilon=0.001)

Solving an MDP by value iteration. [Figure 17.4]

best_policy(mdp, U)

Given an MDP and a utility function U, determine the best policy, as a mapping from state to action. [Equation 17.4]

expected_utility(a, s, U, mdp)

The expected utility of doing a in state s, according to the MDP and U.

policy_iteration(mdp)

Solve an MDP by policy iteration [Figure 17.7]

policy_evaluation(pi, U, mdp, k=20)

Return an updated utility mapping U from each state in the MDP to its utility, using an approximation (modified policy iteration).

class POMDP(actions, transitions=None, evidences=None, rewards=None, states=None, gamma=0.95)

Bases: MDP

A Partially Observable Markov Decision Process, defined by a transition model P(s’|s,a), actions A(s), a reward function R(s), and a sensor model P(e|s). We also keep track of a gamma value, for use by algorithms. The transition and the sensor models are defined as matrices. We also keep track of the possible states and actions for each state. [Page 659].

remove_dominated_plans(input_values)

Remove dominated plans. This method finds all the lines contributing to the upper surface and removes those which don’t.

remove_dominated_plans_fast(input_values)

Remove dominated plans using approximations. Resamples the upper boundary at intervals of 100 and finds the maximum values at these points.

generate_mapping(best, input_values)

Generate mappings after removing dominated plans

max_difference(U1, U2)

Find maximum difference between two utility mappings

class Matrix

Bases: object

Matrix operations class

static add(A, B)

Add two matrices A and B

static scalar_multiply(a, B)

Multiply scalar a to matrix B

static multiply(A, B)

Multiply two matrices A and B element-wise

static matmul(A, B)

Inner-product of two matrices

static transpose(A)

Transpose a matrix

pomdp_value_iteration(pomdp, epsilon=0.1)

Solving a POMDP by value iteration.

update_belief(pomdp, belief, action, observation)

[Equation 17.17] POMDP filtering: update the belief state (a probability distribution over the states) after executing ‘action’ and perceiving ‘observation’. The prediction step propagates the belief through the transition model and the update step weights it by the sensor model, then renormalizes:

b'(s') = alpha * P(o | s') * sum_s P(s' | s, a) b(s)

pomdp_lookahead(pomdp, belief, depth)

[Section 17.5 - Dynamic Decision Networks] Online decision making for a POMDP modeled as a dynamic decision network (DDN): the network is projected ‘depth’ steps into the future and solved by belief-state expectimax search. Decision nodes range over the belief states and chance nodes branch over the possible observations, with the belief updated by POMDP filtering ([Equation 17.17]) along each branch. Returns the action that maximizes the expected discounted utility from ‘belief’.

Making Simple Decisions (Chapter 15/16)

The decision-theoretic algorithms — decision networks and the information-gathering agent — are implemented in aima.probability, alongside the Bayesian-network machinery they build on. They are re-exported here under the chapter’s name; aima.probability is their canonical home.

class DecisionNetwork(action, infer)

Bases: BayesNet

An abstract class for a decision network as a wrapper for a BayesNet. Represents an agent’s current state, its possible actions, reachable states and utilities of those states.

best_action()

Return the best action in the network

get_utility(action, state)

Return the utility for a particular action and state in the network

get_expected_utility(action, evidence)

Compute the expected utility given an action and evidence

class InformationGatheringAgent(decnet, infer, initial_evidence=None)

Bases: Agent

[Figure 16.9] A simple information gathering agent. The agent works by repeatedly selecting the observation with the highest information value, until the cost of the next observation is greater than its expected benefit.

integrate_percept(percept)

Integrate the given percept into the decision network

execute(percept)

Execute the information gathering algorithm

request(variable)

Return the value of the given random variable as the next percept

cost(var)

Return the cost of obtaining evidence through tests, consultants or questions

vpi_cost_ratio(variables)

Return the VPI to cost ratio for the given variables

vpi(variable)

Return VPI for a given variable