OpenRaiser/Intern-Atlas huggingface dataset:
Differential Dynamic Programming with Nonlinear Safety Constraints Under System Uncertainties
Venue: arXiv cs.RO 2022
Year: 2022

Safe operation of systems such as robots requires them to plan and execute trajectories subject to safety constraints. When those systems are subject to uncertainties in their dynamics, it is challenging to ensure that the constraints are not violated. In this paper, we propose Safe-CDDP, a safe trajectory optimization and control approach for systems under additive uncertainties and non-linear safety constraints based on constrained differential dynamic programming (DDP). The safety of the robot during its motion is formulated as chance constraints with user-chosen probabilities of constraint satisfaction. The chance constraints are transformed into deterministic ones in DDP formulation by constraint tightening. To avoid over-conservatism during constraint tightening, linear control gains of the feedback policy derived from the constrained DDP are used in the approximation of closed-loop uncertainty propagation in prediction. The proposed algorithm is empirically evaluated on three different robot dynamics with up to 12 degrees of freedom in simulation. The computational feasibility and applicability of the approach are demonstrated with a physical hardware implementation.
Introducing various Semantic Models for Amharic: Experimentation and Evaluation with multiple Tasks and Datasets
Venue: arXiv cs.CL 2022
Year: 2022

The availability of different pre-trained semantic models enabled the quick development of machine learning components for downstream applications. Despite the availability of abundant text data for low resource languages, only a few semantic models are publicly available. Publicly available pre-trained models are usually built as a multilingual version of semantic models that can not fit well for each language due to context variations. In this work, we introduce different semantic models for Amharic. After we experiment with the existing pre-trained semantic models, we trained and fine-tuned nine new different models using a monolingual text corpus. The models are build using word2Vec embeddings, distributional thesaurus (DT), contextual embeddings, and DT embeddings obtained via network embedding algorithms. Moreover, we employ these models for different NLP tasks and investigate their impact. We find that newly trained models perform better than pre-trained multilingual models. Furthermore, models based on contextual embeddings from RoBERTA perform better than the word2Vec models.
Adversarial Examples in Constrained Domains
Venue: arXiv cs.CR 2022
Year: 2022

Machine learning algorithms have been shown to be vulnerable to adversarial manipulation through systematic modification of inputs (e.g., adversarial examples) in domains such as image recognition. Under the default threat model, the adversary exploits the unconstrained nature of images; each feature (pixel) is fully under control of the adversary. However, it is not clear how these attacks translate to constrained domains that limit which and how features can be modified by the adversary (e.g., network intrusion detection). In this paper, we explore whether constrained domains are less vulnerable than unconstrained domains to adversarial example generation algorithms. We create an algorithm for generating adversarial sketches: targeted universal perturbation vectors which encode feature saliency within the envelope of domain constraints. To assess how these algorithms perform, we evaluate them in constrained (e.g., network intrusion detection) and unconstrained (e.g., image recognition) domains. The results demonstrate that our approaches generate misclassification rates in constrained domains that were comparable to those of unconstrained domains (greater than 95%). Our investigation shows that the narrow attack surface exposed by constrained domains is still sufficiently large to craft successful adversarial examples; and thus, constraints do not appear to make a domain robust. Indeed, with as little as five randomly selected features, one can still generate adversarial examples.
BIGPrior: Towards Decoupling Learned Prior Hallucination and Data Fidelity in Image Restoration
Venue: arXiv cs.CV 2022
Year: 2022

