OpenRaiser/Intern-Atlas huggingface dataset:
Coloring Mixed and Directional Interval Graphs
Venue: arXiv cs.DM 2022
Year: 2022

A mixed graph has a set of vertices, a set of undirected egdes, and a set of directed arcs. A proper coloring of a mixed graph $G$ is a function $c$ that assigns to each vertex in $G$ a positive integer such that, for each edge $uv$ in $G$, $c(u) \ne c(v)$ and, for each arc $uv$ in $G$, $c(u) < c(v)$. For a mixed graph $G$, the chromatic number $χ(G)$ is the smallest number of colors in any proper coloring of $G$. A directional interval graph is a mixed graph whose vertices correspond to intervals on the real line. Such a graph has an edge between every two intervals where one is contained in the other and an arc between every two overlapping intervals, directed towards the interval that starts and ends to the right. Coloring such graphs has applications in routing edges in layered orthogonal graph drawing according to the Sugiyama framework; the colors correspond to the tracks for routing the edges. We show how to recognize directional interval graphs, and how to compute their chromatic number efficiently. On the other hand, for mixed interval graphs, i.e., graphs where two intersecting intervals can be connected by an edge or by an arc in either direction arbitrarily, we prove that computing the chromatic number is NP-hard.
GaitFi: Robust Device-Free Human Identification via WiFi and Vision Multimodal Learning
Venue: arXiv cs.CV 2022
Year: 2022

As an important biomarker for human identification, human gait can be collected at a distance by passive sensors without subject cooperation, which plays an essential role in crime prevention, security detection and other human identification applications. At present, most research works are based on cameras and computer vision techniques to perform gait recognition. However, vision-based methods are not reliable when confronting poor illuminations, leading to degrading performances. In this paper, we propose a novel multimodal gait recognition method, namely GaitFi, which leverages WiFi signals and videos for human identification. In GaitFi, Channel State Information (CSI) that reflects the multi-path propagation of WiFi is collected to capture human gaits, while videos are captured by cameras. To learn robust gait information, we propose a Lightweight Residual Convolution Network (LRCN) as the backbone network, and further propose the two-stream GaitFi by integrating WiFi and vision features for the gait retrieval task. The GaitFi is trained by the triplet loss and classification loss on different levels of features. Extensive experiments are conducted in the real world, which demonstrates that the GaitFi outperforms state-of-the-art gait recognition methods based on single WiFi or camera, achieving 94.2% for human identification tasks of 12 subjects.
Ergodic Secrecy Rate of Optimal Source-Destination Pair Selection in Frequency-Selective Fading
Venue: arXiv cs.IT 2022
Year: 2022

Node selection is a simple technique to achieve diversity and thereby enhance the physical layer security in future wireless communication systems which require low complexity. High-speed data transmission often encounters frequency selective fading. In this context, we evaluate the exact closed-form expression for the ergodic secrecy rate (ESR) of the optimal source-destination pair selection scheme with single-carrier cyclic-prefix modulation, where the destination and eavesdropper channels both exhibit independent frequency selective fading with an arbitrary number of multipath components. A simplified analysis in the high-SNR scenario along with an asymptotic analysis is also provided. We also derive and compare the corresponding results for the sub-optimal source-destination pair selection scheme. We show that our analysis produces the corresponding ESR results under narrowband independent Nakagami-$m$ fading channel with any arbitrary integer parameter $m$. The effect of transmitters, destination and eavesdropping paths correlation on the ESR is also demonstrated. Our solution approach is general and can be used to find the ESR of a wider variety of transmitter selection schemes.
Compound Figure Separation of Biomedical Images: Mining Large Datasets for Self-supervised Learning
Venue: arXiv cs.CV 2022
Year: 2022

With the rapid development of self-supervised learning (e.g., contrastive learning), the importance of having large-scale images (even without annotations) for training a more generalizable AI model has been widely recognized in medical image analysis. However, collecting large-scale task-specific unannotated data at scale can be challenging for individual labs. Existing online resources, such as digital books, publications, and search engines, provide a new resource for obtaining large-scale images. However, published images in healthcare (e.g., radiology and pathology) consist of a considerable amount of compound figures with subplots. In order to extract and separate compound figures into usable individual images for downstream learning, we propose a simple compound figure separation (SimCFS) framework without using the traditionally required detection bounding box annotations, with a new loss function and a hard case simulation. Our technical contribution is four-fold: (1) we introduce a simulation-based training framework that minimizes the need for resource extensive bounding box annotations; (2) we propose a new side loss that is optimized for compound figure separation; (3) we propose an intra-class image augmentation method to simulate hard cases; and (4) to the best of our knowledge, this is the first study that evaluates the efficacy of leveraging self-supervised learning with compound image separation. From the results, the proposed SimCFS achieved state-of-the-art performance on the ImageCLEF 2016 Compound Figure Separation Database. The pretrained self-supervised learning model using large-scale mined figures improved the accuracy of downstream image classification tasks with a contrastive learning algorithm. The source code of SimCFS is made publicly available at https://github.com/hrlblab/ImageSeperation.
Fine-Grained Liquid Democracy for Cumulative Ballots
Venue: arXiv cs.GT 2022
Year: 2022

