OpenRaiser/Intern-Atlas huggingface dataset:
Compatibility of Mating Preferences
Venue: arXiv cs.CY 2016
Year: 2016

Human mating is a complex phenomenon. Although men and women have different preferences in mate selection, there should be compatibility in these preferences since human mating requires agreement of both parties. We investigate how compatible the mating preferences of men and women are in a given property such as age, height, education and income. We use dataset of a large online dating site (N = 44, 255 users). (i) Our findings are based on the "actual behavior" of users trying to find a date online, rather than questions about a "hypothetical" partner as in surveys. (ii) We confirm that women and men have different mating preferences. Women prefer taller and older men with better education and higher income then themselves. Men prefer just the opposite. (iii) Our findings indicate that these differences complement each other. (iv) Highest compatibility is observed in income with 95 %. This might be an indication that income is in the process of becoming more important than other properties, including age, in our modern society. (v) An evolutionary model is developed which produces similar results.
Eilenberg theorems for many-sorted formations
Venue: arXiv cs.FL 2016
Year: 2016

A theorem of Eilenberg establishes that there exists a bijection between the set of all varieties of regular languages and the set of all varieties of finite monoids. In this article after defining, for a fixed set of sorts $S$ and a fixed $S$-sorted signature $Σ$, the concepts of formation of congruences with respect to $Σ$ and of formation of $Σ$-algebras, we prove that the algebraic lattices of all $Σ$-congruence formations and of all $Σ$-algebra formations are isomorphic, which is an Eilenberg's type theorem. Moreover, under a suitable condition on the free $Σ$-algebras and after defining the concepts of formation of congruences of finite index with respect to $Σ$, of formation of finite $Σ$-algebras, and of formation of regular languages with respect to $Σ$, we prove that the algebraic lattices of all $Σ$-finite index congruence formations, of all $Σ$-finite algebra formations, and of all $Σ$-regular language formations are isomorphic, which is also an Eilenberg's type theorem.
Secrecy Capacity in Large Cooperative Networks in Presence of Eavesdroppers with Unknown Locations
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, an extended large wireless network under the secrecy constraint is considered. In contrast to works which use idealized assumptions, a more realistic network situation with unknown eavesdroppers locations is investigated: the legitimate users only know their own Channel State Information (CSI), not the eavesdroppers CSI. Also, the network is analyzed by taking in to account the effects of both fading and path loss. Under these assumptions, a power efficient cooperative scheme, named \emph{stochastic virtual beamforming}, is proposed. Applying this scheme, an unbounded secure rate with any desired outage level is achieved, provided that the density of the legitimate users tends to infinity. In addition, by tending the legitimate users density to the infinity, the tolerable density of eavesdroppers will become unbounded too.
An Initial Seed Selection Algorithm for K-means Clustering of Georeferenced Data to Improve Replicability of Cluster Assignments for Mapping Application
Venue: arXiv cs.LG 2016
Year: 2016

K-means is one of the most widely used clustering algorithms in various disciplines, especially for large datasets. However the method is known to be highly sensitive to initial seed selection of cluster centers. K-means++ has been proposed to overcome this problem and has been shown to have better accuracy and computational efficiency than k-means. In many clustering problems though -such as when classifying georeferenced data for mapping applications- standardization of clustering methodology, specifically, the ability to arrive at the same cluster assignment for every run of the method i.e. replicability of the methodology, may be of greater significance than any perceived measure of accuracy, especially when the solution is known to be non-unique, as in the case of k-means clustering. Here we propose a simple initial seed selection algorithm for k-means clustering along one attribute that draws initial cluster boundaries along the 'deepest valleys' or greatest gaps in dataset. Thus, it incorporates a measure to maximize distance between consecutive cluster centers which augments the conventional k-means optimization for minimum distance between cluster center and cluster members. Unlike existing initialization methods, no additional parameters or degrees of freedom are introduced to the clustering algorithm. This improves the replicability of cluster assignments by as much as 100% over k-means and k-means++, virtually reducing the variance over different runs to zero, without introducing any additional parameters to the clustering process. Further, the proposed method is more computationally efficient than k-means++ and in some cases, more accurate.
Role of a Relay in Bursty Multiple Access Channels
Venue: arXiv cs.IT 2016
Year: 2016

