OpenRaiser/Intern-Atlas huggingface dataset:
UAV-Sensing-Assisted Cellular Interference Coordination: A Cognitive Radio Approach
Venue: arXiv cs.IT 2020
Year: 2020

Aerial-ground interference mitigation has been deemed as the main challenge in realizing cellular-connected unmanned aerial vehicle (UAV) communications. Due to the line-of-sight (LoS)-dominant air-ground channels, the UAV generates/suffers much stronger interference to/from cellular base stations (BSs) over a much larger region in its uplink/downlink communication, as compared to the terrestrial users. As a result, conventional inter-cell interference coordination (ICIC) techniques catered for terrestrial networks become ineffective in mitigating the more severe UAV-induced interference. To deal with this new challenge, this letter introduces a cognitive radio based solution by treating the UAV and terrestrial users as secondary and primary users in the network, respectively. In particular, the LoS channels with terrestrial BSs/users endow the UAV with a powerful spectrum sensing capability for detecting the terrestrial signals over a much larger region than its serving BS. By exploiting this unique feature, we propose a new UAV-sensing-assisted ICIC design for both the UAV downlink and uplink communications. Specifically, the UAV senses its received interference and the transmissions of terrestrial users in the downlink and uplink, respectively, over the resource blocks (RBs) available at its serving BS to assist its RB allocation to the UAV for avoiding the interference with co-channel terrestrial communications. Numerical results demonstrate that the proposed UAV-assisted ICIC outperforms the conventional terrestrial ICIC by engaging the neighboring BSs for cooperation only.
What Is the Gaze Behavior of Pedestrians in Interactions with an Automated Vehicle When They Do Not Understand Its Intentions?
Venue: arXiv cs.HC 2020
Year: 2020

Interactions between pedestrians and automated vehicles (AVs) will increase significantly with the popularity of AV. However, pedestrians often have not enough trust on the AVs , particularly when they are confused about an AV's intention in a interaction. This study seeks to evaluate if pedestrians clearly understand the driving intentions of AVs in interactions and presents experimental research on the relationship between gaze behaviors of pedestrians and their understanding of the intentions of the AV. The hypothesis investigated in this study was that the less the pedestrian understands the driving intentions of the AV, the longer the duration of their gazing behavior will be. A pedestrian--vehicle interaction experiment was designed to verify the proposed hypothesis. A robotic wheelchair was used as the manual driving vehicle (MV) and AV for interacting with pedestrians while pedestrians' gaze data and their subjective evaluation of the driving intentions were recorded. The experimental results supported our hypothesis as there was a negative correlation between the pedestrians' gaze duration on the AV and their understanding of the driving intentions of the AV. Moreover, the gaze duration of most of the pedestrians on the MV was shorter than that on an AV. Therefore, we conclude with two recommendations to designers of external human-machine interfaces (eHMI): (1) when a pedestrian is engaged in an interaction with an AV, the driving intentions of the AV should be provided; (2) if the pedestrian still gazes at the AV after the AV displays its driving intentions, the AV should provide clearer information about its driving intentions.
Coding for Sequence Reconstruction for Single Edits
Venue: arXiv cs.IT 2020
Year: 2020

The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a communication scenario where the sender transmits a codeword from some codebook and the receiver obtains multiple noisy reads of the codeword. The common setup assumes the codebook to be the entire space and the problem is to determine the minimum number of distinct reads that is required to reconstruct the transmitted codeword. Motivated by modern storage devices, we study a variant of the problem where the number of noisy reads $N$ is fixed. Specifically, we design reconstruction codes that reconstruct a codeword from $N$ distinct noisy reads. We focus on channels that introduce single edit error (i.e. a single substitution, insertion, or deletion) and their variants, and design reconstruction codes for all values of $N$. In particular, for the case of a single edit, we show that as the number of noisy reads increases, the number of redundant bits required can be gracefully reduced from $\log n+O(1)$ to $\log \log n+O(1)$, and then to $O(1)$, where $n$ denotes the length of a codeword. We also show that the redundancy of certain reconstruction codes is within one bit of optimality.
TableNet: Deep Learning model for end-to-end Table detection and Tabular data extraction from Scanned Document Images
Venue: arXiv cs.CV 2020
Year: 2020

