OpenRaiser/Intern-Atlas huggingface dataset:
CoInGP: Convolutional Inpainting with Genetic Programming
Venue: arXiv cs.NE 2021
Year: 2021

We investigate the use of Genetic Programming (GP) as a convolutional predictor for missing pixels in images. The training phase is performed by sweeping a sliding window over an image, where the pixels on the border represent the inputs of a GP tree. The output of the tree is taken as the predicted value for the central pixel. We consider two topologies for the sliding window, namely the Moore and the Von Neumann neighborhood. The best GP tree scoring the lowest prediction error over the training set is then used to predict the pixels in the test set. We experimentally assess our approach through two experiments. In the first one, we train a GP tree over a subset of 1000 complete images from the MNIST dataset. The results show that GP can learn the distribution of the pixels with respect to a simple baseline predictor, with no significant differences observed between the two neighborhoods. In the second experiment, we train a GP convolutional predictor on two degraded images, removing around 20% of their pixels. In this case, we observe that the Moore neighborhood works better, although the Von Neumann neighborhood allows for a larger training set.
UAV-Enabled Data Collection for Wireless Sensor Networks with Distributed Beamforming
Venue: arXiv cs.IT 2021
Year: 2021

This paper studies an unmanned aerial vehicle (UAV)-enabled wireless sensor network, in which one UAV flies in the sky to collect the data transmitted from a set of ground nodes (GNs) via distributed beamforming. We consider two scenarios with delay-tolerant and delay-sensitive applications, in which the GNs send the common/shared messages to the UAV via adaptive- and fixed-rate transmissions, respectively. For the two scenarios, we aim to maximize the average data-rate throughput and minimize the transmission outage probability, respectively, by jointly optimizing the UAV's trajectory design and the GNs' transmit power allocation over time, subject to the UAV's flight speed constraints and the GNs' individual average power constraints. However, the two formulated problems are both non-convex and thus generally difficult to be optimally solved. To tackle this issue, we first consider the relaxed problems in the ideal case with the UAV's flight speed constraints ignored, for which the well-structured optimal solutions are obtained to reveal the fundamental performance upper bounds. It is shown that for the two approximate problems, the optimal trajectory solutions have the same multi-location-hovering structure, but with different optimal power allocation strategies. Next, for the general problems with the UAV's flight speed constraints considered, we propose efficient algorithms to obtain high-quality solutions by using the techniques from convex optimization and approximation. Finally, numerical results show that our proposed designs significantly outperform other benchmark schemes, in terms of the achieved data-rate throughput and outage probability under the two scenarios. It is also observed that when the mission period becomes sufficiently long, our proposed designs approach the performance upper bounds when the UAV's flight speed constraints are ignored.
Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-kSAT
Venue: arXiv cs.CC 2021
Year: 2021

We prove tight upper and lower bounds on approximation ratios of all Boolean Max-2CSP problems in the streaming model. Specifically, for every type of Max-2CSP problem, we give an explicit constant $α$, s.t. for any $ε>0$ (i) there is an $(α-ε)$-streaming approximation using space $O(\log{n})$; and (ii) any $(α+ε)$-streaming approximation requires space $Ω(\sqrt{n})$. This generalizes the celebrated work of [Kapralov, Khanna, Sudan SODA 2015; Kapralov, Krachun STOC 2019], who showed that the optimal approximation ratio for Max-CUT was $1/2$. Prior to this work, the problem of determining this ratio was open for all other Max-2CSPs. Our results are quite surprising for some specific Max-2CSPs. For the Max-DCUT problem, there was a gap between an upper bound of $1/2$ and a lower bound of $2/5$ [Guruswami, Velingker, Velusamy APPROX 2017]. We show that neither of these bounds is tight, and the optimal ratio for Max-DCUT is $4/9$. We also establish that the tight approximation for Max-2SAT is $\sqrt{2}/2$, and for Exact Max-2SAT it is $3/4$. As a byproduct, our result gives a separation between space-efficient approximations for Max-2SAT and Exact Max-2SAT. This is in sharp contrast to the setting of polynomial-time algorithms with polynomial space, where the two problems are known to be equally hard to approximate. Finally, we prove that the tight streaming approximation for \mksat{} is $\sqrt{2}/2$ for every $k\geq2$.
Asymptotically Achieving Centralized Rate on the Decentralized Network MISO Channel
Venue: arXiv cs.IT 2021
Year: 2021

