Robust Algorithms

From: Amir massoud Farahmand (sologen_at_yahoo.com)
Date: 12/03/04 

Date: 3 Dec 2004 13:33:20 -0800

You are writing a very advanced algorithm and it looks that you have
noticed to every aspects of implementations, but your program does not
work at all! You may become disappointed of the performance of your
advanced algorithm, or you might find a very small bug in a line of
your code: you had typed x++ instead of x--. The world would be a
better place to live if your programs were not that sensitive to these
small typos.
Not very seriously, I have thought about robust algorithm, i.e. an
algorithm that is insensitive to its changes. Is it possible?! To
answer this question, I must know what is an algorithm and what can be
considered as an algorithm. I think (however, I am not sure), an
algorithm can be considered as a thing that can be implemented by a
Turing machine and vice versa. This remains the big question that is
about the limits of a Turing machine. I know that it is a universal
computer, but I am not sure what is the exact meaning of it: does it
mean that every mathematical calculation (e.g. solving a PDE) is a
"computation" task and can be implemented by a Turing machine. In
addition, I want to know if there exists a problem that cannot be
implemented by an algorithm (you know, I have not had any course on
theory of computation or something similar).
Let's assume that an algorithm is a sufficient framework for almost
everything, including solution of a dynamical system. If the converse
is true, a dynamical system is capable to present an algorithm and is
its equivalent, is it possible to use the same robust analyses of the
dynamical system to an algorithmic one? For instance, we may analyze a
specific algorithm to see whether it is robust to some small changes
or it would become unstable? If x(n) is the state of an algorithm at
moment "n" and x(n+1) = F(x(n))+G(x(n),u(n)) is the next state, we may
present a perturbed version of it as x(n+1)=F(x(n)) + deltaF((x(n)) +
G(x(n),u(n)) + deltaG(x(n),u(n)) + du(n). These deltaF(.) and … can be
considered as perturbations and the stability of the new system is
dependent on their properties. For instance, for the following
algorithm:

Get inputs x(1) … x(k)
Sum = 0;
for(i=1;i<=k;i++)
Sum+=x(i);

a change in "i<=k" to "i<=k+1" does not change the result of the
system; however, a change in "i++" to "i+=2" is dramatic. Is it
possible to represent this problem as a dynamical system? (Maybe! The
original algorithms is an average filter, and the inner loop can be
presented as y(n) = y(n-1) + u(n) which has a critical +1 eigenvalue.
The first perturbation can be considered as a perturbation to the
final time T (+deltaT) (that would result in a smooth change in the
final result) but the second one is not that easy and may be
implemented by a modulator in G. hmmm …
I think there are still some kinds of robust algorithms in the world,
e.g. neural networks, fuzzy systems, different random sampling and
samplings. However, those are not robust in their every aspects: a
neural network is not that robust in the number of layers (if you
change a three layers (1 hidden) NN to a 2 layers (without hidden) NN,
it is not a universal function approximator anymore); a neural network
is not much robust in its learning rate and after a critical value, it
may become chaotic or even diverge; a genetic algorithm is robust to
fitness calculations, but it is not robust in the direction of sorting
in roulette wheel selection, and many more examples. What is crucial
in all these examples? Is it possible to make a really robust
algorithm?

Amir massoud Farahmand
www.sologen.net/thesilog/

Relevant Pages

  • Re: Robust Algorithms
    ... None of the algorithms you cite are robust in the sense you describe I ... Change a single statement in a neural network simulation program ... It is not more robust than any other algorithm. ... You probably want something at the programming encoding level or system ...
    (comp.theory)
  • Re: Robust statistics and optimmization from Python
    ... > FORTRAN or C code that implements a particular "robust" algorithm, ... including those for robust statistics, have been implemented in R, ... usually by wrapping C or Fortran 77 code. ...
    (comp.lang.python)
  • Real-time sinusoidal parameter estimation?
    ... The algorithm will most likely be ... implemented on an FPGA for a real-time control system. ... research on the net and experimented with MATLAB a bit, and the only robust ...
    (comp.dsp)
  • Re: Robust Algorithms
    ... >> Amir massoud Farahmand ... > IMO, no. ... You can make more or less robust algorithms. ... > to include error-detection and correction in any algorithm. ...
    (comp.theory)
  • Re: JSH: Why youre fun
    ... latest perturbation to your system. ... algorithm that you have now withdrawn - posts disappearing from your ... his post here is very much part of his usual cycle. ... It is not funny until a balanced person cracks wise. ...
    (sci.math)