OpenRaiser/Intern-Atlas huggingface dataset:
Document Embedding with Paragraph Vectors
Venue: arXiv cs.CL 2015
Year: 2015

Paragraph Vectors has been recently proposed as an unsupervised method for learning distributed representations for pieces of texts. In their work, the authors showed that the method can learn an embedding of movie review texts which can be leveraged for sentiment analysis. That proof of concept, while encouraging, was rather narrow. Here we consider tasks other than sentiment analysis, provide a more thorough comparison of Paragraph Vectors to other document modelling algorithms such as Latent Dirichlet Allocation, and evaluate performance of the method as we vary the dimensionality of the learned representation. We benchmarked the models on two document similarity data sets, one from Wikipedia, one from arXiv. We observe that the Paragraph Vector method performs significantly better than other methods, and propose a simple improvement to enhance embedding quality. Somewhat surprisingly, we also show that much like word embeddings, vector operations on Paragraph Vectors can perform useful semantic results.
Private Stream Aggregation Revisited
Venue: arXiv cs.CR 2015
Year: 2015

In this work, we investigate the problem of private statistical analysis in the distributed and semi-honest setting. In particular, we study properties of Private Stream Aggregation schemes, first introduced by Shi et al. \cite{2}. These are computationally secure protocols for the aggregation of data in a network and have a very small communication cost. We show that such schemes can be built upon any key-homomorphic \textit{weak} pseudo-random function. Thus, in contrast to the aforementioned work, our security definition can be achieved in the \textit{standard model}. In addition, we give a computationally efficient instantiation of this protocol based on the Decisional Diffie-Hellman problem. Moreover, we show that every mechanism which preserves $(ε,δ)$-differential privacy provides \textit{computational} $(ε,δ)$-differential privacy when it is executed through a Private Stream Aggregation scheme. Finally, we introduce a novel perturbation mechanism based on the \textit{Skellam distribution} that is suited for the distributed setting, and compare its performances with those of previous solutions.
PointQ model of an arterial network: calibration and experiments
Venue: arXiv cs.SY 2015
Year: 2015

The calibration of a PointQ arterial microsimulation model is formulated as a quadratic programming problem (QP) whose decision variables are link flows, demands at entry links, and turn movements at intersections, subject to linear constraints imposed by flow conservation identities and field measurements of a subset of link flows (counts), demands and turn ratios. The quadratic objective function is the deviation of the decision variables from their measured values. The solution to the QP gives estimates of all unmeasured variables and thus yields a fully specified simulation model. Runs of this simulation model can then be compared with other field measurements, such as travel times along routes, to judge the reliability of the calibrated model. A section of the Huntington-Colorado arterial near I-210 in Los Angeles comprising 73 links and 16 intersections is used to illustrate the procedure. Two experiments are conducted with the calibrated model to determine the maximum traffic that can be diverted from the I-210 freeway to the arterial network, with and without permitting changes in the timing plans. The maximum diversion in both cases is obtained by solving a linear programming problem. A third experiment compares the delay and travel time using the existing fixed time control and a max pressure control. The fourth experiment compares two PointQ models: in the first model the freeway traffic follows a pre-specified route while the background traffic moves according to turn ratios, and in the second model turn ratios are modified in a single commodity model to match the link flows. The substantial modification of the turn ratios needed suggests that the use of a single-commodity model as frequently done in CTM models can be misleading...
A SAT-based Public Key Cryptography Scheme
Venue: arXiv cs.CR 2015
Year: 2015

A homomorphic public key crypto-scheme based on the Boolean Satisfiability Problem is proposed. The public key is a SAT formula satisfied by the private key. Probabilistic encryption generates functions implied to be false by the public key XOR the message bits. A zero-knowledge proof is used to provide signatures.
Some studies on multidimensional Fourier theory for Hilbert transform, analytic signal and space-time series analysis
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we propose the Fourier frequency vector (FFV), inherently, associated with multidimensional Fourier transform. With the help of FFV, we are able to provide physical meaning of so called negative frequencies in multidimensional Fourier transform (MDFT), which in turn provide multidimensional spatial and space-time series analysis. The complex exponential representation of sinusoidal function always yields two frequencies, negative frequency corresponding to positive frequency and vice versa, in the multidimensional Fourier spectrum. Thus, using the MDFT, we propose multidimensional Hilbert transform (MDHT) and associated multidimensional analytic signal (MDAS) with following properties: (a) the extra and redundant positive, negative, or both frequencies, introduced due to complex exponential representation of multidimensional Fourier spectrum, are suppressed, (b) real part of MDAS is original signal, (c) real and imaginary part of MDAS are orthogonal, and (d) the magnitude envelope of a original signal is obtained as the magnitude of its associated MDAS, which is the instantaneous amplitude of the MDAS. The proposed MDHT and associated DMAS are generalization of the 1D HT and AS, respectively. We also provide the decomposition of an image into the AM-FM image model by the Fourier method and obtain explicit expression for the analytic image computation by 2DDFT.
Error Rate and Power Allocation Analysis of Regenerative Networks under Generalized Fading Conditions
Venue: arXiv cs.IT 2015
Year: 2015

