An efficient solution to Hidden Markov Models on trees with coupled branches

• URL: http://arxiv.org/abs/2406.01663v1
• Date: Mon, 3 Jun 2024 18:00:00 GMT
• Title: An efficient solution to Hidden Markov Models on trees with coupled branches
• Authors: Farzan Vafa, Sahand Hormoz,
• Abstract summary: We extend the framework of Hidden Models (HMMs) on trees to address scenarios where the tree-like structure of the data includes coupled branches. We develop a programming algorithm that efficiently solves the likelihood, decoding, and parameter learning problems for tree-based HMMs with coupled branches.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Hidden Markov Models (HMMs) are powerful tools for modeling sequential data, where the underlying states evolve in a stochastic manner and are only indirectly observable. Traditional HMM approaches are well-established for linear sequences, and have been extended to other structures such as trees. In this paper, we extend the framework of HMMs on trees to address scenarios where the tree-like structure of the data includes coupled branches -- a common feature in biological systems where entities within the same lineage exhibit dependent characteristics. We develop a dynamic programming algorithm that efficiently solves the likelihood, decoding, and parameter learning problems for tree-based HMMs with coupled branches. Our approach scales polynomially with the number of states and nodes, making it computationally feasible for a wide range of applications and does not suffer from the underflow problem. We demonstrate our algorithm by applying it to simulated data and propose self-consistency checks for validating the assumptions of the model used for inference. This work not only advances the theoretical understanding of HMMs on trees but also provides a practical tool for analyzing complex biological data where dependencies between branches cannot be ignored.

Related papers

• Linear Mode Connectivity in Differentiable Tree Ensembles [13.704584231053675]
  Linear Mode Connectivity (LMC) refers to the phenomenon that remains consistent for linearly interpolated models in the parameter space. We first achieve LMC for soft tree neurons, which are tree-based differentiable models extensively used in practice.
  arXiv  Detail & Related papers  (2024-05-23T14:11:26Z)
• Rapid and Precise Topological Comparison with Merge Tree Neural Networks [7.443474354626664]
  We introduce the merge tree neural networks (MTNN), a learned neural network model designed for merge tree comparison. In particular, we speed up the prior state-of-the-art by more than 100x on the benchmark datasets while maintaining an error rate below 0.1%.
  arXiv  Detail & Related papers  (2024-04-08T21:26:04Z)
• Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles [6.664930499708017]
  The Shapley value (SV) is a concept in explainable artificial intelligence (XAI) research for quantifying additive feature attributions of predictions. We present TreeSHAP-IQ, an efficient method to compute any-order additive Shapley interactions for predictions tree-based models.
  arXiv  Detail & Related papers  (2024-01-22T16:08:41Z)
• Heterogenous Memory Augmented Neural Networks [84.29338268789684]
  We introduce a novel heterogeneous memory augmentation approach for neural networks. By introducing learnable memory tokens with attention mechanism, we can effectively boost performance without huge computational overhead. We show our approach on various image and graph-based tasks under both in-distribution (ID) and out-of-distribution (OOD) conditions.
  arXiv  Detail & Related papers  (2023-10-17T01:05:28Z)
• ARTree: A Deep Autoregressive Model for Phylogenetic Inference [6.935130578959931]
  We propose a deep autoregressive model for phylogenetic inference based on graph neural networks (GNNs) We demonstrate the effectiveness and efficiency of our method on a benchmark of challenging real data tree topology density estimation and variational phylogenetic inference problems.
  arXiv  Detail & Related papers  (2023-10-14T10:26:03Z)
• Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
  In this paper we offer a new perspective on the well established agglomerative clustering algorithm, focusing on recovery of hierarchical structure. We recommend a simple variant of the standard algorithm, in which clusters are merged by maximum average dot product and not, for example, by minimum distance or within-cluster variance. We demonstrate that the tree output by this algorithm provides a bona fide estimate of generative hierarchical structure in data, under a generic probabilistic graphical model.
  arXiv  Detail & Related papers  (2023-05-24T11:05:12Z)
• TreeFlow: Going beyond Tree-based Gaussian Probabilistic Regression [0.0]
  We introduce TreeFlow, the tree-based approach that combines the benefits of using tree ensembles with the capabilities of modeling flexible probability distributions. We evaluate the proposed method on challenging regression benchmarks with varying volume, feature characteristics, and target dimensionality.
  arXiv  Detail & Related papers  (2022-06-08T20:06:23Z)
• Entailment Tree Explanations via Iterative Retrieval-Generation Reasoner [56.08919422452905]
  We propose an architecture called Iterative Retrieval-Generation Reasoner (IRGR) Our model is able to explain a given hypothesis by systematically generating a step-by-step explanation from textual premises. We outperform existing benchmarks on premise retrieval and entailment tree generation, with around 300% gain in overall correctness.
  arXiv  Detail & Related papers  (2022-05-18T21:52:11Z)
• Complex Event Forecasting with Prediction Suffix Trees: Extended Technical Report [70.7321040534471]
  Complex Event Recognition (CER) systems have become popular in the past two decades due to their ability to "instantly" detect patterns on real-time streams of events. There is a lack of methods for forecasting when a pattern might occur before such an occurrence is actually detected by a CER engine. We present a formal framework that attempts to address the issue of Complex Event Forecasting.
  arXiv  Detail & Related papers  (2021-09-01T09:52:31Z)
• Probabilistic Case-based Reasoning for Open-World Knowledge Graph Completion [59.549664231655726]
  A case-based reasoning (CBR) system solves a new problem by retrieving cases' that are similar to the given problem. In this paper, we demonstrate that such a system is achievable for reasoning in knowledge-bases (KBs) Our approach predicts attributes for an entity by gathering reasoning paths from similar entities in the KB.
  arXiv  Detail & Related papers  (2020-10-07T17:48:12Z)
• Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies [76.83991682238666]
  Branch and Bound (B&B) is the exact tree search method typically used to solve Mixed-Integer Linear Programming problems (MILPs) We propose a novel imitation learning framework, and introduce new input features and architectures to represent branching.
  arXiv  Detail & Related papers  (2020-02-12T17:43:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.