OpenRaiser/Intern-Atlas huggingface dataset:
Modified Hard Thresholding Pursuit with Regularization Assisted Support Identification
Venue: arXiv cs.IT 2020
Year: 2020

Hard thresholding pursuit (HTP) is a recently proposed iterative sparse recovery algorithm which is a result of combination of a support selection step from iterated hard thresholding (IHT) and an estimation step from the orthogonal matching pursuit (OMP). HTP has been seen to enjoy improved recovery guarantee along with enhanced speed of convergence. Much of the success of HTP can be attributed to its improved support selection capability due to the support selection step from IHT. In this paper, we propose a generalized HTP algorithm, called regularized HTP (RHTP), where the support selection step of HTP is replaced by a IHT-type support selection where the cost function is replaced by a regularized cost function, while the estimation step continues to use the least squares function. With decomposable regularizer, satisfying certain regularity conditions, the RHTP algorithm is shown to produce a sequence dynamically equivalent to a sequence evolving according to a HTP-like evolution, where the identification stage has a gradient premultiplied with a time-varying diagonal matrix. RHTP is also proven, both theoretically, and numerically, to enjoy faster convergence vis-a-vis HTP with both noiseless and noisy measurement vectors.
Real time Detection of Spectre and Meltdown Attacks Using Machine Learning
Venue: arXiv cs.CR 2020
Year: 2020

Recently discovered Spectre and meltdown attacks affects almost all processors by leaking confidential information to other processes through side-channel attacks. These vulnerabilities expose design flaws in the architecture of modern CPUs. To fix these design flaws, it is necessary to make changes in the hardware of modern processors which is a non-trivial task. Software mitigation techniques for these vulnerabilities cause significant performance degradation. In order to mitigate against Spectre and Meltdown attacks while retaining the performance benefits of modern processors, in this paper, we present a real-time detection mechanism for Spectre and Meltdown attacks by identifying the misuse of speculative execution and side-channel attacks. We use hardware performance counters and software events to monitor activity related to speculative execution, branch prediction, and cache interference. We use various machine learning models to analyze these events. These events produce a very distinctive pattern while the system is under attack; machine learning models are able to detect Meltdown and Spectre attacks under realistic load conditions with an accuracy of over 99%.
Perturbation Analysis of Gradient-based Adversarial Attacks
Venue: arXiv cs.LG 2020
Year: 2020

After the discovery of adversarial examples and their adverse effects on deep learning models, many studies focused on finding more diverse methods to generate these carefully crafted samples. Although empirical results on the effectiveness of adversarial example generation methods against defense mechanisms are discussed in detail in the literature, an in-depth study of the theoretical properties and the perturbation effectiveness of these adversarial attacks has largely been lacking. In this paper, we investigate the objective functions of three popular methods for adversarial example generation: the L-BFGS attack, the Iterative Fast Gradient Sign attack, and Carlini & Wagner's attack (CW). Specifically, we perform a comparative and formal analysis of the loss functions underlying the aforementioned attacks while laying out large-scale experimental results on ImageNet dataset. This analysis exposes (1) the faster optimization speed as well as the constrained optimization space of the cross-entropy loss, (2) the detrimental effects of using the signature of the cross-entropy loss on optimization precision as well as optimization space, and (3) the slow optimization speed of the logit loss in the context of adversariality. Our experiments reveal that the Iterative Fast Gradient Sign attack, which is thought to be fast for generating adversarial examples, is the worst attack in terms of the number of iterations required to create adversarial examples in the setting of equal perturbation. Moreover, our experiments show that the underlying loss function of CW, which is criticized for being substantially slower than other adversarial attacks, is not that much slower than other loss functions. Finally, we analyze how well neural networks can identify adversarial perturbations generated by the attacks under consideration, hereby revisiting the idea of adversarial retraining on ImageNet.
An ASR Guided Speech Intelligibility Measure for TTS Model Selection
Venue: arXiv cs.SD 2020
Year: 2020

