OpenRaiser/Intern-Atlas huggingface dataset:
Denoising Autoencoders for fast Combinatorial Black Box Optimization
Venue: arXiv cs.NE 2015
Year: 2015

Estimation of Distribution Algorithms (EDAs) require flexible probability models that can be efficiently learned and sampled. Autoencoders (AE) are generative stochastic networks with these desired properties. We integrate a special type of AE, the Denoising Autoencoder (DAE), into an EDA and evaluate the performance of DAE-EDA on several combinatorial optimization problems with a single objective. We asses the number of fitness evaluations as well as the required CPU times. We compare the results to the performance to the Bayesian Optimization Algorithm (BOA) and RBM-EDA, another EDA which is based on a generative neural network which has proven competitive with BOA. For the considered problem instances, DAE-EDA is considerably faster than BOA and RBM-EDA, sometimes by orders of magnitude. The number of fitness evaluations is higher than for BOA, but competitive with RBM-EDA. These results show that DAEs can be useful tools for problems with low but non-negligible fitness evaluation costs.
A Unified Platform Enabling Power System Circuit Model Data Transfer Among Different Software
Venue: arXiv cs.SY 2015
Year: 2015

Diversity of software packages to simulate the power system circuits is considerable. It is challenging to transfer power system circuit model data (PSCMD) among different software tools and rebuild the same circuit in the second software environment. This paper proposes a unified platform (UP) where PSCMD are stored in a spreadsheet file with a defined format. Script-based PSCMD transfer applications, written in MATLAB, have been developed for a set of software to read the circuit model data from the UP spreadsheet and reconstruct the circuit in the destination software. This significantly eases the process of transferring circuit model data between each pair of software tools. In this paper ETAP, OpenDSS, Grid LabD, and DEW are considered. In order to test the developed PSCMD transfer applications, circuit model data of a test circuit and an actual sample circuit from a Californian utility company, both built in CYME, were exported into the spreadsheet file according to the UP format. Thereafter, circuit model data were imported successfully from the spreadsheet files into all above mentioned software using the PSCMD transfer applications developed for each software individually. Finally, load flow analysis is performed in all software and the obtained results match with each other.
Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
Venue: arXiv cs.LG 2015
Year: 2015

We analyze stochastic gradient descent for optimizing non-convex functions. In many cases for non-convex functions the goal is to find a reasonable local minimum, and the main concern is that gradient updates are trapped in saddle points. In this paper we identify strict saddle property for non-convex problem that allows for efficient optimization. Using this property we show that stochastic gradient descent converges to a local minimum in a polynomial number of iterations. To the best of our knowledge this is the first work that gives global convergence guarantees for stochastic gradient descent on non-convex functions with exponentially many local minima and saddle points. Our analysis can be applied to orthogonal tensor decomposition, which is widely used in learning a rich class of latent variable models. We propose a new optimization formulation for the tensor decomposition problem that has strict saddle property. As a result we get the first online algorithm for orthogonal tensor decomposition with global convergence guarantee.
Label optimal regret bounds for online local learning
Venue: arXiv cs.LG 2015
Year: 2015

We resolve an open question from (Christiano, 2014b) posed in COLT'14 regarding the optimal dependency of the regret achievable for online local learning on the size of the label set. In this framework the algorithm is shown a pair of items at each step, chosen from a set of $n$ items. The learner then predicts a label for each item, from a label set of size $L$ and receives a real valued payoff. This is a natural framework which captures many interesting scenarios such as collaborative filtering, online gambling, and online max cut among others. (Christiano, 2014a) designed an efficient online learning algorithm for this problem achieving a regret of $O(\sqrt{nL^3T})$, where $T$ is the number of rounds. Information theoretically, one can achieve a regret of $O(\sqrt{n \log L T})$. One of the main open questions left in this framework concerns closing the above gap. In this work, we provide a complete answer to the question above via two main results. We show, via a tighter analysis, that the semi-definite programming based algorithm of (Christiano, 2014a), in fact achieves a regret of $O(\sqrt{nLT})$. Second, we show a matching computational lower bound. Namely, we show that a polynomial time algorithm for online local learning with lower regret would imply a polynomial time algorithm for the planted clique problem which is widely believed to be hard. We prove a similar hardness result under a related conjecture concerning planted dense subgraphs that we put forth. Unlike planted clique, the planted dense subgraph problem does not have any known quasi-polynomial time algorithms. Computational lower bounds for online learning are relatively rare, and we hope that the ideas developed in this work will lead to lower bounds for other online learning scenarios as well.
On the Computation of the Galois Group of Linear Difference Equations
Venue: arXiv cs.SC 2015
Year: 2015

