OpenRaiser/Intern-Atlas huggingface dataset:
Non-Binary Polar Coded System for the Two-User Multiple-Access Channel
Venue: arXiv cs.IT 2021
Year: 2021

This paper presents non-binary polar codes for the two-user multiple-access channel (MAC). The bit error rate (BER) performances of the non-binary polar codes with different kernel factors have been investigated in detail to select a proper parameter from GF(q) for the generator matrix. Furthermore, the successive cancellation decoding for the non-binary polar codes in the two-user MAC is introduced in detail. Simulation results show that the choice of the kernel factors has a significant impact on the block error rate (BLER) performance; moreover, the non-binary polar codes provide a better BLER performance than their binary counterpart in the two-user MAC.
Multi-modal land cover mapping of remote sensing images using pyramid attention and gated fusion networks
Venue: arXiv cs.CV 2021
Year: 2021

Multi-modality data is becoming readily available in remote sensing (RS) and can provide complementary information about the Earth's surface. Effective fusion of multi-modal information is thus important for various applications in RS, but also very challenging due to large domain differences, noise, and redundancies. There is a lack of effective and scalable fusion techniques for bridging multiple modality encoders and fully exploiting complementary information. To this end, we propose a new multi-modality network (MultiModNet) for land cover mapping of multi-modal remote sensing data based on a novel pyramid attention fusion (PAF) module and a gated fusion unit (GFU). The PAF module is designed to efficiently obtain rich fine-grained contextual representations from each modality with a built-in cross-level and cross-view attention fusion mechanism, and the GFU module utilizes a novel gating mechanism for early merging of features, thereby diminishing hidden redundancies and noise. This enables supplementary modalities to effectively extract the most valuable and complementary information for late feature fusion. Extensive experiments on two representative RS benchmark datasets demonstrate the effectiveness, robustness, and superiority of the MultiModNet for multi-modal land cover classification.
Digital Audio Processing Tools for Music Corpus Studies
Venue: arXiv cs.SD 2021
Year: 2021

Digital audio processing tools offer music researchers the opportunity to examine both non-notated music and music as performance. This chapter summarises the types of information that can be extracted from audio as well as currently available audio tools for music corpus studies. The survey of extraction methods includes both a primer on signal processing and background theory on audio feature extraction. The survey of audio tools focuses on widely used tools, including both those with a graphical user interface, namely Audacity and Sonic Visualiser, and code-based tools written in the C/C++, Java, MATLAB, and Python computer programming languages.
Geodesic curves in Gaussian random field manifolds
Venue: arXiv cs.IT 2021
Year: 2021

Random fields are mathematical structures used to model the spatial interaction of random variables along time, with applications ranging from statistical physics and thermodynamics to system's biology and the simulation of complex systems. Despite being studied since the 19th century, little is known about how the dynamics of random fields are related to the geometric properties of their parametric spaces. For example, how can we quantify the similarity between two random fields operating in different regimes using an intrinsic measure? In this paper, we propose a numerical method for the computation of geodesic distances in Gaussian random field manifolds. First, we derive the metric tensor of the underlying parametric space (the 3 x 3 first-order Fisher information matrix), then we derive the 27 Christoffel symbols required in the definition of the system of non-linear differential equations whose solution is a geodesic curve starting at the initial conditions. The fourth-order Runge-Kutta method is applied to numerically solve the non-linear system through an iterative approach. The obtained results show that the proposed method can estimate the geodesic distances for several different initial conditions. Besides, the results reveal an interesting pattern: in several cases, the geodesic curve obtained by reversing the system of differential equations in time does not match the original curve, suggesting the existence of irreversible geometric deformations in the trajectory of a moving reference traveling along a geodesic curve.
CALText: Contextual Attention Localization for Offline Handwritten Text
Venue: arXiv cs.CV 2021
Year: 2021

