Nicolas Balacheff

TREATMENT OF REFUTATIONS: ASPECTS OF THE COMPLEXITY OF A CONSTRUCTIVIST APPROACH TO MATHEMATICS LEARNING

INTRODUCTION

One of the basic hypotheses of research in mathematics education, one being widely considered at the present time, is the constructivist hypothesis which asserts that the subject explores actively its environment that he or she participates actively in the creation of space, time and causality (Inhelder and Caprona, 1985 p.8). Following this hypothesis, we can see that the student himself participates actively in the construction of his own mathematical knowledge. The starting point for the developmental process according to this view, is the experience of a contradiction which is likely to provoke a cognitive disequilibrium: It is the overcoming of such a contradiction which results in new constructions (Piaget, 1975).

I would like to emphasize here the consistency of this Piagetian developmental model with the model proposed by Lakatos to describe the growth of mathematical knowledge through the dialectic of proofs and refutations. "Informal, quasi-impirical, mathematics does not grow through a monotonous increase of the number of undubitably established theorems but through the incessant improvement of guesses by speculation and criticism, by the logic of proofs and refutations" (Lakatos 1976, p.5). But what Lakatos work shows is the complexity of the overcoming of a contradiction in mathematics due to the diversity of the possible ways of dealing with a refutation, its possible treatment. The historical study presented by Lakatos shows the importance of the social dimension of this dialectic. This dimension also plays an essential role in the learning process taking place in the mathematics classroom. It appears at two levels:

(i) Students have to learn mathematics as social knowledge; they are not free to choose the meanings they construct. These meanings must not only be efficient in solving problems, but they must also be coherent with those socially recognized. This condition is necessary for the future participation of students as adults in social activities.

(ii) After the first few steps, mathematics can no longer be learned by means of interactions with a physical environment, but requires the confrontation of the student's cognitive model with that of other students or of the teacher, in the context of a given mathematical activity. Especially in dealing with refutations, the relevance of overcoming is what is at stake in the confrontation of two students' understandings of a problem and its mathematical content.

I have studied the complexity of students' treatment of a refutation by means of an experimental approach within the context of solving a given mathematical problem. My analysis of the data collected takes into account both the cognitive and social dimensions of the phenomena observed. Before presenting this study and its results, I would like to explain the main features of the theoretical framework I adopted.

THE PROBLEM OF CONTRADICTION CONDITIONS FOR THE AWARENESS OF A CONTRADICTION

Following Grize (1983), I consider that a contradiction exists only if it has a witness. That means that a contradiction does not exist by itself, but only with reference to a cognitive system. For instance, a contradiction could be recognised by the teacher in the mathematics classroom, but ignored by students. Here is an example: In a research study about students' conceptions of the convergence of numerical sequences, Robert (1982) reports the following reasoning: Having shown that a numerical sequence (u n ) has a limit λ such that λ<1, some students make the following computation: Lim (u n n+1 + u n n + u n 2 + u n + 1) = lim (u n 2 + u n + 1) = λ 2 + λ + 1

They treat n in two different ways according to whether it appears as a suffix or as an exponent.

In this example the students are not aware of the contradiction which results from the two different treatments of n, whereas it is quite obvious to us.

But, on the other hand, a contradiction could exist for the learner where none exists for the teacher, for example (Balacheff, 1988):

Students of the seventh grade see a contradiction in the fact that the sum of the angles of a triangle does not depend on its size (although area or perimeter do).

In all these examples, the fact that a contradiction is elicited or not depends basically on the knowledge of the one who claims that a contradiction exists or does not.

In the teaching situation, the existence of a referent knowledge (the scientific knowledge or the knowledge to be taught) gives the right to the teacher to decide whether a fact is contradictory or not with respect to this knowledge. The problem for the teacher, then, is to make the student recognise the contradiction he or she alone sees. The didactical question thus becomes twofold: First, what are the conditions necessary to engender, on the part of the student, awareness of a contradiction and, second, what are the conditions under which the student can resolve it.

According to Piaget (1974, p.161) the awareness of a contradiction is only possible at the level at which the subject becomes able to overcome it. I would like to emphasize that, to the extent that such an overcoming is likely to imply a real re-organisation of the subject's knowledge, this condition appears too strong to us. I will not ask for such a potential overcoming of contradictions, but merely that they be seen. Actually, to become aware of a contradiction means to become able to raise the question of the choice between two propositions: an assertion and its negation. Whatever the choice, it implies that the formulation of the assertion is available and that the subject can construct and express its negation.

Thus, consciousness of a contradiction depends on two constructions, and the subject can only be aware of it when he becomes able to carry out these two constructions. But even when a contradiction has been identified, overcoming it might only be possible after a long process. For example, in the case of the sum of the angles of a triangle, overcoming the contradiction I have mentioned above, needs the construction of an invariant, and finally the conceptualization of the Euclidean Postulate and its consequences. That is to say, to construct the relation between the assertion "the sum of the angles of a triangle is 180°" and the assertion "the bigger the triangle, the larger is the sum of its angles", even if it provides access to the problem of the contradiction, is not by itself sufficient to allow it to be overcome.

On the other hand, a contradiction exists only with reference to a disappointed expectation, or with reference to a refuted conjecture. The potential existence of an assertion is not sufficient, to use a metaphor of Taine 1 , it is necessary that it comes to the forefront of the scene. Piaget himself remarks that to become aware of a contradiction is far easier when it appears between an expectation and an external event which contradicts it (ibid). Here Piaget goes beyond the cognitive conditions and takes into account conditions related to the situation within which the subject acts. The existence of such an expectation means that the subject is actually committed to an assertion and is able to sidestep its action. In other words, he or she is able to consider it as a possible object of thinking, even more, an object of discourse. At that point, action is no longer just carried out. Being the product of a choice, it is considered in terms of its validity and the adequateness of its effect. That is to say, action is then related to its aim and a contradiction becomes apparent when this aim is not fulfilled. The choice which has been made and the conditions under which the action has been performed are then put in doubt.

I would like then to state the following conditions as being necessary conditions for the emergence of the awareness of a contradiction:

(i) The existence of an expectation or an anticipation; (ii) The possibility to construct and formulate an assertion related to this expectation, and the possibility to state its negation.

TREATMENT OF REFUTATIONS

A counterexample in the mathematics classroom is often understood as a sort of catastrophe because it implies the definitive rejection of what has been refuted. From this point of view, the mathematics classroom ideology is more Manichaean than dialectic. An analysis of the mathematician's activity shows quite a functioning quite a different and much less radical procedure.

Taking as a basis the model proposed by Lakatos (1976), we can differentiate the implications of a counterexample depending on whether what is considered is the conjecture, its proof 2 , or the related knowledge and the rationality of the problem-solver himself.

1 Quoted by Hadamard (1959, p.34).

2 By "proof" we mean a discourse whose aim is to establish the truth of a conjecture (in French: Preuve), not necessarily a mathematical proof (in French: Démonstration).

Figure 1

The schema3 (fig. 1), showing the conjecture and its proof as the product of both the knowledge and the rationality of a subject, summarizes the main possible consequences of a counterexample. Of course, the conjecture could be rejected, but other issues are possible. For example: To inspect carefully the proof in order to elicit a possible suspect lemma and then to incorporate it as a condition in the statement of the conjecture, or to question the rational of the proof or the underlying knowledge, or even to dismiss the counterexample as a monster. Also, such a process is likely to provoke an evolution of the knowledge related to the proof, resulting in what Lakatos called as a proof-generated concept (Lakatos 1976, p.88 sqq.).

The analysis Lakatos (1976) provides of the development of mathematical knowledge leaves out a question that is essential for the teacher and the educational researcher: What determines the relevance of a choice for overcoming the contradiction brought forth by a counterexample? It is this question that I have investigated by means of an experimental study I will now present.

