OpenRaiser/Intern-Atlas huggingface dataset:
Adaptive Regularized Submodular Maximization
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, we study the problem of maximizing the difference between an adaptive submodular (revenue) function and an non-negative modular (cost) function under the adaptive setting. The input of our problem is a set of $n$ items, where each item has a particular state drawn from some known prior distribution $p$. The revenue function $g$ is defined over items and states, and the cost function $c$ is defined over items, i.e., each item has a fixed cost. The state of each item is unknown initially, one must select an item in order to observe its realized state. A policy $π$ specifies which item to pick next based on the observations made so far. Denote by $g_{avg}(π)$ the expected revenue of $π$ and let $c_{avg}(π)$ denote the expected cost of $π$. Our objective is to identify the best policy $π^o\in \arg\max_πg_{avg}(π)-c_{avg}(π)$ under a $k$-cardinality constraint. Since our objective function can take on both negative and positive values, the existing results of submodular maximization may not be applicable. To overcome this challenge, we develop a series of effective solutions with performance grantees. Let $π^o$ denote the optimal policy. For the case when $g$ is adaptive monotone and adaptive submodular, we develop an effective policy $π^l$ such that $g_{avg}(π^l) - c_{avg}(π^l) \geq (1-\frac{1}{e}-ε)g_{avg}(π^o) - c_{avg}(π^o)$, using only $O(nε^{-2}\log ε^{-1})$ value oracle queries. For the case when $g$ is adaptive submodular, we present a randomized policy $π^r$ such that $g_{avg}(π^r) - c_{avg}(π^r) \geq \frac{1}{e}g_{avg}(π^o) - c_{avg}(π^o)$.
Convergence of Gaussian-smoothed optimal transport distance with sub-gamma distributions and dependent samples
Venue: arXiv cs.LG 2021
Year: 2021

The Gaussian-smoothed optimal transport (GOT) framework, recently proposed by Goldfeld et al., scales to high dimensions in estimation and provides an alternative to entropy regularization. This paper provides convergence guarantees for estimating the GOT distance under more general settings. For the Gaussian-smoothed $p$-Wasserstein distance in $d$ dimensions, our results require only the existence of a moment greater than $d + 2p$. For the special case of sub-gamma distributions, we quantify the dependence on the dimension $d$ and establish a phase transition with respect to the scale parameter. We also prove convergence for dependent samples, only requiring a condition on the pairwise dependence of the samples measured by the covariance of the feature map of a kernel space. A key step in our analysis is to show that the GOT distance is dominated by a family of kernel maximum mean discrepancy (MMD) distances with a kernel that depends on the cost function as well as the amount of Gaussian smoothing. This insight provides further interpretability for the GOT framework and also introduces a class of kernel MMD distances with desirable properties. The theoretical results are supported by numerical experiments.
A Minimax Probability Machine for Non-Decomposable Performance Measures
Venue: arXiv cs.LG 2021
Year: 2021

Imbalanced classification tasks are widespread in many real-world applications. For such classification tasks, in comparison with the accuracy rate, it is usually much more appropriate to use non-decomposable performance measures such as the Area Under the receiver operating characteristic Curve (AUC) and the $F_β$ measure as the classification criterion since the label class is imbalanced. On the other hand, the minimax probability machine is a popular method for binary classification problems and aims at learning a linear classifier by maximizing the accuracy rate, which makes it unsuitable to deal with imbalanced classification tasks. The purpose of this paper is to develop a new minimax probability machine for the $F_β$ measure, called MPMF, which can be used to deal with imbalanced classification tasks. A brief discussion is also given on how to extend the MPMF model for several other non-decomposable performance measures listed in the paper. To solve the MPMF model effectively, we derive its equivalent form which can then be solved by an alternating descent method to learn a linear classifier. Further, the kernel trick is employed to derive a nonlinear MPMF model to learn a nonlinear classifier. Several experiments on real-world benchmark datasets demonstrate the effectiveness of our new model.
Seamless Variability Management With the Virtual Platform
Venue: arXiv cs.SE 2021
Year: 2021

