OpenRaiser/Intern-Atlas huggingface dataset:
Riffled Independence for Efficient Inference with Partial Rankings
Venue: arXiv cs.LG 2014
Year: 2014

Distributions over rankings are used to model data in a multitude of real world settings such as preference analysis and political elections. Modeling such distributions presents several computational challenges, however, due to the factorial size of the set of rankings over an item set. Some of these challenges are quite familiar to the artificial intelligence community, such as how to compactly represent a distribution over a combinatorially large space, and how to efficiently perform probabilistic inference with these representations. With respect to ranking, however, there is the additional challenge of what we refer to as human task complexity users are rarely willing to provide a full ranking over a long list of candidates, instead often preferring to provide partial ranking information. Simultaneously addressing all of these challenges i.e., designing a compactly representable model which is amenable to efficient inference and can be learned using partial ranking data is a difficult task, but is necessary if we would like to scale to problems with nontrivial size. In this paper, we show that the recently proposed riffled independence assumptions cleanly and efficiently address each of the above challenges. In particular, we establish a tight mathematical connection between the concepts of riffled independence and of partial rankings. This correspondence not only allows us to then develop efficient and exact algorithms for performing inference tasks using riffled independence based represen- tations with partial rankings, but somewhat surprisingly, also shows that efficient inference is not possible for riffle independent models (in a certain sense) with observations which do not take the form of partial rankings. Finally, using our inference algorithm, we introduce the first method for learning riffled independence based models from partially ranked data.
Towards Unsupervised Learning of Temporal Relations between Events
Venue: arXiv cs.LG 2014
Year: 2014

Automatic extraction of temporal relations between event pairs is an important task for several natural language processing applications such as Question Answering, Information Extraction, and Summarization. Since most existing methods are supervised and require large corpora, which for many languages do not exist, we have concentrated our efforts to reduce the need for annotated data as much as possible. This paper presents two different algorithms towards this goal. The first algorithm is a weakly supervised machine learning approach for classification of temporal relations between events. In the first stage, the algorithm learns a general classifier from an annotated corpus. Then, inspired by the hypothesis of "one type of temporal relation per discourse, it extracts useful information from a cluster of topically related documents. We show that by combining the global information of such a cluster with local decisions of a general classifier, a bootstrapping cross-document classifier can be built to extract temporal relations between events. Our experiments show that without any additional annotated data, the accuracy of the proposed algorithm is higher than that of several previous successful systems. The second proposed method for temporal relation extraction is based on the expectation maximization (EM) algorithm. Within EM, we used different techniques such as a greedy best-first search and integer linear programming for temporal inconsistency removal. We think that the experimental results of our EM based algorithm, as a first step toward a fully unsupervised temporal relation extraction method, is encouraging.
Pseudo-random Phase Precoded Spatial Modulation
Venue: arXiv cs.IT 2014
Year: 2014

Spatial modulation (SM) is a transmission scheme that uses multiple transmit antennas but only one transmit RF chain. At each time instant, only one among the transmit antennas will be active and the others remain silent. The index of the active transmit antenna will also convey information bits in addition to the information bits conveyed through modulation symbols (e.g.,QAM). Pseudo-random phase precoding (PRPP) is a technique that can achieve high diversity orders even in single antenna systems without the need for channel state information at the transmitter (CSIT) and transmit power control (TPC). In this paper, we exploit the advantages of both SM and PRPP simultaneously. We propose a pseudo-random phase precoded SM (PRPP-SM) scheme, where both the modulation bits and the antenna index bits are precoded by pseudo-random phases. The proposed PRPP-SM system gives significant performance gains over SM system without PRPP and PRPP system without SM. Since maximum likelihood (ML) detection becomes exponentially complex in large dimensions, we propose low complexity local search based detection (LSD) algorithm suited for PRPP-SM systems with large precoder sizes. Our simulation results show that with 4 transmit antennas, 1 receive antenna, $5\times 20$ pseudo-random phase precoder matrix and BPSK modulation, the performance of PRPP-SM using ML detection is better than SM without PRPP with ML detection by about 9 dB at $10^{-2}$ BER. This performance advantage gets even better for large precoding sizes.
A Novel String Distance Function based on Most Frequent K Characters
Venue: arXiv cs.DS 2014
Year: 2014

This study aims to publish a novel similarity metric to increase the speed of comparison operations. Also the new metric is suitable for distance-based operations among strings. Most of the simple calculation methods, such as string length are fast to calculate but does not represent the string correctly. On the other hand the methods like keeping the histogram over all characters in the string are slower but good to represent the string characteristics in some areas, like natural language. We propose a new metric, easy to calculate and satisfactory for string comparison. Method is built on a hash function, which gets a string at any size and outputs the most frequent K characters with their frequencies. The outputs are open for comparison and our studies showed that the success rate is quite satisfactory for the text mining operations.
Resource Allocation Under Channel Uncertainties for Relay-Aided Device-to-Device Communication Underlaying LTE-A Cellular Networks
Venue: arXiv cs.NI 2014
Year: 2014

