OpenRaiser/Intern-Atlas huggingface dataset:
A Tutorial on UAVs for Wireless Networks: Applications, Challenges, and Open Problems
Venue: arXiv cs.IT 2019
Year: 2019

The use of flying platforms such as unmanned aerial vehicles (UAVs), popularly known as drones, is rapidly growing. In particular, with their inherent attributes such as mobility, flexibility, and adaptive altitude, UAVs admit several key potential applications in wireless systems. On the one hand, UAVs can be used as aerial base stations to enhance coverage, capacity, reliability, and energy efficiency of wireless networks. On the other hand, UAVs can operate as flying mobile terminals within a cellular network. Such cellular-connected UAVs can enable several applications ranging from real-time video streaming to item delivery. In this paper, a comprehensive tutorial on the potential benefits and applications of UAVs in wireless communications is presented. Moreover, the important challenges and the fundamental tradeoffs in UAV-enabled wireless networks are thoroughly investigated. In particular, the key UAV challenges such as three-dimensional deployment, performance analysis, channel modeling, and energy efficiency are explored along with representative results. Then, open problems and potential research directions pertaining to UAV communications are introduced. Finally, various analytical frameworks and mathematical tools such as optimization theory, machine learning, stochastic geometry, transport theory, and game theory are described. The use of such tools for addressing unique UAV problems is also presented. In a nutshell, this tutorial provides key guidelines on how to analyze, optimize, and design UAV-based wireless communication systems.
Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation
Venue: arXiv cs.DS 2019
Year: 2019

The notion of treewidth, introduced by Robertson and Seymour in their seminal Graph Minors series, turned out to have tremendous impact on graph algorithmics. Many hard computational problems on graphs turn out to be efficiently solvable in graphs of bounded treewidth: graphs that can be sweeped with separators of bounded size. These efficient algorithms usually follow the dynamic programming paradigm. In the recent years, we have seen a rapid and quite unexpected development of involved techniques for solving various computational problems in graphs of bounded treewidth. One of the most surprising directions is the development of algorithms for connectivity problems that have only single-exponential dependency (i.e., $2^{O(t)}$) on the treewidth in the running time bound, as opposed to slightly superexponential (i.e., $2^{O(t \log t)}$) stemming from more naive approaches. In this work, we perform a thorough experimental evaluation of these approaches in the context of one of the most classic connectivity problem, namely Hamiltonian Cycle.
Not All Samples Are Created Equal: Deep Learning with Importance Sampling
Venue: arXiv cs.LG 2019
Year: 2019

Deep neural network training spends most of the computation on examples that are properly handled, and could be ignored. We propose to mitigate this phenomenon with a principled importance sampling scheme that focuses computation on "informative" examples, and reduces the variance of the stochastic gradients during training. Our contribution is twofold: first, we derive a tractable upper bound to the per-sample gradient norm, and second we derive an estimator of the variance reduction achieved with importance sampling, which enables us to switch it on when it will result in an actual speedup. The resulting scheme can be used by changing a few lines of code in a standard SGD procedure, and we demonstrate experimentally, on image classification, CNN fine-tuning, and RNN training, that for a fixed wall-clock time budget, it provides a reduction of the train losses of up to an order of magnitude and a relative improvement of test errors between 5% and 17%.
Path Puzzles: Discrete Tomography with a Path Constraint is Hard
Venue: arXiv cs.CG 2019
Year: 2019

We prove that path puzzles with complete row and column information--or equivalently, 2D orthogonal discrete tomography with Hamiltonicity constraint--are strongly NP-complete, ASP-complete, and #P-complete. Along the way, we newly establish ASP-completeness and #P-completeness for 3-Dimensional Matching and Numerical 3-Dimensional Matching.
On Cognitive Preferences and the Plausibility of Rule-based Models
Venue: arXiv cs.LG 2019
Year: 2019

