OpenRaiser/Intern-Atlas huggingface dataset:
The Extreme Value Machine
Venue: arXiv cs.LG 2017
Year: 2017

It is often desirable to be able to recognize when inputs to a recognition function learned in a supervised manner correspond to classes unseen at training time. With this ability, new class labels could be assigned to these inputs by a human operator, allowing them to be incorporated into the recognition function --- ideally under an efficient incremental update mechanism. While good algorithms that assume inputs from a fixed set of classes exist, e.g., artificial neural networks and kernel machines, it is not immediately obvious how to extend them to perform incremental learning in the presence of unknown query classes. Existing algorithms take little to no distributional information into account when learning recognition functions and lack a strong theoretical foundation. We address this gap by formulating a novel, theoretically sound classifier --- the Extreme Value Machine (EVM). The EVM has a well-grounded interpretation derived from statistical Extreme Value Theory (EVT), and is the first classifier to be able to perform nonlinear kernel-free variable bandwidth incremental learning. Compared to other classifiers in the same deep network derived feature space, the EVM is accurate and efficient on an established benchmark partition of the ImageNet dataset.
Filtrated Algebraic Subspace Clustering
Venue: arXiv cs.CV 2017
Year: 2017

Subspace clustering is the problem of clustering data that lie close to a union of linear subspaces. In the abstract form of the problem, where no noise or other corruptions are present, the data are assumed to lie in general position inside the algebraic variety of a union of subspaces, and the objective is to decompose the variety into its constituent subspaces. Prior algebraic-geometric approaches to this problem require the subspaces to be of equal dimension, or the number of subspaces to be known. Subspaces of arbitrary dimensions can still be recovered in closed form, in terms of all homogeneous polynomials of degree $m$ that vanish on their union, when an upper bound m on the number of the subspaces is given. In this paper, we propose an alternative, provably correct, algorithm for addressing a union of at most $m$ arbitrary-dimensional subspaces, based on the idea of descending filtrations of subspace arrangements. Our algorithm uses the gradient of a vanishing polynomial at a point in the variety to find a hyperplane containing the subspace S passing through that point. By intersecting the variety with this hyperplane, we obtain a subvariety that contains S, and recursively applying the procedure until no non-trivial vanishing polynomial exists, our algorithm eventually identifies S. By repeating this procedure for other points, our algorithm eventually identifies all the subspaces by returning a basis for their orthogonal complement. Finally, we develop a variant of the abstract algorithm, suitable for computations with noisy data. We show by experiments on synthetic and real data that the proposed algorithm outperforms state-of-the-art methods on several occasions, thus demonstrating the merit of the idea of filtrations.
Hybrid VCSPs with crisp and conservative valued templates
Venue: arXiv cs.CC 2017
Year: 2017

A constraint satisfaction problem (CSP) is a problem of computing a homomorphism ${\bf R} \rightarrow {\bf Γ}$ between two relational structures. Analyzing its complexity has been a very fruitful research direction, especially for fixed template CSPs, denoted $CSP({\bf Γ})$, in which the right side structure ${\bf Γ}$ is fixed and the left side structure ${\bf R}$ is unconstrained. Recently, the hybrid setting, written $CSP_{\mathcal{H}}({\bf Γ})$, where both sides are restricted simultaneously, attracted some attention. It assumes that ${\bf R}$ is taken from a class of relational structures $\mathcal{H}$ that additionally is closed under inverse homomorphisms. The last property allows to exploit algebraic tools that have been developed for fixed template CSPs. The key concept that connects hybrid CSPs with fixed-template CSPs is the so called "lifted language". Namely, this is a constraint language ${\bf Γ}_{\bf R}$ that can be constructed from an input ${\bf R}$. The tractability of that language for any input ${\bf R}\in\mathcal{H}$ is a necessary condition for the tractability of the hybrid problem. In the first part we investigate templates ${\bf Γ}$ for which the latter condition is not only necessary, but also is sufficient. We call such templates ${\bf Γ}$ widely tractable. For this purpose, we construct from ${\bf Γ}$ a new finite relational structure ${\bf Γ}'$ and define $\mathcal{H}_0$ as a class of structures homomorphic to ${\bf Γ}'$. We prove that wide tractability is equivalent to the tractability of $CSP_{\mathcal{H}_0}({\bf Γ})$. Our proof is based on the key observation that ${\bf R}$ is homomorphic to ${\bf Γ}'$ if and only if the core of ${\bf Γ}_{\bf R}$ is preserved by a Siggers polymorphism. Analogous result is shown for valued conservative CSPs.
Impact of Node Speed on Throughput of Energy-Constrained Mobile Networks with Wireless Power Transfer
Venue: arXiv cs.IT 2017
Year: 2017

