OpenRaiser/Intern-Atlas huggingface dataset:
Human Trajectory Prediction using Spatially aware Deep Attention Models
Venue: arXiv cs.LG 2017
Year: 2017

Trajectory Prediction of dynamic objects is a widely studied topic in the field of artificial intelligence. Thanks to a large number of applications like predicting abnormal events, navigation system for the blind, etc. there have been many approaches to attempt learning patterns of motion directly from data using a wide variety of techniques ranging from hand-crafted features to sophisticated deep learning models for unsupervised feature learning. All these approaches have been limited by problems like inefficient features in the case of hand crafted features, large error propagation across the predicted trajectory and no information of static artefacts around the dynamic moving objects. We propose an end to end deep learning model to learn the motion patterns of humans using different navigational modes directly from data using the much popular sequence to sequence model coupled with a soft attention mechanism. We also propose a novel approach to model the static artefacts in a scene and using these to predict the dynamic trajectories. The proposed method, tested on trajectories of pedestrians, consistently outperforms previously proposed state of the art approaches on a variety of large scale data sets. We also show how our architecture can be naturally extended to handle multiple modes of movement (say pedestrians, skaters, bikers and buses) simultaneously.
Equilibria in Sequential Allocation
Venue: arXiv cs.GT 2017
Year: 2017

Sequential allocation is a simple mechanism for sharing multiple indivisible items. We study strategic behavior in sequential allocation. In particular, we consider Nash dynamics, as well as the computation and Pareto optimality of pure equilibria, and Stackelberg strategies. We first demonstrate that, even for two agents, better responses can cycle. We then present a linear-time algorithm that returns a profile (which we call the "bluff profile") that is in pure Nash equilibrium. Interestingly, the outcome of the bluff profile is the same as that of the truthful profile and the profile is in pure Nash equilibrium for \emph{all} cardinal utilities consistent with the ordinal preferences. We show that the outcome of the bluff profile is Pareto optimal with respect to pairwise comparisons. In contrast, we show that an assignment may not be Pareto optimal with respect to pairwise comparisons even if it is a result of a preference profile that is in pure Nash equilibrium for all utilities consistent with ordinal preferences. Finally, we present a dynamic program to compute an optimal Stackelberg strategy for two agents, where the second agent has a constant number of distinct values for the items.
Joint Sparse Recovery With Semisupervised MUSIC
Venue: arXiv cs.IT 2017
Year: 2017

Discrete multiple signal classification (MUSIC) with its low computational cost and mild condition requirement becomes a significant noniterative algorithm for joint sparse recovery (JSR). However, it fails in rank defective problem caused by coherent or limited amount of multiple measurement vectors (MMVs). In this letter, we provide a novel sight to address this problem by interpreting JSR as a binary classification problem with respect to atoms. Meanwhile, MUSIC essentially constructs a supervised classifier based on the labeled MMVs so that its performance will heavily depend on the quality and quantity of these training samples. From this viewpoint, we develop a semisupervised MUSIC (SS-MUSIC) in the spirit of machine learning, which declares that the insufficient supervised information in the training samples can be compensated from those unlabeled atoms. Instead of constructing a classifier in a fully supervised manner, we iteratively refine a semisupervised classifier by exploiting the labeled MMVs and some reliable unlabeled atoms simultaneously. Through this way, the required conditions and iterations can be greatly relaxed and reduced. Numerical experimental results demonstrate that SS-MUSIC can achieve much better recovery performances than other MUSIC extended algorithms as well as some typical greedy algorithms for JSR in terms of iterations and recovery probability.
BP-LED decoding algorithm for LDPC codes over AWGN channels
Venue: arXiv cs.IT 2017
Year: 2017

A new method for low-complexity near-maximum-likelihood (ML) decoding of low-density parity-check (LDPC) codes over the additive white Gaussian noise channel is presented. The proposed method termed belief-propagation--list erasure decoding (BP-LED) is based on erasing carefully chosen unreliable bits performed in case of BP decoding failure. A strategy of introducing erasures into the received vector and a new erasure decoding algorithm are proposed. The new erasure decoding algorithm, called list erasure decoding, combines ML decoding over the BEC with list decoding applied if the ML decoder fails to find a unique solution. The asymptotic exponent of the average list size for random regular LDPC codes from the Gallager ensemble is analyzed. Furthermore, a few examples of regular and irregular quasi-cyclic LDPC codes of short and moderate lengths are studied by simulations and their performance is compared with the upper bound on the LDPC ensemble-average performance and the upper bound on the average performance of random linear codes under ML decoding. A comparison with the BP decoding performance of the WiMAX standard codes and performance of the near-ML BEAST decoding are presented. The new algorithm is applied to decoding a short nonbinary LDPC code over the extension of the binary Galois field. The obtained simulation results are compared to the upper bound on the ensemble-average performance of the binary image of regular nonbinary LDPC codes.
On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation
Venue: arXiv cs.DS 2017
Year: 2017