We investigate efficient ways for the incorporation of liquid democracy into election settings in which voters submit cumulative ballots, i.e., when each voter is assigned a virtual coin that she can then distribute as she wishes among the available election options. In particular, we are interested in fine-grained liquid democracy, meaning that voters are able to designate a partial coin to a set of election options and delegate the decision on how to further split this partial coin among those election options to another voter of her choice. The fact that we wish such delegations to be transitive -- combined with our aim at fully respecting such delegations -- means that inconsistencies and cycles can occur, thus we set to find computationally-efficient ways of resolving voter delegations. To this aim we develop a theory based fixed-point theorems and mathematical programming techniques and we show that for various variants of definitions regarding how to resolve such transitive delegations, there is always a feasible resolution; and we identify under which conditions such solutions are efficiently computable.
Foreseeing the Impact of the Proposed AI Act on the Sustainability and Safety of Critical Infrastructures
Venue: arXiv cs.CY 2022
Year: 2022

The AI Act has been recently proposed by the European Commission to regulate the use of AI in the EU, especially on high-risk applications, i.e. systems intended to be used as safety components in the management and operation of road traffic and the supply of water, gas, heating and electricity. On the other hand, IEC 61508, one of the most adopted international standards for safety-critical electronic components, seem to mostly forbid the use of AI in such systems. Given this conflict between IEC 61508 and the proposed AI Act, also stressed by the fact that IEC 61508 is not an harmonised European standard, with the present paper we study and analyse what is going to happen to industry after the entry into force of the AI Act. In particular, we focus on how the proposed AI Act might positively impact on the sustainability of critical infrastructures by allowing the use of AI on an industry where it was previously forbidden. To do so, we provide several examples of AI-based solutions falling under the umbrella of IEC 61508 that might have a positive impact on sustainability in alignment with the current long-term goals of the EU and the Sustainable Development Goals of the United Nations, i.e., affordable and clean energy, sustainable cities and communities.
Annotated Dataset Creation through General Purpose Language Models for non-English Medical NLP
Venue: arXiv cs.CL 2022
Year: 2022

Obtaining text datasets with semantic annotations is an effortful process, yet crucial for supervised training in natural language processsing (NLP). In general, developing and applying new NLP pipelines in domain-specific contexts for tasks often requires custom designed datasets to address NLP tasks in supervised machine learning fashion. When operating in non-English languages for medical data processing, this exposes several minor and major, interconnected problems such as lack of task-matching datasets as well as task-specific pre-trained models. In our work we suggest to leverage pretrained language models for training data acquisition in order to retrieve sufficiently large datasets for training smaller and more efficient models for use-case specific tasks. To demonstrate the effectiveness of your approach, we create a custom dataset which we use to train a medical NER model for German texts, GPTNERMED, yet our method remains language-independent in principle. Our obtained dataset as well as our pre-trained models are publicly available at: https://github.com/frankkramer-lab/GPTNERMED
Model-Based Reinforcement Learning with SINDy
Venue: arXiv cs.LG 2022
Year: 2022

We draw on the latest advancements in the physics community to propose a novel method for discovering the governing non-linear dynamics of physical systems in reinforcement learning (RL). We establish that this method is capable of discovering the underlying dynamics using significantly fewer trajectories (as little as one rollout with $\leq 30$ time steps) than state of the art model learning algorithms. Further, the technique learns a model that is accurate enough to induce near-optimal policies given significantly fewer trajectories than those required by model-free algorithms. It brings the benefits of model-based RL without requiring a model to be developed in advance, for systems that have physics-based dynamics. To establish the validity and applicability of this algorithm, we conduct experiments on four classic control tasks. We found that an optimal policy trained on the discovered dynamics of the underlying system can generalize well. Further, the learned policy performs well when deployed on the actual physical system, thus bridging the model to real system gap. We further compare our method to state-of-the-art model-based and model-free approaches, and show that our method requires fewer trajectories sampled on the true physical system compared other methods. Additionally, we explored approximate dynamics models and found that they also can perform well.
Text Difficulty Study: Do machines behave the same as humans regarding text difficulty?
Venue: arXiv cs.CL 2022
Year: 2022

