Automatic Document Separation: A Combination of Probabilistic Classification and Finite-State Sequence Modeling - Natural Language Processing and Text Mining - page 133

States

Previous Current

Appraisal Appraisal (A,A) (A,A)

TaxForm Appraisal (T,A) (T,A)

Note Appraisal (N,A)

Appraisal TaxForm (A,T) (A,T)

TexForm TaxForm (T,T)

Note TaxForm (N,T)

Appraisal Note (A,N)

TexForm Note (T,N) (T,N)

Note Note (N,N)

time

page 1 page 2

Fig. 8.4. Partial connection structure for the trellis for model Eq. 8.2.

search . At each time step, it records the locally best path to each state. Due to the
independence of each time step, no locally suboptimal path can be part of the global
solution. We can use Viterbi search to establish the best sequence of document types
according to the model of Eq. 8.2. In fact, in the case of such a simple model, it
su ces to identify the best document type for each page, which automatically will
be a member of the best overall sequence. However, for any non-trivial model, this
is not the case.
The models according to Eq. 8.3 and Eq. 8.4 introduce context into the decision
process. This context or history needs to be reflected in the states of the trellis.
For instance, the states reflecting the model of Eq. 8.3 are annotated with pairs of
document types, the first one denoting the conditioning on the document type of
the previous page and the second one denoting the decision for the current page.
Moreover, the transition structure of the trellis needs to be modified as to ensure the
consistency of paths. For instance, a state marked with “Appraisal” as the current
decision can only be connected to following states that have “Appraisal” in their
history. Figure 8.4 shows part of the connection structure for the model according
to Eq. 8.3.
The extension of the context increases the number of states in a trellis. For the
model of Eq. 8.4, we use triples instead of pairs of document types as state names.
Model 8.6 describes pages in more detail, adding a page type (Start, Middle, End)
to the document type. Thus, for each document type relevant for a specific problem,
we would have three states in the trellis. In addition, the transition structure needs
to be carefully crafted as to only allow paths that describe complete documents,
i.e., follow Eq. 8.5. For instance, in order to be a valid document boundary, a state
associated with an end page must be immediately followed by a state associated
with a start page.
For reasons of simplicity and extensibility, it would be advantageous if these
sequence constraints could be formulated in isolation from the trellis containing the
classification results themselves. Pereira and Riley [16] show that speech recognition