OpenRaiser/Intern-Atlas huggingface dataset:
Balance of thrones: a network study on Game of Thrones
Venue: arXiv cs.SI 2018
Year: 2018

TV dramas constitute an important part of the entertainment industry, with popular shows attracting millions of viewers and resulting in significant revenues. Finding a way to explore formally the social dynamics underpinning these show has therefore important implications, as it would allow us not only to understand which features are most likely to be associated with the popularity of a show, but also to explore the extent to which such fictional world have social interactions comparable with the real world. To begin tackling this question, we employed network analysis to systematically and quantitatively explore how the interactions between noble houses of the fantasy drama TV series Game of Thrones change as the show progresses. Our analysis discloses the invisible threads that connected different houses and shows how tension across the houses, as measure via structural balance, changes over time. To boost the impact of our analysis, we further extended our analysis to explore how different network features correlate with viewers engagement and appreciation of different episodes. This allowed us to derive an hierarchy of features that are associated with the audience response. All in all, our work show how network models may be able to capture social relations present in complex artificial worlds, thus providing a way to qualitatively model social interactions among fictional characters, hence allowing a minimal formal description of the unfolding of stories that can be instrumental in managing complex narratives.
Reverse Curriculum Generation for Reinforcement Learning
Venue: arXiv cs.AI 2018
Year: 2018

Many relevant tasks require an agent to reach a certain state, or to manipulate objects into a desired configuration. For example, we might want a robot to align and assemble a gear onto an axle or insert and turn a key in a lock. These goal-oriented tasks present a considerable challenge for reinforcement learning, since their natural reward function is sparse and prohibitive amounts of exploration are required to reach the goal and receive some learning signal. Past approaches tackle these problems by exploiting expert demonstrations or by manually designing a task-specific reward shaping function to guide the learning agent. Instead, we propose a method to learn these tasks without requiring any prior knowledge other than obtaining a single state in which the task is achieved. The robot is trained in reverse, gradually learning to reach the goal from a set of start states increasingly far from the goal. Our method automatically generates a curriculum of start states that adapts to the agent's performance, leading to efficient training on goal-oriented tasks. We demonstrate our approach on difficult simulated navigation and fine-grained manipulation problems, not solvable by state-of-the-art reinforcement learning methods.
VSE++: Improving Visual-Semantic Embeddings with Hard Negatives
Venue: arXiv cs.LG 2018
Year: 2018

We present a new technique for learning visual-semantic embeddings for cross-modal retrieval. Inspired by hard negative mining, the use of hard negatives in structured prediction, and ranking loss functions, we introduce a simple change to common loss functions used for multi-modal embeddings. That, combined with fine-tuning and use of augmented data, yields significant gains in retrieval performance. We showcase our approach, VSE++, on MS-COCO and Flickr30K datasets, using ablation studies and comparisons with existing methods. On MS-COCO our approach outperforms state-of-the-art methods by 8.8% in caption retrieval and 11.3% in image retrieval (at R@1).
Submodular Minimization Under Congruency Constraints
Venue: arXiv cs.DS 2018
Year: 2018

Submodular function minimization (SFM) is a fundamental and efficiently solvable problem class in combinatorial optimization with a multitude of applications in various fields. Surprisingly, there is only very little known about constraint types under which SFM remains efficiently solvable. The arguably most relevant non-trivial constraint class for which polynomial SFM algorithms are known are parity constraints, i.e., optimizing only over sets of odd (or even) cardinality. Parity constraints capture classical combinatorial optimization problems like the odd-cut problem, and they are a key tool in a recent technique to efficiently solve integer programs with a constraint matrix whose subdeterminants are bounded by two in absolute value. We show that efficient SFM is possible even for a significantly larger class than parity constraints, by introducing a new approach that combines techniques from Combinatorial Optimization, Combinatorics, and Number Theory. In particular, we can show that efficient SFM is possible over all sets (of any given lattice) of cardinality r mod m, as long as m is a constant prime power. This covers generalizations of the odd-cut problem with open complexity status, and with relevance in the context of integer programming with higher subdeterminants. To obtain our results, we establish a connection between the correctness of a natural algorithm, and the inexistence of set systems with specific combinatorial properties. We introduce a general technique to disprove the existence of such set systems, which allows for obtaining extensions of our results beyond the above-mentioned setting. These extensions settle two open questions raised by Geelen and Kapadia [Combinatorica, 2017] in the context of computing the girth and cogirth of certain types of binary matroids.
Document Listing on Repetitive Collections with Guaranteed Performance
Venue: arXiv cs.DS 2018
Year: 2018