We present an algorithm that determines the Galois group of linear difference equations with rational function coefficients.
Network Coding for Cooperative Mobile Devices with Multiple Interfaces
Venue: arXiv cs.IT 2015
Year: 2015

Cooperation among mobile devices and utilizing multiple interfaces such as cellular and local area links simultaneously are promising to meet the increasing throughput demand over cellular links. In particular, when mobile devices are in the close proximity of each other and are interested in the same content, device-to-device connections such as WiFi-Direct, in addition to cellular links, can be utilized to construct a cooperative system. However, it is crucial to understand the potential of network coding for cooperating mobile devices with multiple interfaces. In this paper, we consider this problem, and (i) develop network coding schemes for cooperative mobile devices with multiple interfaces, and (ii) characterize the performance of network coding by using the number of transmissions to recover all packets as a performance metric.
Efficient Hardware Design and Implementation of Encrypted MIPS Processor
Venue: arXiv cs.CR 2015
Year: 2015

The paper describes the design and hardware implementation of 32-bit encrypted MIPS processor based on MIPS pipeline architecture. The organization of pipeline stages in such a way that pipeline can be clocked at high frequency. Encryption and Decryption blocks of data encryption standard (DES) cryptosystem and dependency among themselves are explained in detail with the help of block diagram. In order to increase the processor functionality and performance, especially for security applications we include three new instructions 32-bit LKLW, LKUW and CRYPT. The design has been synthesized at 40nm process technology targeting using Xilinx Virtex-6 device. The encrypted MIPS pipeline processor can work at 218MHz at synthesis level and 744MHz at simulation level.
Uniform Interpolation for Coalgebraic Fixpoint Logic
Venue: arXiv cs.LO 2015
Year: 2015

We use the connection between automata and logic to prove that a wide class of coalgebraic fixpoint logics enjoys uniform interpolation. To this aim, first we generalize one of the central results in coalgebraic automata theory, namely closure under projection, which is known to hold for weak-pullback preserving functors, to a more general class of functors, i.e.; functors with quasi-functorial lax extensions. Then we will show that closure under projection implies definability of the bisimulation quantifier in the language of coalgebraic fixpoint logic, and finally we prove the uniform interpolation theorem.
Financial Market Prediction
Venue: arXiv cs.CE 2015
Year: 2015

Given financial data from popular sites like Yahoo and the London Exchange, the presented paper attempts to model and predict stocks that can be considered "good investments". Stocks are characterized by 125 features ranging from gross domestic product to EDIBTA, and are labeled by discrepancies between stock and market price returns. An artificial neural network (Self-Organizing Map) is fitted to train on more than a million data points to predict "good investments" given testing stocks from 2013 and after.
An Unsupervised Method for Uncovering Morphological Chains
Venue: arXiv cs.CL 2015
Year: 2015

Most state-of-the-art systems today produce morphological analysis based only on orthographic patterns. In contrast, we propose a model for unsupervised morphological analysis that integrates orthographic and semantic views of words. We model word formation in terms of morphological chains, from base words to the observed words, breaking the chains into parent-child relations. We use log-linear models with morpheme and word-level features to predict possible parents, including their modifications, for each word. The limited set of candidate parents for each word render contrastive estimation feasible. Our model consistently matches or outperforms five state-of-the-art systems on Arabic, English and Turkish.
#FailedRevolutions: Using Twitter to Study the Antecedents of ISIS Support
Venue: arXiv cs.SI 2015
Year: 2015

