OpenRaiser/Intern-Atlas huggingface dataset:
A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion
Venue: arXiv cs.LG 2021
Year: 2021

Matrix learning is at the core of many machine learning problems. A number of real-world applications such as collaborative filtering and text mining can be formulated as a low-rank matrix completion problem, which recovers incomplete matrix using low-rank assumptions. To ensure that the matrix solution has a low rank, a recent trend is to use nonconvex regularizers that adaptively penalize singular values. They offer good recovery performance and have nice theoretical properties, but are computationally expensive due to repeated access to individual singular values. In this paper, based on the key insight that adaptive shrinkage on singular values improve empirical performance, we propose a new nonconvex low-rank regularizer called "nuclear norm minus Frobenius norm" regularizer, which is scalable, adaptive and sound. We first show it provably holds the adaptive shrinkage property. Further, we discover its factored form which bypasses the computation of singular values and allows fast optimization by general optimization algorithms. Stable recovery and convergence are guaranteed. Extensive low-rank matrix completion experiments on a number of synthetic and real-world data sets show that the proposed method obtains state-of-the-art recovery performance while being the fastest in comparison to existing low-rank matrix learning methods.
Quantum Hoare logic with classical variables
Venue: arXiv cs.LO 2021
Year: 2021

Hoare logic provides a syntax-oriented method to reason about program correctness and has been proven effective in the verification of classical and probabilistic programs. Existing proposals for quantum Hoare logic either lack completeness or support only quantum variables, thus limiting their capability in practical use. In this paper, we propose a quantum Hoare logic for a simple while language which involves both classical and quantum variables. Its soundness and relative completeness are proven for both partial and total correctness of quantum programs written in the language. Remarkably, with novel definitions of classical-quantum states and corresponding assertions, the logic system is quite simple and similar to the traditional Hoare logic for classical programs. Furthermore, to simplify reasoning in real applications, auxiliary proof rules are provided which support standard logical operation in the classical part of assertions, and of super-operator application in the quantum part. Finally, a series of practical quantum algorithms, in particular the whole algorithm of Shor's factorisation, are formally verified to show the effectiveness of the logic.
Prediction of Homicides in Urban Centers: A Machine Learning Approach
Venue: arXiv cs.AI 2021
Year: 2021

Relevant research has been highlighted in the computing community to develop machine learning models capable of predicting the occurrence of crimes, analyzing contexts of crimes, extracting profiles of individuals linked to crime, and analyzing crimes over time. However, models capable of predicting specific crimes, such as homicide, are not commonly found in the current literature. This research presents a machine learning model to predict homicide crimes, using a dataset that uses generic data (without study location dependencies) based on incident report records for 34 different types of crimes, along with time and space data from crime reports. Experimentally, data from the city of Belém - Pará, Brazil was used. These data were transformed to make the problem generic, enabling the replication of this model to other locations. In the research, analyses were performed with simple and robust algorithms on the created dataset. With this, statistical tests were performed with 11 different classification methods and the results are related to the prediction's occurrence and non-occurrence of homicide crimes in the month subsequent to the occurrence of other registered crimes, with 76% assertiveness for both classes of the problem, using Random Forest. Results are considered as a baseline for the proposed problem.
Generative Design by Reinforcement Learning: Enhancing the Diversity of Topology Optimization Designs
Venue: arXiv cs.CV 2021
Year: 2021

Generative design refers to computational design methods that can automatically conduct design exploration under constraints defined by designers. Among many approaches, topology optimization-based generative designs aim to explore diverse topology designs, which cannot be represented by conventional parametric design approaches. Recently, data-driven topology optimization research has started to exploit artificial intelligence, such as deep learning or machine learning, to improve the capability of design exploration. This study proposes a reinforcement learning (RL) based generative design process, with reward functions maximizing the diversity of topology designs. We formulate generative design as a sequential problem of finding optimal design parameter combinations in accordance with a given reference design. Proximal Policy Optimization is used as the learning framework, which is demonstrated in the case study of an automotive wheel design problem. To reduce the heavy computational burden of the wheel topology optimization process required by our RL formulation, we approximate the optimization process with neural networks. With efficient data preprocessing/augmentation and neural architecture, the neural networks achieve a generalized performance and symmetricity-reserving characteristics. We show that RL-based generative design produces a large number of diverse designs within a short inference time by exploiting GPU in a fully automated manner. It is different from the previous approach using CPU which takes much more processing time and involving human intervention.
WAFFLE: Watermarking in Federated Learning
Venue: arXiv cs.CR 2021
Year: 2021

