OpenRaiser/Intern-Atlas huggingface dataset:
Attention-based Few-Shot Person Re-identification Using Meta Learning
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we investigate the challenging task of person re-identification from a new perspective and propose an end-to-end attention-based architecture for few-shot re-identification through meta-learning. The motivation for this task lies in the fact that humans, can usually identify another person after just seeing that given person a few times (or even once) by attending to their memory. On the other hand, the unique nature of the person re-identification problem, i.e., only few examples exist per identity and new identities always appearing during testing, calls for a few shot learning architecture with the capacity of handling new identities. Hence, we frame the problem within a meta-learning setting, where a neural network based meta-learner is trained to optimize a learner i.e., an attention-based matching function. Another challenge of the person re-identification problem is the small inter-class difference between different identities and large intra-class difference of the same identity. In order to increase the discriminative power of the model, we propose a new attention-based feature encoding scheme that takes into account the critical intra-view and cross-view relationship of images. We refer to the proposed Attention-based Re-identification Metalearning model as ARM. Extensive evaluations demonstrate the advantages of the ARM as compared to the state-of-the-art on the challenging PRID2011, CUHK01, CUHK03 and Market1501 datasets.
Quantifier Elimination for Database Driven Verification
Venue: arXiv cs.LO 2019
Year: 2019

Running verification tasks in database driven systems requires solving quantifier elimination problems of a new kind. These quantifier elimination problems are related to the notion of a cover introduced in ESOP 2008 by Gulwani and Musuvathi. In this paper, we show how covers are strictly related to model completions, a well-known topic in model theory. We also investigate the computation of covers within the Superposition Calculus, by adopting a constrained version of the calculus, equipped with appropriate settings and reduction strategies. In addition, we show that cover computations are computationally tractable for the fragment of the language used in applications to database driven verification. This observation is confirmed by analyzing the preliminary results obtained using the MCMT tool on the verification of data-aware process benchmarks. These benchmarks can be found in the last version of the tool distribution.
Unsupervised Learning by Competing Hidden Units
Venue: arXiv cs.LG 2019
Year: 2019

It is widely believed that the backpropagation algorithm is essential for learning good feature detectors in early layers of artificial neural networks, so that these detectors are useful for the task performed by the higher layers of that neural network. At the same time, the traditional form of backpropagation is biologically implausible. In the present paper we propose an unusual learning rule, which has a degree of biological plausibility, and which is motivated by Hebb's idea that change of the synapse strength should be local - i.e. should depend only on the activities of the pre and post synaptic neurons. We design a learning algorithm that utilizes global inhibition in the hidden layer, and is capable of learning early feature detectors in a completely unsupervised way. These learned lower layer feature detectors can be used to train higher layer weights in a usual supervised way so that the performance of the full network is comparable to the performance of standard feedforward networks trained end-to-end with a backpropagation algorithm.
A Game-Semantic Model of Computation, Revisited: an Automata-Theoretic Perspective
Venue: arXiv cs.LO 2019
Year: 2019

In the previous work, we have given a novel, game-semantic model of computation in an intrinsic, non-inductive and non-axiomatic manner, which is similar to Turing machines but beyond computation on natural numbers, e.g., higher-order computation. As the main theorem of the work, it has been shown that the game-semantic model may execute all the computation of the programming language PCF. The present paper revisits this result from an automata-theoretic perspective: It shows that deterministic non-erasing pushdown automata whose input tape is equipped with simple directed edges between cells can implement all the game-semantic PCF-computation, where the edges rather restrict the cells of the tape which the automata may read off. This is a mathematically highly-surprising phenomenon because it is well-known that the more powerful non-deterministic erasing pushdown automata are strictly weaker than Turing machines (in the Chomsky hierarchy), let alone than PCF.
An Optimal Experimental Design Framework for Adaptive Inflation and Covariance Localization for Ensemble Filters
Venue: arXiv cs.CE 2019
Year: 2019

