Yves Lepage
email: yves.lepage@waseda.jp

Jean Lieber
email: jean.lieber@loria.fr

Case-Based Translation: First Steps from a Knowledge-Light Approach Based on Analogy to a Knowledge-Intensive One

Keywords: Analogy, Machine translation, Knowledge-light case-based reasoning, Knowledge-intensive case-based reasoning

This paper deals with case-based machine translation. It is based on a previous work using a proportional analogy on strings, i.e., a quaternary relation expressing that "String A is to string B as string C is to string D". The first contribution of this paper is the rewording of this work in terms of case-based reasoning: a case is a problem-solution pair (A, A ) where A is a sentence in an origin language and A , its translation in the destination language. First, three cases (A, A ), (B, B ), (C, C ) such that "A is to B as C is to the target problem D" are retrieved. Then, the analogical equation in the destination language "A is to B as C is to x" is solved and D = x is a suggested translation of D. Although it does not involve any linguistic knowledge, this approach was effective and gave competitive results at the time it was proposed. The second contribution of this work aims at examining how this prior knowledge-light case-based machine translation approach could be improved by using additional pieces of knowledge associated with cases, domain knowledge, retrieval knowledge, and adaptation knowledge, and other principles or techniques from case-based reasoning and natural language processing.

Introduction

Right after the advent of computers, machine translation was the very first non-numerical application envisaged for these machines [START_REF] Weaver | Translation. Tech. rep[END_REF]. The first approach consisted in word-to-word translation, relying on large bilingual dictionaries that contained assembly instructions for insertion, deletion or movement of words relying on the inspection of close context. It was rapidly understood that the focus should move from bilingual dictionaries to monolingual grammatical descriptions of languages and the design of parsers and generators, hence the so-called rulebased approach, in which translation itself took place in a transfer phase, working at a higher level of description [START_REF] Boitet | Current state and future outlook of the research at GETA[END_REF].

Data-Oriented Approaches to Machine Translation

The idea of example-based machine translation was introduced for the first time in the seminal paper of Nagao [START_REF] Nagao | A framework of a mechanical translation between Japanese and English by analogy principle[END_REF]: translation should be performed by comparing a new sentence to be translated (the target problem) to existing examples of translations (a source problem and its solution, i.e., its translation). Although some research in example-based machine translation was started, it was rapidly overwhelmed by the stream of statistical machine translation (SMT), an approach that also entirely relies on the availability of aligned parallel corpora, i.e., sets of translated sentences. In the statistical approach to machine translation, several types of knowledge are extracted from aligned corpora: mainly dictionaries of corresponding short sequences of words with associated translation probabilities, probabilities for how they should be reordered, and probabilistic language models for the fluency in the destination language.

Availability of Data for Machine Translation

Statistical machine translation systems require aligned bilingual corpora to extract the above-mentioned knowledge. In 1988, the founders of the approach, IBM researchers [START_REF] Brown | A statistical approach to machine translation[END_REF], used the Hansard corpus of proceedings of the Canadian parliament for French-English. The need for such corpora intensified their production. In 2002, ATR officially announced a multilingual corpus with 160,000 sentences in Japanese, Chinese and English [START_REF] Takezawa | Toward a broad coverage bilingual corpus for speech translation of travel conversation in the real world[END_REF]. The European Parliament speeches corpus (Europarl) contained at least 400,000 sentences in combination with English for 23 other languages in its 3 rd version in 2005 [START_REF] Koehn | Europarl: A Parallel Corpus for Statistical Machine Translation[END_REF]. Evaluation campaigns then collected and released corpora of more that 1 million sentences (WMT 2006 et seq., IWLST 2014 et seq.). With the operational deployment of systems on the Web, large companies or institutions were able to collect very large corpora: Google is claiming 1 billion aligned sentences in French-English in 2016 [START_REF] Johnson | Google's multilingual neural machine translation system: Enabling zero-shot translation[END_REF][START_REF] Schuster | The move to neural machine translation at Google (invited talk)[END_REF]; the World Intellectual Property Organisation (WIPO) is also claiming hundreds of millions of aligned sentences extracted from patent families in various language pairs [START_REF] Ziemski | The United Nations Parallel Corpus v1.0[END_REF]; the DGT-Translation memory of the Directorate-General for Translation of the European Commission released 6.8 million translation units in March 2018 in addition to the several million units already released. Subtitles also constitute an invaluable resource of multilingual aligned data [START_REF] Tiedemann | News from OPUS -A collection of multilingual parallel corpora with tools and interfaces[END_REF][START_REF] Lison | OpenSubtitles2016: Extracting large parallel corpora from movie and TV subtitles[END_REF].

The statistical machine translation approach, which had been dominant in research approximately from 2005 to 2015, was in turn drowned under the tsunami of the neural network approach to machine translation (NMT). This last approach requires even larger amount of data than statistical machine translation systems (and also enormous computation time and power in comparison to statistical machine translation), but, for well-resourced languages, this is no more a problem. Indeed, very large amounts of data are available for such languages and part of such data is not even used during training. For instance, [START_REF] Schuster | The move to neural machine translation at Google (invited talk)[END_REF] reports that Google used only 15 % of the total of the French-English data at their disposal for their neural machine translation system.

The Challenge of Less-Resourced Languages: an Opportunity for Case-Based Reasoning

As enough data is available for well-resourced languages or language-pairs, the consciousness about less-resourced languages is raising among researchers in the natural language processing community. There exist more than 6,000 languages in the world and only slightly more than 100 are available with Google Translate. The Linguistic Data Consortium is aware of the lack of data for the majority of the languages of the world and is starting to explore less expensive ways to collect data for such languages, e.g., through gamification [START_REF] Cieri | Addressing the language resource gap through alternative incentives, workforces and workflows[END_REF]. Other techniques which are being proposed are in the vein of zero-shot translation, i.e., the possibility of mapping data across independently learnt neural network models [START_REF] Johnson | Google's multilingual neural machine translation system: Enabling zero-shot translation[END_REF].

Another possibility could well be the use of case-based reasoning, which is supposed to be a remedy when not so many examples are available. As explained above in Section 1.1, applying case-based reasoning to machine translation was indeed present in Nagao's proposal in 1984, however its first mention with its official name, or at least under the form of memory-based reasoning, is to be found in Kitano's description of massive parallel artificial intelligence later in 1993 [START_REF] Kitano | Challenges of massive parallelism[END_REF].

Purpose of the Paper

The purpose of this paper is twofold. Its first objective is to reword examplebased machine translation, in particular the approach described in [START_REF] Lepage | Purest ever example-based machine translation: detailed presentation and assessment[END_REF], in terms of case-based reasoning, so as to open opportunities for CBR researchers to tackle machine translation for less-resourced language pairs. We will show that this particular approach to example-based machine translation corresponds indeed to a knowledge-light CBR approach using analogies.

