PaperlayerView exact revision on arXiv

Source-linked AI summary

Analogical Dissimilarity: Definition, Algorithms and Two Experiments in Machine Learning

Laurent Miclet, Sabri Bayoudh, Arnaud Delhay

arXiv:1401.3427v1cs.LGcs.AI

TL;DR

Analogical proportion among four objects can be ambiguous, and the paper formalizes a measure of how far objects depart from proportion. It defines dissimilarity and algorithms for sequences and learning, reporting benchmark classification findings and handwritten-character generation results. The authors identify further applications and larger problems as work still needed.

  • Problem

    Analogical proportions can be ambiguous, motivating a formal measure of how far four objects depart from being in proportion.

    Source: §1.1 · p. 1, §3.1 · p. 8

  • Method

    The paper defines analogical dissimilarity, gives sequence algorithms including SEQUANA4 and SOLVANA, and develops FADANA for searching low-dissimilarity training triples.

    Source: §3.4 · p. 10, §4.4 · p. 19, §6 · p. 28

  • Results

    WAPC handles missing values, multiclass problems, and noisy data well in several reported benchmarks, while analogy does not fit every classification problem; analogy-based generation also learns effectively from few original handwriting examples.

    Source: §5.1.4 · pp. 24–25, §5.2.3 · p. 27

  • Takeaways & Limitations

    The paper concludes that analogical dissimilarity and its associated lazy-learning technique can extend to more real data, other data structures, and larger problems.

    Source: §6 · p. 29

    The authors call for more experiments and real-world applications, especially for sequences, and note that analogy does not fit all classification problems.

    Source: §3.4.1 · p. 11, §5.1.4 · p. 25, §6 · p. 29

Abstract

from arXiv · show

This paper defines the notion of analogical dissimilarity between four objects, with a special focus on objects structured as sequences. Firstly, it studies the case where the four objects have a null analogical dissimilarity, i.e. are in analogical proportion. Secondly, when one of these objects is unknown, it gives algorithms to compute it. Thirdly, it tackles the problem of defining analogical dissimilarity, which is a measure of how far four objects are from being in analogical proportion. In particular, when objects are sequences, it gives a definition and an algorithm based on an optimal alignment of the four sequences. It gives also learning algorithms, i.e. methods to find the triple of objects in a learning sample which has the least analogical dissimilarity with a given object. Two practical experiments are described: the first is a classification problem on benchmarks of binary and nominal data, the second shows how the generation of sequences by solving analogical equations enables a handwritten character recognition system to rapidly be adapted to a new writer.

1. Introduction

The paper formalizes analogical proportion among four objects, focusing on morphological relations between sequences because analogy can be ambiguous. It develops analogical equations and a dissimilarity measure to support analogy-based learning, then applies these ideas to classification and handwriting recognition.

1.1 Analogical Proportion between Four Elements

  • Analogical proportions can be ambiguous, motivating a focus on formal morphological properties, especially for sequences.The paper also identifies sequence analogies as relevant to linguistic analysis and learning by analogy.Source: §1.1 · pp. 1–2

1.2 Solving Analogical Equations

  • An analogical equation asks for the fourth object that completes a proportion; on sequences, its solution set may be empty or contain valid forms such as “leaves.”The paper notes that designing algorithms for such equations, particularly approximate solutions, is not straightforward.Source: §1.2 · p. 2

1.3 Using Analogical Proportions in Machine Learning

  • Analogy-based learning searches the training set for a triple forming an approximate proportion with a new example, then solves the corresponding equation among their labels.A voting procedure can be used when multiple triples are found.Source: §1.3 · p. 2

1.4 Related Work

  • The paper distinguishes its same-universe formal analogy from cross-domain transfer, and presents analogical dissimilarity and efficient algorithms as its contribution to structured-object learning.Earlier work had studied structured-object proportions, while this paper proposes formal dissimilarity and algorithms for practical machine-learning problems.Source: §1.4 · p. 3

