# CS 530 - Lecture 04

## Probabalistic Reasoning

Bernhard Firner

2026-02-03

---

## Review

* We talked about **execution monitoring** last class
  * Means paying attention to our original goal and our progress towards it
  * Also includes the feasibility of our planned actions
* We can break this monitoring into three types

---

## Action Monitoring

* Action monitoring is a simple checklist before executing an action
  * This is often how safety is implemented
* For example, TrailNet would stop moving if a person was detected in front of it

---

## Plan Monitoring

* This means that we reassess our plan during execution
* For example, we could a maneuver to avoid an obstacle, but if that obstacle moves our plan is out of date
  * This can be tricky; our agent needs to remember what caused it to begin an action

---

## Goal Monitoring

* This is similar to plan monitoring, but applies to a high-level goal
* Let's say you drop your friend off at the store and look for a parking spot
  * The lot is quite full, so you begin to circle
* If you see your friend exit the store, you can abandon the search for parking
  * Parking was a short-term plan, and it is no longer necessary

---

## TrailNet

* We spent some time looking at TrailNet
  * Autonomous drone software
* Wins:
  * Mixed different kinds of training data
  * Used multiple DNNs to achieve different goals

---

## Learned Components

* Learned components are fused by a controller into waypoint instructions
  * Trail following DNN
  * Object Detection DNN
  * Obstacle Detector

</div>

</div>

---

## Planning

* We can think of those components as "planners"
* Trail following replans at 30fps
  * Each plan is a new position to fly to, always at max speed
* Object detection plans to stop before hitting a person
  * This is action monitoring
* Obstacle detection executes a plan to fly around objects

---

## History

* None of the learned components have a history
* But the controller executes each plan using sensor feedback
  * Needs to execute without getting a new plan for 33ms

---

## Improvements

* The learned components are very separate from the controller
* Actions were "pure pursuit"
  * This is basically a greedy approach to control
  * This reactive approach leads to gain at high speeds, resulting in oscillations
* We'll cover control as its own topic later, but we can talk about pure pursuit

---

## Pure Pursuit

* Pure pursuit tends to overcompensate
* When it overshoots, our planner (the path DNN) steers the other way
* In a robotic agent, this is called **oversteering**

</div>

</div>

---

## Understeering

* You may be tempted to reduce the gain
  * Basically, multiply our steering rate by a smaller constant
  * e.g. if the DNN estimates we are 0.5 meters left, only steer 0.25
* Now we won't react to tight turns

</div>

</div>

---

## Problem and Solution

* Older platforms didn't have a problem
  * This only shows up because faster ML predications have enabled high-speed agents
* Obviously the "gain" of our controller depends upon other variables
  * our current speed
  * our current offset from a desired position
  * physics; for example, is the wind blow our agent to the left?

---

## Controlling High Speed Agents

* You can "tune" pure pursuit, but it is ultimately pointless
* So we need a better controller
  * But a better controller requires more from us
    * Higher fidelity plan
    * Better estimates of our agent's egomotion

---

## Why This Topic?

* AI agents are increasingly being used for real time systems
  * autonomous cars, industry 4.0, general robotics
* Early systems decomposed problem into modules
  * Simplifies problems, but costs performance
  * Now we need that performance back

---

## Goals

* We need techniques to estimate our current state
  * This is both for data collection and for our controller
* We need controllers that match fast replanning
  * DNNs are likely to remake or modify plans with every frame

---

## Probabilistic Reasoning

* Sensing our own state is difficult
  * Discrete samples of a continuous environment
* Let's start by estimating discrete states
  * Then we'll move on to estimates of continuous states
* Some agents operate in discrete space as well

---

## Discrete Means Markov

* Discrete, temporal observations usually mean Markov modelling
* We can use a Markov model to estimate our current state or our past states (filtering)
  * Run time usage vs usage during data collection
* We can also predict what should happen next
* Finally, we can learn a model of the environment

---

## Markov Models

