OpenRaiser/Intern-Atlas huggingface dataset:
HFedMS: Heterogeneous Federated Learning with Memorable Data Semantics in Industrial Metaverse
Venue: arXiv cs.LG 2022
Year: 2022

Federated Learning (FL), as a rapidly evolving privacy-preserving collaborative machine learning paradigm, is a promising approach to enable edge intelligence in the emerging Industrial Metaverse. Even though many successful use cases have proved the feasibility of FL in theory, in the industrial practice of Metaverse, the problems of non-independent and identically distributed (non-i.i.d.) data, learning forgetting caused by streaming industrial data, and scarce communication bandwidth remain key barriers to realize practical FL. Facing the above three challenges simultaneously, this paper presents a high-performance and efficient system named HFEDMS for incorporating practical FL into Industrial Metaverse. HFEDMS reduces data heterogeneity through dynamic grouping and training mode conversion (Dynamic Sequential-to-Parallel Training, STP). Then, it compensates for the forgotten knowledge by fusing compressed historical data semantics and calibrates classifier parameters (Semantic Compression and Compensation, SCC). Finally, the network parameters of the feature extractor and classifier are synchronized in different frequencies (Layer-wiseAlternative Synchronization Protocol, LASP) to reduce communication costs. These techniques make FL more adaptable to the heterogeneous streaming data continuously generated by industrial equipment, and are also more efficient in communication than traditional methods (e.g., Federated Averaging). Extensive experiments have been conducted on the streamed non-i.i.d. FEMNIST dataset using 368 simulated devices. Numerical results show that HFEDMS improves the classification accuracy by at least 6.4% compared with 8 benchmarks and saves both the overall runtime and transfer bytes by up to 98%, proving its superiority in precision and efficiency.
DeepFlow: A Cross-Stack Pathfinding Framework for Distributed AI Systems
Venue: arXiv cs.AR 2022
Year: 2022

Over the past decade, machine learning model complexity has grown at an extraordinary rate, as has the scale of the systems training such large models. However there is an alarmingly low hardware utilization (5-20%) in large scale AI systems. The low system utilization is a cumulative effect of minor losses across different layers of the stack, exacerbated by the disconnect between engineers designing different layers spanning across different industries. We propose CrossFlow, a novel framework that enables cross-layer analysis all the way from the technology layer to the algorithmic layer. We also propose DeepFlow (built on top of CrossFlow using machine learning techniques) to automate the design space exploration and co-optimization across different layers of the stack. We have validated CrossFlow accuracy with distributed training on real commercial hardware and showcase several DeepFlow case studies demonstrating pitfalls of not optimizing across the technology-hardware-software stack for what is likely, the most important workload driving large development investments in all aspects of computing stack.
Parameterized Algorithm for the Disjoint Path Problem on Planar Graphs: Exponential in $k^2$ and Linear in $n$
Venue: arXiv cs.DS 2022
Year: 2022

In this paper, we study the \textsf{Planar Disjoint Paths} problem: Given an undirected planar graph $G$ with $n$ vertices and a set $T$ of $k$ pairs $(s_i,t_i)_{i=1}^k$ of vertices, the goal is to find a set $\mathcal P$ of $k$ pairwise vertex-disjoint paths connecting $s_i$ and $t_i$ for all indices $i\in\{1,\ldots,k\}$. We present a $2^{O(k^2)}n$-time algorithm for the \textsf{Planar Disjoint Paths} problem. This improves the two previously best-known algorithms: $2^{2^{O(k)}}n$-time algorithm [Discrete Applied Mathematics 1995] and $2^{O(k^2)}n^6$-time algorithm [STOC 2020].
Contrastive Learning with Prompt-derived Virtual Semantic Prototypes for Unsupervised Sentence Embedding
Venue: arXiv cs.CL 2022
Year: 2022

