OpenRaiser/Intern-Atlas huggingface dataset:
Online Model Distillation for Efficient Video Inference
Venue: arXiv cs.CV 2020
Year: 2020

High-quality computer vision models typically address the problem of understanding the general distribution of real-world images. However, most cameras observe only a very small fraction of this distribution. This offers the possibility of achieving more efficient inference by specializing compact, low-cost models to the specific distribution of frames observed by a single camera. In this paper, we employ the technique of model distillation (supervising a low-cost student model using the output of a high-cost teacher) to specialize accurate, low-cost semantic segmentation models to a target video stream. Rather than learn a specialized student model on offline data from the video stream, we train the student in an online fashion on the live video, intermittently running the teacher to provide a target for learning. Online model distillation yields semantic segmentation models that closely approximate their Mask R-CNN teacher with 7 to 17$\times$ lower inference runtime cost (11 to 26$\times$ in FLOPs), even when the target video's distribution is non-stationary. Our method requires no offline pretraining on the target video stream, achieves higher accuracy and lower cost than solutions based on flow or video object segmentation, and can exhibit better temporal stability than the original teacher. We also provide a new video dataset for evaluating the efficiency of inference over long running video streams.
Neural Word Search in Historical Manuscript Collections
Venue: arXiv cs.CV 2020
Year: 2020

We address the problem of segmenting and retrieving word images in collections of historical manuscripts given a text query. This is commonly referred to as "word spotting". To this end, we first propose an end-to-end trainable model based on deep neural networks that we dub Ctrl-F-Net. The model simultaneously generates region proposals and embeds them into a word embedding space, wherein a search is performed. We further introduce a simplified version called Ctrl-F-Mini. It is faster with similar performance, though it is limited to more easily segmented manuscripts. We evaluate both models on common benchmark datasets and surpass the previous state of the art. Finally, in collaboration with historians, we employ the Ctrl-F-Net to search within a large manuscript collection of over 100 thousand pages, written across two centuries. With only 11 training pages, we enable large scale data collection in manuscript-based historical research. This results in a speed up of data collection and the number of manuscripts processed by orders of magnitude. Given the time consuming manual work required to study old manuscripts in the humanities, quick and robust tools for word spotting has the potential to revolutionise domains like history, religion and language.
Counting independent sets in graphs with bounded bipartite pathwidth
Venue: arXiv cs.DM 2020
Year: 2020

We show that a simple Markov chain, the Glauber dynamics, can efficiently sample independent sets almost uniformly at random in polynomial time for graphs in a certain class. The class is determined by boundedness of a new graph parameter called bipartite pathwidth. This result, which we prove for the more general hardcore distribution with fugacity $λ$, can be viewed as a strong generalisation of Jerrum and Sinclair's work on approximately counting matchings, that is, independent sets in line graphs. The class of graphs with bounded bipartite pathwidth includes claw-free graphs, which generalise line graphs. We consider two further generalisations of claw-free graphs and prove that these classes have bounded bipartite pathwidth. We also show how to extend all our results to polynomially-bounded vertex weights.
Multi-Dimensional Scaling on Groups
Venue: arXiv cs.LG 2020
Year: 2020

Leveraging the intrinsic symmetries in data for clear and efficient analysis is an important theme in signal processing and other data-driven sciences. A basic example of this is the ubiquity of the discrete Fourier transform which arises from translational symmetry (i.e. time-delay/phase-shift). Particularly important in this area is understanding how symmetries inform the algorithms that we apply to our data. In this paper we explore the behavior of the dimensionality reduction algorithm multi-dimensional scaling (MDS) in the presence of symmetry. We show that understanding the properties of the underlying symmetry group allows us to make strong statements about the output of MDS even before applying the algorithm itself. In analogy to Fourier theory, we show that in some cases only a handful of fundamental "frequencies" (irreducible representations derived from the corresponding group) contribute information for the MDS Euclidean embedding.
Learning Multiplication-free Linear Transformations
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we propose several dictionary learning algorithms for sparse representations that also impose specific structures on the learned dictionaries such that they are numerically efficient to use: reduced number of addition/multiplications and even avoiding multiplications altogether. We base our work on factorizations of the dictionary in highly structured basic building blocks (binary orthonormal, scaling and shear transformations) for which we can write closed-form solutions to the optimization problems that we consider. We show the effectiveness of our methods on image data where we can compare against well-known numerically efficient transforms such as the fast Fourier and the fast discrete cosine transforms.
MergeDTS: A Method for Effective Large-Scale Online Ranker Evaluation
Venue: arXiv cs.IR 2020
Year: 2020