We investigate two closely related LZ78-based compression schemes: LZMW (an old scheme by Miller and Wegman) and LZD (a recent variant by Goto et al.). Both LZD and LZMW naturally produce a grammar for a string of length $n$; we show that the size of this grammar can be larger than the size of the smallest grammar by a factor $Ω(n^{\frac{1}3})$ but is always within a factor $O((\frac{n}{\log n})^{\frac{2}{3}})$. In addition, we show that the standard algorithms using $Θ(z)$ working space to construct the LZD and LZMW parsings, where $z$ is the size of the parsing, work in $Ω(n^{\frac{5}4})$ time in the worst case. We then describe a new Las Vegas LZD/LZMW parsing algorithm that uses $O (z \log n)$ space and $O(n + z \log^2 n)$ time w.h.p..
Rational Fair Consensus in the GOSSIP Model
Venue: arXiv cs.GT 2017
Year: 2017

The \emph{rational fair consensus problem} can be informally defined as follows. Consider a network of $n$ (selfish) \emph{rational agents}, each of them initially supporting a \emph{color} chosen from a finite set $ Σ$. The goal is to design a protocol that leads the network to a stable monochromatic configuration (i.e. a consensus) such that the probability that the winning color is $c$ is equal to the fraction of the agents that initially support $c$, for any $c \in Σ$. Furthermore, this fairness property must be guaranteed (with high probability) even in presence of any fixed \emph{coalition} of rational agents that may deviate from the protocol in order to increase the winning probability of their supported colors. A protocol having this property, in presence of coalitions of size at most $t$, is said to be a \emph{whp\,-$t$-strong equilibrium}. We investigate, for the first time, the rational fair consensus problem in the GOSSIP communication model where, at every round, every agent can actively contact at most one neighbor via a \emph{push$/$pull} operation. We provide a randomized GOSSIP protocol that, starting from any initial color configuration of the complete graph, achieves rational fair consensus within $O(\log n)$ rounds using messages of $O(\log^2n)$ size, w.h.p. More in details, we prove that our protocol is a whp\,-$t$-strong equilibrium for any $t = o(n/\log n)$ and, moreover, it tolerates worst-case permanent faults provided that the number of non-faulty agents is $Ω(n)$. As far as we know, our protocol is the first solution which avoids any all-to-all communication, thus resulting in $o(n^2)$ message complexity.
Fourier Phase Retrieval: Uniqueness and Algorithms
Venue: arXiv cs.IT 2017
Year: 2017

The problem of recovering a signal from its phaseless Fourier transform measurements, called Fourier phase retrieval, arises in many applications in engineering and science. Fourier phase retrieval poses fundamental theoretical and algorithmic challenges. In general, there is no unique mapping between a one-dimensional signal and its Fourier magnitude and therefore the problem is ill-posed. Additionally, while almost all multidimensional signals are uniquely mapped to their Fourier magnitude, the performance of existing algorithms is generally not well-understood. In this chapter we survey methods to guarantee uniqueness in Fourier phase retrieval. We then present different algorithmic approaches to retrieve the signal in practice. We conclude by outlining some of the main open questions in this field.
Learning a Robust Society of Tracking Parts
Venue: arXiv cs.CV 2017
Year: 2017

Object tracking is an essential task in computer vision that has been studied since the early days of the field. Being able to follow objects that undergo different transformations in the video sequence, including changes in scale, illumination, shape and occlusions, makes the problem extremely difficult. One of the real challenges is to keep track of the changes in objects appearance and not drift towards the background clutter. Different from previous approaches, we obtain robustness against background with a tracker model that is composed of many different parts. They are classifiers that respond at different scales and locations. The tracker system functions as a society of parts, each having its own role and level of credibility. Reliable classifiers decide the tracker's next move, while newcomers are first monitored before gaining the necessary level of reliability to participate in the decision process. Some parts that loose their consistency are rejected, while others that show consistency for a sufficiently long time are promoted to permanent roles. The tracker system, as a whole, could also go through different phases, from the usual, normal functioning to states of weak agreement and even crisis. The tracker system has different governing rules in each state. What truly distinguishes our work from others is not necessarily the strength of individual tracking parts, but the way in which they work together and build a strong and robust organization. We also propose an efficient way to learn simultaneously many tracking parts, with a single closed-form formulation. We obtain a fast and robust tracker with state of the art performance on the challenging OTB50 dataset.
Community Identity and User Engagement in a Multi-Community Landscape
Venue: arXiv cs.SI 2017
Year: 2017

