OpenRaiser/Intern-Atlas huggingface dataset:
A note on Thue games
Venue: arXiv cs.DM 2016
Year: 2016

In this work we improve on a result from~\cite{GryKosZma15}. In particular, we investigate the situation where a word is constructed jointly by two players who alternately append letters to the end of an existing word. One of the players (Ann) tries to avoid (non-trivial) repetitions, while the other one (Ben) tries to enforce them. We show a construction that is closer to the lower bound showed in~\cite{GryKozMic13} using entropy compression, and building on the probabilistic arguments based on a version of the Lovász Local Lemma from~\cite{Peg11}. We provide an explicit strategy for Ann to avoid (non-trivial) repetitions over a $7$-letter alphabet.
Approximation algorithms for node-weighted prize-collecting Steiner tree problems on planar graphs
Venue: arXiv cs.DS 2016
Year: 2016

We study the prize-collecting version of the Node-weighted Steiner Tree problem (NWPCST) restricted to planar graphs. We give a new primal-dual Lagrangian-multiplier-preserving (LMP) 3-approximation algorithm for planar NWPCST. We then show a ($2.88 + ε$)-approximation which establishes a new best approximation guarantee for planar NWPCST. This is done by combining our LMP algorithm with a threshold rounding technique and utilizing the 2.4-approximation of Berman and Yaroslavtsev for the version without penalties. We also give a primal-dual 4-approximation algorithm for the more general forest version using techniques introduced by Hajiaghay and Jain.
Basic Reasoning with Tensor Product Representations
Venue: arXiv cs.AI 2016
Year: 2016

In this paper we present the initial development of a general theory for mapping inference in predicate logic to computation over Tensor Product Representations (TPRs; Smolensky (1990), Smolensky & Legendre (2006)). After an initial brief synopsis of TPRs (Section 0), we begin with particular examples of inference with TPRs in the 'bAbI' question-answering task of Weston et al. (2015) (Section 1). We then present a simplification of the general analysis that suffices for the bAbI task (Section 2). Finally, we lay out the general treatment of inference over TPRs (Section 3). We also show the simplification in Section 2 derives the inference methods described in Lee et al. (2016); this shows how the simple methods of Lee et al. (2016) can be formally extended to more general reasoning tasks.
Bounds and Constructions of Codes with Multiple Localities
Venue: arXiv cs.IT 2016
Year: 2016

This paper studies bounds and constructions of locally repairable codes (LRCs) with multiple localities so-called multiple-locality LRCs (ML-LRCs). In the simplest case of two localities some code symbols of an ML-LRC have a certain locality while the remaining code symbols have another one. We extend two bounds, the Singleton and the alphabet-dependent upper bound on the dimension of Cadambe--Mazumdar for LRCs, to the case of ML-LRCs with more than two localities. Furthermore, we construct Singleton-optimal ML-LRCs as well as codes that achieve the extended alphabet-dependent bound. We give a family of binary ML-LRCs based on generalized code concatenation that is optimal with respect to the alphabet-dependent bound.
Learning Hidden Unit Contributions for Unsupervised Acoustic Model Adaptation
Venue: arXiv cs.CL 2016
Year: 2016

This work presents a broad study on the adaptation of neural network acoustic models by means of learning hidden unit contributions (LHUC) -- a method that linearly re-combines hidden units in a speaker- or environment-dependent manner using small amounts of unsupervised adaptation data. We also extend LHUC to a speaker adaptive training (SAT) framework that leads to a more adaptable DNN acoustic model, working both in a speaker-dependent and a speaker-independent manner, without the requirements to maintain auxiliary speaker-dependent feature extractors or to introduce significant speaker-dependent changes to the DNN structure. Through a series of experiments on four different speech recognition benchmarks (TED talks, Switchboard, AMI meetings, and Aurora4) comprising 270 test speakers, we show that LHUC in both its test-only and SAT variants results in consistent word error rate reductions ranging from 5% to 23% relative depending on the task and the degree of mismatch between training and test data. In addition, we have investigated the effect of the amount of adaptation data per speaker, the quality of unsupervised adaptation targets, the complementarity to other adaptation techniques, one-shot adaptation, and an extension to adapting DNNs trained in a sequence discriminative manner.
Invariance to ordinal transformations in rank-aware databases
Venue: arXiv cs.DB 2016
Year: 2016

