Yunfan Lai

THE POLYSEMOUS LIĀH 力 IN EARLY MODERN SOUTHERN MIN AND ITS CONTEMPORARY FATE 1

Keywords:

come

INTRODUCTION

The character 力 liāh was used in Early Modern Southern Min 2 for multiple purposes. It not only retained its original meaning as a lexical verb, 'to catch, to take, to seize' [START_REF] Lien | Grammatical function words 乞, 度, 甲, 將 and 力 In Li4 Jing4 Ji4 荔鏡記 and their development in Southern Min[END_REF], but also developed alternative verb uses, and furthermore underwent grammaticalisation into a polysemous case 2 marker. Productive as it was in the Ming dynasty, 力 liāh might however well have suffered twists and turns with the vicissitude of Chinese dynasties, and is only used as a verb contemporarily, with only a few fossilised traces of grammatical morpheme. This paper aims to account for the main functions of 力 liāh in Ming and Qing dynasties with typological analyses. In the first place, in Section 2, I will talk about the orthographic variants of this morpheme, 力 and 掠 in different versions of script plays; in Section 3, I will briefly discuss the etymology of 力 liāh; Section 4 describes the verb uses of 力 liāh. From Section 5 to Section 7, 力 liāh as a grammatical morpheme will be taken care of, before Section 8 comes up with some ambiguous constructions concerning this character. In Section 9, competing markers such as 共 kāng and 甲 kap will be mentioned. Section 10 focuses on the contemporary uses of 力 liāh and the paper comes to a conclusion in Section 11 with a discussion.

ORTHOGRAPHIC VARIANTS

The morpheme liāh has three orthographies in Ming and Qing dynasties, 力, 扐 and 掠.

力 is the only character used in the Jiājìng version of Lì Jìng Jì and The Classical theatre and art song of South Fukien (van der Loon 1992) (dating from 1604, within the reign of 萬曆 Wànlì (1572-1620) in the Ming dynasty), which indicates the Chôan-Chiu (泉州) origin of their authors. In contemporary Chôan-Chiu, 力 is pronounced liāk [START_REF] Lin | Quanzhou Fangyanzhi 泉州方言志 (The Chôan-Chiu Dialect)[END_REF], not sounding too far from liāh; we however have enough evidence to show that this contemporary pronunciation is irregular: in the historical Chôan-Chiu dictionary of Hùiyīn miàowù [START_REF] Hong | Huiyinmiaowu yu Gudai Quanzhouyin 《彙音妙悟》與古代泉州音 (Huiyinmiaowu and the Old Chôan-Chiu Pronunciation)[END_REF], dating back to 1800, the colloquial pronunciation of 力 (represented as 掠) was under the rhyme class 京 -iaⁿ, indicating liāh or liāⁿh, without the velar coda.

扐 is found in Arte de la lengua Chio Chiu [START_REF] Klöter | Arte de la Lengua Chio Chiu: Ms. 1027, Biblioteca de la Universidad de BarcelonaL Transcript and English Translation[END_REF]) (Chioⁿ-Chiu 漳州 dialect), with two glosses: 'to catch, to hold' as a verb and classifier of textiles. We are not sure if 扐 as a classifier is of the same origin of liāh in this paper, therefore it will not be discussed here.

With Hùiyīn miàowù, we know that the character 掠 was accepted by Chôan-Chiu people in 1800. However, the script play case must be studied The choice of 掠 to represent liāh shows that its users spoke a dialect in which 力 did (and probably still does) not sound similar to liāh. Such dialects are generally spoken in the Southern part of Southern Min speaking regions. It is presumably the Tiê-Chiu dialect 潮州, as Wu (2001b) suggests in the preface. In Tiê-chiu, 力 is pronounced lak 5 and 掠 liaʔ 5 (Lin & Chen 1996: 283, 293). Furthermore, apart from 看 kʰòaⁿ 'to look', we notice the coexistence of 体 thóiⁿ in these resources, which is the common word for 'to look' in modern Tiê-Chiu dialects 3 .

Therefore, the versions with 掠 as liāh should be treated with caution that it might reveal dialectal variance in Early Modern Southern Min.

The figures below show the photocopies of 力 and 掠 in their original appearance.

(a) 掠 in Wànlì (b) 力 in Jiājìng Summing up all the evidence above, 搦 'to press, to hold, to catch' seems to be the best candidate for the etymology of 力 liāh.

VERB USES

The original meaning of liāh, 'to catch, to hold', is attested in the Ming and The structure of example 1c is similar to the transitive constructions that we are going to talk about in Section 5, in which liāh will be analysed as an object marker. However, in this example, the conjunction 便 piān, marking the succession of two events, indicates that liāh should be the predicate of the first event.

Other verb uses are illustrated in 2.

(2) In 2a (written as 掠), liāh takes the meaning of a perception verb, 'to consider as'; 2b is an antithetical pair of clauses, with 有 ū 'to have' in the first clause corresponding to our 力 liāh in the second. These two verbs should have similar meanings given the situation, therefore, liāh in this case has less of an action verb meaning, and more of a stative one: 'to possess, to have'; In 2c, liāh appears as a causative verb, 'to cause to do'.

TRANSITIVE OBJECT

In Southern Min of the Ming Dynasty, liāh has already developed into a grammatical word, with the first function of liāh to be noticed being the object marker of transitive constructions. liāh occurs formally in the following syntactic constructions as an object marker (see also Lien 2010: 46) In the following subsections, I will first examine the referentiality of liāh-marked objects in 5.1, and the affectedness of the verbs available for liāh constructions from 5.2 to 5.3.

Referentiality and definiteness

Referentiality, as defined by [START_REF] Li | Mandarin Chinese: A Functional Reference Grammar[END_REF], is the fact that a noun phrase is used to refer to an entity. This entity may be physical or conceptual, real or hypothetical, singular or plural. A referential noun phrase can be definite or indefinite.

Southern Min is overwhelmingly an SVO language. However, when the object marker is used, the object itself must be preposed. Such construction is often referred to as the 'disposal construction' in the Sinitic tradition, and a great deal of accounts have been put forward for Standard Mandarin and other Chinese dialects.

In Standard Mandarin, for instance, the disposal construction in 把 bǎ is used with strict semantic constraints. In her chapter on differential object marking in Sintic languages, Chappell (2016) Even those objects without any formal indication of referentiality can be proven to imply definite referentiality:

(8) 故意 力-鏡 打-破 kò•.ì liāh-kiàⁿ pʰah-pʰòa deliberately LIAH-mirror
hit-break You deliberately broke the mirror. (嘉靖 19.216) In the episode from which example 8 is drawn, Tân-Saⁿ (陳三), who disguised himself as a mirror polisher, deliberately broke the mirror of Ngō-Niû (五娘), whom he had a crush on. In order to be able to see Ngō-Niû, he tried to frame the maidservant, Ek-Chhun (益春) with the breaking of the mirror. Driven mad, Ek-Chhun shouted at Tân-Saⁿ, "It's you that were trifling with the expensive mirror and it's you that deliberately broke the mirror!"

Given the situation, it is obvious that 鏡 kiàⁿ, even though unmarked, is actually referential to the expensive mirror owned by Ngō-Niû, and broken by Tân-Saⁿ. It represents old or given information.

Examples involving a noun phrase marked by liāh marked by the character 一 chit 'one' are rare, only 7 examples are found in all the five versions of Lì Jìng Jì:

(9)

力-一-鼎 打-破 liāh-chit-tiáⁿ pʰah-pʰòa LIAH-one?-wok hit-break He broke the wok. (順治 9.384) To account for this irregularity, we have two hypotheses. First, these examples are all from the versions of the Qing dynasty, more than a hundred years later than the first version. It could be due to the evolution of the marker, for which the semantic constraints have become looser. Second, we suspect that the character 一 chit is a mistaken form for the homophonous definite marker 只 chit. We cannot determine which of the hypotheses to choose, but the rarity of 一 chit does not have a big enough impact on the general referential reading of the noun phrase marked with liāh, even if 一 chit is really an exception.

Affectedness Hierarchy

Before looking into the semantic roles of the objects and the verbs suitable for liāh constructions, it is worthwhile to introduce [START_REF] Tsunoda | Remarks on Transitivity[END_REF]'s AF-FECTEDNESS HIERARCHY which deals with transitive verb types. In this paper, we adapt a simplified version of the Hierarchy, presented in the following table: In the hierarchy, the leftmost type of verb, having a direct affect on object, tends to have an argument that is most likely to be marked as patient (if the language in question does mark the patient). The degree of patientlikeness decreases as the hierarchy goes rightwards. Therefore, if we consider the Mandarin case, we can easily find that only the resultative verb (Type 1a), implying a change of state on the patient, is suitable for the disposal bǎ construction. In the following subsections, I will discuss the case of Early Modern Southern Min.

INSTRUMENTAL

