OpenRaiser/Intern-Atlas huggingface dataset:
N2SID: Nuclear Norm Subspace Identification
Venue: arXiv cs.SY 2016
Year: 2016

The identification of multivariable state space models in innovation form is solved in a subspace identification framework using convex nuclear norm optimization. The convex optimization approach allows to include constraints on the unknown matrices in the data-equation characterizing subspace identification methods, such as the lower triangular block-Toeplitz of weighting matrices constructed from the Markov parameters of the unknown observer. The classical use of instrumental variables to remove the influence of the innovation term on the data equation in subspace identification is avoided. The avoidance of the instrumental variable projection step has the potential to improve the accuracy of the estimated model predictions, especially for short data length sequences. This is illustrated using a data set from the DaSIy library. An efficient implementation in the framework of the Alternating Direction Method of Multipliers (ADMM) is presented that is used in the validation study.
A Novel Implementation of QuickHull Algorithm on the GPU
Venue: arXiv cs.CG 2016
Year: 2016

We present a novel GPU-accelerated implementation of the QuickHull algorihtm for calculating convex hulls of planar point sets. We also describe a practical solution to demonstrate how to efficiently implement a typical Divide-and-Conquer algorithm on the GPU. We highly utilize the parallel primitives provided by the library Thrust such as the parallel segmented scan for better efficiency and simplicity. To evaluate the performance of our implementation, we carry out four groups of experimental tests using two groups of point sets in two modes on the GPU K20c. Experimental results indicate that: our implementation can achieve the speedups of up to 10.98x over the state-of-art CPU-based convex hull implementation Qhull [16]. In addition, our implementation can find the convex hull of 20M points in about 0.2 seconds.
Unified Capacity Limit of Non-coherent Wideband Fading Channels
Venue: arXiv cs.IT 2016
Year: 2016

In non-coherent wideband fading channels where energy rather than spectrum is the limiting resource, peaky and non-peaky signaling schemes have long been considered species apart, as the first approaches asymptotically the capacity of a wideband AWGN channel with the same average SNR, whereas the second reaches a peak rate at some finite critical bandwidth and then falls to zero as bandwidth grows to infinity. In this paper it is shown that this distinction is in fact an artifact of the limited attention paid in the past to the product between the bandwidth and the fraction of time it is in use. This fundamental quantity, called bandwidth occupancy, measures average bandwidth usage over time. For all signaling schemes with the same bandwidth occupancy, achievable rates approach to the wideband AWGN capacity within the same gap as the bandwidth occupancy approaches its critical value, and decrease to zero as the occupancy goes to infinity. This unified analysis produces quantitative closed-form expressions for the ideal bandwidth occupancy, recovers the existing capacity results for (non-)peaky signaling schemes, and unveils a trade-off between the accuracy of approximating capacity with a generalized Taylor polynomial and the accuracy with which the optimal bandwidth occupancy can be bounded.
Consensus Game Acceptors and Iterated Transductions
Venue: arXiv cs.FL 2016
Year: 2016

We study a game for recognising formal languages, in which two players with imperfect information need to coordinate on a common decision, given private input words correlated by a finite graph. The players have a joint objective to avoid an inadmissible decision, in spite of the uncertainty induced by the input. We show that the acceptor model based on consensus games characterises context-sensitive languages. Further, we describe the expressiveness of these games in terms of iterated synchronous transductions and identify a subclass that characterises context-free languages.
On instruction sets for Boolean registers in program algebra
Venue: arXiv cs.PL 2016
Year: 2016

In previous work carried out in the setting of program algebra, including work in the area of instruction sequence size complexity, we chose instruction sets for Boolean registers that contain only instructions of a few of the possible kinds. In the current paper, we study instruction sequence size bounded functional completeness of all possible instruction sets for Boolean registers. We expect that the results of this study will turn out to be useful to adequately assess results of work that is concerned with lower bounds of instruction sequence size complexity.
The relational model is injective for Multiplicative Exponential Linear Logic
Venue: arXiv cs.LO 2016
Year: 2016

