OpenRaiser/Intern-Atlas huggingface dataset:
Preserving Statistical Validity in Adaptive Data Analysis
Venue: arXiv cs.LG 2016
Year: 2016

A great deal of effort has been devoted to reducing the risk of spurious scientific discoveries, from the use of sophisticated validation techniques, to deep statistical methods for controlling the false discovery rate in multiple hypothesis testing. However, there is a fundamental disconnect between the theoretical results and the practice of data analysis: the theory of statistical inference assumes a fixed collection of hypotheses to be tested, or learning algorithms to be applied, selected non-adaptively before the data are gathered, whereas in practice data is shared and reused with hypotheses and new analyses being generated on the basis of data exploration and the outcomes of previous analyses. In this work we initiate a principled study of how to guarantee the validity of statistical inference in adaptive data analysis. As an instance of this problem, we propose and investigate the question of estimating the expectations of $m$ adaptively chosen functions on an unknown distribution given $n$ random samples. We show that, surprisingly, there is a way to estimate an exponential in $n$ number of expectations accurately even if the functions are chosen adaptively. This gives an exponential improvement over standard empirical estimators that are limited to a linear number of estimates. Our result follows from a general technique that counter-intuitively involves actively perturbing and coordinating the estimates, using techniques developed for privacy preservation. We give additional applications of this technique to our question.
Scalable Link Prediction in Dynamic Networks via Non-Negative Matrix Factorization
Venue: arXiv cs.SI 2016
Year: 2016

We propose a scalable temporal latent space model for link prediction in dynamic social networks, where the goal is to predict links over time based on a sequence of previous graph snapshots. The model assumes that each user lies in an unobserved latent space and interactions are more likely to form between similar users in the latent space representation. In addition, the model allows each user to gradually move its position in the latent space as the network structure evolves over time. We present a global optimization algorithm to effectively infer the temporal latent space, with a quadratic convergence rate. Two alternative optimization algorithms with local and incremental updates are also proposed, allowing the model to scale to larger networks without compromising prediction accuracy. Empirically, we demonstrate that our model, when evaluated on a number of real-world dynamic networks, significantly outperforms existing approaches for temporal link prediction in terms of both scalability and predictive power.
Automatic Subspace Learning via Principal Coefficients Embedding
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we address two challenging problems in unsupervised subspace learning: 1) how to automatically identify the feature dimension of the learned subspace (i.e., automatic subspace learning), and 2) how to learn the underlying subspace in the presence of Gaussian noise (i.e., robust subspace learning). We show that these two problems can be simultaneously solved by proposing a new method (called principal coefficients embedding, PCE). For a given data set $\mathbf{D}\in \mathds{R}^{m\times n}$, PCE recovers a clean data set $\mathbf{D}_{0}\in \mathds{R}^{m\times n}$ from $\mathbf{D}$ and simultaneously learns a global reconstruction relation $\mathbf{C}\in \mathbf{R}^{n\times n}$ of $\mathbf{D}_{0}$. By preserving $\mathbf{C}$ into an $m^{\prime}$-dimensional space, the proposed method obtains a projection matrix that can capture the latent manifold structure of $\mathbf{D}_{0}$, where $m^{\prime}\ll m$ is automatically determined by the rank of $\mathbf{C}$ with theoretical guarantees. PCE has three advantages: 1) it can automatically determine the feature dimension even though data are sampled from a union of multiple linear subspaces in presence of the Gaussian noise, 2) Although the objective function of PCE only considers the Gaussian noise, experimental results show that it is robust to the non-Gaussian noise (\textit{e.g.}, random pixel corruption) and real disguises, 3) Our method has a closed-form solution and can be calculated very fast. Extensive experimental results show the superiority of PCE on a range of databases with respect to the classification accuracy, robustness and efficiency.
No-Regret Learnability for Piecewise Linear Losses
Venue: arXiv cs.LG 2016
Year: 2016

