OpenRaiser/Intern-Atlas huggingface dataset:
A BP-MF-EP Based Iterative Receiver for Joint Phase Noise Estimation, Equalization and Decoding
Venue: arXiv cs.IT 2016
Year: 2016

In this work, with combined belief propagation (BP), mean field (MF) and expectation propagation (EP), an iterative receiver is designed for joint phase noise (PN) estimation, equalization and decoding in a coded communication system. The presence of the PN results in a nonlinear observation model. Conventionally, the nonlinear model is directly linearized by using the first-order Taylor approximation, e.g., in the state-of-the-art soft-input extended Kalman smoothing approach (soft-in EKS). In this work, MF is used to handle the factor due to the nonlinear model, and a second-order Taylor approximation is used to achieve Gaussian approximation to the MF messages, which is crucial to the low-complexity implementation of the receiver with BP and EP. It turns out that our approximation is more effective than the direct linearization in the soft-in EKS with similar complexity, leading to significant performance improvement as demonstrated by simulation results.
On Nyquist-Shannon Theorem with one-sided half of sampling sequence
Venue: arXiv cs.IT 2016
Year: 2016

The classical sampling Nyquist-Shannon-Kotelnikov theorem states that a band-limited continuous time function can be uniquely recovered without error from a infinite two-sided sampling series taken with a sufficient frequency. This short note shows that the function can be recovered from any one-sided semi-infinite half of any oversampling series, with the same boundary for admissible frequencies as in the classical theorem.
ARX modeling of unstable linear systems
Venue: arXiv cs.SY 2016
Year: 2016

High-order ARX models can be used to approximate a quite general class of linear systems in a parametric model structure, and well-established methods can then be used to retrieve the true plant and noise models from the ARX polynomials. However, this commonly used approach is only valid when the plant is stable or if the unstable poles are shared with the true noise model. In this contribution, we generalize this approach to allow the unstable poles not to be shared, by introducing modifications to correctly retrieve the noise model and noise variance.
Online Isotonic Regression
Venue: arXiv cs.LG 2016
Year: 2016

We consider the online version of the isotonic regression problem. Given a set of linearly ordered points (e.g., on the real line), the learner must predict labels sequentially at adversarially chosen positions and is evaluated by her total squared loss compared against the best isotonic (non-decreasing) function in hindsight. We survey several standard online learning algorithms and show that none of them achieve the optimal regret exponent; in fact, most of them (including Online Gradient Descent, Follow the Leader and Exponential Weights) incur linear regret. We then prove that the Exponential Weights algorithm played over a covering net of isotonic functions has a regret bounded by $O\big(T^{1/3} \log^{2/3}(T)\big)$ and present a matching $Ω(T^{1/3})$ lower bound on regret. We provide a computationally efficient version of this algorithm. We also analyze the noise-free case, in which the revealed labels are isotonic, and show that the bound can be improved to $O(\log T)$ or even to $O(1)$ (when the labels are revealed in isotonic order). Finally, we extend the analysis beyond squared loss and give bounds for entropic loss and absolute loss.
Efficient Generation of Inductive Validity Cores for Safety Properties
Venue: arXiv cs.SE 2016
Year: 2016

Symbolic model checkers can construct proofs of properties over very complex models. However, the results reported by the tool when a proof succeeds do not generally provide much insight to the user. It is often useful for users to have traceability information related to the proof: which portions of the model were necessary to construct it. This traceability information can be used to diagnose a variety of modeling problems such as overconstrained axioms and underconstrained properties, and can also be used to measure completeness of a set of requirements over a model. In this paper, we present a new algorithm to efficiently compute the inductive validity core (IVC) within a model necessary for inductive proofs of safety properties for sequential systems. The algorithm is based on the UNSAT core support built into current SMT solvers and a novel encoding of the inductive problem to try to generate a minimal inductive validity core. We prove our algorithm is correct, and describe its implementation in the JKind model checker for Lustre models. We then present an experiment in which we benchmark the algorithm in terms of speed, diversity of produced cores, and minimality, with promising results.
Mining Valence, Arousal, and Dominance - Possibilities for Detecting Burnout and Productivity?
Venue: arXiv cs.SE 2016
Year: 2016

