OpenRaiser/Intern-Atlas huggingface dataset:
1-Bit Massive MIMO Transmission: Embracing Interference with Symbol-Level Precoding
Venue: arXiv cs.IT 2021
Year: 2021

The deployment of large-scale antenna arrays for cellular base stations (BSs), termed as `Massive MIMO', has been a key enabler for meeting the ever-increasing capacity requirement for 5G communication systems and beyond. Despite their promising performance, fully-digital massive MIMO systems require a vast amount of hardware components including radio frequency chains, power amplifiers, digital-to-analog converters (DACs), etc., resulting in a huge increase in terms of the total power consumption and hardware costs for cellular BSs. Towards both spectrally-efficient and energy-efficient massive MIMO deployment, a number of hardware limited architectures have been proposed, including hybrid analog-digital structures, constant-envelope transmission, and use of low-resolution DACs. In this paper, we overview the recent interest in improving the error-rate performance of massive MIMO systems deployed with 1-bit DACs through precoding at the symbol level. This line of research goes beyond traditional interference suppression or cancellation techniques by managing interference on a symbol-by-symbol basis. This provides unique opportunities for interference-aware precoding tailored for practical massive MIMO systems. Firstly, we characterize constructive interference (CI) and elaborate on how CI can benefit the 1-bit signal design by exploiting the traditionally undesired multi-user interference as well as the interference from imperfect hardware components. Subsequently, we overview several solutions for 1-bit signal design to illustrate the gains achievable by exploiting CI. Finally, we identify some challenges and future research directions for 1-bit massive MIMO systems that are yet to be explored.
Lifelong Incremental Reinforcement Learning with Online Bayesian Inference
Venue: arXiv cs.LG 2021
Year: 2021

A central capability of a long-lived reinforcement learning (RL) agent is to incrementally adapt its behavior as its environment changes, and to incrementally build upon previous experiences to facilitate future learning in real-world scenarios. In this paper, we propose LifeLong Incremental Reinforcement Learning (LLIRL), a new incremental algorithm for efficient lifelong adaptation to dynamic environments. We develop and maintain a library that contains an infinite mixture of parameterized environment models, which is equivalent to clustering environment parameters in a latent space. The prior distribution over the mixture is formulated as a Chinese restaurant process (CRP), which incrementally instantiates new environment models without any external information to signal environmental changes in advance. During lifelong learning, we employ the expectation maximization (EM) algorithm with online Bayesian inference to update the mixture in a fully incremental manner. In EM, the E-step involves estimating the posterior expectation of environment-to-cluster assignments, while the M-step updates the environment parameters for future learning. This method allows for all environment models to be adapted as necessary, with new models instantiated for environmental changes and old models retrieved when previously seen environments are encountered again. Experiments demonstrate that LLIRL outperforms relevant existing methods, and enables effective incremental adaptation to various dynamic environments for lifelong learning.
Faster Mean-shift: GPU-accelerated clustering for cosine embedding-based cell segmentation and tracking
Venue: arXiv cs.CV 2021
Year: 2021

Recently, single-stage embedding based deep learning algorithms gain increasing attention in cell segmentation and tracking. Compared with the traditional "segment-then-associate" two-stage approach, a single-stage algorithm not only simultaneously achieves consistent instance cell segmentation and tracking but also gains superior performance when distinguishing ambiguous pixels on boundaries and overlaps. However, the deployment of an embedding based algorithm is restricted by slow inference speed (e.g., around 1-2 mins per frame). In this study, we propose a novel Faster Mean-shift algorithm, which tackles the computational bottleneck of embedding based cell segmentation and tracking. Different from previous GPU-accelerated fast mean-shift algorithms, a new online seed optimization policy (OSOP) is introduced to adaptively determine the minimal number of seeds, accelerate computation, and save GPU memory. With both embedding simulation and empirical validation via the four cohorts from the ISBI cell tracking challenge, the proposed Faster Mean-shift algorithm achieved 7-10 times speedup compared to the state-of-the-art embedding based cell instance segmentation and tracking algorithm. Our Faster Mean-shift algorithm also achieved the highest computational speed compared to other GPU benchmarks with optimized memory consumption. The Faster Mean-shift is a plug-and-play model, which can be employed on other pixel embedding based clustering inference for medical image analysis. (Plug-and-play model is publicly available: https://github.com/masqm/Faster-Mean-Shift)
Computing Weighted Subset Transversals in $H$-Free Graphs
Venue: arXiv cs.DS 2021
Year: 2021

For the Odd Cycle Transversal problem, the task is to find a small set $S$ of vertices in a graph that intersects every cycle of odd length. The Subset Odd Cycle Transversal problem requires S to intersect only those odd cycles that include a vertex of a distinguished vertex subset $T$. If we are given weights for the vertices, we ask instead that $S$ has small weight: this is the problem Weighted Subset Odd Cycle Transversal. We prove an almost-complete complexity dichotomy for Weighted Subset Odd Cycle Transversal for graphs that do not contain a graph $H$ as an induced subgraph. Our general approach can also be used for Weighted Subset Feedback Vertex Set, which enables us to generalize a recent result of Papadopoulos and Tzimas.
Automatic Detection of Aedes aegypti Breeding Grounds Based on Deep Networks with Spatio-Temporal Consistency
Venue: arXiv cs.CV 2021
Year: 2021

Every year, the Aedes aegypti mosquito infects millions of people with diseases such as dengue, zika, chikungunya, and urban yellow fever. The main form to combat these diseases is to avoid mosquito reproduction by searching for and eliminating the potential mosquito breeding grounds. In this work, we introduce a comprehensive dataset of aerial videos, acquired with an unmanned aerial vehicle, containing possible mosquito breeding sites. All frames of the video dataset were manually annotated with bounding boxes identifying all objects of interest. This dataset was employed to develop an automatic detection system of such objects based on deep convolutional networks. We propose the exploitation of the temporal information contained in the videos by the incorporation, in the object detection pipeline, of a spatio-temporal consistency module that can register the detected objects, minimizing most false-positive and false-negative occurrences. Also, we experimentally show that using videos is more beneficial than only composing a mosaic using the frames. Using the ResNet-50-FPN as a backbone, we achieve F$_1$-scores of 0.65 and 0.77 on the object-level detection of `tires' and `water tanks', respectively, illustrating the system capabilities to properly locate potential mosquito breeding objects.
Towards a Formal Foundation of Intermittent Computing
Venue: arXiv cs.PL 2021
Year: 2021

