OpenRaiser/Intern-Atlas huggingface dataset:
The Lexicographic Method for the Threshold Cover Problem
Venue: arXiv cs.DM 2020
Year: 2020

Threshold graphs are a class of graphs that have many equivalent definitions and have applications in integer programming and set packing problems. A graph is said to have a threshold cover of size $k$ if its edges can be covered using $k$ threshold graphs. Chvátal and Hammer, in 1977, defined the threshold dimension $\mathrm{th}(G)$ of a graph $G$ to be the least integer $k$ such that $G$ has a threshold cover of size $k$ and observed that $\mathrm{th}(G)\geqχ(G^*)$, where $G^*$ is a suitably constructed auxiliary graph. Raschle and Simon~[Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing, STOC '95, pages 650--661, 1995] proved that $\mathrm{th}(G)=χ(G^*)$ whenever $G^*$ is bipartite. We show how the lexicographic method of Hell and Huang can be used to obtain a completely new and, we believe, simpler proof for this result. For the case when $G$ is a split graph, our method yields a proof that is much shorter than the ones known in the literature.
Sequential vs. Integrated Algorithm Selection and Configuration: A Case Study for the Modular CMA-ES
Venue: arXiv cs.NE 2020
Year: 2020

When faced with a specific optimization problem, choosing which algorithm to use is always a tough task. Not only is there a vast variety of algorithms to select from, but these algorithms often are controlled by many hyperparameters, which need to be tuned in order to achieve the best performance possible. Usually, this problem is separated into two parts: algorithm selection and algorithm configuration. With the significant advances made in Machine Learning, however, these problems can be integrated into a combined algorithm selection and hyperparameter optimization task, commonly known as the CASH problem. In this work we compare sequential and integrated algorithm selection and configuration approaches for the case of selecting and tuning the best out of 4608 variants of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) tested on the Black Box Optimization Benchmark (BBOB) suite. We first show that the ranking of the modular CMA-ES variants depends to a large extent on the quality of the hyperparameters. This implies that even a sequential approach based on complete enumeration of the algorithm space will likely result in sub-optimal solutions. In fact, we show that the integrated approach manages to provide competitive results at a much smaller computational cost. We also compare two different mixed-integer algorithm configuration techniques, called irace and Mixed-Integer Parallel Efficient Global Optimization (MIP-EGO). While we show that the two methods differ significantly in their treatment of the exploration-exploitation balance, their overall performances are very similar.
A case study of Consistent Vehicle Routing Problem with Time Windows
Venue: arXiv cs.AI 2020
Year: 2020

We develop a heuristic for the Consistent Vehicle Routing Problem with Time Windows (ConVRPTW), which is motivated by a real-world application at a food company's distribution center. Besides standard VRPTW restrictions, ConVRPTW assigns each customer just one driver to fulfill their orders during the whole multi-period planning horizon. For each driver and period, a route is sought to serve all their customers with positive demand. For each customer, the number of periods between consecutive orders and the ordered quantities are highly irregular. This causes difficulties in the daily routing, negatively impacting the service level of the company. Similar problems have been studied as ConVRP, where the number of drivers is fixed a priori, and only the total travel time is minimized. Moreover, the clients present no time window constraints, but the visits should be scheduled with a small arrival time variation. In our model, the objective is to minimize the number of drivers. We impose hard time windows but do not consider time consistency in more detail. We compare solutions given by the heuristic with solutions of a MILP model on a set of small artificial instances and solutions used by the food company on real-world instances. The results show the effectiveness of the heuristic. For the company, we obtain significant improvements in the routing plans, with a lower number of vehicles and a higher rate of orders delivered within the prescribed time window.
Parareal with a Learned Coarse Model for Robotic Manipulation
Venue: arXiv cs.RO 2020
Year: 2020

