OpenRaiser/Intern-Atlas huggingface dataset:
TStarBots: Defeating the Cheating Level Builtin AI in StarCraft II in the Full Game
Venue: arXiv cs.AI 2018
Year: 2018

Starcraft II (SC2) is widely considered as the most challenging Real Time Strategy (RTS) game. The underlying challenges include a large observation space, a huge (continuous and infinite) action space, partial observations, simultaneous move for all players, and long horizon delayed rewards for local decisions. To push the frontier of AI research, Deepmind and Blizzard jointly developed the StarCraft II Learning Environment (SC2LE) as a testbench of complex decision making systems. SC2LE provides a few mini games such as MoveToBeacon, CollectMineralShards, and DefeatRoaches, where some AI agents have achieved the performance level of human professional players. However, for full games, the current AI agents are still far from achieving human professional level performance. To bridge this gap, we present two full game AI agents in this paper - the AI agent TStarBot1 is based on deep reinforcement learning over a flat action structure, and the AI agent TStarBot2 is based on hard-coded rules over a hierarchical action structure. Both TStarBot1 and TStarBot2 are able to defeat the built-in AI agents from level 1 to level 10 in a full game (1v1 Zerg-vs-Zerg game on the AbyssalReef map), noting that level 8, level 9, and level 10 are cheating agents with unfair advantages such as full vision on the whole map and resource harvest boosting. To the best of our knowledge, this is the first public work to investigate AI agents that can defeat the built-in AI in the StarCraft II full game.
Covering and Packing of Rectilinear Subdivision
Venue: arXiv cs.CG 2018
Year: 2018

We study a class of geometric covering and packing problems for bounded regions on the plane. We are given a set of axis-parallel line segments that induces a planar subdivision with a set of bounded (rectilinear) faces. We are interested in the following problems. (P1) Stabbing-Subdivision: Stab all bounded faces by selecting a minimum number of points in the plane. (P2) Independent-Subdivision: Select a maximum size collection of pairwise non-intersecting bounded faces. (P3) Dominating-Subdivision: Select a minimum size collection of faces such that any other face has a non-empty intersection (i.e., sharing an edge or a vertex) with some selected faces. We show that these problems are NP-hard. We even prove that these problems are NP-hard when we concentrate only on the rectangular faces of the subdivision. Further, we provide constant factor approximation algorithms for the Stabbing-Subdivision problem.
Analog Coding Frame-work
Venue: arXiv cs.IT 2018
Year: 2018

Analog coding is a low-complexity method to combat erasures, based on linear redundancy in the signal space domain. Previous work examined "band-limited discrete Fourier transform (DFT)" codes for Gaussian channels with erasures or impulses. We extend this concept to source coding with "erasure side-information" at the encoder and show that the performance of band-limited DFT can be significantly improved using irregular spectrum, and more generally, using equiangular tight frames (ETF). Frames are overcomplete bases and are widely used in mathematics, computer science, engineering, and statistics since they provide a stable and robust decomposition. Design of frames with favorable properties of random subframes is motivated in variety of applications, including code-devision multiple access (CDMA), compressed sensing and analog coding. We present a novel relation between deterministic frames and random matrix theory. We show empirically that the MANOVA ensemble offers a universal description of the spectra of randomly selected subframes with constant aspect ratios, taken from deterministic near-ETFs. Moreover, we derive an analytic framework and bring a formal validation for some of the empirical results, specifically that the asymptotic form for the moments of high orders of subsets of ETF agree with that of MANOVA. Finally, when exploring over-complete bases, the Welch bound is a lower bound on the root mean square cross correlation between vectors. We extend the Welch bound to an erasure setting, in which a reduced frame, composed of a random subset of Bernoulli selected vectors, is of interest. The lower bound involves moment of the reduced frame, and it is tight for ETFs and asymptotically coincides with the MANOVA moments. This result offers a novel perspective on the superiority of ETFs over other frames.
A Generalized Representer Theorem for Hilbert Space - Valued Functions
Venue: arXiv cs.LG 2018
Year: 2018

The necessary and sufficient conditions for existence of a generalized representer theorem are presented for learning Hilbert space-valued functions. Representer theorems involving explicit basis functions and Reproducing Kernels are a common occurrence in various machine learning algorithms like generalized least squares, support vector machines, Gaussian process regression and kernel based deep neural networks to name a few. Due to the more general structure of the underlying variational problems, the theory is also relevant to other application areas like optimal control, signal processing and decision making. We present the generalized representer as a unified view for supervised and semi-supervised learning methods, using the theory of linear operators and subspace valued maps. The implications of the theorem are presented with examples of multi input-multi output regression, kernel based deep neural networks, stochastic regression and sparsity learning problems as being special cases in this unified view.
Zero-error communication over adder MAC
Venue: arXiv cs.IT 2018
Year: 2018

