OpenRaiser/Intern-Atlas huggingface dataset:
Federated Control with Hierarchical Multi-Agent Deep Reinforcement Learning
Venue: arXiv cs.AI 2017
Year: 2017

We present a framework combining hierarchical and multi-agent deep reinforcement learning approaches to solve coordination problems among a multitude of agents using a semi-decentralized model. The framework extends the multi-agent learning setup by introducing a meta-controller that guides the communication between agent pairs, enabling agents to focus on communicating with only one other agent at any step. This hierarchical decomposition of the task allows for efficient exploration to learn policies that identify globally optimal solutions even as the number of collaborating agents increases. We show promising initial experimental results on a simulated distributed scheduling problem.
A Bidirectional Adaptive Bandwidth Mean Shift Strategy for Clustering
Venue: arXiv cs.CV 2017
Year: 2017

The bandwidth of a kernel function is a crucial parameter in the mean shift algorithm. This paper proposes a novel adaptive bandwidth strategy which contains three main contributions. (1) The differences among different adaptive bandwidth are analyzed. (2) A new mean shift vector based on bidirectional adaptive bandwidth is defined, which combines the advantages of different adaptive bandwidth strategies. (3) A bidirectional adaptive bandwidth mean shift (BAMS) strategy is proposed to improve the ability to escape from the local maximum density. Compared with contemporary adaptive bandwidth mean shift strategies, experiments demonstrate the effectiveness of the proposed strategy.
SFCN-OPI: Detection and Fine-grained Classification of Nuclei Using Sibling FCN with Objectness Prior Interaction
Venue: arXiv cs.CV 2017
Year: 2017

Cell nuclei detection and fine-grained classification have been fundamental yet challenging problems in histopathology image analysis. Due to the nuclei tiny size, significant inter-/intra-class variances, as well as the inferior image quality, previous automated methods would easily suffer from limited accuracy and robustness. In the meanwhile, existing approaches usually deal with these two tasks independently, which would neglect the close relatedness of them. In this paper, we present a novel method of sibling fully convolutional network with prior objectness interaction (called SFCN-OPI) to tackle the two tasks simultaneously and interactively using a unified end-to-end framework. Specifically, the sibling FCN branches share features in earlier layers while holding respective higher layers for specific tasks. More importantly, the detection branch outputs the objectness prior which dynamically interacts with the fine-grained classification sibling branch during the training and testing processes. With this mechanism, the fine-grained classification successfully focuses on regions with high confidence of nuclei existence and outputs the conditional probability, which in turn benefits the detection through back propagation. Extensive experiments on colon cancer histology images have validated the effectiveness of our proposed SFCN-OPI and our method has outperformed the state-of-the-art methods by a large margin.
Tracking the Diffusion of Named Entities
Venue: arXiv cs.CL 2017
Year: 2017

Existing studies of how information diffuses across social networks have thus far concentrated on analysing and recovering the spread of deterministic innovations such as URLs, hashtags, and group membership. However investigating how mentions of real-world entities appear and spread has yet to be explored, largely due to the computationally intractable nature of performing large-scale entity extraction. In this paper we present, to the best of our knowledge, one of the first pieces of work to closely examine the diffusion of named entities on social media, using Reddit as our case study platform. We first investigate how named entities can be accurately recognised and extracted from discussion posts. We then use these extracted entities to study the patterns of entity cascades and how the probability of a user adopting an entity (i.e. mentioning it) is associated with exposures to the entity. We put these pieces together by presenting a parallelised diffusion model that can forecast the probability of entity adoption, finding that the influence of adoption between users can be characterised by their prior interactions -- as opposed to whether the users propagated entity-adoptions beforehand. Our findings have important implications for researchers studying influence and language, and for community analysts who wish to understand entity-level influence dynamics.
Finding People's Professions and Nationalities Using Distant Supervision - The FMI@SU "goosefoot" team at the WSDM Cup 2017 Triple Scoring Task
Venue: arXiv cs.IR 2017
Year: 2017

