Markov Logic Networks for Text Mining: A Qualitative and Empirical Comparison with Integer Linear Programming

Markov Logic Networks for Text Mining: A Qualitative and Empirical Comparison with Integer Linear Programming Luis Gerardo Mojica and Vincent Ng Human Language Technology Research Institute University of Texas at Dallas Richardson, TX 75083-0688, USA {mojica,vince}@hlt.utdallas.edu Abstract Joint inference approaches such as Integer Linear Programming (ILP) and Markov Logic Networks (MLNs) have recently been successfully applied to many natural language processing (NLP) tasks, often outperforming their pipeline counterparts. However, MLNs are arguably much less popular among NLP researchers than ILP. While NLP researchers who desire to employ these joint inference frameworks do not necessarily have to understand their theoretical underpinnings, it is imperative that they understand which of them should be applied under what circumstances. With the goal of helping NLP researchers better understand the relative strengths and weaknesses of MLNs and ILP; we will compare them along different dimensions of interest, such as expressiveness, ease of use, scalability, and performance. To our knowledge, this is the first systematic comparison of ILP and MLNs on an NLP task. Keywords: Markov Logic, Integer Linear Programming, Joint Inference 1. Introduction In the early days of the statistical natural language process- ing (NLP) era, many language processing tasks were tack- led using the so-called pipeline architecture: the given task is broken into a series of sub-tasks such that the output of one sub-task is an input to the next sub-task in the sequence. This pipeline architecture is appealing for various reasons, including modularity, modeling convenience, and manage- able computational complexity. However, it suffers from the error propagation problem: errors made in one sub-task are propagated to the next sub-task in the sequence. Realizing this weakness, researchers have turned to joint inference approaches such as Integer Linear Programming (ILP) (Roth and Yih, 2004) and Markov Logic Networks (MLNs) (Domingos and Lowd, 2009), which often outper- form their pipeline counterparts. These joint inference ap- proaches enable manual specification of constraints. These constraints effectively allow incorporation of background knowledge into NLP systems, addressing the aforemen- tioned error propagation problem by allowing the down- stream components to influence the upstream components in a pipelined system architecture. To date, MLNs have been underused in NLP applications, and are arguably much less popular among NLP researchers than ILP. While NLP researchers who desire to employ these joint inference frameworks do not necessarily have to understand their the- oretical underpinnings, it is imperative that they understand which of them should be applied under what circumstances. In light of this discussion, our goal in this paper is to help NLP researchers better understand the relative strengths and weaknesses of MLNs and ILP by comparing them along different dimensions of interest, such as expressive- ness (what can and cannot be expressed using a specifica- tion language?), ease of use (how easy is it to encode con- straints?), scalability (how efficient is the inference pro- cedure, especially when applied to large problems?), and performance (how well do these inference algorithms per- form?). To facilitate the comparison, we will discuss how ILP and MLNs …

Content truncated to 500 words