OpenRaiser/Intern-Atlas huggingface dataset:
DRIFT: A Toolkit for Diachronic Analysis of Scientific Literature
Venue: arXiv cs.CL 2021
Year: 2021

In this work, we present to the NLP community, and to the wider research community as a whole, an application for the diachronic analysis of research corpora. We open source an easy-to-use tool coined: DRIFT, which allows researchers to track research trends and development over the years. The analysis methods are collated from well-cited research works, with a few of our own methods added for good measure. Succinctly put, some of the analysis methods are: keyword extraction, word clouds, predicting declining/stagnant/growing trends using Productivity, tracking bi-grams using Acceleration plots, finding the Semantic Drift of words, tracking trends using similarity, etc. To demonstrate the utility and efficacy of our tool, we perform a case study on the cs.CL corpus of the arXiv repository and draw inferences from the analysis methods. The toolkit and the associated code are available here: https://github.com/rajaswa/DRIFT.
Solving Machine Learning Problems
Venue: arXiv cs.LG 2021
Year: 2021

Can a machine learn Machine Learning? This work trains a machine learning model to solve machine learning problems from a University undergraduate level course. We generate a new training set of questions and answers consisting of course exercises, homework, and quiz questions from MIT's 6.036 Introduction to Machine Learning course and train a machine learning model to answer these questions. Our system demonstrates an overall accuracy of 96% for open-response questions and 97% for multiple-choice questions, compared with MIT students' average of 93%, achieving grade A performance in the course, all in real-time. Questions cover all 12 topics taught in the course, excluding coding questions or questions with images. Topics include: (i) basic machine learning principles; (ii) perceptrons; (iii) feature extraction and selection; (iv) logistic regression; (v) regression; (vi) neural networks; (vii) advanced neural networks; (viii) convolutional neural networks; (ix) recurrent neural networks; (x) state machines and MDPs; (xi) reinforcement learning; and (xii) decision trees. Our system uses Transformer models within an encoder-decoder architecture with graph and tree representations. An important aspect of our approach is a data-augmentation scheme for generating new example problems. We also train a machine learning model to generate problem hints. Thus, our system automatically generates new questions across topics, answers both open-response questions and multiple-choice questions, classifies problems, and generates problem hints, pushing the envelope of AI for STEM education.
Linear Probing Revisited: Tombstones Mark the Death of Primary Clustering
Venue: arXiv cs.DS 2021
Year: 2021

First introduced in 1954, linear probing is one of the oldest data structures in computer science, and due to its unrivaled data locality, it continues to be one of the fastest hash tables in practice. It is widely believed and taught, however, that linear probing should never be used at high load factors; this is because primary-clustering effects cause insertions at load factor $1 - 1 /x$ to take expected time $Θ(x^2)$ (rather than the ideal $Θ(x)$). The dangers of primary clustering, first discovered by Knuth in 1963, have been taught to generations of computer scientists, and have influenced the design of some of many widely used hash tables. We show that primary clustering is not a foregone conclusion. We demonstrate that small design decisions in how deletions are implemented have dramatic effects on the asymptotic performance of insertions, so that, even if a hash table operates continuously at a load factor $1 - Θ(1/x)$, the expected amortized cost per operation is $\tilde{O}(x)$. This is because tombstones created by deletions actually cause an anti-clustering effect that combats primary clustering. We also present a new variant of linear probing (which we call graveyard hashing) that completely eliminates primary clustering on \emph{any} sequence of operations: if, when an operation is performed, the current load factor is $1 - 1/x$ for some $x$, then the expected cost of the operation is $O(x)$. One corollary is that, in the external-memory model with a data blocks of size $B$, graveyard hashing offers the following remarkable guarantee: at any load factor $1 - 1/x$ satisfying $x = o(B)$, graveyard hashing achieves $1 + o(1)$ expected block transfers per operation. Past external-memory hash tables have only been able to offer a $1 + o(1)$ guarantee when the block size $B$ is at least $Ω(x^2)$.
Non-Comparative Fairness for Human-Auditing and Its Relation to Traditional Fairness Notions
Venue: arXiv cs.LG 2021
Year: 2021

