boolean reduct + errors

[Nil Geisweiller]

Hi Moshe,

I've tried out PLOP (rev 170) on SBCL 1.0.29.11.debian, first let me
report 2 things:

1) the QuickStart page http://code.google.com/p/plop/wiki/QuickStart
is probably missing the following in the Section Loading:

(load "foo/trunk/thirdparty/numrecip.lisp")

2) I tried the learning example

(p2sexpr (bool-hillclimb-with-target-truth-table
'(t nil t nil t t nil nil) 10000 '(x y z)))

but got an error (see end of the email).

My purpose was to check if PLOP can reduce the following (which MOSES cannot)

(and (or (and x (not z)) y) (or (and x y) (not z)))

which is equivalent to

(and (or (and x (not z)) y) (or x (not z)))

but it couldn't.

I didn't try in MAXIMA, I gave up when I saw that it fails to reduce
(x and x) but succeeds to reduce (x and false) :-/

I don't know yet how to handle that case and I'd rather go with some
very general principle that will allow me to reduce some super big
class of it rather than a specific hack, even if it's very costly. I
though if I can reduce given assumptions like

1) assuming
(or (and x (not z)) y)

2) then
(or (and x y) (not z))

3) can be reduced to
(or (and x true) (not z))

4) so the overall expression can be reduced to
(and (or (and x (not z)) y) (or x (not z)))

the hard part being from 2 to 3.

The reason I want to improve reduction is to see how it impacts on
MOSESs performance (#eval-wise), I don't care if that optimizer is
very costly for now.

Any thought is very welcome.

Thanks
Nil

========
* (p2sexpr (bool-hillclimb-with-target-truth-table
'(t nil t nil t t nil nil) 10000 '(x y z)))

; (BOOL-HILLCLIMB-WITH-TARGET-TRUTH-TABLE '(T NIL T NIL T T NIL NIL) 10000
; '(X Y Z))
;
; caught STYLE-WARNING:
; undefined function: BOOL-HILLCLIMB-WITH-TARGET-TRUTH-TABLE

; (P2SEXPR
; (BOOL-HILLCLIMB-WITH-TARGET-TRUTH-TABLE '(T NIL T NIL T T NIL NIL) 10000
; '(X Y Z)))
;
; caught STYLE-WARNING:
; undefined function: P2SEXPR
;
; compilation unit finished
; Undefined functions:
; BOOL-HILLCLIMB-WITH-TARGET-TRUTH-TABLE P2SEXPR
; caught 2 STYLE-WARNING conditions

debugger invoked on a UNDEFINED-FUNCTION in thread #<THREAD "initial
thread" RUNNING {AA5E6F1}>:
The function BOOL-HILLCLIMB-WITH-TARGET-TRUTH-TABLE is undefined.

Type HELP for debugger help, or (SB-EXT:QUIT) to exit from SBCL.

restarts (invokable by number or by possibly-abbreviated name):
0: [ABORT] Exit debugger, returning to top level.

("bogus stack frame")

[Moshe Looks]

Nil,

Regarding the error, my guess is that you need to first do

(in-package plop)

Regarding MAXIMA, yes, their Boolean reduction rules are very week!

> 1) assuming
> (or (and x (not z)) y)
>
> 2) then
> (or (and x y) (not z))
>
> 3) can be reduced to
> (or (and x true) (not z))
>
> 4) so the overall expression can be reduced to
> (and (or (and x (not z)) y) (or x (not z)))
>
> the hard part being from 2 to 3.
>
> The reason I want to improve reduction is to see how it impacts on
> MOSESs performance (#eval-wise), I don't care if that optimizer is
> very costly for now.
>
> Any thought is very welcome.
>

If you are only looking at small formulae (arity-wise), and don't care
about wall-clock time then an effective reduction procedure that will
handle the formula in question is:

tt_reduct (expr)
let tt = truth table of expr
for every subtree s in expr from largest to smallest (including leaves)
let expr2 = expr with s removed
let tt2 = truth table of expr2
if tt == tt2
return tt_reduct(reduct(expr2))
return expr

where reduct is the usual rule-based reduction.

But my guess is that reduct for moses is already "good enough" and
that you won't see a significant improvement in # evals. If you want
to see an improvement in # of evals, try turning off the current
reduct and compare that.. ;->

Anyway, looking forward to hearing if you find anything this way!

- Moshe

[Nil Geisweiller]

Hi Moshe,

thanks for you're gusty suggestion ;-)

I've implemented it but now I'm running into other troubles before I
can produce a nice benchmark.

I've a question meanwhile, page 56, Table 6.3 of your PhD
dissertation, do you count the computational effort with all reduced
candidates (i.e. not evaluating twice the same candidate), or you only
use reduction over the exemplars?

The hypothesis I'm trying to check is that a very strong reductor,
even only applied over exemplars, may decrease noticeably #eval.

Nil

> --
> You received this message because you are subscribed to the Google Groups "plop-dev" group.
> To post to this group, send email to plop...@googlegroups.com.
> To unsubscribe from this group, send email to plop-dev+u...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/plop-dev?hl=en.
>
>

[Moshe Looks]

> I've a question meanwhile, page 56, Table 6.3 of your PhD
> dissertation, do you count the computational effort with all reduced
> candidates (i.e. not evaluating twice the same candidate), or you only
> use reduction over the exemplars?
>

I use reduction on all candidates and don't count duplicates (based on
a cache of size 10,000). The computational effort is computed using
the number of programs that actually get evaluated on the fitness
function.

