OpenRaiser/Intern-Atlas huggingface dataset:
Stochastic Bound Majorization
Venue: arXiv cs.LG 2013
Year: 2013

Recently a majorization method for optimizing partition functions of log-linear models was proposed alongside a novel quadratic variational upper-bound. In the batch setting, it outperformed state-of-the-art first- and second-order optimization methods on various learning tasks. We propose a stochastic version of this bound majorization method as well as a low-rank modification for high-dimensional data-sets. The resulting stochastic second-order method outperforms stochastic gradient descent (across variations and various tunings) both in terms of the number of iterations and computation time till convergence while finding a better quality parameter setting. The proposed method bridges first- and second-order stochastic optimization methods by maintaining a computational complexity that is linear in the data dimension and while exploiting second order information about the pseudo-global curvature of the objective function (as opposed to the local curvature in the Hessian).
Combining All Pairs Shortest Paths and All Pairs Bottleneck Paths Problems
Venue: arXiv cs.DS 2013
Year: 2013

We introduce a new problem that combines the well known All Pairs Shortest Paths (APSP) problem and the All Pairs Bottleneck Paths (APBP) problem to compute the shortest paths for all pairs of vertices for all possible flow amounts. We call this new problem the All Pairs Shortest Paths for All Flows (APSP-AF) problem. We firstly solve the APSP-AF problem on directed graphs with unit edge costs and real edge capacities in $\tilde{O}(\sqrt{t}n^{(ω+9)/4}) = \tilde{O}(\sqrt{t}n^{2.843})$ time, where $n$ is the number of vertices, $t$ is the number of distinct edge capacities (flow amounts) and $O(n^ω) < O(n^{2.373})$ is the time taken to multiply two $n$-by-$n$ matrices over a ring. Secondly we extend the problem to graphs with positive integer edge costs and present an algorithm with $\tilde{O}(\sqrt{t}c^{(ω+5)/4}n^{(ω+9)/4}) = \tilde{O}(\sqrt{t}c^{1.843}n^{2.843})$ worst case time complexity, where $c$ is the upper bound on edge costs.
Lower Bound on the BER of a Decode-and-Forward Relay Network Under Chaos Shift Keying Communication System
Venue: arXiv cs.IT 2013
Year: 2013

This paper carries out the first-ever investigation of the analysis of a cooperative Decode-and-Forward (DF) relay network with Chaos Shift Keying (CSK) modulation. The performance analysis of DF-CSK in this paper takes into account the dynamical nature of chaotic signal, which is not similar to a conventional binary modulation performance computation methodology. The expression of a lower bound bit error rate (BER) is derived in order to investigate the performance of the cooperative system under independently and identically distributed (i.i.d.) Gaussian fading wireless environments. The effect of the non-periodic nature of chaotic sequence leading to a non constant bit energy of the considered modulation is also investigated. A computation approach of the BER expression based on the probability density function of the bit energy of the chaotic sequence, channel distribution, and number of relays is presented. Simulation results prove the accuracy of our BER computation methodology.
Demodulation of Sparse PPM Signals with Low Samples Using Trained RIP Matrix
Venue: arXiv cs.OH 2013
Year: 2013

Compressed sensing (CS) theory considers the restricted isometry property (RIP) as a sufficient condition for measurement matrix which guarantees the recovery of any sparse signal from its compressed measurements. The RIP condition also preserves enough information for classification of sparse symbols, even with fewer measurements. In this work, we utilize RIP bound as the cost function for training a simple neural network in order to exploit the near optimal measurements or equivalently near optimal features for classification of a known set of sparse symbols. As an example, we consider demodulation of pulse position modulation (PPM) signals. The results indicate that the proposed method has much better performance than the random measurements and requires less samples than the optimum matched filter demodulator, at the expense of some performance loss. Further, the proposed approach does not need equalizer for multipath channels in contrast to the conventional receiver.
On Regular Sets of Bounds and Determinism versus Nondeterminism
Venue: arXiv cs.CC 2013
Year: 2013