Device-to-device (D2D) communication in cellular networks allows direct transmission between two cellular devices with local communication needs. Due to the increasing number of autonomous heterogeneous devices in future mobile networks, an efficient resource allocation scheme is required to maximize network throughput and achieve higher spectral efficiency. In this paper, performance of network-integrated D2D communication under channel uncertainties is investigated where D2D traffic is carried through relay nodes. Considering a multi-user and multi-relay network, we propose a robust distributed solution for resource allocation with a view to maximizing network sum-rate when the interference from other relay nodes and the link gains are uncertain. An optimization problem is formulated for allocating radio resources at the relays to maximize end-to-end rate as well as satisfy the quality-of-service (QoS) requirements for cellular and D2D user equipments under total power constraint. Each of the uncertain parameters is modeled by a bounded distance between its estimated and bounded values. We show that the robust problem is convex and a gradient-aided dual decomposition algorithm is applied to allocate radio resources in a distributed manner. Finally, to reduce the cost of robustness defined as the reduction of achievable sum-rate, we utilize the \textit{chance constraint approach} to achieve a trade-off between robustness and optimality. The numerical results show that there is a distance threshold beyond which relay-aided D2D communication significantly improves network performance when compared to direct communication between D2D peers.
A Generalized Typicality for Abstract Alphabets
Venue: arXiv cs.IT 2014
Year: 2014

A new notion of typicality for arbitrary probability measures on standard Borel spaces is proposed, which encompasses the classical notions of weak and strong typicality as special cases. Useful lemmas about strong typical sets, including conditional typicality lemma, joint typicality lemma, and packing and covering lemmas, which are fundamental tools for deriving many inner bounds of various multi-terminal coding problems, are obtained in terms of the proposed notion. This enables us to directly generalize lots of results on finite alphabet problems to general problems involving abstract alphabets, without any complicated additional arguments. For instance, quantization procedure is no longer necessary to achieve such generalizations. Another fundamental lemma, Markov lemma, is also obtained but its scope of application is quite limited compared to others. Yet, an alternative theory of typical sets for Gaussian measures, free from this limitation, is also developed. Some remarks on a possibility to generalize the proposed notion for sources with memory are also given.
AM with Multiple Merlins
Venue: arXiv cs.CC 2014
Year: 2014

We introduce and study a new model of interactive proofs: AM(k), or Arthur-Merlin with k non-communicating Merlins. Unlike with the better-known MIP, here the assumption is that each Merlin receives an independent random challenge from Arthur. One motivation for this model (which we explore in detail) comes from the close analogies between it and the quantum complexity class QMA(k), but the AM(k) model is also natural in its own right. We illustrate the power of multiple Merlins by giving an AM(2) protocol for 3SAT, in which the Merlins' challenges and responses consist of only n^{1/2+o(1)} bits each. Our protocol has the consequence that, assuming the Exponential Time Hypothesis (ETH), any algorithm for approximating a dense CSP with a polynomial-size alphabet must take n^{(log n)^{1-o(1)}} time. Algorithms nearly matching this lower bound are known, but their running times had never been previously explained. Brandao and Harrow have also recently used our 3SAT protocol to show quasipolynomial hardness for approximating the values of certain entangled games. In the other direction, we give a simple quasipolynomial-time approximation algorithm for free games, and use it to prove that, assuming the ETH, our 3SAT protocol is essentially optimal. More generally, we show that multiple Merlins never provide more than a polynomial advantage over one: that is, AM(k)=AM for all k=poly(n). The key to this result is a subsampling theorem for free games, which follows from powerful results by Alon et al. and Barak et al. on subsampling dense CSPs, and which says that the value of any free game can be closely approximated by the value of a logarithmic-sized random subgame.
Fixed-rank Rayleigh Quotient Maximization by an $M$PSK Sequence
Venue: arXiv cs.IT 2014
Year: 2014

