OpenRaiser/Intern-Atlas huggingface dataset:
Going Higher in First-Order Quantifier Alternation Hierarchies on Words
Venue: arXiv cs.LO 2017
Year: 2017

We investigate quantifier alternation hierarchies in first-order logic on finite words. Levels in these hierarchies are defined by counting the number of quantifier alternations in formulas. We prove that one can decide membership of a regular language in the levels $\mathcal{B}Σ_2$ (finite boolean combinations of formulas having only one alternation) and $Σ_3$ (formulas having only two alternations and beginning with an existential block). Our proofs work by considering a deeper problem, called separation, which, once solved for lower levels, allows us to solve membership for higher levels.
Halftone Image Watermarking by Content Aware Double-sided Embedding Error Diffusion
Venue: arXiv cs.MM 2017
Year: 2017

In this paper, we carry out a performance analysis from a probabilistic perspective to introduce the EDHVW methods' expected performances and limitations. Then, we propose a new general error diffusion based halftone visual watermarking (EDHVW) method, Content aware Double-sided Embedding Error Diffusion (CaDEED), via considering the expected watermark decoding performance with specific content of the cover images and watermark, different noise tolerance abilities of various cover image content and the different importance levels of every pixel (when being perceived) in the secret pattern (watermark). To demonstrate the effectiveness of CaDEED, we propose CaDEED with expectation constraint (CaDEED-EC) and CaDEED-NVF&IF (CaDEED-N&I). Specifically, we build CaDEED-EC by only considering the expected performances of specific cover images and watermark. By adopting the noise visibility function (NVF) and proposing the importance factor (IF) to assign weights to every embedding location and watermark pixel, respectively, we build the specific method CaDEED-N&I. In the experiments, we select the optimal parameters for NVF and IF via extensive experiments. In both the numerical and visual comparisons, the experimental results demonstrate the superiority of our proposed work.
Sciunits: Reusable Research Objects
Venue: arXiv cs.DL 2017
Year: 2017

Science is conducted collaboratively, often requiring knowledge sharing about computational experiments. When experiments include only datasets, they can be shared using Uniform Resource Identifiers (URIs) or Digital Object Identifiers (DOIs). An experiment, however, seldom includes only datasets, but more often includes software, its past execution, provenance, and associated documentation. The Research Object has recently emerged as a comprehensive and systematic method for aggregation and identification of diverse elements of computational experiments. While a necessary method, mere aggregation is not sufficient for the sharing of computational experiments. Other users must be able to easily recompute on these shared research objects. In this paper, we present the sciunit, a reusable research object in which aggregated content is recomputable. We describe a Git-like client that efficiently creates, stores, and repeats sciunits. We show through analysis that sciunits repeat computational experiments with minimal storage and processing overhead. Finally, we provide an overview of sharing and reproducible cyberinfrastructure based on sciunits gaining adoption in the domain of geosciences.
A Novel Deep Learning Architecture for Testis Histology Image Classification
Venue: arXiv cs.CV 2017
Year: 2017

Unlike other histology analysis, classification of tubule status in testis histology is very challenging due to their high similarity of texture and shape. Traditional deep learning networks have difficulties to capture nuance details among different tubule categories. In this paper, we propose a novel deep learning architecture for feature learning, image classification, and image reconstruction. It is based on stacked auto-encoders with an additional layer, called a hyperlayer, which is created to capture features of an image at different layers in the network. This addition effectively combines features at different scales and thus provides a more complete profile for further classification. Evaluation is performed on a set of 10,542 tubule image patches. We demonstrate our approach with two experiments on two different subsets of the dataset. The results show that the features learned from our architecture achieve more than 98% accuracy and represent an improvement over traditional deep network architectures.
Discovering Class-Specific Pixels for Weakly-Supervised Semantic Segmentation
Venue: arXiv cs.CV 2017
Year: 2017

