Behavior of Analogical Inference w.r.t. Boolean Functions

1 Introduction

There have been several proposals for formalizing analogical inference in logical settings [Davies and Russell, 1987; Russell, 1989; Gust et al., 2006]. More recently, a propositional logic modeling of analogical proportions has been developed [Miclet and Prade, 2009; Prade and Richard, 2013]. This latter view is at the basis of a successful classification method for which empirical evidence was provided in classification problems [Miclet et al., 2008; Bounhas et al., 2017].

Analogical proportions are statements of the form "a is to b as c is d", usually denoted a : b :: c : d. Such a proportion expresses that the ways a and b differ are the same as the ways c and d differ. In this paper, one should think of a, b, c and d as being represented by tuples of m Boolean feature values, i.e., as elements of the m-dimensional Boolean space Bm = {0, 1}m. How does analogy-based inference work?

Let f be a Boolean function from Bm to B and x ∈ Bm such that f(x) is unknown (f(x) can be viewed as a class label). The inference amounts to say that if there exist three items a, b, c with known labels such that a : b :: c : x holds, then f(x) may be the solution (if any) of the analogical proportion f(a) : f(b) :: f(c) : f(x) [Stroppa and Yvon, 2005].

The notion of analogical proportion and the associated inference mechanism may appear a bit uncommon at first glance. First, as far as we know, the relationship between analogical proportion and Hamming distance has never been investigated despite the fact that the latter is a key notion for appreciating differences in a Boolean framework. Second, analogical proportion seems a quite sophisticated relation between 4 items and one may wonder whether it occurs rarely in practice.

In this paper, we shed some light into these concerns. Another important issue is to understand why it works in practice. Beyond the general good reputation of analogy, no explanation for its good results has been provided until now, with the exception of the recent contribution [Couceiro et al., 2017] where a remarkable behavior w.r.t. affine Boolean functions is established. Namely, given a sample S of elements where a function f is known, it is shown that we can guess with certainty the value of f(x) for x /∈ S for some classes of functions f, using analogical inference. The key result is that analogical inference does not make any error iff f is an affine Boolean function. Nevertheless, no theoretical or experimental results were provided regarding the possible link between the accuracy of the inference process and the distance between the target labeling function f and the set of affine functions. Here, we address the latter concern.

The paper is organized as follows. Section 2 gives the necessary background on two models (M and K) of Boolean analogical proportions. In Section 3, we link analogical proportions with Hamming distance. We show that, in general, it is possible to find non trivial intermediary items b and c given any a and d such that a : b :: c : d holds. Section 4 surveys Boolean functions and their algebraic normal forms. In Section 5, we compare the class of model-preserving functions, based on M and K definitions, and show that both coincide with affine functions. In Section 6, we consider the case where the target function is not affine, and show that if a function is ε-close to an affine function, then the probability of making wrong predictions based on analogical inference is upper bounded linearly w.r.t. ε.

2 Analogical Proportions

An analogy A (or analogical proportion 1 ) over a nonempty set X is a quaternary relation over X that satisfies four axioms [Miclet et al., 2008] (all formulas are universally quantified):

1. Reflexivity: A(a, b, a, b).

1 In the paper, the term analogy is short for analogical proportion

1. Symmetry: A(a, b, c, d) =⇒ A(c, d, a, b).
2. Central permutation: A(a, b, c, d) =⇒ A(a, c, b, d).
3. Unicity: A(a, b, a, x) =⇒ x = b.

In this paper, we restrict the interpretation domain X to be the Boolean set B = {0, 1} and A(a, b, c, d) will be denoted a : b :: c : d. It leads to 2 remarkable Boolean models:

The K model was proposed, although very informally, by the American researcher S. Klein [Klein, 1982] more than 25 years before the introduction of the Boolean modeling of analogical proportion. It obeys the 4 postulates of analogical proportion but it has what may be considered as an undesirable behavior: 'a is to b as c is to d' is the same as 'b is to a as c is to d'. Still it is of interest to keep it for comparison with genuine analogical proportion. It is noteworthy that K is such that any added element of B4 would contradict unicity.