Early Modern Southern Min also uses liāh to mark the instrument. This construction ressembles a serial verb construction, and may be interpreted alternatively as a serial verb construction, as [START_REF] Lien | Grammatical function words 乞, 度, 甲, 將 and 力 In Li4 Jing4 Ji4 荔鏡記 and their development in Southern Min[END_REF]

SUMMARY OF THE FUNCTIONS

A summary of the functions of liāh is provided in Table 3 10 below.

Table 3: Functions of liāh and their proportions

The first five rows show the data of different versions of Lì Jìng Jì in their chronological order. The last three lines are those of the other resources, also chronologically ordered. The grey-coloured rows are texts using 掠 as liāh.

The data listed in the table above are not directly usable without the following precisions:

1) The sample size of liāh is relatively small for a detailed and significant statistic analysis. Resources with total liāh counts lower than 70 are to be treated with caution.

2) We are not including the data of van der Loon (1992), as in many cases, the characters are hardly recognisable or simply missing. However, examples will be cited when necessary.

3) Script plays with 掠 may show diactectal variance, which will be discussed later on. They are to be treated separately.

Summary of verb uses

Looking through the five versions of Lì Jìng Jì, we can see that the meaning 'to catch, to hold' is relatively stable, of around 30% to 40% (the Dàoguāng version, with lower than 20%, has however only 67 occurrences of liāh, which is hardly significant).

Most of the causative verbs are in ambiguous constructions (c.f. Section 8), we have only one instance of pure causative use, in van der Loon (1992) (see example 2c).

The stative meaning of liāh is extremely uncommon, only found in van der Loon (1992) (example 2b).

The distribution of liāh meaning 'to consider as' (including the fossilised expression 掠做 liāh.chò 'to consider as'), interestingly, is found to be limited to the script plays using 掠. This could indicate the early innovation of South-Western Southern Min, probably the Tiê-chiu dialect.

Summary of marker uses

From Jiājìng to Guāngxù, the patient marker use of liāh undergoes a slight decrease in frequency. The percentage of perception object use is low but stable, while the one in Wànlì (another dialect) is higher than the other versions. Instrument use is not common, either, of around 5% in each version.

Whether or not the phenomena observed here are related to the evolution of Southern Min will be discussed in Section 11.

AMBIGUOUS CONSTRUCTIONS

Ambiguity may rise due to syntactic, semantic or pragmatic properties.

Whereas all types of ambiguity are included in the statistics in Table 3, in this section, I will focus on the syntactic and semantic types. Four main classes of ambiguity will be accounted for, object marker vs causative verb, object marker vs instrumental marker, object marker vs verb 'to catch' and verb 'to catch' vs instrumental marker.

Object marker vs Causative verb

The ambiguity between an object marker and a causative verb rises when the transitivity of the main verb can be interpreted in two ways. For instance, 閃 siám in 20a can be either transitive 'to wrench' or intransitive 'to be wrenched', which leads to two possible translations. 嫁 kè in 20b can be either ditransitive 'to marry sb. to sb.', or intransitive 'be married to sb.', the two readings both match the context semantically. The context of 22 allows the interpretation of 'to catch', we therefore cannot determine whether it is a real object marker or an action verb.

Verb 'to catch' vs Instrumental marker

The hesitation to choose between verb 'to catch' and intrumental marker is also caused by semantic properties, as 23 shows. Here, liāh can be interpreted either as a verb or an instrumental marker. This example is different from 17 in that the noun phrase following liāh is marked with definite article 只 chit, which makes it less likely to be a canonical instrumental argument (c.f. Givón 1995).

COMPETING MARKERS

將 chiong

The marker 將 chiong can appear as an object marker as well as an instrumental marker in Early Modern Southern Min. Identical constructions of 將 chiong and 力 liāh are put together in 24, 25 (object marker) and 26 (instrumental marker), some of which come from the same texts.

According to (Lien 2002:192), the noun phrase marked by 將 chiong is more often than not inanimate, unlike the case of 力 liāh. We will see that the noun phrases marked by 將 chiong enjoy a larger range than those marked by 力 liāh, as far as semantic roles are concerned. It is an analogy of the disposal construction, with 踏入門去 tāh jīp mn̂g kʰì (step-in-door go) as the original construction. This example shows that 將 chiong enjoyed looser usage constraints than 力 liāh. 9.2 甲 kap and 共 kāng 甲 kap and 共 kāng are worth mentioning as they are often found in disposal constructions in Modern Southern Min (Lien 2002: 194-195), although not quite so in the Ming dynasty. [START_REF] Lien | Grammatical function words 乞, 度, 甲, 將 and 力 In Li4 Jing4 Ji4 荔鏡記 and their development in Southern Min[END_REF] summarises the functions of 甲 kap and 共 kāng in Lì Jìng Jì.

In Southern Min of Ming and Qing dynasties, 甲 kap and 共 kāng generally marked animate objects, especially human objects.

共 kāng appears often with dative and ablative functions that mark goal (28a) and source (28b). The original version, by John Bunyan, is "(but when they saw that they could not prevail), Obstinate went railing back (Bunyan 1684: Part I, Section I, 2.4)", which shows that liāh in this case does mark the object. This example is probably amongst the last productive uses of liāh as an object marker.

A limited number of Type 2 verbs are in fossilised construction with- Table 4 shows the contemporary usage of liāh in the Affectedness Hierarchy. We can clearly see that liāh as a marker moves rightwards to the very end of its old range of use. In the Ming dynasty, it could match verbs of both Type 1 and 2. Later on, it marked the objects of Type 1b and 2 verbs and now it is restricted to Type 2 unproductively.

The gaps that it left in Contemporary Southern Min are filled with the generalisation of 甲 kap. Although 甲 kap usually marked human objects in the Ming dynasty, but as Chappell et al. (2011: 39) pointed out, there is no longer any semantic constraints for this marker. We have shown that liāh in Early Modern Southern Min was a polysemous case marker as well as a polysemous lexical verb, and that one function could be ambiguous with another. The coexistence of various functions and different types of ambiguity suggest that liāh was undergoing more than one grammaticalisation pathway at that time.

The polysemy and polyfunctionality of the morpheme in question, however, reflects several principles of grammaticalisation put forward by [START_REF] Hopper | On some principles of grammaticalization[END_REF]. First, it is related to the LAYERING principle (Hopper 1991: 22), which states that the emergence of new grammaticalisation layers do not imply the loss of the older ones, which instead might occur in interaction with the new layers. In Early Modern Southern Min, liāh was undergoing different layers of grammaticalisation at the same time; second, the PERSIS-TENCE principle, referring to the fact that the grammaticalised morpheme might retain traces of its original lexical meaning. Persistence explains why we have ambiguous forms wavering between the original lexical verb and a case marker. Lord (1982: 287) observes the same phenomenon with kɛ 'to take/ACC' in Gã (Benue-Kwa, West Africa), which can be interpreted as a lexical verb 'to take' or an object marker.

The contemporary use of liāh is virtually restricted to its original verb meaning. [START_REF] Hopper | On some principles of grammaticalization[END_REF] talks about DIVERGENCE, which points out that while grammaticalisation, the original form may remain as an autonomous lexical element. In Southern Min, liāh never lost its original meaning, which moreover seems to be the most persistent one.

Foissilisation of liāh

The traces of the case marker use of liāh are all fossilised constructions with meanings similar to 'to consider as'. Historical resources tell us that liāh with this meaning is restricted to the script plays that used 掠 to represent this morpheme, that is to say, dialects in which 力 did not sound like liāh.

As I mentioned above, I suspect the dialect using 掠 in early script plays was Tiê-chiu, or at least a South-Western variant of Southern Min. Provisionally, we can call it the 掠 lüè-dialects, opposed to the 力 lì-dialects.

Guāngxù and Contemporary Southern Min

Although with a decreasing tendency, the Guāngxù (1875-1908) version of Lì Jìng Jì still contains the productive use of liāh as a case marker. However, as we discussed in Section 10, the case marker liāh already ceased to be productive at the end of the 19th century. The reason why Guāngxù still used liāh as a case marker is therefore not related to the natural evolution of the language, but probably to the archaism and tradition of script play writing. I will leave this field to more capable researchers.

Possible evolutionary pathways

Since Jiājìng is the earliest text known in Southern Min, we have no clue of how exactly liāh transformed from a verb to a grammatical word. It is however not impossible to put forward hypothetical grammaticalisation pathways based on the data we possess, especially the ambiguous constructions.

We have listed four major types of ambiguous constructions in Section 8:

S + V 1 + NP + V 2 → S + MARKER + NP + V (34)
In consequence, the reanalysis is responsible for two new constructions: a disposal construction parallel to OV constructions, and an instrumental construction.

(

) S + V 1 + NP + V 2 → S + OBJECT MARKER + NP + V (36) S + V 1 + NP + V 2 + (NP 2 ) → S + INSTRUMENTAL MARKER + NP 1 + V + (NP 2 ) 35
It would not be surprising that synchronic confusions between the object marker use and the instrumental marker use occasionally occur, as their surface structures are similar.

