OpenRaiser/Intern-Atlas huggingface dataset:
Universum Prescription: Regularization using Unlabeled Data
Venue: arXiv cs.LG 2016
Year: 2016

This paper shows that simply prescribing "none of the above" labels to unlabeled data has a beneficial regularization effect to supervised learning. We call it universum prescription by the fact that the prescribed labels cannot be one of the supervised labels. In spite of its simplicity, universum prescription obtained competitive results in training deep convolutional networks for CIFAR-10, CIFAR-100, STL-10 and ImageNet datasets. A qualitative justification of these approaches using Rademacher complexity is presented. The effect of a regularization parameter -- probability of sampling from unlabeled data -- is also studied empirically.
Combining Monte-Carlo and Hyper-heuristic methods for the Multi-mode Resource-constrained Multi-project Scheduling Problem
Venue: arXiv cs.DS 2016
Year: 2016

Multi-mode resource and precedence-constrained project scheduling is a well-known challenging real-world optimisation problem. An important variant of the problem requires scheduling of activities for multiple projects considering availability of local and global resources while respecting a range of constraints. A critical aspect of the benchmarks addressed in this paper is that the primary objective is to minimise the sum of the project completion times, with the usual makespan minimisation as a secondary objective. We observe that this leads to an expected different overall structure of good solutions and discuss the effects this has on the algorithm design. This paper presents a carefully designed hybrid of Monte-Carlo tree search, novel neighbourhood moves, memetic algorithms, and hyper-heuristic methods. The implementation is also engineered to increase the speed with which iterations are performed, and to exploit the computing power of multicore machines. Empirical evaluation shows that the resulting information-sharing multi-component algorithm significantly outperforms other solvers on a set of "hidden" instances, i.e. instances not available at the algorithm design phase.
Constructing Permutation Arrays from Groups
Venue: arXiv cs.DM 2016
Year: 2016

Let M(n, d) be the maximum size of a permutation array on n symbols with pairwise Hamming distance at least d. We use various combinatorial, algebraic, and computational methods to improve lower bounds for M(n, d). We compute the Hamming distances of affine semilinear groups and projective semilinear groups, and unions of cosets of AGL(1,q) and PGL(2,q) with Frobenius maps to obtain new, improved lower bounds for M(n,d). We give new randomized algorithms. We give better lower bounds for M(n,d) also using new theorems concerning the contraction operation. For example, we prove a quadratic lower bound for M(n,n-2) for all n=2 (mod 3) such that n+1 is a prime power.
A System for Compressive Sensing Signal Reconstruction
Venue: arXiv cs.IT 2016
Year: 2016

An architecture for hardware realization of a system for sparse signal reconstruction is presented. The threshold based reconstruction method is considered, which is further modified in this paper to reduce the system complexity in order to provide easier hardware realization. Instead of using the partial random Fourier transform matrix, the minimization problem is reformulated using only the triangular R matrix from the QR decomposition. The triangular R matrix can be efficiently implemented in hardware without calculating the orthogonal Q matrix. A flexible and scalable realization of matrix R is proposed, such that the size of R changes with the number of available samples and sparsity level.
Flush+Flush: A Fast and Stealthy Cache Attack
Venue: arXiv cs.CR 2016
Year: 2016

Research on cache attacks has shown that CPU caches leak significant information. Proposed detection mechanisms assume that all cache attacks cause more cache hits and cache misses than benign applications and use hardware performance counters for detection. In this article, we show that this assumption does not hold by developing a novel attack technique: the Flush+Flush attack. The Flush+Flush attack only relies on the execution time of the flush instruction, which depends on whether data is cached or not. Flush+Flush does not make any memory accesses, contrary to any other cache attack. Thus, it causes no cache misses at all and the number of cache hits is reduced to a minimum due to the constant cache flushes. Therefore, Flush+Flush attacks are stealthy, i.e., the spy process cannot be detected based on cache hits and misses, or state-of-the-art detection mechanisms. The Flush+Flush attack runs in a higher frequency and thus is faster than any existing cache attack. With 496 KB/s in a cross-core covert channel it is 6.7 times faster than any previously published cache covert channel.
Motion Planning for Global Localization in Non-Gaussian Belief Spaces
Venue: arXiv cs.RO 2016
Year: 2016

