OpenRaiser/Intern-Atlas huggingface dataset:
Spatially-Stationary Model for Holographic MIMO Small-Scale Fading
Venue: arXiv cs.IT 2021
Year: 2021

Imagine an array with a massive (possibly uncountably infinite) number of antennas in a compact space. We refer to a system of this sort as Holographic MIMO. Given the impressive properties of Massive MIMO, one might expect a holographic array to realize extreme spatial resolution, incredible energy efficiency, and unprecedented spectral efficiency. At present, however, its fundamental limits have not been conclusively established. A major challenge for the analysis and understanding of such a paradigm shift is the lack of mathematically tractable and numerically reproducible channel models that retain some semblance to the physical reality. Detailed physical models are, in general, too complex for tractable analysis. This paper aims to take a closer look at this interdisciplinary challenge. Particularly, we consider the small-scale fading in the far-field, and we model it as a zero-mean, spatially-stationary, and correlated Gaussian scalar random field. Physically-meaningful correlation is obtained by requiring that the random field be consistent with the scalar Helmholtz equation. This formulation leads directly to a rather simple and exact description of the three-dimensional small-scale fading as a Fourier plane-wave spectral representation. Suitably discretized, this leads to a discrete representation for the field as a Fourier plane-wave series expansion, from which a computationally efficient way to generate samples of the small-scale fading over spatially-constrained compact spaces is developed. The connections with the conventional tools of linear systems theory and Fourier transform are thoroughly discussed.
A Reproducibility Study of "IP Spoofing Detection in Inter-Domain Traffic"
Venue: arXiv cs.NI 2021
Year: 2021

IP spoofing enables reflection and amplification attacks, which cause major threats to the current Internet infrastructure. Detecting IP packets with incorrect source addresses would help to improve the situation. This is easy at the attacker's network, but very challenging at Internet eXchange Points (IXPs) or in transit networks. In this reproducibility study, we revisit the paper \textit{Detection, Classification, and Analysis of Inter-Domain Traffic with Spoofed Source IP Addresses} published at ACM IMC 2017. Using data from a different IXP and from a different time, we were not able to reproduce the results. Unfortunately, our further analysis reveals structural problems of the state of the art methodology, which are not easy to overcome.
The Power of Two Choices for Random Walks
Venue: arXiv cs.DM 2021
Year: 2021

We apply the power-of-two-choices paradigm to a random walk on a graph: rather than moving to a uniform random neighbour at each step, a controller is allowed to choose from two independent uniform random neighbours. We prove that this allows the controller to significantly accelerate the hitting and cover times in several natural graph classes. In particular, we show that the cover time becomes linear in the number $n$ of vertices on discrete tori and bounded degree trees, of order $\mathcal{O}(n \log \log n)$ on bounded degree expanders, and of order $\mathcal{O}(n (\log \log n)^2)$ on the Erdős-Rényi random graph in a certain sparsely connected regime. We also consider the algorithmic question of computing an optimal strategy, and prove a dichotomy in efficiency between computing strategies for hitting and cover times.
New Bounds on the Biplanar and $k$-Planar Crossing Numbers
Venue: arXiv cs.CG 2021
Year: 2021

The biplanar crossing number of a graph $G$ is the minimum number of crossings over all possible drawings of the edges of $G$ in two disjoint planes. We present new bounds on the biplanar crossing number of complete graphs and complete bipartite graphs. In particular, we prove that the biplanar crossing number of complete bipartite graphs can be approximated to within a factor of $3$, improving over the best previously known approximation factor of $4.03$. For complete graphs, we provide a new approximation factor of $3.17$, improving over the best previous factor of $4.34$. We provide similar improved approximation factors for the $k$-planar crossing number of complete graphs and complete bipartite graphs, for any positive integer $k$. We also investigate the relation between (ordinary) crossing number and biplanar crossing number of general graphs in more depth, and prove that any graph with a crossing number of at most $10$ is biplanar.
You Only Watch Once: A Unified CNN Architecture for Real-Time Spatiotemporal Action Localization
Venue: arXiv cs.CV 2021
Year: 2021

