2008 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology

Interactive Spam Filtering with Active Learning and Feature Selection
Masayuki Okabe
Toyohashi University of Technology
Tenpaku 1-1, Toyohashi, Aichi, Japanokabe@imc.tut.ac.jp

Seiji Yamada
National Institute of Infomatics
Chiyoda, Tokyo, Japanseiji@nii.ac.jp

Abstract== A-Z medications to choose from ==We give you FreeViagraPills (Free you 4-12 pills with any order)This paper proposes an interactive spam ﬁltering methodthat utilizes active learning and feature selection. Selecting effective features are very important in spam ﬁltering because spam mails include so many meaninglesswords that are slightly different from each other. Thus selecting effective and ineffective features is promising approach.Although traditional feature selection methods havebeen done based on some amount of labeled training data,
this assumption does not hold in interactive spam ﬁltering. We propose a method to selecting effective features
through active learning in spam ﬁltering using naive Bayes
approach. Experimental results show that our method outperforms traditional methods that operate with no feature
selection.

== ViagraPill ==== Cialix Pills ==== PenisGrowth Pack ==== SQMA ==== Phentrimine ==== Levitr ==== Tramadol ==== FemaleViagra ==user

Claim your Free 4-12 ViagraPills here with us

ham or spam?

Figure 1. Spam Filtering Process

ﬁer is deﬁned by the ﬁltering method used in a spam ﬁltering system, such as naive Bayes or support vector machines.
Uncertainty sampling is a type of active learning techniquethat tries to reduce the hypothesis space to make classiﬁers.
On the other hand, there is an active learning technique thattries to reduce estimated error that is calculated by the distribution of estimated conditional class probability [4]. The
results of the experiments in which this error reduction approach is tested on naive Bayes show good performancecompared with uncertainty sampling.
The performance of ﬁltering is inﬂuenced by not only theamount of training data, but also the feature set. Feature selection is known to be a good approach [5]. In classiﬁcation
learning, like ﬁltering, feature selection methods that use
class information are promising. However a certain amountof labeled data is necessary for those methods to work well;this is a serious problem when applying feature selection toactive learning. We propose a method to solve this problem.
Our method assumes classess of each unlabeled data can be
estimated using conditional class probability during active
learning. A system can build a pseudo set of labeled data
enough to calculate a feature’s score of importance. Once
we can calculate the score, we need to determine a threshold to decide the amount of necessary features. Our method
set the threshold to a point where score of feature decreases
the most in a sorted list.

1. Introduction
There is a report that 96.5% of e-mails ﬂowing in the Internet are spams [1]. They not only make trafﬁc jams in theInternet, but also annoy users. Most of recent e-mail clients
adopt some form of spam ﬁltering functionality. However
they often fails to remove spams at it’s starting point because they do not have enough information about “ham”
and “spam” mails early in their usage of the system. Although users can give the information explicitly by pushinga button that indicates a spam mail to the system, this is usually frustrating task if there are a lot of spams. Some kindof efﬁcient feedback framework is necessary.
We propose to apply active learning [2] as such framework. In this framework, systems actively select a mail andurge users to indicate that it is “ham” or “spam” as shownin Figure 1. This learning technique tries to reduce the costof data labeling, i.e. reducing the number of data to label byﬁnding effective data to make ﬁlter. Several active learningtechniques have been proposed so far. One of the most popular technique is uncertainty sampling [3] that selects themost uncertain data as a candidate to be labeled. A classi978-0-7695-3496-1/08 $25.00 © 2008 IEEE
DOI 10.1109/WIIAT.2008.336“spam !”

& 400 more meds to choose from165

[4]. This approach estimates the expected error E using
a loss function L that calculates the difference between thetrue distribution of the class probability P (c|x) and the estimated one using a loss function.
E=
L(P (c|x), P̂ (c|x))P (x)(4)

2. Spam Filtering with Naive Bayes Classiﬁer
2.1. Naive Bayes Classiﬁer
Naive Bayes is a basic classiﬁcation technique that is
simple and easy to implement but shows relatively good
performance [6]. Although there are other classiﬁers thatshow better performance such as Support Vector Machines,
many spam ﬁlter implementations are based on naive Bayes
approach because of its simplicity.
The classiﬁer calculates the probability for each mail tobelong to “ham” or “spam” based on the Bayes theorem.
Suppose we want to classify an e-mail x ∈ X into a classc ∈ C. The conditional probability P (c|x) that a data be(x|c)
longs to a class is written by P (c|x) = P (c)Pin which
P (x)Bayes theorem is applied.
Naive Bayes classiﬁers adopts a generative model thatassumes data x are produced by ﬁrst selecting a class c andthen generating an instance x given c. Moreover, it assumes
the independence of features of a data x. According to thegenerative approach, the conditional probability P (c|x, θ)that a data x belongs to a class c is written as follows.
P (c|θ)Πwk ∈x P (wk |c, θ)
c∈C P (c|θ)Πwk ∈x P (wk |c, θ)P (c|x, θ) = x

