OpenRaiser/Intern-Atlas huggingface dataset:
Inferring Population Preferences via Mixtures of Spatial Voting Models
Venue: arXiv cs.CY 2016
Year: 2016

Understanding political phenomena requires measuring the political preferences of society. We introduce a model based on mixtures of spatial voting models that infers the underlying distribution of political preferences of voters with only voting records of the population and political positions of candidates in an election. Beyond offering a cost-effective alternative to surveys, this method projects the political preferences of voters and candidates into a shared latent preference space. This projection allows us to directly compare the preferences of the two groups, which is desirable for political science but difficult with traditional survey methods. After validating the aggregated-level inferences of this model against results of related work and on simple prediction tasks, we apply the model to better understand the phenomenon of political polarization in the Texas, New York, and Ohio electorates. Taken at face value, inferences drawn from our model indicate that the electorates in these states may be less bimodal than the distribution of candidates, but that the electorates are comparatively more extreme in their variance. We conclude with a discussion of limitations of our method and potential future directions for research.
LambdaDL: Syntax and Semantics (Preliminary Report)
Venue: arXiv cs.PL 2016
Year: 2016

Semantic data fuels many different applications, but is still lacking proper integration into programming languages. Untyped access is error-prone while mapping approaches cannot fully capture the conceptualization of semantic data. In this paper, we present $λ_{DL}$,a $λ$-calculus with a modified type system to provide type-safe integration of semantic data. This is achieved by the integration of description logics into the $λ$-calculus for typing and data access. It is centered around several key design principles. Among these are (1) the usage of semantic conceptualizations as types, (2) subtype inference for these types, and (3) type-checked query access to the data by both ensuring the satisfiability of queries as well as typing query results precisely in $λ_{DL}$. The paper motivates the use of a modified type system for semantic data and it provides the theoretic foundation for the integration of description logics as well as the core formal specifications of $λ_{DL}$ including a proof of type safety.
A class of Weiss-Weinstein bounds and its relationship with the Bobrovsky-Mayer-Wolf-Zakai bounds
Venue: arXiv cs.IT 2016
Year: 2016

A fairly general class of Bayesian "large-error" lower bounds of the Weiss-Weinstein family, essentially free from regularity conditions on the probability density functions support, and for which a limiting form yields a generalized Bayesian Cramer-Rao bound (BCRB), is introduced. In a large number of cases, the generalized BCRB appears to be the Bobrovsky-Mayer-Wolf-Zakai bound (BMZB). Interestingly enough, a regularized form of the Bobrovsky-Zakai bound (BZB), applicable when the support of the prior is a constrained parameter set, is obtained. Modified Weiss-Weinstein bound and BZB which limiting form is the BMZB are proposed, in expectation of an increased tightness in the threshold region. Some of the proposed results are exemplified with a reference problem in signal processing: the Gaussian observation model with parameterized mean and uniform prior.
Symplectic Geometric Algorithm for Quaternion Kinematical Differential Equation
Venue: arXiv cs.SY 2016
Year: 2016

Solving quaternion kinematical differential equations is one of the most significant problems in the automation, navigation, aerospace and aeronautics literatures. Most existing approaches for this problem neither preserve the norm of quaternions nor avoid errors accumulated in the sense of long term time. We present symplectic geometric algorithms to deal with the quaternion kinematical differential equation by modeling its time-invariant and time-varying versions with Hamiltonian systems by adopting a three-step strategy. Firstly, a generalized Euler's formula for the autonomous quaternion kinematical differential equation are proved and used to construct symplectic single-step transition operators via the centered implicit Euler scheme for autonomous Hamiltonian system. Secondly, the symplecitiy, orthogonality and invertibility of the symplectic transition operators are proved rigorously. Finally, the main results obtained are generalized to design symplectic geometric algorithm for the time-varying quaternion kinematical differential equation which is a non-autonomous and nonlinear Hamiltonian system essentially. Our novel algorithms have simple algorithmic structures and low time complexity of computation, which are easy to be implemented with real-time techniques. The correctness and efficiencies of the proposed algorithms are verified and validated via numerical simulations.
On the equivalence of proportional-integral and proportional-resonant controllers with anti-windup
Venue: arXiv cs.SY 2016
Year: 2016

It is shown that proportional-integral (PI) control in the synchronously rotating (d, q)-reference frame and proportional-resonant (PR) control in the stationary (α, \b{eta})-reference frame, both with anti-windup, are equivalent if and only if their implementation is done correctly in state space and the controller parameters and the initial values are identical. It is shown that an equivalence in the frequency domain does only hold if simplifying assumptions are satisfied. As consequence of the equivalence, both closed- loop control performances are identical with respect to closed-loop dynamics and steady-state accuracy. The control performance will only differ if their implementation is not done correctly or the time delay induced by the voltage source inverter becomes significant. To the best knowledge of the author, equivalence of PR and PI controllers with anti-windup has not been shown before (in particular not in state space).
Colouring of (P3UP2)-free graphs
Venue: arXiv cs.DM 2016
Year: 2016