The perceptual quality of neural text-to-speech (TTS) is highly dependent on the choice of the model during training. Selecting the model using a training-objective metric such as the least mean squared error does not always correlate with human perception. In this paper, we propose an objective metric based on the phone error rate (PER) to select the TTS model with the best speech intelligibility. The PER is computed between the input text to the TTS model, and the text decoded from the synthesized speech using an automatic speech recognition (ASR) model, which is trained on the same data as the TTS model. With the help of subjective studies, we show that the TTS model chosen with the least PER on validation split has significantly higher speech intelligibility compared to the model with the least training-objective metric loss. Finally, using the proposed PER and subjective evaluation, we show that the choice of best TTS model depends on the genre of the target domain text. All our experiments are conducted on a Hindi language dataset. However, the proposed model selection method is language independent.
Studying The Effect of MIL Pooling Filters on MIL Tasks
Venue: arXiv cs.CV 2020
Year: 2020

There are different multiple instance learning (MIL) pooling filters used in MIL models. In this paper, we study the effect of different MIL pooling filters on the performance of MIL models in real world MIL tasks. We designed a neural network based MIL framework with 5 different MIL pooling filters: `max', `mean', `attention', `distribution' and `distribution with attention'. We also formulated 5 different MIL tasks on a real world lymph node metastases dataset. We found that the performance of our framework in a task is different for different filters. We also observed that the performances of the five pooling filters are also different from task to task. Hence, the selection of a correct MIL pooling filter for each MIL task is crucial for better performance. Furthermore, we noticed that models with `distribution' and `distribution with attention' pooling filters consistently perform well in almost all of the tasks. We attribute this phenomena to the amount of information captured by `distribution' based pooling filters. While point estimate based pooling filters, like `max' and `mean', produce point estimates of distributions, `distribution' based pooling filters capture the full information in distributions. Lastly, we compared the performance of our neural network model with `distribution' pooling filter with the performance of the best MIL methods in the literature on classical MIL datasets and our model outperformed the others.
Two-Timescale Optimization for Intelligent Reflecting Surface Aided D2D Underlay Communication
Venue: arXiv cs.IT 2020
Year: 2020

The performance of a device-to-device (D2D) underlay communication system is limited by the co-channel interference between cellular users (CUs) and D2D devices. To address this challenge, an intelligent reflecting surface (IRS) aided D2D underlay system is studied in this paper. A two-timescale optimization scheme is proposed to reduce the required channel training and feedback overhead, where transmit beamforming at the base station (BS) and power control at the D2D transmitter are adapted to instantaneous effective channel state information (CSI); and the IRS phase shifts are adapted to slow-varying channel mean. Based on the two-timescale optimization scheme, we aim to maximize the D2D ergodic rate subject to a given outage probability constrained signal-to-interference-plus-noise ratio (SINR) target for the CU. The two-timescale problem is decoupled into two sub-problems, and the two sub-problems are solved iteratively with closed-form expressions. Numerical results verify that the two-timescale based optimization performs better than several baselines, and also demonstrate a favorable trade-off between system performance and CSI overhead.
Probability theory and public-key cryptography
Venue: arXiv cs.CR 2020
Year: 2020

In this short note, we address a common misconception at the interface of probability theory and public-key cryptography.
Bitwuzla at the SMT-COMP 2020
Venue: arXiv cs.LO 2020
Year: 2020

In this paper, we present Bitwuzla, our Satisfiability Modulo Theories (SMT) solver for the theories of bit-vectors, floating-points, arrays and uninterpreted functions and their combinations. We discuss selected features and provide details of its configuration and participation in the 2020 edition of the annual SMT competition.
Learning Efficient Representations of Mouse Movements to Predict User Attention
Venue: arXiv cs.HC 2020
Year: 2020

