OpenRaiser/Intern-Atlas huggingface dataset:
Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing
Venue: arXiv cs.DS 2018
Year: 2018

Given a string $S$, the \emph{compressed indexing problem} is to preprocess $S$ into a compressed representation that supports fast \emph{substring queries}. The goal is to use little space relative to the compressed size of $S$ while supporting fast queries. We present a compressed index based on the Lempel--Ziv 1977 compression scheme. We obtain the following time-space trade-offs: For constant-sized alphabets; (i) $O(m + occ \lg\lg n)$ time using $O(z\lg(n/z)\lg\lg z)$ space, or (ii) $O(m(1 + \frac{\lg^εz}{\lg(n/z)}) + occ(\lg\lg n + \lg^εz))$ time using $O(z\lg(n/z))$ space. For integer alphabets polynomially bounded by $n$; (iii) $O(m(1 + \frac{\lg^εz}{\lg(n/z)}) + occ(\lg\lg n + \lg^εz))$ time using $O(z(\lg(n/z) + \lg\lg z))$ space, or (iv) $O(m + occ(\lg\lg n + \lg^ε z))$ time using $O(z(\lg(n/z) + \lg^ε z))$ space, where $n$ and $m$ are the length of the input string and query string respectively, $z$ is the number of phrases in the LZ77 parse of the input string, $occ$ is the number of occurrences of the query in the input and $ε> 0$ is an arbitrarily small constant. In particular, (i) improves the leading term in the query time of the previous best solution from $O(m\lg m)$ to $O(m)$ at the cost of increasing the space by a factor $\lg \lg z$. Alternatively, (ii) matches the previous best space bound, but has a leading term in the query time of $O(m(1+\frac{\lg^ε z}{\lg (n/z)}))$. However, for any polynomial compression ratio, i.e., $z = O(n^{1-δ})$, for constant $δ> 0$, this becomes $O(m)$. Our index also supports extraction of any substring of length $\ell$ in $O(\ell + \lg(n/z))$ time. Technically, our results are obtained by novel extensions and combinations of existing data structures of independent interest, including a new batched variant of weak prefix search.
Bounds on Codes Correcting Tandem and Palindromic Duplications
Venue: arXiv cs.IT 2018
Year: 2018

In this work, we derive upper bounds on the cardinality of tandem duplication and palindromic deletion correcting codes by deriving the generalized sphere packing bound for these error types. We first prove that an upper bound for tandem deletions is also an upper bound for inserting the respective type of duplications. Therefore, we derive the bounds based on these special deletions as this results in tighter bounds. We determine the spheres for tandem and palindromic duplications/deletions and the number of words with a specific sphere size. Our upper bounds on the cardinality directly imply lower bounds on the redundancy which we compare with the redundancy of the best known construction correcting arbitrary burst errors. Our results indicate that the correction of palindromic duplications requires more redundancy than the correction of tandem duplications. Further, there is a significant gap between the minimum redundancy of duplication correcting codes and burst insertion correcting codes.
A Roadmap for the Development of the "SP Machine" for Artificial Intelligence
Venue: arXiv cs.AI 2018
Year: 2018

This paper describes a roadmap for the development of the "SP Machine", based on the "SP Theory of Intelligence" and its realisation in the "SP Computer Model". The SP Machine will be developed initially as a software virtual machine with high levels of parallel processing, hosted on a high-performance computer. The system should help users visualise knowledge structures and processing. Research is needed into how the system may discover low-level features in speech and in images. Strengths of the SP System in the processing of natural language may be augmented, in conjunction with the further development of the SP System's strengths in unsupervised learning. Strengths of the SP System in pattern recognition may be developed for computer vision. Work is needed on the representation of numbers and the performance of arithmetic processes. A computer model is needed of "SP-Neural", the version of the SP Theory expressed in terms of neurons and their inter-connections. The SP Machine has potential in many areas of application, several of which may be realised on short-to-medium timescales.
Multi-period Time Series Modeling with Sparsity via Bayesian Variational Inference
Venue: arXiv cs.NE 2018
Year: 2018