STUDENTS' TREATMENT OF A COUNTEREXAMPLE THE EXPERIMENTAL SETTING A SOCIAL INTERACTION ABOUT THE NUMBER OF DIAGONALS OF A POLYGON

In order to explore the students' behavior when faced with a counterexample, I have used a situation involving social interactions which encouraged the confrontation of different viewpoints about the solution of the problem, and hence, a verbal exchange making explicit the possible refutations, how to deal with them and thus the proving process underlying the solutions proposed by the students.

Pairs of 13-14 year-old students were required to solve the following problem: Give a way of calculating the number of diagonals of a polygon once the number of its vertices is known. The answer to this question was to be expressed in a message addressed to and to be used by other 13-14 year-old students.

Observations, which began in 1981, were carried out mainly during the first semester of 1982. Fourteen pairs were observed for 80-120 minutes4 .

In the experimental setting the communication with "other 13-14 year-old students" is only invoked5 , but it does not actually take place. Nevertheless, this invoked communication structures the students pairs' activity, and more particularly it solicits a verbal formulation of the counting procedure. This is something that students do not normally do straightway even if they are technically capable of it. At the same time, the desire to supply the "other 13-14 year-old students" with a reliable technique is likely to make the students pair to pay more attention to its formulation.

Lastly, the two students have access to as much paper as they want, but, on the other hand, to only one pencil. This constraint reinforces the co-operative nature of the situation, while at the same time giving us more direct access to the dynamic of the two confronted knowledge systems, especially in cases of decision making.

The observer intervenes only after the students have claimed that they have produced a final solution. At this stage he abandons his stance of neutrality and asks the students to deal with counterexamples that he offers. Thus there are two different phases during the observation, one quasi-independent of the observer and the other with a strong observer-student interaction.

THE FIELD OF KNOWLEDGE

The problem I selected calls on students' knowledge that is cultural rather than scholastic, insofar as that, polygons may have been studied in the primary school in the context of geometrical classification, but they are no longer, for these students, a part of the taught curriculum. Sometimes they are mentioned before passing rapidly on to the study of triangles and quadrilaterals. Diagonals, however, figure in the curriculum, as they play an essential role in the study of the parallelogram.

As in the case of the solids in the 18th century6 , students' conceptions of the mathematical content involved do not constitute a theory. In order to solve the problem, students may have to specify the objects to which it is related. In other words, to develop definitions for polygon and diagonal is part of their task.

This experimental study creates a context which is favourable for the emergence of processes like those describe by Lakatos, and thus for the examination of the relevance of his approach for an analysis of students' behaviors when confronted with counterexamples to a conjecture they have produced.

STUDENTS' SOLUTIONS AND THEIR FOUNDATION

The observed problem-solving procedures are closely linked to the meaning students give to the "objects" polygon and diagonal. Particular, the interpretation regular polygon for "polygon", and diameter for "diagonal" leads students to the conjecture f(n)=n/2 7 . Three types of solution have been proposed which «effectively» provide the required number of diagonals. They are:

f(n) = f(n-1) + (n-2) f(n) = (n-3) + (n-3) + (n-4) + … + 2 + 1 f(n) = (n.(n-3))/2
The rational basis for these conjectures are more often than not empirical. But even so, the nature of the underlying proving process can vary considerably from one solution to another (cf. Table I).

Types of proofs 8

Pairs

Naïve empiricism

Crucial experiment

Generic example

Thought experiment

Proof by «reasons»

Lio-Lau Pie-Phi Naï-Val Pie-Mat f(n)=n f(n)=n. s(n) f(n) =n/2 f(n)=n Nad-Eli f(n) function of f(n-1) P 10 Géo-Oli Mar-Lau f(n)=2f(n-1)
Oli P 14 Lau P 10

(n-3)+… , on P 6 (n-3)+… , on P 6 Eve-Chri Bla-Isa Lyd-Mar

Ber-chr Oli-Sté f(n)=n/2 --------------------------------------------------------------> f(n)=n/2 f(n)=n-3, sur P 7 f(n)=n/2 or n-1/2(*) Lyd : f(n)=n/2 no formula for concave ones Chr : f(n)=2n Chr P 8 Ber : f(n)=n(n-3)/2 ----------> Sté P 8 (n-3)+… , s(n)=n-3 ----------------> on P 8 Ant-Dam Ham-Fab f ( n ) = n / 2 f(n)=n 2
(*) using a generic example, but just as a linguistic means. TABLE 1 7 "f" is the name we will use for the function which relates the number n of vertices of a polygon to the number of its diagonals. 8 P n stands for "a polygon with n vertices".

Commentary:

-In the column "crucial experiment" I have indicated the polygon on which this experiment is performed; in the column "generic example" I have indicated the polygon chosen by the students as being generic; -This table does not take account of any chronology, except when an arrow expresses a change in the level of validation for a given conjecture. Naïve empiricism and generic example are dominant. The analysis of the students' dialogue shows that the lack of an operative linguistic means is one of the major reasons for the absence of proofs at a higher level. For example, use of a generic example indicates the willingness of the students to establish their solution in all its generality, but this willingness is hampered by the absence of an efficient linguistic tool to express the objects involved in the problem-solving process and their relationships.

I must emphasize that this complexity is not only linguistic but has also cognitive origins, that is the complexity of the recognition and the elicitation of the concepts needed for the proof. Linguistic constructions and cognitive constructions are dialectically related during the problem-solving process. Let us take the example of f(n)=(n-3)+(n-3)+(n-4)+…+2+1. In this case, students have to express an iterative process and to control it (number of steps, ending of the computation), but at their level of schooling they do not have the conceptual tools needed. To them, the use of a generic example seems the best means to «show» the computation procedure and to justify it. Some of the students mention the need for a mathematical proof, but they do not try to produce one. In fact they stay at a level of proving which is consistent, on the one hand, with their level of uncertainty and what they think is needed by the situational context, and on the other hand, with the cognitive and linguistic constructions they are able to perform (Fischbein, 1982; Balacheff, 1987b).

The social interaction played a fundamental role. In few cases was it an obstacle to reaching a higher level of proof. Especially when the conflict between two students was too strong and «too social», all means seem to be good to them as an argument, even naïve empiricism 9 . But in most cases this social interaction has been the real «engine» which leads the students to an awareness of the need for proofs, forcing them to justify themselves or to elicit the rationality of the decision to be taken. 9 By naive empiricism we mean the situation in which the problem-solver draws the conjecture from the observation of a small number of cases (for example that f(n)=n because P 5 has 5 diagonals). We use the expression crucial experiment when the problem-solver verifies the conjecture on an instance which "doesn't come for free", here the problem of generality is explicitly posed. The generic example involves making explicit the reasons for the truth of the conjecture by means of actions on an object which is not there in its own right, but as a characteristic representative of its class. The thought experiment invokes action by internalising it and detaching itself from a particular representation. (For a precise definition of the different types of proofs, see: Balacheff, 1987a and 1988.) THE TREATMENT OF COUNTEREXAMPLES Most types of treatment of a refutation as described by Lakatos, have been observed. One of the main differences is that in some cases we have to make a distinction between the treatments which follow an analysis on the part of the problem-solver, and those which are merely ad hoc treatment of the conjecture in order to save it in any case.

Tables II andIII give an account of the frequency of each type of treatment in each of the two phases of the experiment. In Table I only 10 student pairs appear out of the 14. The reasons why 4 of them are not mentioned are the following:

-Two pairs proposed at once a correct solution with reference to their conception of polygon and diagonal. Their conviction kept them beyond questions (Martine and Laura, Lionel and Laurent).

-One pair did not take any decision about a refutation they met; they asked for advice from the observer (Naïma and Valérie).

-One pair did not identify any counterexample during their problem-solving process. These tables show important differences between "phase I" and "phase II", but these differences are not the only ones one can possibly foresee a priori.