Contrastive learning has become a new paradigm for unsupervised sentence embeddings. Previous studies focus on instance-wise contrastive learning, attempting to construct positive pairs with textual data augmentation. In this paper, we propose a novel Contrastive learning method with Prompt-derived Virtual semantic Prototypes (ConPVP). Specifically, with the help of prompts, we construct virtual semantic prototypes to each instance, and derive negative prototypes by using the negative form of the prompts. Using a prototypical contrastive loss, we enforce the anchor sentence embedding to be close to its corresponding semantic prototypes, and far apart from the negative prototypes as well as the prototypes of other sentences. Extensive experimental results on semantic textual similarity, transfer, and clustering tasks demonstrate the effectiveness of our proposed model compared to strong baselines. Code is available at https://github.com/lemon0830/promptCSE.
PeSOTIF: a Challenging Visual Dataset for Perception SOTIF Problems in Long-tail Traffic Scenarios
Venue: arXiv cs.CV 2022
Year: 2022

Perception algorithms in autonomous driving systems confront great challenges in long-tail traffic scenarios, where the problems of Safety of the Intended Functionality (SOTIF) could be triggered by the algorithm performance insufficiencies and dynamic operational environment. However, such scenarios are not systematically included in current open-source datasets, and this paper fills the gap accordingly. Based on the analysis and enumeration of trigger conditions, a high-quality diverse dataset is released, including various long-tail traffic scenarios collected from multiple resources. Considering the development of probabilistic object detection (POD), this dataset marks trigger sources that may cause perception SOTIF problems in the scenarios as key objects. In addition, an evaluation protocol is suggested to verify the effectiveness of POD algorithms in identifying the key objects via uncertainty. The dataset never stops expanding, and the first batch of open-source data includes 1126 frames with an average of 2.27 key objects and 2.47 normal objects in each frame. To demonstrate how to use this dataset for SOTIF research, this paper further quantifies the perception SOTIF entropy to confirm whether a scenario is unknown and unsafe for a perception system. The experimental results show that the quantified entropy can effectively and efficiently reflect the failure of the perception algorithm.
Non-existence of a short algorithm for multiplication of $3\times3$ matrices with group $S_4\times S_3$
Venue: arXiv cs.CC 2022
Year: 2022

One of prospective ways to find new fast algorithms of matrix multiplication is to study algorithms admitting nontrivial symmetries. In the work possible algorithms for multiplication of $3\times3$ matrices, admitting a certain group $G$ isomorphic to $S_4\times S_3$, are investigated. It is shown that there exist no such algorithms of length $\leq23$. In the first part of the work, which is the content of the present article, we describe all orbits of length $\leq23$ of $G$ on the set of decomposable tensors in the space $M\otimes M\otimes M$, where $M=M_3({\mathbb C})$ is the space of complex $3\times3$ matrices. In the second part of the work this description will be used to prove that a short algorithm with the above-mentioned group does not exist.
Symbolic Abstract Heaps for Polymorphic Information-flow Guard Inference (Extended Version)
Venue: arXiv cs.PL 2022
Year: 2022

In the realm of sound object-oriented program analyses for information-flow control, very few approaches adopt flow-sensitive abstractions of the heap that enable a precise modeling of implicit flows. To tackle this challenge, we advance a new symbolic abstraction approach for modeling the heap in Java-like programs. We use a store-less representation that is parameterized with a family of relations among references to offer various levels of precision based on user preferences. This enables us to automatically infer polymorphic information-flow guards for methods via a co-reachability analysis of a symbolic finite-state system. We instantiate the heap abstraction with three different families of relations. We prove the soundness of our approach and compare the precision and scalability obtained with each instantiated heap domain by using the IFSpec benchmarks and real-life applications.
Testing Against Independence with an Eavesdropper
Venue: arXiv cs.IT 2022
Year: 2022

