Introduction
Building large-scale knowledge bases often relies on crowdsourcing, where human contributors provide simple facts or "default rules." While humans are adept at identifying typical patterns—such as "birds typically fly"—they often struggle to maintain logical consistency across complex rule sets. Most human knowledge is "defeasible," meaning it consists of general truths that admit exceptions (e.g., "penguins are birds that do not fly").
Existing reasoning systems, such as System P, typically require perfectly consistent inputs. However, crowdsourced data is inherently noisy and often contains conflicting rules. This research addresses a critical gap: how to learn a coherent, stratified logical theory from a messy and inconsistent set of human-provided default rules.
Methodology: Possibilistic Logic and Stratification
The authors frame the challenge as a machine learning problem, aiming to find a "possibilistic logic theory" that accurately classifies the validity of new default rules.
Core Concepts
The framework utilizes Possibilistic Logic, where rules are organized into "strata" or levels. General rules are placed at lower levels, while specific exceptions occupy higher levels. In the event of a conflict, the higher-level (more specific) rule overrides the lower-level one, ensuring logical consistency.
Complexity and Algorithm
Theoretical analysis reveals that determining the existence of a perfect theory for a given set of examples is $\Sigma^P_2$-complete. To manage this computational complexity, the authors propose a greedy heuristic learning algorithm based on the principle of Structural Risk Minimization. The algorithm iteratively samples misclassified examples, generates candidate clauses, and adds them to the theory to maximize accuracy while minimizing model complexity. Finally, it prunes unnecessary literals to maintain high interpretability.
Datasets and Evaluation
The approach was evaluated using two distinct data sources:
- Crowdsourced Rules: Human "expert" rules were collected via the CrowdFlower platform for American Football (play-calling) and Texas Hold’em Poker (betting strategies).
- Markov Logic Networks (MLNs): The method was tested on four standard benchmarks—NLTCS, MSNBC, Plants, and DNA—to determine if possibilistic logic could effectively approximate complex probabilistic inference.
Key Results and Insights
The proposed method demonstrates that logical consistency can be a powerful feature rather than a constraint. Unlike standard classifiers like Random Forests, which may produce logically impossible predictions, this method guarantees a consistent theory.
Performance Comparison
Quantitative results show that the heuristic algorithm is highly competitive with established machine learning models. On the Poker dataset, it achieved 40.5% accuracy, outperforming Random Forests and RIPPER. In the NLTCS and MSNBC datasets, the learned logic theories actually surpassed standard classifiers, reaching accuracies as high as 78.1%.
Interpretability vs. Accuracy
One of the most significant advantages of this approach is the compactness and readability of the resulting models. In the poker experiments, the learned logic theory was ten times smaller than a corresponding decision tree. Despite its size, it captured sophisticated strategies and their exceptions.
Conclusion
This research bridges the gap between logic and probability by providing a method to "compress" complex distributions into human-readable, consistent logical theories. While the current greedy search heuristic does not guarantee an optimal theory, the results indicate that it produces models that are both accurate and highly auditable. Future work will focus on handling even noisier data and integrating these learned theories into larger automated reasoning systems.
Summary updated