Nigar Jebraeil

Adel Noureddine
email: a.noureddine@uel.ac.uk

Joseph Doyle
email: j.doyle@uel.ac.uk

Syed Islam
email: syed.islam@uel.ac.uk

Rabih Bashroush
email: r.bashroush@qub.ac.uk

gUML: Reasoning about Energy at Design Time by Extending UML Deployment Diagrams with Data Centre Contextual Information

With the rising energy demand in ICT services and its associated environmental impact, the need for energy efficient Enterprise ICT solutions is growing. As data centres account for a large part of energy consumption in ICT, data centre operators strive to create opportunities to put more emphasis on reducing energy consumption. However, creating ICT Systems that are energy efficient by design remains a key challenge. In this paper, we identify and map contextual energy information about data centre operations in order to model their power related components. This contextual modelling is then mapped to deployment diagram where we introduce greenUML (gUML), an extension to UML diagrams to improve energy efficiency through energy analysis at design time. gUML will allow system architects to reason about the energy footprint of their applications at design time.

I. INTRODUCTION & MOTIVATION

Tackling climate change and achieving low carbon emission have been an international priority over the past three decades. According to The Centre for Energy-Efficient Telecommunications (CEET), the energy consumption of ICT could exceed the global power supply by 10-15% [START_REF]Centre for energy-efficient telecommunications: Annual report 2013[END_REF]. Additionally, the ICT industry, which delivers the Internet, voice, video and other cloud services, creates more than 830 million tons of carbon dioxide (CO2) on a yearly basis, which counts for about 2 percent of global CO2 emissions [START_REF] Gartner | Gartner estimates ict industry accounts for 2 percent of global co2 emissions[END_REF]. This exceeds the emissions of the entire aviation industry [START_REF] Herzog | World greenhouse gas emissions in 2005 -world resources institute[END_REF]. Yet, this number is expected to double by 2020. This trend is clearly not sustainable. For instance, Japan is expected to spend all its energy capacity to support its ICT energy needs by 2030 if the current trend continues [START_REF] Plan | An inefficient truth[END_REF].

There has been considerable research to try and tackle this problem [START_REF] Liu | Renewable and cooling aware workload management for sustainable data centers[END_REF], [START_REF] Heller | Elastictree: Saving energy in data center networks[END_REF], [START_REF] Mahadevan | Energy proportionality of an enterprise network[END_REF]. To the author's knowledge, however, a comprehensive view of the energy consumption of software in the design and execution lifecycles has not been proposed. While improvements to power management and load balancing solution can reduce the energy consumption of data centres, these improvements are severely limited unless this information can be communicated to software engineers so that appropriate designs and deployments can be created.

In this paper, we present our approach to bring energy related contextual information to design time. In the example of data centres, we identify the main energy consuming components, classify and organise them in an architectural view, then map these contextual information to UML deployment diagram. This mapping helps developers write energy efficient software by reasoning about energy and identifying energy concerns when designing their applications. This paper makes the following contributions:

• The modelling of contextual information related to power components in data centres. • The extension of UML models with green contextual information in new extension called gUML. • The evaluation of how gUML can be used to reduce energy consumption and carbon emissions when designing workload deployment. Our evaluation shows that energy consumption can be reduced by 21% and carbon emissions can be reduced by 92% over the traditional deployment strategy. The paper is structured as follows. Section 2 discusses the related literature. In section 3, we discuss the conceptual mapping of the main layers of a data centre. Section 4 presents the extended UML deployment diagram. Section 5 provides an evaluation using an example workload. Finally, section 6 concludes the paper.

II. RELATED WORK

Other works have been proposed to assist developers at designing energy-aware software. In [START_REF] Manotas | Seeds: A software engineer's energy-optimization decision support framework[END_REF], a software framework is proposed to transform applications based on developers' input and the energy profile of these applications. However, this approach requires manual input and studying multiple variations of the application in order to achieve efficiency transformations. Kwon et al. [START_REF] Kwon | The impact of distributed programming abstractions on application energy consumption[END_REF] presented guidelines to help developers select distributed programming abstractions to satisfy energy constraints. Kumar et al [START_REF] Kumar | Green supplier selection: a new genetic/immune strategy with industrial application[END_REF] use Data Envelopment Analysis to solve environmental decisions making problems. In [START_REF] Bi | Sla-based optimisation of virtualised resource for multi-tier web applications in cloud data centres[END_REF], an HPC based cloud model is proposed to tackle energy optimisation at runtime. Bi et al. [START_REF] Petri | A hpc based cloud model for real-time energy optimisation[END_REF] presented an SLA-based approach to optimise resources in a virtualised environment in data centres. Cohen et al. [START_REF] Cohen | Energy types[END_REF] proposed a programming model in a type-based approach to help developers reason and promote energy efficient software. Their approach enables developers to specify phases and modes. The former represents program workloads while the latter represent required energy states. Finally, in [START_REF] Singh | Impact of developer choices on energy consumption of software on servers[END_REF], the authors show how software developers can achieve energy savings by choosing energy efficient APIs along with optimal parameters in a number of use cases. These approaches provide indications and preliminary steps into energy-aware software design. We aim to propose a comprehensive view of the energy consumption of software throughout their implementation, deployment and execution life-cycles. By proposing energy-aware contextual information modelling and an extension to the UML deployment diagram, software developers can better reason about software energy efficiency at design time and consider energy consumption at individual component and interaction level.

III. CONTEXTUAL INFORMATION MODELLING

In our work, we present a deployment UML diagram, called gUML, as an extension to UML deployment diagram. We add relevant contextual information to produce an energy model. The research process we have chosen in the design of gUML is the design science research process [START_REF] Peffers | The design science research process: A model for producing and presenting information systems research[END_REF]. Accordingly we need to follow the model described in [START_REF] Peffers | The design science research process: A model for producing and presenting information systems research[END_REF] namely: With this methodology defined the next step is to identify and capture the relevant data. Our first step is to produce a general map of power flow throughout data centres. In this section, we identify and classify the relevant information needed for our gUML model in the areas of power, cooling, and network components. A traditional UML diagram can model a variety of system characteristics such as activities, components, interactions and user interfaces to show the structure, behaviour or interactions that exist in a system. Our proposal augments this by placing energy information on the links between the nodes of the UML diagrams so that the energy consumption of design decisions can be easily visualised.

To ensure that the energy information associated with design decisions in gUML is accurate it is essential to identify the most power hungry components of a data centre. Figure 1 illustrates a popular example journey of power flow amongst all levels of a data centre from its entrance point all the way through to its servers. A further breakdown of the most power-consuming components of the data centre as well as the ratio of the power component power consumption to its performance and its dependency to other components are illustrated in Figures 2,3,4 showing the power, cooling and networking component layers respectively. In the next sections we will discuss each of these layers in relation to gUML.

A. Identifying the Power Components of Data Centres

The distributed power is consumed unevenly amongst the six main power component branches that are known as the main streams of power consumption in data centres. Servers and conventional hardware devices currently benefit from energy efficiency solutions such as Dynamic Component Deactivation. These techniques were initially introduced to improve energy consumption in mobile devices. However, servers are rarely in idle mode. They have an average utilisation rate of 10% to 50%. This results in a considerably poor performance in terms of energy efficiency [START_REF] Barroso | The case for energy-proportional computing[END_REF]. Therefore, in order to harness power at hardware level, methods such as Dynamic Power Management (DPM) techniques are applied. These techniques include Dynamic Component Deactivation (DCD) and Dynamic Performance Scaling (DPS). DCD techniques are created based on the idea of an idle mode at the stage of inactivity. In addition, computer components that can dynamically adjust their performance in regards to power consumption can apply different techniques of DPS. Some components, such as the CPU, can adjust clock frequency rather than shutting down completely. This technique lead to the proposal of Dynamic Voltage and Frequency Scaling (DVFS), a technique widely used and supported by modern processors and operating systems [START_REF] Beloglazov | A taxonomy and survey of energy-efficient data centers and cloud computing systems[END_REF], [START_REF] Lee | Minimizing energy consumption for precedence-constrained applications using dynamic voltage scaling[END_REF], [START_REF] Benini | A survey of design techniques for system-level dynamic power management[END_REF]. Thus, to accurately model the energy consumption of a system in gUML, information on the utilisation of power saving techniques in a data centre must be gathered and incorporated into the model so that design decisions accurately reflect the performance of the system.

B. Identifying the Cooling Components Power Consumption

