OpenRaiser/Intern-Atlas huggingface dataset:
WikiM: Metapaths based Wikification of Scientific Abstracts
Venue: arXiv cs.IR 2017
Year: 2017

In order to disseminate the exponential extent of knowledge being produced in the form of scientific publications, it would be best to design mechanisms that connect it with already existing rich repository of concepts -- the Wikipedia. Not only does it make scientific reading simple and easy (by connecting the involved concepts used in the scientific articles to their Wikipedia explanations) but also improves the overall quality of the article. In this paper, we present a novel metapath based method, WikiM, to efficiently wikify scientific abstracts -- a topic that has been rarely investigated in the literature. One of the prime motivations for this work comes from the observation that, wikified abstracts of scientific documents help a reader to decide better, in comparison to the plain abstracts, whether (s)he would be interested to read the full article. We perform mention extraction mostly through traditional tf-idf measures coupled with a set of smart filters. The entity linking heavily leverages on the rich citation and author publication networks. Our observation is that various metapaths defined over these networks can significantly enhance the overall performance of the system. For mention extraction and entity linking, we outperform most of the competing state-of-the-art techniques by a large margin arriving at precision values of 72.42% and 73.8% respectively over a dataset from the ACL Anthology Network. In order to establish the robustness of our scheme, we wikify three other datasets and get precision values of 63.41%-94.03% and 67.67%-73.29% respectively for the mention extraction and the entity linking phase.
Low-Density Code-Domain NOMA: Better Be Regular
Venue: arXiv cs.IT 2017
Year: 2017

A closed-form analytical expression is derived for the limiting empirical squared singular value density of a spreading (signature) matrix corresponding to sparse low-density code-domain (LDCD) non-orthogonal multiple-access (NOMA) with regular random user-resource allocation. The derivation relies on associating the spreading matrix with the adjacency matrix of a large semiregular bipartite graph. For a simple repetition-based sparse spreading scheme, the result directly follows from a rigorous analysis of spectral measures of infinite graphs. Turning to random (sparse) binary spreading, we harness the cavity method from statistical physics, and show that the limiting spectral density coincides in both cases. Next, we use this density to compute the normalized input-output mutual information of the underlying vector channel in the large-system limit. The latter may be interpreted as the achievable total throughput per dimension with optimum processing in a corresponding multiple-access channel setting or, alternatively, in a fully-symmetric broadcast channel setting with full decoding capabilities at each receiver. Surprisingly, the total throughput of regular LDCD-NOMA is found to be not only superior to that achieved with irregular user-resource allocation, but also to the total throughput of dense randomly-spread NOMA, for which optimum processing is computationally intractable. In contrast, the superior performance of regular LDCD-NOMA can be potentially achieved with a feasible message-passing algorithm. This observation may advocate employing regular, rather than irregular, LDCD-NOMA in 5G cellular physical layer design.
Cell Tracking via Proposal Generation and Selection
Venue: arXiv cs.CV 2017
Year: 2017

Microscopy imaging plays a vital role in understanding many biological processes in development and disease. The recent advances in automation of microscopes and development of methods and markers for live cell imaging has led to rapid growth in the amount of image data being captured. To efficiently and reliably extract useful insights from these captured sequences, automated cell tracking is essential. This is a challenging problem due to large variation in the appearance and shapes of cells depending on many factors including imaging methodology, biological characteristics of cells, cell matrix composition, labeling methodology, etc. Often cell tracking methods require a sequence-specific segmentation method and manual tuning of many tracking parameters, which limits their applicability to sequences other than those they are designed for. In this paper, we propose 1) a deep learning based cell proposal method, which proposes candidates for cells along with their scores, and 2) a cell tracking method, which links proposals in adjacent frames in a graphical model using edges representing different cellular events and poses joint cell detection and tracking as the selection of a subset of cell and edge proposals. Our method is completely automated and given enough training data can be applied to a wide variety of microscopy sequences. We evaluate our method on multiple fluorescence and phase contrast microscopy sequences containing cells of various shapes and appearances from ISBI cell tracking challenge, and show that our method outperforms existing cell tracking methods. Code is available at: https://github.com/SaadUllahAkram/CellTracker
A Distributed Learning Dynamics in Social Groups
Venue: arXiv cs.LG 2017
Year: 2017

