OpenRaiser/Intern-Atlas huggingface dataset:
Short-packet Transmission via Variable-Length Codes in the Presence of Noisy Stop Feedback
Venue: arXiv cs.IT 2020
Year: 2020

We present an upper bound on the error probability achievable using variable-length stop feedback codes, for a fixed size of the information payload and a given constraint on the maximum latency and the average service time. Differently from the bound proposed in Polyanskiy et al. (2011), which pertains to the scenario in which the stop signal is sent over a noiseless feedback channel, our bound applies to the practically relevant setup in which the feedback link is noisy. By numerically evaluating our bound, we illustrate that, for fixed latency and reliability constraints, noise in the feedback link can cause a significant increase in the minimum average service time, to the extent that fixed-length codes without feedback may be preferable in some scenarios.
Multimodal Deep Learning for Mental Disorders Prediction from Audio Speech Samples
Venue: arXiv cs.LG 2020
Year: 2020

Key features of mental illnesses are reflected in speech. Our research focuses on designing a multimodal deep learning structure that automatically extracts salient features from recorded speech samples for predicting various mental disorders including depression, bipolar, and schizophrenia. We adopt a variety of pre-trained models to extract embeddings from both audio and text segments. We use several state-of-the-art embedding techniques including BERT, FastText, and Doc2VecC for the text representation learning and WaveNet and VGG-ish models for audio encoding. We also leverage huge auxiliary emotion-labeled text and audio corpora to train emotion-specific embeddings and use transfer learning in order to address the problem of insufficient annotated multimodal data available. All these embeddings are then combined into a joint representation in a multimodal fusion layer and finally a recurrent neural network is used to predict the mental disorder. Our results show that mental disorders can be predicted with acceptable accuracy through multimodal analysis of clinical interviews.
Efficient Computation of Optimal Temporal Walks under Waiting-Time Constraints
Venue: arXiv cs.DS 2020
Year: 2020

Node connectivity plays a central role in temporal network analysis. We provide a comprehensive study of various concepts of walks in temporal graphs, that is, graphs with fixed vertex sets but edge sets changing over time. Taking into account the temporal aspect leads to a rich set of optimization criteria for "shortest" walks. Extending and significantly broadening state-of-the-art work of Wu et al. [IEEE TKDE 2016], we provide an algorithm for computing optimal walks that is capable to deal with various optimization criteria and any linear combination of these. It runs in $O (|V| + |E| \log |E|)$ time where $|V|$ is the number of vertices and $|E|$ is the number of time edges. A central distinguishing factor to Wu et al.'s work is that our model allows to, motivated by real-world applications, respect waiting-time constraints for vertices, that is, the minimum and maximum waiting time allowed in intermediate vertices of a walk. Moreover, other than Wu et al. our algorithm also allows to search for walks that pass multiple subsequent edges in one time step, and it can optimize a richer set of optimization criteria. Our experimental studies indicate that our richer modeling can be achieved without significantly worsening the running time when compared to Wu et al.'s algorithms.
On the Downstream Performance of Compressed Word Embeddings
Venue: arXiv cs.LG 2020
Year: 2020

Compressing word embeddings is important for deploying NLP models in memory-constrained settings. However, understanding what makes compressed embeddings perform well on downstream tasks is challenging---existing measures of compression quality often fail to distinguish between embeddings that perform well and those that do not. We thus propose the eigenspace overlap score as a new measure. We relate the eigenspace overlap score to downstream performance by developing generalization bounds for the compressed embeddings in terms of this score, in the context of linear and logistic regression. We then show that we can lower bound the eigenspace overlap score for a simple uniform quantization compression method, helping to explain the strong empirical performance of this method. Finally, we show that by using the eigenspace overlap score as a selection criterion between embeddings drawn from a representative set we compressed, we can efficiently identify the better performing embedding with up to $2\times$ lower selection error rates than the next best measure of compression quality, and avoid the cost of training a model for each task of interest.
Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Advancing research in the emerging field of deep graph learning requires new tools to support tensor computation over graphs. In this paper, we present the design principles and implementation of Deep Graph Library (DGL). DGL distills the computational patterns of GNNs into a few generalized sparse tensor operations suitable for extensive parallelization. By advocating graph as the central programming abstraction, DGL can perform optimizations transparently. By cautiously adopting a framework-neutral design, DGL allows users to easily port and leverage the existing components across multiple deep learning frameworks. Our evaluation shows that DGL significantly outperforms other popular GNN-oriented frameworks in both speed and memory consumption over a variety of benchmarks and has little overhead for small scale workloads.
Reliability Bounds for Dependent Fading Wireless Channels
Venue: arXiv cs.IT 2020
Year: 2020