Certain optimization problems in communication systems, such as limited-feedback constant-envelope beamforming or noncoherent $M$-ary phase-shift keying ($M$PSK) sequence detection, result in the maximization of a fixed-rank positive semidefinite quadratic form over the $M$PSK alphabet. This form is a special case of the Rayleigh quotient of a matrix and, in general, its maximization by an $M$PSK sequence is $\mathcal{NP}$-hard. However, if the rank of the matrix is not a function of its size, then the optimal solution can be computed with polynomial complexity in the matrix size. In this work, we develop a new technique to efficiently solve this problem by utilizing auxiliary continuous-valued angles and partitioning the resulting continuous space of solutions into a polynomial-size set of regions, each of which corresponds to a distinct $M$PSK sequence. The sequence that maximizes the Rayleigh quotient is shown to belong to this polynomial-size set of sequences, thus efficiently reducing the size of the feasible set from exponential to polynomial. Based on this analysis, we also develop an algorithm that constructs this set in polynomial time and show that it is fully parallelizable, memory efficient, and rank scalable. The proposed algorithm compares favorably with other solvers for this problem that have appeared recently in the literature.
Bases of T-meshes and the refinement of hierarchical B-splines
Venue: arXiv cs.CG 2014
Year: 2014

In this paper we consider spaces of bivariate splines of bi-degree (m, n) with maximal order of smoothness over domains associated to a two-dimensional grid. We define admissible classes of domains for which suitable combinatorial technique allows us to obtain the dimension of such spline spaces and the number of tensor-product B-splines acting effectively on these domains. Following the strategy introduced recently by Giannelli and Juettler, these results enable us to prove that under certain assumptions about the configuration of a hierarchical T-mesh the hierarchical B-splines form a basis of bivariate splines of bi-degree (m, n) with maximal order of smoothness over this hierarchical T-mesh. In addition, we derive a sufficient condition about the configuration of a hierarchical T-mesh that ensures a weighted partition of unity property for hierarchical B-splines with only positive weights.
Bayesian Properties of Normalized Maximum Likelihood and its Fast Computation
Venue: arXiv cs.IT 2014
Year: 2014

The normalized maximized likelihood (NML) provides the minimax regret solution in universal data compression, gambling, and prediction, and it plays an essential role in the minimum description length (MDL) method of statistical modeling and estimation. Here we show that the normalized maximum likelihood has a Bayes-like representation as a mixture of the component models, even in finite samples, though the weights of linear combination may be both positive and negative. This representation addresses in part the relationship between MDL and Bayes modeling. This representation has the advantage of speeding the calculation of marginals and conditionals required for coding and prediction applications.
MIMO Multiway Relaying with Pairwise Data Exchange: A Degrees of Freedom Perspective
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we study achievable degrees of freedom (DoF) of a multiple-input multiple-output (MIMO) multiway relay channel (mRC) where $K$ users, each equipped with $M$ antennas, exchange messages in a pairwise manner via a common $N$-antenna relay node. % A novel and systematic way of joint beamforming design at the users and at the relay is proposed to align signals for efficient implementation of physical-layer network coding (PNC). It is shown that, when the user number $K=3$, the proposed beamforming design can achieve the DoF capacity of the considered mRC for any $(M,N)$ setups. % For the scenarios with $K>3$, we show that the proposed signaling scheme can be improved by disabling a portion of relay antennas so as to align signals more efficiently. Our analysis reveals that the obtained achievable DoF is always piecewise linear, and is bounded either by the number of user antennas $M$ or by the number of relay antennas $N$. Further, we show that the DoF capacity can be achieved for $\frac{M}{N} \in \left(0,\frac{K-1}{K(K-2)} \right]$ and $\frac{M}{N} \in \left[\frac{1}{K(K-1)}+\frac{1}{2},\infty \right)$, which provides a broader range of the DoF capacity than the existing results. Asymptotic DoF as $K\rightarrow \infty$ is also derived based on the proposed signaling scheme.
On the Cooperative Communication over Cognitive Interference Channel
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we investigate the problem of communication over cognitive interference channel (CIC) with partially cooperating (PC) destinations (CIC-PC). This channel consists of two source nodes communicating two independent messages to their corresponding destination nodes. One of the sources, referred to as the cognitive source, has a noncausal knowledge of the message of the other source, referred to as the primary source. Each destination is assumed to decode only its intended message. In addition, the destination corresponding to the cognitive source assists the other destination by transmitting cooperative information through a relay link. We derive a new upper bound on the capacity region of discrete memoryless CI-CPC. Moreover, we characterize the capacity region for two new classes of this channel: (1) degraded CIC-PC, and (2) a class of semideterministic CIC-PC.
On Stochastic Estimation of Partition Function
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we show analytically that the duality of normal factor graphs (NFG) can facilitate stochastic estimation of partition functions. In particular, our analysis suggests that for the $q-$ary two-dimensional nearest-neighbor Potts model, sampling from the primal NFG of the model and sampling from its dual exhibit opposite behaviours with respect to the temperature of the model. For high-temperature models, sampling from the primal NFG gives rise to better estimators whereas for low-temperature models, sampling from the dual gives rise to better estimators. This analysis is validated by experiments.
Deterministic Blind Rendezvous in Cognitive Radio Networks
Venue: arXiv cs.NI 2014
Year: 2014