Cooperative communication has been shown to provide significant increase of transmission reliability and network capacity while expanding coverage in cellular networks. The present work is devoted to the investigation of the end-to-end performance and power allocation of a maximum-ratio-combining based regenerative multi-relay cooperative network over non-homogeneous scattering environment, which is the case in realistic wireless communication scenarios. Novel analytic expressions are derived for the end-to-end symbol-error-rate of both $M-$ary Phase-Shift Keying and $M-$ary Quadrature Amplitude Modulation over independent and non-identically distributed generalized fading channels. The offered results are expressed in closed-form involving the Lauricella function and can be readily evaluated with the aid of a proposed computational algorithm. Simple expressions are also derived for the corresponding symbol-error-rate at asymptotically high signal-to-noise ratios. The derived expressions are corroborated with respective results from computer simulations and are subsequently employed in formulating a power optimization problem that enhances the system performance under total power constraints within the multi-relay cooperative system. Furthermore, it is shown that optimum power allocation provides substantial performance gains over equal power allocation, particularly, when the source-relay and relay-destination paths are highly unbalanced.
EESEN: End-to-End Speech Recognition using Deep RNN Models and WFST-based Decoding
Venue: arXiv cs.CL 2015
Year: 2015

The performance of automatic speech recognition (ASR) has improved tremendously due to the application of deep neural networks (DNNs). Despite this progress, building a new ASR system remains a challenging task, requiring various resources, multiple training stages and significant expertise. This paper presents our Eesen framework which drastically simplifies the existing pipeline to build state-of-the-art ASR systems. Acoustic modeling in Eesen involves learning a single recurrent neural network (RNN) predicting context-independent targets (phonemes or characters). To remove the need for pre-generated frame labels, we adopt the connectionist temporal classification (CTC) objective function to infer the alignments between speech and label sequences. A distinctive feature of Eesen is a generalized decoding approach based on weighted finite-state transducers (WFSTs), which enables the efficient incorporation of lexicons and language models into CTC decoding. Experiments show that compared with the standard hybrid DNN systems, Eesen achieves comparable word error rates (WERs), while at the same time speeding up decoding significantly.
Price of Anarchy for Graph Coloring Games with Concave Payoff
Venue: arXiv cs.GT 2015
Year: 2015

We study the price of anarchy in a class of graph coloring games (a subclass of polymatrix common-payoff games). In those games, players are vertices of an undirected, simple graph, and the strategy space of each player is the set of colors from $1$ to $k$. A tight bound on the price of anarchy of $\frac{k}{k-1}$ is known (Hoefer 2007, Kun et al. 2013), for the case that each player's payoff is the number of her neighbors with different color than herself. The study of more complex payoff functions was left as an open problem. We compute payoff for a player by determining the distance of her color to the color of each of her neighbors, applying a non-negative, real-valued, concave function $f$ to each of those distances, and then summing up the resulting values. This includes the payoff functions suggested by Kun et al. (2013) for future work as special cases. Denote $f^*$ the maximum value that $f$ attains on the possible distances $0,\dots,k-1$. We prove an upper bound of $2$ on the price of anarchy for concave functions $f$ that are non-decreasing or which assume $f^*$ at a distance on or below $\lfloor\frac{k}{2}\rfloor$. Matching lower bounds are given for the monotone case and for the case that $f^*$ is assumed in $\frac{k}{2}$ for even $k$. For general concave functions, we prove an upper bound of $3$. We use a simple but powerful technique: we obtain an upper bound of $λ\geq 1$ on the price of anarchy if we manage to give a splitting $λ_1 + \dots + λ_k = λ$ such that $\sum_{s=1}^k λ_s \cdot f(|s-p|) \geq f^*$ for all $p \in \{1,\dots,k\}$. The discovery of working splittings can be supported by computer experiments. We show how, once we have an idea what kind of splittings work, this technique helps in giving simple proofs, which mainly work by case distinctions, algebraic manipulations, and real calculus.
Ordering Selection Operators Using the Minmax Regret Rule
Venue: arXiv cs.DB 2015
Year: 2015

