OpenRaiser/Intern-Atlas huggingface dataset:
Graph Width Measures for CNF-Encodings with Auxiliary Variables
Venue: arXiv cs.CC 2020
Year: 2020

We consider bounded width CNF-formulas where the width is measured by popular graph width measures on graphs associated to CNF-formulas. Such restricted graph classes, in particular those of bounded treewidth, have been extensively studied for their uses in the design of algorithms for various computational problems on CNF-formulas. Here we consider the expressivity of these formulas in the model of clausal encodings with auxiliary variables. We first show that bounding the width for many of the measures from the literature leads to a dramatic loss of expressivity, restricting the formulas to such of low communication complexity. We then show that the width of optimal encodings with respect to different measures is strongly linked: there are two classes of width measures, one containing primal treewidth and the other incidence cliquewidth, such that in each class the width of optimal encodings only differs by constant factors. Moreover, between the two classes the width differs at most by a factor logarithmic in the number of variables. Both these results are in stark contrast to the setting without auxiliary variables where all width measures we consider here differ by more than constant factors and in many cases even by linear factors.
QPS-r: A Cost-Effective Crossbar Scheduling Algorithm and Its Stability and Delay Analysis
Venue: arXiv cs.PF 2020
Year: 2020

In an input-queued switch, a crossbar schedule, or a matching between the input ports and the output ports needs to be computed in each switching cycle, or time slot. Designing switching algorithms with very low computational complexity, that lead to high throughput and small delay is a challenging problem. There appears to be a fundamental tradeoff between the computational complexity of the switching algorithm and the resultants throughput and delay. Parallel maximal matching algorithms (adapted for switching) appear to have stricken a sweet spot in this tradeoff, and prior work has shown the following performance guarantees. Using maximal matchings in every time slot results in at least 50% switch throughput and order-optimal (i.e., independent of the switch size N) average delay bounds for various traffic arrival processes. On the other hand, their computational complexity can be as low as $O(log^2N)$ per port/processor, which is much lower than those of the algorithms such as maximum weighted matching which ensures better throughput performance. In this work, we propose QPS-r, a parallel iterative switching algorithm that has the lowest possible computational complexity: O(1) per port. Using Lyapunov stability analysis, we show that the throughput and delay performance is identical to that of maximal matching algorithm. Although QPS-r builds upon an existing technique called Queue-Proportional Sampling (QPS), in this paper, we provide analytical guarantees on its throughput and delay under i.i.d. traffic as well as a Markovian traffic model which can model many realistic traffic patterns. We also demonstrate that QPS-3 (running 3 iterations) has comparable empirical throughput and delay performances as iSLIP (running $log_2 N$ iterations), a refined and optimized representative maximal matching algorithm adapted for switching.
How to Fine-Tune BERT for Text Classification?
Venue: arXiv cs.CL 2020
Year: 2020

Language model pre-training has proven to be useful in learning universal language representations. As a state-of-the-art language model pre-training model, BERT (Bidirectional Encoder Representations from Transformers) has achieved amazing results in many language understanding tasks. In this paper, we conduct exhaustive experiments to investigate different fine-tuning methods of BERT on text classification task and provide a general solution for BERT fine-tuning. Finally, the proposed solution obtains new state-of-the-art results on eight widely-studied text classification datasets.
Disentangled Human Body Embedding Based on Deep Hierarchical Neural Network
Venue: arXiv cs.CV 2020
Year: 2020

Human bodies exhibit various shapes for different identities or poses, but the body shape has certain similarities in structure and thus can be embedded in a low-dimensional space. This paper presents an autoencoder-like network architecture to learn disentangled shape and pose embedding specifically for the 3D human body. This is inspired by recent progress of deformation-based latent representation learning. To improve the reconstruction accuracy, we propose a hierarchical reconstruction pipeline for the disentangling process and construct a large dataset of human body models with consistent connectivity for the learning of the neural network. Our learned embedding can not only achieve superior reconstruction accuracy but also provide great flexibility in 3D human body generation via interpolation, bilinear interpolation, and latent space sampling. The results from extensive experiments demonstrate the powerfulness of our learned 3D human body embedding in various applications.
Convergence and Synchronization in Networks of Piecewise-Smooth Systems via Distributed Discontinuous Coupling
Venue: arXiv cs.SY 2020
Year: 2020

