OpenRaiser/Intern-Atlas huggingface dataset:
Circumscribing Polygons and Polygonizations for Disjoint Line Segments
Venue: arXiv cs.CG 2021
Year: 2021

Given a planar straight-line graph $G=(V,E)$ in $\mathbb{R}^2$, a \emph{circumscribing polygon} of $G$ is a simple polygon $P$ whose vertex set is $V$, and every edge in $E$ is either an edge or an internal diagonal of $P$. A circumscribing polygon is a \emph{polygonization} for $G$ if every edge in $E$ is an edge of $P$. We prove that every arrangement of $n$ disjoint line segments in the plane has a subset of size $Ω(\sqrt{n})$ that admits a circumscribing polygon, which is the first improvement on this bound in 20 years. We explore relations between circumscribing polygons and other problems in combinatorial geometry, and generalizations to $\mathbb{R}^3$. We show that it is NP-complete to decide whether a given graph $G$ admits a circumscribing polygon, even if $G$ is 2-regular. Settling a 30-year old conjecture by Rappaport, we also show that it is NP-complete to determine whether a geometric matching admits a polygonization.
Topology-based Representative Datasets to Reduce Neural Network Training Resources
Venue: arXiv cs.LG 2021
Year: 2021

One of the main drawbacks of the practical use of neural networks is the long time required in the training process. Such a training process consists of an iterative change of parameters trying to minimize a loss function. These changes are driven by a dataset, which can be seen as a set of labelled points in an n-dimensional space. In this paper, we explore the concept of are representative dataset which is a dataset smaller than the original one, satisfying a nearness condition independent of isometric transformations. Representativeness is measured using persistence diagrams (a computational topology tool) due to its computational efficiency. We prove that the accuracy of the learning process of a neural network on a representative dataset is "similar" to the accuracy on the original dataset when the neural network architecture is a perceptron and the loss function is the mean squared error. These theoretical results accompanied by experimentation open a door to reducing the size of the dataset to gain time in the training process of any neural network.
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs
Venue: arXiv cs.CC 2021
Year: 2021

We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surface-embedded graphs: the Shortest Cut Graph problem and the Multiway Cut problem. A cut graph of a graph $G$ embedded on a surface $S$ is a subgraph of $G$ whose removal from $S$ leaves a disk. We consider the problem of deciding whether an unweighted graph embedded on a surface of genus $g$ has a cut graph of length at most a given value. We prove a time lower bound for this problem of $n^{Ω(g/\log g)}$ conditionally to ETH. In other words, the first $n^{O(g)}$-time algorithm by Erickson and Har-Peled [SoCG 2002, Discr.\ Comput.\ Geom.\ 2004] is essentially optimal. We also prove that the problem is W[1]-hard when parameterized by the genus, answering a 17-year old question of these authors. A multiway cut of an undirected graph $G$ with $t$ distinguished vertices, called terminals, is a set of edges whose removal disconnects all pairs of terminals. We consider the problem of deciding whether an unweighted graph $G$ has a multiway cut of weight at most a given value. We prove a time lower bound for this problem of $n^{Ω(\sqrt{gt + g^2+t}/\log(g+t))}$, conditionally to ETH, for any choice of the genus $g\ge0$ of the graph and the number of terminals $t\ge4$. In other words, the algorithm by the second author [Algorithmica 2017] (for the more general multicut problem) is essentially optimal; this extends the lower bound by the third author [ICALP 2012] (for the planar case). Reductions to planar problems usually involve a grid-like structure. The main novel idea for our results is to understand what structures instead of grids are needed if we want to exploit optimally a certain value $g$ of the genus.
Symbolic Regression Methods for Reinforcement Learning
Venue: arXiv cs.LG 2021
Year: 2021

