OpenRaiser/Intern-Atlas huggingface dataset:
A Generalization of the Stratonovich's Value of Information and Application to Privacy-Utility Trade-off
Venue: arXiv cs.IT 2022
Year: 2022

The Stratonovich's value of information (VoI) is quantity that measure how much inferential gain is obtained from a perturbed sample under information leakage constraint. In this paper, we introduce a generalized VoI for a general loss function and general information leakage. Then we derive an upper bound of the generalized VoI. Moreover, for a classical loss function, we provide a achievable condition of the upper bound which is weaker than that of in previous studies. Since VoI can be viewed as a formulation of a privacy-utility trade-off (PUT) problem, we provide an interpretation of the achievable condition in the PUT context.
In Defense of Kalman Filtering for Polyp Tracking from Colonoscopy Videos
Venue: arXiv cs.CV 2022
Year: 2022

Real-time and robust automatic detection of polyps from colonoscopy videos are essential tasks to help improve the performance of doctors during this exam. The current focus of the field is on the development of accurate but inefficient detectors that will not enable a real-time application. We advocate that the field should instead focus on the development of simple and efficient detectors that an be combined with effective trackers to allow the implementation of real-time polyp detectors. In this paper, we propose a Kalman filtering tracker that can work together with powerful, but efficient detectors, enabling the implementation of real-time polyp detectors. In particular, we show that the combination of our Kalman filtering with the detector PP-YOLO shows state-of-the-art (SOTA) detection accuracy and real-time processing. More specifically, our approach has SOTA results on the CVC-ClinicDB dataset, with a recall of 0.740, precision of 0.869, $F_1$ score of 0.799, an average precision (AP) of 0.837, and can run in real time (i.e., 30 frames per second). We also evaluate our method on a subset of the Hyper-Kvasir annotated by our clinical collaborators, resulting in SOTA results, with a recall of 0.956, precision of 0.875, $F_1$ score of 0.914, AP of 0.952, and can run in real time.
Foundations for Entailment Checking in Quantitative Separation Logic (extended version)
Venue: arXiv cs.LO 2022
Year: 2022

Quantitative separation logic (QSL) is an extension of separation logic (SL) for the verification of probabilistic pointer programs. In QSL, formulae evaluate to real numbers instead of truth values, e.g., the probability of memory-safe termination in a given symbolic heap. As with \SL, one of the key problems when reasoning with QSL is \emph{entailment}: does a formula f entail another formula g? We give a generic reduction from entailment checking in QSL to entailment checking in SL. This allows to leverage the large body of SL research for the automated verification of probabilistic pointer programs. We analyze the complexity of our approach and demonstrate its applicability. In particular, we obtain the first decidability results for the verification of such programs by applying our reduction to a quantitative extension of the well-known symbolic-heap fragment of separation logic.
Coded Caching for Two-Dimensional Multi-Access Networks
Venue: arXiv cs.IT 2022
Year: 2022

This paper studies a novel multi-access coded caching (MACC) model in the two-dimensional (2D) topology, which is a generalization of the one-dimensional (1D) MACC model proposed by Hachem et al. The 2D MACC model is formed by a server containing $N$ files, $K_1\times K_2$ cache-nodes with $M$ files located at a grid with $K_1$ rows and $K_2$ columns, and $K_1\times K_2$ cache-less users where each user is connected to $L^2$ nearby cache-nodes. The server is connected to the users through an error-free shared link, while the users can retrieve the cached content of the connected cache-nodes without cost. Our objective is to minimize the worst-case transmission load over all possible users' demands. In this paper, we first propose a grouping scheme for the case where $K_1$ and $K_2$ are divisible by $L$. By partitioning the cache-nodes and users into $L^2$ groups such that no two users in the same group share any cache-node, we use the shared-link coded caching scheme proposed by Maddah-Ali and Niesen for each group. Then for any model parameters satisfying $\min\{K_1,K_2\}>L$, we propose a transformation approach which constructs a 2D MACC scheme from two classes of 1D MACC schemes in vertical and horizontal projections, respectively. As a result, we can construct 2D MACC schemes that achieve maximum local caching gain and improved coded caching gain, compared to the baseline scheme by a direct extension from 1D MACC schemes.
Multi-Access Cache-Aided Multi-User Private Information Retrieval
Venue: arXiv cs.IT 2022
Year: 2022

