Intelligence 3E

foundations of computational agents

Many of the algorithms in this book manipulate representations of functions. We extend the standard definition of functions on sets to include functions on variables. A factor is a representation of a function. An array is an explicit representation of a function that can have its individual components modified.

If $S$ is a set, we write $f(S)$ to be a function, with domain $S$. Thus, if $c\in S$, then $f(c)$ is a value in the range of $f$. $f[S]$ is like $f(S)$, but individual components can be updated. This notation is based on that of Python, C, and Java (but C and Java only allow $S$ to be the set of integers $\{0,\mathrm{\dots},n-1\}$ for arrays of size $n$). Thus $f[c]$ is a value in the range of $f$. If $f[c]$ is assigned a new value, it will return that new value.

This notation can be extended to (algebraic) variables. If $X$ is an algebraic variable with domain $D$, then $f(X)$ is a function that given a value $x\in D$, returns a value in the range of $f$. This value is often written as $f(X=x)$ or simply as $f(x)$. Similarly, $f[X]$ is an array indexed by $X$, that is, it is a function of $X$ whose components can be modified.

This notation can also be extended to set of variables. $f({X}_{1},{X}_{2},\mathrm{\dots},{X}_{n})$ is a function such that given a value ${v}_{1}$ for ${X}_{1}$, a value ${v}_{2}$ for ${X}_{2}$, …, and a value ${v}_{n}$ for ${X}_{n}$, returns a value in the range of $f$. Note that it is the name of the variable that is important, not the position. This factor applied to the specific values is written as $f({X}_{1}={v}_{1},{X}_{2}={v}_{2},\mathrm{\dots},{X}_{n}={v}_{n})$. The set of variables, ${X}_{1},{X}_{2},\mathrm{\dots},{X}_{n}$ is called the scope of $f$. The array $f[{X}_{1},{X}_{2},\mathrm{\dots},{X}_{n}]$ is a function on ${X}_{1},{X}_{2},\mathrm{\dots},{X}_{n}$ where the values can be updated.

Assigning just some of the variables gives a function on the remaining variables. Thus, for example, if $f$ is a function with scope ${X}_{1},{X}_{2},\mathrm{\dots},{X}_{n}$, then $f({X}_{1}={v}_{1})$ is a function of ${X}_{2},\mathrm{\dots},{X}_{n}$, such that

$$(f({X}_{1}={v}_{1}))({X}_{2}={v}_{2},\mathrm{\dots},{X}_{n}={v}_{n})=f({X}_{1}={v}_{1},{X}_{2}={v}_{2},\mathrm{\dots},{X}_{n}={v}_{n}).$$ |

Factors can be added, multiplied, or composed with any other operation level on the elements. If ${f}_{1}$ and ${f}_{2}$ are factors, then ${f}_{1}+{f}_{2}$ is a factor with scope the union of the scopes of ${f}_{1}$ and ${f}_{2}$, defined point-wise:

$({f}_{1}+{f}_{2})({X}_{1}={v}_{1},{X}_{2}={v}_{2},\mathrm{\dots},{X}_{n}={v}_{n})$ | ||

$={f}_{1}({X}_{1}={v}_{1},{X}_{2}={v}_{2},\mathrm{\dots},{X}_{n}={v}_{n})+{f}_{2}({X}_{1}={v}_{1},{X}_{2}={v}_{2},\mathrm{\dots},{X}_{n}={v}_{n})$ |

where we assume that ${f}_{1}$ and ${f}_{2}$ ignore variables not in their scope. Multiplication and other binary operators work similarly.

Suppose ${f}_{1}(X,Y)=X+Y$ and ${f}_{2}(Y,Z)=Y+Z$. Then ${f}_{1}+{f}_{2}$ is $X+2Y+Z$, which is a function of $X$, $Y$, and $Z$. Similarly, ${f}_{1}\times {f}_{2}=(X+Y)\times (Y+Z)$.

${f}_{1}(X=2)$ is a function of $Y$, defined by $2+Y$.

Suppose that variable $W$ has domain $\{0,1\}$ and $X$ has domain $\{1,2\}$, the factor ${f}_{3}(W,X)$ can be defined by a table such as

$W$ | $X$ | Value |
---|---|---|

0 | 1 | 2 |

0 | 2 | 1 |

1 | 1 | 0 |

1 | 2 | 3 |

${f}_{3}+{f}_{1}$ is a function on $W$, $X$, and $Y$ such that, for example

$$({f}_{3}+{f}_{1})(W=1,X=2,Y=3)=3+5=8.$$ |

Similarly, $({f}_{3}\times {f}_{1})(W=1,X=2,Y=3)=3\times 5=15$.

Other operations on factors are defined in the book.