Adder MAC is a simple noiseless multiple-access channel (MAC), where if users send messages $X_1,\ldots,X_h\in \{0,1\}^n$, then the receiver receives $Y = X_1+\cdots+X_h$ with addition over $\mathbb{Z}$. Communication over the noiseless adder MAC has been studied for more than fifty years. There are two models of particular interest: uniquely decodable code tuples, and $B_h$-codes. In spite of the similarities between these two models, lower bounds and upper bounds of the optimal sum rate of uniquely decodable code tuple asymptotically match as number of users goes to infinity, while there is a gap of factor two between lower bounds and upper bounds of the optimal rate of $B_h$-codes. The best currently known $B_h$-codes for $h\ge 3$ are constructed using random coding. In this work, we study variants of the random coding method and related problems, in hope of achieving $B_h$-codes with better rate. Our contribution include the following. (1) We prove that changing the underlying distribution used in random coding cannot improve the rate. (2) We determine the rate of a list-decoding version of $B_h$-codes achieved by the random coding method. (3) We study several related problems about Rényi entropy.
Predicting Periodicity with Temporal Difference Learning
Venue: arXiv cs.LG 2018
Year: 2018

Temporal difference (TD) learning is an important approach in reinforcement learning, as it combines ideas from dynamic programming and Monte Carlo methods in a way that allows for online and incremental model-free learning. A key idea of TD learning is that it is learning predictive knowledge about the environment in the form of value functions, from which it can derive its behavior to address long-term sequential decision making problems. The agent's horizon of interest, that is, how immediate or long-term a TD learning agent predicts into the future, is adjusted through a discount rate parameter. In this paper, we introduce an alternative view on the discount rate, with insight from digital signal processing, to include complex-valued discounting. Our results show that setting the discount rate to appropriately chosen complex numbers allows for online and incremental estimation of the Discrete Fourier Transform (DFT) of a signal of interest with TD learning. We thereby extend the types of knowledge representable by value functions, which we show are particularly useful for identifying periodic effects in the reward sequence.
Data Shuffling in Wireless Distributed Computing via Low-Rank Optimization
Venue: arXiv cs.IT 2018
Year: 2018

Intelligent mobile platforms such as smart vehicles and drones have recently become the focus of attention for onboard deployment of machine learning mechanisms to enable low latency decisions with low risk of privacy breach. However, most such machine learning algorithms are both computation-and-memory intensive, which makes it highly difficult to implement the requisite computations on a single device of limited computation, memory, and energy resources. Wireless distributed computing presents new opportunities by pooling the computation and storage resources among devices. For low-latency applications, the key bottleneck lies in the exchange of intermediate results among mobile devices for data shuffling. To improve communication efficiency, we propose a co-channel communication model and design transceivers by exploiting the locally computed intermediate values as side information. A low-rank optimization model is proposed to maximize the achieved degrees-of-freedom (DoF) by establishing the interference alignment condition for data shuffling. Unfortunately, existing approaches to approximate the rank function fail to yield satisfactory performance due to the poor structure in the formulated low-rank optimization problem. In this paper, we develop an efficient DC algorithm to solve the presented low-rank optimization problem by proposing a novel DC representation for the rank function. Numerical experiments demonstrate that the proposed DC approach can significantly improve the communication efficiency whereas the achievable DoF almost remains unchanged when the number of mobile devices grows.
Impacts of Community and Distributed Energy Storage Systems on Unbalanced Low Voltage Networks
Venue: arXiv cs.SY 2018
Year: 2018

Energy storage systems (EES) are expected to be an indispensable resource for mitigating the effects on networks of high penetrations of distributed generation in the near future. This paper analyzes the benefits of EES in unbalanced low voltage (LV) networks regarding three aspects, namely, power losses, the hosting capacity and network unbalance. For doing so, a mixed integer quadratic programmming model (MIQP) is developed to minimize annual energy losses and determine the sizing and placement of ESS, while satisfying voltage constraints. A real unbalanced LV UK grid is adopted to examine the effects of ESS under two scenarios: the installation of one community ESS (CESS) and multiple distributed ESSs (DESSs). The results illustrate that both scenarios present high performance in accomplishing the above tasks, while DESSs, with the same aggregated size, are slightly better. This margin is expected to be amplified as the aggregated size of DESSs increases.
Diffraction-Aware Sound Localization for a Non-Line-of-Sight Source
Venue: arXiv cs.RO 2018
Year: 2018

