OpenRaiser/Intern-Atlas huggingface dataset:
SCRank: Spammer and Celebrity Ranking in Directed Social Networks
Venue: arXiv cs.SI 2018
Year: 2018

Many online social networks allow directed edges: Alice can unilaterally add an "edge" to Bob, typically indicating interest in Bob or Bob's content, without Bob's permission or reciprocation. In directed social networks we observe the rise of two distinctive classes of users: celebrities who accrue unreciprocated incoming links, and follow spammers, who generate unreciprocated outgoing links. Identifying users in these two classes is important for abuse detection, user and content ranking, privacy choices, and other social network features. In this paper we develop SCRank, an iterative algorithm to identify such users. We analyze SCRank both theoretically and experimentally. The spammer-celebrity definition is not amenable to analysis using standard power iteration, so we develop a novel potential function argument to show convergence to an approximate equilibrium point for a class of algorithms including SCRank. We then use experimental evaluation on a real global-scale social network and on synthetically generated graphs to observe that the algorithm converges quickly and consistently. Using synthetic data with built-in ground truth, we also experimentally show that the algorithm provides a good approximation to planted celebrities and spammers.
A new model for Cerebellar computation
Venue: arXiv cs.NE 2018
Year: 2018

The standard state space model is widely believed to account for the cerebellar computation in motor adaptation tasks [1]. Here we show that several recent experiments [2-4] where the visual feedback is irrelevant to the motor response challenge the standard model. Furthermore, we propose a new model that accounts for the the results presented in [2-4]. According to this new model, learning and forgetting are coupled and are error size dependent. We also show that under reasonable assumptions, our proposed model is the only model that accounts for both the classical adaptation paradigm as well as the recent experiments [2-4].
NetChain: Scale-Free Sub-RTT Coordination (Extended Version)
Venue: arXiv cs.DC 2018
Year: 2018

Coordination services are a fundamental building block of modern cloud systems, providing critical functionalities like configuration management and distributed locking. The major challenge is to achieve low latency and high throughput while providing strong consistency and fault-tolerance. Traditional server-based solutions require multiple round-trip times (RTTs) to process a query. This paper presents NetChain, a new approach that provides scale-free sub-RTT coordination in datacenters. NetChain exploits recent advances in programmable switches to store data and process queries entirely in the network data plane. This eliminates the query processing at coordination servers and cuts the end-to-end latency to as little as half of an RTT---clients only experience processing delay from their own software stack plus network delay, which in a datacenter setting is typically much smaller. We design new protocols and algorithms based on chain replication to guarantee strong consistency and to efficiently handle switch failures. We implement a prototype with four Barefoot Tofino switches and four commodity servers. Evaluation results show that compared to traditional server-based solutions like ZooKeeper, our prototype provides orders of magnitude higher throughput and lower latency, and handles failures gracefully.
BigDataBench: A Scalable and Unified Big Data and AI Benchmark Suite
Venue: arXiv cs.DC 2018
Year: 2018