The instrumental construction further gives rise, possibly combining forces with the monotransitive perception object use, to the double-object perception formation, e.g. 力...做 (liāh + NP 1 + chò + NP 2 , see example 13c).

These pathways are by no means strange as far as sinitic languages are concerned. [START_REF] Peyraube | Zaoqi "ba" ziju de Jige Wenti 早期"把"字 句的幾個問題[END_REF]Peyraube ( ,1996) ) discusses the same processes in Medieval Chinese, in which the two serial verb constructions, 'V 1 +NP+V 2 ' and 'V 1 +NP 1 +V 2 +NP 2 ', developed into disposal and instrumental constructions respectively.

The causative verb is found ambiguous with the object marker only. [START_REF] Chappell | From Eurocentrism to Sinocentrism: the case of disposal constructions in Sinitic languages[END_REF] states that the Mandarin disposal marker, 把 bǎ, can be conceptually analysed as denoting a causal relationship between an event and an ensuing state of affairs. It is not unclear that many an example of disposal liāh can opt for a causative reading, especially with a resultative verb, such as 打破 pʰah.pʰòa 'to break' (see example 15a). Therefore, the causative verb use of liāh may well have developed from its transitive object use.

The stative use of liāh is only found in one example in the entire da- Thanks to script plays from the Ming and Qing dynasties, we have been able

to find productive uses of 力 liāh as a grammatical marker, which is completely extinct today. Nevertheless, the original verb use of 力 liāh is preserved in the contemporary language. It might be intuitive that newly emerged functions outlast older ones, the story of 力 liāh gives us a counterexample, its marker uses lost in the competition with other markers, and its oldest function persists until today.

Several tasks are to be completed for further studies.

Most of the elaborated works today on Southern Min concern the variants within Taiwan (which is a sad fact) and efforts on exploring and documenting Southern Min dialects in Fujian have not gone enough. Fieldwork in even the smallest villages in the territory of the homeland of Southern Min should definitely be done. We may find more information about liāh and even more insightful facts about the language there.

Comparative studies between lüè-dialects and lì-dialects must be put forward. The syntactic and lexical differences may amount to a considerable number concerning the dialectology of Early Modern Southern Min.

We should also look into other Sinitic languages, as well as languages around the world, in order to see how Early Southern Min studies can contribute to linguistic typology.

ABBREVIATIONS

  separately. 掠 is the only character used in script plays of two periods: the reign of Wànlì, with 明萬曆刊荔枝記 Míng Wànlì Kān Lìzhījì (Wu 2001b), 蘇六娘 Sūliùniáng (Wu 2002a) and 金花女 Jīnhuānǚ (Wu 2002b); and the reign of 乾隆 Qiánlóng of the Qing dynasty, with 同窓琴書記 Tóngchuāng Qínshū Jì (Wu 2003). In other script plays including 清順治刊荔枝記 Qīng Shùnzhì Kān Lìzhījì (Wu 2001d), 清道光刊荔枝記 Qīng Dàoguāng Kān Lìzhījì (Zheng 2010) and 清光緒刊荔枝記 Qīng Guāngxù Kān Lìzhījì (Wu 2001c), 力 is overwhelmingly used, whereas 掠 is also occasionally found, with 2 instances each in Shùnzhì, Dàoguāng and Guāngxù.

Figure 1 :

 1 Figure 1: Examples of 力 and 掠 in script plays

  observes that preverbal objects in Standard Mandarin must be referential and affected by a highly transitive predicate (which causes a change of state or a change of location). In Early Modern Southern Min, disposal constructions exhibit a similar pattern concerning referentiality of the object. In many a case, the object is also marked by the definite marker 只 chit, as shown by the liāh-chit-gôaⁿ-i tʰn̂g-kúi-tiông LIAH-DEF-cold.clothes take.off-several-time I took off several layers of my winter clothes. b. 力-只-春 來-留滯 liāh-chit-chʰun lâi-lâu.tè LIAH-DEF-spring come-let.stay To let this spring stay 8 . Ten out of 62 examples of liāh as an object marker are attested with the definite marker 只 chit. In other examples, we find pronouns, person names and body parts, etc., which are most likely to be specific and referential.

5. 3

 3 Patient 5.3.1 Proto-typical patient Type 1a verbs (resultative verbs) in Earlier Southern Min often involve a second resultative element such as 破 phòa 'break' or 上 siōng 'up', etc; others might not have any additional element, and can only be identified through their semantic context. We have already seen examples of the prototypical patient marked with liāh in 8 and 9 with the resultative transitive verb 打破 phah phòa. More examples are provided in 10. (10) a. 且 力-只-門掩-上 chʰiá liāh-chit-mn̂g am-siōng CONJ-PATIENT-door shut-up So I shut the door. (嘉靖 28.021) b. 阮來 三哥 力-火 點-光光 只-處 睏 gôan.lâi saⁿ-ko liāh-hóe tiám-kng.kng chit-chʰù turn.out Saⁿ-Ko PATIENT-fire kindle-bright DEM-place kʰùn sleep It turns out that San-Ko lit the candle and slept there. (嘉靖 29.023) c. 益春 力-鋪陳 收-起 ek-chʰun liāh-pʰo.tîn siu-kʰí Ek-Chhun PATIENT-bed.clothes pack-up Ek-Chhun, pack up the bed clothes. (道光 31.064) 5.3.2 Non-resultative patient

  wrench/be.wrenched-one.time (a) He wrenched my waist. (b) He caused my waist to be wrenched. (道光 10.015) b. 卜力仔嫁乞-林大 bēh liāh kiáⁿ kè kʰit-lîm.tōa want LIAH daughter marry -DAT-Lîm.Tōa (a) They want to marry their daughter to Lîm Tōa. (b) They want to make their daughter marry Lîm Tōa. (嘉靖 14.422)8.2 Object marker vs Instrmental markerAs in a disposal construction, the object is preposed, it gives room to add another noun phrase as direct object behind the transitive verb, which creates a new OV construction. The original object, already fronted by the marker liāh, can be therefore considered demoted into an oblique function.As a result, the addition of the noun phrases 哀怨 ai.òan 'melancholy' in 21a and 就裏 chiū.lí 'reason' in 21b cause alternative readings in the examples below.

  play the pípa to convey melancholy (b) convey melancholy with the pípa (絃管 滿天春 上) b. 力 只-恩愛 從頭 共-伊說-出 拙-就裏 liāh chitTell her all about my love from the beginning. (b) Tell her the reason right from the beginning through my love. (道光 22.067) 8.3 Object marker vs Verb 'to catch' This class of ambiguity depends on the semantic interpretation of the text, and is found in ditransitive constructions. send my third brother to the government of ice (b) arrest my third brother and send him to the government of ice. (光緒 36.034)

  take a small fan to lick the fire flies (b) lick the fire flies with a small fan (絃管 滿天春 上)

  .break Inevitably broke this mirror. (嘉靖 19.173) b. 不免力-只-鏡來-打-破 m ̄.bián liāh-chit-kiàⁿ lâi-pʰah-pʰòa inevitably PATIENT-DEM-mirror to-hit.break Inevitably broke this mirror. (嘉靖 19.188) gift back to him. (嘉靖 14.177) b. 你 力-只-禮聘 送轉去 還-伊人 lí liāh-chit-lé.pʰèng sàng.tńg.kʰì 2SG PATIENT-DEM-betrothal.gift send.back hêng-i.lâng return-3SG Send this betrothal gift back to them (嘉靖 14.109) the lychee with a handkerchief. (順治 26.053) b. 伊 力-手帕 包 荔枝 掞-落-來 i liāh-chʰiú.pʰè pau nāi.chi 3SG PATIENT-handkerchief wrap lychee taⁿ-lōh-laî throw-downwards-come She wrapped the lychee with a handkerchief and threw it down. (嘉 靖 18.055)將 chiong has also extended functions, such as marking the path in 27.

  my mistress about it. (萬曆 06.024) b. 值人 卜 共-你-討恩 tī.lâng bēh kāng-lí-tʰó.un who want DAT-2SG-ask.favour Who wants to ask a favour from you? (嘉靖 22.280) (29) a. 甲-啞媽 討一-對-金花 kah-a.ma tʰó chit-tùi-kim.hoe SOURCE-mother require one-pair-gold.flower Ask the mother for a pair of lowers. (嘉靖 13.114) b. 甲-你-鏡 打-破-除 kah-lí-kiàⁿ pʰah-pʰòa-tû PATIENT-2SG-mirror hit-break-PFV He broke your mirror. (嘉靖 19.346) c. 甲-我 來-賣-乞-人-飼 kah-góa lâi-bōe-kʰit-lâng-chʰī PATIENT-1SG to-sell-DAT-person-feed They sold me to others. (嘉靖 13.050) 10. CONTEMPORARY USE Our contemporary data are mainly based on the database of National Tsinghua University, 台語文數位典藏 Tái Yǔwén Shùwèi Diǎncáng, and online dictionaries. The examples include contemporary folklores and narratives and date from 1880 up until now. The verbal meaning 'to catch, to hold' of liāh is by far the dominant use in Contemporary Southern Min, which represents over 90% of the occurrences by my estimate.The meaning 'to consider as' is retained, being fossilised with 做 chò and other similar verbs: 掠做 liāh.chò 'to consider as' , 掠準 liāh.chún 'to believe firmly', etc. be.like same Japanese people consider them as the same (pronunciation). (日本話 ê 根底 (1896))Surprisingly, liāh as an object marker is extremely rare in the contemporary language. Type 1a verbs of the Affectedness Hierarchy are never found with liāh, and I only found one example of Type 1b verbs: and returned. (天路歷程2 (1897))

  The fossilisation of liāh clearly started with the lüè-dialects, more precisely, with the perception use of liāh. Of all 7 instances of perception use found in the lüè-dialects, 6 imply the meaning of 'to consider as' together with the main verb. All 13 instances of lexical use meaning 'to consider as' are from the lüè-dialects, with two of them combined with 做 chò 'to do'. Today, liāh alone cannot have the meaning 'to consider as', only 掠... 做 liāh...chò and 掠做 liāh.chò (and synonyms) are grammatical. The fossilisation of liāh must have moved northwards during the following four centuries. It expanded to the entire Southern Min speaking region.

