OpenRaiser/Intern-Atlas huggingface dataset:
Design Mining Interacting Wind Turbines
Venue: arXiv cs.NE 2015
Year: 2015

An initial study of surrogate-assisted evolutionary algorithms used to design vertical-axis wind turbines wherein candidate prototypes are evaluated under fan generated wind conditions after being physically instantiated by a 3D printer has recently been presented. Unlike other approaches, such as computational fluid dynamics simulations, no mathematical formulations were used and no model assumptions were made. This paper extends that work by exploring alternative surrogate modelling and evolutionary techniques. The accuracy of various modelling algorithms used to estimate the fitness of evaluated individuals from the initial experiments is compared. The effect of temporally windowing surrogate model training samples is explored. A surrogate-assisted approach based on an enhanced local search is introduced; and alternative coevolution collaboration schemes are examined.
HD-CNN: Hierarchical Deep Convolutional Neural Network for Large Scale Visual Recognition
Venue: arXiv cs.CV 2015
Year: 2015

In image classification, visual separability between different object categories is highly uneven, and some categories are more difficult to distinguish than others. Such difficult categories demand more dedicated classifiers. However, existing deep convolutional neural networks (CNN) are trained as flat N-way classifiers, and few efforts have been made to leverage the hierarchical structure of categories. In this paper, we introduce hierarchical deep CNNs (HD-CNNs) by embedding deep CNNs into a category hierarchy. An HD-CNN separates easy classes using a coarse category classifier while distinguishing difficult classes using fine category classifiers. During HD-CNN training, component-wise pretraining is followed by global finetuning with a multinomial logistic loss regularized by a coarse category consistency term. In addition, conditional executions of fine category classifiers and layer parameter compression make HD-CNNs scalable for large-scale visual recognition. We achieve state-of-the-art results on both CIFAR100 and large-scale ImageNet 1000-class benchmark datasets. In our experiments, we build up three different HD-CNNs and they lower the top-1 error of the standard CNNs by 2.65%, 3.1% and 1.1%, respectively.
Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits
Venue: arXiv cs.LG 2015
Year: 2015

A stochastic combinatorial semi-bandit is an online learning problem where at each step a learning agent chooses a subset of ground items subject to constraints, and then observes stochastic weights of these items and receives their sum as a payoff. In this paper, we close the problem of computationally and sample efficient learning in stochastic combinatorial semi-bandits. In particular, we analyze a UCB-like algorithm for solving the problem, which is known to be computationally efficient; and prove $O(K L (1 / Δ) \log n)$ and $O(\sqrt{K L n \log n})$ upper bounds on its $n$-step regret, where $L$ is the number of ground items, $K$ is the maximum number of chosen items, and $Δ$ is the gap between the expected returns of the optimal and best suboptimal solutions. The gap-dependent bound is tight up to a constant factor and the gap-free bound is tight up to a polylogarithmic factor.
Capacity Estimation for Vehicle-to-Grid Frequency Regulation Services with Smart Charging Mechanism
Venue: arXiv cs.SY 2015
Year: 2015

Due to various green initiatives, renewable energy will be massively incorporated into the future smart grid. However, the intermittency of the renewables may result in power imbalance, thus adversely affecting the stability of a power system. Frequency regulation may be used to maintain the power balance at all times. As electric vehicles (EVs) become popular, they may be connected to the grid to form a vehicle-to-grid (V2G) system. An aggregation of EVs can be coordinated to provide frequency regulation services. However, V2G is a dynamic system where the participating EVs come and go independently. Thus it is not easy to estimate the regulation capacities for V2G. In a preliminary study, we modeled an aggregation of EVs with a queueing network, whose structure allows us to estimate the capacities for regulation-up and regulation-down, separately. The estimated capacities from the V2G system can be used for establishing a regulation contract between an aggregator and the grid operator, and facilitating a new business model for V2G. In this paper, we extend our previous development by designing a smart charging mechanism which can adapt to given characteristics of the EVs and make the performance of the actual system follow the analytical model.
Compositional Performance Certification of Interconnected Systems using ADMM
Venue: arXiv cs.SY 2015
Year: 2015

