Olivier Faury
email: ofaury@em-normandie.fr

Ali Cheaitou
email: acheaitou@sharjah.ac.ae

Patrick Rigot-
email: patrick.rigotmuller@mu.ie

Scott Stephenson
email: stephenson@uconn.edu

How attractive is the Northern Sea Route for container shipping? An economic model

Every year, COSCO sends a vessel with containers through the Arctic. This year, Maersk followed suit with the voyage of the 3,956 TEU vessel, Venta. Meanwhile, Arctic shipping hubs are being planned, such as at the ice-free port of Murmansk.

Currently, cargo shipped through the Northern Sea Route (NSR) is composed of raw materials from oil and gas exploitation, a market subject to volatile prices and finite resources. However, sustainable economic development cannot not be based entirely on commodities with these characteristics and that depend on international market volatility. Thus, the shipment of manufactured goods along the NSR may be the next step in its evolution.

Academics agree on the general decline in ice extent and thickness; yet, variability in ice conditions and poorly charted bathymetry in shallow waters may hamper the development of the NSR as a periodic shipping lane for containers.

The aim of this article is to define the relevant market for a maritime company using the NSR, shipping manufactured goods from Asia to Europe, using a new approach to consider sea ice variability and to stress the relevancy of Murmansk as a container hub.

Based on historical environmental data and the POLARIS system, we look at the potential sailing period of ice class 1A vessels according to 3 scenarios: optimistic, intermediate, and pessimistic. We also considered that the vessel could sail directly to Rotterdam or transship the container in Murmansk before reaching Rotterdam.

For each scenario, we define the total cost of the navigation and the number of containers the vessel is able to load on a yearly basis, and hence the yearly loading capacity the NSR is able to provide for this vessel type.

Our results define (1) the transportation cost of a container between Rotterdam and Shanghai and (2) the potential transit time. Compared to the cost and transit time of container shipping by rail and via the Suez Canal route, we characterize the NSR market and the type of cargo NSR shipping should target.

Introduction

Until now, the NSR is mainly used for the exportation of raw materials coming from the oil and gas fields of the Yamal peninsula and its neighbourhood.

Yet its 40% shortcut between the important economic regions of Europe and Asia has piqued the interest of academics and professionals. If this distance savings may be realized for bulk transportation, it may have even greater potential for containers that are highly sensitive to transit time.

However, the NSR faces numerous challenges. Some are related to its geography, such as ice, lack of ports, extra cost due to icebreaker escort, while others are external and are perceived as competitors, such as railroads between Shanghai and Rotterdam, also named the Belt and Road Initiatives project (BRI) and the Suez Canal Route (SCR).

Of the internal elements, ice likely has the highest impact. Due to its presence, vessels are unable to sail safely at their optimal speed, must be winterized involving additional cost, may not be able to sail during winter depending on the level of winterization. The presence of older, thick ice combined with insufficient vessel ice class may mandate the use of icebreakers, leading to additional cost. Low population density and the remoteness of oil and gas fields is the main reason for the low density of ports available for use as repair yards in case of an emergency, further complicating navigation along the route. Yet to enhance the economic attractiveness of this lane and gain in safety, some ports are being upgraded in order to be used as shipping "hubs" such as the case of Murmansk in the Kola peninsula or repair yards. Regarding the issue of a safe navigation, the use of an icebreaker, the reduction of the speed and the winterization of vessel are parameters that influence the way shipowner decide to manage the risk related to the Arctic.

Yet when exporting cargo from China to Europe, two other possibilities exist: the SCR and the BRI. The SCR is the main route used for trade between these two poles of the economic Triade. Schedules along the SCR are largely fixed and are more or less respected by carriers; in addition, unlike the NSR, the SCR is used year-round. The railroad is linked to the Belt and Road Initiative and may benefit from fixed schedules, but has a loading limited loading capacity and may be more expensive than either shipping route. Thus, our analysis will focus on a comparison between the SCR, the railroad and the NSR based on cost and transit time. We will integrate the use of a hub in Murmansk and examine the amount of cargo an ice class 1A container is able to load annually, and which of the three options is faster and least expensive.

Following a literature review, we will present our model. Section 4 focuses on the presentation of the business case while section 5 presents our results. Finally, we will end this analysis with a short discussion and conclusion.

Literature review

As stressed by Theocharis et al. (2018) and [START_REF] Meng | Viability of transarctic shipping routes: a literature review from the navigational and commercial perspectives[END_REF], the NSR has been the subject of frequent analysis in recent years, with most studies dealing with transportation of container vessels. While many studies compare the NSR to the SCR, relatively few examine the profitability of the NSR versus the BRI. Likewise, while most articles assessed the profitability of the NSR versus the SCR, results differ across analyses [START_REF] Lasserre | Case studies of shipping along Arctic routes. Analysis and profitability perspectives for the container sector[END_REF][START_REF] Meng | Viability of transarctic shipping routes: a literature review from the navigational and commercial perspectives[END_REF]. Speed of the vessel, fuel consumption, icebreaker fees, capital and operational expenditures are considered as the main expenditures when dealing with arctic navigation [START_REF] Liu | The potential economic viability of using the Northern Sea Route (NSR) as an alternative route between Asia and Europe[END_REF][START_REF] Gritsenko | A review of Russian ice-breaking tariff policy on the northern sea route 1991-2014[END_REF][START_REF] Lasserre | Case studies of shipping along Arctic routes. Analysis and profitability perspectives for the container sector[END_REF]Erisktad and Ehlers, 2010;[START_REF] Verny | Container shipping on the Northern Sea Route[END_REF].If they are not steady and may change according to the ice conditions, except for [START_REF] Liu | The potential economic viability of using the Northern Sea Route (NSR) as an alternative route between Asia and Europe[END_REF], Faury and Cariou (2016) and faury and Givry (2017), most of cost analysis compute them as factors and not variables.

Few analyses focus on the impact of existing tools, and more precisely on the Polar Code, on Arctic navigation (Fedi et al, 2018a;Faury 2015;Fedi and Faury 2016;Dalaklis et al, 2018). In particular, the POLARIS system is a risk assessment tool providing guidance for optimal speeds for safe navigation, and is understudied despite being part of the Polar Code (Fedi et al, 2018b). In fact, as suggested by [START_REF] Marchenko | Northern Sea Route: Modern State and Challenges[END_REF], unsuitable speed for the environment is the main cause of accidents in Arctic waters. Yet exception for [START_REF] Stoddard | Making sense of Arctic maritime traffic using the Polar Operational Limits Assessment Risk Indexing System (POLARIS)[END_REF] The POLARIS system has not yet been used to define the optimal pathway though the ice infested waters of the Arctic. Close to this analysis, Stephenson et al. (2014) stressed the existing variation of accessibility of the NSR according to different ice scenarios and ice class vessels, but did not examine economic factors. [START_REF] Ragner | Northern Sea Route Cargo Flows and Infrastructure -Present State and Future Potential[END_REF] considers that the lack of port infrastructure is the main reason for the low economic development of the NSR. Since the 2000s, numerous infrastructure projects have been completed or are currently underway. Among them, the Murmansk Transport Hub (MTH), a free trade zone able to handle 1 million TEU in the coming years and connected via railroad to the Russian network and hence to Europe, is estimated to cost 117.4 Billion Rouble and provide 1,700 jobs [START_REF] Trubkina | Extract from the « socio-economic strategy of Murmansk regio till 2025[END_REF]. As explained by [START_REF] Kinossian | Re-colonising the Arctic: The preparation of spatial planning policy in Murmansk Oblast, Russia[END_REF], the Arctic is at the core of the Russian state development strategy, with Murmansk at in the centre, mostly due to its relatively large population, existing industries, and infrastructure such as its large oil and gas tank along the shore [START_REF] Grigoriev | Oil and gas: Russian arctic offshore[END_REF].

Articles comparing the NSR and the railroad are relatively fewer [START_REF] Verny | Container shipping on the Northern Sea Route[END_REF]Moon et al, 2015;[START_REF] Zhu | The environmental costs and economic implications of container shipping on the Northern Sea Route[END_REF]. [START_REF] Verny | Container shipping on the Northern Sea Route[END_REF] compared the economic viability of the NSR versus the railroad with a constant speed. Moon et al (2015) highlighted that the main parameters that influence the choice of transport mode are the transit time and the cost. [START_REF] Zhu | The environmental costs and economic implications of container shipping on the Northern Sea Route[END_REF] concentrated on the market share the NSR and the railroad may capture from the SCR. They compared a 4,500 TEU ice-class vessel versus a 15,000 TEU vessel navigating though the Suez Canal. Considering a fixed length of navigation of 180 days, they concluded that while open, the NSR may attract 20% of the SCR volume, while the railroad would only attract 0.02 %.

Our contribution leans on the integration of the POLARIS system, a risk management tool, within an economic model in order to analyze the profitability of the NSR compared to the railroad and the SCR, positing the use of Murmansk as a container hub to feed the European market as part of the financial strategy of shipowners.

Cost model 3.1. Model parameters

• 𝑅: total number of completed return trips per year from Shanghai to Murmansk.

