OpenRaiser/Intern-Atlas huggingface dataset:
Short Block-length Codes for Ultra-Reliable Low-Latency Communications
Venue: arXiv cs.IT 2018
Year: 2018

This paper reviews the state of the art channel coding techniques for ultra-reliable low latency communication (URLLC). The stringent requirements of URLLC services, such as ultra-high reliability and low latency, have made it the most challenging feature of the fifth generation (5G) mobile systems. The problem is even more challenging for the services beyond the 5G promise, such as tele-surgery and factory automation, which require latencies less than 1ms and failure rate as low as $10^{-9}$. The very low latency requirements of URLLC do not allow traditional approaches such as re-transmission to be used to increase the reliability. On the other hand, to guarantee the delay requirements, the block length needs to be small, so conventional channel codes, originally designed and optimised for moderate-to-long block-lengths, show notable deficiencies for short blocks. This paper provides an overview on channel coding techniques for short block lengths and compares them in terms of performance and complexity. Several important research directions are identified and discussed in more detail with several possible solutions.
Cuttlefish: A Lightweight Primitive for Adaptive Query Processing
Venue: arXiv cs.DB 2018
Year: 2018

Modern data processing applications execute increasingly sophisticated analysis that requires operations beyond traditional relational algebra. As a result, operators in query plans grow in diversity and complexity. Designing query optimizer rules and cost models to choose physical operators for all of these novel logical operators is impractical. To address this challenge, we develop Cuttlefish, a new primitive for adaptively processing online query plans that explores candidate physical operator instances during query execution and exploits the fastest ones using multi-armed bandit reinforcement learning techniques. We prototype Cuttlefish in Apache Spark and adaptively choose operators for image convolution, regular expression matching, and relational joins. Our experiments show Cuttlefish-based adaptive convolution and regular expression operators can reach 72-99% of the throughput of an all-knowing oracle that always selects the optimal algorithm, even when individual physical operators are up to 105x slower than the optimal. Additionally, Cuttlefish achieves join throughput improvements of up to 7.5x compared with Spark SQL's query optimizer.
The Trusted Server: A secure computational environment for privacy compliant evaluations on plain personal data
Venue: arXiv cs.CR 2018
Year: 2018

A growing framework of legal and ethical requirements limit scientific and commercial evalua-tion of personal data. Typically, pseudonymization, encryption, or methods of distributed com-puting try to protect individual privacy. However, computational infrastructures still depend on human system administrators. This introduces severe security risks and has strong impact on privacy: system administrators have unlimited access to the computers that they manage in-cluding encryption keys and pseudonymization-tables. Distributed computing and data obfuscation technologies reduce but do not eliminate the risk of privacy leakage by administrators. They produce higher implementation effort and possible data quality degradation. This paper proposes the Trusted Server as an alternative approach that provides a sealed and inaccessible computational environment in a cryptographically strict sense. During operation or by direct physical access to storage media, data stored and processed inside the Trusted Server can by no means be read, manipulated or leaked, other than by brute-force. Thus, secure and privacy-compliant data processing or evaluation of plain person-related data becomes possible even from multiple sources, which want their data kept mutually secret.
Interpreting Complex Regression Models
Venue: arXiv cs.LG 2018
Year: 2018

Interpretation of a machine learning induced models is critical for feature engineering, debugging, and, arguably, compliance. Yet, best of breed machine learning models tend to be very complex. This paper presents a method for model interpretation which has the main benefit that the simple interpretations it provides are always grounded in actual sets of learning examples. The method is validated on the task of interpreting a complex regression model in the context of both an academic problem -- predicting the year in which a song was recorded and an industrial one -- predicting mail user churn.
A Model of Free Will for Artificial Entities
Venue: arXiv cs.MA 2018
Year: 2018

The impression of free will is the feeling according to which our choices are neither imposed from our inside nor from outside. It is the sense we are the ultimate cause of our acts. In direct opposition with the universal determinism, the existence of free will continues to be discussed. In this paper, free will is linked to a decisional mechanism: an agent is provided with free will if having performed a predictable choice Cp, it can immediately perform another choice Cr in a random way. The intangible feeling of free will is replaced by a decision-making process including a predictable decision-making process immediately followed by an unpredictable decisional one.
Game of the Cursed Prince based on Android
Venue: arXiv cs.CY 2018
Year: 2018

Nowadays Games become an entertainment alternative for various circles, industry and game development business is also a profitable industry. In Indonesia the amount of game consumption is very high, especially the console game type RPG (Role Playing Game). The task of this research is developing game software using Unity 3D to create an Android-based RPG game app. The story is packed with RPG genres so the player can feel the main role of the storys imagination. The game to be built is a game titled The Cursed Prince. Users will get the sensation of royal adventure. Multiplayer game system, graphics in 3D game, The main character in this game is Prince, enemies in this game are wizards and monsters, Game is not limited time to complete. And the game can be saved, so it can be reopened. The game of The Cursed Prince can be part of Indonesian Industry Gaming development.
Improving Graph Convolutional Networks with Non-Parametric Activation Functions
Venue: arXiv cs.NE 2018
Year: 2018

