Kim Gerdes

Bruno Guillaume
email: bruno.guillaume@inria.fr

Sylvain Kahane
email: sylvain@kahane.fr

Guy Perrier
email: guy.perrier@loria.fr

SUD or Surface-Syntactic Universal Dependencies: An annotation scheme near-isomorphic to UD

published or not. The documents may come

L'archive ouverte

Introduction

Universal Dependencies (UD) is an astonishing collaborative project of dozens of research groups around the world, developing an annotation scheme that is applicable to all languages and proposing treebanks based on that scheme for more than 70 languages from different language families (Nivre et al. 2016). From the start, considerable efforts have been made to avoid an anglocentric scheme, going as far as analyzing English prepositions as case markers. The project is based on an ongoing and constantly evolving collaborative construction of the annotation scheme itself by means of an open online discussion group. The project welcomes and collaborates with enrichment efforts such as the enhanced UD annotation of deep syntax (Schuster & Manning 2016) or the annotation of multi-word expressions (Savary et al. 2015).

Just as any annotation project, UD had to make choices among the different annotation options that commonly reflect opposing goals and downstream applications of the resulting treebanks. UD decided to stick to simple tree structures (compared to graphs with multiple governors) and to favor content words as heads, which is supposed to maximize "parallelism between languages because content words vary less than function words between languages" (UD Syntax: General Principles page http://universal dependencies.org/u/overview/syntax.html). The goal of "maximizing parallelism between languages" might be of use for parser development of neighboring languages, but reducing language differences makes the resulting treebank by definition less interesting for typological research on syntax. In particular, UD does not account for the hierarchy between functional words and tends to flatten syntactic structures. The content-word-centric annotation is also problematic for the internal cohesion of the treebank (cf. the difficulty of coherently annotating complex prepositions that usually contain a content word, Gerdes & Kahane 2016) and it marks a break with syntactic traditions, where headedness is defined by distributional properties of individual words (Bloomfield 1933), see Section 2. 1 One of the central advantages of dependency grammar is the clear distinction of category (the POS, i.e. an intrinsic distributional class) and function (i.e. the specific role a word plays towards another word). Sentences such as She became an architect and proud of it which have given rise to a considerable amount of scholarly discussions (Sag 2003) because an X-bar based phrase structure analysis requires deciding on the category of the coordinated argument first. UD inherited from the Stanford parser 2 a mixed annotation scheme where relation labels include 1 UD defines headedness indirectly via the category of the word: Content words are heads in UD and content words are usually understood as words belonging to open distributional classes, such as nouns, verbs, adjectives, and adverbs. 2 The first versions of the Stanford parser were phrase structure based, providing trees that did not include functional information. The dependency output was a conversion from the phrase structure tree where the relations were computed from the category of the constituents (de Marneffe et al. 2006). categories, as for example nsubj where the "n" indicates the category of the dependent. As a consequence of including the POS of the dependent in the relation name, UD has different labels for the same paradigm occupying the same syntactic position. For instance the complement of consider can be nominal or clausal as in I consider this point / to leave / that you leave and receives three different UD relation labels (obj/xcomp/ccomp).

We propose a new surface-syntactic annotation scheme, similar to UD, that we name SUD for Surface-syntactic Universal Dependencies. We want dependency links as well as the dependency labels to be defined based on purely syntactic criteria (Mel'čuk 1988), giving dependency structures closer to traditional dependency syntax (Meaning-Text Theory, Mel'čuk 1988; Word Grammar, Hudson 1984, 2007; Prague Dependency Treebank, Hajič et al. 2017) and headed constituency trees in phrase structure grammar (X-bar Syntax, Jackendoff 1977; Penn Treebank, Marcus et al. 1993). We also propose a hierarchy of SUD dependency relations that allows for under-specifications of dependency labeling.

We conceived the SUD scheme as an alternative to UD and not as a competing annotation scheme, which means that the annotation scheme should have the same information content, the information being only expressed another way. Put differently, we looked for an annotation scheme based on distributionial criteria with an elementary conversion going both ways without loss, i.e. an "isomorphic" annotation. Since the principles underlying SUD are different, the isomorphism with UD cannot be perfect. As a result, SUD is near-isomorphic to UD, and we have developed two treebank conversion grammars for the Grew platform (http://grew.fr, Bonfante et al. 2018): UD to SUD and SUD to UD. We will evaluate the differences between a UD treebank and the results of a double-conversion through SUD in Section 4.

SUD treebanks can be obtained by simple conversion from UD treebanks and can be useful for teaching and typological studies. Inversely, annotations can be done directly in SUD, and ultimately converted into UD. SUD annotations are less redundant and more economical than UD annotations. For instance SUD uses a simple subj relation because the nominal character of a subject should be indicated only once (as a POS). The distinction between clausal and nominal subjects can be recovered automatically from the POS of the subject and its context, but how this context is taken into account depends on the language. 3 The conversion tool Grew and the conversion grammars are freely distributed, and we envision to propose the UD treebanks also under the automatically converted SUD scheme on the UD website. 4 This SUD annotation scheme proposal could benefit from future discussions and evolutions of the UD ecosystem.

As a side effect, the double UD→SUD→UD conversion provides a powerful error mining tool for UD treebanks. Trees that are not stable under this conversion very often contain non-standard uses of the UD annotation scheme that deserve special attention.

Section 2 explain what is surface syntax, what are the criteria defining a surface syntactic structure and how such a structure differs from UD trees. Our SUD annotation scheme is introduced in Section 3. The conversion between UD and SUD is presented in Section 4 and evaluated on the whole set of UD treebanks.

Surface Syntax

We will present defining criteria for a surface syntactic analysis following Mel'čuk 1988 who proposes three types of criteria: A: When to connect two words? B: Who is the governor in a connection? C: How to classify the dependencies?

Criteria for structural choices

The basic type A criterion is the stand-alone property or "autonomizability": Two words are connected if they can form a speech turn. For example in the sentence The little boy talked to Mary "the boy" or "to Mary" can stand alone with the same meaning, for instance as an answer to a question such as Who talked to Mary? or Who did the little boy talk to?. Autonomizability is not sufficient to determine a dependency structure as the set of connections does not necessarily form a tree, and we need further structural criteria to decide which links to preserve (Gerdes & Kahane 2011). For instance, there are no simple criteria to establish a connection between talk and to or talk and Mary because both talk to, and talk Mary are ungrammatical speech turns. This connection can be established by means of criteria of type B determining who, to or Mary, is the head of to Mary. At this point, UD parts with surface syntax criteria and applies the criterion of "content word as head" whereas surface syntax uses distributional criteria of each individual word. The main criterion is that the surface syntactic head determines the distribution of the unit. This suffices to show that Mary is not the head. Although we cannot test whether to has the same distribution as to Mary because a preposition such as to never appears without a noun or a verb, we consider to to be the head, a choice that is consistent with most if not all theoretical syntactic frameworks. 5 The same reasoning can be applied to the auxiliary-verb connection such as has chosen or the copula-adjective connection such as is happy: chosen never commutes with has chosen. 6 A less clear case of function words as heads is the case of a conjunct in a coordination: I invited Bill and Mary. In most positions, Mary and and Mary cannot commute (again and cannot stand alone and cannot be tested). Here a second distributional criterion can be used: A dependent does not change the distribution of its governor. This shows that Mary cannot be considered as a dependent of and, because the commutation of Mary with units of other POSs (and red, and is sleeping, etc.) completely changes the distribution of the phrase.

Note that the case of the determiner-noun connections is less clear-cut. Both UD and traditional surface syntax (Mel'čuk 1988) chooses the noun as the head although boy and the boy do not have the same distribution. The DP analysis makes the opposite choice (Hudson 1984, 2007, Abney 1987). For these two controversial cases, we keep the UD analysis with the functional word as a dependent.

As an illustration of the flat UD structures compared to SUD, consider Figure 1 showing the analyses of I am out of the office today but will be back tomorrow. The UD tree has depth 3 and a maximum number of 8 dependents per node whereas the SUD tree has depth 5 and only a maximum number of 5 dependents per node. We generalize this observation into a general principle: We believe that the syntactic structure follows the dependency length minimization principle: "Languages tend to minimize the surface syntactic dependency length" because this reduces the cognitive load of language processing (Liu 2008, Futrell et al. 2015). We use this argument to attach each conjunct to its closest neighbor conjuncts and to attach shared dependents to the closest conjunct. This gives us a chaining analysis of coordination instead of UD's bouquet analysis. 7 Figure 2 shows an example that illustrates the structural differences for coordination between UD and SUD. 7 One of the arguments in favor of a bouquet analysis is to allow the disambiguation of embedded coordinations such as A and B or C: For (A and B) or C, or C depends on A, while for A and (B or C), or C depends on B. Nevertheless, this disambiguation is partial because in case of a flat coordination such as A, B, or C, we see that or C also depends on A and thus, the bouquet structure cannot distinguish the embedded (A and B) or C situation from the flat A, B, or C situation.

3 Figure 1: UD and SUD analysis of the same sentence (UD_English-EWT@2.2 email-enronsent38_01-0114 ) Our second criterion is used to decide whether a dependent D that appears in two governordependent relations in two different sentences should be labeled with the same function: The relations are the same if the paradigms of units that can commute with D in the two positions are roughly the same, semantic constraints apart. As an example of a semantic selectional restriction, we establish the same subject positions for "think" and "sink" although the paradigms are not exactly the same: the boat sinks vs. ??? the boat thinks. 9 Inversely, the French verbs parler 'talk' and penser 'think' both have a complement with the preposition à 'to', but the pronominalization of these arguments is different: parler à Mary 'talk to Mary' → lui parler 'speak to her' vs. 8 The inverse is not a necessary condition: We can decide to group together under one relation label two dependents that can co-occur with the same governor, in particular modifiers of verbs or of nouns, which can be repeated. 9 Put differently, the set of elements that can occupy sink's subject position and the set of elements that can occupy think's subject position are different. But the two sets are sufficiently similar and the restriction seems to be of semantic nature that we decide not to introduce an "animate-subject" relation and an "inanimate-subject" relation, but to simply use the subj function for these verbs' first positions. penser à Mary 'think of Mary' → penser à elle 'think of her'. This could lead us to distinguishing two types of arguments (e.g. "indirect object" vs. "oblique complement"). 10 Two positions only rarely have exactly the same paradigms and constraints, but they can be more or less similar. Thus, the notion of function is not absolute but rather relative, which justifies a hierarchy of functions, thus allowing for choosing between coarser or finer grained analyses.

Although, as we have shown, UD has a tendency to use several relation labels for the same syntactic function, the UD annotation scheme can also combine two syntactic functions into one: For example, all PP dependents of a verb are connected with the same relation obl to their governor, conflating prepositional arguments and repeatable modifiers. 11

SUD

With this basis, we have developed an annotation scheme that attempts to remain as close as possible to the UD annotation scheme while obeying to surface-syntactic criteria. The SUD annotation scheme is a surface-syntax annotation 10 A third criterion states that redistribution and agreement constraints for both dependency should be the same. As an example of different redistributions, consider cost vs. win: Peter won 100€ can be passivized but not The book costs 100€. Accordingly, an annotation scheme can decide to establish two distinct functions (e.g. "direct object" vs "measure complement"). In SUD, we unite all these cases under the function name comp, see Section 3.1, therefore not distinguishing "indirect objects" from "oblique complements" or "direct objects" from "measure complements". 11 Several UD treebanks decided to keep the verbal valency and thus to mark the distinction between prepositional arguments and modifiers, for example by means of obl:arg vs. obl:mod, such as Arabic, Cantonese, Chinese, Czech, French, Hindi, Polish, Sanskrit, and Slovak. The secondary annotation label of this argument vs. modifier distinction has not yet been unified across languages and some treebanks use :tmod, :npmod, and :loc vs. :agent among others.

Figure 2: Coordination in UD and in SUD (UD_English-LinES@2.2 257, comma attachment as in the original treebank).

scheme, which implies in particular that: 1. Contrarily to UD, function words such as adpositions, subordinating conjunctions, auxiliaries, and copulas are heads. 2. Words that are in the same paradigm of commutation (and thus occupy the same syntactic position) have the same function, i.e. they are connected to their governor by the same syntactic relation.

Structural choices

In a nutshell, UD's case, mark, aux, and cop dependencies are inverted while other UD dependency directions are preserved. In particular, we kept coordinating conjunctions and determiners as dependents (see Section 2.1).

The directional changes of a relation opens the question of the attachment of the dependents involved in the changes. In UD, function words do not have dependents, but in surface syntax, modifiers of the whole phrase are traditionally attached to the head, which can now be a function word. Put differently, we have to decide which dependents are attached to the function word and which remains on the lexical word. It is generally accepted that the subject is a dependent of the auxiliary or the copula, with whom it agrees in inflectional languages. Highly grammaticalized elements such as negation should go onto the auxiliary whereas arguments should remain on the lexical element. For the sake of simplicity, all modifiers have been attached on the auxiliary in SUD and all arguments except the subject remain on the lexical verb. 12 Conjuncts need special rules to be handled correctly, because sometimes they must be raised (Mary was sleeping and knew it) and sometimes not (Mary was sleeping and snoring).

Labeling choices

SUD introduces four new relations: subj, comp, mod, and unknown and reassign a more specific meaning to the dep label. All subjects have the function subj, grouping together UD's nsubj and csubj. All other arguments of adjectives and verbs have the function comp, bundling UD's obj, iobj, xcomp, and ccomp; comp is also used for all complements of function words such as auxiliaries, copulas, adpositions, and subordinating conjunctions, thus replacing UD's aux, cop, case, and mark. Modifiers have the function mod wherever we can clearly distinguish the modifiers 12 A native SUD annotation might choose to propose more specific rules defining the distribution of modifiers between the function verb and the lexical verb. This has no incidence on the automatically obtained corresponding UD analysis, because such a distinction is flattened when converting into UD. from arguments. If not, we use the dep relation to indicate that we cannot. 13 This dep relation is particularly useful for PP attachments to nouns but also for UD's obl relation if it is not specified further as obl:arg or obl:mod. If we have the argument-modifier distinction for PP dependents of verbs we classify obl:arg as comp and obl:mod as mod. If the nature of the relation cannot be determined, we use the unknown label (where UD used the dep label), which becomes the hypernym of all SUD relations (Figure 3). Compared to UD we thus grouped together relation labels whenever the distinction between them is purely categorical, i.e. contingent on the POS of the governor or the dependent. To avoid annotation redundancy, we do not use UD 's acl, advcl, advmod, amod, aux, case, ccomp, cop, csubj, iobj, mark, nmod, nsubj, nummod, obj, obl, and As a general principle of allowing a varying granularity of dependency relation labels, but also to assure the convertibility with UD, SUD relies heavily on secondary relation labels that are, just like in UD, separated from the main label by a colon: primary:secondary. These secondary labels are optional in a simple native SUD annotation but necessary for a full convertibility into UD. On the contrary, the converted SUD uses the distinction between comp:aux and comp:pass to discriminate the complement of an AUX used as a tense auxiliary and as a passive auxiliary, and it also uses comp:cop or comp:caus for the conversion of UD's cop and aux:caus. The UD relations iobj and obl:arg both give comp:obl in SUD, ccomp and obj give comp:obj, and xcomp gives comp:rais (Table 2). 14 13 The dep relation thus becomes a hypernym of comp, mod and subj, as well as cc and det. 14 Although comp:obj and comp:obl are clearly subfunctions of comp, this is not stricto sensu the case of comp:rais. For example, we consider that (Fr.) dormir 'to sleep' and que tu dormes 'that you sleep' have the same function comp:obj in the context Je veux _ 'I want _', while que tu dormes has a different function comp:obl in the context Je m'étonne _ 'I'm surprised _', where it commutes with a PP de ça 'of that'. A native SUD annotation could thus distinguish comp:obj:rais from comp:obl:rais by means of triple labels.

Convertibility between UD and SUD

The conversion UD → SUD is done in three main steps: 1) transforming the bouquet structure into a chaining analysis (for relations conj, fixed and flat); 2) reversing relations aux, cop, mark and case; 3) mapping UD relations to SUD relations following Table 2. The reverse conversion (SUD → UD) also proceeds in three steps in the same vein.

