OpenRaiser/Intern-Atlas huggingface dataset:
CPG graphs: Some structural and hardness results
Venue: arXiv cs.CG 2020
Year: 2020

In this paper we continue the systematic study of Contact graphs of Paths on a Grid (CPG graphs) initiated in [Deniz et al., 2018]. A CPG graph is a graph for which there exists a collection of pairwise interiorly disjoint paths on a grid in one-to-one correspondence with its vertex set such that two vertices are adjacent if and only if the corresponding paths touch at a grid-point. If every such path has at most $k$ bends for some $k \geq 0$, the graph is said to be $B_k$-CPG. We first show that, for any $k \geq 0$, the class of $B_k$-CPG graphs is strictly contained in the class of $B_{k+1}$-CPG graphs even within the class of planar graphs, thus implying that there exists no $k \geq 0$ such that every planar CPG graph is $B_k$-CPG. The main result of the paper is that recognizing CPG graphs and $B_k$-CPG graphs with $k \geq 1$ is $\mathsf{NP}$-complete. Moreover, we show that the same remains true even within the class of planar graphs in the case $k \geq 3$. We then consider several graph problems restricted to CPG graphs and show, in particular, that Independent Set and Clique Cover remain $\mathsf{NP}$-hard for $B_0$-CPG graphs. Finally, we consider the related classes $B_k$-EPG of edge-intersection graphs of paths with at most $k$ bends on a grid. Although it is possible to optimally color a $B_0$-EPG graph in polynomial time, as this class coincides with that of interval graphs, we show that, in contrast, 3-Colorability is $\mathsf{NP}$-complete for $B_1$-EPG graphs.
Lempel-Ziv-like Parsing in Small Space
Venue: arXiv cs.DS 2020
Year: 2020

Lempel-Ziv (LZ77 or, briefly, LZ) is one of the most effective and widely-used compressors for repetitive texts. However, the existing efficient methods computing the exact LZ parsing have to use linear or close to linear space to index the input text during the construction of the parsing, which is prohibitive for long inputs. An alternative is Relative Lempel-Ziv (RLZ), which indexes only a fixed reference sequence, whose size can be controlled. Deriving the reference sequence by sampling the text yields reasonable compression ratios for RLZ, but performance is not always competitive with that of LZ and depends heavily on the similarity of the reference to the text. In this paper we introduce ReLZ, a technique that uses RLZ as a preprocessor to approximate the LZ parsing using little memory. RLZ is first used to produce a sequence of phrases, and these are regarded as metasymbols that are input to LZ for a second-level parsing on a (most often) drastically shorter sequence. This parsing is finally translated into one on the original sequence. We analyze the new scheme and prove that, like LZ, it achieves the $k$th order empirical entropy compression $n H_k + o(n\logσ)$ with $k = o(\log_σn)$, where $n$ is the input length and $σ$ is the alphabet size. In fact, we prove this entropy bound not only for ReLZ but for a wide class of LZ-like encodings. Then, we establish a lower bound on ReLZ approximation ratio showing that the number of phrases in it can be $Ω(\log n)$ times larger than the number of phrases in LZ. Our experiments show that ReLZ is faster than existing alternatives to compute the (exact or approximate) LZ parsing, at the reasonable price of an approximation factor below $2.0$ in all tested scenarios, and sometimes below $1.05$, to the size of LZ.
Explaining Anomalies Detected by Autoencoders Using SHAP
Venue: arXiv cs.LG 2020
Year: 2020

Anomaly detection algorithms are often thought to be limited because they don't facilitate the process of validating results performed by domain experts. In Contrast, deep learning algorithms for anomaly detection, such as autoencoders, point out the outliers, saving experts the time-consuming task of examining normal cases in order to find anomalies. Most outlier detection algorithms output a score for each instance in the database. The top-k most intense outliers are returned to the user for further inspection; however the manual validation of results becomes challenging without additional clues. An explanation of why an instance is anomalous enables the experts to focus their investigation on most important anomalies and may increase their trust in the algorithm. Recently, a game theory-based framework known as SHapley Additive exPlanations (SHAP) has been shown to be effective in explaining various supervised learning models. In this research, we extend SHAP to explain anomalies detected by an autoencoder, an unsupervised model. The proposed method extracts and visually depicts both the features that most contributed to the anomaly and those that offset it. A preliminary experimental study using real world data demonstrates the usefulness of the proposed method in assisting the domain experts to understand the anomaly and filtering out the uninteresting anomalies, aiming at minimizing the false positive rate of detected anomalies.
Spectral Method for Phase Retrieval: an Expectation Propagation Perspective
Venue: arXiv cs.IT 2020
Year: 2020

