OpenRaiser/Intern-Atlas huggingface dataset:
An algorithm for network community structure determination by surprise
Venue: arXiv cs.SI 2020
Year: 2020

Graphs representing real world systems may be studied from their underlying community structure. A community in a network is an intuitive idea for which there is no consensus on its objective mathematical definition. The most used metric in order to detect communities is the modularity, though many disadvantages of this parameter have already been noticed in the literature. In this work, we present a new approach based on a different metric: the surprise. Moreover, the biases of different community detection algorithms and benchmark networks are thoroughly studied, identified and commented about.
Explainable Multi-class Classification of Medical Data
Venue: arXiv cs.LG 2020
Year: 2020

Machine Learning applications have brought new insights into a secondary analysis of medical data. Machine Learning helps to develop new drugs, define populations susceptible to certain illnesses, identify predictors of many common diseases. At the same time, Machine Learning results depend on convolution of many factors, including feature selection, class (im)balance, algorithm preference, and performance metrics. In this paper, we present explainable multi-class classification of a large medical data set. We in details discuss knowledge-based feature engineering, data set balancing, best model selection, and parameter tuning. Six algorithms are used in this study: Support Vector Machine (SVM), Naïve Bayes, Gradient Boosting, Decision Trees, Random Forest, and Logistic Regression. Our empirical evaluation is done on the UCI Diabetes 130-US hospitals for years 1999-2008 dataset, with the task to classify patient hospital re-admission stay into three classes: 0 days, <30 days, or > 30 days. Our results show that using 23 medication features in learning experiments improves Recall of five out of the six applied learning algorithms. This is a new result that expands the previous studies conducted on the same data. Gradient Boosting and Random Forest outperformed other algorithms in terms of the three-class classification Accuracy.
Deep Learning Based Intelligent Inter-Vehicle Distance Control for 6G Enabled Cooperative Autonomous Driving
Venue: arXiv cs.AI 2020
Year: 2020

Research on the sixth generation cellular networks (6G) is gaining huge momentum to achieve ubiquitous wireless connectivity. Connected autonomous driving (CAV) is a critical vertical envisioned for 6G, holding great potentials of improving road safety, road and energy efficiency. However the stringent service requirements of CAV applications on reliability, latency and high speed communications will present big challenges to 6G networks. New channel access algorithms and intelligent control schemes for connected vehicles are needed for 6G supported CAV. In this paper, we investigated 6G supported cooperative driving, which is an advanced driving mode through information sharing and driving coordination. Firstly we quantify the delay upper bounds of 6G vehicle to vehicle (V2V) communications with hybrid communication and channel access technologies. A deep learning neural network is developed and trained for fast computation of the delay bounds in real time operations. Then, an intelligent strategy is designed to control the inter-vehicle distance for cooperative autonomous driving. Furthermore, we propose a Markov Chain based algorithm to predict the parameters of the system states, and also a safe distance mapping method to enable smooth vehicular speed changes. The proposed algorithms are implemented in the AirSim autonomous driving platform. Simulation results show that the proposed algorithms are effective and robust with safe and stable cooperative autonomous driving, which greatly improve the road safety, capacity and efficiency.
ANL: Anti-Noise Learning for Cross-Domain Person Re-Identification
Venue: arXiv cs.CV 2020
Year: 2020

Due to the lack of labels and the domain diversities, it is a challenge to study person re-identification in the cross-domain setting. An admirable method is to optimize the target model by assigning pseudo-labels for unlabeled samples through clustering. Usually, attributed to the domain gaps, the pre-trained source domain model cannot extract appropriate target domain features, which will dramatically affect the clustering performance and the accuracy of pseudo-labels. Extensive label noise will lead to sub-optimal solutions doubtlessly. To solve these problems, we propose an Anti-Noise Learning (ANL) approach, which contains two modules. The Feature Distribution Alignment (FDA) module is designed to gather the id-related samples and disperse id-unrelated samples, through the camera-wise contrastive learning and adversarial adaptation. Creating a friendly cross-feature foundation for clustering that is to reduce clustering noise. Besides, the Reliable Sample Selection (RSS) module utilizes an Auxiliary Model to correct noisy labels and select reliable samples for the Main Model. In order to effectively utilize the outlier information generated by the clustering algorithm and RSS module, we train these samples at the instance-level. The experiments demonstrate that our proposed ANL framework can effectively reduce the domain conflicts and alleviate the influence of noisy samples, as well as superior performance compared with the state-of-the-art methods.
Secret Key Distillation over Satellite-to-satellite Free-space Optics Channel with Eavesdropper Dynamic Positioning
Venue: arXiv cs.IT 2020
Year: 2020