We consider document listing on string collections, that is, finding in which strings a given pattern appears. In particular, we focus on repetitive collections: a collection of size $N$ over alphabet $[1,σ]$ is composed of $D$ copies of a string of size $n$, and $s$ edits are applied on ranges of copies. We introduce the first document listing index with size $\tilde{O}(n+s)$, precisely $O((n\logσ+s\log^2 N)\log D)$ bits, and with useful worst-case time guarantees: Given a pattern of length $m$, the index reports the $\ndoc>0$ strings where it appears in time $O(m\log^{1+ε} N \cdot \ndoc)$, for any constant $ε>0$ (and tells in time $O(m\log N)$ if $\ndoc=0$). Our technique is to augment a range data structure that is commonly used on grammar-based indexes, so that instead of retrieving all the pattern occurrences, it computes useful summaries on them. We show that the idea has independent interest: we introduce the first grammar-based index that, on a text $T[1,N]$ with a grammar of size $r$, uses $O(r\log N)$ bits and counts the number of occurrences of a pattern $P[1,m]$ in time $O(m^2 + m\log^{2+ε} r)$, for any constant $ε>0$. We also give the first index using $O(z\log(N/z)\log N)$ bits, where $T$ is parsed by Lempel-Ziv into $z$ phrases, counting occurrences in time $O(m\log^{2+ε} N)$.
An Explicit Construction of Optimal Dominating Sets in Grid
Venue: arXiv cs.DM 2018
Year: 2018

A dominating set in a graph $G$ is a subset of vertices $D$ such that every vertex in $V\setminus D$ is a neighbor of some vertex of $D$. The domination number of $G$ is the minimum size of a dominating set of $G$ and it is denoted by $γ(G)$. Also, a subset $D$ of a graph $G$ is a $[ 1 , 2 ] $-set if, each vertex $v \in V \setminus D$ is adjacent to either one or two vertices in $D$ and the minimum cardinality of $[ 1 , 2 ] $-dominating set of $G$, is denoted by $γ_{[1,2]}(G)$. Chang's conjecture says that for every $16 \leq m \leq n$, $γ(G_{m,n})= \left \lfloor\frac{(n+2)(m+2)}{5}\right \rfloor-4$ and this conjecture has been proven by Goncalves et al. This paper presents an explicit constructing method to find an optimal dominating set for grid graph $G_{m,n}$ where $m,n\geq 16$ in $O(\text{size of answer})$. In addition, we will show that $γ(G_{m,n})=γ_{[1,2]}(G_{m,n})$ where $m,n\geq 16$ holds in response to an open question posed by Chellali et al.
Scalable and robust set similarity join
Venue: arXiv cs.DB 2018
Year: 2018

Set similarity join is a fundamental and well-studied database operator. It is usually studied in the exact setting where the goal is to compute all pairs of sets that exceed a given similarity threshold (measured e.g. as Jaccard similarity). But set similarity join is often used in settings where 100% recall may not be important --- indeed, where the exact set similarity join is itself only an approximation of the desired result set. We present a new randomized algorithm for set similarity join that can achieve any desired recall up to 100%, and show theoretically and empirically that it significantly improves on existing methods. The present state-of-the-art exact methods are based on prefix-filtering, the performance of which depends on the data set having many rare tokens. Our method is robust against the absence of such structure in the data. At 90% recall our algorithm is often more than an order of magnitude faster than state-of-the-art exact methods, depending on how well a data set lends itself to prefix filtering. Our experiments on benchmark data sets also show that the method is several times faster than comparable approximate methods. Our algorithm makes use of recent theoretical advances in high-dimensional sketching and indexing that we believe to be of wider relevance to the data engineering community.
Sensitive and Nonlinear Far Field RF Energy Harvesting in Wireless Communications
Venue: arXiv cs.IT 2018
Year: 2018

