OpenRaiser/Intern-Atlas huggingface dataset:
From Fine- to Coarse-Grained Dynamic Information Flow Control and Back, a Tutorial on Dynamic Information Flow
Venue: arXiv cs.PL 2022
Year: 2022

This tutorial provides a complete and homogeneous account of the latest advances in fine- and coarse-grained dynamic information-flow control (IFC) security. Since the 70s, the programming language and the operating system communities have proposed different IFC approaches. IFC operating systems track information flows in a coarse-grained fashion, at the granularity of a process. In contrast, traditional language-based approaches to IFC are fine-grained: they track information flows at the granularity of program variables. For decades, researchers believed coarse-grained IFC to be strictly less permissive than fine-grained IFC -- coarse-grained IFC systems seem inherently less precise because they track less information -- and so granularity appeared to be a fundamental feature of IFC systems. We show that the granularity of the tracking system does not fundamentally restrict how precise or permissive dynamic IFC systems can be. To this end, we mechanize two mostly standard languages, one with a fine-grained dynamic IFC system and the other with a coarse-grained dynamic IFC system, and prove a semantics-preserving translation from each language to the other. In addition, we derive the standard security property of non-interference of each language from that of the other via our verified translation. These translations stand to have important implications on the usability of IFC approaches. The coarse- to fine-grained direction can be used to remove the label annotation burden that fine-grained systems impose on developers, while the fine- to coarse-grained translation shows that coarse-grained systems -- which are easier to design and implement -- can track information as precisely as fine-grained systems and provides an algorithm for automatically retrofitting legacy applications to run on existing coarse-grained systems.
Evolving the MCTS Upper Confidence Bounds for Trees Using a Semantic-inspired Evolutionary Algorithm in the Game of Carcassonne
Venue: arXiv cs.NE 2022
Year: 2022

Monte Carlo Tree Search (MCTS) is a sampling best-first method to search for optimal decisions. The success of MCTS depends heavily on how the tree is built and the selection process plays a fundamental role in this. One particular selection mechanism that has proved to be reliable is based on the Upper Confidence Bounds for Trees (UCT). The UCT attempts to balance exploration and exploitation by considering the values stored in the statistical tree of the MCTS. However, some tuning of the MCTS UCT is necessary for this to work well. In this work, we use Evolutionary Algorithms (EAs) to evolve mathematical expressions with the goal to substitute the UCT formula and use the evolved expressions in MCTS. More specifically, we evolve expressions by means of our proposed Semantic-inspired Evolutionary Algorithm in MCTS approach (SIEA-MCTS). This is inspired by semantics in Genetic Programming (GP), where the use of fitness cases is seen as a requirement to be adopted in GP. Fitness cases are normally used to determine the fitness of individuals and can be used to compute the semantic similarity (or dissimilarity) of individuals. However, fitness cases are not available in MCTS. We extend this notion by using multiple reward values from MCTS that allow us to determine both the fitness of an individual and its semantics. By doing so, we show how SIEA-MCTS is able to successfully evolve mathematical expressions that yield better or competitive results compared to UCT without the need of tuning these evolved expressions. We compare the performance of the proposed SIEA-MCTS against MCTS algorithms, MCTS Rapid Action Value Estimation algorithms, three variants of the *-minimax family of algorithms, a random controller and two more EA approaches. We consistently show how SIEA-MCTS outperforms most of these intelligent controllers in the challenging game of Carcassonne.
Neural Tangent Kernel: A Survey
Venue: arXiv cs.LG 2022
Year: 2022

A seminal work [Jacot et al., 2018] demonstrated that training a neural network under specific parameterization is equivalent to performing a particular kernel method as width goes to infinity. This equivalence opened a promising direction for applying the results of the rich literature on kernel methods to neural nets which were much harder to tackle. The present survey covers key results on kernel convergence as width goes to infinity, finite-width corrections, applications, and a discussion of the limitations of the corresponding method.
Recognizing DAGs with Page-Number 2 is NP-complete
Venue: arXiv cs.CG 2022
Year: 2022

The page-number of a directed acyclic graph (a DAG, for short) is the minimum $k$ for which the DAG has a topological order and a $k$-coloring of its edges such that no two edges of the same color cross, i.e., have alternating endpoints along the topological order. In 1999, Heath and Pemmaraju conjectured that the recognition of DAGs with page-number $2$ is NP-complete and proved that recognizing DAGs with page-number $6$ is NP-complete [SIAM J. Computing, 1999]. Binucci et al. recently strengthened this result by proving that recognizing DAGs with page-number $k$ is NP-complete, for every $k\geq 3$ [SoCG 2019]. In this paper, we finally resolve Heath and Pemmaraju's conjecture in the affirmative. In particular, our NP-completeness result holds even for $st$-planar graphs and planar posets.
A systematic review of research on the use and impact of technology for learning Chinese
Venue: arXiv cs.HC 2022
Year: 2022