This paper illustrates the richness of the concept of regular sets of time bounds and demonstrates its application to problems of computational complexity. There is a universe of bounds whose regular subsets allow to represent several time complexity classes of common interest and are linearly ordered with respect to the confinality relation which implies the inclusion between the corresponding complexity classes. By means of classical results of complexity theory, the separation of determinism from nondeterminism is possible for a variety of sets of bounds below $n\cdot\log^*(n)$. The system of all regular bound sets ordered by confinality allows the order-isomorphic embedding of, e.g., the ordered set of real numbers or the Cantor discontinuum.
The impact of mobile nodes arrival patterns in mobile ad hoc networks using poisson models
Venue: arXiv cs.NI 2013
Year: 2013

Mobile Ad hoc Networks (MANETs) are dynamic networks populated by mobile stations, or mobile nodes (MNs). Specifically, MANETs consist of a collection of nodes randomly placed in a line (not necessarily straight). Mobile Ad hoc Networks do appear in many real-world network applications such as a vehicular Mobile Ad hoc Networks built along a highway in a city environment or people in a particular location. Mobile Nodes in Mobile Ad hoc Networks are usually laptops, Personal Digital Assistants or mobile phones. These devices may use Blue-tooth and/or IEEE 802.11 network interfaces and communicate in a decentralized manner. Mobility is a key feature of Mobile Ad hoc Networks. Each node may work as a router and the network can dynamically change with time; when new nodes can join, and other nodes can leave the network. This paper presents comparative results that have been carried out via Matrix lab software simulation. The study investigates the impact of mobile nodes parameters such as the speed, the arrival rate and the size of mobile nodes in a given area using Poisson distribution. The results have indicated that mobile nodes arrival rates may have influence on Mobile Nodes population (as a larger number) in a location.
An evolutionary approach to Function
Venue: arXiv cs.AI 2013
Year: 2013

Background: Understanding the distinction between function and role is vexing and difficult. While it appears to be useful, in practice this distinction is hard to apply, particularly within biology. Results: I take an evolutionary approach, considering a series of examples, to develop and generate definitions for these concepts. I test them in practice against the Ontology for Biomedical Investigations (OBI). Finally, I give an axiomatisation and discuss methods for applying these definitions in practice. Conclusions: The definitions in this paper are applicable, formalizing current practice. As such, they make a significant contribution to the use of these concepts within biomedical ontologies.
Device-to-Device Data Storage for Mobile Cellular Systems
Venue: arXiv cs.NI 2013
Year: 2013

As an alternative to downloading content from a cellular access network, mobile devices could be used to store data files and distribute them through device-to-device (D2D) communication. We consider a D2D-based storage community that is comprised of mobile users. Assuming that transmitting data from a base station to a mobile user consumes more energy than transmitting data between two mobile users, we show that it can be beneficial to use redundant storage to ensure that data files stay available to the community even if some of the storing users leave the network. We derive a tractable closed-form equation stating when redundancy should be used in order to minimize the expected energy consumption of data retrieval. We find that replication is the preferred method of adding redundancy as opposed to regenerating codes. Our findings are verified by computer simulations.
An Approach to Modularization of Distributed Systems
Venue: arXiv cs.DC 2013
Year: 2013

Modularization is an important architectural principle underlying many types of complex systems. It tends to tame the complexity of systems, to facilitate their management, and to enhance their flexibility with respect to evolution. In software, modularization has been practiced and studied thoroughly in local, i.e. non-distributed systems. But very little attention has been paid so far to modularization in distributed systems. This is, in part, because distributed systems are inherently modularized, in the sense that the internals of each component of such a system is inaccessible to other components, thus satisfying the Parnas hiding principle. It is, however, the thesis of this paper that there is much to be gained by being able to treat groups of distributed components as modules, called here distributed modules. And that besides the conventional hiding principle, distributed modularization should provide additional capabilities, which rarely, if ever, figure in conventional modularized systems. These capabilities include, but are not limited to: the ability to impose constraints on which kind of messages can be sent from a given distributed-module to its outside; and the ability to create AOP-like crosscutting modules. This paper introduces a model of modular distributed system, orMDS, which satisfies such capabilities, and which is implemented via the LGI middleware.
An Integer Programming Formulation Applied to Optimum Allocation in Multivariate Stratified Sampling
Venue: arXiv cs.DM 2013
Year: 2013

