OpenRaiser/Intern-Atlas huggingface dataset:
Deciding twin-width at most 4 is NP-complete
Venue: arXiv cs.CC 2021
Year: 2021

We show that determining if an $n$-vertex graph has twin-width at most 4 is NP-complete, and requires time $2^{Ω(n/\log n)}$ unless the Exponential-Time Hypothesis fails. Along the way, we give an elementary proof that $n$-vertex graphs subdivided at least $2 \log n$ times have twin-width at most 4. We also show how to encode trigraphs $H$ (2-edge colored graphs involved in the definition of twin-width) into graphs $G$, in the sense that every $d$-sequence (sequence of vertex contractions witnessing that the twin-width is at most $d$) of $G$ inevitably creates $H$ as an induced subtrigraph, whereas there exists a partial $d$-sequence that actually goes from $G$ to $H$. We believe that these facts and their proofs can be of independent interest.
Joint Analog and Digital Transceiver Design for Wideband Full Duplex MIMO Systems
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we propose a wideband Full Duplex (FD) Multiple-Input Multiple-Output (MIMO) communication system comprising of an FD MIMO node simultaneously communicating with two multi-antenna UpLink (UL) and DownLink (DL) nodes utilizing the same time and frequency resources. To suppress the strong Self-Interference (SI) signal due to simultaneous transmission and reception in FD MIMO systems, we propose a joint design of Analog and Digital (A/D) cancellation as well as transmit and receive beamforming capitalizing on baseband Orthogonal Frequency-Division Multiplexing (OFDM) signal modeling. Considering practical transmitter impairments, we present a multi-tap wideband analog canceller architecture whose number of taps does not scale with the number of transceiver antennas and multipath SI components. We also propose a novel adaptive digital cancellation based on truncated singular value decomposition that reduces the residual SI signal estimation parameters. To maximize the FD sum rate, a joint optimization framework is presented for A/D cancellation and digital beamforming. Finally, our extensive waveform simulation results demonstrate that the proposed wideband FD MIMO design exhibits higher SI cancellation capability with reduced complexity compared to existing cancellation techniques, resulting in improved achievable rate performance.
Effective Rate of RIS-aided Networks with Location and Phase Estimation Uncertainty
Venue: arXiv cs.IT 2021
Year: 2021

Reconfigurable Intelligent Surfaces (RIS) are planar structures connected to electronic circuitry, which can be employed to steer the electromagnetic signals in a controlled manner. Through this, the signal quality and the effective data rate can be substantially improved. While the benefits of RIS-assisted wireless communications have been investigated for various scenarios, some aspects of the network design, such as coverage, optimal placement of RIS, etc., often require complex optimization and numerical simulations, since the achievable effective rate is difficult to predict. This problem becomes even more difficult in the presence of phase estimation errors or location uncertainty, which can lead to substantial performance degradation if neglected. Considering randomly distributed receivers within a ring-shaped RIS-assisted wireless network, this paper mainly investigates the effective rate by taking into account the above-mentioned impairments. Furthermore, exact closed-form expressions for the effective rate are derived in terms of Meijer's $G$-function, which (i) reveals that the location and phase estimation uncertainty should be well considered in the deployment of RIS in wireless networks; and (ii) facilitates future network design and performance prediction.
Anti-Tamper Radio: System-Level Tamper Detection for Computing Systems
Venue: arXiv cs.CR 2021
Year: 2021

A whole range of attacks becomes possible when adversaries gain physical access to computing systems that process or contain sensitive data. Examples include side-channel analysis, bus probing, device cloning, or implanting hardware Trojans. Defending against these kinds of attacks is considered a challenging endeavor, requiring anti-tamper solutions to monitor the physical environment of the system. Current solutions range from simple switches, which detect if a case is opened, to meshes of conducting material that provide more fine-grained detection of integrity violations. However, these solutions suffer from an intricate trade-off between physical security on the one side and reliability, cost, and difficulty to manufacture on the other. In this work, we demonstrate that radio wave propagation in an enclosed system of complex geometry is sensitive against adversarial physical manipulation. We present an anti-tamper radio (ATR) solution as a method for tamper detection, which combines high detection sensitivity and reliability with ease-of-use. ATR constantly monitors the wireless signal propagation behavior within the boundaries of a metal case. Tamper attempts such as insertion of foreign objects, will alter the observed radio signal response, subsequently raising an alarm. The ATR principle is applicable in many computing systems that require physical security such as servers, ATMs, and smart meters. As a case study, we use 19" servers and thoroughly investigate capabilities and limits of the ATR. Using a custom-built automated probing station, we simulate probing attacks by inserting needles with high precision into protected environments. Our experimental results show that our ATR implementation can detect 16 mm insertions of needles of diameter as low as 0.1 mm under ideal conditions. In the more realistic environment of a running 19" server, we demonstrate reliable [...]
Deep Reinforcement Learning Policies Learn Shared Adversarial Features Across MDPs
Venue: arXiv cs.LG 2021
Year: 2021

