OpenRaiser/Intern-Atlas huggingface dataset:
Compressing LSTM Networks by Matrix Product Operators
Venue: arXiv cs.NI 2022
Year: 2022

Long Short Term Memory(LSTM) models are the building blocks of many state-of-the-art natural language processing(NLP) and speech enhancement(SE) algorithms. However, there are a large number of parameters in an LSTM model. This usually consumes a large number of resources to train the LSTM model. Also, LSTM models suffer from computational inefficiency in the inference phase. Existing model compression methods (e.g., model pruning) can only discriminate based on the magnitude of model parameters, ignoring the issue of importance distribution based on the model information. Here we introduce the MPO decomposition, which describes the local correlation of quantum states in quantum many-body physics and is used to represent the large model parameter matrix in a neural network, which can compress the neural network by truncating the unimportant information in the weight matrix. In this paper, we propose a matrix product operator(MPO) based neural network architecture to replace the LSTM model. The effective representation of neural networks by MPO can effectively reduce the computational consumption of training LSTM models on the one hand, and speed up the computation in the inference phase of the model on the other hand. We compare the MPO-LSTM model-based compression model with the traditional LSTM model with pruning methods on sequence classification, sequence prediction, and speech enhancement tasks in our experiments. The experimental results show that our proposed neural network architecture based on the MPO approach significantly outperforms the pruning approach.
Timely Monitoring of Dynamic Sources with Observations from Multiple Wireless Sensors
Venue: arXiv cs.IT 2022
Year: 2022

Age of Information (AoI) has recently received much attention due to its relevance in IoT sensing and monitoring applications. In this paper, we consider the problem of minimizing the AoI in a system in which a set of sources are observed by multiple sensors in a many-to-many relationship, and the probability that a sensor observes a source depends on the state of the source. This model represents many practical scenarios, such as the ones in which multiple cameras or microphones are deployed to monitor objects moving in certain areas. We formulate the scheduling problem as a Markov Decision Process, and show how the age-optimal scheduling policy can be obtained. We further consider partially observable variants of the problem, and devise approximate policies for large state spaces. Our evaluations show that the approximate policies work well in the considered scenarios, and that the fact that sensors can observe multiple sources is beneficial, especially when there is high uncertainty of the source states.
PTAS for Sparse General-Valued CSPs
Venue: arXiv cs.DM 2022
Year: 2022