Given a task, human learns from easy to hard, whereas the model learns randomly. Undeniably, difficulty insensitive learning leads to great success in NLP, but little attention has been paid to the effect of text difficulty in NLP. In this research, we propose the Human Learning Matching Index (HLM Index) to investigate the effect of text difficulty. Experiment results show: (1) LSTM has more human-like learning behavior than BERT. (2) UID-SuperLinear gives the best evaluation of text difficulty among four text difficulty criteria. (3) Among nine tasks, some tasks' performance is related to text difficulty, whereas some are not. (4) Model trained on easy data performs best in easy and medium data, whereas trains on a hard level only perform well on hard data. (5) Training the model from easy to hard leads to fast convergence.
Reversible Data hiding in Encrypted Domain with Public Key Embedding Mechanism
Venue: arXiv cs.CR 2022
Year: 2022

Considering the prospects of public key embedding (PKE) mechanism in active forensics on the integrity or identity of ciphertext for distributed deep learning security, two reversible data hiding in encrypted domain (RDH-ED) algorithms with PKE mechanism are proposed, in which all the elements of the embedding function shall be open to the public, while the extraction function could be performed only by legitimate users. The first algorithm is difference expansion in single bit encrypted domain (DE-SBED), which is optimized from the homomorphic embedding framework based on the bit operations of DE in spatial domain. DE-SBED is suitable for the ciphertext of images encrypted from any single bit encryption and learning with errors (LWE) encryption is selected in this paper. Pixel value ordering is introduced to reduce the distortion of decryption and improve the embedding rates (ER). To apply to more flexible applications, public key recoding on encryption redundancy (PKR-ER) algorithm is proposed. Public embedding key is constructed by recoding on the redundancy from the probabilistic decryption of LWE. It is suitable for any plaintext regardless of the type of medium or the content. By setting different quantization rules for recoding, decryption and extraction functions are separable. No distortion exists in the directly decrypted results of the marked ciphertext and ER could reach over 1.0 bits per bit of plaintext. Correctness and security of the algorithms are proved theoretically by deducing the probability distributions of ciphertext and quantization variable. Experimental results demonstrate the performances in correctness, one-way attribute of security and efficiency of the algorithms.
System Resilience through Health Monitoring and Reconfiguration
Venue: arXiv cs.AI 2022
Year: 2022

We demonstrate an end-to-end framework to improve the resilience of man-made systems to unforeseen events. The framework is based on a physics-based digital twin model and three modules tasked with real-time fault diagnosis, prognostics and reconfiguration. The fault diagnosis module uses model-based diagnosis algorithms to detect and isolate faults and generates interventions in the system to disambiguate uncertain diagnosis solutions. We scale up the fault diagnosis algorithm to the required real-time performance through the use of parallelization and surrogate models of the physics-based digital twin. The prognostics module tracks the fault progressions and trains the online degradation models to compute remaining useful life of system components. In addition, we use the degradation models to assess the impact of the fault progression on the operational requirements. The reconfiguration module uses PDDL-based planning endowed with semantic attachments to adjust the system controls so that the fault impact on the system operation is minimized. We define a resilience metric and use the example of a fuel system model to demonstrate how the metric improves with our framework.
$MC^2$: Rigorous and Efficient Directed Greybox Fuzzing
Venue: arXiv cs.CR 2022
Year: 2022

Directed greybox fuzzing is a popular technique for targeted software testing that seeks to find inputs that reach a set of target sites in a program. Most existing directed greybox fuzzers do not provide any theoretical analysis of their performance or optimality. In this paper, we introduce a complexity-theoretic framework to pose directed greybox fuzzing as a oracle-guided search problem where some feedback about the input space (e.g., how close an input is to the target sites) is received by querying an oracle. Our framework assumes that each oracle query can return arbitrary content with a large but constant amount of information. Therefore, we use the number of oracle queries required by a fuzzing algorithm to find a target-reaching input as the performance metric. Using our framework, we design a randomized directed greybox fuzzing algorithm that makes a logarithmic (wrt. the number of all possible inputs) number of queries in expectation to find a target-reaching input. We further prove that the number of oracle queries required by our algorithm is optimal, i.e., no fuzzing algorithm can improve (i.e., minimize) the query count by more than a constant factor. We implement our approach in MC$^2$ and outperform state-of-the-art directed greybox fuzzers on challenging benchmarks (Magma and Fuzzer Test Suite) by up to two orders of magnitude (i.e., $134\times$) on average. MC$^2$ also found 15 previously undiscovered bugs that other state-of-the-art directed greybox fuzzers failed to find.
Efficient Sparsely Activated Transformers
Venue: arXiv cs.LG 2022
Year: 2022