Online ranker evaluation is one of the key challenges in information retrieval. While the preferences of rankers can be inferred by interleaving methods, the problem of how to effectively choose the ranker pair that generates the interleaved list without degrading the user experience too much is still challenging. On the one hand, if two rankers have not been compared enough, the inferred preference can be noisy and inaccurate. On the other, if two rankers are compared too many times, the interleaving process inevitably hurts the user experience too much. This dilemma is known as the exploration versus exploitation tradeoff. It is captured by the $K$-armed dueling bandit problem, which is a variant of the $K$-armed bandit problem, where the feedback comes in the form of pairwise preferences. Today's deployed search systems can evaluate a large number of rankers concurrently, and scaling effectively in the presence of numerous rankers is a critical aspect of $K$-armed dueling bandit problems. In this paper, we focus on solving the large-scale online ranker evaluation problem under the so-called Condorcet assumption, where there exists an optimal ranker that is preferred to all other rankers. We propose Merge Double Thompson Sampling (MergeDTS), which first utilizes a divide-and-conquer strategy that localizes the comparisons carried out by the algorithm to small batches of rankers, and then employs Thompson Sampling (TS) to reduce the comparisons between suboptimal rankers inside these small batches. The effectiveness (regret) and efficiency (time complexity) of MergeDTS are extensively evaluated using examples from the domain of online evaluation for web search. Our main finding is that for large-scale Condorcet ranker evaluation problems, MergeDTS outperforms the state-of-the-art dueling bandit algorithms.
Facial Expression Recognition using Facial Landmark Detection and Feature Extraction via Neural Networks
Venue: arXiv cs.CV 2020
Year: 2020

The proposed framework in this paper has the primary objective of classifying the facial expression shown by a person. These classifiable expressions can be any one of the six universal emotions along with the neutral emotion. After the initial facial localization is performed, facial landmark detection and feature extraction are applied where in the landmarks are determined to be the fiducial features: the eyebrows, eyes, nose and lips. This is primarily done using state-of-the-art facial landmark detection algorithms as well as traditional edge and corner point detection methods using Sobel filters and Shi Tomasi corner point detection methods respectively. This leads to generation of input feature vectors being formulated using Euclidean distances and trained into a Multi-Layer Perceptron (MLP) neural network in order to classify the expression being displayed. The results achieved have further dealt with higher uniformity in certain emotions and the inherently subjective nature of expression.
Prior-Knowledge and Attention-based Meta-Learning for Few-Shot Learning
Venue: arXiv cs.CV 2020
Year: 2020

Recently, meta-learning has been shown as a promising way to solve few-shot learning. In this paper, inspired by the human cognition process which utilizes both prior-knowledge and vision attention in learning new knowledge, we present a novel paradigm of meta-learning approach with three developments to introduce attention mechanism and prior-knowledge for meta-learning. In our approach, prior-knowledge is responsible for helping meta-learner expressing the input data into high-level representation space, and attention mechanism enables meta-learner focusing on key features of the data in the representation space. Compared with existing meta-learning approaches that pay little attention to prior-knowledge and vision attention, our approach alleviates the meta-learner's few-shot cognition burden. Furthermore, a Task-Over-Fitting (TOF) problem, which indicates that the meta-learner has poor generalization on different K-shot learning tasks, is discovered and we propose a Cross-Entropy across Tasks (CET) metric to model and solve the TOF problem. Extensive experiments demonstrate that we improve the meta-learner with state-of-the-art performance on several few-shot learning benchmarks, and at the same time the TOF problem can also be released greatly.
Fast Mitochondria Detection for Connectomics
Venue: arXiv cs.CV 2020
Year: 2020

High-resolution connectomics data allows for the identification of dysfunctional mitochondria which are linked to a variety of diseases such as autism or bipolar. However, manual analysis is not feasible since datasets can be petabytes in size. We present a fully automatic mitochondria detector based on a modified U-Net architecture that yields high accuracy and fast processing times. We evaluate our method on multiple real-world connectomics datasets, including an improved version of the EPFL mitochondria benchmark. Our results show an Jaccard index of up to 0.90 with inference times lower than 16ms for a 512x512px image tile. This speed is faster than the acquisition speed of modern electron microscopes, enabling mitochondria detection in real-time. Our detector ranks first for real-time detection when compared to previous works and data, results, and code are openly available.
Deep reinforcement learning for search, recommendation, and online advertising: a survey
Venue: arXiv cs.IR 2020
Year: 2020

Search, recommendation, and online advertising are the three most important information-providing mechanisms on the web. These information seeking techniques, satisfying users' information needs by suggesting users personalized objects (information or services) at the appropriate time and place, play a crucial role in mitigating the information overload problem. With recent great advances in deep reinforcement learning (DRL), there have been increasing interests in developing DRL based information seeking techniques. These DRL based techniques have two key advantages -- (1) they are able to continuously update information seeking strategies according to users' real-time feedback, and (2) they can maximize the expected cumulative long-term reward from users where reward has different definitions according to information seeking applications such as click-through rate, revenue, user satisfaction and engagement. In this paper, we give an overview of deep reinforcement learning for search, recommendation, and online advertising from methodologies to applications, review representative algorithms, and discuss some appealing research directions.
Found in Translation: Learning Robust Joint Representations by Cyclic Translations Between Modalities
Venue: arXiv cs.LG 2020
Year: 2020

