OpenRaiser/Intern-Atlas huggingface dataset:
Threshold Treewidth and Hypertree Width
Venue: arXiv cs.DS 2022
Year: 2022

Treewidth and hypertree width have proven to be highly successful structural parameters in the context of the Constraint Satisfaction Problem (CSP). When either of these parameters is bounded by a constant, then CSP becomes solvable in polynomial time. However, here the order of the polynomial in the running time depends on the width, and this is known to be unavoidable; therefore, the problem is not fixed-parameter tractable parameterized by either of these width measures. Here we introduce an enhancement of tree and hypertree width through a novel notion of thresholds, allowing the associated decompositions to take into account information about the computational costs associated with solving the given CSP instance. Aside from introducing these notions, we obtain efficient theoretical as well as empirical algorithms for computing threshold treewidth and hypertree width and show that these parameters give rise to fixed-parameter algorithms for CSP as well as other, more general problems. We complement our theoretical results with experimental evaluations in terms of heuristics as well as exact methods based on SAT/SMT encodings.
Counterfactual Multihop QA: A Cause-Effect Approach for Reducing Disconnected Reasoning
Venue: arXiv cs.AI 2022
Year: 2022

Multi-hop QA requires reasoning over multiple supporting facts to answer the question. However, the existing QA models always rely on shortcuts, e.g., providing the true answer by only one fact, rather than multi-hop reasoning, which is referred as $\textit{disconnected reasoning}$ problem. To alleviate this issue, we propose a novel counterfactual multihop QA, a causal-effect approach that enables to reduce the disconnected reasoning. It builds upon explicitly modeling of causality: 1) the direct causal effects of disconnected reasoning and 2) the causal effect of true multi-hop reasoning from the total causal effect. With the causal graph, a counterfactual inference is proposed to disentangle the disconnected reasoning from the total causal effect, which provides us a new perspective and technology to learn a QA model that exploits the true multi-hop reasoning instead of shortcuts. Extensive experiments have conducted on the benchmark HotpotQA dataset, which demonstrate that the proposed method can achieve notable improvement on reducing disconnected reasoning. For example, our method achieves 5.8% higher points of its Supp$_s$ score on HotpotQA through true multihop reasoning. The code is available at supplementary material.
Performance Evaluation of Query Plan Recommendation with Apache Hadoop and Apache Spark
Venue: arXiv cs.DB 2022
Year: 2022

Access plan recommendation is a query optimization approach that executes new queries using prior created query execution plans (QEPs). The query optimizer divides the query space into clusters in the mentioned method. However, traditional clustering algorithms take a significant amount of execution time for clustering such large datasets. The MapReduce distributed computing model provides efficient solutions for storing and processing vast quantities of data. Apache Spark and Apache Hadoop frameworks are used in the present investigation to cluster different sizes of query datasets in the MapReduce-based access plan recommendation method. The performance evaluation is performed based on execution time. The results of the experiments demonstrated the effectiveness of parallel query clustering in achieving high scalability. Furthermore, Apache Spark achieved better performance than Apache Hadoop, reaching an average speedup of 2x.
On Compressing Sequences for Self-Supervised Speech Models
Venue: arXiv cs.CL 2022
Year: 2022

Compressing self-supervised models has become increasingly necessary, as self-supervised models become larger. While previous approaches have primarily focused on compressing the model size, shortening sequences is also effective in reducing the computational cost. In this work, we study fixed-length and variable-length subsampling along the time axis in self-supervised learning. We explore how individual downstream tasks are sensitive to input frame rates. Subsampling while training self-supervised models not only improves the overall performance on downstream tasks under certain frame rates, but also brings significant speed-up in inference. Variable-length subsampling performs particularly well under low frame rates. In addition, if we have access to phonetic boundaries, we find no degradation in performance for an average frame rate as low as 10 Hz.
Skyplane: Optimizing Transfer Cost and Throughput Using Cloud-Aware Overlays
Venue: arXiv cs.NI 2022
Year: 2022

Cloud applications are increasingly distributing data across multiple regions and cloud providers. Unfortunately, wide-area bulk data transfers are often slow, bottlenecking applications. We demonstrate that it is possible to significantly improve inter-region cloud bulk transfer throughput by adapting network overlays to the cloud setting -- that is, by routing data through indirect paths at the application layer. However, directly applying network overlays in this setting can result in unacceptable increases in cloud egress prices. We present Skyplane, a system for bulk data transfer between cloud object stores that uses cloud-aware network overlays to optimally navigate the trade-off between price and performance. Skyplane's planner uses mixed-integer linear programming to determine the optimal overlay path and resource allocation for data transfer, subject to user-provided constraints on price or performance. Skyplane outperforms public cloud transfer services by up to $4.6\times$ for transfers within one cloud and by up to $5.0\times$ across clouds.
3D GAN Inversion with Pose Optimization
Venue: arXiv cs.CV 2022
Year: 2022

