OpenRaiser/Intern-Atlas huggingface dataset:
LDC Arabic Treebanks and Associated Corpora: Data Divisions Manual
Venue: arXiv cs.CL 2013
Year: 2013

The Linguistic Data Consortium (LDC) has developed hundreds of data corpora for natural language processing (NLP) research. Among these are a number of annotated treebank corpora for Arabic. Typically, these corpora consist of a single collection of annotated documents. NLP research, however, usually requires multiple data sets for the purposes of training models, developing techniques, and final evaluation. Therefore it becomes necessary to divide the corpora used into the required data sets (divisions). This document details a set of rules that have been defined to enable consistent divisions for old and new Arabic treebanks (ATB) and related corpora.
A note on the five valued conjectures of Johansen and Helleseth and zeta functions
Venue: arXiv cs.IT 2013
Year: 2013

For the complete five-valued cross-correlation distribution between two $m$-sequences ${s_t}$ and ${s_{dt}}$ of period $2^m-1$ that differ by the decimation $d={{2^{2k}+1}\over {2^k+1}}$ where $m$ is odd and $\mbox{gcd}(k,m)=1$, Johansen and Hellseth expressed it in terms of some exponential sums. And two conjectures are presented that are of interest in their own right. In this correspondence we study these conjectures for the particular case where $k=3$, and the cases $k=1,2$ can also be analyzed in a similar process. When $k>3$, the degrees of the relevant polynomials will become higher. Here the multiplicity of the biggest absolute value of the cross-correlation is no more than one-sixth of the multiplicity corresponding the smallest absolute value.
3-D Visual Coverage Based on Gradient Descent Techniques on Matrix Manifold and Its Application to Moving Objects Monitoring
Venue: arXiv cs.SY 2013
Year: 2013

This paper investigates coverage control for visual sensor networks based on gradient descent techniques on matrix manifolds. We consider the scenario that networked vision sensors with controllable orientations are distributed over 3-D space to monitor 2-D environment. Then, the decision variable must be constrained on the Lie group SO(3). The contribution of this paper is two folds. The first one is technical, namely we formulate the coverage problem as an optimization problem on SO(3) without introducing local parameterization like Eular angles and directly apply the gradient descent algorithm on the manifold. The second technological contribution is to present not only the coverage control scheme but also the density estimation process including image processing and curve fitting while exemplifying its effectiveness through simulation of moving objects monitoring.
Almost Linear Complexity Methods for Delay-Doppler Channel Estimation
Venue: arXiv cs.IT 2013
Year: 2013

A fundamental task in wireless communication is channel estimation: Compute the channel parameters a signal undergoes while traveling from a transmitter to a receiver. In the case of delay-Doppler channel, i.e., a signal undergoes only delay and Doppler shifts, a widely used method to compute delay-Doppler parameters is the pseudo-random method. It uses a pseudo-random sequence of length N; and, in case of non-trivial relative velocity between transmitter and receiver, its computational complexity is O(N^2logN) arithmetic operations. In [1] the flag method was introduced to provide a faster algorithm for delay-Doppler channel estimation. It uses specially designed flag sequences and its complexity is O(rNlogN) for channels of sparsity r. In these notes, we introduce the incidence and cross methods for channel estimation. They use triple-chirp and double-chirp sequences of length N, correspondingly. These sequences are closely related to chirp sequences widely used in radar systems. The arithmetic complexity of the incidence and cross methods is O(NlogN + r^3), and O(NlogN + r^2), respectively.
Beyond the Shannon's Bound
Venue: arXiv cs.DS 2013
Year: 2013

