Shapley value attribution (SVA) is an increasingly popular Explainable AI (XAI) approach that has been widely used in many recent applied studies to gain new insights into the underlying information systems. However, most existing SVA methods are error-prone, providing biased or unreliable explanations that fail to correctly capture the informational dependencies between features and model outputs. These explanation errors can be decomposed into two components: 1) observation bias which stems from data sparsity and leads to over-informativeness; and 2) structural bias which stems from distributional assumptions and leads to under-informativeness. To alleviate these biases, in this paper, we propose a series of refinement methods that combine out-of-distribution (OOD) detection and importance sampling. In essence, our methods aim to rectify the distribution drift caused by distributional assumptions. We apply our refinement methods to two popular SVAs: the marginal SVA and the surrogate model-based SVA. Our extensive experiments show that the proposed methods significantly enhance the informativeness of both local and global Shapley value-based explanations.

The unprecedented growth of demand for charging electric vehicles (EVs) calls for novel expansion solutions to today’s charging networks. Riding on the wave of the proliferation of sharing economy, Airbnb-like charger sharing markets open the opportunity to expand the existing charging networks without requiring costly and time-consuming infrastructure investments, yet the successful design of such markets relies on innovations at the interface between game theory, mechanism design, and large scale optimization. In this paper, we propose a price-based iterative double auction for charger sharing markets where charger owners rent out their under-utilized chargers to the charge-needing EV drivers. Charger owners and EV drivers form a two-sided market which is cleared by a price-based double auction. Chargers’ locations, availabilities, and unit time service costs as well as drivers’ time and location preferences are considered in the allocation and scheduling process. The goal is to compute social welfare maximizing schedules which benefit both charger owners and EV drivers and, in turn, ensure the continuous growth of the market. We prove that the proposed double auction is budget balanced and individually rational. In addition, results from our computational study show that the proposed auction achieves on average 94% efficiency compared with that of the optimal solutions and is suitable for a larger day-ahead charger sharing market setting in terms of running time.

As the harms of online toxic language become more apparent, countering online toxic behavior is an essential application of natural language processing. The first step in managing toxic language risk is identification, but algorithmic approaches have themselves demonstrated bias. Texts containing some demographic identity terms such as gay or Black are more likely to be labeled as toxic in existing toxic language detection datasets. In many machine learning models introduced for toxic language detection, non-toxic comments containing minority and marginalized community-specific identity terms were given unreasonably high toxicity scores. To address the challenge of bias in toxic language detection, we propose a two-step training approach. A pretrained language model with a multitask learning objective will mitigate biases in the toxicity classifier prediction. Experiments demonstrate that jointly training the pretrained language model with a multitask objective can effectively mitigate the impacts of unintended biases and is more robust to model bias towards commonly-attacked identity groups presented in datasets without significantly hurting the model’s generalizability.

The conditional value-at-risk (CVaR) is a useful risk measure in fields such as machine learning, finance, insurance, energy, etc. When measuring very extreme risk, the commonly used CVaR estimation method of sample averaging does not work well due to limited data above the value-at-risk (VaR), the quantile corresponding to the CVaR level. To mitigate this problem, the CVaR can be estimated by extrapolating above a lower threshold than the VaR using a generalized Pareto distribution (GPD), which is often referred to as the peaks-over-threshold (POT) approach. This method often requires a very high threshold to fit well, leading to high variance in estimation, and can induce significant bias if the threshold is chosen too low. In this paper, we address this bias-variance tradeoff by deriving a new expression for the GPD approximation error of the CVaR, a bias term induced by the choice of threshold, as well as a bias correction method for the estimated GPD parameters. This leads to the derivation of a new CVaR estimator that is asymptotically unbiased and less sensitive to lower thresholds being used. An asymptotic confidence interval for the estimator is also constructed. In a practical setting, we show through experiments that our estimator provides a significant performance improvement compared with competing CVaR estimators in finite samples from heavy-tailed distributions.

