OpenRaiser/Intern-Atlas huggingface dataset:
Computing strong regular characteristic pairs with Groebner bases
Venue: arXiv cs.SC 2020
Year: 2020

The W-characteristic set of a polynomial ideal is the minimal triangular set contained in the reduced lexicographical Groebner basis of the ideal. A pair (G,C) of polynomial sets is a strong regular characteristic pair if G is a reduced lexicographical Groebner basis, C is the W-characteristic set of the ideal <G>, the saturated ideal sat(C) of C is equal to <G>, and C is regular. In this paper, we show that for any polynomial ideal I with given generators one can either detect that I is unit, or construct a strong regular characteristic pair (G,C) by computing Groebner bases such that I$\subseteq$sat(C)=<G> and sat(C) divides I, so the ideal I can be split into the saturated ideal sat(C) and the quotient ideal I:sat(C). Based on this strategy of splitting by means of quotient and with Groebner basis and ideal computations, we devise a simple algorithm to decompose an arbitrary polynomial set F into finitely many strong regular characteristic pairs, from which two representations for the zeros of F are obtained: one in terms of strong regular Groebner bases and the other in terms of regular triangular sets. We present some properties about strong regular characteristic pairs and characteristic decomposition and illustrate the proposed algorithm and its performance by examples and experimental results.
Efficient computation of counterfactual explanations of LVQ models
Venue: arXiv cs.LG 2020
Year: 2020

The increasing use of machine learning in practice and legal regulations like EU's GDPR cause the necessity to be able to explain the prediction and behavior of machine learning models. A prominent example of particularly intuitive explanations of AI models in the context of decision making are counterfactual explanations. Yet, it is still an open research problem how to efficiently compute counterfactual explanations for many models. We investigate how to efficiently compute counterfactual explanations for an important class of models, prototype-based classifiers such as learning vector quantization models. In particular, we derive specific convex and non-convex programs depending on the used metric.
Finding Dominating Induced Matchings in $P_9$-Free Graphs in Polynomial Time
Venue: arXiv cs.DM 2020
Year: 2020

Let $G=(V,E)$ be a finite undirected graph. An edge subset $E' \subseteq E$ is a {\em dominating induced matching} ({\em d.i.m.}) in $G$ if every edge in $E$ is intersected by exactly one edge of $E'$. The \emph{Dominating Induced Matching} (\emph{DIM}) problem asks for the existence of a d.i.m.\ in $G$. The DIM problem is \NP-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree 3 but was solved in linear time for $P_7$-free graphs and in polynomial time for $P_8$-free graphs. In this paper, we solve it in polynomial time for $P_9$-free graphs.
Cycle In Cycle Generative Adversarial Networks for Keypoint-Guided Image Generation
Venue: arXiv cs.CV 2020
Year: 2020

In this work, we propose a novel Cycle In Cycle Generative Adversarial Network (C$^2$GAN) for the task of keypoint-guided image generation. The proposed C$^2$GAN is a cross-modal framework exploring a joint exploitation of the keypoint and the image data in an interactive manner. C$^2$GAN contains two different types of generators, i.e., keypoint-oriented generator and image-oriented generator. Both of them are mutually connected in an end-to-end learnable fashion and explicitly form three cycled sub-networks, i.e., one image generation cycle and two keypoint generation cycles. Each cycle not only aims at reconstructing the input domain, and also produces useful output involving in the generation of another cycle. By so doing, the cycles constrain each other implicitly, which provides complementary information from the two different modalities and brings extra supervision across cycles, thus facilitating more robust optimization of the whole network. Extensive experimental results on two publicly available datasets, i.e., Radboud Faces and Market-1501, demonstrate that our approach is effective to generate more photo-realistic images compared with state-of-the-art models.
Linear Dynamics: Clustering without identification
Venue: arXiv cs.LG 2020
Year: 2020

Linear dynamical systems are a fundamental and powerful parametric model class. However, identifying the parameters of a linear dynamical system is a venerable task, permitting provably efficient solutions only in special cases. This work shows that the eigenspectrum of unknown linear dynamics can be identified without full system identification. We analyze a computationally efficient and provably convergent algorithm to estimate the eigenvalues of the state-transition matrix in a linear dynamical system. When applied to time series clustering, our algorithm can efficiently cluster multi-dimensional time series with temporal offsets and varying lengths, under the assumption that the time series are generated from linear dynamical systems. Evaluating our algorithm on both synthetic data and real electrocardiogram (ECG) signals, we see improvements in clustering quality over existing baselines.
Dueling Posterior Sampling for Preference-Based Reinforcement Learning
Venue: arXiv cs.LG 2020
Year: 2020

