OpenRaiser/Intern-Atlas huggingface dataset:
Control-Flow Residual Analysis for Symbolic Automata
Venue: arXiv cs.LO 2017
Year: 2017

Where full static analysis of systems fails to scale up due to system size, dynamic monitoring has been increasingly used to ensure system correctness. The downside is, however, runtime overheads which are induced by the additional monitoring code instrumented. To address this issue, various approaches have been proposed in the literature to use static analysis in order to reduce monitoring overhead. In this paper we generalise existing work which uses control-flow static analysis to optimise properties specified as automata, and prove how similar analysis can be applied to more expressive symbolic automata - enabling reduction of monitoring instrumentation in the system, and also monitoring logic. We also present empirical evidence of the effectiveness of this approach through an analysis of the effect of monitoring overheads in a financial transaction system.
Combining Discrete and Neural Features for Sequence Labeling
Venue: arXiv cs.CL 2017
Year: 2017

Neural network models have recently received heated research attention in the natural language processing community. Compared with traditional models with discrete features, neural models have two main advantages. First, they take low-dimensional, real-valued embedding vectors as inputs, which can be trained over large raw data, thereby addressing the issue of feature sparsity in discrete models. Second, deep neural networks can be used to automatically combine input features, and including non-local features that capture semantic patterns that cannot be expressed using discrete indicator features. As a result, neural network models have achieved competitive accuracies compared with the best discrete models for a range of NLP tasks. On the other hand, manual feature templates have been carefully investigated for most NLP tasks over decades and typically cover the most useful indicator pattern for solving the problems. Such information can be complementary the features automatically induced from neural networks, and therefore combining discrete and neural features can potentially lead to better accuracy compared with models that leverage discrete or neural features only. In this paper, we systematically investigate the effect of discrete and neural feature combination for a range of fundamental NLP tasks based on sequence labeling, including word segmentation, POS tagging and named entity recognition for Chinese and English, respectively. Our results on standard benchmarks show that state-of-the-art neural models can give accuracies comparable to the best discrete models in the literature for most tasks and combing discrete and neural features unanimously yield better results.
A Parallel Algorithm for Generating a Random Graph with a Prescribed Degree Sequence
Venue: arXiv cs.DC 2017
Year: 2017

Random graphs (or networks) have gained a significant increase of interest due to its popularity in modeling and simulating many complex real-world systems. Degree sequence is one of the most important aspects of these systems. Random graphs with a given degree sequence can capture many characteristics like dependent edges and non-binomial degree distribution that are absent in many classical random graph models such as the Erdős-Rényi graph model. In addition, they have important applications in the uniform sampling of random graphs, counting the number of graphs having the same degree sequence, as well as in string theory, random matrix theory, and matching theory. In this paper, we present an OpenMP-based shared-memory parallel algorithm for generating a random graph with a prescribed degree sequence, which achieves a speedup of 20.5 with 32 cores. One of the steps in our parallel algorithm requires checking the Erdős-Gallai characterization, i.e., whether there exists a graph obeying the given degree sequence, in parallel. This paper presents the first non-trivial parallel algorithm for checking the Erdős-Gallai characterization, which achieves a speedup of 23 using 32 cores.
A Computational Interpretation of Context-Free Expressions
Venue: arXiv cs.FL 2017
Year: 2017

We phrase parsing with context-free expressions as a type inhabitation problem where values are parse trees and types are context-free expressions. We first show how containment among context-free and regular expressions can be reduced to a reachability problem by using a canonical representation of states. The proofs-as-programs principle yields a computational interpretation of the reachability problem in terms of a coercion that transforms the parse tree for a context-free expression into a parse tree for a regular expression. It also yields a partial coercion from regular parse trees to context-free ones. The partial coercion from the trivial language of all words to a context-free expression corresponds to a predictive parser for the expression.
Automatic Myocardial Segmentation by Using A Deep Learning Network in Cardiac MRI
Venue: arXiv cs.CV 2017
Year: 2017