We study a distributed learning process observed in human groups and other social animals. This learning process appears in settings in which each individual in a group is trying to decide over time, in a distributed manner, which option to select among a shared set of options. Specifically, we consider a stochastic dynamics in a group in which every individual selects an option in the following two-step process: (1) select a random individual and observe the option that individual chose in the previous time step, and (2) adopt that option if its stochastic quality was good at that time step. Various instantiations of such distributed learning appear in nature, and have also been studied in the social science literature. From the perspective of an individual, an attractive feature of this learning process is that it is a simple heuristic that requires extremely limited computational capacities. But what does it mean for the group -- could such a simple, distributed and essentially memoryless process lead the group as a whole to perform optimally? We show that the answer to this question is yes -- this distributed learning is highly effective at identifying the best option and is close to optimal for the group overall. Our analysis also gives quantitative bounds that show fast convergence of these stochastic dynamics. Prior to our work the only theoretical work related to such learning dynamics has been either in deterministic special cases or in the asymptotic setting. Finally, we observe that our infinite population dynamics is a stochastic variant of the classic multiplicative weights update (MWU) method. Consequently, we arrive at the following interesting converse: the learning dynamics on a finite population considered here can be viewed as a novel distributed and low-memory implementation of the classic MWU method.
Incentive Mechanism Design for Cache-Assisted D2D Communications: A Mobility-Aware Approach
Venue: arXiv cs.IT 2017
Year: 2017

Caching popular contents at mobile devices, assisted by device-to-device (D2D) communications, is considered as a promising technique for mobile content delivery. It can effectively reduce backhaul traffic and service cost, as well as improving the spectrum efficiency. However, due to the selfishness of mobile users, incentive mechanisms will be needed to motivate device caching. In this paper, we investigate incentive mechanism design in cache-assisted D2D networks, taking advantage of the user mobility information. An inter-contact model is adopted to capture the average time between two consecutive contacts of each device pair. A Stackelberg game is formulated, where each user plays as a follower aiming at maximizing its own utility and the mobile network operator (MNO) plays as a leader aiming at minimizing the cost. Assuming that user responses can be predicted by the MNO, a cost minimization problem is formulated. Since this problem is NP-hard, we reformulate it as a non-negative submodular maximization problem and develop $(\frac{1}{4+ε})$-approximation local search algorithm to solve it. In the simulation, we demonstrate that the local search algorithm provides near optimal performance. By comparing with other caching strategies, we validate the effectiveness of the proposed incentive-based mobility-aware caching strategy.
DeepDeath: Learning to Predict the Underlying Cause of Death with Big Data
Venue: arXiv cs.CL 2017
Year: 2017

Multiple cause-of-death data provides a valuable source of information that can be used to enhance health standards by predicting health related trajectories in societies with large populations. These data are often available in large quantities across U.S. states and require Big Data techniques to uncover complex hidden patterns. We design two different classes of models suitable for large-scale analysis of mortality data, a Hadoop-based ensemble of random forests trained over N-grams, and the DeepDeath, a deep classifier based on the recurrent neural network (RNN). We apply both classes to the mortality data provided by the National Center for Health Statistics and show that while both perform significantly better than the random classifier, the deep model that utilizes long short-term memory networks (LSTMs), surpasses the N-gram based models and is capable of learning the temporal aspect of the data without a need for building ad-hoc, expert-driven features.
A Comment on "A New Degree of Freedom For Energy Efficiency of Digital Communication Systems"
Venue: arXiv cs.IT 2017
Year: 2017

This comment recalls a previously proposed encoding scheme involving two synchronized random number generators (RNGs) to compress the transmission message. It is also claimed that the recently proposed random number modulation (RNM) scheme suffers considerably from the severe error propagation, and that, in general, the overall energy consumption is minimized when all information bits are transmitted as fast as possible with the minimum latency.
A Duality Between Depth-Three Formulas and Approximation by Depth-Two
Venue: arXiv cs.CC 2017
Year: 2017

We establish an explicit link between depth-3 formulas and one-sided approximation by depth-2 formulas, which were previously studied independently. Specifically, we show that the minimum size of depth-3 formulas is (up to a factor of n) equal to the inverse of the maximum, over all depth-2 formulas, of one-sided-error correlation bound divided by the size of the depth-2 formula, on a certain hard distribution. We apply this duality to obtain several consequences: 1. Any function f can be approximated by a CNF formula of size $O(ε2^n / n)$ with one-sided error and advantage $ε$ for some $ε$, which is tight up to a constant factor. 2. There exists a monotone function f such that f can be approximated by some polynomial-size CNF formula, whereas any monotone CNF formula approximating f requires exponential size. 3. Any depth-3 formula computing the parity function requires $Ω(2^{2 \sqrt{n}})$ gates, which is tight up to a factor of $\sqrt n$. This establishes a quadratic separation between depth-3 circuit size and depth-3 formula size. 4. We give a characterization of the depth-3 monotone circuit complexity of the majority function, in terms of a natural extremal problem on hypergraphs. In particular, we show that a known extension of Turan's theorem gives a tight (up to a polynomial factor) circuit size for computing the majority function by a monotone depth-3 circuit with bottom fan-in 2. 5. AC0[p] has exponentially small one-sided correlation with the parity function for odd prime p.
Improving the Performance and Endurance of Persistent Memory with Loose-Ordering Consistency
Venue: arXiv cs.AR 2017
Year: 2017

