OpenRaiser/Intern-Atlas huggingface dataset:
Generalized Few-Shot Video Classification with Video Retrieval and Feature Generation
Venue: arXiv cs.CV 2021
Year: 2021

Few-shot learning aims to recognize novel classes from a few examples. Although significant progress has been made in the image domain, few-shot video classification is relatively unexplored. We argue that previous methods underestimate the importance of video feature learning and propose to learn spatiotemporal features using a 3D CNN. Proposing a two-stage approach that learns video features on base classes followed by fine-tuning the classifiers on novel classes, we show that this simple baseline approach outperforms prior few-shot video classification methods by over 20 points on existing benchmarks. To circumvent the need of labeled examples, we present two novel approaches that yield further improvement. First, we leverage tag-labeled videos from a large dataset using tag retrieval followed by selecting the best clips with visual similarities. Second, we learn generative adversarial networks that generate video features of novel classes from their semantic embeddings. Moreover, we find existing benchmarks are limited because they only focus on 5 novel classes in each testing episode and introduce more realistic benchmarks by involving more novel classes, i.e. few-shot learning, as well as a mixture of novel and base classes, i.e. generalized few-shot learning. The experimental results show that our retrieval and feature generation approach significantly outperform the baseline approach on the new benchmarks.
Accuracy Prediction with Non-neural Model for Neural Architecture Search
Venue: arXiv cs.LG 2021
Year: 2021

Neural architecture search (NAS) with an accuracy predictor that predicts the accuracy of candidate architectures has drawn increasing attention due to its simplicity and effectiveness. Previous works usually employ neural network-based predictors which require more delicate design and are easy to overfit. Considering that most architectures are represented as sequences of discrete symbols which are more like tabular data and preferred by non-neural predictors, in this paper, we study an alternative approach which uses non-neural model for accuracy prediction. Specifically, as decision tree based models can better handle tabular data, we leverage gradient boosting decision tree (GBDT) as the predictor for NAS. We demonstrate that the GBDT predictor can achieve comparable (if not better) prediction accuracy than neural network based predictors. Moreover, considering that a compact search space can ease the search process, we propose to prune the search space gradually according to important features derived from GBDT. In this way, NAS can be performed by first pruning the search space and then searching a neural architecture, which is more efficient and effective. Experiments on NASBench-101 and ImageNet demonstrate the effectiveness of using GBDT as predictor for NAS: (1) On NASBench-101, it is 22x, 8x, and 6x more sample efficient than random search, regularized evolution, and Monte Carlo Tree Search (MCTS) in finding the global optimum; (2) It achieves 24.2% top-1 error rate on ImageNet, and further achieves 23.4% top-1 error rate on ImageNet when enhanced with search space pruning. Code is provided at https://github.com/renqianluo/GBDT-NAS.
A Deep Joint Sparse Non-negative Matrix Factorization Framework for Identifying the Common and Subject-specific Functional Units of Tongue Motion During Speech
Venue: arXiv cs.CV 2021
Year: 2021

Intelligible speech is produced by creating varying internal local muscle groupings -- i.e., functional units -- that are generated in a systematic and coordinated manner. There are two major challenges in characterizing and analyzing functional units.~First, due to the complex and convoluted nature of tongue structure and function, it is of great importance to develop a method that can accurately decode complex muscle coordination patterns during speech. Second, it is challenging to keep identified functional units across subjects comparable due to their substantial variability. In this work, to address these challenges, we develop a new deep learning framework to identify common and subject-specific functional units of tongue motion during speech.~Our framework hinges on joint deep graph-regularized sparse non-negative matrix factorization (NMF) using motion quantities derived from displacements by tagged Magnetic Resonance Imaging. More specifically, we transform NMF with sparse and graph regularizations into modular architectures akin to deep neural networks by means of unfolding the Iterative Shrinkage-Thresholding Algorithm to learn interpretable building blocks and associated weighting map. We then apply spectral clustering to common and subject-specific weighting maps from which we jointly determine the common and subject-specific functional units. Experiments carried out with simulated datasets show that the proposed method achieved on par or better clustering performance over the comparison methods. Experiments carried out with in vivo tongue motion data show that the proposed method can determine the common and subject-specific functional units with increased interpretability and decreased size variability.
Practical Budgeted Submodular Maximization
Venue: arXiv cs.DS 2021
Year: 2021

