OpenRaiser/Intern-Atlas huggingface dataset:
Unperturbed Schelling segregation in two or three dimensions
Venue: arXiv cs.MA 2016
Year: 2016

Schelling's model of segregation, first described in 1969, has become one of the best known models of self-organising behaviour. While Schelling's explicit concern was to understand the mechanisms underlying racial segregation in large cities from a game theoretic perspective, the model should be seen as one of a family, arising in fields as diverse as statistical mechanics, neural networks and the social sciences, and which are concerned with interacting populations situated on network structures. Despite extensive study, however, the (unperturbed) Schelling model has largely resisted rigorous analysis, prior results in the literature generally pertaining to variants of the model in which noise is introduced into the dynamics of the system, the resulting model then being amenable to standard techniques from statistical mechanics or stochastic evolutionary game theory. A series of recent papers (one by Brandt, Immorlica, Kamath, and Kleinberg, and two by the authors), has seen the first rigorous analysis of the one dimensional version of the unperturbed model. Here we provide the first rigorous analysis of the two and three dimensional unperturbed models, establishing most of the phase diagram, and answering a challenge from a recent paper by Brandt, Immorlica, Kamath, and Kleinberg.
Bio-inspired Unsupervised Learning of Visual Features Leads to Robust Invariant Object Recognition
Venue: arXiv cs.CV 2016
Year: 2016

Retinal image of surrounding objects varies tremendously due to the changes in position, size, pose, illumination condition, background context, occlusion, noise, and nonrigid deformations. But despite these huge variations, our visual system is able to invariantly recognize any object in just a fraction of a second. To date, various computational models have been proposed to mimic the hierarchical processing of the ventral visual pathway, with limited success. Here, we show that the association of both biologically inspired network architecture and learning rule significantly improves the models' performance when facing challenging invariant object recognition problems. Our model is an asynchronous feedforward spiking neural network. When the network is presented with natural images, the neurons in the entry layers detect edges, and the most activated ones fire first, while neurons in higher layers are equipped with spike timing-dependent plasticity. These neurons progressively become selective to intermediate complexity visual features appropriate for object categorization. The model is evaluated on 3D-Object and ETH-80 datasets which are two benchmarks for invariant object recognition, and is shown to outperform state-of-the-art models, including DeepConvNet and HMAX. This demonstrates its ability to accurately recognize different instances of multiple object classes even under various appearance conditions (different views, scales, tilts, and backgrounds). Several statistical analysis techniques are used to show that our model extracts class specific and highly informative features.
A Framework for Robust Assessment of Power Grid Stability and Resiliency
Venue: arXiv cs.SY 2016
Year: 2016

Security assessment of large-scale, strongly nonlinear power grids containing thousands to millions of interacting components is a computationally expensive task. Targeting at reducing the computational cost, this paper introduces a framework for constructing a robust assessment toolbox that can provide mathematically rigorous certificates for the grids' stability in the presence of variations in power injections, and for the grids' ability to withstand a bunch sources of faults. By this toolbox we can "off-line" screen a wide range of contingencies or power injection profiles, without reassessing the system stability on a regular basis. In particular, we formulate and solve two novel robust stability and resiliency assessment problems of power grids subject to the uncertainty in equilibrium points and uncertainty in fault-on dynamics. Furthermore, we bring in the quadratic Lyapunov functions approach to transient stability assessment, offering real-time construction of stability/resiliency certificates and real-time stability assessment. The effectiveness of the proposed techniques is numerically illustrated on a number of IEEE test cases.
The maximum-likelihood decoding threshold for graphic codes
Venue: arXiv cs.IT 2016
Year: 2016