The use of deep neural networks as function approximators has led to striking progress for reinforcement learning algorithms and applications. Yet the knowledge we have on decision boundary geometry and the loss landscape of neural policies is still quite limited. In this paper we propose a framework to investigate the decision boundary and loss landscape similarities across states and across MDPs. We conduct experiments in various games from Arcade Learning Environment, and discover that high sensitivity directions for neural policies are correlated across MDPs. We argue that these high sensitivity directions support the hypothesis that non-robust features are shared across training environments of reinforcement learning agents. We believe our results reveal fundamental properties of the environments used in deep reinforcement learning training, and represent a tangible step towards building robust and reliable deep reinforcement learning agents.
Non-Gaussian Component Analysis via Lattice Basis Reduction
Venue: arXiv cs.DS 2021
Year: 2021

Non-Gaussian Component Analysis (NGCA) is the following distribution learning problem: Given i.i.d. samples from a distribution on $\mathbb{R}^d$ that is non-gaussian in a hidden direction $v$ and an independent standard Gaussian in the orthogonal directions, the goal is to approximate the hidden direction $v$. Prior work \cite{DKS17-sq} provided formal evidence for the existence of an information-computation tradeoff for NGCA under appropriate moment-matching conditions on the univariate non-gaussian distribution $A$. The latter result does not apply when the distribution $A$ is discrete. A natural question is whether information-computation tradeoffs persist in this setting. In this paper, we answer this question in the negative by obtaining a sample and computationally efficient algorithm for NGCA in the regime that $A$ is discrete or nearly discrete, in a well-defined technical sense. The key tool leveraged in our algorithm is the LLL method \cite{LLL82} for lattice basis reduction.
Decoupling and Recoupling Spatiotemporal Representation for RGB-D-based Motion Recognition
Venue: arXiv cs.CV 2021
Year: 2021

Decoupling spatiotemporal representation refers to decomposing the spatial and temporal features into dimension-independent factors. Although previous RGB-D-based motion recognition methods have achieved promising performance through the tightly coupled multi-modal spatiotemporal representation, they still suffer from (i) optimization difficulty under small data setting due to the tightly spatiotemporal-entangled modeling;(ii) information redundancy as it usually contains lots of marginal information that is weakly relevant to classification; and (iii) low interaction between multi-modal spatiotemporal information caused by insufficient late fusion. To alleviate these drawbacks, we propose to decouple and recouple spatiotemporal representation for RGB-D-based motion recognition. Specifically, we disentangle the task of learning spatiotemporal representation into 3 sub-tasks: (1) Learning high-quality and dimension independent features through a decoupled spatial and temporal modeling network. (2) Recoupling the decoupled representation to establish stronger space-time dependency. (3) Introducing a Cross-modal Adaptive Posterior Fusion (CAPF) mechanism to capture cross-modal spatiotemporal information from RGB-D data. Seamless combination of these novel designs forms a robust spatialtemporal representation and achieves better performance than state-of-the-art methods on four public motion datasets. Our code is available at https://github.com/damo-cv/MotionRGBD.
Causal Modeling With Infinitely Many Variables
Venue: arXiv cs.AI 2021
Year: 2021

Structural-equations models (SEMs) are perhaps the most commonly used framework for modeling causality. However, as we show, naively extending this framework to infinitely many variables, which is necessary, for example, to model dynamical systems, runs into several problems. We introduce GSEMs (generalized SEMs), a flexible generalization of SEMs that directly specify the results of interventions, in which (1) systems of differential equations can be represented in a natural and intuitive manner, (2) certain natural situations, which cannot be represented by SEMs at all, can be represented easily, (3) the definition of actual causality in SEMs carries over essentially without change.
Intermittent Deployment for Large-Scale Multi-Robot Forage Perception: Data Synthesis, Prediction, and Planning
Venue: arXiv cs.RO 2021
Year: 2021

Monitoring the health and vigor of grasslands is vital for informing management decisions to optimize rotational grazing in agriculture applications. To take advantage of forage resources and improve land productivity, we require knowledge of pastureland growth patterns that is simply unavailable at state of the art. In this paper, we propose to deploy a team of robots to monitor the evolution of an unknown pastureland environment to fulfill the above goal. To monitor such an environment, which usually evolves slowly, we need to design a strategy for rapid assessment of the environment over large areas at a low cost. Thus, we propose an integrated pipeline comprising of data synthesis, deep neural network training and prediction along with a multi-robot deployment algorithm that monitors pasturelands intermittently. Specifically, using expert-informed agricultural data coupled with novel data synthesis in ROS Gazebo, we first propose a new neural network architecture to learn the spatiotemporal dynamics of the environment. Such predictions help us to understand pastureland growth patterns on large scales and make appropriate monitoring decisions for the future. Based on our predictions, we then design an intermittent multi-robot deployment policy for low-cost monitoring. Finally, we compare the proposed pipeline with other methods, from data synthesis to prediction and planning, to corroborate our pipeline's performance.
Automated stability testing of elastic rods with helical centerlines using a robotic system
Venue: arXiv cs.RO 2021
Year: 2021