It is conventional wisdom in machine learning and data mining that logical models such as rule sets are more interpretable than other models, and that among such rule-based models, simpler models are more interpretable than more complex ones. In this position paper, we question this latter assumption by focusing on one particular aspect of interpretability, namely the plausibility of models. Roughly speaking, we equate the plausibility of a model with the likeliness that a user accepts it as an explanation for a prediction. In particular, we argue that, all other things being equal, longer explanations may be more convincing than shorter ones, and that the predominant bias for shorter models, which is typically necessary for learning powerful discriminative models, may not be suitable when it comes to user acceptance of the learned models. To that end, we first recapitulate evidence for and against this postulate, and then report the results of an evaluation in a crowd-sourcing study based on about 3.000 judgments. The results do not reveal a strong preference for simple rules, whereas we can observe a weak preference for longer rules in some domains. We then relate these results to well-known cognitive biases such as the conjunction fallacy, the representative heuristic, or the recogition heuristic, and investigate their relation to rule length and plausibility.
Data Curation with Deep Learning [Vision]
Venue: arXiv cs.DB 2019
Year: 2019

Data curation - the process of discovering, integrating, and cleaning data - is one of the oldest, hardest, yet inevitable data management problems. Despite decades of efforts from both researchers and practitioners, it is still one of the most time consuming and least enjoyable work of data scientists. In most organizations, data curation plays an important role so as to fully unlock the value of big data. Unfortunately, the current solutions are not keeping up with the ever-changing data ecosystem, because they often require substantially high human cost. Meanwhile, deep learning is making strides in achieving remarkable successes in multiple areas, such as image recognition, natural language processing, and speech recognition. In this vision paper, we explore how some of the fundamental innovations in deep learning could be leveraged to improve existing data curation solutions and to help build new ones. In particular, we provide a thorough overview of the current deep learning landscape, and identify interesting research opportunities and dispel common myths. We hope that the synthesis of these important domains will unleash a series of research activities that will lead to significantly improved solutions for many data curation tasks.
A Hybrid Method for Traffic Flow Forecasting Using Multimodal Deep Learning
Venue: arXiv cs.LG 2019
Year: 2019

Traffic flow forecasting has been regarded as a key problem of intelligent transport systems. In this work, we propose a hybrid multimodal deep learning method for short-term traffic flow forecasting, which can jointly and adaptively learn the spatial-temporal correlation features and long temporal interdependence of multi-modality traffic data by an attention auxiliary multimodal deep learning architecture. According to the highly nonlinear characteristics of multi-modality traffic data, the base module of our method consists of one-dimensional Convolutional Neural Networks (1D CNN) and Gated Recurrent Units (GRU) with the attention mechanism. The former is to capture the local trend features and the latter is to capture the long temporal dependencies. Then, we design a hybrid multimodal deep learning framework (HMDLF) for fusing share representation features of different modality traffic data by multiple CNN-GRU-Attention modules. The experimental results indicate that the proposed multimodal deep learning model is capable of dealing with complex nonlinear urban traffic flow forecasting with satisfying accuracy and effectiveness.
On the Expressiveness and Monitoring of Metric Temporal Logic
Venue: arXiv cs.LO 2019
Year: 2019

It is known that Metric Temporal Logic (MTL) is strictly less expressive than the Monadic First-Order Logic of Order and Metric (FO[<, +1]) when interpreted over timed words; this remains true even when the time domain is bounded a priori. In this work, we present an extension of MTL with the same expressive power as FO[<, +1] over bounded timed words (and also, trivially, over time-bounded signals). We then show that expressive completeness also holds in the general (time-unbounded) case if we allow the use of rational constants $q \in \mathbb{Q}$ in formulas. This extended version of MTL therefore yields a definitive real-time analogue of Kamp's theorem. As an application, we propose a trace-length independent monitoring procedure for our extension of MTL, the first such procedure in a dense real-time setting.
Accelerated Methods for Deep Reinforcement Learning
Venue: arXiv cs.LG 2019
Year: 2019