Multimodal sentiment analysis is a core research area that studies speaker sentiment expressed from the language, visual, and acoustic modalities. The central challenge in multimodal learning involves inferring joint representations that can process and relate information from these modalities. However, existing work learns joint representations by requiring all modalities as input and as a result, the learned representations may be sensitive to noisy or missing modalities at test time. With the recent success of sequence to sequence (Seq2Seq) models in machine translation, there is an opportunity to explore new ways of learning joint representations that may not require all input modalities at test time. In this paper, we propose a method to learn robust joint representations by translating between modalities. Our method is based on the key insight that translation from a source to a target modality provides a method of learning joint representations using only the source modality as input. We augment modality translations with a cycle consistency loss to ensure that our joint representations retain maximal information from all modalities. Once our translation model is trained with paired multimodal data, we only need data from the source modality at test time for final sentiment prediction. This ensures that our model remains robust from perturbations or missing information in the other modalities. We train our model with a coupled translation-prediction objective and it achieves new state-of-the-art results on multimodal sentiment analysis datasets: CMU-MOSI, ICT-MMMO, and YouTube. Additional experiments show that our model learns increasingly discriminative joint representations with more input modalities while maintaining robustness to missing or perturbed modalities.
Multichannel Online Dereverberation based on Spectral Magnitude Inverse Filtering
Venue: arXiv cs.SD 2020
Year: 2020

This paper addresses the problem of multichannel online dereverberation. The proposed method is carried out in the short-time Fourier transform (STFT) domain, and for each frequency band independently. In the STFT domain, the time-domain room impulse response is approximately represented by the convolutive transfer function (CTF). The multichannel CTFs are adaptively identified based on the cross-relation method, and using the recursive least square criterion. Instead of the complex-valued CTF convolution model, we use a nonnegative convolution model between the STFT magnitude of the source signal and the CTF magnitude, which is just a coarse approximation of the former model, but is shown to be more robust against the CTF perturbations. Based on this nonnegative model, we propose an online STFT magnitude inverse filtering method. The inverse filters of the CTF magnitude are formulated based on the multiple-input/output inverse theorem (MINT), and adaptively estimated based on the gradient descent criterion. Finally, the inverse filtering is applied to the STFT magnitude of the microphone signals, obtaining an estimate of the STFT magnitude of the source signal. Experiments regarding both speech enhancement and automatic speech recognition are conducted, which demonstrate that the proposed method can effectively suppress reverberation, even for the difficult case of a moving speaker.
Formal Methods in Dependable Systems Engineering: A Survey of Professionals from Europe and North America
Venue: arXiv cs.SE 2020
Year: 2020

Context: Formal methods (FMs) have been around for a while, still being unclear how to leverage their benefits, overcome their challenges, and set new directions for their improvement towards a more successful transfer into practice. Objective: We study the use of formal methods in mission-critical software domains, examining industrial and academic views. Method: We perform a cross-sectional on-line survey. Results: Our results indicate an increased intent to apply FMs in industry, suggesting a positively perceived usefulness. But the results also indicate a negatively perceived ease of use. Scalability, skills, and education seem to be among the key challenges to support this intent. Conclusions: We present the largest study of this kind so far (N = 216), and our observations provide valuable insights, highlighting directions for future theoretical and empirical research of formal methods. Our findings are strongly coherent with earlier observations by Austin and Parkin (1993).
How to Achieve High Classification Accuracy with Just a Few Labels: A Semi-supervised Approach Using Sampled Packets
Venue: arXiv cs.NI 2020
Year: 2020

Network traffic classification, which has numerous applications from security to billing and network provisioning, has become a cornerstone of today's computer networks. Previous studies have developed traffic classification techniques using classical machine learning algorithms and deep learning methods when large quantities of labeled data are available. However, capturing large labeled datasets is a cumbersome and time-consuming process. In this paper, we propose a semi-supervised approach that obviates the need for large labeled datasets. We first pre-train a model on a large unlabeled dataset where the input is the time series features of a few sampled packets. Then the learned weights are transferred to a new model that is re-trained on a small labeled dataset. We show that our semi-supervised approach achieves almost the same accuracy as a fully-supervised method with a large labeled dataset, though we use only 20 samples per class. In tests based on a dataset generated from the more challenging QUIC protocol, our approach yields 98% accuracy. To show its efficacy, we also test our approach on two public datasets. Moreover, we study three different sampling techniques and demonstrate that sampling packets from an arbitrary portion of a flow is sufficient for classification.
On approximate data reduction for the Rural Postman Problem: Theory and experiments
Venue: arXiv cs.DS 2020
Year: 2020

