Keywords: Shared Autonomous Mobility, First-Last Mile Service, Vehicle Routing, Node Embeddings

Autonomous vehicles are anticipated to revolutionize ride-sharing services and subsequently enhance the public transportation systems through a first-last mile transit service. Within this context, a fleet of autonomous vehicles can be modeled as a Dial-a-Ride-Problem with certain features. In this study, we propose a holistic solving approach for this problem, which combines the mixed-integer linear programming formulation with a novel graph dimension reduction method based on the graph embedding framework. This latter method is effective since accounting for heterogeneous travel demands of the covered territory tends to increase the size of the routing graph drastically, thus rendering exact solving of small instances computationally infeasible. An application is provided for the real transport demand of the industrial district of "Vallée de la Chimie" in Lyon city, France. Instances involving more than 50 transport requests, and 10 vehicles could be easily solved. Results suggest that this method generates routes of reduced nodes with a lower vehicle kilometers traveled compared to the constrained K-means based reduction. Reductions in terms of GHG emissions are estimated to be around 75% lesser than the private vehicle mode in our applied service. A sensitivity analysis is also provided.

INTRODUCTION

The urban expansion in most cities around the world followed an automobile-oriented pattern, leading to the emergence of several low-density metropolitan areas, thus increasing the overall infrastructure costs for public transportation (PT) (Sinha, 2003 [35]). Since then and due to this reason, PT systems have been relegated to a secondary role behind private car use in urban mobility. The PT cover for low-density areas and commercial and industrial districts outside the city is limited. Shared mobility, which is the shared use of vehicles, bicycles, and other means of transport to access PT networks, started to appear to be a viable solution to this issue, known as the first-and last-mile commute. The concept of shared mobility is not novel in itself, and could be traced back to the 1990s where it was popular, and even to the year of 1948 for the first car-sharing program (Shaheen & Chan, 2016 [36]). Yet, the major shift in shared mobility is still expected by many to happen with the advent of shared autonomous vehicles (SAV). Several AV manufacturers and service transportation provider companies have heavily invested and adopted specific ride-sharing plans, e.g., Waymo in Phoenix area (Waymo, 2020 [41]), Jaguar Land Rover (Jaguar Land Rover, 2020 [START_REF] Land | Article titled "Jaguar Land Rover reveals Project Vector autonomous ride-share vehicle[END_REF]), and eventually Amazon, a fresh new competitor in this market share (Amazon, 2020 [START_REF] Amazon | Article titled "Amazon Buys Autonomous Taxi Company Zoox. Look Out, Uber and Lyft[END_REF]).

The factors making SAV an attractive transit mode are mainly economic, for both sides of customers and PT and transportation network entities. Due to lower operational and investment costs over fixed routes, transportation companies could propose services at fair prices with a higher frequency. Higher customer satisfaction and time reductions may be equally obtained compared with other transit modes such as parkand-ride and active modes. Another argument in favor of SAV lies in the environmental sustainability of this technology, which is mainly due to the application of electric vehicles in SAV services. Autonomous fleets could reduce GHG emissions by up to 73% compared to conventional taxi fleets (Bauer et al., 2018 [3]). It was shown that each SAV could replace around 11, respectively from 5 to 10 privately owned vehicles, with an increase of 10%, resp. from 6 to 89% travel distance via agent-based simulations of the city of Austin, Texas [START_REF] Fagnant | The travel and environmental implications of shared autonomous vehicles, using agent-based model scenarios[END_REF] [START_REF] Fagnant | The travel and environmental implications of shared autonomous vehicles, using agent-based model scenarios[END_REF]), resp. Lisbon (International Transport Forum, 2015 [START_REF]Urban mobility system upgrade: How shared self-driving cars could change city traffic[END_REF]). The existence of empty trips justifies this latter increase. All these favorable reports led to a resurgence of small-size experimentations of SAV services in Europe, the U.S., and globally. Just in Lyon city in France, where the case study of this paper is located, there are currently three experimentations: Navya shuttle buses in the Confluence area, around Groupama stadium, and Mia buses in the Meyzieu-Décine suburb area. Therefore, there is a great need of efficient design models for the short-time deployment of SAVs, especially to handle the first-last mile transit issue (see [START_REF] Hyland | Taxonomy of shared autonomous vehicle fleet management problems to inform future transportation mobility[END_REF] [START_REF] Hyland | Taxonomy of shared autonomous vehicle fleet management problems to inform future transportation mobility[END_REF] for a taxonomy of SAV fleet management problem classes to accompany this current mobility shift).

A critical component of the design of an SAV service is the vehicle assignment or the process of matching customer requests to vehicles. Most SAV approaches rely on rule-based assignment methods, e.g., [START_REF] Gurumurthy | Analyzing the dynamic ride-sharing potential for shared autonomous vehicle fleets using cellphone data from Orlando, Florida[END_REF] [START_REF] Gurumurthy | Analyzing the dynamic ride-sharing potential for shared autonomous vehicle fleets using cellphone data from Orlando, Florida[END_REF]. Optimization models are almost not used here. This is because SAV studies are mostly on-demand systems, that are dynamic systems that require solving approaches that are computationally cost-efficient and easy to implement (Narayanan et al., 2020 [30]). On the other hand, SAV models that are reservation-based, or in other terms static systems that could be solved beforehand, are relying in general on optimization. However, they are quite few in number, e.g., [START_REF] Levin | Congestion-aware system optimal route choice for shared autonomous vehicles[END_REF] [START_REF] Levin | Congestion-aware system optimal route choice for shared autonomous vehicles[END_REF], [START_REF] Ma | Designing optimal autonomous vehicle sharing and reservation systems: A linear programming approach[END_REF] [START_REF] Ma | Designing optimal autonomous vehicle sharing and reservation systems: A linear programming approach[END_REF]. Both [START_REF] Levin | Congestion-aware system optimal route choice for shared autonomous vehicles[END_REF] and [START_REF] Ma | Designing optimal autonomous vehicle sharing and reservation systems: A linear programming approach[END_REF] proposed a linear programming model to modelize an SAV fleet. In this study, we propose using the famous routing problem of the Dial-a-Ride-Problem (DARP), which is derived from the classical Vehicle Routing Problem (VRP) with additional constraints to account for pickup and drop-off requests. VRP and DARP are both computationally intractable and can be pinned down as mixed-integer linear programming models. According to [START_REF] Ho | A survey of dial-a-ride problems: Literature review and recent developments[END_REF] [START_REF] Ho | A survey of dial-a-ride problems: Literature review and recent developments[END_REF], the largest instance solved to optimality for the basic DARP with time windows is up to 8 vehicles and 96 requests, which is quite small for practical deployment of an SAV service. Therefore, a mechanism has to be found in order to reduce the dimension of the routing graph. To address this research gap, we develop a new reduction method based on the graph embedding framework, specifically around the node2vec algorithmic framework (Grover and Leskovec, 2016 [14]), which will be seen later. The problem we solve is a reservation-based SAV service.

A second objective is to design an SAV service as close as it would work in a real environment. First, this was done by the choice of an application territory. We choose an industrial district in Lyon city (France), called "Vallée de la Chimie" (VC). Although VC is one of the biggest chemical and petrochemical parks in Europe, it is poorly served by public transport systems. It presents a concrete application of the lastmile transit. This study focuses on a classical commute problem between the city center and suburbs where two transportation alternatives compete: highway and rapid transit system. Second, we aim to generate realistic traffic demand accounting for intermodality, i.e., using multiple transport modes on the same trip. The traditional four-step travel models could only produce demand matrices for separate modes (McNally, 2007 [26]). We have relied on a Land Use and Transport Interactions (LUTI) model-based tool called OPTIREL to account for intermodality, without using agent-based simulations. OPTIREL has been previously applied to design new subway lines in Paris among other projects. Therefore, the problem we solve is tested on VC for the commute problem with a local rapid transit system.

The remainder of the paper is organized as follows. A brief literature review on the integration of PT-SAV system, the DARP problem, and the graph embedding framework is presented in the next section. Section 3 introduces the optimization model and the solving approach, while Section 4 describes the study case and the generation of traffic demand. In Section 5, we experimentally evaluate the benefit of the designed last-mile service, before concluding on some final thoughts.

LITERATURE REVIEW

In this section, we briefly review the literature of interest in this paper within the following three subsections.

Integration of PT-SAV systems

