OpenRaiser/Intern-Atlas huggingface dataset:
Bolt-on Differential Privacy for Scalable Stochastic Gradient Descent-based Analytics
Venue: arXiv cs.LG 2017
Year: 2017

While significant progress has been made separately on analytics systems for scalable stochastic gradient descent (SGD) and private SGD, none of the major scalable analytics frameworks have incorporated differentially private SGD. There are two inter-related issues for this disconnect between research and practice: (1) low model accuracy due to added noise to guarantee privacy, and (2) high development and runtime overhead of the private algorithms. This paper takes a first step to remedy this disconnect and proposes a private SGD algorithm to address \emph{both} issues in an integrated manner. In contrast to the white-box approach adopted by previous work, we revisit and use the classical technique of {\em output perturbation} to devise a novel "bolt-on" approach to private SGD. While our approach trivially addresses (2), it makes (1) even more challenging. We address this challenge by providing a novel analysis of the $L_2$-sensitivity of SGD, which allows, under the same privacy guarantees, better convergence of SGD when only a constant number of passes can be made over the data. We integrate our algorithm, as well as other state-of-the-art differentially private SGD, into Bismarck, a popular scalable SGD-based analytics system on top of an RDBMS. Extensive experiments show that our algorithm can be easily integrated, incurs virtually no overhead, scales well, and most importantly, yields substantially better (up to 4X) test accuracy than the state-of-the-art algorithms on many real datasets.
The Learning and Prediction of Application-level Traffic Data in Cellular Networks
Venue: arXiv cs.NI 2017
Year: 2017

Traffic learning and prediction is at the heart of the evaluation of the performance of telecommunications networks and attracts a lot of attention in wired broadband networks. Now, benefiting from the big data in cellular networks, it becomes possible to make the analyses one step further into the application level. In this paper, we firstly collect a significant amount of application-level traffic data from cellular network operators. Afterwards, with the aid of the traffic "big data", we make a comprehensive study over the modeling and prediction framework of cellular network traffic. Our results solidly demonstrate that there universally exist some traffic statistical modeling characteristics, including ALPHA-stable modeled property in the temporal domain and the sparsity in the spatial domain. Meanwhile, the results also demonstrate the distinctions originated from the uniqueness of different service types of applications. Furthermore, we propose a new traffic prediction framework to encompass and explore these aforementioned characteristics and then develop a dictionary learning-based alternating direction method to solve it. Besides, we validate the prediction accuracy improvement and the robustness of the proposed framework through extensive simulation results.
No Need to Pay Attention: Simple Recurrent Neural Networks Work! (for Answering "Simple" Questions)
Venue: arXiv cs.CL 2017
Year: 2017

First-order factoid question answering assumes that the question can be answered by a single fact in a knowledge base (KB). While this does not seem like a challenging task, many recent attempts that apply either complex linguistic reasoning or deep neural networks achieve 65%-76% accuracy on benchmark sets. Our approach formulates the task as two machine learning problems: detecting the entities in the question, and classifying the question as one of the relation types in the KB. We train a recurrent neural network to solve each problem. On the SimpleQuestions dataset, our approach yields substantial improvements over previously published results --- even neural networks based on much more complex architectures. The simplicity of our approach also has practical advantages, such as efficiency and modularity, that are valuable especially in an industry setting. In fact, we present a preliminary analysis of the performance of our model on real queries from Comcast's X1 entertainment platform with millions of users every day.
LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs
Venue: arXiv cs.DS 2017
Year: 2017

We give a general approach for solving optimization problems on noisy minor free graphs, where a δ-fraction of edges and vertices are adversarially corrupted. The noisy setting was first considered by Magen and Moharrami and they gave a (1 + δ)-estimation algorithm for the independent set problem. Later, Chan and Har-Peled designed a local search algorithm that finds a (1 + O(δ))-approximate independent set. However, nothing was known regarding other problems in the noisy setting. Our main contribution is a general LP-based framework that yields a (1 + O(δlog m log log m))-approximation algorithm for noisy MAX-k-CSPs on m clauses.
Universal, Unsupervised (Rule-Based), Uncovered Sentiment Analysis
Venue: arXiv cs.CL 2017
Year: 2017