In light of technological development enforced by the pandemic, learning Chinese has become more digitalised. Confucius institutes went online and now follow 2021 to 2025 Action Plans for the Construction of Teaching Resources for International Chinese Education and International Chinese Online Education. New ways of learning Chinese emerged, such as educational games and intelligent tutoring systems ITS, some of them based on artificial intelligence. The aim of this systematic review is to examine recent research published in ScienceDirect and Scopus databases on the use and impact of educational games and ITS in Chinese language learning. A total of 29 selected studies were analysed.
Qubit Mapping and Routing via MaxSAT
Venue: arXiv cs.AR 2022
Year: 2022

Near-term quantum computers will operate in a noisy environment, without error correction. A critical problem for near-term quantum computing is laying out a logical circuit onto a physical device with limited connectivity between qubits. This is known as the qubit mapping and routing (QMR) problem, an intractable combinatorial problem. It is important to solve QMR as optimally as possible to reduce the amount of added noise, which may render a quantum computation useless. In this paper, we present a novel approach for optimally solving the QMR problem via a reduction to maximum satisfiability (MAXSAT). Additionally, we present two novel relaxation ideas that shrink the size of the MAXSAT constraints by exploiting the structure of a quantum circuit. Our thorough empirical evaluation demonstrates (1) the scalability of our approach compared to state-of-the-art optimal QMR techniques (solves more than 3x benchmarks with 40x speedup), (2) the significant cost reduction compared to state-of-the-art heuristic approaches (an average of ~5x swap reduction), and (3) the power of our proposed constraint relaxations.
On Time and Space: An Experimental Study on Graph Structural and Temporal Encodings
Venue: arXiv cs.HC 2022
Year: 2022

Dynamic networks reflect temporal changes occurring to the graph's structure and are used to model a wide variety of problems in many application fields. We investigate the design space of dynamic graph visualization along two major dimensions: the network structural and temporal representation. Significant research has been conducted evaluating the benefits and drawbacks of different structural representations for static graphs, however, few extend this comparison to a dynamic network setting. We conduct a study where we assess the participants' response times, accuracy, and preferences for different combinations of the graph's structural and temporal representations on typical dynamic network exploration tasks, with and without support of common interaction methods. Our results suggest that matrices provide better support for tasks on lower-level entities and basic interactions require longer response times while increasing accuracy. Node-link with auto animation proved to be the quickest and most accurate combination overall, while animation with playback control the most preferred temporal encoding.
StableFace: Analyzing and Improving Motion Stability for Talking Face Generation
Venue: arXiv cs.CV 2022
Year: 2022

While previous speech-driven talking face generation methods have made significant progress in improving the visual quality and lip-sync quality of the synthesized videos, they pay less attention to lip motion jitters which greatly undermine the realness of talking face videos. What causes motion jitters, and how to mitigate the problem? In this paper, we conduct systematic analyses on the motion jittering problem based on a state-of-the-art pipeline that uses 3D face representations to bridge the input audio and output video, and improve the motion stability with a series of effective designs. We find that several issues can lead to jitters in synthesized talking face video: 1) jitters from the input 3D face representations; 2) training-inference mismatch; 3) lack of dependency modeling among video frames. Accordingly, we propose three effective solutions to address this issue: 1) we propose a gaussian-based adaptive smoothing module to smooth the 3D face representations to eliminate jitters in the input; 2) we add augmented erosions on the input data of the neural renderer in training to simulate the distortion in inference to reduce mismatch; 3) we develop an audio-fused transformer generator to model dependency among video frames. Besides, considering there is no off-the-shelf metric for measuring motion jitters in talking face video, we devise an objective metric (Motion Stability Index, MSI), to quantitatively measure the motion jitters by calculating the reciprocal of variance acceleration. Extensive experimental results show the superiority of our method on motion-stable face video generation, with better quality than previous systems.
Improved Grant-Free Access for URLLC via Multi-Tier-Driven Computing: Network-Load Learning, Prediction, and Resource Allocation
Venue: arXiv cs.IT 2022
Year: 2022

