Information Retrieval from the Ground Up - Philipp Krenn, Elastic

Key Concepts

• Retrieval Augmented Generation (RAG): Focusing on the retrieval aspect of RAG, which involves getting the right context for generation.
• Keyword/Lexical Search: Searching for documents based on the words they contain.
• Vector Search: Searching for documents based on their semantic similarity, using vector embeddings.
• Hybrid Search: Combining keyword and vector search techniques.
• Tokenization: Breaking down text into individual words or tokens.
• Stemming: Reducing words to their root form.
• Stop Words: Common words that are typically removed from search queries.
• Inverted Index: A data structure that maps words to the documents they appear in.
• Term Frequency-Inverse Document Frequency (TF-IDF): A scoring algorithm that measures the importance of a word in a document.
• BM25: An improved version of TF-IDF.
• Dense Vectors: Numerical representations of text that capture semantic meaning.
• Sparse Vectors: Representations of text that use a smaller number of dimensions, often based on word frequencies.
• Reciprocal Rank Fusion (RRF): A method for combining the results of multiple search queries.
• Rescoring: Re-ranking the top results from an initial search using a more expensive but accurate method.
• Analyzers: Components that process text before indexing or searching.
• Mappings: Schemas that define how different fields in an index behave.
• Engrams: Sequences of n characters extracted from a text.
• Slop: The number of words that can be missing or out of order in a phrase search.
• Fuzziness: The degree to which a search query can tolerate misspellings.

Keyword/Lexical Search

• Process:
  1. Tokenization: Breaking text into tokens based on whitespace and punctuation. Asian languages have more complex tokenization rules.
  2. Offset Calculation: Storing the start and end positions of each token for highlighting.
  3. Position Storage: Storing the position of each token for phrase search.
  4. Analysis Customization: Stripping HTML, lowercasing, removing stop words, and stemming.
• Example: Analyzing the phrase "These are not the droids you're looking for."
  • Tokenization results in: "these," "are," "not," "the," "droids," "you're," "looking," "for."
  • After stop word removal and stemming: "droid," "you," "look."
• Language-Specific Analysis: Using the correct analyzer for each language is crucial. Applying the wrong rules can produce garbage results.
• Stop Word Considerations:
  • Removing stop words can improve performance and reduce index size.
  • However, it can also remove important context, such as "not" in "to be or not to be."
• Inverted Index:
  • Data structure: Alphabetical list of tokens with pointers to documents and positions.
  • Enables fast retrieval by directly matching tokens.
• Phrase Search:
  • Requires storing token positions.
  • The slop factor allows for missing words.
• Fuzziness:
  • Allows for misspellings using Levenshtein distance.
  • The auto setting adjusts fuzziness based on token length.
• Scoring (TF-IDF/BM25):
  • Term Frequency (TF): How often a term appears in a document. BM25 flattens the curve to reduce the impact of very frequent terms.
  • Inverse Document Frequency (IDF): How rare a term is across the entire corpus. Rare terms are more relevant.
  • Field Length Norm: Shorter fields with a match are more relevant.
• Customizing Scores: Combining the default score with other factors, such as product margin or rating.
• Multi-Term Search: The algorithm calculates the relevancy of each term and combines them based on the angle between the term vectors.
• Coordination Factor: Rewards documents containing more of the search terms.
• Percentage Translation: Avoid translating scores into percentages, as they are only relevant within a single query and change with data updates.
• Engrams:
  • Breaking down text into sequences of n characters.
  • Useful for handling compound nouns in languages like German.
  • Can be expensive in terms of storage and query time.
  • Edge engrams only consider sequences starting from the beginning of a word.

Vector Search

• Dense Vectors:
  • Representing documents as numerical vectors in a high-dimensional space.
  • Semantic similarity is measured by the distance between vectors.
• Sparse Vectors:
  • Representing documents as a list of relevant tokens with associated scores.
  • The SPLADE model is used for sparse embedding.
  • Can be easier to interpret than dense vectors.
  • Can be expensive at query time due to the large number of tokens.
• Process:
  1. Model Selection: Choosing a pre-trained model or training a custom model.
  2. Embedding Generation: Converting text into dense or sparse vectors.
  3. Indexing: Storing the vectors in a vector database.
  4. Similarity Search: Finding the vectors that are closest to the query vector.
• Example: Using OpenAI's text embedding model to represent Star Wars characters in a vector space.
• Chunking: Breaking up long documents into smaller chunks to improve relevance.
• Challenges:
  • Choosing the right model and parameters.
  • Interpreting the results.
  • Defining a cutoff point for irrelevant results.

Hybrid Search

• Combining Keyword and Vector Search:
  • Leveraging the strengths of both techniques.
  • Keyword search is good for exact matches and specific terms.
  • Vector search is good for semantic similarity and finding related concepts.
• Reciprocal Rank Fusion (RRF):
  • A method for combining the results of multiple search queries based on their rank.
  • Less reliant on the individual scores.
• Rescoring:
  • Re-ranking the top results from an initial search using a more expensive but accurate method.
  • Useful for improving the quality of the final results.
• Filters:
  • Applying boolean filters to include or exclude certain documents.
  • Do not contribute to the score.

Practical Implementation and Considerations

• Elasticsearch:
  • A search engine that supports keyword, vector, and hybrid search.
  • Uses Apache Lucene for indexing and searching.
• Shared Instance: A shared Elasticsearch instance is provided for the workshop, with the URL and credentials (workshop/workshop).
• Index Naming: Participants are advised to use unique index names to avoid overwriting each other's data.
• Language Analyzers: Elasticsearch provides language-specific analyzers for tokenization, stemming, and stop word removal.
• API Keys: OpenAI API key is required to use the text embedding model.
• Data Structures: Elasticsearch uses inverted indexes for keyword search and HNSW (Hierarchical Navigable Small World) graphs for vector search.
• Query DSL: Elasticsearch provides a query DSL (Domain Specific Language) for constructing complex search queries.
• Painless Scripting: Elasticsearch supports Painless scripting for customizing scoring and other search behaviors.
• Performance Tuning:
  • Choosing the right data structures and algorithms.
  • Optimizing query performance.
  • Balancing accuracy and speed.
• Evaluation:
  • Using golden data sets and human experts to evaluate search quality.
  • Analyzing clickstream data to infer user satisfaction.
  • Using LLMs to evaluate search results.
• Use Cases:
  • E-commerce: Showing relevant products to increase sales.
  • Legal: Finding relevant legal cases.
  • Knowledge Management: Retrieving relevant documents from a large corpus.
• Trade-offs:
  • Accuracy vs. speed.
  • Storage vs. query time.
  • Complexity vs. maintainability.

Conclusion

The video provides a comprehensive overview of retrieval techniques, starting from classic keyword search and progressing to modern vector and hybrid search methods. It emphasizes the importance of understanding the underlying algorithms and data structures, as well as the trade-offs involved in choosing different approaches. The speaker highlights the versatility of Elasticsearch as a platform for building sophisticated search applications and offers practical advice for implementing and evaluating different search strategies. The key takeaway is that there is no one-size-fits-all solution for retrieval, and the best approach depends on the specific use case, data, and user expectations.