Cooling management is traditionally considered the largest energy overhead in data centres due to the vast amount of heat produced by IT equipment. The power consumed to cool a data centre is between 30% and 50% of the total power consumption. This number has the potential to increase depending on the IT performance management and geographical situation. Therefore, applied cooling could limit the capacity of the data centre. Despite their remarkable capacity management capabilities, high density computing and workload consolidation are amongst the two most power hungry techniques applied to IT, which immensely affect the level of required cooling capacity [START_REF] Jeonghwan | Profiling, prediction, and capping of power consumption in consolidated environments[END_REF], [START_REF] Liu | Renewable and cooling aware workload management for sustainable data centers[END_REF]. According to American Society of Heating, Refrigerator and Air-Conditioning Engineers' guideline [START_REF] Society | Standards and guidelines[END_REF], there is a broad range of standards introduced for optimal temperature and humidity in data centres. The cooling cost will rise against the cold air supplement. The cooler the data centre environment, the more power will be consumed, hence all best practices and cooling strategies propose to increase and maintain the operating temperature to its highest permissible value and reduce power assigned to cooling, humidity and heat removal in order to achieve an improved PUE [START_REF] Liu | Renewable and cooling aware workload management for sustainable data centers[END_REF], [START_REF] Wang | Adaptive performance control of computing systems via distributed cooperative control: Application to power management in computing clusters[END_REF]. Figure 3 illustrates the model aimed to identify the cooling components that distress power consumption of data centres. Additionally, data centres employ techniques such as aisle containment [START_REF] Pervilä | Cold air containment[END_REF] and the use of air-side economisers known as"free air cooling" [START_REF] Barroso | The datacenter as a computer: An introduction to the design of warehouse-scale machines[END_REF] to reduce the energy consumption of the data centre. All of these factor are integrated into the gUML to accurately predict the energy consumption of the system in different design configurations. It should be noted that the heat load distribution, ACU flow and the general cooling behaviour of data centre that can be calculated by applying a typical Computational Fluid Dynamics (CFD) analysis [START_REF] Ge | Powerpack: Energy profiling and analysis of high-performance systems and applications[END_REF], [START_REF] Gruter | Eod designer: A computation tool for energy optimization of data centers[END_REF] and the results of the CFD simulation can be integrated into the gUML model.

C. Identifying the Network Components of Data Centre

While the power consumed by networking equipment is typically less than power required to cool a data centre, it is still significant. A Data Centre Network may consist of thousands of servers on site. These servers are connected in a wide variety of topologies but fat-tree networks are becoming increasingly popular. In a fat tree network the topology is built from a combination of identical switching elements, so relying on aggregation to higher-speed; more expensive switching elements is not unnecessary [START_REF] Heller | Elastictree: Saving energy in data center networks[END_REF]. Nevertheless, the key feature to supply the requirements of huge bandwidth capacity and highspeed communications for Data Centre Network is to design an efficient interconnecting architecture [START_REF] Dzmitry | Dens: data center energy-efficient network-aware scheduling[END_REF], [START_REF] Patel | Nfra: Generalized network flow based resource allocation for hosting centers[END_REF]. The particular network architecture used by the data centre is integrated into the gUML model so that the energy consumption of networking components can be accurately predicted by system architects.

D. Mapping Power to Workflow

The final factor that is considered in the gUML model is how the workflow is processed. This will greatly affect the energy consumption and as suggested by [START_REF] Shorin | Evaluation of embedded system energy usage with extended uml models[END_REF], modelling and design ought to be based on the substitution between energy consumption and other requirements. We present in Figure 5 an example of a system whose energy consumption is modelled under the gUML proposal. Each energy consuming component is linked to associated energy consuming components. For example, energy consumed by a server should be linked to a UPS component and a cooling component as power for the server must pass through the UPS before it can reach a server and cold air from the cooling component will be required to keep the server at a sufficiently low temperature. Thus, energy cannot be consumed at the server without power being supplied to these components and this must be reflected in the gUML model. This mapping could be then utilised to allocate the workflow towards its most efficient route. This model makes the contextual information available at the design level by extending the UML deployment diagram. This will allow software architects to better reason about the energy implications of their design reasoning by showing them where and how their software should be deployed. Based on our modelling and identification of energy-related contextual information in data centres, we extend the traditional UML deployment diagram. The result is our extension, gUML. It builds on energy contextual information to help guide software developers in designing energy-aware applications. The next section describes our gUML extension.

IV. GUML EXTENDED DEPLOYMENT DIAGRAM

This section presents the design of an extension to the Unified Modelling Language (UML), called gUML. It proposes a view of a holistic approach and is designed to address the workload power consumption in the most efficient way. This will enable data centres to efficiently reduce the amount of energy consumption without having to threaten SLAs or the performance of the entire system. gUML collects the data of each workload's CPU consumption, cooling consumption, and bandwidth consumption. Creating an energy efficient map for the workload to flow within the complex numerous systems requires accurate addressing amongst different levels and stages of workflow, as well as real-time communications that link these layers.

In order to draw an energy-aware UML Diagram, it is necessary to identify the key target parameters of this model. In this case, the model is designed with the target revolving around efficiency, high performance, maintenance, and scalability. To apply all above criteria, a UML deployment diagram is chosen which can best serve the purpose for this model. UML is specifically chosen for its customisation abilities that allow us to deploy the existing modelling tools in order to define our domain, while it is convenient for the end users to leverage the extension.

A. UML Deployment Diagrams

A typical UML deployment diagram models the actual deployment of software components into hardware nodes. It illustrates the configuration of the hardware components (nodes) as well as how software components and artifacts are mapped onto those nodes. Currently, these deployment models lack energy-related information. This is problematic in data centre environments where multiple factors and components have various effects on energy consumption (see Section III).

For instance, efficiently deploying an application to multiple nodes can be achieved by understanding in which server each virtual machine is installed, what rank are the servers installed, what UPS system is used for each server rack, and what cooling techniques or power transformation units are used for these servers and racks. Deploying two components of an application on two virtual machine may lead to varying energy footprint if these two VMs were installed in separate racks, data centres or cooled using different systems.

In our approach, we extend the diagrams with contextual information about the energy consuming hardware (e.g., power generation, cooling, servers, etc.) in data centres. With this information available at design time, software developers can design the different components of their applications with knowledge about energy beyond computational power.

Figure 6(a) illustrates a typical UML component diagram for a simple order system which consults customer, product and account systems to process orders. Figure 6(b) illustrates the gUML counterpart of this diagram. Each component is labelled with a tuple which indicates the energy consumption of the component in the server power, UPS and cooling layers of the data center 1 and each connection is labelled with the energy consumption necesscary to communicate with different components. This will mainly relate to network energy consumption. These figures will be entered by hardware systems architects and will help visualise energy aware software design through greater collaboration between software and hardware architects.

B. Validation

In order to illustrate how gUML can be used to redesign workload placement in an enterprise information system we present a worst case example of a High Performance Computing workload placement and a best case example which can be designed with the aid of the gUML diagram. We assume that the workload is a daxpy or LINPACK like workload which are representative of power hungry HPC workloads [START_REF] Verma | Power-aware dynamic placement of hpc applications[END_REF]. We assume that the total number of FLOPs required to complete the workload is 1TFLOP. We also assume that each virtual machine has a throughput of 250MFLOP/s. We assume that each physical machine can host 4 virtual machines and that each virtual machine processing the workload causes an increase of 10W to the idle power of the physical server whose 1 This can be extended to incorporate additional energy consumption layers as necesscary. idle power is 140W. We assume that the desired completion time of the workload is 5 minutes meaning that 14 virtual machines are required to complete this workload in the desired time. This workload data is based upon the experimentation of Verma et al. [START_REF] Verma | Power-aware dynamic placement of hpc applications[END_REF]. The workload can be sent to two data centres. One located in Sweeden which uses free air cooling and has a carbon intensity of 32g/kWhr. The other is in Germany which uses cold aisle containment cooling and has a carbon intensity of 570g/kWhr [START_REF]Carbon Monitoring for Action[END_REF]. The network topology of both data centres is a two tier fat tree network [START_REF] Al-Fares | A scalable, commodity data center network architecture[END_REF]. We assume that the supply temperature of the cooling system in Germany is 20

10W 1 0 W 1 0 W 10W 1 0 W 1 0 W 1 0 W 1 0 W 10W 1 0 W 1 0 W 10W 1 0 W 1 0 W 1. 75 W 1.7 5W 1.75W 1.7 5W 1 0 W 1 0 W 22 .5 W 2 2 .5 W 4W 4W 3 W 3 W
Fig. 8. Diagram of power consumption in worst case scenario when the virtual machines are distributed among the physical servers at different physical locations. This could easily occur if a traditional global load balancing system such as the least connection method is used. This scenario is depicted in Figure 8. The cooling cost of the data centers is calculated using the following formula:

C = Q COP (T sup ) + P f an
Where Q is the amount of power the servers consume, T sup the temperature of the air that the CRAC units supply, P f an the power required by the fans of the CRAC units and COP is the coefficient of performance (COP), that is the ratio of heat removed to work necessary to remove the heat, is a function of the temperature of the air being supplied by the CRAC unit. The COP of a typical chilled-water CRAC unit used in the calculations of cooling costs is depicted in Figure 7.

In the case of the Swedish data centre free air cooling is used and the only power requirement is for the fans. The network power consumption is calculated by assuming that the physical machines utilise 1Gbps ethernet ports to connect, calculating the number of ports required to communicate with the other physical machines2 and assuming that the power value required to open a port is 0.7W. This is the midrange value from those presented in [START_REF] Mahadevan | Energy proportionality of an enterprise network[END_REF]. The UPS power consumption is assumed to be 10% of the dynamic power supplied to the physical machines which is typical of power losses during normal operation [START_REF] Kontorinis | Managing distributed ups energy for effective power capping in data centers[END_REF]. We could also consider other components such as transformers which operate at the highest efficiency when the load is in the 50-75% range and whose naive use can result power losses in the 60-80% range [START_REF] Beloglazov | A taxonomy and survey of energy-efficient data centers and cloud computing systems[END_REF] but this is left for future work. The energy consumption of the software components implementing the HPC workload would be illustrated in a gUML diagram similar to Figure 6(b). By seperating each of the energy components into tuples it is easy for the software engineer to identify potential power hungry components in the hardware which supports the software deployment. The deployment can then be redesigned in consultation with the data center architect to create a more energy efficient mapping between software and hardware components. Thus, the software engineer of the workload in collaboration with the data center architect would be able to redesign the load balancer to achieve the best case scenario which is depicted in Figure 9. In the best case scenario, the virtual machines are consolidated onto physical machines in the Swedish data centre where the cooling power consumption is lower due to the use of free air cooling. In addition, the networking power consumption is lowered as less networking link are required and thus, ports can be switched off. A comparison of the power consumption and environmental impact of the two scenario are depicted in Table I.

