OpenRaiser/Intern-Atlas huggingface dataset:
An Algorithm for Computing a Minimal Comprehensive Gröbner\, Basis of a Parametric Polynomial System
Venue: arXiv cs.SC 2020
Year: 2020

An algorithm to generate a minimal comprehensive Gröbner\, basis of a parametric polynomial system from an arbitrary faithful comprehensive Gröbner\, system is presented. A basis of a parametric polynomial ideal is a comprehensive Gröbner\, basis if and only if for every specialization of parameters in a given field, the specialization of the basis is a Gröbner\, basis of the associated specialized polynomial ideal. The key idea used in ensuring minimality is that of a polynomial being essential with respect to a comprehensive Gröbner\, basis. The essentiality check is performed by determining whether a polynomial can be covered for various specializations by other polynomials in the associated branches in a comprehensive Gröbner\, system. The algorithm has been implemented and successfully tried on many examples from the literature.
Maximizing Influence-based Group Shapley Centrality
Venue: arXiv cs.GT 2020
Year: 2020

One key problem in network analysis is the so-called influence maximization problem, which consists in finding a set $S$ of at most $k$ seed users, in a social network, maximizing the spread of information from $S$. This paper studies a related but slightly different problem: We want to find a set $S$ of at most $k$ seed users that maximizes the spread of information, when $S$ is added to an already pre-existing - but unknown - set of seed users $T$. We consider such scenario to be very realistic. Assume a central entity wants to spread a piece of news, while having a budget to influence $k$ users. This central authority may know that some users are already aware of the information and are going to spread it anyhow. The identity of these users being however completely unknown. We model this optimization problem using the Group Shapley value, a well-founded concept from cooperative game theory. While the standard influence maximization problem is easy to approximate within a factor $1-1/e-ε$ for any $ε>0$, assuming common computational complexity conjectures, we obtain strong hardness of approximation results for the problem at hand in this paper. Maybe most prominently, we show that it cannot be approximated within $1/n^{o(1)}$ under the Gap Exponential Time Hypothesis. Hence, it is unlikely to achieve anything better than a polynomial factor approximation. Nevertheless, we show that a greedy algorithm can achieve a factor of $\frac{1-1/e}{k}-ε$ for any $ε>0$, showing that not all is lost in settings where $k$ is bounded.
Accelerated ADMM based Trajectory Optimization for Legged Locomotion with Coupled Rigid Body Dynamics
Venue: arXiv cs.RO 2020
Year: 2020

Trajectory optimization is becoming increasingly powerful in addressing motion planning problems of underactuated robotic systems. Numerous prior studies solve such a class of large non-convex optimal control problems in a hierarchical fashion. However, numerical accuracy issues are prone to occur when one uses a full-order model to track reference trajectories generated from a reduced-order model. This study investigates an approach of Alternating Direction Method of Multipliers (ADMM) and proposes a new splitting scheme for legged locomotion problems. Rigid body dynamics constraints and other general constraints such as box and cone constraints are decomposed to multiple sub-problems in a principled manner. The resulting multi-block ADMM framework enables us to leverage the efficiency of an unconstrained optimization method--Differential Dynamical Programming--to iteratively solve the optimizations using centroidal and whole-body models. Furthermore, we propose a Stage-wise Accelerated ADMM with over-relaxation and varying-penalty schemes to improve the overall convergence rate. We evaluate and validate the performance of the proposed ADMM algorithm on a car-parking example and a bipedal locomotion problem over rough terrains.
Capsule GAN Using Capsule Network for Generator Architecture
Venue: arXiv cs.CV 2020
Year: 2020