Bias evaluation in machine-learning based services (MLS) based on traditional algorithmic fairness notions that rely on comparative principles is practically difficult, making it necessary to rely on human auditor feedback. However, in spite of taking rigorous training on various comparative fairness notions, human auditors are known to disagree on various aspects of fairness notions in practice, making it difficult to collect reliable feedback. This paper offers a paradigm shift to the domain of algorithmic fairness via proposing a new fairness notion based on the principle of non-comparative justice. In contrary to traditional fairness notions where the outcomes of two individuals/groups are compared, our proposed notion compares the MLS' outcome with a desired outcome for each input. This desired outcome naturally describes a human auditor's expectation, and can be easily used to evaluate MLS on crowd-auditing platforms. We show that any MLS can be deemed fair from the perspective of comparative fairness (be it in terms of individual fairness, statistical parity, equal opportunity or calibration) if it is non-comparatively fair with respect to a fair auditor. We also show that the converse holds true in the context of individual fairness. Given that such an evaluation relies on the trustworthiness of the auditor, we also present an approach to identify fair and reliable auditors by estimating their biases with respect to a given set of sensitive attributes, as well as quantify the uncertainty in the estimation of biases within a given MLS. Furthermore, all of the above results are also validated on COMPAS, German credit and Adult Census Income datasets.
Breaking Barriers in Robotic Soft Tissue Surgery: Conditional Autonomous Intestinal Anastomosis
Venue: arXiv cs.RO 2021
Year: 2021

Autonomous robotic surgery has the potential to provide efficacy, safety, and consistency independent of individual surgeons skill and experience. Autonomous soft-tissue surgery in unstructured and deformable environments is especially challenging as it necessitates intricate imaging, tissue tracking and surgical planning techniques, as well as a precise execution via highly adaptable control strategies. In the laparoscopic setting, soft-tissue surgery is even more challenging due to the need for high maneuverability and repeatability under motion and vision constraints. We demonstrate the first robotic laparoscopic soft tissue surgery with a level of autonomy of 3 out of 5, which allows the operator to select among autonomously generated surgical plans while the robot executes a wide range of tasks independently. We also demonstrate the first in vivo autonomous robotic laparoscopic surgery via intestinal anastomosis on porcine models. We compared the criteria including needle placement corrections, suture spacing, suture bite size, completion time, lumen patency, and leak pressure between the developed system, manual laparoscopic surgery, and robot-assisted surgery (RAS). The ex vivo results indicate that our system outperforms expert surgeons and RAS techniques in terms of consistency and accuracy, and it leads to a remarkable anastomosis quality in living pigs. These results demonstrate that surgical robots exhibiting high levels of autonomy have the potential to improve consistency, patient outcomes, and access to a standard surgical technique.
DiSH-trend: Intervention Modeling Simulator That Accounts for Trend Influences
Venue: arXiv cs.CY 2021
Year: 2021

Simulation on directed graphs is an important method for understanding the dynamics in the systems where connectivity graphs contain cycles. Discrete Stochastic Heterogeneous Simulator (DiSH) is one of the simulation tools with wide application, which uses regulator values to calculate state updates of regulated elements. Here we present a new simulation approach DiSH-trend which also takes into account the trends in regulating elements. We demonstrate the features of trend-based regulation, as well as hybrid regulation, which is a combination of the trend- and level-based approaches. The modeling capabilities are demonstrated on a small toy model, showcasing different functionalities. Real-world capabilities are demonstrated on a larger network model of food insecurity in the Ethiopian region Oromia. Adding trend-based regulation to models results in increased modeling flexibility, and hybrid regulation improves qualitative dynamic behavior prediction. With appropriate data, DiSH-trend becomes a powerful tool for exploring intervention strategies.
SHORING: Design Provable Conditional High-Order Interaction Network via Symbolic Testing
Venue: arXiv cs.LG 2021
Year: 2021