Customization is a general trend in software engineering, demanding systems that support variable stakeholder requirements. Two opposing strategies are commonly used to create variants: software clone & own and software configuration with an integrated platform. Organizations often start with the former, which is cheap, agile, and supports quick innovation, but does not scale. The latter scales by establishing an integrated platform that shares software assets between variants, but requires high up-front investments or risky migration processes. So, could we have a method that allows an easy transition or even combine the benefits of both strategies? We propose a method and tool that supports a truly incremental development of variant-rich systems, exploiting a spectrum between both opposing strategies. We design, formalize, and prototype the variability-management framework virtual platform. It bridges clone & own and platform-oriented development. Relying on programming-language-independent conceptual structures representing software assets, it offers operators for engineering and evolving a system, comprising: traditional, asset-oriented operators and novel, feature-oriented operators for incrementally adopting concepts of an integrated platform. The operators record meta-data that is exploited by other operators to support the transition. Among others, they eliminate expensive feature-location effort or the need to trace clones. Our evaluation simulates the evolution of a real-world, clone-based system, measuring its costs and benefits.
Explore User Neighborhood for Real-time E-commerce Recommendation
Venue: arXiv cs.IR 2021
Year: 2021

Recommender systems play a vital role in modern online services, such as Amazon and Taobao. Traditional personalized methods, which focus on user-item (UI) relations, have been widely applied in industrial settings, owing to their efficiency and effectiveness. Despite their success, we argue that these approaches ignore local information hidden in similar users. To tackle this problem, user-based methods exploit similar user relations to make recommendations in a local perspective. Nevertheless, traditional user-based methods, like userKNN and matrix factorization, are intractable to be deployed in the real-time applications since such transductive models have to be recomputed or retrained with any new interaction. To overcome this challenge, we propose a framework called self-complementary collaborative filtering~(SCCF) which can make recommendations with both global and local information in real time. On the one hand, it utilizes UI relations and user neighborhood to capture both global and local information. On the other hand, it can identify similar users for each user in real time by inferring user representations on the fly with an inductive model. The proposed framework can be seamlessly incorporated into existing inductive UI approach and benefit from user neighborhood with little additional computation. It is also the first attempt to apply user-based methods in real-time settings. The effectiveness and efficiency of SCCF are demonstrated through extensive offline experiments on four public datasets, as well as a large scale online A/B test in Taobao.
Path Planning for Manipulation using Experience-driven Random Trees
Venue: arXiv cs.RO 2021
Year: 2021

Robotic systems may frequently come across similar manipulation planning problems that result in similar motion plans. Instead of planning each problem from scratch, it is preferable to leverage previously computed motion plans, i.e., experiences, to ease the planning. Different approaches have been proposed to exploit prior information on novel task instances. These methods, however, rely on a vast repertoire of experiences and fail when none relates closely to the current problem. Thus, an open challenge is the ability to generalise prior experiences to task instances that do not necessarily resemble the prior. This work tackles the above challenge with the proposition that experiences are "decomposable" and "malleable", i.e., parts of an experience are suitable to relevantly explore the connectivity of the robot-task space even in non-experienced regions. Two new planners result from this insight: experience-driven random trees (ERT) and its bi-directional version ERTConnect. These planners adopt a tree sampling-based strategy that incrementally extracts and modulates parts of a single path experience to compose a valid motion plan. We demonstrate our method on task instances that significantly differ from the prior experiences, and compare with related state-of-the-art experience-based planners. While their repairing strategies fail to generalise priors of tens of experiences, our planner, with a single experience, significantly outperforms them in both success rate and planning time. Our planners are implemented and freely available in the Open Motion Planning Library.
NLP-CUET@DravidianLangTech-EACL2021: Offensive Language Detection from Multilingual Code-Mixed Text using Transformers
Venue: arXiv cs.CL 2021
Year: 2021