We propose an approach to discover class-specific pixels for the weakly-supervised semantic segmentation task. We show that properly combining saliency and attention maps allows us to obtain reliable cues capable of significantly boosting the performance. First, we propose a simple yet powerful hierarchical approach to discover the class-agnostic salient regions, obtained using a salient object detector, which otherwise would be ignored. Second, we use fully convolutional attention maps to reliably localize the class-specific regions in a given image. We combine these two cues to discover class-specific pixels which are then used as an approximate ground truth for training a CNN. While solving the weakly supervised semantic segmentation task, we ensure that the image-level classification task is also solved in order to enforce the CNN to assign at least one pixel to each object present in the image. Experimentally, on the PASCAL VOC12 val and test sets, we obtain the mIoU of 60.8% and 61.9%, achieving the performance gains of 5.1% and 5.2% compared to the published state-of-the-art results. The code is made publicly available.
A deep learning approach to diabetic blood glucose prediction
Venue: arXiv cs.LG 2017
Year: 2017

We consider the question of 30-minute prediction of blood glucose levels measured by continuous glucose monitoring devices, using clinical data. While most studies of this nature deal with one patient at a time, we take a certain percentage of patients in the data set as training data, and test on the remainder of the patients; i.e., the machine need not re-calibrate on the new patients in the data set. We demonstrate how deep learning can outperform shallow networks in this example. One novelty is to demonstrate how a parsimonious deep representation can be constructed using domain knowledge.
Domain-Sharding for Faster HTTP/2 in Lossy Cellular Networks
Venue: arXiv cs.PF 2017
Year: 2017

HTTP/2 (h2) is a new standard for Web communications that already delivers a large share of Web traffic. Unlike HTTP/1, h2 uses only one underlying TCP connection. In a cellular network with high loss and sudden spikes in latency, which the TCP stack might interpret as loss, using a single TCP connection can negatively impact Web performance. In this paper, we perform an extensive analysis of real world cellular network traffic and design a testbed to emulate loss characteristics in cellular networks. We use the emulated cellular network to measure h2 performance in comparison to HTTP/1.1, for webpages synthesized from HTTP Archive repository data. Our results show that, in lossy conditions, h2 achieves faster page load times (PLTs) for webpages with small objects. For webpages with large objects, h2 degrades the PLT. We devise a new domain-sharding technique that isolates large and small object downloads on separate connections. Using sharding, we show that under lossy cellular conditions, h2 over multiple connections improves the PLT compared to h2 with one connection and HTTP/1.1 with six connections. Finally, we recommend content providers and content delivery networks to apply h2-aware domain-sharding on webpages currently served over h2 for improved mobile Web performance.
Graph Filters and the Z-Laplacian
Venue: arXiv cs.SI 2017
Year: 2017

In network science, the interplay between dynamical processes and the underlying topologies of complex systems has led to a diverse family of models with different interpretations. In graph signal processing, this is manifested in the form of different graph shifts and their induced algebraic systems. In this paper, we propose the unifying Z-Laplacian framework, whose instances can act as graph shift operators. As a generalization of the traditional graph Laplacian, the Z-Laplacian spans the space of all possible Z-matrices, i.e., real square matrices with nonpositive off-diagonal entries. We show that the Z-Laplacian can model general continuous-time dynamical processes, including information flows and epidemic spreading on a given graph. It is also closely related to general nonnegative graph filters in the discrete time domain. We showcase its flexibility by considering two applications. First, we consider a wireless communications networking problem modeled with a graph, where the framework can be applied to model the effects of the underlying communications protocol and traffic. Second, we examine a structural brain network from the perspective of low- to high-frequency connectivity.
Secure SURF with Fully Homomorphic Encryption
Venue: arXiv cs.CV 2017
Year: 2017