We investigate the role of a relay in multiple access channels (MACs) with bursty user traffic, where intermittent data traffic restricts the users to bursty transmissions. As our main result, we characterize the degrees of freedom (DoF) region of a $K$-user bursty multi-input multi-output (MIMO) Gaussian MAC with a relay, where Bernoulli random states are introduced to govern bursty user transmissions. To that end, we extend the noisy network coding scheme to achieve the cut-set bound. Our main contribution is in exploring the role of a relay from various perspectives. First, we show that a relay can provide a DoF gain in bursty channels, unlike in conventional non-bursty channels. Interestingly, we find that the relaying gain can scale with additional antennas at the relay to some extent. Moreover, observing that a relay can help achieve collision-free performances, we establish the necessary and sufficient condition for attaining collision-free DoF. Lastly, we consider scenarios in which some physical perturbation shared around the users may generate data traffic simultaneously, causing transmission patterns across them to be correlated. We demonstrate that for most cases in such scenarios, the relaying gain is greater when the users' transmission patterns are more correlated, hence when more severe collisions take place. Our results have practical implications in various scenarios of wireless networks such as device-to-device systems and random media access control protocols.
Routing and Sorting Via Matchings On Graphs
Venue: arXiv cs.DM 2016
Year: 2016

The paper is divided in to two parts. In the first part we present some new results for the \textit{routing via matching} model introduced by Alon et al\cite{5}. This model can be viewed as a communication scheme on a distributed network. The nodes in the network can communicate via matchings (a step), where a node exchanges data with its partner. Formally, given a connected graph $G$ with vertices labeled from $[1,...,n]$ and a permutation $π$ giving the destination of pebbles on the vertices the problem is to find a minimum step routing scheme. This is denoted as the routing time $rt(G,π)$ of $G$ given $π$. In this paper we present the following new results, which answer one of the open problems posed in \cite{5}: 1) Determining whether $rt(G,π)$ is $\le 2$ can be done in $O(n^{2.5})$ deterministic time for any arbitrary connected graph $G$. 2) Determining whether $rt(G,π)$ is $\le k$ for any $k \ge 3$ is NP-Complete. In the second part we study a related property of graphs, which measures how easy it is to design sorting networks using only the edges of a given graph. Informally, \textit{sorting number} of a graph is the minimum depth sorting network that only uses edges of the graph. Many of the classical results on sorting networks can be represented in this framework. We show that a tree with maximum degree $Δ$ can accommodate a $O(\min(nΔ^2,n^2))$ depth sorting network. Additionally, we give two instance of trees for which this bound is tight.
Prediction-error of Prediction Error (PPE)-based Reversible Data Hiding
Venue: arXiv cs.MM 2016
Year: 2016

This paper presents a novel reversible data hiding (RDH) algorithm for gray-scaled images, in which the prediction-error of prediction error (PPE) of a pixel is used to carry the secret data. In the proposed method, the pixels to be embedded are firstly predicted with their neighboring pixels to obtain the corresponding prediction errors (PEs). Then, by exploiting the PEs of the neighboring pixels, the prediction of the PEs of the pixels can be determined. And, a sorting technique based on the local complexity of a pixel is used to collect the PPEs to generate an ordered PPE sequence so that, smaller PPEs will be processed first for data embedding. By reversibly shifting the PPE histogram (PPEH) with optimized parameters, the pixels corresponding to the altered PPEH bins can be finally modified to carry the secret data. Experimental results have implied that the proposed method can benefit from the prediction procedure of the PEs, sorting technique as well as parameters selection, and therefore outperform some state-of-the-art works in terms of payload-distortion performance when applied to different images.
A Search/Crawl Framework for Automatically Acquiring Scientific Documents
Venue: arXiv cs.IR 2016
Year: 2016