Similar to other industries, the software engineering domain is plagued by psychological diseases such as burnout, which lead developers to lose interest, exhibit lower activity and/or feel powerless. Prevention is essential for such diseases, which in turn requires early identification of symptoms. The emotional dimensions of Valence, Arousal and Dominance (VAD) are able to derive a person's interest (attraction), level of activation and perceived level of control for a particular situation from textual communication, such as emails. As an initial step towards identifying symptoms of productivity loss in software engineering, this paper explores the VAD metrics and their properties on 700,000 Jira issue reports containing over 2,000,000 comments, since issue reports keep track of a developer's progress on addressing bugs or new features. Using a general-purpose lexicon of 14,000 English words with known VAD scores, our results show that issue reports of different type (e.g., Feature Request vs. Bug) have a fair variation of Valence, while increase in issue priority (e.g., from Minor to Critical) typically increases Arousal. Furthermore, we show that as an issue's resolution time increases, so does the arousal of the individual the issue is assigned to. Finally, the resolution of an issue increases valence, especially for the issue Reporter and for quickly addressed issues. The existence of such relations between VAD and issue report activities shows promise that text mining in the future could offer an alternative way for work health assessment surveys.
An Effectful Treatment of Dependent Types
Venue: arXiv cs.PL 2016
Year: 2016

We extend Levy's call-by-push-value (CBPV) analysis from simple to dependent type theory (DTT) in order to study the interaction between computational effects and dependent types. We define the naive system of dependently typed CBPV, dCBPV-, and its extension with a principle of Kleisli extensions for dependent functions, dCBPV+. We investigate these systems from the points of view of syntax, categorical semantics, concrete models and operational semantics, in presence of a range of effects. We observe that, while the expressive power of dCBPV+ is needed if we want well-defined call-by-value (CBV) and call-by-name (CBN) translations of DTT, it is a less straightforward system than dCBPV-, in presence of some effects. Indeed, to be able to construct specific models and to retain the subject reduction property in the operational semantics, we are required to impose certain subtyping conditions, the idea being that the type of a computation may only become more (not less) specified as certain effects are executed.
Gradient approximation and extremum seeking via needle variations
Venue: arXiv cs.SY 2016
Year: 2016

We consider a gradient approximation scheme that is based on applying needle shaped inputs. By using ideas known from the classic proof of the Pontryagin Maximum Principle we derive an approximation that reveals that the considered system moves along a weighted averaged gradient. Moreover, based on the same ideas, we give similar results for arbitrary periodic inputs. We also present a new gradient-based optimization algorithm that is motivated by our calculations and that can be interpreted as a combination of the heavy ball method and Nesterov's method.
Learning Network of Multivariate Hawkes Processes: A Time Series Approach
Venue: arXiv cs.LG 2016
Year: 2016

Learning the influence structure of multiple time series data is of great interest to many disciplines. This paper studies the problem of recovering the causal structure in network of multivariate linear Hawkes processes. In such processes, the occurrence of an event in one process affects the probability of occurrence of new events in some other processes. Thus, a natural notion of causality exists between such processes captured by the support of the excitation matrix. We show that the resulting causal influence network is equivalent to the Directed Information graph (DIG) of the processes, which encodes the causal factorization of the joint distribution of the processes. Furthermore, we present an algorithm for learning the support of excitation matrix (or equivalently the DIG). The performance of the algorithm is evaluated on synthesized multivariate Hawkes networks as well as a stock market and MemeTracker real-world dataset.
Automatic Discrimination of Color Retinal Images using the Bag of Words Approach
Venue: arXiv cs.CV 2016
Year: 2016

