Tonal inflection in Mande languages: The cases of Bamana and Dan-Gwɛɛtaa

Valentin Vydrin

Introduction

Mande is a mid-range language family (its time depth ranges between 5000 and 6000 years) presumably belonging to the Niger-Congo macrofamily. It comprises more than 70 languages. Practically all Mande languages are tonal, therefore the Proto-Mande language most probably was tonal too. Tonal systems of the modern Mande languages are very diverse in the number of tones, in the complexity of rules conditioning the passage of tones from the underlying level to the surface, in the role grammatical tone and a number of tonal morphemes; for a survey (although outdated in some points) see [START_REF] Vydrine | Areal and genetic features in West Mande and South Mande phonology: In what sense did Mande languages evolve?[END_REF]).

It would be too ambitious and too bulky to display here the tone inflections in all the Mande languages (or even those whose tonal systems are sufficiently well studied to date), so, I will limit myself by presenting tonal systems and tonal inflections in two languages of the family, Bamana (Bambara) and Dan (the Gwɛɛtaa dialect), belonging to different branches of the Mande family (35% of cognates in M. Swadesh's 100-wordlist, which corresponds to more than 4000 years of independent existence). This presentation has a secondary task to show how different are these tonal systems, and therefore how risky it may be to refer to Mande tonal systems in general.

Bamana (also Bambara, Bamanankan, ISO 639-3 bam) is mainly spoken in the Republic of Mali by about 4,000,000 L1 speakers and up to 8,000,000 L2 speakers. Legally one of 13 -national languages‖ of Mali, Bamana is the major language of this country. It serves as lingua-franca everywhere, except for the North-Eastern part of the country. The official language of Mali is French, while -national languages‖ share among them mainly the oral sphere. However, it is also taught at a number of primary schools, there are several periodicals and an emergent literature in Bamana.

The Bamana language is represented by numerous local dialects displaying considerable divergences in what concerns the surface-level tonal and segmental realizations. 1 These divergences may result in serious difficulties in mutual intelligibility (or its lacking) among speakers of different dialects, despite the fact that their grammars and vocabularies are similar. However, mutual understanding is ensured by the existence of a pandialectal koine, Standard Bamana stemming from the dialect of Bamako (the capital of Mali). The Bamana data analyzed in this paper belongs to Standard Bamana.

Dan (also Yakuba, Gio, ISO 639-3 dnj) counts about 1,600,000 speakers mainly in Côte d'Ivoire and Liberia; there are also compact areas of Dan in Guinea. 2 It belongs to the Southern Mande group where it remains the biggest language, with relation to the number of speakers. Dan displays a considerable dialectal variation, which is typical of the languages of the forest zone: distant dialects may have up to 10% (or slightly more) of divergent vocabulary in the Swadesh's 100 wordlist (Vydrin 2009a) and be mutually unintelligible. At least two Dan language norms are being established in Côte d'Ivoire: the Western Dan, based on the Blo dialect, and the Eastern Dan, based on the Gwɛɛtaa dialect. In this paper, I concentrate on the analysis of the Eastern variety spoken in the Goueta sousprefecture of the Tonkpi Province of Côte d'Ivoire.

In section 2, I analyze the Bamana tonal system. Its main features are: two levels with a downdrift and downstep; low tone is the marked one; the tonal compactness rule regulates a merger of adjacent tonal domains within syntactic groups of certain types; a floating low tone plays a role of a definite/referential article.

In section 3, Dan Gwɛɛtaa tones are analyzed. This language has 5 level tones; context changes of tones are quasi-nonexistent; there are numerous grammatical tonal modifications; in the majority of cases, it is the extralow which appears as a grammatical tone; an interpretation of extralow as a default tone can be suggested.

The tonal inflection in Bamana

Bamana, with its two level tones, belongs to the languages with a minimal tonal inventory (cf. [START_REF] Hulst | Deconstructing stress‖[END_REF] who suggests to analyze all two-level languages in terms of accent, rather than tone). Unlike the majority of two-level languages, in Bamana it is not the high, but the low tone that is marked. Bamana has a rather high rate of lexical minimal pairs distinguished only by tones: in a dictionary numbering 11,423 entries, 697 pairs have been found, i.e. 1393 words, or about 12,2% of the vocabulary, among these, there is an overwhelming majority of the most frequent words of the language, in particular many auxiliary words. Bamana is an isolating language with an extremely scanty segmental inflectional morphology, which prevents it from combining segmental and tonal elements of inflectional paradigms, for such paradigms are simply missing. Unlike many other Mande languages (including Dan, see below), Bamana has no tonal inflectional markers erasing lexical tones,unless we consider as tonal inflection the tonal compactness (see 2.1; this solution seems to me unnecessary). The only tonal inflection available is the article (reference/definiteness marker) represented by a floating. The purpose of this division is to describe the tonal system of Bamana and the role of the tonal inflection.

Basics of tonal phonology in Bamana.

The tonal system of Bamana (and those of some closely related Manding varieties, very similar to Bamana) was subject of numerous publications, beginning with [START_REF] Welmers | Tonemes and Tone Writing in Maninka‖[END_REF] and [START_REF] Bird | Aspects of Bambara Syntax[END_REF]. It was hotly debated since 1970s [START_REF] Courtenay | On the Nature of the Bambara Tone System‖[END_REF][START_REF] Creissels | Le système tonal du bambara standard[END_REF][START_REF] Creissels | La notion de ton marqué dans l'analyse d'une opposition tonale binaire: Le cas du mandingue‖[END_REF], Creissels 2009[START_REF] Dumestre | Le bambara du Mali : Essai de description linguistique[END_REF], and by now, it is more or less clear how this system works. 3 In what follows, I will display its main features, which is necessary for the understanding of the Bamana tonal inflection.

As mentioned above, Bamana has a two-level tonal system. At the surface level, there is a great variability of pitches which is due to the phenomenon of downdrift and contextual tonal modifications described below.

Tonally dominant and tonally recessive syllables, tonal domain.

Syllables in Bamana fall into tonally dominant and tonally recessive. 4 A tonally dominant syllable has a low or (by default) a high tone associated with it. A tonally recessive syllable inherits its tone from the preceding syllable; its surface tone can be also conditioned by the right context. A sequence consisting of a dominant syllable and the recessive syllables to its right (within a word or a tonally compact group), represents a tonal domain. 5(1) |dùlokoto|  dùlòkòtò ‗produce blisters' |méleke|  méléké ‗envelope'

Any word-initial syllable in a content word is dominant. All suffixes consist of recessive syllables. In most lexemes, it is the initial syllable only that is dominant, the others are recessive, so that the tonal domain coincides with the word. There are however some words that have non-initial dominant syllables. Such lexemes, which include more than one tonal domain, constitute ‗minor tonal classes.' Among these, there are:

prefixed and compound verbs:

( Contrary to the general trend of tonal languages, it is the low tone that is marked in Bamana [START_REF] Creissels | La notion de ton marqué dans l'analyse d'une opposition tonale binaire: Le cas du mandingue‖[END_REF], Creissels 2009). 6 As it is said above, the low tone associated with a dominant syllable spreads to the right up to the end of its domain (most often, to the end of the word, if there is no other low tone dominant syllable on its way):

(4) |gɛ lɛnya|  gɛ ̀lɛ ̀nyà ‗grow difficult'

A low tone spread to the right is curbed if it encounters another low tone associated with a syllable. In this case, a buffer high tone is necessarily inserted between the two low tones.

The buffer high tone is associated with the final segment of the first low tone domain: its final mora (if the domain is equal to one syllable), its final syllable (if the domain includes more than one syllable), its final foot (if the domain includes two feet or more).

In (5a), the first domain consists of only one syllable ma, and the buffer high tone is assigned to the second mora of the first syllable, so that the syllable acquires a rising tone. In (5b), the first domain covers two syllables, kun-na, and the buffer high tone is assigned to its final syllable. If a dominant syllable is not assigned a low ton, it acquires, by default, a high tone which spreads to all the subsequent recessive syllables of the domain, whatever may be the tone of the following domain (in 5c-d, this process can be also regarded as an insertion of a buffer high tone at the end of the high-tone domain, the result is the same).

(5

) a. |mà|dòn|  mǎdòn ‗approach' b. |kùnna|sìri|  kùnnásìrì ‗be ashamed' c. |bólo|bán|  bólóbán ‗get ruined' d. |bólo|kò|  bólókò ‗pass initiation'
It can be therefore said that in Bamana, two adjacent low tone domains are separated by a high tone.7

Tonal compactness.

Certain types of syntactic constructions are subject to the rule of ‗tonal compactness'. In a tonally compact construction, all the domains, except the initial one, are eliminated, and the initial domain extends up to the right boundary of the construction. If the resulting domain carries the low tone and is followed by another low-tone element, its final component is assigned a high tone. 8 The following constructions are tonally compact:

the attributive construction, -noun + simple adjective‖:9 (6) |mìsi| ‗cow' + |bìlen| ‗red'+ ` ART  mìsì bílén-` ‗red cow' |só| ‗house' + |bìlen| ‗red'+ ` ART  só bílén-` ‗red house'

The entire sequence represents one tonal domain, so that its final dissyllabic segment, bilen, followed by a floating low tone of the article (see below), is assigned a buffer high tone (if the tonal compactness rule were not applied, the tonal contours would be *mìsí bìlén-`, *só bìlén-`); the determinative construction, -dependent noun + head noun‖:

(7) a. |mùso| ‗woman' + |sèn| ‗foot/leg'+` ART  mùsò sén-` ‗feminine foot/leg' b. |kámalen| ‗young man' + |sèn| ‗foot/leg'+` ART  kámálén sén-` ‗young man foot/leg' Note that without the tonal compactness rule, the tonal contour would be *mùsó sěn -`, *kámálén sěn-` .

the preverbial construction, -preverbal adverb + verb‖:

(8) |sɛ bɛkɔrɔ| ‗seriously', |dɔ ǵɔya| ‗humiliate' à yé à mùsó-` sɛ ̀bɛ ̀kɔ ̀rɔ ̀ dɔ ̀gɔ ̀yà. 3SG PFV.TR 3SG woman-ART seriously humiliate ‗He seriously humiliated his wife.' (rather than *… sɛ ̀bɛ ̀kɔ ̀rɔ ̀ dɔ ́gɔ ́yá )

2.1.4. Downdrift.
The downdrift in Bamana follows a typical model: the range of rising in the sequence -Low -High‖ is roughly a half of the range of lowering in the sequence -High -Low‖. As a result, a high tone at the end of a sentence may be realized at the same level as a sentence-initial low tone, or even below that level:10 The only tonal inflection in Bamana is a definite (or referential) article. It is realized primarily on the tonal domain following the NP with which the article is associated: if the following domain carries a high tone, this high tone becomes downstepped. This phenomenon is usually described by postulating that the definite/referential NP is followed by a floating low tone, which interacts with the tone of the following domain.

It should be also noted that the floating low tone is suffixed to a noun or to an attribute (in other words, to the rightmost element of a noun phrase of the structure N + Atr). 11 Despite the fact that it has no segmental support, it represents a tonal domain of its own. See example (10), where the high tone of tɛ ́ goes down a notch in relation to the high tone of jɛ ́gɛ ́.12 (10) Jɛ ́gɛ ́-` fish-ART tɛ ́ NEG.be yàn. here ‗The fish is not here.' If the domain preceding the tonal article is low-tonal, a buffer high tone is necessarily inserted at its end, just before the floating low tone (following the rule of -low tone markedness‖), see [START_REF]Bulgarian, Literary Arabic, and many others. In Manding languages, the tonal (in Bamana, Maninka, Jula) or segmental (in Mandinka, Xasonka, Marka-Dafing) grammatical morpheme of definiteness is most often referred to as -article‖, although sometimes, descriptive definitions are used (e.g., -marqueur de détermination nominale‖ , Creissels and Sambou[END_REF]. [START_REF]Bulgarian, Literary Arabic, and many others. In Manding languages, the tonal (in Bamana, Maninka, Jula) or segmental (in Mandinka, Xasonka, Marka-Dafing) grammatical morpheme of definiteness is most often referred to as -article‖, although sometimes, descriptive definitions are used (e.g., -marqueur de détermination nominale‖ , Creissels and Sambou[END_REF] Mùsó-` woman-ART tɛ ́

NEG.be yàn. here ‗The woman is not here.'

In the absence of a floating low tone, the tonal contour of the phrase is very distinctly different, cf. ( 12). ( 12)

Mùsò woman tɛ ́

NEG.be yàn. here ‗There is no woman/there are no women here.'

The floating low tone is neutralized if the following word begins with a low tone. In this context, presence of absence of the tonal article cannot be observed at the surface level. Therefore, sentences (13.a), where fàli ‗donkey' carries an article, and ( 13 In the texts, nouns appear most frequently with the article. Here are some contexts where forms with and without the article can be differentiated:

under negation (11 and 12; 13a and 13b) In the construction of non-firsthand information (15.a), the verb appears with the suffix -la (the -na form is used when the preceding vowel is nasal) which is tonally recessive (it inherits its tone from the verb). The firsthand information construction 15.b) is technically non-verbal: the verb is nominalized and appears with the tonal article, it is followed by the locative postposition ná which carries a downstepped high tone. 13 ORIGIN: the tonal article in Bamana comes back to the segmental article *-ò. This form is still attested in numerous varieties spoken on the geographic periphery of the Manding area: Mandinka, Xasonka, Worodugukan, Marka-Dafin, some Kagoro dialects. Some traces of the segmental article -ò can be found even in some eastern dialects of Bamana, e.g., the dialect of Bore (Давыдов 2011). In its turn, *-ò comes back to an anaphoric pronoun / remote demonstrative determinant *ò ~ *wò (its reflex in modern Bamana is ò). 13 This construction seems to be the only one in Bamana where this -la-form can be used. However, in closely related Manding varieties, such as Maninka of Kita (Creissels 2009), Mandinka (Creissels et Sambou 2013, 125-131), Standard Maninka of Guinea, an analogous form is much more current and appears in various contexts; it can be interpreted in those varieties as an infinitive. The suffix -la goes back to the locative postposition -lá, the same as in the -visual construction‖ (21b). Therefore, the difference between both constructions is not fortuitous; in fact, they represent one and the same construction at different stages of grammaticalization.

