Text Categorization is the task of assigning prede ned categories to text documents. It can provide conceptual views of document collections and has many important applications in the real world. Nowadays, most of the research on text categorization has focused on mapping text documents to a set of categories among which structural relationships hold. Without loss of generality, let us assume that a classi er entrusted with recognizing documents of a given category outputs a degree of membership, usually a value in [0,1]. The behavior of any such classi er typically depends on an acceptance threshold, which turns the degree of membership into a dichotomous decision. In principle, the problem of nding the best acceptance thresholds for a set of classi ers related by taxonomic relationships is a di cult problem. Hence, any proposal aimed at nding suboptimal solutions to this problem may have great importance, especially in the eld of hierarchical text categorization. In this paper, we make an experimental assessment of a greedy threshold selection algorithm aimed at nding a suboptimal combination of thresholds in a hierarchical text categorization setting. The quadratic complexity of the algorithm makes it easier to nd good suboptimal solutions even for large taxonomies. Experimental results, performed on Reuters data collections, show that the proposed approach is able to nd suboptimal solutions with small computational complexity.
The new information era has widely changed our lives thanks to a great deal of new possibilities to create content (i.e., knowledge) and share it all over the world throughout new and widespread communication systems. Human beings have always known the importance of organizing entities or notions in hierarchies, according to the \divide et impera" paradigm. In the last few decades, with the advent of modern information systems, this concept has been widely employed to partition items and concepts into smaller parts, each being e ectively and e ciently managed. The contribution of this approach is particularly evident in the Web 2.0, where the main and most crucial knowledge bases exploit it in order to organize large collections of web pages1, articles2 or emails3 in hierarchies of topics. This organization allows to focus on a speci c level of details ignoring specialization at lower levels and generalization at upper levels. In this scenario, the main goal of automatic categorization systems is to deal with reference taxonomies in an e ective and e cient way {the corresponding research sub eld being Hierarchical Text Categorization (HTC).
Nowadays there is a great amount of contributions in HTC focusing, in
particular, on how to build training sets, selecting features, and learning
methods. In our opinion, a further important issue is concerned with the
fact that, in real-world scenarios, data is typically characterized by
imbalance. In fact, relevant and irrelevant documents (i.e., positive and negative
examples, respectively) are typically imbalanced, turning classi ers trained
with the same percent of positive and negative examples into inadequate
tools. According to [
Without loss of generality, let us assume that a classi er for a category ci 2 C usually consists of a function CSVi : D ! [0; 1]. Given a document dj , CSVi(dj ) returns a categorization status value for it that represents the evidence for the fact dj 2 ci. The behavior of ci depends on an acceptance threshold i, such that CSVi(dj ) i is interpreted as dj 2 ci, and conversely CSVi(dj ) < i is interpreted as dj 2= ci. In HTC, this is transposed into a multidimensional space, i.e., the de nition of a vector of thresholds .
In principle, how to nd the best acceptance thresholds for a set of
classi ers related by taxonomic relationships is a di cult problem. As for TC,
there are various policies for determining the acceptance threshold, the most
important distinction being whether it is analytically or experimentally
derived [
In this paper, we perform an experimental assessment of a greedy
threshold selection algorithm aimed at nding a suboptimal combination of
thresholds in the context of Progressive Filtering (PF), the hierarchical text
categorization setting proposed in [
2see e.g., Wikipedia (http://www.wikipedia.org) and Reuters
(http://www.reuters.com/)
3see e.g., Thunderbird 3 (http://www.mozillamessaging.com/thunderbird/)
solutions while maintaining a quadratic complexity, which makes it easier
to nd good suboptimal solutions even for large taxonomies [
The rest of the paper is organized as follows: in section 2, we brie y recall the PF approach. In section 3 we describe TSA, putting into evidence the theoretical background that allowed to build the algorithm and its computational bene ts. Experiments and results are illustrated in section 4. Conclusions discussed in section 5 end the paper. 2
A way to implement Progressive Filtering (PF) consists of unfolding the given taxonomy into pipelines of classi ers, as depicted in Figure 1. Each node of the pipeline is a binary classi er able to recognize whether or not an input belongs to the corresponding class (i.e., to the corresponding node of the taxonomy).
In principle, PF could be applied to classify any kind of item: images, audios, videos, textual documents, and so on. In this paper we are interested in using PF for hierarchical text categorization, so that textual documents (documents for short hereinafter) have been considered.
Given a taxonomy, where each node represents a classi er entrusted with recognizing all corresponding positive inputs (i.e., interesting documents), each input traverses the taxonomy as a \token", starting from the root. If the current classi er recognizes the token as positive, it passes it on to all its children (if any), and so on. A typical result consists of activating one or more branches within the taxonomy, in which the corresponding classi ers have been activated by the given token. Let us note that partitioning the taxonomy in pipelines gives rise to a set of new classi ers, each represented by a pipeline. For instance, the taxonomy depicted in Figure 1 gives rise to six corresponding pipelines.
As we know from classical text categorization, given a set of documents D and a set of labels C, a function CSVi : D ! [0; 1] exists for each ci 2 C. The behavior of ci is controlled by a threshold i, responsible for relaxing or restricting the acceptance rate of the corresponding classi er. Let us recall that, given d 2 D, CSVi(d) i is interpreted as a decision to categorize d under ci, whereas CSVi(d) < i is interpreted as a decision not to categorize d under ci.
In PF, let us still assume that CSVi exists with the same semantics adopted in the classical case. Considering a pipeline , composed by n classi ers, the acceptance policy strictly depends on the vector of thresholds = h 1; 2; ; ni that embodies the thresholds of all classi ers in . In order to categorize d under , the following constraint must be satis ed: for k = 1::n, CSVi(d) k. On the contrary, d is not categorized under ci in the event that a classi er in rejects it. In so doing, a classi er may have di erent behaviors, depending on which pipeline it is embedded. As a consequence, each pipeline can be considered in isolation from the others. For instance, given 1 = hC1; C2; C3i and 2 = hC1; C2; C4i, the classi er C1 is not compelled to have the same threshold in 1 and in 2 (the same holds for C2).
Actually, the proposed approach performs a sort of \ attening" though preserving the information about the hierarchical relationships embedded in a pipeline. For instance, the pipeline hC1; C2; C3i actually represents the classi er C3, although the information about the existing subsumption relationships are preserved (i.e., C3 C2 C1, where \ " denotes the usual covering).
In PF, given an utility function4, we are interested in nding an e ective (and computationally \light") way to reach a sub-optimum in the task of determining the best vector of thresholds. To this end, for each pipeline a sub-optimal combination of thresholds is searched for, considering the actual ratio between positive and negative examples, which in turn depends on the given scenario. Unfortunately, nding the best acceptance thresholds is a di cult task. In fact, exhaustively trying each possible combination of thresholds (brute-force approach) is unfeasible, the number of thresholds being in nite. However, the brute-force approach can be approximated by de ning a granularity step that requires to assess only a nite number of points in a range [0; 1] in which the thresholds are permitted to vary with step . This \relaxed" brute force algorithm (RBF for short) for calibrating thresholds would be very helpful in the task of nding a sub-optimal solution, 4Di erent utility functions (e.g., precision, recall, F , user-de ned) can be adopted, depending on the constraint imposed by the underlying scenario. although still too heavy from a computational point of view. Thus, in this paper we propose a novel Threshold Selection Algorithm (namely, TSA) devised to deal with this problem, which maintains the capability of nding a near-optimum solution characterized by a low time complexity. 3.2
Utility functions typically adopted in TC, and therefore in HTC, are nearlyconvex with respect to the acceptance threshold. In Figure 2 three typical trends of utility functions are depicted (precision, recall, and F1).
Let us note that setting the threshold of a classi er to 0, no matter which utility function is adopted, forces the classi er to reach its maximum error in terms of false positives (FP). On the other hand, setting the threshold to 1 forces the classi er to reach its maximum error in terms of false negatives (FN).
Due to the shape of the utility function and to its dependence on FP and FN, it becomes feasible to search its maximum around a restricted range (i.e., a subrange of [0; 1]) towards a de ned direction. In particular, bearing in mind that the lower the threshold the less restrictive the classi er, we can build a greedy bottom-up algorithm for selecting decision threshold that relies on two functions: repair (R), which operates on a classi er C by increasing or decreasing its threshold {i.e., R(up; C) and, R(down; C), respectively{ until the selected utility function reaches and maintains a local maximum. calibrate (C), which operates going downwards from the given classi er to its o spring by repeatedly calling R. It is intrinsically recursive and at each step it calls R to calibrate the current classi er.
Given a pipeline = hC1; C2; ; CLi, where L is its depth, TSA is then de ned as follows (all thresholds are initially set to zero): T SA( ) := f or k = L downto 1 do C(up; Ck) which indicates that C is applied to each node of the pipeline, starting from the leaf (k = L).
Under the assumption that p is a structure that contains all information about a pipeline, including the corresponding vector of thresholds and the utility function to be optimized, the pseudo-code of TSA is: function TSA(p:pipeline): for k:=1 to p.length
do p.thresholds[i] = 0 for k:=p.length downto 1
do Calibrate(up,p,k) return p.thresholds end TSA The Calibrate function is de ned as follows: and
C(up; Ck) := R(up; Ck); k = L C(up; Ck) := R(up; Ck) + C(down; Ck+1); k < L (2) (3) C(down; Ck) := R(down; Ck); k = L
C(down; Ck) := R(down; Ck) + C(up; Ck+1); k < L
where the + operator actually denotes a sequence operator, meaning that
in the formula a + b action a is performed before action b. In pseudo-code:
function Calibrate(dir:{up,down}, p:pipeline, level:integer):
Repair(dir,p,level)
if level < p.length then Calibrate(toggle(dir),p,level+1)
end Calibrate
where toggle is a function that reverses the current direction, and Repair is
de ned as:
function Repair(dir:{up,down}, p:pipeline, level:integer):
delta := (dir = up) ? p.delta : -p.delta
best_threshold := p.thresholds[level]
max_uf := p.utility_function()
uf := max_uf
while uf >= max_uf * 0.8 and p.thresholds[level] in [
The factor 0:8 is used to limit the impact of local minimums during the search.
Once calculated the sub-optimal combination of thresholds for a given imbalance, the pipelines are ready to be used in the corresponding scenario. Let us note, here, that this combination depends on both the adopted dataset and the actual input imbalance. In fact, as noted in [10], di erent goals for the system lead to di erent optimal behaviors. 3.3
Searching for a sub-optimal combination of thresholds in a pipeline can be actually viewed as the problem of nding a maximum in a utility function F that depends on the corresponding thresholds : = argmax F ( ) (4)
Unfortunately, the above task is characterized by a high time complexity, being actually a problem of meta-learning (i.e., a learning problem whose instances are in fact learning problems themselves). To calculate the computational complexity, let us de ne a granularity step that requires to visit only a nite number of points in a range [ min; max], 0 min < max 1, in which the thresholds could vary with step . Therefore, p = b 1 ( max min)c being the maximum number of points to be checked for each classi er in a pipeline and L being the length of the pipeline, the average time of TSA, T (T SA), is proportional to (L + L2) p ( max min), which implies that TSA has complexity O(L2). Hence, the time complexity is quadratic with the number of classi ers embedded by a pipeline. As already noted, a comparison between TSA and the brute-force approach is unfeasible, the generic element of the threshold vector being a real number. Nevertheless, experimental results show that the e ectiveness of TSA is almost identical to the one obtained by running RBF , in which only p points are checked for each classi er in a pipeline. Note that the average time of RBF , T (RBF ), is proportional to pL, which in turns implies that its computational complexity is O(pL).
To show the drastic complexity reduction brought by the TSA algorithm, let us consider a pipeline composed of 4 classi ers (i.e., L = 4), and p = 100. In this case the orders of magnitude of T (RBF ) and T (T SA) are 108 whereas 103, respectively.
It is also important to note that, due to the enormous computational time that can be reached, the RBF approach should be applied in practice only by setting p to a value much lower than the one applicable with TSA. For instance, with a ratio of 10 2, i.e., pRBF = 20 and pT SA = 2000, T (RBF ) / 160; 000 and T (T SA) / 20; 000. In other words, TSA is still 8 times faster than RBF (even considering max = 1 and min = 0), while ensuring a better result due to the higher granularity. 4
The Reuters Corpus Volume I (RCV1-v2) [
Experiments have been performed on a SUN Workstation with two Opteron
280, 2Ghz+ and 8Gb Ram. To perform experiments we customized the
X.MAS [
Experiments have been carried out by using classi ers based on the wk
NN technology [
Experiments, performed on a balanced dataset of 2000 documents for each class, have been focused on calculating the performance improvement of TSA vs. RBF. A step T SA = 5 10 4 (hence, pT SA = 2 103) has been adopted to increment thresholds in TSA; whereas a step RBF = 0:05 (hence, pRBF = 20) has been adopted for the RBF approach5. Table 1 illustrates the results comparing the time spent, in seconds and hours, by RBF and TSA. Each row of the table corresponds to the time spent to perform a calibrate step so that the last row corresponds to the total elapsed time. The last column clearly shows that, the ratio between the time spent by the two algorithms is approximately constant. Table 1 shows that, as expected, TSA is faster than RBF notwithstanding the imposed granularity step. To show that the overall performances of PF are not worsened by the adoption of TSA vs. RBF, we performed further experiments aimed at comparing the performance obtained by applying TSA vs. the performance obtained by 5the motivation of this choice has been discussed in the previous section applying RBF. In particular, experiments have been performed by assessing the behavior of PF in terms of F1 in presence of di erent ratios of positive examples vs. negative examples {i.e., from 2 1 to 2 7. Results, summarized in Table 2, show that the performance of TSA is always better than the one obtained with RBF. This is due to the fact that, as previously pointed out, TSA worked with a higher granularity (i.e., pRBF =pT SA = 20=2000 = 10 2).
Taking into account these results, we can also establish the average range of search in which the TSA found a maximum of the utility function with pRBF = 20, pT SA = 2000, and L = 4: TRBF = 8 TT SA = 28 TT SA {i.e., = 0:29. This further interesting result shows that TSA succeeds in nding the sub-optimum within less that the 30% of the search range. For obvious reasons, max min decreases while climbing a pipeline from the leaf to the root. 5
In this paper, after proposing TSA, a threshold selection algorithm for hierarchical text categorization, we made an experimental assessment aimed at nding a suboptimal combination of thresholds in a hierarchical text categorization setting. The quadratic complexity of the algorithm makes it easier to nd good suboptimal solutions even for large taxonomies. Experimental results, performed on Reuters data collections, show that the proposed approach is able to outperform a relaxed version of the brute force approach. Furthermore, TSA is also very e ective in dealing with the input imbalance that typically occurs in real-world scenarios. [10] D. D. Lewis. Evaluating and optimizing autonomous text classi cation systems. In SIGIR '95: Proceedings of the 18th annual international