OpenRaiser/Intern-Atlas huggingface dataset:
Mechanism Design for Efficient Online and Offline Allocation of Electric Vehicles to Charging Stations
Venue: arXiv cs.GT 2020
Year: 2020

We study the problem of allocating Electric Vehicles (EVs) to charging stations and scheduling their charging. We develop offline and online solutions that treat EV users as self-interested agents that aim to maximise their profit and minimise the impact on their schedule. We formulate the problem of the optimal EV to charging station allocation as a Mixed Integer Programming (MIP) one and we propose two pricing mechanisms: A fixed-price one, and another that is based on the well known Vickrey-Clark-Groves (VCG) mechanism. Later, we develop online solutions that incrementally call the MIP-based algorithm. We empirically evaluate our mechanisms and we observe that both scale well. Moreover, the VCG mechanism services on average $1.5\%$ more EVs than the fixed-price one. In addition, when the stations get congested, VCG leads to higher prices for the EVs and higher profit for the stations, but lower utility for the EVs. However, we theoretically prove that the VCG mechanism guarantees truthful reporting of the EVs' preferences. In contrast, the fixed-price one is vulnerable to agents' strategic behaviour as non-truthful EVs can charge in place of truthful ones. Finally, we observe that the online algorithms are on average at $98\%$ of the optimal in EV satisfaction.
Lazy State Determination: More concurrency for contending linearizable transactions
Venue: arXiv cs.DC 2020
Year: 2020

The concurrency control algorithms in transactional systems limits concurrency to provide strong semantics, which leads to poor performance under high contention. As a consequence, many transactional systems eschew strong semantics to achieve acceptable performance. We show that by leveraging semantic information associated with the transactional programs to increase concurrency, it is possible to significantly improve performance while maintaining linearizability. To this end, we introduce the lazy state determination API to easily expose the semantics of application transactions to the database, and propose new optimistic and pessimistic concurrency control algorithms that leverage this information to safely increase concurrency in the presence of contention. Our evaluation shows that our approach can achieve up to 5x more throughput with 1.5c less latency than standard techniques in the popular TPC-C benchmark.
Deep Representation Learning For Multimodal Brain Networks
Venue: arXiv cs.CV 2020
Year: 2020

Applying network science approaches to investigate the functions and anatomy of the human brain is prevalent in modern medical imaging analysis. Due to the complex network topology, for an individual brain, mining a discriminative network representation from the multimodal brain networks is non-trivial. The recent success of deep learning techniques on graph-structured data suggests a new way to model the non-linear cross-modality relationship. However, current deep brain network methods either ignore the intrinsic graph topology or require a network basis shared within a group. To address these challenges, we propose a novel end-to-end deep graph representation learning (Deep Multimodal Brain Networks - DMBN) to fuse multimodal brain networks. Specifically, we decipher the cross-modality relationship through a graph encoding and decoding process. The higher-order network mappings from brain structural networks to functional networks are learned in the node domain. The learned network representation is a set of node features that are informative to induce brain saliency maps in a supervised manner. We test our framework in both synthetic and real image data. The experimental results show the superiority of the proposed method over some other state-of-the-art deep brain network models.
Generative Adversarial Stacked Autoencoders for Facial Pose Normalization and Emotion Recognition
Venue: arXiv cs.CV 2020
Year: 2020

In this work, we propose a novel Generative Adversarial Stacked Autoencoder that learns to map facial expressions, with up to plus or minus 60 degrees, to an illumination invariant facial representation of 0 degrees. We accomplish this by using a novel convolutional layer that exploits both local and global spatial information, and a convolutional layer with a reduced number of parameters that exploits facial symmetry. Furthermore, we introduce a generative adversarial gradual greedy layer-wise learning algorithm designed to train Adversarial Autoencoders in an efficient and incremental manner. We demonstrate the efficiency of our method and report state-of-the-art performance on several facial emotion recognition corpora, including one collected in the wild.
Counterfactual Learning to Rank using Heterogeneous Treatment Effect Estimation
Venue: arXiv cs.IR 2020
Year: 2020

