OpenRaiser/Intern-Atlas huggingface dataset:
Sources of Change for Modern Knowledge Organization Systems
Venue: arXiv cs.DL 2016
Year: 2016

Knowledge Organization Systems (e.g. taxonomies and ontologies) continue to contribute benefits in the design of information systems by providing a shared conceptual underpinning for developers, users, and automated systems. However, the standard mechanisms for the management of KOSs changes are inadequate for systems built on top of thousands of data sources or with the involvement of hundreds of individuals. In this work, we review standard sources of change for KOSs (e.g. institutional shifts; standards cycles; cultural and political; distribution, etc) and then proceed to catalog new sources of change for KOSs ranging from massively cooperative development to always-on automated extraction systems. Finally, we reflect on what this means for the design and management of KOSs.
When is Noisy State Information at the Encoder as Useless as No Information or as Good as Noise-Free State?
Venue: arXiv cs.IT 2016
Year: 2016

For any binary-input channel with perfect state information at the decoder, if the mutual information between the noisy state observation at the encoder and the true channel state is below a positive threshold determined solely by the state distribution, then the capacity is the same as that with no encoder side information. A complementary phenomenon is revealed for the generalized probing capacity. Extensions beyond binary-input channels are developed.
Recurrent Neural Radio Anomaly Detection
Venue: arXiv cs.LG 2016
Year: 2016

We introduce a powerful recurrent neural network based method for novelty detection to the application of detecting radio anomalies. This approach holds promise in significantly increasing the ability of naive anomaly detection to detect small anomalies in highly complex complexity multi-user radio bands. We demonstrate the efficacy of this approach on a number of common real over the air radio communications bands of interest and quantify detection performance in terms of probability of detection an false alarm rates across a range of interference to band power ratios and compare to baseline methods.
Flood-Filling Networks
Venue: arXiv cs.CV 2016
Year: 2016

State-of-the-art image segmentation algorithms generally consist of at least two successive and distinct computations: a boundary detection process that uses local image information to classify image locations as boundaries between objects, followed by a pixel grouping step such as watershed or connected components that clusters pixels into segments. Prior work has varied the complexity and approach employed in these two steps, including the incorporation of multi-layer neural networks to perform boundary prediction, and the use of global optimizations during pixel clustering. We propose a unified and end-to-end trainable machine learning approach, flood-filling networks, in which a recurrent 3d convolutional network directly produces individual segments from a raw image. The proposed approach robustly segments images with an unknown and variable number of objects as well as highly variable object sizes. We demonstrate the approach on a challenging 3d image segmentation task, connectomic reconstruction from volume electron microscopy data, on which flood-filling neural networks substantially improve accuracy over other state-of-the-art methods. The proposed approach can replace complex multi-step segmentation pipelines with a single neural network that is learned end-to-end.
Inferring Coupling of Distributed Dynamical Systems via Transfer Entropy
Venue: arXiv cs.AI 2016
Year: 2016

In this work, we are interested in structure learning for a set of spatially distributed dynamical systems, where individual subsystems are coupled via latent variables and observed through a filter. We represent this model as a directed acyclic graph (DAG) that characterises the unidirectional coupling between subsystems. Standard approaches to structure learning are not applicable in this framework due to the hidden variables, however we can exploit the properties of certain dynamical systems to formulate exact methods based on state space reconstruction. We approach the problem by using reconstruction theorems to analytically derive a tractable expression for the KL-divergence of a candidate DAG from the observed dataset. We show this measure can be decomposed as a function of two information-theoretic measures, transfer entropy and stochastic interaction. We then present two mathematically robust scoring functions based on transfer entropy and statistical independence tests. These results support the previously held conjecture that transfer entropy can be used to infer effective connectivity in complex networks.
Towards High-Efficiency Cascading Outage Simulation and Analysis in Power Systems: A Sequential Importance Sampling Approach
Venue: arXiv cs.SY 2016
Year: 2016