We develop an optimal experimental design framework for adapting the covariance inflation and localization in data assimilation problems. Covariance inflation and localization are ubiquitously employed to alleviate the effect of using ensembles of finite sizes in all practical data assimilation systems. The choice of both the inflation factor and the localization radius can have a significant impact on the performance of the assimilation scheme. These parameters are generally tuned by trial and error, rendering them expensive to optimize in practice. Spatially and temporally varying inflation parameter and localization radii have been recently proposed and have been empirically proven to enhance the performance of the employed assimilation filter. In this study, we present a variational framework for adaptive tuning of the inflation and localization parameters. Each of these parameters is optimized independently, with an objective to minimize the uncertainty in the posterior state. The proposed framework does not assume uncorrelated observations or prior errors and can in principle be applied without expert knowledge about the model and the observations. Thus, it is adequate for handling dense as well as sparse observational networks. We present the mathematical formulation, algorithmic description of the approach, and numerical experiments using the two-layer Lorenz-96 model.
Graphs without a partition into two proportionally dense subgraphs
Venue: arXiv cs.DM 2019
Year: 2019

A \emph{proportionally dense subgraph} (PDS) is an induced subgraph of a graph with the property that each vertex in the PDS is adjacent to proportionally as many vertices in the subgraph as in the rest of the graph. In this paper, we study a partition of a graph into two proportionally dense subgraphs, namely a \emph{$2$-PDS partition}. The question whether all graphs (except stars) have $2$-PDS partition was left open in [Bazgan et al., Algorithmica 80(6) (2018), 1890--1908]. We give a negative answer on that question and present a class of graphs without a $2$-PDS partition.
Spark-Based Anomaly Detection: the Case of Port and Net Scan
Venue: arXiv cs.NI 2019
Year: 2019

The two most spread network anomalies are port and net scan. In this work, we present and analyze the results obtained by traditional approaches for the detection of net scan and port scans. We use a simple threshold-based algorithm, working at flow-level and adapt it for the execution on Apache Spark. The use of Big Data Analytics technologies allows to significantly the execution times of the algorithm so to be used even in current, high-speed networks. The paper describes our approach and presents an experimental analysis in terms of detection performance and execution time. We use real traffic traces from MAWI archive and MAWILab anomaly detectors to compare with our results. The analysis shows that i) our traditional threshold-based algorithm is already able to achieve detection performance higher than MAWILab (in 95% of the considered cases with the best threshold value), currently considered the gold standard in the field; ii) the execution time is much shorter than the trace time, which makes it usable also in real time. Moreover, for each traffic trace we provide the research community with a new labeled dataset, validated by comparisons with MAWILab and extended with other anomalies not detected by it. We publish an updated dataset every day at our project website.
The Sphere Packing Bound for DSPCs with Feedback a la Augustin
Venue: arXiv cs.IT 2019
Year: 2019

Establishing the sphere packing bound for block codes on the discrete stationary product channels with feedback ---which are commonly called the discrete memoryless channels with feedback--- was considered to be an open problem until recently, notwithstanding the proof sketch provided by Augustin in 1978. A complete proof following Augustin's proof sketch is presented, to demonstrate its adequacy and to draw attention to two novel ideas it employs. These novel ideas (i.e., the Augustin's averaging and the use of subblocks) are likely to be applicable in other communication problems for establishing impossibility results.
Policy Optimization With Penalized Point Probability Distance: An Alternative To Proximal Policy Optimization
Venue: arXiv cs.LG 2019
Year: 2019

