Using a Bayesian Network Induction Approach for Text Categorization

1 Introduction

Document categorization has become an important area in information retrieval and gathering. The objective of document categorization is to assign categories to a document. The categories are drawn from a set of pre­ specified categories. It is possible to assign multiple cat­ egories to a document if they are appropriate. A doc­ ument here refers to a piece of text. Traditionally this categorization task is performed manually by domain ex­ perts. Each incoming document has to be read and com­ prehended by an expert who assigns its categories. Ob­ viously a large amount of human resources are required to carry out such categorization tasks. For instance, the OHSUMED document collection, composed of medical journal articles, requires a large amount of resources for manual categorization [Hersh et al., 1994].

A promising way to solve this problem is to automati­ cally categorize documents based on their content. This can be achieved by learning a categorization scheme from a set of training examples. This problem can be viewed as a machine learning problem where an element may be classified into multiple category labels. Recently, some work has been done on this problem [Apte et al., 1994;

Lewis et al., 1996; Yang, 1994; Larkey and Croft, 1996]. We present a new approach based on a Bayesian network induction. We show that it relaxes some major assump­ tions found in a previous approach based on the Bayesian independence classifiers [Lewis, 1992]. In this paper, the basic idea of the Bayesian independence classifier ap­ proach is first reviewed. We then introduce our approach for inducing Bayesian networks. We also contrast its relationship to the Bayesian independence classifier ap­ proach. Experiments were conducted using a large-scale document collection concerning with economic and fi­ nancial news articles form Reuters. The results show that our approach outperformed the Bayesian indepen­ dence classifier as measured by a metric that combines precision and recall measures.

2 Bayesian Independence Classifier Approach

In order to handle multiple category assignments , a sep­ arate classifier is constructed for each category. Each classifier is then used to determine whether a given doc­ ument should be assigned to this category. This yields a set of categories for each document .

Lewis [Lewis , 1992] used a Bayesian approach for text categorization problems. Suppose we need to build a classifier for a particular category. Let the random vari­ able Cj denote the membership ofa document in the j-th category and it can take on binary values 0 and 1. Let d be an incoming document to be categorized. According to Bayes theorem,

To represent document d, we use a vector ~ of cho­ sen predictor terms (Til , . .. , Tip). Each term usually represents a particular word. Note that we may use different terms to represent the same document under different categories. Each predictor term can take on bi­ nary values 0 and 1 denoting absence or presence of the corresponding word in a document. Hence, Equation 1 becomes:

Suppose the value of each term in vector ~ is (th , .. . , tjp) . Equation 2 can be expressed as:

This formula requires estimates for the joint proba­ bilities P(Tj 1 = th, ... , Tjp = tjp I Cj = 1) and P(Th = tjp ... , Tjp = tjp ). Typically these probabili­ ties are difficult to estimate from the training examples.

To overcome this problem, the following two assump­ tions are usually made regarding the marginal and .. con­ ditional independence of predictor terms as follows:

and

Substituting Equations 4 and 5 into Equation 3, we get:

Ideally, we would like a feature term which is strongly related to the ideas that is conveyed by the document. Sometimes the word appears in the document and we can of course assign it as a predictor feature. However, it is also possible that the word does not appear in a docu­ ment and the term may still relate to the ideas conveyed by the document. We are therefore not sure whether an index term should be assigned to a document . To incor­ porate this kind of uncertainty, the probability P(~ I d) is introduced to indicate how close ~ is to the ideal in­ dexing of the document. Each element Tj, in ~ can have binary values 0 or 1. Instead of directly estimating P(Cj = 1 I d) as in Equation 1, we need to consider P(~ I d). Hence the formula for P(Cj = 1 I d) is modi­ fied as follows :

Applying Bayes' Theorem, we get

In order to compute the above expression, the indepen­ dence assumption in Equations 4 and 5 are still required. In addition, it requires the following assumption:

Substituting Equations 4, 5 and 8 into 7, we get:

To evaluate the expression in Equation 9, Lewis [Lewis, 1992] developed an approximation as follows:

3 Bayesian Network Approach

A major assumption in the Bayesian independence clas­ sifiers is that the features are marginally independent as well as conditionally independent to Cj or d. This as­ sumption is used to estimate those high order probabili­ ties such asP(~) , P(~ I Cj), and P(~ I Cj) as shown in Equations 4, 5, and 8. The accuracy of these esti­ mations directly affect the performance of the classifier. Poor estimation will probably not result in good classifi­ cation performance. In our text categorization problem, it is likely that the predictor terms are not independent. We develop a new approach based on a Bayesian network induction that eliminates this assumption.

A Bayesian network consists of nodes and arcs con­ nected together to form a directed acyclicgraph. Each node represents a variable that can take on a discrete set of domain-specific states. Each (directed) arc repre­ sents a probabilistic dependency between the source and destination variables.

