OpenRaiser/Intern-Atlas huggingface dataset:
Faster Deterministic Modular Subset Sum
Venue: arXiv cs.DS 2021
Year: 2021

We consider the Modular Subset Sum problem: given a multiset $X$ of integers from $\mathbb{Z}_m$ and a target integer $t$, decide if there exists a subset of $X$ with a sum equal to $t \pmod{m}$. Recent independent works by Cardinal and Iacono (SOSA'21), and Axiotis et al. (SOSA'21) provided simple and near-linear algorithms for this problem. Cardinal and Iacono gave a randomized algorithm that runs in $O(m \log m)$ time, while Axiotis et al. gave a deterministic algorithm that runs in $O(m \text{ polylog } m)$ time. Both results work by reduction to a text problem, which is solved using a dynamic strings data structure. In this work, we develop a simple data structure, designed specifically to handle the text problem that arises in the algorithms for Modular Subset Sum. Our data structure, which we call the shift-tree, is a simple variant of a segment tree. We provide both a hashing-based and a deterministic variant of the shift-trees. We then apply our data structure to the Modular Subset Sum problem and obtain two algorithms. The first algorithm is Monte-Carlo randomized and matches the $O(m \log m)$ runtime of the Las-Vegas algorithm by Cardinal and Iacono. The second algorithm is fully deterministic and runs in $O(m \log m \cdot α(m))$ time, where $α$ is the inverse Ackermann function.
Coded sparse matrix computation schemes that leverage partial stragglers
Venue: arXiv cs.IT 2021
Year: 2021

Distributed matrix computations over large clusters can suffer from the problem of slow or failed worker nodes (called stragglers) which can dominate the overall job execution time. Coded computation utilizes concepts from erasure coding to mitigate the effect of stragglers by running 'coded' copies of tasks comprising a job; stragglers are typically treated as erasures. While this is useful, there are issues with applying, e.g., MDS codes in a straightforward manner. Several practical matrix computation scenarios involve sparse matrices. MDS codes typically require dense linear combinations of submatrices of the original matrices which destroy their inherent sparsity. This is problematic as it results in significantly higher worker computation times. Moreover, treating slow nodes as erasures ignores the potentially useful partial computations performed by them. Furthermore, some MDS techniques also suffer from significant numerical stability issues. In this work we present schemes that allow us to leverage partial computation by stragglers while imposing constraints on the level of coding that is required in generating the encoded submatrices. This significantly reduces the worker computation time as compared to previous approaches and results in improved numerical stability in the decoding process. Exhaustive numerical experiments on Amazon Web Services (AWS) clusters support our findings.
ParsiNLU: A Suite of Language Understanding Challenges for Persian
Venue: arXiv cs.CL 2021
Year: 2021

Despite the progress made in recent years in addressing natural language understanding (NLU) challenges, the majority of this progress remains to be concentrated on resource-rich languages like English. This work focuses on Persian language, one of the widely spoken languages in the world, and yet there are few NLU datasets available for this rich language. The availability of high-quality evaluation datasets is a necessity for reliable assessment of the progress on different NLU tasks and domains. We introduce ParsiNLU, the first benchmark in Persian language that includes a range of high-level tasks -- Reading Comprehension, Textual Entailment, etc. These datasets are collected in a multitude of ways, often involving manual annotations by native speakers. This results in over 14.5$k$ new instances across 6 distinct NLU tasks. Besides, we present the first results on state-of-the-art monolingual and multi-lingual pre-trained language-models on this benchmark and compare them with human performance, which provides valuable insights into our ability to tackle natural language understanding challenges in Persian. We hope ParsiNLU fosters further research and advances in Persian language understanding.
A Topic Coverage Approach to Evaluation of Topic Models
Venue: arXiv cs.IR 2021
Year: 2021

Topic models are widely used unsupervised models capable of learning topics - weighted lists of words and documents - from large collections of text documents. When topic models are used for discovery of topics in text collections, a question that arises naturally is how well the model-induced topics correspond to topics of interest to the analyst. In this paper we revisit and extend a so far neglected approach to topic model evaluation based on measuring topic coverage - computationally matching model topics with a set of reference topics that models are expected to uncover. The approach is well suited for analyzing models' performance in topic discovery and for large-scale analysis of both topic models and measures of model quality. We propose new measures of coverage and evaluate, in a series of experiments, different types of topic models on two distinct text domains for which interest for topic discovery exists. The experiments include evaluation of model quality, analysis of coverage of distinct topic categories, and the analysis of the relationship between coverage and other methods of topic model evaluation. The paper contributes a new supervised measure of coverage, and the first unsupervised measure of coverage. The supervised measure achieves topic matching accuracy close to human agreement. The unsupervised measure correlates highly with the supervised one (Spearman's $ρ\geq 0.95$). Other contributions include insights into both topic models and different methods of model evaluation, and the datasets and code for facilitating future research on topic coverage.
Dual Control for Exploitation and Exploration (DCEE) in Autonomous Search
Venue: arXiv cs.RO 2021
Year: 2021

