OpenRaiser/Intern-Atlas huggingface dataset:
Mixed Voltage Angle and Frequency Droop Control for Transient Stability of Interconnected Microgrids with Loss of PMU Measurements
Venue: arXiv cs.SY 2020
Year: 2020

We consider the problem of guaranteeing transient stability of a network of interconnected angle droop controlled microgrids, where voltage phase angle measurements from phasor measurement units (PMUs) may be lost, leading to poor performance and instability. In this paper, we propose a novel mixed voltage angle and frequency droop control (MAFD) framework to improve the reliability of such angle droop controlled microgrid interconnections. In this framework, when the phase angle measurement is lost at a microgrid, conventional frequency droop control is temporarily used for primary control in place of angle droop control. We model the network of interconnected microgrids with the MAFD architecture as a nonlinear switched system. We then propose a dissipativity-based distributed secondary control design to guarantee transient stability of this network under arbitrary switching between angle droop and frequency droop controllers. We demonstrate the performance of this control framework by simulation on a test 123-feeder distribution network.
Theoretical Bounds and Constructions of Codes in the Generalized Cayley Metric
Venue: arXiv cs.IT 2020
Year: 2020

Permutation codes have recently garnered substantial research interest due to their potential in various applications including cloud storage systems, genome resequencing and flash memories. In this paper, we study the theoretical bounds and constructions of permutation codes in the generalized Cayley metric. The generalized Cayley metric captures the number of generalized transposition errors in a permutation, and subsumes previously studied error types, including transpositions and translocations, without imposing restrictions on the lengths and positions of the translocated segments. Relying on the breakpoint analysis proposed by Chee and Vu, we first propose a coding scheme that is order-optimal albeit not constructive based on this method. We then develop another construction of permutation codes in the generalized Cayley distance. This scheme is both explicit and systematic. We also prove the existence of order-optimal systematic codes and offer a concrete construction based on this method. For the generalized Cayley metric, we prove that our coding schemes have less redundancy than the existing codes based on interleaving when the codelength is sufficiently large and the number of errors is relatively small.
Reactive Proximity Data Structures for Graphs
Venue: arXiv cs.DS 2020
Year: 2020

We consider data structures for graphs where we maintain a subset of the nodes called sites, and allow proximity queries, such as asking for the closest site to a query node, and update operations that enable or disable nodes as sites. We refer to a data structure that can efficiently react to such updates as reactive. We present novel reactive proximity data structures for graphs of polynomial expansion, i.e., the class of graphs with small separators, such as planar graphs and road networks. Our data structures can be used in several logistical problems and geographic information systems dealing with real-time data, such as emergency dispatching. We experimentally compare our data structure to Dijkstra's algorithm in a system emulating random queries in a real road network.
Fractal AI: A fragile theory of intelligence
Venue: arXiv cs.AI 2020
Year: 2020

Fractal AI is a theory for general artificial intelligence. It allows deriving new mathematical tools that constitute the foundations for a new kind of stochastic calculus, by modelling information using cellular automaton-like structures instead of smooth functions. In the repository included we are presenting a new Agent, derived from the first principles of the theory, which is capable of solving Atari games several orders of magnitude more efficiently than other similar techniques, like Monte Carlo Tree Search. The code provided shows how it is now possible to beat some of the current State of The Art benchmarks on Atari games, without previous learning and using less than 1000 samples to calculate each one of the actions when standard MCTS uses 3 Million samples. Among other things, Fractal AI makes it possible to generate a huge database of top performing examples with a very little amount of computation required, transforming Reinforcement Learning into a supervised problem. The algorithm presented is capable of solving the exploration vs exploitation dilemma on both the discrete and continuous cases, while maintaining control over any aspect of the behaviour of the Agent. From a general approach, new techniques presented here have direct applications to other areas such as Non-equilibrium thermodynamics, chemistry, quantum physics, economics, information theory, and non-linear control theory.
Reservoir computing approaches for representation and classification of multivariate time series
Venue: arXiv cs.NE 2020
Year: 2020

Classification of multivariate time series (MTS) has been tackled with a large variety of methodologies and applied to a wide range of scenarios. Reservoir Computing (RC) provides efficient tools to generate a vectorial, fixed-size representation of the MTS that can be further processed by standard classifiers. Despite their unrivaled training speed, MTS classifiers based on a standard RC architecture fail to achieve the same accuracy of fully trainable neural networks. In this paper we introduce the reservoir model space, an unsupervised approach based on RC to learn vectorial representations of MTS. Each MTS is encoded within the parameters of a linear model trained to predict a low-dimensional embedding of the reservoir dynamics. Compared to other RC methods, our model space yields better representations and attains comparable computational performance, thanks to an intermediate dimensionality reduction procedure. As a second contribution we propose a modular RC framework for MTS classification, with an associated open-source Python library. The framework provides different modules to seamlessly implement advanced RC architectures. The architectures are compared to other MTS classifiers, including deep learning models and time series kernels. Results obtained on benchmark and real-world MTS datasets show that RC classifiers are dramatically faster and, when implemented using our proposed representation, also achieve superior classification accuracy.
Efficient constant factor approximation algorithms for stabbing line segments with equal disks
Venue: arXiv cs.CG 2020
Year: 2020

