Source-linked AI summary
Probabilistic Similarity Logic
Matthias Brocheler, Lilyana Mihalkova, Lise Getoor
TL;DR
Existing relational-learning frameworks support probabilistic reasoning over noisy multi-relational structure but lack direct support for reasoning about similarities. PSL introduces joint probabilistic reasoning over relational structure and similarity, including set similarity, and demonstrates effectiveness on relational tasks and similarity-focused applications.
Problem
Existing SRL frameworks support structural regularities and probabilistic inference but do not directly support reasoning about similarities in relational domains.
Method
PSL uses annotated rules and a joint probabilistic model to combine relational reasoning with domain-specific similarity measures and set-level similarity, with inference formulated as a cone program.
Results
PSL is effective on document similarity and ontology alignment, including an F1 score of 0.865 on the ontology-alignment benchmark.
Takeaways & Limitations
PSL provides a general framework for integrating similarity measures and relational structure, and its set constructs and similarity inference were experimentally validated.
Takeaways & Limitations
The evaluation could not assess the quality of PSL's inferred similarity values directly and instead used similarity post-processing for comparability.
Abstract
from arXiv · showhide
Many machine learning applications require the ability to learn from and reason about noisy multi-relational data. To address this, several effective representations have been developed that provide both a language for expressing the structural regularities of a domain, and principled support for probabilistic inference. In addition to these two aspects, however, many applications also involve a third aspect-the need to reason about similarities-which has not been directly supported in existing frameworks. This paper introduces probabilistic similarity logic (PSL), a general-purpose framework for joint reasoning about similarity in relational domains that incorporates probabilistic reasoning about similarities and relational structure in a principled way. PSL can integrate any existing domain-specific similarity measures and also supports reasoning about similarities between sets of entities. We provide efficient inference and learning techniques for PSL and demonstrate its effectiveness both in common relational tasks and in settings that require reasoning about similarity.
1 Introduction
Probabilistic relational frameworks support structural regularities and uncertainty, but existing SRL frameworks do not directly support reasoning about similarities. PSL addresses this gap by jointly modeling relational structure and similarity, including set-level similarity, across applications such as document similarity and ontology alignment.
- Existing SRL representations combine a language for structural regularities with principled probabilistic inference, but omit direct support for reasoning about similarities.
- PSL jointly reasons about relational structure, similarity, and uncertainty in similarity propagation using annotated rules and a joint probabilistic model.
- PSL integrates existing domain-specific similarity measures into relational reasoning and supports similarity between sets of entities.
- In linked-document settings, document and user similarities are entangled, while relational patterns such as frequent user interaction can also inform document similarity.
- Ontology alignment requires graded similarity reasoning because different vocabularies often provide no exact concept or relationship matches.
- The paper evaluates PSL on document similarity and ontology alignment and reports state-of-the-art ontology-alignment performance using domain-specific similarity measures.
2 PSL
PSL is a relational framework that represents similarities as continuous values, propagates them through annotated rules, and defines a probability distribution for joint inference. Its set constructs improve modeling flexibility and grounding efficiency, while inference and learning use convex optimization and MAP-based approximations.
- Syntax and semantics: PSL propagates similarities through relational structure using annotated rules and represents a probability distribution over similarities between entities or sets.Its rules combine soft rules, hard constraints, and exclusivity constraints.
- Syntax and semantics: PSL supports typed entities, attributes, relations, relation-defined sets, and arbitrary similarity functions over appropriate pairs of entities or sets.The framework provides both first-order and object-oriented shorthand, with sets expressible through relation-defined collections.
- Similarity reasoning: Similarity reasoning combines domain-specific similarity measures with relational structure, including similarities between attributes and between the sets of entities related to two entities.This supports applications such as document similarity and ontology alignment, where relational evidence and similarity measures interact.
- Set constructs: Set constructs avoid grounding-count distortions and reduce computation: rule (8) uses one grounding per concept pair, versus k^2 for rule (7), where k is the maximum relation size.Set-based consequents also capture intended similarity between aligned sub-concepts more directly than enumerating individual pairings.
- Inference and learning: PSL MAP inference transforms activated grounded rules into a second-order cone program, and under the paper’s choices solves it in O(|R|^3.5) time.The stated choices include linear or conic similarity functions, the Lukasiewicz t-(co)norm, and L1- or L2-norm distance functions.
- Inference and learning: Weight learning uses BFGS or the Perceptron algorithm while approximating an intractable expectation with the distance value in the MAP state.The experiments use the L1 distance function.
3 Experiments
The experiments evaluate PSL on Wikipedia category prediction, similarity propagation, and ontology alignment, then test the contributions of relational rules, similarity reasoning, and set constructs. PSL improves over attribute-only baselines, achieves an F1 score of 0.865 on real bibliographic ontologies, and complete PSL outperforms setFree-PSL under noise.
- Experimental scope: PSL is evaluated on category prediction and similarity propagation for Wikipedia documents, plus ontology alignment on bibliographic ontologies.The evaluation addresses PSL’s effectiveness for relational inference and the usefulness of its novel features.
- Wikipedia methodology: The Wikipedia experiments split documents into equal training and test sets, remove cross-set relations, and average Figures 1 and 2 over 16 independent runs.Naive Bayes predictions provide evidence for collective classification, while rule weights are learned with BFGS.
- Wikipedia results: 10.6% average F1 improvement comes from adding link and talk relationships to the attribute-only collective-classification baseline.Adding links alone improves the baseline by 6.5%, and improvements are larger with smaller training corpora; all differences are statistically significant at p = 0.01.
- Wikipedia results: Link and talk relationships yield a huge improvement over the attribute-similarity baseline for category propagation, showing that PSL exploits relational structure.In this task, document text is used only to compute pairwise similarity rather than directly as classifier features.
- Ontology alignment: 0.865 F1 is obtained by PSL on real bibliographic ontology alignment, using one ontology pair for training and three remaining pairs for testing.The reported score is averaged over all possible test ontology pairs in the benchmark.
- Utility of sets: Complete PSL consistently outperforms setFree-PSL on ontology alignment with structural and attribute noise, improving by 9.3% to 57% as attribute noise increases.The comparison averages 10 independent trials, with structural noise levels of 0.2 and 0.4; all differences are statistically significant at p = 0.01.
4 Related Work
PSL extends statistical relational learning by adding principled reasoning about entity and set similarities while retaining probabilistic relational reasoning. Compared with related frameworks, it restricts numeric predicates to similarities and supports tractable inference in the studied subset.
- For ontology alignment, the discrete solver could not be tuned to find an optimal solution, possibly because of complex relational structure and extensive set constructs.
- PSL combines probabilistic reasoning over relational structure with reasoning about similarities between entities and sets.This extends prior SRL capabilities with unified similarity reasoning.
- Unlike Hybrid MLNs, PSL supports set similarity and uses t-(co)norms to combine logical and similarity reasoning.PSL restricts numeric-valued predicates to similarities in [0, 1].
- Hybrid MLNs combine numeric and Boolean values by multiplication, whereas PSL permits a variety of truth-combining functions.The paper uses Lukasiewicz t-(co)norms because they lead to sparser grounded programs.
5 Conclusions and Future Work
The paper introduces a framework for probabilistic reasoning about similarity in relational domains and demonstrates it on two tasks. It validates set constructs and similarity inference, while identifying broader domains and similarity-valued ground truth as future directions.
- PSL integrates probabilistic reasoning about similarity within a relational context and is demonstrated on two tasks involving similarity reasoning.
- Experiments validate the utility of PSL’s set constructs and similarity inference, both identified as novel supported features.
- Future work includes studying alternative distance-from-satisfaction functions, such as L2 distance, and applying PSL to other domains.
- The paper especially seeks domains where PSL can be validated against ground-truth data containing similarity values.