OpenRaiser/Intern-Atlas huggingface dataset:
Parent Oriented Teacher Selection Causes Language Diversity
Venue: arXiv cs.CL 2017
Year: 2017

An evolutionary model for emergence of diversity in language is developed. We investigated the effects of two real life observations, namely, people prefer people that they communicate with well, and people interact with people that are physically close to each other. Clearly these groups are relatively small compared to the entire population. We restrict selection of the teachers from such small groups, called imitation sets, around parents. Then the child learns language from a teacher selected within the imitation set of her parent. As a result, there are subcommunities with their own languages developed. Within subcommunity comprehension is found to be high. The number of languages is related to the relative size of imitation set by a power law.
Learning to Multi-Task by Active Sampling
Venue: arXiv cs.NE 2017
Year: 2017

One of the long-standing challenges in Artificial Intelligence for learning goal-directed behavior is to build a single agent which can solve multiple tasks. Recent progress in multi-task learning for goal-directed sequential problems has been in the form of distillation based learning wherein a student network learns from multiple task-specific expert networks by mimicking the task-specific policies of the expert networks. While such approaches offer a promising solution to the multi-task learning problem, they require supervision from large expert networks which require extensive data and computation time for training. In this work, we propose an efficient multi-task learning framework which solves multiple goal-directed tasks in an on-line setup without the need for expert supervision. Our work uses active learning principles to achieve multi-task learning by sampling the harder tasks more than the easier ones. We propose three distinct models under our active sampling framework. An adaptive method with extremely competitive multi-tasking performance. A UCB-based meta-learner which casts the problem of picking the next task to train on as a multi-armed bandit problem. A meta-learning method that casts the next-task picking problem as a full Reinforcement Learning problem and uses actor critic methods for optimizing the multi-tasking performance directly. We demonstrate results in the Atari 2600 domain on seven multi-tasking instances: three 6-task instances, one 8-task instance, two 12-task instances and one 21-task instance.
Simple vs Optimal Mechanisms in Auctions with Convex Payments
Venue: arXiv cs.GT 2017
Year: 2017

We investigate approximately optimal mechanisms in settings where bidders' utility functions are non-linear; specifically, convex, with respect to payments (such settings arise, for instance, in procurement auctions for energy). We provide constant factor approximation guarantees for mechanisms that are independent of bidders' private information (i.e., prior-free), and for mechanisms that rely to an increasing extent on that information (i.e., detail free). We also describe experiments, which show that for randomly drawn monotone hazard rate distributions, our mechanisms achieve at least 80\% of the optimal revenue, on average. Both our theoretical and experimental results show that in the convex payment setting, it is desirable to allocate across multiple bidders, rather than only to bidders with the highest (virtual) value, as in the traditional quasi-linear utility setting.
Heterogeneity Preserving Upscaling for Heat Transport in Fractured Geothermal Reservoirs
Venue: arXiv cs.CE 2017
Year: 2017

In simulation of fluid injection in fractured geothermal reservoirs, the characteristics of the physical processes are severely affected by the local occurence of connected fractures. To resolve these structurally dominated processes, there is a need to develop discretization strategies that also limit computational effort. In this paper we present an upscaling methodology for geothermal heat transport with fractures represented explicitly in the computational grid. The heat transport is modeled by an advection-conduction equation for the temperature, and solved on a highly irregular coarse grid that preserves the fracture heterogeneity. The upscaling is based on different strategies for the advective term and the conductive term, respectively. The coarse scale advective term is constructed from sums of fine scale fluxes, whereas the coarse scale conductive term is constructed based on numerically computed basis functions. The method naturally incorporates a coupling between the matrix and the fractures via the discretization, so that explicit transfer terms that couple solution variables in the fractures and the matrix are avoided. Numerical results show that the upscaling methodology performs well, in particular for large upscaling ratios, and that it is applicable also to highly complex fracture networks.
Coding for Distributed Fog Computing
Venue: arXiv cs.IT 2017
Year: 2017

Redundancy is abundant in Fog networks (i.e., many computing and storage points) and grows linearly with network size. We demonstrate the transformational role of coding in Fog computing for leveraging such redundancy to substantially reduce the bandwidth consumption and latency of computing. In particular, we discuss two recently proposed coding concepts, namely Minimum Bandwidth Codes and Minimum Latency Codes, and illustrate their impacts in Fog computing. We also review a unified coding framework that includes the above two coding techniques as special cases, and enables a tradeoff between computation latency and communication load to optimize system performance. At the end, we will discuss several open problems and future research directions.
Preemptive Online Partitioning of Sequences
Venue: arXiv cs.DS 2017
Year: 2017

