OpenRaiser/Intern-Atlas huggingface dataset:
Characterizing the Effect of Sentence Context on Word Meanings: Mapping Brain to Behavior
Venue: arXiv cs.CL 2021
Year: 2021

Semantic feature models have become a popular tool for prediction and interpretation of fMRI data. In particular, prior work has shown that differences in the fMRI patterns in sentence reading can be explained by context-dependent changes in the semantic feature representations of the words. However, whether the subjects are aware of such changes and agree with them has been an open question. This paper aims to answer this question through a human-subject study. Subjects were asked to judge how the word change from their generic meaning when the words were used in specific sentences. The judgements were consistent with the model predictions well above chance. Thus, the results support the hypothesis that word meaning change systematically depending on sentence context.
WaveFuse: A Unified Deep Framework for Image Fusion with Discrete Wavelet Transform
Venue: arXiv cs.CV 2021
Year: 2021

We propose an unsupervised image fusion architecture for multiple application scenarios based on the combination of multi-scale discrete wavelet transform through regional energy and deep learning. To our best knowledge, this is the first time the conventional image fusion method has been combined with deep learning. The useful information of feature maps can be utilized adequately through multi-scale discrete wavelet transform in our proposed method.Compared with other state-of-the-art fusion method, the proposed algorithm exhibits better fusion performance in both subjective and objective evaluation. Moreover, it's worth mentioning that comparable fusion performance trained in COCO dataset can be obtained by training with a much smaller dataset with only hundreds of images chosen randomly from COCO. Hence, the training time is shortened substantially, leading to the improvement of the model's performance both in practicality and training efficiency.
Twin-width III: Max Independent Set, Min Dominating Set, and Coloring
Venue: arXiv cs.DS 2021
Year: 2021