A community's identity defines and shapes its internal dynamics. Our current understanding of this interplay is mostly limited to glimpses gathered from isolated studies of individual communities. In this work we provide a systematic exploration of the nature of this relation across a wide variety of online communities. To this end we introduce a quantitative, language-based typology reflecting two key aspects of a community's identity: how distinctive, and how temporally dynamic it is. By mapping almost 300 Reddit communities into the landscape induced by this typology, we reveal regularities in how patterns of user engagement vary with the characteristics of a community. Our results suggest that the way new and existing users engage with a community depends strongly and systematically on the nature of the collective identity it fosters, in ways that are highly consequential to community maintainers. For example, communities with distinctive and highly dynamic identities are more likely to retain their users. However, such niche communities also exhibit much larger acculturation gaps between existing users and newcomers, which potentially hinder the integration of the latter. More generally, our methodology reveals differences in how various social phenomena manifest across communities, and shows that structuring the multi-community landscape can lead to a better understanding of the systematic nature of this diversity.
On the Capacity of Fractal Wireless Networks With Direct Social Interactions
Venue: arXiv cs.IT 2017
Year: 2017

The capacity of a fractal wireless network with direct social interactions is studied in this paper. Specifically, we mathematically formulate the self-similarity of a fractal wireless network by a power-law degree distribution $ P(k) $, and we capture the connection feature between two nodes with degree $ k_{1} $ and $ k_{2} $ by a joint probability distribution $ P(k_{1},k_{2}) $. It is proved that if the source node communicates with one of its direct contacts randomly, the maximum capacity is consistent with the classical result $ Θ\left(\frac{1}{\sqrt{n\log n}}\right) $ achieved by Kumar \cite{Gupta2000The}. On the other hand, if the two nodes with distance $ d $ communicate according to the probability $ d^{-β} $, the maximum capacity can reach up to $ Θ\left(\frac{1}{\log n}\right) $, which exhibits remarkable improvement compared with the well-known result in \cite{Gupta2000The}.
Stochastic Feedback Control of Systems with Unknown Nonlinear Dynamics
Venue: arXiv cs.SY 2017
Year: 2017

This paper studies the stochastic optimal control problem for systems with unknown dynamics. First, an open-loop deterministic trajectory optimization problem is solved without knowing the explicit form of the dynamical system. Next, a Linear Quadratic Gaussian (LQG) controller is designed for the nominal trajectory-dependent linearized system, such that under a small noise assumption, the actual states remain close to the optimal trajectory. The trajectory-dependent linearized system is identified using input-output experimental data consisting of the impulse responses of the nominal system. A computational example is given to illustrate the performance of the proposed approach.
Deep Matching and Validation Network -- An End-to-End Solution to Constrained Image Splicing Localization and Detection
Venue: arXiv cs.CV 2017
Year: 2017

Image splicing is a very common image manipulation technique that is sometimes used for malicious purposes. A splicing detec- tion and localization algorithm usually takes an input image and produces a binary decision indicating whether the input image has been manipulated, and also a segmentation mask that corre- sponds to the spliced region. Most existing splicing detection and localization pipelines suffer from two main shortcomings: 1) they use handcrafted features that are not robust against subsequent processing (e.g., compression), and 2) each stage of the pipeline is usually optimized independently. In this paper we extend the formulation of the underlying splicing problem to consider two input images, a query image and a potential donor image. Here the task is to estimate the probability that the donor image has been used to splice the query image, and obtain the splicing masks for both the query and donor images. We introduce a novel deep convolutional neural network architecture, called Deep Matching and Validation Network (DMVN), which simultaneously localizes and detects image splicing. The proposed approach does not depend on handcrafted features and uses raw input images to create deep learned representations. Furthermore, the DMVN is end-to-end op- timized to produce the probability estimates and the segmentation masks. Our extensive experiments demonstrate that this approach outperforms state-of-the-art splicing detection methods by a large margin in terms of both AUC score and speed.
PVEs: Position-Velocity Encoders for Unsupervised Learning of Structured State Representations
Venue: arXiv cs.RO 2017
Year: 2017

We propose position-velocity encoders (PVEs) which learn---without supervision---to encode images to positions and velocities of task-relevant objects. PVEs encode a single image into a low-dimensional position state and compute the velocity state from finite differences in position. In contrast to autoencoders, position-velocity encoders are not trained by image reconstruction, but by making the position-velocity representation consistent with priors about interacting with the physical world. We applied PVEs to several simulated control tasks from pixels and achieved promising preliminary results.
The risk factors affecting to the software quality failures in Sri Lankan Software industry
Venue: arXiv cs.SE 2017
Year: 2017