* Consider a sequence of observations, $X_1,...,X_T$
  * $T$ is the last step in a chain
  * The probability of observing $X_T$ considers the entire pathway
  * $p(X_T) = p(X_1)\prod_{t=2}^{T}p(X_t|X_{t-1})$
* This is called a Markov Chain

---

## Modelling

* We don't want to create models so specific that they need an entire sequence
  * e.g. $X_{t=1}$ could be the first reading of 10 minute sensor log
  * How much impact does that have on the current state?
* So we'll ignore data outside of a window

---

## Time-Invariance

* Instead, we want to assume that $P(X_t|X_{t-1})$ is independent of how we got to $X_{t-1}$
  * Basically, we decide on a window size
  * If you know anything about LLMs, you recognize this same assumption
* We call this time-invariance, since we'll pretend it doesn't matter how we reached $X_{t-1}$

---

## Forward Probabilities

* Each observation, X, has some state
  * If the states are discrete, we can call the observations a vocabulary
  * And Markov models have often been used with text
* If we observe a sequence, we can multiply probabilities to estimate the next state

---

## Text Example

```python
#! /usr/bin/python3

import argparse
import itertools
import numpy as np
import string
import sys

if __name__ == "__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument(
        "path",
        type=str,
        help="Path to a text file.")
    parser.add_argument(
        "order",
        type=int,
        help="Number of past words to look at. 0 for unigrams.")
    parser.add_argument(
        "start",
        type=str,
        nargs='+',
        help="Starting words for the predictions. Should be > order-1")

args = parser.parse_args()

assert(args.order < len(args.start)+1)

try:
        with open(args.path, 'r', encoding='utf-8') as corpus:
            text = corpus.read()
    except FileNotFoundError:
        print(f"Error: The file '{args.path}' was not found.")
        sys.exit(1)

# Change everything to lowercase.
    # Count the end of sentences as their own tokens.
    text = text.lower().replace('\n', ' ').replace('.', ' .').replace('?', ' ?').replace('!', ' !')
    # Replace unknown characters with a space
    text = ''.join([c if (c.isalpha() or c in ['.', '?', '!']) else ' ' for c in text])
    words = text.split()

# Observations
    # We could initialize this to 0, but, depending upon the ngram length, some occurences may not occur at all
    ngram_chains = dict()

# Now loop through the words
    for i in range(args.order, len(words)):
        ngram = words[i-args.order:i+1]
        # Loop through the ngram chain and fill in any missing links
        cur_dict = ngram_chains
        for gram in ngram[:-1]:
            if gram not in cur_dict:
                cur_dict[gram] = dict()
            cur_dict = cur_dict[gram]
        if ngram[-1] not in cur_dict:
            cur_dict[ngram[-1]] = 0
        cur_dict[ngram[-1]] += 1

# Use the starting word to predict some sentences
    for sample in range(10):
        cur_sentence = [word for word in args.start]
        while cur_sentence[-1] not in ['.', '?', '!'] and len(cur_sentence) < 50:
            # Use the tokens from our sentence to fetch the next word probabilities
            tokens = cur_sentence[-args.order:]
            cur_dict = ngram_chains
            for token in tokens:
                cur_dict = cur_dict[token]
            possible_words = list(cur_dict.keys())
            frequencies = np.array(list(cur_dict.values()))

probabilities = frequencies/np.sum(frequencies)
            next_word = np.random.choice(possible_words, p=probabilities)
            cur_sentence.append(next_word)
        print(' '.join(cur_sentence))

```

---

## Forward Examples

<pre>
$ python3 04_markov_text.py ../../../References/books/PrideAndPrejudice_JaneAusten.txt 2 the people
the people who have often told her the next morning to anybody for more .
the people who suffer as i did not feel quite certain he is insinuating .
the people who lived by trade .
the people hereabouts know i have to say that i had myself endeavoured to forget all that she resents darcy s regard bingley had been continually fluctuating but never to mention .
the people who have often observed how very suddenly you all ?
the people who have often observed that resignation is never for many hours at home and the week preceding it was bestowed with a family ?
the people who have been strange if they can be no want of subject .
the people hereabouts know i hope consider me now .
the people who suffer as i entered the woods to which you must give way to such very superior society but i am very sensible but knew not what to think slightingly of anybody s reserve can be a most important aspect he protested that they were to make herself
the people hereabouts know i have frequently wished to discredit it entirely away .
</pre>