Deep reinforcement learning (RL) has achieved many recent successes, yet experiment turn-around time remains a key bottleneck in research and in practice. We investigate how to optimize existing deep RL algorithms for modern computers, specifically for a combination of CPUs and GPUs. We confirm that both policy gradient and Q-value learning algorithms can be adapted to learn using many parallel simulator instances. We further find it possible to train using batch sizes considerably larger than are standard, without negatively affecting sample complexity or final performance. We leverage these facts to build a unified framework for parallelization that dramatically hastens experiments in both classes of algorithm. All neural network computations use GPUs, accelerating both data collection and training. Our results include using an entire DGX-1 to learn successful strategies in Atari games in mere minutes, using both synchronous and asynchronous algorithms.
On The Uplink Throughput of Zero-Forcing in Cell-Free Massive MIMO with Coarse Quantization
Venue: arXiv cs.IT 2019
Year: 2019

The recently proposed Cell-Free massive MIMO architecture is studied for the uplink. In contrast to most previous works, joint detection is performed using global CSI. Therefore, we study strategies for transferring CSI to the CPU taking into account the fronthaul capacity which limits CSI quantization. Two strategies for pilot-based CSI acquisition are considered: estimate-and-quantize and quantize-and-estimate. These are analysed using the Bussgang decomposition. For a given quantization constraint for the data and CSI the achievable rate per user with Zero-Forcing is determined. Numerical results show that quantize-and-estimate (the simpler strategy) is similar to or better than estimate-and-quantize, especially for 1-bit resolution.
Angle-based Shape Determination Theory of Planar Graphs with Application to Formation Stabilization
Venue: arXiv cs.SY 2019
Year: 2019

This paper presents an angle-based approach for distributed formation shape stabilization of multi-agent systems in the plane. We develop an angle rigidity theory to study whether a planar framework can be determined by angles between segments uniquely up to translations, rotations, scalings and reflections. The proposed angle rigidity theory is applied to the formation stabilization problem, where multiple single-integrator modeled agents cooperatively achieve an angle-constrained formation. During the formation process, the global coordinate system is unknown for each agent and wireless communications between agents are not required. Moreover, by utilizing the advantage of high degrees of freedom, we propose a distributed control law for agents to stabilize a target formation shape with desired orientation and scale. Simulation examples are performed for illustrating effectiveness of the proposed control strategies.
Policy Search in Continuous Action Domains: an Overview
Venue: arXiv cs.LG 2019
Year: 2019

Continuous action policy search is currently the focus of intensive research, driven both by the recent success of deep reinforcement learning algorithms and the emergence of competitors based on evolutionary algorithms. In this paper, we present a broad survey of policy search methods, providing a unified perspective on very different approaches, including also Bayesian Optimization and directed exploration methods. The main message of this overview is in the relationship between the families of methods, but we also outline some factors underlying sample efficiency properties of the various approaches.
HotStuff: BFT Consensus in the Lens of Blockchain
Venue: arXiv cs.DC 2019
Year: 2019

We present HotStuff, a leader-based Byzantine fault-tolerant replication protocol for the partially synchronous model. Once network communication becomes synchronous, HotStuff enables a correct leader to drive the protocol to consensus at the pace of actual (vs. maximum) network delay--a property called responsiveness--and with communication complexity that is linear in the number of replicas. To our knowledge, HotStuff is the first partially synchronous BFT replication protocol exhibiting these combined properties. HotStuff is built around a novel framework that forms a bridge between classical BFT foundations and blockchains. It allows the expression of other known protocols (DLS, PBFT, Tendermint, Casper), and ours, in a common framework. Our deployment of HotStuff over a network with over 100 replicas achieves throughput and latency comparable to that of BFT-SMaRt, while enjoying linear communication footprint during leader failover (vs. quadratic with BFT-SMaRt).
Improving Vulnerability Inspection Efficiency Using Active Learning
Venue: arXiv cs.SE 2019
Year: 2019

