Space Efficiencies in Discourse Modeling via Conditional Random Sampling

2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 513–517, Montr´eal, Canada, June 3-8, 2012. c⃝2012 Association for Computational Linguistics Space Efficiencies in Discourse Modeling via Conditional Random Sampling Brian Kjersten CLSP Johns Hopkins University Benjamin Van Durme HLTCOE Johns Hopkins University Abstract Recent exploratory efforts in discourse-level language modeling have relied heavily on cal- culating Pointwise Mutual Information (PMI), which involves significant computation when done over large collections. Prior work has required aggressive pruning or independence assumptions to compute scores on large col- lections. We show the method of Condi- tional Random Sampling, thus far an underuti- lized technique, to be a space-efficient means of representing the sufficient statistics in dis- course that underly recent PMI-based work. This is demonstrated in the context of induc- ing Shankian script-like structures over news articles. 1 Introduction It has become common to model the distributional affinity between some word or phrase pair, (wi, wj), as a function of co-occurance within some con- text boundary. Church and Hanks (1990) suggested pointwise mutual information: PMI(wi, wj) = log Pr(wi,wj) Pr(wi) Pr(wj), showing linguistically appealing results using contexts defined by fixed width n-gram windows, and syntactic dependencies derived from automatically parsed corpora. Later work such as by Lin (1999) continued this tradition. Here we con- sider document, or discourse-level contexts, such as explored by Rosenfeld (1994) or Church (2000), and more recently by those such as Chambers and Juraf- sky (2008) or Van Durme and Lall (2009b). In the spirit of recent work in randomized algo- rithms for large-scale HLT (such as by Ravichandran et al. (2005), Talbot and Osborne (2007), Goyal et al. (2010), Talbot and Brants (2008),Van Durme and Lall (2009a), Levenberg and Osborne (2009), Goyal et al. (2010), Petrovic et al. (2010), Van Durme and Lall (2010), or Goyal and Daum´e (2011)), we pro- pose the method of Conditional Random Sampling (CRS) by Li and Church (2007) as an efficient way to store approximations of the statistics used to cal- culate PMI for applications in inducing rudimentary script-like structures. Efficiently storing such structures is an impor- tant step in integrating document-level statistics into downstream tasks, such as characterizing complex scenarios (Chambers and Jurafsky, 2011), or story understanding (Gordon et al., 2011). 2 Background Conditional Random Sampling (CRS) Li and Church (2007) proposed CRS to approximate the contingency table between elements in a query, to be used in distributional similarity measures such as cosine similarity, correlation, and PMI. Central is the idea of the postings list, which is made up of the identifiers of each document that contains a given word or phrase. A set of such lists, one per type in the underlying vocabulary, is known as an inverted index. To reduce storage costs, a CRS trun- cates these lists, now called sketches, such that each sketch is no larger than some length parameter k. Formally, assume an ordered list of document identifiers, Ω = (1, 2, ...), where each referenced document is a …

Content truncated to 500 words