In the convex optimization approach to online regret minimization, many methods have been developed to guarantee a $O(\sqrt{T})$ bound on regret for subdifferentiable convex loss functions with bounded subgradients, by using a reduction to linear loss functions. This suggests that linear loss functions tend to be the hardest ones to learn against, regardless of the underlying decision spaces. We investigate this question in a systematic fashion looking at the interplay between the set of possible moves for both the decision maker and the adversarial environment. This allows us to highlight sharp distinctive behaviors about the learnability of piecewise linear loss functions. On the one hand, when the decision set of the decision maker is a polyhedron, we establish $Ω(\sqrt{T})$ lower bounds on regret for a large class of piecewise linear loss functions with important applications in online linear optimization, repeated zero-sum Stackelberg games, online prediction with side information, and online two-stage optimization. On the other hand, we exhibit $o(\sqrt{T})$ learning rates, achieved by the Follow-The-Leader algorithm, in online linear optimization when the boundary of the decision maker's decision set is curved and when $0$ does not lie in the convex hull of the environment's decision set. Hence, the curvature of the decision maker's decision set is a determining factor for the optimal learning rate. These results hold in a completely adversarial setting.
Spatiotemporal Modeling of a Pervasive Game
Venue: arXiv cs.OH 2016
Year: 2016

Given pervasive games that maintain a virtual spatiotemporal model of the physical world, game designers must contend with space and time in the virtual and physical, but an integrated conceptual model is lacking. Because the problem domains of GIS and Pervasive Games overlap, Peuquet's Triad Representational Framework is exapted, from the domain of GIS, and applied to Pervasive Games. Using Dix et al.'s three types of space and Langran's notion of time, virtual time and space are then be mapped to the physical world and vice versa. The approach is evaluated using the pervasive game called Codename: Heroes, as case study.
Visual Representations: Defining Properties and Deep Approximations
Venue: arXiv cs.CV 2016
Year: 2016

Visual representations are defined in terms of minimal sufficient statistics of visual data, for a class of tasks, that are also invariant to nuisance variability. Minimal sufficiency guarantees that we can store a representation in lieu of raw data with smallest complexity and no performance loss on the task at hand. Invariance guarantees that the statistic is constant with respect to uninformative transformations of the data. We derive analytical expressions for such representations and show they are related to feature descriptors commonly used in computer vision, as well as to convolutional neural networks. This link highlights the assumptions and approximations tacitly assumed by these methods and explains empirical practices such as clamping, pooling and joint normalization.
Multiple object tracking with context awareness
Venue: arXiv cs.CV 2016
Year: 2016

Multiple people tracking is a key problem for many applications such as surveillance, animation or car navigation, and a key input for tasks such as activity recognition. In crowded environments occlusions and false detections are common, and although there have been substantial advances in recent years, tracking is still a challenging task. Tracking is typically divided into two steps: detection, i.e., locating the pedestrians in the image, and data association, i.e., linking detections across frames to form complete trajectories. For the data association task, approaches typically aim at developing new, more complex formulations, which in turn put the focus on the optimization techniques required to solve them. However, they still utilize very basic information such as distance between detections. In this thesis, I focus on the data association task and argue that there is contextual information that has not been fully exploited yet in the tracking community, mainly social context and spatial context coming from different views.
Recursive Inspection Games
Venue: arXiv cs.GT 2016
Year: 2016

