OpenRaiser/Intern-Atlas huggingface dataset:
Stochastic Block Models are a Discrete Surface Tension
Venue: arXiv cs.SI 2019
Year: 2019

Networks, which represent agents and interactions between them, arise in myriad applications throughout the sciences, engineering, and even the humanities. To understand large-scale structure in a network, a common task is to cluster a network's nodes into sets called "communities", such that there are dense connections within communities but sparse connections between them. A popular and statistically principled method to perform such clustering is to use a family of generative models known as stochastic block models (SBMs). In this paper, we show that maximum likelihood estimation in an SBM is a network analog of a well-known continuum surface-tension problem that arises from an application in metallurgy. To illustrate the utility of this relationship, we implement network analogs of three surface-tension algorithms, with which we successfully recover planted community structure in synthetic networks and which yield fascinating insights on empirical networks that we construct from hyperspectral videos.
A Collaborative Aerial-Ground Robotic System for Fast Exploration
Venue: arXiv cs.RO 2019
Year: 2019

Autonomous exploration of unknown environments has been widely applied in inspection, surveillance, and search and rescue. In exploration task, the basic requirement for robots is to detect the unknown space as fast as possible. In this paper, we propose an autonomous collaborative system consists of an aerial robot and a ground vehicle to explore in unknown environments. We combine the frontier based method and the harmonic field to generate a path. Then, For the ground robot, a minimum jerk piecewise Bezier curve which can guarantee safety and dynamical feasibility is generated amid obstacles. For the aerial robot, a motion primitive method is adopted for local path planning. We implement the proposed framework on an autonomous collaborative aerial-ground system. Extensive field experiments as well as simulations are presented to validate the method and demonstrate its higher efficiency against each single vehicle.
Code Design for Non-Coherent Detection of Frame Headers in Precoded Satellite Systems
Venue: arXiv cs.IT 2019
Year: 2019

In this paper we propose a simple method for generating short-length rate-compatible codes over $\mathbb{Z}_M$ that are robust to non-coherent detection for $M$-PSK constellations. First, a greedy algorithm is used to construct a family of rotationally invariant codes for a given constellation. Then, by properly modifying such codes we obtain codes that are robust to non-coherent detection. We briefly discuss the optimality of the constructed codes for special cases of BPSK and QPSK constellations. Our method provides an upper bound for the length of optimal codes with a given desired non-coherent distance. We also derive a simple asymptotic upper bound on the frame error rate (FER) of such codes and provide the simulation results for a selected set of proposed codes. Finally, we briefly discuss the problem of designing binary codes that are robust to non-coherent detection for QPSK constellation.
FastScan: Robust Low-Complexity Rate Adaptation Algorithm for Video Streaming over HTTP
Venue: arXiv cs.NI 2019
Year: 2019

This paper proposes and evaluates a novel algorithm for streaming video over HTTP. The problem is formulated as a non-convex optimization problem which is constrained by the predicted available bandwidth, chunk deadlines, available video rates, and buffer occupancy. The objective is to optimize a QoE metric that maintains a tradeoff between maximizing the playback rate of every chunk and ensuring fairness among different chunks for the minimum re-buffering time. We propose FastScan, a low complexity algorithm that solves the problem. Online adaptations for dynamic bandwidth environments are proposed with imperfect available bandwidth prediction. Results of experiments driven by Variable Bit Rate (VBR) encoded video, video platform system (dash.js), and cellular bandwidth traces of a public dataset reveal the robustness of the online version of FastScan algorithm and demonstrate its significant performance improvement as compared to the considered state-of-the-art video streaming algorithms. For example, on an experiment conducted over 100 real cellular available bandwidth traces of a public dataset that spans different available bandwidth regimes, our proposed algorithm (FastScan) achieves the minimum re-buffering (stall) time and the maximum average playback rate in every single trace as compared to Bola, Festive, BBA, RB, and FastMPC, and Pensieve algorithms.
Using Social Network Information in Bayesian Truth Discovery
Venue: arXiv cs.SI 2019
Year: 2019