As the most successful variant and improvement for Trust Region Policy Optimization (TRPO), proximal policy optimization (PPO) has been widely applied across various domains with several advantages: efficient data utilization, easy implementation, and good parallelism. In this paper, a first-order gradient reinforcement learning algorithm called Policy Optimization with Penalized Point Probability Distance (POP3D), which is a lower bound to the square of total variance divergence is proposed as another powerful variant. Firstly, we talk about the shortcomings of several commonly used algorithms, by which our method is partly motivated. Secondly, we address to overcome these shortcomings by applying POP3D. Thirdly, we dive into its mechanism from the perspective of solution manifold. Finally, we make quantitative comparisons among several state-of-the-art algorithms based on common benchmarks. Simulation results show that POP3D is highly competitive compared with PPO. Besides, our code is released in https://github.com/paperwithcode/pop3d.
BesFS: A POSIX Filesystem for Enclaves with a Mechanized Safety Proof
Venue: arXiv cs.CR 2019
Year: 2019

New trusted computing primitives such as Intel SGX have shown the feasibility of running user-level applications in enclaves on a commodity trusted processor without trusting a large OS. However, the OS can still compromise the integrity of an enclave by tampering with the system call return values. In fact, it has been shown that a subclass of these attacks, called Iago attacks, enables arbitrary logic execution in enclave programs. Existing enclave systems have very large TCB and they implement ad-hoc checks at the system call interface which are hard to verify for completeness. To this end, we present BesFS--the first filesystem interface which provably protects the enclave integrity against a completely malicious OS. We prove 167 lemmas and 2 key theorems in 4625 lines of Coq proof scripts, which directly proves the safety properties of the BesFS specification. BesFS comprises of 15 APIs with compositional safety and is expressive enough to support 31 real applications we test. BesFS integrates into existing SGX-enabled applications with minimal impact to TCB. BesFS can serve as a reference implementation for hand-coded API checks.
Personalized Radiotherapy Design for Glioblastoma: Integrating Mathematical Tumor Models, Multimodal Scans and Bayesian Inference
Venue: arXiv cs.CE 2019
Year: 2019

Glioblastoma is a highly invasive brain tumor, whose cells infiltrate surrounding normal brain tissue beyond the lesion outlines visible in the current medical scans. These infiltrative cells are treated mainly by radiotherapy. Existing radiotherapy plans for brain tumors derive from population studies and scarcely account for patient-specific conditions. Here we provide a Bayesian machine learning framework for the rational design of improved, personalized radiotherapy plans using mathematical modeling and patient multimodal medical scans. Our method, for the first time, integrates complementary information from high resolution MRI scans and highly specific FET-PET metabolic maps to infer tumor cell density in glioblastoma patients. The Bayesian framework quantifies imaging and modeling uncertainties and predicts patient-specific tumor cell density with confidence intervals. The proposed methodology relies only on data acquired at a single time point and thus is applicable to standard clinical settings. An initial clinical population study shows that the radiotherapy plans generated from the inferred tumor cell infiltration maps spare more healthy tissue thereby reducing radiation toxicity while yielding comparable accuracy with standard radiotherapy protocols. Moreover, the inferred regions of high tumor cell densities coincide with the tumor radioresistant areas, providing guidance for personalized dose-escalation. The proposed integration of multimodal scans and mathematical modeling provides a robust, non-invasive tool to assist personalized radiotherapy design.
Gaussian Signalling for Covert Communications
Venue: arXiv cs.IT 2019
Year: 2019

