Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).

16.2 Functions, Factors and Arrays

Many of the algorithms in this book manipulate representations of functions. We extend the standard definition of function on sets to include functions on (sets of) 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∈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 C and Java (but these languages only allow for the case where S is the set of integers {0,...,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∈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(X1,X2,...,Xn) is a function such that given a value v1 for X1, a value v2 for X2, ..., and a value vn for Xn 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(X1=v1,X2=v2,...,Xn=vn). The set of variables, X1,X2,...,Xn is called the scope of f. The array f[X1,X2,...,Xn] is a function on X1,X2,...,Xn 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 X1,X2,...,Xn, then f(X1=v1) is a function of X2,...,Xn, such that

(f(X1=v1))(X2=v2,...,Xn=vn)=f(X1=v1,X2=v2,...,Xn=vn)

Factors can be added, multiplied or composed with any other operation level on the elements. If f1 and f2 is a factor, then f1+f2 is a factor with scope the union of the scopes of f1 and f2, defined pointwise:

(f1+f2)(X1=v1,X2=v2,...,Xn=vn)
= f1(X1=v1,X2=v2,...,Xn=vn) + f2(X1=v1,X2=v2,...,Xn=vn)

where we assume that f1 and f2 ignore variables not in their scope. Multiplication and other binary operators work similarly.

Example 16.1: Suppose f1(X,Y)=X+Y and f2(Y,Z)=Y+Z. Then f1+f2 is X+2Y+Z, which is a function of X, Y and Z. Similarly f1×f2=(X+Y)×(Y+Z).

f1(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 f3(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

f3+f1 is a function on W,X,Y, such that, for example,

(f3+f1)(W=1,X=2,Y=3) = 3+5=8

Similarly, (f3×f1)(W=1,X=2,Y=3) = 3×5=15.

Other operations on factors are defined in the book.