This work studies both limited sensitivity and nonlinearity of far field RF energy harvesting observed in reality and quantifies their effect, attempting to fill a major hole in the simultaneous wireless information and power transfer (SWIPT) literature. RF harvested power is modeled as an arbitrary nonlinear, continuous, and non-decreasing function of received power, taking into account limited sensitivity and saturation effects. RF harvester's sensitivity may be several dBs worse than communications receiver's sensitivity, potentially rendering RF information signals useless for energy harvesting purposes. Given finite number of datapoint pairs of harvested (output) power and corresponding input power, a piecewise linear approximation is applied and the statistics of the harvested power are offered, as a function of the wireless channel fading statistics. Limited number of datapoints are needed and accuracy analysis is also provided. Case studies include duty-cycled (non-continuous), as well as continuous SWIPT, comparing with industry-level, RF harvesting. The proposed approximation, even though simple, offers accurate performance for all studied metrics. On the other hand, linear models or nonlinear-unlimited sensitivity harvesting models deviate from reality, especially in the low input power regime. The proposed methodology can be utilized in current and future SWIPT research.
Descriptor System Tools (DSTOOLS) User's Guide
Venue: arXiv cs.SY 2018
Year: 2018

The Descriptor System Tools (DSTOOLS) is a collection of MATLAB functions for the operation on and manipulation of rational transfer function matrices via their descriptor system realizations. The DSTOOLS collection relies on the Control System Toolbox and several mex-functions based on the Systems and Control Library SLICOT. Many of the implemented functions are based on the computational procedures described in Chapter 10 of the book: "A. Varga, Solving Fault Diagnosis Problems - Linear Synthesis Techniques, Springer, 2017". This document is the User's Guide for the version V0.71 of DSTOOLS. First, we present the mathematical background on rational matrices and descriptor systems. Then, we give in-depth information on the command syntax of the main computational functions. Several examples illustrate the use of the main functions of DSTOOLS.
The spread of low-credibility content by social bots
Venue: arXiv cs.SI 2018
Year: 2018

The massive spread of digital misinformation has been identified as a major global risk and has been alleged to influence elections and threaten democracies. Communication, cognitive, social, and computer scientists are engaged in efforts to study the complex causes for the viral diffusion of misinformation online and to develop solutions, while search and social media platforms are beginning to deploy countermeasures. With few exceptions, these efforts have been mainly informed by anecdotal evidence rather than systematic data. Here we analyze 14 million messages spreading 400 thousand articles on Twitter during and following the 2016 U.S. presidential campaign and election. We find evidence that social bots played a disproportionate role in amplifying low-credibility content. Accounts that actively spread articles from low-credibility sources are significantly more likely to be bots. Automated accounts are particularly active in amplifying content in the very early spreading moments, before an article goes viral. Bots also target users with many followers through replies and mentions. Humans are vulnerable to this manipulation, retweeting bots who post links to low-credibility content. Successful low-credibility sources are heavily supported by social bots. These results suggest that curbing social bots may be an effective strategy for mitigating the spread of online misinformation.
The Quantum Theil Index: Characterizing Graph Centralization using von Neumann Entropy
Venue: arXiv cs.IT 2018
Year: 2018