Deep learning provides a promising way to extract effective representations from raw data in an end-to-end fashion and has proven its effectiveness in various domains such as computer vision, natural language processing, etc. However, in domains such as content/product recommendation and risk management, where sequence of event data is the most used raw data form and experts derived features are more commonly used, deep learning models struggle to dominate the game. In this paper, we propose a symbolic testing framework that helps to answer the question of what kinds of expert-derived features could be learned by a neural network. Inspired by this testing framework, we introduce an efficient architecture named SHORING, which contains two components: \textit{event network} and \textit{sequence network}. The \textit{event} network learns arbitrarily yet efficiently high-order \textit{event-level} embeddings via a provable reparameterization trick, the \textit{sequence} network aggregates from sequence of \textit{event-level} embeddings. We argue that SHORING is capable of learning certain standard symbolic expressions which the standard multi-head self-attention network fails to learn, and conduct comprehensive experiments and ablation studies on four synthetic datasets and three real-world datasets. The results show that SHORING empirically outperforms the state-of-the-art methods.
The HCCL Speaker Verification System for Far-Field Speaker Verification Challenge
Venue: arXiv cs.SD 2021
Year: 2021

This paper describes the systems submitted by team HCCL to the Far-Field Speaker Verification Challenge. Our previous work in the AIshell Speaker Verification Challenge 2019 shows that the powerful modeling abilities of Neural Network architectures can provide exceptional performance for this kind of task. Therefore, in this challenge, we focus on constructing deep Neural Network architectures based on TDNN, Resnet and Res2net blocks. Most of the developed systems consist of Neural Network embeddings are applied with PLDA backend. Firstly, the speed perturbation method is applied to augment data and significant performance improvements are achieved. Then, we explore the use of AMsoftmax loss function and propose to join a CE-loss branch when we train model using AMsoftmax loss. In addition, the impact of score normalization on performance is also investigated. The final system, a fusion of four systems, achieves minDCF 0.5342, EER 5.05\% on task1 eval set, and achieves minDCF 0.5193, EER 5.47\% on task3 eval set.
Cluster Representatives Selection in Non-Metric Spaces for Nearest Prototype Classification
Venue: arXiv cs.LG 2021
Year: 2021

The nearest prototype classification is a less computationally intensive replacement for the $k$-NN method, especially when large datasets are considered. In metric spaces, centroids are often used as prototypes to represent whole clusters. The selection of cluster prototypes in non-metric spaces is more challenging as the idea of computing centroids is not directly applicable. In this paper, we present CRS, a novel method for selecting a small yet representative subset of objects as a cluster prototype. Memory and computationally efficient selection of representatives is enabled by leveraging the similarity graph representation of each cluster created by the NN-Descent algorithm. CRS can be used in an arbitrary metric or non-metric space because of the graph-based approach, which requires only a pairwise similarity measure. As we demonstrate in the experimental evaluation, our method outperforms the state of the art techniques on multiple datasets from different domains.
Recent Advancements In Distributed System Communications
Venue: arXiv cs.NI 2021
Year: 2021

Overheads in Operating System kernel network stacks and sockets have been hindering OSes from managing networking operations efficiently for years. Moreover, when building Remote Procedure Calls over TCP, certain TCP features do not match the needs of RPCs, imposing additional overheads. These issues degrade the performance of distributed systems, which rely on fast communications between machines to be able to serve a large number of client requests with low latency and high throughput. The purpose of this literature survey is to look into recent proposals in research literature that aim to overcome these issues. The survey investigates research literature published between 2010-2020, in order to include important advancements during the most recent decade at the time of writing. The proposals found in papers have been categorized into hardware-based and software-based approaches. The former require specialized hardware to offer high communications performance. The latter are implemented in software and don't rely on specialized hardware or require only certain hardware features. Furthermore, the proposals where also classified according to whether they implement kernel bypass, to avoid using the Operating System kernel network stack, or not. The hardware-based approaches examined here are RDMA, programmable Network Interface Controllers (NIC) and System-on-a-Chip (SoC), while the software-based approaches include optimized socket implementations and RPC frameworks, as well as user space networking.
Learning from scarce information: using synthetic data to classify Roman fine ware pottery
Venue: arXiv cs.CV 2021
Year: 2021