A wireless charging station (WCS) transfers energy wirelessly to mobile nodes within its charging region. This paper investigates the impact of node speed on the throughput of WCS overlaid mobile networks when packet transmissions are constrained by the energy status of each node. The energy provision for each node depends on its moving speed. A slow-moving node outside the charging region is unable to receive energy from WCSs for a long time, while one inside the charging region consistently recharges the battery. Reflecting on these phenomena, we design a two-dimensional Markov chain, where the states respectively represent the remaining energy and the distance to the nearest WCS. Solving this enables the following theoretic insights. Firstly, the throughput is a non-decreasing function of node speed. With faster node speed, the throughput converges to that of the independent and identically distributed (i.i.d.) mobility model where nodes can move anywhere without being restricted by their previous positions. Secondly, if the battery capacity of each node is infinite, the throughput is equivalent to that of the i.i.d. mobility model regardless of node speed. Finally, the throughput scaling is calculated as Theta(min(1, m/n)c^{\min(1,m/n))), where n and m represent the number of nodes and WCSs, respectively.
Extensions of the I-MMSE Relation
Venue: arXiv cs.IT 2017
Year: 2017

Unveiling a fundamental link between information theory and estimation theory, the I-MMSE relation by Guo, Shamai and Verdu~\cite{gu05}, together with its numerous extensions, has great theoretical significance and various practical applications. On the other hand, its influences to date have been restricted to channels without feedback or memory, due to the absence of its extensions to such channels. In this paper, we propose extensions of the I-MMSE relation to discrete-time and continuous-time Gaussian channels with feedback and/or memory. Our approach is based on a very simple observation, which can be applied to other scenarios, such as a simple and direct proof of the classical de Bruijn's identity.
A new framework for dynamical models on multiplex networks
Venue: arXiv cs.SI 2017
Year: 2017

Many complex systems have natural representations as multi-layer networks. While these formulations retain more information than standard single-layer network models, there is not yet a fully developed theory for computing network metrics and statistics on these objects. We introduce a family of models of multiplex processes motivated by dynamical applications and investigate the properties of their spectra both theoretically and computationally. We study special cases of multiplex diffusion and Markov dynamics, using the spectral results to compute their rates of convergence. We use our framework to define a version of multiplex eigenvector centrality, which generalizes some existing notions in the literature. Last, we compare our operator to structurally-derived models on synthetic and real-world networks, helping delineate the contexts in which the different frameworks are appropriate.
Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey
Venue: arXiv cs.SY 2017
Year: 2017

We survey incremental methods for minimizing a sum $\sum_{i=1}^mf_i(x)$ consisting of a large number of convex component functions $f_i$. Our methods consist of iterations applied to single components, and have proved very effective in practice. We introduce a unified algorithmic framework for a variety of such methods, some involving gradient and subgradient iterations, which are known, and some involving combinations of subgradient and proximal methods, which are new and offer greater flexibility in exploiting the special structure of $f_i$. We provide an analysis of the convergence and rate of convergence properties of these methods, including the advantages offered by randomization in the selection of components. We also survey applications in inference/machine learning, signal processing, and large-scale and distributed optimization.
On the moment distance of Poisson processes
Venue: arXiv cs.DM 2017
Year: 2017

Consider the distance between two i.i.d. and independent Poisson processes with arrival rate $λ>0$ and respective arrival times $X_1,X_2,\dots$ and $Y_1,Y_2,\dots$ on a line. We give a closed analytical formula for the %expected distance to the power $a$ $\E{|X_{k+r}-Y_k|^a}, $ for any integer $k\ge 1, r\ge 0$ and $a\ge 1.$ The expected difference of the arrival times to the power $a$ between two i.i.d. and independent Poisson processes we represent as the combination of the Pochhammer polynomials. Especially, for $r=0$ and any positive integer $a,$ the following identity is valid $$ \E{|X_k-Y_k|^a}=\frac{a!}{λ^a}\frac{Γ\left(\frac{a}{2}+k\right)}{Γ(k)Γ\left(\frac{a}{2}+1\right)}, $$ where $Γ(z)$ is Gamma function.
Edge Bipartization faster than $2^k$
Venue: arXiv cs.DS 2017
Year: 2017

In the Edge Bipartization problem one is given an undirected graph $G$ and an integer $k$, and the question is whether $k$ edges can be deleted from $G$ so that it becomes bipartite. In 2006, Guo et al. [J. Comput. Syst. Sci., 72(8):1386-1396, 2006] proposed an algorithm solving this problem in time $O(2^k m^2)$; today, this algorithm is a textbook example of an application of the iterative compression technique. Despite extensive progress in the understanding of the parameterized complexity of graph separation problems in the recent years, no significant improvement upon this result has been yet reported. We present an algorithm for Edge Bipartization that works in time $O(1.977^k nm)$, which is the first algorithm with the running time dependence on the parameter better than $2^k$. To this end, we combine the general iterative compression strategy of Guo et al. [J. Comput. Syst. Sci., 72(8):1386-1396, 2006], the technique proposed by Wahlstrom [SODA 2014, 1762-1781] of using a polynomial-time solvable relaxation in the form of a Valued Constraint Satisfaction Problem to guide a bounded-depth branching algorithm, and an involved Measure & Conquer analysis of the recursion tree.
On the Polytope Escape Problem for Continuous Linear Dynamical Systems
Venue: arXiv cs.CC 2017
Year: 2017

