OpenRaiser/Intern-Atlas huggingface dataset:
Log-Concave Polynomials IV: Approximate Exchange, Tight Mixing Times, and Near-Optimal Sampling of Forests
Venue: arXiv cs.DS 2021
Year: 2021

We prove tight mixing time bounds for natural random walks on bases of matroids, determinantal distributions, and more generally distributions associated with log-concave polynomials. For a matroid of rank $k$ on a ground set of $n$ elements, or more generally distributions associated with log-concave polynomials of homogeneous degree $k$ on $n$ variables, we show that the down-up random walk, started from an arbitrary point in the support, mixes in time $O(k\log k)$. Our bound has no dependence on $n$ or the starting point, unlike the previous analyses [ALOV19,CGM19], and is tight up to constant factors. The main new ingredient is a property we call approximate exchange, a generalization of well-studied exchange properties for matroids and valuated matroids, which may be of independent interest. In particular, given function $μ: {[n] \choose k} \to \mathbb{R}_{\geq 0},$ our approximate exchange property implies that a simple local search algorithm gives a $k^{O(k)}$-approximation of $\max_{S} μ(S)$ when $μ$ is generated by a log-concave polynomial, and that greedy gives the same approximation ratio when $μ$ is strongly Rayleigh. As an application, we show how to leverage down-up random walks to approximately sample random forests or random spanning trees in a graph with $n$ edges in time $O(n\log^2 n).$ The best known result for sampling random forest was a FPAUS with high polynomial runtime recently found by \cite{ALOV19, CGM19}. For spanning tree, we improve on the almost-linear time algorithm by [Sch18]. Our analysis works on weighted graphs too, and is the first to achieve nearly-linear running time for these problems.
Resolution Limits for the Noisy Non-Adaptive 20 Questions Problem
Venue: arXiv cs.IT 2021
Year: 2021

We establish fundamental limits on estimation accuracy for the noisy 20 questions problem with measurement-dependent noise and introduce optimal non-adaptive procedures that achieve these limits. The minimal achievable resolution is defined as the absolute difference between the estimated and the true locations of a target over a unit cube, given a finite number of queries constrained by the excess-resolution probability. Inspired by the relationship between the 20 questions problem and the channel coding problem, we derive non-asymptotic bounds on the minimal achievable resolution to estimate the target location. Furthermore, applying the Berry--Esseen theorem to our non-asymptotic bounds, we obtain a second-order asymptotic approximation to the achievable resolution of optimal non-adaptive query procedures with a finite number of queries subject to the excess-resolution probability constraint. We specialize our second-order results to measurement-dependent versions of several channel models including the binary symmetric, the binary erasure and the binary Z- channels. As a complement, we establish a second-order asymptotic achievability bound for adaptive querying and use this to bound the benefit of adaptive querying.
The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability
Venue: arXiv cs.CC 2021
Year: 2021

Satisfiability is considered the canonical NP-complete problem and is used as a starting point for hardness reductions in theory, while in practice heuristic SAT solving algorithms can solve large-scale industrial SAT instances very efficiently. This disparity between theory and practice is believed to be a result of inherent properties of industrial SAT instances that make them tractable. Two characteristic properties seem to be prevalent in the majority of real-world SAT instances, heterogeneous degree distribution and locality. To understand the impact of these two properties on SAT, we study the proof complexity of random k-SAT models that allow to control heterogeneity and locality. Our findings show that heterogeneity alone does not make SAT easy as heterogeneous random k-SAT instances have superpolynomial resolution size. This implies intractability of these instances for modern SAT-solvers. On the other hand, modeling locality with an underlying geometry leads to small unsatisfiable subformulas, which can be found within polynomial time. A key ingredient for the result on geometric random k-SAT can be found in the complexity of higher-order Voronoi diagrams. As an additional technical contribution, we show a linear upper bound on the number of non-empty Voronoi regions, that holds for points with random positions in a very general setting. In particular, it covers arbitrary p-norms, higher dimensions, and weights affecting the area of influence of each point multiplicatively. This is in stark contrast to quadratic lower bounds for the worst case.
HybridQA: A Dataset of Multi-Hop Question Answering over Tabular and Textual Data
Venue: arXiv cs.CL 2021
Year: 2021