Phase retrieval refers to the problem of recovering a signal $\mathbf{x}_{\star}\in\mathbb{C}^n$ from its phaseless measurements $y_i=|\mathbf{a}_i^{\mathrm{H}}\mathbf{x}_{\star}|$, where $\{\mathbf{a}_i\}_{i=1}^m$ are the measurement vectors. Many popular phase retrieval algorithms are based on the following two-step procedure: (i) initialize the algorithm based on a spectral method, (ii) refine the initial estimate by a local search algorithm (e.g., gradient descent). The quality of the spectral initialization step can have a major impact on the performance of the overall algorithm. In this paper, we focus on the model where the measurement matrix $\mathbf{A}=[\mathbf{a}_1,\ldots,\mathbf{a}_m]^{\mathrm{H}}$ has orthonormal columns, and study the spectral initialization under the asymptotic setting $m,n\to\infty$ with $m/n\toδ\in(1,\infty)$. We use the expectation propagation framework to characterize the performance of spectral initialization for Haar distributed matrices. Our numerical results confirm that the predictions of the EP method are accurate for not-only Haar distributed matrices, but also for realistic Fourier based models (e.g. the coded diffraction model). The main findings of this paper are the following: (1) There exists a threshold on $δ$ (denoted as $δ_{\mathrm{weak}}$) below which the spectral method cannot produce a meaningful estimate. We show that $δ_{\mathrm{weak}}=2$ for the column-orthonormal model. In contrast, previous results by Mondelli and Montanari show that $δ_{\mathrm{weak}}=1$ for the i.i.d. Gaussian model. (2) The optimal design for the spectral method coincides with that for the i.i.d. Gaussian model, where the latter was recently introduced by Luo, Alghamdi and Lu.
Design of A Two-point Steering Path Planner Using Geometric Control
Venue: arXiv cs.RO 2020
Year: 2020

For lateral vehicle dynamics, planning trajectories for lane-keeping and lane-change can be generalized as a path planning task to stabilize a vehicle onto a target lane, which is a fundamental element in nowadays autonomous driving systems. On the other hand, two-point steering for lane-change and lane-keeping has been investigated by researchers from psychology as a sensorimotor mechanism of human drivers. In the first part of this paper, using knowledge of geometric control, we will first design a path planner which satisfies five design objectives: generalization for different vehicle models, convergence to the target lane, optimality, safety in lane-change maneuver and low computational complexity. Later, based on this path planner, a two-point steering path planner will be proposed and it will be proved rigorously that this two-point steering path planner possesses the advantage--steering radius of the planned trajectory is smaller than the intrinsic radius of reference line of the target lane. This advantage is also described as "corner-cutting" in driving. The smaller driving radius of the trajectory will result in higher vehicle speed along the winding roads and more comfortness for the passengers.
Analysis of Spectral Methods for Phase Retrieval with Random Orthogonal Matrices
Venue: arXiv cs.IT 2020
Year: 2020

Phase retrieval refers to algorithmic methods for recovering a signal from its phaseless measurements. Local search algorithms that work directly on the non-convex formulation of the problem have been very popular recently. Due to the nonconvexity of the problem, the success of these local search algorithms depends heavily on their starting points. The most widely used initialization scheme is the spectral method, in which the leading eigenvector of a data-dependent matrix is used as a starting point. Recently, the performance of the spectral initialization was characterized accurately for measurement matrices with independent and identically distributed entries. This paper aims to obtain the same level of knowledge for isotropically random column-orthogonal matrices, which are substantially better models for practical phase retrieval systems. Towards this goal, we consider the asymptotic setting in which the number of measurements $m$, and the dimension of the signal, $n$, diverge to infinity with $m/n = δ\in(1,\infty)$, and obtain a simple expression for the overlap between the spectral estimator and the true signal vector.
Individual Preference Aware Caching Policy Design in Wireless D2D Networks
Venue: arXiv cs.NI 2020
Year: 2020