10W 1 0 W 1 0 W 1 0 W 1 0 W 1 0 W 1 0 W 1 0 W 1. 05 W 1.0 5W 1 0 W 1 0 W 7W 7W 10 W 1 0 W 1 0 W 10 W 1 0 W 1 0 W 1 . 0
From Table I we can see that the cooling energy consumption can be reduced by 69% through an increased use of free air cooling and shutting down fans which are not required. We can also see that networking energy consumption can be reduced by 38% by reducing the number of networking ports required for communication between the servers and by shutting down networking ports which are not required. This leads to an overall reduction of energy consumption of 21%. Finally, we can see that by reducing the overall energy consumption and directing all of the workload to the data centre with the lower carbon intensity we can reduce carbon emissions by 92%, illustrating the effectiveness of gUML.

V. CONCLUSION

In this paper, we identify and model various sources of power consumption in data centres in order to collect contextual information for each of these components. These sources are then mapped and contextualised in order to implement our extension for the UML deployment diagram called gUML. Our approach creates an advancement in tackling software energy efficiency in data centres at the design time by giving developers the tools to reason and design their application with contextual energy information for data centres deployment and execution.

However, the scope of profiles discussed in this paper are limited to the power components of data centres. We aim to extend our approach to tackle additional profiles, such as modeling the power components in mobile devices. In addition, tracing cooling components to server points depends on thermodynamics, which can be difficult to compute. Finally, we plan to add software defined data centres features, such as security or monitoring, to our approach.

Fig. 4 .

 4 Fig. 4. Power consuming network components of a data centre

Fig. 5 .

 5 Fig. 5. The map of end to end workload flow

Fig. 6 .

 6 Fig. 6. A typical UML component diagram and its gUML counterpart.

Fig. 7 .

 7 Fig. 7. Typical COP of water chilled computer room air conditioner.

Fig. 9 .

 9 Fig. 9. Diagram of power consumption in best case scenario

  • C. All of the virtual machines communicate with each other to execute the workload.For this particular workload the worst case scenario occurs

		Location 1				Location 2
				Core Layer
	Cooling 3	Cooling 4	UPS 3	UPS 4	Cooling 1	Cooling 2	UPS 1	UPS 2
	Rack 1	Rack 2		Rack 3	Rack 4
				Aggregation Layer
	Server 1	Server 2	Server 3	Server 4	Server 5	Server 6	Server 7
		VM 4		VM 1 VM 6		VM 9		VM 12
	VM 1	VM 3		VM 7		VM 10		VM 13
		VM 2	VM 5	VM 8	VM 11	VM 14
				Process Layer

TABLE I ENERGY

 I CONSUMPTION AND CARBON EMISSIONS FOR TWO SCENARIOS WITH PERCENTAGE REDUCTION OF BEST CASE SCENARIO OVER WORST CASE

				SCENARIO
	Scenario	Virtual	Cooling Energy	Networking	UPS	Energy	Total	Energy	Total Carbon
		Machine	(kJ)	Energy (kJ)	(kJ)		(kJ)		Emissions (g)
		Energy (kJ)
	Worst Case	42	19.5	2.1	4.2		67.8		20.6
	Best Case	42	6	1.3	4.2		53.5		1.7
	Percentage Reduction	0%	69%	38%	0%		21%		92%

In some cases the ports are shared by the physical machines and the power consumption is split between them.


Adrien Barbaresi
email: barbaresi@bbaw.de

Katrin Hein
email: hein@ids-mannheim.de

Data-Driven Identification of German Phrasal Compounds

Keywords: corpus linguistics, word segmentation, morphological analysis, web corpora

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Composition, that is "the combination of two or more lexemes (roots, stems or freely occuring words) in the formation of a new, complex word", is a productive process of German word formation [27, p. 364]. German is indeed considered as a language which makes extensive use of compounds [START_REF] Schlücker | Die deutsche Kompositionsfreudigkeit. Übersicht und Einführung[END_REF], for example Biowahn, Freigeist, or zitronengelb. Compounding does not always operate by a simple string concatenation, it can involve linking elements (e.g. the ens in Schmerzensschrei) as well as the elision of word-final characters in the non-head constituent of a compound [START_REF] Henrich | Determining Immediate Constituents of Compounds in Ger-maNet[END_REF]. In the nonhead position of such determinative compounds, not only lexical categories, but also syntactic units can be inserted -a phenomenon called phrasal compounding.

This paper discusses the automatic detection of german phrasal compounds (PCs) like "Man-muss-doch-über-alles-reden-können"-Credo or Habdichliebpolitik 4 in web corpora. PCs display a specific type of determinative compounds and can be defined as "complex words with phrases in modifier position" [24, p. 153]; their study is worthwhile in theoretical terms alone and sheds light on the general process of composition [START_REF] Hein | Modeling the properties of German phrasal compounds within a usage-based constructional approach[END_REF][START_REF] Hein | Phrasenkomposita im Deutschen. Empirische Untersuchung und konstruktionsgrammatische Modellierung[END_REF][START_REF] Lawrenz | Moderne deutsche Wortbildung. Phrasale Wortbildung im Deutschen: Linguistische Untersuchung und sprachdidaktische Behandlung[END_REF][START_REF] Meibauer | How marginal are phrasal compounds? Generalized insertion, expressivity, and I/Q-interaction[END_REF][START_REF] Meibauer | Phrasenkomposita zwischen Wortsyntax und Lexikon[END_REF][START_REF] Trips | The relevance of phrasal compounds for the architecture of grammar[END_REF]. Phrasal compounding is not restricted to German, but can be found in other languages as well [START_REF]Phrasal compounds from a typological and theoretical perspective. Special issue of STUF. Language typology and universals[END_REF], for example English: "cut-and-run meal" [START_REF] Trips | The relevance of phrasal compounds for the architecture of grammar[END_REF].

While [START_REF] Hein | Phrasenkomposita im Deutschen. Empirische Untersuchung und konstruktionsgrammatische Modellierung[END_REF] (cf. also [START_REF] Particke | Phrasenkomposita: eine morphosyntaktische Beschreibung und Korpusstudie am Beispiel des Deutschen[END_REF]) presented the first elaborated, large corpus-based investigation of German PCs whose immediate constituents are separated by hyphens (e.g. Second-Hand-Liebe, cf. [15, p. 349-353] for orthographic variants), until now no systematic study has ever put into focus PCs which are written as one word, i.e. without hyphens or blanks between their component parts (e.g. Heileweltsache). We want to outline the methodological challenges of their automatic detection in this paper, however the investigation of this PC variant in itself can also be seen as a desideratum.

The absence of linguistical or computational approximations to PCs can notably be explained by the lack of attested data. Within the inventory of nominal compounds, PCs account for an amount of 3.2% [START_REF] Ortner | Substantivkomposita. Deutsche Wortbildung: Typen und Tendenzen in der Gegenwartssprache[END_REF]. As it is assumed that PCs written as one word are even less prominent [START_REF] Hein | Phrasenkomposita im Deutschen. Empirische Untersuchung und konstruktionsgrammatische Modellierung[END_REF], possible hits are to be found at the lower end of the frequency spectrum. Thus, the annotated samples which we put together and use can themselves be considered as a precious and unprecedented source of linguistic evidence.

The automatic detection is indeed particularly challenging, especially the distinction between complex prototypical determinative compounds and PCs which are written in one word, or the distinction between PCs and types of phrasal derivations like Wasserin-Wein-Verwandler [START_REF] Lawrenz | Moderne deutsche Wortbildung. Phrasale Wortbildung im Deutschen: Linguistische Untersuchung und sprachdidaktische Behandlung[END_REF]. It implies to have an operational notion of compounds which can be systematically applied as well as corpora which are large and diverse enough to contain rarely seen phenomena. Web corpora built for linguistic research relying on scientific criteria [START_REF] Barbaresi | Ad hoc and general-purpose corpus construction from web sources[END_REF] seem particularly suitable for this endeavor, as they may comprehend a significant amount of texts from a large gamut of sources.

Method

The detection method grounds on a morphological compound analysis operating on token level. Since German is considered to be a morphologically rich language, stateof-the-art approaches do not always perform well on words absent from the dictionary, which is typically the case for phrasal compounds. Thus, in order to get information on potential segmentation patterns, we use the morphological analyzer SMOR [START_REF] Schmid | SMOR: A German Computational Morphology Covering Derivation, Composition and Inflection[END_REF] in combination with a data-driven morphological segmentation based on affix and component trees. This combination follows from two different goals: to design a robust detection process and to be able to estimate the degree of lexicalization of complex compounds.

