Analogies are 4-ary relations of the form “A is to B as C is to D". While focus has been mostly on how to solve an analogy, i.e. how to find correct values of D given A, B and C, less attention has been drawn on whether solving such an analogy was actually feasible. In this paper, we propose a quantification of the transferability of a source case (A and B) to solve a target problem C. This quantification is based on a complexity minimization principle which has been demonstrated to be eficient for solving analogies. We illustrate these notions on morphological analogies and show its connections with machine learning, and in particular with Unsupervised Domain Adaptation.
Analogies are 4-ary relations of the form “ is to as is to ", denoted : :: : . Even
though humans demonstrate strong capabilities of understanding and generating analogies,
which has been intensively studied by cognitive sciences [
In most cases, the aforementioned methods are designed to provide an answer to any equation
: :: : , regardless of whether the equation makes sense. This is not the case for humans,
who consider that some analogies make more sense than others. Consider for instance the
domain of Hofstadter analogies [
Which analogical equations are indeed solvable, is a rather infrequently discussed question.
However, it would have strong implications, be it in practical applications of analogies (e.g.
in intelligent tutoring systems [
). To do so, we propose a very general formalization
of the problem, which is shown to apply to transfer in both symbolic tasks (like morphological
analogies) and numerical machine learning. Based on this formalization, and getting inspiration
from applications of Kolmogorov complexity in inference [
of Mℛ , . and 5.
Although various definitions of analogy have been proposed in the literature, we consider in
this paper the following definitions, inspired by the recent framework of Antic [
(the problem space) and (the solution space). An element (, ) ∈ will be referred to as a case.
called representation space. A model space Mℛ , of domain based on representation ℛ is defined as a subset mapping a problem ∈ , a solution ∈
Mℛ , ⊆ { : × × ℛ →
[
is called a model of . When the context is clear, we will use the notation M instead We illustrate these notions with two examples that will be further investigated in Sections 4 or conjugation of a verb in natural language): therefore, it is given by = * × *.
Example 1 (Recursive model for morphology). Given an alphabet , we define by * the set of words of . The morphological domain consists of two forms of a word (e.g. declension of a word
We define the representation space ℛ functions 1 from ℛ to . For all ∈ ℱ , we define = ⋃︀ =1( *) . Let ℱ ∞
be the space of all recursive : * × * × ℛ → { 0, 1} as: We can then define the model space
Mℛ , as: (, , ) = ︃{ 1 if ( ) = (, ) 0
otherwise Mℛ , = { | ∈ ℱ } (1) (2)
This example has an easy interpretation. The morphological domain consists of two words 1 and 2, which are typically two flections of a same word. For instance, the tuple “play : played" describes the flection of the English verb “play" from the present tense to the perfect tense. Similarly, the tuple “taloon : talossa" describes the flection of the Finnish noun “talo" from the illative case to the inessive case. 1i.e. functions computable by a Turing machine. See Section 2.2.
For a better readability, we decompose the recursive function ∈ ℱ as ( ) = ( 1( ), 2( )). The function 1 (resp. 2) describes how the word 1 (resp. 2) is formed based on some representation . For instance, in the “play : played" example, we can have 1( ) = , 2( ) = + “ed" (where the + operation is the string concatenation), and both functions are instantiated with = “play".
Example 2 (Probabilistic models on R ). We define the binary domain = × with problem space = (R )* and solution space = ℒ *, for some space ℒ of labels. When ℒ is discrete, the problem is called classification , otherwise regression. An observation on domain consists of one labelled dataset, where the problem is the unlabeled dataset (points in R ) and the labels (in ℒ ).
Let be a set Θ = { : × → [
In this paper, we assume that all considered quantities are computable. For those which are not computable (for instance domains of real numbers used in Example 1), we will introduce relevant computable approximations.
Our framework relies on the use of Kolmogorov complexity [
A function : B* → B* is called partial recursive if its output ( ) corresponds to the output of a given Turing machine after its execution with input when it halts (otherwise, we use the convention ( ) = ∞). With this notation, the function can be improperly likened to a Turing machine. In this case, the input is called a program. A partial recursive function is called prefix if, for all , ∈ B*, if ( ) < ∞ and ( ) < ∞, then is not a proper prefix of .
Complexity ( ) of a string ∈ B*, relative to a partial recursive prefix (p.r.p.) function , is defined as the length of the shortest string such that ( ) = : ( ) = m∈iBn*{ ( ) : ( ) = } (3) where ( ) represents the length of the string .
A key result of the theory of complexity is the existence of an additively optimal p.r.p. function 0: for any p.r.p. function , there exists a constant such that for all ∈ B*, 0 ( ) ≤ ( ) + . These additively optimal p.r.p. functions are used to define Kolmogorov complexity. They present in particular invariance properties, which means that the diference between the complexities defined by two distinct universal p.r.p. functions is bounded. However, it can be shown that Kolmogorov complexity is not computable, and thus cannot be used in practice.
In practice, this limitation is overcome by fixing a reference p.r.p. function which is not optimal but leads to a computable complexity. By definition, this non-optimal complexity is an upper-bound of Kolmogorov complexity (up to an additive constant). This choice of a reference function is particularly restrictive and imposes some biases, which is inherent to any inductive problem. In the following, we will refer to this upper-bound either as complexity or as description length.
describes the observation. standard inference task of supervised learning is to select a model Consider a domain = × and an observation (, ) ∈ . Given a model space M , the which optimally ∈ M
Selecting a model which accurately describes the observation is not enough in general: In
most situations there exists multiple such models, and sometimes even infinitely-many. It is
then necessary to discriminate among all these models, in particular based on the intended use
of the model. In statistical learning for instance, the discrimination is done by both the selection
of a simple model family and a penalization of models [
The inference of the model describing an observed case can then be split into two aspects:
selection of a model accurately describing the case and penalization over the model space. This
idea has been formalized by Algorithmic Information Theory using Kolmogorov complexity. The
Minimum Message Length (MML) [
We remind the computation of complexity is relative to a choice of a reference Turing machine.
Therefore, this choice imposes a strong bias over the intended outcome. A refined
version of
the MDL principle has been proposed, which overcomes this limitation. This version is beyond
the scope of this paper, but we refer the interested reader to (Grünwald, 2007) [
Analogies involve two separate domains: a source domain and a target domain . Given a source problem-solution pair ( , ) ∈ transfer from ( , ) to is informally defined as finding and a target problem ∈
, the analogical
such that the
transformation
↦→ is “similar" to the transformation
↦→ . This notion of similarity is
problematic, especially when the source and target domains are distinct. Existing frameworks
of analogy often assume that the source and target domains are the same [
In this section, we show how complexity can be used to properly define this similarity, even in the case of distinct domains. We will then show that this definition helps quantifying the notion of transferability, i.e. how the source observation ( , ) is useful to find a solution to target problem . 3.1. Inference of a Target Model
maximizing the score ( , , ): problem ∈
∈ and ∈ ℛ The task in the target domain consists in predicting the solution associated to the ∈ . Usually, this is done throughout a model , in particular by finding * ∈ arg max
︂{ ∈ ∈ℛ max ( , , ) ︂} (5) The solution is then estimated by taking corresponds to taking the most probable solution.
In the context of Example 1, this corresponds to choosing a representation that successfully describes given the recursive function associated to , i.e. finding such that 1( ) = .
= 2( ). In the context of Example 2, Equation (5) However, in practice, the model
is not known and needs to be inferred. The dificulty is that, in general, it is not possible to identify
given only. Even worse, there is no guarantee that two models correctly describing can yield the same values of . For instance, in the morphological domain (Example 1), one can build degenerate functions such that ( ) = for all . All such functions successfully describe and yield all possible values for .
The MML principle presented in Equation 5 is meant to be used in a single domain, in particular the source domain. We propose to use it as well to estimate the target model . However, in the context of an analogy, some additional information is provided by the observation of the target model can then be described with regards to the source model . source domain, where a model can be evaluated from observations ( , ) ∈ . The
The limitation of such a relative description of models is that the source model may not be relevant. In the following, we propose to quantify this relevance with two measures of model reusability,
We measure the reusability of a source model to its ability to compress the information about the target domain. We identify two main possible definitions, that we call weak and strong reusability, and will show that a strongly reusable model is necessarily weakly reusable.
The main criterion for weak reusability is that knowing the source model makes the target inference better, in the sense that it compresses more the description of the target case ( , ) ∈
Definition 1 (Weak reusability). Let > 0. A model for case ( , ) in target model space Mℛ , if:
min
∈ Mℛ , is called weakly -reusable ≥ +
min ( | ) + ( , | ) } (6)
It is essential to keep in mind that this definition is relative to the choice of a model space Mℛ , for the target domain. A source model may not be reusable for a case ( , ) depending on the chosen target model space. In the following, we will abusively omit to mention the target model space, for readability purposes.
Note that the models
defined in the left-hand side and in the right-hand side of inequality (6) are not the same. On the left-hand-side, the model corresponds to the optimal target model describing ( , ) while, on the right-hand-side, it is the optimal model describing ( , ) when is known.
|
This notion of reusability means that providing the source model helps finding a new description of the problem shorter than the optimal description by bits. In particular, in the case where Mℛ , = Mℛ , , the optimal model for ( , ) (i.e. the model that minimizes ( ) + ( ,
)) is trivially weakly reusable for ( , ) for all . In other words, when the optimal model for the source domain is also optimal for the target domain, then it is obviously reusable for the target domain. The interesting case will be when the optimal source model is not optimal for the target domain.
We notice that the definition does not require = and aims to quantify the reusability of a model even for a completely diferent task. This is possible since complexity only requires to have computable models: Indeed, the term ( | computable. In practice, the issue of comparing objects of diferent nature is hidden within the ) is defined as long as the models are choice of the reference p.r.p. function for complexity (see Section 2.2).
We propose an alternative definition of reusability, called strong reusability. It is based on the idea that is reuseable if it helps compressing the optimal model of target case ( , ). Unlike previous definition, is not directly involved in the description of ( , ) though. Definition 2 (Strong reusability). Let >
0. A model -reusable for case ( , ) in target model space Mℛ , if: ∈ Mℛ , is called strongly ∈
arg min {
This definition also relies on the choice of a target model space. As for weak reusability, we will abusively omit the model space in the following notations.
Strong reusability is an extremely strong property of a source model. Indeed, it would be a natural property that, in case Mℛ , =
Mℛ , , any model minimizing ( ) + | ( , ) is reusable to ( , ). This is not the case for strong reusability: indeed, the definition implies that any model minimizing ( ) + ( ) can be compressed given , not only itself. Note that this could be alleviated by weakening Definition 2 and | minimizing ( ) + ( , | ) and such that We now present basic properties of these two notions of reusability. All the presented properties follow directly from the definitions.
The first property applies to both weakly and strongly reusable models: it states that the threshold is not unique. The proof of this proposition is trivial and omitted. of to ( , ) the quantity: Proposition 1. Let ∈ Mℛ , and ( , ) ∈ it is also ′-reusable for ( , ) for all ′ ≤ . In the following, we will call degree of reusability . If is -reusable for ( , ), then ( , ( , )) = max {︀ ; is -reusable for ( , )︀} (8)
However, we insist on the fact that the degree of reusability is relative to a chosen target model space. It also depends on which of weak or strong reusability is considered. This dependency would not exist if these two notions of resuability were equivalent, which we will see is not the case. We will use the notation and to specify between the weak and strong cases.
We now show that strong reusability implies weak reusability: If is strongly -reusable for ( , ), then is also weakly -reusable for ( , ). Proposition 2. Let ∈ Mℛ , a source problem, a target case ( , ) ∈ and > 0. ( , | )}. Under the assumptions of the proposition, it follows that: Proof. We call * ∈
Mℛ , an optimal model for ( , ): * ∈ arg min { ( ) + min{ ( ) + ( , | )
} = ( *) + ( , | *) ≥ ( *| ) + + ( , | *) ≥ m in{ ( | ) + ( , | ) + } which proves the proposition.
However, the converse is not true: weak reusability does not imply strong reusability. This is the consequence of the fact that the models implied in Equation (6) are not the same on the right hand side and on the left-hand side. We illustrate this with a simple example. { 1, 2}. We assume the following properties: Example 3. We consider a target model space made up of two distinct models: Mℛ , = • 1 and 2 describe equally well case ( , ), in the sense that ( , | 1) = ( , | 2) 0 take ( 2| ) = ( 2) • Model 1 is more complex than model 2: ( 1) > ( 2) • Model 1 is easily described by source model : for simplicity, we can take ( 1| ) = • Model 2 is not well described by source model : for simplicity, we can
With these assumptions, it can be easily verified that is weakly -reusable for ( , ), ( ) + ( , | ) but ( 2) < ( 2) + = ( 2| ) + . with
≤ ( 2). However, is not strongly -reusable for ( , ), since 2 minimizes Putting together the results of Propositions 1 and 2, as well as the counter-example of Example 3, we can establish the following result: Corollary 1. For ∈ Mℛ , and ( , ) ∈ : ( , ( , )) ≤ ( , ( , )) (9)
The notion of reusability we proposed in Definitions 1 and 2 are not directly applicable to measure transferability from a source observation to a target problem. The property of transferability the target case ( , ) ∈ model is determined based on the source observation. measures the ability to transfer knowledge from a source case ( , ) ∈ . It can be seen as an extension of reusability where the source to apply it to Definition 3 (Transferability). Let ( , ) ∈ models { | ( ) + ( , | ) < ( , ), be strongly (resp. weakly) -transferable to the target case ( , ) ∈ ∈ * such that * is strongly (resp. weakly) reusable for case ( , ).
if the set of compatible
Mℛ , } contains an element be a source case. The case ( , ) is said to
The proposed definition of transferability is very weak, since it only requires the existence of one source model that is reusable. However, it does not take into account the quality of this model in the source domain. For instance, it would acquire equal weight if the reusable source model is associated with complexity ( ) + ( , ) close to ( , ), as if the complexity is close to 0. Such situations are very likely to occur with probabilistic models, since | many such models give positive probability to all observations.
In order to refine this notion, it would be important to define a coeficient of transferability, similar to the degree of reusability defined in Proposition 1. We will denote such a coeficient (( , ), ( , )). We propose two possible definitions below. These definitions rely on the set of compatible models for ( , ) introduced in Definition 3, and denoted M( , ). For simplicity, we will use the notation (resp. ) to designate the case ( , ) (resp. ( , )).
A first definition is a direct application of Definition 3: it associates the transferability of a problem to the maximum reusability of the corresponding model: max (︀ , )︀ =
max with the convention that max ∅ = 0. This definition has the same weakness as the introduced concept of transferability: it does not take into account that the most reusable model might also be very weak to describe ( , ).
In order to alleviate this, our second definition proposes to average the score over the possible models. Therefore, we compute the posterior of the model for given ( , ) and compute the score as the expected value over of the degree of reusability.
avg (︀ , )︀ =
(
|
, ) ( , )
In order to compute the posterior ( , ), we use algorithmic probability [
, ) = 2− ( , | )− ( ) This second definition provides a better idea of how transferable a source observation can be, since it takes into account all possible models describing it. However, it has two major weaknesses. On a theoretical level, it does not reflect the variance of the reusability degree over the compatible models: based on avg only, it is impossible to know whether all models, only very few but very compatible models, or a large number of less compatibles are reusable. On a practical level, the avg score may not be tractable, and would require some approximations.
In this section, we propose to apply the notions introduced in Section 3 to the case of morphological analogies. We will mostly build upon the domain introduced in Example 1.
Morphological analogies are analogies on words involving transformations of a morphological nature, for instance declension or conjugation. Unlike semantic analogies (e.g. “king is to queen as man is to woman"), morphological analogies are mostly of a symbolic nature: they involve the detection of transformations of one form of a word into another form. Typical example of such morphological analogies could be “work : worked :: call : called" in English (transformation from present to preterit, in English), or “voihin : vuossa :: soihin : suossa" (transformation from illative plural to inessive singular in Finnish).
Various works have been proposed to solve such analogies, mostly based on the principles
of proportional analogy [
The model proposed in Example 1 is relevant for a formal treatment of morphological analogies.
However, following Murena et al. [
(13) where the + operation stands for string concatenation, 1, . . . , ∈ * and 0, . . . , ∈ * are words on the alphabet , and : {0, . . . , } → {0, . . . , }. The vector = ( 1, . . . , ) corresponds to the representation, and the models are defined such as in Equation (1).
We notice that the proposed restriction accounts for various types of morphological transformations, such as prefixation, sufixation, change or prefix and/or sufix, but also duplication. However, the language is not Turing complete, and for instance does not cover any conditional statement.
In morphological analogies, the source and target domains are the same.
In order to compute the reusability and transferability, we must define three expressions of complexity: complexity of a model ( ), complexity of a case given a model (, | ) and complexity of a target model given a source model ( | ).
A model is entirely defined by the function . A binary coding of such functions is proposed
in [
Given a model , the case (, ) is coded by providing a correct representation ( 1, . . . , ). In case no representation generates (, ) with model , the two words are hard-coded. In terms of binary representation, we propose the following coding. The string starts with a bit encoding whether the following bits code for the representation vector or for the two words. After this bit, the words are coded letter by letter, with specific delimitors to mark the end of each string. The complexity (, | ) is the length of this code.
For the model transfer, we propose an elementary description. More sophisticated versions have to be discussed in future works. We propose to reuse the source model either by reusing it directly (without modification), or by redefining completely. Such as previously, this choice is indicated by an initial bit. The model complexity is then given by: ( | ) = ︃{ 1 1 + ( ) if = otherwise (14)
Sufixation. We consider the source model associated to transformation ( 1) = ( 1, 1 + “ ”) which consists in sufixing an “s" at the end of a word. We can verify that is -reusable for the target case (“film", “films"). In that case, it can be verified that minimizes quantity ( ) + ( , | ). Consequently, is weakly -reusable for (“film", “films") with ≤ ( ) − 1. This shows that ( , (“film", “films" )) = ( ) − 1. It can also be verified that is the only model minimizing ( ) + ( , | ). Therefore, we also have that is strongly -reusable for (“film", “films") with ≤ ( ) − 1. In this case, we have ( , (“film", “films" )) = ( , (“film", “films" )).
However, the model is not reusable for (“mouse", “mice") for instance, since the minimal transformation for this case is ′( ) = ( + “ouse", + “ ”). We then have ( , (“mouse", “mice")) = ( , (“mouse", “mice")). Duplication. We consider the source model associated to transformation ( 1) = ( 1 + “ − ” + 1, 1). This transformation is the reverse of a duplication (plural form in Indonesian). As for previous example, one can easily check that is not reusable for the case (“orang", “orang-orang"). This was expected, with the choice of the transfer representation ( | ) which forces toward reusing the source model or ignoring it completely. It would not have been the same with other choices though. In particular, if it allowed for model transformation of the form ( 1, 2) ↦→ ( 2, 1).
Domain adaptation is a machine learning task where a hypothesis on a source domain has to be
transferred to a target domain where data are not equally distributed [
The question of transferability of one solved source problem to a target problem has played
a predominant role in the theoretical understanding of domain adaptation. Ben-David et al.
(2010) [
We describe the domain adaptation task in the context of the probabilistic model space defined in Example 2, in which a model is associated to a probability distribution. Such as for the morphological domain (Section 4.3), we need to define the complexities ( ), (, | ) and ( | ).
The term (, | ) is a standard quantity considered by Algorithmic Information Theory. It is commonly computed using the Shannon-Fano coding. Using this allows to define the complexity of an object (, ) knowing a probability distribution as (, | ) = − log (, ). This corresponds to the natural choice when computing (, | ) in our probabilistic domain.
Defining ( ) and ( | ) is more dificult thought and goes beyond the scope of this
paper. Traditionally, the complexity of a probability distribution is assimilated to the probability
of its density function, and specific computations are proposed to estimate these. We refer the
interest the interested reader to [
Extending our framework to domain adaptation is both natural and complex. Indeed, the problem formulation in terms of models allow for a direct characterization of domain adaptation, where a domain is characterized by an unlabeled dataset (the problem) and a vector of predictions (the solution). However, the computation of the complexities may not be as simple as for the symbolic domain. Future works will have to bridge this gap.
In this paper, we introduced a novel understanding of analogical transfer, by focusing on whether
the information contained in the source case were transferable to the target case. We proposed
a formalism based on a notion of models, which we defined in a way that is consistent with
both symbolic analogies and numerical machine learning. Even though this preliminary works
cover only the question of measuring the transferability from a source case ( , ) to a target
case ( , ), it is a first step toward the key question of predicting whether knowledge of
( , ) could be reused to find a solution to problem . We think the proposed framework
could provide a common basis to develop a general understanding of transfer, going beyond the
current statistical theories [
The author wishes to thank the anonymous reviewers for their insightful comments and suggestions. Some of the presented ideas have been inspired by discussions with Antoine Cornuéjols, Jean-Louis Dessalles, Marie Al-Ghossein and Miguel Couceiro. This work was supported by the Academy of Finland Flagship programme: Finnish Center for Artificial Intelligence, FCAI.