We consider the problem of multi-access cache-aided multi-user Private Information Retrieval (MuPIR). In this problem, several files are replicated across multiple servers. There are $K$ users and $C$ cache nodes. Each user can access $L$ cache nodes, and every cache node can be accessed by several users. Each user wants to retrieve one file from the servers, but the users do not want the servers to know their demands. Before the users decide their respective demands, servers will fill the cache nodes from the content of the files. Users will then request their desired files from the servers. Servers will perform coded transmissions, and all the users should get their desired files from these transmissions and the content placed in the caches they are accessing. It is required that any individual server should not get any information about the demands of the users. This problem is an extension of the dedicated cache-aided MuPIR problem, which itself generalizes the widely studied single user PIR setup. In this paper, we propose a MuPIR scheme which utilizes a multi-access setup of the coded caching problem. The presented scheme is order optimal when $K=\binom{C}{L}$ users. We also characterize the rate of the scheme for the special case of cyclic wraparound multi-access setup, where $C=K$ and each user access $L$ consecutive cache nodes in cyclic wraparound fashion.
An improved judgement algorithm of point in-out convex polygons
Venue: arXiv cs.CG 2022
Year: 2022

This paper proposed a method to judge whether the point is inside or outside of the simple convex polygon by the intersection of the vertical line. It determined the point to an area enclosed by two straight lines, then convert the problem of determining whether a point is inside or outside of a convex polygon into the problem of determining whether a point is inside or outside of a quadrilateral. After that, use the ray method to judge it. The complexity of this algorithm is O(1) to O(n). As the experimental results show, the algorithm has fewer intersections and greatly improves the efficiency of the judgment.
ASOC: Adaptive Self-aware Object Co-localization
Venue: arXiv cs.CV 2022
Year: 2022

The primary goal of this paper is to localize objects in a group of semantically similar images jointly, also known as the object co-localization problem. Most related existing works are essentially weakly-supervised, relying prominently on the neighboring images' weak-supervision. Although weak supervision is beneficial, it is not entirely reliable, for the results are quite sensitive to the neighboring images considered. In this paper, we combine it with a self-awareness phenomenon to mitigate this issue. By self-awareness here, we refer to the solution derived from the image itself in the form of saliency cue, which can also be unreliable if applied alone. Nevertheless, combining these two paradigms together can lead to a better co-localization ability. Specifically, we introduce a dynamic mediator that adaptively strikes a proper balance between the two static solutions to provide an optimal solution. Therefore, we call this method \textit{ASOC}: Adaptive Self-aware Object Co-localization. We perform exhaustive experiments on several benchmark datasets and validate that weak-supervision supplemented with self-awareness has superior performance outperforming several compared competing methods.
Would You Mind Me if I Pass by You? Socially-Appropriate Behaviour for an Omni-based Social Robot in Narrow Environment
Venue: arXiv cs.RO 2022
Year: 2022

Interacting physically with robots and sharing environment with them leads to situations where humans and robots have to cross each other in narrow corridors. In these cases, the robot has to make space for the human to pass. From observation of human-human crossing behaviours, we isolated two main factors in this avoiding behaviour: body rotation and sliding motion. We implemented a robot controller able to vary these factors and explored how this variation impacted on people's perception. Results from a within-participants study involving 23 participants show that people prefer a robot rotating its body when crossing them. Additionally, a sliding motion is rated as being warmer. These results show the importance of social avoidance when interacting with humans.
Early Detection of Network Attacks Using Deep Learning
Venue: arXiv cs.CR 2022
Year: 2022