Let $G=(V,E)$ be a multigraph of maximum degree $Δ$. The edges of $G$ can be colored with at most $\frac{3}{2}Δ$ colors by Shannon's theorem. We study lower bounds on the size of subgraphs of $G$ that can be colored with $Δ$ colors. Shannon's Theorem gives a bound of $\fracΔ{\lfloor\frac{3}{2}Δ\rfloor}|E|$. However, for $Δ=3$, Kamiński and Kowalik [SWAT'10] showed that there is a 3-edge-colorable subgraph of size at least $\frac{7}{9}|E|$, unless $G$ has a connected component isomorphic to $K_3+e$ (a $K_3$ with an arbitrary edge doubled). Here we extend this line of research by showing that $G$ has a $Δ$-edge colorable subgraph with at least $\fracΔ{\lfloor\frac{3}{2}Δ\rfloor-1}|E|$ edges, unless $Δ$ is even and $G$ contains $\fracΔ{2}K_3$ or $Δ$ is odd and $G$ contains $\frac{Δ-1}{2}K_3+e$. Moreover, the subgraph and its coloring can be found in polynomial time. Our results have applications in approximation algorithms for the Maximum $k$-Edge-Colorable Subgraph problem, where given a graph $G$ (without any bound on its maximum degree or other restrictions) one has to find a $k$-edge-colorable subgraph with maximum number of edges. In particular, for every even $k \ge 4$ we obtain a $\frac{2k+2}{3k+2}$-approximation and for every odd $k\ge 5$ we get a $\frac{2k+1}{3k}$-approximation. When $4\le k \le 13$ this improves over earlier algorithms due to Feige et al. [APPROX'02]
Playing with parameters: structural parameterization in graphs
Venue: arXiv cs.CC 2013
Year: 2013

When considering a graph problem from a parameterized point of view, the parameter chosen is often the size of an optimal solution of this problem (the "standard" parameter). A natural subject for investigation is what happens when we parameterize such a problem by various other parameters, some of which may be the values of optimal solutions to different problems. Such research is known as parameterized ecology. In this paper, we investigate seven natural vertex problems, along with their respective parameters: the size of a maximum independent set, the size of a minimum vertex cover, the size of a maximum clique, the chromatic number, the size of a minimum dominating set, the size of a minimum independent dominating set and the size of a minimum feedback vertex set. We study the parameterized complexity of each of these problems with respect to the standard parameter of the others.
Feature Learning with Gaussian Restricted Boltzmann Machine for Robust Speech Recognition
Venue: arXiv cs.CL 2013
Year: 2013

In this paper, we first present a new variant of Gaussian restricted Boltzmann machine (GRBM) called multivariate Gaussian restricted Boltzmann machine (MGRBM), with its definition and learning algorithm. Then we propose using a learned GRBM or MGRBM to extract better features for robust speech recognition. Our experiments on Aurora2 show that both GRBM-extracted and MGRBM-extracted feature performs much better than Mel-frequency cepstral coefficient (MFCC) with either HMM-GMM or hybrid HMM-deep neural network (DNN) acoustic model, and MGRBM-extracted feature is slightly better.
On the Dispersions of the Gel'fand-Pinsker Channel and Dirty Paper Coding
Venue: arXiv cs.IT 2013
Year: 2013

This paper studies second-order coding rates for memoryless channels with a state sequence known non-causally at the encoder. In the case of finite alphabets, an achievability result is obtained using constant-composition random coding, and by using a small fraction of the block to transmit the type of the state sequence. For error probabilities less than 1/2, it is shown that the second-order rate improves on an existing one based on i.i.d. random coding. In the Gaussian case (dirty paper coding) with an almost-sure power constraint, an achievability result is obtained used using random coding over the surface of a sphere, and using a small fraction of the block to transmit a quantized description of the state power. It is shown that the second-order asymptotics are identical to the single-user Gaussian channel of the same input power without a state.
On the Non-Uniqueness of Solutions to the Average Cost HJB for Controlled Diffusions with Near-Monotone Costs
Venue: arXiv cs.SY 2013
Year: 2013

We present a theorem for verification of optimality of controlled diffusions under the average cost criterion with near-monotone running cost, without invoking any blanket stability assumptions. The implications of this result to the policy iteration algorithm are also discussed.
Optimal Selection of Spectrum Sensing Duration for an Energy Harvesting Cognitive Radio
Venue: arXiv cs.NI 2013
Year: 2013