Reinforcement learning algorithms can solve dynamic decision-making and optimal control problems. With continuous-valued state and input variables, reinforcement learning algorithms must rely on function approximators to represent the value function and policy mappings. Commonly used numerical approximators, such as neural networks or basis function expansions, have two main drawbacks: they are black-box models offering little insight into the mappings learned, and they require extensive trial and error tuning of their hyper-parameters. In this paper, we propose a new approach to constructing smooth value functions in the form of analytic expressions by using symbolic regression. We introduce three off-line methods for finding value functions based on a state-transition model: symbolic value iteration, symbolic policy iteration, and a direct solution of the Bellman equation. The methods are illustrated on four nonlinear control problems: velocity control under friction, one-link and two-link pendulum swing-up, and magnetic manipulation. The results show that the value functions yield well-performing policies and are compact, mathematically tractable, and easy to plug into other algorithms. This makes them potentially suitable for further analysis of the closed-loop system. A comparison with an alternative approach using neural networks shows that our method outperforms the neural network-based one.
Unconstrained Facial Action Unit Detection via Latent Feature Domain
Venue: arXiv cs.CV 2021
Year: 2021

Facial action unit (AU) detection in the wild is a challenging problem, due to the unconstrained variability in facial appearances and the lack of accurate annotations. Most existing methods depend on either impractical labor-intensive labeling or inaccurate pseudo labels. In this paper, we propose an end-to-end unconstrained facial AU detection framework based on domain adaptation, which transfers accurate AU labels from a constrained source domain to an unconstrained target domain by exploiting labels of AU-related facial landmarks. Specifically, we map a source image with label and a target image without label into a latent feature domain by combining source landmark-related feature with target landmark-free feature. Due to the combination of source AU-related information and target AU-free information, the latent feature domain with transferred source label can be learned by maximizing the target-domain AU detection performance. Moreover, we introduce a novel landmark adversarial loss to disentangle the landmark-free feature from the landmark-related feature by treating the adversarial learning as a multi-player minimax game. Our framework can also be naturally extended for use with target-domain pseudo AU labels. Extensive experiments show that our method soundly outperforms lower-bounds and upper-bounds of the basic model, as well as state-of-the-art approaches on the challenging in-the-wild benchmarks. The code is available at https://github.com/ZhiwenShao/ADLD.
SLOPE for Sparse Linear Regression:Asymptotics and Optimal Regularization
Venue: arXiv cs.IT 2021
Year: 2021

In sparse linear regression, the SLOPE estimator generalizes LASSO by penalizing different coordinates of the estimate according to their magnitudes. In this paper, we present a precise performance characterization of SLOPE in the asymptotic regime where the number of unknown parameters grows in proportion to the number of observations. Our asymptotic characterization enables us to derive the fundamental limits of SLOPE in both estimation and variable selection settings. We also provide a computational feasible way to optimally design the regularizing sequences such that the fundamental limits are reached. In both settings, we show that the optimal design problem can be formulated as certain infinite-dimensional convex optimization problems, which have efficient and accurate finite-dimensional approximations. Numerical simulations verify all our asymptotic predictions. They demonstrate the superiority of our optimal regularizing sequences over other designs used in the existing literature.
Rank Reduction in Bimatrix Games
Venue: arXiv cs.GT 2021
Year: 2021

The rank of a bimatrix game is defined as the rank of the sum of the payoff matrices of the two players. The rank of a game is known to impact both the most suitable computation methods for determining a solution and the expressive power of the game. Under certain conditions on the payoff matrices, we devise a method that reduces the rank of the game without changing the equilibrium of the game. We leverage matrix pencil theory and the Wedderburn rank reduction formula to arrive at our results. We also present a constructive proof of the fact that in a generic square game, the rank of the game can be reduced by 1, and in generic rectangular game, the rank of the game can be reduced by 2 under certain assumptions.
Semantic Bilinear Pooling for Fine-Grained Recognition
Venue: arXiv cs.CV 2021
Year: 2021

