1,721,004 research outputs found
Protein Fold Recognition using Markov Logic Networks
No full textProtein fold recognition is the problem of determining whether a given protein sequence folds into a
previously observed structure. An uncertainty complication is that it is not always true that the structure
has been previously observed. Markov logic networks (MLNs) are a powerful representation that combines
first-order logic and probability by attaching weights to first-order formulas and using these as templates
for features of Markov networks. In this chapter, we describe a simple temporal extension of MLNs that
is able to deal with sequences of logical atoms. We also propose iterated robust tabu search (IRoTS) for
maximum a posteriori (MAP) inference and Markov Chain-IRoTS (MC-IRoTS) for conditional inference
in the new framework. We show how MC-IRoTS can also be used for discriminative weight learning. We
describe how sequences of protein secondary structure can be modeled through the proposed language and
show through some preliminary experiments the promise of our approach for the problem of protein fold
recognition from these sequences
Intelligent Text Processing Techniques for Textual-Profile Gene Characterization
No full textWe present a suite ofMachine Learning and knowledge-based
components for textual-profile based gene prioritization. Most genetic
diseases are characterized by many potential candidate genes that can
cause the disease. Gene expression analysis typically produces a large
number of co-expressed genes that could be potentially responsible for
a given disease. Extracting prior knowledge from text-based genomic
information sources is essential in order to reduce the list of potential
candidate genes to be then further analyzed in laboratory. In this paper
we present a suite of Machine Learning algorithms and knowledge-based
components for improving the computational gene prioritization process.
The suite includes basic Natural Language Processing capabilities,
advanced text classification and clustering algorithms, robust information
extraction components based on qualitative and quantitative keyword
extraction methods and exploitation of lexical knowledge bases for
semantic text processing
Boosting learning and inference in Markov logic through metaheuristics
No full textMarkov Logic (ML) combines Markov networks (MNs) and first-order logic by attaching weights to first-order formulas and using these as templates for features of MNs. State-of-the-art structure learning algorithms in ML maximize the likelihood of a database by performing a greedy search in the space of structures. This can lead to suboptimal results because of the incapability of these approaches to escape local optima. Moreover, due to the combinatorially explosive space of potential candidates these methods are computationally prohibitive. We propose a novel algorithm for structure learning in ML, based on the Iterated Local Search (ILS) metaheuristic that explores the space of structures through a biased sampling of the set of local optima. We show through real-world experiments that the algorithm improves accuracy and learning time over the state-of-the-art algorithms. On the other side MAP and conditional inference for ML are hard computational tasks. This paper presents two algorithms for these tasks based on the Iterated Robust Tabu Search (IRoTS) metaheuristic. The first algorithm performs MAP inference and we show through extensive experiments that it improves over the state-of-the-art algorithm in terms of solution quality and inference time. The second algorithm combines IRoTS steps with simulated annealing steps for conditional inference and we show through experiments that it is faster than the current state-of-the-art algorithm maintaining the same inference quality
A Progressive Technique for Identifying Known Shapes in Images
No full textInformation Retrieval in digital libraries is at the same time a hard task and a crucial issue. While the primary type of information available in digital documents is usually text, images play a very important role because they pictorially describe concepts that are dealt with in the document. Unfortunately, the semantic gap separating such a visual content from the underlying meaning is very wide, and additionally image processing techniques are usually very demanding in computational resources. Hence, only recently the area of Content-Based Image Retrieval has gained more attention. In this paper we describe a new technique to identify known objects in a picture. It is based on shape contours, and works by progressive approximations to save computational resources and to improve preliminary shape extraction. Small (controlled) and more extensive experiments are illustrated, yielding interesting results
Efficient MAP Inference for Statistical Relational Models through Hybrid Metaheuristics
No full textStatistical Relational Models are state-of-the-art representation formalisms at the intersection of logical and statistical machine learning. One of the most promising models is Markov Logic (ML) which combines Markov networks (MNs) and first-order logic by attaching weights to first-order formulas and using these as templates for features of MNs. MAP inference in ML is the task of finding the most likely state of a set of output variables given the state of the input variables and this problem is NP-hard. In this paper we present an algorithm for this inference task based on the Iterated Local Search (ILS) and Robust Tabu Search (RoTS) metaheuristics. The algorithm performs a biased sampling of the set of local optima by using RoTS as a local search procedure and repetitively jumping in the search space through a perturbation operator, focusing the search not on the full space of solutions but on a smaller subspace defined by the solutions that are locally optimal for the optimization engine. We show through extensive experiments in real-world domains that it improves over the state-of-the-art algorithm in terms of solution quality and inference time
A Distance-based Technique for non-Manhattan Layout Analysis
No full textLayout analysis is a fundamental step in automatic document processing. Many different techniques have been proposed to perform this task. Some follow a top-down approach: they start by identifying the high level components of the page structure and then recursively split them until basic blocks are found. On the other hand, bottom-up approaches start with the smallest elements (e.g., the pixels in case of digitized document) and then recursively merge them into higher level components. A first limitation of such methods is that most of them are designed to deal only with digitized documents and hence are not applicable to native digital documents which are nowadays pervasive. Furthermore, top-down and most of bottom-up methods are able to process Manhattan layout documents only. In this work, we propose a general bottom-up strategy to tackle the layout analysis of (possibly) non-Manhattan documents, and two specializations of it to handle both bitmap and PS/PDF sources. It was successfully embedded and tested in the DOMINUS document management system
Towards Multistrategic Statistical Relational Learning
No full textStatistical Relational Learning (SRL) is a growing field in Machine Learning that aims at the integration of logic-based learning approaches with probabilistic graphical models. Markov Logic Networks (MLNs) are one of the state-of-the-art SRL models that combine first-order logic and Markov networks (MNs) by attaching weights to first-order formulas and viewing these as templates for features of MNs. Learning models in SRL consists in learning the structure (logical clauses in MLNs) and the parameters (weights for each clause in MLNs). Structure learning of MLNs is performed by maximizing a likelihood function (or a function thereof) over relational databases and MLNs have been successfully applied to problems in relational and uncertain domains. However, most complex domains are characterized by incomplete data. Until now SRL models have mostly used Expectation-Maximization (EM) for learning statistical parameters under missing values. Multistrategic learning in the relational setting has been a successful approach to dealing with complex problems where multiple inference mechanisms can help solve different subproblems. Abduction is an inference strategy that has been proven useful for completing missing values in observations. In this paper we propose two frameworks for integrating abduction in SRL models. The first tightly integrates logical abduction with structure and parameter learning of MLNs in a single step. During structure search guided by conditional likelihood, clause evaluation is performed by first trying to logically abduce missing values in the data and then by learning optimal pseudo-likelihood parameters using the completed data. The second approach integrates abduction with Structural EM of [17] by performing logical abductive inference in the E-step and then by trying to maximize parameters in the M-step
High Performing Algorithms for MAP and Conditional Inference in Markov Logic
No full textMarkov Logic (ML) combines Markov networks (MNs) and first-order logic by attaching weights to first-order formulas and using these as templates for features of MNs. However, MAP and conditional inference in ML are hard computational tasks. This paper presents two algorithms for these tasks based on the Iterated Robust Tabu Search (IRoTS) metaheuristic. The first algorithm performs MAP inference by performing a biased sampling of the set of local optima. Extensive experiments show that it improves over the state-of-the-art algorithm in terms of solution quality and inference times. The second algorithm combines IRoTS with simulated annealing for conditional inference and we show through experiments that it is faster than the current state-of-the-art algorithm maintaining the same inference quality
- …