In this article we consider a version of the challenging problem of learning from datasets whose size is too limited to allow generalisation beyond the training set. To address the challenge we propose to use a transfer learning approach whereby the model is first trained on a synthetic dataset replicating features of the original objects. In this study the objects were smartphone photographs of near-complete Roman terra sigillata pottery vessels from the collection of the Museum of London. Taking the replicated features from published profile drawings of pottery forms allowed the integration of expert knowledge into the process through our synthetic data generator. After this first initial training the model was fine-tuned with data from photographs of real vessels. We show, through exhaustive experiments across several popular deep learning architectures, different test priors, and considering the impact of the photograph viewpoint and excessive damage to the vessels, that the proposed hybrid approach enables the creation of classifiers with appropriate generalisation performance. This performance is significantly better than that of classifiers trained exclusively on the original data which shows the promise of the approach to alleviate the fundamental issue of learning from small datasets.
Development of a Conversation State Prediction System
Venue: arXiv cs.SD 2021
Year: 2021

With the evolution of the concept of Speaker diarization using LSTM, it is relatively easier to understand the speaker identities for specific segments of input audio stream data than manually tagging the data. With such a concept, it is highly desirable to consider the possibility of using the identified speaker identities to aid in recognizing the Speaker States in a conversation. In this study, the Markov Chains are used to identify and update the Speaker States for the next conversations between the same set of speakers, to enable identification of their states in the most natural and long conversations. The model is based on several audio samples from natural conversations of three or greater than three speakers in two datasets with overall total error percentages for recognized states being lesser than or equal to 12%. The findings imply that the proposed extension to the Speaker diarization is effective to predict the states for a conversation.
BAGUA: Scaling up Distributed Learning with System Relaxations
Venue: arXiv cs.LG 2021
Year: 2021

Recent years have witnessed a growing list of systems for distributed data-parallel training. Existing systems largely fit into two paradigms, i.e., parameter server and MPI-style collective operations. On the algorithmic side, researchers have proposed a wide range of techniques to lower the communication via system relaxations: quantization, decentralization, and communication delay. However, most, if not all, existing systems only rely on standard synchronous and asynchronous stochastic gradient (SG) based optimization, therefore, cannot take advantage of all possible optimizations that the machine learning community has been developing recently. Given this emerging gap between the current landscapes of systems and theory, we build BAGUA, a MPI-style communication library, providing a collection of primitives, that is both flexible and modular to support state-of-the-art system relaxation techniques of distributed training. Powered by this design, BAGUA has a great ability to implement and extend various state-of-the-art distributed learning algorithms. In a production cluster with up to 16 machines (128 GPUs), BAGUA can outperform PyTorch-DDP, Horovod and BytePS in the end-to-end training time by a significant margin (up to 2 times) across a diverse range of tasks. Moreover, we conduct a rigorous tradeoff exploration showing that different algorithms and system relaxations achieve the best performance over different network conditions.
The Semantics of Package Management via Event Structures
Venue: arXiv cs.LO 2021
Year: 2021

We propose an approach to the semantics of package management which relates it to general event structures, well-known mathematical objects used in the semantics of concurrent, nondeterministic systems. In this approach, the data of a package repository is treated as a declarative specification of a nondeterministic, concurrent program. We introduce a process calculus corresponding to this data, and investigate its operational and categorical semantics. Our hope is this lays the basis for further formal study of package management in which the weight of existing tools can be brought to bear.
Robust End-to-End Offline Chinese Handwriting Text Page Spotter with Text Kernel
Venue: arXiv cs.CV 2021
Year: 2021