Figure 3 :

 3 Figure 3: Relations between ambiguous constructions

Figure 4 :

 4 Figure 4: Hypothetical evolution of liāh

  Shuōwén, underlines that the meaning 'to catch, to hold' is recent 6 . Combined with the Guǎngyùn evidence, it is clear that the meaning of 搦 had already shifted to 'to catch, to hold' before the Ming Dynasty. Therefore, semantics-wise, the 搦 hypothesis is plausible.

The original meaning of the character 搦, as in 說文 Shuōwén (100-121 AD), was 'to press' 4 . The Guǎngyùn 廣韻 (1008 AD) has two entries for 搦, both with the meaning 'to catch' or 'to hold' 5 . Duàn Yùcái (段玉裁), in his Commentaries on Phonology-wise, Guǎngyùn gives two pronunciations of 搦: 女角切 (ɳaewk) and 女白切 (ɳaek). The two pronunciations in Middle Chinese have several different reflexes in Modern Southern Min. As for 女角切, we would expect *lōh in Modern Southern Min, which does not seem to be the right paraphrase; on the other hand, in the case of 女白切, we would well expect liāh as a regular correspondence, as unrounded rhymes in the 梗 gěng rhyme class, regardless of the rhyme grade, appear as -iah in Modern Southern Min

[START_REF] Lo | Xiamen Yinxi 廈門音系 (The Phonology of Amoy)[END_REF]

.

The Eastern Min cognate of liāh is nieʔ (Fúzhōu dialect,

Chen & Li 1991: 116)

. The correspondence Eastern -ieʔ :: Southern -iah traces back to Proto-Min *-iak, which matches perfectly the Middle Chinese unrounded 梗 gěng rhymes

(Norman 1981: 70)

. The n-onset of Eastern Min also indicates that the etymology cannot be 掠, the other candidate, whose onset comes from Proto-Min *l-.

Table 1 :

 1 Affectedness Hierarchy

	1		2	3	4	5	6	7
	Direct effect on object
	1a	1b	Perception Pursuit	Knowledge	Feeling	Relationship	Ability
	Resultative	Non-resultative
	打破 pʰah.pʰòa	打 pʰah	看 kʰòaⁿ	等 tán	記得 kì.tit	畏 ùi	有 ū	肴 gâu
	'break'	'hit'	'look at'	'wait	'remember'	'be afraid'	'have'	'be good at'

Table 2 :

 2 In Episode 24 of Lì Jìng jì, in a moonlit night, Tân-Saⁿ went to Ngō-Niû's garden, but hesitated about going in. He started making noises, in the hope that Ngō-Niû would hear him. Ngō-Niû did hear the noises, and asked Ek-Chhun, her maidservant if someone was outside. Ek-Chhun thought it was just a cuckoo, and this caused Ngō-Niû to fall into melancholy: springtime was too short, and even a cuckoo sang sad songs about it. Ek-Chhun asked Ngō-Niû if she was able to let springtime stay, and Ngō-Niû felt powerless to help. The question, uttered by Ek-Chhun, is in 14a, with a liāh construction. What Ngō-Niû answered about it is in 14b, with the same meaning, but using the VO construction.As an object marker, I have shown liāh is compatible with transitive verbs having a direct effect on object and perception verbs, which occupy the first and second slots of the Affectedness Hierarchy. See Table2for a better view of its distribution: liāh Constructions in Affectedness Hierarchy

	Type 1b verbs (non-resultative verbs) do not necessarily cause a change of
	state in the patient. Examples include:
	(11)	a. 你 力-媒姨 打 是 乜 道理
		lí	liāh-bôe.î	pʰah	sī	mih
		2SG	N.R.PATIENT-match.maker hit	be	what
		tō.lí
		reason
		Why did you hit the match maker? (嘉靖 14.254-55)
		b. 煩 你 力-書收
		hôan	lí	liāh-chu		siu
		please 2SG	N.R.PATIENT-letter	receive
		Please take this letter. (嘉靖 25.225)
		c. 力-君 來-攬
		liāh-kun		lâi-lám
		N.R.PATIENT-2SG	come.embrace
		Let me embrace you. (嘉靖 48.088)
		Such constructions are ungrammatical in Standard Mandarin (at least
	for the author), while well attested in Earlier Southern Min.
	5.3.3 Ditransitive constructions
	Ditransitive constructions can also be marked by liāh, illustrated by the sen-
	tences below:
	(12)	a. 你 力-荔枝手帕 獻 乞-我做-乜
		lí	liāh-nāi.chi.chʰiú.pʰè		hiàn	kʰit-góa
		2SG	PATIENT-handkerchief.with.lychee give	DAT-1SG
		chò-mih
		do-what
		Why did you give me the handkerchief with the lychee inside? (道
		光 22.202)
		b. 力-拙-恩愛 全頭 共-伊細說
		liāh-choat-un.ài	chôan.tʰâu	kāng-i

The next category in the Hierarchy, Type 2, perception verbs, are available for liāh constructions. Examples are shown in 13. 13a and 13b illustrate the perception use with simple transitive verbs, and 13c is somewhat structurally ambiguous, in which 力 liāh can be understood as the predicate, or alternatively, a grammatical word marking the observed object, 有心 iú.sim 'care', while 做 chòe 'make' being the predicate. Following the latter analysis, the construction can be termed a double-object perception contruction.

Table 4 :

 4 Contemporary liāh constructions

	1		2	3	4	5	6	7
	Direct effect on object
	1a	1b	Perception Pursuit	Knowledge	Feeling	Relationship	Ability
	Resultative	Non-resultative
	打破 pʰah.pʰòa	打 pʰah	看 kʰòaⁿ	等 tán	記得 kì.tit	畏 ùi	有 ū	肴 gâu
	'break'	'hit'	'look at'	'wait	'remember'	'be afraid'	'have'	'be good at'
	11. DISCUSSION
	11.1 The status of liāh in Southern Min

  Guojia Wenhua Yishu Jijinhui 國家文化藝術基金會.ZHENG, Guoquan (鄭國權). ed. 2010. Lijingji Lizhiji Sizhong "Disanzhong" Qingdai Daoguang Kanben Lizhiji Shuying ji Jiaodingben 荔鏡記荔枝記四種「第三種」清代道光刊本《荔枝记》书影及 校订本 (Four editions of Li Jing ji and Li Zhi Ji, No.3: Photocopies and Annotated Texts of Li Zhi Ji of Qing Daoguang Edition). Beijing 北京: Zhongguo Xiju Chubanshe 中國戲劇出版社.

		Tongchuang Qinshu Ji of Qing Qianlong Edition). Taipei 台北:
	1SG	first person singular	INSTR	instrumental
	1PL	first person plural	LOC	locative
	2SG	second person singular	NEG	negative
	3SG	third person singular	N.R.PATIENT	patient of non-resultative verbs
	3PL	third person plural	OBJ	object
	BEN		benefactive	PATH	path
	CAUS		causative 早期閩南語中"力 liāh"字之多重功能及其現代命運 PATIENT patient
	CL		classifier	PERCEPT 賴雲帆	perception
	CONJ		conjunction	PFV 巴黎第三大學	perfective
	DAT		dative	PROH	prohibitive
	DEF	提要	definite	PART	particle
	DEM	demonstrative 本文立足于明清閩南語文獻研究近代閩南語「力」liāh 的多重功能 SOURCE source
	DETRAN	detransitive 以及引致其多義性之語法化路徑。在早期閩南語中,力 liāh 既是表
		"捉、拿"的動詞,亦是一個多功能的格標記。然而在當代閩南語中,
		力 liāh 的動詞功能尤為顯著,其格標記用法則幾乎丧失能產性。研
		究力 liāh 的歷史可為語言類型學提供有用的材料。
		關鍵詞
		早期閩南語 荔鏡記 賓語標記 語法化 受動性等第