We prove a completeness result for Multiplicative Exponential Linear Logic (MELL): we show that the relational model is injective for MELL proof-nets, i.e. the equality between MELL proof-nets in the relational model is exactly axiomatized by cut-elimination.
A fast PC algorithm for high dimensional causal discovery with multi-core PCs
Venue: arXiv cs.AI 2016
Year: 2016

Discovering causal relationships from observational data is a crucial problem and it has applications in many research areas. The PC algorithm is the state-of-the-art constraint based method for causal discovery. However, runtime of the PC algorithm, in the worst-case, is exponential to the number of nodes (variables), and thus it is inefficient when being applied to high dimensional data, e.g. gene expression datasets. On another note, the advancement of computer hardware in the last decade has resulted in the widespread availability of multi-core personal computers. There is a significant motivation for designing a parallelised PC algorithm that is suitable for personal computers and does not require end users' parallel computing knowledge beyond their competency in using the PC algorithm. In this paper, we develop parallel-PC, a fast and memory efficient PC algorithm using the parallel computing technique. We apply our method to a range of synthetic and real-world high dimensional datasets. Experimental results on a dataset from the DREAM 5 challenge show that the original PC algorithm could not produce any results after running more than 24 hours; meanwhile, our parallel-PC algorithm managed to finish within around 12 hours with a 4-core CPU computer, and less than 6 hours with a 8-core CPU computer. Furthermore, we integrate parallel-PC into a causal inference method for inferring miRNA-mRNA regulatory relationships. The experimental results show that parallel-PC helps improve both the efficiency and accuracy of the causal inference algorithm.
Analysis of classifiers' robustness to adversarial perturbations
Venue: arXiv cs.LG 2016
Year: 2016

The goal of this paper is to analyze an intriguing phenomenon recently discovered in deep networks, namely their instability to adversarial perturbations (Szegedy et. al., 2014). We provide a theoretical framework for analyzing the robustness of classifiers to adversarial perturbations, and show fundamental upper bounds on the robustness of classifiers. Specifically, we establish a general upper bound on the robustness of classifiers to adversarial perturbations, and then illustrate the obtained upper bound on the families of linear and quadratic classifiers. In both cases, our upper bound depends on a distinguishability measure that captures the notion of difficulty of the classification task. Our results for both classes imply that in tasks involving small distinguishability, no classifier in the considered set will be robust to adversarial perturbations, even if a good accuracy is achieved. Our theoretical framework moreover suggests that the phenomenon of adversarial instability is due to the low flexibility of classifiers, compared to the difficulty of the classification task (captured by the distinguishability). Moreover, we show the existence of a clear distinction between the robustness of a classifier to random noise and its robustness to adversarial perturbations. Specifically, the former is shown to be larger than the latter by a factor that is proportional to \sqrt{d} (with d being the signal dimension) for linear classifiers. This result gives a theoretical explanation for the discrepancy between the two robustness properties in high dimensional problems, which was empirically observed in the context of neural networks. To the best of our knowledge, our results provide the first theoretical work that addresses the phenomenon of adversarial instability recently observed for deep networks. Our analysis is complemented by experimental results on controlled and real-world data.
A Fast Distributed Stateless Algorithm for $α$-Fair Packing Problems
Venue: arXiv cs.DC 2016
Year: 2016