We investigate the problem of truth discovery based on opinions from multiple agents who may be unreliable or biased. We consider the case where agents' reliabilities or biases are correlated if they belong to the same community, which defines a group of agents with similar opinions regarding a particular event. An agent can belong to different communities for different events, and these communities are unknown a priori. We incorporate knowledge of the agents' social network in our truth discovery framework and develop Laplace variational inference methods to estimate agents' reliabilities, communities, and the event states. We also develop a stochastic variational inference method to scale our model to large social networks. Simulations and experiments on real data suggest that when observations are sparse, our proposed methods perform better than several other inference methods, including majority voting, TruthFinder, AccuSim, the Confidence-Aware Truth Discovery method, the Bayesian Classifier Combination (BCC) method, and the Community BCC method.
Large-scale Bisample Learning on ID Versus Spot Face Recognition
Venue: arXiv cs.CV 2019
Year: 2019

In real-world face recognition applications, there is a tremendous amount of data with two images for each person. One is an ID photo for face enrollment, and the other is a probe photo captured on spot. Most existing methods are designed for training data with limited breadth (a relatively small number of classes) and sufficient depth (many samples for each class). They would meet great challenges on ID versus Spot (IvS) data, including the under-represented intra-class variations and an excessive demand on computing devices. In this paper, we propose a deep learning based large-scale bisample learning (LBL) method for IvS face recognition. To tackle the bisample problem with only two samples for each class, a classification-verification-classification (CVC) training strategy is proposed to progressively enhance the IvS performance. Besides, a dominant prototype softmax (DP-softmax) is incorporated to make the deep learning scalable on large-scale classes. We conduct LBL on a IvS face dataset with more than two million identities. Experimental results show the proposed method achieves superior performance to previous ones, validating the effectiveness of LBL on IvS face recognition.
Reducing Metadata Leakage from Encrypted Files and Communication with PURBs
Venue: arXiv cs.CR 2019
Year: 2019

Most encrypted data formats leak metadata via their plaintext headers, such as format version, encryption schemes used, number of recipients who can decrypt the data, and even the recipients' identities. This leakage can pose security and privacy risks to users, e.g., by revealing the full membership of a group of collaborators from a single encrypted e-mail, or by enabling an eavesdropper to fingerprint the precise encryption software version and configuration the sender used. We propose that future encrypted data formats improve security and privacy hygiene by producing $\textit{Padded Uniform Random Blobs}$ or PURBs: ciphertexts indistinguishable from random bit strings to anyone without a decryption key. A PURB's content leaks $\textit{nothing at all}$, even the application that created it, and is padded such that even its length leaks as little as possible. Encoding and decoding ciphertexts with $\textit{no}$ cleartext markers presents efficiency challenges, however. We present cryptographically agile encodings enabling legitimate recipients to decrypt a PURB efficiently, even when encrypted for any number of recipients' public keys and/or passwords, and when these public keys are from different cryptographic suites. PURBs employ Padmé, a~novel padding scheme that limits information leakage via ciphertexts of maximum length $M$ to a practical optimum of $O(\log \log M)$ bits, comparable to padding to a power of two, but with lower overhead of at most $12\%$ and decreasing with larger payloads.
Formal Small-step Verification of a Call-by-value Lambda Calculus Machine
Venue: arXiv cs.LO 2019
Year: 2019

We formally verify an abstract machine for a call-by-value lambda-calculus with de Bruijn terms, simple substitution, and small-step semantics. We follow a stepwise refinement approach starting with a naive stack machine with substitution. We then refine to a machine with closures, and finally to a machine with a heap providing structure sharing for closures. We prove the correctness of the three refinement steps with compositional small-step bottom-up simulations. There is an accompanying Coq development verifying all results.
Data-driven model for the identification of the rock type at a drilling bit
Venue: arXiv cs.LG 2019
Year: 2019

