OpenRaiser/Intern-Atlas huggingface dataset:
Long live the scientists: Tracking the scientific fame of great minds in physics
Venue: arXiv cs.DL 2018
Year: 2018

This study utilizes global digitalized books and articles to examine the scientific fame of the most influential physicists. Our research reveals that the greatest minds are gone but not forgotten. Their scientific impacts on human history have persisted for centuries. We also find evidence in support of own-group fame preference, i.e., that the scientists have greater reputations in their home countries or among scholars sharing the same languages. We argue that, when applied appropriately, Google Books and Ngram Viewer can serve as promising tools for altmetrics, providing a more comprehensive picture of the impacts scholars and their achievements have made beyond academia.
Hyperscaling Internet Graph Analysis with D4M on the MIT SuperCloud
Venue: arXiv cs.DC 2018
Year: 2018

Detecting anomalous behavior in network traffic is a major challenge due to the volume and velocity of network traffic. For example, a 10 Gigabit Ethernet connection can generate over 50 MB/s of packet headers. For global network providers, this challenge can be amplified by many orders of magnitude. Development of novel computer network traffic analytics requires: high level programming environments, massive amount of packet capture (PCAP) data, and diverse data products for "at scale" algorithm pipeline development. D4M (Dynamic Distributed Dimensional Data Model) combines the power of sparse linear algebra, associative arrays, parallel processing, and distributed databases (such as SciDB and Apache Accumulo) to provide a scalable data and computation system that addresses the big data problems associated with network analytics development. Combining D4M with the MIT SuperCloud manycore processors and parallel storage system enables network analysts to interactively process massive amounts of data in minutes. To demonstrate these capabilities, we have implemented a representative analytics pipeline in D4M and benchmarked it on 96 hours of Gigabit PCAP data with MIT SuperCloud. The entire pipeline from uncompressing the raw files to database ingest was implemented in 135 lines of D4M code and achieved speedups of over 20,000.
Embedded Pilot-Aided Channel Estimation for OTFS in Delay-Doppler Channels
Venue: arXiv cs.IT 2018
Year: 2018

Orthogonal time frequency space (OTFS) modulation was shown to provide significant error performance advantages over orthogonal frequency division multiplexing (OFDM) in delay--Doppler channels. In order to detect OTFS modulated data, the channel impulse response needs to be known at the receiver. In this paper, we propose embedded pilot-aided channel estimation schemes for OTFS. In each OTFS frame, we arrange pilot, guard, and data symbols in the delay--Doppler plane to suitably avoid interference between pilot and data symbols at the receiver. We develop such symbol arrangements for OTFS over multipath channels with integer and fractional Doppler shifts, respectively. At the receiver, channel estimation is performed based on a threshold method and the estimated channel information is used for data detection via a message passing (MP) algorithm. Thanks to our specific embedded symbol arrangements, both channel estimation and data detection are performed within the same OTFS frame with a minimum overhead. We compare by simulations the error performance of OTFS using the proposed channel estimation and OTFS with ideally known channel information and observe only a marginal performance loss. We also demonstrate that the proposed channel estimation in OTFS significantly outperforms OFDM with known channel information. Finally, we present extensions of the proposed schemes to MIMO and multi-user uplink/downlink.
Efficiently Processing Workflow Provenance Queries on SPARK
Venue: arXiv cs.DC 2018
Year: 2018

In this paper, we investigate how we can leverage Spark platform for efficiently processing provenance queries on large volumes of workflow provenance data. We focus on processing provenance queries at attribute-value level which is the finest granularity available. We propose a novel weakly connected component based framework which is carefully engineered to quickly determine a minimal volume of data containing the entire lineage of the queried attribute-value. This minimal volume of data is then processed to figure out the provenance of the queried attribute-value. The proposed framework computes weakly connected components on the workflow provenance graph and further partitions the large components as a collection of weakly connected sets. The framework exploits the workflow dependency graph to effectively partition the large components into a collection of weakly connected sets. We study the effectiveness of the proposed framework through experiments on a provenance trace obtained from a real-life unstructured text curation workflow. On provenance graphs containing upto 500M nodes and edges, we show that the proposed framework answers provenance queries in real-time and easily outperforms the naive approaches.
Guiding Deep Learning System Testing using Surprise Adequacy
Venue: arXiv cs.SE 2018
Year: 2018

