How fast should I expect this to run?

[tpacker]

After reading that Markov Logic has been used in Siri, I assumed I could run inference on a good-sized database in real-time. I created and tried out a database of just over 100 binary ground predicates (only two predicate types and two formulas), but it's taking much longer than a real-time application could handle. Is this normal? Or am I doing something wrong?

I'm using PyMLNs, MC-SAT, infoInterval=500. I am querying one binary predicate containing one variable and one constant. After about an hour, there's still no info being written to the console.

Are there any references I could read that explain how Markov Logic is used in any real-time applications like Siri, or any benchmarks (how fast does it run on any given databases)?

[opcode81]

Try enabling debug=True to see what the algorithm is doing (and compare the output to a case where inference works without any problems). Perhaps it is not even sampling but trying to find an initial assignment that satisfies all the hard constraints in your model. If you have hard constraints, do check if they are jointly satisfiable. The speed of MC-SAT depends more on the simplicity of the satisfiability problems induced by your model than it does on the size of the database. Therefore, the question of real-time applicability is difficult to answer in general. Note that probabilistic inference is #P-hard, so worst-case behaviour can be rather bad.

[tpacker]

Thanks for the tips. I'm happy to show you the model. I don't think there are any hard constraints or jointly-unsatisfyable constraints. It's meant to represent literary agents who like certain genres of books, and a hierarchy of genres, along with transitive closure of the parent relation within the hierarchy:

LikesGenre(agent, genre) IsParentGenreOf(genre, genre) 10.0 LikesGenre(a, g1) ^ IsParentGenreOf(g1, g2) => LikesGenre(a, g2) 10.0 IsParentGenreOf(g2, g1) ^ IsParentGenreOf(g3, g2) => IsParentGenreOf(g3, g1)

I have 100 genres and 100 parent-child predicates, three agents and half-a-dozen like-predicates per agent.

... IsParentGenreOf(ChildrensLiterature, ChildrensFiction) IsParentGenreOf(ChildrensLiterature, ChildrensNonFiction) LikesGenre(KellyOden, FamilySaga) LikesGenre(KellyOden, Fantasy) ...

I see that the algorithm seems to generate all possible ground predicates with truth values and then it start "step 1" which is where is seems to freeze. The only thing after that in my successful run is "step 2" and "results".

The hierarchy is not strictly a tree -- a genre can have more than one parent. Is that a problem? I tried changing that to a tree but it doesn't seem to help.

Random question: Is it possible to put weights on ground predicates?

[opcode81]

Please provide your full model and evidence database; then I can see what's going on.

Note that while the algorithm does not consider formulas with a weight of 10 hard, they are quite hard: A world in which a formula with a weight of 10 is satisfied is e**10=22026.5 times more probable than a world in which it is not satisfied, other things being equal. If you instead wanted a factor of 10, try using "log(10)" (without the quotes) as a weight instead.

A genre having more than one parent is not a problem, as you did not declare the predicate as functional. But should the genre hierarchy be partly inferred? Because if not, make sure to provide all positive ground atoms as evidence and either declare the predicate as a closed-world predicate or additionally provide all negative ground atoms.

Yes, you can put weights on any formula, including atomic ones (grounded or not).

[tpacker]

lit-agents.zip

[tpacker]

Thanks. I was wondering how the weights were interpreted.

I did try declaring the predicate as closed-world at one point in the UI, but that seemed to produce only 0 probabilities for all results. I tried it again just now with lower weights and both predicates CW, and it finished fine but again has 0 probs for all results.

[opcode81]

Without your mlnquery configuration (query.config.dat), I don't know exactly what you are looking at, but I suspect I know what the problem is. The issue is, most likely, that the formula

10.0 LikesGenre(a, g1) ^ IsParentGenreOf(g1, g2) => LikesGenre(a, g2)