Grant-Free (GF) access has been recognized as a promising candidate for Ultra-Reliable and Low-Latency Communications (URLLC). However, even with GF access, URLLC still may not effectively gain high reliability and millimeter-level latency, simultaneously. This is because the network load is typically time-varying and not known to the base station (BS), and thus, the resource allocated for GF access cannot well adapt to variations of the network load, resulting in low resource utilization efficiency under light network load and leading to severe collisions under heavy network load. To tackle this problem, we propose a multi-tier-driven computing framework and the associated algorithms for URLLC to support users with different QoS requirements. Especially, we concentrate on K - repetition GF access in light of its simplicity and well-balanced performance for practical systems. In particular, our framework consists of three tiers of computation, namely network-load learning, network-load prediction, and adaptive resource allocation. In the first tier, the BS can learn the network-load information from the states (success, collision, and idle) of random-access resources in terms of resource blocks (RB) and time slots. In the second tier, the network-load variation is effectively predicted based on estimation results from the first tier. Finally, in the third tier, by deriving and weighing the failure probabilities of different groups of users, their QoS requirements, and the predicted network loads, the BS is able to dynamically allocate sufficient resources accommodating the varying network loads. Simulation results show that our proposed approach can estimate the network load more accurately compared with the baseline schemes. Moreover, our adaptive resource allocation offers an effective way to enhance the QoS for different URLLC services, simultaneously.
Towards Adversarial Purification using Denoising AutoEncoders
Venue: arXiv cs.LG 2022
Year: 2022

With the rapid advancement and increased use of deep learning models in image identification, security becomes a major concern to their deployment in safety-critical systems. Since the accuracy and robustness of deep learning models are primarily attributed from the purity of the training samples, therefore the deep learning architectures are often susceptible to adversarial attacks. Adversarial attacks are often obtained by making subtle perturbations to normal images, which are mostly imperceptible to humans, but can seriously confuse the state-of-the-art machine learning models. We propose a framework, named APuDAE, leveraging Denoising AutoEncoders (DAEs) to purify these samples by using them in an adaptive way and thus improve the classification accuracy of the target classifier networks that have been attacked. We also show how using DAEs adaptively instead of using them directly, improves classification accuracy further and is more robust to the possibility of designing adaptive attacks to fool them. We demonstrate our results over MNIST, CIFAR-10, ImageNet dataset and show how our framework (APuDAE) provides comparable and in most cases better performance to the baseline methods in purifying adversaries. We also design adaptive attack specifically designed to attack our purifying model and demonstrate how our defense is robust to that.
Perfusion assessment via local remote photoplethysmography (rPPG)
Venue: arXiv cs.CV 2022
Year: 2022

This paper presents an approach to assess the perfusion of visible human tissue from RGB video files. We propose metrics derived from remote photoplethysmography (rPPG) signals to detect whether a tissue is adequately supplied with blood. The perfusion analysis is done in three different scales, offering a flexible approach for different applications. We perform a plane-orthogonal-to-skin rPPG independently for locally defined regions of interest on each scale. From the extracted signals, we derive the signal-to-noise ratio, magnitude in the frequency domain, heart rate, perfusion index as well as correlation between specific rPPG signals in order to locally assess the perfusion of a specific region of human tissue. We show that locally resolved rPPG has a broad range of applications. As exemplary applications, we present results in intraoperative perfusion analysis and visualization during skin and organ transplantation as well as an application for liveliness assessment for the detection of presentation attacks to authentication systems.
Visual-Imagery-Based Analogical Construction in Geometric Matrix Reasoning Task
Venue: arXiv cs.AI 2022
Year: 2022

Raven's Progressive Matrices is a family of classical intelligence tests that have been widely used in both research and clinical settings. There have been many exciting efforts in AI communities to computationally model various aspects of problem solving such figural analogical reasoning problems. In this paper, we present a series of computational models for solving Raven's Progressive Matrices using analogies and image transformations. We run our models following three different strategies usually adopted by human testees. These models are tested on the standard version of Raven's Progressive Matrices, in which we can solve 57 out 60 problems in it. Therefore, analogy and image transformation are proved to be effective in solving RPM problems.
Toward a Mathematical Vulnerability Propagation and Defense Model in Smart Grid Networks
Venue: arXiv cs.CR 2022
Year: 2022

For reducing threat propagation within an inter-connected network, it is essential to distribute the defense investment optimally. Most electric power utilities are resource constrained, yet how to account for costs while designing threat reduction techniques is not well understood. Hence, in this work, a vulnerability propagation and a defense model is proposed based on an epidemic model. The new defense mechanism is then validated through sensitivity of the propagation parameters on the optimal investment with two-node and N-node cases. Further, the model efficacy is evaluated with implementation in one of the communication networks of a cyber-physical power system. Topological impact on the optimal nodal investment is also emphasized. Optimal investment of the neighbors with less degree were found to be highly sensitive to fluctuation in vulnerability exploitability probability.
"Prompt-Gamma Neutron Activation Analysis (PGNAA)" Metal Spectral Classification using Deep Learning Method
Venue: arXiv cs.LG 2022
Year: 2022

