OpenRaiser/Intern-Atlas huggingface dataset:
On the fair division of a random object
Venue: arXiv cs.GT 2021
Year: 2021

Ann likes oranges much more than apples; Bob likes apples much more than oranges. Tomorrow they will receive one fruit that will be an orange or an apple with equal probability. Giving one half to each agent is fair for each realization of the fruit. However, agreeing that whatever fruit appears will go to the agent who likes it more gives a higher expected utility to each agent and is fair in the average sense: in expectation, each agent prefers his allocation to the equal division of the fruit, i.e., he gets a fair share. We turn this familiar observation into an economic design problem: upon drawing a random object (the fruit), we learn the realized utility of each agent and can compare it to the mean of his distribution of utilities; no other statistical information about the distribution is available. We fully characterize the division rules using only this sparse information in the most efficient possible way, while giving everyone a fair share. Although the probability distribution of individual utilities is arbitrary and mostly unknown to the manager, these rules perform in the same range as the best rule when the manager has full access to this distribution.
A lightweight BFT consensus protocol for blockchains
Venue: arXiv cs.DC 2021
Year: 2021

We present a general consensus framework that allows to easily introduce a customizable Byzantine fault tolerant consensus algorithm to an existing (Delegated) Proof-of-Stake blockchain. We prove the safety of the protocol under the assumption that less than 1/3 of the validators are Byzantine. The framework further allows for consensus participants to choose subjective decision thresholds in order to obtain safety even in the case of a larger proportion of Byzantine validators. Moreover, the liveness of the protocol is shown if less than 1/3 of the validators crash. Based on the framework, we introduce Lisk-BFT, a Byzantine fault tolerant consensus algorithm for the Lisk ecosystem. Lisk-BFT integrates with the existing block proposal mechanism, requires only two additional integers in blocks and no additional messages. The protocol is simple and provides safety in the case of static validators if less than 1/3 of the validators are Byzantine. For the case of dynamically changing validators, we prove the safety of the protocol assuming a bound on the number of Byzantine validators and the number of honest validators that can change at one time. We further show the liveness of the Lisk-BFT protocol for less than 1/3 crashing validators.
Rallying Adversarial Techniques against Deep Learning for Network Security
Venue: arXiv cs.CR 2021
Year: 2021

Recent advances in artificial intelligence and the increasing need for powerful defensive measures in the domain of network security, have led to the adoption of deep learning approaches for use in network intrusion detection systems. These methods have achieved superior performance against conventional network attacks, which enable the deployment of practical security systems to unique and dynamic sectors. Adversarial machine learning, unfortunately, has recently shown that deep learning models are inherently vulnerable to adversarial modifications on their input data. Because of this susceptibility, the deep learning models deployed to power a network defense could in fact be the weakest entry point for compromising a network system. In this paper, we show that by modifying on average as little as 1.38 of the input features, an adversary can generate malicious inputs which effectively fool a deep learning based NIDS. Therefore, when designing such systems, it is crucial to consider the performance from not only the conventional network security perspective but also the adversarial machine learning domain.
An LBP-HOG Descriptor Based on Matrix Projection For Mammogram Classification
Venue: arXiv cs.CV 2021
Year: 2021

In image based feature descriptor design, local information from image patches are extracted using iterative scanning operations which cause high computational costs. In order to avoid such scanning operations, we present matrix multiplication based local feature descriptors, namely a Matrix projection based Local Binary Pattern (M-LBP) descriptor and a Matrix projection based Histogram of Oriented Gradients (M-HOG) descriptor. Additionally, an integrated formulation of M-LBP and M-HOG (M-LBP-HOG) is also proposed to perform the two descriptors together in a single step. The proposed descriptors are evaluated using a publicly available mammogram database. The results show promising performances in terms of classification accuracy and computational efficiency.
Capacity of Generalized Discrete-Memoryless Push-to-Talk Two-Way Channels
Venue: arXiv cs.IT 2021
Year: 2021

