OpenRaiser/Intern-Atlas huggingface dataset:
High-Rate Quantum Private Information Retrieval with Weakly Self-Dual Star Product Codes
Venue: arXiv cs.IT 2021
Year: 2021

In the classical private information retrieval (PIR) setup, a user wants to retrieve a file from a database or a distributed storage system (DSS) without revealing the file identity to the servers holding the data. In the quantum PIR (QPIR) setting, a user privately retrieves a classical file by receiving quantum information from the servers. The QPIR problem has been treated by Song et al. in the case of replicated servers, both with and without collusion. QPIR over $[n,k]$ maximum distance separable (MDS) coded servers was recently considered by Allaix et al., but the collusion was essentially restricted to $t=n-k$ servers in the sense that a smaller $t$ would not improve the retrieval rate. In this paper, the QPIR setting is extended to allow for retrieval with high rate for any number of colluding servers $t$ with $1 \leq t \leq n-k$. Similarly to the previous cases, the rates achieved are better than those known or conjectured in the classical counterparts, as well as those of the previously proposed coded and colluding QPIR schemes. This is enabled by considering the stabilizer formalism and weakly self-dual generalized Reed--Solomon (GRS) star product codes.
ABCNet: Attentive Bilateral Contextual Network for Efficient Semantic Segmentation of Fine-Resolution Remote Sensing Images
Venue: arXiv cs.CV 2021
Year: 2021

Semantic segmentation of remotely sensed images plays a crucial role in precision agriculture, environmental protection, and economic assessment. In recent years, substantial fine-resolution remote sensing images are available for semantic segmentation. However, due to the complicated information caused by the increased spatial resolution, state-of-the-art deep learning algorithms normally utilize complex network architectures for segmentation, which usually incurs high computational complexity. Specifically, the high-caliber performance of the convolutional neural network (CNN) heavily relies on fine-grained spatial details (fine resolution) and sufficient contextual information (large receptive fields), both of which trigger high computational costs. This crucially impedes their practicability and availability in real-world scenarios that require real-time processing. In this paper, we propose an Attentive Bilateral Contextual Network (ABCNet), a convolutional neural network (CNN) with double branches, with prominently lower computational consumptions compared to the cutting-edge algorithms, while maintaining a competitive accuracy. Code is available at https://github.com/lironui/ABCNet.
The Importance of Models in Data Analysis with Small Human Movement Datasets -- Inspirations from Neurorobotics Applied to Posture Control of Humanoids and Humans
Venue: arXiv cs.RO 2021
Year: 2021

This work presents a system identification procedure based on Convolutional Neural Networks (CNN) for human posture control using the DEC (Disturbance Estimation and Compensation) parametric model. The modular structure of the proposed control model inspired the design of a modular identification procedure, in the sense that the same neural network is used to identify the parameters of the modules controlling different degrees of freedom. In this way the presented examples of body sway induced by external stimuli provide several training samples at once.
Adaptive Semiparametric Language Models
Venue: arXiv cs.CL 2021
Year: 2021

We present a language model that combines a large parametric neural network (i.e., a transformer) with a non-parametric episodic memory component in an integrated architecture. Our model uses extended short-term context by caching local hidden states -- similar to transformer-XL -- and global long-term memory by retrieving a set of nearest neighbor tokens at each timestep. We design a gating function to adaptively combine multiple information sources to make a prediction. This mechanism allows the model to use either local context, short-term memory, or long-term memory (or any combination of them) on an ad hoc basis depending on the context. Experiments on word-based and character-based language modeling datasets demonstrate the efficacy of our proposed method compared to strong baselines.
Incremental Beam Manipulation for Natural Language Generation
Venue: arXiv cs.CL 2021
Year: 2021

The performance of natural language generation systems has improved substantially with modern neural networks. At test time they typically employ beam search to avoid locally optimal but globally suboptimal predictions. However, due to model errors, a larger beam size can lead to deteriorating performance according to the evaluation metric. For this reason, it is common to rerank the output of beam search, but this relies on beam search to produce a good set of hypotheses, which limits the potential gains. Other alternatives to beam search require changes to the training of the model, which restricts their applicability compared to beam search. This paper proposes incremental beam manipulation, i.e. reranking the hypotheses in the beam during decoding instead of only at the end. This way, hypotheses that are unlikely to lead to a good final output are discarded, and in their place hypotheses that would have been ignored will be considered instead. Applying incremental beam manipulation leads to an improvement of 1.93 and 5.82 BLEU points over vanilla beam search for the test sets of the E2E and WebNLG challenges respectively. The proposed method also outperformed a strong reranker by 1.04 BLEU points on the E2E challenge, while being on par with it on the WebNLG dataset.
Exploring Scale-Measures of Data Sets
Venue: arXiv cs.AI 2021
Year: 2021