An NP-hard problem is considered of intersecting a given set of $n$ straight line segments on the plane with the smallest cardinality set of disks of fixed radii $r>0,$ where the set of segments forms a straight line drawing $G=(V,E)$ of a planar graph without proper edge crossings. To the best of our knowledge, related work only tackles a setting where $E$ consists of (generally, properly overlapping) axis-parallel segments, resulting in an $O(n\log n)$-time and $O(n\log n)$-space 8-approximation algorithm. Exploiting tough connection of the problem with the geometric Hitting Set problem, an $\left(50+52\sqrt{\frac{12}{13}}+ν\right)$-approximate $O\left(n^4\log n\right)$-time and $O\left(n^2\log n\right)$-space algorithm is devised based on the modified Agarwal-Pan algorithm, which uses epsilon nets. More accurate $(34+24\sqrt{2}+ν)$- and $\left(\frac{144}{5}+32\sqrt{\frac{3}{5}}+ν\right)$-approxi\-mate algorithms are also proposed for cases where $G$ is any subgraph of either a generalized outerplane graph or a Delaunay triangulation respectively, which work within the same time and space complexity bounds, where $ν>0$ is an arbitrarily small constant.
Single Day Outdoor Photometric Stereo
Venue: arXiv cs.CV 2020
Year: 2020

Photometric Stereo (PS) under outdoor illumination remains a challenging, ill-posed problem due to insufficient variability in illumination. Months-long capture sessions are typically used in this setup, with little success on shorter, single-day time intervals. In this paper, we investigate the solution of outdoor PS over a single day, under different weather conditions. First, we investigate the relationship between weather and surface reconstructability in order to understand when natural lighting allows existing PS algorithms to work. Our analysis reveals that partially cloudy days improve the conditioning of the outdoor PS problem while sunny days do not allow the unambiguous recovery of surface normals from photometric cues alone. We demonstrate that calibrated PS algorithms can thus be employed to reconstruct Lambertian surfaces accurately under partially cloudy days. Second, we solve the ambiguity arising in clear days by combining photometric cues with prior knowledge on material properties, local surface geometry and the natural variations in outdoor lighting through a CNN-based, weakly-calibrated PS technique. Given a sequence of outdoor images captured during a single sunny day, our method robustly estimates the scene surface normals with unprecedented quality for the considered scenario. Our approach does not require precise geolocation and significantly outperforms several state-of-the-art methods on images with real lighting, showing that our CNN can combine efficiently learned priors and photometric cues available during a single sunny day.
Convex Relaxations of Probabilistic AC Optimal Power Flow for Interconnected AC and HVDC Grids
Venue: arXiv cs.SY 2020
Year: 2020

High Voltage Direct Current (HVDC) systems interconnect AC grids to increase reliability, connect offshore wind generation, and enable coupling of electricity markets. Considering the growing uncertainty in power infeed and the complexity introduced by additional controls, robust decision support tools are necessary. This paper proposes a chance constrained AC-OPF for AC and HVDC grids, which considers wind uncertainty, fully utilizes HVDC control capabilities, and uses the semidefinite relaxation of the AC-OPF. We consider a joint chance constraint for both AC and HVDC systems, we introduce a piecewise affine approximation to achieve tractability of the chance constraint, and we allow corrective control policies for HVDC converters and generators to be determined. An active loss penalty term in the objective function and a systematic procedure to choose the penalty weights allow us to obtain AC-feasible solutions. We introduce Benders decomposition to maintain scalability. Using realistic forecast data, we demonstrate our approach on a 53-bus and a 214-bus AC-DC system, obtaining tight near-global optimality guarantees. With a Monte Carlo analysis, we show that a chance constrained DC-OPF leads to violations, whereas our proposed approach complies with the joint chance constraint.
Pigeonring: A Principle for Faster Thresholded Similarity Search
Venue: arXiv cs.DB 2020
Year: 2020