M is the smallest Boolean model obeying the 4 axioms above. We denote by a : b :: c : d an analogical proportion w.r.t. M. It can be defined by the logical expression:

where ∧, ¬,↔ are respectively the logical connectives for conjunction, negation and equivalence. It expresses the fact that a differs from b as c differs from d (and vice-versa: b differs from a as d from c). Considering B as a subset of R, another equivalent formulation is given by:

a : b :: c : d if and only if a- b = c -d.

Note however that the latter reformulation is not suitable in the Boolean setting since a - b may not belong to B when a, b ∈ B. It can be checked that M (and K) satisfies the code independence property:

which guarantees that 0 and 1 play symmetric roles in the encoding of the Boolean features. An M-analogy over Bm is defined componentwise, i.e., ∀a, b, c, d ∈ Bm,

When an analogy is defined over a set X, given 3 elements a, b, c of X, the requirement that the relation A(a, b, c, x) holds defines an equation where x is the unknown. In the Boolean case, with M or K as models, there is at most one solution. When equation a : b :: c : x is solvable, we abbreviate it with solvable(a, b, c). In this case, sol(a, b, c) denotes the solution. K-analogies extend to Bm as well, and they are always solvable.

Throughout this paper, we will adopt model M.

3 ANewView on Analogies

We first show that an analogy is valid only if certain constraints (in terms of Hamming distances) on their 4 items hold. Then we highlight that analogies emerge as soon as 2 items are compared. We focus on M-analogies here.

3.1 Links with the Hamming Distance

A standard distance over Bm is the Hamming distance: Hm(x, y) = |{i ∈ [1,m] : xi ̸= yi}|, which satisfies:

where x/m denotes the projection of x over Bm. We write H when there is no ambiguity about the dimension. A first link between Boolean analogy and Hamming distance is given by:

Proof: We prove the first equality H(a, b) = H(c, d) by induction on m. Clearly, it holds for m = 1. By definition of analogy on Bm+1 , given a, b, c, d ∈ Bm+1 , a : b :: c : d iff

The induction hypothesis leads to H(a/m, b/m) = H(c/m, d/m) and H(am+1, bm+1) = H(cm+1, dm+1). Adding these two equations leads to the expected result. The same reasoning applies to the two remaining equalities. □

However the reverse property does not hold for 0 : 1 :: 1 : 0 and for 1 : 0 :: 0 : 1. A stronger relation can be established:

Property 2 ∀a, b, c, d, such that a : b :: c : d, we have

Similarly, we have H(d, c) + H(d, b) = H(d, a).

Proof: The first equality is easily proved by induction on m. It is true for m = 1. Since we have a : b :: c : d iff :

we can apply the induction hypothesis to get H(a/m, b/m) + H(a/m, c/m) = H(a/m, d/m) and H(am+1, bm+1) + H(am+1, cm+1) = H(am+1, dm+1). And we are done by adding these two equations. The second equality is deduced from the first one using Property 1. □

As Prop. 2 rules out 0 : 1 :: 1 : 0 and 1 : 0 :: 0 : 1, we may wonder if it characterizes analogy.

Property 3 When m = 1, H(a, b)+H(a, c) = H(a, d) (or H(d, c) +H(d, b) = H(d, a)) implies a : b :: c : d.

Proof: If H(a, d) = 0, then H(a, b) = H(a, c) = 0 and a = b = c = d. If H(a, d) = 1, then either H(a, b) = 0 or H(a, b) = 1. In the first case, a = b and H(a, c) = 1, i.e. c = d since m = 1 and variables can only take values 0 or 1. Similarly if H(a, b) = 1, b = d and H(a, c) = 0, i.e. a = c. The other relation follows by permutation. □

When m > 1, H(a, b)+H(a, c) = H(a, d) is not enough to ensure a : b :: c : d as we can see by taking a = 000, b = 100, c = 110, d = 111. Indeed ai : bi :: ci : di holds only for i = 2, and not for i = 1 or 3, while both H(a, b) + H(a, c) = H(a, d) and H(d, c)+H(d, b) = H(d, a) hold. So, we should require that the relation holds componentwise for characterizing analogy:

Property 4 ∀a, b, c, d ∈ Bm, a : b :: c : d if and only if ∀k = 1, . . . , m, H(ak, bk) + H(ak, ck) = H(ak, dk).

If we consider Bm as a subset of Rm, a : b :: c : d means that the 4 vectors are the vertices of a parallelogram. Note that this parallelogram can be flat (a : b :: a : b), or even reduce to a single vertex (a : a :: a : a). With this interpretation, it is quite clear that given 3 vectors a, b, c ∈ Bm, it is not always possible to find a fourth vector d ∈ Bm such that a : b :: c : d (although this 4th vector always exists in Rm).

3.2 Analogy and Comparison of Two Items

Analogy is implicitly present when we compare two objects. Indeed, for any two distinct objects represented as Boolean vectors a and d, there is a way to fill in the gap between them in a "smooth" way. More precisely, it is possible to find two other vectors b and c such that a : b :: c : d. To formalize this idea, let Agr(a, d) be the set of indices where a and d agree and Dis(a, d) the set of indices where the two vectors differ. Then we have the following easy-to-check result.

Property 5 Let a, d ∈ Bm and take b, c ∈ Bm such that:

1. ∀i∈Agr(a, d), ai=bi=ci=di
2. ∀i∈Dis(a, d), either (bi=ai and ci=di) or (bi=¬ai and ci=¬di).

Then a : b :: c : d. Moreover if |Dis(a, d)| ≥ 2, then we can find a, b, c, d that are pairwise distinct.

Example: Let a = 01100 and d = 00111 in B5 . Then Agr(a, d) = {1, 3} and Dis(a, d) = {2, 4, 5}. By 1., we have b = 0b21b4b5 and c = 0c21c4c5, while 2. gives us more freedom, for instance, b = 01110 and c = 00101 are solutions. Indeed, 01100 : 01110 :: 00101 : 00111. We can check that H(a, b) = H(c, d) = 1, H(a, c) = H(b, d) = 2, while H(a, d) = H(b, c) = 3 = |Dis(a, d)|.

Analogy allows us to compare a to d via some transitional steps involving intermediary values b to c, which are closer to a (or to d) than a is to d. In a visual context, analogies were recently used for expressing constraints in multi-class categorization tasks and attribute transfer [Hwang et al., 2013; Jing et al., 2017]. The latter reference illustrates the creation of "intermediate" images b and c building an analogy with two given images a and d (in an approximative way).

4 Boolean Functions: Brief Overview

We now survey some useful results on Boolean functions.

4.1 B as a Field and Bm as a Vector Space

When it comes to represent a Boolean function, an algebraic view may be more relevant than sticking to the standard logical operators. In that case, multiplication in B is the usual one (corresponding to conjunction), but addition is addition modulo 2 (still denoted + and corresponding to XOR), making B a 2-element field such that x + x = 0. In this way, Bm becomes a vector space over the 2-element field B: scalar multiplication distributes componentwise and addition of vectors is likewise defined componentwise as addition modulo 2. The Hamming weight wt(x) is |{xi|xi = 1}| so that the Hamming distance H(x, y) is just wt(x + y). By endowing B with the total order 0 < 1, Bm becomes totally ordered via the lexicographic order. It is sometimes useful to represent a Boolean function f ∈ Fm by the unique vector of B2m of its values: wt(f) is the number of vectors x such that f(x) = 1. A linear form over Bm is a Boolean function g ∈ Fm such that for every x, y ∈ Bm and α ∈ B we have

Note that the second equality reduces to g(0) = 0 in this case. The set of linear forms over Bm is usually denoted (Bm)∗ and called the dual space of Bm. This is also a vector space over B. Bm is naturally equipped with a dot product given by

This dot product induces the following well known properties

