Vincent Claveau
email: vincent.claveau@irisa.fr

Indiscriminateness in representation spaces of terms and documents

Keywords: intrinsic dimensionality, indiscriminability, RSV scores, distributional thesauri, query expansion

. We show that indiscriminateness may be used to characterize difficult queries; moreover we show that this notion, applied to word embeddings, can help to choose terms to use for query expansion.

Introduction

Examining the properties of representation spaces for documents or words in Information Retrieval (IR) -typically R n with n large-brings precious insights to help the retrieval process. It is well-known that the dimensionality of the representation space is not the same as the dimensionality of the data. In the usual vector space model used in IR, the dimensionality of the representation space is the number of different words in the document collection, yet it often possible to represent the same documents in a space with much less dimensions. This fact is at the heart of techniques like Latent Semantic Indexing or Latent Dirichlet Allocation which reduce the dimensionality of the original (very sparse) vector space to a much smaller (and dense) space.

In this paper, we focus on the intrinsic dimensionality of the data, not from a global perspective (as for LSI or LDA), but more locally on portions of the space. For that purpose, we rely on the work of [START_REF] Houle | Generalized expansion dimension[END_REF] and [START_REF] Amsaleg | Estimating Local Intrinsic Dimensionality[END_REF] which permit to define and estimate the local intrinsic dimensionality of the data (see Sec. 2). They showed that it can be used to measure the indiscriminateness of neighbors of a query, and thus to indirectly assess the potential quality of the answers to this query.

Since indiscriminateness depends on how the neighborhood is defined, and thus on the distance metric used, it is necessary to adapt it to RSV (Relevance Status Value) if one wants to use it in IR (Sect. 3). Then, we show in Sect. 4 how it can be used to analyze the representation space of documents in IR, for instance to detect difficult queries.

Related work

Characterizing the intrinsic dimensionality of data sets have been studied in different ways. For instance, embedding techniques or projection techniques build spaces with lower dimensionality in which data points are projected under certain conditions of discriminateness, like Principal Component Analysis (PCA), Latent Semantic Indexing (LSI), Latent Dirichlet Allocation (LDA) [START_REF] Deerwester | Indexing by latent semantic analysis[END_REF][START_REF] Hoffman | Online learning for latent dirichlet allocation[END_REF] or manifold learning [START_REF] Scholkopf | Nonlinear component analysis as a kernel eigenvalue problem[END_REF][START_REF] Roweis | Nonlinear dimensionality reduction by locally linear embedding[END_REF][START_REF] Venna | Local multidimensional scaling[END_REF]. The intrinsic dimensionality of the whole data set is then the one of this new space obtained through projection.

Recently, [START_REF] Houle | Generalized expansion dimension[END_REF] proposed a generalized expansion measure defining the local intrinsic dimension by examining how many points are met around a query point within a certain distance, and how it evolves when the distance augments. More formally, consider two balls centered in x 1 and x 2 with radius 1 et 2 in R m . The ratio between the volumes of these balls can be expressed as:

volume(B(x, 1 )) volume(B(x, 2 )) = 1 2 m
From that, one can define the dimensionality:

m = ln(volume(B(x, 1 ))) -ln(volume(B(x, 2 ))) ln 1 -ln 2
The idea at the heart of the intrinsic dimension measure is to divert the previous equation by replacing the number of points in the volume instead of the volume itself [14, Sect iv B for justification]. Let us note |B(x, )| the number of points in B(x, ); we have:

m = ln |(B(x, 1 )| -ln |B(x, 2 )| ln 1 -ln 2
The dimensionality is now the one of the data, not the one of the representation space. It is worth noting that this estimate is local to a point x (when considering

x = x 1 = x 2 = x).
This intrinsic dimensionality model has been used in several ways for analyzing and building indexing structures for similarity search [START_REF] Beygelzimer | Cover trees for nearest neighbors[END_REF][START_REF] Houle | Dimensional testing for multi-step similarity search[END_REF][START_REF] Houle | Rank cover trees for nearest neighbor search[END_REF], and for anomaly detection [START_REF] De Vries | Density-preserving projections for large-scale local anomaly detection[END_REF]. Let us also cite the work of [START_REF] Bellogín | Understanding similarity metrics in neighbour-based recommender systems[END_REF]; it does not rely on intrinsic dimensionality but the authors also exploit statistics on distance distribution in a similar context than ours in Sect. 4.

Use for Information Retrieval

The interest of intrinsic dimensionality for IR is its capacity to characterize the neighborhood of a query based on the documents surrounding it in the representation space. If this intrinsic dimensionality is very high, it means that a slight distance variation may completely change the set of documents that are considered as the closest to the query. Therefore, a high intrinsic dimensionality implies a high indiscriminateness of the documents around the query [START_REF] Houle | Generalized expansion dimension[END_REF]. This is this exact property that we want to exploit here, provided that we can adapt it to the particular case of the similarity (Relevance Status Value, RSV) functions used in IR.

Limits

The intrinsic dimensionality definition previously given is set for a space in which the metric used is a distance, typically a L2 distance (Euclidean distance). It is used to define the set of points contained in the balls with different diameters (eg. for a ball centered in x with radius r > 0, the points d i considered are those with L2(x, d i ) ≤ r). Yet, in IR, L2 is rarely used as RSV in the vector space model; instead, cosine has been widely used. As it has been shown [START_REF] Houle | Generalized expansion dimension[END_REF], the intrinsic dimension definition can be used with such angular distances. The approach is the same as before: for a given vector, we compare the number of vectors in its neighborhood, that is, with angles lesser than 1 and 2 .

Most of the common and modern RSV function can be written:

RSV (q, d) = t∈q w q (t) • w d (t)
with w q (t) the weight of term t in query q and w d (t) the weight in document d, as illustrated in Tab. 1 (from [START_REF] Lv | Lower-bounding term frequency normalization[END_REF]). with the following notations: c(t, d) number of occurrences of term t in document d c(t, q) number of occurrences du term t in query q N number of documents in the collection df (t) number of documents containing term t dl(d) length of document d avdl average length of documents c(t, C) number of occurrences of term t in collection C p(t|C) probability of term t for a language model of the collection

The RSV functions can be seen as simple scalar product between document vector d and query vector q, which we note q, d . It differs from cosine in that it does not impose a L2 normalization of the vectors.

The absence of normalization is an important issue since it makes impossible to use the same principle as before to compute the intrinsic dimension. Indeed, for a query q, close documents (in terms of scalar product) may be at any L2 distance. More formally, for two thresholds values for the scalar product 1 and model weighting

BM25+ w d (t) (k1+1)c(t,d) k1(1-b+b•dl(d)/avdl)+c(t,d) + δ • log N +1 df (t)
BM25+ wq(t)

(k3+1)c(t,q) k3+c(t,q)
with k1, k3, b and δ fixed parameters

PL2 w d (t) tf n(t,d)•log 2 (tf n(t,d)•λ t )+log 2 e•(1/λ t -tf n(t,d))+0.5 log 2 (2π•tf n(t,d)) tf n(t,d)+1 PL2 wq(t) c(t, q) with tf n(t, d) = c(t, d) • log 2 1 + c • avdl dl(d) c > 0 a search parameter and λt = N c(t,C) Dir w d (t) log µ dl(d)+µ + c(t,d) (dl(d)+µ)p(t|C) Dir wq(t) c(t, q) µ > 0 a smoothing parameter Piv w d (t) 1+log(1+log(c(t,d))) 1-s+s•dl(d)/avdl • log N +1
df (t) si c(t, d) > 0 and 0 else Piv wq(t) c(t, q) with s a fixed parameter Table 1: Weighting functions of terms in the query and the document for different state-of-the-art IR models: BM25+ [START_REF] Robertson | Okapi at TREC-7: Automatic Ad Hoc, Filtering, VLC and Interactive[END_REF][START_REF] Lv | Lower-bounding term frequency normalization[END_REF], Divergence From Randomness PL2 [START_REF] Amati | Probabilistic models of information retrieval based on measuring the divergence from randomness[END_REF][START_REF] Fang | Diagnostic evaluation of information retrieval models[END_REF], Language modeling with Dirichlet smoothing Dir [START_REF] Zhai | A study of smoothing methods for language models applied to ad hoc information retrieval[END_REF], Pivoted Normalization Piv [START_REF] Singhal | Modern information retrieval: a brief overview[END_REF] Fig. 1: Distribution of the L2 norms of documents in Tipster collection under BM25+ (modified version of BM25 proposed by [START_REF] Lv | Lower-bounding term frequency normalization[END_REF]) Fig. 2: L2 norms of documents in Tipster collection according to their length dl(d) with BM25+; horizontal line is the average length (avdl) Fig. 3: In gray: portion of space defined by the set of points whose scalar products with a normed vector q lie between 1 and 2

Estimate with the Power Law exponent

In spite of the limit caused by the scalar product form of most RSV, we still aim at characterizing the intrinsic dimensionality, or at least the indiscriminateness, locally in the space. In previous work, [START_REF] Levina | Maximum likelihood estimation of intrinsic dimension[END_REF][START_REF] Amsaleg | Estimating Local Intrinsic Dimensionality[END_REF] has shown that the intrinsic dimensionality could be estimated from the repartition of the L2 distances between a query and the other points. In line with this, we propose to characterize indiscriminateness by examining the evolution of the number of neighbors (in our case, documents considered as close to the query) according to the RSV. This evolution can be interpreted as the repartition function of a random variable X which represents the RSV score between a given query and a document. More precisely, since we are only interested in the local behavior of X, that if to the closest documents, we only examine the repartition function for the highest RSV scores. The hypothesis we make is that the distribution of RSV can be locally modeled as a Power Law, that is:

f (x) = λx -α with λ a constant and α > 1 (1)
This is the exponent α which is characteristic of the indiscriminateness of the data. Formally, α cannot be linked to the intrinsic dimensionality as defined by [START_REF] Houle | Generalized expansion dimension[END_REF] due to the problem raised by the use of scalar product as previously explained. In the IR case, we have n observations x i , that is n RSV values of a query with its n closest neighbors (n highest RSV scores). It is thus possible to estimate α from these x i . Among the various methods in the literature, the estimation based on log-likelihood has been shown to be the less biased [START_REF] Clauset | Power-law distributions in empirical data[END_REF]. Let the x i be all the observations greater than a threshold x min ; α is then estimated as:

α = 1 + n • n i=1 ln x i x min -1 (2)
In the experiments reported below, we consider n = 100 observations x i to estimate α, that is the 100 highest RSV scores (x min is the 101st highest RSV score).

Fig. 4 shows the RSV score repartition as an histogram for a given query, and the corresponding Power Law whose exponent α is estimated as previously explained. Two facts are worth noting: first, the hypothesis we make about the distribution following a Power Law seems reasonable, since the histogram is typical for this distribution (the same observation holds for every query tested), and second, the estimation method is adequate, showing very few differences between the real distribution and the Power Law obtained with the estimated α. In this section, we study how the indiscriminateness index α, as defined above, can be used in a standard IR framework. We show how α can be used to characterize the documents close to a query, either within the vector space model or in other spaces where the RSV can nonetheless be seen scalar products in Euclidean spaces. Two IR collections are used in our experiments: Tipster and OHSUMED [START_REF] Hersh | Ohsumed: An interactive retrieval evaluation and new large test collection for research[END_REF]. Tipster contains more than 170 000 documents and 50 queries; it was used in TREC-2. The queries are composed of several parts, including the query itself and a narrative detailing the relevance criteria); in the experiments reported below, only the actual query part is used. OHSUMED contains 350,000 bibliographical notices from Medline and 106 queries from the TREC-9 filtering task. Performance are assessed with standard scores: Precision at different threshold (P@x), R-precision (R-prec), Mean Average Precision (MAP).