Despite the advancements in search engine features, ranking methods, technologies, and the availability of programmable APIs, current-day open-access digital libraries still rely on crawl-based approaches for acquiring their underlying document collections. In this paper, we propose a novel search-driven framework for acquiring documents for scientific portals. Within our framework, publicly-available research paper titles and author names are used as queries to a Web search engine. Next, research papers and sources of research papers are identified from the search results using accurate classification modules. Our experiments highlight not only the performance of our individual classifiers but also the effectiveness of our overall Search/Crawl framework. Indeed, we were able to obtain approximately 0.665 million research documents through our fully-automated framework using about 0.076 million queries. These prolific results position Web search as an effective alternative to crawl methods for acquiring both the actual documents and seed URLs for future crawls.
Forecasting Volatility in Indian Stock Market using Artificial Neural Network with Multiple Inputs and Outputs
Venue: arXiv cs.NE 2016
Year: 2016

Volatility in stock markets has been extensively studied in the applied finance literature. In this paper, Artificial Neural Network models based on various back propagation algorithms have been constructed to predict volatility in the Indian stock market through volatility of NIFTY returns and volatility of gold returns. This model considers India VIX, CBOE VIX, volatility of crude oil returns (CRUDESDR), volatility of DJIA returns (DJIASDR), volatility of DAX returns (DAXSDR), volatility of Hang Seng returns (HANGSDR) and volatility of Nikkei returns (NIKKEISDR) as predictor variables. Three sets of experiments have been performed over three time periods to judge the effectiveness of the approach.
Normative Multiagent Systems: A Dynamic Generalization
Venue: arXiv cs.AI 2016
Year: 2016

Social norms are powerful formalism in coordinating autonomous agents' behaviour to achieve certain objectives. In this paper, we propose a dynamic normative system to enable the reasoning of the changes of norms under different circumstances, which cannot be done in the existing static normative systems. We study two important problems (norm synthesis and norm recognition) related to the autonomy of the entire system and the agents, and characterise the computational complexities of solving these problems.
A Repeated Signal Difference for Recognising Patterns
Venue: arXiv cs.NE 2016
Year: 2016

This paper describes a new mechanism that might help with defining pattern sequences, by the fact that it can produce an upper bound on the ensemble value that can persistently oscillate with the actual values produced from each pattern. With every firing event, a node also receives an on/off feedback switch. If the node fires, then it sends a feedback result depending on the input signal strength. If the input signal is positive or larger, it can store an 'on' switch feedback for the next iteration. If the signal is negative or smaller, it can store an 'off' switch feedback for the next iteration. If the node does not fire, then it does not affect the current feedback situation and receives the switch command produced by the last active pattern event for the same neuron. The upper bound therefore also represents the largest or most enclosing pattern set and the lower value is for the actual set of firing patterns. If the pattern sequence repeats, it will oscillate between the two values, allowing them to be recognised and measured more easily, over time. Tests show that changing the sequence ordering produces different value sets, which can also be measured.
Inductive Coherence
Venue: arXiv cs.AI 2016
Year: 2016

While probability theory is normally applied to external environments, there has been some recent interest in probabilistic modeling of the outputs of computations that are too expensive to run. Since mathematical logic is a powerful tool for reasoning about computer programs, we consider this problem from the perspective of integrating probability and logic. Recent work on assigning probabilities to mathematical statements has used the concept of coherent distributions, which satisfy logical constraints such as the probability of a sentence and its negation summing to one. Although there are algorithms which converge to a coherent probability distribution in the limit, this yields only weak guarantees about finite approximations of these distributions. In our setting, this is a significant limitation: Coherent distributions assign probability one to all statements provable in a specific logical theory, such as Peano Arithmetic, which can prove what the output of any terminating computation is; thus, a coherent distribution must assign probability one to the output of any terminating computation. To model uncertainty about computations, we propose to work with approximations to coherent distributions. We introduce inductive coherence, a strengthening of coherence that provides appropriate constraints on finite approximations, and propose an algorithm which satisfies this criterion.
Learning Sparse Additive Models with Interactions in High Dimensions
Venue: arXiv cs.LG 2016
Year: 2016