In this paper, we consider a time-slotted cognitive radio (CR) setting with buffered and energy harvesting primary and CR users. At the beginning of each time slot, the CR user probabilistically chooses the spectrum sensing duration from a predefined set. If the primary user (PU) is sensed to be inactive, the CR user accesses the channel immediately. The CR user optimizes the sensing duration probabilities in order to maximize its mean data service rate with constraints on the stability of the primary and cognitive queues. The optimization problem is split into two subproblems. The first is a linear-fractional program, and the other is a linear program. Both subproblems can be solved efficiently.
Maximizing the Spread of Stable Influence: Leveraging Norm-driven Moral-Motivation for Green Behavior Change in Networks
Venue: arXiv cs.SI 2013
Year: 2013

In an effort to understand why individuals choose to participate in personally-expensive pro-environmental behaviors, environmental and behavioral economists have examined a moral-motivation model in which the decision to adopt a pro-environmental behavior depends on the society-wide market share of that behavior. An increasing body of practical research on adoption of pro-environmental behavior emphasizes the importance of encouragement from local social contacts and messaging about locally-embraced norms: we respond by extending the moral-motivation model to a social networks setting. We obtain a new decision rule: an individual adopts a pro-environmental behavior if he or she observes a certain threshold of adoption within their local social neighborhood. This gives rise to a concurrent update process which describes adoption of a pro-environmental behavior spreading through a network. The original moral-motivation model corresponds to the special case of our network version in a complete graph. By improving convergence results, we formulate modest-size Integer Programs that accurately (but not efficiently) find minimum-size sets of nodes that convert the entire network, or alternately that maximize long-term adoption in the network given a limited number of nodes which may be temporarily converted. Issues of stability in determining long-term adoption are key. We give hardness of approximation results for these optimization problems. We demonstrate that there exist classes of networks which qualitatively have severely different behavior than the non-networked version, and provide preliminary computational results in in modestly-sized highly-clustered small-world networks related to the famous small-world networks of Watts and Strogatz.
Distinguishing Infections on Different Graph Topologies
Venue: arXiv cs.SI 2013
Year: 2013

The history of infections and epidemics holds famous examples where understanding, containing and ultimately treating an outbreak began with understanding its mode of spread. Influenza, HIV and most computer viruses, spread person to person, device to device, through contact networks; Cholera, Cancer, and seasonal allergies, on the other hand, do not. In this paper we study two fundamental questions of detection: first, given a snapshot view of a (perhaps vanishingly small) fraction of those infected, under what conditions is an epidemic spreading via contact (e.g., Influenza), distinguishable from a "random illness" operating independently of any contact network (e.g., seasonal allergies); second, if we do have an epidemic, under what conditions is it possible to determine which network of interactions is the main cause of the spread -- the causative network -- without any knowledge of the epidemic, other than the identity of a minuscule subsample of infected nodes? The core, therefore, of this paper, is to obtain an understanding of the diagnostic power of network information. We derive sufficient conditions networks must satisfy for these problems to be identifiable, and produce efficient, highly scalable algorithms that solve these problems. We show that the identifiability condition we give is fairly mild, and in particular, is satisfied by two common graph topologies: the grid, and the Erdos-Renyi graphs.
SIED, a Data Privacy Engineering Framework
Venue: arXiv cs.CR 2013
Year: 2013

While a number of data privacy techniques have been proposed in the recent years, a few frameworks have been suggested for the implementation of the data privacy process. Most of the proposed approaches are tailored towards implementing a specific data privacy algorithm but not the overall data privacy engineering and design process. Therefore, as a contribution, this study proposes SIED (Specification, Implementation, Evaluation, and Dissemination), a conceptual framework that takes a holistic approach to the data privacy engineering procedure by looking at the specifications, implementation, evaluation, and finally, dissemination of the privatized data sets.
On the Connectivity Preserving Minimum Cut Problem
Venue: arXiv cs.DS 2013
Year: 2013

