OpenRaiser/Intern-Atlas huggingface dataset:
Hitting Topological Minors is FPT
Venue: arXiv cs.DS 2020
Year: 2020

In the Topological Minor Deletion (TM-Deletion) problem input consists of an undirected graph $G$, a family of undirected graphs ${\cal F}$ and an integer $k$. The task is to determine whether $G$ contains a set of vertices $S$ of size at most $k$, such that the graph $G\setminus S$ obtained from $G$ by removing the vertices of $S$, contains no graph from ${\cal F}$ as a topological minor. We give an algorithm for TM-Deletionwith running time $f(h^\star,k)\cdot |V(G)|^{4}$. Here $h^\star$ is the maximum size of a graph in ${\cal F}$ and $f$ is a computable function of $h^\star$ and $k$. This is the first fixed parameter tractable algorithm (FPT) for the problem. In fact, even for the restricted case of planar inputs the first FPT algorithm was found only recently by Golovach et al. [SODA 2020]. For this case we improve upon the algorithm of Golovach et al. [SODA 2020] by designing an FPT algorithm with explicit dependence on $k$ and $h^\star$.
Event-triggered Learning
Venue: arXiv cs.SY 2020
Year: 2020

The efficient exchange of information is an essential aspect of intelligent collective behavior. Event-triggered control and estimation achieve some efficiency by replacing continuous data exchange between agents with intermittent, or event-triggered communication. Typically, model-based predictions are used at times of no data transmission, and updates are sent only when the prediction error grows too large. The effectiveness in reducing communication thus strongly depends on the quality of the prediction model. In this article, we propose event-triggered learning as a novel concept to reduce communication even further and to also adapt to changing dynamics. By monitoring the actual communication rate and comparing it to the one that is induced by the model, we detect a mismatch between model and reality and trigger model learning when needed. Specifically, for linear Gaussian dynamics, we derive different classes of learning triggers solely based on a statistical analysis of inter-communication times and formally prove their effectiveness with the aid of concentration inequalities.
Probabilistic Regression of Rotations using Quaternion Averaging and a Deep Multi-Headed Network
Venue: arXiv cs.CV 2020
Year: 2020

Accurate estimates of rotation are crucial to vision-based motion estimation in augmented reality and robotics. In this work, we present a method to extract probabilistic estimates of rotation from deep regression models. First, we build on prior work and argue that a multi-headed network structure we name HydraNet provides better calibrated uncertainty estimates than methods that rely on stochastic forward passes. Second, we extend HydraNet to targets that belong to the rotation group, SO(3), by regressing unit quaternions and using the tools of rotation averaging and uncertainty injection onto the manifold to produce three-dimensional covariances. Finally, we present results and analysis on a synthetic dataset, learn consistent orientation estimates on the 7-Scenes dataset, and show how we can use our learned covariances to fuse deep estimates of relative orientation with classical stereo visual odometry to improve localization on the KITTI dataset.
Effective and Efficient Dropout for Deep Convolutional Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Convolutional Neural networks (CNNs) based applications have become ubiquitous, where proper regularization is greatly needed. To prevent large neural network models from overfitting, dropout has been widely used as an efficient regularization technique in practice. However, many recent works show that the standard dropout is ineffective or even detrimental to the training of CNNs. In this paper, we revisit this issue and examine various dropout variants in an attempt to improve existing dropout-based regularization techniques for CNNs. We attribute the failure of standard dropout to the conflict between the stochasticity of dropout and its following Batch Normalization (BN), and propose to reduce the conflict by placing dropout operations right before the convolutional operation instead of BN, or totally address this issue by replacing BN with Group Normalization (GN). We further introduce a structurally more suited dropout variant Drop-Conv2d, which provides more efficient and effective regularization for deep CNNs. These dropout variants can be readily integrated into the building blocks of CNNs and implemented in existing deep learning platforms. Extensive experiments on benchmark datasets including CIFAR, SVHN and ImageNet are conducted to compare the existing building blocks and the proposed ones with dropout training. Results show that our building blocks improve over state-of-the-art CNNs significantly, which is mainly due to the better regularization and implicit model ensemble effect.
The Mathematics of Text Structure
Venue: arXiv cs.CL 2020
Year: 2020