We study influence of ordinal transformations on results of queries in rank-aware databases which derive their operations with ranked relations from totally ordered structures of scores with infima acting as aggregation functions. We introduce notions of ordinal containment and equivalence of ranked relations and prove that infima-based algebraic operations with ranked relations are invariant to ordinal transformations: Queries applied to original and transformed data yield results which are equivalent in terms of the order given by scores, meaning that top-k results of queries remain the same. We show this important property is preserved in alternative query systems based of relational calculi developed in context of Gödel logic. We comment on relationship to monotone query evaluation and show that the results can be attained in alternative rank-aware approaches.
Social Network Extraction: Superficial Method and Information Retrieval
Venue: arXiv cs.IR 2016
Year: 2016

Social network has become one of the themes of government issues, mainly dealing with the chaos. The use of web is steadily gaining ground in these issues. However, most of the web documents are unstructured and lack of semantic. In this paper we proposed an Information Retrieval driven method for dealing with heterogeneity of features in the web. The proposed solution is to compare some approaches have shown the capacity to extract social relation: strength relations and relations based on online academic database.
The minimal hitting set generation problem: algorithms and computation
Venue: arXiv cs.DS 2016
Year: 2016

Finding inclusion-minimal "hitting sets" for a given collection of sets is a fundamental combinatorial problem with applications in domains as diverse as Boolean algebra, computational biology, and data mining. Much of the algorithmic literature focuses on the problem of *recognizing* the collection of minimal hitting sets; however, in many of the applications, it is more important to *generate* these hitting sets. We survey twenty algorithms from across a variety of domains, considering their history, classification, useful features, and computational performance on a variety of synthetic and real-world inputs. We also provide a suite of implementations of these algorithms with a ready-to-use, platform-agnostic interface based on Docker containers and the AlgoRun framework, so that interested computational scientists can easily perform similar tests with inputs from their own research areas on their own computers or through a convenient Web interface.
Superregular matrices and applications to convolutional codes
Venue: arXiv cs.IT 2016
Year: 2016

The main results of this paper are twofold: the first one is a matrix theoretical result. We say that a matriz is superregular if all of its minors that are not trivially zero are nonzero. Given a a times b, a larger than or equal to b, superregular matrix over a field, we show that if all of its rows are nonzero then any linear combination of its columns, with nonzero coefficients, has at least a-b+1 nonzero entries. Secondly, we make use of this result to construct convolutional codes that attain the maximum possible distance for some fixed parameters of the code, namely, the rate and the Forney indices. These results answer some open questions on distances and constructions of convolutional codes posted in the literature.
Indicators of Good Student Performance in Moodle Activity Data
Venue: arXiv cs.CY 2016
Year: 2016

In this paper we conduct an analysis of Moodle activity data focused on identifying early predictors of good student performance. The analysis shows that three relevant hypotheses are largely supported by the data. These hypotheses are: early submission is a good sign, a high level of activity is predictive of good results and evening activity is even better than daytime activity. We highlight some pathological examples where high levels of activity correlates with bad results.
Riemannian geometry applied to detection of respiratory states from EEG signals: the basis for a brain-ventilator interface
Venue: arXiv cs.HC 2016
Year: 2016