Naturally, fine-grained recognition, e.g., vehicle identification or bird classification, has specific hierarchical labels, where fine categories are always harder to be classified than coarse categories. However, most of the recent deep learning based methods neglect the semantic structure of fine-grained objects and do not take advantage of the traditional fine-grained recognition techniques (e.g. coarse-to-fine classification). In this paper, we propose a novel framework with a two-branch network (coarse branch and fine branch), i.e., semantic bilinear pooling, for fine-grained recognition with a hierarchical label tree. This framework can adaptively learn the semantic information from the hierarchical levels. Specifically, we design a generalized cross-entropy loss for the training of the proposed framework to fully exploit the semantic priors via considering the relevance between adjacent levels and enlarge the distance between samples of different coarse classes. Furthermore, our method leverages only the fine branch when testing so that it adds no overhead to the testing time. Experimental results show that our proposed method achieves state-of-the-art performance on four public datasets.
"Won't We Fix this Issue?" Qualitative Characterization and Automated Identification of Wontfix Issues on GitHub
Venue: arXiv cs.SE 2021
Year: 2021

Context: Addressing user requests in the form of bug reports and Github issues represents a crucial task of any successful software project. However, user-submitted issue reports tend to widely differ in their quality, and developers spend a considerable amount of time handling them. Objective: By collecting a dataset of around 6,000 issues of 279 GitHub projects, we observe that developers take significant time (i.e., about five months, on average) before labeling an issue as a wontfix. For this reason, in this paper, we empirically investigate the nature of wontfix issues and methods to facilitate issue management process. Method: We first manually analyze a sample of 667 wontfix issues, extracted from heterogeneous projects, investigating the common reasons behind a "wontfix decision", the main characteristics of wontfix issues and the potential factors that could be connected with the time to close them. Furthermore, we experiment with approaches enabling the prediction of wontfix issues by analyzing the titles and descriptions of reported issues when submitted. Results and conclusion: Our investigation sheds some light on the wontfix issues' characteristics, as well as the potential factors that may affect the time required to make a "wontfix decision". Our results also demonstrate that it is possible to perform prediction of wontfix issues with high average values of precision, recall, and F-measure (90%-93%).
An Attentive Survey of Attention Models
Venue: arXiv cs.LG 2021
Year: 2021

Attention Model has now become an important concept in neural networks that has been researched within diverse application domains. This survey provides a structured and comprehensive overview of the developments in modeling attention. In particular, we propose a taxonomy which groups existing techniques into coherent categories. We review salient neural architectures in which attention has been incorporated, and discuss applications in which modeling attention has shown a significant impact. We also describe how attention has been used to improve the interpretability of neural networks. Finally, we discuss some future research directions in attention. We hope this survey will provide a succinct introduction to attention models and guide practitioners while developing approaches for their applications.
Center and Scale Prediction: Anchor-free Approach for Pedestrian and Face Detection
Venue: arXiv cs.CV 2021
Year: 2021

