OpenRaiser/Intern-Atlas huggingface dataset:
Syntactic Vs. Semantic similarity of Artificial and Real Faults in Mutation Testing Studies
Venue: arXiv cs.SE 2021
Year: 2021

Fault seeding is typically used in controlled studies to evaluate and compare test techniques. Central to these techniques lies the hypothesis that artificially seeded faults involve some form of realistic properties and thus provide realistic experimental results. In an attempt to strengthen realism, a recent line of research uses advanced machine learning techniques, such as deep learning and Natural Language Processing (NLP), to seed faults that look like (syntactically) real ones, implying that fault realism is related to syntactic similarity. This raises the question of whether seeding syntactically similar faults indeed results in semantically similar faults and more generally whether syntactically dissimilar faults are far away (semantically) from the real ones. We answer this question by employing 4 fault-seeding techniques (PiTest - a popular mutation testing tool, IBIR - a tool with manually crafted fault patterns, DeepMutation - a learning-based fault seeded framework and CodeBERT - a novel mutation testing tool that use code embeddings) and demonstrate that syntactic similarity does not reflect semantic similarity. We also show that 60%, 47%, 43%, and 7% of the real faults of Defects4J V2 are semantically resembled by CodeBERT, PiTest, IBIR, and DeepMutation faults. We then perform an objective comparison between the techniques and find that CodeBERT and PiTest have similar fault detection capabilities that subsume IBIR and DeepMutation, and that IBIR is the most cost-effective technique. Moreover, the overall fault detection of PiTest, CodeBERT, IBIR, and DeepMutation was, on average, 54%, 53%, 37%, and 7%.
Concurrent Realizability on Conjunctive Structures
Venue: arXiv cs.LO 2021
Year: 2021

The point of this work is to explore axiomatisations of concurrent computation using the technology of proof theory and realizability. To deal with this problem, we redefine the Concurrent Realizability of Beffara using as realizers a $π$-calculus with global fusions. We define a variant of the Conjunctive Structures of É Miquey as a general structure where belong realizers and truth values from realizability. As for Secuential Realizability, we encode the realizers into the algebraic structure by means of a combinatory presentation, following the work of Honda & Yoshida. In this first work we restricted to work with the $π$-calculus without replication and its corresponding type system is the multiplicative linear logic (MLL).
Private Rank Aggregation in Central and Local Models
Venue: arXiv cs.DS 2021
Year: 2021

In social choice theory, (Kemeny) rank aggregation is a well-studied problem where the goal is to combine rankings from multiple voters into a single ranking on the same set of items. Since rankings can reveal preferences of voters (which a voter might like to keep private), it is important to aggregate preferences in such a way to preserve privacy. In this work, we present differentially private algorithms for rank aggregation in the pure and approximate settings along with distribution-independent utility upper and lower bounds. In addition to bounds in the central model, we also present utility bounds for the local model of differential privacy.
ReSplit: Improving the Structure of Jupyter Notebooks by Re-Splitting Their Cells
Venue: arXiv cs.SE 2021
Year: 2021

Jupyter notebooks represent a unique format for programming - a combination of code and Markdown with rich formatting, separated into individual cells. We propose to perceive a Jupyter Notebook cell as a simplified and raw version of a programming function. Similar to functions, Jupyter cells should strive to contain singular, self-contained actions. At the same time, research shows that real-world notebooks fail to do so and suffer from the lack of proper structure. To combat this, we propose ReSplit, an algorithm for an automatic re-splitting of cells in Jupyter notebooks. The algorithm analyzes definition-usage chains in the notebook and consists of two parts - merging and splitting the cells. We ran the algorithm on a large corpus of notebooks to evaluate its performance and its overall effect on notebooks, and evaluated it by human experts: we showed them several notebooks in their original and the re-split form. In 29.5% of cases, the re-split notebook was selected as the preferred way of perceiving the code. We analyze what influenced this decision and describe several individual cases in detail.
A Test Bench For Evaluating Exoskeletons For Upper Limb Rehabilitation
Venue: arXiv cs.RO 2021
Year: 2021