This paper proposes an optimal autonomous search framework, namely Dual Control for Exploration and Exploitation (DCEE), for a target at unknown location in an unknown environment. Source localisation is to find sources of atmospheric hazardous material release in a partially unknown environment. This paper proposes a control theoretic approach to this autonomous search problem. To cope with an unknown target location, at each step, the target location is estimated by Bayesian inference. Then a control action is taken to minimise the error between future robot position and the hypothesised future estimation of the target location. The latter is generated by hypothesised measurements at the corresponding future robot positions (due to the control action) with the current estimation of the target location as a prior. It shows that this approach can take into account both the error between the next robot position and the estimate of the target location, and the uncertainty of the estimate. This approach is further extended to the case with not only an unknown source location, but also an unknown local environment (e.g. wind speed and direction). Different from current information theoretic approaches, this new control theoretic approach achieves the optimal trade-off between exploitation and exploration in a unknown environment with an unknown target by driving the robot moving towards estimated target location while reducing its estimation uncertainty. This scheme is implemented using particle filtering on a mobile robot. Simulation and experimental studies demonstrate promising performance of the proposed approach. The relationships between the proposed approach, informative path planning, dual control, and classic model predictive control are discussed and compared.
Relighting Images in the Wild with a Self-Supervised Siamese Auto-Encoder
Venue: arXiv cs.CV 2021
Year: 2021

We propose a self-supervised method for image relighting of single view images in the wild. The method is based on an auto-encoder which deconstructs an image into two separate encodings, relating to the scene illumination and content, respectively. In order to disentangle this embedding information without supervision, we exploit the assumption that some augmentation operations do not affect the image content and only affect the direction of the light. A novel loss function, called spherical harmonic loss, is introduced that forces the illumination embedding to convert to a spherical harmonic vector. We train our model on large-scale datasets such as Youtube 8M and CelebA. Our experiments show that our method can correctly estimate scene illumination and realistically re-light input images, without any supervision or a prior shape model. Compared to supervised methods, our approach has similar performance and avoids common lighting artifacts.
Automatic Test Suite Generation for Key-Points Detection DNNs using Many-Objective Search (Experience Paper)
Venue: arXiv cs.CV 2021
Year: 2021

Automatically detecting the positions of key-points (e.g., facial key-points or finger key-points) in an image is an essential problem in many applications, such as driver's gaze detection and drowsiness detection in automated driving systems. With the recent advances of Deep Neural Networks (DNNs), Key-Points detection DNNs (KP-DNNs) have been increasingly employed for that purpose. Nevertheless, KP-DNN testing and validation have remained a challenging problem because KP-DNNs predict many independent key-points at the same time -- where each individual key-point may be critical in the targeted application -- and images can vary a great deal according to many factors. In this paper, we present an approach to automatically generate test data for KP-DNNs using many-objective search. In our experiments, focused on facial key-points detection DNNs developed for an industrial automotive application, we show that our approach can generate test suites to severely mispredict, on average, more than 93% of all key-points. In comparison, random search-based test data generation can only severely mispredict 41% of them. Many of these mispredictions, however, are not avoidable and should not therefore be considered failures. We also empirically compare state-of-the-art, many-objective search algorithms and their variants, tailored for test suite generation. Furthermore, we investigate and demonstrate how to learn specific conditions, based on image characteristics (e.g., head posture and skin color), that lead to severe mispredictions. Such conditions serve as a basis for risk analysis or DNN retraining.
Hiding in the Particles: When Return-Oriented Programming Meets Program Obfuscation
Venue: arXiv cs.CR 2021
Year: 2021

Largely known for attack scenarios, code reuse techniques at a closer look reveal properties that are appealing also for program obfuscation. We explore the popular return-oriented programming paradigm under this light, transforming program functions into ROP chains that coexist seamlessly with the surrounding software stack. We show how to build chains that can withstand popular static and dynamic deobfuscation approaches, evaluating the robustness and overheads of the design over common programs. The results suggest a significant amount of computational resources would be required to carry a deobfuscation attack for secret finding and code coverage goals.
PoP-Net: Pose over Parts Network for Multi-Person 3D Pose Estimation from a Depth Image
Venue: arXiv cs.CV 2021
Year: 2021