Developing a machine that can hold an engaging conversation with a human is one of the main challenges in designing a dialogue system in the field of natural language processing. Responses generated by neural conversational models with log-likelihood training methods tend to lack informativeness and diversity. We address the limitation of log-likelihood training in dialogue generation models, and we present the Reinforce Transformer decoder model, our new approach for training the Transformer decoder based conversational model, which incorporates proximal policy optimization techniques from re-inforcement learning with the Transformer decoder architecture. We specifically examine the use of our proposed model for multi-turn dialogue response generation in a real word human to a human dataset. To verify the effectiveness of our proposed framework, we evaluate our model on the Reddit dialogues data, which is a real word human to a human dataset. Experiments show that our proposed response generating model in a dialogue achieves significant improvement over recurrent sequence-to-sequence models and also the state of the art Transformer based dialogue generation models based on diversity and relevance evaluation metrics.

Reinforcement learning has become an important scheduling solution with many successes in markets with dynamic pricing options, e.g., electric vehicle charging in a deregulated electricity market. However, the highly-uncertain requests and partially-unknown individual preferences remain major challenges to effective demand responses in the user-centric environment. For charging stations who aim to maximize the long-term revenue in this fast-growing market, an accurate estimate of user's sensitivity, or acceptance, of the prices they offered to the potential customers is the key to the success of dynamic pricing. While most existing pricing schemes assume users will consistently follow stable patterns that are observable or inferrable by the charging service provider, it remains crucial to consider how users may be influenced by historic prices they have observed and react strategically to decide optimal charging demands that can maximize their utilities. To overcome this limitation, this paper presents a new framework based on reinforcement mechanism design to determine the optimal charging price in a mechanism design setting, which can optimize the long-term revenue of charging stations as well as the social welfare of users with private utility functions. Specifically, the strategic interaction between the station and users is modelled as a discrete finite Markov decision process, a Q-learning-based dynamic pricing mechanism is proposed to explore how price affects users' demands over a sequence of time. The experiments demonstrate that our pricing mechanism outperforms the predetermined time-of-use pricing in maximizing the long-term revenue of the charging station.

The Fifth Generation (5G) era is bringing tremendous new network capabilities enabling diverse services belonging to different business verticals (i.e., manufacturing, automotive, etc.) and provided with top-notch Quality of Service (QoS) (i.e., ultra-low latency, ultra-reliability, etc.). Empowered by soft-warization technologies such as Network Function Virtualization (NFV), 5G networks are envisioned to be agile, sustainable and self-organized. NFV promotes the automated provisioning of Network Services (NSs) through processing their traffic by a chain of Virtual Network Functions (VNFs). As VNFs are shared between multiple NSs, a clear approach to map and schedule the carried traffic of these services is required. Hence, in this paper, we solve the Latency-Aware Service Schedule Orchestration problem (LASSO) that jointly addresses the mapping and scheduling of services to VNFs. We formulate the problem as a Mixed Integer Linear Program (MILP) and we present ENCHAIN, a novel game-theoretic approach exploiting a scalable solution for the LASSO problem while providing each NS the freedom to decide on its own mapping and scheduling solution.

Variance plays a key role in risk-sensitive reinforcement learning, and most risk measures can be analyzed via variance. In this paper, we consider two law-invariant risks as examples: mean-variance risk and exponential utility risk. With the aid of the state-augmentation transformation (SAT), we show that the two risks can be estimated in Markov decision processes (MDPs) with a stochastic transition-based reward and a randomized policy. To relieve the enlarged state space, a novel definition of isotopic states is proposed for state lumping, considering the special structure of the transformed transition probability. In the numerical experiment, we illustrate state lumping in the SAT, errors from a naive reward simplification, and the validity of the SAT for the two risk estimations.

