Re: Any interest in sparse K-Map issues? (or how to make a guess)

On Jul 23, 4:25 pm, earl.dukersch...@xxxxxxxxxxxxx wrote:
Do you think my scheme for avoiding the combinatorial explosion (my
reply to the first post) has merit?

Yes.

Lets say you have a number of actions, where each action sends a signal to
a different circuit. ...

I think that you burden yourself here with too concrete a description.

Action 5 will toggle the second bit of state 9 to give state D, which
is closer to state F than
state 9.

Action 10 will toggle the third bit of state D to the desired state F.

If the plan fails, do another cycle of learning.

I don't quite understand this.

Phrasing your problem in my terms, I think that what you are seeking
is a way to learn a Boolean function with n inputs and one output from
an oracle. You want to learn this function to some desired degree of
accuracy with as few questions to the Oracle as possible.

You may also wish to enforce a bias toward "simple" solutions.

Initially all possible functions are possible, although, not
necessarily of equal likelihood.

In the case of equal likelihood, you have complete symmetry and you
can choose the next question to that half of the remaining possible
functions will answer yes and half will answer no. (actually
determining which question this is and actually representing the set
of remaining functions may be a bit of a challenge ... I don't know).
In the equiprobable case, I think that you actually have very little
gain from the active learning.

Suppose that you want to learn AND of 3 variables, A, B and C.
Further, suppose that the negative of the log probability of a formula
is proportional to the minimum of number of variables in all of the
terms in the simplest sum of products form of the formula or its
inverse. The truth table for the AND function is as follows

A B C f(A, B, C)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1

Now AND(A, B, C) = ABC and NOT(AND(A,B,C)) = -A + -B + -C so the log
probability is proportional to -3. The most likely formulae are A,
B, C, -A, -B, -C followed by AB, AC, A + C, A + -B and so on. XOR is
as unlikely as any function can get with its sum of products form of
ABC + (-A)(-B)C + (-A)B(-C) + A(-B)(-C) which has complexity of 12.

We can, of course, represent this function by just reading off the
bits in the f column. This is convenient for representation, but it
doesn't help us compute the complexity. AND would be 1000,0000 (I
insert the comma for clarity). XOR would be 1001,0110.

As our first question, let's ask the oracle for f(0,0,0). We get 0 so
we now know that functions that look like ???????0 are all possible.
We also know that formula A, A + B, AB, ABC and AC are all still
possible answers while -A, (-A)(-B) and many others are not possible.
The most likely possibilities are A, B, C followed by AB, A+B, (-A)B,
A(-B) and so on. Asking for f(1, 0, 0) splits these reasonably well.
If this answer is 1, then A is possible and -A, B, and C are not. The
same sort of effect happens for each level of complexity of possible
formula. In fact the answer is 0 so we have the following formulae of
complexity 1 and 2 remaining:

B, C
AB, AC, (-A)B, (-A)C

Many more formulae of higher complexity are also possible.

Asking about f(0, 1, 0) and getting 0 from the oracle will leave us
the following possibilities of complexity 1 and 2,

C
AB, AC, (-A)C

At this point, the answer to f(0,0,1) will affect C and (-A)C. Asking
about f(1, 1, 0) will only affect AB. Asking about f(1,1,1) will
affect C, AB and AC. Considering only the first two levels, f(1,1,1)
therefore appears to be the best question. Getting the answer of 1
leaves

C
AB, AC
ABC

The gain so far is not very impressive, but with larger problems it
can be dramatic, especially if you have a strong prior.

[ comp.ai is moderated ... your article may take a while to appear. ]
.

Relevant Pages

  • Re: Sybase and materialized views
    ... Meaning - I suppose - that Oracle has no problems materializing a view, ... regardless of the complexity and number of tables in the defining select. ...
    (comp.databases.sybase)
  • Re: Oracle 10g RAC performance
    ... conclusion they need Oracle. ... have the idea that since Oracle is pushing RAC to everybody, ... risk more layers of complexity adds. ... a full time DBA just to manage a database. ...
    (comp.databases.oracle.server)