The second step is the most problematic because a lexical head can have several function words depending on it (up to 7 in UD_Japanese!). In such a case, we must decide which one depends on which one.

To do this, we rely on a universal hierarchy of relations that the auxiliaries have with the main verb, in particular mark relations are higher than aux relations and time and aspect auxiliaries are higher than voice auxiliaries (Van Valin 1984, Cinque 1999). When this information is unavailable we rely on the word order: The closest function word is the SUD governor of the lexical head, the next one is the SUD governor of the first one, and so on.

The conversions (UD → SUD and SUD → UD) we proposed are encoded in a rule-based system. The rules are organized by means of a separation of a universal core rule set and a language specific rule set, which for the time being has only been implemented for French.

We use the Grew software (http://grew.fr) based on a computational Graph Rewriting Model. Each conversion is encoded as a graph rewriting system (GRS): a set of rules and a strategy describing how the rule applications must be ordered. Below, we give an example of an UD → SUD rule for the inversion of mark: We have evaluated the results of the double conversion (from UD to SUD first and then from SUD back to UD) against the original UD annotation with the 122 corpora of version 2.2. The experiment were conducted on the test part of each corpus. The median value of the LAS scores is 94.1%. Three corpora have a LAS score below 75%: UD_Korean-Kaist (71.8%), UD_Japanese-BCCWJ (74.0%) and UD_Japanese-GSD (74.4%). The 3 highest values are for UD_Hungarian-Szeged (98.6%), UD_Italian-ParTUT (98.4%), and UD_Italian-PoSTWITA (98.3%). The median value of the UAS scores is 98.8%. The 3 lowest scores are for UD_Yoruba-YTB (85.0%), UD_Japanese-GSD (87.5%) and UD_Japanese-PUD (87.9%). Two corpora have a 100% UAS score: UD_Warlpiri-UFAL and UD_Telugu-MTG.

rule
Figure 4 shows the distribution of LAS (blue curve) and UAS (green curve) on the 122 treebanks. The two curves present ordered set of values of LAS/UAS (not corresponding to the same corpus ordering). Although the scores are very high, the procedure does not allow to evaluate the two conversion systems separately: A dependency may remain unaffected by both conversions when it should have been, and this error will not be detected.

One central source of the discrepancy between a corpus and its double conversion is the inconsistency between a relation name and the POS of its dependent. For instance, the conversion UD→SUD always produces dep for an amod, but the SUD→UD is not able to recover amod if the dependent is not an ADJ. In the corpus with the lowest LAS score (UD_Korean-Kaist), we observed many unusual associations of relation and POS. In the whole corpus UD_Korean-PUD, 22.4% of the advmod relations have a dependent that is not an ADV, and 43.5% of the aux relations have a dependent which is not an AUX. In the corpus UD_Korean-PUD, all the 323 aux relations have a dependent which is not an AUX. Until now, we have only designed a set of generic rules that may be refined for each language and it is difficult to draw conclusions about the full set of corpora.

A part of these inconsistencies may also be linked to MWEs: An MWE as a whole often has a POS which is different from the POS of its first token. In UD 2.2, 4 corpora contain the feature MWEPOS to annotate the POS of the MWEs (the conversion in the evaluation curves above does not uses this feature). If this information is taken into account in the conversions, the LAS scores significantly increase in 3 of the 4 cases (UD_French-Sequoia: +1.05%, UD_Catalan-AnCora: +0.80%, UD_Spanish-AnCora: +0.75% and UD_Portuguese-Bosque: +0.08%).

We believe that a further exploration of these inconsistencies could provide a crucial step for the improvement of the treebanks as well as the conversion rules. As a next experiment, we plan to introduce a new feature UDPOS to add the expected POS where the current UD POS is unexpected. Then, each UDPOS have to be interpreted as: 1) an annotation error, 2) a place where a MWEPOS is missing, or 3) a special usage of the relation that should be taken into account in the language specific conversion rules.

