OpenRaiser/Intern-Atlas huggingface dataset:
Short Cycles via Low-Diameter Decompositions
Venue: arXiv cs.DS 2019
Year: 2019

We present improved algorithms for short cycle decomposition of a graph. Short cycle decompositions were introduced in the recent work of Chu et al, and were used to make progress on several questions in graph sparsification. For all constants $δ\in (0,1]$, we give an $O(mn^δ)$ time algorithm that, given a graph $G,$ partitions its edges into cycles of length $O(\log n)^\frac{1}δ$, with $O(n)$ extra edges not in any cycle. This gives the first subquadratic, in fact almost linear time, algorithm achieving polylogarithmic cycle lengths. We also give an $m \cdot \exp(O(\sqrt{\log n}))$ time algorithm that partitions the edges of a graph into cycles of length $\exp(O(\sqrt{\log n} \log\log n))$, with $O(n)$ extra edges not in any cycle. This improves on the short cycle decomposition algorithms given in Chu et al in terms of all parameters, and is significantly simpler. As a result, we obtain faster algorithms and improved guarantees for several problems in graph sparsification -- construction of resistance sparsifiers, graphical spectral sketches, degree preserving sparsifiers, and approximating the effective resistances of all edges.
Real-time Faulted Line Localization and PMU Placement in Power Systems through Convolutional Neural Networks
Venue: arXiv cs.SY 2019
Year: 2019

Diverse fault types, fast re-closures, and complicated transient states after a fault event make real-time fault location in power grids challenging. Existing localization techniques in this area rely on simplistic assumptions, such as static loads, or require much higher sampling rates or total measurement availability. This paper proposes a faulted line localization method based on a Convolutional Neural Network (CNN) classifier using bus voltages. Unlike prior data-driven methods, the proposed classifier is based on features with physical interpretations that improve the robustness of the location performance. The accuracy of our CNN based localization tool is demonstrably superior to other machine learning classifiers in the literature. To further improve the location performance, a joint phasor measurement units (PMU) placement strategy is proposed and validated against other methods. A significant aspect of our methodology is that under very low observability (7% of buses), the algorithm is still able to localize the faulted line to a small neighborhood with high probability. The performance of our scheme is validated through simulations of faults of various types in the IEEE 39-bus and 68-bus power systems under varying uncertain conditions, system observability, and measurement quality.
IndoSum: A New Benchmark Dataset for Indonesian Text Summarization
Venue: arXiv cs.CL 2019
Year: 2019

Automatic text summarization is generally considered as a challenging task in the NLP community. One of the challenges is the publicly available and large dataset that is relatively rare and difficult to construct. The problem is even worse for low-resource languages such as Indonesian. In this paper, we present IndoSum, a new benchmark dataset for Indonesian text summarization. The dataset consists of news articles and manually constructed summaries. Notably, the dataset is almost 200x larger than the previous Indonesian summarization dataset of the same domain. We evaluated various extractive summarization approaches and obtained encouraging results which demonstrate the usefulness of the dataset and provide baselines for future research. The code and the dataset are available online under permissive licenses.
Efficient architecture for deep neural networks with heterogeneous sensitivity
Venue: arXiv cs.CV 2019
Year: 2019

This work presents a neural network that consists of nodes with heterogeneous sensitivity. Each node in a network is assigned a variable that determines the sensitivity with which it learns to perform a given task. The network is trained by a constrained optimization that maximizes the sparsity of the sensitivity variables while ensuring the network's performance. As a result, the network learns to perform a given task using only a small number of sensitive nodes. Insensitive nodes, the nodes with zero sensitivity, can be removed from a trained network to obtain a computationally efficient network. Removing zero-sensitivity nodes has no effect on the network's performance because the network has already been trained to perform the task without them. The regularization parameter used to solve the optimization problem is found simultaneously during the training of networks. To validate our approach, we design networks with computationally efficient architectures for various tasks such as autoregression, object recognition, facial expression recognition, and object detection using various datasets. In our experiments, the networks designed by the proposed method provide the same or higher performance but with far less computational complexity.
Physics-Driven Regularization of Deep Neural Networks for Enhanced Engineering Design and Analysis
Venue: arXiv cs.LG 2019
Year: 2019

