OpenRaiser/Intern-Atlas huggingface dataset:
A Statistical Parsing Framework for Sentiment Classification
Venue: arXiv cs.CL 2015
Year: 2015

We present a statistical parsing framework for sentence-level sentiment classification in this article. Unlike previous works that employ syntactic parsing results for sentiment analysis, we develop a statistical parser to directly analyze the sentiment structure of a sentence. We show that complicated phenomena in sentiment analysis (e.g., negation, intensification, and contrast) can be handled the same as simple and straightforward sentiment expressions in a unified and probabilistic way. We formulate the sentiment grammar upon Context-Free Grammars (CFGs), and provide a formal description of the sentiment parsing framework. We develop the parsing model to obtain possible sentiment parse trees for a sentence, from which the polarity model is proposed to derive the sentiment strength and polarity, and the ranking model is dedicated to selecting the best sentiment tree. We train the parser directly from examples of sentences annotated only with sentiment polarity labels but without any syntactic annotations or polarity annotations of constituents within sentences. Therefore we can obtain training data easily. In particular, we train a sentiment parser, s.parser, from a large amount of review sentences with users' ratings as rough sentiment polarity labels. Extensive experiments on existing benchmark datasets show significant improvements over baseline sentiment classification approaches.
Synchrony in Neuronal Communications: An Energy Efficient Scheme
Venue: arXiv cs.IT 2015
Year: 2015

We are interested in understanding the neural correlates of attentional processes using first principles. Here we apply a recently developed first principles approach that uses transmitted information in bits per joule to quantify the energy efficiency of information transmission for an inter-spike-interval (ISI) code that can be modulated by means of the synchrony in the presynaptic population. We simulate a single compartment conductance-based model neuron driven by excitatory and inhibitory spikes from a presynaptic population, where the rate and synchrony in the presynaptic excitatory population may vary independently from the average rate. We find that for a fixed input rate, the ISI distribution of the post synaptic neuron depends on the level of synchrony and is well-described by a Gamma distribution for synchrony levels less than 50%. For levels of synchrony between 15% and 50% (restricted for technical reasons), we compute the optimum input distribution that maximizes the mutual information per unit energy. This optimum distribution shows that an increased level of synchrony, as it has been reported experimentally in attention-demanding conditions, reduces the mode of the input distribution and the excitability threshold of post synaptic neuron. This facilitates a more energy efficient neuronal communication.
Causal Network Inference by Optimal Causation Entropy
Venue: arXiv cs.IT 2015
Year: 2015

The broad abundance of time series data, which is in sharp contrast to limited knowledge of the underlying network dynamic processes that produce such observations, calls for a rigorous and efficient method of causal network inference. Here we develop mathematical theory of causation entropy, an information-theoretic statistic designed for model-free causality inference. For stationary Markov processes, we prove that for a given node in the network, its causal parents forms the minimal set of nodes that maximizes causation entropy, a result we refer to as the optimal causation entropy principle. Furthermore, this principle guides us to develop computational and data efficient algorithms for causal network inference based on a two-step discovery and removal algorithm for time series data for a network-couple dynamical system. Validation in terms of analytical and numerical results for Gaussian processes on large random networks highlight that inference by our algorithm outperforms previous leading methods including conditioned Granger causality and transfer entropy. Interestingly, our numerical results suggest that the number of samples required for accurate inference depends strongly on network characteristics such as the density of links and information diffusion rate and not necessarily on the number of nodes.
Reliable Communication in a Dynamic Network in the Presence of Byzantine Faults
Venue: arXiv cs.DC 2015
Year: 2015

We consider the following problem: two nodes want to reliably communicate in a dynamic multihop network where some nodes have been compromised, and may have a totally arbitrary and unpredictable behavior. These nodes are called Byzantine. We consider the two cases where cryptography is available and not available. We prove the necessary and sufficient condition (that is, the weakest possible condition) to ensure reliable communication in this context. Our proof is constructive, as we provide Byzantine-resilient algorithms for reliable communication that are optimal with respect to our impossibility results. In a second part, we investigate the impact of our conditions in three case studies: participants interacting in a conference, robots moving on a grid and agents in the subway. Our simulations indicate a clear benefit of using our algorithms for reliable communication in those contexts.
Distributed Kalman Filtering over Massive Data Sets: Analysis Through Large Deviations of Random Riccati Equations
Venue: arXiv cs.IT 2015
Year: 2015