The problem of optimal allocation of samples in surveys using a stratified sampling plan was first discussed by Neyman in 1934. Since then, many researchers have studied the problem of the sample allocation in multivariate surveys and several methods have been proposed. Basically, these methods are divided into two class: The first involves forming a weighted average of the stratum variances and finding the optimal allocation for the average variance. The second class is associated with methods that require that an acceptable coefficient of variation for each of the variables on which the allocation is to be done. Particularly, this paper proposes a new optimization approach to the second problem. This approach is based on an integer programming formulation. Several experiments showed that the proposed approach is efficient way to solve this problem, considering a comparison of this approach with the other approach from the literature.
Mutation Analysis for Security
Venue: arXiv cs.CR 2013
Year: 2013

Security has become, nowadays, a major concern for the organizations as the majority of its applications are exposed to Internet, which increases the threats of security considerably. Thus, the solution is to improve tools and mechanisms to strengthen the protection of applications against attacks and ensure the different security objectives. Among solutions we will talking about, in this paper, there is Mutation Analysis which is a technique of test that evaluates the quality of software tests and their ability to detect errors, It also compares the criteria and test generation strategies. In this study we will use the Mutation Analysis as a mean to qualify the penetration tests, and then, apply this technique in the security mechanisms and exactly on the mechanisms of access control. At the end we will propose a method for the elimination of hidden mechanisms for access control that will allow the access control policy to evolve.
Spot Transit: Cheaper Internet Transit for Elastic Traffic
Venue: arXiv cs.NI 2013
Year: 2013

We advocate to create a \emph{spot} Internet transit market, where transit is sold using the under-utilized backbone capacity at a lower price. The providers can improve profit by capitalizing the perishable capacity, and customers can buy transit on-demand without a minimum commitment level for elastic traffic, and as a result improve its surplus (i.e. utility gains). We conduct a systematic study of the economical benefits of spot transit both theoretically and empirically. We propose a simple analytical framework with a general demand function, and solve the pricing problem of maximizing the expected profit, taking into account the revenue loss of regular transit when spot transit traffic hikes. We rigorously prove the price advantage of spot transit, as well as profit and surplus improvements for tier-1 ISPs and customers, respectively. Using real-world price data and traffic statistics of 6 IXPs with more than 1000 ISPs, we quantitatively evaluate spot transit and show that significant financial benefits can be achieved in both absolute and relative terms, robust to parameter values.
Domain-Specific Sentiment Word Extraction by Seed Expansion and Pattern Generation
Venue: arXiv cs.CL 2013
Year: 2013

This paper focuses on the automatic extraction of domain-specific sentiment word (DSSW), which is a fundamental subtask of sentiment analysis. Most previous work utilizes manual patterns for this task. However, the performance of those methods highly relies on the labelled patterns or selected seeds. In order to overcome the above problem, this paper presents an automatic framework to detect large-scale domain-specific patterns for DSSW extraction. To this end, sentiment seeds are extracted from massive dataset of user comments. Subsequently, these sentiment seeds are expanded by synonyms using a bootstrapping mechanism. Simultaneously, a synonymy graph is built and the graph propagation algorithm is applied on the built synonymy graph. Afterwards, syntactic and sequential relations between target words and high-ranked sentiment words are extracted automatically to construct large-scale patterns, which are further used to extracte DSSWs. The experimental results in three domains reveal the effectiveness of our method.
Convex Relaxations of Bregman Divergence Clustering
Venue: arXiv cs.LG 2013
Year: 2013