The class of 2K2-free graphs and its various subclasses have been studied in a variety of contexts. In this paper, we are concerned with the colouring of (P3UP2)-free graphs, a super class of 2K2-free graphs. We derive a O(w^3) upper bound for the chromatic number of (P3UP2)-free graphs, and sharper bounds for (P3UP2), diamond)-free graphs, where w denotes the clique number. By applying similar proof techniques we obtain chromatic bounds for (2K2, diamond)-free graphs. The last two classes are perfect if w >=5 and >= 4 respectively.
Hybrid Static/Dynamic Schedules for Tiled Polyhedral Programs
Venue: arXiv cs.PL 2016
Year: 2016

Polyhedral compilers perform optimizations such as tiling and parallelization; when doing both, they usually generate code that executes "barrier-synchronized wavefronts" of tiles. We present a system to express and generate code for hybrid schedules, where some constraints are automatically satisfied through the structure of the code, and the remainder are dynamically enforced at run-time with data flow mechanisms. We prove bounds on the added overheads that are better, by at least one polynomial degree, than those of previous techniques. We propose a generic mechanism to implement the needed synchronization, and show it can be easily realized for a variety of targets: OpenMP, Pthreads, GPU (CUDA or OpenCL) code, languages like X10, Habanero, Cilk, as well as data flow platforms like DAGuE, and OpenStream and MPI. We also provide a simple concrete implementation that works without the need of any sophisticated run-time mechanism. Our experiments show our simple implementation to be competitive or better than the wavefront-synchronized code generated by other systems. We also show how the proposed mechanism can achieve 24% to 70% reduction in energy.
Random Multiple Access for M2M Communications with QoS Guarantees
Venue: arXiv cs.IT 2016
Year: 2016

We propose a novel random multiple access (RMA) scheme with quality of service (QoS) guarantees for machine-to-machine (M2M) communications. We consider a slotted uncoordinated data transmission period during which machine type communication (MTC) devices transmit over the same radio channel. Based on the latency requirements, MTC devices are divided into groups of different sizes, and the transmission frame is divided into subframes of different lengths. In each subframe, each group is assigned an access probability based on which an MTC device decides to transmit replicas of its packet or remain silent. The base station (BS) employs successive interference cancellation (SIC) to recover all the superposed packets. We derive the closed form expressions for the average probability of device resolution for each group, and we use these expressions to design the access probabilities. The accuracy of the expressions is validated through Monte Carlo simulations. We show that the designed access probabilities can guarantee the QoS requirements with high reliability and high energy efficiency. Finally, we show that RMA can outperform standard coordinated access schemes as well as some of the recently proposed M2M access schemes for cellular networks.
SSH (Sketch, Shingle, & Hash) for Indexing Massive-Scale Time Series
Venue: arXiv cs.IR 2016
Year: 2016

Similarity search on time series is a frequent operation in large-scale data-driven applications. Sophisticated similarity measures are standard for time series matching, as they are usually misaligned. Dynamic Time Warping or DTW is the most widely used similarity measure for time series because it combines alignment and matching at the same time. However, the alignment makes DTW slow. To speed up the expensive similarity search with DTW, branch and bound based pruning strategies are adopted. However, branch and bound based pruning are only useful for very short queries (low dimensional time series), and the bounds are quite weak for longer queries. Due to the loose bounds branch and bound pruning strategy boils down to a brute-force search. To circumvent this issue, we design SSH (Sketch, Shingle, & Hashing), an efficient and approximate hashing scheme which is much faster than the state-of-the-art branch and bound searching technique: the UCR suite. SSH uses a novel combination of sketching, shingling and hashing techniques to produce (probabilistic) indexes which align (near perfectly) with DTW similarity measure. The generated indexes are then used to create hash buckets for sub-linear search. Our results show that SSH is very effective for longer time sequence and prunes around 95% candidates, leading to the massive speedup in search with DTW. Empirical results on two large-scale benchmark time series data show that our proposed method can be around 20 times faster than the state-of-the-art package (UCR suite) without any significant loss in accuracy.
Hashkat: Large-scale simulations of online social networks
Venue: arXiv cs.SI 2016
Year: 2016