We study polynomial-time approximation schemes (PTASes) for constraint satisfaction problems (CSPs) such as Maximum Independent Set or Minimum Vertex Cover on sparse graph classes. Baker's approach gives a PTAS on planar graphs, excluded-minor classes, and beyond. For Max-CSPs, and even more generally, maximisation finite-valued CSPs (where constraints are arbitrary non-negative functions), Romero, Wrochna, and Živný [SODA'21] showed that the Sherali-Adams LP relaxation gives a simple PTAS for all fractionally-treewidth-fragile classes, which is the most general "sparsity" condition for which a PTAS is known. We extend these results to general-valued CSPs, which include "crisp" (or "strict") constraints that have to be satisfied by every feasible assignment. The only condition on the crisp constraints is that their domain contains an element which is at least as feasible as all the others (but possibly less valuable). For minimisation general-valued CSPs with crisp constraints, we present a PTAS for all Baker graph classes -- a definition by Dvořák [SODA'20] which encompasses all classes where Baker's technique is known to work, except possibly for fractionally-treewidth-fragile classes. While this is standard for problems satisfying a certain monotonicity condition on crisp constraints, we show this can be relaxed to diagonalisability -- a property of relational structures connected to logics, statistical physics, and random CSPs.
On the Complexity of the Bilevel Minimum Spanning Tree Problem
Venue: arXiv cs.DS 2022
Year: 2022

We consider the bilevel minimum spanning tree (BMST) problem where the leader and the follower choose a spanning tree together, according to different objective functions. By showing that this problem is NP-hard in general, we answer an open question stated in by Shi et al. We prove that BMST remains hard even in the special case where the follower only controls a matching. Moreover, by a polynomial reduction from the vertex-disjoint Steiner trees problem, we give some evidence that BMST might even remain hard in case the follower controls only few edges. On the positive side, we present a polynomial-time $(|V|-1)$-approximation algorithm for BMST, where $|V|$ is the number of vertices in the input graph. Moreover, considering the number of edges controlled by the follower as parameter, we show that 2-approximating BMST is fixed-parameter tractable and that, in case of uniform costs on leader's edges, even solving BMST exactly is fixed-parameter tractable. We finally consider bottleneck variants of BMST and settle the complexity landscape of all combinations of sum or bottleneck objective functions for the leader and follower, for the optimistic as well as the pessimistic setting.
Minoration via Mixed Volumes and Cover's Problem for General Channels
Venue: arXiv cs.IT 2022
Year: 2022

We give a complete solution to an open problem of Thomas Cover in 1987 about the capacity of a relay channel in the general discrete memoryless setting without any additional assumptions. The key step in our approach is to lower bound a certain soft-max of a stochastic process by convex geometry methods, which is based on two ideas: First, the soft-max is lower bounded in terms of the supremum of another process, by approximating a convex set with a polytope with bounded number of vertices. Second, using a result of Pajor, the supremum of the process is lower bounded in terms of packing numbers by means of mixed-volume inequalities (Minkowski's first inequality).
FPCC: Fast Point Cloud Clustering based Instance Segmentation for Industrial Bin-picking
Venue: arXiv cs.CV 2022
Year: 2022

Instance segmentation is an important pre-processing task in numerous real-world applications, such as robotics, autonomous vehicles, and human-computer interaction. Compared with the rapid development of deep learning for two-dimensional (2D) image tasks, deep learning-based instance segmentation of 3D point cloud still has a lot of room for development. In particular, distinguishing a large number of occluded objects of the same class is a highly challenging problem, which is seen in a robotic bin-picking. In a usual bin-picking scene, many identical objects are stacked together and the model of the objects is known. Thus, the semantic information can be ignored; instead, the focus in the bin-picking is put on the segmentation of instances. Based on this task requirement, we propose a Fast Point Cloud Clustering (FPCC) for instance segmentation of bin-picking scene. FPCC includes a network named FPCC-Net and a fast clustering algorithm. FPCC-net has two subnets, one for inferring the geometric centers for clustering and the other for describing features of each point. FPCC-Net extracts features of each point and infers geometric center points of each instance simultaneously. After that, the proposed clustering algorithm clusters the remaining points to the closest geometric center in feature embedding space. Experiments show that FPCC also surpasses the existing works in bin-picking scenes and is more computationally efficient. Our code and data are available at https://github.com/xyjbaal/FPCC.
LayoutLMv2: Multi-modal Pre-training for Visually-Rich Document Understanding
Venue: arXiv cs.CL 2022
Year: 2022

Pre-training of text and layout has proved effective in a variety of visually-rich document understanding tasks due to its effective model architecture and the advantage of large-scale unlabeled scanned/digital-born documents. We propose LayoutLMv2 architecture with new pre-training tasks to model the interaction among text, layout, and image in a single multi-modal framework. Specifically, with a two-stream multi-modal Transformer encoder, LayoutLMv2 uses not only the existing masked visual-language modeling task but also the new text-image alignment and text-image matching tasks, which make it better capture the cross-modality interaction in the pre-training stage. Meanwhile, it also integrates a spatial-aware self-attention mechanism into the Transformer architecture so that the model can fully understand the relative positional relationship among different text blocks. Experiment results show that LayoutLMv2 outperforms LayoutLM by a large margin and achieves new state-of-the-art results on a wide variety of downstream visually-rich document understanding tasks, including FUNSD (0.7895 $\to$ 0.8420), CORD (0.9493 $\to$ 0.9601), SROIE (0.9524 $\to$ 0.9781), Kleister-NDA (0.8340 $\to$ 0.8520), RVL-CDIP (0.9443 $\to$ 0.9564), and DocVQA (0.7295 $\to$ 0.8672). We made our model and code publicly available at \url{https://aka.ms/layoutlmv2}.
Is Pessimism Provably Efficient for Offline RL?
Venue: arXiv cs.LG 2022
Year: 2022

We study offline reinforcement learning (RL), which aims to learn an optimal policy based on a dataset collected a priori. Due to the lack of further interactions with the environment, offline RL suffers from the insufficient coverage of the dataset, which eludes most existing theoretical analysis. In this paper, we propose a pessimistic variant of the value iteration algorithm (PEVI), which incorporates an uncertainty quantifier as the penalty function. Such a penalty function simply flips the sign of the bonus function for promoting exploration in online RL, which makes it easily implementable and compatible with general function approximators. Without assuming the sufficient coverage of the dataset, we establish a data-dependent upper bound on the suboptimality of PEVI for general Markov decision processes (MDPs). When specialized to linear MDPs, it matches the information-theoretic lower bound up to multiplicative factors of the dimension and horizon. In other words, pessimism is not only provably efficient but also minimax optimal. In particular, given the dataset, the learned policy serves as the "best effort" among all policies, as no other policies can do better. Our theoretical analysis identifies the critical role of pessimism in eliminating a notion of spurious correlation, which emerges from the "irrelevant" trajectories that are less covered by the dataset and not informative for the optimal policy.
Artificial Intelligence Development Races in Heterogeneous Settings
Venue: arXiv cs.AI 2022
Year: 2022

Regulation of advanced technologies such as Artificial Intelligence (AI) has become increasingly important, given the associated risks and apparent ethical issues. With the great benefits promised from being able to first supply such technologies, safety precautions and societal consequences might be ignored or shortchanged in exchange for speeding up the development, therefore engendering a racing narrative among the developers. Starting from a game-theoretical model describing an idealised technology race in a fully connected world of players, here we investigate how different interaction structures among race participants can alter collective choices and requirements for regulatory actions. Our findings indicate that, when participants portray a strong diversity in terms of connections and peer-influence (e.g., when scale-free networks shape interactions among parties), the conflicts that exist in homogeneous settings are significantly reduced, thereby lessening the need for regulatory actions. Furthermore, our results suggest that technology governance and regulation may profit from the world's patent heterogeneity and inequality among firms and nations, so as to enable the design and implementation of meticulous interventions on a minority of participants, which is capable of influencing an entire population towards an ethical and sustainable use of advanced technologies.
Divergence Regulated Encoder Network for Joint Dimensionality Reduction and Classification
Venue: arXiv cs.LG 2022
Year: 2022

Feature representation is an important aspect of remote-sensing based image classification. While deep convolutional neural networks are able to effectively amalgamate information, large numbers of parameters often make learned features inscrutable and difficult to transfer to alternative models. In order to better represent statistical texture information for remote-sensing image classification, in this paper, we investigate performing joint dimensionality reduction and classification using a novel histogram neural network. Motivated by a popular dimensionality reduction approach, t-Distributed Stochastic Neighbor Embedding (t-SNE), our proposed method incorporates a classification loss computed on samples in a low-dimensional embedding space. We compare the learned sample embeddings against coordinates found by t-SNE in terms of classification accuracy and qualitative assessment. We also explore use of various divergence measures in the t-SNE objective. The proposed method has several advantages such as readily embedding out-of-sample points and reducing feature dimensionality while retaining class discriminability. Our results show that the proposed approach maintains and/or improves classification performance and reveals characteristics of features produced by neural networks that may be helpful for other applications.
De-identifying Australian Hospital Discharge Summaries: An End-to-End Framework using Ensemble of Deep Learning Models
Venue: arXiv cs.CL 2022
Year: 2022

Electronic Medical Records (EMRs) contain clinical narrative text that is of great potential value to medical researchers. However, this information is mixed with Personally Identifiable Information (PII) that presents risks to patient and clinician confidentiality. This paper presents an end-to-end deidentification framework to automatically remove PII from Australian hospital discharge summaries. Our corpus included 600 hospital discharge summaries which were extracted from the EMRs of two principal referral hospitals in Sydney, Australia. Our end-to-end de-identification framework consists of three components: 1) Annotation: labelling of PII in the 600 hospital discharge summaries using five pre-defined categories: person, address, date of birth, individual identification number, phone/fax number; 2) Modelling: training six named entity recognition (NER) deep learning base-models on balanced and imbalanced datasets; and evaluating ensembles that combine all six base-models, the three base-models with the best F1 scores and the three base-models with the best recall scores respectively, using token-level majority voting and stacking methods; and 3) De-identification: removing PII from the hospital discharge summaries. Our results showed that the ensemble model combined using the stacking Support Vector Machine (SVM) method on the three base-models with the best F1 scores achieved excellent results with a F1 score of 99.16% on the test set of our corpus. We also evaluated the robustness of our modelling component on the 2014 i2b2 de-identification dataset. Our ensemble model, which uses the token-level majority voting method on all six basemodels, achieved the highest F1 score of 96.24% at strict entity matching and the highest F1 score of 98.64% at binary token-level matching compared to two state-of-the-art methods.
Visualization Techniques with Data Cubes: Utilizing Concurrency for Complex Data
Venue: arXiv cs.DB 2022
Year: 2022