Tracking mouse cursor movements can be used to predict user attention on heterogeneous page layouts like SERPs. So far, previous work has relied heavily on handcrafted features, which is a time-consuming approach that often requires domain expertise. We investigate different representations of mouse cursor movements, including time series, heatmaps, and trajectory-based images, to build and contrast both recurrent and convolutional neural networks that can predict user attention to direct displays, such as SERP advertisements. Our models are trained over raw mouse cursor data and achieve competitive performance. We conclude that neural network models should be adopted for downstream tasks involving mouse cursor movements, since they can provide an invaluable implicit feedback signal for re-ranking and evaluation.
Surprisal-Triggered Conditional Computation with Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Autoregressive neural network models have been used successfully for sequence generation, feature extraction, and hypothesis scoring. This paper presents yet another use for these models: allocating more computation to more difficult inputs. In our model, an autoregressive model is used both to extract features and to predict observations in a stream of input observations. The surprisal of the input, measured as the negative log-likelihood of the current observation according to the autoregressive model, is used as a measure of input difficulty. This in turn determines whether a small, fast network, or a big, slow network, is used. Experiments on two speech recognition tasks show that our model can match the performance of a baseline in which the big network is always used with 15% fewer FLOPs.
The Ritva Blockchain: Enabling Confidential Transactions at Scale
Venue: arXiv cs.DC 2020
Year: 2020

The distributed ledger technology has been widely hailed as the break-through technology. It has realised a great number of application scenarios, and improved workflow of many domains. Nonetheless, there remain a few major concerns in adopting and deploying the distributed ledger technology at scale. In this white paper, we tackle two of them, namely the throughput scalability and confidentiality protection for transactions. We learn from the existing body of research, and build a scale-out blockchain platform that champions privacy called RVChain. RVChain takes advantage of trusted execution environment to offer confidentiality protection for transactions, and scales the throughput of the network in proportion with the number of network participants by supporting parallel shadow chains.
Object-Independent Human-to-Robot Handovers using Real Time Robotic Vision
Venue: arXiv cs.RO 2020
Year: 2020

We present an approach for safe and object-independent human-to-robot handovers using real time robotic vision and manipulation. We aim for general applicability with a generic object detector, a fast grasp selection algorithm and by using a single gripper-mounted RGB-D camera, hence not relying on external sensors. The robot is controlled via visual servoing towards the object of interest. Putting a high emphasis on safety, we use two perception modules: human body part segmentation and hand/finger segmentation. Pixels that are deemed to belong to the human are filtered out from candidate grasp poses, hence ensuring that the robot safely picks the object without colliding with the human partner. The grasp selection and perception modules run concurrently in real-time, which allows monitoring of the progress. In experiments with 13 objects, the robot was able to successfully take the object from the human in 81.9% of the trials.
Age-Based Coded Computation for Bias Reduction in Distributed Learning
Venue: arXiv cs.IT 2020
Year: 2020

Coded computation can be used to speed up distributed learning in the presence of straggling workers. Partial recovery of the gradient vector can further reduce the computation time at each iteration; however, this can result in biased estimators, which may slow down convergence, or even cause divergence. Estimator bias will be particularly prevalent when the straggling behavior is correlated over time, which results in the gradient estimators being dominated by a few fast servers. To mitigate biased estimators, we design a $timely$ dynamic encoding framework for partial recovery that includes an ordering operator that changes the codewords and computation orders at workers over time. To regulate the recovery frequencies, we adopt an $age$ metric in the design of the dynamic encoding scheme. We show through numerical results that the proposed dynamic encoding strategy increases the timeliness of the recovered computations, which as a result, reduces the bias in model updates, and accelerates the convergence compared to the conventional static partial recovery schemes.
AI-Powered Learning: Making Education Accessible, Affordable, and Achievable
Venue: arXiv cs.CY 2020
Year: 2020