Offline Chinese handwriting text recognition is a long-standing research topic in the field of pattern recognition. In previous studies, text detection and recognition are separated, which leads to the fact that text recognition is highly dependent on the detection results. In this paper, we propose a robust end-to-end Chinese text page spotter framework. It unifies text detection and text recognition with text kernel that integrates global text feature information to optimize the recognition from multiple scales, which reduces the dependence of detection and improves the robustness of the system. Our method achieves state-of-the-art results on the CASIA-HWDB2.0-2.2 dataset and ICDAR-2013 competition dataset. Without any language model, the correct rates are 99.12% and 94.27% for line-level recognition, and 99.03% and 94.20% for page-level recognition, respectively.
Multiple-criteria Based Active Learning with Fixed-size Determinantal Point Processes
Venue: arXiv cs.LG 2021
Year: 2021

Active learning aims to achieve greater accuracy with less training data by selecting the most useful data samples from which it learns. Single-criterion based methods (i.e., informativeness and representativeness based methods) are simple and efficient; however, they lack adaptability to different real-world scenarios. In this paper, we introduce a multiple-criteria based active learning algorithm, which incorporates three complementary criteria, i.e., informativeness, representativeness and diversity, to make appropriate selections in the active learning rounds under different data types. We consider the selection process as a Determinantal Point Process, which good balance among these criteria. We refine the query selection strategy by both selecting the hardest unlabeled data sample and biasing towards the classifiers that are more suitable for the current data distribution. In addition, we also consider the dependencies and relationships between these data points in data selection by means of centroidbased clustering approaches. Through evaluations on synthetic and real-world datasets, we show that our method performs significantly better and is more stable than other multiple-criteria based AL algorithms.
Machine Learning for Malware Evolution Detection
Venue: arXiv cs.CR 2021
Year: 2021

Malware evolves over time and antivirus must adapt to such evolution. Hence, it is critical to detect those points in time where malware has evolved so that appropriate countermeasures can be undertaken. In this research, we perform a variety of experiments on a significant number of malware families to determine when malware evolution is likely to have occurred. All of the evolution detection techniques that we consider are based on machine learning and can be fully automated -- in particular, no reverse engineering or other labor-intensive manual analysis is required. Specifically, we consider analysis based on hidden Markov models (HMM) and the word embedding techniques HMM2Vec and Word2Vec.
Sublinear-Space Approximation Algorithms for Max r-SAT
Venue: arXiv cs.DS 2021
Year: 2021

In the Max $r$-SAT problem, the input is a CNF formula with $n$ variables where each clause is a disjunction of at most $r$ literals. The objective is to compute an assignment which satisfies as many of the clauses as possible. While there are a large number of polynomial-time approximation algorithms for this problem, we take the viewpoint of space complexity following [Biswas et al., Algorithmica 2021] and design sublinear-space approximation algorithms for the problem. We show that the classical algorithm of [Lieberherr and Specker, JACM 1981] can be implemented to run in $n^{O(1)}$ time while using $(\log{n})$ bits of space. The more advanced algorithms use linear or semi-definite programming, and seem harder to carry out in sublinear space. We show that a more recent algorithm with approximation ratio $\sqrt{2}/2$ [Chou et al., FOCS 2020], designed for the streaming model, can be implemented to run in time $n^{O(r)}$ using $O(r \log{n})$ bits of space. While known streaming algorithms for the problem approximate optimum values and use randomization, our algorithms are deterministic and can output the approximately optimal assignments in sublinear space. For instances of Max $r$-SAT with planar incidence graphs, we devise a factor-$(1 - ε)$ approximation scheme which computes assignments in time $n^{O(r / ε)}$ and uses $\max\{\sqrt{n} \log{n}, (r / ε) \log^2{n}\}$ bits of space.