OpenRaiser/Intern-Atlas huggingface dataset:
Re-scale boosting for regression and classification
Venue: arXiv cs.LG 2015
Year: 2015

Boosting is a learning scheme that combines weak prediction rules to produce a strong composite estimator, with the underlying intuition that one can obtain accurate prediction rules by combining "rough" ones. Although boosting is proved to be consistent and overfitting-resistant, its numerical convergence rate is relatively slow. The aim of this paper is to develop a new boosting strategy, called the re-scale boosting (RBoosting), to accelerate the numerical convergence rate and, consequently, improve the learning performance of boosting. Our studies show that RBoosting possesses the almost optimal numerical convergence rate in the sense that, up to a logarithmic factor, it can reach the minimax nonlinear approximation rate. We then use RBoosting to tackle both the classification and regression problems, and deduce a tight generalization error estimate. The theoretical and experimental results show that RBoosting outperforms boosting in terms of generalization.
Public Transit Labeling
Venue: arXiv cs.DS 2015
Year: 2015

We study the journey planning problem in public transit networks. Developing efficient preprocessing-based speedup techniques for this problem has been challenging: current approaches either require massive preprocessing effort or provide limited speedups. Leveraging recent advances in Hub Labeling, the fastest algorithm for road networks, we revisit the well-known time-expanded model for public transit. Exploiting domain-specific properties, we provide simple and efficient algorithms for the earliest arrival, profile, and multicriteria problems, with queries that are orders of magnitude faster than the state of the art.
An algebraic approach to temporal network analysis based on temporal quantities
Venue: arXiv cs.SI 2015
Year: 2015

In a temporal network, the presence and activity of nodes and links can change through time. To describe temporal networks we introduce the notion of temporal quantities. We define the addition and multiplication of temporal quantities in a way that can be used for the definition of addition and multiplication of temporal networks. The corresponding algebraic structures are semirings. The usual approach to (data) analysis of temporal networks is to transform it into a sequence of time slices -- static networks corresponding to selected time intervals and analyze each of them using standard methods to produce a sequence of results. The approach proposed in this paper enables us to compute these results directly. We developed fast algorithms for the proposed operations. They are available as an open source Python library TQ (Temporal Quantities) and a program Ianus. The proposed approach enables us to treat as temporal quantities also other network characteristics such as degrees, connectivity components, centrality measures, Pathfinder skeleton, etc. To illustrate the developed tools we present some results from the analysis of Franzosi's violence network and Corman's Reuters terror news network.
A Formalisation of Finite Automata using Hereditarily Finite Sets
Venue: arXiv cs.FL 2015
Year: 2015

Hereditarily finite (HF) set theory provides a standard universe of sets, but with no infinite sets. Its utility is demonstrated through a formalisation of the theory of regular languages and finite automata, including the Myhill-Nerode theorem and Brzozowski's minimisation algorithm. The states of an automaton are HF sets, possibly constructed by product, sum, powerset and similar operations.
Emoticon-based Ambivalent Expression: A Hidden Indicator for Unusual Behaviors in Weibo
Venue: arXiv cs.SI 2015
Year: 2015

Recent decades have witnessed online social media being a big-data window for quantificationally testifying conventional social theories and exploring much detailed human behavioral patterns. In this paper, by tracing the emoticon use in Weibo, a group of hidden "ambivalent users" are disclosed for frequently posting ambivalent tweets containing both positive and negative emotions. Further investigation reveals that this ambivalent expression could be a novel indicator of many unusual social behaviors. For instance, ambivalent users with the female as the majority like to make a sound in midnights or at weekends. They mention their close friends frequently in ambivalent tweets, which attract more replies and thus serve as a more private communication way. Ambivalent users also respond differently to public affairs from others and demonstrate more interests in entertainment and sports events. Moreover, the sentiment shift of words adopted in ambivalent tweets is more evident than usual and exhibits a clear "negative to positive" pattern. The above observations, though being promiscuous seemingly, actually point to the self regulation of negative mood in Weibo, which could find its base from the emotion management theories in sociology but makes an interesting extension to the online environment. Finally, as an interesting corollary, ambivalent users are found connected with compulsive buyers and turn out to be perfect targets for online marketing.
Fast Spectral Unmixing based on Dykstra's Alternating Projection
Venue: arXiv cs.CV 2015
Year: 2015