Measurement is a fundamental building block of numerous scientific models and their creation. This is in particular true for data driven science. Due to the high complexity and size of modern data sets, the necessity for the development of understandable and efficient scaling methods is at hand. A profound theory for scaling data is scale-measures, as developed in the field of formal concept analysis. Recent developments indicate that the set of all scale-measures for a given data set constitutes a lattice and does hence allow efficient exploring algorithms. In this work we study the properties of said lattice and propose a novel scale-measure exploration algorithm that is based on the well-known and proven attribute exploration approach. Our results motivate multiple applications in scale recommendation, most prominently (semi-)automatic scaling.
A Faster Algorithm for Finding Closest Pairs in Hamming Metric
Venue: arXiv cs.DS 2021
Year: 2021

We study the Closest Pair Problem in Hamming metric, which asks to find the pair with the smallest Hamming distance in a collection of binary vectors. We give a new randomized algorithm for the problem on uniformly random input outperforming previous approaches whenever the dimension of input points is small compared to the dataset size. For moderate to large dimensions, our algorithm matches the time complexity of the previously best-known locality sensitive hashing based algorithms. Technically our algorithm follows similar design principles as Dubiner (IEEE Trans. Inf. Theory 2010) and May-Ozerov (Eurocrypt 2015). Besides improving the time complexity in the aforementioned areas, we significantly simplify the analysis of these previous works. We give a modular analysis, which allows us to investigate the performance of the algorithm also on non-uniform input distributions. Furthermore, we give a proof of concept implementation of our algorithm which performs well in comparison to a quadratic search baseline. This is the first step towards answering an open question raised by May and Ozerov regarding the practicability of algorithms following these design principles.
The #ETH is False, #k-SAT is in Sub-Exponential Time
Venue: arXiv cs.CC 2021
Year: 2021

We orchestrate a randomized algorithm for #$k$-SAT which counts the exact number of satisfying assignments in $2^{o(n)}$ time. The existence of such algorithm signifies that the #ETH is hereby refuted, and so are $\oplus$ETH, ETH, #SETH, $\oplus$SETH and SETH.
Materializing Knowledge Bases via Trigger Graphs
Venue: arXiv cs.DB 2021
Year: 2021

The chase is a well-established family of algorithms used to materialize Knowledge Bases (KBs), like Knowledge Graphs (KGs), to tackle important tasks like query answering under dependencies or data cleaning. A general problem of chase algorithms is that they might perform redundant computations. To counter this problem, we introduce the notion of Trigger Graphs (TGs), which guide the execution of the rules avoiding redundant computations. We present the results of an extensive theoretical and empirical study that seeks to answer when and how TGs can be computed and what are the benefits of TGs when applied over real-world KBs. Our results include introducing algorithms that compute (minimal) TGs. We implemented our approach in a new engine, and our experiments show that it can be significantly more efficient than the chase enabling us to materialize KBs with 17B facts in less than 40 min on commodity machines.
PHASER: a Robust and Correspondence-free Global Pointcloud Registration
Venue: arXiv cs.RO 2021
Year: 2021

We propose PHASER, a correspondence-free global registration of sensor-centric pointclouds that is robust to noise, sparsity, and partial overlaps. Our method can seamlessly handle multimodal information and does not rely on keypoint nor descriptor preprocessing modules. By exploiting properties of Fourier analysis, PHASER operates directly on the sensor's signal, fusing the spectra of multiple channels and computing the 6-DoF transformation based on correlation. Our registration pipeline starts by finding the most likely rotation followed by computing the most likely translation. Both estimates are distributed according to a probability distribution that takes the underlying manifold into account, i.e., a Bingham and Gaussian distribution, respectively. This further allows our approach to consider the periodic-nature of rotations and naturally represent its uncertainty. We extensively compare PHASER against several well-known registration algorithms on both simulated datasets, and real-world data acquired using different sensor configurations. Our results show that PHASER can globally align pointclouds in less than 100ms with an average accuracy of 2cm and 0.5deg, is resilient against noise, and can handle partial overlap.
RECol: Reconstruction Error Columns for Outlier Detection
Venue: arXiv cs.LG 2021
Year: 2021