In this paper, we introduce a physics-driven regularization method for training of deep neural networks (DNNs) for use in engineering design and analysis problems. In particular, we focus on prediction of a physical system, for which in addition to training data, partial or complete information on a set of governing laws is also available. These laws often appear in the form of differential equations, derived from first principles, empirically-validated laws, or domain expertise, and are usually neglected in data-driven prediction of engineering systems. We propose a training approach that utilizes the known governing laws and regularizes data-driven DNN models by penalizing divergence from those laws. The first two numerical examples are synthetic examples, where we show that in constructing a DNN model that best fits the measurements from a physical system, the use of our proposed regularization results in DNNs that are more interpretable with smaller generalization errors, compared to other common regularization methods. The last two examples concern metamodeling for a random Burgers' system and for aerodynamic analysis of passenger vehicles, where we demonstrate that the proposed regularization provides superior generalization accuracy compared to other common alternatives.
Bottom-up Attention, Models of
Venue: arXiv cs.CV 2019
Year: 2019

In this review, we examine the recent progress in saliency prediction and proposed several avenues for future research. In spite of tremendous efforts and huge progress, there is still room for improvement in terms finer-grained analysis of deep saliency models, evaluation measures, datasets, annotation methods, cognitive studies, and new applications. This chapter will appear in Encyclopedia of Computational Neuroscience.
A Data-Driven Framework for Assessing Cold Load Pick-up Demand in Service Restoration
Venue: arXiv cs.SY 2019
Year: 2019

Cold load pick-up (CLPU) has been a critical concern to utilities. Researchers and industry practitioners have underlined the impact of CLPU on distribution system design and service restoration. The recent large-scale deployment of smart meters has provided the industry with a huge amount of data that is highly granular, both temporally and spatially. In this paper, a data-driven framework is proposed for assessing CLPU demand of residential customers using smart meter data. The proposed framework consists of two interconnected layers: 1) At the feeder level, a nonlinear auto-regression model is applied to estimate the diversified demand during the system restoration and calculate the CLPU demand ratio. 2) At the customer level, Gaussian Mixture Models (GMM) and probabilistic reasoning are used to quantify the CLPU demand increase. The proposed methodology has been verified using real smart meter data and outage cases.
Robust Model Predictive Control of Irrigation Systems with Active Uncertainty Learning and Data Analytics
Venue: arXiv cs.SY 2019
Year: 2019

We develop a novel data-driven robust model predictive control (DDRMPC) approach for automatic control of irrigation systems. The fundamental idea is to integrate both mechanistic models, which describe dynamics in soil moisture variations, and data-driven models, which characterize uncertainty in forecast errors of evapotranspiration and precipitation, into a holistic systems control framework. To better capture the support of uncertainty distribution, we take a new learning-based approach by constructing uncertainty sets from historical data. For evapotranspiration forecast error, the support vector clustering-based uncertainty set is adopted, which can be conveniently built from historical data. As for precipitation forecast errors, we analyze the dependence of their distribution on forecast values, and further design a tailored uncertainty set based on the properties of this type of uncertainty. In this way, the overall uncertainty distribution can be elaborately described, which finally contributes to rational and efficient control decisions. To assure the quality of data-driven uncertainty sets, a training-calibration scheme is used to provide theoretical performance guarantees. A generalized affine decision rule is adopted to obtain tractable approximations of optimal control problems, thereby ensuring the practicability of DDRMPC. Case studies using real data show that, DDRMPC can reliably maintain soil moisture above the safety level and avoid crop devastation. The proposed DDRMPC approach leads to a 40% reduction of total water consumption compared to the fine-tuned open-loop control strategy. In comparison with the carefully tuned rule-based control and certainty equivalent model predictive control, the proposed DDRMPC approach can significantly reduce the total water consumption and improve the control performance.
Comparison-Based Convolutional Neural Networks for Cervical Cell/Clumps Detection in the Limited Data Scenario
Venue: arXiv cs.CV 2019
Year: 2019

Automated detection of cervical cancer cells or cell clumps has the potential to significantly reduce error rate and increase productivity in cervical cancer screening. However, most traditional methods rely on the success of accurate cell segmentation and discriminative hand-crafted features extraction. Recently there are emerging deep learning-based methods which train convolutional neural networks (CNN) to classify image patches, but they are computationally expensive. In this paper we propose an efficient CNN-based object detection methods for cervical cancer cells/clumps detection. Specifically, we utilize the state-of-the-art two-stage object detection method, the Faster-RCNN with Feature Pyramid Network (FPN) as the baseline and propose a novel comparison detector to deal with the limited data problem. The key idea is that classify the proposals by comparing with the reference samples of each category in object detection. In addition, we propose to learn the reference samples of the background from data instead of manually choosing them by some heuristic rules. Experimental results show that the proposed Comparison Detector yields significant improvement on the small dataset, achieving a mean Average Precision (mAP) of 26.3% and an Average Recall (AR) of 35.7%, both improving about 20 points compared to the baseline. Moreover, Comparison Detector improved AR by 4.6 points and achieved marginally better performance in terms of mAP compared with baseline model when training on the medium dataset. Our method is promising for the development of automation-assisted cervical cancer screening systems. Code is available at https://github.com/kuku-sichuan/ComparisonDetector.
Recipe1M+: A Dataset for Learning Cross-Modal Embeddings for Cooking Recipes and Food Images
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we introduce Recipe1M+, a new large-scale, structured corpus of over one million cooking recipes and 13 million food images. As the largest publicly available collection of recipe data, Recipe1M+ affords the ability to train high-capacity modelson aligned, multimodal data. Using these data, we train a neural network to learn a joint embedding of recipes and images that yields impressive results on an image-recipe retrieval task. Moreover, we demonstrate that regularization via the addition of a high-level classification objective both improves retrieval performance to rival that of humans and enables semantic vector arithmetic. We postulate that these embeddings will provide a basis for further exploration of the Recipe1M+ dataset and food and cooking in general. Code, data and models are publicly available.
Simple Policy Evaluation for Data-Rich Iterative Tasks
Venue: arXiv cs.SY 2019
Year: 2019