Several recent studies are starting to explore the benefits of integrating SAV services with existing PT systems. The most commonly adopted approach in this regard is agent-based simulations, whether it concerns the integration, e.g., [START_REF] Shen | Integrating shared autonomous vehicle in public transportation system: A supply-side simulation of the first-mile service in Singapore[END_REF] [START_REF] Shen | Integrating shared autonomous vehicle in public transportation system: A supply-side simulation of the first-mile service in Singapore[END_REF], Pinto et al. (2020) [START_REF] Pinto | Joint design of multimodal transit networks and shared autonomous mobility fleets[END_REF], or merely the intersection of PT-SAV systems, e.g., [START_REF] Fagnant | The travel and environmental implications of shared autonomous vehicles, using agent-based model scenarios[END_REF] [START_REF] Fagnant | The travel and environmental implications of shared autonomous vehicles, using agent-based model scenarios[END_REF]. [START_REF] Liang | Optimizing the service area and trip selection of an electric automated taxi system used for the last mile of train trips[END_REF] [START_REF] Liang | Optimizing the service area and trip selection of an electric automated taxi system used for the last mile of train trips[END_REF] proposed an optimization model for an automated taxi service serving the last mile transit of a train system. Their results are shown for a train station in Delft and include comparisons with human-driven taxis. [START_REF] Shen | Integrating shared autonomous vehicle in public transportation system: A supply-side simulation of the first-mile service in Singapore[END_REF] [START_REF] Shen | Integrating shared autonomous vehicle in public transportation system: A supply-side simulation of the first-mile service in Singapore[END_REF] simulate several scenarios of integrating bus lines with SAVs for the first-mile connectivity during the morning peak hours. Their results based on the Singapore PT show significant savings if lowdemand buses are substituted by SAVs, savings that go up to 860 passenger car unit-kilometers. Pinto et al. (2020) [START_REF] Pinto | Joint design of multimodal transit networks and shared autonomous mobility fleets[END_REF] proposed a bi-level optimization framework to simultaneously modelize the joint transit network parameters and the SAV mobility service. The lower-level problem is a dynamic combined mode choice -traveler assignment problem, while the upper-lever is a modified transit network frequency setting problem. Their results are given for the Chicago metropolitan area. A more detailed review of overall SAV services is provided by [START_REF] Narayanan | Shared autonomous vehicle services: A comprehensive review[END_REF] [START_REF] Narayanan | Shared autonomous vehicle services: A comprehensive review[END_REF].

Dial-a-Ride problems

Designing vehicle routes and schedules for collective people transportation such that each user request has a pickup and a drop-off point locations are referred to as Dial-a-Ride systems, as in early versions of this service, customers have to phone their requests. From a modeling perspective, DARP belongs to the family of routing problems. It is a variant of the vehicle routing problem (VRP), precisely the capacitated VRP with pickup and delivery and Time Windows, with a hands-on transporting passengers rather than goods. Early solving approaches include [START_REF] Psaraftis | A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem[END_REF] [START_REF] Psaraftis | A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem[END_REF], who solved the single-vehicle DARP using dynamic programming, and [START_REF] Jaw | A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows[END_REF] [START_REF] Jaw | A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows[END_REF], who developed one of the first heuristics to the multivehicle DARP. For the exact approaches, Branch-and-Bound and their derived algorithms are the most applied, e.g., [START_REF] Ropke | Models and branch-and-cut algorithms for pickup and delivery problems with time windows[END_REF] [START_REF] Ropke | Models and branch-and-cut algorithms for pickup and delivery problems with time windows[END_REF], Gschwind & Irnich (2014) [START_REF] Gschwind | Effective handling of dynamic time windows and its application to solving the dial-a-ride problem[END_REF]. Concerning metaheuristics, those based on local search, especially those combining local search elements with other metaheuristics currently constitute state-of-the-art solvers, e.g. [START_REF] Masmoudi | Three effective metaheuristics to solve the multidepot multi-trip heterogeneous dial-a-ride problem[END_REF] [START_REF] Masmoudi | Three effective metaheuristics to solve the multidepot multi-trip heterogeneous dial-a-ride problem[END_REF]. Applications of DARPs are overall real-life problems with a diverse range of backgrounds, starting from the standard application to the elderly and disabled people transportation to health care services, to the current emerging applications in public transportation and shared mobility (Ho et al. 2018 [17], Mourad et al. 2019 [START_REF] Mourad | A survey of models and algorithms for optimizing shared mobility[END_REF]). For a more comprehensive review of the problem classes, solving algorithms, and the applications of the DARP, see Cordeau & Laporte (2007) [START_REF] Cordeau | The dial-a-ride problem: models and algorithms[END_REF], [START_REF] Molenbruch | Typology and literature review for dial-a-ride problems[END_REF] [START_REF] Molenbruch | Typology and literature review for dial-a-ride problems[END_REF], and [START_REF] Ho | A survey of dial-a-ride problems: Literature review and recent developments[END_REF] [START_REF] Ho | A survey of dial-a-ride problems: Literature review and recent developments[END_REF].

Graph embeddings

Graph embedding is a powerful method to represent a graph into a low-dimensional vector space by preserving as much as possible its topological structure. It addresses the research question of efficient graph analytics, since traditional methods suffer from the curse of dimensionality and space cost. Essential graph analytic tasks, such as graph classification, node clustering, and link prediction, become scalable to large instances. Representation learning and visualization is another research problem tackled by graph embeddings. There are three main categories of graph embeddings: probabilistic, matrix factorization-based, and deep learning-based methods (see Goyal & Ferrara, 2018 [13] for a survey on the topic). Probabilistic models learn the embedding of graphs through random walks. The samplings given by those walks can capture the neighborhood structure of nodes, connectivities, and other graph properties such as node centrality. Compared with other probabilistic models like DeepWalk (Perozzi et al., 2014 [32]) and LINE (Tang et al., 2015 [38]), the probabilistic model of node2vec (Grover & Leskovec, 2016 [14]) is shown to perform better. This is why we chose node2vec implementation for the graph embedding in the current study. The random walk exploration of this algorithm interpolates between breadth-first (BFS) and depth-first (DFS) searches in order to construct a more informative embedding.

PROPOSED METHOD

Figure 1 illustrates the flowchart of the proposed approach. It is composed of two main distinct blocks: optimization according to the DARP formulation, and the graph reduction mechanism. Given a set of stations in the studied area, the method's inputs are the origin-destination (OD) matrix of the traffic demand, i.e., the number of customers traveling between any two stations, the duration of travel and the traveled distance between all couples of stations. The earliest visit time, service time, and latest visit time for each O-D couple of the demand matrix are also input data. Routing problems in their general formulation are defined on an underlying graph where the set of vertices corresponds to the depot and points to visit, and the set of arcs weighted with costs to travel, generally distances or travel times, represent shortest paths between stations. On this defined routing graph, each point has to be visited only once by precisely one vehicle. Since each initial station could be a pickup and a drop-off point to all the remaining stations, and taking into account all traffic demand inputs of the OD matrix of the area, the dimension of the routing graph to be solved can quickly increase. If n is the total number of stations, the graph dimension could attain a maximum of n (n-1) points to visit without counting the depots. We assume that the vehicle's capacity is greater or equal to every entry of the OD demand matrix. This will prevent us from duplicating the same O-D couple of stations in the routing graph to account for the total demand. The graph reduction mechanism we propose aims to detect groups of pickup and drop-off couple points to be merged, and output a reduced graph that can be easily solvable by a mixed-integer programming solver. Note that clustering and community detection algorithms could be used as well in the step of forming groups 1 . We use the constrained K-means clustering method proposed Bradley et al. (2000) [START_REF] Bradley | Constrained k-means clustering[END_REF] for comparison matter. Our method is overall a model-based heuristic around a central component of mathematical programming. More details of the two main parts of our model is presented in the following.

Mathematical formulation

In this study, we build on [START_REF] Cordeau | A branch-and-cut algorithm for the dial-a-ride problem[END_REF] [START_REF] Cordeau | A branch-and-cut algorithm for the dial-a-ride problem[END_REF] three-index formulation x ij k of the DARP by considering a new objective function and adding new variables. The points to visit are partitioned into two sets: the set of pickup points P and the set of drop-off points D, such that each demand request of the OD demand matrix has a pickup point i ∈ P, a corresponding delivery point which will be denoted deliv (i )∈ D, a maximum riding time L i , and a maximum waiting time M i . Each point i ∈ P ∪ D has a service time ser i , the earliest time to visit tw i early , a latest time to visit tw i late , and a demand load denoted req i , such that for i ∈ P , req i ≥ 0 and req deliv (i) =-req i .

K is the set of vehicles. Each vehicle k ∈ K has a capacity Q k ∈ℕ, GHG emissions up to E k by kilometer, starts from the depot denoted s k and ends at the depot denoted e k . Let D start = { s k : k ∈ K } be the set of all start depots and D end = { e k :k ∈ K } the set of all end depots. For all j ∈ D start ∪ D end , the values serv j =req j =0 are fixed. We associate different start and end depots to each vehicle to make the model more general. However, all these depots may correspond to the same geographical location, which coincide in the case of our application to the transit station of the PT network.

