OpenRaiser/Intern-Atlas huggingface dataset:
Blocked and Hierarchical Disentangled Representation From Information Theory Perspective
Venue: arXiv cs.IT 2021
Year: 2021

We propose a novel and theoretical model, blocked and hierarchical variational autoencoder (BHiVAE), to get better-disentangled representation. It is well known that information theory has an excellent explanatory meaning for the network, so we start to solve the disentanglement problem from the perspective of information theory. BHiVAE mainly comes from the information bottleneck theory and information maximization principle. Our main idea is that (1) Neurons block not only one neuron node is used to represent attribute, which can contain enough information; (2) Create a hierarchical structure with different attributes on different layers, so that we can segment the information within each layer to ensure that the final representation is disentangled. Furthermore, we present supervised and unsupervised BHiVAE, respectively, where the difference is mainly reflected in the separation of information between different blocks. In supervised BHiVAE, we utilize the label information as the standard to separate blocks. In unsupervised BHiVAE, without extra information, we use the Total Correlation (TC) measure to achieve independence, and we design a new prior distribution of the latent space to guide the representation learning. It also exhibits excellent disentanglement results in experiments and superior classification accuracy in representation learning.
Generative Zero-shot Network Quantization
Venue: arXiv cs.CV 2021
Year: 2021

Convolutional neural networks are able to learn realistic image priors from numerous training samples in low-level image generation and restoration. We show that, for high-level image recognition tasks, we can further reconstruct "realistic" images of each category by leveraging intrinsic Batch Normalization (BN) statistics without any training data. Inspired by the popular VAE/GAN methods, we regard the zero-shot optimization process of synthetic images as generative modeling to match the distribution of BN statistics. The generated images serve as a calibration set for the following zero-shot network quantizations. Our method meets the needs for quantizing models based on sensitive information, \textit{e.g.,} due to privacy concerns, no data is available. Extensive experiments on benchmark datasets show that, with the help of generated data, our approach consistently outperforms existing data-free quantization methods.
Learning based signal detection for MIMO systems with unknown noise statistics
Venue: arXiv cs.LG 2021
Year: 2021

This paper aims to devise a generalized maximum likelihood (ML) estimator to robustly detect signals with unknown noise statistics in multiple-input multiple-output (MIMO) systems. In practice, there is little or even no statistical knowledge on the system noise, which in many cases is non-Gaussian, impulsive and not analyzable. Existing detection methods have mainly focused on specific noise models, which are not robust enough with unknown noise statistics. To tackle this issue, we propose a novel ML detection framework to effectively recover the desired signal. Our framework is a fully probabilistic one that can efficiently approximate the unknown noise distribution through a normalizing flow. Importantly, this framework is driven by an unsupervised learning approach, where only the noise samples are required. To reduce the computational complexity, we further present a low-complexity version of the framework, by utilizing an initial estimation to reduce the search space. Simulation results show that our framework outperforms other existing algorithms in terms of bit error rate (BER) in non-analytical noise environments, while it can reach the ML performance bound in analytical noise environments. The code of this paper is available at https://github.com/skypitcher/manfe.
Anti-UAV: A Large Multi-Modal Benchmark for UAV Tracking
Venue: arXiv cs.CV 2021
Year: 2021

Unmanned Aerial Vehicle (UAV) offers lots of applications in both commerce and recreation. With this, monitoring the operation status of UAVs is crucially important. In this work, we consider the task of tracking UAVs, providing rich information such as location and trajectory. To facilitate research on this topic, we propose a dataset, Anti-UAV, with more than 300 video pairs containing over 580k manually annotated bounding boxes. The releasing of such a large-scale dataset could be a useful initial step in research of tracking UAVs. Furthermore, the advancement of addressing research challenges in Anti-UAV can help the design of anti-UAV systems, leading to better surveillance of UAVs. Besides, a novel approach named dual-flow semantic consistency (DFSC) is proposed for UAV tracking. Modulated by the semantic flow across video sequences, the tracker learns more robust class-level semantic information and obtains more discriminative instance-level features. Experimental results demonstrate that Anti-UAV is very challenging, and the proposed method can effectively improve the tracker's performance. The Anti-UAV benchmark and the code of the proposed approach will be publicly available at https://github.com/ucas-vg/Anti-UAV.
Hybrid Beamforming for Terahertz Wireless Communications: Challenges, Architectures, and Open Problems
Venue: arXiv cs.IT 2021
Year: 2021

