OpenRaiser/Intern-Atlas huggingface dataset:
Instantons in self-organizing logic gates
Venue: arXiv cs.ET 2018
Year: 2018

Self-organizing logic is a recently-suggested framework that allows the solution of Boolean truth tables "in reverse," i.e., it is able to satisfy the logical proposition of gates regardless to which terminal(s) the truth value is assigned ("terminal-agnostic logic"). It can be realized if time non-locality (memory) is present. A practical realization of self-organizing logic gates (SOLGs) can be done by combining circuit elements with and without memory. By employing one such realization, we show, numerically, that SOLGs exploit elementary instantons to reach equilibrium points. Instantons are classical trajectories of the non-linear equations of motion describing SOLGs, and connect topologically distinct critical points in the phase space. By linear analysis at those points, we show that these instantons connect the initial critical point of the dynamics, with at least one unstable direction, directly to the final fixed point. We also show that the memory content of these gates only affects the relaxation time to reach the logically consistent solution. Finally, we demonstrate, by solving the corresponding stochastic differential equations, that since instantons connect critical points, noise and perturbations may change the instanton trajectory in the phase space, but not the initial and final critical points. Therefore, even for extremely large noise levels, the gates self-organize to the correct solution. Our work provides a physical understanding of, and can serve as an inspiration for, new models of bi-directional logic gates that are emerging as important tools in physics-inspired, unconventional computing.
Dynamic Graph Coloring
Venue: arXiv cs.DS 2018
Year: 2018

In this paper we study the number of vertex recolorings that an algorithm needs to perform in order to maintain a proper coloring of a graph under insertion and deletion of vertices and edges. We present two algorithms that achieve different trade-offs between the number of recolorings and the number of colors used. For any $d>0$, the first algorithm maintains a proper $O(\mathcal{C} d N^{1/d})$-coloring while recoloring at most $O(d)$ vertices per update, where $\mathcal{C}$ and $N$ are the maximum chromatic number and maximum number of vertices, respectively. The second algorithm reverses the trade-off, maintaining an $O(\mathcal{C} d)$-coloring with $O(d N^{1/d})$ recolorings per update. The two converge when $d = \log N$, maintaining an $O(\mathcal{C} \log N)$-coloring with $O(\log N)$ recolorings per update. We also present a lower bound, showing that any algorithm that maintains a $c$-coloring of a $2$-colorable graph on $N$ vertices must recolor at least $Ω(N^\frac{2}{c(c-1)})$ vertices per update, for any constant $c \geq 2$.
Interpretable Categorization of Heterogeneous Time Series Data
Venue: arXiv cs.LG 2018
Year: 2018

Understanding heterogeneous multivariate time series data is important in many applications ranging from smart homes to aviation. Learning models of heterogeneous multivariate time series that are also human-interpretable is challenging and not adequately addressed by the existing literature. We propose grammar-based decision trees (GBDTs) and an algorithm for learning them. GBDTs extend decision trees with a grammar framework. Logical expressions derived from a context-free grammar are used for branching in place of simple thresholds on attributes. The added expressivity enables support for a wide range of data types while retaining the interpretability of decision trees. In particular, when a grammar based on temporal logic is used, we show that GBDTs can be used for the interpretable classi cation of high-dimensional and heterogeneous time series data. Furthermore, we show how GBDTs can also be used for categorization, which is a combination of clustering and generating interpretable explanations for each cluster. We apply GBDTs to analyze the classic Australian Sign Language dataset as well as data on near mid-air collisions (NMACs). The NMAC data comes from aircraft simulations used in the development of the next-generation Airborne Collision Avoidance System (ACAS X).
A Compressive Sensing Approach to Community Detection with Applications
Venue: arXiv cs.IT 2018
Year: 2018

The community detection problem for graphs asks one to partition the n vertices V of a graph G into k communities, or clusters, such that there are many intracluster edges and few intercluster edges. Of course this is equivalent to finding a permutation matrix P such that, if A denotes the adjacency matrix of G, then PAP^T is approximately block diagonal. As there are k^n possible partitions of n vertices into k subsets, directly determining the optimal clustering is clearly infeasible. Instead one seeks to solve a more tractable approximation to the clustering problem. In this paper we reformulate the community detection problem via sparse solution of a linear system associated with the Laplacian of a graph G and then develop a two-stage approach based on a thresholding technique and a compressive sensing algorithm to find a sparse solution which corresponds to the community containing a vertex of interest in G. Crucially, our approach results in an algorithm which is able to find a single cluster of size n_0 in O(nlog(n)n_0) operations and all k clusters in fewer than O(n^2ln(n)) operations. This is a marked improvement over the classic spectral clustering algorithm, which is unable to find a single cluster at a time and takes approximately O(n^3) operations to find all k clusters. Moreover, we are able to provide robust guarantees of success for the case where G is drawn at random from the Stochastic Block Model, a popular model for graphs with clusters. Extensive numerical results are also provided, showing the efficacy of our algorithm on both synthetic and real-world data sets.
ICDAR2017 Competition on Reading Chinese Text in the Wild (RCTW-17)
Venue: arXiv cs.CV 2018
Year: 2018