The underlying routing graph G=(V , A ) has a vertex set equal to V =P ∪ D ∪ D start ∪ D end . The arc set is defined as A= { (i , j ): ( i ∈ D start , j ∈ P ) ∨ ( i ∈ D , j ∈ D end ) ∨ (i , j ∈ P ∪ D , i ≠ j , i ≠ deliv ( j)) }, 1 This is different from cluster and route methods, which first apply a clustering algorithm to the input visiting points, and second generate optimal routes for each cluster, e.g., Chen et al. (2020) [START_REF] Chen | Solving the first-mile ridesharing problem using autonomous vehicles[END_REF]. and the weights of the graph are given by c ij and d ij , which denote respectively the duration to travel and the distance from i to j.

The decision variable x ij k indicates whether the arc (i , j ) is traversed by vehicle k ∈ K or not, r i and w i gives respectively the riding time and the waiting time for the request associated with pickup i ∈ P, t i k is the arrival time at point i using vehicle k, and q i k is the load of the vehicle k when leaving the point i.

In addition to minimizing total travel times for all vehicles, the degree of customer dissatisfaction in the sense of [START_REF] Psaraftis | A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem[END_REF] [START_REF] Psaraftis | A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem[END_REF] is also minimized plus to the greenhouse gas emissions due to the transport of passengers. Plausible values of E k are drawn from the life-cycle assessment (LCA) conducted by [START_REF] Gawron | Deep decarbonization from electrified autonomous taxi fleets: Life cycle assessment and case study in Austin, TX[END_REF] [START_REF] Gawron | Deep decarbonization from electrified autonomous taxi fleets: Life cycle assessment and case study in Austin, TX[END_REF]. ( ω 1 , ω 2 , ω 3 ) gives the weights between the three quantities in the objective function. The model is as follows.

Min

ω 1 ∑ k ∈ K ∑ i , j ∈V c ij x ij k +ω 2 ∑ i ∈ P ( r i +w i ) + ω 3 ∑ k ∈ K ∑ i ∈V ∑ j ∈V E k d ij x ij k (1)
Subject to:

∑ i ∈ P x s k i k = ∑ i∈ D x i e k k =1 (k ∈ K ) , (2)
∑ k ∈K ∑ j ∈V x ij k =1 (i ∈ P) , (3)
∑ j ∈V x ij k -∑ j ∈V x deliv (i ) j k =0 (i ∈ P ,k ∈ K ) , (4)
∑ j ∈V x ji k -∑ j ∈V x ij k =0 (i ∈ P ∪ D , k ∈ K ) , ( 5
)
t j k ≥ ( t i k +ser i +c ij ) x ij k (i , j ∈V , k ∈ K ) , (6)
t deliv (i )

k ≥ t i k + ser i +c ideliv (i) (i ∈ P ,k ∈ K ) , ( 7
)
tw i early ≤ t i k ≤ tw i late (i ∈ P ∪ D , k ∈ K ) , ( 8
)
q j k ≥ ( q i k +req i ) x ij k (i , j ∈V , k ∈ K ) , (9)
r i ≥ t deliv (i ) k -( t i k + ser i ) (i ∈ P ,k ∈ K ) , ( 10
)
w i ≥ t i k -tw i early (i ∈ P ,k ∈ K ) , ( 11
)
c ideliv (i ) ≤ r i ≤ L i (i ∈ P) , ( 12
) 0 ≤ w i ≤ M i (i ∈ P) , ( 13
) 0 ≤ q i k ≤ Q k (i ∈ V , k ∈ K ) , ( 14
)
x ij k =0 ∨1 (i , j ∈V ,k ∈ K ) . ( 15
)
The routing constraints (2)-( 5) ensure that each vehicle starts and ends at its corresponding depot points in constraint (2), each request is answered in constraint (3), the same vehicle is used for pickup and drop-off in constraint (4), and the flow conservation in constraint [START_REF] Bradley | Constrained k-means clustering[END_REF]. Constraint (6) tracks the service time, while constraint [START_REF] Cordeau | A branch-and-cut algorithm for the dial-a-ride problem[END_REF] ensures that pickup points are visited before their delivery points, and time window constraints are given in [START_REF] Cordeau | The dial-a-ride problem: models and algorithms[END_REF]. Constraint (9) tracks the load of vehicles, which is needed later to compute the vehicle occupancy rate (VOR) indicator. Constraints [START_REF] Fagnant | The travel and environmental implications of shared autonomous vehicles, using agent-based model scenarios[END_REF] and [START_REF] François | Environmental assessment of urban mobility: combining life cycle assessment with land-use and transport interaction modelling-application to Lyon (France)[END_REF] are respectively relative to the riding time and the waiting time for each request. Constraints ( 12)-( 15) represent the binary and the bounding restrictions for the decision variables. Note that the current mixed-integer programming solvers can efficiently handle indicator constraints as in ( 6) and (9). Other useful constraints to add concern the battery management aspect, which includes the recharge time, the battery energy consumption and detours to recharge stations as in Bongiovanni et al. (2019) [START_REF] Bongiovanni | The electric autonomous dial-a-ride problem[END_REF]. Recent simulations (Vosooghi et al., 2020 [40]) suggest that a best strategy for SAV could be deploying batteries with more charging space to avoid charging the battery within the rush hours of the morning and the evening peaks, otherwise alternating charging and routing could drastically increase the passenger kilometer traveled. For this reason and for the time being, we suppose that battery charging operations are set outside the routing process, and that vehicles are set to be initially charged before transporting customers.

For the heuristic to determine the number of vehicles |K| (mentioned in Figure 1), we use the following formula for vehicles with an identical capacity Q=Q k :

vehicles (m)= ∑ i , j ∈V 2 ,i ≠ j demand (i , j )/(n× Q) .
m is an estimate of the average number of O-D requests each vehicle is expected to answer during the time horizon (usually m=3 or 4).

Graph reduction mechanism

The steps of the graph reduction are listed in the below algorithm. At first, node2vec is applied to the routing graph G, which is introduced in the previous section and is weighted by the travel durations ( c ij ) (i , j )∈ A , for the following inputs: the desired dimension size of the embedding d, the number of random walks to launch from each node and their length, plus other parameters related to the guided exploration strategy of the walks. Thereafter, each node of G can be represented by a feature vector of dimension d.

To obtain a similarity matrix S for the nodes of G, we apply the cosine similarity, which is defined for any two real-valued vectors v 1 and v 2 as the cosine of the angle θ between them, i.e., cos (θ )=v

1 ⋅ v 2 / ( ‖ v 1 ‖ ×‖ v 2 ‖
) . Other measures of similarity and distances could be also used at this step.

This step is important because it gives a quantification of the similarity between any two nodes of G while taking into account as much as possible the topology structure of the graph.

The remaining steps concern merging the points to visit. We opt for merging pick-up and drop-off (P-D) couples two by two. This gives us more flexibility in the rate of contraction of the graph G, and allows us to quickly compute the optimal order within the merged P-D couples. For each two P-D couples ( p 1 , deliv ( p 1 ) , p 2 ,deliv ( p 2 )), we compute the following average similarity using the similarity matrix S

simil ( p 1 , p 2 ) = ( S ( p 1 , p 2 ) +S ( deliv ( p 1 ) , deliv ( p 2 )) +S ( p 1 ,deliv ( p 1 )) ) /6 + ( S ( p 2 , deliv ( p 2 )) +S ( p 2 , deliv ( p 1 )) +S ( p 1 ,deliv ( p 2 )) ) / 6 , ( 17
)
which indicates how close the two couples are. Note that we affect a higher input parameters for BFS over DFS in the guided search of node2vec to favor closer nodes within the vicinity of each node of G.

After ranking pairs of the P-D couples by their similarity, we choose the top r × ( |P|∪|D|)/ 2 pairs, with r is the rate of contraction of the graph. The following step proceeds by computing the optimal order of visiting points within each of the chosen pairs. There are only six possible orders respecting the pickup and drop-off constraints among the total 32, which are shown in Figure 2-a. For each optimal order, we output two aggregated nodes in the novel graph, i.e., if an optimal order is for instance ( p 1 , deliv ( p 1 ) , p 2 ,deliv ( p 2 )), the new nodes will correspond to p '= ( p 1 , deliv ( p 1 )) and deliv ( p ')= ( p 2 ,deliv ( p 2 )). The final step updates the graph weights involving the new nodes, as shown in Figure 2-b. Distances between nodes are updated in the same manner. The graph reduction algorithm has an overall time complexity of O (|V| 2 ) , since node2vec runs in O (|V| 2 ) and the number of pairs of P- D couples processed in the merging steps is at maximum COMBIN (n=( |P|∪|D|)/2, k=2)≤|V| 2 /8.

Algorithm: node2vec-based graph reduction