We show that the von Neumann entropy (from herein referred to as the von Neumann index) of a graph's trace normalized combinatorial Laplacian provides structural information about the level of centralization across a graph. This is done by considering the Theil index, which is an established statistical measure used to determine levels of inequality across a system of `agents', e.g., income levels across a population. Here, we establish a Theil index for graphs, which provides us with a macroscopic measure of graph centralization. Concretely, we show that the von Neumann index can be used to bound the graph's Theil index, and thus we provide a direct characterization of graph centralization via the von Neumann index. Because of the algebraic similarities between the bound and the Theil index, we call the bound the von Neumann Theil index. %From an information theoretic perspective, the von Neumann Theil index describes the mutual information between the quantum state corresponding to a graph and the maximally mixed state (which corresponds to the complete graph). We elucidate our ideas by providing examples and a discussion of different $n=7$ vertex graphs. We also discuss how the von Neumann Theil index provides a more comprehensive measure of centralization when compared to traditional centralization measures, and when compared to the graph's classical Theil index. This is because it more accurately accounts for macro-structural changes that occur from micro-structural changes in the graph (e.g., the removal of a vertex). Finally, we provide future direction, showing that the von Neumann Theil index can be generalized by considering the Rényi entropy. We then show that this generalization can be used to bound the negative logarithm of the graph's Jain fairness index.
A Simple Exponential Family Framework for Zero-Shot Learning
Venue: arXiv cs.LG 2018
Year: 2018

We present a simple generative framework for learning to predict previously unseen classes, based on estimating class-attribute-gated class-conditional distributions. We model each class-conditional distribution as an exponential family distribution and the parameters of the distribution of each seen/unseen class are defined as functions of the respective observed class attributes. These functions can be learned using only the seen class data and can be used to predict the parameters of the class-conditional distribution of each unseen class. Unlike most existing methods for zero-shot learning that represent classes as fixed embeddings in some vector space, our generative model naturally represents each class as a probability distribution. It is simple to implement and also allows leveraging additional unlabeled data from unseen classes to improve the estimates of their class-conditional distributions using transductive/semi-supervised learning. Moreover, it extends seamlessly to few-shot learning by easily updating these distributions when provided with a small number of additional labelled examples from unseen classes. Through a comprehensive set of experiments on several benchmark data sets, we demonstrate the efficacy of our framework.
Efficient Yet Deep Convolutional Neural Networks for Semantic Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

Semantic Segmentation using deep convolutional neural network pose more complex challenge for any GPU intensive task. As it has to compute million of parameters, it results to huge memory consumption. Moreover, extracting finer features and conducting supervised training tends to increase the complexity. With the introduction of Fully Convolutional Neural Network, which uses finer strides and utilizes deconvolutional layers for upsampling, it has been a go to for any image segmentation task. In this paper, we propose two segmentation architecture which not only needs one-third the parameters to compute but also gives better accuracy than the similar architectures. The model weights were transferred from the popular neural net like VGG19 and VGG16 which were trained on Imagenet classification data-set. Then we transform all the fully connected layers to convolutional layers and use dilated convolution for decreasing the parameters. Lastly, we add finer strides and attach four skip architectures which are element-wise summed with the deconvolutional layers in steps. We train and test on different sparse and fine data-sets like Pascal VOC2012, Pascal-Context and NYUDv2 and show how better our model performs in this tasks. On the other hand our model has a faster inference time and consumes less memory for training and testing on NVIDIA Pascal GPUs, making it more efficient and less memory consuming architecture for pixel-wise segmentation.
Recursive simplex stars
Venue: arXiv cs.CG 2018
Year: 2018