NOTES 1 The research leading to this paper has received funding from the French Agence Nationale de la Recherche (ANR) for the project entitled «Typologization of synchronic and diachronic processes in Southern Min, a Sinitic language», (TYSOMIN) n° 11-ISH2-001-01, a bilateral cooperative project with the National Science Council of Taiwan (NSC), Principal investigator, Hilary Chappell and Co-investigator, Alain Peyraube. I would like to thank both of the investigators, Hilary Chappell and Alain Peyraube, for their useful comments regarding this paper. My sincere gratitude is also dedicated to Professor Lien Chin-fa and my colleague, Song Na, for their insightful discussions over the subject. I would also like to thank the anonymous reviewer for her/his detailed suggestions and corrections. All faults are mine.

2 c.f. The Southern Min spoken in the Ming Dynasty. The main resource we refer to is the 嘉靖 Jiā Jìng version of 荔鏡記 Lì Jìng Jì, which dates to the th century (Wú 2001a).

3 In Jiājìng 5.025, we also attest an example of 体 thóiⁿ, which is said by Lim-Tōa, a character of Tiê-chiu origin.

4 按也, 從手弱聲 àn yě, cóng shǒu ruò shēng 'To press, its meaning follows the 'hand' part (手) and its pronunciation follows the 'weak' part (弱).' 5 持也 chíyě 'to hold'; 捉搦又正也 zhuō nuò yòu zhèng yě' to catch, or to straighten' 6 搦猶捉也。此今義、非古義也。nuò yóu zhuō yě. cǐ jīn yì, fēi gǔ yì yě.

'搦 means to catch. This is a recent meaning, not an archaic one. ' 7 In this case, 阮 góan '1PL' is in its singular use.

35 8 We will see in Section 8 that this example can also be interpreted as a causative construction, while it would better be understood as a disposal one, according to the context (c.f. Example 14a)


Nawal Benabbou

Patrice Perny

Paolo Viappiani

A regret-based preference elicitation approach for sorting with multicriteria reference profiles

Keywords: Multicriteria sorting, capacity, Choquet integral, fuzzy preference relations, ordered categories

In this paper we present an incremental elicitation method to determine the importance of the coalitions of criteria in a multicriteria sorting method. The method is designed to assign alternatives to predefined categories by comparing their performance vector to reference profiles. These comparisons lead to binary preference indices that are aggregated to determine the membership of the alternatives to predefined categories. We present an active learning process to determine the weighting coefficients modeling the importance of criteria in the aggregation process. Learning examples are generated one by one and presented to the Decision Maker to efficiently reduce the uncertainty attached to criteria weights. The process is stopped when all alternatives can be assigned to a category with the desired guarantee. We present the formal elicitation method as well as numerical tests showing its practical efficiency.

Introduction

The evaluation of alternatives is a critical task in all decision support methods. When the alternatives must be evaluated with respect to multiple criteria, several aggregation procedures have been proposed to assess the overall value of the alternatives, either to rank them by decreasing order of preference, or to assign them to predefined ordered categories on the basis of their intrinsic value. In this paper, we focus on the latter objective and we consider multicriteria evaluation methods assessing the intrinsic value of alternatives by comparing their performances to predefined reference levels.

In this family of methods, we can distinguish two approaches. The 'aggregate then compare' approach consists in a two stage process that first aggregates the performances of every alternative to produce an overall rating (e.g. using a weighted sum) and then compares the resulting rating to reference levels to assign the alternative in a predefined category (e.g., good, medium, bad). For example, alternatives are labelled as 'good' when they rate beyond 10, as 'bad' when they rate below 5, and as 'medium' otherwise. The main drawback of this first approach is that it is often difficult to derive a significant rating from criterion values expressed on different scales.

The second approach overcomes this problem by swapping the aggregation and comparison steps; for this reason, it is named the 'compare then aggregate' approach. This approach requires an ordered sequence of reference profiles to be defined, representing different levels of requirements in the space of criteria; these profiles are totally ordered using Pareto dominance. A category is then implicitly defined by all the alternatives that beat a given reference profile but no other reference profile ranked higher in the dominance order. Thus, reference profiles act as upper and lower bounds of categories. This way of assigning alternatives to ordered categories while using multicriteria evaluations has been initally introduced by Roy in the Electre TRI method [START_REF] Moscarola | Procdure automatique d'examen de dossiers fonde sur une segmentation trichotomique en prsence de critres multiples[END_REF][START_REF] Roy | A multicriteria analysis for trichotomic segmentation problems[END_REF][START_REF] Roy | The outranking approach and the foundations of electre methods[END_REF][START_REF] Dias | Electre tri-c : A multiple criteria sorting method based on characteristic reference actions[END_REF]. Then multiple variants of this method have been proposed, based on a similar scheme [START_REF] Mousseau | Inferring an ELECTRE TRI model from assignment examples[END_REF][START_REF] Perny | Multicriteria filtering methods based on concordance and nondiscordance principles[END_REF][START_REF] Zopounidis | Multicriteria classification and sorting methods: A literature review[END_REF][START_REF] Greco | Multiple criteria sorting with a set of additive value functions[END_REF] and known as 'multicriteria sorting methods'. They have been widely used in various applications (see the above references) and also investigated axiomatically [START_REF] Bouyssou | An axiomatic approach to noncompensatory sorting methods in MCDM, I: The case of two categories[END_REF][START_REF] Bouyssou | An axiomatic approach to noncompensatory sorting methods in MCDM, II: More than two categories[END_REF].

The 'compare then aggregate' approach requires a preference relation to be defined in the space of criteria in order to compare performance vectors of alternatives to reference profiles. This preference relation is usually defined by aggregating the preference relations derived from each criterion considered separately. The aim of this paper is to learn from examples the proper aggregation method to be used to produce the aggregated preference relation. The most common aggregation method used for aggregating preference relations derived from criteria is a weighted majority rule. In this case, the weights of criteria must be learned from examples. This problem has been studied in [START_REF] Mousseau | Inferring an ELECTRE TRI model from assignment examples[END_REF][START_REF] Mousseau | A useroriented implementation of the ELECTRE-TRI method integrating preference elicitation support[END_REF][START_REF] Leroy | Learning the paraeters of a multiple criteria sorting method based on a majority rule[END_REF][START_REF] Sobrie | Learning a majority rule model from large sets of assignment examples[END_REF].

More recently, an extension of this approach has been proposed in [START_REF] Sobrie | Learning the parameters of a non compensatory sorting model[END_REF] based on a generalization of weighted majority using a set function (namely a capacity) weighting any subset of criteria. This generalization enhances the descriptive power of the weighted majority model by allowing positive or negatives synergies among criteria due to the use of a non-necessarily additive definition of criterion weights. In this paper, we generalize this approach in a number of directions. First, we consider a generalized aggregation method to assign alternatives to categories. This method, introduced in [START_REF] Perny | Multicriteria filtering methods based on concordance and nondiscordance principles[END_REF], uses fuzzy preference relations to compare alternatives to references profiles and defines a degree of membership of any alternative to any categories (this method will be formally specified in Section 2). Secondly, the aggregation of fuzzy preference relations is performed using a possibly non linear weighted aggregator, for example the Choquet integral that combines fuzzy preferences with a non-additive measure of the importance of criteria. The learning of classifiers based on a Choquet integral has been investigated in [START_REF] Hüllermeier | Efficient learning of classifiers based on the 2-additive Choquet integral[END_REF]. Our approach is different because we use here the Choquet integral to aggregate fuzzy preferences rather than criterion values. Thirdly, instead of proposing a passive learning approach aiming to assess weighting parameters from a given database of examples, we propose here an active learning of the capacity that progressively asks examples of assignment to the Decision Maker (DM), selected one by one to efficiently reduce the set of possible capacities until a complete assignment of the alternatives can be defined with confidence.

The paper is organized as follows: in Section 2, we recall the main features of the assignment method introduced in [START_REF] Perny | Multicriteria filtering methods based on concordance and nondiscordance principles[END_REF]. Then, the incremental approach proposed to elicit the aggregation function is presented in Section 3. Finally, numerical tests showing the efficiency of the approach are presented in Section 4.

Sorting using reference profiles