Spatiotemporal action localization requires the incorporation of two sources of information into the designed architecture: (1) temporal information from the previous frames and (2) spatial information from the key frame. Current state-of-the-art approaches usually extract these information with separate networks and use an extra mechanism for fusion to get detections. In this work, we present YOWO, a unified CNN architecture for real-time spatiotemporal action localization in video streams. YOWO is a single-stage architecture with two branches to extract temporal and spatial information concurrently and predict bounding boxes and action probabilities directly from video clips in one evaluation. Since the whole architecture is unified, it can be optimized end-to-end. The YOWO architecture is fast providing 34 frames-per-second on 16-frames input clips and 62 frames-per-second on 8-frames input clips, which is currently the fastest state-of-the-art architecture on spatiotemporal action localization task. Remarkably, YOWO outperforms the previous state-of-the art results on J-HMDB-21 and UCF101-24 with an impressive improvement of ~3% and ~12%, respectively. Moreover, YOWO is the first and only single-stage architecture that provides competitive results on AVA dataset. We make our code and pretrained models publicly available.
New Successor Rules to Efficiently Produce Exponentially Many Binary de Bruijn Sequences
Venue: arXiv cs.IT 2021
Year: 2021

We put forward new general criteria to design successor rules that generate binary de Bruijn sequences. Prior fast algorithms based on successor rules in the literature are then shown to be special instances. We implemented the criteria to join the cycles generated by a number of simple feedback shift registers (FSRs) of order $n$. These include the pure cycling register (PCR) and the pure summing register (PSR). For the PCR, we define a transitive relation on its cycles, based on their weights. We also extend the choices of conjugate states by using shift operations. For the PSR, we define three distinct transitive relations on its cycles, namely a run order, a necklace order, and a mixed order. Using the new orders, we propose numerous classes of successor rules. Each class efficiently generates a number, exponential in $n$, of binary de Bruijn sequences. Producing the next bit in each such sequence takes $O(n)$ memory and $O(n)$ time. We implemented computational routines to confirm the claims.
Fair Division of Mixed Divisible and Indivisible Goods
Venue: arXiv cs.GT 2021
Year: 2021

We study the problem of fair division when the resources contain both divisible and indivisible goods. Classic fairness notions such as envy-freeness (EF) and envy-freeness up to one good (EF1) cannot be directly applied to the mixed goods setting. In this work, we propose a new fairness notion envy-freeness for mixed goods (EFM), which is a direct generalization of both EF and EF1 to the mixed goods setting. We prove that an EFM allocation always exists for any number of agents. We also propose efficient algorithms to compute an EFM allocation for two agents and for $n$ agents with piecewise linear valuations over the divisible goods. Finally, we relax the envy-free requirement, instead asking for $ε$-envy-freeness for mixed goods ($ε$-EFM), and present an algorithm that finds an $ε$-EFM allocation in time polynomial in the number of agents, the number of indivisible goods, and $1/ε$.
Justification-Based Reliability in Machine Learning
Venue: arXiv cs.LG 2021
Year: 2021

With the advent of Deep Learning, the field of machine learning (ML) has surpassed human-level performance on diverse classification tasks. At the same time, there is a stark need to characterize and quantify reliability of a model's prediction on individual samples. This is especially true in application of such models in safety-critical domains of industrial control and healthcare. To address this need, we link the question of reliability of a model's individual prediction to the epistemic uncertainty of the model's prediction. More specifically, we extend the theory of Justified True Belief (JTB) in epistemology, created to study the validity and limits of human-acquired knowledge, towards characterizing the validity and limits of knowledge in supervised classifiers. We present an analysis of neural network classifiers linking the reliability of its prediction on an input to characteristics of the support gathered from the input and latent spaces of the network. We hypothesize that the JTB analysis exposes the epistemic uncertainty (or ignorance) of a model with respect to its inference, thereby allowing for the inference to be only as strong as the justification permits. We explore various forms of support (for e.g., k-nearest neighbors (k-NN) and l_p-norm based) generated for an input, using the training data to construct a justification for the prediction with that input. Through experiments conducted on simulated and real datasets, we demonstrate that our approach can provide reliability for individual predictions and characterize regions where such reliability cannot be ascertained.
ZKSENSE: A Friction-less Privacy-Preserving Human Attestation Mechanism for Mobile Devices
Venue: arXiv cs.CR 2021
Year: 2021