• 𝑑𝑜𝑑 0 and 𝑑𝑜𝑑 𝐹 : first and last possible day-of-departure from Shanghai for a trip that can be completed without vessel being blocked, depending on the considered scenario. It is worth noting that 𝑉 𝑟 1 , 𝑉 𝑟 2 are calculated as an average constant speed throughout each NSR-leg of the trip (in the two directions) using the POLARIS system as explained in Section 1 and more precisely based on RIO. It is also clear that these average sailing speeds depend on the day-of-departure (𝑑𝑜𝑑 𝑟 1 ) of trip 𝑟 from Shanghai for 𝑉 𝑟 1 and 𝑑𝑜𝑑 𝑟 2 from Rotterdam (or Murmansk) for 𝑉 𝑟 2 . Moreover, 𝑉 𝑟 3 is equal to the vessel design speed.

Transit time and number of trips

We assume that the vessel operates between Shanghai and Rotterdam (or Murmansk) starting from the first day of the period during which navigation is possible, even with icebreaker assistance, until the last day of that period. A trip that starts in Shanghai also ends in Shanghai. The total duration of trip 𝑟 is then calculated as follows:

𝑇 𝑟 = 𝐷 𝑟 1 24 × 𝑉 𝑟 1 + 𝐷 𝑟 2 24 × 𝑉 𝑟 2 + 𝐷 𝑟 3 24 × 𝑉 𝑟 3 + 𝑃𝑇 (1)
Therefore, based on the ice thickness scenario in the NSR, the day-of-departure of the second trip from Shanghai to Rotterdam (or Murmansk) is calculated as follows:

𝑑𝑜𝑑 2 1 = 𝑑𝑜𝑑 1 1 + 𝑇 1
(2 For any further trip 𝑟 = 3, … , 𝑅, the day-of-departure from Shanghai is then calculated as follows: 3) is then used to determine the value of the total possible number of trips per year 𝑅 so that 𝑅 is the largest possible integer for which:

𝑑𝑜𝑑 𝑟 1 = 𝑑𝑜𝑑 𝑟-1 1 + 𝑇 𝑟-1 (3) Equation (
𝑑𝑜𝑑 𝑅 1 ≤ 𝑑𝑜𝑑 𝐹 𝑎𝑛𝑑 𝑑𝑜𝑑 𝑅+1 1 > 𝑑𝑜𝑑 𝐹 (4) A trip that cannot be completed because of heavy ice conditions is not counted.

Cost calculation

The cost calculations in this section assume that one 1A ice-class vessel is used and for a round trip between Shanghai and Rotterdam or between Shanghai and Murmansk. For the option of a transhipment in Murmansk, we assume that the 1A vessel does a round trip between Shanghai and Murmansk and the containers are transported between Murmansk and Rotterdam using the service of a subcontracting company or a maritime liner. Therefore, in this case, to the total cost per TEU, the transhipment and subcontracting (transportation) cost, 𝐶 𝑇𝐸𝑈 𝑇𝑟𝑎𝑛𝑠 , is added. Given that the cost per trip varies from one trip to another, we calculate the total cost for all trips per year and use it to estimate the average total cost per TEU. The total cost per trip, for the return trip 𝑟 = 1, … , 𝑅 and for a departure on 𝑑𝑜𝑑 𝑟 1 is given as follows: 𝐶 𝑟 = 𝐶𝐴𝑃𝐸𝑋 𝑟 + 𝑂𝑃𝐸𝑋 𝑟 + 𝐵 𝑟 + 𝐼𝐵 𝑟 (5) The total capital expenditures per trip are calculated as follows:

𝐶𝐴𝑃𝐸𝑋 𝑟 = 𝐶𝐴𝑃𝐸𝑋 𝑑 × 𝑇 𝑟 (6) The total operational cost per trip is calculated as follows:

𝑂𝑃𝐸𝑋 𝑟 = 𝑂𝑃𝐸𝑋 𝑑 × 𝑇 𝑟 (7) The total bunker fuel cost per trip for both engines is the sum of the bunker fuel cost from the main and the auxiliary engines:

𝐵 𝑆𝐹𝑂𝐶 𝑀 is the specific fuel oil consumption of the main engine [in g/kWh], 𝐸𝐿 𝑀 the engine load of the main engine [in %], and 𝑃𝑆 𝑀 the power of the main engine [in kW]. Finally, 𝐼𝐵 𝑟 is determined for each trip based on the RIO value on the of the day-of-departure of the trip 𝑑𝑜𝑑 𝑟 1 from Shanghai and 𝑑𝑜𝑑 𝑟 2 from Rotterdam (or Murmansk). The total cost per year is then the sum of the cost of all the trips of one year:

𝐶 𝑦 = ∑ 𝐶 𝑟 𝑅 𝑟=1 (12)
Finally, the total average cost per transported TEU container, assuming that the vessel sails with 𝛼 1 utilization rate from Shanghai to Rotterdam (or to Murmansk) and 𝛼 2 from eastbound is as follows:

𝐶 𝑇𝐸𝑈 = 𝐶 𝑦 𝑅 × (𝛼 1 + 𝛼 2 ) × 𝐾 (13)
It is obvious that the total transportation capacity per year of a 1A vessel with a loading capacity of 𝐾 TEUs is 𝑅 × 𝛼 1 × 𝐾 TEUs westbound and 𝑅 × 𝛼 2 × 𝐾 TEUs eastbound.

In case the TEUs are transported to (?)

Sailing speed in ice and navigability period

Navigation in the Arctic involves numerous challenges, of which the most important is ice. The presence of ice represents one of the highest risks for a vessel transiting along the Russian coast. Thus, in order to minimize risk, the use of specific vessels with stronger hulls and engine power may be necessary to withstand encounters with various concentrations of different types of ice, as well as the extreme cold.

To establish guidelines for safe navigation, the Polar Code considered three classes of vessels. The "A" and "B" classes are considered Polar Class vessels with the ability to sail year-round. Vessels with a class "C" are able to navigate within the Arctic but with a lower resistance to ice pressure and limited sailing period in polar waters.

The ability of a vessel to sail within the Arctic can be defined by numerous means (Fedi et al, 2019). Linked to the Polar Code, the POLARIS System provides a methodology for assessing risk in ice that includes the ice thickness, type, and concentration, the air temperature, and the ice class of the vessel. The result is an index that can be used by ship officers as a decision tool to assist in determining if the vessel is able to sail in this area, at what speed, and whether icebreaker assistance is required.

To obtain this information, we determine the Risk Index Outcome (RIO) of the vessel. The RIO is the combination of the Risk Index Value (RIV; Table 1) and the concentration of various types of ice encountered by the vessel as explained in equation ( 14).

𝑅𝐼𝑂 = (𝑅𝐼𝑉 1 . 𝐶 1 ) + (𝑅𝐼𝑉 2 . 𝐶 2 ) … … … … . +(𝑅𝐼𝑉 𝑛 . 𝐶 𝑛 ) (14)
Here, 𝑅𝐼𝑉 𝑛 indicates the ability of the vessel to maneuverer in a concentration (tenths) of a specific ice type encountered by the vessel (𝐶 𝑛 ). Thus, with a RIV maximum at 3 and a minimum of -8, the RIO of a vessel can fluctuate between 30 (optimal conditions) and -80 (worst conditions). The RIO computed indicates the level of risk faced by the vessel, as explained in Table 2, during its navigation. The definition of the risk level helps the vessel captain define the optimal speed for a safe navigation (Table 3) and whether an icebreaker is needed to sail through the area.

The [START_REF] Imo | /Circ 1519[END_REF] indicates that an ice class 1A is able to sail with a RIO between 30 and -10. Based on the ice class of the vessel and on the recommended speed (IMO, 2016), we assumed that the ship would sail at design speed when the RIO is 30, 8 kts when RIO=0 which represents the moment icebreaker assistance may be made mandatory by underwriters, and 3 kts when RIO = -10. Thus, the speed of the vessel is defined by equation ( 15) which integrates these three constraints.

𝑉 = - 1 300 𝑥 2 + 7 15 𝑥 + 8 (15)
Figure 3: vessels' speed according to their class and RIO when sailing independently or assisted by an icebreaker.

Source: Authors (2019)

Business case

As explained previously, most previous studies dealing with container transportation along the NSR compare its profitability with that of the Suez Canal Route (SCR). Because of the large differences in loading capacity, we examine the relevancy of the NSR compared to the railroad. We assume that the cost of shipping one TEU from Shanghai to Rotterdam would be 2,500 USD with a transit time of 18 days [START_REF] Zhu | The environmental costs and economic implications of container shipping on the Northern Sea Route[END_REF].

Our business case relies on the use of an ice class 1A container vessel with a capacity of 3,600 TEU sailing between Shanghai and Murmansk. The choice of this type of vessel has been motivated by the example of the VENTA, a container vessel that sailed along the NSR in September 2018. Based on Clarksons database (2018) we were able to gather technical and economic information regarding the vessels as highlighted in Table 3. Our business case relies on two scenarios to reach the final destination, Rotterdam. The first possibility is to tranship the goods in Murmansk on an open-water vessel on the remainder of the route to Rotterdam. The second option is to sail directly to Rotterdam from Shanghai. The use of Murmansk as a container transhipment hub is related to the intent of the Russian government to develop this port as an Arctic gateway, as indicated by the planned implementation of the Murmansk Transport Hub (MTH) that shall be able to handle 1 million TEU per year (The Ministry of Foreign Affairs of the Russian Federation, 2010). We also assumed that the vessel would spent two days in ports in order to load or unload container [START_REF] Lasserre | Case studies of shipping along Arctic routes. Analysis and profitability perspectives for the container sector[END_REF] Due to the trade imbalance between Shanghai and Rotterdam, the loading factor varies as a function of the direction. We assume that vessels will sail at 70% capacity on the westbound route and 45% on the eastbound route.

Unsuitable speed is a major cause of accidents [START_REF] Marchenko | Northern Sea Route: Modern State and Challenges[END_REF]. Thus, we define the speed according to the RIO of the vessel. To compute the RIO, we extract data from the European Copernicus database which has access to a full range of data on ice conditions worldwide. In this analysis, we use the TOPAZ4 Arctic Ocean Physics Reanalysis data collected via satellite for the period between 1991 and 2015. We used the ARCTIC_REANALYSIS_PHYS_002_003 dataset [START_REF] Von Schuckmann | The Copernicus Marine Environment Monitoring Service Ocean State Report[END_REF] which provides gridded ice thickness and concentration at 12.5 km resolution for 35 years.

To compute the RIO, we extract the ice conditions for XXX Cells over 25 years at daily scale for each year (365 days) and used the RIV of an ice class 1A vessel. Because underwriters require a defined route when agreeing to insure a vessel (Fedi et al, 2018), we assumed one static route connecting the Bering strait to Murmansk.

Based on the RIO values obtained along the grid cells of this route, the vessel speeds (Figure 4) for an ice class 1A with technical specificities of the Venta Maersk was calculated for three scenarios:

• The 75 th best percentile in terms of navigation conditions (good case scenario);

• The median scenario;

• The 25 th lowest percentile in terms of navigation conditions (bad case scenario).

Figure 4 shows the navigability risk assessment for three scenarios on the 21 st of July. In the worst case, it would be technically impossible for an ice class 1A to safely cross the Arctic. On the other hand, in the median case, navigation of the entire route is feasible even if the assistance of an icebreaker may be required, assistance that would not be mandatory in the best-case scenario.

Daily CAPEX definition

Our model assumed that the vessel has a life time of 15 years. During this period, the shipowner has two opportunities to utilize the vessel. One assumes that the shipowner may use the vessel elsewhere during periods of severe ice conditions. This assumption leads us to consider a daily CAPEX of 6,921 USD per day. The other assumes that ice-class vessel specificities prevent its use in open waters. In fact, the characteristics of the water has a negative impact of the manoeuvrability of the vessel, increasing fuel consumption. These technical considerations could lead to an oversupply of container vessels in the market during severe ice periods. In this case, the daily CAPEX would change in regards to the number of sailing days in each scenario.

Bunker price

As explained by [START_REF] Lasserre | Case studies of shipping along Arctic routes. Analysis and profitability perspectives for the container sector[END_REF], the bunker price is one of the main expenditures when sailing within the Arctic. In our case, we assumed a bunker price equal to the mean of the 380cst bunker prices at Rotterdam over the last 10 years from January 4 th 2008 to September 21 st 2018 (Clarksons Database, 2018).

Freight rate between Murmansk and Rotterdam

Our analysis is from the perspective of a shipowner willing to invest in and focus exclusively on the Arctic market. Thus, for the leg between Murmansk and Rotterdam, transportation would be subcontracted to another maritime company. Hence, the cost of shipping a container between Murmansk and Rotterdam is 1,120 USD and 523 USD in the opposite direction.

Regarding the cost of transportation for a container between Rotterdam and Shanghai, we grounded our analysis on the vessel characteristics of the Venta; i.e. 3,600 TEU loading capacity and an optimal speed of 19 kts (Table 3).

Icebreaker fees

The icebreakers fees depend on four types of parameters: technical, month, geography and economic (NSRA, 2018). The technical parameter includes the gross tonnage of the vessel and its ice class. Icebreaker assistance in winter or spring (between December and June) may represent an additional cost of 60% compared to the same assistance in summer or autumn. As explained by [START_REF] Liu | The potential economic viability of using the Northern Sea Route (NSR) as an alternative route between Asia and Europe[END_REF] and [START_REF] Marchenko | Northern Sea Route: Modern State and Challenges[END_REF], the ice conditions change with natural variability. In addition, the NSR is comprised of seven zones (Figure 4) from Novaya Zemlya in the west to the Bering Strait in the East.

For each area crossed escorted by an icebreaker, the vessel must pay fees as a function of the number of zone where the icebreaker was required. The fees are presented in Rub; thus, the exchange rate has an impact on the cost of the assistance. In our case, computed costs are shown in Table 4.

Result

Results are presented according to five scenarios: three conditions of navigation (worst, median and best case) and two market conditions (year-round exploitation of the vessel, or only during the period of navigation along the NSR).

The navigation conditions have a direct impact on the length of the navigation period within the Arctic and thus the cost it may represent. When applied to the ice class 1A vessel, we obtain transit periods for three possible ice conditions as shown in Figure 5a and 5b. Figures 5a and 5b stress the impact of the ice conditions upon the length of navigability of an ice class 1A vessel in both directions. The dotted lines represent the potential length of navigation without icebreaker assistance and the solid line with an icebreaker.

In the worst case, regardless of direction, the icebreaker appears as a mandatory option for navigation.

In the worst case, the vessel would sail 63 of 78 days assisted by an icebreaker when sailing from the Bering Strait to Murmansk, and 57 of 78 days assisted by an icebreaker in the opposite direction.

From the Bering Strait to Murmansk (B/M) in the median and best-case, the vessel would sail 135 days and 174 days respectively (including 27 and 35 days of icebreaker assistance, respectively, for each leg) and 137 days (27 with an icebreaker) and 175 days (35 with an icebreaker) from Murmansk to the Bering Strait (M/B). The assumption of Murmansk as a container hub provides the possibility to transport 2,160 additional containers in the worst and median case and 4,320 containers in the best case compared to transporting containers directly to Rotterdam. This result can be easily explained by the additional distance covered by the vessel.

Cost of the NSR according to ice conditions and length of depreciation period

Regarding the number of days (Table 5) while the 1A vessel is in use, the use of a hub allows sailing 1.3 and 3.6 additional days in the worst and best case, respectively. In the median case with the use of a hub, if the number of containers transported is higher compared to the direct option, the number of days sailed is lower when the vessel stops in Murmansk. This result can be explained by the length of the last eastbound journey in the direct option. In the case of hub option, the last eastbound voyage take place on day 313 and the vessel spends 9.1 days sailing along the NSR, with time for another trip. If the company opts for the direct option, the last journey occurs on day 344 and, due to harsh sailing conditions, the length of the navigation period along the NSR lasts 19.1 days in addition to the 3.6 days of travel between Rotterdam and Murmansk.

If the use of a hub in Murmansk provides the possibility for the shipowner to use its ships for longer periods to transport more containers, the cost analysis is a little more complex, except in the median case. In the worst and best-case scenario, the use of Murmansk as a hub dramatically increases the cost of a container (Table 5) in both eastbound and westbound directions. The exception is the median case when sailing toward Shanghai. The ice conditions and the length of each journey provide the opportunity to sail for less time but to transport a larger number of containers. Because most of the cost varies according to the length of navigation period, the OPEX, CAPEX, fuel, icebreaker expenditures are lower, explaining the difference between the eastbound median case using a hub versus the option linking directly to Rotterdam. If the shipowner decides to wait for the NSR to reopen due to economic and technical parameters (Table 6a,6b), then the extra cost per container would range from 124 USD and 1028 USD.

To conclude this section of our analysis, we stressed the strong impact ice conditions may have on profitability, as is well known. However, the risk management policy of the shipowner may also provide a different vision according to their interpretation of the data, which may affect their decision to enter the Arctic market.

Compared to the railroad and the SCR

The NSR, railroad and SCR are the main transportation corridors linking the Europe to Asia. For a company wishing to position itself within one of these markets, an analysis of the benefits and shortcomings in term of cost and transit time may be needed.

For a company wishing to position itself in the transportation market between the Asian and European markets, various routes exist with different constraints. To assess the cost of shipping a container between Shanghai and Rotterdam we assumed a vessel with the same specifications as the Venta. We added the Suez Canal fees as a function of the direction, which came to 173,594 USD traveling westbound and 173,160 USD traveling eastbound (Table 3). With a distance of 10,525 nm between the ports (Sea distance, 2019) and the vessel sailing at constant optimal speed, the transit time is 23,1 days. Thus, the vessel would complete 8 journeys westbound and 7 eastbound.

Therefore, the cost of a container from Shanghai to Rotterdam would cost 756 USD and 1123 USD from Rotterdam to Shanghai with knowledge that the vessel would transport 40,176 containers year-round.

According to [START_REF] Rodermann | The enablers and inhibitors of intermodal rail freight between Asia and Europe[END_REF], [START_REF] Lasserre | L'essor des nouvelles liaisons ferroviaires transasiatiques: un décollage récent pour une idée ancienne[END_REF], and [START_REF] Verny | Container shipping on the Northern Sea Route[END_REF], the cost of transporting a container from north China to Western Europe is approximately 2,500 USD with a transit time of 18 days [START_REF] Zhu | The environmental costs and economic implications of container shipping on the Northern Sea Route[END_REF].

Table 7a shows that the NSR is not always more expensive than the SCR, but it is clearly more economically advantageous than the railroad option, except in the worst case and if the vessel is used only during the period of transit along the NSR traveling Eastbound. Our model found that the NSR is already able to provide a more economical solution than the SCR in specific ice conditions (best-case) if the shipowner uses its vessel year-round and does not tranship its cargo in Murmansk.

Regarding the transit time, the railroad is by far the optimal option, with 18 days compared to 23.1 days though the SCR, and the changing transit time of the NSR option except in the westbound direction in the median and best-case if a hub is used. If the transit time of railroad and SCR option is constant, it is definitely not the case for the NSR. Thus, in order to define an average transit time, we considered the number of days the vessel spends sailing divided by the number of journeys. However, looking at the average transit time provided by the north option, the NSR is globally more attractive than the SCR.

Except during extreme sailing periods, sailing along the NSR between the Bering strait and Murmansk takes less than 10 days in all ice scenarios (Figure 5a, 5b). This short transit time raises the question of the value of a hub at each end of the NSR and indicates the viability of the NSR as a potential transport lane with a shorter transit time than the railroad when ice conditions allow for safe navigation.

Discussion and conclusion

In addition to stressing the impact of ice upon the profitability of the NSR, this article highlights the economic impact of various risk management policies, the relevancy of Murmansk as a hub for container transhipping, the impact of depreciation in relation to the period during which a vessel is used, and the benefits and limitations of the NSR compared to the SCR and the railroad option.

Our model attempts to integrate as much as relevant data and parameters as possible. Yet, due to the complexity of this area, we are aware of some limitations. One of the main limitations is the use of a vessel with a TEU capacity equivalent to the vessel used along the NSR. We are aware that vessels sailing between Shanghai and Rotterdam call at numerous ports to load and unload containers. Our model is limited to comparing cost and transit time. Using such an example resulted in a shorter possible transit time without changing the navigation cost. Moreover, using a bigger vessel would involve different cost and thus tackle the question of the cost comparison.

Our results emphasize the importance of POLARIS as a way to define the technical and economic feasibility of navigation as a function of the risk perception of the shipowner.

If the use of an Arctic hub becomes relevant in order to increase the number of containers transported, we find that it also has a negative impact on the transportation cost of a container. Simultaneously, sailing directly to Rotterdam decreases the cost of a container.

Investing in ice class vessels is compulsory for safe, unassisted navigation in polar waters. However, the technical features of ice class vessels may not ease their use in other markets when the NSR is inaccessible. Our analysis highlighted the importance of anticipating such issues for supply chain management given the strong impact on transportation cost, and that additional costs are reduced by the length of the navigation period.

Finally, compared to the SCR and the railroad, the NSR can offer a shorter mean transit time, but this result is highly dependent on the ice conditions. From an economic point of view, the cost of transportation is clearly less expensive along the NSR than via railroad. Furthermore, compared to the SCR, the NSR is able to be cost effective in some cases.

Our analysis is aimed to provide another point of view of the NSR integrating the impact of risk management policy and the use of a hub in accordance with investments made by the Russian government at the Murmansk Transport Hub to reach a capacity of 1 million TEU per year. Yet, given the aforementioned limitations, numerous opportunities for future research remain to further investigate the profitability of the NSR, such as through analysis of the elasticity of the freight rate.

CLARKSONS

Figure 4 :

 4 Figure 4: Navigability risk assessment July 21 st for an IA vessel transiting the NSR. Legend: Red = No go; Orange = Ice-breaker escort; Green = Go. Source: Authors (2019) based on Copernicus -Arctic_Reanalysis_Phys_002_003

Figure 5 :

 5 Figure 5: Sailing duration and allowed navigability periods for a 1A vessel on the Bering-Murmansk route according to the day of departure, for the 25 th , 50 th , and 75 th percentiles of ice conditions of the past 25 years.

  𝐹 𝐴 and 𝐹 𝑀 (𝑉): daily fuel consumption of auxiliary and main engines[ton/day]. 𝐹 𝑀 (𝑉) is a function of the sailing speed 𝑉. • 𝐵 𝑟 𝐴 and 𝐵 𝑟 𝑀 : total fuel cost of the vessel per trip 𝑟 for the auxiliary and the main engines respectively [USD/trip]. • 𝐵 𝑟 : total fuel cost of the vessel per trip 𝑟 for both engines [USD/trip]. • 𝐼𝐵 𝑟 : total NSR fee per trip 𝑟 including transit and pilotage fees, as well as the cost of the use of icebreakers if needed [USD/trip]. • 𝐶 𝑟 : total cost per trip for one vessel 𝑟 including capital cost, operational cost, bunker cost and NSR fees [USD/trip]. 𝐶 𝑇𝐸𝑈 : average total cost per TEU container transported from Shanghai to Rotterdam or from Rotterdam to Shanghai, including the transshipment cost for the option with transshipment [USD/TEU]. • K: total carrying capacity of the vessel [TEU]. • 𝛼 1 , 𝛼 2 : utilization rate of the vessel capacity westbound and eastbound respectively [%].

	• 𝑉 𝑟 1 and 𝑉 𝑟 2 : average sailing speed of the vessel during trip 𝑟 = 1, … , 𝑅 while sailing on the NSR part of the route from Shanghai to Rotterdam (or to Murmansk) and vice-versa respectively [knots]. • 𝑉 𝑟 3 : average sailing speed of the vessel during trip 𝑟 = 1, … , 𝑅 while sailing in open water in both directions [knot]. • 𝑉 𝐷𝑆 : vessel design speed [knot]. • 𝐷 𝑟 1 and 𝐷 𝑟 2 : average NSR distance of trip 𝑟 = 1, … , 𝑅 from Shanghai to Rotterdam (or to Murmansk) and vice-versa respectively [nm]. • 𝐷 𝑟 3 : total average distance of trip 𝑟 = 1, … , 𝑅 in open-water (outside the NSR zones) in both directions, i.e. from Shanghai to Rotterdam (or to Murmansk) and vice-versa [nm]. • 𝑃𝑇: total port time per trip [days]. • 𝑇 𝑟 : total duration of trip 𝑟 including sailing and port times [days]. • 𝑑𝑜𝑑 𝑟 1 and 𝑑𝑜𝑑 𝑟 2 : day-of-departure of the vessel for trip 𝑟 = 1, . . . , 𝑅 from Shanghai to Rotterdam (or to Murmansk) and vice-versa respectively. • 𝐶𝐴𝑃𝐸𝑋 𝑟 and 𝐶𝐴𝑃𝐸𝑋 𝑑 : Capital expenses corresponding to the vessel fixed cost or the chartering cost, per trip 𝑟 or per day respectively [USD/trip] and [USD/day] respectively. • 𝑂𝑃𝐸𝑋 𝑟 and 𝑂𝑃𝐸𝑋 𝑑 : operational costs, including crew, insurance, stores, lubricants, repairs, and maintenance, per trip 𝑟 or per day respectively [USD/trip] and [USD/day] respectively. • 𝐶 𝑏 𝐴 and 𝐶 𝑏 𝑀 : bunker fuel price per ton used for the auxiliary and main engines respectively [USD/ton]. assuming that the vessel sails continuously during the period when sailing is possible even with icebreaker assistance between Shanghai and Rotterdam (or Murmansk) [USD/year]. • 𝐶 𝑇𝐸𝑈 𝑇𝑟𝑎𝑛𝑠 : total cost per TEU container corresponding to transshipping and subcontracting the transportation of transshipped containers from Murmansk to Rotterdam and vice versa [USD/TEU]. This cost corresponds to the option of using the NSR with a transshipment in Murmansk. • • 𝐶 𝑦 : total cost per year including capital cost, operational cost, bunker cost and NSR fees •

Table 1 :

 1

Risk Index Values

Source: Authors based on

[START_REF] Imo | /Circ 1519[END_REF]

Table 2 .

 2 Risk Index Outcome Criteria

RIOSHIP Ice classes PC1-PC7 Ice classes below PC7 and ships not assigned an ice class

	RIO ≥ 0	Normal operation	Normal operation
	-10 ≤ RIO ˂ 0	Elevated operational risk	Operation subject to special consideration
	RIO ≤ -10	Operation subject to special consideration	Operation subject to special consideration
		Source: IMO (2016).

Table 3 :

 3 Economic and technical parameters

		Venta Maersk	Open water & SCR	Railroad
	CAPEX (Mln USD°1	38	38
	Daily CAPEX (USD) 1	6,941	6,941
	OPEX (USD)	6,121	6,121
	TEU Capacity (TEU) 1	3,600	3,600
	Loading factor Eastbound 3	45%	60%
	Loading factor Westbound 3	70%	87%
	GT (Ton) 1	34,882	34,882
	Optimal speed (Kts) 1	19	19
	Main engine power (Kw) 1	19,620	19,620
	Main engine SFOC () 1	170	170
	Auxiliary engine daily fuel consumption (Ton/day)	2000	2000
	Fuel cost (USD / Ton) 1	441.05	441.05
	Time spent in port (days)	2	2
	Icebreaker fees	See Table 4
	Suez Canal fees Eastbound (USD) 4		173,169
	Suez Canal fees Westbound (USD) 4		173,594
	Murmansk Rotterdam freight rate (USD/TEU) 2		1,120
	Rotterdam Murmansk freight rate (USD/TEU) 2		523

Table 4 :

 4 icebreaker fees per zone for an ice class 1A vessel with an exchange rate of 0.149109 Rub for 1 USD(xe converter, 2019)

	Source: Authors based on NSRA (2018)

Table 5a :

 5a TEU cost for Shanghai/Murmansk/Rotterdam with a daily CAPEX of 6,941 USD

			Number of journey	Number of days	TEU LOADED		Average TEU cost
			Westbound	Eastbound	exploited	Westbound	Eastbound	Westbound	Eastbound	CTEU
	25%	HUB	3	3	112.6	7,560	4,860	1,811 USD	1,919 USD	1,865 USD
	50%	HUB	5	4	160.3	12,600	6,480	1,947 USD	1,257 USD	1,602 USD
	75%	HUB	6	5	191.5	15,120	8,100	1,791 USD	998 USD	1,394 USD
						Source: Authors (2019)

Table 5b :

 5b TEU cost for Shanghai/Rotterdam with a daily CAPEX of 6,941 USD

		Number of journey	Number of days	TEU LOADED		Average TEU cost
		Westbound Eastbound	exploited	Westbound	Eastbound	Westbound	Eastbound	CTEU
	25% DIRECT	3	2	111.3	7,560	3,240	1,090 USD	1,183 USD	1,137 USD
	50% DIRECT	4	4	170.2	10,080	6,480	547 USD	1,653 USD	1,100 USD
	75% DIRECT	5	4	187.9	12,600	6,480	820 USD	587 USD	703 USD
					Source: Authors (2019)

Table 6a :

 6a TEU cost for Shanghai/Murmansk/Rotterdam with a variable daily CAPEX

			Number of journey	Number of days	TEU LOADED		Average TEU cost
			Westbound	Eastbound	exploited	Westbound Eastbound Westbound	Eastbound	CTEU
	25%	HUB	3	3	112.6	7,560	4,860	2,101 USD	2,947 USD	2,524 USD
	50%	HUB	5	4	160.3	12,600	6,480	2,103 USD	2,161 USD	2,132 USD
	75%	HUB	6	5	191.5	15,120	8,100	1,915 USD	1,825 USD	1,870 USD
					Source: Authors (2019)

Table 6b :

 6b TEU cost for Shanghai/Rotterdam with a variable daily CAPEX

			Number of journey	Number of days	TEU LOADED		Average TEU cost
			Westbound Eastbound	exploited	Westbound	Eastbound	Westbound	Eastbound	CTEU
	25%	DIRECT	3	2	111.3	7,560	3,240	1,367 USD	1,862 USD	1,614 USD
	50%	DIRECT	4	4	170.2	10,080	6,480	745 USD	1,945 USD	1,345 USD
	75%	DIRECT	5	4	187.9	12,600	6,480	967 USD	880 USD	923 USD
					Source: Authors (2019)

Table 7a :

 7a Cost comparison of NSR, SCR and Railroad

			Worst-case			Median-case			Best-case		SCR	Railroad
		Steady CAPEX	Variable CAPEX	Steady CAPEX	Variable CAPEX	Steady CAPEX	Variable CAPEX
		hub	direct	hub	direct	hub	direct	hub	direct	hub	direct	hub	direct
	Westbound	1,811 USD	1,090 USD	2,101 USD	1,367 USD	1,947 USD	547 USD	2,103 USD	745 USD	1,791 USD 820 USD 1,915 USD	967 USD	756 USD	2,500 USD
	Eastbound	1,919 USD	1,183 USD	2,947 USD	1,862 USD	1,257 USD	1,653 USD 2,161 USD 1,945 USD	998 USD	587 USD 1,825 USD	880 USD	1,241 USD	2,500 USD
							Source: Authors (2019)

Table 7b :

 7b Transit-time comparison of NSR, SCR and Railroad

				NSR
		Worst-case	Median-case	Best-case		SCR	Railroad
		Hub	Direct	Hub	Direct	Hub	Direct
	Westbound	16.4	21.1	16.4	19.3	15.9	19.3	23.1	18
	Eastbound	21.2	23.9	19.6	23.2	19.3	22.8	23.1

  Database, 2018, https://www.clarksons.net/portal DALAKLIS, D., BAXEVANI, E., SIOUSIOURAS, P., 2018, The future of arctic shipping business and the positive influence of the international code for ships operating in polar waters. The Journal of Ocean Technology, Vol. 13, No. 4, 2018 FAURY, O., GIVRY, P., 2017, Evolution of ice class investment attractiveness depending on climatic and economic conditions. Proceedings of the International Association Maritime Economics Conference, 2017, Kyoto, Japan, June 27-30. Paper ID 83. FEDI, L., FAURY, O., GRITSENKO, D. 2018a, The impact of the Polar Code on risk mitigation in Arctic Waters: a 'Toolbox' for underwriters? MaritimePolicy and Management, 45:4, 478-494, doi.10.1080/03088839.2018.1443227.

FEDI, L., ETIENNE, L., FAURY, O., RIGOT-MULLER, P., STEPHENSON, S., CHEAITOU, A., 2018b, Arctic navigation: stakes, benefits and limits of the POLARIS System. The Journal of Ocean

Technology, Vol. 13, N°. 4, 2018

Suez calculator (2019)

Source: Authors (2019)


Marcio Dahia

Hugo Santana

Ernesto Trajano

Geber Ramalho

Carlos Sandroni
email: sandroni@terra.com.br

Giordano Cabral
email: giordano.cabral@lip6.fr

Pat- Terns Using

To Generate

USING PATTERNS TO GENERATE RHYTHMIC ACCOMPANIMENT FOR GUITAR

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

INTRODUCTION

Although its potential use in programs for musical accompaniment and composition, the automatic generation of rhythm has not been much explored in the Computer Music literature. This task is difficult to model due to the lack of formal knowledge on this musical dimension: the musicians explain its rhythmic choices in high level, from abstract criteria such as swing, not being able to supply objective rules that elucidate their decisions in granularity of notes.

Moreover, in contrast to tasks such as harmony generation, which are facilitated by the availability of an extensive bibliography in musical theory, there are just few works on rhythm as accompaniment [START_REF] Baggi | NeurSwing: An Intelligent Workbench for the Investigation of Swing in Jazz. Computer-Generated Music[END_REF] [START_REF] Burton | Genetic Algorithm Utilizing Neural Network Fitness Evaluation for Musical Composition[END_REF]. In fact, the available literature itself indicates that this musical dimension is more associated with subjectivity.

These problems become obvious when we try to mimic the behaviour of instruments in which rhythm has an important role. This is the case of D'Accord Guitar1 [START_REF] Cabral | D´Accord Guitar: an innovative guitar performance system In proc[END_REF], an application developed to assist users in the task of learning how to play guitar, which shows the music been played in real-time in a virtual guitar. This system provides two methods for the rhythmic accompaniment generation: selecting a rhythmic pattern from a list and using it during the whole song, or creating it from scratch by means of a computer keyboard. Neither of these approaches completely satisfies the user needs. Whereas the former is very poor rhythmically and totally different from a human-created accompaniment; the second is extremely timeconsuming.

In this circumstance, automatic generation of rhythmic accompaniment could be used to guarantee good musical results without demanding any effort from the user. This task is one of those implemented by Automatic Accompaniment Systems. These systems generate musical lines (melody, chords, rhythm, etc.) of a given song using its chord grid, the other musicians' performance and the very system's previous performance. Among these systems, we highlight ImPact [START_REF] Ramalho | An Artificially Intelligent Jazz Performer[END_REF], which represents an earlier and successful effort of our research team in creating jazz bass lines in real time, by reusing melody fragments previously played by human musicians.

In this work, we discuss the reuse of the model implemented in ImPact to deal with the rhythmic accompaniment problem, as well as the necessary adaptations to cope with the domain specific features, mainly the system's inputs, musical fragments and output. In order to validate the work, we developed Cyber-João, an agent that generates Bossa Nova rhythmic accompaniment based on rhythmic patterns played by João Gilberto.

The paper is structured as follows. In Section 2, we discuss the complexity of the rhythmic accompaniment generation task. In Section 3, it is given a brief overview of the existing solutions, emphasizing the fragment reuse methodology. In Section 4, we present our model, explaining the most important development steps. In Section 5, we explain the experiment we made and the obtained results. Finally, in Section 6, we point out some conclusions and future works.

MODELING RHYTHMIC ACCOMPANIMENT

Generating rhythmic accompaniment is a difficult problem for several reasons. First, the accompaniment agent's environment is complex, since it is dynamic, non-deterministic, continuous and non-episodic [START_REF] Russell | Artificial Intelligence: a modern approach[END_REF]. If the accompaniment must be performed in real time, the task is even harder. Second, rhythmic accompaniment is under constraint, since although there are musical restrictions to guide the musicians; they are not enough to establish the rhythm to be played. In fact, a musician can play completely different rhythms, all of them acceptable.

Third, knowledge formalization is another problem, since musicians are often unable to explain precisely why they decide to play certain notes instead of other ones. This is particularly difficult in rhythm generation. In fact, contrary to the large literature on harmony and counterpoint and their use by computer systems, there are few works describing rhythm choices, most of them applied to drums [START_REF] Baggi | NeurSwing: An Intelligent Workbench for the Investigation of Swing in Jazz. Computer-Generated Music[END_REF] [START_REF] Burton | Genetic Algorithm Utilizing Neural Network Fitness Evaluation for Musical Composition[END_REF]. Rhythm generation seems to be rather intuitive than formally justifiable.

STATE OF ART

There are two major approaches to handle the automatic accompaniment generation problem: attempting to develop a computational model to generate notes from scratch, e.g., using grammars [START_REF] Johnson-Laird | Jazz Improvisation: A Theory at the Computational Level In[END_REF], or creating new accompaniments by appending music fragments, retrieved from a library, to one another. We have adopted the second approach whose advantages we describe next.

Fragment reuse

The motivation of reusing fragments is fourfold [START_REF] Ramalho | An Artificially Intelligent Jazz Performer[END_REF]. First, it minimizes the formalization problem, described in section 2, due to the fact that the fragments by themselves embody a certain musical knowledge. Second, fragment reuse is a scalable approach, since it is possible to use the same process to any instrument and style. Third, this approach improves expressiveness, since, by reusing fragments directly captured from a human musician, performance nuances can be taken into account. Fourth, this is a very natural approach to the rhythmic accompaniment problem; since it is very common practice to learn a rhythm by assimilating its most important rhythmic patterns [START_REF] Sandroni | O Olhar do Aprendiz: Observações sobre a prática do violão popular no Brasil, fartamente documentada por exemplos em partitura[END_REF].

However, in order to properly reuse fragments, there are five main topics that should be considered: Should one use fixed-length or variable-length fragments? Using fragments of fixed length, makes the appending of fragments easier, however, it is not musically plausible;

What is the fragments granularity? The more finegrained the fragment is, the more responsive the system can be, although, it can diminish the musical continuity;

What kind of description is necessary to index the fragments? The more attributes exist (e.g., tempo, density, dissonance, etc.), the more precise will be the choice of the fragments, although it will increase the dependency of style-specific knowledge and restrict the insertion of new fragments in the library; Which are the best retrieval criteria? A rich description requires a more powerful technique (such as similarity measures) than a simple one. For example, a random choice does not require any kind of description;

How to modify a fragment towards a better fit in the new context? Complex adaptations are hard to implement since the various characteristics of a given fragment are interdependent.

In the following, we discuss how two successful systems addressed these questions.

ImPact

The ImPact system [START_REF] Ramalho | An Artificially Intelligent Jazz Performer[END_REF] simulates a bass player. It deals with the problems described in section 2 by conceiving an innovative knowledge-intensive agent whose environment is the chord grid, its previous execution and the other musicians' performance.

It reuses 256 bass lines fragments with variable lengths, corresponding to typical chord sequences, such as II-V and II-V-I. Fragments are retrieved using a Case-Based Reasoning approach [START_REF] Kolodner | Case-Based Reasoning[END_REF] supported by a rich description of the environment and the fragments' musical properties. Production Rules [START_REF] Russell | Artificial Intelligence: a modern approach[END_REF] are used to determine the musical properties the retrieved fragments are supposed to exhibit. The retrieval strategy, coupled with the rich description described above, generates excellent musical results. However, this approach is highly domain-dependent and difficult to implement. Regarding the adaptation of the retrieved fragments, some basic mechanisms (transposition, note deletion and insertion, etc.) are provided.

Band-in-a-box

Band-in-a-Box2 is a broadly used commercial tool for automatically creating accompaniment and solo to electric guitar, piano, bass, drums and strings in a large number of styles (although the user may create his/her own ones). It has a number of musical fragments (up to 1620 per style) of different length (1 to 4 measures) using single chord granularity. In Band-in-a-box, there is no attributes concerning musical property of the fragments, just environment ones. Concerning the retrieval criteria, the software uses a random choice biased by user-entry weights to each fragment; using a simple set of rules to restrict the group of fragments that disagree with the environment attributes. For instance, there are some fragments that can only be played in the beginning of the song; others are supposed to be played in the end, and so on. Just transposition adaptation is provided.

OUR MODEL

Although the Band-in-a-Box approach is very attractive because of its simplicity and flexibility, we were most interested in musical plausibility, and the ImPact system was more qualified regarding this aspect.

In order to evaluate in what extent ImPact approach could be adapted to the automatic generation of guitar rhythmic accompaniment, we chose a specific musical style: Bossa Nova. The advantages of choosing such a well-known and documented style is to benefit from the knowledge concerning rhythmic patterns description [START_REF] Garcia | Bim Bom: A contradição sem conflitos de João Gilberto[END_REF], as well as to better evaluate the system performance. In this context, we decided to reuse rhythmic fragments played by João Gilberto, since they are the most representative ones in Bossa Nova [START_REF] Sandroni | O Olhar do Aprendiz: Observações sobre a prática do violão popular no Brasil, fartamente documentada por exemplos em partitura[END_REF].

Due to the change of instrument (from bass to guitar), style (from Jazz to Bossa Nova) and environment (from ensemble to voice-and-guitar), the main implemented modifications of the original ImPact were: new library of musical fragments, new attributes of these fragments, new rules to improve the fragments retrieval and new perceptions (acquired from melody). It is important to emphasize that some of these new elements are difficult to elicit (as compared to the case of Jazz bass lines) due to the poor formalization of rhythmic accompaniment for guitar.

Rhythmic fragments

The task of choosing Bossa Nova rhythmic fragments was simplified by two musicology works [START_REF] Garcia | Bim Bom: A contradição sem conflitos de João Gilberto[END_REF] [START_REF] Sandroni | O Olhar do Aprendiz: Observações sobre a prática do violão popular no Brasil, fartamente documentada por exemplos em partitura[END_REF]. They transcribed and analyzed João Gilberto's most important rhythmic patterns and highlighted some important features:

All patterns last two measures (in 2/4 signature); Just two kinds of events are allowed (one produced by the thumb and the other, produced by forefinger, middle finger, and ring finger together, which we call, from now on, "plucking block");

Several patterns anticipate their first event producing syncopation, an important rhythmic characteristic of Bossa Nova style.

There are four groups of patterns: the cyclic, beginning, special and fill-in, as depicted in Figure 1 (thumb in the lower clef and plucking block attacks in upper one);

There is a clear difference in performance of slow Bossa Nova songs (less than 120 quarter notes per minute) and faster ones, some patterns being forbidden to be used in the former. Based on the above considerations, we decided that our rhythmic patterns would have fixed length and twomeasure granularity. For the same reason, we did not implemented adaptations on the Bossa Nova patterns: they will be reused exactly as played by João Gilberto.

Each pattern is represented by a small but effective set of attributes. They are of two kinds: environmental and musical ones. Environmental attributes describe the context where the pattern has been used. They are:

Harmonic rhythm, indicating how harmony (chords) changes in a given period of time (e.g. one or two measures). This attribute can have 15 different values ranging from a single chord lasting two 2/4 measures to four chords (one per beat);

Tempo, which can assume 2 values: "slow" (< 120 quarters per minute) or "fast".

Musical attributes describe the pattern's musical properties, i.e., its characteristics. They are:

Beginning, a binary attribute pointing out whether a pattern started at the down beat;

Fill-in, binary attribute indicating whether the pattern has been used as a "fill-in accompaniment", i.e., fragments commonly used when there is no melody been sung, or in turnarounds and turn backs.

Usage, determining how frequently the pattern has been used. The values range from 5 (maximum usage) and 1 (minimum usage);

Density, describing the number of musical events in each pattern's measure. The possible values are "High", "Medium", and "Low". Table 1 shows an example of rhythmic pattern and its description. We have identified and indexed, with the help of experts and the literature [START_REF] Garcia | Bim Bom: A contradição sem conflitos de João Gilberto[END_REF] [START_REF] Sandroni | O Olhar do Aprendiz: Observações sobre a prática do violão popular no Brasil, fartamente documentada por exemplos em partitura[END_REF], 21 patterns in the library.

Retrieval technique

Following the ImPact approach, the retrieval technique consists in a mixed use of Rule-Based and Case-Based Reasoning. The former is used to extract from the environment (in our case, the chord grid and the melody) characteristics that suggest a musical intention (patterns' musical properties), as exemplified in Figure 2. To achieve these rules, we used the traditional method of knowledge acquisition [START_REF] Russell | Artificial Intelligence: a modern approach[END_REF] in which we interviewed specialists obtaining, after analysis, 6 rules that were consensus for all of them. Case-Based Reasoning is employed to effectively choose the best pattern in the library (case base).

In order to improve the retrieval, all attributes are weighted from 5 to 1, according to their importance, again obtained through specialists, as normally used in Case-Based systems. The query is performed by knearest neighbors [START_REF] Kolodner | Case-Based Reasoning[END_REF].

Rhythmic Pattern

Environment

EXPERIMENTS AND RESULTS

In order to analyze the real effectiveness of our approach, we have implemented Cyber-João. Also, to improve this analysis, we have implemented two other systems (less complex than the former): Crazy-João and João-in-a-Box. The first one selects the patterns to be used in the song by random choice; it is the baseline of our experiment. The second one, use the same retrieve criteria found in Band-in-a-Box, which is random choice bounded by weights and constrained by rules. The great benefit about these two new approaches is that they are not related with the style and demand little programming effort, instead of the approach used in ImPact/Cyber-João. So, we evaluated here if a knowledge intensive approach is really better in this case.

Thanks to modularity, it was possible to reuse a great amount of Cyber-João's code in implementation of Crazy-João and João-in-a-Box. However, it is important to note that there is a subtle difference on the effect of the set of rules between Cyber-João and João-in-a-Box. Whereas the former acts on the musical properties of the pattern being retrieved, the second acts directly in the rule base, restricting the groups to be used in a given moment (like Band-in-a-box).

We used four classical Bossa Nova songs: Chega de Saudade, Desafinado, Insesatez and Lígia. The election of the songs obeyed two criteria: Availability of a goodquality melody in MIDI format and the tempo of the songs (the two first ones are considered fast, while the other two, slow ones). Each song was generated by each three systems, resulting in a corpus of twelve samples. The corpus was blinded and presented to six evaluators, all of them, Bossa Nova musicians. They answered to a questionnaire in which they had to point out a score (among bad, acceptable, good, and excellent) for each sample and then, the best version for each song (ties were allowed).

Table 2, shows the score summarization grouped by system. Based on this data, we can perceive a clear difference between the Crazy-João results and the other's. While less than 9% of the evaluations were at least good for this system, the others received at least more than 66%. Obviously, as one could imagine, the use of random choice to select the rhythm patterns in the Bossa Nova style is completely discouraged. The Table 3 summarizes the results of the best version for each song. There were three ties: two in Desafinado and one in Insensatez, so the sum of the total goes to 27 rather than 24. The results show that Cyber-João was evaluated as the best version more than 62% of the times; almost two times Joao-in-a-box did.

System

Song

Crazy-João João-in-a-box

CONCLUSIONS

In this paper, we presented a model for generating the rhythmic accompaniment for guitar, based on the reuse of previously stored rhythmic fragments. To validate this model we implemented Cyber-João, a system that plays Bossa Nova. It was coded in C++ and is fully integrated to D'Accord Guitar. It takes as input a dv3 file (D'Accord Guitar format) containing the melody and chord grid of a given song. Reusing a rhythmic pattern library, Cyber-João generates the correspondent accompaniment. It is important to note however, that this is a general approach to the rhythmic generation problem. According to musicians' analysis of the preliminary outcome, Cyber-João exhibits excellent results: it was evaluated as good and excellent in 75% of the cases.

We are now coding a large corpus of Bossa Nova songs in order to provide a more precise evaluation of Cyber-João. In this perspective we intend to develop a feedback support system to help experts to judge and comment agent's choice and automatically generating statistical results, which can be used to improve the agent's knowledge.

The preliminary results encourage us to reuse the same approach in other musical styles. This is reinforced by the fact that the rhythmic fragment attributes in Cyber-João library are quite generic. Besides, the combination of this approach with an automatic extractor of rhythmic pattern [START_REF] Santana | VexPat -An Analysis Tool for the Discovery of Musical Patterns[END_REF] would speed up the development of new guitar accompaniment systems.

Figure 1 .

 1 Figure 1. Examples of rhythmic pattern groups found in Bossa Nova.

Table 1 .Figure 2 .

 12 Figure 2. Examples of two Cyber-João's Rules

Table 2 .

 2 Example of a pattern and its attribute values.

		Bad Acceptable Good Excellent
	Crazy-João	12	10	2	0
	Cyber-João	2	4	7	11

Table 3 .

 3 Results of the best version for each song.

http://www.daccordmusic.com

Band-in-a-Box is a trademark of PG. Music Inc. (http://www.bandinabox.com) all information obtained from user manual and using the software.


Carlos Pérez-Sancho

José M Iñesta
email: inesta@dlsi.ua.es

Jorge Calera-Rubio

STYLE RECOGNITION THROUGH STATISTICAL EVENT MODELS

The automatic classification of music fragments into styles is one challenging problem within the music information retrieval (MIR) domain and also for the understanding of music style perception. This has a number of applications, including the indexation and exploration of music databases. Some technologies employed in text classification can be applied to this problem. The key point here is to establish something in music equivalent to the words in texts. A number of works use the combination of intervals and duration ratios for this purpose. In this paper, different statistical text recognition algorithms are applied to style recognition using this kind of melody representation, exploring and comparing their performance for different word sizes.

INTRODUCTION

The automatic machine learning and pattern recognition techniques, successfully employed in other fields, can be also applied to music analysis. One of the tasks that can be posed is the modelization of the music style. Immediate applications are the classification, indexation, and content-based search in digital music libraries, where digitised (MP3), sequenced (MIDI) or structurally represented (XML) music can be found. For example, the computer could be trained in the user musical taste in order to look for that kind of music over large musical databases.

A number of recent papers explore the capabilities of machine learning methods to recognise music style, either using audio or symbolic sources. Among the first, for example, Pampalk et al. [START_REF] Pampalk | Exploring music collections by browsing different views[END_REF] use self-organising maps (SOM) to pose the problem of organising music digital libraries according to sound features of musical themes, in such a way that similar themes are clustered, performing a content-based classification of the sounds. Whitman et al. [START_REF] Whitman | Artist detection in music with minnowmatch[END_REF] present a system based on neural networks and support vector machines able to classify an audio fragment into a given list of sources or artists. Also Soltau et al. [START_REF] Soltau | Recognition of music types[END_REF] describe a neural system to recognise music types from sound inputs.

Dealing with symbolic data, we can find a recent work by Cruz et al. [START_REF] Cruz | Musical style identification using grammatical inference: The encoding problem[END_REF], where the authors show the ability of grammatical inference methods for modeling musical style. A stochastic grammar for each musical style is inferred from examples, and those grammars are used to parse and classify new melodies. In [START_REF] Ponce De León | Feature-driven recognition of music styles[END_REF] the authors compare the performance of different pattern recognition paradigms to recognise music style using descriptive statistics of pitches, intervals, durations, silences, etc. Other approaches like hidden Markov models [START_REF] Chai | Folk music classification using hidden markov models[END_REF] or multi layer feed forward neural networks [START_REF] Buzzanca | A supervised learning approach to musical style recognition[END_REF] have been used to pose this problem.

Our aim is to explore the capabilities of text categorization algorithms to solve problems relevant to computer music. In this paper, some of those methods are applied to the recognition of musical genres from a symbolic representation of melodies. Jazz and classical music styles have been chosen as an initial benchmark for the proposed methodology due to the general agreement in the musicology community about their definition and limits.

METHODOLOGY

Data set

Experiments in section 3 were performed using a corpus of MIDI files collected from different web sources, without any processing. It is a quite heterogeneus corpus, not specifically created to test our system. The melodies are real-time sequenced by musicians, without quantization. The corpus is made up of a total of 110 MIDI files, 45 of them being classical music and 65 being jazz music. Each MIDI file contains a monophonic sequence written in the 4/4 meter. The length of the corpus is around 10,000 bars (40,000 beats). Classical melody samples were taken from works by Mozart, Bach, Schubert, Chopin, Grieg, Vivaldi, Schumann, Brahms, Beethoven, Dvorak, Haendel, Paganini and Mendelssohn. Jazz music samples were standard tunes from a variety of well known jazz authors including Charlie Parker, Duke Ellington, Bill Evans, Miles Davis, etc.

Encoding

Since we are trying to use text categorization approaches, there is a need to find an appropriate encoding, something like music words, that captures relevant information of the data and is suitable for that kind of algorithms to be applied.

One possible encoding is the one proposed by Doraisamy and Rüger [START_REF] Doraisamy | Robust polyphonic music retrieval with n-grams[END_REF], that make use of pitch intervals and inter onset time ratios (IOR) to build series of symbols of a given length. We will name these series ¢ -words (we will use also just "words" for short in this document), due to the analogy to text we are trying to establish. A se-fH 0d 0i AH fH0d 0d0i 0iAH fH0d0i 0d0iAH quence of ¢ notes generates ¢ ¡ ¢ pitch intervals and ¢ £ ¢ IOR 1 that are represented together as a word with ¤ ¢ ¥ ¦¤ symbols. Note that all the pitches and durations contained in the ¢ -word are represented in a relative way (intervals and ratios) with respect to the pitch and duration of the first note, giving more generality to the coded information, which is reported to be useful for music classification [START_REF] Cruz | Musical style identification using grammatical inference: The encoding problem[END_REF][START_REF] Chai | Folk music classification using hidden markov models[END_REF].

Using this encoding, all the music words of order ¢ are extracted from the melody track of each MIDI file. If the sequence has § notes, § ¨ ¢ © ¢ is the number of ¢ - words can be extracted from it. Thus, each melody in our database is transformed into a sequence of words in the form ! #" ! #" %$ &$ '$ ( ) 10 32 1" ! 40 32 5" 76 8 2 90 @ A"

)B A"

where C represents the position of the C ED GF note in the sequence. See Fig. 1 for an example of the coding. Using this scheme, a melody can be considered as a set of musical ¢ -words in the same way that a text document is considered for classification as a set of words.

For obtaining the codes, a non-linear mapping from numerical values to letters is applied. Intervals are mapped into a set of 53 letters, where '0' represents the unison, and the IOR into a set of 21 letters, where 'Z' represents the IOR = 1. This is also useful to quantize the MIDI sequence and also to impose limits to the permitted ranges for intervals and IOR (see [START_REF] Doraisamy | Robust polyphonic music retrieval with n-grams[END_REF] for details).

In order to illustrate the distribution of codes for both styles, histograms of intervals and IORs are displayed in Fig. 2. Note the different frequencies for each style, that are in the basis of the recognition system.

Also, stop words are used to segmentate the melody into musical phrases. For that, a simple criterion has been considered: when a silence equal or longer than a whole note is found, no word is coded across it. This implies that ¢ H ¢ ¢ -words less than the amount given above are extracted for each time that a long silence is found.

Word lengths

In order to test the classification ability of different word lengths, ¢ , a range for ¢ PI ¤ RQ TS UQ (V 6

has been established. W Jazz Classical Total % X Y `X The shorter ¢ -words are less specific and provide more general information and, on the other hand larger ¢ -words are maybe more informative but the models based on them will be more difficult to train. The vocabulary of each length has a size s t 0 s vu xw y cS ¤ ¢ f 0 32 1"

words. In Table 1 the number of words that have been extracted from the training set for each length is displayed. From left to right: the total number of different words found, their percentages on the vocabulary size, and the number of different words for jazz and classical music are displayed.

Naive Bayes Classifier

The naive Bayes classifier, as described in [START_REF] Mccallum | A comparison of event models for naive bayes text classification[END_REF], has been used. In this framework, classification is performed following the well-known Bayes' classification rule. In a context where we have a set of classes u

" Q cQ $ &$ '$ Q T c R ,
a melody is assigned to the class p with maximum a posteriori probability (MAP), in order to minimize the probability of error:

w G s u w G w s w G (1)
where w G is the a priori probability of class , w s

is the probability of being generated by class , and w G u ¢¡ R B A" w G w s . Since w is just a nor- malization factor to ensure that ¡ R B A" w s u ¢ we can just ignore it and assign to the class which maximizes w G w G s .

Our classifier is based on the naive Bayes assumption, i.e. it assumes that all words in a melody are independent of each other, and also independent of the order they are generated. This assumption is clearly false in our problem and also in the case of text classification, but naive Bayes can obtain near optimal classification errors in spite of that [START_REF] Domingos | Beyond independence: conditions for the optimality of simple bayesian classifier[END_REF]. To reflect this independence assumption, melodies can be represented as a vector

u ¤£ G " Q T @Q $ &$ &$ Q ( ¥ 4 §¦ , where each component D I ©¨Q ¢ 6
represents whether the word D appears in the document or not, and s s is the size of the vocabulary. Thus, the class-conditional probability of a document w s is given by the probability distribution of words D in class , which can be learned from a labelled training sample using a supervised learning method.

Multivariate Bernoulli model

In this model, melodies are represented by a binary vector

u £ " Q ( Q $ '$ &$ Q T ¥ 4 ¦ ,
where w D s are the class-conditional probabilities of each word in the vocabulary, and these are the parameters to be learned from the training sample.

Given a labelled sample of melodies u " Q ( @Q $ '$ &$ Q T 0 6

, Bayes-optimal estimates for probabilities w D s can be easily calculated by counting the number of occurrences of each word in the corresponding class:

w D s u ¢ © § D ¤ © ¦ § (3)
where § D is the number of melodies in class p containing word D , and § is the total number of melodies in class . Also, a Laplacean prior has been introduced in the equation above to avoid probabilities of 0 or 1. Prior probabilities for classes w G can be estimated from the training sample using a maximum likelihood estimate:

w G u § s Hs (4)
Classification of new melodies is performed then using Eq. 1, which is expanded using Eqs. 2 and 4.

Multinomial model

This model takes into account word frequencies in each melody, rather than just the occurrence or non-occurence of words as in the multivariate Bernoulli model. In consequence, documents are represented by a vector, where each component D is the number of occurrences of word D in the melody. In this model, the probability that a melody has been generated by a class p is the multinomial distribution, assuming that the melody length in words, s s , is class-independent [7]:

w s u w Ts s s s ¥ 4 D B #" w D s ©! " D (5)
In this case, Bayes-optimal estimates for class-conditional word probabilities are:

w D s u ¢ © § D s s '© #¡ ¥ 4 $ B A" § $ (6)
where § D is the sum of occurrences of word D in melodies in class . Class prior probabilities are also calculated us- ing Eq. 4.

Feature selection

The methods explained above use a representation of musical pieces as a vector of symbols. A common practice in text classification is to reduce the dimensionality of those vectors by selecting the words which contribute most to discriminate the class of a document. A widely used measure to rank the words is the average mutual information (AMI) [START_REF] Cover | Elements of Information Theory[END_REF].

For the multivariate Bernoulli model, the AMI is calculated between (1) the class of a document and (2) the absence or presence of a word in the document. We define % as a random variable over all classes, and & D as a ran- dom variable over the absence or presence of word D in a melody, & D taking on values in ' D I ¨Q ¢ 6

, where ' D u ïndicates the absence of word D and ' D u ¢ indicates the presence of word D . The AMI is calculated for each D

as 2 : w % )( & D u 0 1 B A" 1 2 " 43 65 47 98 " A@ w Q A' D CB ED GF w G @Q A' D w G w H' D ( 7
)
where w is the number of melodies for class p di- vided by the total number of melodies; w I' D is the num- ber of melodies containing the word D divided by the total number of melodies; and w G Q A' D is the number of melodies in class having a value ' D for word D divided by the total number of melodies.

In the case of the multinomial model, the AMI is calculated between (1) the class of the melody from which a word occurrence is drawn and (2) a random variable over all the word occurrences, instead of melodies. In this case, Eq. 7 is also used, but w G is the number of word occur- rences appearing in melodies in class divided by the total number of word occurrences, w H' D is the number of occurrences of the word D divided by the total number of word occurrences, and w @Q ' D is the number of occur- rences of word D in melodies with class label , divided by the total number of word occurrences.

RESULTS

The style recognition ability of the different word sizes has been tested. For each model, the naive Bayes classifier has been applied to the words extracted from the melodies in our training set. The experiments have been made following a leave-one-out scheme: the training has been constructed with all the melodies but one, kept for test. After training the model, the words in the test melody are extracted and used to classify it. The presented results are the percentage of successfully classified melodies.

The evolution of the classification as a function of the significance of the used information is presented in the graphs in figure 3. For this, the words in the training set have been ordered according to two different criteria:

(1) their frequencies in the training set, and (2) their AMI value. After that, experiments using only the best situated words (s s in the graphs) have been performed.

Note that the results were not conclusive in terms of different statistical distributions or word order, since all the methods performed comparatively. There is a tendency of the Bernoullis to classify better for small values of s s while multinomials seem to provide better results for larger s s .

Table 2 shows the best results obtained in the experiments. The best accuracy was obtained for the word size ¢ u ¤ , reaching a 93.25% of successful style identifica- tion. Large ¢ -words only perform well (above 80%) for very small s s values, and get worse rapidly for larger va- lues. This preference for little specific information points to the fact that the method is indeed able to classify but maybe the training set is small, and the results can be improved for larger models with more training melodies.

Also the values for precision and recall have been studied. Note that the recall figures get very low as ¢ increases, being the cause of the lower classification rates obtained for large words. In fact, the tendency of lengths ¢ Hu ¤ Q TS is to get low percentage rates when s s increases that are due to low recall and very high precision values: there are a lot of unclassified melodies, but the decisions taken by the classifier are usually very precise. It can be said that the classifier learns very well but little. This fact also reflects the need of a larger training set.

Finally, we have compared our results to those obtained by our research group with the same training set, but using melodic, harmonic and rhythmic statistical descriptors. They are fed into well-known supervised classifiers like, ¡ -nearest neighbours ( ¡ -NN) or a standard Bayes rule (see [START_REF] Ponce De León | Feature-driven recognition of music styles[END_REF] for details). In those experiments, the best recognition rates obtained when extracting the descriptors from the whole melody were 91.0% for Bayes and 93.0% for ¡ -NN, after a long study of the parameter space and the descriptor selection procedures. Thus, the first results obtained under this new approach are very encouraging.

CONCLUSIONS

In this paper, the feasibility of using text classification technologies for music style recognition has been tested. The first results of our research in this particular application have been presented and discussed. The models based on 2-words had the best performance, reaching a 93.25% of successful style recognition. Larger word lengths have provided also good results using small vocabulary sizes. In these cases, the precision of the classifiers are good or even perfect but the recall figures are very low, due to a lot of unclassified melodies. This fact points to a lack of training data. It is very likely that longer words would improve their performance with larger corpora. The various statistical distributions tested did not present significant differences in classification.

The results have been compared to those obtained by other description and classification techniques, providing similar or even better results. We are convinced that an increment of the data available for training will improve the results clearly, specially for larger ¢ -word sizes, were the method has proved to be very accurate, but lacks retrieval power.

In the further work, more data and styles will be included in our experimental framework and other classifiers, based on the symbolic representation of music, will be investigated.

Figure 1 .

 1 Figure 1. An example of short melody and the coding of all the possible 2-(top), 3-(middle) and 4-words (bottom) in it.

Figure 2 .

 2 Figure 2. Histograms: (top) normalized frequencies of intervals in the training set; (bottom) frequencies of inter onset ratios. In the abcises, the coding letters are represented.

  word D appears at least once in the melody. Using this approach, each class follows a multivariate Bernoulli distribution:

Figure 3 .

 3 Figure 3. Evolution of style recognition percentage in average for both classes and different word sizes. The four plots in each graph represent: mvB multi-variate Bernoulli, mn multinomial, (f) words sorted by frequencies, (AMI) words sorted by AMI.

Table 1 .

 1 Number

	2	425	485	548	49.2
	3 4	4883 6481	3840 6209 12501 a cb d fe hg i pd cq Rr 7903 0.638

of words in the training sets for the different word lengths: number of different words in each style, total of different words in the corpus, and percentage on the vocabulary size.

Table 2 .

 2 Best results in classification percentages obtained in the experiments. For each word length value, ¢ , the table shows, from left to right: best classification, size of vocabulary used for it, and precision and recall figures for both styles, also in percentage.

	Best classification % W	Jazz X Y `X Prec. Recall Prec. Recall Classical
	2	93.25	300	94	95	93	91
	3	86.78	50	79	57	97	71
	4	90.62	20	50	9	100	58

The last IOR is computed using the duration of the last note while the others use the time between note onsets. This permits to give more information to a

2-word than just one interval.

The convention P RQ §S UT VP XW YP was used, since àQ §S UT bdc eP as fc eP .

Acknowledgment

This work was supported by the Spanish CICYT project TIRIG, code TIC2003-08496-C04.