Graph neural networks (GNNs) are a class of neural networks that allow to efficiently perform inference on data that is associated to a graph structure, such as, e.g., citation networks or knowledge graphs. While several variants of GNNs have been proposed, they only consider simple nonlinear activation functions in their layers, such as rectifiers or squashing functions. In this paper, we investigate the use of graph convolutional networks (GCNs) when combined with more complex activation functions, able to adapt from the training data. More specifically, we extend the recently proposed kernel activation function, a non-parametric model which can be implemented easily, can be regularized with standard $\ell_p$-norms techniques, and is smooth over its entire domain. Our experimental evaluation shows that the proposed architecture can significantly improve over its baseline, while similar improvements cannot be obtained by simply increasing the depth or size of the original GCN.
Multi-Goal Reinforcement Learning: Challenging Robotics Environments and Request for Research
Venue: arXiv cs.LG 2018
Year: 2018

The purpose of this technical report is two-fold. First of all, it introduces a suite of challenging continuous control tasks (integrated with OpenAI Gym) based on currently existing robotics hardware. The tasks include pushing, sliding and pick & place with a Fetch robotic arm as well as in-hand object manipulation with a Shadow Dexterous Hand. All tasks have sparse binary rewards and follow a Multi-Goal Reinforcement Learning (RL) framework in which an agent is told what to do using an additional input. The second part of the paper presents a set of concrete research ideas for improving RL algorithms, most of which are related to Multi-Goal RL and Hindsight Experience Replay.
On Strong NP-Completeness of Rational Problems
Venue: arXiv cs.DM 2018
Year: 2018

The computational complexity of the partition, 0-1 subset sum, unbounded subset sum, 0-1 knapsack and unbounded knapsack problems and their multiple variants were studied in numerous papers in the past where all the weights and profits were assumed to be integers. We re-examine here the computational complexity of all these problems in the setting where the weights and profits are allowed to be any rational numbers. We show that all of these problems in this setting become strongly NP-complete and, as a result, no pseudo-polynomial algorithm can exist for solving them unless P=NP. Despite this result we show that they all still admit a fully polynomial-time approximation scheme.
Retrieval-Augmented Convolutional Neural Networks for Improved Robustness against Adversarial Examples
Venue: arXiv cs.LG 2018
Year: 2018

We propose a retrieval-augmented convolutional network and propose to train it with local mixup, a novel variant of the recently proposed mixup algorithm. The proposed hybrid architecture combining a convolutional network and an off-the-shelf retrieval engine was designed to mitigate the adverse effect of off-manifold adversarial examples, while the proposed local mixup addresses on-manifold ones by explicitly encouraging the classifier to locally behave linearly on the data manifold. Our evaluation of the proposed approach against five readily-available adversarial attacks on three datasets--CIFAR-10, SVHN and ImageNet--demonstrate the improved robustness compared to the vanilla convolutional network.
Representations of Sparse Distributed Networks: A Locality-Sensitive Approach
Venue: arXiv cs.DS 2018
Year: 2018

In 1999, Brodal and Fagerberg (BF) gave an algorithm for maintaining a low outdegree orientation of a dynamic uniformly sparse graph. Specifically, for a dynamic graph on $n$-vertices, with arboricity bounded by $α$ at all times, the BF algorithm supports edge updates in $O(\log n)$ amortized update time, while keeping the maximum outdegree in the graph bounded by $O(α)$. Such an orientation provides a basic data structure for uniformly sparse graphs, which found applications to a plethora of dynamic graph algorithms. A significant weakness of the BF algorithm is the possible \emph{temporary} blowup of the maximum outdegree, following edge insertions. Although BF eventually reduces all outdegrees to $O(α)$, local memory usage at the vertices, which is an important quality measure in distributed systems, cannot be bounded. We show how to modify the BF algorithm to guarantee that the outdegrees of all vertices are bounded by $O(α)$ at all times, without hurting any of its other properties, and present an efficient distributed implementation of the modified algorithm. This provides the \emph{first} representation of distributed networks in which the local memory usage at all vertices is bounded by the arboricity (which is essentially the average degree of the densest subgraph) rather than the maximum degree. For settings where there are no local memory constraints, we take the temporary outdegree blowup to the extreme and allow a permanent outdegree blowup. This allows us to address the second significant weakness of the BF algorithm -- its inherently \emph{global} nature: An insertion of an edge $(u,v)$ may trigger changes in the orientations of edges that are far away from $u$ and $v$. We suggest an alternative \emph{local} scheme, which does not guarantee any outdegree bound on the vertices, yet is just as efficient as the BF scheme for various applications.
A Learning Approach for Low-Complexity Optimization of Energy Efficiency in Multi-Carrier Wireless Networks
Venue: arXiv cs.NI 2018
Year: 2018

