OpenRaiser/Intern-Atlas huggingface dataset:
Intelligent social bots uncover the link between user preference and diversity of news consumption
Venue: arXiv cs.SI 2019
Year: 2019

The boom of online social media and microblogging platforms has rapidly alter the way we consume news and exchange opinions. Even though considerable efforts try to recommend various contents to users, loss of information diversity and the polarization of interest groups are still an enormous challenge for industry and academia. Here, we take advantage of benign social bots to design a controlled experiment on Weibo (the largest microblogging platform in China). These software bots can exhibit human-like behavior (e.g., preferring particular content) and simulate the formation of personal social networks and news consumption under two well-accepted sociological hypotheses (i.e., homophily and triadic closure). We deployed 68 bots to Weibo, and each bot ran for at least 2 months and followed 100 to 120 accounts. In total, we observed 5,318 users and recorded about 630,000 messages exposed to these bots. Our results show, even with the same selection behaviors, bots preferring entertainment content are more likely to form polarized communities with their peers, in which about 80\% of the information they consume is of the same type, which is a significant difference for bots preferring sci-tech content. The result suggests that users preference played a more crucial role in limiting themselves access to diverse content by compared with the two well-known drivers (self-selection and pre-selection). Furthermore, our results reveal an ingenious connection between specific content and its propagating sub-structures in the same social network. In the Weibo network, entertainment news favors a unidirectional star-like sub-structure, while sci-tech news spreads on a bidirectional clustering sub-structure. This connection can amplify the diversity effect of user preference. The discovery may have important implications for diffusion dynamics study and recommendation system design.
Unsupervised Anomaly Localization using Variational Auto-Encoders
Venue: arXiv cs.LG 2019
Year: 2019

An assumption-free automatic check of medical images for potentially overseen anomalies would be a valuable assistance for a radiologist. Deep learning and especially Variational Auto-Encoders (VAEs) have shown great potential in the unsupervised learning of data distributions. In principle, this allows for such a check and even the localization of parts in the image that are most suspicious. Currently, however, the reconstruction-based localization by design requires adjusting the model architecture to the specific problem looked at during evaluation. This contradicts the principle of building assumption-free models. We propose complementing the localization part with a term derived from the Kullback-Leibler (KL)-divergence. For validation, we perform a series of experiments on FashionMNIST as well as on a medical task including >1000 healthy and >250 brain tumor patients. Results show that the proposed formalism outperforms the state of the art VAE-based localization of anomalies across many hyperparameter settings and also shows a competitive max performance.
AI-based evaluation of the SDGs: The case of crop detection with earth observation data
Venue: arXiv cs.CV 2019
Year: 2019

The framework of the seventeen sustainable development goals is a challenge for developers and researchers applying artificial intelligence (AI). AI and earth observations (EO) can provide reliable and disaggregated data for better monitoring of the sustainable development goals (SDGs). In this paper, we present an overview of SDG targets, which can be effectively measured with AI tools. We identify indicators with the most significant contribution from the AI and EO and describe an application of state-of-the-art machine learning models to one of the indicators. We describe an application of U-net with SE blocks for efficient segmentation of satellite imagery for crop detection. Finally, we demonstrate how AI can be more effectively applied in solutions directly contributing towards specific SDGs and propose further research on an AI-based evaluative infrastructure for SDGs.
Truly Concurrent Bisimilarities are Game Equivalent
Venue: arXiv cs.LO 2019
Year: 2019

We design games for truly concurrent bisimilarities, including strongly truly concurrent bisimilarities and branching truly concurrent bisimilarities, such as pomset bisimilarities, step bisimilarities, history-preserving bisimilarities and hereditary history-preserving bisimilarities.
Genetic Network Architecture Search
Venue: arXiv cs.NE 2019
Year: 2019

