Learning in FOL with a Similarity Measure

Gilles BissonAAAI 1992

Abstract

This paper introduces a framework for performing similarity-based learning within First-Order Logic (FOL) by treating entity similarity as a system of equations. By iteratively propagating similarity scores through relational structures, the author provides a robust way to handle complex, multi-object data that traditional propositional logic struggles to represent.

Introduction: The Relational Matching Problem

In the early 1990s, machine learning was largely split between two paradigms. Valued Propositional Logic (VPL) was efficient and handled numerical data well but failed when the number of objects or their relationships varied—such as in molecular modeling. Conversely, First-Order Logic (FOL) offered high expressivity for complex structures but was computationally intensive and historically poor at handling "fuzzy" similarities.

The core challenge addressed here is the matching problem: given two examples with multiple entities, how do we determine which object in Example A corresponds to which in Example B? Without a reliable similarity measure for entities in a relational context, clustering and generalization in FOL remain prohibitively difficult.

Methodology: Similarity as a System of Equations

The author proposes a novel similarity measure that accounts for both the intrinsic attributes of an entity and its structural role within a system.

1. Typed Representation and Predicate Weights

The language distinguishes between entities (objects) and values (properties like "blue" or "22 years old"). It also introduces predicate weights, allowing users to define which relationships are most significant for the task at hand.

2. Recursive Similarity Propagation

The "secret sauce" of the paper is modeling similarity as a recursive property. The similarity between two entities $X$ and $Y$ depends on the similarity of the entities they are connected to. For example, two parents are considered more similar if their children are also similar.

3. Iterative Refinement (Jacobi’s Method)

Because similarity is recursive, it is modeled as a system of equations. To solve this, the author uses an iterative approach inspired by Jacobi’s method:

  • Iteration 0: Calculate a "crude" similarity based only on shared predicates.
  • Iteration $n$: Refine the similarity by propagating information from connected entities identified in the previous step.
  • Convergence: Information "flows" through the relational graph, with the influence of distant entities decreasing geometrically.
Table 1: Example of similarity scores calculated for individuals based on their relational occurrences.

Illustrative Examples

The framework was demonstrated using several domains to highlight its flexibility:

  • Chemical Structures: A toy example involving the representation of Ethanol illustrates the difficulty of labeling atoms based on their relational roles.
Figure 1: The structural representation of Ethanol used to demonstrate relational matching challenges.
  • Geometric Shapes: A small dataset of triangles and squares with properties like color and relative position ("left of") demonstrated the iterative similarity calculation.

Key Insights and Results

  • Relational Transitivity: Similarity is transitive. If Entity A is related to B, and Entity C is related to D, the similarity between A and C is influenced by the similarity between B and D.
  • Global Optimization: Matching is not a preprocessing step but a global optimization problem. By framing similarity as a matrix problem, linear algebra tools can find the "best" match across an entire relational structure.
  • Efficiency and Stability: The author demonstrates that 2–3 iterations are usually sufficient for a stable estimate, making the approach computationally feasible despite the theoretical NP-hardness of FOL matching.
  • Mathematical Convergence: The characteristic matrix of the similarity system is shown to be "diagonally dominant," ensuring that a solution can almost always be found.

Limitations

The framework faces challenges with non-linear instability in cases where an entity has multiple identical roles (e.g., a father with two sons). Furthermore, it currently only handles positive literals and does not account for negation. Finally, the computation remains quadratic relative to the number of examples and entities, which may limit scalability for very large relational databases.

Summary updated

BibTeX
@inproceedings{bisson1992learning,
  author = {Gilles Bisson},
  title = {{Learning in FOL with a Similarity Measure}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure