OpenRaiser/Intern-Atlas huggingface dataset:
The Anchors Hierachy: Using the triangle inequality to survive high dimensional data
Venue: arXiv cs.LG 2013
Year: 2013

This paper is about metric data structures in high-dimensional or non-Euclidean space that permit cached sufficient statistics accelerations of learning algorithms. It has recently been shown that for less than about 10 dimensions, decorating kd-trees with additional "cached sufficient statistics" such as first and second moments and contingency tables can provide satisfying acceleration for a very wide range of statistical learning tasks such as kernel regression, locally weighted regression, k-means clustering, mixture modeling and Bayes Net learning. In this paper, we begin by defining the anchors hierarchy - a fast data structure and algorithm for localizing data based only on a triangle-inequality-obeying distance metric. We show how this, in its own right, gives a fast and effective clustering of data. But more importantly we show how it can produce a well-balanced structure similar to a Ball-Tree (Omohundro, 1991) or a kind of metric tree (Uhlmann, 1991; Ciaccia, Patella, & Zezula, 1997) in a way that is neither "top-down" nor "bottom-up" but instead "middle-out". We then show how this structure, decorated with cached sufficient statistics, allows a wide variety of statistical learning algorithms to be accelerated even in thousands of dimensions.
Nash Convergence of Gradient Dynamics in Iterated General-Sum Games
Venue: arXiv cs.GT 2013
Year: 2013

Multi-agent games are becoming an increasing prevalent formalism for the study of electronic commerce and auctions. The speed at which transactions can take place and the growing complexity of electronic marketplaces makes the study of computationally simple agents an appealing direction. In this work, we analyze the behavior of agents that incrementally adapt their strategy through gradient ascent on expected payoff, in the simple setting of two-player, two-action, iterated general-sum games, and present a surprising result. We show that either the agents will converge to Nash equilibrium, or if the strategies themselves do not converge, then their average payoffs will nevertheless converge to the payoffs of a Nash equilibrium.
On the Use of Skeletons when Learning in Bayesian Networks
Venue: arXiv cs.AI 2013
Year: 2013

In this paper, we present a heuristic operator which aims at simultaneously optimizing the orientations of all the edges in an intermediate Bayesian network structure during the search process. This is done by alternating between the space of directed acyclic graphs (DAGs) and the space of skeletons. The found orientations of the edges are based on a scoring function rather than on induced conditional independences. This operator can be used as an extension to commonly employed search strategies. It is evaluated in experiments with artificial and real-world data.
A Branch-and-Bound Algorithm for MDL Learning Bayesian Networks
Venue: arXiv cs.AI 2013
Year: 2013

This paper extends the work in [Suzuki, 1996] and presents an efficient depth-first branch-and-bound algorithm for learning Bayesian network structures, based on the minimum description length (MDL) principle, for a given (consistent) variable ordering. The algorithm exhaustively searches through all network structures and guarantees to find the network with the best MDL score. Preliminary experiments show that the algorithm is efficient, and that the time complexity grows slowly with the sample size. The algorithm is useful for empirically studying both the performance of suboptimal heuristic search algorithms and the adequacy of the MDL principle in learning Bayesian networks.
On retracts, absolute retracts, and folds in cographs
Venue: arXiv cs.DM 2013
Year: 2013

Let G and H be two cographs. We show that the problem to determine whether H is a retract of G is NP-complete. We show that this problem is fixed-parameter tractable when parameterized by the size of H. When restricted to the class of threshold graphs or to the class of trivially perfect graphs, the problem becomes tractable in polynomial time. The problem is also soluble when one cograph is given as an induced subgraph of the other. We characterize absolute retracts of cographs.
Energy-Efficient Scheduling with Time and Processors Eligibility Restrictions
Venue: arXiv cs.DS 2013
Year: 2013

While previous work on energy-efficient algorithms focused on assumption that tasks can be assigned to any processor, we initially study the problem of task scheduling on restricted parallel processors. The objective is to minimize the overall energy consumption while speed scaling (SS) method is used to reduce energy consumption under the execution time constraint (Makespan $C_{max}$). In this work, we discuss the speed setting in the continuous model that processors can run at arbitrary speed in $[s_{min},s_{max}]$. The energy-efficient scheduling problem, involving task assignment and speed scaling, is inherently complicated as it is proved to be NP-Complete. We formulate the problem as an Integer Programming (IP) problem. Specifically, we devise a polynomial time optimal scheduling algorithm for the case tasks have a uniform size. Our algorithm runs in $O(mn^3logn)$ time, where $m$ is the number of processors and $n$ is the number of tasks. We then present a polynomial time algorithm that achieves an approximation factor of $2^{α-1}(2-\frac{1}{m^α})$ ($α$ is the power parameter) when the tasks have arbitrary size work. Experimental results demonstrate that our algorithm could provide an efficient scheduling for the problem of task scheduling on restricted parallel processors.
Network Throughput Optimization via Error Correcting Codes
Venue: arXiv cs.IT 2013
Year: 2013