Conclusion

Based on UD, we propose a new annotation scheme, SUD, which follows standard distributional criteria for headedness and relation labeling and is thus closer to traditional constituency-based surface syntax as well as to dependency-based surface syntax. This means in particular that this new scheme can be employed more easily by users and annotators that are trained in more traditional forms of syntax. As an experiment, we are now developing a new treebank directly in SUD and this treebank will subsequently be converted into UD, the automatic transformation providing a quality and coherence control of the SUD annotation.

Such a format is useful for every computation that concerns the form of the sentence such as word order (Chen et al. submitted) and the relation to prosody, etc. Conversely, UD might be a better entry point to the semantic content of the sentence.

The lower dependency length gives psycholinguistic support to SUD treebanks. Possibly related is the fact that various experiments on parser performance also consistently give an advantage to function-wordheaded structures (Schwartz et al. 2012, Silveira and Manning 2015, Kirilin and Versley 2015, Rehbein et al. 2017) 15 which provides another raison d'être for parallel SUD treebanks. The whole UD 2.2 database, with its 122 treebanks, has been converted into SUD and is already accessible at https://gitlab.inria.fr/grew/ SUD. We would like to see this alternative to be distributed on the UD website as soon as possible and hope that the new scheme will from discussions with the whole community and evolve in parallel to the UD scheme. Then SUD would become an alternative annotation option for UD treebank developers.

As a last point, it appears that the conversion between UD and SUD sheds light on some potential problems in UD treebanks. We have to better understand why the double conversion UD→SUD→UD gives bad results on some treebanks and to what extent this is due to problems in our conversion grammar, or rather caused by an unexpected usage of the UD scheme that could be fixed, either by correcting the treebank or by adapting the annotation reference guide to include and standardize the new analyses of a given construction. It might be useful to adapt the SUD conversion for each language, which could eventually allow for isomorphic transformations. [START_REF]This aspect distinguishes SUD from Enhanced UD. The latter is clearly a new level of annotation with additional information. On the contrary, SUD is an alternative encoding of UD information. minimization in 37 languages[END_REF] Making the UD treebanks SUD compliant would lead to a more homogeneous annotation and could lead the way in the ongoing discussion towards the upcoming UD 3.0 annotation scheme.

  For instance, Mary and to Mary have a profoundly different distribution as they can never commute: Mary slept vs. *To Mary slept. The boy talked to Mary vs. *The boy talked Mary.

Figure 3 :

 3 Figure 3: LAS and UAS of UD→SUD→UD transformations across the UD 2.2 treebanks, displayed on the X-axis by ascending LAS (resp. UAS) order.

