OpenRaiser/Intern-Atlas huggingface dataset:
Of the People: Voting Is More Effective with Representative Candidates
Venue: arXiv cs.GT 2017
Year: 2017

In light of the classic impossibility results of Arrow and Gibbard and Satterthwaite regarding voting with ordinal rules, there has been recent interest in characterizing how well common voting rules approximate the social optimum. In order to quantify the quality of approximation, it is natural to consider the candidates and voters as embedded within a common metric space, and to ask how much further the chosen candidate is from the population as compared to the socially optimal one. We use this metric preference model to explore a fundamental and timely question: does the social welfare of a population improve when candidates are representative of the population? If so, then by how much, and how does the answer depend on the complexity of the metric space? We restrict attention to the most fundamental and common social choice setting: a population of voters, two independently drawn candidates, and a majority rule election. When candidates are not representative of the population, it is known that the candidate selected by the majority rule can be thrice as far from the population as the socially optimal one. We examine how this ratio improves when candidates are drawn independently from the population of voters. Our results are two-fold: When the metric is a line, the ratio improves from $3$ to $4-2\sqrt{2}$, roughly $1.1716$; this bound is tight. When the metric is arbitrary, we show a lower bound of $1.5$ and a constant upper bound strictly better than $2$ on the approximation ratio of the majority rule. The positive result depends in part on the assumption that candidates are independent and identically distributed. However, we show that independence alone is not enough to achieve the upper bound: even when candidates are drawn independently, if the population of candidates can be different from the voters, then an upper bound of $2$ on the approximation is tight.
On the expressive power of quasiperiodic SFT
Venue: arXiv cs.DM 2017
Year: 2017

In this paper we study the shifts, which are the shift-invariant and topologically closed sets of configurations over a finite alphabet in $\mathbb{Z}^d$. The minimal shifts are those shifts in which all configurations contain exactly the same patterns. Two classes of shifts play a prominent role in symbolic dynamics, in language theory and in the theory of computability: the shifts of finite type (obtained by forbidding a finite number of finite patterns) and the effective shifts (obtained by forbidding a computably enumerable set of finite patterns). We prove that every effective minimal shift can be represented as a factor of a projective subdynamics on a minimal shift of finite type in a bigger (by $1$) dimension. This result transfers to the class of minimal shifts a theorem by M.Hochman known for the class of all effective shifts and thus answers an open question by E.Jeandel. We prove a similar result for quasiperiodic shifts and also show that there exists a quasiperiodic shift of finite type for which Kolmogorov complexity of all patterns of size $n\times n$ is $Ω(n)$.
Streaming for Aibohphobes: Longest Palindrome with Mismatches
Venue: arXiv cs.DS 2017
Year: 2017

A palindrome is a string that reads the same as its reverse, such as "aibohphobia" (fear of palindromes). Given an integer $d>0$, a $d$-near-palindrome is a string of Hamming distance at most $d$ from its reverse. We study the natural problem of identifying a longest $d$-near-palindrome in data streams. The problem is relevant to the analysis of DNA databases, and to the task of repairing recursive structures in documents such as XML and JSON. We present an algorithm that returns a $d$-near-palindrome whose length is within a multiplicative $(1+ε)$-factor of the longest $d$-near-palindrome. Our algorithm also returns the set of mismatched indices of the $d$-near-palindrome, using $\mathcal{O}\left(\frac{d\log^7 n}{ε\log(1+ε)}\right)$ bits of space, and $\mathcal{O}\left(\frac{d\log^6 n}{ε\log(1+ε)}\right)$ update time per arriving symbol. We show that $Ω(d\log n)$ space is necessary for estimating the length of longest $d$-near-palindromes with high probability. We further obtain an additive-error approximation algorithm and a comparable lower bound, as well as an exact two-pass algorithm that solves the longest $d$-near-palindrome problem using $\mathcal{O}\left(d^2\sqrt{n}\log^6 n\right)$ bits of space.
Digital Grid: Transforming the Electric Power Grid into an Innovation Engine for the United States
Venue: arXiv cs.CY 2017
Year: 2017