Recognition of Arabic-like scripts such as Persian and Urdu is more challenging than Latin-based scripts. This is due to the presence of a two-dimensional structure, context-dependent character shapes, spaces and overlaps, and placement of diacritics. Not much research exists for offline handwritten Urdu script which is the 10th most spoken language in the world. We present an attention based encoder-decoder model that learns to read Urdu in context. A novel localization penalty is introduced to encourage the model to attend only one location at a time when recognizing the next character. In addition, we comprehensively refine the only complete and publicly available handwritten Urdu dataset in terms of ground-truth annotations. We evaluate the model on both Urdu and Arabic datasets and show that contextual attention localization outperforms both simple attention and multi-directional LSTM models.
Frequency Estimation with One-Sided Error
Venue: arXiv cs.DS 2021
Year: 2021

Frequency estimation is one of the most fundamental problems in streaming algorithms. Given a stream $S$ of elements from some universe $U=\{1 \ldots n\}$, the goal is to compute, in a single pass, a short sketch of $S$ so that for any element $i \in U$, one can estimate the number $x_i$ of times $i$ occurs in $S$ based on the sketch alone. Two state of the art solutions to this problems are the Count-Min and Count-Sketch algorithms. The frequency estimator $\tilde{x}$ produced by Count-Min, using $O(1/\varepsilon \cdot \log n)$ dimensions, guarantees that $\|\tilde{x}-x\|_{\infty} \le \varepsilon \|x\|_1$ with high probability, and $\tilde{x} \ge x$ holds deterministically. Also, Count-Min works under the assumption that $x \ge 0$. On the other hand, Count-Sketch, using $O(1/\varepsilon^2 \cdot \log n)$ dimensions, guarantees that $\|\tilde{x}-x\|_{\infty} \le \varepsilon \|x\|_2$ with high probability. A natural question is whether it is possible to design the best of both worlds sketching method, with error guarantees depending on the $\ell_2$ norm and space comparable to Count-Sketch, but (like Count-Min) also has the no-underestimation property. Our main set of results shows that the answer to the above question is negative. We show this in two incomparable computational models: linear sketching and streaming algorithms. We also study the complementary problem, where the sketch is required to not over-estimate, i.e., $\tilde{x} \le x$ should hold always.
Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds
Venue: arXiv cs.DS 2021
Year: 2021

A dynamic algorithm against an adaptive adversary is required to be correct when the adversary chooses the next update after seeing the previous outputs of the algorithm. We obtain faster dynamic algorithms against an adaptive adversary and separation results between what is achievable in the oblivious vs. adaptive settings. To get these results we exploit techniques from differential privacy, cryptography, and adaptive data analysis. We give a general reduction transforming a dynamic algorithm against an oblivious adversary to a dynamic algorithm robust against an adaptive adversary. This reduction maintains several copies of the oblivious algorithm and uses differential privacy to protect their random bits. Using this reduction we obtain dynamic algorithms against an adaptive adversary with improved update and query times for global minimum cut, all pairs distances, and all pairs effective resistance. We further improve our update and query times by showing how to maintain a sparsifier over an expander decomposition that can be refreshed fast. This fast refresh enables it to be robust against what we call a blinking adversary that can observe the output of the algorithm only following refreshes. We believe that these techniques will prove useful for additional problems. On the flip side, we specify dynamic problems that, assuming a random oracle, every dynamic algorithm that solves them against an adaptive adversary must be polynomially slower than a rather straightforward dynamic algorithm that solves them against an oblivious adversary. We first show a separation result for a search problem and then show a separation result for an estimation problem. In the latter case our separation result draws from lower bounds in adaptive data analysis.
Cross-modal Zero-shot Hashing by Label Attributes Embedding
Venue: arXiv cs.CV 2021
Year: 2021

