OpenRaiser/Intern-Atlas huggingface dataset:
A data-driven method for syndrome type identification and classification in traditional Chinese medicine
Venue: arXiv cs.LG 2016
Year: 2016

Objective: The efficacy of traditional Chinese medicine (TCM) treatments for Western medicine (WM) diseases relies heavily on the proper classification of patients into TCM syndrome types. We develop a data-driven method for solving the classification problem, where syndrome types are identified and quantified based on patterns detected in unlabeled symptom survey data. Method: Latent class analysis (LCA) has been applied in WM research to solve a similar problem, i.e., to identify subtypes of a patient population in the absence of a gold standard. A widely known weakness of LCA is that it makes an unrealistically strong independence assumption. We relax the assumption by first detecting symptom co-occurrence patterns from survey data and use those patterns instead of the symptoms as features for LCA. Results: The result of the investigation is a six-step method: Data collection, symptom co-occurrence pattern discovery, pattern interpretation, syndrome identification, syndrome type identification, and syndrome type classification. A software package called Lantern is developed to support the application of the method. The method is illustrated using a data set on Vascular Mild Cognitive Impairment (VMCI). Conclusions: A data-driven method for TCM syndrome identification and classification is presented. The method can be used to answer the following questions about a Western medicine disease: What TCM syndrome types are there among the patients with the disease? What is the prevalence of each syndrome type? What are the statistical characteristics of each syndrome type in terms of occurrence of symptoms? How can we determine the syndrome type(s) of a patient?
On the Capacity of Vector Gaussian Channels With Bounded Inputs
Venue: arXiv cs.IT 2016
Year: 2016

The capacity of a deterministic multiple-input multiple-output (MIMO) channel under the peak and average power constraints is investigated. For the identity channel matrix, the approach of Shamai et al. is generalized to the higher dimension settings to derive the necessary and sufficient conditions for the optimal input probability density function. This approach prevents the usage of the identity theorem of the holomorphic functions of several complex variables which seems to fail in the multi-dimensional scenarios. It is proved that the support of the capacity-achieving distribution is a finite set of hyper-spheres with mutual independent phases and amplitude in the spherical domain. Subsequently, it is shown that when the average power constraint is relaxed, if the number of antennas is large enough, the capacity has a closed form solution and constant amplitude signaling at the peak power achieves it. Moreover, it will be observed that in a discrete-time memoryless Gaussian channel, the average power constrained capacity, which results from a Gaussian input distribution, can be closely obtained by an input where the support of its magnitude is a discrete finite set. Finally, we investigate some upper and lower bounds for the capacity of the non-identity channel matrix and evaluate their performance as a function of the condition number of the channel.
Achievable Rates and Training Optimization for Uplink Multiuser Massive MIMO Systems
Venue: arXiv cs.IT 2016
Year: 2016

We study the performance of uplink transmission in a large-scale (massive) MIMO system, where all the transmitters have single antennas and the base station has a large number of antennas. Specifically, we first derive the rates that are possible through minimum mean-squared error (MMSE) channel estimation and three linear receivers: maximum ratio combining (MRC), zero-forcing (ZF), and MMSE. Based on the derived rates, we quantify the amount of energy savings that are possible through increased number of base-station antennas or increased coherence interval. We also analyze achievable total degrees of freedom (DoF) of such a system without assuming channel state information at the receiver, which is shown to be the same as that of a point-to-point MIMO channel. Linear receiver is sufficient to achieve total DoF when the number of users is less than the number of antennas. When the number of users is equal to or larger than the number of antennas, nonlinear processing is necessary to achieve the full degrees of freedom. Finally, the training period and optimal training energy allocation under the average and peak power constraints are optimized jointly to maximize the achievable sum rate when either MRC or ZF receiver is adopted at the receiver.
A Statistical Decision-Theoretic Framework for Social Choice
Venue: arXiv cs.AI 2016
Year: 2016