Within a fairly short amount of time, the Islamic State of Iraq and Syria (ISIS) has managed to put large swaths of land in Syria and Iraq under their control. To many observers, the sheer speed at which this "state" was established was dumbfounding. To better understand the roots of this organization and its supporters we present a study using data from Twitter. We start by collecting large amounts of Arabic tweets referring to ISIS and classify them into pro-ISIS and anti-ISIS. This classification turns out to be easily done simply using the name variants used to refer to the organization: the full name and the description as "state" is associated with support, whereas abbreviations usually indicate opposition. We then "go back in time" by analyzing the historic timelines of both users supporting and opposing and look at their pre-ISIS period to gain insights into the antecedents of support. To achieve this, we build a classifier using pre-ISIS data to "predict", in retrospect, who will support or oppose the group. The key story that emerges is one of frustration with failed Arab Spring revolutions. ISIS supporters largely differ from ISIS opposition in that they refer a lot more to Arab Spring uprisings that failed. We also find temporal patterns in the support and opposition which seems to be linked to major news, such as reported territorial gains, reports on gruesome acts of violence, and reports on airstrikes and foreign intervention.
Approximating LZ77 in Small Space
Venue: arXiv cs.DS 2015
Year: 2015

Given a positive \(ε\leq 1\) and read-only access to a string \(S [1..n]\) whose LZ77 parse consists of $z$ phrases, with high probability we can build an LZ77-like parse of $S$ that consists of $\Oh{z / ε}$ phrases using $\Oh{n^{1 + ε}}$ time, $\Oh{n^{1 + ε} / B}$ I/Os (where $B$ is the size of a disk block) and $\Oh{z / ε}$ space.
Specification of Complex Structures in Distributed Service Function Chaining Using a YANG Data Model
Venue: arXiv cs.NI 2015
Year: 2015

While services benefit from distributed cloud centers running in isolation, allowing multiple centers to cooperate on implementing services unlocks the full power of distributed cloud computing. Distributed cloud services are typically set up by chaining together a number of functions that are specified with an implicit order. They can incorporate complex structures, e.g., include functions that classify and forward flows over distinct branches and functions that are traversed by certain types of flows but skipped by others. These requirements need specification techniques more powerful than existing graph-based ones. We present a context-free grammar for abstract description of service function chaining structures and a concrete syntax based on the YANG data modeling language that can easily be translated into an explicit configuration of service functions. Finally, we present examples of using our models for complex services within common use cases of service function chaining.
Representation Learning with Deep Extreme Learning Machines for Efficient Image Set Classification
Venue: arXiv cs.CV 2015
Year: 2015

Efficient and accurate joint representation of a collection of images, that belong to the same class, is a major research challenge for practical image set classification. Existing methods either make prior assumptions about the data structure, or perform heavy computations to learn structure from the data itself. In this paper, we propose an efficient image set representation that does not make any prior assumptions about the structure of the underlying data. We learn the non-linear structure of image sets with Deep Extreme Learning Machines (DELM) that are very efficient and generalize well even on a limited number of training samples. Extensive experiments on a broad range of public datasets for image set classification (Honda/UCSD, CMU Mobo, YouTube Celebrities, Celebrity-1000, ETH-80) show that the proposed algorithm consistently outperforms state-of-the-art image set classification methods both in terms of speed and accuracy.
Brain Tumor Segmentation: A Comparative Analysis
Venue: arXiv cs.CV 2015
Year: 2015