For a class $\mathcal{C}$ of binary linear codes, we write $θ_{\mathcal{C}}\colon (0,1) \to [0,\frac{1}{2}]$ for the maximum-likelihood decoding threshold function of $\mathcal{C}$, the function whose value at $R \in (0,1)$ is the largest bit-error rate $p$ that codes in $\mathcal{C}$ can tolerate with a negligible probability of maximum-likelihood decoding error across a binary symmetric channel. We show that, if $\mathcal{C}$ is the class of cycle codes of graphs, then $θ_{\mathcal{C}}(R) \le \frac{(1-\sqrt{R})^2}{2(1+R)}$ for each $R$, and show that equality holds only when $R$ is asymptotically achieved by cycle codes of regular graphs.
Compressive Random Access Using A Common Overloaded Control Channel
Venue: arXiv cs.IT 2016
Year: 2016

We introduce a "one shot" random access procedure where users can send a message without a priori synchronizing with the network. In this procedure a common overloaded control channel is used to jointly detect sparse user activity and sparse channel profiles. The detected information is subsequently used to demodulate the data in dedicated frequency slots. We analyze the system theoretically and provide a link between achievable rates and standard compressing sensing estimates in terms of explicit expressions and scaling laws. Finally, we support our findings with simulations in an LTE-A-like setting allowing "one shot" sparse random access of 100 users in 1ms.
User Attraction via Wireless Charging in Cellular Networks
Venue: arXiv cs.IT 2016
Year: 2016

A strong motivation of charging depleted battery can be an enabler for network capacity increase. In this light we propose a spatial attraction cellular network (SAN) consisting of macro cells overlaid with small cell base stations that wirelessly charge user batteries. Such a network makes battery depleting users move toward the vicinity of small cell base stations. With a fine adjustment of charging power, this user spatial attraction (SA) improves in spectral efficiency as well as load balancing. We jointly optimize both enhancements thanks to SA, and derive the corresponding optimal charging power in a closed form by using a stochastic geometric approach.
How do you revise your belief set with %$;@*?
Venue: arXiv cs.AI 2016
Year: 2016

In the classic AGM belief revision theory, beliefs are static and do not change their own shape. For instance, if p is accepted by a rational agent, it will remain p to the agent. But such rarely happens to us. Often, when we accept some information p, what is actually accepted is not the whole p, but only a portion of it; not necessarily because we select the portion but because p must be perceived. Only the perceived p is accepted; and the perception is subject to what we already believe (know). What may, however, happen to the rest of p that initially escaped our attention? In this work we argue that the invisible part is also accepted to the agent, if only unconsciously. Hence some parts of p are accepted as visible, while some other parts as latent, beliefs. The division is not static. As the set of beliefs changes, what were hidden may become visible. We present a perception-based belief theory that incorporates latent beliefs.
Timed Orchestration for Component-based Systems
Venue: arXiv cs.FL 2016
Year: 2016

Individual machines in flexible production lines explicitly expose capabilities at their interfaces by means of parametric skills. Given such a set of configurable machines, a line integrator is faced with the problem of finding and tuning parameters for each machine such that the overall production line implements given safety and temporal requirements in an optimized and robust fashion. We formalize this problem of configuring and orchestrating flexible production lines as a parameter synthesis problem for systems of parametric timed automata, where interactions are based on skills. Parameter synthesis problems for interaction-level LTL properties are translated to parameter synthesis problems for state-based safety properties. For safety properties, synthesis problems are solved by checking satisfiability of $\exists\forall$SMT constraints. For constraint generation, we provide a set of computationally cheap over-approximations of the set of reachable states, together with fence constructions as sufficient conditions for safety formulas. We demonstrate the feasibility of our approach by solving typical machine configuration problems as encountered in industrial automation.
On the Approximation Performance of Degree Heuristics for Matching
Venue: arXiv cs.DS 2016
Year: 2016

