OpenRaiser/Intern-Atlas huggingface dataset:
Statistical Analysis of a Posteriori Channel and Noise Distribution Based on HARQ Feedback
Venue: arXiv cs.IT 2016
Year: 2016

In response to a comment on one of our manuscript, this work studies the posterior channel and noise distributions conditioned on the NACKs and ACKs of all previous transmissions in HARQ system with statistical approaches. Our main result is that, unless the coherence interval (time or frequency) is large as in block-fading assumption, the posterior distribution of the channel and noise either remains almost identical to the prior distribution, or it mostly follows the same class of distribution as the prior one. In the latter case, the difference between the posterior and prior distribution can be modeled as some parameter mismatch, which has little impact on certain type of applications.
On improvements of the $r$-adding walk in a finite field of characteristic 2
Venue: arXiv cs.CR 2016
Year: 2016

It is currently known from the work of Shoup and Nechaev that a generic algorithm to solve the discrete logarithm problem in a group of prime order must have complexity at least $k\sqrt{N}$ where $N$ is the order of the group. In many collision search algorithms this complexity is achieved. So with generic algorithms one can only hope to make the $k$ smaller. This $k$ depends on the complexity of the iterative step in the generic algorithms. The $\sqrt{N}$ comes from the fact there is about $\sqrt{N}$ iterations before a collision. So if we can find ways that can reduce the amount of work in one iteration then that is of great interest and probably the only possible modification of a generic algorithm. The modified $r$-adding walk allegedly does just that. It claims to reduce the amount of work done in one iteration of the original $r$-adding walk. In this paper we study this modified $r$-adding walk, we critically analyze it and we compare it with the original $r$-adding walk.
Robust State Estimation against Sparse Integrity Attacks
Venue: arXiv cs.IT 2016
Year: 2016

We consider the problem of robust state estimation in the presence of integrity attacks. There are $m$ sensors monitoring a dynamical process. Subject to the integrity attacks, $p$ out of $m$ measurements can be arbitrarily manipulated. The classical approach such as the MMSE estimation in the literature may not provide a reliable estimate under this so-called $(p,m)$-sparse attack. In this work, we propose a robust estimation framework where distributed local measurements are computed first and fused at the estimator based on a convex optimization problem. We show the sufficient and necessary conditions for robustness of the proposed estimator. The sufficient and necessary conditions are shown to be tight, with a trivial gap. We also present an upper bound on the damage an attacker can cause when the sufficient condition is satisfied. Simulation results are also given to illustrate the effectiveness of the estimator.
Sublinear-Time Algorithms for Counting Star Subgraphs with Applications to Join Selectivity Estimation
Venue: arXiv cs.DS 2016
Year: 2016

We study the problem of estimating the value of sums of the form $S_p \triangleq \sum \binom{x_i}{p}$ when one has the ability to sample $x_i \geq 0$ with probability proportional to its magnitude. When $p=2$, this problem is equivalent to estimating the selectivity of a self-join query in database systems when one can sample rows randomly. We also study the special case when $\{x_i\}$ is the degree sequence of a graph, which corresponds to counting the number of $p$-stars in a graph when one has the ability to sample edges randomly. Our algorithm for a $(1 \pm \varepsilon)$-multiplicative approximation of $S_p$ has query and time complexities $Ø(\frac{m \log \log n}{ε^2 S_p^{1/p}})$. Here, $m=\sum x_i/2$ is the number of edges in the graph, or equivalently, half the number of records in the database table. Similarly, $n$ is the number of vertices in the graph and the number of unique values in the database table. We also provide tight lower bounds (up to polylogarithmic factors) in almost all cases, even when $\{x_i\}$ is a degree sequence and one is allowed to use the structure of the graph to try to get a better estimate. We are not aware of any prior lower bounds on the problem of join selectivity estimation. For the graph problem, prior work which assumed the ability to sample only \emph{vertices} uniformly gave algorithms with matching lower bounds [Gonen, Ron, and Shavitt. \textit{SIAM J. Comput.}, 25 (2011), pp. 1365-1411]. With the ability to sample edges randomly, we show that one can achieve faster algorithms for approximating the number of star subgraphs, bypassing the lower bounds in this prior work. For example, in the regime where $S_p\leq n$, and $p=2$, our upper bound is $\tilde{O}(n/S_p^{1/2})$, in contrast to their $Ω(n/S_p^{1/3})$ lower bound when no random edge queries are available.
On-line Bayesian System Identification
Venue: arXiv cs.SY 2016
Year: 2016

