Hidden Markov Models for Text Categorization in Multi-Page Documents.
In the traditional setting, text categorization is formulated as a concept learning problem where each instance is a single isolated document. However, this perspective is not appropriate in the case of many digital libraries that offer as contents scanned and optically read books or magazines. In this paper, we propose a more general formulation of text categorization, allowing documents to be organized as sequences of pages. We introduce a novel hybrid system specifically designed for multi-page text documents. The architecture relies on hidden Markov models whose emissions are bag-of-words resulting from a multinomial word event model, as in the generative portion of the Naive Bayes classifier. The rationale behind our proposal is that taking into account contextual information provided by the whole page sequence can help disambiguation and improves single page classification accuracy. Our results on two datasets of scanned journals from the Making of America collection confirm the importance of using whole page sequences. The empirical evaluation indicates that the error rate (as obtained by running the Naive Bayes classifier on isolated pages) can be significantly reduced if contextual information is incorporated.
Figure

1. Bayesian network for the Naive Bayes classifier.
2.2. Hidden Markov models
HMMs have been introduced several years ago as a tool for probabilistic sequence modeling.
The interest in this area developed particularly in the Seventies, within the speech recognition
research community (Rabiner, 1989). During the last years a large number of variants
and improvements over the standard HMM have been proposed and applied. Undoubt-
edly, Markovian models are now regarded as one of the most significant state-of-the-art
approaches for sequence learning. Besides several applications in pattern recognition and
molecular biology, HMMs have been also applied to text related tasks, including natural
language modeling (Charniak, 1993) and, more recently, information retrieval and extraction
(Freitag and McCallum, 2000; McCallum et al., 2000). The recent view of the HMM as
a particular case of Bayesian networks (Bengio and Frasconi, 1995; Lucke, 1995; Smyth et
al., 1997) has helped their theoretical understanding and the ability to conceive extensions
to the standard model in a sound and formally elegant framework.
An HMM describes two related discrete-time stochastic processes. The first process pertains
to hidden discrete state variables, denoted Xt , forming a first-order Markov chain
and taking realizations on a finite set {x1,.,xN }. The second process pertains to observed
variables or emissions, denoted Dt . Starting from a given state at time 0 (or given
an initial state distribution P(X0)) the model probabilistically transitions to a new state
X1 and correspondingly emits observation D1. The process is repeated recursively until
an end state is reached. Note that, as this form of computation may suggest, HMMs are
closely related to stochastic regular grammars (Charniak, 1993). The Markov property
prescribes that Xt+1 is conditionally independent of X1,.,Xt1 given Xt . Furthermore,
it is assumed that Dt is independent of the rest given Xt . These two conditional
independence assumptions are graphically depicted using the Bayesian network of
figure 2. As a result, an HMM is fully specified by the following conditional probability
P(Xt | Xt1) (transition distribution)
(2)
P(Dt | Xt ) (emission distribution)
Since the process is stationary, the transition distribution can be represented as a square
stochastic matrix whose entries are the transition probabilities
abbreviated as P(xi | x j ) in the following. In the classic literature, emissions are restricted
HIDDEN MARKOV MODELS 199

Figure