This paper studies the convergence of the estimation error process and the characterization of the corresponding invariant measure in distributed Kalman filtering for potentially unstable and large linear dynamic systems. A gossip network protocol termed Modified Gossip Interactive Kalman Filtering (M-GIKF) is proposed, where sensors exchange their filtered states (estimates and error covariances) and propagate their observations via inter-sensor communications of rate $\overlineγ$; $\overlineγ$ is defined as the averaged number of inter-sensor message passages per signal evolution epoch. The filtered states are interpreted as stochastic particles swapped through local interaction. The paper shows that the conditional estimation error covariance sequence at each sensor under M-GIKF evolves as a random Riccati equation (RRE) with Markov modulated switching. By formulating the RRE as a random dynamical system, it is shown that the network achieves weak consensus, i.e., the conditional estimation error covariance at a randomly selected sensor converges weakly (in distribution) to a unique invariant measure. Further, it is proved that as $\overlineγ \rightarrow \infty$ this invariant measure satisfies the Large Deviation (LD) upper and lower bounds, implying that this measure converges exponentially fast (in probability) to the Dirac measure $δ_{P^*}$, where $P^*$ is the stable error covariance of the centralized (Kalman) filtering setup. The LD results answer a fundamental question on how to quantify the rate at which the distributed scheme approaches the centralized performance as the inter-sensor communication rate increases.
Vector Bin-and-Cancel for MIMO Distributed Full-Duplex
Venue: arXiv cs.IT 2015
Year: 2015

In a multi-input multi-output (MIMO) full-duplex network, where an in-band full-duplex infrastruc- ture node communicates with two half-duplex mobiles supporting simultaneous up- and downlink flows, the inter-mobile interference between the up- and downlink mobiles limits the system performance. We study the impact of leveraging an out-of-band side-channel between mobiles in such network under different channel models. For time-invariant channels, we aim to characterize the generalized degrees- of-freedom (GDoF) of the side-channel assisted MIMO full-duplex network. For slow-fading channels, we focus on the diversity-multiplexing tradeoff (DMT) of the system with various assumptions as to the availability of channel state information at the transmitter (CSIT). The key to the optimal performance is a vector bin-and-cancel strategy leveraging Han-Kobayashi message splitting, which is shown to achieve the system capacity region to within a constant bit. We quantify how the side-channel improve the GDoF and DMT compared to a system without the extra orthogonal spectrum. The insights gained from our analysis reveal: i) the tradeoff between spatial resources from multiple antennas at different nodes and spectral resources of the side-channel, and ii) the interplay between the channel uncertainty at the transmitter and use of the side-channel.
Fast Numerical Nonlinear Fourier Transforms
Venue: arXiv cs.IT 2015
Year: 2015

The nonlinear Fourier transform, which is also known as the forward scattering transform, decomposes a periodic signal into nonlinearly interacting waves. In contrast to the common Fourier transform, these waves no longer have to be sinusoidal. Physically relevant waveforms are often available for the analysis instead. The details of the transform depend on the waveforms underlying the analysis, which in turn are specified through the implicit assumption that the signal is governed by a certain evolution equation. For example, water waves generated by the Korteweg-de Vries equation can be expressed in terms of cnoidal waves. Light waves in optical fiber governed by the nonlinear Schrödinger equation (NSE) are another example. Nonlinear analogs of classic problems such as spectral analysis and filtering arise in many applications, with information transmission in optical fiber, as proposed by Yousefi and Kschischang, being a very recent one. The nonlinear Fourier transform is eminently suited to address them -- at least from a theoretical point of view. Although numerical algorithms are available for computing the transform, a "fast" nonlinear Fourier transform that is similarly effective as the fast Fourier transform is for computing the common Fourier transform has not been available so far. The goal of this paper is to address this problem. Two fast numerical methods for computing the nonlinear Fourier transform with respect to the NSE are presented. The first method achieves a runtime of $O(D^2)$ floating point operations, where $D$ is the number of sample points. The second method applies only to the case where the NSE is defocusing, but it achieves an $O(D\log^2D)$ runtime. Extensions of the results to other evolution equations are discussed as well.
Recurrence for Pandimensional Space-Filling Functions
Venue: arXiv cs.CG 2015
Year: 2015

A space-filling function is a bijection from the unit line segment to the unit square, cube, or hypercube. The function from the unit line segment is continuous. The inverse function, while well-defined, is not continuous. Space-filling curves, the finite approximations to space-filling functions, have found application in global optimization, database indexing, and dimension reduction among others. For these applications the desired transforms are mapping a scalar to multidimensional coordinates and mapping multidimensional coordinates to a scalar. Presented are recurrences which produce space-filling functions and curves of any rank $d\ge2$ based on serpentine Hamiltonian paths on $({\bf Z}\bmod s)^d$ where $s\ge2$. The recurrences for inverse space-filling functions are also presented. Both Peano and Hilbert curves and functions and their generalizations to higher dimensions are produced by these recurrences. The computations of these space-filling functions and their inverse functions are absolutely convergent geometric series. The space-filling functions are constructed as limits of integer recurrences and equivalently as non-terminating real recurrences. Scaling relations are given which enable the space-filling functions and curves and their inverses to extend beyond the unit area or volume and even to all of $d$-space. This unification of pandimensional space-filling curves facilitates quantitative comparison of curves generated from different Hamiltonian paths. The isotropy and performance in dimension reduction of a variety of space-filling curves are analyzed. For dimension reduction it is found that Hilbert curves perform somewhat better than Peano curves and their isotropic variants.
On the Performance of Optimized Dense Device-to-Device Wireless Networks
Venue: arXiv cs.IT 2015
Year: 2015