We analyze the high-SNR regime of the MxK Network MISO channel in which each transmitter has access to a different channel estimate, possibly with different precision. It has been recently shown that, for some regimes, this setting attains the same Degrees-of-Freedom as the ideal centralized setting with perfect CSI sharing, in which all the transmitters are endowed with the best estimate available at any transmitter. This result is restricted by the limitations of the DoF metric, as it only provides information about the slope of growth of the capacity as a function of the SNR, without any insight about the possible performance at a given SNR. To overcome this limitation, we analyze the affine approximation of the rate on the high-SNR regime for this decentralized Network MISO setting for the antenna configurations in which it achieves the DoF of the centralized setting. We show that, for a regime of antenna configurations, it is possible to asymptotically attain the same achievable rate as in the ideal centralized scenario. Consequently, it is possible to achieve the beamforming gain of the ideal perfect-CSI-sharing setting even if only a subset of transmitters is endowed with precise CSI, which can be exploited in scenarios such as distributed massive MIMO where the number of transmit antennas is much bigger than the number of served users. This outcome is a consequence of the synergistic compromise between CSI precision at the transmitters and consistency between the locally-computed precoders, which is an inherent trade-off of decentralized settings that does not exist in a centralized CSI configuration. We propose a precoding scheme achieving the previous result, which is built on an uneven structure in which some transmitters reduce the precision of their own precoding for the sake of using transmission parameters that can be more easily predicted by the other transmitters.
An Almost Optimal Approximation Algorithm for Monotone Submodular Multiple Knapsack
Venue: arXiv cs.DS 2021
Year: 2021

We study the problem of maximizing a monotone submodular function subject to a Multiple Knapsack constraint. The input is a set $I$ of items, each has a non-negative weight, and a set of bins of arbitrary capacities. Also, we are given a submodular, monotone and non-negative function $f$ over subsets of the items. The objective is to find a packing of a subset of items $A \subseteq I$ in the bins such that $f(A)$ is maximized. Our main result is an almost optimal polynomial time $(1-e^{-1}-\varepsilon)$-approximation algorithm for the problem, for any $\varepsilon>0$. The algorithm relies on a structuring technique which converts a general multiple knapsack constraint to a constraint in which the bins are partitioned into groups of exponentially increasing cardinalities, each consisting of bins of uniform capacity. We derive the result by combining structuring with a refined analysis of techniques for submodular optimization subject to knapsack constraints.
Filter Grafting for Deep Neural Networks: Reason, Method, and Cultivation
Venue: arXiv cs.LG 2021
Year: 2021