The pigeonhole principle states that if $n$ items are contained in $m$ boxes, then at least one box has no more than $n / m$ items. It is utilized to solve many data management problems, especially for thresholded similarity searches. Despite many pigeonhole principle-based solutions proposed in the last few decades, the condition stated by the principle is weak. It only constrains the number of items in a single box. By organizing the boxes in a ring, we propose a new principle, called the pigeonring principle, which constrains the number of items in multiple boxes and yields stronger conditions. To utilize the new principle, we focus on problems defined in the form of identifying data objects whose similarities or distances to the query is constrained by a threshold. Many solutions to these problems utilize the pigeonhole principle to find candidates that satisfy a filtering condition. By the new principle, stronger filtering conditions can be established. We show that the pigeonhole principle is a special case of the new principle. This suggests that all the pigeonhole principle-based solutions are possible to be accelerated by the new principle. A universal filtering framework is introduced to encompass the solutions to these problems based on the new principle. Besides, we discuss how to quickly find candidates specified by the new principle. The implementation requires only minor modifications on top of existing pigeonhole principle-based algorithms. Experimental results on real datasets demonstrate the applicability of the new principle as well as the superior performance of the algorithms based on the new principle.
Adaptive Quantile Sparse Image (AQuaSI) Prior for Inverse Imaging Problems
Venue: arXiv cs.CV 2020
Year: 2020

Inverse problems play a central role for many classical computer vision and image processing tasks. Many inverse problems are ill-posed, and hence require a prior to regularize the solution space. However, many of the existing priors, like total variation, are based on ad-hoc assumptions that have difficulties to represent the actual distribution of natural images. Thus, a key challenge in research on image processing is to find better suited priors to represent natural images. In this work, we propose the Adaptive Quantile Sparse Image (AQuaSI) prior. It is based on a quantile filter, can be used as a joint filter on guidance data, and be readily plugged into a wide range of numerical optimization algorithms. We demonstrate the efficacy of the proposed prior in joint RGB/depth upsampling, on RGB/NIR image restoration, and in a comparison with related regularization by denoising approaches.
Microblog Topic Identification using Linked Open Data
Venue: arXiv cs.IR 2020
Year: 2020

The extensive use of social media for sharing and obtaining information has resulted in the development of topic detection models to facilitate the comprehension of the overwhelming amount of short and distributed posts. Probabilistic topic models, such as Latent Dirichlet Allocation, and matrix factorization based approaches such as Latent Semantic Analysis and Non-negative Matrix Factorization represent topics as sets of terms that are useful for many automated processes. However, the determination of what a topic is about is left as a further task. Alternatively, techniques that produce summaries are human comprehensible, but less suitable for automated processing. This work proposes an approach that utilizes Linked Open Data (LOD) resources to extract semantically represented topics from collections of microposts. The proposed approach utilizes entity linking to identify the elements of topics from microposts. The elements are related through co-occurrence graphs, which are processed to yield topics. The topics are represented using an ontology that is introduced for this purpose. A prototype of the approach is used to identify topics from 11 datasets consisting of more than one million posts collected from Twitter during various events, such as the 2016 US election debates and the death of Carrie Fisher. The characteristics of the approach with more than 5 thousand generated topics are described in detail. The potentials of semantic topics in revealing information, that is not otherwise easily observable, is demonstrated with semantic queries of various complexities. A human evaluation of topics from 36 randomly selected intervals resulted in a precision of 81.0% and F1 score of 93.3%. Furthermore, they are compared with topics generated from the same datasets from an approach that produces human readable topics from microblog post collections.
Large scale distributed neural network training through online distillation
Venue: arXiv cs.LG 2020
Year: 2020

Techniques such as ensembling and distillation promise model quality improvements when paired with almost any base model. However, due to increased test-time cost (for ensembles) and increased complexity of the training pipeline (for distillation), these techniques are challenging to use in industrial settings. In this paper we explore a variant of distillation which is relatively straightforward to use as it does not require a complicated multi-stage setup or many new hyperparameters. Our first claim is that online distillation enables us to use extra parallelism to fit very large datasets about twice as fast. Crucially, we can still speed up training even after we have already reached the point at which additional parallelism provides no benefit for synchronous or asynchronous stochastic gradient descent. Two neural networks trained on disjoint subsets of the data can share knowledge by encouraging each model to agree with the predictions the other model would have made. These predictions can come from a stale version of the other model so they can be safely computed using weights that only rarely get transmitted. Our second claim is that online distillation is a cost-effective way to make the exact predictions of a model dramatically more reproducible. We support our claims using experiments on the Criteo Display Ad Challenge dataset, ImageNet, and the largest to-date dataset used for neural language modeling, containing $6\times 10^{11}$ tokens and based on the Common Crawl repository of web data.
Non-existence of certain kind of finite-letter mutual information characterization for a class of time-invariant Markoff channels
Venue: arXiv cs.IT 2020
Year: 2020