Deep Learning (DL) systems are rapidly being adopted in safety and security critical domains, urgently calling for ways to test their correctness and robustness. Testing of DL systems has traditionally relied on manual collection and labelling of data. Recently, a number of coverage criteria based on neuron activation values have been proposed. These criteria essentially count the number of neurons whose activation during the execution of a DL system satisfied certain properties, such as being above predefined thresholds. However, existing coverage criteria are not sufficiently fine grained to capture subtle behaviours exhibited by DL systems. Moreover, evaluations have focused on showing correlation between adversarial examples and proposed criteria rather than evaluating and guiding their use for actual testing of DL systems. We propose a novel test adequacy criterion for testing of DL systems, called Surprise Adequacy for Deep Learning Systems (SADL), which is based on the behaviour of DL systems with respect to their training data. We measure the surprise of an input as the difference in DL system's behaviour between the input and the training data (i.e., what was learnt during training), and subsequently develop this as an adequacy criterion: a good test input should be sufficiently but not overtly surprising compared to training data. Empirical evaluation using a range of DL systems from simple image classifiers to autonomous driving car platforms shows that systematic sampling of inputs based on their surprise can improve classification accuracy of DL systems against adversarial examples by up to 77.5% via retraining.
The Social Cost of Strategic Classification
Venue: arXiv cs.LG 2018
Year: 2018

Consequential decision-making typically incentivizes individuals to behave strategically, tailoring their behavior to the specifics of the decision rule. A long line of work has therefore sought to counteract strategic behavior by designing more conservative decision boundaries in an effort to increase robustness to the effects of strategic covariate shift. We show that these efforts benefit the institutional decision maker at the expense of the individuals being classified. Introducing a notion of social burden, we prove that any increase in institutional utility necessarily leads to a corresponding increase in social burden. Moreover, we show that the negative externalities of strategic classification can disproportionately harm disadvantaged groups in the population. Our results highlight that strategy-robustness must be weighed against considerations of social welfare and fairness.
Drawing Subcubic 1-Planar Graphs with Few Bends, Few Slopes, and Large Angles
Venue: arXiv cs.CG 2018
Year: 2018

We show that the 1-planar slope number of 3-connected cubic 1-planar graphs is at most 4 when edges are drawn as polygonal curves with at most 1 bend each. This bound is obtained by drawings whose vertex and crossing resolution is at least $π/4$. On the other hand, if the embedding is fixed, then there is a 3-connected cubic 1-planar graph that needs 3 slopes when drawn with at most 1 bend per edge. We also show that 2 slopes always suffice for 1-planar drawings of subcubic 1-planar graphs with at most 2 bends per edge. This bound is obtained with vertex resolution $π/2$ and the drawing is RAC (crossing resolution $π/2$). Finally, we prove lower bounds for the slope number of straight-line 1-planar drawings in terms of number of vertices and maximum degree.
A Perspective on Unique Information: Directionality, Intuitions, and Secret Key Agreement
Venue: arXiv cs.IT 2018
Year: 2018

Recently, the partial information decomposition emerged as a promising framework for identifying the meaningful components of the information contained in a joint distribution. Its adoption and practical application, however, have been stymied by the lack of a generally-accepted method of quantifying its components. Here, we briefly discuss the bivariate (two-source) partial information decomposition and two implicitly directional interpretations used to intuitively motivate alternative component definitions. Drawing parallels with secret key agreement rates from information-theoretic cryptography, we demonstrate that these intuitions are mutually incompatible and suggest that this underlies the persistence of competing definitions and interpretations. Having highlighted this hitherto unacknowledged issue, we outline several possible solutions.
Context-Free Session Types for Applied Pi-Calculus
Venue: arXiv cs.LO 2018
Year: 2018

