OpenRaiser/Intern-Atlas huggingface dataset:
Learning Games and Rademacher Observations Losses
Venue: arXiv cs.LG 2016
Year: 2016

It has recently been shown that supervised learning with the popular logistic loss is equivalent to optimizing the exponential loss over sufficient statistics about the class: Rademacher observations (rados). We first show that this unexpected equivalence can actually be generalized to other example / rado losses, with necessary and sufficient conditions for the equivalence, exemplified on four losses that bear popular names in various fields: exponential (boosting), mean-variance (finance), Linear Hinge (on-line learning), ReLU (deep learning), and unhinged (statistics). Second, we show that the generalization unveils a surprising new connection to regularized learning, and in particular a sufficient condition under which regularizing the loss over examples is equivalent to regularizing the rados (with Minkowski sums) in the equivalent rado loss. This brings simple and powerful rado-based learning algorithms for sparsity-controlling regularization, that we exemplify on a boosting algorithm for the regularized exponential rado-loss, which formally boosts over four types of regularization, including the popular ridge and lasso, and the recently coined slope --- we obtain the first proven boosting algorithm for this last regularization. Through our first contribution on the equivalence of rado and example-based losses, Omega-R.AdaBoost~appears to be an efficient proxy to boost the regularized logistic loss over examples using whichever of the four regularizers. Experiments display that regularization consistently improves performances of rado-based learning, and may challenge or beat the state of the art of example-based learning even when learning over small sets of rados. Finally, we connect regularization to differential privacy, and display how tiny budgets can be afforded on big domains while beating (protected) example-based learning.
In a World That Counts: Clustering and Detecting Fake Social Engagement at Scale
Venue: arXiv cs.SI 2016
Year: 2016

How can web services that depend on user generated content discern fake social engagement activities by spammers from legitimate ones? In this paper, we focus on the social site of YouTube and the problem of identifying bad actors posting inorganic contents and inflating the count of social engagement metrics. We propose an effective method, Leas (Local Expansion at Scale), and show how the fake engagement activities on YouTube can be tracked over time by analyzing the temporal graph based on the engagement behavior pattern between users and YouTube videos. With the domain knowledge of spammer seeds, we formulate and tackle the problem in a semi-supervised manner --- with the objective of searching for individuals that have similar pattern of behavior as the known seeds --- based on a graph diffusion process via local spectral subspace. We offer a fast, scalable MapReduce deployment adapted from the localized spectral clustering algorithm. We demonstrate the effectiveness of our deployment at Google by achieving an manual review accuracy of 98% on YouTube Comments graph in practice. Comparing with the state-of-the-art algorithm CopyCatch, Leas achieves 10 times faster running time. Leas is actively in use at Google, searching for daily deceptive practices on YouTube's engagement graph spanning over a billion users.
Kauffman's adjacent possible in word order evolution
Venue: arXiv cs.CL 2016
Year: 2016

Word order evolution has been hypothesized to be constrained by a word order permutation ring: transitions involving orders that are closer in the permutation ring are more likely. The hypothesis can be seen as a particular case of Kauffman's adjacent possible in word order evolution. Here we consider the problem of the association of the six possible orders of S, V and O to yield a couple of primary alternating orders as a window to word order evolution. We evaluate the suitability of various competing hypotheses to predict one member of the couple from the other with the help of information theoretic model selection. Our ensemble of models includes a six-way model that is based on the word order permutation ring (Kauffman's adjacent possible) and another model based on the dual two-way of standard typology, that reduces word order to basic orders preferences (e.g., a preference for SV over VS and another for SO over OS). Our analysis indicates that the permutation ring yields the best model when favoring parsimony strongly, providing support for Kauffman's general view and a six-way typology.
Frame Structure Design and Analysis for Millimeter Wave Cellular Systems
Venue: arXiv cs.NI 2016
Year: 2016

The millimeter-wave (mmWave) frequencies have attracted considerable attention for fifth generation (5G) cellular communication as they offer orders of magnitude greater bandwidth than current cellular systems. However, the medium access control (MAC) layer may need to be significantly redesigned to support the highly directional transmissions, ultra-low latencies and high peak rates expected in mmWave communication. To address these challenges, we present a novel mmWave MAC layer frame structure with a number of enhancements including flexible, highly granular transmission times, dynamic control signal locations, extended messaging and ability to efficiently multiplex directional control signals. Analytic formulae are derived for the utilization and control overhead as a function of control periodicity, number of users, traffic statistics, signal-to-noise ratio and antenna gains. Importantly, the analysis can incorporate various front-end MIMO capability assumptions -- a critical feature of mmWave. Under realistic system and traffic assumptions, the analysis reveals that the proposed flexible frame structure design offers significant benefits over designs with fixed frame structures similar to current 4G long-term evolution (LTE). It is also shown that fully digital beamforming architectures offer significantly lower overhead compared to analog and hybrid beamforming under equivalent power budgets.
Synthesis of recurrent neural networks for dynamical system simulation
Venue: arXiv cs.NE 2016
Year: 2016