Online algorithms process their inputs piece by piece, taking irrevocable decisions for each data item. This model is too restrictive for most partitioning problems, since data that is yet to arrive may render it impossible to extend partial partitionings to the entire data set reasonably well. In this work, we show that preemption might be a potential remedy. We consider the problem of partitioning online sequences, where $p-1$ separators need to be inserted into a sequence of integers that arrives online so as to create $p$ contiguous partitions of similar weight. While without preemption no algorithm with non-trivial competitive ratio is possible, if preemption is allowed, i.e., inserted partition separators may be removed but not reinserted again, then we show that constant competitive algorithms can be obtained. Our contributions include: We first give a simple deterministic $2$-competitive preemptive algorithm for arbitrary $p$ and arbitrary sequences. Our main contribution is the design of a highly non-trivial partitioning scheme, which, under some natural conditions and $p$ being a power of two, allows us to improve the competitiveness to $1.68$. We also show that the competitiveness of deterministic (randomized) algorithms is at least $\frac{4}{3}$ (resp. $\frac{6}{5}$). For $p=2$, the problem corresponds to the interesting special case of preemptively guessing the center of a weighted request sequence. While deterministic algorithms fail here, we provide a randomized $1.345$-competitive algorithm for all-ones sequences and prove that this is optimal. For weighted sequences, we give a $1.628$-competitive algorithm and a lower bound of $1.5$.
An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits
Venue: arXiv cs.LG 2017
Year: 2017

We present a new strategy for gap estimation in randomized algorithms for multiarmed bandits and combine it with the EXP3++ algorithm of Seldin and Slivkins (2014). In the stochastic regime the strategy reduces dependence of regret on a time horizon from $(\ln t)^3$ to $(\ln t)^2$ and eliminates an additive factor of order $Δe^{1/Δ^2}$, where $Δ$ is the minimal gap of a problem instance. In the adversarial regime regret guarantee remains unchanged.
Density Independent Algorithms for Sparsifying $k$-Step Random Walks
Venue: arXiv cs.DS 2017
Year: 2017

We give faster algorithms for producing sparse approximations of the transition matrices of $k$-step random walks on undirected, weighted graphs. These transition matrices also form graphs, and arise as intermediate objects in a variety of graph algorithms. Our improvements are based on a better understanding of processes that sample such walks, as well as tighter bounds on key weights underlying these sampling processes. On a graph with $n$ vertices and $m$ edges, our algorithm produces a graph with about $n\log{n}$ edges that approximates the $k$-step random walk graph in about $m + n \log^4{n}$ time. In order to obtain this runtime bound, we also revisit "density independent" algorithms for sparsifying graphs whose runtime overhead is expressed only in terms of the number of vertices.
Throughput Optimal Beam Alignment in Millimeter Wave Networks
Venue: arXiv cs.IT 2017
Year: 2017

Millimeter wave communications rely on narrow-beam transmissions to cope with the strong signal attenuation at these frequencies, thus demanding precise beam alignment between transmitter and receiver. The communication overhead incurred to achieve beam alignment may become a severe impairment in mobile networks. This paper addresses the problem of optimizing beam alignment acquisition, with the goal of maximizing throughput. Specifically, the algorithm jointly determines the portion of time devoted to beam alignment acquisition, as well as, within this portion of time, the optimal beam search parameters, using the framework of Markov decision processes. It is proved that a bisection search algorithm is optimal, and that it outperforms exhaustive and iterative search algorithms proposed in the literature. The duration of the beam alignment phase is optimized so as to maximize the overall throughput. The numerical results show that the throughput, optimized with respect to the duration of the beam alignment phase, achievable under the exhaustive algorithm is 88.3% lower than that achievable under the bisection algorithm. Similarly, the throughput achievable by the iterative search algorithm for a division factor of 4 and 8 is, respectively, 12.8% and 36.4% lower than that achievable by the bisection algorithm.
Filtering Tweets for Social Unrest
Venue: arXiv cs.CL 2017
Year: 2017

Since the events of the Arab Spring, there has been increased interest in using social media to anticipate social unrest. While efforts have been made toward automated unrest prediction, we focus on filtering the vast volume of tweets to identify tweets relevant to unrest, which can be provided to downstream users for further analysis. We train a supervised classifier that is able to label Arabic language tweets as relevant to unrest with high reliability. We examine the relationship between training data size and performance and investigate ways to optimize the model building process while minimizing cost. We also explore how confidence thresholds can be set to achieve desired levels of performance.
Beating the World's Best at Super Smash Bros. with Deep Reinforcement Learning
Venue: arXiv cs.LG 2017
Year: 2017