Cache-aided wireless device-to-device (D2D) networks allow significant throughput increase, depending on the concentration of the popularity distribution of files. Many studies assume that all users have the same preference distribution; however, this may not be true in practice. This work investigates whether and how the information about individual preferences can benefit cache-aided D2D networks. We examine a clustered network and derive a network utility that considers both the user distribution and channel fading effects into the analysis. We also formulate a utility maximization problem for designing caching policies. This maximization problem can be applied to optimize several important quantities, including throughput, energy efficiency (EE), cost, and hit-rate, and to solve different tradeoff problems. We provide a general approach that can solve the proposed problem under the assumption that users coordinate, then prove that the proposed approach can obtain the stationary point under a mild assumption. Using simulations of practical setups, we show that performance can improve significantly with proper exploitation of individual preferences. We also show that different types of tradeoffs exist between different performance metrics and that they can be managed through caching policy and cooperation distance designs.
Multiview 2D/3D Rigid Registration via a Point-Of-Interest Network for Tracking and Triangulation ($\text{POINT}^2$)
Venue: arXiv cs.CV 2020
Year: 2020

We propose to tackle the problem of multiview 2D/3D rigid registration for intervention via a Point-Of-Interest Network for Tracking and Triangulation ($\text{POINT}^2$). $\text{POINT}^2$ learns to establish 2D point-to-point correspondences between the pre- and intra-intervention images by tracking a set of random POIs. The 3D pose of the pre-intervention volume is then estimated through a triangulation layer. In $\text{POINT}^2$, the unified framework of the POI tracker and the triangulation layer enables learning informative 2D features and estimating 3D pose jointly. In contrast to existing approaches, $\text{POINT}^2$ only requires a single forward-pass to achieve a reliable 2D/3D registration. As the POI tracker is shift-invariant, $\text{POINT}^2$ is more robust to the initial pose of the 3D pre-intervention image. Extensive experiments on a large-scale clinical cone-beam CT (CBCT) dataset show that the proposed $\text{POINT}^2$ method outperforms the existing learning-based method in terms of accuracy, robustness and running time. Furthermore, when used as an initial pose estimator, our method also improves the robustness and speed of the state-of-the-art optimization-based approaches by ten folds.
Multinomial Random Forest: Toward Consistency and Privacy-Preservation
Venue: arXiv cs.LG 2020
Year: 2020

Despite the impressive performance of random forests (RF), its theoretical properties have not been thoroughly understood. In this paper, we propose a novel RF framework, dubbed multinomial random forest (MRF), to analyze the \emph{consistency} and \emph{privacy-preservation}. Instead of deterministic greedy split rule or with simple randomness, the MRF adopts two impurity-based multinomial distributions to randomly select a split feature and a split value respectively. Theoretically, we prove the consistency of the proposed MRF and analyze its privacy-preservation within the framework of differential privacy. We also demonstrate with multiple datasets that its performance is on par with the standard RF. To the best of our knowledge, MRF is the first consistent RF variant that has comparable performance to the standard RF.
Zero-Shot Autonomous Vehicle Policy Transfer: From Simulation to Real-World via Adversarial Learning
Venue: arXiv cs.SY 2020
Year: 2020

In this article, we demonstrate a zero-shot transfer of an autonomous driving policy from simulation to University of Delaware's scaled smart city with adversarial multi-agent reinforcement learning, in which an adversary attempts to decrease the net reward by perturbing both the inputs and outputs of the autonomous vehicles during training. We train the autonomous vehicles to coordinate with each other while crossing a roundabout in the presence of an adversary in simulation. The adversarial policy successfully reproduces the simulated behavior and incidentally outperforms, in terms of travel time, both a human-driving baseline and adversary-free trained policies. Finally, we demonstrate that the addition of adversarial training considerably improves the performance \eat{stability and robustness} of the policies after transfer to the real world compared to Gaussian noise injection.
Channel Estimation and Hybrid Precoding for Distributed Phased Arrays Based MIMO Wireless Communications
Venue: arXiv cs.IT 2020
Year: 2020