A function $f: \mathbb{R}^d \rightarrow \mathbb{R}$ is referred to as a Sparse Additive Model (SPAM), if it is of the form $f(\mathbf{x}) = \sum_{l \in \mathcal{S}}ϕ_{l}(x_l)$, where $\mathcal{S} \subset [d]$, $|\mathcal{S}| \ll d$. Assuming $ϕ_l$'s and $\mathcal{S}$ to be unknown, the problem of estimating $f$ from its samples has been studied extensively. In this work, we consider a generalized SPAM, allowing for second order interaction terms. For some $\mathcal{S}_1 \subset [d], \mathcal{S}_2 \subset {[d] \choose 2}$, the function $f$ is assumed to be of the form: $$f(\mathbf{x}) = \sum_{p \in \mathcal{S}_1}ϕ_{p} (x_p) + \sum_{(l,l^{\prime}) \in \mathcal{S}_2}ϕ_{(l,l^{\prime})} (x_{l},x_{l^{\prime}}).$$ Assuming $ϕ_{p},ϕ_{(l,l^{\prime})}$, $\mathcal{S}_1$ and, $\mathcal{S}_2$ to be unknown, we provide a randomized algorithm that queries $f$ and exactly recovers $\mathcal{S}_1,\mathcal{S}_2$. Consequently, this also enables us to estimate the underlying $ϕ_p, ϕ_{(l,l^{\prime})}$. We derive sample complexity bounds for our scheme and also extend our analysis to include the situation where the queries are corrupted with noise -- either stochastic, or arbitrary but bounded. Lastly, we provide simulation results on synthetic data, that validate our theoretical findings.
Text-based LSTM networks for Automatic Music Composition
Venue: arXiv cs.AI 2016
Year: 2016

In this paper, we introduce new methods and discuss results of text-based LSTM (Long Short-Term Memory) networks for automatic music composition. The proposed network is designed to learn relationships within text documents that represent chord progressions and drum tracks in two case studies. In the experiments, word-RNNs (Recurrent Neural Networks) show good results for both cases, while character-based RNNs (char-RNNs) only succeed to learn chord progressions. The proposed system can be used for fully automatic composition or as semi-automatic systems that help humans to compose music by controlling a diversity parameter of the model.
Clustering Comparable Corpora of Russian and Ukrainian Academic Texts: Word Embeddings and Semantic Fingerprints
Venue: arXiv cs.CL 2016
Year: 2016

We present our experience in applying distributional semantics (neural word embeddings) to the problem of representing and clustering documents in a bilingual comparable corpus. Our data is a collection of Russian and Ukrainian academic texts, for which topics are their academic fields. In order to build language-independent semantic representations of these documents, we train neural distributional models on monolingual corpora and learn the optimal linear transformation of vectors from one language to another. The resulting vectors are then used to produce `semantic fingerprints' of documents, serving as input to a clustering algorithm. The presented method is compared to several baselines including `orthographic translation' with Levenshtein edit distance and outperforms them by a large margin. We also show that language-independent `semantic fingerprints' are superior to multi-lingual clustering algorithms proposed in the previous work, at the same time requiring less linguistic resources.
Cognitive state classification using transformed fMRI data
Venue: arXiv cs.CV 2016
Year: 2016