Cross-modal hashing (CMH) is one of the most promising methods in cross-modal approximate nearest neighbor search. Most CMH solutions ideally assume the labels of training and testing set are identical. However, the assumption is often violated, causing a zero-shot CMH problem. Recent efforts to address this issue focus on transferring knowledge from the seen classes to the unseen ones using label attributes. However, the attributes are isolated from the features of multi-modal data. To reduce the information gap, we introduce an approach called LAEH (Label Attributes Embedding for zero-shot cross-modal Hashing). LAEH first gets the initial semantic attribute vectors of labels by word2vec model and then uses a transformation network to transform them into a common subspace. Next, it leverages the hash vectors and the feature similarity matrix to guide the feature extraction network of different modalities. At the same time, LAEH uses the attribute similarity as the supplement of label similarity to rectify the label embedding and common subspace. Experiments show that LAEH outperforms related representative zero-shot and cross-modal hashing methods.
Stable Lifelong Learning: Spiking neurons as a solution to instability in plastic neural networks
Venue: arXiv cs.NE 2021
Year: 2021

Synaptic plasticity poses itself as a powerful method of self-regulated unsupervised learning in neural networks. A recent resurgence of interest has developed in utilizing Artificial Neural Networks (ANNs) together with synaptic plasticity for intra-lifetime learning. Plasticity has been shown to improve the learning capabilities of these networks in generalizing to novel environmental circumstances. However, the long-term stability of these trained networks has yet to be examined. This work demonstrates that utilizing plasticity together with ANNs leads to instability beyond the pre-specified lifespan used during training. This instability can lead to the dramatic decline of reward seeking behavior, or quickly lead to reaching environment terminal states. This behavior is shown to hold consistent for several plasticity rules on two different environments across many training time-horizons: a cart-pole balancing problem and a quadrupedal locomotion problem. We present a solution to this instability through the use of spiking neurons.
Mapping Access to Water and Sanitation in Colombia using Publicly Accessible Satellite Imagery, Crowd-sourced Geospatial Information and RandomForests
Venue: arXiv cs.CY 2021
Year: 2021

Up-to-date, granular, and reliable quality of life data is crucial for humanitarian organizations to develop targeted interventions for vulnerable communities, especially in times of crisis. One such quality of life data is access to water, sanitation and hygeine (WASH). Traditionally, data collection is done through door-to-door surveys sampled over large areas. Unfortunately, the huge costs associated with collecting these data deter more frequent and large-coverage surveys. To address this challenge, we present a scalable and inexpensive end-to-end WASH estimation workflow using a combination of machine learning and census data, publicly available satellite images, and crowd-sourced geospatial information. We generate a map of WASH estimates at a granularity of 250m x 250m across the entire country of Colombia. The model was able to explain up to 65% of the variation in predicting access to water supply, sewage, and toilets. The code is made available with MIT License at https://github.com/thinkingmachines/geoai-immap-wash.
Learning Finite Linear Temporal Logic Specifications with a Specialized Neural Operator
Venue: arXiv cs.AI 2021
Year: 2021

Finite linear temporal logic ($\mathsf{LTL}_f$) is a powerful formal representation for modeling temporal sequences. We address the problem of learning a compact $\mathsf{LTL}_f$ formula from labeled traces of system behavior. We propose a novel neural network operator and evaluate the resulting architecture, Neural$\mathsf{LTL}_f$. Our approach includes a specialized recurrent filter, designed to subsume $\mathsf{LTL}_f$ temporal operators, to learn a highly accurate classifier for traces. Then, it discretizes the activations and extracts the truth table represented by the learned weights. This truth table is converted to symbolic form and returned as the learned formula. Experiments on randomly generated $\mathsf{LTL}_f$ formulas show Neural$\mathsf{LTL}_f$ scales to larger formula sizes than existing approaches and maintains high accuracy even in the presence of noise.
Interactive Error Correcting Codes Over Binary Erasure Channels Resilient to $>\frac12$ Adversarial Corruption
Venue: arXiv cs.DS 2021
Year: 2021