Cloud computing is an important part of today's world because offloading computations is a method to reduce costs. In this paper, we investigate computing the Speeded Up Robust Features (SURF) using Fully Homomorphic Encryption (FHE). Performing SURF in FHE enables a method to offload the computations while maintaining security and privacy of the original data. In support of this research, we developed a framework to compute SURF via a rational number based compatible with FHE. Although floating point (R) to rational numbers (Q) conversion introduces error, our research provides tight bounds on the magnitude of error in terms of parameters of FHE. We empirically verified the proposed method against a set of images at different sizes and showed that our framework accurately computes most of the SURF keypoints in FHE.
Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
Venue: arXiv cs.LG 2017
Year: 2017

Algorithm-dependent generalization error bounds are central to statistical learning theory. A learning algorithm may use a large hypothesis space, but the limited number of iterations controls its model capacity and generalization error. The impacts of stochastic gradient methods on generalization error for non-convex learning problems not only have important theoretical consequences, but are also critical to generalization errors of deep learning. In this paper, we study the generalization errors of Stochastic Gradient Langevin Dynamics (SGLD) with non-convex objectives. Two theories are proposed with non-asymptotic discrete-time analysis, using Stability and PAC-Bayesian results respectively. The stability-based theory obtains a bound of $O\left(\frac{1}{n}L\sqrt{βT_k}\right)$, where $L$ is uniform Lipschitz parameter, $β$ is inverse temperature, and $T_k$ is aggregated step sizes. For PAC-Bayesian theory, though the bound has a slower $O(1/\sqrt{n})$ rate, the contribution of each step is shown with an exponentially decaying factor by imposing $\ell^2$ regularization, and the uniform Lipschitz constant is also replaced by actual norms of gradients along trajectory. Our bounds have no implicit dependence on dimensions, norms or other capacity measures of parameter, which elegantly characterizes the phenomenon of "Fast Training Guarantees Generalization" in non-convex settings. This is the first algorithm-dependent result with reasonable dependence on aggregated step sizes for non-convex learning, and has important implications to statistical learning aspects of stochastic gradient methods in complicated models such as deep learning.
On recent advances in 2D Constrained Delaunay triangulation algorithms
Venue: arXiv cs.CG 2017
Year: 2017

In this article, recent works on 2D Constrained Delaunay triangulation(CDT) algorithms have been reported. Since the review of CDT algorithms presented by de Floriani(Issues on Machine Vision, Springer Vienna, pg. 95--104, 1989), different algorithms for construction and applications of CDT have appeared in literature each concerned with different aspects of computation and different suitabilities. Therefore, objective of this work is to report an update over that review article considering contemporary prominent algorithms and generalizations for the problem of two dimensional Constrained Delaunay triangulation.
Multidimensional classification of hippocampal shape features discriminates Alzheimer's disease and mild cognitive impairment from normal aging
Venue: arXiv cs.CV 2017
Year: 2017

We describe a new method to automatically discriminate between patients with Alzheimer's disease (AD) or mild cognitive impairment (MCI) and elderly controls, based on multidimensional classification of hippocampal shape features. This approach uses spherical harmonics (SPHARM) coefficients to model the shape of the hippocampi, which are segmented from magnetic resonance images (MRI) using a fully automatic method that we previously developed. SPHARM coefficients are used as features in a classification procedure based on support vector machines (SVM). The most relevant features for classification are selected using a bagging strategy. We evaluate the accuracy of our method in a group of 23 patients with AD (10 males, 13 females, age $\pm$ standard-deviation (SD) = 73 $\pm$ 6 years, mini-mental score (MMS) = 24.4 $\pm$ 2.8), 23 patients with amnestic MCI (10 males, 13 females, age $\pm$ SD = 74 $\pm$ 8 years, MMS = 27.3 $\pm$ 1.4) and 25 elderly healthy controls (13 males, 12 females, age $\pm$ SD = 64 $\pm$ 8 years), using leave-one-out cross-validation. For AD vs controls, we obtain a correct classification rate of 94%, a sensitivity of 96%, and a specificity of 92%. For MCI vs controls, we obtain a classification rate of 83%, a sensitivity of 83%, and a specificity of 84%. This accuracy is superior to that of hippocampal volumetry and is comparable to recently published SVM-based whole-brain classification methods, which relied on a different strategy. This new method may become a useful tool to assist in the diagnosis of Alzheimer's disease.
Orthogonal and Idempotent Transformations for Learning Deep Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