Let K , ∈ {1, . . . , q}, be a set of q ordered categories, K1 being the best category and Kq being the worst one. Let X be the set of alternatives that must be assigned into one of these categories. Let us assume that every alternative is represented by a performance vector x = (x1, . . . , xn) ∈ R n where xi denotes the performance of x with respect to criterion i, i ∈ N = {1, . . . , n}; we assume here that criteria are to be maximized. Let us denote {r 0 , r 1 , . . . , r q } the set of reference profiles used to defined the bounds of the categories. Each element r ∈ R n defines the lower boundary of category K , ∈ {1, . . . , q}, while r 0 ∈ R n represents a top performance profile (not feasible) chosen to bound above all possible criterion values. These reference profiles are defined in such a way that r i > r +1 i for all i ∈ N and ∈ {0, . . . , q -1}.

These reference profiles being defined, the principle of a preferencebased assignment method is to assign x to category K when x is preferred to r and x is not preferred to r -1 . In the method introduced in [START_REF] Perny | Multicriteria filtering methods based on concordance and nondiscordance principles[END_REF], this principle is implemented by comparing x to all profiles r using a preference index defined as follows:

P (x, r , θ) = f θ (P1(x, r ), . . . , Pn(x, r )) (1)
where f θ is an aggregation function (compatible with Pareto dominance) parameterized by θ and Pi(x, r ) is a monocriterion preference index defined by:

Pi(x, r ) =      1 if xi -r i > γ + i x i -r i -γ - i γ + i -γ - i if γ - i < xi -r i ≤ γ + i 0 if xi -r i ≤ γ - i
The variation of index Pi(x, r ) as the difference xi -r i increases is represented here below:

xi -r i Pi(x, r ) 1- 0 | γ - i | γ + i Figure 1. Preference index P i (x, r ) as a function of x i -r i
This index represents the credibility of the statement "x is better than r w.r.t criterion i". The index is maximal (i.e. equals 1) when the score difference xi -r i exceeds the preference threshold γ + i . It is minimal when the difference xi -r i falls below the indifference threshold γ - i . These thresholds are part of the definition of the criterion scale and are defined by the DM in such a way that γ + i > γ - i . The preference threshold γ + i defines the minimal difference compatible with a strict preference, whereas the indifference threshold γ - i represents the maximal score difference compatible with an indifference (absence of preference). Between these two thresholds, there is an area where we may hesitate between strict preference and indifference; in this area, the preference index grows linearly with xi -r i (see Figure 1).

