OpenRaiser/Intern-Atlas huggingface dataset:
Higher-Order Decision Theory
Venue: arXiv cs.GT 2015
Year: 2015

Classical decision theory models behaviour in terms of utility maximisation where utilities represent rational preference relations over outcomes. However, empirical evidence and theoretical considerations suggest that we need to go beyond this framework. We propose to represent goals by higher-order functions or operators that take other functions as arguments where the max and argmax operators are special cases. Our higher-order functions take a context function as their argument where a context represents a process from actions to outcomes. By that we can define goals being dependent on the actions and the process in addition to outcomes only. This formulation generalises outcome based preferences to context-dependent goals. We show how to uniformly represent within our higher-order framework classical utility maximisation but also various other extensions that have been debated in economics.
Performing Bayesian Risk Aggregation using Discrete Approximation Algorithms with Graph Factorization
Venue: arXiv cs.AI 2015
Year: 2015

Risk aggregation is a popular method used to estimate the sum of a collection of financial assets or events, where each asset or event is modelled as a random variable. Applications, in the financial services industry, include insurance, operational risk, stress testing, and sensitivity analysis, but the problem is widely encountered in many other application domains. This thesis has contributed two algorithms to perform Bayesian risk aggregation when model exhibit hybrid dependency and high dimensional inter-dependency. The first algorithm operates on a subset of the general problem, with an emphasis on convolution problems, in the presence of continuous and discrete variables (so called hybrid models) and the second algorithm offer a universal method for general purpose inference over much wider classes of Bayesian Network models.
ControlIt! - A Software Framework for Whole-Body Operational Space Control
Venue: arXiv cs.RO 2015
Year: 2015

Whole Body Operational Space Control (WBOSC) is a pioneering algorithm in the field of human-centered Whole-Body Control (WBC). It enables floating-base highly-redundant robots to achieve unified motion/force control of one or more operational space objectives while adhering to physical constraints. Limited studies exist on the software architecture and APIs that enable WBOSC to perform and be integrated into a larger system. In this paper we address this by presenting ControlIt!, a new open-source software framework for WBOSC. Unlike previous implementations, ControlIt! is multi-threaded to increase servo frequencies on standard PC hardware. A new parameter binding mechanism enables tight integration between ControlIt! and external processes via an extensible set of transport protocols. To support a new robot, only two plugins and a URDF model needs to be provided --- the rest of ControlIt! remains unchanged. New WBC primitives can be added by writing a Task or Constraint plugin. ControlIt!'s capabilities are demonstrated on Dreamer, a 16-DOF torque controlled humanoid upper body robot containing both series elastic and co-actuated joints, and using it to perform a product disassembly task. Using this testbed, we show that ControlIt! can achieve average servo latencies of about 0.5ms when configured with two Cartesian position tasks, two orientation tasks, and a lower priority posture task. This is significantly higher than the 5ms that was achieved using UTA-WBC, the prototype implementation of WBOSC that is both application and platform-specific. Variations in the product's position is handled by updating the goal of the Cartesian position task. ControlIt!'s source code is released under an LGPL license and we hope it will be adopted and maintained by the WBC community for the long term as a platform for WBC development and integration.
The Benefit of Limited Feedback to Generation-Based Random Linear Network Coding in Wireless Broadcast
Venue: arXiv cs.IT 2015
Year: 2015

Random linear network coding (RLNC) is asymptotically throughput optimal in the wireless broadcast of a block of packets from a sender to a set of receivers, but suffers from heavy computational load and packet decoding delay. To mitigate this problem while maintaining good throughput, we partition the packet block into disjoint generations after broadcasting the packets uncoded once and collecting one round of feedback about receivers' packet reception state. We prove the NP-hardness of the optimal partitioning problem by using a hypergraph coloring approach, and develop an efficient heuristic algorithm for its solution. Simulations show that our algorithm outperforms existing solutions.
Performance Characterization and Transmission Schemes for Instantly Decodable Network Coding in Wireless Broadcast
Venue: arXiv cs.IT 2015
Year: 2015