Distributed phased arrays based multiple-input multiple-output (DPA-MIMO) is a newly introduced architecture that enables both spatial multiplexing and beamforming while facilitating highly reconfigurable hardware implementation in millimeter-wave (mmWave) frequency bands. With a DPA-MIMO system, we focus on channel state information (CSI) acquisition and hybrid precoding. As benefited from a coordinated and open-loop pilot beam pattern design, all the sub-arrays can perform channel sounding with less training overhead compared with the traditional orthogonal operation of each sub-array. Furthermore, two sparse channel recovery algorithms, known as joint orthogonal matching pursuit (JOMP) and joint sparse Bayesian learning with $\ell_2$ reweighting (JSBL-$\ell_2$), are proposed to exploit the hidden structured sparsity in the beam-domain channel vector. Finally, successive interference cancellation (SIC) based hybrid precoding through sub-array grouping is illustrated for the DPA-MIMO system, which decomposes the joint sub-array RF beamformer design into an interactive per-sub-array-group handle. Simulation results show that the proposed two channel estimators fully take advantage of the partial coupling characteristic of DPA-MIMO channels to perform channel recovery, and the proposed hybrid precoding algorithm is suitable for such array-of-sub-arrays architecture with satisfactory performance and low complexity.
On the Complexity of the k-Level in Arrangements of Pseudoplanes
Venue: arXiv cs.CG 2020
Year: 2020

A classical open problem in combinatorial geometry is to obtain tight asymptotic bounds on the maximum number of k-level vertices in an arrangement of n hyperplanes in d dimensions (vertices with exactly k of the hyperplanes passing below them). This is a dual version of the k-set problem, which, in a primal setting, seeks bounds for the maximum number of k-sets determined by n points in d dimensions, where a k-set is a subset of size k that can be separated from its complement by a hyperplane. The k-set problem is still wide open even in the plane, with a substantial gap between the best known upper and lower bounds. The gap gets larger as the dimension grows. In three dimensions, the best known upper bound is O(nk^(3/2)). In its dual version, the problem can be generalized by replacing hyperplanes by other families of surfaces (or curves in the planes). Reasonably sharp bounds have been obtained for curves in the plane, but the known upper bounds are rather weak for more general surfaces, already in three dimensions, except for the case of triangles. The best known general bound, due to Chan is O(n^2.997), for families of surfaces that satisfy certain (fairly weak) properties. In this paper we consider the case of pseudoplanes in 3 dimensions (defined in detail in the introduction), and establish the upper bound O(nk^(5/3)) for the number of k-level vertices in an arrangement of n pseudoplanes. The bound is obtained by establishing suitable (and nontrivial) extensions of dual versions of classical tools that have been used in studying the primal k-set problem, such as the Lova'sz Lemma and the Crossing Lemma.
Neutron: An Implementation of the Transformer Translation Model and its Variants
Venue: arXiv cs.CL 2020
Year: 2020

The Transformer translation model is easier to parallelize and provides better performance compared to recurrent seq2seq models, which makes it popular among industry and research community. We implement the Neutron in this work, including the Transformer model and its several variants from most recent researches. It is highly optimized, easy to modify and provides comparable performance with interesting features while keeping readability.
A Lightweight Optical Flow CNN - Revisiting Data Fidelity and Regularization
Venue: arXiv cs.CV 2020
Year: 2020

Over four decades, the majority addresses the problem of optical flow estimation using variational methods. With the advance of machine learning, some recent works have attempted to address the problem using convolutional neural network (CNN) and have showed promising results. FlowNet2, the state-of-the-art CNN, requires over 160M parameters to achieve accurate flow estimation. Our LiteFlowNet2 outperforms FlowNet2 on Sintel and KITTI benchmarks, while being 25.3 times smaller in the model size and 3.1 times faster in the running speed. LiteFlowNet2 is built on the foundation laid by conventional methods and resembles the corresponding roles as data fidelity and regularization in variational methods. We compute optical flow in a spatial-pyramid formulation as SPyNet but through a novel lightweight cascaded flow inference. It provides high flow estimation accuracy through early correction with seamless incorporation of descriptor matching. Flow regularization is used to ameliorate the issue of outliers and vague flow boundaries through feature-driven local convolutions. Our network also owns an effective structure for pyramidal feature extraction and embraces feature warping rather than image warping as practiced in FlowNet2 and SPyNet. Comparing to LiteFlowNet, LiteFlowNet2 improves the optical flow accuracy on Sintel Clean by 23.3%, Sintel Final by 12.8%, KITTI 2012 by 19.6%, and KITTI 2015 by 18.8%, while being 2.2 times faster. Our network protocol and trained models are made publicly available on https://github.com/twhui/LiteFlowNet2.
A Truthful Cardinal Mechanism for One-Sided Matching
Venue: arXiv cs.GT 2020
Year: 2020