Criteria for dependency labels

			nsubj						punct
				cop				conj
				case					cc
					case					aux
					det		obl:tmod				cop	obl:tmod
	I PRON	am AUX	out ADP	of ADP	the DET	office NOUN	today NOUN	but CCONJ	will AUX	be AUX	back ADV	tomorrow NOUN	. PUNCT
													.
								punct
						conj
					mod
					comp						mod
	subj		obl:arg	dep	det			cc	comp:aux	obl:arg
	I PRON	am AUX	out ADP	of ADP	the DET	office NOUN	today NOUN	but CCONJ	will AUX	be AUX	back ADV	tomorrow NOUN	. PUNCT
													.
	2.2

We need criteria to decide whether two dependencies (in two different sentences) must be labeled by the same relation or not. Our first criterion allows us to decide when the governors are the same: If two dependents occupy the same position, i.e. they are mutually exclusive, they must be connected to their governor by the same relation.

8

This implies that in This apple is good for you and Eating this apple is good for you, both this apple and eating this apple must have the same function. Equally, that apple and to eat that apple have the same function in I want that apple and I want to eat that apple. This criterion is currently not used in UD (cf. nsubj vs. csubj for subjects and obj vs. xcomp for objects).

Table 1 :

 1 xcomp relations. All other UD relation labels are preserved. SUD and corresponding UD relation labels

	SUD dependency Corresponding UD dependencies
	dep	acl, amod, nmod, nummod, obl
	comp	aux, ccomp, iobj, obj, obl:arg, xcomp, cop, mark, case
	mod	advcl, advmod, obl:mod
	subj	csubj, nsubj

Table 2 :

 2 UD-SUD transformation correspondences

	left_mark {
	pattern { e:H-[mark]->X1; X1 << H }
	without { H-[aux|aux:pass|aux:caus|cop|
	mark|case]->X2; X1 << X2 }
	commands {
	del_edge e;
	add_edge X1-[comp]-> H;
	shift_out H =[aux|aux:pass|aux:caus|
	cop|mark|case|conj|cc|root]=> X1; } }
	The rule contains three parts: the pattern part says
	that the rule applies on a dependency e labeled
	mark, with a dependent X1 preceding its head H;
	the without part ensures that there is no other
	element aux, cop, case or mark depending on H
	between X1 and H; the commands part describes
	the required modifications on the structure: delete
	the matched edge e, add a new edge comp in the
	reverse order, and the shift_out command gives
	the list of relations that must be moved from node
	H to node X1. It is worth noting that aux, case,
	cop, and mark that remain to be inverted must be
	raised onto the auxiliary.
	6

The clausal character of a phrase is more or less explicit depending on the language. If a language allows for clauses without subjects, without subordinating conjunctions, or without verbs, the conversion SUD → UD has to be adapted accordingly. If all three indicators are absent while the clause-noun distinction remains relevant, we would have to rely on an additional feature in SUD in order to obtain a correct transformation.

For the time being, the SUD treebanks are available on https://gitlab.inria.fr/grew/SUD

The tokenization is quintessential here. If an annotation scheme of a inflectional language decides to separate case markers, such a case marker will become the head of the word[START_REF] Groß | Catenae in morphology[END_REF]

If the dependent of an aux relation is optional, invariable, and non-verbal, it should be tagged as PART. Then it will not be promoted to the head-position in the UD → SUD conversion.


Fabrizio Antenucci

Silvio Franz

Pierfrancesco Urbani

Lenka Zdeborová

On the glassy nature of the hard phase in inference problems

An algorithmically hard phase was described in a range of inference problems: even if the signal can be reconstructed with a small error from an information theoretic point of view, known algorithms fail unless the noise-to-signal ratio is sufficiently small. This hard phase is typically understood as a metastable branch of the dynamical evolution of message passing algorithms. In this work we study the metastable branch for a prototypical inference problem, the low-rank matrix factorization, that presents a hard phase. We show that for noise-to-signal ratios that are below the information theoretic threshold, the posterior measure is composed of an exponential number of metastable glassy states and we compute their entropy, called the complexity. We show that this glassiness extends even slightly below the algorithmic threshold below which the well-known approximate message passing (AMP) algorithm is able to closely reconstruct the signal. Counter-intuitively, we find that the performance of the AMP algorithm is not improved by taking into account the glassy nature of the hard phase.

I. INTRODUCTION

Inference problems are ubiquitous in many scientific areas involving data. They can be summarized as follows: a signal is measured or observed in some way and the inference task is to reconstruct the signal from the set of observations. Many practical applications involving data rely on our ability to solve inference problems fast and efficiently. While from the point of view of computational complexity theory many of the practically important inference problems are algorithmically hard in the worst case, practitioners are solving them every day in many cases of interest. It is hence an important research question to know which types of inference problems can be solved efficiently and which cannot. Formally satisfying answer to this question would lead to an entirely new theory of typical computational complexity, and would likely shed new light on the way we develop algorithms.

For a range of inference problems the Bayesian inference naturally leads to statistical physics of systems with disorder, see e.g. [START_REF] Grassberger | NATO ASI series. Series C: mathematical and physical sciences[END_REF]. This connection was explored in a range of recent works and brought a class of models for inference problem in which the Bayes-optimal inference can be analyzed and presents a first order phase transition. As common in physics in high dimension, the first order phase transition is associated to the existence of a metastable region in which known efficient algorithms fail to reach the theoretical optimal performance. This metastable region was coined as the hard phase, see e.g. [START_REF] Zdeborová | [END_REF]. It has been located in error correcting codes [START_REF] Richardson | Modern coding theory[END_REF][START_REF] Mézard | Information, physics, and computation[END_REF], compressed sensing [START_REF] Krzakala | [END_REF], community detection [6], the hidden-dense submatrix problem [7,8], low-rank estimation problems including data clustering, sparse PCA or tensor factorization [START_REF] Richard | Advances in Neural Information Processing Systems[END_REF][START_REF] Lesieur | Information Theory (ISIT), 2017 IEEE International Symposium on[END_REF], learning in neural networks [START_REF] Györgyi | [END_REF]. The nature of the hard phase in all these problems is of the same origin, and therefore it is expected that algorithmic improvement in any of them would lead to improvement in all the others as well.

In the current state-of-the-art (including the references above) the hard phase is located as a performance barrier of a class of message passing algorithms. Message passing algorithms can be seen as spin-offs of the cavity method of spin glasses [START_REF] Mézard | Spin glass theory and beyond[END_REF]. In the context of inference on dense graphical models the algorithms is called approximate message passing (AMP) known from the context of compressed sensing [START_REF] Donoho | [END_REF]. In the limit of large system size, the dynamical evolution of AMP can be tracked by the so-called state evolution (SE) [START_REF] Donoho | [END_REF]14], whose fixed point equations coincide with the saddle point equations describing the thermodynamic of the system under the replica symmetric assumption. The analysis of SE and its comparison to the analysis of the Bayes-optimal performance reveals that there is an interval of noise-to-signal ratio where the signal could be reconstructed by sampling the posterior measure, while AMP is not able to converge to the optimal error. This interval marks the presence of the hard phase.

In this paper we want to attract further attention of the physics community towards the existence of this hard phase related to a 1st order phase transition in the optimal performance in inference problems. The following open questions might use the physics-like approach and insights: Could there be a physics-inspired algorithm that is able to overcome the algorithmic barrier the AMP algorithm encounters? Note that in problems where the corresponding graphical model can be designed, such as compressed sensing or error correcting codes, such a strategy related to nucleation indeed exists [START_REF] Krzakala | [END_REF]15]. But what about the more ubiquitous problems where the graphical model is fixed? Are there some physical principles or laws that can provide further evidence towards the impenetrability of the algorithmic barrier?