An error correcting code ($\mathsf{ECC}$) allows a sender to send a message to a receiver such that even if a constant fraction of the communicated bits are corrupted, the receiver can still learn the message correctly. Due to their importance and fundamental nature, $\mathsf{ECC}$s have been extensively studied, one of the main goals being to maximize the fraction of errors that the $\mathsf{ECC}$ is resilient to. For adversarial erasure errors (over a binary channel) the maximal error resilience of an $\mathsf{ECC}$ is $\frac12$ of the communicated bits. In this work, we break this $\frac12$ barrier by introducing the notion of an interactive error correcting code ($\mathsf{iECC}$) and constructing an $\mathsf{iECC}$ that is resilient to adversarial erasure of $\frac35$ of the total communicated bits. We emphasize that the adversary can corrupt both the sending party and the receiving party, and that both parties' rounds contribute to the adversary's budget. We also prove an impossibility (upper) bound of $\frac23$ on the maximal resilience of any binary $\mathsf{iECC}$ to adversarial erasures. In the bit flip setting, we prove an impossibility bound of $\frac27$.
Access Management in Joint Sensing and Communication Systems: Efficiency versus Fairness
Venue: arXiv cs.NI 2021
Year: 2021

In this paper, we consider a distributed joint sensing and communication (DJSC) system in which multiple radar sensors are deployed. Each sensor is equipped with a sensing function and a communication function, and thus it is a JSC node. The JSC nodes are able to perform sensing their surrounding environments, e.g., weather conditions or available spectrum. Furthermore, they can cooperatively detect and track a common target. The information, i.e., of the environment and target, collected by the JSC nodes is transmitted to a base station (BS) for further processing. As such, different aspects of the target to be viewed simultaneously, which significantly improves the performance of the target detection and tracking. However, both the sensing function and communication function require a certain amount of bandwidth for their operations, and deploying multiple JSC nodes may consume a large amount of bandwidth. Therefore, we investigate the bandwidth allocation problem for the DJSC system. In particular, we aim to optimize the bandwidth allocation to the sensing function and the communication function of the JSC nodes. To improve the allocation efficiency while benefiting the spatial diversity advantage of the DJSC systems, the objective is to maximize the sum of sensing performances, i.e., estimation rates, communication performances, i.e., communication data rates, and fairnesses of all the users. The optimization problem is non-convex and difficult to be solved. For this, we propose a fully polynomial time approximation algorithm, and we prove that the approximation algorithm can guarantee a near-optimal solution with an accuracy bound of $ε$. Furthermore, we propose to use a heuristic algorithm with lower complexity. The simulation results show that both the proposed algorithms are able to achieve the solutions close to the optimum in a computationally efficient fashion.
Learning to Rectify for Robust Learning with Noisy Labels
Venue: arXiv cs.LG 2021
Year: 2021

Label noise significantly degrades the generalization ability of deep models in applications. Effective strategies and approaches, \textit{e.g.} re-weighting, or loss correction, are designed to alleviate the negative impact of label noise when training a neural network. Those existing works usually rely on the pre-specified architecture and manually tuning the additional hyper-parameters. In this paper, we propose warped probabilistic inference (WarPI) to achieve adaptively rectifying the training procedure for the classification network within the meta-learning scenario. In contrast to the deterministic models, WarPI is formulated as a hierarchical probabilistic model by learning an amortization meta-network, which can resolve sample ambiguity and be therefore more robust to serious label noise. Unlike the existing approximated weighting function of directly generating weight values from losses, our meta-network is learned to estimate a rectifying vector from the input of the logits and labels, which has the capability of leveraging sufficient information lying in them. This provides an effective way to rectify the learning procedure for the classification network, demonstrating a significant improvement of the generalization ability. Besides, modeling the rectifying vector as a latent variable and learning the meta-network can be seamlessly integrated into the SGD optimization of the classification network. We evaluate WarPI on four benchmarks of robust learning with noisy labels and achieve the new state-of-the-art under variant noise types. Extensive study and analysis also demonstrate the effectiveness of our model.
OpenMP aware MHP Analysis for Improved Static Data-Race Detection
Venue: arXiv cs.PL 2021
Year: 2021

