OpenRaiser/Intern-Atlas huggingface dataset:
Church-Rosser Systems, Codes with Bounded Synchronization Delay and Local Rees Extensions
Venue: arXiv cs.FL 2017
Year: 2017

What is the common link, if there is any, between Church-Rosser systems, prefix codes with bounded synchronization delay, and local Rees extensions? The first obvious answer is that each of these notions relates to topics of interest for WORDS: Church-Rosser systems are certain rewriting systems over words, codes are given by sets of words which form a basis of a free submonoid in the free monoid of all words (over a given alphabet) and local Rees extensions provide structural insight into regular languages over words. So, it seems to be a legitimate title for an extended abstract presented at the conference WORDS 2017. However, this work is more ambitious, it outlines some less obvious but much more interesting link between these topics. This link is based on a structure theory of finite monoids with varieties of groups and the concept of local divisors playing a prominent role. Parts of this work appeared in a similar form in conference proceedings where proofs and further material can be found.
Networks of Collaborations: Hypergraph Modeling and Visualisation
Venue: arXiv cs.SI 2017
Year: 2017

The acknowledged model for networks of collaborations is the hypergraph model. Nonetheless when it comes to be visualized hypergraphs are transformed into simple graphs. Very often, the transformation is made by clique expansion of the hyperedges resulting in a loss of information for the user and in artificially more complex graphs due to the high number of edges represented. The extra-node representation gives substantial improvement in the visualisation of hypergraphs and in the retrieval of information. This paper aims at showing qualitatively and quantitatively how the extra-node representation can improve the visualisation of hypergraphs without loss of information.
Image Companding and Inverse Halftoning using Deep Convolutional Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we introduce deep learning technology to tackle two traditional low-level image processing problems, companding and inverse halftoning. We make two main contributions. First, to the best knowledge of the authors, this is the first work that has successfully developed deep learning based solutions to these two traditional low-level image processing problems. This not only introduces new methods to tackle well-known image processing problems but also demonstrates the power of deep learning in solving traditional signal processing problems. Second, we have developed an effective deep learning algorithm based on insights into the properties of visual quality of images and the internal representation properties of a deep convolutional neural network (CNN). We train a deep CNN as a nonlinear transformation function to map a low bit depth image to higher bit depth or from a halftone image to a continuous tone image. We also employ another pretrained deep CNN as a feature extractor to derive visually important features to construct the objective function for the training of the mapping CNN. We present experimental results to demonstrate the effectiveness of the new deep learning based solutions.
Employing Emotion Cues to Verify Speakers in Emotional Talking Environments
Venue: arXiv cs.SD 2017
Year: 2017

Usually, people talk neutrally in environments where there are no abnormal talking conditions such as stress and emotion. Other emotional conditions that might affect people talking tone like happiness, anger, and sadness. Such emotions are directly affected by the patient health status. In neutral talking environments, speakers can be easily verified, however, in emotional talking environments, speakers cannot be easily verified as in neutral talking ones. Consequently, speaker verification systems do not perform well in emotional talking environments as they do in neutral talking environments. In this work, a two-stage approach has been employed and evaluated to improve speaker verification performance in emotional talking environments. This approach employs speaker emotion cues (text-independent and emotion-dependent speaker verification problem) based on both Hidden Markov Models (HMMs) and Suprasegmental Hidden Markov Models (SPHMMs) as classifiers. The approach is comprised of two cascaded stages that combines and integrates emotion recognizer and speaker recognizer into one recognizer. The architecture has been tested on two different and separate emotional speech databases: our collected database and Emotional Prosody Speech and Transcripts database. The results of this work show that the proposed approach gives promising results with a significant improvement over previous studies and other approaches such as emotion-independent speaker verification approach and emotion-dependent speaker verification approach based completely on HMMs.
Speaker Identification in Shouted Talking Environments Based on Novel Third-Order Hidden Markov Models
Venue: arXiv cs.SD 2017
Year: 2017

In this work we propose, implement, and evaluate novel models called Third-Order Hidden Markov Models (HMM3s) to enhance low performance of text-independent speaker identification in shouted talking environments. The proposed models have been tested on our collected speech database using Mel-Frequency Cepstral Coefficients (MFCCs). Our results demonstrate that HMM3s significantly improve speaker identification performance in such talking environments by 11.3% and 166.7% compared to second-order hidden Markov models (HMM2s) and first-order hidden Markov models (HMM1s), respectively. The achieved results based on the proposed models are close to those obtained in subjective assessment by human listeners.
Robust Moment Closure Method for the Chemical Master Equation
Venue: arXiv cs.SY 2017
Year: 2017