The electric power grid is one of the largest and most complex infrastructures ever built by mankind. Modern civilization depends on it for industry production, human mobility, and comfortable living. However, many critical technologies such as the 60 Hz transformers were developed at the beginning of the 20th century and have changed very little since then.1 The traditional unidirectional power from the generation to the customer through the transmission-distribution grid has also changed nominally, but it no longer meets the need of the 21st century market energy customers. On one hand, 128m US residential customers pay $15B/per month for their utility bill, yet they have no option to select their energy supplier. In a world of where many traditional industries are transformed by digital Internet technology (Amazon, Ebay, Uber, Airbnb), the traditional electric energy market is lagging significantly behind. A move towards a true digital grid is needed. Such a digital grid requires a tight integration of the physical layer (energy and power) with digital and cyber information to allow an open and real time market akin to the world of e-commerce. Another major factor that is pushing for this radical transformation are the rapidly changing patterns in energy resources ownership and load flow. Driven by the decreasing cost in distributed solar, energy storage, electric vehicle, on site generation and microgrids, the high penetration of Distributed Energy Resource (DER) is shifting challenges substantially towards the edge of grid from the control point of view. The envisioned Digital Grid must facilitate the open competition and open innovation needed to accelerate of the adoption of new DER technologies while satisfying challenges in grid stability, data explosion and cyber security.
Exponential scaling of neural algorithms - a future beyond Moore's Law?
Venue: arXiv cs.NE 2017
Year: 2017

Although the brain has long been considered a potential inspiration for future computing, Moore's Law - the scaling property that has seen revolutions in technologies ranging from supercomputers to smart phones - has largely been driven by advances in materials science. As the ability to miniaturize transistors is coming to an end, there is increasing attention on new approaches to computation, including renewed enthusiasm around the potential of neural computation. This paper describes how recent advances in neurotechnologies, many of which have been aided by computing's rapid progression over recent decades, are now reigniting this opportunity to bring neural computation insights into broader computing applications. As we understand more about the brain, our ability to motivate new computing paradigms with continue to progress. These new approaches to computing, which we are already seeing in techniques such as deep learning and neuromorphic hardware, will themselves improve our ability to learn about the brain and accordingly can be projected to give rise to even further insights. This paper will describe how this positive feedback has the potential to change the complexion of how computing sciences and neurosciences interact, and suggests that the next form of exponential scaling in computing may emerge from our progressive understanding of the brain.
GRASS: Generative Recursive Autoencoders for Shape Structures
Venue: arXiv cs.GR 2017
Year: 2017

We introduce a novel neural network architecture for encoding and synthesis of 3D shapes, particularly their structures. Our key insight is that 3D shapes are effectively characterized by their hierarchical organization of parts, which reflects fundamental intra-shape relationships such as adjacency and symmetry. We develop a recursive neural net (RvNN) based autoencoder to map a flat, unlabeled, arbitrary part layout to a compact code. The code effectively captures hierarchical structures of man-made 3D objects of varying structural complexities despite being fixed-dimensional: an associated decoder maps a code back to a full hierarchy. The learned bidirectional mapping is further tuned using an adversarial setup to yield a generative model of plausible structures, from which novel structures can be sampled. Finally, our structure synthesis framework is augmented by a second trained module that produces fine-grained part geometry, conditioned on global and local structural context, leading to a full generative pipeline for 3D shapes. We demonstrate that without supervision, our network learns meaningful structural hierarchies adhering to perceptual grouping principles, produces compact codes which enable applications such as shape classification and partial matching, and supports shape synthesis and interpolation with significant variations in topology and geometry.
Electrical Vehicle Charging Station Profit Maximization: Admission, Pricing, and Online Scheduling
Venue: arXiv cs.SY 2017
Year: 2017