A stochastic algorithm is presented for a class of optimisation problems that arise when a group of agents compete to share a single constrained resource in an optimal manner. The approach uses intermittent single-bit feedback, which indicates a constraint violation and does not require inter-agent communication. The algorithm is based on a positive matrix model of AIMD, which is extended to the nonhomogeneous Markovian case. The key feature is the assignment of back-off probabilities to the individual agents as a function of the past average access to the resource. This leads to a nonhomogeneous Markov chain in an extended state space, and we show almost sure convergence of the average access to the social optimum.

We propose two improvements to the SSD-single shot multibox detector. First, we propose an adaptive approach for default box selection in SSD. This uses data to reduce the uncertainty in the selection of best aspect ratios for the default boxes and improves performance of SSD for datasets containing small and complex objects (e.g., equipments at construction sites). We do so by finding the distribution of aspect ratios of the given training dataset, and then choosing representative values. Secondly, we propose an ensemble algorithm, using SSD as components, which improves the performance of SSD, especially for small amount of training datasets. Compared to the conventional SSD algorithm, adaptive box selection improves mean average precision by 3%, while ensemble-based SSD improves it by 8%.

The rapid growth of ubiquitous mobile smart devices has led to the creation of a new era of mobile crowdsourcing applications, where human workers participate and perform tasks in exchange of a monetary reward. Such crowdsourcing systems can play a vital role during emergency events, where fast and accurate responses are needed. However, a commonly ignored aspect is how the price (i.e. the reward paid to workers) must be set in order for the system to meet two important requirements: (i) to timely receive an adequate number of responses which is crucial during emergencies, and (ii) to meet budget constraints. In the majority of the existing systems, the price per task is set up-front and remains unchanged for all upcoming tasks, leading to either higher monetary cost than necessary or to significantly larger latency than expected. In this work, we provide a formulation based on Kalman Filters that enables the system to estimate the user/worker behavior, i.e., the likelihood over time for a user to provide answers for a specific reward. Specifically, we focus on the problem of developing an adaptive pricing policy to incentivize the users to rapidly provide their responses. Our mechanism can be adjusted dynamically to bridge the gap among the users' behavior and the system's needs so as to maximize the overall utility of the system. We simulate our model and through extensive experimental evaluation we show how our system performs and provides benefits to both the users and the system operator.

Achieving a balance of supply and demand in a multi-agent system with many individual self-interested and rational agents that act as suppliers and consumers is a natural problem in a variety of real-life domains-smart power grids, data centers, and others. In this paper, we address the profit-maximization problem for a group of distributed supplier and consumer agents, with no inter-agent communication. We simulate a scenario of a market with S suppliers and C consumers such that at every instant, each supplier agent supplies a certain quantity and simultaneously, each consumer agent consumes a certain quantity. The information about the total amount supplied and consumed is only kept with the center. The proposed algorithm is a combination of the classical additive-increase multiplicative-decrease (AIMD) algorithm in conjunction with a probabilistic rule for the agents to respond to a capacity signal. This leads to a nonhomogeneous Markov chain and we show almost sure convergence of this chain to the social optimum, for our market of distributed supplier and consumer agents. Employing this AIMD-type algorithm, the center sends a feedback message to the agents in the supplier side if there is a scenario of excess supply, or to the consumer agents if there is excess consumption. Each agent has a concave utility function whose derivative tends to 0 when an optimum quantity is supplied/consumed. Hence when social convergence is reached, each agent supplies or consumes a quantity which leads to its individual maximum profit, without the need of any communication. So eventually, each agent supplies or consumes a quantity which leads to its individual maximum profit, without communicating with any other agents. Our simulations show the efficacy of this approach.