We provide a rigorous definition of a certain kind of characterization for capacity regions of a family of Markoff networks which is based on optimization problems resulting out of calculating conditional mutual information from a finite number of random variables and by constraining these random variables in a certain way. This definition is partly motivated by the definition of single-letter characterizations in information theory. For a point-to-point Markoff channel, we prove that approximating the solution to these characterizations within an additive constant is a computable problem. Based on previous undecidability results concerning capacities of certain class of finite state machine channels (FSMCs), it will follow that there exists an example of family of FSMCs for which given such a characterization, this characterization cannot represent the capacity of this family of FSMCs.
Neural Automated Essay Scoring and Coherence Modeling for Adversarially Crafted Input
Venue: arXiv cs.CL 2020
Year: 2020

We demonstrate that current state-of-the-art approaches to Automated Essay Scoring (AES) are not well-suited to capturing adversarially crafted input of grammatical but incoherent sequences of sentences. We develop a neural model of local coherence that can effectively learn connectedness features between sentences, and propose a framework for integrating and jointly training the local coherence model with a state-of-the-art AES model. We evaluate our approach against a number of baselines and experimentally demonstrate its effectiveness on both the AES task and the task of flagging adversarial input, further contributing to the development of an approach that strengthens the validity of neural essay scoring models.
Spell Once, Summon Anywhere: A Two-Level Open-Vocabulary Language Model
Venue: arXiv cs.CL 2020
Year: 2020

We show how the spellings of known words can help us deal with unknown words in open-vocabulary NLP tasks. The method we propose can be used to extend any closed-vocabulary generative model, but in this paper we specifically consider the case of neural language modeling. Our Bayesian generative story combines a standard RNN language model (generating the word tokens in each sentence) with an RNN-based spelling model (generating the letters in each word type). These two RNNs respectively capture sentence structure and word structure, and are kept separate as in linguistics. By invoking the second RNN to generate spellings for novel words in context, we obtain an open-vocabulary language model. For known words, embeddings are naturally inferred by combining evidence from type spelling and token context. Comparing to baselines (including a novel strong baseline), we beat previous work and establish state-of-the-art results on multiple datasets.
Discovery of Driving Patterns by Trajectory Segmentation
Venue: arXiv cs.AI 2020
Year: 2020

Telematics data is becoming increasingly available due to the ubiquity of devices that collect data during drives, for different purposes, such as usage based insurance (UBI), fleet management, navigation of connected vehicles, etc. Consequently, a variety of data-analytic applications have become feasible that extract valuable insights from the data. In this paper, we address the especially challenging problem of discovering behavior-based driving patterns from only externally observable phenomena (e.g. vehicle's speed). We present a trajectory segmentation approach capable of discovering driving patterns as separate segments, based on the behavior of drivers. This segmentation approach includes a novel transformation of trajectories along with a dynamic programming approach for segmentation. We apply the segmentation approach on a real-word, rich dataset of personal car trajectories provided by a major insurance company based in Columbus, Ohio. Analysis and preliminary results show the applicability of approach for finding significant driving patterns.
Accelerator-Aware Pruning for Convolutional Neural Networks
Venue: arXiv cs.NE 2020
Year: 2020

Convolutional neural networks have shown tremendous performance capabilities in computer vision tasks, but their excessive amounts of weight storage and arithmetic operations prevent them from being adopted in embedded environments. One of the solutions involves pruning, where certain unimportant weights are forced to have a value of zero. Many pruning schemes have been proposed, but these have mainly focused on the number of pruned weights. Previous pruning schemes scarcely considered ASIC or FPGA accelerator architectures. When these pruned networks are run on accelerators, the lack of consideration of the architecture causes some inefficiency problems, including internal buffer misalignments and load imbalances. This paper proposes a new pruning scheme that reflects accelerator architectures. In the proposed scheme, pruning is performed so that the same number of weights remain for each weight group corresponding to activations fetched simultaneously. In this way, the pruning scheme resolves the inefficiency problems, doubling the accelerator performance. Even with this constraint, the proposed pruning scheme reached a pruning ratio similar to that of previous unconstrained pruning schemes, not only on AlexNet and VGG16 but also on state-of-the-art very deep networks such as ResNet. Furthermore, the proposed scheme demonstrated a comparable pruning ratio on compact networks such as MobileNet and on slimmed networks that were already pruned in a channel-wise manner. In addition to improving the efficiency of previous sparse accelerators, it will be also shown that the proposed pruning scheme can be used to reduce the logic complexity of sparse accelerators.The pruned models are publicly available at https://github.com/HyeongjuKang/accelerator-aware-pruning.