Federated learning is a distributed learning technique where machine learning models are trained on client devices in which the local training data resides. The training is coordinated via a central server which is, typically, controlled by the intended owner of the resulting model. By avoiding the need to transport the training data to the central server, federated learning improves privacy and efficiency. But it raises the risk of model theft by clients because the resulting model is available on every client device. Even if the application software used for local training may attempt to prevent direct access to the model, a malicious client may bypass any such restrictions by reverse engineering the application software. Watermarking is a well-known deterrence method against model theft by providing the means for model owners to demonstrate ownership of their models. Several recent deep neural network (DNN) watermarking techniques use backdooring: training the models with additional mislabeled data. Backdooring requires full access to the training data and control of the training process. This is feasible when a single party trains the model in a centralized manner, but not in a federated learning setting where the training process and training data are distributed among several client devices. In this paper, we present WAFFLE, the first approach to watermark DNN models trained using federated learning. It introduces a retraining step at the server after each aggregation of local models into the global model. We show that WAFFLE efficiently embeds a resilient watermark into models incurring only negligible degradation in test accuracy (-0.17%), and does not require access to training data. We also introduce a novel technique to generate the backdoor used as a watermark. It outperforms prior techniques, imposing no communication, and low computational (+3.2%) overhead.
Analysis and Optimization for Large-Scale LoRa Networks: Throughput Fairness and Scalability
Venue: arXiv cs.IT 2021
Year: 2021

LoRa networks are pivotally enabling Long Range connectivity to low-cost and power-constrained user equipments (UEs) in a wide area, whereas a critical issue is to effectively allocate wireless resources to support potentially massive UEs while resolving the prominent near-far fairness issue, which is challenging due to the lack of tractable analytical model and the practical requirement for low-complexity and low-overhead design. Leveraging on stochastic geometry, especially the Poisson rain model, we derive (semi-) closed-form formulas for the aggregate interference distribution, packet success probability and hence system throughput in both single-cell and multi-cell setups with frequency reuse, by accounting for channel fading, random UE distribution, partial packet overlapping, and/or multi-gateway packet reception. The analytical formulas require only average channel statistics and spatial UE distribution, which enable tractable network performance evaluation and incubate our proposed Iterative Balancing (IB) method that quickly yields high-level policies of joint spreading factor (SF) allocation, power control, and duty cycle adjustment for gauging the average max-min UE throughput or supported UE density with rate requirements. Numerical results validate the analytical formulas and the effectiveness of our proposed optimization scheme, which greatly alleviates the near-far fairness issue and reduces the spatial power consumption, while significantly improving the cell-edge throughput as well as the spatial (sum) throughput for the majority of UEs, by adapting to the UE/gateway densities.
Sequence-to-Sequence Predictive Model: From Prosody To Communicative Gestures
Venue: arXiv cs.HC 2021
Year: 2021

Communicative gestures and speech acoustic are tightly linked. Our objective is to predict the timing of gestures according to the acoustic. That is, we want to predict when a certain gesture occurs. We develop a model based on a recurrent neural network with attention mechanism. The model is trained on a corpus of natural dyadic interaction where the speech acoustic and the gesture phases and types have been annotated. The input of the model is a sequence of speech acoustic and the output is a sequence of gesture classes. The classes we are using for the model output is based on a combination of gesture phases and gesture types. We use a sequence comparison technique to evaluate the model performance. We find that the model can predict better certain gesture classes than others. We also perform ablation studies which reveal that fundamental frequency is a relevant feature for gesture prediction task. In another sub-experiment, we find that including eyebrow movements as acting as beat gesture improves the performance. Besides, we also find that a model trained on the data of one given speaker also works for the other speaker of the same conversation. We also perform a subjective experiment to measure how respondents judge the naturalness, the time consistency, and the semantic consistency of the generated gesture timing of a virtual agent. Our respondents rate the output of our model favorably.
Pictorial and apictorial polygonal jigsaw puzzles: The lazy caterer model, properties, and solvers
Venue: arXiv cs.CV 2021
Year: 2021

Jigsaw puzzle solving, the problem of constructing a coherent whole from a set of non-overlapping unordered visual fragments, is fundamental to numerous applications and yet most of the literature of the last two decades has focused thus far on less realistic puzzles whose pieces are identical squares. Here we formalize a new type of jigsaw puzzle where the pieces are general convex polygons generated by cutting through a global polygonal shape/image with an arbitrary number of straight cuts, a generation model inspired by the celebrated Lazy caterer's sequence. We analyze the theoretical properties of such puzzles, including the inherent challenges in solving them once pieces are contaminated with geometrical noise. To cope with such difficulties and obtain tractable solutions, we abstract the problem as a multi-body spring-mass dynamical system endowed with hierarchical loop constraints and a layered reconstruction process. We define evaluation metrics and present experimental results on both apictorial and pictorial puzzles to show that they are solvable completely automatically.
A blockchain-based Forensic Model for Financial Crime Investigation: The Embezzlement Scenario
Venue: arXiv cs.CR 2021
Year: 2021