A key component of many robotics model-based planning and control algorithms is physics predictions, that is, forecasting a sequence of states given an initial state and a sequence of controls. This process is slow and a major computational bottleneck for robotics planning algorithms. Parallel-in-time integration methods can help to leverage parallel computing to accelerate physics predictions and thus planning. The Parareal algorithm iterates between a coarse serial integrator and a fine parallel integrator. A key challenge is to devise a coarse model that is computationally cheap but accurate enough for Parareal to converge quickly. Here, we investigate the use of a deep neural network physics model as a coarse model for Parareal in the context of robotic manipulation. In simulated experiments using the physics engine Mujoco as fine propagator we show that the learned coarse model leads to faster Parareal convergence than a coarse physics-based model. We further show that the learned coarse model allows to apply Parareal to scenarios with multiple objects, where the physics-based coarse model is not applicable. Finally, we conduct experiments on a real robot and show that Parareal predictions are close to real-world physics predictions for robotic pushing of multiple objects. Videos are at https://youtu.be/wCh2o1rf-gA.
Time-Sensitive Networking in IEEE 802.11be: On the Way to Low-latency WiFi 7
Venue: arXiv cs.NI 2020
Year: 2020

Short time after the official launch of WiFi 6, IEEE 802.11 working groups are already designing its successor in the wireless local area network (WLAN) ecosystem: WiFi 7. With the IEEE 802.11be amendment as one of its main constituent parts, future WiFi 7 aims to include time-sensitive networking (TSN) capabilities to support low latency and ultra reliability in license-exempt spectrum bands. This article first introduces the key features of IEEE 802.11be, which are then used as the basis to discuss how TSN functionalities could be implemented in WiFi 7. Finally, benefits and requirements of the most representative low-latency use cases for WiFi 7 are reviewed.
ABOUT ML: Annotation and Benchmarking on Understanding and Transparency of Machine Learning Lifecycles
Venue: arXiv cs.CY 2020
Year: 2020

We present the "Annotation and Benchmarking on Understanding and Transparency of Machine Learning Lifecycles" (ABOUT ML) project as an initiative to operationalize ML transparency and work towards a standard ML documentation practice. We make the case for the project's relevance and effectiveness in consolidating disparate efforts across a variety of stakeholders, as well as bringing in the perspectives of currently missing voices that will be valuable in shaping future conversations. We describe the details of the initiative and the gaps we hope this project will help address.
Sim2Real Predictivity: Does Evaluation in Simulation Predict Real-World Performance?
Venue: arXiv cs.CV 2020
Year: 2020

Does progress in simulation translate to progress on robots? If one method outperforms another in simulation, how likely is that trend to hold in reality on a robot? We examine this question for embodied PointGoal navigation, developing engineering tools and a research paradigm for evaluating a simulator by its sim2real predictivity. First, we develop Habitat-PyRobot Bridge (HaPy), a library for seamless execution of identical code on simulated agents and robots, transferring simulation-trained agents to a LoCoBot platform with a one-line code change. Second, we investigate the sim2real predictivity of Habitat-Sim for PointGoal navigation. We 3D-scan a physical lab space to create a virtualized replica, and run parallel tests of 9 different models in reality and simulation. We present a new metric called Sim-vs-Real Correlation Coefficient (SRCC) to quantify predictivity. We find that SRCC for Habitat as used for the CVPR19 challenge is low (0.18 for the success metric), suggesting that performance differences in this simulator-based challenge do not persist after physical deployment. This gap is largely due to AI agents learning to exploit simulator imperfections, abusing collision dynamics to 'slide' along walls, leading to shortcuts through otherwise non-navigable space. Naturally, such exploits do not work in the real world. Our experiments show that it is possible to tune simulation parameters to improve sim2real predictivity (e.g. improving $SRCC_{Succ}$ from 0.18 to 0.844), increasing confidence that in-simulation comparisons will translate to deployed systems in reality.
Towards Partial Supervision for Generic Object Counting in Natural Scenes
Venue: arXiv cs.CV 2020
Year: 2020