Although many convex relaxations of clustering have been proposed in the past decade, current formulations remain restricted to spherical Gaussian or discriminative models and are susceptible to imbalanced clusters. To address these shortcomings, we propose a new class of convex relaxations that can be flexibly applied to more general forms of Bregman divergence clustering. By basing these new formulations on normalized equivalence relations we retain additional control on relaxation quality, which allows improvement in clustering quality. We furthermore develop optimization methods that improve scalability by exploiting recent implicit matrix norm methods. In practice, we find that the new formulations are able to efficiently produce tighter clusterings that improve the accuracy of state of the art methods.
Bethe-ADMM for Tree Decomposition based Parallel MAP Inference
Venue: arXiv cs.AI 2013
Year: 2013

We consider the problem of maximum a posteriori (MAP) inference in discrete graphical models. We present a parallel MAP inference algorithm called Bethe-ADMM based on two ideas: tree-decomposition of the graph and the alternating direction method of multipliers (ADMM). However, unlike the standard ADMM, we use an inexact ADMM augmented with a Bethe-divergence based proximal function, which makes each subproblem in ADMM easy to solve in parallel using the sum-product algorithm. We rigorously prove global convergence of Bethe-ADMM. The proposed algorithm is extensively evaluated on both synthetic and real datasets to illustrate its effectiveness. Further, the parallel Bethe-ADMM is shown to scale almost linearly with increasing number of cores.
Multiple Instance Learning by Discriminative Training of Markov Networks
Venue: arXiv cs.LG 2013
Year: 2013

We introduce a graphical framework for multiple instance learning (MIL) based on Markov networks. This framework can be used to model the traditional MIL definition as well as more general MIL definitions. Different levels of ambiguity -- the portion of positive instances in a bag -- can be explored in weakly supervised data. To train these models, we propose a discriminative max-margin learning algorithm leveraging efficient inference for cardinality-based cliques. The efficacy of the proposed framework is evaluated on a variety of data sets. Experimental results verify that encoding or learning the degree of ambiguity can improve classification performance.
Discovering Cyclic Causal Models with Latent Variables: A General SAT-Based Procedure
Venue: arXiv cs.AI 2013
Year: 2013

We present a very general approach to learning the structure of causal models based on d-separation constraints, obtained from any given set of overlapping passive observational or experimental data sets. The procedure allows for both directed cycles (feedback loops) and the presence of latent variables. Our approach is based on a logical representation of causal pathways, which permits the integration of quite general background knowledge, and inference is performed using a Boolean satisfiability (SAT) solver. The procedure is complete in that it exhausts the available information on whether any given edge can be determined to be present or absent, and returns "unknown" otherwise. Many existing constraint-based causal discovery algorithms can be seen as special cases, tailored to circumstances in which one or more restricting assumptions apply. Simulations illustrate the effect of these assumptions on discovery and how the present algorithm scales.
Constrained Bayesian Inference for Low Rank Multitask Learning
Venue: arXiv cs.LG 2013
Year: 2013

We present a novel approach for constrained Bayesian inference. Unlike current methods, our approach does not require convexity of the constraint set. We reduce the constrained variational inference to a parametric optimization over the feasible set of densities and propose a general recipe for such problems. We apply the proposed constrained Bayesian inference approach to multitask learning subject to rank constraints on the weight matrix. Further, constrained parameter estimation is applied to recover the sparse conditional independence structure encoded by prior precision matrices. Our approach is motivated by reverse inference for high dimensional functional neuroimaging, a domain where the high dimensionality and small number of examples requires the use of constraints to ensure meaningful and effective models. For this application, we propose a model that jointly learns a weight matrix and the prior inverse covariance structure between different tasks. We present experimental validation showing that the proposed approach outperforms strong baseline models in terms of predictive performance and structure recovery.
Collective Diffusion Over Networks: Models and Inference
Venue: arXiv cs.SI 2013
Year: 2013