We consider the problem of maximizing a non-negative monotone submodular function subject to a knapsack constraint, which is also known as the Budgeted Submodular Maximization (BSM) problem. Sviridenko (2004) showed that by guessing 3 appropriate elements of an optimal solution, and then executing a greedy algorithm, one can obtain the optimal approximation ratio of $α=1-1/e\approx 0.632$ for BSM. However, the need to guess (by enumeration) 3 elements makes the algorithm of Sviridenko impractical as it leads to a time complexity of $O(n^5)$ (which can be slightly improved using the thresholding technique of Badanidiyuru & Vondrak (2014), but only to roughly $O(n^4)$). Our main results in this paper show that fewer guesses suffice. Specifically, by making only 2 guesses, we get the same optimal approximation ratio of $α$ with an improved time complexity of roughly $O(n^3)$. Furthermore, by making only a single guess, we get an almost as good approximation ratio of $0.6174>0.9767α$ in roughly $O(n^2)$ time. Prior to our work, the only algorithms that were known to obtain an approximation ratio close to $α$ for BSM were the algorithm of Sviridenko and an algorithm of Ene & Nguyen (2019) that achieves $(α-ε)$-approximation. However, the algorithm of Ene & Nguyen requires ${(1/ε)}^{O(1/ε^4)}n\log^2 n$ time, and hence, is of theoretical interest only as ${(1/ε)}^{O(1/ε^4)}$ is huge even for moderate values of $ε$. In contrast, all the algorithms we analyze are simple and parallelizable, which makes them good candidates for practical use. Recently, Tang et al. (2020) studied a simple greedy algorithm that already has a long research history, and proved that its approximation ratio is at least 0.405. We improve over this result, and show that the approximation ratio of this algorithm is within the range [0.427, 0.462].
Bribery and Control in Stable Marriage
Venue: arXiv cs.GT 2021
Year: 2021

We initiate the study of external manipulations in Stable Marriage by considering several manipulative actions as well as several manipulation goals. For instance, one goal is to make sure that a given pair of agents is matched in a stable solution, and this may be achieved by the manipulative action of reordering some agents' preference lists. We present a comprehensive study of the computational complexity of all problems arising in this way. We find several polynomial-time solvable cases as well as NP-hard ones. For the NP-hard cases, focusing on the natural parameter budget (that is, the number of manipulative actions one is allowed to perform), we also conduct a parameterized complexity analysis and encounter mostly parameterized hardness results.
RulePad: Interactive Authoring of Checkable Design Rules
Venue: arXiv cs.SE 2021
Year: 2021

Good documentation offers the promise of enabling developers to easily understand design decisions. Unfortunately, in practice, design documents are often rarely updated, becoming inaccurate, incomplete, and untrustworthy. A better solution is to enable developers to write down design rules which are checked against code for consistency. But existing rule checkers require learning specialized query languages or program analysis frameworks, creating a barrier to writing project-specific rules. We introduce two new techniques for authoring design rules: snippet-based authoring and semi-natural-language authoring. In snippet-based authoring, developers specify characteristics of elements to match by writing partial code snippets. In semi-natural language authoring, a textual representation offers a representation for understanding design rules and resolving ambiguities. We implemented these approaches in RulePad. To evaluate RulePad, we conducted a between-subjects study with 14 participants comparing RulePad to the PMD Designer, a utility for writing rules in a popular rule checker. We found that those with RulePad were able to successfully author 13 times more query elements in significantly less time and reported being significantly more willing to use RulePad in their everyday work.
Multimodal price prediction
Venue: arXiv cs.CV 2021
Year: 2021