This paper presents a fast spectral unmixing algorithm based on Dykstra's alternating projection. The proposed algorithm formulates the fully constrained least squares optimization problem associated with the spectral unmixing task as an unconstrained regression problem followed by a projection onto the intersection of several closed convex sets. This projection is achieved by iteratively projecting onto each of the convex sets individually, following Dyktra's scheme. The sequence thus obtained is guaranteed to converge to the sought projection. Thanks to the preliminary matrix decomposition and variable substitution, the projection is implemented intrinsically in a subspace, whose dimension is very often much lower than the number of bands. A benefit of this strategy is that the order of the computational complexity for each projection is decreased from quadratic to linear time. Numerical experiments considering diverse spectral unmixing scenarios provide evidence that the proposed algorithm competes with the state-of-the-art, namely when the number of endmembers is relatively small, a circumstance often observed in real hyperspectral applications.
Multiuser MIMO Beamforming with Full-duplex Open-loop Training
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, full-duplex radios are used to continuously update the channel state information at the transmitter, which is required to compute the downlink precoding matrix in MIMO broadcast channels. The full-duplex operation allows leveraging channel reciprocity for open-loop uplink training to estimate the downlink channels. However, the uplink transmission of training creates interference at the downlink receiving mobile nodes. We characterize the optimal training resource allocation and its associated spectral efficiency, in the proposed open-loop training based full-duplex system. We also evaluate the performance of the half-duplex counterpart to derive the relative gains of full-duplex training. Despite the existence of inter-node interference due to full-duplex, significant spectral efficiency improvement is attained over half-duplex operation.
Immutable Views -- Access control (to your information) for masses
Venue: arXiv cs.CR 2015
Year: 2015

There are a lot of on going efforts in the research community as well as industry around providing privacy-preserving and secure storage for personal data. Although, over time it has adopted many tag lines such as Personal Information Hub [12], personal container [8], DataBox [4], Personal Data Store (PDS) [3] and many others, these are essentially reincarnations of a simple idea: provide a secure way and place for users to store their information and allow them to provision who has access to that information. In this paper, we would like to discuss a way to facilitate access control mechanism (AC) in the various "personal cloud" proposals.
Energy Efficiency and Sum Rate when Massive MIMO meets Device-to-Device Communication
Venue: arXiv cs.IT 2015
Year: 2015

This paper considers a scenario of short-range communication, known as device-to-device (D2D) communication, where D2D users reuse the downlink resources of a cellular network to transmit directly to their corresponding receivers. In addition, multiple antennas at the base station (BS) are used in order to simultaneously support multiple cellular users using multiuser or massive MIMO. The network model considers a fixed number of cellular users and that D2D users are distributed according to a homogeneous Poisson point process (PPP). Two metrics are studied, namely, average sum rate (ASR) and energy efficiency (EE). We derive tractable expressions and study the tradeoffs between the ASR and EE as functions of the number of BS antennas and density of D2D users for a given coverage area.
DART: Dropouts meet Multiple Additive Regression Trees
Venue: arXiv cs.LG 2015
Year: 2015