Terahertz (THz) communications are regarded as a pillar technology for the sixth generation (6G) wireless systems, by offering multi-ten-GHz bandwidth. To overcome the short transmission distance and huge propagation loss, ultra-massive (UM) MIMO systems that employ sub-millimeter wavelength antennas array are proposed to enable an enticingly high array gain. In the UM-MIMO systems, hybrid beamforming stands out for its great potential in promisingly high data rate and reduced power consumption. In this paper, challenges and features of the THz hybrid beamforming design are investigated, in light of the distinctive THz peculiarities. Specifically, we demonstrate that the spatial degree-of-freedom (SDoF) is less than 5, which is caused by the extreme sparsity of the THz channel. The blockage problem caused by the huge reflection and scattering losses, as high as 15 dB or over, is studied. Moreover, we analyze the challenges led by the array containing 1024 or more antennas, including the requirement for intelligent subarray architecture, strict energy efficiency, and propagation characterization based on spherical-wave propagation mechanisms. Owning up to hundreds of GHz bandwidth, beam squint effect could cause over 5~dB array gain loss, when the fractional bandwidth exceeds 10%. Inspired by these facts, three novel THz-specific hybrid beamforming architectures are presented, including widely-spaced multi-subarray, dynamic array-of-subarrays, and true-time-delay-based architectures. We also demonstrate the potential data rate, power consumption, and array gain capabilities for THz communications. As a roadmap of THz hybrid beamforming design, multiple open problems and potential research directions are elaborated.
Content-Based Textual File Type Detection at Scale
Venue: arXiv cs.SE 2021
Year: 2021

Programming language detection is a common need in the analysis of large source code bases. It is supported by a number of existing tools that rely on several features, and most notably file extensions, to determine file types. We consider the problem of accurately detecting the type of files commonly found in software code bases, based solely on textual file content. Doing so is helpful to classify source code that lack file extensions (e.g., code snippets posted on the Web or executable scripts), to avoid misclassifying source code that has been recorded with wrong or uncommon file extensions, and also shed some light on the intrinsic recognizability of source code files. We propose a simple model that (a) use a language-agnostic word tokenizer for textual files, (b) group tokens in 1-/2-grams, (c) build feature vectors based on N-gram frequencies, and (d) use a simple fully connected neural network as classifier. As training set we use textual files extracted from GitHub repositories with at least 1000 stars, using existing file extensions as ground truth. Despite its simplicity the proposed model reaches 85% in our experiments for a relatively high number of recognized classes (more than 130 file types).
A Note on Connectivity of Sublevel Sets in Deep Learning
Venue: arXiv cs.LG 2021
Year: 2021

It is shown that for deep neural networks, a single wide layer of width $N+1$ ($N$ being the number of training samples) suffices to prove the connectivity of sublevel sets of the training loss function. In the two-layer setting, the same property may not hold even if one has just one neuron less (i.e. width $N$ can lead to disconnected sublevel sets).
Synwalk -- Community Detection via Random Walk Modelling
Venue: arXiv cs.SI 2021
Year: 2021

Complex systems, abstractly represented as networks, are ubiquitous in everyday life. Analyzing and understanding these systems requires, among others, tools for community detection. As no single best community detection algorithm can exist, robustness across a wide variety of problem settings is desirable. In this work, we present Synwalk, a random walk-based community detection method. Synwalk builds upon a solid theoretical basis and detects communities by synthesizing the random walk induced by the given network from a class of candidate random walks. We thoroughly validate the effectiveness of our approach on synthetic and empirical networks, respectively, and compare Synwalk's performance with the performance of Infomap and Walktrap. Our results indicate that Synwalk performs robustly on networks with varying mixing parameters and degree distributions. We outperform Infomap on networks with high mixing parameter, and Infomap and Walktrap on networks with many small communities and low average degree. Our work has a potential to inspire further development of community detection via synthesis of random walks and we provide concrete ideas for future research.
Improved Algorithms for the General Exact Satisfiability Problem
Venue: arXiv cs.DS 2021
Year: 2021