Unreliable fading wireless channels are the main challenge for strict performance guarantees in mobile communications. Diversity schemes including massive number of antennas, huge spectrum bands and multi-connectivity links are applied to improve the outage performance. The success of these approaches relies heavily on the joint distribution of the underlying fading channels. In this work, we consider the $\varepsilon$-outage capacity of slowly fading wireless diversity channels and provide lower and upper bounds for fixed marginal distributions of the individual channels. This answers the question about the best and worst case outage probability achievable over $n$ fading channels with a given distribution, e.g., Rayleigh fading, but not necessarily statistically independent. Interestingly, the best-case joint distribution enables achieving a zero-outage capacity greater than zero without channel state information at the transmitter for $n \geq 2$. Furthermore, the results are applied to characterize the worst- and best-case joint distribution for zero-outage capacity with perfect channel state information everywhere. All results are specialized to Rayleigh fading and compared to the standard assumption of independent and identically distributed fading component channels. The results show a significant impact of the joint distribution and the gap between worst- and best-case can be arbitrarily large.
Prospect Theory Based Crowdsourcing for Classification in the Presence of Spammers
Venue: arXiv cs.HC 2020
Year: 2020

We consider the $M$-ary classification problem via crowdsourcing, where crowd workers respond to simple binary questions and the answers are aggregated via decision fusion. The workers have a reject option to skip answering a question when they do not have the expertise, or when the confidence of answering that question correctly is low. We further consider that there are spammers in the crowd who respond to the questions with random guesses. Under the payment mechanism that encourages the reject option, we study the behavior of honest workers and spammers, whose objectives are to maximize their monetary rewards. To accurately characterize human behavioral aspects, we employ prospect theory to model the rationality of the crowd workers, whose perception of costs and probabilities are distorted based on some value and weight functions, respectively. Moreover, we estimate the number of spammers and employ a weighted majority voting decision rule, where we assign an optimal weight for every worker to maximize the system performance. The probability of correct classification and asymptotic system performance are derived. We also provide simulation results to demonstrate the effectiveness of our approach.
Joint Radar-Communications Strategies for Autonomous Vehicles
Venue: arXiv cs.IT 2020
Year: 2020

Self-driving cars constantly asses their environment in order to choose routes, comply with traffic regulations, and avoid hazards. To that aim, such vehicles are equipped with wireless communications transceivers as well as multiple sensors, including automotive radars. The fact that autonomous vehicles implement both radar and communications motivates designing these functionalities in a joint manner. Such dual function radar-communications (DFRC) designs are the focus of a large body of recent works. These approaches can lead to substantial gains in size, cost, power consumption, robustness, and performance, especially when both radar and communications operate in the same range, which is the case in vehicular applications. This article surveys the broad range of DFRC strategies and their relevance to autonomous vehicles. We identify the unique characteristics of automotive radar technologies and their combination with wireless communications requirements of self-driving cars. Then, we map the existing DFRC methods along with their pros and cons in the context of autonomous vehicles, and discuss the main challenges and possible research directions for realizing their full potential.
Binocular Rivalry Oriented Predictive Auto-Encoding Network for Blind Stereoscopic Image Quality Measurement
Venue: arXiv cs.MM 2020
Year: 2020

Stereoscopic image quality measurement (SIQM) has become increasingly important for guiding stereo image processing and commutation systems due to the widespread usage of 3D contents. Compared with conventional methods which are relied on hand-crafted features, deep learning oriented measurements have achieved remarkable performance in recent years. However, most existing deep SIQM evaluators are not specifically built for stereoscopic contents and consider little prior domain knowledge of the 3D human visual system (HVS) in network design. In this paper, we develop a Predictive Auto-encoDing Network (PAD-Net) for blind/No-Reference stereoscopic image quality measurement. In the first stage, inspired by the predictive coding theory that the cognition system tries to match bottom-up visual signal with top-down predictions, we adopt the encoder-decoder architecture to reconstruct the distorted inputs. Besides, motivated by the binocular rivalry phenomenon, we leverage the likelihood and prior maps generated from the predictive coding process in the Siamese framework for assisting SIQM. In the second stage, quality regression network is applied to the fusion image for acquiring the perceptual quality prediction. The performance of PAD-Net has been extensively evaluated on three benchmark databases and the superiority has been well validated on both symmetrically and asymmetrically distorted stereoscopic images under various distortion types.
Rate-Memory Trade-off for Multi-access Coded Caching with Uncoded Placement
Venue: arXiv cs.IT 2020
Year: 2020