A standard choice for f θ is a compromise operator, i.e. that verifies mini∈N {xi} ≤ f θ (x) ≤ maxi∈N {xi} for all x = (x1, . . . , xn) ∈ R n . When using such an operator, the overall preference index P (x, r , θ) defined by Equation ( 1) necessary belongs to [0, 1]. Value 1 is achieved when the criteria are unanimously in favor of strict preference, whereas value 0 is achieved when criteria are unanimously against preference. Between these two extreme cases, the overall index measures the strength of arguments supporting the statement "x is better than r ". A common choice for f θ is the weighted sum f θ (p1, . . . , pn) = n i=1 θipi where θi is the weight attached to criterion i. A more interesting choice is to define f θ as a Choquet integral [START_REF] Grabisch | The application of fuzzy integrals in multicriteria decision making[END_REF][START_REF] Grabisch | Aggregation Functions (Encyclopedia of Mathematics and Its Applications[END_REF] which provides a more general and more flexible aggregator. In this case, θ is the set function defining the weight of any coalition of criteria. We will come back to this case in Section 3.2.

After the aggregation step, the index measuring on the [0, 1] scale the membership of any alternative x to any category K , ∈ {1, . . . , q}, is defined by:

m (x, θ) = min P (x,r ,θ), 1-P (x,r -1 ,θ) (2)
and finally, alternative x is assigned to category K * where * is the smallest index such that:

m * (x, θ) = max k∈{1,...,q} m k (x, θ)
This procedure is the general preference-based filtering method introduced in [START_REF] Perny | Multicriteria filtering methods based on concordance and nondiscordance principles[END_REF]. Equation ( 2) ensures that, for any fixed x and θ, m (x, θ) (seen as a function of ) is unimodal, with a maximum at least equal to 0.5 (for more details see [START_REF] Perny | Multicriteria filtering methods based on concordance and nondiscordance principles[END_REF]). This method is typical of the 'compare then aggregate' approach. We first compare any alternative x to all reference profiles by considering each criterion separately, which leads to indices Pi(x, r ), i ∈ N . These indices are then aggregated using function f θ to define the membership of x to any category K . The advantage of this approach, compared to the more classical 'aggregate then compare' approach lies in the use of reference vectors r instead of scalar thresholds on aggregated values. This provides a finer control in the definition of category boundaries in the multiobjective space. The decision of assigning an alternative is based on the scoring vector and not on an aggregated value: two alternatives having the same "average" value but different profiles may enter into different categories, as shown in the following example:

Example 1. Let us consider two alternatives x, y and a sequence of 3 reference profiles r 0 , r 1 , r 2 with the following grades on three criteria: The three reference profiles allow the definition of two categories K1 and K2. We use here the same valuation scale with a preference threshold γ + i = 1 and indifference threshold γ - i = 0, for all i ∈ N = {1, 2, 3}. Let us assume that f θ is the weighted sum with weights θ = (1/3, 1/3, 1/3), i.e. f θ (z1, z2, z3) = (z1 + z2 + z3)/3 for all z ∈ R n . We obtain P (x, r 0 , θ) = P (y, r 0 , θ) = 0 and P (x, r 2 , θ) = P (y, r 2 , θ) = 1. The only difference between x and y are due to profil r 1 . We indeed have: P (x, r 1 , θ) = 2/3 and P (y, r 1 , θ) = 1/3. Hence, using Equation (2), we get the following membership values:

1 2 3 x 6
m1 m2 x 2/3 1/3 y 1/3 2/3
As a consequence, x is here assigned to category K1 whereas y is assigned to category K2.

In this example, x obtains a better position than y (since K1 is better than K2). Note that alternatives x and y would be undiscernible with the 'aggregate then compare' approach since they have the same average: f θ (x) = f θ (y). Moreover, if the grade of y increases from 30 to 50 on criterion 1, it can easily be checked that y remains in K2. There is no improvement despite the fact that the average score of y defined by f θ increases. This is due to the fact that here, there is no point in improving its performance on criterion 1 since it already exceeds the value of reference profile r 1 while the weaknesses of y on criteria 2 and 3 remain. This example illustrates the non-compensatory nature of this sorting procedure, where difference of grades does not play any role beyond a given threshold; this is a clear difference with procedures based on the direct aggregation of criterion values.

3 An incremental approach for sorting alternatives using reference profiles

The procedure introduced in the previous section involves at some step an aggregation operation f θ in which parameter θ controls the importance of criteria and coalitions of criteria in the overall assessment of alternatives. Our aim is to propose, in the framework of the approach presented above, an incremental procedure to assess parameter θ. We assume that this parameter is initially unknown and we want to use an active learning process to progressively reduce the uncertainty attached to θ. Examples will be selected one by one and presented to the DM that will be asked to classify them; these new classifications will induce constraints restricting the space of admissible θ, and the process will be repeated until being able to classify all the alternatives in X.

Our procedure relies on the notion of minimax regret, allowing to make robust decisions in face of uncertainty, and to ask informative queries to further reduce the uncertainty on the space of admissible θ. This can be seen as an adaptation to sorting problems of incremental elicitation mechanisms designed for choice problems (e.g., [START_REF] Wang | Incremental Utility Elicitation with the Minimax Regret Decision Criterion[END_REF][START_REF] Benabbou | Incremental Elicitation of Choquet Capacities for Multicriteria Decision Making[END_REF]).

Whenever θ is precisely known, we wish to assign x to the category K such that m (x, θ) ≥ m k (x, θ) for all k ∈ {1, . . . , q}. Therefore, it is natural to define the loss or regret associated to assigning x to K rather than assigning it to K k as:

R(x, K , K k , θ) = m k (x, θ) -m (x, θ).
When we only know that θ belong to an uncertainty set Θ, we may be interested in computing the following regrets: Definition 1. For any alternative x ∈ X, the pairwise max regret (PMR) of assigning x to the category K instead of assigning it to the category K k is defined by:

PMR(x, K , K k , Θ) = max θ∈Θ R(x, K , K k , θ) = max θ∈Θ m k (x, θ) -m (x, θ) .
PMR(x, K , K k , Θ) is the maximum feasible gap between the membership indices of alternative x with respect to categories K k and K . It represents the worst-case loss that we may incur by assigning x to category K instead of category K k when parameter θ belongs to Θ. Definition 2. The max regret (MR) of assigning x ∈ X to category K is defined by: MR(x, K , Θ) = max k∈{1,...,q} PMR(x, K , K k , Θ) MR(x, K , Θ) is the worst-case loss that we may incur by assigning alternative x to category K instead of any other categories. We now define the notion of minimax regret and the regret-optimal category associated to alternative x ∈ X: Definition 3. The minimax regret (mMR) of alternative x ∈ X is:

mMR(x, Θ) = min ∈{1,...,q} MR(x, K , Θ)
Considering the uncertainty set Θ, a cautious decision rule would consist in assigning alternative x to the category minimizing MR(x, K , Θ), named the regret-optimal category of x here below. In order to assess the maximal error on the complete assignment when using this rule, we introduce now the notion of maximum minimax regret: Definition 4. The maximum minimax regret (MmMR) is:

MmMR(X, Θ) = max x∈X mMR(x, Θ)
In sorting problems, MmMR plays the role of measuring the current decision quality; in particular, if MmMR = 0, then we know that the complete assignment is valid. However, it might be the case that the aggregate value MmMR is too large according to the DM. In that case, it is natural to consider incremental elicitation procedures to make this value decrease until a given tolerance threshold δ ≥ 0. This is actually possible due to the fact that the inequality MmMR(X, Θ ) ≤ MmMR(X, Θ) is true for all Θ ⊆ Θ, meaning that the value MmMR cannot increase when including new preference information obtained from the DM; actually, in the subsection devoted to numerical tests, we will see that, in practice, it strictly decreases when queries are chosen in a reasoned way.

As in a choice problems, comparison queries between alternatives might be asked; however, in our context, it is less straightforward to identify a pair of alternatives forming an informative preference query (i.e. which is likely to induce a regret reduction). Instead, we can ask the DM to choose, for a given alternative, the category that fits best (either among a pair of categories, among a given subset of categories, or among all possible categories). For this type of queries, we will denote K

x K k the preference for category K over category K k concerning the assignement of alternative x ∈ X. For choosing which query to ask next, we propose to focus on an alternative x that is associated with the largest value mMR in the current regret-optimal assignment; by asking a query involving such an alternative, we are indeed likely to reduce the value MmMR since MmMR(X, Θ) = mMR(x, Θ) holds. There are at least the two following possibilities:

• we can ask the DM to assign x to the most relevant category or • we can ask the DM to compare the regret-optimal category K * of alternative x with its regret-maximizing adversarial category (the one that maximizes PMR(x, K * , K k , ΘP )) and state which one is the most relevant among the two.

The latter approach has the advantage of requiring less effort from the DM while focusing on the pair of categories inducing the current value MmMR.

Determination of the optimal assignment using mixed integer linear programming

Let P be the set gathering all preference statements of type K x K k collected so far, and let ΘP be the set containing all parameters θ consistent with information P, i.e. such that m (x, θ) ≥ m k (x, θ) for all examples K x K k ∈ P. We assume here that operator f θ is linear in θ (e.g., a weighted sum or a Choquet integral). In order to determine the regret-optimal assignment, we need a method that efficiently computes PMR(x, K , K k , ΘP ) for any x ∈ X and any , k ∈ {1, . . . , q}. This computation is challenging because it requires a maximization of the difference of two minima. Nevertheless, we will show that this optimization problem can be decomposed in two mixed integer linear programs. In order to do that, we need first to show that the answers to preference queries induce linear constraints over the set of parameters ΘP .

Proposition 1. Let x ∈ X be any alternative and

K , K k two cate- gories such that = k. If > k, then Θ P∪K x K k is: θ ∈ ΘP , 1-P (x, r -1 , θ) ≥ min{P (x, r k , θ), 1-P (x, r k-1 , θ)} otherwise Θ P∪K xKk is: θ ∈ ΘP , P (x, r , θ) ≥ min{P (x, r k , θ), 1 -P (x, r k-1 , θ)}
Proof : If we observe that category K is preferred to category K k for the assignment of alternative x ∈ X, then we want to restrict ΘP to all parameters θ such that m (x, θ) ≥ m k (x, θ), which can be rewritten min{P (x, r , θ), 1 -P (x, r -1 , θ)} ≥ min{P (x, r k , θ), 1 -P (x, r k-1 , θ)}. This is actually equivalent to imposing the two following constraints:

P (x, r , θ) ≥ min{P (x, r k , θ), 1 -P (x, r k-1 , θ)} (3) 1 -P (x, r -1 , θ) ≥ min{P (x, r k , θ), 1 -P (x, r k-1 , θ)} (4)
First, assume that K , K k are such that > k. In that case, we know that we have Pi(x, r ) ≥ Pi(x, r k ) for all i ∈ N . Therefore, since f θ is compatible with Pareto dominance, then we have P (x, r , θ) ≥ P (x, r k , θ) for all θ ∈ ΘP . As a consequence, Equation (3) holds for all θ ∈ ΘP and so the associated constraint is not needed for updating the set of feasible parameters ΘP according to the observed preference (x, K K k ). Hence, only Equation (4) remains in that case. Now, assuming that < k, we have Pi(x, r -1 ) ≤ Pi(x, r k-1 ) for all i ∈ N . Therefore, since f θ is compatible with Pareto dominance, then P (x, r -1 , θ) ≤ P (x, r k-1 , θ) for all θ ∈ ΘP , i.e. 1-P (x, r -1 , θ) ≥ 1-P (x, r k-1 , θ). Therefore, Equation ( 4) holds for all θ ∈ ΘP and so the associated constraint is not needed for updating the set of feasible parameters ΘP according to K x K k . Hence, only Equation (3) remains.

Thus, if the DM states that, for a given alternative x ∈ X, category K is better suited than category K k , then it is sufficient to impose the following constraint over the set of feasible parameters:

• 1 -P (x, r -1 , θ) ≥ min{P (x, r k , θ), 1 -P (x, r k-1 , θ)} if > k, • P (x, r , θ) ≥ min{P (x, r k , θ), 1 -P (x, r k-1 , θ)} otherwise.
These constraints can be linearized using standard linearization of the min aggregator. In particular, this is done in the following way:

If > k, we impose:

M b + 1 -P (x, r -1 , θ) ≥ P (x, r k , θ) M (1 -b) + 1 -P (x, r -1 , θ) ≥ 1 -P (x, r k-1 , θ) If < k, we impose: M b + P (x, r , θ) ≥ P (x, r k , θ) M (1 -b) + P (x, r , θ) ≥ 1 -P (x, r k-1 , θ)
where b is a boolean variable and M is a numerical scalar value greater than one.

Hence, we proved that ΘP can be described with linear constraints when P is composed of preferences of type (x, K , K k ). Now, the following proposition proves that PMR-optimizations can be performed using mixed integer linear programming.

Proposition 2. For any x ∈ X and any , k ∈ {1, . . . , q}, we have:

PMR(x, K , K k , ΘP ) = max{β1, β2}
where β1 and β2 are respectively the optimum values of the following mixed integer linear programs:

max θ∈Θ P t∈R {t-P (x, r , θ)} max θ∈Θ P t∈R {t+P (x, r -1 , θ)-1} s.t. t ≤ P (x, r k , θ) s.t. t ≤ P (x, r k , θ) t ≤ 1-P (x, r k-1 , θ) t ≤ 1-P (x, r k-1 , θ)
Proof : For any alternative x ∈ X and any two categories K , K k :

PMR(x, K , K k , ΘP ) = max θ∈Θ P R(x, K , K k , θ) = max θ∈Θ P m k (x, θ) -m (x, θ)
Since m k (x, θ) = min{P (x, r k , θ), 1 -P (x, r k-1 , θ)}, we can compute PMR(x, K , K k , ΘP ) by solving the following program:

max θ∈Θ P t∈R t -m (x, θ) s.t. t ≤ P (x, r k , θ) t ≤ 1 -P (x, r k-1 , θ)
This program is obtained by using standard linearization of the min aggregator. Then, we have:

t -m (x, θ) = t -min{P (x, r , θ), 1 -P (x, r -1 , θ)} = t + max{-P (x, r , θ), P (x, r -1 , θ) -1} = max{t -P (x, r , θ), t + P (x, r -1 , θ) -1}
Therefore, PMR(x, K , K k , ΘP ) can be computed by solving the following optimization problem:

max θ∈Θ P t∈R max{t -P (x, r , θ), t + P (x, r -1 , θ) -1} s.t. t ≤ P (x, r k , θ) t ≤ 1 -P (x, r k-1 , θ)
The result is finally obtained by interchanging the max operators.

Therefore, computing PMR(x, K , K k , ΘP ) can be easily performed by solving two mixed integer linear programs and then selecting the greatest optima.

Application to Choquet integrals

In this subsection, we will focus on a particular instance obtained by interpreting f θ as a Choquet integral in Equation ( 1). This allows positive or negative synergies among arguments when aggregating preference indices Pi(x, r ) into an overall index P (x, r , θ). We now recall the definition of Choquet capacities and (discrete) Choquet integrals 2 . A normalized Choquet capacity v is a real-valued setfunction defined on 2 N such that v(∅) = 0, v(N ) = 1 and v(A) ≤ v(B) for all A ⊆ B ⊆ N ; value v(A) is the weight attached to coalition A, for any A ⊆ N . The Choquet integral is then defined by:

Cv(x) = n i=1 x (i) -x (i-1) v(X (i) ) with x (0) = 0
where (.) is a permutation of {1, . . . , n} which sorts the components of x by increasing order (i.e. x (i) ≤ x (i+1) for i ∈ {1, . . . , n -1}) and X (i) = {(i), . . . , (n)}. In the following, the uncertain capacity function v takes the role of θ and the set of feasible parameters ΘP is the set of all normalized capacities compatible with P. Alternative x ∈ X is now compared to any profile r using the preference index:

P (x, r , v) = Cv(P1(x, r ), . . . , Pn(x, r ))
The membership of solution x to category K is now defined by:

m (x, v) = min{P (x, r , v), 1 -P (x, r -1 , v)}
In the particular case where ΘP is a set of strictly monotonic capacities (i.e. v(A) < v(B) for all A ⊂ B ⊆ N ), we can linearize the constraints induced by P in a simpler way, so that we can avoid the use of boolean variables. Proposition 3. For any x ∈ X and any , k ∈ {1, . . . , q}: If > k and Pi(x, r -1 ) = Pi(x, r k-1 ) for some i ∈ N , then

Θ P∪K x K k = {v ∈ ΘP , 1 -P (x, r -1 , v) ≥ P (x, r k , v)}
If < k and Pi(x, r ) = Pi(x, r k ) for some i ∈ N , then

Θ P∪K x K k = {v ∈ ΘP , P (x, r , v) ≥ 1 -P (x, r k-1 , v)} Otherwise, Θ P∪K x K k = ΘP .
Proof : Assume that > k. According to Proposition 1, capacities v ∈ ΘP that are compatible with K x K k are those verifying:

1 -P (x, r -1 , v) ≥ min{P (x, r k , v), 1 -P (x, r k-1 , v)} (5)
Since > k, we know that Pi(x, r -1 ) ≥ Pi(x, r k-1 ) for all i ∈ N .

In the case where Pi(x, r -1 ) = Pi(x, r k-1 ) for all i ∈ N , we have P (x, r -1 , v) = P (x, r k-1 , v), i.e. 1 -P (x, r -1 , v) = 1 -P (x, r k-1 , v); therefore, for all v ∈ ΘP , Equation ( 5) is satisfied and so Θ P∪K xKk = ΘP . Now, consider the case where Pi(x, r -1 ) = Pi(x, r k-1 ) for some i ∈ N . Since v ∈ ΘP is strictly monotonic, then Cv is strictly increasing with Pareto dominance, and so we have P (x, r -1 , v) > P (x, r k-1 , v), i.e. 1 -P (x, r -1 , v) < 1 -P (x, r k-1 , v). As a consequence, Equation ( 5) is satisfied if and only if we have 1 -P (x, r -1 , v) ≥ P (x, r k , v). Hence, Θ P∪K x K k = {v ∈ ΘP , 1 -P (x, r -1 , v) ≥ P (x, r k , v)}. Now, assume that < k. In that case, according to Proposition 1, capacities v ∈ ΘP that satisfy K x K k are those verifying:

P (x, r , v) ≥ min{P (x, r k , θ), 1 -P (x, r k-1 , v)} (6)
2 Refer, for instance, to [START_REF] Grabisch | The application of fuzzy integrals in multicriteria decision making[END_REF][START_REF] Grabisch | Aggregation Functions (Encyclopedia of Mathematics and Its Applications[END_REF] for a much more detailed description.

Since < k, we have Pi(x, r ) ≤ Pi(x, r k ) for all i ∈ N . First, assume that Pi(x, r ) = Pi(x, r k ) for all i ∈ N . In that case, we have P (x, r , v) = P (x, r k , v) and so Equation ( 6) is verified by all capacities v ∈ ΘP ; hence Θ P∪K xKk = ΘP . Now, assume that Pi(x, r ) = Pi(x, r k ) for some i ∈ N . Since v ∈ ΘP is strictly monotonic, then Cv is strictly increasing with Pareto dominance, and so we necessarily have P (x, r , v) < P (x, r k , v). Therefore, Equation ( 6) is satisfied if and only if P (x, r , v) ≥ 1-P (x, r k-1 , v) and so Θ P∪K x K k = {v ∈ ΘP , P (x, r , v) ≥ 1 -P (x, r k-1 , v)}.

Thus, according to Proposition 3, observing that category K is preferred to category K k for alternative x amounts to imposing:

• the linear constraint 1 -P (x, r -1 , v) ≥ P (x, r k , v) if > k and Pi(x, r -1 ) = Pi(x, r k-1 ) for some i ∈ N , • the linear constraint P (x, r , v) ≥ 1 -P (x, r k-1 , v) if < k and
Pi(x, r ) = Pi(x, r k ) for some i ∈ N and • no additional constraints otherwise.

As a consequence, when assuming that the DM's preferences can be modeled by a Choquet integral with a strictly monotonic capacity, the PMR-optimization consists in solving two linear programs (instead of mixed integer linear programs in the general case) and then selecting the maximum between the two optima (see Proposition 2).

Numerical tests

In this section, we consider datasets of alternatives uniformly drawn within [0, 1] n and simulated DMs answer to preference queries according to a randomly generated Choquet integral (defined with a strictly monotonic capactity). First, we want to compare the following query selection strategies in terms of MmMR reduction:

• S0: this strategy asks the DM to state which among all the categories suits most a randomly chosen alternative in the dataset. • S1: this strategy asks to compare the regret-optimal category of x with its regret-maximizing adversarial category, where x is the alternative associated with the largest mMR (see Section 3). • S2: this strategy asks which among all the categories suits most the alternative associated with the largest mMR value.

Linear optimizations are performed by the Gurobi solver called from a program written in Java. The reference profiles under consideration are constant utility profiles dividing the utility scale [0, 1] into intervals of same size on every criterion. In Figure 2, we report the MmMR at each iteration step of the incremental procedures; results are obtained by averaging over 100runs. First, we can see that the MmMR value reduces significantly faster with S1 and S2 than with S0; for instance, after at most 20 queries on average, the MmMR value is around 40 percent of the maximum regret in the dataset with S1 and S2, while still remaining above 80 percent with S0. Moreover, as expected, S2 turns out to be more informative than S1 (since the MmMR reduces more quickly). However, we also note that S1 needs just approximately 3 additional queries on average to achieve the same level of regret as S2. This empirical evidence suggests to use S1 instead of S2 since the former has lower cognitive cost than the latter while still being very effective (asking the DM to state which among all the categories suits most a given alternative indeed requires much more cognitive effort from the DM than the comparison of two categories).

The next numerical tests aim to evaluate the impact of the following parameters on computation times of MmMR calculations: q the number of categories, n the number of criteria, p the number of observed preferences and the number of alternatives. In Table 1, computation times are obtained by averaging over 100 runs.

In particular, computation times drastically increase with q, the number of categories (due to the quadratic number of PMRcomputations). Moreover, computation times are significantly impacted by the number of criteria. This is due to the fact that the number of variables and constraints of the linear programs grows exponentially with the number of criteria (in order to ensure monotonicity of the Choquet capacity); note however that computation times can be further reduced when considering some particular subclasses of capacities (2-additive capacities, belief functions).

Conclusion

The main advantage of our approach is that assignment queries are selected using the minimax regret criterion. The constraints derived from these examples indeed allow an efficient reduction of uncertainty where it is decisive, thus facilitating the assignment of remaining alternatives to a category. This applies to a wide family of weighted aggregation functions, including weighted sums, ordered weigthed averaging operators and Choquet integrals. For Choquet integrals, the proposed approach is practically feasible provided that the number of criteria is not too large (about 10). For problems involving a larger number of criteria, the linear programs to be solved for computing regrets is computationally demanding, due to monotonicity constraints. In this case, a first solution consists in using capacity admitting compact representations, e.g. k-additive capacities [START_REF] Grabisch | The application of fuzzy integrals in multicriteria decision making[END_REF] for a bounded k; in this particular case, the elicitation of the capacity remains tractable (see e.g. [START_REF] Fallah Tehrani | Learning monotone nonlinear models using the Choquet integral[END_REF] for k = 2). Another interesting option would be to use fictitious alternatives with very simple profiles as learning example. This allows to drastically simplify the management of the monotonicity constraint, even with large numbers of criteria, as shown for choice problems in [START_REF] Benabbou | Incremental Elicitation of Choquet Capacities for Multicriteria Decision Making[END_REF].

Figure 2 .

 2 Figure 2. Maximum minimax regret reduction for strategies S0, S1 and S2 (n = 5, 150 alternatives, 5 categories).

  p = 5 p = 0 p = 5 p = 0 p = 5 p = 0 p = 5 0.

Table 1 .

 1 Computation times (in seconds) of MmMR calculations; results for instances with |X| = 50, 100, 200 are respectively given in lines 1,2,3.