In this paper, we use augmented the hierarchical latent variable model to model multi-period time series, where the dynamics of time series are governed by factors or trends in multiple periods. Previous methods based on stacked recurrent neural network (RNN) and deep belief network (DBN) models cannot model the tendencies in multiple periods, and no models for sequential data pay special attention to redundant input variables which have no or even negative impact on prediction and modeling. Applying hierarchical latent variable model with multiple transition periods, our proposed algorithm can capture dependencies in different temporal resolutions. Introducing Bayesian neural network with Horseshoe prior as input network, we can discard the redundant input variables in the optimization process, concurrently with the learning of other parts of the model. Based on experiments with both synthetic and real-world data, we show that the proposed method significantly improves the modeling and prediction performance on multi-period time series.
Mapping the Americanization of English in Space and Time
Venue: arXiv cs.CL 2018
Year: 2018

As global political preeminence gradually shifted from the United Kingdom to the United States, so did the capacity to culturally influence the rest of the world. In this work, we analyze how the world-wide varieties of written English are evolving. We study both the spatial and temporal variations of vocabulary and spelling of English using a large corpus of geolocated tweets and the Google Books datasets corresponding to books published in the US and the UK. The advantage of our approach is that we can address both standard written language (Google Books) and the more colloquial forms of microblogging messages (Twitter). We find that American English is the dominant form of English outside the UK and that its influence is felt even within the UK borders. Finally, we analyze how this trend has evolved over time and the impact that some cultural events have had in shaping it.
Decision-Making and Biases in Cybersecurity Capability Development: Evidence from a Simulation Game Experiment
Venue: arXiv cs.CR 2018
Year: 2018

We developed a simulation game to study the effectiveness of decision-makers in overcoming two complexities in building cybersecurity capabilities: potential delays in capability development; and uncertainties in predicting cyber incidents. Analyzing 1,479 simulation runs, we compared the performances of a group of experienced professionals with those of an inexperienced control group. Experienced subjects did not understand the mechanisms of delays any better than inexperienced subjects; however, experienced subjects were better able to learn the need for proactive decision-making through an iterative process. Both groups exhibited similar errors when dealing with the uncertainty of cyber incidents. Our findings highlight the importance of training for decision-makers with a focus on systems thinking skills, and lay the groundwork for future research on uncovering mental biases about the complexities of cybersecurity.
Discriminative Localization in CNNs for Weakly-Supervised Segmentation of Pulmonary Nodules
Venue: arXiv cs.CV 2018
Year: 2018

Automated detection and segmentation of pulmonary nodules on lung computed tomography (CT) scans can facilitate early lung cancer diagnosis. Existing supervised approaches for automated nodule segmentation on CT scans require voxel-based annotations for training, which are labor- and time-consuming to obtain. In this work, we propose a weakly-supervised method that generates accurate voxel-level nodule segmentation trained with image-level labels only. By adapting a convolutional neural network (CNN) trained for image classification, our proposed method learns discriminative regions from the activation maps of convolution units at different scales, and identifies the true nodule location with a novel candidate-screening framework. Experimental results on the public LIDC-IDRI dataset demonstrate that, our weakly-supervised nodule segmentation framework achieves competitive performance compared to a fully-supervised CNN-based segmentation method.
Direct interactive visualization of locally refined spline volumes for scalar and vector fields
Venue: arXiv cs.GR 2018
Year: 2018

We present a novel approach enabling interactive visualization of volumetric Locally Refined B-splines (LR-splines). To this end we propose a highly efficient algorithm for direct visualization of scalar and vector fields given by an LR-spline. In both cases, our main contribution to achieve interactive frame rates is an acceleration structure for fast element look-up and a change of basis for efficient evaluation. To further improve the efficiency, we present a heuristic for adaptive sampling distance for the numerical integration. A comparison with existing adaptive approaches is performed. The algorithms are designed to fully utilize modern graphics processing unit (GPU) capabilities. Important applications where LR-spline volumes emerge are given for instance by approximation of large-scale simulation and sensor data, and Isogeometric Analysis (IGA). We showcase interactive rendering achieved by our approach on different representative use cases, stemming from simulations of wind flow around a telescope, Magnetic Resonance (MR) imaging of a human brain, and simulations of a fluidized bed used for mixing and coating particles in industrial processes.
Eclipse: Practicability Beyond kNN and Skyline
Venue: arXiv cs.DB 2018
Year: 2018

