OpenRaiser/Intern-Atlas huggingface dataset:
Deterministic Algorithms for Submodular Maximization Problems
Venue: arXiv cs.DS 2015
Year: 2015

Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function maximization. In this area most algorithms are randomized, and in almost all cases the approximation ratios obtained by current randomized algorithms are superior to the best results obtained by known deterministic algorithms. Derandomization of algorithms for general submodular function maximization seems hard since the access to the function is done via a value oracle. This makes it hard, for example, to apply standard derandomization techniques such as conditional expectations. Therefore, an interesting fundamental problem in this area is whether randomization is inherently necessary for obtaining good approximation ratios. In this work we give evidence that randomization is not necessary for obtaining good algorithms by presenting a new technique for derandomization of algorithms for submodular function maximization. Our high level idea is to maintain explicitly a (small) distribution over the states of the algorithm, and carefully update it using marginal values obtained from an extreme point solution of a suitable linear formulation. We demonstrate our technique on two recent algorithms for unconstrained submodular maximization and for maximizing submodular function subject to a cardinality constraint. In particular, for unconstrained submodular maximization we obtain an optimal deterministic $1/2$-approximation showing that randomization is unnecessary for obtaining optimal results for this setting.
Automatic Extraction of the Passing Strategies of Soccer Teams
Venue: arXiv cs.CV 2015
Year: 2015

Technology offers new ways to measure the locations of the players and of the ball in sports. This translates to the trajectories the ball takes on the field as a result of the tactics the team applies. The challenge professionals in soccer are facing is to take the reverse path: given the trajectories of the ball is it possible to infer the underlying strategy/tactic of a team? We propose a method based on Dynamic Time Warping to reveal the tactics of a team through the analysis of repeating series of events. Based on the analysis of an entire season, we derive insights such as passing strategies for maintaining ball possession or counter attacks, and passing styles with a focus on the team or on the capabilities of the individual players.
Joint Optimization of Area Spectral Efficiency and Delay Over PPP Interfered Ad-hoc Networks
Venue: arXiv cs.IT 2015
Year: 2015

Due to the increasing demand on user data rates, future wireless communication networks require higher spectral efficiency. To reach higher spectral efficiencies, wireless network technologies collaborate and construct a seamless interconnection between multiple tiers of architectures at the cost of increased co-channel interference. To evaluate the performance of the co-channel transmission based communication, we propose a new metric for area spectral efficiency (ASE) of interference limited Ad-hoc network by assuming that the nodes are randomly distributed according to a Poisson point processes (PPP). We introduce a utility function, U = ASE/delay and derive the optimal ALOHA transmission probability p and the SIR threshold τthat jointly maximize the ASE and minimize the local delay. Finally numerical results has been conducted to confirm that the joint optimization based on the U metric achieves a significant performance gain compared to conventional systems.
Dropout Training for SVMs with Data Augmentation
Venue: arXiv cs.LG 2015
Year: 2015

Dropout and other feature noising schemes have shown promising results in controlling over-fitting by artificially corrupting the training data. Though extensive theoretical and empirical studies have been performed for generalized linear models, little work has been done for support vector machines (SVMs), one of the most successful approaches for supervised learning. This paper presents dropout training for both linear SVMs and the nonlinear extension with latent representation learning. For linear SVMs, to deal with the intractable expectation of the non-smooth hinge loss under corrupting distributions, we develop an iteratively re-weighted least square (IRLS) algorithm by exploring data augmentation techniques. Our algorithm iteratively minimizes the expectation of a re-weighted least square problem, where the re-weights are analytically updated. For nonlinear latent SVMs, we consider learning one layer of latent representations in SVMs and extend the data augmentation technique in conjunction with first-order Taylor-expansion to deal with the intractable expected non-smooth hinge loss and the nonlinearity of latent representations. Finally, we apply the similar data augmentation ideas to develop a new IRLS algorithm for the expected logistic loss under corrupting distributions, and we further develop a non-linear extension of logistic regression by incorporating one layer of latent representations. Our algorithms offer insights on the connection and difference between the hinge loss and logistic loss in dropout training. Empirical results on several real datasets demonstrate the effectiveness of dropout training on significantly boosting the classification accuracy of both linear and nonlinear SVMs. In addition, the nonlinear SVMs further improve the prediction performance on several image datasets.
Approaching Maximum Embedding Efficiency on Small Covers Using Staircase-Generator Codes
Venue: arXiv cs.MM 2015
Year: 2015