Directional oil well drilling requires high precision of the wellbore positioning inside the productive area. However, due to specifics of engineering design, sensors that explicitly determine the type of the drilled rock are located farther than 15m from the drilling bit. As a result, the target area runaways can be detected only after this distance, which in turn, leads to a loss in well productivity and the risk of the need for an expensive re-boring operation. We present a novel approach for identifying rock type at the drilling bit based on machine learning classification methods and data mining on sensors readings. We compare various machine-learning algorithms, examine extra features coming from mathematical modeling of drilling mechanics, and show that the real-time rock type classification error can be reduced from 13.5 % to 9 %. The approach is applicable for precise directional drilling in relatively thin target intervals of complex shapes and generalizes appropriately to new wells that are different from the ones used for training the machine learning model.
PatchFCN for Intracranial Hemorrhage Detection
Venue: arXiv cs.CV 2019
Year: 2019

This paper studies the problem of detecting and segmenting acute intracranial hemorrhage on head computed tomography (CT) scans. We propose to solve both tasks as a semantic segmentation problem using a patch-based fully convolutional network (PatchFCN). This formulation allows us to accurately localize hemorrhages while bypassing the complexity of object detection. Our system demonstrates competitive performance with a human expert and the state-of-the-art on classification tasks (0.976, 0.966 AUC of ROC on retrospective and prospective test sets) and on segmentation tasks (0.785 pixel AP, 0.766 Dice score), while using much less data and a simpler system. In addition, we conduct a series of controlled experiments to understand "why" PatchFCN outperforms standard FCN. Our studies show that PatchFCN finds a good trade-off between batch diversity and the amount of context during training. These findings may also apply to other medical segmentation tasks.
Similarity Join and Similarity Self-Join Size Estimation in a Streaming Environment
Venue: arXiv cs.DB 2019
Year: 2019

We study the problem of similarity self-join and similarity join size estimation in a streaming setting where the goal is to estimate, in one scan of the input and with sublinear space in the input size, the number of record pairs that have a similarity within a given threshold. The problem has many applications in data cleaning and query plan generation, where the cost of a similarity join may be estimated before actually doing the join. On unary input where two records either match or don't match, the problem becomes join and self-join size estimation for which one-pass algorithms are readily available. Our work addresses the problem for d-ary input, for d >= 1, where the degree of similarity can vary from 1 to d. We show that our proposed algorithm gives an accurate estimate and scales well with the input size. We provide error bounds and time and space costs, and conduct an extensive experimental evaluation of our algorithm, comparing its estimation accuracy to a few competitors, including some multi-pass algorithms. Our results show that given the same space, the proposed algorithm has an order of magnitude less error for a large range of similarity thresholds.
On the Covariance-Hessian Relation in Evolution Strategies
Venue: arXiv cs.NE 2019
Year: 2019

We consider Evolution Strategies operating only with isotropic Gaussian mutations on positive quadratic objective functions, and investigate the covariance matrix when constructed out of selected individuals by truncation. We prove that the covariance matrix over $(1,λ)$-selected decision vectors becomes proportional to the inverse of the landscape Hessian as the population-size $λ$ increases. This generalizes a previous result that proved an equivalent phenomenon when sampling was assumed to take place in the vicinity of the optimum. It further confirms the classical hypothesis that statistical learning of the landscape is an inherent characteristic of standard Evolution Strategies, and that this distinguishing capability stems only from the usage of isotropic Gaussian mutations and rank-based selection. We provide broad numerical validation for the proven results, and present empirical evidence for its generalization to $(μ,λ)$-selection.
Context-Aware Policy Reuse
Venue: arXiv cs.AI 2019
Year: 2019