Existing question answering datasets focus on dealing with homogeneous information, based either only on text or KB/Table information alone. However, as human knowledge is distributed over heterogeneous forms, using homogeneous information alone might lead to severe coverage problems. To fill in the gap, we present HybridQA https://github.com/wenhuchen/HybridQA, a new large-scale question-answering dataset that requires reasoning on heterogeneous information. Each question is aligned with a Wikipedia table and multiple free-form corpora linked with the entities in the table. The questions are designed to aggregate both tabular information and text information, i.e., lack of either form would render the question unanswerable. We test with three different models: 1) a table-only model. 2) text-only model. 3) a hybrid model that combines heterogeneous information to find the answer. The experimental results show that the EM scores obtained by two baselines are below 20\%, while the hybrid model can achieve an EM over 40\%. This gap suggests the necessity to aggregate heterogeneous information in HybridQA. However, the hybrid model's score is still far behind human performance. Hence, HybridQA can serve as a challenging benchmark to study question answering with heterogeneous information.
Communication Efficient Federated Learning with Energy Awareness over Wireless Networks
Venue: arXiv cs.LG 2021
Year: 2021

In federated learning (FL), reducing the communication overhead is one of the most critical challenges since the parameter server and the mobile devices share the training parameters over wireless links. With such consideration, we adopt the idea of SignSGD in which only the signs of the gradients are exchanged. Moreover, most of the existing works assume Channel State Information (CSI) available at both the mobile devices and the parameter server, and thus the mobile devices can adopt fixed transmission rates dictated by the channel capacity. In this work, only the parameter server side CSI is assumed, and channel capacity with outage is considered. In this case, an essential problem for the mobile devices is to select appropriate local processing and communication parameters (including the transmission rates) to achieve a desired balance between the overall learning performance and their energy consumption. Two optimization problems are formulated and solved, which optimize the learning performance given the energy consumption requirement, and vice versa. Furthermore, considering that the data may be distributed across the mobile devices in a highly uneven fashion in FL, a stochastic sign-based algorithm is proposed. Extensive simulations are performed to demonstrate the effectiveness of the proposed methods.
Cross-lingual Contextualized Topic Models with Zero-shot Learning
Venue: arXiv cs.CL 2021
Year: 2021

Many data sets (e.g., reviews, forums, news, etc.) exist parallelly in multiple languages. They all cover the same content, but the linguistic differences make it impossible to use traditional, bag-of-word-based topic models. Models have to be either single-language or suffer from a huge, but extremely sparse vocabulary. Both issues can be addressed by transfer learning. In this paper, we introduce a zero-shot cross-lingual topic model. Our model learns topics on one language (here, English), and predicts them for unseen documents in different languages (here, Italian, French, German, and Portuguese). We evaluate the quality of the topic predictions for the same document in different languages. Our results show that the transferred topics are coherent and stable across languages, which suggests exciting future research directions.
On Using Stack Overflow Comment-Edit Pairs to recommend code maintenance changes
Venue: arXiv cs.SE 2021
Year: 2021

Code maintenance data sets typically consist of a before and after version of the code that contains the improvement or fix. Such data sets are important for software engineering support tools related to code maintenance, such as program repair, code recommender systems, or Application Programming Interface (API) misuse detection. Most of the current data sets are constructed from mining commit history in version-control systems or issues in issue-tracking systems. In this paper, we investigate whether Stack Overflow can be used as an additional data source. Comments on Stack Overflow provide an effective way for developers to point out problems with existing answers, alternative solutions, or pitfalls. In this paper, we mine comment-edit pairs from Stack Overflow and investigate their potential usefulness. These pairs have the added benefit of having concrete descriptions of why the change is needed as well as potentially having less tangled changes to deal with. We first design a technique to extract related comment-edit pairs and then investigate the nature of these pairs. We find that the majority of comment-edit pairs are not tangled, but only 27% of the studied pairs are potentially useful for the above applications. We categorize the types of mined pairs and find that the highest ratio of useful pairs come from categories Correction, Obsolete, Flaw, and Extension. To demonstrate the effectiveness of our extracted pairs, we submitted 15 pull requests on GitHub, 10 of which have been accepted to widely used repositories such as Apache Beam and nltk. Our work is the first to investigate Stack Overflow comment-edit pairs and opens the door for future work in this direction. Based on our findings and observations, we provide concrete suggestions on how to potentially identify a larger set of useful comment-edit pairs, which can also be facilitated by our shared data.
On the Approximate Nearest Neighbor Queries among Curves under the Fréchet Distance
Venue: arXiv cs.CG 2021
Year: 2021