We study a distributed binary hypothesis testing (HT) problem with communication and security constraints, involving three parties: a remote sensor called Alice, a legitimate decision centre called Bob, and an eavesdropper called Eve, all having their own source observations. In this system, Alice conveys a rate R description of her observation to Bob, and Bob performs a binary hypothesis test on the joint distribution underlying his and Alice's observations. The goal of Alice and Bob is to maximise the exponential decay of Bob's miss-detection (type II-error) probability under two constraints: Bob's false alarm-probability (type-I error) probability has to stay below a given threshold and Eve's uncertainty (equivocation) about Alice's observations should stay above a given security threshold even when Eve learns Alice's message. For the special case of testing against independence, we characterise the largest possible type-II error exponent under the described type-I error probability and security constraints.
Information Properties of a Random Variable Decomposition through Lattices
Venue: arXiv cs.IT 2022
Year: 2022

A full-rank lattice in the Euclidean space is a discrete set formed by all integer linear combinations of a basis. Given a probability distribution on $\mathbb{R}^n$, two operations can be induced by considering the quotient of the space by such a lattice: wrapping and quantization. For a lattice $Λ$, and a fundamental domain $D$ which tiles $\mathbb{R}^n$ through $Λ$, the wrapped distribution over the quotient is obtained by summing the density over each coset, while the quantized distribution over the lattice is defined by integrating over each fundamental domain translation. These operations define wrapped and quantized random variables over $D$ and $Λ$, respectively, which sum up to the original random variable. We investigate information-theoretic properties of this decomposition, such as entropy, mutual information and the Fisher information matrix, and show that it naturally generalizes to the more abstract context of locally compact topological groups.
Detecting and Preventing Credential Misuse in OTP-Based Two and Half Factor Authentication Toward Centralized Services Utilizing Blockchain-Based Identity Management
Venue: arXiv cs.CR 2022
Year: 2022

This work focuses on the problem of detection and prevention of stolen and misused secrets (such as private keys) for authentication toward centralized services. We propose a solution for such a problem based on the blockchain-based two-factor authentication scheme SmartOTPs, which we modify for our purposes and utilize in the setting of two and half-factor authentication against a centralized service provider. Our proposed solution consists of four entities that interact together to ensure authentication: (1) the user, (2) the authenticator, (3) the service provider, and (4) the smart contract. Out of two and a half factors of our solution, the first factor stands for the private key, and the second and a half factor stands for one-time passwords (OTPs) and their precursors, where OTPs are obtained from the precursors (a.k.a., pre-images) by cryptographically secure hashing. We describe the protocol for bootstrapping our approach as well as the authentication procedure. We make the security analysis of our solution, where on top of the main attacker model that steals secrets from the client, we analyze man-in-the-middle attacks and malware tampering with the client. In the case of stolen credentials, we show that our solution enables the user to immediately detect the attack occurrence and proceed to re-initialization with fresh credentials.
CAN Bus: The Future of Additive Manufacturing (3D Printing)
Venue: arXiv cs.NI 2022
Year: 2022

Additive Manufacturing (AM) is gaining renewed popularity and attention due to low-cost fabrication systems proliferating the market. Current communication protocols used in AM limit the connection flexibility between the control board and peripherals; they are often complex in their wiring and thus restrict their avenue of expansion. Thus, the Controller Area Network (CAN) bus is an attractive pathway for inter-hardware connections due to its innate quality. However, the combination of CAN and AM is not well explored and documented in existing literature. This article aims to provide examples of CAN bus applications in AM.
Knowledge Retrieval
Venue: arXiv cs.RO 2022
Year: 2022

Robots are man made machines which are used to accomplish the tasks. Robots are mainly used to do complex tasks and work in hazardous environment where humans are difficult to work. They are not only designed to use in hazardous environment but also in the environment where humans are performing the same task repeatedly. These are also used for cooking purpose some tasks can be completed with the interaction of both the human and robot one of such things is cooking where human should help robot in making dishes. This paper mainly focusses on Functional Object Oriented Network which is structured knowledge representation using the input output and motion nodes. Task tress are generated using the task tree FOON is produced and collections of all FOONS forms the universal FOON. Different algorithms to traverse the tree in order to get the best output are also discussed in this paper. The desired node or goal node can be achieved from the start node using the different search algorithms and comparison between them is discussed.
Algorithm for Dynamic Fingerprinting Radio Map Creation Using IMU Measurements
Venue: arXiv cs.NI 2022
Year: 2022