does not have the effect that you think it does. Any implication A => B with a positive weight not only increases the probability of worlds in which A and B are true but also of worlds where A is false; it affects all worlds where the formula is true in the same way. The semantics of probabilistic logical models are quite different from logical models that build upon implications/Horn clauses, where an implication never affects the "truth" of the antecedent but only the consequent. I have dubbed the fundamental misunderstanding that the two worlds are strongly related the probabilistic implication fallacy.

The consequence is, in your case, that the formula models something quite different from your expectations, which, owing to the large weight value, causes the probability of some atoms to be very close to 0. You will find that if you reduce the weight, e.g. to log(1.1), the values go up, but of course that does not solve your problem. Ultimately, you probably want to model something completely different (see the linked paper for inspiration).

As far as the second formula is concerned, I am not sure why you would want to have it in this form. If the relation is observable, then you should instead apply the closed-world assumption and provide all true atoms as evidence. Computing the transitive closure of an evidence relation can and should be performed outside of the probabilistic context. There are other languages (such as ProbCog's BLNs) which have explicit support for logical pre-computations on evidence predicates for the sake of convenience, but this can always be moved to a pre-computation step outside of the formalism.

[tpacker]

query.config.dat.zip

[tpacker]

Thanks. Very helpful. I see what you mean regarding moving the transitive closure outside of MLN. I might try that I also appreciate what you say about the fallacy, though in my case I'm not sure I thought about it long enough to even make that fallacy. :-)

As far as what I intended, I was hoping to explore MLNs and see if I could get it to rank agents by how close they were to the genre in the query, hoping that those with explicit relationships would be ranked at the top, and those "close by" in some fuzzy way would be ranked just below with non-zero probs. I chose MLNs hoping that I could simply use a single formalism and not have to worry about jumping back and forth between hard logic, belief networks, etc. I had high hopes because Dr. Domingos' sales pitches were pretty convincing.

I tried it with lower weights like 0.0953. It works much better. It runs fast enough that I can let it run for few steps now and get answers back from a query like "LikeGenre(a, CurrentAffairs)". Adding the predicates back to the closed world list also seems to work now, and seems to get it to run faster, enough so that I can let it run for more steps. But the outcome is not what I expect. When I query for agents who like CurrentAffairs, I'm expecting ErikHane to be given the highest probability because he's the only one who has an explicit connection to CurrentAffairs via the rules. But instead I get these probs after 200 steps and weights of 0.15:

0.490000 LikesGenre(EricSmith,CurrentAffairs) 0.440000 LikesGenre(ErikHane,CurrentAffairs) 0.490000 LikesGenre(KellyOden,CurrentAffairs)

BLNs sound like they might work better with my use case. I'll have to learn more about them.

[tpacker]

I suppose, as the weights get bigger or harder, it will get closer to my expectations?

With weights of 0.5:

0.510000 LikesGenre(EricSmith,CurrentAffairs) 0.660000 LikesGenre(ErikHane,CurrentAffairs) 0.490000 LikesGenre(KellyOden,CurrentAffairs)

[opcode81]

No matter how you set the weight, I doubt that the formula will achieve what you want (probabilistic implication fallacy). While you may obtain a sensible result for the three atoms you queried, you will receive strange results for atoms like LikesGenre(a, Fiction). For instance, with weight 0.5, you get

0.531000  LikesGenre(EricSmith,CurrentAffairs) 
0.002000  LikesGenre(EricSmith,Fiction)        
0.627000  LikesGenre(ErikHane,CurrentAffairs)  
0.001000  LikesGenre(ErikHane,Fiction)         
0.543000  LikesGenre(KellyOden,CurrentAffairs) 
0.004000  LikesGenre(KellyOden,Fiction)     

I would expect that those near-zero values are not in line with your expectations, but they correctly reflect what the formula models. By contrast, if you model something like this,

log(2) IsParentGenreOf(g, sg) ^ (LikesGenre(a, g) <=> LikesGenre(a, sg))

or, more verbosely,

log(2) IsParentGenreOf(g, sg) ^  LikesGenre(a, g) ^  LikesGenre(a, sg)
log(1) IsParentGenreOf(g, sg) ^  LikesGenre(a, g) ^ !LikesGenre(a, sg)
log(1) IsParentGenreOf(g, sg) ^ !LikesGenre(a, g) ^  LikesGenre(a, sg)
log(2) IsParentGenreOf(g, sg) ^ !LikesGenre(a, g) ^ !LikesGenre(a, sg)

you will obtain a result like this:

0.565000  LikesGenre(EricSmith,CurrentAffairs)  
0.980600  LikesGenre(EricSmith,Fiction)         
0.673400  LikesGenre(ErikHane,CurrentAffairs)   
0.790200  LikesGenre(ErikHane,Fiction)          
0.500400  LikesGenre(KellyOden,CurrentAffairs)  
0.918800  LikesGenre(KellyOden,Fiction)         

The result was computed via Gibbs sampling, which works much better for a model like this, because the model lacks determinism (the presence of determinism being the main reason to apply MC-SAT in the first place) and also because MC-SAT's Markov chain displays extremely slow mixing in a case like this, where so many formulas must be deselected for a switch between modes to take place because of the many connected LikesGenre atoms. Before you try Gibbs sampling yourself, make sure to pull new changes, as I've pushed some optimisations that will greatly speed things up. (No need to run make_apps or anything, just pull.)

[opcode81]

Pedro Domingos tends to highlight the strengths of MLNs without mentioning the many problems that render applications of MLNs difficult in practice. In general, I would not recommend that anyone apply MLNs unless they have really taken the time to study the semantics in detail and thus are aware of the many pitfalls. Perusing the paper I linked earlier can help in that regard.

[tpacker]

I should probably change the name of my predicates and explain my use-case better. It's true that normally when someone likes a sub-genre, you can say that they also like the parent genre. But in the case of trying to find what literary agent would represent a book (my intended use-case), we actually can't say that an agent who represents books in a sub-genre of fiction will be a good fit for representing all fiction. There are other sub-genres that they will explicitly reject, even within fiction.

On the other hand, if that agent says they represent a long list of sub-genres which all happen to be inside fiction, then I would hope that Markov logic will be fuzzy enough to let that evidence accumulate and start proposing that agent when all we know about a book is that it is fiction. But I'm sure it would take some work to find the right balance here between hard and soft.

Question: The formula

log(2) IsParentGenreOf(g, sg) ^ (LikesGenre(a, g) <=> LikesGenre(a, sg))

seems to cause the system to take this unjustified leap: when an agent likes a sub-genre, the system will also believe that not only is every other genre a parent of that sub-genre, but also that the agent will like those other genres. Am I reading this correctly? Or are these rules asymmetrical, meaning the left-hand side is treated differently than the right-hand side?

[opcode81]

IsParentGenreOf being an evidence predicate (to which we apply the closed-world assumption), the model never reasons about it at all; it is given as an input. The atom is there as a pre-condition for the rest. Therefore, what the weighted formula states is that for the case where sg is a sub-genre of g, a world where an agent likes both sg and g or neither genre is twice as probable as a world where the agent likes one but not the other. I deliberately added the variant of the model which gives you more control over the four ways in which an agent might like/not like two related genres. In the form I presented, the more verbose model represents exactly the same distribution as the one formula model, yet the other formulation allows you to change the weights of the four cases in order to achieve something different: If one case has a weight of log(x) and another a weight of log(y), then the probability ratio between the two cases will be x:y.

I don't see an "unjustified leap". To the contrary; the formula does something very close to what you described. Notice how ErikHane has a lower probability of liking Fiction than the other two in the result I reported? That's because ErikHane likes fewer sub-genres of Fiction than the two others.

[opcode81]

Shall we regard your issue as resolved?

[tpacker]

Yes. Thanks for all your help. I may have to come back to this later when I have more time.