OpenRaiser/Intern-Atlas huggingface dataset:
Parity Decision Tree Complexity is Greater Than Granularity
Venue: arXiv cs.CC 2018
Year: 2018

We prove a new lower bound on the parity decision tree complexity $\mathsf{D}_{\oplus}(f)$ of a Boolean function $f$. Namely, granularity of the Boolean function $f$ is the smallest $k$ such that all Fourier coefficients of $f$ are integer multiples of $1/2^k$. We show that $\mathsf{D}_{\oplus}(f)\geq k+1$. This lower bound is an improvement of lower bounds through the sparsity of $f$ and through the degree of $f$ over $\mathbb{F}_2$. Using our lower bound we determine the exact parity decision tree complexity of several important Boolean functions including majority and recursive majority. For majority the complexity is $n - \mathsf{B}(n)+1$, where $\mathsf{B}(n)$ is the number of ones in the binary representation of $n$. For recursive majority the complexity is $\frac{n+1}{2}$. Finally, we provide an example of a function for which our lower bound is not tight. Our results imply new lower bound of $n - \mathsf{B}(n)$ on the multiplicative complexity of majority.
Subset Scanning Over Neural Network Activations
Venue: arXiv cs.LG 2018
Year: 2018

This work views neural networks as data generating systems and applies anomalous pattern detection techniques on that data in order to detect when a network is processing an anomalous input. Detecting anomalies is a critical component for multiple machine learning problems including detecting adversarial noise. More broadly, this work is a step towards giving neural networks the ability to recognize an out-of-distribution sample. This is the first work to introduce "Subset Scanning" methods from the anomalous pattern detection domain to the task of detecting anomalous input of neural networks. Subset scanning treats the detection problem as a search for the most anomalous subset of node activations (i.e., highest scoring subset according to non-parametric scan statistics). Mathematical properties of these scoring functions allow the search to be completed in log-linear rather than exponential time while still guaranteeing the most anomalous subset of nodes in the network is identified for a given input. Quantitative results for detecting and characterizing adversarial noise are provided for CIFAR-10 images on a simple convolutional neural network. We observe an "interference" pattern where anomalous activations in shallow layers suppress the activation structure of the original image in deeper layers.
The Ocean Tensor Package
Venue: arXiv cs.MS 2018
Year: 2018

Matrix and tensor operations form the basis of a wide range of fields and applications, and in many cases constitute a substantial part of the overall computational complexity. The ability of general-purpose GPUs to speed up many of these operations and enable others has resulted in a widespread adaptation of these devices. In order for tensor operations to take full advantage of the computational power, specialized software is required, and currently there exist several packages (predominantly in the area of deep learning) that incorporate tensor operations on both CPU and GPU. Nevertheless, a stand-alone framework that supports general tensor operations is still missing. In this paper we fill this gap and propose the Ocean Tensor Library: a modular tensor-support package that is designed to serve as a foundational layer for applications that require dense tensor operations on a variety of device types. The API is carefully designed to be powerful, extensible, and at the same time easy to use. The package is available as open source.
Left Ventricle Segmentation via Optical-Flow-Net from Short-axis Cine MRI: Preserving the Temporal Coherence of Cardiac Motion
Venue: arXiv cs.CV 2018
Year: 2018

Quantitative assessment of left ventricle (LV) function from cine MRI has significant diagnostic and prognostic value for cardiovascular disease patients. The temporal movement of LV provides essential information on the contracting/relaxing pattern of heart, which is keenly evaluated by clinical experts in clinical practice. Inspired by the expert way of viewing Cine MRI, we propose a new CNN module that is able to incorporate the temporal information into LV segmentation from cine MRI. In the proposed CNN, the optical flow (OF) between neighboring frames is integrated and aggregated at feature level, such that temporal coherence in cardiac motion can be taken into account during segmentation. The proposed module is integrated into the U-net architecture without need of additional training. Furthermore, dilated convolution is introduced to improve the spatial accuracy of segmentation. Trained and tested on the Cardiac Atlas database, the proposed network resulted in a Dice index of 95% and an average perpendicular distance of 0.9 pixels for the middle LV contour, significantly outperforming the original U-net that processes each frame individually. Notably, the proposed method improved the temporal coherence of LV segmentation results, especially at the LV apex and base where the cardiac motion is difficult to follow.
On the Heterogeneous Distributions in Paper Citations
Venue: arXiv cs.DL 2018
Year: 2018