Optimising queries in real-world situations under imperfect conditions is still a problem that has not been fully solved. We consider finding the optimal order in which to execute a given set of selection operators under partial ignorance of their selectivities. The selectivities are modelled as intervals rather than exact values and we apply a concept from decision theory, the minimisation of the maximum regret, as a measure of optimality. We show that the associated decision problem is NP-hard, which renders a brute-force approach to solving it impractical. Nevertheless, by investigating properties of the problem and identifying special cases which can be solved in polynomial time, we gain insight that we use to develop a novel heuristic for solving the general problem. We also evaluate minmax regret query optimisation experimentally, showing that it outperforms a currently employed strategy of optimisers that uses mean values for uncertain parameters.
How Data Volume Affects Spark Based Data Analytics on a Scale-up Server
Venue: arXiv cs.DC 2015
Year: 2015

Sheer increase in volume of data over the last decade has triggered research in cluster computing frameworks that enable web enterprises to extract big insights from big data. While Apache Spark is gaining popularity for exhibiting superior scale-out performance on the commodity machines, the impact of data volume on the performance of Spark based data analytics in scale-up configuration is not well understood. We present a deep-dive analysis of Spark based applications on a large scale-up server machine. Our analysis reveals that Spark based data analytics are DRAM bound and do not benefit by using more than 12 cores for an executor. By enlarging input data size, application performance degrades significantly due to substantial increase in wait time during I/O operations and garbage collection, despite 10\% better instruction retirement rate (due to lower L1 cache misses and higher core utilization). We match memory behaviour with the garbage collector to improve performance of applications between 1.6x to 3x.
Perceived Social Loafing in Undergraduate Software Engineering Teams
Venue: arXiv cs.CY 2015
Year: 2015

We surveyed 237 undergraduate students who are enrolled in various subjects and are members of software engineering teams. Their being a member in a team is part of the requirements of the course. We found that each of task visibility, distributive justice, and intrinsic task involvement were negatively associated with social loafing. We also found out that dominance, aggression and sucker effect each were positively correlated with social loafing. We further found out that perception of social loafing exists among members of software engineering teams.
Inferences in a Virtual Community: Demography, User Preferences, and Network Topology
Venue: arXiv cs.SI 2015
Year: 2015

This paper presents a computational procedure for extracting demography data, mining patterns of human preferences, and measuring the topology of a virtual network. The network was created from the personal and relationships data of an online Internet-based community, where persons are considered nodes in the network, and relationships between persons are considered edges. A community of Friendster users whose listed hometown is Los Baños, Laguna was used as a test bed for the methodology. The method was able to provide the following demographic, preferential, and topological results about the test bed: (1) There are more female users (52.34\%) than male (47.66\%); (2) Homophily (i.e., birds-of-a-feather adage) is observed in the preferences of users with respect to age levels, such that they are strongly biased towards being friends with users of a similar age; (3) There is heterophily in gender preference such that friendship among users of the opposite gender occurs more often. (4) It exhibits a small-world characteristic with an average path length of 4.5 (maximum=12) among connected users, shorter than the well-known {\em six degrees of separation}~\cite{travers69}; And (5) The network exhibits a scale-free characteristics with heavily-tailed power-law distribution (with the power $λ= -1.02$ and $R^2 = 0.84$) suggesting the presence of many users acting as the network hubs. The methodology was successful in providing important data from a virtual community which can be used by several researchers in the fields of statistics, mathematics, physics, social sciences, and computer science.
New $q$-ary Quantum MDS Codes with Distances Bigger than $\frac{q}{2}$
Venue: arXiv cs.IT 2015
Year: 2015

Constructions of quantum MDS codes have been studied by many authors. We refer to the table in page 1482 of [3] for known constructions. However there are only few $q$-ary quantum MDS $[[n,n-2d+2,d]]_q$ codes with minimum distances $d>\frac{q}{2}$ for sparse lengths $n>q+1$. In the case $n=\frac{q^2-1}{m}$ where $m|q+1$ or $m|q-1$ there are complete results. In the case $n=\frac{q^2-1}{m}$ where $m|q^2-1$ is not a factor of $q-1$ or $q+1$, there is no $q$-ary quantum MDS code with $d> \frac{q}{2}$ has been constructed. In this paper we propose a direct approch to construct Hermitian self-orthogonal codes over ${\bf F}_{q^2}$. Thus we give some new $q$-ary quantum codes in this case. Moreover we present many new $q$-ary quantum MDS codes with lengths of the form $\frac{w(q^2-1)}{u}$ and minimum distances $d > \frac{q}{2}$.
The Submodular Secretary Problem Goes Linear
Venue: arXiv cs.DS 2015
Year: 2015