In preference-based reinforcement learning (RL), an agent interacts with the environment while receiving preferences instead of absolute feedback. While there is increasing research activity in preference-based RL, the design of formal frameworks that admit tractable theoretical analysis remains an open challenge. Building upon ideas from preference-based bandit learning and posterior sampling in RL, we present DUELING POSTERIOR SAMPLING (DPS), which employs preference-based posterior sampling to learn both the system dynamics and the underlying utility function that governs the preference feedback. As preference feedback is provided on trajectories rather than individual state-action pairs, we develop a Bayesian approach for the credit assignment problem, translating preferences to a posterior distribution over state-action reward models. We prove an asymptotic Bayesian no-regret rate for DPS with a Bayesian linear regression credit assignment model. This is the first regret guarantee for preference-based RL to our knowledge. We also discuss possible avenues for extending the proof methodology to other credit assignment models. Finally, we evaluate the approach empirically, showing competitive performance against existing baselines.
Minimum-Latency FEC Design with Delayed Feedback: Mathematical Modeling and Efficient Algorithms
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we consider the packet-level forward error correction (FEC) code design, without feedback or with delayed feedback, for achieving the minimum end-to-end latency, i.e., the latency between the time when packet is generated at the source and its \emph{in-order delivery} to the application layer of the destination. We first show that the minimum-latency FEC design problem can be modeled as a partially observable Markov decision process (POMDP), and hence the optimal code construction can be obtained by solving the corresponding POMDP. However, solving the POMDP optimally is in general difficult unless the size is very small. To this end, we propose an efficient heuristic algorithm, namely the majority vote policy, for obtaining a high quality approximate solution. We also derive the tight lower and upper bounds of the optimal state values of this POMDP, based on which a more sophisticated D-step search algorithm is implemented for obtaining near-optimal solutions. The simulation results show that the proposed code designs via solving the POMDP, either with the majority vote policy or the D-step search algorithm, strictly outperform the existing schemes, in both cases, without or with only delayed feedback.
Network Inference from Consensus Dynamics with Unknown Parameters
Venue: arXiv cs.SI 2020
Year: 2020

We explore the problem of inferring the graph Laplacian of a weighted, undirected network from snapshots of a single or multiple discrete-time consensus dynamics, subject to parameter uncertainty, taking place on the network. Specifically, we consider three problems in which we assume different levels of knowledge about the diffusion rates, observation times, and the input signal power of the dynamics. To solve these underdetermined problems, we propose a set of algorithms that leverage the spectral properties of the observed data and tools from convex optimization. Furthermore, we provide theoretical performance guarantees associated with these algorithms. We complement our theoretical work with numerical experiments, that demonstrate how our proposed methods outperform current state-of-the-art algorithms and showcase their effectiveness in recovering both synthetic and real-world networks.
BlurNet: Defense by Filtering the Feature Maps
Venue: arXiv cs.LG 2020
Year: 2020

Recently, the field of adversarial machine learning has been garnering attention by showing that state-of-the-art deep neural networks are vulnerable to adversarial examples, stemming from small perturbations being added to the input image. Adversarial examples are generated by a malicious adversary by obtaining access to the model parameters, such as gradient information, to alter the input or by attacking a substitute model and transferring those malicious examples over to attack the victim model. Specifically, one of these attack algorithms, Robust Physical Perturbations ($RP_2$), generates adversarial images of stop signs with black and white stickers to achieve high targeted misclassification rates against standard-architecture traffic sign classifiers. In this paper, we propose BlurNet, a defense against the $RP_2$ attack. First, we motivate the defense with a frequency analysis of the first layer feature maps of the network on the LISA dataset, which shows that high frequency noise is introduced into the input image by the $RP_2$ algorithm. To remove the high frequency noise, we introduce a depthwise convolution layer of standard blur kernels after the first layer. We perform a blackbox transfer attack to show that low-pass filtering the feature maps is more beneficial than filtering the input. We then present various regularization schemes to incorporate this low-pass filtering behavior into the training regime of the network and perform white-box attacks. We conclude with an adaptive attack evaluation to show that the success rate of the attack drops from 90\% to 20\% with total variation regularization, one of the proposed defenses.
A Verified Architecture for Proofs of Execution on Remote Devices under Full Software Compromise
Venue: arXiv cs.CR 2020
Year: 2020