Cardiac function is of paramount importance for both prognosis and treatment of different pathologies such as mitral regurgitation, ischemia, dyssynchrony and myocarditis. Cardiac behavior is determined by structural and functional features. In both cases, the analysis of medical imaging studies requires to detect and segment the myocardium. Nowadays, magnetic resonance imaging (MRI) is one of the most relevant and accurate non-invasive diagnostic tools for cardiac structure and function. In this work we propose to use a deep learning technique to assist the automatization of myocardial segmentation in cardiac MRI. We present several improvements to previous works in this paper: we propose to use the Jaccard distance as optimization objective function, we integrate a residual learning strategy into the code, and we introduce a batch normalization layer to train the fully convolutional neural network. Our results demonstrate that this architecture outperforms previous approaches based on a similar network architecture, and that provides a suitable approach for myocardial segmentation. Our benchmark shows that the automatic myocardial segmentation takes less than 22 seg. for a volume of 128~x~128~x~13 pixels in a 3.1 GHz intel core i7.
Preconditioned Spectral Clustering for Stochastic Block Partition Streaming Graph Challenge
Venue: arXiv cs.MS 2017
Year: 2017

Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) is demonstrated to efficiently solve eigenvalue problems for graph Laplacians that appear in spectral clustering. For static graph partitioning, 10-20 iterations of LOBPCG without preconditioning result in ~10x error reduction, enough to achieve 100% correctness for all Challenge datasets with known truth partitions, e.g., for graphs with 5K/.1M (50K/1M) Vertices/Edges in 2 (7) seconds, compared to over 5,000 (30,000) seconds needed by the baseline Python code. Our Python code 100% correctly determines 98 (160) clusters from the Challenge static graphs with 0.5M (2M) vertices in 270 (1,700) seconds using 10GB (50GB) of memory. Our single-precision MATLAB code calculates the same clusters at half time and memory. For streaming graph partitioning, LOBPCG is initiated with approximate eigenvectors of the graph Laplacian already computed for the previous graph, in many cases reducing 2-3 times the number of required LOBPCG iterations, compared to the static case. Our spectral clustering is generic, i.e. assuming nothing specific of the block model or streaming, used to generate the graphs for the Challenge, in contrast to the base code. Nevertheless, in 10-stage streaming comparison with the base code for the 5K graph, the quality of our clusters is similar or better starting at stage 4 (7) for emerging edging (snowballing) streaming, while the computations are over 100-1000 faster.
Hierarchical Multi-scale Attention Networks for Action Recognition
Venue: arXiv cs.CV 2017
Year: 2017

Recurrent Neural Networks (RNNs) have been widely used in natural language processing and computer vision. Among them, the Hierarchical Multi-scale RNN (HM-RNN), a kind of multi-scale hierarchical RNN proposed recently, can learn the hierarchical temporal structure from data automatically. In this paper, we extend the work to solve the computer vision task of action recognition. However, in sequence-to-sequence models like RNN, it is normally very hard to discover the relationships between inputs and outputs given static inputs. As a solution, attention mechanism could be applied to extract the relevant information from input thus facilitating the modeling of input-output relationships. Based on these considerations, we propose a novel attention network, namely Hierarchical Multi-scale Attention Network (HM-AN), by combining the HM-RNN and the attention mechanism and apply it to action recognition. A newly proposed gradient estimation method for stochastic neurons, namely Gumbel-softmax, is exploited to implement the temporal boundary detectors and the stochastic hard attention mechanism. To amealiate the negative effect of sensitive temperature of the Gumbel-softmax, an adaptive temperature training method is applied to better the system performance. The experimental results demonstrate the improved effect of HM-AN over LSTM with attention on the vision task. Through visualization of what have been learnt by the networks, it can be observed that both the attention regions of images and the hierarchical temporal structure can be captured by HM-AN.
On the repeated inversion of a covariance matrix
Venue: arXiv cs.NA 2017
Year: 2017

In many cases, the values of some model parameters are determined by maximising the likelihood of a set of data points given the parameter values. The presence of outliers in the data and correlations between data points complicate this procedure. An efficient procedure for the elimination of outliers is presented which takes the correlations between data points into account.
Revisiting the Centroid-based Method: A Strong Baseline for Multi-Document Summarization
Venue: arXiv cs.CL 2017
Year: 2017

The centroid-based model for extractive document summarization is a simple and fast baseline that ranks sentences based on their similarity to a centroid vector. In this paper, we apply this ranking to possible summaries instead of sentences and use a simple greedy algorithm to find the best summary. Furthermore, we show possi- bilities to scale up to larger input docu- ment collections by selecting a small num- ber of sentences from each document prior to constructing the summary. Experiments were done on the DUC2004 dataset for multi-document summarization. We ob- serve a higher performance over the orig- inal model, on par with more complex state-of-the-art methods.
Evaluation of Deep Learning on an Abstract Image Classification Dataset
Venue: arXiv cs.CV 2017
Year: 2017

Convolutional Neural Networks have become state of the art methods for image classification over the last couple of years. By now they perform better than human subjects on many of the image classification datasets. Most of these datasets are based on the notion of concrete classes (i.e. images are classified by the type of object in the image). In this paper we present a novel image classification dataset, using abstract classes, which should be easy to solve for humans, but variations of it are challenging for CNNs. The classification performance of popular CNN architectures is evaluated on this dataset and variations of the dataset that might be interesting for further research are identified.
$k$-Nearest Neighbor Augmented Neural Networks for Text Classification
Venue: arXiv cs.CL 2017
Year: 2017

