OpenRaiser/Intern-Atlas huggingface dataset:
On optimal ordering in the optimal stopping problem
Venue: arXiv cs.DM 2020
Year: 2020

In the classical optimal stopping problem, a player is given a sequence of random variables $X_1\ldots X_n$ with known distributions. After observing the realization of $X_i$, the player can either accept the observed reward from $X_i$ and stop, or reject the observed reward from $X_i$ and continue to observe the next variable $X_{i+1}$ in the sequence. Under any fixed ordering of the random variables, an optimal stopping policy, one that maximizes the player's expected reward, is given by the solution of a simple dynamic program. In this paper, we investigate the relatively less studied question of selecting the order in which the random variables should be observed so as to maximize the expected reward at the stopping time. To demonstrate the benefits of order selection, we prove a novel prophet inequality showing that, when the support of each random variable has size at most 2, the optimal ordering can achieve an expected reward that is within a factor of 1.25 of the expected hindsight maximum; this is an improvement over the corresponding factor of 2 for the worst-case ordering. We also provide a simple $O(n^2)$ algorithm for finding an optimal ordering in this case. Perhaps surprisingly, we demonstrate that a slightly more general case - each random variable $X_i$ is restricted to have 3-point support of form $\{0, m_i, 1\}$ - is NP-hard, and provide an FPTAS for that case.
PRESTvO: PRivacy Enabled Smartphone-based access To vehicle On-board units
Venue: arXiv cs.CR 2020
Year: 2020

Smartphones are quickly moving toward complementing or even replacing traditional car keys. We advocate a role-based access control policy mixed with attributes that facilitates access to various functionalities of vehicular on-board units from smartphones. We use a rights-based access control policy for in-vehicle functionalities similar to the case of a file allocation table of a contemporary OS, in which read, write or execute operations can be performed over various vehicle functions. Further, to assure the appropriate security, we develop a protocol suite using identity-based cryptography and we rely on group signatures that preserve the anonymity of group members for assuring privacy and traceability. To prove the feasibility of our approach, we develop a proof-of-concept implementation with modern smartphones, aftermarket Android head-units and test computational feasibility on a real-world in-vehicle controller. Our implementation relies on state-of-the-art cryptography, including traditional building blocks and more modern pairing-friendly curves, that facilitate the adoption of group signatures and identity-based cryptography in automotive-based scenarios.
HyPar-Flow: Exploiting MPI and Keras for Scalable Hybrid-Parallel DNN Training using TensorFlow
Venue: arXiv cs.DC 2020
Year: 2020