The second objective is to open paths for improving this approach to examplebased machine translation, as such rewording will open opportunities to CBR researchers to easily spot possible places where improvement can be brought. In particular, we see opportunities for CBR researchers to work on more elaborated description of cases, or introducing and representing domain knowledge, or knowledge dedicated to retrieval and adaptation.

These two objectives are addressed in Sections 3 and 4. They are preceded by a section giving some preliminaries, Section 2.

2 Preliminaries: Definitions, Notations, Assumptions

On Case-based Reasoning

A Reminder of the Main Notions. Case-based reasoning (CBR [START_REF] Riesbeck | Inside Case-Based Reasoning[END_REF]) aims at solving a new problem-the target problem, denoted by tgt-with the help of cases, where a case represents a problem-solving episode. In this paper, a case is denoted by an ordered pair (pb, sol(pb)) where pb is a problem and sol(pb) is a solution of pb. However, it may occur that some additional pieces of information are associated with a case. The case base is a finite set of cases and constitutes an essential source of knowledge of the CBR system. A source case (srce, sol(srce)) is an element of the case base, srce is a source problem.

The process model of CBR consists usually in four steps: retrieval, adaptation, correction and memorization (also known as retrieve, reuse, revise and retain in the 4Rs model of [START_REF] Aamodt | Case-based reasoning: Foundational issues, methodological variations, and system approaches[END_REF]). Retrieval consists in selecting one or several source case(s). Adaptation uses this or these case(s) to propose a first solution sol(tgt) to tgt. This solution sol(tgt) is possibly corrected, e.g. by confrontation to a human expert. Finally, the newly formed case (tgt, sol(tgt)) is memorized in the case base if this is judged to be useful.

The knowledge model of CBR decomposes its knowledge base in four containers [24]. The first one is the case base, already mentioned. The domain ontology contains knowledge about the objects and properties used to represent the cases in the application domain. It can be considered as a representation of necessary conditions for a case to be licit. The retrieval knowledge is used during the retrieval step, the adaptation knowledge, during the adaptation step.

The First Approach to Example-Based Machine Translation. The seminal paper in example-based machine translation by Nagao in 1984 [START_REF] Nagao | A framework of a mechanical translation between Japanese and English by analogy principle[END_REF], was indeed "case-based reasoning comes early." In its introduction, the problem of translation is stated as follows: given a sentence in a language to be translated into another language, use another sentence in the same language that differs by only one word and for which the translation in the other language is known, change the word that differs in the other language to get the final translation. Given the above description of example-based machine translation, one can imagine a CBR process based on the use of a bilingual dictionary for managing several mismatches between the source and the target problems. This was the approach explored in [START_REF] Sato | Example-based Machine Translation[END_REF]. An entry of such a dictionary is a pair (w o , w d ) where w o (resp., w d ) is a word in the origin language (resp., the destination language). It also contains the pair (ε, ε): the empty string ε is considered as a particular word in both languages. The principle of this approach is as follows:

Retrieval Find a case (srce, sol(srce)) that is similar to tgt in that a minimal number of words have to be substituted in srce to get tgt. Adaptation For each word substitution w o s w o t from srce to tgt in the origin language, the word substitution w d s w d t is built in the destination language, using the dictionary entries (w o s , w d s ) and (w o t , w d t ). Then, these substitutions are applied on sol(srce) to get sol(tgt).

For example, with French as origin language and English as destination language:

tgt = Amenez-moi à Pluton. srce = Amenez-moi à votre chef. sol(srce) = Take me to your leader. hence tgt = σ o (srce) with σ o = chef Pluton • votre ε.
Given the entries (Pluton, Pluto), (chef , leader ), (votre, your ) and (ε, ε)

it comes σ d = leader Pluto • your ε hence sol(tgt) = σ d (sol(srce)) = Take me to Pluto. (correct translation)
Note that this approach is likely to propose a large number of incorrect translations among the proposed solutions, in particular because a single word in the origin language can be translated in different ways and no context is used here to select the appropriate word.

A more elaborate approach to example-based machine translation was proposed in [START_REF] Sadler | Pilot implementation of a bilingual knowledge bank[END_REF] in which additional pieces of information are added to cases in the form of their dependency parses. Adaptation is constrained by the shape of the dependency trees, in that only sub-sequences of words which correspond to a sub-tree in dependency trees can be substituted for. It then becomes crucial to be able to align dependency sub-trees across languages and to perform fast approximate retrieval of sub-trees. The Kyoto EBMT system implemented such an approach [START_REF] Nakazawa | EBMT system of KYOTO team in patentMT task at NTCIR-9[END_REF].

On Strings and Texts

An alphabet A is a finite set. A character is an element of A. A string of length ≥ 0 on A is a finite sequence α 1 α 2 . . . α of characters.
The set of strings is denoted by A * . It contains the empty string ε. Edit distances on strings are distance functions on A * , defined as follows. An edit operation is a function from A * to A * . Common edit operations are the following ones:

-Deletions consist in removing a character of a string. For example, the deletion of the 3 rd character of the string case yields cae. -Insertions consist in inserting a character into a string at a given position.

For example, inserting s after position 4 of string case yields cases. -Substitutions consist in replacing a character of a string with another character. For example, the substitution of c with b at the 1 st position of case yields base. A substitution can be written as the composition of a deletion and an insertion. In the example: case → ase → base. -Swaps consist in swapping two contiguous characters. For example, swapping a with s in case yields csae. -Shifts are extension of swaps to non-necessarily contiguous sequences of characters. The length of the gap is usually taken into account to compute the weight of shifts. For example, shifting se with ca in case yields seca. -Etc.

An edit path is a sequence P = e 1 ; . . . ; e p-1 ; e p of edit operations e i . Such a path relates a string S 1 to a string S 2 if e p (e p-1 (. . . (e 1 (S 1 )) . . .)) = S 2 . Let weight be a function that associates to an edit operation e an integer weight(e) > 0. This function is extended on edit paths by weight(e 1 ; e 2 ; . . . ; e p ) = p i=1 weight(e i ). Given a set of edit operations and a function weight, the edit distance from a string S 1 to a string S 2 is defined as

dist(S 1 , S 2 ) = min{weight(P) | P: path from S 1 to S 2 }
The Levenshtein distance is an edit distance that considers deletions, additions and substitutions only, each with a weight of 1. The LCS distance (longest common subsequence) is simpler in that it considers deletions and insertions only, with a weight of weight(e) = 1 for every operation (in this setting, substitutions have a weight of 2). The computation of the Levenshtein or the LCS distance is quadratic in the worst case [START_REF] Backurs | Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)[END_REF] (proving that the Levenshtein distance can be computed in lesser time would imply P = N P [START_REF] Wagner | The string-to-string correction problem[END_REF]). Better behaviours can be obtained for felicitous cases; for instance, the computation of the distance between two equal strings is of course linear in the length of the string by Ukkonen's algorithm [START_REF] Ukkonen | Algorithms for approximate string matching[END_REF].

