OpenRaiser/Intern-Atlas huggingface dataset:
Real-time Travel Time Estimation Using Matrix Factorization
Venue: arXiv cs.LG 2019
Year: 2019

Estimating the travel time of any route is of great importance for trip planners, traffic operators, online taxi dispatching and ride-sharing platforms, and navigation provider systems. With the advance of technology, many traveling cars, including online taxi dispatch systems' vehicles are equipped with Global Positioning System (GPS) devices that can report the location of the vehicle every few seconds. This paper uses GPS data and the Matrix Factorization techniques to estimate the travel times on all road segments and time intervals simultaneously. We aggregate GPS data into a matrix, where each cell of the original matrix contains the average vehicle speed for a segment and a specific time interval. One of the problems with this matrix is its high sparsity. We use Alternating Least Squares (ALS) method along with a regularization term to factorize the matrix. Since this approach can solve the sparsity problem that arises from the absence of cars in many road segments in a specific time interval, matrix factorization is suitable for estimating the travel time. Our comprehensive evaluation results using real data provided by one of the largest online taxi dispatching systems in Iran, shows the strength of our proposed method.
Optimization for Reinforcement Learning: From Single Agent to Cooperative Agents
Venue: arXiv cs.LG 2019
Year: 2019

This article reviews recent advances in multi-agent reinforcement learning algorithms for large-scale control systems and communication networks, which learn to communicate and cooperate. We provide an overview of this emerging field, with an emphasis on the decentralized setting under different coordination protocols. We highlight the evolution of reinforcement learning algorithms from single-agent to multi-agent systems, from a distributed optimization perspective, and conclude with future directions and challenges, in the hope to catalyze the growing synergy among distributed optimization, signal processing, and reinforcement learning communities.
BlockLot: Blockchain based Verifiable Lottery
Venue: arXiv cs.DC 2019
Year: 2019

We propose BlockLot, a blockchain based verifiable lottery. BlockLot provides transparent, immutable, fair, and verifiable lottery services enhanced by recent blockchain technologies such as append-only (replicated) distributed ledger and smart contract. In addition, BlockLot allows all participants to perform various verification to ensure that the system is actually working as expected. We implement BlockLot services which includes open, query, subscribe, and draw in smart contracts. We also develop webbased user interface for using the lottery services provided by BlockLot. The web interface allows the user to verify the lottery as well.
Discovery and Separation of Features for Invariant Representation Learning
Venue: arXiv cs.LG 2019
Year: 2019

Supervised machine learning models often associate irrelevant nuisance factors with the prediction target, which hurts generalization. We propose a framework for training robust neural networks that induces invariance to nuisances through learning to discover and separate predictive and nuisance factors of data. We present an information theoretic formulation of our approach, from which we derive training objectives and its connections with previous methods. Empirical results on a wide array of datasets show that the proposed framework achieves state-of-the-art performance, without requiring nuisance annotations during training.
Noisy, Greedy and Not So Greedy k-means++
Venue: arXiv cs.DS 2019
Year: 2019

The k-means++ algorithm due to Arthur and Vassilvitskii has become the most popular seeding method for Lloyd's algorithm. It samples the first center uniformly at random from the data set and the other $k-1$ centers iteratively according to $D^2$-sampling where the probability that a data point becomes the next center is proportional to its squared distance to the closest center chosen so far. k-means++ is known to achieve an approximation factor of $O(\log k)$ in expectation. Already in the original paper on k-means++, Arthur and Vassilvitskii suggested a variation called greedy k-means++ algorithm in which in each iteration multiple possible centers are sampled according to $D^2$-sampling and only the one that decreases the objective the most is chosen as a center for that iteration. It is stated as an open question whether this also leads to an $O(\log k)$-approximation (or even better). We show that this is not the case by presenting a family of instances on which greedy k-means++ yields only an $Ω(\ell\cdot \log k)$-approximation in expectation where $\ell$ is the number of possible centers that are sampled in each iteration. We also study a variation, which we call noisy k-means++ algorithm. In this variation only one center is sampled in every iteration but not exactly by $D^2$-sampling anymore. Instead in each iteration an adversary is allowed to change the probabilities arising from $D^2$-sampling individually for each point by a factor between $1-ε_1$ and $1+ε_2$ for parameters $ε_1 \in [0,1)$ and $ε_2 \ge 0$. We prove that noisy k-means++ compute an $O(\log^2 k)$-approximation in expectation. We also discuss some applications of this result.
ReD-CaNe: A Systematic Methodology for Resilience Analysis and Design of Capsule Networks under Approximations
Venue: arXiv cs.LG 2019
Year: 2019

