OpenRaiser/Intern-Atlas huggingface dataset:
Dissecting BFT Consensus: In Trusted Components we Trust!
Venue: arXiv cs.DB 2022
Year: 2022

The growing interest in reliable multi-party applications has fostered widespread adoption of Byzantine Fault-Tolerant (BFT) consensus protocols. Existing BFT protocols need f more replicas than Paxos-style protocols to prevent equivocation attacks. Trust-BFT protocols instead seek to minimize this cost by making use of trusted components at replicas. This paper makes two contributions. First, we analyze the design of existing Trust-BFT protocols and uncover three fundamental limitations that preclude most practical deployments. Some of these limitations are fundamental, while others are linked to the state of trusted components today. Second, we introduce a novel suite of consensus protocols, FlexiTrust, that attempts to sidestep these issues. We show that our FlexiTrust protocols achieve up to 185% more throughput than their Trust-BFT counterparts.
Direct Molecular Conformation Generation
Venue: arXiv cs.AI 2022
Year: 2022

Molecular conformation generation aims to generate three-dimensional coordinates of all the atoms in a molecule and is an important task in bioinformatics and pharmacology. Previous methods usually first predict the interatomic distances, the gradients of interatomic distances or the local structures (e.g., torsion angles) of a molecule, and then reconstruct its 3D conformation. How to directly generate the conformation without the above intermediate values is not fully explored. In this work, we propose a method that directly predicts the coordinates of atoms: (1) the loss function is invariant to roto-translation of coordinates and permutation of symmetric atoms; (2) the newly proposed model adaptively aggregates the bond and atom information and iteratively refines the coordinates of the generated conformation. Our method achieves the best results on GEOM-QM9 and GEOM-Drugs datasets. Further analysis shows that our generated conformations have closer properties (e.g., HOMO-LUMO gap) with the groundtruth conformations. In addition, our method improves molecular docking by providing better initial conformations. All the results demonstrate the effectiveness of our method and the great potential of the direct approach. The code is released at https://github.com/DirectMolecularConfGen/DMCG
Technical Report: A Hierarchical Deliberative-Reactive System Architecture for Task and Motion Planning in Partially Known Environments
Venue: arXiv cs.RO 2022
Year: 2022

We describe a task and motion planning architecture for highly dynamic systems that combines a domain-independent sampling-based deliberative planning algorithm with a global reactive planner. We leverage the recent development of a reactive, vector field planner that provides guarantees of reachability to large regions of the environment even in the face of unknown or unforeseen obstacles. The reachability guarantees can be formalized using contracts that allow a deliberative planner to reason purely in terms of those contracts and synthesize a plan by choosing a sequence of reactive behaviors and their target configurations, without evaluating specific motion plans between targets. This reduces both the search depth at which plans will be found, and the number of samples required to ensure a plan exists, while crucially preserving correctness guarantees. The result is reduced computational cost of synthesizing plans, and increased robustness of generated plans to actuator noise, model misspecification, or unknown obstacles. Simulation studies show that our hierarchical planning and execution architecture can solve complex navigation and rearrangement tasks, even when faced with narrow passageways or incomplete world information.
Exploring Sub-skeleton Trajectories for Interpretable Recognition of Sign Language
Venue: arXiv cs.CV 2022
Year: 2022