Price prediction is one of the examples related to forecasting tasks and is a project based on data science. Price prediction analyzes data and predicts the cost of new products. The goal of this research is to achieve an arrangement to predict the price of a cellphone based on its specifications. So, five deep learning models are proposed to predict the price range of a cellphone, one unimodal and four multimodal approaches. The multimodal methods predict the prices based on the graphical and non-graphical features of cellphones that have an important effect on their valorizations. Also, to evaluate the efficiency of the proposed methods, a cellphone dataset has been gathered from GSMArena. The experimental results show 88.3% F1-score, which confirms that multimodal learning leads to more accurate predictions than state-of-the-art techniques.
Mechanisms for Hiding Sensitive Genotypes with Information-Theoretic Privacy
Venue: arXiv cs.IT 2021
Year: 2021

Motivated by the growing availability of personal genomics services, we study an information-theoretic privacy problem that arises when sharing genomic data: a user wants to share his or her genome sequence while keeping the genotypes at certain positions hidden, which could otherwise reveal critical health-related information. A straightforward solution of erasing (masking) the chosen genotypes does not ensure privacy, because the correlation between nearby positions can leak the masked genotypes. We introduce an erasure-based privacy mechanism with perfect information-theoretic privacy, whereby the released sequence is statistically independent of the sensitive genotypes. Our mechanism can be interpreted as a locally-optimal greedy algorithm for a given processing order of sequence positions, where utility is measured by the number of positions released without erasure. We show that finding an optimal order is NP-hard in general and provide an upper bound on the optimal utility. For sequences from hidden Markov models, a standard modeling approach in genetics, we propose an efficient algorithmic implementation of our mechanism with complexity polynomial in sequence length. Moreover, we illustrate the robustness of the mechanism by bounding the privacy leakage from erroneous prior distributions. Our work is a step towards more rigorous control of privacy in genomic data sharing.
GLOW : Global Weighted Self-Attention Network for Web Search
Venue: arXiv cs.IR 2021
Year: 2021

Deep matching models aim to facilitate search engines retrieving more relevant documents by mapping queries and documents into semantic vectors in the first-stage retrieval. When leveraging BERT as the deep matching model, the attention score across two words are solely built upon local contextualized word embeddings. It lacks prior global knowledge to distinguish the importance of different words, which has been proved to play a critical role in information retrieval tasks. In addition to this, BERT only performs attention across sub-words tokens which weakens whole word attention representation. We propose a novel Global Weighted Self-Attention (GLOW) network for web document search. GLOW fuses global corpus statistics into the deep matching model. By adding prior weights into attention generation from global information, like BM25, GLOW successfully learns weighted attention scores jointly with query matrix $Q$ and key matrix $K$. We also present an efficient whole word weight sharing solution to bring prior whole word knowledge into sub-words level attention. It aids Transformer to learn whole word level attention. To make our models applicable to complicated web search scenarios, we introduce combined fields representation to accommodate documents with multiple fields even with variable number of instances. We demonstrate GLOW is more efficient to capture the topical and semantic representation both in queries and documents. Intrinsic evaluation and experiments conducted on public data sets reveal GLOW to be a general framework for document retrieve task. It significantly outperforms BERT and other competitive baselines by a large margin while retaining the same model complexity with BERT.
Online Template Attacks: Revisited
Venue: arXiv cs.CR 2021
Year: 2021