We propose a method for learning the neural network architecture that based on Genetic Algorithm (GA). Our approach uses a genetic algorithm integrated with standard Stochastic Gradient Descent(SGD) which allows the sharing of weights across all architecture solutions. The method uses GA to design a sub-graph of Convolution cell which maximizes the accuracy on the validation-set. Through experiments, we demonstrate this methods performance on both CIFAR10 and CIFAR100 dataset with an accuracy of 96% and 80.1%. The code and result of this work available in GitHub:https://github.com/haihabi/GeneticNAS.
From LTL to Unambiguous Büchi Automata via Disambiguation of Alternating Automata
Venue: arXiv cs.FL 2019
Year: 2019

This paper proposes a new algorithm for the generation of unambiguous Büchi automata (UBA) from LTL formulas. Unlike existing tableau-based LTL-to-UBA translations, our algorithm deals with very weak alternating automata (VWAA) as an intermediate representation. It relies on a new notion of unambiguity for VWAA and a disambiguation procedure for VWAA. We introduce optimizations on the VWAA level and new LTL simplifications targeted at generating small UBA. We report on an implementation of the construction in our tool duggi and discuss experimental results that compare the automata sizes and computation times of duggi with the tableau-based LTL-to-UBA translation of the SPOT tool set. Our experiments also cover the analysis of Markov chains under LTL specifications, which is an important application of UBA.
RegDem: Increasing GPU Performance via Shared Memory Register Spilling
Venue: arXiv cs.PF 2019
Year: 2019

GPU utilization, measured as occupancy, is limited by the parallel threads' combined usage of on-chip resources, such as registers and the programmer-managed shared memory. Higher resource demand means lower effective parallel thread count, and therefore lower program performance. Our investigation found that registers are often the occupancy limiters. The de-facto nvcc compiler-based approach spills excessive registers to the off-chip memory, ignoring the shared memory and leaving the on-chip resources underutilized. To mitigate the register demand, this paper presents a binary translation technique, called RegDem, that spills excessive registers to the underutilized shared memory by transforming the GPU assembly code (SASS). Most GPU programs do not fully use shared memory, thus allowing RegDem to use it for register spilling. The higher occupancy achieved by RegDem outweighs the slightly higher cost of accessing shared memory instead of placing data in registers. The paper also presents a compile-time performance predictor that models instructions stalls to choose the best version from a set of program variants. Cumulatively, these techniques outperform the nvcc compiler with a 9% geometric mean, the highest observed being 18%.
HashGraph -- Scalable Hash Tables Using A Sparse Graph Data Structure
Venue: arXiv cs.DS 2019
Year: 2019

Hash tables are ubiquitous and used in a wide range of applications for efficient probing of large and unsorted data. If designed properly, hash-tables can enable efficients look ups in a constant number of operations or commonly referred to as O(1) operations. As data sizes continue to grow and data becomes less structured (as is common for big-data applications), the need for efficient and scalable hash table also grows. In this paper we introduce HashGraph, a new scalable approach for building hash tables that uses concepts taken from sparse graph representations--hence the name HashGraph. We show two different variants of HashGraph, a simple algorithm that outlines the method to create the hash-table and an advanced method that creates the hash table in a more efficient manner (with an improved memory access pattern). HashGraph shows a new way to deal with hash-collisions that does not use "open-addressing" or "chaining", yet has all the benefits of both these approaches. HashGraph currently works for static inputs, though recent progress with dynamic graph data structures suggest that HashGraph might be extended to dynamic inputs as well. We show that HashGraph can deal with a large number of hash-values per entry without loss of performance as most open-addressing and chaining approaches have. Further, we show that HashGraph is indifferent to the load-factor. Lastly, we show a new probing algorithm for the second phase of value lookups. Given the above, HashGraph is extremely fast and outperforms several state of the art hash-table implementations. The implementation of HashGraph in this paper is for NVIDIA GPUs, though HashGraph is not architecture dependent. Using a NVIDIA GV100 GPU, HashGraph is anywhere from 2X-8X faster than cuDPP, WarpDrive, and cuDF. HashGraph is able to build a hash-table at a rate of 2.5 billion keys per second and can probe at nearly the same rate.
Weight-space symmetry in deep networks gives rise to permutation saddles, connected by equal-loss valleys across the loss landscape
Venue: arXiv cs.LG 2019
Year: 2019