The $k$ nearest neighbor ($k$NN) query is a fundamental problem in databases. Given a set of multidimensional data points and a query point, $k$NN returns the $k$ nearest neighbors based on a scoring function such as weighted sum given an attribute weight vector. However, the attribute weight vector can be difficult to specify in practice. Skyline returns the points including all possible nearest neighbors without requiring the exact attribute weight vector or a scoring function but the number of returned points can be prohibitively large for practical use. In this paper, we propose a novel \emph{eclipse} definition which provides a more flexible and customizable definition than the classic $1$NN and skyline. In eclipse, users can specify a range of attribute weights and control the number of returned points. We show that both $1$NN and skyline are instantiations of eclipse. To compute eclipse points, we propose a baseline algorithm with time complexity of $O(n^22^{d-1})$, and an improved $O(n\log ^{d-1}n)$ time transformation-based algorithm by transforming the eclipse problem to the skyline problem, where $n$ is the number of points and $d$ is the number of dimensions. Furthermore, we propose a novel index-based algorithm utilizing duality transform with much better efficiency. The experimental results on the real NBA dataset and the synthetic datasets demonstrate the effectiveness and efficiency of our eclipse algorithms.
Placing your Coins on a Shelf
Venue: arXiv cs.CG 2018
Year: 2018

We consider the problem of packing a family of disks "on a shelf", that is, such that each disk touches the $x$-axis from above and such that no two disks overlap. We prove that the problem of minimizing the distance between the leftmost point and the rightmost point of any disk is NP-hard. On the positive side, we show how to approximate this problem within a factor of 4/3 in $O(n \log n)$ time, and provide an $O(n \log n)$-time exact algorithm for a special case, in particular when the ratio between the largest and smallest radius is at most four.
Multimedia Semantic Integrity Assessment Using Joint Embedding Of Images And Text
Venue: arXiv cs.MM 2018
Year: 2018

Real world multimedia data is often composed of multiple modalities such as an image or a video with associated text (e.g. captions, user comments, etc.) and metadata. Such multimodal data packages are prone to manipulations, where a subset of these modalities can be altered to misrepresent or repurpose data packages, with possible malicious intent. It is, therefore, important to develop methods to assess or verify the integrity of these multimedia packages. Using computer vision and natural language processing methods to directly compare the image (or video) and the associated caption to verify the integrity of a media package is only possible for a limited set of objects and scenes. In this paper, we present a novel deep learning-based approach for assessing the semantic integrity of multimedia packages containing images and captions, using a reference set of multimedia packages. We construct a joint embedding of images and captions with deep multimodal representation learning on the reference dataset in a framework that also provides image-caption consistency scores (ICCSs). The integrity of query media packages is assessed as the inlierness of the query ICCSs with respect to the reference dataset. We present the MultimodAl Information Manipulation dataset (MAIM), a new dataset of media packages from Flickr, which we make available to the research community. We use both the newly created dataset as well as Flickr30K and MS COCO datasets to quantitatively evaluate our proposed approach. The reference dataset does not contain unmanipulated versions of tampered query packages. Our method is able to achieve F1 scores of 0.75, 0.89 and 0.94 on MAIM, Flickr30K and MS COCO, respectively, for detecting semantically incoherent media packages.
Buildup of Speaking Skills in an Online Learning Community: A Network-Analytic Exploration
Venue: arXiv cs.SI 2018
Year: 2018