Generic object counting in natural scenes is a challenging computer vision problem. Existing approaches either rely on instance-level supervision or absolute count information to train a generic object counter. We introduce a partially supervised setting that significantly reduces the supervision level required for generic object counting. We propose two novel frameworks, named lower-count (LC) and reduced lower-count (RLC), to enable object counting under this setting. Our frameworks are built on a novel dual-branch architecture that has an image classification and a density branch. Our LC framework reduces the annotation cost due to multiple instances in an image by using only lower-count supervision for all object categories. Our RLC framework further reduces the annotation cost arising from large numbers of object categories in a dataset by only using lower-count supervision for a subset of categories and class-labels for the remaining ones. The RLC framework extends our dual-branch LC framework with a novel weight modulation layer and a category-independent density map prediction. Experiments are performed on COCO, Visual Genome and PASCAL 2007 datasets. Our frameworks perform on par with state-of-the-art approaches using higher levels of supervision. Additionally, we demonstrate the applicability of our LC supervised density map for image-level supervised instance segmentation.
A farewell to Professor RNDr. Věra Trnková}, DrSc
Venue: arXiv cs.LO 2020
Year: 2020

This is an introduction of the volume of the journal Commentationes Mathematicae Universitatis Caroalinae dedicated to the memory of Věra Trnková}.
The quadratic hull of a code and the geometric view on multiplication algorithms
Venue: arXiv cs.IT 2020
Year: 2020

We introduce the notion of quadratic hull of a linear code, and give some of its properties. We then show that any symmetric bilinear multiplication algorithm for a finite-dimensional algebra over a field can be obtained by evaluation-interpolation at simple points (i.e. of degree and multiplicity 1) on a naturally associated space, namely the quadratic hull of the corresponding code. This also provides a geometric answer to some questions such as: which linear maps actually are multiplication algorithms, or which codes come from supercodes (as asked by Shparlinski-Tsfasman-Vladut). We illustrate this with examples, in particular we describe the quadratic hull of all the optimal algorithms computed by Barbulescu-Detrey-Estibals-Zimmermann for small algebras. In our presentation we actually work with multiplication reductions. This is a generalization of multiplication algorithms, that allows for instance evaluation-interpolation at points of higher degree and/or with multiplicities, and also includes the recently introduced notion of "reverse multiplication-friendly embedding" from Cascudo-Cramer-Xing-Yang. All our results hold in this more general context.
WaLDORf: Wasteless Language-model Distillation On Reading-comprehension
Venue: arXiv cs.LG 2020
Year: 2020

Transformer based Very Large Language Models (VLLMs) like BERT, XLNet and RoBERTa, have recently shown tremendous performance on a large variety of Natural Language Understanding (NLU) tasks. However, due to their size, these VLLMs are extremely resource intensive and cumbersome to deploy at production time. Several recent publications have looked into various ways to distil knowledge from a transformer based VLLM (most commonly BERT-Base) into a smaller model which can run much faster at inference time. Here, we propose a novel set of techniques which together produce a task-specific hybrid convolutional and transformer model, WaLDORf, that achieves state-of-the-art inference speed while still being more accurate than previous distilled models.
Common Voice: A Massively-Multilingual Speech Corpus
Venue: arXiv cs.CL 2020
Year: 2020

The Common Voice corpus is a massively-multilingual collection of transcribed speech intended for speech technology research and development. Common Voice is designed for Automatic Speech Recognition purposes but can be useful in other domains (e.g. language identification). To achieve scale and sustainability, the Common Voice project employs crowdsourcing for both data collection and data validation. The most recent release includes 29 languages, and as of November 2019 there are a total of 38 languages collecting data. Over 50,000 individuals have participated so far, resulting in 2,500 hours of collected audio. To our knowledge this is the largest audio corpus in the public domain for speech recognition, both in terms of number of hours and number of languages. As an example use case for Common Voice, we present speech recognition experiments using Mozilla's DeepSpeech Speech-to-Text toolkit. By applying transfer learning from a source English model, we find an average Character Error Rate improvement of 5.99 +/- 5.48 for twelve target languages (German, French, Italian, Turkish, Catalan, Slovenian, Welsh, Irish, Breton, Tatar, Chuvash, and Kabyle). For most of these languages, these are the first ever published results on end-to-end Automatic Speech Recognition.
Knowledge forest: a novel model to organize knowledge fragments
Venue: arXiv cs.AI 2020
Year: 2020