This paper addresses how to improve the computational efficiency and estimation reliability in cascading outage analysis. We first formulate a cascading outage as a Markov chain with specific state space and transition probability by leveraging the Markov property of cascading outages. It provides a rigorous formulation that allows analytic investigation on cascading outages in the framework of standard mathematical statistics. Then we derive a sequential importance sampling (SIS) based simulation strategy for cascading outage simulation and blackout risk analysis with theoretical justification. Numerical experiments manifest that the proposed SIS strategy can significantly bring down the number of simulations and reduce the estimation variance of cascading outage analysis compared with the traditional Monte Carlo simulation strategy.
Combinatorial Prophet Inequalities
Venue: arXiv cs.DS 2016
Year: 2016

We introduce a novel framework of Prophet Inequalities for combinatorial valuation functions. For a (non-monotone) submodular objective function over an arbitrary matroid feasibility constraint, we give an $O(1)$-competitive algorithm. For a monotone subadditive objective function over an arbitrary downward-closed feasibility constraint, we give an $O(\log n \log^2 r)$-competitive algorithm (where $r$ is the cardinality of the largest feasible subset). Inspired by the proof of our subadditive prophet inequality, we also obtain an $O(\log n \cdot \log^2 r)$-competitive algorithm for the Secretary Problem with a monotone subadditive objective function subject to an arbitrary downward-closed feasibility constraint. Even for the special case of a cardinality feasibility constraint, our algorithm circumvents an $Ω(\sqrt{n})$ lower bound by Bateni, Hajiaghayi, and Zadimoghaddam \cite{BHZ13-submodular-secretary_original} in a restricted query model. En route to our submodular prophet inequality, we prove a technical result of independent interest: we show a variant of the Correlation Gap Lemma for non-monotone submodular functions.
Inter-WBANs Interference Mitigation Using Orthogonal Walsh Hadamard Codes
Venue: arXiv cs.NI 2016
Year: 2016

A Wireless Body Area Network (WBAN) provides health care services. The performance and utility of WBANs can be degraded due to interference. In this paper, our contribution for co-channel interference mitigation among coexisting WBANs is threefold. First, we propose a distributed orthogonal code allocation scheme, namely, OCAIM, where, each WBAN generates sensor interference lists (SILs), and then all sensors belonging to these lists are allocated orthogonal codes. Secondly, we propose a distributed time reference correlation scheme, namely, DTRC, that is used as a building block of OCAIM. DTRC enables eachWBAN to generate a virtual time-based pattern to relate the different superframes. Accordingly, DTRC provides each WBAN with the knowledge about, 1) which superframes and, 2) which time-slots of those superframes interfere with the time-slots within its superframe. Thirdly, we further analyze the success and collision probabilities of frames transmissions when the number of coexisting WBANs grows. The simulation results demonstrate that OCAIM outperforms other competing schemes in terms of interference mitigation and power savings.
Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs
Venue: arXiv cs.DS 2016
Year: 2016

In this paper we introduce a notion of spectral approximation for directed graphs. While there are many potential ways one might define approximation for directed graphs, most of them are too strong to allow sparse approximations in general. In contrast, we prove that for our notion of approximation, such sparsifiers do exist, and we show how to compute them in almost linear time. Using this notion of approximation, we provide a general framework for solving asymmetric linear systems that is broadly inspired by the work of [Peng-Spielman, STOC`14]. Applying this framework in conjunction with our sparsification algorithm, we obtain an almost linear time algorithm for solving directed Laplacian systems associated with Eulerian Graphs. Using this solver in the recent framework of [Cohen-Kelner-Peebles-Peng-Sidford-Vladu, FOCS`16], we obtain almost linear time algorithms for solving a directed Laplacian linear system, computing the stationary distribution of a Markov chain, computing expected commute times in a directed graph, and more. For each of these problems, our algorithms improves the previous best running times of $O((nm^{3/4} + n^{2/3} m) \log^{O(1)} (n κε^{-1}))$ to $O((m + n2^{O(\sqrt{\log{n}\log\log{n}})}) \log^{O(1)} (n κε^{-1}))$ where $n$ is the number of vertices in the graph, $m$ is the number of edges, $κ$ is a natural condition number associated with the problem, and $ε$ is the desired accuracy. We hope these results open the door for further studies into directed spectral graph theory, and will serve as a stepping stone for designing a new generation of fast algorithms for directed graphs.
An All-In-One Convolutional Neural Network for Face Analysis
Venue: arXiv cs.CV 2016
Year: 2016