During the last decade, the matroid secretary problem (MSP) became one of the most prominent classes of online selection problems. Partially linked to its numerous applications in mechanism design, substantial interest arose also in the study of nonlinear versions of MSP, with a focus on the submodular matroid secretary problem (SMSP). So far, O(1)-competitive algorithms have been obtained for SMSP over some basic matroid classes. This created some hope that, analogously to the matroid secretary conjecture, one may even obtain O(1)-competitive algorithms for SMSP over any matroid. However, up to now, most questions related to SMSP remained open, including whether SMSP may be substantially more difficult than MSP; and more generally, to what extend MSP and SMSP are related. Our goal is to address these points by presenting general black-box reductions from SMSP to MSP. In particular, we show that any O(1)-competitive algorithm for MSP, even restricted to a particular matroid class, can be transformed in a black-box way to an O(1)-competitive algorithm for SMSP over the same matroid class. This implies that the matroid secretary conjecture is equivalent to the same conjecture for SMSP. Hence, in this sense SMSP is not harder than MSP. Also, to find O(1)-competitive algorithms for SMSP over a particular matroid class, it suffices to consider MSP over the same matroid class. Using our reductions we obtain many first and improved O(1)-competitive algorithms for SMSP over various matroid classes by leveraging known algorithms for MSP. Moreover, our reductions imply an O(loglog(rank))-competitive algorithm for SMSP, thus, matching the currently best asymptotic algorithm for MSP, and substantially improving on the previously best O(log(rank))-competitive algorithm for SMSP.
Stable Drug Designing By Minimizing Drug Protein Interaction Energy Using PSO
Venue: arXiv cs.CE 2015
Year: 2015

Each and every biological function in living organism happens as a result of protein-protein interactions.The diseases are no exception to this. Identifying one or more proteins for a particular disease and then designing a suitable chemical compound (known as drug) to destroy these proteins has been an interesting topic of research in bio-informatics. In previous methods, drugs were designed using only seven chemical components and were represented as a fixed-length tree. But in reality, a drug contains many chemical groups collectively known as pharmacophore. Moreover, the chemical length of the drug cannot be determined before designing the drug.In the present work, a Particle Swarm Optimization (PSO) based methodology has been proposed to find out a suitable drug for a particular disease so that the drug-protein interaction becomes stable. In the proposed algorithm, the drug is represented as a variable length tree and essential functional groups are arranged in different positions of that drug. Finally, the structure of the drug is obtained and its docking energy is minimized simultaneously. Also, the orientation of chemical groups in the drug is tested so that it can bind to a particular active site of a target protein and the drug fits well inside the active site of target protein. Here, several inter-molecular forces have been considered for accuracy of the docking energy. Results show that PSO performs better than the earlier methods.
Multilinear Map Layer: Prediction Regularization by Structural Constraint
Venue: arXiv cs.CV 2015
Year: 2015

In this paper we propose and study a technique to impose structural constraints on the output of a neural network, which can reduce amount of computation and number of parameters besides improving prediction accuracy when the output is known to approximately conform to the low-rankness prior. The technique proceeds by replacing the output layer of neural network with the so-called MLM layers, which forces the output to be the result of some Multilinear Map, like a hybrid-Kronecker-dot product or Kronecker Tensor Product. In particular, given an "autoencoder" model trained on SVHN dataset, we can construct a new model with MLM layer achieving 62\% reduction in total number of parameters and reduction of $\ell_2$ reconstruction error from 0.088 to 0.004. Further experiments on other autoencoder model variants trained on SVHN datasets also demonstrate the efficacy of MLM layers.
Randomised Rounding with Applications
Venue: arXiv cs.DS 2015
Year: 2015

We develop new techniques for rounding packing integer programs using iterative randomized rounding. It is based on a novel application of multidimensional Brownian motion in $\mathbb{R}^n$. Let $\overset{\sim}{x} \in {[0,1]}^n$ be a fractional feasible solution of a packing constraint $A x \leq 1,\ \ $ $A \in {\{0,1 \}}^{m\times n}$ that maximizes a linear objective function. The independent randomized rounding method of Raghavan-Thompson rounds each variable $x_i$ to 1 with probability $\overset{\sim}{x_i}$ and 0 otherwise. The expected value of the rounded objective function matches the fractional optimum and no constraint is violated by more than $O(\frac{\log m} {\log\log m})$.In contrast, our algorithm iteratively transforms $\overset{\sim}{x}$ to $\hat{x} \in {\{ 0,1\}}^{n}$ using a random walk, such that the expected values of $\hat{x}_i$'s are consistent with the Raghavan-Thompson rounding. In addition, it gives us intermediate values $x'$ which can then be used to bias the rounding towards a superior solution.The reduced dependencies between the constraints of the sparser system can be exploited using {\it Lovasz Local Lemma}. For $m$ randomly chosen packing constraints in $n$ variables, with $k$ variables in each inequality, the constraints are satisfied within $O(\frac{\log (mkp\log m/n) }{\log\log (mkp\log m/n)})$ with high probability where $p$ is the ratio between the maximum and minimum coefficients of the linear objective function. Further, we explore trade-offs between approximation factors and error, and present applications to well-known problems like circuit-switching, maximum independent set of rectangles and hypergraph $b$-matching. Our methods apply to the weighted instances of the problems and are likely to lead to better insights for even dependent rounding.