While a vast number of location-based services appeared lately, indoor positioning solutions are developed to provide reliable position information in environments where traditionally used satellite-based positioning systems cannot provide access to accurate position estimates. Indoor positioning systems can be based on many technologies; however, radio networks and more precisely Wi-Fi networks seem to attract the attention of a majority of the research teams. The most widely used localization approach used in Wi-Fi-based systems is based on fingerprinting framework. Fingerprinting algorithms, however, require a radio map for position estimation. This paper will describe a solution for dynamic radio map creation, which is aimed to reduce the time required to build a radio map. The proposed solution is using measurements from IMUs (Inertial Measurement Units), which are processed with a particle filter dead reckoning algorithm. Reference points (RPs) generated by the implemented dead reckoning algorithm are then processed by the proposed reference point merging algorithm, in order to optimize the radio map size and merge similar RPs. The proposed solution was tested in a real-world environment and evaluated by the implementation of deterministic fingerprinting positioning algorithms, and the achieved results were compared with results achieved with a static radio map. The achieved results presented in the paper show that positioning algorithms achieved similar accuracy even with a dynamic map with a low density of reference points.
On Fork-free T-perfect Graphs
Venue: arXiv cs.DM 2022
Year: 2022

In an attempt to understanding the complexity of the independent set problem, Chv{á}tal defined t-perfect graphs. While a full characterization of this class is still at large, progress has been achieved for claw-free graphs [Bruhn and Stein, Math.\ Program.\ 2012] and $P_{5}$-free graphs [Bruhn and Fuchs, SIAM J.\ Discrete Math.\ 2017]. We take one more step to characterize fork-free t-perfect graphs, and show that they are strongly t-perfect and three-colorable. We also present polynomial-time algorithms for recognizing and coloring these graphs.
No Word Embedding Model Is Perfect: Evaluating the Representation Accuracy for Social Bias in the Media
Venue: arXiv cs.CL 2022
Year: 2022

News articles both shape and reflect public opinion across the political spectrum. Analyzing them for social bias can thus provide valuable insights, such as prevailing stereotypes in society and the media, which are often adopted by NLP models trained on respective data. Recent work has relied on word embedding bias measures, such as WEAT. However, several representation issues of embeddings can harm the measures' accuracy, including low-resource settings and token frequency differences. In this work, we study what kind of embedding algorithm serves best to accurately measure types of social bias known to exist in US online news articles. To cover the whole spectrum of political bias in the US, we collect 500k articles and review psychology literature with respect to expected social bias. We then quantify social bias using WEAT along with embedding algorithms that account for the aforementioned issues. We compare how models trained with the algorithms on news articles represent the expected social bias. Our results suggest that the standard way to quantify bias does not align well with knowledge from psychology. While the proposed algorithms reduce the~gap, they still do not fully match the literature.
Optimal Zero-Error Coding for Computing under Pairwise Shared Side Information
Venue: arXiv cs.IT 2022
Year: 2022

We study the zero-error source coding problem in which an encoder with Side Information (SI) $g(Y)$ transmits source symbols $X$ to a decoder. The decoder has SI $Y$ and wants to recover $f(X,Y)$ where $f,g$ are deterministic. We exhibit a condition on the source distribution and $g$ that we call "pairwise shared side information", such that the optimal rate has a single-letter expression. This condition is satisfied if every pair of source symbols "share" at least one SI symbol for all output of $g$. It has a practical interpretation, as $Y$ models a request made by the encoder on an image $X$, and $g(Y)$ corresponds to the type of request. It also has a graph-theoretical interpretation: under "pairwise shared side information" the characteristic graph can be written as a disjoint union of OR products. In the case where the source distribution is full-support, we provide an analytic expression for the optimal rate. We develop an example under "pairwise shared side information", and we show that the optimal coding scheme outperforms several strategies from the literature.
Towards learning to explain with concept bottleneck models: mitigating information leakage
Venue: arXiv cs.LG 2022
Year: 2022

