quote: Original post by Arringhen
This is why FSM are considered deterministic algorithm and GA or Neural Nets are non deterministic...

Wait... Some neural networks are probabilistic, some are completely deterministic. Let's be clear, too, about the source of any randomness: The most common neural architecture (MLP) is most often trained with some variation of backpropagation. The (forward) firing of an MLP is completely deterministic. Backpropagation as a training algorithm is also completely deterministic. It is the intialization which is probabilistic. Regardless, MLPs can be trained by totally determinstic algorithms (though they rarely are), and there are other neural architectures (polynomial networks, RAM neuron discriminators, SDMs, etc.), which are completely determinstic.

On the other hand, not all finite state machines are deterministic (though the vast majority are, in practice). The most common "crisp" FSMs and fuzzy FSMs are deterministic, while stochastic automata and lattice automata are not.

-Predictor
http://will.dwinnell.com




[edited by - Predictor on February 11, 2004 8:56:45 AM]

quote: Original post by Timkin
So how would you describe an algorithm that branched based on the perception of a stochastic event in the environment (and yes, let''s assume the event is truly stochastic, like the emmision of a gamma photon from a radioactive isotope)? Is the algorithm deterministic given the input, deterministic or stochastic if we ignore the input, or does the input count as part of the computational algorithm and hence make the algorithm stochastic?

I''d think the definition of algorithm generally separates it totally from any data, so personally I''d class it as deterministic. But I wasn''t really trying to make a point, just trying to understand what the original poster had meant by the term. (Which has now been clarified above.)

quote: I think its sufficient to say that at some level a system may be perceived as stochastic

I agree with this. I definitely agree that the behavior of a system system or algorithm can be perceived as stochastic. A blackboard would be a good example of a system which, to an individual kb, would be perceived as stochastic. The individual kbs may add a rule, but they have no way of predicting what may happen as a result.

At the same time, to a higher level system, which knew what kbs were attached and how they operated, the behavior of the blackboard would still be deterministic.

In games however, keeping a percept history is probably enough to make decisions feel random to the player, as they cannot observe the 'rules' which drive the system.

[edited by - BrianL on February 11, 2004 12:43:23 PM]

quote: Original post by Kylotan
I''d think the definition of algorithm generally separates it totally from any data

Of course... but what if the perception is stochastic. That is, for the same input data, the perception of that data might be different.

Timkin

quote: Original post by Kylotan
I'd think the definition of algorithm generally separates it totally from any data, so personally I'd class it as deterministic.

Some algorithms are deliberately probabilistic, like genetic algorithms, many solutions to the Dining Philosophers problem and Buffon's Needle algorithms (Buffon actually threw pieces of bread onto the floor, in a sort of Monte Carlo process).

-Predictor
http://will.dwinnell.com





[edited by - Predictor on February 12, 2004 8:20:09 AM]