OpenRaiser/Intern-Atlas huggingface dataset:
Novel Polynomial Basis and Its Application to Reed-Solomon Erasure Codes
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we present a new basis of polynomial over finite fields of characteristic two and then apply it to the encoding/decoding of Reed-Solomon erasure codes. The proposed polynomial basis allows that $h$-point polynomial evaluation can be computed in $O(h\log_2(h))$ finite field operations with small leading constant. As compared with the canonical polynomial basis, the proposed basis improves the arithmetic complexity of addition, multiplication, and the determination of polynomial degree from $O(h\log_2(h)\log_2\log_2(h))$ to $O(h\log_2(h))$. Based on this basis, we then develop the encoding and erasure decoding algorithms for the $(n=2^r,k)$ Reed-Solomon codes. Thanks to the efficiency of transform based on the polynomial basis, the encoding can be completed in $O(n\log_2(k))$ finite field operations, and the erasure decoding in $O(n\log_2(n))$ finite field operations. To the best of our knowledge, this is the first approach supporting Reed-Solomon erasure codes over characteristic-2 finite fields while achieving a complexity of $O(n\log_2(n))$, in both additive and multiplicative complexities. As the complexity leading factor is small, the algorithms are advantageous in practical applications.
The ZX-calculus is incomplete for quantum mechanics
Venue: arXiv cs.LO 2014
Year: 2014

We prove that the ZX-calculus is incomplete for quantum mechanics. We suggest the addition of a new 'color-swap' rule, of which currently no analytical formulation is known and which we suspect may be necessary, but not sufficient to make the ZX-calculus complete.
BRICS countries and scientific excellence: A bibliometric analysis of most frequently-cited papers
Venue: arXiv cs.DL 2014
Year: 2014

The BRICS countries (Brazil, Russia, India, and China, and South Africa) are noted for their increasing participation in science and technology. The governments of these countries have been boosting their investments in research and development to become part of the group of nations doing research at a world-class level. This study investigates the development of the BRICS countries in the domain of top-cited papers (top 10% and 1% most frequently cited papers) between 1990 and 2010. To assess the extent to which these countries have become important players on the top level, we compare the BRICS countries with the top-performing countries worldwide. As the analyses of the (annual) growth rates show, with the exception of Russia, the BRICS countries have increased their output in terms of most frequently-cited papers at a higher rate than the top-cited countries worldwide. In a further step of analysis for this study, we generate co-authorship networks among authors of highly cited papers for four time points to view changes in BRICS participation (1995, 2000, 2005, and 2010). Here, the results show that all BRICS countries succeeded in becoming part of this network, whereby the Chinese collaboration activities focus on the USA.
Towards Understanding Cyberbullying Behavior in a Semi-Anonymous Social Network
Venue: arXiv cs.SI 2014
Year: 2014

Cyberbullying has emerged as an important and growing social problem, wherein people use online social networks and mobile phones to bully victims with offensive text, images, audio and video on a 247 basis. This paper studies negative user behavior in the Ask.fm social network, a popular new site that has led to many cases of cyberbullying, some leading to suicidal behavior.We examine the occurrence of negative words in Ask.fms question+answer profiles along with the social network of likes of questions+answers. We also examine properties of users with cutting behavior in this social network.
Virtual Reflexes
Venue: arXiv cs.CY 2014
Year: 2014

Virtual Reality is used successfully to treat people for regular phobias. A new challenge is to develop Virtual Reality Exposure Training for social skills. Virtual actors in such systems have to show appropriate social behavior including emotions, gaze, and keeping distance. The behavior must be realistic and real-time. Current approaches consist of four steps: 1) trainee social signal detection, 2) cognitive-affective interpretation, 3) determination of the appropriate bodily responses, and 4) actuation. The "cognitive" detour of such approaches does not match the directness of human bodily reflexes and causes unrealistic responses and delay. Instead, we propose virtual reflexes as concurrent sensory-motor processes to control virtual actors. Here we present a virtual reflexes architecture, explain how emotion and cognitive modulation are embedded, detail its workings, and give an example description of an aggression training application.
Complexity of Grammar Induction for Quantum Types
Venue: arXiv cs.CL 2014
Year: 2014

Most categorical models of meaning use a functor from the syntactic category to the semantic category. When semantic information is available, the problem of grammar induction can therefore be defined as finding preimages of the semantic types under this forgetful functor, lifting the information flow from the semantic level to a valid reduction at the syntactic level. We study the complexity of grammar induction, and show that for a variety of type systems, including pivotal and compact closed categories, the grammar induction problem is NP-complete. Our approach could be extended to linguistic type systems such as autonomous or bi-closed categories.
Colorful bin packing
Venue: arXiv cs.DS 2014
Year: 2014

