OpenRaiser/Intern-Atlas huggingface dataset:
Enhanced Fairness Testing via Generating Effective Initial Individual Discriminatory Instances
Venue: arXiv cs.SE 2022
Year: 2022

Fairness testing aims at mitigating unintended discrimination in the decision-making process of data-driven AI systems. Individual discrimination may occur when an AI model makes different decisions for two distinct individuals who are distinguishable solely according to protected attributes, such as age and race. Such instances reveal biased AI behaviour, and are called Individual Discriminatory Instances (IDIs). In this paper, we propose an approach for the selection of the initial seeds to generate IDIs for fairness testing. Previous studies mainly used random initial seeds to this end. However this phase is crucial, as these seeds are the basis of the follow-up IDIs generation. We dubbed our proposed seed selection approach I&D. It generates a large number of initial IDIs exhibiting a great diversity, aiming at improving the overall performance of fairness testing. Our empirical study reveal that I&D is able to produce a larger number of IDIs with respect to four state-of-the-art seed generation approaches, generating 1.68X more IDIs on average. Moreover, we compare the use of I&D to train machine learning models and find that using I&D reduces the number of remaining IDIs by 29% when compared to the state-of-the-art, thus indicating that I&D is effective for improving model fairness
Shape Completion with Points in the Shadow
Venue: arXiv cs.CV 2022
Year: 2022

Single-view point cloud completion aims to recover the full geometry of an object based on only limited observation, which is extremely hard due to the data sparsity and occlusion. The core challenge is to generate plausible geometries to fill the unobserved part of the object based on a partial scan, which is under-constrained and suffers from a huge solution space. Inspired by the classic shadow volume technique in computer graphics, we propose a new method to reduce the solution space effectively. Our method considers the camera a light source that casts rays toward the object. Such light rays build a reasonably constrained but sufficiently expressive basis for completion. The completion process is then formulated as a point displacement optimization problem. Points are initialized at the partial scan and then moved to their goal locations with two types of movements for each point: directional movements along the light rays and constrained local movement for shape refinement. We design neural networks to predict the ideal point movements to get the completion results. We demonstrate that our method is accurate, robust, and generalizable through exhaustive evaluation and comparison. Moreover, it outperforms state-of-the-art methods qualitatively and quantitatively on MVP datasets.
Beware of the Ostrich Policy: End-Users' Perceptions Towards Data Transparency and Control
Venue: arXiv cs.HC 2022
Year: 2022

End users' awareness about the data they share, the purpose of sharing that data, and their control over it, is key to establishing trust and eradicating privacy concerns. We experimented on personal data management by prototyping a Point-of-Interest recommender system in which data collected on the user can be viewed, edited, deleted, and shared via elements in the User Interface. Based on our qualitative findings, in this paper we discuss "The ostrich policy" adopted by end users who do not want to manage their personal data. We sound a waking whistle to design and model for personal data management by understanding end users' perceptions towards data transparency and control.
Unveil the unseen: Exploit information hidden in noise
Venue: arXiv cs.LG 2022
Year: 2022

Noise and uncertainty are usually the enemy of machine learning, noise in training data leads to uncertainty and inaccuracy in the predictions. However, we develop a machine learning architecture that extracts crucial information out of the noise itself to improve the predictions. The phenomenology computes and then utilizes uncertainty in one target variable to predict a second target variable. We apply this formalism to PbZr$_{0.7}$Sn$_{0.3}$O$_{3}$ crystal, using the uncertainty in dielectric constant to extrapolate heat capacity, correctly predicting a phase transition that otherwise cannot be extrapolated. For the second example -- single-particle diffraction of droplets -- we utilize the particle count together with its uncertainty to extrapolate the ground truth diffraction amplitude, delivering better predictions than when we utilize only the particle count. Our generic formalism enables the exploitation of uncertainty in machine learning, which has a broad range of applications in the physical sciences and beyond.
Practical LR Parser Generation
Venue: arXiv cs.FL 2022
Year: 2022