Inputs: The routing graph G=(V , A ), the contraction rate r.

1. Apply the node2vec algorithm to G.

2. Compute the similarity matrix S of G using the cosine measure on the embedding of 1.

3. Compute for each two P-D couples ( p 1 , deliv ( p 1 ) , p 2 , deliv ( p 2 )) the value simil ( p 1 , p 2 ).

4. Select the top r × ( |P|∪|D|)/ 2 similar pairs of P-D couples.

5. Compute the optimal order of points to visit within each chosen pair.

6. Update the graph's costs for the arcs going to/coming from the newly merged nodes.

CASE STUDY: THE INDUSTRIAL DISTRICT OF "VALLÉE DE LA CHIMIE", LYON CITY

In this section, we describe the studied territory and the process used to generate the input demand data.

Territory

Lyon is the second-largest urban area of France and is home to several industrial hubs. The largest of them is "Vallée de la Chimie" (VC) for approximately 17 km 2 . Situated about 10 km away from city center, VC has currently over 1,000 companies, 6 research and development centers, mostly working in the chemical, energy and the environmental sectors, and it attracts over 20,000 jobs (Métropole de Lyon, 2020 [START_REF]Vallée de la Chimie Presentation[END_REF]).

In terms of mobility infrastructure, a Rapid Transit System (RTS) links VC to the city center on a regular schedule (each 30 min in rush hours, otherwise once by hour). There are quite few buses connecting VC to Lyon city (in total three, two are drawn in the right map of Figure 3 in light red lines). The highway A7 also crosses the territory. This artery is essential for logistic transportation and gets severely congested in the morning rush hours, as A7 is also the south entry point to the city. Commuting to work accounts for a significant part of mobility flows from/to VC. By considering the low PT supply and the highway's high saturation, a typical last-mile transit issue occurs. A number of experimentations to overcome this issue are currently conducted in this territory: Personal Rapid Transit (PRT) from the Esprit project (Esprit, 2019 [9]) and a demand-responsive transit (DRT) service from the local PT service (TCL, 2020 [START_REF] Tcl | Transport à la demande[END_REF]). VC constitutes a good study example for the SAV deployment. This test case is finally classic and generalizable to several other mobility situations all over the world. Indeed, it corresponds to the framework of a commute problem with two main alternatives: PT and the private vehicle which experiments bottleneck.

Demand generation

To generate the traffic demand, we apply a Land Use and Transport Interaction (LUTI) model. LUTI models are spatial interaction models that integrate the socio-demographic and economic features of the population to the transport infrastructure and mobility features, to answer questions such as, what is the transport modal share of a middle-sized income household living in the suburb to commute to work to the city center. With LUTI models, the cause/effect relationships between land use and transport become well understood, and the mobility patterns are well identified. It is noteworthy that LUTI models are extensively used for urban and transport plannings (see [START_REF] Acheampong | Land use-transport interaction modeling: A review of the literature and future research directions[END_REF] for a review on the topic).

We use the LUTI model called OPTIREL, which has the advantage to account for intermodality. OPTIREL proceeds by decomposing the area's space according to the transport mode used from/to the target territory. For instance, the first zone of the studied territory is solely accessible by walking, the second zone is larger and is accessible by bus or RTS system (from/to the territory), the third zone is even larger. It delimits areas accessible by private vehicles combined with relay parking. In this manner, it is possible to define mobility solutions combining several modes in the step of the modal decomposition. The classical four-step travel models define zones according to the administrative or the population census based spatial decomposition, which turns out to be a rigid assumption for combining several modes in the third step of modal share. The traffic demand considered in our application corresponds to the PT demand arriving in the territory by train during the morning peak [7h-10h]. This interval will set our time horizon. Ten stations are defined for the planned SAV service, which correspond to stations of the Esprit project (Esprit, 2019 [9]), and cover the north part of VC. They are shown in Figure 4. The main transit station is "Gare Feyzin" which will coincide with the depots of all vehicles. We can notice from our input OD demand matrix, generated by OPTIREL, and shown in Figure 4, that traffic coming from "Gare Feyzin" is the highest. Interestingly, the traffic is also high from the stations "Hector Berlioz"and "Thomas" which are the closest stations to the transit station. Finally, duration and distances between stations are generated using web mapping services.

Indicators

Two main performance measures are used: the vehicle kilometers traveled (VKT), and the vehicle occupancy rate (VOR). Two additional measures are extracted from them. VKT indicates the total distance traveled by all vehicles of K to satisfy the demand, and is equal to,

VKT ( x )= ∑ k ∈ K ∑ i , j ∈V 2 ,i ≠ j d ij x i , j k .
We also use a correlated measure to VKT, which is the total GHG emissions generated for all trips to provide an order of magnitude of SAV emissions : GHG ( x )= E k VKT ( x ). To get a glimpse of the GHG environmental gain of using SAV, which is previously established in the literature, we show the gap:

GHG gain ( x )= GHG pv (demand) -GHG ( x ) GHG pv (demand)
, with GHG pv (demand ) represents GHG emissions estimated for the input demand and the personal vehicle mode.

The third measure VOR is an average of the load rate of all vehicles at each step of the routing, and is equal to,

VOR ( x ,q )= 1 |K| 1 |P|∪|D| ∑ k ∈ K ∑ i , j∈ P ∪ D ,i ≠ j x ji k q i k Q .
VOR can also be seen as an index of comfort of the mobility service. The last measure, the zero occupancy rate (ZOR) is equal to the percentage of trips between any two stations which have an occupancy rate equal to zero, and is given by,

ZOR ( x , q )= 1 |K| ∑ k ∈ K ∑ i , j ∈P ∪ D , i≠ j , q i k =0 x ji k (|P|∪|D|)-1 .
All measures are computed on the original non-reduced problem.

Baseline scenario

Accounting for the total demand of VC leads to solving a problem of 54 points to visit 2 plus the dummy start and end vehicle depots, which is a computationally hard problem for k >2 vehicles. The graph reduction mechanism makes this optimization more manageable. CPLEX solver could attain a solution for the baseline scenario within a relative MIP gap of 23% in 0.28, 277.17, and 3609.62 seconds when the graph contraction rate is respectively 50%, 45%, and 40%. In the rest of the study, we set the contraction rate of the routing graph at r=50 % . Figure 5 illustrates the SAV routes obtained for the baseline scenario. This scenario has a total traveled distance of VKT =65.46 (respectively 74.44 km) for an average occupation rate of VOR=42.1 % (resp. 31.6 %), and a total emissions of GHG=11.12 (resp. 12.73 Kg CO 2 -eq) for node2vec (resp. constrained K-means) based node reduction. By drawing on the estimates of the vehicle occupancy rate and the GHG emissions of private vehicles computed for the Lyon urban area (François et al, 2017 [START_REF] François | Environmental assessment of urban mobility: combining life cycle assessment with land-use and transport interaction modelling-application to Lyon (France)[END_REF]), we obtain :

GHG pv (demand )= ∑ i , j ∈V 2 ,i ≠ j demand (i , j) × d ij 175 g CO 2 -eq / Km 1.33 person/ car =43.8 Kg CO 2 -eq .
Therefore, compared to the private vehicle mode, the SAV service leads to a reduction of 74.61% of GHG emissions for the territory of VC when relying on the node2vec reduction.

Sensitivity analysis

Figure 6 shows the sensitivity analysis performed on the baseline scenario, by varying the fleet size |K|, the maximum riding time L, and the vehicle's capacity Q . For a number of vehicles equal to 1, 5, and 10, the total traveled distance VKT slowly decreases to be resp. 67.70, 64.53, and 59.88 km for the node2vec reduction. K-means clustering generates tours in the same decreasing trend, but with higher VKT, which is an indication of a lower performance to find best pairs of P-D couples to merge. While |K| is multiplied by 10, VKT of node2vec is divided by 1.13. Having more vehicles actually allows more flexibility for the routing optimization to produce efficient assignments of vehicles to the transport requests. VKT is decreasing in function of Q, which is expected since larger capacities imply smaller tours. Node2vec is again much efficient than K-means reduction in this regard. VKT is overall stable under varying L. As some values of L and Q may constraint the number of possible arrangements of Figure 2-a, an oscillatory effect when varying L and Q could be seen for VKT and VOR index as well.

GHG gain plots on the other hand show the substantial cut in terms of GHG emissions if SAV are deployed instead of private vehicles, especially for the node2vec method. The reduction corresponds to resp. 73.57% and 76.62% of GHG emissions if the fleet size is equal to resp. 1 and 10. Concerning the vehicle occupation rate, we notice that this rate is not affected much by the size |K| and the riding time L, and oscillates around the mean value of 35%. The vehicle's capacity Q, on the other hand, has some influence on VOR. VOR decreases from 38.5 (resp. 43.3%) to 24.9 (resp. 22.7%) when the capacity increases from 20 to 50 for node2vec (resp. K-means) reduction. This particular point should be carefully considered by the designers of SAV services to achieve a fair tradeoff between users' comfort and the costs for an additional capacity of automated vehicles and buses. As for empty trips, ZOR is solely impacted by the size |K|. This index decreases for an increase of |K|, otherwise it has a constant value around 10%.