Over the past two decades, fair resource allocation problems have received considerable attention in a variety of application areas. However, little progress has been made in the design of distributed algorithms with convergence guarantees for general and commonly used $α$-fair allocations. In this paper, we study weighted $α$-fair packing problems, that is, the problems of maximizing the objective functions (i) $\sum_j w_j x_j^{1-α}/(1-α)$ when $α> 0$, $α\neq 1$ and (ii) $\sum_j w_j \ln x_j$ when $α= 1$, over linear constraints $Ax \leq b$, $x\geq 0$, where $w_j$ are positive weights and $A$ and $b$ are non-negative. We consider the distributed computation model that was used for packing linear programs and network utility maximization problems. Under this model, we provide a distributed algorithm for general $α$ that converges to an $\varepsilon-$approximate solution in time (number of distributed iterations) that has an inverse polynomial dependence on the approximation parameter $\varepsilon$ and poly-logarithmic dependence on the problem size. This is the first distributed algorithm for weighted $α-$fair packing with poly-logarithmic convergence in the input size. The algorithm uses simple local update rules and is stateless (namely, it allows asynchronous updates, is self-stabilizing, and allows incremental and local adjustments). We also obtain a number of structural results that characterize $α-$fair allocations as the value of $α$ is varied. These results deepen our understanding of fairness guarantees in $α-$fair packing allocations, and also provide insight into the behavior of $α-$fair allocations in the asymptotic cases $α\rightarrow 0$, $α\rightarrow 1$, and $α\rightarrow \infty$.
The Penn Jerboa: A Platform for Exploring Parallel Composition of Templates
Venue: arXiv cs.RO 2016
Year: 2016

We have built a 12DOF, passive-compliant legged, tailed biped actuated by four brushless DC motors. We anticipate that this machine will achieve varied modes of quasistatic and dynamic balance, enabling a broad range of locomotion tasks including sitting, standing, walking, hopping, running, turning, leaping, and more. Achieving this diversity of behavior with a single under-actuated body, requires a correspondingly diverse array of controllers, motivating our interest in compositional techniques that promote mixing and reuse of a relatively few base constituents to achieve a combinatorially growing array of available choices. Here we report on the development of one important example of such a behavioral programming method, the construction of a novel monopedal sagittal plane hopping gait through parallel composition of four decoupled 1DOF base controllers. For this example behavior, the legs are locked in phase and the body is fastened to a boom to restrict motion to the sagittal plane. The platform's locomotion is powered by the hip motor that adjusts leg touchdown angle in flight and balance in stance, along with a tail motor that adjusts body shape in flight and drives energy into the passive leg shank spring during stance. The motor control signals arise from the application in parallel of four simple, completely decoupled 1DOF feedback laws that provably stabilize in isolation four corresponding 1DOF abstract reference plants. Each of these abstract 1DOF closed loop dynamics represents some simple but crucial specific component of the locomotion task at hand. We present a partial proof of correctness for this parallel composition of template reference systems along with data from the physical platform suggesting these templates are anchored as evidenced by the correspondence of their characteristic motions with a suitably transformed image of traces from the physical platform.
Elements of style of BPMN language
Venue: arXiv cs.SE 2016
Year: 2016

Several BPMN graphical tools support, at least partly, the OMG's BPMN specification. The BPMN standard is an essential guide for tools' makers when implementing the rules regarding depiction of BPMN diagrammatic constructs. Process modelers should also know how to rigorously use BPMN constructs when depicting business processes either for business or IT purposes. Several already published OMG's standards include the formal specification of well-formedness rules concern-ing the metamodels they address. However, the BPMN standard does not. Instead, the rules regarding BPMN elements are only informally specified in natural language throughout the overall BPMN documentation. Without strict rules concerning the correct usage of BPMN elements, no wonder that plenty of available BPMN tools fail to enforce BPMN process models' correctness. To mitigate this problem, and therefore contribute for achieving BPMN models' correctness, we propose to supplement the BPMN metamodel with well-formedness rules expressed by OCL invariants. So, this document contributes to bring together a set of requirements that tools' makers must comply with, in order to claim a broader BPMN 2 compliance. For the regular process modeler, this report provides an extensive and pragmatic catalog of BPMN elements' usage, to be followed in order to attain correct BPMN process models.
Total variation on a tree
Venue: arXiv cs.CV 2016
Year: 2016