Parsing is a fundamental building block in modern compilers, and for industrial programming languages, it is a surprisingly involved task. There are known approaches to generate parsers automatically, but the prevailing consensus is that automatic parser generation is not practical for real programming languages: LR/LALR parsers are considered to be far too restrictive in the grammars they support, and LR parsers are often considered too inefficient in practice. As a result, virtually all modern languages use recursive-descent parsers written by hand, a lengthy and error-prone process that dramatically increases the barrier to new programming language development. In this work we demonstrate that, contrary to the prevailing consensus, we can have the best of both worlds: for a very general, practical class of grammars -- a strict superset of Knuth's canonical LR -- we can generate parsers automatically, and the resulting parser code, as well as the generation procedure itself, is highly efficient. This advance relies on several new ideas, including novel automata optimization procedures; a new grammar transformation ("CPS"); per-symbol attributes; recursive-descent actions; and an extension of canonical LR parsing, which we refer to as XLR, which endows shift/reduce parsers with the power of bounded nondeterministic choice. With these ingredients, we can automatically generate efficient parsers for virtually all programming languages that are intuitively easy to parse -- a claim we support experimentally, by implementing the new algorithms in a new software tool called langcc, and running them on syntax specifications for Golang 1.17.8 and Python 3.9.12. The tool handles both languages automatically, and the generated code, when run on standard codebases, is 1.2x faster than the corresponding hand-written parser for Golang, and 4.3x faster than the CPython parser, respectively.
Hierarchical Collision Avoidance for Adaptive-Speed Multirotor Teleoperation
Venue: arXiv cs.RO 2022
Year: 2022

This paper improves safe motion primitives-based teleoperation of a multirotor by developing a hierarchical collision avoidance method that modulates maximum speed based on environment complexity and perceptual constraints. Safe speed modulation is challenging in environments that exhibit varying clutter. Existing methods fix maximum speed and map resolution, which prevents vehicles from accessing tight spaces and places the cognitive load for changing speed on the operator. We address these gaps by proposing a high-rate (10 Hz) teleoperation approach that modulates the maximum vehicle speed through hierarchical collision checking. The hierarchical collision checker simultaneously adapts the local map's voxel size and maximum vehicle speed to ensure motion planning safety. The proposed methodology is evaluated in simulation and real-world experiments and compared to a non-adaptive motion primitives-based teleoperation approach. The results demonstrate the advantages of the proposed teleoperation approach both in time taken and the ability to complete the task without requiring the user to specify a maximum vehicle speed.
Grammars over the Lambek Calculus with Permutation: Recognizing Power and Connection to Branching Vector Addition Systems with States
Venue: arXiv cs.FL 2022
Year: 2022

In (Van Benthem, 1991) it is proved that all permutation closures of context-free languages can be generated by grammars over the Lambek calculus with the permutation rule (LP-grammars); however, to our best knowledge, it is not established whether the converse holds or not. In this paper, we show that LP-grammars are equivalent to linearly-restricted branching vector addition systems with states and with additional memory (shortly, lBVASSAM), which are modified branching vector addition systems with states. Then an example of such an lBVASSAM is presented, which generates a non-semilinear set of vectors; this yields that LP-grammars generate more than permutation closures of context-free languages. Moreover, equivalence of LP-grammars and lBVASSAM allows us to present a normal form for LP-grammars and, as a consequence, prove that LP-grammars are equivalent to LP-grammars without product. Finally, we prove that the class of languages generated by LP-grammars is closed under intersection.
Evolution of a Web-Scale Near Duplicate Image Detection System
Venue: arXiv cs.CV 2022
Year: 2022

