OpenRaiser/Intern-Atlas huggingface dataset:
Almost-Polynomial Ratio ETH-Hardness of Approximating Densest $k$-Subgraph
Venue: arXiv cs.CC 2017
Year: 2017

In the Densest $k$-Subgraph problem, given an undirected graph $G$ and an integer $k$, the goal is to find a subgraph of $G$ on $k$ vertices that contains maximum number of edges. Even though the state-of-the-art algorithm for the problem achieves only $O(n^{1/4 + \varepsilon})$ approximation ratio (Bhaskara et al., 2010), previous attempts at proving hardness of approximation, including those under average case assumptions, fail to achieve a polynomial ratio; the best ratios ruled out under any worst case assumption and any average case assumption are only any constant (Raghavendra and Steurer, 2010) and $2^{Ω(\log^{2/3} n)}$ (Alon et al., 2011) respectively. In this work, we show, assuming the exponential time hypothesis (ETH), that there is no polynomial-time algorithm that approximates Densest $k$-Subgraph to within $n^{1/(\log \log n)^c}$ factor of the optimum, where $c > 0$ is a universal constant independent of $n$. In addition, our result has "perfect completeness", meaning that we prove that it is ETH-hard to even distinguish between the case in which $G$ contains a $k$-clique and the case in which every induced $k$-subgraph of $G$ has density at most $1/n^{-1/(\log \log n)^c}$ in polynomial time. Moreover, if we make a stronger assumption that there is some constant $\varepsilon > 0$ such that no subexponential-time algorithm can distinguish between a satisfiable 3SAT formula and one which is only $(1 - \varepsilon)$-satisfiable (also known as Gap-ETH), then the ratio above can be improved to $n^{f(n)}$ for any function $f$ whose limit is zero as $n$ goes to infinity (i.e. $f \in o(1)$).
Online Visual Multi-Object Tracking via Labeled Random Finite Set Filtering
Venue: arXiv cs.CV 2017
Year: 2017

This paper proposes an online visual multi-object tracking algorithm using a top-down Bayesian formulation that seamlessly integrates state estimation, track management, clutter rejection, occlusion and mis-detection handling into a single recursion. This is achieved by modeling the multi-object state as labeled random finite set and using the Bayes recursion to propagate the multi-object filtering density forward in time. The proposed filter updates tracks with detections but switches to image data when mis-detection occurs, thereby exploiting the efficiency of detection data and the accuracy of image data. Furthermore the labeled random finite set framework enables the incorporation of prior knowledge that mis-detections of long tracks which occur in the middle of the scene are likely to be due to occlusions. Such prior knowledge can be exploited to improve occlusion handling, especially long occlusions that can lead to premature track termination in on-line multi-object tracking. Tracking performance are compared to state-of-the-art algorithms on well-known benchmark video datasets.
On The Stability of Video Detection and Tracking
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we study an important yet less explored aspect in video detection and tracking -- stability. Surprisingly, there is no prior work that tried to study it. As a result, we start our work by proposing a novel evaluation metric for video detection which considers both stability and accuracy. For accuracy, we extend the existing accuracy metric mean Average Precision (mAP). For stability, we decompose it into three terms: fragment error, center position error, scale and ratio error. Each error represents one aspect of stability. Furthermore, we demonstrate that the stability metric has low correlation with accuracy metric. Thus, it indeed captures a different perspective of quality. Lastly, based on this metric, we evaluate several existing methods for video detection and show how they affect accuracy and stability. We believe our work can provide guidance and solid baselines for future researches in the related areas.
Dealing with Range Anxiety in Mean Estimation via Statistical Queries
Venue: arXiv cs.LG 2017
Year: 2017

We give algorithms for estimating the expectation of a given real-valued function $ϕ:X\to {\bf R}$ on a sample drawn randomly from some unknown distribution $D$ over domain $X$, namely ${\bf E}_{{\bf x}\sim D}[ϕ({\bf x})]$. Our algorithms work in two well-studied models of restricted access to data samples. The first one is the statistical query (SQ) model in which an algorithm has access to an SQ oracle for the input distribution $D$ over $X$ instead of i.i.d. samples from $D$. Given a query function $ϕ:X \to [0,1]$, the oracle returns an estimate of ${\bf E}_{{\bf x}\sim D}[ϕ({\bf x})]$ within some tolerance $τ$. The second, is a model in which only a single bit is communicated from each sample. In both of these models the error obtained using a naive implementation would scale polynomially with the range of the random variable $ϕ({\bf x})$ (which might even be infinite). In contrast, without restrictions on access to data the expected error scales with the standard deviation of $ϕ({\bf x})$. Here we give a simple algorithm whose error scales linearly in standard deviation of $ϕ({\bf x})$ and logarithmically with an upper bound on the second moment of $ϕ({\bf x})$. As corollaries, we obtain algorithms for high dimensional mean estimation and stochastic convex optimization in these models that work in more general settings than previously known solutions.
Recurrent Memory Addressing for describing videos
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we introduce Key-Value Memory Networks to a multimodal setting and a novel key-addressing mechanism to deal with sequence-to-sequence models. The proposed model naturally decomposes the problem of video captioning into vision and language segments, dealing with them as key-value pairs. More specifically, we learn a semantic embedding (v) corresponding to each frame (k) in the video, thereby creating (k, v) memory slots. We propose to find the next step attention weights conditioned on the previous attention distributions for the key-value memory slots in the memory addressing schema. Exploiting this flexibility of the framework, we additionally capture spatial dependencies while mapping from the visual to semantic embedding. Experiments done on the Youtube2Text dataset demonstrate usefulness of recurrent key-addressing, while achieving competitive scores on BLEU@4, METEOR metrics against state-of-the-art models.
Gland Instance Segmentation Using Deep Multichannel Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