Object detection generally requires sliding-window classifiers in tradition or anchor box based predictions in modern deep learning approaches. However, either of these approaches requires tedious configurations in boxes. In this paper, we provide a new perspective where detecting objects is motivated as a high-level semantic feature detection task. Like edges, corners, blobs and other feature detectors, the proposed detector scans for feature points all over the image, for which the convolution is naturally suited. However, unlike these traditional low-level features, the proposed detector goes for a higher-level abstraction, that is, we are looking for central points where there are objects, and modern deep models are already capable of such a high-level semantic abstraction. Besides, like blob detection, we also predict the scales of the central points, which is also a straightforward convolution. Therefore, in this paper, pedestrian and face detection is simplified as a straightforward center and scale prediction task through convolutions. This way, the proposed method enjoys a box-free setting. Though structurally simple, it presents competitive accuracy on several challenging benchmarks, including pedestrian detection and face detection. Furthermore, a cross-dataset evaluation is performed, demonstrating a superior generalization ability of the proposed method. Code and models can be accessed at (https://github.com/liuwei16/CSP and https://github.com/hasanirtiza/Pedestron).
Deep CNN-Based Channel Estimation for mmWave Massive MIMO Systems
Venue: arXiv cs.IT 2021
Year: 2021

For millimeter wave (mmWave) massive multiple-input multiple-output (MIMO) systems, hybrid processing architecture is usually used to reduce the complexity and cost, which poses a very challenging issue in channel estimation. In this paper, deep convolutional neural network (CNN) is employed to address this problem. We first propose a spatial-frequency CNN (SF-CNN) based channel estimation exploiting both the spatial and frequency correlation, where the corrupted channel matrices at adjacent subcarriers are input into the CNN simultaneously. Then, exploiting the temporal correlation in time-varying channels, a spatial-frequency-temporal CNN (SFT-CNN) based approach is developed to further improve the accuracy. Moreover, we design a spatial pilot-reduced CNN (SPR-CNN) to save spatial pilot overhead for channel estimation, where channels in several successive coherence intervals are grouped and estimated by a channel estimation unit with memory. Numerical results show that the proposed SF-CNN and SFT-CNN based approaches outperform the non-ideal minimum mean-squared error (MMSE) estimator but with reduced complexity, and achieve the performance close to the ideal MMSE estimator that is very difficult to be implemented in practical situations. They are also robust to different propagation scenarios. The SPR-CNN based approach achieves comparable performance to SF-CNN and SFT-CNN based approaches while only requires about one third of spatial pilot overhead at the cost of complexity. Our work clearly shows that deep CNN can efficiently exploit channel correlation to improve the estimation performance for mmWave massive MIMO systems.
Unification and combination of a class of traversal strategies made with pattern matching and fixed-points
Venue: arXiv cs.LO 2021
Year: 2021

Motivated by an ongoing project on computer aided derivation of asymptotic models governed by partial differential equations, we introduce a class of term transformations that consists of traversal strategies and insertion of contexts. We define unification and combination operations on this class which amount to merging transformations in order to obtain more complex ones. We show that the unification and combination operations enjoy nice algebraic properties like associativity, congruence and the existence of neutral elements. The main part of this paper is devoted to proving that the unification and combination operations are correct.
Smart Buildings Enabled by 6G Communications
Venue: arXiv cs.NI 2021
Year: 2021

Smart building (SB), a promising solution to fast-paced and continuous urbanization around the world, includes the integration of a wide range of systems and services and involves the construction of multiple layers. SB is capable of sensing, acquiring, and processing a very large amount of data as well as performing appropriate actions and adaptation. Rapid increases in the number of connected nodes and thereby the data transmission demand of SB have led to conventional transmission and processing techniques becoming insufficient to provide satisfactory services. In order to enhance the intelligence of SBs and achieve efficient monitoring and control, sixth generation (6G) communication technologies, particularly indoor visible light communications (VLC) and machine learning (ML), are required to be incorporated in SBs. Herein, we envision a novel SB framework featuring a reliable data transmission network, powerful data processing, and reasoning abilities, all of which are enabled by 6G communications. Primary simulation results support the promising visions of the proposed SB framework.
Image Resizing by Reconstruction from Deep Features
Venue: arXiv cs.CV 2021
Year: 2021

Traditional image resizing methods usually work in pixel space and use various saliency measures. The challenge is to adjust the image shape while trying to preserve important content. In this paper we perform image resizing in feature space where the deep layers of a neural network contain rich important semantic information. We directly adjust the image feature maps, extracted from a pre-trained classification network, and reconstruct the resized image using a neural-network based optimization. This novel approach leverages the hierarchical encoding of the network, and in particular, the high-level discriminative power of its deeper layers, that recognizes semantic objects and regions and allows maintaining their aspect ratio. Our use of reconstruction from deep features diminishes the artifacts introduced by image-space resizing operators. We evaluate our method on benchmarks, compare to alternative approaches, and demonstrate its strength on challenging images.
The Shapley Value of Tuples in Query Answering
Venue: arXiv cs.DB 2021
Year: 2021

We investigate the application of the Shapley value to quantifying the contribution of a tuple to a query answer. The Shapley value is a widely known numerical measure in cooperative game theory and in many applications of game theory for assessing the contribution of a player to a coalition game. It has been established already in the 1950s, and is theoretically justified by being the very single wealth-distribution measure that satisfies some natural axioms. While this value has been investigated in several areas, it received little attention in data management. We study this measure in the context of conjunctive and aggregate queries by defining corresponding coalition games. We provide algorithmic and complexity-theoretic results on the computation of Shapley-based contributions to query answers; and for the hard cases we present approximation algorithms.
Compositionality of Rewriting Rules with Conditions
Venue: arXiv cs.LO 2021
Year: 2021

We extend the notion of compositional associative rewriting as recently studied in the rule algebra framework literature to the setting of rewriting rules with conditions. Our methodology is category-theoretical in nature, where the definition of rule composition operations encodes the non-deterministic sequential concurrent application of rules in Double-Pushout (DPO) and Sesqui-Pushout (SqPO) rewriting with application conditions based upon $\mathcal{M}$-adhesive categories. We uncover an intricate interplay between the category-theoretical concepts of conditions on rules and morphisms, the compositionality and compatibility of certain shift and transport constructions for conditions, and thirdly the property of associativity of the composition of rules.
CleanML: A Study for Evaluating the Impact of Data Cleaning on ML Classification Tasks
Venue: arXiv cs.DB 2021
Year: 2021

Data quality affects machine learning (ML) model performances, and data scientists spend considerable amount of time on data cleaning before model training. However, to date, there does not exist a rigorous study on how exactly cleaning affects ML -- ML community usually focuses on developing ML algorithms that are robust to some particular noise types of certain distributions, while database (DB) community has been mostly studying the problem of data cleaning alone without considering how data is consumed by downstream ML analytics. We propose a CleanML study that systematically investigates the impact of data cleaning on ML classification tasks. The open-source and extensible CleanML study currently includes 14 real-world datasets with real errors, five common error types, seven different ML models, and multiple cleaning algorithms for each error type (including both commonly used algorithms in practice as well as state-of-the-art solutions in academic literature). We control the randomness in ML experiments using statistical hypothesis testing, and we also control false discovery rate in our experiments using the Benjamini-Yekutieli (BY) procedure. We analyze the results in a systematic way to derive many interesting and nontrivial observations. We also put forward multiple research directions for researchers.
Privacy-Preserving Smart Parking System Using Blockchain and Private Information Retrieval
Venue: arXiv cs.CR 2021
Year: 2021

Searching for available parking spaces is a major problem for drivers especially in big crowded cities, causing traffic congestion and air pollution, and wasting drivers' time. Smart parking systems are a novel solution to enable drivers to have real-time parking information for pre-booking. However, current smart parking requires drivers to disclose their private information, such as desired destinations. Moreover, the existing schemes are centralized and vulnerable to the bottleneck of the single point of failure and data breaches. In this paper, we propose a distributed privacy-preserving smart parking system using blockchain. A consortium blockchain created by different parking lot owners to ensure security, transparency, and availability is proposed to store their parking offers on the blockchain. To preserve drivers' location privacy, we adopt a private information retrieval (PIR) technique to enable drivers to retrieve parking offers from blockchain nodes privately, without revealing which parking offers are retrieved. Furthermore, a short randomizable signature is used to enable drivers to reserve available parking slots in an anonymous manner. Besides, we introduce an anonymous payment system that cannot link drivers' to specific parking locations. Finally, our performance evaluations demonstrate that the proposed scheme can preserve drivers' privacy with low communication and computation overhead.