In this report, we generalize Shannon's push-to-talk two-way channel (PTT-TWC) by allowing reliable full-duplex transmission as well as noisy reception in the half-duplex (PTT) mode. Viewing a PTT-TWC as two state-dependent one-way channels, we introduce a channel symmetry property pertaining to the one-way channels. Shannon's TWC capacity inner bound is shown to be tight for the generalized model under this symmetry property. We also analytically derive the capacity region, which is shown to be the convex hull of (at most) 4 rate pairs. Examples that illustrate different shapes of the capacity region are given, and efficient transmission schemes are discussed via the examples.
TightCap: 3D Human Shape Capture with Clothing Tightness Field
Venue: arXiv cs.CV 2021
Year: 2021

In this paper, we present TightCap, a data-driven scheme to capture both the human shape and dressed garments accurately with only a single 3D human scan, which enables numerous applications such as virtual try-on, biometrics and body evaluation. To break the severe variations of the human poses and garments, we propose to model the clothing tightness - the displacements from the garments to the human shape implicitly in the global UV texturing domain. To this end, we utilize an enhanced statistical human template and an effective multi-stage alignment scheme to map the 3D scan into a hybrid 2D geometry image. Based on this 2D representation, we propose a novel framework to predicted clothing tightness via a novel tightness formulation, as well as an effective optimization scheme to further reconstruct multi-layer human shape and garments under various clothing categories and human postures. We further propose a new clothing tightness dataset (CTD) of human scans with a large variety of clothing styles, poses and corresponding ground-truth human shapes to stimulate further research. Extensive experiments demonstrate the effectiveness of our TightCap to achieve high-quality human shape and dressed garments reconstruction, as well as the further applications for clothing segmentation, retargeting and animation.
Fast Weakly Supervised Action Segmentation Using Mutual Consistency
Venue: arXiv cs.CV 2021
Year: 2021

Action segmentation is the task of predicting the actions for each frame of a video. As obtaining the full annotation of videos for action segmentation is expensive, weakly supervised approaches that can learn only from transcripts are appealing. In this paper, we propose a novel end-to-end approach for weakly supervised action segmentation based on a two-branch neural network. The two branches of our network predict two redundant but different representations for action segmentation and we propose a novel mutual consistency (MuCon) loss that enforces the consistency of the two redundant representations. Using the MuCon loss together with a loss for transcript prediction, our proposed approach achieves the accuracy of state-of-the-art approaches while being $14$ times faster to train and $20$ times faster during inference. The MuCon loss proves beneficial even in the fully supervised setting.
A Novel Neural Network-Based Symbolic Regression Method: Neuro-Encoded Expression Programming
Venue: arXiv cs.NE 2021
Year: 2021

Neuro-encoded expression programming(NEEP) that aims to offer a novel continuous representation of combinatorial encoding for genetic programming methods is proposed in this paper. Genetic programming with linear representation uses nature-inspired operators (e.g., crossover, mutation) to tune expressions and finally search out the best explicit function to simulate data. The encoding mechanism is essential for genetic programmings to find a desirable solution efficiently. However, the linear representation methods manipulate the expression tree in discrete solution space, where a small change of the input can cause a large change of the output. The unsmooth landscapes destroy the local information and make difficulty in searching. The neuro-encoded expression programming constructs the gene string with recurrent neural network (RNN) and the weights of the network are optimized by powerful continuous evolutionary algorithms. The neural network mappings smoothen the sharp fitness landscape and provide rich neighborhood information to find the best expression. The experiments indicate that the novel approach improves training efficiency and reduces test errors on several well-known symbolic regression problems.
Generic Variance Bounds on Estimation and Prediction Errors in Time Series Analysis: An Entropy Perspective
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we obtain generic bounds on the variances of estimation and prediction errors in time series analysis via an information-theoretic approach. It is seen in general that the error bounds are determined by the conditional entropy of the data point to be estimated or predicted given the side information or past observations. Additionally, we discover that in order to achieve the prediction error bounds asymptotically, the necessary and sufficient condition is that the "innovation" is asymptotically white Gaussian. When restricted to Gaussian processes and 1-step prediction, our bounds are shown to reduce to the Kolmogorov-Szegö formula and Wiener-Masani formula known from linear prediction theory.
Relative-perfectness of discrete gradient vector fields and multi-parameter persistent homology
Venue: arXiv cs.CG 2021
Year: 2021