Approximate near-neighbors search (\textsc{ANNS}) is a long-studied problem in computational geometry. %that has received considerable attention by researchers in the community. In this paper, we revisit the problem and propose the first data structure for curves under the (continuous) Fréchet distance in $\Reals^d$. Given a set $¶$ of $n$ curves of size at most $m$ each in $\Reals^d$, and a real fixed $δ>0$, we aim to preprocess $¶$ into a data structure so that for any given query curve $Q$ of size $k$, we can efficiently report all curves in $¶$ whose Fréchet distances to $Q$ are at most $δ$. In the case that $k$ is given in the preprocessing stage, for any $\eps>0$ we propose a deterministic data structure whose space is $n \cdot O\big(\max\big\{\big(\frac{\sqrt{d}}{\eps}\big)^{kd}, \big(\frac{\D\sqrt{d}}{\eps^2}\big)^{kd}\big\}\big)$ that can answer \textsc{$(1+\eps)δ$-ANNS} queries in $O(kd)$ query time, where $\D$ is the diameter of $¶$. Considering $k$ as part of the query slightly changes the space to $n \cdot O\big(\frac{1}{\eps}\big)^{md} $ with $O(kd)$ query time within an approximation factor of $5+\eps$. We show that our generic data structure for ANNS can give an alternative treatment of the approximate subtrajectory range searching problem studied by de Berg et al. [8]. We also revisit the time-window data structure for spatial density maps in [6]. Given $θ>0$, and $n$ time-stamped points spread over $m$ regions in a map, for any query window $W$, we propose a data structure of size $O(n/\eps^2)$ and construction time $O((n+m)/\eps^2)$ that can approximately return the regions containing at least $θ$ points whose times are within $W$ in $O(1)$ query time.
On the existence and non-existence of improper homomorphisms of oriented and $2$-edge-coloured graphs to reflexive targets
Venue: arXiv cs.DM 2021
Year: 2021

We consider non-trivial homomorphisms to reflexive oriented graphs in which some pair of adjacent vertices have the same image. Using a notion of convexity for oriented graphs, we study those oriented graphs that do not admit such homomorphisms. We fully classify those oriented graphs with tree-width $2$ that do not admit such homomorphisms and show that it is NP-complete to decide if a graph admits an orientation that does not admit such homomorphisms. We prove analogous results for $2$-edge-coloured graphs. We apply our results on oriented graphs to provide a new tool in the study of chromatic number of orientations of planar graphs -- a long-standing open problem.
Energy-Based Imitation Learning
Venue: arXiv cs.LG 2021
Year: 2021

We tackle a common scenario in imitation learning (IL), where agents try to recover the optimal policy from expert demonstrations without further access to the expert or environment reward signals. Except the simple Behavior Cloning (BC) that adopts supervised learning followed by the problem of compounding error, previous solutions like inverse reinforcement learning (IRL) and recent generative adversarial methods involve a bi-level or alternating optimization for updating the reward function and the policy, suffering from high computational cost and training instability. Inspired by recent progress in energy-based model (EBM), in this paper, we propose a simplified IL framework named Energy-Based Imitation Learning (EBIL). Instead of updating the reward and policy iteratively, EBIL breaks out of the traditional IRL paradigm by a simple and flexible two-stage solution: first estimating the expert energy as the surrogate reward function through score matching, then utilizing such a reward for learning the policy by reinforcement learning algorithms. EBIL combines the idea of both EBM and occupancy measure matching, and via theoretic analysis we reveal that EBIL and Max-Entropy IRL (MaxEnt IRL) approaches are two sides of the same coin, and thus EBIL could be an alternative of adversarial IRL methods. Extensive experiments on qualitative and quantitative evaluations indicate that EBIL is able to recover meaningful and interpretative reward signals while achieving effective and comparable performance against existing algorithms on IL benchmarks.
Multi-Scale Thermal to Visible Face Verification via Attribute Guided Synthesis
Venue: arXiv cs.CV 2021
Year: 2021