In this paper, a real-time method called PoP-Net is proposed to predict multi-person 3D poses from a depth image. PoP-Net learns to predict bottom-up part representations and top-down global poses in a single shot. Specifically, a new part-level representation, called Truncated Part Displacement Field (TPDF), is introduced which enables an explicit fusion process to unify the advantages of bottom-up part detection and global pose detection. Meanwhile, an effective mode selection scheme is introduced to automatically resolve the conflicting cases between global pose and part detections. Finally, due to the lack of high-quality depth datasets for developing multi-person 3D pose estimation, we introduce Multi-Person 3D Human Pose Dataset (MP-3DHP) as a new benchmark. MP-3DHP is designed to enable effective multi-person and background data augmentation in model training, and to evaluate 3D human pose estimators under uncontrolled multi-person scenarios. We show that PoP-Net achieves the state-of-the-art results both on MP-3DHP and on the widely used ITOP dataset, and has significant advantages in efficiency for multi-person processing. To demonstrate one of the applications of our algorithm pipeline, we also show results of virtual avatars driven by our calculated 3D joint positions. MP-3DHP Dataset and the evaluation code have been made available at: https://github.com/oppo-us-research/PoP-Net.
Age-Optimal Power Allocation in Industrial IoT: A Risk-Sensitive Federated Learning Approach
Venue: arXiv cs.NI 2021
Year: 2021

This work studies a real-time environment monitoring scenario in the industrial Internet of things, where wireless sensors proactively collect environmental data and transmit it to the controller. We adopt the notion of risk-sensitivity in financial mathematics as the objective to jointly minimize the mean, variance, and other higher-order statistics of the network energy consumption subject to the constraints on the age of information (AoI) threshold violation probability and the AoI exceedances over a pre-defined threshold. We characterize the extreme AoI staleness using results in extreme value theory and propose a distributed power allocation approach by weaving in together principles of Lyapunov optimization and federated learning (FL). Simulation results demonstrate that the proposed FL-based distributed solution is on par with the centralized baseline while consuming 28.50% less system energy and outperforms the other baselines.
Transmit Power Pool Design for Grant-Free NOMA-IoT Networks via Deep Reinforcement Learning
Venue: arXiv cs.IT 2021
Year: 2021

Grant-free non-orthogonal multiple access (GF-NOMA) is a potential multiple access framework for short-packet internet-of-things (IoT) networks to enhance connectivity. However, the resource allocation problem in GF-NOMA is challenging due to the absence of closed-loop power control. We design a prototype of transmit power pool (PP) to provide open-loop power control. IoT users acquire their transmit power in advance from this prototype PP solely according to their communication distances. Firstly, a multi-agent deep Q-network (DQN) aided GF-NOMA algorithm is proposed to determine the optimal transmit power levels for the prototype PP. More specifically, each IoT user acts as an agent and learns a policy by interacting with the wireless environment that guides them to select optimal actions. Secondly, to prevent the Q-learning model overestimation problem, double DQN based GF-NOMA algorithm is proposed. Numerical results confirm that the double DQN based algorithm finds out the optimal transmit power levels that form the PP. Comparing with the conventional online learning approach, the proposed algorithm with the prototype PP converges faster under changing environments due to limiting the action space based on previous learning. The considered GF-NOMA system outperforms the networks with fixed transmission power, namely all the users have the same transmit power and the traditional GF with orthogonal multiple access techniques, in terms of throughput.
DeepSweep: An Evaluation Framework for Mitigating DNN Backdoor Attacks using Data Augmentation
Venue: arXiv cs.CR 2021
Year: 2021

Public resources and services (e.g., datasets, training platforms, pre-trained models) have been widely adopted to ease the development of Deep Learning-based applications. However, if the third-party providers are untrusted, they can inject poisoned samples into the datasets or embed backdoors in those models. Such an integrity breach can cause severe consequences, especially in safety- and security-critical applications. Various backdoor attack techniques have been proposed for higher effectiveness and stealthiness. Unfortunately, existing defense solutions are not practical to thwart those attacks in a comprehensive way. In this paper, we investigate the effectiveness of data augmentation techniques in mitigating backdoor attacks and enhancing DL models' robustness. An evaluation framework is introduced to achieve this goal. Specifically, we consider a unified defense solution, which (1) adopts a data augmentation policy to fine-tune the infected model and eliminate the effects of the embedded backdoor; (2) uses another augmentation policy to preprocess input samples and invalidate the triggers during inference. We propose a systematic approach to discover the optimal policies for defending against different backdoor attacks by comprehensively evaluating 71 state-of-the-art data augmentation functions. Extensive experiments show that our identified policy can effectively mitigate eight different kinds of backdoor attacks and outperform five existing defense methods. We envision this framework can be a good benchmark tool to advance future DNN backdoor studies.
Demystifying Deep Neural Networks Through Interpretation: A Survey
Venue: arXiv cs.LG 2021
Year: 2021