Previous work

The combination is deemed to be necessary as SMOR can be subject to coverage issues. In previous work on non-standard text in an under-resourced variety of written German, namely retro-digitized newspaper texts from former East Germany, we showed that a data-driven method could overcome data sparsity and trump SMOR's full-fledged morphological analysis to predict whether a given token is to be considered as part of the language or as an OCR error [START_REF] Barbaresi | Bootstrapped OCR error detection for a less-resourced language variant[END_REF].

A similar approach has also been used to build an unsupervised morphological model for a number of different languages and language varieties for the Discriminating between Similar Languages shared task [START_REF] Malmasi | Discriminating between Similar Languages and Arabic Dialect Identification: A Report on the Third DSL Shared Task[END_REF][START_REF] Barbaresi | An Unsupervised Morphological Criterion for Discriminating Similar Languages[END_REF]. Criteria resulting from the segmentation analysis are statistically relevant and can be used as a sparse feature in a model to discriminate similar languages. A reasonable hypothesis is that they add new linguistically motivated information, dealing with the morpho-lexical logic of the languages to be classified while also yielding insights on linguistic typology.

Data-driven segmentation process

The method is based on segmentation and affix analysis. The original idea behind this simple yet efficient principle appears to go back to Harris' letter successor variety which grounds on transitional probabilities to detect morpheme boundaries [START_REF] Harris | From Phoneme to Morphemes[END_REF]. The principle has proven valuable to construct stem dictionaries for document classification [START_REF] Hafer | Word Segmentation by Letter Successor Varieties[END_REF], it has been used in the past by spell-checkers [START_REF] Peterson | Computer programs for detecting and correcting spelling errors[END_REF][START_REF] Jones | A spelling checker based on affix classes[END_REF], as it is both linguistically relevant and computationally efficient. Relevant information is stored in a trie [START_REF] Fredkin | Trie Memory[END_REF], a data structure allowing for prefix search and its reverse opposite in order to look for sublexicons, which greatly extends lexical coverage. Forward (prefix) and backward (suffix) tries are used in a similar fashion, albeit with different constraints. This approach does not necessarily perform evenly across languages; it has for example led to considerable progress in morphologically-rich languages such as Arabic [START_REF] Hamadou | A compression technique for Arabic dictionaries: the affix analysis[END_REF] or Basque [START_REF] Agirre | XUXEN: A spelling checker/corrector for Basque based on two-level morphology[END_REF]. Similar approaches have been used successfully to segment words into morphemes in an unsupervised way and for several languages. A more recent implementation has been the RePortS algorithm which gained attention in the context of the PASCAL challenge [START_REF] Keshava | A simpler, intuitive approach to morpheme induction[END_REF][START_REF] Dasgupta | High-performance, language-independent morphological segmentation[END_REF][START_REF] Demberg | A language-independent Unsupervised Model for Morphological Segmentation[END_REF] by outperforming most of the other systems. The present approach makes similar assumptions as the work cited and adapts the base algorithm to the task at hand. In this regard, this experiment also tests if the data-driven morphological analysis of surface forms can be useful in the context of phrasal compounds.

Implementation

In order to build the corresponding model, a dictionary is composed by observing unigrams in the training data, then prefix and suffix trees are constructed using this dictionary. Additionally, an affix candidate list is constituted by decomposing the tokens present in the training data. The identification algorithm aims at the decomposition into possibly known parts. It consists of two main phases: first a prefix/suffix search over respective trees in order to look for the longest possible known subwords, and secondly sanity checks including a series of known composition rules to see if the rest could itself be an affix or a word out of the dictionary. If αβ is a concatenation absent from the dictionary and if α and β are both in training data, then αβ is considered to be a valid token. The segmentation can be repeated if necessary, in order to identify all necessary components of long words. It is only performed backward here since the nominal basis is a discriminative criterion in this study.

Once the word has been decomposed into potentially meaningful parts, the morphological analysis tool SMOR [START_REF] Schmid | SMOR: A German Computational Morphology Covering Derivation, Composition and Inflection[END_REF] is used to determine the grammatical category of the identified root, i.e. the last matched subword on the right. If it is considered to be a valid noun, the rest of the subwords is analyzed in the same way. Adjectival and adverbial combinations on a noun base are used as a cue that the token is a phrasal compound.

For example, the token Allerweltsfragen is not necessarily in the dictionary, but it can be decomposed into Allerwelt+s+fragen and ultimately into aller+welt+s+fragen. Fragen and Welt are identified as in-dictionary nouns, aller is a valid component, and s is among a fixed number of composition rules. Thus, this token is classified as PC.

Evaluation

The evaluation is performed on a gold standard of manually annotated samples: lists of PCs (coarse-grained and fine-grained) and a list of other similar compounds (noise). There are 123 coarse, 103 fine, and 504 noise tokens. The samples mainly come from experiments with billion-token web corpora [START_REF] Barbaresi | For a fistful of blogs: Discovery and comparative benchmarking of republishable German content[END_REF][START_REF] Barbaresi | Efficient construction of metadata-enhanced web corpora[END_REF], completed by results from previous studies [START_REF]IDS: Deutsches Referenzkorpus/Archiv der Korpora geschriebener Gegenwartssprache 2011-I[END_REF]. They are annotated manually following expert criteria defined in [START_REF] Hein | Phrasenkomposita im Deutschen. Empirische Untersuchung und konstruktionsgrammatische Modellierung[END_REF]. 5Apart from morphological criteria such as binarity or constraints for the realization of linking elements, the question whether the non-head can be considered as a phrasal element is crucial for the identification as PC. We assume a gradual understanding of the category "phrase" in this context, with congruency between the elements of the non-head being an important criterion, cf. Harte-Jungs-Gerede or 1000-Stunden-Jahr, but not Dreibettzimmerzuschlag. In addition to these classical cases, entities whose status as a phrase is less clear are also considered here, e.g. Coca-Cola-trink-Unterhaltungs-Freundschaft (contains only a verb stem as verbal element). Both syntactically complete structures (e.g. "Der-Reporter-macht-sich-langsam-auf-den-Weg-indie-Redaktion"-Stunde) as well as sentence-like elliptical structures (e.g. "Jetzt geht's los"-Motto) in non-head position are considered to be within the category "sentence".

Entities which do not correspond to our criteria are gathered in the noise list, whose purpose resides in emulating larger datasets by entailing long tokens such as proper names, complex compounds, and compounds which share a formal similarity with phrasal compounds, notably complex nominal compounds (Waschsalontristesse).

In order to do justice to the numerous entities which fulfill certain, but not all of the criteria linked to the PC-status, we make use of a coarse inter-category. Constructs which have something to do with PCs from a coarse-grained perspective, particularly constructs with a phrasal component, are collected in this list: Immernacktschlafende, product of phrasal derivation [START_REF] Lawrenz | Moderne deutsche Wortbildung. Phrasale Wortbildung im Deutschen: Linguistische Untersuchung und sprachdidaktische Behandlung[END_REF]; Grünkohlinderbadewannewaschens, product of phrasal conversion [START_REF] Lawrenz | Moderne deutsche Wortbildung. Phrasale Wortbildung im Deutschen: Linguistische Untersuchung und sprachdidaktische Behandlung[END_REF]; Afterwork[ichraffmichgradsonochauf]FeierabendSportler, phrasal element in the middle of a complex construction [START_REF] Finkbeiner | Boris "Ich bin drin" Becker ("Boris I am in Becker"). Syntax, semantics and pragmatics of a special naming construction[END_REF]; Einpersonenhaushalt, lack of congruency within the non-head, potential phrase because of the A+N-non-head; Mehr-Aufmerksamkeitsheischerei, realization of a non paradigmatic linking element in combination with a non-lexicalized non-head [START_REF] Hein | Phrasenkomposita im Deutschen. Empirische Untersuchung und konstruktionsgrammatische Modellierung[END_REF]. Because they share certain properties with fine-grained PCs, the entities from the coarse list can be useful for the automatic detection of PCs that are fully compatible with the theoretical model.

After empirical testing, the smallest possible token length for learning and searching is fixed to 4 characters, the upper bound on token and subword length during learning phase is 16 characters. We test several lists which are expected to contain valuable information on variation at morphological level. On one hand, morphologically motivated word lists which have been made available for training and/or experiments on German words by the MarMoT [START_REF] Müller | General methods for fine-grained morphological and syntactic disambiguation[END_REF] and GermaNet [START_REF] Henrich | Determining Immediate Constituents of Compounds in Ger-maNet[END_REF] systems are tested in this particular context. On the other hand, an empirical dataset is used for comparison, it stems from a combination of common tokens from a german reference corpus [START_REF] Geyken | The DWDS corpus: A reference corpus for the German language of the 20th century[END_REF] and from newspaper corpora [START_REF] Barbaresi | Ad hoc and general-purpose corpus construction from web sources[END_REF] (as described in [START_REF] Barbaresi | Bootstrapped OCR error detection for a less-resourced language variant[END_REF]). 1. Results of evaluation on manually annotated samples (coarse and fine-grained). MMT = MarMoT, GNT = Germanet, CPS = corpus data. Higher is better.