Objective: A new image instance segmentation method is proposed to segment individual glands (instances) in colon histology images. This process is challenging since the glands not only need to be segmented from a complex background, they must also be individually identified. Methods: We leverage the idea of image-to-image prediction in recent deep learning by designing an algorithm that automatically exploits and fuses complex multichannel information - regional, location, and boundary cues - in gland histology images. Our proposed algorithm, a deep multichannel framework, alleviates heavy feature design due to the use of convolutional neural networks and is able to meet multifarious requirements by altering channels. Results: Compared with methods reported in the 2015 MICCAI Gland Segmentation Challenge and other currently prevalent instance segmentation methods, we observe state-of-the-art results based on the evaluation metrics. Conclusion: The proposed deep multichannel algorithm is an effective method for gland instance segmentation. Significance: The generalization ability of our model not only enable the algorithm to solve gland instance segmentation problems, but the channel is also alternative that can be replaced for a specific task.
Neural Information Retrieval: A Literature Review
Venue: arXiv cs.IR 2017
Year: 2017

A recent "third wave" of Neural Network (NN) approaches now delivers state-of-the-art performance in many machine learning tasks, spanning speech recognition, computer vision, and natural language processing. Because these modern NNs often comprise multiple interconnected layers, this new NN research is often referred to as deep learning. Stemming from this tide of NN work, a number of researchers have recently begun to investigate NN approaches to Information Retrieval (IR). While deep NNs have yet to achieve the same level of success in IR as seen in other areas, the recent surge of interest and work in NNs for IR suggest that this state of affairs may be quickly changing. In this work, we survey the current landscape of Neural IR research, paying special attention to the use of learned representations of queries and documents (i.e., neural embeddings). We highlight the successes of neural IR thus far, catalog obstacles to its wider adoption, and suggest potentially promising directions for future research.
The Distribution of Optimal Strategies in Symmetric Zero-sum Games
Venue: arXiv cs.GT 2017
Year: 2017

Given a skew-symmetric matrix, the corresponding two-player symmetric zero-sum game is defined as follows: one player, the row player, chooses a row and the other player, the column player, chooses a column. The payoff of the row player is given by the corresponding matrix entry, the column player receives the negative of the row player. A randomized strategy is optimal if it guarantees an expected payoff of at least 0 for a player independently of the strategy of the other player. We determine the probability that an optimal strategy randomizes over a given set of actions when the game is drawn from a distribution that satisfies certain regularity conditions. The regularity conditions are quite general and apply to a wide range of natural distributions.
Space-Efficient Hidden Surface Removal
Venue: arXiv cs.CG 2017
Year: 2017

We propose a space-efficient algorithm for hidden surface removal that combines one of the fastest previous algorithms for that problem with techniques based on bit manipulation. Such techniques had been successfully used in other settings, for example to reduce working space for several graph algorithms. However, bit manipulation is not usually employed in geometric algorithms because the standard model of computation (the real RAM) does not support it. For this reason, we first revisit our model of computation to have a reasonable theoretical framework. Under this framework we show how the use of a bit representation for the union of triangles, in combination with rank-select data structures, allows us to implicitly compute the union of $n$ triangles with roughly $O(1)$ bits per union boundary vertex. This results in an algorithm that uses at most as much space as the previous one, and depending on the input, can give a reduction of up to a factor $Θ(\log n)$, while maintaining the running time.
Can Self-Censorship in News Media be Detected Algorithmically? A Case Study in Latin America
Venue: arXiv cs.SI 2017
Year: 2017