Learning-to-Rank (LTR) models trained from implicit feedback (e.g. clicks) suffer from inherent biases. A well-known one is the position bias -- documents in top positions are more likely to receive clicks due in part to their position advantages. To unbiasedly learn to rank, existing counterfactual frameworks first estimate the propensity (probability) of missing clicks with intervention data from a small portion of search traffic, and then use inverse propensity score (IPS) to debias LTR algorithms on the whole data set. These approaches often assume the propensity only depends on the position of the document, which may cause high estimation variance in applications where the search context (e.g. query, user) varies frequently. While context-dependent propensity models reduce variance, accurate estimations may require randomization or intervention on a large amount of traffic, which may not be realistic in real-world systems, especially for long tail queries. In this work, we employ heterogeneous treatment effect estimation techniques to estimate position bias when intervention click data is limited. We then use such estimations to debias the observed click distribution and re-draw a new de-biased data set, which can be used for any LTR algorithms. We conduct simulations with varying experiment conditions and show the effectiveness of the proposed method in regimes with long tail queries and sparse clicks.
Estimation for High-Dimensional Multi-Layer Generalized Linear Model -- Part I: The Exact MMSE Estimator
Venue: arXiv cs.IT 2020
Year: 2020

This two-part work considers the minimum means square error (MMSE) estimation problem for a high dimensional multi-layer generalized linear model (ML-GLM), which resembles a feed-forward fully connected deep learning network in that each of its layer mixes up the random input with a known weighting matrix and activates the results via non-linear functions, except that the activation here is stochastic and following some random distribution. Part I of the work focuses on the exact MMSE estimator, whose implementation is long known infeasible. For this exact estimator, an asymptotic analysis on the performance is carried out using a new replica method that is refined from certain aspects. A decoupling principle is then established, suggesting that, in terms of joint input-and-estimate distribution, the original estimation problem of multiple-input multiple-output is indeed identical to a simple single-input single-output one subjected to additive white Gaussian noise (AWGN) only. The variance of the AWGN is further shown to be determined by some coupled equations, whose dependency on the weighting and activation is given explicitly and analytically. Comparing to existing results, this paper is the first to offer a decoupling principle for the ML-GLM estimation problem. To further address the implementation issue of an exact solution, Part II proposes an approximate estimator, ML-GAMP, whose per-iteration complexity is as low as GAMP, while its asymptotic MSE (if converged) is as optimal as the exact MMSE estimator.
Migration and Refugee Crisis: a Critical Analysis of Online Public Perception
Venue: arXiv cs.SI 2020
Year: 2020

The migration rate and the level of resentments towards migrants are an important issue in modern civilisation. The infamous EU refugee crisis caught many countries unprepared, leading to sporadic and rudimentary containment measures that, in turn, led to significant public discourse. Decades of offline data collected via traditional survey methods have been utilised earlier to understand public opinion to foster peaceful coexistence. Capturing and understanding online public opinion via social media is crucial towards a joint strategic regulation spanning safety, rights of migrants and cordial integration for economic prosperity. We present a analysis of opinions on migrants and refugees expressed by the users of a very popular social platform, Twitter. We analyse sentiment and the associated context of expressions in a vast collection of tweets related to the EU refugee crisis. Our study reveals a marginally higher proportion of negative sentiments vis-a-vis migrants and a large proportion of the negative sentiments is more reflected among the ordinary users. Users with many followers and non-governmental organisations (NGO) tend to tweet favourably about the topic, offsetting the distribution of negative sentiment. We opine that they can be encouraged to be more proactive in neutralising negative attitudes that may arise concerning similar incidences.
A polynomial time 12-approximation algorithm for restricted Santa Claus problem
Venue: arXiv cs.DS 2020
Year: 2020

