OpenRaiser/Intern-Atlas huggingface dataset:
Implementing $\Diamond P$ with Bounded Messages on a Network of ADD Channels
Venue: arXiv cs.DC 2017
Year: 2017

We present an implementation of the eventually perfect failure detector ($\Diamond P$) from the original hierarchy of the Chandra-Toueg oracles on an arbitrary partitionable network composed of unreliable channels that can lose and reorder messages. Prior implementations of $\Diamond P$ have assumed different partially synchronous models ranging from bounded point-to-point message delay and reliable communication to unbounded message size and known network topologies. We implement $\Diamond P$ under very weak assumptions on an arbitrary, partitionable network composed of Average Delayed/Dropped (ADD) channels to model unreliable communication. Unlike older implementations, our failure detection algorithm uses bounded-sized messages to eventually detect all nodes that are unreachable (crashed or disconnected) from it.
The Tensor Memory Hypothesis
Venue: arXiv cs.AI 2017
Year: 2017

We discuss memory models which are based on tensor decompositions using latent representations of entities and events. We show how episodic memory and semantic memory can be realized and discuss how new memory traces can be generated from sensory input: Existing memories are the basis for perception and new memories are generated via perception. We relate our mathematical approach to the hippocampal memory indexing theory. We describe the first detailed mathematical models for the complete processing pipeline from sensory input and its semantic decoding, i.e., perception, to the formation of episodic and semantic memories and their declarative semantic decodings. Our main hypothesis is that perception includes an active semantic decoding process, which relies on latent representations of entities and predicates, and that episodic and semantic memories depend on the same decoding process. We contribute to the debate between the leading memory consolidation theories, i.e., the standard consolidation theory (SCT) and the multiple trace theory (MTT). The latter is closely related to the complementary learning systems (CLS) framework. In particular, we show explicitly how episodic memory can teach the neocortex to form a semantic memory, which is a core issue in MTT and CLS.
Medication non adherence: finding solutions through design thinking approach
Venue: arXiv cs.HC 2017
Year: 2017

Medical non-adherence increasingly is recognized as a major medical health problem. Approximately 50% of patients do not take their medications as prescribed and such poor adherence has been shown to result in complications, death, and increased health care costs. This problem becomes even more significant for patients with chronic illness and those who need to take medications lifetime, like transplant patients. Studies show that one-half of rejection episodes and 15% of graft losses happen due to immunosuppression medications non-adherence. This article explores factors that have an impact on non-compliant behavior among transplant patients: patient factors, illness factor, therapeutic regimen factors. Using user-centered design thinking approach a set of hypotheses are defined and discussed strategies to enhance adherence by using mobile technology and gamification techniques.
D4M 3.0: Extended Database and Language Capabilities
Venue: arXiv cs.DB 2017
Year: 2017

The D4M tool was developed to address many of today's data needs. This tool is used by hundreds of researchers to perform complex analytics on unstructured data. Over the past few years, the D4M toolbox has evolved to support connectivity with a variety of new database engines, including SciDB. D4M-Graphulo provides the ability to do graph analytics in the Apache Accumulo database. Finally, an implementation using the Julia programming language is also now available. In this article, we describe some of our latest additions to the D4M toolbox and our upcoming D4M 3.0 release. We show through benchmarking and scaling results that we can achieve fast SciDB ingest using the D4M-SciDB connector, that using Graphulo can enable graph algorithms on scales that can be memory limited, and that the Julia implementation of D4M achieves comparable performance or exceeds that of the existing MATLAB(R) implementation.
Enabling Massive Deep Neural Networks with the GraphBLAS
Venue: arXiv cs.DC 2017
Year: 2017