Identity transformations, used as skip-connections in residual networks, directly connect convolutional layers close to the input and those close to the output in deep neural networks, improving information flow and thus easing the training. In this paper, we introduce two alternative linear transforms, orthogonal transformation and idempotent transformation. According to the definition and property of orthogonal and idempotent matrices, the product of multiple orthogonal (same idempotent) matrices, used to form linear transformations, is equal to a single orthogonal (idempotent) matrix, resulting in that information flow is improved and the training is eased. One interesting point is that the success essentially stems from feature reuse and gradient reuse in forward and backward propagation for maintaining the information during flow and eliminating the gradient vanishing problem because of the express way through skip-connections. We empirically demonstrate the effectiveness of the proposed two transformations: similar performance in single-branch networks and even superior in multi-branch networks in comparison to identity transformations.
Computing Tutte Paths
Venue: arXiv cs.DS 2017
Year: 2017

Tutte paths are one of the most successful tools for attacking Hamiltonicity problems in planar graphs. Unfortunately, results based on them are non-constructive, as their proofs inherently use an induction on overlapping subgraphs and these overlaps hinder to bound the running time to a polynomial. For special cases however, computational results of Tutte paths are known: For 4-connected planar graphs, Tutte paths are in fact Hamiltonian paths and Chiba and Nishizeki showed how to compute such paths in linear time. For 3-connected planar graphs, Tutte paths have a more complicated structure, and it has only recently been shown that they can be computed in polynomial time. However, Tutte paths are defined for general 2-connected planar graphs and this is what most applications need. Unfortunately, no computational results are known. We give the first efficient algorithm that computes a Tutte path (for the general case of 2-connected planar graphs). One of the strongest existence results about such Tutte paths is due to Sanders, which allows to prescribe the end vertices and an intermediate edge of the desired path. Encompassing and strengthening all previous computational results on Tutte paths, we show how to compute this special Tutte path efficiently. Our method refines both, the results of Thomassen and Sanders, and avoids overlapping subgraphs by using a novel iterative decomposition along 2-separators. Finally, we show that our algorithm runs in quadratic time.
Towards Release Strategy Optimization for Apps in Google Play
Venue: arXiv cs.SE 2017
Year: 2017

In the appstore-centric ecosystem, app developers have an urgent requirement to optimize their release strategy to maximize the success opportunity of their apps. To address this problem, we introduce an approach to assisting developers to select the proper release opportunity based on the purpose of the update and current condition of the app. Before that, we propose the interval of an update to its previous update to characterize release patterns, and find significance of the release opportunity through empirical analysis. We mined the update-history data of 17,820 apps from 33 categories in Google Play, over a period of 105 days. With 41,028 releases identified from these apps, we reveal important characteristics of update intervals and how these factors can influence update effects. We suggest developers to synthetically consider app ranking, rating trend, and what to update in addition to the opportunity before releasing an app version. We propose a Multinomial Naive Bayes model to help decide an optimal release opportunity to gain better user adoption.
Malware distributions and graph structure of the Web
Venue: arXiv cs.SI 2017
Year: 2017