2. Bayesian networks for standard HMMs.
to be symbols in a finite alphabet or multivariate continuous variables (Rabiner, 1989). As
explained in the next section, our model allows emissions to be bag-of-words.
3. The multi-page classifier
We now turn to the description of our classifier for multi-page documents. In this case the
categorization task consists of learning from examples a function that maps the whole document
sequence d1,.,dT into a corresponding sequence of page categories, c1,.,cT .
This section presents the architecture and the asociated algorithms for grammar extraction,
training, and classification.
3.1. Architecture
The system is based on an HMM whose emissions are associated with entire pages of the
document. Thus, the realizations of the observation Dt are bag-of-words representing the
text in the t-th page of the document. HMM states are related to pages categories by a
deterministic function  that maps state realizations into page categories. We assume that
is a surjection but not a bijection, i.e. that there are more state realizations than categories.
This enriches the expressive power of the model, allowing different transition behaviors for
pages of the same class, depending on where the page is actually encountered within the
sequence. However, if the page contents depends on the category but not on the context of
the category within the sequence,5 multiple states may introduce too many parameters and
it may be convenient to assume that
P(Dt | xi
This constrains emission parameters to be the same for a given page category, a form of
parameters sharing that may help to reduce overfitting. The emission distribution is modeled
by assuming conditional word independence given the class, like in Eq. (1):
|dt |
P(dt | ck . (4)
Therefore, the architecture can be graphically described as the merging of the Bayesian
networks for HMMs and Naive Bayes, as shown in figure 3. We remark that the state (and
200 FRASCONI ET AL.

Figure

3. Bayesian network describing the architecture of the sequential classifier.
hence the category) at page t depends not only on the contents of that page, but also on
the contents of all other pages in the document, summarized into the HMM states. This
probabilistic dependency implements the mechanism for taking contextual information into
account.
The algorithms used in this paper are derived from the literature on Markov models
(Rabiner, 1989), inference and learning in Bayesian networks (Pearl, 1988; Heckerman,
1997; Jensen, 1996) and classification with Naive Bayes (Lewis and Gale, 1994; Kalt,
1996). In the following we give details about the integration of all these methods.
3.2. Induction of HMM topology
The structure or topology of an HMM is a representation of the allowable transitions
between hidden states. More precisely, the topology is described by a directed graph whose
vertices are state realizations {x1,.,xN }, and whose edges are the pairs
An HMM is said to be ergodic if its transition graph is fully-connected.

However, in almost all interesting application domains, less connected structures are better
suited for capturing the observed properties of the sequences being modeled, since they
convey domain prior knowledge. Thus, starting from the right structure is an important
problem in practical Hidden Markov modeling. As an example, consider figure 4, showing
a (very simplified) graph that describes transitions between the parts of a hypothetical set
of books. Possible state realizations are {start, title, dedication, preface, toc, regular, index,
end} (note that in this simplified example  is a one-to-one mapping).

Figure

4. Example of HMM transition graph.
HIDDEN MARKOV MODELS 201
While a structure of this kind could be hand-crafted by a domain expert, it may be more
advantageous to learn it automatically from data. We now briefly describe the solution
adopted to automatically infer HMM transition graphs from sample multi-page documents.
Let us assume that all the pages of the available training documents are labeled with the
class they belong to. One can then imagine to take advantage of the observed labels to
search for an effective structure in the space of HMMs topologies. Our approach is based
on the application of an algorithm for data-driven model induction adapted from previous
works on construction of HMMs of text phrases for information extraction (McCallum et al.,
2000). The algorithm starts by building a structure that can only explain the available
training sequences (a maximally specific model). This initial structure has as many paths
(from the initial to the final state) as there are training sequences. Every path is associated
with one sequence of pages, i.e. a distinct state is created for every page in the training set.
Each state x is labeled by (x), the category of the corresponding page in the document.
Note that, unlike the example shown in figure 4, several states are generated for the same
category. The algorithm then iteratively applies merging heuristics that collapse states so
as to augment generalization capabilities over unseen sequences. The first heuristic, called
neighbor-merging, collapses two states x and x if they are neighbors in the graph and
(x). The second heuristic, called V-merging, collapses two states x and x if
they share a transition from or to a common state, thus reducing the
branching factor of the structure.
3.3. Inference and learning
Given the HMM topology extracted by the algorithm described above, the learning problem
consists of determining transition and emission parameters. One important distinction that
needs to be made when training Bayesian networks is whether or not all the variables are
observed. Assuming complete data (all variables observed), maximum likelihood estimation
of the parameters could be solved using a one-step algorithm that collects sufficient statistics
for each parameter (Heckerman, 1997). In our case, data are complete if and only if the
following two conditions are met:
1. there is a one-to-one mapping between HMM states and page categories (i.e.
and for
2. the category is known for each page in the training documents, i.e. the dataset consists
of sequences of pairs ({d1, c1},.,{dT , cT }), being ct the (known) category of page t
and being T the number of pages in the document.
Under these assumptions, estimation of transition parameters is straightforward and can be
accomplished as follows:
where N(ci, cj ) is the number of times a page of class ci follows a page of class cj in the
trainingset.Similarly,estimationofemissionparametersinthiscasewouldbeaccomplished
exactly like in the case of the Naive Bayes classifier (see, e.g. Mitchell (1997)):
P(w |
where N(w, ck) is the number of occurrences of word w in pages of class ck and |V | is the
vocabulary size (1/|V | corresponds to a Dirichlet prior over the parameters (Heckerman,
1997) and plays a regularization role for whose words which are very rare within a class).
Conditions 1 and 2 above, however, are normally not satisfied. First, in order to model
more accurately different contexts in which a category may occur, it may be convenient to
have multiple distinct HMM states for the same page category. This implies that page labels
do not determine a unique state path. Second, labeling pages in the training set is a time
consuming process that needs to be performed by hand and it may be important to use also
unlabeled documents for training (Joachims, 1999; Nigam et al., 2000). This means that
label c may be not available for some t. If assumption 2 is satisfied but assumption 1 is not,
we can derive the following approximated estimation formula for transition parameters:
where N(xi, x j )counts how many times state xi follows x j during the state merge procedure
described in Section 3.2. However, in general, the presence of hidden variables requires an
iterative maximum likelihood estimation algorithm, such as gradient ascent or expectation-maximization
(EM). Our implementation uses the EM algorithm, originally formulated
in Dempster et al. (1977) and usable for any Bayesian network with local conditional
probability distributions belonging to the exponential family (Heckerman, 1997). Here the
EM algorithm essentially reduces to the Baum-Welch form (Rabiner, 1989) with the only
modification that some evidence is entered into state variables. Since multiple states are
associated with a category and even for labeled documents only the page category is known,
state evidence takes the form of findings (Jensen, 1996). State evidence is taken into account
in the E-step by changing forward propagation as follows:
ct

where
.
is the forward variable in the Baum-Welch algorithm. The emission probability P(dt
is obtained from Eq. (4), using ck
TheM-stepisperformedinthestandardwayfortransitionparameters,byreplacingcounts
in Eq. (5) with their expectations given all the observed variables. Emission probabilities
HIDDEN MARKOV MODELS 203
are also estimated using expected word counts. If parameters are shared as indicated in
Eq. (3), these counts should be summed over states having the same label. Thus, in the case
of incomplete data, Eq. (6) is replaced by
P(w | ck)

where S is the number of training sequences, N(w, ck) is the number of occurrences of
word w in pages of class ck and P(Xt = xi | d1,.,dT ) is the probability of being in state
xi at page t given the observed sequence of pages d1 .dT . Readers familiar with HMMs
should recognize that the latter quantity can be computed by the Baum-Welch procedure
during the E-step. The sum on p extends over training sequences, while the sum on t extends
over pages of the p-th document in the training set. The E- and M-steps are iterated until a
local maximum of the (incomplete) data likelihood is reached.
Note that if page categories are observed, it is convenient to use the estimates computed
with Eq. (7) as a starting point, rather than using random initial parameters. Similarly, an
initial estimate of the emission parameters can be obtained from Eq. (6).
It is interesting to point out a related application of the EM algorithm for learning from
labeled and unlabeled documents (Nigam et al., 2000). In that paper, the only concern was
to allow the learner to take advantage of unlabeled documents in the training set. As a major
difference, the method in Nigam et al. (2000) assumes flat single-page documents and, if
applied to multi-page documents, would be equivalent to a zero-order Markov model that
cannot take contextual information into account.
3.4. Page classification
Given a document of T pages, classification is performed by first computing the sequence
of states x1,.,xT that was most likely to have generated the observed sequence of pages,
and then mapping each state to the corresponding category (xt ). The most likely state
sequence can be obtained by running an adapted version of Viterbi's algorithm, whose
more general form is the max-propagation algorithm for Bayesian networks described in
Jensen (1996). Briefly, the following quantity
is computed using the following recursion:

204 FRASCONI ET AL.
The optimal state sequence is then retrieved by backtracking:
Finally, categories are obtained as ct = (xt ). By contrast, note that the Naive Bayes clas-
sifier would compute the most likely categories as
ct
Comparing Eqs. (11)-(15) to Eq. (16) we see that both classifiers rely on the same emission
model P(dt | cj ) but while Naive Bayes employs the prior class probability to compute its
final prediction, the HMM classifier takes advantage of a dynamic term (in square brackets
in Eq. (12)) that incorporates grammatical constraints.
4. Experimental results
In this section, we describe a set of experiments that give empirical evidence of the effectiveness
of the proposed model. The main purpose of our experiments was to make a
comparison between our multi-page classification approach and a traditional isolated page
classification system, like the well known Naive Bayes text classifier. The evaluation has
been conducted over real-world documents that are naturally organized in the form of page
sequences. We used two different datasets associated with two journals in the Making of
America (MOA) collection. MOA is a joined project between the University of Michigan
and Cornell University (see http:/moa.umdl.umich.edu/about.html and Shaw and
Blumson (1997)) for collecting and making available digitized information about history
and evolution processes of the American society between the XIX and the XX century.
4.1. Datasets
The first dataset is a subset of the journal American Missionary, a sociological magazine
with strong Christian guidelines. The task consists of correctly classifying pages of previously
unseen documents into one of the ten categories described in Table 1. Most of these
categories are related to the topic of the articles, but some are related to the parts of the
journal (i.e. Contents, Receipts, and Advertisements). The dataset we selected contains 95
issues from 1884 to 1893, for a total of 3222 OCR text pages. Special issues and final report
issues (typically November and December issues) have been removed from the dataset as
they contain categories not found in the rest. The ten categories are temporally stable over
the
The second dataset is a subset of Scribners Monthly, a recreational and cultural magazine
printed in the second half of the XIX century. Table 2 describes the categories we have
selected for this classification task. The filtered dataset contains a total of 6035 OCR text
pages, organized into issues ranging from year 1870 to 1875. Although spanning a shorter
temporal interval, the number of pages in this second dataset is larger than in the first one
because issues are about 3-4 times longer.
HIDDEN MARKOV MODELS 205

Table

1. Categories in the American Missionary domain.
Name Description
Cover and index of surveys
Editorial articles
Afro-Americans' surveys
American Indians' surveys
Reports from China missions
Articles about female condition
Education and childhood
Magazine information
Lists of founders
Contents is mostly graphic, with little text description

Table

2. Categories in the Scribners Monthly domain.
Name Description
1. Article
2. Books and Authors at Home and Abroad
Generic articles
Book reviews
Broad cultural news
Poems or tales
Articles on home living
Scientific articles
Articles on fine arts
News reports
Category labels for the two datasets were obtained semi-automatically, starting from the
MOAXMLfilessuppliedwiththedocumentscollections.Theassignedcategorieswerethen
manually checked. In the case of a page containing the end and the beginning of two articles
belonging to different categories, the page was assigned the category of the ending article.
Each page within a document is represented as a bag-of-words, counting the number of
word occurrences within the page. It is worth remarking that in both datasets, instances
are text documents output by an OCR system. Imperfections of the recognition algorithm
and the presence of images in some pages yields noisy text, containing misspelled or
nonexistent words, and trash characters (see Bicknese (1998) for a report of OCR accuracy
in the MOA digital library). Although these errors may negatively affect the learning process
and subsequent results in the evaluation phase, we made no attempts to correct and filter out
misspelledwords,exceptforthefeatureselectionprocessdescribedinSection4.3.However,
since OCR extracted documents preserve the text layout found in the original image, it was
necessary to rejoin word fragments that had been hyphenated due to line breaking.
206 FRASCONI ET AL.
4.2. Grammar induction
In the case of completely labeled documents, it is possible to run the structure learning
algorithm presented in Section 3.2. In figure 5 we show an example of induced HMM
topology for the journal The American Missionary. This structure was extracted using 10
issues (year 1884) as a training set. Each vertex in the transition graph is associated with one
HMM state and is labeled with the corresponding category index (see Table 1). Edges are
labeled with the transition probability from source to target state, estimated in this case by
counting state transitions during the state merging procedure (see Eq. (7)). These values are
also used as initial estimates of P(xi |x j )and subsequently refined by the EM algorithm. The
associated stochastic grammar implies that valid sequences must start with the index page
(class 1), followed by a page of general communications (class 8). Next state is associated
with a page of an editorial article (2). Self transition here has a value of 0.91, meaning that
with high probability the next page will belong to the editorial too. With lower probability
(0.07) next page is one of The South survey (3) or (probability 0.008) The Indians (4)
or Bureau of Women's work (6).
In figure 6 we show one example of induced HMM topology for journal Scribners
Monthly,obtainedfrom12trainingissues(year1871).AlthoughissuesofScribnersMonthly
are longer and the number of categories is comparable to those in the American Missionary,
the extracted transition diagram in figure 6 is simpler than the one in figure 5. This reflects
less variability in the sequential organization of articles in Scribners Monthly. Note that
category 7 (Home and Society) is rare and never occurs in 1871.
4.3. Feature selection
Text pages were first preprocessed with common filtering algorithms including stemming
and stop words removal. Still, the bag-of-words representation of pages leads to a very
high-dimensional feature space that can be responsible of overfitting in conjunction to algorithms
based on generative probabilistic models. Feature selection is a technique for
limiting overfitting by removing non-informative words from documents. In our experi-
ments, we performed feature selection using information gain (Yang and Pedersen, 1997).
This criterion is often employed in different machine learning contexts. It measures the
average number of bits of information about the category that are gained by including a
word in a document. For each dictionary term w, the gain is defined as
K K
P(ck | w)log P(ck | w)
where w denotes the absence of word w. Feature selection is performed by retaining only the
words having the highest average mutual information with the class variable. OCR errors,
however, can produce very noisy features which may be responsible of poor performance
HIDDEN MARKOV MODELS 207

Figure

5. Data induced HMM topology for American Missionary, year 1884. Numbers in each node correspond
208 FRASCONI ET AL.

Figure

6. Data induced HMM topology for Scribners Monthly, year 1871. Numbers in each node correspond to
HIDDEN MARKOV MODELS 209
even if feature selection is performed. For this reason, it may be convenient to prune from
the dictionary (before applying the information gain criterion) all the words occurring less
than a given threshold h in the training set. Preliminary experiments showed that best
performances are achieved by pruning words having less than occurrences.
4.4. Accuracy comparisons
In the following we compare isolated page classification (using standard Naive Bayes) to
sequential classification (using the proposed HMM architecture). Although classification
accuracy could be estimated by fixing a split of the available data into a training and a
test set, here we suggest a method that attempts to incorporate some peculiarities of digital
libraries domain. In particular, hand-labeling of documents for the purpose of training is
a very expensive activity and working with large training sets is likely to be unrealistic
in practical applications. For this reason, in most experiments we deliberately used small
fractions of the available data for training.
Moreover, there is a problem of temporal stability as the journal organization may change
over time. In our test we attempted to address this aspect by assuming that training data is
available for a given year and we decided to test generalization over journal issues published
in different years. Splitting according to publication year can be an advantage for the training
algorithm since it increases the likelihood that different issue organizations are represented
in the training set.
The resulting method is related to k-fold cross-validation, a common approach for accuracy
estimation that partitions the dataset into k subsets and iteratively use one subset for
testing and the other k  1 for training. In our experiments we reversed the proportions of
data in the training and test sets, using all the journal issues in one year for training, and
the remaining issues for testing. We believe that this setting is more realistic in the case of
digital libraries.
In the following experiments, the HMM classifiers were trained by first extracting the
transition structure, then initializing the parameters using Eqs. (6) and (7), and finally tuning
the parameters using the EM algorithm. We found that the initial parameter estimates are
very close to the final solution found by the EM algorithm. Typically, 2 or 3 iterations are
sufficient for EM to converge.
4.4.1. American Missionary dataset. The results of the ten resulting experiments are
shown in figure 7. The hybrid HMM classifier (performing sequential classification) consistently
outperforms the plain Naive Bayes classifier working on isolated pages. The graph
on the top summarizes results obtained without feature selection. Averaging the results over
all the ten experiments, NB achieves 61.9% accuracy, while the HMM achieves 80.4%. This
corresponds to a 48.4% error rate reduction. The graph on the bottom refers to results obtained
by selecting the best 300 words according to the information gain criterion. The
average accuracy in this case is 69.8% for NB and 80.6% for the HMM (a 35.7% error
rate reduction). In both cases, words occurring less than 10 times in their training sets were
pruned. When using feature selection, NB improves while the HMM performance is essentially
the same. Moreover, the standard deviation of the accuracy is smaller for NB (2.8%,
compared to 4.2% for the HMM). The larger variability in the case of the HMM is due to

Figure

7. Isolated vs. sequential page classification on the American Missionary dataset. For each column,
classifiers are trained on documents of the corresponding year and tested on all remaining issues.
the structure induction algorithm. In facts, the sequential organization of journal issues is
temporally less stable than article contents.
4.4.2. Scribners Monthly dataset. Similar experiments have been carried out on the Scrib-
ners Monthly journal. Results using no feature selection are shown on the top of figure 8. The
average accuracy is 81.0%, for isolated page classification and 89.6% for sequential classi-
fication (the error reduction is 42.5%). After feature selection, the average accuracy drops
to 75.3% for the isolated page classifier, while it remains similar for the sequential classifier.
HIDDEN MARKOV MODELS 211

Figure

8. Isolated vs. sequential page classification on the Scribners Monthly dataset.
Noticeably, feature selection has different effects on the two datasets when coupled with
the Naive Bayes classifier: it tends to improve accuracy for the American Missionary and
tends to worsen for the Scribners Monthly. On the other hand, the HMM is almost insensitive
to feature selection, in both datasets. This is apparently counterintuitive since the emission
model is almost the same for the two classifiers (except for the EM tuning of emission
parameters in the case of the HMM). However, it should be remarked that the Naive Bayes'
final prediction is biased by the class prior (Eq. (16)) while the HMM's prediction is biased
by extracted grammar (Eqs. (11)-(15)). The latter provides more robust information that
effectively compensates for the crude approximation in the emission model, prescribing
212 FRASCONI ET AL.
conditional word independence. This robustness also affects positively performance if a
suboptimal set of features is selected for representing document pages.
4.5. Learning using ergodic HMMs
The following experiments provide a basis for evaluating the effects of the structure learning
algorithm presented in Section 3.2. In the present setting, we trained an ergodic HMM with
ten states (each state mapped to exactly one class). Emission parameters were initialized
using Eq. (6) while transition probabilities were initialized with random values. In this case
the EM algorithm takes the full responsibility for extracting sequential structure from data.
After training, arcs with associated probability less than 0.001 were pruned away.
The evaluation was performed using the American Missionary dataset, training on single
years as in the previous set of experiments. As expected (see figure 9), results are worse
than those obtained in conjunction with the grammar extraction algorithm. However, the
trained HMM outperforms the Naive Bayes classifier also in this case.
4.6. Effects of the training set size
To investigate the effects of the size of the training set we propose a set of experiments
alternative to those reported in Section 4.4. In these experiments we selected a variable
number of sequences (journal issues) n for training (randomly chosen in the dataset) and
tested generalization on all the remaining sequences. The accuracy is then reported as a
function of n, after averaging over 20 trials (each trial with the same proportion of training
and test sequences). All these experiments were performed on the American Missionary
dataset. As shown in figure 10, generalization for both the isolated and the sequential
classifier tends to saturate after about 15 sequences in the training set. This is slightly more

Figure

9. Comparison between the ergodic HMM and the HMM based on the extracted grammar.
HIDDEN MARKOV MODELS 213

Figure

10. Learning curve for the sequential and the isolated classifiers.
than the average number of issues in a single year. The sequential classifier consistently
outperforms the isolated page classifier.
4.7. Learning with partially labeled documents
Since labeling is an expensive human activity, we evaluated our system also when only
a fraction of the training documents pages are labeled. In particular, we are interested in
measuring the loss of accuracy due to missing page labels. Since structure learning is not
feasible with partially labeled documents, we used in this case an ergodic (fully connected)
HMM with ten states (one per class).
We have performed six different experiments on the American Missionary dataset, using
different percentages of labeled pages. In all the experiments, all issues of year 1884 form
the training set and the remaining issues form the test set. Table 3 shows detailed results of
the experiment. Classification accuracy is reported for single classes and for the entire test
set. Using 30% of labeled pages the HMM fails to learn a reliable transition structure and the
Naive Bayes classifier (trained with EM as in Nigam et al. (2000)) obtains higher accuracy

Table

4). However, with higher percentages of known page labels the comparison favors
again the sequential classifier. Using only 50% of labeled pages, the HMM outperforms the
isolated page classifier that was trained on completely labeled data. With greater percentages
of labeled documents, performances begin to saturate reaching a maximum of 80.24% when
all the labels are known (this corresponds to the result obtained in Section 4.5).
5. Conclusions
We have presented a text categorization system for multi-page documents which is capable
of effectively taking into account contextual information to improve accuracy with
respect to traditional isolated page classifiers. Our method can smoothly deal with unlabeled
pages within a document, although we have found that learning the HMM structure further
214 FRASCONI ET AL.

Table

3. Results achieved by the model trained by Expectation-Maximization, varying percentage of labeled
documents.
Percentage of labeled documents
Category
Another aspect is the granularity of document structure being exploited. Working at
the level of pages is straightforward since page boundaries are readily available. However,
actual category boundaries may not coincide with page boundaries. Some pages may contain
portions of text belonging to different articles (in this case, the page would belong to
multiple categories). Although this is not very critical for single-column journals such as
the American Missionary, the case of documents typeset in two or three columns certainly
deservesattention.Afurtherdirectionofinvestigationisthereforerelatedtothedevelopment
of algorithms capable of performing automatic segmentation of a continuous stream of text,
without necessarily relying on page boundaries.
Finally, text categorization methods that take document structure into account may be extremely
useful for other types of documents natively available in electronic form, including
web pages and documents produced with other typesetting systems. In particular, hypertexts
(like most documents in the Internet) are organized as directed graphs, a structure that can be
seen as a generalization of sequences. However, devising a classifier that can capture context
inhypertextsbyextendingthearchitecturedescribedinthispaperisstillanopenproblem:al-
though the extension of HMMs from sequences to trees is straightforward (see e.g. Diligenti
etal.(2001)),thegeneralcaseofdirectedgraphsisdifficultbecauseofthepresenceofcycles.
Preliminary research in this direction (based on simplified models incorporating graphical
transition structure) is presented in Diligenti et al. (2000) and Passerini et al. (2001).

Acknowledgments

We thank the Cornell University Library for providing us data collected within the Making
of America project. This research was partially supported by EC grant # IST-1999-20021
under METAe project.
Notes
1. A related formulation would consist of assigning a global category to a whole multi-page document, but this
formulation is not considered in this paper.
2. After observing the text.
3. A Bayesian network is an annotated graph in which nodes represent random variables and missing edges
encode conditional independence statements amongst these variables. Given a particular state of knowledge,
the semantics of belief networks determine whether collecting evidence about a set of variables does modify
one's belief about some other set of variables (Jensen, 1996; Pearl, 1988).
4. We adopt the standard convention of denoting variables by uppercase letters and realizations by the corresponding
lowercase letters. Moreover, we use the table notation for probabilities as in Jensen (1996); for example
P(X) is a shorthand for the table denotes the two-dimensional
table with entries
5. Of course this does not mean that the category is independent of the context.


--R

An Input Output HMM Architecture.
Bayesian Networks dor Data Mining.
An Introduction to Bayesian Networks.
Text Categorization with Support Vector Machines: Learning with Many Relevant Fea- tures
Transductive Inference for Text Classification using Support Vector Machines.
An Experimental Evaluation of OCR Text Representations for Learning Document Classifiers.
A New Probabilistic Model of Text Classification and Retrieval.
Hierarchically Classifying Documents using Very Few Words.
A Sequential Algorithm for Training Text Classifiers.
Comparison of Two Learning Algorithms for Text Categorization.
Bayesian Belief Networks as a Tool for Stochastic Parsing.
Automating the Construction of Internet Portals with Machine Learning.
Machine Learning.
Feature Selection
Text Classification from Labeled and Unlabeled Documents using EM.
Evaluation Methods for Focused Crawling.
Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference.
A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition.
Online Searching and Page Presentation at the University of Michigan.
Probabilistic Independence Networks for Hidden Markov Probability Models.
Hidden Markov Model Induction by Bayesian Model Merging.
An Example-Based Mapping Method for Text Classification and Retrieval
A Comparative Study on Feature Selection in Text Categorization.
--TR
Probabilistic reasoning in intelligent systems: networks of plausible inference
An example-based mapping method for text categorization and retrieval
A sequential algorithm for training text classifiers
Bayesian Belief Networks as a tool for stochastic parsing
Probabilistic independence networks for hidden Markov probability models
Feature selection, perception learning, and a usability case study for text categorization
Text Classification from Labeled and Unlabeled Documents using EM
Statistical Language Learning
Machine Learning
Introduction to Bayesian Networks
Bayesian Networks for Data Mining
Automating the Construction of Internet Portals with Machine Learning
Text Categorization with Suport Vector Machines
Hierarchically Classifying Documents Using Very Few Words
A Comparative Study on Feature Selection in Text Categorization
Transductive Inference for Text Classification using Support Vector Machines
Hidden Markov Model} Induction by Bayesian Model Merging
Focused Crawling Using Context Graphs
Image Document Categorization Using Hidden Tree Markov Models and Structured Representations
Information Extraction with HMM Structures Learned by Stochastic Optimization
Evaluation Methods for Focused Crawling
A New Probabilistic Model of Text Classification and Retrieval TITLE2:

--CTR
Fabrizio Sebastiani, Machine learning in automated text categorization, ACM Computing Surveys (CSUR), v.34 n.1, p.1-47, March 2002
text categorization;hidden Markov models;multi-page documents;naive bayes;digital libraries