OpenRaiser/Intern-Atlas huggingface dataset:
tinyLTE: Lightweight, Ad-Hoc Deployable Cellular Network for Vehicular Communication
Venue: arXiv cs.NI 2018
Year: 2018

The application of LTE technology has evolved from infrastructure-based deployments in licensed bands to new use cases covering ad hoc, device-to-device communications and unlicensed band operation. Vehicular communication is an emerging field of particular interest for LTE, covering in our understanding both automotive (cars) as well as unmanned aerial vehicles. Existing commercial equipment is designed for infrastructure making it unsuitable for vehicular applications requiring low weight and unlicensed band support (e.g. 5.9 GHz ITS-band). In this work, we present tinyLTE, a system design which provides fully autonomous, multi-purpose and ultra-compact LTE cells by utilizing existing open source eNB and EPC implementations. Due to its small form factor and low weight, the tinyLTE system enables mobile deployment on board of cars and drones as well as smooth integration with existing roadside infrastructure. Additionally, the standalone design allows for systems to be chained in a multi-hop configuration. The paper describes the lean and low-cost design concept and implementation followed by a performance evaluation for single and two-hop configurations at 5.9 GHz. The results from both lab and field experiments validate the feasibility of the tinyLTE approach and demonstrate its potential to even support real-time vehicular applications (e.g. with a lowest average end-to-end latency of around 7 ms in the lab experiment).
Wealth Inequality and the Price of Anarchy
Venue: arXiv cs.GT 2018
Year: 2018