The motivation of the present work was to challenge the conjecture about impenetrability of the hard phase for efficient algorithms. We analyze the following physicsmotivated strategy: It is known that the metastable part of the posterior measure in the hard phase is glassy [16,17]. Yet, the AMP algorithm fails to describe this glassiness properly. In some other contexts where message passing algorithms are successfully used, a correct account of glassiness leads to algorithm that improve over simpler ones. Notably this is the case of random constraint satisfaction problems, where the influential work [18] has shown that survey propagation, that takes correctly glassiness into account, beats the performance of belief propagation.

We pose therefore the problem whether, in inference tasks, the reconstruction of the signal becomes easier when one uses algorithms in which the glassiness is correctly taken into account. We investigate this strategy thoroughly in the present work. We confirm that the hard phase is glassy in the sense that it consists of an exponential number of local optima at higher free energy than the equilibrium one. However, when it comes to the reconstruction of the signal, our analysis leads us to the remarkable conclusion that, in contrast to constraint satisfaction and optimization problems, in inference problems taking into account the glassiness of the hard phase does not improve upon the performance of the simplest AMP algorithm. We thus provide an additional evidence towards the bold conjecture that in the corresponding inference problems AMP is the best of lowcomputational-complexity inference algorithms.

Our analysis of the glassiness of the hard phase provides new insights on the performance of Monte Carlo or Langevin dynamics. Presence of the glassiness suggests that these sampling-based algorithms are sloweddown and thus their commonly used versions may not be able to match the performance of AMP. While this aligns with some of the the early literature [16], more recent literature [6] suggested, based on numerical evidence, that Monte Carlo sampling is as good as the message passing algorithm. Based on conclusion of our work, this question of performance barriers of sampling-based algorithms should be re-opened and investigated more thoroughly. Good understanding of performance of these algorithms is especially important in the view of the fact that some of the most performing systems currently use stochastic gradient descent, that can be seen as a variant of the Langevin dynamics.

This paper is organized as follows. In Section II we introduce the model on which we illustrate the main findings of this paper, we expect this picture to be generic and apply to all the models where the hard phase related to a first order phase transition in the performance of the Bayesian inference was identified. In Section III we remind the basic setting of Bayesian inference. In Section IV we then remind the replica approach to the study of the corresponding posterior measure. Section IV A then summarized the known replica symmetric diagram and the resulting phase transitions. Section IV B then includes the main technical results of the paper where we quantitatively analyze the glassiness of the hard phase, giving rise to our conclusions in section V.

II. MODEL