The permutation symmetry of neurons in each layer of a deep neural network gives rise not only to multiple equivalent global minima of the loss function, but also to first-order saddle points located on the path between the global minima. In a network of $d-1$ hidden layers with $n_k$ neurons in layers $k = 1, \ldots, d$, we construct smooth paths between equivalent global minima that lead through a `permutation point' where the input and output weight vectors of two neurons in the same hidden layer $k$ collide and interchange. We show that such permutation points are critical points with at least $n_{k+1}$ vanishing eigenvalues of the Hessian matrix of second derivatives indicating a local plateau of the loss function. We find that a permutation point for the exchange of neurons $i$ and $j$ transits into a flat valley (or generally, an extended plateau of $n_{k+1}$ flat dimensions) that enables all $n_k!$ permutations of neurons in a given layer $k$ at the same loss value. Moreover, we introduce high-order permutation points by exploiting the recursive structure in neural network functions, and find that the number of $K^{\text{th}}$-order permutation points is at least by a factor $\sum_{k=1}^{d-1}\frac{1}{2!^K}{n_k-K \choose K}$ larger than the (already huge) number of equivalent global minima. In two tasks, we illustrate numerically that some of the permutation points correspond to first-order saddles (`permutation saddles'): first, in a toy network with a single hidden layer on a function approximation task and, second, in a multilayer network on the MNIST task. Our geometric approach yields a lower bound on the number of critical points generated by weight-space symmetries and provides a simple intuitive link between previous mathematical results and numerical observations.
On the Importance of demand Consolidation in Mobility on Demand
Venue: arXiv cs.NI 2019
Year: 2019

Mobility on Demand (MoD) services, like Uber and Lyft, are revolutionizing the way people move in cities around the world and are often considered a convenient alternative to public transit, since they offer higher Quality of Service (QoS - less waiting time, door-to-door service) at a cheap price. In the next decades, these advantages are expected to be further amplified by Automated MoD (AMoD), in which drivers will be replaced by automated vehicles, with a big gain in terms of cost-efficiency. MoD is usually intended as a door-to-door service. However, there has been recent interest toward consolidating, e.g., aggregating, the travel demand by limiting the number of admitted stop locations. This implies users have to walk from/to their intended origin/destination. The contribution of this paper is a systematic study the impact of consolidation on the operator cost and on user QoS. We introduce a MoD system where pick-ups and drop-offs can only occur in a limited subset of admitted stop locations. The density of such locations is a system parameter: the less the density, the more the user demand is consolidated. We show that, by decreasing stop density, we can increase system capacity (number of passengers we are able to serve). On the contrary, increasing it, we can improve QoS. The system is tested in AMoDSim, an open-source simulator. The code to reproduce the results presented here is available on-line. This work is a first step toward flexible mobility services that are able to autonomously re-configure themselves, favoring capacity or QoS, depending on the amount of travel demand coming from users. In other words, the services we envisage in this work shift their operational mode to any intermediate point in the range from a taxi-like door-to-door service to a bus-like service, with few served stops and more passengers on-board.
Visualizing Uncertainty and Saliency Maps of Deep Convolutional Neural Networks for Medical Imaging Applications
Venue: arXiv cs.LG 2019
Year: 2019

Deep learning models are now used in many different industries, while in certain domains safety is not a critical issue in the medical field it is a huge concern. Not only, we want the models to generalize well but we also want to know the models confidence respect to its decision and which features matter the most. Our team aims to develop a full pipeline in which not only displays the uncertainty of the models decision but also, the saliency map to show which sets of pixels of the input image contribute most to the predictions.
Kolmogorov's Algorithmic Mutual Information Is Equivalent to Bayes' Law
Venue: arXiv cs.IT 2019
Year: 2019

