Linear Function Approximation ![](logo.gif)
A linear function approximator is a function y=f(x,w) that is linear
in the weights, though not necessarily linear in the input x:
y = w_1 * f_1(x) + w_2 * f_2(x) + ... + w_n * f_n(x)
where x, y, and w can be vectors,
the f_i() functions can be linear
or nonlinear, and w_i is the ith
element of the w vector. Examples of linear function approximators
include:
- Lookup table
There is a separate weight for each possible value of x.
There are only n possible values for x,
and f_i(x)=1
when x=i and f_i(x)=0 otherwise.
- Linear
The output is just the dot product of w and x.
The individual functions are just f_i(x)=x_i, where
x_i is the ith
element of vector x.
- Radial Basis Functions
Each f_i(x) function looks like a smooth bump.
Each f_i() function has a "center" location, and
f_i(x) is a monotonic function of the distance
from x to the center. The "distance" may be
Euclidean distance (circular bumps), or there may be
a diagonal covariance matrix (ellipsoidal bumps parallel to
the axes), or there may be a full covariance matrix (general
ellipsoidal bumps). To be a linear function approximator,
the bumps must not move or change shape.
- Wavelets
Each f_i(x) is a wavelet, typically the product of a
cosine and a Gaussian. This is particularly useful in
image applications, because the human visual system seems
to use similar functions.
- CMAC
Each f_i(x) function has a value of 1 inside of
k square regions
in input space, and 0 everywhere else. A hash function is used
to make sure that the k squares are randomly scattered. The
functions are chosen so that for any give x, there will be
exactly c different f_i(x) functions active, and
their square regions will be offset from one another slightly.
Because of the hash function, the CMAC has the nice property that
it makes good use of its weights even when all the training
examples are in one small region of input space which wasn't known
beforehand. One particularly interesting example of this is when
the input space is very high dimensional, but all training
examples come from a simple, low-dimensional manifold. For some
reason, people often implement CMACs with k=1, which
destroys this useful property. The hash function was originally
proposed to be reminiscent of random neuron wiring in the brain.
Linear function approximators have several nice properties. For
supervised learning, the weights can be found immediately
at the cost of a single matrix inversion, without any
gradient-descent or incremental learning. For
reinforcement learning,
the weights can be found at the cost of solving a single
linear program.
For incremental reinforcement learning algorithms there are also
a few useful properties. For a lookup table, almost all the
incremental algorithms are guaranteed to converge to optimality.
For other linear function approximators, TD(lambda) is guaranteed
to converge when doing on-policy training (transitions are trained
on with a frequency proportional to their frequency in the Markov
chain).
Unfortunately, very few other convergence results are true. TD(lambda)
can diverge for off-policy training. Q-learning can diverge even
with on-policy training. SARSA can oscillate wildly and periodically
forget everything useful it had learned so far. For incremental
algorithms, limiting the function approximator to linear function
approximators does not help convergence very much.
Fortunately there are ways to ensure that all these algorithms will
converge: use the the residual form of
each algorithm. In that case, they will converge for both linear
and nonlinear function approximators.
There are also results indicating that nonlinear function approximators
may be more powerful in general than linear function approximators for
learning high-dimensional functions. For example, if the target
function is fairly smooth (has little energy in the high requencies),
and the function approximator is nonlinear,
then it is known that the number of weights needed for a good fit
grows only polynomially with the dimensionality of the input.
This is true for such diverse function approximators as
sigmoidal neural networks and linear
combinations of sine waves. It may even be true for all of the
popular nonlinear function approximators. But it has been shown
that it is not true for any linear function approximator. This
result suggests that linear function approximators may be most
useful in cases where the input space is low dimensional, or where
the training examples all come from a low-dimensional manifold
in a high-dimensional space.
More Information
Back to Glossary Index