Detecting difficult queries

The distribution of documents around a query, or more precisely, the distribution of distances (or RSV) between a query and its closest documents can help characterize the difficulty of the query. In order to assess that, we look for a correlation between the index α (cf. Eqn. 2) around a query and the Average Precision (AP) of this query. This is illustrated in Fig. 5 on the Tipster collection, with BM25+ [START_REF] Lv | Lower-bounding term frequency normalization[END_REF] as RSV.

The set of points exhibit the expected dependency between index α and the performance. In Tab. 2, we indicate the Pearson, Spearman and Kendall correlations (and their p-values) between the list of queries ordered by AP and the list of queries ordered by α on Tipster with a BM25+ model. The same information is given in Tab. 3 for OHSUMED with a Dirichlet LM (µ is set to 1000 for which it maximizes the MAP). The inverse correlation clearly appears: a low retrieval performance for query is related to a high indiscriminateness around this query. Same observations also hold with other RSV functions on both collections, but some model parameters have a high impact on the results. For instance, we can observe the influence of smoothing on indiscriminateness within languages models. When smoothing is heavy (high µ in Dirichlet smoothing for example), documents tends to have similar weights for every query term, and thus similar RSV score, which thus makes the documents more difficult to discriminate (high α index). When µ is low, (inverse) correlation is high and tends to diminish when µ gets higher. It can be verified in Fig. 6, where the correlation between AP and α are given for several µ.