In this paper, we take a statistical decision-theoretic viewpoint on social choice, putting a focus on the decision to be made on behalf of a system of agents. In our framework, we are given a statistical ranking model, a decision space, and a loss function defined on (parameter, decision) pairs, and formulate social choice mechanisms as decision rules that minimize expected loss. This suggests a general framework for the design and analysis of new social choice mechanisms. We compare Bayesian estimators, which minimize Bayesian expected loss, for the Mallows model and the Condorcet model respectively, and the Kemeny rule. We consider various normative properties, in addition to computational complexity and asymptotic behavior. In particular, we show that the Bayesian estimator for the Condorcet model satisfies some desired properties such as anonymity, neutrality, and monotonicity, can be computed in polynomial time, and is asymptotically different from the other two rules when the data are generated from the Condorcet model for some ground truth parameter.
Validation of Matching
Venue: arXiv cs.LG 2016
Year: 2016

We introduce a technique to compute probably approximately correct (PAC) bounds on precision and recall for matching algorithms. The bounds require some verified matches, but those matches may be used to develop the algorithms. The bounds can be applied to network reconciliation or entity resolution algorithms, which identify nodes in different networks or values in a data set that correspond to the same entity. For network reconciliation, the bounds do not require knowledge of the network generation process.
Secret Key Agreement: General Capacity and Second-Order Asymptotics
Venue: arXiv cs.IT 2016
Year: 2016

We revisit the problem of secret key agreement using interactive public communication for two parties and propose a new secret key agreement protocol. The protocol attains the secret key capacity for general observations and attains the second-order asymptotic term in the maximum length of a secret key for independent and identically distributed observations. In contrast to the previously suggested secret key agreement protocols, the proposed protocol uses interactive communication. In fact, the standard one-way communication protocol used prior to this work fails to attain the asymptotic results above. Our converse proofs rely on a recently established upper bound for secret key lengths. Both our lower and upper bounds are derived in a single-shot setup and the asymptotic results are obtained as corollaries.
Convergence Analysis for Regular Wireless Consensus Networks
Venue: arXiv cs.DC 2016
Year: 2016

Average consensus algorithms can be implemented over wireless sensor networks (WSN), where global statistics can be computed using communications among sensor nodes locally. Simple execution, robustness to global topology changes due to frequent node failures and underlying distributed philosophy has made consensus algorithms more suitable to WSNs. Since these algorithms are iterative in nature, their performance is characterized by convergence speed. We study the convergence of the average consensus algorithms for WSNs using regular graphs. We obtained the analytical expressions for optimal consensus and convergence parameters which decides the convergence time for r-nearest neighbor cycle and torus networks. We have also derived the generalized expression for optimal consensus and convergence parameters for m-dimensional r-nearest neighbor torus networks. The obtained analytical results agree with the simulation results and shown the effect of network dimension, number of nodes and transmission radius on convergence time. This work provides the basic analytical tools for managing and controlling the performance of average consensus algorithm in the finite sized practical networks.
Statistical Delay Tradeoffs in Buffer-Aided Two-Hop Wireless Communication Systems
Venue: arXiv cs.IT 2016
Year: 2016

This paper analyzes the impact of statistical delay constraints on the achievable rate of a two-hop wireless communication link, in which the communication between a source and a destination is accomplished via a buffer-aided relay node. It is assumed that there is no direct link between the source and the destination, and the buffer-aided relay forwards the information to the destination by employing the decode-and-forward scheme. Given statistical delay constraints specified via maximum delay and delay violation probability, the tradeoff between the statistical delay constraints imposed on any two concatenated queues is identified. With this characterization, the maximum constant arrival rates that can be supported by this two-hop link are obtained by determining the effective capacity of such links as a function of the statistical delay constraints, signal-to-noise ratios (SNR) at the source and relay, and the fading distributions of the links. It is shown that asymmetric statistical delay constraints at the buffers of the source and relay node can improve the achievable rate. Overall, the impact of the statistical delay tradeoff on the achievable throughput is provided.
Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometry
Venue: arXiv cs.LG 2016
Year: 2016