3. The tonal inflection in Dan-Gwɛɛtaa.

The tonal system of Dan-Gwɛɛtaa is radically different from that of Bamana: a great number of contrastive tones; almost non-existent contextual modifications of tones; no differentiation into dominant and recessive syllables; a considerable number of inflectional tonal morphemes in all major segments of grammar: verb, noun, auxiliaries.

Basics of tonal phonology in Dan.

Dan-Gwɛɛtaa has five level tones (a̋ extra-high -á high -ā mid -à low -ȁ extra-low) and three modulated tones (all are falling: ä extra-high-falling -â high-falling -a mid-falling). In the tonological studies, existence of true five-level tonal systems are often treated with certain distrust,14 therefore, I am illustrating the tone contrasts in table 1. Modulated lexical tones, especially Extrahigh-Falling (tīītïɗȅ ‗extremely black', zīīzïɗȅ ‗extremely ancient') and Mid-Falling are rare. Because of their rarity, the phonological status of lexical modulated tones (single tones or combinations of level tones) is difficult to be determined. An argument in favour of a bi-tonemic interpretation of the modulated tones is the fact that falling tones in Dan-Gwɛɛtaa also result from combination with an extralow tonal suffix which serves as the infinitive marker (see 3.2).

The domain of a tone is the syllable. Another important rhythmic unit in Dan is the metric foot (cf. in particular (Vydrin 2010a)): there are numerous restrictions on combinations of tones within this unit (see 3.1.2). There are in Dan light feet (V, CV), heavy feet (CVV, CVŋ, CVVV, CVVŋ, ClVŋ, ClVV) and extraheavy feet (CVVV, CVVŋ). Contextual changes of tones are very few (and they will not be discussed in this paper).

Is there a neutral tone in Dan-Gwɛɛtaa?

In tonological studies, one can find statements as the following one: -In a three-tone language, neutralization of tonal contrasts by tone deletion will be to M‖ (Odden 1996, 21). Let us see if the same trend is valid in a five-level language. In Dan-Gwɛɛtaa, there seems to be no clear cases of tonal neutralization. However, the following facts can be considered in this relation:

1) In heavy feet, there are rather strict restrictions on tonal combinations:

all combinations of identical initial and final tones are allowed (cf. the kaa series in the table 1); all combinations with the final extralow tone are possible: fle̋ȅ ‗kernel of a nut', fa ̰́̋ a ̰ ‗hat', ɗɤ ŋ ‗citrus fruit', kèȅ ‗after' (the latter pattern, Low-Extralow, is relatively rare); combinations -mid-high‖ and -mid-extrahigh‖ are allowed, although both are much less frequent than those with final extralow tone: sʌ ̰ ŋ ́ ‗star', yēe̋ ‗cotton'.

Other tonal combinations are extremely rare (Low-Extrahigh: wɛ ̀i̋-ɗē ‗a round dance'; Mid-Low: sūà ‗falsehood'; etc.). The combinations of tones in the feet are represented in the Table 2.

Table 2. Combinations of tones in the feet in Dan-Gwɛɛtaa. 2 EL L M H EH 1 EH + -- -- -- + H + -- -- + -- M + (rare) + + + L + + -- -- (rare) EL + -- -- -- --
The three modulated tones in Dan-Gwɛɛtaa (mentioned in 3.1.1) reproduce the most frequent tonal patters of the heavy feet; all end in extralow tone. An extraheavy feet, as a rule, cannot carry more than two different tones (e.g., gbíɤ ɤ ‗pregnancy', ɗūʌ ʌ ‗younger maternal uncle'). 15 Their tonal patterns are the same as those of the heavy feet.

2) Among the tonal morphemes described below, the most grammaticalized ones (and, at the same time, those whose origins are the most difficult to trace back) are those of the neutral aspect, the conjoint form of the verb, the infinitive, the nominalization, and the izaphet. Of these, three are represented by the extralow tone, and one (the tonal modification of the conjoint form) is represented by a tonal lowering (to the extralow or low, rarely to the mid tone), which can also be interpreted as a result of amalgamation of the tone of the stem with an extralow-tone morpheme.

With all necessary reservations, one can suggest the interpretation of the extralow tone in Dan Gwɛɛtaa as a default one. If so, one could speak of oppositions of the lexical tones (in their diversity) to the uniforme (extralow) grammatical tones, and that of the diverse footinitial tones (a strong position) to the final tone (either the same as the initial, or extralow).

Tone as an exponent of inflection. 16

Infinitive

The infinitive is marked by a syllable-final tonal modulation of the verbal stem.17 Cf. (16a), where the verb ɗā ‗save' is used in the construction of perfect with its lexical tone, and (16b) where it appears in the infinitive form (in both tomograms, the verb ɗā is indicated with cursors; the tonal drop at the end of the verb is clearly visible in (16b)):

Inflections of pronominal predicative markers (or auxiliaries).

The basic word order in a verbal phrase is (S) AUX -(DO) -V, where S is a subject (optional), AUX is an auxiliary word whose root expresses person and number, and the inflection expresses TAM and polarity; DO is a direct object which is obligatory in the transitive constructions and impossible in intransitive ones; V is a verbal predicate. The inflections within AUXs are very often expressed either by tones only, or simultaneously by tonal and segmental modifications of the stems, cf. table 3.18 Existential, optative and conjoint sets differ only in tones; the same is true for the sets of the perfect and prohibitive, presumptive and negative imperfective. Diachronically, these sets result from fusion of subject pronouns with auxiliaries.

Neutral aspect marker on the verb

In modern Dan-Gwɛɛtaa, the neutral aspect is marked on the verbal root (which usually coincides with a metric foot) by an extra-low tone (replacing the lexical tones). 19 Cf. (17a), where the verb we̋ ‗speak' appears with its lexical tone, and (17b) where it is used in the construction of neutral aspect: ORIGIN: The neutral aspect extra-low tone morpheme comes back to a locative postposition *ɓa or *ɓȁ which first grammaticalized into an imperfective marker (via the stage of an infinitive or supin marker). In more detail, see (Vydrin 2012).

Conjoint status marker

The -conjoint‖ (dependent) status of the verbal construction is marked by the tone lowering of the root morpheme (a metric foot) of a verb; the conjoint form of a verb is necessarily preceded by a predicative marker of the conjoint set (see above). This marker appears in dependent clauses, after a focalized NP (18b), in consecutive constructions, and in some other contexts. Cf. (18a), where the verb appears with its lexical tone: The pattern of the lowering depends on the lexical tone of the verb and on the metric foot structure. There is no single rule for all the verbs; there are rather several classes of verbs, each of them follows a rule of its own, e.g. in ( 19 ORIGIN: The tonal lowering (the marker of the conjoint status marker) may originate in a segmental suffix whose form cannot be reconstructed at the present state of our knowledge.

Tone as an exponent of the izaphet marker 20

In certain types of inalienable possessive nominal constructions, the extra-low tone (replacing lexical tones) on the root morpheme of a noun is used as the izaphet marker. Cf. ungrammatical *dɯ wɔ ̰ and an NP with a different meaning gɤ ̀ɤ ɗɯ ̋ ‗trunk of iroko tree.' ( 20 application or non-application of the izaphet tonal morpheme may depend on rhythmic factors, such as position of the construction in the sentence.

Most probably, the izaphet (extra-)low-tone morpheme should be reconstructed already for the Proto-South-Mande level: similar tonal morphemes are attested in other varieties of Dan (Макеева 2012), in Mano and Guro. Related phenomena are also found in some Southwestern Mande languages and in Susu [START_REF] Green | Internal tonal processes in Susu[END_REF], which can be viewed as an argument in favour of even more ancient origin of this tonal inflection.

Nominalization

When a verb is nominalized together with its indirect object or cicumstant (which keeps its post-verbal position), the lexical tone of the verb is substituted by an extralow tone which can be regarded as a nominalization marker:

( ORIGIN: This tonal infection can be probably reconstructed for the proto-language of the Mano-Dan-Tura subgroup: at least in one other language of the subgroup, Mano, a low-tone morpheme is available whose semantics and usage is exactly the same as the nominalization tonal morpheme in Dan-Gwɛɛtaa (Khachaturyan 2014).

Case in locative nouns.

There is a subclass of nouns, the so-called locative nouns, which have developed a declension system comprising six cases: common, locative, inessive, subessive, adessive, comitative. The declension patterns are highly irregular. Most nouns have only two cases (usually, the common and the locative case). Not a single locative noun has all six case forms. Different cases are formed by using a whole number of formal means: suffixes, final vowel copying, vowel modification, tonal modifications. ORIGIN: The declination of -locative nouns‖ in Dan-Gwɛɛtaa stems from a fusion of noun stems with postpositions. The tonal contrasts among the case forms reflect the original lexical tones of the postpositions. So, the non-low tone of the comitative case can be explained through the high tone of the comitative postposition ká, and the extralow tone of the subessive case is inherited from the subessive postposition ɓȁ. For more details, see (Vydrin 2011).

Concluding remarks

Although both languages belong to one mid-range family, the tonal systems of Bamana and Dan-Gwɛɛtaa seem totally different, cf. table 5. There are two factors that can explain this divergence. The first one is just the time distance: as is proved by the history of better documented languages (especially those of East Asia), 4000 years (and even less) of independent evolution is quite enough to let tonal systems transform radically. The second factor is the areal influence: among all South Mande languages, Dan seems to be the most influenced by Kru languages whose typical characteristics are the polytony and multiple grammatical tones [START_REF] Bearth | -The tone puzzle of Wobe‖[END_REF]Vydrin 2009b). Bamana (and other languages of the Manding group), to the contrary, has a long history of contacts with languages (Pulaar-Fulfulde, Wolof) or two-tone languages which tend to evolve towards accent-like systems. This environment was less conductive to the complication of its tonal system and grows of the functional load of tones. However, this tendency by itself does not exclude retention or emergence of tonal inflections: Bamana rather represents an extreme case, a language where the presence of tonal inflections is minimized, while in other two-level tonal languages of the Mande family it may be more prominent.

  inflection in Bamana: the floating low tone as the definite/referential article.

  human\EMPH REL.3SG.JNT be 3SG.OPT REFL.SG self save ‗Every man for himself!' (Sauve qui peut!) (16.b) Ká wɔ ̰ sʌ kʌ Zla ̰ a ̰ ɗȍ kā ɗā-.' 2PL.PRF matter good do God go\NEUT 2PL.NSBJ save-INF ‗If you do good deeds, God will save you.' ORIGIN: The infinitive marker seems to come back to the same *ɓa or *ɓȁ postposition as the neutral aspect marker (see below); it represents another cycle of grammaticalization of this postposition (Vydrin 2012).

  ɗɤ . 3SG.EXIST speak\NEUT REFL.SG nose.LOC ‗He snuffles.'

(

  28.a) Gwʌ yà glɯ ̄ɯ ̄ŋ̄. stone 3SG.PRF roll ‗The/a stone has rolled.' (28.b) Gwʌ ɗʌ ̰̀̋ ɤ ́ glɯ ̏ɯ ̏ŋ̏. stone FOC REL.3SG.COJNT roll\COJNT ‗It is a stone that is rolling.'

Table 1 .

 1 Minimal series demonstrating contrast of five level tones in Dan-Gwɛɛtaa

	Extra-High		ɗɛ̋		gba̰	ka̋a̋	ya̋
			‗leaves'		‗foot, leg'	‗scabies'	‗yams (sp.)'
	High		ɗɛ ́	gɔ ̰		káá	yá
			‗other'	‗miss sb.'		2PL NEG, PRESTV	1PL.EXCL PRF
	Mid	di ̰		gɔ ̰	gba ̰	kāā	yā
		‗taste'		‗venerable'	‗wing'	2PL PROSP	‗here'
	Low		ɗɛ ̀	gɔ ̰	gba ̰̀̋	kàà	yà ~ yȁ
			‗how many?'	‗husband'	‗ceiling'	‗scratch'	3SG of PRF
	Extra-Low	di ̰	ɗɛ	gɔ ̰	gba ̰	kȁȁ	yȁ
		‗disappointment'	‗call'	‗grass shed'	‗go in' (sharp object)	‗reed'	‗sit down'
	High-Falling				gba ̰		yâ
					‗uproar'		‗badly'
	Mid-Falling	di̰̋
		‗hunger'

Table 3 .

 3 Pronominal predicative makers in Dan-Gwɛɛtaa.

			Singular		Dual			Plural
		1	2	3	Log.	INCL	1.EXCL	1.INCL	2	3	Log.
	Existential	ā	ī/ɯ	yɤ /yɤ ̀	ɤ	kō	yī	kwā	kā	wȍ	wō
	Conjoint	á	í/ɯ ́	Ø/ɤ ́/yɤ ́	ɤ ́	kó	yí	kwá	ká	wó	wó
	Optative	á	í/ɯ ́	Ø/yɤ	ɤ̋	kó	yí	kwá	ká	wȍ	wő
	Perfect	ɓa ̰́̋	ɓá	yà/yȁ	yá	kó	yá	kwá	ká	wà/wȁ	wá
	Prohibitive	ɓa ̰́̋	ɓá	yá	-	kó	yá	kwá	ká	wá	-
	Prospective	ɓa ̰ a ̰	ɓīī	yɤ ɤ	-	kōō	yīī	kwāā	kāā	wōō	-
	Presumptive	ɓa ̰ a ̰	ɓāȁ	yāȁ	-	kōȍ	yāȁ	kwāȁ	kāȁ	wāȁ	-
	Neg. Imperfective ɓa ̰́̋ a ̰́̋	ɓáá	yáá	-	kóó	yáá	kwáá	káá	wáá	-
	Neg. Perfective	ɓi ̰ i ̰	ɓíí	yíí	-	kóó	yíí	kwíí	kíí	wíí	-
	Imperative	-	Ø/ɓɤ	-	-	kȍ	-	kwȁ	kȁ	-	-

  ), (altogether, 13 models of tonal change are available).

	(19) ɗi̋ʌ̋ʌ̋	 ɗīʌ ʌ	‗mash (fruit)'
	ɓʌ̰ ŋ̋ gi̋a̋	 ɓʌ ̰̀̋ ŋ ̀  gȉȁ	‗swallow' ‗grow overripe'
	ɗōŋ	 ɗòŋ ̀	‗count'
	kplae ae  kplae ̀aè ‗grow thin', etc.

  Application or non-application of this tonal inflection is influenced by several factors which look rather as tendencies than as rules (in fact, they are not yet utterly clear):words with generic meanings are more inclined to carry the izaphet marker: ɓɛ ̰ ‗human being', ɗē ‗woman', bɯ ̋ ‗wilderness', ɓláà ‗farm, field', ɗīāŋ ‗talk, speech', ɗɯ ̋ ‗tree'20 Izaphet is a head marking in nominal constructions.etc. have the izaphet form (respectively ɓɛ̰ , ɗȅ, bɯ , ɓlȁȁ, ɗȉȁŋ , ɗɯ ), while many other nouns with more specific meanings do not;if the two nouns in the construction are in the PART -WHOLE relation, the izaphet marking is absent (22a, 23a). If the relation can be described as -the first noun equals the second one‖, the izaphet marker is present (22b, 23b):

	(22) a. bāā ɗɯ ̋ ‗cassava stem',
		b. bāā ɗɯ ‗cassava plant' (ɗɯ ̋ ‗tree')
	(23) a. bīɤ sɔ̰ ‗elephant tusk' (sɔ̰ ‗tooth, tusk'; *bīɤ sɔ ̰ would be ungrammatical)
		b. bīɤ wɯ ‗elephant's carcass', ‗elephant's body' (wɯ ‗meat');
	) dɯ	wɔ ̰
	magic matter\IZF
	‗sorcery' (wɔ̰̋ ́  wɔ ̰ )
	(21) gɤ ̀ɤ	ɗɯ
	iroko tree\IZF
	‗iroko tree' (ɗɯ ́  ɗɯ )

  NSUBJ namesake-father nose 3SG.EXIST STICK\NMLZ land.sub-ger with ‗My friend has a flat nose' (lit. -My friend's nose is stuck to the earth‖, cf. ɗʌ ̰̀̋ ŋ ̀ ‗stick').

	24) yí	tɔ̏	ká	ɓīʌ̋gā
	water draw\NMLZ with creeper
	‗rope for drawing water' (cf. tɔ ́ ‗draw (water)')
	(25) N	tɒ̋ɒ̋ŋ -dʌ		yu ̰	yɤ	ɗʌ̰ ŋ̏	si̋āā-sɯ	ká
	1SG.