We present a multi-purpose algorithm for simultaneous face detection, face alignment, pose estimation, gender recognition, smile detection, age estimation and face recognition using a single deep convolutional neural network (CNN). The proposed method employs a multi-task learning framework that regularizes the shared parameters of CNN and builds a synergy among different domains and tasks. Extensive experiments show that the network has a better understanding of face and achieves state-of-the-art result for most of these tasks.
Quantile Reinforcement Learning
Venue: arXiv cs.LG 2016
Year: 2016

In reinforcement learning, the standard criterion to evaluate policies in a state is the expectation of (discounted) sum of rewards. However, this criterion may not always be suitable, we consider an alternative criterion based on the notion of quantiles. In the case of episodic reinforcement learning problems, we propose an algorithm based on stochastic approximation with two timescales. We evaluate our proposition on a simple model of the TV show, Who wants to be a millionaire.
Designing Sparse Reliable Pose-Graph SLAM: A Graph-Theoretic Approach
Venue: arXiv cs.RO 2016
Year: 2016

In this paper, we aim to design sparse D-optimal (determinantoptimal) pose-graph SLAM problems through the synthesis of sparse graphs with the maximum weighted number of spanning trees. Characterizing graphs with the maximum number of spanning trees is an open problem in general. To tackle this problem, several new theoretical results are established in this paper, including the monotone log-submodularity of the weighted number of spanning trees. By exploiting these structures, we design a complementary pair of near-optimal efficient approximation algorithms with provable guarantees. Our theoretical results are validated using random graphs and a publicly available pose-graph SLAM dataset.
Recent Advances in Transient Imaging: A Computer Graphics and Vision Perspective
Venue: arXiv cs.CV 2016
Year: 2016

Transient imaging has recently made a huge impact in the computer graphics and computer vision fields. By capturing, reconstructing, or simulating light transport at extreme temporal resolutions, researchers have proposed novel techniques to show movies of light in motion, see around corners, detect objects in highly-scattering media, or infer material properties from a distance, to name a few. The key idea is to leverage the wealth of information in the temporal domain at the pico or nanosecond resolution, information usually lost during the capture-time temporal integration. This paper presents recent advances in this field of transient imaging from a graphics and vision perspective, including capture techniques, analysis, applications and simulation.
An empirical study for Vietnamese dependency parsing
Venue: arXiv cs.CL 2016
Year: 2016

This paper presents an empirical comparison of different dependency parsers for Vietnamese, which has some unusual characteristics such as copula drop and verb serialization. Experimental results show that the neural network-based parsers perform significantly better than the traditional parsers. We report the highest parsing scores published to date for Vietnamese with the labeled attachment score (LAS) at 73.53% and the unlabeled attachment score (UAS) at 80.66%.
A-Ward_p\b{eta}: Effective hierarchical clustering using the Minkowski metric and a fast k -means initialisation
Venue: arXiv cs.LG 2016
Year: 2016