We present a binary session type system using context-free session types to a version of the applied pi-calculus of Abadi et. al. where only base terms, constants and channels can be sent. Session types resemble process terms from BPA and we use a version of bisimulation equivalence to characterize type equivalence. We present a quotiented type system defined on type equivalence classes for which type equivalence is built into the type system. Both type systems satisfy general soundness properties; this is established by an appeal to a generic session type system for psi-calculi.
Trace and Testing Metrics on Nondeterministic Probabilistic Processes
Venue: arXiv cs.LO 2018
Year: 2018

The combination of nondeterminism and probability in concurrent systems lead to the development of several interpretations of process behavior. If we restrict our attention to linear properties only, we can identify three main approaches to trace and testing semantics: the trace distributions, the trace-by-trace and the extremal probabilities approaches. In this paper, we propose novel notions of behavioral metrics that are based on the three classic approaches above, and that can be used to measure the disparities in the linear behavior of processes wrt trace and testing semantics. We study the properties of these metrics, like non-expansiveness, and we compare their expressive powers.
Novel Time Asynchronous NOMA schemes for Downlink Transmissions
Venue: arXiv cs.IT 2018
Year: 2018

In this work, we investigate the effect of time asynchrony in non-orthogonal multiple access (NOMA) schemes for downlink transmissions. First, we analyze the benefit of adding intentional timing offsets to the conventional power domain-NOMA (P-NOMA). This method which is called Asynchronous-Power Domain-NOMA (AP-NOMA) introduces artificial symbol-offsets between packets destined for different users. It reduces the mutual interference which results in enlarging the achievable rate-region of the conventional P-NOMA. Then, we propose a precoding scheme which fully exploits the degrees of freedom provided by the time asynchrony. We call this multiple access scheme T-NOMA which provides higher degrees of freedom for users compared to the conventional P-NOMA or even the modified AP-NOMA. T-NOMA adopts a precoding at the base station and a linear preprocessing scheme at the receiving user which decomposes the broadcast channel into parallel channels circumventing the need for Successive Interference Cancellation (SIC). The numerical results show that T-NOMA outperforms AP-NOMA and both outperform the conventional P-NOMA. We also compare the maximum sum-rate and fairness provided by these methods. Moreover, the impact of pulse shape and symbol offset on the performance of AP-NOMA and T-NOMA schemes are investigated.
Approach for Video Classification with Multi-label on YouTube-8M Dataset
Venue: arXiv cs.CV 2018
Year: 2018

Video traffic is increasing at a considerable rate due to the spread of personal media and advancements in media technology. Accordingly, there is a growing need for techniques to automatically classify moving images. This paper use NetVLAD and NetFV models and the Huber loss function for video classification problem and YouTube-8M dataset to verify the experiment. We tried various attempts according to the dataset and optimize hyperparameters, ultimately obtain a GAP score of 0.8668.
Generalized Capsule Networks with Trainable Routing Procedure
Venue: arXiv cs.CV 2018
Year: 2018