We present a novel sound localization algorithm for a non-line-of-sight (NLOS) sound source in indoor environments. Our approach exploits the diffraction properties of sound waves as they bend around a barrier or an obstacle in the scene. We combine a ray tracing based sound propagation algorithm with a Uniform Theory of Diffraction (UTD) model, which simulate bending effects by placing a virtual sound source on a wedge in the environment. We precompute the wedges of a reconstructed mesh of an indoor scene and use them to generate diffraction acoustic rays to localize the 3D position of the source. Our method identifies the convergence region of those generated acoustic rays as the estimated source position based on a particle filter. We have evaluated our algorithm in multiple scenarios consisting of a static and dynamic NLOS sound source. In our tested cases, our approach can localize a source position with an average accuracy error, 0.7m, measured by the L2 distance between estimated and actual source locations in a 7m*7m*3m room. Furthermore, we observe 37% to 130% improvement in accuracy over a state-of-the-art localization method that does not model diffraction effects, especially when a sound source is not visible to the robot.
Optimization of hybrid parallel application execution in heterogeneous high performance computing systems considering execution time and power consumption
Venue: arXiv cs.DC 2018
Year: 2018

Many important computational problems require utilization of high performance computing (HPC) systems that consist of multi-level structures combining higher and higher numbers of devices with various characteristics. Utilizing full power of such systems requires programming parallel applications that are hybrid in two meanings: they can utilize parallelism on multiple levels at the same time and combine together programming interfaces specific for various types of computing devices. The main goal of parallel processing is increasing the processing performance, and therefore decreasing the application execution time. The international HPC community is targeting development of "Exascale" supercomputers (able to sustain $10^{18}$ floating point operations per second) by the year 2020. One of the main obstacles to achieving this goal is power consumption of the computing systems that exceeds the energy supply limits. New programming models and algorithms that consider this criterion are one of the key areas where significant progress is necessary in order to achieve the goal. The goal of the dissertation is to extract a general model of hybrid parallel application execution in heterogeneous HPC systems that is a synthesis of existing specific approaches and developing an optimization methodology for such execution aiming for minimization of the contradicting objectives of application execution time and power consumption of the utilized computing hardware. Both meanings of the application hybridity result in multiplicity of execution parameters of nontrivial interdependences and influence on the considered optimization criteria. Mapping of the application processes on computing devices has also a significant impact on these criteria.
The unreasonable effectiveness of small neural ensembles in high-dimensional brain
Venue: arXiv cs.AI 2018
Year: 2018

Despite the widely-spread consensus on the brain complexity, sprouts of the single neuron revolution emerged in neuroscience in the 1970s. They brought many unexpected discoveries, including grandmother or concept cells and sparse coding of information in the brain. In machine learning for a long time, the famous curse of dimensionality seemed to be an unsolvable problem. Nevertheless, the idea of the blessing of dimensionality becomes gradually more and more popular. Ensembles of non-interacting or weakly interacting simple units prove to be an effective tool for solving essentially multidimensional problems. This approach is especially useful for one-shot (non-iterative) correction of errors in large legacy artificial intelligence systems. These simplicity revolutions in the era of complexity have deep fundamental reasons grounded in geometry of multidimensional data spaces. To explore and understand these reasons we revisit the background ideas of statistical physics. In the course of the 20th century they were developed into the concentration of measure theory. New stochastic separation theorems reveal the fine structure of the data clouds. We review and analyse biological, physical, and mathematical problems at the core of the fundamental question: how can high-dimensional brain organise reliable and fast learning in high-dimensional world of data by simple tools? Two critical applications are reviewed to exemplify the approach: one-shot correction of errors in intellectual systems and emergence of static and associative memories in ensembles of single neurons.
Should I Bug You? Identifying Domain Experts in Software Projects Using Code Complexity Metrics
Venue: arXiv cs.SE 2018
Year: 2018

In any sufficiently complex software system there are experts, having a deeper understanding of parts of the system than others. However, it is not always clear who these experts are and which particular parts of the system they can provide help with. We propose a framework to elicit the expertise of developers and recommend experts by analyzing complexity measures over time. Furthermore, teams can detect those parts of the software for which currently no, or only few experts exist and take preventive actions to keep the collective code knowledge and ownership high. We employed the developed approach at a medium-sized company. The results were evaluated with a survey, comparing the perceived and the computed expertise of developers. We show that aggregated code metrics can be used to identify experts for different software components. The identified experts were rated as acceptable candidates by developers in over 90% of all cases.
Inferring Multiplex Diffusion Network via Multivariate Marked Hawkes Process
Venue: arXiv cs.SI 2018
Year: 2018