It is in phase I that rejection of the conjecture is dominant, and not in phase II in which one might have expected that a counterexample proposed by the observer would provoke a rejection of the conjecture. On the other hand, the rejection of the counterexample is dominant in the phase II as well as its being treated as an exception. Two explanations can be proposed for this phenomenon:

-The rejection of the conjecture appears in the case of very fragile ones which are verified in only one case: f(n)=n (verified by P 5 ), f(n)=2.n (verified by P 7 ), f(n)=n 2 (verified by no polygon, but conjectured by Hamdi and Fabrice…).

-The rejection of the counterexample happens when it is opposed by a strong conjecture whether or not it is strongly established (with respect to the conceptions of the students) or correct. In the case of Lydie and Marie, the information given is in brackets because these two students did not succeed in reaching agreement about how to treat the counterexample proposed by the observer. Lydie wanted to introduce a condition while Marie wanted to the reject the conjecture and then to search for a new solution.

In the following I will present some details of the categories of treatment of a refutation. Samples of the students' behavior will be given to help the reader make sense of them.

REJECTION OF THE CONJECTURE

The analysis of this type of response to a counterexample involves two different behaviors:

-The immediate rejection of the conjecture, as soon as the counterexample has been produced. This decision is more often than not taken following a naïve empiricism. This behavior is coherent insofar as the observation of few a polygons was sufficient to construct the conjecture, one counterexample is sufficient to dismiss it.

Christophe defends the conjecture f(n)=2n, deduced from observation of P 7 . Bertrand refutes it by P 8 . In the conflict between the two students, this refutation is considered by Christophe as a crucial experiment; he then rejects his conjecture.

Lionel and Laurent defend the conjecture f(n)=n, deduced from observation of P 5 . When the observer proposes P 6 they surrender: "So, we were wrong" (Lau. 204) 10 ; they then proceed towards a new solution.

Hamdi and Fabrice defend the conjecture f(n)=n 2 , not from the observation of some polygons, but directly from their conception of what a diagonal consists of. When the observer proposes the counterexample P 5 , they reject their conjecture and start their search for a solution again.

-The rejection of the conjecture after an analysis of the possible origin of its refutation. This analysis provides students with new elements to restart the search for a solution to the problem:

Blandine and Elisabeth defend the conjecture f(n)=n/2; its refutation by P 9 leads them to an analysis which reveals that when they draw the diagonals joining the vertices two by two one vertex is left. They then modify their conception of diagonal and give up their conjecture.

Georges and Olivier defend the conjecture 11 f(n)=n.s(n). Its refutation by P 7 leads them to its modification into f(n)=n/2.s(n), but they give it up because it appears to be impossible to divide 7 by 2. Afterwards they keep as a guide line for the search for a new conjecture, the fact that no diagonal should be counted twice.

Lionel and Laurent, whose conjecture f(n)=n.(n-3)/2 is refuted by the observer by means of a polygon P 5 with three aligned vertices (fig. 2), keep their initial conjecture for the convex polygons and propose f(n)=(n(n-3)/2)-1 for the others. Exploring this new conjecture, they notice that it is no longer correct for any non-convex polygons, in fact "it depends on the shape" (Lau 970). Then they give up this new conjecture. 10 "Lau 204" is a reference to the protocol of this pair of pupils, it means "Laurent is speaking, action N° 204". 11 Here "s" is the name of the function which associates with the number n of the vertices of a polygon, the number s(n) of its diagonals at one vertex. That means that pupils have recognized the invariance of the number of diagonals belonging to each vertex of the polygon.

MODIFICATION OF THE CONJECTURE

The modification of the conjecture when faced with a refutation appears to be equally possible in both the phases of the experiment12 . Three main types of such a treatment can be distinguished:

-The ad hoc modification which consists in a direct adaptation of the conjecture to superficial features, observed by the students, of the relations between the result expected and the one indicated by the counterexample. The origin of the new conjecture is related to the observation of one case only, thus it has a naïve empiricist foundation:

Lionel and Laurent conjecture f(n)=n.(n-3) as a solution. It is refuted by P 5 ; they then conclude that the solution should be f(n)=(n.(n-3))/2 and they validate it by means of a crucial experiment on P 7 . No analysis is done about the possible reasons for this division by 2, it comes from the relation they establish between the result of the counting on P 5 and what they expected. Their dialogue shows this: "Why would you like to divide by 2 ? They will not understand." (Lio 396) "We must divide by two because… with 4, it works and with 5 also, and with 6 also… " (Lau 399) -The modification which follows an analysis of the sources of the refutation with reference to the foundation of the conjecture:

Bertrand and Christophe conjecture f(n)=n.(n-3); they meet the counterexample P 7 . Then, trying to find the reasons why this polygon does not fit the formula, Bertrand discovers that "the diagonal AF, that is also the diagonal FA" (Ber 287). Then they propose to modify the formula into f(n)=(n.(n-3))/2, because "otherwise some diagonal would be counted twice" (Ber 384), thus "that means to divide by two" (Chr 403).

Georges and Olivier conjecture f(n)=n.s(n) after having observed that the number of diagonals is the same at each vertex of a polygon. Their analysis after a refutation by P 5 leads them towards the conclusion that "they [the diagonals] appear again after… " (Geo 198), and they consider the new conjecture f

(n)=[n/2].s(n).
-The modifications which consists of reducing the domain of validity of the initial conjecture to a set of objects which excludes the counterexample, and in constructing a solution specific to the objects the class of which the counterexample is considered a good representative:

Blandine and Isabelle conjecture f(n)=n/2; after its refutation by polygons having an odd number of vertices they search for a solution for this category of objects. They finally conjecture f(n)=n/2 for «even polygons» and f(n)=(n-1)/2 for «odd polygons».

Evelyne and Christine conjecture f(n)=n/2, paying no attention to polygons with an odd number of vertices. After the refutation by the observer, who produces P 5 , they reduce their solution to the polygons with an even number of vertices. For the odd polygons they propose f(n)=n… Nadine and Elisabeth conjecture, following a crucial experiment, that f(n+1)=f(n)+a(n+1) 13 . The observer proposes as a counterexample a polygon P 5 with three vertices which are aligned (fig. 2); they then try to find a solution for this kind of polygon: "The one which has a vertex inside" (Nad 175). But they find that the solution they envisage is strongly related to the shape of the polygon, finally they surrender.

THE COUNTEREXAMPLE CONSIDERED AS AN EXCEPTION

This type of treatment of a counterexample is quite seldom. It appears just once in the first phase of the experiment. A possible explanation could be the belief that a mathematical assertion must not suffer any exception:

When faced with a triangle produced by the observer as a counterexample to their conjecture, Blandine and Isabelle decide that it should be considered an exception because "it has no diagonals" (Isa 184).

Georges and Olivier take the same decision, deciding that their conjecture is valid "from 4… because triangles are particular cases" (Geo 508). When faced with a polygon P5, three vertices of which are aligned, they state that "it is again a particular case" (Oli 590), but "that's a lot of exceptions" (Oli 625). They are not really very confident: "Perhaps it is the good solution, even if there are a lot of exceptions" (Oli 645). Then they try to find a specific solution for these cases. Failing to do so, they finally keep on with the decision to consider these counterexamples as exceptions.

When Hamdi and Fabrice conjecture f(n)=n 2 as a solution; they envisage the case of the triangle but "any polygon should not have zero diagonals" (Ham 222). When the observer proposes the case of P 4 they claim again that "it is a particular case" (Fab 279), and they confirm their initial solution but "except the particular cases… triangles and equilaterals" (Ham 389). They continue to consider these polygons as exceptions, even when they propose the solution f(n)=(n.(n-3))/2 for which it is no longer the case.

INTRODUCTION OF A CONDITION

The decision to introduce a condition in the statement of the conjecture follows two types of strategies:

-Some students try to find a condition by means of an analysis of the counterexample to bear down the class of objects of which it is a representative:

Hamdi and Fabrice introduce a condition in order to brush aside the objects represented by the counterexample the observer proposes to them (fig. 3 Naïma and Valérie protect their conjecture against the counterexamples produced by the observer, adding ad hoc conditions: "all the edges should be of the same size", "the edges should be on a circle", "to a vertex belongs only one line". This strategy is absolutely resolute "I don't mind, I answer with conditions" (Val 504).

-Some students try to find a condition by means of an analysis of the refuted conjecture and its foundations:

Blandine and Isabelle decide to introduce a condition against non-convex polygons, one of them having been produced by the observer as a counterexample, because "the diagonals should be inside, as they should intersect just once" (Isa 206). They then decide that the polygons to which the conjecture applies must be convex.

Olivier and Stéphane conjecture that the larger the number of vertices of a polygon, the larger is the number of its diagonals. That happens to be refuted by a polygon P 7 which has some vertices on the same line. The students analyse the origin of this refutation and introduce a condition: "We have to say that it works if the points are not on the same line" (Sté 77).

The decision to introduce a condition seemed "not allowed" to some students, because of the experimental contract 14 . For example, the conjecture f(n)=n/2 having been refuted, Evelyne proposes to introduce a condition on the number of vertices of a polygon: "It is always divided by two… so the number should be even"(Eve 85). But the students finally do not introduce this condition, because no restrictions on the type of polygon have been stated in the text of the problem: "It might not be so, because there [in the text of the problem] it is not said that the polygon has… that the number of vertices is even" (Eve 140).

THE DEFINITION REVISITED

Most of the students posing the problem of what a polygon is, or trying to elicit a definition of polygon or diagonal, are those whose conjecture is f(n)=n/2 (6 cases of the 9 observed). Their uncertainty about what a polygon is is noticeable from the very beginning of the experiment, but it is only after a refutation that some of them clearly state this problem of definition:

The doubt about what a polygon could be urges Antoine and Damien to pose the problem of its definition: "It could take a long time if we search like that… if we have not the exact data" (Dam 77). Taking P 8 as a prototype, they put aside the odd polygons: "It cannot be an odd number as far as we say that the edges should be parallel two by two" (Dam 221). Actually this problem turns into being part of the «game»: "the rule tells that we are the teacher… We tell him [the observer] a polygon is what we have given, and he should find whether our definition is correct or not" (Ant 383).

Blandine and Isabelle straight away pose the problem of the definition of polygon and diagonal. A first counterexample they encounter against their conjecture (f(n)=n/2) leads them to the following statement: "it [a diagonal] joins two vertices" (Bla 18). Later a new conjecture having been formulated (f(n)=n.(n-3)) and then refuted by P 7 , they refine their definition: "to each vertex belongs one diagonal" (Isa 70). Relying upon that definition, they return to their initial conjecture which they now hold quite strongly.

Naïma and Valérie conjecture f(n)=n/2, after the refutation by the observer they state that "it is perhaps necessary to know the definition of polygon" (Val 285). In fact, they come to the idea that the problem is basically a problem of definition and, after having stated a definition, they modify it to cope with the 14 The relationships between the actors involved in the situation (the two pupils and the observer) are determined by rules which are both explicit (like what is said about the task), and implicit (like those suggested by the aim of the experiment). All these rules constitute what we call the «experimental contract» (Balacheff and Laborde, 1985). counterexamples produced by the observer. But they recognise that the definition they propose is "what we think" (Naï 444). This focus on the problem of definition could be related to the wish "to find something valid for all polygons" (Naï 353).

REJECTION OF THE COUNTEREXAMPLE

This way of treating a counterexample is the most widely distributed among the observations I have made. It appears at least once in each of 11 pairs out of the 14 observed. On the other hand, its presence is more frequent in phase II of my experiment during which the students were perhaps more eager to defend their conjecture against refutation by the observer. But not all these reactions should be considered the same.

Three main categories can be differentiated:

-The counterexample is rejected after an analysis which reveals that actually it does not refute the conjecture: It is shown that the refutation is made on the ground of a misinterpretation. The possibility of such an analysis was opened by the case of a polygon P 5 with three aligned vertices, proposed by the observer15 :

Bertrand and Christophe discover the hidden diagonal in the drawing by the observer of a polygon P 5 with three aligned vertices. They suggest that it might be good to inform the recipients of their message of such a possible event. When faced with a new counterexample produced by the observer, a polygon P 4 with edges crossing elsewhere than the vertices, they make an attempt to show the same misinterpretation on the part of the observer. They fail in doing so… -The counterexample is rejected with reference to a precise conception of what is a polygon: Conception which may have been formulated previously as a definition: Pierre and Mathieu, who have conjectured f(n)=n/2, reject a convex polygon P 5 , because it appears not to be regular: "The edges are not exactly equal" (Mat 63). About the same polygon Mathieu even suggests that "maybe a polygon with 5 edges doesn't exist" (Mat 135). Actually the difficulties with this counterexample will be overcome later while revisiting the definition of diagonal. ), analysing them as joint figures but not real polygons: "That's not a polygon" (Oli 768) "Wait… a polygon is a thing… here it's not a polygon… they are two triangles… [to the observer] Is that a polygon ? " (Sté 769). Actually, in order to reject the counterexample the students have to raise the problem of the definition of a polygon: "To a point it must be related to no more than two other points" (Sté 382) -The last category is the one Lakatos named «monster-barring», the counterexample is in this case rejected by students without any further considerations about the definition or any debate about their conceptions. It is, in particular, the case for the triangle because of its lack of diagonals.

Evelyne and Christine reject the triangle as a counterexample to their conjecture f(n)=n/2 because "the triangle has no diagonal" (Chr 113). Later on, the triangle being met again, they reject it definitely and explicitly: "the triangle is not a polygon" (Chr 473).

Hamdi and Fabrice reject the triangle despite the fact that the observer has shown that it fits their latest conjecture. Since it was a real counterexample to a previous conjecture, they do not want to consider it again and "whatever it is, in a triangle there are no diagonals… so we are not interested" (Fab 553).

STRATEGIES IN THE TREATMENT OF A COUNTEREXAMPLE: STABILITY AND DISPERSION

When the number of counterexamples met by a pair of students is large, it is of interest to examine their global strategy and the distribution of the type of treatments they have chosen. With respect to this question two types of categories should be recognised:

-Stability of treatment: Few different types of treatment are used by the students. The origin of this stability, which has been observed in three pairs, is quite different from one case to another: In the case of Bertrand and Christophe, or Olivier and Stéphane, it is due to the success of the first decision they took about a counterexample; in the case of Naïma and Valérie it is a consequence of their commitment in a «definition game»16 .

-The diversity in the treatment of the counterexamples cannot be characterized in few words; I give an account of the pairs which appear to be the most significant with respect to this kind of behavior.

Evelyne and Christine: These students construct and defend the conjecture f(n)=n/2, first on the basis of naïve empiricism, and then on that of a thought experiment related to the conception of diagonal which they elicit after the refutation of their conjecture by P 7 : "A diagonal is a straight line which belongs to a vertex of a polygon and which cuts its surface in two pieces".

But they do not share the same point of view: One of them would like to introduce a condition in the statement of the conjecture; the other would prefer to consider the definition again. Finally, it is this last decision which is taken, following an argument of Evelyne, who says that if a condition was necessary, it would have been stated in the description of the task. In other words the students have not the right to restrict the scope of the polygons which fit the conjecture; they have to give a solution for all of them. Actually, the definition they choose restricts the set of the polygons to those for which the conjecture is valid: "If we say that a polygon is… a thing whose sides are always parallel two by two… then it is not necessary to be more precise. We have just to divide by two" (Chr 201).

But on the other hand, the case of the triangle is not dealt with referring to the definition. It is rejected as a polygon because it has no diagonals; it appears to the eyes of the students as a kind of monster.