We have developed an AI-powered socio-technical system for making online learning in higher education more accessible, affordable and achievable. In particular, we have developed four novel and intertwined AI technologies: (1) VERA, a virtual experimentation research assistant for supporting inquiry-based learning of scientific knowledge, (2) Jill Watson Q&A, a virtual teaching assistant for answering questions based on educational documents including the VERA user reference guide, (3) Jill Watson SA, a virtual social agent that promotes online interactions, and (4) Agent Smith, that helps generate a Jill Watson Q&A agent for new documents such as class syllabi. The results are positive: (i) VERA enhances ecological knowledge and is freely available online; (ii) Jill Watson Q&A has been used by >4,000 students in >12 online classes and saved teachers >500 hours of work; (iii) Jill Q&A and Jill Watson SA promote learner engagement, interaction, and community; and (iv). Agent Smith helps generate Jill Watson Q&A for a new syllabus within ~25 hours. Put together, these innovative technologies help make online learning simultaneously more accessible (by making materials available online), affordable (by saving teacher time), and achievable (by providing learning assistance and fostering student engagement).
On the Predictive Power of Neural Language Models for Human Real-Time Comprehension Behavior
Venue: arXiv cs.CL 2020
Year: 2020

Human reading behavior is tuned to the statistics of natural language: the time it takes human subjects to read a word can be predicted from estimates of the word's probability in context. However, it remains an open question what computational architecture best characterizes the expectations deployed in real time by humans that determine the behavioral signatures of reading. Here we test over two dozen models, independently manipulating computational architecture and training dataset size, on how well their next-word expectations predict human reading time behavior on naturalistic text corpora. We find that across model architectures and training dataset sizes the relationship between word log-probability and reading time is (near-)linear. We next evaluate how features of these models determine their psychometric predictive power, or ability to predict human reading behavior. In general, the better a model's next-word expectations, the better its psychometric predictive power. However, we find nontrivial differences across model architectures. For any given perplexity, deep Transformer models and n-gram models generally show superior psychometric predictive power over LSTM or structurally supervised neural models, especially for eye movement data. Finally, we compare models' psychometric predictive power to the depth of their syntactic knowledge, as measured by a battery of syntactic generalization tests developed using methods from controlled psycholinguistic experiments. Once perplexity is controlled for, we find no significant relationship between syntactic knowledge and predictive power. These results suggest that different approaches may be required to best model human real-time language comprehension behavior in naturalistic reading versus behavior for controlled linguistic materials designed for targeted probing of syntactic knowledge.
Hierarchical Clustering: a 0.585 Revenue Approximation
Venue: arXiv cs.DS 2020
Year: 2020

Hierarchical Clustering trees have been widely accepted as a useful form of clustering data, resulting in a prevalence of adopting fields including phylogenetics, image analysis, bioinformatics and more. Recently, Dasgupta (STOC 16') initiated the analysis of these types of algorithms through the lenses of approximation. Later, the dual problem was considered by Moseley and Wang (NIPS 17') dubbing it the Revenue goal function. In this problem, given a nonnegative weight $w_{ij}$ for each pair $i,j \in [n]=\{1,2, \ldots ,n\}$, the objective is to find a tree $T$ whose set of leaves is $[n]$ that maximizes the function $\sum_{i<j \in [n]} w_{ij} (n -|T_{ij}|)$, where $|T_{ij}|$ is the number of leaves in the subtree rooted at the least common ancestor of $i$ and $j$. In our work we consider the revenue goal function and prove the following results. First, we prove the existence of a bisection (i.e., a tree of depth 2 in which the root has two children, each being a parent of $n/2$ leaves) which approximates the general optimal tree solution up to a factor of $\frac{1}{2}$ (which is tight). Second, we apply this result in order to prove a $\frac{2}{3}p$ approximation for the general revenue problem, where $p$ is defined as the approximation ratio of the Max-Uncut Bisection problem. Since $p$ is known to be at least 0.8776 (Wu et al., 2015, Austrin et al., 2016), we get a 0.585 approximation algorithm for the revenue problem. This improves a sequence of earlier results which culminated in an 0.4246-approximation guarantee (Ahmadian et al., 2019).
Asymptotically Scale-invariant Multi-resolution Quantization
Venue: arXiv cs.IT 2020
Year: 2020