Given two events $A$ and $B$, Bayes' law is based on the argument that the probability of $A$ given $B$ is proportional to the probability of $B$ given $A$. When probabilities are interpreted in the Bayesian sense, Bayes' law constitutes a learning algorithm which shows how one can learn from a new observation to improve their belief in a theory that is consistent with that observation. Kolmogorov's notion of algorithmic information, which is based on the theory of algorithms, proposes an objective measure of the amount of information in a finite string about itself and concludes that for any two finite strings $x$ and $y$, the amount of information in $x$ about $y$ is almost equal to the amount of information in $y$ about $x$. We view this conclusion of Kolmogorov as the algorithmic information version of Bayes' law. This can be easily demonstrated if one considers the work of Levin on prefix Kolmogorov complexity and then expresses the amount of Kolmogorov mutual information between two finite strings using Solomonoff's a priori probability.
Solidity 0.5: when typed does not mean type safe
Venue: arXiv cs.PL 2019
Year: 2019

The recent release of Solidity 0.5 introduced a new type to prevent Ether transfers to smart contracts that are not supposed to receive money. Unfortunately, the compiler fails in enforcing the guarantees this type intended to convey, hence the type soundness of Solidity 0.5 is no better than that of Solidity 0.4. In this paper we discuss a paradigmatic example showing that vulnerable Solidity patterns based on potentially unsafe callback expressions are still unchecked. We also point out a solution that strongly relies on formal methods to support a type-safer smart contracts programming discipline, while being retro-compatible with legacy Solidity code.
Un Modelo Ontológico para el Gobierno Electrónico
Venue: arXiv cs.DL 2019
Year: 2019

Decision making often requires information that must be Provided with the rich data format. Addressing these new requirements appropriately makes it necessary for government agencies to orchestrate large amounts of information from different sources and formats, to be efficiently delivered through the devices commonly used by people, such as computers, netbooks, tablets and smartphones. To overcome these problems, a model is proposed for the conceptual representation of the State's organizational units, seen as georeferenced entities of Electronic Government, based on ontologies designed under the principles of Linked Open Data, which allows the automatic extraction of information through the machines, which supports the process of governmental decision making and gives citizens full access to find and process through mobile technologies.
MigrationMiner: An Automated Detection Tool of Third-Party Java Library Migration at the Method Level
Venue: arXiv cs.SE 2019
Year: 2019

In this paper we introduce, MigrationMiner, an automated tool that detects code migrations performed between Java third-party library. Given a list of open source projects, the tool detects potential library migration code changes and collects the specific code fragments in which the developer replaces methods from the retired library with methods from the new library. To support the migration process, MigrationMiner collects the library documentation that is associated with every method involved in the migration. We evaluate our tool on a benchmark of manually validated library migrations. Results show that MigrationMiner achieves an accuracy of 100%. A demo video of MigrationMiner is available at https://youtu.be/sAlR1HNetXc.
Global Aggregations of Local Explanations for Black Box models
Venue: arXiv cs.IR 2019
Year: 2019

The decision-making process of many state-of-the-art machine learning models is inherently inscrutable to the extent that it is impossible for a human to interpret the model directly: they are black box models. This has led to a call for research on explaining black box models, for which there are two main approaches. Global explanations that aim to explain a model's decision making process in general, and local explanations that aim to explain a single prediction. Since it remains challenging to establish fidelity to black box models in globally interpretable approximations, much attention is put on local explanations. However, whether local explanations are able to reliably represent the black box model and provide useful insights remains an open question. We present Global Aggregations of Local Explanations (GALE) with the objective to provide insights in a model's global decision making process. Overall, our results reveal that the choice of aggregation matters. We find that the global importance introduced by Local Interpretable Model-agnostic Explanations (LIME) does not reliably represent the model's global behavior. Our proposed aggregations are better able to represent how features affect the model's predictions, and to provide global insights by identifying distinguishing features.
Node-Constrained Traffic Engineering: Theory and Applications
Venue: arXiv cs.NI 2019
Year: 2019