There has been a recent explosion in the capabilities of game-playing artificial intelligence. Many classes of RL tasks, from Atari games to motor control to board games, are now solvable by fairly generic algorithms, based on deep learning, that learn to play from experience with minimal knowledge of the specific domain of interest. In this work, we will investigate the performance of these methods on Super Smash Bros. Melee (SSBM), a popular console fighting game. The SSBM environment has complex dynamics and partial observability, making it challenging for human and machine alike. The multi-player aspect poses an additional challenge, as the vast majority of recent advances in RL have focused on single-agent environments. Nonetheless, we will show that it is possible to train agents that are competitive against and even surpass human professionals, a new result for the multi-player video game setting.
An Efficient Four-Parameter Affine Motion Model for Video Coding
Venue: arXiv cs.MM 2017
Year: 2017

In this paper, we study a simplified affine motion model based coding framework to overcome the limitation of translational motion model and maintain low computational complexity. The proposed framework mainly has three key contributions. First, we propose to reduce the number of affine motion parameters from 6 to 4. The proposed four-parameter affine motion model can not only handle most of the complex motions in natural videos but also save the bits for two parameters. Second, to efficiently encode the affine motion parameters, we propose two motion prediction modes, i.e., advanced affine motion vector prediction combined with a gradient-based fast affine motion estimation algorithm and affine model merge, where the latter attempts to reuse the affine motion parameters (instead of the motion vectors) of neighboring blocks. Third, we propose two fast affine motion compensation algorithms. One is the one-step sub-pixel interpolation, which reduces the computations of each interpolation. The other is the interpolation-precision-based adaptive block size motion compensation, which performs motion compensation at the block level rather than the pixel level to reduce the interpolation times. Our proposed techniques have been implemented based on the state-of-the-art high efficiency video coding standard, and the experimental results show that the proposed techniques altogether achieve on average 11.1% and 19.3% bits saving for random access and low delay configurations, respectively, on typical video sequences that have rich rotation or zooming motions. Meanwhile, the computational complexity increases of both encoder and decoder are within an acceptable range.
Computing Influence of a Product through Uncertain Reverse Skyline
Venue: arXiv cs.DB 2017
Year: 2017

Understanding the influence of a product is crucially important for making informed business decisions. This paper introduces a new type of skyline queries, called uncertain reverse skyline, for measuring the influence of a probabilistic product in uncertain data settings. More specifically, given a dataset of probabilistic products P and a set of customers C, an uncertain reverse skyline of a probabilistic product q retrieves all customers c in C which include q as one of their preferred products. We present efficient pruning ideas and techniques for processing the uncertain reverse skyline query of a probabilistic product using R-Tree data index. We also present an efficient parallel approach to compute the uncertain reverse skyline and influence score of a probabilistic product. Our approach significantly outperforms the baseline approach derived from the existing literature. The efficiency of our approach is demonstrated by conducting extensive experiments with both real and synthetic datasets.
Ultra-Reliable Short-Packet Communications with Wireless Energy Transfer
Venue: arXiv cs.IT 2017
Year: 2017

We analyze and optimize a wireless system with energy transfer in the downlink and information transfer in the uplink, under quasi-static Nakagami-m fading. We consider ultra-reliable communication scenarios representative of the fifth-generation of wireless systems, with strict error and latency requirements. The error probability and delay are investigated, and an approximation for the former is given and validated through simulations. The numerical results demonstrate that there are optimum numbers of channels uses for both energy and information transfer for a given message length.
Answering Conjunctive Queries under Updates
Venue: arXiv cs.DB 2017
Year: 2017

We consider the task of enumerating and counting answers to $k$-ary conjunctive queries against relational databases that may be updated by inserting or deleting tuples. We exhibit a new notion of q-hierarchical conjunctive queries and show that these can be maintained efficiently in the following sense. During a linear time preprocessing phase, we can build a data structure that enables constant delay enumeration of the query results; and when the database is updated, we can update the data structure and restart the enumeration phase within constant time. For the special case of self-join free conjunctive queries we obtain a dichotomy: if a query is not q-hierarchical, then query enumeration with sublinear$^\ast$ delay and sublinear update time (and arbitrary preprocessing time) is impossible. For answering Boolean conjunctive queries and for the more general problem of counting the number of solutions of k-ary queries we obtain complete dichotomies: if the query's homomorphic core is q-hierarchical, then size of the the query result can be computed in linear time and maintained with constant update time. Otherwise, the size of the query result cannot be maintained with sublinear update time. All our lower bounds rely on the OMv-conjecture, a conjecture on the hardness of online matrix-vector multiplication that has recently emerged in the field of fine-grained complexity to characterise the hardness of dynamic problems. The lower bound for the counting problem additionally relies on the orthogonal vectors conjecture, which in turn is implied by the strong exponential time hypothesis. $^\ast)$ By sublinear we mean $O(n^{1-\varepsilon})$ for some $\varepsilon>0$, where $n$ is the size of the active domain of the current database.
Energy-Efficient Wireless Content Delivery with Proactive Caching
Venue: arXiv cs.NI 2017
Year: 2017