Classic image-restoration algorithms use a variety of priors, either implicitly or explicitly. Their priors are hand-designed and their corresponding weights are heuristically assigned. Hence, deep learning methods often produce superior image restoration quality. Deep networks are, however, capable of inducing strong and hardly predictable hallucinations. Networks implicitly learn to be jointly faithful to the observed data while learning an image prior; and the separation of original data and hallucinated data downstream is then not possible. This limits their wide-spread adoption in image restoration. Furthermore, it is often the hallucinated part that is victim to degradation-model overfitting. We present an approach with decoupled network-prior based hallucination and data fidelity terms. We refer to our framework as the Bayesian Integration of a Generative Prior (BIGPrior). Our method is rooted in a Bayesian framework and tightly connected to classic restoration methods. In fact, it can be viewed as a generalization of a large family of classic restoration algorithms. We use network inversion to extract image prior information from a generative network. We show that, on image colorization, inpainting and denoising, our framework consistently improves the inversion results. Our method, though partly reliant on the quality of the generative network inversion, is competitive with state-of-the-art supervised and task-specific restoration methods. It also provides an additional metric that sets forth the degree of prior reliance per pixel relative to data fidelity.
The Complexity of Finding Fair Independent Sets in Cycles
Venue: arXiv cs.CC 2022
Year: 2022