This paper presents a method for motion planning under uncertainty to deal with situations where ambiguous data associations result in a multimodal hypothesis on the robot state. In the global localization problem, sometimes referred to as the "lost or kidnapped robot problem", given little to no a priori pose information, the localization algorithm should recover the correct pose of a mobile robot with respect to a global reference frame. We present a Receding Horizon approach, to plan actions that sequentially disambiguate a multimodal belief to achieve tight localization on the correct pose in finite time, i.e., converge to a unimodal belief. Experimental results are presented using a physical ground robot operating in an artificial maze-like environment. We demonstrate two runs wherein the robot is given no a priori information about its initial pose and the planner is tasked to localize the robot.
Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
Venue: arXiv cs.IT 2016
Year: 2016

We consider the problem of recovering a complete (i.e., square and invertible) matrix $\mathbf A_0$, from $\mathbf Y \in \mathbb{R}^{n \times p}$ with $\mathbf Y = \mathbf A_0 \mathbf X_0$, provided $\mathbf X_0$ is sufficiently sparse. This recovery problem is central to theoretical understanding of dictionary learning, which seeks a sparse representation for a collection of input signals and finds numerous applications in modern signal processing and machine learning. We give the first efficient algorithm that provably recovers $\mathbf A_0$ when $\mathbf X_0$ has $O(n)$ nonzeros per column, under suitable probability model for $\mathbf X_0$. Our algorithmic pipeline centers around solving a certain nonconvex optimization problem with a spherical constraint, and hence is naturally phrased in the language of manifold optimization. In a companion paper (arXiv:1511.03607), we have showed that with high probability our nonconvex formulation has no "spurious" local minimizers and around any saddle point the objective function has a negative directional curvature. In this paper, we take advantage of the particular geometric structure, and describe a Riemannian trust region algorithm that provably converges to a local minimizer with from arbitrary initializations. Such minimizers give excellent approximations to rows of $\mathbf X_0$. The rows are then recovered by linear programming rounding and deflation.
Performing Highly Accurate Predictions Through Convolutional Networks for Actual Telecommunication Challenges
Venue: arXiv cs.LG 2016
Year: 2016

We investigated how the application of deep learning, specifically the use of convolutional networks trained with GPUs, can help to build better predictive models in telecommunication business environments, and fill this gap. In particular, we focus on the non-trivial problem of predicting customer churn in telecommunication operators. Our model, called WiseNet, consists of a convolutional network and a novel encoding method that transforms customer activity data and Call Detail Records (CDRs) into images. Experimental evaluation with several machine learning classifiers supports the ability of WiseNet for learning features when using structured input data. For this type of telecommunication business problems, we found that WiseNet outperforms machine learning models with hand-crafted features, and does not require the labor-intensive step of feature engineering. Furthermore, the same model has been applied without retraining to a different market, achieving consistent results. This confirms the generalization property of WiseNet and the ability to extract useful representations.
PageRank in undirected random graphs
Venue: arXiv cs.SI 2016
Year: 2016

PageRank has numerous applications in information retrieval, reputation systems, machine learning, and graph partitioning.In this paper, we study PageRank in undirected random graphs with expansion property. The Chung-Lu random graph representsan example of such graphs. We show that in the limit, as the size of the graph goes to infinity, PageRank can be represented by a mixture of the restart distribution and the vertex degree distribution.
A genetic algorithm to discover flexible motifs with support
Venue: arXiv cs.LG 2016
Year: 2016