Chinese is the most widely used language in the world. Algorithms that read Chinese text in natural images facilitate applications of various kinds. Despite the large potential value, datasets and competitions in the past primarily focus on English, which bares very different characteristics than Chinese. This report introduces RCTW, a new competition that focuses on Chinese text reading. The competition features a large-scale dataset with 12,263 annotated images. Two tasks, namely text localization and end-to-end recognition, are set up. The competition took place from January 20 to May 31, 2017. 23 valid submissions were received from 19 teams. This report includes dataset description, task definitions, evaluation protocols, and results summaries and analysis. Through this competition, we call for more future research on the Chinese text reading problem. The official website for the competition is http://rctw.vlrlab.net
RON-Gauss: Enhancing Utility in Non-Interactive Private Data Release
Venue: arXiv cs.CR 2018
Year: 2018

A key challenge facing the design of differential privacy in the non-interactive setting is to maintain the utility of the released data. To overcome this challenge, we utilize the Diaconis-Freedman-Meckes (DFM) effect, which states that most projections of high-dimensional data are nearly Gaussian. Hence, we propose the RON-Gauss model that leverages the novel combination of dimensionality reduction via random orthonormal (RON) projection and the Gaussian generative model for synthesizing differentially-private data. We analyze how RON-Gauss benefits from the DFM effect, and present multiple algorithms for a range of machine learning applications, including both unsupervised and supervised learning. Furthermore, we rigorously prove that (a) our algorithms satisfy the strong $ε$-differential privacy guarantee, and (b) RON projection can lower the level of perturbation required for differential privacy. Finally, we illustrate the effectiveness of RON-Gauss under three common machine learning applications -- clustering, classification, and regression -- on three large real-world datasets. Our empirical results show that (a) RON-Gauss outperforms previous approaches by up to an order of magnitude, and (b) loss in utility compared to the non-private real data is small. Thus, RON-Gauss can serve as a key enabler for real-world deployment of privacy-preserving data release.
A Recurrent Encoder-Decoder Approach with Skip-filtering Connections for Monaural Singing Voice Separation
Venue: arXiv cs.SD 2018
Year: 2018

The objective of deep learning methods based on encoder-decoder architectures for music source separation is to approximate either ideal time-frequency masks or spectral representations of the target music source(s). The spectral representations are then used to derive time-frequency masks. In this work we introduce a method to directly learn time-frequency masks from an observed mixture magnitude spectrum. We employ recurrent neural networks and train them using prior knowledge only for the magnitude spectrum of the target source. To assess the performance of the proposed method, we focus on the task of singing voice separation. The results from an objective evaluation show that our proposed method provides comparable results to deep learning based methods which operate over complicated signal representations. Compared to previous methods that approximate time-frequency masks, our method has increased performance of signal to distortion ratio by an average of 3.8 dB.
Anisotropic Radial Layout for Visualizing Centrality and Structure in Graphs
Venue: arXiv cs.CG 2018
Year: 2018

This paper presents a novel method for layout of undirected graphs, where nodes (vertices) are constrained to lie on a set of nested, simple, closed curves. Such a layout is useful to simultaneously display the structural centrality and vertex distance information for graphs in many domains, including social networks. Closed curves are a more general constraint than the previously proposed circles, and afford our method more flexibility to preserve vertex relationships compared to existing radial layout methods. The proposed approach modifies the multidimensional scaling (MDS) stress to include the estimation of a vertex depth or centrality field as well as a term that penalizes discord between structural centrality of vertices and their alignment with this carefully estimated field. We also propose a visualization strategy for the proposed layout and demonstrate its effectiveness using three social network datasets.
Edge Caching in Dense Heterogeneous Cellular Networks with Massive MIMO Aided Self-backhaul
Venue: arXiv cs.NI 2018
Year: 2018

This paper focuses on edge caching in dense heterogeneous cellular networks (HetNets), in which small base stations (SBSs) with limited cache size store the popular contents, and massive multiple-input multiple-output (MIMO) aided macro base stations provide wireless self-backhaul when SBSs require the non-cached contents. Our aim is to address the effects of cell load and hit probability on the successful content delivery (SCD), and present the minimum required base station density for avoiding the access overload in an arbitrary small cell and backhaul overload in an arbitrary macrocell. The massive MIMO backhaul achievable rate without downlink channel estimation is derived to calculate the backhaul time, and the latency is also evaluated in such networks. The analytical results confirm that hit probability needs to be appropriately selected, in order to achieve SCD. The interplay between cache size and SCD is explicitly quantified. It is theoretically demonstrated that when non-cached contents are requested, the average delay of the non-cached content delivery could be comparable to the cached content delivery with the help of massive MIMO aided self-backhaul, if the average access rate of cached content delivery is lower than that of self-backhauled content delivery. Simulation results are presented to validate our analysis.
NarrowBand IoT Data Transmission Procedures for Massive Machine Type Communications
Venue: arXiv cs.NI 2018
Year: 2018