We study a multi-access variant of the popular coded caching framework, which consists of a central server with a catalog of $N$ files, $K$ caches with limited memory $M$, and $K$ users such that each user has access to $L$ consecutive caches with a cyclic wrap-around and requests one file from the central server's catalog. The server assists in file delivery by transmitting a message of size $R$ over a shared error-free link and the goal is to characterize the optimal rate-memory trade-off. This setup was studied previously by Hachem et al., where an achievable rate and an information-theoretic lower bound were derived. However, the multiplicative gap between them was shown to scale linearly with the access degree $L$ and thus order-optimality could not be established. A series of recent works have used a natural mapping of the coded caching problem to the well-known index coding problem to derive tighter characterizations of the optimal rate-memory trade-off under the additional assumption that the caches store uncoded content. We follow a similar strategy for the multi-access framework and provide new bounds for the optimal rate-memory trade-off $R^*(M)$ over all uncoded placement policies. In particular, we derive a new achievable rate for any $L \ge 1$ and a new lower bound, which works for any uncoded placement policy and $L \ge K/2$. We then establish that the (multiplicative) gap between the new achievable rate and the lower bound is at most $2$ independent of all parameters, thus establishing an order-optimal characterization of $R^*(M)$ for any $L\ge K/2$. This is a significant improvement over the previously known gap result, albeit under the restriction of uncoded placement policies. Finally, we also characterize $R^*(M)$ exactly for a few special cases.
High Accuracy and High Fidelity Extraction of Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

In a model extraction attack, an adversary steals a copy of a remotely deployed machine learning model, given oracle prediction access. We taxonomize model extraction attacks around two objectives: *accuracy*, i.e., performing well on the underlying learning task, and *fidelity*, i.e., matching the predictions of the remote victim classifier on any input. To extract a high-accuracy model, we develop a learning-based attack exploiting the victim to supervise the training of an extracted model. Through analytical and empirical arguments, we then explain the inherent limitations that prevent any learning-based strategy from extracting a truly high-fidelity model---i.e., extracting a functionally-equivalent model whose predictions are identical to those of the victim model on all possible inputs. Addressing these limitations, we expand on prior work to develop the first practical functionally-equivalent extraction attack for direct extraction (i.e., without training) of a model's weights. We perform experiments both on academic datasets and a state-of-the-art image classifier trained with 1 billion proprietary images. In addition to broadening the scope of model extraction research, our work demonstrates the practicality of model extraction attacks against production-grade systems.
Learning a Spatial Field in Minimum Time with a Team of Robots
Venue: arXiv cs.RO 2020
Year: 2020

We study an informative path-planning problem where the goal is to minimize the time required to learn a spatially varying entity. We use Gaussian Process (GP) regression for learning the underlying field. Our goal is to ensure that the GP posterior variance, which is also the mean square error between the learned and actual fields, is below a predefined value. We study three versions of the problem. In the placement version, the objective is to minimize the number of measurement locations while ensuring that the posterior variance is below a predefined threshold. In the mobile robot version, we seek to minimize the total time required to visit and collect measurements from the measurement locations using a single robot. We also study a multi-robot version where the objective is to minimize the time required by the last robot to return to a common starting location called depot. By exploiting the properties of GP regression, we present constant-factor approximation algorithms. In addition to the theoretical results, we also compare the empirical performance using a real-world dataset, with other baseline strategies.
Efron-Stein PAC-Bayesian Inequalities
Venue: arXiv cs.LG 2020
Year: 2020

We prove semi-empirical concentration inequalities for random variables which are given as possibly nonlinear functions of independent random variables. These inequalities describe concentration of random variable in terms of the data/distribution-dependent Efron-Stein (ES) estimate of its variance and they do not require any additional assumptions on the moments. In particular, this allows us to state semi-empirical Bernstein type inequalities for general functions of unbounded random variables, which gives user-friendly concentration bounds for cases where related methods (e.g. bounded differences) might be more challenging to apply. We extend these results to Efron-Stein PAC-Bayesian inequalities which hold for arbitrary probability kernels that define a random, data-dependent choice of the function of interest. Finally, we demonstrate a number of applications, including PAC-Bayesian generalization bounds for unbounded loss functions, empirical Bernstein type generalization bounds, new truncation-free bounds for off-policy evaluation with Weighted Importance Sampling (WIS), and off-policy PAC-Bayesian learning with WIS.
Tensor Analysis with n-Mode Generalized Difference Subspace
Venue: arXiv cs.LG 2020
Year: 2020