We consider broadcasting a block of packets to multiple wireless receivers under random packet erasures using instantly decodable network coding (IDNC). The sender first broadcasts each packet uncoded once, then generates coded packets according to receivers' feedback about their missing packets. We focus on strict IDNC (S-IDNC), where each coded packet includes at most one missing packet of every receiver. But we will also compare it with general IDNC (G-IDNC), where this condition is relaxed. We characterize two fundamental performance limits of S-IDNC: 1) the number of transmissions to complete the broadcast, and 2) the average delay for a receiver to decode a packet. We derive a closed-form expression for the expected minimum number of transmissions in terms of the number of packets and receivers and the erasure probability. We prove that it is NP-hard to minimize the decoding delay of S-IDNC. We also derive achievable upper bounds on the above two performance limits. We show that G-IDNC can outperform S-IDNC %in terms of the number of transmissions without packet erasures, but not necessarily with packet erasures. Next, we design optimal and heuristic S-IDNC transmission schemes and coding algorithms with full/intermittent receiver feedback. We present simulation results to corroborate the developed theory and compare with existing schemes.
Towards Structured Deep Neural Network for Automatic Speech Recognition
Venue: arXiv cs.LG 2015
Year: 2015

In this paper we propose the Structured Deep Neural Network (Structured DNN) as a structured and deep learning algorithm, learning to find the best structured object (such as a label sequence) given a structured input (such as a vector sequence) by globally considering the mapping relationships between the structure rather than item by item. When automatic speech recognition is viewed as a special case of such a structured learning problem, where we have the acoustic vector sequence as the input and the phoneme label sequence as the output, it becomes possible to comprehensively learned utterance by utterance as a whole, rather than frame by frame. Structured Support Vector Machine (structured SVM) was proposed to perform ASR with structured learning previously, but limited by the linear nature of SVM. Here we propose structured DNN to use nonlinear transformations in multi-layers as a structured and deep learning algorithm. It was shown to beat structured SVM in preliminary experiments on TIMIT.
Lipschitz Robustness of Timed I/O Systems
Venue: arXiv cs.FL 2015
Year: 2015

We present the first study of robustness of systems that are both timed as well as reactive (I/O). We study the behavior of such timed I/O systems in the presence of "uncertain inputs" and formalize their robustness using the analytic notion of Lipschitz continuity. Thus, a timed I/O system is K-(Lipschitz) robust if the perturbation in its output is at most K times the perturbation in its input. We quantify input and output perturbation using "similarity functions" over timed words such as the timed version of the Manhattan distance and the Skorokhod distance. We consider two models of timed I/O systems --- timed transducers and asynchronous sequential circuits. While K-robustness is undecidable even for discrete transducers, we identify a class of timed transducers which admits a polynomial space decision procedure for K-robustness. For asynchronous sequential circuits, we reduce K-robustness w.r.t. timed Manhattan distances to K-robusness of discrete letter-to-letter transducers and show PSPACE-compeleteness of the problem.
Unsupervised Feature Analysis with Class Margin Optimization
Venue: arXiv cs.LG 2015
Year: 2015