Given an undirected graph with edge weights and a subset $R$ of its edges, the Rural Postman Problem (RPP) is to find a closed walk of minimum total weight containing all edges of $R$. We prove that RPP is WK[1]-complete parameterized by the number and cost $d$ of edges traversed additionally to the required ones. Thus, in particular, RPP instances cannot be polynomial-time compressed to instances of size polynomial in $d$ unless the polynomial-time hierarchy collapses. In contrast, denoting by $b\leq 2d$ the number of vertices incident to an odd number of edges of $R$ and by $c\leq d$ the number of connected components formed by the edges in $R$, we show how to reduce any RPP instance $I$ to an RPP instance $I'$ with $2b+O(c/\varepsilon)$ vertices in $O(n^3)$ time so that any $α$-approximate solution for $I'$ gives an $α(1+\varepsilon)$-approximate solution for $I$, for any $α\geq 1$ and $\varepsilon>0$. That is, we provide a polynomial-size approximate kernelization scheme (PSAKS). We experimentally evaluate it on wide-spread benchmark data sets as well as on two real snow plowing instances from Berlin. On instances with few connected components, the number of vertices and required edges is reduced to about $50\,\%$ at a $1\,\%$ solution quality loss. We also make first steps towards a PSAKS for the parameter $c$.
Residual Dense Network for Image Restoration
Venue: arXiv cs.CV 2020
Year: 2020

Convolutional neural network has recently achieved great success for image restoration (IR) and also offered hierarchical features. However, most deep CNN based IR models do not make full use of the hierarchical features from the original low-quality images, thereby achieving relatively-low performance. In this paper, we propose a novel residual dense network (RDN) to address this problem in IR. We fully exploit the hierarchical features from all the convolutional layers. Specifically, we propose residual dense block (RDB) to extract abundant local features via densely connected convolutional layers. RDB further allows direct connections from the state of preceding RDB to all the layers of current RDB, leading to a contiguous memory mechanism. To adaptively learn more effective features from preceding and current local features and stabilize the training of wider network, we proposed local feature fusion in RDB. After fully obtaining dense local features, we use global feature fusion to jointly and adaptively learn global hierarchical features in a holistic way. We demonstrate the effectiveness of RDN with several representative IR applications, single image super-resolution, Gaussian image denoising, image compression artifact reduction, and image deblurring. Experiments on benchmark and real-world datasets show that our RDN achieves favorable performance against state-of-the-art methods for each IR task quantitatively and visually.
Synthesizing Robust Domains of Attraction for State-Constrained Perturbed Polynomial Systems
Venue: arXiv cs.SY 2020
Year: 2020

In this paper we propose a novel semi-definite programming based method to compute robust domains of attraction for state-constrained perturbed polynomial systems. A robust domain of attraction is a set of states such that every trajectory starting from it will approach an equilibrium while never violating a specified state constraint, regardless of the actual perturbation. The semi-definite program is constructed by relaxing a generalized Zubov's equation. The existence of solutions to the constructed semi-definite program is guaranteed and there exists a sequence of solutions such that their strict one sub-level sets inner-approximate the interior of the maximal robust domain of attraction in measure under appropriate assumptions. Some illustrative examples demonstrate the performance of our method.
On the Approximability of Time Disjoint Walks
Venue: arXiv cs.DS 2020
Year: 2020

We introduce the combinatorial optimization problem Time Disjoint Walks (TDW), which has applications in collision-free routing of discrete objects (e.g., autonomous vehicles) over a network. This problem takes as input a digraph $G$ with positive integer arc lengths, and $k$ pairs of vertices that each represent a trip demand from a source to a destination. The goal is to find a walk and delay for each demand so that no two trips occupy the same vertex at the same time, and so that a min-max or min-sum objective over the trip durations is realized. We focus here on the min-sum variant of Time Disjoint Walks, although most of our results carry over to the min-max case. We restrict our study to various subclasses of DAGs, and observe that there is a sharp complexity boundary between Time Disjoint Walks on oriented stars and on oriented stars with the central vertex replaced by a path. In particular, we present a poly-time algorithm for min-sum and min-max TDW on the former, but show that min-sum TDW on the latter is NP-hard. Our main hardness result is that for DAGs with max degree $Δ\leq3$, min-sum Time Disjoint Walks is APX-hard. We present a natural approximation algorithm for the same class, and provide a tight analysis. In particular, we prove that it achieves an approximation ratio of $Θ(k/\log k)$ on bounded-degree DAGs, and $Θ(k)$ on DAGs and bounded-degree digraphs.