We present a novel unsupervised approach for multilingual sentiment analysis driven by compositional syntax-based rules. On the one hand, we exploit some of the main advantages of unsupervised algorithms: (1) the interpretability of their output, in contrast with most supervised models, which behave as a black box and (2) their robustness across different corpora and domains. On the other hand, by introducing the concept of compositional operations and exploiting syntactic information in the form of universal dependencies, we tackle one of their main drawbacks: their rigidity on data that are structured differently depending on the language concerned. Experiments show an improvement both over existing unsupervised methods, and over state-of-the-art supervised models when evaluating outside their corpus of origin. Experiments also show how the same compositional operations can be shared across languages. The system is available at http://www.grupolys.org/software/UUUSA/
Yet Another Proof of the Entropy Power Inequality
Venue: arXiv cs.IT 2017
Year: 2017

Yet another simple proof of the entropy power inequality is given, which avoids both the integration over a path of Gaussian perturbation and the use of Young's inequality with sharp constant or Rényi entropies. The proof is based on a simple change of variables, is formally identical in one and several dimensions, and easily settles the equality case.
On Capacity of the Writing onto Fast Fading Dirt Channel
Venue: arXiv cs.IT 2017
Year: 2017

The "Writing onto Fast Fading Dirt" (WFFD) channel is investigated to study the effects of partial channel knowledge on the capacity of the "writing on dirty paper" channel. The WFFD channel is the Gel'fand-Pinsker channel in which the output is obtained as the sum of the input, white Gaussian noise and a fading-times-state term. The fading-times-state term is equal to the element-wise product of the channel state sequence, known only at the transmitter, and a fast fading process, known only at the receiver. We consider the case of Gaussian distributed channel states and derive an approximate characterization of capacity for different classes of fading distributions, both continuous and discrete. In particular, we prove that if the fading distribution concentrates in a sufficiently small interval, then capacity is approximately equal to the AWGN capacity times the probability of this interval. We also show that there exists a class of fading distributions for which having the transmitter treat the fading-times-state term as additional noise closely approaches capacity. Although a closed-form expression of the capacity of the general WFFD channel remains unknown, our results show that the presence of fading can severely reduce the usefulness of channel state knowledge at the transmitter.
Inversion-Based Output Tracking and Unknown Input Reconstruction of Square Discrete-Time Linear Systems
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, we propose a framework for output tracking control of both minimum phase (MP) and non-minimum phase (NMP) systems {as well as systems with transmission zeros on the unit circle}. Towards this end, we first address the problem of unknown state and input reconstruction of non-minimum phase systems. An unknown input observer (UIO) is designed that accurately reconstructs the minimum phase states of the system. The reconstructed minimum phase states serve as inputs to an FIR filter for a delayed non-minimum phase state reconstruction. It is shown that a quantified upper bound of the reconstruction error exponentially decreases as the estimation delay is increased. Therefore, an almost perfect reconstruction can be achieved by selecting the delay to be sufficiently large. Our proposed inversion scheme is then applied to solve the output-tracking control problem. {We have also proposed a methodology to handle the output tracking problem of systems that have transmission zeros on the unit circle in addition to MP and NMP zeros.} Simulation case studies are also presented that demonstrate the merits and capabilities of our proposed methodologies.
Scalable motif-aware graph clustering
Venue: arXiv cs.DS 2017
Year: 2017

We develop new methods based on graph motifs for graph clustering, allowing more efficient detection of communities within networks. We focus on triangles within graphs, but our techniques extend to other clique motifs as well. Our intuition, which has been suggested but not formalized similarly in previous works, is that triangles are a better signature of community than edges. We therefore generalize the notion of conductance for a graph to {\em triangle conductance}, where the edges are weighted according to the number of triangles containing the edge. This methodology allows us to develop variations of several existing clustering techniques, including spectral clustering, that minimize triangles split by the cluster instead of edges cut by the cluster. We provide theoretical results in a planted partition model to demonstrate the potential for triangle conductance in clustering problems. We then show experimentally the effectiveness of our methods to multiple applications in machine learning and graph mining.
Scalable Semi-supervised Learning with Graph-based Kernel Machine
Venue: arXiv cs.LG 2017
Year: 2017