Large-scale deployments of massive Machine Type Communications (mMTC) involve several challenges on cellular networks. To address the challenges of mMTC, or more generally, Internet of Things (IoT), the 3rd Generation Partnership Project has developed NarrowBand IoT (NB-IoT) as part of Release 13. NB-IoT is designed to provide better indoor coverage, support of a massive number of low-throughput devices, with relaxed delay requirements, and lower-energy consumption. NB-IoT reuses Long Term Evolution functionality with simplifications and optimizations. Particularly for small data transmissions, NB-IoT specifies two procedures to reduce the required signaling: one of them based on the Control Plane (CP), and the other on the User Plane (UP). In this work, we provide an overview of these procedures as well as an evaluation of their performance. The results of the energy consumption show both optimizations achieve a battery lifetime extension of more than 2 years for a large range in the considered cases, and up to 8 years for CP with good coverage. In terms of cell capacity relative to SR, CP achieves gains from 26% to 224%, and UP ranges from 36% to 165%. The comparison of CP and UP optimizations yields similar results, except for some specific configurations.
Do latent tree learning models identify meaningful structure in sentences?
Venue: arXiv cs.CL 2018
Year: 2018

Recent work on the problem of latent tree learning has made it possible to train neural networks that learn to both parse a sentence and use the resulting parse to interpret the sentence, all without exposure to ground-truth parse trees at training time. Surprisingly, these models often perform better at sentence understanding tasks than models that use parse trees from conventional parsers. This paper aims to investigate what these latent tree learning models learn. We replicate two such models in a shared codebase and find that (i) only one of these models outperforms conventional tree-structured models on sentence classification, (ii) its parsing strategies are not especially consistent across random restarts, (iii) the parses it produces tend to be shallower than standard Penn Treebank (PTB) parses, and (iv) they do not resemble those of PTB or any other semantic or syntactic formalism that the authors are aware of.
FLASH: Randomized Algorithms Accelerated over CPU-GPU for Ultra-High Dimensional Similarity Search
Venue: arXiv cs.DS 2018
Year: 2018

We present FLASH (\textbf{F}ast \textbf{L}SH \textbf{A}lgorithm for \textbf{S}imilarity search accelerated with \textbf{H}PC), a similarity search system for ultra-high dimensional datasets on a single machine, that does not require similarity computations and is tailored for high-performance computing platforms. By leveraging a LSH style randomized indexing procedure and combining it with several principled techniques, such as reservoir sampling, recent advances in one-pass minwise hashing, and count based estimations, we reduce the computational and parallelization costs of similarity search, while retaining sound theoretical guarantees. We evaluate FLASH on several real, high-dimensional datasets from different domains, including text, malicious URL, click-through prediction, social networks, etc. Our experiments shed new light on the difficulties associated with datasets having several million dimensions. Current state-of-the-art implementations either fail on the presented scale or are orders of magnitude slower than FLASH. FLASH is capable of computing an approximate k-NN graph, from scratch, over the full webspam dataset (1.3 billion nonzeros) in less than 10 seconds. Computing a full k-NN graph in less than 10 seconds on the webspam dataset, using brute-force ($n^2D$), will require at least 20 teraflops. We provide CPU and GPU implementations of FLASH for replicability of our results.
Balancing Information Exposure in Social Networks
Venue: arXiv cs.SI 2018
Year: 2018

Social media has brought a revolution on how people are consuming news. Beyond the undoubtedly large number of advantages brought by social-media platforms, a point of criticism has been the creation of echo chambers and filter bubbles, caused by social homophily and algorithmic personalization. In this paper we address the problem of balancing the information exposure in a social network. We assume that two opposing campaigns (or viewpoints) are present in the network, and that network nodes have different preferences towards these campaigns. Our goal is to find two sets of nodes to employ in the respective campaigns, so that the overall information exposure for the two campaigns is balanced. We formally define the problem, characterize its hardness, develop approximation algorithms, and present experimental evaluation results. Our model is inspired by the literature on influence maximization, but we offer significant novelties. First, balance of information exposure is modeled by a symmetric difference function, which is neither monotone nor submodular, and thus, not amenable to existing approaches. Second, while previous papers consider a setting with selfish agents and provide bounds on best response strategies (i.e., move of the last player), we consider a setting with a centralized agent and provide bounds for a global objective function.
Distributed Optimal Frequency Control Considering a Nonlinear Network-Preserving Model
Venue: arXiv cs.SY 2018
Year: 2018