Price of anarchy quantifies the degradation of social welfare in games due to the lack of a centralized authority that can enforce the optimal outcome. At its antipodes, mechanism design studies how to ameliorate these effects by incentivizing socially desirable behavior and implementing the optimal state as equilibrium. In practice, the responsiveness to such measures depends on the wealth of each individual. This leads to a natural, but largely unexplored, question. Does optimal mechanism design entrench, or maybe even exacerbate, social inequality? We study this question in nonatomic congestion games, arguably one of the most thoroughly studied settings from the perspectives of price of anarchy as well as mechanism design. We introduce a new model that incorporates the wealth distribution of the population and captures the income elasticity of travel time. This allows us to argue about the equality of wealth distribution both before and after employing a mechanism. We start our analysis by establishing a broad qualitative result, showing that tolls always increase inequality in symmetric congestion games under any reasonable metric of inequality, e.g., the Gini index. Next, we introduce the iniquity index, a novel measure for quantifying the magnitude of these forces towards a more unbalanced wealth distribution and show it has good normative properties (robustness to scaling of income, no-regret learning). We analyze iniquity both in theoretical settings (Pigou's network under various wealth distributions) as well as experimental ones (based on a large scale field experiment in Singapore). Finally, we provide an algorithm for computing optimal tolls for any point of the trade-off of relative importance of efficiency and equality. We conclude with a discussion of our findings in the context of theories of justice as developed in contemporary social sciences.
A Learning-based Stochastic MPC Design for Cooperative Adaptive Cruise Control to Handle Interfering Vehicles
Venue: arXiv cs.SY 2018
Year: 2018

Vehicle to Vehicle (V2V) communication has a great potential to improve reaction accuracy of different driver assistance systems in critical driving situations. Cooperative Adaptive Cruise Control (CACC), which is an automated application, provides drivers with extra benefits such as traffic throughput maximization and collision avoidance. CACC systems must be designed in a way that are sufficiently robust against all special maneuvers such as cutting-into the CACC platoons by interfering vehicles or hard braking by leading cars. To address this problem, a Neural- Network (NN)-based cut-in detection and trajectory prediction scheme is proposed in the first part of this paper. Next, a probabilistic framework is developed in which the cut-in probability is calculated based on the output of the mentioned cut-in prediction block. Finally, a specific Stochastic Model Predictive Controller (SMPC) is designed which incorporates this cut-in probability to enhance its reaction against the detected dangerous cut-in maneuver. The overall system is implemented and its performance is evaluated using realistic driving scenarios from Safety Pilot Model Deployment (SPMD).
Stochastic Hyperparameter Optimization through Hypernetworks
Venue: arXiv cs.LG 2018
Year: 2018

Machine learning models are often tuned by nesting optimization of model weights inside the optimization of hyperparameters. We give a method to collapse this nested optimization into joint stochastic optimization of weights and hyperparameters. Our process trains a neural network to output approximately optimal weights as a function of hyperparameters. We show that our technique converges to locally optimal weights and hyperparameters for sufficiently large hypernetworks. We compare this method to standard hyperparameter optimization strategies and demonstrate its effectiveness for tuning thousands of hyperparameters.
Adaptive Geospatial Joins for Modern Hardware
Venue: arXiv cs.DB 2018
Year: 2018

Geospatial joins are a core building block of connected mobility applications. An especially challenging problem are joins between streaming points and static polygons. Since points are not known beforehand, they cannot be indexed. Nevertheless, points need to be mapped to polygons with low latencies to enable real-time feedback. We present an adaptive geospatial join that uses true hit filtering to avoid expensive geometric computations in most cases. Our technique uses a quadtree-based hierarchical grid to approximate polygons and stores these approximations in a specialized radix tree. We emphasize on an approximate version of our algorithm that guarantees a user-defined precision. The exact version of our algorithm can adapt to the expected point distribution by refining the index. We optimized our implementation for modern hardware architectures with wide SIMD vector processing units, including Intel's brand new Knights Landing. Overall, our approach can perform up to two orders of magnitude faster than existing techniques.
Faster Algorithms for some Optimization Problems on Collinear Points
Venue: arXiv cs.CG 2018
Year: 2018

We propose faster algorithms for the following three optimization problems on $n$ collinear points, i.e., points in dimension one. The first two problems are known to be NP-hard in higher dimensions. 1- Maximizing total area of disjoint disks: In this problem the goal is to maximize the total area of nonoverlapping disks centered at the points. Acharyya, De, and Nandy (2017) presented an $O(n^2)$-time algorithm for this problem. We present an optimal $Θ(n)$-time algorithm. 2- Minimizing sum of the radii of client-server coverage: The $n$ points are partitioned into two sets, namely clients and servers. The goal is to minimize the sum of the radii of disks centered at servers such that every client is in some disk, i.e., in the coverage range of some server. Lev-Tov and Peleg (2005) presented an $O(n^3)$-time algorithm for this problem. We present an $O(n^2)$-time algorithm, thereby improving the running time by a factor of $Θ(n)$. 3- Minimizing total area of point-interval coverage: The $n$ input points belong to an interval $I$. The goal is to find a set of $n$ disks of minimum total area, covering $I$, such that every disk contains at least one input point. We present an algorithm that solves this problem in $O(n^2)$ time.
Mapping the Invocation Structure of Online Political Interaction
Venue: arXiv cs.SI 2018
Year: 2018

The surge in political information, discourse, and interaction has been one of the most important developments in social media over the past several years. There is rich structure in the interaction among different viewpoints on the ideological spectrum. However, we still have only a limited analytical vocabulary for expressing the ways in which these viewpoints interact. In this paper, we develop network-based methods that operate on the ways in which users share content; we construct \emph{invocation graphs} on Web domains showing the extent to which pages from one domain are invoked by users to reply to posts containing pages from other domains. When we locate the domains on a political spectrum induced from the data, we obtain an embedded graph showing how these interaction links span different distances on the spectrum. The structure of this embedded network, and its evolution over time, helps us derive macro-level insights about how political interaction unfolded through 2016, leading up to the US Presidential election. In particular, we find that the domains invoked in replies spanned increasing distances on the spectrum over the months approaching the election, and that there was clear asymmetry between the left-to-right and right-to-left patterns of linkage.
Byzantine-Resilient Distributed Observers for LTI Systems
Venue: arXiv cs.SY 2018
Year: 2018

Consider a linear time-invariant (LTI) dynamical system monitored by a network of sensors, modeled as nodes of an underlying directed communication graph. We study the problem of collaboratively estimating the state of the system when certain nodes are compromised by adversaries. Specifically, we consider a Byzantine adversary model, where a compromised node possesses complete knowledge of the system dynamics and the network, and can deviate arbitrarily from the rules of any prescribed algorithm. We first characterize certain fundamental limitations of any distributed state estimation algorithm in terms of the measurement and communication structure of the nodes. We then develop an attack-resilient, provably correct state estimation algorithm that admits a fully distributed implementation. To characterize feasible network topologies that guarantee success of our proposed technique, we introduce a notion of `strong-robustness' that captures both measurement and communication redundancy. Finally, by drawing connections to bootstrap percolation theory, we argue that given an LTI system and an associated sensor network, the `strong-robustness' property can be checked in polynomial time.
Resilient Leader-Follower Consensus to Arbitrary Reference Values
Venue: arXiv cs.SY 2018
Year: 2018

The problem of consensus in the presence of misbehaving agents has increasingly attracted attention in the literature. Prior results have established algorithms and graph structures for multi-agent networks which guarantee the consensus of normally behaving agents in the presence of a bounded number of misbehaving agents. The final consensus value is guaranteed to fall within the convex hull of initial agent states. However, the problem of consensus tracking considers consensus to arbitrary reference values which may not lie within such bounds. Conditions for consensus tracking in the presence of misbehaving agents has not been fully studied. This paper presents conditions for a network of agents using the W-MSR algorithm to achieve this objective.
Semantic segmentation of trajectories with agent models
Venue: arXiv cs.CV 2018
Year: 2018

In many cases, such as trajectories clustering and classification, we often divide a trajectory into segments as preprocessing. In this paper, we propose a trajectory semantic segmentation method based on learned behavior models. In the proposed method, we learn some behavior models from video sequences. Next, using learned behavior models and a hidden Markov model, we segment a trajectory into semantic segments. Comparing with the Ramer-Douglas-Peucker algorithm, we show the effectiveness of the proposed method.
Computational Red Teaming in a Sudoku Solving Context: Neural Network Based Skill Representation and Acquisition
Venue: arXiv cs.LG 2018
Year: 2018

In this paper we provide an insight into the skill representation, where skill representation is seen as an essential part of the skill assessment stage in the Computational Red Teaming process. Skill representation is demonstrated in the context of Sudoku puzzle, for which the real human skills used in Sudoku solving, along with their acquisition, are represented computationally in a cognitively plausible manner, by using feed-forward neural networks with back-propagation, and supervised learning. The neural network based skills are then coupled with a hard-coded constraint propagation computational Sudoku solver, in which the solving sequence is kept hard-coded, and the skills are represented through neural networks. The paper demonstrates that the modified solver can achieve different levels of proficiency, depending on the amount of skills acquired through the neural networks. Results are encouraging for developing more complex skill and skill acquisition models usable in general frameworks related to the skill assessment aspect of Computational Red Teaming.
A Multi-Disciplinary Review of Knowledge Acquisition Methods: From Human to Autonomous Eliciting Agents
Venue: arXiv cs.AI 2018
Year: 2018

This paper offers a multi-disciplinary review of knowledge acquisition methods in human activity systems. The review captures the degree of involvement of various types of agencies in the knowledge acquisition process, and proposes a classification with three categories of methods: the human agent, the human-inspired agent, and the autonomous machine agent methods. In the first two categories, the acquisition of knowledge is seen as a cognitive task analysis exercise, while in the third category knowledge acquisition is treated as an autonomous knowledge-discovery endeavour. The motivation for this classification stems from the continuous change over time of the structure, meaning and purpose of human activity systems, which are seen as the factor that fuelled researchers' and practitioners' efforts in knowledge acquisition for more than a century. We show through this review that the KA field is increasingly active due to the higher and higher pace of change in human activity, and conclude by discussing the emergence of a fourth category of knowledge acquisition methods, which are based on red-teaming and co-evolution.
Single-View Food Portion Estimation: Learning Image-to-Energy Mappings Using Generative Adversarial Networks
Venue: arXiv cs.CV 2018
Year: 2018

Due to the growing concern of chronic diseases and other health problems related to diet, there is a need to develop accurate methods to estimate an individual's food and energy intake. Measuring accurate dietary intake is an open research problem. In particular, accurate food portion estimation is challenging since the process of food preparation and consumption impose large variations on food shapes and appearances. In this paper, we present a food portion estimation method to estimate food energy (kilocalories) from food images using Generative Adversarial Networks (GAN). We introduce the concept of an "energy distribution" for each food image. To train the GAN, we design a food image dataset based on ground truth food labels and segmentation masks for each food image as well as energy information associated with the food image. Our goal is to learn the mapping of the food image to the food energy. We can then estimate food energy based on the energy distribution. We show that an average energy estimation error rate of 10.89% can be obtained by learning the image-to-energy mapping.
Fully Dynamic Maximal Independent Set with Sublinear Update Time
Venue: arXiv cs.DS 2018
Year: 2018

A maximal independent set (MIS) can be maintained in an evolving $m$-edge graph by simply recomputing it from scratch in $O(m)$ time after each update. But can it be maintained in time sublinear in $m$ in fully dynamic graphs? We answer this fundamental open question in the affirmative. We present a deterministic algorithm with amortized update time $O(\min\{Δ,m^{3/4}\})$, where $Δ$ is a fixed bound on the maximum degree in the graph and $m$ is the (dynamically changing) number of edges. We further present a distributed implementation of our algorithm with $O(\min\{Δ,m^{3/4}\})$ amortized message complexity, and $O(1)$ amortized round complexity and adjustment complexity (the number of vertices that change their output after each update). This strengthens a similar result by Censor-Hillel, Haramaty, and Karnin (PODC'16) that required an assumption of a non-adaptive oblivious adversary.
Modelling and Analysis of Temporal Preference Drifts Using A Component-Based Factorised Latent Approach
Venue: arXiv cs.IR 2018
Year: 2018

The changes in user preferences can originate from substantial reasons, like personality shift, or transient and circumstantial ones, like seasonal changes in item popularities. Disregarding these temporal drifts in modelling user preferences can result in unhelpful recommendations. Moreover, different temporal patterns can be associated with various preference domains, and preference components and their combinations. These components comprise preferences over features, preferences over feature values, conditional dependencies between features, socially-influenced preferences, and bias. For example, in the movies domain, the user can change his rating behaviour (bias shift), her preference for genre over language (feature preference shift), or start favouring drama over comedy (feature value preference shift). In this paper, we first propose a novel latent factor model to capture the domain-dependent component-specific temporal patterns in preferences. The component-based approach followed in modelling the aspects of preferences and their temporal effects enables us to arbitrarily switch components on and off. We evaluate the proposed method on three popular recommendation datasets and show that it significantly outperforms the most accurate state-of-the-art static models. The experiments also demonstrate the greater robustness and stability of the proposed dynamic model in comparison with the most successful models to date. We also analyse the temporal behaviour of different preference components and their combinations and show that the dynamic behaviour of preference components is highly dependent on the preference dataset and domain. Therefore, the results also highlight the importance of modelling temporal effects but also underline the advantages of a component-based architecture that is better suited to capture domain-specific balances in the contributions of the aspects.
On multi-step prediction models for receding horizon control
Venue: arXiv cs.SY 2018
Year: 2018

The derivation of multi-step-ahead prediction models from sampled data of a linear system is considered. A dedicated prediction model is built for each future time step of interest. In addition to a nominal model, the set of all models consistent with data and prior information is derived as well, making the approach suitable for robust control design within a Model Predictive Control framework. The resulting parameter identification problem is solved through a sequence of convex programs, overcoming the non-convexity arising when identifying 1-step prediction models with an output-error criterion. At the same time, the derived models guarantee a worst-case error which is always smaller than the one obtained by iterating models identified with a 1-step prediction error criterion.
Less is More: Exploiting the Standard Compiler Optimization Levels for Better Performance and Energy Consumption
Venue: arXiv cs.PF 2018
Year: 2018

This paper presents the interesting observation that by performing fewer of the optimizations available in a standard compiler optimization level such as -O2, while preserving their original ordering, significant savings can be achieved in both execution time and energy consumption. This observation has been validated on two embedded processors, namely the ARM Cortex-M0 and the ARM Cortex-M3, using two different versions of the LLVM compilation framework; v3.8 and v5.0. Experimental evaluation with 71 embedded benchmarks demonstrated performance gains for at least half of the benchmarks for both processors. An average execution time reduction of 2.4% and 5.3% was achieved across all the benchmarks for the Cortex-M0 and Cortex-M3 processors, respectively, with execution time improvements ranging from 1% up to 90% over the -O2. The savings that can be achieved are in the same range as what can be achieved by the state-of-the-art compilation approaches that use iterative compilation or machine learning to select flags or to determine phase orderings that result in more efficient code. In contrast to these time consuming and expensive to apply techniques, our approach only needs to test a limited number of optimization configurations, less than 64, to obtain similar or even better savings. Furthermore, our approach can support multi-criteria optimization as it targets execution time, energy consumption and code size at the same time.
Learning to recognize touch gestures: recurrent vs. convolutional features and dynamic sampling
Venue: arXiv cs.LG 2018
Year: 2018

We propose a fully automatic method for learning gestures on big touch devices in a potentially multi-user context. The goal is to learn general models capable of adapting to different gestures, user styles and hardware variations (e.g. device sizes, sampling frequencies and regularities). Based on deep neural networks, our method features a novel dynamic sampling and temporal normalization component, transforming variable length gestures into fixed length representations while preserving finger/surface contact transitions, that is, the topology of the signal. This sequential representation is then processed with a convolutional model capable, unlike recurrent networks, of learning hierarchical representations with different levels of abstraction. To demonstrate the interest of the proposed method, we introduce a new touch gestures dataset with 6591 gestures performed by 27 people, which is, up to our knowledge, the first of its kind: a publicly available multi-touch gesture dataset for interaction. We also tested our method on a standard dataset of symbolic touch gesture recognition, the MMG dataset, outperforming the state of the art and reporting close to perfect performance.
Tool Demonstration: FSolidM for Designing Secure Ethereum Smart Contracts
Venue: arXiv cs.CR 2018
Year: 2018

Blockchain-based distributed computing platforms enable the trusted execution of computation - defined in the form of smart contracts - without trusted agents. Smart contracts are envisioned to have a variety of applications, ranging from financial to IoT asset tracking. Unfortunately, the development of smart contracts has proven to be extremely error prone. In practice, contracts are riddled with security vulnerabilities comprising a critical issue since bugs are by design non-fixable and contracts may handle financial assets of significant value. To facilitate the development of secure smart contracts, we have created the FSolidM framework, which allows developers to define contracts as finite state machines (FSMs) with rigorous and clear semantics. FSolidM provides an easy-to-use graphical editor for specifying FSMs, a code generator for creating Ethereum smart contracts, and a set of plugins that developers may add to their FSMs to enhance security and functionality.