We study a variant of online bin packing, called colorful bin packing. In this problem, items that are presented one by one are to be packed into bins of size 1. Each item i has a size s_i \in [0,1] and a color c_i \in C, where C is a set of colors (that is not necessarily known in advance). The total size of items packed into a bin cannot exceed its size, thus an item i can always be packed into a new bin, but an item cannot be packed into a non-empty bin if the previous item packed into that bin has the same color, or if the occupied space in it is larger than 1-s_i. This problem generalizes standard online bin packing and online black and white bin packing (where |C|=2). We prove that colorful bin packing is harder than black and white bin packing in the sense that an online algorithm for zero size items that packs the input into the smallest possible number of bins cannot exist for C \geq 3, while it is known that such an algorithm exists for |C|=2. We show that natural generalizations of classic algorithms for bin packing fail to work for the case |C| \geq 3 and moreover, algorithms that perform well for black and white bin packing do not perform well either, already for the case |C|=3. Our main results are a new algorithm for colorful bin packing that we design and analyze, whose absolute competitive ratio is 4, and a new lower bound of 2 on the asymptotic competitive ratio of any algorithm, that is valid even for black and white bin packing.
Discovering and Exploiting Entailment Relationships in Multi-Label Learning
Venue: arXiv cs.LG 2014
Year: 2014

This work presents a sound probabilistic method for enforcing adherence of the marginal probabilities of a multi-label model to automatically discovered deterministic relationships among labels. In particular we focus on discovering two kinds of relationships among the labels. The first one concerns pairwise positive entailement: pairs of labels, where the presence of one implies the presence of the other in all instances of a dataset. The second concerns exclusion: sets of labels that do not coexist in the same instances of the dataset. These relationships are represented with a Bayesian network. Marginal probabilities are entered as soft evidence in the network and adjusted through probabilistic inference. Our approach offers robust improvements in mean average precision compared to the standard binary relavance approach across all 12 datasets involved in our experiments. The discovery process helps interesting implicit knowledge to emerge, which could be useful in itself.
Locating Crashing Faults based on Crash Stack Traces
Venue: arXiv cs.SE 2014
Year: 2014

Software crashes due to its increasing complexity. Once a crash happens, a crash report could be sent to software developers for investigation upon user permission. Because of the large number of crash reports and limited information, debugging for crashes is often a tedious and labor-intensive task. In this paper, we propose a statistical fault localization framework to help developers locate functions that contain crashing faults. We generate the execution traces for the failing traces based on the crash stack, and the passing traces from normal executions. We form program spectra by combining generated passing and failing trace, and then apply statistical fault localization techniques such as Ochiai to locate the crashing faults. We also propose two heuristics to improve the fault localization performance. We evaluate our approach using the real-world Firefox crash report data. The results show that the performance of our method is promising. Our approach permits developers to locate 63.9% crashing faults by examining only 5% Firefox 3.6 functions in the spectra.
Structured Stochastic Variational Inference
Venue: arXiv cs.LG 2014
Year: 2014

Stochastic variational inference makes it possible to approximate posterior distributions induced by large datasets quickly using stochastic optimization. The algorithm relies on the use of fully factorized variational distributions. However, this "mean-field" independence approximation limits the fidelity of the posterior approximation, and introduces local optima. We show how to relax the mean-field approximation to allow arbitrary dependencies between global parameters and local hidden variables, producing better parameter estimates by reducing bias, sensitivity to local optima, and sensitivity to hyperparameters.
A Deterministic TCP Bandwidth Sharing Model
Venue: arXiv cs.NI 2014
Year: 2014

Traditionally TCP bandwidth sharing has been investigated mainly by stochastic approaches due to its seemingly chaotic nature. Even though of great generality, the theories deal mainly with expectation values, which is prone to misinterpretation with respect to the Quality-of-Experience (QoE). We disassemble TCP operating conditions into dominating scenarios and show that bandwidth sharing alone follows mostly deterministic rules. From the analysis we derive significant root causes of well-known TCP aspects like unequal sharing, burstiness of losses, global synchronization, and on buffer sizing. We base our model on a detailed analysis of bandwidth sharing experiments with subsequent mathematical reproduction.
Prediction of Transformed (DCT) Video Coding Residual for Video Compression
Venue: arXiv cs.IT 2014
Year: 2014

Video compression has been investigated by means of analysis-synthesis, and more particularly by means of inpainting. The first part of our approach has been to develop the inpainting of DCT coefficients in an image. This has shown good results for image compression without overpassing todays compression standards like JPEG. We then looked at integrating the same approach in a video coder, and in particular in the widely used H264 AVC standard coder, but the same approach can be used in the framework of HEVC. The originality of this work consists in cancelling at the coder, then automatically restoring, at the decoder, some well chosen DCT residual coefficients. For this purpose, we have developed a restoration model of transformed coefficients. By using a total variation based model, we derive conditions for the reconstruction of transformed coefficients that have been suppressed or altered. The main purpose here, in a video coding context, is to improve the ratedistortion performance of existing coders. To this end DCT restoration is used as an additional prediction step to the spatial prediction of the transformed coefficients, based on an image regularization process. The method has been successfully tested with the H.264 AVC video codec standard.
Automated Classification of Airborne Laser Scanning Point Clouds
Venue: arXiv cs.CE 2014
Year: 2014