In this paper we make two novel contributions to hierarchical clustering. First, we introduce an anomalous pattern initialisation method for hierarchical clustering algorithms, called A-Ward, capable of substantially reducing the time they take to converge. This method generates an initial partition with a sufficiently large number of clusters. This allows the cluster merging process to start from this partition rather than from a trivial partition composed solely of singletons. Our second contribution is an extension of the Ward and Ward p algorithms to the situation where the feature weight exponent can differ from the exponent of the Minkowski distance. This new method, called A-Ward p\b{eta} , is able to generate a much wider variety of clustering solutions. We also demonstrate that its parameters can be estimated reasonably well by using a cluster validity index. We perform numerous experiments using data sets with two types of noise, insertion of noise features and blurring within-cluster values of some features. These experiments allow us to conclude: (i) our anomalous pattern initialisation method does indeed reduce the time a hierarchical clustering algorithm takes to complete, without negatively impacting its cluster recovery ability; (ii) A-Ward p\b{eta} provides better cluster recovery than both Ward and Ward p.
Generating Families of Practical Fast Matrix Multiplication Algorithms
Venue: arXiv cs.MS 2016
Year: 2016

Matrix multiplication (GEMM) is a core operation to numerous scientific applications. Traditional implementations of Strassen-like fast matrix multiplication (FMM) algorithms often do not perform well except for very large matrix sizes, due to the increased cost of memory movement, which is particularly noticeable for non-square matrices. Such implementations also require considerable workspace and modifications to the standard BLAS interface. We propose a code generator framework to automatically implement a large family of FMM algorithms suitable for multiplications of arbitrary matrix sizes and shapes. By representing FMM with a triple of matrices [U,V,W] that capture the linear combinations of submatrices that are formed, we can use the Kronecker product to define a multi-level representation of Strassen-like algorithms. Incorporating the matrix additions that must be performed for Strassen-like algorithms into the inherent packing and micro-kernel operations inside GEMM avoids extra workspace and reduces the cost of memory movement. Adopting the same loop structures as high-performance GEMM implementations allows parallelization of all FMM algorithms with simple but efficient data parallelism without the overhead of task parallelism. We present a simple performance model for general FMM algorithms and compare actual performance of 20+ FMM algorithms to modeled predictions. Our implementations demonstrate a performance benefit over conventional GEMM on single core and multi-core systems. This study shows that Strassen-like fast matrix multiplication can be incorporated into libraries for practical use.
Pilot Distribution Optimization and Power Control in Multi-Cellular Large Scale MIMO Systems
Venue: arXiv cs.IT 2016
Year: 2016

Massive MIMO communication systems have been identified as one of the most prominent technologies of the next generation wireless standards, such as 5G, due to the large gains in energy and spectral efficiency that can be achieved. In the asymptotic condition of infinite number of antennas at the base station (BS), the performance bottleneck of these systems is due to the pilot contamination effect, i.e., the directional interference arising from users in adjacent cells that reuse the same set of orthogonal training sequences, and thus the interference seen by each user is determined by the pilot sequence assigned to him. We show in this paper that the system performance can be improved by appropriately assigning the pilot sequences to the users, in the so-called pilot allocation scheme. Depending on the optimization metric adopted, it is more advantageous to a user with certain long- term fading coefficient be assigned to a specific pilot sequence, whose interference can be completely estimated in advance by the BS by only knowing the long term fading coefficients of users in adjacent cells. Besides, if the objective is to maximize the number of users with a target quality of service, we have shown that the pilot allocation schemes can be combined with power control algorithms, resulting in much more improvements for the system. For unitary frequency reuse factor, we have found that the data throughput provided for 95% of the users increases when applying power control algorithm from 134kbps to 1.461Mbps with no pilot allocation, while this performance gain provided by power control changes from 793kbps to 6.743Mbps when pilot allocation is employed. If the reuse factor increases to 3, a 95%-likely data throughput of 17.310Mbps can be assured when pilot allocation and power control are suitably combined.
Can Big Media Data Revolutionarize Gun Violence Prevention?
Venue: arXiv cs.CY 2016
Year: 2016