Detecting outliers or anomalies is a common data analysis task. As a sub-field of unsupervised machine learning, a large variety of approaches exist, but the vast majority treats the input features as independent and often fails to recognize even simple (linear) relationships in the input feature space. Hence, we introduce RECol, a generic data pre-processing approach to generate additional columns in a leave-one-out-fashion: For each column, we try to predict its values based on the other columns, generating reconstruction error columns. We run experiments across a large variety of common baseline approaches and benchmark datasets with and without our RECol pre-processing method and show that the generated reconstruction error feature space generally seems to support common outlier detection methods and often considerably improves their ROC-AUC and PR-AUC values.
Federated mmWave Beam Selection Utilizing LIDAR Data
Venue: arXiv cs.IT 2021
Year: 2021

Efficient link configuration in millimeter wave (mmWave) communication systems is a crucial yet challenging task due to the overhead imposed by beam selection. For vehicle-to-infrastructure (V2I) networks, side information from LIDAR sensors mounted on the vehicles has been leveraged to reduce the beam search overhead. In this letter, we propose a federated LIDAR aided beam selection method for V2I mmWave communication systems. In the proposed scheme, connected vehicles collaborate to train a shared neural network (NN) on their locally available LIDAR data during normal operation of the system. We also propose a reduced-complexity convolutional NN (CNN) classifier architecture and LIDAR preprocessing, which significantly outperforms previous works in terms of both the performance and the complexity.
"Facebook Promotes More Harassment": Social Media Ecosystem, Skill and Marginalized Hijra Identity in Bangladesh
Venue: arXiv cs.HC 2021
Year: 2021

Social interaction across multiple online platforms is a challenge for gender and sexual minorities (GSM) due to the stigmatization they face, which increases the complexity of their self-presentation decisions. These online interactions and identity disclosures can be more complicated for GSM in non-Western contexts due to consequentially different audiences and perceived affordances by the users, and limited baseline understanding of the conflation of these two with local norms and the opportunities they practically represent. Using focus group discussions and semi-structured interviews, we engaged with 61 \textit{Hijra} individuals from Bangladesh, a severely stigmatized GSM from south Asia, to understand their overall online participation and disclosure behaviors through the lens of personal social media ecosystems. We find that along with platform audiences, affordances, and norms, participant skill/knowledge, and cultural influences also impact navigation through multiple platforms, resulting in differential benefits from privacy features. This impacts how Hijra perceive online spaces, and shape their self-presentation and disclosure behaviors over time. Content Warning: This paper discusses graphic contents (e.g. rape and sexual harassment) related to Hijra.
Compressed Object Detection
Venue: arXiv cs.CV 2021
Year: 2021

Deep learning approaches have achieved unprecedented performance in visual recognition tasks such as object detection and pose estimation. However, state-of-the-art models have millions of parameters represented as floats which make them computationally expensive and constrain their deployment on hardware such as mobile phones and IoT nodes. Most commonly, activations of deep neural networks tend to be sparse thus proving that models are over parametrized with redundant neurons. Model compression techniques, such as pruning and quantization, have recently shown promising results by improving model complexity with little loss in performance. In this work, we extended pruning, a compression technique that discards unnecessary model connections, and weight sharing techniques for the task of object detection. With our approach, we are able to compress a state-of-the-art object detection model by 30.0% without a loss in performance. We also show that our compressed model can be easily initialized with existing pre-trained weights, and thus is able to fully utilize published state-of-the-art model zoos.
Progressive Neural Image Compression with Nested Quantization and Latent Ordering
Venue: arXiv cs.LG 2021
Year: 2021

We present PLONQ, a progressive neural image compression scheme which pushes the boundary of variable bitrate compression by allowing quality scalable coding with a single bitstream. In contrast to existing learned variable bitrate solutions which produce separate bitstreams for each quality, it enables easier rate-control and requires less storage. Leveraging the latent scaling based variable bitrate solution, we introduce nested quantization, a method that defines multiple quantization levels with nested quantization grids, and progressively refines all latents from the coarsest to the finest quantization level. To achieve finer progressiveness in between any two quantization levels, latent elements are incrementally refined with an importance ordering defined in the rate-distortion sense. To the best of our knowledge, PLONQ is the first learning-based progressive image coding scheme and it outperforms SPIHT, a well-known wavelet-based progressive image codec.
How to Train Your Robot with Deep Reinforcement Learning; Lessons We've Learned
Venue: arXiv cs.RO 2021
Year: 2021