We review several of the most widely used techniques for training recurrent neural networks to approximate dynamical systems, then describe a novel algorithm for this task. The algorithm is based on an earlier theoretical result that guarantees the quality of the network approximation. We show that a feedforward neural network can be trained on the vector field representation of a given dynamical system using backpropagation, then recast, using matrix manipulations, as a recurrent network that replicates the original system's dynamics. After detailing this algorithm and its relation to earlier approaches, we present numerical examples that demonstrate its capabilities. One of the distinguishing features of our approach is that both the original dynamical systems and the recurrent networks that simulate them operate in continuous time.
Analysis and Optimization of Caching and Multicasting in Large-Scale Cache-Enabled Wireless Networks
Venue: arXiv cs.IT 2016
Year: 2016

Caching and multicasting at base stations are two promising approaches to support massive content delivery over wireless networks. However, existing analysis and designs do not fully explore and exploit the potential advantages of the two approaches. In this paper, we consider the analysis and optimization of caching and multicasting in a large-scale cache-enabled wireless network. We propose a random caching and multicasting scheme with a design parameter. By carefully handling different types of interferers and adopting appropriate approximations, we derive a tractable expression for the successful transmission probability in the general region, utilizing tools from stochastic geometry. We also obtain a closed-form expression for the successful transmission probability in the high signal-to-noise ratio (SNR) and user density region. Then, we consider the successful transmission probability maximization, which is a very complex non-convex problem in general. Using optimization techniques, we develop an iterative numerical algorithm to obtain a local optimal caching and multicasting design in the general region. To reduce complexity and maintain superior performance, we also derive an asymptotically optimal caching and multicasting design in the asymptotic region, based on a two-step optimization framework. Finally, numerical simulations show that the asymptotically optimal design achieves a significant gain in successful transmission probability over some baseline schemes in the general region.
The Limitations of Optimization from Samples
Venue: arXiv cs.DS 2016
Year: 2016

In this paper we consider the following question: can we optimize objective functions from the training data we use to learn them? We formalize this question through a novel framework we call optimization from samples (OPS). In OPS, we are given sampled values of a function drawn from some distribution and the objective is to optimize the function under some constraint. While there are interesting classes of functions that can be optimized from samples, our main result is an impossibility. We show that there are classes of functions which are statistically learnable and optimizable, but for which no reasonable approximation for optimization from samples is achievable. In particular, our main result shows that there is no constant factor approximation for maximizing coverage functions under a cardinality constraint using polynomially-many samples drawn from any distribution. We also show tight approximation guarantees for maximization under a cardinality constraint of several interesting classes of functions including unit-demand, additive, and general monotone submodular functions, as well as a constant factor approximation for monotone submodular functions with bounded curvature.
Local and global gestalt laws: A neurally based spectral approach
Venue: arXiv cs.CV 2016
Year: 2016

A mathematical model of figure-ground articulation is presented, taking into account both local and global gestalt laws. The model is compatible with the functional architecture of the primary visual cortex (V1). Particularly the local gestalt law of good continuity is described by means of suitable connectivity kernels, that are derived from Lie group theory and are neurally implemented in long range connectivity in V1. Different kernels are compatible with the geometric structure of cortical connectivity and they are derived as the fundamental solutions of the Fokker Planck, the Sub-Riemannian Laplacian and the isotropic Laplacian equations. The kernels are used to construct matrices of connectivity among the features present in a visual stimulus. Global gestalt constraints are then introduced in terms of spectral analysis of the connectivity matrix, showing that this processing can be cortically implemented in V1 by mean field neural equations. This analysis performs grouping of local features and individuates perceptual units with the highest saliency. Numerical simulations are performed and results are obtained applying the technique to a number of stimuli.
Car Segmentation and Pose Estimation using 3D Object Models
Venue: arXiv cs.CV 2016
Year: 2016

Image segmentation and 3D pose estimation are two key cogs in any algorithm for scene understanding. However, state-of-the-art CRF-based models for image segmentation rely mostly on 2D object models to construct top-down high-order potentials. In this paper, we propose new top-down potentials for image segmentation and pose estimation based on the shape and volume of a 3D object model. We show that these complex top-down potentials can be easily decomposed into standard forms for efficient inference in both the segmentation and pose estimation tasks. Experiments on a car dataset show that knowledge of segmentation helps perform pose estimation better and vice versa.
Content-Centric Sparse Multicast Beamforming for Cache-Enabled Cloud RAN
Venue: arXiv cs.IT 2016
Year: 2016