In this work, we examine the optimality of Gaussian signalling for covert communications with an upper bound on $\mathcal{D}(p_{_1}||p_{_0})$ or $\mathcal{D}(p_{_0}||p_{_1})$ as the covertness constraint, where $\mathcal{D}(p_{_1}||p_{_0})$ and $\mathcal{D}(p_{_0}||p_{_1})$ are different due to the asymmetry of Kullback-Leibler divergence, $p_{_0}(y)$ and $p_{_1}(y)$ are the likelihood functions of the observation ${y}$ at the warden under the null hypothesis (no covert transmission) and alternative hypothesis (a covert transmission occurs), respectively. Considering additive white Gaussian noise at both the receiver and the warden, we prove that Gaussian signalling is optimal in terms of maximizing the mutual information of transmitted and received signals for covert communications with an upper bound on $\mathcal{D}(p_{_1}||p_{_0})$ as the constraint. More interestingly, we also prove that Gaussian signalling is not optimal for covert communications with an upper bound on $\mathcal{D}(p_{_0}||p_{_1})$ as the constraint, for which as we explicitly show skew-normal signalling can outperform Gaussian signalling in terms of achieving higher mutual information. Finally, we prove that, for Gaussian signalling, an upper bound on $\mathcal{D}(p_{_1}||p_{_0})$ is a tighter covertness constraint in terms of leading to lower mutual information than the same upper bound on $\mathcal{D}(p_{_0}||p_{_1})$, by proving $\mathcal{D}(p_{_0}||p_{_1}) \leq \mathcal{D}(p_{_1}||p_{_0})$.
Topic Discovery in Massive Text Corpora Based on Min-Hashing
Venue: arXiv cs.CL 2019
Year: 2019

The task of discovering topics in text corpora has been dominated by Latent Dirichlet Allocation and other Topic Models for over a decade. In order to apply these approaches to massive text corpora, the vocabulary needs to be reduced considerably and large computer clusters and/or GPUs are typically required. Moreover, the number of topics must be provided beforehand but this depends on the corpus characteristics and it is often difficult to estimate, especially for massive text corpora. Unfortunately, both topic quality and time complexity are sensitive to this choice. This paper describes an alternative approach to discover topics based on Min-Hashing, which can handle massive text corpora and large vocabularies using modest computer hardware and does not require to fix the number of topics in advance. The basic idea is to generate multiple random partitions of the corpus vocabulary to find sets of highly co-occurring words, which are then clustered to produce the final topics. In contrast to probabilistic topic models where topics are distributions over the complete vocabulary, the topics discovered by the proposed approach are sets of highly co-occurring words. Interestingly, these topics underlie various thematics with different levels of granularity. An extensive qualitative and quantitative evaluation using the 20 Newsgroups (18K), Reuters (800K), Spanish Wikipedia (1M), and English Wikipedia (5M) corpora shows that the proposed approach is able to consistently discover meaningful and coherent topics. Remarkably, the time complexity of the proposed approach is linear with respect to corpus and vocabulary size; a non-parallel implementation was able to discover topics from the entire English edition of Wikipedia with over 5 million documents and 1 million words in less than 7 hours.
Weakly Supervised Deep Recurrent Neural Networks for Basic Dance Step Generation
Venue: arXiv cs.LG 2019
Year: 2019

Synthesizing human's movements such as dancing is a flourishing research field which has several applications in computer graphics. Recent studies have demonstrated the advantages of deep neural networks (DNNs) for achieving remarkable performance in motion and music tasks with little effort for feature pre-processing. However, applying DNNs for generating dance to a piece of music is nevertheless challenging, because of 1) DNNs need to generate large sequences while mapping the music input, 2) the DNN needs to constraint the motion beat to the music, and 3) DNNs require a considerable amount of hand-crafted data. In this study, we propose a weakly supervised deep recurrent method for real-time basic dance generation with audio power spectrum as input. The proposed model employs convolutional layers and a multilayered Long Short-Term memory (LSTM) to process the audio input. Then, another deep LSTM layer decodes the target dance sequence. Notably, this end-to-end approach has 1) an auto-conditioned decode configuration that reduces accumulation of feedback error of large dance sequence, 2) uses a contrastive cost function to regulate the mapping between the music and motion beat, and 3) trains with weak labels generated from the motion beat, reducing the amount of hand-crafted data. We evaluate the proposed network based on i) the similarities between generated and the baseline dancer motion with a cross entropy measure for large dance sequences, and ii) accurate timing between the music and motion beat with an F-measure. Experimental results revealed that, after training using a small dataset, the model generates basic dance steps with low cross entropy and maintains an F-measure score similar to that of a baseline dancer.
Verification Protocols with Sub-Linear Communication for Polynomial Matrix Operations
Venue: arXiv cs.SC 2019
Year: 2019