Empirical Risk Minimization (ERM) is a standard technique in machine learning, where a model is selected by minimizing a loss function over constraint set. When the training dataset consists of private information, it is natural to use a differentially private ERM algorithm, and this problem has been the subject of a long line of work started with Chaudhuri and Monteleoni 2008. A private ERM algorithm outputs an approximate minimizer of the loss function and its error can be measured as the difference from the optimal value of the loss function. When the constraint set is arbitrary, the required error bounds are fairly well understood \cite{BassilyST14}. In this work, we show that the geometric properties of the constraint set can be used to derive significantly better results. Specifically, we show that a differentially private version of Mirror Descent leads to error bounds of the form $\tilde{O}(G_{\mathcal{C}}/n)$ for a lipschitz loss function, improving on the $\tilde{O}(\sqrt{p}/n)$ bounds in Bassily, Smith and Thakurta 2014. Here $p$ is the dimensionality of the problem, $n$ is the number of data points in the training set, and $G_{\mathcal{C}}$ denotes the Gaussian width of the constraint set that we optimize over. We show similar improvements for strongly convex functions, and for smooth functions. In addition, we show that when the loss function is Lipschitz with respect to the $\ell_1$ norm and $\mathcal{C}$ is $\ell_1$-bounded, a differentially private version of the Frank-Wolfe algorithm gives error bounds of the form $\tilde{O}(n^{-2/3})$. This captures the important and common case of sparse linear regression (LASSO), when the data $x_i$ satisfies $|x_i|_{\infty} \leq 1$ and we optimize over the $\ell_1$ ball. We show new lower bounds for this setting, that together with known bounds, imply that all our upper bounds are tight.
Interval edge-colorings of complete graphs
Venue: arXiv cs.DM 2016
Year: 2016

An edge-coloring of a graph $G$ with colors $1,2,\ldots,t$ is an interval $t$-coloring if all colors are used, and the colors of edges incident to each vertex of $G$ are distinct and form an interval of integers. A graph $G$ is interval colorable if it has an interval $t$-coloring for some positive integer $t$. For an interval colorable graph $G$, $W(G)$ denotes the greatest value of $t$ for which $G$ has an interval $t$-coloring. It is known that the complete graph is interval colorable if and only if the number of its vertices is even. However, the exact value of $W(K_{2n})$ is known only for $n \leq 4$. The second author showed that if $n = p2^q$, where $p$ is odd and $q$ is nonnegative, then $W(K_{2n}) \geq 4n-2-p-q$. Later, he conjectured that if $n \in \mathbb{N}$, then $W(K_{2n}) = 4n - 2 - \left\lfloor\log_2{n}\right\rfloor - \left \| n_2 \right \|$, where $\left \| n_2 \right \|$ is the number of $1$'s in the binary representation of $n$. In this paper we introduce a new technique to construct interval colorings of complete graphs based on their 1-factorizations, which is used to disprove the conjecture, improve lower and upper bounds on $W(K_{2n})$ and determine its exact values for $n \leq 12$.
Mutual information in nonlinear communication channel. Preliminary analytical results in large SNR and small nonlinearity limit
Venue: arXiv cs.IT 2016
Year: 2016

Applying perturbation theory to the path-integral representation for the mutual information of the nonlinear communication channel described by the nonlinear Shrödinger equation (NLSE) with the additive Gaussian noise we analyze the analytical expression for the mutual information at large signal-to-noise ratio ($\mathrm{SNR}$) and small nonlinearity. We classify all possible corrections to the mutual information in nonlinearity parameter and demonstrate that all singular in $\mathrm{SNR}$ terms vanish in the final result. Furthermore our analytical result demonstrates that the corrections to Shannon's contribution to the mutual information in the leading order in $\mathrm{SNR}$ are of order of squared nonlinearity parameter. We outline the way for the calculation of these corrections in the further investigations.
Performance Analysis of mmWave Ad Hoc Networks
Venue: arXiv cs.IT 2016
Year: 2016

