The curse of dimensionality is a well-recognized problem in the field of document filtering. In particular, this concerns methods where vector space models are utilized to describe the document-concept space. When performing content classification across a variety of topics, the number of different concepts (dimensions) rapidly explodes and as a result many techniques are rendered inapplicable. Furthermore the extent of information represented by each of the concepts may vary significantly. In this paper, we present a dimensionality reduction approach which approximates the user's preferences in the form of value function and leads to a quick and efficient filtering procedure. The proposed system requires the user to provide preference information in the form of a training set in order to generate a search rule. Each document in the training set is profiled into a vector of concepts. The document profiling is accomplished by utilizing Wikipedia-articles to define the semantic information contained in words which allows them to be perceived as concepts. Once the set of concepts contained in the training set is known, a modified Wilks' lambda approach is used for dimensionality reduction by ensuring minimal loss of semantic information.
Most information retrieval systems are based on free language searching, where the user can compose any ad hoc query by presenting a list of keywords or a short phrase to describe a topic. The popularity of phrase-based methods can largely be explained by their convenience for the users. However, the ease of usage comes with a few drawbacks as well. While exploring a new topic or searching within an expert domain with specialized terminology it can be surprisingly hard to find the right words for getting the relevant content. To cope with the ambiguity of the vocabulary, concept-based document classification techniques have been proposed, as concepts by definition cannot be ambiguous. However, the use of concepts instead of keywords is only part of the solution. If the filtering methods rely on vector-space models of documents and concepts, a dimension reduction technique comes in handy. Instead of training the classifiers using the entire concept-base, the learning of filtering models is improved by restricting the space to those concepts that are most relevant for the given task.
In this paper, we introduce, Wilks-VF, a light-weight concept selection method
inspired by Wilks’ lambda to reduce the curse of dimensionality. In Wilks-VF the
document classification task is carried out in the following three stages: 1) Once
the user has supplied a training sample of relevant and irrelevant documents, a
semantic profiler is applied to build a document-concept space representation.
The semantic knowledge is drawn from Wikipedia, which provides the semantic
relatedness information. 2) Next, the Wilks’ lambda based dimension
reduction method is used to select concepts that provide the best separation between
relevant and irrelevant documents. 3) Finally, the value function framework
proposed by Malo et al. [
The main contribution of the Wilks-VF, as compared to the existing literature, is a light-weight concept selection method, where a clustering based Wilks’ lambda approach is used to equip the methodology for on-line usability. Evaluation of the framework’s classification performance is carried out using the Reuters TREC-11 corpus. The result is then benchmarked with other well-known feature selection methods. As primary performance measures we use F-Score, precision and recall. The obtained results are promising, but the work is still preliminary and further evaluation with other corpora needs to be carried out. 2
During the last decade, the role of document content descriptors (words/phrases
vs. categories/concepts) in the performance of information retrieval systems has
piqued considerable interest [
To alleviate the curse of the dimensionality problem which is often
encountered in classification tasks, such as document filtering, a number of feature
selection techniques have been proposed [
This section describes the steps of the procedure and the implementation of the framework. First, we describe the Wikipedia based document indexing procedure, where every document is transformed into a stream of concepts. Next, we present the dimensionality reduction approach utilizing Wilks’ lambda, and finally we describe an efficient linear optimization method for learning the value function based document classifier. 3.1
The document profiling approach used in this paper is similar to the technique
adopted by Malo et al.[
Even after the financial crisis of 2008 just six megabanks - Bank of America, Morgan Stanley, Citigroup, Goldman Sachs, Wells Fargo and JPMorgan Chase – are as strong as ever. Together they control assets adding up to more than 60 percent of the US gross domestic product. Morgan Stanley Subprime
Finacial crisis of 2008
Goldman Sachs
Bill Clinton Investment banking
Leveraged buyout
In this paper, we used the concept-relatedness measure described by Malo
et al.[
Wilks’ lambda is used to identify the concepts which best separate the relevant
documents from the irrelevant ones. Once the documents have been profiled into
a matrix where each row represents a document and each column represents a
concept, Wilks’ lambda tests whether there are differences between the means
of the two identified groups of subjects (relevant and irrelevant documents) on
a number of dependent variables (concepts). A large difference in the means
indicates that the chosen concept can be used to distinguish a relevant document
from an irrelevant one [
Wilks’ lambda statistic. Let X ∈ IRN×|Cˆ| denote the document-concept matrix, where N is the number of documents in the training set and |Cˆ| is the number of different concepts found in the documents. The matrix can be decomposed into two parts according to the relevance of the documents X =
XR XIR , where XR and XIR are the collections of profiles corresponding to the relevant documents and the irrelevant ones respectively. The dimensionality reduction procedure is based on the assumption that the profile means, x¯R and x¯IR in the two document groups are different. If x¯R = x¯IR, none of the concepts are able to differentiate between relevant and irrelevant concepts. The hypothesis H0 : x¯R = x¯IR can be tested by the principle of maximum likelihood, using a Wilks’ lambda statistic, where T denotes the total centered cross product and W denotes the within groups cross product Λ = |W | |T | = |XRT HXR + XITRHXIR| .
|XT HX|
In the above equation, Λ follows the F-distribution and can be tested with the
approximation developed by Rao [
Additional information. In order to choose the concepts that provide the best separation between the two groups, we employ Wilks’ lambda to evaluate the information content of the concepts. Let
T =
T11 T12 T21 T22 and W =
W11 W12 W21 W22 be the block-representation of the total and between groups matrices, where T11 = T11(q,q) and W11 = W11(q,q) refer to those variables, q, that are included into the model. For simplicity, we can assume that the variables in the model have indices 1, 2, . . . , q. For this purpose, we introduce the decomposition of Wilks’ lambda into two parts: the information content of the selected concepts Λ1 and the information content of the remaining concepts Λ2,1: Λ = Λ1Λ2,1 = |W11| |W22 − W21W1−11W12| .
|T11| |T22 − T21T1−11T12| The parts of the decomposition can be interpreted as follows: 1. if Λ1 ≈ 1, then variables i = 1, 2, . . . , q are not able to separate the groups 2. if Λ1 << 1, then variables i = 1, 2, . . . , q separate the groups very well 3. if Λ2,1 ≈ 1, then variables i = q + 1, q + 2, . . . , p are not able to provide additional information 4. if Λ2,1 << 1, then variables i = q + 1, q + 2, . . . , p contain at least some additional information Selection heuristic. Motivated by the Wilks’ lambda statistic, we now introduce the following heuristic for concept selection: 1. Initiation: Let M = {1, 2, . . . , |C|} denote the index set of all concepts and let N = ∅ be the collection of selected concept indices. 2. Ranking: For every concept index i ∈ M , compute λi = wii/tii and sort the index set M in ascending order according to (λi)i∈M values. The smaller the λi, the better the separation power of the concept. 3. Selection: For the sorted index set M , choose q concepts with smallest λ-values. Denote this set as Mq and write M = M \ Mq and N = N ∪ Mq. Construct cross-product matrices Wii and Tii, in such a way that they correspond to N selected concept indices. 4. Evaluation: Test Λ1 and Λ2,1. If the test based on Λ2,1 indicates no remaining information, then stop. 5. Update: For the remaining indices j ∈ M , compute λj = (wii−wj1W1−11w1j ) /(tjj −tj1T1−11t1j ). This step is carried out to remove the effect of the already selected variables. Then the execution moves to Step 2 and the process is repeated. In practice choosing a large q (i.e. several concepts are selected at once), leads to a quick termination of the algorithm. which is preferable for on-line use. That is, for most topics a single iteration should give sufficiently good results. 6. Output: The collection of selected concepts corresponding to the index set
N . 3.3
In the Wilks-VF framework, the utility or value of each document is obtained based on a combination of the individual attributes (i.e. concepts). Learning a filtering rule in this system is in essence equal to finding the optimal parameters for the user’s value function. The process used in this paper is formalized as follows: Definition 2. Value Function: Let D denote the space of profiled documents, where each d ∈ D is a vector of Wikipedia concepts. A value function representing the user’s preference information is defined as mapping V : D → IR, given by V (d) = X μ(c, d)w(c),
c∈CN
where w(c) ∈ [
Let D(R) and D(IR) denote the set of relevant and irrelevant documents
originally supplied by the user. The parameters of the value function are determined
by solving the following linear optimization problem. Maximize ǫ subject to
V (d(R)) − V (d(IR)) ≥ ǫ
∀d(R) ∈ D(R), d(IR) ∈ D(IR)
A positive weight indicates a relevant concept and a negative an irrelevant one.
When ǫ > 0, the obtained value function is consistent with the user’s preferences.
Based on the Wilks-VF a simple document classification rule is obtained by
choosing a suitable cutoff [
In this section, we present the results of the Wilks-VF method. The method has been tested on Reuters TREC-11 newswire documents, which is a collection of news stories from 1996 to 1997. The collection is divided into 100 subsets or topics. All documents belonging to a topic are classified as either relevant or irrelevant to the given topics. These topics are further partitioned into a training and an evaluation set. The purpose of the training set is to generate a search query, which is then applied onto the evaluation set in order to evaluate its performance.
The results from all 100 topics are reported together with five benchmark
methods in Table 1. As benchmarks, we consider the following commonly
applied feature selection techniques: Gain ratio [
F-Score Recall Precision Model
F-Score Recall Precision
As can be seen from the table, the Wilks-VF method is competitive in terms of F-Score. When searching for reasons, it appears that the performance differences are largely explained by recall levels. The recall for Wilks-VF is considerably better than other methods, as can be observed in Table 1. Differences across precision are however, smaller for different methods. Thisproposed by Cilibrasi and Vitanyi means that the advantage of Wilks-VF is its ability to retrieve relevant instances. 5
The paper discusses an important aspect in document classification, i.e. dimensionality reduction. Dimensionality reduction is ubiquitous in various fields and has been widely studied. In this paper, we have specialized a well known Wilks lambda procedure for document classification. The novelty introduced in the approach is a cluster based concept selection procedure which ensures that all the concepts which are significant for classification are selected. The dimensionality reduction procedure has been integrated with a recently suggested value function approach which makes the overall system computationally less expensive to an extent that the methodology can be developed for on-line usage. The empirical results computed on the Reuters TREC-11 corpus show that the Wilks-VF approach is efficient when compared with other widely used methods for dimensionality reduction.