Making sense of the physical world has always been at the core of mapping. Up until recently, this has always dependent on using the human eye. Using airborne lasers, it has become possible to quickly "see" more of the world in many more dimensions. The resulting enormous point clouds serve as data sources for applications far beyond the original mapping purposes ranging from flooding protection and forestry to threat mitigation. In order to process these large quantities of data, novel methods are required. In this contribution, we develop models to automatically classify ground cover and soil types. Using the logic of machine learning, we critically review the advantages of supervised and unsupervised methods. Focusing on decision trees, we improve accuracy by including beam vector components and using a genetic algorithm. We find that our approach delivers consistently high quality classifications, surpassing classical methods.
An Empirical Comparison of Parsing Methods for Stanford Dependencies
Venue: arXiv cs.CL 2014
Year: 2014

Stanford typed dependencies are a widely desired representation of natural language sentences, but parsing is one of the major computational bottlenecks in text analysis systems. In light of the evolving definition of the Stanford dependencies and developments in statistical dependency parsing algorithms, this paper revisits the question of Cer et al. (2010): what is the tradeoff between accuracy and speed in obtaining Stanford dependencies in particular? We also explore the effects of input representations on this tradeoff: part-of-speech tags, the novel use of an alternative dependency representation as input, and distributional representaions of words. We find that direct dependency parsing is a more viable solution than it was found to be in the past. An accompanying software release can be found at: http://www.ark.cs.cmu.edu/TBSD
Stable Graphical Models
Venue: arXiv cs.LG 2014
Year: 2014

Stable random variables are motivated by the central limit theorem for densities with (potentially) unbounded variance and can be thought of as natural generalizations of the Gaussian distribution to skewed and heavy-tailed phenomenon. In this paper, we introduce stable graphical (SG) models, a class of multivariate stable densities that can also be represented as Bayesian networks whose edges encode linear dependencies between random variables. One major hurdle to the extensive use of stable distributions is the lack of a closed-form analytical expression for their densities. This makes penalized maximum-likelihood based learning computationally demanding. We establish theoretically that the Bayesian information criterion (BIC) can asymptotically be reduced to the computationally more tractable minimum dispersion criterion (MDC) and develop StabLe, a structure learning algorithm based on MDC. We use simulated datasets for five benchmark network topologies to empirically demonstrate how StabLe improves upon ordinary least squares (OLS) regression. We also apply StabLe to microarray gene expression data for lymphoblastoid cells from 727 individuals belonging to eight global population groups. We establish that StabLe improves test set performance relative to OLS via ten-fold cross-validation. Finally, we develop SGEX, a method for quantifying differential expression of genes between different population groups.
Overloaded Satellite Receiver Using SIC with Hybrid Beamforming and ML Detection
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, a new receiver structure that is intended to detect the signals from multiple adjacent satellites in the presence of other interfering satellites is proposed. We tackle the worst case interference conditions, i.e., it is assumed that uncoded signals that fully overlap in frequency arrive at a multiple-element small-size parabolic antenna in a spatially correlated noise environment. The proposed successive interference cancellation (SIC) receiver, denoted by SIC Hy/ML, employs hybrid beamforming and disjoint maximum likelihood (ML) detection. Depending on the individual signals spatial position, the proposed SIC Hy/ML scheme takes advantage of two types of beamformers: a maximum ratio combining (MRC) beamformer and a compromised array response (CAR) beamformer. The performance of the proposed receiver is compared to an SIC receiver that uses only MRC beamforming scheme with ML detection for all signals, a joint ML detector, and a minimum mean square error detector. It is found that SIC Hy/ML outperforms the other schemes by a large margin.
A Complete Solver for Constraint Games
Venue: arXiv cs.GT 2014
Year: 2014

Game Theory studies situations in which multiple agents having conflicting objectives have to reach a collective decision. The question of a compact representation language for agents utility function is of crucial importance since the classical representation of a $n$-players game is given by a $n$-dimensional matrix of exponential size for each player. In this paper we use the framework of Constraint Games in which CSP are used to represent utilities. Constraint Programming --including global constraints-- allows to easily give a compact and elegant model to many useful games. Constraint Games come in two flavors: Constraint Satisfaction Games and Constraint Optimization Games, the first one using satisfaction to define boolean utilities. In addition to multimatrix games, it is also possible to model more complex games where hard constraints forbid certain situations. In this paper we study complete search techniques and show that our solver using the compact representation of Constraint Games is faster than the classical game solver Gambit by one to two orders of magnitude.
An All-Around Near-Optimal Solution for the Classic Bin Packing Problem
Venue: arXiv cs.DS 2014
Year: 2014

