OpenRaiser/Intern-Atlas huggingface dataset:
On Location Hiding in Distributed Systems
Venue: arXiv cs.MA 2016
Year: 2016

We consider the following problem - a group of mobile agents perform some task on a terrain modeled as a graph. In a given moment of time an adversary gets an access to the graph and positions of the agents. Shortly before adversary's observation the mobile agents have a chance to relocate themselves in order to hide their initial configuration. We assume that the initial configuration may possibly reveal to the adversary some information about the task they performed. Clearly agents have to change their location in possibly short time using minimal energy. In our paper we introduce a definition of a \emph{well hiding} algorithm in which the starting and final configurations of the agents have small mutual information. Then we discuss the influence of various features of the model on the running time of the optimal well-hiding algorithm. We show that if the topology of the graph is known to the agents, then the number of steps proportional to the diameter of the graph is sufficient and necessary. In the unknown topology scenario we only consider a single agent case. We first show that the task is impossible in the deterministic case if the agent has no memory. Then we present a polynomial randomized algorithm. Finally in the model with memory we show that the number of steps proportional to the number of edges of the graph is sufficient and necessary. In some sense we investigate how complex is the problem of "losing" information about location (both physical and logical) for different settings.
Sub-channel and Power Allocation for Non-orthogonal Multiple Access Relay Networks with Amplify-and-Forward Protocol
Venue: arXiv cs.NI 2016
Year: 2016

In this paper, we study the resource allocation problem for a single-cell non-orthogonal multiple access (NOMA) relay network where an OFDM amplify-and-forward (AF) relay allocates the spectrum and power resources to the source-destination (SD) pairs. We aim to optimize the resource allocation to maximize the average sum-rate. The optimal approach requires an exhaustive search, leading to an NP-hard problem. To solve this problem, we propose two efficient many-to-many two-sided SD pair-subchannel matching algorithms in which the SD pairs and sub-channels are considered as two sets of players chasing their own interests. The proposed algorithms can provide a sub-optimal solution to this resource allocation problem in affordable time. Both the static matching algorithm and dynamic matching algorithm converge to a pair-wise stable matching after a limited number of iterations. Simulation results show that the capacity of both proposed algorithms in the NOMA scheme significantly outperforms the conventional orthogonal multiple access scheme. The proposed matching algorithms in NOMA scheme also achieve a better user-fairness performance than the conventional orthogonal multiple access.
Classify or Select: Neural Architectures for Extractive Document Summarization
Venue: arXiv cs.CL 2016
Year: 2016