Transfer learning can greatly speed up reinforcement learning for a new task by leveraging policies of relevant tasks. Existing works of policy reuse either focus on only selecting a single best source policy for transfer without considering contexts, or cannot guarantee to learn an optimal policy for a target task. To improve transfer efficiency and guarantee optimality, we develop a novel policy reuse method, called Context-Aware Policy reuSe (CAPS), that enables multi-policy transfer. Our method learns when and which source policy is best for reuse, as well as when to terminate its reuse. CAPS provides theoretical guarantees in convergence and optimality for both source policy selection and target task learning. Empirical results on a grid-based navigation domain and the Pygame Learning Environment demonstrate that CAPS significantly outperforms other state-of-the-art policy reuse methods.
Prosody Modifications for Question-Answering in Voice-Only Settings
Venue: arXiv cs.CL 2019
Year: 2019

Many popular form factors of digital assistants---such as Amazon Echo, Apple Homepod, or Google Home---enable the user to hold a conversation with these systems based only on the speech modality. The lack of a screen presents unique challenges. To satisfy the information need of a user, the presentation of the answer needs to be optimized for such voice-only interactions. In this paper, we propose a task of evaluating the usefulness of audio transformations (i.e., prosodic modifications) for voice-only question answering. We introduce a crowdsourcing setup where we evaluate the quality of our proposed modifications along multiple dimensions corresponding to the informativeness, naturalness, and ability of the user to identify key parts of the answer. We offer a set of prosodic modifications that highlight potentially important parts of the answer using various acoustic cues. Our experiments show that some of these prosodic modifications lead to better comprehension at the expense of only slightly degraded naturalness of the audio.
Rethinking Blockchain Security: Position Paper
Venue: arXiv cs.CR 2019
Year: 2019

Blockchain technology has become almost as famous for incidents involving security breaches as for its innovative potential. We shed light on the prevalence and nature of these incidents through a database structured using the STIX format. Apart from OPSEC-related incidents, we find that the nature of many incidents is specific to blockchain technology. Two categories stand out: smart contracts, and techno-economic protocol incentives. For smart contracts, we propose to use recent advances in software testing to find flaws before deployment. For protocols, we propose the PRESTO framework that allows us to compare different protocols within a five-dimensional framework.
Ensemble Pruning based on Objection Maximization with a General Distributed Framework
Venue: arXiv cs.LG 2019
Year: 2019

Ensemble pruning, selecting a subset of individual learners from an original ensemble, alleviates the deficiencies of ensemble learning on the cost of time and space. Accuracy and diversity serve as two crucial factors while they usually conflict with each other. To balance both of them, we formalize the ensemble pruning problem as an objection maximization problem based on information entropy. Then we propose an ensemble pruning method including a centralized version and a distributed version, in which the latter is to speed up the former. At last, we extract a general distributed framework for ensemble pruning, which can be widely suitable for most of the existing ensemble pruning methods and achieve less time consuming without much accuracy degradation. Experimental results validate the efficiency of our framework and methods, particularly concerning a remarkable improvement of the execution speed, accompanied by gratifying accuracy performance.
Failure Analysis of the Interval-Passing Algorithm for Compressed Sensing
Venue: arXiv cs.IT 2019
Year: 2019

In this work, we perform a complete failure analysis of the interval-passing algorithm (IPA) for compressed sensing, an efficient iterative algorithm for reconstructing a $k$-sparse nonnegative $n$-dimensional real signal $\boldsymbol{x}$ from a small number of linear measurements $\boldsymbol{y}$. In particular, we show that the IPA fails to recover $\boldsymbol{x}$ from $\boldsymbol{y}$ if and only if it fails to recover a corresponding binary vector of the same support, and also that only positions of nonzero values in the measurement matrix are of importance to the success of recovery. Based on this observation, we introduce termatiko sets and show that the IPA fails to fully recover $\boldsymbol x$ if and only if the support of $\boldsymbol x$ contains a nonempty termatiko set, thus giving a complete (graph-theoretic) description of the failing sets of the IPA. Two heuristics to locate small-size termatiko sets are presented. For binary column-regular measurement matrices with no $4$-cycles, we provide a lower bound on the termatiko distance, defined as the smallest size of a nonempty termatiko set. For measurement matrices constructed from the parity-check matrices of array LDPC codes, upper bounds on the termatiko distance are provided for column-weight at most $7$, while for column-weight $3$, the exact termatiko distance and its corresponding multiplicity are provided. Next, we show that adding redundant rows to the measurement matrix does not create new termatiko sets, but rather potentially removes termatiko sets and thus improves performance. An algorithm is provided to efficiently search for such redundant rows. Finally, we present numerical results for different specific measurement matrices and also for protograph-based ensembles of measurement matrices, as well as simulation results of IPA performance, showing the influence of small-size termatiko sets.
On Tighter Generalization Bound for Deep Neural Networks: CNNs, ResNets, and Beyond
Venue: arXiv cs.LG 2019
Year: 2019