It is worth noting that edit distances have been used in CBR on other structures, such as temporal sequences [START_REF] Rougegrez-Loriette | Prédiction de processus à partir de comportement observé : le système REBECAS[END_REF] or graphs [START_REF] Bunke | Similarity measures for structured representations[END_REF][START_REF] Lieber | Using classification in case-based planning[END_REF].

A Knowledge-Light Approach to Case-Based Translation Using Analogies

In [START_REF] Lepage | Purest ever example-based machine translation: detailed presentation and assessment[END_REF], an implementation of example-based machine translation was proposed and evaluated. The approach was effective: at that time, it delivered comparable results to nascent statistical methods. It worked only on the string level and did not involve any linguistic knowledge. The purpose of this section is to describe it anew, but this time, in terms of knowledge-light CBR. Before relating it to CBR, an analogical relation between strings is introduced. A proportional analogy between strings is defined as follows. First, let A = {α 1 , α 2 , . . . , α p } be a predefined finite set of characters, i.e., an alphabet. For a given string S ∈ A * , where A * is the set of all strings on A, let π(S) = (|S| α1 , |S| α2 , . . . |S| αp ) be the Parikh vector of string S, i.e., the vector of the number |S| αi of occurrences of each character α i in S. Then, four strings A, B, C, D are in proportional analogy, i.e., A : B :: C : D, if π(A) : π(B) :: π(C) : π(D) and dist(A, B) = dist(C, D), with dist the LCS distance. If A : B :: C : D, it can be proven that dist(A, C) = dist(B, D) also holds, thanks to the exchange of the means. For example, it can be easily checked that the following strings make a proportional analogy:

Analogy Between Strings

A = to reason B = reasoning C = to do D = doing In particular, |B| r -|A| r = 1-1 = |D| r -|C| r = 0-0, |B| n -|A| n = 2-1 = |D| n - |C| n = 1 -0, dist(A, B) = dist(C, D) = 6, and dist(A, C) = dist(B, D) = 6.
Two words of caution: On integers, any analogical equation has exactly one solution (D = B -A + C always exists). By contrast, on strings, it can have zero, one or multiple solutions. For example, a : b :: ac : x has two solutions: bc or cb. Also, notice that, on strings, conformity is not transitive in the general case: A : B :: C : D and C : D :: E : F do not imply A : B :: E : F in general.

Case Representation

In the domain of machine translation, a problem pb is given by a sentence in an "origin" language (e.g., French) and a solution of pb is a sentence sol(pb) in a "destination" language (e.g., English). A case is a pair (pb, sol(pb)), without additional information. Fig. 1 illustrates a case base containing such cases, i.e., pairs of translated sentences. He wants to do that. Je peux faire du vélo aujourd'hui.

I can ride my bicycle today. J'aime ce chat.

I like this cat. J'ai sauté au plafond.

I hit the roof.

Fig. 1. A toy case base of translations from French into English.

No Domain Knowledge Used

It is worth mentioning that this approach uses no domain knowledge (no linguistic knowledge about any of the two languages involved or about their relationships): the knowledge is contained only in the cases. This makes the approach independent of any language: only the case acquisition has to be carried out to apply it to a new pair of origin and destination languages.

Retrieval

Let tgt be the French sentence to be translated. In the running example, the following French sentence is chosen: tgt = Je veux faire du vélo.

Retrieval aims at finding one or several triples of source cases ((srce A , sol(srce A )), (srce B , sol(srce B )), (srce C , sol(srce C ))) such that srce A : srce B :: srce C : tgt. With the running example, the source problems could be srce A = Tu peux le faire aujourd'hui.

srce B = Tu veux le faire.

srce C = Je peux faire du vélo aujourd'hui.

If no such triple can be found, an alternative approach can be applied (see Section 3.6).

Adaptation

Given a target problem and a source case triple that has been retrieved, the adaptation is based on the following principle: if four sentences in the origin language are in proportional analogy then it is plausible that their translations in the destination language are also in proportional analogy. Based on this idea, the adaptation of the source case triple to solve the target problem consists in solving the following analogical equation: The equation is solvable and gives the following solution which is a correct translation of tgt: sol(tgt) = I want to ride my bicycle.

Since there may be several retrieved source case triples and, for each of them, several solutions to the analogical equation in the destination language, the approach may propose a set of solutions sol(tgt) (possibly repeated a number of times), not necessarily all correct. The translation examples in [START_REF] Lepage | Purest ever example-based machine translation: detailed presentation and assessment[END_REF] suggest that the quality of the solutions should be correlated with their output frequency.

Recursive Application of the CBR Process

The main bottleneck of the above approach lies in the fact that the first step of retrieval is obviously prone to fail in the majority of cases, unless a more flexible definition of analogy between strings is provided. We will discuss more flexible approaches later (Sections 4.1 and 4.5). With the purely symbolic approach described above in Section 3.1 for analogy between strings, there is statistically very little chance to find a source case triple of sentences which makes an analogy with a given target problem (the input sentence to translate), even in a dense data set consisting of very short sentences from similar restricted domains exhibiting a large number of commutations (like the BTEC corpus: My tooth hurts., My head hurts., My head hurts badly., etc.). In [START_REF] Lepage | Purest ever example-based machine translation: detailed presentation and assessment[END_REF] where a purely symbolic approach was adopted, a recursive application of the method was proposed to remedy this problem: instead of triples, pairs of cases (srce A , srce B ) are retrieved. Solving srce B : srce A :: tgt : x for x yields srce C . When srce C does not already belong to the case base, it is considered a new target on which to apply the CBR process recursively. This recursive application is different from [START_REF] Stahl | Applying recursive CBR for the customization of structured products in an electronic shop[END_REF] where recursive reasoning is applied to sub-components, hence on the hierarchical structure of the cases. Recursive CBR on sub-parts of sentences seems also a promising topic for translation. We think that all this opens new avenues to study: how to combine retrieval with a recursive application of the CBR process itself on entire cases or sub-parts of cases so as to lead to a solution of the target problem as fast as possible?

Towards a Knowledge-Intensive Approach to Case-Based Translation Using Analogies

The approach presented in the previous section is effective, though it only uses simple cases, the LCS edit distance and no other knowledge containers. The aim of this section is to examine how this approach can be improved thanks to a more flexible definition of analogies (Section 4.1), a richer case representation (Section 4.2), the use of domain knowledge (Section 4.3), and the modification of the following CBR steps using some additional knowledge: retrieval and adaptation (Sections 4.4 and 4.5). Other techniques related to CBR or to natural language processing could be used as well to improve the system, such as case maintenance techniques or textual CBR techniques (see e.g. [START_REF] Smyth | Remembering To Forget[END_REF] and [START_REF] Weber | Textual case-based reasoning[END_REF]).

Using More Flexible Analogies