With web and mobile platforms becoming more prominent devices utilized in data analysis, there are currently few systems which are not without flaw. In order to increase the performance of these systems and decrease errors of data oversimplification, we seek to understand how other programming languages can be used across these platforms which provide data and type safety, as well as utilizing concurrency to perform complex data manipulation tasks.
Classification and Segmentation of Pulmonary Lesions in CT Images Using a Combined VGG-XGBoost Method, and an Integrated Fuzzy Clustering-Level Set Technique
Venue: arXiv cs.CV 2022
Year: 2022

Given that lung cancer is one of the deadliest illnesses, early identification and diagnosis are critical to preserving a patient's life. However, lung illness diagnosis is time-intensive and requires the expertise of a pulmonary disease specialist, subject to a significant rate of inaccuracy. Our objective is to design a system capable of accurately detecting and classifying lung lesions and segmenting them in CT-scan images. The suggested technique extracts features automatically from the CT-scan image and then classifies them using Ensemble Gradient Boosting methods. Finally, if a lesion is detected in the CT-scan image, it is segmented using a hybrid approach based on Fuzzy Clustering and Level Set. To train and test our models we gathered a dataset that included CT images of patients residing in Mashhad, Iran. Finally, the results indicate 96% accuracy within this dataset. This approach may assist clinicians in diagnosing lung abnormalities and avoiding potential errors.
Nonlinear Filter for Simultaneous Localization and Mapping on a Matrix Lie Group using IMU and Feature Measurements
Venue: arXiv cs.RO 2022
Year: 2022