The financial crime landscape is evolving along with the digitization in financial services. In this context, laws and regulations cannot efficiently cope with a fast-moving industry such as finance, which translates in late adoption of measures and legal voids, providing a fruitful landscape for malicious actors. In parallel, blockchain technology and its promising features such as immutability, verifiability, and authentication, enhance the opportunities of financial forensics. In this paper, we focus on an embezzlement scheme and we provide a forensic-by-design methodology for its investigation. In addition, the feasibility and adaptability of our approach can be extended and embrace digital investigations on other types of schemes. We provide a functional implementation based on smart contracts and we integrate standardised forensic flows and chain of custody preservation mechanisms. Finally, we discuss the benefits and challenges of the symbiotic relationship between blockchain and financial investigations, along with future research directions.
Dataset Bias in Few-shot Image Recognition
Venue: arXiv cs.CV 2021
Year: 2021

The goal of few-shot image recognition (FSIR) is to identify novel categories with a small number of annotated samples by exploiting transferable knowledge from training data (base categories). Most current studies assume that the transferable knowledge can be well used to identify novel categories. However, such transferable capability may be impacted by the dataset bias, and this problem has rarely been investigated before. Besides, most of few-shot learning methods are biased to different datasets, which is also an important issue that needs to be investigated deeply. In this paper, we first investigate the impact of transferable capabilities learned from base categories. Specifically, we use the relevance to measure relationships between base categories and novel categories. Distributions of base categories are depicted via the instance density and category diversity. The FSIR model learns better transferable knowledge from relevant training data. In the relevant data, dense instances or diverse categories can further enrich the learned knowledge. Experimental results on different sub-datasets of ImagNet demonstrate category relevance, instance density and category diversity can depict transferable bias from base categories. Second, we investigate performance differences on different datasets from dataset structures and different few-shot learning methods. Specifically, we introduce image complexity, intra-concept visual consistency, and inter-concept visual similarity to quantify characteristics of dataset structures. We use these quantitative characteristics and four few-shot learning methods to analyze performance differences on five different datasets. Based on the experimental analysis, some insightful observations are obtained from the perspective of both dataset structures and few-shot learning methods. We hope these observations are useful to guide future FSIR research.
Sampling Multiple Edges Efficiently
Venue: arXiv cs.DS 2021
Year: 2021

We present a sublinear time algorithm that allows one to sample multiple edges from a distribution that is pointwise $ε$-close to the uniform distribution, in an \emph{amortized-efficient} fashion. We consider the adjacency list query model, where access to a graph $G$ is given via degree and neighbor queries. The problem of sampling a single edge in this model has been raised by Eden and Rosenbaum (SOSA 18). Let $n$ and $m$ denote the number of vertices and edges of $G$, respectively. Eden and Rosenbaum provided upper and lower bounds of $Θ^*(n/\sqrt m)$ for sampling a single edge in general graphs (where $O^*(\cdot)$ suppresses $\textrm{poly}(1/ε)$ and $\textrm{poly}(\log n)$ dependencies). We ask whether the query complexity lower bound for sampling a single edge can be circumvented when multiple samples are required. That is, can we get an improved amortized per-sample cost if we allow a preprocessing phase? We answer in the affirmative. We present an algorithm that, if one knows the number of required samples $q$ in advance, has an overall cost that is sublinear in $q$, namely, $O^*(\sqrt q \cdot(n/\sqrt m))$, which is strictly preferable to $O^*(q\cdot (n/\sqrt m))$ cost resulting from $q$ invocations of the algorithm by Eden and Rosenbaum. Subsequent to a preliminary version of this work, Tětek and Thorup (arXiv, preprint) proved that this bound is essentially optimal.
Stable Matchings with Restricted Preferences: Structure and Complexity
Venue: arXiv cs.DM 2021
Year: 2021

It is well known that every stable matching instance $I$ has a rotation poset $R(I)$ that can be computed efficiently and the downsets of $R(I)$ are in one-to-one correspondence with the stable matchings of $I$. Furthermore, for every poset $P$, an instance $I(P)$ can be constructed efficiently so that the rotation poset of $I(P)$ is isomorphic to $P$. In this case, we say that $I(P)$ realizes $P$. Many researchers exploit the rotation poset of an instance to develop fast algorithms or to establish the hardness of stable matching problems. In order to gain a parameterized understanding of the complexity of sampling stable matchings, Bhatnagar et al. [SODA 2008] introduced stable matching instances whose preference lists are restricted but nevertheless model situations that arise in practice. In this paper, we study four such parameterized restrictions; our goal is to characterize the rotation posets that arise from these models: $k$-bounded, $k$-attribute, $(k_1, k_2)$-list, $k$-range. We prove that there is a constant $k$ so that every rotation poset is realized by some instance in the first three models for some fixed constant $k$. We describe efficient algorithms for constructing such instances given the Hasse diagram of a poset. As a consequence, the fundamental problem of counting stable matchings remains $\#$BIS-complete even for these restricted instances. For $k$-range preferences, we show that a poset $P$ is realizable if and only if the Hasse diagram of $P$ has pathwidth bounded by functions of $k$. Using this characterization, we show that the following problems are fixed parameter tractable when parametrized by the range of the instance: exactly counting and uniformly sampling stable matchings, finding median, sex-equal, and balanced stable matchings.
Analog Lagrange Coded Computing
Venue: arXiv cs.IT 2021
Year: 2021