In this paper, we study a generalization of the classical minimum cut prob- lem, called Connectivity Preserving Minimum Cut (CPMC) problem, which seeks a minimum cut to separate a pair (or pairs) of source and destination nodes and meanwhile ensure the connectivity between the source and its partner node(s). The CPMC problem is a rather powerful formulation for a set of problems and finds applications in many other areas, such as network security, image processing, data mining, pattern recognition, and machine learning. For this important problem, we consider two variants, connectiv- ity preserving minimum node cut (CPMNC) and connectivity preserving minimum edge cut (CPMEC). For CPMNC, we show that it cannot be ap- proximated within αlogn for some constant α unless P=NP, and cannot be approximated within any poly(logn) unless NP has quasi-polynomial time algorithms. The hardness results hold even for graphs with unit weight and bipartite graphs. Particularly, we show that polynomial time solutions exist for CPMEC in planar graphs and for CPMNC in some special planar graphs. The hardness of CPMEC in general graphs remains open, but the polynomial time algorithm in planar graphs still has important practical applications.
The Multiple-orientability Thresholds for Random Hypergraphs
Venue: arXiv cs.DM 2013
Year: 2013

A $k$-uniform hypergraph $H = (V, E)$ is called $\ell$-orientable, if there is an assignment of each edge $e\in E$ to one of its vertices $v\in e$ such that no vertex is assigned more than $\ell$ edges. Let $H_{n,m,k}$ be a hypergraph, drawn uniformly at random from the set of all $k$-uniform hypergraphs with $n$ vertices and $m$ edges. In this paper we establish the threshold for the $\ell$-orientability of $H_{n,m,k}$ for all $k\ge 3$ and $\ell \ge 2$, i.e., we determine a critical quantity $c_{k, \ell}^*$ such that with probability $1-o(1)$ the graph $H_{n,cn,k}$ has an $\ell$-orientation if $c < c_{k, \ell}^*$, but fails doing so if $c > c_{k, \ell}^*$. Our result has various applications including sharp load thresholds for cuckoo hashing, load balancing with guaranteed maximum load, and massive parallel access to hard disk arrays.
Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases
Venue: arXiv cs.DB 2013
Year: 2013

The best current methods for exactly computing the number of satisfying assignments, or the satisfying probability, of Boolean formulas can be seen, either directly or indirectly, as building 'decision-DNNF' (decision decomposable negation normal form) representations of the input Boolean formulas. Decision-DNNFs are a special case of 'd-DNNF's where 'd' stands for 'deterministic'. We show that any decision-DNNF can be converted into an equivalent 'FBDD' (free binary decision diagram) -- also known as a 'read-once branching program' (ROBP or 1-BP) -- with only a quasipolynomial increase in representation size in general, and with only a polynomial increase in size in the special case of monotone k-DNF formulas. Leveraging known exponential lower bounds for FBDDs, we then obtain similar exponential lower bounds for decision-DNNFs which provide lower bounds for the recent algorithms. We also separate the power of decision-DNNFs from d-DNNFs and a generalization of decision-DNNFs known as AND-FBDDs. Finally we show how these imply exponential lower bounds for natural problems associated with probabilistic databases.
Probabilistic Conditional Preference Networks
Venue: arXiv cs.AI 2013
Year: 2013

In order to represent the preferences of a group of individuals, we introduce Probabilistic CP-nets (PCP-nets). PCP-nets provide a compact language for representing probability distributions over preference orderings. We argue that they are useful for aggregating preferences or modelling noisy preferences. Then we give efficient algorithms for the main reasoning problems, namely for computing the probability that a given outcome is preferred to another one, and the probability that a given outcome is optimal. As a by-product, we obtain an unexpected linear-time algorithm for checking dominance in a standard, tree-structured CP-net.
Hilbert Space Embeddings of Predictive State Representations
Venue: arXiv cs.LG 2013
Year: 2013

Predictive State Representations (PSRs) are an expressive class of models for controlled stochastic processes. PSRs represent state as a set of predictions of future observable events. Because PSRs are defined entirely in terms of observable data, statistically consistent estimates of PSR parameters can be learned efficiently by manipulating moments of observed training data. Most learning algorithms for PSRs have assumed that actions and observations are finite with low cardinality. In this paper, we generalize PSRs to infinite sets of observations and actions, using the recent concept of Hilbert space embeddings of distributions. The essence is to represent the state as a nonparametric conditional embedding operator in a Reproducing Kernel Hilbert Space (RKHS) and leverage recent work in kernel methods to estimate, predict, and update the representation. We show that these Hilbert space embeddings of PSRs are able to gracefully handle continuous actions and observations, and that our learned models outperform competing system identification algorithms on several prediction benchmarks.
SparsityBoost: A New Scoring Function for Learning Bayesian Network Structure
Venue: arXiv cs.LG 2013
Year: 2013