With the recent advances in NeRF-based 3D aware GANs quality, projecting an image into the latent space of these 3D-aware GANs has a natural advantage over 2D GAN inversion: not only does it allow multi-view consistent editing of the projected image, but it also enables 3D reconstruction and novel view synthesis when given only a single image. However, the explicit viewpoint control acts as a main hindrance in the 3D GAN inversion process, as both camera pose and latent code have to be optimized simultaneously to reconstruct the given image. Most works that explore the latent space of the 3D-aware GANs rely on ground-truth camera viewpoint or deformable 3D model, thus limiting their applicability. In this work, we introduce a generalizable 3D GAN inversion method that infers camera viewpoint and latent code simultaneously to enable multi-view consistent semantic image editing. The key to our approach is to leverage pre-trained estimators for better initialization and utilize the pixel-wise depth calculated from NeRF parameters to better reconstruct the given image. We conduct extensive experiments on image reconstruction and editing both quantitatively and qualitatively, and further compare our results with 2D GAN-based editing to demonstrate the advantages of utilizing the latent space of 3D GANs. Additional results and visualizations are available at https://3dgan-inversion.github.io .
Sample Efficient Dynamics Learning for Symmetrical Legged Robots:Leveraging Physics Invariance and Geometric Symmetries
Venue: arXiv cs.RO 2022
Year: 2022

Model generalization of the underlying dynamics is critical for achieving data efficiency when learning for robot control. This paper proposes a novel approach for learning dynamics leveraging the symmetry in the underlying robotic system, which allows for robust extrapolation from fewer samples. Existing frameworks that represent all data in vector space fail to consider the structured information of the robot, such as leg symmetry, rotational symmetry, and physics invariance. As a result, these schemes require vast amounts of training data to learn the system's redundant elements because they are learned independently. Instead, we propose considering the geometric prior by representing the system in symmetrical object groups and designing neural network architecture to assess invariance and equivariance between the objects. Finally, we demonstrate the effectiveness of our approach by comparing the generalization to unseen data of the proposed model and the existing models. We also implement a controller of a climbing robot based on learned inverse dynamics models. The results show that our method generates accurate control inputs that help the robot reach the desired state while requiring less training data than existing methods.
Task Grouping for Multilingual Text Recognition
Venue: arXiv cs.CV 2022
Year: 2022

Most existing OCR methods focus on alphanumeric characters due to the popularity of English and numbers, as well as their corresponding datasets. On extending the characters to more languages, recent methods have shown that training different scripts with different recognition heads can greatly improve the end-to-end recognition accuracy compared to combining characters from all languages in the same recognition head. However, we postulate that similarities between some languages could allow sharing of model parameters and benefit from joint training. Determining language groupings, however, is not immediately obvious. To this end, we propose an automatic method for multilingual text recognition with a task grouping and assignment module using Gumbel-Softmax, introducing a task grouping loss and weighted recognition loss to allow for simultaneous training of the models and grouping modules. Experiments on MLT19 lend evidence to our hypothesis that there is a middle ground between combining every task together and separating every task that achieves a better configuration of task grouping/separation.
Smart Headset, Computer Vision and Machine Learning for Efficient Prawn Farm Management
Venue: arXiv cs.CV 2022
Year: 2022

Understanding the growth and distribution of the prawns is critical for optimising the feed and harvest strategies. An inadequate understanding of prawn growth can lead to reduced financial gain, for example, crops are harvested too early. The key to maintaining a good understanding of prawn growth is frequent sampling. However, the most commonly adopted sampling practice, the cast net approach, is unable to sample the prawns at a high frequency as it is expensive and laborious. An alternative approach is to sample prawns from feed trays that farm workers inspect each day. This will allow growth data collection at a high frequency (each day). But measuring prawns manually each day is a laborious task. In this article, we propose a new approach that utilises smart glasses, depth camera, computer vision and machine learning to detect prawn distribution and growth from feed trays. A smart headset was built to allow farmers to collect prawn data while performing daily feed tray checks. A computer vision + machine learning pipeline was developed and demonstrated to detect the growth trends of prawns in 4 prawn ponds over a growing season.
Upper bounds on the Rate of Uniformly-Random Codes for the Deletion Channel
Venue: arXiv cs.IT 2022
Year: 2022