In this paper, we consider the restricted case of the problem and improve the current best approximation ratio by presenting a polynomial time 12-approximation algorithm using linear programming and semi-definite programming. Our algorithm starts by solving the configuration LP and uses the optimum value to get a 12-gap instance. This is then followed by the well-known clustering technique of Bansal and Sviridenko\cite{bansal}. We then apply the analysis of Asadpour \textit{et al.} \cite{AFS,AFS2} to show that the clustered instance has an integer solution which is at least $\frac{1}{6}$ times the best possible value, which was computed by solving the configuration LP. To find this solution, we formulate a problem called the Extended Assignment Problem, and formulate it as an LP. We then, show that the associated polytope is integral and gives us an fractional solution of value at least $\frac{1}{6}$ times the optimum. From this solution we find a solution to a new quadratic program that we introduce to select one machine from each cluster, and then we show that the resulting instance has an Assignment LP fractional solution of value at least $\frac{1}{6}$ times the optimum. We then use the well known rounding technique due to Bezakova and Dani \cite{bezakova} on the 12-gap instance to get our 12-approximate solution.
Why Research on Test-Driven Development is Inconclusive?
Venue: arXiv cs.SE 2020
Year: 2020

[Background] Recent investigations into the effects of Test-Driven Development (TDD) have been contradictory and inconclusive. This hinders development teams to use research results as the basis for deciding whether and how to apply TDD. [Aim] To support researchers when designing a new study and to increase the applicability of TDD research in the decision-making process in the industrial context, we aim at identifying the reasons behind the inconclusive research results in TDD. [Method] We studied the state of the art in TDD research published in top venues in the past decade, and analyzed the way these studies were set up. [Results] We identified five categories of factors that directly impact the outcome of studies on TDD. [Conclusions] This work can help researchers to conduct more reliable studies, and inform practitioners of risks they need to consider when consulting research on TDD.
DeepCO: Offline Combinatorial Optimization Framework Utilizing Deep Learning
Venue: arXiv cs.LG 2020
Year: 2020

Combinatorial optimization serves as an essential part in many modern industrial applications. A great number of the problems are offline setting due to safety and/or cost issues. While simulation-based approaches appear difficult to realise for complicated systems, in this research, we propose DeepCO, an offline combinatorial optimization framework utilizing deep learning. We also design an offline variation of Travelling Salesman Problem (TSP) to model warehouse operation sequence optimization problem for evaluation. With only limited historical data, novel proposed distribution regularized optimization method outperforms existing baseline method in offline TSP experiment reducing route length by 5.7% averagely and shows great potential in real world problems.
Complementary Boundary Generator with Scale-Invariant Relation Modeling for Temporal Action Localization: Submission to ActivityNet Challenge 2020
Venue: arXiv cs.CV 2020
Year: 2020

This technical report presents an overview of our solution used in the submission to ActivityNet Challenge 2020 Task 1 (\textbf{temporal action localization/detection}). Temporal action localization requires to not only precisely locate the temporal boundaries of action instances, but also accurately classify the untrimmed videos into specific categories. In this paper, we decouple the temporal action localization task into two stages (i.e. proposal generation and classification) and enrich the proposal diversity through exhaustively exploring the influences of multiple components from different but complementary perspectives. Specifically, in order to generate high-quality proposals, we consider several factors including the video feature encoder, the proposal generator, the proposal-proposal relations, the scale imbalance, and ensemble strategy. Finally, in order to obtain accurate detections, we need to further train an optimal video classifier to recognize the generated proposals. Our proposed scheme achieves the state-of-the-art performance on the temporal action localization task with \textbf{42.26} average mAP on the challenge testing set.
On Distribution Testing in the Conditional Sampling Model
Venue: arXiv cs.DS 2020
Year: 2020