Concept bottleneck models perform classification by first predicting which of a list of human provided concepts are true about a datapoint. Then a downstream model uses these predicted concept labels to predict the target label. The predicted concepts act as a rationale for the target prediction. Model trust issues emerge in this paradigm when soft concept labels are used: it has previously been observed that extra information about the data distribution leaks into the concept predictions. In this work we show how Monte-Carlo Dropout can be used to attain soft concept predictions that do not contain leaked information.
Multi-Task Learning Framework for Extracting Emotion Cause Span and Entailment in Conversations
Venue: arXiv cs.CL 2022
Year: 2022

Predicting emotions expressed in text is a well-studied problem in the NLP community. Recently there has been active research in extracting the cause of an emotion expressed in text. Most of the previous work has done causal emotion entailment in documents. In this work, we propose neural models to extract emotion cause span and entailment in conversations. For learning such models, we use RECCON dataset, which is annotated with cause spans at the utterance level. In particular, we propose MuTEC, an end-to-end Multi-Task learning framework for extracting emotions, emotion cause, and entailment in conversations. This is in contrast to existing baseline models that use ground truth emotions to extract the cause. MuTEC performs better than the baselines for most of the data folds provided in the dataset.
Further Improvements on Approximating the Uniform Cost-Distance Steiner Tree Problem
Venue: arXiv cs.DS 2022
Year: 2022

In this paper, we consider the Uniform Cost-Distance Steiner Tree Problem in metric spaces, a generalization of the well-known Steiner tree problem. Cost-distance Steiner trees minimize the sum of the total length and the weighted path lengths from a dedicated root to the other terminals, which have a weight to penalize the path length. They are applied when the tree is intended for signal transmission, e.g. in chip design or telecommunication networks, and the signal speed through the tree has to be considered besides the total length. Constant factor approximation algorithms for the uniform cost-distance Steiner tree problem have been known since the first mentioning of the problem by Meyerson, Munagala, and Plotkin. Recently, the approximation factor was improved from 2.87 to 2.39 by Khazraei and Held. We refine their approach further and reduce the approximation factor down to 2.15.
SLICT: Multi-input Multi-scale Surfel-Based Lidar-Inertial Continuous-Time Odometry and Mapping
Venue: arXiv cs.RO 2022
Year: 2022

While feature association to a global map has significant benefits, to keep the computations from growing exponentially, most lidar-based odometry and mapping methods opt to associate features with local maps at one voxel scale. Taking advantage of the fact that surfels (surface elements) at different voxel scales can be organized in a tree-like structure, we propose an octree-based global map of multi-scale surfels that can be updated incrementally. This alleviates the need for recalculating, for example, a k-d tree of the whole map repeatedly. The system can also take input from a single or a number of sensors, reinforcing the robustness in degenerate cases. We also propose a point-to-surfel (PTS) association scheme, continuous-time optimization on PTS and IMU preintegration factors, along with loop closure and bundle adjustment, making a complete framework for Lidar-Inertial continuous-time odometry and mapping. Experiments on public and in-house datasets demonstrate the advantages of our system compared to other state-of-the-art methods. To benefit the community, we release the source code and dataset at https://github.com/brytsknguyen/slict.
Towards Extending the Range of Bugs That Automated Program Repair Can Handle
Venue: arXiv cs.SE 2022
Year: 2022

Modern automated program repair (APR) is well-tuned to finding and repairing bugs that introduce observable erroneous behavior to a program. However, a significant class of bugs does not lead to such observable behavior (e.g., liveness/termination bugs, non-functional bugs, and information flow bugs). Such bugs can generally not be handled with current APR approaches, so, as a community, we need to develop complementary techniques. To stimulate the systematic study of alternative APR approaches and hybrid APR combinations, we devise a novel bug classification system that enables methodical analysis of their bug detection power and bug repair capabilities. To demonstrate the benefits, we analyze the repair of termination bugs in sequential and concurrent programs. The study shows that integrating dynamic APR with formal analysis techniques, such as termination provers and software model checkers, reduces complexity and improves the overall reliability of these repairs.