Complex networks are a successful framework to describe collective behaviour in many applications, but a notable gap remains in the current literature, that of proving asymptotic convergence in networks of piecewise-smooth systems. Indeed, a wide variety of physical systems display discontinuous dynamics that change abruptly, including dry friction mechanical oscillators, electrical power converters, and biological neurons. In this paper, we study how to enforce global asymptotic state-synchronization in these networks. Specifically, we propose the addition of a distributed discontinuous coupling action to the commonly used diffusive coupling protocol. Moreover, we provide analytical estimates of the thresholds on the coupling gains required for convergence, and highlight the importance of a new connectivity measure, which we named minimum density. The theoretical results are illustrated by a set of representative examples.
HolPy: Interactive Theorem Proving in Python
Venue: arXiv cs.LO 2020
Year: 2020

HolPy is an interactive theorem proving system implemented in Python. It uses higher-order logic as the logical foundation. Its main features include a pervasive use of macros in producing, checking, and storing proofs, a JSON-based format for theories, and an API for implementing proof automation and other extensions in Python. A point-and-click-based user interface is implemented for general-purpose theorem proving. We describe the main design decisions of HolPy, current applications, and plans for the future.
A Survey of Blocking and Filtering Techniques for Entity Resolution
Venue: arXiv cs.DB 2020
Year: 2020

Efficiency techniques are an integral part of Entity Resolution, since its infancy. In this survey, we organized the bulk of works in the field into Blocking, Filtering and hybrid techniques, facilitating their understanding and use. We also provided an in-dept coverage of each category, further classifying the corresponding works into novel sub-categories. Lately, the efficiency techniques have received more attention, due to the rise of Big Data. This includes large volumes of semi-structured data, which pose challenges not only to the scalability of efficiency techniques, but also to their core assumptions: the requirement of Blocking for schema knowledge and of Filtering for high similarity thresholds. The former led to the introduction of schema-agnostic Blocking in conjunction with Block Processing techniques, while the latter led to more relaxed criteria of similarity. Our survey covers these new fields in detail, putting in context all relevant works.
Function Space Pooling For Graph Convolutional Networks
Venue: arXiv cs.LG 2020
Year: 2020

Convolutional layers in graph neural networks are a fundamental type of layer which output a representation or embedding of each graph vertex. The representation typically encodes information about the vertex in question and its neighbourhood. If one wishes to perform a graph centric task, such as graph classification, this set of vertex representations must be integrated or pooled to form a graph representation. In this article we propose a novel pooling method which maps a set of vertex representations to a function space representation. This method is distinct from existing pooling methods which perform a mapping to either a vector or sequence space. Experimental graph classification results demonstrate that the proposed method generally outperforms most baseline pooling methods and in some cases achieves best performance.
Automatic Malware Description via Attribute Tagging and Similarity Embedding
Venue: arXiv cs.LG 2020
Year: 2020

With the rapid proliferation and increased sophistication of malicious software (malware), detection methods no longer rely only on manually generated signatures but have also incorporated more general approaches like machine learning detection. Although powerful for conviction of malicious artifacts, these methods do not produce any further information about the type of threat that has been detected neither allows for identifying relationships between malware samples. In this work, we address the information gap between machine learning and signature-based detection methods by learning a representation space for malware samples in which files with similar malicious behaviors appear close to each other. We do so by introducing a deep learning based tagging model trained to generate human-interpretable semantic descriptions of malicious software, which, at the same time provides potentially more useful and flexible information than malware family names. We show that the malware descriptions generated with the proposed approach correctly identify more than 95% of eleven possible tag descriptions for a given sample, at a deployable false positive rate of 1% per tag. Furthermore, we use the learned representation space to introduce a similarity index between malware files, and empirically demonstrate using dynamic traces from files' execution, that is not only more effective at identifying samples from the same families, but also 32 times smaller than those based on raw feature vectors.
Perfect Italian domination on planar and regular graphs
Venue: arXiv cs.DM 2020
Year: 2020

A perfect Italian dominating function of a graph $G=(V,E)$ is a function $f : V \to \{0,1,2\}$ such that for every vertex $f(v) = 0$, it holds that $\sum_{u \in N(v)} f(u) = 2$, i.e., the weight of the labels assigned by $f$ to the neighbors of $v$ is exactly two. The weight of a perfect Italian function is the sum of the weights of the vertices. The perfect Italian domination number of $G$, denoted by $γ^p_I(G)$, is the minimum weight of any perfect Italian dominating function of $G$. While introducing the parameter, Haynes and Henning (Discrete Appl. Math. (2019), 164--177) also proposed the problem of determining the best possible constants $c_\mathcal{G}$ such that $γ^p_I(G) \leq c_\mathcal{G} \times n$ for all graphs of order $n$ when $G$ is in a particular class $\mathcal{G}$ of graphs. They proved that $c_\mathcal{G} = 1$ when $\mathcal{G}$ is the class of bipartite graphs, and raised the question for planar graphs and regular graphs. We settle their question precisely for planar graphs by proving that $c_\mathcal{G} = 1$ and for cubic graphs by proving that $c_\mathcal{G} = 2/3$. For split graphs, we also show that $c_\mathcal{G} = 1$. In addition, we characterize the graphs $G$ with $γ^p_I(G)$ equal to 2 and 3 and determine the exact value of the parameter for several simple structured graphs. We conclude by proving that it is NP-complete to decide whether a given bipartite planar graph admits a perfect Italian dominating function of weight $k$.
Two-sided profile-based optimality in the stable marriage problem
Venue: arXiv cs.DS 2020
Year: 2020