In this study, we explore peer-interaction effects in online networks on speaking skill development. In particular, we present an evidence for gradual buildup of skills in a small-group setting that has not been reported in the literature. We introduce a novel dataset of six online communities consisting of 158 participants focusing on improving their speaking skills. They video-record speeches for 5 prompts in 10 days and exchange comments and performance-ratings with their peers. We ask (i) whether the participants' ratings are affected by their interaction patterns with peers, and (ii) whether there is any gradual buildup of speaking skills in the communities towards homogeneity. To analyze the data, we employ tools from the emerging field of Graph Signal Processing (GSP). GSP enjoys a distinction from Social Network Analysis in that the latter is concerned primarily with the connection structures of graphs, while the former studies signals on top of graphs. We study the performance ratings of the participants as graph signals atop underlying interaction topologies. Total variation analysis of the graph signals show that the participants' rating differences decrease with time (slope=-0.04, p<0.01), while average ratings increase (slope=0.07, p<0.05)--thereby gradually building up the ratings towards community-wide homogeneity. We provide evidence for peer-influence through a prediction formulation. Our consensus-based prediction model outperforms baseline network-agnostic regression models by about 23% in predicting performance ratings. This, in turn, shows that participants' ratings are affected by their peers' ratings and the associated interaction patterns, corroborating previous findings. Then, we formulate a consensus-based diffusion model that captures these observations of peer-influence from our analyses.
Learning Representations and Generative Models for 3D Point Clouds
Venue: arXiv cs.CV 2018
Year: 2018

Three-dimensional geometric data offer an excellent domain for studying representation learning and generative modeling. In this paper, we look at geometric data represented as point clouds. We introduce a deep AutoEncoder (AE) network with state-of-the-art reconstruction quality and generalization ability. The learned representations outperform existing methods on 3D recognition tasks and enable shape editing via simple algebraic manipulations, such as semantic part editing, shape analogies and shape interpolation, as well as shape completion. We perform a thorough study of different generative models including GANs operating on the raw point clouds, significantly improved GANs trained in the fixed latent space of our AEs, and Gaussian Mixture Models (GMMs). To quantitatively evaluate generative models we introduce measures of sample fidelity and diversity based on matchings between sets of point clouds. Interestingly, our evaluation of generalization, fidelity and diversity reveals that GMMs trained in the latent space of our AEs yield the best results overall.
Model-Based Speech Enhancement in the Modulation Domain
Venue: arXiv cs.SD 2018
Year: 2018

This paper presents an algorithm for modulation-domain speech enhancement using a Kalman filter. The proposed estimator jointly models the estimated dynamics of the spectral amplitudes of speech and noise to obtain an MMSE estimation of the speech amplitude spectrum with the assumption that the speech and noise are additive in the complex domain. In order to include the dynamics of noise amplitudes with those of speech amplitudes, we propose a statistical "Gaussring" model that comprises a mixture of Gaussians whose centers lie in a circle on the complex plane. The performance of the proposed algorithm is evaluated using the perceptual evaluation of speech quality measure, segmental SNR measure, and short-time objective intelligibility measure. For speech quality measures, the proposed algorithm is shown to give a consistent improvement over a wide range of SNRs when compared to competitive algorithms. Speech recognition experiments also show that the Gaussring-model-based algorithm performs well for two types of noise.
A Human and Group Behaviour Simulation Evaluation Framework utilising Composition and Video Analysis
Venue: arXiv cs.CV 2018
Year: 2018

In this work we present the modular Crowd Simulation Evaluation through Composition framework (CSEC) which provides a quantitative comparison between different pedestrian and crowd simulation approaches. Evaluation is made based on the comparison of source footage against synthetic video created through novel composition techniques. The proposed framework seeks to reduce the complexity of simulation evaluation and provide a platform from which the comparison of differing simulation algorithms as well as parametric tuning can be conducted to improve simulation accuracy or providing measures of similarity between crowd simulation algorithms and source data. Through the use of features designed to mimic the Human Visual System (HVS), specific simulation properties can be evaluated relative to sample footage. Validation was performed on a number of popular crowd datasets and through comparisons of multiple pedestrian and crowd simulation algorithms.
Automatic Construction of Real-World Datasets for 3D Object Localization using Two Cameras
Venue: arXiv cs.CV 2018
Year: 2018