The potential of wearable robotics technology is undeniable. However, quantifying its value is difficult. Various types of exoskeleton robots have already been developed and tested for upper limb rehabilitation but, evaluations are not standardized, particularly in pediatric rehabilitation. This paper proposes a methodology for the quantitative evaluation of upper limb exoskeletons that, like a test bench, would serve for replicable testing. We determined the range of motion (ROM) and joint torques using both kinematic modeling and experimental measurements (using sensors integrated into Dynamixel actuators). The proposed test bench can provide an accurate range of motion (ROM) and joint torques during the pronation-supination (PS) task. The range of motion obtained with the physical prototype was approximately 156.26 +- 4.71° during the PS task, while it was approximately 146.84 +- 14.32° for the multibody model. The results show that the average range of experimental torques (0.28 +- 0.06 N.m) was overestimated by 40% and just 3.4%, respectively, when compared to the average range of simulated torques (0.2 +- 0.05 N.m) and to the highest range of simulated torques (0.29 N.m). For the experimental measurements, test-retest reliability was excellent (0.96-0.98) within sessions and excellent (0.93) or good (0.81-0.86) between sessions. Finally, the suggested approach provides a ROM close to the normal ROM necessary during PS tasks. These results validate the measurements' accuracy and underline the proposed methodology's relevance. The proposed test bench could become a reference standard for evaluating exoskeletons. This study also addresses a methodological aspect on the accurate assessment of joint torques that can serve in applications such as the sizing of actuators in exoskeletons or the non-invasive evaluation of muscle forces in the human body.
Reversible Upper Confidence Bound Algorithm to Generate Diverse Optimized Candidates
Venue: arXiv cs.LG 2021
Year: 2021

Most algorithms for the multi-armed bandit problem in reinforcement learning aimed to maximize the expected reward, which are thus useful in searching the optimized candidate with the highest reward (function value) for diverse applications (e.g., AlphaGo). However, in some typical application scenaios such as drug discovery, the aim is to search a diverse set of candidates with high reward. Here we propose a reversible upper confidence bound (rUCB) algorithm for such a purpose, and demonstrate its application in virtual screening upon intrinsically disordered proteins (IDPs). It is shown that rUCB greatly reduces the query times while achieving both high accuracy and low performance loss.The rUCB may have potential application in multipoint optimization and other reinforcement-learning cases.
A Survey of Deep Learning Techniques for Dynamic Branch Prediction
Venue: arXiv cs.AR 2021
Year: 2021

Branch prediction is an architectural feature that speeds up the execution of branch instruction on pipeline processors and reduces the cost of branching. Recent advancements of Deep Learning (DL) in the post Moore's Law era is accelerating areas of automated chip design, low-power computer architectures, and much more. Traditional computer architecture design and algorithms could benefit from dynamic predictors based on deep learning algorithms which learns from experience by optimizing its parameters on large number of data. In this survey paper, we focus on traditional branch prediction algorithms, analyzes its limitations, and presents a literature survey of how deep learning techniques can be applied to create dynamic branch predictors capable of predicting conditional branch instructions. Prior surveys in this field focus on dynamic branch prediction techniques based on neural network perceptrons. We plan to improve the survey based on latest research in DL and advanced Machine Learning (ML) based branch predictors.
Tiansuan Constellation: An Open Research Platform
Venue: arXiv cs.DC 2021
Year: 2021

Satellite network is the first step of interstellar voyages. It can provide global Internet connectivity everywhere on earth, where most areas cannot access the Internet by the terrestrial infrastructure due to the geographic accessibility and high cost. The space industry experiences a rise in large low-earth-orbit satellite constellations to achieve universal connectivity. The research community is also urgent to do some leading research to bridge the connectivity divide. Researchers now conduct their work by simulation, which is far from enough. However, experiments on real satellites are blocked by the high threshold of space technology, such as deployment cost and unknown risks. To solve the above dilemma, we are eager to contribute to the universal connectivity and build an open research platform, Tiansuan constellation to support experiments on real satellite networks. We discuss the potential research topics that would benefit from Tiansuan constellation. We provide two case studies that have already deployed in two experimental satellites of Tiansuan constellation.
Flag: a Self-Dual Modality for Non-Commutative Contraction and Duplication in the Category of Coherence Spaces
Venue: arXiv cs.LO 2021
Year: 2021

After reminding what coherences spaces are and how they interpret linear logic, we define a modality "flag" in the category of coherence spaces (or hypercoherences) with two inverse linear (iso)morphisms: "duplication" from (flag A) to ((flag A) < (flag A)) and "contraction" in the opposite direction -- where < is the self dual and non-commutative connective known as "before" in pomset logic and known as "seq(ential)" in the deep inference system (S)BV. In addition, as expected, the coherence space A is a retract of its modal image (flag A). This suggests an intuitive interpretation of (flag A) as "repeatedly A" or as "A at any instant" when "before" is given a temporal interpretation. We hope the semantic construction of flag(A) will help to design proof rules for "flag" and we briefly discuss this at the end of the paper.
Exponentially Handsome Proof Nets and Their Normalization
Venue: arXiv cs.LO 2021
Year: 2021