Academic papers have been the protagonists in disseminating expertise. Naturally, paper citation pattern analysis is an efficient and essential way of investigating the knowledge structure of science and technology. For decades, it has been observed that citation of scientific literature follows a heterogeneous and heavy-tailed distribution, and many of them suggest a power-law distribution, log-normal distribution, and related distributions. However, many studies are limited to small-scale approaches; therefore, it is hard to generalize. To overcome this problem, we investigate 21 years of citation evolution through a systematic analysis of the entire citation history of 42,423,644 scientific literatures published from 1996 to 2016 and contained in SCOPUS. We tested six candidate distributions for the scientific literature in three distinct levels of Scimago Journal & Country Rank (SJR) classification scheme. First, we observe that the raw number of annual citation acquisitions tends to follow the log-normal distribution for all disciplines, except for the first year of the publication. We also find significant disparity between the yearly acquired citation number among the journals, which suggests that it is essential to remove the citation surplus inherited from the prestige of the journals. Our simple method for separating the citation preference of an individual article from the inherited citation of the journals reveals an unexpected regularity in the normalized annual acquisitions of citations across the entire field of science. Specifically, the normalized annual citation acquisitions have power-law probability distributions with an exponential cut-off of the exponents around 2.3, regardless of its publication and citation year. Our results imply that journal reputation has a substantial long-term impact on the citation.
The Frontiers of Fairness in Machine Learning
Venue: arXiv cs.LG 2018
Year: 2018

The last few years have seen an explosion of academic and popular interest in algorithmic fairness. Despite this interest and the volume and velocity of work that has been produced recently, the fundamental science of fairness in machine learning is still in a nascent state. In March 2018, we convened a group of experts as part of a CCC visioning workshop to assess the state of the field, and distill the most promising research directions going forward. This report summarizes the findings of that workshop. Along the way, it surveys recent theoretical work in the field and points towards promising directions for research.
Integrating Taxonomies into Theory-Based Digital Health Interventions for Behavior Change: A Holistic Framework
Venue: arXiv cs.HC 2018
Year: 2018

Digital health interventions have been emerging in the last decade. Due to their interdisciplinary nature, digital health interventions are guided and influenced by theories (e.g., behavioral theories, behavior change technologies, persuasive technology) from different research communities. However, digital health interventions are always coded using various taxonomies and reported in insufficient perspectives. The inconsistency and incomprehensiveness will bring difficulty for conducting systematic reviews and sharing contributions among communities. Based on existing related work, therefore, we propose a holistic framework that embeds behavioral theories, behavior change technique (BCT) taxonomy, and persuasive system design (PSD) principles. Including four development steps, two toolboxes, and one workflow, our framework aims to guide digital health intervention developers to design, evaluate, and report their work in a formative and comprehensive way.
Leveraging Program Analysis to Reduce User-Perceived Latency in Mobile Applications
Venue: arXiv cs.SE 2018
Year: 2018

Reducing network latency in mobile applications is an effective way of improving the mobile user experience and has tangible economic benefits. This paper presents PALOMA, a novel client-centric technique for reducing the network latency by prefetching HTTP requests in Android apps. Our work leverages string analysis and callback control-flow analysis to automatically instrument apps using PALOMA's rigorous formulation of scenarios that address "what" and "when" to prefetch. PALOMA has been shown to incur significant runtime savings (several hundred milliseconds per prefetchable HTTP request), both when applied on a reusable evaluation benchmark we have developed and on real applications
Joint Receiver Design for Internet of Things
Venue: arXiv cs.IT 2018
Year: 2018

Internet of things (IoT) is an ever-growing network of objects that connect, collect and exchange data. To achieve the mission of connecting everything, physical layer communication is of indispensable importance. In this work, we propose a new receiver tailored for the characteristics of IoT communications. Specifically, our design is suitable for sporadic transmissions of small-to-medium sized packets in IoT applications. With joint design in the new receiver, strong reliability is guaranteed and power saving is expected.
Catching Loosely Synchronized Behavior in Face of Camouflage
Venue: arXiv cs.SI 2018
Year: 2018

Fraud has severely detrimental impacts on the business of social networks and other online applications. A user can become a fake celebrity by purchasing "zombie followers" on Twitter. A merchant can boost his reputation through fake reviews on Amazon. This phenomenon also conspicuously exists on Facebook, Yelp and TripAdvisor, etc. In all the cases, fraudsters try to manipulate the platform's ranking mechanism by faking interactions between the fake accounts they control and the target customers.
Routing-Aware Partitioning of the Internet Address Space for Server Ranking in CDNs
Venue: arXiv cs.NI 2018
Year: 2018