Finding repeated patterns or motifs in a time series is an important unsupervised task that has still a number of open issues, starting by the definition of motif. In this paper, we revise the notion of motif support, characterizing it as the number of patterns or repetitions that define a motif. We then propose GENMOTIF, a genetic algorithm to discover motifs with support which, at the same time, is flexible enough to accommodate other motif specifications and task characteristics. GENMOTIF is an anytime algorithm that easily adapts to many situations: searching in a range of segment lengths, applying uniform scaling, dealing with multiple dimensions, using different similarity and grouping criteria, etc. GENMOTIF is also parameter-friendly: it has only two intuitive parameters which, if set within reasonable bounds, do not substantially affect its performance. We demonstrate the value of our approach in a number of synthetic and real-world settings, considering traffic volume measurements, accelerometer signals, and telephone call records.
Joint Training of Generic CNN-CRF Models with Stochastic Optimization
Venue: arXiv cs.CV 2016
Year: 2016

We propose a new CNN-CRF end-to-end learning framework, which is based on joint stochastic optimization with respect to both Convolutional Neural Network (CNN) and Conditional Random Field (CRF) parameters. While stochastic gradient descent is a standard technique for CNN training, it was not used for joint models so far. We show that our learning method is (i) general, i.e. it applies to arbitrary CNN and CRF architectures and potential functions; (ii) scalable, i.e. it has a low memory footprint and straightforwardly parallelizes on GPUs; (iii) easy in implementation. Additionally, the unified CNN-CRF optimization approach simplifies a potential hardware implementation. We empirically evaluate our method on the task of semantic labeling of body parts in depth images and show that it compares favorably to competing techniques.
Which type of citation analysis generates the most accurate taxonomy of scientific and technical knowledge?
Venue: arXiv cs.DL 2016
Year: 2016

In 1965, Derek de Solla Price foresaw the day when a citation-based taxonomy of science and technology would be delineated and correspondingly used for science policy. A taxonomy needs to be comprehensive and accurate if it is to be useful for policy making, especially now that policy makers are utilizing citation-based indicators to evaluate people, institutions and laboratories. Determining the accuracy of a taxonomy, however, remains a challenge. Previous work on the accuracy of partition solutions is sparse, and the results of those studies, while useful, have not been definitive. In this study we compare the accuracies of topic-level taxonomies based on the clustering of documents using direct citation, bibliographic coupling, and co-citation. Using a set of new gold standards - articles with at least 100 references - we find that direct citation is better at concentrating references than either bibliographic coupling or co-citation. Using the assumption that higher concentrations of references denote more accurate clusters, direct citation thus provides a more accurate representation of the taxonomy of scientific and technical knowledge than either bibliographic coupling or co-citation. We also find that discipline-level taxonomies based on journal schema are highly inaccurate compared to topic-level taxonomies, and recommend against their use.
Mixed Monotonicity of Partial First-In-First-Out Traffic Flow Models
Venue: arXiv cs.SY 2016
Year: 2016

In vehicle traffic networks, congestion on one outgoing link of a diverging junction often impedes flow to other outgoing links, a phenomenon known as the first-in-first-out (FIFO) property. Simplified traffic models that do not account for the FIFO property result in monotone dynamics for which powerful analysis techniques exist. FIFO models are in general not monotone, but have been shown to be mixed monotone - a generalization of monotonicity that enables similarly powerful analysis techniques. In this paper, we study traffic flow models for which the FIFO property is only partial, that is, flows at diverging junctions exhibit a combination of FIFO and non-FIFO phenomena. We show that mixed monotonicity extends to this wider class of models and establish conditions that guarantee convergence to an equilibrium.
Hierarchical Spatial Sum-Product Networks for Action Recognition in Still Images
Venue: arXiv cs.CV 2016
Year: 2016

Recognizing actions from still images is popularly studied recently. In this paper, we model an action class as a flexible number of spatial configurations of body parts by proposing a new spatial SPN (Sum-Product Networks). First, we discover a set of parts in image collections via unsupervised learning. Then, our new spatial SPN is applied to model the spatial relationship and also the high-order correlations of parts. To learn robust networks, we further develop a hierarchical spatial SPN method, which models pairwise spatial relationship between parts inside sub-images and models the correlation of sub-images via extra layers of SPN. Our method is shown to be effective on two benchmark datasets.
Estimation of Timing Offsets and Phase Shifts Between Packet Replicas in MARSALA Random Access
Venue: arXiv cs.IT 2016
Year: 2016

