OpenRaiser/Intern-Atlas huggingface dataset:
Strategic Network Formation with Attack and Immunization
Venue: arXiv cs.GT 2016
Year: 2016

Strategic network formation arises where agents receive benefit from connections to other agents, but also incur costs for forming links. We consider a new network formation game that incorporates an adversarial attack, as well as immunization against attack. An agent's benefit is the expected size of her connected component post-attack, and agents may also choose to immunize themselves from attack at some additional cost. Our framework is a stylized model of settings where reachability rather than centrality is the primary concern and vertices vulnerable to attacks may reduce risk via costly measures. In the reachability benefit model without attack or immunization, the set of equilibria is the empty graph and any tree. The introduction of attack and immunization changes the game dramatically; new equilibrium topologies emerge, some more sparse and some more dense than trees. We show that, under a mild assumption on the adversary, every equilibrium network with $n$ agents contains at most $2n-4$ edges for $n\geq 4$. So despite permitting topologies denser than trees, the amount of overbuilding is limited. We also show that attack and immunization don't significantly erode social welfare: every non-trivial equilibrium with respect to several adversaries has welfare at least as that of any equilibrium in the attack-free model. We complement our theory with simulations demonstrating fast convergence of a new bounded rationality dynamic which generalizes linkstable best response but is considerably more powerful in our game. The simulations further elucidate the wide variety of asymmetric equilibria and demonstrate topological consequences of the dynamics e.g. heavy-tailed degree distributions. Finally, we report on a behavioral experiment on our game with over 100 participants, where despite the complexity of the game, the resulting network was surprisingly close to equilibrium.
Moral Lineage Tracing
Venue: arXiv cs.CV 2016
Year: 2016

Lineage tracing, the tracking of living cells as they move and divide, is a central problem in biological image analysis. Solutions, called lineage forests, are key to understanding how the structure of multicellular organisms emerges. We propose an integer linear program (ILP) whose feasible solutions define a decomposition of each image in a sequence into cells (segmentation), and a lineage forest of cells across images (tracing). Unlike previous formulations, we do not constrain the set of decompositions, except by contracting pixels to superpixels. The main challenge, as we show, is to enforce the morality of lineages, i.e., the constraint that cells do not merge. To enforce morality, we introduce path-cut inequalities. To find feasible solutions of the NP-hard ILP, with certified bounds to the global optimum, we define efficient separation procedures and apply these as part of a branch-and-cut algorithm. We show the effectiveness of this approach by analyzing feasible solutions for real microscopy data in terms of bounds and run-time, and by their weighted edit distance to ground truth lineage forests traced by humans.
Randomization can be as helpful as a glimpse of the future in online computation
Venue: arXiv cs.DS 2016
Year: 2016