Recent studies show that 20.4% of the internet traffic originates from automated agents. To identify and block such ill-intentioned traffic, mechanisms that verify the humanness of the user are widely deployed, with CAPTCHAs being the most popular. Traditional CAPTCHAs require extra user effort (e.g., solving mathematical puzzles), which can severely downgrade the end-user's experience, especially on mobile, and provide sporadic humanness verification of questionable accuracy. More recent solutions like Google's reCAPTCHA v3, leverage user data, thus raising significant privacy concerns. To address these issues, we present zkSENSE: the first zero-knowledge proof-based humanness attestation system for mobile devices. zkSENSE moves the human attestation to the edge: onto the user's very own device, where humanness of the user is assessed in a privacy-preserving and seamless manner. zkSENSE achieves this by classifying motion sensor outputs of the mobile device, based on a model trained by using both publicly available sensor data and data collected from a small group of volunteers. To ensure the integrity of the process, the classification result is enclosed in a zero-knowledge proof of humanness that can be safely shared with a remote server. We implement zkSENSE as an Android service to demonstrate its effectiveness and practicality. In our evaluation, we show that zkSENSE successfully verifies the humanness of a user across a variety of attacking scenarios and demonstrates 92% accuracy. On a two years old Samsung S9, zkSENSE's attestation takes around 3 seconds (when visual CAPTCHAs need 9.8 seconds) and consumes a negligible amount of battery.
Hardness and Approximation of Minimum Convex Partition
Venue: arXiv cs.CG 2021
Year: 2021

We consider the Minimum Convex Partition problem: Given a set P of n points in the plane, draw a plane graph G on P, with positive minimum degree, such that G partitions the convex hull of P into a minimum number of convex faces. We show that Minimum Convex Partition is NP-hard, and we give several approximation algorithms, from an O(log OPT)-approximation running in O(n^8)-time, where OPT denotes the minimum number of convex faces needed, to an O(sqrt(n) log n)-approximation algorithm running in O(n^2)-time. We say that a point set is k-directed if the (straight) lines containing at least three points have up to k directions. We present an O(k)-approximation algorithm running in n^O(k)-time. Those hardness and approximation results also holds for the Minimum Convex Tiling problem, defined similarly but allowing the use of Steiner points. The approximation results are obtained by relating the problem to the Covering Points with Non-Crossing Segments problem. We show that this problem is NP-hard, and present an FPT algorithm. This allows us to obtain a constant-approximation FPT algorithm for the Minimum Convex Partition Problem where the parameter is the number of faces.
Privacy Preserving Gaze Estimation using Synthetic Images via a Randomized Encoding Based Framework
Venue: arXiv cs.CV 2021
Year: 2021

Eye tracking is handled as one of the key technologies for applications that assess and evaluate human attention, behavior, and biometrics, especially using gaze, pupillary, and blink behaviors. One of the challenges with regard to the social acceptance of eye tracking technology is however the preserving of sensitive and personal information. To tackle this challenge, we employ a privacy-preserving framework based on randomized encoding to train a Support Vector Regression model using synthetic eye images privately to estimate the human gaze. During the computation, none of the parties learn about the data or the result that any other party has. Furthermore, the party that trains the model cannot reconstruct pupil, blinks or visual scanpath. The experimental results show that our privacy-preserving framework is capable of working in real-time, with the same accuracy as compared to non-private version and could be extended to other eye tracking related problems.
Log Message Anomaly Detection and Classification Using Auto-B/LSTM and Auto-GRU
Venue: arXiv cs.LG 2021
Year: 2021

