OpenRaiser/Intern-Atlas huggingface dataset:
Automated, Targeted Testing of Property-Based Testing Predicates
Venue: arXiv cs.PL 2021
Year: 2021

Context: This work is based on property-based testing (PBT). PBT is an increasingly important form of software testing. Furthermore, it serves as a concrete gateway into the abstract area of formal methods. Specifically, we focus on students learning PBT methods. Inquiry: How well do students do at PBT? Our goal is to assess the quality of the predicates they write as part of PBT. Prior work introduced the idea of decomposing the predicate's property into a conjunction of independent subproperties. Testing the predicate against each subproperty gives a "semantic" understanding of their performance. Approach: The notion of independence of subproperties both seems intuitive and was an important condition in prior work. First, we show that this condition is overly restrictive and might hide valuable information: it both undercounts errors and makes it hard to capture misconceptions. Second, we introduce two forms of automation, one based on PBT tools and the other on SAT-solving, to enable testing of student predicates. Third, we compare the output of these automated tools against manually-constructed tests. Fourth, we also measure the performance of those tools. Finally, we re-assess student performance reported in prior work. Knowledge: We show the difficulty caused by the independent subproperty requirement. We provide insight into how to use automation effectively to assess PBT predicates. In particular, we discuss the steps we had to take to beat human performance. We also provide insight into how to make the automation work efficiently. Finally, we present a much richer account than prior work of how students did. Grounding: Our methods are grounded in mathematical logic. We also make use of well-understood principles of test generation from more formal specifications. This combination ensures the soundness of our work. We use standard methods to measure performance. Importance: As both educators and programmers, we believe PBT is a valuable tool for students to learn, and its importance will only grow as more developers appreciate its value. Effective teaching requires a clear understanding of student knowledge and progress. Our methods enable a rich and automated analysis of student performance on PBT that yields insight into their understanding and can capture misconceptions. We therefore expect these results to be valuable to educators.
A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
Venue: arXiv cs.CC 2021
Year: 2021

We refute the Probabilistic Universal Graph Conjecture of Harms, Wild, and Zamaraev, which states that a hereditary graph property admits a constant-size probabilistic universal graph if and only if it is stable and has at most factorial speed. Our counter-example follows from the existence of a sequence of $n \times n$ Boolean matrices $M_n$, such that their public-coin randomized communication complexity tends to infinity, while the randomized communication complexity of every $\sqrt{n}\times \sqrt{n}$ submatrix of $M_n$ is bounded by a universal constant.
Identifying Population Movements with Non-Negative Matrix Factorization from Wi-Fi User Counts in Smart and Connected Cities
Venue: arXiv cs.LG 2021
Year: 2021

Non-Negative Matrix Factorization (NMF) is a valuable matrix factorization technique which produces a "parts-based" decomposition of data sets. Wi-Fi user counts are a privacy-preserving indicator of population movements in smart and connected urban environments. In this paper, we apply NMF with a novel matrix embedding to Wi-Fi user count data from the University of Colorado at Boulder Campus for the purpose of automatically identifying patterns of human movement in a Smart and Connected infrastructure environment.
Online Coverage Planning for an Autonomous Weed Mowing Robot with Curvature Constraints
Venue: arXiv cs.RO 2021
Year: 2021

The land used for grazing cattle takes up about one-third of the land in the United States. These areas can be highly rugged. Yet, they need to be maintained to prevent weeds from taking over the nutritious grassland. This can be a daunting task especially in the case of organic farming since herbicides cannot be used. In this paper, we present the design of Cowbot, an autonomous weed mowing robot for pastures. Cowbot is an electric mower designed to operate in the rugged environments on cow pastures and provide a cost-effective method for weed control in organic farms. Path planning for the Cowbot is challenging since weed distribution on pastures is unknown. Given a limited field of view, online path planning is necessary to detect weeds and plan paths to mow them. We study the general online path planning problem for an autonomous mower with curvature and field of view constraints. We develop two online path planning algorithms that are able to utilize new information about weeds to optimize path length and ensure coverage. We deploy our algorithms on the Cowbot and perform field experiments to validate the suitability of our methods for real-time path planning. We also perform extensive simulation experiments which show that our algorithms result in up to 60 % reduction in path length as compared to baseline boustrophedon and random-search based coverage paths.
Imitation and Supervised Learning of Compliance for Robotic Assembly
Venue: arXiv cs.RO 2021
Year: 2021