To reduce training time of large-scale DNNs, scientists have started to explore parallelization strategies like data-parallelism, model-parallelism, and hybrid-parallelism. While data-parallelism has been extensively studied and developed, several problems exist in realizing model-parallelism and hybrid-parallelism efficiently. Four major problems we focus on are: 1) defining a notion of a distributed model across processes, 2) implementing forward/back-propagation across process boundaries that requires explicit communication, 3) obtaining parallel speedup on an inherently sequential task, and 4) achieving scalability without losing out on a model's accuracy. To address these problems, we create HyPar-Flow --- a model-size/-type agnostic, scalable, practical, and user-transparent system for hybrid-parallel training by exploiting MPI, Keras, and TensorFlow. HyPar-Flow provides a single API that can be used to perform data, model, and hybrid parallel training of any Keras model at scale. We create an internal distributed representation of the user-provided Keras model, utilize TF's Eager execution features for distributed forward/back-propagation across processes, exploit pipelining to improve performance and leverage efficient MPI primitives for scalable communication. Between model partitions, we use send and recv to exchange layer-data/partial-errors while allreduce is used to accumulate/average gradients across model replicas. Beyond the design and implementation of HyPar-Flow, we also provide comprehensive correctness and performance results on three state-of-the-art HPC systems including TACC Frontera (#5 on Top500.org). For ResNet-1001, an ultra-deep model, HyPar-Flow provides: 1) Up to 1.6x speedup over Horovod-based data-parallel training, 2) 110x speedup over single-node on 128 Stampede2 nodes, and 3) 481x speedup over single-node on 512 Frontera nodes.
ZiMM: a deep learning model for long term and blurry relapses with non-clinical claims data
Venue: arXiv cs.LG 2020
Year: 2020

This paper considers the problems of modeling and predicting a long-term and ``blurry'' relapse that occurs after a medical act, such as a surgery. The relapse is observed only indirectly, in a ``blurry'' fashion, through longitudinal prescriptions of drugs over a long period of time after the medical act. We introduce a new model, called ZiMM (Zero-inflated Mixture of Multinomial distributions) in order to capture long-term and blurry relapses. On top of it, we build an end-to-end deep-learning architecture called ZiMM Encoder-Decoder (ZiMM ED) that can learn from the complex, irregular, highly heterogeneous and sparse patterns of health events that are observed through a claims-only database. ZiMM ED is applied on a ``non-clinical'' claims database, that contains only timestamped reimbursement codes for drug purchases, medical procedures and hospital diagnoses, the only available clinical feature being the age of the patient. This setting is more challenging than a setting where bedside clinical signals are available. Our motivation for using such a non-clinical claims database is its exhaustivity population-wise, compared to clinical electronic health records coming from a single or a small set of hospitals. Indeed, we consider a dataset containing the claims of almost \emph{all French citizens} who had surgery for prostatic problems, with a history between 1.5 and 5 years. We consider a long-term (18 months) relapse (urination problems still occur despite surgery), which is blurry since it is observed only through the reimbursement of a specific set of drugs for urination problems. Our experiments show that ZiMM ED improves several baselines, including non-deep learning and deep-learning approaches, and that it allows working on such a dataset with minimal preprocessing work.
High Reliability Downlink MU-MIMO: New OSTBC Approach and Superposition Modulated Side Information
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, a proposal to improve the reliability of a downlink multiuser (MU) MIMO transmission scheme is investigated with the use of a new approach in orthogonal space-time block codes (OSTBC) and network coding with a superposition modulated system and side information. With the new encoded OSTBC approach, diversity is offered where each user receives all other users' symbols, which allows the recovery of symbols in several ways. In addition, multiple users can be accommodated with the same resource, which is quite useful in a wireless system where resources are always restricted. By employing superposition modulation, the side information needed for error recovery can be transmitted over the same resource used for the normal information frame. In addition, the proposed system exploits diversity through a novel technique of sub-constellation alignment-based signal combining for efficient side information dissemination. A detailed analysis of the new OSTBC approach is carried out. It is shown that the performance of the MU-MIMO system can be improved significantly in terms of block and frame error rates (BLER, FER) considered as reliability measures. By accommodating a reasonable number of multiple users, high reliability is achieved at the expense of the rate. To compensate for the low rate, conventional OSTBC can be considered and simulation results are shown, where, as a penalty to pay, multiple orthogonal resources are required.
GANprintR: Improved Fakes and Evaluation of the State of the Art in Face Manipulation Detection
Venue: arXiv cs.CV 2020
Year: 2020

The availability of large-scale facial databases, together with the remarkable progresses of deep learning technologies, in particular Generative Adversarial Networks (GANs), have led to the generation of extremely realistic fake facial content, raising obvious concerns about the potential for misuse. Such concerns have fostered the research on manipulation detection methods that, contrary to humans, have already achieved astonishing results in various scenarios. In this study, we focus on the synthesis of entire facial images, which is a specific type of facial manipulation. The main contributions of this study are four-fold: i) a novel strategy to remove GAN "fingerprints" from synthetic fake images based on autoencoders is described, in order to spoof facial manipulation detection systems while keeping the visual quality of the resulting images; ii) an in-depth analysis of the recent literature in facial manipulation detection; iii) a complete experimental assessment of this type of facial manipulation, considering the state-of-the-art fake detection systems (based on holistic deep networks, steganalysis, and local artifacts), remarking how challenging is this task in unconstrained scenarios; and finally iv) we announce a novel public database, named iFakeFaceDB, yielding from the application of our proposed GAN-fingerprint Removal approach (GANprintR) to already very realistic synthetic fake images. The results obtained in our empirical evaluation show that additional efforts are required to develop robust facial manipulation detection systems against unseen conditions and spoof techniques, such as the one proposed in this study.
Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries
Venue: arXiv cs.DB 2020
Year: 2020

We study ranked enumeration of join-query results according to very general orders defined by selective dioids. Our main contribution is a framework for ranked enumeration over a class of dynamic programming problems that generalizes seemingly different problems that had been studied in isolation. To this end, we extend classic algorithms that find the k-shortest paths in a weighted graph. For full conjunctive queries, including cyclic ones, our approach is optimal in terms of the time to return the top result and the delay between results. These optimality properties are derived for the widely used notion of data complexity, which treats query size as a constant. By performing a careful cost analysis, we are able to uncover a previously unknown tradeoff between two incomparable enumeration approaches: one has lower complexity when the number of returned results is small, the other when the number is very large. We theoretically and empirically demonstrate the superiority of our techniques over batch algorithms, which produce the full result and then sort it. Our technique is not only faster for returning the first few results, but on some inputs beats the batch algorithm even when all results are produced.
Resolvable Ambiguity
Venue: arXiv cs.FL 2020
Year: 2020

