OpenRaiser/Intern-Atlas huggingface dataset:
Word Embeddings via Causal Inference: Gender Bias Reducing and Semantic Information Preserving
Venue: arXiv cs.CL 2021
Year: 2021

With widening deployments of natural language processing (NLP) in daily life, inherited social biases from NLP models have become more severe and problematic. Previous studies have shown that word embeddings trained on human-generated corpora have strong gender biases that can produce discriminative results in downstream tasks. Previous debiasing methods focus mainly on modeling bias and only implicitly consider semantic information while completely overlooking the complex underlying causal structure among bias and semantic components. To address these issues, we propose a novel methodology that leverages a causal inference framework to effectively remove gender bias. The proposed method allows us to construct and analyze the complex causal mechanisms facilitating gender information flow while retaining oracle semantic information within word embeddings. Our comprehensive experiments show that the proposed method achieves state-of-the-art results in gender-debiasing tasks. In addition, our methods yield better performance in word similarity evaluation and various extrinsic downstream NLP tasks.
The Fundamental Limits of Interval Arithmetic for Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

Interval analysis (or interval bound propagation, IBP) is a popular technique for verifying and training provably robust deep neural networks, a fundamental challenge in the area of reliable machine learning. However, despite substantial efforts, progress on addressing this key challenge has stagnated, calling into question whether interval arithmetic is a viable path forward. In this paper we present two fundamental results on the limitations of interval arithmetic for analyzing neural networks. Our main impossibility theorem states that for any neural network classifying just three points, there is a valid specification over these points that interval analysis can not prove. Further, in the restricted case of one-hidden-layer neural networks we show a stronger impossibility result: given any radius $α< 1$, there is a set of $O(α^{-1})$ points with robust radius $α$, separated by distance $2$, that no one-hidden-layer network can be proven to classify robustly via interval analysis.
Semantic Construction Grammar: Bridging the NL / Logic Divide
Venue: arXiv cs.CL 2021
Year: 2021

In this paper, we discuss Semantic Construction Grammar (SCG), a system developed over the past several years to facilitate translation between natural language and logical representations. Crucially, SCG is designed to support a variety of different methods of representation, ranging from those that are fairly close to the NL structure (e.g. so-called 'logical forms'), to those that are quite different from the NL structure, with higher-order and high-arity relations. Semantic constraints and checks on representations are integral to the process of NL understanding with SCG, and are easily carried out due to the SCG's integration with Cyc's Knowledge Base and inference engine.
3D Scene Understanding at Urban Intersection using Stereo Vision and Digital Map
Venue: arXiv cs.CV 2021
Year: 2021

The driving behavior at urban intersections is very complex. It is thus crucial for autonomous vehicles to comprehensively understand challenging urban traffic scenes in order to navigate intersections and prevent accidents. In this paper, we introduce a stereo vision and 3D digital map based approach to spatially and temporally analyze the traffic situation at urban intersections. Stereo vision is used to detect, classify and track obstacles, while a 3D digital map is used to improve ego-localization and provide context in terms of road-layout information. A probabilistic approach that temporally integrates these geometric, semantic, dynamic and contextual cues is presented. We qualitatively and quantitatively evaluate our proposed technique on real traffic data collected at an urban canyon in Tokyo to demonstrate the efficacy of the system in providing comprehensive awareness of the traffic surroundings.
LUNAR: Unifying Local Outlier Detection Methods via Graph Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

