Integrating Background Knowledge Into Text Classification

1 Using Background Knowledge

Supervised learning algorithms rely on a corpus of labeled training examples to produce accurate automatic text clas­ sifiers. An insufficient number of training examples often results in learned models that are suboptimal when classi­ fying previously unseen examples. Numerous different ap­ proaches have been taken to compensate for the lack of train­ ing examples. These include the use of unlabeled exam­ ples [Bennet and Demiriz, 1998; Blum and Mitchell, 1998; Nigam et al., 2000; Goldman and Zhou, 2000], the use of test examples [Joachims, 1999], and choosing a small set of spe­ cific unlabeled examples to be manually classified [Lewis and Gale, 1994].

Our approach does not assume the availability of either un­ labeled examples or test examples. As a result of the explo­ sion of the amount of data that is available, it is often the case that text, databases and other sources of knowledge that are related to the text classification task are readily available from the World Wide Web. We incorporate such "background knowledge" into different learners to improve classification of unknown instances. The use of external readily available textual resources allows learning systems to model the do­ main in a way that would be impossible by simply using a small set of training instances. For example, if a text classi­ fication task is to determine the sub-discipline of physics that a paper title should belong to, background knowledge such as abstracts, physics newsgroups, and perhaps even book re­ views of physics books can be used by learners to create more accurate classifiers.

Haym Hirsh

Rutgers University 110 Frelinghuysen Road Piscataway, NJ 08854 hirsh@ cs.rutgers.edu

We present three methods of incorporating background knowledge into the text classification task. Each of these methods uses the corpus of background knowledge in a dif­ ferent way, yet empirically, on a wide variety of text clas­ sification tasks we can show that accuracy on test sets can be improved when incorporating background knowledge into these systems. We ran all three methods incorporating back­ ground knowledge on a range of problems from nine differ­ ent text classification tasks. Details on the data sets can be found at (www.cs.csi.cuny.edurzelikovi/datasets; each var­ ied on the size of each example, the size of each piece of background knowledge, the number of examples and number of items of background knowledge, and the relationship of the background knowledge to the classification task.

2 Methods

In our first approach we use Naive Bayes and EM as in [Nigam et al., 2000]. We can substitute more general back­ ground knowledge for unlabeled examples, and obtain im­ provements in accuracy on text classifiers that are created us­ ing both the training set and the set of background knowledge. Naive Bayes classifiers make the assumption that examples (both labeled and unlabeled) have been generated by a mix­ ture model that has a one-to-one correspondence with classes. Even if this assumption is true for the labeled data and the test data, by its very nature, background knowledge should not fit this assumption at all. However, the interesting observation that we make is that to gain leverage out of unlabeled exam­ ples, the unlabeled data that we have need not be specifically and accurately unlabeled examples. As long as the vocabu­ lary and classification structure closely resembles the train­ ing/test data, background knowledge can improve classifica­ tion accuracy in textual data using the EM algorithm.

A second approach that we take is based upon a near­ est neighbor text classifier using WHIRL [Cohen, 1998; Cohen and Hirsh, 1998]. Instead of simply comparing a test example to the corpus of training examples, we use the items of background knowledge as "bridges" to connect each new example with labeled training examples. A labeled training example is useful in classifying an unknown test instance if there exists some set of unlabeled background know ledge that is similar to both the test example and the training example. We call this a "second-order" approach to classification [Ze­ Iikovitz and Hirsh, 2000; 2002], in that data are no longer directly compared but rather, are compared one step removed, through an intermediary.

Finally we use the background knowledge to redescribe both the training and the test examples. To do this, we add the background knowledge documents to the training set, to create a large, sparse term-by-document (t x d) ma­ trix. We then use Latent Semantic Indexing (LSI) [Deer­ wester et al., 1990] to automatically redescribe textual data in a new smaller semantic space using singular value de­ composition. The original space is decomposed into lin­ early independent dimensions or "factors", and the terms and documents of the training and test examples are then repre­ sented in this new vector space [Zelikovitz and Hirsh, 2001; 2002]. Documents with high similarity no longer simply share words with each other, but instead are located near each other in the new semantic space. Since this semantic space was created by incorporating the background knowledge, the model of the domain that it creates reflects both the training set and the background knowledge.

3 Comparison of Approaches

Different types of background knowledge are most useful for each of these three systems. The system based upon WHIRL performs best on the problems where the form and size of the background knowledge is substantially different than the training and test data. For example, we classify names of companies by area using Yahoo! pages as background knowl­ edge. These background pieces of data are not really classi­ fiable, in the sense that they do not necessarily belong to any specific class. Since this WHIRL-based method does not at­ tempt to classify the background knowledge, but merely uses it to index into the training corpus, it makes the best use of this background knowledge.

For the data sets where the background knowledge fits very closely to the training and test classification task, EM outper­ forms the other systems. For example, EM performed best when classifying physics papers by subdiscipline using ab­ stracts as background knowledge. This is consistent with the way EM makes use of background knowledge. Since EM actually classifies the background knowledge, and uses the background know ledge to decide on the parameters of its gen­ erative model, the closer the background knowledge is to the training and test sets, the better EM will perform. Ideally, for EM, we wish the background knowledge to be generated from the same model as the training and test sets.

Reexpressing the data and background with LSI seems to be most effective when there is very limited training data. On the smallest data sets, it outperforms all the other methods in many domains. When very few training examples exist, this method can still build a space that correctly models the domain by using the available background knowledge.

We are currently looking at methods to evaluate sets of background knowledge to determine the amount of back­ ground knowledge as well as the measure of relevance that it must have to the training set to be useful for each of these learners.