Software engineers can find vulnerabilities with less effort if they are directed towards code that might contain more vulnerabilities. HARMLESS is an incremental support vector machine tool that builds a vulnerability prediction model from the sourcecode inspected to date, then suggests what source code files should be inspected next. In this way, HARMLESS can reduce the time and effort required to achieve some desired level of recall for finding vulnerabilities. The tool also provides feedback on when to stop (at that desired level of recall) while at the same time, correcting human errors by double-checking suspicious files. This paper evaluates HARMLESS on Mozilla Firefox vulnerability data. HARMLESS found 80, 90, 95, 99% of the vulnerabilities by inspecting 10, 16, 20, 34% of the source code files. When targeting 90, 95, 99% recall, HARMLESS could stop after inspecting 23, 30, 47% of the source code files. Even when human reviewers fail to identify half of the vulnerabilities (50% false negative rate), HARMLESScould detect 96% of the missing vulnerabilities by double-checking half of the inspected files. Our results serve to highlight the very steep cost of protecting software from vulnerabilities (in our case study that cost is, for example, the human effort of inspecting 28,750$\times$20% = 5,750 source code files to identify 95% of the vulnerabilities). While this result could benefit the mission-critical projects where human resources are available for inspecting thousands of source code files, the research challenge for future work is how to further reduce that cost. The conclusion of this paper discusses various ways that goal might be achieved.
Trajectory-based Scene Understanding using Dirichlet Process Mixture Model
Venue: arXiv cs.CV 2019
Year: 2019

Appropriate modeling of a surveillance scene is essential for detection of anomalies in road traffic. Learning usual paths can provide valuable insight into road traffic conditions and thus can help in identifying unusual routes taken by commuters/vehicles. If usual traffic paths are learned in a nonparametric way, manual interventions in road marking road can be avoided. In this paper, we propose an unsupervised and nonparametric method to learn frequently used paths from the tracks of moving objects in $Θ(kn)$ time, where $k$ denotes the number of paths and $n$ represents the number of tracks. In the proposed method, temporal dependencies of the moving objects are considered to make the clustering meaningful using Temporally Incremental Gravity Model (TIGM). In addition, the distance-based scene learning makes it intuitive to estimate the model parameters. Further, we have extended TIGM hierarchically as Dynamically Evolving Model (DEM) to represent notable traffic dynamics of a scene. Experimental validation reveals that the proposed method can learn a scene quickly without prior knowledge about the number of paths ($k$). We have compared the results with various state-of-the-art methods. We have also highlighted the advantages of the proposed method over existing techniques popularly used for designing traffic monitoring applications. It can be used for administrative decision making to control traffic at junctions or crowded places and generate alarm signals, if necessary.
Cubical Assemblies, a Univalent and Impredicative Universe and a Failure of Propositional Resizing
Venue: arXiv cs.LO 2019
Year: 2019

We construct a model of cubical type theory with a univalent and impredicative universe in a category of cubical assemblies. We show that this impredicative universe in the cubical assembly model does not satisfy a form of propositional resizing.
Sdf-GAN: Semi-supervised Depth Fusion with Multi-scale Adversarial Networks
Venue: arXiv cs.CV 2019
Year: 2019

Refining raw disparity maps from different algorithms to exploit their complementary advantages is still challenging. Uncertainty estimation and complex disparity relationships among pixels limit the accuracy and robustness of existing methods and there is no standard method for fusion of different kinds of depth data. In this paper, we introduce a new method to fuse disparity maps from different sources, while incorporating supplementary information (intensity, gradient, etc.) into a refiner network to better refine raw disparity inputs. A discriminator network classifies disparities at different receptive fields and scales. Assuming a Markov Random Field for the refined disparity map produces better estimates of the true disparity distribution. Both fully supervised and semi-supervised versions of the algorithm are proposed. The approach includes a more robust loss function to inpaint invalid disparity values and requires much less labeled data to train in the semi-supervised learning mode. The algorithm can be generalized to fuse depths from different kinds of depth sources. Experiments explored different fusion opportunities: stereo-monocular fusion, stereo-ToF fusion and stereo-stereo fusion. The experiments show the superiority of the proposed algorithm compared with the most recent algorithms on public synthetic datasets (Scene Flow, SYNTH3, our synthetic garden dataset) and real datasets (Kitti2015 dataset and Trimbot2020 Garden dataset).
The carbon footprint of distributed cloud storage
Venue: arXiv cs.DC 2019
Year: 2019