There is a pressing market demand to minimize the test time of Prompt Gamma Neutron Activation Analysis (PGNAA) spectra measurement machine, so that it could function as an instant material analyzer, e.g. to classify waste samples instantaneously and determine the best recycling method based on the detected compositions of the testing sample. This article introduces a new development of the deep learning classification and contrive to reduce the test time for PGNAA machine. We propose both Random Sampling Methods and Class Activation Map (CAM) to generate "downsized" samples and train the CNN model continuously. Random Sampling Methods (RSM) aims to reduce the measuring time within a sample, and Class Activation Map (CAM) is for filtering out the less important energy range of the downsized samples. We shorten the overall PGNAA measuring time down to 2.5 seconds while ensuring the accuracy is around 96.88 % for our dataset with 12 different species of substances. Compared with classifying different species of materials, it requires more test time (sample count rate) for substances having the same elements to archive good accuracy. For example, the classification of copper alloys requires nearly 24 seconds test time to reach 98 % accuracy.
A Spanish dataset for Targeted Sentiment Analysis of political headlines
Venue: arXiv cs.CL 2022
Year: 2022

Subjective texts have been studied by several works as they can induce certain behaviours in their users. Most work focuses on user-generated texts in social networks, but some other texts also comprise opinions on certain topics and could influence judgement criteria during political decisions. In this work, we address the task of Targeted Sentiment Analysis for the domain of news headlines, published by the main outlets during the 2019 Argentinean Presidential Elections. For this purpose, we present a polarity dataset of 1,976 headlines mentioning candidates in the 2019 elections at the target level. Preliminary experiments with state-of-the-art classification algorithms based on pre-trained linguistic models suggest that target information is helpful for this task. We make our data and pre-trained models publicly available.
The case for fully Bayesian optimisation in small-sample trials
Venue: arXiv cs.LG 2022
Year: 2022

While sample efficiency is the main motive for use of Bayesian optimisation when black-box functions are expensive to evaluate, the standard approach based on type II maximum likelihood (ML-II) may fail and result in disappointing performance in small-sample trials. The paper provides three compelling reasons to adopt fully Bayesian optimisation (FBO) as an alternative. First, failures of ML-II are more commonplace than implied by the existing studies using the contrived settings. Second, FBO is more robust than ML-II, and the price of robustness is almost trivial. Third, FBO has become simple to implement and fast enough to be practical. The paper supports the argument using relevant experiments, which reflect the current practice regarding models, algorithms, and software platforms. Since the benefits seem to outweigh the costs, researchers should consider adopting FBO for their applications so that they can guard against potential failures that end up wasting precious research resources.
Uncertainty-Induced Transferability Representation for Source-Free Unsupervised Domain Adaptation
Venue: arXiv cs.CV 2022
Year: 2022

Source-free unsupervised domain adaptation (SFUDA) aims to learn a target domain model using unlabeled target data and the knowledge of a well-trained source domain model. Most previous SFUDA works focus on inferring semantics of target data based on the source knowledge. Without measuring the transferability of the source knowledge, these methods insufficiently exploit the source knowledge, and fail to identify the reliability of the inferred target semantics. However, existing transferability measurements require either source data or target labels, which are infeasible in SFUDA. To this end, firstly, we propose a novel Uncertainty-induced Transferability Representation (UTR), which leverages uncertainty as the tool to analyse the channel-wise transferability of the source encoder in the absence of the source data and target labels. The domain-level UTR unravels how transferable the encoder channels are to the target domain and the instance-level UTR characterizes the reliability of the inferred target semantics. Secondly, based on the UTR, we propose a novel Calibrated Adaption Framework (CAF) for SFUDA, including i)the source knowledge calibration module that guides the target model to learn the transferable source knowledge and discard the non-transferable one, and ii)the target semantics calibration module that calibrates the unreliable semantics. With the help of the calibrated source knowledge and the target semantics, the model adapts to the target domain safely and ultimately better. We verified the effectiveness of our method using experimental results and demonstrated that the proposed method achieves state-of-the-art performances on the three SFUDA benchmarks. Code is available at https://github.com/SPIresearch/UTR.
Optimal Probabilistic Constellation Shaping for Covert Communications
Venue: arXiv cs.IT 2022
Year: 2022

In this paper, we investigate the optimal probabilistic constellation shaping design for covert communication systems from a practical view. Different from conventional covert communications with equiprobable constellations modulation, we propose nonequiprobable constellations modulation schemes to further enhance the covert rate. Specifically, we derive covert rate expressions for practical discrete constellation inputs for the first time. Then, we study the covert rate maximization problem by jointly optimizing the constellation distribution and power allocation. In particular, an approximate gradient descent method is proposed for obtaining the optimal probabilistic constellation shaping. To strike a balance between the computational complexity and the transmission performance, we further develop a framework that maximizes a lower bound on the achievable rate where the optimal probabilistic constellation shaping problem can be solved efficiently using the Frank-Wolfe method. Extensive numerical results show that the optimized probabilistic constellation shaping strategies provide significant gains in the achievable covert rate over the state-of-the-art schemes.