We consider an on-line system identification setting, in which new data become available at given time steps. In order to meet real-time estimation requirements, we propose a tailored Bayesian system identification procedure, in which the hyper-parameters are still updated through Marginal Likelihood maximization, but after only one iteration of a suitable iterative optimization algorithm. Both gradient methods and the EM algorithm are considered for the Marginal Likelihood optimization. We compare this "1-step" procedure with the standard one, in which the optimization method is run until convergence to a local minimum. The experiments we perform confirm the effectiveness of the approach we propose.
Exact Random Coding Secrecy Exponents for the Wiretap Channel
Venue: arXiv cs.IT 2016
Year: 2016

We analyze the exact exponential decay rate of the expected amount of information leaked to the wiretapper in Wyner's wiretap channel setting using wiretap channel codes constructed from both i.i.d. and constant-composition random codes. Our analysis for those sampled from i.i.d. random coding ensemble shows that the previously-known achievable secrecy exponent using this ensemble is indeed the exact exponent for an average code in the ensemble. Furthermore, our analysis on wiretap channel codes constructed from the ensemble of constant-composition random codes leads to an exponent which, in addition to being the exact exponent for an average code, is larger than the achievable secrecy exponent that has been established so far in the literature for this ensemble (which in turn was known to be smaller than that achievable by wiretap channel codes sampled from i.i.d. random coding ensemble). We show examples where the exact secrecy exponent for the wiretap channel codes constructed from random constant-composition codes is larger than that of those constructed from i.i.d. random codes and examples where the exact secrecy exponent for the wiretap channel codes constructed from i.i.d. random codes is larger than that of those constructed from constant-composition random codes. We, hence, conclude that, unlike the error correction problem, there is no general ordering between the two random coding ensembles in terms of their secrecy exponent.
How Good is Bargained Routing?
Venue: arXiv cs.NI 2016
Year: 2016

In the context of networking, research has focused on non-cooperative games, where the selfish agents cannot reach a binding agreement on the way they would share the infrastructure. Many approaches have been proposed for mitigating the typically inefficient operating points. However, in a growing number of networking scenarios selfish agents are able to communicate and reach an agreement. Hence, the degradation of performance should be considered at an operating point of a cooperative game. Accordingly, our goal is to lay foundations for the application of cooperative game theory to fundamental problems in networking. We explain our choice of the Nash Bargaining Scheme (NBS) as the solution concept, and introduce the Price of Selfishness (PoS), which considers the degradation of performance at the worst NBS. We focus on the fundamental load balancing game of routing over parallel links. First, we consider agents with identical performance objectives. We show that, while the PoA here can be large, through bargaining, all agents, and the system, strictly improve their performance. Interestingly, in a two-agent system or when all agents have identical demands, we establish that they reach social optimality. We then consider agents with different performance objectives and demonstrate that the PoS and PoA can be unbounded, yet we explain why both measures are unsuitable. Accordingly, we introduce the Price of Heterogeneity (PoH), as an extension of the PoA. We establish an upper-bound on the PoH and indicate its further motivation for bargaining. Finally, we discuss network design guidelines that follow from our findings
Which tone-mapping operator is the best? A comparative study of perceptual quality
Venue: arXiv cs.GR 2016
Year: 2016

Tone-mapping operators (TMO) are designed to generate perceptually similar low-dynamic range images from high-dynamic range ones. We studied the performance of fifteen TMOs in two psychophysical experiments where observers compared the digitally generated tone-mapped images to their corresponding physical scenes. All experiments were performed in a controlled environment and the setups were designed to emphasise different image properties: in the first experiment we evaluated the local relationships among intensity-levels, and in the second one we evaluated global visual appearance among physical scenes and tone-mapped images, which were presented side by side. We ranked the TMOs according to how well they reproduce the results obtained in the physical scene. Our results show that ranking position clearly depends on the adopted evaluation criteria, which implies that, in general, these tone-mapping algorithms consider either local or global image attributes but rarely both. We conclude that a more thorough and standardized evaluation criteria are needed to study all the characteristics of TMOs, as there is ample room for improvement in future developments.
Bandit Structured Prediction for Learning from Partial Feedback in Statistical Machine Translation
Venue: arXiv cs.CL 2016
Year: 2016

We present an approach to structured prediction from bandit feedback, called Bandit Structured Prediction, where only the value of a task loss function at a single predicted point, instead of a correct structure, is observed in learning. We present an application to discriminative reranking in Statistical Machine Translation (SMT) where the learning algorithm only has access to a 1-BLEU loss evaluation of a predicted translation instead of obtaining a gold standard reference translation. In our experiment bandit feedback is obtained by evaluating BLEU on reference translations without revealing them to the algorithm. This can be thought of as a simulation of interactive machine translation where an SMT system is personalized by a user who provides single point feedback to predicted translations. Our experiments show that our approach improves translation quality and is comparable to approaches that employ more informative feedback in learning.
Content Aware Neural Style Transfer
Venue: arXiv cs.CV 2016
Year: 2016

