OpenRaiser/Intern-Atlas huggingface dataset:
Exploring DeshuffleGANs in Self-Supervised Generative Adversarial Networks
Venue: arXiv cs.CV 2021
Year: 2021

Generative Adversarial Networks (GANs) have become the most used networks towards solving the problem of image generation. Self-supervised GANs are later proposed to avoid the catastrophic forgetting of the discriminator and to improve the image generation quality without needing the class labels. However, the generalizability of the self-supervision tasks on different GAN architectures is not studied before. To that end, we extensively analyze the contribution of a previously proposed self-supervision task, deshuffling of the DeshuffleGANs in the generalizability context. We assign the deshuffling task to two different GAN discriminators and study the effects of the task on both architectures. We extend the evaluations compared to the previously proposed DeshuffleGANs on various datasets. We show that the DeshuffleGAN obtains the best FID results for several datasets compared to the other self-supervised GANs. Furthermore, we compare the deshuffling with the rotation prediction that is firstly deployed to the GAN training and demonstrate that its contribution exceeds the rotation prediction. We design the conditional DeshuffleGAN called cDeshuffleGAN to evaluate the quality of the learnt representations. Lastly, we show the contribution of the self-supervision tasks to the GAN training on the loss landscape and present that the effects of these tasks may not be cooperative to the adversarial training in some settings. Our code can be found at https://github.com/gulcinbaykal/DeshuffleGAN.
Reinforcement Learning for Test Case Prioritization
Venue: arXiv cs.SE 2021
Year: 2021

Continuous Integration (CI) significantly reduces integration problems, speeds up development time, and shortens release time. However, it also introduces new challenges for quality assurance activities, including regression testing, which is the focus of this work. Though various approaches for test case prioritization have shown to be very promising in the context of regression testing, specific techniques must be designed to deal with the dynamic nature and timing constraints of CI. Recently, Reinforcement Learning (RL) has shown great potential in various challenging scenarios that require continuous adaptation, such as game playing, real-time ads bidding, and recommender systems. Inspired by this line of work and building on initial efforts in supporting test case prioritization with RL techniques, we perform here a comprehensive investigation of RL-based test case prioritization in a CI context. To this end, taking test case prioritization as a ranking problem, we model the sequential interactions between the CI environment and a test case prioritization agent as an RL problem, using three alternative ranking models. We then rely on carefully selected and tailored state-of-the-art RL techniques to automatically and continuously learn a test case prioritization strategy, whose objective is to be as close as possible to the optimal one. Our extensive experimental analysis shows that the best RL solutions provide a significant accuracy improvement over previous RL-based work, with prioritization strategies getting close to being optimal, thus paving the way for using RL to prioritize test cases in a CI context.
Weed Density and Distribution Estimation for Precision Agriculture using Semi-Supervised Learning
Venue: arXiv cs.CV 2021
Year: 2021

Uncontrolled growth of weeds can severely affect the crop yield and quality. Unrestricted use of herbicide for weed removal alters biodiversity and cause environmental pollution. Instead, identifying weed-infested regions can aid selective chemical treatment of these regions. Advances in analyzing farm images have resulted in solutions to identify weed plants. However, a majority of these approaches are based on supervised learning methods which requires huge amount of manually annotated images. As a result, these supervised approaches are economically infeasible for the individual farmer because of the wide variety of plant species being cultivated. In this paper, we propose a deep learning-based semi-supervised approach for robust estimation of weed density and distribution across farmlands using only limited color images acquired from autonomous robots. This weed density and distribution can be useful in a site-specific weed management system for selective treatment of infected areas using autonomous robots. In this work, the foreground vegetation pixels containing crops and weeds are first identified using a Convolutional Neural Network (CNN) based unsupervised segmentation. Subsequently, the weed infected regions are identified using a fine-tuned CNN, eliminating the need for designing hand-crafted features. The approach is validated on two datasets of different crop/weed species (1) Crop Weed Field Image Dataset (CWFID), which consists of carrot plant images and the (2) Sugar Beets dataset. The proposed method is able to localize weed-infested regions a maximum recall of 0.99 and estimate weed density with a maximum accuracy of 82.13%. Hence, the proposed approach is shown to generalize to different plant species without the need for extensive labeled data.
Debiasing classifiers: is reality at variance with expectation?
Venue: arXiv cs.LG 2021
Year: 2021