Log messages are now widely used in software systems. They are important for classification as millions of logs are generated each day. Most logs are unstructured which makes classification a challenge. In this paper, Deep Learning (DL) methods called Auto-LSTM, Auto-BLSTM and Auto-GRU are developed for anomaly detection and log classification. These models are used to convert unstructured log data to extracted features which is suitable for classification algorithms. They are evaluated using four data sets, namely BGL, Openstack, Thunderbird and IMDB. The first three are popular log data sets while the fourth is a movie review data set which is used for sentiment classification. The results obtained show that Auto-LSTM, Auto-BLSTM and Auto-GRU perform better than other well-known algorithms.
Auto-Precision Scaling for Distributed Deep Learning
Venue: arXiv cs.DC 2021
Year: 2021

It has been reported that the communication cost for synchronizing gradients can be a bottleneck, which limits the scalability of distributed deep learning. Using low-precision gradients is a promising technique for reducing the bandwidth requirement. In this work, we propose Auto Precision Scaling (APS), an algorithm that can improve the accuracy when we communicate gradients by low-precision floating-point values. APS can improve the accuracy for all precisions with a trivial communication cost. Our experimental results show that for many applications, APS can train state-of-the-art models by 8-bit gradients with no or only a tiny accuracy loss (<0.05%). Furthermore, we can avoid any accuracy loss by designing a hybrid-precision technique. Finally, we propose a performance model to evaluate the proposed method. Our experimental results show that APS can get a significant speedup over state-of-the-art methods. To make it available to researchers and developers, we design and implement CPD (Customized-Precision Deep Learning) system, which can simulate the training process using an arbitrary low-precision customized floating-point format. We integrate CPD into PyTorch and make it open-source.
Volume-preserving Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

We propose a novel approach to addressing the vanishing (or exploding) gradient problem in deep neural networks. We construct a new architecture for deep neural networks where all layers (except the output layer) of the network are a combination of rotation, permutation, diagonal, and activation sublayers which are all volume preserving. Our approach replaces the standard weight matrix of a neural network with a combination of diagonal, rotational and permutation matrices, all of which are volume-preserving. We introduce a coupled activation function allowing us to preserve volume even in the activation function portion of a neural network layer. This control on the volume forces the gradient (on average) to maintain equilibrium and not explode or vanish. To demonstrate our architecture we apply our volume-preserving neural network model to two standard datasets.
Gemmini: Enabling Systematic Deep-Learning Architecture Evaluation via Full-Stack Integration
Venue: arXiv cs.DC 2021
Year: 2021

DNN accelerators are often developed and evaluated in isolation without considering the cross-stack, system-level effects in real-world environments. This makes it difficult to appreciate the impact of System-on-Chip (SoC) resource contention, OS overheads, and programming-stack inefficiencies on overall performance/energy-efficiency. To address this challenge, we present Gemmini, an open-source*, full-stack DNN accelerator generator. Gemmini generates a wide design-space of efficient ASIC accelerators from a flexible architectural template, together with flexible programming stacks and full SoCs with shared resources that capture system-level effects. Gemmini-generated accelerators have also been fabricated, delivering up to three orders-of-magnitude speedups over high-performance CPUs on various DNN benchmarks. * https://github.com/ucb-bar/gemmini
The Sitting Closer to Friends than Enemies Problem in Trees
Venue: arXiv cs.DM 2021
Year: 2021