Word vector representations may allow for a more flexible definition of analogies between sentences, considered as sequences of words. One of the recent breakthroughs in natural language processing is the use of (shallow) artificial neural networks for the fast computation of distributional semantic word vector representations (word embeddings) from large corpora [START_REF] Mikolov | Efficient estimation of word representations in vector space[END_REF][START_REF] Pham | Learning distributed representations for multilingual text sequences[END_REF][START_REF] Řehůřek | Making sense of word2vec, available on line 24[END_REF]. This offers the possibility of solving semantic analogies, as illustrated by the hackneyed example man : woman :: king : x leads to x = queen [START_REF] Mikolov | Efficient estimation of word representations in vector space[END_REF], through the computation of semantic similarities between words. Vector representations of words had in fact already been proposed [START_REF] Turney | Corpus-based learning of analogies and semantic relations[END_REF][START_REF] Turney | From frequency to meaning: Vector space models of semantics[END_REF] to answer (SAT) questions using a model inspired by Gentner's structural mapping engine [START_REF] Gentner | Structure mapping: A theoretical model for analogy[END_REF], called the Latent Relation Mapping Engine [START_REF] Turney | The latent relation mapping engine: Algorithm and experiments[END_REF]. As for sentences, so-called soft alignment matrices give the word-toword distance between each pair of words in two sentences. Figure 2 illustrates how it could be possible to use such representations to solve analogical equations between sentences. Some attempts have already been made either using soft alignment representations [START_REF] Kaveeta | Solving analogical equations between strings of symbols using neural networks[END_REF] or vector representations of sentences [START_REF] Ma | Structural sentence similarity estimation for short texts[END_REF].

We think that this general problem is relevant for the CBR community as it falls within the topic of computational analogy: how to solve analogical equations between sentences in a truly semantic way?

Enriching the Case Representation

The approach of [START_REF] Lepage | Purest ever example-based machine translation: detailed presentation and assessment[END_REF] shows that "raw cases", i.e. pairs of translated sentences only, can already be effective. However, additional pieces of information to a case can improve its re-usability through CBR. In particular, linguistic information can be used. For instance, parts of speech or morphological features like verb tenses (see an example in Section 4.3) or the fact that a sequence of characters constitutes a noun in singular form (example in Section 4.5), can be used. This is related to the various steps of the CBR process and raises several issues. In particular, the following question is worth studying, from a case acquisition effort perspective: when is it more beneficial to (manually or automatically) acquire additional information on cases instead of acquiring new raw cases?

Taking into Account Domain Ontology

The domain ontology (or domain knowledge) is used for several purposes. First it expresses a vocabulary in which cases can be expressed. For example, in a cooking application (such as Taaable [START_REF] Cordier | Taaable: a Case-Based System for personalized Cooking[END_REF]), queries, cases and other knowledge units are expressed with terms like citrus fruit, lemon, etc. Here, this would be the vocabulary used to represent features of the cases in an enriched representation.

Second it expresses integrity constraints about this vocabulary. In the cooking application, this could be for example ϕ = lemon ⇒ citrus fruit. 1 Indeed, ϕ can be read as the integrity constraint "There is no recipe with lemon and without citrus fruit.", formally: "ϕ∧lemon∧¬citrus fruit is insatisfiable." Back to the machine translation application, what could be such an integrity constraint and how could it be used to better solve translation problems? One possible answer is the use of linguistic knowledge about the destination language that will recognize that a sentence is not correct (because of a non existing word or because of an ungrammatical construction); this can be used to simply rank the possible solutions. For example, the sentence I have gone. should be preferred to I have goed., if both are produced. Standard NLP techniques would, e.g., determine that future tense is used consistently in both languages, so that translation of future tense into future tense should be preferred. For example, the French sentence Je me lèverai. (future tense) could be translated into I will get up. and I am going to get up. According to this criterion, the first sentence could be preferred to the second one though, in fact, both translations are acceptable here. This is why the less preferred solution should be given a lower rank but not necessarily discarded.

What are the NLP techniques case-based translation using analogies can profit from when it is applied to less-resourced languages? E.g., when not enough data is available to build reliable N-gram language models, can linguistic knowledge like incomplete linguistic parsers help to efficiently rank the possible translations? Can case-based translation using analogies identify lacking linguistic descriptions of less-resourced languages?

Taking into Account Retrieval Knowledge

In a standard CBR setting, the complexity of retrieval is typically O(n) to pick up the most similar case, or O(n × log n) to sort the entire case base, of size n, by similarity to the target problem. For the model described in Section 3.4, the complexity of retrieval is the price to pay for the lightness of knowledge and the null cost of adaptation: the previous complexities become O(n 3 ) or O(n 3 × log n 3 ) = O(n 3 × log n). In the case of the approach described in Section 3.6, this complexity is quadratic or more, because a recursive application of the CBR process has a cost.

A way to reduce the computational cost of retrieval is to explicitly compile retrieval knowledge in advance, e.g., in the form of analogical clusters, i.e., series of source pairs which stand for the same transformation. For instance (English meaning below French):

Il peut faire ça aujourd'hui. : Il veut faire ça. This technique has never been applied to example-based machine translation, but it has been used for statistical machine translation to create new pairs of aligned sentences (in CBR terms, source problems and their solutions) so as to augment the training data (the case base in CBR terms) [START_REF] Yang | Inflating a small parallel corpus into a large quasiparallel corpus using monolingual data for Chinese-Japanese machine translation[END_REF]. Analogical clusters identify well attested transformations, which should thus be reliable. It is then possible to choose to generate new source cases srce C from such clusters only, by simultaneously solving all possible analogies formed by the set of the case pairs in a given cluster in conjunction with tgt, as illustrated below (English meaning of tgt below: 'I want to ride a bicycle'). During retrieval, computing the similarity of tgt to each sentence in the case base reduces the cost of retrieval to O(n) or O(log n). The most similar cases can lead directly to the clusters they belong to using an inverse index. This avoids redundancy firstly in the retrieval of source case pairs, secondly in the generation of srce C , and thirdly in adaptation, because the generation of the same srce C is factored once in comparison with several generations in the absence of clusters. This should thus considerably speed up the overall process.

As enriching not only the case base but also the retrieval knowledge should be an essential feature of a knowledge-intensive CBR approach, the question of managing the dynamic aspect of retrieval knowledge in the recursive application of the CBR process (Sect. 3.6) is a challenging question: when and how should new retrieval knowledge be compiled and added to profit from new cases of the type (srce C , sol(srce C )) that are added to the case base along the recursive application of the CBR process?

Using Adaptation Knowledge

The proportional analogy on strings defined in Section 3.1 is used for adapting three cases in order to solve a target problem. It covers a wide variety of situations. However, some situations that are recognized as analogies are not covered by it, hence the usefulness of defining specific edit operations or even specific edit distances for specific languages, constituting therefore new adaptation knowledge.