We describe the system that our FMI@SU student's team built for participating in the Triple Scoring task at the WSDM Cup 2017. Given a triple from a "type-like" relation, profession or nationality, the goal is to produce a score, on a scale from 0 to 7, that measures the relevance of the statement expressed by the triple: e.g., how well does the profession of an Actor fit for Quentin Tarantino? We propose a distant supervision approach using information crawled from Wikipedia, DeletionPedia, and DBpedia, together with task-specific word embeddings, TF-IDF weights, and role occurrence order, which we combine in a linear regression model. The official evaluation ranked our submission 1st on Kendall's Tau, 7th on Average score difference, and 9th on Accuracy, out of 21 participating teams.
Notes on complexity of packing coloring
Venue: arXiv cs.CC 2017
Year: 2017

A packing $k$-coloring for some integer $k$ of a graph $G=(V,E)$ is a mapping $φ:V\to\{1,\ldots,k\}$ such that any two vertices $u, v$ of color $φ(u)=φ(v)$ are in distance at least $φ(u)+1$. This concept is motivated by frequency assignment problems. The \emph{packing chromatic number} of $G$ is the smallest $k$ such that there exists a packing $k$-coloring of $G$. Fiala and Golovach showed that determining the packing chromatic number for chordal graphs is \NP-complete for diameter exactly 5. While the problem is easy to solve for diameter 2, we show \NP-completeness for any diameter at least 3. Our reduction also shows that the packing chromatic number is hard to approximate within $n^{{1/2}-\varepsilon}$ for any $\varepsilon > 0$. In addition, we design an \FPT algorithm for interval graphs of bounded diameter. This leads us to exploring the problem of finding a partial coloring that maximizes the number of colored vertices.
Limits for Rumor Spreading in stochastic populations
Venue: arXiv cs.MA 2017
Year: 2017

Biological systems can share and collectively process information to yield emergent effects, despite inherent noise in communication. While man-made systems often employ intricate structural solutions to overcome noise, the structure of many biological systems is more amorphous. It is not well understood how communication noise may affect the computational repertoire of such groups. To approach this question we consider the basic collective task of rumor spreading, in which information from few knowledgeable sources must reliably flow into the rest of the population. In order to study the effect of communication noise on the ability of groups that lack stable structures to efficiently solve this task, we consider a noisy version of the uniform PULL model. We prove a lower bound which implies that, in the presence of even moderate levels of noise that affect all facets of the communication, no scheme can significantly outperform the trivial one in which agents have to wait until directly interacting with the sources. Our results thus show an exponential separation between the uniform PUSH and PULL communication models in the presence of noise. Such separation may be interpreted as suggesting that, in order to achieve efficient rumor spreading, a system must exhibit either some degree of structural stability or, alternatively, some facet of the communication which is immune to noise. We corroborate our theoretical findings with a new analysis of experimental data regarding recruitment in Cataglyphis niger desert ants.
The Heisenberg Defense: Proactively Defending SGX Enclaves against Page-Table-Based Side-Channel Attacks
Venue: arXiv cs.CR 2017
Year: 2017

Protected-module architectures (PMAs) have been proposed to provide strong isolation guarantees, even on top of a compromised system. Unfortunately, Intel SGX -- the only publicly available high-end PMA -- has been shown to only provide limited isolation. An attacker controlling the untrusted page tables, can learn enclave secrets by observing its page access patterns. Fortifying existing protected-module architectures in a real-world setting against side-channel attacks is an extremely difficult task as system software (hypervisor, operating system, ...) needs to remain in full control over the underlying hardware. Most state-of-the-art solutions propose a reactive defense that monitors for signs of an attack. Such approaches unfortunately cannot detect the most novel attacks, suffer from false-positives, and place an extraordinary heavy burden on enclave-developers when an attack is detected. We present Heisenberg, a proactive defense that provides complete protection against page table based side channels. We guarantee that any attack will either be prevented or detected automatically before {\em any} sensitive information leaks. Consequently, Heisenberg can always securely resume enclave execution -- even when the attacker is still present in the system. We present two implementations. Heisenberg-HW relies on very limited hardware features to defend against page-table-based attacks. We use the x86/SGX platform as an example, but the same approach can be applied when protected-module architectures are ported to different platforms as well. Heisenberg-SW avoids these hardware modifications and can readily be applied. Unfortunately, it's reliance on Intel Transactional Synchronization Extensions (TSX) may lead to significant performance overhead under real-life conditions.
DancingLines: An Analytical Scheme to Depict Cross-Platform Event Popularity
Venue: arXiv cs.IR 2017
Year: 2017

