Definition: In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
Input: We consider Conditional Random Fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) x1 . . . xn is the sum of terms over intervals [i, j] where each term is non-zero only if the substring xi . . . xj equals a prespecified pattern α. Such CRFs can be naturally applied to many sequence tagging problems. We present efficient algorithms for the three standard inference tasks in a CRF, namely computing (i) the partition function, (ii) marginals, and (iii) computing the MAP. Their complexities are respectively O(nL), O(nL`max) and O(nLmin{|D|, log(`max+1)}) where L is the combined length of input patterns, `max is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of [Ye et al. NIPS 2009] whose complexities are respectively O(nL|D|), O ( n|Γ|L`max ) and O(nL|D|), where |Γ| is the number of input patterns. In addition, we give an efficient algorithm for sampling, and revisit the case of MAP with non-positive weights. This paper addresses the sequence labeling (or the sequence tagging) problem: given an observation z (which is usually a sequence of n values), infer labeling x = x1 . . . xn where each variable xi takes values in some finite domain D. Such problem appears in many domains such as text and speech analysis, signal analysis, and bioinformatics. One of the most successful approaches for tackling the problem is the Hidden Markov Model (HMM). The kth order HMM is given by the probability distribution p(x|z) = 1 Z exp{−E(x|z)} with the energy function E(x|z) = ∑ i∈[1,n] ψi(xi, zi) + ∑ (i,j)∈Ek ψij(xi:j) (1) where Ek = {(i, i+ k) | i ∈ [1, n− k]} and xi:j = xi . . . xj is the substring of x from i to j. A popular generalization is the Conditional Random Field model [3] that allows all terms to depend on the full observation z: E(x|z) = ∑ i∈[1,n] ψi(xi, z) + ∑ (i,j)∈Ek ψij(xi:j , z) (2) A preliminary version of this paper appeared in Proceedings of the 30th International Conference on Machine Learning (ICML), 2013 [8]. This work was partially supported by the European Research Council under the European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no 616160. 1 ar X iv :1 21 0. 05 08 v5 [ cs .L G ] 2 0 Ja n 20 17 We study a particular variant of this model called a pattern-based CRF. It is defined via

Inference algorithms for pattern-based CRFs on sequence data