Later on a counterexample, P 5 , because it is produced by the observer, imposes itself as a polygon. Then the initial definition is rejected, and a new one is considered: "for sure a polygon can have any number of diagonals… but it should be regular" (Chr 270). Thus the only solution to save the conjecture is to introduce a condition and to search for a solution specific to odd polygons. This last solution starts from a student's conception of diagonal as an «axis of symmetry». In case of P5 it corresponds to a drawing they make (fig. 5). The solution they conjecture is f(n)=n for odd polygons, first proved by means of a thought experiment and afterwards proved «by reasons» 17 . The uncertainty which remains is an uncertainty about the premises of the students' reasoning: Definition of polygon and of diagonal. It is on the basis of these definitions that they then treat the counterexamples produced by the observer. These definitions are even written into their message: "If the number of vertices of the polygon is even: You divide the number by two and you will obtain the number of its diagonals. If the number of vertices of the polygon is odd: The number of the diagonals is equal to the number of the vertices. A polygon is a geometrical figure which can have any number of vertices but whose edges must be equal" Figure 5 For Evelyne and Christine, dealing with a counterexample is directed by what I would like to call a problématique 18 of the definition which originates in their reading of the experimental contract, following which they think that they cannot introduce any reduction of the field of polygons to be considered. The only one which escapes this treatment is the triangle which appears to them as a "monster" and which is definitely rejected as such 19 .

Hamdi and Fabrice: From their conceptions of polygon and diagonal, these students conjecture: f(n)=n2. After a refutation they encounter with P 4 , they first try to modify this conjecture. Failing in doing so, they decide to submit it to the observer. His refutation by P 5 as a counterexample leads them to give up this first conjecture. The two refutations lead them to the problem of the definition "he [the observer] should have given the definition of polygon" (Ham 228).

They then search for a new solution taking as (implicit) basis what appears to be a correct conception of a convex polygon. Their new conjecture is f(n)=n.(n-3), which is refuted by the observer by the counterexample P 6 . They modify their conjecture into f(n)=(n.(n-3))/2. Actually, it is an ad hoc modification which is elaborated straightaway from the arithmetical relation they establish between the result obtained (that is, 9) and the one they had computed (that is, 18). This conjecture is then confirmed in the case of P 5 . 17 That is what we have called in French: Preuve en raison , that is a proof by what could be seen as a real computation on statements (in French: Calcul sur des énoncés ). 18 By «problématique» we mean the framework within which problems are stated and recognized as being relevant. 19 We should remark that, following their definition of polygon and diagonal and the solution they proposed for odd polygons, the triangle is no longer a counterexample. On the other hand, there is a contradiction they do not examine, between what they know about the triangle and the fact that the conceptions they have elaborated lead to 3 diagonals for a [equilateral…] triangle.

Then they envisage a crucial experiment on P 16 which they finally abandon. They state in their message that the triangles and the quadrilaterals are outside the domain of validity of their conjecture. They change their mind in the case of the quadrilateral after an example produced by the observer, but they stand on their position in the case of the triangle.

The other counterexamples produced by the observer are the following drawings (fig. 6).

Figure 6 First, on the one hand, Fabrice refuses to accept them as being polygons, but on the other, Hamdi treats them as exceptions. Then Fabrice remembers that there are polygons with edges intersecting elsewhere than vertices, so he revises his point of view and he considers further the drawings of the observer as being polygons. Thus the task for the students becomes that of stating a condition to push aside this kind of objects: "it does not work for polygons which have a point in the middle" (Fab 682). We should notice that this condition is in no way related to an analysis of the conjecture and its possible foundations but consist in an ad hoc adaptation to the apparent features of the counterexamples.

The rejection of their initial conjecture by Hamdi and Fabrice is due to their uncertainty about their conceptions which underlie it. It is this same uncertainty which leads them to raise the problem of the definition. The modification of their second conjecture f(n)=n.(n-3) appears to be unavoidable as the counterexample P6 cannot be rejected as not being a polygon, but this modification is ad hoc in order to save the conjecture. On the other hand the counterexamples produced afterwards by the observer do not lead to new modifications, they are rejected: The conditions introduced by the students being nothing but ad hoc means to preserve the conjecture.

Then, the treatment of the refutations is dominated by the students' analysis of the objects in question, perhaps to the detriment of an analysis of the rationality of the conjecture.

Pierre and Mathieu: These students do not share the same conception of polygon and diagonal, this disagreement is at the core of their conflict. According to Pierre, a polygon is a «geometrical figure with several sides» but diagonal is taken as a synonym of oblique (actually, a line non-parallel to the edges of the polygon). For Mathieu, a polygon is nothing but a regular polygon whose diagonals are diameters. For a while Mathieu considers the diagonals as being axes of symmetry; this conception is rejected by Pierre because of his own conception. Finally, this conception is rejected after confrontation with the case of the square.

The first conjecture of these students: f(n)=n/2, is refuted by P 5 . The treatment of this counterexample is at stake in a debate between Pierre and Mathieu about what is or is not a diagonal, a polygon, or about the relevance of a proposed response:

-Mathieu proposes to reject the conjecture, but Pierre opposes that: It is so convincing that that should not be done; -Pierre suggests treating it as an exception but Mathieu refuses because a mathematical assertion must apply to each of the mathematical objects concerned; -Mathieu proposes to reject it as a non-polygon, but Pierre refuses, referring to the etymology of the word «polygon»;

-Pierre proposes to stretch the concept of diagonal (including "half-diagonals"), but such an extension clearly appears to be too ad hoc. Finally they search for a specific solution for the odd polygons, despite the fact that they consider that a «mathematical» solution should be expressed by a unique formula. They conjecture f(n)=n/2 for even polygons, and f(n)=n-1 for odd polygons (which is in fact an ad hoc adaptation of the initial conjecture). But Pierre, challenged by the failure of his attempt to stretch the concept of diagonal, finally changes his mind about what a diagonal consists of accepting the proposal of Mathieu. They propose to the observer: f(n)=n/2 for even polygons, and f(n)=n for odd polygons (which is again an ad hoc adaptation to the case of P 5 ) .

After the next refutation of that conjecture by the observer, Pierre surrenders, while Mathieu tries to find one solution. Finally they abandon it.

The conflict between Pierre and Mathieu is, first of all, a conflict between two different conceptions about what a polygon or a diagonal is. This conflict leads them to debate the problem of the definition of these objects. This problem being solved, and the two students' agreement about what is allowed in mathematics being found (status of the exceptions, unique formula), overcoming of a refutation consists in the search for specific solutions, and then for one solution. For Pierre, the fact that each of their solutions is refuted leads to the idea that the situation is nothing but a game in which they have to "guess" a solution. Actually, he abandons the search to try to obtain the solution from the observer.

CONCLUSION

Three factors appear to determine students' choice in their treatment of a refutation:

