OpenRaiser/Intern-Atlas huggingface dataset:
HiGitClass: Keyword-Driven Hierarchical Classification of GitHub Repositories
Venue: arXiv cs.LG 2021
Year: 2021

GitHub has become an important platform for code sharing and scientific exchange. With the massive number of repositories available, there is a pressing need for topic-based search. Even though the topic label functionality has been introduced, the majority of GitHub repositories do not have any labels, impeding the utility of search and topic-based analysis. This work targets the automatic repository classification problem as keyword-driven hierarchical classification. Specifically, users only need to provide a label hierarchy with keywords to supply as supervision. This setting is flexible, adaptive to the users' needs, accounts for the different granularity of topic labels and requires minimal human effort. We identify three key challenges of this problem, namely (1) the presence of multi-modal signals; (2) supervision scarcity and bias; (3) supervision format mismatch. In recognition of these challenges, we propose the HiGitClass framework, comprising of three modules: heterogeneous information network embedding; keyword enrichment; topic modeling and pseudo document generation. Experimental results on two GitHub repository collections confirm that HiGitClass is superior to existing weakly-supervised and dataless hierarchical classification methods, especially in its ability to integrate both structured and unstructured data for repository classification.
Active Learning for Graph Neural Networks via Node Feature Propagation
Venue: arXiv cs.LG 2021
Year: 2021

Graph Neural Networks (GNNs) for prediction tasks like node classification or edge prediction have received increasing attention in recent machine learning from graphically structured data. However, a large quantity of labeled graphs is difficult to obtain, which significantly limits the true success of GNNs. Although active learning has been widely studied for addressing label-sparse issues with other data types like text, images, etc., how to make it effective over graphs is an open question for research. In this paper, we present an investigation on active learning with GNNs for node classification tasks. Specifically, we propose a new method, which uses node feature propagation followed by K-Medoids clustering of the nodes for instance selection in active learning. With a theoretical bound analysis we justify the design choice of our approach. In our experiments on four benchmark datasets, the proposed method outperforms other representative baseline methods consistently and significantly.
Community Detection in Multiplex Networks
Venue: arXiv cs.SI 2021
Year: 2021

A multiplex network models different modes of interaction among same-type entities. In this article we provide a taxonomy of community detection algorithms in multiplex networks. We characterize the different algorithms based on various properties and we discuss the type of communities detected by each method. We then provide an extensive experimental evaluation of the reviewed methods to answer three main questions: to what extent the evaluated methods are able to detect ground-truth communities, to what extent different methods produce similar community structures and to what extent the evaluated methods are scalable. One goal of this survey is to help scholars and practitioners to choose the right methods for the data and the task at hand, while also emphasizing when such choice is problematic.
Landing Probabilities of Random Walks for Seed-Set Expansion in Hypergraphs
Venue: arXiv cs.LG 2021
Year: 2021

We describe the first known mean-field study of landing probabilities for random walks on hypergraphs. In particular, we examine clique-expansion and tensor methods and evaluate their mean-field characteristics over a class of random hypergraph models for the purpose of seed-set community expansion. We describe parameter regimes in which the two methods outperform each other and propose a hybrid expansion method that uses partial clique-expansion to reduce the projection distortion and low-complexity tensor methods applied directly on the partially expanded hypergraphs.
Regular Model Checking with Regular Relations
Venue: arXiv cs.LO 2021
Year: 2021

Regular model checking is an exploration technique for infinite state systems where state spaces are represented as regular languages and transition relations are expressed using rational relations over infinite (or finite) strings. We extend the regular model checking paradigm to permit the use of more powerful transition relations: the class of regular relations, of which the rational relations are a strict subset. We use the language of monadic second-order logic on infinite strings to specify such relations and adopt streaming string transducers (SSTs) as a suitable computational model. We introduce nondeterministic SSTs over infinite strings and show that they precisely capture the relations definable in MSO. We further explore theoretical properties of omega-NSSTs required to effectively carry out regular model checking. In particular, we establish that the regular type checking problem for omega-NSSTs is decidable in PSPACE. Since the post-image of a regular language under a regular relation may not be regular (or even context-free), approaches that iteratively compute the image can not be effectively carried out in this setting. Instead, we utilize the fact that regular relations are closed under composition, which, together with our decidability result, provides a foundation for regular model checking with regular relations.
Decentralized Heterogeneous Multi-Player Multi-Armed Bandits with Non-Zero Rewards on Collisions
Venue: arXiv cs.LG 2021
Year: 2021