The idea is to learn a Bayesian network for the set of variables representing the predictor terms ~ as well as the category Cj . The network provides a means for us to exploit the inherent dependency among these variables . Instead of relying on estimating high order probabilities as described above, we can compute P(Cj = 1 I~) di­ rectly from the Bayesian network which already encodes the dependencies among the terms in ~ as well as the category Ci .

Apart from an acyclic graph structure, a Bayesian net­ work consists of a set of conditional probability parame­ ters associated with each node in the network. Suppose X denotes a node representing one of the domain vari­ ables in a Bayesian network. Let Y x be the set of parents of node X in the network structure (i.e., there is a di­ rected arc from each node in Y x pointing to X). There is a conditional probability distribution P(X I Y x) asso­ ciated with X. If X does not have parents in the network structure, there is a prior probability distribution P(X) associated with X.

After the network is constructed, it can be used for conducting reasoning. A common and useful kind of rea­ soning is to perform probabilistic inferences. In a typical scenario, the states of some variables are observed. We are interested in calculating the posterior probability dis­ tribution of some other variables given the instantiation of the observed variables.

To use Bayesian networks as classifiers in our text cat­ egorization problem, we first construct a Bayesian net­ work for variables in {Ci} U ~ (i.e., {Cj, Til, . .. , Tip}). Machine learning techniques can be used to automat­ ically construct a network from training documents. Once this network is constructed, it can be used to categorize documents, using probabilistic inferences on the network. More specifically, the feature variables representing the document (i.e., variables in ~) are instantiated appropriately. The posterior probability P(Ci = 1 I ~) is then computed. The document will be determined as being assigned to the category if this probability value exceeds a certain threshold. The main advantage of this approach over the Bayesian indepen­ dence classifier is that it relaxes those assumptions re­ garding feature independence. . The network structure can capture the inherent dependency during the induc­ tion process.

The next issue is how to learn a Bayesian network from the training documents. There has been some research on learning Bayesian networks from data [Heckerman et al., 1995; Spirtes and Meek, 1995; Lam and Bacchus, 1994]. It is well known that learning arbitrary networks is quite computationally expensive. Since our purpose is to make use of the network for classification, we re­ strict our consideration to a family of network structures known as classification-based network structures. This can reduce the learning complexity considerably and at the same time achieve our objective for performing clas­ sification. A classification-based network structure isba­ sically an arbitrary Bayesian network structure with the restriction that Ci has no parents (i.e., Ycj = 0). Fig­ ure 1 shows an example of a classification-based net­ work structure. The rationale behind these structures is that the states of the feature variables may depend on the membership of the category, but not the other way around, if such dependencies exist. Bayesian networks have been adopted to build other classifiers [Friedman and Goldszmidt, 1996]. We focus on exploring Bayesian networks to solve large-scale document categorization problems and propose classification-based network struc­ tures to solve these tasks.

4 Automatic Construction of Bayesian Networks

To learn a Bayesian network from training examples, we make use of a technique based on the Minimum Descrip­ tion Length (MDL) principle derived from [Lam and Bac­ chus, 1994]. Central to this approach is a score metric for a candidate network structure, where the score met­ ric is a function representing the total description length, L(B), of a candidate network structure B.

The total description length is decomposed into a func­ tion Ltotai associated with each individual node in the network as follows:

where X is a node in the network. Ltotal of a node X depends only on its parent set. Hence, Ltotai is a constant if the parent set is fixed. The domain variables in our current categorization problem are { Ci} U ~ (i.e., { Ci, Til, ... , Tip}). The network structures we consider are classification-based network structures as described in Section 3. Thus, node Ci has a fixed set of parents, i.e., empty parent set. As a result, the score metric of a candidate network becomes:

The function Ltotal is composed of two components:

where Lnetwork and Ldata are called network description length and data description length respectively.

As described in [Lam and Bacchus, 1994], the network description length for a variable xi is given as follows:

where n is the number of variables. Sj is the number of possible states of variable Xi, and Q represents the number of bits required to store a numerical value.

This network description length has the property that the higher the topological complexity of the network the longer is its description length. It is widely recognized that conducting inference on highly-connected networks is likely to be intractable [Cooper, 1990], thus they are not very useful in practice. By minimizing this length function, we favor more useful networks, that is, those having simple topology.

For our categorization problem, there are p + 1 vari­ ables and each variable can take on binary values. Thus the network description length should be refined to:

Apart from the simplicity issue, we also need to con­ sider the accuracy issue which refers to how accurate a network structure represents the training data. The ac­ curacy issue is captured by the data description length as follows:

where the summation is taken over all possible instanti­ ations of that variable and its parents. M(.) is the num­ ber of cases that match a particular instantiation in the training data. The log function will be 0 if M (Tj,) = 0. It can be shown that this data description length has the property that the more accurate the network structure the shorter is the description length. By minimizing this length function, we favor accurate networks.