A data-based policy for iterative control task is presented. The proposed strategy is model-free and can be applied whenever safe input and state trajectories of a system performing an iterative task are available. These trajectories, together with a user-defined cost function, are exploited to construct a piecewise affine approximation to the value function. Approximated value functions are then used to evaluate the control policy by solving a linear program. We show that for linear system subject to convex cost and constraints, the proposed strategy guarantees closed-loop constraint satisfaction and performance bounds on the closed-loop trajectory. We evaluate the proposed strategy in simulations and experiments, the latter carried out on the Berkeley Autonomous Race Car (BARC) platform. We show that the proposed strategy is able to reduce the computation time by one order of magnitude while achieving the same performance as our model-based control algorithm.
Learning Socially Appropriate Robot Approaching Behavior Toward Groups using Deep Reinforcement Learning
Venue: arXiv cs.RO 2019
Year: 2019

Deep reinforcement learning has recently been widely applied in robotics to study tasks such as locomotion and grasping, but its application to social human-robot interaction (HRI) remains a challenge. In this paper, we present a deep learning scheme that acquires a prior model of robot approaching behavior in simulation and applies it to real-world interaction with a physical robot approaching groups of humans. The scheme, which we refer to as Staged Social Behavior Learning (SSBL), considers different stages of learning in social scenarios. We learn robot approaching behaviors towards small groups in simulation and evaluate the performance of the model using objective and subjective measures in a perceptual study and a HRI user study with human participants. Results show that our model generates more socially appropriate behavior compared to a state-of-the-art model.
LRW-1000: A Naturally-Distributed Large-Scale Benchmark for Lip Reading in the Wild
Venue: arXiv cs.CV 2019
Year: 2019

Large-scale datasets have successively proven their fundamental importance in several research fields, especially for early progress in some emerging topics. In this paper, we focus on the problem of visual speech recognition, also known as lipreading, which has received increasing interest in recent years. We present a naturally-distributed large-scale benchmark for lip reading in the wild, named LRW-1000, which contains 1,000 classes with 718,018 samples from more than 2,000 individual speakers. Each class corresponds to the syllables of a Mandarin word composed of one or several Chinese characters. To the best of our knowledge, it is currently the largest word-level lipreading dataset and also the only public large-scale Mandarin lipreading dataset. This dataset aims at covering a "natural" variability over different speech modes and imaging conditions to incorporate challenges encountered in practical applications. It has shown a large variation in this benchmark in several aspects, including the number of samples in each class, video resolution, lighting conditions, and speakers' attributes such as pose, age, gender, and make-up. Besides providing a detailed description of the dataset and its collection pipeline, we evaluate several typical popular lipreading methods and perform a thorough analysis of the results from several aspects. The results demonstrate the consistency and challenges of our dataset, which may open up some new promising directions for future work.
A Comprehensive Survey on Networking over TV White Spaces
Venue: arXiv cs.NI 2019
Year: 2019

TV white spaces refer to the allocated but locally unused TV spectrum and can be used by unlicensed devices as secondary users. Thanks to their lower frequencies (e.g., 54 -- 698 MHz in the US), communication over the TV spectrum has excellent propagation characteristics over long distances and through obstacles. These characteristics along with their wide availability make the TV white spaces a great choice and alternative to many existing wireless technologies, especially the ones that need long range and high bandwidth communication. In the last decade, there have been numerous efforts from academia, industries, and standards bodies for exploiting the potentials of the TV white spaces for several applications including wireless broadband Internet access. Their characteristics and features also hold potentials for many new applications including sensing and monitoring, Internet of Things, wireless control, smart utility, location-based services, and transportation and logistics. In this paper, we perform a retrospective review and comparative study of existing work on networking in the TV white spaces. Additionally, we discuss the associated research challenges such as dealing with the interference between primary and secondary TV spectrum users, TV white space temporal and spatial variations and fragmentation, antenna design, mobility, and security. We also describe the future research directions to handle the above challenges. To the best of our knowledge, this is the first comprehensive survey on the literature of TV white space networking research.
Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron
Venue: arXiv cs.LG 2019
Year: 2019