Many well-established anomaly detection methods use the distance of a sample to those in its local neighbourhood: so-called `local outlier methods', such as LOF and DBSCAN. They are popular for their simple principles and strong performance on unstructured, feature-based data that is commonplace in many practical applications. However, they cannot learn to adapt for a particular set of data due to their lack of trainable parameters. In this paper, we begin by unifying local outlier methods by showing that they are particular cases of the more general message passing framework used in graph neural networks. This allows us to introduce learnability into local outlier methods, in the form of a neural network, for greater flexibility and expressivity: specifically, we propose LUNAR, a novel, graph neural network-based anomaly detection method. LUNAR learns to use information from the nearest neighbours of each node in a trainable way to find anomalies. We show that our method performs significantly better than existing local outlier methods, as well as state-of-the-art deep baselines. We also show that the performance of our method is much more robust to different settings of the local neighbourhood size.
Efficient Action Poisoning Attacks on Linear Contextual Bandits
Venue: arXiv cs.LG 2021
Year: 2021

Contextual bandit algorithms have many applicants in a variety of scenarios. In order to develop trustworthy contextual bandit systems, understanding the impacts of various adversarial attacks on contextual bandit algorithms is essential. In this paper, we propose a new class of attacks: action poisoning attacks, where an adversary can change the action signal selected by the agent. We design action poisoning attack schemes against linear contextual bandit algorithms in both white-box and black-box settings. We further analyze the cost of the proposed attack strategies for a very popular and widely used bandit algorithm: LinUCB. We show that, in both white-box and black-box settings, the proposed attack schemes can force the LinUCB agent to pull a target arm very frequently by spending only logarithm cost.
Dandelion-Picking Legged Robot
Venue: arXiv cs.RO 2021
Year: 2021

Agriculture is currently undergoing a robotics revolution, but robots using wheeled or treads suffer from known disadvantages: they are unable to move over rubble and steep or loose ground, and they trample continuous strips of land thereby reducing the viable crop area. Legged robots offer an alternative, but existing commercial legged robots are complex, expensive, and hard to maintain. We propose the use of multilegged robots using low-degree-of-freedom (low-DoF) legs and demonstrate our approach with a lawn pest control task: picking dandelions using our inexpensive and easy to fabricate BigANT robot. For this task we added an RGB-D camera to the robot. We also rigidly attached a flower picking appendage to the robot chassis. Thanks to the versatility of legs, the robot could be programmed to perform a ``swooping'' motion that allowed this 0-DoF appendage to pluck the flowers. Our results suggest that robots with six or more low-DoF legs may hit a sweet-spot for legged robots designed for agricultural applications by providing enough mobility, stability, and low complexity.
Towards Full-to-Empty Room Generation with Structure-Aware Feature Encoding and Soft Semantic Region-Adaptive Normalization
Venue: arXiv cs.CV 2021
Year: 2021

The task of transforming a furnished room image into a background-only is extremely challenging since it requires making large changes regarding the scene context while still preserving the overall layout and style. In order to acquire photo-realistic and structural consistent background, existing deep learning methods either employ image inpainting approaches or incorporate the learning of the scene layout as an individual task and leverage it later in a not fully differentiable semantic region-adaptive normalization module. To tackle these drawbacks, we treat scene layout generation as a feature linear transformation problem and propose a simple yet effective adjusted fully differentiable soft semantic region-adaptive normalization module (softSEAN) block. We showcase the applicability in diminished reality and depth estimation tasks, where our approach besides the advantages of mitigating training complexity and non-differentiability issues, surpasses the compared methods both quantitatively and qualitatively. Our softSEAN block can be used as a drop-in module for existing discriminative and generative models. Implementation is available on vcl3d.github.io/PanoDR/.
Predicting Physical World Destinations for Commands Given to Self-Driving Cars
Venue: arXiv cs.AI 2021
Year: 2021

In recent years, we have seen significant steps taken in the development of self-driving cars. Multiple companies are starting to roll out impressive systems that work in a variety of settings. These systems can sometimes give the impression that full self-driving is just around the corner and that we would soon build cars without even a steering wheel. The increase in the level of autonomy and control given to an AI provides an opportunity for new modes of human-vehicle interaction. However, surveys have shown that giving more control to an AI in self-driving cars is accompanied by a degree of uneasiness by passengers. In an attempt to alleviate this issue, recent works have taken a natural language-oriented approach by allowing the passenger to give commands that refer to specific objects in the visual scene. Nevertheless, this is only half the task as the car should also understand the physical destination of the command, which is what we focus on in this paper. We propose an extension in which we annotate the 3D destination that the car needs to reach after executing the given command and evaluate multiple different baselines on predicting this destination location. Additionally, we introduce a model that outperforms the prior works adapted for this particular setting.
Robustification of Online Graph Exploration Methods
Venue: arXiv cs.LG 2021
Year: 2021

Exploring unknown environments is a fundamental task in many domains, e.g., robot navigation, network security, and internet search. We initiate the study of a learning-augmented variant of the classical, notoriously hard online graph exploration problem by adding access to machine-learned predictions. We propose an algorithm that naturally integrates predictions into the well-known Nearest Neighbor (NN) algorithm and significantly outperforms any known online algorithm if the prediction is of high accuracy while maintaining good guarantees when the prediction is of poor quality. We provide theoretical worst-case bounds that gracefully degrade with the prediction error, and we complement them by computational experiments that confirm our results. Further, we extend our concept to a general framework to robustify algorithms. By interpolating carefully between a given algorithm and NN, we prove new performance bounds that leverage the individual good performance on particular inputs while establishing robustness to arbitrary inputs.
Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem
Venue: arXiv cs.CG 2021
Year: 2021

Let $P$ be a set of points in $\mathbb{R}^d$, where each point $p\in P$ has an associated transmission range $ρ(p)$. The range assignment $ρ$ induces a directed communication graph $\mathcal{G}_ρ(P)$ on $P$, which contains an edge $(p,q)$ iff $|pq| \leq ρ(p)$. In the broadcast range-assignment problem, the goal is to assign the ranges such that $\mathcal{G}_ρ(P)$ contains an arborescence rooted at a designated node and whose cost $\sum_{p \in P} ρ(p)^2$ is minimized. We study trade-offs between the stability of the solution -- the number of ranges that are modified when a point is inserted into or deleted from $P$ -- and its approximation ratio. We introduce $k$-stable algorithms, which are algorithms that modify the range of at most $k$ points when they update the solution. We also introduce the concept of a stable approximation scheme (SAS). A SAS is an update algorithm that, for any given fixed parameter $\varepsilon>0$, is $k(ε)$-stable and maintains a solution with approximation ratio $1+\varepsilon$, where the stability parameter $k(\varepsilon)$ only depends on $\varepsilon$ and not on the size of $P$. We study such trade-offs in three settings. - In $\mathbb{R}^1$, we present a SAS with $k(\varepsilon)=O(1/\varepsilon)$, which we show is tight in the worst case. We also present a 1-stable $(6+2\sqrt{5})$-approximation algorithm, a $2$-stable 2-approximation algorithm, and a $3$-stable $1.97$-approximation algorithm. - In $\mathbb{S}^1$ (where the underlying space is a circle) we prove that no SAS exists, even though an optimal solution can always be obtained by cutting the circle at an appropriate point and solving the resulting problem in $\mathbb{R}^1$. - In $\mathbb{R}^2$, we also prove that no SAS exists, and we present a $O(1)$-stable $O(1)$-approximation algorithm.
Sentiment Analysis on Brazilian Portuguese User Reviews
Venue: arXiv cs.CL 2021
Year: 2021

Sentiment Analysis is one of the most classical and primarily studied natural language processing tasks. This problem had a notable advance with the proposition of more complex and scalable machine learning models. Despite this progress, the Brazilian Portuguese language still disposes only of limited linguistic resources, such as datasets dedicated to sentiment classification, especially when considering the existence of predefined partitions in training, testing, and validation sets that would allow a more fair comparison of different algorithm alternatives. Motivated by these issues, this work analyzes the predictive performance of a range of document embedding strategies, assuming the polarity as the system outcome. This analysis includes five sentiment analysis datasets in Brazilian Portuguese, unified in a single dataset, and a reference partitioning in training, testing, and validation sets, both made publicly available through a digital repository. A cross-evaluation of dataset-specific models over different contexts is conducted to evaluate their generalization capabilities and the feasibility of adopting a unique model for addressing all scenarios.
Surrogate-data-enriched Physics-Aware Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

Neural networks can be used as surrogates for PDE models. They can be made physics-aware by penalizing underlying equations or the conservation of physical properties in the loss function during training. Current approaches allow to additionally respect data from numerical simulations or experiments in the training process. However, this data is frequently expensive to obtain and thus only scarcely available for complex models. In this work, we investigate how physics-aware models can be enriched with computationally cheaper, but inexact, data from other surrogate models like Reduced-Order Models (ROMs). In order to avoid trusting too-low-fidelity surrogate solutions, we develop an approach that is sensitive to the error in inexact data. As a proof of concept, we consider the one-dimensional wave equation and show that the training accuracy is increased by two orders of magnitude when inexact data from ROMs is incorporated.
Sparse Depth Completion with Semantic Mesh Deformation Optimization
Venue: arXiv cs.CV 2021
Year: 2021

Sparse depth measurements are widely available in many applications such as augmented reality, visual inertial odometry and robots equipped with low cost depth sensors. Although such sparse depth samples work well for certain applications like motion tracking, a complete depth map is usually preferred for broader applications, such as 3D object recognition, 3D reconstruction and autonomous driving. Despite the recent advancements in depth prediction from single RGB images with deeper neural networks, the existing approaches do not yield reliable results for practical use. In this work, we propose a neural network with post-optimization, which takes an RGB image and sparse depth samples as input and predicts the complete depth map. We make three major contributions to advance the state-of-the-art: an improved backbone network architecture named EDNet, a semantic edge-weighted loss function and a semantic mesh deformation optimization method. Our evaluation results outperform the existing work consistently on both indoor and outdoor datasets, and it significantly reduces the mean average error by up to 19.5% under the same settings of 200 sparse samples on NYU-Depth-V2 dataset.
Semantic Cut Elimination for the Logic of Bunched Implications, Formalized in Coq
Venue: arXiv cs.LO 2021
Year: 2021

The logic of bunched implications (BI) is a substructural logic that forms the backbone of separation logic, the much studied logic for reasoning about heap-manipulating programs. Although the proof theory and metatheory of BI are mathematically involved, the formalization of important metatheoretical results is still incipient. In this paper we present a self-contained formalized, in the Coq proof assistant, proof of a central metatheoretical property of BI: cut elimination for its sequent calculus. The presented proof is *semantic*, in the sense that is obtained by interpreting sequents in a particular "universal" model. This results in a more modular and elegant proof than a standard Gentzen-style cut elimination argument, which can be subtle and error-prone in manual proofs for BI. In particular, our semantic approach avoids unnecessary inversions on proof derivations, or the uses of cut reductions and the multi-cut rule. Besides modular, our approach is also robust: we demonstrate how our method scales, with minor modifications, to (i) an extension of BI with an arbitrary set of \emph{simple structural rules}, and (ii) an extension with an S4-like $\Box$ modality.
TechRank: A Network-Centrality Approach for Informed Cybersecurity-Investment
Venue: arXiv cs.CR 2021
Year: 2021

The cybersecurity technological landscape is a complex ecosystem in which entities -- such as companies and technologies -- influence each other in a non-trivial manner. Measuring the influence between entities is a tenet for informed technological investments in critical infrastructure. To study the mutual influence of companies and technologies from the cybersecurity field, we consider a bi-partite graph that links both sets of entities. Each node in this graph is weighted by applying a recursive algorithm based on the method of reflection. This endeavor helps to measure the impact of an entity on the cybersecurity market. Our results help researchers measure more precisely the magnitude of influence of each entity, and allows decision-makers to devise more informed investment strategies, according to their portfolio preferences. Finally, a research agenda is suggested, with the aim of allowing tailor-made investments by arbitrarily calibrating specific features of both types of entities.
Stackless Ray-Object Intersections Using Approximate Minimum Weight Triangulations: Results in 2D That Outperform Roped KD-Trees (And Massively Outperform BVHs)
Venue: arXiv cs.GR 2021
Year: 2021

The kd-tree and Bounding Volume Hierarchy (BVH) are well-known data structures for computing ray-object intersections. Less known is the Constrained Convex Space Partitioning (CCSP), which partitions space and makes the geometric primitives exactly overlap with the boundaries of its cells. Consequently, it is robust against ill-fitting cells that plague methods with axis-aligned cells (kd-tree, BVH) and it permits an efficient, stackless traversal. Within computer graphics, CCSPs have received some attention in both 2D and 3D, but their construction methods were never directly aimed at minimizing their traversal cost -- even having fundamentally opposing goals for Delaunay-type methods. Instead, for an isotropic and translation-invariant ray distribution the traversal cost is minimized by minimizing the weight: the total boundary size of all cells in the structure. We study the 2D case using triangulations as CCSPs and minimize their total edge length using a simulated annealing process that allows for topological changes and varying vertex count. Standard Delaunay-based triangulation techniques show total edge lengths ranging from 10% higher to twice as high as our optimized triangulations for a variety of scenes, with a similar difference in traversal cost when using the triangulations for ray tracing. Compared to a roped kd-tree, our triangulations require less traversal steps for all scenes that we tested and they are robust against the kd-tree's pathological behaviour when geometry becomes misaligned with the world axes. Moreover, the stackless traversal strongly outperforms a BVH, which always requires a top-down descent in the hierarchy. In fact, we show several scenes where the number of traversal operations for our triangulations decreases(!) as the number of geometric primitives $N$ increases, in contrast to the increasing $\log N$ behaviour of a BVH.
Towards autonomous artificial agents with an active self: modeling sense of control in situated action
Venue: arXiv cs.AI 2021
Year: 2021

In this paper we present a computational modeling account of an active self in artificial agents. In particular we focus on how an agent can be equipped with a sense of control and how it arises in autonomous situated action and, in turn, influences action control. We argue that this requires laying out an embodied cognitive model that combines bottom-up processes (sensorimotor learning and fine-grained adaptation of control) with top-down processes (cognitive processes for strategy selection and decision-making). We present such a conceptual computational architecture based on principles of predictive processing and free energy minimization. Using this general model, we describe how a sense of control can form across the levels of a control hierarchy and how this can support action control in an unpredictable environment. We present an implementation of this model as well as first evaluations in a simulated task scenario, in which an autonomous agent has to cope with un-/predictable situations and experiences corresponding sense of control. We explore different model parameter settings that lead to different ways of combining low-level and high-level action control. The results show the importance of appropriately weighting information in situations where the need for low/high-level action control varies and they demonstrate how the sense of control can facilitate this.
Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity
Venue: arXiv cs.LG 2021
Year: 2021

Gradient descent ascent (GDA), the simplest single-loop algorithm for nonconvex minimax optimization, is widely used in practical applications such as generative adversarial networks (GANs) and adversarial training. Albeit its desirable simplicity, recent work shows inferior convergence rates of GDA in theory even assuming strong concavity of the objective on one side. This paper establishes new convergence results for two alternative single-loop algorithms -- alternating GDA and smoothed GDA -- under the mild assumption that the objective satisfies the Polyak-Lojasiewicz (PL) condition about one variable. We prove that, to find an $ε$-stationary point, (i) alternating GDA and its stochastic variant (without mini batch) respectively require $O(κ^{2} ε^{-2})$ and $O(κ^{4} ε^{-4})$ iterations, while (ii) smoothed GDA and its stochastic variant (without mini batch) respectively require $O(κε^{-2})$ and $O(κ^{2} ε^{-4})$ iterations. The latter greatly improves over the vanilla GDA and gives the hitherto best known complexity results among single-loop algorithms under similar settings. We further showcase the empirical efficiency of these algorithms in training GANs and robust nonlinear regression.