A multi-resolution quantizer is a sequence of quantizers where the output of a coarser quantizer can be deduced from the output of a finer quantizer. In this paper, we propose an asymptotically scale-invariant multi-resolution quantizer, which performs uniformly across any choice of average quantization step, when the length of the range of input numbers is large. Scale invariance is especially useful in worst case or adversarial settings, ensuring that the performance of the quantizer would not be affected greatly by small changes of storage or error requirements. We also show that the proposed quantizer achieves a tradeoff between rate and error that is arbitrarily close to the optimum.
Grafted network for person re-identification
Venue: arXiv cs.CV 2020
Year: 2020

Convolutional neural networks have shown outstanding effectiveness in person re-identification (re-ID). However, the models always have large number of parameters and much computation for mobile application. In order to relieve this problem, we propose a novel grafted network (GraftedNet), which is designed by grafting a high-accuracy rootstock and a light-weighted scion. The rootstock is based on the former parts of ResNet-50 to provide a strong baseline, while the scion is a new designed module, composed of the latter parts of SqueezeNet, to compress the parameters. To extract more discriminative feature representation, a joint multi-level and part-based feature is proposed. In addition, to train GraftedNet efficiently, we propose an accompanying learning method, by adding an accompanying branch to train the model in training and removing it in testing for saving parameters and computation. On three public person re-ID benchmarks (Market1501, DukeMTMC-reID and CUHK03), the effectiveness of GraftedNet are evaluated and its components are analyzed. Experimental results show that the proposed GraftedNet achieves 93.02%, 85.3% and 76.2% in Rank-1 and 81.6%, 74.7% and 71.6% in mAP, with only 4.6M parameters.
Fairness-Aware Explainable Recommendation over Knowledge Graphs
Venue: arXiv cs.IR 2020
Year: 2020

There has been growing attention on fairness considerations recently, especially in the context of intelligent decision making systems. Explainable recommendation systems, in particular, may suffer from both explanation bias and performance disparity. In this paper, we analyze different groups of users according to their level of activity, and find that bias exists in recommendation performance between different groups. We show that inactive users may be more susceptible to receiving unsatisfactory recommendations, due to insufficient training data for the inactive users, and that their recommendations may be biased by the training records of more active users, due to the nature of collaborative filtering, which leads to an unfair treatment by the system. We propose a fairness constrained approach via heuristic re-ranking to mitigate this unfairness problem in the context of explainable recommendation over knowledge graphs. We experiment on several real-world datasets with state-of-the-art knowledge graph-based explainable recommendation algorithms. The promising results show that our algorithm is not only able to provide high-quality explainable recommendations, but also reduces the recommendation unfairness in several respects.
Constraint Reductions
Venue: arXiv cs.AI 2020
Year: 2020

This is a commentary on the CP 2003 paper "Efficient cnf encoding of boolean cardinality constraints". After recalling its context, we outline a classification of Constraints with respect to their deductive power regarding General Arc Consistency (GAC).
Exploiting Class Labels to Boost Performance on Embedding-based Text Classification
Venue: arXiv cs.CL 2020
Year: 2020

Text classification is one of the most frequent tasks for processing textual data, facilitating among others research from large-scale datasets. Embeddings of different kinds have recently become the de facto standard as features used for text classification. These embeddings have the capacity to capture meanings of words inferred from occurrences in large external collections. While they are built out of external collections, they are unaware of the distributional characteristics of words in the classification dataset at hand, including most importantly the distribution of words across classes in training data. To make the most of these embeddings as features and to boost the performance of classifiers using them, we introduce a weighting scheme, Term Frequency-Category Ratio (TF-CR), which can weight high-frequency, category-exclusive words higher when computing word embeddings. Our experiments on eight datasets show the effectiveness of TF-CR, leading to improved performance scores over the well-known weighting schemes TF-IDF and KLD as well as over the absence of a weighting scheme in most cases.