Table 4 .

 4 The latter case is illustrated by examples (26-29), where cases are expressed by tones: mid or extrahigh for the comitative case (26, 28), extralow for the subessive case (27, 29). The locative nouns are not very numerous: in my Dan-Gwɛɛtaa dictionary (version from June 2014 containing 2775 lexemes), there were 53 of them (without toponyms). There are five locative nouns that differentiate case forms by tones only, see table 4. Locative nouns with case forms differentiated only by tones

	(26) Yà	gwa̰ nʌ ́ zʌ gɛ̰ ɛ̰ .
	3SG.PRF cat	hit foot/leg.COM
	‗He has kicked a cat.'
	(27) Yà	dɔ	ɤ	gɛ̰ ɛ̰ .
	3SG.PRF stand REFL.SG foot/leg.SUB
	‗He has got up.'
	(28) Yɤ	zu ̰		kpɛ̰ ŋ̋-ɗɤ	n	ya̰ a̰ .
	3SG.EXIST reach\NEUT ouside-LOC 1SG.NSUBJ eye.COM
	‗He has got out in my presence.'
	(29) Sūʌ̋ʌ̋ yà	dɔ -'		ya̰ a ̰ .
	sty	3SG.PRF put-3SG.NSUBJ eye.SUB
	‗He has got a sty on his eye.'
	COMMON	LOCATIVE INESSIVE	SUBESSIVE	ADESSIVE	COMITATIVE
	gɛ ̰ ŋ̏ɗɛ̏	gɛ ŋ ɗɤ			gɛ̰ ɛ̰	gɛ ̰ ɛ ̰
	‗foot, leg'	‗at the feet'			‗on the feet'	‗with/by the feet'
	ya ̰		yʌ ̰ ŋ		ya ̰ a̰	ya ̰ a ̰
	‗eye'		‗in the eyes'	‗on the eye'	‗before the eyes of'
	kó		kőő		kwʌ ́ʌ̏	kwʌ ʌ
	‗each other'		‗in each other'	‗together'	‗together'
	kɔ̏				kwɛ ŋ̏, kwɛ ɛ̏	kɔ̏ɔ̏	kɔ ɔ
	‗hand'				‗in the hands of'	‗on the hands of'	‗with a hand'
	zi ̰ a ̰ a ̰					zi ̰ a̰ a̰ ~ zi ̰ a ̰ a ̰ tȁ
	‗road'					‗at the road, on the road'

Table 5 .

 5 Comparison of characteristics of the tonal systems of Bamana and Dan-Gwɛɛtaa

		Bamana	Dan-Gwɛɛtaa
	Number of tones	2	5 (+ 3 modulated)
	Downdrift & downstep	+	-
	Contextual changes of tones very much	minimal
	Max. size of tonal domain	Unlimited (a tonally compact unit) syllable
	Number of tonal inflections 1	numerous
	Character of realizations of	downstep & contextual	substitution of the lexical tone
	tonal inflections	modifications to the right

See http://www-01.sil.org/SILESR/2000/2000-003/Manding/Bamana.htm.

Cf. http://www-01.sil.org/SILESR/2000/2000-003/Dan-Tura-Mano_map.htm.

There is also a formalist tradition of the study of Bamana tone represented mainly by American authors[START_REF] Leben | Tonal Feet as Tonal Domains‖[END_REF][START_REF] Weidmann | A Foot-Based Reanalysis of Edge-in Tonal Phenomena in Bambara‖[END_REF][START_REF] Green | Prosodic Phonology in Bamana(Bambara) : Syllable Complexity, Metrical Structure, and Tone[END_REF] intended to place the Bamana data into the framework of particular theories. In this paper, I am not going to discuss the formalist approaches to the Bamana tone.

Cf. Eric Campbell's paper on Zenzontepec Chatino (this volume) where tone bearing units similar (although not identical!) to the Bamana -tonally recessive‖ ones are analysed as -no tone morae‖. A crucial difference between the Zenzontepec Chatino -no tone morae‖ and the Bamana -tonally recessive syllables‖ lies in the fact that the former carries a default low tone in a -neutral‖ context which is ousted by the marked mid and high tones in certain contexts according to the predefined set of rules, while in Bamana, the -recessive syllables‖ have no tone of their own, their tonality always depends completely on the left or right context. Alternatively, the -recessive syllables‖ in Bamana could be termed as -no tone syllables‖ too.

The vowels of tonally dominant syllables are underlined. A vertical bar subdivides a word into domains. The acute accent designates a high tone, and the grave accent stands for a low tone.

Both publications deal with the Kita Maninka, however, the analysis is relevant for Bamana as well. I am not going to reproduce here Creissel's argumentation in favour of the low tone markedness.

There are in fact some exceptions: the infinitive marker kà and the 3SG pronoun à always appear with low tone, without any rising, even when followed by another low-tone word.

Tonal compactness in Manding resembles, at least externally, the tonal transformation in Shanghai, as described in(Yip 2007, 242).

More precisely, focalized adjectives derived from qualitative verbs by the means of the suffix -man also form tonally compact groups with their head nouns: |só| ‗hous' + |fìn-man| ‗black'  só fínmán ‗the house (which is) black'. Adjectives derived with other suffixes behave as tonally autonomous.

This is the way the Bamana downdrift is most often represented in grammars. In fact, the reality is more complicated: as a rule, the phrase-initial low tone is realized very low, and the subsequent high tone rises very high; then follows a sharp drop. As a result, the first high tone in a sentence becomes very proeminent, while all subsequent tonal fluctuations are considerably less significant in amplitude. However, for the purposes of this paper, these peculiarities (most probably, of intonative nature) are of no crucial importance, and we can abstract ourselves from these details.

Cf. for example in(Yip 2007, 231): -it is possible to contrast up to four <...> and probably five <...> different level tones‖.

The only exception seems to be a Manding borrowing gbàúȕ ‗kitchen' (from Jula gbà-búgú` ).

Tone also serves in Dan-Gwɛɛtaa to express degrees of intensity of adjectives (often in combination with plurality), e.g.: ɗɤ̋ɤ̋dɤ ɤ ‗round' -ɗɤ̋ɤ̋ɗɤ̋ɤ̋ ‗very round' (pl.). However, formation of the intensive forms belongs rather to the derivation than to inflection, so, it will not be analyzed here.

Designated here by an apostrpohe.

For reasons of space, I cannot delve here into detailed description of grammatical semantics and functions of the predicative pronominal markers.

For the details on the neutral aspect in Dan-Gwɛɛtaa see(Vydrin

2010b).

Acknowledgments

This work is supported by a public grant overseen by the French National Research Agency (ANR) as part of the -Investissements d'Avenir‖ program (reference: ANR-10-LABX-0083)‖. I would like to thank Nina Sumbatova for her insightful remarks and advices which helped very much to improve this text.

Abbreviations: ARTdefinite/referential article (floating low tone); CMMcommon case; COMcomitative case; COPcopula; EMPHtonal marker of the emphatic definite form; EXCLexcusive; EXIexistential pronominal predicative markers; FOCfocalization particle; Hhigh tone; INCLinclusive; INFinfinitive tonal inflection; intens.intensive; IPFVimperfective; IZFizaphet tonal inflection; JNTconjoint pronominal predicative markers; conjoint tonal inflection; Llow tone; LOClocative case; Mmid tone; NEGnegative; NEUTneutal aspect tonal inflection; NMLZnominalization; NONVISnon-visual (non-firsthand); NPnoun phrase; NSBJnon-subjective pronominal set; PFV -Perfective; PLplural; PPpostposition; PRESTVpresentative; PRFperfect; PRHprohibitive; PROSPprospective; REFLreflexive pronoun; RELrelativization marker; SGsingular; SUBsubessive case; supint.superintensive; TRtransitive


Yu Golubev

Th Zimolo

Estimation in Ill-posed Linear Models with Nuisance Design

The paper deals with recovering an unknown vector θ ∈ R p in two simple linear models: in the first one we observe y = b • θ + ξ and z = b + σξ , whereas in the second one we have at our disposal y = b 2 • θ + b • ξ and z = b + σξ . Here b ∈ R p is a nuisance vector with positive components and ξ, ξ ∈ R p are standard white Gaussian noises in R p . It is assumed that p is large and components b k of b are small for large k. In order to get good statistical estimates of θ in this situation, we propose to combine minimax estimates of 1/b k and 1/b 2