We consider the problem of minimizing the continuous valued total variation subject to different unary terms on trees and propose fast direct algorithms based on dynamic programming to solve these problems. We treat both the convex and the non-convex case and derive worst case complexities that are equal or better than existing methods. We show applications to total variation based 2D image processing and computer vision problems based on a Lagrangian decomposition approach. The resulting algorithms are very efficient, offer a high degree of parallelism and come along with memory requirements which are only in the order of the number of image pixels.
Computing with Tangles
Venue: arXiv cs.DM 2016
Year: 2016

Tangles of graphs have been introduced by Robertson and Seymour in the context of their graph minor theory. Tangles may be viewed as describing "k-connected components" of a graph (though in a twisted way). They play an important role in graph minor theory. An interesting aspect of tangles is that they cannot only be defined for graphs, but more generally for arbitrary connectivity functions (that is, integer-valued submodular and symmetric set functions). However, tangles are difficult to deal with algorithmically. To start with, it is unclear how to represent them, because they are families of separations and as such may be exponentially large. Our first contribution is a data structure for representing and accessing all tangles of a graph up to some fixed order. Using this data structure, we can prove an algorithmic version of a very general structure theorem due to Carmesin, Diestel, Harman and Hundertmark (for graphs) and Hundertmark (for arbitrary connectivity functions) that yields a canonical tree decomposition whose parts correspond to the maximal tangles. (This may be viewed as a generalisation of the decomposition of a graph into its 3-connected components.)
Weakly Supervised Object Localization with Multi-fold Multiple Instance Learning
Venue: arXiv cs.CV 2016
Year: 2016

Object category localization is a challenging problem in computer vision. Standard supervised training requires bounding box annotations of object instances. This time-consuming annotation process is sidestepped in weakly supervised learning. In this case, the supervised information is restricted to binary labels that indicate the absence/presence of object instances in the image, without their locations. We follow a multiple-instance learning approach that iteratively trains the detector and infers the object locations in the positive training images. Our main contribution is a multi-fold multiple instance learning procedure, which prevents training from prematurely locking onto erroneous object locations. This procedure is particularly important when using high-dimensional representations, such as Fisher vectors and convolutional neural network features. We also propose a window refinement method, which improves the localization accuracy by incorporating an objectness prior. We present a detailed experimental evaluation using the PASCAL VOC 2007 dataset, which verifies the effectiveness of our approach.
A Meta-Analysis of the Anomaly Detection Problem
Venue: arXiv cs.AI 2016
Year: 2016

This article provides a thorough meta-analysis of the anomaly detection problem. To accomplish this we first identify approaches to benchmarking anomaly detection algorithms across the literature and produce a large corpus of anomaly detection benchmarks that vary in their construction across several dimensions we deem important to real-world applications: (a) point difficulty, (b) relative frequency of anomalies, (c) clusteredness of anomalies, and (d) relevance of features. We apply a representative set of anomaly detection algorithms to this corpus, yielding a very large collection of experimental results. We analyze these results to understand many phenomena observed in previous work. First we observe the effects of experimental design on experimental results. Second, results are evaluated with two metrics, ROC Area Under the Curve and Average Precision. We employ statistical hypothesis testing to demonstrate the value (or lack thereof) of our benchmarks. We then offer several approaches to summarizing our experimental results, drawing several conclusions about the impact of our methodology as well as the strengths and weaknesses of some algorithms. Last, we compare results against a trivial solution as an alternate means of normalizing the reported performance of algorithms. The intended contributions of this article are many; in addition to providing a large publicly-available corpus of anomaly detection benchmarks, we provide an ontology for describing anomaly detection contexts, a methodology for controlling various aspects of benchmark creation, guidelines for future experimental design and a discussion of the many potential pitfalls of trying to measure success in this field.
Class Probability Estimation via Differential Geometric Regularization
Venue: arXiv cs.LG 2016
Year: 2016