The Internet has become a prime subject to security attacks and intrusions by attackers. These attacks can lead to system malfunction, network breakdown, data corruption or theft. A network intrusion detection system (IDS) is a tool used for identifying unauthorized and malicious behavior by observing the network traffic. State-of-the-art intrusion detection systems are designed to detect an attack by inspecting the complete information about the attack. This means that an IDS would only be able to detect an attack after it has been executed on the system under attack and might have caused damage to the system. In this paper, we propose an end-to-end early intrusion detection system to prevent network attacks before they could cause any more damage to the system under attack while preventing unforeseen downtime and interruption. We employ a deep neural network-based classifier for attack identification. The network is trained in a supervised manner to extract relevant features from raw network traffic data instead of relying on a manual feature selection process used in most related approaches. Further, we introduce a new metric, called earliness, to evaluate how early our proposed approach detects attacks. We have empirically evaluated our approach on the CICIDS2017 dataset. The results show that our approach performed well and attained an overall 0.803 balanced accuracy.
Bit-serial Weight Pools: Compression and Arbitrary Precision Execution of Neural Networks on Resource Constrained Processors
Venue: arXiv cs.LG 2022
Year: 2022

Applications of neural networks on edge systems have proliferated in recent years but the ever-increasing model size makes neural networks not able to deploy on resource-constrained microcontrollers efficiently. We propose bit-serial weight pools, an end-to-end framework that includes network compression and acceleration of arbitrary sub-byte precision. The framework can achieve up to 8x compression compared to 8-bit networks by sharing a pool of weights across the entire network. We further propose a bit-serial lookup based software implementation that allows runtime-bitwidth tradeoff and is able to achieve more than 2.8x speedup and 7.5x storage compression compared to 8-bit weight pool networks, with less than 1% accuracy drop.
BFS based distributed algorithm for parallel local directed sub-graph enumeration
Venue: arXiv cs.DC 2022
Year: 2022

Estimating the frequency of sub-graphs is of importance for many tasks, including sub-graph isomorphism, kernel-based anomaly detection, and network structure analysis. While multiple algorithms were proposed for full enumeration or sampling-based estimates, these methods fail in very large graphs. Recent advances in parallelization allow for estimates of total sub-graphs counts in very large graphs. The task of counting the frequency of each sub-graph associated with each vertex also received excellent solutions for undirected graphs. However, there is currently no good solution for very large directed graphs. We here propose VDMC (Vertex specific Distributed Motif Counting) -- a fully distributed algorithm to optimally count all the 3 and 4 vertices connected directed graphs (sub-graph motifs) associated with each vertex of a graph. VDMC counts each motif only once and its efficacy is linear in the number of counted motifs. It is fully parallelized to be efficient in GPU-based computation. VDMC is based on three main elements: 1) Ordering the vertices and only counting motifs containing increasing order vertices, 2) sub-ordering motifs based on the average length of the BFS composing the motif, and 3) removing isomorphisms only once for the entire graph. We here compare VDMC to analytical estimates of the expected number of motifs and show its accuracy. VDMC is available as a highly efficient CPU and GPU code with a novel data structure for efficient graph manipulation. We show the efficacy of VDMC and real-world graphs. VDMC allows for the precise analysis of sub-graph frequency around each vertex in large graphs and opens the way for the extension of methods until now limited to graphs of thousands of edges to graphs with millions of edges and above. GIT: https://github.com/louzounlab/graph-measures
A Machine Learning-based Characterization Framework for Parametric Representation of Nonlinear Sloshing
Venue: arXiv cs.LG 2022
Year: 2022