Nowadays, events usually burst and are propagated online through multiple modern media like social networks and search engines. There exists various research discussing the event dissemination trends on individual medium, while few studies focus on event popularity analysis from a cross-platform perspective. Challenges come from the vast diversity of events and media, limited access to aligned datasets across different media and a great deal of noise in the datasets. In this paper, we design DancingLines, an innovative scheme that captures and quantitatively analyzes event popularity between pairwise text media. It contains two models: TF-SW, a semantic-aware popularity quantification model, based on an integrated weight coefficient leveraging Word2Vec and TextRank; and wDTW-CD, a pairwise event popularity time series alignment model matching different event phases adapted from Dynamic Time Warping. We also propose three metrics to interpret event popularity trends between pairwise social platforms. Experimental results on eighteen real-world event datasets from an influential social network and a popular search engine validate the effectiveness and applicability of our scheme. DancingLines is demonstrated to possess broad application potentials for discovering the knowledge of various aspects related to events and different media.
Find the Conversation Killers: a Predictive Study of Thread-ending Posts
Venue: arXiv cs.CL 2017
Year: 2017

How to improve the quality of conversations in online communities has attracted considerable attention recently. Having engaged, urbane, and reactive online conversations has a critical effect on the social life of Internet users. In this study, we are particularly interested in identifying a post in a multi-party conversation that is unlikely to be further replied to, which therefore kills that thread of the conversation. For this purpose, we propose a deep learning model called the ConverNet. ConverNet is attractive due to its capability of modeling the internal structure of a long conversation and its appropriate encoding of the contextual information of the conversation, through effective integration of attention mechanisms. Empirical experiments on real-world datasets demonstrate the effectiveness of the proposal model. For the widely concerned topic, our analysis also offers implications for improving the quality and user experience of online conversations.
A short variational proof of equivalence between policy gradients and soft Q learning
Venue: arXiv cs.LG 2017
Year: 2017

Two main families of reinforcement learning algorithms, Q-learning and policy gradients, have recently been proven to be equivalent when using a softmax relaxation on one part, and an entropic regularization on the other. We relate this result to the well-known convex duality of Shannon entropy and the softmax function. Such a result is also known as the Donsker-Varadhan formula. This provides a short proof of the equivalence. We then interpret this duality further, and use ideas of convex analysis to prove a new policy inequality relative to soft Q-learning.
Network Utility Maximization in Adversarial Environments
Venue: arXiv cs.NI 2017
Year: 2017

Stochastic models have been dominant in network optimization theory for over two decades, due to their analytical tractability. However, these models fail to capture non-stationary or even adversarial network dynamics which are of increasing importance for modeling the behavior of networks under malicious attacks or characterizing short-term transient behavior. In this paper, we consider the network utility maximization problem in adversarial network settings. In particular, we focus on the tradeoffs between total queue length and utility regret which measures the difference in network utility between a causal policy and an "oracle" that knows the future within a finite time horizon. Two adversarial network models are developed to characterize the adversary's behavior. We provide lower bounds on the tradeoff between utility regret and queue length under these adversarial models, and analyze the performance of two control policies (i.e., the Drift-plus-Penalty algorithm and the Tracking Algorithm).
Aerial Spectral Super-Resolution using Conditional Adversarial Networks
Venue: arXiv cs.CV 2017
Year: 2017