Table 1 summarizes the results. The training data from the MarMoT morphological toolkit lead to the best general results (coarse+fine) as well as the best compromise between precision and recall (F1-measure), but the empirical data from a selection of corpora reaches the best accuracies in all three settings. Therefore, it appears that coarse-grained detection of phrasal compounds is best performed with empirical learning data, whereas fine-grained detection can benefit from a combination of rule-based and frequency-based word lists.

Discussion

More seldom seen combinations can be problematic and lead to a decrease in recall, mostly because of segmentation and component identification issues. First, the token Halsringreitjungfrau is correctly segmented into Halsring+reit+jungfrau, but since neither the "reit" modifier (corresponding to the verb reiten) nor the potential noun "Reitjungfrau" are present in the training data, the case is left undecided at the current stage of implementation. The greediness of the search algorithm could also be fine-tuned: the (non-PC) token Ichhaballesimgrifflern is decomposed into ichhaballesim -an unknown string resulting from the algorithm not being greedy enough, whereas the decomposition into lern and griff is too greedy and misses the nominal formation in dative form.

Second, the dictionary coverage obtained from reference and newspaper corpora affects precision. Grünpanzerschildkröte (a rare species of tortoise) is wrongly considered to be a PC (lack of congruency) since the token is decomposed correctly, grün is an adjective, and Grünpanzer does not appear to be lexicalized. Component parts coming from other languages are also problematic, such as in Mainstream+medien+superfrau, where the lexical class of Mainstream is hard to assess automatically due to sparse data. Additionally, a systematic notion of congruence as well as a refined analysis of combining elements seem to be necessary to improve the detection process: so are Grün+gemüse+n+spendeaktion and Nicht+eintreten+s+entscheid both analyzed as PCs, although this is no clear-cut case and only the first one has been annotated as a potential/coarse-grained one.

Finally, the model does not presently yield information about frequency effects. As it is restricted to concatenative morphology, the fact that a stem has to be in the dictionary is a strong limitation impeding recall in particular [START_REF] Demberg | A language-independent Unsupervised Model for Morphological Segmentation[END_REF]. However, an overall conservative setting has been kept so far as it prevents the model from overgenerating.

Conclusions

We have presented a study to identify and document a rare phenomenon on which there is very little empirical evidence, phrasal compounds occurring in the form of as a single token without punctuation between their component parts. Our method implies a systematic approach as well as corpora which are large and diverse enough. It operates at the crossroads of qualitative and quantitative research, in such a way that both approaches benefit from each other. On one hand, we need empirical data to draw conclusions on this rarely observed phenomenon. On the other hand, trying to replicate fine-grained decisions also makes for more stringent and thorough criteria. Our method is based on word segmentation and morphological analysis, the first takes advantage of a data-driven learning process while the latter uses existing software. As documented examples are quite scarce, machine-based scans through large web corpora are one possible way to look at these compounds in all their (so far unsuspected) variety.

Since one specific communicative function of -at least one sort of -PCs can be seen in producing expressivity effects [START_REF] Hein | Phrasenkomposita im Deutschen. Empirische Untersuchung und konstruktionsgrammatische Modellierung[END_REF][START_REF] Meibauer | How marginal are phrasal compounds? Generalized insertion, expressivity, and I/Q-interaction[END_REF], this word formation type seems to be predestined for a productive use in computer-based communication, which web corpora entail. Our results show that coarse-grained detection of phrasal compounds is best performed with empirical data, whereas fine-grained detection could be improved with a combination of rule-based and frequency-based word lists. Additionally, the investigation of PCs in web corpora displays a fruitful supplement to the newspaper-based investigations. If we compare results from both sources, there seem to be parallels inasmuch as certain lexemes are more predestined than others to appear as a head word in PCs. For example, there are many PCs whose head word is a denomination of a person (e.g. Frau) in the present findings. Such heads are often combined with non heads which express a stereotypical property of a person or a type of person [START_REF] Steyer | Satzwertige usuelle Wortverbindungen und gebrauchsbasierte Muster[END_REF], such as Wäschewaschaufhängbüglezusammenlegfrau or buchcoverfotosmitsmartphonecamerabildermachfrau.

Looking at the PCs which we have automatically extracted from web corpora, one can conclude that their orthographic realization, i.e. the missing use of punctuation between the component parts, seems to increase their degree of expressivity. This holds especially for very complex/long PCs like AfterworkichraffmichgradsonochaufFeier-abendSportler. Catching attention or being creative seems to be more important in this case than facilitating the reception for the reader by the use of punctuation. Moreover, creatively formed PCs such as Oberflächlichallesmöglicheabernichtsrichtiglerner contribute to reject the claim [START_REF] Lawrenz | Moderne deutsche Wortbildung. Phrasale Wortbildung im Deutschen: Linguistische Untersuchung und sprachdidaktische Behandlung[END_REF] that predominantly lexicalized PCs (e.g. Armeleuteessen) are written as one word. Future work includes giving answers to linguistically relevant open questions with respect to the proportion of PCs written together in comparison to PCs with hyphens, the potential existence of a systematic difference between both PC types, and further properties of compounds which are suitable both for qualitative analysis and automatic identification.

"One-should-be-able-to-talk-about-everything motto", "I-like-you-policy". All examples appear in their original graphic realization, as found in previous studies[START_REF]IDS: Deutsches Referenzkorpus/Archiv der Korpora geschriebener Gegenwartssprache 2011-I[END_REF] and billion-token web corpora[START_REF] Barbaresi | For a fistful of blogs: Discovery and comparative benchmarking of republishable German content[END_REF][START_REF] Barbaresi | Efficient construction of metadata-enhanced web corpora[END_REF]

One PC-type defined is not captured by our automatic detection: Word formations whose nonhead consists of not explicitly coordinated NPs, e.g. Frage-Antwort-Stunde, cf. p. 194 f.


Adrien Barbaresi
email: adrien.barbaresi@oeaw.ac.at

Discriminating between Similar Languages using Weighted Subword Features

The present contribution revolves around a contrastive subword n-gram model which has been tested in the Discriminating between Similar Languages shared task. I present and discuss the method used in this 14-way language identification task comprising varieties of 6 main language groups. It features the following characteristics: (1) the preprocessing and conversion of a collection of documents to sparse features; (2) weighted character ngram profiles; (3) a multinomial Bayesian classifier. Meaningful bag-of-n-grams features can be used as a system in a straightforward way, my approach outperforms most of the systems used in the DSL shared task (3rd rank).

Introduction

Language identification is the task of predicting the language(s) that a given document is written in. It can be seen as a text categorization task in which documents are assigned to pre-existing categories. This research field has found renewed interest in the 1990s due to advances in statistical approaches, and it has been active ever since, particularly since the methods developed have also been deemed relevant for text categorization, native language identification, authorship attribution, text-based geolocation, and dialectal studies [START_REF] Lui | Classifying English Documents by National Dialect[END_REF].

As of 2014 and the first Discriminating between Similar Languages (DSL) shared task (Zampieri et al., 2014), a unified dataset [START_REF] Tan | Merging Comparable Data Sources for the Discrimination of Similar Languages: The DSL Corpus Collection[END_REF] comprising news texts of closely-related language varieties has been used to test and benchmark systems. The documents to be classified are quite short and may even be difficult to distinguish for human annotators, thus adding to the difficulty and the interest of the task. A second shared task took place in 2015 [START_REF] Zampieri | Overview of the DSL Shared Task 2015[END_REF]. An analysis of recent developments can be found in Goutte el al. (2016) as well as in the report on the third shared task [START_REF] Malmasi | Discriminating between Similar Languages and Arabic Dialect Identification: A Report on the Third DSL Shared Task[END_REF].

The present study was conducted on the occasion of the fourth VarDial workshop [START_REF] Zampieri | Findings of the VarDial Evaluation Campaign 2017[END_REF]. It focuses on submissions to the DSL task, a 14-way language identification task comprising varieties of six main language groups: Bosnian (bs), Croatian (hr), and Serbian (sr); Argentine (es-AR), Peruan (es-PE), and Peninsular Spanish (es-ES); Dari Persian (fa-AF) and Farsi/Iranian Persian (fa-IR); Québec French (fr-CA) and Hexagonal French (fr-FR); Malay (Bahasa Melayu, my) and Indonesian (Bahasa Indonesia, id); Brazilian Portuguese (pt-BR) and European Portuguese (pt-PT).