In recent years, many deep-learning based models are proposed for text classification. This kind of models well fits the training set from the statistical point of view. However, it lacks the capacity of utilizing instance-level information from individual instances in the training set. In this work, we propose to enhance neural network models by allowing them to leverage information from $k$-nearest neighbor (kNN) of the input text. Our model employs a neural network that encodes texts into text embeddings. Moreover, we also utilize $k$-nearest neighbor of the input text as an external memory, and utilize it to capture instance-level information from the training set. The final prediction is made based on features from both the neural network encoder and the kNN memory. Experimental results on several standard benchmark datasets show that our model outperforms the baseline model on all the datasets, and it even beats a very deep neural network model (with 29 layers) in several datasets. Our model also shows superior performance when training instances are scarce, and when the training set is severely unbalanced. Our model also leverages techniques such as semi-supervised training and transfer learning quite well.
Effective Blog Pages Extractor for Better UGC Accessing
Venue: arXiv cs.IR 2017
Year: 2017

Blog is becoming an increasingly popular media for information publishing. Besides the main content, most of blog pages nowadays also contain noisy information such as advertisements etc. Removing these unrelated elements can improves user experience, but also can better adapt the content to various devices such as mobile phones. Though template-based extractors are highly accurate, they may incur expensive cost in that a large number of template need to be developed and they will fail once the template is updated. To address these issues, we present a novel template-independent content extractor for blog pages. First, we convert a blog page into a DOM-Tree, where all elements including the title and body blocks in a page correspond to subtrees. Then we construct subtree candidate set for the title and the body blocks respectively, and extract both spatial and content features for elements contained in the subtree. SVM classifiers for the title and the body blocks are trained using these features. Finally, the classifiers are used to extract the main content from blog pages. We test our extractor on 2,250 blog pages crawled from nine blog sites with obviously different styles and templates. Experimental results verify the effectiveness of our extractor.
Deep Style Match for Complementary Recommendation
Venue: arXiv cs.AI 2017
Year: 2017

Humans develop a common sense of style compatibility between items based on their attributes. We seek to automatically answer questions like "Does this shirt go well with that pair of jeans?" In order to answer these kinds of questions, we attempt to model human sense of style compatibility in this paper. The basic assumption of our approach is that most of the important attributes for a product in an online store are included in its title description. Therefore it is feasible to learn style compatibility from these descriptions. We design a Siamese Convolutional Neural Network architecture and feed it with title pairs of items, which are either compatible or incompatible. Those pairs will be mapped from the original space of symbolic words into some embedded style space. Our approach takes only words as the input with few preprocessing and there is no laborious and expensive feature engineering.
Navigation Objects Extraction for Better Content Structure Understanding
Venue: arXiv cs.AI 2017
Year: 2017

Existing works for extracting navigation objects from webpages focus on navigation menus, so as to reveal the information architecture of the site. However, web 2.0 sites such as social networks, e-commerce portals etc. are making the understanding of the content structure in a web site increasingly difficult. Dynamic and personalized elements such as top stories, recommended list in a webpage are vital to the understanding of the dynamic nature of web 2.0 sites. To better understand the content structure in web 2.0 sites, in this paper we propose a new extraction method for navigation objects in a webpage. Our method will extract not only the static navigation menus, but also the dynamic and personalized page-specific navigation lists. Since the navigation objects in a webpage naturally come in blocks, we first cluster hyperlinks into different blocks by exploiting spatial locations of hyperlinks, the hierarchical structure of the DOM-tree and the hyperlink density. Then we identify navigation objects from those blocks using the SVM classifier with novel features such as anchor text lengths etc. Experiments on real-world data sets with webpages from various domains and styles verified the effectiveness of our method.
m-TSNE: A Framework for Visualizing High-Dimensional Multivariate Time Series
Venue: arXiv cs.LG 2017
Year: 2017

Multivariate time series (MTS) have become increasingly common in healthcare domains where human vital signs and laboratory results are collected for predictive diagnosis. Recently, there have been increasing efforts to visualize healthcare MTS data based on star charts or parallel coordinates. However, such techniques might not be ideal for visualizing a large MTS dataset, since it is difficult to obtain insights or interpretations due to the inherent high dimensionality of MTS. In this paper, we propose 'm-TSNE': a simple and novel framework to visualize high-dimensional MTS data by projecting them into a low-dimensional (2-D or 3-D) space while capturing the underlying data properties. Our framework is easy to use and provides interpretable insights for healthcare professionals to understand MTS data. We evaluate our visualization framework on two real-world datasets and demonstrate that the results of our m-TSNE show patterns that are easy to understand while the other methods' visualization may have limitations in interpretability.
Maximum A Posteriori Estimation of Distances Between Deep Features in Still-to-Video Face Recognition
Venue: arXiv cs.CV 2017
Year: 2017