k with regularization techniques based on the roughness penalty approach. We provide new non-asymptotic upper bounds for the mean square risks of the estimates related to this method.

Introduction

This paper deals with estimating an unknown vector θ ∈ R p in two simple linear models. In the first one θ is estimated based on the data

y k = b k θ k + ξ k , k = 1, . . . , p, z k = b k + σξ k , k = 1, . . . , p, (1)
whereas in the second one θ is recovered from the observations

y k = b 2 k θ k + b k ξ k , k = 1, . . . , p, z k = b k + σξ k , k = 1, . . . , p, (2)
where ξ and ξ are independent standard white Gaussian noises in R p and b ∈ R p is an unknown nuisance vector with nonnegative components b k ≥ 0, k = 1, 2, . . . , p. In order to simplify numerous technical details, it is assumed in what follows that the noise levels an σ are known.

In spite of very simple probabilistic structures of (1) and (2), estimation of θ in these statistical models is a nontrivial problem. Principal difficulties arise when :

• p is large;

• b k are small.
The basic idea to overcome these difficulties is based on regularization methods which nowadays are well-developed in the case σ = 0. These methods are usually related to the roughness penalty approach and the main goal in this paper to adapt this approach to the case σ > 0.

Linear models (1) and ( 2) play a rather important role in studying, for instance, the noisy periodic deconvolution problem. Suppose we have at our disposal the noisy data

Y (t) = 1 0 h(t -u)X(u) du + n(t), t ∈ [0, 1], Z(t) =h(t) + σn (t), t ∈ [0, 1], (3) where
• n(t) and n (t) are independent standard white Gaussian noises;

• h(t), t ∈ [0, 1] is an unknown periodic function with period 1.

Our goal is to recover X(t), t ∈ [0, 1] based on the observation {Y (t), Z(t), t ∈ [0, 1]}.

The continuous time model ( 3) can be easily transformed into the socalled sequence space model with the help of the standard trigonometric basis on [0, 1] ϕ 0 (t) = 1, ϕ k (t) = √ 2 cos(2πkt), ϕ * k (t) = √ 2 sin(2πkt), k = 1, 2, . . . .

Denote for brevity

X 0 = 1 0 X(t)ϕ 0 (t) dt, X k = 1 0 X(t)ϕ k (t) dt, X * k = 1 0 X(t)ϕ * k (t) dt; Y 0 = 1 0 Y (t)ϕ 0 (t) dt, Y k = 1 0 Y (t)ϕ k (t) dt, Y * k = 1 0 Y (t)ϕ * k (t) dt; Z 0 = 1 0 Z(t)ϕ 0 (t) dt, Z k = 1 0 Z(t)ϕ k (t) dt, Z * k = 1 0 Z(t)ϕ * k (t) dt; h 0 = 1 0 h(t)ϕ 0 (t) dt, h k = 1 0 h(t)ϕ k (t) dt, h * k = 1 0 h(t)ϕ * k (t) dt.
Then with a simple algebra we arrive at the following statistical model :

Y 0 = h 0 X 0 + ξ 0 , Y k = X k h k -X * k h * k √ 2 + ξ k , Y * k = X k h * k + X * k h k √ 2 + ξ -k ; Z 0 = h 0 + σξ 0 , Z k = h k + σξ k , Z * k = h * k + σξ -k . (4)
which is equivalent to (3). In the above equations, ξ and ξ are independent white Gaussian noises. Suppose h(•) is a symmetric function with h k > 0. This means that h * k = 0. In other words, we assume that the convolution operator H : L 2 (0, 1) → L 2 (0, 1) defined by

Hx(t) = 1 0 h(t -u)x(u) du, t ∈ [0, 1]
is self-adjoint and positively defined. In this case, estimation X k , k = 0, 1, . . . in ( 4) is equivalent to estimation of X k based on the data

Y 0 = h 0 X 0 + ξ 0 , Y k = X k h k √ 2 + ξ k ; Z 0 = h 0 + σξ 0 , Z k = h k + σξ k
and to estimation X * k , k = 1, 2, . . . with the help of the observations

Y * k = X * k h k √ 2 + ξ -k ; Z k = h k + σξ k .
Thus we see that if H is self-adjoint and positively defined operator, then the noisy deconvolution is equivalent to recovering θ ∈ l 2 in Model (1). In the general case, one can rewrite (4) in the following equivalent form:

Y 0 = h 0 X 0 + ξ 0 , Y k Z k + Y * k Z * k = X k (h 2 k + h * 2 k ) √ 2 + (ξ k h k + ξ -k h * k ) + σ(ξ -k ξ k + ξ -k ξ -k ), Y * k Z k -Y * k Z * k = X * k (h 2 k + h * 2 k ) √ 2 + (ξ -k h k -ξ k h * k ) + σ(ξ -k ξ -k -ξ k ξ -k ), Z 0 = h 0 + σξ 0 , Z 2 k = h 2 k + 2σh k ξ k + σ 2 ξ 2 k , Z * 2 k = h * 2 k + 2σh * k ξ -k + σ 2 ξ 2 -k . (5)
Therefore, denoting for brevity

b i = h 2 k + h * 2 k , Ȳk = Y k Z k -Y * k Z * k , Ȳ * k = Y * k Z k + Y k Z * k , Zk = Z 2 k + Z * 2 k ,
and omitting the second order terms proportional to σ and σ 2 , we arrive at the following approximation of (5):

Y 0 = h 0 X 0 + ξ 0 , Ȳk ≈ X k b 2 k √ 2 + b k ξk , Ȳ * k ≈ X * k b 2 k √ 2 + b k ξ * k ; Z 0 = h 0 + σξ 0 , Zk = b k + σ ξ k ,
where ξ 0 ξk , ξ * k , ξ k are mutually independent standard Gaussian random variables. So, we see that recovering X k and X * k in ( 4) is nearly equivalent to estimating θ ∈ l 2 in Model [START_REF] Cavalier | Adaptive estimation for inverse problems with noisy operators[END_REF].

Another example, where statistical models similar to (1) and (2) appear, is related to the probability density deconvolution problem. Suppose we observe n i.i.d pairs of random variables

(Y i , Z i ), i = 1, . . . , n, where Y i = Z i + X i .
Random vectors (X 1 , . . . , X n ) , (Z 1 , . . . , Z n ) (Z 1 , . . . , Z n ) are assumed to be independent and variables Z i and Z i are identically distributed. The goal is to estimate the probability density of X 1 . Notice also that statistical problems close to the mentioned above are common in econometric applications related to the instrumental variables, see for instance [START_REF] Johannes | Convergence rates for ill-posed inverse problems with an unknown operator[END_REF], [START_REF] Chen | On rate optimality for ill-posed inverse problems in econometrics[END_REF] and references herein.

The problem of estimation θ in (1) has been already addressed in several paper, see for instance [START_REF] Cai | Prediction in functional linear regression[END_REF], [START_REF] Cavalier | Adaptive estimation for inverse problems with noisy operators[END_REF], [START_REF] Efroimovich | On inverse problems with unknown operators[END_REF], [START_REF] Marteau | Regularization of inverse problems with unknown operator[END_REF], [START_REF] Hoffmann | Nonlinear estimation for linear inverse problems with error in the operator[END_REF]. The principal idea in these papers is to estimate unknown b -1 i using a "natural" estimate 1/z i and then to correct obvious drawbacks of this method with a thresholding method.

In fact, as we will see below, estimating 1/b i is a rather nontrivial and interesting from a mathematical viewpoint statistical problem. This problem is so nontrivial that at the moment we can prove the optimality of proposed estimators only with the help of computerized calculations.

Main results

Univariate minimax inversion

The main idea in estimating θ ∈ R p in (1) and ( 2) is based on a solution to the following simple statistical problem. Suppose we observe a Gaussian random variable

z = µ + σξ, (6)
where µ ∈ R + is an unknown parameter and ξ is a standard Gaussian random variable. Our goal is to estimate 1/µ. More precisely, we are looking for the so-called minimax estimator μ-1 (z) of 1/µ and its minimax risk defined by

r 1 (σ) def = inf μ-1 sup µ>0 µ 4 E µ μ-1 (z) -µ -1 2 = sup µ>0 µ 4 E µ μ-1 (z) -µ -1 2 , ( 7
)
where inf is taken over all measurable functions μ-1 (•) : R 1 → R + , and E µ stands for the expectation w.r.t. the probability measure generated by the observation [START_REF] Marteau | Regularization of inverse problems with unknown operator[END_REF]. Notice that the considered problem is closely related with estimating θ in Models (1) and (2) when = 0.

We begin with a lower bound for the minimax risk r 1 (σ).

Lemma 1.

r 1 (σ) ≥ σ 2 . ( 8
)
Proof. Inequality (8) may be proved the help of the Van Trees inequality [START_REF] Van Trees | Detection, Estimation, and Modulation Theory, V.1[END_REF] (see also, e.g., [START_REF] Gill | Applications of the Van Trees inequality: a Bayesian Cramer-Rao bound[END_REF]) which bounds from below the Bayesian risk of any estimate of g(µ) based on the observation z ∈ R 1 with a probability density P (•; µ), where µ ∈ [a, b] is an unknown parameter. Recall that the Bayesian risk is defined by

R(π, P ) = inf g b a R π(µ)P (z; µ) g(z) -g(µ) 2 dµ dz. Suppose g(µ), µ ∈ [a, b] is differentiable and π(•) is a probability density on [a, b] such that π(a) = π(b) = π (a) = π (b) = 0 with b a π 2 (µ) π(µ) dµ < ∞. Then R(π, P ) ≥ 1 I(π) + I(P ) b a g µ (µ)π(µ) dµ 2 , (9)
where Fisher's informations I(π) and I(P ) are defined as follows :

I(π) = b a π 2 µ (µ) π(µ) dµ and
I(P ) = b a π(µ) R P 2 µ (z; µ) P (z; µ) dz dµ.
In the considered statistical problem

g(µ) = 1 µ and P (z; µ) = 1 √ 2πσ 2 exp - (z -µ) 2 2σ 2 .
Let us take

π(µ) = 1 b -a π • 1 b -a µ - a + b 2 , where π • (x) = 2 cos 2 (πx), x ∈ [-1/2, 1/2].
Hence

1/2 -1/2 π 2 • (x) π • (x) dx = 8π 2 1/2 -1/2 sin 2 (πx) dx = 4π 2
and therefore

I(π) = 4π 2 (b -a) 3 . (10)
Next, we obviously have

b a π(µ)g µ (µ) dµ 2 = b a π(µ) µ 2 dµ 2 ≥ 1 b 4 . (11)
It is also well known that

I(P ) = 1 σ 2 .
Thus, substituting this equation and ( 10)-( 11) in ( 9), we obtain

R(π, P ) ≥ b -4 σ -2 + 4π 2 (b -a) -3
and combining this inequality with

r 1 (σ) ≥ a 4 R(π, P ), we arrive at r 1 (σ) ≥ a 4 b -4 σ -2 + 4π 2 (b -a) -3 . ( 12
)
In order to finish the proof, let us choose b = a + √ a and take the limit in (12) as a → ∞.

Lemma 1 motivates the following definition. Definition 1. An estimator μ-1 (z) of 1/µ is called strong-minimax if the following relations hold true :

• sup µ>0 µ 2 E µ μ-1 (z)µ -1 2 = σ 2 ; (13) • sup µ>0 E µ [μ -1 (z)µ] 2 = 1. ( 14
)
In order to demonstrate that strong-minimax estimators of 1/µ exist, let us consider the following family of non-linear estimates μ-1

β (z) = z + z 2 + βσ 2 , β > 0, (15)
where z + = max(z, 0). There are simple heuristic arguments helping to understand where these estimates come from. Assume that the unknown parameter µ in (6) belongs to R. As above, our goal is to estimate 1/µ based on Z. Consider the following Bayesian risk :

R π (μ) = ∞ -∞ π(µ)µ 2 E µ [µμ(z) -1] 2 dµ,
where μ(z) is an estimate of 1/µ and π(•) is an a priory distribution density of µ. It can be checked with the standard arguments that

arg min μ R π (μ) = ∞ -∞ µ 3 π(µ) exp - (z -µ) 2 2σ 2 dµ ∞ -∞ µ 4 π(µ) exp - (z -µ) 2 2σ 2 dµ.
Assume that a priory density π(•) is a Cauchy density

π(µ) = π γ (µ) = 1 πγ[1 + (µ/γ) 2 ]
with the scale parameter γ > 0. Then it is clear that as γ → 0

arg min μ R πγ (μ) → z z 2 + σ 2 .
Unfortunately, this estimate is not minimax, but its minimax modification is given by (15) where β > 1 is a tuning parameter to be chosen properly. More precisely, for μ-1 β (z) the following fact holds.

Lemma 2. There exist constants

