Maximising a function
Consider the relationship between
AI search and the problem of
maximising a function.
The AI program constructs a "solution" x.
x may be multi-dimensional (e.g. an array of 10,000 numbers)
We can test the "fitness" of x which is f(x).
Find the x value that gives maximum fitness f(x).
Does the function have an equation?
Equation
If we have an equation for the function and it is differentiable:
-
Differentiate. Search for slope = 0.
This will give local max and min points if they exist
(if not infinite).
No equation
The interesting case is where no equation known / not differentiable
(but can still judge fitness of any given x).
-
Example of an Unknown or postulated function:
Input x = All the parameters that control a mobile robot.
Fitness f(x) = How well the robot played soccer.
Find x that maximises f(x).
General approach:
- Learn from exemplars (many samples of x and f(x)).
Build up a map of the function, ever increasing in accuracy and detail.
- If only interested in max fitness,
the map will end up in more detail in uplands (keep exploring)
than in lowlands (which we abandon).
Fitness function should not be chaotic
The idea of Maximising a function
from exemplars
is that "nearby" Input should generate
"nearby" Output.
But some functions defeat this idea.
With "chaotic" functions, a small change in input leads to massive changes in output.
These functions are hard or sometimes impossible to learn from exemplars.
Non-chaotic functions
We do
not expect in general
to be able to maximise a chaotic (or discontinuous) function from exemplars.
The global maximum must be surrounded by some continuous
zone of uplands,
otherwise how can we find it.
It cannot be a single, isolated point
or else the odds of finding that precise x go to zero.
Ancient Brain