> The hypothesis I'm trying to check is that a very strong reductor,
> even only applied over exemplars, may decrease noticeably #eval.
>

Let me know how it goes!

- Moshe

[Nil Geisweiller]

I got some benchmark (see attached) but there are fairly
disappointing, over 30 trials only 3 (indicated with a left arrow on
the benchmark) led to better performance using the super reductor (in
term of less #evals counting duplicates).

I'm not sure exactly why. Note that the search with super reductor
often halts because no more non-visited non-dominated candidate are
left, I'm sure what to do about that, I've tried to just revisit them
but it bears to fruits. I must precise too that the reductor used
during the pruning knob heuristic is the classical one, I tried with
the super one but it's even worth in term of halting the search
prematurely. My results are with 3-parity problem and now I'm
computing some benchmarks with 6-parity to see if that yield to the
same kind of results.

Nil

[Nil Geisweiller]

> left, I'm sure what to do about that, I've tried to just revisit them

not sure...

Nil

[Nil Geisweiller]

Moshe,

I've retried your learning example but without success, the other
examples work though. Here's the log again:

#<PACKAGE "PLOP">

* (p2sexpr (bool-hillclimb-with-target-truth-table
'(t nil t nil t t nil nil) 10000 '(x y z)))

; (PLOP:BOOL-HILLCLIMB-WITH-TARGET-TRUTH-TABLE '(T NIL T NIL T T
NIL NIL) 10000
; '(PLOP::X PLOP::Y PLOP::Z))

;
; caught STYLE-WARNING:
; undefined function: BOOL-HILLCLIMB-WITH-TARGET-TRUTH-TABLE
;

; compilation unit finished
; Undefined function:
; BOOL-HILLCLIMB-WITH-TARGET-TRUTH-TABLE
; caught 1 STYLE-WARNING condition

debugger invoked on a UNDEFINED-FUNCTION in thread #<THREAD "initial
thread" RUNNING {AA5E6F1}>:
The function BOOL-HILLCLIMB-WITH-TARGET-TRUTH-TABLE is undefined.

Type HELP for debugger help, or (SB-EXT:QUIT) to exit from SBCL.

restarts (invokable by number or by possibly-abbreviated name):
0: [ABORT] Exit debugger, returning to top level.

("bogus stack frame")

0]

Nil

[Nil Geisweiller]

On Mon, Aug 9, 2010 at 9:31 AM, Nil Geisweiller <ngei...@googlemail.com> wrote:

>> left, I'm sure what to do about that, I've tried to just revisit them

what I could do is revisiting them with a lower reduct effort, since
as my 2 benchmarks show the less the reduct effort the less this
blocking situation occurs. I'll try that tomorrow.

Nil