In the design of greedy algorithms for the maximum cardinality matching problem the utilization of degree information when selecting the next edge is a well established and successful approach. We define the class of "degree sensitive" greedy matching algorithms, which allows us to analyze many well-known heuristics, and provide tight approximation guarantees under worst case tie breaking. We exhibit algorithms in this class with optimal approximation guarantee for bipartite graphs. In particular the Karp-Sipser algorithm, which picks an edge incident with a degree-1 node if possible and otherwise an arbitrary edge, turns out to be optimal with approximation guarantee D/(2D-2), where D is the maximum degree.
Computational Cost Reduction in Learned Transform Classifications
Venue: arXiv cs.CV 2016
Year: 2016

We present a theoretical analysis and empirical evaluations of a novel set of techniques for computational cost reduction of classifiers that are based on learned transform and soft-threshold. By modifying optimization procedures for dictionary and classifier training, as well as the resulting dictionary entries, our techniques allow to reduce the bit precision and to replace each floating-point multiplication by a single integer bit shift. We also show how the optimization algorithms in some dictionary training methods can be modified to penalize higher-energy dictionaries. We applied our techniques with the classifier Learning Algorithm for Soft-Thresholding, testing on the datasets used in its original paper. Our results indicate it is feasible to use solely sums and bit shifts of integers to classify at test time with a limited reduction of the classification accuracy. These low power operations are a valuable trade off in FPGA implementations as they increase the classification throughput while decrease both energy consumption and manufacturing cost.
On Asymptotic Gate Complexity and Depth of Reversible Circuits Without Additional Memory
Venue: arXiv cs.ET 2016
Year: 2016

Reversible computation is one of the most promising emerging technologies of the future. The usage of reversible circuits in computing devices can lead to a significantly lower power consumption. In this paper we study reversible logic circuits consisting of NOT, CNOT and 2-CNOT gates. We introduce a set $F(n,q)$ of all transformations $\mathbb Z_2^n \to \mathbb Z_2^n$ that can be implemented by reversible circuits with $(n+q)$ inputs. We define the Shannon gate complexity function $L(n,q)$ and the depth function $D(n,q)$ as functions of $n$ and the number of additional inputs $q$. First, we prove general lower bounds for functions $L(n,q)$ and $D(n,q)$. Second, we introduce a new group theory based synthesis algorithm, which can produce a circuit $\mathfrak S$ without additional inputs and with the gate complexity $L(\mathfrak S) \leq 3n 2^{n+4}(1+o(1)) \mathop / \log_2 n$. Using these bounds, we state that almost every reversible circuit with no additional inputs, consisting of NOT, CNOT and 2-CNOT gates, implements a transformation from $F(n,0)$ with the gate complexity $L(n,0) \asymp n 2^n \mathop / \log_2 n$ and with the depth $D(n,0) \geq 2^n(1-o(1)) \mathop / (3\log_2 n)$.
Don't let Google know I'm lonely!
Venue: arXiv cs.CR 2016
Year: 2016

From buying books to finding the perfect partner, we share our most intimate wants and needs with our favourite online systems. But how far should we accept promises of privacy in the face of personal profiling? In particular we ask how can we improve detection of sensitive topic profiling by online systems? We propose a definition of privacy disclosure we call ε-indistinguishability from which we construct scalable, practical tools to assess an adversaries learning potential. We demonstrate our results using openly available resources, detecting a learning rate in excess of 98% for a range of sensitive topics during our experiments.
A new kernel-based approach for overparameterized Hammerstein system identification
Venue: arXiv cs.SY 2016
Year: 2016

In this paper we propose a new identification scheme for Hammerstein systems, which are dynamic systems consisting of a static nonlinearity and a linear time-invariant dynamic system in cascade. We assume that the nonlinear function can be described as a linear combination of $p$ basis functions. We reconstruct the $p$ coefficients of the nonlinearity together with the first $n$ samples of the impulse response of the linear system by estimating an $np$-dimensional overparameterized vector, which contains all the combinations of the unknown variables. To avoid high variance in these estimates, we adopt a regularized kernel-based approach and, in particular, we introduce a new kernel tailored for Hammerstein system identification. We show that the resulting scheme provides an estimate of the overparameterized vector that can be uniquely decomposed as the combination of an impulse response and $p$ coefficients of the static nonlinearity. We also show, through several numerical experiments, that the proposed method compares very favorably with two standard methods for Hammerstein system identification.
A survey on modeling of microgrids - from fundamental physics to phasors and voltage sources
Venue: arXiv cs.SY 2016
Year: 2016