Recent advances in Capsule Networks (CapsNets) have shown their superior learning capability, compared to the traditional Convolutional Neural Networks (CNNs). However, the extremely high complexity of CapsNets limits their fast deployment in real-world applications. Moreover, while the resilience of CNNs have been extensively investigated to enable their energy-efficient implementations, the analysis of CapsNets' resilience is a largely unexplored area, that can provide a strong foundation to investigate techniques to overcome the CapsNets' complexity challenge. Following the trend of Approximate Computing to enable energy-efficient designs, we perform an extensive resilience analysis of the CapsNets inference subjected to the approximation errors. Our methodology models the errors arising from the approximate components (like multipliers), and analyze their impact on the classification accuracy of CapsNets. This enables the selection of approximate components based on the resilience of each operation of the CapsNet inference. We modify the TensorFlow framework to simulate the injection of approximation noise (based on the models of the approximate components) at different computational operations of the CapsNet inference. Our results show that the CapsNets are more resilient to the errors injected in the computations that occur during the dynamic routing (the softmax and the update of the coefficients), rather than other stages like convolutions and activation functions. Our analysis is extremely useful towards designing efficient CapsNet hardware accelerators with approximate components. To the best of our knowledge, this is the first proof-of-concept for employing approximations on the specialized CapsNet hardware.
PTAS for Steiner Tree on Map Graphs
Venue: arXiv cs.DS 2019
Year: 2019

We study the Steiner tree problem on map graphs, which substantially generalize planar graphs as they allow arbitrarily large cliques. We obtain a PTAS for Steiner tree on map graphs, which builds on the result for planar edge weighted instances of Borradaile et al. The Steiner tree problem on map graphs can be casted as a special case of the planar node-weighted Steiner tree problem, for which only a 2.4-approximation is known. We prove and use a contraction decomposition theorem for planar node weighted instances. This readily reduces the problem of finding a PTAS for planar node-weighted Steiner tree to finding a spanner, i.e., a constant-factor approximation containing a nearly optimum solution. Finally, we pin-point places where known techniques for constructing such spanner fail on node weighted instances and further progress requires new ideas.
On the Equilibria and Efficiency of Electricity Markets with Renewable Power Producers and Congestion Constraints
Venue: arXiv cs.GT 2019
Year: 2019

With increasing renewable penetration in power systems, a prominent challenge in efficient and reliable power system operation is handling the uncertainties inherent in the renewable generation. In this paper, we propose a simple two-settlement market mechanism in which renewable power producers (RPPs) participate, so that a) the independent system operator (ISO) does not need to consider the uncertainties of the renewables in its economic dispatch, and yet b) the market equilibrium is shown to approach social efficiency as if the ISO solves a stochastic optimization taking into account all the uncertainties. In showing this result, a key innovation is a new approach of efficiently computing the Nash equilibrium (NE) among the strategic RPPs in congestion-constrained power networks. In particular, the proposed approach decouples finding an NE into searching over congestion patterns and computing an NE candidate assuming a congestion pattern. As such, the computational complexity of finding an NE grows only cubically with the number of RPPs in the market. We demonstrate our results in the IEEE 14-bus system and show that the NE approaches social efficiency as the number of RPPs grows.
Using Laplacian Spectrum as Graph Feature Representation
Venue: arXiv cs.LG 2019
Year: 2019

Graphs possess exotic features like variable size and absence of natural ordering of the nodes that make them difficult to analyze and compare. To circumvent this problem and learn on graphs, graph feature representation is required. A good graph representation must satisfy the preservation of structural information, with two particular key attributes: consistency under deformation and invariance under isomorphism. While state-of-the-art methods seek such properties with powerful graph neural-networks, we propose to leverage a simple graph feature: the graph Laplacian spectrum (GLS). We first remind and show that GLS satisfies the aforementioned key attributes, using a graph perturbation approach. In particular, we derive bounds for the distance between two GLS that are related to the \textit{divergence to isomorphism}, a standard computationally expensive graph divergence. We finally experiment GLS as graph representation through consistency tests and classification tasks, and show that it is a strong graph feature representation baseline.
SemEval-2017 Task 4: Sentiment Analysis in Twitter
Venue: arXiv cs.CL 2019
Year: 2019

This paper describes the fifth year of the Sentiment Analysis in Twitter task. SemEval-2017 Task 4 continues with a rerun of the subtasks of SemEval-2016 Task 4, which include identifying the overall sentiment of the tweet, sentiment towards a topic with classification on a two-point and on a five-point ordinal scale, and quantification of the distribution of sentiment towards a topic across a number of tweets: again on a two-point and on a five-point ordinal scale. Compared to 2016, we made two changes: (i) we introduced a new language, Arabic, for all subtasks, and (ii)~we made available information from the profiles of the Twitter users who posted the target tweets. The task continues to be very popular, with a total of 48 teams participating this year.
On the Legal Compatibility of Fairness Definitions
Venue: arXiv cs.CY 2019
Year: 2019