We establish a margin based data dependent generalization error bound for a general family of deep neural networks in terms of the depth and width, as well as the Jacobian of the networks. Through introducing a new characterization of the Lipschitz properties of neural network family, we achieve significantly tighter generalization bounds than existing results. Moreover, we show that the generalization bound can be further improved for bounded losses. Aside from the general feedforward deep neural networks, our results can be applied to derive new bounds for popular architectures, including convolutional neural networks (CNNs) and residual networks (ResNets). When achieving same generalization errors with previous arts, our bounds allow for the choice of larger parameter spaces of weight matrices, inducing potentially stronger expressive ability for neural networks. Numerical evaluation is also provided to support our theory.
Geometric Shape Features Extraction Using a Steady State Partial Differential Equation System
Venue: arXiv cs.CV 2019
Year: 2019

A unified method for extracting geometric shape features from binary image data using a steady state partial differential equation (PDE) system as a boundary value problem is presented in this paper. The PDE and functions are formulated to extract the thickness, orientation, and skeleton simultaneously. The main advantages of the proposed method is that the orientation is defined without derivatives and thickness computation is not imposed a topological constraint on the target shape. A one-dimensional analytical solution is provided to validate the proposed method. In addition, two-dimensional numerical examples are presented to confirm the usefulness of the proposed method.
Asymptotic maximum order statistic for SIR in $κ-μ$ shadowed fading
Venue: arXiv cs.IT 2019
Year: 2019

Using tools from extreme value theory (EVT), it is proved that, when the user signal and the interferer signals undergo independent and non-identically distributed (i.n.i.d.) $κ-μ$ shadowed fading, the limiting distribution of the maximum of $L$ independent and identically distributed (i.i.d.) signal-to-interference ratio (SIR) random variables (RVs) is a Frechet distribution. It is observed that this limiting distribution is close to the true distribution of maximum, for maximum SIR evaluated over moderate $L$. Further, moments of the maximum RV is shown to converge to the moments of the Frechet RV. Also, the rate of convergence of the actual distribution of the maximum to the Frechet distribution is derived and is analyzed for different $κ$ and $μ$ parameters. Finally, results from stochastic ordering are used to analyze the variation in the limiting distribution with respect to the variation in source fading parameters. These results are then used to derive upper bound for the rate in Full Array Selection (FAS) schemes for antenna selection and the asymptotic outage probability and the ergodic rate in maximum-sum-capacity (MSC) scheduling systems.
Detecting Statistically Significant Communities
Venue: arXiv cs.SI 2019
Year: 2019

Community detection is a key data analysis problem across different fields. During the past decades, numerous algorithms have been proposed to address this issue. However, most work on community detection does not address the issue of statistical significance. Although some research efforts have been made towards mining statistically significant communities, deriving an analytical solution of p-value for one community under the configuration model is still a challenging mission that remains unsolved. The configuration model is a widely used random graph model in community detection, in which the degree of each node is preserved in the generated random networks. To partially fulfill this void, we present a tight upper bound on the p-value of a single community under the configuration model, which can be used for quantifying the statistical significance of each community analytically. Meanwhile, we present a local search method to detect statistically significant communities in an iterative manner. Experimental results demonstrate that our method is comparable with the competing methods on detecting statistically significant communities.