With the widespread use of mobile phones and scanners to photograph and upload documents, the need for extracting the information trapped in unstructured document images such as retail receipts, insurance claim forms and financial invoices is becoming more acute. A major hurdle to this objective is that these images often contain information in the form of tables and extracting data from tabular sub-images presents a unique set of challenges. This includes accurate detection of the tabular region within an image, and subsequently detecting and extracting information from the rows and columns of the detected table. While some progress has been made in table detection, extracting the table contents is still a challenge since this involves more fine grained table structure(rows & columns) recognition. Prior approaches have attempted to solve the table detection and structure recognition problems independently using two separate models. In this paper, we propose TableNet: a novel end-to-end deep learning model for both table detection and structure recognition. The model exploits the interdependence between the twin tasks of table detection and table structure recognition to segment out the table and column regions. This is followed by semantic rule-based row extraction from the identified tabular sub-regions. The proposed model and extraction approach was evaluated on the publicly available ICDAR 2013 and Marmot Table datasets obtaining state of the art results. Additionally, we demonstrate that feeding additional semantic features further improves model performance and that the model exhibits transfer learning across datasets. Another contribution of this paper is to provide additional table structure annotations for the Marmot data, which currently only has annotations for table detection.
Decentralization in Digital Societies -- A Design Paradox
Venue: arXiv cs.CY 2020
Year: 2020

Digital societies come with a design paradox: On the one hand, technologies, such as Internet of Things, pervasive and ubiquitous systems, allow a distributed local intelligence in interconnected devices of our everyday life such as smart phones, smart thermostats, self-driving cars, etc. On the other hand, Big Data collection and storage is managed in a highly centralized fashion, resulting in privacy-intrusion, surveillance actions, discriminatory and segregation social phenomena. What is the difference between a distributed and a decentralized system design? How "decentralized" is the processing of our data nowadays? Does centralized design undermine autonomy? Can the level of decentralization in the implemented technologies influence ethical and social dimensions, such as social justice? Can decentralization convey sustainability? Are there parallelisms between the decentralization of digital technology and the decentralization of urban development?
An Optimal Algorithm for 1-D Cutting Stock Problem
Venue: arXiv cs.DM 2020
Year: 2020

We present an $nΔ^{O(k^2)}$ time algorithm to obtain an optimal solution for $1$-dimensional cutting stock problem: the bin packing problem of packing $n$ items onto unit capacity bins under the restriction that the number of item sizes $k$ is fixed, where $Δ$ is the reciprocal of the size of the smallest item. We employ elementary ideas in both the design and analysis our algorithm.
On the Phase Sequences and Permutation Functions in the SLM Scheme for OFDM-IM Systems
Venue: arXiv cs.IT 2020
Year: 2020

In orthogonal frequency division multiplexing with index modulation (OFDM-IM), the active subcarriers can convey information bits by modulated symbols as well as their indices. OFDM-IM has attracted a great deal of attention from researchers by virtue of high energy efficiency. Unfortunately, OFDM-IM has inherited large peak-to-average power ratio (PAPR) of the classical OFDM signal, but there are few works dealing with it. Selected mapping (SLM) is a promising PAPR reduction technique that is distortionless, has good PAPR reducing capability, and can be easily adapted in OFDM-IM systems. In SLM for OFDM-IM systems, the phase sequences rotate the OFDM-IM block in the frequency domain before the inverse fast Fourier transform (IFFT) is applied. Also, permutation in the frequency domain can be easily introduced before multiplication of phase sequences in SLM. In this paper, we investigate the phase sequence set (PSS) and permutation functions in the SLM scheme for OFDM-IM systems; First, the efficiency of the permutation is analyzed as a function of the number of active subcarriers. Second, the optimal conditions for the PSS and permutation functions are derived, which is verified through simulations.
Stance Detection Benchmark: How Robust Is Your Stance Detection?
Venue: arXiv cs.CL 2020
Year: 2020