An online template attack (OTA) is a powerful technique previously used to attack elliptic curve scalar multiplication algorithms. This attack has only been analyzed in the realm of power consumption and EM side channels, where the signals leak related to the value being processed. However, microarchitecture signals have no such feature, invalidating some assumptions from previous OTA works. In this paper, we revisit previous OTA descriptions, proposing a generic framework and evaluation metrics for any side-channel signal. Our analysis reveals OTA features not previously considered, increasing its application scenarios and requiring a fresh countermeasure analysis to prevent it. In this regard, we demonstrate that OTAs can work in the backward direction, allowing to mount an augmented projective coordinates attack with respect to the proposal by Naccache, Smart and Stern (Eurocrypt 2004). This demonstrates that randomizing the initial targeted algorithm state does not prevent the attack as believed in previous works. We analyze three libraries libgcrypt, mbedTLS, and wolfSSL using two microarchitecture side channels. For the libgcrypt case, we target its EdDSA implementation using Curve25519 twist curve. We obtain similar results for mbedTLS and wolfSSL with curve secp256r1. For each library, we execute extensive attack instances that are able to recover the complete scalar in all cases using a single trace. This work demonstrates that microarchitecture online template attacks are also very powerful in this scenario, recovering secret information without knowing a leakage model. This highlights the importance of developing secure-by-default implementations, instead of fix-on-demand ones.
M-Evolve: Structural-Mapping-Based Data Augmentation for Graph Classification
Venue: arXiv cs.LG 2021
Year: 2021

Graph classification, which aims to identify the category labels of graphs, plays a significant role in drug classification, toxicity detection, protein analysis etc. However, the limitation of scale in the benchmark datasets makes it easy for graph classification models to fall into over-fitting and undergeneralization. To improve this, we introduce data augmentation on graphs (i.e. graph augmentation) and present four methods:random mapping, vertex-similarity mapping, motif-random mapping and motif-similarity mapping, to generate more weakly labeled data for small-scale benchmark datasets via heuristic transformation of graph structures. Furthermore, we propose a generic model evolution framework, named M-Evolve, which combines graph augmentation, data filtration and model retraining to optimize pre-trained graph classifiers. Experiments on six benchmark datasets demonstrate that the proposed framework helps existing graph classification models alleviate over-fitting and undergeneralization in the training on small-scale benchmark datasets, which successfully yields an average improvement of 3 - 13% accuracy on graph classification tasks.
Migratable AI: Effect of identity and information migration on users perception of conversational AI agents
Venue: arXiv cs.CY 2021
Year: 2021

Conversational AI agents are proliferating, embodying a range of devices such as smart speakers, smart displays, robots, cars, and more. We can envision a future where a personal conversational agent could migrate across different form factors and environments to always accompany and assist its user to support a far more continuous, personalized, and collaborative experience. This opens the question of what properties of a conversational AI agent migrates across forms, and how it would impact user perception. To explore this, we developed a Migratable AI system where a user's information and/or the agent's identity can be preserved as it migrates across form factors to help its user with a task. We designed a 2x2 between-subjects study to explore the effects of information migration and identity migration on user perceptions of trust, competence, likeability, and social presence. Our results suggest that identity migration had a positive effect on trust, competence, and social presence, while information migration had a positive effect on trust, competence, and likeability. Overall, users report the highest trust, competence, likeability, and social presence towards the conversational agent when both identity and information were migrated across embodiments.
AMITE: A Novel Polynomial Expansion for Analyzing Neural Network Nonlinearities
Venue: arXiv cs.LG 2021
Year: 2021