In order to be concrete we concentrate on a prototypical example of an inference problem with a hard phasethe constrained rank-one matrix estimation. This problem is representative of the whole class of inference problems where the hard phase related to a 1st order phase transition was identified [7,[START_REF] Lesieur | Information Theory (ISIT), 2015 IEEE International Symposium on[END_REF][START_REF] Lesieur | [END_REF]. We choose this example because it is very close to the Sherrington-Kirkpatrick model for which the study of glassy states is the most advanced [START_REF] Mézard | Spin glass theory and beyond[END_REF]. Glassiness was also studied in detail in the spherical or Ising p-spin model, corresponding to spiked tensor estimation [START_REF] Richard | Advances in Neural Information Processing Systems[END_REF]. However, in that model the hard phase spans the full low-noise phase and the transition towards the easy phase, on which we aim focus here, happens for noise-to-signal-ratio too low to be straightforwardly investigated within the replica method.

In the rank-one matrix estimation problem the signal, denoted by x (0) ∈ R N , is extracted from some separable prior probability distribution given by P X (x (0) ) = N i=1 P (x (0) i ). This signal is subjected to noisy measurements of the following form

Y ij = 1 √ N x (0) i x (0) j + ξ ij , ∀ i ≤ j (1)
where ξ ij are Gaussian random variables with zero mean and variance ∆. Therefore one observes the signal through the matrix Y . The inference problem is to reconstruct the signal x (0) given the observation of the matrix Y . The informational-theoretically optimal performance in this problem was analyzed in detail in [START_REF] Lesieur | [END_REF] and this analysis was proven rigorously to be correct in [START_REF] Deshpande | Information Theory (ISIT), 2014 IEEE International Symposium on[END_REF][START_REF] Krzakala | Information Theory Workshop (ITW)[END_REF][START_REF] Barbier | Advances in Neural Information Processing Systems[END_REF][START_REF] Lelarge | [END_REF].

Refs. [START_REF] Lesieur | [END_REF][START_REF] Deshpande | Information Theory (ISIT), 2014 IEEE International Symposium on[END_REF][START_REF] Rangan | Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on[END_REF] also analyzed the performance of the AMP algorithm.

While the theoretical part of this paper is for a generic prior P X , the results section focuses on the Rademacher-Bernoulli prior

P X (x) = (1 -ρ) δ(x) + ρ 2 [δ(x -1) + δ(x + 1)] (2)
as this is a prototypical yet simple example in which the hard phase appears for sufficiently low ρ [START_REF] Lesieur | Information Theory (ISIT), 2015 IEEE International Symposium on[END_REF][START_REF] Lesieur | [END_REF]. Let us mention that the rank-one matrix estimation with the Rademacher-Bernoulli prior has a very natural interpretation in terms of community detection problem. Keeping this interpretation in mind can help the reader to get intuition about the problem. Nodes are of three types:

x (0) = 1 belong to one community, x (0) = -1 to a second community, and x (0) = 0 does not belong to any community. The observations Y ij (1) can be interpreted as weights on edges of a graph that are on average larger for nodes that are either both in community one or both in community two, they are on average smaller if one of the nodes is in community one and the other in community two, and they are independent and unbiased when one of the nodes does not belong to any community. Thanks to the output universality result of [START_REF] Krzakala | Information Theory Workshop (ITW)[END_REF][START_REF] Lesieur | Communication, Control, and Computing[END_REF] the result presented in this paper also hold for a model where the observations Y ij ∈ {0, 1} correspond to the adjacency matrix of an unweighted graph with Fisher information corresponding to the inverse of the variance ∆.

III. BAYESIAN INFERENCE AND APPROXIMATE MESSAGE PASSING

We study the the so-called Bayes optimal setting, which means that we know both the prior P X (x) and the variance ∆ of the noise. The probability distribution of x given Y is given by Bayes formula

P (x|Y ) ∝ P X (x)P (Y |x) . (3)
Since the noise ξ ij is Gaussian we have

P (Y |x) ∝ i≤j exp - 1 2∆ Y ij - x i x j √ N 2 ≡ i≤j G Y ij | x i x j √ N . (4)
Both in Eq. ( 3) and ( 4) we have omitted the normalization constants. An estimate of the components of the signal that minimize the mean-squared-error with the ground truth signal x (0) is computed as

xi = x i (5)
where the brackets stand for the average over the posterior measure Eq. ( 3). Therefore in order to solve the inference problem we need to compute the local magnetizations {x i }. The AMP algorithm is aiming to do precisely that, its derivation can be found e.g. in [START_REF] Lesieur | [END_REF]. AMP boils down to a set of recursion relations of the form

x(t+1) i = AMP i x(t) , x(t-1) i , (6)
whose iterative fixed point is taken as an estimate of the signal. In this work we do not investigate the properties of AMP algorithm but we focus on the statistical properties of the posterior measure that AMP is trying to describe, analyzing the free energy of the system within the replica method. It is known that the replica symmetric (RS) solution describes the fixed points of the state evolution for AMP in the thermodynamic limit. In fact, it is possible to derive a generalized AMP, that we call Approximate Survey Propagation (ASP) algorithm, whose state evolution fixed points coincide with the replica equations in the one-step replica symmetry breaking (1RSB) ansatz, which is known to provide a better description -in many case exact-of glassy states [START_REF] Antenucci | [END_REF]. In the next sections we hence study the thermodynamics of the above model in the RS and 1RSB ansatz, focusing on its properties in the hard phase.

IV. THE REPLICA APPROACH TO THE POSTERIOR MEASURE

In order to study the posterior measure, we define the corresponding free energy as

f [∆; Y ] = - 1 N ln N i=1 dx i P X (x i ) i≤j G Y ij x i x j √ N .
(7) This is a random object since it depends on the matrix Y . Furthermore it depends on ∆ through the function G. Indeed, we want to study the typical behavior of this sample-dependent free energy. Therefore we define

f(∆) = f [∆; Y ] ≡   i≤j dY ij   P (Y )f [∆; Y ] , (8)
where Y is obtained as in Eq. ( 1), so that P (Y ) is given by

P (Y ) ∝ dx (0) P X x (0) i≤j G Y ij x (0) i x (0) j √ N . (9)
In order to perform the average defined in Eq. ( 8) we use the replica method [START_REF] Mézard | Spin glass theory and beyond[END_REF]. Introducing

Z = N i=1 dx i P X (x i ) i≤j G Y ij x i x j √ N , (10)
we get

f(∆) = - 1 N lim n→0 ∂ n   i≤j dY ij   P (Y )Z n . ( 11
)
For integer n we can represent Z n as an n-dimensional integral over n replicas x (a) with a = 1, . . . , n. Stated in this way the problem is obviously symmetric under the exchange of the n replicas among themselves. Moreover since we need to integrate over the signal distribution P (Y ) we end up with a system of n + 1 replicas, that, in the Bayes optimal case, is symmetric under the permutation among all the n + 1 replicas. Performing standard manipulations, see e.g. [START_REF] Mézard | Spin glass theory and beyond[END_REF], we arrive at a closed expression for f(∆) that is

f(∆) = - 1 N ln DqDq exp [N S (q, q)] , (12)
where S is a function that can be computed explicitly and q and q are (n + 1) × (n + 1) overlap matrices. In the large N limit, the integral in Eq. ( 12) can be evaluated using the saddle point method. At the saddle point level the physical meaning of the overlap matrix q is given in terms of

q ab = 1 N N i=1 x (a) i x (b) i , (13)
while the matrix q is just a Lagrange multiplier. We denote m the magnetization of the system, meaning

m ≡ q 0a = q a0 = 1 N N i=1 x (0) i x (a) i a > 0 . (14)
The saddle point equations for q and q can be written in complete generality for any n but then one needs to take the analytic continuation down to n → 0. One needs an appropriate scheme from which one can take the replica limit. Here we consider two schemes: the replica symmetric (RS) and the 1-step replica symmetry breaking (1RSB) one. We refer here to symmetry under permutations of the n replicas with index a = 1, . . . , n.

A. Reminder of the replica symmetric solution

The RS scheme boils down to consider

q ab = (q d -q 0 ) δ ab + q 0 a, b ≥ 1 , qab = (q d -q0 ) δ ab + q0 a, b ≥ 1 , q 0a = q a0 = m a ≥ 1 , q0a = qa0 = m a ≥ 1 . (15)
From the point of view of the inference, the relevant quantity to look at is the Mean Square Error (MSE)

MSE = 1 N N i=1 x i -x (0) i 2 =ρ -2m + q 0 , (16)
where ρ ≡ x (0) 2 . Replica symmetry among all the n+1 replicas is obtained for m = q 0 . It is well known that, as a direct consequence of Bayes optimality (also called Nishimori condition [START_REF] Zdeborová | [END_REF]), this fully replica symmetric solution is the one that describes thermodynamically dominant states. The more general ansatz is, however, important as it allows to describes metastable states where the Nishimori identities might not hold. Plugging this ansatz inside the expression for S and taking the saddle point equations w.r.t. all these parameters one gets the replica symmetric solution as reported in [START_REF] Lesieur | [END_REF], and proven to give the equilibrium solution in [START_REF] Barbier | Advances in Neural Information Processing Systems[END_REF][START_REF] Lelarge | [END_REF]. The RS free energy can be expressed as

f RS (∆) = min m {φ RS (m, ∆)} (17)
with

φ RS (m, ∆) = m 2 4∆ -E x (0) ,W f m ∆ , m ∆ x (0) + m ∆ W (18)
where and x (0) and W are random variables distributed according P X x (0) and a standard normal distribution, respectively. The values of m for which φ RS is stationary are the solution of

f (A, B) = ln dx P X (x) e -1 2 Ax 2 +Bx , (19)
m = E x (0) ,W x (0) ∂f ∂B m ∆ , m ∆ x (0) + m ∆ W . (20)
Equilibrium properties of the inference problem are given by the global minima of the free energy Eq. (18). Local minima of the free energy that do not correspond to the equilibrium solution are called metastable.

For illustration, we consider the case of the Rademacher-Bernoulli prior (2) and we set ρ = 0.08 so that the inference problem has an hard phase [START_REF] Lesieur | [END_REF]. The replica symmetric phase diagram is represented in Fig. 1 (yellow curve).

At high ∆ the noise is so strong that the signal cannot be recovered and therefore m = 0. Upon decreasing ∆ the signal is relatively stronger w.r.t the noise and for ∆ = ∆ dyn ∼ 1.041ρ 2 the system undergoes a dynamical transition. On the one hand one can see that the free energy (18) develops a local metastable minimum with m > 0. On the other hand, the m = 0 state undergoes a clustering transition according to the pattern familiar in the physics of spin glasses [START_REF] Franz | [END_REF]29]. The corresponding RS free energy ceases to describe a paramagnetic state and it describes a non-ergodic phase with an exponential number exp(N Σ(∆)) of metastable states -aka clusters -with zero overlap among each other and identical energy and internal entropy. Both the zero m dominating branch and the metastable m > 0 branch have identical energy and internal entropy. Their free energy difference is the com-plexity f (m > 0) -f (m = 0) = Σ(∆). Moreover, as we will see in the next section, the typical overlap q 1 between configurations in these states coincides with the value of m of the magnetized solution. For that reason the magnetized state corresponds just to one cluster among the exponential multiplicity dominating the thermodynamics. The complexity (i.e. log of their number) of the thermodynamic states decreases with ∆, until it vanishes at a value ∆ = ∆ IT ∼ 1.0295ρ 2 where there is the information theoretic phase transition and Σ(∆ IT = 0). The signal is here strong enough so that a first order phase transition happens where the minimum with positive magnetization becomes the global minimum of the free energy. The complexity of the m = 0 solution becomes negative, the solution is non physical and consequently RSB is necessary to describe the metastable branch. Despite this fact, this RS metastable branch cannot be just dismissed as unphysical: it continues to be relevant algorithmically as dynamical attractor of the AMP algorithm. Decreasing the intensity of the noise further, another phase transition happens in this RS branch. At ∆ = ∆ c = ρ 2 the metastable minimum develops a small magnetization. Decreasing even further ∆, at ∆ = ∆ alg ∼ 0.9805ρ 2 this metastable minimum disappears with a spinodal transition. In the interval [∆ alg , ∆ IT ] one finds the hard phase defined by the property that the AMP algorithm is suboptimal (the shaded yellow region in Fig. 1): the global minimum of the free energy has a high m (low MSE), but the small m non-physical local minimum continues to describe the attractor of the AMP. The state evolution describing the AMP algorithm starting from random conditions converges to the local minimum of lowest magnetization.

