The information is at the present time often saved and available in electronic form. With still increasing quantity of accessible, most frequently text information, the need of organization of these data is raising. The problem of fast and effective information retrieval occurs very often. In this contribution we describe the method for creating word vector space and using NOT operation for more effective acquirement of relevant documents.
High volume of text documents and the rate of growth these documents requires finding new approaches in linguistics and in areas related with information retrieval (IR). These new approaches are based on principles which are derived from natural sciences.
Noticeable expansion of geometrics was motivated
by Descartes ideas and by establishment of the
coordinate system which permit interconnection
between geometrics and algebra [
In IR was geometrical methods enveloped in the
form of the vector model. Another meaningful step in
geometrical understanding of the world was
interconnection of geometrics and logics.
This connection was made on the ground of the
quantum physics [
A huge amount of multimedia data is at the present
time coupled with expansion of information
technologies. Among these data we can include
especially text, image and acoustic documents. The set
of text documents we will be consider as an input area.
Almost in all well-known information retrieval systems
occurs the morphological part. By the help of this part
we can, by using stop-list, remove non-semantic words
from documents, and semantic significant words
convert to the basic form. In this way, we specify terms
which after evaluation make vector in the space of
concepts. This vector is then used for documents
identification from the point of view his content [
The application of the method based on combination of the vector model and Boolean logic appears as a suitable way for creating the model of natural language. In this contribution we present constructions in the vector space based on the standard linear algebra, and also some examples of using the vector negation for separation meanings of ambiguous words. In quantum logic arbitrary sets are substituted by linear subspaces of the vector space and union, intersection and complement are substituted by the vector sum, intersection and orthogonal complements of these subspaces.
A useful tool for information retrieving and
processing is latent semantic analysis – LSA. This
method, which is based on singular value
decomposition (SVD), we can use for improving access
to desirable documents. We regard the factor of greatest
singular values k. LSA has geometrical representation,
in which objects (e.g. documents and terms) are
distributed in the low-dimensional space. As an
example we can use term-document matrix, in which
rows represent terms and columns of matrix represent
documents. Nonzero values in matrix signify that
corresponding documents include required terms. This
vector space model was described by Salton [
In the first part of our contribution is described representation of word meanings in the vector space. Second part is focused on operations in the word space. Next chapter is devoted to basic knowledge from Boolean logic. In the last part we mentioned theoretical knowledge applied in the process of searching word meanings.
Vector space could be understood as a set of points,
in which each point of the space is defined by the list
of coordinates [
Similar techniques are used in information retrieval
for determination similarity relation between words and
documents. Similarity can be determined by calculating
cosine of the angle between two vectors [
i i ∑ wi2 ∑ di2 = w ⋅ d w d The calculus is further simplified by normalization of all vectors to the same length, consequently then the cosine similarity is equal with euclidean inner product. This is standard method which avoids add great weight of consequence to frequent words or large documents. Normalized vectors was used in all models and experiments described in this contribution.
This structure can by used for determination similarities between pairs of words – two words will have high similarity, if they will be situated in same documents and only seldom is one word occurred without another. Some words are combined into combined query statements by using the commutative vector sum.
The term-document matrices are typically very
sparse. Information could be concentrated in low
number of dimensions when we use singular values
from decomposition, transformation each word into
n-dimensional subspace. This guarantees method
of least squares. Each word is then represented by using
n most significant latent variables. This process is called
latent semantic analysis – LSA [
At investigation dependencies of words in the word
space we can use logical operations, mainly primarily
negation in relations of orthogonality and disjunction in
relations of the vector sum of subspaces.
3.1 Vector negation
We would like to model meaning of expression
„koruna NOT klenot“ (koruna – crown as a coin, klenot
– crown as a jewel) in a such way, that system will be
able to awake, that we are interested in finances,
but not about meaning of the word koruna in the sense
of the jewel. Therefore we need to find aspects of
meaning the word koruna which are different from the
word koruna as a jewel, and have no relation to this
word. Word meanings have not interrelationship if they
have not any common marks. Document is considered
as irrelevant for user if the inner product with user
query is equal to zero, when query vector and document
vector are orthogonal [
Definition 1. Two words a and b are considered as
irrelevant to each other, if their vectors are orthogonal,
i.e. a a b are irrelevant to each other, if a ⋅ b = 0 [
A┴ ≡ {v ∈V: ∀a∈ A, a · v = 0}.
If A and B are subspaces of the space V, then NOT B represent B┴ and A NOT B represent projection A into B┴. When a, b belongs to V, then a NOT b represent projection a into <b>┴, where <b> is the subspace {λb : λ∈R}.
These definitions can be used for realization calculations with vectors in vector space. We apply standard method of projection.
Theorem 1. Let a, b are subsets of V. Then a NOT b is represented by vector a NOT b = a − a ⋅ b
2 b , b 2 where b
= b ⋅ b is length of the vector b [
Example: When we are doing inner product with b, then we obtain (a NOT b)⋅ b = a − ab⋅2b ⋅ b = a ⋅ b − (a ⋅ b)(b ⋅ b) b ⋅ b This proves that a NOT b and b are orthogonal, therefore vector a NOT b is certainly part of a, that is irrelevant to b (Definition 1), as we required.
When we have normalized vectors, then Theorem 1 has following form
a NOT b = a − (a ⋅ b)b .
For the purpose of finding expressions or documents, which correspondent to a NOT b, is not important for each candidate from a as well as b consequently determine certain differences. Theorem 1 shows that finding similarity between another vector and a NOT b is simple calculus of inner product.
With concept of quantum logic we met for the first time
in the theory of the quantum mechanic, which was
presented by Birkhoff and von Neumann (1936) [
The structure of the quantum logic is simple and we
can obtain it by substitution of sets and subspaces by
vector spaces and subspaces [
Disjunction
A AND B = A ∩ B A OR B = A + B
NOT A = A⊥ It is simple to prove, that these three operations on L(V) are sufficed to realize any necessary relations ( A + A⊥ = V , A ∩ A⊥ = 0 ) and to define logic on L(V).
The important piece of knowledge is also that every subspace A ∈ L(V ) can be identified (by using scalar product) with special projective map PA : V → A and through this bijection is logic of subspaces L(V) equivalent to logic of projection mapping in the vector space V.
The quantum logic is distinguished from Boolean logic at least in two properties: quantum logic is not distributive as well as commutative.
The disjunction in set theory can be modeled as union of sets, which corresponds in linear algebra to the vector sum of subspaces, where A+B is the smallest subspace of V containing A as well as B.
For determination of similarity between arbitrary
objects is necessary to define some function
σ: D × D → R. These functions assign a real number to
pair of objects oi, oj from their domain area D. This
formula will be a measure of similarity relation
of objects, which must satisfy following requests:
1. σ (oi, oj) ≥ 0
2. σ (oi, oj) = σ (oj, oi) , i.e. remaining of symmetry
3. when oi = oj, than σ (oj, oi) = max σ (ok, ol); for ∀ ok,
ol ∈ D
Definition 3. Let terms b1 ... bn ∈ V. Term b1 OR ... OR
bn is represented by thesubspace [
B = {λ1b1 + K + λ nbn : λ i ∈ R}.
The search of similarity relation between an individual term a and a general subspace B, is more complicated as a search of similarity relation between individual terms.
From the look of quantum physic, we can use PB
to measure a probability that any element was found
in some state [
In practice, if the set {bj} is orthonormal then it is
not correct only to calculate sim(a,bj) for every vector bj
in order. For obtaining an orthonormal base {b~j } for
subspace B is convenient firstly construct orthonormal
base for B by in practice used Gram-Schmidt method
[
PB (a) = ∑ (a ⋅ b~j )b~j
j sim(a, B) = ∑ (a ⋅ b~j ).
j For enumeration sim(a,B) we need to calculate ~ a scalar product a with every vector b j . This similarity relation is more difficult to calculate as in Theorem 1. The result which we reached by comparing every document a NOT b using only one operation - scalar product, is the loss for disjunction, although how we will show later, but is desirable for negated disjunction.
In this part is presented an introductory example
of vector connections which demonstrate usage of
vector negation and vector conjunction, vector
disjunction and negation together for finding vectors
which represent different meanings of ambiguous
words. We describe shortly a document of obtained
experiment. It shows that vector negation has smart
contribution contrary of classic Boolean method which
was described in paper [
Our word space was constructed from 28 articles written in year 2006 which was obtained from the Internet. The total number of acquired words was 5260. The collection of articles was focused on economy, culture, sport, health and science and from every sphere was processed at least two articles. Documents which concern meanings of the word koruna (crown as coin) are marked as D13, D14, D15. On the other hand, documents related to koruna (crown as jewel) are marked D10, D11, D
Over data source was created parser which separated
individual words from the text. By using morphological
analyzer [
The data in Table 1 represent that vector negation is very effective for selection of relevant documents which correspond to the required word koruna (crown) and left out the word klenot (jewel).
LSI regards k greatest singular values. The choice of k have to be enough small for obtaining faster access to documents, but enough great for adequate interception of structure of the corpus. koruna NOT klenot D14 D13 D15 D10 D24 D25 D27 D28 D26 D07 D22 D08 D04 D16 D06 D03 D21 D05 D20 D17 D18 D23 D09 D19 k=2 k=8
k=15
We realized a decomposition of matrix A for different values of k. The most relevant documents were obtained for value of factor k=15. On the contrary, for the very small k=2 is obtained great volume of documents. It reduces their relevance in regard to required document.
The vector negation and disjunction can be combined with selection of some searched query from areas of documents. We do not negate only one argument, but several. If the user determines that he wants documents related with a but not with b1,b2,...,bn, it will be interpreted (without next indication) that he wants only documents witch are not related with unwanted terms bi. In this way, the next expression
a AND (NOT b1) AND (NOT b2) ... AND (NOT bn) will pass into form
a NOT (b1 OR b2 ... OR bn).
By using Definition 3 we will form a disjunction b1 OR b2 ... OR bn as vector subspace B = {λ1b1 + ... +λnbn, λi ∈ R}. This term can be transformed on definite vector which is orthogonal to all irrelevant arguments {bj}. This vector will be a - PB(a), where PB is projection on the subspace B as in Theorem 1. This implies that calculus of the similarity between all vectors with term a NOT (b1 OR b2 ... OR bn) is the same as simple scalar product which has the same computing effectiveness as the Theorem 1. This technique is assigned to systematic reduction of irrelevant terms.
The negation in the vector space is suitable tool for dimension reduction of required documents. The specification of searched documents can be realized by using several disjunction operations in query. Our word space consisted of 5260 words. More relevant results can be obtained by application this method for largest document database.
Actual experiments represent calculus of similarity in the relation term-document. By construction of the vector space model we have represented individual occurrences in documents through Boolean function, i.e. we have expressed attendance if you like absence of the given term in the document.
Contemporary experiments will be in future carried out over lexical database of words and the word connections in the WordNet, where are recorded relative lexical and semantic relations between individual contained words or concepts.
In the next experiments we target our effort to calculation of similarity in relation term-term by various forms of representation the weight of individual term in the document.