Let us exemplify with the case of marked plural forms of nouns in Indonesian or Malay. Marked plurals are expressed by repetition: the marked plural form of a noun w is w-w. For the sake of simplicity, let us express the case using English: the marked plural of cat (several cats) would be cat-cat. Therefore, in such languages, the analogy A : B :: C : D between the following strings makes sense:

A = I like this cat. B = She likes cat-cat. C = I avoid this dog. D = She avoids dog-dog.

(

The definition of proportional analogy of commutation presented in Section 3.1 does not cover this case, because, e.g.,

|B| t -|A| t = 2 -2 = |D| t -|C| t = 0 -1.
In order to take this phenomenon into account, the idea is to define an edit distance dist whose edit operations are the ones of the LCS distance, plus an edit operation repeat noun that would replace a substring w that is recognized as a noun in singular form, with its marked plural form w-w (in a manner reminiscent of what was done for consonant spreading in Arabic in the framework of two-level morphology [START_REF] Beesley | Consonant spreading in Arabic stems[END_REF]) and its reverse edit operation, replacing w-w with w. Each of the above edit operations should be assigned a cost of 1. Another change to the proportional analogy of Section 3.1 is the fact that the number of occurrences |S| c of character c in string S is considered only for the strings obtained by removing the nouns w and w-w involved in the computation of the two new edit operations. With these changes the sentences in (1) are in analogy. Another language-dependent procedure that can be integrated in the adaptation process is the use of correction techniques in the destination language. For example, for tgt = As-tu mangé une orange ? , a retrieved triple of source cases can be (srce A , sol(srce A )) = (J'ai sauté au plafond., I hit the roof.) (srce B , sol(srce B )) = (J'ai mangé une orange., I ate an orange.) (srce C , sol(srce C )) = (As-tu sauté au plafond ? , Did you hit the roof ? ) This leads to the proposed solution sol(tgt) = Did you ate an orange? , which is incorrect. A spell-checker, such as the ones used in some word processors, can be used to correct sol(tgt) in such a situation. It is noteworthy that domain knowledge can play a role in a correction process: linguistic knowledge can be used to examine what makes a sentence incorrect. If such an automatic correction process fails, a human user can correct the sentence, giving birth to a correction case: (Did you ate an orange? , Did you eat an orange? ) in the example. Research in correcting SMT errors using, e.g., a NMT system trained on correction cases already exists [START_REF] Pal | A neural network based approach to automatic post-editing[END_REF]. Sets of correction cases are already available2 . But basically, SMT and NMT systems are not traceable, which should be contrasted to case-based translation systems using analogies: used cases can easily be traced and the adaptation and correction knowledge is explicit.

This last topic is directly of interest to the CBR community: can we implement MT systems which are true explainable AI systems, i.e., systems where human-readable linguistic knowledge is easy to integrate and leads directly to visible improvement and where translation results can be intuitively explained?

Conclusion

The application aimed in this paper is machine translation (MT), especially MT for language pairs for which corpora of examples are small, relatively to the size of the corpora used in nowadays neural network approaches to MT. Indeed, it is our working hypothesis that case-based MT is competitive in such a context. This hypothesis is based on the prior work of [START_REF] Lepage | Purest ever example-based machine translation: detailed presentation and assessment[END_REF] that is reformulated here in terms of case-based MT. This reformulation constitutes the first contribution of this paper. This approach is knowledge-light in the sense that the only languagedependent pieces of knowledge are the cases, which are raw cases, representing only the problem and the solution (the sentences in the origin and destination languages), without any additional information. This approach is based on the transfer of proportional analogies found in the origin language onto the destination language.

The second contribution of this work is a theoretical examination of the question: "How can this knowledge-light case-based MT approach be improved by incorporating some new pieces of knowledge and other principles, methods, and techniques from CBR or NLP?" Obviously, the answers given in this paper are at an embryonic stage. Therefore, future directions of work are obvious: implementing and testing the ideas presented and developing new ideas for knowledge-intensive case-based MT.

Our impression is that this issue of case-based MT, though little explored nowadays, deserves much research: there are certainly many ways to improve it and it is worth doing so with the aim of developing competitive MT systems that are not limited to pairs of languages with very large corpora. One way, still under investigation, is to continue this research through a contest, similar to the Computer Cooking Contest. Such contests already exist for MT, but they focus on very large corpora. The idea would be to organize such a contest on smaller corpora like the small ones offered by the Tatoeba project3 and to use the off-the-shelf automatic evaluation techniques of the MT community.

A

  proportional analogy is a quaternary relation between four objects A, B, C and D denoted by A : B :: C : D. In all generality, we call conformity the operation denoted by the sign :: and ratio the operation denoted by the sign :. An analogy should satisfy the following properties (for any objects A, B, C and D of the same type): Reflexivity of conformity: A : B :: A : B; Symmetry of conformity: if A : B :: C : D then C : D :: A : B; Exchange of the means: if A : B :: C : D then A : C :: B : D. An analogical equation is an expression of the form A : B :: C : x where A, B and C are given objects and x is the unknow. Solving such an equation for x consists in finding the objects x satisfying this equation.A proportional analogy between numbers is defined by A : B ::C : D if B -A = D -C, i.e., conformity is equality and ratio is subtraction. A proportional analogy between n-tuples of numbers (A = (a 1 , a 2 , . . . , a n )) is defined by A : B :: C : D if a i : b i :: c i : d i for each i ∈ {1, 2, . . . , n}. For instance, (0, 2) : (3, 3) :: (1, 6) : (4, 7).

  srce sol(srce) As-tu sauté au plafond ?Did you hit the roof ? Elle évite ce chien.She avoids this dog. Elle évite les chiens. She avoids dogs. Il veut faire ça.

  sol(srce A ) : sol(srce B ) :: sol(srce C ) : x In the running example, the English sentences translating the French sentences srce A , srce B and srce C are sol(srce A ) = You can do it today. sol(srce B ) = You want to do it. sol(srce C ) = I can ride my bicycle today.

Fig. 2 .

 2 Fig. 2. Soft alignment matrices for analogies between sequences of words (example from Sect. 3.5). A cell in a matrix is the distance between the two corresponding words (arccos of the cosine of their vectors in the word embedding space), the closer the whiter. The two matrices in (a) are computed from three given sentences. How to compute the matrices in (b) from the matrices in (a) is an open problem. The solution of the analogy in (c) should be computed from the matrices in (b).

  Il veut faire ça. Je veux le faire. Tu veux la voir ? : Il peut faire ça aujourd'hui. Je peux le faire aujourd'hui. Tu peux la voir aujourd'hui ? :: Je veux faire du vélo. : x leads to x = Je peux faire du vélo aujourd'hui. 'I can ride my bicycle today.'

  Je peux le faire aujourd'hui. : Je veux le faire.

	'He can do that today.'	'He wants to do that.'
	'I can do it today.'	'I want to do it.'
	Tu peux la voir aujourd'hui ? : Tu veux la voir ?
	'Can you see her today?'	'Do you want to see her?'

In this section, the ideas are illustrated in propositional logic, but could easily be expressed in other formalisms.

E.g., https://www.matecat.com/. The authors of this paper are currently working on a slightly different scenario and are collecting such correction cases for use in a case-based correction system.

https://tatoeba.org/

The first author is supported by a JSPS Grant-In-Aid 18K11447: "Self-explainable and fast-to-train example-based machine translation using neural networks."


Valéry Psyché

Jacqueline Bourdeau

Roger Nkambou

Riichiro Mizoguchi

Making Learning Design Standards Work with an Ontology of Educational Theories

In this paper, we present an ontology of educational theories their relation to learning design. This ontology takes into account learning design (LD) specifications such as OUNL-EML and IMS-LD at the conceptual level (1), semantic web standards such as OWL at the formal level (2), as well as JAVA standards at the implementation level (3).

This ontology is intended to provide a knowledge base for any IMS-LD compliant authoring systems/LKMS, in order to provide services to authors of LD scenarios. The ontological engineering (OE) has been done using the Hozo ontology editor at levels 1 and 2 respectively.

Introduction

The research presented in this paper follows the initial idea developed in [START_REF] Bourdeau | Collaborative Ontological Engineering of Instructional Design Knowledge for an ITS Authoring Environment[END_REF] [2] [START_REF] Mizoguchi | Knowledge engineering of educational systems for authoring systems design[END_REF], regarding the elicitation through ontological engineering (OE) of instructional design, instruction, learning and knowledge in an authoring system.

The foundations of ontological engineering issues in authoring systems were established in [START_REF] Psyché | Ontology Development at the Conceptual Level for Theory-Aware ITS Authoring Systems[END_REF] [START_REF] Bourdeau | Potential of an Ontology-based ITS Authoring Environment: One Example[END_REF], in which we presented (a) a case analysis and (b) the rationale behind it. In (a), specifically, an author assisted by an authoring system or a Learning and Knowledge Management System (LKMS) needs to select a relevant learning design (LD) strategy in order to produce a learning scenario. In this case, the author benefits from having access to the theories on which such strategies rely. In (b), we have introduced the rationale for concrete situations in the authoring process that exploit a theory-aware authoring system. In the present article, we propose an ontology of educational theories which describes these theories and their links to the LD, in order to make authoring systems theory-aware. We also discuss the question of having this ontology compliant to e-learning standards in order to provide shareable and reusable services.

Our former research was based on [START_REF] Reigeluth | Instructional Theories in Action[END_REF] for the representation of the educational theories, and on MISA [START_REF] Paquette | Instructional Engineering for Network-based Learning[END_REF] for that of the learning design process. Recently, in order to enhance and complete these representations, our work has been further inspired by the following: the Open University of the Netherlands' Educational Modeling Language (OUNL-EML) [START_REF] Koper | Modeling Units of Study from a Pedagogical Perspective[END_REF] and the IMS Learning Design [START_REF]IMS LD, CP, QTI, CD and SS Specifications[END_REF] (IMS-LD) specifications.

In section 1, we give an overview of related work and e-learning technologies standardization efforts. In section 2, we discuss the needs/requirements of authors/learning designers, and the services that an appropriate system could provide in this respect. In section 3, we propose an educational ontology which integrates LD specifications, following which we propose an OWL formalization of this ontology. We conclude in section 4 by summarizing our contribution and by listing our objectives in terms of further work.

Overview of Related Work and E-learning Technologies Standardization Efforts

In e-learning, ontologies are increasingly used to organize LD knowledge in authoring systems and LKMS [10] [11] [12] [13] [START_REF] Aroyo | EASE[END_REF]. In most cases, ontologies facilitate the referencing and the retrieval of semantically marked-up learning objects [START_REF] Recker | A non-authoritative Educational Metadata Ontology for Filtering and Recommending Learning Objects[END_REF] [START_REF] Leidig | L3 Towards an Open Learning Envir[END_REF]. The most valuable characteristics of ontologies in this respect are shareability, explicitness, and formalism.

Concurrently, recognized standard-initiating organizations have set forth the importance of sharing a common view of the educational field. In 2002, the European Committee for Standardization (CEN/ISSS) conducted a survey of educational modeling languages (EMLs) [START_REF] Rawlings | Survey of Educational Modelling Languages (EMLs)[END_REF], in which the six existing EMLs were compared. Two distinct groups seemingly emerged. The first, consisting of CDF, LMML, Targeteam, and TML, restricts itself to the modeling of learning content and structure. These languages seem to ignore the existence of pedagogical models. The second consists of PALO and OUNL-EML, and this group lives up to the survey's working definition of EML: "An EML is a semantic rich information model and binding, describing the content and process within "units of learning" from a pedagogical perspective" [START_REF] Rawlings | Survey of Educational Modelling Languages (EMLs)[END_REF]. The survey has shown that the expressive power of OUNL-EML exceeds that of PALO. The OUNL-EML [START_REF] Koper | Modeling Units of Study from a Pedagogical Perspective[END_REF] [17], now called EML, aims at providing a pedagogical meta-model. It consists of four extendable models which describe: (a) how learners learn (based on a consensus among learning theories); (b) how units of studies which are applicable in real practice are modeled, given the learning model and the instruction model; (c) the type of content and the organization of that content; and (d) the theories, principles and models of instruction as they are described in the literature or as they are conceived in the mind of practitioners. EML and its subsequent integration to IMS-LD has been to date the most important initiative towards integrating instructional design preoccupations in the international e-learning standardization effort [START_REF] Paquette | Instructional Engineering for Network-based Learning[END_REF].

IMS-LD [START_REF]IMS LD, CP, QTI, CD and SS Specifications[END_REF] takes the EML information model as its base. For binding purposes, it is made compatible with the IMS specifications: CP, QTI, CD, SS [START_REF]IMS LD, CP, QTI, CD and SS Specifications[END_REF]. The LD is positioned as the containment framework for all these specifications allowing instructional design (called "Learning Design" in IMS and henceforth in this paper) to be included into content packages. According to [START_REF]IMS LD, CP, QTI, CD and SS Specifications[END_REF] "A Learning Design is a description of a method enabling learners to attain certain learning objectives by performing certain learning activities in a certain order in the context of a certain learning environment. A learning design is based on the pedagogical principles of the designer and on specific domain and context variables". In this definition, the place of educational theories in the LD specification is not clear. As a result, however, it underlines the importance of educational theories in the LD specification, since most of existing LD tools fail to explicitly integrate educational theories.

Indeed, the current learning technologies standards and specifications mainly focus on describing knowledge about learning design and content (e.g. LOM, Dublin Core, SCORM, CANCORE), thus offering only limited support to describe knowledge of the educational theories. Consequently, authors/learning designers cannot rely on assistance stemming from theories in their learning design process. Why are LD standards so limited? It may be because of the lack of representation of this theoretical knowledge as well as the lack of a compliance mechanism between these standards and this theoretical knowledge. Such a problem has been one of the concerns of the Learning Object Repository Network (LORNET) research network in Canada. LORNET is developing an authoring environment in the form of a LKMS compliant with IMS-LD standards; we believe that such an LKMS could benefit from providing authors with access to LD theories in order to enhance the quality of their design, and to improve their expertise. "A taxonomy of pedagogies is a common request as this would enable people to search for learning designs according to the embedded pedagogy" [START_REF] Koper | Representing the Learning Design of Units of Learning[END_REF]. In order to thus make LD standards work with a representation of LD theories, a technical solution is needed.

Why linking LD Standards to a Representation of Educational Theories?

Assuming that the main user is an author/learning designer, this section introduces: the needs of an author for such a knowledge representation, the resulting services he/she can expect from an appropriate system, and how theses services can be supported through the binding of LD standards to theories. Our goal is consequently to provide services whose specific purpose would be linked to consultation of theories, eventually linking such theories to learning designs based on those theories. Some needs of the author using an authoring system, as suggested in Such a system should therefore assist an author in designing scenarios while improving expertise gained in LD. More specifically, this system should provide the following services [START_REF] Meisel | An Ontology-Based Approach to Intelligent Instructional Design Support[END_REF]: (a) Assist the author in the selection of an appropriate LD method with regards to a scenario and encourage the application of a wide range of available LD methods when requested; (b) Inform this author about a particular LD method when queried; (c) Check and highlight errors in the authoring/design of a scenario when validation is needed/required. (d) Provide relevant examples. These services can be provided through a repository of LD scenarios [START_REF] Koper | Representing the Learning Design of Units of Learning[END_REF] linked to a learning design ontology, as illustrated in Fig. 1. The LD ontology itself consequently depends on the LD theory ontology and the content domain ontology (cf. section 3 for details). Fig. 1 also shows that searching, browsing, referencing and validation services are common requests. Some of these could be directly provided by a software agent to the author (searching, browsing), while other services (referencing, validation), could be provided through an authoring system or LKMS. Table 1 shows a detailed use case of a search that might be conducted by an author indicating the type of support potentially given by the agent. Fig. 2 shows the interactions and flow of information between the agent and the author while providing those services. The possibility of using LD standards for other services [START_REF] Psyché | CIAO, an Interface Agent Prototype to facilitate the use of ontology in intelligent authoring system[END_REF] [20], is also explored. For instance, in the case of a validation service, an agent aware of the LD standards would be able to highlight errors or check the consistency of a scenario during the authoring process. This means that with a representation of the LD, an agent would be able to follow and assist the author in the process of authoring a LD scenario. This active assistance is possible only if the ontologies involved are well formalized given that the agent will need to query and reason about the elements within the ontology, which also explains why OWL is used (cf. section 4 for details). Clearly, an author would benefit from these services if the LD was linked to a representation of theories. We assume that the authoring system or LKMS used for indirect services is compliant with LD standards. On the basis of these hypotheses, we now propose how LD standards and LD theories could be connected.

Integration of LD Standards through Representation and Binding with Theories

This section describes the solution that has been developed in order to realize this integration: 1) an EML representation in the ontology, 2) a binding mechanism between LD and theories. As a preliminary to this discussion, we first elaborate on our OE methodology:

Methodology

Our methodology follows the three main steps of OE (before implementation): 1) analysis , 2) conceptualization, 3) formalization, followed by an evaluation [START_REF] Gomez-Perez | Ontology Evaluation[END_REF] and documentation of the ontology.

• Analysis of the domain. This step was done by creating a glossary of terms, and includes the following tasks: (a) Identifying each the type of each term (Class, Properties, Individuals); (b) Adding an informal description for each term; (c) Adding synonyms and acronyms if available; • Conceptualization. The conceptual modeling includes the following tasks:

(a) Creating models of classes; (b) Creating ad hoc property models. • Formalization. This step was conducted using Hozo [START_REF] Bourdeau | Potential of an Ontology-based ITS Authoring Environment: One Example[END_REF]

An Ontological Conceptualization Compliant with EML & IMSL-LD

We argued previously that LD standards have a very limited connection to theories. Because IMS-LD [START_REF]IMS LD, CP, QTI, CD and SS Specifications[END_REF] relies upon EML, we examined the EML meta-model [START_REF] Koper | Modeling Units of Study from a Pedagogical Perspective[END_REF] and how LD relates to theories in this meta-model. Fig. 3 shows that the "Unit of Study" is at its heart and relates to theories, to content domain and to learning models. In our view, ontologies could try to match this structure and we thus propose a structure consisting of three ontologies (Fig. 4), in which the "Learning Design Ontology" corresponds to the "Unit of study" and includes the "Learning Model", while relating to the two other ontologies, the "Learning Design Theories", and the "Content Domain" Ontology. This conceptualization builds upon the ontology of theories presented in [START_REF] Psyché | Ontology Development at the Conceptual Level for Theory-Aware ITS Authoring Systems[END_REF], and takes into account the classes proposed by EML [START_REF] Koper | Modeling Units of Study from a Pedagogical Perspective[END_REF] and extracted from [START_REF] Greeno | Cognition and Learning[END_REF]. Classes for theories in EML are paradigm-based: "behaviourism", "rationalism", and "pragmatism-sociohistoricism".

