next up previous contents
Next: Computational complexity Up: Evaluation of the algorithm Previous: Evaluation of the algorithm

Fixed point iteration of winning strengths

The preliminary winning strengths tex2html_wrap_inline1737 were defined by equation 3.7


We shall rewrite this


where tex2html_wrap_inline2015 and tex2html_wrap_inline2017 . This equation has to be solved numerically, since tex2html_wrap_inline1737 appear in both sides of the equation, and it is impossible to find the solution in a closed form. The computation only needs to be done for the neurons in the set of winners, and therefore n equals the number of winners.

Newton's method is often a good choice when one has to numerically solve equations. If we denote tex2html_wrap_inline2023 , then solving equation 4.1 is equivalent to finding the root of tex2html_wrap_inline2025 . Finding the root using Newton's method requires the computation of the inverse of the Jacobian matrix of tex2html_wrap_inline2025 , however. It is a n by n matrix, because both vectors tex2html_wrap_inline1919 and tex2html_wrap_inline1463 have n elements. In some cases it is possible to find an efficient way to compute the inverse of the Jacobian. This is possible, if the Jacobian is for example close to diagonal matrix. In our case the Jacobian is not at all close to diagonal matrix, and it does not seem to have any other properties which would allow us to compute the inverse efficiently.

We are going to solve the equation 4.1 by using another popular method: fixed point iteration. If we have an equation of the form x = f(x) we can try to find the solution simply by iterating x(t+1) = f(x(t)). This is the standard fixed point iteration. Suppose tex2html_wrap_inline2043 is a solution satisfying tex2html_wrap_inline2045 . The iteration converges to tex2html_wrap_inline2043 only if tex2html_wrap_inline2049 . Notice that if the derivative f' is negative, the value x(t) oscillates around the solution tex2html_wrap_inline2043 , and if the derivative is positive, the value x(t) changes monotonically. The closer the derivative is to zero the faster is the convergence.

It is also possible to speed up the convergence by modifying the iteration. Aitken extrapolation formula [Atkinson, 1989, page 86,] makes the assumption that the values x(t) form a geometric series if we use the standard fixed point iteration. This assumption is usually valid at least when x(t) are close to the solution tex2html_wrap_inline2043 and the derivative f'(x(t)) is approximately constant. We shall start from x(t) and compute the values x(t+1) and x(t+2) by using the standard fixed point iteration. Then we shall assume that x(t), x(t+1) and x(t+2) are consecutive values in a geometric series which converges to tex2html_wrap_inline2043 , and solve an estimate tex2html_wrap_inline2081 . We can then assign tex2html_wrap_inline2083 and iterate the process.

If we know that f'(x) < 0 for all x, it is also possible to derive an alternative modification which can speed up the convergence. Let us write tex2html_wrap_inline2089 , and consider the iteration process tex2html_wrap_inline2091 . For a proper choice of tex2html_wrap_inline2093 the derivative tex2html_wrap_inline2095 , and the convergence is at least quadratic. Even if tex2html_wrap_inline2097 , by choosing tex2html_wrap_inline2093 sufficiently small the iteration can be made to converge (see figure 4.1). We shall find a way to adapt the tex2html_wrap_inline2093 so that the derivative of tex2html_wrap_inline2103 with respect to x will become as close to zero as possible.

If tex2html_wrap_inline2093 is too large, the derivative is less than zero and x(t) oscillates. This will manifest itself as an alternating sign of the differences of consecutive values of x(t). If tex2html_wrap_inline2093 is too small, the derivative is greater than zero and x(t) changes monotonically. This too can be detected from the sign of the differences, which stays unchanged. We can now formulate a rule for adapting the tex2html_wrap_inline2093 during iteration. After each iteration of x(t) we shall calculate the sign of x(t)-x(t-1). If it has changed after last iteration, we shall decrease tex2html_wrap_inline2093 , otherwise we shall increase it. The use of tex2html_wrap_inline2093 speeds up convergence and allows convergence even if tex2html_wrap_inline2127 .

In our case the equation 4.1 is a system of equations. We can still use the Aitken extrapolation formula or the adaptation rule for tex2html_wrap_inline2093 proposed above, but this time we have to apply the modifications to each of the functions tex2html_wrap_inline2131 separately. Both of the modified methods and the standard fixed point iteration were tested in simulations. The iterated function was like that in equation 4.1. There were ten neurons, and the values tex2html_wrap_inline2133 were sampled from an even distribution between -4 and 0. The closer the values were to zero the better the convergence was. The distribution used in this test can be thought of as a sort of worst case, because normally the values are not this small. Figure 4.2 shows a typical test run. The standard method did not converge at all. The iteration using Aitken extrapolation formula usually converged, but much more slowly than the proposed method, which converged in all tests. The good performance of the proposed method is probably due to the fact that all partial derivatives tex2html_wrap_inline2135 since tex2html_wrap_inline2137 . Therefore the value of each of the variables tex2html_wrap_inline2139 typically oscillate in the standard fixed point iteration, and the use of adaptive tex2html_wrap_inline2093 can efficiently dampen the oscillation.

Figure 4.1: In the left, fixed point iteration does not converge to the solution tex2html_wrap_inline2043 , because tex2html_wrap_inline2145 . The derivative is negative, and therefore the derivative of a new function tex2html_wrap_inline2089 can be made zero by a proper choose of tex2html_wrap_inline2093 . In the right, tex2html_wrap_inline2151 , and tex2html_wrap_inline2153 .

Figure 4.2: The proposed modified fixed point iteration method using adaptive tex2html_wrap_inline2093 (solid line) has been compared with the standard method (dotted line) and Aitken extrapolation formula (dashed line). The proposed method has converged much more rapidly than the iteration using Aitken extrapolation formula, while the standard method has not converged at all.

next up previous contents
Next: Computational complexity Up: Evaluation of the algorithm Previous: Evaluation of the algorithm

Harri Lappalainen
Thu May 9 14:06:29 DST 1996