Five different threshold segmentation based approaches have been reviewed and compared over here to extract the tumor from set of brain images. This research focuses on the analysis of image segmentation methods, a comparison of five semi-automated methods have been undertaken for evaluating their relative performance in the segmentation of tumor. Consequently, results are compared on the basis of quantitative and qualitative analysis of respective methods. The purpose of this study was to analytically identify the methods, most suitable for application for a particular genre of problems. The results show that of the region growing segmentation performed better than rest in most cases.
Compositional Distributional Semantics with Long Short Term Memory
Venue: arXiv cs.CL 2015
Year: 2015

We are proposing an extension of the recursive neural network that makes use of a variant of the long short-term memory architecture. The extension allows information low in parse trees to be stored in a memory register (the `memory cell') and used much later higher up in the parse tree. This provides a solution to the vanishing gradient problem and allows the network to capture long range dependencies. Experimental results show that our composition outperformed the traditional neural-network composition on the Stanford Sentiment Treebank.
Optimal Pricing is Hard
Venue: arXiv cs.GT 2015
Year: 2015

We show that computing the revenue-optimal deterministic auction in unit-demand single-buyer Bayesian settings, i.e. the optimal item-pricing, is computationally hard even in single-item settings where the buyer's value distribution is a sum of independently distributed attributes, or multi-item settings where the buyer's values for the items are independent. We also show that it is intractable to optimally price the grand bundle of multiple items for an additive bidder whose values for the items are independent. These difficulties stem from implicit definitions of a value distribution. We provide three instances of how different properties of implicit distributions can lead to intractability: the first is a #P-hardness proof, while the remaining two are reductions from the SQRT-SUM problem of Garey, Graham, and Johnson. While simple pricing schemes can oftentimes approximate the best scheme in revenue, they can have drastically different underlying structure. We argue therefore that either the specification of the input distribution must be highly restricted in format, or it is necessary for the goal to be mere approximation to the optimal scheme's revenue instead of computing properties of the scheme itself.
Co-Utility: Self-Enforcing Protocols without Coordination Mechanisms
Venue: arXiv cs.GT 2015
Year: 2015

Performing some task among a set of agents requires the use of some protocol that regulates the interactions between them. If those agents are rational, they may try to subvert the protocol for their own benefit, in an attempt to reach an outcome that provides greater utility. We revisit the traditional notion of self-enforcing protocols implemented using existing game-theoretic solution concepts, we describe its shortcomings in real-world applications, and we propose a new notion of self-enforcing protocols, namely co-utile protocols. The latter represent a solution concept that can be implemented without a coordination mechanism in situations when traditional self-enforcing protocols need a coordination mechanism. Co-utile protocols are preferable in decentralized systems of rational agents because of their efficiency and fairness. We illustrate the application of co-utile protocols to information technology, specifically to preserving the privacy of query profiles of database/search engine users.
Multiuser Scheduling for Simultaneous Wireless Information and Power Transfer Systems
Venue: arXiv cs.IT 2015
Year: 2015

In this thesis, we study the downlink multiuser scheduling and power allocation problem for systems with simultaneous wireless information and power transfer (SWIPT). In the first part of the thesis, we focus on multiuser scheduling. We design optimal scheduling algorithms that maximize the long-term average system throughput under different fairness requirements, such as proportional fairness and equal throughput fairness. In particular, the algorithm designs are formulated as non-convex optimization problems which take into account the minimum required average sum harvested energy in the system. The problems are solved by using convex optimization techniques and the proposed optimization framework reveals the tradeoff between the long-term average system throughput and the sum harvested energy in multiuser systems with fairness constraints. Simulation results demonstrate that substantial performance gains can be achieved by the proposed optimization framework compared to existing suboptimal scheduling algorithms from the literature. In the second part of the thesis, we investigate the joint user scheduling and power allocation algorithm design for SWIPT systems. The algorithm design is formulated as a non-convex optimization problem which maximizes the achievable rate subject to a minimum required average power transfer. Subsequently, the non-convex optimization problem is reformulated by big-M method which can be solved optimally. Furthermore, we show that joint power allocation and user scheduling is an efficient way to enlarge the feasible trade-off region for improving the system performance in terms of achievable data rate and harvested energy.
Scalable Nuclear-norm Minimization by Subspace Pursuit Proximal Riemannian Gradient
Venue: arXiv cs.LG 2015
Year: 2015

Nuclear-norm regularization plays a vital role in many learning tasks, such as low-rank matrix recovery (MR), and low-rank representation (LRR). Solving this problem directly can be computationally expensive due to the unknown rank of variables or large-rank singular value decompositions (SVDs). To address this, we propose a proximal Riemannian gradient (PRG) scheme which can efficiently solve trace-norm regularized problems defined on real-algebraic variety $\mMLr$ of real matrices of rank at most $r$. Based on PRG, we further present a simple and novel subspace pursuit (SP) paradigm for general trace-norm regularized problems without the explicit rank constraint $\mMLr$. The proposed paradigm is very scalable by avoiding large-rank SVDs. Empirical studies on several tasks, such as matrix completion and LRR based subspace clustering, demonstrate the superiority of the proposed paradigms over existing methods.
Mobile Node Localization via Pareto Optimization: Algorithm and Fundamental Performance Limitations
Venue: arXiv cs.IT 2015
Year: 2015

Accurate estimation of the position of network nodes is essential, e.g., in localization, geographic routing, and vehicular networks. Unfortunately, typical positioning techniques based on ranging or on velocity and angular measurements are inherently limited. To overcome the limitations of specific positioning techniques, the fusion of multiple and heterogeneous sensor information is an appealing strategy. In this paper, we investigate the fundamental performance of linear fusion of multiple measurements of the position of mobile nodes, and propose a new distributed recursive position estimator. The Cramér-Rao lower bounds for the parametric and a-posteriori cases are investigated. The proposed estimator combines information coming from ranging, speed, and angular measurements, which is jointly fused by a Pareto optimization problem where the mean and the variance of the localization error are simultaneously minimized. A distinguished feature of the method is that it assumes a very simple dynamical model of the mobility and therefore it is applicable to a large number of scenarios providing good performance. The main challenge is the characterization of the statistical information needed to model the Fisher information matrix and the Pareto optimization problem. The proposed analysis is validated by Monte Carlo simulations, and the performance is compared to several Kalman-based filters, commonly employed for localization and sensor fusion. Simulation results show that the proposed estimator outperforms the traditional approaches that are based on the extended Kalman filter when no assumption on the model of motion is used. In such a scenario, better performance is achieved by the proposed method, but at the price of an increased computational complexity.
Dealing With 4-Variables by Resolution: An Improved MaxSAT Algorithm
Venue: arXiv cs.DS 2015
Year: 2015

We study techniques for solving the Maximum Satisfiability problem (MaxSAT). Our focus is on variables of degree 4. We identify cases for degree-4 variables and show how the resolution principle and the kernelization techniques can be nicely integrated to achieve more efficient algorithms for the MaxSAT problem. As a result, we present an algorithm of time $O^*(1.3248^k)$ for the MaxSAT problem, improving the previous best upper bound $O^*(1.358^k)$ by Ivan Bliznets and Alexander.
Broadcasting Correlated Vector Gaussians
Venue: arXiv cs.IT 2015
Year: 2015

The problem of sending two correlated vector Gaussian sources over a bandwidth-matched two-user scalar Gaussian broadcast channel is studied in this work, where each receiver wishes to reconstruct its target source under a covariance distortion constraint. We derive a lower bound on the optimal tradeoff between the transmit power and the achievable reconstruction distortion pair. Our derivation is based on a new bounding technique which involves the introduction of appropriate remote sources. Furthermore, it is shown that this lower bound is achievable by a class of hybrid schemes for the special case where the weak receiver wishes to reconstruct a scalar source under the mean squared error distortion constraint.