Filter is the key component in modern convolutional neural networks (CNNs). However, since CNNs are usually over-parameterized, a pre-trained network always contain some invalid (unimportant) filters. These filters have relatively small $l_{1}$ norm and contribute little to the output (\textbf{Reason}). While filter pruning removes these invalid filters for efficiency consideration, we tend to reactivate them to improve the representation capability of CNNs. In this paper, we introduce filter grafting (\textbf{Method}) to achieve this goal. The activation is processed by grafting external information (weights) into invalid filters. To better perform the grafting, we develop a novel criterion to measure the information of filters and an adaptive weighting strategy to balance the grafted information among networks. After the grafting operation, the network has fewer invalid filters compared with its initial state, enpowering the model with more representation capacity. Meanwhile, since grafting is operated reciprocally on all networks involved, we find that grafting may lose the information of valid filters when improving invalid filters. To gain a universal improvement on both valid and invalid filters, we compensate grafting with distillation (\textbf{Cultivation}) to overcome the drawback of grafting . Extensive experiments are performed on the classification and recognition tasks to show the superiority of our method. Code is available at \textcolor{black}{\emph{https://github.com/fxmeng/filter-grafting}}.
Binary MIMO Detection via Homotopy Optimization and Its Deep Adaptation
Venue: arXiv cs.IT 2021
Year: 2021

In this paper we consider maximum-likelihood (ML) MIMO detection under one-bit quantized observations and binary symbol constellations. This problem is motivated by the recent interest in adopting coarse quantization in massive MIMO systems--as an effective way to scale down the hardware complexity and energy consumption. Classical MIMO detection techniques consider unquantized observations, and many of them are not applicable to the one-bit MIMO case. We develop a new non-convex optimization algorithm for the one-bit ML MIMO detection problem, using a strategy called homotopy optimization. The idea is to transform the ML problem into a sequence of approximate problems, from easy (convex) to hard (close to ML), and with each problem being a gradual modification of its previous. Then, our attempt is to iteratively trace the solution path of these approximate problems. This homotopy algorithm is well suited to the application of deep unfolding, a recently popular approach for turning certain model-based algorithms into data-driven, and performance enhanced, ones. While our initial focus is on one-bit MIMO detection, the proposed technique also applies naturally to the classical unquantized MIMO detection. We performed extensive simulations and show that the proposed homotopy algorithms, both non-deep and deep, have satisfactory bit-error probability performance compared to many state-of-the-art algorithms. Also, the deep homotopy algorithm has attractively low computational complexity.
A verifiably secure and proportional committee election rule
Venue: arXiv cs.DS 2021
Year: 2021

The property of proportional representation in approval-based committee elections has appeared in the social choice literature for over a century, and is typically understood as avoiding the underrepresentation of minorities. However, we argue that the security of some distributed systems is directly linked to the opposite goal of avoiding the overrepresentation of any minority, a goal not previously formalized that leads us to an optimization objective known as maximin support. After providing a thorough analysis of the computational complexity of this objective, we propose a new efficient election rule that simultaneously achieves a) a constant-factor approximation guarantee for it, and b) the property of proportional justified representation (PJR) - one of the strongest forms of proportional representation. However, the most striking feature of the new rule is that one can verify in linear time that the winning committee satisfies the two aforementioned guarantees, even when the algorithm is executed by an untrusted party who only communicates the output. As a result, the rule can be adapted into a verifiable computing scheme. Moreover, its verification procedure easily admits parallel processing for further efficiency. Our work is motivated by an application on blockchain networks that implement Nominated Proof-of-Stake, where the community elects a committee of validators to participate in the consensus protocol, and where preventing overrepresentation protects the network against attacks by an adversarial minority. Our election rule enables a validator selection protocol with formal guarantees on security and proportionality, and its adaptation as a verifiable computing scheme with a parallelized verification proves to be key for its successful implementation given the computationally limited nature of the blockchain architecture.
Capturing Global Informativeness in Open Domain Keyphrase Extraction
Venue: arXiv cs.CL 2021
Year: 2021

Open-domain KeyPhrase Extraction (KPE) aims to extract keyphrases from documents without domain or quality restrictions, e.g., web pages with variant domains and qualities. Recently, neural methods have shown promising results in many KPE tasks due to their powerful capacity for modeling contextual semantics of the given documents. However, we empirically show that most neural KPE methods prefer to extract keyphrases with good phraseness, such as short and entity-style n-grams, instead of globally informative keyphrases from open-domain documents. This paper presents JointKPE, an open-domain KPE architecture built on pre-trained language models, which can capture both local phraseness and global informativeness when extracting keyphrases. JointKPE learns to rank keyphrases by estimating their informativeness in the entire document and is jointly trained on the keyphrase chunking task to guarantee the phraseness of keyphrase candidates. Experiments on two large KPE datasets with diverse domains, OpenKP and KP20k, demonstrate the effectiveness of JointKPE on different pre-trained variants in open-domain scenarios. Further analyses reveal the significant advantages of JointKPE in predicting long and non-entity keyphrases, which are challenging for previous neural KPE methods. Our code is publicly available at https://github.com/thunlp/BERT-KPE.
Cross-modal Speaker Verification and Recognition: A Multilingual Perspective
Venue: arXiv cs.CV 2021
Year: 2021