Experimental analysis of the mechanics of a deformable object, and particularly its stability, requires repetitive testing and, depending on the complexity of the object's shape, a testing setup that can manipulate many degrees of freedom at the object's boundary. Motivated by recent advancements in robotic manipulation of deformable objects, this paper addresses these challenges by constructing a method for automated stability testing of a slender elastic rod -- a canonical example of a deformable object -- using a robotic system. We focus on rod configurations with helical centerlines since the stability of a helical rod can be described using only three parameters, but experimentally determining the stability requires manipulation of both the position and orientation at one end of the rod, which is not possible using traditional experimental methods that only actuate a limited number of degrees of freedom. Using a recent geometric characterization of stability for helical rods, we construct and implement a manipulation scheme to explore the space of stable helices, and we use a vision system to detect the onset of instabilities within this space. The experimental results obtained by our automated testing system show good agreement with numerical simulations of elastic rods in helical configurations. The methods described in this paper lay the groundwork for automation to grow within the field of experimental mechanics.
About a Proof Pearl: A Purported Solution to a POPLMARK Challenge Problem that is Not One
Venue: arXiv cs.LO 2021
Year: 2021

The POPLMARK Challenge comprises a set of problems intended to measure the strength of reasoning systems in the realm of mechanizing programming language meta-theory at the time the challenge was enunciated. Included in the collection is the exercise of demonstrating transitivity of subtyping for a specific algorithmic formulation of subtyping for an extension of System F. The challenge represented by this problem derives from the fact that, for the given formulation, subtyping must be proved simultaneously with another property called narrowing. In a paper published as a proof pearl, Brigitte Pientka claimed to have presented a solution to the problem in which "the full power of parametric and higher-order judgments" is exploited to "get the narrowing lemma for free." We show this claim to be inaccurate. In particular, we show that the simplification is in substantial part the result of changing the formulation of the subtyping relation in a way that modifies the challenge rather than the outcome of the manner in which the argument is mechanized.
Overview of the HASOC Subtrack at FIRE 2021: Hate Speech and Offensive Content Identification in English and Indo-Aryan Languages
Venue: arXiv cs.CL 2021
Year: 2021

The widespread of offensive content online such as hate speech poses a growing societal problem. AI tools are necessary for supporting the moderation process at online platforms. For the evaluation of these identification tools, continuous experimentation with data sets in different languages are necessary. The HASOC track (Hate Speech and Offensive Content Identification) is dedicated to develop benchmark data for this purpose. This paper presents the HASOC subtrack for English, Hindi, and Marathi. The data set was assembled from Twitter. This subtrack has two sub-tasks. Task A is a binary classification problem (Hate and Not Offensive) offered for all three languages. Task B is a fine-grained classification problem for three classes (HATE) Hate speech, OFFENSIVE and PROFANITY offered for English and Hindi. Overall, 652 runs were submitted by 65 teams. The performance of the best classification algorithms for task A are F1 measures 0.91, 0.78 and 0.83 for Marathi, Hindi and English, respectively. This overview presents the tasks and the data development as well as the detailed results. The systems submitted to the competition applied a variety of technologies. The best performing algorithms were mainly variants of transformer architectures.
Optimal discharge of patients from intensive care via a data-driven policy learning framework
Venue: arXiv cs.LG 2021
Year: 2021

Clinical decision support tools rooted in machine learning and optimization can provide significant value to healthcare providers, including through better management of intensive care units. In particular, it is important that the patient discharge task addresses the nuanced trade-off between decreasing a patient's length of stay (and associated hospitalization costs) and the risk of readmission or even death following the discharge decision. This work introduces an end-to-end general framework for capturing this trade-off to recommend optimal discharge timing decisions given a patient's electronic health records. A data-driven approach is used to derive a parsimonious, discrete state space representation that captures a patient's physiological condition. Based on this model and a given cost function, an infinite-horizon discounted Markov decision process is formulated and solved numerically to compute an optimal discharge policy, whose value is assessed using off-policy evaluation strategies. Extensive numerical experiments are performed to validate the proposed framework using real-life intensive care unit patient data.
Deep Bayesian Learning for Car Hacking Detection
Venue: arXiv cs.CR 2021
Year: 2021