We consider a D2D wireless network where $n$ users are densely deployed in a squared planar region and communicate with each other without the help of a wired infrastructure. For this network, we examine the 3-phase hierarchical cooperation (HC) scheme and the 2-phase improved HC scheme based on the concept of {\em network multiple access}. Exploiting recent results on the optimality of treating interference as noise in Gaussian interference channels, we optimize the achievable average per-link rate and not just its scaling law. In addition, we provide further improvements on both the previously proposed hierarchical cooperation schemes by a more efficient use of TDMA and spatial reuse. Thanks to our explicit achievable rate expressions, we can compare HC scheme with multihop routing (MR), where the latter can be regarded as the current practice of D2D wireless networks. Our results show that the improved and optimized HC schemes yield very significant rate gains over MR in realistic conditions of channel propagation exponents, signal to noise ratio, and number of users. This sheds light on the long-standing question about the real advantage of HC scheme over MR beyond the well-known scaling laws analysis. In contrast, we also show that our rate optimization is non-trivial, since when HC is applied with off-the-shelf choice of the system parameters, no significant rate gain with respect to MR is achieved. We also show that for large pathloss exponent the sum rate is a nearly linear function of the number of users $n$ in the range of networks of practical size. This also sheds light on a long-standing dispute on the effective achievability of linear sum rate scaling with HC. Finally, we notice that the achievable sum rate for large $α$ is much larger than for small $α$. This suggests that HC scheme may be a very effective approach for networks operating at mm-waves.
Rendezvous in Networks in Spite of Delay Faults
Venue: arXiv cs.DS 2015
Year: 2015

Two mobile agents, starting from different nodes of an unknown network, have to meet at the same node. Agents move in synchronous rounds using a deterministic algorithm. Each agent has a different label, which it can use in the execution of the algorithm, but it does not know the label of the other agent. Agents do not know any bound on the size of the network. In each round an agent decides if it remains idle or if it wants to move to one of the adjacent nodes. Agents are subject to delay faults: if an agent incurs a fault in a given round, it remains in the current node, regardless of its decision. If it planned to move and the fault happened, the agent is aware of it. We consider three scenarios of fault distribution: random (independently in each round and for each agent with constant probability 0 < p < 1), unbounded adver- sarial (the adversary can delay an agent for an arbitrary finite number of consecutive rounds) and bounded adversarial (the adversary can delay an agent for at most c consecutive rounds, where c is unknown to the agents). The quality measure of a rendezvous algorithm is its cost, which is the total number of edge traversals. For random faults, we show an algorithm with cost polynomial in the size n of the network and polylogarithmic in the larger label L, which achieves rendezvous with very high probability in arbitrary networks. By contrast, for unbounded adversarial faults we show that rendezvous is not feasible, even in the class of rings. Under this scenario we give a rendezvous algorithm with cost O(nl), where l is the smaller label, working in arbitrary trees, and we show that Ω(l) is the lower bound on rendezvous cost, even for the two-node tree. For bounded adversarial faults, we give a rendezvous algorithm working for arbitrary networks, with cost polynomial in n, and logarithmic in the bound c and in the larger label L.
Information-Geometric Equivalence of Transportation Polytopes
Venue: arXiv cs.IT 2015
Year: 2015

This paper deals with transportation polytopes in the probability simplex (that is, sets of categorical bivariate probability distributions with prescribed marginals). Information projections between such polytopes are studied, and a sufficient condition is described under which these mappings are homeomorphisms.
Polynomial Time Attack on Wild McEliece Over Quadratic Extensions
Venue: arXiv cs.CR 2015
Year: 2015

We present a polynomial time structural attack against the McEliece system based on Wild Goppa codes from a quadratic finite field extension. This attack uses the fact that such codes can be distinguished from random codes to compute some filtration, that is to say a family of nested subcodes which will reveal their secret algebraic description.
On algorithmic equivalence of instruction sequences for computing bit string functions
Venue: arXiv cs.LO 2015
Year: 2015

Every partial function from bit strings of a given length to bit strings of a possibly different given length can be computed by a finite instruction sequence that contains only instructions to set and get the content of Boolean registers, forward jump instructions, and a termination instruction. We look for an equivalence relation on instruction sequences of this kind that captures to a reasonable degree the intuitive notion that two instruction sequences express the same algorithm.
How to Scale Exponential Backoff
Venue: arXiv cs.DC 2015
Year: 2015

