Pierre Godard
email: godard@limsi.fr

Kevin Löser
email: loser@limsi.fr

Alexandre Allauzen
email: allauzen@limsi.fr

Laurent Besacier
email: laurent.besacier@imag.fr

François Yvon
email: yvon@limsi.fr

Unsupervised Word Segmentation: does tone matter ?

come

Introduction

Many languages will face extinction in the coming decades. Half of the 7,000 languages spoken worldwide are expected to disappear by the end of this century [START_REF]The Cambridge Handbook of Endangered Languages[END_REF], and there are too few field linguists to document all of these endangered languages. Innovative speech data collection methodologies [START_REF] Bird | Aikuma: A mobile app for collaborative language documentation[END_REF][START_REF] Blachon | Parallel speech collection for under-resourced language studies using the LIG-Aikuma mobile device app[END_REF] as well as computational assistance [START_REF] Adda | Breaking the unwritten language barrier: The Bulb project[END_REF][START_REF] Stücker | Innovative technologies for under-resourced language documentation: The Bulb project[END_REF] were recently proposed to help them in their documentation and description work. This paper follows similar objectives and focuses on the unsupervised discovery of words from an unsegmented sequence of symbols. While such material could be obtained by automatic phone recognition from speech, we investigate here oracle data (hand-annotated symbols from linguists) in a rather limited resource setting (only a few thousand sentences). In this context, our main question is to evaluate the usefulness of tone information in unsupervised word segmentation, and we use Mboshi, a mostly unwritten African language of the Bantu family, as our main test case.

The integration of tonal information in segmentation relies on Bayesian nonparametric (BNP) models, popularized in Natural Language Processing (NLP) by [START_REF] Goldwater | Contextual dependencies in unsupervised word segmentation[END_REF][START_REF] Goldwater | A Bayesian framework for word segmentation: Exploring the effects of context[END_REF][START_REF] Goldwater | Interpolating between types and tokens by estimating power-law generators[END_REF]. In this approach, (pseudo)-words or (pseudo)-morphs are generated by a bigram model over a non-finite inventory, through the use of a Dirichlet process (DP), or a more general Pitman-Yor process (PYP), which enables to discover units that follow a power-law distribution, a universal characteristic of language lexicons. These algorithms were originally designed as computational models of language acquisition and were mainly applied to non-tonal languages, with the exception of [START_REF] Johnson | Unsupervised phonemic Chinese word segmentation using adaptor grammars[END_REF], who investigated the use of adaptor grammars for unsupervised word segmentation of Mandarin Chinese. Tones were shown to have a small impact on segmentation accuracy and were reported to yield a small improvement for simple grammars and no improvement with more complex ones. Also worth mentioning is the work of [START_REF] Ludusan | Prosodic boundary information helps unsupervised word segmentation[END_REF], who studied the role of prosodic information (at a macroscopic level) for word segmentation. The approach was tested on English and Japanese: for both languages, it was shown that prosodic boundaries were actually helping word segmentation. Contributions: we investigate in this paper whether and how tone annotation can help word segmentation in the case where the distribution of tones obey morphological and syntactical, as well as lexical, constraints. After briefly presenting some peculiarities of Mboshi, we first show (in Section 2) that tones help disambiguate word boundaries in a supervised setting -suggesting that this information could also help the unsupervised discovery of words. We then present in Section 3 a new hierarchical BNP model, which uses generalized backoff schemes to integrate tonal representations in word segmentation. Based on the experiments reported in Section 4, we conclude that, notwithstanding the inherent unstability of BNP models, tonal information can improve word discovery procedures.

A Preliminary Study: Supervised Word Segmentation

In order to assess the potential for tones to help discovering a tonal language's word units, we first conducted a supervised experiment making use of decision trees. We start this section by presenting a short sketch of the language targeted in this work: Mboshi.

Mboshi language

Mboshi is a language spoken in Congo-Brazzavile, and it was one of the languages documented by the BULB (Breaking the Unwritten Language Barrier) project [START_REF] Adda | Breaking the unwritten language barrier: The Bulb project[END_REF][START_REF] Stücker | Innovative technologies for under-resourced language documentation: The Bulb project[END_REF], using the LIG-AIKUMA tool [START_REF] Blachon | Parallel speech collection for under-resourced language studies using the LIG-Aikuma mobile device app[END_REF]. Preliminary experiments for a small portion of it were reported in [START_REF] Godard | Preliminary experiments on unsupervised word discovery in mboshi[END_REF]. Mboshi is a two tone Bantu language whose words are typically composed of roots and affixes. Almost all Mboshi words include at least one prefix, while the presence of several prefixes and one suffix is also very common. While the language can be considered as rarely written, linguists have nonetheless defined a non-standard grapheme form of it, considered to be close to the language phonology. The suffix structure tends to be a single vowel (e.g. -a or -i) whereas the prefix structure may be both CV and V. Most common syllable structures are V and CV, although CCV may arise due to affricates and pre-nasalized plosives (coded with symbols dz and mb). Mboshi also makes use of short and long vowels (coded respectively as V and VV). With respect to tones, the high tone is coded using an acute accent on the vowel while low tone vowel has no special marker. Word root, prefix and suffix all bear specific tones which tend to be realized as such in their surface forms. 3Tonal modifications may also arise from vowel deletion at word boundaries. Concerning grammatical tones, word root, prefix and suffix all bear specific tones which tend to be realized as such in their surface forms. Tonal modifications may arise from vowel deletion at word boundaries. A productive combination of tonal contours in words can also take place due to the preceding and appended affixes. These tone combinations play an important grammatical role particularly in the differentiation of tenses. However, in Mboshi, the tones of the roots are not modified due to conjugations, unlike in many other Bantu languages.

Data and representations