Modern society is increasingly surrounded by, and accustomed to, a wide range of Cyber-Physical Systems (CPS), Internet-of-Things (IoT), and smart devices. They often perform safety-critical functions, e.g., personal medical devices, automotive CPS and industrial automation (smart factories). Some devices are small, cheap and specialized sensors and/or actuators. They tend to run simple software and operate under control of a more sophisticated central control unit. The latter is responsible for the decision-making and orchestrating the entire system. If devices are left unprotected, consequences of forged sensor readings or ignored actuation commands can be catastrophic, particularly, in safety-critical settings. This prompts the following three questions: (1) How to trust data produced by a simple remote embedded device? and (2) How to ascertain that this data was produced via execution of expected software? Furthermore, (3) Is it possible to attain (1) and (2) under the assumption that all software on the remote device could be modified or compromised? In this paper we answer these questions by designing, proving security of, and formally verifying, VAPE: Verified Architecture for Proofs of Execution. To the best of our knowledge, this is the first of its kind result for low-end embedded systems. Our work has a range of applications, especially, to authenticated sensing and trustworthy actuation, which are increasingly relevant in the context of safety-critical systems. VAPE architecture is publicly available and our evaluation demonstrates that it incurs low overhead, affordable even for lowest-end embedded devices, e.g., those based on MSP430 or ARV ATMega processors.
A Note on Colourings of Connected Oriented Cubic Graphs
Venue: arXiv cs.DM 2020
Year: 2020

In this note we show every orientation of a connected cubic graph admits an oriented 8-colouring. This lowers the best-known upper bound for the chromatic number of the family of orientations of connected cubic graphs. We further show that every such oriented graph admits a 2-dipath 7-colouring. These results imply that either the chromatic number for the family of oriented connected cubic graphs equals the 2-dipath chromatic number or the long-standing conjecture of Sopena [Journal of Graph Theory 25:191-205 1997] regarding the chromatic number of orientations of connected cubic graphs is false.
A VR System for Immersive Teleoperation and Live Exploration with a Mobile Robot
Venue: arXiv cs.HC 2020
Year: 2020

Applications like disaster management and industrial inspection often require experts to enter contaminated places. To circumvent the need for physical presence, it is desirable to generate a fully immersive individual live teleoperation experience. However, standard video-based approaches suffer from a limited degree of immersion and situation awareness due to the restriction to the camera view, which impacts the navigation. In this paper, we present a novel VR-based practical system for immersive robot teleoperation and scene exploration. While being operated through the scene, a robot captures RGB-D data that is streamed to a SLAM-based live multi-client telepresence system. Here, a global 3D model of the already captured scene parts is reconstructed and streamed to the individual remote user clients where the rendering for e.g. head-mounted display devices (HMDs) is performed. We introduce a novel lightweight robot client component which transmits robot-specific data and enables a quick integration into existing robotic systems. This way, in contrast to first-person exploration systems, the operators can explore and navigate in the remote site completely independent of the current position and view of the capturing robot, complementing traditional input devices for teleoperation. We provide a proof-of-concept implementation and demonstrate the capabilities as well as the performance of our system regarding interactive object measurements and bandwidth-efficient data streaming and visualization. Furthermore, we show its benefits over purely video-based teleoperation in a user study revealing a higher degree of situation awareness and a more precise navigation in challenging environments.
Semantic Estimation of 3D Body Shape and Pose using Minimal Cameras
Venue: arXiv cs.CV 2020
Year: 2020

We aim to simultaneously estimate the 3D articulated pose and high fidelity volumetric occupancy of human performance, from multiple viewpoint video (MVV) with as few as two views. We use a multi-channel symmetric 3D convolutional encoder-decoder with a dual loss to enforce the learning of a latent embedding that enables inference of skeletal joint positions and a volumetric reconstruction of the performance. The inference is regularised via a prior learned over a dataset of view-ablated multi-view video footage of a wide range of subjects and actions, and show this to generalise well across unseen subjects and actions. We demonstrate improved reconstruction accuracy and lower pose estimation error relative to prior work on two MVV performance capture datasets: Human 3.6M and TotalCapture.
Deep Density-aware Count Regressor
Venue: arXiv cs.CV 2020
Year: 2020

We seek to improve crowd counting as we perceive limits of currently prevalent density map estimation approach on both prediction accuracy and time efficiency. We leverage multilevel pixelation of density map as it helps improve SNR of training data and therefore, reduce prediction error. To achieve a better model, we introduce multilayer gradient fusion for training a density-aware global count regressor. More specifically, on training stage, a backbone network receives gradients from multiple branches to learn the density information, whereas those branches are to be detached to accelerate inference. By taking advantages of such method, our model improves benchmark results on public datasets and exhibits itself to be a new solution to crowd counting problems in practice.
Deep Kernel Learning for Clustering
Venue: arXiv cs.LG 2020
Year: 2020