A common standpoint when designing the syntax of programming languages is that the grammar definition has to be unambiguous. However, requiring up front unambiguous grammars can force language designers to make more or less arbitrary choices to disambiguate the language. In this paper, we depart from the traditional view of unambiguous grammar design, and enable the detection of ambiguities to be delayed until parse time, allowing the user of the language to perform the disambiguation. A natural decision problem follows: given a language definition, can a user always disambiguate an ambiguous program? We introduce and formalize this fundamental problem - called the resolvable ambiguity problem - and divide it into separate static and dynamic resolvability problems. We provide solutions to the static problem for a restricted language class and sketch proofs of soundness and completeness. We also provide a sound and complete solution to the dynamic problem for a much less restricted class of languages. The approach is evaluated through two separate case studies, covering both a large existing programming language, and the composability of domain-specific languages.
ViWi: A Deep Learning Dataset Framework for Vision-Aided Wireless Communications
Venue: arXiv cs.LG 2020
Year: 2020

The growing role that artificial intelligence and specifically machine learning is playing in shaping the future of wireless communications has opened up many new and intriguing research directions. This paper motivates the research in the novel direction of \textit{vision-aided wireless communications}, which aims at leveraging visual sensory information in tackling wireless communication problems. Like any new research direction driven by machine learning, obtaining a development dataset poses the first and most important challenge to vision-aided wireless communications. This paper addresses this issue by introducing the Vision-Wireless (ViWi) dataset framework. It is developed to be a parametric, systematic, and scalable data generation framework. It utilizes advanced 3D-modeling and ray-tracing softwares to generate high-fidelity synthetic wireless and vision data samples for the same scenes. The result is a framework that does not only offer a way to generate training and testing datasets but helps provide a common ground on which the quality of different machine learning-powered solutions could be assessed.
Improving PHY-Security of UAV-Enabled Transmission with Wireless Energy Harvesting: Robust Trajectory Design and Communications Resource Allocation
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we consider an unmanned aerial vehicle (UAV) assisted communications system, including two cooperative UAVs, a wireless-powered ground destination node leveraging simultaneous wireless information and power transfer (SWIPT) technique, and a terrestrial passive eavesdropper. One UAV delivers confidential information to destination and the other sends jamming signals to against eavesdropping and assist destination with energy harvesting. Assuming UAVs have partial information about eavesdropper's location, we propose two transmission schemes: friendly UAV jamming (FUJ) and Gaussian jamming transmission (GJT) for the cases when jamming signals are known and unknown a priori at destination, respectively. Then, we formulate an average secrecy rate maximization problem to jointly optimize the transmission power and trajectory of UAVs, and the power splitting ratio of destination. Being non-convex and hence difficult to solve the formulated problem, we propose a computationally efficient iterative algorithm based on block coordinate descent and successive convex approximation to obtain a suboptimal solution. Finally, numerical results are provided to substantiate the effectiveness of our proposed multiple-UAV schemes, compared to other existing benchmarks. Specifically, we find that the FUJ demonstrates significant secrecy performance improvement in terms of the optimal instantaneous and average secrecy rate compared to the GJT and the conventional single-UAV counterpart.
On a Centrality Maximization Game
Venue: arXiv cs.SI 2020
Year: 2020

The Bonacich centrality is a well-known measure of the relative importance of nodes in a network. This notion is, for example, at the core of Google's PageRank algorithm. In this paper we study a network formation game where each player corresponds to a node in the network to be formed and can decide how to rewire his m out-links aiming at maximizing his own Bonacich centrality, which is his utility function. We study the Nash equilibria (NE) and the best response dynamics of this game and we provide a complete classification of the set of NE when m=1 and a fairly complete classification of the NE when m=2. Our analysis shows that the centrality maximization performed by each node tends to create undirected and disconnected or loosely connected networks, namely 2-cliques for m=1 and rings or a special "Butterfly"-shaped graph when m=2. Our results build on locality property of the best response function in such game that we formalize and prove in the paper.
Separating Local & Shuffled Differential Privacy via Histograms
Venue: arXiv cs.CR 2020
Year: 2020

Recent work in differential privacy has highlighted the shuffled model as a promising avenue to compute accurate statistics while keeping raw data in users' hands. We present a protocol in this model that estimates histograms with error independent of the domain size. This implies an arbitrarily large gap in sample complexity between the shuffled and local models. On the other hand, the models are equivalent when we impose the constraints of pure differential privacy and single-message randomizers.
Generalized Maximum Causal Entropy for Inverse Reinforcement Learning
Venue: arXiv cs.LG 2020
Year: 2020

We consider the problem of learning from demonstrated trajectories with inverse reinforcement learning (IRL). Motivated by a limitation of the classical maximum entropy model in capturing the structure of the network of states, we propose an IRL model based on a generalized version of the causal entropy maximization problem, which allows us to generate a class of maximum entropy IRL models. Our generalized model has an advantage of being able to recover, in addition to a reward function, another expert's function that would (partially) capture the impact of the connecting structure of the states on experts' decisions. Empirical evaluation on a real-world dataset and a grid-world dataset shows that our generalized model outperforms the classical ones, in terms of recovering reward functions and demonstrated trajectories.
Regions of Interest Segmentation from LiDAR Point Cloud for Multirotor Aerial Vehicles
Venue: arXiv cs.RO 2020
Year: 2020