With the rise of self-drive cars and connected vehicles, cars are equipped with various devices to assistant the drivers or support self-drive systems. Undoubtedly, cars have become more intelligent as we can deploy more and more devices and software on the cars. Accordingly, the security of assistant and self-drive systems in the cars becomes a life-threatening issue as smart cars can be invaded by malicious attacks that cause traffic accidents. Currently, canonical machine learning and deep learning methods are extensively employed in car hacking detection. However, machine learning and deep learning methods can easily be overconfident and defeated by carefully designed adversarial examples. Moreover, those methods cannot provide explanations for security engineers for further analysis. In this work, we investigated Deep Bayesian Learning models to detect and analyze car hacking behaviors. The Bayesian learning methods can capture the uncertainty of the data and avoid overconfident issues. Moreover, the Bayesian models can provide more information to support the prediction results that can help security engineers further identify the attacks. We have compared our model with deep learning models and the results show the advantages of our proposed model. The code of this work is publicly available
Interpreting Audiograms with Multi-stage Neural Networks
Venue: arXiv cs.CV 2021
Year: 2021

Audiograms are a particular type of line charts representing individuals' hearing level at various frequencies. They are used by audiologists to diagnose hearing loss, and further select and tune appropriate hearing aids for customers. There have been several projects such as Autoaudio that aim to accelerate this process through means of machine learning. But all existing models at their best can only detect audiograms in images and classify them into general categories. They are unable to extract hearing level information from detected audiograms by interpreting the marks, axis, and lines. To address this issue, we propose a Multi-stage Audiogram Interpretation Network (MAIN) that directly reads hearing level data from photos of audiograms. We also established Open Audiogram, an open dataset of audiogram images with annotations of marks and axes on which we trained and evaluated our proposed model. Experiments show that our model is feasible and reliable.
Scenario-Based Safety Assessment Framework for Automated Vehicles
Venue: arXiv cs.RO 2021
Year: 2021

Automated vehicles (AVs) are expected to increase traffic safety and traffic efficiency, among others by enabling flexible mobility-on-demand systems. This is particularly important in Singapore, being one of the world's most densely populated countries, which is why the Singaporean authorities are currently actively facilitating the deployment of AVs. As a consequence, however, the need arises for a formal AV road approval procedure. To this end, a safety assessment framework is proposed, which combines aspects of the standardized functional safety design methodology with a traffic scenario-based approach. The latter involves using driving data to extract AV-relevant traffic scenarios. The underlying approach is based on decomposition of scenarios into elementary events, subsequent scenario parametrization, and sampling of the estimated probability density functions of the scenario parameters to create test scenarios. The resulting test scenarios are subsequently employed for virtual testing in a simulation environment and physical testing on a proving ground and in real life. As a result, the proposed assessment pipeline thus provides statistically relevant and quantitative measures for the AV performance in a relatively short time frame due to the simulation-based approach. Ultimately, the proposed methodology provides authorities with a formal road approval procedure for AVs. In particular, the proposed methodology will support the Singaporean Land Transport Authority for road approval of AVs.
SuperStyleNet: Deep Image Synthesis with Superpixel Based Style Encoder
Venue: arXiv cs.CV 2021
Year: 2021

Existing methods for image synthesis utilized a style encoder based on stacks of convolutions and pooling layers to generate style codes from input images. However, the encoded vectors do not necessarily contain local information of the corresponding images since small-scale objects are tended to "wash away" through such downscaling procedures. In this paper, we propose deep image synthesis with superpixel based style encoder, named as SuperStyleNet. First, we directly extract the style codes from the original image based on superpixels to consider local objects. Second, we recover spatial relationships in vectorized style codes based on graphical analysis. Thus, the proposed network achieves high-quality image synthesis by mapping the style codes into semantic labels. Experimental results show that the proposed method outperforms state-of-the-art ones in terms of visual quality and quantitative measurements. Furthermore, we achieve elaborate spatial style editing by adjusting style codes.
SiamTrans: Zero-Shot Multi-Frame Image Restoration with Pre-Trained Siamese Transformers
Venue: arXiv cs.CV 2021
Year: 2021

We propose a novel zero-shot multi-frame image restoration method for removing unwanted obstruction elements (such as rains, snow, and moire patterns) that vary in successive frames. It has three stages: transformer pre-training, zero-shot restoration, and hard patch refinement. Using the pre-trained transformers, our model is able to tell the motion difference between the true image information and the obstructing elements. For zero-shot image restoration, we design a novel model, termed SiamTrans, which is constructed by Siamese transformers, encoders, and decoders. Each transformer has a temporal attention layer and several self-attention layers, to capture both temporal and spatial information of multiple frames. Only pre-trained (self-supervised) on the denoising task, SiamTrans is tested on three different low-level vision tasks (deraining, demoireing, and desnowing). Compared with related methods, ours achieves the best performances, even outperforming those with supervised learning.