Deep Neural Networks (DNNs) have emerged as a core tool for machine learning. The computations performed during DNN training and inference are dominated by operations on the weight matrices describing the DNN. As DNNs incorporate more stages and more nodes per stage, these weight matrices may be required to be sparse because of memory limitations. The GraphBLAS.org math library standard was developed to provide high performance manipulation of sparse weight matrices and input/output vectors. For sufficiently sparse matrices, a sparse matrix library requires significantly less memory than the corresponding dense matrix implementation. This paper provides a brief description of the mathematics underlying the GraphBLAS. In addition, the equations of a typical DNN are rewritten in a form designed to use the GraphBLAS. An implementation of the DNN is given using a preliminary GraphBLAS C library. The performance of the GraphBLAS implementation is measured relative to a standard dense linear algebra library implementation. For various sizes of DNN weight matrices, it is shown that the GraphBLAS sparse implementation outperforms a BLAS dense implementation as the weight matrix becomes sparser.
An Empirical Study on Team Formation in Online Games
Venue: arXiv cs.CY 2017
Year: 2017

Online games provide a rich recording of interactions that can contribute to our understanding of human behavior. One potential lesson is to understand what motivates people to choose their teammates and how their choices leadto performance. We examine several hypotheses about team formation using a large, longitudinal dataset from a team-based online gaming environment. Specifically, we test how positive familiarity, homophily, and competence determine team formationin Battlefield 4, a popular team-based game in which players choose one of two competing teams to play on. Our dataset covers over two months of in-game interactions between over 380,000 players. We show that familiarity is an important factorin team formation, while homophily is not. Competence affects team formation in more nuanced ways: players with similarly high competence team-up repeatedly, but large variations in competence discourage repeated interactions.
Optimal Control for Constrained Coverage Path Planning
Venue: arXiv cs.RO 2017
Year: 2017

The problem of constrained coverage path planning involves a robot trying to cover maximum area of an environment under some constraints that appear as obstacles in the map. Out of the several coverage path planning methods, we consider augmenting the linear sweep-based coverage method to achieve minimum energy/ time optimality along with maximum area coverage. In addition, we also study the effects of variation of different parameters on the performance of the modified method.
A Machine Learning Approach to Routing
Venue: arXiv cs.NI 2017
Year: 2017

Can ideas and techniques from machine learning be leveraged to automatically generate "good" routing configurations? We investigate the power of data-driven routing protocols. Our results suggest that applying ideas and techniques from deep reinforcement learning to this context yields high performance, motivating further research along these lines.
Hypotheses testing on infinite random graphs
Venue: arXiv cs.LG 2017
Year: 2017

Drawing on some recent results that provide the formalism necessary to definite stationarity for infinite random graphs, this paper initiates the study of statistical and learning questions pertaining to these objects. Specifically, a criterion for the existence of a consistent test for complex hypotheses is presented, generalizing the corresponding results on time series. As an application, it is shown how one can test that a tree has the Markov property, or, more generally, to estimate its memory.
The Static and Stochastic VRPTW with both random Customers and Reveal Times: algorithms and recourse strategies
Venue: arXiv cs.AI 2017
Year: 2017

Unlike its deterministic counterpart, static and stochastic vehicle routing problems (SS-VRP) aim at modeling and solving real-life operational problems by considering uncertainty on data. We consider the SS-VRPTW-CR introduced in Saint-Guillain et al. (2017). Like the SS-VRP introduced by Bertsimas (1992), we search for optimal first stage routes for a fleet of vehicles to handle a set of stochastic customer demands, i.e., demands are uncertain and we only know their probabilities. In addition to capacity constraints, customer demands are also constrained by time windows. Unlike all SS-VRP variants, the SS-VRPTW-CR does not make any assumption on the time at which a stochastic demand is revealed, i.e., the reveal time is stochastic as well. To handle this new problem, we introduce waiting locations: Each vehicle is assigned a sequence of waiting locations from which it may serve some associated demands, and the objective is to minimize the expected number of demands that cannot be satisfied in time. In this paper, we propose two new recourse strategies for the SS-VRPTW-CR, together with their closed-form expressions for efficiently computing their expectations: The first one allows us to take vehicle capacities into account; The second one allows us to optimize routes by avoiding some useless trips. We propose two algorithms for searching for routes with optimal expected costs: The first one is an extended branch-and-cut algorithm, based on a stochastic integer formulation, and the second one is a local search based heuristic method. We also introduce a new public benchmark for the SS-VRPTW-CR, based on real-world data coming from the city of Lyon. We evaluate our two algorithms on this benchmark and empirically demonstrate the expected superiority of the SS-VRPTW-CR anticipative actions over a basic "wait-and-serve" policy.
Achieving an Efficient and Fair Equilibrium Through Taxation
Venue: arXiv cs.GT 2017
Year: 2017