Table 2. Classes and Properties of the Ontology of Educational Theories

Classes

• Theory: theory of knowledge, learning theory, theory of instruction, ID theory;

• Paradigm: Behaviourism, Rationalism, Pragmatism-Sociohistoricism (EML);

• Learning Theory: Piaget, Bruner, Vytgosky, other;

• Theory of Instruction: Inquiry teaching, Socratic, Algo-Heuristic, other;

• Instructional Design Theory: Component Display, Elaboration, other;

Properties • A theory of knowledge has a paradigm as one of its parts;

• A theory of learning, instruction, and instructional design has a paradigm as an attribute;

• A theory of learning, instruction, and instructional design has the following parts:

o theorist, concepts, principles, paradigm, content domain, reference, date; • Theories of learning, instruction, and instructional design rely on a theory of knowledge;

• Models issued from a theory are extracted from a theory; • Models emerging from practice (eclectic) are extracted from practice;

• Learning Designs are inspired by models.

It appears that these classes correspond, in our ontology, both to the theory of knowledge on which each theory of learning relies, and to the main paradigms identified, although the names sometimes differ [START_REF] Ertmer | Behaviorism, cognitivism, constructivism[END_REF] [24] [START_REF] Kearsley | Explorations in Learning & Instruction: The Theory Into Practice Database[END_REF]. Although these classes should allow for classifying all theories of learning, instruction and instructional design, EML adds another class, called "eclectic", for learning design models that have emerged from practice as opposed to being based on theory. This "other" class has therefore been added to our ontology. Table 2 shows the classes and properties which consequently were obtained as a result of the conceptualization. As a result Fig. 5 shows an UML representation of the theories which binds with the IMS-LD. The main entities of the ontology (theory, paradigm, model, domain and LD) are in grey. 2 illustrates examples of how we conceive the binding mechanism between LD and educational theories.