A new network construction method is presented for building of scalable, high throughput, low latency networks. The method is based on the exact equivalence discovered between the problem of maximizing network throughput (measured as bisection bandwidth) for a large class of practically interesting Cayley graphs and the problem of maximizing codeword distance for linear error correcting codes. Since the latter problem belongs to a more mature research field with large collections of optimal solutions available, a simple translation recipe is provided for converting the existent optimal error correcting codes into optimal throughput networks. The resulting networks, called here Long Hop networks, require 1.5-5 times fewer switches, 2-6 times fewer internal cables and 1.2-2 times fewer `average hops' than the best presently known networks for the same number of ports provided and the same total throughput. These advantage ratios increase with the network size and switch radix. Independently interesting byproduct of the discovered equivalence is an efficient O(n*log(n)) algorithm based on Walsh-Hadamard transform for computing exact bisections of this class of Cayley graphs (this is NP complete problem for general graphs).
Improving the Spectral Efficiency of Nonlinear Satellite Systems through Time-Frequency Packing and Advanced Processing
Venue: arXiv cs.IT 2013
Year: 2013

We consider realistic satellite communications systems for broadband and broadcasting applications, based on frequency-division-multiplexed linear modulations, where spectral efficiency is one of the main figures of merit. For these systems, we investigate their ultimate performance limits by using a framework to compute the spectral efficiency when suboptimal receivers are adopted and evaluating the performance improvements that can be obtained through the adoption of the time-frequency packing technique. Our analysis reveals that introducing controlled interference can significantly increase the efficiency of these systems. Moreover, if a receiver which is able to account for the interference and the nonlinear impairments is adopted, rather than a classical predistorter at the transmitter coupled with a simpler receiver, the benefits in terms of spectral efficiency can be even larger. Finally, we consider practical coded schemes and show the potential advantages of the optimized signaling formats when combined with iterative detection/decoding.
One-Round Multi-Party Communication Complexity of Distinguishing Sums
Venue: arXiv cs.CC 2013
Year: 2013

We consider an instance of the following problem: Parties P_1,..., P_k each receive an input x_i, and a coordinator (distinct from each of these parties) wishes to compute f(x_1,..., x_k) for some predicate f. We are interested in one-round protocols where each party sends a single message to the coordinator; there is no communication between the parties themselves. What is the minimum communication complexity needed to compute f, possibly with bounded error? We prove tight bounds on the one-round communication complexity when f corresponds to the promise problem of distinguishing sums (namely, determining which of two possible values the {x_i} sum to) or the problem of determining whether the {x_i} sum to a particular value. Similar problems were studied previously by Nisan and in concurrent work by Viola. Our proofs rely on basic theorems from additive combinatorics, but are otherwise elementary.
A Decidable Theory of Skiplists of Unbounded Size and Arbitrary Height
Venue: arXiv cs.LO 2013
Year: 2013

This paper presents a theory of skiplists of arbitrary height, and shows decidability of the satisfiability problem for quantifier-free formulas. A skiplist is an imperative software data structure that implements sets by maintaining several levels of ordered singly-linked lists in memory, where each level is a sublist of its lower levels. Skiplists are widely used in practice because they offer a performance comparable to balanced binary trees, and can be implemented more efficiently. To achieve this performance, most implementations dynamically increment the height (the number of levels). Skiplists are difficult to reason about because of the dynamic size (number of nodes) and the sharing between the different layers. Furthermore, reasoning about dynamic height adds the challenge of dealing with arbitrary many levels. The first contribution of this paper is the theory TSL that allows to express the heap memory layout of a skiplist of arbitrary height. The second contribution is a decision procedure for the satisfiability prob- lem of quantifier-free TSL formulas. The last contribution is to illustrate the formal verification of a practical skiplist implementation using this decision procedure.
Language learning from positive evidence, reconsidered: A simplicity-based approach
Venue: arXiv cs.CL 2013
Year: 2013

Children learn their native language by exposure to their linguistic and communicative environment, but apparently without requiring that their mistakes are corrected. Such learning from positive evidence has been viewed as raising logical problems for language acquisition. In particular, without correction, how is the child to recover from conjecturing an over-general grammar, which will be consistent with any sentence that the child hears? There have been many proposals concerning how this logical problem can be dissolved. Here, we review recent formal results showing that the learner has sufficient data to learn successfully from positive evidence, if it favours the simplest encoding of the linguistic input. Results include the ability to learn a linguistic prediction, grammaticality judgements, language production, and form-meaning mappings. The simplicity approach can also be scaled-down to analyse the ability to learn a specific linguistic constructions, and is amenable to empirical test as a framework for describing human language acquisition.
Binary Diversity for Non-Binary LDPC Codes over the Rayleigh Channel
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we analyze the performance of several bit-interleaving strategies applied to Non-Binary Low-Density Parity-Check (LDPC) codes over the Rayleigh fading channel. The technique of bit-interleaving used over fading channel introduces diversity which could provide important gains in terms of frame error probability and detection. This paper demonstrates the importance of the way of implementing the bit-interleaving, and proposes a design of an optimized bit-interleaver inspired from the Progressive Edge Growth algorithm. This optimization algorithm depends on the topological structure of a given LDPC code and can also be applied to any degree distribution and code realization. In particular, we focus on non-binary LDPC codes based on graph with constant symbol-node connection $d_v = 2$. These regular $(2,dc)$-NB-LDPC codes demonstrate best performance, thanks to their large girths and improved decoding thresholds growing with the order of Finite Field. Simulations show excellent results of the proposed interleaving technique compared to the random interleaver as well as to the system without interleaver.
Average-Case Performance of Rollout Algorithms for Knapsack Problems
Venue: arXiv cs.DS 2013
Year: 2013

Rollout algorithms have demonstrated excellent performance on a variety of dynamic and discrete optimization problems. Interpreted as an approximate dynamic programming algorithm, a rollout algorithm estimates the value-to-go at each decision stage by simulating future events while following a greedy policy, referred to as the base policy. While in many cases rollout algorithms are guaranteed to perform as well as their base policies, there have been few theoretical results showing additional improvement in performance. In this paper we perform a probabilistic analysis of the subset sum problem and knapsack problem, giving theoretical evidence that rollout algorithms perform strictly better than their base policies. Using a stochastic model from the existing literature, we analyze two rollout methods that we refer to as the consecutive rollout and exhaustive rollout, both of which employ a simple greedy base policy. For the subset sum problem, we prove that after only a single iteration of the rollout algorithm, both methods yield at least a 30% reduction in the expected gap between the solution value and capacity, relative to the base policy. Analogous results are shown for the knapsack problem.
Sophie, an FDTD code on the way to multicore, getting rid of the memory bandwidth bottleneck better using cache
Venue: arXiv cs.DC 2013
Year: 2013

FDTD codes, such as Sophie developed at CEA/DAM, no longer take advantage of the processor's increased computing power, especially recently with the raising multicore technology. This is rooted in the fact that low order numerical schemes need an important memory bandwidth to bring and store the computed fields. The aim of this article is to present a programming method at the software's architecture level that improves the memory access pattern in order to reuse data in cache instead of constantly accessing RAM memory. We will exhibit a more than two computing time improvement in practical applications. The target audience of this article is made of computing scientists and of electrical engineers that develop simulation codes with no specific knowledge in computer science or electronics.
Consensus Networks over Finite Fields
Venue: arXiv cs.SY 2013
Year: 2013

This work studies consensus strategies for networks of agents with limited memory, computation, and communication capabilities. We assume that agents can process only values from a finite alphabet, and we adopt the framework of finite fields, where the alphabet consists of the integers {0,...,p-1}, for some prime number p, and operations are performed modulo p. Thus, we define a new class of consensus dynamics, which can be exploited in certain applications such as pose estimation in capacity and memory constrained sensor networks. For consensus networks over finite fields, we provide necessary and sufficient conditions on the network topology and weights to ensure convergence. We show that consensus networks over finite fields converge in finite time, a feature that can be hardly achieved over the field of real numbers. For the design of finite-field consensus networks, we propose a general design method, with high computational complexity, and a network composition rule to generate large consensus networks from smaller components. Finally, we discuss the application of finite-field consensus networks to distributed averaging and pose estimation in sensor networks.
Real Time scheduling with Virtual Nodes for Self Stabilization in Wireless Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

In this paper we propose a new scheduling algorithm called Real Time Scheduling (RTS) which uses virtual nodes for self stabilization. This algorithm deals with all the contributing components of the end-to-end travelling delay of data packets in sensor network and with virtual nodes algorithm achieves QoS in terms of packet delivery, multiple connections, better power management and stable routes in case of failure. RTS delays packets at intermediate hops (not just prioritizes them) for a duration that is a function of their deadline. Delaying packets allows the network to avoid hot spotting while maintaining deadline-faithfulness. We compare RTS with another prioritizing and scheduling algorithm for real-time data dissemination in sensor networks, velocity monotonic scheduling. This paper simulates RTS based on two typical routing protocols, shortest path routing and greedy forwarding with J-Sim.
Recurrent Neural Network Method in Arabic Words Recognition System
Venue: arXiv cs.NE 2013
Year: 2013

The recognition of unconstrained handwriting continues to be a difficult task for computers despite active research for several decades. This is because handwritten text offers great challenges such as character and word segmentation, character recognition, variation between handwriting styles, different character size and no font constraints as well as the background clarity. In this paper primarily discussed Online Handwriting Recognition methods for Arabic words which being often used among then across the Middle East and North Africa people. Because of the characteristic of the whole body of the Arabic words, namely connectivity between the characters, thereby the segmentation of An Arabic word is very difficult. We introduced a recurrent neural network to online handwriting Arabic word recognition. The key innovation is a recently produce recurrent neural networks objective function known as connectionist temporal classification. The system consists of an advanced recurrent neural network with an output layer designed for sequence labeling, partially combined with a probabilistic language model. Experimental results show that unconstrained Arabic words achieve recognition rates about 79%, which is significantly higher than the about 70% using a previously developed hidden markov model based recognition system.
Cross-layer Optimization for Next Generation Wi-Fi
Venue: arXiv cs.ET 2013
Year: 2013

From the initial 1997 specification to the undergoing IEEE 802.11ac standardization, a leap in throughput has been observed with every new generation. The expectations for next generations on issues like throughput, range, reliability, and power consumption are even higher. This is quite a challenge considering all the work already done. Cross-layer optimization of physical (PHY) and medium access control (MAC) layers can be an interesting exploration path for further enhancement. During this thesis we have studied cross-layer optimization techniques, with a focus on the IEEE 802.11ac standard. A new multichannel aggregation scheme involving cross-knowledge between PHY and MAC layers has been proposed to improve performance in collision-prone environments. We have shown that some functionalities directly involved PHY and MAC layers. An accurate modeling of both PHY and MAC mechanisms is thus needed to have a realistic characterization of such functionalities. A cross-layer simulator, compliant with IEEE 802.11ac specifications, has thus been implemented. To the best of our knowledge, this is the first simulator incorporating detailed PHY and MAC functionalities for the IEEE 802.11ac standard. The multiple-user multiple-input, multiple-output (MU-MIMO) technique, which is one of the main innovations of the IEEE 802.11ac, needs both PHY and MAC layer considerations. We have thus used the implemented cross-layer simulator to evaluate the performance of MU-MIMO and compared it with the single-user MIMO (SU-MIMO). The aim of these studies was to evaluate the 'real' gains of MU-MIMO solutions (accounting for PHY+MAC) over SU-MIMO solutions and not the generally accepted ones. The impact of the channel sounding interval has particularly been studied. Finally, we have proposed a short PHY layer version of acknowledgment frames for overhead reduction in IEEE 802.11ah communications.
Duality and Optimization for Generalized Multi-hop MIMO Amplify-and-Forward Relay Networks with Linear Constraints
Venue: arXiv cs.IT 2013
Year: 2013

We consider a generalized multi-hop MIMO amplify-and-forward (AF) relay network with multiple sources/destinations and arbitrarily number of relays. We establish two dualities and the corresponding dual transformations between such a network and its dual, respectively under single network linear constraint and per-hop linear constraint. The result is a generalization of the previous dualities under different special cases and is proved using new techniques which reveal more insight on the duality structure that can be exploited to optimize MIMO precoders. A unified optimization framework is proposed to find a stationary point for an important class of non-convex optimization problems of AF relay networks based on a local Lagrange dual method, where the primal algorithm only finds a stationary point for the inner loop problem of maximizing the Lagrangian w.r.t. the primal variables. The input covariance matrices are shown to satisfy a polite water-filling structure at a stationary point of the inner loop problem. The duality and polite water-filling are exploited to design fast primal algorithms. Compared to the existing algorithms, the proposed optimization framework with duality-based primal algorithms can be used to solve more general problems with lower computation cost.
Throughput Optimizing Localized Link Scheduling for Multihop Wireless Networks Under Physical Interference Model
Venue: arXiv cs.NI 2013
Year: 2013

We study throughput-optimum localized link scheduling in wireless networks. The majority of results on link scheduling assume binary interference models that simplify interference constraints in actual wireless communication. While the physical interference model reflects the physical reality more precisely, the problem becomes notoriously harder under the physical interference model. There have been just a few existing results on link scheduling under the physical interference model, and even fewer on more practical distributed or localized scheduling. In this paper, we tackle the challenges of localized link scheduling posed by the complex physical interference constraints. By cooperating the partition and shifting strategies into the pick-and-compare scheme, we present a class of localized scheduling algorithms with provable throughput guarantee subject to physical interference constraints. The algorithm in the linear power setting is the first localized algorithm that achieves at least a constant fraction of the optimal capacity region subject to physical interference constraints. The algorithm in the uniform power setting is the first localized algorithm with a logarithmic approximation ratio to the optimal solution. Our extensive simulation results demonstrate correctness and performance efficiency of our algorithms.