The combination of persistent homology and discrete Morse theory has proven very effective in visualizing and analyzing big and heterogeneous data. Indeed, topology provides computable and coarse summaries of data independently from specific coordinate systems and does so robustly to noise. Moreover, the geometric content of a discrete gradient vector field is very useful for visualization purposes. The specific case of multivariate data still demands for further investigations, on the one hand, for computational reasons, it is important to reduce the necessary amount of data to be processed. On the other hand, for analysis reasons, the multivariate case requires the detection and interpretation of the possible interdepedance among data components. To this end, in this paper we introduce and study a notion of perfectness for discrete gradient vector fields with respect to multi-parameter persistent homology, called relative-perfectness. As a natural generalization of usual perfectness in Morse theory for homology, relative-perfectness entails having the least number of critical cells relevant for multi-parameter persistence. As a first contribution, we support our definition of relative-perfectness by generalizing Morse inequalities to the filtration structure where homology groups involved are relative with respect to subsequent sublevel sets. In order to allow for an interpretation of critical cells in $2$-parameter persistence, our second contribution consists of two inequalities bounding Betti tables of persistence modules from above and below, via the number of critical cells. Our last result is the proof that existing algorithms based on local homotopy expansions allow for efficient computability over simplicial complexes up to dimension $2$.
Predicative proof theory of PDL and basic applications
Venue: arXiv cs.LO 2021
Year: 2021

Propositional dynamic logic (PDL) is presented in Schütte-style mode as one-sided semiformal tree-like sequent calculus Seq$_ω^{\text{pdl}}$ with standard cut rule and the omega-rule with principal formulas $\left[ P^{\ast }\right] \!A$. The omega-rule-free derivations in Seq$_{ω}^{\text{pdl}}$ are finite (trees) and sequents deducible by these finite derivations are valid in PDL. Moreover the cut-elimination theorem for Seq$_ω^{\text{pdl}}$ is provable in Peano Arithmetic (PA)extended by transfinite induction up to Veblen's ordinal $φ_ω\left( 0\right) $. Hence (by the cutfree subformula property) such predicative extension of PA proves that any given $\left[ P^{\ast }\right] $-free sequent is valid in PDL iff it is deducible in Seq$_ω^{\text{pdl}}$ by a finite cut- and omega-rule-free derivation, while PDL-validity of arbitrary star-free sequents is decidable in polynomial space. The former also implies standard Herbrand-style conclusions, which eventually leads to PSPACE-decidability of PDL-validity of $S$, provided that $P$ is atomic and $A$ is in a suitable \emph{basic conjunctive normal form}. Furthermore we consider star-free formulas $A$ in dual \emph{basic disjunctive normal form}, and corresponding expansions $S=\left\langle P^{\ast }\right\rangle \!A\vee Z$ whose PDL-validity problem is known to be EXPTIME-complete. We show that cutfree-derivability in Seq$_ω^{\text{pdl}}$ (hence PDL-validity) of such $S$\ is equivalent to plain validity of a suitable "transparent" quantified boolean formula $\widehat{S}$. The whole proof can be formalized in PA extended by transfinite induction along $φ_ω\left( 0\right)$ -- actually in the corresponding primitive recursive weakening, $\mathbf{PRA}_{φ_{ω}\left( 0\right)}$.
Joint Discriminative and Generative Learning for Person Re-identification
Venue: arXiv cs.CV 2021
Year: 2021