Formalizing and Implementing the Ontology for Agent Use

The software agent receives a LD scenario description and retrieves a selection of matching theories available on a web-based knowledge base using a set of emerging standards (RFD-S, OWL) and tools (Hozo, Jena2). To achieve this goal, a formalization (level 2 in [START_REF] Mizoguchi | A Step Towards Ontological Engineering[END_REF]) followed by an implementation (level 3 in [START_REF] Mizoguchi | A Step Towards Ontological Engineering[END_REF]) of the ontology was necessary.

The formalization was done in OWL (Web Ontology Language) using the Hozo ontology editor. OWL is designed for use by applications that need to process information in addition to displaying information to humans. In comparison to XML, RDF, and RDF Schema (RDF-S), it facilitates better machine interpretability of Web content since it provides additional vocabulary along with a formal semantics. OWL has three increasingly-expressive sublanguages: OWL Lite, OWL DL, and OWL Full [START_REF]OWL Specification Development[END_REF]. Our formalization was conducted using OWL DL. The Hozo editor allows for the creation of classes and properties, in addition to a graphic representation of the ontology, the hierarchy of classes and the properties. It also generates the OWL code as shown in Fig. 6 (right window). A subsequent ontology implementation using Jena2 is in progress. Jena2, developed by Hewlett-Packard, is a Java framework for programming Semantic Web applications. It includes useful features, including an ontology API, a reasoning system, a query language (RDQL). The ontology API offers support for the implementation of the above-formalized ontologies (RDFS, OWL) into JAVA classes. The reasoning system, an inference engine, together with rule sets for RDFS / OWL, works with the ontology API in order to infer additional facts from a particular ontology source. RDQL offers support for querying a networked knowledge base consisting of the above elements, and allows the agent to query the ontology of theories about elements of LD scenario specified by the author.

Conclusion

In merging LD standards with an ontology of theories to serve the needs of authors working within an authoring system or a LKMS, we found that IMS-LD cannot link the learning design with instructional design theories. We developed a solution that integrates LD in a structure of ontologies, and allows for communication between LD and theories. We described the ontology of theories with its classes and properties. A first version has been formalized in OWL using the Hozo ontology editor. This work needs to be further developed to provide the services expected by its users. The ontology also needs to be merged with the ontology of the three instructional models (Gagne-Briggs, Merrill and Collins) that has been previously developed [START_REF] Psyché | Ontology Development at the Conceptual Level for Theory-Aware ITS Authoring Systems[END_REF]. Furthermore, a deeper integration of LD standards is envisaged within an ontology of LD. The agent will be implemented according to JAVA standards. At this point, our work will be interfaced with the LKMS developed by LORNET. Both an evaluation of the ontology and of the services provided by the agent are foreseen. The evaluation of the ontology itself then follows criteria and guidelines by [START_REF] Gomez-Perez | Ontology Evaluation[END_REF]. The services provided by the agent to a learning designer in the process of authoring using an IMS-LD compliant tool will be evaluated in the following way: a mockup will represent the interactions between the agent and the human author, in the context of a real task. Three LD experts will judge the services' relevance, usefulness and meaningfulness.

  [START_REF] Bourdeau | Potential of an Ontology-based ITS Authoring Environment: One Example[END_REF] [START_REF] Nkambou | Authoring Tool for Knowledge Engineering in ITS[END_REF], are the following: (a) Query about which theories apply best to a specific LD, or about design principles related to theories; (b) Extract, (re)view and browse among theories in order to select LD strategies, or among templates of LD scenarios; (c) Review examples of good LD scenarios or principles in order to design a LD scenario; (d) Reuse or modify a template of LD scenario; (e) Validate (check consistency) among design principles.

Figure 1 .

 1 Figure 1. Main Use Cases and Provided Services

Figure 2 .

 2 Figure 2. Interactions between Agent and Author during Authoring Process

Figure 3 . 4 .

 34 Figure 3. The EML meta-model Figure 4. The resulting ontologies

Figure 5 .

 5 Figure 5. A UML representation of the ontology of theories What theories are mapped to the LD, and how? Table2illustrates examples of how we conceive the binding mechanism between LD and educational theories.

Figure 6 .

 6 Figure 6. Formalization of the Ontology of Educational Theories in Hozo

Table 1 .Example of a Service: Searching a Theory Use Case Goal Perform a search to find a suitable theory Success End Condition The

 1

	The author searches for
	appropriate theories for
	sequencing instruction that
	would map an LD activity
	structure in a particular LD
	scenario.	5	Author selects a theory item in the list

suitable theory is found and provided by an agent.

Failed End Condition

No input from the author or no matching theory.

Primary Actor

User: Author / Learning Designer DESCRIPTION

Step Branching Action 1

Author: wants to select a given type of instructional activity 2 Ontology Agent: consults the ontology 3

Ontology Agent: performs queries as to which theories could map the learning design activity 4

Ontology Agent: outputs a list of suitable theories from the ontology

  This is an iterative process, which stops once the ontology is stabilized. Finally; (f) Add individuals.• Evaluation. This step[START_REF] Gomez-Perez | Ontology Evaluation[END_REF] is performed during the conceptualization and formalization steps: (a) Verification: check (assisted by the editor) if the ontology is syntactically correct. (b)Validation: make sure (with domain experts) that the ontology correctly models the real world (domain) for which it was created. • Documentation. At this stage, we document the ontology using OWL terminology:(a) Creating a dictionary of classes. For each class, indicate the: identifier, equivalent class, super and sub-classes, individuals, class property; (b) Creating a dictionary of properties. For each property, indicate the: name, type, domain, range, characteristics, restrictions; (c) Creating a dictionary of class axioms: indicate boolean combinations; (d) Creating a dictionary of individuals. For each individual, indicate the: individual name, type name, ObjectPropertyValue, DataPropertyValue.

. For each class: (a) Add the subclasses in order to create taxonomies of classes; (b) Add predefined properties; (c) Add ad hoc properties; (d) Add comments (or annotations) if necessary; (e) Add axioms if necessary.

Table 3 .

 3 An Excerpt of the Binding Mechanism

IMS-LD Element Binding by Properties Matching Classes (C) /Instances (I) of Theory Method Type of Paradigm:

Acknowledgments

Thanks to Ophélie Tremblay, Michel Leonard, Karin Lundgren, Ioan Rosca, Olga Marino and Gilbert Paquette (LICEF), and to Danièle Allard (Mizoguchi Lab.), for their advice or feedback. Financial support was provided by the Canadian National Science and Engineering Research Council, the LICEF Research Center and GDAC Research Lab.