CONCLUSION

In this study, we propose a model-based heuristic design for a shared autonomous vehicle (SAV) service by combining the formulation of the Dial-a-Ride-Problem (DARP) and a graph reduction mechanism. This latter procedure is based on the graph embedding framework node2vec, and allows us to merge similar couples of pickup and drop-off points, and hence solving instances with a large number of O-D requests and fleet size. A study case analysis is provided for an industrial district of the Lyon urban area (France), wherein the traffic demand is generated by a LUTI model. In the paper, we address in a classical commute problem between city center and suburbs where two transportation alternatives compete: highway and rapid transit system (RTS). The SAV service is deployed as a last-mile transit for the RTS.

Our results suggest that node2vec is more efficient for node reduction than the constrained K-means (in terms of vehicle traveled distance), in addition around 75% reduction of GHG emissions are gained by SAV service when compared to the private vehicle choice.

The limitations of the study mainly concerns the maximum reduction rate, which is currently 50% as reduction is done by merging couples of pickup and drop-off pairs, and the specificity of our application case. One natural improvement is to enlarge the reduction mechanism to three pickup and drop-off pairs. We also think that integrating the current approach with the LUTI model would generate precise partitions of the mode share for the studied territory and population, which would in return help to fix the adequate parameters of the SAV service, i.e., load capacity, fleet size, maximum riding time, in a causeand-effect loop. Table 1. Numerical values of the sensitivity analysis (plotted in Figure 6).

Figure 1 .

 1 Figure 1. Flowchart showing the method's main modules.

Figure 2 .

 2 Figure 2. Possible arrangements for a pair of P-D couples in (a), and the updated travel costs involving merged P-D pairs in (b).

Figure 3 .

 3 Figure 3. The placement of VC within the Lyon urban area in the left map, and the transport network connecting VC in the right map. Source: www.openstreetmap.org/.

Figure 4 .

 4 Figure 4. The locations of the ten stations considered in the study (left map), and the input OD demand matrix (right plot), which is colored according to the demand intensity: green=low, yellow and orange=middle, and red=high.

2

  The number of points to visit for the full OD demand matrix of Figure4is 180 points. We have only 54 points in our input data, since some O-D couples have a null demand.

Figure 5 .

 5 Figure 5. SAV routes for the baseline scenario with the graph embedding reduction (first row) and the K-means based reduction (second row).

Figure 6 .

 6 Figure 6. Sensitivity analysis on the baseline scenario of the fleet size (first column), the clients maximum riding time (second column) and the vehicles' capacity (third column) for the indicators VKT (fist row), VOR (second row), ZOR (third row) and GHG gain (fourth row).

ACKNOWLEDGEMENTS

This work is supported by "Lyon Urban School" (ANR-17-CONV-0004) of Université de Lyon, within the program "Investissements d'Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR). We would like to warmly thank Guy Bourgeois for making the data of OPTIREL available.

RESULTS

In this section, we test the proposed method on the study case and show its usefulness.

Parameters setting

For solving the DARP, ILOG CPLEX 12.10 solver is used, with the termination criteria set to a relative gap of 1%. Although the routing graph is reduced, we have noticed that the problem (1)- [START_REF] Gschwind | Effective handling of dynamic time windows and its application to solving the dial-a-ride problem[END_REF] takes extended time to find a first solution, which is not the case for the problem (1)-( 15) excluding the precedence constraint [START_REF] Cordeau | A branch-and-cut algorithm for the dial-a-ride problem[END_REF]. Thus, we solve the latter problem in a first step, rearrange the points to visit for each vehicle by solving the single-vehicle DARP problem (1)- [START_REF] Gschwind | Effective handling of dynamic time windows and its application to solving the dial-a-ride problem[END_REF] , and then consider this solution a starting point for our main optimization. The effect of adding an initial good quality starting point is beneficial in our CPLEX solving process. In the absence of precise data about the customers' time windows, we set the constraints [START_REF] Cordeau | The dial-a-ride problem: models and algorithms[END_REF] to two time windows, each with one hour duration, and uniformly at random partition P and D points on the two time windows, with the condition that each dropoff point has the same time window of its pickup point. We do not consider customers waiting times w i with this configuration of time windows. A fixed service time ser i =1 minute is associated to each point to visit i ∈ P ∪ D. In the baseline scenario, we set the capacity of vehicles to Q=25>20=max i , j ∈V 2 ,i ≠ j demand (i , j), the number of vehicles to vehicles (m=3)=4, the maximum riding time to L=15 minutes, and the weights of the objective function to ( ω 1 , ω 2 , ω 3 ) =(1,1,0.1). The GHG emission rate is chosen to be equal to E k =0.171 KgCO 2 -eq / km, which corresponds to the short- range electric autonomous taxi scenarios in [START_REF] Gawron | Deep decarbonization from electrified autonomous taxi fleets: Life cycle assessment and case study in Austin, TX[END_REF] [START_REF] Gawron | Deep decarbonization from electrified autonomous taxi fleets: Life cycle assessment and case study in Austin, TX[END_REF]. For the input parameters of node2vec, the dimension size is set to 30, while the walk length is equal to 6 for 1000 random walks launched from each node. Since node2vec is a stochastic method, we launch this method multiple times, exactly 50 times for each configuration of Q and L, then choose the instance with the minimal inside travel time. This latter value is given by the summation of travel times inside the reduced nodes. For instance, the inside travel time of the graph of Figure 2-b is equal to c ij +c kl . The calculation is done for each configuration of Q and L as the possible arrangements of P-D couples could be less than six (Figure 2-a). All experiments are performed on an Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz machine with 32 GB RAM memory.

Constrained K-means

The constrained K-means clustering proposed by [START_REF] Bradley | Constrained k-means clustering[END_REF] [START_REF] Bradley | Constrained k-means clustering[END_REF] extends the traditional algorithm ensuring that each cluster contains at least a minimum number of elements. The problem of minimum cost flow optimization is used to solve the new formulation. Similarly, it is possible to add a maximum size constraint to clusters. In order to have a fair comparison with node2vec, we associate to each pickup node a value similar to the average of the expression (17) : cost avg ( p )= ∑ ( c pq + c deliv ( p)deliv (q) +c pdeliv ( p ) +c qdeliv (q ) +c pdeliv ( q) +c qdeliv ( p) ) /12 + ∑ ( c qp +c deliv (q) deliv ( p) +c deliv ( p) p +c deliv (q) q +c deliv (q ) p +c deliv ( p)q ) /12.

This expression has twelve terms for each q ∈ P to account for the asymmetry of the travel times c ij .

Clusters are generated with a maximum size of two and a minimum size of one, for the clustering with the best inside travel time among 50 runs.

|K| =4

Q = 25


Titouan Parcollet
email: t.parcollet@samsung.com

Shucong Zhang

Alberto Gil

C P Ramos

Rogier Van Dalen

Sourav Bhattacharya

On the (In)Efficiency of Acoustic Feature Extractors for Self-Supervised Speech Representation Learning

Keywords:

Speech representations learned with self-supervised learning (SSL) have the potential to significantly improve the performance of a number of audio applications, especially when availability of labeled data from the deployment domain is limited. Despite their successes, SSL training methods are compute-and memory-heavy, and require large investments in computing infrastructure, thus putting it out of the reach of most institutions. Therefore, building efficient model architectures is essential for the wide-scale adoption of SSL in speech technologies. CNN-based Acoustic Feature Extractors (AFE), which are widely used as encoders of acoustic waveforms, remain one of the main efficiency bottlenecks. This work proposes replacing CNN-based AFEs with more efficient ones and demonstrates that SSL pre-training time and memory consumption can be reduced by a factor of two to three over existing methods while preserving performances in speech-, command-, and speakerrecognition tasks.

Introduction

