FOA Home
We can make a similar guess that (at least some small sets of) keywords
are similarly correlated, and that the vector space representation of a
document corpus (cf. Section §3.4 )
might be simplified in a similar way. The goal is to ``reduce the
dimensionality'' of the documents' representation in the same way as we
reduced that of our students' sizes.
But while we can draw a simple
picture revealing the correlational structure between two dimensions,
the picture is much more complicated when we try to conceive of the full
$V 10^{5}$ space of index terms. For the $D$ vectors we seek a smaller
$k
One of the
most effective ways to characterize the correlational structure among
large sets of objects is via EIGENFACTOR ANALYSIS . The technique
we consider is called SINGULAR VALUE DECOMPOSITION . This factors
any rectangular matrix into three terms: J = U L A^{T} where $U$ and $A$
are each ORTHONORMAL , and $L$ is a diagonal matrix
``connecting'' them. $ and vice versa. An orthonormal matrix contains
mutually orthogonal vectors of unit length. The most common example of
an orthonormal set o vectors are the column vectors of the identity
matrix $\mathbf{I}$, corresponding to the coordinate vectors, but any
rotation of this system is also orthonormal.}
As before (cf. Equation
(FOAref) ) using inner product to measure similarity, we can
define $X$: X = J J^{T} Since $J$ is a $D \times V$ matrix, $X$ is a $D
\times D$ symmetric, square matrix capturing all $D \choose 2$
inter-document simularities. Then $U$ is the system of eigenvectors of
$X$ and $L$ has the squareroot's of the eignenvalues
$\sqrt{\lambda_{i}}$ along its diagonal. By convention, we order these
in decreasing order:
Large eigenvalues correspond to dominant
correlations and so, just as looking for the
As
always, anytime we throw something away (viz., the small eigenvectors),
the result must be an approximation. That is, there will be a difference
bewteen our reduced-dimension representation $J_{k}$ and the original
$J$.
One easy way to measure this discrepancy is by refering to the
$D^{2}$ inter-document similarities latent in the $X$ matrix, and
consider how much different they are in the approximate matrix $X_{k}$
X_{k}= J_{k} J_{k}^{T} using the $L_{2}$ norm $|| \cdot ||_{2}$ to
measure deviation. Then: \mathname{Err} = ||X-X_{k}||_{2}
In fact,
approximating $X$ with its reduced $k$-rank SVD decomposition turns out
to be optimal, in the sense that it results in mininal $$ over all other
rank-$k$ alternatives [REF865] .
Top of Page
Singular value decomposition
SIZE dimension
which captured the main interaction between HEIGHT and
WEIGHT, we will rely on the first $k$ dimensions to capture
the dominant modes of interaction in $J$. J_{k} = U_k L_k A_k^T This
operation is shown schematically in Figure (figure) .