Recent advances in tracking sensors and pose estimation software enable smart systems to use trajectories of skeleton joint locations for supervised learning. We study the problem of accurately recognizing sign language words, which is key to narrowing the communication gap between hard and non-hard of hearing people. Our method explores a geometric feature space that we call `sub-skeleton' aspects of movement. We assess similarity of feature space trajectories using natural, speed invariant distance measures, which enables clear and insightful nearest neighbor classification. The simplicity and scalability of our basic method allows for immediate application in different data domains with little to no parameter tuning. We demonstrate the effectiveness of our basic method, and a boosted variation, with experiments on data from different application domains and tracking technologies. Surprisingly, our simple methods improve sign recognition over recent, state-of-the-art approaches.
Fair Representation Clustering with Several Protected Classes
Venue: arXiv cs.DS 2022
Year: 2022

We study the problem of fair $k$-median where each cluster is required to have a fair representation of individuals from different groups. In the fair representation $k$-median problem, we are given a set of points $X$ in a metric space. Each point $x\in X$ belongs to one of $\ell$ groups. Further, we are given fair representation parameters $α_j$ and $β_j$ for each group $j\in [\ell]$. We say that a $k$-clustering $C_1, \cdots, C_k$ fairly represents all groups if the number of points from group $j$ in cluster $C_i$ is between $α_j |C_i|$ and $β_j |C_i|$ for every $j\in[\ell]$ and $i\in [k]$. The goal is to find a set $\mathcal{C}$ of $k$ centers and an assignment $ϕ: X\rightarrow \mathcal{C}$ such that the clustering defined by $(\mathcal{C}, ϕ)$ fairly represents all groups and minimizes the $\ell_1$-objective $\sum_{x\in X} d(x, ϕ(x))$. We present an $O(\log k)$-approximation algorithm that runs in time $n^{O(\ell)}$. Note that the known algorithms for the problem either (i) violate the fairness constraints by an additive term or (ii) run in time that is exponential in both $k$ and $\ell$. We also consider an important special case of the problem where $α_j = β_j = \frac{f_j}{f}$ and $f_j, f \in \mathbb{N}$ for all $j\in [\ell]$. For this special case, we present an $O(\log k)$-approximation algorithm that runs in $(kf)^{O(\ell)}\log n + poly(n)$ time.
SDEX: Monte Carlo Simulation of Stochastic Differential Equations on Memristor Crossbars
Venue: arXiv cs.ET 2022
Year: 2022

Here we present stochastic differential equations (SDEs) on a memristor crossbar, where the source of gaussian noise is derived from the random conductance due to ion drift in the devices during programming. We examine the effects of line resistance on the generation of normal random vectors, showing the skew and kurtosis are within acceptable bounds. We then show the implementation of a stochastic differential equation solver for the Black-Scholes SDE, and compare the distribution with the analytic solution. We determine that the random number generation works as intended, and calculate the energy cost of the simulation.
Sensing the Breath: A Multimodal Singing Tutoring Interface with Breath Guidance
Venue: arXiv cs.HC 2022
Year: 2022

Breath is a significant component in singing performance, which is still underresearched in most singing-related music interfaces. In this paper, we present a multimodal system that detects the learner's singing pitch and breathing states and provides real-time visual tutoring feedback. Specifically, the breath detector is a wearable belt with pressure sensors and flexible fabric. It monitors real-time body movement of the abdomen, back waist, and twin ribs. A breath visualization algorithm is developed to display real-time breath states, together with the singing pitch contours on an interactive score interface. User studies show that our system can help users not only gain deeper breath during singing but also improve pitch accuracy in vocal training, especially for those with some musical background.
Deep Learning Algorithm for Threat Detection in Hackers Forum (Deep Web)
Venue: arXiv cs.CR 2022
Year: 2022

In our current society, the inter-connectivity of devices provides easy access for netizens to utilize cyberspace technology for illegal activities. The deep web platform is a consummative ecosystem shielded by boundaries of trust, information sharing, trade-off, and review systems. Domain knowledge is shared among experts in hacker's forums which contain indicators of compromise that can be explored for cyberthreat intelligence. Developing tools that can be deployed for threat detection is integral in securing digital communication in cyberspace. In this paper, we addressed the use of TOR relay nodes for anonymizing communications in deep web forums. We propose a novel approach for detecting cyberthreats using a deep learning algorithm Long Short-Term Memory (LSTM). The developed model outperformed the experimental results of other researchers in this problem domain with an accuracy of 94\% and precision of 90\%. Our model can be easily deployed by organizations in securing digital communications and detection of vulnerability exposure before cyberattack.
Channel State Acquisition in FDD Massive MIMO: Rate-Distortion Bound and Effectiveness of "Analog" Feedback
Venue: arXiv cs.IT 2022
Year: 2022

We consider the problem of estimating channel fading coefficients (modeled as a correlated Gaussian vector) via Downlink (DL) training and Uplink (UL) feedback in wideband FDD massive MIMO systems. Using rate-distortion theory, we derive optimal bounds on the achievable channel state estimation error in terms of the number of training pilots in DL ($β_{tr}$) and feedback dimension in UL ($β_{fb}$), with random, spatially isotropic pilots. It is shown that when the number of training pilots exceeds the channel covariance rank ($r$), the optimal rate-distortion feedback strategy achieves an estimation error decay of $Θ(SNR^{-α})$ in estimating the channel state, where $α= min (β_{fb}/r , 1)$ is the so-called quality scaling exponent. We also discuss an "analog" feedback strategy, showing that it can achieve the optimal quality scaling exponent for a wide range of training and feedback dimensions with no channel covariance knowledge and simple signal processing at the user side. Our findings are supported by numerical simulations comparing various strategies in terms of channel state mean squared error and achievable ergodic sum-rate in DL with zero-forcing precoding.
A Psychoacoustic Quality Criterion for Path-Traced Sound Propagation
Venue: arXiv cs.SD 2022
Year: 2022

In developing virtual acoustic environments, it is important to understand the relationship between the computation cost and the perceptual significance of the resultant numerical error. In this paper, we propose a quality criterion that evaluates the error significance of path-tracing-based sound propagation simulators. We present an analytical formula that estimates the error signal power spectrum. With this spectrum estimation, we can use a modified Zwicker's loudness model to calculate the relative loudness of the error signal masked by the ideal output. Our experimental results show that the proposed criterion can explain the human perception of simulation error in a variety of cases.
A Taxonomy for Contrasting Industrial Control Systems Asset Discovery Tools
Venue: arXiv cs.CR 2022
Year: 2022

Asset scanning and discovery is the first and foremost step for organizations to understand what assets they have and what to protect. There is currently a plethora of free and commercial asset scanning tools specializing in identifying assets in industrial control systems (ICS). However, there is little information available on their comparative capabilities and how their respective features contrast. Nor is it clear to what depth of scanning these tools can reach and whether they are fit-for-purpose in a scaled industrial network architecture. We provide the first systematic feature comparison of free-to-use asset scanning tools on the basis of an ICS scanning taxonomy that we propose. Based on the taxonomy, we investigate scanning depths reached by the tools' features and validate our investigation through experimentation on Siemens, Schneider Electric, and Allen Bradley devices in a testbed environment.
Feasible Wrench Set Computation for Legged Robots
Venue: arXiv cs.RO 2022
Year: 2022

During locomotion, legged robots interact with the ground by sequentially establishing and breaking contact. The interaction wrenches that arise from contact are used to steer the robot Center of Mass (CoM) and reject perturbations that make the system deviate from the desired trajectory and often make them fall. The feasibility of a given control target (desired CoM wrench or acceleration) is conditioned by the contact point distribution, ground friction, and actuation limits. In this work, we develop a method to compute the set of feasible wrenches that a legged robot can exert on its CoM through contact. The presented method can be used with any amount of non-co-planar contacts and takes into account actuation limits and limitations based on an inelastic contact model with Coulomb friction. This is exemplified with a planar biped model standing with the feet at different heights. Exploiting assumptions from the contact model, we explain how to compute the set of wrenches that are feasible on the CoM when the contacts remain in position as well as the ones that are feasible when some of the contacts are broken. Therefore, this method can be used to assess whether a switch in contact configuration is feasible while achieving a given control task. Furthermore, the method can be used to identify the directions in which the system is not actuated (i.e. a wrench cannot be exerted in those directions). We show how having a joint be actuated or passive can change the non-actuated wrench directions of a robot at a given pose using a spatial model of a lower-extremity exoskeleton. Therefore, this method is also a useful tool for the design phase of the system. This work presents a useful tool for the control and design of legged systems that extends on the current state of the art.
Use and abuse of instance parameters in the Lean mathematical library
Venue: arXiv cs.LO 2022
Year: 2022

The Lean mathematical library mathlib features extensive use of the typeclass pattern for organising mathematical structures, based on Lean's mechanism of instance parameters. Related mechanisms for typeclasses are available in other provers including Agda, Coq and Isabelle with varying degrees of adoption. This paper analyses representative examples of design patterns involving instance parameters in the current Lean 3 version of mathlib, focussing on complications arising at scale and how the mathlib community deals with them.
A Survey of Methods for Automated Algorithm Configuration
Venue: arXiv cs.AI 2022
Year: 2022

Algorithm configuration (AC) is concerned with the automated search of the most suitable parameter configuration of a parametrized algorithm. There is currently a wide variety of AC problem variants and methods proposed in the literature. Existing reviews do not take into account all derivatives of the AC problem, nor do they offer a complete classification scheme. To this end, we introduce taxonomies to describe the AC problem and features of configuration methods, respectively. We review existing AC literature within the lens of our taxonomies, outline relevant design choices of configuration approaches, contrast methods and problem variants against each other, and describe the state of AC in industry. Finally, our review provides researchers and practitioners with a look at future research directions in the field of AC.
Selection in the Presence of Implicit Bias: The Advantage of Intersectional Constraints
Venue: arXiv cs.CY 2022
Year: 2022

In selection processes such as hiring, promotion, and college admissions, implicit bias toward socially-salient attributes such as race, gender, or sexual orientation of candidates is known to produce persistent inequality and reduce aggregate utility for the decision maker. Interventions such as the Rooney Rule and its generalizations, which require the decision maker to select at least a specified number of individuals from each affected group, have been proposed to mitigate the adverse effects of implicit bias in selection. Recent works have established that such lower-bound constraints can be very effective in improving aggregate utility in the case when each individual belongs to at most one affected group. However, in several settings, individuals may belong to multiple affected groups and, consequently, face more extreme implicit bias due to this intersectionality. We consider independently drawn utilities and show that, in the intersectional case, the aforementioned non-intersectional constraints can only recover part of the total utility achievable in the absence of implicit bias. On the other hand, we show that if one includes appropriate lower-bound constraints on the intersections, almost all the utility achievable in the absence of implicit bias can be recovered. Thus, intersectional constraints can offer a significant advantage over a reductionist dimension-by-dimension non-intersectional approach to reducing inequality.
Algorithmic Fairness Datasets: the Story so Far
Venue: arXiv cs.CY 2022
Year: 2022

Data-driven algorithms are studied in diverse domains to support critical decisions, directly impacting people's well-being. As a result, a growing community of researchers has been investigating the equity of existing algorithms and proposing novel ones, advancing the understanding of risks and opportunities of automated decision-making for historically disadvantaged populations. Progress in fair Machine Learning hinges on data, which can be appropriately used only if adequately documented. Unfortunately, the algorithmic fairness community suffers from a collective data documentation debt caused by a lack of information on specific resources (opacity) and scatteredness of available information (sparsity). In this work, we target data documentation debt by surveying over two hundred datasets employed in algorithmic fairness research, and producing standardized and searchable documentation for each of them. Moreover we rigorously identify the three most popular fairness datasets, namely Adult, COMPAS and German Credit, for which we compile in-depth documentation. This unifying documentation effort supports multiple contributions. Firstly, we summarize the merits and limitations of Adult, COMPAS and German Credit, adding to and unifying recent scholarship, calling into question their suitability as general-purpose fairness benchmarks. Secondly, we document and summarize hundreds of available alternatives, annotating their domain and supported fairness tasks, along with additional properties of interest for fairness researchers. Finally, we analyze these datasets from the perspective of five important data curation topics: anonymization, consent, inclusivity, sensitive attributes, and transparency. We discuss different approaches and levels of attention to these topics, making them tangible, and distill them into a set of best practices for the curation of novel resources.
Predicting Cyber-Attack using Cyber Situational Awareness: The Case of Independent Power Producers (IPPs)
Venue: arXiv cs.CR 2022
Year: 2022

The increasing critical dependencies on Internetof-Things (IoT) have raised security concerns; its application on the critical infrastructures (CIs) for power generation has come under massive cyber-attack over the years. Prior research efforts to understand cybersecurity from Cyber Situational Awareness (CSA) perspective fail to critically consider the various Cyber Situational Awareness (CSA) security vulnerabilities from a human behavioural perspective in line with the CI. This study evaluates CSA elements to predict cyber-attacks in the power generation sector. Data for this research article was collected from IPPs using the survey method. The analysis method was employed through Partial Least Squares Structural Equation Modeling (PLS-SEM) to assess the proposed model. The results revealed negative effects on people and cyber-attack, but significant in predicting cyber-attacks. The study also indicated that information handling is significant and positively influences cyber-attack. The study also reveals no mediation effect between the association of People and Attack and Information and Attack. It could result from an effective cyber security control implemented by the IPPs. Finally, the study also shows no sign of network infrastructure cyber-attack predictions. The reasons could be because managers of IPPs had adequate access policies and security measures in place.
Hacking the Colony: On the Disruptive Effect of Misleading Pheromone and How to Defend Against It
Venue: arXiv cs.MA 2022
Year: 2022

Ants have evolved to seek and retrieve food by leaving trails of pheromones. This mechanism has inspired several approaches to decentralized multi-robot coordination. However, in this paper, we show that pheromone trails are a fragile mechanism for coordination, and can be sabotaged to starve the colony. We introduce detractors: malicious agents that leave a misleading, but indistinguishable, trail of food pheromone to distract and trap cooperator ants in the nest. We analyze the effectiveness of detractors with respect to parameters such as evaporation rate of misleading pheromone and fraction of detractors in the colony. In addition, we propose a countermeasure to this attack by introducing a new type of pheromone: the cautionary pheromone. Cooperator ants secrete this type of pheromone atop existing food trails as a warning. When the cautionary pheromone intensity exceeds the food pheromone intensity, cooperator ants ignore overlapping food pheromone. We show that, despite its simplicity, this defense mechanism can limit, but not nullify, the effect of detractors. Ultimately, our work shows that pheromone-based coordination, while effective, is also fragile.
Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methods
Venue: arXiv cs.LG 2022
Year: 2022

While SGD, which samples from the data with replacement is widely studied in theory, a variant called Random Reshuffling (RR) is more common in practice. RR iterates through random permutations of the dataset and has been shown to converge faster than SGD. When the order is chosen deterministically, a variant called incremental gradient descent (IG), the existing convergence bounds show improvement over SGD but are worse than RR. However, these bounds do not differentiate between a good and a bad ordering and hold for the worst choice of order. Meanwhile, in some cases, choosing the right order when using IG can lead to convergence faster than RR. In this work, we quantify the effect of order on convergence speed, obtaining convergence bounds based on the chosen sequence of permutations while also recovering previous results for RR. In addition, we show benefits of using structured shuffling when various levels of abstractions (e.g. tasks, classes, augmentations, etc.) exists in the dataset in theory and in practice. Finally, relying on our measure, we develop a greedy algorithm for choosing good orders during training, achieving superior performance (by more than 14 percent in accuracy) over RR.