OpenRaiser/Intern-Atlas huggingface dataset:
Algorithms for Subpath Convex Hull Queries and Ray-Shooting Among Segments
Venue: arXiv cs.CG 2020
Year: 2020

In this paper, we first consider the subpath convex hull query problem: Given a simple path $π$ of $n$ vertices, preprocess it so that the convex hull of any query subpath of $π$ can be quickly obtained. Previously, Guibas, Hershberger, and Snoeyink [SODA 90'] proposed a data structure of $O(n)$ space and $O(\log n\log\log n)$ query time; reducing the query time to $O(\log n)$ increases the space to $O(n\log\log n)$. We present an improved result that uses $O(n)$ space while achieving $O(\log n)$ query time. Like the previous work, our query algorithm returns a compact interval tree representing the convex hull so that standard binary-search-based queries on the hull can be performed in $O(\log n)$ time each. Our new result leads to improvements for several other problems. In particular, with the help of the above result, we present new algorithms for the ray-shooting problem among segments. Given a set of $n$ (possibly intersecting) line segments in the plane, preprocess it so that the first segment hit by a query ray can be quickly found. We give a data structure of $O(n\log n)$ space that can answer each query in $(\sqrt{n}\log n)$ time. If the segments are nonintersecting or if the segments are lines, then the space can be reduced to $O(n)$. All these are classical problems that have been studied extensively. Previously data structures of $\widetilde{O}(\sqrt{n})$ query time (the notation $\widetilde{O}$ suppresses a polylogarithmic factor) were known in early 1990s; nearly no progress has been made for over two decades. For all problems, our results provide improvements by reducing the space of the data structures by at least a logarithmic factor while the preprocessing and query times are the same as before or even better.
Feedback game on $3$-chromatic Eulerian triangulations of surfaces
Venue: arXiv cs.DM 2020
Year: 2020

In this paper, we study the feedback game on $3$-chromatic Eulerian triangulations of surfaces. We prove that the winner of the game on every $3$-chromatic Eulerian triangulation of a surface all of whose vertices have degree $0$ modulo $4$ is always fixed. Moreover, we also study the case of $3$-chromatic Eulerian triangulations of surfaces which have at least two vertices whose degrees are $2$ modulo $4$, and in particular, we determine the winner of the game on a concrete class of such graphs, called an octahedral path.
On the Optimization of Multi-Cloud Virtualized Radio Access Networks
Venue: arXiv cs.NI 2020
Year: 2020

We study the important and challenging problem of virtualized radio access network (vRAN) design in its most general form. We develop an optimization framework that decides the number and deployment locations of central/cloud units (CUs); which distributed units (DUs) each of them will serve; the functional split that each BS will implement; and the network paths for routing the traffic to CUs and the network core. Our design criterion is to minimize the operator's expenditures while serving the expected traffic. To this end, we combine a linearization technique with a cutting-planes method in order to expedite the exact solution of the formulated problem. We evaluate our framework using real operational networks and system measurements, and follow an exhaustive parameter-sensitivity analysis. We find that the benefits when departing from single-CU deployments can be as high as 30% for our networks, but these gains diminish with the further addition of CUs. Our work sheds light on the vRAN design from a new angle, highlights the importance of deploying multiple CUs, and offers a rigorous framework for optimizing the costs of Multi-CUs vRAN.
A metric Suite for Systematic Quality Assessment of Linked Open Data
Venue: arXiv cs.DB 2020
Year: 2020

Abstract- The vision of the Linked Open Data (LOD) initiative is to provide a distributed model for publishing and meaningfully interlinking open data. The realization of this goal depends strongly on the quality of the data that is published as a part of the LOD. This paper focuses on the systematic quality assessment of datasets prior to publication on the LOD cloud. To this end, we identify important quality deficiencies that need to be avoided and/or resolved prior to the publication of a dataset. We then propose a set of metrics to measure these quality deficiencies in a dataset. This way, we enable the assessment and identification of undesirable quality characteristics of a dataset through our proposed metrics. This will help publishers to filter out low-quality data based on the quality assessment results, which in turn enables data consumers to make better and more informed decisions when using the open datasets.
Optimizing User Interface Layouts via Gradient Descent
Venue: arXiv cs.HC 2020
Year: 2020

Automating parts of the user interface (UI) design process has been a longstanding challenge. We present an automated technique for optimizing the layouts of mobile UIs. Our method uses gradient descent on a neural network model of task performance with respect to the model's inputs to make layout modifications that result in improved predicted error rates and task completion times. We start by extending prior work on neural network based performance prediction to 2-dimensional mobile UIs with an expanded interaction space. We then apply our method to two UIs, including one that the model had not been trained on, to discover layout alternatives with significantly improved predicted performance. Finally, we confirm these predictions experimentally, showing improvements up to 9.2 percent in the optimized layouts. This demonstrates the algorithm's efficacy in improving the task performance of a layout, and its ability to generalize and improve layouts of new interfaces.
Searching for Winograd-aware Quantized Networks
Venue: arXiv cs.LG 2020
Year: 2020

Lightweight architectural designs of Convolutional Neural Networks (CNNs) together with quantization have paved the way for the deployment of demanding computer vision applications on mobile devices. Parallel to this, alternative formulations to the convolution operation such as FFT, Strassen and Winograd, have been adapted for use in CNNs offering further speedups. Winograd convolutions are the fastest known algorithm for spatially small convolutions, but exploiting their full potential comes with the burden of numerical error, rendering them unusable in quantized contexts. In this work we propose a Winograd-aware formulation of convolution layers which exposes the numerical inaccuracies introduced by the Winograd transformations to the learning of the model parameters, enabling the design of competitive quantized models without impacting model size. We also address the source of the numerical error and propose a relaxation on the form of the transformation matrices, resulting in up to 10% higher classification accuracy on CIFAR-10. Finally, we propose wiNAS, a neural architecture search (NAS) framework that jointly optimizes a given macro-architecture for accuracy and latency leveraging Winograd-aware layers. A Winograd-aware ResNet-18 optimized with wiNAS for CIFAR-10 results in 2.66x speedup compared to im2row, one of the most widely used optimized convolution implementations, with no loss in accuracy.
Denoising IMU Gyroscopes with Deep Learning for Open-Loop Attitude Estimation
Venue: arXiv cs.RO 2020
Year: 2020

This paper proposes a learning method for denoising gyroscopes of Inertial Measurement Units (IMUs) using ground truth data, and estimating in real time the orientation (attitude) of a robot in dead reckoning. The obtained algorithm outperforms the state-of-the-art on the (unseen) test sequences. The obtained performances are achieved thanks to a well-chosen model, a proper loss function for orientation increments, and through the identification of key points when training with high-frequency inertial data. Our approach builds upon a neural network based on dilated convolutions, without requiring any recurrent neural network. We demonstrate how efficient our strategy is for 3D attitude estimation on the EuRoC and TUM-VI datasets. Interestingly, we observe our dead reckoning algorithm manages to beat top-ranked visual-inertial odometry systems in terms of attitude estimation although it does not use vision sensors. We believe this paper offers new perspectives for visual-inertial localization and constitutes a step toward more efficient learning methods involving IMUs. Our open-source implementation is available at https://github.com/mbrossar/denoise-imu-gyro.
Analysis of Amnesiac Flooding
Venue: arXiv cs.DC 2020
Year: 2020

The broadcast operation in distributed systems is used to spread information located at some nodes to all other nodes. This operation is often realized by flooding, where the source nodes send a message containing the information to all neighbors. Each node receiving the message for the first time forwards it to all other neighbors. A stateless variant of flooding for synchronous systems is called amnesiac flooding. In this case, every time a node receives a message, it forwards it to those neighbors, from which it did not receive the message in the current round. The algorithm is oblivious and therefore scales very well. Stateless protocols are advantageous in high volume applications, increasing performance by removing the load caused by retention of session information and by providing crash tolerance. In this paper we analyze the termination time of amnesiac flooding. We define the (k,c)-flooding problem, which aims at finding a set $S$ of size $k$, such that amnesiac flooding when started concurrently by all nodes of $S$ terminates in a minimal number of rounds. We prove that this problem is NP-complete. We provide sharp upper and lower bounds for the time complexity of amnesiac flooding and reveal a discrepancy between bipartite and non-bipartite graphs. All results are based on the insight, that for every non-bipartite graph there exists a bipartite graph such that the execution of amnesiac flooding on both graphs is strongly correlated. This construction considerably simplifies existing proofs for amnesiac flooding and allows to analyze the (k,c)-flooding problem.
KEML: A Knowledge-Enriched Meta-Learning Framework for Lexical Relation Classification
Venue: arXiv cs.CL 2020
Year: 2020

Lexical relations describe how concepts are semantically related, in the form of relation triples. The accurate prediction of lexical relations between concepts is challenging, due to the sparsity of patterns indicating the existence of such relations. We propose the Knowledge-Enriched Meta-Learning (KEML) framework to address the task of lexical relation classification. In KEML, the LKB-BERT (Lexical Knowledge Base-BERT) model is presented to learn concept representations from massive text corpora, with rich lexical knowledge injected by distant supervision. A probabilistic distribution of auxiliary tasks is defined to increase the model's ability to recognize different types of lexical relations. We further combine a meta-learning process over the auxiliary task distribution and supervised learning to train the neural lexical relation classifier. Experiments over multiple datasets show that KEML outperforms state-of-the-art methods.
Study of Coarse Quantization-Aware Block Diagonalization Algorithms for MIMO Systems with Low Resolution
Venue: arXiv cs.IT 2020
Year: 2020

It is known that the estimated energy consumption of digital-to analog converters (DACs) is around 30\% of the energy consumed by analog-to-digital converters (ADCs) keeping fixed the sampling rate and bit resolution. Assuming that similarly to ADC, DAC dissipation doubles with every extra bit of resolution, a decrease in two resolution bits, for instance from 4 to 2 bits, represents a 75$\% $ lower dissipation. The current limitations in sum-rates of 1-bit quantization have motivated researchers to consider extra bits in resolution to obtain higher levels of sum-rates. Following this, we devise coarse quantization-aware precoding using few bits for the broadcast channel of multiple-antenna systems based on the Bussgang theorem. In particular, we consider block diagonalization algorithms, which have not been considered in the literature so far. The sum-rates achieved by the proposed Coarse Quantization-Aware Block Diagonalization (CQA-BD) and its regularized version (CQA-RBD) are superior to those previously reported in the literature. Simulations illustrate the performance of the proposed CQA-BD and CGA-RBD algorithms against existing approaches.
Distributed Ledger for Provenance Tracking of Artificial Intelligence Assets
Venue: arXiv cs.CR 2020
Year: 2020

High availability of data is responsible for the current trends in Artificial Intelligence (AI) and Machine Learning (ML). However, high-grade datasets are reluctantly shared between actors because of lacking trust and fear of losing control. Provenance tracing systems are a possible measure to build trust by improving transparency. Especially the tracing of AI assets along complete AI value chains bears various challenges such as trust, privacy, confidentiality, traceability, and fair remuneration. In this paper we design a graph-based provenance model for AI assets and their relations within an AI value chain. Moreover, we propose a protocol to exchange AI assets securely to selected parties. The provenance model and exchange protocol are then combined and implemented as a smart contract on a permission-less blockchain. We show how the smart contract enables the tracing of AI assets in an existing industry use case while solving all challenges. Consequently, our smart contract helps to increase traceability and transparency, encourages trust between actors and thus fosters collaboration between them.
Breaking Batch Normalization for better explainability of Deep Neural Networks through Layer-wise Relevance Propagation
Venue: arXiv cs.LG 2020
Year: 2020

The lack of transparency of neural networks stays a major break for their use. The Layerwise Relevance Propagation technique builds heat-maps representing the relevance of each input in the model s decision. The relevance spreads backward from the last to the first layer of the Deep Neural Network. Layer-wise Relevance Propagation does not manage normalization layers, in this work we suggest a method to include normalization layers. Specifically, we build an equivalent network fusing normalization layers and convolutional or fully connected layers. Heatmaps obtained with our method on MNIST and CIFAR 10 datasets are more accurate for convolutional layers. Our study also prevents from using Layerwise Relevance Propagation with networks including a combination of connected layers and normalization layer.
Relevant-features based Auxiliary Cells for Energy Efficient Detection of Natural Errors
Venue: arXiv cs.LG 2020
Year: 2020

Deep neural networks have demonstrated state-of-the-art performance on many classification tasks. However, they have no inherent capability to recognize when their predictions are wrong. There have been several efforts in the recent past to detect natural errors but the suggested mechanisms pose additional energy requirements. To address this issue, we propose an ensemble of classifiers at hidden layers to enable energy efficient detection of natural errors. In particular, we append Relevant-features based Auxiliary Cells (RACs) which are class specific binary linear classifiers trained on relevant features. The consensus of RACs is used to detect natural errors. Based on combined confidence of RACs, classification can be terminated early, thereby resulting in energy efficient detection. We demonstrate the effectiveness of our technique on various image classification datasets such as CIFAR-10, CIFAR-100 and Tiny-ImageNet.
MLIR: A Compiler Infrastructure for the End of Moore's Law
Venue: arXiv cs.PL 2020
Year: 2020

This work presents MLIR, a novel approach to building reusable and extensible compiler infrastructure. MLIR aims to address software fragmentation, improve compilation for heterogeneous hardware, significantly reduce the cost of building domain specific compilers, and aid in connecting existing compilers together. MLIR facilitates the design and implementation of code generators, translators and optimizers at different levels of abstraction and also across application domains, hardware targets and execution environments. The contribution of this work includes (1) discussion of MLIR as a research artifact, built for extension and evolution, and identifying the challenges and opportunities posed by this novel design point in design, semantics, optimization specification, system, and engineering. (2) evaluation of MLIR as a generalized infrastructure that reduces the cost of building compilers-describing diverse use-cases to show research and educational opportunities for future programming languages, compilers, execution environments, and computer architecture. The paper also presents the rationale for MLIR, its original design principles, structures and semantics.
The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalization
Venue: arXiv cs.LG 2020
Year: 2020

Adversarial training has shown its ability in producing models that are robust to perturbations on the input data, but usually at the expense of decrease in the standard accuracy. To mitigate this issue, it is commonly believed that more training data will eventually help such adversarially robust models generalize better on the benign/unperturbed test data. In this paper, however, we challenge this conventional belief and show that more training data can hurt the generalization of adversarially robust models in the classification problems. We first investigate the Gaussian mixture classification with a linear loss and identify three regimes based on the strength of the adversary. In the weak adversary regime, more data improves the generalization of adversarially robust models. In the medium adversary regime, with more training data, the generalization loss exhibits a double descent curve, which implies the existence of an intermediate stage where more training data hurts the generalization. In the strong adversary regime, more data almost immediately causes the generalization error to increase. Then we move to the analysis of a two-dimensional classification problem with a 0-1 loss. We prove that more data always hurts the generalization performance of adversarially trained models with large perturbations. To complement our theoretical results, we conduct empirical studies on Gaussian mixture classification, support vector machines (SVMs), and linear regression.
On Maximizing Information Reliability in Wireless Powered Cooperative Networks
Venue: arXiv cs.NI 2020
Year: 2020

Unpredictable nature of fading channels and difficulty in tracking channel state information pose major challenge in wireless energy harvesting communication system design. In this work, we address relay selection problem for wireless powered communication networks, where the relays harvest energy from the source radio frequency signals. A single source-destination pair is considered without a direct link. The connecting relay nodes are equipped with storage batteries of infinite size. We assume that the channel state information (CSI) on the source-relay link is available at the relay nodes. Depending on the availability of the CSI on the relay-destination link at the relay node, we propose two relay selection schemes and evaluate their outage probability. Availability of the CSI at the relay node on the relay-destination link considerably improves the performance due to additional flexibility in the relay selection mechanism. Due to absence of CSI throughout the network at the time of transmission path selection, the analysis of the problem is not tractable. Therefore, we relax our assumptions on availability of CSI and closed-form expressions of the outage probability as a function of the amount of the available harvested energy are derived for both CSI availability cases. Finally, we numerically quantify the performance for the proposed schemes and compare the outage probability for fixed and equal number of wireless powered forwarding relays.
IoT Based Real Time Noise Mapping System for Urban Sound Pollution Study
Venue: arXiv cs.NI 2020
Year: 2020

This paper describes the development of a system that enables real time data visualization via a webapp regarding sound intensity using multiple node devices connected through internet. The prototypes were realized using ATmega328 (Arduino Nano) and ESP8266 hardware modules, NodeMCU Arduino wrapper library, Google maps and firebase API along with JavaScript webapp. System architecture is such that multiple node devices will be installed in different locations of the target area. On each node device, an Arduino Nano interfaced with a Sound Sensor measures the ambient sound intensity and ESP8266 Wi-Fi module transmits the data to a database via web API. On the webapp, it plots all the real-time data from the devices over Google maps according to the locations of the node devices. The logged data that is collected can then be used to carry out researches regarding sound pollution in targeted areas.
Interactive Summarizing -- Automatic Slide Localization Technology as Generative Learning Tool
Venue: arXiv cs.CY 2020
Year: 2020

Making a summary is a common learning strategy in lecture learning. It is an effective way for learners to engage in both traditional and video lectures. Video summarization is an effective technology applied to enhance learners' summarizing experience in a video lecture. In this article, we propose to apply cutting-edge automatic slide localization technology to lecture video learning experience. An interactive summarizing model is designed to explain how learners are engaged in the video lecture learning process supported by convolutional neural network and the possibility of related learning analytics.
Back to the Future: Joint Aware Temporal Deep Learning 3D Human Pose Estimation
Venue: arXiv cs.CV 2020
Year: 2020

We propose a new deep learning network that introduces a deeper CNN channel filter and constraints as losses to reduce joint position and motion errors for 3D video human body pose estimation. Our model outperforms the previous best result from the literature based on mean per-joint position error, velocity error, and acceleration errors on the Human 3.6M benchmark corresponding to a new state-of-the-art mean error reduction in all protocols and motion metrics. Mean per joint error is reduced by 1%, velocity error by 7% and acceleration by 13% compared to the best results from the literature. Our contribution increasing positional accuracy and motion smoothness in video can be integrated with future end to end networks without increasing network complexity. Our model and code are available at https://vnmr.github.io/ Keywords: 3D, human, image, pose, action, detection, object, video, visual, supervised, joint, kinematic
Multi-Attribute Guided Painting Generation
Venue: arXiv cs.CV 2020
Year: 2020

Controllable painting generation plays a pivotal role in image stylization. Currently, the control way of style transfer is subject to exemplar-based reference or a random one-hot vector guidance. Few works focus on decoupling the intrinsic properties of painting as control conditions, e.g., artist, genre and period. Under this circumstance, we propose a novel framework adopting multiple attributes from the painting to control the stylized results. An asymmetrical cycle structure is equipped to preserve the fidelity, associating with style preserving and attribute regression loss to keep the unique distinction of colors and textures between domains. Several qualitative and quantitative results demonstrate the effect of the combinations of multiple attributes and achieve satisfactory performance.