Unsupervised feature selection has been always attracting research attention in the communities of machine learning and data mining for decades. In this paper, we propose an unsupervised feature selection method seeking a feature coefficient matrix to select the most distinctive features. Specifically, our proposed algorithm integrates the Maximum Margin Criterion with a sparsity-based model into a joint framework, where the class margin and feature correlation are taken into account at the same time. To maximize the total data separability while preserving minimized within-class scatter simultaneously, we propose to embed Kmeans into the framework generating pseudo class label information in a scenario of unsupervised feature selection. Meanwhile, a sparsity-based model, ` 2 ,p-norm, is imposed to the regularization term to effectively discover the sparse structures of the feature coefficient matrix. In this way, noisy and irrelevant features are removed by ruling out those features whose corresponding coefficients are zeros. To alleviate the local optimum problem that is caused by random initializations of K-means, a convergence guaranteed algorithm with an updating strategy for the clustering indicator matrix, is proposed to iteractively chase the optimal solution. Performance evaluation is extensively conducted over six benchmark data sets. From plenty of experimental results, it is demonstrated that our method has superior performance against all other compared approaches.
Exploiting an Oracle that Reports AUC Scores in Machine Learning Contests
Venue: arXiv cs.LG 2015
Year: 2015

In machine learning contests such as the ImageNet Large Scale Visual Recognition Challenge and the KDD Cup, contestants can submit candidate solutions and receive from an oracle (typically the organizers of the competition) the accuracy of their guesses compared to the ground-truth labels. One of the most commonly used accuracy metrics for binary classification tasks is the Area Under the Receiver Operating Characteristics Curve (AUC). In this paper we provide proofs-of-concept of how knowledge of the AUC of a set of guesses can be used, in two different kinds of attacks, to improve the accuracy of those guesses. On the other hand, we also demonstrate the intractability of one kind of AUC exploit by proving that the number of possible binary labelings of $n$ examples for which a candidate solution obtains a AUC score of $c$ grows exponentially in $n$, for every $c\in (0,1)$.
Recognition of Changes in SAR Images Based on Gauss-Log Ratio and MRFFCM
Venue: arXiv cs.CV 2015
Year: 2015

A modified version of MRFFCM (Markov Random Field Fuzzy C means) based SAR (Synthetic aperture Radar) image change detection method is proposed in this paper. It involves three steps: Difference Image (DI) generation by using Gauss-log ratio operator, speckle noise reduction by SRAD (Speckle Reducing Anisotropic Diffusion), and the detection of changed regions by using MRFFCM. The proposed method is compared with existing methods such as FCM and MRFFCM using simulated and real SAR images. The measures used for evaluation includes Overall Error (OE), Percentage Correct Classification (PCC), Kappa Coefficient (KC), Root Mean Square Error (RMSE), and Peak Signal to Noise Ratio (PSNR). The results show that the proposed method is better compared to FCM and MRFFCM based change detection method.
Clustering-Based Predictive Process Monitoring
Venue: arXiv cs.SE 2015
Year: 2015

Business process enactment is generally supported by information systems that record data about process executions, which can be extracted as event logs. Predictive process monitoring is concerned with exploiting such event logs to predict how running (uncompleted) cases will unfold up to their completion. In this paper, we propose a predictive process monitoring framework for estimating the probability that a given predicate will be fulfilled upon completion of a running case. The predicate can be, for example, a temporal logic constraint or a time constraint, or any predicate that can be evaluated over a completed trace. The framework takes into account both the sequence of events observed in the current trace, as well as data attributes associated to these events. The prediction problem is approached in two phases. First, prefixes of previous traces are clustered according to control flow information. Secondly, a classifier is built for each cluster using event data to discriminate between fulfillments and violations. At runtime, a prediction is made on a running case by mapping it to a cluster and applying the corresponding classifier. The framework has been implemented in the ProM toolset and validated on a log pertaining to the treatment of cancer patients in a large hospital.
Carry Value Transformation (CVT) - Exclusive OR (XOR) Tree and Its Significant Properties
Venue: arXiv cs.DM 2015
Year: 2015

CVT and XOR are two binary operations together used to calculate the sum of two non-negative integers on using a recursive mechanism. In this present study the convergence behaviors of this recursive mechanism has been captured through a tree like structure named as CVT-XOR Tree. We have analyzed how to identify the parent nodes, leaf nodes and internal nodes in the CVT-XOR Tree. We also provide the parent information, depth information and the number of children of a node in different CVT-XOR Trees on defining three different matrices. Lastly, one observation is made towards very old Mathematical problem of Goldbach Conjecture.
A Certified Universal Gathering Algorithm for Oblivious Mobile Robots
Venue: arXiv cs.DC 2015
Year: 2015

We present a new algorithm for the problem of universal gathering mobile oblivious robots (that is, starting from any initial configuration that is not bivalent, using any number of robots, the robots reach in a finite number of steps the same position, not known beforehand) without relying on a common chirality. We give very strong guaranties on the correctness of our algorithm by proving formally that it is correct, using the COQ proof assistant. To our knowledge, this is the first certified positive (and constructive) result in the context of oblivious mobile robots. It demonstrates both the effectiveness of the approach to obtain new algorithms that are truly generic, and its managability since the amount of developped code remains human readable.
A Novel Approach Towards Clustering Based Image Segmentation
Venue: arXiv cs.CV 2015
Year: 2015

In computer vision, image segmentation is always selected as a major research topic by researchers. Due to its vital rule in image processing, there always arises the need of a better image segmentation method. Clustering is an unsupervised study with its application in almost every field of science and engineering. Many researchers used clustering in image segmentation process. But still there requires improvement of such approaches. In this paper, a novel approach for clustering based image segmentation is proposed. Here, we give importance on color space and choose lab for this task. The famous hard clustering algorithm K-means is used, but as its performance is dependent on choosing a proper distance measure, so, we go for cosine distance measure. Then the segmented image is filtered with sobel filter. The filtered image is analyzed with marker watershed algorithm to have the final segmented result of our original image. The MSE and PSNR values are evaluated to observe the performance.
Semidefinite and Spectral Relaxations for Multi-Label Classification
Venue: arXiv cs.LG 2015
Year: 2015

In this paper, we address the problem of multi-label classification. We consider linear classifiers and propose to learn a prior over the space of labels to directly leverage the performance of such methods. This prior takes the form of a quadratic function of the labels and permits to encode both attractive and repulsive relations between labels. We cast this problem as a structured prediction one aiming at optimizing either the accuracies of the predictors or the F 1-score. This leads to an optimization problem closely related to the max-cut problem, which naturally leads to semidefinite and spectral relaxations. We show on standard datasets how such a general prior can improve the performances of multi-label techniques.
Characterizing degrees of freedom through additive combinatorics
Venue: arXiv cs.IT 2015
Year: 2015

We establish a formal connection between the problem of characterizing degrees of freedom (DoF) in constant single-antenna interference channels (ICs), with general channel matrix, and the field of additive combinatorics. The theory we develop is based on a recent breakthrough result by Hochman in fractal geometry. Our first main contribution is an explicit condition on the channel matrix to admit full, i.e., $K/2$ DoF; this condition is satisfied for almost all channel matrices. We also provide a construction of corresponding DoF-optimal input distributions. The second main result is a new DoF-formula exclusively in terms of Shannon entropies. This formula is more amenable to both analytical statements and numerical evaluations than the DoF-formula by Wu et al., which is in terms of Rényi information dimension. We then use the new DoF-formula to shed light on the hardness of finding the exact number of DoF in ICs with rational channel coefficients, and to improve the best known bounds on the DoF of a well-studied channel matrix.
The combinatorics of LCD codes: Linear Programming bound and orthogonal matrices
Venue: arXiv cs.IT 2015
Year: 2015

Linear Complementary Dual codes (LCD) are binary linear codes that meet their dual trivially. We construct LCD codes using orthogonal matrices, self-dual codes, combinatorial designs and Gray map from codes over the family of rings $R_k$. We give a linear programming bound on the largest size of an LCD code of given length and minimum distance. We make a table of lower bounds for this combinatorial function for modest values of the parameters.
Portfolio Allocation for Sellers in Online Advertising
Venue: arXiv cs.GT 2015
Year: 2015

In markets for online advertising, some advertisers pay only when users respond to ads. So publishers estimate ad response rates and multiply by advertiser bids to estimate expected revenue for showing ads. Since these estimates may be inaccurate, the publisher risks not selecting the ad for each ad call that would maximize revenue. The variance of revenue can be decomposed into two components -- variance due to `uncertainty' because the true response rate is unknown, and variance due to `randomness' because realized response statistics fluctuate around the true response rate. Over a sequence of many ad calls, the variance due to randomness nearly vanishes due to the law of large numbers. However, the variance due to uncertainty doesn't diminish. We introduce a technique for ad selection that augments existing estimation and explore-exploit methods. The technique uses methods from portfolio optimization to produce a distribution over ads rather than selecting the single ad that maximizes estimated expected revenue. Over a sequence of similar ad calls, ads are selected according to the distribution. This approach decreases the effects of uncertainty and increases revenue.
Large-scale Simple Question Answering with Memory Networks
Venue: arXiv cs.LG 2015
Year: 2015