Deep reinforcement learning (RL) has emerged as a promising approach for autonomously acquiring complex behaviors from low level sensor observations. Although a large portion of deep RL research has focused on applications in video games and simulated control, which does not connect with the constraints of learning in real environments, deep RL has also demonstrated promise in enabling physical robots to learn complex skills in the real world. At the same time,real world robotics provides an appealing domain for evaluating such algorithms, as it connects directly to how humans learn; as an embodied agent in the real world. Learning to perceive and move in the real world presents numerous challenges, some of which are easier to address than others, and some of which are often not considered in RL research that focuses only on simulated domains. In this review article, we present a number of case studies involving robotic deep RL. Building off of these case studies, we discuss commonly perceived challenges in deep RL and how they have been addressed in these works. We also provide an overview of other outstanding challenges, many of which are unique to the real-world robotics setting and are not often the focus of mainstream RL research. Our goal is to provide a resource both for roboticists and machine learning researchers who are interested in furthering the progress of deep RL in the real world.
Chord Embeddings: Analyzing What They Capture and Their Role for Next Chord Prediction and Artist Attribute Prediction
Venue: arXiv cs.SD 2021
Year: 2021

Natural language processing methods have been applied in a variety of music studies, drawing the connection between music and language. In this paper, we expand those approaches by investigating \textit{chord embeddings}, which we apply in two case studies to address two key questions: (1) what musical information do chord embeddings capture?; and (2) how might musical applications benefit from them? In our analysis, we show that they capture similarities between chords that adhere to important relationships described in music theory. In the first case study, we demonstrate that using chord embeddings in a next chord prediction task yields predictions that more closely match those by experienced musicians. In the second case study, we show the potential benefits of using the representations in tasks related to musical stylometrics.
All Subgraphs of a Wheel are 5-Coupled-Choosable
Venue: arXiv cs.DM 2021
Year: 2021

A wheel graph consists of a cycle along with a center vertex connected to every vertex in the cycle. In this paper we show that every subgraph of a wheel graph has list coupled chromatic number at most 5, and this coloring can be found in linear time. We further show that `5' is tight for every wheel graph with at least 5 vertices, and briefly discuss possible generalizations to planar graphs of treewidth 3.
Another estimation of Laplacian spectrum of the Kronecker product of graphs
Venue: arXiv cs.SI 2021
Year: 2021

The relationships between eigenvalues and eigenvectors of a product graph and those of its factor graphs have been known for the standard products, while characterization of Laplacian eigenvalues and eigenvectors of the Kronecker product of graphs using the Laplacian spectra and eigenvectors of the factors turned out to be quite challenging and has remained an open problem to date. Several approaches for the estimation of Laplacian spectrum of the Kronecker product of graphs have been proposed in recent years. However, it turns out that not all the methods are practical to apply in network science models, particularly in the context of multilayer networks. Here we develop a practical and computationally efficient method to estimate Laplacian spectra of this graph product from spectral properties of their factor graphs which is more stable than the alternatives proposed in the literature. We emphasize that a median of the percentage errors of our estimated Laplacian spectrum almost coincides with the $x$-axis, unlike the alternatives which have sudden jumps at the beginning followed by a gradual decrease for the percentage errors. The percentage errors confined (confidence of the estimations) up to $\pm$10% for all considered approximations, depending on a graph density. Moreover, we theoretically prove that the percentage errors becomes smaller when the network grows or the edge density level increases. Additionally, some novel theoretical results considering the exact formulas and lower bounds related to the certain correlation coefficients corresponding to the estimated eigenvectors are presented.
BAXTER: Bi-modal Aerial-Terrestrial Hybrid Vehicle for Long-endurance Versatile Mobility: Preprint Version
Venue: arXiv cs.RO 2021
Year: 2021

Unmanned aerial vehicles are rapidly evolving within the field of robotics. However, their performance is often limited by payload capacity, operational time, and robustness to impact and collision. These limitations of aerial vehicles become more acute for missions in challenging environments such as subterranean structures which may require extended autonomous operation in confined spaces. While software solutions for aerial robots are developing rapidly, improvements to hardware are critical to applying advanced planners and algorithms in large and dangerous environments where the short range and high susceptibility to collisions of most modern aerial robots make applications in realistic subterranean missions infeasible. To provide such hardware capabilities, one needs to design and implement a hardware solution that takes into the account the Size, Weight, and Power (SWaP) constraints. This work focuses on providing a robust and versatile hybrid platform that improves payload capacity, operation time, endurance, and versatility. The Bi-modal Aerial and Terrestrial hybrid vehicle (BAXTER) is a solution that provides two modes of operation, aerial and terrestrial. BAXTER employs two novel hardware mechanisms: the M-Suspension and the Decoupled Transmission which together provide resilience during landing and crashes and efficient terrestrial operation. Extensive flight tests were conducted to characterize the vehicle's capabilities, including robustness and endurance. Additionally, we propose Agile Mode Transfer (AMT), a transition from aerial to terrestrial operation that seeks to minimize impulses during impact to the ground which is a quick and simple transition process that exploits BAXTER's resilience to impact.