JOURNAL OF LATEX CLASS FILES, VOL. 6, NO. 1, JANUARY 2007

1

Modeling Noisy Annotated Datawith Application to Social Annotation
Tomoharu Iwata, Takeshi Yamada, and Naonori Ueda
Abstract—We propose a probabilistic topic model for analyzing and extracting content-related annotations from noisy annotateddiscrete data such as web pages stored using social bookmarking services. With these services, since users can attach annotations
freely, some annotations do not describe the semantics of the content, thus they are noisy, i.e. not content-related. The extractionof content-related annotations can be used as a prepossessing step in machine learning tasks such as text classification and image
recognition, or can improve information retrieval performance. The proposed model is a generative model for content and annotations,in which the annotations are assumed to originate either from topics that generated the content or from a general distribution unrelated
to the content. We demonstrate the effectiveness of the proposed method by using synthetic data and real social annotation data fortext and images.
Index Terms—Topic Models, Gibbs sampling, Text Modeling, Social Annotation, Noisy DataF1

I NTRODUCTIONR

ECENTLY there has been great interest in social anno-tation, also called collaborative tagging or folksonomy, created by users freely annotating objects such as
web pages [1], photographs [2], blog posts [3], videos [4],music [5], and scientific papers [6]. Delicious, which
is a social bookmarking service, and Flickr, which isan online photo sharing service, are two representativesocial annotation services, and they have succeeded incollecting huge numbers of annotations. Since users can
attach annotations freely in social annotation services,
the annotations include those that do not describe thesemantics of the content, and are, therefore, not contentrelated [7]. For example, annotations such as ’nikon’or ’canon’ in a social photo service often represent thename of the manufacturer of the camera with which
the photographs were taken, or annotations such as’2008’ or ’november’ indicate when they were taken.
Other examples of content-unrelated annotations include
those designed to remind the annotator such as ’toread’,
those identifying qualities such as ’great’, and those
identifying ownership.
Content-unrelated annotations can often constitutenoise if used for training samples in machine learning
tasks, such as automatic text classification and image
recognition. Although the performance of a classifier
can generally be improved by increasing the number oftraining samples, noisy samples have a detrimental effecton the classifier. We can improve classifier performance
if we can employ huge amounts of social annotation datafrom which content-unrelated annotations have been filtered out. Content-unrelated annotations may also constitute noise in information retrieval. For example, a user
• T. Iwata, T. Yamada, and N. Ueda are with NTT Communication Science
Laboratories, 2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto, Japan.

may wish to retrieve a photograph of a Nikon camera
rather than a photograph taken by a Nikon camera.
In this paper, we propose a probabilistic topic model
for analyzing and extracting content-related annotations
from noisy annotated data, which we call the noisy
annotation topic model (NATM). A number of methods
for automatic annotation have been proposed [8], [9],[10], [11], [12]. However, they implicitly assume that allannotations are related to content, and to the best of
our knowledge, no attempt has been made to extract
content-related annotations automatically. The extractionof content-related annotations can improve the performance of machine learning and information retrieval
tasks. The NATM can also be used for the automatic
generation of content-related annotations.
The NATM is a generative model for content andannotation. It first generates content, and then generates
the annotations. We assume that each annotation is associated with a latent variable that indicates whether or not
it is related to the content, and the annotation originates
either from the topics that generated the content or froma content-unrelated general distribution depending on
the latent variable. The inference can be achieved basedon collapsed Gibbs sampling.
Intuitively speaking, our approach considers an annotation to be content-related when it is almost always
attached to objects in a specific topic. On the other
hand, an annotation that is attached to objects in various topics is considered to be content-unrelated. Even
if annotations are nominally the same, some may berelated to the content, and others may not. For example,
the annotation ’nikon’ attached to a photograph abouta camera made by Nikon is related to the content, on
the other hand one attached to a photograph taken witha Nikon camera is not. To deal with this situation, theNATM models the relevance of each annotation to thecontent by considering both the annotation text and the

JOURNAL OF LATEX CLASS FILES, VOL. 6, NO. 1, JANUARY 2007

relationship between the content and annotation.
The NATM is based on topic models. A topic model isa hierarchical probabilistic model, in which a document
is modeled as a mixture of topics, and where a topic
is modeled as a probability distribution over words.
Topic models are successfully used for a wide variety
of applications including information retrieval [13], [14],collaborative filtering [15], [16], and visualization [17] aswell as for modeling annotated data [9]. The NATM is anextension of correspondence latent Dirichlet allocation(Corr-LDA) [9], which is a generative topic model forcontent and annotation. Since the Corr-LDA assumes
that all annotations are related to the content, it cannot
be used for separating content-related annotations fromcontent-unrelated annotations.
The extraction of content-related annotations can beconsidered a binary classification problem. However,as regards real social annotation data, the annotations
are not explicitly labeled as content related/unrelated.
Therefore, we cannot use supervised binary classifiers
such as the support vector machine (SVM) [18]. The
NATM is an unsupervised model, which can extract
content-related annotations without content relevancelabels.
In the rest of this paper, we assume that the given
data are annotated document data, in which the content
of each document is represented by words appearing
in the document, and each document has both contentrelated and content-unrelated annotations. The NATM
is applicable to a wide range of discrete data with noisy
annotations. These include annotated image data, where
each image is represented with visual words [19], andannotated movie data, where each movie is represented
by user ratings.
The remainder of this paper is organized as follows.
In Section 2, we briefly review related work. In Section 3, we formulate the proposed noisy annotation
topic model, and describe its inference procedures. We
also present procedures in a partially explicit relevancesetting and procedures for using the proposed modelfor the preprocessing when training different types ofclassifiers. In Sections 4 and 5, we demonstrate theeffectiveness of the proposed model by using synthetic
data and real social annotation data, respectively. Finally,
we provide concluding remarks and a discussion of
future work in Section 6.

2 R ELATED WORK
Recently a number of models have been proposed forautomatic annotation especially for images [8], [9], [10],[11], [12]. However, since they do not model the relevance between content and annotation, they cannot be
used for extracting content-related annotations. These
automatic annotation methods are based on supervisedclassifiers, in which all annotations of training samples
are considered even if they are unrelated to the content.
This means they cannot be employed for the automatic
generation of content-related annotations.

2

Topic models for social annotation have been proposed [20], [21], which model the relationships between
objects, annotations, and users. In contrast to these models, the NATM does not require user information. There
are some social annotation data in which user information is unavailable. Therefore, the proposed model isapplicable to wider range of data sets than the methods
that require user information. In [20], entropy is used as
an indicator of the ambiguity of the annotation, where
the entropy represents how uniformly the annotation
is attached over topics. Since ambiguous annotations
imply that they are attached to documents covering
a wide range of topics independent of content, thisentropy-based method may also be used for extracting
content-related annotations. However, the NATM has
three advantages over the entropy-based methods. First,
even if annotations have the same name, the NATM
is able to consider some of them to be related to thecontent and others not by taking account of the relevanceof each annotation to the content. Second, the entropybased method requires some ad-hoc entropy thresholds
for classifying whether or not each annotation is contentrelated. On the other hand, the NATM does not require
any thresholds because the classification is explicitly
achieved by inferring a latent variable that represents therelevance of each annotation to the content. Third, theNATM simultaneously models content and annotations
with their relevance in one probabilistic framework. On
the other hand, since the entropy-based method finds
content-unrelated annotations via post-processing after
the inference, errors accumulated in the inference cannot
be corrected in the extraction process.
Topic models with a background distribution [22], [23]assume that words are generated either from a topicspecific distribution or from a corpus-wide background
distribution. Although they are generative models for
documents without annotations, the NATM is related to
it in the sense that data may generated from a topicunrelated distribution depending on a latent variable.
There are other topic models that generate a word depending on a latent binary variable. For example, citationinfluence models [24] are also related to the proposedmodel because they assume that a word is generated
according to topic proportions of the document or thoseof a cited document depending on the latent binary
variable. In short, the citation influence models are topic
models for generating words in a content using thecitation information, whereas the proposed model is a
topic model for generating both words in a content andannotations from the same topics. Therefore, the aim isdifferent from ours. [25] recently introduced a probabilistic model designed to understand scene images, objects
and associated noisy annotations. Their model uses aswitch variable that decides whether a annotation is visually relevant or not. The switch variable depends on an
object in the content, and visually irrelevant annotations
are generated from the scene dependent distribution.
Therefore, the visually irrelevant annotations do notJOURNAL OF LATEX CLASS FILES, VOL. 6, NO. 1, JANUARY 2007