Several fundamental changes in technology indicate domain-specific hardware and software co-design is the only path left. In this context, architecture, system, data management, and machine learning communities pay greater attention to innovative big data and AI algorithms, architecture, and systems. Unfortunately, complexity, diversity, frequently-changed workloads, and rapid evolution of big data and AI systems raise great challenges. First, the traditional benchmarking methodology that creates a new benchmark or proxy for every possible workload is not scalable, or even impossible for Big Data and AI benchmarking. Second, it is prohibitively expensive to tailor the architecture to characteristics of one or more application or even a domain of applications. We consider each big data and AI workload as a pipeline of one or more classes of units of computation performed on different initial or intermediate data inputs, each class of which we call a data motif. On the basis of our previous work that identifies eight data motifs taking up most of the run time of a wide variety of big data and AI workloads, we propose a scalable benchmarking methodology that uses the combination of one or more data motifs---to represent diversity of big data and AI workloads. Following this methodology, we present a unified big data and AI benchmark suite---BigDataBench 4.0, publicly available from~\url{http://prof.ict.ac.cn/BigDataBench}. This unified benchmark suite sheds new light on domain-specific hardware and software co-design: tailoring the system and architecture to characteristics of the unified eight data motifs other than one or more application case by case. Also, for the first time, we comprehensively characterize the CPU pipeline efficiency using the benchmarks of seven workload types in BigDataBench 4.0.
Locally Adaptive Learning Loss for Semantic Image Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

We propose a novel locally adaptive learning estimator for enhancing the inter- and intra- discriminative capabilities of Deep Neural Networks, which can be used as improved loss layer for semantic image segmentation tasks. Most loss layers compute pixel-wise cost between feature maps and ground truths, ignoring spatial layouts and interactions between neighboring pixels with same object category, and thus networks cannot be effectively sensitive to intra-class connections. Stride by stride, our method firstly conducts adaptive pooling filter operating over predicted feature maps, aiming to merge predicted distributions over a small group of neighboring pixels with same category, and then it computes cost between the merged distribution vector and their category label. Such design can make groups of neighboring predictions from same category involved into estimations on predicting correctness with respect to their category, and hence train networks to be more sensitive to regional connections between adjacent pixels based on their categories. In the experiments on Pascal VOC 2012 segmentation datasets, the consistently improved results show that our proposed approach achieves better segmentation masks against previous counterparts.
Conflict and Convention in Dynamic Networks
Venue: arXiv cs.SI 2018
Year: 2018

An important way to resolve games of conflict (snowdrift, hawk-dove, chicken) involves adopting a convention: a correlated equilibrium that avoids any conflict between aggressive strategies. Dynamic networks allow individuals to resolve conflict via their network connections rather than changing their strategy. Exploring how behavioral strategies coevolve with social networks reveals new dynamics that can help explain the origins and robustness of conventions. Here we model the emergence of conventions as correlated equilibria in dynamic networks. Our results show that networks have the tendency to break the symmetry between the two conventional solutions in a strongly biased way. Rather than the correlated equilibrium associated with ownership norms (play aggressive at home, not away), we usually see the opposite host-guest norm (play aggressive away, not at home) evolve on dynamic networks, a phenomenon common to human interaction. We also show that learning to avoid conflict can produce realistic network structures in a way different than preferential attachment models.
Sleep-deprived Fatigue Pattern Analysis using Large-Scale Selfies from Social Med
Venue: arXiv cs.CV 2018
Year: 2018

The complexities of fatigue have drawn much attention from researchers across various disciplines. Short-term fatigue may cause safety issue while driving; thus, dynamic systems were designed to track driver fatigue. Long-term fatigue could lead to chronic syndromes, and eventually affect individuals physical and psychological health. Traditional methodologies of evaluating fatigue not only require sophisticated equipment but also consume enormous time. In this paper, we attempt to develop a novel and efficient method to predict individual's fatigue rate by scrutinizing human facial cues. Our goal is to predict fatigue rate based on a selfie. To associate the fatigue rate with user behaviors, we have collected nearly 1-million timeline posts from 10,480 users on Instagram. We first detect all the faces and identify their demographics using automatic algorithms. Next, we investigate the fatigue distribution by weekday over different age, gender, and ethnic groups. This work represents a promising way to assess sleep-deprived fatigue, and our study provides a viable and efficient computational framework for user fatigue modeling in large-scale via social media.
Multi-Scale Spectrum Sensing in Dense Multi-Cell Cognitive Networks
Venue: arXiv cs.IT 2018
Year: 2018

Multi-scale spectrum sensing is proposed to overcome the cost of full network state information on the spectrum occupancy of primary users (PUs) in dense multi-cell cognitive networks. Secondary users (SUs) estimate the local spectrum occupancies and aggregate them hierarchically to estimate spectrum occupancy at multiple spatial scales. Thus, SUs obtain fine-grained estimates of spectrum occupancies of nearby cells, more relevant to scheduling tasks, and coarse-grained estimates of those of distant cells. An agglomerative clustering algorithm is proposed to design a cost-effective aggregation tree, matched to the structure of interference, robust to local estimation errors and delays. Given these multi-scale estimates, the SU traffic is adapted in a decentralized fashion in each cell, to optimize the trade-off among SU cell throughput, interference caused to PUs, and mutual SU interference. Numerical evaluations demonstrate a small degradation in SU cell throughput (up to 15% for a 0dB interference-to-noise ratio experienced at PUs) compared to a scheme with full network state information, using only one-third of the cost incurred in the exchange of spectrum estimates. The proposed interference-matched design is shown to significantly outperform a random tree design, by providing more relevant information for network control, and a state-of-the-art consensus-based algorithm, which does not leverage the spatio-temporal structure of interference across the network.
EmotionLines: An Emotion Corpus of Multi-Party Conversations
Venue: arXiv cs.CL 2018
Year: 2018

Feeling emotion is a critical characteristic to distinguish people from machines. Among all the multi-modal resources for emotion detection, textual datasets are those containing the least additional information in addition to semantics, and hence are adopted widely for testing the developed systems. However, most of the textual emotional datasets consist of emotion labels of only individual words, sentences or documents, which makes it challenging to discuss the contextual flow of emotions. In this paper, we introduce EmotionLines, the first dataset with emotions labeling on all utterances in each dialogue only based on their textual content. Dialogues in EmotionLines are collected from Friends TV scripts and private Facebook messenger dialogues. Then one of seven emotions, six Ekman's basic emotions plus the neutral emotion, is labeled on each utterance by 5 Amazon MTurkers. A total of 29,245 utterances from 2,000 dialogues are labeled in EmotionLines. We also provide several strong baselines for emotion detection models on EmotionLines in this paper.
Sequence-Aware Recommender Systems
Venue: arXiv cs.IR 2018
Year: 2018

Recommender systems are one of the most successful applications of data mining and machine learning technology in practice. Academic research in the field is historically often based on the matrix completion problem formulation, where for each user-item-pair only one interaction (e.g., a rating) is considered. In many application domains, however, multiple user-item interactions of different types can be recorded over time. And, a number of recent works have shown that this information can be used to build richer individual user models and to discover additional behavioral patterns that can be leveraged in the recommendation process. In this work we review existing works that consider information from such sequentially-ordered user- item interaction logs in the recommendation process. Based on this review, we propose a categorization of the corresponding recommendation tasks and goals, summarize existing algorithmic solutions, discuss methodological approaches when benchmarking what we call sequence-aware recommender systems, and outline open challenges in the area.
GPU Implementation and Optimization of a Flexible MAP Decoder for Synchronization Correction
Venue: arXiv cs.DC 2018
Year: 2018

In this paper we present an optimized parallel implementation of a flexible MAP decoder for synchronization error correcting codes, supporting a very wide range of code sizes and channel conditions. On mid-range GPUs we demonstrate decoding speedups of more than two orders of magnitude over a CPU implementation of the same optimized algorithm, and more than an order of magnitude over our earlier GPU implementation. The prominent challenge is to maintain high parallelization efficiency over a wide range of code sizes and channel conditions, and different execution hardware. We ensure this with a dynamic strategy for choosing parallel execution parameters at run-time. We also present a variant that trades off some decoding speed for significantly reduced memory requirement, with no loss to the decoder's error correction performance. The increased throughput of our implementation and its ability to work with less memory allow us to analyse larger codes and poorer channel conditions, and makes practical use of such codes more feasible.
Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms
Venue: arXiv cs.LG 2018
Year: 2018

We study the problem of robustly learning multi-dimensional histograms. A $d$-dimensional function $h: D \rightarrow \mathbb{R}$ is called a $k$-histogram if there exists a partition of the domain $D \subseteq \mathbb{R}^d$ into $k$ axis-aligned rectangles such that $h$ is constant within each such rectangle. Let $f: D \rightarrow \mathbb{R}$ be a $d$-dimensional probability density function and suppose that $f$ is $\mathrm{OPT}$-close, in $L_1$-distance, to an unknown $k$-histogram (with unknown partition). Our goal is to output a hypothesis that is $O(\mathrm{OPT}) + ε$ close to $f$, in $L_1$-distance. We give an algorithm for this learning problem that uses $n = \tilde{O}_d(k/ε^2)$ samples and runs in time $\tilde{O}_d(n)$. For any fixed dimension, our algorithm has optimal sample complexity, up to logarithmic factors, and runs in near-linear time. Prior to our work, the time complexity of the $d=1$ case was well-understood, but significant gaps in our understanding remained even for $d=2$.
Closed-form solution to cooperative visual-inertial structure from motion
Venue: arXiv cs.RO 2018
Year: 2018

This paper considers the problem of visual-inertial sensor fusion in the cooperative case and it provides new theoretical contributions, which regard its observability and its resolvability in closed form. The case of two agents is investigated. Each agent is equipped with inertial sensors (accelerometer and gyroscope) and with a monocular camera. By using the monocular camera, each agent can observe the other agent. No additional camera observations (e.g., of external point features in the environment) are considered. All the inertial sensors are assumed to be affected by a bias. First, the entire observable state is analytically derived. This state includes the absolute scale, the relative velocity between the two agents, the three Euler angles that express the rotation between the two agent frames and all the accelerometer and gyroscope biases. Second, the paper provides the extension of the closed-form solution given in [19] (which holds for a single agent) to the aforementioned cooperative case. The impact of the presence of the bias on the performance of this closed-form solution is investigated. As in the case of a single agent, this performance is significantly sensitive to the presence of a bias on the gyroscope, while, the presence of a bias on the accelerometer is negligible. Finally, a simple and effective method to obtain the gyroscope bias is proposed. Extensive simulations clearly show that the proposed method is successful. It is amazing that, it is possible to automatically retrieve the absolute scale and simultaneously calibrate the gyroscopes not only without any prior knowledge (as in [13]), but also without external point features in the environment.
Unsupervised Grammar Induction with Depth-bounded PCFG
Venue: arXiv cs.CL 2018
Year: 2018

There has been recent interest in applying cognitively or empirically motivated bounds on recursion depth to limit the search space of grammar induction models (Ponvert et al., 2011; Noji and Johnson, 2016; Shain et al., 2016). This work extends this depth-bounding approach to probabilistic context-free grammar induction (DB-PCFG), which has a smaller parameter space than hierarchical sequence models, and therefore more fully exploits the space reductions of depth-bounding. Results for this model on grammar acquisition from transcribed child-directed speech and newswire text exceed or are competitive with those of other models when evaluated on parse accuracy. Moreover, gram- mars acquired from this model demonstrate a consistent use of category labels, something which has not been demonstrated by other acquisition models.
Evaluating Scoped Meaning Representations
Venue: arXiv cs.CL 2018
Year: 2018

Semantic parsing offers many opportunities to improve natural language understanding. We present a semantically annotated parallel corpus for English, German, Italian, and Dutch where sentences are aligned with scoped meaning representations in order to capture the semantics of negation, modals, quantification, and presupposition triggers. The semantic formalism is based on Discourse Representation Theory, but concepts are represented by WordNet synsets and thematic roles by VerbNet relations. Translating scoped meaning representations to sets of clauses enables us to compare them for the purpose of semantic parser evaluation and checking translations. This is done by computing precision and recall on matching clauses, in a similar way as is done for Abstract Meaning Representations. We show that our matching tool for evaluating scoped meaning representations is both accurate and efficient. Applying this matching tool to three baseline semantic parsers yields F-scores between 43% and 54%. A pilot study is performed to automatically find changes in meaning by comparing meaning representations of translations. This comparison turns out to be an additional way of (i) finding annotation mistakes and (ii) finding instances where our semantic analysis needs to be improved.
Gossiping in Message-Passing Systems
Venue: arXiv cs.FL 2018
Year: 2018

We study the gossip problem in a message-passing environment: When a process receives a message, it has to decide whether the sender has more recent information on other processes than itself. This problem is at the heart of many distributed algorithms, and it is tightly related to questions from formal methods concerning the expressive power of distributed automata. We provide a non-deterministic gossip protocol for message-passing systems with unbounded FIFO channels, using only finitely many local states and a finite message alphabet. We show that this is optimal in the sense that there is no deterministic counterpart. As an application, the gossip protocol allows us to show that message-passing systems capture well-known extensions of linear-time temporal logics to a concurrent setting.
Interactive Image Manipulation with Natural Language Instruction Commands
Venue: arXiv cs.CV 2018
Year: 2018

We propose an interactive image-manipulation system with natural language instruction, which can generate a target image from a source image and an instruction that describes the difference between the source and the target image. The system makes it possible to modify a generated image interactively and make natural language conditioned image generation more controllable. We construct a neural network that handles image vectors in latent space to transform the source vector to the target vector by using the vector of instruction. The experimental results indicate that the proposed framework successfully generates the target image by using a source image and an instruction on manipulation in our dataset.
Bandwidth Partitioning and Downlink Analysis in Millimeter Wave Integrated Access and Backhaul for 5G
Venue: arXiv cs.IT 2018
Year: 2018

With the increasing network densification, it has become exceedingly difficult to provide traditional fiber backhaul access to each cell site, which is especially true for small cell base stations (SBSs). The increasing maturity of millimeter wave (mm-wave) communication has opened up the possibility of providing high-speed wireless backhaul to such cell sites. Since mm-wave is also suitable for access links, the third generation partnership project (3GPP) is envisioning an integrated access and backhaul (IAB) architecture for the fifth generation (5G) cellular networks in which the same infrastructure and spectral resources will be used for both access and backhaul. In this paper, we develop an analytical framework for IAB-enabled cellular network using which its downlink rate coverage probability is accurately characterized. Using this framework, we study the performance of three backhaul bandwidth (BW) partition strategies: 1) equal partition: when all SBSs obtain equal share of the backhaul BW; 2) instantaneous load-based partition: when the backhaul BW share of an SBS is proportional to its instantaneous load; and 3) average load-based partition: when the backhaul BW share of an SBS is proportional to its average load. Our analysis shows that depending on the choice of the partition strategy, there exists an optimal split of access and backhaul BW for which the rate coverage is maximized. Further, there exists a critical volume of cell-load (total number of users) beyond which the gains provided by the IAB-enabled network disappear and its performance converges to that of the traditional macro-only network with no SBSs.