Multi-replicA decoding using corRelation baSed LocALisAtion (MARSALA) is a recent random access technique designed for satellite return links. It follows the multiple transmission and interference cancellation scheme of Contention Resolution Diversity Slotted Aloha (CRDSA). In addition, at the receiver side, MARSALA uses autocorrelation to localise replicas of a same packet so as to coherently combine them. Previous work has shown good performance of MARSALA with an assumption of ideal channel state information and perfectly coherent combining of the different replicas of a given packet. However, in a real system, synchronisation errors such as timing offsets and phase shifts between the replicas on separate timeslots will result in less constructive combining of the received signals. This paper describes a method to estimate and compensate the timing and phase differences between the replicas, prior to their combination. Then, the impact of signal misalignment in terms of residual timing offsets and phase shifts, is modeled and evaluated analytically. Finally, the performance of MARSALA in realistic channel conditions is assessed through simulations, and compared to CRDSA in various scenarios.
Learning to retrieve out-of-vocabulary words in speech recognition
Venue: arXiv cs.CL 2016
Year: 2016

Many Proper Names (PNs) are Out-Of-Vocabulary (OOV) words for speech recognition systems used to process diachronic audio data. To help recovery of the PNs missed by the system, relevant OOV PNs can be retrieved out of the many OOVs by exploiting semantic context of the spoken content. In this paper, we propose two neural network models targeted to retrieve OOV PNs relevant to an audio document: (a) Document level Continuous Bag of Words (D-CBOW), (b) Document level Continuous Bag of Weighted Words (D-CBOW2). Both these models take document words as input and learn with an objective to maximise the retrieval of co-occurring OOV PNs. With the D-CBOW2 model we propose a new approach in which the input embedding layer is augmented with a context anchor layer. This layer learns to assign importance to input words and has the ability to capture (task specific) key-words in a bag-of-word neural network model. With experiments on French broadcast news videos we show that these two models outperform the baseline methods based on raw embeddings from LDA, Skip-gram and Paragraph Vectors. Combining the D-CBOW and D-CBOW2 models gives faster convergence during training.
Tight Running Time Lower Bounds for Vertex Deletion Problems
Venue: arXiv cs.DS 2016
Year: 2016