A distributed computing scenario is considered, where the computational power of a set of worker nodes is used to perform a certain computation task over a dataset that is dispersed among the workers. Lagrange coded computing (LCC), proposed by Yu et al., leverages the well-known Lagrange polynomial to perform polynomial evaluation of the dataset in such a scenario in an efficient parallel fashion while keeping the privacy of data amidst possible collusion of workers. This solution relies on quantizing the data into a finite field, so that Shamir's secret sharing, as one of its main building blocks, can be employed. Such a solution, however, is not properly scalable with the size of dataset, mainly due to computation overflows. To address such a critical issue, we propose a novel extension of LCC to the analog domain, referred to as analog LCC (ALCC). All the operations in the proposed ALCC protocol are done over the infinite fields of R/C but for practical implementations floating-point numbers are used. We characterize the privacy of data in ALCC, against any subset of colluding workers up to a certain size, in terms of the distinguishing security (DS) and the mutual information security (MIS) metrics. Also, the accuracy of outcome is characterized in a practical setting assuming operations are performed using floating-point numbers. Consequently, a fundamental trade-off between the accuracy of the outcome of ALCC and its privacy level is observed and is numerically evaluated. Moreover, we implement the proposed scheme to perform matrix-matrix multiplication over a batch of matrices. It is observed that ALCC is superior compared to the state-of-the-art LCC, implemented using fixed-point numbers, assuming both schemes use an equal number of bits to represent data symbols.
A Computational-Graph Partitioning Method for Training Memory-Constrained DNNs
Venue: arXiv cs.DC 2021
Year: 2021

Many state-of-the-art Deep Neural Networks (DNNs) have substantial memory requirements. Limited device memory becomes a bottleneck when training those models. We propose ParDNN, an automatic, generic, and non-intrusive partitioning strategy for DNNs that are represented as computational graphs. ParDNN decides a placement of DNN's underlying computational graph operations across multiple devices so that the devices' memory constraints are met and the training time is minimized. ParDNN is completely independent of the deep learning aspects of a DNN. It requires no modification neither at the model nor at the systems level implementation of its operation kernels. ParDNN partitions DNNs having billions of parameters and hundreds of thousands of operations in seconds to few minutes. Our experiments with TensorFlow on 16 GPUs demonstrate efficient training of 5 very large models while achieving superlinear scaling for both the batch size and training throughput. ParDNN either outperforms or qualitatively improves upon the related work.
BGC: Multi-Agent Group Belief with Graph Clustering
Venue: arXiv cs.AI 2021
Year: 2021

Recent advances have witnessed that value decomposed-based multi-agent reinforcement learning methods make an efficient performance in coordination tasks. Most current methods assume that agents can make communication to assist decisions, which is impractical in some situations. In this paper, we propose a semi-communication method to enable agents can exchange information without communication. Specifically, we introduce a group concept to help agents learning a belief which is a type of consensus. With this consensus, adjacent agents tend to accomplish similar sub-tasks to achieve cooperation. We design a novel agent structure named Belief in Graph Clustering(BGC), composed of an agent characteristic module, a belief module, and a fusion module. To represent each agent characteristic, we use an MLP-based characteristic module to generate agent unique features. Inspired by the neighborhood cognitive consistency, we propose a group-based module to divide adjacent agents into a small group and minimize in-group agents' beliefs to accomplish similar sub-tasks. Finally, we use a hyper-network to merge these features and produce agent actions. To overcome the agent consistent problem brought by GAT, a split loss is introduced to distinguish different agents. Results reveal that the proposed method achieves a significant improvement in the SMAC benchmark. Because of the group concept, our approach maintains excellent performance with an increase in the number of agents.
Fair and consistent prize allocation in competitions
Venue: arXiv cs.GT 2021
Year: 2021

Given the final ranking of a competition, how should the total prize endowment be allocated among the competitors? We study consistent prize allocation rules satisfying elementary solidarity and fairness principles. In particular, we axiomatically characterize several families of rules satisfying anonymity, order preservation, and endowment monotonicity, which all fall between the Equal Division rule and the Winner-Takes-All rule. Specific characterizations of rules and subfamilies are directly obtained. To our knowledge, this paper is the first that develops and motivates prize allocation rules for rank-order competitions directly from axioms.