We revisit the well-studied problem of designing mechanisms for one-sided matching markets, where a set of $n$ agents needs to be matched to a set of $n$ heterogeneous items. Each agent $i$ has a value $v_{i,j}$ for each item $j$, and these values are private information that the agents may misreport if doing so leads to a preferred outcome. Ensuring that the agents have no incentive to misreport requires a careful design of the matching mechanism, and mechanisms proposed in the literature mitigate this issue by eliciting only the \emph{ordinal} preferences of the agents, i.e., their ranking of the items from most to least preferred. However, the efficiency guarantees of these mechanisms are based only on weak measures that are oblivious to the underlying values. In this paper we achieve stronger performance guarantees by introducing a mechanism that truthfully elicits the full \emph{cardinal} preferences of the agents, i.e., all of the $v_{i,j}$ values. We evaluate the performance of this mechanism using the much more demanding Nash bargaining solution as a benchmark, and we prove that our mechanism significantly outperforms all ordinal mechanisms (even non-truthful ones). To prove our approximation bounds, we also study the population monotonicity of the Nash bargaining solution in the context of matching markets, providing both upper and lower bounds which are of independent interest.
Fisher Discriminative Least Squares Regression for Image Classification
Venue: arXiv cs.CV 2020
Year: 2020

Discriminative least squares regression (DLSR) has been shown to achieve promising performance in multi-class image classification tasks. Its key idea is to force the regression labels of different classes to move in opposite directions by means of the proposed the joint use of the $ε$-draggings technique, yielding discriminative regression model exhibiting wider margins, and the Fisher criterion. The $ε$-draggings technique ignores an important problem: its non-negative relaxation matrix is dynamically updated in optimization, which means the dragging values can also cause the labels from the same class to be uncorrelated. In order to learn a more powerful discriminative projection, as well as regression labels, we propose a Fisher regularized DLSR (FDLSR) framework by constraining the relaxed labels using the Fisher criterion. On one hand, the Fisher criterion improves the intra-class compactness of the relaxed labels during relaxation learning. On the other hand, it is expected further to enhance the inter-class separability of $ε$-draggings technique. FDLSR for the first time ever attempts to integrate the Fisher discriminant criterion and $ε$-draggings technique into one unified model because they are absolutely complementary in learning discriminative projection. Extensive experiments on various datasets demonstrate that the proposed FDLSR method achieves performance that is superior to other state-of-the-art classification methods. The Matlab codes of this paper are available at https://github.com/chenzhe207/FDLSR.
Class-incremental Learning via Deep Model Consolidation
Venue: arXiv cs.CV 2020
Year: 2020

Deep neural networks (DNNs) often suffer from "catastrophic forgetting" during incremental learning (IL) --- an abrupt degradation of performance on the original set of classes when the training objective is adapted to a newly added set of classes. Existing IL approaches tend to produce a model that is biased towards either the old classes or new classes, unless with the help of exemplars of the old data. To address this issue, we propose a class-incremental learning paradigm called Deep Model Consolidation (DMC), which works well even when the original training data is not available. The idea is to first train a separate model only for the new classes, and then combine the two individual models trained on data of two distinct set of classes (old classes and new classes) via a novel double distillation training objective. The two existing models are consolidated by exploiting publicly available unlabeled auxiliary data. This overcomes the potential difficulties due to the unavailability of original training data. Compared to the state-of-the-art techniques, DMC demonstrates significantly better performance in image classification (CIFAR-100 and CUB-200) and object detection (PASCAL VOC 2007) in the single-headed IL setting.