Monday, March 6, 2017

example20_hidden_variables.zubr

This is our first example with the hidden variables. The Perkun section of the zubr specification looks as follows:

values
{
    value FALSE, TRUE;
    value MOVE, DONT_MOVE;
}

variables
{
    input variable alpha:{FALSE, TRUE}; // alpha may have value FALSE or TRUE   
    hidden variable gamma:{FALSE, TRUE};
    output variable beta:{MOVE, DONT_MOVE};
}


What is it good for? Imagine an automaton that can do either MOVE or DONT_MOVE. When it constantly does MOVE then the input will be:

FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE,...

But it is not known where in the sequence we begin. So even though it knows that two FALSE are succeeding when it gets a FALSE it does not know whether it was the first FALSE in the sequence or the second one.

The payoff function makes the program to "like" TRUE as input and "dislike" FALSE.

You may process the example with zubr to obtain the Java optimizer code:

zubr example20_hidden_variables.zubr > MyOptimizer.java

Here is the link to the program (you can run it directly from my server):

http://www.pawelbiernacki.net/hiddenVariablesOptimizer.jnlp

There are three scenarios possible:

1.  TRUE -> DONT_MOVE
     TRUE -> DONT_MOVE
     TRUE -> DONT_MOVE
     ....

2.  FALSE -> MOVE
     FALSE -> MOVE
     TRUE -> MOVE
     TRUE -> DONT_MOVE
     TRUE -> DONT_MOVE
     ...

3.  FALSE -> MOVE
     TRUE -> MOVE
     TRUE -> DONT_MOVE
     TRUE -> DONT_MOVE
     ...

You can see that the program created by zubr behaves a little as if it were indeterministic. Sometimes it responds TRUE with MOVE, sometimes with DONT_MOVE.

In fact it is completely deterministic, but it has a state, which is a belief (probability distribution over a set of two possible facts - gamma => FALSE and gamma => TRUE). This belief changes depending on the performed actions and obtained results. Because it has this additional knowledge (the belief) the optimizer can permit itself for example to choose MOVE when it knows that after MOVE still a TRUE will follow. On the contrary in the first scenario after TRUE it does not know whether another TRUE will follow, therefore it chooses DONT_MOVE.

This is an important point that I want to make - the state is very important for successful optimization and the hidden variables are a natural way to construct such states. Second - the optimizers can be deterministic, but still better than functions based on the input variables. In the case discussed here it is easy to construct a function that performs just as well as the zubr generated optimizer:

f(FALSE) = MOVE
f(TRUE) = DONT_MOVE

So in this case a function is just as good as the zubr optimizer, but in the more complex cases the functions just cannot beat the optimizers. We will later discuss such an example. The hidden variable based optimizers differ from the functions in so far that they have a deeper "understanding" of the outer world.

Download zubr from https://sourceforge.net/projects/perkun/.





No comments:

Post a Comment