β • ≥ 3/2 and β • ≤ √ 7 + 4 such that μ-1 β (z) from (15) is a strong-minimax estimator for any β ∈ [β • , β • ] . Proof. Let Ψ ξ,β (x) def = [1 + xξ] + (1 + xξ) 2 + βx 2 , x ∈ R + ,
where ξ is a standard Gaussian random variable. Then Equations ( 14) and ( 13) are equivalent to the following ones :

EΨ 2 ξ,β (x) ≤ 1, x ≥ 0, (16)
E[1 -Ψ ξ,β (x)] 2 ≤ x 2 , x ≥ 0. ( 17
) Notice that if x ≥ 1/2β, then Ψ ξ,β (x) ≤ 1.
Indeed, the above condition is equivalent to

1 + xξ ≤ (1 + xξ) 2 + βx 2 , i.e, 0 ≤ β + ξ 2 + ξ x = ξ + 1 2x 2 + β - 1 4x 2 .
So, to prove ( 16) is remains to verify that

EΨ 2 ξ,β (x) ≤ 1, for all x ∈ 0, 1 2β .
It can be checked with a simple algebra that

1 -Ψ ξ,β (x) =xξ + x 2 (β -ξ 2 ) -3x 3 ξ(ξ 2 + β) -x 4 (ξ 2 + β) 2 + [1 -Ψ ξ,β (x)][2xξ + x 2 (ξ 2 + β)] 2 (18)
We begin with lower and upper bounds for β. Notice that for small x we have from (18)

1 -Ψ ξ,β (x) = xξ + O(x 2 )
and so

1 -Ψ ξ,β (x) = xξ + x 2 (β -ξ 2 ) + x 3 ξ(ξ 2 -3β) + O(x 4 ) Therefore EΨ 2 ξ,β (x) = 1 + x 2 (3 -2β) + O(x 4 ) (19)
and

E Ψ ξ,β (x) -1 2 =x 2 + x 4 (β 2 -8β + 9) + O(x 6 ). ( 20
)
Hence with ( 19) and ( 20) we obtain that β • ≥ 3/2. On the other hand, with (20) we arrive at

β • > 4 - √ 7 ≈ 1.35 and β • ≤ 4 + √ 7 ≈ 6.65.
In order to obtain more precise bounds for β, we computed numerically the following functions:

R 0 (β) = sup x≥0 EΨ 2 ξ,β (x) and R 1 (β) = sup x≥0 x -2 E Ψ ξ,β (x) -1 2 .
Their plots are shown on Figure 1. We see that 3/2 is the exact lower bound for β, i.e. β • = 1.5, whereas β • ≈ 2.7.

In fact, the family of strong-minimax estimators of 1/µ is wide. For instance, along with the Bayesian approach, the roughness penalty method may be used to obtain such estimators. A simplest example of such an estimator is given by

μβ (z) = arg max µ>0 - (z -µ) 2 2σ 2 + β log(µ) = z 2 + z 2 4 + βσ 2 . ( 21
)
With this estimate we arrive at the following estimate of 1/µ μ-1

β (z) = 1 μβ (z) = 1 βσ 2 z 2 4 + βσ 2 - z 2 . ( 22
)
For this method a fact similar to Lemma 2 holds. At the moment we cannot provide an analytical proof of this result. The computerized proof is based on computing the risk functions

Lemma 3. There exist constants β• , β• such that μ-1 β (z) is strong-minimax for any β ∈ [ β• , β• ].
R 0 (β) = sup µ>0 E µ [µμ -1 (z)] 2 and R 1 (β) = sup µ>0 µ 2 E µ [µμ -1 (z) -1] 2
shown on Figure 2.

Comparing Figures 1 and2, we see that from a practical viewpoint the estimator from ( 22) is strong-minimax for a wider range of β. This is rather useful property, since the noise level σ is usually known only approximately.

Notice also that μβ (Z) in ( 21) is the minimax estimator of µ for any

β ∈ [0, 1/2], i.e. inf μ sup µ>0 E µ [μ(Z) -µ] 2 = sup µ>0 E µ [μ β (Z) -µ] 2 = σ 2 , β ∈ [0, 1/2].
Along with strong-minimax estimates of 1/µ we will need in the sequel strong-minimax estimates of 1/µ 2 defined as follows.

Definition 2. An estimator μ-2 (z) of 1/µ 2 is called strong-minimax if • sup µ>0 µ 2 E µ μ-2 (z)µ 2 -1 2 = 4σ 2 ; (23) • sup µ>0 E µ [μ -2 (z)µ 2 ] 2 = 1. ( 24
)
Recall that the usual minimax estimator μ-2 (z) of 1/µ 2 and its minimax risk are defined by

r 2 (σ) def = inf μ-2 sup µ>0 µ 6 E µ μ-2 (z) - 1 µ 2 2 = sup µ>0 µ 6 E µ μ-2 (z) - 1 µ 2 2 ,
where inf is taken over all measurable functions μ-2 (•) : R 1 → R + . The next lemma bounds from below the minimax risk r 2 (σ).

Lemma 4. r 2 (σ) ≥ 4σ 2 .
The proof of this lemma is quite similar to the one of Lemma 1 and therefore it is omitted.

In order to show that the set of strongly-minimax estimates of 1/µ 2 is nonempty, we study numerically the family of the following estimates (see Equations ( 21) and ( 22) for a motivation) : The risk functions

μ-2 β (z) = 1 [μ β (z)] 2 = 1 β 2 σ 4 z 2 4 + βσ 2 - z 2
R 0 (β) = sup µ>0 E µ [µ 2 μ-2 β (z)] 2 and R 1 (β) = 1 4 sup µ>0 µ 2 E µ [µ 2 μ-2 β (z) -1] 2
related to the estimate μ-2 (z) are plotted on Figure 3. From this figure we see that β• ≈ 2.5 and β• ≈ 8.8.

Roughness penalty inversion

One of the most standard ways to construct good estimates of high dimensional vectors θ in ( 1) is based on the roughness penalty approach. Suppose θ k are independent zero mean Gaussian random variables with zero mean and Eθ 2 k = Σ 2 k , k = 1, . . . , p. Let b-1 (z k ) be a strong-minimax estimate of 1/b k (see ( 13) and ( 14)). Then we estimate unknown b k by 1/ b-1 (z k ) and thus we estimate θ k in Model (1) as follows :

θk (y k , z k ) = arg max θ - 1 2 2 θ b-1 (z k ) -y k 2 - θ 2 2Σ 2 k .
It can be seen easily that

θk (y k , z k ) = b-1 (z k ) 1 + 2 Σ -2 k [ b-1 (z k )] 2 y k .
In Model (2) we estimate θ k based on the same idea, i.e.,

θk (y k , z k ) = arg max θ - b-2 (z k ) 2 2 θ b-2 (z k ) -y k 2 - θ 2 2Σ 2 k , or, equivalently, θk (y k , z k ) = b-2 (z k ) 1 + 2 Σ -2 k b-2 (z k ) y k . ( 25
)
It is assumed that in the above equations b-2 (z k ) is a strong-minimax estimate of 1/b 2 k . Our goal is to show that θ(y, z) and θ(y, z) can mimic the pseudoestimate in Models ( 1) and ( 2)

θ• k (y k ) = h • k y k b k , (26)
where

h • k = 1 1 + 2 Σ -2 k b -2 k .
Emphasize that θ• k (y k ) is the roughness penalty estimate constructed assuming that b k are known exactly.

Theorem 1. Let b-1 (z k ) be a strong-minimax estimate of 1/b k . Then E θ(y, z) -θ 2 1/2 ≤ E θ• (y) -θ 2 1/2 + + p k=1 h • k σ 2 θ 2 k b 2 k + 2 b 2 k min 1, σ 2 b 2 k 1/2 . ( 27
)
For the projection method θk (y, z)

= 1{k ≤ W } b-1 (z k )y k the following in- equality E θ(y, z) -θ 2 1/2 ≤ E h • • y -θ 2 1/2 + σ W k=1 θ 2 k b 2 k 1/2 , ( 28
)
where h • k = 1{k ≤ W }, holds.
Proof. Notice that θ(y, z) admits the following decomposition

θk (y k , z k ) = 1 b k b k b-1 (z k ) 1 + 2 Σ -2 k b -2 k [b k b-1 (z k )] 2 y k .
Denote for brevity

ρ k = 2 Σ -2 k b -2 k , ζ k = b k b-1 (z k ), h • k = 1 1 + ρ k , hk = ζ k 1 + ρ k ζ 2 k .
Let us begin with analyzing the projection method. In this case

Σ 2 k = ∞, k ≤ W, 0, k > W,
where W is a given projection frequency. So, we obviously obtain

h • k = 1{k ≤ W } and hk = ζ k 1{k ≤ W }.
Therefore it can be seen easily that

E θ -θ• k (y) 2 = k>W θ 2 k + 2 W k=1 1 b 2 k
and by the strong-minimax property of b-1 k (z k ) (see ( 13) and ( 14)) we obtain

E θ -θ(y, z) 2 = k>W θ 2 k + E W k=1 (1 -ζ k ) 2 θ 2 k + 2 E W k=1 ζ 2 k b 2 k ≤ k>W θ 2 k + 2 W k=1 1 b 2 k + σ 2 W k=1 θ 2 k b 2 k = E θ -θ• (y) 2 + σ 2 p k=1 h •2 k θ 2 k b 2 k ,
thus proving (28).

In the general case, to control the risk of θ(y, z), we make use of the following equation :

E θ -θ(y, z) 2 = E (1 -h) • θ 2 + 2 p k=1 b -2 k E h2 k .
We begin with upper-bounding the last term in this equation. With a simple algebra one obtains

E h2 k =h 2 k E ζ k (1 + ρ k ) 1 + ρ k ζ 2 k 2 ≤h 2 k Eζ 2 k 1{ζ k ≥ 1} + h 2 k E ζ k + (1 -ζ 2 k ) ρ k ζ k 1 + ρ k ζ 2 k 2 1{ζ k < 1} ≤h 2 k Eζ 2 k 1{ζ k ≥ 1} + h 2 k E ζ k + (1 -ζ k ) 2ρ k ζ k 1 + ρ k ζ 2 k 2 1{ζ k < 1} ≤h 2 k Eζ 2 k 1{ζ k ≥ 1} + h 2 k E ζ k + √ ρ k (1 -ζ k ) 2 1{ζ k < 1}. (29)
In deriving the above inequality it was used that max

x≥0 x 1 + ρ k x 2 = 1 2 √ ρ k .
Next we continue (29) with help of

E(1 -ζ k ) 2 + ≤ min{1, σ 2 b -2 k },
which easily follows from the strong-minimax property of b-1

k (z k ). Using (x + y) 2 ≤ (1 + z)x 2 + 1 + 1 z y 2 , z > 0, (30)
we obtain for any z > 0

E h2 k ≤(1 + z)h 2 k + 1 + 1 z ρ k h 2 k min{1, σ 2 b -2 k } ≤(1 + z)h 2 k + 1 + 1 z h k min{1, σ 2 b -2 k }. (31)
Now, we proceed with upper-bounding E(1 -hk ) 2 . Obviously, we have

1 -hk = ρ k 1 + ρ k + 1 1 + ρ k × (ζ k -1) × ρ k ζ k -1 1 + ρ k ζ 2 k . (32)
Notice also that

|ρ k ζ k -1| 1 + ρ k ζ 2 k = ρ k × |ρ k ζ k -1| ρ k + (ρ k ζ k ) 2 ≤ ρ k × max x≥0 |x -1| ρ k + x 2 . ( 33
)
One can check also with a simple algebra that max x≥0

x -1

ρ k + x 2 = 1 2 + 2 √ 1 + ρ k ,
and thus

ρ k × max x≥0 |x -1| ρ k + x 2 = ρ k × max 1 ρ k , 1 2 + 2 √ 1 + ρ k = max 1, √ 1 + ρ k -ρ k 2 ≤ 1 + ρ k . (34)
Hence, combining (32)-( 34) with (30) and with the strong-minimax property of b-1 (z k ), we arrive at the following inequality

E[1 -hk ] 2 ≤ (1 + z)[1 -h k ] 2 + σ 2 1 + 1 z h k b -2 k ( 35
)
that holds for any z > 0.

Thus with (35) and (31) we get

E θ -θ(y, z) 2 ≤(1 + z)E θ -h • y 2 + 1 + 1 z p k=1 h k σ 2 θ 2 k b 2 k + 2 b 2 k min 1, σ 2 b 2 k .
Finally, minimizing the right-hand side at the above equation w.r.t. z > 0, we finish the proof of (27).

The next theorem controls the performance of the roughness penalty method in Model (2).

Theorem 2. Let b-2 (z k ) be a strong-minimax estimate of 1/b 2 k . Then E θ(y, z) -θ 2 1/2 ≤ E θ• (y) -θ 2 1/2 + + p k=1 h •2 k 4σ 2 θ 2 k b 2 k + 2 b 2 k min 1, 4σ 2 b 2 k 1/2 (36)
For the projection estimate θk (y, z) = 1{k ≤ W } b-2 (z k )y k the following inequality holds

