In this paper, we compare performance of several dimension reduction techniques, namely LSI, random projections and FastMap. The qualitative comparison is based on rank lists and evaluated on a subset of TREC 5 collection and corresponding TREC 8 ad-hoc queries. Moreover, projection times and intrinsic dimensionality were measured to present a common baseline for methods' usability.
The information retrieval [
In the vector model, we have to solve several problems. The ones addressed in this paper are problems with the ability to index given collection, search efficiency and result set quality.
Latent semantic indexing (LSI ) adds an important step to the indexing process. In addition to recording which terms a document contains, the method examines the document collection as a whole, to see which other documents contain some of those same terms. LSI considers documents that have many terms in common to be semantically close, and ones with few words in common to be semantically distant. However it is not suitable for huge collections and is computationally expensive, so other methods of dimension reduction were proposed. We test two of them – Random projection, which projects document vectors into a subspace using a randomly generated matrix, and FastMap, a pivot-based method based loosely on Multi-Dimensional Scaling. Since both of them were created for Euclidean spaces, they may not supply good results for a different distance functions. In our case, we need to evaluate, how these methods behave when using cosine measure, common in text retrieval.
The rest of this paper is organised as follows. In the second section, we describe classic vector model and its problems, which may be addressed by dimension reduction. The third section explains used dimension reduction methods. In the fourth section, we briefly describe qualitative measures used for evaluation of our tests and in the fifth the projection properties. In the sixth section, we supply results of tests on a subset of TREC 5 collection. In conclusions we give ideas for future research. 2
In vector model, a document Dj is represented as a vector dj of term weights, which record the extent of importance of the term for the document.
To portrait the vector model, we usually use an n × m term-by-document matrix A, having n rows – term vectors t1 . . . tn (where n is the total number of terms in collection) and m columns – document vectors d1, . . . dm, where m is the size of collection (or corpus) C.
Term weights can be calculated in many different ways: wij ∈ {0, 1}; as a
membership grade to a fuzzy set; or as a product of functions of term frequency
both in a document and in the whole collection [
A query Q is represented as an n-dimensional vector q in the same vector space as the document vectors. There are several ways how to search for relevant documents. Generally, we can compute some Ln metrics to represent the similarity of query and document vectors. However, in text retrieval better results can be obtained by computing similarity, usually using the cosine measure: SIMcos(dj , q) = dj • q ||dj ||.||q|| = n P (wi,j . qi) i=1 s n n
P wi2,j . P qi2 i=1 i=1
As one can see, we do not only obtain documents which are considered relevant, but according to their similarity (or distance) to the query vector, we can order them and obtain a rank for every document in the answer set. If we need a metrics instead of similarity measure, we can use the deviation metric ddev(x, y) = arccos(SIMcos(x, y)).
We can define a threshold t, too. All documents closer than t will be considered relevant, whilst the rest will be irrelevant. However, the choice of t is not exact and its value is usually determined experimentally.
The main problem of the vector model is that the document vectors have a big dimension (e.g. 150,000) and are quite sparse (i.e. most co-ordinates are zero). If we store them as classical vectors, the storage volume is huge – consider size of a term-by-document matrix consisting of 100,000 terms and 200,000 documents.
We can use existing compression schemes for the term-by-document matrix representation to decrease memory usage, but then the access time is much longer and we are limited by the fact, that we cannot access either the term or the document vectors quickly. Another way is to use combined storage with both row and column compression, but updating would still pose a problem.
The second problem is the so-called “curse of dimensionality”, which causes
classical indexing structures like M-trees, A-trees, iDistance, etc. (see [
Third, the synonyms of terms and other semantically related words are not taken into account.
The first two problems can be addressed for queries containing only a few words by inverted list, which is in fact a compressed storage of term vectors. Only term vectors for terms contained in a query Q are loaded and processed, computing rank for all documents containing at least one of the terms at once. However, the inverted list is not efficient when searching for similar documents, because significant part of index must be processed. 3
We used three methods of dimension reduction - latent semantic indexing, random projection, and FastMap, which are briefly described bellow. 3.1
LSI [
Formally, we decompose the term-by-document matrix A by singular value decomposition (SVD ), calculating singular values and singular vectors of A. SVD is especially suitable in its variant for sparse matrices.
Theorem 1 (Singular value decomposition [
A = U ΣV T is called singular decomposition of matrix A and the numbers σ1, . . . , σr are singular values of the matrix A. Columns of U (or V ) are called left (or right) singular vectors of matrix A.
Now we have a decomposition of the original term-by-document matrix A. The left and right singular vectors (i.e. U and V matrices) are not sparse. We get r nonzero singular numbers, where r is the rank of the original matrix A. Because the singular values usually fall quickly, we can take only k greatest singular values with the corresponding singular vector coordinates and create a k-reduced singular decomposition of A.
Definition 1 ([
A = U ΣV T ≈ Ak = (UkU0) Σk 0 0 Σ0
VkT V0T We call Ak = UkΣkVkT a k-reduced singular value decomposition (rank-k SVD).
Instead of the Ak matrix, a concept-by-document matrix Dk = ΣkVkT is used in LSI as the representation of document collection. The document vectors (columns in Dk) are now represented as points in k-dimensional space (the pseudodocument-space). For an illustration of rank-k SVD see Figure 1.
Rank-k SVD is the best rank-k approximation of the original matrix A. This means that any other decomposition will increase the approximation error, calculated as a sum of squares (Frobenius norm) of error matrix B = A − Ak. However, it does not implicate that we could not obtain better precision and recall values with a different approximation.
The value of k was experimentally determined as several tens or hundreds (e.g. 50–250), it is known to be dependent on the number of topics in collection, however its exact value cannot be simply determined.
The LSI is hard to compute with complexity O(mn2) for dense and O(mnc)
for sparse matrices having on the average c nonzero values per column [
Several approximate methods for faster SVD calculation were offered, such as
application of Monte-Carlo method [
We used the latter method, applying LSI on a matrix with reduced document vectors created by random projection. This method has a complexity of O(ml(l+ c)). 3.3
Random projection is a fast method of dimension reduction. Unlike LSI method, it does not require expensive computation of decomposition. Instead, it uses a randomly-generated projection matrix to reduce dimension of vector space. Vector from original space with dimension n is multiplied with projection matrix to obtain a vector in reduced space of dimension l, where l << n.
Results of dimensionality reduction by random projection are of course worse than in case of LSI and we do not obtain latent semantics. If the reduced dimension is high enough and random values building projection matrix have a zero-mean unit-variance distribution such as N (0, 1), the Euclidean distances and angles between vectors are well-preserved.
The minimal “safe” dimension can be obtained from Johnson-Lindenstrauss
lemma, however the currently known bound is still quite high and experiments
showed that even smaller dimensions can be used [
4+2β Rn, given ε > 0, β > 0 and l > 0, l ≥ l0 = ε2/2−ε3/3 log m, there exists with probability at least 1 − n−β mapping f : Rn → Rl, such that for all u, v ∈ P (1 − ε)||u − v||2 ≤ ||f (u) − f (v)||2 ≤ (1 + ε)||u − v||2
Since we JL lemma considers only Euclidean distances, we don’t have yet
any bounds for cosine measure. Papadimitriou et al showed in [
f (vi).f (vj ) ≤ (1 − ε)vi.vj + ε(vi2 + vj2).
Are the lengths of all vk ≤ 1, changes the inner product at most by 2ε. Again, real-life data indicate that the bound is still too high and smaller dimensions can be used.
When calculating the Euclidean distances, we need to apply a scaling factor pn/l first, to obtain correct results because less coordinates are being used.
Classical implementations of random projection used orthogonalisation,
normalisation and a dense projection matrix with Gaussian distribution. Achlioptas
showed that orthogonalisation and normalisation can be skipped. He also
proposed yet another powerful simplification – instead of using real coefficients of
N (0, 1) distribution, he offered two possible distributions for elements rij of
projection matrix R8 [
>>>><−1 with probability 16 8<−1 with probability 12 rij = √3. >:>>> 0 with probability 23 rij = :+1 with probability 12 .
+1 with probability 16 .
The √3 component does not have to be stored in projection matrix. It can be used together with scaling factor after calculation of projected vector coordinate. If we are calculating cosine measure, it can be even discarded and instead of multiplication, we can use addition and subtraction.
We used this method in our tests, since previous results [
FastMap [
In first step, it chooses two points, which should be most distant for calculated reduced dimension. Because it would be expensive to calculate distances between all points, it uses following heuristics: 1. A random point c0 is chosen. 2. The point bi having maximal distance δ(ci, bi) from ci is chosen, and based on it we select the point ai with maximal distance δ(bi, ai) 3. We iteratively repeat step 2 with ci+1 = ai (authors suggest 5 iterations). 4. Points a = ai and b = bi in the last iteration are pivots for the next reduction step.
In second step (having the two pivots a, b), we use the cosine law to calculate position of each point on line joining a and b. The coordinate xi of point pi is calculated as and the distance function for next reduction step is modified to xi = δ2(ai, pi) + δ2(ai, bi) − δ2(bi, pi)
2δ(ai, bi) δ02(p0i, p0j ) = δ2(pi, pj ) − (xi − xj )2
The pivots in original and reduced space are recorded and when we need to process a query, it is projected using the second step of projection algorithm only. Once projected, we can again use the original distance function in reduced space.
The complexity of FastMap is O(mck) for sparse and O(mnk) for dense matrices. 4
Since we need an universal evaluation of any retrieval method, we use some measures to determine quality of such method. In case of Information Retrieval we usually use two such measures - precision and recall. Both are calculated from the number of objects relevant to the query Rel – determined by some other method, e.g. by manual annotation of given collection and the number of retrieved objects Ret. Based on these numbers we define precision (P ) as a fraction of retrieved relevant objects in all retrieved objects and recall (R) as a fraction of retrieved relevant objects in all relevant objects. Formally: P = |Rel ∩ Ret| and R = |Rel ∩ Ret|
|Ret| |Rel|
So we can say that recall and precision denote, respectively, completeness of
retrieval and purity of retrieval. Unfortunately, it was observed that with the
increase of recall, the precision usually decreases [
For the overall comparison of precision and recall across different methods
on a given collection, we usually use the technique of rank lists [
The search in a collection of high-dimensional document vectors is negatively
affected by a phenomenon called the curse of dimensionality [
Sometimes, we need to verify, how well are the distances between objects preserved in the reduced dimension. To do so, we usually calculate the stress of projection f as stress = s (Pm i,j=1(d0(f (xi), f (xj )) − d(xi, xj ))2
Pm i,j=1 d2(xi, xj ) , where d is the distance function in original and d0 in projected space. The lower the stress, the better. If stress = 0, then the projection did not change the distances at all.
However, the stress function must not be overrated – even if the distances are not well-preserved, they might have been scaled by some factor, making the only difference in the choice of similarity threshold. 6
For testing of our approach, we used a subset of TREC collection [
We calculated random projection into dimensions l ∈ {100, 250, 500, 1000}; both classic and approximate LSI (with random projection into l = 1000) for k ∈ {100, 250}. For FastMap, we used for every value of k suggested 5 iterations to choose “most distant” points. Additionally we calculated FastMap for k = 100 and 3 iterations (which yielded slightly worse results). Classic LSI was included to provide a baseline, since its improvement of recall is well-known.
The reduction and query projection times are shown in Table 1 1. 6.1
We calculated stress and intrinsic dimension for each projection method for deviation metrics. 1 Since the LSI was calculated on a different computer, the LSI calculation times are only approximate
Reduction method k LSI FastMap RP RP+LSI 50 0.05 0.14 0.02 0.05 100 0.12 0.28 0.03 0.12 250 0.35 1.00 0.07 0.35 500 – – 0.13 0.78 1000 – – 0.25 – (b) Distance histogram − VSM
Distance histogram − FM250 5 ] 4 % [ y c en 3 u q e r fe 2 c n a t isd 1
The stress, summarised in Table 2a is quite low for both LSI and random projection, however in case of FastMap are the deviations not well-preserved. From the look at distance distribution histograms of original and FastMap reduced space in Figure 2 one can observe that the distances are highly reduced. The question, if the change affects only the dissimilarity threshold will be partly solved in the next section.
In Table 2b, we can observe high intrinsic dimensions for both LSI
variants and especially for random projection, whilst the intrinsic dimension for
FastMap is surprisingly low. Additional tests on real data structures are
required for FastMap, to verify the indexability of reduced data. In case of LSI,
we recently offered a modified σ-LSI model [
Reduction method k LSI FastMap RP RP+LSI 50 25.1 0.2 53.3 46.8 100 51.1 0.5 100.2 93.9 250 121.1 0.9 217.1 206.4 500 – – 343.7 329.7 1000 – – 489.3 – VM ←− 31.8 −→ (b) 6.2
Firstly, we used rank lists and measured interpolated average precision of the above mentioned TREC Queries at the 11 standard recall levels. Results are summarised in Figure 3. We can see that while classic LSI provides even better results than vector model due to latent semantics, other reduction techniques try with a different success to reach the results of vector model. In our case, we got results close to vector model for random projection with l=1000 and FastMap with k=250.
Since the important part of precision-recall curve is close to the 100% recall, we also calculated the mean average precision for all relevant documents in rank lists. The relative results against vector model (100%) are shown in Table 3. In this paper, we have compared three well-known dimension reduction methods from the view of indexability, distance preservation and results on real-live text data (using cosine measure as similarity function). Whilst the LSI is known to provide latent semantics, it is computationally expensive and in case we only need to battle the “curse of dimensionality” by reducing the dimension, FastMap
RP+LSI k=50 (l=1000) RP+LSI k=100 (l=1000) RP+LSI k=250 (l=1000) RP+LSI k=500 (l=1000) 0 ] 3 % [ n iisco 20 e r P 0 4 0 ] 3 % [ n iisco 20 e r P 0 1 0 4 0 ] 3 % [ n iisco 20 e r P 0 1
RP l=100 RP l=250 RP l=500 RP l=1000 40 60 Recall [%] (b)
FM k=50, 5 iterations FM k=100, 3 iterations FM k=100, 5 iterations FM k=250, 5 iterations 0
0 0 20 40 60 Recall [%] (c) 40 60 Recall [%] (d) 80 100 0 20 80 100 or random projection may suffice. As expected, LSI was the slowest, but most exact method, followed by FastMap, which is faster but less accurate, and Random projections which are fast, but accurate only in high dimensions and have high intrinsic dimensionality.
There are some other newly-proposed methods, which may be interesting
for future testing, e.g. the SparseMap [