Intermittently powered devices enable new applications in harsh or inaccessible environments, such as space or in-body implants, but also introduce problems in programmability and correctness. Researchers have developed programming models to ensure that programs make progress and do not produce erroneous results due to memory inconsistencies caused by intermittent executions. As the technology has matured, more and more features are added to intermittently powered devices, such as I/O. Prior work has shown that all existing intermittent execution models have problems with repeated device or sensor inputs (RIO). RIOs could leave intermittent executions in an inconsistent state. Such problems and the proliferation of existing intermittent execution models necessitate a formal foundation for intermittent computing. In this paper, we formalize intermittent execution models, their correctness properties with respect to memory consistency and inputs, and identify the invariants needed to prove systems correct. We prove equivalence between several existing intermittent systems. To address RIO problems, we define an algorithm for identifying variables affected by RIOs that need to be restored after reboot and prove the algorithm correct. Finally, we implement the algorithm in a novel intermittent runtime system that is correct with respect to input operations and evaluate its performance.
Algorithmic Stability in Fair Allocation of Indivisible Goods Among Two Agents
Venue: arXiv cs.GT 2021
Year: 2021

Many allocation problems in multiagent systems rely on agents specifying cardinal preferences. However, allocation mechanisms can be sensitive to small perturbations in cardinal preferences, thus causing agents who make ``small" or ``innocuous" mistakes while reporting their preferences to experience a large change in their utility for the final outcome. To address this, we introduce a notion of algorithmic stability and study it in the context of fair and efficient allocations of indivisible goods among two agents. We show that it is impossible to achieve exact stability along with even a weak notion of fairness and even approximate efficiency. As a result, we propose two relaxations to stability, namely, approximate-stability and weak-approximate-stability, and show how existing algorithms in the fair division literature that guarantee fair and efficient outcomes perform poorly with respect to these relaxations. This leads us to explore the possibility of designing new algorithms that are more stable. Towards this end, we present a general characterization result for pairwise maximin share allocations, and in turn use it to design an algorithm that is approximately-stable and guarantees a pairwise maximin share and Pareto optimal allocation for two agents. Finally, we present a simple framework that can be used to modify existing fair and efficient algorithms in order to ensure that they also achieve weak-approximate-stability.
MKQA: A Linguistically Diverse Benchmark for Multilingual Open Domain Question Answering
Venue: arXiv cs.CL 2021
Year: 2021

Progress in cross-lingual modeling depends on challenging, realistic, and diverse evaluation sets. We introduce Multilingual Knowledge Questions and Answers (MKQA), an open-domain question answering evaluation set comprising 10k question-answer pairs aligned across 26 typologically diverse languages (260k question-answer pairs in total). Answers are based on a heavily curated, language-independent data representation, making results comparable across languages and independent of language-specific passages. With 26 languages, this dataset supplies the widest range of languages to-date for evaluating question answering. We benchmark a variety of state-of-the-art methods and baselines for generative and extractive question answering, trained on Natural Questions, in zero shot and translation settings. Results indicate this dataset is challenging even in English, but especially in low-resource languages
What does BERT know about books, movies and music? Probing BERT for Conversational Recommendation
Venue: arXiv cs.IR 2021
Year: 2021