A compositional performance certification method is presented for interconnected systems using subsystem dissipativity properties and the interconnection structure. A large-scale optimization problem is formulated to search for the most relevant dissipativity properties. The alternating direction method of multipliers (ADMM) is employed to decompose and solve this problem, and is demonstrated on several examples.
Randomness Efficient Fast-Johnson-Lindenstrauss Transform with Applications in Differential Privacy and Compressed Sensing
Venue: arXiv cs.DS 2015
Year: 2015

The Johnson-Lindenstrauss property ({\sf JLP}) of random matrices has immense application in computer science ranging from compressed sensing, learning theory, numerical linear algebra, to privacy. This paper explores the properties and applications of a distribution of random matrices. Our distribution satisfies {\sf JLP} with desirable properties like fast matrix-vector multiplication, sparsity, and optimal subspace embedding. We can sample a random matrix from this distribution using exactly $2n+n \log n$ random bits. We show that a random matrix picked from this distribution preserves differential privacy under the condition that the input private matrix satisfies certain spectral property. This improves the run-time of various differentially private mechanisms like Blocki {\it et al.} (FOCS 2012) and Upadhyay (ASIACRYPT 13). Our final construction has a bounded column sparsity. Therefore, this answers an open problem stated in Blocki {\it et al.} (FOCS 2012). Using the results of Baranuik {\it et al.} (Constructive Approximation: 28(3)), our result implies a randomness efficient matrices that satisfies the Restricted-Isometry Property of optimal order for small sparsity with exactly linear random bits. We also show that other known distributions of sparse random matrices with the {\sf JLP} does not preserves differential privacy; thereby, answering one of the open problem posed by Blocki {\it et al.} (FOCS 2012). Extending on the works of Kane and Nelson (JACM: 61(1)), we also give unified analysis of some of the known Johnson-Lindenstrauss transform. We also present a self-contained simplified proof of an inequality on quadratic form of Gaussian variables that we use in all our proofs.
An Ontology for Comprehensive Tutoring of Euphonic Conjunctions of Sanskrit Grammar
Venue: arXiv cs.CL 2015
Year: 2015

Euphonic conjunctions (sandhis) form a very important aspect of Sanskrit morphology and phonology. The traditional and modern methods of studying about euphonic conjunctions in Sanskrit follow different methodologies. The former involves a rigorous study of the Paninian system embodied in Panini's Ashtadhyayi, while the latter usually involves the study of a few important sandhi rules with the use of examples. The former is not suitable for beginners, and the latter, not sufficient to gain a comprehensive understanding of the operation of sandhi rules. This is so since there are not only numerous sandhi rules and exceptions, but also complex precedence rules involved. The need for a new ontology for sandhi-tutoring was hence felt. This work presents a comprehensive ontology designed to enable a student-user to learn in stages all about euphonic conjunctions and the relevant aphorisms of Sanskrit grammar and to test and evaluate the progress of the student-user. The ontology forms the basis of a multimedia sandhi tutor that was given to different categories of users including Sanskrit scholars for extensive and rigorous testing.
Identification of Linear Time-Varying Systems Through Waveform Diversity
Venue: arXiv cs.IT 2015
Year: 2015

Linear, time-varying (LTV) systems composed of time shifts, frequency shifts, and complex amplitude scalings are operators that act on continuous finite-energy waveforms. This paper presents a novel, resource-efficient method for identifying the parametric description of such systems, i.e., the time shifts, frequency shifts, and scalings, from the sampled response to linear frequency modulated (LFM) waveforms, with emphasis on the application to radar processing. If the LTV operator is probed with a sufficiently diverse set of LFM waveforms, then the system can be identified with high accuracy. In the case of noiseless measurements, the identification is perfect, while in the case of noisy measurements, the accuracy is inversely proportional to the noise level. The use of parametric estimation techniques with recently proposed denoising algorithms allows the estimation of the parameters with high accuracy.
Distributed Nonparametric Sequential Spectrum Sensing under Electromagnetic Interference
Venue: arXiv cs.IT 2015
Year: 2015

A nonparametric distributed sequential algorithm for quick detection of spectral holes in a Cognitive Radio set up is proposed. Two or more local nodes make decisions and inform the fusion centre (FC) over a reporting Multiple Access Channel (MAC), which then makes the final decision. The local nodes use energy detection and the FC uses mean detection in the presence of fading, heavy-tailed electromagnetic interference (EMI) and outliers. The statistics of the primary signal, channel gain or the EMI is not known. Different nonparametric sequential algorithms are compared to choose appropriate algorithms to be used at the local nodes and the FC. Modification of a recently developed random walk test is selected for the local nodes for energy detection as well as at the fusion centre for mean detection. It is shown via simulations and analysis that the nonparametric distributed algorithm developed performs well in the presence of fading, EMI and is robust to outliers. The algorithm is iterative in nature making the computation and storage requirements minimal.
Design of LDPC Code Ensembles with Fast Convergence Properties
Venue: arXiv cs.IT 2015
Year: 2015

The design of low-density parity-check (LDPC) code ensembles optimized for a finite number of decoder iterations is investigated. Our approach employs EXIT chart analysis and differential evolution to design such ensembles for the binary erasure channel and additive white Gaussian noise channel. The error rates of codes optimized for various numbers of decoder iterations are compared and it is seen that in the cases considered, the best performance for a given number of decoder iterations is achieved by codes which are optimized for this particular number. The design of generalized LDPC (GLDPC) codes is also considered, showing that these structures can offer better performance than LDPC codes for low-iteration-number designs. Finally, it is illustrated that LDPC codes which are optimized for a small number of iterations exhibit significant deviations in terms of degree distribution and weight enumerators with respect to LDPC codes returned by more conventional design tools.
Zero-Correlation Linear Cryptanalysis of Reduced-round MISTY1
Venue: arXiv cs.CR 2015
Year: 2015

The MISTY1 algorithm, proposed by Matsui in FSE 1997, is a block cipher with a 64-bit block size and a 128-bit key size. It was recommended by the European NESSIE project and the CRYPTREC project, and became one RFC in 2002 and an ISO standard in 2005, respectively. In this paper, we first investigate the properties of the FL linear function and identify 232 subkey- dependent zero-correlation linear approximations over 5-round MISTY1 with 3 FL layers. Fur- thermore, some observations on the FL, FO and FI functions are founded and based upon those observations, we select 27 subkey-dependent zero-correlation linear approximations and then, pro- pose the zero-correlation linear attacks on 7-round MISTY1 with 4 FL layers. Besides, for the case without FL layers, 27 zero-correlation linear approximations over 5-round MISTY1 are employed to the analysis of 7-round MISTY1. The zero-correlation linear attack on the 7-round with 4 FL layers needs about 2^{119:5} encryptions with 2^{62.9} known plaintexts and 2^61 memory bytes. For the attack on 7-round without FL layers, the data complexity is about 2^{63.9} known plaintexts, the time complexity is about 2^{81} encryptions and the memory requirements are about 2^{93} bytes. Both have lower time complexity than previous attacks.
A GPU-based parallel algorithm for enumerating all chordless cycles in graphs
Venue: arXiv cs.DC 2015
Year: 2015

In a finite undirected simple graph, a chordless cycle is an induced subgraph which is a cycle. We propose a GPU parallel algorithm for enumerating all chordless cycles of such a graph. The algorithm, implemented in OpenCL, is based on a previous sequential algorithm developed by the current authors for the same problem. It uses a more compact data structure for solution representation which is suitable for the memory-size limitation of a GPU. Moreover, for graphs with a sufficiently large amount of chordless cycles, the algorithm presents a significant improvement in execution time that outperforms the sequential method.
Near-Optimal Scheduling for LTL with Future Discounting
Venue: arXiv cs.LO 2015
Year: 2015