Stance Detection (StD) aims to detect an author's stance towards a certain topic or claim and has become a key component in applications like fake news detection, claim validation, and argument search. However, while stance is easily detected by humans, machine learning models are clearly falling short of this task. Given the major differences in dataset sizes and framing of StD (e.g. number of classes and inputs), we introduce a StD benchmark that learns from ten StD datasets of various domains in a multi-dataset learning (MDL) setting, as well as from related tasks via transfer learning. Within this benchmark setup, we are able to present new state-of-the-art results on five of the datasets. Yet, the models still perform well below human capabilities and even simple adversarial attacks severely hurt the performance of MDL models. Deeper investigation into this phenomenon suggests the existence of biases inherited from multiple datasets by design. Our analysis emphasizes the need of focus on robustness and de-biasing strategies in multi-task learning approaches. The benchmark dataset and code is made available.
(Theta, triangle)-free and (even hole, $K_4$)-free graphs. Part 2 : bounds on treewidth
Venue: arXiv cs.DM 2020
Year: 2020

A {\em theta} is a graph made of three internally vertex-disjoint chordless paths $P_1 = a \dots b$, $P_2 = a \dots b$, $P_3 = a \dots b$ of length at least~2 and such that no edges exist between the paths except the three edges incident to $a$ and the three edges incident to $b$. A {\em pyramid} is a graph made of three chordless paths $P_1 = a \dots b_1$, $P_2 = a \dots b_2$, $P_3 = a \dots b_3$ of length at least~1, two of which have length at least 2, vertex-disjoint except at $a$, and such that $b_1b_2b_3$ is a triangle and no edges exist between the paths except those of the triangle and the three edges incident to~$a$. An \emph{even hole} is a chordless cycle of even length. For three non-negative integers $i\leq j\leq k$, let $S_{i,j,k}$ be the tree with a vertex $v$, from which start three paths with $i$, $j$, and $k$ edges respectively. We denote by $K_t$ the complete graph on $t$ vertices. We prove that for all non-negative integers $i, j, k$, the class of graphs that contain no theta, no $K_3$, and no $S_{i, j, k}$ as induced subgraphs have bounded treewidth. We prove that for all non-negative integers $i, j, k, t$, the class of graphs that contain no even hole, no pyramid, no $K_t$, and no $S_{i, j, k}$ as induced subgraphs have bounded treewidth. To bound the treewidth, we prove that every graph of large treewidth must contain a large clique or a minimal separator of large cardinality.
Optimal Options for Multi-Task Reinforcement Learning Under Time Constraints
Venue: arXiv cs.LG 2020
Year: 2020

Reinforcement learning can greatly benefit from the use of options as a way of encoding recurring behaviours and to foster exploration. An important open problem is how can an agent autonomously learn useful options when solving particular distributions of related tasks. We investigate some of the conditions that influence optimality of options, in settings where agents have a limited time budget for learning each task and the task distribution might involve problems with different levels of similarity. We directly search for optimal option sets and show that the discovered options significantly differ depending on factors such as the available learning time budget and that the found options outperform popular option-generation heuristics.
A Fast Analytical Model of Fully Associative Caches
Venue: arXiv cs.PF 2020
Year: 2020