Acquiring labels are often costly, whereas unlabeled data are usually easy to obtain in modern machine learning applications. Semi-supervised learning provides a principled machine learning framework to address such situations, and has been applied successfully in many real-word applications and industries. Nonetheless, most of existing semi-supervised learning methods encounter two serious limitations when applied to modern and large-scale datasets: computational burden and memory usage demand. To this end, we present in this paper the Graph-based semi-supervised Kernel Machine (GKM), a method that leverages the generalization ability of kernel-based method with the geometrical and distributive information formulated through a spectral graph induced from data for semi-supervised learning purpose. Our proposed GKM can be solved directly in the primal form using the Stochastic Gradient Descent method with the ideal convergence rate $O(\frac{1}{T})$. Besides, our formulation is suitable for a wide spectrum of important loss functions in the literature of machine learning (e.g., Hinge, smooth Hinge, Logistic, L1, and ε-insensitive) and smoothness functions (i.e., $l_p(t) = |t|^p$ with $p\ge1$). We further show that the well-known Laplacian Support Vector Machine is a special case of our formulation. We validate our proposed method on several benchmark datasets to demonstrate that GKM is appropriate for the large-scale datasets since it is optimal in memory usage and yields superior classification accuracy whilst simultaneously achieving a significant computation speed-up in comparison with the state-of-the-art baselines.
A segmental framework for fully-unsupervised large-vocabulary speech recognition
Venue: arXiv cs.CL 2017
Year: 2017

Zero-resource speech technology is a growing research area that aims to develop methods for speech processing in the absence of transcriptions, lexicons, or language modelling text. Early term discovery systems focused on identifying isolated recurring patterns in a corpus, while more recent full-coverage systems attempt to completely segment and cluster the audio into word-like units---effectively performing unsupervised speech recognition. This article presents the first attempt we are aware of to apply such a system to large-vocabulary multi-speaker data. Our system uses a Bayesian modelling framework with segmental word representations: each word segment is represented as a fixed-dimensional acoustic embedding obtained by mapping the sequence of feature frames to a single embedding vector. We compare our system on English and Xitsonga datasets to state-of-the-art baselines, using a variety of measures including word error rate (obtained by mapping the unsupervised output to ground truth transcriptions). Very high word error rates are reported---in the order of 70--80% for speaker-dependent and 80--95% for speaker-independent systems---highlighting the difficulty of this task. Nevertheless, in terms of cluster quality and word segmentation metrics, we show that by imposing a consistent top-down segmentation while also using bottom-up knowledge from detected syllable boundaries, both single-speaker and multi-speaker versions of our system outperform a purely bottom-up single-speaker syllable-based approach. We also show that the discovered clusters can be made less speaker- and gender-specific by using an unsupervised autoencoder-like feature extractor to learn better frame-level features (prior to embedding). Our system's discovered clusters are still less pure than those of unsupervised term discovery systems, but provide far greater coverage.
Using Word Embeddings in Twitter Election Classification
Venue: arXiv cs.IR 2017
Year: 2017

Word embeddings and convolutional neural networks (CNN) have attracted extensive attention in various classification tasks for Twitter, e.g. sentiment classification. However, the effect of the configuration used to train and generate the word embeddings on the classification performance has not been studied in the existing literature. In this paper, using a Twitter election classification task that aims to detect election-related tweets, we investigate the impact of the background dataset used to train the embedding models, the context window size and the dimensionality of word embeddings on the classification performance. By comparing the classification results of two word embedding models, which are trained using different background corpora (e.g. Wikipedia articles and Twitter microposts), we show that the background data type should align with the Twitter classification dataset to achieve a better performance. Moreover, by evaluating the results of word embeddings models trained using various context window sizes and dimensionalities, we found that large context window and dimension sizes are preferable to improve the performance. Our experimental results also show that using word embeddings and CNN leads to statistically significant improvements over various baselines such as random, SVM with TF-IDF and SVM with word embeddings.
State power and elite autonomy in a networked civil society: The board interlocking of Chinese non-profits
Venue: arXiv cs.SI 2017
Year: 2017

In response to failures of central planning, the Chinese government has experimented not only with free-market trade zones, but with allowing non-profit foundations to operate in a decentralized fashion. A network study shows how these foundations have connected together by sharing board members, in a structural parallel to what is seen in corporations in the United States and Europe. This board interlocking leads to the emergence of an elite group with privileged network positions. While the presence of government officials on non-profit boards is widespread, government officials are much less common in a subgroup of foundations that control just over half of all revenue in the network. This subgroup, associated with business elites, not only enjoys higher levels of within-elite links, but even preferentially excludes government officials from the NGOs with higher degree. The emergence of this structurally autonomous sphere is associated with major political and social events in the state-society relationship. Cluster analysis reveals multiple internal components within this sphere that share similar levels of network influence. Rather than a core-periphery structure centered around government officials, the Chinese non-profit world appears to be a multipolar one of distinct elite groups, many of which achieve high levels of independence from direct government control.
Diversified Visual Attention Networks for Fine-Grained Object Classification
Venue: arXiv cs.CV 2017
Year: 2017