Self-Supervised Learning (SSL) of deep learning systems leverages a vast amount of unlabeled data to deliver groundbreaking performance across a wide range of domains, including computer vision, robotics [START_REF] Jing | Self-supervised visual feature learning with deep neural networks: A survey[END_REF][START_REF] Sinha | S4rl: Surprisingly simple self-supervision for offline reinforcement learning in robotics[END_REF], audio, speech, and language processing [START_REF] Mohamed | Self-supervised speech representation learning: A review[END_REF][START_REF] Liu | Self-supervised learning: Generative or contrastive[END_REF]. Especially most sub-fields of speech processing increasingly use large pre-trained SSL models to reach previously unseen performance. For instance, SSL has led to stateof-the-art (SOTA) performance for Automatic Speech Recognition (ASR) [START_REF] Hsu | Hubert: Self-supervised speech representation learning by masked prediction of hidden units[END_REF][START_REF] Chen | Wavlm: Large-scale selfsupervised pre-training for full stack speech processing[END_REF], automatic emotion recognition [START_REF] Evain | Task agnostic and task specific self-supervised learning from speech with lebenchmark[END_REF][START_REF] Yang | SUPERB: Speech Processing Universal PERformance Benchmark[END_REF], automatic speaker verification [START_REF] Chen | Large-scale self-supervised speech representation learning for automatic speaker verification[END_REF][START_REF] Yang | SUPERB: Speech Processing Universal PERformance Benchmark[END_REF], Automatic Speech Translation (AST) [START_REF] Nguyen | Investigating self-supervised pre-training for end-to-end speech translation[END_REF][START_REF] Babu | XLS-R: Self-supervised Cross-lingual Speech Representation Learning at Scale[END_REF], Spoken Language Understanding (SLU) [START_REF] Yang | SUPERB: Speech Processing Universal PERformance Benchmark[END_REF][START_REF] Laperriere | On the use of semantically-aligned speech representations for spoken language understanding[END_REF], speech enhancement [START_REF] Huang | Investigating self-supervised learning for speech enhancement and separation[END_REF][START_REF] Wang | Selfsupervised learning for speech enhancement[END_REF], and speech separation [START_REF] Huang | Investigating self-supervised learning for speech enhancement and separation[END_REF][START_REF] Tsai | Superb-sg: Enhanced speech processing universal performance benchmark for semantic and generative capabilities[END_REF]. Alongside remarkable performance in English, SSLtrained models are reducing the gap between low-and highresource languages [START_REF] Babu | XLS-R: Self-supervised Cross-lingual Speech Representation Learning at Scale[END_REF][START_REF] Nguyen | Investigating self-supervised pre-training for end-to-end speech translation[END_REF], increasing the accessibility for cutting-edge technologies across many languages.

However, SSL pre-training requires significant computing infrastructure limiting participation to a handful of industrial actors. For example, pre-training of a SOTA SSL architecture requires extremely large datasets, e.g., tens or hundreds of thousand hours of speech. It also requires architectures with billions of neural network parameters to reach an optimal level of performance, so that a single training can require 64 or 128 highend GPUs to complete a single pre-training process and take a few weeks [START_REF] Evain | Task agnostic and task specific self-supervised learning from speech with lebenchmark[END_REF]. This leads to high environmental costs and can easily run into hundreds of thousands of US dollars. The high cost alone acts as a high barrier for accessibility in the development of novel SSL techniques. Current SSL leaderboards, such as the SUPERB Benchmark, are occupied by models originating from two companies only [START_REF] Tsai | Superb-sg: Enhanced speech processing universal performance benchmark for semantic and generative capabilities[END_REF].

It is therefore vital to make SSL training more efficient. Three culprits for the high cost can be identified [START_REF] Gao | Federated Self-supervised Speech Representations: Are We There Yet?[END_REF]: (i) the Acoustic Feature Extractor (AFE), which transforms the raw waveform into a latent representation; (ii) the "context encoder", which is often a large Transformer; and (iii) the SSL training objective. The last aspect, the objective, has seen efficiency improvements such as Data2Vec [START_REF] Baevski | Data2vec: A general framework for self-supervised learning in speech, vision and language[END_REF] and HuBERT [START_REF] Hsu | Hubert: Self-supervised speech representation learning by masked prediction of hidden units[END_REF]. Improvements to the first two parts, on the other hands, are hardly explored. SOTA SSL-trained models rely on the same CNN-based AFE combined with a large vanilla Transformer. Careful engineering of these two parts could lead to significant efficiency gains [START_REF] Vyas | On-demand compute reduction with stochastic wav2vec 2.0[END_REF] and allow pre-training on mid-tier GPU (e.g., Nvidia Ti 80/90 families) [START_REF] Gao | Federated Self-supervised Speech Representations: Are We There Yet?[END_REF].

There exists some scattered work on improving the efficiency of the AFE. One line of research, which this paper will continue, is to exploit decades of research in the signal processing domain aiming at extracting the best representation of the speech signal. [START_REF] Lin | Melhubert: A simplified hubert on mel spectrogram[END_REF] proposed to train a small HuBERT model with Mel filterbanks instead of the standard CNN-based AFE. However, the paper focusses on downstream performance and the streaming capabilities of the model, and without mention of pre-training efficiency. [START_REF] Wu | Performance-efficiency trade-offs in unsupervised pre-training for speech recognition[END_REF], on the other hand, introduced a new CNN-based AFE inspired by the wav2vec 2.0 AFE [START_REF] Baevski | wav2vec 2.0: A framework for self-supervised learning of speech representations[END_REF], but optimized to increase throughput. This demonstrates that a careful design combined with a time decimation of the input sequence could lead to improvements both in training time and in downstream performance. However, there exists no systematic study of the gains in efficiency and accessibility from choosing different AFEs on speech SSL pre-training. This paper has three main contributions:

1. Introduce new efficient AFEs for training with speech SSL.

A systematic evaluation of different efficiency metrics over

eight AFEs on a carefully crafted contrastive SSL pretraining task with mid-tier GPUs (e.g. RTX 3090).

An examination of the effects on downstream performance

for Automatic Speech Recognition (ASR), Keyword Spotting (KS), and Automatic Speaker Verification (ASV).

The conducted experiments, implemented with methods from the widely-adopted SpeechBrain toolkit [START_REF] Ravanelli | Speechbrain: A general-purpose speech toolkit[END_REF] to facilitate reproducibility, show that a few AFEs introduced in this article make pre-training faster, e.g., reducing from 7 days for a wav2vec 2.0 to 1.8 days (Section 3.1), as well as a more memory efficient, e.g., from 80 GB to 24 GB GPU (Section 3.2), with no degradation in downstream performance. Hence, greater accessibility to speech SSL research can be reached without sacrificing task-specific results or high implementation complexity.

Acoustic Feature Extractors

In this section, we consider AFEs that can replace the standard and inefficient CNN AFE [START_REF] Baevski | wav2vec 2.0: A framework for self-supervised learning of speech representations[END_REF] in wav2vec 2.0 to improve the efficiency of pre-training. In section 2.1, we introduce the AFE in standard wav2vec 2.0 and a more efficient variance, SEW. In section 2.2, we consider AFEs based on Mel filterbanks and learnable filters, with fewer trainable parameters.

Existing AFEs used in self-supervised learning

The majority of large-scale speech SSL models rely on a one-dimensional and end-to-end convolutional network first introduced in wav2vec 2.0 [START_REF] Baevski | wav2vec 2.0: A framework for self-supervised learning of speech representations[END_REF].

Wav2vec 2.0. The original wav2vec 2.0 AFE, also used in WavLM [START_REF] Chen | Wavlm: Large-scale selfsupervised pre-training for full stack speech processing[END_REF] and HuBERT [START_REF] Hsu | Hubert: Self-supervised speech representation learning by masked prediction of hidden units[END_REF], is composed of a number of 1D-convolutions operating directly on the raw audio waveform. The direct connection to the high-dimensional waveform has been identified as the main reason for the high VRAM consumption of this AFE [START_REF] Gao | Match to win: Analysing sequences lengths for efficient self-supervised learning in speech and audio[END_REF][START_REF] Wu | Performance-efficiency trade-offs in unsupervised pre-training for speech recognition[END_REF]. We use the original wav2vec 2.0 frontend [START_REF] Baevski | wav2vec 2.0: A framework for self-supervised learning of speech representations[END_REF], which has seven 1D-convolutional layers with kernels and strides equal to [START_REF] Babu | XLS-R: Self-supervised Cross-lingual Speech Representation Learning at Scale[END_REF][START_REF] Mohamed | Self-supervised speech representation learning: A review[END_REF][START_REF] Mohamed | Self-supervised speech representation learning: A review[END_REF][START_REF] Mohamed | Self-supervised speech representation learning: A review[END_REF][START_REF] Mohamed | Self-supervised speech representation learning: A review[END_REF][START_REF] Mohamed | Self-supervised speech representation learning: A review[END_REF][START_REF] Mohamed | Self-supervised speech representation learning: A review[END_REF] and [START_REF] Hsu | Hubert: Self-supervised speech representation learning by masked prediction of hidden units[END_REF][START_REF] Sinha | S4rl: Surprisingly simple self-supervision for offline reinforcement learning in robotics[END_REF][START_REF] Sinha | S4rl: Surprisingly simple self-supervision for offline reinforcement learning in robotics[END_REF][START_REF] Sinha | S4rl: Surprisingly simple self-supervision for offline reinforcement learning in robotics[END_REF][START_REF] Sinha | S4rl: Surprisingly simple self-supervision for offline reinforcement learning in robotics[END_REF][START_REF] Sinha | S4rl: Surprisingly simple self-supervision for offline reinforcement learning in robotics[END_REF][START_REF] Sinha | S4rl: Surprisingly simple self-supervision for offline reinforcement learning in robotics[END_REF]. This is equivalent to a 25 ms window, with a hop length of 20 ms, resulting in an output frequency of 49 Hz (i.e. 49 vectors emitted per second of speech).