Multiple Additive Regression Trees (MART), an ensemble model of boosted regression trees, is known to deliver high prediction accuracy for diverse tasks, and it is widely used in practice. However, it suffers an issue which we call over-specialization, wherein trees added at later iterations tend to impact the prediction of only a few instances, and make negligible contribution towards the remaining instances. This negatively affects the performance of the model on unseen data, and also makes the model over-sensitive to the contributions of the few, initially added tress. We show that the commonly used tool to address this issue, that of shrinkage, alleviates the problem only to a certain extent and the fundamental issue of over-specialization still remains. In this work, we explore a different approach to address the problem that of employing dropouts, a tool that has been recently proposed in the context of learning deep neural networks. We propose a novel way of employing dropouts in MART, resulting in the DART algorithm. We evaluate DART on ranking, regression and classification tasks, using large scale, publicly available datasets, and show that DART outperforms MART in each of the tasks, with a significant margin. We also show that DART overcomes the issue of over-specialization to a considerable extent.
Adaptive importance sampling for control and inference
Venue: arXiv cs.SY 2015
Year: 2015

Path integral (PI) control problems are a restricted class of non-linear control problems that can be solved formally as a Feyman-Kac path integral and can be estimated using Monte Carlo sampling. In this contribution we review path integral control theory in the finite horizon case. We subsequently focus on the problem how to compute and represent control solutions. Within the PI theory, the question of how to compute becomes the question of importance sampling. Efficient importance samplers are state feedback controllers and the use of these requires an efficient representation. Learning and representing effective state-feedback controllers for non-linear stochastic control problems is a very challenging, and largely unsolved, problem. We show how to learn and represent such controllers using ideas from the cross entropy method. We derive a gradient descent method that allows to learn feed-back controllers using an arbitrary parametrisation. We refer to this method as the Path Integral Cross Entropy method or PICE. We illustrate this method for some simple examples. The path integral control methods can be used to estimate the posterior distribution in latent state models. In neuroscience these problems arise when estimating connectivity from neural recording data using EM. We demonstrate the path integral control method as an accurate alternative to particle filtering.
A Monte Carlo Study of Pairwise Comparisons
Venue: arXiv cs.OH 2015
Year: 2015

Consistent approximations obtained by geometric means ($GM$) and the principal eigenvector ($EV$), turned out to be close enough for 1,000,000 not-so-inconsistent pairwise comparisons matrices. In this respect both methods are accurate enough for most practical applications. As the enclosed Table 1 demonstrates, the biggest difference between average deviations of $GM$ and $EV$ solutions is 0.00019 for the Euclidean metric and 0.00355 for the Tchebychev metric. For practical applications, this precision is far better than expected. After all we are talking, in most cases, about relative subjective comparisons and one tenth of a percent is usually below our threshold of perception.
An Algorithm for the Optimal Consistent Approximation to a Pairwise Comparisons Matrix by Orthogonal Projections
Venue: arXiv cs.OH 2015
Year: 2015

The algorithm for finding the optimal consistent approximation of an inconsistent pairwise comparisons matrix is based on a logarithmic transformation of a pairwise comparisons matrix into a vector space with the Euclidean metric. Orthogonal basis is introduced in the vector space. The orthogonal projection of the transformed matrix onto the space formed by the images of consistent matrices is the required consistent approximation.
A simpler sublinear algorithm for approximating the triangle count
Venue: arXiv cs.DS 2015
Year: 2015

A recent result of Eden, Levi, and Ron (ECCC 2015) provides a sublinear time algorithm to estimate the number of triangles in a graph. Given an undirected graph $G$, one can query the degree of a vertex, the existence of an edge between vertices, and the $i$th neighbor of a vertex. Suppose the graph has $n$ vertices, $m$ edges, and $t$ triangles. In this model, Eden et al provided a $O(\poly(\eps^{-1}\log n)(n/t^{1/3} + m^{3/2}/t))$ time algorithm to get a $(1+\eps)$-multiplicative approximation for $t$, the triangle count. This paper provides a simpler algorithm with the same running time (up to differences in the $\poly(\eps^{-1}\log n)$ factor) that has a substantially simpler analysis.
FPGA-Based Bandwidth Selection for Kernel Density Estimation Using High Level Synthesis Approach
Venue: arXiv cs.OH 2015
Year: 2015