---

## Forward Examples

<pre>
$ python3 04_markov_text.py ../../../References/books/AnnaKarenina_LeoTolstoy.txt 3 the people who
the people who got in and out he was thinking as he stepped out into the crowd of gazing women who had succeeded in putting him in the surging crowd in the boxes and in the whole people a longing to help their brothers not in word but in deed
the people who seemed whirling by as they ran beside the train or your beau frère said anna though not quite on the same ground as he she added with a smile full of triumph and happiness shining in his eyes .
the people who are very pleasant if one accepts them for what they try to appear to be absorbed in other things besides his tooth .
the people who had not read the book filled with troubles falsehoods sorrow and evil flared up more brightly than ever before into this intricate affair and that he had been educated and had been expecting him all the bitterness of which he had been speaking to had gone away
the people who got in and out with spoils or in search of a purchaser .
the people who despised him .
the people who had not played .
the people who got in and out dropped down on the carpet and its little dress tucked up behind it was wonderfully charming .
the people who met him .
the people who got in and sat down to the required light weight but still he was glad of this appeal for tenderness .
</pre>

---

## Forward Examples

<pre>
$ python3 04_markov_text.py ../../../References/books/CalculusMadeEasy_SilvanusPThompson.tex 2 the variable
the variable then its fluxion was called dot x .
the variable then its fluxion was dppagesep .png begin answers iii pageref ex xi .
the variable term is of no more be the sum of the value of b ?
the variable term is .
the variable quantities in the shape of a sphere a cone whose volume is a maximum textit b after it has the meaning we found that there is neither maximum nor dpnote tn omitting line break in the value of the most difficult way .
the variable term to fall to dfrac x x x .
the variable term is textit the calculus has been integrated .
the variable then its fluxion was called dot x .
the variable term is .
the variable quantities in the breadth of it and equate to zero you feel at first but more and more examples for himself at every stage so as to form the result on pageref page ansex xiii for answers .
</pre>

---

## Usefulness

* Forward pass is not super useful right now
  * Can be used to predict multiple steps
  * Could assign a probability to a possible next observation 
  * Language models are basically Markov models shoved into a DNN and do a better job
* But Markov models do give us real probabilities

---

## Data

* A big focus of this class is data
  * How do we get data to train an AI agent?
  * How do we properly interpret ML outputs when deciding agent actions?
* Markov models, and other sequential techniques, are part of the solution

---

## Filtering

* Let's say we have an untrustworthy data source
  * Could be a sensor, could be a DNN object detector
* Neither a sensor, such as a radar, nor a DNN give real probabilities
* We can use a Markov model to assign actual probabilities to observations

---

## Example

* Let's say a sign detecting DNN has the following characteristics:
  * False positive rate of 0.01
  * False negative rate of 0.001
* Our agent should stop when we are greater than 99.99% certain we've seen a stop sign

---

## Example Continued

* $1 - 0.01^2 = 99.99\%$, so we wait for three frames with with a stop sign detected
  * Right?

<p class="fragment big" data-fragment-index="1">Wrong!</p>

---

## Correlation

* Mistakes may be correlated, so using raw failure rate is wrong
* With a Markov model, we can assign a false positive probability based upon the last several predictions
* We can then use real data to solve for probabilities
  * Even better, we can add something relevant, like speed, to the model
  * Why? Because faster speeds have less correlation between frames

---

## Detection Fixing Example

* Let's continue this stop sign example
* We run a sign detector on every frame to detect stop signs
  * We have some real-world statistics from a validation set
  * How can we improve our detection?

---

## Increased Evidence

* Let's say we had a sequence of detections like this: {false, false, false, true}
  * Without sequential logic, we would use the true positive rate of 0.99
  * But this discards structural information