Traffic engineering (TE) is a fundamental task in networking. Conventionally, traffic can take any path connecting the source and destination. Emerging technologies such as segment routing, however, use logical paths going through a predetermined set of middlepoints. Inspired by this, in this work we introduce the problem of node-constrained TE, where traffic must go through a set of middlepoints, and study its theoretical fundamentals. We show that the general node-constrained TE that constrains the traffic to take paths going through one or more middlepoints is NP-hard for directed graphs but strongly polynomial for undirected graphs, unveiling a profound dichotomy between the two cases. We additionally investigate the popular variant of node-constrained TE that uses shortest paths between middlepoints, and show that the problem can now be solved in weakly polynomial time for a fixed number of middlepoints. Yet if we constrain the end-to-end paths to be acyclic, the problem can become NP-hard. This explains why existing work focuses on the computationally tractable variant. An important application of our work concerns the computational complexity of flow centrality, first proposed in 1991 by Freeman et al. [21]: we show that it is NP-hard for directed but strongly polynomial for undirected graphs. Finally, we investigate the middlepoint selection problem in general node-constrained TE. We introduce group flow centrality as a solution concept for multi-commodity networks, study its complexity, and show that it is monotone but not submodular for both directed and undirected graphs. Our work provides a thorough theoretical treatment of node-constrained TE and its applications.
Short Text Conversation Based on Deep Neural Network and Analysis on Evaluation Measures
Venue: arXiv cs.CL 2019
Year: 2019

With the development of Natural Language Processing, Automatic question-answering system such as Waston, Siri, Alexa, has become one of the most important NLP applications. Nowadays, enterprises try to build automatic custom service chatbots to save human resources and provide a 24-hour customer service. Evaluation of chatbots currently relied greatly on human annotation which cost a plenty of time. Thus, has initiated a new Short Text Conversation subtask called Dialogue Quality (DQ) and Nugget Detection (ND) which aim to automatically evaluate dialogues generated by chatbots. In this paper, we solve the DQ and ND subtasks by deep neural network. We proposed two models for both DQ and ND subtasks which is constructed by hierarchical structure: embedding layer, utterance layer, context layer and memory layer, to hierarchical learn dialogue representation from word level, sentence level, context level to long range context level. Furthermore, we apply gating and attention mechanism at utterance layer and context layer to improve the performance. We also tried BERT to replace embedding layer and utterance layer as sentence representation. The result shows that BERT produced a better utterance representation than multi-stack CNN for both DQ and ND subtasks and outperform other models proposed by other researches. The evaluation measures are proposed by , that is, NMD, RSNOD for DQ and JSD, RNSS for ND, which is not traditional evaluation measures such as accuracy, precision, recall and f1-score. Thus, we have done a series of experiments by using traditional evaluation measures and analyze the performance and error.
Fusion-Based Cooperative Support Identification for Compressive Networked Sensing
Venue: arXiv cs.IT 2019
Year: 2019

This paper proposes a fusion-based cooperative support identification scheme for distributed compressive sparse signal recovery via resource-constrained wireless sensor networks. The proposed support identification protocol involves: (i) local sparse sensing for economizing data gathering and storage, (ii) local binary decision making for partial support knowledge inference, (iii) binary information exchange among active nodes, and (iv) binary data aggregation for support estimation. Then, with the aid of the estimated signal support, a refined local decision is made at each node. Only the measurements of those informative nodes will be sent to the fusion center, which employs a weighted $\ell_1$-minimization for global signal reconstruction. The design of a Bayesian local decision rule is discussed, and the average communication cost is analyzed. Computer simulations are used to illustrate the effectiveness of the proposed scheme.