With the rapid growth of knowledge, it shows a steady trend of knowledge fragmentization. Knowledge fragmentization manifests as that the knowledge related to a specific topic in a course is scattered in isolated and autonomous knowledge sources. We term the knowledge of a facet in a specific topic as a knowledge fragment. The problem of knowledge fragmentization brings two challenges: First, knowledge is scattered in various knowledge sources, which exerts users' considerable efforts to search for the knowledge of their interested topics, thereby leading to information overload. Second, learning dependencies which refer to the precedence relationships between topics in the learning process are concealed by the isolation and autonomy of knowledge sources, thus causing learning disorientation. To solve the knowledge fragmentization problem, we propose a novel knowledge organization model, knowledge forest, which consists of facet trees and learning dependencies. Facet trees can organize knowledge fragments with facet hyponymy to alleviate information overload. Learning dependencies can organize disordered topics to cope with learning disorientation. We conduct extensive experiments on three manually constructed datasets from the Data Structure, Data Mining, and Computer Network courses, and the experimental results show that knowledge forest can effectively organize knowledge fragments, and alleviate information overload and learning disorientation.
Compressed DenseNet for Lightweight Character Recognition
Venue: arXiv cs.CV 2020
Year: 2020

Convolutional Recurrent Neural Network (CRNN) is a popular network for recognizing texts in images. Advances like the variant of CRNN, such as Dense Convolutional Network with Connectionist Temporal Classification, has reduced the running time of the network, but exposing the inner computation cost and weight size of the convolutional networks as a bottleneck. Specifically, the DenseNet based models utilize the dense blocks as the core module, but the inner features are combined in the form of concatenation in dense blocks. As such, the number of channels of combined features delivered as the input of the layers close to the output and the relevant computational cost grows rapidly with the dense blocks getting deeper. This will severely bring heavy computational cost and big weight size, which restrict the depth of dense blocks. In this paper, we propose a compressed convolution block called Lightweight Dense Block (LDB). To reduce the computing cost and weight size, we re-define and re-design the way of combining internal features of the dense blocks. LDB is a convolutional block similarly as dense block, but it can reduce the computation cost and weight size to (1/L, 2/L), compared with original ones, where L is the number of layers in blocks. Moreover, LDB can be used to replace the original dense block in any DenseNet based models. Based on the LDBs, we propose a Compressed DenseNet (CDenseNet) for the lightweight character recognition. Extensive experiments demonstrate that CDenseNet can effectively reduce the weight size while delivering the promising recognition results.
A Hybrid Approach and Unified Framework for Bibliographic Reference Extraction
Venue: arXiv cs.CV 2020
Year: 2020

Publications are an integral part in a scientific community. Bibliographic reference extraction from scientific publication is a challenging task due to diversity in referencing styles and document layout. Existing methods perform sufficiently on one dataset however, applying these solutions to a different dataset proves to be challenging. Therefore, a generic solution was anticipated which could overcome the limitations of the previous approaches. The contribution of this paper is three-fold. First, it presents a novel approach called DeepBiRD which is inspired by human visual perception and exploits layout features to identify individual references in a scientific publication. Second, we release a large dataset for image-based reference detection with 2401 scans containing 38863 references, all manually annotated for individual reference. Third, we present a unified and highly configurable end-to-end automatic bibliographic reference extraction framework called BRExSys which employs DeepBiRD along with state-of-the-art text-based models to detect and visualize references from a bibliographic document. Our proposed approach pre-processes the images in which a hybrid representation is obtained by processing the given image using different computer vision techniques. Then, it performs layout driven reference detection using Mask R-CNN on a given scientific publication. DeepBiRD was evaluated on two different datasets to demonstrate the generalization of this approach. The proposed system achieved an AP50 of 98.56% on our dataset. DeepBiRD significantly outperformed the current state-of-the-art approach on their dataset. Therefore, suggesting that DeepBiRD is significantly superior in performance, generalized, and independent of any domain or referencing style.
A Deep Neural Network's Loss Surface Contains Every Low-dimensional Pattern
Venue: arXiv cs.LG 2020
Year: 2020