[Moshe Looks]

You're right, sorry, I forgot that I took out the hillclimber. Try
'moses', or 'moses-on-target'...

On Mon, Aug 9, 2010 at 10:01 AM, Nil Geisweiller

[Nil Geisweiller]

On Mon, Aug 9, 2010 at 6:03 PM, Moshe Looks <madsc...@google.com> wrote:
> You're right, sorry, I forgot that I took out the hillclimber. Try
> 'moses', or 'moses-on-target'...

I tried that

#<PACKAGE "PLOP">
* (p2sexpr (moses-on-target '(t nil t nil t t nil nil) 10000 '(x y z)))

debugger invoked on a UNDEFINED-FUNCTION in thread #<THREAD "initial
thread" RUNNING {AA5E6F1}>:

The function NIL is undefined.

Type HELP for debugger help, or (SB-EXT:QUIT) to exit from SBCL.

restarts (invokable by number or by possibly-abbreviated name):
0: [ABORT] Exit debugger, returning to top level.

(SB-KERNEL:%COERCE-CALLABLE-TO-FUN NIL)

isn't it strange that NIL is undefined?

[Moshe Looks]

Try e.g.

PLOP> (moses-on-target '(true true false false) 1000 '(func (bool bool) bool))

[Nil Geisweiller]

On Mon, Aug 9, 2010 at 9:26 PM, Moshe Looks <madsc...@google.com> wrote:
> Try e.g.
>
> PLOP> (moses-on-target '(true true false false) 1000 '(func (bool bool) bool))

I'm getting that

#<PACKAGE "PLOP">
* (moses-on-target '(true true false false) 1000 '(func (bool bool) bool))

debugger invoked on a SIMPLE-TYPE-ERROR in thread #<THREAD "initial
thread" RUNNING {AA5E6F1}>:
Argument X is not a NUMBER: NIL

Type HELP for debugger help, or (SB-EXT:QUIT) to exit from SBCL.

restarts (invokable by number or by possibly-abbreviated name):
0: [ABORT] Exit debugger, returning to top level.

(SB-KERNEL:TWO-ARG-+ NIL 1)

[Nil Geisweiller]

Hi Moshe,

1)

after uncovering and fixing a bug in metapopulation::insert (would not
insert a candidate if there is already one with same score and size
even if it was non-dominated) I decided to give another shot to the
super-reductor.

Problem = 3-parity
algo = hillclimbing
I don't count duplicates. Each result is the average of the number of
evaluations to reach the optimal solution over 100 runs (using seed =
1 to 100).

PSR = population size ratio
Std = standard reductor
Super = super reductor
Eval = number of evals to reach solution averaged over 100 runs

Here's the results:
----
PSR = 20, Std
Eval = 76512
----
PSR = 20, Super
Eval = 34180
----
PSR = 1, Std
Eval = 12712
----
PSR = 1, Super
Eval = 8664
----

So according to these experiments there is an advantage (#eval-wise)
in using a super reductor. I tried with PSR = 1 as I expected to be
the worse situation for the super-reductor to shine, but even then
it's still advantageous. I carefully checked that no result from the
super reductor experiments halted prematurely due to the blockage
situation I described in a previous post, of course no blockage
occurred as it was due to the metapopulation::insert bug...

Now I'm thinking how leverage this in term of raw speed, my proposal
is to move the reduction (the one occurring before inserting a
candidate to the metapopulation) in metapopulation::select_exemplar,
that is: select a candidate, super-reduce it, and possibly redo a
selection if it turns out that it has already been visited. I'll let
you know how it goes (when it goes because I'm busy with other stuff
too). I'd be curious to try with an even stronger reductor although I
guess it would (if ever) only help lightly as the super-reductor you
suggested is very powerful already.

2)

I tried to test how much ignoring dominated candidates helps (so I
dis-activated dominance check and include all candidates in the
metapop). I tried only with 3-parity and different PSR but in every
case I got no difference at all. I checked carefully the logs of a few
trials and indeed I understood why, the probability to find a
dominated candidate with a high score so that it is selected in the
first place is usually very very low, at least in my experiments. I
can imagine that with different bscore defs or different problems it
would be another story. Do you know any specific problem that really
show the advantage of selecting only non-dominated candidates?