Microgrids have been identified as key components of modern electrical systems to facilitate the integration of renewable distributed generation units. Their analysis and controller design requires the development of advanced (typically model-based) techniques naturally posing an interesting challenge to the control community. Although there are widely accepted reduced order models to describe the dynamic behavior of microgrids, they are typically presented without details about the reduction procedure---hampering the understanding of the physical phenomena behind them. Preceded by an introduction to basic notions and definitions in power systems, the present survey reviews key characteristics and main components of a microgrid. We introduce the reader to the basic functionality of DC/AC inverters, as well as to standard operating modes and control schemes of inverter-interfaced power sources in microgrid applications. Based on this exposition and starting from fundamental physics, we present detailed dynamical models of the main microgrid components. Furthermore, we clearly state the underlying assumptions which lead to the standard reduced model with inverters represented by controllable voltage sources, as well as static network and load representations, hence, providing a complete modular model derivation of a three-phase inverter-based microgrid.
Algorithms for the minimum sum coloring problem: a review
Venue: arXiv cs.DM 2016
Year: 2016

The Minimum Sum Coloring Problem (MSCP) is a variant of the well-known vertex coloring problem which has a number of AI related applications. Due to its theoretical and practical relevance, MSCP attracts increasing attention. The only existing review on the problem dates back to 2004 and mainly covers the history of MSCP and theoretical developments on specific graphs. In recent years, the field has witnessed significant progresses on approximation algorithms and practical solution algorithms. The purpose of this review is to provide a comprehensive inspection of the most recent and representative MSCP algorithms. To be informative, we identify the general framework followed by practical solution algorithms and the key ingredients that make them successful. By classifying the main search strategies and putting forward the critical elements of the reviewed methods, we wish to encourage future development of more powerful methods and motivate new applications.
Reliable Uplink Communication through Double Association in Wireless Heterogeneous Networks
Venue: arXiv cs.IT 2016
Year: 2016

We investigate methods for network association that improve the reliability of uplink transmissions in dense wireless heterogeneous networks. The stochastic geometry analysis shows that the double association, in which an uplink transmission is transmitted to a macro Base Station (BS) and small BS, significantly improves the probability of successful transmission.
Vandermonde Decomposition of Multilevel Toeplitz Matrices with Application to Multidimensional Super-Resolution
Venue: arXiv cs.IT 2016
Year: 2016

The Vandermonde decomposition of Toeplitz matrices, discovered by Carathéodory and Fejér in the 1910s and rediscovered by Pisarenko in the 1970s, forms the basis of modern subspace methods for 1D frequency estimation. Many related numerical tools have also been developed for multidimensional (MD), especially 2D, frequency estimation; however, a fundamental question has remained unresolved as to whether an analog of the Vandermonde decomposition holds for multilevel Toeplitz matrices in the MD case. In this paper, an affirmative answer to this question and a constructive method for finding the decomposition are provided when the matrix rank is lower than the dimension of each Toeplitz block. A numerical method for searching for a decomposition is also proposed when the matrix rank is higher. The new results are applied to studying MD frequency estimation within the recent super-resolution framework. A precise formulation of the atomic $\ell_0$ norm is derived using the Vandermonde decomposition. Practical algorithms for frequency estimation are proposed based on relaxation techniques. Extensive numerical simulations are provided to demonstrate the effectiveness of these algorithms compared to the existing atomic norm and subspace methods.
Smart Detector Cell: A Scalable All-Spin Circuit for Low Power Non-Boolean Pattern Recognition
Venue: arXiv cs.ET 2016
Year: 2016