We provide simple but surprisingly useful direct product theorems for proving lower bounds on online algorithms with a limited amount of advice about the future. As a consequence, we are able to translate decades of research on randomized online algorithms to the advice complexity model. Doing so improves significantly on the previous best advice complexity lower bounds for many online problems, or provides the first known lower bounds. For example, if $n$ is the number of requests, we show that: (1) A paging algorithm needs $Ω(n)$ bits of advice to achieve a competitive ratio better than $H_k=Ω(\log k)$, where $k$ is the cache size. Previously, it was only known that $Ω(n)$ bits of advice were necessary to achieve a constant competitive ratio smaller than $5/4$. (2) Every $O(n^{1-\varepsilon})$-competitive vertex coloring algorithm must use $Ω(n\log n)$ bits of advice. Previously, it was only known that $Ω(n\log n)$ bits of advice were necessary to be optimal. For certain online problems, including the MTS, $k$-server, paging, list update, and dynamic binary search tree problem, our results imply that randomization and sublinear advice are equally powerful (if the underlying metric space or node set is finite). This means that several long-standing open questions regarding randomized online algorithms can be equivalently stated as questions regarding online algorithms with sublinear advice. For example, we show that there exists a deterministic $O(\log k)$-competitive $k$-server algorithm with advice complexity $o(n)$ if and only if there exists a randomized $O(\log k)$-competitive $k$-server algorithm without advice. Technically, our main direct product theorem is obtained by extending an information theoretical lower bound technique due to Emek, Fraigniaud, Korman, and Rosén [ICALP'09].
Convolutional Clustering for Unsupervised Learning
Venue: arXiv cs.LG 2016
Year: 2016

The task of labeling data for training deep neural networks is daunting and tedious, requiring millions of labels to achieve the current state-of-the-art results. Such reliance on large amounts of labeled data can be relaxed by exploiting hierarchical features via unsupervised learning techniques. In this work, we propose to train a deep convolutional network based on an enhanced version of the k-means clustering algorithm, which reduces the number of correlated parameters in the form of similar filters, and thus increases test categorization accuracy. We call our algorithm convolutional k-means clustering. We further show that learning the connection between the layers of a deep convolutional neural network improves its ability to be trained on a smaller amount of labeled data. Our experiments show that the proposed algorithm outperforms other techniques that learn filters unsupervised. Specifically, we obtained a test accuracy of 74.1% on STL-10 and a test error of 0.5% on MNIST.
Policy Distillation
Venue: arXiv cs.LG 2016
Year: 2016

Policies for complex visual tasks have been successfully learned with deep reinforcement learning, using an approach called deep Q-networks (DQN), but relatively large (task-specific) networks and extensive training are needed to achieve good performance. In this work, we present a novel method called policy distillation that can be used to extract the policy of a reinforcement learning agent and train a new network that performs at the expert level while being dramatically smaller and more efficient. Furthermore, the same method can be used to consolidate multiple task-specific policies into a single policy. We demonstrate these claims using the Atari domain and show that the multi-task distilled agent outperforms the single-task teachers as well as a jointly-trained DQN agent.
Neural network-based clustering using pairwise constraints
Venue: arXiv cs.LG 2016
Year: 2016

This paper presents a neural network-based end-to-end clustering framework. We design a novel strategy to utilize the contrastive criteria for pushing data-forming clusters directly from raw data, in addition to learning a feature embedding suitable for such clustering. The network is trained with weak labels, specifically partial pairwise relationships between data instances. The cluster assignments and their probabilities are then obtained at the output layer by feed-forwarding the data. The framework has the interesting characteristic that no cluster centers need to be explicitly specified, thus the resulting cluster distribution is purely data-driven and no distance metrics need to be predefined. The experiments show that the proposed approach beats the conventional two-stage method (feature embedding with k-means) by a significant margin. It also compares favorably to the performance of the standard cross entropy loss for classification. Robustness analysis also shows that the method is largely insensitive to the number of clusters. Specifically, we show that the number of dominant clusters is close to the true number of clusters even when a large k is used for clustering.
Efficient inference in occlusion-aware generative models of images
Venue: arXiv cs.LG 2016
Year: 2016

We present a generative model of images based on layering, in which image layers are individually generated, then composited from front to back. We are thus able to factor the appearance of an image into the appearance of individual objects within the image --- and additionally for each individual object, we can factor content from pose. Unlike prior work on layered models, we learn a shape prior for each object/layer, allowing the model to tease out which object is in front by looking for a consistent shape, without needing access to motion cues or any labeled data. We show that ordinary stochastic gradient variational bayes (SGVB), which optimizes our fully differentiable lower-bound on the log-likelihood, is sufficient to learn an interpretable representation of images. Finally we present experiments demonstrating the effectiveness of the model for inferring foreground and background objects in images.
Manifold Regularized Deep Neural Networks using Adversarial Examples
Venue: arXiv cs.LG 2016
Year: 2016

Learning meaningful representations using deep neural networks involves designing efficient training schemes and well-structured networks. Currently, the method of stochastic gradient descent that has a momentum with dropout is one of the most popular training protocols. Based on that, more advanced methods (i.e., Maxout and Batch Normalization) have been proposed in recent years, but most still suffer from performance degradation caused by small perturbations, also known as adversarial examples. To address this issue, we propose manifold regularized networks (MRnet) that utilize a novel training objective function that minimizes the difference between multi-layer embedding results of samples and those adversarial. Our experimental results demonstrated that MRnet is more resilient to adversarial examples and helps us to generalize representations on manifolds. Furthermore, combining MRnet and dropout allowed us to achieve competitive classification performances for three well-known benchmarks: MNIST, CIFAR-10, and SVHN.
Deep Manifold Traversal: Changing Labels with Convolutional Features
Venue: arXiv cs.LG 2016
Year: 2016

Many tasks in computer vision can be cast as a "label changing" problem, where the goal is to make a semantic change to the appearance of an image or some subject in an image in order to alter the class membership. Although successful task-specific methods have been developed for some label changing applications, to date no general purpose method exists. Motivated by this we propose deep manifold traversal, a method that addresses the problem in its most general form: it first approximates the manifold of natural images then morphs a test image along a traversal path away from a source class and towards a target class while staying near the manifold throughout. The resulting algorithm is surprisingly effective and versatile. It is completely data driven, requiring only an example set of images from the desired source and target domains. We demonstrate deep manifold traversal on highly diverse label changing tasks: changing an individual's appearance (age and hair color), changing the season of an outdoor image, and transforming a city skyline towards nighttime.
A convnet for non-maximum suppression
Venue: arXiv cs.CV 2016
Year: 2016

Non-maximum suppression (NMS) is used in virtually all state-of-the-art object detection pipelines. While essential object detection ingredients such as features, classifiers, and proposal methods have been extensively researched surprisingly little work has aimed to systematically address NMS. The de-facto standard for NMS is based on greedy clustering with a fixed distance threshold, which forces to trade-off recall versus precision. We propose a convnet designed to perform NMS of a given set of detections. We report experiments on a synthetic setup, and results on crowded pedestrian detection scenes. Our approach overcomes the intrinsic limitations of greedy NMS, obtaining better recall and precision.
Directional Initial Access for Millimeter Wave Cellular Systems
Venue: arXiv cs.IT 2016
Year: 2016

The millimeter wave (mmWave) bands have recently attracted considerable interest for next-generation cellular systems due to the massive available bandwidths at these frequencies. However, a key challenge in designing mmWave cellular systems is initial access -- the procedure by which a mobile establishes an initial link-layer connection to a base station cell. MmWave communication relies on highly directional transmissions and the initial access procedure must thus provide a mechanism by which initial transmission directions can be searched in a potentially large angular space. Design options are compared considering different scanning and signaling procedures to evaluate access delay and system overhead. The channel structure and multiple access issues are also considered. The analysis demonstrates significant benefits of low-resolution fully digital architectures in comparison to single stream analog beamforming.
TEMPO: Feature-Endowed Teichmüller Extremal Mappings of Point Clouds
Venue: arXiv cs.CG 2016
Year: 2016

In recent decades, the use of 3D point clouds has been widespread in computer industry. The development of techniques in analyzing point clouds is increasingly important. In particular, mapping of point clouds has been a challenging problem. In this paper, we develop a discrete analogue of the Teichmüller extremal mappings, which guarantee uniform conformality distortions, on point cloud surfaces. Based on the discrete analogue, we propose a novel method called TEMPO for computing Teichmüller extremal mappings between feature-endowed point clouds. Using our proposed method, the Teichmüller metric is introduced for evaluating the dissimilarity of point clouds. Consequently, our algorithm enables accurate recognition and classification of point clouds. Experimental results demonstrate the effectiveness of our proposed method.
Recurrent Gaussian Processes
Venue: arXiv cs.LG 2016
Year: 2016

We define Recurrent Gaussian Processes (RGP) models, a general family of Bayesian nonparametric models with recurrent GP priors which are able to learn dynamical patterns from sequential data. Similar to Recurrent Neural Networks (RNNs), RGPs can have different formulations for their internal states, distinct inference methods and be extended with deep structures. In such context, we propose a novel deep RGP model whose autoregressive states are latent, thereby performing representation and dynamical learning simultaneously. To fully exploit the Bayesian nature of the RGP model we develop the Recurrent Variational Bayes (REVARB) framework, which enables efficient inference and strong regularization through coherent propagation of uncertainty across the RGP layers and states. We also introduce a RGP extension where variational parameters are greatly reduced by being reparametrized through RNN-based sequential recognition models. We apply our model to the tasks of nonlinear system identification and human motion modeling. The promising obtained results indicate that our RGP model maintains its highly flexibility while being able to avoid overfitting and being applicable even when larger datasets are not available.
Unsupervised learning of object semantic parts from internal states of CNNs by population encoding
Venue: arXiv cs.LG 2016
Year: 2016

We address the key question of how object part representations can be found from the internal states of CNNs that are trained for high-level tasks, such as object classification. This work provides a new unsupervised method to learn semantic parts and gives new understanding of the internal representations of CNNs. Our technique is based on the hypothesis that semantic parts are represented by populations of neurons rather than by single filters. We propose a clustering technique to extract part representations, which we call Visual Concepts. We show that visual concepts are semantically coherent in that they represent semantic parts, and visually coherent in that corresponding image patches appear very similar. Also, visual concepts provide full spatial coverage of the parts of an object, rather than a few sparse parts as is typically found in keypoint annotations. Furthermore, We treat single visual concept as part detector and evaluate it for keypoint detection using the PASCAL3D+ dataset and for part detection using our newly annotated ImageNetPart dataset. The experiments demonstrate that visual concepts can be used to detect parts. We also show that some visual concepts respond to several semantic parts, provided these parts are visually similar. Thus visual concepts have the essential properties: semantic meaning and detection capability. Note that our ImageNetPart dataset gives rich part annotations which cover the whole object, making it useful for other part-related applications.
Constructive Galois Connections: Taming the Galois Connection Framework for Mechanized Metatheory
Venue: arXiv cs.PL 2016
Year: 2016

Galois connections are a foundational tool for structuring abstraction in semantics and their use lies at the heart of the theory of abstract interpretation. Yet, mechanization of Galois connections remains limited to restricted modes of use, preventing their general application in mechanized metatheory and certified programming. This paper presents constructive Galois connections, a variant of Galois connections that is effective both on paper and in proof assistants; is complete with respect to a large subset of classical Galois connections; and enables more general reasoning principles, including the "calculational" style advocated by Cousot. To design constructive Galois connection we identify a restricted mode of use of classical ones which is both general and amenable to mechanization in dependently-typed functional programming languages. Crucial to our metatheory is the addition of monadic structure to Galois connections to control a "specification effect". Effectful calculations may reason classically, while pure calculations have extractable computational content. Explicitly moving between the worlds of specification and implementation is enabled by our metatheory. To validate our approach, we provide two case studies in mechanizing existing proofs from the literature: one uses calculational abstract interpretation to design a static analyzer, the other forms a semantic basis for gradual typing. Both mechanized proofs closely follow their original paper-and-pencil counterparts, employ reasoning principles not captured by previous mechanization approaches, support the extraction of verified algorithms, and are novel.
Occurrence Typing Modulo Theories
Venue: arXiv cs.PL 2016
Year: 2016

We present a new type system combining occurrence typing, previously used to type check programs in dynamically-typed languages such as Racket, JavaScript, and Ruby, with dependent refinement types. We demonstrate that the addition of refinement types allows the integration of arbitrary solver-backed reasoning about logical propositions from external theories. By building on occurrence typing, we can add our enriched type system as an extension of Typed Racket---adding dependency and refinement reuses the existing formalism while increasing its expressiveness. Dependent refinement types allow Typed Racket programmers to express rich type relationships, ranging from data structure invariants such as red-black tree balance to preconditions such as vector bounds. Refinements allow programmers to embed the propositions that occurrence typing in Typed Racket already reasons about into their types. Further, extending occurrence typing to refinements allows us to make the underlying formalism simpler and more powerful. In addition to presenting the design of our system, we present a formal model of the system, show how to integrate it with theories over both linear arithmetic and bitvectors, and evaluate the system in the context of the full Typed Racket implementation. Specifically, we take safe vector access as a case study, and examine all vector accesses in a 56,000 line corpus of Typed Racket programs. Our system is able to prove that 50% of these are safe with no new annotation, and with a few annotations and modifications, we can capture close to 80%.
Propagation Path Loss Models for 5G Urban Micro- and Macro-Cellular Scenarios
Venue: arXiv cs.IT 2016
Year: 2016

This paper presents and compares two candidate large-scale propagation path loss models, the alpha-beta-gamma (ABG) model and the close-in (CI) free space reference distance model, for the design of fifth generation (5G) wireless communication systems in urban micro- and macro-cellular scenarios. Comparisons are made using the data obtained from 20 propagation measurement campaigns or ray-tracing studies from 2 GHz to 73.5 GHz over distances ranging from 5 m to 1429 m. The results show that the one-parameter CI model has a very similar goodness of fit (i.e., the shadow fading standard deviation) in both line-of-sight and non-line-of-sight environments, while offering substantial simplicity and more stable behavior across frequencies and distances, as compared to the three-parameter ABG model. Additionally, the CI model needs only one very subtle and simple modification to the existing 3GPP floating-intercept path loss model (replacing a constant with a close-in free space reference value) in order to provide greater simulation accuracy, more simplicity, better repeatability across experiments, and higher stability across a vast range of frequencies.
Tradeoffs for nearest neighbors on the sphere
Venue: arXiv cs.DS 2016
Year: 2016

We consider tradeoffs between the query and update complexities for the (approximate) nearest neighbor problem on the sphere, extending the recent spherical filters to sparse regimes and generalizing the scheme and analysis to account for different tradeoffs. In a nutshell, for the sparse regime the tradeoff between the query complexity $n^{ρ_q}$ and update complexity $n^{ρ_u}$ for data sets of size $n$ is given by the following equation in terms of the approximation factor $c$ and the exponents $ρ_q$ and $ρ_u$: $$c^2\sqrt{ρ_q}+(c^2-1)\sqrt{ρ_u}=\sqrt{2c^2-1}.$$ For small $c=1+ε$, minimizing the time for updates leads to a linear space complexity at the cost of a query time complexity $n^{1-4ε^2}$. Balancing the query and update costs leads to optimal complexities $n^{1/(2c^2-1)}$, matching bounds from [Andoni-Razenshteyn, 2015] and [Dubiner, IEEE-TIT'10] and matching the asymptotic complexities of [Andoni-Razenshteyn, STOC'15] and [Andoni-Indyk-Laarhoven-Razenshteyn-Schmidt, NIPS'15]. A subpolynomial query time complexity $n^{o(1)}$ can be achieved at the cost of a space complexity of the order $n^{1/(4ε^2)}$, matching the bound $n^{Ω(1/ε^2)}$ of [Andoni-Indyk-Patrascu, FOCS'06] and [Panigrahy-Talwar-Wieder, FOCS'10] and improving upon results of [Indyk-Motwani, STOC'98] and [Kushilevitz-Ostrovsky-Rabani, STOC'98]. For large $c$, minimizing the update complexity results in a query complexity of $n^{2/c^2+O(1/c^4)}$, improving upon the related exponent for large $c$ of [Kapralov, PODS'15] by a factor $2$, and matching the bound $n^{Ω(1/c^2)}$ of [Panigrahy-Talwar-Wieder, FOCS'08]. Balancing the costs leads to optimal complexities $n^{1/(2c^2-1)}$, while a minimum query time complexity can be achieved with update complexity $n^{2/c^2+O(1/c^4)}$, improving upon the previous best exponents of Kapralov by a factor $2$.