We propose a deep learning approach for discovering kernels tailored to identifying clusters over sample data. Our neural network produces sample embeddings that are motivated by--and are at least as expressive as--spectral clustering. Our training objective, based on the Hilbert Schmidt Information Criterion, can be optimized via gradient adaptations on the Stiefel manifold, leading to significant acceleration over spectral methods relying on eigendecompositions. Finally, our trained embedding can be directly applied to out-of-sample data. We show experimentally that our approach outperforms several state-of-the-art deep clustering methods, as well as traditional approaches such as $k$-means and spectral clustering over a broad array of real-life and synthetic datasets.
Towards Online Observability-Aware Trajectory Optimization for Landmark-based Estimators
Venue: arXiv cs.RO 2020
Year: 2020

As autonomous systems increasingly rely on onboard sensing for localization and perception, the parallel tasks of motion planning and state estimation become more strongly coupled. This coupling is well-captured by augmenting the planning objective with a posterior-covariance penalty -- however, prediction of the estimator covariance is challenging when the observation model depends on unknown landmarks, as is the case in Simultaneous Localization and Mapping (SLAM). This paper addresses these challenges in the case of landmark- and SLAM-based estimators, enabling efficient prediction (and ultimately minimization) of this performance metric. First, we provide an interval-based filtering approximation of the SLAM inference process which allows for recursive propagation of the ego-covariance while avoiding the quadratic complexity of explicitly tracking landmark uncertainty. Secondly, we introduce a Lie-derivative measurement bundling scheme that simplifies the recursive "bundled" update, representing significant computational savings for high-rate sensors such as cameras. Finally, we identify a large class of measurement models (which includes orthographic camera projection) for which the contributions from each landmark can be directly combined, making evaluation of the information gained at each timestep (nearly) independent of the number of landmarks. This also enables the generalization from finite sets of landmarks $\{\ell^{(n)} \}$ to distributions, foregoing the need for fully-specified linearization points at planning time and allowing for new landmarks to be anticipated. Taken together, these contributions allow SLAM performance to be accurately and efficiently predicted, paving the way for online, observability-aware trajectory optimization in unknown space.
Robust Online Multi-target Visual Tracking using a HISP Filter with Discriminative Deep Appearance Learning
Venue: arXiv cs.CV 2020
Year: 2020

We propose a novel online multi-target visual tracker based on the recently developed Hypothesized and Independent Stochastic Population (HISP) filter. The HISP filter combines advantages of traditional tracking approaches like MHT and point-process-based approaches like PHD filter, and it has linear complexity while maintaining track identities. We apply this filter for tracking multiple targets in video sequences acquired under varying environmental conditions and targets density using a tracking-by-detection approach. We also adopt deep CNN appearance representation by training a verification-identification network (VerIdNet) on large-scale person re-identification data sets. We construct an augmented likelihood in a principled manner using this deep CNN appearance features and spatio-temporal information. Furthermore, we solve the problem of two or more targets having identical label considering the weight propagated with each confirmed hypothesis. Extensive experiments on MOT16 and MOT17 benchmark data sets show that our tracker significantly outperforms several state-of-the-art trackers in terms of tracking accuracy.
TAPER: Time-Aware Patient EHR Representation
Venue: arXiv cs.LG 2020
Year: 2020

Effective representation learning of electronic health records is a challenging task and is becoming more important as the availability of such data is becoming pervasive. The data contained in these records are irregular and contain multiple modalities such as notes, and medical codes. They are preempted by medical conditions the patient may have, and are typically jotted down by medical staff. Accompanying codes are notes containing valuable information about patients beyond the structured information contained in electronic health records. We use transformer networks and the recently proposed BERT language model to embed these data streams into a unified vector representation. The presented approach effectively encodes a patient's visit data into a single distributed representation, which can be used for downstream tasks. Our model demonstrates superior performance and generalization on mortality, readmission and length of stay tasks using the publicly available MIMIC-III ICU dataset. Code avaialble at https://github.com/sajaddarabi/TAPER-EHR
Mixture-based Multiple Imputation Model for Clinical Data with a Temporal Dimension
Venue: arXiv cs.LG 2020
Year: 2020

The problem of missing values in multivariable time series is a key challenge in many applications such as clinical data mining. Although many imputation methods show their effectiveness in many applications, few of them are designed to accommodate clinical multivariable time series. In this work, we propose a multiple imputation model that capture both cross-sectional information and temporal correlations. We integrate Gaussian processes with mixture models and introduce individualized mixing weights to handle the variance of predictive confidence of Gaussian process models. The proposed model is compared with several state-of-the-art imputation algorithms on both real-world and synthetic datasets. Experiments show that our best model can provide more accurate imputation than the benchmarks on all of our datasets.