1.5 Organization of the Paper

  • The paper proceeds from proportion definitions and equations through dissimilarity and fast triple search, then reports benchmark classification and handwriting-generation applications.The handwriting experiment uses generated examples to train from few learning patterns.Source: §1.5 · p. 4

2. Analogical Proportions and Equations

The paper defines analogical proportion according to the objects’ domain, with general axioms and domain-specific forms for sets, vectors, and sequences. It also treats solving for an unknown fourth object as an analogical equation.

2.1 The Axioms of Analogical Proportion

  • Analogical proportion is a relation on four objects, with symmetry of “as,” exchange of the means, and determinism as guiding axioms.The first two axioms yield three canonical forms for a proportion.Source: §2.1 · pp. 4–5

2.2 Analogical Equations

  • An analogical equation finds a fourth term that makes the proportion true, and depending on the object domain it can have no, one, or several solutions.The paper defines D as a solution to A : B :: C : x exactly when A : B :: C : D.Source: §2.2 · p. 5

2.3.1 AN ANALOGICAL PROPORTION IN FINITE SETS

  • For finite sets, A : B :: C : D holds when the same elements are added to and removed from A and C to obtain B and D.The paper presents a theorem giving conditions for solvability of set-valued analogical equations, but the supplied passage does not specify those conditions.Source: §2.3.1 · p. 5, §2.3 · p. 5

2.3.3 ANALOGICAL PROPORTIONS IN {0, 1}n

  • Binary objects represent truth-valued features, and each feature of an unknown object can be solved independently from the three known values.Some binary equations have no solution: the paper reports two unsolvable cases among the eight possible assignments on the known objects.Source: §2.3.3 · p. 6

2.4.1 DEFINITION

  • In Rn, four vectors are in analogical proportion when they form a parallelogram, equivalently when their opposite-side vector differences match.Given three vectors, the equation for the fourth has exactly one solution.Source: §2.4.1 · p. 6, §2.4.2 · p. 7, Figure 1 · p. 7

2.5.1 NOTATIONS

  • The sequence framework treats objects as finite strings over an alphabet and adds an empty symbol for alignments.An alignment inserts empty symbols while preserving each sequence’s order, and disallows an all-empty column.Source: §2.5.1 · p. 7, §2.5.2 · pp. 7–8

2.5.2 DEFINITION

  • A four-sequence alignment places the four sequences into equal-length rows using the augmented alphabet, excluding columns empty in all four rows.The definition also requires that each row, after ignoring inserted empty symbols, is semantically equivalent to its original sequence.Source: §2.5.2 · pp. 7–8
  • Sequence proportion is defined through an alignment whose corresponding letters satisfy the analogy in the augmented alphabet.The paper contrasts this with earlier sequence definitions that accept only trivial analogies between letters.Source: §2.5.2 · p. 8

3.1 Motivation

Analogical dissimilarity measures how far four objects are from a true proportion, with zero assigned when analogy holds. The paper seeks properties that support a generalized nearest-neighbor search for triples.

3.1 Motivation

  • Analogical dissimilarity assigns zero when four objects are in analogy and increases as they depart from proportion.It provides a numerical measure of the phrase “almost as.”Source: §3.1 · p. 8
  • The measure is intended to be symmetric, invariant to exchanging the middle terms, and to satisfy a triangle inequality.These properties are presented as requirements for analogical dissimilarity.Source: §3.1 · p. 9
  • Those properties support generalizing fast nearest-neighbor search to find a training-set triple with least dissimilarity when paired with an unknown object.The resulting lazy-learning process generalizes the nearest-neighbor method.Source: §3.1 · p. 9

3.2 A Definition in {0, 1}n

For binary-feature objects, analogical dissimilarity sums feature-level dissimilarities, measuring the changes needed to make four values analogical. The resulting measure is zero exactly for proportions and has symmetry and triangle-inequality properties.