The work "Loss Landscape Sightseeing with Multi-Point Optimization" (Skorokhodov and Burtsev, 2019) demonstrated that one can empirically find arbitrary 2D binary patterns inside loss surfaces of popular neural networks. In this paper we prove that: (i) this is a general property of deep universal approximators; and (ii) this property holds for arbitrary smooth patterns, for other dimensionalities, for every dataset, and any neural network that is sufficiently deep and wide. Our analysis predicts not only the existence of all such low-dimensional patterns, but also two other properties that were observed empirically: (i) that it is easy to find these patterns; and (ii) that they transfer to other data-sets (e.g. a test-set).
On the Explanation of Machine Learning Predictions in Clinical Gait Analysis
Venue: arXiv cs.LG 2020
Year: 2020

Machine learning (ML) is increasingly used to support decision-making in the healthcare sector. While ML approaches provide promising results with regard to their classification performance, most share a central limitation, namely their black-box character. Motivated by the interest to understand the functioning of ML models, methods from the field of Explainable Artificial Intelligence (XAI) have recently become important. This article investigates the usefulness of XAI methods in clinical gait classification. For this purpose, predictions of state-of-the-art classification methods are explained with an established XAI method, i.e., Layer-wise Relevance Propagation (LRP). We propose to evaluate the obtained explanations with two complementary approaches: a statistical analysis of the underlying data using Statistical Parametric Mapping and a qualitative evaluation by a clinical expert. A gait dataset comprising ground reaction force measurements from 132 patients with different lower-body gait disorders and 62 healthy controls is utilized. We investigate several gait classification tasks, employ multiple classification methods, and analyze the impact of data normalization and different signal components for classification performance and explanation quality. Our experiments show that explanations obtained by LRP exhibit promising statistical properties concerning inter-class discriminativity and are also in line with clinically relevant biomechanical gait characteristics.
New Bounds on Antipowers in Words
Venue: arXiv cs.FL 2020
Year: 2020

Fici et al. defined a word to be a k-power if it is the concatenation of k consecutive identical blocks, and an r-antipower if it is the concatenation of r pairwise distinct blocks of the same size. They defined N (k, r) as the smallest l such that every binary word of length l contains either a k-power or an r-antipower. In this note we obtain some new upper and lower bounds on N (k, r). We also consider avoiding 3-antipowers and 4-antipowers over larger alphabets, and obtain a lower bound for N (k, 5) in the binary case.
Uncovering Relations for Marketing Knowledge Representation
Venue: arXiv cs.AI 2020
Year: 2020

Online behaviors of consumers and marketers generate massive marketing data, which ever more sophisticated models attempt to turn into insights and aid decisions by marketers. Yet, in making decisions human managers bring to bear marketing knowledge which reside outside of data and models. Thus, it behooves creation of an automated marketing knowledge base that can interact with data and models. Currently, marketing knowledge is dispersed in large corpora, but no definitive knowledge base for marketing exists. Out of the two broad aspects of marketing knowledge - representation and reasoning - this treatise focuses on the former. Specifically, we focus on creation of marketing knowledge graph from corpora, which requires identification of entities and relations. The relation identification task is particularly challenging in marketing, because of the non-factoid nature of much marketing knowledge, and the difficulty of forming rules that govern relations. Specifically, we define a set of relations to capture marketing knowledge, propose a pipeline for creating the knowledge graph from text and propose a rule-guided semi-supervised relation prediction algorithm to extract relations between marketing entities from sentences.