Our study uses a corpus in Mboshi built both from translated reference sentences for oral language documentation [START_REF]Enquête et description des langues à tradition orale[END_REF] and from a Mboshi dictionary [START_REF] Beapami | Dictionnaire Mbochi-Français[END_REF]. This corpus, comprising more than 9K sentences, is split in three parts that we call S, M and L and for which we give basic statistics in Table 1. Subset S can be considered as homogeneous, as it comes from a single source; subsets M and L come from two different sources and exhibit more lexical diversity. In our transcriptions, Mboshi's tonal system consisting of a pair of high and low tones is simply represented using diacritics on vowels: acute accent for a high tone, and no accent for a low tone. Our approach consists in varying the representation of the input text and comparing the full transcription with diacritics (letter+tone) to i) the transcription letter where diacritics are removed, ii) the transcription xV where vowels are replaced by the symbol 'V', iii) the transcription xLH where high-toned vowels are replaced by the symbol 'H' and low-toned vowels are replaced by 'L', iv) the transcriptions CV (resp. CLH) where consonants in xV (resp. xLH) are replaced by a generic symbol, 'C' (see Table 2). We expect the systematic comparison of tonal (letter+tone, xLH, and CLH) with their non tonal counterpart (letter, xV, CV) to shed some light on the usefulness of this information.

Disambiguating Word Boundaries with Decision trees

For each representation of the text, we train a decision tree classifier4 to predict a binary decision corresponding to the presence or absence of a word boundary after each character. This prediction is based on features encoding a fixed-length window of characters centered around the decision point; and consider in our experiments windows of varying size 5 We report the precision, recall and Fmeasure computed on ambiguous6 word boundaries in Table 3 on the S corpus 7where 10% of the number of sentences have been held out for testing purposes. For the pseudo-orthographic (letter and letter+tone) text representations, it seems that the tonal information is of little value to disambiguate the frontiers. However, as we simplify the text representation, despite a drop in F-measure, the contrast between a representation ignoring tones (CV) and one that captures them (CLH) becomes much sharper, suggesting that a tonal signal can be used to improve segmentation. This motivates the design of new models that could capture this signal directly on pseudo-orthographic representations and help improve the precision of unsupervised segmentation. 3. Precision, Recall and F-measure on word boundaries in various text representations of corpus S with a decision tree classifier (11-words window width).

3 Non-parametric segmentation models with tone information

Pitman-Yor processes

PYPs are a class of stochastic processes used as models for sparse probability distributions with a countably infinite support and distributed according to a power-law, and therefore especially suited to model distributions arising in linguistic data [START_REF] Teh | Hierarchical Dirichlet processes[END_REF][START_REF] Goldwater | Interpolating between types and tokens by estimating power-law generators[END_REF]. A PYP is defined by some base distribution P 0 , and two

