Because multiple runs of separate linear-chain CRFs ignore the dependency between source sentences, the second approach we propose is to use a 2D CRF that models all pair relationships jointly.

Our experimental results show that our proposed sentence type tagging method works very well, even for the minority categories, and that using 2D CRF further improves performance over linear-chain CRFs for identifying dependency relation between sentences.

In Section 3, we introduce the use of CRFs for sentence type and dependency tagging.

Our study is different in several aspects: we are using forum domains, unlike most work of DA tagging on conversational speech; we use CRFs for sentence type tagging; and more importantly, we also propose to use different CRFs for sentence relation detection.

To automatically label sentences in a thread with their types, we adopt a sequence labeling approach, specifically linear-chain conditional random fields ( CRFs ), which have shown good performance in many other tasks (Lafferty, 2001).

Linear-chain CRFs is a type of undirected graphical models.

CRFs is a special case of undirected graphical model in which w are log-linear functions:

While most of the state-of-the-art CWS systems used semi-Markov conditional random fields or latent variable conditional random fields, we simply use a single first-order conditional random fields ( CRFs ) for the joint modeling.

The semi-Markov CRFs and latent variable CRFs relax the Markov assumption of CRFs to express more complicated dependencies, and therefore to achieve higher disambiguation power.

Alternatively, our plan is not to relax Markov assumption of CRFs , but to exploit more complicated dependencies via using refined high-dimensional features.

3.1 A Joint Model Based on CRFs

First, we briefly review CRFs .

CRFs are proposed as a method for structured classification by solving “the label bias problem” (Lafferty et al., 2001).

Sequence tagging algorithms including HMMs (Ra-biner, 1989), CRFs (Lafferty et al., 2001), and Collins’s perceptron (Collins, 2002) have been widely employed in NLP applications.

In this section, we formulate the sequential decoding problem in the context of perceptron algorithm (Collins, 2002) and CRFs (Lafferty et al., 2001).

and a CRFs model is

For CRFs , Z (x) is an instance-specific normalization function

A similar idea was applied to CRFs as well (Cohn, 2006; Jeong, 2009).