In previous work we gave a mathematical foundation, referred to as DisCoCat, for how words interact in a sentence in order to produce the meaning of that sentence. To do so, we exploited the perfect structural match of grammar and categories of meaning spaces. Here, we give a mathematical foundation, referred to as DisCoCirc, for how sentences interact in texts in order to produce the meaning of that text. First we revisit DisCoCat. While in DisCoCat all meanings are fixed as states (i.e. have no input), in DisCoCirc word meanings correspond to a type, or system, and the states of this system can evolve. Sentences are gates within a circuit which update the variable meanings of those words. Like in DisCoCat, word meanings can live in a variety of spaces e.g. propositional, vectorial, or cognitive. The compositional structure are string diagrams representing information flows, and an entire text yields a single string diagram in which word meanings lift to the meaning of an entire text. While the developments in this paper are independent of a physical embodiment (cf. classical vs. quantum computing), both the compositional formalism and suggested meaning model are highly quantum-inspired, and implementation on a quantum computer would come with a range of benefits. We also praise Jim Lambek for his role in mathematical linguistics in general, and the development of the DisCo program more specifically.
VATEX: A Large-Scale, High-Quality Multilingual Dataset for Video-and-Language Research
Venue: arXiv cs.CV 2020
Year: 2020

We present a new large-scale multilingual video description dataset, VATEX, which contains over 41,250 videos and 825,000 captions in both English and Chinese. Among the captions, there are over 206,000 English-Chinese parallel translation pairs. Compared to the widely-used MSR-VTT dataset, VATEX is multilingual, larger, linguistically complex, and more diverse in terms of both video and natural language descriptions. We also introduce two tasks for video-and-language research based on VATEX: (1) Multilingual Video Captioning, aimed at describing a video in various languages with a compact unified captioning model, and (2) Video-guided Machine Translation, to translate a source language description into the target language using the video information as additional spatiotemporal context. Extensive experiments on the VATEX dataset show that, first, the unified multilingual model can not only produce both English and Chinese descriptions for a video more efficiently, but also offer improved performance over the monolingual models. Furthermore, we demonstrate that the spatiotemporal video context can be effectively utilized to align source and target languages and thus assist machine translation. In the end, we discuss the potentials of using VATEX for other video-and-language research.
Taco-VC: A Single Speaker Tacotron based Voice Conversion with Limited Data
Venue: arXiv cs.SD 2020
Year: 2020

This paper introduces Taco-VC, a novel architecture for voice conversion based on Tacotron synthesizer, which is a sequence-to-sequence with attention model. The training of multi-speaker voice conversion systems requires a large number of resources, both in training and corpus size. Taco-VC is implemented using a single speaker Tacotron synthesizer based on Phonetic PosteriorGrams (PPGs) and a single speaker WaveNet vocoder conditioned on mel spectrograms. To enhance the converted speech quality, and to overcome over-smoothing, the outputs of Tacotron are passed through a novel speechenhancement network, which is composed of a combination of the phoneme recognition and Tacotron networks. Our system is trained just with a single speaker corpus and adapts to new speakers using only a few minutes of training data. Using mid-size public datasets, our method outperforms the baseline in the VCC 2018 SPOKE non-parallel voice conversion task and achieves competitive results compared to multi-speaker networks trained on large private datasets.
Minimum Enclosing Ball Revisited: Stability and Sub-linear Time Algorithms
Venue: arXiv cs.CG 2020
Year: 2020

In this paper, we revisit the Minimum Enclosing Ball (MEB) problem and its robust version, MEB with outliers, in Euclidean space $\mathbb{R}^d$. Though the problem has been extensively studied before, most of the existing algorithms need at least linear time (in the number of input points $n$ and the dimensionality $d$) to achieve a $(1+ε)$-approximation. Motivated by some recent developments on beyond worst-case analysis, we introduce the notion of stability for MEB (with outliers), which is natural and easy to understand. Roughly speaking, an instance of MEB is stable, if the radius of the resulting ball cannot be significantly reduced by removing a small fraction of the input points. Under the stability assumption, we present two sampling algorithms for computing approximate MEB with sample complexities independent of the number of input points $n$. In particular, the second algorithm has the sample complexity even independent of the dimensionality $d$. Further, we extend the idea to achieve a sub-linear time approximation algorithm for the MEB with outliers problem. Note that most existing sub-linear time algorithms for the problems of MEB and MEB with outliers usually result in bi-criteria approximations, where the "bi-criteria" means that the solution has to allow the approximations on the radius and the number of covered points. Differently, all the algorithms proposed in this paper yield single-criterion approximations (with respect to radius). We expect that our proposed notion of stability and techniques will be applicable to design sub-linear time algorithms for other optimization problems.
FoveaBox: Beyond Anchor-based Object Detector
Venue: arXiv cs.CV 2020
Year: 2020