We study the search problem for optimal schedulers for the linear temporal logic (LTL) with future discounting. The logic, introduced by Almagor, Boker and Kupferman, is a quantitative variant of LTL in which an event in the far future has only discounted contribution to a truth value (that is a real number in the unit interval [0, 1]). The precise problem we study---it naturally arises e.g. in search for a scheduler that recovers from an internal error state as soon as possible---is the following: given a Kripke frame, a formula and a number in [0, 1] called a margin, find a path of the Kripke frame that is optimal with respect to the formula up to the prescribed margin (a truly optimal path may not exist). We present an algorithm for the problem; it works even in the extended setting with propositional quality operators, a setting where (threshold) model-checking is known to be undecidable.
Lightweight Monte Carlo Verification of Markov Decision Processes with Rewards
Venue: arXiv cs.LO 2015
Year: 2015

Markov decision processes are useful models of concurrency optimisation problems, but are often intractable for exhaustive verification methods. Recent work has introduced lightweight approximative techniques that sample directly from scheduler space, bringing the prospect of scalable alternatives to standard numerical model checking algorithms. The focus so far has been on optimising the probability of a property, but many problems require quantitative analysis of rewards. In this work we therefore present lightweight statistical model checking algorithms to optimise the rewards of Markov decision processes. We consider the standard definitions of rewards used in model checking, introducing an auxiliary hypothesis test to accommodate reachability rewards. We demonstrate the performance of our approach on a number of standard case studies.
Towards a Model Theory for Distributed Representations
Venue: arXiv cs.AI 2015
Year: 2015

Distributed representations (such as those based on embeddings) and discrete representations (such as those based on logic) have complementary strengths. We explore one possible approach to combining these two kinds of representations. We present a model theory/semantics for first order logic based on vectors of reals. We describe the model theory, discuss some interesting properties of such a system and present a simple approach to query answering.
Bitcoin over Tor isn't a good idea
Venue: arXiv cs.CR 2015
Year: 2015

Bitcoin is a decentralized P2P digital currency in which coins are generated by a distributed set of miners and transaction are broadcasted via a peer-to-peer network. While Bitcoin provides some level of anonymity (or rather pseudonymity) by encouraging the users to have any number of random-looking Bitcoin addresses, recent research shows that this level of anonymity is rather low. This encourages users to connect to the Bitcoin network through anonymizers like Tor and motivates development of default Tor functionality for popular mobile SPV clients. In this paper we show that combining Tor and Bitcoin creates an attack vector for the deterministic and stealthy man-in-the-middle attacks. A low-resource attacker can gain full control of information flows between all users who chose to use Bitcoin over Tor. In particular the attacker can link together user's transactions regardless of pseudonyms used, control which Bitcoin blocks and transactions are relayed to the user and can \ delay or discard user's transactions and blocks. In collusion with a powerful miner double-spending attacks become possible and a totally virtual Bitcoin reality can be created for such set of users. Moreover, we show how an attacker can fingerprint users and then recognize them and learn their IP address when they decide to connect to the Bitcoin network directly.
Spector bar recursion over finite partial functions
Venue: arXiv cs.LO 2015
Year: 2015