• Bm and (Bm)∗ are isomorphic.
• x ↦→ gx where gx(y) =< x, y > is an isomorphism.

Analogy over B (thought of as a field) can then be defined by:

Extension to Bm is made componentwise. These definitions are strictly equivalent to the ones given in Section 2. We have to note that a : b :: c : d implies d = a + b + c and, with the notations of Section 2, if solvable(a, b, c) then sol(a, b, c) = a + b + c. This is also true with vectors in Bm. The reverse property does not hold as can be seen with 0110 which is not an analogy but where the last element is still the sum of the 3 first elements.

4.2 Polynomial Representation of Boolean Functions

A monomial is a term of the form xI ≜ ∏ i∈Ixi, for some (possibly empty) finite set of positive integers I with the convention that 1 is the empty monomial x∅. The size | I | is called the degree of xIdenoted d(xI). A polynomial is a sum of monomials ∑I⊆{1,...,m} ωI · xI where each ωI belongs to B (addition is understood as addition modulo 2). Equipped with scalar multiplication over B and addition, the set B[x1, . . . , xm] of polynomials is a ring over B. The degree of a polynomial is the largest degree of its monomials. The monomial 0 is just 0 · x∅. Note that 0 and 1 are the only monomials of degree 0. A projection (corresponding to the selection of one feature) is obviously reduced to a monomial of degree 1.

Each Boolean function f ∈ Fm is uniquely represented by a polynomial called ANF for Algebraic Normal Form [Stone, 1936; Zhegalkin, 1927] i.e.,

The degree d(f) of a Boolean function f is the degree of its ANF. With no danger of ambiguity, we confuse f with its ANF. The negation of a function f is just f + 1. When d(f) ≤ 1, we say that f is affine. In other words, a function f ∈ Fm is affine iff

where ω = (ω1, . . . , ωm). The set of affine functions of arity m is denoted by Lm, so that L = ⋃m Lm is the set of all affine functions. If the term ω0 is 0, the affine function is just a linear form. Thus, affine functions are either linear forms (including the constant function 0) or their complements.

5 Analogy and Affine Functions

5.1 Predicting by Analogy

For m ≥ 1, let Fm = F(Bm, B), denote the set of all Boolean functions of arity m, and let F = ⋃m∈N Fm, i.e., the set of all Boolean functions. Given a sample set S ⊆ Bm and a function f ∈ Fm, the analogical root of a given element x ∈ Bm, denoted by RS(x, f), can be defined as follows [Hug et al., 2016]:

Definition 1 For f ∈ Fm, define RS(x, f) to be the set

In other words, RS(x, f) is the set of triples over S that are analogically linked to x or, equivalently, the set of vertices a, b, c ∈ S3 such that (a, b, c, x) is a parallelogram in the Boolean cube Bm. The set RS(x, f) can be used to provide a prediction for the label f(x) of x using analogical inference. For any element x ∈ Bm \ S such that RS(x, f) ̸= ∅, the analogical label of x is defined as follows:

Definition 2

where Mode(Σ) returns the most frequent element of a multiset Σ (i.e. xS,f is the most common label among all candidate labels). In case of a tie, the returned element is randomly chosen among the most frequent elements. It is clear that, for these elements, we do not necessarily have xS,f = f(x).

Definition 3 A function f ∈ Fm is said to be analogy preserving (AP ) if for every x ∈ Bm\S such that RS(x, f ) ̸= ∅, we have xS,f = f(x).

Note that, thanks to code independency property, f is AP iff ¬f is AP . Proposition 1, which has been proved in [Couceiro et al., 2017], gives an alternative description of AP functions.

Proposition 1 A function f : Bm → B is AP if and only if for every a, b, c, d ∈ Bm, the following implication holds:

Analogical prediction may look quite similar, at least in principle, to a k-NN technique where a final vote among k candidates is performed. Nevertheless, we can ensure the accuracy of the prediction: this is not the case with k-NN algorithms.

5.2 FromAP Functions to KP Functions