Unlike classification, position labels cannot be assigned manually by humans. For this reason, generating supervision for precise object localization is a hard task. This paper details a method to create large datasets for 3D object localization, with real world images, using an industrial robot to generate position labels. By knowledge of the geometry of the robot, we are able to automatically synchronize the images of the two cameras and the object 3D position. We applied it to generate a screw-driver localization dataset with stereo images, using a KUKA LBR iiwa robot. This dataset could then be used to train a CNN regressor to learn end-to-end stereo object localization from a set of two standard uncalibrated cameras.
Joint Pilot Design and Uplink Power Allocation in Multi-Cell Massive MIMO Systems
Venue: arXiv cs.IT 2018
Year: 2018

This paper considers pilot design to mitigate pilot contamination and provide good service for everyone in multi-cell Massive multiple input multiple output (MIMO) systems. Instead of modeling the pilot design as a combinatorial assignment problem, as in prior works, we express the pilot signals using a pilot basis and treat the associated power coefficients as continuous optimization variables. We compute a lower bound on the uplink capacity for Rayleigh fading channels with maximum ratio detection that applies with arbitrary pilot signals. We further formulate the max-min fairness problem under power budget constraints, with the pilot signals and data powers as optimization variables. Because this optimization problem is non-deterministic polynomial-time hard due to signomial constraints, we then propose an algorithm to obtain a local optimum with polynomial complexity. Our framework serves as a benchmark for pilot design in scenarios with either ideal or non-ideal hardware. Numerical results manifest that the proposed optimization algorithms are close to the optimal solution obtained by exhaustive search for different pilot assignments and the new pilot structure and optimization bring large gains over the state-of-the-art suboptimal pilot design.
Malware in the Future? Forecasting of Analyst Detection of Cyber Events
Venue: arXiv cs.CR 2018
Year: 2018

There have been extensive efforts in government, academia, and industry to anticipate, forecast, and mitigate cyber attacks. A common approach is time-series forecasting of cyber attacks based on data from network telescopes, honeypots, and automated intrusion detection/prevention systems. This research has uncovered key insights such as systematicity in cyber attacks. Here, we propose an alternate perspective of this problem by performing forecasting of attacks that are analyst-detected and -verified occurrences of malware. We call these instances of malware cyber event data. Specifically, our dataset was analyst-detected incidents from a large operational Computer Security Service Provider (CSSP) for the U.S. Department of Defense, which rarely relies only on automated systems. Our data set consists of weekly counts of cyber events over approximately seven years. Since all cyber events were validated by analysts, our dataset is unlikely to have false positives which are often endemic in other sources of data. Further, the higher-quality data could be used for a number for resource allocation, estimation of security resources, and the development of effective risk-management strategies. We used a Bayesian State Space Model for forecasting and found that events one week ahead could be predicted. To quantify bursts, we used a Markov model. Our findings of systematicity in analyst-detected cyber attacks are consistent with previous work using other sources. The advanced information provided by a forecast may help with threat awareness by providing a probable value and range for future cyber events one week ahead. Other potential applications for cyber event forecasting include proactive allocation of resources and capabilities for cyber defense (e.g., analyst staffing and sensor configuration) in CSSPs. Enhanced threat awareness may improve cybersecurity.
A simple but tough-to-beat baseline for the Fake News Challenge stance detection task
Venue: arXiv cs.CL 2018
Year: 2018

Identifying public misinformation is a complicated and challenging task. An important part of checking the veracity of a specific claim is to evaluate the stance different news sources take towards the assertion. Automatic stance evaluation, i.e. stance detection, would arguably facilitate the process of fact checking. In this paper, we present our stance detection system which claimed third place in Stage 1 of the Fake News Challenge. Despite our straightforward approach, our system performs at a competitive level with the complex ensembles of the top two winning teams. We therefore propose our system as the 'simple but tough-to-beat baseline' for the Fake News Challenge stance detection task.