OpenRaiser/Intern-Atlas huggingface dataset:
SLATE: A Sequence Labeling Approach for Task Extraction from Free-form Inked Content
Venue: arXiv cs.CL 2022
Year: 2022

We present SLATE, a sequence labeling approach for extracting tasks from free-form content such as digitally handwritten (or "inked") notes on a virtual whiteboard. Our approach allows us to create a single, low-latency model to simultaneously perform sentence segmentation and classification of these sentences into task/non-task sentences. SLATE greatly outperforms a baseline two-model (sentence segmentation followed by classification model) approach, achieving a task F1 score of 84.4%, a sentence segmentation (boundary similarity) score of 88.4% and three times lower latency compared to the baseline. Furthermore, we provide insights into tackling challenges of performing NLP on the inking domain. We release both our code and dataset for this novel task.
Computing Square Colorings on Bounded-Treewidth and Planar Graphs
Venue: arXiv cs.DS 2022
Year: 2022

A square coloring of a graph $G$ is a coloring of the square $G^2$ of $G$, that is, a coloring of the vertices of $G$ such that any two vertices that are at distance at most $2$ in $G$ receive different colors. We investigate the complexity of finding a square coloring with a given number of $q$ colors. We show that the problem is polynomial-time solvable on graphs of bounded treewidth by presenting an algorithm with running time $n^{2^{\operatorname{tw} + 4}+O(1)}$ for graphs of treewidth at most $\operatorname{tw}$. The somewhat unusual exponent $2^{\operatorname{tw}}$ in the running time is essentially optimal: we show that for any $ε>0$, there is no algorithm with running time $f(\operatorname{tw})n^{(2-ε)^{\operatorname{tw}}}$ unless the Exponential-Time Hypothesis (ETH) fails. We also show that the square coloring problem is NP-hard on planar graphs for any fixed number $q \ge 4$ of colors. Our main algorithmic result is showing that the problem (when the number of colors $q$ is part of the input) can be solved in subexponential time $2^{O(n^{2/3}\log n)}$ on planar graphs. The result follows from the combination of two algorithms. If the number $q$ of colors is small ($\le n^{1/3}$), then we can exploit a treewidth bound on the square of the graph to solve the problem in time $2^{O(\sqrt{qn}\log n)}$. If the number of colors is large ($\ge n^{1/3}$), then an algorithm based on protrusion decompositions and building on our result for the bounded-treewidth case solves the problem in time $2^{O(n\log n/q)}$.
Knowledge Retrieval for Robotic Cooking
Venue: arXiv cs.RO 2022
Year: 2022

Search algorithms are applied where data retrieval with specified specifications is required. The motivation behind developing search algorithms in Functional Object-Oriented Networks is that most of the time, a certain recipe needs to be retrieved or ingredients for a certain recipe needs to be determined. According to the introduction, there is a time when execution of an entire recipe is not available for a robot thus prompting the need to retrieve a certain recipe or ingredients. With a quality FOON, robots can decipher a task goal, find the correct objects at the required states on which to operate and output a sequence of proper manipulation motions. This paper shows several proposed weighted FOON and task planning algorithms that allow a robot and a human to successfully complete complicated tasks together with higher success rates than a human doing them alone.
Faster Walsh-Hadamard Transform and Matrix Multiplication over Finite Fields using Lookup Tables
Venue: arXiv cs.DS 2022
Year: 2022

We use lookup tables to design faster algorithms for important algebraic problems over finite fields. These faster algorithms, which only use arithmetic operations and lookup table operations, may help to explain the difficulty of determining the complexities of these important problems. Our results over a constant-sized finite field are as follows. The Walsh-Hadamard transform of a vector of length $N$ can be computed using $O(N \log N / \log \log N)$ bit operations. This generalizes to any transform defined as a Kronecker power of a fixed matrix. By comparison, the Fast Walsh-Hadamard transform (similar to the Fast Fourier transform) uses $O(N \log N)$ arithmetic operations, which is believed to be optimal up to constant factors. Any algebraic algorithm for multiplying two $N \times N$ matrices using $O(N^ω)$ operations can be converted into an algorithm using $O(N^ω/ (\log N)^{ω/2 - 1})$ bit operations. For example, Strassen's algorithm can be converted into an algorithm using $O(N^{2.81} / (\log N)^{0.4})$ bit operations. It remains an open problem with practical implications to determine the smallest constant $c$ such that Strassen's algorithm can be implemented to use $c \cdot N^{2.81} + o(N^{2.81})$ arithmetic operations; using a lookup table allows one to save a super-constant factor in bit operations.
Distributional Shift Adaptation using Domain-Specific Features
Venue: arXiv cs.LG 2022
Year: 2022