The Exact Satisfiability problem asks if we can find a satisfying assignment to each clause such that exactly one literal in each clause is assigned $1$, while the rest are all assigned $0$. We can generalise this problem further by defining that a $C^j$ clause is solved iff exactly $j$ of the literals in the clause are $1$ and all others are $0$. We now introduce the family of Generalised Exact Satisfiability problems called G$i$XSAT as the problem to check whether a given instance consisting of $C^j$ clauses with $j \in \{0,1,\ldots,i\}$ for each clause has a satisfying assignment. In this paper, we present faster exact polynomial space algorithms, using a nonstandard measure, to solve G$i$XSAT, for $i\in \{2,3,4\}$, in $O(1.3674^n)$ time, $O(1.5687^n)$ time and $O(1.6545^n)$ time, respectively, using polynomial space, where $n$ is the number of variables. This improves the current state of the art for polynomial space algorithms from $O(1.4203^n)$ time for G$2$XSAT by Zhou, Jiang and Yin and from $O(1.6202^n)$ time for G$3$XSAT by Dahllöf and from $O(1.6844^n)$ time for G$4$XSAT which was by Dahllöf as well. In addition, we present faster exact algorithms solving G$2$XSAT, G$3$XSAT and G$4$XSAT in $O(1.3188^n)$ time, $O(1.3407^n)$ time and $O(1.3536^n)$ time respectively at the expense of using exponential space.
Quantitative Security Risk Modeling and Analysis with RisQFLan
Venue: arXiv cs.CR 2021
Year: 2021

Domain-specific quantitative modeling and analysis approaches are fundamental in scenarios in which qualitative approaches are inappropriate or unfeasible. In this paper, we present a tool-supported approach to quantitative graph-based security risk modeling and analysis based on attack-defense trees. Our approach is based on QFLan, a successful domain-specific approach to support quantitative modeling and analysis of highly configurable systems, whose domain-specific components have been decoupled to facilitate the instantiation of the QFLan approach in the domain of graph-based security risk modeling and analysis. Our approach incorporates distinctive features from three popular kinds of attack trees, namely enhanced attack trees, capabilities-based attack trees and attack countermeasure trees, into the domain-specific modeling language. The result is a new framework, called RisQFLan, to support quantitative security risk modeling and analysis based on attack-defense diagrams. By offering either exact or statistical verification of probabilistic attack scenarios, RisQFLan constitutes a significant novel contribution to the existing toolsets in that domain. We validate our approach by highlighting the additional features offered by RisQFLan in three illustrative case studies from seminal approaches to graph-based security risk modeling analysis based on attack trees.
Sum-Rate-Distortion Function for Indirect Multiterminal Source Coding in Federated Learning
Venue: arXiv cs.IT 2021
Year: 2021

One of the main focus in federated learning (FL) is the communication efficiency since a large number of participating edge devices send their updates to the edge server at each round of the model training. Existing works reconstruct each model update from edge devices and implicitly assume that the local model updates are independent over edge devices. In FL, however, the model update is an indirect multi-terminal source coding problem, also called as the CEO problem where each edge device cannot observe directly the gradient that is to be reconstructed at the decoder, but is rather provided only with a noisy version. The existing works do not leverage the redundancy in the information transmitted by different edges. This paper studies the rate region for the indirect multiterminal source coding problem in FL. The goal is to obtain the minimum achievable rate at a particular upper bound of gradient variance. We obtain the rate region for the quadratic vector Gaussian CEO problem under unbiased estimator and derive an explicit formula of the sum-rate-distortion function in the special case where gradient are identical over edge device and dimension. Finally, we analyse communication efficiency of convex Minibatched SGD and non-convex Minibatched SGD based on the sum-rate-distortion function, respectively.
Copycat CNN: Are Random Non-Labeled Data Enough to Steal Knowledge from Black-box Models?
Venue: arXiv cs.CR 2021
Year: 2021

