A derived variable is a mapping between states to a set, usually the natural numbers. Remember, if we can, given a state and match it to a number and show a relation which would iterate the state and decrease the states’ number. We can show that the algorithm terminates.

For a matrix, for instance, like:

\begin{equation} \begin{bmatrix} a & b \\ c & d \end{bmatrix} \end{equation}

We wish to find the matrix’s determinant; we write it down as:

\begin{equation} \begin{vmatrix} a & b \\ c & d \end{vmatrix} \end{equation}

geometric interpretation of determinants

Geometrically, determinants are how matrices send a unit object after its mapping; i.e. how does it transform the area of a unit square.

determinants can be computed along any axes

You can pick any row or column as the “axes”, and expand the matrix along any direction

Computational memory of this type of model is fixed. In particular, the class of problems this type of automata solves (“languages it recognizes”) is called regular languages.

We want to explore the closure properties of regular languages (does combining regular languages result in regular languages)

constituents

A DFA is a five-tuple \(M = (Q, \Sigma, \delta, q_{0}, F)\).

• \(Q\): finite set of all states
• \(\Sigma\): the alphabet
• \(\delta: Q \times \Sigma \to Q\), the transition function
• \(q_0 \in Q\): the start state
• \(F \subseteq Q\): the accept states, which means we accept the input string we got if after processing the string we ended up at one of these states

requirements

if processing an input results in an accepting state, we accept the input; otherwise, we reject the input. this is the computation.

key idea: let’s build a tree such that, after taking the action, the observation is deterministic. Therefore, you get a belief tree with no branching on observations.

DESPOT trees

We make an assumption, that the actual observation given are fixed given belief. That is:

\begin{equation} O(o|b,a) = 1 \end{equation}

for some specific \(o\), everything else is \(0\) for every b,a.

Sample Scenarios

To make such a tree, let’s sample of set of scenarios: sequences of actions and observations (because, given a belief and action, we assume observation is fixed. So, given an initial belief and an action, you will always go down a single “scenario”).

A health concern relating to glucose and obesity.