-
Geometric Collaborative Filtering with Convergence
Authors:
Hisham Husain,
Julien Monteil
Abstract:
Latent variable collaborative filtering methods have been a standard approach to modelling user-click interactions due to their simplicity and effectiveness. However, there is limited work on analyzing the mathematical properties of these methods in particular on preventing the overfitting towards the identity, and such methods typically utilize loss functions that overlook the geometry between it…
▽ More
Latent variable collaborative filtering methods have been a standard approach to modelling user-click interactions due to their simplicity and effectiveness. However, there is limited work on analyzing the mathematical properties of these methods in particular on preventing the overfitting towards the identity, and such methods typically utilize loss functions that overlook the geometry between items. In this work, we introduce a notion of generalization gap in collaborative filtering and analyze this with respect to latent collaborative filtering models. We present a geometric upper bound that gives rise to loss functions, and a way to meaningfully utilize the geometry of item-metadata to improve recommendations. We show how these losses can be minimized and gives the recipe to a new latent collaborative filtering algorithm, which we refer to as GeoCF, due to the geometric nature of our results. We then show experimentally that our proposed GeoCF algorithm can outperform other all existing methods on the Movielens20M and Netflix datasets, as well as two large-scale internal datasets. In summary, our work proposes a theoretically sound method which paves a way to better understand generalization of collaborative filtering at large.
△ Less
Submitted 3 October, 2024;
originally announced October 2024.
-
Personalised Outfit Recommendation via History-aware Transformers
Authors:
Myong Chol Jung,
Julien Monteil,
Philip Schulz,
Volodymyr Vaskovych
Abstract:
We present the history-aware transformer (HAT), a transformer-based model that uses shoppers' purchase history to personalise outfit predictions. The aim of this work is to recommend outfits that are internally coherent while matching an individual shopper's style and taste. To achieve this, we stack two transformer models, one that produces outfit representations and another one that processes th…
▽ More
We present the history-aware transformer (HAT), a transformer-based model that uses shoppers' purchase history to personalise outfit predictions. The aim of this work is to recommend outfits that are internally coherent while matching an individual shopper's style and taste. To achieve this, we stack two transformer models, one that produces outfit representations and another one that processes the history of purchased outfits for a given shopper. We use these models to score an outfit's compatibility in the context of a shopper's preferences as inferred from their previous purchases. During training, the model learns to discriminate between purchased and random outfits using 3 losses: the focal loss for outfit compatibility typically used in the literature, a contrastive loss to bring closer learned outfit embeddings from a shopper's history, and an adaptive margin loss to facilitate learning from weak negatives. Together, these losses enable the model to make personalised recommendations based on a shopper's purchase history.
Our experiments on the IQON3000 and Polyvore datasets show that HAT outperforms strong baselines on the outfit Compatibility Prediction (CP) and the Fill In The Blank (FITB) tasks. The model improves AUC for the CP hard task by 15.7% (IQON3000) and 19.4% (Polyvore) compared to previous SOTA results. It further improves accuracy on the FITB hard task by 6.5% and 9.7%, respectively. We provide ablation studies on the personalisation, constrastive loss, and adaptive margin loss that highlight the importance of these modelling choices.
△ Less
Submitted 26 September, 2024; v1 submitted 28 June, 2024;
originally announced July 2024.
-
MARec: Metadata Alignment for cold-start Recommendation
Authors:
Julien Monteil,
Volodymyr Vaskovych,
Wentao Lu,
Anirban Majumder,
Anton van den Hengel
Abstract:
For many recommender systems, the primary data source is a historical record of user clicks. The associated click matrix is often very sparse, as the number of users x products can be far larger than the number of clicks. Such sparsity is accentuated in cold-start settings, which makes the efficient use of metadata information of paramount importance. In this work, we propose a simple approach to…
▽ More
For many recommender systems, the primary data source is a historical record of user clicks. The associated click matrix is often very sparse, as the number of users x products can be far larger than the number of clicks. Such sparsity is accentuated in cold-start settings, which makes the efficient use of metadata information of paramount importance. In this work, we propose a simple approach to address cold-start recommendations by leveraging content metadata, Metadata Alignment for cold-start Recommendation. We show that this approach can readily augment existing matrix factorization and autoencoder approaches, enabling a smooth transition to top performing algorithms in warmer set-ups. Our experimental results indicate three separate contributions: first, we show that our proposed framework largely beats SOTA results on 4 cold-start datasets with different sparsity and scale characteristics, with gains ranging from +8.4% to +53.8% on reported ranking metrics; second, we provide an ablation study on the utility of semantic features, and proves the additional gain obtained by leveraging such features ranges between +46.8% and +105.5%; and third, our approach is by construction highly competitive in warm set-ups, and we propose a closed-form solution outperformed by SOTA results by only 0.8% on average.
△ Less
Submitted 26 September, 2024; v1 submitted 20 April, 2024;
originally announced April 2024.
-
Reservation of Virtualized Resources with Optimistic Online Learning
Authors:
Jean-Baptiste Monteil,
George Iosifidis,
Ivana Dusparic
Abstract:
The virtualization of wireless networks enables new services to access network resources made available by the Network Operator (NO) through a Network Slicing market. The different service providers (SPs) have the opportunity to lease the network resources from the NO to constitute slices that address the demand of their specific network service. The goal of any SP is to maximize its service utili…
▽ More
The virtualization of wireless networks enables new services to access network resources made available by the Network Operator (NO) through a Network Slicing market. The different service providers (SPs) have the opportunity to lease the network resources from the NO to constitute slices that address the demand of their specific network service. The goal of any SP is to maximize its service utility and minimize costs from leasing resources while facing uncertainties of the prices of the resources and the users' demand. In this paper, we propose a solution that allows the SP to decide its online reservation policy, which aims to maximize its service utility and minimize its cost of reservation simultaneously. We design the Optimistic Online Learning for Reservation (OOLR) solution, a decision algorithm built upon the Follow-the-Regularized Leader (FTRL), that incorporates key predictions to assist the decision-making process. Our solution achieves a $\mathcal{O}(\sqrt{T})$ regret bound where $T$ represents the horizon. We integrate a prediction model into the OOLR solution and we demonstrate through numerical results the efficacy of the combined models' solution against the FTRL baseline.
△ Less
Submitted 15 March, 2023;
originally announced March 2023.
-
A city-scale IoT-enabled ridesharing platform
Authors:
Claudio Gambella,
Julien Monteil,
Anton Dekusar,
Sergio Cabrero Barros,
Andrea Simonetto,
Yassine Lassoued
Abstract:
The advent of on-demand mobility systems is expected to have a tremendous potential on the wellness of transportation users in cities. Yet such positive effects are reached when the systems under consideration enable seamless integration between data sources that involve a high number of transportation actors. In this paper we report on the effort of designing and deploying an integrated system, i…
▽ More
The advent of on-demand mobility systems is expected to have a tremendous potential on the wellness of transportation users in cities. Yet such positive effects are reached when the systems under consideration enable seamless integration between data sources that involve a high number of transportation actors. In this paper we report on the effort of designing and deploying an integrated system, including algorithms and platforms, that can operate in cities, in an Internet of Things (IoT)-aware fashion. The system was evaluated by enabling/disabling the IoT components of the system, highlighting the necessity of real-time data integration for efficient mobility services.
△ Less
Submitted 2 December, 2019;
originally announced December 2019.
-
On model selection for scalable time series forecasting in transport networks
Authors:
Julien Monteil,
Anton Dekusar,
Claudio Gambella,
Yassine Lassoued,
Martin Mevissen
Abstract:
The transport literature is dense regarding short-term traffic predictions, up to the scale of 1 hour, yet less dense for long-term traffic predictions. The transport literature is also sparse when it comes to city-scale traffic predictions, mainly because of low data availability. In this work, we report an effort to investigate whether deep learning models can be useful for the long-term large-s…
▽ More
The transport literature is dense regarding short-term traffic predictions, up to the scale of 1 hour, yet less dense for long-term traffic predictions. The transport literature is also sparse when it comes to city-scale traffic predictions, mainly because of low data availability. In this work, we report an effort to investigate whether deep learning models can be useful for the long-term large-scale traffic prediction task, while focusing on the scalability of the models. We investigate a city-scale traffic dataset with 14 weeks of speed observations collected every 15 minutes over 1098 segments in the hypercenter of Los Angeles, California. We look at a variety of state-of-the-art machine learning and deep learning predictors for link-based predictions, and investigate how such predictors can scale up to larger areas with clustering, and graph convolutional approaches. We discuss that modelling temporal and spatial features into deep learning predictors can be helpful for long-term predictions, while simpler, not deep learning-based predictors, achieve very satisfactory performance for link-based and short-term forecasting. The trade-off is discussed not only in terms of prediction accuracy vs prediction horizon but also in terms of training time and model sizing.
△ Less
Submitted 18 February, 2021; v1 submitted 29 November, 2019;
originally announced November 2019.
-
On the needs for MaaS platforms to handle competition in ridesharing mobility
Authors:
Venktesh Pandey,
Julien Monteil,
Claudio Gambella,
Andrea Simonetto
Abstract:
Ridesharing has been emerging as a new type of mobility. However, the early promises of ridesharing for alleviating congestion in cities may be undermined by a number of challenges, including the growing number of proposed services and the subsequent increasing number of vehicles, as a natural consequence of competition. In this work, we present optimization-based approaches to model cooperation a…
▽ More
Ridesharing has been emerging as a new type of mobility. However, the early promises of ridesharing for alleviating congestion in cities may be undermined by a number of challenges, including the growing number of proposed services and the subsequent increasing number of vehicles, as a natural consequence of competition. In this work, we present optimization-based approaches to model cooperation and competition between multiple ridesharing companies, in a real-time on-demand setting. A recent trend relies on solving the integrated combination of Dial-A-Ride Problems (DARP), which compute the cost of assigning incoming requests to vehicle routes, plus Linear Assignment Problems (LAP), which assign vehicles to requests. While the DARPs, are solved at the level of the vehicles of each company, we introduce cooperative and competitive approaches to solve the LAP. The cooperative model, which could make use of Mobility as a Service platforms, is shown to solve the LAP to optimality following closely results from the literature, and limiting the amount of information the companies are required to share. We investigate how a realistic model of competition deviates from this optimality and provide worst case bounds. We evaluate these models with respect to a centralized model on one-week instances of the New York City taxi dataset. Model variants coping with noise in the travel time estimations, bias in the assignment costs, and preferences in the competitive case are also presented and validated. The computational results suggest that cooperation among ridesharing companies can be conducted in such a way to limit the degradation of the level of service with respect to a centralized model. Finally, we argue that the competition can lower the quality of the ridesharing service, especially in the case customer preferences are accommodated.
△ Less
Submitted 15 June, 2019;
originally announced June 2019.
-
Personalized Optimization with User's Feedback
Authors:
Andrea Simonetto,
Emiliano Dall'Anese,
Julien Monteil,
Andrey Bernstein
Abstract:
This paper develops an online algorithm to solve a time-varying optimization problem with an objective that comprises a known time-varying cost and an unknown function. This problem structure arises in a number of engineering systems and cyber-physical systems where the known function captures time-varying engineering costs, and the unknown function models user's satisfaction; in this context, the…
▽ More
This paper develops an online algorithm to solve a time-varying optimization problem with an objective that comprises a known time-varying cost and an unknown function. This problem structure arises in a number of engineering systems and cyber-physical systems where the known function captures time-varying engineering costs, and the unknown function models user's satisfaction; in this context, the objective is to strike a balance between given performance metrics and user's satisfaction. Key challenges related to the problem at hand are related to (1) the time variability of the problem, and (2) the fact that learning of the user's utility function is performed concurrently with the execution of the online algorithm. This paper leverages Gaussian processes (GP) to learn the unknown cost function from noisy functional evaluation and build pertinent upper confidence bounds. Using the GP formalism, the paper then advocates time-varying optimization tools to design an online algorithm that exhibits tracking of the oracle-based optimal trajectory within an error ball, while learning the user's satisfaction function with no-regret. The algorithmic steps are inexact, to account for possible limited computational budgets or real-time implementation considerations. Numerical examples are illustrated based on a problem related to vehicle platooning.
△ Less
Submitted 5 August, 2020; v1 submitted 2 May, 2019;
originally announced May 2019.
-
Real-time City-scale Ridesharing via Linear Assignment Problems
Authors:
Andrea Simonetto,
Julien Monteil,
Claudio Gambella
Abstract:
In this paper, we propose a novel, computational efficient, dynamic ridesharing algorithm. The beneficial computational properties of the algorithm arise from casting the ridesharing problem as a linear assignment problem between fleet vehicles and customer trip requests within a federated optimization architecture. The resulting algorithm is up to four times faster than the state-of-the-art, even…
▽ More
In this paper, we propose a novel, computational efficient, dynamic ridesharing algorithm. The beneficial computational properties of the algorithm arise from casting the ridesharing problem as a linear assignment problem between fleet vehicles and customer trip requests within a federated optimization architecture. The resulting algorithm is up to four times faster than the state-of-the-art, even if it is implemented on a less dedicated hardware, and achieves similar service quality. Current literature showcases the ability of state-of-the-art ridesharing algorithms to tackle very large fleets and customer requests in almost near real-time, but the benefits of ridesharing seem limited to centralized systems. Our algorithm suggests that this does not need to be the case. The algorithm that we propose is fully distributable among multiple ridesharing companies. By leveraging two datasets, the New York city taxi dataset and the Melbourne Metropolitan Area dataset, we show that with our algorithm, real-time ridesharing offers clear benefits with respect to more traditional taxi fleets in terms of level of service, even if one considers partial adoption of the system. In fact, e.g., the quality of the solutions obtained in the state-of-the-art works that tackle the whole customer set of the New York city taxi dataset is achieved, even if one considers only a proportion of the fleet size and customer requests. This could make real-time urban-scale ridesharing very attractive to small enterprises and city authorities alike. However, in some cases, e.g., in multi-company scenarios where companies have predefined market shares, we show that the number of vehicles needed to achieve a comparable performance to the monopolistic setting increases, and this raises concerns on the possible negative effects of multi-company ridesharing.
△ Less
Submitted 27 February, 2019;
originally announced February 2019.
-
Using Deep Learning to Extend the Range of Air-Pollution Monitoring and Forecasting
Authors:
Philipp Haehnel,
Jakub Marecek,
Julien Monteil,
Fearghal O'Donncha
Abstract:
Across numerous applications, forecasting relies on numerical solvers for partial differential equations (PDEs). Although the use of deep-learning techniques has been proposed, actual applications have been restricted by the fact the training data are obtained using traditional PDE solvers. Thereby, the uses of deep-learning techniques were limited to domains, where the PDE solver was applicable.…
▽ More
Across numerous applications, forecasting relies on numerical solvers for partial differential equations (PDEs). Although the use of deep-learning techniques has been proposed, actual applications have been restricted by the fact the training data are obtained using traditional PDE solvers. Thereby, the uses of deep-learning techniques were limited to domains, where the PDE solver was applicable.
We demonstrate a deep-learning framework for air-pollution monitoring and forecasting that provides the ability to train across different model domains, as well as a reduction in the run-time by two orders of magnitude. It presents a first-of-a-kind implementation that combines deep-learning and domain-decomposition techniques to allow model deployments extend beyond the domain(s) on which the it has been trained.
△ Less
Submitted 26 January, 2020; v1 submitted 22 October, 2018;
originally announced October 2018.
-
Bayesian Classifier for Route Prediction with Markov Chains
Authors:
Jonathan P. Epperlein,
Julien Monteil,
Mingming Liu,
Yingqi Gu,
Sergiy Zhuk,
Robert Shorten
Abstract:
We present here a general framework and a specific algorithm for predicting the destination, route, or more generally a pattern, of an ongoing journey, building on the recent work of [Y. Lassoued, J. Monteil, Y. Gu, G. Russo, R. Shorten, and M. Mevissen, "Hidden Markov model for route and destination prediction," in IEEE International Conference on Intelligent Transportation Systems, 2017]. In the…
▽ More
We present here a general framework and a specific algorithm for predicting the destination, route, or more generally a pattern, of an ongoing journey, building on the recent work of [Y. Lassoued, J. Monteil, Y. Gu, G. Russo, R. Shorten, and M. Mevissen, "Hidden Markov model for route and destination prediction," in IEEE International Conference on Intelligent Transportation Systems, 2017]. In the presented framework, known journey patterns are modelled as stochastic processes, emitting the road segments visited during the journey, and the ongoing journey is predicted by updating the posterior probability of each journey pattern given the road segments visited so far. In this contribution, we use Markov chains as models for the journey patterns, and consider the prediction as final, once one of the posterior probabilities crosses a predefined threshold. Despite the simplicity of both, examples run on a synthetic dataset demonstrate high accuracy of the made predictions.
△ Less
Submitted 31 August, 2018;
originally announced August 2018.
-
A Hidden Markov Model for Route and Destination Prediction
Authors:
Yassine Lassoued,
Julien Monteil,
Yingqi Gu,
Giovanni Russo,
Robert Shorten,
Martin Mevissen
Abstract:
We present a simple model and algorithm for predicting driver destinations and routes, based on the input of the latest road links visited as part of an ongoing trip. The algorithm may be used to predict any clusters previously observed in a driver's trip history. It assumes that the driver's historical trips are grouped into clusters sharing similar patterns. Given a new trip, the algorithm attem…
▽ More
We present a simple model and algorithm for predicting driver destinations and routes, based on the input of the latest road links visited as part of an ongoing trip. The algorithm may be used to predict any clusters previously observed in a driver's trip history. It assumes that the driver's historical trips are grouped into clusters sharing similar patterns. Given a new trip, the algorithm attempts to predict the cluster in which the trip belongs. The proposed algorithm has low temporal complexity. In addition, it does not require the transition and emission matrices of the Markov chain to be computed. Rather it relies on the frequencies of co-occurrences of road links and trip clusters. We validate the proposed algorithm against an experimental dataset. We discuss the success and convergence of the algorithm and show that our algorithm has a high prediction success rate.
△ Less
Submitted 15 March, 2018;
originally announced April 2018.
-
On $\mathcal{L}_{\infty}$ string stability of nonlinear bidirectional asymmetric heterogeneous platoon systems
Authors:
Julien Monteil,
Giovanni Russo,
Robert Shorten
Abstract:
This paper is concerned with the study of bidirectionally coupled platoon systems. The case considered is when the vehicles are heterogeneous and the coupling can be nonlinear and asymmetric. For such systems, a sufficient condition for $\mathcal{L}_{\infty}$ string stability is presented. The effectiveness of our approach is illustrated via a numerical example, where it is shown how our result ca…
▽ More
This paper is concerned with the study of bidirectionally coupled platoon systems. The case considered is when the vehicles are heterogeneous and the coupling can be nonlinear and asymmetric. For such systems, a sufficient condition for $\mathcal{L}_{\infty}$ string stability is presented. The effectiveness of our approach is illustrated via a numerical example, where it is shown how our result can be recast as an optimization problem, allowing to design the control protocol for each vehicle independently on the other vehicles and hence leading to a bottom-up approach for the design of string stable systems able to track a time-varying reference speed.
△ Less
Submitted 24 December, 2018; v1 submitted 23 January, 2018;
originally announced January 2018.
-
$\mathcal{L}_2$ and $\mathcal{L}_{\infty}$ stability analysis of heterogeneous traffic with application to parameter optimisation for the control of automated vehicles
Authors:
Julien Monteil,
Melanie Bouroche,
Douglas J. Leith
Abstract:
The presence of (partially) automated vehicles on the roads presents an opportunity to compensate the unstable behaviour of conventional vehicles. Vehicles subject to perturbations should (i) recover their equilibrium speed, (ii) react not to propagate but absorb perturbations. In this work, we start with considering vehicle systems consisting of heterogeneous vehicles updating their dynamics acco…
▽ More
The presence of (partially) automated vehicles on the roads presents an opportunity to compensate the unstable behaviour of conventional vehicles. Vehicles subject to perturbations should (i) recover their equilibrium speed, (ii) react not to propagate but absorb perturbations. In this work, we start with considering vehicle systems consisting of heterogeneous vehicles updating their dynamics according to realistic behavioural car-following models. Definitions of all types of stability that are of interest in the vehicle system, namely input-output stability, scalability, weak and strict string stability, are introduced based on recent studies. Then, frequency domain linear stability analyses are conducted after linearisation of the modelled system of vehicles, leading to conditions for input-output stability, strict and weak string stability over the behavioural parameters of the system, for finite and infinite systems of homogeneous and heterogeneous vehicles. This provides a solid basis that was missing for car-following model-based control design in mixed traffic systems where only a proportion of vehicles can be controlled. After visualisation of the theoretical results in simulation, we formulate an optimisation strategy with LMI constraints to tune the behavioural parameters of the automated vehicles in order to maximise the L1 string stability of the mixed traffic flow while considering the comfort of automated driving. The optimisation strategy systematically leads to increased traffic flow stability. We show that very few automated vehicles are required to prevent the
△ Less
Submitted 15 March, 2018; v1 submitted 22 September, 2016;
originally announced September 2016.