We propose a novel filter for segmenting the regions of interest from LiDAR 3D point cloud for multirotor aerial vehicles. It is specially targeted for real-time applications and works on sparse LiDAR point clouds without preliminary mapping. We use this filter as a crucial component of fast obstacle avoidance system for agriculture drone operating at low altitude. As the first step, each point cloud is transformed into a depth image and then identify places near to the vehicle (local maxima) by locating areas with high pixel densities. Afterwards, we merge the original depth image with identified locations after maximizing intensities of pixels in which local maxima were obtained. Next step is to calculate the range angle image that represents angles between two consecutive laser beams based on the improved depth image. Once the corresponding range angle image is constructed, smoothing is applied to reduce the noise. Finally, we find out connected components within the improved depth image while incorporating smoothed range angle image. This allows separating the regions of interest. The filter has been tested on various simulated environments as well as an actual drone and provides real-time performance. We make our source code, dataset available at https://github.com/GPrathap/hagen.git and real world experiment result can be found on the following link: https://www.youtube.com/watch?v=iHd_ZkhKPjc available online.
ADCC: An Effective and Intelligent Attention Dense Color Constancy System for Studying Images in Smart Cities
Venue: arXiv cs.CV 2020
Year: 2020

As a novel method eliminating chromatic aberration on objects, computational color constancy has becoming a fundamental prerequisite for many computer vision applications. Among algorithms performing this task, the learning-based ones have achieved great success in recent years. However, they fail to fully consider the spatial information of images, leaving plenty of room for improvement of the accuracy of illuminant estimation. In this paper, by exploiting the spatial information of images, we propose a color constancy algorithm called Attention Dense Color Constancy (ADCC) using convolutional neural network (CNN). Specifically, based on the 2D log-chrominance histograms of the input images as well as their specially augmented ones, ADCC estimates the illuminant with a self-attention DenseNet. The augmented images help to tell apart the edge gradients, edge pixels and non-edge ones in log-histogram, which contribute significantly to the feature extraction and color-ambiguity elimination, thereby advancing the accuracy of illuminant estimation. Simulations and experiments on benchmark datasets demonstrate that the proposed algorithm is effective for illuminant estimation compared to the state-of-the-art methods. Thus, ADCC offers great potential in promoting applications of smart cities, such as smart camera, where color is an important factor for distinguishing objects.
Dont Even Look Once: Synthesizing Features for Zero-Shot Detection
Venue: arXiv cs.CV 2020
Year: 2020

Zero-shot detection, namely, localizing both seen and unseen objects, increasingly gains importance for large-scale applications, with large number of object classes, since, collecting sufficient annotated data with ground truth bounding boxes is simply not scalable. While vanilla deep neural networks deliver high performance for objects available during training, unseen object detection degrades significantly. At a fundamental level, while vanilla detectors are capable of proposing bounding boxes, which include unseen objects, they are often incapable of assigning high-confidence to unseen objects, due to the inherent precision/recall tradeoffs that requires rejecting background objects. We propose a novel detection algorithm Dont Even Look Once (DELO), that synthesizes visual features for unseen objects and augments existing training algorithms to incorporate unseen object detection. Our proposed scheme is evaluated on Pascal VOC and MSCOCO, and we demonstrate significant improvements in test accuracy over vanilla and other state-of-art zero-shot detectors
vqSGD: Vector Quantized Stochastic Gradient Descent
Venue: arXiv cs.LG 2020
Year: 2020

In this work, we present a family of vector quantization schemes \emph{vqSGD} (Vector-Quantized Stochastic Gradient Descent) that provide an asymptotic reduction in the communication cost with convergence guarantees in first-order distributed optimization. In the process we derive the following fundamental information theoretic fact: $Θ(\frac{d}{R^2})$ bits are necessary and sufficient to describe an unbiased estimator ${\hat{g}}({g})$ for any ${g}$ in the $d$-dimensional unit sphere, under the constraint that $\|{\hat{g}}({g})\|_2\le R$ almost surely. In particular, we consider a randomized scheme based on the convex hull of a point set, that returns an unbiased estimator of a $d$-dimensional gradient vector with almost surely bounded norm. We provide multiple efficient instances of our scheme, that are near optimal, and require only $o(d)$ bits of communication at the expense of tolerable increase in error. The instances of our quantization scheme are obtained using the properties of binary error-correcting codes and provide a smooth tradeoff between the communication and the estimation error of quantization. Furthermore, we show that \emph{vqSGD} also offers strong privacy guarantees.