This paper presents Capsule GAN, a Generative adversarial network using Capsule Network not only in the discriminator but also in the generator. Recently, Generative adversarial networks (GANs) has been intensively studied. However, generating images by GANs is difficult. Therefore, GANs sometimes generate poor quality images. These GANs use convolutional neural networks (CNNs). However, CNNs have the defect that the relational information between features of the image may be lost. Capsule Network, proposed by Hinton in 2017, overcomes the defect of CNNs. Capsule GAN reported previously uses Capsule Network in the discriminator. However, instead of using Capsule Network, Capsule GAN reported in previous studies uses CNNs in generator architecture like DCGAN. This paper introduces two approaches to use Capsule Network in the generator. One is to use DigitCaps layer from the discriminator as the input to the generator. DigitCaps layer is the output layer of Capsule Network. It has the features of the input images of the discriminator. The other is to use the reverse operation of recognition process in Capsule Network in the generator. We compare Capsule GAN proposed in this paper with conventional GAN using CNN and Capsule GAN which uses Capsule Network in the discriminator only. The datasets are MNIST, Fashion-MNIST and color images. We show that Capsule GAN outperforms the GAN using CNN and the GAN using Capsule Network in the discriminator only. The architecture of Capsule GAN proposed in this paper is a basic architecture using Capsule Network. Therefore, we can apply the existing improvement techniques for GANs to Capsule GAN.
Speeding up Linear Programming using Randomized Linear Algebra
Venue: arXiv cs.DS 2020
Year: 2020

Linear programming (LP) is an extremely useful tool and has been successfully applied to solve various problems in a wide range of areas, including operations research, engineering, economics, or even more abstract mathematical areas such as combinatorics. It is also used in many machine learning applications, such as $\ell_1$-regularized SVMs, basis pursuit, nonnegative matrix factorization, etc. Interior Point Methods (IPMs) are one of the most popular methods to solve LPs both in theory and in practice. Their underlying complexity is dominated by the cost of solving a system of linear equations at each iteration. In this paper, we consider \emph{infeasible} IPMs for the special case where the number of variables is much larger than the number of constraints. Using tools from Randomized Linear Algebra, we present a preconditioning technique that, when combined with the Conjugate Gradient iterative solver, provably guarantees that infeasible IPM algorithms (suitably modified to account for the error incurred by the approximate solver), converge to a feasible, approximately optimal solution, without increasing their iteration complexity. Our empirical evaluations verify our theoretical results on both real-world and synthetic data.
Efficient improper learning for online logistic regression
Venue: arXiv cs.LG 2020
Year: 2020

We consider the setting of online logistic regression and consider the regret with respect to the 2-ball of radius B. It is known (see [Hazan et al., 2014]) that any proper algorithm which has logarithmic regret in the number of samples (denoted n) necessarily suffers an exponential multiplicative constant in B. In this work, we design an efficient improper algorithm that avoids this exponential constant while preserving a logarithmic regret. Indeed, [Foster et al., 2018] showed that the lower bound does not apply to improper algorithms and proposed a strategy based on exponential weights with prohibitive computational complexity. Our new algorithm based on regularized empirical risk minimization with surrogate losses satisfies a regret scaling as O(B log(Bn)) with a per-round time-complexity of order O(d^2).
Multi-dimensional Skyline Query to Find Best Shopping Mall for Customers
Venue: arXiv cs.DB 2020
Year: 2020

This paper presents a new application for multi-dimensional Skyline query. The idea presented in this paper can be used to find best shopping malls based on users requirements. A web-based application was used to simulate the problem and proposed solution. Also, a mathematical definition was developed to define the problem and show how multi-dimensional Skyline query can be used to solve complex problems, such as, finding shopping malls using multiple different criteria. The idea of this paper can be used in other fields, where different criteria should be considered.
Toronto-3D: A Large-scale Mobile LiDAR Dataset for Semantic Segmentation of Urban Roadways
Venue: arXiv cs.CV 2020
Year: 2020