Recently, there has been significant work studying distribution testing under the Conditional Sampling model. In this model, a query specifies a subset $S$ of the domain, and the output received is a sample drawn from the distribution conditioned on being in $S$. In this paper, we improve query complexity bounds for several classic distribution testing problems in this model. First, we prove that tolerant uniformity testing in the conditional sampling model can be solved using $\tilde{O}(\varepsilon^{-2})$ queries, which is optimal and improves upon the $\tilde{O}(\varepsilon^{-20})$-query algorithm of Canonne et al. [CRS15]. This bound even holds under a restricted version of the conditional sampling model called the Pair Conditional Sampling model. Next, we prove that tolerant identity testing in the conditional sampling model can be solved in $\tilde{O}(\varepsilon^{-4})$ queries, which is the first known bound independent of the support size of the distribution for this problem. Next, we use our algorithm for tolerant uniformity testing to get an $\tilde{O}(\varepsilon^{-4})$-query algorithm for monotonicity testing in the conditional sampling model, improving on the $\tilde{O}(\varepsilon^{-22})$-query algorithm of Canonne [Can15]. Finally, we study (non-tolerant) identity testing under the pair conditional sampling model, and provide a tight bound of $\tildeΘ(\sqrt{\log N} \cdot \varepsilon^{-2})$ for the query complexity, where the domain of the distribution has size $N$. This improves upon both the known upper and lower bounds in [CRS15].
MKLpy: a python-based framework for Multiple Kernel Learning
Venue: arXiv cs.LG 2020
Year: 2020

Multiple Kernel Learning is a recent and powerful paradigm to learn the kernel function from data. In this paper, we introduce MKLpy, a python-based framework for Multiple Kernel Learning. The library provides Multiple Kernel Learning algorithms for classification tasks, mechanisms to compute kernel functions for different data types, and evaluation strategies. The library is meant to maximize the usability and to simplify the development of novel solutions.
On the Comparison of Classic and Deep Keypoint Detector and Descriptor Methods
Venue: arXiv cs.CV 2020
Year: 2020