Modern machine learning focuses on highly expressive models that are able to fit or interpolate the data completely, resulting in zero training loss. For such models, we show that the stochastic gradients of common loss functions satisfy a strong growth condition. Under this condition, we prove that constant step-size stochastic gradient descent (SGD) with Nesterov acceleration matches the convergence rate of the deterministic accelerated method for both convex and strongly-convex functions. We also show that this condition implies that SGD can find a first-order stationary point as efficiently as full gradient descent in non-convex settings. Under interpolation, we further show that all smooth loss functions with a finite-sum structure satisfy a weaker growth condition. Given this weaker condition, we prove that SGD with a constant step-size attains the deterministic convergence rate in both the strongly-convex and convex settings. Under additional assumptions, the above results enable us to prove an O(1/k^2) mistake bound for k iterations of a stochastic perceptron algorithm using the squared-hinge loss. Finally, we validate our theoretical findings with experiments on synthetic and real datasets.
Wave: A New Family of Trapdoor One-Way Preimage Sampleable Functions Based on Codes
Venue: arXiv cs.CR 2019
Year: 2019

We present here a new family of trapdoor one-way Preimage Sampleable Functions (PSF) based on codes, the Wave-PSF family. The trapdoor function is one-way under two computational assumptions: the hardness of generic decoding for high weights and the indistinguishability of generalized $(U,U+V)$-codes. Our proof follows the GPV strategy [GPV08]. By including rejection sampling, we ensure the proper distribution for the trapdoor inverse output. The domain sampling property of our family is ensured by using and proving a variant of the left-over hash lemma. We instantiate the new Wave-PSF family with ternary generalized $(U,U+V)$-codes to design a "hash-and-sign" signature scheme which achieves existential unforgeability under adaptive chosen message attacks (EUF-CMA) in the random oracle model. For 128 bits of classical security, signature sizes are in the order of 15 thousand bits, the public key size in the order of 4 megabytes, and the rejection rate is limited to one rejection every 10 to 12 signatures.
Pruning Deep Neural Networks using Partial Least Squares
Venue: arXiv cs.CV 2019
Year: 2019

Modern pattern recognition methods are based on convolutional networks since they are able to learn complex patterns that benefit the classification. However, convolutional networks are computationally expensive and require a considerable amount of memory, which limits their deployment on low-power and resource-constrained systems. To handle these problems, recent approaches have proposed pruning strategies that find and remove unimportant neurons (i.e., filters) in these networks. Despite achieving remarkable results, existing pruning approaches are ineffective since the accuracy of the original network is degraded. In this work, we propose a novel approach to efficiently remove filters from convolutional networks. Our approach estimates the filter importance based on its relationship with the class label on a low-dimensional space. This relationship is computed using Partial Least Squares (PLS) and Variable Importance in Projection (VIP). Our method is able to reduce up to 67% of the floating point operations (FLOPs) without penalizing the network accuracy. With a negligible drop in accuracy, we can reduce up to 90% of FLOPs. Additionally, sometimes the method is even able to improve the accuracy compared to original, unpruned, network. We show that employing PLS+VIP as the criterion for detecting the filters to be removed is better than recent feature selection techniques, which have been employed by state-of-the-art pruning methods. Finally, we show that the proposed method achieves the highest FLOPs reduction and the smallest drop in accuracy when compared to state-of-the-art pruning approaches. Codes are available at: https://github.com/arturjordao/PruningNeuralNetworks
The UCR Time Series Archive
Venue: arXiv cs.LG 2019
Year: 2019

The UCR Time Series Archive - introduced in 2002, has become an important resource in the time series data mining community, with at least one thousand published papers making use of at least one data set from the archive. The original incarnation of the archive had sixteen data sets but since that time, it has gone through periodic expansions. The last expansion took place in the summer of 2015 when the archive grew from 45 to 85 data sets. This paper introduces and will focus on the new data expansion from 85 to 128 data sets. Beyond expanding this valuable resource, this paper offers pragmatic advice to anyone who may wish to evaluate a new algorithm on the archive. Finally, this paper makes a novel and yet actionable claim: of the hundreds of papers that show an improvement over the standard baseline (1-nearest neighbor classification), a large fraction may be mis-attributing the reasons for their improvement. Moreover, they may have been able to achieve the same improvement with a much simpler modification, requiring just a single line of code.