The increasing accessibility of the internet facilitated social media usage and encouraged individuals to express their opinions liberally. Nevertheless, it also creates a place for content polluters to disseminate offensive posts or contents. Most of such offensive posts are written in a cross-lingual manner and can easily evade the online surveillance systems. This paper presents an automated system that can identify offensive text from multilingual code-mixed data. In the task, datasets provided in three languages including Tamil, Malayalam and Kannada code-mixed with English where participants are asked to implement separate models for each language. To accomplish the tasks, we employed two machine learning techniques (LR, SVM), three deep learning (LSTM, LSTM+Attention) techniques and three transformers (m-BERT, Indic-BERT, XLM-R) based methods. Results show that XLM-R outperforms other techniques in Tamil and Malayalam languages while m-BERT achieves the highest score in the Kannada language. The proposed models gained weighted $f_1$ score of $0.76$ (for Tamil), $0.93$ (for Malayalam), and $0.71$ (for Kannada) with a rank of $3^{rd}$, $5^{th}$ and $4^{th}$ respectively.
Knowledge-Base Enriched Word Embeddings for Biomedical Domain
Venue: arXiv cs.CL 2021
Year: 2021

Word embeddings have been shown adept at capturing the semantic and syntactic regularities of the natural language text, as a result of which these representations have found their utility in a wide variety of downstream content analysis tasks. Commonly, these word embedding techniques derive the distributed representation of words based on the local context information. However, such approaches ignore the rich amount of explicit information present in knowledge-bases. This is problematic, as it might lead to poor representation for words with insufficient local context such as domain specific words. Furthermore, the problem becomes pronounced in domain such as bio-medicine where the presence of these domain specific words are relatively high. Towards this end, in this project, we propose a new word embedding based model for biomedical domain that jointly leverages the information from available corpora and domain knowledge in order to generate knowledge-base powered embeddings. Unlike existing approaches, the proposed methodology is simple but adept at capturing the precise knowledge available in domain resources in an accurate way. Experimental results on biomedical concept similarity and relatedness task validates the effectiveness of the proposed approach.
Generalized and Transferable Patient Language Representation for Phenotyping with Limited Data
Venue: arXiv cs.CL 2021
Year: 2021

The paradigm of representation learning through transfer learning has the potential to greatly enhance clinical natural language processing. In this work, we propose a multi-task pre-training and fine-tuning approach for learning generalized and transferable patient representations from medical language. The model is first pre-trained with different but related high-prevalence phenotypes and further fine-tuned on downstream target tasks. Our main contribution focuses on the impact this technique can have on low-prevalence phenotypes, a challenging task due to the dearth of data. We validate the representation from pre-training, and fine-tune the multi-task pre-trained models on low-prevalence phenotypes including 38 circulatory diseases, 23 respiratory diseases, and 17 genitourinary diseases. We find multi-task pre-training increases learning efficiency and achieves consistently high performance across the majority of phenotypes. Most important, the multi-task pre-training is almost always either the best-performing model or performs tolerably close to the best-performing model, a property we refer to as robust. All these results lead us to conclude that this multi-task transfer learning architecture is a robust approach for developing generalized and transferable patient language representations for numerous phenotypes.
Optimal Approximation Rate of ReLU Networks in terms of Width and Depth
Venue: arXiv cs.LG 2021
Year: 2021

