TL;DR
This paper tackles the challenge of classifying documents in a "one-class" setting, where only positive examples are readily available, by combining information from multiple sources (text and social network data). They introduce a novel "Mapping Co-Convergence" framework that extends existing one-class classification methods to effectively leverage these diverse data modalities, leading to improved performance in identifying responsive documents in large email corpora.
What Problem Does This Paper Address?
In many real-world scenarios, like legal discovery, we need to identify specific types of documents (e.g., those relevant to a lawsuit) when we have plenty of examples of what we're looking for, but very few (or no clear examples) of what we're not looking for. This is known as the "one-class classification" problem. Traditional methods struggle when the "negative" class is ill-defined or vast. Furthermore, documents, especially emails, contain more than just text; they implicitly encode social relationships between senders and receivers. Existing classification methods often overlook this rich social network information, focusing solely on textual content. This paper aims to bridge this gap by developing a method that effectively combines textual and social network information within a one-class classification framework to improve accuracy.
Methods
The core of the paper lies in their proposed Mapping Co-Convergence framework. This method builds upon the Mapping Convergence (MC) algorithm, which iteratively refines a decision boundary by using a one-class SVM to classify unlabeled data as negative. The key innovations are:
- Multi-modality: Instead of relying on a single data representation (like text), they extract features from two distinct "views" of the documents:
- Text-based: Standard bag-of-words representation (using TF-IDF, binary, or frequency weighting).
- Social Network-based: Features derived from the communication network of email senders and receivers (e.g., centrality measures, hub/authority scores, clique information).
- Mapping Co-Convergence: This is an extension of the Mapping Convergence algorithm that explicitly handles multiple views. At each iteration, it aggregates predictions from classifiers trained on each view. This aggregation helps identify items that are confidently classified as negative across multiple modalities, leading to a more robust negative set for training. This process is designed to be more resilient to noise and improve convergence.
- One-Class SVM (OC-SVM): They utilize OC-SVM as the underlying classifier, which is well-suited for identifying a boundary around positive examples without explicit negative data.
- PP Measure: A novel performance evaluation metric is introduced, the "PP measure," which plots the percentage of the entire dataset classified as positive against the percentage of true positives retained. This is crucial for one-class settings where true labels for unlabeled data are unknown.
Datasets
The paper uses the following datasets:
- Enron Corpus: A large collection of approximately 250,000 emails from 150 top managers of Enron Corporation. This corpus is central to the study, as it provides rich email communication data from which both text and social network features can be extracted. A subset of 186 emails identified as "responsive" from government exhibits (DOJ) serves as the positive training data.
- INEX08 Wikipedia Challenge Corpus: Used for evaluating the framework on a standard text classification task. It contains text files with subject class labels.
- Letter Recognition Dataset (UCI ML Repository): Used to evaluate the framework on a non-sparse dataset with numerical features.
Key Insights and Ideas
- Social context matters: The implicit social network within email communication provides valuable information for classification that text alone misses. Understanding who is communicating with whom significantly aids in determining document relevance.
- Multi-modality is key for one-class problems: When negative examples are scarce or ill-defined, combining information from different sources (text, social network) provides a more comprehensive view of the data, leading to better decision boundaries.
- Co-training principles enhance one-class learning: Adapting co-training ideas to the one-class setting, where multiple views interact and agree on classifications, significantly improves robustness and performance.
- Iterative refinement is crucial: The Mapping Convergence and Co-Convergence approaches demonstrate that iteratively building a set of confident negative examples from unlabeled data is an effective strategy for one-class classification.
- Novel evaluation metric is necessary: The PP measure is a valuable contribution, offering a way to assess classifier performance in a true one-class scenario where ground truth for unlabeled data is unavailable.
Key Results
- Improved Performance: The proposed Mapping Co-Convergence framework, combining text and social network features, achieved the best results on the Enron Corpus. Specifically, it retained 93% of the positives while discarding 90% of the unlabeled data.
- Text vs. Social Network: Both text-based (TF-IDF) and social network-based features individually contributed to classification, but their combination yielded superior results.
- Parameter Sensitivity: The performance of OC-SVMs, and by extension the proposed framework, can be sensitive to parameter choices (like
vandgamma), requiring careful tuning. - Feature Reduction: For the Enron text data, reducing the number of features did not improve performance, unlike in some other text classification tasks.
Limitations and Future Work
- Parameter Sensitivity: The authors acknowledge that the algorithms are somewhat sensitive to parameter selection, and while some parameters can be chosen based on their properties, others require empirical tuning.
- Instability from Cross-Validation: The use of random cross-validation for handling unlabeled data introduces some instability, which could be mitigated by higher fold cross-validation at the cost of computational expense.
- Confidence Measure: The method for estimating confidence in predictions is based on the distance to the decision plane, which is a simplification. More advanced confidence estimation techniques could be explored.
- Aggregation Function: The naive averaging of predictions from different classifiers is a simple approach. Future work could investigate more sophisticated aggregation functions.
- Joint Modality Processing: The paper uses a two-step ensemble approach. Future research could explore methods that jointly process different modalities, rather than combining them sequentially.
Summary updated