3.2 A Definition in {0, 1}n

  • For four binary values, analogical dissimilarity is the minimum number of bit switches needed to produce an analogical proportion.The paper characterizes it as a four-dimensional extension of edit distance.Source: §3.2 · p. 9
  • For objects described by binary features, total analogical dissimilarity is the sum of the dissimilarities over their features.The paper’s properties include symmetry for “as,” exchange of medians, and asymmetry for “is to.”Source: §3.2 · p. 9, §3.2.1 · p. 9

3.2.1 PROPERTIES

  • AD(u, v, w, x) is zero exactly when u : v :: w : x, and AD satisfies the triangle inequality.The paper states AD(u, v, z, t) ≤ AD(u, v, w, x) + AD(w, x, z, t).Source: §3.2.1 · p. 9

3.3 Analogical Dissimilarity in Rn

In R^n, analogical dissimilarity measures how far four vectors are from forming a parallelogram. Its definition preserves several properties of analogical proportion, including a triangle inequality.

3.3 Analogical Dissimilarity in Rn

  • AD(u, v, w, x) is the p-norm distance between u + x and v + w, and is also the distance from x to the solution of u : v :: w : t.It is zero when the four vectors satisfy u + x = v + w.Source: §3.3 · p. 10
  • The definition guarantees coherence with analogy, symmetry for ‘as’, exchange of medians, triangle inequality, and asymmetry for ‘is to’.The triangle inequality follows from the underlying norm.Source: §3.3 · p. 10
  • AD satisfies AD(u, v, z, t) ≤ AD(u, v, w, x) + AD(w, x, z, t).This inequality follows from the triangle inequality for the norm.Source: §3.3 · p. 10

3.4 Analogical Dissimilarity between Sequences

The paper extends analogical dissimilarity to sequences using an optimal alignment of four sequences. The resulting definition retains key properties of analogical proportion, while the algorithms require no particular alphabet.

3.4 Analogical Dissimilarity between Sequences

  • SEQUANA4 computes dissimilarity between four sequences, while SOLVANA returns all exact solutions to a sequence equation or least-dissimilar sentences when no solution exists.Both algorithms are presented without assumptions specific to the sequence alphabet.Source: §3.4 · pp. 10–11

3.4.1 DEFINITION

  • An alignment’s cost is the sum of the analogical dissimilarities of its aligned 4-tuples of letters, and sequence AD is the minimum cost over alignments.The augmented alphabet includes ∽, with AD(∽, ∽, a, a) = 0 and AD(∽, a, b, c) > 0 for letters a, b, c.Source: §3.4.1 · p. 11, §3.4 · p. 11
  • The sequence definition preserves coherence with analogy, symmetry for ‘as’, exchange of medians, and asymmetry for ‘is to’.Source: §3.4.1 · p. 11

3.5 Computing the Analogical Dissimilarity between Four Sequences: the SEQUANA4 Algorithm

SEQUANA4 computes the analogical dissimilarity of four sequences by finding an optimal alignment with dynamic programming. Its correctness does not require the triangle inequality for sequence dissimilarity.

3.5 Computing the Analogical Dissimilarity between Four Sequences: the SEQUANA4 Algorithm

  • SEQUANA4 uses dynamic programming that progresses through all four sequences in synchrony to build an optimal alignment.Source: §3.5 · p. 11
  • The algorithm takes an augmented alphabet with letter-level dissimilarity as input and returns the dissimilarity between four sequences.The recurrence requires correct progression of the four sequence indices.Source: §3.5 · p. 12
  • SEQUANA4’s correctness requires coherence with analogy, symmetry for ‘as’, and exchange of medians, but not the triangle inequality.For sequence AD, the triangle inequality does not always hold.Source: §3.5 · pp. 11–12

3.6 Generalized Resolution of Analogical Equations in Sequences: the SOLVANA Algorithm

The SOLVANA algorithm finds best approximate solutions to analogical equations on sequences when exact solutions may not exist. It uses dynamic programming to return optimal generated sequences in a DAG, including ties.