SEW.

The "Squeezed and Efficient Wav2vec" (SEW) [START_REF] Wu | Performance-efficiency trade-offs in unsupervised pre-training for speech recognition[END_REF] AFE shares a similar network architecture as the wav2vec 2.0 AFE, with almost identical receptive field, e.g., window of 24.8 ms and the hop length of 20 ms. Compared to the wav2vec 2.0 AFE, the SEW AFE reduces the computational complexity by cutting the number of channels in the lower layers as well as the kernel size. The AFE contains seven 1D-convolutional layers with kernel sizes [START_REF] Evain | Task agnostic and task specific self-supervised learning from speech with lebenchmark[END_REF][START_REF] Mohamed | Self-supervised speech representation learning: A review[END_REF][START_REF] Mohamed | Self-supervised speech representation learning: A review[END_REF][START_REF] Mohamed | Self-supervised speech representation learning: A review[END_REF][START_REF] Mohamed | Self-supervised speech representation learning: A review[END_REF][START_REF] Sinha | S4rl: Surprisingly simple self-supervision for offline reinforcement learning in robotics[END_REF][START_REF] Sinha | S4rl: Surprisingly simple self-supervision for offline reinforcement learning in robotics[END_REF] and stride [5, 2, 2, 2, 2, 2, 2] respectively. The AFE doubles the number of channels whenever the sequence length is reduced by a factor of four generating channels size of [64, 128, 128, 256, 256, 512, 512].

AFEs inspired by Speech Processing

Representing the speech signal in an efficient way has been an active field of research well before the emergence of deep learning, offering plenty of techniques [START_REF] Lawson | Survey and evaluation of acoustic features for speaker recognition[END_REF][START_REF] Abdel-Hamid | Applying convolutional neural networks concepts to hybrid nn-hmm model for speech recognition[END_REF]. We would like to exploit this knowledge to build a more efficient AFE for training with SSL.

Mel Filterbanks. Mel filterbanks, whose outputs we will call "FBanks", are a well-known and extensively used transformation of the waveform to the frequency domain inspired by human hearing [START_REF] Kopparapu | Choice of mel filter bank in computing mfcc of a resampled speech[END_REF]. Even large pre-trained models, such as Whisper [START_REF] Radford | Robust speech recognition via large-scale weak supervision[END_REF], rely on FBank as an input representation. FBank are extremely quick and cheap to compute enabling a good compression of any speech waveform at a very low cost. A standard and common parametrization of FBank gives a window of size 25 ms and a hop length of 10 ms with a per-frame size of 40 or 80 bins. Lin et al. [START_REF] Lin | Melhubert: A simplified hubert on mel spectrogram[END_REF] have first proposed to pre-train a small HuBERT model using FBanks only. However, the authors do not explore the efficiency and downstream superiority of their approach. In this paper, 80 FBanks are extracted every 20 ms and with a window size of 25 ms to mimic the time resolution of the wav2vec 2.0 AFE, resulting in an output frequency of 50 Hz.

FastAudio. This AFE is a learnable FBank acoustic extractor.

Speech filters are trained alongside the rest of the neural network to optimise the considered objective [START_REF] Fu | Fastaudio: A learnable audio front-end for spoof speech detection[END_REF]. For instance, in FastAudio, triangular FBanks are initialized following the standard mel-scale, before adapting their central frequencies and frequency bands during training. FastAudio is not faster than a standard Fbank extraction at training time, and it only becomes equivalent at inference. However, FastAudio has never been trained with SSL and unlike the original FastAudio implementation, we propose to only optimize the central frequencies alongside the rest of the neural network. Indeed, adding the bands as learnable parameters would make FastAudio filters collapse to a single value while combined with the quantization process of wav2vec 2.0 pre-training. Fixing the bands forces FastAudio to keep filtering the signal properly. The output frequency is equivalent to FBanks.

Mel Filterbanks and CNN. FBanks have been combined for years with 1D or 2D CNNs to either enhance their feature representation or reduce their time resolution. For instance, most SOTA ASR systems using Transformers, Transducers, or recurrent architectures, rely on this type of AFEs. To the best of our knowledge, these AFEs have never been properly investigated in the context of speech SSL, and this paper proposes two different combinations of FBanks and CNN following common approaches from the speech-processing literature. First, "FBank-CNN1d" aggregates a standard melfilterbanks extraction from a 25 ms window and a hop length of 10 ms with a two-layered one-dimensional CNN made of 512 filters with kernel sizes and strides of [START_REF] Mohamed | Self-supervised speech representation learning: A review[END_REF][START_REF] Mohamed | Self-supervised speech representation learning: A review[END_REF], [2, 1] respectively. Layer-normalization and GeLU activations are applied between each layer. The resulting output frequency is 50 Hz. Second, "FBank-CNN2d" is inspired by SOTA Transformer architectures originating from well-known toolkits. Hence, it combines the same standard mel-filterbanks parametrization with a two-layered two-dimensional convolutional CNN made of (128, 64) filters and kernel sizes and strides of [START_REF] Mohamed | Self-supervised speech representation learning: A review[END_REF][START_REF] Mohamed | Self-supervised speech representation learning: A review[END_REF], [START_REF] Sinha | S4rl: Surprisingly simple self-supervision for offline reinforcement learning in robotics[END_REF][START_REF] Sinha | S4rl: Surprisingly simple self-supervision for offline reinforcement learning in robotics[END_REF] respectively. The output frequency is therefore halved to 25 Hz, while the feature dimension is increased from 512 for "FBank-CNN1d" to 1280. Layer normalizations and Leaky ReLU activations are applied between each layers.

SincNet and Leaf Following the success of mel-filterbanks and CNN, Leaf [START_REF] Zeghidour | Leaf: A learnable frontend for audio classification[END_REF], and SincNet [START_REF] Parcollet | E2e-sincnet: Toward fully end-to-end speech recognition[END_REF] merge those two techniques into a single paradigm. Here, the mel-filterbank computation is replaced with a one-dimensional convolutional layer parametrized with common signal processing filters, e.g., triangular for SincNet and Gabor filters for Leaf. The parameters of those filters are then optimized via backpropagation with the task of interest. Other convolutional layers are then added to the filtering layer to complete the AFE. It results in layers with lower computational and memory costs than CNN layers as they require fewer parameters. SincNet and Leaf AFEs have never been applied to speech SSL before. Based on previous experiments for end-to-end ASR [START_REF] Parcollet | E2e-sincnet: Toward fully end-to-end speech recognition[END_REF], we parametrize the SincNet layer with filters of size 129 with a stride of 5 samples. The number of filters is reduced from 512 in [START_REF] Parcollet | E2e-sincnet: Toward fully end-to-end speech recognition[END_REF] to 128 to further reducing the complexity of the CNN. The convolutional front end is composed of five one-dimensional layers of [128, 128, 256, 256, 512] filters with kernel sizes and strides of [START_REF] Mohamed | Self-supervised speech representation learning: A review[END_REF][START_REF] Mohamed | Self-supervised speech representation learning: A review[END_REF][START_REF] Mohamed | Self-supervised speech representation learning: A review[END_REF][START_REF] Mohamed | Self-supervised speech representation learning: A review[END_REF][START_REF] Mohamed | Self-supervised speech representation learning: A review[END_REF], [2, 2, 2, 2, 2] respectively. The resulting output frequency is equal to 50 Hz. Lastly, Leaf follows its original implementation [START_REF] Zeghidour | Leaf: A learnable frontend for audio classification[END_REF] adapted to the 20 ms hop-length of the wav2vec 2.0 to get an output frequency of 50 Hz.

Experiments

In this section we present the performance of each AFE following a two-step process. First, the efficiency is benchmarked to offer empirical insights on potential training speed and memory gains (see §3.1). Then, downstream performance is evaluated, offering a complete view of the advantages of each solution, and following three tasks from the SUPERB benchmark [START_REF] Tsai | Superb-sg: Enhanced speech processing universal performance benchmark for semantic and generative capabilities[END_REF]: automatic speech recognition (ASR), automatic speaker verification (ASV), and keyword spotting (KS) (see §3.2).