While the cost of computation is an easy to understand local property, the cost of data movement on cached architectures depends on global state, does not compose, and is hard to predict. As a result, programmers often fail to consider the cost of data movement. Existing cache models and simulators provide the missing information but are computationally expensive. We present a lightweight cache model for fully associative caches with least recently used (LRU) replacement policy that gives fast and accurate results. We count the cache misses without explicit enumeration of all memory accesses by using symbolic counting techniques twice: 1) to derive the stack distance for each memory access and 2) to count the memory accesses with stack distance larger than the cache size. While this technique seems infeasible in theory, due to non-linearities after the first round of counting, we show that the counting problems are sufficiently linear in practice. Our cache model often computes the results within seconds and contrary to simulation the execution time is mostly problem size independent. Our evaluation measures modeling errors below 0.6% on real hardware. By providing accurate data placement information we enable memory hierarchy aware software development.
Secret key authentication capacity region, Part II: typical authentication rate
Venue: arXiv cs.IT 2020
Year: 2020

This paper investigates the secret key authentication capacity region. Specifically, the focus is on a model where a source must transmit information over an adversary controlled channel where the adversary, prior to the source's transmission, decides whether or not to replace the destination's observation with an arbitrary one of their choosing (done in hopes of having the destination accept a false message). To combat the adversary, the source and destination share a secret key which they may use to guarantee authenticated communications. The secret key authentication capacity region here is then defined as the region of jointly achievable message rate, authentication rate, and key consumption rate (i.e., how many bits of secret key are needed). This is the second of a two part study, with the studies separated by how the authentication rate is measured. Here, the authentication rate is measured by the minimum of the maximum probability of false acceptance where the minimization is over all highly probable subsets of observations at the adversary. That is, consider the maximum probability of false authentication as a function of the adversary's observation, and the adversary's observation as a random variable. The authentication rate is then measured as the smallest number for which the probability that the maximum probability of false authentication is greater than said number is arbitrary small. This is termed typical authentication, since it only needs to consider adversarial observations which are typical with the transmission. Under this measure of authentication matching inner and outer bounds are determined.
Recognizing Images with at most one Spike per Neuron
Venue: arXiv cs.NE 2020
Year: 2020

In order to port the performance of trained artificial neural networks (ANNs) to spiking neural networks (SNNs), which can be implemented in neuromorphic hardware with a drastically reduced energy consumption, an efficient ANN to SNN conversion is needed. Previous conversion schemes focused on the representation of the analog output of a rectified linear (ReLU) gate in the ANN by the firing rate of a spiking neuron. But this is not possible for other commonly used ANN gates, and it reduces the throughput even for ReLU gates. We introduce a new conversion method where a gate in the ANN, which can basically be of any type, is emulated by a small circuit of spiking neurons, with At Most One Spike (AMOS) per neuron. We show that this AMOS conversion improves the accuracy of SNNs for ImageNet from 74.60% to 80.97%, thereby bringing it within reach of the best available ANN accuracy (85.0%). The Top5 accuracy of SNNs is raised to 95.82%, getting even closer to the best Top5 performance of 97.2% for ANNs. In addition, AMOS conversion improves latency and throughput of spike-based image classification by several orders of magnitude. Hence these results suggest that SNNs provide a viable direction for developing highly energy efficient hardware for AI that combines high performance with versatility of applications.
Modeling Musical Structure with Artificial Neural Networks
Venue: arXiv cs.SD 2020
Year: 2020

In recent years, artificial neural networks (ANNs) have become a universal tool for tackling real-world problems. ANNs have also shown great success in music-related tasks including music summarization and classification, similarity estimation, computer-aided or autonomous composition, and automatic music analysis. As structure is a fundamental characteristic of Western music, it plays a role in all these tasks. Some structural aspects are particularly challenging to learn with current ANN architectures. This is especially true for mid- and high-level self-similarity, tonal and rhythmic relationships. In this thesis, I explore the application of ANNs to different aspects of musical structure modeling, identify some challenges involved and propose strategies to address them. First, using probability estimations of a Restricted Boltzmann Machine (RBM), a probabilistic bottom-up approach to melody segmentation is studied. Then, a top-down method for imposing a high-level structural template in music generation is presented, which combines Gibbs sampling using a convolutional RBM with gradient-descent optimization on the intermediate solutions. Furthermore, I motivate the relevance of musical transformations in structure modeling and show how a connectionist model, the Gated Autoencoder (GAE), can be employed to learn transformations between musical fragments. For learning transformations in sequences, I propose a special predictive training of the GAE, which yields a representation of polyphonic music as a sequence of intervals. Furthermore, the applicability of these interval representations to a top-down discovery of repeated musical sections is shown. Finally, a recurrent variant of the GAE is proposed, and its efficacy in music prediction and modeling of low-level repetition structure is demonstrated.
Implementation of the VBM3D Video Denoising Method and Some Variants
Venue: arXiv cs.CV 2020
Year: 2020