The goal of Content Delivery Networks (CDNs) is to serve content to end-users with high performance. In order to do that, a CDN measures the latency on the paths from its servers to users and then selects a best available server for each user. For large CDNs, monitoring paths from thousands of servers to millions of users is a challenging task due to its size. In this paper, we address this problem and propose a framework to scale the task of path monitoring. Simply stated, the goal of our framework is clustering IP addresses (clients) such that in each cluster the choice of best available server is same (or similar). Then, finding a best available server for one client in a given cluster will be sufficient to assign that server to the rest of the clients in the cluster. To achieve this goal, first we introduce two distance metrics to compute how similar the server choices of any given two clients. Second, we use a clustering method that is based on interdomain routing information. We evaluate the goodness of our clusters by using the metrics we introduce. We show that there is a strong correlation between the similarity in how two destination clients are routed to in the Internet and the similarity in their server selections. Finally, we show how to choose representative clients from each cluster so that it is sufficient to learn the latencies from the CDN servers to the representative and find a best available server accordingly for the rest of the clients in the same cluster.
PQC: Triple Decomposition Problem Applied To GL(d, Fp) - A Secure Framework For Canonical Non-Commutative Cryptography
Venue: arXiv cs.CR 2018
Year: 2018

Post-Quantum Cryptography (PQC) attempts to find cryptographic protocols resistant to attacks using Shor polynomial time algorithm for numerical field problems or Grover search algorithm. A mostly overlooked but valuable line of solutions is provided by non-commutative algebraic structures, specifically canonical protocols that rely on one-way trapdoor functions (OWTF). Here we develop an algebraic framework who could be applied to different asymmetric protocols like D-H KE (Diffie-Hellman key exchange), Public Key Encryption, Digital Signature, ZKP (zero-knowledge proof) authentication, Oblivious Transfer, Multi-Party Computing, and so on. The trapdoor one-way functions selected are (a) Triple decomposition Problem (TDP) developed by Kurt, where a known element is factored into a product of three unknown factors and (b) a new version of conjugacy search that we refer from now on as Blind Conjugacy Search Problem (BCSP). Our platform structure is the general linear group GL(d,F_p) d-square non-singular matrices of prime field values. We give support to the fact that this framework is cryptographically secure against classical attacks like linear algebra attacks, length-based attacks, side-channel attacks against square (or duplicate) and multiply (or sum) algorithm, high sensitivity to pseudo random deterministic generators, etc. At same time it is immune against quantum attacks (using Grover and Shor), if the size parameters are carefully selected. Semantic security and IND-CCA2 compliance for this framework is discussed.
Predicting the outcomes of policy diffusion from U.S. states to federal law
Venue: arXiv cs.CY 2018
Year: 2018

In the United States, national policies often begin as state laws, which then spread from state to state until they gain momentum to become enacted as a national policy. However, not every state policy reaches the national level. Previous work has suggested that state-level policies are more likely to become national policies depending on their geographic origin, their category of legislation, or some characteristic of their initiating states, such as wealth, urbanicity, or ideological liberalism. Here, we tested these hypotheses by divorcing the set of traits from the states' identities and building predictive forecasting models of state policies becoming national policies. Using a large, longitudinal data set of state level policies and their traits, we train models to predict (i) whether policies become national policy, and (ii) how many states must pass a given policy before it becomes national. Using these models as components, we then develop a logistic growth model to forecast when a currently spreading state-level policy is likely to pass at the national level. Our results indicate that traits of initiating states are not systematically correlated with becoming national policy and they predict neither how many states must enact a policy before it becomes national nor whether it ultimately becomes a national law. In contrast, the cumulative number of state-level adoptions of a policy is reasonably predictive of when a policy becomes national. For the policies of same sex marriage and methamphetamine precursor laws, we investigate how well the logistic growth model could forecast the probable time horizon for true national action. We close with a data-driven forecast of when marijuana legalization and "stand your ground" laws will become national policy.
Transition-based Parsing with Lighter Feed-Forward Networks
Venue: arXiv cs.CL 2018
Year: 2018

We explore whether it is possible to build lighter parsers, that are statistically equivalent to their corresponding standard version, for a wide set of languages showing different structures and morphologies. As testbed, we use the Universal Dependencies and transition-based dependency parsers trained on feed-forward networks. For these, most existing research assumes de facto standard embedded features and relies on pre-computation tricks to obtain speed-ups. We explore how these features and their size can be reduced and whether this translates into speed-ups with a negligible impact on accuracy. The experiments show that grand-daughter features can be removed for the majority of treebanks without a significant (negative or positive) LAS difference. They also show how the size of the embeddings can be notably reduced.
Safe Adaptive Cruise Control with Road Grade Preview and V2V Communication
Venue: arXiv cs.SY 2018
Year: 2018

We present the design of a safe Adaptive Cruise Control (ACC) which uses road grade and lead vehicle motion preview. The ACC controller is designed by using a Model Predictive Control (MPC) framework to optimize comfort, safety, energy-efficiency and speed tracking accuracy. Safety is achieved by computing a robust invariant terminal set. The paper presents a novel approach to compute such set which is less conservative than existing methods. The proposed controller ensures safe inter-vehicle spacing at all times despite changes in the road grade and uncertainty in the predicted motion of the lead vehicle. Simulation results compare the proposed controller with a controller that does not incorporate prior grade knowledge on two scenarios including car-following and autonomous intersection crossing. The results demonstrate the effectiveness of the proposed control algorithm.
Robust Receiver Design for Non-orthogonal Multiple Access
Venue: arXiv cs.IT 2018
Year: 2018