Person re-identification (re-id) remains challenging due to significant intra-class variations across different cameras. Recently, there has been a growing interest in using generative models to augment training data and enhance the invariance to input changes. The generative pipelines in existing methods, however, stay relatively separate from the discriminative re-id learning stages. Accordingly, re-id models are often trained in a straightforward manner on the generated data. In this paper, we seek to improve learned re-id embeddings by better leveraging the generated data. To this end, we propose a joint learning framework that couples re-id learning and data generation end-to-end. Our model involves a generative module that separately encodes each person into an appearance code and a structure code, and a discriminative module that shares the appearance encoder with the generative module. By switching the appearance or structure codes, the generative module is able to generate high-quality cross-id composed images, which are online fed back to the appearance encoder and used to improve the discriminative module. The proposed joint learning framework renders significant improvement over the baseline without using generated data, leading to the state-of-the-art performance on several benchmark datasets.
Long-Term Human Video Generation of Multiple Futures Using Poses
Venue: arXiv cs.CV 2021
Year: 2021

Predicting future human behavior from an input human video is a useful task for applications such as autonomous driving and robotics. While most previous works predict a single future, multiple futures with different behavior can potentially occur. Moreover, if the predicted future is too short (e.g., less than one second), it may not be fully usable by a human or other systems. In this paper, we propose a novel method for future human pose prediction capable of predicting multiple long-term futures. This makes the predictions more suitable for real applications. Also, from the input video and the predicted human behavior, we generate future videos. First, from an input human video, we generate sequences of future human poses (i.e., the image coordinates of their body-joints) via adversarial learning. Adversarial learning suffers from mode collapse, which makes it difficult to generate a variety of multiple poses. We solve this problem by utilizing two additional inputs to the generator to make the outputs diverse, namely, a latent code (to reflect various behaviors) and an attraction point (to reflect various trajectories). In addition, we generate long-term future human poses using a novel approach based on unidimensional convolutional neural networks. Last, we generate an output video based on the generated poses for visualization. We evaluate the generated future poses and videos using three criteria (i.e., realism, diversity and accuracy), and show that our proposed method outperforms other state-of-the-art works.
General Purpose (GenP) Bioimage Ensemble of Handcrafted and Learned Features with Data Augmentation
Venue: arXiv cs.CV 2021
Year: 2021

Bioimage classification plays a crucial role in many biological problems. In this work, we present a new General Purpose (GenP) ensemble that boosts performance by combining local features, dense sampling features, and deep learning approaches. First, we introduce three new methods for data augmentation based on PCA/DCT; second, we show that different data augmentation approaches can boost the performance of an ensemble of CNNs; and, finally, we propose a set of handcrafted/learned descriptors that are highly generalizable. Each handcrafted descriptor is used to train a different Support Vector Machine (SVM), and the different SVMs are combined with the ensemble of CNNs. Our method is evaluated on a diverse set of bioimage classification problems. Results demonstrate that the proposed GenP bioimage ensemble obtains state-of-the-art performance without any ad-hoc dataset tuning of parameters (thus avoiding the risk of overfitting/overtraining).
Parametric updates in parametric timed automata
Venue: arXiv cs.FL 2021
Year: 2021

We introduce a new class of Parametric Timed Automata (PTAs) where we allow clocks to be compared to parameters in guards, as in classic PTAs, but also to be updated to parameters. We focus here on the EF-emptiness problem: "is the set of parameter valuations for which some given location is reachable in the instantiated timed automaton empty?". This problem is well-known to be undecidable for PTAs, and so it is for our extension. Nonetheless, if we update all clocks each time we compare a clock with a parameter and each time we update a clock to a parameter, we obtain a syntactic subclass for which we can decide the EF-emptiness problem and even perform the exact synthesis of the set of rational valuations such that a given location is reachable. To the best of our knowledge, this is the first non-trivial subclass of PTAs, actually even extended with parametric updates, for which this is possible.
Constrained Restless Bandits for Dynamic Scheduling in Cyber-Physical Systems
Venue: arXiv cs.SY 2021
Year: 2021