Transformer-based neural networks have achieved state-of-the-art task performance in a number of machine learning domains including natural language processing and computer vision. To further improve their accuracy, recent work has explored the integration of dynamic behavior into these networks in the form of mixture-of-expert (MoE) layers. In this paper, we explore the introduction of MoE layers to optimize a different metric: inference latency. We introduce a novel system named PLANER that takes an existing Transformer-based network and a user-defined latency target and produces an optimized, sparsely-activated version of the original network that tries to meet the latency target while maintaining baseline accuracy. We evaluate PLANER on two real-world language modeling tasks using the Transformer-XL network and achieve inference latency reductions of over 2x at iso-accuracy.
One-class Recommendation Systems with the Hinge Pairwise Distance Loss and Orthogonal Representations
Venue: arXiv cs.IR 2022
Year: 2022

In one-class recommendation systems, the goal is to learn a model from a small set of interacted users and items and then identify the positively-related user-item pairs among a large number of pairs with unknown interactions. Most previous loss functions rely on dissimilar pairs of users and items, which are selected from the ones with unknown interactions, to obtain better prediction performance. This strategy introduces several challenges such as increasing training time and hurting the performance by picking "similar pairs with the unknown interactions" as dissimilar pairs. In this paper, the goal is to only use the similar set to train the models. We point out three trivial solutions that the models converge to when they are trained only on similar pairs: collapsed, partially collapsed, and shrinking solutions. We propose two terms that can be added to the objective functions in the literature to avoid these solutions. The first one is a hinge pairwise distance loss that avoids the shrinking and collapsed solutions by keeping the average pairwise distance of all the representations greater than a margin. The second one is an orthogonality term that minimizes the correlation between the dimensions of the representations and avoids the partially collapsed solution. We conduct experiments on a variety of tasks on public and real-world datasets. The results show that our approach using only similar pairs outperforms state-of-the-art methods using similar pairs and a large number of dissimilar pairs.
Temporal Flow Mask Attention for Open-Set Long-Tailed Recognition of Wild Animals in Camera-Trap Images
Venue: arXiv cs.CV 2022
Year: 2022

Camera traps, unmanned observation devices, and deep learning-based image recognition systems have greatly reduced human effort in collecting and analyzing wildlife images. However, data collected via above apparatus exhibits 1) long-tailed and 2) open-ended distribution problems. To tackle the open-set long-tailed recognition problem, we propose the Temporal Flow Mask Attention Network that comprises three key building blocks: 1) an optical flow module, 2) an attention residual module, and 3) a meta-embedding classifier. We extract temporal features of sequential frames using the optical flow module and learn informative representation using attention residual blocks. Moreover, we show that applying the meta-embedding technique boosts the performance of the method in open-set long-tailed recognition. We apply this method on a Korean Demilitarized Zone (DMZ) dataset. We conduct extensive experiments, and quantitative and qualitative analyses to prove that our method effectively tackles the open-set long-tailed recognition problem while being robust to unknown classes.
Graph Neural Networks with Motif-aware for Tenuous Subgraph Finding
Venue: arXiv cs.SI 2022
Year: 2022

Tenuous subgraph finding aims to detect a subgraph with few social interactions and weak relationships among nodes. Despite significant efforts have been made on this task, they are mostly carried out in view of graph-structured data. These methods depend on calculating the shortest path and need to enumerate all the paths between nodes, which suffer the combinatorial explosion. Moreover, they all lack the integration of neighborhood information. To this end, we propose a novel model named Graph Neural Network with Motif-aware for tenuous subgraph finding (GNNM), a neighborhood aggregation based GNNs framework which can capture the latent relationship between nodes. Specially, we design a GNN module to project nodes into a low dimensional vector combining the higher-order correlation within nodes based on a motif-aware module. And then design greedy algorithms in vector space to obtain a tenuous subgraph whose size is greater than a specified constraint. Particularly, considering existing evaluation indicators cannot capture the latent friendship between nodes, we introduce a novel Potential Friend(PF) concept to measure the tenuity of a graph from a new perspective. Experimental results on the real-world and synthetic datasets demonstrate that our proposed method GNNM outperforms existing algorithms in efficiency and subgraph quality.
PaRTAA: A Real-time Multiprocessor for Mixed-Criticality Airborne Systems
Venue: arXiv cs.AR 2022
Year: 2022

Mixed-criticality systems, where multiple systems with varying criticality-levels share a single hardware platform, require isolation between tasks with different criticality-levels. Isolation can be achieved with software-based solutions or can be enforced by a hardware level partitioning. An asymmetric multiprocessor architecture offers hardware-based isolation at the cost of underutilized hardware resources, and the inter-core communication mechanism is often a single point of failure in such architectures. In contrast, a partitioned uniprocessor offers efficient resource utilization at the cost of limited scalability. We propose a partitioned real-time asymmetric architecture (PaRTAA) specifically designed for mixed-criticality airborne systems, featuring robust partitioning within processing elements for establishing isolation between tasks with varying criticality. The granularity in the processing element offers efficient resource utilization where inter-dependent tasks share the same processing element for sequential execution while preserving isolation, and independent tasks simultaneously execute on different processing elements as per system requirements.