We recently introduced the graph invariant twin-width, and showed that first-order model checking can be solved in time $f(d,k)n$ for $n$-vertex graphs given with a witness that the twin-width is at most $d$, called $d$-contraction sequence or $d$-sequence, and formulas of size $k$ [Bonnet et al., FOCS '20]. The inevitable price to pay for such a general result is that $f$ is a tower of exponentials of height roughly $k$. In this paper, we show that algorithms based on twin-width need not be impractical. We present $2^{O(k)}n$-time algorithms for $k$-Independent Set, $r$-Scattered Set, $k$-Clique, and $k$-Dominating Set when an $O(1)$-sequence is provided. We further show how to solve weighted $k$-Independent Set, Subgraph Isomorphism, and Induced Subgraph Isomorphism, in time $2^{O(k \log k)}n$. These algorithms are based on a dynamic programming scheme following the sequence of contractions forward. We then show a second algorithmic use of the contraction sequence, by starting at its end and rewinding it. As an example, we establish that bounded twin-width classes are $χ$-bounded. This significantly extends the $χ$-boundedness of bounded rank-width classes, and does so with a very concise proof. The third algorithmic use of twin-width builds on the second one. Playing the contraction sequence backward, we show that bounded twin-width graphs can be edge-partitioned into a linear number of bicliques, such that both sides of the bicliques are on consecutive vertices, in a fixed vertex ordering. Given that biclique edge-partition, we show how to solve the unweighted Single-Source Shortest Paths and hence All-Pairs Shortest Paths in sublinear time $O(n \log n)$ and time $O(n^2 \log n)$, respectively. Finally we show that Min Dominating Set and related problems have constant integrality gaps on bounded twin-width classes, thereby getting constant approximations on these classes.
Downlink channel access performance of NR-U: Impact of numerology and mini-slots on coexistence with Wi-Fi in the 5 GHz band
Venue: arXiv cs.NI 2021
Year: 2021

Coexistence between cellular systems and Wi-Fi gained the attention of the research community when LTE License Assisted Access (LAA) entered the unlicensed band. The recent introduction of NR-U as part of 5G introduces new coexistence opportunities because it implements scalable numerology (flexible subcarrier spacing and OFDM symbol lengths), and non-slot based scheduling (mini-slots), which considerably impact channel access. This paper analyzes the impact of NR-U settings on its coexistence with Wi-Fi networks and compares it with LAA operation using simulations and experiments. First, we propose a downlink channel access simulation model, which addresses the problem of the dependency and non-uniformity of transmission attempts of different nodes, as a result of the synchronization mechanism introduced by NR-U. Second, we validate the accuracy of the proposed model using FPGA-based LAA, NR-U, and Wi-Fi prototypes with over-the-air transmissions. Additionally, we show that replacing LAA with NR-U would not only allow to overcome the problem of bandwidth wastage caused by reservation signals but also, in some cases, to preserve fairness in channel access for both scheduled and random-access systems. Finally, we conclude that fair coexistence of the aforementioned systems in unlicensed bands is not guaranteed in general, and novel mechanisms are necessary for improving the sharing of resources between scheduled and contention-based technologies.
On the Convergence of Tsetlin Machines for the IDENTITY- and NOT Operators
Venue: arXiv cs.AI 2021
Year: 2021

The Tsetlin Machine (TM) is a recent machine learning algorithm with several distinct properties, such as interpretability, simplicity, and hardware-friendliness. Although numerous empirical evaluations report on its performance, the mathematical analysis of its convergence is still open. In this article, we analyze the convergence of the TM with only one clause involved for classification. More specifically, we examine two basic logical operators, namely, the "IDENTITY"- and "NOT" operators. Our analysis reveals that the TM, with just one clause, can converge correctly to the intended logical operator, learning from training data over an infinite time horizon. Besides, it can capture arbitrarily rare patterns and select the most accurate one when two candidate patterns are incompatible, by configuring a granularity parameter. The analysis of the convergence of the two basic operators lays the foundation for analyzing other logical operators. These analyses altogether, from a mathematical perspective, provide new insights on why TMs have obtained state-of-the-art performance on several pattern recognition problems.
A Lifelong Learning Approach to Mobile Robot Navigation
Venue: arXiv cs.RO 2021
Year: 2021

This paper presents a self-improving lifelong learning framework for a mobile robot navigating in different environments. Classical static navigation methods require environment-specific in-situ system adjustment, e.g. from human experts, or may repeat their mistakes regardless of how many times they have navigated in the same environment. Having the potential to improve with experience, learning-based navigation is highly dependent on access to training resources, e.g. sufficient memory and fast computation, and is prone to forgetting previously learned capability, especially when facing different environments. In this work, we propose Lifelong Learning for Navigation (LLfN) which (1) improves a mobile robot's navigation behavior purely based on its own experience, and (2) retains the robot's capability to navigate in previous environments after learning in new ones. LLfN is implemented and tested entirely onboard a physical robot with a limited memory and computation budget.
Families In Wild Multimedia: A Multimodal Database for Recognizing Kinship
Venue: arXiv cs.CV 2021
Year: 2021

Kinship, a soft biometric detectable in media, is fundamental for a myriad of use-cases. Despite the difficulty of detecting kinship, annual data challenges using still-images have consistently improved performances and attracted new researchers. Now, systems reach performance levels unforeseeable a decade ago, closing in on performances acceptable to deploy in practice. Like other biometric tasks, we expect systems can receive help from other modalities. We hypothesize that adding modalities to FIW, which has only still-images, will improve performance. Thus, to narrow the gap between research and reality and enhance the power of kinship recognition systems, we extend FIW with multimedia (MM) data (i.e., video, audio, and text captions). Specifically, we introduce the first publicly available multi-task MM kinship dataset. To build FIW MM, we developed machinery to automatically collect, annotate, and prepare the data, requiring minimal human input and no financial cost. The proposed MM corpus allows the problem statements to be more realistic template-based protocols. We show significant improvements in all benchmarks with the added modalities. The results highlight edge cases to inspire future research with different areas of improvement. FIW MM supplies the data needed to increase the potential of automated systems to detect kinship in MM. It also allows experts from diverse fields to collaborate in novel ways.
Efficient Cross-Shard Transaction Execution in Sharded Blockchains
Venue: arXiv cs.CR 2021
Year: 2021

Sharding is a promising blockchain scaling solution. But it currently suffers from high latency and low throughput when it comes to cross-shard transactions, i.e., transactions that require coordination from multiple shards. The root cause of these limitations arise from the use of the classic two-phase commit protocol, which involves locking assets for extended periods of time. This paper presents Rivet, a new paradigm for blockchain sharding that achieves lower latency and higher throughput for cross-shard transactions. Rivet has a single reference shard running consensus, and multiple worker shards maintaining disjoint states and processing a subset of transactions in the system. Rivet obviates the need for consensus within each worker shard, and as a result, tolerates more failures within a shard and lowers communication overhead. We prove the correctness and security of Rivet. We also propose a more realistic framework for evaluating sharded blockchains by creating a benchmark based on real Ethereum transactions. An evaluation of our prototype implementation of Rivet and the baseline two-phase commit, atop 50+ AWS EC2 instances, using our evaluation framework demonstrates the latency and throughput improvements for cross-shard transactions.
MLR-SNet: Transferable LR Schedules for Heterogeneous Tasks
Venue: arXiv cs.LG 2021
Year: 2021

The learning rate (LR) is one of the most important hyper-parameters in stochastic gradient descent (SGD) algorithm for training deep neural networks (DNN). However, current hand-designed LR schedules need to manually pre-specify a fixed form, which limits their ability to adapt practical non-convex optimization problems due to the significant diversification of training dynamics. Meanwhile, it always needs to search proper LR schedules from scratch for new tasks, which, however, are often largely different with task variations, like data modalities, network architectures, or training data capacities. To address this learning-rate-schedule setting issues, we propose to parameterize LR schedules with an explicit mapping formulation, called \textit{MLR-SNet}. The learnable parameterized structure brings more flexibility for MLR-SNet to learn a proper LR schedule to comply with the training dynamics of DNN. Image and text classification benchmark experiments substantiate the capability of our method for achieving proper LR schedules. Moreover, the explicit parameterized structure makes the meta-learned LR schedules capable of being transferable and plug-and-play, which can be easily generalized to new heterogeneous tasks. We transfer our meta-learned MLR-SNet to query tasks like different training epochs, network architectures, data modalities, dataset sizes from the training ones, and achieve comparable or even better performance compared with hand-designed LR schedules specifically designed for the query tasks. The robustness of MLR-SNet is also substantiated when the training data are biased with corrupted noise. We further prove the convergence of the SGD algorithm equipped with LR schedule produced by our MLR-Net, with the convergence rate comparable to the best-known ones of the algorithm for solving the problem.
A convergence analysis of the price of anarchy in atomic congestion games
Venue: arXiv cs.GT 2021
Year: 2021

This paper provides a comprehensive convergence analysis of the PoA of both pure and mixed Nash equilibria in atomic congestion games with unsplittable demands.
Intersectional Affirmative Action Policies for Top-k Candidates Selection
Venue: arXiv cs.CY 2021
Year: 2021

We study the problem of selecting the top-k candidates from a pool of applicants, where each candidate is associated with a score indicating his/her aptitude. Depending on the specific scenario, such as job search or college admissions, these scores may be the results of standardized tests or other predictors of future performance and utility. We consider a situation in which some groups of candidates experience historical and present disadvantage that makes their chances of being accepted much lower than other groups. In these circumstances, we wish to apply an affirmative action policy to reduce acceptance rate disparities, while avoiding any large decrease in the aptitude of the candidates that are eventually selected. Our algorithmic design is motivated by the frequently observed phenomenon that discrimination disproportionately affects individuals who simultaneously belong to multiple disadvantaged groups, defined along intersecting dimensions such as gender, race, sexual orientation, socio-economic status, and disability. In short, our algorithm's objective is to simultaneously: select candidates with high utility, and level up the representation of disadvantaged intersectional classes. This naturally involves trade-offs and is computationally challenging due to the the combinatorial explosion of potential subgroups as more attributes are considered. We propose two algorithms to solve this problem, analyze them, and evaluate them experimentally using a dataset of university application scores and admissions to bachelor degrees in an OECD country. Our conclusion is that it is possible to significantly reduce disparities in admission rates affecting intersectional classes with a small loss in terms of selected candidate aptitude. To the best of our knowledge, we are the first to study fairness constraints with regards to intersectional classes in the context of top-k selection.
Event-based Stereo Visual Odometry
Venue: arXiv cs.CV 2021
Year: 2021

Event-based cameras are bio-inspired vision sensors whose pixels work independently from each other and respond asynchronously to brightness changes, with microsecond resolution. Their advantages make it possible to tackle challenging scenarios in robotics, such as high-speed and high dynamic range scenes. We present a solution to the problem of visual odometry from the data acquired by a stereo event-based camera rig. Our system follows a parallel tracking-and-mapping approach, where novel solutions to each subproblem (3D reconstruction and camera pose estimation) are developed with two objectives in mind: being principled and efficient, for real-time operation with commodity hardware. To this end, we seek to maximize the spatio-temporal consistency of stereo event-based data while using a simple and efficient representation. Specifically, the mapping module builds a semi-dense 3D map of the scene by fusing depth estimates from multiple local viewpoints (obtained by spatio-temporal consistency) in a probabilistic fashion. The tracking module recovers the pose of the stereo rig by solving a registration problem that naturally arises due to the chosen map and event data representation. Experiments on publicly available datasets and on our own recordings demonstrate the versatility of the proposed method in natural scenes with general 6-DoF motion. The system successfully leverages the advantages of event-based cameras to perform visual odometry in challenging illumination conditions, such as low-light and high dynamic range, while running in real-time on a standard CPU. We release the software and dataset under an open source licence to foster research in the emerging topic of event-based SLAM.
The Unreasonable Effectiveness of Machine Learning in Moldavian versus Romanian Dialect Identification
Venue: arXiv cs.CL 2021
Year: 2021

Motivated by the seemingly high accuracy levels of machine learning models in Moldavian versus Romanian dialect identification and the increasing research interest on this topic, we provide a follow-up on the Moldavian versus Romanian Cross-Dialect Topic Identification (MRC) shared task of the VarDial 2019 Evaluation Campaign. The shared task included two sub-task types: one that consisted in discriminating between the Moldavian and Romanian dialects and one that consisted in classifying documents by topic across the two dialects of Romanian. Participants achieved impressive scores, e.g. the top model for Moldavian versus Romanian dialect identification obtained a macro F1 score of 0.895. We conduct a subjective evaluation by human annotators, showing that humans attain much lower accuracy rates compared to machine learning (ML) models. Hence, it remains unclear why the methods proposed by participants attain such high accuracy rates. Our goal is to understand (i) why the proposed methods work so well (by visualizing the discriminative features) and (ii) to what extent these methods can keep their high accuracy levels, e.g. when we shorten the text samples to single sentences or when we use tweets at inference time. A secondary goal of our work is to propose an improved ML model using ensemble learning. Our experiments show that ML models can accurately identify the dialects, even at the sentence level and across different domains (news articles versus tweets). We also analyze the most discriminative features of the best performing models, providing some explanations behind the decisions taken by these models. Interestingly, we learn new dialectal patterns previously unknown to us or to our human annotators. Furthermore, we conduct experiments showing that the machine learning performance on the MRC shared task can be improved through an ensemble based on stacking.
Domain-Specific Language Model Pretraining for Biomedical Natural Language Processing
Venue: arXiv cs.CL 2021
Year: 2021

Pretraining large neural language models, such as BERT, has led to impressive gains on many natural language processing (NLP) tasks. However, most pretraining efforts focus on general domain corpora, such as newswire and Web. A prevailing assumption is that even domain-specific pretraining can benefit by starting from general-domain language models. In this paper, we challenge this assumption by showing that for domains with abundant unlabeled text, such as biomedicine, pretraining language models from scratch results in substantial gains over continual pretraining of general-domain language models. To facilitate this investigation, we compile a comprehensive biomedical NLP benchmark from publicly-available datasets. Our experiments show that domain-specific pretraining serves as a solid foundation for a wide range of biomedical NLP tasks, leading to new state-of-the-art results across the board. Further, in conducting a thorough evaluation of modeling choices, both for pretraining and task-specific fine-tuning, we discover that some common practices are unnecessary with BERT models, such as using complex tagging schemes in named entity recognition (NER). To help accelerate research in biomedical NLP, we have released our state-of-the-art pretrained and task-specific models for the community, and created a leaderboard featuring our BLURB benchmark (short for Biomedical Language Understanding & Reasoning Benchmark) at https://aka.ms/BLURB.
On Learning Universal Representations Across Languages
Venue: arXiv cs.CL 2021
Year: 2021

Recent studies have demonstrated the overwhelming advantage of cross-lingual pre-trained models (PTMs), such as multilingual BERT and XLM, on cross-lingual NLP tasks. However, existing approaches essentially capture the co-occurrence among tokens through involving the masked language model (MLM) objective with token-level cross entropy. In this work, we extend these approaches to learn sentence-level representations and show the effectiveness on cross-lingual understanding and generation. Specifically, we propose a Hierarchical Contrastive Learning (HiCTL) method to (1) learn universal representations for parallel sentences distributed in one or multiple languages and (2) distinguish the semantically-related words from a shared cross-lingual vocabulary for each sentence. We conduct evaluations on two challenging cross-lingual tasks, XTREME and machine translation. Experimental results show that the HiCTL outperforms the state-of-the-art XLM-R by an absolute gain of 4.2% accuracy on the XTREME benchmark as well as achieves substantial improvements on both of the high-resource and low-resource English-to-X translation tasks over strong baselines.
Low Dimensional State Representation Learning with Reward-shaped Priors
Venue: arXiv cs.LG 2021
Year: 2021

Reinforcement Learning has been able to solve many complicated robotics tasks without any need for feature engineering in an end-to-end fashion. However, learning the optimal policy directly from the sensory inputs, i.e the observations, often requires processing and storage of a huge amount of data. In the context of robotics, the cost of data from real robotics hardware is usually very high, thus solutions that achieve high sample-efficiency are needed. We propose a method that aims at learning a mapping from the observations into a lower-dimensional state space. This mapping is learned with unsupervised learning using loss functions shaped to incorporate prior knowledge of the environment and the task. Using the samples from the state space, the optimal policy is quickly and efficiently learned. We test the method on several mobile robot navigation tasks in a simulation environment and also on a real robot.
5G Network Planning under Service and EMF Constraints: Formulation and Solutions
Venue: arXiv cs.NI 2021
Year: 2021

We target the planning of a 5G cellular network under 5G service and ElectroMagnetic Fields (EMFs) constraints. We initially model the problem with a Mixed Integer Linear Programming (MILP) formulation. The pursued objective is a weighed function of next-generation Node-B (gNB) installation costs and 5G service coverage level from a massive Multiple Input Multiple Output (MIMO) system. In addition, we precisely model restrictive EMF constraints and we integrate scaling parameters to estimate the power radiated by 5G gNBs. Since the considered planning problem is NP-Hard, and therefore very challenging to be solved even for small problem instances, we design an efficient heuristic, called PLATEA, to practically solve it. Results, obtained over a realistic scenario that includes EMF exposure from pre-5G technologies (e.g., 2G, 3G, 4G), prove that the cellular planning selected by PLATEA ensures 5G service and restrictive EMF constraints. However, we demonstrate that the results are strongly affected by: i) the relative weight between gNB installation costs and 5G service coverage level, ii) the scaling parameters to estimate the exposure generated by 5G gNBs, iii) the amount of exposure from pre-5G technologies and iv) the adopted frequency reuse scheme.