FPGA technology can offer significantly hi\-gher performance at much lower power consumption than is available from CPUs and GPUs in many computational problems. Unfortunately, programming for FPGA (using ha\-rdware description languages, HDL) is a difficult and not-trivial task and is not intuitive for C/C++/Java programmers. To bring the gap between programming effectiveness and difficulty the High Level Synthesis (HLS) approach is promoting by main FPGA vendors. Nowadays, time-intensive calculations are mainly performed on GPU/CPU architectures, but can also be successfully performed using HLS approach. In the paper we implement a bandwidth selection algorithm for kernel density estimation (KDE) using HLS and show techniques which were used to optimize the final FPGA implementation. We are also going to show that FPGA speedups, comparing to highly optimized CPU and GPU implementations, are quite substantial. Moreover, power consumption for FPGA devices is usually much less than typical power consumption of the present CPUs and GPUs.
Error Performance Analysis of FSO Links with Equal Gain Diversity Receivers over Double Generalized Gamma Fading Channels
Venue: arXiv cs.IT 2015
Year: 2015

Free space optical (FSO) communication has been receiving increasing attention in recent years with its ability to achieve ultra-high data rates over unlicensed optical spectrum. A major performance limiting factor in FSO systems is atmospheric turbulence which severely degrades the system performance. To address this issue, multiple transmit and/or receive apertures can be employed, and the performance can be improved via diversity gain. In this paper, we investigate the bit error rate (BER) performance of FSO systems with transmit diversity or receive diversity with equal gain combining (EGC) over atmospheric turbulence channels described by the Double Generalized Gamma (Double GG) distribution. The Double GG distribution, recently proposed, generalizes many existing turbulence models in a closed-form expression and covers all turbulence conditions. Since the distribution function of a sum of Double GG random variables (RVs) appears in BER expression, we first derive a closed-form upper bound for the distribution of the sum of Double GG distributed RVs. A novel union upper bound for the average BER as well as corresponding asymptotic expression is then derived and evaluated in terms of Meijer's G-functions.
A Rewritable, Random-Access DNA-Based Storage System
Venue: arXiv cs.IT 2015
Year: 2015

We describe the first DNA-based storage architecture that enables random access to data blocks and rewriting of information stored at arbitrary locations within the blocks. The newly developed architecture overcomes drawbacks of existing read-only methods that require decoding the whole file in order to read one data fragment. Our system is based on new constrained coding techniques and accompanying DNA editing methods that ensure data reliability, specificity and sensitivity of access, and at the same time provide exceptionally high data storage capacity. As a proof of concept, we encoded parts of the Wikipedia pages of six universities in the USA, and selected and edited parts of the text written in DNA corresponding to three of these schools. The results suggest that DNA is a versatile media suitable for both ultrahigh density archival and rewritable storage applications.
Predicate Abstraction for Linked Data Structures
Venue: arXiv cs.PL 2015
Year: 2015

We present Alias Refinement Types (ART), a new approach to the verification of correctness properties of linked data structures. While there are many techniques for checking that a heap-manipulating program adheres to its specification, they often require that the programmer annotate the behavior of each procedure, for example, in the form of loop invariants and pre- and post-conditions. Predicate abstraction would be an attractive abstract domain for performing invariant inference, existing techniques are not able to reason about the heap with enough precision to verify functional properties of data structure manipulating programs. In this paper, we propose a technique that lifts predicate abstraction to the heap by factoring the analysis of data structures into two orthogonal components: (1) Alias Types, which reason about the physical shape of heap structures, and (2) Refinement Types, which use simple predicates from an SMT decidable theory to capture the logical or semantic properties of the structures. We prove ART sound by translating types into separation logic assertions, thus translating typing derivations in ART into separation logic proofs. We evaluate ART by implementing a tool that performs type inference for an imperative language, and empirically show, using a suite of data-structure benchmarks, that ART requires only 21% of the annotations needed by other state-of-the-art verification techniques.
Bayesian Sparse Tucker Models for Dimension Reduction and Tensor Completion
Venue: arXiv cs.LG 2015
Year: 2015