We present the design of a learning-based compliance controller for assembly operations for industrial robots. We propose a solution within the general setting of learning from demonstration (LfD), where a nominal trajectory is provided through demonstration by an expert teacher. This can be used to learn a suitable representation of the skill that can be generalized to novel positions of one of the parts involved in the assembly, for example the hole in a peg-in-hole (PiH) insertion task. Under the expectation that this novel position might not be entirely accurately estimated by a vision or other sensing system, the robot will need to further modify the generated trajectory in response to force readings measured by means of a force-torque (F/T) sensor mounted at the wrist of the robot or another suitable location. Under the assumption of constant velocity of traversing the reference trajectory during assembly, we propose a novel accommodation force controller that allows the robot to safely explore different contact configurations. The data collected using this controller is used to train a Gaussian process model to predict the misalignment in the position of the peg with respect to the target hole. We show that the proposed learning-based approach can correct various contact configurations caused by misalignment between the assembled parts in a PiH task, achieving high success rate during insertion. We show results using an industrial manipulator arm, and demonstrate that the proposed method can perform adaptive insertion using force feedback from the trained machine learning models.
Study of Polar Codes Based on Piecewise Gaussian Approximation
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we investigate the construction of polar codes by Gaussian approximation (GA) and develop an approach based on piecewise Gaussian approximation (PGA). In particular, with the piecewise approach we obtain a function that replaces the original GA function with a more accurate approximation, which results in significant gain in performance. The proposed PGA construction of polar codes is presented in its integral form as well as an alternative approximation that does not rely on the integral form. Simulations results show that the proposed PGA construction outperforms the standard GA for several examples of polar codes and rates.
FAMINet: Learning Real-time Semi-supervised Video Object Segmentation with Steepest Optimized Optical Flow
Venue: arXiv cs.CV 2021
Year: 2021

Semi-supervised video object segmentation (VOS) aims to segment a few moving objects in a video sequence, where these objects are specified by annotation of first frame. The optical flow has been considered in many existing semi-supervised VOS methods to improve the segmentation accuracy. However, the optical flow-based semi-supervised VOS methods cannot run in real time due to high complexity of optical flow estimation. A FAMINet, which consists of a feature extraction network (F), an appearance network (A), a motion network (M), and an integration network (I), is proposed in this study to address the abovementioned problem. The appearance network outputs an initial segmentation result based on static appearances of objects. The motion network estimates the optical flow via very few parameters, which are optimized rapidly by an online memorizing algorithm named relaxed steepest descent. The integration network refines the initial segmentation result using the optical flow. Extensive experiments demonstrate that the FAMINet outperforms other state-of-the-art semi-supervised VOS methods on the DAVIS and YouTube-VOS benchmarks, and it achieves a good trade-off between accuracy and efficiency. Our code is available at https://github.com/liuziyang123/FAMINet.
Optimal Grouping Strategy for Reconfigurable Intelligent Surface Assisted Wireless Communications
Venue: arXiv cs.IT 2021
Year: 2021