We consider the maximum coding rate achievable by uniformly-random codes for the deletion channel. We prove an upper bound that's within 0.1 of the best known lower bounds for all values of the deletion probability $d,$ and much closer for small and large $d.$ We give simulation results which suggest that our upper bound is within 0.05 of the exact value for all $d$, and within $0.01$ for $d>0.75$. Despite our upper bounds, based on simulations, we conjecture that a positive rate is achievable with uniformly-random codes for all deletion probabilities less than 1. Our results imply impossibility results for the (equivalent) problem of compression of i.i.d. sources correlated via the deletion channel, a relevant model for DNA storage.
Distributed Computation for the Non-metric Data Placement Problem using Glauber Dynamics and Auctions
Venue: arXiv cs.GT 2022
Year: 2022

We consider the non-metric data placement problem and develop distributed algorithms for computing or approximating its optimal integral solution. We first show that the non-metric data placement problem is inapproximable up to a logarithmic factor. We then provide a game-theoretic decomposition of the objective function and show that natural Glauber dynamics in which players update their resources with probability proportional to the utility they receive from caching those resources will converge to an optimal global solution for a sufficiently large noise parameter. In particular, we establish the polynomial mixing time of the Glauber dynamics for a certain range of noise parameters. Finally, we provide another auction-based distributed algorithm, which allows us to approximate the optimal global solution with a performance guarantee that depends on the ratio of the revenue vs. social welfare obtained from the underlying auction. Our results provide the first distributed computation algorithms for the non-metric data placement problem.
Polycentric Clustering and Structural Regularization for Source-free Unsupervised Domain Adaptation
Venue: arXiv cs.CV 2022
Year: 2022

Source-Free Domain Adaptation (SFDA) aims to solve the domain adaptation problem by transferring the knowledge learned from a pre-trained source model to an unseen target domain. Most existing methods assign pseudo-labels to the target data by generating feature prototypes. However, due to the discrepancy in the data distribution between the source domain and the target domain and category imbalance in the target domain, there are severe class biases in the generated feature prototypes and noisy pseudo-labels. Besides, the data structure of the target domain is often ignored, which is crucial for clustering. In this paper, a novel framework named PCSR is proposed to tackle SFDA via a novel intra-class Polycentric Clustering and Structural Regularization strategy. Firstly, an inter-class balanced sampling strategy is proposed to generate representative feature prototypes for each class. Furthermore, k-means clustering is introduced to generate multiple clustering centers for each class in the target domain to obtain robust pseudo-labels. Finally, to enhance the model's generalization, structural regularization is introduced for the target domain. Extensive experiments on three UDA benchmark datasets show that our method performs better or similarly against the other state of the art methods, demonstrating our approach's superiority for visual domain adaptation problems.
Cargo Ecosystem Dependency-Vulnerability Knowledge Graph Construction and Vulnerability Propagation Study
Venue: arXiv cs.CR 2022
Year: 2022

Currently, little is known about the structure of the Cargo ecosystem and the potential for vulnerability propagation. Many empirical studies generalize third-party dependency governance strategies from a single software ecosystem to other ecosystems but ignore the differences in the technical structures of different software ecosystems, making it difficult to directly generalize security governance strategies from other ecosystems to the Cargo ecosystem. To fill the gap in this area, this paper constructs a knowledge graph of dependency vulnerabilities for the Cargo ecosystem using techniques related to knowledge graphs to address this challenge. This paper is the first large-scale empirical study in a related research area to address vulnerability propagation in the Cargo ecosystem. This paper proposes a dependency-vulnerability knowledge graph parsing algorithm to determine the vulnerability propagation path and propagation range and empirically studies the characteristics of vulnerabilities in the Cargo ecosystem, the propagation range, and the factors that cause vulnerability propagation. Our research has found that the Cargo ecosystem's security vulnerabilities are primarily memory-related. 18% of the libraries affected by the vulnerability is still affected by the vulnerability in the latest version of the library. The number of versions affected by the propagation of the vulnerabilities is 19.78% in the entire Cargo ecosystem. This paper looks at the characteristics and propagation factors triggering vulnerabilities in the Cargo ecosystem. It provides some practical resolution strategies for administrators of the Cargo community, developers who use Cargo to manage third-party libraries, and library owners. This paper provides new ideas for improving the overall security of the Cargo ecosystem.
Let's Talk Through Physics! Covert Cyber-Physical Data Exfiltration on Air-Gapped Edge Devices
Venue: arXiv cs.CR 2022
Year: 2022