In this section we recall the explicit description (Proposition 3 below) of the class of AP functions, which was recently presented in [Couceiro et al., 2017] by making use of tools in clone theory [Denecke and Wismath, 2002; Lau, 2006]. The intuition comes from the following result in [Szendrei, 1980].

Proposition 2 A function f ∈ Fm is affine if and only if for every a, b, c ∈ Bm, we have

Inspired by the latter result, the following explicit description of AP functions has been obtained:

Proposition 3 A function f is AP if and only if it is affine.

This result provides a clear picture of what can be expected from a prediction outside a given Boolean sample: only affine functions can ensure sound predictions. If the number of Boolean functions of arity m is 22m , the number of affine functions of arity m is just 2m+1 . This shows that affine functions constitute a rather small subclass of functions in this landscape. This fact asks for an extension of our results to non affine functions.

In fact, everything which has been done in the previous sections, based on the smallest model M of analogy, can be done with the model K. Let us denote K(a, b, c, d) the fact that a, b, c, d belong to model K. Obviously

and the main difference with analogy is that every triple in Bm is uniquely K-solvable i.e.,

In fact, d = a + b + c is the unique solution of the equation K(a, b, c, x). The definitions we have used for defining AP functions still apply and lead to the following definition for an KP (for K-preserving) function:

Definition 4 f is KP if and only if ∀a, b, c, d ∈ Bm:

Using Proposition 2, we get the following result:

Proposition 4 The class of KP functions is the class of affine functions.

Proof: Observe that K(a, b, c, d) means d = a+b+c, and thus if f is KP, then f(a + b + c) = f(a) + f(b) + f(c) by (1). It then follows from Proposition 2 that f is affine. □

So considering analogical inference, using model M or K does not make any difference w.r.t. preserving functions.

6 Approximately Affine Functions

Applying analogical inference without caution may lead to incorrect labelling of instances x /∈ S: if f is not AP , we may have xS,f ̸= f(x) for some x. It is natural to ask whether the use of analogical inference to approximately affine functions can ensure labels which are also approximately correct. Let us formalize what we mean by "approximation".

6.1 The Meaning of Approximately Affine

The word approximation is understood in various ways within the Boolean algebra community. In this paper we will take a probabilistic approach. Given two functions f, g ∈ Fm, the Hamming distance H(f, g) between f and g is just wt(f +g) when f and g are represented as vectors (see Section 4.1). In other words,

Let P denote the uniform distribution 2 over Bm. Then P (x ∈ dis(f, g)) = H(f,g) 2m is a distance over the set Fm of all Boolean functions, and we will denote it by d(f, g).

2 Using the uniform probability will allow to use relative frequencies as probability approximation.

Now, we say that a function g approximates f at level ε or that it is ε-close to f if d(f, g) ≤ ε. This can also be read as "the proportion of x ∈ Bm such that f(x) ̸= g(x) does not exceed ε". Given a set C ⊆ Fm, d(f, C) is defined as usual as ming∈Cd(f, g). Obviously, when it comes to computing the distance d(f,L) of f to the set L of affine functions, we are sure that d(f,L) ≤ 12 . Indeed, if there is an affine function g such that d(f, g) > 1 2 , then g + 1 is still affine and d(f, g + 1) < 12 , by definition.

Definition 5 A function f is ε-close to C if d(f, C) ≤ ε. If f is ε-close to the set L of affine functions for a threshold ε, then f is said ε-approximately affine (necessarily ε ∈ [0, 1 2 ]).

As we will see, this notion of ε-closeness allow us to assess the quality of the analogical inference.

6.2 Sound Analogical Inference

In this section, we mainly recall concepts introduced in [Couceiro et al., 2017]. Given a subset S ⊆ Bm, a function f ∈ Fm, and an element x ∈ Bm, if RS(x, f) ̸= ∅, then an analogical label xS,f can be associated to x. Let us then define the analogical extension ES(f) of S w.r.t. f as the set of x ∈ Bm such that RS(x, f) ̸= ∅. Formally:

Intuitively, ES(f) can be seen as the set of all x ∈ Bm that are the fourth vertex of a parallelogram built with 3 vertices from the sample set S, provided that the equation related to the associated labels is solvable. It is clear that S ⊆ ES(f) because a : a :: a : a always holds. Define

Hence, we are interested in the elements x ∈ ES(f) \ S whose predicted label xS,f is f(x).

Definition 7 We say that ES(f) is sound if errS,f = 0.

Due to the definition of the probability P, errS,f = 0 means the proportion of wrong analogical labels is zero. In this case, ES(f) can be used as an extended sample set for classification tasks. In the opposite case, ES(f) is said to be unsound (i.e. noisy) which is equivalent to errS,f > 0. Thus Proposition 1 can then be restated as follows:

Proposition 5 A function f ∈ Fm is AP if and only if for every S ⊆ Bm, ES(f) is sound.

6.3 Approximately Sound Extension

By Proposition 5, if f is not affine (and thus not AP), then there exists a sample S such that ES(f) is unsound. It means that 3 P(errS,f > 0) > 0 where P relates to the probability over all possible choices of the sample S.

This probability provides a measure of the imperfection of f w.r.t. analogical inference. Given a function f ε-close to L, can we determine an upper bound of this probability? The following proposition gives a positive answer.

3 From a rigorous viewpoint, we should denote P ′ (errS,f > 0) where P is the probability distribution over the universe Bm, and P ′ is the induced distribution over the powerset 2Bm . In our case, errS,f > 0 simply means {x ∈ ES(f) : |x ̸= f(x)} ̸= ∅.

Proposition 6 Let ε ∈ [0, 12 ]. If f is ε-approximately affine, then P (errS,f > 0) ≤ 4ε.

Proof: Let be f ε-close to L and g ∈ L such that

Given a sample set S, an element x ∈ ES(f) \ S, the occurrence of xS,f ̸= f(x) implies that there are a, b, c ∈ S:

This implies that there are a, b, c ∈ Bm such that

Now, for the sake of contradiction, suppose that

In this case, solvable(g(a), g(b), g(c)), and thus sol(g(a), g(b), g(c)) = g(x) since g is affine. Furthermore, f(x) = g(x) implies that

which yields the desired contradiction. As a consenquence, one of the following conditions must hold:

But the probability of this event is upper bounded by

Hence, the occurrence of the event (ES(f) is unsound) is upper bounded by 4ε, which completes the proof. □

This result tells us that if we can upper bound the distance between f and L by a small ε, then the probability that no noise will be introduced by using ES(f) instead of S in our classifier 4 , will be at least 1 - 4ε.

From a practical point of view, testing that a function is approximately linear (i.e. affine where the final constant in its ANF is 0) can be checked via a simple test due to Blum, Luby, and Rubinfeld [Blum et al., 1993] also known as BLR test. It can be proved that if BLR test accepts f with a probability at least 1 - 4ε, then f is ε-close to L. The test can be performed with O( 1ε ) queries. See [Kaufman et al., 2008] for a comprehensive analysis of the test.

4 The factor 4 has no link with the VC-dim of an analogical classifier, which is infinite [Hug et al., 2016]. This multiplicative scalar is due to the fact that analogical proportion involves 4 items.

6.4 Relaxing the Bounds