Machine learning algorithms typically assume that the training and test samples come from the same distributions, i.e., in-distribution. However, in open-world scenarios, streaming big data can be Out-Of-Distribution (OOD), rendering these algorithms ineffective. Prior solutions to the OOD challenge seek to identify invariant features across different training domains. The underlying assumption is that these invariant features should also work reasonably well in the unlabeled target domain. By contrast, this work is interested in the domain-specific features that include both invariant features and features unique to the target domain. We propose a simple yet effective approach that relies on correlations in general regardless of whether the features are invariant or not. Our approach uses the most confidently predicted samples identified by an OOD base model (teacher model) to train a new model (student model) that effectively adapts to the target domain. Empirical evaluations on benchmark datasets show that the performance is improved over the SOTA by ~10-20%
Improve Model Testing by Integrating Bounded Model Checking and Coverage Guided Fuzzing
Venue: arXiv cs.SE 2022
Year: 2022

The control logic models built by Simulink or Ptolemy have been widely used in industry scenes. It is an urgent need to ensure the safety and security of the control logic models. Test case generation technologies are widely used to ensure the safety and security. State-of-the-art model testing tools employ model checking techniques or search-based methods to generate test cases. Traditional search based techniques based on Simulink simulation are plagued by problems such as low speed and high overhead. Traditional model checking techniques such as symbolic execution have limited performance when dealing with nonlinear elements and complex loops. Recently, coverage guided fuzzing technologies are known to be effective for test case generation, due to their high efficiency and impressive effects over complex branches of loops. In this paper, we apply fuzzing methods to improve model testing and demonstrate the effectiveness. The fuzzing methods aim to cover more program branches by mutating valuable seeds. Inspired by this feature, we propose a novel integration technology SPsCGF, which leverages bounded model checking for symbolic execution to generate test cases as initial seeds and then conduct fuzzing based upon these worthy seeds. In this manner, our work combines the advantages of the model checking methods and fuzzing techniques in a novel way. Since the control logic models always receive signal inputs, we specifically design novel mutation operators for signals to improve the existing fuzzing method in model testing. Over the evaluated benchmarks which consist of industrial cases, SPsCGF could achieve 8% to 38% higher model coverage and 3x-10x time efficiency compared with the state-of-the-art works.
A Framework for Automated Correctness Checking of Biochemical Protocol Realizations on Digital Microfluidic Biochips
Venue: arXiv cs.ET 2022
Year: 2022

Recent advances in digital microfluidic (DMF) technologies offer a promising platform for a wide variety of biochemical applications, such as DNA analysis, automated drug discovery, and toxicity monitoring. For on-chip implementation of complex bioassays, automated synthesis tools have been developed to meet the design challenges. Currently, the synthesis tools pass through a number of complex design steps to realize a given biochemical protocol on a target DMF architecture. Thus, design errors can arise during the synthesis steps. Before deploying a DMF biochip on a safety critical system, it is necessary to ensure that the desired biochemical protocol has been correctly implemented, i.e., the synthesized output (actuation sequences for the biochip) is free from any design or realization errors. We propose a symbolic constraint-based analysis framework for checking the correctness of a synthesized biochemical protocol with respect to the original design specification. The verification scheme based on this framework can detect several post-synthesis fluidic violations and realization errors in 2D-array based or pin-constrained biochips as well as in cyberphysical systems. It further generates diagnostic feedback for error localization. We present experimental results on the polymerase chain reaction (PCR) and in-vitro multiplexed bioassays to demonstrate the proposed verification approach.
ZK-IMG: Attested Images via Zero-Knowledge Proofs to Fight Disinformation
Venue: arXiv cs.CR 2022
Year: 2022

Over the past few years, AI methods of generating images have been increasing in capabilities, with recent breakthroughs enabling high-resolution, photorealistic "deepfakes" (artificially generated images with the purpose of misinformation or harm). The rise of deepfakes has potential for social disruption. Recent work has proposed using ZK-SNARKs (zero-knowledge succinct non-interactive argument of knowledge) and attested cameras to verify that images were taken by a camera. ZK-SNARKs allow verification of image transformations non-interactively (i.e., post-hoc) with only standard cryptographic hardness assumptions. Unfortunately, this work does not preserve input privacy, is impractically slow (working only on 128$\times$128 images), and/or requires custom cryptographic arguments. To address these issues, we present zk-img, a library for attesting to image transformations while hiding the pre-transformed image. zk-img allows application developers to specify high level image transformations. Then, zk-img will transparently compile these specifications to ZK-SNARKs. To hide the input or output images, zk-img will compute the hash of the images inside the ZK-SNARK. We further propose methods of chaining image transformations securely and privately, which allows for arbitrarily many transformations. By combining these optimizations, zk-img is the first system to be able to transform HD images on commodity hardware, securely and privately.
On the Robustness of Explanations of Deep Neural Network Models: A Survey
Venue: arXiv cs.LG 2022
Year: 2022