During mechanical ventilation, patient-ventilator disharmony is frequently observed and may result in increased breathing effort, compromising the patient's comfort and recovery. This circumstance requires clinical intervention and becomes challenging when verbal communication is difficult. In this work, we propose a brain computer interface (BCI) to automatically and non-invasively detect patient-ventilator disharmony from electroencephalographic (EEG) signals: a brain-ventilator interface (BVI). Our framework exploits the cortical activation provoked by the inspiratory compensation when the subject and the ventilator are desynchronized. Use of a one-class approach and Riemannian geometry of EEG covariance matrices allows effective classification of respiratory states. The BVI is validated on nine healthy subjects that performed different respiratory tasks that mimic a patient-ventilator disharmony. Classification performances, in terms of areas under ROC curves, are significantly improved using EEG signals compared to detection based on air flow. Reduction in the number of electrodes that can achieve discrimination can often be desirable (e.g. for portable BCI systems). By using an iterative channel selection technique, the Common Highest Order Ranking (CHOrRa), we find that a reduced set of electrodes (n=6) can slightly improve for an intra-subject configuration, and it still provides fairly good performances for a general inter-subject setting. Results support the discriminant capacity of our approach to identify anomalous respiratory states, by learning from a training set containing only normal respiratory epochs. The proposed framework opens the door to brain-ventilator interfaces for monitoring patient's breathing comfort and adapting ventilator parameters to patient respiratory needs.
Analytical Modeling of Interference Aware Power Control for the Uplink of Heterogeneous Cellular Networks
Venue: arXiv cs.IT 2016
Year: 2016

Inter-cell interference is one of the main limiting factors in current Heterogeneous Cellular Networks (HCNs). Uplink Fractional Power Control (FPC) is a well known method that aims to cope with such limiting factor as well as to save battery live. In order to do that, the path losses associated with Mobile Terminal (MT) transmissions are partially compensated so that a lower interference is leaked towards neighboring cells. Classical FPC techniques only consider a set of parameters that depends on the own MT transmission, like desired received power at the Base Station (BS) or the path loss between the MT and its serving BS, among others. Contrary to classical FPC, in this paper we use stochastic geometry to analyze a power control mechanism that keeps the interference generated by each MT under a given threshold. We also consider a maximum transmitted power and a partial compensation of the path loss. Interestingly, our analysis reveals that such Interference Aware (IA) method can reduce the average power consumption and increase the average spectral efficiency. Additionally, the variance of the interference is reduced, thus improving the performance of Adaptive Modulation and Coding (AMC) since the interference can be better estimated at the MT.
Type Soundness for Path Polymorphism
Venue: arXiv cs.LO 2016
Year: 2016

Path polymorphism is the ability to define functions that can operate uniformly over arbitrary recursively specified data structures. Its essence is captured by patterns of the form $x\,y$ which decompose a compound data structure into its parts. Typing these kinds of patterns is challenging since the type of a compound should determine the type of its components. We propose a static type system (i.e. no run-time analysis) for a pattern calculus that captures this feature. Our solution combines type application, constants as types, union types and recursive types. We address the fundamental properties of Subject Reduction and Progress that guarantee a well-behaved dynamics. Both these results rely crucially on a notion of pattern compatibility and also on a coinductive characterisation of subtyping.
Predicting the Effectiveness of Self-Training: Application to Sentiment Classification
Venue: arXiv cs.CL 2016
Year: 2016

The goal of this paper is to investigate the connection between the performance gain that can be obtained by selftraining and the similarity between the corpora used in this approach. Self-training is a semi-supervised technique designed to increase the performance of machine learning algorithms by automatically classifying instances of a task and adding these as additional training material to the same classifier. In the context of language processing tasks, this training material is mostly an (annotated) corpus. Unfortunately self-training does not always lead to a performance increase and whether it will is largely unpredictable. We show that the similarity between corpora can be used to identify those setups for which self-training can be beneficial. We consider this research as a step in the process of developing a classifier that is able to adapt itself to each new test corpus that it is presented with.
Document image classification, with a specific view on applications of patent images
Venue: arXiv cs.CV 2016
Year: 2016