The growing interest in creating a parametric representation of liquid sloshing inside a container stems from its practical applications in modern engineering systems. The resonant excitation, on the other hand, can cause unstable and nonlinear water waves, resulting in chaotic motions and non-Gaussian signals. This paper presents a novel machine learning-based framework for nonlinear liquid sloshing representation learning. The proposed method is a parametric modeling technique that is based on sequential learning and sparse regularization. The dynamics are categorized into two parts: linear evolution and nonlinear forcing. The former advances the dynamical system in time on an embedded manifold, while the latter causes divergent behaviors in temporal evolution, such as bursting and switching. The proposed framework's merit is demonstrated using an experimental dataset of liquid sloshing in a tank under horizontal excitation with a wide frequency range and various vertical slat screen settings.
Strong Converse Theorem for Source Encryption under Side-Channel Attacks
Venue: arXiv cs.IT 2022
Year: 2022

We are interested in investigating the security of source encryption with a symmetric key under side-channel attacks. In this paper, we propose a general framework of source encryption with a symmetric key under the side-channel attacks, which applies to \emph{any} source encryption with a symmetric key and \emph{any} kind of side-channel attacks targeting the secret key. We also propose a new security criterion for strong secrecy under side-channel attacks, which is a natural extension of mutual information, i.e., \emph{the maximum conditional mutual information between the plaintext and the ciphertext given the adversarial key leakage, where the maximum is taken over all possible plaintext distribution}. Under this new criterion, we successfully formulate the rate region, which serves as both necessary and sufficient conditions to have secure transmission even under side-channel attacks. Furthermore, we also prove another theoretical result on our new security criterion, which might be interesting in its own right: in the case of the discrete memoryless source, no perfect secrecy under side-channel attacks in the standard security criterion, i.e., the ordinary mutual information, is achievable without achieving perfect secrecy in this new security criterion, although our new security criterion is more strict than the standard security criterion.
DropNAS: Grouped Operation Dropout for Differentiable Architecture Search
Venue: arXiv cs.LG 2022
Year: 2022

Neural architecture search (NAS) has shown encouraging results in automating the architecture design. Recently, DARTS relaxes the search process with a differentiable formulation that leverages weight-sharing and SGD where all candidate operations are trained simultaneously. Our empirical results show that such procedure results in the co-adaption problem and Matthew Effect: operations with fewer parameters would be trained maturely earlier. This causes two problems: firstly, the operations with more parameters may never have the chance to express the desired function since those with less have already done the job; secondly, the system will punish those underperforming operations by lowering their architecture parameter, and they will get smaller loss gradients, which causes the Matthew Effect. In this paper, we systematically study these problems and propose a novel grouped operation dropout algorithm named DropNAS to fix the problems with DARTS. Extensive experiments demonstrate that DropNAS solves the above issues and achieves promising performance. Specifically, DropNAS achieves 2.26% test error on CIFAR-10, 16.39% on CIFAR-100 and 23.4% on ImageNet (with the same training hyperparameters as DARTS for a fair comparison). It is also observed that DropNAS is robust across variants of the DARTS search space. Code is available at https://github.com/wiljohnhong/DropNAS.
SSLGuard: A Watermarking Scheme for Self-supervised Learning Pre-trained Encoders
Venue: arXiv cs.CR 2022
Year: 2022

Self-supervised learning is an emerging machine learning paradigm. Compared to supervised learning which leverages high-quality labeled datasets, self-supervised learning relies on unlabeled datasets to pre-train powerful encoders which can then be treated as feature extractors for various downstream tasks. The huge amount of data and computational resources consumption makes the encoders themselves become the valuable intellectual property of the model owner. Recent research has shown that the machine learning model's copyright is threatened by model stealing attacks, which aim to train a surrogate model to mimic the behavior of a given model. We empirically show that pre-trained encoders are highly vulnerable to model stealing attacks. However, most of the current efforts of copyright protection algorithms such as watermarking concentrate on classifiers. Meanwhile, the intrinsic challenges of pre-trained encoder's copyright protection remain largely unstudied. We fill the gap by proposing SSLGuard, the first watermarking scheme for pre-trained encoders. Given a clean pre-trained encoder, SSLGuard injects a watermark into it and outputs a watermarked version. The shadow training technique is also applied to preserve the watermark under potential model stealing attacks. Our extensive evaluation shows that SSLGuard is effective in watermark injection and verification, and it is robust against model stealing and other watermark removal attacks such as input noising, output perturbing, overwriting, model pruning, and fine-tuning.
Variable-Length Stop-Feedback Codes With Finite Optimal Decoding Times for BI-AWGN Channels
Venue: arXiv cs.IT 2022
Year: 2022