This paper proposes computationally efficient algorithms to maximize the energy efficiency in multi-carrier wireless interference networks, by a suitable allocation of the system radio resources, namely the transmit powers and subcarrier assignment. The problem is formulated as the maximization of the system Global Energy-Efficiency subject to both maximum power and minimum rate constraints. This leads to a challenging non-convex fractional problem, which is tackled through an interplay of fractional programming, learning, and game theory. The proposed algorithmic framework is provably convergent and has a complexity linear in both the number of users and subcarriers, whereas other available solutions can only guarantee a polynomial complexity in the number of users and subcarriers. Numerical results show that the proposed method performs similarly as other, more complex, algorithms.
On tradeoffs between width- and fill-like graph parameters
Venue: arXiv cs.DM 2018
Year: 2018

In this work we consider two two-criteria optimization problems: given an input graph, the goal is to find its interval (or chordal) supergraph that minimizes the number of edges and its clique number simultaneously. For the interval supergraph, the problem can be restated as simultaneous minimization of the pathwidth $pw(G)$ and the profile $p(G)$ of the input graph $G$. We prove that for an arbitrary graph $G$ and an integer $t\in\{1,\ldots,pw(G)+1\}$, there exists an interval supergraph $G'$ of $G$ such that for its clique number it holds $ω(G')\leq(1+\frac{2}{t})(pw(G)+1)$ and the number of its edges is bounded by $|E(G')|\leq(t+2)p(G)$. In other words, the pathwidth and the profile of a graph can be simultaneously minimized within the factors of $1+\frac{2}{t}$ (plus a small constant) and $t+2$, respectively. Note that for a fixed $t$, both upper bounds provide constant factor approximations. On the negative side, we show an example that proves that, for some graphs, there is no solution in which both parameters are optimal. In case of finding a chordal supergraph, the two corresponding graph parameters that reflect its clique size and number of edges are the treewidth and fill-in. We obtain that the treewidth and the fill-in problems are also `orthogonal' in the sense that for some graphs, a solution that minimizes one of those parameters cannot minimize the other. As a motivating example, we recall graph searching games which illustrates a need of simultaneous minimization of these pairs of graph parameters.
Event-Triggered Controller Synthesis for Dynamical Systems with Temporal Logic Constraints
Venue: arXiv cs.RO 2018
Year: 2018

In this work, we propose an event-triggered con- trol framework for dynamical systems with temporal logical constraints. Event-triggered control methodologies have proven to be very efficient in reducing sensing, communication and computation costs. When a continuous feedback control is re- placed with an event-triggered strategy, the corresponding state trajectories also differ. In a system with logical constraints, such small deviation in the trajectory might lead to unsatisfiability of the logical constraints. In this work, we develop an approach where we ensure that the event-triggered state trajectory is confined within an tube of the ideal trajectory associated with the continuous state feedback. At the same time, we will ensure satisfiability of the logical constraints as well. Furthermore, we show that the proposed method works for delayed systems as long as the delay is bounded by a certain quantity.
Multi-Observation Regression
Venue: arXiv cs.LG 2018
Year: 2018

Recent work introduced loss functions which measure the error of a prediction based on multiple simultaneous observations or outcomes. In this paper, we explore the theoretical and practical questions that arise when using such multi-observation losses for regression on data sets of $(x,y)$ pairs. When a loss depends on only one observation, the average empirical loss decomposes by applying the loss to each pair, but for the multi-observation case, empirical loss is not even well-defined, and the possibility of statistical guarantees is unclear without several $(x,y)$ pairs with exactly the same $x$ value. We propose four algorithms formalizing the concept of empirical risk minimization for this problem, two of which have statistical guarantees in settings allowing both slow and fast convergence rates, but which are out-performed empirically by the other two. Empirical results demonstrate practicality of these algorithms in low-dimensional settings, while lower bounds demonstrate intrinsic difficulty in higher dimensions. Finally, we demonstrate the potential benefit of the algorithms over natural baselines that use traditional single-observation losses via both lower bounds and simulations.
On Euler Emulation of Observer-Based Stabilizers for Nonlinear Time-Delay Systems
Venue: arXiv cs.SY 2018
Year: 2018

In this paper, we deal with the problem of the stabilization in the sample-and-hold sense, by emulation of continuous-time, observer-based, global stabilizers. Fully nonlinear time-delay systems are studied. Sufficient conditions are provided such that the Euler approximation of continuous-time, observer-based, global stabilizers, for nonlinear time-delay systems, yields stabilization in the sample-and-hold sense. Submitted (in an extended version) to Automatica.
Preservation of Indigenous Culture among Indigenous Migrants through Social Media: the Igorot Peoples
Venue: arXiv cs.CY 2018
Year: 2018

The value and relevance of indigenous knowledge towards sustainability of human societies drives for its preservation. This work explored the use of Facebook groups to promote indigenous knowledge among Igorot peoples in the diaspora. The virtual communities help intensify the connection of Igorot migrants to their traditional culture despite the challenges of assimilation to a different society. A survey of posts on 20 Facebook groups identified and classified the indigenous cultural elements conveyed through social media. A subsequent survey of 56 Igorot migrants revealed that popular social media has a significant role in the exchange, revitalization, practice, and learning of indigenous culture; inciting an effective medium to leverage preservation strategies.
Convolutional Neural Network Achieves Human-level Accuracy in Music Genre Classification
Venue: arXiv cs.SD 2018
Year: 2018

Music genre classification is one example of content-based analysis of music signals. Traditionally, human-engineered features were used to automatize this task and 61% accuracy has been achieved in the 10-genre classification. However, it's still below the 70% accuracy that humans could achieve in the same task. Here, we propose a new method that combines knowledge of human perception study in music genre classification and the neurophysiology of the auditory system. The method works by training a simple convolutional neural network (CNN) to classify a short segment of the music signal. Then, the genre of a music is determined by splitting it into short segments and then combining CNN's predictions from all short segments. After training, this method achieves human-level (70%) accuracy and the filters learned in the CNN resemble the spectrotemporal receptive field (STRF) in the auditory system.
Surrogate Model Assisted Cooperative Coevolution for Large Scale Optimization
Venue: arXiv cs.NE 2018
Year: 2018

It has been shown that cooperative coevolution (CC) can effectively deal with large scale optimization problems (LSOPs) through a divide-and-conquer strategy. However, its performance is severely restricted by the current context-vector-based sub-solution evaluation method since this method needs to access the original high dimensional simulation model when evaluating each sub-solution and thus requires many computation resources. To alleviate this issue, this study proposes a novel surrogate model assisted cooperative coevolution (SACC) framework. SACC constructs a surrogate model for each sub-problem obtained via decomposition and employs it to evaluate corresponding sub-solutions. The original simulation model is only adopted to reevaluate some good sub-solutions selected by surrogate models, and these real evaluated sub-solutions will be in turn employed to update surrogate models. By this means, the computation cost could be greatly reduced without significantly sacrificing evaluation quality. To show the efficiency of SACC, this study uses radial basis function (RBF) and success-history based adaptive differential evolution (SHADE) as surrogate model and optimizer, respectively. RBF and SHADE have been proved to be effective on small and medium scale problems. This study first scales them up to LSOPs of 1000 dimensions under the SACC framework, where they are tailored to a certain extent for adapting to the characteristics of LSOP and SACC. Empirical studies on IEEE CEC 2010 benchmark functions demonstrate that SACC significantly enhances the evaluation efficiency on sub-solutions, and even with much fewer computation resource, the resultant RBF-SHADE-SACC algorithm is able to find much better solutions than traditional CC algorithms.
#DebateNight: The Role and Influence of Socialbots on Twitter During the 1st 2016 U.S. Presidential Debate
Venue: arXiv cs.SI 2018
Year: 2018

Serious concerns have been raised about the role of 'socialbots' in manipulating public opinion and influencing the outcome of elections by retweeting partisan content to increase its reach. Here we analyze the role and influence of socialbots on Twitter by determining how they contribute to retweet diffusions. We collect a large dataset of tweets during the 1st U.S. Presidential Debate in 2016 (#DebateNight) and we analyze its 1.5 million users from three perspectives: user influence, political behavior (partisanship and engagement) and botness. First, we define a measure of user influence based on the user's active contributions to information diffusions, i.e. their tweets and retweets. Given that Twitter does not expose the retweet structure - it associates all retweets with the original tweet - we model the latent diffusion structure using only tweet time and user features, and we implement a scalable novel approach to estimate influence over all possible unfoldings. Next, we use partisan hashtag analysis to quantify user political polarization and engagement. Finally, we use the BotOrNot API to measure user botness (the likelihood of being a bot). We build a two-dimensional "polarization map" that allows for a nuanced analysis of the interplay between botness, partisanship and influence. We find that not only social bots are more active on Twitter - starting more retweet cascades and retweeting more -- but they are 2.5 times more influential than humans, and more politically engaged. Moreover, pro-Republican bots are both more influential and more politically engaged than their pro-Democrat counterparts. However we caution against blanket statements that software designed to appear human dominates political debates. We find that many highly influential Twitter users are in fact pro-Democrat and that most pro-Republican users are mid-influential and likely to be human (low botness).