We consider a sequential inspection game where an inspector uses a limited number of inspections over a larger number of time periods to detect a violation (an illegal act) of an inspectee. Compared with earlier models, we allow varying rewards to the inspectee for successful violations. As one possible example, the most valuable reward may be the completion of a sequence of thefts of nuclear material needed to build a nuclear bomb. The inspectee can observe the inspector, but the inspector can only determine if a violation happens during a stage where he inspects, which terminates the game; otherwise the game continues. Under reasonable assumptions for the payoffs, the inspector's strategy is independent of the number of successful violations. This allows to apply a recursive description of the game, even though this normally assumes fully informed players after each stage. The resulting recursive equation in three variables for the equilibrium payoff of the game, which generalizes several other known equations of this kind, is solved explicitly in terms of sums of binomial coefficients. We also extend this approach to non-zero-sum games and, similar to Maschler (1966), "inspector leadership" where the inspector commits to (the same) randomized inspection schedule, but the inspectee acts legally (rather than mixes as in the simultaneous game) as long as inspections remain.
Recovering Spatiotemporal Correspondence between Deformable Objects by Exploiting Consistent Foreground Motion in Video
Venue: arXiv cs.CV 2016
Year: 2016

Given unstructured videos of deformable objects, we automatically recover spatiotemporal correspondences to map one object to another (such as animals in the wild). While traditional methods based on appearance fail in such challenging conditions, we exploit consistency in object motion between instances. Our approach discovers pairs of short video intervals where the object moves in a consistent manner and uses these candidates as seeds for spatial alignment. We model the spatial correspondence between the point trajectories on the object in one interval to those in the other using a time-varying Thin Plate Spline deformation model. On a large dataset of tiger and horse videos, our method automatically aligns thousands of pairs of frames to a high accuracy, and outperforms the popular SIFT Flow algorithm.
Context-Dependent Fine-Grained Entity Type Tagging
Venue: arXiv cs.CL 2016
Year: 2016

Entity type tagging is the task of assigning category labels to each mention of an entity in a document. While standard systems focus on a small set of types, recent work (Ling and Weld, 2012) suggests that using a large fine-grained label set can lead to dramatic improvements in downstream tasks. In the absence of labeled training data, existing fine-grained tagging systems obtain examples automatically, using resolved entities and their types extracted from a knowledge base. However, since the appropriate type often depends on context (e.g. Washington could be tagged either as city or government), this procedure can result in spurious labels, leading to poorer generalization. We propose the task of context-dependent fine type tagging, where the set of acceptable labels for a mention is restricted to only those deducible from the local context (e.g. sentence or document). We introduce new resources for this task: 12,017 mentions annotated with their context-dependent fine types, and we provide baseline experimental results on this data.
Joint Segmentation and Deconvolution of Ultrasound Images Using a Hierarchical Bayesian Model based on Generalized Gaussian Priors
Venue: arXiv cs.CV 2016
Year: 2016

This paper proposes a joint segmentation and deconvolution Bayesian method for medical ultrasound (US) images. Contrary to piecewise homogeneous images, US images exhibit heavy characteristic speckle patterns correlated with the tissue structures. The generalized Gaussian distribution (GGD) has been shown to be one of the most relevant distributions for characterizing the speckle in US images. Thus, we propose a GGD-Potts model defined by a label map coupling US image segmentation and deconvolution. The Bayesian estimators of the unknown model parameters, including the US image, the label map and all the hyperparameters are difficult to be expressed in closed form. Thus, we investigate a Gibbs sampler to generate samples distributed according to the posterior of interest. These generated samples are finally used to compute the Bayesian estimators of the unknown parameters. The performance of the proposed Bayesian model is compared with existing approaches via several experiments conducted on realistic synthetic data and in vivo US images.
Wrong side of the tracks: Big Data and Protected Categories
Venue: arXiv cs.IT 2016
Year: 2016

When we use machine learning for public policy, we find that many useful variables are associated with others on which it would be ethically problematic to base decisions. This problem becomes particularly acute in the Big Data era, when predictions are often made in the absence of strong theories for underlying causal mechanisms. We describe the dangers to democratic decision-making when high-performance algorithms fail to provide an explicit account of causation. We then demonstrate how information theory allows us to degrade predictions so that they decorrelate from protected variables with minimal loss of accuracy. Enforcing total decorrelation is at best a near-term solution, however. The role of causal argument in ethical debate urges the development of new, interpretable machine-learning algorithms that reference causal mechanisms.
A Fire Fighter's Problem
Venue: arXiv cs.CG 2016
Year: 2016