We present FoveaBox, an accurate, flexible, and completely anchor-free framework for object detection. While almost all state-of-the-art object detectors utilize predefined anchors to enumerate possible locations, scales and aspect ratios for the search of the objects, their performance and generalization ability are also limited to the design of anchors. Instead, FoveaBox directly learns the object existing possibility and the bounding box coordinates without anchor reference. This is achieved by: (a) predicting category-sensitive semantic maps for the object existing possibility, and (b) producing category-agnostic bounding box for each position that potentially contains an object. The scales of target boxes are naturally associated with feature pyramid representations. In FoveaBox, an instance is assigned to adjacent feature levels to make the model more accurate.We demonstrate its effectiveness on standard benchmarks and report extensive experimental analysis. Without bells and whistles, FoveaBox achieves state-of-the-art single model performance on the standard COCO and Pascal VOC object detection benchmark. More importantly, FoveaBox avoids all computation and hyper-parameters related to anchor boxes, which are often sensitive to the final detection performance. We believe the simple and effective approach will serve as a solid baseline and help ease future research for object detection. The code has been made publicly available at https://github.com/taokong/FoveaBox .
Direct Modelling of Speech Emotion from Raw Speech
Venue: arXiv cs.SD 2020
Year: 2020

Speech emotion recognition is a challenging task and heavily depends on hand-engineered acoustic features, which are typically crafted to echo human perception of speech signals. However, a filter bank that is designed from perceptual evidence is not always guaranteed to be the best in a statistical modelling framework where the end goal is for example emotion classification. This has fuelled the emerging trend of learning representations from raw speech especially using deep learning neural networks. In particular, a combination of Convolution Neural Networks (CNNs) and Long Short Term Memory (LSTM) have gained great traction for the intrinsic property of LSTM in learning contextual information crucial for emotion recognition; and CNNs been used for its ability to overcome the scalability problem of regular neural networks. In this paper, we show that there are still opportunities to improve the performance of emotion recognition from the raw speech by exploiting the properties of CNN in modelling contextual information. We propose the use of parallel convolutional layers to harness multiple temporal resolutions in the feature extraction block that is jointly trained with the LSTM based classification network for the emotion recognition task. Our results suggest that the proposed model can reach the performance of CNN trained with hand-engineered features from both IEMOCAP and MSP-IMPROV datasets.
Evaluation of Greek Word Embeddings
Venue: arXiv cs.CL 2020
Year: 2020

Since word embeddings have been the most popular input for many NLP tasks, evaluating their quality is of critical importance. Most research efforts are focusing on English word embeddings. This paper addresses the problem of constructing and evaluating such models for the Greek language. We created a new word analogy corpus considering the original English Word2vec word analogy corpus and some specific linguistic aspects of the Greek language as well. Moreover, we created a Greek version of WordSim353 corpora for a basic evaluation of word similarities. We tested seven word vector models and our evaluation showed that we are able to create meaningful representations. Last, we discovered that the morphological complexity of the Greek language and polysemy can influence the quality of the resulting word embeddings.
A Closer Look at Few-shot Classification
Venue: arXiv cs.CV 2020
Year: 2020

Few-shot classification aims to learn a classifier to recognize unseen classes during training with limited labeled examples. While significant progress has been made, the growing complexity of network designs, meta-learning algorithms, and differences in implementation details make a fair comparison difficult. In this paper, we present 1) a consistent comparative analysis of several representative few-shot classification algorithms, with results showing that deeper backbones significantly reduce the performance differences among methods on datasets with limited domain differences, 2) a modified baseline method that surprisingly achieves competitive performance when compared with the state-of-the-art on both the \miniI and the CUB datasets, and 3) a new experimental setting for evaluating the cross-domain generalization ability for few-shot classification algorithms. Our results reveal that reducing intra-class variation is an important factor when the feature backbone is shallow, but not as critical when using deeper backbones. In a realistic cross-domain evaluation setting, we show that a baseline method with a standard fine-tuning practice compares favorably against other state-of-the-art few-shot learning algorithms.
Handover Management for mmWave Networks with Proactive Performance Prediction Using Camera Images and Deep Reinforcement Learning
Venue: arXiv cs.NI 2020
Year: 2020

For millimeter-wave networks, this paper presents a paradigm shift for leveraging time-consecutive camera images in handover decision problems. While making handover decisions, it is important to predict future long-term performance---e.g., the cumulative sum of time-varying data rates---proactively to avoid making myopic decisions. However, this study experimentally notices that a time-variation in the received powers is not necessarily informative for proactively predicting the rapid degradation of data rates caused by moving obstacles. To overcome this challenge, this study proposes a proactive framework wherein handover timings are optimized while obstacle-caused data rate degradations are predicted before the degradations occur. The key idea is to expand a state space to involve time consecutive camera images, which comprises informative features for predicting such data rate degradations. To overcome the difficulty in handling the large dimensionality of the expanded state space, we use a deep reinforcement learning for deciding the handover timings. The evaluations performed based on the experimentally obtained camera images and received powers demonstrate that the expanded state space facilitates (i) the prediction of obstacle-caused data rate degradations from 500 ms before the degradations occur and (ii) superior performance to a handover framework without the state space expansion
Reconstruction of C&C Channel for P2P Botnet
Venue: arXiv cs.CR 2020
Year: 2020