The Chemical Master Equation (CME) is used to stochastically model biochemical reaction networks, under the Markovian assumption. The low-order statistical moments induced by the CME are often the key quantities that one is interested in. However, in most cases, the moments equation is not closed; in the sense that the first $n$ moments depend on the higher order moments, for any positive integer $n$. In this paper, we develop a moment closure technique in which the higher order moments are approximated by an affine function of the lower order moments. We refer to such functions as the affine Moment Closure Functions (MCF) and prove that they are optimal in the worst-case context, in which no a priori information on the probability distribution is available. Furthermore, we cast the problem of finding the optimal affine MCF as a linear program, which is tractable. We utilize the affine MCFs to derive a finite dimensional linear system that approximates the low-order moments. We quantify the approximation error in terms of the $% l_{\infty }$ induced norm of some linear system. Our results can be effectively used to approximate the low-order moments and characterize the noise properties of the biochemical network under study.
Measuring, Characterizing, and Detecting Facebook Like Farms
Venue: arXiv cs.CR 2017
Year: 2017

Social networks offer convenient ways to seamlessly reach out to large audiences. In particular, Facebook pages are increasingly used by businesses, brands, and organizations to connect with multitudes of users worldwide. As the number of likes of a page has become a de-facto measure of its popularity and profitability, an underground market of services artificially inflating page likes, aka like farms, has emerged alongside Facebook's official targeted advertising platform. Nonetheless, there is little work that systematically analyzes Facebook pages' promotion methods. Aiming to fill this gap, we present a honeypot-based comparative measurement study of page likes garnered via Facebook advertising and from popular like farms. First, we analyze likes based on demographic, temporal, and social characteristics, and find that some farms seem to be operated by bots and do not really try to hide the nature of their operations, while others follow a stealthier approach, mimicking regular users' behavior. Next, we look at fraud detection algorithms currently deployed by Facebook and show that they do not work well to detect stealthy farms which spread likes over longer timespans and like popular pages to mimic regular users. To overcome their limitations, we investigate the feasibility of timeline-based detection of like farm accounts, focusing on characterizing content generated by Facebook accounts on their timelines as an indicator of genuine versus fake social activity. We analyze a range of features, grouped into two main categories: lexical and non-lexical. We find that like farm accounts tend to re-share content, use fewer words and poorer vocabulary, and more often generate duplicate comments and likes compared to normal users. Using relevant lexical and non-lexical features, we build a classifier to detect like farms accounts that achieves precision higher than 99% and 93% recall.
Rank-1 Constrained Multichannel Wiener Filter for Speech Recognition in Noisy Environments
Venue: arXiv cs.SD 2017
Year: 2017

Multichannel linear filters, such as the Multichannel Wiener Filter (MWF) and the Generalized Eigenvalue (GEV) beamformer are popular signal processing techniques which can improve speech recognition performance. In this paper, we present an experimental study on these linear filters in a specific speech recognition task, namely the CHiME-4 challenge, which features real recordings in multiple noisy environments. Specifically, the rank-1 MWF is employed for noise reduction and a new constant residual noise power constraint is derived which enhances the recognition performance. To fulfill the underlying rank-1 assumption, the speech covariance matrix is reconstructed based on eigenvectors or generalized eigenvectors. Then the rank-1 constrained MWF is evaluated with alternative multichannel linear filters under the same framework, which involves a Bidirectional Long Short-Term Memory (BLSTM) network for mask estimation. The proposed filter outperforms alternative ones, leading to a 40% relative Word Error Rate (WER) reduction compared with the baseline Weighted Delay and Sum (WDAS) beamformer on the real test set, and a 15% relative WER reduction compared with the GEV-BAN method. The results also suggest that the speech recognition accuracy correlates more with the Mel-frequency cepstral coefficients (MFCC) feature variance than with the noise reduction or the speech distortion level.
Reconciling Selfish Routing with Social Good
Venue: arXiv cs.GT 2017
Year: 2017

Selfish routing is a central problem in algorithmic game theory, with one of the principal applications being that of routing in road networks. Inspired by the emergence of routing technologies and autonomous driving, we revisit selfish routing and consider three possible outcomes of it: (i) $θ$-Positive Nash Equilibrium flow, where every path that has non-zero flow on all of its edges has cost no greater than $θ$ times the cost of any other path, (ii) $θ$-Used Nash Equilibrium flow, where every used path that appears in the path flow decomposition has cost no greater than $θ$ times the cost of any other path, and (iii) $θ$-Envy Free flow, where every path that appears in the path flow decomposition has cost no greater than $θ$ times the cost of any other path in the path flow decomposition. We first examine the relations of these outcomes among each other and then measure their possible impact on the network's performance. Afterwards, we examine the computational complexity of finding such flows of minimum social cost and give a range for $θ$ for which this task is easy and a range for $θ$ for which this task is NP-hard. Finally, we propose deterministic strategies which, in a worst case approach, can be used by a central planner in order to provide good such flows, and further introduce a natural idea for randomly routing players after giving them specific guarantees about their costs in the randomized routing, as a tool for the central planner to implement a desired flow.
Modifying Optimal SAT-based Approach to Multi-agent Path-finding Problem to Suboptimal Variants
Venue: arXiv cs.AI 2017
Year: 2017

