AI Planning, Bayes’ Rule, and Machine Learning Concepts

Posted on Apr 2, 2025 in Naval Architecture

Planning involves finding an action sequence that, when executed in the initial state, leads to a goal state. The challenge lies in creating a language expressive enough for diverse problems yet restrictive enough for efficient algorithms.

Representation of States and Goals

Planners decompose the world into logical conditions, representing a state as a conjunction of positive literals. The closed-world assumption dictates that unmentioned conditions are false.

A goal is a partially specified state, represented as a conjunction of positive ground literals (e.g., Rich and Famous). A propositional state s satisfies a goal g if s contains all atoms in g.

Representation of Actions

An action is defined by its preconditions (what must be true before execution) and effects (what happens after execution).

This is an action schema, representing multiple actions derived by instantiating variables. An action schema includes:

Action name and parameter list (e.g., Fly(p, from, to)).
Precondition: A conjunction of function-free positive literals that must be true before execution. Variables must appear in the parameter list.
Effect: A conjunction of function-free literals describing state changes. Positive literal P becomes true; negative literal ¬P becomes false. Variables must appear in the parameter list.

Forward State-Space Search (Progression Planning)

This approach starts from the initial state and explores action sequences until a goal state is reached. The formulation as a state-space search problem is as follows:

Initial state: The initial state of the planning problem (a set of positive ground literals).
Goal test: Checks if the state satisfies the goal.
Actions: Applicable actions are those whose preconditions are satisfied. The successor state is generated by adding positive effect literals and deleting negative effect literals.
Step cost: Typically 1 for each action.

Backward State-Space Search

This search starts with the goal state and computes parent states by regressing actions. Given a goal description g and an action a, the regression from g over a is g’ = (g – ADD(a)) ∪ PRECOND(a).

The regression represents:

Effects that don’t need to be true because they were added.
Conditions that must be true because they are preconditions.

Irrelevant actions are less of an issue, but regression yields a set of states, making heuristics development challenging.

Bayes’ Rule and Its Use

Bayes’ rule (or Bayes’ theorem) underlies modern AI systems for probabilistic inference. Bayes’ theorem gives you the actual probability of an event given the measured test probabilities. For example:

Correct for measurement errors by using real probabilities and the chance of false positives/negatives.
Construct computational models of oil reservoirs given observed data.

Bayes’ rule is useful for answering probabilistic queries conditioned on evidence, such as medical diagnosis.

The Semantics of Bayesian Networks

A Bayesian network is a directed graph with nodes annotated with quantitative probability information:

Nodes represent random variables (discrete or continuous).
Directed links connect pairs of nodes; X is a parent of Y if there’s an arrow from X to Y.
Each node X has a conditional probability distribution P(X | Parents(X)).
The graph is a directed, acyclic graph (DAG).

The network’s topology specifies conditional independence relationships. An arrow typically indicates that X directly influences Y.

Inference in Temporal Models

Basic inference tasks in temporal models include:

Filtering/Monitoring: Computing the belief state (posterior distribution over the current state), given all evidence to date: P(Xt | e1:t).
Prediction: Computing the posterior distribution over the future state: P(X _t+k | e _1:t) for some k > 0.
Smoothing (Hindsight): Computing the posterior distribution over a past state, given all evidence up to the present: P(X _k | e _1:t) for some k such that 0 < k ≤ t.

Hidden Markov Models (HMM)

A hidden Markov model (HMM) is a statistical Markov model where the system is assumed to be a Markov process with unobserved (hidden) states. It’s the simplest dynamic Bayesian network.

Unlike simpler Markov models, the state isn’t directly visible; only output dependent on the state is visible. Each state has a probability distribution over possible output tokens. The sequence of tokens provides information about the sequence of states.

HMMs are generalizations of mixture models where hidden variables are related through a Markov process. They are used in temporal pattern recognition, such as speech, handwriting, gesture recognition, part-of-speech tagging, and bioinformatics.

Machine Learning: Forms of Learning

The design of a learning element is affected by:

Which components of the performance element are to be learned.
What feedback is available.
What representation is used.

Agent components that can be learned include:

Direct mapping from conditions to actions.
Means to infer world properties from percept sequences.
Information about world evolution and action results.
Utility information indicating state desirability.
Action-value information indicating action desirability.
Goals describing states that maximize utility.

Types of feedback determine the learning problem: supervised, unsupervised, and reinforcement learning.

Supervised learning: Learning a function from input-output examples.
Unsupervised learning: Learning patterns in the input without specific output values.
Reinforcement learning: Learning from reinforcement.

Machine Learning: Inductive Learning

Inductive learning involves recovering an unknown function from examples. An example is a pair (x, f(x)), where x is the input and f(x) is the output.

The task of pure inductive inference (or induction) is to return a function h that approximates f, called a hypothesis. A good hypothesis will generalize well, predicting unseen examples correctly.

Simplified model of real learning:

Ignores prior knowledge.
Assumes a deterministic, observable environment.
Assumes examples are given.
Assumes the agent wants to learn f.

Machine Learning: Learning Decision Trees Algorithm

A decision tree takes an object described by attributes and returns a decision. Input attributes can be discrete or continuous. The output value can also be discrete (classification) or continuous (regression). The tree performs a sequence of tests, with internal nodes corresponding to attribute tests and branches labeled with possible values. Leaf nodes specify the value to be returned.

Statistical Learning Methods: Naive Bayes Models

Naive Bayes methods are supervised learning algorithms based on Bayes’ theorem with the “naive” assumption of independence between features. Given a class variable y and a feature vector x₁, …, x_n, Bayes’ theorem states:

P(y| x_{1, ……}x_n) = ((P(y)P(x_1,…..x_n|y))\ P(x_{1, ……}x_n))

Since P( x_{1, ……}x_n) is constant, the classification rule is:

Maximum A Posteriori (MAP) estimation is used to estimate P(y) and P(x_i|y); the former is the relative frequency of class y in the training set.

Different naive Bayes classifiers differ in their assumptions about the distribution of P(x_i|y).

Single-Layer Feed-Forward Neural Networks (Perceptrons)

A network with inputs connected directly to outputs is a single-layer neural network or perceptron network. Each output unit is independent, so each weight affects only one output. With a threshold activation function, the perceptron represents a Boolean function.

A perceptron can represent elementary Boolean functions (AND, OR, NOT) and some complex Boolean functions compactly.

Multilayer Feed-Forward Neural Networks

A multilayer feed-forward neural network consists of multiple adaptive layers without cycles from later to earlier layers. A network with a single complete hidden layer includes input nodes, output nodes, and hidden nodes. Each hidden node takes inputs from all input nodes and feeds into all output nodes.