Breaking down botnets have always been a big challenge. The robustness of C&C channels is increased, and the detection of botmaster is harder in P2P botnets. In this paper, we propose a probabilistic method to reconstruct the topologies of the C&C channel for P2P botnets. Due to the geographic dispersion of P2P botnet members, it is not possible to supervise all members, and there does not exist all necessary data for applying other graph reconstruction methods. So far, no general method has been introduced to reconstruct C&C channel topology for all type of P2P botnet. In our method, the probability of connections between bots is estimated by using the inaccurate receiving times of several cascades, network model parameters of C&C channel, and end-to-end delay distribution of the Internet. The receiving times can be collected by observing the external reaction of bots to commands. The results of our simulations show that more than 90% of the edges in a 1000-member network with node degree mean 50, have been accurately estimated by collecting the inaccurate receiving times of 22 cascades. In case the receiving times of just half of the bots are collected, this accuracy of estimation is obtained by using 95 cascades.
A Relation-Augmented Fully Convolutional Network for Semantic Segmentation in Aerial Scenes
Venue: arXiv cs.CV 2020
Year: 2020

Most current semantic segmentation approaches fall back on deep convolutional neural networks (CNNs). However, their use of convolution operations with local receptive fields causes failures in modeling contextual spatial relations. Prior works have sought to address this issue by using graphical models or spatial propagation modules in networks. But such models often fail to capture long-range spatial relationships between entities, which leads to spatially fragmented predictions. Moreover, recent works have demonstrated that channel-wise information also acts a pivotal part in CNNs. In this work, we introduce two simple yet effective network units, the spatial relation module and the channel relation module, to learn and reason about global relationships between any two spatial positions or feature maps, and then produce relation-augmented feature representations. The spatial and channel relation modules are general and extensible, and can be used in a plug-and-play fashion with the existing fully convolutional network (FCN) framework. We evaluate relation module-equipped networks on semantic segmentation tasks using two aerial image datasets, which fundamentally depend on long-range spatial relational reasoning. The networks achieve very competitive results, bringing significant improvements over baselines.
STAND: A Spatio-Temporal Algorithm for Network Diffusion Simulation
Venue: arXiv cs.SI 2020
Year: 2020

Information, ideas, and diseases, or more generally, contagions, spread over space and time through individual transmissions via social networks, as well as through external sources. A detailed picture of any diffusion process can be achieved only when both a good network structure and individual diffusion pathways are obtained. The advent of rich social, media and locational data allows us to study and model this diffusion process in more detail than previously possible. Nevertheless, how information, ideas or diseases are propagated through the network as an overall process is difficult to trace. This propagation is continuous over space and time, where individual transmissions occur at different rates via complex, latent connections. To tackle this challenge, a probabilistic spatiotemporal algorithm for network diffusion (STAND) is developed based on the survival model in this research. Both time and spatial distance are used as explanatory variables to simulate the diffusion process over two different network structures. The aim is to provide a more detailed measure of how different contagions are transmitted through various networks where nodes are geographic places at a large scale.
Parametrised Complexity of Model Checking and Satisfiability in Propositional Dependence Logic
Venue: arXiv cs.LO 2020
Year: 2020

In this paper, we initiate a systematic study of the parametrised complexity in the field of Dependence Logics which finds its origin in the Dependence Logic of Väänänen from 2007. We study a propositional variant of this logic (PDL) and investigate a variety of parametrisations with respect to the central decision problems. The model checking problem (MC) of PDL is NP-complete. The subject of this research is to identify a list of parametrisations (formula-size, treewidth, treedepth, team-size, number of variables) under which MC becomes fixed-parameter tractable. Furthermore, we show that the number of disjunctions or the arity of dependence atoms (dep-arity) as a parameter both yield a paraNP-completeness result. Then, we consider the satisfiability problem (SAT) showing a different picture: under team-size, or dep-arity SAT is paraNP-complete whereas under all other mentioned parameters the problem is in FPT. Finally, we introduce a variant of the satisfiability problem, asking for teams of a given size, and show for this problem an almost complete picture.
SPHINCS$^+$ post-quantum digital signature scheme with Streebog hash function
Venue: arXiv cs.CR 2020
Year: 2020

Many commonly used public key cryptosystems will become insecure once a scalable quantum computer is built. New cryptographic schemes that can guarantee protection against attacks with quantum computers, so-called post-quantum algorithms, have emerged in recent decades. One of the most promising candidates for a post-quantum signature scheme is SPHINCS$^+$, which is based on cryptographic hash functions. In this contribution, we analyze the use of the new Russian standardized hash function, known as Streebog, for the implementation of the SPHINCS$^+$ signature scheme. We provide a performance comparison with SHA-256-based instantiation and give benchmarks for various sets of parameters.