Tensor Space Model

Today, more and more documents in intranets are XML ones, and their number increases on the Internet too. Despite the numerous existing XML databases, there is a lack of tools using the structure to solve several classical problems such as keyword-based queries for information retrieval or clustering of XML documents. Moreover, it is still difficult to manage collections (such as the Internet) where XML documents are mixed with non-XML documents (such as Postscript, PDF, etc.).

From: pascal@source.org (Pascal Francq)
Subject: Example of an email
Article-I.D.: src.17194 
Date: Thu, 20 Jul 2006 10:08:50 +0200
Distribution: Paul Otlet Institute

Do you buy the remaster version of the In Rock album from Deep Purple?
Pascal

<?xml version="1.0" standalone="no"?>
<discography xmlns="http://music.org/">
<group groupID="Deep Purple">
   <groupName> Deep Purple </groupName>
   <album>
      <albumName> In Rock </albumName> 
      <published> 1969 </published> 
   </album>
</group>
</discography>

The vector space model was introduced to represent documents in search engines, but it can be used to represent any kind of objects. In this model, the objects (for example documents) are represented as a set of features, $f_{i}$ . For each object, $o_{n}$ , a vector of features $\vec{o}_{n}=(o_{1,n},\ldots,o_{|F|,n})$ is defined and a weight is associated with each feature ($|F|$ being the total number of different features). Initially, the model supposes that for documents $o_{i,n}>0$ , but negative weights may be allowed to represent other objects [13]. Several methods exist to compute these weights based on quantity, $e_{i,n}$ , related to the feature $f_{i}$ for the object $o_{n}$ [3]. For textual documents, the features are selected terms contained in the documents, and $e_{i,n}$ is the number of occurrences of these terms.

Some models proposed to replace the different words by their stems (“connects”, “connected”, etc. are replaced by “connect”) and to remove the stopwords (“and”, “or”, “the”, etc. in English) [16, 12, 11].

In practice, since most collections do not content structure documents only, a main constraint for the model is to manage documents with different levels of semantic information. Moreover, numerous algorithms, from information retrieval [2] to social browsing [14], were developed for non-structured textual documents. Ideally, the new model representing documents should be “as much compatible as possible” to the previous model in order to take advantage of existing researches in information science.

In this paper, an adaptation of the extended vector space model for objects (such as XML documents) is proposed. Specifically, it is suggested that each object is represented by a tensor in a concept space. This adaptation of the classical vector space model has a major advantage. Since there exist several algorithms using the vector space model, the proposed approach makes existing algorithms easily adaptable. In particular, if a new similarity measure taking the richness if the tensors into account exists (as proposed in this article), most information science algorithms (such as the documents clustering, users profiling or users clustering) should work without any changes (and use indirectly richest features if available). Moreover, collections mixing XML documents and non-structured documents can be managed.

As explained previously, for the representation of textual documents, indexing the documents with all the index terms (features) is not necessary useful. In this paper, we propose to classify the methods depending if they represent XML documents with a full structure approach (all the tags are used to represent the document), or with a partial structure approach (only specific tags are used).

Denoyer and Gallinari separate the nodes of a tree corresponding to an XML document into structure or content nodes [10]. They propose to train different classifiers on each pair of a structure nodes and the corresponding content nodes, the predictions of each classifier being then combined to find the corresponding category. The interesting idea of this approach is that the relevant features are the combination of the content and the semantic (represented by the structure node). On the other hand, this approach used for classification cannot be applied as such to other types of problems (for example clustering, profiling or retrieving).