TABLE 1
Notation
Symbol
D
W
T
K
Nd
Md
wdn
zdn
tdm
cdm
rdm

Description
number of documents
number of unique words
number of unique annotations
number of topics
number of words in the dth document
number of annotations in the dth document
nth word in the dth document, wdn ∈ {1, · · · , W }topic of the nth word in the dth document,zdn ∈ {1, · · · , K}
mth annotation in the dth document, tdm ∈ {1, · · · , T }topic of the mth annotation in the dth document,
cdm ∈ {1, · · · , K}
relevance to the content of the mth annotation of thedth document, rdm = 1 if relevant, rdm = 0 otherwise

have obvious visual correspondences, but they relate to
the content. Since they focus on image analysis, theirmodel is not appropriate for text such as social bookmark
data.
The NATM is related to the partial label learning
problem [26], in which each training sample is labeledwith a set of possible labels, one of which is correct,
when we consider a content-related annotation to be thecorrect label. However, the partial label learning assumes
that there is only one correct label per sample. Since there
may be multiple content-related annotations, methods
for the partial label learning cannot be used for our
purpose.

3

P ROPOSED METHOD

3.1 Noisy Annotation Topic Model
Suppose that, we have a set of D documents, and eachdocument consists of a pair of words and annotationsd(wd , td ), where wd = {wdn }Nn=1 is the set of words
in the dth document that represents the content, anddtd = {tdm }M
m=1 is the set of assigned annotations, or tags.
The vocabulary of words and that of annotations can bedifferent. For example, words and annotations can bediscrete visual features and tags, respectively, and they
can be written in different languages. Our notation issummarized in Table 1.
The proposed noisy annotation topic model (NATM)
first generates the content, and then generates the annotations. The generative process for the content is
the same as that of basic topic models, such as latent
Dirichlet allocation (LDA) [13]. Each document has topic
proportions θd that are sampled from a Dirichlet distribution. For each of the Nd words in the document, a
topic zdn is chosen from the topic proportions, and thenword wdn is generated from a topic-specific multinomial
distribution φzdn . In the generative process for annotations, each annotation is assessed as to whether or not it
is related to the content. In particular, each annotation isassociated with a latent variable rdm with a value rdm =0 if annotation tdm is unrelated to the content; rdm = 1
otherwise. If the annotation is not related to the content,