This paper addresses the distributed optimal frequency control of power systems considering a network-preserving model with nonlinear power flows and excitation voltage dynamics. Salient features of the proposed distributed control strategy are fourfold: i) nonlinearity is considered to cope with large disturbances; ii) only a part of generators are controllable; iii) no load measurement is required; iv) communication connectivity is required only for the controllable generators. To this end, benefiting from the concept of 'virtual load demand', we first design the distributed controller for the controllable generators by leveraging the primal-dual decomposition technique. We then propose a method to estimate the virtual load demand of each controllable generator based on local frequencies. We derive incremental passivity conditions for the uncontrollable generators. Finally, we prove that the closed-loop system is asymptotically stable and its equilibrium attains the optimal solution to the associated economic dispatch problem. Simulations, including small and large-disturbance scenarios, are carried on the New England system, demonstrating the effectiveness of our design.
IAD: Interaction-Aware Diffusion Framework in Social Networks
Venue: arXiv cs.SI 2018
Year: 2018

In networks, multiple contagions, such as information and purchasing behaviors, may interact with each other as they spread simultaneously. However, most of the existing information diffusion models are built on the assumption that each individual contagion spreads independently, regardless of their interactions. Gaining insights into such interaction is crucial to understand the contagion adoption behaviors, and thus can make better predictions. In this paper, we study the contagion adoption behavior under a set of interactions, specifically, the interactions among users, contagions' contents and sentiments, which are learned from social network structures and texts. We then develop an effective and efficient interaction-aware diffusion (IAD) framework, incorporating these interactions into a unified model. We also present a generative process to distinguish user roles, a co-training method to determine contagions' categories and a new topic model to obtain topic-specific sentiments. Evaluation on large-scale Weibo dataset demonstrates that our proposal can learn how different users, contagion categories and sentiments interact with each other efficiently. With these interactions, we can make a more accurate prediction than the state-of-art baselines. Moreover, we can better understand how the interactions influence the propagation process and thus can suggest useful directions for information promotion or suppression in viral marketing.
Radial Line Fourier Descriptor for Historical Handwritten Text Representation
Venue: arXiv cs.CV 2018
Year: 2018

Automatic recognition of historical handwritten manuscripts is a daunting task due to paper degradation over time. Recognition-free retrieval or word spotting is popularly used for information retrieval and digitization of the historical handwritten documents. However, the performance of word spotting algorithms depends heavily on feature detection and representation methods. Although there exist popular feature descriptors such as Scale Invariant Feature Transform (SIFT) and Speeded Up Robust Features (SURF), the invariant properties of these descriptors amplify the noise in the degraded document images, rendering them more sensitive to noise and complex characteristics of historical manuscripts. Therefore, an efficient and relaxed feature descriptor is required as handwritten words across different documents are indeed similar, but not identical. This paper introduces a Radial Line Fourier (RLF) descriptor for handwritten word representation, with a short feature vector of 32 dimensions. A segmentation-free and training-free handwritten word spotting method is studied herein that relies on the proposed RLF descriptor, takes into account different keypoint representations and uses a simple preconditioner-based feature matching algorithm. The effectiveness of the RLF descriptor for segmentation-free handwritten word spotting is empirically evaluated on well-known historical handwritten datasets using standard evaluation measures.
Unreported links between trial registrations and published articles were identified using document similarity measures in a cross-sectional analysis of ClinicalTrials.gov
Venue: arXiv cs.IR 2018
Year: 2018

Objectives: Trial registries can be used to measure reporting biases and support systematic reviews but 45% of registrations do not provide a link to the article reporting on the trial. We evaluated the use of document similarity methods to identify unreported links between ClinicalTrials.gov and PubMed. Study Design and Setting: We extracted terms and concepts from a dataset of 72,469 ClinicalTrials.gov registrations and 276,307 PubMed articles, and tested methods for ranking articles across 16,005 reported links and 90 manually-identified unreported links. Performance was measured by the median rank of matching articles, and the proportion of unreported links that could be found by screening ranked candidate articles in order. Results: The best performing concept-based representation produced a median rank of 3 (IQR 1-21) for reported links and 3 (IQR 1-19) for the manually-identified unreported links, and term-based representations produced a median rank of 2 (1-20) for reported links and 2 (IQR 1-12) in unreported links. The matching article was ranked first for 40% of registrations, and screening 50 candidate articles per registration identified 86% of the unreported links. Conclusions: Leveraging the growth in the corpus of reported links between ClinicalTrials.gov and PubMed, we found that document similarity methods can assist in the identification of unreported links between trial registrations and corresponding articles.