* We should be using the sequence to determine probabilities

---

## Viterbi Algorithm

* The algorithm we want to use involves dynamic programming
  * Given the full sequence of observations, what are the highest probability states?
* Again, we have some data from a validation set:
  * P(false|no sign) = 0.99
  * P(true|no sign) = 0.01
  * P(false|sign) = 0.001
  * P(true|sign) = 0.999

---

## Emission Matrix

* Those probabilities can be put into a matrix to simplify things
* We'll call this $B$, the emission matrix
  * The top row corresponds to observations when there is no sign
  * The bottom row corresponds to observations when there is a sign

<p><math display="block" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>B</mi><mo>=</mo><mrow><mo stretchy="true" form="prefix">(</mo><mtable><mtr><mtd columnalign="center" style="text-align: center"><mn>0.99</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.01</mn></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mn>0.001</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.999</mn></mtd></mtr></mtable><mo stretchy="true" form="postfix">)</mo></mrow></mrow><annotation encoding="application/x-tex">B = 
  \begin{pmatrix}
    0.99 & 0.01\\
    0.001 & 0.999
  \end{pmatrix}</annotation></semantics></math></p>

---

## Transition Matrix

* We also need to know how likely a sign is to stick around
* It is useful at this point to represent the $P(X_t|X_{t-1})$ as a matrix
  * Called a `transition matrix`
  * $K\times K$, where $K$ is the number of possible states
  * $k=2$ for our sign detector

---

## Transition Matrix

* Let's say that signs stick around for around 10 frames per encounter
* And we go around 1000 frames between signs
* We'll call the transition matrix $A$
  * The top row corresponds to transitions when there is no sign
  * The bottom row corresponds to transitions when there is a sign

<p><math display="block" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>A</mi><mo>=</mo><mrow><mo stretchy="true" form="prefix">(</mo><mtable><mtr><mtd columnalign="center" style="text-align: center"><mn>0.999</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.001</mn></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mn>0.1</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.9</mn></mtd></mtr></mtable><mo stretchy="true" form="postfix">)</mo></mrow></mrow><annotation encoding="application/x-tex">A = 
  \begin{pmatrix}
    0.999 & 0.001\\
    0.1 & 0.9
  \end{pmatrix}</annotation></semantics></math></p>

---

## Observation Probabilities

* Let's simplify things by expanding the probabilities of our observations, given either state (sign or no sign)
  * For simplicity, let's call $O$ a matrix of observations

<p><math display="block" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo>=</mo><mrow><mo stretchy="true" form="prefix">(</mo><mtable><mtr><mtd columnalign="center" style="text-align: center"><mn>1</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0</mn></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mn>1</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0</mn></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mn>1</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0</mn></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mn>0</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>1</mn></mtd></mtr></mtable><mo stretchy="true" form="postfix">)</mo></mrow></mrow><annotation encoding="application/x-tex">O = 
  \begin{pmatrix}
    1 & 0\\
    1 & 0\\
    1 & 0\\
    0 & 1
  \end{pmatrix}</annotation></semantics></math></p>

---

## Observation Probabilities

* The top row corresponds to the observation probabilities given that there is no sign
* The bottom row corresponds to the observation probabilities given that there is a sign

<p><math display="block" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>B</mi><msup><mi>O</mi><mi>T</mi></msup><mo>=</mo><mrow><mo stretchy="true" form="prefix">(</mo><mtable><mtr><mtd columnalign="center" style="text-align: center"><mn>0.99</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.99</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.99</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.01</mn></mtd></mtr><mtr><mtd columnalign="center" style="text-align: center"><mn>0.001</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.001</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.001</mn></mtd><mtd columnalign="center" style="text-align: center"><mn>0.999</mn></mtd></mtr></mtable><mo stretchy="true" form="postfix">)</mo></mrow></mrow><annotation encoding="application/x-tex">BO^T = 
  \begin{pmatrix}
    0.99 & 0.99 & 0.99 & 0.01\\
    0.001 & 0.001 & 0.001 & 0.999
  \end{pmatrix}</annotation></semantics></math></p>