In this paper we tackle the recently proposed problem of hidden streams. In many situations, the data stream that we are interested in, is not directly accessible. Instead, part of the data can be accessed only through applying filters (e.g. keyword filtering). In fact this is the case of the most discussed social stream today, Twitter. The problem in this case is how to retrieve as many relevant documents as possible by applying the most appropriate set of filters to the original stream and, at the same time, respect a number of constrains (e.g. maximum number of filters that can be applied). In this work we introduce a search approach on a dynamic filter space. We utilize heterogeneous filters (not only keywords) making no assumptions about the attributes of the individual filters. We advance current research by considering realistically hard constraints based on real-world scenarios that require tracking of multiple dynamic topics. We demonstrate the effectiveness of our approaches on a set of topics of static and dynamic nature. The development of the approach was motivated by a real application. Our system is deployed in Dublin City's Traffic Management Center and allows the city officers to analyze large sources of heterogeneous data and identify events related to traffic as well as emergencies.

Parking spaces are resources that can be pooled together and shared, particularly when there exist complementary daytime and nighttime users. We provide solutions to two design questions. First, given a quality of service requirement, how many spaces should be set aside as contingency during the day for nighttime users? Next, how can we replace the first-come-first-served access method by one that aims for optimal efficiency while keeping user preferences private?

We model crowdsensing as the selection of sensors with unknown variance to monitor a large linear dynamical system. To achieve low estimation error, we propose a Thompson sampling approach combining submodular optimization and a scalable online variational inference algorithm to maintain the posterior distribution over the variance. We also consider three alternative parameter estimation algorithms. We illustrate the behavior of our sensor selection algorithms on real traffic data from the city of Dublin. Our online algorithm achieves significantly lower estimation error than sensor selection using a fixed variance value for all sensors.

We consider robust optimization for polynomial optimization problems where the uncertainty set is a set of candidate probability density functions. This set is a ball around a density function estimated from data samples, i.e., it is data-driven and random. Polynomial optimization problems are inherently hard due to nonconvex objectives and constraints. However, we show that by employing polynomial and histogram density estimates, we can introduce robustness with respect to distributional uncertainty sets without making the problem harder. We show that the solution to the distributionally robust problem is the limit of a sequence of tractable semidefinite programming relaxations. We also give finite-sample consistency guarantees for the data-driven uncertainty sets. Finally, we apply our model and solution method in a water network problem.

No abstract available.

We consider a sequential decision problem where the rewards are generated by a piecewise-stationary distribution. However, the different reward distributions are unknown and may change at unknown instants. Our approach uses a limited number of side observations on past rewards, but does not require prior knowledge of the frequency of changes. In spite of the adversarial nature of the reward process, we provide an algorithm whose regret, with respect to the baseline with perfect knowledge of the distributions and the changes, is O(k log(T)), where k is the number of changes up to time T. This is in contrast to the case where side observations are not available, and where the regret is at least Ω(√T).

Market mechanisms have been suggested in the last few years as a tool for allocating shared networks resources among several competing users. In this paper, we consider the efficiency loss of such mechanisms in the presence of a large number of users. We model the user interactions as a game with a heterogeneous population of players characterized by random utility functions. If the utility functions are bounded, then the non-cooperative equilibrium are nearly as efficient as the social optimum with high probability when the number of users is large. This efficiency result holds for a single link with a fixed or an increasing capacity. Using a standard probabilistic analysis, we show that the efficiency loss incurred by the market mechanism decreases almost exponentially in the number of users. If, however, the utility functions are not bounded, then the loss of efficiency does not converge to zero. We also provide results for networks by sampling the users at random based on their paths.

Abstract — We consider the loss of efficiency in competitive market mechanisms used to allocate network resources. We model large heterogeneous populations of users assuming that each user has a random utility function. We show that if the utility functions are bounded, the competitive equilibrium will be nearly as efficient as the social optimum with high probability as the number of users increases. This is the case for inelastic capacity as well as elastic capacity, under some standard assumptions. This result extends to a network setup where sources and destinations are picked at random. If, however, the utility functions are not bounded, then the loss of efficiency does not converge to zero. Collaborating simulations are also presented. I.