Handsome proof nets were introduced by Retoré as a syntax for multiplicative linear logic. These proof nets are defined by means of cographs (graphs representing formulas) equipped with a vertices partition satisfying simple topological conditions. In this paper we extend this syntax to multiplicative linear logic with units and exponentials. For this purpose we develop a new sound and complete sequent system for the logic, enforcing a stronger notion of proof equivalence with respect to the one usually considered in the literature. We then define combinatorial proofs, a graphical proof system able to capture syntactically the proof equivalence, for the cut-free fragment of the calculus. We conclude the paper by defining the exponentially handsome proof nets as combinatorial proofs with cuts and defining an internal normalization procedure for this syntax.
A Braided Lambda Calculus
Venue: arXiv cs.LO 2021
Year: 2021

We present an untyped linear lambda calculus with braids, the corresponding combinatory logic, and the semantic models given by crossed G-sets.
Harmony in the Light of Computational Ludics
Venue: arXiv cs.LO 2021
Year: 2021

Prawitz formulated the so-called inversion principle as one of the characteristic features of Gentzen's intuitionistic natural deduction. In the literature on proof-theoretic semantics, this principle is often coupled with another that is called the recovery principle. By adopting the Computational Ludics framework, we reformulate these principles into one and the same condition, which we call the harmony condition. We show that this reformulation allows us to reveal two intuitive ideas standing behind these principles: the idea of "containment" present in the inversion principle, and the idea that the recovery principle is the "converse" of the inversion principle. We also formulate two other conditions in the Computational Ludics framework, and we show that each of them is equivalent to the harmony condition.
Efficiently Enumerating Scaled Copies of Point Set Patterns
Venue: arXiv cs.CG 2021
Year: 2021

Problems on repeated geometric patterns in finite point sets in Euclidean space are extensively studied in the literature of combinatorial and computational geometry. Such problems trace their inspiration to Erdős' original work on that topic. In this paper, we investigate the particular case of finding scaled copies of any pattern within a set of $n$ points, that is, the algorithmic task of efficiently enumerating all such copies. We initially focus on one particularly simple pattern of axis-parallel squares, and present an algorithm with an $O(n\sqrt{n})$ running time and $O(n)$ space for this task, involving various bucket-based and sweep-line techniques. Our algorithm is worst-case optimal, as it matches the known lower bound of $Ω(n\sqrt{n})$ on the maximum number of axis-parallel squares determined by $n$ points in the plane, thereby solving an open question for more than three decades of realizing that bound for this pattern. We extend our result to an algorithm that enumerates all copies, up to scaling, of any full-dimensional fixed set of points in $d$-dimensional Euclidean space, that works in time $O(n^{1+1/d})$ and space $O(n)$, also matching the corresponding lower bound due to Elekes and Erdős.
Investigating Pose Representations and Motion Contexts Modeling for 3D Motion Prediction
Venue: arXiv cs.CV 2021
Year: 2021

Predicting human motion from historical pose sequence is crucial for a machine to succeed in intelligent interactions with humans. One aspect that has been obviated so far, is the fact that how we represent the skeletal pose has a critical impact on the prediction results. Yet there is no effort that investigates across different pose representation schemes. We conduct an indepth study on various pose representations with a focus on their effects on the motion prediction task. Moreover, recent approaches build upon off-the-shelf RNN units for motion prediction. These approaches process input pose sequence sequentially and inherently have difficulties in capturing long-term dependencies. In this paper, we propose a novel RNN architecture termed AHMR (Attentive Hierarchical Motion Recurrent network) for motion prediction which simultaneously models local motion contexts and a global context. We further explore a geodesic loss and a forward kinematics loss for the motion prediction task, which have more geometric significance than the widely employed L2 loss. Interestingly, we applied our method to a range of articulate objects including human, fish, and mouse. Empirical results show that our approach outperforms the state-of-the-art methods in short-term prediction and achieves much enhanced long-term prediction proficiency, such as retaining natural human-like motions over 50 seconds predictions. Our codes are released.
YACLC: A Chinese Learner Corpus with Multidimensional Annotation
Venue: arXiv cs.CL 2021
Year: 2021