Recent years have seen a surge in finding association between faces and voices within a cross-modal biometric application along with speaker recognition. Inspired from this, we introduce a challenging task in establishing association between faces and voices across multiple languages spoken by the same set of persons. The aim of this paper is to answer two closely related questions: "Is face-voice association language independent?" and "Can a speaker be recognised irrespective of the spoken language?". These two questions are very important to understand effectiveness and to boost development of multilingual biometric systems. To answer them, we collected a Multilingual Audio-Visual dataset, containing human speech clips of $154$ identities with $3$ language annotations extracted from various videos uploaded online. Extensive experiments on the three splits of the proposed dataset have been performed to investigate and answer these novel research questions that clearly point out the relevance of the multilingual problem.
Word Equations: Inherently Interpretable Sparse Word Embeddingsthrough Sparse Coding
Venue: arXiv cs.CL 2021
Year: 2021

Word embeddings are a powerful natural language processing technique, but they are extremely difficult to interpret. To enable interpretable NLP models, we create vectors where each dimension is inherently interpretable. By inherently interpretable, we mean a system where each dimension is associated with some human understandable hint that can describe the meaning of that dimension. In order to create more interpretable word embeddings, we transform pretrained dense word embeddings into sparse embeddings. These new embeddings are inherently interpretable: each of their dimensions is created from and represents a natural language word or specific grammatical concept. We construct these embeddings through sparse coding, where each vector in the basis set is itself a word embedding. Therefore, each dimension of our sparse vectors corresponds to a natural language word. We also show that models trained using these sparse embeddings can achieve good performance and are more interpretable in practice, including through human evaluations.
Conversations with Search Engines: SERP-based Conversational Response Generation
Venue: arXiv cs.IR 2021
Year: 2021

In this paper, we address the problem of answering complex information needs by conversing conversations with search engines, in the sense that users can express their queries in natural language, and directly receivethe information they need from a short system response in a conversational manner. Recently, there have been some attempts towards a similar goal, e.g., studies on Conversational Agents (CAs) and Conversational Search (CS). However, they either do not address complex information needs, or they are limited to the development of conceptual frameworks and/or laboratory-based user studies. We pursue two goals in this paper: (1) the creation of a suitable dataset, the Search as a Conversation (SaaC) dataset, for the development of pipelines for conversations with search engines, and (2) the development of astate-of-the-art pipeline for conversations with search engines, the Conversations with Search Engines (CaSE), using this dataset. SaaC is built based on a multi-turn conversational search dataset, where we further employ workers from a crowdsourcing platform to summarize each relevant passage into a short, conversational response. CaSE enhances the state-of-the-art by introducing a supporting token identification module and aprior-aware pointer generator, which enables us to generate more accurate responses. We carry out experiments to show that CaSE is able to outperform strong baselines. We also conduct extensive analyses on the SaaC dataset to show where there is room for further improvement beyond CaSE. Finally, we release the SaaC dataset and the code for CaSE and all models used for comparison to facilitate future research on this topic.
Bipartite Stochastic Matching: Online, Random Order, and I.I.D. Models
Venue: arXiv cs.DS 2021
Year: 2021

