Search

Steady state analysis of dynamical systems for biological networks give rise to algebraic varieties in high-dimensional spaces whose study is of interest in their own right. We demonstrate this for the shuttle model of the Wnt signaling pathway. Here the variety is described by a polynomial system in 19 unknowns and 36 parameters. Current methods from computational algebraic geometry and combinatorics are applied to analyze this model., Comment: 24 pages, 2 figures

The canonical Wnt signaling pathway, mediated by $\beta$-catenin, is crucially involved in development, adult stem cell tissue maintenance and a host of diseases including cancer. We undertake analysis of different mathematical models of Wnt from the literature, and compare them to a new mechanistic model of Wnt signaling that targets spatial localization of key molecules. Using Bayesian methods we infer parameters for each of the models to mammalian Wnt signaling data and find that all models can fit this time course. We are able to overcome this lack of data by appealing to algebraic methods (concepts from chemical reaction network theory and matroid theory) to analyze the models without recourse to specific parameter values. These approaches provide insight into Wnt signaling: The new model (unlike any other investigated) permits a bistable switch in the system via control of shuttling and degradation parameters, corresponding to stem-like vs committed cell states in the differentiation hierarchy. Our analysis also identifies groups of variables that must be measured to fully characterize and discriminate between competing models, and thus serves as a guide for performing minimal experiments for model comparison., Comment: 37 pages, 6 figures; errors fixed and comparison with data

We investigate the problem of completing partial matrices to rank-one matrices in the standard simplex. The motivation for studying this problem comes from statistics: A lack of eligible completion can provide a falsification test for partial observations to come from the independence model. For each pattern of specified entries, we give equations and inequalities which are satisfied if and only if an eligible completion exists. We also describe the set of valid completions, and we optimize over this set., Comment: 21 pages, 4 figures, Related code at https://www.math.upenn.edu/~zvihr/probCompletion.html. This version is edited and reorganized

An affine variety induces the structure of an algebraic matroid on the set of coordinates of the ambient space. The matroid has two natural decorations: a circuit polynomial attached to each circuit, and the degree of the projection map to each base, called the base degree. Decorated algebraic matroids can be computed via symbolic computation using Groebner bases, or through linear algebra in the space of differentials (with decorations calculated using numerical algebraic geometry). Both algorithms are developed here. Failure of the second algorithm occurs on a subvariety called the non-matroidal or NM- locus. Decorated algebraic matroids have widespread relevance anywhere that coordinates have combinatorial significance. Examples are computed from applied algebra, in algebraic statistics and chemical reaction network theory, as well as more theoretical examples from algebraic geometry and matroid theory., Comment: 15 pages; added link to references, note on page 1, and small formatting fixes

This paper studies the properties of two kinds of matroids: (a) algebraic matroids and (b) finite and infinite matroids whose ground set have some canonical symmetry, for example row and column symmetry and transposition symmetry. For (a) algebraic matroids, we expose cryptomorphisms making them accessible to techniques from commutative algebra. This allows us to introduce for each circuit in an algebraic matroid an invariant called circuit polynomial, generalizing the minimal poly- nomial in classical Galois theory, and studying the matroid structure with multivariate methods. For (b) matroids with symmetries we introduce combinatorial invariants capturing structural properties of the rank function and its limit behavior, and obtain proofs which are purely combinatorial and do not assume algebraicity of the matroid; these imply and generalize known results in some specific cases where the matroid is also algebraic. These results are motivated by, and readily applicable to framework rigidity, low-rank matrix completion and determinantal varieties, which lie in the intersection of (a) and (b) where additional results can be derived. We study the corresponding matroids and their associated invariants, and for selected cases, we characterize the matroidal structure and the circuit polynomials completely.

We introduce the author-topic model, a generative model for documents that extends Latent Dirichlet Allocation (LDA; Blei, Ng, & Jordan, 2003) to include authorship information. Each author is associated with a multinomial distribution over topics and each topic is associated with a multinomial distribution over words. A document with multiple authors is modeled as a distribution over topics that is a mixture of the distributions associated with the authors. We apply the model to a collection of 1,700 NIPS conference papers and 160,000 CiteSeer abstracts. Exact inference is intractable for these datasets and we use Gibbs sampling to estimate the topic and author distributions. We compare the performance with two other generative models for documents, which are special cases of the author-topic model: LDA (a topic model) and a simple author model in which each author is associated with a distribution over words rather than a distribution over topics. We show topics recovered by the author-topic model, and demonstrate applications to computing similarity between authors and entropy of author output., Comment: Appears in Proceedings of the Twentieth Conference on Uncertainty in Artificial Intelligence (UAI2004)

We propose a hierarchy for approximate inference based on the Dobrushin, Lanford, Ruelle (DLR) equations. This hierarchy includes existing algorithms, such as belief propagation, and also motivates novel algorithms such as factorized neighbors (FN) algorithms and variants of mean field (MF) algorithms. In particular, we show that extrema of the Bethe free energy correspond to approximate solutions of the DLR equations. In addition, we demonstrate a close connection between these approximate algorithms and Gibbs sampling. Finally, we compare and contrast various of the algorithms in the DLR hierarchy on spin-glass problems. The experiments show that algorithms higher up in the hierarchy give more accurate results when they converge but tend to be less stable., Comment: Appears in Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence (UAI2005)

Latent topic models have been successfully applied as an unsupervised topic discovery technique in large document collections. With the proliferation of hypertext document collection such as the Internet, there has also been great interest in extending these approaches to hypertext [6, 9]. These approaches typically model links in an analogous fashion to how they model words - the document-link co-occurrence matrix is modeled in the same way that the document-word co-occurrence matrix is modeled in standard topic models. In this paper we present a probabilistic generative model for hypertext document collections that explicitly models the generation of links. Specifically, links from a word w to a document d depend directly on how frequent the topic of w is in d, in addition to the in-degree of d. We show how to perform EM learning on this model efficiently. By not modeling links as analogous to words, we end up using far fewer free parameters and obtain better link prediction results., Comment: Appears in Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (UAI2008)

We study curves consisting of unions of projective lines whose intersections are given by graphs. Under suitable hypotheses on the graph, these so-called \emph{graph curves} can be embedded in projective space as line arrangements. We discuss property $N_p$ for these embeddings and are able to produce products of linear forms that generate the ideal in certain cases. We also briefly discuss questions regarding the higher-dimensional subspace arrangements obtained by taking the secant varieties of graph curves., Comment: 15 pages; a major revision of v1

Mutual learning of a pair of tree parity machines with continuous and discrete weight vectors is studied analytically. The analysis is based on a mapping procedure that maps the mutual learning in tree parity machines onto mutual learning in noisy perceptrons. The stationary solution of the mutual learning in the case of continuous tree parity machines depends on the learning rate where a phase transition from partial to full synchronization is observed. In the discrete case the learning process is based on a finite increment and a full synchronized state is achieved in a finite number of steps. The synchronization of discrete parity machines is introduced in order to construct an ephemeral key-exchange protocol. The dynamic learning of a third tree parity machine (an attacker) that tries to imitate one of the two machines while the two still update their weight vectors is also analyzed. In particular, the synchronization times of the naive attacker and the flipping attacker recently introduced in [1] are analyzed. All analytical results are found to be in good agreement with simulation results.

Mutual learning process between two parity feed-forward networks with discrete and continuous weights is studied analytically, and we find that the number of steps required to achieve full synchronization between the two networks in the case of discrete weights is finite. The synchronization process is shown to be non-self-averaging and the analytical solution is based on random auxiliary variables. The learning time of an attacker that is trying to imitate one of the networks is examined analytically and is found to be much longer than the synchronization time. Analytical results are found to be in agreement with simulations.

The information processing abilities of a multilayer neural network with a number of hidden units scaling as the input dimension are studied using statistical mechanics methods. The mapping from the input layer to the hidden units is performed by general symmetric Boolean functions whereas the hidden layer is connected to the output by either discrete or continuous couplings. Introducing an overlap in the space of Boolean functions as order parameter the storage capacity if found to scale with the logarithm of the number of implementable Boolean functions. The generalization behaviour is smooth for continuous couplings and shows a discontinuous transition to perfect generalization for discrete ones., Comment: 4 pages, 2 figures

On-line and batch learning of a perceptron in a discrete weight space, where each weight can take $2 L+1$ different values, are examined analytically and numerically. The learning algorithm is based on the training of the continuous perceptron and prediction following the clipped weights. The learning is described by a new set of order parameters, composed of the overlaps between the teacher and the continuous/clipped students. Different scenarios are examined among them on-line learning with discrete/continuous transfer functions and off-line Hebb learning. The generalization error of the clipped weights decays asymptotically as $exp(-K \alpha^2)$/$exp(-e^{|\lambda| \alpha})$ in the case of on-line learning with binary/continuous activation functions, respectively, where $\alpha$ is the number of examples divided by N, the size of the input vector and $K$ is a positive constant that decays linearly with 1/L. For finite $N$ and $L$, a perfect agreement between the discrete student and the teacher is obtained for $\alpha \propto \sqrt{L \ln(NL)}$. A crossover to the generalization error $\propto 1/\alpha$, characterized continuous weights with binary output, is obtained for synaptic depth $L > O(\sqrt{N})$., Comment: 10 pages, 5 figs., submitted to PRE