We introduce a new family of binary linear codes suitable for steganographic matrix embedding. The main characteristic of the codes is the staircase random block structure of the generator matrix. We propose an efficient list decoding algorithm for the codes that finds a close codeword to a given random word. We provide both theoretical analysis of the performance and stability of the decoding algorithm, as well as practical results. Used for matrix embedding, these codes achieve almost the upper theoretical bound of the embedding efficiency for covers in the range of 1000 - 1500 bits, which is at least an order of magnitude smaller than the values reported in related works.
A Counter-Example to the Mismatched Decoding Converse for Binary-Input Discrete Memoryless Channels
Venue: arXiv cs.IT 2015
Year: 2015

This paper studies the mismatched decoding problem for binary-input discrete memoryless channels. An example is provided for which an achievable rate based on superposition coding exceeds the LM rate (Hui, 1983; Csiszár-Körner, 1981), thus providing a counter-example to a previously reported converse result (Balakirsky, 1995). Both numerical evaluations and theoretical results are used in establishing this claim.
Removing Biases from Trainable MT Metrics by Using Self-Training
Venue: arXiv cs.CL 2015
Year: 2015

Most trainable machine translation (MT) metrics train their weights on human judgments of state-of-the-art MT systems outputs. This makes trainable metrics biases in many ways. One of them is preferring longer translations. These biased metrics when used for tuning are evaluating different types of translations -- n-best lists of translations with very diverse quality. Systems tuned with these metrics tend to produce overly long translations that are preferred by the metric but not by humans. This is usually solved by manually tweaking metric's weights to equally value recall and precision. Our solution is more general: (1) it does not address only the recall bias but also all other biases that might be present in the data and (2) it does not require any knowledge of the types of features used which is useful in cases when manual tuning of metric's weights is not possible. This is accomplished by self-training on unlabeled n-best lists by using metric that was initially trained on standard human judgments. One way of looking at this is as domain adaptation from the domain of state-of-the-art MT translations to diverse n-best list translations.
On ISI-free Modulations for Diffusion based Molecular Communication
Venue: arXiv cs.IT 2015
Year: 2015

A diffusion molecular channel is a channel with memory, as molecules released into the medium hit the receptors after a random delay. Coding over the diffusion channel is performed by choosing the type, intensity, or the released time of molecules diffused in the environment over time. To avoid intersymbol interference (ISI), molecules of the same type should be released at time instances that are sufficiently far apart. This ensures that molecules of a previous transmission are faded in the environment, before molecules of the same type are reused for signaling. In this paper, we consider ISI-free time-slotted modulation schemes. The maximum reliable transmission rate for these modulations is given by the constrained coding capacity of the graph that represents the permissible transmission sequences. However, achieving the constrained coding capacity requires long blocklengths and delays at the decoder, making it impractical for simple nanomachines. The main contribution of this paper is to consider modulations with small delay (short blocklength) and show that they get very close to constrained coding capacity.
Simulating Brain Reaction to Methamphetamine Regarding Consumer Personality
Venue: arXiv cs.NE 2015
Year: 2015

Addiction, as a nervous disease, can be analysed using mathematical modelling and computer simulations. In this paper, we use an existing mathematical model to predict and simulate human brain response to the consumption of a single dose of methamphetamine. The model is implemented and coded in Matlab. Three types of personalities including introverts, ambiverts and extroverts are studied. The parameters of the mathematical model are calibrated and optimized, according to psychological theories, using a real coded genetic algorithm. The simulations show significant correlation between people response to methamphetamine abuse and their personality. They also show that one of the causes of tendency to stimulants roots in consumers personality traits. The results can be used as a tool for reducing attitude towards addiction.
Modeling and Performance Analysis of Clustered Device-to-Device Networks
Venue: arXiv cs.IT 2015
Year: 2015

Device-to-device (D2D) communication enables direct communication between proximate devices thereby improving the overall spectrum utilization and offloading traffic from cellular networks. This paper develops a new spatial model for D2D networks in which the device locations are modeled as a Poisson cluster process. Using this model, we study the performance of a typical D2D receiver in terms of coverage probability under two realistic content availability setups: (i) content of interest for a typical device is available at a device chosen uniformly at random from the same cluster, which we term uniform content availability, and (ii) content of interest is available at the $k^{th}$ closest device from the typical device inside the same cluster, which we term $k$-closest content availability. Using these coverage probability results, we also characterize the area spectral efficiency (ASE) of the whole network for the two setups. A key intermediate step in this analysis is the derivation of the distributions of distances from a typical device to both the intra- and inter-cluster devices. Our analysis reveals that an optimum number of D2D transmitters must be simultaneously activated per cluster in order to maximize ASE. This can be interpreted as the classical tradeoff between more aggressive frequency reuse and higher interference power. The optimum number of simultaneously transmitting devices and the resulting ASE increase as the content is made available closer to the receivers. Our analysis also quantifies the best and worst case performance of clustered D2D networks both in terms of coverage and ASE.
Call Graph Profiling for Multi Agent Systems
Venue: arXiv cs.MA 2015
Year: 2015