Training large-scale question answering systems is complicated because training sources usually cover a small portion of the range of possible questions. This paper studies the impact of multitask and transfer learning for simple question answering; a setting for which the reasoning required to answer is quite easy, as long as one can retrieve the correct evidence given a question, which can be difficult in large-scale conditions. To this end, we introduce a new dataset of 100k questions that we use in conjunction with existing benchmarks. We conduct our study within the framework of Memory Networks (Weston et al., 2015) because this perspective allows us to eventually scale up to more complex reasoning, and show that Memory Networks can be successfully trained to achieve excellent performance.
Visualizing and Understanding Recurrent Networks
Venue: arXiv cs.LG 2015
Year: 2015

Recurrent Neural Networks (RNNs), and specifically a variant with Long Short-Term Memory (LSTM), are enjoying renewed interest as a result of successful applications in a wide range of machine learning problems that involve sequential data. However, while LSTMs provide exceptional results in practice, the source of their performance and their limitations remain rather poorly understood. Using character-level language models as an interpretable testbed, we aim to bridge this gap by providing an analysis of their representations, predictions and error types. In particular, our experiments reveal the existence of interpretable cells that keep track of long-range dependencies such as line lengths, quotes and brackets. Moreover, our comparative analysis with finite horizon n-gram models traces the source of the LSTM improvements to long-range structural dependencies. Finally, we provide analysis of the remaining errors and suggests areas for further study.
Local Nonstationarity for Efficient Bayesian Optimization
Venue: arXiv cs.LG 2015
Year: 2015