Convolutional neural networks have been successful lately enabling companies to develop neural-based products, which demand an expensive process, involving data acquisition and annotation; and model generation, usually requiring experts. With all these costs, companies are concerned about the security of their models against copies and deliver them as black-boxes accessed by APIs. Nonetheless, we argue that even black-box models still have some vulnerabilities. In a preliminary work, we presented a simple, yet powerful, method to copy black-box models by querying them with natural random images. In this work, we consolidate and extend the copycat method: (i) some constraints are waived; (ii) an extensive evaluation with several problems is performed; (iii) models are copied between different architectures; and, (iv) a deeper analysis is performed by looking at the copycat behavior. Results show that natural random images are effective to generate copycats for several problems.
Joint Autoregressive and Graph Models for Software and Developer Social Networks
Venue: arXiv cs.IR 2021
Year: 2021

Social network research has focused on hyperlink graphs, bibliographic citations, friend/follow patterns, influence spread, etc. Large software repositories also form a highly valuable networked artifact, usually in the form of a collection of packages, their developers, dependencies among them, and bug reports. This "social network of code" is rarely studied by social network researchers. We introduce two new problems in this setting. These problems are well-motivated in the software engineering community but not closely studied by social network scientists. The first is to identify packages that are most likely to be troubled by bugs in the immediate future, thereby demanding the greatest attention. The second is to recommend developers to packages for the next development cycle. Simple autoregression can be applied to historical data for both problems, but we propose a novel method to integrate network-derived features and demonstrate that our method brings additional benefits. Apart from formalizing these problems and proposing new baseline approaches, we prepare and contribute a substantial dataset connecting multiple attributes built from the long-term history of 20 releases of Ubuntu, growing to over 25,000 packages with their dependency links, maintained by over 3,800 developers, with over 280k bug reports.
Enabling Large Neural Networks on Tiny Microcontrollers with Swapping
Venue: arXiv cs.AR 2021
Year: 2021

Running neural networks (NNs) on microcontroller units (MCUs) is becoming increasingly important, but is very difficult due to the tiny SRAM size of MCU. Prior work proposes many algorithm-level techniques to reduce NN memory footprints, but all at the cost of sacrificing accuracy and generality, which disqualifies MCUs for many important use cases. We investigate a system solution for MCUs to execute NNs out of core: dynamically swapping NN data chunks between an MCU's tiny SRAM and its large, low-cost external flash. Out-of-core NNs on MCUs raise multiple concerns: execution slowdown, storage wear out, energy consumption, and data security. We present a study showing that none is a showstopper; the key benefit -- MCUs being able to run large NNs with full accuracy and generality -- triumphs the overheads. Our findings suggest that MCUs can play a much greater role in edge intelligence.
Optimal Demand Private Coded Caching for Users with Small Buffers
Venue: arXiv cs.IT 2021
Year: 2021

Coded Caching is an efficient technique to reduce peak hour network traffic. One limitation of known coded caching schemes is that the demands of all users are revealed to their peers in the delivery phase. Schemes that assure privacy for user demands are studied in recent past. Assuming that the users are equipped with caches of small memory sizes, the achievable rate under demand privacy constraints is investigated in this work. We present an MDS code based demand private coded caching scheme with $K$ users and $N$ files that achieves a memory rate pair $\left(\frac{1}{K(N-1)+1},N\left(1-\frac{1}{K(N-1)+1}\right)\right)$. The presented memory-rate pair meets the lower bound under demand-privacy requirements, proposed by Yan \textit{et al.} in the recent work \cite{c13}. By memory sharing this characterizes the exact rate-memory trade-off for the demand private coded caching scheme for cache memory $M\in \left[0,\frac{1}{K(N-1)+1}\right]$.
Certifying Inexpressibility
Venue: arXiv cs.FL 2021
Year: 2021