E θ(y, z) -θ 2 1/2 ≤ E h • • y -θ 2 1/2 + 2σ W k=1 θ 2 k b 2 k 1/2 , ( 37
)
where h • k = 1{k ≤ W }.
Proof. In view of (25), we can decompose θ(y , z) as follows

θk (y k , z k ) = b-2 (z k )b 2 k 1 + 2 Σ -2 k b-2 (z k ) × y k b 2 k .
Denote for brevity

ζ k = b-2 (z k )b 2 k , ρ k = 2 Σ 2 k b 2 k , hk = ζ k 1 + ρ k ζ k .
With these notations we have

E[θ k -θk (y k , z k )] 2 = E[1 -hk ] 2 θ 2 k + 2 b -2 k E h2 k . ( 38
)
We begin upper-bounding the right-hand side at this equation for the projection estimate with the projection frequency W . For this estimate

hk = ζ k 1{k ≤ W }.
Therefore by the strong-minimax property of b-2 (z k ) we obtain from (38)

E θ -θ(y , z) 2 ≤ p k=W +1 θ 2 p + 2 W k=1 1 b 2 k + 4σ 2 W k=1 θ 2 k b 2 k ,
thus proving (37).

Let us now turn to the general case. We begin with controlling the bias term in the risk decomposition (38). Using (30) and the strong minimax property of b-2 (z k ), we obtain

E[1 -hk ] 2 =E ρ k 1 + ρ k + 1 -ζ k (1 + ρ k ζ k )(1 + ρ k ) 2 ≤(1 + z) ρ k 1 + ρ k 2 + 1 + 1 z E 1 -ζ k (1 + ρ k k )(1 + ρ k ) 2 ≤(1 + z)[1 -h • k ] 2 + 4σ 2 1 + 1 z h •2 k b 2 k . ( 39
)
With the same arguments we upper-bound the variance term

E h2 k =h •2 k E ζ k (1 + ρ k ) 1 + ρ k ζ k 2 ≤h •2 k Eζ 2 k 1{ζ k ≥ 1} + h •2 k E ζ k + (1 -ζ k ) ρ k ζ k 1 + ρ k ζ k 2 1{ζ k < 1} ≤h •2 k Eζ 2 k 1{ζ k ≥ 1} + h •2 k E ζ k + (1 -ζ k ) 2 1{ζ k < 1} ≤(1 + z)h •2 k + 1 + 1 z h •2 k min 1, 4σ 2 b 2 k . (40)
Finally, combining (38), (40), and (39), we finish the proof.

Minimax multivariate inversion

Since the upper bounds in Theorems 1 and 2 are almost equivalent but Theorem 2 deals with a more general statistical model, we will focus in what follows on Model [START_REF] Cavalier | Adaptive estimation for inverse problems with noisy operators[END_REF]. With the help of Theorem 2 one can easily compute the maximal risk E θ(y , z) -θ 2 over the ellipsoid

Θ = θ : p k=1 θ 2 k a 2 k ≤ 1 , where {a 2 k , k = 1, . . . , p} is a given monotone sequence a 2 1 ≤ a 2 2 ≤ • • • ≤ a 2 p .
Theorem 3. The maximal risk of θ(y , z) from (25) is upper-bounded as follows :

sup θ∈Θ E θ(y , z) -θ 2 1/2 ≤ R(Σ, Θ) + R + (Σ, Θ), where R(Σ, Θ) = 4 max k 1 ( 2 + b 2 k Σ 2 k ) 2 a 2 k + 2 p k=1 Σ 4 k b 2 k ( 2 + Σ 2 k b 2 k ) 2 , R + (Σ, Θ) = 4σ 2 max k Σ 4 k b 2 k ( 2 + Σ 2 k b 2 k ) 2 a 2 k + 2 p k=1 Σ 4 k b 2 k ( 2 + Σ 2 k b 2 k ) 2 min 1, 4σ 2 b 2 k .
Proof. It follows immediately from Equation (36) combined with

h • k = b 2 k Σ 2 k 2 + b 2 k Σ 2 k , sup θ∈Θ (1 -h • ) • θ 2 ≤ max k (1 -h • k ) 2 a -2 k , sup θ∈Θ p k=1 h •2 k θ 2 k b 2 k ≤ max k h •2 k b 2 k a 2 k .
The minimax risk of the projection method can be controlled with the help of the following theorem.

Theorem 4. Let θpr (y k , z k ) = 1{k ≤ W } b-2 (z k )y k , then sup θ∈Θ E θpr (y , z) -θ 2 1/2 ≤ R pr (W, Θ) + R + pr (W, Θ),
where

R pr (W, Θ) =a -2 W +1 + 2 W k=1 1 b 2 k , R + pr (W, Θ) = 4σ 2 max k∈[1,W ] 1 b 2 k a 2 k .
Proof. It follows immediately from (37).

Example. We illustrate the above theorem with a simple example, assuming that p = ∞ and

b 2 k = B 2 k -2q , a 2 k = A -2 k 2g , k = 1, 2
, . . . . Computing the risk of the spectral cut-off method in this case is very simple. We have

R pr (W, Θ) = A 2 (W + 1) 2q + 2 B 2 W k=1 k 2g , R + pr (W, Θ) = 4σ 2 A 2 W 2(g-q) + B 2 ,
where (x) + = max(0, x). Very often, we are interested in the minimax projection bandwidth minimizing R pr (W, Θ). This bandwidth can be easily computed for small , namely, .

W • =
Notice also that

R + pr (W • , Θ) = (1 + o(1)) 4σ 2 A 2 B 2 2qA 2 B 2 2
2(g-q) + /(1+2q+2g) , → 0.

So, we see that when q ≥ g the excess risk R + pr (W • , Θ) has a parametric order σ 2 .

This example shows, in particular, that one can construct good estimates of θ even in the case, where σ 2 2 . This prompts, for instance, that the upper bounds in Proposition 3.2 and Theorem 5.1 in [START_REF] Hoffmann | Nonlinear estimation for linear inverse problems with error in the operator[END_REF] might be improved, since they are expressed in terms of max( 2 , σ 2 ).

Let us emphasize that the minimax projection bandwidth W • cannot be used in practice since it depends strongly on A 2 and q which are hardly known. Therefore, in applications, only data-driven projection bandwidths can be used. Constructing good data-driven bandwidths is very important in applied statistics and we will provide a natural solution to this problem in a forthcoming paper.

Sometimes we are interested in computing Σ

Acknowledgments

This work was partially supported by RFBR research projects 13-01-12447 and 13-07-12111.

Figure 1 :

 1 Figure 1: Risk functions R 0 (β) and R 1 (β) for b-1 (z).

Figure 2 :

 2 Figure 2: Risk functions R 0 (β) and R 1 (β) for the estimator from (22).

Figure 3 :Lemma 5 .

 35 Figure 3: Risk functions R 0 (β) and R 1 (β) for μ-2 β (z).

  arg min W R pr (W, Θ) = (1 + o(1))

2 k 2 k = 2 b 2 k |a k | µ - 1 +, where µ is a root of 2 ∞

 222212 resulting in asymptotically (as → 0) minimax estimators over Θ provided that b k are assumed to be known. Recall that an asymptotically minimax estimate θ (y) based on the observationsy k = b k θ k + ξ k , k = 1, . . . is defined by sup θ∈Θ E θ (y) -θ 2 = (1 + o(1)) inf θ sup θ∈Θ E θ(y) -θ 2 , → 0,where inf is taken over all estimates of θ. The theory of asymptotically minimax estimation over ellipsoids has been developed in the pioneering article[START_REF] Pinsker | Optimal filtering of square integrable signals in Gaussian white noise[END_REF]. It follows, in particular, from this paper that ifb 2 k = (1 + o(1))B 2 k 2g , a 2 k = (1 + o(1))A -2 k -2q for A, B, q, g ∈ (0, ∞),as k → ∞, then asymptotically minimax estimate of θ is given by (26) with Σ


Jianbing Ma

Weiru Liu
email: w.liu@qub.ac.uk

Didier Dubois
email: dubois@irit.fr

Rational Partial Choice Functions and Their Application to Belief Revision

Necessary and sufficient conditions for choice functions to be rational have been intensively studied in the past. However, in these attempts, a choice function is completely specified. That is, given any subset of options, called an issue, the best option over that issue is always known, whilst in real-world scenarios, it is very often that only a few choices are known instead of all. In this paper, we study partial choice functions and investigate necessary and sufficient rationality conditions for situations where only a few choices are known. We prove that our necessary and sufficient condition for partial choice functions boils down to the necessary and sufficient conditions for complete choice functions proposed in the literature. Choice functions have been instrumental in belief revision theory. That is, in most approaches to belief revision, the problem studied can simply be described as the choice of possible worlds compatible with the input information, given an agent's prior belief state. The main effort has been to devise strategies in order to infer the agents revised belief state. Our study considers the converse problem: given a collection of input information items and their corresponding revision results (as provided by an agent), does there exist a rational revision operation used by the agent and a consistent belief state that may explain the observed results?

Introduction

Choice functions are commonly used in economic and social sciences to describe the process following which, faced with a ranking problem, an individual makes choices by selecting a few outcomes in each subset of possible outcomes (such a subset is called an issue); the selected outcomes are those to which no other outcomes can be strictly more preferred according to its preference. These observable choices testify of a non-directly observable preference relation. There has been a considerable amount of study about the definition of optimal choices under different types of preference relations (e.g., [START_REF] Arrow | Uncertainty and the welfare economics of medical care[END_REF]). Equally interesting is the converse problem described as: given a choice function, that is, an abstract mapping that selects some desirable outcomes for each issue [START_REF] Moulin | Choice functions over a finite set: A summary[END_REF], does there exist an underlying rational preference relation from which this choice function can be derived? Several solutions to this problem exist for a long time, for instance [START_REF] Chernoff | Rational selection of decision functions[END_REF][START_REF] Moulin | Choice functions over a finite set: A summary[END_REF][START_REF] Sen | Internal consistency of choice[END_REF]. However, in these attempts, the choice functions are full-fledged mappings that provide every issue with a set of mapped outcomes. In real-world scenarios, it is very often that choices of only a few issues are known, instead of choices over all the issues. Actually it is natural that given the whole set of issues, only a subset of them may have been exposed to the agent and hence the agent can only provide a limited response to the issues. Therefore, it is interesting to study conditions ensuring the existence of a rational preference that can reflect these choices. In this paper, we define the concept of partial choice functions and investigate their necessary and sufficient conditions for scenarios where only a few choices are known. We also examine the relationships between partial and (complete) choice functions and between their necessary and sufficient conditions.

Interestingly, our study and investigation result can be applied to study the converse belief revision problem. Belief revision [1, 13, 8, 17, 18, 20-22, 19, 16, 11] performs belief change on an agent's beliefs when new evidence is received. In classical belief revision, it is a default assumption that there is a clear and consistent belief structure (e.g., a total pre-order over possible worlds, the most plausible possible worlds of which generate the belief set) embedded in an agent's mind, based on which this agent performs revision upon receiving new information. Here, we consider the converse of this problem. That is, if there are several revision scenarios, each of which consisting of a piece of new information and its corresponding revision result (represented as pairs (µ i , φ i ) subsequently), then does there exist a rational belief structure from which these revision scenarios proceed. In other words, for each input µ i , does the agent exhibit the existence of a belief structure where φ i is exactly the revision result based on µ i in scenario (µ i , φ i )? Figures 1 and2 provide intuitive illustration of the difference between classic belief revision and its converse problem. That is, in classic belief revision, given an agent's a priori belief state and a newly received piece of information, appropriate revision strategies (operators) are designed to revise the agent's belief set and derive a new one. Whilst the converse problem is: given a set of revision scenarios (pairs of evidence and revision result), does the agent exhibit the existence of a consistent prior epistemic state justifying these revision results? Here by epistemic state, we mean the ranking of possible worlds, hence the corresponding prior belief set.

Belief revision1 always respects the Success postulate such that the revision result (φ i ) should respect the new information (µ i ). Semantically, the models of the revision result should be a subset of the models of the formula representing the new information (i.e., M od(φ i ) ⊆ M od(µ i )). Therefore, the converse belief revision problem reduces to what we have discussed above on inducing a preference relation for choices. Actually, belief revision theory has borrowed material from choice function theory via axioms 7 and 8 of the AGM framework (see Section 4 for details). This does not come as a surprise. An extensive discussion of the relationships between choice function axioms and properties of non-monotonic consequences, a topic closely related to belief revision, can be found in [START_REF] Lindström | A semantic approach to nonmonotonic reasoning: inference operations and choice[END_REF][START_REF] Lehmann | Nonmonotonic logics and semantics[END_REF][START_REF] Rott | Change, choice and inference[END_REF]. These papers also include an extensive bibliography on that topic. The last two AGM axioms are in fact not characteristic of the revision problem and one may argue that, by means of the two axioms, the AGM approach chooses as much an uncertainty framework that is not probabilistic by means of such two axioms as it provides core axioms for belief revision (the first six). Note that the converse belief revision problem discussed here is different from the converse problem of iterated belief revision addressed in [START_REF] Booth | Reconstructing an agent's epistemic state from observations[END_REF] and the converse belief revision in multi-agent systems [START_REF] Biskup | Revising belief without revealing secrets[END_REF]. Here, the multiple revision scenarios do not correspond to a sequence of revision actions, where the iteration may cause successive changes of an agent's belief structure. Instead, here we assume a given agent's belief structure, to which every new piece of information is applied separately so as to derive a different new belief state. This is in line with the view of belief revision as defeasible inference discussed in [START_REF] Delgrande | Iterated revision as prioritized merging[END_REF][START_REF] Dubois | Three scenarios for the revision of epistemic states[END_REF], one of the three kinds of belief revision perspectives.