The ICT (Information Communication Technologies) ecosystem is estimated to be responsible, as of today, for 10% of the total worldwide energy demand - equivalent to the combined energy production of Germany and Japan. Cloud storage, mainly operated through large and densely-packed data centers, constitutes a non-negligible part of it. However, since the cloud is a fast-inflating market and the energy-efficiency of data centers is mostly an insensitive issue for the collectivity, its carbon footprint shows no signs of slowing down. In this paper, we analyze a novel paradigm for cloud storage (implemented by Cubbit, http://cubbit.io), in which data are stored and distributed over a network of p2p-interacting ARM-based single-board devices. We compare Cubbit's distributed cloud to the traditional centralized solution in terms of environmental footprint and energy efficiency. We demonstrate that, compared to the centralized cloud, the distributed architecture of Cubbit has a carbon footprint reduced of a 77% factor for data storage and of a 50% factor for data transfers. These results provide an example of how a radical paradigm shift in a large-reach technology can benefit both the final consumer as well as our society as a whole.
DoubleEcho: Mitigating Context-Manipulation Attacks in Copresence Verification
Venue: arXiv cs.CR 2019
Year: 2019

Copresence verification based on context can improve usability and strengthen security of many authentication and access control systems. By sensing and comparing their surroundings, two or more devices can tell whether they are copresent and use this information to make access control decisions. To the best of our knowledge, all context-based copresence verification mechanisms to date are susceptible to context-manipulation attacks. In such attacks, a distributed adversary replicates the same context at the (different) locations of the victim devices, and induces them to believe that they are copresent. In this paper we propose DoubleEcho, a context-based copresence verification technique that leverages acoustic Room Impulse Response (RIR) to mitigate context-manipulation attacks. In DoubleEcho, one device emits a wide-band audible chirp and all participating devices record reflections of the chirp from the surrounding environment. Since RIR is, by its very nature, dependent on the physical surroundings, it constitutes a unique location signature that is hard for an adversary to replicate. We evaluate DoubleEcho by collecting RIR data with various mobile devices and in a range of different locations. We show that DoubleEcho mitigates context-manipulation attacks whereas all other approaches to date are entirely vulnerable to such attacks. DoubleEcho detects copresence (or lack thereof) in roughly 2 seconds and works on commodity devices.
3D Point Cloud Denoising using Graph Laplacian Regularization of a Low Dimensional Manifold Model
Venue: arXiv cs.CV 2019
Year: 2019

3D point cloud - a new signal representation of volumetric objects - is a discrete collection of triples marking exterior object surface locations in 3D space. Conventional imperfect acquisition processes of 3D point cloud - e.g., stereo-matching from multiple viewpoint images or depth data acquired directly from active light sensors - imply non-negligible noise in the data. In this paper, we adopt a previously proposed low-dimensional manifold model for the surface patches in the point cloud and seek self-similar patches to denoise them simultaneously using the patch manifold prior. Due to discrete observations of the patches on the manifold, we approximate the manifold dimension computation defined in the continuous domain with a patch-based graph Laplacian regularizer and propose a new discrete patch distance measure to quantify the similarity between two same-sized surface patches for graph construction that is robust to noise. We show that our graph Laplacian regularizer has a natural graph spectral interpretation, and has desirable numerical stability properties via eigenanalysis. Extensive simulation results show that our proposed denoising scheme can outperform state-of-the-art methods in objective metrics and can better preserve visually salient structural features like edges.