Let $G$ be a cycle graph and let $V_1,\ldots,V_m$ be a partition of its vertex set into $m$ sets. An independent set $S$ of $G$ is said to fairly represent the partition if $|S \cap V_i| \geq \frac{1}{2} \cdot |V_i| -1$ for all $i \in [m]$. It is known that for every cycle and every partition of its vertex set, there exists an independent set that fairly represents the partition (Aharoni et al., A Journey through Discrete Math., 2017). We prove that the problem of finding such an independent set is $\mathsf{PPA}$-complete. As an application, we show that the problem of finding a monochromatic edge in a Schrijver graph, given a succinct representation of a coloring that uses fewer colors than its chromatic number, is $\mathsf{PPA}$-complete as well. The work is motivated by the computational aspects of the `cycle plus triangles' problem and of its extensions.
Generating Large-Scale Trajectories Efficiently using Double Descriptions of Polynomials
Venue: arXiv cs.RO 2022
Year: 2022

For quadrotor trajectory planning, describing a polynomial trajectory through coefficients and end-derivatives both enjoy their own convenience in energy minimization. We name them double descriptions of polynomial trajectories. The transformation between them, causing most of the inefficiency and instability, is formally analyzed in this paper. Leveraging its analytic structure, we design a linear-complexity scheme for both jerk/snap minimization and parameter gradient evaluation, which possesses efficiency, stability, flexibility, and scalability. With the help of our scheme, generating an energy optimal (minimum snap) trajectory only costs 1 $μs$ per piece at the scale up to 1,000,000 pieces. Moreover, generating large-scale energy-time optimal trajectories is also accelerated by an order of magnitude against conventional methods.
Parametric Flatten-T Swish: An Adaptive Non-linear Activation Function For Deep Learning
Venue: arXiv cs.LG 2022
Year: 2022

Activation function is a key component in deep learning that performs non-linear mappings between the inputs and outputs. Rectified Linear Unit (ReLU) has been the most popular activation function across the deep learning community. However, ReLU contains several shortcomings that can result in inefficient training of the deep neural networks, these are: 1) the negative cancellation property of ReLU tends to treat negative inputs as unimportant information for the learning, resulting in a performance degradation; 2) the inherent predefined nature of ReLU is unlikely to promote additional flexibility, expressivity, and robustness to the networks; 3) the mean activation of ReLU is highly positive and leads to bias shift effect in network layers; and 4) the multilinear structure of ReLU restricts the non-linear approximation power of the networks. To tackle these shortcomings, this paper introduced Parametric Flatten-T Swish (PFTS) as an alternative to ReLU. By taking ReLU as a baseline method, the experiments showed that PFTS improved classification accuracy on SVHN dataset by 0.31%, 0.98%, 2.16%, 17.72%, 1.35%, 0.97%, 39.99%, and 71.83% on DNN-3A, DNN-3B, DNN-4, DNN- 5A, DNN-5B, DNN-5C, DNN-6, and DNN-7, respectively. Besides, PFTS also achieved the highest mean rank among the comparison methods. The proposed PFTS manifested higher non-linear approximation power during training and thereby improved the predictive performance of the networks.
Augmented Equivariant Attention Networks for Microscopy Image Reconstruction
Venue: arXiv cs.CV 2022
Year: 2022

It is time-consuming and expensive to take high-quality or high-resolution electron microscopy (EM) and fluorescence microscopy (FM) images. Taking these images could be even invasive to samples and may damage certain subtleties in the samples after long or intense exposures, often necessary for achieving high-quality or high resolution in the first place. Advances in deep learning enable us to perform image-to-image transformation tasks for various types of microscopy image reconstruction, computationally producing high-quality images from the physically acquired low-quality ones. When training image-to-image transformation models on pairs of experimentally acquired microscopy images, prior models suffer from performance loss due to their inability to capture inter-image dependencies and common features shared among images. Existing methods that take advantage of shared features in image classification tasks cannot be properly applied to image reconstruction tasks because they fail to preserve the equivariance property under spatial permutations, something essential in image-to-image transformation. To address these limitations, we propose the augmented equivariant attention networks (AEANets) with better capability to capture inter-image dependencies, while preserving the equivariance property. The proposed AEANets captures inter-image dependencies and shared features via two augmentations on the attention mechanism, which are the shared references and the batch-aware attention during training. We theoretically derive the equivariance property of the proposed augmented attention model and experimentally demonstrate its consistent superiority in both quantitative and visual results over the baseline methods.
Fair Machine Learning Under Partial Compliance
Venue: arXiv cs.CY 2022
Year: 2022

Typically, fair machine learning research focuses on a single decisionmaker and assumes that the underlying population is stationary. However, many of the critical domains motivating this work are characterized by competitive marketplaces with many decisionmakers. Realistically, we might expect only a subset of them to adopt any non-compulsory fairness-conscious policy, a situation that political philosophers call partial compliance. This possibility raises important questions: how does the strategic behavior of decision subjects in partial compliance settings affect the allocation outcomes? If k% of employers were to voluntarily adopt a fairness-promoting intervention, should we expect k% progress (in aggregate) towards the benefits of universal adoption, or will the dynamics of partial compliance wash out the hoped-for benefits? How might adopting a global (versus local) perspective impact the conclusions of an auditor? In this paper, we propose a simple model of an employment market, leveraging simulation as a tool to explore the impact of both interaction effects and incentive effects on outcomes and auditing metrics. Our key findings are that at equilibrium: (1) partial compliance (k% of employers) can result in far less than proportional (k%) progress towards the full compliance outcomes; (2) the gap is more severe when fair employers match global (vs local) statistics; (3) choices of local vs global statistics can paint dramatically different pictures of the performance vis-a-vis fairness desiderata of compliant versus non-compliant employers; and (4) partial compliance to local parity measures can induce extreme segregation.
Intelligent Reflecting Surface (IRS)-Aided Covert Wireless Communications with Delay Constraint
Venue: arXiv cs.IT 2022
Year: 2022

This work examines the performance gain achieved by deploying an intelligent reflecting surface (IRS) in covert communications. To this end, we formulate the joint design of the transmit power and the IRS reflection coefficients by taking into account the communication covertness for the cases with global channel state information (CSI) and without a warden's instantaneous CSI. For the case of global CSI, we first prove that perfect covertness is achievable with the aid of the IRS even for a single-antenna transmitter, which is impossible without an IRS. Then, we develop a penalty successive convex approximation (PSCA) algorithm to tackle the design problem. Considering the high complexity of the PSCA algorithm, we further propose a low-complexity two-stage algorithm, where analytical expressions for the transmit power and the IRS's reflection coefficients are derived. For the case without the warden's instantaneous CSI, we first derive the covertness constraint analytically facilitating the optimal phase shift design. Then, we consider three hardware-related constraints on the IRS's reflection amplitudes and determine their optimal designs together with the optimal transmit power. Our examination shows that significant performance gain can be achieved by deploying an IRS into covert communications.
From Eye-blinks to State Construction: Diagnostic Benchmarks for Online Representation Learning
Venue: arXiv cs.AI 2022
Year: 2022

We present three new diagnostic prediction problems inspired by classical-conditioning experiments to facilitate research in online prediction learning. Experiments in classical conditioning show that animals such as rabbits, pigeons, and dogs can make long temporal associations that enable multi-step prediction. To replicate this remarkable ability, an agent must construct an internal state representation that summarizes its interaction history. Recurrent neural networks can automatically construct state and learn temporal associations. However, the current training methods are prohibitively expensive for online prediction -- continual learning on every time step -- which is the focus of this paper. Our proposed problems test the learning capabilities that animals readily exhibit and highlight the limitations of the current recurrent learning methods. While the proposed problems are nontrivial, they are still amenable to extensive testing and analysis in the small-compute regime, thereby enabling researchers to study issues in isolation, ultimately accelerating progress towards scalable online representation learning methods.
Bridging the Performance Gap between FGSM and PGD Adversarial Training
Venue: arXiv cs.CR 2022
Year: 2022

Deep learning achieves state-of-the-art performance in many tasks but exposes to the underlying vulnerability against adversarial examples. Across existing defense techniques, adversarial training with the projected gradient decent attack (adv.PGD) is considered as one of the most effective ways to achieve moderate adversarial robustness. However, adv.PGD requires too much training time since the projected gradient attack (PGD) takes multiple iterations to generate perturbations. On the other hand, adversarial training with the fast gradient sign method (adv.FGSM) takes much less training time since the fast gradient sign method (FGSM) takes one step to generate perturbations but fails to increase adversarial robustness. In this work, we extend adv.FGSM to make it achieve the adversarial robustness of adv.PGD. We demonstrate that the large curvature along FGSM perturbed direction leads to a large difference in performance of adversarial robustness between adv.FGSM and adv.PGD, and therefore propose combining adv.FGSM with a curvature regularization (adv.FGSMR) in order to bridge the performance gap between adv.FGSM and adv.PGD. The experiments show that adv.FGSMR has higher training efficiency than adv.PGD. In addition, it achieves comparable performance of adversarial robustness on MNIST dataset under white-box attack, and it achieves better performance than adv.PGD under white-box attack and effectively defends the transferable adversarial attack on CIFAR-10 dataset.
Speed-Robust Scheduling -- Sand, Bricks, and Rocks
Venue: arXiv cs.DS 2022
Year: 2022

The speed-robust scheduling problem is a two-stage problem where given $m$ machines, jobs must be grouped into at most $m$ bags while the processing speeds of the given $m$ machines are unknown. After the speeds are revealed, the grouped jobs must be assigned to the machines without being separated. To evaluate the performance of algorithms, we determine upper bounds on the worst-case ratio of the algorithm's makespan and the optimal makespan given full information. We refer to this ratio as the robustness factor. We give an algorithm with a robustness factor $2-1/m$ for the most general setting and improve this to $1.8$ for equal-size jobs. For the special case of infinitesimal jobs, we give an algorithm with an optimal robustness factor equal to $e/(e-1) \approx 1.58$. The particular machine environment in which all machines have either speed $0$ or $1$ was studied before by Stein and Zhong (SODA 2019). For this setting, we provide an algorithm for scheduling infinitesimal jobs with an optimal robustness factor of $(1+\sqrt{2})/2 \approx 1.207$. It lays the foundation for an algorithm matching the lower bound of $4/3$ for equal-size jobs.
Wayback Machine: A tool to capture the evolutionary behaviour of the bug reports and their triage process in open-source software systems
Venue: arXiv cs.SE 2022
Year: 2022

The issue tracking system (ITS) is a rich data source for data-driven decision-making. Different characteristics of bugs, such as severity, priority, and time to fix, provide a clear picture of an ITS. Nevertheless, such information may be misleading. For example, the exact time and the effort spent on a bug might be significantly different from the actual reporting time and the fixing time. Similarly, these values may be subjective, e.g., severity and priority values are assigned based on the intuition of a user or a developer rather than a structured and well-defined procedure. Hence, we explore the evolution of the bug dependency graph together with priority and severity levels to explore the actual triage process. Inspired by the idea of the "Wayback Machine" for the World Wide Web, we aim to reconstruct the historical decisions made in the ITS. Therefore, any bug prioritization or bug triage algorithms/scenarios can be applied in the same environment using our proposed ITS Wayback Machine. More importantly, we track the evolutionary metrics in the ITS when a custom triage/prioritization strategy is employed. We test the efficiency of the proposed algorithm using data extracted from three open-source projects. Our empirical study sheds light on the overlooked evolutionary metrics--e.g., overdue bugs and developers' loads--which are facilitated via our proposed past-event re-generator.
Theoretical Rule-based Knowledge Graph Reasoning by Connectivity Dependency Discovery
Venue: arXiv cs.CL 2022
Year: 2022

Discovering precise and interpretable rules from knowledge graphs is regarded as an essential challenge, which can improve the performances of many downstream tasks and even provide new ways to approach some Natural Language Processing research topics. In this paper, we present a fundamental theory for rule-based knowledge graph reasoning, based on which the connectivity dependencies in the graph are captured via multiple rule types. It is the first time for some of these rule types in a knowledge graph to be considered. Based on these rule types, our theory can provide precise interpretations to unknown triples. Then, we implement our theory by what we call the RuleDict model. Results show that our RuleDict model not only provides precise rules to interpret new triples, but also achieves state-of-the-art performances on one benchmark knowledge graph completion task, and is competitive on other tasks.
Mathematical Analysis of Path MTU Discovery With New Generation Networks
Venue: arXiv cs.NI 2022
Year: 2022

In this paper we have presented the effects of path mtu discovery in IPv4 & IPv6 in mathematical, logical and graphical representation. We try to give a mathematical model to the working of path mtu discovery and calculated its behaviour using a transmission of a packet. We analysed the time consumed to transmit a single packet from source to destination in IPv6 network in the presence of PMTUD and similarly in IPv4 network with DF bit 1. Based on our analysis, we concluded that the communication time increases with the varying MTU of the intermediate nodes. Moreover, we formulated the mathematical model to determine the communication delay in a network. Our model shows that the asymptotic lower bound for time taken is $Ω(n)$ and the asymptotic upper bound is $Θ(n^2)$, using PMTUD. We have find that the packet drop frequency follows the Bernoulli's trials and which helps to define the success probability of the packet drop frequency, which shows that the probability is higher for packet drop rate for beginning $2\%$ of the total nodes in the path. We further found that $^{n}C_{a}$ possible number of a-combinations without repetitions that can be formed for a particular number of packet drop frequency. The relation between summation (acts as a coefficient in the time wastage equation) of each combination and their frequency resulted in symmetric graph and also mathematical and statistical structures to measure time wastage and its behaviour. This also helps in measuring the possible relative maximum, minimum and average time wastage. We also measured the probability of relative maximum, min and average summation for a given value of packet drop frequency and number of nodes in a path.
Synthetic Data -- Anonymisation Groundhog Day
Venue: arXiv cs.LG 2022
Year: 2022

Synthetic data has been advertised as a silver-bullet solution to privacy-preserving data publishing that addresses the shortcomings of traditional anonymisation techniques. The promise is that synthetic data drawn from generative models preserves the statistical properties of the original dataset but, at the same time, provides perfect protection against privacy attacks. In this work, we present the first quantitative evaluation of the privacy gain of synthetic data publishing and compare it to that of previous anonymisation techniques. Our evaluation of a wide range of state-of-the-art generative models demonstrates that synthetic data either does not prevent inference attacks or does not retain data utility. In other words, we empirically show that synthetic data does not provide a better tradeoff between privacy and utility than traditional anonymisation techniques. Furthermore, in contrast to traditional anonymisation, the privacy-utility tradeoff of synthetic data publishing is hard to predict. Because it is impossible to predict what signals a synthetic dataset will preserve and what information will be lost, synthetic data leads to a highly variable privacy gain and unpredictable utility loss. In summary, we find that synthetic data is far from the holy grail of privacy-preserving data publishing.