Orthogonal locality preserving indexing

Deng Cai, Xiaofei HeSIGIR 2005 · DOI

TL;DR

This paper introduces Orthogonal Locality Preserving Indexing (OLPI), a novel method for document indexing that aims to overcome the dimensionality sensitivity of existing techniques like Locality Preserving Indexing (LPI). By ensuring orthogonal basis functions, OLPI preserves the document space's metric structure, leading to more stable and often superior performance in tasks like similarity evaluation and clustering.

What Problem Does This Paper Address?

Representing and indexing documents efficiently is crucial for information retrieval, clustering, and classification. Traditional methods like Latent Semantic Indexing (LSI) focus on global Euclidean structure, while Locality Preserving Indexing (LPI) emphasizes local manifold structure. However, LPI suffers from a significant drawback: its performance is highly sensitive to the chosen dimensionality. An inaccurate estimation of the intrinsic dimensionality can drastically degrade LPI's effectiveness, sometimes even making it perform worse than the original representation. This sensitivity stems from LPI's non-orthogonal basis functions, which distort the metric structure of the document space. The paper aims to develop a method that retains LPI's strength in capturing local structure while mitigating its dimensionality sensitivity.

Methods

The core contribution of this paper is the Orthogonal Locality Preserving Indexing (OLPI) algorithm. OLPI builds upon the principles of LPI but introduces a crucial modification: it computes mutually orthogonal basis functions. This orthogonality is key to preserving the metric structure of the document space.

The OLPI algorithm involves several steps:

  1. PCA Projection: Documents are initially projected into a subspace using Principal Component Analysis (PCA) to decorrelate features and reduce dimensionality without losing information.
  2. Adjacency Graph Construction: A graph is built where nodes represent documents. Edges are established between documents considered "close" (e.g., within the $p$ nearest neighbors).
  3. Weight Computation: Weights ($S_{ij}$) are assigned to edges based on the similarity between connected documents.
  4. Orthogonal Locality Preserving Projections: This is the novel part. The algorithm iteratively computes orthogonal basis vectors. The first vector is an eigenvector of a specific matrix derived from the graph Laplacian and the PCA-projected data. Subsequent vectors are computed by minimizing a locality preserving function subject to orthogonality constraints with previously computed vectors. This iterative process ensures that the new basis functions are orthogonal and respect the local geometric structure.
  5. OLPI Embedding: The final document representation is obtained by transforming the PCA-projected documents using the computed orthogonal basis vectors.

The paper also provides theoretical justifications, showing that minimizing the locality preserving function with orthogonality constraints leads to the OLPI algorithm.

Datasets

The paper evaluates its proposed algorithm on two main datasets:

  1. TDT2 Corpus: This corpus consists of news articles from various sources (newswires, radio, television) collected in 1998. For experiments, the authors selected the largest 20 semantic categories, resulting in 8741 documents. Documents were represented as term-frequency vectors.
  2. 30 TREC Ad Hoc Topics: For similarity evaluation, the authors used 30 document subsets derived from TREC ad hoc topics (topics 251-550). These subsets were created by selecting keywords with high frequencies and forming document collections around them. This approach allowed for comparing algorithms on different "queries" or thematic collections.

Key Insights and Ideas

  • Orthogonality is Key to Stability: The paper strongly suggests that the non-orthogonality of LPI is the root cause of its sensitivity to dimensionality. By enforcing orthogonality, OLPI preserves the metric structure, making it robust to dimensionality choices.
  • Local Structure Preservation is Crucial: Both LPI and OLPI demonstrate that preserving local geometric structure is vital for effective document representation, often outperforming LSI, which focuses on global structure.
  • OLPI Offers a Better Trade-off: OLPI appears to offer the best of both worlds: it retains the locality-preserving power of LPI while adding the stability and metric preservation benefits of orthogonal bases.
  • Dimensionality Reduction is Essential: Experiments consistently show that achieving good performance in tasks like clustering and similarity evaluation requires significant dimensionality reduction, and OLPI excels at this.

Key Results

  • Superior Performance: In similarity evaluation experiments (Figure 2), OLPI consistently achieved higher average precision than LSI and, importantly, was less sensitive to the dimensionality reduction rate than LPI.
  • Clustering Accuracy: For document clustering (Figure 4), OLPI demonstrated strong performance, often reaching its peak at very low dimensions and maintaining a stable performance above the baseline. LPI's performance, in contrast, degraded significantly after its optimal dimension. LSI did not outperform the baseline in clustering.
  • Locality Preserving Power: Figure 1, comparing eigenvalues of LPI and OLPI, shows that OLPI's eigenvalues are consistently smaller, indicating a greater locality preserving power. This is directly linked to its improved performance.

Limitations and Future Work

  • Linearity Assumption: The current OLPI algorithm is linear. The authors acknowledge that document spaces might be non-linear and suggest that extending OLPI to reproduce kernel Hilbert spaces could lead to better performance. However, they note the challenge of identifying the true geometric structure in high-dimensional spaces.
  • Connectedness Assumption: The current work assumes the document space is connected. The authors propose investigating scenarios where the document space might be disconnected, with components having different dimensionalities, and how to handle such cases.
  • Real-world Applicability: While OLPI shows promise, further investigation into its performance on diverse, real-world datasets and its scalability for very large corpora would be beneficial.

Summary updated

BibTeX
@inproceedings{cai2005orthogonal,
  author = {Deng Cai and Xiaofei He},
  title = {{Orthogonal locality preserving indexing}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2005},
  doi = {10.1145/1076034.1076039},
}
Figure