-The analysis with reference to the problem itself. It gives a central place to the discussion on the nature of the objects concerned, and thus on their definition. This analysis potentially leads to any type of treatment which could be considered, none of them being privileged a priori. The choice the students make can be understood only in the light of a local analysis or of the specific character and knowledge of each of the individuals. The type of treatment can change in the course of the problem-solving process: Modification of the definition followed by the introduction of a condition or a modification of the initial conjecture when the conceptions have been stabilized. The origins of the choice between the introduction of a condition and the search for a specific solution, and the modification of the conjecture, cannot be traced in the data gathered. What could be conjectured is that when the refutation might brush aside a wide range of polygons (with respect to the students' conceptions), then a modification of the conjecture is decided which consists in a specific solution (extension to the odd polygons in case of f(n)=n/2, search for a solution for non-convex polygons).

-The analysis with reference to a global conception of what mathematics consists of. This could be a serious obstacle to some of the treatments of a refutation: Refusal to treat the counterexample as an exception, refusal of a solution which cannot be expressed by a unique formula, etc.

-The analysis with reference to the situation. What is in question is mainly the didactical contract which leads students to favour some treatments of the counterexample (definition game, riddle game in which they abandon their solution quite easily) or constitutes an obstacle to others (refusal to introduce a condition because it has not been stated in the problem statement). Whatever is the case, the role played by the experimental contract should not be over-estimated. In particular, it should be noticed that the fact that treating the counterexample as an exception or its rejection, during phase II of the experiment, confirms the result already known about the fact that one counterexample is generally not sufficient for students to call a conjecture into question (Burk 1984, Galbraith 1979). The fact that this treatment has been observed in other, and quite different, experimental settings, suggests that it is not specific to the experimental contract in this situation as it might be conjectured at first. One of the questions I have examined is that of a possible influence of the type of conjecture on the choice of a treatment of a refutation. One hypothesis might be that if the conjecture is false, then its rejection or its modification or a revision of the definition should be dominant, but that, if the conjecture is correct, then the rejection of the counterexample should be dominant. Actually, I have observed that conjectures like f(n)=n or f(n)=2n are abandoned after their refutation. In fact, such conjectures are very fragile in so far as they are verified by only one polygon. It is quite different when the conjecture is verified by a large set of polygons, like f(n)=n/2. The strength of that conjecture comes from the fact that it is related (explicitly or not) to the conception of a polygon as a regular polygon and the diagonal as a diameter 20 . On the other hand, I have checked the type of treatment of the counterexample against the type of foundation of the conjecture; it appears that no treatment of the counterexample is privileged, whether the foundation of the conjecture is naïve empiricism or a thought experiment.

I have also examined the case of the correct conjectures. It should be noticed that they implicitly refer to a correct conception of polygon and diagonal. These conjectures are the result of a process which has occupied all the first phase of the experiment, whether they have been constructed deductively or are the result of a dialectic between successive attempts and their refutation. The treatment appears to be far less varied than in the case of the conjecture f(n)=n/2. A first type of treatment which is dominant is the rejection of the counterexample after its analysis relative to the students' conceptions, a second type of treatment is to consider the counterexample as an exception or to introduce a condition (actually this last treatment could be a way for some students to escape particular cases).

Whatever is the level of proving involved in the problem-solving process, it appears that the robustness of the students' conceptions and the existence of a large domain of validity of their conjecture lead to privilege the treatments which consist of keeping aside counterexamples which appear to be some kind of «monsters» 21 in the eyes of the students. On the other hand, I have found that in the case of the conjecture f(n)=n/2, the limitation to even polygons is associated with an important uncertainty about the definition, which is often reconsidered after the refutation.

Mathematicians, Lakatos considers, share almost the same rational background. In the case of the students the background is not the same: Naïve empiricism, or pragmatic validations, can be the basis of their proof and can constitute the roots of their belief in the truth of a statement. If this is so, the discussion of the criticism of a counterexample or of the modification of conjecture could appear less relevant to the teacher than the discussion of its «logical» background. How can we escape the fact that faced with a counterexample produced by the teacher, students claim that it is a particular case when in fact, what should be questioned is the naïve empiricism on which their conjecture is based? At a higher level of schooling this problem can still appear: A student may be discussing the legitimacy of a counterexample, when it is his or her understanding of the related mathematical knowledge that should be questioned.

To base the learning of mathematics on the students' becoming aware of a contradiction requires that we take into account the uncertainty about the ways they might find to overcome the contradiction. If, as I believe, we cannot assume that there is strict determinism in cognitive development, what could be the role played by a particular situation? Rather the teacher's interventions will be fundamental. The way he or she manages the teaching situation may bring the students to see that their knowledge and the rationality of their 20 Such a conception is reinforced by the prototype of the square. 21 That is, a «monster» with respect to their conception of what a polygon is. For example, a polygon must have diagonals (actually the problem underlying this view is that of the interpretation of «zero»).

Nicolas Balacheff (1991) Treatment of refutations 20 / 20 conjectures must be questioned and perhaps modified, because no ad hoc adaptation of a particular solution, or its radical rejection, can by itself lead to a conceptual advance.

  Figure 2.

  ): "Except these which have a point in their middle" (Ham 616). Such a condition has nothing to do with what could constitute the foundation of their conjecture.

  Figure 3.

Figure 4 .

 4 Figure 4. Olivier and Stéphane reject the counterexamples proposed by the observer (fig 4.), analysing them as joint figures but not real polygons: "That's not a polygon" (Oli 768) "Wait… a polygon is a thing… here it's not a polygon… they are two triangles… [to the observer] Is that a polygon ? " (Sté 769). Actually, in order to reject the counterexample the students have to raise the problem of the definition of a polygon: "To a point it must be related to no more than two other points"(Sté 382)

Indeed such a schema just evokes the range of possible consequences, but it is sufficient to give an idea of what we call the openness of the possible ways to treat a refutation.

cf.(Balacheff, 1988) for a complete report on this research.

That is to say: Communication is fiction; the other participants (the receivers) do not exist.(Mugny 1985, chap. 10). We call such a situation: Situation for communication.

In 1758 Euler published his Elementa doctrinae solidorum which was about "corpora hedris planis inclusa". It is there that we find the first formulation of the famous theorem.NicolasBalacheff (1991) Treatment of refutations

NicolasBalacheff (1991) Treatment of refutations

cf. TableII and Table III.

Here "a" is the name of a function which gives the value of the difference between the number of diagonals of Pn and that of Pn+1.

cf. figure2

Against each counterexample proposed by the observer, they enrich their definition with a new ad hoc clause.NicolasBalacheff (1991) Treatment of refutations

Acknowledgement:

I am greatly indebted to David Pimm and Ernst Von Glasersfeld for helping me with the English version of my text.


Benjamin Lecouteux

Laurent Besacier

Hervé Blanchon

LIG English-French Spoken Language Translation System for IWSLT 2011

This paper describes the system developed by the LIG laboratory for the 2011 IWSLT evaluation. We participated to the English-French MT and SLT tasks. The development of a reference translation system (MT task), as well as an ASR output translation system (SLT task) are presented. We focus this year on the SLT task and on the use of multiple 1-best ASR outputs to improve overall translation quality. The main experiment presented here compares the performance of a SLT system where multiple ASR 1-best are combined before translation (source combination), with a SLT system where multiple ASR 1-best are translated, the system combination being conducted afterwards on the target side (target combination). The experimental results show that the second approach (target combination) overpasses the first one, when the performance is measured with BLEU.

Introduction

This paper describes LIG approach for the evaluation campaign of the 2011 International Workshop on Spoken Language Translation (IWSLT-2011), English-French MT and SLT tasks.

This year we focus on the SLT task and on the use of multiple 1-best ASR outputs to improve translation. Two different approaches are proposed:

-source combination: multiple ASR 1-best are combined before translation, -target combination: multiple ASR 1-best are translated, before applying system combination on the target side.

The remainder of the paper is structured as follows. Section 2 reminds the starting point of this work, namely the former LIG SLT system presented last year for IWSLT 2010. Then, we describe chronologically the work done this year to improve both MT and SLT English-French systems, including the update of the models with data provided this year (section 3). The best system obtained in section 3 is used for the experiments detailed in section 4 where target combination is compared to source combination. Finally, in section 5 we sum up our work.

Overview of MT and SLT LIG systems in 2010

This section describes the starting point of this work which is the LIG system presented last year for IWSLT 2010. More details on this system can be found in [START_REF] Besacier | LIG Statistical Machine Translation Systems for IWSLT 2010[END_REF].

Last year, a new task was dedicated to the translation of the TED Talks corpus, a collection of public speeches on a variety of topics for which video, transcripts and translations are available on the Web. Training data for this exercise was limited to a supplied collection of freely available parallel texts, including a parallel corpus of TED Talks. The translation input conditions of the TALK task consisted of (1) automatic speech recognition (ASR) outputs, i.e., word lattices (SLF), N-best lists (NBEST) and 1-best (1BEST) speech recognition results, and (2) correct recognition results (CRR), i.e., text input without speech recognition errors. Participants of the TALK task had to submit MT runs for both input conditions.