Learner corpus collects language data produced by L2 learners, that is second or foreign-language learners. This resource is of great relevance for second language acquisition research, foreign-language teaching, and automatic grammatical error correction. However, there is little focus on learner corpus for Chinese as Foreign Language (CFL) learners. Therefore, we propose to construct a large-scale, multidimensional annotated Chinese learner corpus. To construct the corpus, we first obtain a large number of topic-rich texts generated by CFL learners. Then we design an annotation scheme including a sentence acceptability score as well as grammatical error and fluency-based corrections. We build a crowdsourcing platform to perform the annotation effectively (https://yaclc.wenmind.net). We name the corpus YACLC (Yet Another Chinese Learner Corpus) and release it as part of the CUGE benchmark (http://cuge.baai.ac.cn). By analyzing the original sentences and annotations in the corpus, we found that YACLC has a considerable size and very high annotation quality. We hope this corpus can further enhance the studies on Chinese International Education and Chinese automatic grammatical error correction.
Feferman-Vaught Decompositions for Prefix Classes of First Order Logic
Venue: arXiv cs.LO 2021
Year: 2021

The Feferman-Vaught theorem provides a way of evaluating a first order sentence $φ$ on a disjoint union of structures by producing a decomposition of $φ$ into sentences which can be evaluated on the individual structures and the results of these evaluations combined using a propositional formula. This decomposition can in general be non-elementarily larger than $φ$. We show that for first order sentences in prenex normal form with a fixed number of quantifier alternations, such a decomposition, further with the same number of quantifier alternations, can be obtained in time elementary in the size of $φ$. We obtain this result as a consequence of a more general decomposition theorem that we prove for a family of infinitary logics we define. We extend these results by considering binary operations other than disjoint union, in particular sum-like operations such as ordered sum and NLC-sum, that are definable using quantifier-free interpretations.
Comparing different solutions for testing resistive defects in low-power SRAMs
Venue: arXiv cs.AR 2021
Year: 2021

Low-power SRAM architectures are especially sensitive to many types of defects that may occur during manufacturing. Among these, resistive defects can appear. This paper analyzes some types of such defects that may impair the device functionalities in subtle ways, depending on the defect characteristics, and that may not be directly or easily detectable by traditional test methods, such as March algorithms. We analyze different methods to test such defects and discuss them in terms of complexity and test time.
Studying the Interplay between Information Loss and Operation Loss in Representations for Classification
Venue: arXiv cs.LG 2021
Year: 2021

Information-theoretic measures have been widely adopted in the design of features for learning and decision problems. Inspired by this, we look at the relationship between i) a weak form of information loss in the Shannon sense and ii) the operation loss in the minimum probability of error (MPE) sense when considering a family of lossy continuous representations (features) of a continuous observation. We present several results that shed light on this interplay. Our first result offers a lower bound on a weak form of information loss as a function of its respective operation loss when adopting a discrete lossy representation (quantization) instead of the original raw observation. From this, our main result shows that a specific form of vanishing information loss (a weak notion of asymptotic informational sufficiency) implies a vanishing MPE loss (or asymptotic operational sufficiency) when considering a general family of lossy continuous representations. Our theoretical findings support the observation that the selection of feature representations that attempt to capture informational sufficiency is appropriate for learning, but this selection is a rather conservative design principle if the intended goal is achieving MPE in classification. Supporting this last point, and under some structural conditions, we show that it is possible to adopt an alternative notion of informational sufficiency (strictly weaker than pure sufficiency in the mutual information sense) to achieve operational sufficiency in learning.
Machine Learning Application Development: Practitioners' Insights
Venue: arXiv cs.SE 2021
Year: 2021

Nowadays, intelligent systems and services are getting increasingly popular as they provide data-driven solutions to diverse real-world problems, thanks to recent breakthroughs in Artificial Intelligence (AI) and Machine Learning (ML). However, machine learning meets software engineering not only with promising potentials but also with some inherent challenges. Despite some recent research efforts, we still do not have a clear understanding of the challenges of developing ML-based applications and the current industry practices. Moreover, it is unclear where software engineering researchers should focus their efforts to better support ML application developers. In this paper, we report about a survey that aimed to understand the challenges and best practices of ML application development. We synthesize the results obtained from 80 practitioners (with diverse skills, experience, and application domains) into 17 findings; outlining challenges and best practices for ML application development. Practitioners involved in the development of ML-based software systems can leverage the summarized best practices to improve the quality of their system. We hope that the reported challenges will inform the research community about topics that need to be investigated to improve the engineering process and the quality of ML-based applications.
BatchLens: A Visualization Approach for Analyzing Batch Jobs in Cloud Systems
Venue: arXiv cs.HC 2021
Year: 2021

Cloud systems are becoming increasingly powerful and complex. It is highly challenging to identify anomalous execution behaviors and pinpoint problems by examining the overwhelming intermediate results/states in complex application workflows. Domain scientists urgently need a friendly and functional interface to understand the quality of the computing services and the performance of their applications in real time. To meet these needs, we explore data generated by job schedulers and investigate general performance metrics (e.g., utilization of CPU, memory and disk I/O). Specifically, we propose an interactive visual analytics approach, BatchLens, to provide both providers and users of cloud service with an intuitive and effective way to explore the status of system batch jobs and help them conduct root-cause analysis of anomalous behaviors in batch jobs. We demonstrate the effectiveness of BatchLens through a case study on the public Alibaba bench workload trace datasets.