It is shown here that given any vector space retrieval model with dot product as its object similarity function, there exists a semantic network retrieval model such that the two models are equivalent under ranked retrieval.
Proof:Let ,
, and
. For each
,
define
where
and
are defined to be matrices
of all zeros,
|
, and
. If
,
where
completes
,
if
contains
,
and f is the dot product of two sequences. If there is no
such that
completes
, then
.
It is shown that by proving that for all
and for
,
.
( ) Let
such that
. Since
,
.
Since
is the dot product,
. By definition of
,
.
The ordering of the labels of nodes in the semantic network model may only decrease the
similarity between an object and the retrieval object. The dot product of two vectors
representing objects containing the same set of tokens will have non-zero entries in all
of those dimensions. In the spreading activation model two objects with the same set of
tokens may have labels that list the tokens in different orders. Only the label with the
tokens listed in the same order will allow completion. Hence
, and
.
But by construction there is at least one label
for
and
one label
for
such that
,
.
Thus
and
.
Hence
so that
,
and
.
( ) Let
such that
. By definition of
,
where
,
,
and
completes both
and
.
Since completes
and
, it must be the case that
and
=
.
By the definition of
this means that
.
This means that
so that
<
.
Thus
=
as claimed.