The scientific method drives improvements in public health, but a strategy of obstructionism has impeded scientists from gathering even a minimal amount of information to address America's gun violence epidemic. We argue that in spite of a lack of federal investment, large amounts of publicly available data offer scientists an opportunity to measure a range of firearm-related behaviors. Given the diversity of available data - including news coverage, social media, web forums, online advertisements, and Internet searches (to name a few) - there are ample opportunities for scientists to study everything from trends in particular types of gun violence to gun-related behaviors (such as purchases and safety practices) to public understanding of and sentiment towards various gun violence reduction measures. Science has been sidelined in the gun violence debate for too long. Scientists must tap the big media data stream and help resolve this crisis.
PrivLogit: Efficient Privacy-preserving Logistic Regression by Tailoring Numerical Optimizers
Venue: arXiv cs.LG 2016
Year: 2016

Safeguarding privacy in machine learning is highly desirable, especially in collaborative studies across many organizations. Privacy-preserving distributed machine learning (based on cryptography) is popular to solve the problem. However, existing cryptographic protocols still incur excess computational overhead. Here, we make a novel observation that this is partially due to naive adoption of mainstream numerical optimization (e.g., Newton method) and failing to tailor for secure computing. This work presents a contrasting perspective: customizing numerical optimization specifically for secure settings. We propose a seemingly less-favorable optimization method that can in fact significantly accelerate privacy-preserving logistic regression. Leveraging this new method, we propose two new secure protocols for conducting logistic regression in a privacy-preserving and distributed manner. Extensive theoretical and empirical evaluations prove the competitive performance of our two secure proposals while without compromising accuracy or privacy: with speedup up to 2.3x and 8.1x, respectively, over state-of-the-art; and even faster as data scales up. Such drastic speedup is on top of and in addition to performance improvements from existing (and future) state-of-the-art cryptography. Our work provides a new way towards efficient and practical privacy-preserving logistic regression for large-scale studies which are common for modern science.
Generalized Topic Modeling
Venue: arXiv cs.LG 2016
Year: 2016

Recently there has been significant activity in developing algorithms with provable guarantees for topic modeling. In standard topic models, a topic (such as sports, business, or politics) is viewed as a probability distribution $\vec a_i$ over words, and a document is generated by first selecting a mixture $\vec w$ over topics, and then generating words i.i.d. from the associated mixture $A{\vec w}$. Given a large collection of such documents, the goal is to recover the topic vectors and then to correctly classify new documents according to their topic mixture. In this work we consider a broad generalization of this framework in which words are no longer assumed to be drawn i.i.d. and instead a topic is a complex distribution over sequences of paragraphs. Since one could not hope to even represent such a distribution in general (even if paragraphs are given using some natural feature representation), we aim instead to directly learn a document classifier. That is, we aim to learn a predictor that given a new document, accurately predicts its topic mixture, without learning the distributions explicitly. We present several natural conditions under which one can do this efficiently and discuss issues such as noise tolerance and sample complexity in this model. More generally, our model can be viewed as a generalization of the multi-view or co-training setting in machine learning.
Research on Life Characteristics of Internet Based on Network Motifs
Venue: arXiv cs.NI 2016
Year: 2016

From biosystem to complex system,the study of life is always an important area. Inspired by hyper-cycle theory about the evolution of non-life system, we study the metabolism, self-replication and mutation behavior in the Internet based on node entity, connection relationship and function subgraph--motif--of network topology. Firstly a framework of complex network evolution is proposed to analyze the birth and death phenomena of Internet topology from January 1998 to August 2013. Then we find the Internet metabolism behavior from angle of node, motif to global topology, i.e. one born node is only added into Internet, subsequently takes part in the local reconstruction activities. Meanwhile there are nodes' and motifs' death. In process of the local reconstruction, although the Internet system replicates motifs repeatedly by adding or removing actions, the system characteristics and global structure are not destroyed. Statistics about the motif M3 which is a full connectivity subgraph shows that the process of its metabolism is fluctuation that causes mutation of Internet. Furthermore we find that mutation is instinctive reaction of Internet when it's influenced from inside or outside environment, such as Internet bubble, social network rising and finance crisis. The behaviors of metabolism, self-replication and mutation of Internet indicate its life characteristic as a complex artificial life. And our work will inspire people to study the life-like phenomena of other complex systems from angle of topology structure.