next up previous
Next: Choosing Up: Stochastic Models Previous: Stochastic Models

   
Using $\alpha$ to control the convergence rate

Decreasing the parameter $\alpha$ causes the noise influence to decrease, but on the other hand the convergence is slower. Usually we will use $\alpha$-values such that: $\lim_{i \rightarrow \infty} \alpha_{i} = 0$.

Let us look at one Typical Example:

We would like to solve : EV[g(r,V)]=r, where the expectation regards p(V|r).

We can write iterations of the form :

$r_{n+1} \leftarrow (1-\alpha)r_{n}+\alpha E[g(r_{n},V)].$

Computing the expected value can be complicated, but if
P(V|r) is known and can be simulated or sampled, we can get samples ${\tilde{V}}$ and use them to evaluate EV[g(r,V)]. For example we can sample $\tilde{V_{1}},...,\tilde{V_{k}}$ and compute $\frac{1}{k}\sum_{i=1}^{k} g(r_{n},\tilde{V_{i}})$ as the observed average.

If
K is large, then the average will be close to its expected value EV[g(r,V)] and in such a case we should expect a similar behaviour. The other extrem is the case of k=1 (one sample), $\tilde{V_{n}}$ .

$r_{n+1} \leftarrow (1-\alpha_{n})r_{n}+\alpha_{n} g(r_{n},\tilde{V_{n}})$ where $\tilde{V_{n}}$ is distributed by p(v|r).

This algorithm is called the Robbins-Morro algorithm . The iterations can be written as:

$r_{n+1} \leftarrow (1-\alpha_{n})r_{n} + \alpha_{n} [E(g(r,V) + g(r,\tilde{V}) - E(g(r,V)]$

where we can define :
Hrn = E[g(rn,V)],
$W_{n} = g(r,\tilde{V}) - E(g(r,V)$. (and E[Wn] = 0 by definition of ${\tilde{V}}$)
This implies that for each
$s\in S$ we have,

$r_{n+1}(s) \leftarrow (1-\alpha_{n})r_{n}(s) + \alpha_{n}(s) [(Hr_{n})(s) + %
W_{n}(s)]$.


next up previous
Next: Choosing Up: Stochastic Models Previous: Stochastic Models
Yishay Mansour
1999-12-16