We study the problem of supervised learning for both binary and multiclass classification from a unified geometric perspective. In particular, we propose a geometric regularization technique to find the submanifold corresponding to a robust estimator of the class probability $P(y|\pmb{x})$. The regularization term measures the volume of this submanifold, based on the intuition that overfitting produces rapid local oscillations and hence large volume of the estimator. This technique can be applied to regularize any classification function that satisfies two requirements: firstly, an estimator of the class probability can be obtained; secondly, first and second derivatives of the class probability estimator can be calculated. In experiments, we apply our regularization technique to standard loss functions for classification, our RBF-based implementation compares favorably to widely used regularization methods for both binary and multiclass classification.
A Single-Pass Classifier for Categorical Data
Venue: arXiv cs.AI 2016
Year: 2016

This paper describes a new method for classifying a dataset that partitions elements into their categories. It has relations with neural networks but a slightly different structure, requiring only a single pass through the classifier to generate the weight sets. A grid-like structure is required as part of a novel idea of converting a 1-D row of real values into a 2-D structure of value bands. Each cell in any band then stores a distinct set of weights, to represent its own importance and its relation to each output category. During classification, all of the output weight lists can be retrieved and summed to produce a probability for what the correct output category is. The bands possibly work like hidden layers of neurons, but they are variable specific, making the process orthogonal. The construction process can be a single update process without iterations, making it potentially much faster. It can also be compared with k-NN and may be practical for partial or competitive updating.
Uniform Random Number Generation from Markov Chains: Non-Asymptotic and Asymptotic Analyses
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we derive non-asymptotic achievability and converse bounds on the random number generation with/without side-information. Our bounds are efficiently computable in the sense that the computational complexity does not depend on the block length. We also characterize the asymptotic behaviors of the large deviation regime and the moderate deviation regime by using our bounds, which implies that our bounds are asymptotically tight in those regimes. We also show the second order rates of those problems, and derive single letter forms of the variances characterizing the second order rates. Further, we address the equivocation rates for these problems.
Varilets: Additive Decomposition, Topological Total Variation, and Filtering of Scalar Fields
Venue: arXiv cs.CG 2016
Year: 2016

Continuous interpolation of real-valued data is characterized by piecewise monotone functions on a compact metric space. Topological total variation of piecewise monotone function f:X->R is a homeomorphism-invariant generalization of 1D total variation. A varilet basis is a collection of piecewise monotone functions { $g_i$ |i = 1...n}, called varilets, such that every linear combination $\sum a_ig_i$ has topological total variation $\sum |a_i|$. A varilet transform for $f$ is a varilet basis for which $f =\sum α_ig_i$. Filtered versions of $f$ result from altering the coefficients $α_i$.
Relaxed Leverage Sampling for Low-rank Matrix Completion
Venue: arXiv cs.IT 2016
Year: 2016

We consider the problem of exact recovery of any $m\times n$ matrix of rank $\varrho$ from a small number of observed entries via the standard nuclear norm minimization framework. Such low-rank matrices have degrees of freedom $(m+n)\varrho - \varrho^2$. We show that any arbitrary low-rank matrices can be recovered exactly from a $Θ\left(((m+n)\varrho - \varrho^2)\log^2(m+n)\right)$ randomly sampled entries, thus matching the lower bound on the required number of entries (in terms of degrees of freedom), with an additional factor of $O(\log^2(m+n))$. To achieve this bound on sample size we observe each entry with probabilities proportional to the sum of corresponding row and column leverage scores, minus their product. We show that this relaxation in sampling probabilities (as opposed to sum of leverage scores in Chen et al, 2014) can give us an $O(\varrho^2\log^2(m+n))$ additive improvement on the (best known) sample size obtained by Chen et al, 2014, for the nuclear norm minimization. Experiments on real data corroborate the theoretical improvement on sample size. Further, exact recovery of $(a)$ incoherent matrices (with restricted leverage scores), and $(b)$ matrices with only one of the row or column spaces to be incoherent, can be performed using our relaxed leverage score sampling, via nuclear norm minimization, without knowing the leverage scores a priori. In such settings also we can achieve improvement on sample size.