---

## Step By Step

* Let's go through this step by step
* Observation 1: false
  * Let's assume no prior bias about our initial state
* We begin with column 1 of $BO^T$

---

## Step 2

* {false, **false**, false, true}
* For no sign:
  * Either remained in no sign state from step 1 and observed no sign:
    * $0.999\times0.99\times0.99 = 0.979$
  * Or transitioned from sign in step 1 and observed no sign:
    * $0.001\times0.1\times0.99 = 0.000099$

---

## Step 2

* For sign:
  * Either transitioned from no sign in step 1 and observed no sign:
    * $0.99\times0.001\times0.001 = 0.00000099$
  * Or remained in sign state from step 1 and again observed no sign:
    * $0.001\times0.9\times0.001 = 0.0000009$

---

## Step 3

* {false, false, **false**, true}
* For no sign:
  * Either remained in no sign state from step 2 and observed no sign:
    * $0.979\times0.99\times0.99 = 0.96$
  * Or transitioned from sign in step 2 and observed no sign:
    * $0.00000099\times0.1\times0.99 = 0.$

---

## Step 3

* For sign:
  * Either transitioned from no sign in step 2 and observed no sign:
    * $0.979\times0.001\times0.001 = 0.00000009$
  * Or remained in sign state from step 2 and again observed no sign:
    * $0.00000099\times0.9\times0.001 = 0.$

---

## Step 4

* {false, false, false, **true**}
* For no sign:
  * Either remained in no sign state from step 2 and observed a sign:
    * $0.96\times0.99\times0.01 = 0.0095$
  * Or transitioned from sign in step 2 and observed a sign:
    * $0.00000009\times0.1\times0.01 = 0.$

---

## Step 4

* For sign:
  * Either transitioned from no sign in step 2 and observed a sign:
    * $0.96\times0.001\times0.999 = 0.000959$
  * Or remained in sign state from step 2 and again observed a sign:
    * $0.00000009\times0.9\times0.999 = 0.$

---

## Observation

* The transition matrix, along with past information, means that it is more likely we haven't yet seen a stop sign
  * If there were two observations in a row, the sign probability would get ahead of the no sign probability

---

## Details

* Probabilities will all eventually go to 0
  * So we would likely switch to log probabilities, turning multiplication into addition
* In practice, we would also choose a filtering window size

---

## Other Algorithms

* The Viterbi algorithm finds the most likely actual sequence given some observations
* The state itself is hidden, and is only correlated with the observation
  * So this is an example of a **Hidden Markov Model** (HMM)
* Once we recognize that, there are plenty of uses for HMMs

---

## Hidden Markov Models

* HMMs are useful for more than just fixing noisy data
* They give us a real probability estimates of the characteristics of a system
  * Meaning that we can estimate the transition and emission matrices
* We can also estimate steady states, giving us global statistics about a system

---

## Uses

* The most widely cited uses are for e-commerce
  * Predicting things about a customer from their browsing
  * Predicting how a website will be navigated
* But there are other uses
* We'll go into more detail on HMMs next time

<!--
* So let's talk about making good estimates of what is happening in a probabalistic setting
  * We'll start with discrete spaces and move on to continuous values
* Markov models
* Filtering and prediction
  * This could be applied to a sensor (e.g. radar detecting a car) or a DNN (YOLO detecting a person)
* Smoothing
  * Use forward-backward with YOLO to estimate if an object is actually present
  * This uses future information, so it is an offline algorithm
  * We could use fixed-lag smoothing to run online with a set delay
* Most likely sequence
  * Viterbi or Baum-Walsh
  * Discrete localization
  * Hidden of observations
    * Such as the state of a user of a website

"For 530: most likely sequences from markov models, section 14. Then kalman filters."
-->

---

## Evaluation Preferences

* (11) Don't change
* () Prefer to not work in a group
* (3) Hate exams
* (6) Excited to spend 20 hours on the project
* (1) Excited to spend 10 hours
* (1) Excited to spend a few hours with an LLM