Hashkat (http://hashkat.org) is a free, open source, agent based simulation software package designed to simulate large-scale online social networks (e.g. Twitter, Facebook, LinkedIn, etc). It allows for dynamic agent generation, edge creation, and information propagation. The purpose of hashkat is to study the growth of online social networks and how information flows within them. Like real life online social networks, hashkat incorporates user relationships, information diffusion, and trending topics. Hashkat was implemented in C++, and was designed with extensibility in mind. The software includes Shell and Python scripts for easy installation and usability. In this report, we describe all of the algorithms and features integrated into hashkat before moving on to example use cases. In general, hashkat can be used to understand the underlying topology of social networks, validate sampling methods of such networks, develop business strategy for advertising on online social networks, and test new features of an online social network before going into production.
On Multiplicative Multitask Feature Learning
Venue: arXiv cs.LG 2016
Year: 2016

We investigate a general framework of multiplicative multitask feature learning which decomposes each task's model parameters into a multiplication of two components. One of the components is used across all tasks and the other component is task-specific. Several previous methods have been proposed as special cases of our framework. We study the theoretical properties of this framework when different regularization conditions are applied to the two decomposed components. We prove that this framework is mathematically equivalent to the widely used multitask feature learning methods that are based on a joint regularization of all model parameters, but with a more general form of regularizers. Further, an analytical formula is derived for the across-task component as related to the task-specific component for all these regularizers, leading to a better understanding of the shrinkage effect. Study of this framework motivates new multitask learning algorithms. We propose two new learning formulations by varying the parameters in the proposed framework. Empirical studies have revealed the relative advantages of the two new formulations by comparing with the state of the art, which provides instructive insights into the feature learning problem with multiple tasks.
A data augmentation methodology for training machine/deep learning gait recognition algorithms
Venue: arXiv cs.CV 2016
Year: 2016

There are several confounding factors that can reduce the accuracy of gait recognition systems. These factors can reduce the distinctiveness, or alter the features used to characterise gait, they include variations in clothing, lighting, pose and environment, such as the walking surface. Full invariance to all confounding factors is challenging in the absence of high-quality labelled training data. We introduce a simulation-based methodology and a subject-specific dataset which can be used for generating synthetic video frames and sequences for data augmentation. With this methodology, we generated a multi-modal dataset. In addition, we supply simulation files that provide the ability to simultaneously sample from several confounding variables. The basis of the data is real motion capture data of subjects walking and running on a treadmill at different speeds. Results from gait recognition experiments suggest that information about the identity of subjects is retained within synthetically generated examples. The dataset and methodology allow studies into fully-invariant identity recognition spanning a far greater number of observation conditions than would otherwise be possible.
MIMO Multiway Distributed-Relay Channel with Full Data Exchange: An Achievable Rate Perspective
Venue: arXiv cs.IT 2016
Year: 2016

We consider efficient communications over the multiple-input multiple-output (MIMO) multiway distributed relay channel (MDRC) with full data exchange, where each user, equipped with multiple antennas, broadcasts its message to all the other users via the help of a number of distributive relays. We propose a physical-layer network coding (PNC) based scheme involving linear precoding for channel alignment nested lattice coding for PNC, and lattice-based precoding for interference mitigation, We show that, with the proposed scheme, distributed relaying achieves the same sum-rate as cooperative relaying in the high SNR regime. We also show that the proposed scheme achieve the asymptotic sum capacity of the MIMO MDRC within a constant gap at high SNR. Numerical results demonstrate that the proposed scheme considerably outperforms the existing schemes including decode-and-forward and amplify-and-forward.
A Novel Boundary Matching Algorithm for Video Temporal Error Concealment
Venue: arXiv cs.MM 2016
Year: 2016

With the fast growth of communication networks, the video data transmission from these networks is extremely vulnerable. Error concealment is a technique to estimate the damaged data by employing the correctly received data at the decoder. In this paper, an efficient boundary matching algorithm for estimating damaged motion vectors (MVs) is proposed. The proposed algorithm performs error concealment for each damaged macro block (MB) according to the list of identified priority of each frame. It then uses a classic boundary matching criterion or the proposed boundary matching criterion adaptively to identify matching distortion in each boundary of candidate MB. Finally, the candidate MV with minimum distortion is selected as an MV of damaged MB and the list of priorities is updated. Experimental results show that the proposed algorithm improves both objective and subjective qualities of reconstructed frames without any significant increase in computational cost. The PSNR for test sequences in some frames is increased about 4.7, 4.5, and 4.4 dB compared to the classic boundary matching, directional boundary matching, and directional temporal boundary matching algorithm, respectively.
Hardness of approximation for strip packing
Venue: arXiv cs.DS 2016
Year: 2016

Strip packing is a classical packing problem, where the goal is to pack a set of rectangular objects into a strip of a given width, while minimizing the total height of the packing. The problem has multiple applications, e.g. in scheduling and stock-cutting, and has been studied extensively. When the dimensions of objects are allowed to be exponential in the total input size, it is known that the problem cannot be approximated within a factor better than $3/2$, unless $\mathrm{P}=\mathrm{NP}$. However, there was no corresponding lower bound for polynomially bounded input data. In fact, Nadiradze and Wiese [SODA 2016] have recently proposed a $(1.4 + ε)$ approximation algorithm for this variant, thus showing that strip packing with polynomially bounded data can be approximated better than when exponentially large values in the input data are allowed. Their result has subsequently been improved to a $(4/3 + ε)$ approximation by two independent research groups [FSTTCS 2016, arXiv:1610.04430]. This raises a question whether strip packing with polynomially bounded input data admits a quasi-polynomial time approximation scheme, as is the case for related two-dimensional packing problems like maximum independent set of rectangles or two-dimensional knapsack. In this paper we answer this question in negative by proving that it is NP-hard to approximate strip packing within a factor better than $12/11$, even when admitting only polynomially bounded input data. In particular, this shows that the strip packing problem admits no quasi-polynomial time approximation scheme, unless $\mathrm{NP} \subseteq \mathrm{DTIME}(2^{\mathrm{polylog}(n)})$.
How Document Pre-processing affects Keyphrase Extraction Performance
Venue: arXiv cs.CL 2016
Year: 2016

The SemEval-2010 benchmark dataset has brought renewed attention to the task of automatic keyphrase extraction. This dataset is made up of scientific articles that were automatically converted from PDF format to plain text and thus require careful preprocessing so that irrevelant spans of text do not negatively affect keyphrase extraction performance. In previous work, a wide range of document preprocessing techniques were described but their impact on the overall performance of keyphrase extraction models is still unexplored. Here, we re-assess the performance of several keyphrase extraction models and measure their robustness against increasingly sophisticated levels of document preprocessing.
Maxmin convolutional neural networks for image classification
Venue: arXiv cs.CV 2016
Year: 2016

Convolutional neural networks (CNN) are widely used in computer vision, especially in image classification. However, the way in which information and invariance properties are encoded through in deep CNN architectures is still an open question. In this paper, we propose to modify the standard convo- lutional block of CNN in order to transfer more information layer after layer while keeping some invariance within the net- work. Our main idea is to exploit both positive and negative high scores obtained in the convolution maps. This behav- ior is obtained by modifying the traditional activation func- tion step before pooling. We are doubling the maps with spe- cific activations functions, called MaxMin strategy, in order to achieve our pipeline. Extensive experiments on two classical datasets, MNIST and CIFAR-10, show that our deep MaxMin convolutional net outperforms standard CNN.
Spatio-temporal features of FocusST
Venue: arXiv cs.SE 2016
Year: 2016

In this technical report we summarise the spatio-temporal features and present the core operators of FocusST specification framework. We present the general idea of these operators, using a Steam Boiler System example to illustrate how the specification framework can be applied. FocusST was inspired by Focus, a framework for formal specification and development of interactive systems. In contrast to Focus, FocusST is devoted to specify and to analyse spatial (S) and timing (T) aspects of the systems, which is also reflected in the name of the framework: the extension ST highlights the spatio-temporal nature of the specifications.
Sequence Segmentation Using Joint RNN and Structured Prediction Models
Venue: arXiv cs.CL 2016
Year: 2016

We describe and analyze a simple and effective algorithm for sequence segmentation applied to speech processing tasks. We propose a neural architecture that is composed of two modules trained jointly: a recurrent neural network (RNN) module and a structured prediction model. The RNN outputs are considered as feature functions to the structured model. The overall model is trained with a structured loss function which can be designed to the given segmentation task. We demonstrate the effectiveness of our method by applying it to two simple tasks commonly used in phonetic studies: word segmentation and voice onset time segmentation. Results sug- gest the proposed model is superior to previous methods, ob- taining state-of-the-art results on the tested datasets.
Active User Authentication for Smartphones: A Challenge Data Set and Benchmark Results
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, automated user verification techniques for smartphones are investigated. A unique non-commercial dataset, the University of Maryland Active Authentication Dataset 02 (UMDAA-02) for multi-modal user authentication research is introduced. This paper focuses on three sensors - front camera, touch sensor and location service while providing a general description for other modalities. Benchmark results for face detection, face verification, touch-based user identification and location-based next-place prediction are presented, which indicate that more robust methods fine-tuned to the mobile platform are needed to achieve satisfactory verification accuracy. The dataset will be made available to the research community for promoting additional research.