Update to support asynchronous group based cycle detection in LBP

[GoogleCodeExporter]

{{{
Hi Ciaran,

On 8/21/2012 7:36 PM, Ciaran O'Reilly wrote:
> Hi Rodrigo,
>
> On 8/21/2012 7:14 PM, Rodrigo de Salvo Braz wrote:
>> Hi Ciaran,
>>
>> Bummer. Let's see what is going on...
>>
>> On 8/21/2012 3:58 PM, Ciaran O'Reilly wrote:
>>> Hi Rodrigo,
>>>
>>> I've gone ahead and committed the updates for this. Unfortunately, the
>>> logic as it currently stands is flawed The reason is that when the
>>> neighbors for a random variable are extracted from an intensionally
>>> defined parfactor, say:
>>>
>>> {{(on X,Y) [if p(X) or q(Y) then 1 else 0] | true }}
>>>
>>> the neighbors for [p(X)] will be:
>>>
>>> {{(on Y) [if p(X) or q(Y) then 1 else 0] | true }}
>>>
>>> i.e. X is dropped as we are essentially grounding the random variable.
>>> This means that when I perform the R_in and R_complete_simplify checks
>>> in the updated version of R_m_to_v_from_f, on something like this:
>>>
>>> ( ([ p(X'') ]), ([ if p(X'') or q(Y'') then 1 else 0 ]) )
>>> in
>>> {{ ( on Y ) ( ([ p(X) ]), ([ if p(X) or q(Y) then 1 else 0 ]) ) }}
>>>
>>> an indefinite answer is returned of the form:
>>>
>>> X'' = X
>>>
>>> due to X being free in the intensional set that was placed in
>>> beingComputed previously. So the logic, as is, will keep expanding in
>>> a similar manner to the asynchronous individual update schedule.
>>>
>>> One idea I've played with in my local workspace, is to extend
>>> beingComputed with an intensional set that has its scoping expression
>>> extended with the logical variables from the random variable as well,
>>> so in this example instead of:
>>>
>>> {{ ( on Y ) ( ([ p(X) ]), ([ if p(X) or q(Y) then 1 else 0 ]) ) }}
>>>
>>> you would extend beingComputed with:
>>>
>>> {{ ( on Y, X ) ( ([ p(X) ]), ([ if p(X) or q(Y) then 1 else 0 ]) ) }}
>>>
>>> i.e. essentially the original parfactor from which you expanded your
>>> walk of the graph from (Note: in the general case this would also
>>> include constraints on the variable being expanded). Then the logic is
>>> able to return a definite yes or no. However, I'm not sure this is a
>>> sensible thing to do in the context of the algorithm as a whole.
>>
>> My feeling is that that is not quite correct because when we have the
>> set beingComputed equal to {{ ( on Y ) ( ([ p(X) ]), ([ if p(X) or q(Y)
>> then 1 else 0 ]) ) }}, we are saying that only the messages to p(X), for
>> the particular (unknown) value of X, not for every possible value of X.
>> Maybe there is some other justification for taking such step (just like
>> when you proposed your group-based asynchronous schedule and I didn't
>> see how it would be correct but was later convinced), but I am not
>> seeing it right now.
>>
>> Before we investigate that route more, I would like to understand where
>> that X'' is coming from, exactly.
>
> I pulled it from the trace output but it comes from the standardizing apart 
logic as you traverse the graph.
>
>> Is this something I can reproduce from
>> the committed code?
>
> No.
>
> You need to put this logic into DefaultProductFactor:
>
> // TODO - correct idea?
> List<Expression> indexExpressions = new 
ArrayList<Expression>(IntensionalSet.getIndexExpressions(domainS));
> Set<Expression> indices           = new 
LinkedHashSet<Expression>(IntensionalSet.getIndices(domainS));
> for (Expression v : Variables.get(msgToV_F.get(0), process)) {
>     if (!indices.contains(v)) {
>         indexExpressions.add(v);
>     }
> }
>
> Expression extendedScopingExpressionI = new 
DefaultFunctionApplication(IntensionalSet.SCOPED_VARIABLES_LABEL, 
Expressions.makeKleeneListIfNeeded(indexExpressions));
> // TODO - end correct idea?
>
> and pass extendedScopingExpressionI through to R_m_to_v_from_f instead of the 
current argument scopingExpressionI
>
>> What test is it?
>
> LBPTest.testBeliefForLoopyModels()
>
> just run the first test in the list of 4 (it runs under synchronous as does 
the second one).
>
> Use these VM Arguments:
> -Xms500M -Xmx1500M
> 
-Dlpi.lbp.belief.propagation.update.schedule.name=asynchronous_group_based_cycle
_detection
> -Dlpi.lbp.max.number.of.iterations.for.convergence=9
> -Dgrinder.display.tree.util.ui=false
> -Dgrinder.wait.until.ui.closed.enabled=false
> -Dtrace.level=trace
> -Djustification.level=off
> -Drewriter.logging.grinder.RewriteOnce=DENY
>
>
>> Or maybe you can just tell me what
>> that X'' is representing. Is it a free variable, or scoped somewhere at
>> a higher level in that context?
>
> As noted above its introduced as part of the standardize apart logic.

Ok, I took a look and now I feel I understand your correction better. 
Essentially, we want 
to put in beingComputed a *class* of messages being computing, and leaving a 
free variable X 
there defeats this purpose. It is as if we fixed the problem observed in the 
initial asynchronous 
schedule but for Y only, having it persist for X. So this new correction 
implements your idea as it 
was originally conceived.

Thanks,

Rodrigo 
}}}

Original issue reported on code.google.com by [email protected] on 11 Apr 2013 at 12:01