Thermal-to-visible face verification is a challenging problem due to the large domain discrepancy between the modalities. Existing approaches either attempt to synthesize visible faces from thermal faces or learn domain-invariant robust features from these modalities for cross-modal matching. In this paper, we use attributes extracted from visible images to synthesize attribute-preserved visible images from thermal imagery for cross-modal matching. A pre-trained attribute predictor network is used to extract the attributes from the visible image. Then, a novel multi-scale generator is proposed to synthesize the visible image from the thermal image guided by the extracted attributes. Finally, a pre-trained VGG-Face network is leveraged to extract features from the synthesized image and the input visible image for verification. Extensive experiments evaluated on three datasets (ARL Face Database, Visible and Thermal Paired Face Database, and Tufts Face Database) demonstrate that the proposed method achieves state-of-the-art performance. In particular, it achieves around 2.41\%, 2.85\% and 1.77\% improvements in Equal Error Rate (EER) over the state-of-the-art methods on the ARL Face Database, Visible and Thermal Paired Face Database, and Tufts Face Database, respectively. An extended dataset (ARL Face Dataset volume III) consisting of polarimetric thermal faces of 121 subjects is also introduced in this paper. Furthermore, an ablation study is conducted to demonstrate the effectiveness of different modules in the proposed method.
Tightening Exploration in Upper Confidence Reinforcement Learning
Venue: arXiv cs.LG 2021
Year: 2021

The upper confidence reinforcement learning (UCRL2) algorithm introduced in (Jaksch et al., 2010) is a popular method to perform regret minimization in unknown discrete Markov Decision Processes under the average-reward criterion. Despite its nice and generic theoretical regret guarantees, this algorithm and its variants have remained until now mostly theoretical as numerical experiments in simple environments exhibit long burn-in phases before the learning takes place. In pursuit of practical efficiency, we present UCRL3, following the lines of UCRL2, but with two key modifications: First, it uses state-of-the-art time-uniform concentration inequalities to compute confidence sets on the reward and (component-wise) transition distributions for each state-action pair. Furthermore, to tighten exploration, it uses an adaptive computation of the support of each transition distribution, which in turn enables us to revisit the extended value iteration procedure of UCRL2 to optimize over distributions with reduced support by disregarding low probability transitions, while still ensuring near-optimism. We demonstrate, through numerical experiments in standard environments, that reducing exploration this way yields a substantial numerical improvement compared to UCRL2 and its variants. On the theoretical side, these key modifications enable us to derive a regret bound for UCRL3 improving on UCRL2, that for the first time makes appear notions of local diameter and local effective support, thanks to variance-aware concentration bounds.
A novel embedded min-max approach for feature selection in nonlinear support vector machine classification
Venue: arXiv cs.LG 2021
Year: 2021

In recent years, feature selection has become a challenging problem in several machine learning fields, such as classification problems. Support Vector Machine (SVM) is a well-known technique applied in classification tasks. Various methodologies have been proposed in the literature to select the most relevant features in SVM. Unfortunately, all of them either deal with the feature selection problem in the linear classification setting or propose ad-hoc approaches that are difficult to implement in practice. In contrast, we propose an embedded feature selection method based on a min-max optimization problem, where a trade-off between model complexity and classification accuracy is sought. By leveraging duality theory, we equivalently reformulate the min-max problem and solve it without further ado using off-the-shelf software for nonlinear optimization. The efficiency and usefulness of our approach are tested on several benchmark data sets in terms of accuracy, number of selected features and interpretability.
Forecasting directional movements of stock prices for intraday trading using LSTM and random forests
Venue: arXiv cs.LG 2021
Year: 2021