Although organizations are continuously making concerted efforts to harden their systems against network attacks by air-gapping critical systems, attackers continuously adapt and uncover covert channels to exfiltrate data from air-gapped systems. For instance, attackers have demonstrated the feasibility of exfiltrating data from a computer sitting in a Faraday cage by exfiltrating data using magnetic fields. Although a large body of work has recently emerged highlighting various physical covert channels, these attacks have mostly targeted open-loop cyber-physical systems where the covert channels exist on physical channels that are not being monitored by the victim. Network architectures such as fog computing push sensitive data to cyber-physical edge devices--whose physical side channels are typically monitored via state estimation. In this paper, we formalize covert data exfiltration that uses existing cyber-physical models and infrastructure of individual devices to exfiltrate data in a stealthy manner, i.e., we propose a method to circumvent cyber-physical state estimation intrusion detection techniques while exfiltrating sensitive data from the network. We propose a generalized model for encoding and decoding sensitive data within cyber-physical control loops. We evaluate our approach on a distributed IoT network that includes computation nodes residing on physical drones as well as on an industrial control system for the control of a robotic arm. Unlike prior works, we formalize the constraints of covert cyber-physical channel exfiltration in the presence of a defender performing state estimation.
A Reinforcement Learning Approach to Estimating Long-term Treatment Effects
Venue: arXiv cs.LG 2022
Year: 2022

Randomized experiments (a.k.a. A/B tests) are a powerful tool for estimating treatment effects, to inform decisions making in business, healthcare and other applications. In many problems, the treatment has a lasting effect that evolves over time. A limitation with randomized experiments is that they do not easily extend to measure long-term effects, since running long experiments is time-consuming and expensive. In this paper, we take a reinforcement learning (RL) approach that estimates the average reward in a Markov process. Motivated by real-world scenarios where the observed state transition is nonstationary, we develop a new algorithm for a class of nonstationary problems, and demonstrate promising results in two synthetic datasets and one online store dataset.
Legal Case Document Summarization: Extractive and Abstractive Methods and their Evaluation
Venue: arXiv cs.CL 2022
Year: 2022

Summarization of legal case judgement documents is a challenging problem in Legal NLP. However, not much analyses exist on how different families of summarization models (e.g., extractive vs. abstractive) perform when applied to legal case documents. This question is particularly important since many recent transformer-based abstractive summarization models have restrictions on the number of input tokens, and legal documents are known to be very long. Also, it is an open question on how best to evaluate legal case document summarization systems. In this paper, we carry out extensive experiments with several extractive and abstractive summarization methods (both supervised and unsupervised) over three legal summarization datasets that we have developed. Our analyses, that includes evaluation by law practitioners, lead to several interesting insights on legal summarization in specific and long document summarization in general.
Transformer-Based Speech Synthesizer Attribution in an Open Set Scenario
Venue: arXiv cs.SD 2022
Year: 2022

Speech synthesis methods can create realistic-sounding speech, which may be used for fraud, spoofing, and misinformation campaigns. Forensic methods that detect synthesized speech are important for protection against such attacks. Forensic attribution methods provide even more information about the nature of synthesized speech signals because they identify the specific speech synthesis method (i.e., speech synthesizer) used to create a speech signal. Due to the increasing number of realistic-sounding speech synthesizers, we propose a speech attribution method that generalizes to new synthesizers not seen during training. To do so, we investigate speech synthesizer attribution in both a closed set scenario and an open set scenario. In other words, we consider some speech synthesizers to be "known" synthesizers (i.e., part of the closed set) and others to be "unknown" synthesizers (i.e., part of the open set). We represent speech signals as spectrograms and train our proposed method, known as compact attribution transformer (CAT), on the closed set for multi-class classification. Then, we extend our analysis to the open set to attribute synthesized speech signals to both known and unknown synthesizers. We utilize a t-distributed stochastic neighbor embedding (tSNE) on the latent space of the trained CAT to differentiate between each unknown synthesizer. Additionally, we explore poly-1 loss formulations to improve attribution results. Our proposed approach successfully attributes synthesized speech signals to their respective speech synthesizers in both closed and open set scenarios.
A Survey of Parameters Associated with the Quality of Benchmarks in NLP
Venue: arXiv cs.CL 2022
Year: 2022

Several benchmarks have been built with heavy investment in resources to track our progress in NLP. Thousands of papers published in response to those benchmarks have competed to top leaderboards, with models often surpassing human performance. However, recent studies have shown that models triumph over several popular benchmarks just by overfitting on spurious biases, without truly learning the desired task. Despite this finding, benchmarking, while trying to tackle bias, still relies on workarounds, which do not fully utilize the resources invested in benchmark creation, due to the discarding of low quality data, and cover limited sets of bias. A potential solution to these issues -- a metric quantifying quality -- remains underexplored. Inspired by successful quality indices in several domains such as power, food, and water, we take the first step towards a metric by identifying certain language properties that can represent various possible interactions leading to biases in a benchmark. We look for bias related parameters which can potentially help pave our way towards the metric. We survey existing works and identify parameters capturing various properties of bias, their origins, types and impact on performance, generalization, and robustness. Our analysis spans over datasets and a hierarchy of tasks ranging from NLI to Summarization, ensuring that our parameters are generic and are not overfitted towards a specific task or dataset. We also develop certain parameters in this process.