Different classes of automata on infinite words have different expressive power. Deciding whether a given language $L \subseteq Σ^ω$ can be expressed by an automaton of a desired class can be reduced to deciding a game between Prover and Refuter: in each turn of the game, Refuter provides a letter in $Σ$, and Prover responds with an annotation of the current state of the run (for example, in the case of Büchi automata, whether the state is accepting or rejecting, and in the case of parity automata, what the color of the state is). Prover wins if the sequence of annotations she generates is correct: it is an accepting run iff the word generated by Refuter is in $L$. We show how a winning strategy for Refuter can serve as a simple and easy-to-understand certificate to inexpressibility, and how it induces additional forms of certificates. Our framework handles all classes of deterministic automata, including ones with structural restrictions like weak automata. In addition, it can be used for refuting separation of two languages by an automaton of the desired class, and for finding automata that approximate $L$ and belong to the desired class.
Item Recommendation from Implicit Feedback
Venue: arXiv cs.IR 2021
Year: 2021

The task of item recommendation is to select the best items for a user from a large catalogue of items. Item recommenders are commonly trained from implicit feedback which consists of past actions that are positive only. Core challenges of item recommendation are (1) how to formulate a training objective from implicit feedback and (2) how to efficiently train models over a large item catalogue. This article provides an overview of item recommendation, its unique characteristics and some common approaches. It starts with an introduction to the problem and discusses different training objectives. The main body deals with learning algorithms and presents sampling based algorithms for general recommenders and more efficient algorithms for dot product models. Finally, the application of item recommenders for retrieval tasks is discussed.
Modeling and Leveraging Analytic Focus During Exploratory Visual Analysis
Venue: arXiv cs.HC 2021
Year: 2021

Visual analytics systems enable highly interactive exploratory data analysis. Across a range of fields, these technologies have been successfully employed to help users learn from complex data. However, these same exploratory visualization techniques make it easy for users to discover spurious findings. This paper proposes new methods to monitor a user's analytic focus during visual analysis of structured datasets and use it to surface relevant articles that contextualize the visualized findings. Motivated by interactive analyses of electronic health data, this paper introduces a formal model of analytic focus, a computational approach to dynamically update the focus model at the time of user interaction, and a prototype application that leverages this model to surface relevant medical publications to users during visual analysis of a large corpus of medical records. Evaluation results with 24 users show that the modeling approach has high levels of accuracy and is able to surface highly relevant medical abstracts.
Distributed Compilation System for High-Speed Software Build Processes
Venue: arXiv cs.DC 2021
Year: 2021

The idle time of personal computers has increased steadily due to the generalization of computer usage and cloud computing. Clustering research aims at utilizing idle computer resources for processing a variable workload on a large number of computers. The workload is processed continually despite the volatile status of the individual computer resources. This paper proposes a distributed compilation system for improving the processing speed of CPU-intensive software compilations. This significantly reduces the compilation time of mass sources by using the idle resources. We expect gains of up to 65% compared to non-distributed compilation systems.
Prior Preference Learning from Experts:Designing a Reward with Active Inference
Venue: arXiv cs.LG 2021
Year: 2021

Active inference may be defined as Bayesian modeling of a brain with a biologically plausible model of the agent. Its primary idea relies on the free energy principle and the prior preference of the agent. An agent will choose an action that leads to its prior preference for a future observation. In this paper, we claim that active inference can be interpreted using reinforcement learning (RL) algorithms and find a theoretical connection between them. We extend the concept of expected free energy (EFE), which is a core quantity in active inference, and claim that EFE can be treated as a negative value function. Motivated by the concept of prior preference and a theoretical connection, we propose a simple but novel method for learning a prior preference from experts. This illustrates that the problem with inverse RL can be approached with a new perspective of active inference. Experimental results of prior preference learning show the possibility of active inference with EFE-based rewards and its application to an inverse RL problem.