This paper concentrates on the approximation power of deep feed-forward neural networks in terms of width and depth. It is proved by construction that ReLU networks with width $\mathcal{O}\big(\max\{d\lfloor N^{1/d}\rfloor,\, N+2\}\big)$ and depth $\mathcal{O}(L)$ can approximate a Hölder continuous function on $[0,1]^d$ with an approximation rate $\mathcal{O}\big(λ\sqrt{d} (N^2L^2\ln N)^{-α/d}\big)$, where $α\in (0,1]$ and $λ>0$ are Hölder order and constant, respectively. Such a rate is optimal up to a constant in terms of width and depth separately, while existing results are only nearly optimal without the logarithmic factor in the approximation rate. More generally, for an arbitrary continuous function $f$ on $[0,1]^d$, the approximation rate becomes $\mathcal{O}\big(\,\sqrt{d}\,ω_f\big( (N^2L^2\ln N)^{-1/d}\big)\,\big)$, where $ω_f(\cdot)$ is the modulus of continuity. We also extend our analysis to any continuous function $f$ on a bounded set. Particularly, if ReLU networks with depth $31$ and width $\mathcal{O}(N)$ are used to approximate one-dimensional Lipschitz continuous functions on $[0,1]$ with a Lipschitz constant $λ>0$, the approximation rate in terms of the total number of parameters, $W=\mathcal{O}(N^2)$, becomes $\mathcal{O}(\tfracλ{W\ln W})$, which has not been discovered in the literature for fixed-depth ReLU networks.
On the Approximation Ratio of the 3-Opt Algorithm for the (1,2)-TSP
Venue: arXiv cs.DM 2021
Year: 2021

The (1,2)-TSP is a special case of the TSP where each edge has cost either 1 or 2. In this paper we give a lower bound of $\frac{3}{2}$ for the approximation ratio of the 2-Opt algorithm for the (1,2)-TSP. Moreover, we show that the 3-Opt algorithm has an exact approximation ratio of $\frac{11}{8}$ for the (1,2)-TSP. Furthermore, we introduce the 3-Opt++-algorithm, an improved version of the 3-Opt algorithm for the (1-2)-TSP with an exact approximation ratio of $\frac{4}{3}$.
On the Utility of Gradient Compression in Distributed Training Systems
Venue: arXiv cs.DC 2021
Year: 2021

A rich body of prior work has highlighted the existence of communication bottlenecks in synchronous data-parallel training. To alleviate these bottlenecks, a long line of recent work proposes gradient and model compression methods. In this work, we evaluate the efficacy of gradient compression methods and compare their scalability with optimized implementations of synchronous data-parallel SGD across more than 200 different setups. Surprisingly, we observe that only in 6 cases out of more than 200, gradient compression methods provide speedup over optimized synchronous data-parallel training in the typical data-center setting. We conduct an extensive investigation to identify the root causes of this phenomenon, and offer a performance model that can be used to identify the benefits of gradient compression for a variety of system setups. Based on our analysis, we propose a list of desirable properties that gradient compression methods should satisfy, in order for them to provide a meaningful end-to-end speedup.
Machine learning for detection of stenoses and aneurysms: application in a physiologically realistic virtual patient database
Venue: arXiv cs.LG 2021
Year: 2021

This study presents an application of machine learning (ML) methods for detecting the presence of stenoses and aneurysms in the human arterial system. Four major forms of arterial disease -- carotid artery stenosis (CAS), subclavian artery stenosis (SAC), peripheral arterial disease (PAD), and abdominal aortic aneurysms (AAA) -- are considered. The ML methods are trained and tested on a physiologically realistic virtual patient database (VPD) containing 28,868 healthy subjects, which is adapted from the authors previous work and augmented to include the four disease forms. Six ML methods -- Naive Bayes, Logistic Regression, Support Vector Machine, Multi-layer Perceptron, Random Forests, and Gradient Boosting -- are compared with respect to classification accuracies and it is found that the tree-based methods of Random Forest and Gradient Boosting outperform other approaches. The performance of ML methods is quantified through the F1 score and computation of sensitivities and specificities. When using all the six measurements, it is found that maximum F1 scores larger than 0.9 are achieved for CAS and PAD, larger than 0.85 for SAS, and larger than 0.98 for both low- and high-severity AAAs. Corresponding sensitivities and specificities are larger than 90% for CAS and PAD, larger than 85% for SAS, and larger than 98% for both low- and high-severity AAAs. When reducing the number of measurements, it is found that the performance is degraded by less than 5% when three measurements are used, and less than 10% when only two measurements are used for classification. For AAA, it is shown that F1 scores larger than 0.85 and corresponding sensitivities and specificities larger than 85% are achievable when using only a single measurement. The results are encouraging to pursue AAA monitoring and screening through wearable devices which can reliably measure pressure or flow-rates
Time Matters: Exploring the Effects of Urgency and Reaction Speed in Automated Traders
Venue: arXiv cs.MA 2021
Year: 2021