We employ both random forests and LSTM networks (more precisely CuDNNLSTM) as training methodologies to analyze their effectiveness in forecasting out-of-sample directional movements of constituent stocks of the S&P 500 from January 1993 till December 2018 for intraday trading. We introduce a multi-feature setting consisting not only of the returns with respect to the closing prices, but also with respect to the opening prices and intraday returns. As trading strategy, we use Krauss et al. (2017) and Fischer & Krauss (2018) as benchmark. On each trading day, we buy the 10 stocks with the highest probability and sell short the 10 stocks with the lowest probability to outperform the market in terms of intraday returns -- all with equal monetary weight. Our empirical results show that the multi-feature setting provides a daily return, prior to transaction costs, of 0.64% using LSTM networks, and 0.54% using random forests. Hence we outperform the single-feature setting in Fischer & Krauss (2018) and Krauss et al. (2017) consisting only of the daily returns with respect to the closing prices, having corresponding daily returns of 0.41% and of 0.39% with respect to LSTM and random forests, respectively.
Testing Machine Translation via Referential Transparency
Venue: arXiv cs.CL 2021
Year: 2021

Machine translation software has seen rapid progress in recent years due to the advancement of deep neural networks. People routinely use machine translation software in their daily lives, such as ordering food in a foreign restaurant, receiving medical diagnosis and treatment from foreign doctors, and reading international political news online. However, due to the complexity and intractability of the underlying neural networks, modern machine translation software is still far from robust and can produce poor or incorrect translations; this can lead to misunderstanding, financial loss, threats to personal safety and health, and political conflicts. To address this problem, we introduce referentially transparent inputs (RTIs), a simple, widely applicable methodology for validating machine translation software. A referentially transparent input is a piece of text that should have similar translations when used in different contexts. Our practical implementation, Purity, detects when this property is broken by a translation. To evaluate RTI, we use Purity to test Google Translate and Bing Microsoft Translator with 200 unlabeled sentences, which detected 123 and 142 erroneous translations with high precision (79.3% and 78.3%). The translation errors are diverse, including examples of under-translation, over-translation, word/phrase mistranslation, incorrect modification, and unclear logic.
Taskflow: A Lightweight Parallel and Heterogeneous Task Graph Computing System
Venue: arXiv cs.DC 2021
Year: 2021

Taskflow aims to streamline the building of parallel and heterogeneous applications using a lightweight task graph-based approach. Taskflow introduces an expressive task graph programming model to assist developers in the implementation of parallel and heterogeneous decomposition strategies on a heterogeneous computing platform. Our programming model distinguishes itself as a very general class of task graph parallelism with in-graph control flow to enable end-to-end parallel optimization. To support our model with high performance, we design an efficient system runtime that solves many of the new scheduling challenges arising out of our models and optimizes the performance across latency, energy efficiency, and throughput. We have demonstrated the promising performance of Taskflow in real-world applications. As an example, Taskflow solves a large-scale machine learning workload up to 29% faster, 1.5x less memory, and 1.9x higher throughput than the industrial system, oneTBB, on a machine of 40 CPUs and 4 GPUs. We have opened the source of Taskflow and deployed it to large numbers of users in the open-source community.
Visual Question Answering Using Semantic Information from Image Descriptions
Venue: arXiv cs.CL 2021
Year: 2021

In this work, we propose a deep neural architecture that uses an attention mechanism which utilizes region based image features, the natural language question asked, and semantic knowledge extracted from the regions of an image to produce open-ended answers for questions asked in a visual question answering (VQA) task. The combination of both region based features and region based textual information about the image bolsters a model to more accurately respond to questions and potentially do so with less required training data. We evaluate our proposed architecture on a VQA task against a strong baseline and show that our method achieves excellent results on this task.