Bayesian optimization has shown to be a fundamental global optimization algorithm in many applications: ranging from automatic machine learning, robotics, reinforcement learning, experimental design, simulations, etc. The most popular and effective Bayesian optimization relies on a surrogate model in the form of a Gaussian process due to its flexibility to represent a prior over function. However, many algorithms and setups relies on the stationarity assumption of the Gaussian process. In this paper, we present a novel nonstationary strategy for Bayesian optimization that is able to outperform the state of the art in Bayesian optimization both in stationary and nonstationary problems.
Optimum-width upward drawings of trees
Venue: arXiv cs.CG 2015
Year: 2015

An upward drawing of a tree is a drawing such that no parents are below their children. It is order-preserving if the edges to children appear in prescribed order around each node. Chan showed that any tree has an upward order-preserving drawing with width O(log n). In this paper, we present linear-time algorithms that finds upward with instance-optimal width, i.e., the width is the minimum-possible for the input tree. We study two different models. In the first model, the drawings need not be order-preserving; a very simple algorithm then finds straight-line drawings of optimal width. In the second model, the drawings must be order-preserving; and we give an algorithm that finds optimum-width poly-line drawings, i.e., edges are allowed to have bends. We also briefly study order-preserving upward straight-line drawings, and show that some trees require larger width if drawings must be straight-line.