It is well known that a game equilibrium can be far from efficient or fair, due to the misalignment between individual and social objectives. The focus of this paper is to design a new mechanism framework that induces an efficient and fair equilibrium in a general class of games. To achieve this goal, we propose a taxation framework, which first imposes a tax on each player based on the perceived payoff (income), and then redistributes the collected tax to other players properly. By turning the tax rate, this framework spans the continuum space between strategic interactions (of selfish players) and altruistic interactions (of unselfish players), hence provides rich modeling possibilities. The key challenge in the design of this framework is the proper taxing rule (i.e., the tax exemption and tax rate) that induces the desired equilibrium in a wide range of games. First, we propose a flat tax rate (i.e., a single tax rate for all players), which is necessary and sufficient for achieving an efficient equilibrium in any static strategic game with common knowledge. Then, we provide several tax exemption rules that achieve some typical fairness criterions (such as the Max-min fairness) at the equilibrium. We further illustrate the implementation of the framework in the game of Prisoners' Dilemma.
Robust polynomial regression up to the information theoretic limit
Venue: arXiv cs.DS 2017
Year: 2017

We consider the problem of robust polynomial regression, where one receives samples $(x_i, y_i)$ that are usually within $σ$ of a polynomial $y = p(x)$, but have a $ρ$ chance of being arbitrary adversarial outliers. Previously, it was known how to efficiently estimate $p$ only when $ρ< \frac{1}{\log d}$. We give an algorithm that works for the entire feasible range of $ρ< 1/2$, while simultaneously improving other parameters of the problem. We complement our algorithm, which gives a factor 2 approximation, with impossibility results that show, for example, that a $1.09$ approximation is impossible even with infinitely many samples.
Analysis of Convolutional Neural Networks for Document Image Classification
Venue: arXiv cs.CV 2017
Year: 2017

Convolutional Neural Networks (CNNs) are state-of-the-art models for document image classification tasks. However, many of these approaches rely on parameters and architectures designed for classifying natural images, which differ from document images. We question whether this is appropriate and conduct a large empirical study to find what aspects of CNNs most affect performance on document images. Among other results, we exceed the state-of-the-art on the RVL-CDIP dataset by using shear transform data augmentation and an architecture designed for a larger input image. Additionally, we analyze the learned features and find evidence that CNNs trained on RVL-CDIP learn region-specific layout features.
Partial Optimality of Dual Decomposition for MAP Inference in Pairwise MRFs
Venue: arXiv cs.DS 2017
Year: 2017

Markov random fields (MRFs) are a powerful tool for modelling statistical dependencies for a set of random variables using a graphical representation. An important computational problem related to MRFs, called maximum a posteriori (MAP) inference, is finding a joint variable assignment with the maximal probability. It is well known that the two popular optimisation techniques for this task, linear programming (LP) relaxation and dual decomposition (DD), have a strong connection both providing an optimal solution to the MAP problem when a corresponding LP relaxation is tight. However, less is known about their relationship in the opposite and more realistic case. In this paper, we explain how the fully integral assignments obtained via DD partially agree with the optimal fractional assignments via LP relaxation when the latter is not tight. In particular, for binary pairwise MRFs the corresponding result suggests that both methods share the partial optimality property of their solutions.
Half-Duplex Routing is NP-hard
Venue: arXiv cs.IT 2017
Year: 2017