We study the problem of finding "fair" stable matchings in the Stable Marriage problem with Incomplete lists (SMI). In particular, we seek stable matchings that are optimal with respect to profile, which is a vector that indicates the number of agents who have their first-, second-, third-choice partner, etc. In a rank maximal stable matching, the maximum number of agents have their first-choice partner, and subject to this, the maximum number of agents have their second-choice partner, etc., whilst in a generous stable matching $M$, the minimum number of agents have their $d$th-choice partner, and subject to this, the minimum number of agents have their $(d-1)$th-choice partner, etc., where $d$ is the maximum rank of an agent's partner in $M$. Irving et al. [18] presented an $O(nm^2\log n)$ algorithm for finding a rank-maximal stable matching, which can be adapted easily to the generous stable matching case, where $n$ is the number of men / women and $m$ is the number of acceptable man-woman pairs. An $O(n^{0.5}m^{1.5})$ algorithm for the rank-maximal stable matching problem was later given by Feder [7]. However these approaches involve the use of weights that are in general exponential in $n$. In this paper we present an $O(nm^2\log n)$ algorithm for finding a rank-maximal stable matching using a vector-based approach that involves weights that are polynomially-bounded in $n$. We conduct an empirical evaluation, and show how this approach has a far reduced memory requirement (an estimated $100$-fold improvement for instances with $100, 000$ men or women) when compared to Irving et al.'s algorithm above. Additionally, we show how to adapt our algorithm for the generous case. Finally, we examine the complexity of the problem of finding profile-based optimal stable matchings in the Stable Roommates problem (SR).
Vision-based Robotic Grasping From Object Localization, Object Pose Estimation to Grasp Estimation for Parallel Grippers: A Review
Venue: arXiv cs.RO 2020
Year: 2020

This paper presents a comprehensive survey on vision-based robotic grasping. We conclude three key tasks during vision-based robotic grasping, which are object localization, object pose estimation and grasp estimation. In detail, the object localization task contains object localization without classification, object detection and object instance segmentation. This task provides the regions of the target object in the input data. The object pose estimation task mainly refers to estimating the 6D object pose and includes correspondence-based methods, template-based methods and voting-based methods, which affords the generation of grasp poses for known objects. The grasp estimation task includes 2D planar grasp methods and 6DoF grasp methods, where the former is constrained to grasp from one direction. These three tasks could accomplish the robotic grasping with different combinations. Lots of object pose estimation methods need not object localization, and they conduct object localization and object pose estimation jointly. Lots of grasp estimation methods need not object localization and object pose estimation, and they conduct grasp estimation in an end-to-end manner. Both traditional methods and latest deep learning-based methods based on the RGB-D image inputs are reviewed elaborately in this survey. Related datasets and comparisons between state-of-the-art methods are summarized as well. In addition, challenges about vision-based robotic grasping and future directions in addressing these challenges are also pointed out.
Stroke extraction for offline handwritten mathematical expression recognition
Venue: arXiv cs.CV 2020
Year: 2020

Offline handwritten mathematical expression recognition is often considered much harder than its online counterpart due to the absence of temporal information. In order to take advantage of the more mature methods for online recognition and save resources, an oversegmentation approach is proposed to recover strokes from textual bitmap images automatically. The proposed algorithm first breaks down the skeleton of a binarized image into junctions and segments, then segments are merged to form strokes, finally stroke order is normalized by using recursive projection and topological sort. Good offline accuracy was obtained in combination with ordinary online recognizers, which are not specially designed for extracted strokes. Given a ready-made state-of-the-art online handwritten mathematical expression recognizer, the proposed procedure correctly recognized 58.22%, 65.65%, and 65.22% of the offline formulas rendered from the datasets of the Competitions on Recognition of Online Handwritten Mathematical Expressions(CROHME) in 2014, 2016, and 2019 respectively. Furthermore, given a trainable online recognition system, retraining it with extracted strokes resulted in an offline recognizer with the same level of accuracy. On the other hand, the speed of the entire pipeline was fast enough to facilitate on-device recognition on mobile phones with limited resources. To conclude, stroke extraction provides an attractive way to build optical character recognition software.
Knowledge-Based Sequential Decision-Making Under Uncertainty
Venue: arXiv cs.AI 2020
Year: 2020