We present an empirical study of debiasing methods for classifiers, showing that debiasers often fail in practice to generalize out-of-sample, and can in fact make fairness worse rather than better. A rigorous evaluation of the debiasing treatment effect requires extensive cross-validation beyond what is usually done. We demonstrate that this phenomenon can be explained as a consequence of bias-variance trade-off, with an increase in variance necessitated by imposing a fairness constraint. Follow-up experiments validate the theoretical prediction that the estimation variance depends strongly on the base rates of the protected class. Considering fairness--performance trade-offs justifies the counterintuitive notion that partial debiasing can actually yield better results in practice on out-of-sample data.
A Smart Backtracking Algorithm for Computing Set Partitions with Parts of Certain Sizes
Venue: arXiv cs.DS 2021
Year: 2021

Let $α=\{a_1,a_2,a_3,...,a_n\}$ be a set of elements, $δ< n$ be a non-negative integer, and $Γ: α\to \{0, 1, 2, ..., n\}$ be a total mapping. Then, we call $Γ$ a \emph{partition} of $α$ if and only if for all $x \in α$, $Γ(x) \neq 0$. Further, we call $Γ$ a $δ$-\emph{partition} of $α$ if and only if $Γ$ is a partition of $α$ and for all $i \in \{1, 2, 3, ..., n\}$, $|\{x: Γ(x)=i\}| > δ$. We give a non-trivial algorithm that computes all $δ$-partitions of $α$ in $Ω(n)$ time. On the opposite, a naive generate-and-test algorithm would compute all $δ$-partitions of $α$ in $Ω(nB_n)$ time where $B_n$ is the Bell number.
Towards a more perfect union type
Venue: arXiv cs.PL 2021
Year: 2021

We present a principled theoretical framework for inferring and checking the union types, and show its work in practice on JSON data structures. The framework poses a union type inference as a learning problem from multiple examples. The categorical framework is generic and easily extensible.
IFC models for (semi)automating common planning checks for building permits
Venue: arXiv cs.CY 2021
Year: 2021

To support building permit issuing with automatic digital tools, the reuse of models produced by designers would make the process quicker and more objective. However, current studies and pilots often leave a gap with respect to the models as actually provided by architects, having varying quality and content. In this study, rather than taking a top down approach, we started from the available data and made the necessary inferences, which gave the opportunity to tackle basic and common issues often preventing smooth automatic processing. Specific characteristics of the IFC models were outlined and a tool was developed to extract the necessary information from them to check representative regulations. While the case study is specific in location, regulations and input models, the type of issues encountered are a generally applicable example for automated code compliance checking. This represents a solid base for future works towards the automation of building permits issuing.
Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems
Venue: arXiv cs.DS 2021
Year: 2021

We develop fast approximation algorithms for the minimum-cost version of the Bounded-Degree MST problem (BD-MST) and its generalization the Crossing Spanning Tree problem (Crossing-ST). We solve the underlying LP to within a $(1+ε)$ approximation factor in near-linear time via the multiplicative weight update (MWU) technique. This yields, in particular, a near-linear time algorithm that outputs an estimate $B$ such that $B \le B^* \le \lceil (1+ε)B \rceil +1$ where $B^*$ is the minimum-degree of a spanning tree of a given graph. To round the fractional solution, in our main technical contribution, we describe a fast near-linear time implementation of swap-rounding in the spanning tree polytope of a graph. The fractional solution can also be used to sparsify the input graph that can in turn be used to speed up existing combinatorial algorithms. Together, these ideas lead to significantly faster approximation algorithms than known before for the two problems of interest. In addition, a fast algorithm for swap rounding in the graphic matroid is a generic tool that has other applications, including to TSP and submodular function maximization.
"What's This?" -- Learning to Segment Unknown Objects from Manipulation Sequences
Venue: arXiv cs.CV 2021
Year: 2021