Simplicity and accuracy cannot usually be maximized simultaneously. Given a particular network structure, it will become more accurate if we increase its topological complexity appropriately. As a result, we are faced with a tradeoff between simplicity and accuracy. It is desir­ able to learn an accurate network, and at the same time the structure should be as simple as possible. The score metric Ltotai, based on the MDL measure, offers a prin­ cipled means to perform such tradeoff by considering the sum of the network description length Lnetwork and the data description length Ldata (note that both Lnetwork and Ldata are non-negative).

Within the framework, a shorter length Ltotal corre­ sponds to a better network. In this text categorization problem, we would like to find a classification-based net­ work which has the lowest Ltotal· In situations where an optimal solution cannot be obtained due to limited Sj computing resources, we wish to find a network with Ltotal as low as possible. To find a good structure, we employ a best-first search strategy guided by the MDL metric. The heuristic function of a candidate network is basically composed of the MDL metric of the network structure and the arc to be added to the network. When we generate a candidate network structure, we impose a restriction that an arc cannot direct from a node rep­ resenting a term to the node representing the category. Thus classification-based network structure topology can be maintained. This constraint increases the search ef­ ficiency because non-classification-based structures will be ignored during the search process.

5 Experimental Results

We have conducted experiments to demonstrate the per­ formance of our approach. We implemented our ap­ proach as well as the Bayesian independence classifier ap­ proach. Thus we can directly compare the performance of both approaches. The document collection used in this experiment are economic and financial news articles from Reuters. There are 22,173 full text documents in the corpus. We used 21,450 documents between Feb. 26 1987 and Oct. 20 1987 in our experiment. These texts vary in length from single line bulletins to multi-page articles. Each document is assigned to one or more cat­ egories of economic interest. We partitioned the corpus into training and testing collection in the same way as the experiment done in [Lewis, 1992]. The texts before Apr. 7 1987 belongs to the training collection while those after this date belongs to the testing collection. There are 14,704 and 6,746 documents in the training and test­ ing collection respectively. There are 112 categories in the training collection and the performance evaluation is based on these categories.

For each category, we select features based on the mu­ tual information gain of the candidate feature and the category. The mutual information of a term Ti and cat­ egory Ci is defined as:

After mutual information of each term is calculated, the terms are ranked in descending order of mutual infor­ mation and the top p terms are chosen as the predictor features for the category.

For the evaluation of our categorization system, the performance of each category is measured. The overall effectiveness is then computed by the mean performance across each category. Consider a particular category, the effectiveness of the categorization can be shown in a contingency table as follows:

where q is the number of documents belonging to the category and assigned to the category; r is the number of documents not belonging to the category and assigned to the category; s is the number of documents belonging to the category but not assigned to the category; t is the number of documents not belonging to the category and not assigned to the category.

Some common effectiveness measures can then be de­ fined in terms of these values:

(precision)S = qj(q + r)

Recall is the proportion of documents belonging to the category that the system successfully assigns to the cat­ egory. Precision is the proportion of documents assigned to the category by the system that really belong to the category. An ideal categorization system would have re­ call and precision equal to 1. However , perfect recall can be achieved by a system that puts every document in the category, while perfect precision can be achieved by a system that puts no documents in the category, so just using either recall or precision does not provide a fair evaluation to a system.

Therefore, an effectiveness measure called F measure, proposed by [Van Rijsbergen, 1979; Lewis et al., 1996], combines the recall and precision into a single score as follows :

j3 ranges from 0 to infinity. When j3 is 0, Ff3 is the same as the precision. When j3 equals to infinity, Ff3 is the same as recall. The variation of j3 between 0 and infinity corresponds to the variation of the weight to re­ call and precision. In our evaluation, /3 is set to 1 (i.e., equal weight on recall and precision) . After we compute all F1 values for each category, the mean F1 value across categories is computed so as to compute the overall eva!uation of our categorization system.

Table 1 shows the performance of the Bayesian inde­ pendence classifier approach and our Bayesian network approach measured using F1 for each category in the ex­ periment. The mean F1 measure of the Bayesian inde­ pendence classifier is 0.443 whereas the mean F1 measure of our Bayesian network induction approach is 0.542. Therefore, there is roughly a 22.3% improvement for our Bayesian network approach. There are 88 out of 112 categories where the performance of the Bayesian net­ work approach is the same or better than the Bayesian independence classifier approach.

We also investigate the sensitivity of the probabil­ ity threshold on the performance of the Bayesian net­ work approach. Figure 2 shows the performance of the Bayesian network approach when we varied the proba­ bility threshold.

6 Conclusion

Bayesian methods for automatic document categoriza­ tion are investigated in this paper. We first reviewed an existing technique based on the Bayesian independence classifier approach. After discussing its drawbacks, we introduced a new approach based on Bayesian networks. The theoretical justifications of our new approach is also described. Experiments were conducted using a large document collection from Reuters news articles. The re­ sults show that our approach outperformed the Bayesian independence classifier as measured by a metric that combines precision and recall measures.