TL;DR
This paper introduces a novel string pattern matching algorithm for video question answering (videoQA) that significantly outperforms existing methods. By leveraging suffix trees to find common subsequences between questions and video passages, the system achieves state-of-the-art results in retrieving relevant video segments.
What Problem Does This Paper Address?
The explosion of video content has created a demand for effective ways to search and retrieve information within videos. While text-based question answering (QA) has seen significant progress, extending this capability to multimedia, particularly video, remains a nascent field. Traditional videoQA systems often rely on complex approaches involving external knowledge bases or extensive manual annotation. This paper addresses the challenge of building a robust and efficient videoQA system that can directly answer natural language questions by retrieving relevant video passages, without requiring extensive external resources or manual effort. The core problem is to accurately rank video passages based on their relevance to a given question in the presence of OCR errors and the inherent complexity of video data.
Methods
The proposed system introduces a string pattern matching-based passage ranking algorithm for videoQA. The core innovation lies in using suffix trees to efficiently find common subsequences between a question and video passages.
Here's a breakdown of the key techniques:
- Video Processing Pipeline: The system first processes raw video frames to extract text using an OCR (Optical Character Recognition) pipeline. This involves text detection, binarization, frame tracking, and finally OCR to convert image text into ASCII.
- Sentence and Passage Segmentation: Extracted text is segmented into sentences, and then every three consecutive sentences are grouped into a "passage." This passage unit is considered a natural and informative segment for answering questions.
- Tokenization: Both questions and passages are tokenized at multiple granularities: unigram, bigram, and trigram.
- Initial Retrieval: To reduce the search space, a BM-25 ranking model is used to retrieve the top-1000 most relevant passages as initial candidates.
- String Pattern Matching: The heart of the algorithm is the use of suffix trees to find common subsequences between the question (Q) and each candidate passage (P). This allows for identifying shared textual patterns.
- Scoring Function: A novel scoring function,
Passage_Score(P) = λ × QW_Density(Q, P) + (1-λ) × QW_Weight(Q, P), is introduced. QW_Density(Q, P)measures how densely the matched question words appear in the passage, taking into account subsequence length and a discriminative power (DP) score.QW_Weight(Q, P)estimates the content information of the passage relevant to the question, also utilizing subsequence information.- Retokenization and DP Score: Algorithms are proposed for retokenizing subsequences to avoid overly long matches and for computing the discriminative power (DP) of subsequences, extending the BM-25 schema.
- Passage Scoring Optimization: The final passage score considers the density and weight of matched question words in both the head and tail fragments of a passage, recognizing that answers are often localized.
Datasets
- Discovery Videos: The evaluation was conducted on a dataset comprising 75.6 hours of Discovery videos (93 video names). This dataset was chosen due to its popularity in multimedia research.
- Chinese Questions: 253 Chinese questions were collected for evaluation. These questions were derived from previous studies and real user logs.
- Annotation: Answers were annotated by following TREC-QA and NTCIR guidelines. Crucially, for evaluation, the recognized text was mapped to corresponding video frames to account for OCR errors and ensure accurate assessment. 368 passage&frame segments were labeled as answers.
Key Insights and Ideas
- Passage as a Natural Unit: The paper validates the intuition that passages (groups of sentences) are more suitable and informative units for video answers than short phrases, providing richer context.
- Suffix Trees for Subsequence Matching: Leveraging suffix trees for finding common subsequences between questions and video passages is a powerful and efficient approach for identifying relevant textual overlap.
- Impact of Word Segmentation: Surprisingly, using a highly-trained Chinese word segmentation tool decreased the performance of most ranking models, including their own. This highlights the robustness of their unigram-based approach in the face of OCR errors and the challenges of accurate segmentation in noisy text.
- Density and Weight are Complementary: The proposed scoring function, which combines "question word density" and "question word weight," performs better than using either component alone, indicating that both the presence and the importance of matched terms contribute to relevance.
- Head/Tail Passage Scoring: Focusing the scoring on the head and tail fragments of a passage improves performance, suggesting that answers are often concentrated at the beginning or end of a relevant segment.
Key Results
- State-of-the-Art Performance: The proposed string pattern matching algorithm achieved the best performance among seven compared ranking models.
- MRR Improvement: It outperformed the second-best method (language model) by 10.16% in terms of MRR (top1) score and 7.39% in MRR (top5) score.
- Precision and Recall: The method achieved a precision rate of 0.208 and a pattern recall rate of 0.711, also outperforming other models.
- Handling Non-Answered Questions: The proposed method covered the most non-answered questions, indicating its effectiveness in identifying relevant passages even when a direct answer isn't present.
- Word Segmentation Detriment: Using a sophisticated word segmentation tool led to performance drops of at least 10% in MRR, precision, and pattern-recall for most models, including their own.
Limitations and Future Work
- Limitations:
- The paper acknowledges that the performance of their method is negatively impacted by the use of a trained Chinese word segmentation tool, suggesting that their unigram-based approach is more robust to OCR errors.
- The study focused on text-based retrieval within video; multi-modal features (audio, visual) were not integrated.
- Future Work:
- The authors plan to integrate other useful features from videos (e.g., audio, visual cues) to support multi-model-based multimedia question answering.
- A demo version of their videoQA system is available online.
Summary updated