A metric space $\mathcal{T}$ is a \emph{real tree} if for any pair of points $x, y \in \mathcal{T}$ all topological embeddings $σ$ of the segment $[0,1]$ into $\mathcal{T}$, such that $σ(0)=x$ and $σ(1)=y$, have the same image (which is then a geodesic segment from $x$ to $y$). A \emph{signed graph} is a graph where each edge has a positive or negative sign. The \emph{Sitting Closer to Friends than Enemies} problem in trees has a signed graph $S$ as an input. The purpose is to determine if there exists an injective mapping (called \emph{valid distance drawing}) from $V(S)$ to the points of a real tree such that, for every $u \in V(S)$, for every positive neighbor $v$ of $u$, and negative neighbor $w$ of $u$, the distance between $v$ and $u$ is smaller than the distance between $w$ and $u$. In this work, we show that a complete signed graph has a valid distance drawing in a real tree if and only if its subgraph composed of all (and only) its positive edges has an intersection representation by unit balls in a real tree. Besides, as an instrumental result, we show that a graph has an intersection representation by unit balls in a real tree if and only if it has an intersection representation by proper balls, and if and only if it has an intersection representation by arbitrary balls in a real tree.
Evaluating Commonsense in Pre-trained Language Models
Venue: arXiv cs.CL 2021
Year: 2021

Contextualized representations trained over large raw text data have given remarkable improvements for NLP tasks including question answering and reading comprehension. There have been works showing that syntactic, semantic and word sense knowledge are contained in such representations, which explains why they benefit such tasks. However, relatively little work has been done investigating commonsense knowledge contained in contextualized representations, which is crucial for human question answering and reading comprehension. We study the commonsense ability of GPT, BERT, XLNet, and RoBERTa by testing them on seven challenging benchmarks, finding that language modeling and its variants are effective objectives for promoting models' commonsense ability while bi-directional context and larger training set are bonuses. We additionally find that current models do poorly on tasks require more necessary inference steps. Finally, we test the robustness of models by making dual test cases, which are correlated so that the correct prediction of one sample should lead to correct prediction of the other. Interestingly, the models show confusion on these test cases, which suggests that they learn commonsense at the surface rather than the deep level. We release a test set, named CATs publicly, for future research.
Learning Multi-level Weight-centric Features for Few-shot Learning
Venue: arXiv cs.CV 2021
Year: 2021

Few-shot learning is currently enjoying a considerable resurgence of interest, aided by the recent advance of deep learning. Contemporary approaches based on weight-generation scheme delivers a straightforward and flexible solution to the problem. However, they did not fully consider both the representation power for unseen categories and weight generation capacity in feature learning, making it a significant performance bottleneck. This paper proposes a multi-level weight-centric feature learning to give full play to feature extractor's dual roles in few-shot learning. Our proposed method consists of two essential techniques: a weight-centric training strategy to improve the features' prototype-ability and a multi-level feature incorporating a mid- and relation-level information. The former increases the feasibility of constructing a discriminative decision boundary based on a few samples. Simultaneously, the latter helps improve the transferability for characterizing novel classes and preserve classification capability for base classes. We extensively evaluate our approach to low-shot classification benchmarks. Experiments demonstrate our proposed method significantly outperforms its counterparts in both standard and generalized settings and using different network backbones.
A Formal System for the Universal Quantification of Schematic Variables
Venue: arXiv cs.LO 2021
Year: 2021

We advocate the use of de Bruijn's universal abstraction $λ^\infty$ for the quantification of schematic variables in the predicative setting and we present a typed $λ$-calculus featuring the quantifier $λ^\infty$ accompanied by other practically useful constructions like explicit substitutions and expected type annotations. The calculus stands just on two notions, i.e., bound rt-reduction and parametric validity, and has the expressive power of $λ\rightarrow$. Thus, while not aiming at being a logical framework by itself, it does enjoy many desired invariants of logical frameworks including confluence of reduction, strong normalization, preservation of type by reduction, decidability, correctness of types and uniqueness of types up to conversion. This calculus belongs to the $λδ$ family of formal systems, which borrow some features from the pure type systems and some from the languages of the Automath tradition, but stand outside both families. In particular, the calculus includes and evolves two earlier systems of this family. Moreover, a machine-checked specification of its theory is available.