In this paper we present the first algorithm with optimal average-case and close-to-best known worst-case performance for the classic on-line problem of bin packing. It has long been observed that known bin packing algorithms with optimal average-case performance were not optimal in the worst-case sense. In particular First Fit and Best Fit had optimal average-case ratio of 1 but a worst-case competitive ratio of 1.7. The wasted space of First Fit and Best Fit for a uniform random sequence of length $n$ is expected to be $Θ(n^{2/3})$ and $Θ(\sqrt{n} \log ^{3/4} n)$, respectively. The competitive ratio can be improved to 1.691 using the Harmonic algorithm; further variations of this algorithm can push down the competitive ratio to 1.588. However, Harmonic and its variations have poor performance on average; in particular, Harmonic has average-case ratio of around 1.27. In this paper, first we introduce a simple algorithm which we term Harmonic Match. This algorithm performs as well as Best Fit on average, i.e., it has an average-case ratio of 1 and expected wasted space of $Θ(\sqrt{n} \log ^{3/4} n)$. Moreover, the competitive ratio of the algorithm is as good as Harmonic, i.e., it converges to $ 1.691$ which is an improvement over 1.7 of Best Fit and First Fit. We also introduce a different algorithm, termed as Refined Harmonic Match, which achieves an improved competitive ratio of $1.636$ while maintaining the good average-case performance of Harmonic Match and Best Fit. Finally, our extensive experimental evaluation of the studied bin packing algorithms shows that our proposed algorithms have comparable average-case performance with Best Fit and First Fit, and this holds also for sequences that follow distributions other than the uniform distribution.
A Novel Approach for Video Temporal Annotation
Venue: arXiv cs.MM 2014
Year: 2014

Recent advances in computing, communication, and data storage have led to an increasing number of large digital libraries publicly available on the Internet. Main problem of content-based video retrieval is inferring semantics from raw video data. Video data play an important role in these libraries. Instead of words, a video retrieval system deals with collections of video records. Therefore, the system is confronted with the problem of video understanding. Because machine understanding of the video data is still an unsolved research problem, text annotations are usually used to describe the content of video data according to the annotator's understanding and the purpose of that video data. Most of proposed systems for video annotation are domain dependent. In addition, in many of these systems, an important feature of video data, temporality, is disregarded. In this paper, we proposed a framework for video temporal annotation. The proposed system uses domain knowledge and a time ontology to perform temporal annotation of input video.
Consistent Subset Sampling
Venue: arXiv cs.DS 2014
Year: 2014

Consistent sampling is a technique for specifying, in small space, a subset $S$ of a potentially large universe $U$ such that the elements in $S$ satisfy a suitably chosen sampling condition. Given a subset $\mathcal{I}\subseteq U$ it should be possible to quickly compute $\mathcal{I}\cap S$, i.e., the elements in $\mathcal{I}$ satisfying the sampling condition. Consistent sampling has important applications in similarity estimation, and estimation of the number of distinct items in a data stream. In this paper we generalize consistent sampling to the setting where we are interested in sampling size-$k$ subsets occurring in some set in a collection of sets of bounded size $b$, where $k$ is a small integer. This can be done by applying standard consistent sampling to the $k$-subsets of each set, but that approach requires time $Θ(b^k)$. Using a carefully designed hash function, for a given sampling probability $p \in (0,1]$, we show how to improve the time complexity to $Θ(b^{\lceil k/2\rceil}\log \log b + pb^k)$ in expectation, while maintaining strong concentration bounds for the sample. The space usage of our method is $Θ(b^{\lceil k/4\rceil})$. We demonstrate the utility of our technique by applying it to several well-studied data mining problems. We show how to efficiently estimate the number of frequent $k$-itemsets in a stream of transactions and the number of bipartite cliques in a graph given as incidence stream. Further, building upon a recent work by Campagna et al., we show that our approach can be applied to frequent itemset mining in a parallel or distributed setting. We also present applications in graph stream mining.
On the relation between graph distance and Euclidean distance in random geometric graphs
Venue: arXiv cs.DM 2014
Year: 2014

Given any two vertices u, v of a random geometric graph, denote by d_E(u,v) their Euclidean distance and by d_G(u,v) their graph distance. The problem of finding upper bounds on d_G(u,v) in terms of d_E(u,v) has received a lot of attention in the literature. In this paper, we improve these upper bounds for values of r=omega(sqrt(log n)) (i.e. for r above the connectivity threshold). Our result also improves the best-known estimates on the diameter of random geometric graphs. We also provide a lower bound on d_G(u,v) in terms of d_E(u,v).