Inferring spectral signatures from ground based natural images has acquired a lot of interest in applied deep learning. In contrast to the spectra of ground based images, aerial spectral images have low spatial resolution and suffer from higher noise interference. In this paper, we train a conditional adversarial network to learn an inverse mapping from a trichromatic space to 31 spectral bands within 400 to 700 nm. The network is trained on AeroCampus, a first of its kind aerial hyperspectral dataset. AeroCampus consists of high spatial resolution color images and low spatial resolution hyperspectral images (HSI). Color images synthesized from 31 spectral bands are used to train our network. With a baseline root mean square error of 2.48 on the synthesized RGB test data, we show that it is possible to generate spectral signatures in aerial imagery.
Freebase-triples: A Methodology for Processing the Freebase Data Dumps
Venue: arXiv cs.DB 2017
Year: 2017

The Freebase knowledge base was a significant Semantic Web and linked data technology during its years of operations since 2007. Following its acquisition by Google in 2010 and its shutdown in 2016, Freebase data is contained in a data dump of billions of RDF triples. In this research, an exploration of the Freebase data dumps will show best practices in understanding and using the Freebase data and also present a general methodology for parsing the linked data. The analysis is done with limited computing resources and the use of open-source Unix-like tools. The results showcase the efficiency of the technique and highlight redundancies in the data, with the possibility of restructuring nearly 60% of the original data. As an archival dataset that has not changed since 2015, Freebase's semantic structured data has applications in other prominent fields, such as information retrieval (IR) and knowledge-based question answering (KBQA). Freebase can also serve as a gateway to other structured datasets, such as DBpedia, Wikidata, and YAGO.
Towards Structured Analysis of Broadcast Badminton Videos
Venue: arXiv cs.CV 2017
Year: 2017

Sports video data is recorded for nearly every major tournament but remains archived and inaccessible to large scale data mining and analytics. It can only be viewed sequentially or manually tagged with higher-level labels which is time consuming and prone to errors. In this work, we propose an end-to-end framework for automatic attributes tagging and analysis of sport videos. We use commonly available broadcast videos of matches and, unlike previous approaches, does not rely on special camera setups or additional sensors. Our focus is on Badminton as the sport of interest. We propose a method to analyze a large corpus of badminton broadcast videos by segmenting the points played, tracking and recognizing the players in each point and annotating their respective badminton strokes. We evaluate the performance on 10 Olympic matches with 20 players and achieved 95.44% point segmentation accuracy, 97.38% player detection score (mAP@0.5), 97.98% player identification accuracy, and stroke segmentation edit scores of 80.48%. We further show that the automatically annotated videos alone could enable the gameplay analysis and inference by computing understandable metrics such as player's reaction time, speed, and footwork around the court, etc.
Stochastic Geometry Modeling and Analysis of Single- and Multi-Cluster Wireless Networks
Venue: arXiv cs.IT 2017
Year: 2017

This paper develops a stochastic geometry-based approach for the modeling and analysis of single- and multi-cluster wireless networks. We first define finite homogeneous Poisson point processes to model the number and locations of the transmitters in a confined region as a single-cluster wireless network. We study the coverage probability for a reference receiver for two strategies; closest-selection, where the receiver is served by the closest transmitter among all transmitters, and uniform-selection, where the serving transmitter is selected randomly with uniform distribution. Second, using Matern cluster processes, we extend our model and analysis to multi-cluster wireless networks. Here, the receivers are modeled in two types, namely, closed- and open-access. Closed-access receivers are distributed around the cluster centers of the transmitters according to a symmetric normal distribution and can be served only by the transmitters of their corresponding clusters. Open-access receivers, on the other hand, are placed independently of the transmitters and can be served by all transmitters. In all cases, the link distance distribution and the Laplace transform (LT) of the interference are derived. We also derive closed-form lower bounds on the LT of the interference for single-cluster wireless networks. The impact of different parameters on the performance is also investigated.
Building a Sentiment Corpus of Tweets in Brazilian Portuguese
Venue: arXiv cs.CL 2017
Year: 2017