3.6.1 APPROXIMATE SOLUTIONS TO AN ANALOGICAL EQUATION

  • Best approximate solutions are the objects closest to being in analogical proportion with the three known objects; the k-best are those with minimal dissimilarity in fourth position.The approach applies to domains, including sequences, for which analogical dissimilarity is defined.Source: §3.6.1 · p. 13

3.6.2 THE SOLVANA ALGORITHM

  • SOLVANA builds a three-dimensional matrix from the three known sequences and uses dynamic programming and backtracking to return all best solutions as a DAG.It stores both costs and candidate letters along optimal paths, with complexity O(m * n^3), where m = Card(Σ′) and n is the maximum sequence length.Source: §3.6.2 · pp. 13–14

3.6.3 EXAMPLE

  • When no exact solution exists for ab : Bc :: Bc : x, six best approximate solutions have AD(ab, Bc, Bc, y) = 4, including BB and Cc.Figure 3 displays the DAG of results for this example.Source: §3.6.3 · p. 14

4. Analogical Dissimilarity and Machine Learning

This section seeks the training-set triple with minimum analogical dissimilarity to a query object, then develops FADANA and a prototype-based variant to search for it.

4.1 Motivation

  • The search assumes an analogical dissimilarity with coherence, symmetry for ‘as’, triangle inequality, exchange of medians, and asymmetry for ‘is to’.Finding the least-dissimilar triple is intended to support supervised machine learning, including classification.Source: §4.1 · pp. 14–15

4.2 The Brute Force Solution

  • Brute-force search checks all triples in S, requiring m³ analogical-dissimilarity calls, reducible by a factor of eight without changing search complexity.This direct search motivates a more efficient algorithm.Source: §4.2 · p. 15

4.3 ‘FADANA’: FAst search of the least Dissimilar ANAlogy

  • FADANA extends AESA to find the triple in S with minimum analogical dissimilarity to y by treating the dissimilarity as a distance between object pairs.The original preliminary computation and storage require O(m⁴).Source: §4.3 · p. 16, §4.3.1 · p. 16

4.3.2 PRINCIPLE OF THE ALGORITHM

  • For each object xi in S, the algorithm searches couples in S against (xi, y), then retains the best triple found across these loops.The couple pool is refilled when xi changes.Source: §4.3.2 · p. 16, §4.3.4 · p. 16

4.3.5 SELECTION

  • FADANA selects the most promising untested couple using the maximum discrepancy between stored and newly computed analogical distances.This criterion selects a candidate relative to the current query pair.Source: §4.3.5 · p. 17

4.3.6 ELIMINATION

  • The elimination step discards couples whose distance bounds show they cannot improve the best dissimilarity found so far.The bound δ is updated during the algorithm and is not reinitialized when the query-side object changes.Source: §4.3.6 · pp. 17–18

4.4 Selection of Base Prototypes in FADANA

  • The improved FADANA variant limits preliminary computation and storage to N·m² using greedily selected base-prototype couples.The first couple is chosen at random; each subsequent one is selected as far as possible from the previous choices.Source: §4.4 · p. 19

4.5 Efficiency of FADANA

  • The optimal number of base prototypes is between 10% and 20% when optimizing computation-time performance.The reported inline analogical-dissimilarity computations are averaged over the test set.Source: §4.5 · p. 19

5. Two Applications in Machine Learning Problems

This application tests analogical dissimilarity for classifying binary and nominal symbolic objects, then develops weighted scoring and evaluates WAPC on UCI benchmarks.

5.1 Classification of Objects Described by Binary and Nominal Features

  • The experiment examines analogical dissimilarity for learning classification rules on symbolic objects, rather than sequences.The comparison uses WAPC, standard classifiers, and APC across eight UCI databases with binary and nominal attributes.Source: §5.1 · p. 19, §5.1.4 · p. 23

5.1.1 METHOD DESCRIPTION

  • The k least-dissimilar 3-tuples whose label analogy has an exact solution vote on the new object's class.The classifier sorts eligible triples by analogical dissimilarity and uses the majority among their class-equation solutions.Source: §5.1.1 · p. 20