Polynomial expansions are important in the analysis of neural network nonlinearities. They have been applied thereto addressing well-known difficulties in verification, explainability, and security. Existing approaches span classical Taylor and Chebyshev methods, asymptotics, and many numerical approaches. We find that while these individually have useful properties such as exact error formulas, adjustable domain, and robustness to undefined derivatives, there are no approaches that provide a consistent method yielding an expansion with all these properties. To address this, we develop an analytically modified integral transform expansion (AMITE), a novel expansion via integral transforms modified using derived criteria for convergence. We show the general expansion and then demonstrate application for two popular activation functions, hyperbolic tangent and rectified linear units. Compared with existing expansions (i.e., Chebyshev, Taylor, and numerical) employed to this end, AMITE is the first to provide six previously mutually exclusive desired expansion properties such as exact formulas for the coefficients and exact expansion errors (Table II). We demonstrate the effectiveness of AMITE in two case studies. First, a multivariate polynomial form is efficiently extracted from a single hidden layer black-box Multi-Layer Perceptron (MLP) to facilitate equivalence testing from noisy stimulus-response pairs. Second, a variety of Feed-Forward Neural Network (FFNN) architectures having between 3 and 7 layers are range bounded using Taylor models improved by the AMITE polynomials and error formulas. AMITE presents a new dimension of expansion methods suitable for analysis/approximation of nonlinearities in neural networks, opening new directions and opportunities for the theoretical analysis and systematic testing of neural networks.
SMEs' Confidentiality Concerns for Security Information Sharing
Venue: arXiv cs.CY 2021
Year: 2021

Small and medium-sized enterprises are considered an essential part of the EU economy, however, highly vulnerable to cyberattacks. SMEs have specific characteristics which separate them from large companies and influence their adoption of good cybersecurity practices. To mitigate the SMEs' cybersecurity adoption issues and raise their awareness of cyber threats, we have designed a self-paced security assessment and capability improvement method, CYSEC. CYSEC is a security awareness and training method that utilises self-reporting questionnaires to collect companies' information about cybersecurity awareness, practices, and vulnerabilities to generate automated recommendations for counselling. However, confidentiality concerns about cybersecurity information have an impact on companies' willingness to share their information. Security information sharing decreases the risk of incidents and increases users' self-efficacy in security awareness programs. This paper presents the results of semi-structured interviews with seven chief information security officers of SMEs to evaluate the impact of online consent communication on motivation for information sharing. The results were analysed in respect of the Self Determination Theory. The findings demonstrate that online consent with multiple options for indicating a suitable level of agreement improved motivation for information sharing. This allows many SMEs to participate in security information sharing activities and supports security experts to have a better overview of common vulnerabilities. The final publication is available at Springer via https://doi.org/10.1007/978-3-030-57404-8_22
Mismatched Data Detection in Massive MU-MIMO
Venue: arXiv cs.IT 2021
Year: 2021

We investigate mismatched data detection for massive multi-user (MU) multiple-input multiple-output (MIMO) wireless systems in which the prior distribution of the transmit signal used in the data detector differs from the true prior. In order to minimize the performance loss caused by the prior mismatch, we include a tuning stage into the recently proposed large-MIMO approximate message passing (LAMA) algorithm, which enables the development of data detectors with optimal as well as sub-optimal parameter tuning. We show that carefully-selected priors enable the design of simpler and computationally more efficient data detection algorithms compared to LAMA that uses the optimal prior, while achieving near-optimal error-rate performance. In particular, we demonstrate that a hardware-friendly approximation of the exact prior enables the design of low-complexity data detectors that achieve near individually-optimal performance. Furthermore, for Gaussian priors and uniform priors within a hypercube covering the quadrature amplitude modulation (QAM) constellation, our performance analysis recovers classical and recent results on linear and non-linear massive MU-MIMO data detection, respectively.
Predicting Sequences of Traversed Nodes in Graphs using Network Models with Multiple Higher Orders
Venue: arXiv cs.LG 2021
Year: 2021

We propose a novel sequence prediction method for sequential data capturing node traversals in graphs. Our method builds on a statistical modelling framework that combines multiple higher-order network models into a single multi-order model. We develop a technique to fit such multi-order models in empirical sequential data and to select the optimal maximum order. Our framework facilitates both next-element and full sequence prediction given a sequence-prefix of any length. We evaluate our model based on six empirical data sets containing sequences from website navigation as well as public transport systems. The results show that our method out-performs state-of-the-art algorithms for next-element prediction. We further demonstrate the accuracy of our method during out-of-sample sequence prediction and validate that our method can scale to data sets with millions of sequences.