Query expansion

Projecting words in continuous representation spaces, such as vector spaces, has been widely studied recently. In these spaces, it is possible to find semantic proximity between words with the help vector-based distances. It makes it possible to build semantic lexicons in which each word is associated with its closest neighbors. In order to do so, these embedding techniques rely on the distributional hypothesis: close words share close contexts. By comparing contexts of words (words occurring before and after), these techniques infer proximities between the words and/or a vector representation of the words. In this field, Word2Vec [START_REF] Mikolov | Linguistic regularities in continuous space word representations[END_REF] is very well-known: words are represented as vectors with the help of a neural approach. In recent work, [START_REF] Claveau | Improving distributional thesauri by exploring the graph of neighbors[END_REF] have shown that IR techniques could also be used to build such vector representation for words. In this later work, the authors use similarities like Okapi-BM25 between contexts of two words to build distributional thesauri. Finally, a word is represented by its similarity scores to every other word. This approach, called spectral, has yielded good results in numerous tasks [START_REF] Claveau | Direct vs. indirect evaluation of distributional thesauri[END_REF].

Semantic lexicons can be used for query expansion: the closest semantic neighbors of query words are added to the query. It has been used as a way to evaluate the quality of the lexicons. In this section, we examine indiscriminateness, as previously defined, in representation spaces generated by Word2Vec or the spectral approach. Since they also rely on similarity based on RSV, we use the same estimation technique of index α to characterize the local properties of the word spaces. In particular, we examine how α can be used in the query expansion task.

Framework