The rapid emergence of electric vehicles (EVs) demands an advanced infrastructure of publicly accessible charging stations that provide efficient charging services. In this paper, we propose a new charging station operation mechanism, the JoAP, which jointly optimizes the EV admission control, pricing, and charging scheduling to maximize the charging station's profit. More specifically, by introducing a tandem queueing network model, we analytically characterize the average charging station profit as a function of the admission control and pricing policies. Based on the analysis, we characterize the optimal JoAP algorithm. Through extensive simulations, we demonstrate that the proposed JoAP algorithm on average can achieve 330% and 531% higher profit than a widely adopted benchmark method under two representative waiting-time penalty rates.
A Unification Algorithm for GP 2 (Long Version)
Venue: arXiv cs.LO 2017
Year: 2017

The graph programming language GP 2 allows to apply sets of rule schemata (or "attributed" rules) non-deterministically. To analyse conflicts of programs statically, graphs labelled with expressions are overlayed to construct critical pairs of rule applications. Each overlay induces a system of equations whose solutions represent different conflicts. We present a rule-based unification algorithm for GP expressions that is terminating, sound and complete. For every input equation, the algorithm generates a finite set of substitutions. Soundness means that each of these substitutions solves the input equation. Since GP labels are lists constructed by concatenation, unification modulo associativity and unit law is required. This problem, which is also known as word unification, is infinitary in general but becomes finitary due to GP's rule schema syntax and the assumption that rule schemata are left-linear. Our unification algorithm is complete in that every solution of an input equation is an instance of some substitution in the generated set.
Online Covering with Sum of $\ell_q$-Norm Objectives
Venue: arXiv cs.DS 2017
Year: 2017

We consider fractional online covering problems with $\ell_q$-norm objectives. The problem of interest is of the form $\min\{ f(x) \,:\, Ax\ge 1, x\ge 0\}$ where $f(x)=\sum_{e} c_e \|x(S_e)\|_{q_e} $ is the weighted sum of $\ell_q$-norms and $A$ is a non-negative matrix. The rows of $A$ (i.e. covering constraints) arrive online over time. We provide an online $O(\log d+\log ρ)$-competitive algorithm where $ρ= \frac{\max a_{ij}}{\min a_{ij}}$ and $d$ is the maximum of the row sparsity of $A$ and $\max |S_e|$. This is based on the online primal-dual framework where we use the dual of the above convex program. Our result expands the class of convex objectives that admit good online algorithms: prior results required a monotonicity condition on the objective $f$ which is not satisfied here. This result is nearly tight even for the linear special case. As direct applications we obtain (i) improved online algorithms for non-uniform buy-at-bulk network design and (ii) the first online algorithm for throughput maximization under $\ell_p$-norm edge capacities.
Structured sampling and fast reconstruction of smooth graph signals
Venue: arXiv cs.SI 2017
Year: 2017

This work concerns sampling of smooth signals on arbitrary graphs. We first study a structured sampling strategy for such smooth graph signals that consists of a random selection of few pre-defined groups of nodes. The number of groups to sample to stably embed the set of $k$-bandlimited signals is driven by a quantity called the \emph{group} graph cumulative coherence. For some optimised sampling distributions, we show that sampling $O(k\log(k))$ groups is always sufficient to stably embed the set of $k$-bandlimited signals but that this number can be smaller -- down to $O(\log(k))$ -- depending on the structure of the groups of nodes. Fast methods to approximate these sampling distributions are detailed. Second, we consider $k$-bandlimited signals that are nearly piecewise constant over pre-defined groups of nodes. We show that it is possible to speed up the reconstruction of such signals by reducing drastically the dimension of the vectors to reconstruct. When combined with the proposed structured sampling procedure, we prove that the method provides stable and accurate reconstruction of the original signal. Finally, we present numerical experiments that illustrate our theoretical results and, as an example, show how to combine these methods for interactive object segmentation in an image using superpixels.
A Polya Contagion Model for Networks
Venue: arXiv cs.SI 2017
Year: 2017