We present two novel and contrasting Recurrent Neural Network (RNN) based architectures for extractive summarization of documents. The Classifier based architecture sequentially accepts or rejects each sentence in the original document order for its membership in the final summary. The Selector architecture, on the other hand, is free to pick one sentence at a time in any arbitrary order to piece together the summary. Our models under both architectures jointly capture the notions of salience and redundancy of sentences. In addition, these models have the advantage of being very interpretable, since they allow visualization of their predictions broken up by abstract features such as information content, salience and redundancy. We show that our models reach or outperform state-of-the-art supervised models on two different corpora. We also recommend the conditions under which one architecture is superior to the other based on experimental evidence.
`Who would have thought of that!': A Hierarchical Topic Model for Extraction of Sarcasm-prevalent Topics and Sarcasm Detection
Venue: arXiv cs.CL 2016
Year: 2016

Topic Models have been reported to be beneficial for aspect-based sentiment analysis. This paper reports a simple topic model for sarcasm detection, a first, to the best of our knowledge. Designed on the basis of the intuition that sarcastic tweets are likely to have a mixture of words of both sentiments as against tweets with literal sentiment (either positive or negative), our hierarchical topic model discovers sarcasm-prevalent topics and topic-level sentiment. Using a dataset of tweets labeled using hashtags, the model estimates topic-level, and sentiment-level distributions. Our evaluation shows that topics such as `work', `gun laws', `weather' are sarcasm-prevalent topics. Our model is also able to discover the mixture of sentiment-bearing words that exist in a text of a given sentiment-related label. Finally, we apply our model to predict sarcasm in tweets. We outperform two prior work based on statistical classifiers with specific features, by around 25\%.
Automatic discovery of discriminative parts as a quadratic assignment problem
Venue: arXiv cs.CV 2016
Year: 2016

Part-based image classification consists in representing categories by small sets of discriminative parts upon which a representation of the images is built. This paper addresses the question of how to automatically learn such parts from a set of labeled training images. The training of parts is cast as a quadratic assignment problem in which optimal correspondences between image regions and parts are automatically learned. The paper analyses different assignment strategies and thoroughly evaluates them on two public datasets: Willow actions and MIT 67 scenes. State-of-the art results are obtained on these datasets.
Columbia MVSO Image Sentiment Dataset
Venue: arXiv cs.MM 2016
Year: 2016

The Multilingual Visual Sentiment Ontology (MVSO) consists of 15,600 concepts in 12 different languages that are strongly related to emotions and sentiments expressed in images. These concepts are defined in the form of Adjective-Noun Pair (ANP), which are crawled and discovered from online image forum Flickr. In this work, we used Amazon Mechanical Turk as a crowd-sourcing platform to collect human judgments on sentiments expressed in images that are uniformly sampled over 3,911 English ANPs extracted from a tag-restricted subset of MVSO. Our goal is to use the dataset as a benchmark for the evaluation of systems that automatically predict sentiments in images or ANPs.
Real Stable Polynomials and Matroids: Optimization and Counting
Venue: arXiv cs.DS 2016
Year: 2016

A great variety of fundamental optimization and counting problems arising in computer science, mathematics and physics can be reduced to one of the following computational tasks involving polynomials and set systems: given an $m$-variate real polynomial $g$ and a family of subsets $B$ of $[m]$, (1) find $S\in B$ such that the monomial in $g$ corresponding to $S$ has the largest coefficient in $g$, or (2) compute the sum of coefficients of monomials in $g$ corresponding to all the sets in $B$. Special cases of these problems, such as computing permanents, sampling from DPPs and maximizing subdeterminants have been topics of recent interest in theoretical computer science. In this paper we present a general convex programming framework geared to solve both of these problems. We show that roughly, when $g$ is a real stable polynomial with non-negative coefficients and $B$ is a matroid, the integrality gap of our relaxation is finite and depends only on $m$ (and not on the coefficients of g). Prior to our work, such results were known only in sporadic cases that relied on the structure of $g$ and $B$; it was not even clear if one could formulate a convex relaxation that has a finite integrality gap beyond these special cases. Two notable examples are a result by Gurvits on the van der Waerden conjecture for real stable $g$ when $B$ is a single element and a result by Nikolov and Singh for multilinear real stable polynomials when $B$ is a partition matroid. Our work, which encapsulates most interesting cases of $g$ and $B$, benefits from both - we were inspired by the latter in deriving the right convex programming relaxation and the former in establishing the integrality gap. However, proving our results requires significant extensions of both; in that process we come up with new notions and connections between stable polynomials and matroids which should be of independent interest.
Earliness-Aware Deep Convolutional Networks for Early Time Series Classification
Venue: arXiv cs.LG 2016
Year: 2016

We present Earliness-Aware Deep Convolutional Networks (EA-ConvNets), an end-to-end deep learning framework, for early classification of time series data. Unlike most existing methods for early classification of time series data, that are designed to solve this problem under the assumption of the availability of a good set of pre-defined (often hand-crafted) features, our framework can jointly perform feature learning (by learning a deep hierarchy of \emph{shapelets} capturing the salient characteristics in each time series), along with a dynamic truncation model to help our deep feature learning architecture focus on the early parts of each time series. Consequently, our framework is able to make highly reliable early predictions, outperforming various state-of-the-art methods for early time series classification, while also being competitive when compared to the state-of-the-art time series classification algorithms that work with \emph{fully observed} time series data. To the best of our knowledge, the proposed framework is the first to perform data-driven (deep) feature learning in the context of early classification of time series data. We perform a comprehensive set of experiments, on several benchmark data sets, which demonstrate that our method yields significantly better predictions than various state-of-the-art methods designed for early time series classification. In addition to obtaining high accuracies, our experiments also show that the learned deep shapelets based features are also highly interpretable and can help gain better understanding of the underlying characteristics of time series data.
Motion Estimated-Compensated Reconstruction with Preserved-Features in Free-Breathing Cardiac MRI
Venue: arXiv cs.CV 2016
Year: 2016

To develop an efficient motion-compensated reconstruction technique for free-breathing cardiac magnetic resonance imaging (MRI) that allows high-quality images to be reconstructed from multiple undersampled single-shot acquisitions. The proposed method is a joint image reconstruction and motion correction method consisting of several steps, including a non-rigid motion extraction and a motion-compensated reconstruction. The reconstruction includes a denoising with the Beltrami regularization, which offers an ideal compromise between feature preservation and staircasing reduction. Results were assessed in simulation, phantom and volunteer experiments. The proposed joint image reconstruction and motion correction method exhibits visible quality improvement over previous methods while reconstructing sharper edges. Moreover, when the acceleration factor increases, standard methods show blurry results while the proposed method preserves image quality. The method was applied to free-breathing single-shot cardiac MRI, successfully achieving high image quality and higher spatial resolution than conventional segmented methods, with the potential to offer high-quality delayed enhancement scans in challenging patients.
SIR Asymptotics in General Network Models
Venue: arXiv cs.IT 2016
Year: 2016

In the performance analyses of wireless networks, asymptotic quantities and properties often pro- vide useful results and insights. The asymptotic analyses become especially important when complete analytical expressions of the performance metrics of interest are not available, which is often the case if one departs from very specific modeling assumptions. In this paper, we consider the asymptotics of the SIR distribution in general wireless network models, including ad hoc and cellular networks, simple and non-simple point processes, and singular and bounded path loss models, for which, in most cases, finding analytical expressions of the complete SIR distribution seems hopeless. We show that the lower tails of the SIR distributions decay polynomially with the order solely determined by the path loss exponent or the fading parameter, while the upper tails decay exponentially, with the exception of cellular networks with singular path loss. In addition, we analyze the impact of the nearest interferer on the asymptotic properties of the SIR distributions, and we formulate three crisp conjectures that -if true- determine the asymptotic behavior in many cases based on the large-scale path loss properties of the desired signal and/or nearest interferer only.
Feature Extraction and Soft Computing Methods for Aerospace Structure Defect Classification
Venue: arXiv cs.CV 2016
Year: 2016

This study concerns the effectiveness of several techniques and methods of signals processing and data interpretation for the diagnosis of aerospace structure defects. This is done by applying different known feature extraction methods, in addition to a new CBIR-based one; and some soft computing techniques including a recent HPC parallel implementation of the U-BRAIN learning algorithm on Non Destructive Testing data. The performance of the resulting detection systems are measured in terms of Accuracy, Sensitivity, Specificity, and Precision. Their effectiveness is evaluated by the Matthews correlation, the Area Under Curve (AUC), and the F-Measure. Several experiments are performed on a standard dataset of eddy current signal samples for aircraft structures. Our experimental results evidence that the key to a successful defect classifier is the feature extraction method - namely the novel CBIR-based one outperforms all the competitors - and they illustrate the greater effectiveness of the U-BRAIN algorithm and the MLP neural network among the soft computing methods in this kind of application. Keywords- Non-destructive testing (NDT); Soft Computing; Feature Extraction; Classification Algorithms; Content-Based Image Retrieval (CBIR); Eddy Currents (EC).
Steady State Visually Evoked Potentials detection using a single electrode consumer-grade EEG device for BCI applications
Venue: arXiv cs.HC 2016
Year: 2016

Brain-Computer Interfaces (BCIs) implement a direct communication pathway between the brain of an user and an external device, as a computer or a machine in general. One of the most used brain responses to implement non-invasive BCIs is the so called steady-state visually evoked potential (SSVEP). This periodic response is generated when an user gazes to a light flickering at a constant frequency. The SSVEP response can be detected in the user's electroencephalogram (EEG) at the corresponding frequency of the attended flickering stimulus. In SSVEP based BCIs, multiple stimuli, flickering at different frequencies, are commonly presented to the user, where to each stimulus is associated a command for an actuator. One of the limitations to a wider adoption of BCIs is given by the need of EEG acquisition devices and software tools which are commonly not meant for end-user usage. In this work, exploiting state-of-the-art software tools, the use of a low cost easy to wear single electrode EEG device is demonstrated to be exploitable to implement simple SSVEP based BCIs. The obtained results, although less impressive than the ones obtainable with professional EEG equipment, are interesting in view of practical low cost BCI applications meant for end-users.
Multilinear Low-Rank Tensors on Graphs & Applications
Venue: arXiv cs.CV 2016
Year: 2016

We propose a new framework for the analysis of low-rank tensors which lies at the intersection of spectral graph theory and signal processing. As a first step, we present a new graph based low-rank decomposition which approximates the classical low-rank SVD for matrices and multi-linear SVD for tensors. Then, building on this novel decomposition we construct a general class of convex optimization problems for approximately solving low-rank tensor inverse problems, such as tensor Robust PCA. The whole framework is named as 'Multilinear Low-rank tensors on Graphs (MLRTG)'. Our theoretical analysis shows: 1) MLRTG stands on the notion of approximate stationarity of multi-dimensional signals on graphs and 2) the approximation error depends on the eigen gaps of the graphs. We demonstrate applications for a wide variety of 4 artificial and 12 real tensor datasets, such as EEG, FMRI, BCI, surveillance videos and hyperspectral images. Generalization of the tensor concepts to non-euclidean domain, orders of magnitude speed-up, low-memory requirement and significantly enhanced performance at low SNR are the key aspects of our framework.
Lost in Space: Geolocation in Event Data
Venue: arXiv cs.CL 2016
Year: 2016

Extracting the "correct" location information from text data, i.e., determining the place of event, has long been a goal for automated text processing. To approximate human-like coding schema, we introduce a supervised machine learning algorithm that classifies each location word to be either correct or incorrect. We use news articles collected from around the world (Integrated Crisis Early Warning System [ICEWS] data and Open Event Data Alliance [OEDA] data) to test our algorithm that consists of two stages. In the feature selection stage, we extract contextual information from texts, namely, the N-gram patterns for location words, the frequency of mention, and the context of the sentences containing location words. In the classification stage, we use three classifiers to estimate the model parameters in the training set and then to predict whether a location word in the test set news articles is the place of the event. The validation results show that our algorithm improves the accuracy rate of the current geolocation methods of dictionary approach by as much as 25%.
Finite Bases with Respect to the Superposition in Classes of Elementary Recursive Functions, dissertation
Venue: arXiv cs.CC 2016
Year: 2016

This is a thesis that was defended in 2009 at Lomonosov Moscow State University. In Chapter 1: 1. It is proved that that the class of lower (Skolem) elementary functions is the set of all polynomial-bounded functions that can be obtained by a composition of $x+1$, $xy$, $\max(x-y,0)$, $x\wedge y$, $\lfloor x/y \rfloor$, and one exponential function ($2^x$ or $x^y$) using formulas that have no more than 2 floors with respect to an exponent (for example, $(x+y)^{xy+z}+1$ has 2 floors, $2^{2^x}$ has 3 floors). Here $x\wedge y$ is a bitwise AND of $x$ and $y$. 2. It is proved that $\{x+y,\ \max(x-y,0),\ x\wedge y,\ \lfloor x/y \rfloor,\ 2^{\lfloor \log_2 x \rfloor^2}\}$ and $\{x+y,\ \max(x-y,0),\ x\wedge y,\ \lfloor x/y \rfloor,\ x^{\lfloor \log_2 y \rfloor}\}$ are composition bases in the functional version of the uniform $\mathrm{TC}^0$ (also known as $\mathrm{FOM}$). 3. The hierarchy of classes exhausting the class of elementary functions is described in terms of compositions with restrictions on a number of floors in a formula. The results of Chapter 1 are published in: 1) Volkov S.A. An exponential expansion of the Skolem-elementary functions, and bounded superpositions of simple arithmetic functions (in Russian), Mathematical Problems of Cybernetics, Moscow, Fizmatlit, 2007, vol. 16, pp. 163-190 2) doi:10.1134/S1064562407040217 In Chapter 2 a simple composition basis in the class ${\cal E}^2$ of Grzegorczyk hierarchy is described. This result is published in DOI: 10.1515/156939206779238436 In Chapter 3 it is proved that the group of permutations $\mathrm{Gr}(Q)=\{f:\ f,f^{-1}\in Q\}$ is generated by two permutations for many classes $Q$. For example, this is proved for $Q=\mathrm{FP}$, where $\mathrm{FP}$ is the class of all polynomial-time computable functions (of the length of input). The results of chapter 3 are published in DOI: 10.1515/DMA.2008.046
Performance Analysis of Partial Interference Cancellation in Multi-Antenna UDNs
Venue: arXiv cs.IT 2016
Year: 2016

The employment of partial zero-forcing (PZF) receivers at the base stations represents an efficient and low-complexity technique for uplink interference management in cellular networks. In this paper, we focus on the performance analysis of ultra-dense networks (UDNs) in which the multi-antenna receivers adopt PZF. We provide both integral expressions and tight closed-form approximations for the probability of successful transmission, which can be used to accurately evaluate the optimal tradeoff between interference cancellation and array gain. Numerical results show that no more than half of the available degrees of freedom should be used for interference cancellation.
Light Field Stitching for Extended Synthetic Aperture
Venue: arXiv cs.CV 2016
Year: 2016

Through capturing spatial and angular radiance distribution, light field cameras introduce new capabilities that are not possible with conventional cameras. So far in the light field imaging literature, the focus has been on the theory and applications of single light field capture. By combining multiple light fields, it is possible to obtain new capabilities and enhancements, and even exceed physical limitations, such as spatial resolution and aperture size of the imaging device. In this paper, we present an algorithm to register and stitch multiple light fields. We utilize the regularity of the spatial and angular sampling in light field data, and extend some techniques developed for stereo vision systems to light field data. Such an extension is not straightforward for a micro-lens array (MLA) based light field camera due to extremely small baseline and low spatial resolution. By merging multiple light fields captured by an MLA based camera, we obtain larger synthetic aperture, which results in improvements in light field capabilities, such as increased depth estimation range/accuracy and wider perspective shift range.
Extensive-Form Perfect Equilibrium Computation in Two-Player Games
Venue: arXiv cs.GT 2016
Year: 2016

We study the problem of computing an Extensive-Form Perfect Equilibrium (EFPE) in 2-player games. This equilibrium concept refines the Nash equilibrium requiring resilience w.r.t. a specific vanishing perturbation (representing mistakes of the players at each decision node). The scientific challenge is intrinsic to the EFPE definition: it requires a perturbation over the agent form, but the agent form is computationally inefficient, due to the presence of highly nonlinear constraints. We show that the sequence form can be exploited in a non-trivial way and that, for general-sum games, finding an EFPE is equivalent to solving a suitably perturbed linear complementarity problem. We prove that Lemke's algorithm can be applied, showing that computing an EFPE is $\textsf{PPAD}$-complete. In the notable case of zero-sum games, the problem is in $\textsf{FP}$ and can be solved by linear programming. Our algorithms also allow one to find a Nash equilibrium when players cannot perfectly control their moves, being subject to a given execution uncertainty, as is the case in most realistic physical settings.
On Threshold Routing in a Service System with Highest-Bidder-First and FIFO Services
Venue: arXiv cs.GT 2016
Year: 2016

In this paper, we consider a two server system serving heterogeneous customers. One of the server has a FIFO scheduling policy and charges a fixed admission price to each customer. The second queue follows the highest-bidder-first (HBF) policy where an arriving customer bids for its position in the queue. Customers make an individually optimal choice of the server and for such system, we characterize the equilibrium routing of customers. We specifically show that this routing is characterized by two thresholds.