Non-orthogonal multiple access (NOMA) has been proposed for massive connectivity in future generations of wireless communications. A dominant NOMA scheme is based on power optimization, in which decoding of target user is assumed to be perfect. In this work, rather than optimize on power domain, we are aimed to propose a robust receiver that can detect and decode the data streams of target user by FEC code diversity. Compared with existing NOMA receivers, our novel receiver substantially improves the bit-error-rate (BER) performance, and BER flooring can even be eliminated by assigning proper interleaving patterns to different users.
Spatial Co-location Pattern Mining - A new perspective using Graph Database
Venue: arXiv cs.DB 2018
Year: 2018

Spatial co-location pattern mining refers to the task of discovering the group of objects or events that co-occur at many places. Extracting these patterns from spatial data is very difficult due to the complexity of spatial data types, spatial relationships, and spatial auto-correlation. These patterns have applications in domains including public safety, geo-marketing, crime prediction and ecology. Prior work focused on using the spatial join. While these approaches provide state-of-the-art results, they are very expensive to compute due to the multiway spatial join and scaling them to real-world datasets is an open problem. We address these limitations by formulating the co-location pattern discovery as a clique enumeration problem over a neighborhood graph (which is materialized using a distributed graph database). We propose three new traversal based algorithms, namely $CliqueEnum_G$, $CliqueEnum_K$ and $CliqueExtend$. We provide the empirical evidence for the effectiveness of our proposed algorithms by evaluating them for a large real-life dataset. The three algorithms allow for a trade-off between time and memory requirements and support interactive data analysis without having to recompute all the intermediate results. These attributes make our algorithms applicable to a wide range of use cases for different data sizes.
Labeling Gaps Between Words: Recognizing Overlapping Mentions with Mention Separators
Venue: arXiv cs.CL 2018
Year: 2018

In this paper, we propose a new model that is capable of recognizing overlapping mentions. We introduce a novel notion of mention separators that can be effectively used to capture how mentions overlap with one another. On top of a novel multigraph representation that we introduce, we show that efficient and exact inference can still be performed. We present some theoretical analysis on the differences between our model and a recently proposed model for recognizing overlapping mentions, and discuss the possible implications of the differences. Through extensive empirical analysis on standard datasets, we demonstrate the effectiveness of our approach.
Atrial fibrosis quantification based on maximum likelihood estimator of multivariate images
Venue: arXiv cs.CV 2018
Year: 2018

We present a fully-automated segmentation and quantification of the left atrial (LA) fibrosis and scars combining two cardiac MRIs, one is the target late gadolinium-enhanced (LGE) image, and the other is an anatomical MRI from the same acquisition session. We formulate the joint distribution of images using a multivariate mixture model (MvMM), and employ the maximum likelihood estimator (MLE) for texture classification of the images simultaneously. The MvMM can also embed transformations assigned to the images to correct the misregistration. The iterated conditional mode algorithm is adopted for optimization. This method first extracts the anatomical shape of the LA, and then estimates a prior probability map. It projects the resulting segmentation onto the LA surface, for quantification and analysis of scarring. We applied the proposed method to 36 clinical data sets and obtained promising results (Accuracy: $0.809\pm .150$, Dice: $0.556\pm.187$). We compared the method with the conventional algorithms and showed an evidently and statistically better performance ($p<0.03$).
The Bregman chord divergence
Venue: arXiv cs.LG 2018
Year: 2018

Distances are fundamental primitives whose choice significantly impacts the performances of algorithms in machine learning and signal processing. However selecting the most appropriate distance for a given task is an endeavor. Instead of testing one by one the entries of an ever-expanding dictionary of {\em ad hoc} distances, one rather prefers to consider parametric classes of distances that are exhaustively characterized by axioms derived from first principles. Bregman divergences are such a class. However fine-tuning a Bregman divergence is delicate since it requires to smoothly adjust a functional generator. In this work, we propose an extension of Bregman divergences called the Bregman chord divergences. This new class of distances does not require gradient calculations, uses two scalar parameters that can be easily tailored in applications, and generalizes asymptotically Bregman divergences.
Mining useful Macro-actions in Planning
Venue: arXiv cs.AI 2018
Year: 2018

Planning has achieved significant progress in recent years. Among the various approaches to scale up plan synthesis, the use of macro-actions has been widely explored. As a first stage towards the development of a solution to learn on-line macro-actions, we propose an algorithm to identify useful macro-actions based on data mining techniques. The integration in the planning search of these learned macro-actions shows significant improvements over six classical planning benchmarks.