Fine-grained object classification is a challenging task due to the subtle inter-class difference and large intra-class variation. Recently, visual attention models have been applied to automatically localize the discriminative regions of an image for better capturing critical difference and demonstrated promising performance. However, without consideration of the diversity in attention process, most of existing attention models perform poorly in classifying fine-grained objects. In this paper, we propose a diversified visual attention network (DVAN) to address the problems of fine-grained object classification, which substan- tially relieves the dependency on strongly-supervised information for learning to localize discriminative regions compared with attentionless models. More importantly, DVAN explicitly pursues the diversity of attention and is able to gather discriminative information to the maximal extent. Multiple attention canvases are generated to extract convolutional features for attention. An LSTM recurrent unit is employed to learn the attentiveness and discrimination of attention canvases. The proposed DVAN has the ability to attend the object from coarse to fine granularity, and a dynamic internal representation for classification is built up by incrementally combining the information from different locations and scales of the image. Extensive experiments con- ducted on CUB-2011, Stanford Dogs and Stanford Cars datasets have demonstrated that the proposed diversified visual attention networks achieve competitive performance compared to the state- of-the-art approaches, without using any prior knowledge, user interaction or external resource in training or testing.
Efficiently Inferring Pairwise Subtree Prune-and-Regraft Adjacencies between Phylogenetic Trees
Venue: arXiv cs.DS 2017
Year: 2017

We develop a time-optimal $O(mn^2)$-time algorithm to construct the subtree prune-regraft (SPR) graph on a collection of m phylogenetic trees with n leaves. This improves on the previous bound of $O(mn^3)$. Such graphs are used to better understand the behaviour of phylogenetic methods and recommend parameter choices and diagnostic criteria. The limiting factor in these analyses has been the difficulty in constructing such graphs for large numbers of trees. We also develop the first efficient algorithms for constructing the nearest-neighbor interchange (NNI) and tree bisection-and-reconnection (TBR) graphs
A Crowdsourcing Approach To Collecting Tutorial Videos -- Toward Personalized Learning-at-Scale
Venue: arXiv cs.HC 2017
Year: 2017

We investigated the feasibility of crowdsourcing full-fledged tutorial videos from ordinary people on the Web on how to solve math problems related to logarithms. This kind of approach (a form of learnersourcing) to efficiently collecting tutorial videos and other learning resources could be useful for realizing personalized learning-at-scale, whereby students receive specific learning resources -- drawn from a large and diverse set -- that are tailored to their individual and time-varying needs. Results of our study, in which we collected 399 videos from 66 unique "teachers" on Mechanical Turk, suggest that (1) approximately 100 videos -- over $80\%$ of which are mathematically fully correct -- can be crowdsourced per week for \$5/video; (2) the crowdsourced videos exhibit significant diversity in terms of language style, presentation media, and pedagogical approach; (3) the average learning gains (posttest minus pretest score) associated with watching the videos was stat.~sig.~higher than for a control video ($0.105$ versus $0.045$); and (4) the average learning gains ($0.1416$) from watching the best tested crowdsourced videos was comparable to the learning gains ($0.1506$) from watching a popular Khan Academy video on logarithms.
Neighborhood Features Help Detecting Non-Technical Losses in Big Data Sets
Venue: arXiv cs.LG 2017
Year: 2017

Electricity theft is a major problem around the world in both developed and developing countries and may range up to 40% of the total electricity distributed. More generally, electricity theft belongs to non-technical losses (NTL), which are losses that occur during the distribution of electricity in power grids. In this paper, we build features from the neighborhood of customers. We first split the area in which the customers are located into grids of different sizes. For each grid cell we then compute the proportion of inspected customers and the proportion of NTL found among the inspected customers. We then analyze the distributions of features generated and show why they are useful to predict NTL. In addition, we compute features from the consumption time series of customers. We also use master data features of customers, such as their customer class and voltage of their connection. We compute these features for a Big Data base of 31M meter readings, 700K customers and 400K inspection results. We then use these features to train four machine learning algorithms that are particularly suitable for Big Data sets because of their parallelizable structure: logistic regression, k-nearest neighbors, linear support vector machine and random forest. Using the neighborhood features instead of only analyzing the time series has resulted in appreciable results for Big Data sets for varying NTL proportions of 1%-90%. This work can therefore be deployed to a wide range of different regions around the world.