Detecting near duplicate images is fundamental to the content ecosystem of photo sharing web applications. However, such a task is challenging when involving a web-scale image corpus containing billions of images. In this paper, we present an efficient system for detecting near duplicate images across 8 billion images. Our system consists of three stages: candidate generation, candidate selection, and clustering. We also demonstrate that this system can be used to greatly improve the quality of recommendations and search results across a number of real-world applications. In addition, we include the evolution of the system over the course of six years, bringing out experiences and lessons on how new systems are designed to accommodate organic content growth as well as the latest technology. Finally, we are releasing a human-labeled dataset of ~53,000 pairs of images introduced in this paper.
Evolutionary Deep Reinforcement Learning Using Elite Buffer: A Novel Approach Towards DRL Combined with EA in Continuous Control Tasks
Venue: arXiv cs.NE 2022
Year: 2022

Despite the numerous applications and success of deep reinforcement learning in many control tasks, it still suffers from many crucial problems and limitations, including temporal credit assignment with sparse reward, absence of effective exploration, and a brittle convergence that is extremely sensitive to the hyperparameters of the problem. The problems of deep reinforcement learning in continuous control, along with the success of evolutionary algorithms in facing some of these problems, have emerged the idea of evolutionary reinforcement learning, which attracted many controversies. Despite successful results in a few studies in this field, a proper and fitting solution to these problems and their limitations is yet to be presented. The present study aims to study the efficiency of combining the two fields of deep reinforcement learning and evolutionary computations further and take a step towards improving methods and the existing challenges. The "Evolutionary Deep Reinforcement Learning Using Elite Buffer" algorithm introduced a novel mechanism through inspiration from interactive learning capability and hypothetical outcomes in the human brain. In this method, the utilization of the elite buffer (which is inspired by learning based on experience generalization in the human mind), along with the existence of crossover and mutation operators, and interactive learning in successive generations, have improved efficiency, convergence, and proper advancement in the field of continuous control. According to the results of experiments, the proposed method surpasses other well-known methods in environments with high complexity and dimension and is superior in resolving the mentioned problems and limitations.
Performance Analysis of Reconfigurable Intelligent Surface Assisted Two-Way NOMA Networks
Venue: arXiv cs.IT 2022
Year: 2022

This paper investigates the performance of reconfigurable intelligent surface assisted two-way non-orthogonal multiple access (RIS-TW-NOMA) networks, where a pair of users exchange their information through a RIS. The influence of imperfect successive interference cancellation on RIS-TW-NOMA is taken into account. To evaluate the potential performance of RIS-TW-NOMA, we derive the exact and asymptotic expressions of outage probability and ergodic rate for a pair of users. Based on the analytical results, the diversity orders and high signal-to-noise ratio (SNR) slopes are obtained in the high SNR regime, which are closely related to the number of RIS elements. Additionally, we analyze the system throughput and energy efficiency of RIS-TW-NOMA networks in both delay-limited and delay-tolerant transmission modes. Numerical results indicate that: 1) The outage behaviors and ergodic rate of RIS-TW-NOMA are superior to that of RIS-TW-OMA and two-way relay OMA (TWR-OMA); 2) As the number of RIS elements increases, the RIS-TW-NOMA networks are capable of achieving the enhanced outage performance; and 3) By comparing with RIS-TW-OMA and TWR-OMA networks, the energy efficiency and system throughput of RIS-TW-NOMA has obvious advantages.
Progressive tearing and cutting of soft-bodies in high-performance virtual reality
Venue: arXiv cs.GR 2022
Year: 2022

We present an algorithm that allows a user within a virtual environment to perform real-time unconstrained cuts or consecutive tears, i.e., progressive, continuous fractures on a deformable rigged and soft-body mesh model in high-performance 10ms. In order to recreate realistic results for different physically-principled materials such as sponges, hard or soft tissues, we incorporate a novel soft-body deformation, via a particle system layered on-top of a linear-blend skinning model. Our framework allows the simulation of realistic, surgical-grade cuts and continuous tears, especially valuable in the context of medical VR training. In order to achieve high performance in VR, our algorithms are based on Euclidean geometric predicates on the rigged mesh, without requiring any specific model pre-processing. The contribution of this work lies on the fact that current frameworks supporting similar kinds of model tearing, either do not operate in high-performance real-time or only apply to predefined tears. The framework presented allows the user to freely cut or tear a 3D mesh model in a consecutive way, under 10ms, while preserving its soft-body behaviour and/or allowing further animation.
Multiple Waypoint Navigation in Unknown Indoor Environments
Venue: arXiv cs.RO 2022
Year: 2022