Simultaneous Localization and Mapping (SLAM) is a process of concurrent estimation of the vehicle's pose and feature locations with respect to a frame of reference. This paper proposes a computationally cheap geometric nonlinear SLAM filter algorithm structured to mimic the nonlinear motion dynamics of the true SLAM problem posed on the matrix Lie group of $\mathbb{SLAM}_{n}\left(3\right)$. The nonlinear filter on manifold is proposed in continuous form and it utilizes available measurements obtained from group velocity vectors, feature measurements and an inertial measurement unit (IMU). The unknown bias attached to velocity measurements is successfully handled by the proposed estimator. Simulation results illustrate the robustness of the proposed filter in discrete form demonstrating its utility for the six-degrees-of-freedom (6 DoF) pose estimation as well as feature estimation in three-dimensional (3D) space. In addition, the quaternion representation of the nonlinear filter for SLAM is provided. Keywords: Simultaneous Localization and Mapping, Nonlinear observer algorithm for SLAM, inertial measurement unit, inertial vision system, pose, position, attitude, landmark, estimation, IMU, SE(3), SO(3), unmanned aerial vehicle, rigid-body, noise, nonlinear observer for SLAM, Gaussian filter, Kalman filtering, navigation.
Characterizing Intersectional Group Fairness with Worst-Case Comparisons
Venue: arXiv cs.LG 2022
Year: 2022

Machine Learning or Artificial Intelligence algorithms have gained considerable scrutiny in recent times owing to their propensity towards imitating and amplifying existing prejudices in society. This has led to a niche but growing body of work that identifies and attempts to fix these biases. A first step towards making these algorithms more fair is designing metrics that measure unfairness. Most existing work in this field deals with either a binary view of fairness (protected vs. unprotected groups) or politically defined categories (race or gender). Such categorization misses the important nuance of intersectionality - biases can often be amplified in subgroups that combine membership from different categories, especially if such a subgroup is particularly underrepresented in historical platforms of opportunity. In this paper, we discuss why fairness metrics need to be looked at under the lens of intersectionality, identify existing work in intersectional fairness, suggest a simple worst case comparison method to expand the definitions of existing group fairness metrics to incorporate intersectionality, and finally conclude with the social, legal and political framework to handle intersectional fairness in the modern context.
Perfect domination, Roman domination and perfect Roman domination in lexicographic product graphs
Venue: arXiv cs.DM 2022
Year: 2022

The aim of this paper is to obtain closed formulas for the perfect domination number, the Roman domination number and the perfect Roman domination number of lexicographic product graphs. We show that these formulas can be obtained relatively easily for the case of the first two parameters. The picture is quite different when it concerns the perfect Roman domination number. In this case, we obtain general bounds and then we give sufficient and/or necessary conditions for the bounds to be achieved. We also discuss the case of perfect Roman graphs and we characterize the lexicographic product graphs where the perfect Roman domination number equals the Roman domination number.
Progressive Interpretation Synthesis: Interpreting Task Solving by Quantifying Previously Used and Unused Information
Venue: arXiv cs.AI 2022
Year: 2022

A deep neural network is a good task solver, but it is difficult to make sense of its operation. People have different ideas about how to form the interpretation about its operation. We look at this problem from a new perspective where the interpretation of task solving is synthesized by quantifying how much and what previously unused information is exploited in addition to the information used to solve previous tasks. First, after learning several tasks, the network acquires several information partitions related to each task. We propose that the network, then, learns the minimal information partition that supplements previously learned information partitions to more accurately represent the input. This extra partition is associated with un-conceptualized information that has not been used in previous tasks. We manage to identify what un-conceptualized information is used and quantify the amount. To interpret how the network solves a new task, we quantify as meta-information how much information from each partition is extracted. We implement this framework with the variational information bottleneck technique. We test the framework with the MNIST and the CLEVR dataset. The framework is shown to be able to compose information partitions and synthesize experience-dependent interpretation in the form of meta-information. This system progressively improves the resolution of interpretation upon new experience by converting a part of the un-conceptualized information partition to a task-related partition. It can also provide a visual interpretation by imaging what is the part of previously un-conceptualized information that is needed to solve a new task.