concentration (θ ∈] -d, ∞[) and discount (d ∈ [0,
+ K • d. l K+1 is
then chosen by sampling from P 0 and K is incremented.

The table layout defines a distribution P (l) over D(P 0 ), where P (l) is the probability of obtaining l by uniformly picking a random customer and returning its table label. When N → ∞, P (l) converges to a sample of PYP(P 0 , θ, d).

Given a particular table setup, the probability of sampling a label x is computed as:

P (x|n 1 . . . n K , l 1 . . . l K ) ∝ K k=1 1 l k =x • (n k -d) + (θ + Kd) • P 0 (x).

Sampling segmentations using a PYP-distributed unigram word model

In this work, we model a sentence as a concatenation of words drawn from a unigram distribution P w generated by a PYP(P spl , θ, d) as in [START_REF] Goldwater | A Bayesian framework for word segmentation: Exploring the effects of context[END_REF]. P spl is the spelling model, for instance a n-gram model over character sequences (see below).

We tokenize a corpus s 1 . . . s n of n sentences by Gibbs-sampling every segmentation s i conditioned on all other segmentations. 8 As explained above, sampling x ∼ P w can be done by maintaining a CRP associated to P w , such that for every token t in the current lexicon L there is a customer seated at a table labelled with the type of t. We also placed agnostic priors on the PYP hyperparameters: θ ∼ exp(1) and d ∼ Beta(1, 5) and resampled these hyperparameters as well as the CRP table layouts every 200 iterations.

A spelling model with tones

The spelling model defines a distribution over character strings that reflects how word forms should look like. Obvious candidate spelling models are n-gram models of character sequences:

9 P spl (w) = l i=1 P (c i |c i-n+1 . . . c i-1 )
• P (stop|c l-n+1 . . . c l )

In order to also integrate tone information in the spelling model P spl , we define the set of contexts K as the set of sequences τ 1 . . . τ j c j+1 . . . c k (with k ∈ {0, . . . , n-1}), where τ i are tones symbols from the set {H(high tone), L(low tone), C(consonant)} and c i are regular characters. A context is thus a sequence of length at most n -1 comprising a prefix of tones and a suffix of characters.

For every non-empty context κ ∈ K, we further assume that the conditional distribution P (c|κ) recursively arises from a PYP with base distribution P (c|β(κ)), where β is a backoff function. The base distribution of the unigram distribution (κ is empty) is the uniform distribution. In this setting, base distributions of PYPs themselves arise from PYPs, giving rise to a hierarchical PYP whose structure is defined by the backoff function β. To enrich the model with awareness of tone patterns, we designed the following backoff scheme, where characters are first replaced by tones (rightwards), then dropped (rightwards), as follows:

c 1 . . . c n-1 β -→ τ 1 c 2 . . . c n-1 β -→ τ 1 τ 2 c 3 . . . c n-1 β -→ . . . β -→ τ 1 . . . τ n-1 β -→ τ 2 . . . τ n-1 β -→ τ 3 . . . τ n-1 β -→ τ n-1 β -→ ∅.
On a Mboshi example, backoff will thus unfold as follows: ámid

β -→ Hmid β -→ HCid β -→ HCLd β -→ HCLC β -→ CLC β -→ LC β -→ C β -→ ∅.
This model is referred to as multi in our experiments. We also evaluated an alternative backoff scheme β , where only one single tone is remembered: 9 where we add initial padding symbols as needed.

c 1 . . . c n-1 β -→ τ 1 c 2 . . . c n-1 β -→ τ 2 c 3 . . . c n-1 β -→ . . . β -→ τ n-2 c n-1 β -→ τ n-1 β -→ ∅

This is illustrated on the same Mboshi example: ámid

β -→ Hmid β -→ Cid β -→ Ld β -→ C β -→ ∅.
This model is referred to as last in our experiments. We compare our tone models multi and last to a baseline PYP n-gram spelling model -referred to later on in our experiments as base -that is unable to distinguish between high and low tones. In this baseline, the backoff scheme β base is simply defined by:

c 1 . . . c n-1 βbase ---→ c 2 . . . c n-1 βbase ---→ c 3 . . . c n-1 βbase ---→ . . . βbase ---→ c n-2 c n-1 βbase ---→ c n-1 βbase ---→ ∅
It corresponds on the previously used example to:

ámid βbase ---→ mid βbase ---→ id βbase ---→ d βbase ---→ ∅.

Experiments

Several setups are considered with varying corpus sizes (S, M, and L) and text representations (letter+tone, letter, etc.). We report precision, recall and Fmeasure on word boundaries (BP, BR, BF) and word types (LP, LR, LF) with respect to S used as a test set for all corpora sizes. Additionally, we make the spelling model's Markov order vary between 1 and 6 and also conduct experiments with the base model on all the text representations discussed in Section 2.2. Each configuration (144 in total) is ran 5 times resulting in a total of 720 measures. Table 4 gives the results of the best thirty runs in terms of F-measure on word boundaries (BF).

Unlike what was observed in the supervised setting (Section 2), there seems to be some benefit in keeping the tonal information in the representation (letter+tone vs. letter): 22 out of the 30 best runs use tone information and top 9 configurations actually use the letter+tone representation. We can also observe that large values of n (beyond 3) do not help much and that n = 3 seems to be a good compromise. The benefit of our tone models (multi and last) is less conclusive when compared to the base model, which also obtained very good performance.

Also note that we did not observe a clear trend when increasing the corpus size. This might be due to the more heterogeneous nature of our Mboshi M, and L subsets mentioned in section 2.2. Of particular interest are the results obtained with the xLH representation and the base model: notwithstanding the replacement of 14 symbols (Mboshi has a 7 vowels inventory, each prone to carry a low or high tone) by only 2 symbols encoding the tonal information, the performance compares to the very best result on our segmentation task.

To serve as another baseline, we also ran dpseg [START_REF] Goldwater | Contextual dependencies in unsupervised word segmentation[END_REF][START_REF] Goldwater | A Bayesian framework for word segmentation: Exploring the effects of context[END_REF] 10 for all the possible representations and corpus sizes (18 configurations). It implements a Nonparametric Bayesian approach, where (pseudo)-words are generated by a bigram model over a non-finite inventory, through the use of a Dirichlet-Process. We used the same hyper-parameters as [START_REF] Godard | Preliminary experiments on unsupervised word discovery in mboshi[END_REF], which were tuned on a larger English corpus and then successfully applied to the segmentation of Mboshi. The best configuration lead to a F-measure on word boundaries (BF) equal to 70.40% which is significantly below the performance of the top-30 configurations reported in table 4. Table 5 and 6 brings complementary view on our models' behavior. They compare different models/representations configurations for which F-measures on word boundaries are averaged over spelling model's Markov order and runs. Results in Table 5 are reported for the S corpus. They confirm the benefit of keeping tonal information in the representation. As expected, impoverished representations yield worse performance than the letter+tone or letter representations. However, they still convey enough signal to reliably detect word boundaries.This result is encouraging for future experiments on true speech input, where coarse grain pseudo-phones or pseudo-syllable units could be extracted.

All these results should be taken with some care, given the large standard deviations of results inside each model/ representation combination. The standard deviation is even more important for the results of table 6 (L corpus). One explanation might be the heterogeneous nature of the L corpus, but it does not explain all the variability of our runs. The benefit of tone representation is also less clear for the L corpus than for the S corpus: as more data are considered in training, the usefulness of complex backoff schemes and rich information actually decreases.

In summary, it seems that our models do not take full advantage of the strong signal reflected in the last two lines of Table 3. This might be because these models cannot learn tonal regularities at the grammatical level and are by design limited to learn lexically-based tonal regularities. Yet, tones in Mboshi, as in most Bantu languages, play as much a grammatical role as a lexical one. Related is the current limitation of our models to a unigram word model embedding the more structured spelling model. Bigram dependencies at the word level were consistently shown to improve segmentation [START_REF] Goldwater | A Bayesian framework for word segmentation: Exploring the effects of context[END_REF]. This will be an upcoming extension of the models presented in this work.

Conclusion

In a preliminary study, we showed that when learning a segmentation classifier on a simplified representation of a Mboshi corpus where all characters were collapsed to two 'vowel' and 'consonant' categories, supplying that classifier with tones provided an increase in performance and even led to a competitive segmentation accuracy despite the considerable simplification of the data. This suggested that segmentation could benefit from sensitivity to tonal cues, and we tried to leverage the latter in an unsupervised setting by introducing hierarchical n-gram spelling models that incorporate tone-conditional distributions

Table 1 .

 1 Corpus statistics for the Mboshi corpus (letter+tone representation).

	name #sent #tokens #types
	S	1,174	6,238 1,664
	M	4,904 27,990 7,271
	L	9,256 52,433 11,440

Table 2 .

 2 Various representations of the text.

	name	representation
	letter	wa ayεε la midi
	letter+tone	wa áyεε la midí
	CV	CV VCVV CV CVCV
	CLH	CL HCLL CL CLCH
	xV	wV VyVV lV mVdV
	xLH	wL HyLL lL mLdH

  1[) hyperparameters, and generates sparse versions of P 0 , whose degree of sparsity is controlled by θ and d. Rather than explicitly defining PYP(P 0 , θ, d), we use the Chinese Restaurant Process (CRP) metaphor to recall its main properties. We assume a restaurant with K tables, with n k customers seated at table k (k ∈ {1, . . . , K}), and N = K k=1 n k the total number of customers. Each table has a label l k from the domain D(P 0 ) of P 0 . The restaurant is initially empty, with no table. Customers enter one by one and: seat at table k table with probability proportional to n k -d seat at an empty table with probability proportional to θ

Table 4 .

 4 Top

	corpus size model Markov order representation	BP BR BF	LP LR LF
	M	base	3	letter+tone	89.07 72.89 80.17	58.28 62.80 60.46
	S	last	1	letter+tone	77.59 81.50 79.50	54.13 45.67 49.54
	M	last	3	letter+tone	87.20 72.93 79.43	56.53 60.64 58.51
	M	base	3	letter+tone	86.53 71.52 78.31	55.93 60.34 58.05
	L	base	3	letter+tone	89.17 69.23 77.95	55.80 62.44 58.93
	S	multi	3	letter+tone	88.58 69.08 77.62	52.12 54.03 53.05
	M	last	3	letter+tone	83.82 71.48 77.16	52.94 57.87 55.30
	M	last	6	letter+tone	76.29 78.04 77.16	47.98 46.45 47.21
	S	last	1	letter+tone	76.86 77.47 77.16	54.45 47.42 50.69
	L	base	2	letter	81.51 73.20 77.13	55.25 55.21 55.23
	S	last	6	letter+tone	80.25 74.23 77.12	53.16 48.56 50.75
	M	base	3	letter	88.85 68.13 77.12	57.36 63.46 60.26
	M	base	3	letter	87.71 68.33 76.81	57.44 63.12 60.15
	M	last	5	letter+tone	84.25 70.56 76.80	50.75 57.09 53.73
	M	base	3	letter	89.35 67.24 76.73	56.64 63.39 59.83
	M	last	3	letter+tone	85.66 69.23 76.58	52.92 58.29 55.48
	M	base	4	letter	94.24 64.32 76.46	54.49 65.37 59.44
	L	base	3	letter	89.10 66.96 76.46	54.05 62.78 58.09
	L	base	4	letter+tone	90.90 65.88 76.39	52.28 62.08 56.76
	M	base	3	xLH	87.96 67.26 76.23	52.88 62.44 57.26
	S	last	1	letter+tone	72.64 79.94 76.11	48.96 42.61 45.57
	S	last	1	letter+tone	76.38 75.67 76.02	51.83 45.07 48.22
	M	base	3	letter	88.49 66.53 75.96	55.61 62.17 58.71
	M	base	2	xLH	81.70 70.64 75.77	53.19 52.49 52.84
	M	base	6	letter	74.72 76.62 75.66	48.74 47.31 48.01
	L	base	2	xLH	81.24 70.62 75.55	50.59 53.15 51.84
	M	last	4	letter+tone	86.32 67.16 75.54	50.11 57.21 53.42
	M	base	2	xLH	81.89 69.91 75.42	52.28 52.24 52.26
	M	base	3	letter+tone	86.54 66.65 75.30	52.70 57.57 55.03
	L	base	3	letter+tone	86.66 66.57 75.30	51.76 58.35 54.86
		30 best F-measures on word boundaries (BF) for all models, corpora
	sizes, spelling model's Markov order, text representations and 5 runs for each (144
	configurations * 5 runs were evaluated in total). A dpseg baseline was also run for
	all possible representations and corpus sizes (18 configurations) and best configuration
	lead to BF equals to 70.40%.

Table 5 .

 5 Comparing different models/representations configurations: F-measures on word boundaries averaged over spelling model's Markov order and runs -S corpus

	model representation BF average std dev min max
	last letter+tone	72.71	3.17 64.97 79.50
	base letter+tone	69.62	1.82 66.16 73.03
	multi letter+tone	69.48	3.93 61.46 77.62
	base	letter	69.26	1.98 65.01 73.33
	base	xLH	66.42	3.96 54.43 73.93
	base	xV	63.44	4.48 48.91 71.32
	base	CV	56.14	1.87 52.68 63.47
	base	CLH	50.34	4.19 44.79 60.45

Table 6 .

 6 Comparing different models/representations configurations: F-measures on word boundaries averaged over spelling model's Markov order and runs -L corpus in their hierarchy. These models were compared to a standard Pitman-Yor ngram spelling model for numerous settings. While we were able to observe some benefit in keeping the tonal information in the representation (letter+tone vs. letter), our proposed spelling model with tones was less successful in capturing tonal signal in unsupervised word segmentation. For this reason, in future work, we hope to exploit tone not purely within the spelling model, but also on the grammatical level beyond simple unigram word sequence models.

	model representation BF average std dev min max
	base	letter	69.86	4.22 57.23 77.13
	base	xLH	66.16	6.46 54.45 75.55
	last letter+tone	65.80	5.94 42.45 73.95
	base letter+tone	65.40	8.99 43.82 77.95
	base	xV	63.98	7.16 44.12 73.85
	multi letter+tone	60.94	7.51 46.94 72.86
	base	CLH	55.25	6.25 32.99 63.44
	base	CV	49.90	8.34 23.61 64.85

The distinction between high and low tones is phonological (see[START_REF] Rialland | How intonations interact with tones in Embosi (Bantu C25), a two-tone language without downdrift[END_REF]).

We use scikit-learn's implementation (http://scikit-learn.org/stable/modules/tree. html)

With padding at the beginning and end of the sentence.

We exclude word boundaries corresponding to the beginning and end of the sentence.

Similar results are obtained for the larger corpora.

Following[START_REF] Mochihashi | Bayesian unsupervised word segmentation with nested Pitman-Yor language modeling[END_REF], we use a forward filtering-backward sampling (FFBS) algorithm to sample segmentations. As this method only approximates the posterior distribution, we also perform a Metropolis-Hastings correction step.

http://homepages.inf.ed.ac.uk/sgwater/resources.html

Acknowledgments

This work was partly funded by the French ANR and the German DFG under grant ANR-14-CE35-0002. We warmly thank Martine Adda-Decker and Annie Rialland (from LPP-CNRS) for the sketch on the Mboshi language, as well as Gilles Adda (from LIMSI-CNRS), for many meaningful conversations and contributions.


Leila Amgoud
email: amgoud@irit.fr

Henri Prade
email: prade@irit.fr

Generation and evaluation of different types of arguments in negotiation

Keywords:

Until now, AI argumentation-based systems have been mainly developed for handling inconsistency.

In that explanation-oriented perspective, only one type of argument has been considered. Several argumentation frameworks have then been proposed for generating and evaluating such arguments. However, recent works on argumentation-based negotiation have emphasized different other types of arguments such as threats, rewards, appeals, etc... The purpose of this paper is to provide a logical framework which encompass the classical argumentation-based framework and handles the new types of arguments. More precisely, we give the logical definitions of these arguments and their weighting systems. These definitions take into account that negotiation dialogues involve not only agents' beliefs (of various strengths) but also their goals (having maybe different priorities), the beliefs on the goals of other agents, etc... In other words, from the different belief and goal bases maintained by an agent, we can generate all the possible threats, rewards, explanations, appeals which are associated to them. Finally, we show how to evaluate conflicting arguments of different types. The possibilistic logic framework is used for handling formulas with different degrees of certainty or priority.

Introduction

Argumentation is a promising approach for reasoning with inconsistent knowledge, based on the construction and the comparison of arguments. It may be also considered as a different method for handling uncertainty. A basic idea behind argumentation is that it should be possible to say more about the certainty of a particular fact than assessing a certainty degree in [0,1]. In particular, it should be possible to assess the reason why a fact holds, under the form of arguments, and combine these arguments for the certainty evaluation. Indeed, the process of combination may be viewed as a kind of reasoning about the arguments in order to determine the most acceptable of them. Various argument-based frameworks to defeasible reasoning have been developed (Amgoud & Cayrol 2002a;2002b;[START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF][START_REF] Prakken | Argument-based extended logic programming with defeasible priorties[END_REF] for generating and evaluating arguments. In that explanation-oriented perspective, only one type of argument has been considered. Namely, what we call explanatory arguments.

Recent works on negotiation [START_REF] Amgoud | Reaching agreement through argumentation: A possibilistic approach[END_REF][START_REF] Kraus | Reaching agreements through argumentation: a logical model and implementation[END_REF] Sycara, & Evenchik 1998; [START_REF] Parsons | Agents that reason and negotiate by arguing[END_REF][START_REF] Rahwan | Argumentationbased negotiation[END_REF][START_REF] Ramchurn | Persuasive negotiation for autonomous agents: a rhetorical approach[END_REF] have argued that argumentation plays a key role in finding a compromise. Indeed, an offer supported by a 'good argument' has a better chance to be accepted by another agent. Argumentation may also lead an agent to change its goals and finally may constrain an agent to respond in a particular way. For example, if an agent receives a threat, this agent may accept the offer even if it is not really acceptable for it. In addition to explanatory arguments studied in classical argumentation frameworks, the above works on argumentation-based negotiation have emphasized different other types of arguments such as threats, rewards, appeals, etc... In [START_REF] Kraus | Reaching agreements through argumentation: a logical model and implementation[END_REF][START_REF] Ramchurn | Persuasive negotiation for autonomous agents: a rhetorical approach[END_REF], these arguments are treated as speech acts with pre-conditions and postconditions.

The purpose of this paper is to provide a logical framework which encompasses the classical argumentation-based framework and handles the new types of arguments. More precisely, we give the logical definitions of these arguments and their weighting systems. These definitions take into account the fact that negotiation dialogues involve not only agents' beliefs (of various strengths), but also their goals (having maybe different priorities), and the beliefs on the goals of other agents. Thus, from the different belief and goal bases maintained by an agent, we can generate all the possible threats, rewards, explanations, appeals, which are associated to them. Finally, we show how to evaluate conflicting arguments of different types. The possibilistic logic framework is used for handling formulas with different degrees of certainty or priority. An illustrative example is grounded in the last section.

Types of arguments

In what follows, L will denote a propositional language. denotes classical inference and ≡ denotes logical equivalence. We suppose that we have two negotiating agents: P (called also a proponent) and C (called also an opponent). In all what follows, we suppose also that P presents an argument to C. Each negotiating agent is supposed to have a set G of goals to pursue, a knowledge base, K, gathering the information it has about the environment, and finally a base GO, containing what the agent believes the goals of the other agent are, as already assumed in [START_REF] Amgoud | Reaching agreement through argumentation: A possibilistic approach[END_REF]. K may be pervaded with uncertainty (the beliefs are more or less certain), and the goals in G and GO may not have equal priority. Thus, levels of certainty are assigned to formulas in K, and levels of priority are assigned to the goals. We obtain three possibilistic bases [START_REF] Dubois | A brief overview of possibilistic logic[END_REF] that model gradual knowledge and preferences:

K = {(k i , α i ), i = 1, . . . , n}, G = {(g j , β j ), j = 1, . . . , m}, GO = {(go l , δ l ), l = 1, . . . , p}
where k i , g j , go l are propositions of the language L and α i , β j , δ l are elements of [0, 1], or of any linearly ordered scale, finite or not. We shall denote by K * , G * and GO * the corresponding sets of classical propositions when weights are ignored, i.e.

K * = {k i , i = 1, . . . , n}, G * = {g j , j = 1, . . . , m}, GO * = {go l , l = 1, . . . , p}
We distinguish between three categories of arguments according to their logical definitions: the threats, the rewards and the explanatory arguments. In what follows we will discuss each category of arguments.

Threats

Threats are very common in human negotiation. They have a negative character and are applied to force an agent to behave in a certain way. Two forms of threats can be distinguished:

You should do α otherwise I will do β You shouldn't do α otherwise I will do β

The first case occurs when an agent P needs an agent C to do α and C refuses. P threatens then C by doing β which, according to its beliefs, will have bad consequences for C. Let's consider the following example:

Example 1 A mother asks her child to carry out his school work and he refuses. The mother then threatens him not to let him go to the festival organized by her friend the next week-end.

The second kind of threats occurs when an agent C wants to do some action α, which is not acceptable for P . In this case, P threatens that if C insists to do α then it will do β which, according to P 's beliefs, will have bad consequences for C. To illustrate this kind of threat, we consider the following example borrowed from [START_REF] Kraus | Reaching agreements through argumentation: a logical model and implementation[END_REF].

Example 2 A labor union insists on a wage increase. The management says it cannot affort it, and asks the union to withdraw its request. The management threatens that, if it grants this increase, it will have to lay off employees to compensate for the higher operational cost that the increase will entail.

In fact, for a threat to be effective, it should be paintful for its receiver and conflicts at least one of its goals. A threat is then made up of three parts: i) the conclusion that the agent who makes the threat wants, the threat itself and finally the threatened goal. IN the case of of example 1, the mother has a threat in favour of doing the school work. Formally: Definition 1 (Threat) A threat is a triple <H, h, φ> such that:

1. H ⊆ K * , 2. H ∪ {¬h} ¬φ such that φ ∈ GO * , 3. H ∪ {¬h} is consistent and minimal (for set inclusion) among the sets satisfying the two first conditions.

A t will denote the set of all threats that may be constructed from the bases <K, G, GO>. H is the support of the threat, h its conclusion and φ is the threatened goal.

Note that the above definition captures the two forms of threats.

Example 3 Let's consider an agent P having the three following bases:

K = {(¬ f inish -work → overtime, 1)}, G = {(f inish -work, 1)} and GO = {(¬overtime, 0.7)}.
Let's suppose that the agent P asks the agent C to finish the work and that C refuses. P can then make the following threat:

< {¬ f inish-work → overtime}, f inish-work, ¬overtime>.

Rewards

During a negotiation an agent P can entice agent C to do α by offering to do an action β as a reward. Of course, agent P believes that β will contribute to the goals of C. Thus, a reward has generally, at least from the point of view of its sender, a positive character. As for threats, two forms of rewards can be distinguished: "If you do α then I will do β" and "If you don't do α then I will do β".

Example 4 A sales agent tries to persuade a customer to buy a computer by offering a set of blank cassettes.

Formally, a reward is defined as follows:

Definition 2 (Reward) A reward is a triple <H, h, φ> such that:

1. H ⊆ K * , 2. H ∪ {h} φ such that φ ∈ GO * , 3. H ∪ {h} is consistent

and minimal (for set inclusion) among the sets satisfying the two first conditions.

A r will denote the set of all the rewards that can be constructed from <K, G, GO>. H is the support of the reward, h its conclusion and φ the rewarded goal.

Example 5 Let's consider an agent P having the three following bases:

K = {(f inish -work → high -budget, 1), (high -budget → high -salary, 0.6)}, G = {(f inish - work, 1)} and GO = {(high -salary, 1)}.
We suppose the agent P asks C to finish the work and C refuses. P can then present the following reward in favour of its offer/ request "finish-work": <{f inish-work

→ high -budget, high -budget → high -salary}, f inish -work, high -salary>.
In [START_REF] Kraus | Reaching agreements through argumentation: a logical model and implementation[END_REF], another kind of arguments has been pointed out. It is the so-called appeal to self-interest. In this case, an agent P believes that the suggested offer implies one of C's goals. In fact, this case may be seen as a self-reward and consequently it is a particular case of rewards.

Explanatory arguments

Explanations constitute the most common category of arguments. In classical argumentation-based frameworks which have been developed for handling inconsistency in knowledge bases, each conclusion is justified by arguments. They represent the reasons to believe in the fact. Such arguments have a deductive form. Indeed, from premisses, a fact or a goal is entailed. Formally:

Definition 3 (Explanatory argument) An explanatory ar- gument is a pair <H, h> such that: i) H ⊆ K * ∪ G * ∪ GO * , ii) H h, iii) H is consistent

