From: ted.dunning@gmail.com   
      
   On Jul 23, 4:25 pm, earl.dukersch...@doit.wisc.edu 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. ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)