This paper studies a class of constrained restless multi-armed bandits (CRMAB). The constraints are in the form of time varying set of actions (set of available arms). This variation can be either stochastic or semi-deterministic. Given a set of arms, a fixed number of them can be chosen to be played in each decision interval. The play of each arm yields a state dependent reward. The current states of arms are partially observable through binary feedback signals from arms that are played. The current availability of arms is fully observable. The objective is to maximize long term cumulative reward. The uncertainty about future availability of arms along with partial state information makes this objective challenging. Applications for CRMAB can be found in resource allocation in cyber-physical systems involving components with time varying availability. First, this optimization problem is analyzed using Whittle's index policy. To this end, a constrained restless single-armed bandit is studied. It is shown to admit a threshold-type optimal policy and is also indexable. An algorithm to compute Whittle's index is presented. An alternate solution method with lower complexity is also presented in the form of an online rollout policy. A detailed discussion on the complexity of both these schemes is also presented, which suggests that online rollout policy with short look ahead is simpler to implement than Whittle's index computation. Further, upper bounds on the value function are derived in order to estimate the degree of sub-optimality of various solutions. The simulation study compares the performance of Whittle's index, online rollout, myopic and modified Whittle's index policies.
Uncertainty about Uncertainty: Optimal Adaptive Algorithms for Estimating Mixtures of Unknown Coins
Venue: arXiv cs.LG 2021
Year: 2021

Given a mixture between two populations of coins, "positive" coins that each have -- unknown and potentially different -- bias $\geq\frac{1}{2}+Δ$ and "negative" coins with bias $\leq\frac{1}{2}-Δ$, we consider the task of estimating the fraction $ρ$ of positive coins to within additive error $ε$. We achieve an upper and lower bound of $Θ(\fracρ{ε^2Δ^2}\log\frac{1}δ)$ samples for a $1-δ$ probability of success, where crucially, our lower bound applies to all fully-adaptive algorithms. Thus, our sample complexity bounds have tight dependence for every relevant problem parameter. A crucial component of our lower bound proof is a decomposition lemma (see Lemmas 17 and 18) showing how to assemble partially-adaptive bounds into a fully-adaptive bound, which may be of independent interest: though we invoke it for the special case of Bernoulli random variables (coins), it applies to general distributions. We present simulation results to demonstrate the practical efficacy of our approach for realistic problem parameters for crowdsourcing applications, focusing on the "rare events" regime where $ρ$ is small. The fine-grained adaptive flavor of both our algorithm and lower bound contrasts with much previous work in distributional testing and learning.
Bayesian Search for Robust Optima
Venue: arXiv cs.LG 2021
Year: 2021

Many expensive black-box optimisation problems are sensitive to their inputs. In these problems it makes more sense to locate a region of good designs, than a single-possibly fragile-optimal design. Expensive black-box functions can be optimised effectively with Bayesian optimisation, where a Gaussian process is a popular choice as a prior over the expensive function. We propose a method for robust optimisation using Bayesian optimisation to find a region of design space in which the expensive function's performance is relatively insensitive to the inputs whilst retaining a good quality. This is achieved by sampling realisations from a Gaussian process that is modelling the expensive function, and evaluating the improvement for each realisation. The expectation of these improvements can be optimised cheaply with an evolutionary algorithm to determine the next location at which to evaluate the expensive function. We describe an efficient process to locate the optimum expected improvement. We show empirically that evaluating the expensive function at the location in the candidate uncertainty region about which the model is most uncertain, or at random, yield the best convergence in contrast to exploitative schemes. We illustrate our method on six test functions in two, five, and ten dimensions, and demonstrate that it is able to outperform two state-of-the-art approaches from the literature. We also demonstrate our method one two real-world problems in 4 and 8 dimensions, which involve training robot arms to push objects onto targets.