Not all varieties are to be considered equally since differences may stem from extra-linguistic factors. It is for instance assumed that Malay and Indonesian derive from a millenium-old lingua franca, so that shorter texts have been considered to be a problem for language identification [START_REF] Bali | Automatic Identification of Close Languages-Case Study: Malay and Indonesian[END_REF]. Besides, the Bosnian/Serbian language pair seems to be difficult to tell apart whereas Croatian distinguishes itself from the two other varieties mostly because of political motives (Ljubeši [Pleaseinsertintopreamble] et al., 2007;[START_REF] Tiedemann | Efficient discrimination between closely related languages[END_REF].

The remainder of this paper is organized as follows: in section 2 the method is presented, it is then evaluated and discussed in section 3.

Method

Preprocessing

Preliminary tests have shown that adding a custom linguistic preprocessing step could slightly improve the results. As such, instances are tokenized using the SoMaJo tokenizer [START_REF] Proisl | SoMaJo: Stateof-the-art tokenization for German web and social media texts[END_REF], which achieves state-of-the-art accuracies on both web and CMC data for German. As it is rule-based, it is deemed efficient enough for the languages of the shared task. No stop words are used since relevant cues are expected to be found automatically as explained below. Additionnally, the text is converted to lowercase as it led to better results during development phase on 2016 data.

Bag of n-grams approach

Statistical indicators such as character-and tokenbased language models have proven to be efficient on short text samples, especially character n-gram frequency profiles from length 1 to 5, whose interest is (inter alia) to perform indirect word stemming [START_REF] Cavnar | N-Gram-Based Text Categorization[END_REF]. In the context of the shared task, a simple approach using n-gram features and discriminative classification achieved competitive results [START_REF] Purver | A Simple Baseline for Discriminating Similar Languages[END_REF]. Although features relying on the output of instruments may yield useful information such as POSfeatures [START_REF] Zampieri | N-gram language models and POS distribution for the identification of Spanish varieties[END_REF], the diversity of the languages to classify as well as the prevalence of statistical methods call for low-resource methods that can be trained and applied easily.

In view of this I document work on a refined version of the Bayesline [START_REF] Tan | Merging Comparable Data Sources for the Discrimination of Similar Languages: The DSL Corpus Collection[END_REF] which has been referenced in the last shared task (Barbaresi, 2016a) and which has now been used in official competition. After looking for linguistically relevant subword methods to overcome data sparsity (Barbaresi, 2016b), it became clear that taking frequency effects into consideration is paramount. As a consequence, the present method grounds on a bag-of-n-grams approach. It first proceeds by constructing a dictionary representation which is used to map words to indices. After turning the language samples into numerical feature vectors (a process also known as vectorization), the documents can be treated as a sparse matrix (one row per document, one column per n-gram).

Higher-order n-grams mentioned in the development tests below use feature hashing, also known as the "hashing trick" [START_REF] Weinberger | Feature Hashing for Large Scale Multitask Learning[END_REF], where words are directly mapped to indices with a hashing function, thus sparing memory. The upper bound on the number of features has been fixed to 2 24 in the experiments below.

Term-weighting

The next step resides in counting and normalizing, which implies to weight with diminishing importance tokens that occur in the majority of samples. The concept of term-weighting originates from the field of information retrieval [START_REF] Peter | A Statistical Approach to Mechanized Encoding and Searching of Literary Information[END_REF][START_REF] Sparck | A Statistical Interpretation of Term Specificity and its Application in Retrieval[END_REF]. The whole operation is performed using existing implementations by the scikit-learn toolkit [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF], which features an adapted version of the tfidf (term-frequency/inverse document-frequency) term-weighting formula.1 Smooth idf weights are obtained by systematically adding one to document frequencies, as if an extra document was seen containing every term in the collection exactly once, which prevents zero divisions.

Naive Bayes classifier

The classifier used entails a conditional probability model where events represent the occurrence of an n-gram in a single document. In this context, a multinomial Bayesian classifier assigns a probability to each target language during test phase. It has been shown that Naive Bayes classifiers were not only to be used as baselines for text classification tasks. They can compete with state-ofthe-art classification algorithms such as support vector machines, especially when using approriate preprocessing concerning the distribution of event frequencies [START_REF] Rennie | Tackling the Poor Assumptions of Naive Bayes Text Classifiers[END_REF]; additionally they are robust enough for the task at hand, as their decisions may be correct even if their probability estimates are inaccurate [START_REF] Rish | An Empirical Study of the Naive Bayes Classifier[END_REF].

"Bayesline" formula

The Bayesline formula used in the shared task grounds on existing code [START_REF] Tan | Merging Comparable Data Sources for the Discrimination of Similar Languages: The DSL Corpus Collection[END_REF] 2 and takes advantage of a comparable feature extraction technique and of a similar Bayesian classifier. The improvements described here concern the preprocessing phase, the vector representation, and the parameters of classification. Character n-grams from length 2 to 7 are taken into account. 3 Evaluation

Data from the third edition

In order to justify the choice of the formula, experiments have been conducted on data from the third edition of the DSL shared task [START_REF] Malmasi | Discriminating between Similar Languages and Arabic Dialect Identification: A Report on the Third DSL Shared Task[END_REF]; training and development sets have been combined as training data, and gold data used for evaluation. The method described above has been tested with several n-gram ranges; the results are summarized in Table 1. The best combinations were found with a minimum n-gram length of 1 to 3 and a maximum n-gram length of 6 to 8. Accordingly, an aurea mediocritas from 2 to 7 has been chosen.

Table 2 shows the extraction, training, and testing times for n-gram lengths with a mininum of 2. One can conclude that the method is computationnally efficient on the shared task data. Execution with feature hashing is necessary for higherorder n-grams due to memory constraints; it effectively improves scalability but it also seems to be a trade-off between computational efficiency and accuracy, probably due to the upper bound on used features and/or hash collisions. Table 3 documents the efficiency and accuracy of several algorithms on the classification task, without extensive parameter selection. The Ridge [START_REF] Rifkin | Notes on Regularized Least Squares[END_REF] and Naive Bayes classifiers would have outperformed the best submis-sion of the 2016 competition (0.894) with scores of respectively 0.895 and 0.902, while the Passive-Aggressive [START_REF] Crammer | Online Passive-Aggressive Algorithms[END_REF] and Linear Support Vector [START_REF] Fan | LIBLINEAR: A Library for Large Linear Classification[END_REF] classifiers would have been ranked second with a score of 0.892. It is noteworthy that the Naive Bayes classifier would still have performed best without taking the development data into consideration (accuracy of 0.898).

Range Extraction Training

Data from the fourth edition

As expected, the method performed well on the fourth shared task, as it reached the 3rd place out of 11 teams (with an accuracy of 0.925 and a weighted F1 of 0.925). In terms of statistical significance, it was ranked first (among others) by the organizers. The official baseline/Bayesline used a comparable algorithm with lower results (accuracy and weighted F1 of 0.889).

The confusion matrix in Figure 1 details the results. Three-way classifications between the variants of Spanish and within the Bosnian-Croatian-Serbian complex still leave room for improvement, although Peruvian Spanish does not seem to be as noisy as the Mexican Spanish data from the last edition. The F-score on variants of Persian is fairly high (0.960) which proves that the method can be applied to a wide range of alphabets.

The same method has been tested without preprocessing on new data consisting in the identification of Swiss German dialects (GDI shared task). The low result (second to last with an accuracy of 0.627 and a weighted F1 of 0.606) can be explained by the lack of adaptation, most notably to the presence of much shorter instances. The classification of the Lucerne variant is particularly problematic, it calls for tailored solutions.

Conclusion

The present contribution revolves around a contrastive subword n-gram model which has been tested in the Discriminating between Similar Languages shared task. It features the following char- (3) a multinomial Bayesian classifier, hence the name "Bayesline". Meaningful bag-of-n-grams features can be used as a system in a straightforward way. In fact my method outperforms most of the systems used in the DSL shared task.

Thus, I propose a new baseline and make the necessary components available under an open source licence. 4 The Bayesline efficiency as well as the difficulty to reach higher scores in open training could be explained by artificial regular-4 https://github.com/adbar/vardial-experiments ities in the test data. For instance, the results for the Dari/Iranian Persian and Malay/Indonesian pairs are striking, these clear distinctions do not reflect the known commonalities between these language varieties. This could be an artifact of the data, which feature standard language of a different nature than the continuum "on the field", that is between two countries as well as within a single country. The conflict between in-vitro and real-world language identification has already been emphasized in the past [START_REF] Baldwin | Language Identification: The Long and the Short of the Matter[END_REF]; it calls for the inclusion of web texts (Barbaresi, 2016c) into the existing task reference.

Figure 1 :

 1 Figure 1: Confusion matrix for DSL task (closed training, 2017 data)

Table 1 :

 1 Benchmark by F1-weighted of a common range of n-gram length combinations on 2016 DSL data (*=hashed features)

	3

Table 3 :

 3 Comparison of several classifier types on the extracted feature vectors, ordered by ascending training time (in seconds) on data from 2016. Classifiers used without extensive parameter tuning, linear SVC and SGD with L2 penalty.

	Type	Training (s) Accuracy F1-weighted
	Naive Bayes	14	.902	.902
	Bernoulli NB	16	.882	.883
	Nearest Centroid/Rocchio	33	.759	.760
	Stochastic Gradient Descent	464	.813	.813
	Perceptron	764	.884	.884
	Passive-Aggressive	947	.892	.892
	Linear Support Vector Classifier	1269	.892	.892
	Ridge Classifier	1364	.895	.895

http://scikit-learn.org/stable/modules/feature extraction.html

2 https://github.com/alvations/

bayesline 3 TfidfVectorizer(analyzer='char', ngram range=(2,7), strip accents=None, lowercase=True) followed by MultinomialNB(alpha=0.005), adapted from https://web.archive.org/web/20161215142013/http://scikitlearn.org/stable/auto examples/text/document classification 20newsgroups.html

Acknowledgments

Thanks to the anonymous reviewers for their comments.


Cyril Nguyen

Van Phu

Nadir Farhi

Haj-Salem Habib

Jean-Patrick Lebacque

A vehicle-to-infrastructure communication based algorithm for urban traffic control

Keywords: intelligent transportation systems, traffic control, intelligent vehicles, vehicular ad hoc networks

We present in this paper a new algorithm for urban traffic light control with mixed traffic (communicating and non communicating vehicles) and mixed infrastructure (equipped and unequipped junctions). We call equipped junction here a junction with a traffic light signal (TLS) controlled by a road side unit (RSU). On such a junction, the RSU manifests its connectedness to equipped vehicles by broadcasting its communication address and geographical coordinates. The RSU builds a map of connected vehicles approaching and leaving the junction. The algorithm allows the RSU to select a traffic phase, based on the built map. The selected traffic phase is applied by the TLS; and both equipped and unequipped vehicles must respect it. The traffic management is in feedback on the traffic demand of communicating vehicles. We simulated the vehicular traffic as well as the communications. The two simulations are combined in a closed loop with visualization and monitoring interfaces. Several indicators on vehicular traffic (mean travel time, ended vehicles) and IEEE 802.11p communication performances (endto-end delay, throughput) are derived and illustrated in three dimension maps. We then extended the traffic control to a urban road network where we also varied the number of equipped junctions. Other indicators are shown for road traffic performances in the road network case, where high gains are experienced in the simulation results.

I. INTRODUCTION

A. Introduction

Penetration rate of communicating vehicles is expected to increase in the next years. Compared to in-road detectors and video sensors, a wireless road side unit (RSU) can collect more detailed vehicle data such as location, speed and acceleration rate, more than once a second, on some hundred meters range and probably at lower cost [START_REF] Florin | A survey of vehicular communications for traffic signal optimization[END_REF]. This new amount of high resolution data provided by V2X communication enables new traffic signal controls. We present a new reactive algorithm based on V2I communications using WAVE/IEEE 802.11p protocol. Simulation for road traffic and communication networking has been conducted using VEINS framework [START_REF] Sommer | Bidirectionally Coupled Network and Road Traffic Simulation for Improved IVC Analysis[END_REF]. This simulation framework led to a performance study of both road traffic and communication protocols. We show that the gain in road traffic performance is significant most of the time, especially in the case of a high penetration rate for vehicles and junctions.

B. State of the art

In the field of traffic signal control based on vehicular communication, several approaches have been developed in the few last years [START_REF] Goodall | Traffic signal control with connected vehicles[END_REF] : over-saturation algorithms which tend to avoid blockages by using V2I communication, gap-out algorithms which terminate the phase green if no vehicle is detected during a gap-out time, and platoon based algorithms which use vehicle clustering to provide acyclic timing plans. Some other approaches tend to minimize cumulative delays.

In [START_REF] Agbolosu-Amison | Quantifying benefits of a dynamic gap-out feature at an actuated traffic signalized intersection under cooperative vehicle infrastructure system[END_REF], a dynamic gap-out algorithm has been presented. Total vehicular delays are minimized and the optimization determines "phase sequence, phase green times, and gap-out times (both dynamic and regular gap-outs)." In [START_REF] Kwatirayo | Optimizing intersection traffic flow using vanet[END_REF], a reactive control based on VANET communication is detailed. Different weights are assigned to vehicles depending on their distance to the junction. A timing plan is then computed and applied using these weights.

Some papers have finely evaluated performances of WAVE/IEEE 802.11.p protocols [START_REF] Wang | Ieee 802.11p performance evaluation and protocol enhancement[END_REF], some of them comparing pros and cons of WAVE and alternatives such as LTE [START_REF] Mir | Lte and ieee 802.11p for vehicular networking: a performance evaluation[END_REF]. Coupling road traffic and communication simulators have recently been achieved in VEINS [START_REF] Sommer | Bidirectionally Coupled Network and Road Traffic Simulation for Improved IVC Analysis[END_REF]. We also report ITETRIS [START_REF] Kumar | itetris: Adaptation of its technologies for large scale integrated simulation[END_REF] and VSimRTI [START_REF] Schünemann | V2x simulation runtime infrastructure vsimrti: An assessment tool to design smart traffic management systems[END_REF] that declare successful coupled simulation, even if we haven't been in measure to evaluate these last two softwares in detail. However, in the case of road traffic control applications, we did not see communication performance studies with specialized communication simulators.

C. Paper organization

We aimed in this paper to propose a new traffic light control algorithm, based on V2I communication and evaluated with a fine grained and extended simulation tool, VEINS [START_REF] Sommer | Bidirectionally Coupled Network and Road Traffic Simulation for Improved IVC Analysis[END_REF]. We modified VEINS in order to include TCP/IP support over IEEE 802.11p. We present some performance indicators of the WAVE protocol stack in the scenario of this new kind of road traffic control. This paper is organized in four parts. In part I, it has been provided the global context and state of the art in the field of connected traffic light signal control. In part II, a new algorithm is presented for road traffic control. Then simulation scenarii and results are shown for one junction and for a small American like road network in part III. In part IV we open perspectives to future works.

II. CONNECTED TRAFFIC LIGHT SIGNAL CONTROL

A. Algorithm description

In this section we describe a new local control algorithm. This control makes some hypothesis on vehicles and infras-tructure and is composed of the following subtasks : building a map, electing a vehicle and actuating the TLS.

1) Assumptions: We use the terminology described in [START_REF] Florin | A survey of vehicular communications for traffic signal optimization[END_REF]. We assume that some junctions of the road network are equipped with traffic light signals (TLS) with communication capabilities. In our case the communication protocol is IEEE 802.11p coupled with the Internet Protocol version 4 (IPv4) and the Transmission Control Protocol (TCP). TCP adds transport services to IEEE 802.11.p, such as a reliable and ordered delivery of byte streams [START_REF] Tanenbaum | Computer Networks[END_REF]. It is used in conjunction with IP which provides network routing services. Hence, we suppose that some TLS are able to communicate with the TCP/IP protocols over IEEE 802.11p and we consider it as an Intersection Agent (IA). Similarly, we suppose that some cars are equipped with the same communication capabilities and are also able to localize themselves, for example with GPS modules which provide in addition global time synchronization. We call them equipped vehicles or Vehicle Agents (VA) [START_REF] Florin | A survey of vehicular communications for traffic signal optimization[END_REF].