Blind rendezvous is a fundamental problem in cognitive radio networks. The problem involves a collection of agents (radios) that wish to discover each other in the blind setting where there is no shared infrastructure and they initially have no knowledge of each other. Time is divided into discrete slots; spectrum is divided into discrete channels, $\{1,2,..., n\}$. Each agent may access a single channel in a single time slot and we say that two agents rendezvous when they access the same channel in the same time slot. The model is asymmetric: each agent $A_i$ may only use a particular subset $S_i$ of the channels and different agents may have access to different subsets of channels. The goal is to design deterministic channel hopping schedules for each agent so as to guarantee rendezvous between any pair of agents with overlapping channel sets. Two independent sets of authors, Shin et al. and Lin et al., gave the first constructions guaranteeing asynchronous blind rendezvous in $O(n^2)$ and $O(n^3)$ time, respectively. We present a substantially improved construction guaranteeing that any two agents, $A_i$, $A_j$, will rendezvous in $O(|S_i| |S_j| \log\log n)$ time. Our results are the first that achieve nontrivial dependence on $|S_i|$, the size of the set of available channels. This allows us, for example, to save roughly a quadratic factor over the best previous results in the important case when channel subsets have constant size. We also achieve the best possible bound of $O(1)$ time for the symmetric situation; previous works could do no better than $O(n)$. Using the probabilistic method and Ramsey theory we provide evidence in support of our suspicion that our construction is asymptotically optimal for small size channel subsets: we show both a $c |S_i||S_j|$ lower bound and a $c \log\log n$ lower bound when $|S_i|, |S_j| \leq n/2$.
A Shannon Approach to Secure Multi-party Computations
Venue: arXiv cs.IT 2014
Year: 2014

In secure multi-party computations (SMC), parties wish to compute a function on their private data without revealing more information about their data than what the function reveals. In this paper, we investigate two Shannon-type questions on this problem. We first consider the traditional one-shot model for SMC which does not assume a probabilistic prior on the data. In this model, private communication and randomness are the key enablers to secure computing, and we investigate a notion of randomness cost and capacity. We then move to a probabilistic model for the data, and propose a Shannon model for discrete memoryless SMC. In this model, correlations among data are the key enablers for secure computing, and we investigate a notion of dependency which permits the secure computation of a function. While the models and questions are general, this paper focuses on summation functions, and relies on polar code constructions.
Linear Codes are Optimal for Index-Coding Instances with Five or Fewer Receivers
Venue: arXiv cs.IT 2014
Year: 2014

We study zero-error unicast index-coding instances, where each receiver must perfectly decode its requested message set, and the message sets requested by any two receivers do not overlap. We show that for all these instances with up to five receivers, linear index codes are optimal. Although this class contains 9847 non-isomorphic instances, by using our recent results and by properly categorizing the instances based on their graphical representations, we need to consider only 13 non-trivial instances to solve the entire class. This work complements the result by Arbabjolfaei et al. (ISIT 2013), who derived the capacity region of all unicast index-coding problems with up to five receivers in the diminishing-error setup. They employed random-coding arguments, which require infinitely-long messages. We consider the zero-error setup; our approach uses graph theory and combinatorics, and does not require long messages.
Improved Robust Node Position Estimation in Wireless Sensor Networks
Venue: arXiv cs.NI 2014
Year: 2014

A new method for estimating the relative positions of location-unaware nodes from the location-aware nodes and the received signal strength (RSS) between the nodes, in a wireless sensor network (WSN), is proposed. In the method, a regularization term is incorporated in the optimization problem leading to significant improvement in the estimation accuracy even in the presence of position errors of the location-aware nodes and distance errors between the nodes. The regularization term is appropriated weighted on the basis of the degree of connectivity between the nodes in the network. The method is formulated as a convex optimization problem using the semidefinite relaxation approach. Experimental comparisons with state-of-the-art competing methods show that the proposed method yields node positions that are much more accurate even in the presence of measurement errors.
A novel method of generating tunable underlying network topologies for social simulation
Venue: arXiv cs.SI 2014
Year: 2014

We propose a method of generating different scale-free networks, which has several input parameters in order to adjust the structure, so that they can serve as a basis for computer simulation of real-world phenomena. The topological structure of these networks was studied to determine what kind of networks can be produced and how can we give the appropriate values of parameters to get a desired structure.
Use HMM and KNN for classifying corneal data
Venue: arXiv cs.CV 2014
Year: 2014

These days to gain classification system with high accuracy that can classify complicated pattern are so useful in medicine and industry. In this article a process for getting the best classifier for Lasik data is suggested. However at first it's been tried to find the best line and curve by this classifier in order to gain classifier fitting, and in the end by using the Markov method a classifier for topographies is gained.