In this paper, we are interested in the performance of a variable-length stop-feedback (VLSF) code with $m$ optimal decoding times for the binary-input additive white Gaussian noise channel. We first develop tight approximations on the tail probability of length-$n$ cumulative information density. Building on the work of Yavas \emph{et al.}, for a given information density threshold, we formulate the integer program of minimizing the upper bound on average blocklength over all decoding times subject to the average error probability, minimum gap and integer constraints. Eventually, minimization of locally minimum upper bounds over all thresholds will yield the globally minimum upper bound and this is called the two-step minimization. For the integer program, we present a greedy algorithm that yields possibly suboptimal integer decoding times. By allowing a positive real-valued decoding time, we develop the gap-constrained sequential differential optimization (SDO) procedure that sequentially produces the optimal, real-valued decoding times. We identify the error regime in which Polyanskiy's scheme of stopping at zero does not improve the achievability bound. In this error regime, the two-step minimization with the gap-constrained SDO shows that a finite $m$ suffices to attain Polyanskiy's bound for VLSF codes with $m = \infty$.
Search Trajectories Networks of Multiobjective Evolutionary Algorithms
Venue: arXiv cs.NE 2022
Year: 2022

Understanding the search dynamics of multiobjective evolutionary algorithms (MOEAs) is still an open problem. This paper extends a recent network-based tool, search trajectory networks (STNs), to model the behavior of MOEAs. Our approach uses the idea of decomposition, where a multiobjective problem is transformed into several single-objective problems. We show that STNs can be used to model and distinguish the search behavior of two popular multiobjective algorithms, MOEA/D and NSGA-II, using 10 continuous benchmark problems with 2 and 3 objectives. Our findings suggest that we can improve our understanding of MOEAs using STNs for algorithm analysis.
An Algorithmic Framework for Locally Constrained Homomorphisms
Venue: arXiv cs.DS 2022
Year: 2022

A homomorphism $f$ from a guest graph $G$ to a host graph $H$ is locally bijective, injective or surjective if for every $u\in V(G)$, the restriction of $f$ to the neighbourhood of $u$ is bijective, injective or surjective, respectively. The corresponding decision problems, LBHOM, LIHOM and LSHOM, are well studied both on general graphs and on special graph classes. Apart from complexity results when the problems are parameterized by the treewidth and maximum degree of the guest graph, the three problems still lack a thorough study of their parameterized complexity. This paper fills this gap: we prove a number of new FPT, W[1]-hard and para-NP-complete results by considering a hierarchy of parameters of the guest graph $G$. For our FPT results, we do this through the development of a new algorithmic framework that involves a general ILP model. To illustrate the applicability of the new framework, we also use it to prove FPT results for the Role Assignment problem, which originates from social network theory and is closely related to locally surjective homomorphisms.
Porting OpenACC to OpenMP on heterogeneous systems
Venue: arXiv cs.DC 2022
Year: 2022

This documentation is designed for beginners in Graphics Processing Unit (GPU)-programming and who want to get familiar with OpenACC and OpenMP offloading models. Here we present an overview of these two programming models as well as of the GPU-architectures. Specifically, we provide some insights into the functionality of these models and perform experiments involving different directives and discuss their performance. This is achieved through the use of a mini-application based on solving numerically the Laplace equation. Such experiments reveal the benefit of the use of GPU, which in our case manifests by an increase of the performance by almost a factor of 52. We further carry out a comparative study between the OpenACC and OpenMP models in the aim of converting OpenACC to OpenMP on heterogeneous systems. In this context, we present a short overview of the open-source OpenACC compiler Clacc, which is designed based on translating OpenACC to OpenMP in Clang.