Randomized exponential backoff is a widely deployed technique for coordinating access to a shared resource. A good backoff protocol should, arguably, satisfy three natural properties: (i) it should provide constant throughput, wasting as little time as possible; (ii) it should require few failed access attempts, minimizing the amount of wasted effort; and (iii) it should be robust, continuing to work efficiently even if some of the access attempts fail for spurious reasons. Unfortunately, exponential backoff has some well-known limitations in two of these areas: it provides poor (sub-constant) throughput (in the worst case), and is not robust (to resource acquisition failures). The goal of this paper is to "fix" exponential backoff by making it scalable, particularly focusing on the case where processes arrive in an on-line, worst-case fashion. We present a relatively simple backoff protocol~Re-Backoff~that has, at its heart, a version of exponential backoff. It guarantees expected constant throughput with dynamic process arrivals and requires only an expected polylogarithmic number of access attempts per process. Re-Backoff is also robust to periods where the shared resource is unavailable for a period of time. If it is unavailable for $D$ time slots, Re-Backoff provides the following guarantees. When the number of packets is a finite $n$, the average expected number of access attempts for successfully sending a packet is $O(\log^2( n + D))$. In the infinite case, the average expected number of access attempts for successfully sending a packet is $O( \log^2(η) + \log^2(D) )$ where $η$ is the maximum number of processes that are ever in the system concurrently.
Lazy Model Expansion: Interleaving Grounding with Search
Venue: arXiv cs.LO 2015
Year: 2015

Finding satisfying assignments for the variables involved in a set of constraints can be cast as a (bounded) model generation problem: search for (bounded) models of a theory in some logic. The state-of-the-art approach for bounded model generation for rich knowledge representation languages, like ASP, FO(.) and Zinc, is ground-and-solve: reduce the theory to a ground or propositional one and apply a search algorithm to the resulting theory. An important bottleneck is the blowup of the size of the theory caused by the reduction phase. Lazily grounding the theory during search is a way to overcome this bottleneck. We present a theoretical framework and an implementation in the context of the FO(.) knowledge representation language. Instead of grounding all parts of a theory, justifications are derived for some parts of it. Given a partial assignment for the grounded part of the theory and valid justifications for the formulas of the non-grounded part, the justifications provide a recipe to construct a complete assignment that satisfies the non-grounded part. When a justification for a particular formula becomes invalid during search, a new one is derived; if that fails, the formula is split in a part to be grounded and a part that can be justified. The theoretical framework captures existing approaches for tackling the grounding bottleneck such as lazy clause generation and grounding-on-the-fly, and presents a generalization of the 2-watched literal scheme. We present an algorithm for lazy model expansion and integrate it in a model generator for FO(ID), a language extending first-order logic with inductive definitions. The algorithm is implemented as part of the state-of-the-art FO(ID) Knowledge-Base System IDP. Experimental results illustrate the power and generality of the approach.
A Stochastic Geometry Analysis of Inter-cell Interference Coordination and Intra-cell Diversity
Venue: arXiv cs.IT 2015
Year: 2015

Inter-cell interference coordination (ICIC) and intra-cell diversity (ICD) play important roles in improving cellular downlink coverage. Modeling cellular base stations (BSs) as a homogeneous Poisson point process (PPP), this paper provides explicit finite-integral expressions for the coverage probability with ICIC and ICD, taking into account the temporal/spectral correlation of the signal and interference. In addition, we show that in the high-reliability regime, where the user outage probability goes to zero, ICIC and ICD affect the network coverage in drastically different ways: ICD can provide order gain while ICIC only offers linear gain. In the high-spectral efficiency regime where the SIR threshold goes to infinity, the order difference in the coverage probability does not exist, however the linear difference makes ICIC a better scheme than ICD for realistic path loss exponents. Consequently, depending on the SIR requirements, different combinations of ICIC and ICD optimize the coverage probability.
AC-KBO Revisited
Venue: arXiv cs.LO 2015
Year: 2015

Equational theories that contain axioms expressing associativity and commutativity (AC) of certain operators are ubiquitous. Theorem proving methods in such theories rely on well-founded orders that are compatible with the AC axioms. In this paper we consider various definitions of AC-compatible Knuth-Bendix orders. The orders of Steinbach and of Korovin and Voronkov are revisited. The former is enhanced to a more powerful version, and we modify the latter to amend its lack of monotonicity on non-ground terms. We further present new complexity results. An extension reflecting the recent proposal of subterm coefficients in standard Knuth-Bendix orders is also given. The various orders are compared on problems in termination and completion.