We consider issues of time in automated trading strategies in simulated financial markets containing a single exchange with public limit order book and continuous double auction matching. In particular, we explore two effects: (i) reaction speed - the time taken for trading strategies to calculate a response to market events; and (ii) trading urgency - the sensitivity of trading strategies to approaching deadlines. Much of the literature on trading agents focuses on optimising pricing strategies only and ignores the effects of time, while real-world markets continue to experience a race to zero latency, as automated trading systems compete to quickly access information and act in the market ahead of others. We demonstrate that modelling reaction speed can significantly alter previously published results, with simple strategies such as SHVR outperforming more complex adaptive algorithms such as AA. We also show that adding a pace parameter to ZIP traders (ZIP-Pace, or ZIPP) can create a sense of urgency that significantly improves profitability.
Terahertz Wireless Communications: Co-sharing for Terrestrial and Satellite Systems above 100 GHz
Venue: arXiv cs.IT 2021
Year: 2021

This paper demonstrates how spectrum up to 1 THz will support mobile communications beyond 5G in the coming decades. Results of rooftop surrogate satellite/tower base station measurements at 140 GHz show the natural isolation between terrestrial networks and surrogate satellite systems, as well as between terrestrial mobile users and co-channel fixed backhaul links. These first-of-their-kind measurements and accompanying analysis show that by keeping the energy radiated by terrestrial emitters on the horizon (e.g., elevation angles $\leq$15\textdegree), there will not likely be interference in the same or adjacent bands between passive satellite sensors and terrestrial terminals, or between mobile links and terrestrial backhaul links at frequencies above 100 GHz.
Unsupervised Domain Adaptation for Cross-Subject Few-Shot Neurological Symptom Detection
Venue: arXiv cs.LG 2021
Year: 2021

Modern machine learning tools have shown promise in detecting symptoms of neurological disorders. However, current approaches typically train a unique classifier for each subject. This subject-specific training scheme requires long labeled recordings from each patient, thus failing to detect symptoms in new patients with limited recordings. This paper introduces an unsupervised domain adaptation approach based on adversarial networks to enable few-shot, cross-subject epileptic seizure detection. Using adversarial learning, features from multiple patients were encoded into a subject-invariant space and a discriminative model was trained on subject-invariant features to make predictions. We evaluated this approach on the intracranial EEG (iEEG) recordings from 9 patients with epilepsy. Our approach enabled cross-subject seizure detection with a 9.4\% improvement in 1-shot classification accuracy compared to the conventional subject-specific scheme.
Scaling up Mean Field Games with Online Mirror Descent
Venue: arXiv cs.AI 2021
Year: 2021

We address scaling up equilibrium computation in Mean Field Games (MFGs) using Online Mirror Descent (OMD). We show that continuous-time OMD provably converges to a Nash equilibrium under a natural and well-motivated set of monotonicity assumptions. This theoretical result nicely extends to multi-population games and to settings involving common noise. A thorough experimental investigation on various single and multi-population MFGs shows that OMD outperforms traditional algorithms such as Fictitious Play (FP). We empirically show that OMD scales up and converges significantly faster than FP by solving, for the first time to our knowledge, examples of MFGs with hundreds of billions states. This study establishes the state-of-the-art for learning in large-scale multi-agent and multi-population games.