B. Glassy phase and complexity

The low branch RS solution is non-physical below ∆ IT , its existence, however, suggests that metastable states exist that should be described with RSB. We therefore consider the 1RSB ansatz. We divide the n replicas a = 1, . . . , n into n/s blocks, where s is the so-called Parisi parameter [START_REF] Mézard | Spin glass theory and beyond[END_REF]. The overlap matrix becomes

q ab =      q d a = b q 1 a
, b in the same block q 0 a, b in different blocks [START_REF] Deshpande | Information Theory (ISIT), 2014 IEEE International Symposium on[END_REF] and analogous for q. For s strictly equal to one we get back the replica symmetric ansatz Eq. (15). Note that for s = 1, m and q 0 are in general different in the solution: this is crucial when evaluating the MSE Eq. ( 16) as the minimum of the MSE does not correspond in general to the maximum of m.

The 1RSB free energy takes the form

f 1RSB (∆, s) = extr φ 1RSB (m, q 0 , q 1 , ∆, s) , (22)
with

φ 1RSB (m, q 0 , q 1 , ∆, s) = m 2 2∆ -s q 2 0 4∆ -(1 -s) q 2 1 4∆ + - 1 s E x (0) ,W f q 1 ∆ , m ∆ x (0) + q 0 ∆ W, q 1 -q 0 ∆ , (23)
where

f (A, B, C) = ln dh C 2π e -1 2 Ch 2 • • dx P X (x) e -1 2 Ax 2 +(B+Ch)x s . ( 24
)
The stationary points of the 1RSB free energy are now obtained by the fixed points of

m = 1 s E x (0) ,W x (0) ∂f ∂B q 0 = 1 s 2 E x (0) ,W ∂f ∂B 2 q 1 = 2 s(s -1) E x (0) ,W ∂f ∂A + ∂f ∂C (25)
where A = q 1 /∆, B = mx (0) /∆ + W q 0 /∆ and C = (q 1 -q 0 )/∆ and the extremum is a minimum in m and a maximum in the other parameters. We would like to reiterate here the observation that in the same way that the stationary points of the RS free energy correspond to state evolution fixed points of the AMP algorithm, the stationary points of the 1RSB free energy correspond to the fixed points of the state evolution of an approximate survey propagation algorithm that depends on s [START_REF] Antenucci | [END_REF]. In particular, the expression (16) exactly gives the MSE of such algorithm with m and q 0 being the solution of [START_REF] Rangan | Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on[END_REF].

For high enough ∆ the 1RSB solution collapses to the RS one, meaning that q 0 = q 1 = m = 0. At ∆ dyn the saddle point equations for s = 1 admit a solution with m = q 0 = 0, q 1 > 0. The value of q 1 in this solution coincides with the value of m in the high magnetization RS branch discussed in the previous section. At ∆ IT the metastable states undergo an entropy crisis transition. Although the thermodynamically dominant state becomes the state with high correlation with the ground truth signal, glassy states continue to exist. In fact as far as these states are concerned -if we neglect the high magnetization state -the system undergoes there a Kauzmann transition where the dominant glassy states have zero complexity and a value of the Parisi parameter s is determined by the condition that complexity Σ(∆, s) (defined below) is equal to zero1 .

Let us now discuss s = 1 solutions. It is well known that the Parisi parameter s can be interpreted as an effective temperature that enables to select families of metastable states of given (internal) free energy [30]. Their corresponding complexity Σ (defined as the log of their number) is obtained by deriving (23) w.r.t s [30], and multiplying the result by s 2 , i.e.

Σ (∆, s) = s 2 4∆ q 2 1 -q 2 0 -s 2 ∂ ∂s E x (0) ,W 1 s f q 1 ∆ , m ∆ x (0) + q 0 ∆ W, q 1 -q 0 ∆ (26)
As expected this complexity for s = 1 coincides with the free energy difference between the two RS branches discussed in the previous section.

In Fig. 2 we plot the complexity as function of both s and of the noise variance ∆. For each value of s we find two regions: a physical region where Σ is positive, and an non-physical one where Σ < 0. Note as the physical region with positive complexity continues not only below ∆ IT , but even well below ∆ alg .

The 1RSB solution is not guaranteed to give the exact description of the glassy states. It is well known that in the replica solutions should be stable against (further) breaking of the replica symmetry. This requires that all the eigenvalues of the Hessian of the free energy should be positive in the solution. The 1RSB solutions can loose stability in two possible ways, associated, to negative values of the following eigenvalues [31][32][33]:

λ I = 1 - 1 ∆ ∞ -∞ dhP (s, h) (f ′′ (s, h)) 2 λ II = 1 - 1 ∆ ∞ -∞ dhP (1, h) (f ′′ (1, h)) 2 . (27)
where

(A = q 1 /∆, B = m ∆ x (0) + h and C = (q 1 -q 0 )/∆ ) f (1, h) = ln dxP (x) exp - A 2 x 2 + hx , f (s, h) = 1 s ln dz √ 2πC e -z 2 2C e sf (1,h-z) , (28)
P (s, h) =E x (0) ∆ 2πq 0 exp - ∆ 2q 0 B 2 , P (1, h) =e sf (1,h) dz e -z 2 2C √ 2πC • P (s, h -z) e -sf (s,h-z) . (29)
A negative λ I (type I instability) signals the appearance of new scales of distance between states. A negative λ II on the other hand is met for small ∆ and small s, where the glassy states are unstable against a Gardner transition to further RSB [31,32]. Each metastable state splits into a hierarchy of new states (type II instability) [33]. In Fig. 2 we mark with full lines the stable region, with dashed lines the unstable ones. Type I instability is found in the physical region at low value of s for sufficiently large ∆ and it has been found also in spin glass models [33][34][35]. Type II instability is found for large s in the non-physical region of negative complexity. Let's now discuss in detail the glassy solutions that one finds for ∆ < ∆ IT representing metastable states with higher free energy than the high-magnetization solution. These solutions have zero or low magnetization (overlap with the signal). As already remarked, for a given ∆, among all the glassy states the ones with lowest total free energy turn out to be the ones with zero complexity Σ. For different fixed values of the parame-ter s, the complexity curves reach zero value at different values of ∆. Remarkably, as illustrated in Fig. 2 a stable (towards higher levels of RSB) zero-complexity solution is found down to a value of noise ∆ 1RSB,equil < ∆ alg . Stable solutions of positive complexity exists down to ∆ 1RSB,stable < ∆ 1RSB,equil , and solutions with positive complexity (irrespective of the stability) down to ∆ 1RSB,all < ∆ 1RSB,stable . Example of specific values for ρ = 0.08 in Fig. 2 are ∆ alg ∼ 0.9805ρ 2 , ∆ 1RSB,equil ∼ 0.951ρ 2 , ∆ 1RSB,stable ∼ 0.918ρ 2 , ∆ 1RSB,all ∼ 0.903ρ 2 . This notably means that for ∆ < ∆ alg , namely in the easy phase where AMP converges close to the signal, families of metastable states continue to exist, some of them being stable with extensive complexity.