Semantic segmentation of large-scale outdoor point clouds is essential for urban scene understanding in various applications, especially autonomous driving and urban high-definition (HD) mapping. With rapid developments of mobile laser scanning (MLS) systems, massive point clouds are available for scene understanding, but publicly accessible large-scale labeled datasets, which are essential for developing learning-based methods, are still limited. This paper introduces Toronto-3D, a large-scale urban outdoor point cloud dataset acquired by a MLS system in Toronto, Canada for semantic segmentation. This dataset covers approximately 1 km of point clouds and consists of about 78.3 million points with 8 labeled object classes. Baseline experiments for semantic segmentation were conducted and the results confirmed the capability of this dataset to train deep learning models effectively. Toronto-3D is released to encourage new research, and the labels will be improved and updated with feedback from the research community.
Particle robots A new specie of hybrid bio-inspired robotics
Venue: arXiv cs.RO 2020
Year: 2020

Inspired by a couple of simple organisms without eyes, neither ears. This paper presents a novel hybrid bionic robot, called "particle robot", which mix a macro-organism and a micro-organism in the same robot. On one hand, an interesting rather boring animal, the biological Echinoids (sea urchins) is mixed with the viruses micro-organisms, in specific the rotaviruses; together with spherical mobile robots. Analogously, from a pure robotic perspective, this bio-inspired robot can be seen as a spherical mobile robot wearing an actuated exoskeleton. The robot has two main configurations: when the spines are contracted it becomes a spherical mobile robot able to move in a fast pace on land, embedding all spherical mobile robots properties. On the other hand, when the spines or legs are extended in a controlled pattern, it can walk on flat surfaces as well as move on snow and over rocks as a bionic sea urchin. The spines of the robot are telescopic linear actuators, which combines soft and hard 3D print materials to make the actuation unit flexible for compressing it in minimal space and rigid for lifting the robot.
Interpretable Deep Recurrent Neural Networks via Unfolding Reweighted $\ell_1$-$\ell_1$ Minimization: Architecture Design and Generalization Analysis
Venue: arXiv cs.LG 2020
Year: 2020

Deep unfolding methods---for example, the learned iterative shrinkage thresholding algorithm (LISTA)---design deep neural networks as learned variations of optimization methods. These networks have been shown to achieve faster convergence and higher accuracy than the original optimization methods. In this line of research, this paper develops a novel deep recurrent neural network (coined reweighted-RNN) by the unfolding of a reweighted $\ell_1$-$\ell_1$ minimization algorithm and applies it to the task of sequential signal reconstruction. To the best of our knowledge, this is the first deep unfolding method that explores reweighted minimization. Due to the underlying reweighted minimization model, our RNN has a different soft-thresholding function (alias, different activation functions) for each hidden unit in each layer. Furthermore, it has higher network expressivity than existing deep unfolding RNN models due to the over-parameterizing weights. Importantly, we establish theoretical generalization error bounds for the proposed reweighted-RNN model by means of Rademacher complexity. The bounds reveal that the parameterization of the proposed reweighted-RNN ensures good generalization. We apply the proposed reweighted-RNN to the problem of video frame reconstruction from low-dimensional measurements, that is, sequential frame reconstruction. The experimental results on the moving MNIST dataset demonstrate that the proposed deep reweighted-RNN significantly outperforms existing RNN models.
Constraint Solving with Deep Learning for Symbolic Execution
Venue: arXiv cs.SE 2020
Year: 2020

Symbolic execution is a powerful systematic software analysis technique, but suffers from the high cost of constraint solving, which is the key supporting technology that affects the effectiveness of symbolic execution. Techniques like Green and GreenTrie reuse constraint solutions to speed up constraint solving for symbolic execution; however, these reuse techniques require syntactic/semantic equivalence or implication relationship between constraints. This paper introduces DeepSover, a novel approach to constraint solving with deep learning for symbolic execution. Our key insight is to utilize the collective knowledge of a set of constraint solutions to train a deep neural network, which is then used to classify path conditions for their satisfiability during symbolic execution. Experimental evaluation shows DeepSolver is highly accurate in classifying path conditions, is more efficient than state-of-the-art constraint solving and constraint solution reuse techniques, and can well support symbolic execution tasks.
Inverting the Pose Forecasting Pipeline with SPF2: Sequential Pointcloud Forecasting for Sequential Pose Forecasting
Venue: arXiv cs.CV 2020
Year: 2020