We consider a fully decentralized multi-player stochastic multi-armed bandit setting where the players cannot communicate with each other and can observe only their own actions and rewards. The environment may appear differently to different players, $\textit{i.e.}$, the reward distributions for a given arm are heterogeneous across players. In the case of a collision (when more than one player plays the same arm), we allow for the colliding players to receive non-zero rewards. The time-horizon $T$ for which the arms are played is \emph{not} known to the players. Within this setup, where the number of players is allowed to be greater than the number of arms, we present a policy that achieves near order-optimal expected regret of order $O(\log^{1 + δ} T)$ for some $0 < δ< 1$ over a time-horizon of duration $T$. This paper is accepted at IEEE Transactions on Information Theory.
Maximum Probability Theorem: A Framework for Probabilistic Learning
Venue: arXiv cs.LG 2021
Year: 2021

We present a theoretical framework of probabilistic learning derived by Maximum Probability (MP) Theorem shown in the current paper. In this probabilistic framework, a model is defined as an event in the probability space, and a model or the associated event -- either the true underlying model or the parameterized model -- have a quantified probability measure. This quantification of a model's probability measure is derived by the MP Theorem, in which we have shown that an event's probability measure has an upper-bound given its conditional distribution on an arbitrary random variable. Through this alternative framework, the notion of model parameters is encompassed in the definition of the model or the associated event. Therefore, this framework deviates from the conventional approach of assuming a prior on the model parameters. Instead, the regularizing effects of assuming prior over parameters is seen through maximizing probabilities of models or according to information theory, minimizing the information content of a model. The probability of a model in our framework is invariant to reparameterization and is solely dependent on the model's likelihood function. Also, rather than maximizing the posterior in a conventional Bayesian setting, the objective function in our alternative framework is defined as the probability of set operations (e.g. intersection) on the event of the true underlying model and the event of the model at hand. Our theoretical framework, as a derivation of MP theorem, adds clarity to probabilistic learning through solidifying the definition of probabilistic models, quantifying their probabilities, and providing a visual understanding of objective functions.
Smoothness-Adaptive Contextual Bandits
Venue: arXiv cs.LG 2021
Year: 2021

We study a non-parametric multi-armed bandit problem with stochastic covariates, where a key complexity driver is the smoothness of payoff functions with respect to covariates. Previous studies have focused on deriving minimax-optimal algorithms in cases where it is a priori known how smooth the payoff functions are. In practice, however, the smoothness of payoff functions is typically not known in advance, and misspecification of smoothness may severely deteriorate the performance of existing methods. In this work, we consider a framework where the smoothness of payoff functions is not known, and study when and how algorithms may adapt to unknown smoothness. First, we establish that designing algorithms that adapt to unknown smoothness of payoff functions is, in general, impossible. However, under a self-similarity condition (which does not reduce the minimax complexity of the dynamic optimization problem at hand), we establish that adapting to unknown smoothness is possible, and further devise a general policy for achieving smoothness-adaptive performance. Our policy infers the smoothness of payoffs throughout the decision-making process, while leveraging the structure of off-the-shelf non-adaptive policies. We establish that for problem settings with either differentiable or non-differentiable payoff functions, this policy matches (up to a logarithmic scale) the regret rate that is achievable when the smoothness of payoffs is known a priori.
Single and Union Non-parallel Support Vector Machine Frameworks
Venue: arXiv cs.LG 2021
Year: 2021

Considering the classification problem, we summarize the nonparallel support vector machines with the nonparallel hyperplanes to two types of frameworks. The first type constructs the hyperplanes separately. It solves a series of small optimization problems to obtain a series of hyperplanes, but is hard to measure the loss of each sample. The other type constructs all the hyperplanes simultaneously, and it solves one big optimization problem with the ascertained loss of each sample. We give the characteristics of each framework and compare them carefully. In addition, based on the second framework, we construct a max-min distance-based nonparallel support vector machine for multiclass classification problem, called NSVM. It constructs hyperplanes with large distance margin by solving an optimization problem. Experimental results on benchmark data sets show the advantages of our NSVM.
Multiscale Evolutionary Perturbation Attack on Community Detection
Venue: arXiv cs.SI 2021
Year: 2021