and minimal (for set inclusion).

A e will denote the set of all the explanatory arguments that can be constructed from <K, G, GO>. H is the support of the argument and h its conclusion.

Example 6 Let's consider the case of an agent who wants to go to Sydney. K = {(conf erence, 0.8), (cancelled, 0.4), (conf erence → Sydney, 1), (cancelled → ¬conf erence, 1)}. G = {(Sydney, 1)} and GO = ∅.

The agent wants to go to Sydney and justifies his wish by the following explanatory argument: <{conf erence, conf erence → Sydney}, Sydney>. Indeed, from its beliefs one can deduce the fact Sydney.

In [START_REF] Kraus | Reaching agreements through argumentation: a logical model and implementation[END_REF], other kinds of arguments have been proposed and they are called appeals. We argue that the different forms of appeals can be modelled as explanatory arguments. In what follows, we will show through examples how such appeals are defined as explanatory arguments.

An appeal to prevailing practice: In this case, the agent believes that the opponent agent refuses to perform the requested action since it contradicts one of its own goals. However, the agent gives a counter-example from a third agent's actions, hoping it will serve as a convincing evidence. Of course, the third agent should have the same goals as the opponent and sould have performed the action successfully.

Example 7 An agent P asks another agent C to make overtime. C refuses because it is afraid that this is punished by law. The bases of C are then: K = {(overtime → T oBeP unished, 1)}, G = {(¬T oBeP unished, 1)} and GO = ∅. When the opponent C receives the offer overtime, it constructs an explanatory argument in favor of T oBeP unished: <{overtime, overtime → T oBeP unished}, T oBeP unished>.