Indoor motion planning focuses on solving the problem of navigating an agent through a cluttered environment. To date, quite a lot of work has been done in this field, but these methods often fail to find the optimal balance between computationally inexpensive online path planning, and optimality of the path. Along with this, these works often prove optimality for single-start single-goal worlds. To address these challenges, we present a multiple waypoint path planner and controller stack for navigation in unknown indoor environments where waypoints include the goal along with the intermediary points that the robot must traverse before reaching the goal. Our approach makes use of a global planner (to find the next best waypoint at any instant), a local planner (to plan the path to a specific waypoint), and an adaptive Model Predictive Control strategy (for robust system control and faster maneuvers). We evaluate our algorithm on a set of randomly generated obstacle maps, intermediate waypoints, and start-goal pairs, with results indicating a significant reduction in computational costs, with high accuracies and robust control.
Online and semi-online scheduling on two hierarchical machines with a common due date to maximize the total early work
Venue: arXiv cs.DS 2022
Year: 2022

In this study, we investigated several online and semi-online scheduling problems on two hierarchical machines with a common due date to maximize the total early work. For the pure online case, we designed an optimal online algorithm with a competitive ratio of $\sqrt 2$. For the case when the total processing time is known, we proposed an optimal semi-online algorithm with a competitive ratio of $\frac{4}{3}$. Additionally, for the cases when the largest processing time is known, we gave optimal algorithms with a competitive ratio of $\frac{6}{5}$ if the largest job is a lower hierarchy one, and of $\sqrt 5-1$ if the largest job is a higher hierarchy one, respectively.
Translationally Invariant Constraint Optimization Problems
Venue: arXiv cs.CC 2022
Year: 2022

We study the complexity of classical constraint satisfaction problems on a 2D grid. Specifically, we consider the complexity of function versions of such problems, with the additional restriction that the constraints are translationally invariant, namely, the variables are located at the vertices of a 2D grid and the constraint between every pair of adjacent variables is the same in each dimension. The only input to the problem is thus the size of the grid. This problem is equivalent to one of the most interesting problems in classical physics, namely, computing the lowest energy of a classical system of particles on the grid. We provide a tight characterization of the complexity of this problem, and show that it is complete for the class $FP^{NEXP}$. Gottesman and Irani (FOCS 2009) also studied classical translationally-invariant constraint satisfaction problems; they show that the problem of deciding whether the cost of the optimal solution is below a given threshold is NEXP-complete. Our result is thus a strengthening of their result from the decision version to the function version of the problem. Our result can also be viewed as a generalization to the translationally invariant setting, of Krentel's famous result from 1988, showing that the function version of SAT is complete for the class $FP^{NP}$. An essential ingredient in the proof is a study of the complexity of a gapped variant of the problem. We show that it is NEXP-hard to approximate the cost of the optimal assignment to within an additive error of $Ω(N^{1/4})$, for an $N \times N$ grid. To the best of our knowledge, no gapped result is known for CSPs on the grid, even in the non-translationally invariant case. As a byproduct of our results, we also show that a decision version of the optimization problem which asks whether the cost of the optimal assignment is odd or even is also complete for $P^{NEXP}$.
Playing Technique Detection by Fusing Note Onset Information in Guzheng Performance
Venue: arXiv cs.SD 2022
Year: 2022