This paper presents a content-centric transmission design in a cloud radio access network (cloud RAN) by incorporating multicasting and caching. Users requesting a same content form a multicast group and are served by a same cluster of base stations (BSs) cooperatively. Each BS has a local cache and it acquires the requested contents either from its local cache or from the central processor (CP) via backhaul links. We investigate the dynamic content-centric BS clustering and multicast beamforming with respect to both channel condition and caching status. We first formulate a mixed-integer nonlinear programming problem of minimizing the weighted sum of backhaul cost and transmit power under the quality-of-service constraint for each multicast group. Theoretical analysis reveals that all the BSs caching a requested content can be included in the BS cluster of this content, regardless of the channel conditions. Then we reformulate an equivalent sparse multicast beamforming (SBF) problem. By adopting smoothed $\ell_0$-norm approximation and other techniques, the SBF problem is transformed into the difference of convex (DC) programs and effectively solved using the convex-concave procedure algorithms. Simulation results demonstrate significant advantage of the proposed content-centric transmission. The effects of three heuristic caching strategies are also evaluated.
Beauty and Brains: Detecting Anomalous Pattern Co-Occurrences
Venue: arXiv cs.AI 2016
Year: 2016

Our world is filled with both beautiful and brainy people, but how often does a Nobel Prize winner also wins a beauty pageant? Let us assume that someone who is both very beautiful and very smart is more rare than what we would expect from the combination of the number of beautiful and brainy people. Of course there will still always be some individuals that defy this stereotype; these beautiful brainy people are exactly the class of anomaly we focus on in this paper. They do not posses intrinsically rare qualities, it is the unexpected combination of factors that makes them stand out. In this paper we define the above described class of anomaly and propose a method to quickly identify them in transaction data. Further, as we take a pattern set based approach, our method readily explains why a transaction is anomalous. The effectiveness of our method is thoroughly verified with a wide range of experiments on both real world and synthetic data.
A Class of Linear Codes with a Few Weights
Venue: arXiv cs.IT 2016
Year: 2016

Linear codes have been an interesting subject of study for many years, as linear codes with few weights have applications in secrete sharing, authentication codes, association schemes, and strongly regular graphs. In this paper, a class of linear codes with a few weights over the finite field $\gf(p)$ are presented and their weight distributions are also determined, where $p$ is an odd prime. Some of the linear codes obtained are optimal in the sense that they meet certain bounds on linear codes.
A Triple Helix Model of Medical Innovation: Supply, Demand, and Technological Capabilities in terms of Medical Subject Headings
Venue: arXiv cs.DL 2016
Year: 2016

We develop a model of innovation that enables us to trace the interplay among three key dimensions of the innovation process: (i) demand of and (ii) supply for innovation, and (iii) technological capabilities available to generate innovation in the forms of products, processes, and services. Building on triple helix research, we use entropy statistics to elaborate an indicator of mutual information among these dimensions that can provide indication of reduction of uncertainty. To do so, we focus on the medical context, where uncertainty poses significant challenges to the governance of innovation. We use the Medical Subject Headings (MeSH) of MEDLINE/PubMed to identify publications classified within the categories "Diseases" (C), "Drugs and Chemicals" (D), "Analytic, Diagnostic, and Therapeutic Techniques and Equipment" (E) and use these as knowledge representations of demand, supply, and technological capabilities, respectively. Three case-studies of medical research areas are used as representative 'entry perspectives' of the medical innovation process. These are: (i) human papilloma virus, (ii) RNA interference, and (iii) magnetic resonance imaging. We find statistically significant periods of synergy among demand, supply, and technological capabilities (C-D-E) that point to three-dimensional interactions as a fundamental perspective for the understanding and governance of the uncertainty associated with medical innovation. Among the pairwise configurations in these contexts, the demand-technological capabilities (C-E) provided the strongest link, followed by the supply-demand (D-C) and the supply-technological capabilities (D-E) channels.
Adaptive Ensemble Learning with Confidence Bounds
Venue: arXiv cs.LG 2016
Year: 2016

Extracting actionable intelligence from distributed, heterogeneous, correlated and high-dimensional data sources requires run-time processing and learning both locally and globally. In the last decade, a large number of meta-learning techniques have been proposed in which local learners make online predictions based on their locally-collected data instances, and feed these predictions to an ensemble learner, which fuses them and issues a global prediction. However, most of these works do not provide performance guarantees or, when they do, these guarantees are asymptotic. None of these existing works provide confidence estimates about the issued predictions or rate of learning guarantees for the ensemble learner. In this paper, we provide a systematic ensemble learning method called Hedged Bandits, which comes with both long run (asymptotic) and short run (rate of learning) performance guarantees. Moreover, our approach yields performance guarantees with respect to the optimal local prediction strategy, and is also able to adapt its predictions in a data-driven manner. We illustrate the performance of Hedged Bandits in the context of medical informatics and show that it outperforms numerous online and offline ensemble learning methods.
A Latent-Variable Lattice Model
Venue: arXiv cs.LG 2016
Year: 2016