2) Dynamic Maps: With such capabilities, the IA can build a map of the connected vehicles coming and leaving the junction. Similarly each vehicle agent (VA) builds a map of the IAs approaching or leaving it in its communication range. To achieve this, we designed and programmed a map module in OMNET++ [START_REF] Varga | The omnet++ discrete event simulation system[END_REF]. For the map of the vehicles, the coordinates system is relative to the earth. Instead, for the map of the IAs, the coordinates system is relative to the concerned vehicle position. This change of coordinates enables the use of the same module for IAs map and vehicles map. The maps are dynamic; they are updated periodically each time a message is received for the IA, and triggered on timer for the vehicles. Map's data that are older than a given time, named here map module length, are cleared.

An IA signals itself by broadcasting its IP address and coordinates via UDP protocol. Once the IA announced, the vehicles equipped with UDP client build a local map of all the IAs in their communication range. These vehicles then elect the closest IA approaching. So, the vehicles know their relative positions to the closest junction approaching, without need for communication with the IA anymore. Once close to the elected junction, the vehicles open a TCP connection with the IA.

After the TCP connection with the elected IA is established, all vehicles approaching the junction send periodically their position to the IA, each message being timestamped, with a time period named here position send interval. These vehicles data received by the IA enable the build of a map indexed by a unique vehicle identifier, described in TABLE I. Among the different fields of the map, we notice the state of the vehicle (approaching or leaving the junction) which is computed using the positions of vehicles and TLS.

3) Election: We say the road state and a given junction map are synchronized when all vehicles in the junction map have been detected in the last map module timeout seconds. Periodically, every election interval time and when the junction map is synchronized, the IA computes the lead the car position is defined by its radius to the TLS and sin θ the angle this radius is from the (x) axis s the state of the car whether the car is coming or leaving the junction vehicles on the approaching edges. In our case, we suppose that the junctions have only two incoming edges, each edge having one lane. So there can be two lead vehicles maximum in our case. The two incoming edge priorities alternate every cycle duration/2, where cycle duration is the duration of the TLS periodic program. A vehicle among lead vehicles from incoming edges is elected with the Algorithm 1. If the Algorithm 1 runs successfully, the IA sends a message to the elected vehicle. Otherwise the RSU will try to elect a vehicle after a election interval time.

Algorithm 1: Vehicle Election

1 function Elect (p, v, d p , d v , d min , α)
Input :

• p is the identifier of the lead vehicle on the prioritized edge, and it is N one if no vehicle is detected on the prioritized edge • v is the identifier of the lead vehicle on the non prioritized edge, and it is N one if no vehicle is detected on the non prioritized edge • d p represents the distance p is to the junction, in case p = N one, • d v represents the distance v is to the junction, in case v = N one, • d min > 0 is the minimum distance to consider a vehicle close to the junction, • α > 1 is a coefficient to ponderate the minimum distance. Output: p or v.

4) Action:

The elected vehicle has now the power to set the TLS to a favorable state, which is green light for the edge on which it is moving and red light for other edges. To do this, the elected vehicle sends a message to the IA with its established TCP connection. We set a minimum and a maximum duration for a given TLS state : min state duration and max state duration. If no state switch has happened during max state duration time, the state of the TLS is automatically changed. Similarly, the state of the TLS must remain the same for at least min state duration. With the min state duration we ensure stability. With the max state duration we ensure dynamics of the states and avoid blockages of the TLS. As we set max state duration = cycle duration/2, if no vehicle is connected near a junction, then the associated TLS will follow an open loop cyclic program with cycle duration period. Once the connected vehicles know they are leaving the junction (with GPS and local map but not with communication means), they disconnect after they reach a given distance away from the junction.

The process starts again for the next junction and so on.

B. Properties of the algorithm 1) Property 1:

The local control is safe because the control is done by means of a TLS which never gives green light simultaneously to antagonistic phases.

2) Property 2: It is not necessary for a vehicle to be equipped to pass the junction.

3) Property 3: As the control tends to minimize delays for equipped vehicles, communicating equipments of vehicles are encouraged. As the control presents gains for the road traffic, communicating equipments of junctions are encouraged.

C. Implementation

We used VEINS Framework [START_REF] Sommer | Bidirectionally Coupled Network and Road Traffic Simulation for Improved IVC Analysis[END_REF] which includes SUMO [START_REF] Krajzewicz | Recent development and applications of SUMO -Simulation of Urban MObility[END_REF] as microscopic traffic simulator and OMNET++ [START_REF] Varga | The omnet++ discrete event simulation system[END_REF] as communication network simulator. We modified and extended VEINS Framework in order to get TCP/IP support over IEEE 802.11p. To do this, "inet" models and Veins framework have been integrated and connected together. Fig. 1: The IEEE WAVE protocols stack [START_REF]Ieee guide for wireless access in vehicular environments (wave)architecture[END_REF] Some application modules have been written : map, car, road side unit, TCP client and server, UDP client and server applications, which implement the algorithm described above. Commands to control the TLS states have been added. The MAC1609 module of VEINS framework module has been modified to connect TCP/IP to IEEE 802.11p layers.

III. SIMULATION RESULTS

We simulated a few runs with different seeds, each run being reproducible. We present statistical results for the road network case with 20 different simulations and preliminary results (one typical run) for the one junction case.

A. One Junction with connected TLS 1) Scenario for one junction: We used the following road network, composed of one junction, with one lane incoming edges of 300 m length. We varied the demand which is the number of vehicles (uniformally inserted in time) per lane per hour. For each of this traffic demand, we varied the ratio of equipped vehicles with on board unit (OBU). The total simulation time is 600 s. For the communication and the control algorithm, the main parameters are described in TABLE II. 2) Simulation measurements: For the communication we have measured the mean TCP end-to-end delay, TCP throughput on RSU (Road Side Unit) and the amount of TCP application data sent divided by the total simulation time. We define the simulation indicator mean TCP end-to-end delay as the sum of all packet delays divided by the number of packets exchanged. The throughput on RSU is the sum of TCP application packet (successfully received) sizes divided by the simulation time. A given number of communicating hosts may be the result of different combinations of a demand multiplied by a ratio of equipped vehicles. For example, 100% equipped vehicles of 100 vehicles in total, gives the same number as 10% equipped vehicles of a total of 1000 vehicles.

In figure 2 we can see that the amount of TCP application data sent by the nodes increases as the mean vehicle speed decreases. We assume that as the mean vehicle speed is low, the communicating vehicles remain connected longer, and then they send more messages.

In figure 3, we see that the mean TCP end-to-end delay can be as high as 0.8s when vehicle speed is low (about 8m/s). We know from figure 2 that there are more data sent by the nodes when mean speed is low. We suppose that as there are more messages sent in case of low speeds, the mean TCP end-to-end delay will be higher.

The order of magnitudes of end-to-end delay is similar to the ones exposed in [START_REF] Mir | Lte and ieee 802.11p for vehicular networking: a performance evaluation[END_REF]. Clearly, in figure 4, the throughput on RSU is increasing linearly with the number of communicating vehicles. For the road traffic, we measured the ratio of the ended vehicles by the inserted vehicles, and the mean travel time. We observe on figure 5 that the ratio of the ended vehicles by the inserted vehicles increases when the demand decreases and the ratio of equipped vehicles increases. For a given ratio of equipped vehicles, as the road traffic demand increases, the ratio of the ended vehicles by the inserted vehicles decreases. For a given demand, this ratio increases with the number of equipped vehicles.

In figure 6, for a given demand, the mean travel time decreases as the number of equipped vehicles increases. This should encourage the spreading of vehicle communication capabilities. For a fixed demand, the difference in travel time between the worst and the best cases for a total distance of 600 m, may be as high as 20 seconds. Fig. 3: Mean TCP end-to-end delay (s) q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0 100 200 300 400 For the actuator, we define the mean action interval as the mean time interval between two consecutive changes of traffic lights state. We observe in figure 7 that the traffic light state is stable for high traffic demand combined with a high equipped vehicle penetration rate. This minimizes the total yellow time of the traffic light, and then maximizes the junction capacity. For a low demand combined with a high equipped vehicle penetration rate, the control is more reactive. B. Traffic control at the road network level 1) Scenario for the road network: We consider here an American like network with 16 junctions and 40 edges of length 500 m each. This is the same network considered in [START_REF] Farhi | A semi-decentralized control strategy for urban traffic[END_REF], where centralized and decentralized road traffic controls have been combined. Each edge has one lane. We varied the number of equipped junctions : 25%, 50%, 100%; and the penetration rate of equipped vehicles : 20%, 50%, 80%. We defined nine zones in the network. The simulated time is 1800 s and the communication parameters are the same as in the "one junction" scenario. We used SUMO "origin Fig. 8: Regular network example. and destination edges instead of a complete list of edges. In this case the simulation performs fastest-path routing based on the traffic conditions found in the network at the time of departure/flow begin." [START_REF]Vehicle Types, and Routes#Incomplete Routes[END_REF]. The road traffic demand is given in tables III and IV.

3 elected = v; 4 else 5 elected

 35 2 if (p = N one and v = N one and d p > αd min and d v < d min ) or (p == N one and v = N one and d v < d min ) then = p; 6 return elected;

4 ) Property 4 :

 44 When no vehicle is equipped near an equipped junction, the max state duration for a state induces that the TLS runs half time red and half time green light. It is equivalent to a simple open loop cyclic TLS program.

NFig. 2 :

 2 Fig.2: Amount of TCP application data sent divided by the total simulation time (bit/s)

Fig. 4 :

 4 Fig. 4: TCP application throughput on RSU (bit/s)

DFig. 5 :Fig. 6 :

 56 Fig. 5: Ratio of ended vehicles by inserted vehicles at 600s simulation time

DFig. 7 :

 7 Fig. 7: Mean action interval (s) for a cycle duration of 90 s.

TABLE I :

 I The IA and vehicle map module

		unique vehicle identifier
	c	the IA to car TCP connection identifier
	T	the trajectory which is an ordered map of couples (time, coordinates)
	lst	the last time the vehicle data has been received by the IA
	fst	the first time the vehicle data has been received by the IA
	r	the radius is the distance the car is to the approaching junction
	cos θ

TABLE II :

 II Main parameters for the communication and road traffic control. Other parameters are VEINS defaults ones.

	Parameter name	Parameter value
	vehicle TCP position send interval	500 ms
	UDP broadcasting interval	500 ms
	IA election interval	500 ms
	cycle duration	90 s
	max state duration	45 s
	min state duration	8 s
	map module timeout	2 s
	map module length	5 s
	d min	100 m
	α	2
	MAC 1609 use service channel	true
	MAC 1609 bitrate	27 Mbps
	MAC 1609 carrier frequency	5.890 × 10 9 Hz
	transmit power	1 mW
	application message payload	30 bytes
	transceiver sensitivity	-89 dBm

TABLE III :

 III The traffic demand for the first 900 s. Simulation results: (TableV, Table VI and Table VII) We compare our algorithm with an open loop fixed cycle TLS program, where the same cycle time is considered in both cases. This open loop cyclic control can also be achieved with

	Origins	Destinations	Center zone	Each other zone
		Center zone	0	10 (veh)
	Each other zone	15 (veh)	15 (veh)
	2)

zero communicating vehicles in our algorithm. The gain of our algorithm in terms of ended vehicles can be very high, as much as 30%. The gain in running vehicles can be as high as 40% and the gain in mean travel time can reach 30%. We observe that when the penetration rate is 20% and when all junctions are equipped, the algorithm is not efficient. We suppose that as there are less vehicles communicating, less vehicles manage to connect in time (before having passed the junction). It then could be possible that the TLS map is not a good image of the real traffic. This could explain why the cycles of the TLS are not globally adequate. When all junctions are equipped, this can even be globally disturbing.

IV. CONCLUSIONS

We presented a new V2I based TLS control algorithm, with its design, implementation and performance study for communication and road traffic. Compared to an open loop cyclic TLS program, we showed that the presented algorithm features high gains in most of the configurations. However, in few cases, where low penetration rate for vehicles is combined with high ratio of equipped junctions, it seems that the algorithm is not efficient and produces some losses. An hypothesis for this phenomenon has been proposed. Future works could benefit from a mix of microscopic and macroscopic road traffic controls, based on vehicular communication networking.