Diabetic retinopathy (DR) and age related macular degeneration (ARMD) are among the major causes of visual impairment worldwide. DR is mainly characterized by red spots, namely microaneurysms and bright lesions, specifically exudates whereas ARMD is mainly identified by tiny yellow or white deposits called drusen. Since exudates might be the only manifestation of the early diabetic retinopathy, there is an increase demand for automatic retinopathy diagnosis. Exudates and drusen may share similar appearances, thus discriminating between them is of interest to enhance screening performance. In this research, we investigative the role of bag of words approach in the automatic diagnosis of retinopathy diabetes. We proposed to use a single based and multiple based methods for the construction of the visual dictionary by combining the histogram of word occurrences from each dictionary and building a single histogram. The introduced approach is evaluated for automatic diagnosis of normal and abnormal color fundus images with bright lesions. This approach has been implemented on 430 fundus images, including six publicly available datasets, in addition to one local dataset. The mean accuracies reported are 97.2% and 99.77% for single based and multiple based dictionaries respectively.
Computing the Approximate Convex Hull in High Dimensions
Venue: arXiv cs.CG 2016
Year: 2016

In this paper, an effective method with time complexity of $\mathcal{O}(K^{3/2}N^2\log \frac{K}{ε_0})$ is introduced to find an approximation of the convex hull for $N$ points in dimension $n$, where $K$ is close to the number of vertices of the approximation. Since the time complexity is independent of dimension, this method is highly suitable for the data in high dimensions. Utilizing a greedy approach, the proposed method attempts to find the best approximate convex hull for a given number of vertices. The approximate convex hull can be a helpful substitute for the exact convex hull for on-line processes and applications that have a favorable trade off between accuracy and parsimony.
The Quadratic Minimum Spanning Tree Problem and its Variations
Venue: arXiv cs.DS 2016
Year: 2016

The quadratic minimum spanning tree problem and its variations such as the quadratic bottleneck spanning tree problem, the minimum spanning tree problem with conflict pair constraints, and the bottleneck spanning tree problem with conflict pair constraints are useful in modeling various real life applications. All these problems are known to be NP-hard. In this paper, we investigate these problems to obtain additional insights into the structure of the problems and to identify possible demarcation between easy and hard special cases. New polynomially solvable cases have been identified, as well as NP-hard instances on very simple graphs. As a byproduct, we have a recursive formula for counting the number of spanning trees on a $(k,n)$-accordion and a characterization of matroids in the context of a quadratic objective function.
Towards Bottom-Up Analysis of Social Food
Venue: arXiv cs.CY 2016
Year: 2016

Social media provide a wealth of information for research into public health by providing a rich mix of personal data, location, hashtags, and social network information. Among these, Instagram has been recently the subject of many computational social science studies. However despite Instagram's focus on image sharing, most studies have exclusively focused on the hashtag and social network structure. In this paper we perform the first large scale content analysis of Instagram posts, addressing both the image and the associated hashtags, aiming to understand the content of partially-labelled images taken in-the-wild and the relationship with hashtags that individuals use as noisy labels. In particular, we explore the possibility of learning to recognise food image content in a data driven way, discovering both the categories of food, and how to recognise them, purely from social network data. Notably, we demonstrate that our approach to food recognition can often achieve accuracies greater than 70% in recognising popular food-related image categories, despite using no manual annotation. We highlight the current capabilities and future challenges and opportunities for such data-driven analysis of image content and the relation to hashtags.
Multichannel Variable-Size Convolution for Sentence Classification
Venue: arXiv cs.CL 2016
Year: 2016

We propose MVCNN, a convolution neural network (CNN) architecture for sentence classification. It (i) combines diverse versions of pretrained word embeddings and (ii) extracts features of multigranular phrases with variable-size convolution filters. We also show that pretraining MVCNN is critical for good performance. MVCNN achieves state-of-the-art performance on four tasks: on small-scale binary, small-scale multi-class and largescale Twitter sentiment prediction and on subjectivity classification.
Fuzzy alternating $\mathrm{B\ddot{u}chi}$ automata over distributive lattices
Venue: arXiv cs.FL 2016
Year: 2016