The design, implementation and testing of Multi Agent Systems is typically a very complex task. While a number of specialist agent programming languages and toolkits have been created to aid in the development of such systems, the provision of associated development tools still lags behind those available for other programming paradigms. This includes tools such as debuggers and profilers to help analyse system behaviour, performance and efficiency. AgentSpotter is a profiling tool designed specifically to operate on the concepts of agent-oriented programming. This paper extends previous work on AgentSpotter by discussing its Call Graph View, which presents system performance information, with reference to the communication between the agents in the system. This is aimed at aiding developers in examining the effect that agent communication has on the processing requirements of the system.
Artificial Prediction Markets for Online Prediction of Continuous Variables-A Preliminary Report
Venue: arXiv cs.AI 2015
Year: 2015

We propose the Artificial Continuous Prediction Market (ACPM) as a means to predict a continuous real value, by integrating a range of data sources and aggregating the results of different machine learning (ML) algorithms. ACPM adapts the concept of the (physical) prediction market to address the prediction of real values instead of discrete events. Each ACPM participant has a data source, a ML algorithm and a local decision-making procedure that determines what to bid on what value. The contributions of ACPM are: (i) adaptation to changes in data quality by the use of learning in: (a) the market, which weights each market participant to adjust the influence of each on the market prediction and (b) the participants, which use a Q-learning based trading strategy to incorporate the market prediction into their subsequent predictions, (ii) resilience to a changing population of low- and high-performing participants. We demonstrate the effectiveness of ACPM by application to an influenza-like illnesses data set, showing ACPM out-performs a range of well-known regression models and is resilient to variation in data source quality.
Are Slepian-Wolf Rates Necessary for Distributed Parameter Estimation?
Venue: arXiv cs.IT 2015
Year: 2015

We consider a distributed parameter estimation problem, in which multiple terminals send messages related to their local observations using limited rates to a fusion center who will obtain an estimate of a parameter related to observations of all terminals. It is well known that if the transmission rates are in the Slepian-Wolf region, the fusion center can fully recover all observations and hence can construct an estimator having the same performance as that of the centralized case. One natural question is whether Slepian-Wolf rates are necessary to achieve the same estimation performance as that of the centralized case. In this paper, we show that the answer to this question is negative. We establish our result by explicitly constructing an asymptotically minimum variance unbiased estimator (MVUE) that has the same performance as that of the optimal estimator in the centralized case while requiring information rates less than the conditions required in the Slepian-Wolf rate region.
Inappropriate use of L-BFGS, Illustrated on frame field design
Venue: arXiv cs.GR 2015
Year: 2015

L-BFGS is a hill climbing method that is guarantied to converge only for convex problems. In computer graphics, it is often used as a black box solver for a more general class of non linear problems, including problems having many local minima. Some works obtain very nice results by solving such difficult problems with L-BFGS. Surprisingly, the method is able to escape local minima: our interpretation is that the approximation of the Hessian is smoother than the real Hessian, making it possible to evade the local minima. We analyse the behavior of L-BFGS on the design of 2D frame fields. It involves an energy function that is infinitly continuous, strongly non linear and having many local minima. Moreover, the local minima have a clear visual interpretation: they corresponds to differents frame field topologies. We observe that the performances of LBFGS are almost unpredictables: they are very competitive when the field is sampled on the primal graph, but really poor when they are sampled on the dual graph.
Second Order Cone Programming for Sensor Node Localization in Mixed LOS/NLOS Conditions
Venue: arXiv cs.NI 2015
Year: 2015

In this paper, a novel method for sensor node localization under mixed line-of-sight/non-line-of-sight (LOS/NLOS) conditions based on second order cone programming (SOCP) is presented. SOCP methods have, hitherto, not been utilized in the node localization under mixed LOS/NLOS conditions. Unlike semidefinite programming (SDP) formulation, SOCP is computationally efficient for resource constrained ad-hoc sensor network. The proposed method can work seamlessly in mixed LOS/NLOS conditions. The robustness of the method is due to the fair utilization of all measurements obtained under LOS and NLOS conditions. The computational complexity of this method is quadratic in the number of nearest neighbours of the unknown node. Extensive simulations and real field deployments are used to evaluate the performance of the proposed method. The experimental results of the proposed method is reasonably better when compared to similar methods in literature.
Manifold regularization in structured output space for semi-supervised structured output prediction
Venue: arXiv cs.LG 2015
Year: 2015