We present a novel framework for self-supervised grasped object segmentation with a robotic manipulator. Our method successively learns an agnostic foreground segmentation followed by a distinction between manipulator and object solely by observing the motion between consecutive RGB frames. In contrast to previous approaches, we propose a single, end-to-end trainable architecture which jointly incorporates motion cues and semantic knowledge. Furthermore, while the motion of the manipulator and the object are substantial cues for our algorithm, we present means to robustly deal with distraction objects moving in the background, as well as with completely static scenes. Our method neither depends on any visual registration of a kinematic robot or 3D object models, nor on precise hand-eye calibration or any additional sensor data. By extensive experimental evaluation we demonstrate the superiority of our framework and provide detailed insights on its capability of dealing with the aforementioned extreme cases of motion. We also show that training a semantic segmentation network with the automatically labeled data achieves results on par with manually annotated training data. Code and pretrained model are available at https://github.com/DLR-RM/DistinctNet.
Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space
Venue: arXiv cs.DS 2021
Year: 2021

We provide $\widetilde{O}(ε^{-1})$-pass semi-streaming algorithms for computing $(1-ε)$-approximate maximum cardinality matchings in bipartite graphs. Our most efficient methods are deterministic and use optimal, $O(n)$, space, improving upon the space complexity of the previous state-of-the-art $\widetilde{O}(ε^{-1})$-pass algorithm of Ahn and Guha. To obtain our results we provide semi-streaming adaptations of more general continuous optimization tools. Further, we leverage these techniques to obtain improvements for streaming variants of approximate linear programming, optimal transport, exact matching, transshipment, and shortest path problems.
Less Arbitrary waiting time
Venue: arXiv cs.PL 2021
Year: 2021

Property testing is the cheapest and most precise way of building up a test suite for your program. Especially if the datatypes enjoy nice mathematical laws. But it is also the easiest way to make it run for an unreasonably long time. We prove connection between deeply recursive data structures, and epidemic growth rate, and show how to fix the problem, and make Arbitrary instances run in linear time with respect to assumed test size.
ControlFlag: A Self-Supervised Idiosyncratic Pattern Detection System for Software Control Structures
Venue: arXiv cs.SE 2021
Year: 2021

Software debugging has been shown to utilize upwards of half of developers' time. Yet, machine programming (MP), the field concerned with the automation of software (and hardware) development, has recently made strides in both research and production-quality automated debugging systems. In this paper we present ControlFlag, a self-supervised MP system that aims to improve debugging by attempting to detect idiosyncratic pattern violations in software control structures. ControlFlag also suggests possible corrections in the event an anomalous pattern is detected. We present ControlFlag's design and provide an experimental evaluation and analysis of its efficacy in identifying potential programming errors in production-quality software. As a first concrete evidence towards improving software quality, ControlFlag has already found an anomaly in CURL that has been acknowledged and fixed by its developers. We also discuss future extensions of ControlFlag.
A Reinforcement Learning Approach to the Orienteering Problem with Time Windows
Venue: arXiv cs.LG 2021
Year: 2021