We give a new version of fuzzy alternating $\mathrm{B\ddot{u}chi}$ automata over distributive lattices: weights are putting in every leaf node of run trees rather than along with edges from every node to its children. Such settings are great benefit to obtain complement just by taking dual operation and replacing each final weight with its complement. We prove that $L$-fuzzy nondeterministic $\mathrm{B\ddot{u}chi}$ automata have the same expressive power as $L$-fuzzy alternating $\mathrm{B\ddot{u}chi}$ ones. A direct construction (without related knowledge about $L$-fuzzy nondeterministic $\mathrm{B\ddot{u}chi}$ ones such as: above equivalence relation and their closure properties) is given to show that the languages recognized by $L$-fuzzy alternating co-$\mathrm{B\ddot{u}chi}$ automata are also $L$-fuzzy $ω$-regular. Furthermore, the closure properties and the discussion about decision problems for fuzzy alternating $\mathrm{B\ddot{u}chi}$ automata are illustrated in our paper.
On Reliability Function Of BSC: Expanding The Region, Where It Is Known Exactly
Venue: arXiv cs.IT 2016
Year: 2016

The region of rates ("straight-line"), where the BSC reliability function is known exactly, is expanded.
Caching in Wireless Small Cell Networks: A Storage-Bandwidth Tradeoff
Venue: arXiv cs.IT 2016
Year: 2016

Caching contents at the network edge is an efficient mean for offloading traffic, reducing latency and improving users' quality-of-experience. In this letter, we focus on aspects of storage-bandwidth tradeoffs in which small cell base stations are distributed according to a homogeneous Poisson point process and cache contents according to a given content popularity distribution, subject to storage constraints. We provide a closed-form expression of the cache-miss probability, defined as the probability of not satisfying users' requests over a given coverage area, as a function of signal-to-interference ratio, cache size, base stations density and content popularity. In particular, it is shown that for a given minimum cache size, the popularity based caching strategy achieves lower outage probability for a given base station density compared to uniform caching. Furthermore, we show that popularity based caching attains better performance in terms of cache-miss probability for the same amount of spectrum.
Semi-Supervised Verified Feedback Generation
Venue: arXiv cs.SE 2016
Year: 2016

Students have enthusiastically taken to online programming lessons and contests. Unfortunately, they tend to struggle due to lack of personalized feedback when they make mistakes. The overwhelming number of submissions precludes manual evaluation. There is an urgent need of program analysis and repair techniques capable of handling both the scale and variations in student submissions, while ensuring quality of feedback. Towards this goal, we present a novel methodology called semi-supervised verified feedback generation. We cluster submissions by solution strategy and ask the instructor to identify or add a correct submission in each cluster. We then verify every submission in a cluster against the instructor-validated submission in the same cluster. If faults are detected in the submission then feedback suggesting fixes to them is generated. Clustering reduces the burden on the instructor and also the variations that have to be handled during feedback generation. The verified feedback generation ensures that only correct feedback is generated. We have applied this methodology to iterative dynamic programming (DP) assignments. Our clustering technique uses features of DP solutions. We have designed a novel counter-example guided feedback generation algorithm capable of suggesting fixes to all faults in a submission. In an evaluation on 2226 submissions to 4 problems, we could generate verified feedback for 1911 (85%) submissions in 1.6s each on an average. Our technique does a good job of reducing the burden on the instructor. Only one submission had to be manually validated or added for every 16 submissions.
Nested Invariance Pooling and RBM Hashing for Image Instance Retrieval
Venue: arXiv cs.CV 2016
Year: 2016