Routing is a widespread approach to transfer information from a source node to a destination node in many deployed wireless ad-hoc networks. Today's implemented routing algorithms seek to efficiently find the path/route with the largest Full-Duplex (FD) capacity, which is given by the minimum among the point-to-point link capacities in the path. Such an approach may be suboptimal if then the nodes in the selected path are operated in Half-Duplex (HD) mode. Recently, the capacity (up to a constant gap that only depends on the number of nodes in the path) of an HD line network i.e., a path) has been shown to be equal to half of the minimum of the harmonic means of the capacities of two consecutive links in the path. This paper asks the questions of whether it is possible to design a polynomial-time algorithm that efficiently finds the path with the largest HD capacity in a relay network. This problem of finding that path is shown to be NP-hard in general. However, if the number of cycles in the network is polynomial in the number of nodes, then a polynomial-time algorithm can indeed be designed.
Resilient Linear Classification: An Approach to Deal with Attacks on Training Data
Venue: arXiv cs.LG 2017
Year: 2017

Data-driven techniques are used in cyber-physical systems (CPS) for controlling autonomous vehicles, handling demand responses for energy management, and modeling human physiology for medical devices. These data-driven techniques extract models from training data, where their performance is often analyzed with respect to random errors in the training data. However, if the training data is maliciously altered by attackers, the effect of these attacks on the learning algorithms underpinning data-driven CPS have yet to be considered. In this paper, we analyze the resilience of classification algorithms to training data attacks. Specifically, a generic metric is proposed that is tailored to measure resilience of classification algorithms with respect to worst-case tampering of the training data. Using the metric, we show that traditional linear classification algorithms are resilient under restricted conditions. To overcome these limitations, we propose a linear classification algorithm with a majority constraint and prove that it is strictly more resilient than the traditional algorithms. Evaluations on both synthetic data and a real-world retrospective arrhythmia medical case-study show that the traditional algorithms are vulnerable to tampered training data, whereas the proposed algorithm is more resilient (as measured by worst-case tampering).
A Logical Approach to Cloud Federation
Venue: arXiv cs.DC 2017
Year: 2017

Federated clouds raise a variety of challenges for managing identity, resource access, naming, connectivity, and object access control. This paper shows how to address these challenges in a comprehensive and uniform way using a data-centric approach. The foundation of our approach is a trust logic in which participants issue authenticated statements about principals, objects, attributes, and relationships in a logic language, with reasoning based on declarative policy rules. We show how to use the logic to implement a trust infrastructure for cloud federation that extends the model of NSF GENI, a federated IaaS testbed. It captures shared identity management, GENI authority services, cross-site interconnection using L2 circuits, and a naming and access control system similar to AWS Identity and Access Management (IAM), but extended to a federated system without central control.
GlobeNet: Convolutional Neural Networks for Typhoon Eye Tracking from Remote Sensing Imagery
Venue: arXiv cs.NE 2017
Year: 2017

Advances in remote sensing technologies have made it possible to use high-resolution visual data for weather observation and forecasting tasks. We propose the use of multi-layer neural networks for understanding complex atmospheric dynamics based on multichannel satellite images. The capability of our model was evaluated by using a linear regression task for single typhoon coordinates prediction. A specific combination of models and different activation policies enabled us to obtain an interesting prediction result in the northeastern hemisphere (ENH).
The Message or the Messenger? Inferring Virality and Diffusion Structure from Online Petition Signature Data
Venue: arXiv cs.CY 2017
Year: 2017

Goel et al. (2016) examined diffusion data from Twitter to conclude that online petitions are shared more virally than other types of content. Their definition of structural virality, which measures the extent to which diffusion follows a broadcast model or is spread person to person (virally), depends on knowing the topology of the diffusion cascade. But often the diffusion structure cannot be observed directly. We examined time-stamped signature data from the Obama White House's We the People petition platform. We developed measures based on temporal dynamics that, we argue, can be used to infer diffusion structure as well as the more intrinsic notion of virality sometimes known as infectiousness. These measures indicate that successful petitions are likely to be higher in both intrinsic and structural virality than unsuccessful petitions are. We also investigate threshold effects on petition signing that challenge simple contagion models, and report simulations for a theoretical model that are consistent with our data.
Unsupervised Incremental Learning of Deep Descriptors From Video Streams
Venue: arXiv cs.CV 2017
Year: 2017