The Orienteering Problem with Time Windows (OPTW) is a combinatorial optimization problem where the goal is to maximize the total score collected from different visited locations. The application of neural network models to combinatorial optimization has recently shown promising results in dealing with similar problems, like the Travelling Salesman Problem. A neural network allows learning solutions using reinforcement learning or supervised learning, depending on the available data. After the learning stage, it can be generalized and quickly fine-tuned to further improve performance and personalization. The advantages are evident since, for real-world applications, solution quality, personalization, and execution times are all important factors that should be taken into account. This study explores the use of Pointer Network models trained using reinforcement learning to solve the OPTW problem. We propose a modified architecture that leverages Pointer Networks to better address problems related with dynamic time-dependent constraints. Among its various applications, the OPTW can be used to model the Tourist Trip Design Problem (TTDP). We train the Pointer Network with the TTDP problem in mind, by sampling variables that can change across tourists visiting a particular instance-region: starting position, starting time, available time, and the scores given to each point of interest. Once a model-region is trained, it can infer a solution for a particular tourist using beam search. We based the assessment of our approach on several existing benchmark OPTW instances. We show that it generalizes across different tourists that visit each region and that it generally outperforms the most commonly used heuristic, while computing the solution in realistic times.
Symmetric Parallax Attention for Stereo Image Super-Resolution
Venue: arXiv cs.CV 2021
Year: 2021

Although recent years have witnessed the great advances in stereo image super-resolution (SR), the beneficial information provided by binocular systems has not been fully used. Since stereo images are highly symmetric under epipolar constraint, in this paper, we improve the performance of stereo image SR by exploiting symmetry cues in stereo image pairs. Specifically, we propose a symmetric bi-directional parallax attention module (biPAM) and an inline occlusion handling scheme to effectively interact cross-view information. Then, we design a Siamese network equipped with a biPAM to super-resolve both sides of views in a highly symmetric manner. Finally, we design several illuminance-robust losses to enhance stereo consistency. Experiments on four public datasets demonstrate the superior performance of our method. Source code is available at https://github.com/YingqianWang/iPASSR.
Interpretable Locally Adaptive Nearest Neighbors
Venue: arXiv cs.LG 2021
Year: 2021

When training automated systems, it has been shown to be beneficial to adapt the representation of data by learning a problem-specific metric. This metric is global. We extend this idea and, for the widely used family of k nearest neighbors algorithms, develop a method that allows learning locally adaptive metrics. These local metrics not only improve performance but are naturally interpretable. To demonstrate important aspects of how our approach works, we conduct a number of experiments on synthetic data sets, and we show its usefulness on real-world benchmark data sets.
Multiscale Reduced-Order Modeling of a Titanium Skin Panel Subjected to Thermo-Mechanical Loading
Venue: arXiv cs.CE 2021
Year: 2021

This manuscript presents the formulation, implementation, calibration and application of a multiscale reduced-order model to simulate a titanium panel structure subjected to thermo-mechanical loading associated with high-speed flight. The formulation is based on the eigenstrain-based reduced-order homogenization model (EHM) and further considers thermal strain as well as temperature dependent material properties and evolution laws. The material microstructure (i.e., at the scale of a polycrystalline representative volume element (RVE)) and underlying microstructural mechanisms are directly incorporated and fully coupled with a structural analysis, allowing concurrently probing the response at the structural scale and the material microscale. The proposed approach was fully calibrated using a series of uniaxial tension tests of Ti-6242S at a wide range of temperatures and two different strain rates. The calibrated model is then adopted to study the response of a generic aircraft skin panel subjected to thermo-mechanical loading associated with high-speed flight. The analysis focuses on demonstrating the capability of the model to predict not only the structural scale response, but simultaneously the microscale response, and further studies the effects of temperature and texture on the response.
Smooth approximations and CSPs over finitely bounded homogeneous structures
Venue: arXiv cs.LO 2021
Year: 2021

We develop the novel machinery of smooth approximations, and apply it to confirm the CSP dichotomy conjecture for first-order reducts of the random tournament, various homogeneous graphs including the random graph, and for expansions of the order of the rationals. Apart from obtaining these dichotomy results, we show how our new proof technique allows to unify and significantly simplify the previous results from the literature. For all but the last structure, we moreover characterize those CSPs which are solvable by local consistency methods, again using the same machinery.
Posture Adjustment for a Wheel-legged Robotic System via Leg Force Control with Prescribed Transient Performance
Venue: arXiv cs.RO 2021
Year: 2021