3)

Could you please help me to run plop ;-), here's a recall of my previous post:

>> Try e.g.
>>
>> PLOP> (moses-on-target '(true true false false) 1000 '(func (bool bool) bool))
>
> I'm getting that
>
> #<PACKAGE "PLOP">
> * (moses-on-target '(true true false false) 1000 '(func (bool bool) bool))
>
> debugger invoked on a SIMPLE-TYPE-ERROR in thread #<THREAD "initial
> thread" RUNNING {AA5E6F1}>:
>  Argument X is not a NUMBER: NIL
>
> Type HELP for debugger help, or (SB-EXT:QUIT) to exit from SBCL.
>
> restarts (invokable by number or by possibly-abbreviated name):
>  0: [ABORT] Exit debugger, returning to top level.
>
> (SB-KERNEL:TWO-ARG-+ NIL 1)

Thanks!
Nil

[Nil Geisweiller]

> I don't count duplicates.

cerr << "I do count duplicates, of course..." << endl;

Nil

[Moshe Looks]

Nil,

> Now I'm thinking how leverage this in term of raw speed, my proposal
> is to move the reduction (the one occurring before inserting a
> candidate to the metapopulation) in metapopulation::select_exemplar,
> that is: select a candidate, super-reduce it, and possibly redo a
> selection if it turns out that it has already been visited. I'll let
> you know how it goes (when it goes because I'm busy with other stuff
> too). I'd be curious to try with an even stronger reductor although I
> guess it would (if ever) only help lightly as the super-reductor you
> suggested is very powerful already.
>

This is interesting, but 3-parity is a very extreme case (since there
are only 2^8 = 256) possible truth tables. Also, the numbers are still
quite a bit higher than the ones I reported in my dissertation for the
earlier version moses...

> I tried to test how much ignoring dominated candidates helps (so I
> dis-activated dominance check and include all candidates in the
> metapop). I tried only with 3-parity and different PSR but in every
> case I got no difference at all. I checked carefully the logs of a few
> trials and indeed I understood why, the probability to find a
> dominated candidate with a high score so that it is selected in the
> first place is usually very very low, at least in my experiments. I
> can imagine that with different bscore defs or different problems it
> would be another story. Do you know any specific problem that really
> show the advantage of selecting only non-dominated candidates?
>

If I understand what you're did here, its to modify the metapopulation
insertion criterion so that any candidate can potentially become a
deme, right? But the selection criterion for creating a deme that I
hacked up (exponentially decreasing with # of errors made, iirc), is
so heavily biased towards the best candidates, that this is unlikely
to change the algorithms behavior (just increase its memory usage).

So I don't think that the algorithm's behavior will be altered much by
this kind of change, unless you also change the selection criterion
for creating a deme. I experimented a bit with stronger (always pick
the best solution) and weaker (roulette selection based on fitness)
deme creation mechanisms, and IIRC both were significantly worse. I
worked a bit on smarter deme selection criterion as well, more
recently.

> Could you please help me to run plop ;-), here's a recall of my previous post:
>

Fixed. Try revision 172...

- Moshe

[Nil Geisweiller]

Hi Moshe,

>> Now I'm thinking how leverage this in term of raw speed, my proposal
>> is to move the reduction (the one occurring before inserting a
>> candidate to the metapopulation) in metapopulation::select_exemplar,
>> that is: select a candidate, super-reduce it, and possibly redo a
>> selection if it turns out that it has already been visited. I'll let
>> you know how it goes (when it goes because I'm busy with other stuff
>> too). I'd be curious to try with an even stronger reductor although I
>> guess it would (if ever) only help lightly as the super-reductor you
>> suggested is very powerful already.
>>
> This is interesting, but 3-parity is a very extreme case (since there
> are only 2^8 = 256) possible truth tables.

sure, I'll try with other more difficult problems (as soon as I have
some time for it).

> Also, the numbers are still
> quite a bit higher than the ones I reported in my dissertation for the
> earlier version moses...