Community detection, aiming to group nodes based on their connections, plays an important role in network analysis, since communities, treated as meta-nodes, allow us to create a large-scale map of a network to simplify its analysis. However, for privacy reasons, we may want to prevent communities from being discovered in certain cases, leading to the topics on community deception. In this paper, we formalize this community detection attack problem in three scales, including global attack (macroscale), target community attack (mesoscale) and target node attack (microscale). We treat this as an optimization problem and further propose a novel Evolutionary Perturbation Attack (EPA) method, where we generate adversarial networks to realize the community detection attack. Numerical experiments validate that our EPA can successfully attack network community algorithms in all three scales, i.e., hide target nodes or communities and further disturb the community structure of the whole network by only changing a small fraction of links. By comparison, our EPA behaves better than a number of baseline attack methods on six synthetic networks and three real-world networks. More interestingly, although our EPA is based on the louvain algorithm, it is also effective on attacking other community detection algorithms, validating its good transferability.
Fine-grained Fact Verification with Kernel Graph Attention Network
Venue: arXiv cs.CL 2021
Year: 2021

Fact Verification requires fine-grained natural language inference capability that finds subtle clues to identify the syntactical and semantically correct but not well-supported claims. This paper presents Kernel Graph Attention Network (KGAT), which conducts more fine-grained fact verification with kernel-based attentions. Given a claim and a set of potential evidence sentences that form an evidence graph, KGAT introduces node kernels, which better measure the importance of the evidence node, and edge kernels, which conduct fine-grained evidence propagation in the graph, into Graph Attention Networks for more accurate fact verification. KGAT achieves a 70.38% FEVER score and significantly outperforms existing fact verification models on FEVER, a large-scale benchmark for fact verification. Our analyses illustrate that, compared to dot-product attentions, the kernel-based attention concentrates more on relevant evidence sentences and meaningful clues in the evidence graph, which is the main source of KGAT's effectiveness.
When Segmentation is Not Enough: Rectifying Visual-Volume Discordance Through Multisensor Depth-Refined Semantic Segmentation for Food Intake Tracking in Long-Term Care
Venue: arXiv cs.CV 2021
Year: 2021

Malnutrition is a multidomain problem affecting 54% of older adults in long-term care (LTC). Monitoring nutritional intake in LTC is laborious and subjective, limiting clinical inference capabilities. Recent advances in automatic image-based food estimation have not yet been evaluated in LTC settings. Here, we describe a fully automatic imaging system for quantifying food intake. We propose a novel deep convolutional encoder-decoder food network with depth-refinement (EDFN-D) using an RGB-D camera for quantifying a plate's remaining food volume relative to reference portions in whole and modified texture foods. We trained and validated the network on the pre-labelled UNIMIB2016 food dataset and tested on our two novel LTC-inspired plate datasets (689 plate images, 36 unique foods). EDFN-D performed comparably to depth-refined graph cut on IOU (0.879 vs. 0.887), with intake errors well below typical 50% (mean percent intake error: -4.2%). We identify how standard segmentation metrics are insufficient due to visual-volume discordance, and include volume disparity analysis to facilitate system trust. This system provides improved transparency, approximates human assessors with enhanced objectivity, accuracy, and precision while avoiding hefty semi-automatic method time requirements. This may help address short-comings currently limiting utility of automated early malnutrition detection in resource-constrained LTC and hospital settings.
Automatic Reminiscence Therapy for Dementia
Venue: arXiv cs.MM 2021
Year: 2021

With people living longer than ever, the number of cases with dementia such as Alzheimer's disease increases steadily. It affects more than 46 million people worldwide, and it is estimated that in 2050 more than 100 million will be affected. While there are not effective treatments for these terminal diseases, therapies such as reminiscence, that stimulate memories from the past are recommended. Currently, reminiscence therapy takes place in care homes and is guided by a therapist or a carer. In this work, we present an AI-based solution to automatize the reminiscence therapy, which consists in a dialogue system that uses photos as input to generate questions. We run a usability case study with patients diagnosed of mild cognitive impairment that shows they found the system very entertaining and challenging. Overall, this paper presents how reminiscence therapy can be automatized by using machine learning, and deployed to smartphones and laptops, making the therapy more accessible to every person affected by dementia.
Generalized SAT-Attack-Resistant Logic Locking
Venue: arXiv cs.CR 2021
Year: 2021

Logic locking is used to protect integrated circuits (ICs) from piracy and counterfeiting. An encrypted IC implements the correct function only when the right key is input. Many existing logic-locking methods are subject to the powerful satisfiability (SAT)-based attack. Recently, an Anti-SAT scheme has been developed. By adopting two complementary logic blocks that consist of AND/NAND trees, it makes the number of iterations needed by the SAT attack exponential to the number of input bits. Nevertheless, the Anti-SAT scheme is vulnerable to the later AppSAT and removal attacks. This paper proposes a generalized (G-)Anti-SAT scheme. Different from the Anti-SAT scheme, a variety of complementary or non-complementary functions can be adopted for the two blocks in our G-Anti-SAT scheme. The Anti-SAT scheme is just a special case of our proposed design. Our design can achieve higher output corruptibility, which is also tunable, so that better resistance to the AppSAT and removal attacks is achieved. Meanwhile, unlike existing AppSAT-resilient designs, our design does not sacrifice the resistance to the SAT attack.
ACE: Adaptive Confusion Energy for Natural World Data Distribution
Venue: arXiv cs.CV 2021
Year: 2021