Censorship in social media has been well studied and provides insight into how governments stifle freedom of expression online. Comparatively less (or no) attention has been paid to detecting (self) censorship in traditional media (e.g., news) using social media as a bellweather. We present a novel unsupervised approach that views social media as a sensor to detect censorship in news media wherein statistically significant differences between information published in the news media and the correlated information published in social media are automatically identified as candidate censored events. We develop a hypothesis testing framework to identify and evaluate censored clusters of keywords, and a new near-linear-time algorithm (called GraphDPD) to identify the highest scoring clusters as indicators of censorship. We outline extensive experiments on semi-synthetic data as well as real datasets (with Twitter and local news media) from Mexico and Venezuela, highlighting the capability to accurately detect real-world self censorship events.
Quasi-regular sequences and optimal schedules for security games
Venue: arXiv cs.GT 2017
Year: 2017

We study security games in which a defender commits to a mixed strategy for protecting a finite set of targets of different values. An attacker, knowing the defender's strategy, chooses which target to attack and for how long. If the attacker spends time $t$ at a target $i$ of value $α_i$, and if he leaves before the defender visits the target, his utility is $t \cdot α_i $; if the defender visits before he leaves, his utility is 0. The defender's goal is to minimize the attacker's utility. The defender's strategy consists of a schedule for visiting the targets; it takes her unit time to switch between targets. Such games are a simplified model of a number of real-world scenarios such as protecting computer networks from intruders, crops from thieves, etc. We show that optimal defender play for this continuous time security games reduces to the solution of a combinatorial question regarding the existence of infinite sequences over a finite alphabet, with the following properties for each symbol $i$: (1) $i$ constitutes a prescribed fraction $p_i$ of the sequence. (2) The occurrences of $i$ are spread apart close to evenly, in that the ratio of the longest to shortest interval between consecutive occurrences is bounded by a parameter $K$. We call such sequences $K$-quasi-regular. We show that, surprisingly, $2$-quasi-regular sequences suffice for optimal defender play. What is more, even randomized $2$-quasi-regular sequences suffice for optimality. We show that such sequences always exist, and can be calculated efficiently. The question of the least $K$ for which deterministic $K$-quasi-regular sequences exist is fascinating. Using an ergodic theoretical approach, we show that deterministic $3$-quasi-regular sequences always exist. For $2 \leq K < 3$ we do not know whether deterministic $K$-quasi-regular sequences always exist.
Nearly Optimal Bounds for Orthogonal Least Squares
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we study the orthogonal least squares (OLS) algorithm for sparse recovery. On the one hand, we show that if the sampling matrix $\mathbf{A}$ satisfies the restricted isometry property (RIP) of order $K + 1$ with isometry constant $$ δ_{K + 1} < \frac{1}{\sqrt{K+1}}, $$ then OLS exactly recovers the support of any $K$-sparse vector $\mathbf{x}$ from its samples $\mathbf{y} = \mathbf{A} \mathbf{x}$ in $K$ iterations. On the other hand, we show that OLS may not be able to recover the support of a $K$-sparse vector $\mathbf{x}$ in $K$ iterations for some $K$ if $$ δ_{K + 1} \geq \frac{1}{\sqrt{K+\frac{1}{4}}}. $$
Multiframe Motion Coupling for Video Super Resolution
Venue: arXiv cs.CV 2017
Year: 2017

The idea of video super resolution is to use different view points of a single scene to enhance the overall resolution and quality. Classical energy minimization approaches first establish a correspondence of the current frame to all its neighbors in some radius and then use this temporal information for enhancement. In this paper, we propose the first variational super resolution approach that computes several super resolved frames in one batch optimization procedure by incorporating motion information between the high-resolution image frames themselves. As a consequence, the number of motion estimation problems grows linearly in the number of frames, opposed to a quadratic growth of classical methods and temporal consistency is enforced naturally. We use infimal convolution regularization as well as an automatic parameter balancing scheme to automatically determine the reliability of the motion information and reweight the regularization locally. We demonstrate that our approach yields state-of-the-art results and even is competitive with machine learning approaches.
Sparse Representation in Fourier and Local Bases Using ProSparse: A Probabilistic Analysis
Venue: arXiv cs.IT 2017
Year: 2017

Finding the sparse representation of a signal in an overcomplete dictionary has attracted a lot of attention over the past years. This paper studies ProSparse, a new polynomial complexity algorithm that solves the sparse representation problem when the underlying dictionary is the union of a Vandermonde matrix and a banded matrix. Unlike our previous work which establishes deterministic (worst-case) sparsity bounds for ProSparse to succeed, this paper presents a probabilistic average-case analysis of the algorithm. Based on a generating-function approach, closed-form expressions for the exact success probabilities of ProSparse are given. The success probabilities are also analyzed in the high-dimensional regime. This asymptotic analysis characterizes a sharp phase transition phenomenon regarding the performance of the algorithm.
Automating the Last-Mile for High Performance Dense Linear Algebra
Venue: arXiv cs.MS 2017
Year: 2017