We adopt the following experimental framework. The IR collection is Tipster (see previous section). The distributional lexicons are the spectral one developed by [START_REF] Claveau | Improving distributional thesauri by exploring the graph of neighbors[END_REF] and a Word2Vec model trained on the GoogleNews (freely available at https://code.google.com/p/word2vec/). The IR system used is Indri [START_REF] Metzler | Combining the language model and inference network approaches to retrieval[END_REF][START_REF] Strohman | Indri: A language-model based search engine for complex queries (extended version)[END_REF]. It is known to offer state-of-the-art performance, and moreover this probabilistic systems implements a combination of language modeling [START_REF] Ponte | A language modeling approach to information retrieval[END_REF] and inference networks [START_REF] Turtle | Evaluation of an inference network-based retrieval model[END_REF] which makes it possible to use operators AND OR... In the experiments report below, standard settings are used (Dirichlet smoothing parameter µ = 2500). Thanks to its query language, this system allows us to easily expand the query with the semantic neighbors found in the distributional lexicon: the operator '#syn' aggregates counts of words considered as synonyms. In order to limit the effect of inflection (plural/singular) on the results, both plural and singular forms of the words are added to the query (original words of the query or words added from the lexicon). Performance is evaluated with the standard IR scores, by comparing results with and without expansion.

Experiments

Many uses for the α index of the words in the semantic lexicon are possible. Here, we report the results of two experiments where the α indexes of the words are used to filter expansions, with two different settings. In the first setting (Filter 1 hereafter) we compute α for each word of the original query, and we only add semantic neighbors for words of the original queries having α lower than a certain threshold. In the experiment, the threshold is fixed as the average α of the words of all the queries. In the second setting (Filter 2), we first filter words MAP R-Prec P@5 P@10 P@50 P@100 No expansion Results with the spectral lexicon are given in Tab. 4, and those for Word2Vec are in Tab. 5. Statistical significance (Wilcoxon with p = 0.05) are given: expansion results are compared with non-expanded version; expansion + filter 1 or 2 are compared with expansion (with no filtering). Non significant results are in italics.

The good results of expanding query (without filtering) with lexical resources are already known. Yet, it is worth noting that they are slightly made better, but not significantly, by filtering the words to be expanded (Filter 1) with the α index. When filtering also the words to add to the query (Filter 2), the gains are significantly better. These results holds for both lexical resources. In practice, a close examination of the expanded queries shows that words whose α are above the maximum threshold are indeed polysemic or general ones: choice, term, use, way, young...

Concluding remarks

In this article, we have shown how to adapt the notion of intrinsic dimensionality [START_REF] Houle | Generalized expansion dimension[END_REF] to RSV similarities used in IR. In the follow up of [START_REF] Amsaleg | Estimating Local Intrinsic Dimensionality[END_REF], we have defined the α index to characterize indiscriminateness among neighbors of any point in the representation space. In a standard IR setting, we can exhibit the link between this index computed for any query and the performance of to be expected for this query. We have also applied this approach to word representation spaces, as generated by embedding techniques. We have shown how to improve query expansion by filtering the words to add to the query based on their indiscriminateness.

This work opens many research avenues. From a theoretical point of view, defining intrinsic dimensionality in the case of similarities used in IR, instead of distances studied by [START_REF] Houle | Generalized expansion dimension[END_REF], raises questions. In this article, we have used the α index with the hypothesis that the RSV scores follow a Power Law distribution. Although this is experimentally verified, the precise link between intrinsic dimensionality and α should be formally investigated. From an applicative point of view, one can finds many use for this indiscriminateness notion. For instance, it may allow to propose LSI or LDA representation by adapted to the local complexity. Another pragmatic use would be to help formulate a query during an online search: when typing a word making the query α to raise, a user could be asked to precise or reformulate the query, which may improve the results as seen in Sect. 4.

Fig. 4 :

 4 Fig. 4: Example RSV values repartition (red histogram) and the corresponding Power Law (blue) obtained with log-likelihood estimate of α from the RSV values

Fig. 5 :

 5 Fig. 5: Performance (AP) of queries from Tipster according to their index α with a BM25+ model

coefficient

  Value p-value Pearson r -0.7150 5.43e -09 Spearman ρ -0.7753 3.82e -11 Kendall τ -0.5755 3.69e -09 Table 2: Correlations (and their associated p-values) between AP and index α on Tipster with a BM25+ model coefficient Value p-value Pearson r -0.4919 9.85e -08 Spearman ρ -0.6141 3.26e -12 Kendall τ -0.4494 1.14e -11

Table 3 :Fig. 6 :

 36 Fig. 6: Evolution of correlation scores (Pearson's r, Spearman's ρ, Kendall's τ ) according to Dirichlet smoothing paramater µ.

Table 4 :

 4 Relative performance gain (%) on Tipster with query expansion with and without filtering; spectral lexicon

		21.78 30.93 92.80 89.40 79.60 70.48
	with expansion	+13.80 +9.58 +2.16 +4.03 +5.58 +8.26
	with expansion + Filter 1	+16.22 +10.78 +3.02 +4.47 +9.20 +12.51
	with expansion + Filter 1 & 2 +22.83 +13.00 +2.56 +6.31 +14.10 +21.39
		MAP R-Prec P@5 P@10 P@50 P@100
	No expansion	21.78 30.93 92.80 89.40 79.60 70.48
	with expansion	+13.52 +9.50 +2.59 +3.36 +8.29 +9.99
	with expansion + Filter 1 +15.73 +9.27 +2.22 +4.96 +9.63 +14.41
	with expansion + Filter 2 +20.76 +13.63 +3.88 +5.82 +10.15 +14.27

Table 5 :

 5 Relative performance gain (%) on Tipster with query expansion with and without filtering; Word2Vec with Filter 1, and moreover, only semantic neighbors with α below a certain threshold are used to expand the queries.

( 1 ≥ 2 ), the part of space containing points d i such that 1 ≥ d i , q ≥ 2 is infinite, as illustrated in Fig.