The large amount of data available in social media, forums and websites motivates researches in several areas of Natural Language Processing, such as sentiment analysis. The popularity of the area due to its subjective and semantic characteristics motivates research on novel methods and approaches for classification. Hence, there is a high demand for datasets on different domains and different languages. This paper introduces TweetSentBR, a sentiment corpora for Brazilian Portuguese manually annotated with 15.000 sentences on TV show domain. The sentences were labeled in three classes (positive, neutral and negative) by seven annotators, following literature guidelines for ensuring reliability on the annotation. We also ran baseline experiments on polarity classification using three machine learning methods, reaching 80.99% on F-Measure and 82.06% on accuracy in binary classification, and 59.85% F-Measure and 64.62% on accuracy on three point classification.
Studying the Impact of Managers on Password Strength and Reuse
Venue: arXiv cs.CR 2017
Year: 2017

Despite their well-known security problems, passwords are still the incumbent authentication method for virtually all online services. To remedy the situation, end-users are very often referred to password managers as a solution to the password reuse and password weakness problems. However, to date the actual impact of password managers on password security and reuse has not been studied systematically. In this paper, we provide the first large-scale study of the password managers' influence on users' real-life passwords. From 476 participants of an online survey on users' password creation and management strategies, we recruit 170 participants that allowed us to monitor their passwords in-situ through a browser plugin. In contrast to prior work, we collect the passwords' entry methods (e.g., human or password manager) in addition to the passwords and their metrics. Based on our collected data and our survey, we gain a more complete picture of the factors that influence our participants' passwords' strength and reuse. We quantify for the first time that password managers indeed benefit the password strength and uniqueness, however, also our results also suggest that those benefits depend on the users' strategies and that managers without password generators rather aggravate the existing problems.
Human-Centric Data Cleaning [Vision]
Venue: arXiv cs.DB 2017
Year: 2017

Data Cleaning refers to the process of detecting and fixing errors in the data. Human involvement is instrumental at several stages of this process, e.g., to identify and repair errors, to validate computed repairs, etc. There is currently a plethora of data cleaning algorithms addressing a wide range of data errors (e.g., detecting duplicates, violations of integrity constraints, missing values, etc.). Many of these algorithms involve a human in the loop, however, this latter is usually coupled to the underlying cleaning algorithms. There is currently no end-to-end data cleaning framework that systematically involves humans in the cleaning pipeline regardless of the underlying cleaning algorithms. In this paper, we highlight key challenges that need to be addressed to realize such a framework. We present a design vision and discuss scenarios that motivate the need for such a framework to judiciously assist humans in the cleaning process. Finally, we present directions to implement such a framework.
RIDI: Robust IMU Double Integration
Venue: arXiv cs.CV 2017
Year: 2017

This paper proposes a novel data-driven approach for inertial navigation, which learns to estimate trajectories of natural human motions just from an inertial measurement unit (IMU) in every smartphone. The key observation is that human motions are repetitive and consist of a few major modes (e.g., standing, walking, or turning). Our algorithm regresses a velocity vector from the history of linear accelerations and angular velocities, then corrects low-frequency bias in the linear accelerations, which are integrated twice to estimate positions. We have acquired training data with ground-truth motions across multiple human subjects and multiple phone placements (e.g., in a bag or a hand). The qualitatively and quantitatively evaluations have demonstrated that our algorithm has surprisingly shown comparable results to full Visual Inertial navigation. To our knowledge, this paper is the first to integrate sophisticated machine learning techniques with inertial navigation, potentially opening up a new line of research in the domain of data-driven inertial navigation. We will publicly share our code and data to facilitate further research.