Heavily pre-trained transformer models such as BERT have recently shown to be remarkably powerful at language modelling by achieving impressive results on numerous downstream tasks. It has also been shown that they are able to implicitly store factual knowledge in their parameters after pre-training. Understanding what the pre-training procedure of LMs actually learns is a crucial step for using and improving them for Conversational Recommender Systems (CRS). We first study how much off-the-shelf pre-trained BERT "knows" about recommendation items such as books, movies and music. In order to analyze the knowledge stored in BERT's parameters, we use different probes that require different types of knowledge to solve, namely content-based and collaborative-based. Content-based knowledge is knowledge that requires the model to match the titles of items with their content information, such as textual descriptions and genres. In contrast, collaborative-based knowledge requires the model to match items with similar ones, according to community interactions such as ratings. We resort to BERT's Masked Language Modelling head to probe its knowledge about the genre of items, with cloze style prompts. In addition, we employ BERT's Next Sentence Prediction head and representations' similarity to compare relevant and non-relevant search and recommendation query-document inputs to explore whether BERT can, without any fine-tuning, rank relevant items first. Finally, we study how BERT performs in a conversational recommendation downstream task. Overall, our analyses and experiments show that: (i) BERT has knowledge stored in its parameters about the content of books, movies and music; (ii) it has more content-based knowledge than collaborative-based knowledge; and (iii) fails on conversational recommendation when faced with adversarial data.
Synchronized Planarity with Applications to Constrained Planarity Problems
Venue: arXiv cs.DS 2021
Year: 2021

We introduce the problem Synchronized Planarity. Roughly speaking, its input is a loop-free multi-graph together with synchronization constraints that, e.g., match pairs of vertices of equal degree by providing a bijection between their edges. Synchronized Planarity then asks whether the graph admits a crossing-free embedding into the plane such that the orders of edges around synchronized vertices are consistent. We show, on the one hand, that Synchronized Planarity can be solved in quadratic time, and, on the other hand, that it serves as a powerful modeling language that lets us easily formulate several constrained planarity problems as instances of Synchronized Planarity. In particular, this lets us solve Clustered Planarity in quadratic time, where the most efficient previously known algorithm has an upper bound of $O(n^{8})$.
A Novel Point Inclusion Test for Convex Polygons Based on Voronoi Tessellations
Venue: arXiv cs.CG 2021
Year: 2021

The point inclusion tests for polygons, in other words the point-in-polygon (PIP) algorithms, are fundamental tools for many scientific fields related to computational geometry, and they have been studied for a long time. The PIP algorithms get direct or indirect geometric definition of a polygonal entity, and validate its containment of a given point. The PIP algorithms, which are working directly on the geometric entities, derive linear boundary definitions for the edges of the polygons. Moreover, almost all direct test methods rely on the two-point form of the line equation to partition the space into half-spaces. Voronoi tessellations use an alternate approach for half-space partitioning. Instead of line equation, distance comparison between generator points is used to accomplish the same task. Voronoi tessellations consist of convex polygons, which are defined between generator points. Therefore, Voronoi tessellations have become an inspiration for us to develop a new approach of the PIP testing, specialized for convex polygons. The equations, essential to the conversion of a convex polygon to a Voronoi polygon, are derived. As a reference, a very standard convex PIP testing algorithm, \textit{the sign of offset}, is selected for comparison. For generalization of the comparisons, \textit{the ray crossing} algorithm is used as another reference. All algorithms are implemented as vector and matrix operations without any branching. This enabled us to benefit from the CPU optimizations of the underlying linear algebra libraries. Experimentation showed that, our proposed algorithm can have comparable performance characteristics with the reference algorithms. Moreover, it has simplicity, both from a geometric representation and the mental model.
Dense Scene Multiple Object Tracking with Box-Plane Matching
Venue: arXiv cs.CV 2021
Year: 2021

Multiple Object Tracking (MOT) is an important task in computer vision. MOT is still challenging due to the occlusion problem, especially in dense scenes. Following the tracking-by-detection framework, we propose the Box-Plane Matching (BPM) method to improve the MOT performacne in dense scenes. First, we design the Layer-wise Aggregation Discriminative Model (LADM) to filter the noisy detections. Then, to associate remaining detections correctly, we introduce the Global Attention Feature Model (GAFM) to extract appearance feature and use it to calculate the appearance similarity between history tracklets and current detections. Finally, we propose the Box-Plane Matching strategy to achieve data association according to the motion similarity and appearance similarity between tracklets and detections. With the effectiveness of the three modules, our team achieves the 1st place on the Track-1 leaderboard in the ACM MM Grand Challenge HiEve 2020.
Privacy Enhancing Machine Learning via Removal of Unwanted Dependencies
Venue: arXiv cs.LG 2021
Year: 2021