This paper presents a content-aware style transfer algorithm for paintings and photos of similar content using pre-trained neural network, obtaining better results than the previous work. In addition, the numerical experiments show that the style pattern and the content information is not completely separated by neural network.
Nonparametric Bayesian Storyline Detection from Microtexts
Venue: arXiv cs.CL 2016
Year: 2016

News events and social media are composed of evolving storylines, which capture public attention for a limited period of time. Identifying storylines requires integrating temporal and linguistic information, and prior work takes a largely heuristic approach. We present a novel online non-parametric Bayesian framework for storyline detection, using the distance-dependent Chinese Restaurant Process (dd-CRP). To ensure efficient linear-time inference, we employ a fixed-lag Gibbs sampling procedure, which is novel for the dd-CRP. We evaluate on the TREC Twitter Timeline Generation (TTG), obtaining encouraging results: despite using a weak baseline retrieval model, the dd-CRP story clustering method is competitive with the best entries in the 2014 TTG task.
Signal Flow Graph Approach to Efficient DST I-IV Algorithms
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, fast and efficient discrete sine transformation (DST) algorithms are presented based on the factorization of sparse, scaled orthogonal, rotation, rotation-reflection, and butterfly matrices. These algorithms are completely recursive and solely based on DST I-IV. The presented algorithms have low arithmetic cost compared to the known fast DST algorithms. Furthermore, the language of signal flow graph representation of digital structures is used to describe these efficient and recursive DST algorithms having $(n-1)$ points signal flow graph for DST-I and $n$ points signal flow graphs for DST II-IV.
Approximating the $k$-Level in Three-Dimensional Plane Arrangements
Venue: arXiv cs.CG 2016
Year: 2016