This work proposes a force control strategy with prescribed transient performance for the legs of a wheel-legged robotic system to realize the posture adjustment on uneven roads. A dynamic model of the robotic system is established with the body postures as inputs and the leg forces as outputs, such that the desired forces for the wheel-legs are calculated by the posture reference and feedback. Based on the funnel control scheme, the legs realize force tracking with prescribed transient performance. To improve the robustness of the force control system, an event-based mechanism is designed for the online segment of the funnel function. As a result, the force tracking error of the wheel-leg evolves inside the performance funnel with proved convergence. The absence of Zeno behavior for the event-triggering condition is also guaranteed. The proposed control scheme is applied to the wheel-legged physical prototype for the performance of force tracking and posture adjustment. Multiple comparative experimental results are presented to validate the stability and effectiveness of the proposed methodology.
Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu
Venue: arXiv cs.DS 2021
Year: 2021

We provide finite sample guarantees for the classical Chow-Liu algorithm (IEEE Trans.~Inform.~Theory, 1968) to learn a tree-structured graphical model of a distribution. For a distribution $P$ on $Σ^n$ and a tree $T$ on $n$ nodes, we say $T$ is an $\varepsilon$-approximate tree for $P$ if there is a $T$-structured distribution $Q$ such that $D(P\;||\;Q)$ is at most $\varepsilon$ more than the best possible tree-structured distribution for $P$. We show that if $P$ itself is tree-structured, then the Chow-Liu algorithm with the plug-in estimator for mutual information with $\widetilde{O}(|Σ|^3 n\varepsilon^{-1})$ i.i.d.~samples outputs an $\varepsilon$-approximate tree for $P$ with constant probability. In contrast, for a general $P$ (which may not be tree-structured), $Ω(n^2\varepsilon^{-2})$ samples are necessary to find an $\varepsilon$-approximate tree. Our upper bound is based on a new conditional independence tester that addresses an open problem posed by Canonne, Diakonikolas, Kane, and Stewart~(STOC, 2018): we prove that for three random variables $X,Y,Z$ each over $Σ$, testing if $I(X; Y \mid Z)$ is $0$ or $\geq \varepsilon$ is possible with $\widetilde{O}(|Σ|^3/\varepsilon)$ samples. Finally, we show that for a specific tree $T$, with $\widetilde{O} (|Σ|^2n\varepsilon^{-1})$ samples from a distribution $P$ over $Σ^n$, one can efficiently learn the closest $T$-structured distribution in KL divergence by applying the add-1 estimator at each node.
SplitEasy: A Practical Approach for Training ML models on Mobile Devices
Venue: arXiv cs.LG 2021
Year: 2021

Modern mobile devices, although resourceful, cannot train state-of-the-art machine learning models without the assistance of servers, which require access to, potentially, privacy-sensitive user data. Split learning has recently emerged as a promising technique for training complex deep learning (DL) models on low-powered mobile devices. The core idea behind this technique is to train the sensitive layers of a DL model on mobile devices while offloading the computationally intensive layers to a server. Although a lot of works have already explored the effectiveness of split learning in simulated settings, a usable toolkit for this purpose does not exist. In this work, we highlight the theoretical and technical challenges that need to be resolved to develop a functional framework that trains ML models in mobile devices without transferring raw data to a server. Focusing on these challenges, we propose SplitEasy, a framework for training ML models on mobile devices using split learning. Using the abstraction provided by SplitEasy, developers can run various DL models under split learning setting by making minimal modifications. We provide a detailed explanation of SplitEasy and perform experiments with six state-of-the-art neural networks. We demonstrate how SplitEasy can train models that cannot be trained solely by a mobile device while incurring nearly constant time per data sample.