Structured output prediction aims to learn a predictor to predict a structured output from a input data vector. The structured outputs include vector, tree, sequence, etc. We usually assume that we have a training set of input-output pairs to train the predictor. However, in many real-world appli- cations, it is difficult to obtain the output for a input, thus for many training input data points, the structured outputs are missing. In this paper, we dis- cuss how to learn from a training set composed of some input-output pairs, and some input data points without outputs. This problem is called semi- supervised structured output prediction. We propose a novel method for this problem by constructing a nearest neighbor graph from the input space to present the manifold structure, and using it to regularize the structured out- put space directly. We define a slack structured output for each training data point, and proposed to predict it by learning a structured output predictor. The learning of both slack structured outputs and the predictor are unified within one single minimization problem. In this problem, we propose to mini- mize the structured loss between the slack structured outputs of neighboring data points, and the prediction error measured by the structured loss. The problem is optimized by an iterative algorithm. Experiment results over three benchmark data sets show its advantage.
Mountain Peak Detection in Online Social Media
Venue: arXiv cs.CV 2015
Year: 2015

We present a system for the classification of mountain panoramas from user-generated photographs followed by identification and extraction of mountain peaks from those panoramas. We have developed an automatic technique that, given as input a geo-tagged photograph, estimates its FOV (Field Of View) and the direction of the camera using a matching algorithm on the photograph edge maps and a rendered view of the mountain silhouettes that should be seen from the observer's point of view. The extraction algorithm then identifies the mountain peaks present in the photograph and their profiles. We discuss possible applications in social fields such as photograph peak tagging on social portals, augmented reality on mobile devices when viewing a mountain panorama, and generation of collective intelligence systems (such as environmental models) from massive social media collections (e.g. snow water availability maps based on mountain peak states extracted from photograph hosting services).
Multiple-Path Selection for new Highway Alignments using Discrete Algorithms
Venue: arXiv cs.DS 2015
Year: 2015

This paper addresses the problem of finding multiple near-optimal, spatially-dissimilar paths that can be considered as alternatives in the decision making process, for finding optimal corridors in which to construct a new road. We further consider combinations of techniques for reducing the costs associated with the computation and increasing the accuracy of the cost formulation. Numerical results for five algorithms to solve the dissimilar multipath problem show that a "bidirectional approach" yields the fastest running times and the most robust algorithm. Further modifications of the algorithms to reduce the running time were tested and it is shown that running time can be reduced by an average of 56 percent without compromising the quality of the results.
Capacity-Achieving Rateless Polar Codes
Venue: arXiv cs.IT 2015
Year: 2015

A rateless coding scheme transmits incrementally more and more coded bits over an unknown channel until all the information bits are decoded reliably by the receiver. We propose a new rateless coding scheme based on polar codes, and we show that this scheme is capacity-achieving, i.e. its information rate is as good as the best code specifically designed for the unknown channel. Previous rateless coding schemes are designed for specific classes of channels such as AWGN channels, binary erasure channels, etc. but the proposed rateless coding scheme is capacity-achieving for broad classes of channels as long as they are ordered via degradation. Moreover, it inherits the conceptual and computational simplicity of polar codes.
MergeShuffle: A Very Fast, Parallel Random Permutation Algorithm
Venue: arXiv cs.DS 2015
Year: 2015

This article introduces an algorithm, MergeShuffle, which is an extremely efficient algorithm to generate random permutations (or to randomly permute an existing array). It is easy to implement, runs in $n\log_2 n + O(1)$ time, is in-place, uses $n\log_2 n + Θ(n)$ random bits, and can be parallelized accross any number of processes, in a shared-memory PRAM model. Finally, our preliminary simulations using OpenMP suggest it is more efficient than the Rao-Sandelius algorithm, one of the fastest existing random permutation algorithms. We also show how it is possible to further reduce the number of random bits consumed, by introducing a second algorithm BalancedShuffle, a variant of the Rao-Sandelius algorithm which is more conservative in the way it recursively partitions arrays to be shuffled. While this algorithm is of lesser practical interest, we believe it may be of theoretical value. Our full code is available at: https://github.com/axel-bacher/mergeshuffle
Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
Venue: arXiv cs.DS 2015
Year: 2015

We present the first almost-linear time algorithm for constructing linear-sized spectral sparsification for graphs. This improves all previous constructions of linear-sized spectral sparsification, which requires $Ω(n^2)$ time. A key ingredient in our algorithm is a novel combination of two techniques used in literature for constructing spectral sparsification: Random sampling by effective resistance, and adaptive constructions based on barrier functions.
Hash Function Learning via Codewords
Venue: arXiv cs.LG 2015
Year: 2015

In this paper we introduce a novel hash learning framework that has two main distinguishing features, when compared to past approaches. First, it utilizes codewords in the Hamming space as ancillary means to accomplish its hash learning task. These codewords, which are inferred from the data, attempt to capture similarity aspects of the data's hash codes. Secondly and more importantly, the same framework is capable of addressing supervised, unsupervised and, even, semi-supervised hash learning tasks in a natural manner. A series of comparative experiments focused on content-based image retrieval highlights its performance advantages.