Ad hoc networks provide an on-demand, infrastructure-free means to communicate between soldiers in war zones, aid workers in disaster areas, or consumers in device-to-device (D2D) applications. Unfortunately, ad hoc networks are limited by interference due to nearby transmissions. Millimeter-wave (mmWave) devices offer several potential advantages for ad hoc networks including reduced interference due to directional antennas and building blockages, not to mention huge bandwidth channels for large data rates.. This paper uses a stochastic geometry approach to characterize the one-way and two-way signal-to-interference ratio distribution of a mmWave ad hoc network with directional antennas, random blockages, and ALOHA channel access. The interference-to-noise ratio shows that a fundamental limitation of an ad hoc network, interference, may still be an issue. The performance of mmWave ad hoc networks is bounded by the transmission capacity and area spectral efficiency. The results show that mmWave networks can support much higher densities and larger spectral efficiencies, even in the presence of blockage, compared with lower frequency communication for certain link distances. Due to the increased bandwidth, the rate coverage of mmWave can be much greater than lower frequency devices.
A Simple Homotopy Proximal Mapping for Compressive Sensing
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we present a novel yet simple homotopy proximal mapping algorithm for compressive sensing. The algorithm adopts a simple proximal mapping of the $\ell_1$ norm at each iteration and gradually reduces the regularization parameter for the $\ell_1$ norm. We prove a global linear convergence of the proposed homotopy proximal mapping (HPM) algorithm for solving compressive sensing under three different settings (i) sparse signal recovery under noiseless measurements, (ii) sparse signal recovery under noisy measurements, and (iii) nearly-sparse signal recovery under sub-gaussian noisy measurements. In particular, we show that when the measurement matrix satisfies Restricted Isometric Properties (RIP), our theoretical results in settings (i) and (ii) almost recover the best condition on the RIP constants for compressive sensing. In addition, in setting (iii), our results for sparse signal recovery are better than the previous results, and furthermore our analysis explicitly exhibits that more observations lead to not only more accurate recovery but also faster convergence. Compared with previous studies on linear convergence for sparse signal recovery, our algorithm is simple and efficient, and our results are better and provide more insights. Finally our empirical studies provide further support for the proposed homotopy proximal mapping algorithm and verify the theoretical results.
On abstract normalisation beyond neededness
Venue: arXiv cs.LO 2016
Year: 2016

We study normalisation of multistep strategies, strategies that reduce a set of redexes at a time, focussing on the notion of necessary sets, those which contain at least one redex that cannot be avoided in order to reach a normal form. This is particularly appealing in the setting of non-sequential rewrite systems, in which terms that are not in normal form may not have any needed redex. We first prove a normalisation theorem for abstract rewrite systems (ARS), a general rewriting framework encompassing many rewriting systems developed by P-A.Melliès in his PhD thesis. The theorem states that multistep strategies reducing so called necessary and never-gripping sets of redexes at a time are normalising in any ARS. Gripping refers to an abstract property reflecting the behavior of higher-order substitution. We then apply this result to the particular case of PPC, a calculus of patterns and to the lambda-calculus with parallel-or.
Multihop Caching-Aided Coded Multicasting for the Next Generation of Cellular Networks
Venue: arXiv cs.IT 2016
Year: 2016