VBM3D is an extension to video of the well known image denoising algorithm BM3D, which takes advantage of the sparse representation of stacks of similar patches in a transform domain. The extension is rather straightforward: the similar 2D patches are taken from a spatio-temporal neighborhood which includes neighboring frames. In spite of its simplicity, the algorithm offers a good trade-off between denoising performance and computational complexity. In this work we revisit this method, providing an open-source C++ implementation reproducing the results. A detailed description is given and the choice of parameters is thoroughly discussed. Furthermore, we discuss several extensions of the original algorithm: (1) a multi-scale implementation, (2) the use of 3D patches, (3) the use of optical flow to guide the patch search. These extensions allow to obtain results which are competitive with even the most recent state of the art.
RECAST: Interactive Auditing of Automatic Toxicity Detection Models
Venue: arXiv cs.CL 2020
Year: 2020

As toxic language becomes nearly pervasive online, there has been increasing interest in leveraging the advancements in natural language processing (NLP), from very large transformer models to automatically detecting and removing toxic comments. Despite the fairness concerns, lack of adversarial robustness, and limited prediction explainability for deep learning systems, there is currently little work for auditing these systems and understanding how they work for both developers and users. We present our ongoing work, RECAST, an interactive tool for examining toxicity detection models by visualizing explanations for predictions and providing alternative wordings for detected toxic speech.
Foveated Haptic Gaze
Venue: arXiv cs.HC 2020
Year: 2020

As digital worlds become ubiquitous via video games, simulations, virtual and augmented reality, people with disabilities who cannot access those worlds are becoming increasingly disenfranchised. More often than not the design of these environments focuses on vision, making them inaccessible in whole or in part to people with visual impairments. Accessible games and visual aids have been developed but their lack of prevalence or unintuitive interfaces make them impractical for daily use. To address this gap, we present Foveated Haptic Gaze, a method for conveying visual information via haptics that is intuitive and designed for interacting with real-time 3-dimensional environments. To validate our approach we developed a prototype of the system along with a simplified first-person shooter game. Lastly we present encouraging user study results of both sighted and blind participants using our system to play the game with no visual feedback.
Entropy-Constrained Maximizing Mutual Information Quantization
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we investigate the quantization of the output of a binary input discrete memoryless channel that maximizing the mutual information between the input and the quantized output under an entropy-constrained of the quantized output. A polynomial time algorithm is introduced that can find the truly global optimal quantizer. These results hold for binary input channels with an arbitrary number of quantized output. Finally, we extend these results to binary input continuous output channels and show a sufficient condition such that a single threshold quantizer is an optimal quantizer. Both theoretical results and numerical results are provided to justify our techniques.
High Performance I/O For Large Scale Deep Learning
Venue: arXiv cs.DC 2020
Year: 2020

Training deep learning (DL) models on petascale datasets is essential for achieving competitive and state-of-the-art performance in applications such as speech, video analytics, and object recognition. However, existing distributed filesystems were not developed for the access patterns and usability requirements of DL jobs. In this paper, we describe AIStore, a highly scalable, easy-to-deploy storage system, and WebDataset, a standards-based storage format and library that permits efficient access to very large datasets. We compare system performance experimentally using image classification workloads and storing training data on a variety of backends, including local SSDs, single-node NFS, and two identical bare-metal clusters: HDFS and AIStore.