Special Feature

Multiple Topic Detection by Parametric Mixture Models (PMM)—
Automatic Web Page Categorization for Browsing
Kazumi Saito†
Abstract
This article explains a statistical model called PMM (parametric mixture models) for efficiently
detecting multiple topics in documents such as Web pages describing a wide variety of contents. It also
shows that in experiments using a set of real Web pages, PMM outperformed conventional methods interms of topic detection performance.

1. Introduction
What do you do when you want to find a specificfact such as the height of Mt. Fuji? The traditional
way was to look in a reference book at home or in alibrary, but these days many people perform a Web
search using keywords such as “height” and “Mt.
Fuji”. This can quickly retrieve the desired information from among the huge number of pages on theWorld Wide Web. On the other hand, we sometimes
want to learn something new by browsing documents.
In this article, I mainly focus on the latter situation.
In general, we can easily browse even a huge number of documents and books if each one is suitably
categorized according to its topic. For instance,libraries employ a standard classification system forcategorizing books to make it easy to find books.
However, a general document may have more than
one topic, so it may be difficult for a librarian todecide on a single place to put a book about visiting
historical places in Kyoto. Should it go under travel,
society, or history? It might be best to regard the book
as having all three of these topics and put one copy ineach of these locations.
Web pages let authors freely write about their ownintentions, opinions, etc., so they often cover multiple
topics. To cope with this situation, we need to categorize a document using multiple topics. However,when considering a wide variety of topics, the total† NTT Communication Science Laboratories
Soraku-gun, 619-0237 Japan
E-mail: saito@cslab.kecl.ntt.co.jp

Vol. 3 No. 3 Mar. 2005

number of combinations of multiple topics becomes
extremely large. While it would be impossible to prepare physical shelves in a library to hold multiple
copies of books, we can easily prepare multiple virtual shelves for multi-topic documents by making fulluse of hyperlinks.
2. Web page categorization by directory
Many portal sites are equipped with a directory service where Web pages are categorized into multiple
topics by humans. For instance, the open directory
project [1] constructed a hierarchical classification
directory where its top level consists of 16 general
topics (categories) and each of these topics is in turndecomposed into several specific subtopics (Fig. 1).
Many pages can be found by following more than one
path. For example, you can find the home page of
NTT Communications by following a series of hyperlinks starting under either “Business” or “Regional”
on the top-level page of the open directory. We canregard this Web page as a typical example of a multitopic document, i.e., one that refers to both “business& regional” information.
It is difficult to place every Web page into a directory. Namely, since the number of Web pages isincreasing every day, it is highly labor intensive forhumans to assign a suitable multi-topic label to eachWeb page one by one. Therefore, it would be very
convenient if a personal computer could automatically determine a suitable multi-topic label for each Web
page. To this end, by considering the intrinsic natureof multi-topic documents, NTT Communication Sci15

Special Feature

Fig. 1. Web page classification by directory in a portal site.

Sample document:
Camembert is covered by white moldand Gorgonzola contains blue mold.
Word:

Camembert cover white mold Gorgonzola …

Frequency:

1

1

1

2

1…

Fig. 2. Document representation by word frequency.

ence Laboratories has developed a multiple topic
detection model called PMM (parametric mixturemodels).
3. Parametric mixture models
To produce an input data set for PMM, we first analyze a document (Web page) by decomposing it into
a set of words and counting the frequency of eachword. We exclude 571 well-known stop-words suchas “is” and “by” and truncate some words such as
conjugated verbs like “cover” (Fig. 2). Here, since theappearance order of words is completely ignored, thedocument representation based on word frequency iscalled a bag-of-words expression. This expression is
widely used in the text mining field.
Now, consider the frequency of words appearing in
multi-topic documents. By examining actual Web
pages related to the topic “cheese”, we found that thecharacteristic word set of the Web pages whose dualtopic category is cheese “sales & recipes” consists ofa mixture of the two sets of characteristic words: thatfor Web pages on the single topic “sales” and that for
16

pages on “recipes” (Fig. 3). Based on this insight, mycolleague and I developed PMM [2]. Namely, themain contribution of PMM is that this natural insightis mathematically formalized as a statistical model.
From a set of documents labeled by allowing multiple topics, we can automatically construct the PMM
model by using a learning algorithm. Therefore, if thetraining data set is replaced, we can easily construct amodel for another topic detection system. Since
PMM consists of general-purpose techniques, we caneasily apply it to a set of general documents, not justWeb pages. Of course, PMM can also be used todetect an unknown multi-topic label of a new document.
There are many conventional methods for document categorization. However, the statistical methods
such as naive Bayes (NB), as well as pattern recognition methods such as support vector machines(SVM), cannot simultaneously detect multiple topics
of documents. Some existing methods, such as the knearest neighbors (k-NN) method and neural network(NN) method, can detect multiple topics in documents, but they do not consider the intrinsic properNTT Technical Review

Special Feature

Sales

Recipes

Sales & recipes
cow, kitchen knife, cut, sugar,cow, sheep, goat, milk, grass,cut, gram, pan, roaster, set,price, ripeness, keeping …

kitchen knife, sugar, dish, cakehome, ripeness, set, roaster,refrigerator, present …

Characteristic words of multi-topic documents
are a mixture of those of single-topic documents.

Fig. 3. Basic idea of parametric mixture models.

Table 1. Topic detection performance of PMM.
Problem name(top category)Arts & humanities
Business & economy
Computers & Internet
Education
Entertainment
HealthRecreation
ReferenceScience
Social science
Society & culture