The rapid rise of IoT and Big Data has facilitated copious data driven applications to enhance our quality of life. However, the omnipresent and all-encompassing nature of the data collection can generate privacy concerns. Hence, there is a strong need to develop techniques that ensure the data serve only the intended purposes, giving users control over the information they share. To this end, this paper studies new variants of supervised and adversarial learning methods, which remove the sensitive information in the data before they are sent out for a particular application. The explored methods optimize privacy preserving feature mappings and predictive models simultaneously in an end-to-end fashion. Additionally, the models are built with an emphasis on placing little computational burden on the user side so that the data can be desensitized on device in a cheap manner. Experimental results on mobile sensing and face datasets demonstrate that our models can successfully maintain the utility performances of predictive models while causing sensitive predictions to perform poorly.
Compression and Symmetry of Small-World Graphs and Structures
Venue: arXiv cs.IT 2021
Year: 2021

For various purposes and, in particular, in the context of data compression, a graph can be examined at three levels. Its structure can be described as the unlabeled version of the graph; then the labeling of its structure can be added; and finally, given then structure and labeling, the contents of the labels can be described. Determining the amount of information present at each level and quantifying the degree of dependence between them, requires the study of symmetry, graph automorphism, entropy, and graph compressibility. In this paper, we focus on a class of small-world graphs. These are geometric random graphs where vertices are first connected to their nearest neighbors on a circle and then pairs of non-neighbors are connected according to a distance-dependent probability distribution. We establish the degree distribution of this model, and use it to prove the model's asymmetry in an appropriate range of parameters. Then we derive the relevant entropy and structural entropy of these random graphs, in connection with graph compression.
Exploring Swedish & English fastText Embeddings for NER with the Transformer
Venue: arXiv cs.CL 2021
Year: 2021

In this paper, our main contributions are that embeddings from relatively smaller corpora can outperform ones from larger corpora and we make the new Swedish analogy test set publicly available. To achieve a good network performance in natural language processing (NLP) downstream tasks, several factors play important roles: dataset size, the right hyper-parameters, and well-trained embeddings. We show that, with the right set of hyper-parameters, good network performance can be reached even on smaller datasets. We evaluate the embeddings at both the intrinsic and extrinsic levels. The embeddings are deployed with the Transformer in named entity recognition (NER) task and significance tests conducted. This is done for both Swedish and English. We obtain better performance in both languages on the downstream task with smaller training data, compared to recently released, Common Crawl versions; and character n-grams appear useful for Swedish, a morphologically rich language.
TweepFake: about Detecting Deepfake Tweets
Venue: arXiv cs.CL 2021
Year: 2021

The recent advances in language modeling significantly improved the generative capabilities of deep neural models: in 2019 OpenAI released GPT-2, a pre-trained language model that can autonomously generate coherent, non-trivial and human-like text samples. Since then, ever more powerful text generative models have been developed. Adversaries can exploit these tremendous generative capabilities to enhance social bots that will have the ability to write plausible deepfake messages, hoping to contaminate public debate. To prevent this, it is crucial to develop deepfake social media messages detection systems. However, to the best of our knowledge no one has ever addressed the detection of machine-generated texts on social networks like Twitter or Facebook. With the aim of helping the research in this detection field, we collected the first dataset of \real deepfake tweets, TweepFake. It is real in the sense that each deepfake tweet was actually posted on Twitter. We collected tweets from a total of 23 bots, imitating 17 human accounts. The bots are based on various generation techniques, i.e., Markov Chains, RNN, RNN+Markov, LSTM, GPT-2. We also randomly selected tweets from the humans imitated by the bots to have an overall balanced dataset of 25,572 tweets (half human and half bots generated). The dataset is publicly available on Kaggle. Lastly, we evaluated 13 deepfake text detection methods (based on various state-of-the-art approaches) to both demonstrate the challenges that Tweepfake poses and create a solid baseline of detection techniques. We hope that TweepFake can offer the opportunity to tackle the deepfake detection on social media messages as well.
Possibility conditions for Open Access
Venue: arXiv cs.GT 2021
Year: 2021

This is an attempt to formalize the conditions of possibility for free, libre, open access to scientific knowledge within a game. The challenge is to enunciate the terms under which agents participating in the Grand conversation of science would be willing to open share, exchange, negotiate or surrender their contributions, considering their corresponding intentions, goals, beliefs and expected utilities. Many conclusions can be drawn from the game here described. We have made many simplifying decisions along the modelling process that must be taken into account as a determining context for those conclusions, of course. It can be safely state, however, that under the current conditions of the game, Editors will keep betting on Toll Access, knowledge distribution models even if all the other Academic agent go for Open Access.