Below, we first provide some preliminaries in Section 2. In Section 3, we define the notion of partial choice function and propose a necessary and sufficient condition for a partial choice function to be rational. We then compare our solution with related works in Section 4, showing that our condition can recover the conditions proposed in the literature. In Section 5, we show how this condition can be used to solve the converse belief revision problem. Finally, in Section 6, we conclude the paper.

Preliminaries

Logic: We consider a propositional language L defined in a usual sense. We use M od(φ) to denote the set of models for φ. We write φ |= µ iff M od(φ) ⊆ M od(µ). For a set A of models, f orm(A) denotes a formula whose set of models is A. That is, M od(f orm(A)) = A.

Choice Functions: Let X denote the finite set of all conceivable outcomes, and P(X) represent the family of all non-empty subsets of X. Each A ∈ P(X) is called an issue (or agenda) and let R denote a complete and reflexive binary relation defined on X. R is a total pre-order if it is transitive, i.e., xRy, yRz implies xRz for any x, y, z ∈ X.

Let M (A, R) denote the set of maximal elements (choices) in A such that (so here xRy means x ≥ y): M (A, R) = {x|x ∈ A and xRy, ∀y ∈ A}. A choice function is a mapping F : P(X) → P(X) satisfying: ∀A ∈ P(X), F(A) ⊆ A. A choice function F is said to be rational, if there is a total preorder R such that for all A ∈ P(X), F(A) = M (A, R).

Elements x and y are called indifferent in terms of R, denoted x ∼ R y, if both xRy and yRx hold.

If F is a mapping from P(X) → P(X), then for any issue A ⊆ X, we know the choice F(A) over A. But in real-world applications, usually we only know choices over a few issues. For instance, if we view a country as the set of its cities, then for a familiar country, we can tell our choices on preferred cities, while for unfamiliar countries, we cannot. Formally, we define the notion of a partial choice function.

Definition 1 Let Ω be a subset of P(X), a partial choice function F over Ω is a map- ping: Ω → P(X) satisfying: ∀A ∈ Ω, F(A) ⊆ A.
Here Ω denotes the set of issues whose maximal elements are known. Note that in [START_REF] Bonanno | Rational choice and agm belief revision[END_REF], although it is not explicitly defined, the choice frame proposed does contain a partial choice function.

Let Ω = A∈Ω A denote the union of all sets in Ω. Similarly, we denote a partial choice function F over Ω as rational2 if there is a total pre-order R over Ω such that for all A ∈ Ω, F(A) = M (A, R). Obviously, if Ω = P(X), then our definition reduces to the standard definition.

Note that a total pre-order R over Ω can be easily extended to X such that: for any w, w ′ ∈ Ω, w ∼ R w ′ ; and for w ∈ Ω, w ′ ∈ Ω, wRw ′ but not w ′ Rw (this is a matter of convention, considering that options outside Ω are less relevant here).

With this extension,

A ∈ Ω, F(A) = M (A, R) still holds for any A ∈ Ω.
Now we provide a necessary and sufficient condition ensuring the rationality of a partial choice function:

Let (A 1 , • • • , A i , • • • , A k ) be a sequence of issues and the circular permutation σ(i) = i + 1, i = 1, . . . , k -1 and σ(k) = 1. Circular Consistency If A σ(i) ∩ F (Ai) = ∅, 1 ≤ i ≤ k, then A σ(i) ∩ F (Ai) = Ai ∩ F (A σ(i) ), 1 ≤ i ≤ k.
This Circular Consistency condition shows that if an issue and the outcomes of the next issue are correlated circularly for k issues, then this correlation establishes equivalent relations between issues and outcomes circularly.

We have the following result on two successive issues.

Lemma 1 Let Ω = {A, A ′ }, if

the Circular Consistency condition holds, and

A ′ ∩ F(A) = A ∩ F(A ′ ), then A ′ ∩ F(A) = F(A) ∩ F(A ′ ).
Fig. 2 illustrates Lemma 1. The two circles represent A i and A i+1 , respectively. The intersections of the rectangle with the two circles represent F(A i ) and F(A i+1 ), respectively, and the crossed section represents F(A i ) ∩ F(A i+1 ). Now we give the following representation theorem which shows that the above condition is necessary and sufficient to ensure the partial choice function being rational.

Theorem 1 Let F be a partial choice function over Ω, then F is rational if and only if F satisfies the Circular Consistency condition.

Fig. 2. Illustration of the two issue case

Proof: The only if part is simple and we omit it here due to lack of space.

For the if part, assume that F satisfies the Circular Consistency condition. We use graph theory to prove the existence of a total pre-order R. We view each issue A ∈ Ω as a point. If F(A i ) ∩ F(A j ) = ∅, then we connect points A i and A j with an edge (no direction). Let G denote the formed graph. Graph G has several (≤ n) connected components 3 , each of which contains a set of points (issues).

A simple fact that should be mentioned here is that for any two points A i , A j in the same connected component, we could find a set of points

{A t1 , • • • , A tm } such that A t1 = A i , A tm = A j and for any t s , t s+1 , F(A ts ) ∩ F(A ts+1 ) = ∅.
That is, there is a path between points A i and A j , which is ensured by the connectiveness of the connected component. Now we view each connected component as a node. For two points A i , A j in different nodes X, Y , respectively, if F(A i ) ∩ A j = ∅, then we create a directed edge from X to Y . If there are multiple directed edges from X to Y , we compress them as one edge. This forms a new graph G ′ .

Here we should point out an important fact:

G ′ has no directed cycles. Otherwise suppose G ′ has a cycle X 1 → X 2 → • • • → X k → X 1 . Without loss of general- ity, let points A i1 , A i2 be contained in X i (1 ≤ i ≤ k) and F(A (i-1)2 ∩ A i1 = ∅, F(A i2 ) ∩ A (i+1)1 = ∅ hold (when i = k, i + 1 is changed to 1; when i = 1, i -1 is changed to k).
As mentioned earlier, points i 1 and i 2 in connected component X i can also be connected by a path

{A t1 = A i1 , • • • , A tm i = A i2 } such that F(A ts ) ∩ A ts+1 = ∅ (Actually it is F(A ts ) ∩ F(A ts+1 ) = ∅. However, clearly F(A ts ) ∩ F(A ts+1 ) = ∅ implies F(A ts ) ∩ A ts+1 = ∅), 1 ≤ s < m i . Hence finally we get a cycle {A i1 , • • • , A i2 , A (i+1)1 , • • • , A (i+1)2 , • • • , A (i-1)2 , A i1 }.
For any two adjacent points A l , A l ′ in that cycle, we always have F(A l )∩A l ′ = ∅. By the Circular Consistency condition and Lemma 1, we get

F(A (i-1)2 )∩F(A i1 ) = F(A (i-1)2 )∩A i1 = ∅.
That is, points A (i-1)2 and A i1 should be in the same node, which creates a contradiction since they are in different nodes X i-1 and X i , respectively.

Since G ′ has no directed cycles, each of its directed connected component is a connected directed acyclic graph (DAG). For each of such DAG H with nodes Y 1 , • • • , Y k ∈ H, we establish a mapping f H associating each node of H with a natural number. To do this, first we associate each node with a number indicating its maximal level.

-Any node with 0 in-degree 4 is assigned level 0.

-Iteratively, a node is assigned with level k if each of its parent nodes is assigned with a level value such that the maximal value among these is k -1 5 .

With the concept of level of node, we define f H as follows.

-Any node with 0 in-degree (level 0) is assigned 1.

-Iteratively (by increasing the level value by 1 each time), for any node Z with s in-degree and hence has s directed in-edges,

Z 1 → Z, • • •, Z s → Z, f H (Z) = s i=1 f H (Z i ) + s. This construction ensures that if a directed edge Z ′ → Z exists, then f H (Z ′ ) < f H (Z).
Now we establish a mapping f : G → N such that for any point

A i in tree H (in fact in a node Y t of H), f (A i ) = f H (Y t ).
Obviously we can see that any two points in the same sub-graph of G (hence in the same node) have the same f value.

Finally we establish a mapping g :

Ω → N ∪ {0} as follows. If w ∈ F(A i ), then g(w) = f (A i ). If w ∈ Ai∈Ω F(A i ), then g(w) = 0.
Here we need to clarify that g is a valid mapping. That is, we

must show if w ∈ F(A i ) ∩ F(A j ), then f (A i ) = f (A j ). In fact, if F(A i ) ∩ F(A j ) = ∅, then points A i and A j are in the same connected component of G, and hence f (A i ) = f (A j ).
We define R as:

wRw ′ if and only if g(w) ≥ g(w ′ ). It remains to show ∀i, F(A i ) = M (A i , R).
By the definition of g, we know that if w, w ′ ∈ F(A i ), then g(w) = g(w ′ ). Now it is sufficient to show that if w ∈ F(A i ) and w ′ ∈ A i \ F(A i ), then g(w) > g(w ′ ).

If w ′ ∈ Ai∈Ω F(A i ), then g(w) ≥ 1 > 0 = g(w ′ ).

Else suppose w ′ is in some

F(A j ) (hence w ′ ∈ A i ∩ F(A j )), then F(A j ) ∩ A i = ∅. If F(A j ) ∩ F(A i ) = ∅, then according to Lemma 1, we have F(A j ) ∩ F(A i ) = F(A j ) ∩ A i , hence w ′ ∈ F(A i ) ∩ F(A j ) which contradicts with w ′ ∈ F(A i ).
Therefore, we should have F(A j )∩F(A i ) = ∅, which implies that points A j and A i are not in the same connected component of G, otherwise F(A j ) ∩ F(A i ) = F(A j ) ∩ A i = ∅. Now we can conclude that in graph G ′ , there is a directed edge from the node containing point A j to the node containing point A i . Therefore, by the definition of f H and f , we know f (A i ) > f (A j ). Hence g(w) = f (A i ) > f (A j ) = g(w ′ ). This completes the proof. ✷ Note that this proof also shows how to construct such a pre-order R by which F is rationalized.

Fig. 3 illustrates the above theorem where each solid circle represents an A i . The intersection of a solid circle (representing A i ) with the dashed red ring in the center represents F(A i ). Note that Fig. 3 just shows a sequence of issues that satisfy the Fig. 3. Illustration of the k Issue Case Circular Consistency condition. However, there could be multiple sequences (not necessarily disjoint), each of which satisfies the Circular Consistency condition. So Fig. 3 is not necessarily a complete view for all sets A 1 , • • • , A n .

From Fig. 3, we can also see that ∀x ∈ F(A i ), y ∈ F(A j ), 1 ≤ i, j ≤ k, we have x ∼ R y (as elements in the dashed red ring have the same plausibility). Note that for z ∈ F(A m ), m > k, we do not necessarily have x ∼ R z.

Related Work

Classical works proved that a choice function F is rational if and only if it satisfies the following condition [START_REF] Moulin | Choice functions over a finite set: A summary[END_REF][START_REF] Sen | Internal consistency of choice[END_REF]: Sen for all B ∈ P(X) and all a ∈ B, a ∈ F(B) if and only if ∀b ∈ B, a ∈ F({a, b}).

As a corollary, when a partial choice function turns into a choice function, our Circular Consistency condition implies condition Sen.

Corollary 1 Let F be a choice function, then if it satisfies Circular Consistency, it satisfies Sen.

Also, in [START_REF] Chernoff | Rational selection of decision functions[END_REF], Chernoff introduced a necessary condition for a choice function to be rational:

Chernoff for all B, B ′ ∈ P(X), if B ⊆ B ′ , then F(B ′ ) ∩ B ⊆ F(B).
Again, when a partial choice function turns into a choice function, our Circular Consistency condition also induces condition Chernoff.

Corollary 2 Let F be a choice function, then if it satisfies Circular Consistency, it satisfies Chernoff.

A lot of choice function conditions are reviewed in [START_REF] Lindström | A semantic approach to nonmonotonic reasoning: inference operations and choice[END_REF][START_REF] Lehmann | Nonmonotonic logics and semantics[END_REF][START_REF] Rott | Change, choice and inference[END_REF] relating choice function theory to AGM theory and nonmonotonic reasoning. It can be shown that most of these conditions are derivable from our Circular Consistency condition. Since most of these conditions are straightforward to understand and also due to space limitation, here we omit most of them and only present the well-known Chernoff and Sen conditions. Interested readers can refer to [START_REF] Lindström | A semantic approach to nonmonotonic reasoning: inference operations and choice[END_REF] for details. Now we first explore relationships between our approach to the well-known AGM framework. Let K be a consistent belief set representing the agent's initial beliefs. K is represented as a set of formulas. Let B K be a mapping from K to any subset of formulas. The AGM axioms are listed as follows:

AGM1 B K (φ) = [B K (φ)] P L
where for any set of formulas S, [S] P L is defined as the PL-deductive closure of S in the usual way.

AGM2 φ ∈ B K (φ). AGM3 B K (φ) ⊆ [K ∪ {φ}] P L . AGM4 If ¬φ ∈ K, then [K ∪ {φ}] P L ⊆ B K (φ). AGM5 B K (φ) = Φ 0 if
and only if φ is a contradictory, where Φ 0 is the set of formulas of the propositional language.

AGM6 If φ ↔ ψ is a tautology, then B K (φ) = B K (ψ). AGM7 B K (φ ∧ ψ) ⊆ [B K (φ) ∪ {φ}] P L . AGM8 If ¬ψ ∈ B K (φ), then [B K (φ) ∪ {φ}] P L ⊆ B K (φ ∧ ψ).
Note that the Chernoff condition is very similar to the above AGM7 and AGM8 axioms 6 . It is easy to see that B K is a choice function at the semantic level. That is, M od(B K (φ)) ⊆ M od(φ) for any φ. For simplicity, by abuse of notation, we write B K (M od(φ)) ⊆ M od(φ) (here notation B K is taken as a mapping from a set of models to another set of models). Now, let B = M od(ψ ∧ φ), B ′ = M od(φ) and F = B K , then B ⊆ B ′ , and hence we obtain

B K (B ′ ) ∩ B ⊆ B K (B) which is equivalent to B K (φ) ∧ ψ |= B K (ψ ∧ φ).
A general condition called Arrow's condition [START_REF] Arrow | Uncertainty and the welfare economics of medical care[END_REF] that generalizes both Sen and Chernoff says: if B ⊆ B ′ , and

F(B ′ ) ∩ B = ∅, then F(B) = F(B ′ ) ∩ B.
Indeed, if some of the best in B ′ , belong to its subset B, none of the other elements in B can be a best element in B (they are dominated inside B ′ ). This is closely connected to Axiom 8 in the AGM framework.

In [START_REF] Bonanno | Rational choice and agm belief revision[END_REF], the correspondence between AGM revision and rational choice functions is studied. It shows that a choice frame 7 is rational if and only if it is AGM-consistent, where AGM-consistent is defined as: for every interpretation 8 of the choice frame, the associated partial belief revision function can be extended to a full-domain belief revision function that satisfies the AGM-postulates.

Let F ORM (A) = {φ : M od(φ) ∈ A} be a set of formulas whose set of models are subsets of A. Note that F ORM (A) is different from f orm(A). With this notation, for a partial choice function, the associated partial belief revision function is defined as follows.

Definition 2 Let F be a partial choice function such that F : Ω → P(X), the associated belief revision function B F is a mapping

B F : F ORM (Ω) → F ORM (P(X)) such that B F (φ) = F(M od(φ)).
A full-domain belief revision function B : F ORM (P(X)) → F ORM (P(X)) is called an extension of a partial belief revision function

B F if for any φ ∈ F ORM (Ω), B(φ) = B F (φ).
We can also define a partial choice function is AGM-consistent if its associated partial belief revision function can be extended to a full-domain belief revision function that satisfies the AGM-postulates. Now we have the following corollary.

Corollary 3 Let F be a partial choice function, then it satisfies Circular Consistency if and only if it is AGM-consistent.

This Corollary suggests that there is an unearthed relationship between the Circular Consistency condition and the AGM postulates. We will leave this topic in future work.

Remarks: Although condition Chernoff looks similar to a Monotonicity property, Monotonicity does not hold for rational partial choice functions in general.

Mon If A 1 ⊆ A 2 , then F(A 1 ) ⊆ F(A 2 ). Example 1 Let A 1 = {w 1 , w 2 }, A 2 = {w 1 , w 2 , w 3 }, F(A 1 ) = {w 1 , w 2 }, and F(A 2 ) = {w 3 }. We could see that F is a partial choice function over Ω = {A 1 , A 2 }
and it is rational in terms of a pre-order such that w 3 ≺ w 1 ≃ w 2 , i.e., we indeed have

F(A 1 ) = M (A 1 , ) and F(A 2 ) = M (A 2 ,
). But it does not satisfy the Monotonicity property. That is, we have A 1 ⊂ A 2 , but we do not have F(A 1 ) ⊆ F(A 2 ).

Converse Belief Revision Problem

As mentioned in Introduction, our result can be applied to the converse belief revision problem. Here we provide two necessary and sufficient conditions such that if a set of revision scenarios satisfy these two conditions, then there must be a consistent belief structure in the agent's mind, and vice versa.

To proceed, first, let us formalize the definition of a revision scenario.

Definition 3 (Revision scenario) A revision scenario, denoted as rs = (µ, φ), is a pair of formulae µ and φ, where µ represents a new piece of evidence and φ represents the revision result upon receiving µ.

Below, we simply call a revision scenario a scenario. Now we propose two conditions, i.e., Success and Circular Consistency conditions. Let rs i = (µ i , φ i ), 1 ≤ i ≤ n be n distinct revision scenarios.

Success For any rs

i = (µ i , φ i ), φ i |= µ i , 1 ≤ i ≤ n.
Explanation: This is a variant of the well-known success postulate in the AGM framework. The revision result should respect the evidence. Circular Consistency Let {(µ 1 , φ 1 ), • • • , (µ k , φ k )} be any set of revision scenarios (i.e., a subset of the set of all rs i s) such that k ≤ n, and let σ be a circular permutation such that σ(i

) = i + 1, i = 1 . . . k, σ(k) = 1. Then If µ σ(i) ∧ φ i |= ⊥, 1 ≤ i ≤ k, Then µ σ(i) ∧ φ i ≡ µ i ∧ φ σ(i) , 1 ≤ i ≤ k.
As a corollary of Theorem 1, the following representation theorem shows that the above two conditions are necessary and sufficient to ensure that an agent has a consistent belief structure.

Corollary 4 Let RS be a set of scenarios, then there exists a belief structure, represented by a total pre-order over W , s.t., ∀rs = (µ, φ) ∈ RS, φ = min(M od(µ), ) if and only if scenarios in RS satisfy Success and Circular Consistency.

Example 2 Suppose a hacking action was discovered originating from one of the PCs in an office. The log file shows that the action was conducted between 4pm to 5pm. A suspect Y declared that he left the office between 4pm and 5pm and he did not log on to any computer before he left. A witness suggested that Y was seen doing something with that particular computer at that time. Now if suspect Y explains:

Viewing web pages: Y was viewing web pages, OR Cleaning the monitor: Y was cleaning the equipment. Does Y have a consistent belief structure with each one of these two explanations? The answer to the above question is important. Certainly, we cannot say Y is innocent if Y does have a consistent belief structure, as it only shows that Y 's statements are coherent. However, Y should be considered highly suspiciously if he fails to demonstrate consistency in its response to questions/evidence.

Here suppose a system security engineer has two pieces of evidence: there was a hacking action during 4pm to 5pm and Y was seen using the PC at the time. Y 's reactions to the two pieces of evidence may allow the security engineer spotting an inconsistency between the statements, or equivalently, establishing whether Y is applying a consistent belief structure when responding to the two inputs.

Let µ 1 be 'a hacking action was discovered from 4pm to 5pm', ψ 1 be 'Y did not log on to any computer in the office'. Then φ 1 = µ 1 ∧ ψ 1 is Y 's revision result upon receiving µ 1 , meaning that "although there was a hacking action, it is not me (i.e., Y ) since I did not log on to any computer". Let µ 2 be 'Y was seen doing something with the PC at that time'. To consider possible revision results for the two situations described above, let φ 2 be 'Y was viewing web pages', and φ ′ 2 be 'Y was cleaning the monitor'. Here we should note that φ 1 ∧ φ 2 ≡ ⊥ since if Y was viewing web pages, then Y must have logged on to the PC, conflicting with Y 's claim not logging on to any computers in the office. In this situation, as we only focus on two possibilities: 'Y was viewing web pages' and 'Y was cleaning the monitor', for simplicity we can assume that these two are exclusive and exhaustive. Hence it is easy to see that 'Y was cleaning the monitor' indicates 'Y did not log on to the PC' and 'Y was viewing web pages' indicates 'Y had logged on to the PC', therefore we have φ 2 = µ 2 ∧ ¬ψ 1 and φ ′ 2 = µ 2 ∧ ψ 1 . Now to justify whether Y has a consistent belief structure, we check the two postulates. Therefore, by Corollary 4, we obtain the following conclusions:

Success Obviously we have

φ 1 |= µ 1 , φ 2 |= µ 2 ,
-If the revision result by Y is 'Y was viewing web pages', then Y does not have a consistent belief structure, and hence Y is highly suspect. -If the revision result by Y (his explanation) is 'Y was cleaning the monitor, then Y has a consistent belief structure, and hence Y might be innocent.

These conclusions are in line with our intuition. In the second case, a belief structure for Y is: :

{µ 1 ∧ ψ 1 ≺ µ 1 ∧ ¬ψ 1 ≃ µ 2 ∧ ψ 1 ≺ µ 2 ∧ ¬ψ 1 }.
Here note that there are both models for ψ 1 and models for ¬ψ 1 appearing in Y 's belief structure. This is because it is an inferred belief structure from the current information. Y 's actual belief structure could be more elaborated, but should be consistent with the inferred belief structure.

Conclusion

In this paper, we proved a necessary and sufficient condition, i.e., Circular Consistency, for a partial choice function to be rational. Also, we have demonstrated that this solution can be used to construct a consistent belief structure for an agent from a set of revision scenarios. In addition, by comparing with related works, we proved that when a partial choice function turns into a choice function, our Circular Consistency condition can recover the necessary and sufficient conditions proposed before.

In terms of belief revision, our study hinted why lying could be a hard thing to do: one always needs to keep a track of what had been said to maintain consistency between different scenarios. This commonsense is widely acknowledged, and it is again partially proved in this paper in the belief revision scenario. Our study also provided some insights about belief revision in general.

As future work, one attempt is to investigate whether there are simpler conditions that can be used to replace the Circular Consistency condition, especially on whether the Circular Consistency condition can be decomposed into some AGM-like or Sen, Chernoff-like conditions. In addition, there is a notion called sub-rationality introduced by Deb [START_REF] Deb | Binariness and rational choice[END_REF] such that a choice function F is sub-rational if for some order R, M (A, R) ⊆ F(A) holds for all A ∈ P(X). It is interesting to study the necessary and sufficient conditions for sub-rational partial choice functions.

Fig. 1 .

 1 Fig. 1. Classic (a) and Inversed (b) Belief Revision

  and φ ′ 2 |= µ 2 . Circular Consistency For the two revision results φ 2 and φ ′ 2 , we have µ 1 ∧φ 2 |= ⊥ and µ 2 ∧φ 1 |= ⊥, but we do not have µ 1 ∧φ 2 ≡ µ 2 ∧φ 1 , we have µ 1 ∧ φ ′ 2 |= ⊥ and µ 2 ∧ φ 1 |= ⊥, and we have µ 1 ∧ φ ′ 2 ≡ µ 2 ∧ φ 1 .

Here we do not consider non-prioritized belief revision which can be seen as belief merging.

An alternative definition would be to say a partial choice function F is rational if and only if it can be extended to a rational choice function over P(X) (i.e., there is a rational choice function over P(X) that agrees with F on Ω). These two definitions are equivalent.

In graph theory[START_REF] Biggs | Graph Theory[END_REF], a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which (the subgraph) is connected to no additional vertices. A directed connected component of a directed graph is a subgraph in which any two vertices are connected to each other by a direct path, and which is connected to no additional vertices. Graph G has n connected components only when all Ais are pairwise disjoint. In all other cases, G has less than n connected components. Here notice that the connected components, when viewed as a set of Ais (its points), are a partition of Ω.

The number of directed edges pointing to a node is called the in-degree of the node.

Here we can prove that the level of a node is the maximal length of any path from some 0 in-degree node to this node. However, this result is not essential in our proof so we omit it here.

The similarity between Chernoff and AGM7, AGM8 axioms can be shown more clearly if we define B ′ K (φ) = ψ∈B K (φ) ψ, and hence AGM7 and AGM8 axioms are translated as:

In[START_REF] Bonanno | Rational choice and agm belief revision[END_REF], a choice frame consists of a set of alternatives X, a collection Ω of subsets of X, and a partial choice function F : Ω → P(X).

In[START_REF] Bonanno | Rational choice and agm belief revision[END_REF], an interpretation of a choice frame is obtained by adding a valuation V that assigns to every atom p the subset of X at which p is true, and it is extended to formulas in the usual way. This is a standard definition of an interpretation.

Acknowledgement

This work has been partially funded by EPSRC PACES project (Ref: EP/J012149/1).