As a loss function, we use the log loss function described
below.
L=−P (c|x) log P̂ (c|x)(5)
c∈C

Since true distribution is unknown, we replace P (c|x) toP̂ (c|x). As a result, an expected loss when adding a data is
calculated by the following formula.
E=

1 −P̂ ∗ (c|x) log P̂ ∗ (c|x)
|P |

(6)

x∈P c∈C

where P̂ ∗ (c|x) is conditional class probability when adding
a data (x, c) selected by each active learning process. This
procedure repeats to consider each unlabeled data in thepool as a feedback candidate. For each data, it considers
each possible label c for x, and adds each pair (x, c) to thetraining data set to make temporary new training data bywhich a temporal new classiﬁer is created. By using this
temporal classiﬁer, resulting expected losses are estimated.
Each estimated losse E(x, c) are aggregated by multiplying
its present conditional class probability P (c|x).

(1)

Here wk is the kth word that appears in x, θ = (θc , θw|c ) isa set parameters that includes the class prior and the probability of generating word w class c. Using maximum aposteriori estimation, each parameter is calculated as follows.

1 + x∈X δ(x, c)
θ̂c =
(2)
|C| + |X|

1 + x∈X N (wk , x)δ(x, c)(3)θ̂wk |c =|V | |V | + k=1 x∈X N (wk , x)δ(x, c)

3. Feature Selection through Active Learning
3.1. Feature selection by Information Gain
Feature selection is a technique for improving classiﬁcation performance by removing unnecessary features. Although there are several measures to select effective featuresin text classiﬁcation, we use information gain since it is oneof most effective techniques [5]. Information gain (IG) is
calculated by the following formula.
IG(w) = −P (c) log P (c)(7)

where V is all kinds of words that are used to estimate parameters. N (wk , x) is word frequency of a word wk appears in x. δ(x, c) is a function that returns 1 if the class ofx equals to c and 0 otherwise.

2.2. Naive Bayes with Active Learningc∈C

Until now, we have explained a classiﬁcation techniquewith an assumption that we have enough training data (i.e.
enough mails categorized either “ham” or “spam”). However such assumption is unrealistic. When we start to use amail client, there are no classiﬁed mails. We need to identify spams to the client one by one.
In this interactive process, active learning tries to reducelabeling cost by selecting data that is expected to improvethe classiﬁcation performance most. We adopt a samplingtechnique for error reduction approach proposed by Roy+P (w)

P (c|w) log P (c|w)

c∈C+P (w̄)P (c|w̄) log P (c|w̄)c∈C

Where P (c) is the probability that data with class c is selected among all training data, P (c|w) is the probability
that data with class c is selected among all data in which
a word w appears, and P (c|w̄) is the probability that data166with class c is selected among all data in which a word w
does not appear.
When using IG in active learning, there are mainly two
problems. The ﬁrst one is the lack of training data. Since
there are few training data in the early stage of active learning, the conﬁdence of the value of IG is low. The second
is how to decide the amount of features to use. Although
this problem is not limited to the case of active learning, it
is more serious because the conﬁdence of IG is low. We
explain the solution of these problems.

Algorithm 1 Procedure for active learning with feature selection
1: V : vocabulary set
2: wi : ith word in V
3: Conduct sample selection and update probabilities
4: Calculate conditional probability P (c|x) for each x
5: Select x that has the probability more than Tconf
6: Make a pseudo training data set Dpse that consists oftrue and pseudo training data.
7: for i = 1 to |V | do
8:
calculate IG(wi ) using Dpse
9: end for
10: Sort V in descending order
11: Find the largest gap point and create new vocabulary set
V∗
12: return V ∗3.2. Selection of a feature set though active
learning process
We summarize again each problem when applying feature selection in active learning and show the solution foreach problem. The ﬁrst problem is how to prepare enoughlabeled data. The normal feature selection technique needssome amount of labeled training data. However there aresmall number of labeled data in the early stage of active
learning. We propose a solution for the problem by assuming the class of unlabeled data that have some certain
conﬁdence of their class labels. we assume the class labelof unlabeled data by the probability P (c|x) with large differences between the two classes, i.e. “ham” and “spam”
class. Moreover even if there are enough unlabeled datawith high probability of conditional class conﬁdence, it is
difﬁcult to discriminate the important features if the amountof data in each class is biased to one class. According to theabove consideration, we adopt two thresholds to prepare thesource data for selecting important features to classify.