$\renewcommand{\Re}{{\rm I\!\hspace{-0.025em} R}} \newcommand{\SetX}{\mathsf{X}} \newcommand{\eps}{\varepsilon} \newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}} \newcommand{\IntRange}[1]{[ #1 ]} \newcommand{\Space}{\ovebarline{\mathsf{m}}} \newcommand{\pth}[2][\!]{#1\left({#2}\right)} \newcommand{\Arr}{\cal A}$ Let $H$ be a set of $n$ planes in three dimensions, and let $r \leq n$ be a parameter. We give a simple alternative proof of the existence of a $(1/r)$-cutting of the first $n/r$ levels of $\Arr(H)$, which consists of $O(r)$ semi-unbounded vertical triangular prisms. The same construction yields an approximation of the $(n/r)$-level by a terrain consisting of $O(r/\eps^3)$ triangular faces, which lies entirely between the levels $(1\pm\eps)n/r$. The proof does not use sampling, and exploits techniques based on planar separators and various structural properties of levels in three-dimensional arrangements and of planar maps. The proof is constructive, and leads to a simple randomized algorithm, with expected near-linear running time. An application of this technique allows us to mimic Matousek's construction of cuttings in the plane, to obtain a similar construction of "layered" $(1/r)$-cutting of the entire arrangement $\Arr(H)$, of optimal size $O(r^3)$. Another application is a simplified optimal approximate range counting algorithm in three dimensions, competing with that of Afshani and Chan.
Streaming Similarity Self-Join
Venue: arXiv cs.DB 2016
Year: 2016

We introduce and study the problem of computing the similarity self-join in a streaming context (SSSJ), where the input is an unbounded stream of items arriving continuously. The goal is to find all pairs of items in the stream whose similarity is greater than a given threshold. The simplest formulation of the problem requires unbounded memory, and thus, it is intractable. To make the problem feasible, we introduce the notion of time-dependent similarity: the similarity of two items decreases with the difference in their arrival time. By leveraging the properties of this time-dependent similarity function, we design two algorithmic frameworks to solve the sssj problem. The first one, MiniBatch (MB), uses existing index-based filtering techniques for the static version of the problem, and combines them in a pipeline. The second framework, Streaming (STR), adds time filtering to the existing indexes, and integrates new time-based bounds deeply in the working of the algorithms. We also introduce a new indexing technique (L2), which is based on an existing state-of-the-art indexing technique (L2AP), but is optimized for the streaming case. Extensive experiments show that the STR algorithm, when instantiated with the L2 index, is the most scalable option across a wide array of datasets and parameters.
Scalability in Neural Control of Musculoskeletal Robots
Venue: arXiv cs.RO 2016
Year: 2016

Anthropomimetic robots are robots that sense, behave, interact and feel like humans. By this definition, anthropomimetic robots require human-like physical hardware and actuation, but also brain-like control and sensing. The most self-evident realization to meet those requirements would be a human-like musculoskeletal robot with a brain-like neural controller. While both musculoskeletal robotic hardware and neural control software have existed for decades, a scalable approach that could be used to build and control an anthropomimetic human-scale robot has not been demonstrated yet. Combining Myorobotics, a framework for musculoskeletal robot development, with SpiNNaker, a neuromorphic computing platform, we present the proof-of-principle of a system that can scale to dozens of neurally-controlled, physically compliant joints. At its core, it implements a closed-loop cerebellar model which provides real-time low-level neural control at minimal power consumption and maximal extensibility: higher-order (e.g., cortical) neural networks and neuromorphic sensors like silicon-retinae or -cochleae can naturally be incorporated.
Tight Bounds for Consensus Systems Convergence
Venue: arXiv cs.DM 2016
Year: 2016

We analyze the asymptotic convergence of all infinite products of matrices taken in a given finite set, by looking only at finite or periodic products. It is known that when the matrices of the set have a common nonincreasing polyhedral norm, all infinite products converge to zero if and only if all infinite periodic products with period smaller than a certain value converge to zero, and bounds exist on that value. We provide a stronger bound holding for both polyhedral norms and polyhedral seminorms. In the latter case, the matrix products do not necessarily converge to 0, but all trajectories of the associated system converge to a common invariant space. We prove our bound to be tight, in the sense that for any polyhedral seminorm, there is a set of matrices such that not all infinite products converge, but every periodic product with period smaller than our bound does converge. Our technique is based on an analysis of the combinatorial structure of the face lattice of the unit ball of the nonincreasing seminorm. The bound we obtain is equal to half the size of the largest antichain in this lattice. Explicitly evaluating this quantity may be challenging in some cases. We therefore link our problem with the Sperner property: the property that, for some graded posets, -- in this case the face lattice of the unit ball -- the size of the largest antichain is equal to the size of the largest rank level. We show that some sets of matrices with invariant polyhedral seminorms lead to posets that do not have that Sperner property. However, this property holds for the polyhedron obtained when treating sets of stochastic matrices, and our bound can then be easily evaluated in that case. In particular, we show that for the dimension of the space $n \geq 8$, our bound is smaller than the previously known bound by a multiplicative factor of $\frac{3}{2 \sqrt{πn}}$.
Integrity Constraints for General-Purpose Knowledge Bases
Venue: arXiv cs.DB 2016
Year: 2016

Integrity constraints in databases have been studied extensively since the 1980s, and they are considered essential to guarantee database integrity. In recent years, several authors have studied how the same notion can be adapted to reasoning frameworks, in such a way that they achieve the purpose of guaranteeing a system's consistency, but are kept separate from the reasoning mechanisms. In this paper we focus on multi-context systems, a general-purpose framework for combining heterogeneous reasoning systems, enhancing them with a notion of integrity constraints that generalizes the corresponding concept in the database world.
Adapting the Hypercube Model to Archive Deferred Representations and Their Descendants
Venue: arXiv cs.DL 2016
Year: 2016

The web is today's primary publication medium, making web archiving an important activity for historical and analytical purposes. Web pages are increasingly interactive, resulting in pages that are increasingly difficult to archive. Client-side technologies (e.g., JavaScript) enable interactions that can potentially change the client-side state of a representation. We refer to representations that load embedded resources via JavaScript as deferred representations. It is difficult to archive all of the resources in deferred representations and the result is archives with web pages that are either incomplete or that erroneously load embedded resources from the live web. We propose a method of discovering and crawling deferred representations and their descendants (representation states that are only reachable through client-side events). We adapt the Dincturk et al. Hypercube model to construct a model for archiving descendants, and we measure the number of descendants and requisite embedded resources discovered in a proof-of-concept crawl. Our approach identified an average of 38.5 descendants per seed URI crawled, 70.9% of which are reached through an onclick event. This approach also added 15.6 times more embedded resources than Heritrix to the crawl frontier, but at a rate that was 38.9 times slower than simply using Heritrix. We show that our dataset has two levels of descendants. We conclude with proposed crawl policies and an analysis of the storage requirements for archiving descendants.
Tracing Digital Footprints to Academic Articles: An Investigation of PeerJ Publication Referral Data
Venue: arXiv cs.DL 2016
Year: 2016

In this study, we propose a novel way to explore the patterns of people's visits to academic articles. About 3.4 million links to referral source of visitors of 1432 papers published in the journal of PeerJ are collected and analyzed. We find that at least 57% visits are from external referral sources, among which General Search Engine, Social Network, and News & Blog are the top three categories of referrals. Academic Resource, including academic search engines and academic publishers' sites, is the fourth largest category of referral sources. In addition, our results show that Google contributes significantly the most in directing people to scholarly articles. This encompasses the usage of Google the search engine, Google Scholar the academic search engine, and diverse specific country domains of them. Focusing on similar disciplines to PeerJ's publication scope, NCBI is the academic search engine on which people are the most frequently directed to PeerJ. Correlation analysis and regression analysis indicates that papers with more mentions are expected to have more visitors, and Facebook, Twitter and Reddit are the most commonly used social networking tools that refer people to PeerJ.