Knowledge about the graph structure of the Web is important for understanding this complex socio-technical system and for devising proper policies supporting its future development. Knowledge about the differences between clean and malicious parts of the Web is important for understanding potential treats to its users and for devising protection mechanisms. In this study, we conduct data science methods on a large crawl of surface and deep Web pages with the aim to increase such knowledge. To accomplish this, we answer the following questions. Which theoretical distributions explain important local characteristics and network properties of websites? How are these characteristics and properties different between clean and malicious (malware-affected) websites? What is the prediction power of local characteristics and network properties to classify malware websites? To the best of our knowledge, this is the first large-scale study describing the differences in global properties between malicious and clean parts of the Web. In other words, our work is building on and bridging the gap between \textit{Web science} that tackles large-scale graph representations and \textit{Web cyber security} that is concerned with malicious activities on the Web. The results presented herein can also help antivirus vendors in devising approaches to improve their detection algorithms.
Optimized Signaling of Binary Correlated Sources over GMACs
Venue: arXiv cs.IT 2017
Year: 2017

This work focuses on the construction of optimized binary signaling schemes for two-sender uncoded transmission of correlated sources over non-orthogonal Gaussian multiple access channels. Specifically, signal constellations with binary pulse-amplitude-modulation are designed for two senders to optimize the overall system performance. Although the two senders transmit their own messages independently, it is observed that the correlation between message sources can be exploited to mitigate the interference present in the non-orthogonal multiple access channel. Based on a performance analysis under joint maximum-a-posteriori decoding, optimized constellations for various basic waveform correlations between the senders are derived. Numerical results further confirm the effectiveness of the proposed design.
Sentence-level quality estimation by predicting HTER as a multi-component metric
Venue: arXiv cs.CL 2017
Year: 2017

This submission investigates alternative machine learning models for predicting the HTER score on the sentence level. Instead of directly predicting the HTER score, we suggest a model that jointly predicts the amount of the 4 distinct post-editing operations, which are then used to calculate the HTER score. This also gives the possibility to correct invalid (e.g. negative) predicted values prior to the calculation of the HTER score. Without any feature exploration, a multi-layer perceptron with 4 outputs yields small but significant improvements over the baseline.
Deformable Registration through Learning of Context-Specific Metric Aggregation
Venue: arXiv cs.CV 2017
Year: 2017

We propose a novel weakly supervised discriminative algorithm for learning context specific registration metrics as a linear combination of conventional similarity measures. Conventional metrics have been extensively used over the past two decades and therefore both their strengths and limitations are known. The challenge is to find the optimal relative weighting (or parameters) of different metrics forming the similarity measure of the registration algorithm. Hand-tuning these parameters would result in sub optimal solutions and quickly become infeasible as the number of metrics increases. Furthermore, such hand-crafted combination can only happen at global scale (entire volume) and therefore will not be able to account for the different tissue properties. We propose a learning algorithm for estimating these parameters locally, conditioned to the data semantic classes. The objective function of our formulation is a special case of non-convex function, difference of convex function, which we optimize using the concave convex procedure. As a proof of concept, we show the impact of our approach on three challenging datasets for different anatomical structures and modalities.
Shape Generation using Spatially Partitioned Point Clouds
Venue: arXiv cs.CV 2017
Year: 2017

We propose a method to generate 3D shapes using point clouds. Given a point-cloud representation of a 3D shape, our method builds a kd-tree to spatially partition the points. This orders them consistently across all shapes, resulting in reasonably good correspondences across all shapes. We then use PCA analysis to derive a linear shape basis across the spatially partitioned points, and optimize the point ordering by iteratively minimizing the PCA reconstruction error. Even with the spatial sorting, the point clouds are inherently noisy and the resulting distribution over the shape coefficients can be highly multi-modal. We propose to use the expressive power of neural networks to learn a distribution over the shape coefficients in a generative-adversarial framework. Compared to 3D shape generative models trained on voxel-representations, our point-based method is considerably more light-weight and scalable, with little loss of quality. It also outperforms simpler linear factor models such as Probabilistic PCA, both qualitatively and quantitatively, on a number of categories from the ShapeNet dataset. Furthermore, our method can easily incorporate other point attributes such as normal and color information, an additional advantage over voxel-based representations.