3rdm = 0, annotation tdm is sampled from a general topicunrelated multinomial distribution ψ0 . If the annotationis related to the content, rdm = 1, annotation tdm issampled from a topic-specific multinomial distribution
ψcdm , where cdm is the topic for the annotation. Topicd
cdm is sampled given topics zd = {zdn }N
n=1 that havepreviously generated content. This means that topic cdm
is generated from a multinomial distribution, in which, where Nkd is the number of words
P (cdm = k) = NNkddassigned to topic k in the dth document.
In summary, the NATM assumes the following generative process for a set of annotated documents{(wd , td )}D
d=1 ,1) Draw relevance probability
λ ∼ Beta(η)2) Draw content-unrelated annotation probabilityψ0 ∼ Dirichlet(γ)3) For each topic k = 1, · · · , K:a) Draw word probability
φk ∼ Dirichlet(β)b) Draw annotation probabilityψk ∼ Dirichlet(γ)4) For each document d = 1, · · · , D:a) Draw topic proportions
θd ∼ Dirichlet(α)b) For each word n = 1, · · · , Nd :i) Draw topic for word
zdn ∼ Multinomial(θd )ii) Draw word
wdn ∼ Multinomial(φzdn )c) For each annotation m = 1, · · · , Md :i) Draw topic for annotation
cdm ∼ Multinomial({ NNkd
}K
k=1 )
d
ii) Draw relevancerdm ∼ Bernoulli(λ)iii) Draw annotation{
Multinomial(ψ0 )if rdm = 0
tdm ∼Multinomial(ψcdm ) otherwise
where α, β and γ are Dirichlet distribution parameters,and η is a beta distribution parameter. Figure 1 showsa graphical model representation of the NATM, whereshaded and unshaded nodes indicate observed and latent variables, respectively.
Each latent relevance variable rdm is drawn from a
Bernoulli distribution with parameter λ, where λ represents the probability that an annotation is related to thecontent. We assume that λ is generated according to abeta distribution because it is conjugate to a Bernoulli
distribution, and the inference can be efficiently performed based on collapsed Gibbs sampling by integrating out the parameter λ. We use conjugate Dirichletpriors for the multinomial parameters in the proposedmodel as used in the LDA.
Topics for annotations are drawn proportional to thenumber of topics assigned in the content. Therefore,
annotations tend to be assigned the same topics with the

JOURNAL OF LATEX CLASS FILES, VOL. 6, NO. 1, JANUARY 2007

α

η

θ

λ

z

w

c

t

φ

N

ψ

r

K

K+1

4

β
γ

M D

Fig. 1. Graphical model representation of the proposed
noisy annotation topic model (NATM) with content relevance.
content, and a topic for content and the corresponding
topic for annotation have similar meaning.
Intuitively speaking, the proposed model assumes that
content-related annotations have the same topics withthe ones assigned to the words in the content. Therefore,
a content-related annotation is assigned a topic c thatis generated from topics in the content. The proposedmodel assumes that content-unrelated annotations are
independent from the topics in the content, and they
are generated by a general topic-unrelated multinomial
distribution.
As with the Corr-LDA, the NATM first generates thecontent and then generates the annotations by modeling the conditional distribution of latent topics forannotation given the topics in the content. Therefore, it
achieves a comprehensive fit of the joint distribution ofcontent and annotations and finds superior conditional
distributions of annotations given content [9].
The joint distribution on words, annotations, topics forwords, topics for annotations and relevance is describedas follows:
P (W , T , Z, C, R|α, β, γ, η)= P (Z|α)P (W |Z, β)P (T |C, R, γ)P (R|η)P (C|Z),(1){wd }Dd=1 ,{td }D
d=1 ,Z = {zd }D
d=1 ,= {rd }D
d=1 , and

where W =T =Md
C = {cd }D
d=1 , cd = {cdm }m=1 , R
drd = {rdm }M
m=1 . We can integrate out multinomial disKK
tribution parameters, {θd }Dd=1 , {φk }k=1 and {ψk0 }k0 =0 ,because we use Dirichlet distributions for their priors,
which are conjugate to multinomial distributions. The
first term on the∫ right hand side of (1) is calculated by∏D
P (Z|α) = d=1 P (zd |θd )P (θd |α)dθd , and we have thefollowing equation by integrating out {θd }D
d=1 ,()D ∏ ∏Γ(αK)
k Γ(Nkd + α)
P (Z|α) =
,
(2)
Γ(α)K
Γ(Nd + αK)dwhere Γ(·) is the gamma function. Similarly, the second
term is given as follows,()K ∏ ∏
Γ(βW )w Γ(Nkw + β)
P (W |Z, β) =
,
(3)
Γ(β)W
Γ(Nk + βW )kwhere Nkw is the number of ∑times word w has been
assigned to topic k, and Nk = w Nkw . The third term

is given as follows,)K+1 ∏ ∏(0Γ(γT )t Γ(Mk t + γ)
, (4)P (T |C, R, γ) =TΓ(γ)Γ(Mk0 + γT )
0
k

0

0

where k ∈ {0, · · · , K}, and k = 0 indicates irrelevanceto the content. Mk0 t is the number of times annotationt has been identified as content-unrelated if k 0∑
= 0, oras content-related topic k 0 if k 0 6= 0, and Mk0 = t Mk0 t .
The Bernoulli parameter λ can also be integrated out
because we use a beta distribution for the prior, whichis the conjugate prior of a Bernoulli distribution. The
fourth term is given as follows,
P (R|η) =Γ(2η) Γ(M0 + η)Γ(M − M0 + η),
Γ(η)2
Γ(M + 2η)

(5)where M is the number of annotations, and M0 is thenumber of content-unrelated annotations. The fifth term
is given as follows,0∏ ∏ ( Nkd )Mkd
P (C|Z) =
,
(6)
Nd
d

k

0
Mkd

is the number of annotations that are aswhere
signed to topic k in the dth document.
3.2

Inference

The inference of the latent topics Z given content W
and annotations T can be efficiently computed using
collapsed Gibbs sampling [27]. Given the current state of
all but one variable, zj , where j = (d, n), the assignmentof a latent topic to the nth word in the dth document issampled from,P (zj = k|W , T , Z\j , C, R)∝

Nkd\j + α Nkwj \j + β
Nd\j + αK Nk\j + βW(

Nkd\j + 1
Nkd\j

0
)Mkd

, (7)

where \j represents the count when excluding the nthword in the dth document. Given the current state of all
but one variable, ri , where i = (d, m), the assignment ofeither relevance or irrelevance to the mth annotation in
the dth document is estimated as follows,
M0\i + η M0ti \i + γ
P (ri = 0|W , T , Z, C, R\i ) ∝,M\i + 2η M0\i + γT
M\i − M0\i + η Mci ti \i + γ.
M\i + 2ηMci \i + γT
(8)
The assignment of a topic to a content-unrelated annotation is estimated as follows,
Nkd
P (ci = k|ri = 0, W , T , Z, C\i , R\i ) ∝,(9)Nd
P (ri = 1|W , T , Z, C, R\i ) ∝and the assignment of a topic to a content-related annotation is estimated as follows,
Mkti \i + γ Nkd
P (ci = k|ri = 1, W , T , Z, C\i , R\i ) ∝.
Mk\i + γT Nd(10)

JOURNAL OF LATEX CLASS FILES, VOL. 6, NO. 1, JANUARY 2007

5

One iteration of the Gibbs sampler corresponds to sample topics for each word and for each annotation, and therelevance of each annotation in the given documents.
The parameters α, β, γ, and η are estimated by maximizing the joint distribution (1). The following updating
rules for maximizing the joint distribution are derived
by using the bounds as described in [28],
∑ ∑
(new)
d
z Ψ(nzd + α) − DKΨ(α)
∑
α
←α
,
(11)
K ( d Ψ(Nd + αK) − DΨ(αK))
∑ ∑
(new)
z∑ w Ψ(nzw + β) − KW Ψ(β)
,
(12)
β
←β
W ( z Ψ(nz + βW ) − KΨ(βW ))
∑ ∑
(new)
t
z 0 Ψ(mz 0 t + γ) − (K + 1)T Ψ(γ), (13)γ←γ ∑T ( z0 Ψ(mz0 + γT ) − (K + 1)Ψ(γT ))η (new) ← ηΨ(m0 + η) + Ψ(m − m0 + η) − 2Ψ(η), (14)2 (Ψ(m + 2η) − Ψ(2η))

where Ψ(·) is a digamma function defined by Ψ(x) =∂ log Γ(x). These update rules can find a local optimum∂xsolution for the parameters.
By iterating Gibbs sampling with (7), (8), and (9) or(10), and maximum likelihood estimation with (11), (12),(13), and (14), we can infer latent topics for words andannotations as well as the relevance to their content
while optimizing the parameters.
(s)
Let {rdm }Ss=1 be S sampled values of the relevancevariable rdm after the burn-in period. The relevanceprobability of the mth annotation in the dth document
can be estimated by,1 ∑ (s)r .
S s=1 dm
Sr̂dm =(15)

The inferred model can also predict content-related annotations given content without annotations. In particular, the probability of content-related annotation t in thedth document can be calculated as follows,∑
P (t|d, D) =θ̂dk ψ̂kt ,(16)
kwhere θ̂dk = NNkd
is the point estimate of the topic prod
Mkt +γportions for annotations, and ψ̂kt = M
is the point
k +γT
estimate of the annotation multinomial distribution.
3.3 Partially explicit relevance setting
In the above discussion, we assumed that none of the annotations were labeled as content related/unrelated, or
relevance information was implicit. However in practice,
the content relevance labels for some annotations might
be available. For example, some social annotations canbe manually labeled by experts. Therefore, we consider
a partially explicit relevance setting, in which we haveannotations labeled with related or unrelated as wellas unlabeled annotations. The NATM can deal directlywith labeled annotations. In an implicit relevance setting,relevance variables r are assumed to be hidden for all

annotations as in Figure 1. In a partially explicit setting,relevance variables r are assumed to be observed andfixed for explicit relevance annotations, and hidden for
implicit relevance annotations. Thus, Gibbs sampling ofr for each explicit relevance annotation is unnecessary.
The other inference procedures in a partially explicit
setting are the same as those in an implicit setting. In
particular, the inference can be performed by iterating
Gibbs sampling with (7) for each word, (8) for each
unlabeled annotation, (9) or (10) for each explicit andimplicit annotation, and maximum likelihood estimation
with (11), (12), (13), and (14). By using the explicit
relevance information, the NATM can be inferred more
precisely.
3.4

Combination with different classifiers

The NATM can be used for the prepossessing of classifier
training. By filtering out content-unrelated annotations,
we can improve classifier performance. The NATM can
predict annotations given content without annotationsby (16). However, different classifiers might achieve better classification performance than the topic model based
method in some applications. For example, discriminative classifiers such as maximum entropy models [29]and support vector machines [30] usually perform better
when training data are abundant than generative classifiers such as naive Bayes models and topic models,
and this has been experimentally confirmed in a textclassification problem [31]. Thus, we present proceduresthat combine the advantage of the NATM in filtering out
content-unrelated annotations and the advantage of different classifiers as regards high classification accuracy.
In general, a classifier is trained by minimizing the following empirical error function over the given samples,
E=

Md
D ∑
∑

J(xd , tdm ),(17)

d=1 m=1

where xd is the feature vector of the dth document’s
content, each sample is represented by a pair consistingof the feature vector and annotation (x, t), and the error
function J(x, t) represents the error of the classifier given
the sample. Typical error functions include negative log
likelihood J(x, t) = − log P (t|x), and 0-1 loss function,
J(x, t) = 0 if f (x) = t and J(x, t) = 1 otherwise. If there
are no content-unrelated annotations, the minimizationof E will lead to the minimization of the expected error
when we have sufficient numbers of samples. However,noisy samples, i.e., content-unrelated annotations, havea detrimental effect on training classifiers. Therefore, we
propose the following weighted error function,
Er =

Md
D ∑
∑

r̂dm J(xd , tdm ),(18)

d=1 m=1

where each sample is weighted by the relevance tothe content r̂dm that is calculated by (15). When using

JOURNAL OF LATEX CLASS FILES, VOL. 6, NO. 1, JANUARY 20076

the weights, content-unrelated annotations are less effective for training than content-related ones. Therefore,
a detrimental effect of content-unrelated annotations
can be eliminated. The classifier that is used should
be capable of dealing with weighted samples. This is
not a severe limitation of our approach because many
common classifiers are able to learn with a weighted
error. For example, to learn a classifier based on an
exponential family, such as one with multinomial or
Gaussian class-conditional distributions, we have only
to calculate weighted sufficient statistics. The SVM withweights for each sample, which is called the fuzzy
SVM [32] or weighted SVM [33], has also been proposed.
With feature selection methods, features that are usefulfor improving classifier performance are extracted. Thisapproach selects samples that are useful for trainingclassifiers instead of selecting useful features.
We describe the procedure for training maximum entropy models with the proposed weighted frameworkusing the NATM as an example. The maximum entropy
model, which is also called the logistic regression or loglinear model, is a discriminative model, and it estimatesa probability distribution that maximizes entropy under the constraints in the given samples. This model
has been used in various research fields such as textclassification [29] and collaborative filtering [34]. The
maximum-entropy distribution of annotation t givenfeature vector x is represented as follows:
exp(µ>t x)
P (t|x) = ∑T,>
t0 =1 exp(µt0 x)(19)where µt is an unknown parameter vector for annotationt, and where µ>t represents the transpose of µt . When
we use a negative log likelihood for the error function
and a Gaussian prior for µt with mean 0 and covarianceν −1 I [35], the weighted error function becomes:
(
)
Md
D ∑
T
∑
∑
ME
>
>
= −
Er
r̂dm µtdm xd − log
exp(µt0 xd )
+

t0 =1

d=1 m=1T∑νk µt k2 .
2 t=1

(20)

We can estimate the unknown parameters {µt }t∈T byminimization via the quasi-Newton method [36]. The
global optimality of the estimate is guaranteed due tothe concavity of the weighted error function.

4 E XPERIMENTS WITH S YNTHETIC CONTENTUNRELATED ANNOTATIONS
4.1 Data
We evaluated the NATM quantitatively by using labeled text data from the 20 Newsgroups corpus [37]1
and adding synthetic content-unrelated annotations.
The corpus contains about 20,000 articles categorized
1. Available at the UCI
http://archive.ics.uci.edu/ml/

into 20 discussion groups. We considered these 20 categories as content-related annotations, and we also randomly attached dummy categories to training samples
as content-unrelated annotations. We created four typesof training data, 20News-DP, 20News-DU, 20News-SP,
and 20News-SU. In 20News-DP and 20News-DU, thedummy content-unrelated annotations were different
from the content-related annotations. On the other hand,in 20News-SP and 20News-SU, the dummy contentunrelated annotations were chosen from the contentrelated annotations. In some real social annotation data,
nominally same annotations can be both content-related
and unrelated. To evaluate the NATM in this situation,
we constructed 20News-SP and 20News-SU. 20News-DP
and 20News-SP were used for evaluating the NATM
when analyzing data with different probabilities ofadding content-unrelated annotations, and 20News-DU
and 20News-SU were used with different numbers of
unique content-unrelated annotations. Specifically, inthe 20News-DP data, the number of unique contentunrelated annotations was set at 20, and the probabilityof adding content-unrelated annotations per document
was set at {0.05, · · · , 1.0}. In the 20News-DU data, thenumber of unique content-unrelated annotations was set
at {1, · · · , 20}, and the probability of adding contentunrelated annotations per document was set at 1.0. In
the 20News-SP data, the number of unique contentunrelated annotations was set at 10 and they wereselected from the content-related annotations of 20 categories, and the probability of adding content-unrelated
annotations per document was set at {0.05, · · · , 1.0}. In
the 20News-SU data, the number of unique contentunrelated annotations was set at {1, · · · , 20}, and theprobability of adding content-unrelated annotations per
document was set at 1.0. We omitted stop-words andwords that occurred only once. The vocabulary size was
52,647. We sampled 100 documents from each of the 20
categories, for a total of 2,000 documents. We used 10% of the samples as test data. The synthetic contentunrelated annotation data are summarized in Table 2.

MachineLearning

Repository

4.2

Perplexity

We evaluated the predictive performance of each method
using the following perplexity of held-out contentrelated annotations given the content,( ∑ ∑M test)
testd
m=1 log P (tdm |d, D)d∑
Perplexity = exp −, (21)
testd Md
where Mdtest is the number of held-out annotations in thedth document, ttest
dm is the mth held-out annotation in thedth document, and D represents the training samples.
A lower perplexity represents higher predictive performance. In the NATM, we calculated the probability ofcontent-related annotation t in the dth document given
the training samples using (16). Note that no contentunrelated annotations were attached to the test samples.

JOURNAL OF LATEX CLASS FILES, VOL. 6, NO. 1, JANUARY 2007

7

TABLE 2
Summary of the synthetic content-unrelated annotation data.
unrelated annotations are different from related annotations
number of unique content-unrelated annotations
probability of adding content-unrelated annotations

We compared the proposed NATM with the correspondence latent Dirichlet allocation (Corr-LDA). The
Corr-LDA [9] is a topic model for words and annotations, where all of the annotations are considered to be
relevant to the content. For the NATM and the CorrLDA, we set the number of latent topics, K, at 20,
and estimated latent topics and parameters by using
collapsed Gibbs sampling and the fixed-point iteration
method, respectively.
Figure 2 shows the average perplexities over 100 experiments on the four data sets. The perplexities of the
NATM were lower than those of the Corr-LDA in all of
the data sets. This result indicates that the NATM canrobustly predict content-related annotations with noisy
training data. The perplexity achieved by the Corr-LDA
was high because it does not take account of the relevance to the content and it considers all attached annotations to be content-related even if they are not. As theprobability of content-unrelated annotations increases,
the performance of the Corr-LDA deteriorated as shownin Figure 2 (a) and (c). On the other hand, the performance of the NATM provided low perplexity even when
the probability of the content-unrelated annotations wasincreased. The low perplexity of the NATM in Figure 2(c) and (d) shows that the NATM can appropriately
model noisy data with the same name of content-related
and unrelated annotations. In the 20News-SU data, thenumber of occurrence of each unrelated annotation decreases as the number of unique unrelated annotations
increases, because the probability of adding unrelated
annotations is fixed. Therefore, the estimated probabilityof generating a certain unrelated annotation becomes
low, and the perplexity by the Corr-LDA for the held-out
related annotations decreases in the 20News-SU.
4.3 Extracting content-related annotations
We evaluated the performance in terms of extracting
content-related annotations. We considered extraction asa binary classification problem, in which each annotation is classified as either content-related or contentunrelated. For the evaluation measurement, we used Fmeasure, which is the harmonic mean of precision andrecall.
We compared the NATM with a entropy-based
method and a baseline method. With the entropy-based
method, we estimated the topic probability for each annotation P (c|t) using the Corr-LDA, and we used the entropy for an indicator of the ambiguity of the annotation
as is used in [20]. In particular, P (c|t) is calculated byusing the Bayes rule P (c|t) ∝ P (c)P (t|c), where P (c) and

20News-DPyes
20
0.05, · · · , 1

20News-DU
yes
1,· · · ,20
1

20News-SP
no10
0.05, · · · , 1

20News-SU
no1,· · · ,201

P (t|c) are obtained by the inference of the Corr-LDA.
∑K
The entropy is given by − c=1 P (c|t) log P (c|t). Then,
we sorted annotations according to their entropies indescending order, and the annotations that are allocatedbefore the maximum gap of the entropies are estimatedas content-unrelated, and those after the maximum
gap are estimated as content-related. With the baseline
method, the annotations are considered to be contentrelated if any of the words in the annotations appear in
the document. For example, when the category name is’comp.graphics’, if ’computer’ or ’graphics’ appears in
the document, it is considered to be content-related. We
assume that the baseline method knows that contentunrelated annotations do not appear in any document.
Therefore, the precision of the baseline method is always
one, because there are no false positive samples. Notethat this baseline method does not support image data,
because words in the annotations never appear in thecontent.
F-measures for the four 20News data sets are shownin Figure 3. A higher F-measure represents higher
classification performance. The NATM achieved highF-measures with a wide range of ratios of contentunrelated annotations. The F-measures for 20News-DP
and 20News-DU achieved by the NATM exceeded 0.89,
and the F-measure without unrelated annotations wasone. This result implies that the NATM can flexibly handle cases with different ratios of content-unrelated annotations. The F-measures for 20News-SP and 20NewsSU are lower than those of 20News-DP and 20NewsDU because annotations with the same name can beboth content-related and unrelated in 20News-SP and
20News-SU. The F-measures achieved by the entropybased method were lower than those by the NATM in
the most cases except for 20News-DU. The F-measuresachieved by the baseline method were low because
annotations might be related to the content even if theannotations did not appear in the document. On theother hand, the NATM considers that annotations are
related to the content when the topic, or latent semantics,of the content and the topic for the annotations are
similar even if they did not appear in the document.
Figure 4 shows the ratio of the number of contentrelated annotations to that of all annotations. The ratio
can be estimated byλ̂ =M − M0 + η,
M + 2η

(22)

with the NATM. Here, M is the number of annotations,
M0 is the number of content-unrelated annotations, andJOURNAL OF LATEX CLASS FILES, VOL. 6, NO. 1, JANUARY 2007

7.5

perplexity

perplexity

8

7
6.5

9.5

6.8

9

6.6

8.5

6.4

8

6.2

7.5
7
6.5

6

0.2

0.4

0.6

0.8

1

7
6.5
6
5.5

5
0

probability of content-unrelated annotations

5.8

5.2

5
0

7.5

6

5.4
NATM
Corr-LDA

5.5

5

NATM
Corr-LDA

8

5.6

6

5.5

8.5
NATM
Corr-LDA

perplexity

NATM
Corr-LDA

perplexity

9
8.5

8

5

10

15

20

5
0

number of unique content-unrelated annotations(a) 20News-DP

0.2

0.4

0.6

0.8

1

0

probability of content-unrelated annotations(b) 20News-DU

5

10

15

20

number of unique content-unrelated annotations(c) 20News-SP(d) 20News-SU

1

1

0.8

0.8

0.6
0.4
0.2

0.6
0.4
0.2

NATM
Entropy
Baseline

0
0.2

0.4

0.6

0.8

probability of content-unrelated annotations(a) 20News-DP

1

0.6
0.4
0.2

NATM
Entropy
Baseline

00F-measure1
0.8
F-measure1
0.8
F-measureF-measureFig. 2. Perplexities of the held-out content-related annotations in 20News data.

5

10

15

20

number of unique content-unrelated annotations(b) 20News-DU

0.4
0.2

NATM
Entropy
Baseline

0
0

0.6

NATM
Entropy
Baseline

0
0

0.2

0.4

0.6

0.8

probability of content-unrelated annotations(c) 20News-SP

1

0

5

10

15

20

number of unique content-unrelated annotations(d) 20News-SU

Fig. 3. F-measures of content relevance in 20News data.

η is the parameter of the beta distribution. The estimatedratios were close to the true ratios even though the
NATM is unsupervised.
4.4 Scalability
The time complexity of one iteration of our Gibbs sampling is O(DK(N +M )), where D denotes the number of
documents, K denotes the number of topics, and N and
M are the average number of words and annotations ina document, respectively. We experimentally evaluatedthe scalability of the proposed model using a computerwith a Corei7 965 3.2GHz CPU and a 12GB memory.
Figure 5 (a) shows the average computational time withdifferent numbers of documents while fixing the numberof topics at 20, and Figure 5 (b) shows the average computational time with different numbers of topics while
fixing the number of documents at 2,000. We performed
100 experiments using a 20News-DP data set, where we
set the probability of content-unrelated annotations at 1,
and the number of iterations at 1,000. The computationaltime is linear against the number of documents, and thenumber of topics. These results are consistent with thetheoretical computational complexities.
4.5 Analysis on parameter estimation
The proposed model has four parameters α, β, γ andη. We can find a local optimum solution by using (11),(12), (13), and (14). Here, we experimentally investigate
sensitiveness of the parameter estimation for the initial condition. We performed 100 experiments using a
20News-DP data set, where we set the probability ofcontent-unrelated annotations at 1. The initial values forthe parameters are randomly chosen from a uniform
distribution from 0 to 1. Table 3 shows the average

TABLE 3
Average estimated parameters and their standard
deviations in 20News-DP data.
variableαβγηaverage ± standard deviation
0.0909 ± 0.0003
0.0143 ± 0.0001
0.0201 ± 0.0006
16.7975 ± 0.8553

estimated parameters and their standard deviations. The
standard deviations were small for all the parameters.
This result indicates that the proposed inference procedure is robust to the initialization even though they are
local optima.
We experimentally evaluated the importance of updating parameters. Figure 6 shows the perplexities of theheld-out content-related annotations in 20News-DP datawhen we fixed a parameter. For example, in Figure 6 (a),α was fixed with the value at the x-axis, and the other parameters, β, γ and η, were estimated by maximizing thejoint likelihood. The horizontal line shows the perplexity
when the all parameters were estimated. The perplexities
changed depending on the values of parameters α, β andγ, and the proposed model achieved low perplexities
by estimating these parameters. This result indicatesthat estimating these parameters is important for the
performance. The value of η did not influence on theperformance. Note that the range of the y-axis in Figure 6(d) is narrow compared with the other figures. This isbecause η is a hyper-parameter for a Bernoulli distribution, which has only one parameter. Figure 7 shows
the F-measures in 20News-DP data when we fixed aparameter. The F-measures shows the same tendency ofthe perplexities in Figure 6. The parameter settings that

JOURNAL OF LATEX CLASS FILES, VOL. 6, NO. 1, JANUARY 2007

1

Estimated
True

0.6
0.4
0.2

0.6
0.4
0.2

0
0.2

0.4

0.6

0.8

1

0.6
0.4

5

10

15

20

(a) 20News-DP

0.4

0
0

number of unique content-unrelated annotations

0.6

0.2

0
0

probability of content-unrelated annotations

Estimated
True

0.8

0.2

0
0

1

Estimated
True

0.8
lambda0.8
lambdalambda0.8

1

Estimated
True

lambda

1

9

0.2

0.4

0.6

0.8

1

0

probability of content-unrelated annotations(b) 20News-DU

5

10

15

20

number of unique content-unrelated annotations(c) 20News-SP(d) 20News-SU

Fig. 4. Estimated content-related annotation ratios in 20News data.
1400

4000
3500

1200

3000
secondsecond

1000
800

2500
2000
1500

600

1000
400

500

200

0
500 1000 1500 2000 2500 3000 3500 4000

10

number of documents

20

30

40

50

60

70

80

90 100

number of topics(a) different numbers of documents(b) different numbers of topics

Fig. 5. Computational time (second) of the proposed model with (a) different numbers of documents and (b) different
numbers of topics.

achieved lower perplexities achieved relatively higher Fmeasures.
4.6 Partially explicit relevance setting
In Section 3.3, we described an extension of the NATM
for a partially explicit relevance setting, where someof the annotations were explicitly labeled with relatedor unrelated. We evaluated the NATM in the partially
explicit setting using 20News data sets. We used two
sets of training data 20News-Dpart and 20News-Spart.
In 20News-Dpart, for each document, we randomly
attached a content-unrelated annotation that was different from the content-related annotations. The numberof unique content-unrelated annotations was set at 20.
In 20News-Spart, for each document, we randomly attached a content-unrelated annotation that was chosenfrom the content-related annotations. The number of
unique content-unrelated annotations was set at 10. For
both of the data sets, the probability of being labeled
was set at {0, 0.05, · · · , 1.0}. Figures 8, 9 and 10 show
the perplexities, F-measures and the estimated contentrelated annotation ratios in the partially explicit setting,respectively. As the proportion of labeled annotations
increases, the performance for all of the measurements
was improved. This result indicates that the use of explicitly labeled annotations is important for the modelingif relevance information is available.
4.7 Combination with different classifiers
We evaluated the NATM when using it for the prepossessing when training different types of classifiers as
described in Section 3.4. The task is text classification
using 20News data sets. For the classifier, we used amaximum entropy model (MaxEnt) that has confirmed
its effectiveness in text classification [29]. We used thesame four data sets as in Section 4, 20News-DP, 20NewsDU, 20News-SP, and 20News-SU. The classifier performance was evaluated in terms of classification accuracy.
Figure 11 shows the result. By combining the NATM andmaximum entropy models, the accuracies were betterin the presence of noise compared with those without
using the NATM. The accuracy of the NATM when not
combined with maximum entropy models was 0.50 for
data without noise. In terms of classification accuracy,
the NATM alone is worse than the maximum entropy
model, which is a discriminative classifier whose effectiveness for text classification tasks has been confirmed
in many applications. However, by using the NATM for
preprocessing with high performance classifiers, contentunrelated annotations are filtered out, and the classification performance is improved. Since the proposed
combination framework in (18) is general as describedin Section 3.4, we can select high performance classifiers
that depend on the application and the type of given
data. The perplexities were high when there was one
unique content-unrelated annotation in Figure 11 (b) and(d). Because, in this case, all the samples are labeled witha content-unrelated annotation, and the discriminativeclassifier is trained to attach the content-unrelated annotation.

5

E XPERIMENTS WITH REAL SOCIAL ANNOTA -

TIONS

5.1

Data

We analyzed the following three sets of real social annotation data taken from two social bookmarking services

JOURNAL OF LATEX CLASS FILES, VOL. 6, NO. 1, JANUARY 2007

24

45

40

22

40

35
5.95

35

16
14
12
10

30

30

perplexity

perplexity

18

25
20

4
0.0001 0.001

0.01

0.1

1

10

100

5.9
5.85
5.8

5
0.0001 0.001

1000

20

10

10

6

25

15

15

8

6

perplexity

20
perplexity

10

0.01

0.1

1

alpha

beta

(a) α

(b) β

10

100

5
0.0001 0.001

1000

0.01

0.1

1

10

100

5.75
0.0001 0.001 0.01

1000

gamma

0.1

1

10

100

1000

eta

(c) γ

(d) η

Fig. 6. Perplexities of the held-out content-related annotations in 20News-DP data with a fixed parameter. The
horizontal line shows the perplexity when the all parameters were estimated.
1

1

0.98

0.95

0.98
0.978

0.9

0.9
0.88

F-measureF-measure

0.92

0.8
0.75
0.7

0.85
0.8

0.65

0.86

0.976

0.9

0.85

0.94

F-measure

0.96
F-measure

1
0.95

0.75
0.7

0.55

0.82
0.0001 0.001 0.01

0.1

1

10

100

0.5
0.0001 0.001 0.01

1000

alpha

0.1

1

10

100

beta

(a) α

0.97

0.966

0.65
0.0001 0.001 0.01

1000

0.972

0.968

0.6

0.84

0.974

0.1

1

10

100

1000

gamma

(b) β

0.964
0.0001 0.001 0.01

0.1

1

10

100

1000

eta

(c) γ

(d) η

Fig. 7. F-measures in 20News-DP data with a fixed parameter. The horizontal line shows the F-measure when the allparameters were estimated.
6

5.5

5.9

5.45

5.8

5.4
5.35
perplexity

perplexity

5.7
5.6
5.5
5.4

5.3
5.25
5.2

5.3

5.15

5.2

5.1

5.1
5

5.05
0

0.2

0.4

0.6

0.8

1

0

0.2

0.4

0.6

0.8

probability of labeled annotations

probability of labeled annotations(a) 20News-Dpart(b) 20News-Spart

1

1.01

0.96

1

0.95
0.94

0.99

F-measureF-measureFig. 8. Perplexities of the held-out content-related annotations with different probabilities of labeled annotations in apartially explicit setting.

0.98
0.97

0.93
0.92
0.91

0.96

0.9

0.95

0.89
0

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

0

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

probability of labeled annotations

probability of labeled annotations(a) 20News-Dpart(b) 20News-SpartFig. 9. F-measures of content relevance with different probabilities of labeled annotations in a partially explicit setting.

and a photo sharing service, namely Hatena, Delicious,and Flickr.
From the Hatena data, we used web pages and theirannotations in Hatena::Bookmark, which is a social
bookmarking service in Japan, which were collectedusing a similar method to that used in [20], [21]. Specifically, we first obtained a list of URLs of popular bookmarks for October 2008. We then obtained a list of users
who had bookmarked the URLs in the list. Next, we

obtained a new list of URLs that had been bookmarked
by the users. By iterating the above process, we collected
a set of web pages and their annotations. We omitted
stop-words and words and annotations that occurred in
fewer than ten documents. We omitted documents withfewer than ten unique words and also omitted those
without annotations. The numbers of documents, unique
words, and unique annotations were 39,132, 8,885, and43,667, respectively. From the Delicious data, we used

JOURNAL OF LATEX CLASS FILES, VOL. 6, NO. 1, JANUARY 2007

1

11

1

Estimated
True

Estimated
True

0.8
lambdalambda

0.8
0.6
0.4
0.2

0.6
0.4
0.2

0

0
0

0.2

0.4

0.6

0.8

1

0

0.2

0.4

0.6

0.8

probability of labeled annotations

probability of labeled annotations(a) 20News-Dpart(b) 20News-Spart

1

0.76

0.8

0.7

0.74

0.7

0.6

0.72

0.6

0.5

0.7

0.5

0.4
0.3
0.2
NATM+MaxEnt
MaxEnt0
0.8

probability of content-unrelated annotations(a) 20News-DP

1

0.68
0.66
0.64

0.1
0.6

accuracy

0.8

accuracy

0.76
0.758
0.756
0.754
0.752
0.75
0.748
0.746
0.744
0.742
0.74 NATM+MaxEnt
MaxEnt
0.738
0
0.2
0.4

accuracy

accuracy

Fig. 10. Estimated content-related annotation ratios with different probabilities of labeled annotations in a partially
explicit setting.

0

5

10

15

20

number of unique content-unrelated annotations(b) 20News-DU

0.4
0.3
0.2

0.62 NATM+MaxEnt
MaxEnt
0.6
0
0.2
0.4

0.1

NATM+MaxEnt
MaxEnt

0
0.6

0.8

1

probability of content-unrelated annotations

0

5

10

15

20

number of unique content-unrelated annotations(c) 20News-SP(d) 20News-SU

Fig. 11. Accuracies in 20News data with the NATM combined with the maximum entropy model.

web pages and their annotations that were collectedusing the same method as that used for the Hatena data.
The numbers of documents, unique words, and uniqueannotations were 65,528, 30,274, and 21,454, respectively.
From the Flickr data, we used photographs and theirannotations provided in Flickr that were collected in
November 2008 using the same method as that used
for the Hatena data. We transformed photo images into
visual words by using scale-invariant feature transformation (SIFT) [38] and k-means as described in [19].
We omitted annotations that were attached to fewer
than ten images. The numbers of images, unique visual
words, and unique annotations were 12,711, 200, and2,197, respectively. For the experiments, we used 2,000
documents that were randomly sampled from each data
set.
5.2 Results
The upper half of each table in Tables 4 and 5 shows
probable content-unrelated annotations in the leftmost
column, and probable annotations for some topics,
which were estimated with the NATM using 50 topics.
The lower half in Table 4 shows probable words inthe content for each topic. With the Hatena data, wetranslated Japanese words into English, and we omitted
words that had the same translated meaning in a topic.
For content-unrelated annotations, words that seemed
to be irrelevant to the content were extracted, such as’toread’, ’later’, ’*’, ’?’, ’imported’, ’2008’, ’nikon’, and’cannon’. Each topic has characteristic annotations andwords, for example, Topic1 in the Hatena data is about
economics, Topic2 is about cell-phone, and Topic3 isabout music. Figure 12 shows some examples of the

TABLE 7
Average frequency of the ten most probablecontent-unrelated annotations.
Data
HatenaDelicious
Flickr

NATM
4033.910334.5
463.5

Entropy34.0
1386.337.8

extraction of content-related annotations.
For the comparison, we show the ten highest entropy
annotations estimated with the Corr-LDA using 50 topics, which were content-unrelated annotations estimatedby the entropy-based method. Some annotations were
content-unrelated, such as ’goodread’, ’readthis’ and ’reference’ in Delicious, and ’canoneos20d’ and ’60mm’ in
Flickr. However, more content-related annotations wereextracted as unrelated compared with the NATM. The
entropy-based method was likely to extract low frequency annotations as shown in Table 7. Table 7 shows
the average frequency of the ten most probable contentunrelated annotations with the NATM and the entropybased method. This is because the variance of the estimated entropies for low frequency annotations are large
with the entropy-based method. On the other hand, theproposed model is robust because the content-unrelated
annotations are estimated in a Bayesian framework.
Figure 13 (a)(b)(c) shows the average perplexities over
100 experiments for held-out annotations in the three
real social annotation data sets with different numbersof topics. Figure 13 (d) shows the result with Patent
data as an example of data without content-unrelated
annotations. The Patent data consist of patents publishedin Japan from January to March in 2004, to which Inter-

JOURNAL OF LATEX CLASS FILES, VOL. 6, NO. 1, JANUARY 2007

12

TABLE 4
The ten most probable content-unrelated annotations (leftmost column), and the ten most probable annotations forsome topics (other columns), estimated with the NATM using 50 topics. Each column represents one topic. The lower
half in (a) and (b) shows probable words in the content.
unrelatedtoread
troll
later
web
summarygreat*
reference?
neta

Topic1
economics
financebusinessinternational
japan
money
usa
biz
stock
marketyen
year
economics
financeinvestment
japan
marketexchangebankgoldunrelatedreferencewebdesignimported
tools
web2.0
toreadwork
internetcool

Topic2
mobileiPhonepc
cell-phonecellgadgethardwareapple
ipod
networkcell
yenhandling
usege
on-board
product
phone
digitalyear
pc

Topic1
economics
financemoneybusiness
economyfinancialusa
Financerecession
Money
money
government
financialmarketeconomiccrisiscrediteconomyyears
business(a) Hatena
Topic3Topic4musicoversea
perfumeinternational
sound
world
music-stream militarycontent
korea
techno
war
audio
Japan
sound
peninsulaseriouseast-asia
CD
diplomacy
music
japan
track
korea
year
country
soundpersonCDjapanese
live
futurealbum
korea
listenchina
anonymous military
tour
say

Topic2
iphonemobilehardwareiPhone
ipod
apple
games
phone
tech
gadgetiphoneapple
2
ipod
mobile
game
gps
phone
games
blackberry(b) Delicious
Topic3Topic4foodenvironment
recipesciencerecipes green
cooking sustainability
Foodenergydessert home
Recipes Technology
Cooking housebaking Environment
cook
future1energyrecipegreen
recipes rating
food
star
october spacecheese
solar
2
power
make
oil
love
water
2008
systemTopic5sciencetechnology
chinascience-technology
traffic
tech
news
sf
physics
technology
space
year
earth
experiment
china
photo
changeday
world
earthquake
Topic5statistics
data
math
graph
visualisation
visualization
processing
graphs
chart
excel
2
1
sampledata
test
distribution
size
population
statisticalprobability

Topic6
programming
development
businessitmanagement
work
how-to-worksystem-dev
technology
dev
development
systemweb
information
seriestechnology
changecompany
peoplemanagement

Topic6
rubyprogramming
rails
php
development
opensource
frameworkcode
pythonrubyonrails
rails
php
web
ruby
licenseproject
djangomysql
1pythonTABLE 5The ten most probable content-unrelated annotations (leftmost column), and the ten most probable annotations forsome topics (other columns), estimated with the NATM using 50 topics on Flickr.
unrelated
2008
canon
nikon
bw
red
nyc
blue
color
sanfrancisco
deTopic1
music
live
paris
gig
concertshow
graffiti
fashionbenchjg

Topic2
night
rock
house
park
mallorycoachinncreature
texas
concert

Topic3
autumnpark
mountains
leavescanadamountainyellowgreen
river
britishcolumbia

national Patent Classification (IPC) codes were attachedby experts according to their content. The numbers of
documents, unique words, and unique annotations (IPC
codes) were 9,557, 104,621, and 6,117, respectively. With

Topic4beach
water
naturebird
campingmd
sunwildlife
backpacking
food

Topic5sky
cloudsspringaustralia
lake
sunsetsoccer
d80
sea
beach

Topic6familyportrait
baby
friends
cute
dof
black
boy
lightsdress

the Patent data, the perplexities of the NATM and theCorr-LDA were almost the same. On the other hand,with real social annotation data, the NATM achieved
lower perplexities than the Corr-LDA, especially with

JOURNAL OF LATEX CLASS FILES, VOL. 6, NO. 1, JANUARY 200713

flash game games cool action fun flashgames free flashgame toread temp onlinegames online_game r
tools microsoft windows maintenance utilities software todo Microsoft update pc PC
barter swap imported business firefox:bookmarks
programming theory cs mathematics wikipedia in graph detection computer math reference cycle algorithms scienceno_tag peru friends
blogging business businesses small Business Corporate no_tag blogs cookie
painting toread blogpost cool art sf graffiti publicart novelty sanfrancisco video
typo3 webdesign design gallery cms showcase portal gallerie inspiracion bestoftypo3 opensource via:mento.info css
online elearning courses
politics obama history newspapers election2008 reference news blogged photos global world History usa election

Fig. 12. Examples of content-related annotations in the Delicious data extracted by the NATM. Each row shows
annotations attached to a document; content-unrelated annotations are shaded.
TABLE 6
The ten highest entropy annotations estimated with the Corr-LDA using 50 topics.
HatenaDelicious
FlickrXP, deferred, maikoh, PS, text editor, mouse, FirefoxAddOn, webdev, movable, technical tips
relationship, newsletter, faster, stumble, goodread, Blogger, readthis, r, crossplatform, reference
blonde, canoneos20d, 60mm, entertainment, 1855mm, scenic, advertising, macro, little, sunday

Hatena and Delicious data. This result implies that it
is important to consider relevance to the content whenanalyzing noisy social annotation data. The perplexityof the Corr-LDA with social annotation data becomesworse as the number of topics increases because theCorr-LDA overfits noisy content-unrelated annotations.
With the Flickr data, the difference in perplexities was
small, because it is more difficult to extract features fromimage data than text data. In text data, words are used
to represent the content, where most words have somesemantics. On the other hand, some visual words inimage data might not have semantics, and they might
fail to represent the content.

6 C ONCLUSION
We have proposed a topic model for extracting contentrelated annotations from noisy annotated data. The proposed model can be applied in both implicit and partially explicit relevance settings, and it can also be usedas the preprocessing for different classifiers as well as
for modeling noisy annotated data. We have confirmed
experimentally that the proposed method can extract
content-related annotations appropriately, and can beused for analyzing social annotation data.
Although our results have been encouraging to date,
we must extend our approach in a number of directions.
First, we want to determine the number of topics automatically by extending the proposed model to a nonparametric Bayesian model such as the Dirichlet process
mixture model [39]. Second, we want to incorporate user
information into the model for modeling social annotation data. Third, a framework to deal with contentunrelated annotations can be used in models other than
topic models. Finally, since the proposed method istheoretically applicable to various kinds of annotation
data, we will confirm this in additional experiments.
R EFERENCES[1]

Delicious, http://delicious.com.

[2]
[3]
[4]
[5]
[6]
[7]

Flickr, http://flickr.com.
Technorati, http://technorati.com.
YouTube, http://www.youtube.com.
Last.fm, http://www.last.fm.
CiteULike, http://www.citeulike.org.
S. Golder and B. A. Huberman, “Usage patterns of collaborative
tagging systems,” Journal of Information Science, vol. 32, no. 2, pp.
198–208, 2006.
[8] K. Barnard, P. Duygulu, D. Forsyth, N. de Freitas, D. M. Blei, and
M. I. Jordan, “Matching words and pictures,” Journal of Machine
Learning Research, vol. 3, pp. 1107–1135, 2003.
[9] D. M. Blei and M. I. Jordan, “Modeling annotated data,” in
SIGIR ’03: Proceedings of the 26th Annual International ACM SIGIR
Conference on Research and Development in Information Retrieval,
2003, pp. 127–134.
[10] S. Feng, R. Manmatha, and V. Lavrenko, “Multiple Bernoulli
relevance models for image and video annotation,” in CVPR ’04:
Proceedings of the IEEE Computer Society Conference on Computer
Vision and Pattern Recognition, vol. 2, 2004, pp. 1002–1009.
[11] J. Jeon, V. Lavrenko, and R. Manmatha, “Automatic image annotation and retrieval using cross-media relevance models,” in
SIGIR ’03: Proceedings of the 26th Annual International ACM SIGIR
Conference on Research and Development in Information Retrieval.
ACM, 2003, pp. 119–126.
[12] J. Jeon and R. Manmatha, “Using maximum entropy for automatic
image annotation,” in CIVR ’04: Proceedings of the 3rd International
Conference on Image and Video Retrieval, 2004, pp. 24–32.
[13] D. M. Blei, A. Y. Ng, and M. I. Jordan, “Latent Dirichlet allocation,” Journal of Machine Learning Research, vol. 3, pp. 993–1022,
2003.
[14] T. Hofmann, “Probabilistic latent semantic analysis,” in UAI ’99:
Proceedings of 15th Conference on Uncertainty in Artificial Intelligence,
1999, pp. 289–296.
[15] ——, “Collaborative filtering via Gaussian probabilistic latentsemantic analysis,” in Proceedings of the 26th Annual International
ACM SIGIR Conference on Research and Development in Information
Retrieval. ACM Press, 2003, pp. 259–266.
[16] T. Iwata, S. Watanabe, T. Yamada, and N. Ueda, “Topic tracking
model for analyzing consumer purchase behavior,” in IJCAI ’09:
Proceedings of 21st International Joint Conference on Artificial Intelligence, 2009, pp. 1427–1432.
[17] T. Iwata, T. Yamada, and N. Ueda, “Probabilistic latent semantic
visualization: topic model for visualizing documents,” in KDD’08: Proceedings of the 14th ACM SIGKDD International Conferenceon Knowledge Discovery and Data Mining. ACM, 2008, pp. 363–371.
[18] V. N. Vapnik, The nature of statistical learning theory. Springer,
1995.
[19] G. Csurka, C. Dance, J. Willamowski, L. Fan, and C. Bray, “Visual
categorization with bags of keypoints,” in ECCV International
Workshop on Statistical Learning in Computer Vision, 2004.

JOURNAL OF LATEX CLASS FILES, VOL. 6, NO. 1, JANUARY 2007

NATM
Corr-LDA
2200

4050

2600

4000

2400

3950

perplexity

perplexity

perplexity

2100

3800

3650
3600
0

20

40

60

number of topics(a) Hatena

80

100

1400

1000
0

20

40

60

80

100

1700

1500

1200

NATM
Corr-LDA

1800

1600

1400

3700

2000

1900

1800
1600

3750
2050

2000

2000

3850

NATM
Corr-LDA

2100

2200

3900
2150

2200
NATM
Corr-LDA

perplexity

2250

14

1300
0

20

40

number of topics(b) Delicious

60

80

100

0

20

40

60

number of topics

number of topics(c) Flickr(d) Patent

80

100

Fig. 13. Perplexities of held-out annotations with different numbers of topics in social annotation data (a)(b)(c), and indata without content unrelated annotations (d).

[20] X. Wu, L. Zhang, and Y. Yu, “Exploring social annotations for thesemantic web,” in WWW ’06: Proceedings of the 15th International
Conference on World Wide Web. ACM, 2006, pp. 417–426.
[21] D. Zhou, J. Bian, S. Zheng, H. Zha, and C. L. Giles, “Exploring social annotations for information retrieval,” in WWW ’08:
Proceedings of the 17th International Conference on World Wide Web.
ACM, 2008, pp. 715–724.
[22] T. L. Griffiths, M. Steyvers, D. M. Blei, and J. B. Tenenbaum,“Integrating topics and syntax,” in In In Advances in Neural
Information Processing Systems, vol. 17, 2005, pp. 537–544.
[23] C. Chemudugunta, P. Smyth, and M. Steyvers, “Modeling generaland specific aspects of documents with a probabilistic topic
model,” in Advances in Neural Information Processing Systems 19,
B. Schölkopf, J. Platt, and T. Hoffman, Eds. MIT Press, 2007, pp.
241–248.
[24] L. Dietz, S. Bickel, and T. Scheffer, “Unsupervised predictionof citation influences,” in Proceedings of the 24th international
conference on Machine learning, ser. ICML ’07. New York, NY,
USA: ACM, 2007, pp. 233–240.
[25] L.-J. Li, R. Socher, and L. Fei-Fei, “Towards total scene understanding: Classification, annotation and segmentation in an
automatic framework,” in IEEE Computer Society Conference on
Computer Vision and Pattern Recognition. Los Alamitos, CA, USA:IEEE Computer Society, 2009, pp. 2036–2043.
[26] N. Nguyen and R. Caruana, “Classification with partial labels,”in KDD ’08: Proceedings of the 14th ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining. ACM, 2008,
pp. 551–559.
[27] T. L. Griffiths and M. Steyvers, “Finding scientific topics,” Proceedings of the National Academy of Sciences, vol. 101 Suppl 1, pp.
5228–5235, 2004.
[28] T. Minka, “Estimating a Dirichlet distribution,” M.I.T., Tech. Rep.,
2000.
[29] K. Nigam, J. Lafferty, and A. McCallum, “Using maximum entropy for text classification,” in Proceedings of IJCAI-99 Workshop
on Machine Learning for Information Filtering, 1999, pp. 61–67.
[30] V. Vapnik, Statistical Learning Theory. New York: Wiley, 1998.
[31] R. Raina, Y. Shen, A. Y. Ng, and A. McCallum, “Classification
with hybrid generative / discriminative models,” in Advances in
Neural Information Processing Systems, 2004.
[32] C.-F. Lin and S.-D. Wang, “Fuzzy support vector machines,” IEEE.
Transactions on Neural Networks, vol. 13, no. 2, pp. 464–471, 2002.
[33] X. Yang, Q. Song, and Y. Wang, “Weighted support vector
machine for data classification,” International Journal of Pattern
Recognition and Artificial Intelligence, vol. 21, no. 5, pp. 961–976,
2007.
[34] T. Iwata, K. Saito, and T. Yamada, “Recommendation method
for extending subscription periods,” in KDD ’06: Proceedings of
the ACM SIGKDD Conference on Knowledge Discovery and Data
Miniining, 2006, pp. 574–579.
[35] S. F. Chen and R. Rosenfeld, “A Gaussian prior for smoothing maximum entropy models,” Computer Science Department,
Carnegie Mellon University, Tech. Rep. CMUCS–99–108, 1999.
[36] D. C. Liu and J. Nocedal, “On the limited memory BFGS method
for large scale optimization,” Mathematical Programming, vol. 45,
no. 3, pp. 503–528, 1989.
[37] K. Lang, “NewsWeeder: learning to filter netnews,” in ICML ’95:
Proceedings of the 12th International Conference on Machine Learning,
1995, pp. 331–339.

[38] D. G. Lowe, “Distinctive image features from scale-invariant
keypoints,” International Journal of Computer Vision, vol. 60, no. 2,
pp. 91–110, 2004.
[39] Y. W. Teh, M. I. Jordan, M. J. Beal, and D. M. Blei, “Hierarchical
Dirichlet processes,” Journal of the American Statistical Association,
vol. 101, no. 476, pp. 1566–1581, 2006.

PLACE
PHOTO
HERE

Tomoharu Iwata received the B.S. degree inenvironmental information from Keio University
in 2001, the M.S. degree in arts and sciencesfrom the University of Tokyo in 2003, and the
Ph.D. degree in informatics from Kyoto University in 2008. He is currently a research scientist
at Learning and Intelligent Systems ResearchGroup of NTT Communication Science Laboratories, Kyoto, Japan. His research interests include data mining, machine learning, information
visualization, and recommender systems.

PLACE
PHOTO
HERE

Takeshi Yamada received the B.S. degree inmathematics from the University of Tokyo in
1988 and the Ph.D. degree in informatics from
Kyoto University in 2003. He was a Leaderof Emergent Learning and Systems ResearchGroup of NTT Communication Science Laboratories and is currently a Senior Manager of
NTT Science and Core Technology Laboratory
Group. His research interests include Data Mining, Statistical Machine Learning, Graph Visualization, Metaheuristics and Combinatorial Opti-

mization.

Naonori Ueda received the B.S., M.S., andPh D degrees in Communication Engineeringfrom Osaka University, Osaka, Japan, in 1982,
1984, and 1992, respectively. In 1984, he joined
PLACE
the Electrical Communication Laboratories, NTT,
PHOTO
Japan. In 1991, he joined the NTT CommunicaHERE
tion Science Laboratories. His current researchinterests include parametric and non-parametric
Bayesian approach to machine learning, patternrecognition, data mining, signal processing, andcyber-physical systems. Currently, he is a director of NTT Communication Science Laboratories.