Suppose that a circular fire spreads in the plane at unit speed. A single fire fighter can build a barrier at speed $v>1$. How large must $v$ be to ensure that the fire can be contained, and how should the fire fighter proceed? We contribute two results. First, we analyze the natural curve $\mbox{FF}_v$ that develops when the fighter keeps building, at speed $v$, a barrier along the boundary of the expanding fire. We prove that the behavior of this spiralling curve is governed by a complex function $(e^{w Z} - s \, Z)^{-1}$, where $w$ and $s$ are real functions of $v$. For $v>v_c=2.6144 \ldots$ all zeroes are complex conjugate pairs. If $ϕ$ denotes the complex argument of the conjugate pair nearest to the origin then, by residue calculus, the fire fighter needs $Θ( 1/ϕ)$ rounds before the fire is contained. As $v$ decreases towards $v_c$ these two zeroes merge into a real one, so that argument $ϕ$ goes to~0. Thus, curve $\mbox{FF}_v$ does not contain the fire if the fighter moves at speed $v=v_c$. (That speed $v>v_c$ is sufficient for containing the fire has been proposed before by Bressan et al. [7], who constructed a sequence of logarithmic spiral segments that stay strictly away from the fire.) Second, we show that any curve that visits the four coordinate half-axes in cyclic order, and in inreasing distances from the origin, needs speed $v>1.618\ldots$, the golden ratio, in order to contain the fire. Keywords: Motion Planning, Dynamic Environments, Spiralling strategies, Lower and upper bounds
Suppressing Alignment: Joint PAPR and Out-of-Band Power Leakage Reduction for OFDM-Based Systems
Venue: arXiv cs.IT 2016
Year: 2016

Orthogonal frequency division multiplexing (OFDM) inherently suffers from two major drawbacks: high out-of-band (OOB) power leakage and high peak-to-average power ratio (PAPR). This paper proposes a novel approach called suppressing alignment for the joint reduction of the OOB power leakage and PAPR. The proposed approach exploits the temporal degrees of freedom provided by the cyclic prefix(CP), a necessary redundancy in OFDM systems, to generate a suppressing signal, that when added to the OFDM symbol, results in marked reduction in both the OOB power leakage and PAPR. Additionally, and in order to not cause any interference to the information data carried by the OFDM symbol, the proposed approach utilizes the wireless channel to perfectly align the suppressing signal with the CP duration at the OFDM receiver. Essentially, maintaining a bit error rate (BER) performance similar to legacy OFDM without requiring any change in the receiver structure.
Joint Deep Learning for Car Detection
Venue: arXiv cs.CV 2016
Year: 2016

Traditional object recognition approaches apply feature extraction, part deformation handling, occlusion handling and classification sequentially while they are independent from each other. Ouyang and Wang proposed a model for jointly learning of all of the mentioned processes using one deep neural network. We utilized, and manipulated their toolbox in order to apply it in car detection scenarios where it had not been tested. Creating a single deep architecture from these components, improves the interaction between them and can enhance the performance of the whole system. We believe that the approach can be used as a general purpose object detection toolbox. We tested the algorithm on UIUC car dataset, and achieved an outstanding result. The accuracy of our method was 97 % while the previously reported results showed an accuracy of up to 91 %. We strongly believe that having an experiment on a larger dataset can show the advantage of using deep models over shallow ones.
Qualitatively accurate spectral schemes for advection and transport
Venue: arXiv cs.SY 2016
Year: 2016

The transport and continuum equations exhibit a number of conservation laws. For example, scalar multiplication is conserved by the transport equation, while positivity of probabilities is conserved by the continuum equation. Certain discretization techniques, such as particle based methods, conserve these properties, but converge slower than spectral discretization methods on smooth data. Standard spectral discretization methods, on the other hand, do not conserve the invariants of the transport equation and the continuum equation. This article constructs a novel spectral discretization technique that conserves these important invariants while simultaneously preserving spectral convergence rates. The performance of this proposed method is illustrated on several numerical experiments.
Breaking the Curse of Dimensionality with Convex Neural Networks
Venue: arXiv cs.LG 2016
Year: 2016