The Guzheng is a kind of traditional Chinese instruments with diverse playing techniques. Instrument playing techniques (IPT) play an important role in musical performance. However, most of the existing works for IPT detection show low efficiency for variable-length audio and provide no assurance in the generalization as they rely on a single sound bank for training and testing. In this study, we propose an end-to-end Guzheng playing technique detection system using Fully Convolutional Networks that can be applied to variable-length audio. Because each Guzheng playing technique is applied to a note, a dedicated onset detector is trained to divide an audio into several notes and its predictions are fused with frame-wise IPT predictions. During fusion, we add the IPT predictions frame by frame inside each note and get the IPT with the highest probability within each note as the final output of that note. We create a new dataset named GZ_IsoTech from multiple sound banks and real-world recordings for Guzheng performance analysis. Our approach achieves 87.97% in frame-level accuracy and 80.76% in note-level F1-score, outperforming existing works by a large margin, which indicates the effectiveness of our proposed method in IPT detection.
Capacity Analysis and Sum Rate Maximization for the SCMA Cellular Network Coexisting with D2D Communications
Venue: arXiv cs.IT 2022
Year: 2022

Sparse code multiple access (SCMA) is the most concerning scheme among non-orthogonal multiple access (NOMA) technologies for 5G wireless communication new interface. Another efficient technique in 5G aimed to improve spectral efficiency for local communications is device-to-device (D2D) communications. Therefore, we utilize the SCMA cellular network coexisting with D2D communications for the connection demand of the Internet of things (IOT), and improve the system sum rate performance of the hybrid network. We first derive the information-theoretic expression of the capacity for all users and find the capacity bound of cellular users based on the mutual interference between cellular users and D2D users. Then we consider the power optimization problem for the cellular users and D2D users jointly to maximize the system sum rate. To tackle the non-convex optimization problem, we propose a geometric programming (GP) based iterative power allocation algorithm. Simulation results demonstrate that the proposed algorithm converges fast and well improves the sum rate performance.
Skew Cyclic Codes Over A Finite Ring : A Note on a result of Mohammadi et al
Venue: arXiv cs.IT 2022
Year: 2022

In this small note we correct an error made by Mohammadi et al. in their paper entitled "On Skew Cyclic Codes Over A Finite Ring" ( Iranian Jl. Math. Sci. Inform. Vol 14 (1) (2019), 135-145).
Rewarding Episodic Visitation Discrepancy for Exploration in Reinforcement Learning
Venue: arXiv cs.LG 2022
Year: 2022

Exploration is critical for deep reinforcement learning in complex environments with high-dimensional observations and sparse rewards. To address this problem, recent approaches proposed to leverage intrinsic rewards to improve exploration, such as novelty-based exploration and prediction-based exploration. However, many intrinsic reward modules require sophisticated structures and representation learning, resulting in prohibitive computational complexity and unstable performance. In this paper, we propose Rewarding Episodic Visitation Discrepancy (REVD), a computation-efficient and quantified exploration method. More specifically, REVD provides intrinsic rewards by evaluating the Rényi divergence-based visitation discrepancy between episodes. To make efficient divergence estimation, a k-nearest neighbor estimator is utilized with a randomly-initialized state encoder. Finally, the REVD is tested on Atari games and PyBullet Robotics Environments. Extensive experiments demonstrate that REVD can significantly improves the sample efficiency of reinforcement learning algorithms and outperforms the benchmarking methods.
Rank Aggregation Using Scoring Rules
Venue: arXiv cs.GT 2022
Year: 2022

To aggregate rankings into a social ranking, one can use scoring systems such as Plurality, Veto, and Borda. We distinguish three types of methods: ranking by score, ranking by repeatedly choosing a winner that we delete and rank at the top, and ranking by repeatedly choosing a loser that we delete and rank at the bottom. The latter method captures the frequently studied voting rules Single Transferable Vote (aka Instant Runoff Voting), Coombs, and Baldwin. In an experimental analysis, we show that the three types of methods produce different rankings in practice. We also provide evidence that sequentially selecting winners is most suitable to detect the "true" ranking of candidates. For different rules in our classes, we then study the (parameterized) computational complexity of deciding in which positions a given candidate can appear in the chosen ranking. As part of our analysis, we also consider the Winner Determination problem for STV, Coombs, and Baldwin and determine their complexity when there are few voters or candidates.