Past literature has been effective in demonstrating ideological gaps in machine learning (ML) fairness definitions when considering their use in complex socio-technical systems. However, we go further to demonstrate that these definitions often misunderstand the legal concepts from which they purport to be inspired, and consequently inappropriately co-opt legal language. In this paper, we demonstrate examples of this misalignment and discuss the differences in ML terminology and their legal counterparts, as well as what both the legal and ML fairness communities can learn from these tensions. We focus this paper on U.S. anti-discrimination law since the ML fairness research community regularly references terms from this body of law.
Time-Guided High-Order Attention Model of Longitudinal Heterogeneous Healthcare Data
Venue: arXiv cs.LG 2019
Year: 2019

Due to potential applications in chronic disease management and personalized healthcare, the EHRs data analysis has attracted much attention of both researchers and practitioners. There are three main challenges in modeling longitudinal and heterogeneous EHRs data: heterogeneity, irregular temporality and interpretability. A series of deep learning methods have made remarkable progress in resolving these challenges. Nevertheless, most of existing attention models rely on capturing the 1-order temporal dependencies or 2-order multimodal relationships among feature elements. In this paper, we propose a time-guided high-order attention (TGHOA) model. The proposed method has three major advantages. (1) It can model longitudinal heterogeneous EHRs data via capturing the 3-order correlations of different modalities and the irregular temporal impact of historical events. (2) It can be used to identify the potential concerns of medical features to explain the reasoning process of the healthcare model. (3) It can be easily expanded into cases with more modalities and flexibly applied in different prediction tasks. We evaluate the proposed method in two tasks of mortality prediction and disease ranking on two real world EHRs datasets. Extensive experimental results show the effectiveness of the proposed model.
Follow the Flow: sets, relations, and categories as special cases of functions with no domain
Venue: arXiv cs.LO 2019
Year: 2019

We introduce, develop, and apply a new approach for dealing with the intuitive notion of function, called Flow Theory. Within our framework all functions are monadic and none of them has any domain. Sets, proper classes, categories, functors, and even relations are special cases of functions. In this sense, functions in Flow are not equivalent to functions in ZFC. Nevertheless, we prove both ZFC and Category Theory are naturally immersed within Flow. Besides, our framework provides major advantages as a language for axiomatization of standard mathematical and physical theories. Russell's paradox is avoided without any equivalent to the Separation Scheme. Hierarchies of sets are obtained without any equivalent to the Power Set Axiom. And a clear principle of duality emerges from Flow, in a way which was not anticipated neither by Category Theory nor by standard set theories. Besides, there seems to be within Flow an identification not only with the common practice of doing mathematics (which is usually quite different from the ways proposed by logicians), but even with the common practice of teaching this formal science.
Information bottleneck through variational glasses
Venue: arXiv cs.CV 2019
Year: 2019

Information bottleneck (IB) principle [1] has become an important element in information-theoretic analysis of deep models. Many state-of-the-art generative models of both Variational Autoencoder (VAE) [2; 3] and Generative Adversarial Networks (GAN) [4] families use various bounds on mutual information terms to introduce certain regularization constraints [5; 6; 7; 8; 9; 10]. Accordingly, the main difference between these models consists in add regularization constraints and targeted objectives. In this work, we will consider the IB framework for three classes of models that include supervised, unsupervised and adversarial generative models. We will apply a variational decomposition leading a common structure and allowing easily establish connections between these models and analyze underlying assumptions. Based on these results, we focus our analysis on unsupervised setup and reconsider the VAE family. In particular, we present a new interpretation of VAE family based on the IB framework using a direct decomposition of mutual information terms and show some interesting connections to existing methods such as VAE [2; 3], beta-VAE [11], AAE [12], InfoVAE [5] and VAE/GAN [13]. Instead of adding regularization constraints to an evidence lower bound (ELBO) [2; 3], which itself is a lower bound, we show that many known methods can be considered as a product of variational decomposition of mutual information terms in the IB framework. The proposed decomposition might also contribute to the interpretability of generative models of both VAE and GAN families and create a new insights to a generative compression [14; 15; 16; 17]. It can also be of interest for the analysis of novelty detection based on one-class classifiers [18] with the IB based discriminators.
EMAP: Explanation by Minimal Adversarial Perturbation
Venue: arXiv cs.LG 2019
Year: 2019