We introduce a new, demand-driven variant of Spector's bar recursion in the spirit of the Berardi-Bezem-Coquand functional. The recursion takes place over finite partial functions $u$, where the control parameter $φ$, used in Spector's bar recursion to terminate the computation at sequences $s$ satisfying $φ(\hat{s})<|s|$, now acts as a guide for deciding exactly where to make bar recursive updates, terminating the computation whenever $φ(\hat{u})\in\mbox{dom}(u)$. We begin by exploring theoretical aspects of this new form of recursion, then in the main part of the paper we show that demand-driven bar recursion can be directly used to give an alternative functional interpretation of classical countable choice. We provide a short case study as an illustration, in which we extract a new bar recursive program from the proof that there is no injection from $\mathbb{N}\to\mathbb{N}$ to $\mathbb{N}$, and compare this to the program that would be obtained using Spector's original variant. We conclude by formally establishing that our new bar recursor is primitive recursively equivalent to the original Spector bar recursion, and thus defines the same class of functionals when added to Gödel's system $\sf T$.
Matching Theory for Future Wireless Networks: Fundamentals and Applications
Venue: arXiv cs.IT 2015
Year: 2015

The emergence of novel wireless networking paradigms such as small cell and cognitive radio networks has forever transformed the way in which wireless systems are operated. In particular, the need for self-organizing solutions to manage the scarce spectral resources has become a prevalent theme in many emerging wireless systems. In this paper, the first comprehensive tutorial on the use of matching theory, a Nobelprize winning framework, for resource management in wireless networks is developed. To cater for the unique features of emerging wireless networks, a novel, wireless-oriented classification of matching theory is proposed. Then, the key solution concepts and algorithmic implementations of this framework are exposed. Then, the developed concepts are applied in three important wireless networking areas in order to demonstrate the usefulness of this analytical tool. Results show how matching theory can effectively improve the performance of resource allocation in all three applications discussed.
Sampling in the Analysis Transform Domain
Venue: arXiv cs.IT 2015
Year: 2015

Many signal and image processing applications have benefited remarkably from the fact that the underlying signals reside in a low dimensional subspace. One of the main models for such a low dimensionality is the sparsity one. Within this framework there are two main options for the sparse modeling: the synthesis and the analysis ones, where the first is considered the standard paradigm for which much more research has been dedicated. In it the signals are assumed to have a sparse representation under a given dictionary. On the other hand, in the analysis approach the sparsity is measured in the coefficients of the signal after applying a certain transformation, the analysis dictionary, on it. Though several algorithms with some theory have been developed for this framework, they are outnumbered by the ones proposed for the synthesis methodology. Given that the analysis dictionary is either a frame or the two dimensional finite difference operator, we propose a new sampling scheme for signals from the analysis model that allows to recover them from their samples using any existing algorithm from the synthesis model. The advantage of this new sampling strategy is that it makes the existing synthesis methods with their theory also available for signals from the analysis framework.
Practical Massively Parallel Sorting
Venue: arXiv cs.DS 2015
Year: 2015

Previous parallel sorting algorithms do not scale to the largest available machines, since they either have prohibitive communication volume or prohibitive critical path length. We describe algorithms that are a viable compromise and overcome this gap both in theory and practice. The algorithms are multi-level generalizations of the known algorithms sample sort and multiway mergesort. In particular our sample sort variant turns out to be very scalable. Some tools we develop may be of independent interest -- a simple, practical, and flexible sorting algorithm for small inputs working in logarithmic time, a near linear time optimal algorithm for solving a constrained bin packing problem, and an algorithm for data delivery, that guarantees a small number of message startups on each processor.
Heteroscedastic Treed Bayesian Optimisation
Venue: arXiv cs.LG 2015
Year: 2015

Optimising black-box functions is important in many disciplines, such as tuning machine learning models, robotics, finance and mining exploration. Bayesian optimisation is a state-of-the-art technique for the global optimisation of black-box functions which are expensive to evaluate. At the core of this approach is a Gaussian process prior that captures our belief about the distribution over functions. However, in many cases a single Gaussian process is not flexible enough to capture non-stationarity in the objective function. Consequently, heteroscedasticity negatively affects performance of traditional Bayesian methods. In this paper, we propose a novel prior model with hierarchical parameter learning that tackles the problem of non-stationarity in Bayesian optimisation. Our results demonstrate substantial improvements in a wide range of applications, including automatic machine learning and mining exploration.