Persistent memory provides high-performance data persistence at main memory. Memory writes need to be performed in strict order to satisfy storage consistency requirements and enable correct recovery from system crashes. Unfortunately, adhering to such a strict order significantly degrades system performance and persistent memory endurance. This paper introduces a new mechanism, Loose-Ordering Consistency (LOC), that satisfies the ordering requirements at significantly lower performance and endurance loss. LOC consists of two key techniques. First, Eager Commit eliminates the need to perform a persistent commit record write within a transaction. We do so by ensuring that we can determine the status of all committed transactions during recovery by storing necessary metadata information statically with blocks of data written to memory. Second, Speculative Persistence relaxes the write ordering between transactions by allowing writes to be speculatively written to persistent memory. A speculative write is made visible to software only after its associated transaction commits. To enable this, our mechanism supports the tracking of committed transaction ID and multi-versioning in the CPU cache. Our evaluations show that LOC reduces the average performance overhead of memory persistence from 66.9% to 34.9% and the memory write traffic overhead from 17.1% to 3.4% on a variety of workloads.
A performance spectrum for parallel computational frameworks that solve PDEs
Venue: arXiv cs.MS 2017
Year: 2017

Important computational physics problems are often large-scale in nature, and it is highly desirable to have robust and high performing computational frameworks that can quickly address these problems. However, it is no trivial task to determine whether a computational framework is performing efficiently or is scalable. The aim of this paper is to present various strategies for better understanding the performance of any parallel computational frameworks for solving PDEs. Important performance issues that negatively impact time-to-solution are discussed, and we propose a performance spectrum analysis that can enhance one's understanding of critical aforementioned performance issues. As proof of concept, we examine commonly used finite element simulation packages and software and apply the performance spectrum to quickly analyze the performance and scalability across various hardware platforms, software implementations, and numerical discretizations. It is shown that the proposed performance spectrum is a versatile performance model that is not only extendable to more complex PDEs such as hydrostatic ice sheet flow equations, but also useful for understanding hardware performance in a massively parallel computing environment. Potential applications and future extensions of this work are also discussed.
Mind the Gap: A Well Log Data Analysis
Venue: arXiv cs.AI 2017
Year: 2017

The main task in oil and gas exploration is to gain an understanding of the distribution and nature of rocks and fluids in the subsurface. Well logs are records of petro-physical data acquired along a borehole, providing direct information about what is in the subsurface. The data collected by logging wells can have significant economic consequences, due to the costs inherent to drilling wells, and the potential return of oil deposits. In this paper, we describe preliminary work aimed at building a general framework for well log prediction. First, we perform a descriptive and exploratory analysis of the gaps in the neutron porosity logs of more than a thousand wells in the North Sea. Then, we generate artificial gaps in the neutron logs that reflect the statistics collected before. Finally, we compare Artificial Neural Networks, Random Forests, and three algorithms of Linear Regression in the prediction of missing gaps on a well-by-well basis.
The Complexity of Routing with Few Collisions
Venue: arXiv cs.CC 2017
Year: 2017

We study the computational complexity of routing multiple objects through a network in such a way that only few collisions occur: Given a graph $G$ with two distinct terminal vertices and two positive integers $p$ and $k$, the question is whether one can connect the terminals by at least $p$ routes (e.g. paths) such that at most $k$ edges are time-wise shared among them. We study three types of routes: traverse each vertex at most once (paths), each edge at most once (trails), or no such restrictions (walks). We prove that for paths and trails the problem is NP-complete on undirected and directed graphs even if $k$ is constant or the maximum vertex degree in the input graph is constant. For walks, however, it is solvable in polynomial time on undirected graphs for arbitrary $k$ and on directed graphs if $k$ is constant. We additionally study for all route types a variant of the problem where the maximum length of a route is restricted by some given upper bound. We prove that this length-restricted variant has the same complexity classification with respect to paths and trails, but for walks it becomes NP-complete on undirected graphs.
Constant Space and Non-Constant Time in Distributed Computing
Venue: arXiv cs.DC 2017
Year: 2017

While the relationship of time and space is an established topic in traditional centralised complexity theory, this is not the case in distributed computing. We aim to remedy this by studying the time and space complexity of algorithms in a weak message-passing model of distributed computing. While a constant number of communication rounds implies a constant number of states visited during the execution, the other direction is not clear at all. We consider several graph families and show that indeed, there exist non-trivial graph problems that are solvable by constant-space algorithms but that require a non-constant running time. This provides us with a new complexity class for distributed computing and raises interesting questions about the existence of further combinations of time and space complexity.
Why & When Deep Learning Works: Looking Inside Deep Learnings
Venue: arXiv cs.LG 2017
Year: 2017