Explainability has been widely stated as a cornerstone of the responsible and trustworthy use of machine learning models. With the ubiquitous use of Deep Neural Network (DNN) models expanding to risk-sensitive and safety-critical domains, many methods have been proposed to explain the decisions of these models. Recent years have also seen concerted efforts that have shown how such explanations can be distorted (attacked) by minor input perturbations. While there have been many surveys that review explainability methods themselves, there has been no effort hitherto to assimilate the different methods and metrics proposed to study the robustness of explanations of DNN models. In this work, we present a comprehensive survey of methods that study, understand, attack, and defend explanations of DNN models. We also present a detailed review of different metrics used to evaluate explanation methods, as well as describe attributional attack and defense methods. We conclude with lessons and take-aways for the community towards ensuring robust explanations of DNN model predictions.
Profiling Obese Subgroups in National Health and Nutritional Status Survey Data using Machine Learning Techniques: A Case Study from Brunei Darussalam
Venue: arXiv cs.CV 2022
Year: 2022

National Health and Nutritional Status Survey (NHANSS) is conducted annually by the Ministry of Health in Negara Brunei Darussalam to assess the population health and nutritional patterns and characteristics. The main aim of this study was to discover meaningful patterns (groups) from the obese sample of NHANSS data by applying data reduction and interpretation techniques. The mixed nature of the variables (qualitative and quantitative) in the data set added novelty to the study. Accordingly, the Categorical Principal Component (CATPCA) technique was chosen to interpret the meaningful results. The relationships between obesity and the lifestyle factors like demography, socioeconomic status, physical activity, dietary behavior, history of blood pressure, diabetes, etc., were determined based on the principal components generated by CATPCA. The results were validated with the help of the split method technique to counter verify the authenticity of the generated groups. Based on the analysis and results, two subgroups were found in the data set, and the salient features of these subgroups have been reported. These results can be proposed for the betterment of the healthcare industry.
On the use of learning-based forecasting methods for ameliorating fashion business processes: A position paper
Venue: arXiv cs.CV 2022
Year: 2022

The fashion industry is one of the most active and competitive markets in the world, manufacturing millions of products and reaching large audiences every year. A plethora of business processes are involved in this large-scale industry, but due to the generally short life-cycle of clothing items, supply-chain management and retailing strategies are crucial for good market performance. Correctly understanding the wants and needs of clients, managing logistic issues and marketing the correct products are high-level problems with a lot of uncertainty associated to them given the number of influencing factors, but most importantly due to the unpredictability often associated with the future. It is therefore straightforward that forecasting methods, which generate predictions of the future, are indispensable in order to ameliorate all the various business processes that deal with the true purpose and meaning of fashion: having a lot of people wear a particular product or style, rendering these items, people and consequently brands fashionable. In this paper, we provide an overview of three concrete forecasting tasks that any fashion company can apply in order to improve their industrial and market impact. We underline advances and issues in all three tasks and argue about their importance and the impact they can have at an industrial level. Finally, we highlight issues and directions of future work, reflecting on how learning-based forecasting methods can further aid the fashion industry.
DSCOT: An NFT-Based Blockchain Architecture for the Authentication of IoT-Enabled Smart Devices in Smart Cities
Venue: arXiv cs.CR 2022
Year: 2022

Smart city architecture brings all the underlying architectures, i.e., Internet of Things (IoT), Cyber-Physical Systems (CPSs), Internet of Cyber-Physical Things (IoCPT), and Internet of Everything (IoE), together to work as a system under its umbrella. The goal of smart city architecture is to come up with a solution that may integrate all the real-time response applications. However, the cyber-physical space poses threats that can jeopardize the working of a smart city where all the data belonging to people, systems, and processes will be at risk. Various architectures based on centralized and distributed mechanisms support smart cities; however, the security concerns regarding traceability, scalability, security services, platform assistance, and resource management persist. In this paper, private blockchain-based architecture Decentralized Smart City of Things (DSCoT) is proposed. It actively utilizes fog computing for all the users and smart devices connected to a fog node in a particular management system in a smart city, i.e., a smart house or hospital, etc. Non-fungible tokens (NFTs) have been utilized for representation to define smart device attributes. NFTs in the proposed DSCoT architecture provide devices and user authentication (IoT) functionality. DSCoT has been designed to provide a smart city solution that ensures robust security features such as Confidentiality, Integrity, Availability (CIA), and authorization by defining new attributes and functions for Owner, User, Fog, and IoT devices authentication. The evaluation of the proposed functions and components in terms of Gas consumption and time complexity has shown promising results. Comparatively, the Gas consumption for minting DSCoT NFT showed approximately 27%, and a DSCoT approve() was approximately 11% more efficient than the PUF-based NFT solution.
The hull of two classical propagation rules and their applications
Venue: arXiv cs.IT 2022
Year: 2022