We propose an intelligent proactive content caching scheme to reduce the energy consumption in wireless downlink. We consider an online social network (OSN) setting where new contents are generated over time, and remain \textit{relevant} to the user for a random lifetime. Contents are downloaded to the user equipment (UE) through a time-varying wireless channel at an energy cost that depends on the channel state and the number of contents downloaded. The user accesses the OSN at random time instants, and consumes all the relevant contents. To reduce the energy consumption, we propose \textit{proactive caching} of contents under favorable channel conditions to a finite capacity cache memory. Assuming that the channel quality (or equivalently, the cost of downloading data) is memoryless over time slots, we show that the optimal caching policy, which may replace contents in the cache with shorter remaining lifetime with contents at the server that remain relevant longer, has certain threshold structure with respect to the channel quality. Since the optimal policy is computationally demanding in practice, we introduce a simplified caching scheme and optimize its parameters using policy search. We also present two lower bounds on the energy consumption. We demonstrate through numerical simulations that the proposed caching scheme significantly reduces the energy consumption compared to traditional reactive caching tools, and achieves close-to-optimal performance for a wide variety of system parameters.
3-Dimensional Optical Orthogonal Codes with Ideal Autocorrelation-Bounds and Optimal Constructions
Venue: arXiv cs.IT 2017
Year: 2017

Several new constructions of 3-dimensional optical orthogonal codes are presented here. In each case the codes have ideal autocorrelation $\mathbf{ λ_a=0} $, and in all but one case a cross correlation of $ \mathbf{λ_c=1} $. All codes produced are optimal with respect to the applicable Johnson bound either presented or developed here. Thus, on one hand the codes are as large as possible, and on the other, the bound(s) are shown to be tight. All codes are constructed by using a particular automorphism (a Singer cycle) of $ \mathbf{ PG(k,q)} $, the finite projective geometry of dimension $ k $ over the field of order $ \mathbf{q} $, or by using an affine analogue in $ AG(k,q) $.
Active One-shot Learning
Venue: arXiv cs.LG 2017
Year: 2017

Recent advances in one-shot learning have produced models that can learn from a handful of labeled examples, for passive classification and regression tasks. This paper combines reinforcement learning with one-shot learning, allowing the model to decide, during classification, which examples are worth labeling. We introduce a classification task in which a stream of images are presented and, on each time step, a decision must be made to either predict a label or pay to receive the correct label. We present a recurrent neural network based action-value function, and demonstrate its ability to learn how and when to request labels. Through the choice of reward function, the model can achieve a higher prediction accuracy than a similar model on a purely supervised task, or trade prediction accuracy for fewer label requests.
Toric Codes, Multiplicative Structure and Decoding
Venue: arXiv cs.IT 2017
Year: 2017

Long linear codes constructed from toric varieties over finite fields, their multiplicative structure and decoding. The main theme is the inherent multiplicative structure on toric codes. The multiplicative structure allows for \emph{decoding}, resembling the decoding of Reed-Solomon codes and aligns with decoding by error correcting pairs. We have used the multiplicative structure on toric codes to construct linear secret sharing schemes with \emph{strong multiplication} via Massey's construction generalizing the Shamir Linear secret sharing shemes constructed from Reed-Solomon codes. We have constructed quantum error correcting codes from toric surfaces by the Calderbank-Shor-Steane method.
Approximating the Frequency Response of Contractive Systems
Venue: arXiv cs.SY 2017
Year: 2017

We consider contractive systems whose trajectories evolve on a compact and convex state-space. It is well-known that if the time-varying vector field of the system is periodic then the system admits a unique globally asymptotically stable periodic solution. Obtaining explicit information on this periodic solution and its dependence on various parameters is important both theoretically and in numerous applications. We develop an approach for approximating such a periodic trajectory using the periodic trajectory of a simpler system (e.g. an LTI system). Our approximation includes an error bound that is based on the input-to-state stability property of contractive systems. We show that in some cases this error bound can be computed explicitly. We also use the bound to derive a new theoretical result, namely, that a contractive system with an additive periodic input behaves like a low pass filter. We demonstrate our results using several examples from systems biology.