Which page? Recall that I do count duplicates, and I do not report
computational efforts just averages of #evals to reach the solution.
The result in your dissertation page 56 do not count duplicates which
is why I did not try to compare to it. Using the super-reductor it's
clear that it would be much lower but that is not my goal since
reducing all candidates using such a reductor is not gonna lead to an
overall speed increase anyway.

>
>> I tried to test how much ignoring dominated candidates helps (so I
>> dis-activated dominance check and include all candidates in the
>> metapop). I tried only with 3-parity and different PSR but in every
>> case I got no difference at all. I checked carefully the logs of a few
>> trials and indeed I understood why, the probability to find a
>> dominated candidate with a high score so that it is selected in the
>> first place is usually very very low, at least in my experiments. I
>> can imagine that with different bscore defs or different problems it
>> would be another story. Do you know any specific problem that really
>> show the advantage of selecting only non-dominated candidates?
>>
> If I understand what you're did here, its to modify the metapopulation
> insertion criterion so that any candidate can potentially become a
> deme, right?

Right.

> But the selection criterion for creating a deme that I
> hacked up (exponentially decreasing with # of errors made, iirc), is
> so heavily biased towards the best candidates, that this is unlikely
> to change the algorithms behavior (just increase its memory usage).
>
> So I don't think that the algorithm's behavior will be altered much by
> this kind of change, unless you also change the selection criterion
> for creating a deme.

Yes that was my point, thus the motivation to move exemplar reduction
inside metapop::select_exemplar to save unnecessary reductions (which
does matter when using this bastard! ;-). Then the only drawback is
that the occam's razor is a bit broken since a large unreduced
candidate corresponding to very short reduced one may loose against a
short unreduced candidate corresponding to a not so short reduced one.
I don't know if that's a problem, I'd need to experiment, if that is
really a problem then only the best ones would be reduced before
selection, instead of the entire metapop.

> I experimented a bit with stronger (always pick
> the best solution) and weaker (roulette selection based on fitness)
> deme creation mechanisms, and IIRC both were significantly worse. I
> worked a bit on smarter deme selection criterion as well, more
> recently.

Cool, is it in OSS PLOP already?

>
>> Could you please help me to run plop ;-), here's a recall of my previous post:
>>
> Fixed. Try revision 172...

Thanks
Nil

[Moshe Looks]

> Which page? Recall that I do count duplicates, and I do not report
> computational efforts just averages of #evals to reach the solution.
> The result in your dissertation page 56 do not count duplicates which
> is why I did not try to compare to it. Using the super-reductor it's
> clear that it would be much lower but that is not my goal since
> reducing all candidates using such a reductor is not gonna lead to an
> overall speed increase anyway.
>

Ah, sorry; you're right, I never looked at #evals counting duplicates.
But with the super-reductor really you are doing multiple evals
(computations of the truth table) in the course of reduction.. Of
course for 3-parity a truth table is 8 entries and this is trivial,
but e.g. for even a slightly harder gp toy problem like the
11-multiplexer (2^11 = 2048 fitness cases) counting evals (and not
duplicates) is clearly the way to go...

>> I experimented a bit with stronger (always pick
>> the best solution) and weaker (roulette selection based on fitness)
>> deme creation mechanisms, and IIRC both were significantly worse. I
>> worked a bit on smarter deme selection criterion as well, more
>> recently.
>
> Cool, is it in OSS PLOP already?
>

Yes, in moses.lisp ; this is
http://code.google.com/p/plop/wiki/ChoosingPromisingExemplars which I
think you commented on way back when...

- Moshe

[Nil Geisweiller]

>>> I experimented a bit with stronger (always pick
>>> the best solution) and weaker (roulette selection based on fitness)
>>> deme creation mechanisms, and IIRC both were significantly worse. I
>>> worked a bit on smarter deme selection criterion as well, more
>>> recently.
>>
>> Cool, is it in OSS PLOP already?
>>
> Yes, in moses.lisp ; this is
> http://code.google.com/p/plop/wiki/ChoosingPromisingExemplars which I
> think you commented on way back when...

Interesting! looking forward to seeing a benchmark.

Nil