A network epidemics model based on the classical Polya urn scheme is investigated. Temporal contagion processes are generated on the network nodes using a modified Polya sampling scheme that accounts for spatial infection among neighbouring nodes. The stochastic properties and the asymptotic behaviour of the resulting network contagion process are analyzed. Unlike the classical Polya process, the network process is noted to be non-stationary in general, although it is shown to be time-invariant in its first and some of its second-order statistics and to satisfy martingale convergence properties under certain conditions. Three classical Polya processes, one computational and two analytical, are proposed to statistically approximate the contagion process of each node, showing a good fit for a range of system parameters. Finally, empirical results compare and contrast our model with the well-known discrete time SIS model.
Computing Constrained Approximate Equilibria in Polymatrix Games
Venue: arXiv cs.GT 2017
Year: 2017

This paper is about computing constrained approximate Nash equilibria in polymatrix games, which are succinctly represented many-player games defined by an interaction graph between the players. In a recent breakthrough, Rubinstein showed that there exists a small constant $ε$, such that it is PPAD-complete to find an (unconstrained) $ε$-Nash equilibrium of a polymatrix game. In the first part of the paper, we show that is NP-hard to decide if a polymatrix game has a constrained approximate equilibrium for 9 natural constraints and any non-trivial approximation guarantee. These results hold even for planar bipartite polymatrix games with degree 3 and at most 7 strategies per player, and all non-trivial approximation guarantees. These results stand in contrast to similar results for bimatrix games, which obviously need a non-constant number of actions, and which rely on stronger complexity-theoretic conjectures such as the exponential time hypothesis. In the second part, we provide a deterministic QPTAS for interaction graphs with bounded treewidth and with logarithmically many actions per player that can compute constrained approximate equilibria for a wide family of constraints that cover many of the constraints dealt with in the first part.
Probabilistically-Shaped Coded Modulation with Hard Decision Decoding for Coherent Optical Systems
Venue: arXiv cs.IT 2017
Year: 2017

We consider probabilistic shaping to maximize the achievable information rate of coded modulation (CM) with hard decision decoding. The proposed scheme using binary staircase codes outperforms its uniform CM counterpart by more than 1.3 dB for 64-QAM and 5 bits/symbol.
A Time-Vertex Signal Processing Framework
Venue: arXiv cs.LG 2017
Year: 2017

An emerging way to deal with high-dimensional non-euclidean data is to assume that the underlying structure can be captured by a graph. Recently, ideas have begun to emerge related to the analysis of time-varying graph signals. This work aims to elevate the notion of joint harmonic analysis to a full-fledged framework denoted as Time-Vertex Signal Processing, that links together the time-domain signal processing techniques with the new tools of graph signal processing. This entails three main contributions: (a) We provide a formal motivation for harmonic time-vertex analysis as an analysis tool for the state evolution of simple Partial Differential Equations on graphs. (b) We improve the accuracy of joint filtering operators by up-to two orders of magnitude. (c) Using our joint filters, we construct time-vertex dictionaries analyzing the different scales and the local time-frequency content of a signal. The utility of our tools is illustrated in numerous applications and datasets, such as dynamic mesh denoising and classification, still-video inpainting, and source localization in seismic events. Our results suggest that joint analysis of time-vertex signals can bring benefits to regression and learning.
Transmit Array Interpolation for DOA Estimation via Tensor Decomposition in 2D MIMO Radar
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we propose a two-dimensional (2D) joint transmit array interpolation and beamspace design for planar array mono-static multiple-input-multiple-output (MIMO) radar for direction-of-arrival (DOA) estimation via tensor modeling. Our underlying idea is to map the transmit array to a desired array and suppress the transmit power outside the spatial sector of interest. In doing so, the signal-tonoise ratio is improved at the receive array. Then, we fold the received data along each dimension into a tensorial structure and apply tensor-based methods to obtain DOA estimates. In addition, we derive a close-form expression for DOA estimation bias caused by interpolation errors and argue for using a specially designed look-up table to compensate the bias. The corresponding Cramer-Rao Bound (CRB) is also derived. Simulation results are provided to show the performance of the proposed method and compare its performance to CRB.
Max-Pooling Loss Training of Long Short-Term Memory Networks for Small-Footprint Keyword Spotting
Venue: arXiv cs.CL 2017
Year: 2017