CapsNet (Capsule Network) was first proposed by~\citet{capsule} and later another version of CapsNet was proposed by~\citet{emrouting}. CapsNet has been proved effective in modeling spatial features with much fewer parameters. However, the routing procedures in both papers are not well incorporated into the whole training process. The optimal number of routing procedure is misery which has to be found manually. To overcome this disadvantages of current routing procedures in CapsNet, we embed the routing procedure into the optimization procedure with all other parameters in neural networks, namely, make coupling coefficients in the routing procedure become completely trainable. We call it Generalized CapsNet (G-CapsNet). We implement both "full-connected" version of G-CapsNet and "convolutional" version of G-CapsNet. G-CapsNet achieves a similar performance in the dataset MNIST as in the original papers. We also test two capsule packing method (cross feature maps or with feature maps) from previous convolutional layers and see no evident difference. Besides, we also explored possibility of stacking multiple capsule layers. The code is shared on \hyperlink{https://github.com/chenzhenhua986/CAFFE-CapsNet}{CAFFE-CapsNet}.
Exploring Biofeedback with a Tangible Interface Designed for Relaxation
Venue: arXiv cs.HC 2018
Year: 2018

Anxiety is a common health issue that can occur throughout one's existence. In this pilot study we explore an alternative technique to regulate it: biofeedback. The long-term objective is to offer an ecological device that could help people cope with anxiety, by exposing their inner state in a comprehensive manner. We propose a first iteration of this device, "Inner Flower", that uses heart rate to adapt a breathing guide to the user, and we investigate its efficiency and usability. Traditionally, such device requires user's full attention. We propose an ambient modality during which the device operates in the peripheral vision. Beside comparing "Ambient" and "Focus" conditions, we also compare the biofeedback with a sham feedback (fixed breathing guide). We found that the Focus group demonstrated higher relaxation and performance on a cognitive task (N-back). However, there was no noticeable effect of the Ambient feedback, and the biofeedback condition did not yield any significant difference when compared to the sham feedback. These results, while promising, highlight the pitfalls of any research related to biofeedback, where it is difficult to fully comprehend the underlying mechanisms of such technique.
Wide Activation for Efficient and Accurate Image Super-Resolution
Venue: arXiv cs.CV 2018
Year: 2018

In this report we demonstrate that with same parameters and computational budgets, models with wider features before ReLU activation have significantly better performance for single image super-resolution (SISR). The resulted SR residual network has a slim identity mapping pathway with wider (\(2\times\) to \(4\times\)) channels before activation in each residual block. To further widen activation (\(6\times\) to \(9\times\)) without computational overhead, we introduce linear low-rank convolution into SR networks and achieve even better accuracy-efficiency tradeoffs. In addition, compared with batch normalization or no normalization, we find training with weight normalization leads to better accuracy for deep super-resolution networks. Our proposed SR network \textit{WDSR} achieves better results on large-scale DIV2K image super-resolution benchmark in terms of PSNR with same or lower computational complexity. Based on WDSR, our method also won 1st places in NTIRE 2018 Challenge on Single Image Super-Resolution in all three realistic tracks. Experiments and ablation studies support the importance of wide activation for image super-resolution. Code is released at: https://github.com/JiahuiYu/wdsr_ntire2018
Don't Give Me the Details, Just the Summary! Topic-Aware Convolutional Neural Networks for Extreme Summarization
Venue: arXiv cs.CL 2018
Year: 2018

We introduce extreme summarization, a new single-document summarization task which does not favor extractive strategies and calls for an abstractive modeling approach. The idea is to create a short, one-sentence news summary answering the question "What is the article about?". We collect a real-world, large-scale dataset for this task by harvesting online articles from the British Broadcasting Corporation (BBC). We propose a novel abstractive model which is conditioned on the article's topics and based entirely on convolutional neural networks. We demonstrate experimentally that this architecture captures long-range dependencies in a document and recognizes pertinent content, outperforming an oracle extractive system and state-of-the-art abstractive approaches when evaluated automatically and by humans.
On the convergence of optimistic policy iteration for stochastic shortest path problem
Venue: arXiv cs.LG 2018
Year: 2018

In this paper, we prove some convergence results of a special case of optimistic policy iteration algorithm for stochastic shortest path problem. We consider both Monte Carlo and $TD(λ)$ methods for the policy evaluation step under the condition that the termination state will eventually be reached almost surely.
WiSeBE: Window-based Sentence Boundary Evaluation
Venue: arXiv cs.CL 2018
Year: 2018

Sentence Boundary Detection (SBD) has been a major research topic since Automatic Speech Recognition transcripts have been used for further Natural Language Processing tasks like Part of Speech Tagging, Question Answering or Automatic Summarization. But what about evaluation? Do standard evaluation metrics like precision, recall, F-score or classification error; and more important, evaluating an automatic system against a unique reference is enough to conclude how well a SBD system is performing given the final application of the transcript? In this paper we propose Window-based Sentence Boundary Evaluation (WiSeBE), a semi-supervised metric for evaluating Sentence Boundary Detection systems based on multi-reference (dis)agreement. We evaluate and compare the performance of different SBD systems over a set of Youtube transcripts using WiSeBE and standard metrics. This double evaluation gives an understanding of how WiSeBE is a more reliable metric for the SBD task.
Multi-operator spectrum sharing using matching game in small cells network
Venue: arXiv cs.GT 2018
Year: 2018

In this paper, we study a problem where multiple operators (OPs) need to share a common pool of spectrum with each other. Our objective is to maximize the social welfare, defined as the overall weighted sum rate of the OPs. The problem is decomposed into two parts: the first part is to allocate RBs to OPs, which we do so by extending the framework of many-to-one matching game with externalities. The second part is to allocate power of small cell base stations (SBSs) belonging to each OP, which is accomplished using reinforcement learning. Assuming that the SBSs associated with each OPs are spatially distributed according to Poisson point process (PPP), we show that pairwise stable matchings achieve local maximas of the social welfare function. We propose two algorithms to search for the stable matchings. Simulation results show that these algorithms are well behaved in terms of convergence and efficiency of the solutions.
Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation
Venue: arXiv cs.IT 2018
Year: 2018

We study the role of interaction in the Common Randomness Generation (CRG) and Secret Key Generation (SKG) problems. In the CRG problem, two players, Alice and Bob, respectively get samples $X_1,X_2,\dots$ and $Y_1,Y_2,\dots$ with the pairs $(X_1,Y_1)$, $(X_2, Y_2)$, $\dots$ being drawn independently from some known probability distribution $μ$. They wish to communicate so as to agree on $L$ bits of randomness. The SKG problem is the restriction of the CRG problem to the case where the key is required to be close to random even to an eavesdropper who can listen to their communication (but does not have access to the inputs of Alice and Bob). In this work, we study the relationship between the amount of communication and the number of rounds of interaction in both the CRG and the SKG problems. Specifically, we construct a family of distributions $μ= μ_{r, n,L}$, parametrized by integers $r$, $n$ and $L$, such that for every $r$ there exists a constant $b = b(r)$ for which CRG (respectively SKG) is feasible when $(X_i,Y_i) \sim μ_{r,n,L}$ with $r+1$ rounds of communication, each consisting of $O(\log n)$ bits, but when restricted to $r/2 - 3$ rounds of interaction, the total communication must exceed $Ω(n/\log^{b}(n))$ bits. Prior to our work no separations were known for $r \geq 2$.
Turning Cliques into Paths to Achieve Planarity
Venue: arXiv cs.DS 2018
Year: 2018

Motivated by hybrid graph representations, we introduce and study the following beyond-planarity problem, which we call $h$-Clique2Path Planarity: Given a graph $G$, whose vertices are partitioned into subsets of size at most $h$, each inducing a clique, remove edges from each clique so that the subgraph induced by each subset is a path, in such a way that the resulting subgraph of $G$ is planar. We study this problem when $G$ is a simple topological graph, and establish its complexity in relation to $k$-planarity. We prove that $h$-Clique2Path Planarity is NP-complete even when $h=4$ and $G$ is a simple $3$-plane graph, while it can be solved in linear time, for any $h$, when $G$ is $1$-plane.
Opportunistic Treating Interference as Noise
Venue: arXiv cs.IT 2018
Year: 2018

We consider a $K$-user interference network with $M$ states, where each transmitter has $M$ messages and over State $m$, Receiver $k$ wishes to decode the first $π_k(m) \in \{1,2,\cdots,M\}$ messages from its desired transmitter. This problem of channel with states models opportunistic communications, where more messages are sent for better channel states. The first message from each transmitter has the highest priority as it is required to be decoded regardless of the state of the receiver; the second message is opportunistically decoded if the state allows a receiver to decode 2 messages; and the $M$-th message has the lowest priority as it is decoded if and only if the receiver wishes to decode all $M$ messages. For this interference network with states, we show that if any possible combination of the channel states satisfies a condition under which power control and treating interference as noise (TIN) are sufficient to achieve the entire generalized degrees of freedom (GDoF) region of this channel state by itself, then a simple layered superposition encoding scheme with power control and a successive decoding scheme with TIN achieves the entire GDoF region of the network with $M$ states for all $KM$ messages.