Resources Used in 2010

Last year, we used the TED Talks collection plus other parallel corpora distributed by the ACL 2010 Workshop on Statistical Machine Translation (WMT).

For the training of the translation models, the provided Europarl and News parallel corpora were used (total 1,767,780 sentences) as well as the TED training corpus (total 47,652 sentences). For the language model training, in addition to the French side of the bitexts described above (News-mono+TED-mono), the 2010 News monolingual corpus in French was available (total 15,234,997 sentences).

The TED dev set (934 sentences) was used both for tuning and evaluation purpose. This corpus will be referred to as Dev2010 in the rest of this paper.

Preprocessing / Post-processing in 2010

As preprocessing, we lowercased and tokenized all the data but kept punctuation for the LM and TM models training. Before translation, a source English sentence is thus lowercased and tokenized. The translated output in French needs to be detokenized and recased. The best technique found to re-case the translated output used a SMT-like approach where a phrase table was trained from a parallel French no-case/case corpus (trained on the News monolingual corpus in French of 15M sentences, see [START_REF] Besacier | LIG Statistical Machine Translation Systems for IWSLT 2010[END_REF]).

For the Reference translation (MT) task, the punctuation of the translated output was refined using the punctuation of the source sentence (practically, the ending punctuation mark of the source sentence was put at the end of the translated sentence).

Language modeling in 2010

The target language model was a standard 3-gram language model trained using the SRI language modeling toolkit [START_REF] Stolcke | SRILM -An Extensible Language Modeling Toolkit[END_REF]. The smoothing technique applied was the modified Kneser-Ney discounting with interpolation. We interpolated a LM trained on the TED training data (47k sentences) with a LM trained on Europarl, News, UN and News-mono (24M sentences in total). After a perplexity test to optimize the interpolation weight (on Dev2010), we chose an interpolation weight equal to 0.5.

Translation modeling and tuning

For the translation model training, the uncased (but punctuated) corpus was word aligned and then, the pairs of source and corresponding target phrases were extracted from the word-aligned bilingual training corpus using the scripts provided with the Moses decoder [START_REF] Koehn | Moses: Open Source Toolkit for Statistical Machine Translation[END_REF]. The result is a phrasetable containing all the aligned phrases. This phrase-table, produced by the translation modeling, is used to extract several translations models. In the experiments reported here, only 8 features were used in the phrase-based models: 5 translation model scores, 1 distance-based reordering score, 1 LM score and 1 word penalty score.

We used the Minimum Error Rate Training (MERT) method to tune the weights. MERT was applied on the TED Dev2010 corpus (934 sentences). Moreover, it is important to note that, during tuning, punctuation was systematically removed from the Nbest lists and BLEU was calculated using un-punctuated references. While such tuning procedure might be sub-optimal to optimize BLEU (cased), we did this to anticipate the ASR output translation task for which decoding (and tuning) is also done without punctuation.

Other aspects of the LIG 2010 MT system

Last year, additional improvements over the above described baseline were proposed (see [START_REF] Besacier | LIG Statistical Machine Translation Systems for IWSLT 2010[END_REF] for more details):

-do not reorder over punctuation during decoding, -apply phrase-table pruning with a technique similar to [START_REF] Johnson | Improving Translation Quality by Discarding Most of the Phrasetable[END_REF] (retuning with MERT needed after pruning).

SLT system for IWSLT 2010

For the speech translation (SLT) task, the TM and LM models described above were used. However, the pre-/postprocessing was different since, for instance, no "source punctuation" could be used in the case of ASR input.

First, in order to be consistent with our translation model, the ASR output was lowercased and tokenized before translation. Moreover, the (source) English ASR output was re-punctuated (see [START_REF] Besacier | LIG Statistical Machine Translation Systems for IWSLT 2010[END_REF] for more details). Finally, it was necessary to develop a true re-punctuation system for French in the case of ASR output translation. This was done by building a French language model trained on punctuated and uncased French data (Europarl +News+UN+Newsmono: 24M sentences in total). The punctuation was restored after translation using this LM and the hidden-ngram command from SRILM toolkit. After repunctuation, we used the SMT-based recaser presented earlier. For the SLT task, the final system submitted by LIG in 2010 was ranked among the best sites that participated to the TALK task last year.

Improvements of MT and SLT systems

done for 2011 After retuning on dev2010 data, this approach improved the system by more than 1 point BLEU [START_REF] Papineni | BLEU: A method for automatic evaluation of machine translation[END_REF][START_REF] Potet | The LIGA machine translation system for WMT[END_REF]. Note that in this case there are 10 phrase table translation features instead of 5.

Iterative improvement of the MT system

Improvement of the SLT system

The pre-/-post-processing for SLT described in section 2.6 was not changed this year for 2011 evaluation. However, we performed a tuning adapted to ASR input by re-estimating the log-linear weights using the dev2010 ASR output (corresponding to a rover between several systems, provided by the organizers). The BLEU score was improved significantly using the new weights both on dev2010 and tst2010. The other improvements of the SLT system are described in section 4 which details the source/target combination approaches.

Source versus Target Combination

This year, since several ASR system outputs were provided for the evaluation (see table 4 for an overview of ASR system performance on tst2010 data), we decided to investigate different combination techniques. More precisely, we compared the performance of a SLT system where multiple ASR 1-best are combined before translation (source combination), with a SLT system where multiple ASR 1-best are translated, the system combination being conducted afterwards on the target side (target combination). The TM and LM used, as well as the log-linear weights are the one of the system (8) described in section 3.2 (performance given in table 3). This means that the log-linear weights of the SMT system were not re-tuned in the experiments described in this section.

Source combination

In order to combine sources we applied a classical ROVER [START_REF] Fiscus | A post-processing system to yield reduced word error rates:recognizer output voting error reduction (ROVER)[END_REF] weighted by the ASR WER quality. The used cost function for word selection is:

alpha*Sum(WordOcc) + (1-alpha)*Sum(Confidence(W))
Where alpha=0.9 and confidence scores are empirically defined: 1 for best system (4), 0.8 for systems (2) and (0) and 0.5 for system (1).

Target combination

In that case, we propose a MT systems combination similar to the one used in [START_REF] Potet | The LIGA machine translation system for WMT[END_REF]. System combination is based on the 500-best translated outputs generated from each ASR source system. We used the Moses option distinct, ensuring that the hypotheses produced for a given sentence are different inside an N-best list. Each N-best list is associated with a set of 13 features:

• 10 translation model scores (2 phrase tables * 5 scores each) • 1 distance-based reordering score • 1 language model score • 1 word penalty score N-best are combined in several steps. The first one takes as input lowercased 500-best lists, since preliminary experiments have shown a better behaviour using only lowercased output (with cased output, combination presents some degradations). The score combination weights are optimized on a development corpus, in order to maximize the BLEU score at the sentence level when N-best lists are reordered according to the 13 available scores. To this end, we resorted to the SRILM nbest-optimize tool to do a simplex-based Amoeba search [START_REF] William | Numerical Recipes in C: The Art of Scientific Computing[END_REF] on the error function with multiple restarts to avoid local minima.

Once the optimized feature weights are computed independently for each ASR source, N-best lists are turned into confusion networks [START_REF] Mangu | Finding consensus in speech recognition: Word error minimization and other applications of confusion networks[END_REF]. The 13 features are used to compute posteriors relatively to all the hypotheses in the Nbest list. Confusion networks are computed for each sentence and for each system. Then, these confusion networks computed for each sentence are merged into a single one. A ROVER is applied on the combined confusion network and generates a lowercased 1-best. The usual post-processing described in 2.6 is finally applied as usual to obtain adequate output.