In this work, we study and determine the dimensions of Euclidean and Hermitian hulls of two classical propagation rules, namely, the direct sum construction and the $(\mathbf{u},\mathbf{u+v})$-construction. Some new criteria for the resulting codes derived from these two propagation rules being self-dual, self-orthogonal, or linear complementary dual (LCD) codes are given. As an application, we construct some linear codes with prescribed hull dimensions, many new binary, ternary Euclidean formally self-dual (FSD) LCD codes, and quaternary Hermitian FSD LCD codes. Some new even-like, odd-like, Euclidean and Hermitian self-orthogonal codes are also obtained. Many of {these} codes are also (almost) optimal according to the Database maintained by Markus Grassl. Our methods contribute positively to improve the lower bounds on the minimum distance of known LCD codes.
Composite Fixed-Length Ordered Features for Palmprint Template Protection with Diminished Performance Loss
Venue: arXiv cs.CR 2022
Year: 2022

Palmprint recognition has become more and more popular due to its advantages over other biometric modalities such as fingerprint, in that it is larger in area, richer in information and able to work at a distance. However, the issue of palmprint privacy and security (especially palmprint template protection) remains under-studied. Among the very few research works, most of them only use the directional and orientation features of the palmprint with transformation processing, yielding unsatisfactory protection and identification performance. Thus, this paper proposes a palmprint template protection-oriented operator that has a fixed length and is ordered in nature, by fusing point features and orientation features. Firstly, double orientations are extracted with more accuracy based on MFRAT. Then key points of SURF are extracted and converted to be fixed-length and ordered features. Finally, composite features that fuse up the double orientations and SURF points are transformed using the irreversible transformation of IOM to generate the revocable palmprint template. Experiments show that the EER after irreversible transformation on the PolyU and CASIA databases are 0.17% and 0.19% respectively, and the absolute precision loss is 0.08% and 0.07%, respectively, which proves the advantage of our method.
DoSA : A System to Accelerate Annotations on Business Documents with Human-in-the-Loop
Venue: arXiv cs.CL 2022
Year: 2022

Business documents come in a variety of structures, formats and information needs which makes information extraction a challenging task. Due to these variations, having a document generic model which can work well across all types of documents and for all the use cases seems far-fetched. For document-specific models, we would need customized document-specific labels. We introduce DoSA (Document Specific Automated Annotations), which helps annotators in generating initial annotations automatically using our novel bootstrap approach by leveraging document generic datasets and models. These initial annotations can further be reviewed by a human for correctness. An initial document-specific model can be trained and its inference can be used as feedback for generating more automated annotations. These automated annotations can be reviewed by human-in-the-loop for the correctness and a new improved model can be trained using the current model as pre-trained model before going for the next iteration. In this paper, our scope is limited to Form like documents due to limited availability of generic annotated datasets, but this idea can be extended to a variety of other documents as more datasets are built. An open-source ready-to-use implementation is made available on GitHub https://github.com/neeleshkshukla/DoSA.
Evaluating and Improving Context Attention Distribution on Multi-Turn Response Generation using Self-Contained Distractions
Venue: arXiv cs.CL 2022
Year: 2022

Despite the rapid progress of open-domain generation-based conversational agents, most deployed systems treat dialogue contexts as single-turns, while systems dealing with multi-turn contexts are less studied. There is a lack of a reliable metric for evaluating multi-turn modelling, as well as an effective solution for improving it. In this paper, we focus on an essential component of multi-turn generation-based conversational agents: context attention distribution, i.e. how systems distribute their attention on dialogue's context. For evaluation of this component, We introduce a novel attention-mechanism-based metric: DAS ratio. To improve performance on this component, we propose an optimization strategy that employs self-contained distractions. Our experiments on the Ubuntu chatlogs dataset show that models with comparable perplexity can be distinguished by their ability on context attention distribution. Our proposed optimization strategy improves both non-hierarchical and hierarchical models on the proposed metric by about 10% from baselines.
Sampling an Edge in Sublinear Time Exactly and Optimally
Venue: arXiv cs.DS 2022
Year: 2022

Sampling edges from a graph in sublinear time is a fundamental problem and a powerful subroutine for designing sublinear-time algorithms. Suppose we have access to the vertices of the graph and know a constant-factor approximation to the number of edges. An algorithm for pointwise $\varepsilon$-approximate edge sampling with complexity $O(n/\sqrt{\varepsilon m})$ has been given by Eden and Rosenbaum [SOSA 2018]. This has been later improved by Tětek and Thorup [STOC 2022] to $O(n \log(\varepsilon^{-1})/\sqrt{m})$. At the same time, $Ω(n/\sqrt{m})$ time is necessary. We close the problem, by giving an algorithm with complexity $O(n/\sqrt{m})$ for the task of sampling an edge exactly uniformly.