Modern deep learning algorithms tend to optimize an objective metric, such as minimize a cross entropy loss on a training dataset, to be able to learn. The problem is that the single metric is an incomplete description of the real world tasks. The single metric cannot explain why the algorithm learn. When an erroneous happens, the lack of interpretability causes a hardness of understanding and fixing the error. Recently, there are works done to tackle the problem of interpretability to provide insights into neural networks behavior and thought process. The works are important to identify potential bias and to ensure algorithm fairness as well as expected performance.
Uniform Capacitated Facility Location Problems with Penalties/Outliers
Venue: arXiv cs.DS 2021
Year: 2021

In this paper, we present a framework to design approximation algorithms for capacitated facility location problems with penalties/outliers using LP-rounding. Primal-dual technique, which has been particularly successful in dealing with outliers and penalties, has not been very successful in dealing with capacities. On the other hand, no primal-dual solution has been able to break the hardness of capacitated facility location problem(CFLP). LP-rounding techniques had also not been very successful in dealing with capacities until a recent work by Grover et al. \cite{GroverGKP18}. Their constant factor approximation violating the capacities by a small factor ($1 + ε$) is promising while dealing with capacities.Though LP-rounding has not been very promising while dealing with penalties and outliers, we successfully apply it to deal with them along with capacities. That is, our results are obtained by rounding the solution to the natural LP once again exhibiting the power of LP-rounding technique. Solutions obtained by LP-rounding are easy to integrate with other LP-based algorithms.In this paper, we apply our framework to obtain first constant factor approximations for capacitated facility location problem with outlier (CFLPO) and capacitated $k$-facility location problem with penalty(C$k$FLPP) for hard uniform capacities using LP-rounding. Our solutions incur slight violations in capacities, ($1 + ε$) for the problems without cardinality($k$) constraint and ($2 + ε$) for the problems with the cardinality constraint. For the outlier variant, we also incur a small loss ($1 + ε$) in outliers. Due to the hardness of the underlying problems, the violations are inevitable. Thus we achieve the best possible by rounding the solution of natural LP for these problems. To the best of our knowledge, no results are known for CFLPO and C$k$FLPP.
A survey of sketches in traffic measurement: Design, Optimization, Application and Implementation
Venue: arXiv cs.DS 2021
Year: 2021

Network measurement probes the underlying network to support upper-level decisions such as network management, network update, network maintenance, network defense and beyond. Due to the massive, speedy, unpredictable features of network flows, sketches are widely implemented in measurement nodes to approximately record the frequency or estimate the cardinality of flows. At their cores, sketches usually maintain one or multiple counter array(s), and rely on hash functions to select the counter(s) for each flow. Then the space-efficient sketches from the distributed measurement nodes are aggregated to provide statistics of the undergoing flows. Currently, tremendous redesigns and optimizations have been proposed to improve the sketches for better network measurement performance. However, existing reviews or surveys mainly focus on one particular aspect of measurement tasks. Researchers and engineers in the network measurement community desire an all-in-one survey that covers the entire processing pipeline of sketch-based network measurement. To this end, we present the first comprehensive survey of this area. We first introduce the preparation of flows for measurement, then detail the most recent investigations of design, aggregation, decoding, application and implementation of sketches for network measurement. To summarize the existing efforts, we carry out an in-depth study of the existing literature, covering more than 90 sketch designs and optimization strategies. Furthermore, we conduct a comprehensive analysis and qualitative/quantitative comparison of the sketch designs. Finally,we highlight the open issues for future sketch-based network measurement research.
Phase Retrieval with Holography and Untrained Priors: Tackling the Challenges of Low-Photon Nanoscale Imaging
Venue: arXiv cs.LG 2021
Year: 2021

Phase retrieval is the inverse problem of recovering a signal from magnitude-only Fourier measurements, and underlies numerous imaging modalities, such as Coherent Diffraction Imaging (CDI). A variant of this setup, known as holography, includes a reference object that is placed adjacent to the specimen of interest before measurements are collected. The resulting inverse problem, known as holographic phase retrieval, is well-known to have improved problem conditioning relative to the original. This innovation, i.e. Holographic CDI, becomes crucial at the nanoscale, where imaging specimens such as viruses, proteins, and crystals require low-photon measurements. This data is highly corrupted by Poisson shot noise, and often lacks low-frequency content as well. In this work, we introduce a dataset-free deep learning framework for holographic phase retrieval adapted to these challenges. The key ingredients of our approach are the explicit and flexible incorporation of the physical forward model into an automatic differentiation procedure, the Poisson log-likelihood objective function, and an optional untrained deep image prior. We perform extensive evaluation under realistic conditions. Compared to competing classical methods, our method recovers signal from higher noise levels and is more resilient to suboptimal reference design, as well as to large missing regions of low frequencies in the observations. Finally, we show that these properties carry over to experimental data acquired on optical wavelengths. To the best of our knowledge, this is the first work to consider a dataset-free machine learning approach for holographic phase retrieval.