Many autonomous systems forecast aspects of the future in order to aid decision-making. For example, self-driving vehicles and robotic manipulation systems often forecast future object poses by first detecting and tracking objects. However, this detect-then-forecast pipeline is expensive to scale, as pose forecasting algorithms typically require labeled sequences of object poses, which are costly to obtain in 3D space. Can we scale performance without requiring additional labels? We hypothesize yes, and propose inverting the detect-then-forecast pipeline. Instead of detecting, tracking and then forecasting the objects, we propose to first forecast 3D sensor data (e.g., point clouds with $100$k points) and then detect/track objects on the predicted point cloud sequences to obtain future poses, i.e., a forecast-then-detect pipeline. This inversion makes it less expensive to scale pose forecasting, as the sensor data forecasting task requires no labels. Part of this work's focus is on the challenging first step -- Sequential Pointcloud Forecasting (SPF), for which we also propose an effective approach, SPFNet. To compare our forecast-then-detect pipeline relative to the detect-then-forecast pipeline, we propose an evaluation procedure and two metrics. Through experiments on a robotic manipulation dataset and two driving datasets, we show that SPFNet is effective for the SPF task, our forecast-then-detect pipeline outperforms the detect-then-forecast approaches to which we compared, and that pose forecasting performance improves with the addition of unlabeled data.
TTTTTackling WinoGrande Schemas
Venue: arXiv cs.CL 2020
Year: 2020

We applied the T5 sequence-to-sequence model to tackle the AI2 WinoGrande Challenge by decomposing each example into two input text strings, each containing a hypothesis, and using the probabilities assigned to the "entailment" token as a score of the hypothesis. Our first (and only) submission to the official leaderboard yielded 0.7673 AUC on March 13, 2020, which is the best known result at this time and beats the previous state of the art by over five points.
Unsupervised Hierarchical Graph Representation Learning by Mutual Information Maximization
Venue: arXiv cs.LG 2020
Year: 2020

Graph representation learning based on graph neural networks (GNNs) can greatly improve the performance of downstream tasks, such as node and graph classification. However, the general GNN models do not aggregate node information in a hierarchical manner, and can miss key higher-order structural features of many graphs. The hierarchical aggregation also enables the graph representations to be explainable. In addition, supervised graph representation learning requires labeled data, which is expensive and error-prone. To address these issues, we present an unsupervised graph representation learning method, Unsupervised Hierarchical Graph Representation (UHGR), which can generate hierarchical representations of graphs. Our method focuses on maximizing mutual information between "local" and high-level "global" representations, which enables us to learn the node embeddings and graph embeddings without any labeled data. To demonstrate the effectiveness of the proposed method, we perform the node and graph classification using the learned node and graph embeddings. The results show that the proposed method achieves comparable results to state-of-the-art supervised methods on several benchmarks. In addition, our visualization of hierarchical representations indicates that our method can capture meaningful and interpretable clusters.
Progress Extrapolating Algorithmic Learning to Arbitrary Sequence Lengths
Venue: arXiv cs.LG 2020
Year: 2020

Recent neural network models for algorithmic tasks have led to significant improvements in extrapolation to sequences much longer than training, but it remains an outstanding problem that the performance still degrades for very long or adversarial sequences. We present alternative architectures and loss-terms to address these issues, and our testing of these approaches has not detected any remaining extrapolation errors within memory constraints. We focus on linear time algorithmic tasks including copy, parentheses parsing, and binary addition. First, activation binning was used to discretize the trained network in order to avoid computational drift from continuous operations, and a binning-based digital loss term was added to encourage discretizable representations. In addition, a localized differentiable memory (LDM) architecture, in contrast to distributed memory access, addressed remaining extrapolation errors and avoided unbounded growth of internal computational states. Previous work has found that algorithmic extrapolation issues can also be alleviated with approaches relying on program traces, but the current effort does not rely on such traces.
Gaze-Sensing LEDs for Head Mounted Displays
Venue: arXiv cs.CV 2020
Year: 2020