Within the context of stochastic probing with commitment, we consider the online stochastic matching problem; that is, the one sided online bipartite matching problem where edges adjacent to an online node must be probed to determine if they exist, based on known edge probabilities. If a probed edge exists, it must be used in the matching (if possible). We study this problem in the generality of a patience (or budget) constraint which limits the number of probes that can be made to edges adjacent to an online node. The patience constraint results in modelling and computational efficiency issues that are not encountered in the special cases of unit patience and full (i.e., unlimited) patience. The stochastic matching problem leads to a variety of settings. Our main contribution is to provide a new LP relaxation and a unified approach for establishing new and improved competitive bounds in three different input model settings (namely, adversarial, random order, and known i.i.d.). In all these settings, the algorithm does not have any control on the ordering of the online nodes. We establish competitive bounds in these settings, all of which generalize the standard non-stochastic setting when edges do not need to be probed (i.e., exist with certainty). All of our competitive ratios hold for arbitrary edge probabilities and patience constraints: (1) A $1-1/e$ ratio when the stochastic graph is known, offline vertices are weighted and online arrivals are adversarial. (2) A $1-1/e$ ratio when the stochastic graph is known, edges are weighted, and online arrivals are given in random order (i.e., in ROM, the random order model). (3) A $1-1/e$ ratio when online arrivals are drawn i.i.d. from a known stochastic type graph and edges are weighted. (4) A (tight) $1/e$ ratio when the stochastic graph is unknown, edges are weighted and online arrivals are given in random order.
Informed Sampling for Diversity in Concept-to-Text NLG
Venue: arXiv cs.CL 2021
Year: 2021

Deep-learning models for language generation tasks tend to produce repetitive output. Various methods have been proposed to encourage lexical diversity during decoding, but this often comes at a cost to the perceived fluency and adequacy of the output. In this work, we propose to ameliorate this cost by using an Imitation Learning approach to explore the level of diversity that a language generation model can reliably produce. Specifically, we augment the decoding process with a meta-classifier trained to distinguish which words at any given timestep will lead to high-quality output. We focus our experiments on concept-to-text generation where models are sensitive to the inclusion of irrelevant words due to the strict relation between input and output. Our analysis shows that previous methods for diversity underperform in this setting, while human evaluation suggests that our proposed method achieves a high level of diversity with minimal effect to the output's fluency and adequacy.
Whittle index based Q-learning for restless bandits with average reward
Venue: arXiv cs.LG 2021
Year: 2021

A novel reinforcement learning algorithm is introduced for multiarmed restless bandits with average reward, using the paradigms of Q-learning and Whittle index. Specifically, we leverage the structure of the Whittle index policy to reduce the search space of Q-learning, resulting in major computational gains. Rigorous convergence analysis is provided, supported by numerical experiments. The numerical experiments show excellent empirical performance of the proposed scheme.
Learning Deformable Image Registration from Optimization: Perspective, Modules, Bilevel Training and Beyond
Venue: arXiv cs.CV 2021
Year: 2021

Conventional deformable registration methods aim at solving an optimization model carefully designed on image pairs and their computational costs are exceptionally high. In contrast, recent deep learning based approaches can provide fast deformation estimation. These heuristic network architectures are fully data-driven and thus lack explicit geometric constraints, e.g., topology-preserving, which are indispensable to generate plausible deformations. We design a new deep learning based framework to optimize a diffeomorphic model via multi-scale propagation in order to integrate advantages and avoid limitations of these two categories of approaches. Specifically, we introduce a generic optimization model to formulate diffeomorphic registration and develop a series of learnable architectures to obtain propagative updating in the coarse-to-fine feature space. Moreover, we propose a novel bilevel self-tuned training strategy, allowing efficient search of task-specific hyper-parameters. This training strategy increases the flexibility to various types of data while reduces computational and human burdens. We conduct two groups of image registration experiments on 3D volume datasets including image-to-atlas registration on brain MRI data and image-to-image registration on liver CT data. Extensive results demonstrate the state-of-the-art performance of the proposed method with diffeomorphic guarantee and extreme efficiency. We also apply our framework to challenging multi-modal image registration, and investigate how our registration to support the down-streaming tasks for medical image analysis including multi-modal fusion and image segmentation.