For a graph class $Π$, the $Π$-Vertex Deletion problem has as input an undirected graph $G=(V,E)$ and an integer $k$ and asks whether there is a set of at most $k$ vertices that can be deleted from $G$ such that the resulting graph is a member of $Π$. By a classic result of Lewis and Yannakakis [J. Comput. Syst. Sci. '80], $Π$-Vertex Deletion is NP-hard for all hereditary properties $Π$. We adapt the original NP-hardness construction to show that under the Exponential Time Hypothesis (ETH) tight complexity results can be obtained. We show that $Π$-Vertex Deletion does not admit a $2^{o(n)}$-time algorithm where $n$ is the number of vertices in $G$. We also obtain a dichotomy for running time bounds that include the number $m$ of edges in the input graph: On the one hand, if $Π$ contains all independent sets, then there is no $2^{o(n+m)}$-time algorithm for $Π$-Vertex Deletion. On the other hand, if there is a fixed independent set that is not contained in $Π$ and containment in $Π$ can determined in $2^{O(n)}$ time or $2^{o(m)}$ time, then $Π$-Vertex Deletion can be solved in $2^{O(\sqrt{m})}+O(n)$ or $2^{o({m})}+O(n)$ time, respectively. We also consider restrictions on the domain of the input graph $G$. For example, we obtain that $Π$-Vertex Deletion cannot be solved in $2^{o(\sqrt{n})}$ time if $G$ is planar and $Π$ is hereditary and contains and excludes infinitely many planar graphs. Finally, we provide similar results for the problem variant where the deleted vertex set has to induce a connected graph.
Doctor AI: Predicting Clinical Events via Recurrent Neural Networks
Venue: arXiv cs.LG 2016
Year: 2016

Leveraging large historical data in electronic health record (EHR), we developed Doctor AI, a generic predictive model that covers observed medical conditions and medication uses. Doctor AI is a temporal model using recurrent neural networks (RNN) and was developed and applied to longitudinal time stamped EHR data from 260K patients over 8 years. Encounter records (e.g. diagnosis codes, medication codes or procedure codes) were input to RNN to predict (all) the diagnosis and medication categories for a subsequent visit. Doctor AI assesses the history of patients to make multilabel predictions (one label for each diagnosis or medication category). Based on separate blind test set evaluation, Doctor AI can perform differential diagnosis with up to 79% recall@30, significantly higher than several baselines. Moreover, we demonstrate great generalizability of Doctor AI by adapting the resulting models from one institution to another without losing substantial accuracy.
Supplementary Materials for "How to Avoid Reidentification with Proper Anonymization"- Comment on "Unique in the shopping mall: on the reidentifiability of credit card metadata"
Venue: arXiv cs.CR 2016
Year: 2016

The study by De Montjoye et al. ("Science", 30 January 2015, p. 536) claimed that most individuals can be reidentified from a deidentified credit card transaction database and that anonymization mechanisms are not effective against reidentification. Such claims deserve detailed quantitative scrutiny, as they might seriously undermine the willingness of data owners and subjects to share data for research. In a recent Technical Comment published in "Science" (18 March 2016, p. 1274), we demonstrate that the reidentification risk reported by De Montjoye et al. was significantly overestimated (due to a misunderstanding of the reidentification attack) and that the alleged ineffectiveness of anonymization is due to the choice of poor and undocumented methods and to a general disregard of 40 years of anonymization literature. The technical comment also shows how to properly anonymize data, in order to reduce unequivocal reidentifications to zero while retaining even more analytical utility than with the poor anonymization mechanisms employed by De Montjoye et al. In conclusion, data owners, subjects and users can be reassured that sound privacy models and anonymization methods exist to produce safe and useful anonymized data. Supplementary materials detailing the data sets, algorithms and extended results of our study are available here. Moreover, unlike the De Montjoye et al.'s data set, which was never made available, our data, anonymized results, and anonymization algorithms can be freely downloaded from http://crises-deim.urv.cat/opendata/SPD_Science.zip
Rate of Price Discovery in Iterative Combinatorial Auctions
Venue: arXiv cs.GT 2016
Year: 2016

We study a class of iterative combinatorial auctions which can be viewed as subgradient descent methods for the problem of pricing bundles to balance supply and demand. We provide concrete convergence rates for auctions in this class, bounding the number of auction rounds needed to reach clearing prices. Our analysis allows for a variety of pricing schemes, including item, bundle, and polynomial pricing, and the respective convergence rates confirm that more expressive pricing schemes come at the cost of slower convergence. We consider two models of bidder behavior. In the first model, bidders behave stochastically according to a random utility model, which includes standard best-response bidding as a special case. In the second model, bidders behave arbitrarily (even adversarially), and meaningful convergence relies on properly designed activity rules.
Knowledge Base Population using Semantic Label Propagation
Venue: arXiv cs.CL 2016
Year: 2016

A crucial aspect of a knowledge base population system that extracts new facts from text corpora, is the generation of training data for its relation extractors. In this paper, we present a method that maximizes the effectiveness of newly trained relation extractors at a minimal annotation cost. Manual labeling can be significantly reduced by Distant Supervision, which is a method to construct training data automatically by aligning a large text corpus with an existing knowledge base of known facts. For example, all sentences mentioning both 'Barack Obama' and 'US' may serve as positive training instances for the relation born_in(subject,object). However, distant supervision typically results in a highly noisy training set: many training sentences do not really express the intended relation. We propose to combine distant supervision with minimal manual supervision in a technique called feature labeling, to eliminate noise from the large and noisy initial training set, resulting in a significant increase of precision. We further improve on this approach by introducing the Semantic Label Propagation method, which uses the similarity between low-dimensional representations of candidate training instances, to extend the training set in order to increase recall while maintaining high precision. Our proposed strategy for generating training data is studied and evaluated on an established test collection designed for knowledge base population tasks. The experimental results show that the Semantic Label Propagation strategy leads to substantial performance gains when compared to existing approaches, while requiring an almost negligible manual annotation effort.