Deep reinforcement learning (DRL) algorithms have achieved great success on sequential decision-making problems, yet is criticized for the lack of data-efficiency and explainability. Especially, explainability of subtasks is critical in hierarchical decision-making since it enhances the transparency of black-box-style DRL methods and helps the RL practitioners to understand the high-level behavior of the system better. To improve the data-efficiency and explainability of DRL, declarative knowledge is introduced in this work and a novel algorithm is proposed by integrating DRL with symbolic planning. Experimental analysis on publicly available benchmarks validates the explainability of the subtasks and shows that our method can outperform the state-of-the-art approach in terms of data-efficiency.
Learning Cross-lingual Embeddings from Twitter via Distant Supervision
Venue: arXiv cs.CL 2020
Year: 2020

Cross-lingual embeddings represent the meaning of words from different languages in the same vector space. Recent work has shown that it is possible to construct such representations by aligning independently learned monolingual embedding spaces, and that accurate alignments can be obtained even without external bilingual data. In this paper we explore a research direction that has been surprisingly neglected in the literature: leveraging noisy user-generated text to learn cross-lingual embeddings particularly tailored towards social media applications. While the noisiness and informal nature of the social media genre poses additional challenges to cross-lingual embedding methods, we find that it also provides key opportunities due to the abundance of code-switching and the existence of a shared vocabulary of emoji and named entities. Our contribution consists of a very simple post-processing step that exploits these phenomena to significantly improve the performance of state-of-the-art alignment methods.
Functorial Question Answering
Venue: arXiv cs.CL 2020
Year: 2020

Distributional compositional (DisCo) models are functors that compute the meaning of a sentence from the meaning of its words. We show that DisCo models in the category of sets and relations correspond precisely to relational databases. As a consequence, we get complexity-theoretic reductions from semantics and entailment of a fragment of natural language to evaluation and containment of conjunctive queries, respectively. Finally, we define question answering as an NP-complete problem.
Taking Care of The Discretization Problem: A Comprehensive Study of the Discretization Problem and A Black-Box Adversarial Attack in Discrete Integer Domain
Venue: arXiv cs.LG 2020
Year: 2020

Numerous methods for crafting adversarial examples were proposed recently with high success rate. Since most existing machine learning based classifiers normalize images into some continuous, real vector, domain firstly, attacks often craft adversarial examples in such domain. However, "adversarial" examples may become benign after denormalizing them back into the discrete integer domain, known as the discretization problem. This problem was mentioned in some work, but has received relatively little attention. In this work, we first conduct a comprehensive study of existing methods and tools for crafting. We theoretically analyze 34 representative methods and empirically study 20 representative open source tools for crafting adversarial images. Our study reveals that the discretization problem is far more serious than originally thought. This suggests that the discretization problem should be taken into account seriously when crafting adversarial examples and measuring attack success rate. As a first step towards addressing this problem in black-box scenario, we propose a black-box method which reduces the adversarial example searching problem to a derivative-free optimization problem. Our method is able to craft adversarial images by derivative-free search in the discrete integer domain. Experimental results show that our method is comparable to recent white-box methods (e.g., FGSM, BIM and C\&W) and achieves significantly higher success rate in terms of adversarial examples in the discrete integer domain than recent black-box methods (e.g., ZOO, NES-PGD and Bandits). Moreover, our method is able to handle models that is non-differentiable and successfully break the winner of NIPS 2017 competition on defense with 95\% success rate. Our results suggest that discrete optimization algorithms open up a promising area of research into effective black-box attacks.
Borrow from Anywhere: Pseudo Multi-modal Object Detection in Thermal Imagery
Venue: arXiv cs.CV 2020
Year: 2020

Can we improve detection in the thermal domain by borrowing features from rich domains like visual RGB? In this paper, we propose a pseudo-multimodal object detector trained on natural image domain data to help improve the performance of object detection in thermal images. We assume access to a large-scale dataset in the visual RGB domain and relatively smaller dataset (in terms of instances) in the thermal domain, as is common today. We propose the use of well-known image-to-image translation frameworks to generate pseudo-RGB equivalents of a given thermal image and then use a multi-modal architecture for object detection in the thermal image. We show that our framework outperforms existing benchmarks without the explicit need for paired training examples from the two domains. We also show that our framework has the ability to learn with less data from thermal domain when using our approach. Our code and pre-trained models are made available at https://github.com/tdchaitanya/MMTOD