Diffusion processes in networks are increasingly used to model the spread of information and social influence. In several applications in computational sustainability such as the spread of wildlife, infectious diseases and traffic mobility pattern, the observed data often consists of only aggregate information. In this work, we present new models that generalize standard diffusion processes to such collective settings. We also present optimization based techniques that can accurately learn the underlying dynamics of the given contagion process, including the hidden network structure, by only observing the time a node becomes active and the associated aggregate information. Empirically, our technique is highly robust and accurately learns network structure with more than 90% recall and precision. Results on real-world flu spread data in the US confirm that our technique can also accurately model infectious disease spread.
On the Complexity of Strong and Epistemic Credal Networks
Venue: arXiv cs.AI 2013
Year: 2013

Credal networks are graph-based statistical models whose parameters take values in a set, instead of being sharply specified as in traditional statistical models (e.g., Bayesian networks). The computational complexity of inferences on such models depends on the irrelevance/independence concept adopted. In this paper, we study inferential complexity under the concepts of epistemic irrelevance and strong independence. We show that inferences under strong independence are NP-hard even in trees with ternary variables. We prove that under epistemic irrelevance the polynomial time complexity of inferences in credal trees is not likely to extend to more general models (e.g. singly connected networks). These results clearly distinguish networks that admit efficient inferences and those where inferences are most likely hard, and settle several open questions regarding computational complexity.
Treedy: A Heuristic for Counting and Sampling Subsets
Venue: arXiv cs.DS 2013
Year: 2013

Consider a collection of weighted subsets of a ground set N. Given a query subset Q of N, how fast can one (1) find the weighted sum over all subsets of Q, and (2) sample a subset of Q proportionally to the weights? We present a tree-based greedy heuristic, Treedy, that for a given positive tolerance d answers such counting and sampling queries to within a guaranteed relative error d and total variation distance d, respectively. Experimental results on artificial instances and in application to Bayesian structure discovery in Bayesian networks show that approximations yield dramatic savings in running time compared to exact computation, and that Treedy typically outperforms a previously proposed sorting-based heuristic.
Finite-Time Analysis of Kernelised Contextual Bandits
Venue: arXiv cs.LG 2013
Year: 2013

We tackle the problem of online reward maximisation over a large finite set of actions described by their contexts. We focus on the case when the number of actions is too big to sample all of them even once. However we assume that we have access to the similarities between actions' contexts and that the expected reward is an arbitrary linear function of the contexts' images in the related reproducing kernel Hilbert space (RKHS). We propose KernelUCB, a kernelised UCB algorithm, and give a cumulative regret bound through a frequentist analysis. For contextual bandits, the related algorithm GP-UCB turns out to be a special case of our algorithm, and our finite-time analysis improves the regret bound of GP-UCB for the agnostic case, both in the terms of the kernel-dependent quantity and the RKHS norm of the reward function. Moreover, for the linear kernel, our regret bound matches the lower bound for contextual linear bandits.
Bounded Approximate Symbolic Dynamic Programming for Hybrid MDPs
Venue: arXiv cs.AI 2013
Year: 2013

Recent advances in symbolic dynamic programming (SDP) combined with the extended algebraic decision diagram (XADD) data structure have provided exact solutions for mixed discrete and continuous (hybrid) MDPs with piecewise linear dynamics and continuous actions. Since XADD-based exact solutions may grow intractably large for many problems, we propose a bounded error compression technique for XADDs that involves the solution of a constrained bilinear saddle point problem. Fortuitously, we show that given the special structure of this problem, it can be expressed as a bilevel linear programming problem and solved to optimality in finite time via constraint generation, despite having an infinite set of constraints. This solution permits the use of efficient linear program solvers for XADD compression and enables a novel class of bounded approximate SDP algorithms for hybrid MDPs that empirically offers order-of-magnitude speedups over the exact solution in exchange for a small approximation error.