Academic literature on the topic 'Search in graphs AND/OR with probabilistic transitions'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Search in graphs AND/OR with probabilistic transitions.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Journal articles on the topic "Search in graphs AND/OR with probabilistic transitions"
1
Lian, Xiang, Lei Chen, and Zi Huang. "Keyword Search Over Probabilistic RDF Graphs." IEEE Transactions on Knowledge and Data Engineering 27, no. 5 (2015): 1246–60. http://dx.doi.org/10.1109/tkde.2014.2365791.
Full text
2
SATO, TAISUKE, and PHILIPP MEYER. "Infinite probability computation by cyclic explanation graphs." Theory and Practice of Logic Programming 14, no. 6 (2013): 909–37. http://dx.doi.org/10.1017/s1471068413000562.
Full textAbstract:
AbstractTabling in logic programming has been used to eliminate redundant computation and also to stop infinite loop. In this paper we investigate another possibility of tabling, i.e. to compute an infinite sum of probabilities for probabilistic logic programs. Using PRISM, a logic-based probabilistic modeling language with a tabling mechanism, we generalize prefix probability computation for probabilistic context-free grammars (PCFGs) to probabilistic logic programs. Given a top-goal, we search for all proofs with tabling and obtain an explanation graph which compresses them and may be cyclic. We then convert the explanation graph to a set of linear probability equations and solve them by matrix operation. The solution gives us the probability of the top-goal, which, in nature, is an infinite sum of probabilities. Our general approach to prefix probability computation through tabling not only allows to deal with non-probabilistic context-free grammars such as probabilistic left-corner grammars but has applications such as plan recognition and probabilistic model checking and makes it possible to compute probability for probabilistic models describing cyclic relations.
3
Agarwal, Shubhangi, Sourav Dutta, and Arnab Bhattacharya. "ChiSeL." Proceedings of the VLDB Endowment 13, no. 10 (2020): 1654–68. http://dx.doi.org/10.14778/3401960.3401964.
Full textAbstract:
Subgraph querying is one of the most important primitives in many applications. Although the field is well studied for deterministic graphs, in many situations, the graphs are probabilistic in nature. In this paper, we address the problem of subgraph querying in large probabilistic labeled graphs. We employ a novel algorithmic framework, called ChiSeL, that uses the idea of statistical significance for approximate subgraph matching on uncertain graphs that have uncertainty in edges. For each candidate matching vertex in the target graph that matches a query vertex, we compute its statistical significance using the chi-squared statistic. The search algorithm then proceeds in a greedy manner by exploring the vertex neighbors having the largest chi-square score. In addition to edge uncertainty, we also show how ChiSeL can handle uncertainty in labels and/or vertices. Experiments on large real-life graphs show the efficiency and effectiveness of our algorithm.
4
Rajaraman, Mabaran, Glenn Philen, and Kenji Shimada. "Tracking Tagged Inventory in Unstructured Environments Through Probabilistic Dependency Graphs." Logistics 3, no. 4 (2019): 21. http://dx.doi.org/10.3390/logistics3040021.
Full textAbstract:
Logging and tracking raw materials, workpieces and engineered products for seamless and quick pulls is a complex task in the construction and shipbuilding industries due to lack of structured storage solutions. Additional uncertainty is introduced if workpieces are stacked and moved by multiple stakeholders without maintaining an active and up-to-date log of such movements. While there are frameworks proposed to improve workpiece pull times using a variety of tracking modes based on deterministic approaches, there is little discussion of cases wherein direct observations are sparse due to occlusions from stacking and interferences. Our work addresses this problem by: logging visible part locations and timestamps, through a network of custom designed observation devices; and building a graph-based model to identify events that highlight part interactions and estimate stack formation to search for parts that are not directly observable. By augmenting the site workers and equipment with our wearable devices, we avoid adding additional cognitive effort for the workers. Native building blocks of the graph-based model were evaluated through simulations. Experiments were also conducted in an active shipyard to validate our proposed system.
5
Rojas-Guzmán, Carlos, and Mark A. Kramer. "An Evolutionary Computing Approach to Probabilistic Reasoning on Bayesian Networks." Evolutionary Computation 4, no. 1 (1996): 57–85. http://dx.doi.org/10.1162/evco.1996.4.1.57.
Full textAbstract:
Bayesian belief networks can be used to represent and to reason about complex systems with uncertain or incomplete information. Bayesian networks are graphs capable of encoding and quantifying probabilistic dependence and conditional independence among variables. Diagnostic reasoning, also referred to as abductive inference, determining the most probable explanation (MPE), or finding the maximum a posteriori instantiation (MAP), involves determining the global most probable system description given the values of any subset of variables. In some cases abductive inference can be performed with exact algorithms using distributed network computations, but the problem is NP-hard, and complexity increases significantly with the presence of undirected cycles, the number of discrete states per variable, and the number of variables in the network. This paper describes an approximate method composed of a graph-based evolutionary algorithm that uses nonbinary alphabets, graphs instead of strings, and graph operators to perform abductive inference on multiply connected networks for which systematic search methods are not feasible. The motivation, basis, and adequacy of the method are discussed, and experimental results are presented.
6
Chen, Xuelu, Muhao Chen, Weijia Shi, Yizhou Sun, and Carlo Zaniolo. "Embedding Uncertain Knowledge Graphs." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 3363–70. http://dx.doi.org/10.1609/aaai.v33i01.33013363.
Full textAbstract:
Embedding models for deterministic Knowledge Graphs (KG) have been extensively studied, with the purpose of capturing latent semantic relations between entities and incorporating the structured knowledge they contain into machine learning. However, there are many KGs that model uncertain knowledge, which typically model the inherent uncertainty of relations facts with a confidence score, and embedding such uncertain knowledge represents an unresolved challenge. The capturing of uncertain knowledge will benefit many knowledge-driven applications such as question answering and semantic search by providing more natural characterization of the knowledge. In this paper, we propose a novel uncertain KG embedding model UKGE, which aims to preserve both structural and uncertainty information of relation facts in the embedding space. Unlike previous models that characterize relation facts with binary classification techniques, UKGE learns embeddings according to the confidence scores of uncertain relation facts. To further enhance the precision of UKGE, we also introduce probabilistic soft logic to infer confidence scores for unseen relation facts during training. We propose and evaluate two variants of UKGE based on different confidence score modeling strategies. Experiments are conducted on three real-world uncertain KGs via three tasks, i.e. confidence prediction, relation fact ranking, and relation fact classification. UKGE shows effectiveness in capturing uncertain knowledge by achieving promising results, and it consistently outperforms baselines on these tasks.
7
KOZMA, ROBERT, MARKO PULJIC, and LEONID PERLOVSKY. "MODELING GOAL-ORIENTED DECISION MAKING THROUGH COGNITIVE PHASE TRANSITIONS." New Mathematics and Natural Computation 05, no. 01 (2009): 143–57. http://dx.doi.org/10.1142/s1793005709001246.
Full textAbstract:
Cognitive experiments indicate the presence of discontinuities in brain dynamics during high-level cognitive processing. Non-linear dynamic theory of brains pioneered by Freeman explains the experimental findings through the theory of metastability and edge-of-criticality in cognitive systems, which are key properties associated with robust operation and fast and reliable decision making. Recently, neuropercolation has been proposed to model such critical behavior. Neuropercolation is a family of probabilistic models based on the mathematical theory of bootstrap percolations on lattices and random graphs and motivated by structural and dynamical properties of neural populations in the cortex. Neuropercolation exhibits phase transitions and it provides a novel mathematical tool for studying spatio-temporal dynamics of multi-stable systems. The present work reviews the theory of cognitive phase transitions based on neuropercolation models and outlines the implications to decision making in brains and in artificial designs.
8
Bueno, Thiago P., Leliane N. De Barros, Denis D. Mauá, and Scott Sanner. "Deep Reactive Policies for Planning in Stochastic Nonlinear Domains." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 7530–37. http://dx.doi.org/10.1609/aaai.v33i01.33017530.
Full textAbstract:
Recent advances in applying deep learning to planning have shown that Deep Reactive Policies (DRPs) can be powerful for fast decision-making in complex environments. However, an important limitation of current DRP-based approaches is either the need of optimal planners to be used as ground truth in a supervised learning setting or the sample complexity of high-variance policy gradient estimators, which are particularly troublesome in continuous state-action domains. In order to overcome those limitations, we introduce a framework for training DRPs in continuous stochastic spaces via gradient-based policy search. The general approach is to explicitly encode a parametric policy as a deep neural network, and to formulate the probabilistic planning problem as an optimization task in a stochastic computation graph by exploiting the re-parameterization of the transition probability densities; the optimization is then solved by leveraging gradient descent algorithms that are able to handle non-convex objective functions. We benchmark our approach against stochastic planning domains exhibiting arbitrary differentiable nonlinear transition and cost functions (e.g., Reservoir Control, HVAC and Navigation). Results show that DRPs with more than 125,000 continuous action parameters can be optimized by our approach for problems with 30 state fluents and 30 action fluents on inexpensive hardware under 6 minutes. Also, we observed a speedup of 5 orders of magnitude in the average inference time per decision step of DRPs when compared to other state-of-the-art online gradient-based planners when the same level of solution quality is required.
9
Drosatos, George, and Eleni Kaldoudi. "A probabilistic semantic analysis of eHealth scientific literature." Journal of Telemedicine and Telecare 26, no. 7-8 (2019): 414–32. http://dx.doi.org/10.1177/1357633x19846252.
Full textAbstract:
Introduction eHealth emerged as an interdisciplinary research area about 70 years ago. This study employs probabilistic techniques to semantically analyse scientific literature related to the field of eHealth in order to identify topics and trends and discuss their comparative evolution. Methods Authors collected titles and abstracts of published literature on eHealth as indexed in PubMed. Basic statistical and bibliometric techniques were applied to overall describe the collected corpus; Latent Dirichlet Allocation was employed for unsupervised topics identification; topics trends analysis was performed, and correlation graphs were plotted were relevant. Results A total of 30,425 records on eHealth were retrieved from PubMed (all records till 31 December 2017, search on 8 May 2018) and 23,988 of these were included to the study corpus. eHealth domain shows a growth higher than the growth of the entire PubMed corpus, with a mean increase of eHealth corpus proportion of about 7% per year for the last 20 years. Probabilistic topics modelling identified 100 meaningful topics, which were organised by the authors in nine different categories: general; service model; disease; medical specialty; behaviour and lifestyle; education; technology; evaluation; and regulatory issues. Discussion Trends analysis shows a continuous shift in focus. Early emphasis on medical image transmission and system integration has been replaced by increased focus on standards, wearables and sensor devices, now giving way to mobile applications, social media and data analytics. Attention on disease is also shifting, from initial popularity of surgery, trauma and acute heart disease, to the emergence of chronic disease support, and the recent attention to cancer, infectious disease, mental disorders, paediatrics and perinatal care; most interestingly the current swift increase is in research related to lifestyle and behaviour change. The steady growth of all topics related to assessment and various systematic evaluation techniques indicates a maturing research field that moves towards real world application.
10
Harris, Marcus, and Martin Zwick. "Graphical Models in Reconstructability Analysis and Bayesian Networks." Entropy 23, no. 8 (2021): 986. http://dx.doi.org/10.3390/e23080986.
Full textAbstract:
Reconstructability Analysis (RA) and Bayesian Networks (BN) are both probabilistic graphical modeling methodologies used in machine learning and artificial intelligence. There are RA models that are statistically equivalent to BN models and there are also models unique to RA and models unique to BN. The primary goal of this paper is to unify these two methodologies via a lattice of structures that offers an expanded set of models to represent complex systems more accurately or more simply. The conceptualization of this lattice also offers a framework for additional innovations beyond what is presented here. Specifically, this paper integrates RA and BN by developing and visualizing: (1) a BN neutral system lattice of general and specific graphs, (2) a joint RA-BN neutral system lattice of general and specific graphs, (3) an augmented RA directed system lattice of prediction graphs, and (4) a BN directed system lattice of prediction graphs. Additionally, it (5) extends RA notation to encompass BN graphs and (6) offers an algorithm to search the joint RA-BN neutral system lattice to find the best representation of system structure from underlying system variables. All lattices shown in this paper are for four variables, but the theory and methodology presented in this paper are general and apply to any number of variables. These methodological innovations are contributions to machine learning and artificial intelligence and more generally to complex systems analysis. The paper also reviews some relevant prior work of others so that the innovations offered here can be understood in a self-contained way within the context of this paper.
Dissertations / Theses on the topic "Search in graphs AND/OR with probabilistic transitions"
1
Delgado, Daniel Javier Casani. "Planejamento probabilístico como busca num espaço de transição de estados." Universidade de São Paulo, 2013. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-04062013-060258/.
Full textAbstract:
Um dos modelos mais usados para descrever problemas de planejamento probabilístico, i.e., planejamento de ações com efeitos probabilísticos, é o processo de decisão markoviano (Markov Decision Process - MDP). Soluções tradicionais são baseadas em programação dinâmica, sendo as mais ecientes aquelas baseadas em programação dinâmica em tempo real (Real-Time Dynamic Programming - RTDP), por explorarem somente os estados alcançáveis a partir de um dado estado inicial. Por outro lado, existem soluções ecientes baseadas em métodos de busca heurística em um grafo AND/OR, sendo que os nós AND representam os efeitos probabilísticos das ações e os nós OR representam as escolhas de ações alternativas. Tais soluções também exploram somente estados alcançáveis a partir de um estado inicial porém, guardam um subgrafo solução parcial e usam programação dinâmica para a atualização do custo dos nós desse subgrafo. No entanto, problemas com grandes espaços de estados limitam o uso prático desses métodos. MDPs fatorados permitem explorar a estrutura do problema, representando MDPs muito grandes de maneira compacta e assim, favorecer a escalabilidade das soluções. Neste trabalho, apresentamos uma análise comparativa das diferentes soluções para MDPs, com ênfase naquelas que fazem busca heurística e as comparamos com soluções baseadas em programação dinâmica assíncrona, consideradas o estado da arte das soluções de MPDs. Além disso, propomos um novo algoritmo de busca heurística para MDPs fatorados baseado no algoritmo ILAO* e o testamos nos problemas da competição de planejamento probabilístico IPPC-2011.<br>One of the most widely used models to describe probabilistic planning problems, i.e., planning of actions with probabilistic eects, is the Markov Decision Process - MDP. The traditional solutions are based on dynamic programming, whereas the most ecient solutions are based on Real-Time Dynamic Programming - RTDP, which explore only the reachable states from a given initial state. Moreover, there are ecient solutions based on search methods in a AND/OR graph, where AND nodes represent the probabilistic eects of an action and OR nodes represent the choices of alternative actions. These solutions also explore only reachable states but maintain the parcial subgraph solution, using dynamic programming for updating the cost of nodes of these subgraph. However, problems with large state spaces limit the practical use of these methods. Factored representation of MDPs allow to explore the structure of the problem, and can represent very large MDPs compactly and thus improve the scalability of the solutions. In this dissertation, we present a comparative analysis of dierent solutions for MDPs, with emphasis on heuristic search methods. We compare the solutions which are based on asynchronous dynamic programming which are also considered the state of the art. We also propose a new factored algorithm based on the search algorithm ILAO*. It is also tested by using the problems of the International Probabilistic Planning Competition IPPC-2011.
Book chapters on the topic "Search in graphs AND/OR with probabilistic transitions"
1
Paul, Swarna Kamal, Prince Gupta, and Parama Bhaumik. "Learning to Solve Single Variable Linear Equations by Universal Search with Probabilistic Program Graphs." In Advances in Intelligent Systems and Computing. Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-16681-6_31.
Full text
2
"The Propriety of Phase Transitions in Random Graphs." In Progress in Pure and Applied Discrete Mathematics, Vol. 1: Probabilistic Methods in Discrete Mathematics. De Gruyter, 1993. http://dx.doi.org/10.1515/9783112318980-023.
Full textConference papers on the topic "Search in graphs AND/OR with probabilistic transitions"
1
Emamjomeh-Zadeh, Ehsan, David Kempe, and Vikrant Singhal. "Deterministic and probabilistic binary search in graphs." In STOC '16: Symposium on Theory of Computing. ACM, 2016. http://dx.doi.org/10.1145/2897518.2897656.
Full text
2
Tong, Yongxin, Xiaofei Zhang, Caleb Chen Cao, and Lei Chen. "Efficient Probabilistic Supergraph Search Over Large Uncertain Graphs." In CIKM '14: 2014 ACM Conference on Information and Knowledge Management. ACM, 2014. http://dx.doi.org/10.1145/2661829.2661872.
Full text
3
Trösser, Fulya, Simon de Givry, and George Katsirelos. "Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming." In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/584.
Full textAbstract:
Bayesian networks are probabilistic graphical models with a wide range of application areas including gene regulatory networks inference, risk analysis and image processing. Learning the structure of a Bayesian network (BNSL) from discrete data is known to be an NP-hard task with a superexponential search space of directed acyclic graphs. In this work, we propose a new polynomial time algorithm for discovering a subset of all possible cluster cuts, a greedy algorithm for approximately solving the resulting linear program, and a generalized arc consistency algorithm for the acyclicity constraint. We embed these in the constraint programming-based branch-and-bound solver CPBayes and show that, despite being suboptimal, they improve performance by orders of magnitude. The resulting solver also compares favorably with GOBNILP, a state-of-the-art solver for the BNSL problem which solves an NP-hard problem to discover each cut and solves the linear program exactly.
4
Medya, Sourav, Tiyani Ma, Arlei Silva, and Ambuj Singh. "A Game Theoretic Approach For Core Resilience." In Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}. International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/ijcai.2020/480.
Full textAbstract:
K-cores are maximal induced subgraphs where all vertices have degree at least k. These dense patterns have applications in community detection, network visualization and protein function prediction. However, k-cores can be quite unstable to network modifications, which motivates the question: How resilient is the k-core structure of a network, such as the Web or Facebook, to edge deletions? We investigate this question from an algorithmic perspective. More specifically, we study the problem of computing a small set of edges for which the removal minimizes the k-core structure of a network. This paper provides a comprehensive characterization of the hardness of the k-core minimization problem (KCM), including innaproximability and parameterized complexity. Motivated by these challenges, we propose a novel algorithm inspired by Shapley value---a cooperative game-theoretic concept--- that is able to leverage the strong interdependencies in the effects of edge removals in the search space. We efficiently approximate Shapley values using a randomized algorithm with probabilistic guarantees. Our experiments, show that the proposed algorithm outperforms competing solutions in terms of k-core minimization while being able to handle large graphs. Moreover, we illustrate how KCM can be applied in the analysis of the k-core resilience of networks.