The channel estimation overhead of reconfigurable intelligent surface (RIS) assisted communication systems can be prohibitive. Prior works have demonstrated via simulations that grouping neighbouring RIS elements can help to reduce the pilot overhead and improve achievable rate. In this paper, we present an analytical study of RIS element grouping. We derive a tight closed-form upper bound for the achievable rate and then maximize it with respect to the group size. Our analysis reveals that more coarse-grained grouping is important-when the channel coherence time is low (high mobility scenarios) or the transmit power is large. We also demonstrate that optimal grouping can yield significant performance improvements over simple `On-Off' RIS element switching schemes that have been recently considered.
Control Analysis of Packet Transmission Algorithms: Study on Fairness and Stability
Venue: arXiv cs.NI 2021
Year: 2021

This document is a study of fairness, feedback and stability notions of different packet transmission algorithms. We start the discussion with defining two scalable control algorithms namely primal and dual algorithm. We discuss the dual algorithm model and then understand the fair dual algorithm. Further, we discuss different notions of fairness under fair dual algorithm those correspond to TCP and RCP congestion control protocols. Feedback parameters are analyzed in each of these fairness algorithms and thus their stability is studied.
Improving Tagging Consistency and Entity Coverage for Chemical Identification in Full-text Articles
Venue: arXiv cs.CL 2021
Year: 2021

This paper is a technical report on our system submitted to the chemical identification task of the BioCreative VII Track 2 challenge. The main feature of this challenge is that the data consists of full-text articles, while current datasets usually consist of only titles and abstracts. To effectively address the problem, we aim to improve tagging consistency and entity coverage using various methods such as majority voting within the same articles for named entity recognition (NER) and a hybrid approach that combines a dictionary and a neural model for normalization. In the experiments on the NLM-Chem dataset, we show that our methods improve models' performance, particularly in terms of recall. Finally, in the official evaluation of the challenge, our system was ranked 1st in NER by significantly outperforming the baseline model and more than 80 submissions from 16 teams.
Frailty Care Robot for Elderly and Its Application for Physical and Psychological Support
Venue: arXiv cs.RO 2021
Year: 2021

To achieve continuous frail care in the daily lives of the elderly, we propose AHOBO, a frail care robot for the elderly at home. Two types of support systems by AHOBO were implemented to support the elderly in both physical health and psychological aspects. For physical health frailty care, we focused on blood pressure and developed a support system for blood pressure measurement with AHOBO. For psychological frailty care, we implemented reminiscent coloring with the AHOBO as a recreational activity with the robot. The usability of the system was evaluated based on the assumption of continuous use in daily life. For the support system in blood pressure measurement, we performed a qualitative evaluation using a questionnaire for 16 subjects, including elderly people under blood pressure measurement by the system. The results confirmed that the proposed robot does not affect the blood pressure readings and is acceptable in terms of ease of use based on subjective evaluation. For the reminiscent coloring interaction, a subjective evaluation was conducted on two elderly people under the verbal fluency task, and it has been confirmed that the interaction can be used continuously in daily life. The widespread use of the proposed robot as an interface for AI that supports daily life will lead to a society in which AI robots support people from the cradle to the grave.
Textbook to triples: Creating knowledge graph in the form of triples from AI TextBook
Venue: arXiv cs.CL 2021
Year: 2021

A knowledge graph is an essential and trending technology with great applications in entity recognition, search, or question answering. There are a plethora of methods in natural language processing for performing the task of Named entity recognition; however, there are very few methods that could provide triples for a domain-specific text. In this paper, an effort has been made towards developing a system that could convert the text from a given textbook into triples that can be used to visualize as a knowledge graph and use for further applications. The initial assessment and evaluation gave promising results with an F1 score of 82%.
Capitalization and Punctuation Restoration: a Survey
Venue: arXiv cs.CL 2021
Year: 2021

Ensuring proper punctuation and letter casing is a key pre-processing step towards applying complex natural language processing algorithms. This is especially significant for textual sources where punctuation and casing are missing, such as the raw output of automatic speech recognition systems. Additionally, short text messages and micro-blogging platforms offer unreliable and often wrong punctuation and casing. This survey offers an overview of both historical and state-of-the-art techniques for restoring punctuation and correcting word casing. Furthermore, current challenges and research directions are highlighted.
Federated Social Recommendation with Graph Neural Network
Venue: arXiv cs.IR 2021
Year: 2021

Recommender systems have become prosperous nowadays, designed to predict users' potential interests in items by learning embeddings. Recent developments of the Graph Neural Networks~(GNNs) also provide recommender systems with powerful backbones to learn embeddings from a user-item graph. However, only leveraging the user-item interactions suffers from the cold-start issue due to the difficulty in data collection. Hence, current endeavors propose fusing social information with user-item interactions to alleviate it, which is the social recommendation problem. Existing work employs GNNs to aggregate both social links and user-item interactions simultaneously. However, they all require centralized storage of the social links and item interactions of users, which leads to privacy concerns. Additionally, according to strict privacy protection under General Data Protection Regulation, centralized data storage may not be feasible in the future, urging a decentralized framework of social recommendation. To this end, we devise a novel framework \textbf{Fe}drated \textbf{So}cial recommendation with \textbf{G}raph neural network (FeSoG). Firstly, FeSoG adopts relational attention and aggregation to handle heterogeneity. Secondly, FeSoG infers user embeddings using local data to retain personalization. Last but not least, the proposed model employs pseudo-labeling techniques with item sampling to protect the privacy and enhance training. Extensive experiments on three real-world datasets justify the effectiveness of FeSoG in completing social recommendation and privacy protection. We are the first work proposing a federated learning framework for social recommendation to the best of our knowledge.
A hybrid optimization approach for employee rostering: Use cases at Swissgrid and lessons learned
Venue: arXiv cs.AI 2021
Year: 2021

Employee rostering is a process of assigning available employees to open shifts. Automating it has ubiquitous practical benefits for nearly all industries, such as reducing manual workload and producing flexible, high-quality schedules. In this work, we develop a hybrid methodology which combines Mixed-Integer Linear Programming (MILP) with scatter search, an evolutionary algorithm, having as use case the optimization of employee rostering for Swissgrid, where it is currently a largely manual process. The hybrid methodology guarantees compliance with labor laws, maximizes employees' preference satisfaction, and distributes workload as uniformly as possible among them. Above all, it is shown to be a robust and efficient algorithm, consistently solving realistic problems of varying complexity to near-optimality an order of magnitude faster than an MILP-alone approach using a state-of-the-art commercial solver. Several practical extensions and use cases are presented, which are incorporated into a software tool currently being in pilot use at Swissgrid.
Qimaera: Type-safe (Variational) Quantum Programming in Idris
Venue: arXiv cs.PL 2021
Year: 2021

Variational Quantum Algorithms are hybrid classical-quantum algorithms where classical and quantum computation work in tandem to solve computational problems. These algorithms create interesting challenges for the design of suitable programming languages. In this paper we introduce Qimaera, which is a set of libraries for the Idris 2 programming language that enable the programmer to implement (variational) quantum algorithms where the full power of the elegant Idris language works in synchrony with quantum programming primitives that we introduce. The two key ingredients of Idris that make this possible are (1) dependent types which allow us to implement unitary (i.e. reversible and controllable) quantum operations; and (2) linearity which allows us to enforce fine-grained control over the execution of quantum operations that ensures compliance with the laws of quantum mechanics. We demonstrate that Qimaera is suitable for variational quantum programming by providing implementations of the two most prominent variational quantum algorithms -- QAOA and VQE. To the best of our knowledge, this is the first implementation of these algorithms that has been achieved in a type-safe framework.
A Software Tool for Evaluating Unmanned Autonomous Systems
Venue: arXiv cs.SE 2021
Year: 2021

The North Carolina Agriculture and Technical State University (NC A&T) in collaboration with Georgia Tech Research Institute (GTRI) has developed methodologies for creating simulation-based technology tools that are capable of inferring the perceptions and behavioral states of autonomous systems. These methodologies have the potential to provide the Test and Evaluation (T&E) community at the Department of Defense (DoD) with a greater insight into the internal processes of these systems. The methodologies use only external observations and do not require complete knowledge of the internal processing of and/or any modifications to the system under test. This paper presents an example of one such simulation-based technology tool, named as the Data-Driven Intelligent Prediction Tool (DIPT). DIPT was developed for testing a multi-platform Unmanned Aerial Vehicle (UAV) system capable of conducting collaborative search missions. DIPT's Graphical User Interface (GUI) enables the testers to view the aircraft's current operating state, predicts its current target-detection status, and provides reasoning for exhibiting a particular behavior along with an explanation of assigning a particular task to it.
Hierarchical Knowledge Distillation for Dialogue Sequence Labeling
Venue: arXiv cs.CL 2021
Year: 2021

This paper presents a novel knowledge distillation method for dialogue sequence labeling. Dialogue sequence labeling is a supervised learning task that estimates labels for each utterance in the target dialogue document, and is useful for many applications such as dialogue act estimation. Accurate labeling is often realized by a hierarchically-structured large model consisting of utterance-level and dialogue-level networks that capture the contexts within an utterance and between utterances, respectively. However, due to its large model size, such a model cannot be deployed on resource-constrained devices. To overcome this difficulty, we focus on knowledge distillation which trains a small model by distilling the knowledge of a large and high performance teacher model. Our key idea is to distill the knowledge while keeping the complex contexts captured by the teacher model. To this end, the proposed method, hierarchical knowledge distillation, trains the small model by distilling not only the probability distribution of the label classification, but also the knowledge of utterance-level and dialogue-level contexts trained in the teacher model by training the model to mimic the teacher model's output in each level. Experiments on dialogue act estimation and call scene segmentation demonstrate the effectiveness of the proposed method.
Learning Explicit User Interest Boundary for Recommendation
Venue: arXiv cs.IR 2021
Year: 2021

The core objective of modelling recommender systems from implicit feedback is to maximize the positive sample score $s_p$ and minimize the negative sample score $s_n$, which can usually be summarized into two paradigms: the pointwise and the pairwise. The pointwise approaches fit each sample with its label individually, which is flexible in weighting and sampling on instance-level but ignores the inherent ranking property. By qualitatively minimizing the relative score $s_n - s_p$, the pairwise approaches capture the ranking of samples naturally but suffer from training efficiency. Additionally, both approaches are hard to explicitly provide a personalized decision boundary to determine if users are interested in items unseen. To address those issues, we innovatively introduce an auxiliary score $b_u$ for each user to represent the User Interest Boundary(UIB) and individually penalize samples that cross the boundary with pairwise paradigms, i.e., the positive samples whose score is lower than $b_u$ and the negative samples whose score is higher than $b_u$. In this way, our approach successfully achieves a hybrid loss of the pointwise and the pairwise to combine the advantages of both. Analytically, we show that our approach can provide a personalized decision boundary and significantly improve the training efficiency without any special sampling strategy. Extensive results show that our approach achieves significant improvements on not only the classical pointwise or pairwise models but also state-of-the-art models with complex loss function and complicated feature encoding.