One approach, for understanding human brain functioning, is to analyze the changes in the brain while performing cognitive tasks. Towards this, Functional Magnetic Resonance (fMR) images of subjects performing well-defined tasks are widely utilized for task-specific analyses. In this work, we propose a procedure to enable classification between two chosen cognitive tasks, using their respective fMR image sequences. The time series of expert-marked anatomically-mapped relevant voxels are processed and fed as input to the classical Naive Bayesian and SVM classifiers. The processing involves use of random sieve function, phase information in the data transformed using Fourier and Hilbert transformations. This processing results in improved classification, as against using the voxel intensities directly, as illustrated. The novelty of the proposed method lies in utilizing the phase information in the transformed domain, for classifying between the cognitive tasks along with random sieve function chosen with a particular probability distribution. The proposed classification procedure is applied on a publicly available dataset, StarPlus data, with 6 subjects performing the two distinct cognitive tasks of watching either a picture or a sentence. The classification accuracy stands at an average of 65.6%(using Naive Bayes classifier) and 76.4%(using SVM classifier) for raw data. The corresponding classification accuracy stands at 96.8% and 97.5% for Fourier transformed data. For Hilbert transformed data, it is 93.7% and 99%, for 6 subjects, on 2 cognitive tasks.
Online Row Sampling
Venue: arXiv cs.DS 2016
Year: 2016

Finding a small spectral approximation for a tall $n \times d$ matrix $A$ is a fundamental numerical primitive. For a number of reasons, one often seeks an approximation whose rows are sampled from those of $A$. Row sampling improves interpretability, saves space when $A$ is sparse, and preserves row structure, which is especially important, for example, when $A$ represents a graph. However, correctly sampling rows from $A$ can be costly when the matrix is large and cannot be stored and processed in memory. Hence, a number of recent publications focus on row sampling in the streaming setting, using little more space than what is required to store the outputted approximation [KL13, KLM+14]. Inspired by a growing body of work on online algorithms for machine learning and data analysis, we extend this work to a more restrictive online setting: we read rows of $A$ one by one and immediately decide whether each row should be kept in the spectral approximation or discarded, without ever retracting these decisions. We present an extremely simple algorithm that approximates $A$ up to multiplicative error $ε$ and additive error $δ$ using $O(d \log d \log(ε||A||_2/δ)/ε^2)$ online samples, with memory overhead proportional to the cost of storing the spectral approximation. We also present an algorithm that uses $O(d^2$) memory but only requires $O(d\log(ε||A||_2/δ)/ε^2)$ samples, which we show is optimal. Our methods are clean and intuitive, allow for lower memory usage than prior work, and expose new theoretical properties of leverage score based matrix approximation.
Selfish Computation Offloading for Mobile Cloud Computing in Dense Wireless Networks
Venue: arXiv cs.NI 2016
Year: 2016

Offloading computation to a mobile cloud is a promising solution to augment the computation capabilities of mobile devices. In this paper we consider selfish mobile devices in a dense wireless network, in which individual mobile devices can offload computations via multiple access points (APs) to a mobile cloud so as to minimize their computation costs, and we provide a game theoretical analysis of the problem. We show that in the case of an elastic cloud, all improvement paths are finite, and thus a pure strategy Nash equilibrium exists and can be computed easily. In the case of a non-elastic cloud we show that improvement paths may cycle, yet we show that a pure Nash equilibrium exists and we provide an efficient algorithm for computing one. Furthermore, we provide an upper bound on the price of anarchy (PoA) of the game. We use simulations to evaluate the time complexity of computing Nash equilibria and to provide insights into the PoA under realistic scenarios. Our results show that the equilibrium cost may be close to optimal, and the cost difference is due to too many mobile users offloading simultaneously.
Understanding Rating Behaviour and Predicting Ratings by Identifying Representative Users
Venue: arXiv cs.IR 2016
Year: 2016

Online user reviews describing various products and services are now abundant on the web. While the information conveyed through review texts and ratings is easily comprehensible, there is a wealth of hidden information in them that is not immediately obvious. In this study, we unlock this hidden value behind user reviews to understand the various dimensions along which users rate products. We learn a set of users that represent each of these dimensions and use their ratings to predict product ratings. Specifically, we work with restaurant reviews to identify users whose ratings are influenced by dimensions like 'Service', 'Atmosphere' etc. in order to predict restaurant ratings and understand the variation in rating behaviour across different cuisines. While previous approaches to obtaining product ratings require either a large number of user ratings or a few review texts, we show that it is possible to predict ratings with few user ratings and no review text. Our experiments show that our approach outperforms other conventional methods by 16-27% in terms of RMSE.