4. Experiments
In the experiments, we used an e-mail collection that isused in the TREC Spam Filtering Track [7]. This data set
contains about 90,000 e-mails that are sorted by date. Since
this data is too large to simulate active learning, we usedﬁrst 1000 mails listed in the index ﬁle in this data set anddivide them two data sets. They are labeled (a) 1-500, (b)501-1000. As shown in Table 1, their composition differ
especially in the pool set. Each data set consists of 500
data elements in which ﬁrst 100 data are used for the poolof unlabeled training; the remaining 400 are used for testing. The process of active learning starts from no labeledtraining data, and then add labeled data one by one until all
100 data elements have been processed. E-mails are preprocessed by removing only symbols. Each data are represented as a bag of words.
We compared our method with other two ones.

1. Tconf : threshold for the conditional probability ofclass conﬁdence of each unlabeled data.
2. Tbal : threshold for the balance of the amount of training data in the classes.

1. ELOSS-FS : This is our proposed method. Parameters
Tconf and Tbal are set to 0.9 and 0.1, respectively.

Both thresholds are lower limits that must be satisﬁed.
Tconf controls the amount of source data for feature selection. Tbal is a parameter to prevent from making an unbalanced source data set where data with only one class occupies the set. This is the solution for the ﬁrst problem. The
second problem is how to deﬁne the amount of useful features. To cope with this problem, we propose to deﬁne theamount of features by ﬁnding the largest gap point. Gap
points can be found by ﬁrstly sorting the score of IG(w)s,
and secondly checking the difference of the score between
rank k and rank k + 1. If the largest gap point is K, we
select features until the Kth feature in the sorted list of IG.
Algorithm 1 summarizes the procedure of active learning
accompanied with feature selection.

2. ELOSS : naive Bayes based active learning with sample error reduction
3. UNCERT : naive Bayes based active learning with uncertainty sampling
The system ELOSS is naive Bayes based active learningwith sample error reduction approach that is the basis of
our proposed method. Our method merge feature selection procedure to this method. This base method uses allfeatures. The system UNCERT is also naive Bayes based
active learning with uncertainty sampling. This techniqueselects a data that is the most difﬁcult to classify, namely
the difference between class probability.

167

(b) 501-1000
1

0.8

0.8

0.6

0.6

Accuracy

Accuracy(a) 1-500
1

0.4

0.2

0

0.2

ELOSS-FSELOSS
UNCERT
0

10

20

30

40

50

60

70

80

0.4

90

0

100

ELOSS-FSELOSS
UNCERT
0

10

Number of labeled data

20

30

40

50

60

70

80

90

100

Number of labeled data

Figure 2. Results of experimentsout feature selection and an approach based on uncertainty
sampling.

Table 1. Composition in two data sets
1-500
501-1000
ham spam ham spam
pool
77
23
15
85
test
31
369
70
330

References[1] Sophos’s report: http://www.sophos.com/pressofﬁce/news/articles/2008/07/dirtydozjul08.html,2008.

Figure 2 shows the results on two data sets. On alldata sets, our method shows better or comparative performance to other two methods. For Data 1-500, ELOSS-FS
and ELOSS are comparative during the early stage (until
about 40 data are added). In the following stage, ELOSSFS mostly outperforms ELOSS. UNCERT shows poor performance in this data set. We observed that UNCERT selects mostly ham mails in the early stage of active learning
though ELOSS and ELOSS-FS select ham and spam alternately. The difference between their selection patterns may
be the reason of the results in Data 1-500.
Also, for Data 501-1000, UNCERT slightly outperforms
ELOSS-FS until about 20 data are added. However fromthe point, ELOSS-FS gets better, and UNCERT decreasing
to the same performance of ELOSS.

[2] S. Tong, D. Koller, Support vector machine active
learning with applications to text classiﬁcation. In
Proceedings of the Seventeenth International Conference on Machine Learning , 2001.
[3] D. Lewis, W. Gale, A sequential algorithm for training text classiﬁers, In Proceedings of the International
ACM-SIGIR Conference on Research and Development in Information Retrieval, pp. 3-12, 1994.
[4] N. Roy and A. McCallum, Toward Optimal Active
Learning through Sampling Estimation of Error Reduction, In Proceedings of the Eighteenth International Conference on Machine Learning, pp.441-448,
2001.
[5] Y. Yang and J. O. Pederson, Feature selection in statistical learning of text categorization, In Proceedings ofthe Fourteenth International Conference on Machine
Learning, pp.412-420, 1997.

5. Conclusions
In this paper, we propose a feature selection approachwith active learning. Our approach iteratively applies information gain based feature selection through active learning.
To cope with the lack of labeled training data, we attachedpseudo labels estimated by temporal conditional class probabilities. Also, in order to determine the amount of features,
we set a threshold by ﬁnding the largest gap among information gain scores. Experimental results showed that our proposed method outperformed a conventional approach with-[6] A. McCallum, K. Nigam, A comparisonof event models for naive Bayes text classiﬁcation, In Proceedingsof AAAI-98 Workshop on Learning for Text Categorization, 1998.
[7] G. Cormack and T. Lynam, TREC 2005 Spam Track
Overview, In Proceedings of the Fourteenth Text Retrieval Conference, 2005.

168