We give a new consistent scoring function for structure learning of Bayesian networks. In contrast to traditional approaches to scorebased structure learning, such as BDeu or MDL, the complexity penalty that we propose is data-dependent and is given by the probability that a conditional independence test correctly shows that an edge cannot exist. What really distinguishes this new scoring function from earlier work is that it has the property of becoming computationally easier to maximize as the amount of data increases. We prove a polynomial sample complexity result, showing that maximizing this score is guaranteed to correctly learn a structure with no false edges and a distribution close to the generating distribution, whenever there exists a Bayesian network which is a perfect map for the data generating distribution. Although the new score can be used with any search algorithm, we give empirical results showing that it is particularly effective when used together with a linear programming relaxation approach to Bayesian network structure learning.
Optimization With Parity Constraints: From Binary Codes to Discrete Integration
Venue: arXiv cs.AI 2013
Year: 2013

Many probabilistic inference tasks involve summations over exponentially large sets. Recently, it has been shown that these problems can be reduced to solving a polynomial number of MAP inference queries for a model augmented with randomly generated parity constraints. By exploiting a connection with max-likelihood decoding of binary codes, we show that these optimizations are computationally hard. Inspired by iterative message passing decoding algorithms, we propose an Integer Linear Programming (ILP) formulation for the problem, enhanced with new sparsification techniques to improve decoding performance. By solving the ILP through a sequence of LP relaxations, we get both lower and upper bounds on the partition function, which hold with high probability and are much tighter than those obtained with variational methods.
Solving Limited-Memory Influence Diagrams Using Branch-and-Bound Search
Venue: arXiv cs.AI 2013
Year: 2013

A limited-memory influence diagram (LIMID) generalizes a traditional influence diagram by relaxing the assumptions of regularity and no-forgetting, allowing a wider range of decision problems to be modeled. Algorithms for solving traditional influence diagrams are not easily generalized to solve LIMIDs, however, and only recently have exact algorithms for solving LIMIDs been developed. In this paper, we introduce an exact algorithm for solving LIMIDs that is based on branch-and-bound search. Our approach is related to the approach of solving an influence diagram by converting it to an equivalent decision tree, with the difference that the LIMID is converted to a much smaller decision graph that can be searched more efficiently.
A Sound and Complete Algorithm for Learning Causal Models from Relational Data
Venue: arXiv cs.AI 2013
Year: 2013

The PC algorithm learns maximally oriented causal Bayesian networks. However, there is no equivalent complete algorithm for learning the structure of relational models, a more expressive generalization of Bayesian networks. Recent developments in the theory and representation of relational models support lifted reasoning about conditional independence. This enables a powerful constraint for orienting bivariate dependencies and forms the basis of a new algorithm for learning structure. We present the relational causal discovery (RCD) algorithm that learns causal relational models. We prove that RCD is sound and complete, and we present empirical results that demonstrate effectiveness.
The Supervised IBP: Neighbourhood Preserving Infinite Latent Feature Models
Venue: arXiv cs.LG 2013
Year: 2013

We propose a probabilistic model to infer supervised latent variables in the Hamming space from observed data. Our model allows simultaneous inference of the number of binary latent variables, and their values. The latent variables preserve neighbourhood structure of the data in a sense that objects in the same semantic concept have similar latent values, and objects in different concepts have dissimilar latent values. We formulate the supervised infinite latent variable problem based on an intuitive principle of pulling objects together if they are of the same type, and pushing them apart if they are not. We then combine this principle with a flexible Indian Buffet Process prior on the latent variables. We show that the inferred supervised latent variables can be directly used to perform a nearest neighbour search for the purpose of retrieval. We introduce a new application of dynamically extending hash codes, and show how to effectively couple the structure of the hash codes with continuously growing structure of the neighbourhood preserving infinite latent feature space.