Learning by Analogy: A Classification Rule for Binary and Nominal Data

Sabri Bayoudh, Laurent Miclet, Arnaud DelhayIJCAI 2007

Abstract

Traditional instance-based learning often relies on proximity metrics, assuming that similar objects belong to the same class. This paper proposes an alternative approach based on analogical proportions—the relational logic that "object $A$ is to $B$ as $C$ is to $D$." By formalizing this concept for binary and nominal data, the authors introduce the Analogical Proportion Classifier (APC). This method identifies relational patterns among triplets of training data to predict the class of a query object. Experimental results on UCI benchmarks show that this approach, particularly its weighted version (WAPC), achieves high accuracy on complex logical problems where distance-based methods often struggle.

Introduction: Beyond Proximity

Most instance-based learning algorithms, such as k-Nearest Neighbors (k-NN), operate on the principle of proximity: if a new object is close to a known object in feature space, they likely share a class. However, this ignores the underlying relational logic between objects.

Consider the relationship between animals. A "calf" relates to a "bull" in a specific way (young/male). If we observe a "kitten," we can infer its relationship to a "tomcat" based on that same pattern. While a distance metric might see a kitten and a tomcat as distinct from a calf and a bull, an analogical classifier recognizes the shared relational structure.

Figure 1: Relational attributes of animals illustrating analogical proportions.

The challenge addressed in this research is formalizing these "analogical proportions" ($a:b :: c:d$) for categorical data and implementing them in a computationally efficient classification framework.

Methodology

The core of the proposed system is the Analogical Proportion Classifier (APC). Unlike k-NN, which looks at single neighbors, APC looks at triplets $(a, b, c)$ from the training set to find a solution for the class of a query object $x$.

Analogical Dissimilarity (AD)

In real-world, noisy datasets, perfect analogies are rare. To handle this, the authors define Analogical Dissimilarity (AD). This metric quantifies how far a set of four objects is from forming a perfect analogy by counting the necessary bit flips. In binary space, an analogical proportion follows a "parallelogram" logic.

Figure 3: Valid vs. invalid analogical proportions in binary space.

The Classification Rule

To classify a new object $x$, the algorithm:

  1. Searches for triplets $(a, b, c)$ in the training set.
  2. Evaluates the relationship $class(a) : class(b) :: class(c) : class(x)$.
  3. Selects the $k$ triplets with the lowest AD.
  4. Uses these triplets to "vote" on the most likely class for $x$.

Optimization and Weighting

To make the search feasible, the authors developed the FADANA algorithm, which uses base prototypes to prune the $O(m^3)$ search space. Additionally, the Weighted APC (WAPC)* introduces a 3D weighting matrix to account for the fact that different attributes contribute differently to an analogy depending on the classes involved.

Experimental Results

The method was evaluated against eight classical benchmarks from the UCI Machine Learning Repository, including the MONK logic problems and medical datasets like SPECT and Breast-W.

  • Logical Precision: WAPC achieved 100% accuracy on the MONK 2 problem, a synthetic task designed to test complex feature interactions that often defeat simpler classifiers.
  • Robustness: On the Breast-W (96%) and Mushroom (98%) datasets, the analogical approach matched or outperformed complex models like Multi-layer Perceptrons and Logistic Model Trees.
  • Missing Data: The framework treats missing values as a neutral state, allowing it to maintain performance on incomplete datasets more effectively than some decision tree methods.

Conclusion

Analogical classification represents a fundamental shift from proximity-based learning to relational learning. By utilizing training objects that may be distant in feature space but logically related, APC can capture patterns that k-NN misses. While computational complexity remains a challenge for very large datasets, the success of WAPC on logical benchmarks suggests that analogical reasoning is a powerful tool for categorical data analysis.

Summary updated

BibTeX
@inproceedings{bayoudh2007learning,
  author = {Sabri Bayoudh and Laurent Miclet and Arnaud Delhay},
  title = {{Learning by Analogy: A Classification Rule for Binary and Nominal Data}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
}
Figure