Browsing by Subject "Affinity propagation"
Now showing 1 - 3 of 3
Results Per Page
Sort Options
Item Multi-scale error-correcting codes and their decoding using belief propagation(2014-05) Yoo, Yong Seok; Fiete, Ila; Vishwanath, SriramThis work is motivated from error-correcting codes in the brain. To counteract the effect of representation noise, a large number of neurons participate in encoding even low-dimensional variables. In many brain areas, the mean firing rates of neurons as a function of represented variable, called the tuning curve, have unimodal shape centered at different values, defining a unary code. This dissertation focuses on a new type of neural code where neurons have periodic tuning curves, with a diversity of periods. Neurons that exhibit this tuning are grid cells of the entorhinal cortex, which represent self-location in two-dimensional space. First, we investigate mutual information between such multi-scale codes and the coded variable as a function of tuning curve width. For decoding, we consider maximum likelihood (ML) and plausible neural network (NN) based models. For unary neural codes, Fisher information increases with narrower tuning, regardless of the decoding method. By contrast, for the multi-scale neural code, the optimal tuning curve width depends on the decoding method. While narrow tuning is optimal for ML decoding, a finite width, matched to statistics of the noise, is optimal with a NN decoder. This finding may explain why actual neural tuning curves have relatively wide tuning. Next, motivated by the observation that multi-scale codes involve non-trivial decoding, we examine a decoding algorithm based on belief propagation (BP) because BP promises certain gains in decoding efficiency. The decoding problem is first formulated as a subset selection problem on a graph and then approximately solved by BP. Even though the graph has many cycles, BP converges to a fixed point after few iterations. The mean square error of BP approaches to that of ML at high signal-to-noise ratios. Finally, using the multi-scale code, we propose a joint source-channel coding scheme that allows separate senders to transmit complementary information over additive Gaussian noise channels without cooperation. The receiver decodes one sender's codeword using the other as side information and achieves a lower distortion using the same number of transmissions. The proposed scheme offers a new framework to design distributed joint source-channel codes for continuous variables.Item On a class of distributed algorithms over networks and graphs(2011-05) Lee, Sang Hyun, 1977-; Vishwanath, Sriram; Vikalo, Haris; Powers, Edward J.; Ghosh, Joydeep; Sanghavi, Sujay; Qiu, LiliDistributed iterative algorithms are of great importance, as they are known to provide low-complexity and approximate solutions to what are otherwise high-dimensional intractable optimization problems. The theory of message-passing based algorithms is fairly well developed in the coding, machine learning and statistical physics literatures. Even though several applications of message-passing algorithms have already been identified, this work aims at establishing that a plethora of other applications exist where it can be of great importance. In particular, the goal of this work is to develop and demonstrate applications of this class of algorithms in network communications and computational biology. In the domain of communications, message-passing based algorithms provide distributed ways of inferring the optimal solution without the aid of a central agent for various optimization problems that happen in the resource allocation of communication networks. Our main framework is Affinity Propagation (AP), originally developed for clustering problems. We reinterpret this framework to unify the development of distributed algorithms for discrete resource allocation problems. Also, we consider a network-coded communication network, where continuous rate allocation is studied. We formulate an optimization problem with a linear cost function, and then utilize a Belief Propagation (BP) approach to determine a decentralized rate allocation strategy. Next, we move to the domain of computational biology, where graphical representations and computational biology play a major role. First, we consider the motif finding problem with several DNA sequences. In effect, this is a sequence matching problem, which can be modeled using various graphical representations and also solved using low-complexity algorithms based on message-passing techniques. In addition, we address the application of message-passing algorithms for a DNA sequencing problem where the one dimensional structure of a single DNA sequence is identified. We reinterpret the problem as being equivalent to the decoding of a nonlinear code. Based on the iterative decoding framework, we develop an appropriate graphical model which enables us to derive a message-passing algorithm to improve the performance of the DNA sequencing problem. Although this work consists of disparate application domains of communications, networks and computational biology, graphical models and distributed message-passing algorithms form a common underlying theme.Item Outcome prediction and structure discovery in healthcare data(2016-08) Arzeno-González, Natalia María; Vikalo, Haris; Ghosh, Joydeep; Lawson, Karla A; Sanghavi, Sujay; Vishwanath, SriramGrowing use of electronic medical records, advances in data mining and machine learning, and the continually increasing cost of healthcare in the United States drive the necessity of algorithmic solutions with the potential to improve patient care and reduce healthcare costs. Such algorithms can enable the identification of the most relevant parameters for predicting adverse events, reveal underlying physiological mechanisms of diseases, and determine likelihood of complications that may lead to rehospitalization of discharged patients. Key limitations in computational tools currently used in healthcare or with the potential to greatly benefit the healthcare system can be overcome by methods that allow for soft constraints or promote smoothness. In this dissertation we develop three main algorithms incorporating softness or smoothness in the constraints or solution and demonstrate applications in diverse aspects of healthcare with the potential to greatly reduce healthcare costs. We first develop an outcome prediction algorithm that preserves the clinical knowledge from the development of additive risk scores with hard thresholds (of the form add p points if variable x is above/below threshold t). This novel method is not only easily optimizable for different patient sub-populations, but reveals clinically interpretable information such as the maximum contribution of a physiologic variable to the risk score and the range of values for which risk increases. We then turn to overcoming limitations in two clustering settings. In a semi-supervised setting, where pairwise constraints (relationships between pairs of points) are available, we develop an algorithm capable of performing accurate clustering under noisy constraints. This is achieved via soft constraints that impose a penalty on the objective when violated. Finally, we examine the scenario where clustering data are available at multiple points in time under the assumption of temporal smoothness, i.e., data points are more likely to remain in the same cluster than to change cluster membership between consecutive time steps. In this setting, we develop an evolutionary clustering algorithm that automatically infers the number of clusters at each time and matches the clusters across time steps while finding a global clustering solution. The proposed schemes outperform existing methods in benchmark and non-healthcare datasets as well as in the tasks of mortality prediction from clinical data and breast cancer metastasis prediction from gene expression data. As an additional healthcare application, we use our proposed evolutionary clustering algorithm to study the evolution of health plan clusters inferred from medication adherence data and provide a detailed analysis of the clusters.