This paper proposes a new method which builds a simplex based approximation of a $d-1$-dimensional manifold $M$ separating a $d$-dimensional compact set into two parts, and an efficient algorithm classifying points according to this approximation. In a first variant, the approximation is made of simplices that are defined in the cubes of a regular grid covering the compact set, from boundary points that approximate the intersection between $M$ and the edges of the cubes. All the simplices defined in a cube share the barycentre of the boundary points located in the cube and include simplices similarly defined in cube facets, and so on recursively. In a second variant, the Kuhn triangulation is used to break the cubes into simplices and the approximation is defined in these simplices from the boundary points computed on their edges, with the same principle. Both the approximation in cubes and in simplices define a separating surface on the whole grid and classifying a point on one side or the other of this surface requires only a small number (at most $d$) of simple tests. Under some conditions on the definition of the boundary points and on the reach of $M$, for both variants the Hausdorff distance between $M$ and its approximation decreases like $\mathcal{O}(d n_G^{-2})$, where $n_G$ is the number of points on each axis of the grid. The approximation in cubes requires computing less boundary points than the approximation in simplices but the latter is always a manifold and is more accurate for a given value of $n_G$. The paper reports tests of the method when varying $n_G$ and the dimensionality of the space (up to 9).
Two Types of Social Grooming Methods depending on the Trade-off between the Number and Strength of Social Relationships
Venue: arXiv cs.SI 2018
Year: 2018

Humans use various social bonding methods known as social grooming, e.g. face to face communication, greetings, phone, and social networking sites (SNS). SNS have drastically decreased time and distance constraints of social grooming. In this paper, I show that two types of social grooming (elaborate social grooming and lightweight social grooming) were discovered in a model constructed by thirteen communication data-sets including face to face, SNS, and Chacma baboons. The separation of social grooming methods is caused by a difference in the trade-off between the number and strength of social relationships. The trade-off of elaborate social grooming is weaker than the trade-off of lightweight social grooming. On the other hand, the time and effort of elaborate methods are higher than lightweight methods. Additionally, my model connects social grooming behaviour and social relationship forms with these trade-offs. By analyzing the model, I show that individuals tend to use elaborate social grooming to reinforce a few close relationships (e.g. face to face and Chacma baboons). In contrast, people tend to use lightweight social grooming to maintain many weak relationships (e.g. SNS). Humans with lightweight methods who live in significantly complex societies use various social grooming to effectively construct social relationships.
Inference from Randomized Transmissions by Many Backscatter Sensors
Venue: arXiv cs.IT 2018
Year: 2018

Attaining the vision of Smart Cities requires the deployment of an enormous number of sensors for monitoring various conditions of the environment. Backscatter-sensors have emerged to be a promising solution due to the uninterruptible energy supply and relative simple hardwares. On the other hand, backscatter-sensors with limited signal-processing capabilities are unable to support conventional algorithms for multiple-access and channel-training. Thus, the key challenge in designing backscatter-sensor networks is to enable readers to accurately detect sensing-values given simple ALOHA random access, primitive transmission schemes, and no knowledge of channel-states. We tackle this challenge by proposing the novel framework of backscatter sensing featuring random-encoding at sensors and statistical-inference at readers. Specifically, assuming the on/off keying for backscatter transmissions, the practical random-encoding scheme causes the on/off transmission of a sensor to follow a distribution parameterized by the sensing values. Facilitated by the scheme, statistical-inference algorithms are designed to enable a reader to infer sensing-values from randomized transmissions by multiple sensors. The specific design procedure involves the construction of Bayesian networks, namely deriving conditional distributions for relating unknown parameters and variables to signals observed by the reader. Then based on the Bayesian networks and the well-known expectation-maximization principle, inference algorithms are derived to recover sensing-values.
Entropy-Based $Sim(3)$ Calibration of 2D Lidars to Egomotion Sensors
Venue: arXiv cs.RO 2018
Year: 2018

This paper explores the use of an entropy-based technique for point cloud reconstruction with the goal of calibrating a lidar to a sensor capable of providing egomotion information. We extend recent work in this area to the problem of recovering the $Sim(3)$ transformation between a 2D lidar and a rigidly attached monocular camera, where the scale of the camera trajectory is not known a priori. We demonstrate the robustness of our approach on realistic simulations in multiple environments, as well as on data collected from a hand-held sensor rig. Given a non-degenerate trajectory and a sufficient number of lidar measurements, our calibration procedure achieves millimetre-scale and sub-degree accuracy. Moreover, our method relaxes the need for specific scene geometry, fiducial markers, or overlapping sensor fields of view, which had previously limited similar techniques.