Markov random field (MRF) learning is intractable, and its approximation algorithms are computationally expensive. We target a small subset of MRF that is used frequently in computer vision. We characterize this subset with three concepts: Lattice, Homogeneity, and Inertia; and design a non-markov model as an alternative. Our goal is robust learning from small datasets. Our learning algorithm uses vector quantization and, at time complexity O(U log U) for a dataset of U pixels, is much faster than that of general-purpose MRF.
Deep Reinforcement Learning in Large Discrete Action Spaces
Venue: arXiv cs.AI 2016
Year: 2016

Being able to reason in an environment with a large number of discrete actions is essential to bringing reinforcement learning to a larger class of problems. Recommender systems, industrial plants and language models are only some of the many real-world tasks involving large numbers of discrete actions for which current methods are difficult or even often impossible to apply. An ability to generalize over the set of actions as well as sub-linear complexity relative to the size of the set are both necessary to handle such tasks. Current approaches are not able to provide both of these, which motivates the work in this paper. Our proposed approach leverages prior information about the actions to embed them in a continuous space upon which it can generalize. Additionally, approximate nearest-neighbor methods allow for logarithmic-time lookup complexity relative to the number of actions, which is necessary for time-wise tractable training. This combined approach allows reinforcement learning methods to be applied to large-scale learning problems previously intractable with current methods. We demonstrate our algorithm's abilities on a series of tasks having up to one million actions.
Communication and Randomness Lower Bounds for Secure Computation
Venue: arXiv cs.CR 2016
Year: 2016

In secure multiparty computation (MPC), mutually distrusting users collaborate to compute a function of their private data without revealing any additional information about their data to other users. While it is known that information theoretically secure MPC is possible among $n$ users (connected by secure and noiseless links and have access to private randomness) against the collusion of less than $n/2$ users in the honest-but-curious model, relatively less is known about the communication and randomness complexity of secure computation. In this work, we employ information theoretic techniques to obtain lower bounds on the amount of communication and randomness required for secure MPC. We restrict ourselves to a concrete interactive setting involving 3 users under which all functions are securely computable against corruption of a single user in the honest-but-curious model. We derive lower bounds for both the perfect security case (i.e., zero-error and no leakage of information) and asymptotic security (where the probability of error and information leakage vanish as block-length goes to $\infty$). Our techniques include the use of a data processing inequality for residual information (i.e., the gap between mutual information and Gács-Körner common information), a new information inequality for 3-user protocols, and the idea of distribution switching. Our lower bounds are shown to be tight for various functions of interest. In particular, we show concrete functions which have "communication-ideal" protocols, i.e., which achieve the minimum communication simultaneously on all links in the network, and also use minimum amount of randomness. Also, we obtain the first explicit example of a function that incurs a higher communication cost than the input length in the secure computation model of "Feige, Kilian, and Naor [STOC, 1994]", who had shown that such functions exist.
Colouring Diamond-free Graphs
Venue: arXiv cs.DM 2016
Year: 2016

The Colouring problem is that of deciding, given a graph $G$ and an integer $k$, whether $G$ admits a (proper) $k$-colouring. For all graphs $H$ up to five vertices, we classify the computational complexity of Colouring for $(\mbox{diamond},H)$-free graphs. Our proof is based on combining known results together with proving that the clique-width is bounded for $(\mbox{diamond}, P_1+2P_2)$-free graphs. Our technique for handling this case is to reduce the graph under consideration to a $k$-partite graph that has a very specific decomposition. As a by-product of this general technique we are also able to prove boundedness of clique-width for four other new classes of $(H_1,H_2)$-free graphs. As such, our work also continues a recent systematic study into the (un)boundedness of clique-width of $(H_1,H_2)$-free graphs, and our five new classes of bounded clique-width reduce the number of open cases from 13 to 8.
Context-Based Prediction of App Usage
Venue: arXiv cs.LG 2016
Year: 2016

There are around a hundred installed apps on an average smartphone. The high number of apps and the limited number of app icons that can be displayed on the device's screen requires a new paradigm to address their visibility to the user. In this paper we propose a new online algorithm for dynamically predicting a set of apps that the user is likely to use. The algorithm runs on the user's device and constantly learns the user's habits at a given time, location, and device state. It is designed to actively help the user to navigate to the desired app as well as to provide a personalized feeling, and hence is aimed at maximizing the AUC. We show both theoretically and empirically that the algorithm maximizes the AUC, and yields good results on a set of 1,000 devices.