Data races, a major source of bugs in concurrent programs, can result in loss of manpower and time as well as data loss due to system failures. OpenMP, the de facto shared memory parallelism framework used in the HPC community, also suffers from data races. To detect race conditions in OpenMP programs and improve turnaround time and/or developer productivity, we present a data flow analysis based, fast, static data race checker in the LLVM compiler framework. Our tool can detect races in the presence or absence of explicit barriers, with implicit or explicit synchronization. In addition, our tool effectively works for the OpenMP target offloading constructs and also supports the frequently used OpenMP constructs. We formalize and provide a data flow analysis framework to perform Phase Interval Analysis (PIA) of OpenMP programs. Phase intervals are then used to compute the MHP (and its complement NHP) sets for the programs, which, in turn, are used to detect data races statically. We evaluate our work using multiple OpenMP race detection benchmarks and real world applications. Our experiments show that the checker is comparable to the state-of-the-art in various performance metrics with around 90% accuracy, almost perfect recall, and significantly lower runtime and memory footprint.
Identifying Best Fair Intervention
Venue: arXiv cs.CY 2021
Year: 2021

We study the problem of best arm identification with a fairness constraint in a given causal model. The goal is to find a soft intervention on a given node to maximize the outcome while meeting a fairness constraint by counterfactual estimation with only partial knowledge of the causal model. The problem is motivated by ensuring fairness on an online marketplace. We provide theoretical guarantees on the probability of error and empirically examine the effectiveness of our algorithm with a two-stage baseline.
LMStream: When Distributed Micro-Batch Stream Processing Systems Meet GPU
Venue: arXiv cs.DC 2021
Year: 2021

This paper presents LMStream, which ensures bounded latency while maximizing the throughput on the GPU-enabled micro-batch streaming systems. The main ideas behind LMStream's design can be summarized as two novel mechanisms: (1) dynamic batching and (2) dynamic operation-level query planning. By controlling the micro-batch size, LMStream significantly reduces the latency of individual dataset because it does not perform unconditional buffering only for improving GPU utilization. LMStream bounds the latency to an optimal value according to the characteristics of the window operation used in the streaming application. Dynamic mapping between a query to an execution device based on the data size and dynamic device preference improves both the throughput and latency as much as possible. In addition, LMStream proposes a low-overhead online cost model parameter optimization method without interrupting the real-time stream processing. We implemented LMStream on Apache Spark, which supports micro-batch stream processing. Compared to the previous throughput-oriented method, LMStream showed an average latency improvement up to a maximum of 70.7%, while improving average throughput up to 1.74x.
SEGA: Semantic Guided Attention on Visual Prototype for Few-Shot Learning
Venue: arXiv cs.CV 2021
Year: 2021

Teaching machines to recognize a new category based on few training samples especially only one remains challenging owing to the incomprehensive understanding of the novel category caused by the lack of data. However, human can learn new classes quickly even given few samples since human can tell what discriminative features should be focused on about each category based on both the visual and semantic prior knowledge. To better utilize those prior knowledge, we propose the SEmantic Guided Attention (SEGA) mechanism where the semantic knowledge is used to guide the visual perception in a top-down manner about what visual features should be paid attention to when distinguishing a category from the others. As a result, the embedding of the novel class even with few samples can be more discriminative. Concretely, a feature extractor is trained to embed few images of each novel class into a visual prototype with the help of transferring visual prior knowledge from base classes. Then we learn a network that maps semantic knowledge to category-specific attention vectors which will be used to perform feature selection to enhance the visual prototypes. Extensive experiments on miniImageNet, tieredImageNet, CIFAR-FS, and CUB indicate that our semantic guided attention realizes anticipated function and outperforms state-of-the-art results.