We introduce a new gaze tracker for Head Mounted Displays (HMDs). We modify two off-the-shelf HMDs to be gaze-aware using Light Emitting Diodes (LEDs). Our key contribution is to exploit the sensing capability of LEDs to create low-power gaze tracker for virtual reality (VR) applications. This yields a simple approach using minimal hardware to achieve good accuracy and low latency using light-weight supervised Gaussian Process Regression (GPR) running on a mobile device. With our hardware, we show that Minkowski distance measure based GPR implementation outperforms the commonly used radial basis function-based support vector regression (SVR) without the need to precisely determine free parameters. We show that our gaze estimation method does not require complex dimension reduction techniques, feature extraction, or distortion corrections due to off-axis optical paths. We demonstrate two complete HMD prototypes with a sample eye-tracked application, and report on a series of subjective tests using our prototypes.
On Broadcasting Time in the Model of Travelling Agents
Venue: arXiv cs.SI 2020
Year: 2020

Consider the following broadcasting process run on a connected graph $G=(V,E)$. Suppose that $k \ge 2$ agents start on vertices selected from $V$ uniformly and independently at random. One of the agents has a message that she wants to communicate to the other agents. All agents perform independent random walks on $G$, with the message being passed when an agent that knows the message meets an agent that does not know the message. The broadcasting time $ξ(G,k)$ is the time it takes to spread the message to all agents. Our ultimate goal is to gain a better understanding of the broadcasting process run on real-world networks of roads of large cities that might shed some light on the behaviour of future autonomous and connected vehicles. Due to the complexity of road networks, such phenomena have to be studied using simulation in practical applications. In this paper, we study the process on the simplest scenario, i.e., the family of complete graphs, as in this case the problem is analytically tractable. We provide tight bounds for $ξ(K_n,k)$ that hold asymptotically almost surely for the whole range of the parameter $k$. These theoretical results reveal interesting relationships and, at the same time, are also helpful to understand and explain the behaviour we observe in more realistic networks.
Quality Control of Neuron Reconstruction Based on Deep Learning
Venue: arXiv cs.CV 2020
Year: 2020

Neuron reconstruction is essential to generate exquisite neuron connectivity map for understanding brain function. Despite the significant amount of effect that has been made on automatic reconstruction methods, manual tracing by well-trained human annotators is still necessary. To ensure the quality of reconstructed neurons and provide guidance for annotators to improve their efficiency, we propose a deep learning based quality control method for neuron reconstruction in this paper. By formulating the quality control problem into a binary classification task regarding each single point, the proposed approach overcomes the technical difficulties resulting from the large image size and complex neuron morphology. Not only it provides the evaluation of reconstruction quality, but also can locate exactly where the wrong tracing begins. This work presents one of the first comprehensive studies for whole-brain scale quality control of neuron reconstructions. Experiments on five-fold cross validation with a large dataset demonstrate that the proposed approach can detect 74.7% errors with only 1.4% false alerts.
AQPDBJUT Dataset: Picture-Based PM Monitoring in the Campus of BJUT
Venue: arXiv cs.CV 2020
Year: 2020

Ensuring the students in good physical levels is imperative for their future health. In recent years, the continually growing concentration of Particulate Matter (PM) has done increasingly serious harm to student health. Hence, it is highly required to prevent and control PM concentrations in the campus. As the source of PM prevention and control, developing a good model for PM monitoring is extremely urgent and has posed a big challenge. It has been found in prior works that photobased methods are available for PM monitoring. To verify the effectiveness of existing PM monitoring methods in the campus, we establish a new dataset which includes 1,500 photos collected in the Beijing University of Technology. Experiments show that stated-of-the-art methods are far from ideal for PM monitoring in the campus.