MOSES improvement update

[Xiaohui Liu]

Hi all,

I am so sorry for having not update the work log of my GSoC project in the wiki, since I have left for my family about 11 days. I went back to school last week.

In the last week , I have finished the first part of tasks (implement the SA algorithm) .  I have modified the moses-disjuction  to using SA. But the SA maybe need some improvement too. It is not performance well.

About add the contin and onto type to  the moses. I am studying it now. I have wrote some unit tests about the field_set.

I have push the code to the branch :
 https://launchpad.net/~xiaohui/opencog/moses
and update the wiki

Thanks,
Xiaohui

[Nil Geisweiller]

Great Xiaohui,

her are my comments:

1) the parameters

INIT_TEMPERATURE
MIN_TEMPERATURE
TEMP_STEPSIZE

should be passed in the constructor of simulated_annealing instead of
being C++ macros.

2) line 956 of file optimization.h
bImprovement_made = lower_energy > best_energy ? true : false;
can be replaced by
bImprovement_made = lower_energy > best_energy;

And I'd rather move that instruction out of the conditional (before it
since best_energy is not modified yet) because the result has nothing
to do whether the condition is true or not.

3) Also I noticed that the distance is always 1, and that is probably
fine but maybe that would be interesting to be able to modulate it
too, that is having the temperature modulate both accept_probability
and the distance (the higher the temperature the higher the distance
with respect to some parameter to tune). You could have a parameter to
influence how much the temperature affects accept_probability too.

You should also be able to modulate number_of_new_instances, in SA it
is usually 1, that neighbors are picked up one by one and everytime it
is decided (based on accept_probability) whether to move to that new
center or not, so I'm sure that this may have an impact on the way SA
runs, the smaller number_of_new_instances is, the fastest a jump will
occur. Maybe you can just modulate FRACTION_OF_REMAINING too.

So you would have 6 parameters to tweak SA:

the 3 existing, init_temp, min_temp, temp_step_size, and 3 more,
accept_prob_temp_intensity, dist_temp_intensity,
fraction_of_remaining.

4) I don't think you should call best_energy by this name, because it
is not the best energy found so far since it can be re-affected with a
higher energy if the conditional line 954 is true and lower energy is
higher than best_energy. Or you need to add comment explaining that
when you define it, but my advice is to change its name, maybe
new_center_energy.

Also for that reason bImprovement is not necessarily true when an
improvement is done so far (since best_energy does not measure the
best energy), the improvement could be just local and bImprovement
would switch to true.

Anyway, IMO, bImrpovement should not be a good condition to stop the
algo (even if the improvement is global, I mean at the deme level),
actually it should be the opposite (according to SA original algo),
that is as long as SA either finds better neighbor or jumps the algo
keeps searching, and it is only when it get stucked in a local optimal
(once the temperature is too low to allow any more jumps) that the
search stops.

So you have rethink that part of the code.

5) BTW I noticed in your benchmark for maxevals=100, arity=5, SA takes
2s and hillclimbing 0s, is that an error of measurement? and if not do
you know why it is so?

Thanks
Nil

[Xiaohui Liu]

On Tue, Aug 4, 2009 at 2:00 AM, Nil Geisweiller <ngei...@googlemail.com> wrote:

Hi,

>
>> 3) Also I noticed that the distance is always 1, and that is probably
>> fine but maybe that would be interesting to be able to modulate it
>> too, that is having the temperature modulate both accept_probability
>> and the distance (the higher the temperature the higher the distance
>> with respect to some parameter to tune). You could have a parameter to
>> influence how much the temperature affects accept_probability too.
>>
>> You should also be able to modulate number_of_new_instances, in SA it
>> is usually 1, that neighbors are picked up one by one and everytime it
>> is decided (based on accept_probability) whether to move to that new
>> center or not, so I'm sure that this may have an impact on the way SA
>> runs, the smaller number_of_new_instances is, the fastest a jump will
>> occur. Maybe you can just modulate FRACTION_OF_REMAINING too.
>>
>> So you would have 6 parameters to tweak SA:
>>
>> the 3 existing, init_temp, min_temp, temp_step_size, and 3 more,
>> accept_prob_temp_intensity, dist_temp_intensity,
>> fraction_of_remaining.
>

> I set the distance always be 1 because of I haven't thought that it could be
> modulated by the temperature too.
> I thought that the SA should pick the neighbors one by one before coding,
> maybe the iterative hillcilimbing algo gives me an effect and let me to
> think sample the neighbors like it. So, Nil, we could sample the neighbor
> one by one(i.e. let the sample_size always to be 1 every iteration), and the
> fraction_of_remaining won't need any more.

It could be an interesting variation with more than 1 at a time,
though perhaps it amounts to having a lower initial temperature and a
slower temperature decrease, so we can let it at 1 and let that for
later, possibly.

>
> The parameters accept_prob_temp_intensity, and dist_temp_intensity you
> mentioned above, I am still not clear about how to use them. In the
> accept_probability function, I have use the current temparature to modulate
> the accept_probablity. Could you give me an example about it?

accept_prob_temp_intensity and dist_temp_intensity would be in [0,1]
and represent the degree to which accept_prob and distance are
modulated by the temperature, so for instance

actual_prob = accept_prob_temp_intensity * accept_prob

actual_distance = min(1, dist_temp_intensity * distance_temp(T...))

That way we can tweak the sensitivity of jump distance and jump
probability seperatly.

 Hi Nil,
 
Here we use let actual_distance =  min(1, dist_temp_intensity * dist_temp(T...))  and It leads the actual_distance always to be 1 or 0. But 0 here is not valid, because the distance should greater than 0. So ,should we change min to max?

You mentioned that the higher temperature ,the higher the distance should be. So ,the distance should decrease as the temperature, right?  If I thought correctly, the dist_temp could like this:
 
int dist_temp ( double current_temp)
{
    return (int)( (max_dist - min_dist) / (init_temp - min_temp) * (current_temp - min_temp) + min_dist );
}

any comments?

>> 5) BTW I noticed in your benchmark for maxevals=100, arity=5, SA takes
>> 2s and hillclimbing 0s, is that an error of measurement? and if not do
>> you know why it is so?
>

>  It is not an error of measurement, maybe it is because some errors happens
> in the iteration.
> I found that the size of center_instance have changed:
> Iterate 1:
> Found instance:[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
> 0 0 0 0 0 0 1 0 0 0 ]
> Iterate 2:
> Found instance:[ 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 000]
>
> there may be some mistake in the assignment of the instance.

You mean within a single deme? if so yes that must be a bug.

Nil

[Nil Geisweiller]

Hi Xiaohui,

>
>  Hi Nil,
>
> Here we use let actual_distance =  min(1, dist_temp_intensity * dist_temp(T...))  and It leads the actual_distance always to be 1 or 0. But 0 here is not valid, because the distance should greater than 0. So ,should we change min to max?

yes sorry, max.

>
> You mentioned that the higher temperature ,the higher the distance should be. So ,the distance should decrease as the temperature, right?  If I thought correctly, the dist_temp could like this:
>
> int dist_temp ( double current_temp)
> {
>     return (int)( (max_dist - min_dist) / (init_temp - min_temp) * (current_temp - min_temp) + min_dist );
> }
>
> any comments?

that seems correct.

Nil