Modern instance-based model-agnostic explanation methods (LIME, SHAP, L2X) are of great use in data-heavy industries for model diagnostics, and for end-user explanations. These methods generally return either a weighting or subset of input features as an explanation of the classification of an instance. An alternative literature argues instead that counterfactual instances provide a more useable characterisation of a black box classifier's decisions. We present EMAP, a neural network based approach which returns as Explanation the Minimal Adversarial Perturbation to an instance required to cause the underlying black box model to missclassify. We show that this approach combines the two paradigms, recovering the output of feature-weighting methods in continuous feature spaces, whilst also indicating the direction in which the nearest counterfactuals can be found. Our method also provides an implicit confidence estimate in its own explanations, adding a clarity to model diagnostics other methods lack. Additionally, EMAP improves upon the speed of sampling-based methods such as LIME by an order of magnitude, allowing for model explanations in time-critical applications, or at the dataset level, where sampling-based methods are infeasible. We extend our approach to categorical features using a partitioned Gumbel layer, and demonstrate its efficacy on several standard datasets.
Online information of vaccines: information quality is an ethical responsibility of search engines
Venue: arXiv cs.SI 2019
Year: 2019

The fact that internet companies may record our personal data and track our online behavior for commercial or political purpose has emphasized aspects related to online privacy. This has also led to the development of search engines that promise no tracking and privacy. Search engines also have a major role in spreading low-quality health information such as that of anti-vaccine websites. This study investigates the relationship between search engines' approach to privacy and the scientific quality of the information they return. We analyzed the first 30 webpages returned searching 'vaccines autism' in English, Spanish, Italian and French. The results show that alternative search engines (Duckduckgo, Ecosia, Qwant, Swisscows and Mojeek) may return more anti-vaccine pages (10 to 53 percent) than Google.com (zero). Some localized versions of Google, however, returned more anti-vaccine webpages (up to 10 percent) than Google.com. Our study suggests that designing a search engine that is privacy savvy and avoids issues with filter bubbles that can result from user tracking is necessary but insufficient; instead, mechanisms should be developed to test search engines from the perspective of information quality (particularly for health-related webpages), before they can be deemed trustworthy providers of public health information.
Properties of nowhere dense graph classes related to independent set problem
Venue: arXiv cs.DS 2019
Year: 2019

A set is called r-independent, if every two vertices of it are in distance greater then r. In the r-independent set problem with parameter k, we ask whether in a given graph G there exists an r-independent set of size k. In this work we present an algorithm for this problem, which applied to a graph from any fixed nowhere dense class, works in time bounded by f(k, r)*G, for some function f. We also present alternative algorithm, with running time bounded by g(k, r)*G, working on slightly more general classes of graphs.
GPU Algorithm for Earliest Arrival Time Problem in Public Transport Networks
Venue: arXiv cs.DC 2019
Year: 2019

Given a temporal graph G, a source vertex s, and a departure time at source vertex t_s, the earliest arrival time problem EAT is to start from s on or after t_s and reach all the vertices in G as early as possible. Ni et al. have proposed a parallel algorithm for EAT and obtained a speedup up to 9.5 times on real-world graphs with respect to the connection-scan serial algorithm by using multi-core processors. We propose a topology-driven parallel algorithm for EAT on public transport networks and implement using general-purpose programming on the graphics processing unit GPU. A temporal edge or connection in a temporal graph for a public transport network is associated with a departure time and a duration time, and many connections exist from u to v for an edge (u,v). We propose two pruning techniques connection-type and clustering, and use arithmetic progression technique appropriately to process many connections of an edge, without scanning all of them. In the connection-type technique, the connections of an edge with the same duration are grouped together. In the clustering technique, we follow 24-hour format and the connections of an edge are partitioned into 24 clusters so that the departure time of connections in the i^{th} cluster is at least i-hour and at most i+1-hour. The arithmetic progression technique helps to store a sequence of departure times of various connections in a compact way. We propose a hybrid approach to combine the three techniques connection-type, clustering and arithmetic progression in an appropriate way. Our techniques achieve an average speedup up to 59.09 times when compared to the existing connection-scan serial algorithm running on CPU. Also, the average speedup of our algorithm is 12.48 times against the parallel edge-scan-dependency graph algorithm running on GPU.
Towards a Formal Model for Composable Container Systems
Venue: arXiv cs.LO 2019
Year: 2019

In modern cloud-based architectures, containers play a central role: they provide powerful isolation mechanisms such that developers can focus on the logic and dependencies of applications while system administrators can focus on deployment and management issue. In this work, we propose a formal model for container-based systems, using the framework of Bigraphical Reactive Systems (BRSs). We first introduce local directed bigraphs, a graph-based formalism which allows us to deal with localized resources. Then, we define a signature for modelling containers and provide some examples of bigraphs modelling containers. These graphs can be analysed and manipulated using techniques from graph theory: properties about containers can be formalized as properties of the corresponding bigraphic representations. Moreover, it turns out that the composition of containers as performed by e.g. docker-compose, corresponds precisely to the composition of the corresponding bigraphs inside an ``environment bigraph'' which in turn is obtained directly from the YAML file used to define the composition of containers.