The paper deals with the still-to-video face recognition for the small sample size problem based on computation of distances between high-dimensional deep bottleneck features. We present the novel statistical recognition method, in which the still-to-video recognition task is casted into Maximum A Posteriori estimation. In this method we maximize the joint probabilistic density of the distances to all reference still images. It is shown that this likelihood can be estimated with the known asymptotically normal distribution of the Kullback-Leibler discriminations between nonnegative features. The experimental study with the LFW (Labeled Faces in the Wild), YTF (YouTube Faces) and IJB-A (IARPA Janus Benchmark A) datasets has been provided. We demonstrated, that the proposed approach can be applied with the state-of-the-art deep features and dissimilarity measures. Our algorithm achieves 3-5% higher accuracy when compared with conventional aggregation of decisions obtained for all frames.
A Model for Donation Verification
Venue: arXiv cs.DS 2017
Year: 2017

In this paper, we introduce a model for donation verification. A randomized algorithm is developed to check if the money claimed being received by the collector is $(1-ε)$-approximation to the total amount money contributed by the donors. We also derive some negative results that show it is impossible to verify the donations under some circumstances.
Gatherplots: Generalized Scatterplots for Nominal Data
Venue: arXiv cs.HC 2017
Year: 2017

Overplotting of data points is a common problem when visualizing large datasets in a scatterplot, particularly when mapping nominal dimensions to one of the scatterplot axes. Transparency, aggregation, and jittering have previously been suggested to address this issue, but these solutions all have drawbacks for assessing the data distribution in the plot. We propose gatherplots, an extension of scatterplots that eliminates overplotting, particularly for nominal variables. In gatherplots, every data point that maps to the same position coalesces to form a stacked entity, thereby making it easier to compare the absolute and relative sizes of data groupings. The size and aspect ratio of data points can also be changed dynamically to make it easier to compare the composition of different groups. Furthermore, several embedded interaction techniques support slicing and dicing the gatherplot by pivoting on particular dimensions, ranges, and values in the dataset. Our evaluation shows that gatherplots enable users from the general public to judge the relative portion of subgroups more quickly and more correctly than when using conventional scatterplots with jittering. Furthermore, a review conducted by a group of visualization experts evaluated and commented on the gatherplot design.
Part-to-whole Registration of Histology and MRI using Shape Elements
Venue: arXiv cs.CV 2017
Year: 2017

Image registration between histology and magnetic resonance imaging (MRI) is a challenging task due to differences in structural content and contrast. Too thick and wide specimens cannot be processed all at once and must be cut into smaller pieces. This dramatically increases the complexity of the problem, since each piece should be individually and manually pre-aligned. To the best of our knowledge, no automatic method can reliably locate such piece of tissue within its respective whole in the MRI slice, and align it without any prior information. We propose here a novel automatic approach to the joint problem of multimodal registration between histology and MRI, when only a fraction of tissue is available from histology. The approach relies on the representation of images using their level lines so as to reach contrast invariance. Shape elements obtained via the extraction of bitangents are encoded in a projective-invariant manner, which permits the identification of common pieces of curves between two images. We evaluated the approach on human brain histology and compared resulting alignments against manually annotated ground truths. Considering the complexity of the brain folding patterns, preliminary results are promising and suggest the use of characteristic and meaningful shape elements for improved robustness and efficiency.
Measuring social spam and the effect of bots on information diffusion in social media
Venue: arXiv cs.SI 2017
Year: 2017

Bots have been playing a crucial role in online platform ecosystems, as efficient and automatic tools to generate content and diffuse information to the social media human population. In this chapter, we will discuss the role of social bots in content spreading dynamics in social media. In particular, we will first investigate some differences between diffusion dynamics of content generated by bots, as opposed to humans, in the context of political communication, then study the characteristics of bots behind the diffusion dynamics of social media spam campaigns.
Study of Set-Membership Kernel Adaptive Algorithms and Applications
Venue: arXiv cs.LG 2017
Year: 2017

Adaptive algorithms based on kernel structures have been a topic of significant research over the past few years. The main advantage is that they form a family of universal approximators, offering an elegant solution to problems with nonlinearities. Nevertheless these methods deal with kernel expansions, creating a growing structure also known as dictionary, whose size depends on the number of new inputs. In this paper we derive the set-membership kernel-based normalized least-mean square (SM-NKLMS) algorithm, which is capable of limiting the size of the dictionary created in stationary environments. We also derive as an extension the set-membership kernelized affine projection (SM-KAP) algorithm. Finally several experiments are presented to compare the proposed SM-NKLMS and SM-KAP algorithms to the existing methods.