Example

  • The example considers five labeled objects and 75 non-equivalent analogical equations, with Table 2 illustrating sorted candidates and classification as k varies.The table displays only the first 14 lines, and its ordering uses an arbitrary analogical dissimilarity.Source: Example · p. 21, Table 2 · p. 21

5.1.2 WEIGHTING THE ATTRIBUTES

  • The analogical weighting matrix assigns attribute weights according to the first class in a proportion and the class obtained as its solution.Its dimensions are attributes × classes × classes; the authors use it to emphasize more discriminative attributes.Source: §5.1.2 · p. 22

5.1.3 LEARNING THE WEIGHTING MATRIX FROM THE TRAINING SAMPLE

  • The training sample estimates each matrix entry from the frequency of attribute-level analogical proportions, and modifying the dissimilarity step yields WAPC.The method estimates probabilities over six possible binary-attribute proportion patterns.Source: §5.1.3 · pp. 22–23

5.1.4 EXPERIMENTS AND RESULTS

  • WAPC handles missing values and multiclass problems well in some benchmarks, but its poor recognition on another database shows analogy does not fit every classification problem.Weighting is effective on some datasets; results for MO. and B.S are identical for WAPC and APC because all AD values computed up to k = 100 are null.Source: §5.1.4 · pp. 24–25, Table 3 · p. 25

5.2 Handwritten Character Recognition: Generation of New Examples

The second application augments small writer-specific samples with synthetic online handwritten characters generated by analogical proportion. Across three classifiers, combined generation strategies reach reference recognition rates with fewer original examples, although analogy alone is less efficient than ad-hoc methods.

5.2.1 INTRODUCTION

  • The goal is quick writer-dependent adaptation with typically only 2 or 3 examples of each character from the new user.The motivation is that acquiring many labeled examples can be expensive or inconvenient, while handwriting style should be retained.Source: §5.2.1 · pp. 25–26

5.2.2 ANALOGY BASED GENERATION

  • The method generates synthetic online-character sequences by analogical proportion from a small set of examples; the illustration generates letter f examples using three instances.The sequences use Freeman symbols augmented with anchorage-point symbols.Source: §5.2.2 · p. 26, Figure 7 · p. 26

5.2.3 EXPERIMENTS

  • Four original characters with complete generation outperform RR10, while RR30 is reached with 9 or 10; the strategies need about three times fewer originals for the same recognition rate.The three classifiers show the same global behavior, and the combined strategies outperform image distortions alone; analogy alone is less efficient than the ad-hoc methods.Source: §5.2.3 · p. 27, Figure 8 · p. 28

6. Conclusions and Future Work

The paper formalizes analogy and analogical dissimilarity between four objects, with sequence analogy defined through optimal alignments and applied to lazy supervised learning. The authors see extension to more real data, other structures, and larger problems as a promising direction, while noting that further work remains.

6. Conclusions and Future Work

  • The paper introduces analogical dissimilarity for measuring how far four objects are from analogy, with sequence analogy defined using optimal alignments.Source: §6 · p. 28
  • For lazy supervised learning, the authors describe improving brute-force search by generalizing a fast nearest-neighbor algorithm and report preliminary experiments.Source: §6 · p. 28
  • The authors identify suitable data and supervision as open questions, noting linguistic applications and ongoing work on phoneme-to-grapheme transcription and interest in biosequences.Source: §6 · p. 29
  • They suggest extending sequence methods to ordered trees and possibly combining sequence models such as HMMs through analogical construction.Source: §6 · p. 29
  • FADANA is a first answer to scaling, but more experiments remain, not all dissimilarity properties have been used, and an O(m) precomputation-and-storage algorithm is still being pursued.Source: §6 · p. 29
  • The authors conclude that analogical dissimilarity and its associated lazy-learning technique may extend to more real data, other data structures, and larger problems.Source: §6 · p. 29
Loading 1401.3427v1…