The purpose of this study is to give a performance comparison between several classic hand-crafted and deep key-point detector and descriptor methods. In particular, we consider the following classical algorithms: SIFT, SURF, ORB, FAST, BRISK, MSER, HARRIS, KAZE, AKAZE, AGAST, GFTT, FREAK, BRIEF and RootSIFT, where a subset of all combinations is paired into detector-descriptor pipelines. Additionally, we analyze the performance of two recent and perspective deep detector-descriptor models, LF-Net and SuperPoint. Our benchmark relies on the HPSequences dataset that provides real and diverse images under various geometric and illumination changes. We analyze the performance on three evaluation tasks: keypoint verification, image matching and keypoint retrieval. The results show that certain classic and deep approaches are still comparable, with some classic detector-descriptor combinations overperforming pretrained deep models. In terms of the execution times of tested implementations, SuperPoint model is the fastest, followed by ORB. The source code is published on \url{https://github.com/kristijanbartol/keypoint-algorithms-benchmark}.
Reconfigurable Intelligent Surfaces for the Connectivity of Autonomous Vehicles
Venue: arXiv cs.NI 2020
Year: 2020

The use of real-time software-controlled reconfigurable intelligent surface (RIS) units is proposed to increase the reliability of vehicle-to-everything (V2X) communications. The optimum placement problem of the RIS units is formulated by considering their sizes and operating modes. The solution of the problem is given, where it is shown that the placement of the RIS depends on the locations of the transmitter and the receiver. The proposed RIS-supported highway deployment can combat the high path loss experienced by the use of higher frequency bands, including the millimeter-wave and the terahertz bands, that are expected to be used in the next-generation wireless networks, enabling the use of the existing base station deployment plans to remain operational, while providing reliable and energy-efficient connectivity for autonomous vehicles.
Morphological Skip-Gram: Using morphological knowledge to improve word representation
Venue: arXiv cs.CL 2020
Year: 2020

Natural language processing models have attracted much interest in the deep learning community. This branch of study is composed of some applications such as machine translation, sentiment analysis, named entity recognition, question and answer, and others. Word embeddings are continuous word representations, they are an essential module for those applications and are generally used as input word representation to the deep learning models. Word2Vec and GloVe are two popular methods to learn word embeddings. They achieve good word representations, however, they learn representations with limited information because they ignore the morphological information of the words and consider only one representation vector for each word. This approach implies that Word2Vec and GloVe are unaware of the word inner structure. To mitigate this problem, the FastText model represents each word as a bag of characters n-grams. Hence, each n-gram has a continuous vector representation, and the final word representation is the sum of its characters n-grams vectors. Nevertheless, the use of all n-grams character of a word is a poor approach since some n-grams have no semantic relation with their words and increase the amount of potentially useless information. This approach also increases the training phase time. In this work, we propose a new method for training word embeddings, and its goal is to replace the FastText bag of character n-grams for a bag of word morphemes through the morphological analysis of the word. Thus, words with similar context and morphemes are represented by vectors close to each other. To evaluate our new approach, we performed intrinsic evaluations considering 15 different tasks, and the results show a competitive performance compared to FastText.
Quadrilateral meshes for PSLGs
Venue: arXiv cs.CG 2020
Year: 2020

We prove that every planar straight line graph with $n$ vertices has a conforming quadrilateral mesh with $O(n^2)$ elements, all angles $\leq 120^\circ$ and all new angles $\geq 60^\circ$. Both the complexity and the angle bounds are sharp. Moreover, all but $O(n)$ of the angles may be taken in a smaller interval, say $[89^\circ, 91^\circ]$.
Investigating Bias and Fairness in Facial Expression Recognition
Venue: arXiv cs.CV 2020
Year: 2020

Recognition of expressions of emotions and affect from facial images is a well-studied research problem in the fields of affective computing and computer vision with a large number of datasets available containing facial images and corresponding expression labels. However, virtually none of these datasets have been acquired with consideration of fair distribution across the human population. Therefore, in this work, we undertake a systematic investigation of bias and fairness in facial expression recognition by comparing three different approaches, namely a baseline, an attribute-aware and a disentangled approach, on two well-known datasets, RAF-DB and CelebA. Our results indicate that: (i) data augmentation improves the accuracy of the baseline model, but this alone is unable to mitigate the bias effect; (ii) both the attribute-aware and the disentangled approaches fortified with data augmentation perform better than the baseline approach in terms of accuracy and fairness; (iii) the disentangled approach is the best for mitigating demographic bias; and (iv) the bias mitigation strategies are more suitable in the existence of uneven attribute distribution or imbalanced number of subgroup data.
A Big Data Approach for Sequences Indexing on the Cloud via Burrows Wheeler Transform
Venue: arXiv cs.DC 2020
Year: 2020

Indexing sequence data is important in the context of Precision Medicine, where large amounts of ``omics'' data have to be daily collected and analyzed in order to categorize patients and identify the most effective therapies. Here we propose an algorithm for the computation of Burrows Wheeler transform relying on Big Data technologies, i.e., Apache Spark and Hadoop. Our approach is the first that distributes the index computation and not only the input dataset, allowing to fully benefit of the available cloud resources.
Push, Stop, and Replan: An Application of Pebble Motion on Graphs to Planning in Automated Warehouses
Venue: arXiv cs.RO 2020
Year: 2020

The pebble-motion on graphs is a subcategory of multi-agent pathfinding problems dealing with moving multiple pebble-like objects from a node to a node in a graph with a constraint that only one pebble can occupy one node at a given time. Additionally, algorithms solving this problem assume that individual pebbles (robots) cannot move at the same time and their movement is discrete. These assumptions disqualify them from being directly used in practical applications, although they have otherwise nice theoretical properties. We present modifications of the Push and Rotate algorithm [1], which relax the presumptions mentioned above and demonstrate, through a set of experiments, that the modified algorithm is applicable for planning in automated warehouses.
The Price of Anarchy of Two-Buyer Sequential Multiunit Auctions
Venue: arXiv cs.GT 2020
Year: 2020

We study the efficiency of sequential multiunit auctions with two-buyers and complete information. For general valuation functions, we show that the price of anarchy is exactly $1/T$ for auctions with $T$ items for sale. For concave valuation functions, we show that the price of anarchy is bounded below by $1-1/e\simeq 0.632$. This bound is asymptotically tight as the number of items sold tends to infinity.