The Polyhedral Escape Problem for continuous linear dynamical systems consists of deciding, given an affine function $f: \mathbb{R}^{d} \rightarrow \mathbb{R}^{d}$ and a convex polyhedron $\mathcal{P} \subseteq \mathbb{R}^{d}$, whether, for some initial point $\boldsymbol{x}_{0}$ in $\mathcal{P}$, the trajectory of the unique solution to the differential equation $\dot{\boldsymbol{x}}(t)=f(\boldsymbol{x}(t))$, $\boldsymbol{x}(0)=\boldsymbol{x}_{0}$, is entirely contained in $\mathcal{P}$. We show that this problem is decidable, by reducing it in polynomial time to the decision version of linear programming with real algebraic coefficients, thus placing it in $\exists \mathbb{R}$, which lies between NP and PSPACE. Our algorithm makes use of spectral techniques and relies among others on tools from Diophantine approximation.
Quantifying Controversy in Social Media
Venue: arXiv cs.SI 2017
Year: 2017

Which topics spark the most heated debates on social media? Identifying those topics is not only interesting from a societal point of view, but also allows the filtering and aggregation of social media content for disseminating news stories. In this paper, we perform a systematic methodological study of controversy detection by using the content and the network structure of social media. Unlike previous work, rather than study controversy in a single hand-picked topic and use domain specific knowledge, we take a general approach to study topics in any domain. Our approach to quantifying controversy is based on a graph-based three-stage pipeline, which involves (i) building a conversation graph about a topic; (ii) partitioning the conversation graph to identify potential sides of the controversy; and (iii) measuring the amount of controversy from characteristics of the graph. We perform an extensive comparison of controversy measures, different graph-building approaches, and data sources. We use both controversial and non-controversial topics on Twitter, as well as other external datasets. We find that our new random-walk-based measure outperforms existing ones in capturing the intuitive notion of controversy, and show that content features are vastly less helpful in this task.
Converse Bounds for Entropy-Constrained Quantization Via a Variational Entropy Inequality
Venue: arXiv cs.IT 2017
Year: 2017

We derive a lower bound on the smallest output entropy that can be achieved via vector quantization of a $d$-dimensional source with given expected $r$th-power distortion. Specialized to the one-dimensional case, and in the limit of vanishing distortion, this lower bound converges to the output entropy achieved by a uniform quantizer, thereby recovering the result by Gish and Pierce that uniform quantizers are asymptotically optimal as the allowed distortion tends to zero. Our lower bound holds for all $d$-dimensional memoryless sources having finite differential entropy and whose integer part has finite entropy. In contrast to Gish and Pierce, we do not require any additional constraints on the continuity or decay of the source probability density function. For one-dimensional sources, the derivation of the lower bound reveals a necessary condition for a sequence of quantizers to be asymptotically optimal as the allowed distortion tends to zero. This condition implies that any sequence of asymptotically-optimal almost-regular quantizers must converge to a uniform quantizer as the allowed distortion tends to zero.
Coordinated Electric Vehicle Charging Control with Aggregator Power Trading and Indirect Load Control
Venue: arXiv cs.SY 2017
Year: 2017

Due to the increasing concern for greenhouse gas emissions and fossil fuel security, electric vehicles (EVs) have attracted much attention in recent years. EVs can aggregate together constituting the vehicle-to-grid system. Coordination of EVs is beneficial to the power system in many ways. In this paper, we formulate a novel large-scale EV charging problem with energy trading in order to maximize the aggregator profit. This problem is non-convex and can be solved with a centralized iterative approach. To overcome the computation complexity issue brought by the non-convexity, we develop a distributed optimization-based heuristic. To evaluate our proposed approach, a modified IEEE 118 bus testing system is employed with 10 aggregators serving 30 000 EVs. The simulation results indicate that our proposed distributed heuristic with energy trading can effectively increase the total profit of aggregators. In addition, the proposed distributed optimization-based heuristic strategy can achieve near-optimal performance.
Characterization of metrics induced by hierarchical posets
Venue: arXiv cs.IT 2017
Year: 2017