We present a novel unsupervised method for face identity learning from video sequences. The method exploits the ResNet deep network for face detection and VGGface fc7 face descriptors together with a smart learning mechanism that exploits the temporal coherence of visual data in video streams. We present a novel feature matching solution based on Reverse Nearest Neighbour and a feature forgetting strategy that supports incremental learning with memory size control, while time progresses. It is shown that the proposed learning procedure is asymptotically stable and can be effectively applied to relevant applications like multiple face tracking.
Simple and Effective Dimensionality Reduction for Word Embeddings
Venue: arXiv cs.CL 2017
Year: 2017

Word embeddings have become the basic building blocks for several natural language processing and information retrieval tasks. Pre-trained word embeddings are used in several downstream applications as well as for constructing representations for sentences, paragraphs and documents. Recently, there has been an emphasis on further improving the pre-trained word vectors through post-processing algorithms. One such area of improvement is the dimensionality reduction of the word embeddings. Reducing the size of word embeddings through dimensionality reduction can improve their utility in memory constrained devices, benefiting several real-world applications. In this work, we present a novel algorithm that effectively combines PCA based dimensionality reduction with a recently proposed post-processing algorithm, to construct word embeddings of lower dimensions. Empirical evaluations on 12 standard word similarity benchmarks show that our algorithm reduces the embedding dimensionality by 50%, while achieving similar or (more often) better performance than the higher dimension embeddings.
WASSA-2017 Shared Task on Emotion Intensity
Venue: arXiv cs.CL 2017
Year: 2017

We present the first shared task on detecting the intensity of emotion felt by the speaker of a tweet. We create the first datasets of tweets annotated for anger, fear, joy, and sadness intensities using a technique called best--worst scaling (BWS). We show that the annotations lead to reliable fine-grained intensity scores (rankings of tweets by intensity). The data was partitioned into training, development, and test sets for the competition. Twenty-two teams participated in the shared task, with the best system obtaining a Pearson correlation of 0.747 with the gold intensity scores. We summarize the machine learning setups, resources, and tools used by the participating teams, with a focus on the techniques and resources that are particularly useful for the task. The emotion intensity dataset and the shared task are helping improve our understanding of how we convey more or less intense emotions through language.
The Accuracy of Cell-based Dynamic Traffic Assignment: Impact of Signal Control on System Optimality
Venue: arXiv cs.SY 2017
Year: 2017

Dynamic Traffic Assignment (DTA) provides an approach to determine the optimal path and/or departure time based on the transportation network characteristics and user behavior (e.g., selfish or social). In the literature, most of the contributions study DTA problems without including traffic signal control in the framework. The few contributions that report signal control models are either mixed-integer or nonlinear formulations and computationally intractable. The only continuous linear signal control method presented in the literature is the Cycle-length Same as Discrete Time-interval (CSDT) control scheme. This model entails a trade-off between cycle-length and cell-length. Furthermore, this approach compromises accuracy and usability of the solutions. In this study, we propose a novel signal control model namely, Signal Control with Realistic Cycle length (SCRC) which overcomes the trade-off between cycle-length and cell-length and strikes a balance between complexity and accuracy. The underlying idea of this model is to use a different time scale for the cycle-length. This time scale can be set to any multiple of the time slot of the Dynamic Network Loading (DNL) model (e.g. CTM, TTM, and LTM) and enables us to set realistic lengths for the signal control cycles. Results show, the SCRC model not only attains accuracy comparable to the CSDT model but also more resilient against extreme traffic conditions. Furthermore, the presented approach substantially reduces computational complexity and can attain solution faster.