We design and analyze new protocols to verify the correctness of various computations on matrices over the ring F[x] of univariate polynomials over a field F. For the sake of efficiency, and because many of the properties we verify are specific to matrices over a principal ideal domain, we cannot simply rely on previously-developed linear algebra protocols for matrices over a field. Our protocols are interactive, often randomized, and feature a constant number of rounds of communication between the Prover and Verifier. We seek to minimize the communication cost so that the amount of data sent during the protocol is significantly smaller than the size of the result being verified, which can be useful when combining protocols or in some multi-party settings. The main tools we use are reductions to existing linear algebra verification protocols and a new protocol to verify that a given vector is in the F[x]-row space of a given matrix.
The Implementation of the Colored Abstract Simplicial Complex and its Application to Mesh Generation
Venue: arXiv cs.MS 2019
Year: 2019

We introduce CASC: a new, modern, and header-only C++ library which provides a data structure to represent arbitrary dimension abstract simplicial complexes (ASC) with user-defined classes stored directly on the simplices at each dimension. This is accomplished by using the latest C++ language features including variadic template parameters introduced in C++11 and automatic function return type deduction from C++14. Effectively CASC decouples the representation of the topology from the interactions of user data. We present the innovations and design principles of the data structure and related algorithms. This includes a metadata aware decimation algorithm which is general for collapsing simplices of any dimension. We also present an example application of this library to represent an orientable surface mesh.
Implicit Generative Modeling of Random Noise during Training for Adversarial Robustness
Venue: arXiv cs.LG 2019
Year: 2019

We introduce a Noise-based prior Learning (NoL) approach for training neural networks that are intrinsically robust to adversarial attacks. We find that the implicit generative modeling of random noise with the same loss function used during posterior maximization, improves a model's understanding of the data manifold furthering adversarial robustness. We evaluate our approach's efficacy and provide a simplistic visualization tool for understanding adversarial data, using Principal Component Analysis. Our analysis reveals that adversarial robustness, in general, manifests in models with higher variance along the high-ranked principal components. We show that models learnt with our approach perform remarkably well against a wide-range of attacks. Furthermore, combining NoL with state-of-the-art adversarial training extends the robustness of a model, even beyond what it is adversarially trained for, in both white-box and black-box attack scenarios.
Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processes
Venue: arXiv cs.LG 2019
Year: 2019

While designing the state space of an MDP, it is common to include states that are transient or not reachable by any policy (e.g., in mountain car, the product space of speed and position contains configurations that are not physically reachable). This leads to defining weakly-communicating or multi-chain MDPs. In this paper, we introduce \tucrl, the first algorithm able to perform efficient exploration-exploitation in any finite Markov Decision Process (MDP) without requiring any form of prior knowledge. In particular, for any MDP with $S^{\texttt{C}}$ communicating states, $A$ actions and $Γ^{\texttt{C}} \leq S^{\texttt{C}}$ possible communicating next states, we derive a $\widetilde{O}(D^{\texttt{C}} \sqrt{Γ^{\texttt{C}} S^{\texttt{C}} AT})$ regret bound, where $D^{\texttt{C}}$ is the diameter (i.e., the longest shortest path) of the communicating part of the MDP. This is in contrast with optimistic algorithms (e.g., UCRL, Optimistic PSRL) that suffer linear regret in weakly-communicating MDPs, as well as posterior sampling or regularised algorithms (e.g., REGAL), which require prior knowledge on the bias span of the optimal policy to bias the exploration to achieve sub-linear regret. We also prove that in weakly-communicating MDPs, no algorithm can ever achieve a logarithmic growth of the regret without first suffering a linear regret for a number of steps that is exponential in the parameters of the MDP. Finally, we report numerical simulations supporting our theoretical findings and showing how TUCRL overcomes the limitations of the state-of-the-art.