Combining pattern-based CRFs and weighted context-free grammars

Abstract

We consider two models for the sequence labeling (tagging) problem. The first one is a Pattern-Based Conditional Random Field (PB), in which the energy of a string (chain labeling) $x=x_{1}\ldots x_{n}\in D^{n}$ is a sum of terms over intervals $[i,j]$ where each term is non-zero only if the substring $x_{i}\ldots x_{j}$ equals a prespecified word $w\in\Lambda$ . The second model is a Weighted Context-Free Grammar (WCFG) frequently used for natural language processing. PB and WCFG encode local and non-local interactions respectively, and thus can be viewed as complementary.

We propose a Grammatical Pattern-Based CRF model (GPB) that combines the two in a natural way. We argue that it has certain advantages over existing approaches such as the Hybrid model of Benedí and Sanchez that combines $N$ -grams and WCFGs. The focus of this paper is to analyze the complexity of inference tasks in a GPB such as computing MAP. We present a polynomial-time algorithm for general GPBs and a faster version for a special case that we call Interaction Grammars.

Keywords

Pattern-based conditional random fields weighted context-free grammar interaction grammars

Get full access to this article

View all access options for this article.

References

Aho

A.V.

and Hopcroft

J.E.

, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1st edition, 1974.

Assylbekov

and Takhanov

, Reusing weights in subword-aware neural language models, in: Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), pages 1413–1423, New Orleans, Louisiana, June 2018. Association for Computational Linguistics.

Assylbekov

Takhanov

Myrzakhmetov

and Washington

J.N.

, Syllable-aware neural language models: A failure to beat character-aware ones, in: Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 1866–1872, Copenhagen, Denmark, Sept. 2017. Association for Computational Linguistics.

Bar-Hillel

Perles

and Shamir

, On formal properties of simple phrase structure grammars, Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung 14 (1961), 143–172. Reprinted in Y. Bar-Hillel. (1964). Language and Information: Selected Essays on their Theory and Application, Addison-Wesley 1964, 116–150.

Benedí

J.-M.

and Sánchez

J.-A.

, Combination of N-grams and stochastic context-free grammars for language modeling, in: COLING, pages 55–61, 2000.

Coppersmith

and Winograd

, Matrix multiplication via arithmetic progressions, in: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC ’87, pages 1–6, 1987.

Cormen

T.H.

Leiserson

C.E.

Rivest

R.L.

and Stein

, Introduction to Algorithms, The MIT Press, 2 edition, 2001.

Demetrescu

and Italiano

, A new approach to dynamic all pairs shortest paths, J. ACM 51(6) (2004), 968–992.

Earley

, An efficient context-free parsing algorithm, Commun. ACM 13(2) (Feb. 1970), 94–102.

10.

Goldberg

A.V.

, Scaling algorithms for the shortest paths problem, in: SODA, pages 222–231, 1993.

11.

Karger

Koller

and Phillips

S.J.

. Finding the hidden path: time bounds for all-pairs shortest paths, SIAM Journal on Computing 22(6) (1993), 1199–1217. Full version of paper in FOCS ’91.

12.

Katsirelos

Narodytska

and Walsh

, The weighted grammar constraint, Annals of Operations Research 184 (2011), 179–207.

13.

Nguyen

V.C.

Lee

W.S.

and Chieu

H.L.

, Semi-Markov conditional random field with high-order features, in: ICML 2011 Structured Sparsity: Learning and Inference Workshop, 2011.

14.

Nowozin

and Lampert

C.H.

, Structured learning and prediction in computer vision, Foundations and Trends in Computer Graphics and Vision 6 (2011), 185–365.

15.

Qian

Jiang

Zhang

Huang

and Wu

, Sparse higher order conditional random fields for improved sequence labeling, in: ICML, 2009.

16.

Salvador

and Benedí

J.-M.

, RNA modeling by combining stochastic context-free grammars and n-gram models, International Journal of Pattern Recognition and Artificial Intelligence 16 (2002), 309–315.

17.

Takhanov

and Assylbekov

, Patterns versus characters in subword-aware neural language modeling, in: Liu

Xie

Zhao

and El-Alfy

E.-S.M.

, eds, Neural Information Processing, pages 157–166, Cham, 2017. Springer International Publishing.

18.

Takhanov

and Kolmogorov

, Inference algorithms for pattern-based CRFs on sequence data, in: ICML, 2013.

19.

Wang

Mahajan

and Huang

, A unified context-free grammar and n-gram model for spoken language processing, in: International Conference of Acoustics, Speech, and Signal Processing, pages 1639–1642, 2000.

20.

Lee

W.S.

Chieu

H.L.

and Wu

, Conditional random fields with high-order features for sequence labeling, in: NIPS, 2009.

21.

C.-N.J.

and Joachims

, Learning structural SVMs with latent variables, in: ICML, pages 1169–1176, 2009.

22.

Zwick

, All pairs shortest paths using bridging sets and rectangular matrix multiplication, J. ACM 49(3) (2002), 289–317.