Our definition of approximately sound extension is a rather strict. For a sample S, having a probability errS,f strictly positive does not mean that the classifier will performs modestly starting from S. For instance, starting with any S, if this probability is in ]0, 0.001], then the probability of having P(errS,f) > 0 is 1 despite the algorithm being highly satisfactory. This fact asks for a relaxation of our definition. A bad performance would be more accurately described by errS,f > δ, for some δ ∈ [0, 1[.

Definition 8 We say that ES(f) is δ-sound if errS,f ≤ δ. Similarly, f is δ-sound if ∀S ⊂ Bm, ES(f) is δ-sound 5 .

If f is δ-sound (for a small δ), then we can consider the analogical inference principle as a valuable inference principle for f since the error rate is quite low. With this view, we are interested in the probability of f not being δ-sound, which then becomes: ηf(δ) = P(errS,f > δ). In the case when δ = 0 and f is ε-approximately affine, we have that ηf (0) ≤ 4ε. In fact, we can prove the following:

Proposition 7 Let ε ∈ [0, 12 ], δ ∈ [0, 1]. If f is εapproximately affine, then P(errS,f > δ) ≤ 4ε · (1 - δ).

Proof: Given a sample set S and x ∈ ES(f) \ S, it follows from Prop. 6 that P(xS,f ̸= f(x)) ≤ 4ε. For errS,f > δ to occur, such an x should lie outside an area of radius δ and the probability of picking such an x is 1 - δ. Obviously if δ = 1, then ∀f, P(errS,f > 1) = 0 since ∀S, errS,f ≤ 1. □

6.5 Experiments

In order to investigate whether the bounds in Propositions 6 and 7 are tight, we implemented the following protocol.

For X = B8 , we started from 3 affine functions:

1. g1(x) = x1 which is the first projection.
2. g2(x) = x1+x2 (all variables but x1, x2 are irrelevant)
3. g3(x) = Σmi=1xi where all variables are relevant.

To get an ε-close function, we just flip a random fraction ε of the values of gi on the universe X. Doing so, we are sure to get a function fi,ε such that d(fi,ε, gi) ≤ ε and then d(fi,ε, L) ≤ ε. There is no need to go beyond 0.5 since

where g + 1 ∈ L if g ∈ L.

For each approximately affine function fi,ε, we performed 100 experiments with a random S of size |X| 2 = 27 :

1. For each S, we estimated the probability errS,fi,ε by

i.e., the proportion of elements x in ES(fi,ε) \ S whose analogical predicted label is not equal to fi,ε(x).

1. The probability of interest ηfi,ε(δ) = P(errS,fi,ε >δ) is taken as the proportion of errors over the 100 experiments.

5 Note that f is 0-sound iff f is AP.

In figures 1, 2 and 3, we provide η(δ) as a function of ε for δ = 0, 0.3, 0.5 respectively. The upper theoretical bound 4ε · (1 - δ) from Proposition 7 is shown as a dashed line. We observe that for all approximately affine functions f1, f2, f3, the computed probability remains below the theoretical bound. Figures 1 and 2 show that the bounds are tight.

To give an idea of the behavior of 1-NN in the same context, we show (Fig. 4) a comparison between the evolution of ω = 1 - err and the proportion τ of properly classified elements in ES(fi,ε) \ S by 1-NN wrt ε. As expected, 1-NN becomes better when we move away from affine functions, i.e., the opposite behavior to analogy-based classifier.

7 Conclusion

Analogical inference allows to predict the exact labels of elements outside a given sample set S, provided that the labelling function f is affine. In the case when f is only approximately affine, we provided a probability of null error: it is less than 4 times the distance between the target function f and the set L of affine functions. As this distance can be evaluated via the BLR test, we have a way to upper bound the error associated with any Boolean function. Our experiments agree with this upper bound, and indicate that the bound may be tight. When relaxing the error requirement to a non null error bounded by δ, we get another theoretical upper bound.

We note that the upper bound does not rely on the size of S, just because the external probability P is considered over the whole set of potential samples S. Introducing the size of S as a parameter could further refine this upper bound.

These results provide clues suggesting why (and when) analogical inference gives good prediction results. Still, there exist known cases of functions f that are far from being affine, but for which the analogical inference works well [Bayoudh et al., 2007]. This is yet to be explained.

Also, in real life applications, we rarely deal with purely Boolean datasets: often they mix Boolean with symbolic attributes taking values in finite sets. A typical example of such an attribute is color. Obviously, on the set of values of color, there is no structure, no order and no known operator. Binarizing the attribute values, leads us to considering partial Boolean functions, which is a topic of ongoing research.

Acknowledgements

This work is partially supported by ANR-11-LABX0040-CIMI (Centre International de Math´ematiques et d'Informatique) within the program ANR-11-IDEX-000202, project ISIPA.