The conventional omnipotent eavesdropper assumption in quantum cryptography study can be too strict for some realistic scenarios. In this paper, we study the secret key distillation over a satellite-to-satellite free space optics channel in which we assume that the eavesdropper (Eve) is restricted in her ability of power collection due to the limited size of her aperture but can change the position of her aperture to gain advantages over the communication parties (Alice and Bob) and we determine the achievable key rate lower and upper bounds with respect to different scenarios. We first study the case where Eve is behind Bob and we prove that the optimal eavesdropping strategy for her in long-distance transmission case is to place her aperture on the beam transmission axis and set Bob-to-Eve distance equal to Alice-to-Bob distance. We also show that the achievable key rate would be characterized by a Bessel function integral related to Eve's position in a short-distance transmission case. We then investigate the case where Eve is before Bob and show similar results with Eve's and Bob's roles exchanged.
My Teacher Thinks The World Is Flat! Interpreting Automatic Essay Scoring Mechanism
Venue: arXiv cs.CL 2020
Year: 2020

Significant progress has been made in deep-learning based Automatic Essay Scoring (AES) systems in the past two decades. However, little research has been put to understand and interpret the black-box nature of these deep-learning based scoring models. Recent work shows that automated scoring systems are prone to even common-sense adversarial samples. Their lack of natural language understanding capability raises questions on the models being actively used by millions of candidates for life-changing decisions. With scoring being a highly multi-modal task, it becomes imperative for scoring models to be validated and tested on all these modalities. We utilize recent advances in interpretability to find the extent to which features such as coherence, content and relevance are important for automated scoring mechanisms and why they are susceptible to adversarial samples. We find that the systems tested consider essays not as a piece of prose having the characteristics of natural flow of speech and grammatical structure, but as `word-soups' where a few words are much more important than the other words. Removing the context surrounding those few important words causes the prose to lose the flow of speech and grammar, however has little impact on the predicted score. We also find that since the models are not semantically grounded with world-knowledge and common sense, adding false facts such as ``the world is flat'' actually increases the score instead of decreasing it.
Improving Opinion Spam Detection by Cumulative Relative Frequency Distribution
Venue: arXiv cs.SI 2020
Year: 2020

Over the last years, online reviews became very important since they can influence the purchase decision of consumers and the reputation of businesses, therefore, the practice of writing fake reviews can have severe consequences on customers and service providers. Various approaches have been proposed for detecting opinion spam in online reviews, especially based on supervised classifiers. In this contribution, we start from a set of effective features used for classifying opinion spam and we re-engineered them, by considering the Cumulative Relative Frequency Distribution of each feature. By an experimental evaluation carried out on real data from Yelp.com, we show that the use of the distributional features is able to improve the performances of classifiers.
MeDAL: Medical Abbreviation Disambiguation Dataset for Natural Language Understanding Pretraining
Venue: arXiv cs.CL 2020
Year: 2020

One of the biggest challenges that prohibit the use of many current NLP methods in clinical settings is the availability of public datasets. In this work, we present MeDAL, a large medical text dataset curated for abbreviation disambiguation, designed for natural language understanding pre-training in the medical domain. We pre-trained several models of common architectures on this dataset and empirically showed that such pre-training leads to improved performance and convergence speed when fine-tuning on downstream medical tasks.
ALP-KD: Attention-Based Layer Projection for Knowledge Distillation
Venue: arXiv cs.CL 2020
Year: 2020

Knowledge distillation is considered as a training and compression strategy in which two neural networks, namely a teacher and a student, are coupled together during training. The teacher network is supposed to be a trustworthy predictor and the student tries to mimic its predictions. Usually, a student with a lighter architecture is selected so we can achieve compression and yet deliver high-quality results. In such a setting, distillation only happens for final predictions whereas the student could also benefit from teacher's supervision for internal components. Motivated by this, we studied the problem of distillation for intermediate layers. Since there might not be a one-to-one alignment between student and teacher layers, existing techniques skip some teacher layers and only distill from a subset of them. This shortcoming directly impacts quality, so we instead propose a combinatorial technique which relies on attention. Our model fuses teacher-side information and takes each layer's significance into consideration, then performs distillation between combined teacher layers and those of the student. Using our technique, we distilled a 12-layer BERT (Devlin et al. 2019) into 6-, 4-, and 2-layer counterparts and evaluated them on GLUE tasks (Wang et al. 2018). Experimental results show that our combinatorial approach is able to outperform other existing techniques.
Blackwell Online Learning for Markov Decision Processes
Venue: arXiv cs.LG 2020
Year: 2020

This work provides a novel interpretation of Markov Decision Processes (MDP) from the online optimization viewpoint. In such an online optimization context, the policy of the MDP is viewed as the decision variable while the corresponding value function is treated as payoff feedback from the environment. Based on this interpretation, we construct a Blackwell game induced by MDP, which bridges the gap among regret minimization, Blackwell approachability theory, and learning theory for MDP. Specifically, from the approachability theory, we propose 1) Blackwell value iteration for offline planning and 2) Blackwell $Q-$learning for online learning in MDP, both of which are shown to converge to the optimal solution. Our theoretical guarantees are corroborated by numerical experiments.
Adversarial Multi-scale Feature Learning for Person Re-identification
Venue: arXiv cs.CV 2020
Year: 2020

Person Re-identification (Person ReID) is an important topic in intelligent surveillance and computer vision. It aims to accurately measure visual similarities between person images for determining whether two images correspond to the same person. The key to accurately measure visual similarities is learning discriminative features, which not only captures clues from different spatial scales, but also jointly inferences on multiple scales, with the ability to determine reliability and ID-relativity of each clue. To achieve these goals, we propose to improve Person ReID system performance from two perspective: \textbf{1).} Multi-scale feature learning (MSFL), which consists of Cross-scale information propagation (CSIP) and Multi-scale feature fusion (MSFF), to dynamically fuse features cross different scales.\textbf{2).} Multi-scale gradient regularizor (MSGR), to emphasize ID-related factors and ignore irrelevant factors in an adversarial manner. Combining MSFL and MSGR, our method achieves the state-of-the-art performance on four commonly used person-ReID datasets with neglectable test-time computation overhead.
Learning algorithms from circuit lower bounds
Venue: arXiv cs.CC 2020
Year: 2020

We revisit known constructions of efficient learning algorithms from various notions of constructive circuit lower bounds such as distinguishers breaking pseudorandom generators or efficient witnessing algorithms which find errors of small circuits attempting to compute hard functions. As our main result we prove that if it is possible to find efficiently, in a particular interactive way, errors of many p-size circuits attempting to solve hard problems, then p-size circuits can be PAC learned over the uniform distribution with membership queries by circuits of subexponential size. The opposite implication holds as well. This provides a new characterisation of learning algorithms and extends the natural proofs barrier of Razborov and Rudich. The proof is based on a method of exploiting Nisan-Wigderson generators introduced by Krajíček (2010) and used to analyze complexity of circuit lower bounds in bounded arithmetic. An interesting consequence of known constructions of learning algorithms from circuit lower bounds is a learning speedup of Oliveira and Santhanam (2016). We present an alternative proof of this phenomenon and discuss its potential to advance the program of hardness magnification.
Human Expression Recognition using Facial Shape Based Fourier Descriptors Fusion
Venue: arXiv cs.CV 2020
Year: 2020

Dynamic facial expression recognition has many useful applications in social networks, multimedia content analysis, security systems and others. This challenging process must be done under recurrent problems of image illumination and low resolution which changes at partial occlusions. This paper aims to produce a new facial expression recognition method based on the changes in the facial muscles. The geometric features are used to specify the facial regions i.e., mouth, eyes, and nose. The generic Fourier shape descriptor in conjunction with elliptic Fourier shape descriptor is used as an attribute to represent different emotions under frequency spectrum features. Afterwards a multi-class support vector machine is applied for classification of seven human expression. The statistical analysis showed our approach obtained overall competent recognition using 5-fold cross validation with high accuracy on well-known facial expression dataset.
Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem
Venue: arXiv cs.DS 2020
Year: 2020

We present the first nontrivial approximation algorithm for the bottleneck asymmetric traveling salesman problem. Given an asymmetric metric cost between n vertices, the problem is to find a Hamiltonian cycle that minimizes its bottleneck (or maximum-length edge) cost. We achieve an O(log n / log log n) approximation performance guarantee by giving a novel algorithmic technique to shortcut Eulerian circuits while bounding the lengths of the shortcuts needed. This allows us to build on a related result of Asadpour, Goemans, Mądry, Oveis Gharan, and Saberi to obtain this guarantee. Furthermore, we show how our technique yields stronger approximation bounds in some cases, such as the bounded orientable genus case studied by Oveis Gharan and Saberi. We also explore the possibility of further improvement upon our main result through a comparison to the symmetric counterpart of the problem.
Recommending Courses in MOOCs for Jobs: An Auto Weak Supervision Approach
Venue: arXiv cs.DB 2020
Year: 2020

The proliferation of massive open online courses (MOOCs) demands an effective way of course recommendation for jobs posted in recruitment websites, especially for the people who take MOOCs to find new jobs. Despite the advances of supervised ranking models, the lack of enough supervised signals prevents us from directly learning a supervised ranking model. This paper proposes a general automated weak supervision framework AutoWeakS via reinforcement learning to solve the problem. On the one hand, the framework enables training multiple supervised ranking models upon the pseudo labels produced by multiple unsupervised ranking models. On the other hand, the framework enables automatically searching the optimal combination of these supervised and unsupervised models. Systematically, we evaluate the proposed model on several datasets of jobs from different recruitment websites and courses from a MOOCs platform. Experiments show that our model significantly outperforms the classical unsupervised, supervised and weak supervision baselines.
FOREST: An Interactive Multi-tree Synthesizer for Regular Expressions
Venue: arXiv cs.FL 2020
Year: 2020

Form validators based on regular expressions are often used on digital forms to prevent users from inserting data in the wrong format. However, writing these validators can pose a challenge to some users. We present FOREST, a regular expression synthesizer for digital form validations. FOREST produces a regular expression that matches the desired pattern for the input values and a set of conditions over capturing groups that ensure the validity of integer values in the input. Our synthesis procedure is based on enumerative search and uses a Satisfiability Modulo Theories (SMT) solver to explore and prune the search space. We propose a novel representation for regular expressions synthesis, multi-tree, which induces patterns in the examples and uses them to split the problem through a divide-and-conquer approach. We also present a new SMT encoding to synthesize capture conditions for a given regular expression. To increase confidence in the synthesized regular expression, we implement user interaction based on distinguishing inputs. We evaluated FOREST on real-world form-validation instances using regular expressions. Experimental results show that FOREST successfully returns the desired regular expression in 72% of the instances and outperforms REGEL, a state-of-the-art regular expression synthesizer.
I-Health: Leveraging Edge Computing and Blockchain for Epidemic Management
Venue: arXiv cs.CY 2020
Year: 2020

Epidemic situations typically demand intensive data collection and management from different locations/entities within a strict time constraint. Such demand can be fulfilled by leveraging the intensive and easy deployment of the Internet of Things (IoT) devices. The management and containment of such situations also rely on cross-organizational and national collaboration. Thus, this paper proposes an Intelligent-Health (I-Health) system that aims to aggregate diverse e-health entities in a unique national healthcare system by enabling swift, secure exchange and storage of medical data. In particular, we design an automated patients monitoring scheme, at the edge, which enables the prompt discovery, remote monitoring, and fast emergency response for critical medical events, such as emerging epidemics. Furthermore, we develop a blockchain optimization model that aims to optimize medical data sharing between different health entities to provide effective and secure health services. Finally, we show the effectiveness of our system, in adapting to different critical events, while highlighting the benefits of the proposed I-Health system.
Freshness-Optimal Caching for Information Updating Systems with Limited Cache Storage Capacity
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we investigate a cache updating system with a server containing $N$ files, $K$ relays and $M$ users. The server keeps the freshest versions of the files which are updated with fixed rates. Each relay can download the fresh files from the server in a certain period of time. Each user can get the fresh files from any relay as long as the relay has stored the fresh versions of the requested files. Due to the limited storage capacity and updating capacity of each relay, different cache designs will lead to different average freshness of all updating files at users. In order to keep the average freshness as large as possible in the cache updating system, we formulate an average freshness-optimal cache updating problem (AFOCUP) to obtain an optimal cache scheme. However, because of the nonlinearity of the AFOCUP, it is difficult to seek out the optimal cache scheme. As a result, an linear approximate model is suggested by distributing the total update rates completely in accordance with the number of files in the relay in advance. Then we utilize the greedy algorithm to search the optimal cache scheme that is satisfied with the limited storage capacity of each relay. Finally, some numerical examples are provided to illustrate the performance of the approximate solution.
Approximate Automata for Omega-Regular Languages
Venue: arXiv cs.FL 2020
Year: 2020

Automata over infinite words, also known as omega-automata, play a key role in the verification and synthesis of reactive systems. The spectrum of omega-automata is defined by two characteristics: the acceptance condition (e.g. Büchi or parity) and the determinism (e.g., deterministic or nondeterministic) of an automaton. These characteristics play a crucial role in applications of automata theory. For example, certain acceptance conditions can be handled more efficiently than others by dedicated tools and algorithms. Furthermore, some applications, such as synthesis and probabilistic model checking, require that properties are represented as some type of deterministic omega-automata. However, properties cannot always be represented by automata with the desired acceptance condition and determinism. In this paper we study the problem of approximating linear-time properties by automata in a given class. Our approximation is based on preserving the language up to a user-defined precision given in terms of the size of the finite lasso representation of infinite executions that are preserved. We study the state complexity of different types of approximating automata, and provide constructions for the approximation within different automata classes, for example, for approximating a given automaton by one with a simpler acceptance condition.
Is human scoring the best criteria for summary evaluation?
Venue: arXiv cs.CL 2020
Year: 2020

Normally, summary quality measures are compared with quality scores produced by human annotators. A higher correlation with human scores is considered to be a fair indicator of a better measure. We discuss observations that cast doubt on this view. We attempt to show a possibility of an alternative indicator. Given a family of measures, we explore a criterion of selecting the best measure not relying on correlations with human scores. Our observations for the BLANC family of measures suggest that the criterion is universal across very different styles of summaries.