We propose a max-pooling based loss function for training Long Short-Term Memory (LSTM) networks for small-footprint keyword spotting (KWS), with low CPU, memory, and latency requirements. The max-pooling loss training can be further guided by initializing with a cross-entropy loss trained network. A posterior smoothing based evaluation approach is employed to measure keyword spotting performance. Our experimental results show that LSTM models trained using cross-entropy loss or max-pooling loss outperform a cross-entropy loss trained baseline feed-forward Deep Neural Network (DNN). In addition, max-pooling loss trained LSTM with randomly initialized network performs better compared to cross-entropy loss trained LSTM. Finally, the max-pooling loss trained LSTM initialized with a cross-entropy pre-trained network shows the best performance, which yields $67.6\%$ relative reduction compared to baseline feed-forward DNN in Area Under the Curve (AUC) measure.
Stock Volatility Prediction Using Recurrent Neural Networks with Sentiment Analysis
Venue: arXiv cs.SI 2017
Year: 2017

In this paper, we propose a model to analyze sentiment of online stock forum and use the information to predict the stock volatility in the Chinese market. We have labeled the sentiment of the online financial posts and make the dataset public available for research. By generating a sentimental dictionary based on financial terms, we develop a model to compute the sentimental score of each online post related to a particular stock. Such sentimental information is represented by two sentiment indicators, which are fused to market data for stock volatility prediction by using the Recurrent Neural Networks (RNNs). Empirical study shows that, comparing to using RNN only, the model performs significantly better with sentimental indicators.
Density Evolution on a Class of Smeared Random Graphs: A Theoretical Framework for Fast MRI
Venue: arXiv cs.IT 2017
Year: 2017

We introduce a new ensemble of random bipartite graphs, which we term the `smearing ensemble', where each left node is connected to some number of consecutive right nodes. Such graphs arise naturally in the recovery of sparse wavelet coefficients when signal acquisition is in the Fourier domain, such as in magnetic resonance imaging (MRI). Graphs from this ensemble exhibit small, structured cycles with high probability, rendering current techniques for determining iterative decoding thresholds inapplicable. In this paper, we develop a theoretical platform to analyze and evaluate the effects of smearing-based structure. Despite the existence of these small cycles, we derive exact density evolution recurrences for iterative decoding on graphs with smear-length two. Further, we give lower bounds on the performance of a much larger class from the smearing ensemble, and provide numerical experiments showing tight agreement between empirical thresholds and those determined by our bounds. Finally, we describe a system architecture to recover sparse wavelet representations in the MRI setting, giving explicit thresholds on the minimum number of Fourier samples needing to be acquired for the $1$-stage Haar wavelet setting. In particular, we show that $K$-sparse $1$-stage Haar wavelet coefficients of an $n$-dimensional signal can be recovered using $2.63K$ Fourier domain samples asymptotically using $\mathcal{O}(K\log{K})$ operations.
Metacognitive Learning Approach for Online Tool Condition Monitoring
Venue: arXiv cs.AI 2017
Year: 2017

As manufacturing processes become increasingly automated, so should tool condition monitoring (TCM) as it is impractical to have human workers monitor the state of the tools continuously. Tool condition is crucial to ensure the good quality of products: Worn tools affect not only the surface quality but also the dimensional accuracy, which means higher reject rate of the products. Therefore, there is an urgent need to identify tool failures before it occurs on the fly. While various versions of intelligent tool condition monitoring have been proposed, most of them suffer from a cognitive nature of traditional machine learning algorithms. They focus on the how to learn process without paying attention to other two crucial issues: what to learn, and when to learn. The what to learn and the when to learn provide self regulating mechanisms to select the training samples and to determine time instants to train a model. A novel tool condition monitoring approach based on a psychologically plausible concept, namely the metacognitive scaffolding theory, is proposed and built upon a recently published algorithm, recurrent classifier (rClass). The learning process consists of three phases: what to learn, how to learn, when to learn and makes use of a generalized recurrent network structure as a cognitive component. Experimental studies with real-world manufacturing data streams were conducted where rClass demonstrated the highest accuracy while retaining the lowest complexity over its counterparts.