Understanding the diffusion in social network is an important task. However, this task is challenging since (1) the network structure is usually hidden with only observations of events like "post" or "repost" associated with each node, and (2) the interactions between nodes encompass multiple distinct patterns which in turn affect the diffusion patterns. For instance, social interactions seldom develop on a single channel, and multiple relationships can bind pairs of people due to their various common interests. Most previous work considers only one of these two challenges which is apparently unrealistic. In this paper, we study the problem of \emph{inferring multiplex network} in social networks. We propose the Multiplex Diffusion Model (MDM) which incorporates the multivariate marked Hawkes process and topic model to infer the multiplex structure of social network. A MCMC based algorithm is developed to infer the latent multiplex structure and to estimate the node-related parameters. We evaluate our model based on both synthetic and real-world datasets. The results show that our model is more effective in terms of uncovering the multiplex network structure.
Benchmarking Reinforcement Learning Algorithms on Real-World Robots
Venue: arXiv cs.LG 2018
Year: 2018

Through many recent successes in simulation, model-free reinforcement learning has emerged as a promising approach to solving continuous control robotic tasks. The research community is now able to reproduce, analyze and build quickly on these results due to open source implementations of learning algorithms and simulated benchmark tasks. To carry forward these successes to real-world applications, it is crucial to withhold utilizing the unique advantages of simulations that do not transfer to the real world and experiment directly with physical robots. However, reinforcement learning research with physical robots faces substantial resistance due to the lack of benchmark tasks and supporting source code. In this work, we introduce several reinforcement learning tasks with multiple commercially available robots that present varying levels of learning difficulty, setup, and repeatability. On these tasks, we test the learning performance of off-the-shelf implementations of four reinforcement learning algorithms and analyze sensitivity to their hyper-parameters to determine their readiness for applications in various real-world tasks. Our results show that with a careful setup of the task interface and computations, some of these implementations can be readily applicable to physical robots. We find that state-of-the-art learning algorithms are highly sensitive to their hyper-parameters and their relative ordering does not transfer across tasks, indicating the necessity of re-tuning them for each task for best performance. On the other hand, the best hyper-parameter configuration from one task may often result in effective learning on held-out tasks even with different robots, providing a reasonable default. We make the benchmark tasks publicly available to enhance reproducibility in real-world reinforcement learning.
Survey on Error Concealment Strategies and Subjective Testing of 3D Videos
Venue: arXiv cs.MM 2018
Year: 2018

Over the last decade, different technologies to visualize 3D scenes have been introduced and improved. These technologies include stereoscopic, multi-view, integral imaging and holographic types. Despite increasing consumer interest; poor image quality, crosstalk or side effects of 3D displays and also the lack of defined broadcast standards has hampered the advancement of 3D displays to the mass consumer market. Also, in real time transmission of 3DTV sequences over packet-based networks may results in visual quality degradations due to packet loss and others. In the conventional 2D videos different extrapolation and directional interpolation strategies have been used for concealing the missing blocks but in 3D, it is still an emerging field of research. Few studies have been carried out to define the assessment methods of stereoscopic images and videos. But through industrial and commercial perspective, subjective quality evaluation is the most direct way to evaluate human perception on 3DTV systems. This paper reviews the state-of-the-art error concealment strategies and the subjective evaluation of 3D videos and proposes a low complexity frame loss concealment method for the video decoder. Subjective testing on prominent datasets videos and comparison with existing concealment methods show that the proposed method is very much efficient to conceal errors of stereoscopic videos in terms of computation time, comfort and distortion.
Metric Learning for Phoneme Perception
Venue: arXiv cs.LG 2018
Year: 2018

Metric functions for phoneme perception capture the similarity structure among phonemes in a given language and therefore play a central role in phonology and psycho-linguistics. Various phenomena depend on phoneme similarity, such as spoken word recognition or serial recall from verbal working memory. This study presents a new framework for learning a metric function for perceptual distances among pairs of phonemes. Previous studies have proposed various metric functions, from simple measures counting the number of phonetic dimensions that two phonemes share (place-, manner-of-articulation and voicing), to more sophisticated ones such as deriving perceptual distances based on the number of natural classes that both phonemes belong to. However, previous studies have manually constructed the metric function, which may lead to unsatisfactory account of the empirical data. This study presents a framework to derive the metric function from behavioral data on phoneme perception using learning algorithms. We first show that this approach outperforms previous metrics suggested in the literature in predicting perceptual distances among phoneme pairs. We then study several metric functions derived by the learning algorithms and show how perceptual saliencies of phonological features can be derived from them. For English, we show that the derived perceptual saliencies are in accordance with a previously described order among phonological features and show how the framework extends the results to more features. Finally, we explore how the metric function and perceptual saliencies of phonological features may vary across languages. To this end, we compare results based on two English datasets and a new dataset that we have collected for Hebrew.