We present a new circuit for non-Boolean recognition of binary images. Employing all-spin logic (ASL) devices, we design logic comparators and non-Boolean decision blocks for compact and efficient computation. By manipulation of fan-in number in different stages of the circuit, the structure can be extended for larger training sets or larger images. Operating based on the mainly similarity idea, the system is capable of constructing a mean image and compare it with a separate input image within a short decision time. Taking advantage of the non-volatility of ASL devices, the proposed circuit is capable of hybrid memory/logic operation. Compared with existing CMOS pattern recognition circuits, this work achieves a smaller footprint, lower power consumption, faster decision time and a lower operational voltage. To the best of our knowledge, this is the first fully spin-based complete pattern recognition circuit demonstrated using spintronic devices.
Hybrid IP/SDN networking: open implementation and experiment management tools
Venue: arXiv cs.NI 2016
Year: 2016

The introduction of SDN in large-scale IP provider networks is still an open issue and different solutions have been suggested so far. In this paper we propose a hybrid approach that allows the coexistence of traditional IP routing with SDN based forwarding within the same provider domain. The solution is called OSHI - Open Source Hybrid IP/SDN networking as we have fully implemented it combining and extending Open Source software. We discuss the OSHI system architecture and the design and implementation of advanced services like Pseudo Wires and Virtual Switches. In addition, we describe a set of Open Source management tools for the emulation of the proposed solution using either the Mininet emulator or distributed physical testbeds. We refer to this suite of tools as Mantoo (Management tools). Mantoo includes an extensible web-based graphical topology designer, which provides different layered network "views" (e.g. from physical links to service relationships among nodes). The suite can validate an input topology, automatically deploy it over a Mininet emulator or a distributed SDN testbed and allows access to emulated nodes by opening consoles in the web GUI. Mantoo provides also tools to evaluate the performance of the deployed nodes.
Evolutionary Cost-sensitive Extreme Learning Machine
Venue: arXiv cs.CV 2016
Year: 2016

Conventional extreme learning machines solve a Moore-Penrose generalized inverse of hidden layer activated matrix and analytically determine the output weights to achieve generalized performance, by assuming the same loss from different types of misclassification. The assumption may not hold in cost-sensitive recognition tasks, such as face recognition based access control system, where misclassifying a stranger as a family member may result in more serious disaster than misclassifying a family member as a stranger. Though recent cost-sensitive learning can reduce the total loss with a given cost matrix that quantifies how severe one type of mistake against another, in many realistic cases the cost matrix is unknown to users. Motivated by these concerns, this paper proposes an evolutionary cost-sensitive extreme learning machine (ECSELM), with the following merits: 1) to our best knowledge, it is the first proposal of ELM in evolutionary cost-sensitive classification scenario; 2) it well addresses the open issue of how to define the cost matrix in cost-sensitive learning tasks; 3) an evolutionary backtracking search algorithm is induced for adaptive cost matrix optimization. Experiments in a variety of cost-sensitive tasks well demonstrate the effectiveness of the proposed approaches, with about 5%~10% improvements.
Improved Microaneurysm Detection using Deep Neural Networks
Venue: arXiv cs.CV 2016
Year: 2016

In this work, we propose a novel microaneurysm (MA) detection for early diabetic retinopathy screening using color fundus images. Since MA usually the first lesions to appear as an indicator of diabetic retinopathy, accurate detection of MA is necessary for treatment. Each pixel of the image is classified as either MA or non-MA using a deep neural network with dropout training procedure using maxout activation function. No preprocessing step or manual feature extraction is required. Substantial improvements over standard MA detection method based on the pipeline of preprocessing, feature extraction, classification followed by post processing is achieved. The presented method is evaluated in publicly available Retinopathy Online Challenge (ROC) and Diaretdb1v2 database and achieved state-of-the-art accuracy.