Datasets. The Librispeech dataset is used to evaluate both efficiency and downstream performance. During the former, two different sets are created by randomly selecting 1,000 sentences from the 100 hours clean set and then reducing them to either 5 s or 15s. For full SSL pre-training, however, the full Librispeech dataset of 960 hours is considered, with an upper duration limit of 30 s to maximise downstream performance.

Practical considerations. Due to the high pre-training cost associated with contrastive learning, no architecture search has been conducted. We finalized learnable AFE architectures by running a few pre-training epochs with a small set of architectural hyperparameters taken from the literature. In all experiments, AFEs are the only difference between all models and the rest of the architecture strictly follows the original wav2vec 2.0 BASE model [START_REF] Baevski | wav2vec 2.0: A framework for self-supervised learning of speech representations[END_REF], as described in the SpeechBrain Librispeech recipe (commit 71c1490). Efficiency experiments are powered with an isolated RTX 3090 for precise measurements compared to four shared Tesla A100 for pre-training.

(In)Efficiency Analysis

The overall pre-training efficiency of the eight AFEs is evaluated for the first time on a carefully crafted benchmark to enable an extensive comparison of training costs.

Metrics and evaluation.

Each AFE follows a pre-training for a single epoch over the two above-described datasets. A warm-up of 5 backward steps is used to avoid the cudnn optimization overhead. The mini-batch size is fixed to fit the memory budget. AFEs are compared over standard efficiency metrics including the averaged training time necessary to process the 1,000 sentences, the average forward and backward propagation times, the peak VRAM consumption, and the time necessary to process one second of speech including forward and backward computations. The latter metric expresses the throughput of the neural network. Measurements are obtained with full-precision operations on a single RTX 3090 24GB. Note however that our SSL AFEs can exhibit even smaller GPU requirements via low precision arithmetics, e.g., half-precision, or lower precision optimizers e.g. 8-bit [START_REF] Dettmers | 8-bit optimizers via block-wise quantization[END_REF] among others. processing time for all its components compared to the baseline. This is due to the lack of cudnn support in its implementation. Hence may expect a roughly halved training time in real pretraining conditions for the candidate AFE, excluding Leaf, compared to the baseline. Memory-and throughput-wise, FBank-CNN2d clearly outperforms the other AFEs by only consuming 7 GB of memory against 18 GB and 13 GB for wav2vec 2.0 and Fbank-CNN1d respectively on 15 seconds long utterances. The latter behavior is expected due to the lower time resolution of the model. This lowered time resolution also enables the Fbank-CNN2d to exhibit the highest gain in throughput when dealing with longer sentences as the processing time per second of speech decreases from 2.2 ms to 1.4 ms for 5 s and 15 s sentences respectively. Again, all AFE models except Leaf offer significant gains both in terms of VRAM consumption and throughput compared to the base wav2vec 2.0. Mini-batch size variations have also been investigated, yet not reported for the sake of readability. In fact, the less memory-demanding AFEs, e.g. FBank-CNN2d, enable much larger mini-batch sizes than the standard wav2vec 2.0 (e.g. 64 against 16 with 15 s long sentences). This results in better utilization of the GPU, smaller training times, and critically, enabling the training of speech SSL models on cheap GPU such as the Ti 80 and 90 families.

Downstream Evaluation

The downstream performances of seven AFEs are evaluated on three downstream tasks originating from the SUPERB benchmark. We decided to discard Leaf due to poor processing speed performance resulting in untractable training times. Table 1: Downstream results wav2vec 2.0 pre-training with seven AFEs (Leaf is discarded due to poor efficiency measurements). For speech recognition, word error rates (WER) after fine-tuning are on the subsets of Librispeech (dev-clean and test-clean). For keyword spotting, accuracies are on Google Speech Commands. For speaker verification, the equal error rate (EER) is after fine-tuning on VoxCeleb1. GPU requirements are for 200k steps with 4 GPUs in less than 7 days of pre-training, within GPU memory. [START_REF] Baevski | wav2vec 2.0: A framework for self-supervised learning of speech representations[END_REF]. Hence, the number of negatives (100), the length of the masks [START_REF] Nguyen | Investigating self-supervised pre-training for end-to-end speech translation[END_REF], their probability (0.65), and the 1.6 hours mini-batch length are identical.

AFE

Downstream evaluation.

ASR training is performed with the 100 hours clean subset of Librispeech. Word error rates are reported on the dev and test clean sets with 4-gram rescoring. Two dense layers alongside layer normalization are added on top of the pre-trained model following the official SpeechBrain recipe. The entire architecture including wav2vec 2.0 is finetuned with the CTC loss. KS is done with the Google Speech Command dataset with the 12 actions set. Average pooling is applied to the output of the wav2vec 2.0 with a final dense layer for classification. Again, and in contrast to SUPERB, the whole architecture is fine-tuned from end-to-end. Finally, ASV is conducted with the VoxCeleb1 dataset. In this case, the wav2vec 2.0 is frozen to add some diversity to our evaluation. Hence, we follow the SUPERB approach and instead extract a learned weighted sum from all the layers of the wav2vec 2.0. Nevertheless, this evaluation uses the SOTA ECAPA-TDNN architecture [START_REF] Desplanques | Ecapa-tdnn: Emphasized channel attention, propagation and aggregation in tdnn based speaker verification[END_REF] to consume those features instead of the mere x-vector [START_REF] Snyder | X-vectors: Robust dnn embeddings for speaker recognition[END_REF] model from SUPERB. Hyper-parameters are identical to existing SpeechBrain recipes for each dataset.

Downstream results. First, the reported results in Table 1 are in-line with previous works evaluating partially pre-trained wav2vec 2.0 [START_REF] Vyas | On-demand compute reduction with stochastic wav2vec 2.0[END_REF]. Speaker verification EER, for instance, are even better than those reported within the official SUPERB leaderboard with 6.0% against 4.1% in our experiments for the base wav2vec 2.0. The latter difference is due to the use of the ECAPA-TDNN architecture as a downstream decoder. Then, pre-training and Librispeech fine-tuning times also align with findings from the efficiency analysis with every AFE offering speed-ups ranging from 1.4× for SincNet to 3.7× for FBANK-CNN2d compared to wav2vec 2.0. Hence, the total pre-training time is lowered to 180 against 670 GPU hours for FBANK-CNN2d and wav2vec 2.0 respectively. Most newly introduced AFEs also lower the bar in terms of GPU requirements as they enable a 7 days or less pre-training on four Tesla V100 32GB or RTX 3090 24GB for the FBANK-CNN2d compared to four Tesla A100 80GB for the wav2vec 2.0. The latter change induces a decrease in the unitary GPU price of a factor of roughly 10×. Wav2vec 2.0, however, offers the most consistent downstream performance across the three tasks. We hypothesize that such behavior is the result of the extensive hyperparameter tuning at the origin of the wav2vec 2.0 architecture. Nevertheless, the drop in accuracies and word error rates observed with more efficient AFEs are far from dramatic. Indeed, FBANK-CNN1d obtains similar performance to the baseline with a 0.1 % relative increase in WER and EER and an equivalent accuracy on KS, while the pre-training time is reduced by 2.5×. The fastest and cheapest alternative, FBANK-CNN2d, suffers from higher WER with a relative increase of 1.3 %, but also similar or identical ASV and KS performance compared to wav2vec 2.0. SEW, the standard FBANK, and FastAudio also offer important speed and memory improvements, but also show important increases in WER. ASV and KS accuracies also illustrate that the latter AFEs are totally suitable for these tasks. SincNet sits in the middle, as it offers the smallest speed improvement (i.e. 1.4×) but also exhibits comparable WER, EER and KS accuracy against wav2vec 2.0. Overall, Table 1 shows that certain AFE, such as FBANK-CNN1d or SincNet can significantly lower the pretraining cost of wav2vec 2.0-based SSL models while ensuring a similar level of downstream performance. There exist use cases where a relative gain of 0.1 % in raw performance with a 3× increase in computing cost might not be justified. Hence, such results should encourage the community to integrate better descriptors of the model efficiency in standardized benchmarks.

Conclusion

Acoustic features extractors play an important role in the large compute and memory costs of speech SSL pre-training. This paper bridges the gap between the existing abundant speech processing literature and SSL pre-training and compares extensively three novel and five existing AFE, both at the efficiency and downstream performance levels. The observed results suggest that significant compute and memory savings can be achieved without disproportionated downstream performance impact. The latter finding is a major step forward to lowering the entry bar to speech SSL pre-training.

(Figure 1 :

 1 Figure1: Efficiency analysis of the eight AFEs. Time measurements are averages for processing 1,000 sentences. The stacked bar charts report forward and backward timings while the scatter plot offers a view of the throughput (i.e. averaged processing time in ms to train on one second of speech) against peak VRAM. Aside from Leaf, all proposed AFEs offer a training speed-up and a better throughput/VRAM ratio.