The main focus of this paper is document image classification and retrieval, where we analyze and compare different parameters for the RunLeght Histogram (RL) and Fisher Vector (FV) based image representations. We do an exhaustive experimental study using different document image datasets, including the MARG benchmarks, two datasets built on customer data and the images from the Patent Image Classification task of the Clef-IP 2011. The aim of the study is to give guidelines on how to best choose the parameters such that the same features perform well on different tasks. As an example of such need, we describe the Image-based Patent Retrieval task's of Clef-IP 2011, where we used the same image representation to predict the image type and retrieve relevant patents.
Political Speech Generation
Venue: arXiv cs.CL 2016
Year: 2016

In this report we present a system that can generate political speeches for a desired political party. Furthermore, the system allows to specify whether a speech should hold a supportive or opposing opinion. The system relies on a combination of several state-of-the-art NLP methods which are discussed in this report. These include n-grams, Justeson & Katz POS tag filter, recurrent neural networks, and latent Dirichlet allocation. Sequences of words are generated based on probabilities obtained from two underlying models: A language model takes care of the grammatical correctness while a topic model aims for textual consistency. Both models were trained on the Convote dataset which contains transcripts from US congressional floor debates. Furthermore, we present a manual and an automated approach to evaluate the quality of generated speeches. In an experimental evaluation generated speeches have shown very high quality in terms of grammatical correctness and sentence transitions.
A Score-level Fusion Method for Eye Movement Biometrics
Venue: arXiv cs.CV 2016
Year: 2016

This paper proposes a novel framework for the use of eye movement patterns for biometric applications. Eye movements contain abundant information about cognitive brain functions, neural pathways, etc. In the proposed method, eye movement data is classified into fixations and saccades. Features extracted from fixations and saccades are used by a Gaussian Radial Basis Function Network (GRBFN) based method for biometric authentication. A score fusion approach is adopted to classify the data in the output layer. In the evaluation stage, the algorithm has been tested using two types of stimuli: random dot following on a screen and text reading. The results indicate the strength of eye movement pattern as a biometric modality. The algorithm has been evaluated on BioEye 2015 database and found to outperform all the other methods. Eye movements are generated by a complex oculomotor plant which is very hard to spoof by mechanical replicas. Use of eye movement dynamics along with iris recognition technology may lead to a robust counterfeit-resistant person identification system.
Identifier Namespaces in Mathematical Notation
Venue: arXiv cs.IR 2016
Year: 2016

In this thesis, we look at the problem of assigning each identifier of a document to a namespace. At the moment, there does not exist a special dataset where all identifiers are grouped to namespaces, and therefore we need to create such a dataset ourselves. To do that, we need to find groups of documents that use identifiers in the same way. This can be done with cluster analysis methods. We argue that documents can be represented by the identifiers they contain, and this approach is similar to representing textual information in the Vector Space Model. Because of this, we can apply traditional document clustering techniques for namespace discovery. Because the problem is new, there is no gold standard dataset, and it is hard to evaluate the performance of our method. To overcome it, we first use Java source code as a dataset for our experiments, since it contains the namespace information. We verify that our method can partially recover namespaces from source code using only information about identifiers. The algorithms are evaluated on the English Wikipedia, and the proposed method can extract namespaces on a variety of topics. After extraction, the namespaces are organized into a hierarchical structure by using existing classification schemes such as MSC, PACS and ACM. We also apply it to the Russian Wikipedia, and the results are consistent across the languages. To our knowledge, the problem of introducing namespaces to mathematics has not been studied before, and prior to our work there has been no dataset where identifiers are grouped into namespaces. Thus, our result is not only a good start, but also a good indicator that automatic namespace discovery is possible.
The complexity of bit retrieval
Venue: arXiv cs.DS 2016
Year: 2016