On this system we observe a different behaviour compared to the one presented in [START_REF] Potet | The LIGA machine translation system for WMT[END_REF]: combining the N-best of a single system does not improve the BLEU score. Thus, all the experiments reported below involves combination of several N-best lists (except for first four lines of table 5).

Experiments

The results obtained from individual ASR systems show that the best transcription system (system4) leads to the best BLEU score while the worst one (system1) leads to the lowest BLEU score (2.9% WER absolute difference gave 1.6 BLEU difference). However, the correlation between ASR performance and BLEU is not so clear while looking at results for system0 and system2 (lower WER for system 0 but lower BLEU too). As far as system combination is concerned, it is important to note that we decided to tune the combination weights on tst2010 data, which is twice bigger than dev2010 data. Thus, dev2010 was considered as a validation test in the case of table 5 results. When two systems are available, target combination is inefficient while source combination cannot be applied. When three systems are available, the target combination is clearly better than the source combination on the validation set (which is dev2010, cf remark above). The same trend is observed with four systems. We can note that as more ASR systems [START_REF] Federico | Sebastian Stueker -Overview of the IWSLT[END_REF][START_REF] Koehn | Moses: Open Source Toolkit for Statistical Machine Translation[END_REF][START_REF] Johnson | Improving Translation Quality by Discarding Most of the Phrasetable[END_REF] are added to the combination, the overall performance improves.

So, in order to take advantage of both combinations we also experimented a source+target combination where the (source) rover is added as a new system to the target combination method. However in this last experiment a slight BLEU degradation is observed on the validation set (dev2010), even if the results on the development set (tst2010 here) are better. This disappointing result may be explained by the fact that the ROVER source introduces redundant information and leads to the elimination of marginal assumptions.

Official Results

At the time of submission, we had not evaluated all the combinations described in table 5. So, at this time, the source+target combined system (last line of table 5) was submitted as our "primary" (LIG_P) system, our contrastive system corresponding to source combination strategy only (LIG_C1 ; rover4021). The official results of table 6 (obtained on tst2011 data) confirm that the target combination (and source+target) outperforms the source combination.

Conclusion

This paper presented the work done at LIG this year for IWSLT2011. While the English-French MT was mostly updated on the new data, without radical changes, we proposed several approaches to take advantage of multiple ASR system outputs. The experimental results obtained show that combining translation hypotheses (obtained from several translated ASR 1best) on the target language side lead to better results than combining ASR 1best on the source side, before translation (0.4 BLEU improvement observed).

Table 1

 1

	reports the results obtained on Dev2010 (934
	sentences) and Tst2010 (1664 sentences) with last year LIG
	system.

Table 1 :

 1 Performance of the IWSLT 2010 LIG MT system using BLEU[START_REF] Papineni | BLEU: A method for automatic evaluation of machine translation[END_REF] -BLEU measured with punct+case (c+p), case only (c) and none (x)

	Corpus	BLEU c+p	BLEU c	BLEU X
	Dev2010	0.2408	0.2179	02311
	Tst2010	0.2758	0.2479	0.2590

Table 2

 2 summarizes the iterative improvements done this year over the LIG 2010 system. First, we evaluated the performance of a phrase-table trained on the TED 2011 bilingual data (107268 sentences in total) only with and without tuning[START_REF] Federico | Sebastian Stueker -Overview of the IWSLT[END_REF][START_REF] Koehn | Moses: Open Source Toolkit for Statistical Machine Translation[END_REF]. The target language model was also updated using the TED 2011 mono (111431 sentences) data (4), which slightly increased the performance. The results obtained show a reasonable performance of the PT trained on TED 2011 only, so we experimented multiple phrasetable decoding where translation options are collected from one table, and additional options are collected from the other table. When the same translation option (in terms of identical input phrase and output phrase) is found in multiple tables, separate translation options are created for each occurrence, but with different scores (this corresponds to the either option defined in the moses advanced features1 )

Table 2 :

 2 Iterative improvement of the LIG MT system in 2011

		BLEU	BLEU	BLEU
	System	c+p dev2010/	c dev2010/	x dev2010/
		tst2010	tst2010	tst2010
	1. LIG 2010	0.2408/	0.2179/	02311/
	2010 bitexts	0.2758	0.2479	0.2590
	2. PT trained on TED2011 bitext	0.2270/	0.2044/	0.2167/
	only (no tuning)	0.2782	0.2508	0.2611
	3. PT trained on TED2011 bitext	0.2411/	0.2168/	0.2296/
	only (+tuning)	0.2781	0.2513	0.2621
	4. (1)+update LM using TED 2011	0.2452/	0.2207/	0.2335/
	mono	0.2789	0.2516	0.2623
	5. Multiple PT -Either(1,4) -no	0.2397/	0.2167/	0.2293/
	tuning + updated LM	0.2898	0.2618	0.2726
	6. Multiple PT -Either(1,4) +	0.2524/	0.2289/	0.2420/
	tuning + updated LM	0.2896	0.2623	0.2733

Table 3 :

 3 Iterative improvement of the LIG SLT system in 2011 (using the rover provided by the organizers as input)

		BLEU	BLEU	BLEU
	Corpus	c+p dev2010/	c dev2010/	x dev2010/
		tst2010	tst2010	tst2010
	7. (6) + pre-/post-process described	0.1670/	0.1606/	0.1709/
	in 2.6	0.2027	0.1992	0.2081
	8. (7)+ tuning on ASR input	0.1745/	0.1671/	0.1766/
	(Dev2010)	0.2087	0.2046	0.2133

Table 4 :

 4 ASR performance[START_REF] Federico | Sebastian Stueker -Overview of the IWSLT[END_REF] of the system (outputs) used (on tst2010)

	System	WER%
	0	17.1
	1	18.2
	2	17.4
	3 (not used)	27.3
	4	15.3

Table 5 :

 5 Source vs Target Combination (system3 has been removed from the experiments) -here

combination tuned on tst2010 and evaluated on dev2010

		BLEU	BLEU	BLEU
	Combination	c+p dev2010/	c dev2010/	x dev2010/
		tst2010	tst2010	tst2010
	Sys 0 alone	0.1671/	0.1602/	0.1695/
		0.2012	0.1957	0.2039
	Sys 1 alone	0.1608/	0.1534/	0.1622/
		0.1944	0.1909	0.1985
	Sys 2 alone	0.1737/	0.1664/	0.1768/
		0.2027	0.1975	0.2072
	Sys 4 alone	0.1770/	0.1709/	0.1811/
		0.2082	0.2033	0.2125
	Target comb. (systems 42)	0.1772/	0.1710/	0.1812/
		0.2085	0.2036	0.2130
	Source comb. (rover systems 420)	0.1787/	0.1709/	0.1811/
	done at LIG	0.2139	0.2099	0.2191
	Target comb. (systems 420)	0.1815/	0.1748/	0.1852/
		0.2136	0.2087	0.2178
	Source comb. (rover systems 0213)	0.1745/	0.1671/	0.1766/
	provided by IWSLT orga. (cf tab 3)	0.2087	0.2046	0.2133
	Source comb. (rover systems 4021)	0.1797/	0.1726/	0.1826/
	done at LIG	0.2159	0.2115	0.2209
	Target comb. (systems 4021)	0.1841/	0.1782/	0.1889/
		0.2143	0.2099	0.2189
	Source+Target comb. (systems	0.1818/	0.1758/	0.1859/
	4021R)	0.2166	0.2120	0.2215

Table 6 :

 6 Official automatic evaluation results obtained by LIG at IWSLT11 (BLEU score) -SLT Task

	System.	bleu(p+c)	bleu(x)
	LIG_P (Tst2011)	0,2485	0,2598
	source+target comb. (4201R)
	LIG_C1 (Tst2011)	0,2453	0,2561
	source comb. (4201)
	LIG_PostEval (Tst2011)	0.2489	0.2599
	Target comb (4201)

http://www.statmt.org/moses/?n=Moses.AdvancedFeatures#ntoc15