Basic statistics
TopicsVocab. Words
26111.1
23146
30
102.1
21924
33
128.234096
33
111.8
27534
21
145.7
32001
32
108.8
30605
22
129.9
30324
33
163.7
39679
40
173.3
37187
39
154.4
52350
27
176.2
31802

ties of documents with multiple topics, so we thinkthat they will have natural limitations for this task.
4. Application to document classification
To evaluate the topic detection performance ofPMM, we performed experiments using a set of Web
pages stored in the directory of the popular Japaneseportal site “goo”, which is similar to Yahoo. We conducted separate experiments on each of the 11 toplevel categories and regarded their second-level categories as multiple topics to be detected [3]. For eachcategory, Table 1 shows basic statistics, i.e., thevocabulary size (the total number of different words),
the average number of words in one Web page, andthe number of single topics.
For each of these 11 categories, Table 1 compares
the topic detection performance of PMM with thoseof the main conventional methods: NB, SVM, k-NN,and NN. In the experiments, we used 2000 documents as a training set and a different set of 3000 docVol. 3 No. 3 Mar. 2005

NB41.675.0
56.5
39.3
54.5
66.4
51.8
52.6
42.4
41.7
47.2

Multi-topic detection performance
PMM
NN
kNN
SVM
50.6
43.3
40.0
47.1
75.5
77.4
78.4
74.5
61.0
53.8
51.1
56.2
51.3
44.1
42.9
47.8
59.7
54.9
47.6
56.9
66.2
66.0
60.4
67.1
55.2
49.6
44.4
52.1
61.1
55.0
53.3
55.4
51.4
45.8
43.9
49.2
61.1
62.2
59.5
65.0
54.2
50.5
46.4
51.4

uments as the test set. In the evaluation, we employed
the F-measure, which is widely used in the field of
information retrieval. The F-measure is 100% if all of
the topics are perfectly detected and 0% if any one of
the topics cannot be detected. In the table, the numbers in red show the best performance among themethods used in our experiments. As shown in thetable, PMM outperformed the conventional methods
by up to 10%, indicating its superiority over conventional methods. Using a 2.0-GHz Pentium PC, thetraining time for PMM was about 4 minutes (averagefor 11 problems) and the test time using 3000 pages
was about 1 minute, indicating that PMM is very efficient especially compared with k-NN or NN.
5. Application to document retrieval
Although keyword search is widely used to retrieve
desired documents, we cannot obtain documents that
do not contain adequate keywords. It would be very
convenient if we could retrieve documents by topic
17

Special FeatureEntertainment

Computers andInternetFig. 4. Visualization of Web page retrieval results based on topic similarity.

similarity [4]. In our experiment using real Web
pages, a Web page describing a study of the problems
with the natural environment enabled us to retrievesome related Web pages describing environmental
protection and solar batteries even though these pages
did not explicitly contain any of the keywords “natural environment problems”. This shows that PMM canretrieve Web pages that a standard keyword searchfails to retrieve. Moreover, by replacing the set of
documents used for training PMM, we can retrieve
Web pages with different aspects.
We can also use PMM to arrange the retrieved Web
pages based on topic similarity. Figure 4 shows athree-dimensional visualization map obtained bykeyword searching using a term “CD” in the site“goo”. This visualization method is explained indetail in the next feature article in this issue[5]. EachWeb page is represented by a colored circle, where
one color indicates the topic “Entertainment” and theother “Computers & Internet”. We can easily distinguish the two main fields for CD, i.e., compact disccontents (software) and compact disc equipment(hardware). Note that this experiment was conductedusing Japanese Web pages.
6. Conclusion
PMM (parametric mixture models) is a new statistical model for efficiently detecting documents about
multiple topics such as Web pages describing a wide
variety of contents. Our experiments using a set ofreal Web pages showed that PMM outperformed con18

ventional methods in terms of topic detection performance. We believe that PMM can be a basic modelfor constructing various Web services.
References
[1]
[2]
[3]

[4]
[5]

http://dmoz.org/
N. Ueda and K. Saito, “Parametric mixture models for multiple-topictext,” Trans. of IEICE, Vol. J87-D-II, No. 3, pp. 872-883, 2004.
N. Ueda and K. Saito, “Single-shot Detection of Multi-category ofText using Parametric Mixture Models,” Proceedings of the 8thInternational Conference on Knowledge Discovery and Data Mining(ACM SIGKDD2002), Edmonton, Alberta, Canada, pp. 626-631,
2002.
N. Ueda and K. Saito, “Multiple-topic model for topic-based text
retrieval,” Trans. of IPSJ, Vol. 44, No. SIG14 (TOM 9), pp. 1-8, 2003.
T. Yamada, “Visualizing Large-scale Network Data Structures,” NTT
Technical Review, Vol. 3, No. 3, pp. 19-23, 2005.

Kazumi Saito
Distinguished Technical Member, SeniorResearch Scientist, Emergent Learning ResearchGroup, Intelligent Communication Laboratory,
NTT Communication Science Laboratories.
He received the B.S. degree in mathematics
from Keio University, Yokohama, Kanagawa in
1985 and the Ph.D. degree in electrical engineering from the University of Tokyo, Tokyo in
1998. In 1985, he joined the Electrical Communication Laboratories of NTT. He has received
the Funai Best Paper Award of FIT2004, Best
Paper Award of the Japanese Society of ArtificialIntelligence, and Best Paper Award of the Information Processing Society of Japan. He is amember of IEEE, the Institute of Electronics,
Information and Communication Engineers ofJapan, Japanese Neural Networks Society,Japanese Society of Artificial Intelligence, andInformation Processing Society of Japan.

NTT Technical Review