High performance dense linear algebra (DLA) libraries often rely on a general matrix multiply (Gemm) kernel that is implemented using assembly or with vector intrinsics. In particular, the real-valued Gemm kernels provide the overwhelming fraction of performance for the complex-valued Gemm kernels, along with the entire level-3 BLAS and many of the real and complex LAPACK routines. Thus,achieving high performance for the Gemm kernel translates into a high performance linear algebra stack above this kernel. However, it is a monumental task for a domain expert to manually implement the kernel for every library-supported architecture. This leads to the belief that the craft of a Gemm kernel is more dark art than science. It is this premise that drives the popularity of autotuning with code generation in the domain of DLA. This paper, instead, focuses on an analytical approach to code generation of the Gemm kernel for different architecture, in order to shed light on the details or voo-doo required for implementing a high performance Gemm kernel. We distill the implementation of the kernel into an even smaller kernel, an outer-product, and analytically determine how available SIMD instructions can be used to compute the outer-product efficiently. We codify this approach into a system to automatically generate a high performance SIMD implementation of the Gemm kernel. Experimental results demonstrate that our approach yields generated kernels with performance that is competitive with kernels implemented manually or using empirical search.
Optimal Scheduling of Multiple Sensors with Packet Length Constraint
Venue: arXiv cs.SY 2017
Year: 2017

This paper considers the problem of sensory data scheduling of multiple processes. There are $n$ independent linear time-invariant processes and a remote estimator monitoring all the processes. Each process is measured by a sensor, which sends its local state estimate to the remote estimator. The sizes of the packets are different due to different dimensions of each process, and thus it may take different lengths of time steps for the sensors to send their data. Because of bandwidth limitation, only a portion of all the sensors are allowed to transmit. Our goal is to minimize the average of estimation error covariance of the whole system at the remote estimator. The problem is formulated as a Markov decision process (MDP) with average cost over an infinite time horizon. We prove the existence of a deterministic and stationary policy for the problem. We also find that the optimal policy has a consistent behavior and threshold type structure. A numerical example is provided to illustrate our main results.
Heterogeneous Cellular Networks with Spatio-Temporal Traffic: Delay Analysis and Scheduling
Venue: arXiv cs.IT 2017
Year: 2017

Emergence of new types of services has led to various traffic and diverse delay requirements in fifth generation (5G) wireless networks. Meeting diverse delay requirements is one of the most critical goals for the design of 5G wireless networks. Though the delay of point-to-point communications has been well investigated, the delay of multi-point to multi-point communications has not been thoroughly studied since it is a complicated function of all links in the network. In this work, we propose a novel tractable approach to analyze the delay in the heterogenous cellular networks with spatio-temporal random arrival of traffic. Specifically, we propose the notion of \emph{delay outage} and evaluated the effect of different scheduling policies on the delay performance. Our numerical analysis reveals that offloading policy based on cell range expansion greatly reduces the macrocell traffic while bringing a small amount of growth for the picocell traffic. Our results also show that the delay performance of round-robin scheduling outperforms first in first out scheduling for heavy traffic, and it is reversed for light traffic. In summary, this analytical framework provides an understanding and a rule-of-thumb for the practical deployment of 5G systems where delay requirement is increasingly becoming a key concern.
Geometric deep learning: going beyond Euclidean data
Venue: arXiv cs.CV 2017
Year: 2017

Many scientific fields study data with an underlying structure that is a non-Euclidean space. Some examples include social networks in computational social sciences, sensor networks in communications, functional networks in brain imaging, regulatory networks in genetics, and meshed surfaces in computer graphics. In many applications, such geometric data are large and complex (in the case of social networks, on the scale of billions), and are natural targets for machine learning techniques. In particular, we would like to use deep neural networks, which have recently proven to be powerful tools for a broad range of problems from computer vision, natural language processing, and audio analysis. However, these tools have been most successful on data with an underlying Euclidean or grid-like structure, and in cases where the invariances of these structures are built into networks used to model them. Geometric deep learning is an umbrella term for emerging techniques attempting to generalize (structured) deep neural models to non-Euclidean domains such as graphs and manifolds. The purpose of this paper is to overview different examples of geometric deep learning problems and present available solutions, key difficulties, applications, and future research directions in this nascent field.
Asynchronous Distributed Automata: A Characterization of the Modal Mu-Fragment
Venue: arXiv cs.FL 2017
Year: 2017

We establish the equivalence between a class of asynchronous distributed automata and a small fragment of least fixpoint logic, when restricted to finite directed graphs. More specifically, the logic we consider is (a variant of) the fragment of the modal $μ$-calculus that allows least fixpoints but forbids greatest fixpoints. The corresponding automaton model uses a network of identical finite-state machines that communicate in an asynchronous manner and whose state diagram must be acyclic except for self-loops. Exploiting the connection with logic, we also prove that the expressive power of those machines is independent of whether or not messages can be lost.