The goal of this work is the computation of very compact binary hashes for image instance retrieval. Our approach has two novel contributions. The first one is Nested Invariance Pooling (NIP), a method inspired from i-theory, a mathematical theory for computing group invariant transformations with feed-forward neural networks. NIP is able to produce compact and well-performing descriptors with visual representations extracted from convolutional neural networks. We specifically incorporate scale, translation and rotation invariances but the scheme can be extended to any arbitrary sets of transformations. We also show that using moments of increasing order throughout nesting is important. The NIP descriptors are then hashed to the target code size (32-256 bits) with a Restricted Boltzmann Machine with a novel batch-level regularization scheme specifically designed for the purpose of hashing (RBMH). A thorough empirical evaluation with state-of-the-art shows that the results obtained both with the NIP descriptors and the NIP+RBMH hashes are consistently outstanding across a wide range of datasets.
A branch and bound algorithm for a fractional 0-1 programming problem
Venue: arXiv cs.DS 2016
Year: 2016

We consider a fractional 0-1 programming problem arising in manufacturing. The problem consists in clustering of machines together with parts processed on these machines into manufacturing cells so that intra-cell processing of parts is maximized and inter-cell movement is minimized. This problem is called Cell Formation Problem (CFP) and it is an NP-hard optimization problem with Boolean variables and constraints and with a fractional objective function. Because of its high computational complexity there are a lot of heuristics developed for it. In this paper we suggest a branch and bound algorithm which provides exact solutions for the CFP with a variable number of cells and grouping efficacy objective function. This algorithm finds optimal solutions for 21 of the 35 popular benchmark instances from literature and for the remaining 14 instances it finds good solutions close to the best known.
Recent techniques and results on the Erdős-Pósa property
Venue: arXiv cs.DM 2016
Year: 2016

Several min-max relations in graph theory can be expressed in the framework of the Erdős-Pósa property. Typically, this property reveals a connection between packing and covering problems on graphs. We describe some recent techniques for proving this property that are related to tree-like decompositions. We also provide an unified presentation of the current state of the art on this topic.
TAPER: query-aware, partition-enhancement for large, heterogenous, graphs
Venue: arXiv cs.DB 2016
Year: 2016

Graph partitioning has long been seen as a viable approach to address Graph DBMS scalability. A partitioning, however, may introduce extra query processing latency unless it is sensitive to a specific query workload, and optimised to minimise inter-partition traversals for that workload. Additionally, it should also be possible to incrementally adjust the partitioning in reaction to changes in the graph topology, the query workload, or both. Because of their complexity, current partitioning algorithms fall short of one or both of these requirements, as they are designed for offline use and as one-off operations. The TAPER system aims to address both requirements, whilst leveraging existing partitioning algorithms. TAPER takes any given initial partitioning as a starting point, and iteratively adjusts it by swapping chosen vertices across partitions, heuristically reducing the probability of inter-partition traversals for a given pattern matching queries workload. Iterations are inexpensive thanks to time and space optimisations in the underlying support data structures. We evaluate TAPER on two different large test graphs and over realistic query workloads. Our results indicate that, given a hash-based partitioning, TAPER reduces the number of inter-partition traversals by around 80%; given an unweighted METIS partitioning, by around 30%. These reductions are achieved within 8 iterations and with the additional advantage of being workload-aware and usable online.
Modeling Time Series Similarity with Siamese Recurrent Networks
Venue: arXiv cs.CV 2016
Year: 2016

Traditional techniques for measuring similarities between time series are based on handcrafted similarity measures, whereas more recent learning-based approaches cannot exploit external supervision. We combine ideas from time-series modeling and metric learning, and study siamese recurrent networks (SRNs) that minimize a classification loss to learn a good similarity measure between time series. Specifically, our approach learns a vectorial representation for each time series in such a way that similar time series are modeled by similar representations, and dissimilar time series by dissimilar representations. Because it is a similarity prediction models, SRNs are particularly well-suited to challenging scenarios such as signature recognition, in which each person is a separate class and very few examples per class are available. We demonstrate the potential merits of SRNs in within-domain and out-of-domain classification experiments and in one-shot learning experiments on tasks such as signature, voice, and sign language recognition.