In multi-agent path finding (MAPF) the task is to find non-conflicting paths for multiple agents. In this paper we focus on finding suboptimal solutions for MAPF for the sum-of-costs variant. Recently, a SAT-based approached was developed to solve this problem and proved beneficial in many cases when compared to other search-based solvers. In this paper, we present SAT-based unbounded- and bounded-suboptimal algorithms and compare them to relevant algorithms. Experimental results show that in many case the SAT-based solver significantly outperforms the search-based solvers.
Where to Play: Retrieval of Video Segments using Natural-Language Queries
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we propose a new approach for retrieval of video segments using natural language queries. Unlike most previous approaches such as concept-based methods or rule-based structured models, the proposed method uses image captioning model to construct sentential queries for visual information. In detail, our approach exploits multiple captions generated by visual features in each image with `Densecap'. Then, the similarities between captions of adjacent images are calculated, which is used to track semantically similar captions over multiple frames. Besides introducing this novel idea of 'tracking by captioning', the proposed method is one of the first approaches that uses a language generation model learned by neural networks to construct semantic query describing the relations and properties of visual information. To evaluate the effectiveness of our approach, we have created a new evaluation dataset, which contains about 348 segments of scenes in 20 movie-trailers. Through quantitative and qualitative evaluation, we show that our method is effective for retrieval of video segments using natural language queries.
Photonic Hybrid Precoding for Millimeter Wave RoF Systems
Venue: arXiv cs.IT 2017
Year: 2017

Large propagation path loss and limited scattering of millimeter wave (mmwave) channels create new challenges for physical layer signal processing. Hence, in this article, we propose a photonic hybrid precoding model for mmwave radio-over-fiber systems that overcomes hardware constraints on radio frequency precoding. With help of silicon photonic integrated circuits (Si-PICs), the photonic precoding strategy combats the large losses of mmwave and mitigates inter-user interference. Simulation results show that the proposed model can offer significant coding gains over conventional precoding systems.
Vectorial Dimension Reduction for Tensors Based on Bayesian Inference
Venue: arXiv cs.CV 2017
Year: 2017

Dimensionality reduction for high-order tensors is a challenging problem. In conventional approaches, higher order tensors are `vectorized` via Tucker decomposition to obtain lower order tensors. This will destroy the inherent high-order structures or resulting in undesired tensors, respectively. This paper introduces a probabilistic vectorial dimensionality reduction model for tensorial data. The model represents a tensor by employing a linear combination of same order basis tensors, thus it offers a mechanism to directly reduce a tensor to a vector. Under this expression, the projection base of the model is based on the tensor CandeComp/PARAFAC (CP) decomposition and the number of free parameters in the model only grows linearly with the number of modes rather than exponentially. A Bayesian inference has been established via the variational EM approach. A criterion to set the parameters (factor number of CP decomposition and the number of extracted features) is empirically given. The model outperforms several existing PCA-based methods and CP decomposition on several publicly available databases in terms of classification and clustering accuracy.
A Fast Method For Computing Principal Curvatures From Range Images
Venue: arXiv cs.CV 2017
Year: 2017

Estimation of surface curvature from range data is important for a range of tasks in computer vision and robotics, object segmentation, object recognition and robotic grasping estimation. This work presents a fast method of robustly computing accurate metric principal curvature values from noisy point clouds which was implemented on GPU. In contrast to existing readily available solutions which first differentiate the surface to estimate surface normals and then differentiate these to obtain curvature, amplifying noise, our method iteratively fits parabolic quadric surface patches to the data. Additionally previous methods with a similar formulation use less robust techniques less applicable to a high noise sensor. We demonstrate that our method is fast and provides better curvature estimates than existing techniques. In particular we compare our method to several alternatives to demonstrate the improvement.
On Asymptotic Properties of Hyperparameter Estimators for Kernel-based Regularization Methods
Venue: arXiv cs.SY 2017
Year: 2017

The kernel-based regularization method has two core issues: kernel design and hyperparameter estimation. In this paper, we focus on the second issue and study the properties of several hyperparameter estimators including the empirical Bayes (EB) estimator, two Stein's unbiased risk estimators (SURE) and their corresponding Oracle counterparts, with an emphasis on the asymptotic properties of these hyperparameter estimators. To this goal, we first derive and then rewrite the first order optimality conditions of these hyperparameter estimators, leading to several insights on these hyperparameter estimators. Then we show that as the number of data goes to infinity, the two SUREs converge to the best hyperparameter minimizing the corresponding mean square error, respectively, while the more widely used EB estimator converges to another best hyperparameter minimizing the expectation of the EB estimation criterion. This indicates that the two SUREs are asymptotically optimal but the EB estimator is not. Surprisingly, the convergence rate of two SUREs is slower than that of the EB estimator, and moreover, unlike the two SUREs, the EB estimator is independent of the convergence rate of $Φ^TΦ/N$ to its limit, where $Φ$ is the regression matrix and $N$ is the number of data. A Monte Carlo simulation is provided to demonstrate the theoretical results.
Complex-network approach for visualizing and quantifying the evolution of a scientific topic
Venue: arXiv cs.DL 2017
Year: 2017

Tracing the evolution of specific topics is a subject area which belongs to the general problem of mapping the structure of scientific knowledge. Often bibliometric data bases are used to study the history of scientific topic evolution from its appearance to its extinction or merger with other topics. In this chapter the authors present an analysis of the academic response to the disaster that occurred in 1986 in Chornobyl (Chernobyl), Ukraine, considered as one of the most devastating nuclear power plant accidents in history. Using a bibliographic database the distributions of Chornobyl-related papers in different scientific fields are analysed, as are their growth rates and properties of co-authorship networks. Elements of descriptive statistics and tools of complex-network theory are used to highlight interdisciplinary as well as international effects. In particular, tools of complex-network science enable information visualization complemented by further quantitative analysis. A further goal of the chapter is to provide a simple pedagogical introduction to the application of complex-network analysis for visual data representation and interdisciplinary communication.
A Projected Inverse Dynamics Approach for Dual-arm Cartesian Impedance Control
Venue: arXiv cs.RO 2017
Year: 2017

We propose a method for dual-arm manipulation of rigid objects, subject to external disturbance. The problem is formulated as a Cartesian impedance controller within a projected inverse dynamics framework. We use the constrained component of the controller to enforce contact and the unconstrained controller to accomplish the task with a desired 6-DOF impedance behaviour. Furthermore, the proposed method optimises the torque required to maintain contact, subject to unknown disturbances, and can do so without direct measurement of external force. The techniques are evaluated on a single-arm wiping a table and a dual-arm platform manipulating a rigid object of unknown mass and with human interaction.
Towards Understanding the Evolution of the WWW Conference
Venue: arXiv cs.DL 2017
Year: 2017

The World Wide Web conference is a well-established and mature venue with an already long history. Over the years it has been attracting papers reporting many important research achievements centered around the Web. In this work we aim at understanding the evolution of WWW conference series by detecting crucial years and important topics. We propose a simple yet novel approach based on tracking the classification errors of the conference papers according to their predicted publication years.
On the tightness of Tietäväinen's bound for distributions with limited independence
Venue: arXiv cs.IT 2017
Year: 2017

In 1990, Tietäväinen showed that if the only information we know about a linear code is its dual distance $d$, then its covering radius $R$ is at most $\frac{n}{2}-(\frac{1}{2}-o(1))\sqrt{dn}$. While Tietäväinen's bound was later improved for large values of $d$, it is still the best known upper bound for small values including the $d = o(n)$ regime. Tietäväinen's bound holds also for $(d-1)$-wise independent probability distributions on $\{0,1\}^n$, of which linear codes with dual distance $d$ are special cases. We show that Tietäväinen's bound on $R-\frac{n}{2}$ is asymptotically tight up to a factor of $2$ for $k$-wise independent distributions if $k\leq\frac{n^{1/3}}{\log^2{n}}$. Namely, we show that there exists a $k$-wise independent probability distribution $μ$ on $\{0,1\}^n$ whose covering radius is at least $\frac{n}{2}-\sqrt{kn}$. Our key technical contribution is the following lemma on low degree polynomials, which implies the existence of $μ$ by linear programming duality. We show that, for sufficiently large $k\leq\frac{n^{1/3}}{\log^2{n}}$ and for each polynomial $f(v)\in {\mathbb R}[v]$ of degree at most $k$, the expected value of $f$ with respect to the binomial distribution cannot be positive if $f(w)\leq 0$ for each integer $w$ such that $|w-n/2|\leq\sqrt{kn}$. The proof uses tools from approximation theory.