This argument confirms to him that its goal will be violated then it refuses the offer. The proponent P reassures him by telling that another collegue makes overtime and it never has problems with law. In fact, it presents the following counter-argument: <{overtime, ¬T oBeP unished}, ¬(overtime → T oBeP unished)>. This last argument is an appeal to prevailing practice.

An appeal to past promise: In this case, the agent expects the opponent agent to perform an action based on past promise. Let's illustrate it by the following example:

Example 8 A child asks his mother to buy a gift to him and the mother refuses. The child points out that she promised to buy something to him if he succeeds at his examinations. The bases of the child are: K = {(success, 1), (success → gif t, 1)}, G = {(gif t, 1)} and GO = ∅. The child's argument is then: <{success, success → gif t}, gif t>.

A counter-example: This argument is similar to "appeal to prevailing practice"; however, the counter-example is taken from the opponent agent's own history of activities. In this case, the counter argument produced by the proponent should be constructed from the beliefs of the opponent. In the case of example 7, the support of the counter-argument should be included in the base of C. Thus, C would have a conflicting base. These three types of arguments have the same nature and they are all deductive. They are defined logically as explanatory arguments. The nature of these arguments, however, plays a key role in the strategies used by the agents. For example, a counter-example may lead quickly the other agent to change its mind than an appeal to prevailing practice. In what follows, we denote by A x the set of arguments of nature x with x ∈ {t, r, e}.