Bit retrieval is the problem of reconstructing a binary sequence from its periodic autocorrelation, with applications in cryptography and x-ray crystallography. After defining the problem, with and without noise, we describe and compare various algorithms for solving it. A geometrical constraint satisfaction algorithm, relaxed-reflect-reflect, is currently the best algorithm for noisy bit retrieval.
Quantification of Ultrasonic Texture heterogeneity via Volumetric Stochastic Modeling for Tissue Characterization
Venue: arXiv cs.CV 2016
Year: 2016

Intensity variations in image texture can provide powerful quantitative information about physical properties of biological tissue. However, tissue patterns can vary according to the utilized imaging system and are intrinsically correlated to the scale of analysis. In the case of ultrasound, the Nakagami distribution is a general model of the ultrasonic backscattering envelope under various scattering conditions and densities where it can be employed for characterizing image texture, but the subtle intra-heterogeneities within a given mass are difficult to capture via this model as it works at a single spatial scale. This paper proposes a locally adaptive 3D multi-resolution Nakagami-based fractal feature descriptor that extends Nakagami-based texture analysis to accommodate subtle speckle spatial frequency tissue intensity variability in volumetric scans. Local textural fractal descriptors - which are invariant to affine intensity changes - are extracted from volumetric patches at different spatial resolutions from voxel lattice-based generated shape and scale Nakagami parameters. Using ultrasound radio-frequency datasets we found that after applying an adaptive fractal decomposition label transfer approach on top of the generated Nakagami voxels, tissue characterization results were superior to the state of art. Experimental results on real 3D ultrasonic pre-clinical and clinical datasets suggest that describing tumor intra-heterogeneity via this descriptor may facilitate improved prediction of therapy response and disease characterization.
Smoothing parameter estimation framework for IBM word alignment models
Venue: arXiv cs.CL 2016
Year: 2016

IBM models are very important word alignment models in Machine Translation. Following the Maximum Likelihood Estimation principle to estimate their parameters, the models will easily overfit the training data when the data are sparse. While smoothing is a very popular solution in Language Model, there still lacks studies on smoothing for word alignment. In this paper, we propose a framework which generalizes the notable work Moore [2004] of applying additive smoothing to word alignment models. The framework allows developers to customize the smoothing amount for each pair of word. The added amount will be scaled appropriately by a common factor which reflects how much the framework trusts the adding strategy according to the performance on data. We also carefully examine various performance criteria and propose a smoothened version of the error count, which generally gives the best result.
MIMO Architectures for Efficient Communication in Space
Venue: arXiv cs.IT 2016
Year: 2016

The characteristics of a space-to-space multiple-input, multiple-output (MIMO) communication channel that distinguish it from terrestrial MIMO communication channels are summarized and discussed primarily from an information-theoretic viewpoint. The implications of these characteristics for the design and application of future space-based communication systems are also discussed, and it is shown that in general, either energy-efficient or spectrally-efficient communication in space can only be achieved using a distributed MIMO architecture.
Super-Resolution of Complex Exponentials from Modulations with Unknown Waveforms
Venue: arXiv cs.IT 2016
Year: 2016

Super-resolution is generally referred to as the task of recovering fine details from coarse information. Motivated by applications such as single-molecule imaging, radar imaging, etc., we consider parameter estimation of complex exponentials from their modulations with unknown waveforms, allowing for non-stationary blind super-resolution. This problem, however, is ill-posed since both the parameters associated with the complex exponentials and the modulating waveforms are unknown. To alleviate this, we assume that the unknown waveforms live in a common low-dimensional subspace. Using a lifting trick, we recast the blind super-resolution problem as a structured low-rank matrix recovery problem. Atomic norm minimization is then used to enforce the structured low-rankness, and is reformulated as a semidefinite program that is solvable in polynomial time. We show that, up to scaling ambiguities, exact recovery of both of the complex exponential parameters and the unknown waveforms is possible when the waveform subspace is random and the number of measurements is proportional to the number of degrees of freedom in the problem. Numerical simulations support our theoretical findings, showing that non-stationary blind super-resolution using atomic norm minimization is possible.