Next generation of cellular networks deploying wireless distributed femtocaching infrastructure proposed by Golrezaei et. al. are studied. By taking advantage of multihop communications in each cell, the number of required femtocaching helpers is significantly reduced. This reduction of femtocaches is achieved by using the underutilized storage and communication capabilities in the User Terminals (UTs), which results in reducing the deployment costs of distributed femtocaches. A multihop index coding technique is proposed to code the cached contents in helpers to achieve order optimal capacity gains. This can serve as an efficient content delivery algorithm for the solution provided by Golrezaei et. al. As an example, we consider a wireless cellular system in which contents have a popularity distribution. It has been shown that if the contents follow a high content reuse popularity distribution, our approach can replace many unicast communication with multicast communication. We will prove that simple linear index codes found by heuristics based on graph coloring algorithms can achieve order optimal capacity under Zipfian content popularity distribution.
Gesture-based Continuous Authentication for Wearable Devices: the Google Glass Case
Venue: arXiv cs.CR 2016
Year: 2016

We study the feasibility of touch gesture behavioural biometrics for implicit authentication of users on a smartglass (Google Glass) by proposing a continuous authentication system using two classifiers: SVM with RBF kernel, and a new classifier based on Chebyshev's concentration inequality. Based on data collected from 30 volunteers, we show that such authentication is feasible both in terms of classification accuracy and computational load on smartglasses. We achieve a classification accuracy of up to 99% with only 75 training samples using behavioural biometric data from four different types of touch gestures. To show that our system can be generalized, we test its performance on touch data from smartphones and found the accuracy to be similar to smartglasses. Finally, our experiments on the permanence of gestures show that the negative impact of changing user behaviour with time on classification accuracy can be best alleviated by periodically replacing older training samples with new randomly chosen samples.
Provable Tensor Methods for Learning Mixtures of Generalized Linear Models
Venue: arXiv cs.LG 2016
Year: 2016

We consider the problem of learning mixtures of generalized linear models (GLM) which arise in classification and regression problems. Typical learning approaches such as expectation maximization (EM) or variational Bayes can get stuck in spurious local optima. In contrast, we present a tensor decomposition method which is guaranteed to correctly recover the parameters. The key insight is to employ certain feature transformations of the input, which depend on the input generative model. Specifically, we employ score function tensors of the input and compute their cross-correlation with the response variable. We establish that the decomposition of this tensor consistently recovers the parameters, under mild non-degeneracy conditions. We demonstrate that the computational and sample complexity of our method is a low order polynomial of the input and the latent dimensions.
Compact Compositional Models
Venue: arXiv cs.CV 2016
Year: 2016

Learning compact and interpretable representations is a very natural task, which has not been solved satisfactorily even for simple binary datasets. In this paper, we review various ways of composing experts for binary data and argue that competitive forms of interaction are best suited to learn low-dimensional representations. We propose a new composition rule that discourages experts from focusing on similar structures and that penalizes opposing votes strongly so that abstaining from voting becomes more attractive. We also introduce a novel sequential initialization procedure, which is based on a process of oversimplification and correction. Experiments show that with our approach very intuitive models can be learned.
Transition to congestion in communication/computation networks: from ideal to realistic resource allocation via Montecarlo simulations
Venue: arXiv cs.NI 2016
Year: 2016

We generalize previous studies on critical phenomena in communication networks by adding computational capabilities to the nodes to better describe real-world situations such as cloud computing. A set of tasks with random origin and destination with a multi-tier computational structure is distributed on a network modeled as a graph. The execution time (or latency) of each task is statically computed and the sum is used as the energy in a Montecarlo simulation in which the temperature parameter controls the resource allocation optimality. We study the transition to congestion by varying temperature and system load. A method to approximately recover the time-evolution of the system by interpolating the latency probability distributions is presented. This allows us to study the standard transition to the congested phase by varying the task production rate. We are able to reproduce the main known results on network congestion and to gain a deeper insight over the maximum theoretical performance of a system and its sensitivity to routing and load balancing errors.
An Ordinal Minimax Theorem
Venue: arXiv cs.GT 2016
Year: 2016

In the early 1950s Lloyd Shapley proposed an ordinal and set-valued solution concept for zero-sum games called \emph{weak saddle}. We show that all weak saddles of a given zero-sum game are interchangeable and equivalent. As a consequence, every such game possesses a unique set-based value.