Software project failure and cancellation rates increase day by day due to technical failures, quality failures, lack of end client acceptance etc. and also the lack of proper management. There are a number of reasons affected by the software project failures. According to empirical evidence, inadequate testing resources are one of the major factors that contribute to the poor quality. The main objectives of this study are to study the risk factors that affect the software quality to provide some recommendation to minimize the risk of poor quality. There are three main factors affecting to software quality namely proper testing, test planning and QA team which are directly impacted to the software quality risks. To conduct this study, I employed an open-ended questionnaire for collecting qualitative data from responses analyzed them using thematic approach method. The participants with their experiences agreed only with requirement clarity and clearly defined acceptance criteria, not with adequate unit testing and finally and also with that not doing regression testing force to quality failures. As of data analysis, not having proper formal test planning, initial test planning not being realistic, not following quality risk management, non-proper process and contingency action planning also lead to the risk of poor project quality. According to the participants added that the following factors are also behind the reasons for the lack quality of software. The experienced and skilled employees move out from the company as there is not a proper QA process and team members as they do not have the risk management mentality.
Inexpensive Cost-Optimized Measurement Proposal for Sequential Model-Based Diagnosis
Venue: arXiv cs.AI 2017
Year: 2017

In this work we present strategies for (optimal) measurement selection in model-based sequential diagnosis. In particular, assuming a set of leading diagnoses being given, we show how queries (sets of measurements) can be computed and optimized along two dimensions: expected number of queries and cost per query. By means of a suitable decoupling of two optimizations and a clever search space reduction the computations are done without any inference engine calls. For the full search space, we give a method requiring only a polynomial number of inferences and guaranteeing query properties existing methods cannot provide. Evaluation results using real-world problems indicate that the new method computes (virtually) optimal queries instantly independently of the size and complexity of the considered diagnosis problems.
Bayesian Unification of Gradient and Bandit-based Learning for Accelerated Global Optimisation
Venue: arXiv cs.AI 2017
Year: 2017

Bandit based optimisation has a remarkable advantage over gradient based approaches due to their global perspective, which eliminates the danger of getting stuck at local optima. However, for continuous optimisation problems or problems with a large number of actions, bandit based approaches can be hindered by slow learning. Gradient based approaches, on the other hand, navigate quickly in high-dimensional continuous spaces through local optimisation, following the gradient in fine grained steps. Yet, apart from being susceptible to local optima, these schemes are less suited for online learning due to their reliance on extensive trial-and-error before the optimum can be identified. In this paper, we propose a Bayesian approach that unifies the above two paradigms in one single framework, with the aim of combining their advantages. At the heart of our approach we find a stochastic linear approximation of the function to be optimised, where both the gradient and values of the function are explicitly captured. This allows us to learn from both noisy function and gradient observations, and predict these properties across the action space to support optimisation. We further propose an accompanying bandit driven exploration scheme that uses Bayesian credible bounds to trade off exploration against exploitation. Our empirical results demonstrate that by unifying bandit and gradient based learning, one obtains consistently improved performance across a wide spectrum of problem environments. Furthermore, even when gradient feedback is unavailable, the flexibility of our model, including gradient prediction, still allows us outperform competing approaches, although with a smaller margin. Due to the pervasiveness of bandit based optimisation, our scheme opens up for improved performance both in meta-optimisation and in applications where gradient related information is readily available.
L1-norm Error Function Robustness and Outlier Regularization
Venue: arXiv cs.CV 2017
Year: 2017

In many real-world applications, data come with corruptions, large errors or outliers. One popular approach is to use L1-norm function. However, the robustness of L1-norm function is not well understood so far. In this paper, we present a new outlier regularization framework to understand and analyze the robustness of L1-norm function. There are two main features for the proposed outlier regularization. (1) A key property of outlier regularization is that how far an outlier lies away from its theoretically predicted value does not affect the final regularization and analysis results. (2) Another important feature of outlier regularization is that it has an equivalent continuous representation that closely relates to L1 function. This provides a new way to understand and analyze the robustness of L1 function. We apply our outlier regularization framework to PCA and propose an outlier regularized PCA (ORPCA) model. Comparing to the trace-normbased robust PCA, ORPCA has several benefits: (1) It does not suffer singular value suppression. (2) It can retain small high rank components which help retain fine details of data. (3) ORPCA can be computed more efficiently.
Probabilistic Program Abstractions
Venue: arXiv cs.AI 2017
Year: 2017

Abstraction is a fundamental tool for reasoning about complex systems. Program abstraction has been utilized to great effect for analyzing deterministic programs. At the heart of program abstraction is the relationship between a concrete program, which is difficult to analyze, and an abstract program, which is more tractable. Program abstractions, however, are typically not probabilistic. We generalize non-deterministic program abstractions to probabilistic program abstractions by explicitly quantifying the non-deterministic choices. Our framework upgrades key definitions and properties of abstractions to the probabilistic context. We also discuss preliminary ideas for performing inference on probabilistic abstractions and general probabilistic programs.