With the development of deep learning, standard classification problems have achieved good results. However, conventional classification problems are often too idealistic. Most data in the natural world usually have imbalanced distribution and fine-grained characteristics. Recently, many state-of-the-art approaches tend to focus on one or another separately, but rarely on both. In this paper, we introduce a novel and adaptive batch-wise regularization based on the proposed Adaptive Confusion Energy (ACE) to flexibly address the nature world distribution, which usually involves fine-grained and long-tailed properties at the same time. ACE increases the difficulty of the training process and further alleviates the overfitting problem. Through the datasets with the technical issue in fine-grained (CUB, CAR, AIR) and long-tailed (ImageNet-LT), or comprehensive issues (CUB-LT, iNaturalist), the result shows that the ACE is not only competitive to some state-of-the-art on performance but also demonstrates the effectiveness of training.
Scalable Evaluation and Improvement of Document Set Expansion via Neural Positive-Unlabeled Learning
Venue: arXiv cs.CL 2021
Year: 2021

We consider the situation in which a user has collected a small set of documents on a cohesive topic, and they want to retrieve additional documents on this topic from a large collection. Information Retrieval (IR) solutions treat the document set as a query, and look for similar documents in the collection. We propose to extend the IR approach by treating the problem as an instance of positive-unlabeled (PU) learning -- i.e., learning binary classifiers from only positive and unlabeled data, where the positive data corresponds to the query documents, and the unlabeled data is the results returned by the IR engine. Utilizing PU learning for text with big neural networks is a largely unexplored field. We discuss various challenges in applying PU learning to the setting, including an unknown class prior, extremely imbalanced data and large-scale accurate evaluation of models, and we propose solutions and empirically validate them. We demonstrate the effectiveness of the method using a series of experiments of retrieving PubMed abstracts adhering to fine-grained topics. We demonstrate improvements over the base IR solution and other baselines.
Off-the-grid Recovery of Time and Frequency Shifts with Multiple Measurement Vectors
Venue: arXiv cs.IT 2021
Year: 2021

We address the problem of estimating time and frequency shifts of a known waveform in the presence of multiple measurement vectors (MMVs). This problem naturally arises in radar imaging and wireless communications. Specifically, a signal ensemble is observed, where each signal of the ensemble is formed by a superposition of a small number of scaled, time-delayed, and frequency shifted versions of a known waveform sharing the same continuous-valued time and frequency components. The goal is to recover the continuous-valued time-frequency pairs from a small number of observations. In this work, we propose a semidefinite programming which exactly recovers $s$ pairs of time-frequency shifts from $L$ regularly spaced samples per measurement vector under a minimum separation condition between the time-frequency shifts. Moreover, we prove that the number $s$ of time-frequency shifts scales linearly with the number $L$ of samples up to a log-factor. Extensive numerical results are also provided to validate the effectiveness of the proposed method over the single measurement vectors (SMVs) problem. In particular, we find that our approach leads to a relaxed minimum separation condition and reduced number of required samples.
Masked Language Model Scoring
Venue: arXiv cs.CL 2021
Year: 2021

Pretrained masked language models (MLMs) require finetuning for most NLP tasks. Instead, we evaluate MLMs out of the box via their pseudo-log-likelihood scores (PLLs), which are computed by masking tokens one by one. We show that PLLs outperform scores from autoregressive language models like GPT-2 in a variety of tasks. By rescoring ASR and NMT hypotheses, RoBERTa reduces an end-to-end LibriSpeech model's WER by 30% relative and adds up to +1.7 BLEU on state-of-the-art baselines for low-resource translation pairs, with further gains from domain adaptation. We attribute this success to PLL's unsupervised expression of linguistic acceptability without a left-to-right bias, greatly improving on scores from GPT-2 (+10 points on island effects, NPI licensing in BLiMP). One can finetune MLMs to give scores without masking, enabling computation in a single inference pass. In all, PLLs and their associated pseudo-perplexities (PPPLs) enable plug-and-play use of the growing number of pretrained MLMs; e.g., we use a single cross-lingual model to rescore translations in multiple languages. We release our library for language model scoring at https://github.com/awslabs/mlm-scoring.