The strengths of the arguments

In (Amgoud & Cayrol 2002a), it has been argued that arguments may have different forces according to the beliefs from which they are constructed. The basic idea is that arguments using more certain beliefs are stronger than arguments using less certain beliefs. Thus, a level of certainty is assigned to each argument. These certainty levels make it possible to compare arguments. In fact, an argument A is preferred to another argument B iff A is stronger than B. As mentioned before, each of the three bases <K, G, GO> is pervaded with uncertainty or equipped with priority levels. From these degrees, we first define the force of an explanatory argument.

Definition 4 (Force of an explanatory argument) Let

A = <H, h> ∈ A e . The force of <H, h> is F orce(A) = min{a i such that (ϕ i , a i ) ∈ H}.
Example 9 In example 6, the force of the explanatory argument <{conf erence, conf erence → Sydney}, Sydney> is 0.8. Whereas, the force of the argument <{cancelled, cancelled → ¬conf erence}, ¬conf erence> is 0.4.

Concerning the threats, things are different since a threat involves goals and beliefs. Intuitively, a threat is strong if, according to the most certain beliefs, it invalidates an important goal. A threat is weak if, according to the less certain beliefs, it invalidates a less important goal. In other terms, the force of a threat represents to what extent the agent (the agent sending it or receiving it) is certain that it will violate its most important goals. Formally:

Definition 5 (Force of a threat) Let

A = <H, h, φ> ∈ A t . The force of a threat A is F orce(A) = min(α, β) such that α = min{a i such that (ϕ i , a i ) ∈ H and (φ, β) ∈ GO ∪ G.
Note that when a threat is evaluated by the proponent (the agent presenting the threat), then (φ, α) ∈ GO. However, when it is evaluated by its receiver, (φ, α) ∈ G.

Example 10

In example 3 the force of the threat < {¬ f inish -work → overtime}, f inish -work, ¬overtime> is min(1, 0.7) = 0.7.

As for threats, rewards involve beliefs and goals. Thus, a reward is strong when it is for sure that it will contribute to the achievement of an important goal. It is weak if it is not sure that it will contribute to the achievement of a less important goal.

Definition 6 (Force of a reward) Let

A = <H, h, φ> ∈ A r . The force of a reward A is F orce(A) = min(α, β) such that α = min{a i such that (ϕ i , a i ) ∈ H and (φ, β) ∈ GO ∪ G.
Example 11 In example 5, the force of the reward <{f inish -work → high -budget, high -budget → high -salary}, f inish -work, high -salary> is 0.6.

The forces of the arguments makes it possible to compare different arguments as follows:

Definition 7 (Preference relation) Let A 1 and A 2 be arguments of A x . A 1 is preferred to A 2 , denoted by A 1 A 2 , iff F orce(A 1 ) ≥ F orce(A 2 ).
In fact, the forces of arguments will play two roles: in one hand they allow an agent to compare different threats or different rewards in order to select the "best" one. In the other hand, the forces are useful for determining the acceptable arguments among the conflicting ones.

Conflicts between arguments

Due to inconsistency in knowledge bases, arguments may be conflicting. In this section, we will show the different kinds of conflicts which may exist between arguments of the same nature and also between arguments of different natures.

Conflicts between explanatory arguments

In classical argumentation frameworks, different conflict relations between what we call in this paper explanatory arguments have been defined. The most common ones are the relations of rebut where two explanatory arguments support contradictory conclusions and the relation of undercut where the conclusion of an explanatory argument contradicts an element of the support of another explanatory argument.

Definition 8 Let <H, h>, <H , h > ∈ A e . <H, h> def eats e <H , h > iff ∃ h" ∈ H such that h ≡ ¬h", or h ≡ ¬h .

Example 12 (Continued) In example 6, the explanatory argument <{cancelled, cancelled → ¬conf erence}, ¬conf erence> undercuts the argument <{conf erence, conf erence → Sydney}, Sydney> whereas it rebuts the argument <{conf erence}, conf erence>.

Conflicts between threats / rewards

Two arguments of type "threats" may be conflicting for one of the three following reasons: the support of an argument inferes the negation of the conclusion of the other argument. This case occurs when, for example, an agent P threatens C to do β if C refuses to do α, and at his turn, C threatens P to do δ if P does β.

the threats support contradictory conclusions. the threatened goals are contradictory. Since a rational agent should have consistent goals, this case arises when the two threats are given by different agents.

As for threats, rewards may also be conflicting for one of the three following reasons: the support of an argument inferes the negation of the conclusion of the other argument. This occurs when an agent P promises to C to do β if C refuses to do α. C, at his turn, promises to P to do δ if P doesn't pursue β.

the rewards support contradictory conclusions. This kind of conflict has no sense if the two rewards are constructed by the same agent. Because this means that the agent will contribute to the achievement of a goal of the other agent regardless what the value of h is. However, when the two rewards are given by different agents, this means that one of them wants h and the other ¬h and each of them tries to persuade the other to change its mind by offering a reward.

the rewarded goals are contradictory. Formally:

Definition 9 Let <H, h, φ>, <H , h , φ > ∈ A t (resp. ∈ A r ).
<H , h , φ > def eats t <H, h, φ> (resp. <H , h , φ > def eats r <H, h, φ>) iff: H ¬h, or h ≡ ¬h , or φ ≡ ¬φ .

Note that the conflict relation between threats (or rewards) is generally symmetric.

Mixed conflicts

It is obvious that explanatory arguments can defeat threats and rewards. In fact, one can easily undercut an element used in the support of a threat or a reward. The defeat relation used in this case is the relation "undercut" defined above. An explanatory argument can also defeat a threat or a reward when the two arguments have contradictory conclusions. Finally, an explanatory argument may conclude the negation of the goal threatened (resp. rewarded) by the threat (resp. the reward). Formally: Definition 10 Let <H, h> ∈ A e and <H , h , φ> ∈ A t (resp. ∈ A r ). <H, h> def eats m <H , h , φ> iff: ∃h" ∈ H such that h ≡ ¬h" or h ≡ ¬h or h ≡ ¬φ.

Evaluation of Arguments

In classical argumentation, a basic argumentation framework is defined as a pair consisting of a set of arguments and a binary relation representing the defeasibility relationship between arguments. In such a framework, arguments are all considered as explanatory. However, in this paper we have argued that arguments may be of different natures. So the basic framework introduced initially by Dung in [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] will be extended.

Definition 11 (Argumentation framework) An argumentation framework is a tuple A e , A t , A r , defeat e , defeat t , defeat r , defeat m . This framework will return three categories of arguments:

The class of acceptable arguments. Indeed, the conclusions of acceptable explanatory arguments will hold and inferred from the bases. Conclusions of acceptable threats should also be considered. In fact, such threats are seen as serious ones. Finally, conclusions of acceptable rewards should be retained since the reward will be pursued.

The class of rejected arguments. An argument is rejected if it is defeated by an acceptable one. Conclusions of rejected explanatory arguments will not be inferred from the bases. Rejected threats will not be considered since they are weak or not credible. Similarly, rejected rewards will be discarded since they are considered as weak.

The class of arguments in abeyance. Such arguments are neither acceptable nor rejected.

In what follows, we will try to define what is an acceptable argument. Intuitively, it is clear that an argument which is not defeated at all will be accepted. C will denote the set of all the arguments of (A e , A t , A r ) which are not defeated. Due to the forces of the arguments, as in (Amgoud & Cayrol 2002a), we can accept some defeated arguments if they are stronger than any defeaters.

Definition 12

The set of acceptable arguments is C = {A ∈ A x such that ∀B ∈ A y , A B}.

Illustrative example

Let us illustrate the proposed framework in a negotiation dialogue between a boss B, and a worker W . However, for the sake of simplicity, the strategy about decision moves is not discussed in detail. The knowledge base K B of B is made of the following pieces of information, whose meaning is easy to guess ('overtime' is short for 'ask for overtime'): K B = {(person-sick, 1), (person-sick → late-work, a 1 ), (latework ∧ ¬ overtime → ¬ finished-in-time, a 2 ), (overtime → finished-in-time, 1), (¬ finished-in-time → penalty, 1), (overtime → pay ∨ free-day, 1), (pay → extra-cost, 1)} with a 1 > a 2 . Possible actions for B are represented by their effects under the form of fully certain propositions: A B = {(T, 1), (overtime, 1), (pay, 1), (free-day, 1)}, where T denotes the tautology and corresponds to the result of the action 'do nothing'. On his side, W has the following bases: K W = {(person-sick → late-work, d 1 ), (overtime → late-work, 1), (late-work ∧ pay → overtime, d 1 ), (free-day → get-free-time, 1), (pay → get-money, 1), (¬ late-work, d 2 )}, with d 1 > d 2 . G W = {(¬ overtime ∨ pay, 1), (get-money, e 1 ), (¬ overtime, e 2 ), (getfree-time, e 3 )} with e 1 > e 2 > e 3 , GO W = {(¬ pay, f)}. For the sake of simplicity, the set of possible actions of W is not used in the example.

Here it's a sketch of what can take place between B and W . In the current situation (person-sick, 1), B is led to choose the actions 'overtime' and "free-day" (according to a regulation he knows in K B ). Indeed it can be checked that this decision maximizes in A B a pessimistic qualitative utility [START_REF] Dubois | Logical representation and computation of optimal decisions in a qualitative setting[END_REF]; see [START_REF] Dubois | Decisiontheoretic foundations of qualitative possibility theory[END_REF] for axiomatic justifications. More precisely, "overtime" maximizes a such that (K Ba ), overtime (G B ) 1-a , where (K Ba ) is the set of formulas having a level of certainty at least equal to a, (G B ) 1-a is the set of goals with a priority strictly greater than 1 -a.

Here (K B ) a2 , overtime ¬penalty with (G B ) b1 = {¬ penalty}. If B does nothing (action (T,1)), K B P L (penalty, min(a 1 , a 2 )) (where P L denotes the possibilistic logic consequence relation [START_REF] Dubois | Possibilistic logic. Handbook of Logic in Artificial Intelligence and Logic Programming[END_REF]. This would contradict his most prioritary goal in G B . The chosen action only contradicts his less prioritary goal, namely "free-day". B knows also that overtime is a threat for W , but not so strong (c ¡ 1) according to GO B . When W receives the command overtime, it challenges it since it believes ¬overtime (indeed K W P L (¬overtime, d 2 )), due to the argument {(overtime → late-work, 1), (¬ late-work, d 2 )}. Then B provides the explanatory counter-argument {personsick, person-sick → late-work}. Then W accepts to revise his knowledge base by accepting (late-work, 1), since he ignored (person-sick, 1). Although "free-day" is a reward for him with strength e 3 (according to K W and G W ), he still does not endorse "overtime", which is thus not perceived as a threat for him. Indeed according to K W , the only case when he is obliged to accept "overtime" is under the two conditions "late-work" and "pay". When B sees that W does not endorse "overtime", he regretfully proposes "pay" (since it violates his secondary goal), and considers that it is a strong "reward" for W (according to GO B ). W feels B's offer a bit as a threat, that he cannot escape here by doing something), since it violates his third goal; it's also a reward since it pleases his three other goals!

Conclusion

Argumentation-based negotiation focuses on the necessity of exchanging arguments during a negotiation process. In fact, an offer supported by an argument has a better chance to be accepted by the other agent. In [START_REF] Kraus | Reaching agreements through argumentation: a logical model and implementation[END_REF], a list of the different kinds of arguments that may be exchanged during a negotiation has been addressed. Among those arguments, there are the threats and the rewards. The authors have then tried to define how those arguments are generated. They presented that in terms of speech acts having pre-conditions. Later on in [START_REF] Ramchurn | Persuasive negotiation for autonomous agents: a rhetorical approach[END_REF], the authors have tried to give a way for evaluating the force of threats and rewards. However no formalization of the different arguments has been given. The aim of this paper is twice. First, it presents a logical framework in which the arguments are defined, the different conflicts which may exist between them are described, the force of each kind of arguments is defined in a clear way on the basis of the different bases of an agent and finaly the acceptability of the arguments is studied. This work can be seen as a first formalization of different kinds of arguments. This is beneficial both for negotiation dialogue and also for argumentation theory since in classical argumentation the nature of arguments is not taken into account or the arguments are supposed to have the same nature. An extension of this work will be to study more deeply the notion of acceptability of such arguments. In this paper we have presented only the individual acceptability where only the direct defeaters are taken into account. However, we would like to investigate the notion of joint acceptability as defined by Dung in classical argumentation. We are also planning to investigate more deeply the language used in our framework. In fact, in this paper we have used a propositional language and thus no distinction is done between a fact and an action. Another perspective of this work is to investigate the integration of this framework in the more general architecture of a negotiation dialogue introduced in [START_REF] Amgoud | Reaching agreement through argumentation: A possibilistic approach[END_REF].

  Goals of B are given by G B = {(¬ penalty, b 1 ), (¬ extra-cost, b 2 ), ¬ free-day, b 3 )}, with b 1 > b 2 > b 3 . What he thinks are the goals of W are GO B = {(pay, 1), (¬ overtime, c)}.