In this paper we consider metrics determined by hierarchical posets and give explicit formulae for the main parameters of a linear code: the minimum distance and the packing, covering and Chebyshev radii of a code. We also present ten characterizations of hierarchical poset metrics, including new characterizations and simple new proofs to the known ones.
On the convergence of the sparse possibilistic c-means algorithm
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, a convergence proof for the recently proposed sparse possibilistic c-means (SPCM) algorithm is provided, utilizing the celebrated Zangwill convergence theorem. It is shown that the iterative sequence generated by SPCM converges to a stationary point or there exists a subsequence of it that converges to a stationary point of the cost function of the algorithm.
Cost Sensitive Learning of Deep Feature Representations from Imbalanced Data
Venue: arXiv cs.CV 2017
Year: 2017

Class imbalance is a common problem in the case of real-world object detection and classification tasks. Data of some classes is abundant making them an over-represented majority, and data of other classes is scarce, making them an under-represented minority. This imbalance makes it challenging for a classifier to appropriately learn the discriminating boundaries of the majority and minority classes. In this work, we propose a cost sensitive deep neural network which can automatically learn robust feature representations for both the majority and minority classes. During training, our learning procedure jointly optimizes the class dependent costs and the neural network parameters. The proposed approach is applicable to both binary and multi-class problems without any modification. Moreover, as opposed to data level approaches, we do not alter the original data distribution which results in a lower computational cost during the training process. We report the results of our experiments on six major image classification datasets and show that the proposed approach significantly outperforms the baseline algorithms. Comparisons with popular data sampling techniques and cost sensitive classifiers demonstrate the superior performance of our proposed method.
A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and Few Random Positions
Venue: arXiv cs.GT 2017
Year: 2017

We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph $G = (V, E)$, with local rewards $r: E \to \ZZ$, and three types of positions: black $V_B$, white $V_W$, and random $V_R$ forming a partition of $V$. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, or not, even when $|V_R|=0$. In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this paper, we show that BWR-games with a constant number of random positions can be solved in pseudo-polynomial time. More precisely, in any BWR-game with $|V_R|=O(1)$, a saddle point in uniformly optimal pure stationary strategies can be found in time polynomial in $|V_W|+|V_B|$, the maximum absolute local reward, and the common denominator of the transition probabilities.
The GAP Benchmark Suite
Venue: arXiv cs.DC 2017
Year: 2017

We present a graph processing benchmark suite with the goal of helping to standardize graph processing evaluations. Fewer differences between graph processing evaluations will make it easier to compare different research efforts and quantify improvements. The benchmark not only specifies graph kernels, input graphs, and evaluation methodologies, but it also provides optimized baseline implementations. These baseline implementations are representative of state-of-the-art performance, and thus new contributions should outperform them to demonstrate an improvement. The input graphs are sized appropriately for shared memory platforms, but any implementation on any platform that conforms to the benchmark's specifications could be compared. This benchmark suite can be used in a variety of settings. Graph framework developers can demonstrate the generality of their programming model by implementing all of the benchmark's kernels and delivering competitive performance on all of the benchmark's graphs. Algorithm designers can use the input graphs and the baseline implementations to demonstrate their contribution. Platform designers and performance analysts can use the suite as a workload representative of graph processing.
Probabilistic Asynchronous Arbitrary Pattern Formation
Venue: arXiv cs.DC 2017
Year: 2017

We propose a new probabilistic pattern formation algorithm for oblivious mobile robots that operates inthe ASYNC model. Unlike previous work, our algorithm makes no assumptions about the local coordinatesystems of robots (the robots do not share a common "North" nor a common "Right"), yet it preserves theability from any initial configuration that contains at least 5 robots to form any general pattern (and not justpatterns that satisfy symmetricity predicates). Our proposal also gets rid of the previous assumption (in thesame model) that robots do not pause while moving (so, our robots really are fully asynchronous), and theamount of randomness is kept low -- a single random bit per robot per Look-Compute-Move cycle is used.Our protocol consists in the combination of two phases, a probabilistic leader election phase, and a deterministicpattern formation one. As the deterministic phase does not use chirality, it may be of independentinterest in the deterministic context. A noteworthy feature of our algorithm is the ability to form patternswith multiplicity points (except the gathering case due to impossibility results), a new feature in the contextof pattern formation that we believe is an important asset of our approach.
Multi-armed Bandit Problem with Known Trend
Venue: arXiv cs.LG 2017
Year: 2017

We consider a variant of the multi-armed bandit model, which we call multi-armed bandit problem with known trend, where the gambler knows the shape of the reward function of each arm but not its distribution. This new problem is motivated by different online problems like active learning, music and interface recommendation applications, where when an arm is sampled by the model the received reward change according to a known trend. By adapting the standard multi-armed bandit algorithm UCB1 to take advantage of this setting, we propose the new algorithm named A-UCB that assumes a stochastic model. We provide upper bounds of the regret which compare favourably with the ones of UCB1. We also confirm that experimentally with different simulations