In the field of XML documents retrieval, all the approaches use a full structure. Most of them are based on a structured query language where the users are able to build queries containing index terms and structure elements. The best known example of such query languages are the “official” XPath and XQuery expressions of the W3C [21, 5]. An interesting approach is proposed by [6]. The authors use the XML structure to disambiguate the words contained in the tags. If a given tag, $x$ , is searched and a document contains a tag $y$ related to $x$ in WordNet [B]  [B] WordNet is a freely and publicly available lexical database of English (http://wordnet.princeton.edu)., they suppose that a similarity exists between the two tags and the content associated to tag $y$ may be relevant to the query. This idea suggests that the combinations of tags and content are the “comparison unit” between XML structures. In recent years, some approaches have been proposed to manage keyword-based queries which are easier to formulate for “normal” users and do not need a knowledge of the underlying structure. Recently, an multi-criteria approach to rank XML fragments was included in the GALILEI platform [1]. This study shows that using the proximity between the tags (corresponding to certain keywords) and the content containing some keywords as criteria provides better ranking results. Again, this recalls the importance of the combination of the content and the corresponding tags.

It must be noticed that several methods compute some similarity measures between XML documents or between an XML document and its schema [24]. In particular, in the field of XML filtering, several solutions were developed to detect part of XML documents related to a set of predefined XPath or XQuery expressions [7]. Since these methods make global comparisons on the whole XML trees (documents or schemas), they are not well suited to compare XML documents sharing only small parts of their schemas (for example two different documents using the same subset of tags). Moreover, most of them are limited to the structure part of the documents and does not include the content. Therefore, these methods were not used to solve problems such as classification, clustering or profiling (at least in the knowledge of the author).

Another solution was proposed by Wu and Tang for XML documents classification [23]. One of their assumptions is that each class is identified by key terms that are not in any other classes. The key terms are extracted from a set of pre-categorized documents, and each class is represented by key paths which are all the paths of the XML trees of the pre-categorized documents starting from the root tag and ending with a tag containing at least one key term. They compute a similarity between a document and the class based on a comparison between all the paths of the documents ending with a tag containing at least one key term and the corresponding key paths. The document is then assigned to the class with which it has the highest similarity. A drawback of this approach is that the key paths are not well suited to represent classes of XML documents having different schemas (a same tag or key term being in different levels of the hierarchy for different XML schemas will have different paths).

In the context of hypertext categorization, a study shows that, when available, using metadata as specific dimensions in the features spaces increases the quality of the classification [25]. In particular, one of the methods used by the authors for the classification is the classical k-Means algorithms where the distances between the documents are computed as the cosines between the corresponding vectors (including the metadata). This can be seen as a first adaptation of the classical vector space model.

A more formal adaptation of the classical vector space model (section 1.3↑) to use structure information was proposed by Fox [27]. His model suggests that each document is represented by a set of subvectors, each subvector representing a specific type of concepts called c-types (authors, bibliographical links, etc.). The c-types to use remain free for particular purposes. In the context of XML documents, the model suggested by Fox has already been used [28]. Adapted for the well-known INEX 2005 collection, the authors define 18 c-types corresponding to important tags of the INEX 2005 collection. The main drawback of this approach is that the c-types used are dependent of that particular INEX 2005 collection and cannot be used for other XML documents collections.

The concept types and categories do not influence the concept space, they serve only to recognize concepts that are related. We will use this information to propose a new similarity measure. Let us define two functions: $Type(c_{i})$ that returns the type of a given concept, $c_{i}$ ; and $Cat(c_{i})$ that returns the category of a given concept, $c_{i}$ .

First of all, taking the dependance into account is a tricky problem: it complicates the model, increases the computational power needed (in particular for a large corpus), and the existing attempts don’t performed better [3].

Secondly, since the model is statistical, such a dependance can be taken into account indirectly through the co-occurrences of the concepts. To illustrate that, let us suppose two domains: genetic algorithms (described with terms like “genetic”, “algorithm”, “performance”, “chromosome”, “heuristic”, etc.) and genetics (described with terms like “genetic”, “biology”, “chromosome”, “heredity”, etc.). To describe these domaines, the terms “genetic” and “chromosome” are not enough, we must combine them, i.e. they are dependent from other terms. Yet, it is reasonable to suppose that documents about genetic algorithms will also contained “heuristic” or “performance”, while the terms “biology” and “heredity” will appear in documents about genetics. This means that their descriptions don’t include the terms “genetic” and “chromosome” alone, but will also be defined by other terms in order to make clean distinction between the two domains.

Le us imagine that a object (for example a document), $o_{v}$ , has a “author” metadata which is “Pascal Francq”, and contents a single sentence “The connections are optical fibres”. If we suppose that we remove the stopwords and take only the stems into account, the object has two elements:

Let us suppose that the space contains 7 concepts: $c_{0}$ represents “author”, $c_{1}$ represents “body”, $c_{2}$ represents the term “Pascal”, $c_{2}$ represents the term “Francq”, $c_{3}$ represents the term “coffee”, $c_{4}$ represents the term “ connect”, $c_{5}$ represents the term “optic” and $c_{6}$ represents the concept “fiber”. The object $o_{v}$ is represented by the following tensor:

$$\begin{eqnarray*} \hat{o}_{z} & = & \left[\begin{array}{cccccccc} 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right] \end{eqnarray*}$$

As this example shows, the matrix representing a tensor is highly sparse. This tensor $\hat{o}_{z}$ can be seen as a set of vectors $\vec{o}_{i,z}$ , each vector being associated to a particular meta-concept, $c_{i}$ . As for the concepts, we can define two functions: $Type(\vec{o}_{i,z})$ that returns the type of the meta-concept, $c_{i}$ , associated to the vector; and $Cat(\vec{o}_{i,z})$ that returns the category of that meta-concept.

In fact, if we suppose that there is only one meta-concept (for example “body”), the tensor space model is identical to the classical vector space model. The tensor space model can therefore be qualified as an extension of the vector space model if the method used to compute the document descriptions can extract multiple meta-concepts.

$$\begin{eqnarray*} if_{i} & = & \log\frac{|\mathcal{D}|}{|\mathcal{D}_{i}|} \end{eqnarray*}$$ where $|\mathcal{D}|$ is the total number of documents, and $|\mathcal{D}_{i}|$ the number of those containing the feature $f_{i}$ .

For a given number of documents, $if$ increases when $|\mathcal{D}_{i}|$ decreases: the discriminant value of a given feature decreases when it occurs often in the corpus. In fact, its value is null if it appears in each document of the corpus.

This factor can be generalized to any kind objects (documents, profiles, etc.) that are described with terms [13]:

$$\begin{eqnarray} if_{i}(\mathcal{O}) & = & \log\frac{|\mathcal{O}|}{|\mathcal{O}_{i}|}\label{eq:if_vector} \end{eqnarray}$$ where $|\mathcal{O}|$ is the total number of objects, and $|O_{i}|$ the number of those containing the feature $f_{i}$ .

$$if_{i}(\mathcal{O})=\log\frac{|\mathcal{O}|}{|\mathcal{O}_{i}|}=\log\frac{|\mathcal{O}\mathcal{\setminus O}'|+|\mathcal{O}'|}{|\mathcal{O}'|}$$ where $\mathcal{O}\mathcal{\setminus O}'$ represents the set of objects which don’t contain any email address.

In practice, since $c_{i}$ is contained in each object providing some email addresses, its discriminant value should be null. But, due to the quantity $|\mathcal{O}\mathcal{\setminus O}'|$ , it is not the case. Therefore, a modification is proposed to compute the inverse object frequency factor, $if_{i}(\mathcal{O})$ , for concept, $c_{i}$ :

$$\begin{equation} iof_{i}(\mathcal{O})=\log\frac{|\mathcal{O}_{T(c_{i})}|}{|\mathcal{O}_{T(c_{i}),i}|}\label{eq:if_Tensor} \end{equation}$$ where $|\mathcal{O}_{T(c_{i})}|$ is the total number of objects described by at least one concept of the same type as $c_{i}$ , and $|\mathcal{O}_{T(c_{i}),i}|$ the number of those containing the concept $c_{i}$ .

When applying (↓) to compute the inverse object frequency factor in the case of the email address just presented, its value is now null since $|\mathcal{O}_{T(c_{i})}|=|\mathcal{O}_{T(c_{i}),i}|=|\mathcal{O}'|$ .

Several methods adapt these weights [3]. One of the most used in information retrieval is based on the term frequency ($tf$ ) and inverse document frequency ($idf$ ) factors [19, 20]:

$$\begin{equation} o_{i,n}=tf\cdot idf=\frac{e_{i,n}}{\max_{l}\, e_{l,n}}\cdot\log\frac{|\mathcal{D}_{i}|}{|\mathcal{D}|}\label{eq:oij_Vector} \end{equation}$$ where $o_{i,n}$ represents the weights of an element in the vector, $|\mathcal{D}|$ the total number of documents, $|\mathcal{D}_{i}|$ the number of those containing feature $f_{i}$ and $e_{i,n}$ is the occurrence of the feature $f_{i}$ for the document $d_{n}$ .

These factors have an interpretation: the $tf$ is sort of document length normalization while the $idf$ infers the importance of a particular feature regarding its distribution in the corpus (a feature appearing very often in the documents of the corpus has a less importance).

In the previous section, I explained how the the inverse object frequency factor has to be adapted to a concept space where the concepts are structured in types. Similar reasoning can be done with the term frequency factor where the normalization of a particular weight is done regarding the vector (and the whole tensor). It is therefore possible to propose a concept weighting method for the tensor space model that transform a local weight $o_{ij,n}$ :

$$\begin{align} W_{\mathcal{O}}(\hat{o}_{v})= & \begin{cases} o_{ii,v} & i=j\\ \frac{o_{ij,v}}{\max_{l\mid l\neq i}\left|o_{il,v}\right|}\cdot\log\frac{|\mathcal{O}_{T(c_{j})}|}{|\mathcal{O}_{T(c_{j}),j}|} & i\neq j \end{cases}\label{eq:oij_Tensor} \end{align}$$ where \strikeout off\uuline off\uwave off$W_{\mathcal{O}}(\hat{o}_{v})$ is also a tensor, and\uuline default\uwave default $\left|o_{il,v}\right|$ represents the absolute value of $o_{il,v}$ and its uses is necessary because, for some objects (such as profiles), the weights may be negative.

This formula can be adapted to any subset of objects, $\mathcal{S}$ :

$$\begin{align} W_{\mathcal{S}}(\hat{o_{v}})= & \begin{cases} o_{ii,v} & i=j\\ \frac{o_{ij,v}}{\max_{l\mid l\neq i}|o_{il,v}|}\cdot\log\frac{|\mathcal{S}{}_{T(c_{j})}|}{|\mathcal{S}{}_{T(c_{j}),j}|} & i\neq j \end{cases}\label{eq:Weight_Tensor} \end{align}$$ where \strikeout off\uuline off\uwave off$W_{\mathcal{S}}(\hat{o}_{v})$ is also a tensor, \uuline default\uwave default$|\mathcal{S}{}_{T(c_{i})}|$ is the total number of objects of the subset described by at least one concept of the same type as $c_{i}$ , and $|\mathcal{S}{}_{T(c_{i}),i}|$ the number of those containing the concept $c_{i}$ .

This latest formula allows to act as a magnifying glass that focuses on a particular subset of objects (for example all the documents assessed by a user with a given profile).

$$\begin{eqnarray*} \hat{o}_{1}=\left[\begin{array}{ccccc} 0 & 0 & 2 & 1 & 3\\ 0 & 0 & 1 & 3 & 2\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 \end{array}\right] & & \hat{o}_{2}=\left[\begin{array}{ccccc} 0 & 0 & 1 & 2 & 0\\ 0 & 0 & 2 & 0 & 3\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 \end{array}\right] \end{eqnarray*}$$ where $c_{1}$ and $c_{2}$ represent concept types (for example, a metadata “author”) and the other concepts correspond to terms. Moreover, the weights associated to $c_{1}$ and $c_{2}$ are not identical.

If we make a classic sum:

$$\begin{eqnarray*} \hat{o}_{1}+\hat{o}_{1} & = & \left[\begin{array}{ccccc} 0 & 0 & 3 & 3 & 3\\ 0 & 0 & 3 & 3 & 5\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 \end{array}\right] \end{eqnarray*}$$

Identically, if we multiply the tensor $\hat{o}_{1}$ by 3:

$$\begin{eqnarray*} 3\times\hat{o}_{1} & = & \left[\begin{array}{ccccc} 0 & 0 & 6 & 3 & 9\\ 0 & 0 & 3 & 9 & 6\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 \end{array}\right] \end{eqnarray*}$$

In the GALILEI library, the class GDescription provides a representation for a tensor describing an object [D]  [D] In practice, each object having a description inherits from the class GDescriptionObject (document, profile, etc.). In practice, it is a container of vectors implemented trough the GVector class. Each vector is associated to a concept, $c_{i}$ , and a weight representing the element $o_{i,i}$ of the corresponding tensor. The new operators are implemented as operators of the classes GDescription and GVector.

The GALILEI library provides the class GConcept that represents a given concept. It has the method GetIf that computes the inverse frequency for a particular type of object. In practice, it is dynamically updated each time an object description is added (method GDescription::AddRefs) or removed (method GDescription::DelRefs) from the session. To compute the inverse frequency for a set of descriptions, the GALILEI library provides the class GDescriptionSet and its method GetIf.

References

[1] Faiza Abbaci, Pascal Francq: “Multi-criteria Decision Support to Rank XML Fragments”, Proceedings of the 2007 Internation Conference on Internet Computing, 2007.

[2] Ricardo Baeza-Yates, Berthier Ribeiro-Neto: Modern Information Retrieval. Addison-Wesley, 1999.

[3] Ricardo Baeza-Yates, Berthier Ribeiro-Neto: Modern Information Retrieval: The Concepts and Technology behind Search. Addison-Wesley Professional, 2011.

[4] Tim Berners-Lee, James Hendler, Ora Lassila: “The Semantic Web”, Scientific American, 2001.

[5] S. Boag, D. Chamberlin, M. F. Fernandez, D. Florescu, J. Robie, J. Simeon, M. Stefanescu: “XQuery 1.0: An XML Query Language”, W3C Working Draft, 2002.

[6] Davide Buscaldi, Giovanna Guerrini, Marco Mesiti, Paolo Rosso: “Tag semantics for the retrieval of XML documents”, Proceedings of the 1st international symposium on Information and communication technologies, pp. 273—278, 2003.

[7] Songting Chen, Hua-Gang Li, Jun'ichi Tatemura, Wang-Ping Hsiung, Divyakant Agrawal, K. Selçuk Candan: “Scalable Filtering of Multiple Generalized-Tree-Pattern Queries over XML Streams”, IEEE Transactions on Knowledge and Data Engineering, pp. 1627—1640, 2008.

[8] N. A. Chinchor: “Overview of MUC-7/MET-2”, Proceedings of the Seventh Message Understanding Conference (MUC-7), 1998.

[9] DCMI: Dublin Core Metadata Element Set, Version 1.1: Reference Description. 1999. URL: http://dublincore.org/documents/dces.

[10] Ludovic Denoyer, Patrick Gallinari: “Bayesian network model for semi-structured document classification”, Information Processing & Management, pp. 807—827, 2004.

[11] Willian B. Frakes: Stemming Algorithms in Information Retrieval: Data Structures & Algorithms (Frakes, William B. and Baeza-Yates, Ricardo, ed.). Prentice-Hall, 1992.

[12] W. Francis, H. Kucera: Frequency Analysis of English Usage. Houghton Mifflin, 1982.

[13] Pascal Francq: Collaborative and structured search: an integrated approach for sharing documents among users. 2003.

[14] Pascal Francq: The GALILEI Platform: Social Browsing to Build Communities of Interests and Share Relevant Information and Expertise in Open source for knowledge and learning management : strategies beyond tools (Lytras, Miltiadis D. and Naeve, Ambjorn, ed.). Idea Group Publishing, 2007.

[15] S. Liu, C. A. McMahon, S. J. Culley: “A review of structured document retrieval (SDR) technology to improve information access performance in engineering document management”, Computers in Industry, pp. 3—16, 2008.

[16] H. P. Luhn: “A Statistical Approach to Mechanized Encoding and Searching of Literary Information”, IBM Journal of Research and Development, pp. 309—317, 1957.

[17] Andrea Molinari, Gabriella Pasi, R. A. Marques Pereira: “An indexing model of HTML documents”, Proceedings of the 2003 ACM symposium on Applied computing, pp. 834—840, 2003.

[18] Peter Murray-Rust: “CML - Chemical Markup Language”, World Wide Web Journal, pp. 135—147, 1997.

[19] G. Salton: Automatic Information Organization and Retrieval. McGraw-Hill, 1968.

[20] G. Salton: The SMART Retrieval System — Experiments in Automatic Document processing. Prentice Hall Inc., 1971.

[21] W3C: XML Path Language (XPath) Version 1.0. 1999. URL: http://www.w3.org/TR/xpath.

[22] W3C: eXtensible Stylesheet Language (XSL) Version 1.0. 2000. URL: http://www.w3c.org/TR/xsl.

[23] Junwei Wu, Jian Tang: “A bottom-up approach for XML documents classification”, Proceedings of the 2008 international symposium on Database engineering & applications, pp. 131—137, 2008.

[24] Guangming Xing, Chaitanya R. Malla, Zhonghang Xia, Snigdha Dantala Venkata: “Computing edit distances between an XML document and a schema and its application in document classification”, Proceedings of the 2006 ACM symposium on Applied computing, pp. 831—835, 2006.

[25] Y. Yang, S. Slattery, R. Ghani: “A Study of Approaches to Hypertext Categorization”, Journal of Intelligent Information Systems, pp. 219—241, 2002.

[26] Jeonghee Yi, Neel Sundaresan: “A classifier for semi-structured documents”, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 340—344, 2000.