The Intel Collaborative Research Institute for Computational Intelligence (ICRI-CI) has been heavily supporting Machine Learning and Deep Learning research from its foundation in 2012. We have asked six leading ICRI-CI Deep Learning researchers to address the challenge of "Why & When Deep Learning works", with the goal of looking inside Deep Learning, providing insights on how deep networks function, and uncovering key observations on their expressiveness, limitations, and potential. The output of this challenge resulted in five papers that address different facets of deep learning. These different facets include a high-level understating of why and when deep networks work (and do not work), the impact of geometry on the expressiveness of deep networks, and making deep networks interpretable.
Linguistic Diversities of Demographic Groups in Twitter
Venue: arXiv cs.SI 2017
Year: 2017

The massive popularity of online social media provides a unique opportunity for researchers to study the linguistic characteristics and patterns of user's interactions. In this paper, we provide an in-depth characterization of language usage across demographic groups in Twitter. In particular, we extract the gender and race of Twitter users located in the U.S. using advanced image processing algorithms from Face++. Then, we investigate how demographic groups (i.e. male/female, Asian/Black/White) differ in terms of linguistic styles and also their interests. We extract linguistic features from 6 categories (affective attributes, cognitive attributes, lexical density and awareness, temporal references, social and personal concerns, and interpersonal focus), in order to identify the similarities and differences in particular writing set of attributes. In addition, we extract the absolute ranking difference of top phrases between demographic groups. As a dimension of diversity, we also use the topics of interest that we retrieve from each user. Our analysis unveils clear differences in the writing styles (and the topics of interest) of different demographic groups, with variation seen across both gender and race lines. We hope our effort can stimulate the development of new studies related to demographic information in the online space.
GQ($λ$) Quick Reference and Implementation Guide
Venue: arXiv cs.LG 2017
Year: 2017

This document should serve as a quick reference for and guide to the implementation of linear GQ($λ$), a gradient-based off-policy temporal-difference learning algorithm. Explanation of the intuition and theory behind the algorithm are provided elsewhere (e.g., Maei & Sutton 2010, Maei 2011). If you questions or concerns about the content in this document or the attached java code please email Adam White (adam.white@ualberta.ca). The code is provided as part of the source files in the arXiv submission.
Distribution of degrees of freedom over structure and motion of rigid bodies
Venue: arXiv cs.CV 2017
Year: 2017

This paper is concerned with recovery of motion and structure parameters from multiframes under orthogonal projection when only points are traced. The main question is how many points and/or how many frames are necessary for the task. It is demonstrated that 3 frames and 3 points are the absolute minimum. Closed-form solution is presented. Furthermore, it is shown that the task may be linearized if either four points or four frames are available. It is demonstrated that no increase in the number of points may lead to recovery of structure and motion parameters from two frames only. It is shown that instead the increase in the number of points may support the task of tracing the points from frame to frame.
Weighted Selection Combinings for Differential Decode-and-Forward Cooperative Networks
Venue: arXiv cs.IT 2017
Year: 2017

Two weighted selection combining (WSC) schemes are proposed for a differential decode-and-forward relaying system in Rayleigh fading channels. Compared to the conventional selection combining scheme, the decision variable of the relay link is multiplied by a scale factor to combat the error propagation phenomenon. Average bit-error rate (ABER) expressions of the two proposed WSC schemes are derived in closed-form and verified by simulation results. For the second WSC scheme, asymptotic ABER expression and diversity order are derived to gain more insight into this scheme. Moreover, it is demonstrated that both WSC schemes can overcome the extra noise amplification induced by the link adaptive relaying scheme. The first WSC scheme is slightly inferior to the second one, which has a higher complexity. Both proposed WSC schemes outperform the conventional selection combining scheme.
Building a Semantic Role Labelling System for Vietnamese
Venue: arXiv cs.CL 2017
Year: 2017

Semantic role labelling (SRL) is a task in natural language processing which detects and classifies the semantic arguments associated with the predicates of a sentence. It is an important step towards understanding the meaning of a natural language. There exists SRL systems for well-studied languages like English, Chinese or Japanese but there is not any such system for the Vietnamese language. In this paper, we present the first SRL system for Vietnamese with encouraging accuracy. We first demonstrate that a simple application of SRL techniques developed for English could not give a good accuracy for Vietnamese. We then introduce a new algorithm for extracting candidate syntactic constituents, which is much more accurate than the common node-mapping algorithm usually used in the identification step. Finally, in the classification step, in addition to the common linguistic features, we propose novel and useful features for use in SRL. Our SRL system achieves an $F_1$ score of 73.53\% on the Vietnamese PropBank corpus. This system, including software and corpus, is available as an open source project and we believe that it is a good baseline for the development of future Vietnamese SRL systems.