Tucker decomposition is the cornerstone of modern machine learning on tensorial data analysis, which have attracted considerable attention for multiway feature extraction, compressive sensing, and tensor completion. The most challenging problem is related to determination of model complexity (i.e., multilinear rank), especially when noise and missing data are present. In addition, existing methods cannot take into account uncertainty information of latent factors, resulting in low generalization performance. To address these issues, we present a class of probabilistic generative Tucker models for tensor decomposition and completion with structural sparsity over multilinear latent space. To exploit structural sparse modeling, we introduce two group sparsity inducing priors by hierarchial representation of Laplace and Student-t distributions, which facilitates fully posterior inference. For model learning, we derived variational Bayesian inferences over all model (hyper)parameters, and developed efficient and scalable algorithms based on multilinear operations. Our methods can automatically adapt model complexity and infer an optimal multilinear rank by the principle of maximum lower bound of model evidence. Experimental results and comparisons on synthetic, chemometrics and neuroimaging data demonstrate remarkable performance of our models for recovering ground-truth of multilinear rank and missing entries.
Neural dissimilarity indices that predict oddball detection in behaviour
Venue: arXiv cs.IT 2015
Year: 2015

Neuroscientists have recently shown that images that are difficult to find in visual search elicit similar patterns of firing across a population of recorded neurons. The $L^{1}$ distance between firing rate vectors associated with two images was strongly correlated with the inverse of decision time in behaviour. But why should decision times be correlated with $L^{1}$ distance? What is the decision-theoretic basis? In our decision theoretic formulation, we modeled visual search as an active sequential hypothesis testing problem with switching costs. Our analysis suggests an appropriate neuronal dissimilarity index which correlates equally strongly with the inverse of decision time as the $L^{1}$ distance. We also consider a number of other possibilities such as the relative entropy (Kullback-Leibler divergence) and the Chernoff entropy of the firing rate distributions. A more stringent test of equality of means, which would have provided a strong backing for our modeling fails for our proposed as well as the other already discussed dissimilarity indices. However, test statistics from the equality of means test, when used to rank the indices in terms of their ability to explain the observed results, places our proposed dissimilarity index at the top followed by relative entropy, Chernoff entropy and the $L^{1}$ indices. Computations of the different indices requires an estimate of the relative entropy between two Poisson point processes. An estimator is developed and is shown to have near unbiased performance for almost all operating regions.
Energy Efficiency in Secure Multi-Antenna Systems
Venue: arXiv cs.IT 2015
Year: 2015

The problem of resource allocation in multiple-antenna wiretap channels is investigated, wherein a malicious user tries to eavesdrop the communication between two legitimate users. Both multiple input single output single-antenna eavesdropper (MISO-SE) and multiple input multiple output multiple-antenna eavesdropper (MIMO-ME) systems are considered. Unlike most papers dealing with physical layer security, the focus of the resource allocation process here is not to maximize the secrecy capacity, but rather to maximize the energy efficiency of the system. Two fractional energy-efficient metrics are introduced, namely the ratios between the system secrecy capacity and the consumed power, and between the system secret-key rate and the consumed power. Both performance metrics are measured in bit/Joule, and result in non-concave fractional optimization problems, which are tackled by fractional programming theory and sequential convex optimization. For both performance metrics, the energy-efficient resource allocation is carried out considering both perfect as well as statistical channel state information (CSI) as to the channel from the legitimate transmitter to the eavesdropper.
Processing heterogeneous data space measurement subpolar territories to formulate stochastic models assessment geohazards
Venue: arXiv cs.CY 2015
Year: 2015

The article describes the development of a knowledge base of forecasting the state of the individual parameters geoenvironment circumpolar territory using satellite data. The paper provides an analysis of the parameters characterizing the state of polar territory. Select a model and method for processing geodata. Developing an information system of formation of the knowledge base, taking into account development trends (predicting) the values of these parameters.