The increasing use of multiple sensors, which produce a large amount of multi-dimensional data, requires efficient representation and classification methods. In this paper, we present a new method for multi-dimensional data classification that relies on two premises: 1) multi-dimensional data are usually represented by tensors, since this brings benefits from multilinear algebra and established tensor factorization methods; and 2) multilinear data can be described by a subspace of a vector space. The subspace representation has been employed for pattern-set recognition, and its tensor representation counterpart is also available in the literature. However, traditional methods do not use discriminative information of the tensors, degrading the classification accuracy. In this case, generalized difference subspace (GDS) provides an enhanced subspace representation by reducing data redundancy and revealing discriminative structures. Since GDS does not handle tensor data, we propose a new projection called n-mode GDS, which efficiently handles tensor data. We also introduce the n-mode Fisher score as a class separability index and an improved metric based on the geodesic distance for tensor data similarity. The experimental results on gesture and action recognition show that the proposed method outperforms methods commonly used in the literature without relying on pre-trained models or transfer learning.
Dense Extreme Inception Network: Towards a Robust CNN Model for Edge Detection
Venue: arXiv cs.CV 2020
Year: 2020

This paper proposes a Deep Learning based edge detector, which is inspired on both HED (Holistically-Nested Edge Detection) and Xception networks. The proposed approach generates thin edge-maps that are plausible for human eyes; it can be used in any edge detection task without previous training or fine tuning process. As a second contribution, a large dataset with carefully annotated edges has been generated. This dataset has been used for training the proposed approach as well the state-of-the-art algorithms for comparisons. Quantitative and qualitative evaluations have been performed on different benchmarks showing improvements with the proposed method when F-measure of ODS and OIS are considered.
Efficient Multivariate Bandit Algorithm with Path Planning
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we solve the arms exponential exploding issue in multivariate Multi-Armed Bandit (Multivariate-MAB) problem when the arm dimension hierarchy is considered. We propose a framework called path planning (TS-PP) which utilizes decision graph/trees to model arm reward success rate with m-way dimension interaction, and adopts Thompson sampling (TS) for heuristic search of arm selection. Naturally, it is quite straightforward to combat the curse of dimensionality using a serial processes that operates sequentially by focusing on one dimension per each process. For our best acknowledge, we are the first to solve Multivariate-MAB problem using graph path planning strategy and deploying alike Monte-Carlo tree search ideas. Our proposed method utilizing tree models has advantages comparing with traditional models such as general linear regression. Simulation studies validate our claim by achieving faster convergence speed, better efficient optimal arm allocation and lower cumulative regret.
Restricted Minimum Error Entropy Criterion for Robust Classification
Venue: arXiv cs.LG 2020
Year: 2020

The minimum error entropy (MEE) criterion has been verified as a powerful approach for non-Gaussian signal processing and robust machine learning. However, the implementation of MEE on robust classification is rather a vacancy in the literature. The original MEE only focuses on minimizing the Renyi's quadratic entropy of the error probability distribution function (PDF), which could cause failure in noisy classification tasks. To this end, we analyze the optimal error distribution in the presence of outliers for those classifiers with continuous errors, and introduce a simple codebook to restrict MEE so that it drives the error PDF towards the desired case. Half-quadratic based optimization and convergence analysis of the new learning criterion, called restricted MEE (RMEE), are provided. Experimental results with logistic regression and extreme learning machine are presented to verify the desirable robustness of RMEE.
Cumulative Quality Modeling for HTTP Adaptive Streaming
Venue: arXiv cs.MM 2020
Year: 2020

Thanks to the abundance of Web platforms and broadband connections, HTTP Adaptive Streaming has become the de facto choice for multimedia delivery nowadays. However, the visual quality of adaptive video streaming may fluctuate strongly during a session due to bandwidth fluctuations. So, it is important to evaluate the quality of a streaming session over time. In this paper, we propose a model to estimate the cumulative quality for HTTP Adaptive Streaming. In the model, a sliding window of video segments is employed as the basic building block. Through statistical analysis using a subjective dataset, we identify three important components of the cumulative quality model, namely the minimum window quality, the last window quality, and the average window quality. Experiment results show that the proposed model achieves high prediction performance and outperforms related quality models. In addition, another advantage of the proposed model is its simplicity and effectiveness for deployment in real-time estimation. The source code of the proposed model has been made available to the public at https://github.com/TranHuyen1191/CQM.
A review on ranking problems in statistical learning
Venue: arXiv cs.LG 2020
Year: 2020

Ranking problems, also known as preference learning problems, define a widely spread class of statistical learning problems with many applications, including fraud detection, document ranking, medicine, credit risk screening, image ranking or media memorability. In this article, we systematically review different types of instance ranking problems, i.e., ranking problems that require the prediction of an order of the response variables, and the corresponding loss functions resp. goodness criteria. We discuss the difficulties when trying to optimize those criteria. As for a detailed and comprehensive overview of existing machine learning techniques to solve such ranking problems, we systemize existing techniques and recapitulate the corresponding optimization problems in a unified notation. We also discuss to which of the ranking problems the respective algorithms are tailored and identify their strengths and limitations. Computational aspects and open research problems are also considered.