Σ [10 -3 ] s ∆ = ∆ dyn = 1.041ρ 2 ∆ = ∆ IT = 1.0295ρ 2 ∆ = 1.010ρ 2 ∆ = 0.982ρ 2 ∆ = 0.980ρ 2 ∆ = 0.978ρ 2 ∆ = 0.974ρ 2 ∆ = 0.970ρ 2 ∆ = 0.965ρ 2 ∆ = 0.950ρ 2 0 2 4 6 8 0.9ρ 2 0.95ρ 2 ∆ alg ∆ c =ρ 2 ∆ IT ∆ dyn 1.07ρ 2
One can discuss how do these states influence Monte-Carlo dynamics, that explore the space of configuration according to principles of physical dynamics. On the one hand, one could conjecture that Monte-Carlo dynamics gets trapped by glassy states even below ∆ alg . On the other hand, the dynamics is expected to fall out of equilibrium for all ∆ < ∆ dyn and it is not a priori clear in which states it should get trapped. While AMP clearly works for ∆ < ∆ alg and does not work for ∆ > ∆ alg , our analysis does not provide any reason why the threshold ∆ alg should be relevant for Monte Carlo or other sampling-based algorithms. For such physical dynamics, numerical simulations and analytic studies in suitable models are necessary to clarify the question of what is the corresponding algorithmic threshold.

So far we focused on glassy states of complexity (i.e. existing with probability one for typical instance). There are also solutions of the 1RSB equations having negative complexity. We will call the negativecomplexity solution the ghost-glassy states. From the physics point of view those solutions do not correspond to physical states for typical instances. Yet, from the algorithmic point of view they do correspond to the fixed points of the ASP algorithm [START_REF] Antenucci | [END_REF] run for a given value of Parisi parameter s, as such they can be reached algorithmically. At this point it becomes relevant to understand for which value ∆ alg (s) do the ghost-glassy state disappear, developing a spinodal instability towards the highmagnetization state. In particular we can ask the natural question if with a suitable choice of the Parisi parameter s the ASP improves over the algorithmic threshold ∆ alg ≡ ∆ alg (s = 1) of the usual AMP (s = 1) and if we could have an s for which ∆ alg (s) > ∆ alg [START_REF] Grassberger | NATO ASI series. Series C: mathematical and physical sciences[END_REF]. With this question in mind in Fig. 3 we plot the mean-squared error (MSE) with the ground truth signal given by Eq. ( 16) as a function of s for various values of ∆. We initialize the 1RSB fixed point equations at infinitesimal magnetization and iterate them till a fixed point. We observe that for all values of ∆ the MSE is minimized for s = 1, i.e. by the canonical AMP algorithm.

The fact that among all the values of s the lowest MSE is reached by the s = 1 states for all ∆ is unexpected from the physics point of view. It implies that the AMP that neglects glassiness and wrongly describes the region ∆ < ∆ IT works better as an inference algorithm than an algorithm that correctly describes the metastable states in this region. However, such a result could be anticipated based on mathematical theorem of [7] that implies that AMP is optimal among all local algorithms. This theorem applies as long as an iterative algorithm only uses information from nearest neighbours and (nearly) reaches a fixed point after O(1) iterations.

= ∆ c = ρ 2 ∆ = 0.987ρ 2 ∆ = 0.981ρ 2 ∆ = 0.980ρ 2 ∆ = 0.974ρ 2 ∆ = 0.965ρ 2 ∆ = 0.950ρ 2

V. CONCLUSION

In conclusion, we studied the glassy nature of the hard phase in inference problems. Our results imply that indeed the corresponding metastable state is glassy, i.e. composed of exponentially many states. We evaluate their number (complexity) as a function of their internal free energy to conclude that this glassiness extends to a range of the noise parameter ∆ even larger than the extent of the the hard phase. This finding re-opens the natural question of performance limits of Monte-Carlo based sampling. While some recent works [6] anticipated numerically that Monte-Carlo and message pass-ing will share the same algorithmic threshold, our results do not provide any evidence of this. Instead they suggest that since glassiness is present also below the algorithmic threshold of AMP the performance of samplingbased algorithms will be different in general. Concerning the AMP algorithm, we conclude that, despite the fact that it assumes the hard-phase not to be glassy, the improved description in terms of one-step replica symmetry breaking, that takes glassiness into account, does not provide algorithmic improvement. This is at variance with the situation in random constraint satisfaction problems, where the knowledge of the organization space of solutions provided by 1RSB leads to algorithmic improvement [36].

In this paper we use the example of low-rank matrix estimation with spins 0 and ±1 as a prototypical example in which the hard phase exists. We checked that the resulting picture applies in a range of parameters and also for some other models (such as planted mixed pspin model) where the hard phase was identified. We expect the picture presented here to be generic in all the problems where the hard phase related to a first order phase transition was identified.

Finally, we want to mention that the results shown here may be compelling also beyond inference problems. In particular, we notice that the instabilities of the RS solution at ∆ alg and ∆ c can be related to a similar phenomenon occurring in the mean field theory of liquids and glasses [37,38]. A phase structure similar to the one presented in this paper is found in that case, if we identify ∆ as analogue to an (inverse) density parameter and the reconstruction phase as the crystal. Also in that case, the RS solution representing the liquid at low density describes a non-ergodic extensive complexity phase at higher density. As it is the case here, there is a density where complexity vanishes, but the solution can be continued below this point. Finally, there is a maximum density where the solution undergoes an instability -called Kirkwood instability -and ceases to exist [39,40]. Our analysis suggests that within inference models not only the non-physical negative complexity RS solution could undergo this instability, but also the glassy ones. Whether this phenomenon could be relevant for other glassy systems is an intriguing question.

FIG. 2 :

 2 FIG. 2:The complexity of metastable states Σ as a function of the Parisi parameter s and the noise ∆, for prior[START_REF] Zdeborová | [END_REF] with sparsity ρ = 0.08. Upper panel, complexity at fixed s in the whole domain of existence of a non-trivial fixed point. Lower panel, the physical region of positive Σ as function of ∆. We draw the stable solutions with a solid line and the unstable, wrt the eigenvalues[START_REF] Antenucci | [END_REF], with a dashed line. For each value of ∆ ∈ [∆IT, ∆ dyn ] the value of Σ(∆, s = 1) represents the complexity of the family of thermodynamically dominating states. Below ∆IT the s = 1 solution in nonphysical and Σ(∆, s = 1) < 0. The algorithmic threshold of AMP occurs when the ghost-glassy states at s = 1 have a spinodal transition towards the signal.

FIG. 3 :

 3 FIG.3:The MSE as a function of the Parisi parameter s for different values of the noise strength ∆. The smallest MSE is always reached for s = 1, corresponding to the performance of the AMP algorithm, with a threshold at ∆ alg = 0.9805ρ 2 .

  The magnetization, aka the overlap, between the signal and the states described by the 1RSB solution at Parisi parameter s, as a function of the noise strength ∆, and sparsity ρ = 0.08. The curve that show a spinodal transition towards the strongly magnetized solution at largest values of ∆ is the one for s = 1. The same curve represents also the performance of the AMP algorithm. Taking the glassiness of the metastable branch into account does not improve upon AMP.

	0.6
		s=0.90
		s=0.95
	0.4	s=0.98
		s=1.02
	m	s=1.03
		s=1.05
	0.2	s=1.00
	0	0.85ρ 2	0.9ρ 2	0.95ρ 2 ∆ alg ∆ c =ρ 2 ∆ IT ∆ dyn
			∆
	FIG. 1:

Notice the analogy of the high-magnetization state here with the crystal state in the physics of glasses.

Acknowledgments

We would like to thank Giulio Biroli, Florent Krzakala, and Guilhem Semerjian for fruitful discussions. This work is supported by "Investissements d'Avenir" LabEx PALM (ANR-10-LABX-0039-PALM) (SaMURai and StatPhysDisSys projects), and from the ERC under the European Unions Horizon 2020 Research and Innovation Programme Grant Agreement 714608-SMiLe. The work of SF was supported by a grant from the Simons Foundation (No. 454941, Silvio Franz).