We consider neural networks with a single hidden layer and non-decreasing homogeneous activa-tion functions like the rectified linear units. By letting the number of hidden units grow unbounded and using classical non-Euclidean regularization tools on the output weights, we provide a detailed theoretical analysis of their generalization performance, with a study of both the approximation and the estimation errors. We show in particular that they are adaptive to unknown underlying linear structures, such as the dependence on the projection of the input variables onto a low-dimensional subspace. Moreover, when using sparsity-inducing norms on the input weights, we show that high-dimensional non-linear variable selection may be achieved, without any strong assumption regarding the data and with a total number of variables potentially exponential in the number of ob-servations. In addition, we provide a simple geometric interpretation to the non-convex problem of addition of a new unit, which is the core potentially hard computational element in the framework of learning from continuously many basis functions. We provide simple conditions for convex relaxations to achieve the same generalization error bounds, even when constant-factor approxi-mations cannot be found (e.g., because it is NP-hard such as for the zero-homogeneous activation function). We were not able to find strong enough convex relaxations and leave open the existence or non-existence of polynomial-time algorithms.
Accurate solution of near-colliding Prony systems via decimation and homotopy continuation
Venue: arXiv cs.NA 2016
Year: 2016

We consider polynomial systems of Prony type, appearing in many areas of mathematics. Their robust numerical solution is considered to be difficult, especially in "near-colliding" situations. We consider a case when the structure of the system is a-priori fixed. We transform the nonlinear part of the Prony system into a Hankel-type polynomial system. Combining this representation with a recently discovered "decimation" technique, we present an algorithm which applies homotopy continuation to an appropriately chosen Hankel-type system as above. In this way, we are able to solve for the nonlinear variables of the original system with high accuracy when the data is perturbed.
Providing Long-Term Participation Incentive in Participatory Sensing
Venue: arXiv cs.GT 2016
Year: 2016

Providing an adequate long-term participation incentive is important for a participatory sensing system to maintain enough number of active users (sensors), so as to collect a sufficient number of data samples and support a desired level of service quality. In this work, we consider the sensor selection problem in a general time-dependent and location-aware participatory sensing system, taking the long-term user participation incentive into explicit consideration. We study the problem systematically under different information scenarios, regarding both future information and current information (realization). In particular, we propose a Lyapunov-based VCG auction policy for the on-line sensor selection, which converges asymptotically to the optimal off-line benchmark performance, even with no future information and under (current) information asymmetry. Extensive numerical results show that our proposed policy outperforms the state-of-art policies in the literature, in terms of both user participation (e.g., reducing the user dropping probability by 25% to 90%) and social performance (e.g., increasing the social welfare by 15% to 80%).
New bounds on the number of tests for disjunct matrices
Venue: arXiv cs.IT 2016
Year: 2016

Given $n$ items with at most $d$ of which being positive, instead of testing these items individually, the theory of combinatorial group testing aims to identify all positive items using as few tests as possible. This paper is devoted to a fundamental and thirty-year-old problem in the nonadaptive group testing theory. A binary matrix is called $d$-disjunct if the boolean sum of arbitrary $d$ columns does not contain another column not in this collection. Let $T(d)$ denote the minimal $t$ such that there exists a $t\times n$ $d$-disjunct matrix with $n>t$. $T(d)$ can also be viewed as the minimal $t$ such that there exists a nonadaptive group testing scheme which is better than the trivial one that tests each item individually. It was known that $T(d)\ge\binom{d+2}{2}$ and was conjectured that $T(d)\ge(d+1)^2$. In this paper we narrow the gap by proving $T(d)/d^2\ge(15+\sqrt{33})/24$, a quantity in [6/7,7/8].